On the Optimal Communication Weights in Distributed Optimization Algorithms
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913227817877504 |
|---|---|
| author | Colla, Sebastien Hendrickx, Julien M. |
| author_facet | Colla, Sebastien Hendrickx, Julien M. |
| contents | We establish that in distributed optimization, the prevalent strategy of minimizing the second-largest eigenvalue modulus (SLEM) of the averaging matrix for selecting communication weights, while optimal for existing theoretical performance bounds, is generally not optimal regarding the exact worst-case performance of the algorithms. This exact performance can be computed using the Performance Estimation Problem (PEP) approach. We thus rely on PEP to formulate an optimization problem that determines the optimal communication weights for a distributed optimization algorithm deployed on a specified undirected graph. Our results show that the optimal weights can outperform the weights minimizing the second-largest eigenvalue modulus (SLEM) of the averaging matrix. This suggests that the SLEM is not the best characterization of weighted network performance for decentralized optimization. Additionally, we explore and compare alternative heuristics for weight selection in distributed optimization. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_05705 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Optimal Communication Weights in Distributed Optimization Algorithms Colla, Sebastien Hendrickx, Julien M. Optimization and Control Multiagent Systems We establish that in distributed optimization, the prevalent strategy of minimizing the second-largest eigenvalue modulus (SLEM) of the averaging matrix for selecting communication weights, while optimal for existing theoretical performance bounds, is generally not optimal regarding the exact worst-case performance of the algorithms. This exact performance can be computed using the Performance Estimation Problem (PEP) approach. We thus rely on PEP to formulate an optimization problem that determines the optimal communication weights for a distributed optimization algorithm deployed on a specified undirected graph. Our results show that the optimal weights can outperform the weights minimizing the second-largest eigenvalue modulus (SLEM) of the averaging matrix. This suggests that the SLEM is not the best characterization of weighted network performance for decentralized optimization. Additionally, we explore and compare alternative heuristics for weight selection in distributed optimization. |
| title | On the Optimal Communication Weights in Distributed Optimization Algorithms |
| topic | Optimization and Control Multiagent Systems |
| url | https://arxiv.org/abs/2402.05705 |