mlsanityData to 14 Oct 2026

Unified Analysis of Decentralized Gradient Descent: a Contraction Mapping Framework

arXiv 2503.14353 ↗First posted 18 Mar 2025eess.SP cs.DC cs.LGcited by 10

Not on the map. Why?

Abstract (arXiv)

The decentralized gradient descent (DGD) algorithm, and its sibling, diffusion, are workhorses in decentralized machine learning, distributed inference and estimation, and multi-agent coordination. We propose a novel, principled framework for the analysis of DGD and diffusion for strongly convex, smooth objectives, and arbitrary undirected topologies, using contraction mappings coupled with a result called the mean Hessian theorem (MHT). The use of these tools yields tight convergence bounds, both in the noise-free and noisy regimes. While these bounds are qualitatively similar to results found in the literature, our approach using contractions together with the MHT decouples the algorithm dynamics (how quickly the algorithm converges to its fixed point) from its asymptotic convergence properties (how far the fixed point is from the global optimum). This yields a simple, intuitive analysis that is accessible to a broader audience. Extensions are provided to multiple local gradient updates, time-varying step sizes, noisy gradients (stochastic DGD and diffusion), communication noise, and random topologies.

Key facts. Cited by 10 papers in the map (data through 14 Oct 2026). Builds on 35 of its 68 references that are in the map. First posted on arXiv 18 Mar 2025.

Builds on

35 of 68 references.

References · 35

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,669
  2. 2019On the Convergence of FedAvg on Non-IID Datacited by 1,229
  3. 2018Local SGD Converges Fast and Communicates Littlecited by 605
  4. 2014Convex Optimization: Algorithms and Complexitycited by 575
  5. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 367
  6. 2018Broadband Analog Aggregation for Low-Latency Federated Edge Learning (Extended Version)cited by 191
  7. 2019Federated Learning over Wireless Fading Channelscited by 183
  8. 2013On the Convergence of Decentralized Gradient Descentcited by 159
  9. 2016Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphscited by 150
  10. 2022Decentralized Federated Learning: Fundamentals, State of the Art, Frameworks, Trends, and Challengescited by 138
  11. 2021Distributed Learning in Wireless Networks: Recent Progress and Future Challengescited by 129
  12. 2016NEXT: In-Network Nonconvex Optimizationcited by 107
23 more
  1. 2017Optimal algorithms for smooth and strongly convex distributed optimization in networkscited by 83
  2. 2021Federated Learning over Wireless Device-to-Device Networks: Algorithms and Convergence Analysiscited by 51
  3. 2021Semi-Decentralized Federated Learning with Cooperative D2D Local Model Aggregationscited by 51
  4. 2017Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Developmentcited by 50
  5. 2021Federated Learning: A Signal Processing Perspectivecited by 49
  6. 2018An Exact Quantized Decentralized Gradient Descent Algorithmcited by 36
  7. 2021Decentralized Riemannian Gradient Descent on the Stiefel Manifoldcited by 33
  8. 2018New Convergence Aspects of Stochastic Gradient Algorithmscited by 30
  9. 2020Convergence of Federated Learning over a Noisy Downlinkcited by 29
  10. 2020A general framework for decentralized optimization with first-order methodscited by 28
  11. 2017Balancing Communication and Computation in Distributed Optimizationcited by 23
  12. 2021Over-the-Air Decentralized Federated Learningcited by 18
  13. 2018Convergence rates for distributed stochastic optimization over random networkscited by 16
  14. 2020Decentralized SGD with Over-the-Air Computationcited by 16
  15. 2018Accelerated Gossip in Networks of Given Dimension using Jacobi Polynomial Iterationscited by 15
  16. 2020Distributed Algorithms for Composite Optimization: Unified Framework and Convergence Analysiscited by 15
  17. 2021Finite-Bit Quantization For Distributed Algorithms With Linear Convergencecited by 15
  18. 2020Decentralized optimization over noisy, rate-constrained networks: Achieving consensus by communicating differencescited by 12
  19. 2022SAFARI: Sparsity enabled Federated Learning with Limited and Unreliable Communicationscited by 11
  20. 2022Non-Coherent Over-the-Air Decentralized Gradient Descentcited by 9
  21. 2019Adaptation and learning over networks under subspace constraints -- Part I: Stability Analysiscited by 7
  22. 2021Wireless Federated Learning (WFL) for 6G Networks -- Part I: Research Challenges and Future Trendscited by 6
  23. 2022Federated Optimization of Smooth Loss Functionscited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 8.

10 papers.

  1. 2025Time-Varying Optimization for Streaming Data Via Temporal Weightingcited by 2
  2. 2026Tight Analysis of Decentralized SGD: A Markov Chain Perspectivecited by 1
  3. 2026Decentralized Time-Varying Optimization for Streaming Data via Temporal Weightingcited by 1
  4. 2026Your Neighbors Know: Leveraging Local Neighborhoods for Backdoor Detection in Decentralized Learningcited by 1
  5. 2025A Unified Convergence Analysis for Semi-Decentralized Learning: Sampled-to-Sampled vs. Sampled-to-All Communicationcited by 0
  6. 2026Interference-Robust Non-Coherent Over-the-Air Computation for Decentralized Optimizationcited by 0
  7. 2026Decentralized Gradient Descent: Bottleneck Regimes and Budget Complexitycited by 0
  8. 2026Mixed-Timescale Differential Coding for Downlink Model Broadcast in Wireless Federated Learningcited by 0
  9. 2026Distributed Optimization with Streaming Data: A Temporal Weighting Perspectivecited by 0
  10. 2026A Contraction Framework for Stochastic Operators with Bootstrapping: Application to TD Learningcited by 0