# On the Convergence of Decentralized Gradient Descent

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

## Key facts

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

## Built on by (most cited first, 30 of 159)

- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [Decentralized Federated Learning: Fundamentals, State of the Art, Frameworks, Trends, and Challenges](https://mlsanity.com/paper/2211.08413/) (2022)
- [Decentralized Federated Averaging](https://mlsanity.com/paper/2104.11375/) (2021)
- [Federated Learning with Partial Model Personalization](https://mlsanity.com/paper/2204.03809/) (2022)
- [Decentralized Federated Learning: Balancing Communication and Computing Costs](https://mlsanity.com/paper/2107.12048/) (2021)
- [Consensus Control for Decentralized Deep Learning](https://mlsanity.com/paper/2102.04828/) (2021)
- [DecentLaM: Decentralized Momentum SGD for Large-batch Deep Training](https://mlsanity.com/paper/2104.11981/) (2021)
- [On the Unreasonable Effectiveness of Federated Averaging with Heterogeneous Data](https://mlsanity.com/paper/2206.04723/) (2022)
- [Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices](https://mlsanity.com/paper/2103.03239/) (2021)
- [Decentralized Riemannian Gradient Descent on the Stiefel Manifold](https://mlsanity.com/paper/2102.07091/) (2021)
- [KNAS: Green Neural Architecture Search](https://mlsanity.com/paper/2111.13293/) (2021)
- [Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compression](https://mlsanity.com/paper/2206.03665/) (2022)
- [Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGD](https://mlsanity.com/paper/2105.08023/) (2021)
- [Beyond spectral gap: The role of the topology in decentralized learning](https://mlsanity.com/paper/2206.03093/) (2022)
- [Accelerating Gossip SGD with Periodic Global Averaging](https://mlsanity.com/paper/2105.09080/) (2021)
- [Communication-Efficient Topologies for Decentralized Learning with O(1) Consensus Rate](https://mlsanity.com/paper/2210.07881/) (2022)
- [Revisiting Optimal Convergence Rate for Smooth and Non-convex Stochastic Decentralized Optimization](https://mlsanity.com/paper/2210.07863/) (2022)
- [On the Performance of Gradient Tracking with Local Updates](https://mlsanity.com/paper/2210.04757/) (2022)
- [Decentralized Stochastic Bilevel Optimization with Improved per-Iteration Complexity](https://mlsanity.com/paper/2210.12839/) (2022)
- [DeEPCA: Decentralized Exact PCA with Linear Convergence Rate](https://mlsanity.com/paper/2102.03990/) (2021)
- [Distributed Learning Systems with First-order Methods](https://mlsanity.com/paper/2104.05245/) (2021)
- [On the Convergence of Decentralized Adaptive Gradient Methods](https://mlsanity.com/paper/2109.03194/) (2021)
- [Towards Demystifying Serverless Machine Learning Training](https://mlsanity.com/paper/2105.07806/) (2021)
- [Semi-Decentralized Federated Learning with Collaborative Relaying](https://mlsanity.com/paper/2205.10998/) (2022)
- [Joint Optimization of Communications and Federated Learning Over the Air](https://mlsanity.com/paper/2104.03490/) (2021)
- [Decentralized Low-Rank Fine-Tuning of Large Language Models](https://mlsanity.com/paper/2501.15361/) (2025)
- [NET-FLEET: Achieving Linear Convergence Speedup for Fully Decentralized Federated Learning with Heterogeneous Data](https://mlsanity.com/paper/2208.08490/) (2022)
- [DIGEST: Fast and Communication Efficient Decentralized Learning with Local Updates](https://mlsanity.com/paper/2307.07652/) (2023)
- [Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization](https://mlsanity.com/paper/2104.02596/) (2021)
- [Decentralized Optimization Over the Stiefel Manifold by an Approximate Augmented Lagrangian Function](https://mlsanity.com/paper/2112.14949/) (2021)

## Abstract (arXiv)

Consider the consensus problem of minimizing f(x)=sumi=1n fi(x) where each fi is only known to one individual agent i out of a connected network of n agents. All the agents shall collaboratively solve this problem and obtain the solution subject to data exchanges restricted to between neighboring agents. Such algorithms avoid the need of a fusion center, offer better network load balance, and improve data privacy. We study the decentralized gradient descent method in which each agent i updates its variable x(i), which is a local approximate to the unknown variable x, by combining the average of its neighbors' with the negative gradient step -α nabla fi(x(i)). The iteration is x(i)(k+1) gets sumneighbor j of i wij x(j)(k) - α nabla fi(x(i)(k)),quadfor each agent i, where the averaging coefficients form a symmetric doubly stochastic matrix W=[wij] ∈ ℝn × n. We analyze the convergence of this iteration and derive its converge rate, assuming that each fi is proper closed convex and lower bounded, nabla fi is Lipschitz continuous with constant Lfi, and stepsize α is fixed. Provided that α < O(1/Lh) where Lh=maxiLfi, the objective error at the averaged solution, f(frac1nsumi x(i)(k))-f^*, reduces at a speed of O(1/k) until it reaches O(α). If fi are further (restricted) strongly convex, then both frac1nsumi x(i)(k) and each x(i)(k) converge to the global minimizer x^* at a linear rate until reaching an O(α)-neighborhood of x^*. We also develop an iteration for decentralized basis pursuit and establish its linear convergence to an O(α)-neighborhood of the true unknown sparse signal.