Open Journal of Mathematical Optimization

Exploiting Agent Symmetries for Performance Analysis of Distributed Optimization Methods
Sebastien Colla1; Julien M. Hendrickx1
1UCLouvain, ICTEAM institute, Louvain-la-Neuve, Belgium
Open Journal of Mathematical Optimization, Volume 7 (2026), article no. 1, 42 p.

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.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/ojmo.49
Keywords: Distributed optimization, Performance estimation problem, Worst-case analysis.

Sebastien Colla  1 ; Julien M. Hendrickx  1

1 UCLouvain, ICTEAM institute, Louvain-la-Neuve, Belgium
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights
Sebastien Colla; Julien M. Hendrickx. Exploiting Agent Symmetries for Performance Analysis of Distributed Optimization Methods. Open Journal of Mathematical Optimization, Volume 7 (2026), article  no. 1, 42 p.. doi: 10.5802/ojmo.49
@article{OJMO_2026__7__A1_0,
     author = {Sebastien Colla and Julien M. Hendrickx},
     title = {Exploiting {Agent} {Symmetries} for {Performance} {Analysis} of {Distributed} {Optimization} {Methods}},
     journal = {Open Journal of Mathematical Optimization},
     eid = {1},
     pages = {1--42},
     year = {2026},
     publisher = {Universit\'e de Montpellier},
     volume = {7},
     doi = {10.5802/ojmo.49},
     language = {en},
     url = {https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.49/}
}
TY  - JOUR
AU  - Sebastien Colla
AU  - Julien M. Hendrickx
TI  - Exploiting Agent Symmetries for Performance Analysis of Distributed Optimization Methods
JO  - Open Journal of Mathematical Optimization
PY  - 2026
SP  - 1
EP  - 42
VL  - 7
PB  - Université de Montpellier
UR  - https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.49/
DO  - 10.5802/ojmo.49
LA  - en
ID  - OJMO_2026__7__A1_0
ER  - 
%0 Journal Article
%A Sebastien Colla
%A Julien M. Hendrickx
%T Exploiting Agent Symmetries for Performance Analysis of Distributed Optimization Methods
%J Open Journal of Mathematical Optimization
%] 1
%D 2026
%P 1-42
%V 7
%I Université de Montpellier
%U https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.49/
%R 10.5802/ojmo.49
%G en
%F OJMO_2026__7__A1_0

[1] Nizar Bousselmi; Julien M. Hendrickx; François Glineur Interpolation Conditions for Linear Operators and applications to Performance Estimation Problems (2023) | arXiv | Zbl

[2] Stephen Boyd; Neal Parikh; Eric Chu; Borja Peleato; Jonathan Eckstein Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers, Found. Trends Mach. Learn., Volume 3 (2011), pp. 1-122 | DOI | Zbl

[3] Sébastien Colla Computer-Aided Analysis of Decentralized Optimization Methods, Ph. D. Thesis, UCLouvain, Belgium (2024)

[4] Sebastien Colla; Julien M. Hendrickx Automated Worst-Case Performance Analysis of Decentralized Gradient Descent, 2021 IEEE 60th Conference on Decision and Control (CDC), IEEE Press (2021), pp. 2627-2633 | DOI

[5] Sebastien Colla; Julien M. Hendrickx Automated Performance Estimation for Decentralized Optimization via Network Size Independent Problems, 2022 IEEE 61st Conference on Decision and Control (CDC), IEEE Press (2022), pp. 5192-5199 | DOI

[6] Sébastien Colla; Julien M. Hendrickx Automatic Performance Estimation for Decentralized Optimization, IEEE Trans. Autom. Control, Volume 68 (2023) no. 12, pp. 7136-7150 | DOI | Zbl | MR

[7] Yoel Drori; Marc Teboulle Performance of first-order methods for smooth convex minimization: A novel approach, Math. Program., Volume 145 (2014), pp. 451-482 | DOI | Zbl | MR

[8] John C. Duchi; Alekh Agarwal; Martin J. Wainwright Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling, IEEE Trans. Autom. Control, Volume 57 (2012) no. 3, pp. 592-606 | DOI | Zbl | MR

[9] Baptiste Goujaud; Céline Moucer; François Glineur; Julien Hendrickx; Adrien Taylor; Aymeric Dieuleveut PEPit: computer-assisted worst-case analyses of first-order optimization methods in Python (2022) | arXiv | Zbl

[10] Hanley; Chi-Kwong Li Generalized doubly stochastic matrices and linear preservers, Linear Multilinear Algebra, Volume 53 (2005), pp. 1-11 | DOI | Zbl

[11] Dušan Jakovetić A unification and generalization of exact distributed first-order methods, IEEE Trans. Signal Inf. Process. Networks, Volume 5 (2018) no. 1, pp. 31-46 | MR

[12] Dmitry Kovalev; Adil Salim; Peter Richtárik Optimal and practical algorithms for smooth and strongly convex decentralized optimization, Adv. Neural Inf. Process. Syst., Volume 33 (2020), pp. 18342-18352

[13] Laurent Lessard; Benjamin Recht; Andrew Packard Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints, SIAM J. Optim., Volume 26 (2016) no. 1, pp. 57-95 | DOI | Zbl | MR

[14] Huan Li; Cong Fang; Wotao Yin; Zhouchen Lin Decentralized accelerated gradient methods with increasing penalty parameters, IEEE Trans. Signal Process., Volume 68 (2020), pp. 4855-4870 | MR | Zbl

[15] Huan Li; Zhouchen Lin Revisiting extra for smooth distributed optimization, SIAM J. Optim., Volume 30 (2020) no. 3, pp. 1795-1821 | Zbl | MR

[16] Zhi Li; Wei Shi; Ming Yan A Decentralized Proximal-Gradient Method With Network Independent Step-Sizes and Separated Convergence Rates, IEEE Trans. Signal Process., Volume 67 (2019) no. 17, pp. 4494-4506 | DOI | Zbl | MR

[17] Qing Ling; Yaohua Liu; Wei Shi; Zhi Tian Weighted ADMM for fast decentralized network optimization, IEEE Trans. Signal Process., Volume 64 (2016) no. 22, pp. 5930-5942 | DOI | Zbl | MR

[18] Angelia Nedić; Alex Olshevsky; Michael G. Rabbat Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization, Proc. IEEE, Volume 106 (2018) no. 5, pp. 953-976 | DOI

[19] Angelia Nedić; Alex Olshevsky; Wei Shi Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs, SIAM J. Optim., Volume 27 (2017) no. 4, pp. 2597-2633 | DOI | Zbl | MR

[20] Angelia Nedić; Alex Olshevsky; Wei Shi; César A Uribe Geometrically convergent distributed optimization with uncoordinated step-sizes, 2017 American Control Conference (ACC), IEEE Press (2017), pp. 3950-3955 | DOI

[21] Angelia Nedić; Asuman Ozdaglar Distributed Subgradient Methods for Multi-Agent Optimization, IEEE Trans. Autom. Control, Volume 54 (2009), pp. 48-61 | DOI | Zbl | MR

[22] Guannan Qu; Na Li Accelerated Distributed Nesterov Gradient Descent, IEEE Trans. Autom. Control, Volume 65 (2020) no. 6, pp. 2566-2581 | DOI | MR | Zbl

[23] Kevin Scaman; Francis Bach; Sébastien Bubeck; Yin Tat Lee; Laurent Massoulié Optimal Algorithms for Smooth and Strongly Convex Distributed Optimization in Networks, Proceedings of the 34th International Conference on Machine Learning (Doina Precup; Yee Whye Teh, eds.) (Proceedings of Machine Learning Research), Volume 70, PMLR (2017), pp. 3027-3036

[24] Kevin Scaman; Francis Bach; Sébastien Bubeck; Yin Tat Lee; Laurent Massoulié Optimal Convergence Rates for Convex Distributed Optimization in Networks, J. Mach. Learn. Res., Volume 20 (2019), 159, 31 pages | MR | Zbl

[25] Wei Shi; Qing Ling; Gang Wu; Wotao Yin EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization, SIAM J. Optim., Volume 25 (2015) no. 2, pp. 944-966 | DOI | MR | Zbl

[26] Wei Shi; Qing Ling; Gang Wu; Wotao Yin A proximal gradient algorithm for decentralized composite optimization, IEEE Trans. Signal Process., Volume 63 (2015) no. 22, pp. 6013-6023 | DOI | MR | Zbl

[27] Wei Shi; Qing Ling; Kun Yuan; Gang Wu; Wotao Yin On the Linear Convergence of the ADMM in Decentralized Consensus Optimization, IEEE Trans. Signal Process., Volume 62 (2014) no. 7, pp. 1750-1761 | DOI | MR | Zbl

[28] Zhuoqing Song; Lei Shi; Shi Pu; Ming Yan Optimal Gradient Tracking for Decentralized Optimization (2024) | arXiv

[29] Akhil Sundararajan; Bryan Van Scoy; Laurent Lessard Analysis and Design of First-Order Distributed Optimization Algorithms Over Time-Varying Graphs, IEEE Transactions on Control of Network Systems, Volume 7 (2020), pp. 1597-1608 | DOI | MR | Zbl

[30] Adrien B. Taylor; Julien M. Hendrickx; François Glineur Exact Worst-Case Performance of First-Order Methods for Composite Convex Optimization, SIAM J. Optim., Volume 27 (2017) no. 3, pp. 1283-1313 | DOI | MR | Zbl

[31] Adrien B. Taylor; Julien M. Hendrickx; François Glineur Performance estimation toolbox (PESTO): Automated worst-case analysis of first-order optimization methods, 2017 IEEE 56th Conference on Decision and Control (CDC), IEEE Press (2017), pp. 1278-1283 | DOI | Zbl

[32] Adrien B. Taylor; Julien M. Hendrickx; François Glineur Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methods, Math. Program., Volume 161 (2017), pp. 307-345 | DOI | MR | Zbl

[33] César A Uribe; Soomin Lee; Alexander Gasnikov; Angelia Nedić A dual approach for optimal algorithms in distributed optimization over networks, 2020 Information Theory and Applications Workshop (ITA), IEEE Press (2020), pp. 1-37

[34] Lin Xiao; Stephen Boyd Fast linear iterations for distributed averaging, Syst. Control Lett., Volume 53 (2004) no. 1, pp. 65-78 | Zbl | DOI | MR

[35] Jinming Xu; Ye Tian; Ying Sun; Gesualdo Scutari Accelerated primal-dual algorithms for distributed smooth convex optimization over networks, International Conference on Artificial Intelligence and Statistics, PMLR (2020), pp. 2381-2391

[36] Jinming Xu; Shanying Zhu; Yeng Chai Soh; Lihua Xie Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes, 2015 IEEE 54th Conference on Decision and Control (CDC), IEEE Press (2015), pp. 2055-2060

Cited by Sources: