mlsanityData to 7 Oct 2026

A Unified Theory of Decentralized SGD with Changing Topology and Local Updates

arXiv 2003.10422 ↗First posted 23 Mar 2020cs.LG cs.DC math.OCcited by 361

Not on the map. Why?

Abstract (arXiv)

Decentralized stochastic optimization methods have gained a lot of attention recently, mainly because of their cheap per iteration cost, data locality, and their communication-efficiency. In this paper we introduce a unified convergence analysis that covers a large variety of decentralized SGD methods which so far have required different intuitions, have different applications, and which have been developed separately in various communities. Our algorithmic framework covers local SGD updates and synchronous and pairwise gossip updates on adaptive network topology. We derive universal convergence rates for smooth (convex and non-convex) problems and the rates interpolate between the heterogeneous (non-identically distributed data) and iid-data settings, recovering linear convergence rates in many special cases, for instance for over-parametrized models. Our proofs rely on weak assumptions (typically improving over prior work in several aspects) and recover (and improve) the best known complexity results for a host of important scenarios, such as for instance coorperative SGD and federated averaging (local SGD).

Key facts. Cited by 361 papers in the map (data through 7 Oct 2026). First posted on arXiv 23 Mar 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 47; 2022: 65; 2023: 75; 2024: 66; 2025: 68; 2026: 40.

361 papers.

Sort:

By area:

  1. 2021Towards Out-Of-Distribution Generalization: A Surveycited by 431
  2. 2021A Field Guide to Federated Optimizationcited by 312
  3. 2021Federated Multi-Task Learning under a Mixture of Distributionscited by 189
  4. 2022ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!cited by 134
  5. 2021Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradientscited by 122
  6. 2022Federated Learning with Partial Model Personalizationcited by 114
  7. 2021Edge Artificial Intelligence for 6G: Vision, Enabling Technologies, and Applicationscited by 96
  8. 2022Decentralized Training of Foundation Models in Heterogeneous Environmentscited by 87
  9. 2021MARINA: Faster Non-Convex Distributed Learning with Compressioncited by 77
  10. 2022Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learningcited by 76
  11. 2021Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Datacited by 69
  12. 2022An Improved Analysis of Gradient Tracking for Decentralized Machine Learningcited by 68
38 more
  1. 2021What Do We Mean by Generalization in Federated Learning?cited by 62
  2. 2021Exponential Graph is Provably Efficient for Decentralized Deep Trainingcited by 55
  3. 2022FedAvg with Fine Tuning: Local Updates Lead to Representation Learningcited by 55
  4. 2021Consensus Control for Decentralized Deep Learningcited by 49
  5. 2023Improving the Model Consistency of Decentralized Federated Learningcited by 45
  6. 2021STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learningcited by 43
  7. 2021Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivitycited by 43
  8. 2021DecentLaM: Decentralized Momentum SGD for Large-batch Deep Trainingcited by 40
  9. 2021RelaySum for Decentralized Deep Learning on Heterogeneous Datacited by 39
  10. 2021Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspectivecited by 38
  11. 2022Federated Minimax Optimization: Improved Convergence Analyses and Algorithmscited by 37
  12. 2022Topology-aware Generalization of Decentralized SGDcited by 37
  13. 2023Stochastic Gradient Descent under Markovian Sampling Schemescited by 37
  14. 2023Momentum Benefits Non-IID Federated Learning Simply and Provablycited by 37
  15. 2021Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devicescited by 36
  16. 2022On the Unreasonable Effectiveness of Federated Averaging with Heterogeneous Datacited by 36
  17. 2021Cross-Gradient Aggregation for Decentralized Learning from Non-IID datacited by 32
  18. 2023Decentralized Gradient Tracking with Local Stepscited by 32
  19. 2021Local Adaptivity in Federated Learning: Convergence and Consistencycited by 31
  20. 2022Refined Convergence and Topology Learning for Decentralized SGD with Heterogeneous Datacited by 31
  21. 2023On the Convergence of Federated Averaging with Cyclic Client Participationcited by 31
  22. 2021The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communicationcited by 30
  23. 2021Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learningcited by 30
  24. 2021Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Lossescited by 30
  25. 2022Byzantine-Robust Decentralized Learning via ClippedGossipcited by 29
  26. 2024Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learningcited by 29
  27. 2021Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGDcited by 28
  28. 2022Beyond spectral gap: The role of the topology in decentralized learningcited by 27
  29. 2022Muffliato: Peer-to-Peer Privacy Amplification for Decentralized Optimization and Averagingcited by 27
  30. 2023DoCoFL: Downlink Compression for Cross-Device Federated Learningcited by 27
  31. 2022Private Non-Convex Federated Learning Without a Trusted Servercited by 26
  32. 2021Accelerating Gossip SGD with Periodic Global Averagingcited by 25
  33. 2021Decentralized Local Stochastic Extra-Gradient for Variational Inequalitiescited by 25
  34. 2022Communication-Efficient Topologies for Decentralized Learning with O(1) Consensus Ratecited by 25
  35. 2023Robust Distributed Learning: Tight Error Bounds and Breakdown Point under Data Heterogeneitycited by 25
  36. 2022DELTA: Diverse Client Sampling for Fasting Federated Learningcited by 24
  37. 2021Personalized Federated Learning for Heterogeneous Clients with Clustered Knowledge Transfercited by 23
  38. 2021Towards Federated Learning on Time-Evolving Heterogeneous Datacited by 23

50 most cited of 361 All 361 (JSON)