# Several Performance Bounds on Decentralized Online Optimization are Highly Conservative and Potentially Misleading

arXiv: https://arxiv.org/abs/2509.06466 · HTML: https://mlsanity.com/paper/2509.06466/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 17 references that are in the map.
- First posted on arXiv 8 Sep 2025.

## Builds on (most cited first, 9 of 9)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methods](https://mlsanity.com/paper/1502.05666/) (2015)
- [Optimal Complexity and Certification of Bregman First-Order Methods](https://mlsanity.com/paper/1911.08510/) (2019)
- [Distributed Mirror Descent for Online Composite Optimization](https://mlsanity.com/paper/2004.00837/) (2020)
- [Automatic Performance Estimation for Decentralized Optimization](https://mlsanity.com/paper/2203.05963/) (2022)
- [Optimized projection-free algorithms for online learning: construction and worst-case analysis](https://mlsanity.com/paper/2506.05855/) (2025)
- [Interpolation Conditions for Linear Operators and Applications to Performance Estimation Problems](https://mlsanity.com/paper/2302.08781/) (2023)
- [Exploiting Agent Symmetries for Performance Analysis of Distributed Optimization Methods](https://mlsanity.com/paper/2403.11724/) (2024)
- [Online Convex Optimization and Integral Quadratic Constraints: An automated approach to regret analysis](https://mlsanity.com/paper/2503.23600/) (2025)

## Built on by (most cited first, 2 of 2)

- [Local Updates in Distributed Optimization: Provable Acceleration and Topology Effects](https://mlsanity.com/paper/2601.03442/) (2026)
- [Accelerating Optimization and Machine Learning through Decentralization](https://mlsanity.com/paper/2604.19518/) (2026)

## Abstract (arXiv)

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.