# Automated Worst-Case Performance Analysis of Decentralized Gradient Descent

arXiv: https://arxiv.org/abs/2103.14396 · HTML: https://mlsanity.com/paper/2103.14396/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Mar 2021.

## Built on by (most cited first, 2 of 2)

- [PEPit: computer-assisted worst-case analyses of first-order optimization methods in Python](https://mlsanity.com/paper/2201.04040/) (2022)
- [Tight Analysis of Decentralized SGD: A Markov Chain Perspective](https://mlsanity.com/paper/2601.07021/) (2026)

## Abstract (arXiv)

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.