# Refined Convergence and Topology Learning for Decentralized SGD with Heterogeneous Data

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 56 references that are in the map.
- First posted on arXiv 9 Apr 2022.

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

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [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)
- [The Non-IID Data Quagmire of Decentralized Machine Learning](https://mlsanity.com/paper/1910.00189/) (2019)
- [Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication](https://mlsanity.com/paper/1902.00340/) (2019)
- [Federated Multi-Task Learning under a Mixture of Distributions](https://mlsanity.com/paper/2108.10252/) (2021)
- [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)
- [D2: Decentralized Training over Decentralized Data](https://mlsanity.com/paper/1803.07068/) (2018)
- [Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization](https://mlsanity.com/paper/1709.08765/) (2017)
- [Decentralized Collaborative Learning of Personalized Models over Networks](https://mlsanity.com/paper/1610.05202/) (2016)
- [Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Data](https://mlsanity.com/paper/2102.04761/) (2021)
- [An Improved Analysis of Gradient Tracking for Decentralized Machine Learning](https://mlsanity.com/paper/2202.03836/) (2022)
- [MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling](https://mlsanity.com/paper/1905.09435/) (2019)
- [Exponential Graph is Provably Efficient for Decentralized Deep Training](https://mlsanity.com/paper/2110.13363/) (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)
- [Throughput-Optimal Topology Design for Cross-Silo Federated Learning](https://mlsanity.com/paper/2010.12229/) (2020)
- [Fully Decentralized Joint Learning of Personalized Models and Collaboration Graphs](https://mlsanity.com/paper/1901.08460/) (2019)
- [Decentralized gradient methods: does topology matter?](https://mlsanity.com/paper/2002.12688/) (2020)
- [On the Influence of Bias-Correction on Distributed Stochastic Optimization](https://mlsanity.com/paper/1903.10956/) (2019)
- [Cross-Gradient Aggregation for Decentralized Learning from Non-IID data](https://mlsanity.com/paper/2103.02051/) (2021)
- [New Convergence Aspects of Stochastic Gradient Algorithms](https://mlsanity.com/paper/1811.12403/) (2018)
- [Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGD](https://mlsanity.com/paper/2105.08023/) (2021)
- [Gossip Dual Averaging for Decentralized Optimization of Pairwise Functions](https://mlsanity.com/paper/1606.02421/) (2016)
- [Proximity Without Consensus in Online Multi-Agent Optimization](https://mlsanity.com/paper/1606.05578/) (2016)
- [Periodic Stochastic Gradient Descent with Momentum for Decentralized Training](https://mlsanity.com/paper/2008.10435/) (2020)

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

- [Beyond spectral gap: The role of the topology in decentralized learning](https://mlsanity.com/paper/2206.03093/) (2022)
- [One-Shot Federated Conformal Prediction](https://mlsanity.com/paper/2302.06322/) (2023)
- [Epidemic Learning: Boosting Decentralized Learning with Randomized Communication](https://mlsanity.com/paper/2310.01972/) (2023)
- [Momentum Tracking: Momentum Acceleration for Decentralized Deep Learning on Heterogeneous Data](https://mlsanity.com/paper/2209.15505/) (2022)
- [Decentralized SGD and Average-direction SAM are Asymptotically Equivalent](https://mlsanity.com/paper/2306.02913/) (2023)
- [Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithm](https://mlsanity.com/paper/2306.02939/) (2023)
- [Collaborative Learning via Prediction Consensus](https://mlsanity.com/paper/2305.18497/) (2023)
- [Differentially Private Decentralized Learning with Random Walks](https://mlsanity.com/paper/2402.07471/) (2024)
- [Mirror Sinkhorn: Fast Online Optimization on Transport Polytopes](https://mlsanity.com/paper/2211.10420/) (2022)
- [Asymmetrically Decentralized Federated Learning](https://mlsanity.com/paper/2310.05093/) (2023)
- [CoBo: Collaborative Learning via Bilevel Optimization](https://mlsanity.com/paper/2409.05539/) (2024)
- [Low-Cost Privacy-Preserving Decentralized Learning](https://mlsanity.com/paper/2403.11795/) (2024)
- [DIMAT: Decentralized Iterative Merging-And-Training for Deep Learning Models](https://mlsanity.com/paper/2404.08079/) (2024)
- [Topology Learning for Heterogeneous Decentralized Federated Learning over Unreliable D2D Networks](https://mlsanity.com/paper/2312.13611/) (2023)
- [Does Worst-Performing Agent Lead the Pack? Analyzing Agent Dynamics in Unified Distributed SGD](https://mlsanity.com/paper/2409.17499/) (2024)
- [DICE: Data Influence Cascade in Decentralized Learning](https://mlsanity.com/paper/2507.06931/) (2025)
- [Dynamic Topology Optimization for Non-IID Data in Decentralized Learning](https://mlsanity.com/paper/2602.03383/) (2026)
- [Fusing Multiple Algorithms for Heterogeneous Online Learning](https://mlsanity.com/paper/2312.05432/) (2023)
- [Energy-efficient Decentralized Learning via Graph Sparsification](https://mlsanity.com/paper/2401.03083/) (2024)
- [Distribution-Aware Mobility-Assisted Decentralized Federated Learning](https://mlsanity.com/paper/2505.18866/) (2025)
- [Fedivertex: a Graph Dataset based on Decentralized Social Networks for Trustworthy Machine Learning](https://mlsanity.com/paper/2505.20882/) (2025)
- [Time-varying Mixing Matrix Design for Energy-efficient Decentralized Federated Learning](https://mlsanity.com/paper/2512.24069/) (2025)
- [Tight Analysis of Decentralized SGD: A Markov Chain Perspective](https://mlsanity.com/paper/2601.07021/) (2026)
- [ERIS: Enhancing the Privacy-Utility-Scalability Trade-Off in Federated Learning via Federated Shard Aggregation](https://mlsanity.com/paper/2602.08617/) (2026)
- [Improved Convergence Analysis of Topology Dependence in Decentralized SGD](https://mlsanity.com/paper/2606.09154/) (2026)
- [Communication Optimization for Decentralized Learning atop Bandwidth-limited Edge Networks](https://mlsanity.com/paper/2504.12210/) (2025)
- [A Unified Convergence Analysis for Semi-Decentralized Learning: Sampled-to-Sampled vs. Sampled-to-All Communication](https://mlsanity.com/paper/2511.11560/) (2025)
- [Mobility-Assisted Decentralized Federated Learning: Convergence Analysis and A Data-Driven Approach](https://mlsanity.com/paper/2512.24694/) (2025)
- [Optimizing Stochastic Gradient Push under Broadcast Communications](https://mlsanity.com/paper/2604.15549/) (2026)
- [Stability and Generalization for Decentralized Markov SGD](https://mlsanity.com/paper/2605.01701/) (2026)

## Abstract (arXiv)

One of the key challenges in decentralized and federated learning is to design algorithms that efficiently deal with highly heterogeneous data distributions across agents. In this paper, we revisit the analysis of the popular Decentralized Stochastic Gradient Descent algorithm (D-SGD) under data heterogeneity. We exhibit the key role played by a new quantity, called neighborhood heterogeneity, on the convergence rate of D-SGD. By coupling the communication topology and the heterogeneity, our analysis sheds light on the poorly understood interplay between these two concepts. We then argue that neighborhood heterogeneity provides a natural criterion to learn data-dependent topologies that reduce (and can even eliminate) the otherwise detrimental effect of data heterogeneity on the convergence time of D-SGD. For the important case of classification with label skew, we formulate the problem of learning such a good topology as a tractable optimization problem that we solve with a Frank-Wolfe algorithm. As illustrated over a set of simulated and real-world experiments, our approach provides a principled way to design a sparse topology that balances the convergence speed and the per-iteration communication costs of D-SGD under data heterogeneity.