Several Performance Bounds on Decentralized Online Optimization are Highly Conservative and Potentially Misleading
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914027512266752 |
|---|---|
| author | Meunier, Erwan Hendrickx, Julien M. |
| author_facet | Meunier, Erwan Hendrickx, Julien M. |
| contents | We analyze Decentralized Online Optimization algorithms using the Performance Estimation Problem approach which allows, to automatically compute exact worst-case performance of optimization algorithms. Our analysis shows that several available performance guarantees are very conservative, sometimes by multiple orders of magnitude, and can lead to misguided choices of algorithm. Moreover, at least in terms of worst-case performance, some algorithms appear not to benefit from inter-agent communications for a significant period of time. We show how to improve classical methods by tuning their step-sizes, and find that we can save up to 20% on their actual worst-case performance regret. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_06466 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Several Performance Bounds on Decentralized Online Optimization are Highly Conservative and Potentially Misleading Meunier, Erwan Hendrickx, Julien M. Optimization and Control Artificial Intelligence Distributed, Parallel, and Cluster Computing Multiagent Systems We analyze Decentralized Online Optimization algorithms using the Performance Estimation Problem approach which allows, to automatically compute exact worst-case performance of optimization algorithms. Our analysis shows that several available performance guarantees are very conservative, sometimes by multiple orders of magnitude, and can lead to misguided choices of algorithm. Moreover, at least in terms of worst-case performance, some algorithms appear not to benefit from inter-agent communications for a significant period of time. We show how to improve classical methods by tuning their step-sizes, and find that we can save up to 20% on their actual worst-case performance regret. |
| title | Several Performance Bounds on Decentralized Online Optimization are Highly Conservative and Potentially Misleading |
| topic | Optimization and Control Artificial Intelligence Distributed, Parallel, and Cluster Computing Multiagent Systems |
| url | https://arxiv.org/abs/2509.06466 |