2025/09/08 by Erwan Meunier, Julien M. Hendrickx, Meunier, Erwan +1
Computer Science · Decision Sciences · #Artificial Intelligence (cs.AI) #Auction Theory and Applications #Distributed #FOS: Computer and information sciences #FOS: Mathematics #IoT and Edge/Fog Computing #Multiagent Systems (cs.MA) #Optimization and Control (math.OC) #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2509.06466
openalex publication_date 2025/09/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.