{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T15:13:43Z","timestamp":1780672423815,"version":"3.54.1"},"reference-count":36,"publisher":"MathDoc\/Centre Mersenne","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats: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.<\/jats:p>","DOI":"10.5802\/ojmo.49","type":"journal-article","created":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T09:06:25Z","timestamp":1776675985000},"page":"1-42","source":"Crossref","is-referenced-by-count":0,"title":["Exploiting Agent Symmetries for Performance Analysis of Distributed Optimization Methods"],"prefix":"10.5802","volume":"7","author":[{"given":"Sebastien","family":"Colla","sequence":"first","affiliation":[{"name":"UCLouvain, ICTEAM institute, Louvain-la-Neuve, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Julien M.","family":"Hendrickx","sequence":"additional","affiliation":[{"name":"UCLouvain, ICTEAM institute, Louvain-la-Neuve, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"3842","published-online":{"date-parts":[[2026,4,20]]},"reference":[{"key":"key2026060516482374989_1","author":"Bousselmi, Nizar","year":"2023","unstructured":"[1] Bousselmi, Nizar; Hendrickx, Julien M.; Glineur, Fran\u00e7ois Interpolation Conditions for Linear Operators and applications to Performance Estimation Problems (2023)","journal-title":"Interpolation Conditions for Linear Operators and applications to Performance Estimation Problems"},{"key":"key2026060516482374989_2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/2200000016","article-title":"Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers","volume":"3","author":"Boyd, Stephen","year":"2011","unstructured":"[2] Boyd, Stephen; Parikh, Neal; Chu, Eric; Peleato, Borja; Eckstein, Jonathan Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers, Found. Trends Mach. Learn., Volume 3 (2011), pp. 1-122","journal-title":"Found. Trends Mach. Learn."},{"key":"key2026060516482374989_3","author":"Colla, S\u00e9bastien","year":"2024","unstructured":"[3] Colla, S\u00e9bastien Computer-Aided Analysis of Decentralized Optimization Methods, Ph. D. Thesis, UCLouvain, Belgium (2024)","journal-title":"Computer-Aided Analysis of Decentralized Optimization Methods"},{"key":"key2026060516482374989_4","doi-asserted-by":"publisher","first-page":"2627","DOI":"10.1109\/CDC45484.2021.9683505","article-title":"Automated Worst-Case Performance Analysis of Decentralized Gradient Descent","author":"Colla, Sebastien","year":"2021","unstructured":"[4] Colla, Sebastien; Hendrickx, Julien M. Automated Worst-Case Performance Analysis of Decentralized Gradient Descent, 2021 IEEE 60th Conference on Decision and Control (CDC), IEEE Press (2021), pp. 2627-2633","journal-title":"2021 IEEE 60th Conference on Decision and Control (CDC)"},{"key":"key2026060516482374989_5","doi-asserted-by":"publisher","first-page":"5192","DOI":"10.1109\/CDC51059.2022.9993346","article-title":"Automated Performance Estimation for Decentralized Optimization via Network Size Independent Problems","author":"Colla, Sebastien","year":"2022","unstructured":"[5] Colla, Sebastien; Hendrickx, Julien M. 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","journal-title":"2022 IEEE 61st Conference on Decision and Control (CDC)"},{"issue":"12","key":"key2026060516482374989_6","doi-asserted-by":"publisher","first-page":"7136","DOI":"10.1109\/TAC.2023.3251902","article-title":"Automatic Performance Estimation for Decentralized Optimization","volume":"68","author":"Colla, S\u00e9bastien","year":"2023","unstructured":"[6] Colla, S\u00e9bastien; Hendrickx, Julien M. Automatic Performance Estimation for Decentralized Optimization, IEEE Trans. Autom. Control, Volume 68 (2023) no. 12, pp. 7136-7150","journal-title":"IEEE Trans. Autom. Control"},{"key":"key2026060516482374989_7","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/s10107-013-0653-0","article-title":"Performance of first-order methods for smooth convex minimization: A novel approach","volume":"145","author":"Drori, Yoel","year":"2014","unstructured":"[7] Drori, Yoel; Teboulle, Marc Performance of first-order methods for smooth convex minimization: A novel approach, Math. Program., Volume 145 (2014), pp. 451-482","journal-title":"Math. Program."},{"issue":"3","key":"key2026060516482374989_8","doi-asserted-by":"publisher","first-page":"592","DOI":"10.1109\/TAC.2011.2161027","article-title":"Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling","volume":"57","author":"Duchi, John C.","year":"2012","unstructured":"[8] Duchi, John C.; Agarwal, Alekh; Wainwright, Martin J. Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling, IEEE Trans. Autom. Control, Volume 57 (2012) no. 3, pp. 592-606","journal-title":"IEEE Trans. Autom. Control"},{"key":"key2026060516482374989_9","author":"Goujaud, Baptiste","year":"2022","unstructured":"[9] Goujaud, Baptiste; Moucer, C\u00e9line; Glineur, Fran\u00e7ois; Hendrickx, Julien; Taylor, Adrien; Dieuleveut, Aymeric PEPit: computer-assisted worst-case analyses of first-order optimization methods in Python (2022)","journal-title":"PEPit: computer-assisted worst-case analyses of first-order optimization methods in Python"},{"key":"key2026060516482374989_10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1080\/03081080410001681599","article-title":"Generalized doubly stochastic matrices and linear preservers","volume":"53","author":"Hanley","year":"2005","unstructured":"[10] Hanley; Li, Chi-Kwong Generalized doubly stochastic matrices and linear preservers, Linear Multilinear Algebra, Volume 53 (2005), pp. 1-11","journal-title":"Linear Multilinear Algebra"},{"issue":"1","key":"key2026060516482374989_11","first-page":"31","article-title":"A unification and generalization of exact distributed first-order methods","volume":"5","author":"Jakoveti\u0107, Du\u0161an","year":"2018","unstructured":"[11] Jakoveti\u0107, Du\u0161an A unification and generalization of exact distributed first-order methods, IEEE Trans. Signal Inf. Process. Networks, Volume 5 (2018) no. 1, pp. 31-46","journal-title":"IEEE Trans. Signal Inf. Process. Networks"},{"key":"key2026060516482374989_12","first-page":"18342","article-title":"Optimal and practical algorithms for smooth and strongly convex decentralized optimization","volume":"33","author":"Kovalev, Dmitry","year":"2020","unstructured":"[12] Kovalev, Dmitry; Salim, Adil; Richt\u00e1rik, Peter Optimal and practical algorithms for smooth and strongly convex decentralized optimization, Adv. Neural Inf. Process. Syst., Volume 33 (2020), pp. 18342-18352","journal-title":"Adv. Neural Inf. Process. Syst."},{"issue":"1","key":"key2026060516482374989_13","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/15M1009597","article-title":"Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints","volume":"26","author":"Lessard, Laurent","year":"2016","unstructured":"[13] Lessard, Laurent; Recht, Benjamin; Packard, Andrew Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints, SIAM J. Optim., Volume 26 (2016) no. 1, pp. 57-95","journal-title":"SIAM J. Optim."},{"key":"key2026060516482374989_14","doi-asserted-by":"crossref","first-page":"4855","DOI":"10.1109\/TSP.2020.3018317","article-title":"Decentralized accelerated gradient methods with increasing penalty parameters","volume":"68","author":"Li, Huan","year":"2020","unstructured":"[14] Li, Huan; Fang, Cong; Yin, Wotao; Lin, Zhouchen Decentralized accelerated gradient methods with increasing penalty parameters, IEEE Trans. Signal Process., Volume 68 (2020), pp. 4855-4870","journal-title":"IEEE Trans. Signal Process."},{"issue":"3","key":"key2026060516482374989_15","doi-asserted-by":"crossref","first-page":"1795","DOI":"10.1137\/18M122902X","article-title":"Revisiting extra for smooth distributed optimization","volume":"30","author":"Li, Huan","year":"2020","unstructured":"[15] Li, Huan; Lin, Zhouchen Revisiting extra for smooth distributed optimization, SIAM J. Optim., Volume 30 (2020) no. 3, pp. 1795-1821","journal-title":"SIAM J. Optim."},{"issue":"17","key":"key2026060516482374989_16","doi-asserted-by":"publisher","first-page":"4494","DOI":"10.1109\/TSP.2019.2926022","article-title":"A Decentralized Proximal-Gradient Method With Network Independent Step-Sizes and Separated Convergence Rates","volume":"67","author":"Li, Zhi","year":"2019","unstructured":"[16] Li, Zhi; Shi, Wei; Yan, Ming 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","journal-title":"IEEE Trans. Signal Process."},{"issue":"22","key":"key2026060516482374989_17","doi-asserted-by":"publisher","first-page":"5930","DOI":"10.1109\/TSP.2016.2602803","article-title":"Weighted ADMM for fast decentralized network optimization","volume":"64","author":"Ling, Qing","year":"2016","unstructured":"[17] Ling, Qing; Liu, Yaohua; Shi, Wei; Tian, Zhi Weighted ADMM for fast decentralized network optimization, IEEE Trans. Signal Process., Volume 64 (2016) no. 22, pp. 5930-5942","journal-title":"IEEE Trans. Signal Process."},{"issue":"5","key":"key2026060516482374989_18","doi-asserted-by":"publisher","first-page":"953","DOI":"10.1109\/JPROC.2018.2817461","article-title":"Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization","volume":"106","author":"Nedi\u0107, Angelia","year":"2018","unstructured":"[18] Nedi\u0107, Angelia; Olshevsky, Alex; Rabbat, Michael G. Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization, Proc. IEEE, Volume 106 (2018) no. 5, pp. 953-976","journal-title":"Proc. IEEE"},{"issue":"4","key":"key2026060516482374989_19","doi-asserted-by":"publisher","first-page":"2597","DOI":"10.1137\/16M1084316","article-title":"Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs","volume":"27","author":"Nedi\u0107, Angelia","year":"2017","unstructured":"[19] Nedi\u0107, Angelia; Olshevsky, Alex; Shi, Wei Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs, SIAM J. Optim., Volume 27 (2017) no. 4, pp. 2597-2633","journal-title":"SIAM J. Optim."},{"key":"key2026060516482374989_20","doi-asserted-by":"publisher","first-page":"3950","DOI":"10.23919\/ACC.2017.7963560","article-title":"Geometrically convergent distributed optimization with uncoordinated step-sizes","author":"Nedi\u0107, Angelia","year":"2017","unstructured":"[20] Nedi\u0107, Angelia; Olshevsky, Alex; Shi, Wei; Uribe, C\u00e9sar A Geometrically convergent distributed optimization with uncoordinated step-sizes, 2017 American Control Conference (ACC), IEEE Press (2017), pp. 3950-3955","journal-title":"2017 American Control Conference (ACC)"},{"key":"key2026060516482374989_21","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1109\/TAC.2008.2009515","article-title":"Distributed Subgradient Methods for Multi-Agent Optimization","volume":"54","author":"Nedi\u0107, Angelia","year":"2009","unstructured":"[21] Nedi\u0107, Angelia; Ozdaglar, Asuman Distributed Subgradient Methods for Multi-Agent Optimization, IEEE Trans. Autom. Control, Volume 54 (2009), pp. 48-61","journal-title":"IEEE Trans. Autom. Control"},{"issue":"6","key":"key2026060516482374989_22","doi-asserted-by":"publisher","first-page":"2566","DOI":"10.1109\/TAC.2019.2937496","article-title":"Accelerated Distributed Nesterov Gradient Descent","volume":"65","author":"Qu, Guannan","year":"2020","unstructured":"[22] Qu, Guannan; Li, Na Accelerated Distributed Nesterov Gradient Descent, IEEE Trans. Autom. Control, Volume 65 (2020) no. 6, pp. 2566-2581","journal-title":"IEEE Trans. Autom. Control"},{"key":"key2026060516482374989_23","first-page":"3027","article-title":"Optimal Algorithms for Smooth and Strongly Convex Distributed Optimization in Networks","volume":"70","author":"Scaman, Kevin","year":"2017","unstructured":"[23] Scaman, Kevin; Bach, Francis; Bubeck, S\u00e9bastien; Lee, Yin Tat; Massouli\u00e9, Laurent Optimal Algorithms for Smooth and Strongly Convex Distributed Optimization in Networks, Proceedings of the 34th International Conference on Machine Learning (Precup, Doina; Teh, Yee Whye, eds.) (Proceedings of Machine Learning Research), Volume 70, PMLR (2017), pp. 3027-3036","journal-title":"Proceedings of the 34th International Conference on Machine Learning"},{"key":"key2026060516482374989_24","article-title":"Optimal Convergence Rates for Convex Distributed Optimization in Networks","volume":"20","author":"Scaman, Kevin","year":"2019","unstructured":"[24] Scaman, Kevin; Bach, Francis; Bubeck, S\u00e9bastien; Lee, Yin Tat; Massouli\u00e9, Laurent Optimal Convergence Rates for Convex Distributed Optimization in Networks, J. Mach. Learn. Res., Volume 20 (2019), 159, 31 pages","journal-title":"J. Mach. Learn. Res."},{"issue":"2","key":"key2026060516482374989_25","doi-asserted-by":"publisher","first-page":"944","DOI":"10.1137\/14096668X","article-title":"EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization","volume":"25","author":"Shi, Wei","year":"2015","unstructured":"[25] Shi, Wei; Ling, Qing; Wu, Gang; Yin, Wotao EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization, SIAM J. Optim., Volume 25 (2015) no. 2, pp. 944-966","journal-title":"SIAM J. Optim."},{"issue":"22","key":"key2026060516482374989_26","doi-asserted-by":"publisher","first-page":"6013","DOI":"10.1109\/TSP.2015.2461520","article-title":"A proximal gradient algorithm for decentralized composite optimization","volume":"63","author":"Shi, Wei","year":"2015","unstructured":"[26] Shi, Wei; Ling, Qing; Wu, Gang; Yin, Wotao A proximal gradient algorithm for decentralized composite optimization, IEEE Trans. Signal Process., Volume 63 (2015) no. 22, pp. 6013-6023","journal-title":"IEEE Trans. Signal Process."},{"issue":"7","key":"key2026060516482374989_27","doi-asserted-by":"publisher","first-page":"1750","DOI":"10.1109\/TSP.2014.2304432","article-title":"On the Linear Convergence of the ADMM in Decentralized Consensus Optimization","volume":"62","author":"Shi, Wei","year":"2014","unstructured":"[27] Shi, Wei; Ling, Qing; Yuan, Kun; Wu, Gang; Yin, Wotao On the Linear Convergence of the ADMM in Decentralized Consensus Optimization, IEEE Trans. Signal Process., Volume 62 (2014) no. 7, pp. 1750-1761","journal-title":"IEEE Trans. Signal Process."},{"key":"key2026060516482374989_28","author":"Song, Zhuoqing","year":"2024","unstructured":"[28] Song, Zhuoqing; Shi, Lei; Pu, Shi; Yan, Ming Optimal Gradient Tracking for Decentralized Optimization (2024)","journal-title":"Optimal Gradient Tracking for Decentralized Optimization"},{"key":"key2026060516482374989_29","doi-asserted-by":"publisher","first-page":"1597","DOI":"10.1109\/TCNS.2020.2988009","article-title":"Analysis and Design of First-Order Distributed Optimization Algorithms Over Time-Varying Graphs","volume":"7","author":"Sundararajan, Akhil","year":"2020","unstructured":"[29] Sundararajan, Akhil; Scoy, Bryan Van; Lessard, Laurent 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","journal-title":"IEEE Transactions on Control of Network Systems"},{"issue":"3","key":"key2026060516482374989_30","doi-asserted-by":"publisher","first-page":"1283","DOI":"10.1137\/16M108104X","article-title":"Exact Worst-Case Performance of First-Order Methods for Composite Convex Optimization","volume":"27","author":"Taylor, Adrien B.","year":"2017","unstructured":"[30] Taylor, Adrien B.; Hendrickx, Julien M.; Glineur, Fran\u00e7ois Exact Worst-Case Performance of First-Order Methods for Composite Convex Optimization, SIAM J. Optim., Volume 27 (2017) no. 3, pp. 1283-1313","journal-title":"SIAM J. Optim."},{"key":"key2026060516482374989_31","doi-asserted-by":"publisher","first-page":"1278","DOI":"10.1109\/CDC.2017.8263832","article-title":"Performance estimation toolbox (PESTO): Automated worst-case analysis of first-order optimization methods","author":"Taylor, Adrien B.","year":"2017","unstructured":"[31] Taylor, Adrien B.; Hendrickx, Julien M.; Glineur, Fran\u00e7ois 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","journal-title":"2017 IEEE 56th Conference on Decision and Control (CDC)"},{"key":"key2026060516482374989_32","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/s10107-016-1009-3","article-title":"Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methods","volume":"161","author":"Taylor, Adrien B.","year":"2017","unstructured":"[32] Taylor, Adrien B.; Hendrickx, Julien M.; Glineur, Fran\u00e7ois Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methods, Math. Program., Volume 161 (2017), pp. 307-345","journal-title":"Math. Program."},{"key":"key2026060516482374989_33","first-page":"1","article-title":"A dual approach for optimal algorithms in distributed optimization over networks","author":"Uribe, C\u00e9sar A","year":"2020","unstructured":"[33] Uribe, C\u00e9sar A; Lee, Soomin; Gasnikov, Alexander; Nedi\u0107, Angelia A dual approach for optimal algorithms in distributed optimization over networks, 2020 Information Theory and Applications Workshop (ITA), IEEE Press (2020), pp. 1-37","journal-title":"2020 Information Theory and Applications Workshop (ITA)"},{"issue":"1","key":"key2026060516482374989_34","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.sysconle.2004.02.022","article-title":"Fast linear iterations for distributed averaging","volume":"53","author":"Xiao, Lin","year":"2004","unstructured":"[34] Xiao, Lin; Boyd, Stephen Fast linear iterations for distributed averaging, Syst. Control Lett., Volume 53 (2004) no. 1, pp. 65-78","journal-title":"Syst. Control Lett."},{"key":"key2026060516482374989_35","first-page":"2381","article-title":"Accelerated primal-dual algorithms for distributed smooth convex optimization over networks","author":"Xu, Jinming","year":"2020","unstructured":"[35] Xu, Jinming; Tian, Ye; Sun, Ying; Scutari, Gesualdo Accelerated primal-dual algorithms for distributed smooth convex optimization over networks, International Conference on Artificial Intelligence and Statistics, PMLR (2020), pp. 2381-2391","journal-title":"International Conference on Artificial Intelligence and Statistics"},{"key":"key2026060516482374989_36","first-page":"2055","article-title":"Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes","author":"Xu, Jinming","year":"2015","unstructured":"[36] Xu, Jinming; Zhu, Shanying; Soh, Yeng Chai; Xie, Lihua 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","journal-title":"2015 IEEE 54th Conference on Decision and Control (CDC)"}],"container-title":["Open Journal of Mathematical Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/ojmo.centre-mersenne.org\/item\/10.5802\/ojmo.49.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T14:48:28Z","timestamp":1780670908000},"score":1,"resource":{"primary":{"URL":"https:\/\/ojmo.centre-mersenne.org\/articles\/10.5802\/ojmo.49\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,20]]},"references-count":36,"alternative-id":["10.5802\/ojmo.49"],"URL":"https:\/\/doi.org\/10.5802\/ojmo.49","relation":{},"ISSN":["2777-5860"],"issn-type":[{"value":"2777-5860","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,20]]},"article-number":"1"}}