# Unified Analysis of Decentralized Gradient Descent: a Contraction Mapping Framework arXiv: https://arxiv.org/abs/2503.14353 ยท HTML: https://mlsanity.com/paper/2503.14353/ ## 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 (most cited first, 30 of 35) - [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016) - [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019) - [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018) - [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014) - [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020) - [Broadband Analog Aggregation for Low-Latency Federated Edge Learning (Extended Version)](https://mlsanity.com/paper/1812.11494/) (2018) - [Federated Learning over Wireless Fading Channels](https://mlsanity.com/paper/1907.09769/) (2019) - [On the Convergence of Decentralized Gradient Descent](https://mlsanity.com/paper/1310.7063/) (2013) - [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016) - [Decentralized Federated Learning: Fundamentals, State of the Art, Frameworks, Trends, and Challenges](https://mlsanity.com/paper/2211.08413/) (2022) - [Distributed Learning in Wireless Networks: Recent Progress and Future Challenges](https://mlsanity.com/paper/2104.02151/) (2021) - [NEXT: In-Network Nonconvex Optimization](https://mlsanity.com/paper/1602.00591/) (2016) - [Optimal algorithms for smooth and strongly convex distributed optimization in networks](https://mlsanity.com/paper/1702.08704/) (2017) - [Federated Learning over Wireless Device-to-Device Networks: Algorithms and Convergence Analysis](https://mlsanity.com/paper/2101.12704/) (2021) - [Semi-Decentralized Federated Learning with Cooperative D2D Local Model Aggregations](https://mlsanity.com/paper/2103.10481/) (2021) - [Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Development](https://mlsanity.com/paper/1702.05122/) (2017) - [Federated Learning: A Signal Processing Perspective](https://mlsanity.com/paper/2103.17150/) (2021) - [An Exact Quantized Decentralized Gradient Descent Algorithm](https://mlsanity.com/paper/1806.11536/) (2018) - [Decentralized Riemannian Gradient Descent on the Stiefel Manifold](https://mlsanity.com/paper/2102.07091/) (2021) - [New Convergence Aspects of Stochastic Gradient Algorithms](https://mlsanity.com/paper/1811.12403/) (2018) - [Convergence of Federated Learning over a Noisy Downlink](https://mlsanity.com/paper/2008.11141/) (2020) - [A general framework for decentralized optimization with first-order methods](https://mlsanity.com/paper/2009.05837/) (2020) - [Balancing Communication and Computation in Distributed Optimization](https://mlsanity.com/paper/1709.02999/) (2017) - [Over-the-Air Decentralized Federated Learning](https://mlsanity.com/paper/2106.08011/) (2021) - [Convergence rates for distributed stochastic optimization over random networks](https://mlsanity.com/paper/1803.07836/) (2018) - [Decentralized SGD with Over-the-Air Computation](https://mlsanity.com/paper/2003.04216/) (2020) - [Accelerated Gossip in Networks of Given Dimension using Jacobi Polynomial Iterations](https://mlsanity.com/paper/1805.08531/) (2018) - [Distributed Algorithms for Composite Optimization: Unified Framework and Convergence Analysis](https://mlsanity.com/paper/2002.11534/) (2020) - [Finite-Bit Quantization For Distributed Algorithms With Linear Convergence](https://mlsanity.com/paper/2107.11304/) (2021) - [Decentralized optimization over noisy, rate-constrained networks: Achieving consensus by communicating differences](https://mlsanity.com/paper/2010.11292/) (2020) ## Built on by (most cited first, 10 of 10) - [Time-Varying Optimization for Streaming Data Via Temporal Weighting](https://mlsanity.com/paper/2510.13052/) (2025) - [Tight Analysis of Decentralized SGD: A Markov Chain Perspective](https://mlsanity.com/paper/2601.07021/) (2026) - [Decentralized Time-Varying Optimization for Streaming Data via Temporal Weighting](https://mlsanity.com/paper/2605.06971/) (2026) - [Your Neighbors Know: Leveraging Local Neighborhoods for Backdoor Detection in Decentralized Learning](https://mlsanity.com/paper/2605.19969/) (2026) - [A Unified Convergence Analysis for Semi-Decentralized Learning: Sampled-to-Sampled vs. Sampled-to-All Communication](https://mlsanity.com/paper/2511.11560/) (2025) - [Interference-Robust Non-Coherent Over-the-Air Computation for Decentralized Optimization](https://mlsanity.com/paper/2602.12426/) (2026) - [Decentralized Gradient Descent: Bottleneck Regimes and Budget Complexity](https://mlsanity.com/paper/2607.12172/) (2026) - [Mixed-Timescale Differential Coding for Downlink Model Broadcast in Wireless Federated Learning](https://mlsanity.com/paper/2607.13119/) (2026) - [Distributed Optimization with Streaming Data: A Temporal Weighting Perspective](https://mlsanity.com/paper/2608.09565/) (2026) - [A Contraction Framework for Stochastic Operators with Bootstrapping: Application to TD Learning](https://mlsanity.com/paper/2609.29961/) (2026) ## 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.