# Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGD

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 58 references that are in the map.
- First posted on arXiv 17 May 2021.

## Builds on (most cited first, 30 of 30)

- [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)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization](https://mlsanity.com/paper/1905.03817/) (2019)
- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [On the Convergence of Decentralized Gradient Descent](https://mlsanity.com/paper/1310.7063/) (2013)
- [Asynchronous Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1710.06952/) (2017)
- [Stochastic Gradient Push for Distributed Deep Learning](https://mlsanity.com/paper/1811.10792/) (2018)
- [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016)
- [D2: Decentralized Training over Decentralized Data](https://mlsanity.com/paper/1803.07068/) (2018)
- [NEXT: In-Network Nonconvex Optimization](https://mlsanity.com/paper/1602.00591/) (2016)
- [Distributed Stochastic Gradient Tracking Methods](https://mlsanity.com/paper/1805.11454/) (2018)
- [Optimal algorithms for smooth and strongly convex distributed optimization in networks](https://mlsanity.com/paper/1702.08704/) (2017)
- [Unified Optimal Analysis of the (Stochastic) Gradient Method](https://mlsanity.com/paper/1907.04232/) (2019)
- [Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Data](https://mlsanity.com/paper/2102.04761/) (2021)
- [Optimal Complexity in Decentralized Training](https://mlsanity.com/paper/2006.08085/) (2020)
- [On the Linear Convergence of the ADMM in Decentralized Consensus Optimization](https://mlsanity.com/paper/1307.5561/) (2013)
- [An improved convergence analysis for decentralized online stochastic non-convex optimization](https://mlsanity.com/paper/2008.04195/) (2020)
- [A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates](https://mlsanity.com/paper/1704.07807/) (2017)
- [Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Development](https://mlsanity.com/paper/1702.05122/) (2017)
- [Optimal Algorithms for Non-Smooth Distributed Optimization in Networks](https://mlsanity.com/paper/1806.00291/) (2018)
- [DecentLaM: Decentralized Momentum SGD for Large-batch Deep Training](https://mlsanity.com/paper/2104.11981/) (2021)
- [On the Influence of Bias-Correction on Distributed Stochastic Optimization](https://mlsanity.com/paper/1903.10956/) (2019)
- [A Dual Approach for Optimal Algorithms in Distributed Optimization over Networks](https://mlsanity.com/paper/1809.00710/) (2018)
- [Balancing Communication and Computation in Distributed Optimization](https://mlsanity.com/paper/1709.02999/) (2017)
- [Decentralized Proximal Gradient Algorithms with Linear Convergence Rates](https://mlsanity.com/paper/1909.06479/) (2019)
- [Fast decentralized non-convex finite-sum optimization with recursive variance reduction](https://mlsanity.com/paper/2008.07428/) (2020)
- [Exact Diffusion for Distributed Optimization and Learning --- Part II: Convergence Analysis](https://mlsanity.com/paper/1702.05142/) (2017)
- [Improving the Transient Times for Distributed Stochastic Gradient Methods](https://mlsanity.com/paper/2105.04851/) (2021)

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

- [ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!](https://mlsanity.com/paper/2202.09357/) (2022)
- [Stochastic Controlled Averaging for Federated Learning with Communication Compression](https://mlsanity.com/paper/2308.08165/) (2023)
- [An Improved Analysis of Gradient Tracking for Decentralized Machine Learning](https://mlsanity.com/paper/2202.03836/) (2022)
- [Exponential Graph is Provably Efficient for Decentralized Deep Training](https://mlsanity.com/paper/2110.13363/) (2021)
- [Momentum Benefits Non-IID Federated Learning Simply and Provably](https://mlsanity.com/paper/2306.16504/) (2023)
- [Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compression](https://mlsanity.com/paper/2206.03665/) (2022)
- [Refined Convergence and Topology Learning for Decentralized SGD with Heterogeneous Data](https://mlsanity.com/paper/2204.04452/) (2022)
- [Revisiting Optimal Convergence Rate for Smooth and Non-convex Stochastic Decentralized Optimization](https://mlsanity.com/paper/2210.07863/) (2022)
- [BlueFog: Make Decentralized Algorithms Practical for Optimization and Deep Learning](https://mlsanity.com/paper/2111.04287/) (2021)
- [Unbiased Compression Saves Communication in Distributed Optimization: When and How Much?](https://mlsanity.com/paper/2305.16297/) (2023)
- [Data-heterogeneity-aware Mixing for Decentralized Learning](https://mlsanity.com/paper/2204.06477/) (2022)
- [CEDAS: A Compressed Decentralized Stochastic Gradient Method with Improved Convergence](https://mlsanity.com/paper/2301.05872/) (2023)
- [Optimal Multitask Linear Regression and Contextual Bandits under Sparse Heterogeneity](https://mlsanity.com/paper/2306.06291/) (2023)
- [DSGD-CECA: Decentralized SGD with Communication-Optimal Exact Consensus Algorithm](https://mlsanity.com/paper/2306.00256/) (2023)
- [Optimal Complexity in Non-Convex Decentralized Learning over Time-Varying Networks](https://mlsanity.com/paper/2211.00533/) (2022)
- [On the Trade-off between Flatness and Optimization in Distributed Learning](https://mlsanity.com/paper/2406.20006/) (2024)
- [Distributed Random Reshuffling Methods with Improved Convergence](https://mlsanity.com/paper/2306.12037/) (2023)
- [A Proximal Gradient Method With Probabilistic Multi-Gossip Communications for Decentralized Composite Optimization](https://mlsanity.com/paper/2312.11861/) (2023)
- [Collaborative Learning of Discrete Distributions under Heterogeneity and Communication Constraints](https://mlsanity.com/paper/2206.00707/) (2022)
- [Adjacent Leader Decentralized Stochastic Gradient Descent](https://mlsanity.com/paper/2405.11389/) (2024)
- [Generalization Error Analysis for Attack-Free and Byzantine-Resilient Decentralized Learning with Data Heterogeneity](https://mlsanity.com/paper/2506.09438/) (2025)
- [FedSLoP: Memory-Efficient Federated Learning with Low-Rank Gradient Projection](https://mlsanity.com/paper/2604.24012/) (2026)
- [Accelerated Decentralized Stochastic Gradient Descent for Strongly Convex Optimization](https://mlsanity.com/paper/2606.07496/) (2026)
- [Row-Stochastic Matrices Can Provably Outperform Doubly Stochastic Matrices in Decentralized Learning](https://mlsanity.com/paper/2511.19513/) (2025)
- [Local adapt-then-combine algorithms for distributed nonsmooth optimization: Achieving provable communication acceleration](https://mlsanity.com/paper/2602.16148/) (2026)
- [Stability and Generalization for Decentralized Markov SGD](https://mlsanity.com/paper/2605.01701/) (2026)
- [Unveiling High-Probability Generalization in Decentralized SGD](https://mlsanity.com/paper/2605.10205/) (2026)
- [Theoretical Foundations of Communication-Efficient, Robust, and Practical Distributed and Federated Optimization](https://mlsanity.com/paper/2608.06563/) (2026)
- [SPADE-DFL: Communication-Efficient Decentralized Federated Learning via Derivative-Free Linearized ADMM](https://mlsanity.com/paper/2609.29446/) (2026)

## Abstract (arXiv)

We consider the decentralized stochastic optimization problems, where a network of n nodes, each owning a local cost function, cooperate to find a minimizer of the globally-averaged cost. A widely studied decentralized algorithm for this problem is decentralized SGD (D-SGD), in which each node averages only with its neighbors. D-SGD is efficient in single-iteration communication, but it is very sensitive to the network topology. For smooth objective functions, the transient stage (which measures the number of iterations the algorithm has to experience before achieving the linear speedup stage) of D-SGD is on the order of Omega(n/(1-β)2) and Omega(n3/(1-β)4) for strongly and generally convex cost functions, respectively, where 1-β ∈ (0,1) is a topology-dependent quantity that approaches 0 for a large and sparse network. Hence, D-SGD suffers from slow convergence for large and sparse networks. In this work, we study the non-asymptotic convergence property of the D2/Exact-diffusion algorithm. By eliminating the influence of data heterogeneity between nodes, D2/Exact-diffusion is shown to have an enhanced transient stage that is on the order of tildeOmega(n/(1-β)) and Omega(n3/(1-β)2) for strongly and generally convex cost functions, respectively. Moreover, when D2/Exact-diffusion is implemented with gradient accumulation and multi-round gossip communications, its transient stage can be further improved to tildeOmega(1/(1-β)^frac12) and tildeOmega(n/(1-β)) for strongly and generally convex cost functions, respectively. These established results for D2/Exact-Diffusion have the best (i.e., weakest) dependence on network topology to our knowledge compared to existing decentralized algorithms. We also conduct numerical simulations to validate our theories.