mlsanityData to 7 Oct 2026

Optimal Complexity in Decentralized Training

arXiv 2006.08085 ↗First posted 15 Jun 2020cs.LG stat.MLcited by 59

Not on the map. Why?

Abstract (arXiv)

Decentralization is a promising method of scaling up parallel machine learning systems. In this paper, we provide a tight lower bound on the iteration complexity for such methods in a stochastic non-convex setting. Our lower bound reveals a theoretical gap in known convergence rates of many existing decentralized training algorithms, such as D-PSGD. We prove by construction this lower bound is tight and achievable. Motivated by our insights, we further propose DeTAG, a practical gossip-style decentralized algorithm that achieves the lower bound with only a logarithm gap. Empirically, we compare DeTAG with other decentralized algorithms on image classification tasks, and we show DeTAG enjoys faster convergence compared to baselines, especially on unshuffled data and in sparse networks.

Key facts. Cited by 59 papers in the map (data through 7 Oct 2026). First posted on arXiv 15 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 11; 2023: 11; 2024: 13; 2025: 11; 2026: 7.

59 papers.

Sort:

By area:

  1. 2021Edge Artificial Intelligence for 6G: Vision, Enabling Technologies, and Applicationscited by 96
  2. 2021RelaySum for Decentralized Deep Learning on Heterogeneous Datacited by 39
  3. 2022Topology-aware Generalization of Decentralized SGDcited by 37
  4. 2022Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compressioncited by 33
  5. 2021Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGDcited by 28
  6. 2022Beyond spectral gap: The role of the topology in decentralized learningcited by 27
  7. 2022Revisiting Optimal Convergence Rate for Smooth and Non-convex Stochastic Decentralized Optimizationcited by 22
  8. 2023Epidemic Learning: Boosting Decentralized Learning with Randomized Communicationcited by 21
  9. 2022Momentum Tracking: Momentum Acceleration for Decentralized Deep Learning on Heterogeneous Datacited by 20
  10. 2025Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexitycited by 17
  11. 2021BlueFog: Make Decentralized Algorithms Practical for Optimization and Deep Learningcited by 16
  12. 2023Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oraclescited by 16
38 more
  1. 2022Maximizing Communication Efficiency for Large-scale Training via 0/1 Adamcited by 15
  2. 2022Data-heterogeneity-aware Mixing for Decentralized Learningcited by 12
  3. 2023Lower Bounds and Accelerated Algorithms in Distributed Stochastic Optimization with Communication Compressioncited by 11
  4. 2024Trustworthy Federated Learning: Privacy, Security, and Beyondcited by 11
  5. 2023CEDAS: A Compressed Decentralized Stochastic Gradient Method with Improved Convergencecited by 9
  6. 2023Beyond Exponential Graph: Communication-Efficient Topologies for Decentralized Learning via Finite-time Convergencecited by 8
  7. 2023A2CiD2: Accelerating Asynchronous Communication in Decentralized Deep Learningcited by 7
  8. 2024Optimal and Efficient Algorithms for Decentralized Online Convex Optimizationcited by 7
  9. 2021Distributed Random Reshuffling over Networkscited by 6
  10. 2022An Efficient Stochastic Algorithm for Decentralized Nonconvex-Strongly-Concave Minimax Optimizationcited by 6
  11. 2022DoCoM: Compressed Decentralized Optimization with Near-Optimal Sample Complexitycited by 5
  12. 2022Sign Bit is Enough: A Learning Synchronization Framework for Multi-hop All-reduce with Ultimate Compressioncited by 5
  13. 2024LoCo: Low-Bit Communication Adaptor for Large-scale Model Trainingcited by 5
  14. 2022Optimal Complexity in Non-Convex Decentralized Learning over Time-Varying Networkscited by 4
  15. 2023A One-Sample Decentralized Proximal Algorithm for Non-Convex Stochastic Composite Optimizationcited by 4
  16. 2023On the Computation-Communication Trade-Off with A Flexible Gradient Tracking Approachcited by 4
  17. 2024Towards Faster Decentralized Stochastic Optimization with Communication Compressioncited by 4
  18. 2021Loss Landscape Dependent Self-Adjusting Learning Rates in Decentralized Stochastic Gradient Descentcited by 3
  19. 2023Beyond spectral gap (extended): The role of the topology in decentralized learningcited by 3
  20. 2024Online Optimization Perspective on First-Order and Zero-Order Decentralized Nonsmooth Nonconvex Stochastic Optimizationcited by 3
  21. 2023Distributed Random Reshuffling Methods with Improved Convergencecited by 2
  22. 2023Variance-reduced accelerated methods for decentralized stochastic double-regularized nonconvex strongly-concave minimax problemscited by 2
  23. 2024On the Complexity of Finite-Sum Smooth Optimization under the Polyak-Lojasiewicz Conditioncited by 2
  24. 2024Socialized Learning: A Survey of the Paradigm Shift for Edge Intelligence in Networked Systemscited by 2
  25. 2024Overlay-based Decentralized Federated Learning in Bandwidth-limited Networkscited by 2
  26. 2025DICE: Data Influence Cascade in Decentralized Learningcited by 2
  27. 2024Energy-efficient Decentralized Learning via Graph Sparsificationcited by 1
  28. 2024OledFL: Unleashing the Potential of Decentralized Federated Learning via Opposite Lookahead Enhancementcited by 1
  29. 2024ROSS: RObust decentralized Stochastic learning based on Shapley valuescited by 1
  30. 2025Enhancing Parallelism in Decentralized Stochastic Convex Optimizationcited by 1
  31. 2025Unveiling the Power of Multiple Gossip Steps: A Stability-Based Generalization Analysis in Decentralized Trainingcited by 1
  32. 2025Time-varying Mixing Matrix Design for Energy-efficient Decentralized Federated Learningcited by 1
  33. 2026Near-Optimal Decentralized Stochastic Nonconvex Optimization with Heavy-Tailed Noisecited by 1
  34. 2026Heterogeneous Decentralized Diffusion Modelscited by 1
  35. 2024Communication-Efficient and Privacy-Preserving Decentralized Meta-Learningcited by 0
  36. 2024Accelerating Distributed Optimization: A Primal-Dual Perspective on Local Stepscited by 0
  37. 2025Communication Optimization for Decentralized Learning atop Bandwidth-limited Edge Networkscited by 0
  38. 2025Topology-Aware Knowledge Propagation in Decentralized Learningcited by 0

50 most cited of 59 All 59 (JSON)