Automated Performance Estimation for Decentralized Optimization via Network Size Independent Problems
arXiv:2210.00695 · doi:10.1109/CDC51059.2022.9993346
Abstract
We develop a novel formulation of the Performance Estimation Problem (PEP) for decentralized optimization whose size is independent of the number of agents in the network. The PEP approach allows computing automatically the worst-case performance and worst-case instance of first-order optimization methods by solving an SDP. Unlike previous work, the size of our new PEP formulation is independent of the network size. For this purpose, we take a global view of the decentralized problem and we also decouple the consensus subspace and its orthogonal complement. We apply our methodology to different decentralized methods such as DGD, DIGing and EXTRA and obtain numerically tight performance guarantees that are valid for any network size.
arXiv comment8 pages, 3 figures, accepted for Conference on Decision and Control 2022. arXiv admin note: text overlap with arXiv:2203.05963
References in corpus (7)
- Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints
- A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates
- Optimized first-order methods for smooth convex minimization
- Exact Worst-case Performance of First-order Methods for Composite Convex Optimization
- Automated Worst-Case Performance Analysis of Decentralized Gradient Descent
- Automatic Performance Estimation for Decentralized Optimization
- PEPit: computer-assisted worst-case analyses of first-order optimization methods in Python