Tight Analysis of Decentralized SGD: A Markov Chain Perspective
Not on the map. Why?
Abstract (arXiv)
We propose a novel analysis of the Decentralized Stochastic Gradient Descent (DSGD) algorithm with constant step size, interpreting the iterates of the algorithm as a Markov chain. We show that DSGD converges to a stationary distribution, with its bias, to first order, decomposable into two components: one due to decentralization (growing with the graph's spectral gap and clients' heterogeneity) and one due to stochasticity. Remarkably, the variance of local parameters is, at the first-order, inversely proportional to the number of clients, regardless of the network topology and even when clients' iterates are not averaged at the end. As a consequence of our analysis, we obtain non-asymptotic convergence bounds for clients' local iterates, confirming that DSGD has linear speed-up in the number of clients, and that the network topology only impacts higher-order terms.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 51 of its 89 references that are in the map. First posted on arXiv 11 Jan 2026.
Builds on
51 of 89 references.
References · 51
- 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,669
- 2019Advances and Open Problems in Federated Learningcited by 3,046
- 2020Adaptive Federated Optimizationcited by 1,046
- 2018Local SGD Converges Fast and Communicates Littlecited by 605
- 2017Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descentcited by 502
- 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 367
- 2018Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learningcited by 278
- 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
- 2019Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communicationcited by 221
- 2019On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimizationcited by 180
- 2014EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimizationcited by 160
- 2013On the Convergence of Decentralized Gradient Descentcited by 159
38 more
- 2019On the Convergence of Local Descent Methods in Federated Learningcited by 153
- 2018Stochastic Gradient Push for Distributed Deep Learningcited by 152
- 2016Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphscited by 150
- 2018D2: Decentralized Training over Decentralized Datacited by 140
- 2020FedSplit: An algorithmic framework for fast federated optimizationcited by 108
- 2016NEXT: In-Network Nonconvex Optimizationcited by 107
- 2018Distributed Stochastic Gradient Tracking Methodscited by 106
- 2018Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithmscited by 106
- 2017Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chainscited by 88
- 2017Optimal algorithms for smooth and strongly convex distributed optimization in networkscited by 83
- 2020From Local SGD to Local Fixed-Point Methods for Federated Learningcited by 74
- 2022An Improved Analysis of Gradient Tracking for Decentralized Machine Learningcited by 69
- 2015Perturbed Iterate Analysis for Asynchronous Stochastic Optimizationcited by 67
- 2015Communication Complexity of Distributed Convex Learning and Optimizationcited by 60
- 2021Convergence and Accuracy Trade-Offs in Federated Learning and Meta-Learningcited by 52
- 2017A decentralized proximal-gradient method with network independent step-sizes and separated convergence ratescited by 51
- 2017Communication-Efficient Algorithms for Decentralized and Stochastic Optimizationcited by 43
- 2020Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimizationcited by 43
- 2021Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspectivecited by 38
- 2022On the Unreasonable Effectiveness of Federated Averaging with Heterogeneous Datacited by 38
- 2020Decentralized gradient methods: does topology matter?cited by 35
- 2022Refined Convergence and Topology Learning for Decentralized SGD with Heterogeneous Datacited by 32
- 2015Taming the Wild: A Unified Analysis of Hogwild!-Style Algorithmscited by 31
- 2021Local Adaptivity in Federated Learning: Convergence and Consistencycited by 31
- 2018A Dual Approach for Optimal Algorithms in Distributed Optimization over Networkscited by 27
- 2022Beyond spectral gap: The role of the topology in decentralized learningcited by 27
- 2020An Optimal Algorithm for Decentralized Finite Sum Optimizationcited by 19
- 2015On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variantscited by 18
- 2016ASAGA: Asynchronous Parallel SAGAcited by 18
- 2018Graph-Dependent Implicit Regularisation for Distributed Stochastic Subgradient Descentcited by 14
- 2020Revisiting EXTRA for Smooth Distributed Optimizationcited by 12
- 2023Asynchronous SGD on Graphs: a Unified Framework for Asynchronous Decentralized and Federated Optimizationcited by 11
- 2023Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithmcited by 10
- 2025Unified Analysis of Decentralized Gradient Descent: a Contraction Mapping Frameworkcited by 10
- 2024Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolationcited by 6
- 2017Convergence diagnostics for stochastic gradient descent with constant step sizecited by 5
- 2025Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Upcited by 3
- 2021Automated Worst-Case Performance Analysis of Decentralized Gradient Descentcited by 2
50 most cited of 51 All 51 (JSON)
Built on by
Citing papers per year: 2026: 1.
1 paper.