Exploiting Agent Symmetries for Performance Analysis of Distributed Optimization Methods
(2026) Open Journal of Mathematical Optimization — Vol. 7, n° 1, p. 1-42 (2026)
Files
OJMO_2026__7__A1_0.pdf
Open Access - Adobe PDF
- 1.17 MB
Details
- Authors
- Abstract
- We show that, in many settings, the worst-case performance of a distributed optimization algorithm is independent of the number of agents in the system, and can thus be computed in the fundamental case with just two agents. This result relies on a novel approach that systematically exploits symmetries in worst-case performance computation, framed as Semidefinite Programming (SDP) via the Performance Estimation Problem (PEP) framework. Harnessing agent symmetries in the PEP yields compact problems whose size is independent of the number of agents in the system. When all agents are equivalent in the problem, we establish the explicit conditions under which the resulting worst-case performance is independent of the number of agents and is therefore equivalent to the basic case with two agents. Our compact PEP formulation also allows the consideration of multiple equivalence classes of agents, and its size only depends on the number of equivalence classes. This enables practical and automated performance analysis of distributed algorithms in numerous complex and realistic settings, such as the analysis of the worst agent performance. We leverage this new tool to analyze the performance of the EXTRA algorithm in advanced settings and its scalability with the number of agents, providing a tighter analysis and deeper understanding of the algorithm performance.
- Affiliations
Citations
Colla, S., & Hendrickx, J. (2026). Exploiting Agent Symmetries for Performance Analysis of Distributed Optimization Methods. Open Journal of Mathematical Optimization, 7(1), 1-42. https://doi.org/10.5802/ojmo.49 (Original work published 2026)