Automated Worst-Case Performance Analysis of Decentralized Gradient Descent
arXiv:2103.14396 · doi:10.1109/CDC45484.2021.9683505
Abstract
We develop a methodology to automatically compute worst-case performance bounds for a class of decentralized algorithms that optimize the average of local functions distributed across a network. We extend the recently proposed PEP approach to decentralized optimization. This approach allows computing the exact worst-case performance and worst-case instance of centralized algorithms by solving an SDP. We obtain an exact formulation when the network matrix is given, and a relaxation when considering entire classes of network matrices characterized by their spectral range. We apply our methodology to the decentralized (sub)gradient method, obtain a nearly tight worst-case performance bound that significantly improves over the literature, and gain insights into the worst communication networks for a given spectral range.
arXiv comment7 pages, 4 figures, accepted at the Conference on Decision and Control 2021
References in corpus (4)
- 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
- On the Convergence of Decentralized Gradient Descent