Several Performance Bounds on Decentralized Online Optimization are Highly Conservative and Potentially Misleading
This work addresses misleading performance analysis for researchers and practitioners in decentralized optimization, though it is incremental as it refines existing methods rather than introducing new paradigms.
The paper tackled the problem of conservative performance bounds in Decentralized Online Optimization algorithms, showing that existing guarantees are often off by multiple orders of magnitude and can mislead algorithm selection, with tuning step-sizes improving worst-case regret by up to 20%.
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.