Exponential convergence of a distributed divide-and-conquer algorithm for constrained convex optimization on networks
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914071452844032 |
|---|---|
| author | Emirov, Nazar Song, Guohui Sun, Qiyu |
| author_facet | Emirov, Nazar Song, Guohui Sun, Qiyu |
| contents | We propose a divide-and-conquer (DAC) algorithm for constrained convex optimization over networks, where the global objective is the sum of local objectives attached to individual agents. The algorithm is fully distributed: each iteration solves local subproblems around selected fusion centers and coordinates only with neighboring fusion centers. Under standard assumptions of smoothness, strong convexity, and locality on the objective function, together with polynomial growth conditions on the underlying graph, we establish exponential convergence of the DAC iterations and derive explicit bounds for both exact and inexact local solvers. Numerical experiments on three representative losses ($L_2$ distance, quadratic, and entropy) confirm the theory and demonstrate scalability and effectiveness. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_01511 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Exponential convergence of a distributed divide-and-conquer algorithm for constrained convex optimization on networks Emirov, Nazar Song, Guohui Sun, Qiyu Optimization and Control Distributed, Parallel, and Cluster Computing Numerical Analysis We propose a divide-and-conquer (DAC) algorithm for constrained convex optimization over networks, where the global objective is the sum of local objectives attached to individual agents. The algorithm is fully distributed: each iteration solves local subproblems around selected fusion centers and coordinates only with neighboring fusion centers. Under standard assumptions of smoothness, strong convexity, and locality on the objective function, together with polynomial growth conditions on the underlying graph, we establish exponential convergence of the DAC iterations and derive explicit bounds for both exact and inexact local solvers. Numerical experiments on three representative losses ($L_2$ distance, quadratic, and entropy) confirm the theory and demonstrate scalability and effectiveness. |
| title | Exponential convergence of a distributed divide-and-conquer algorithm for constrained convex optimization on networks |
| topic | Optimization and Control Distributed, Parallel, and Cluster Computing Numerical Analysis |
| url | https://arxiv.org/abs/2510.01511 |