# Analysis and Design of First-Order Distributed Optimization Algorithms over Time-Varying Graphs

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jul 2019.

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

- [PEPit: computer-assisted worst-case analyses of first-order optimization methods in Python](https://mlsanity.com/paper/2201.04040/) (2022)
- [Towards a Systems Theory of Algorithms](https://mlsanity.com/paper/2401.14029/) (2024)
- [Learning to optimize with convergence guarantees using nonlinear system theory](https://mlsanity.com/paper/2403.09389/) (2024)
- [Convex Programs and Lyapunov Functions for Reinforcement Learning: A Unified Perspective on the Analysis of Value-Based Methods](https://mlsanity.com/paper/2202.06922/) (2022)
- [On Centralized and Distributed Mirror Descent: Convergence Analysis Using Quadratic Constraints](https://mlsanity.com/paper/2105.14385/) (2021)
- [Exact Formulas for Finite-Time Estimation Errors of Decentralized Temporal Difference Learning with Linear Function Approximation](https://mlsanity.com/paper/2204.09801/) (2022)
- [A Tight Theory of Error Feedback Algorithms in Distributed Optimization](https://mlsanity.com/paper/2605.31594/) (2026)

## Abstract (arXiv)

This work concerns the analysis and design of distributed first-order optimization algorithms over time-varying graphs. The goal of such algorithms is to optimize a global function that is the average of local functions using only local computations and communications. Several different algorithms have been proposed that achieve linear convergence to the global optimum when the local functions are strongly convex. We provide a unified analysis that yields the worst-case linear convergence rate as a function of the condition number of the local functions, the spectral gap of the graph, and the parameters of the algorithm. The framework requires solving a small semidefinite program whose size is fixed; it does not depend on the number of local functions or the dimension of their domain. The result is a computationally efficient method for distributed algorithm analysis that enables the rapid comparison, selection, and tuning of algorithms. Finally, we propose a new algorithm, which we call SVL, that is easily implementable and achieves a faster worst-case convergence rate than all other known algorithms.