582. Computer-Aided Analysis of Decentralized Online Optimization Algorithms
Invited abstract in session TB-8: Systematic and computer-aided analyses IV: Online & distributed gradient methods, stream Systematic and computer-aided analyses of optimization algorithms.
Tuesday, 10:30-12:30Room: B100/7007
Authors (first author is the speaker)
| 1. | Erwan Meunier
|
| ICTEAM, UCLouvain | |
| 2. | Julien Hendrickx
|
| ICTEAM |
Abstract
We present a novel application of the Performance Estimation Problem (PEP) framework to Decentralized Online Optimization (DOO), enabling the automatic computation of exact worst-case performance bounds for popular algorithms in this setting, would they be Projection-based, Projection-Free or relying on the Mirror-Descent scheme. Our findings reveal that existing theoretical guarantees can significantly overestimate true worst-case behavior, often by several orders of magnitude, potentially leading to suboptimal algorithmic choices in practice. Notably, we also uncover that certain algorithms do not benefit from inter-agent communication in the worst-case, challenging common intuitions about decentralized cooperation. By leveraging PEP-based analysis, we propose a principled way of refining step-size strategies. Thanks to this approach, we show that the worst-case regret of classical methods can be reduced by up to 20%. This work highlights the value of near tight performance estimation for the principled design and deployment of decentralized optimization algorithms.
Keywords
- Computer-aided algorithm analysis
- Distributed optimization
- Stochastic optimization
Status: accepted
Back to the list of papers