mlsanityData to 7 Oct 2026

Accelerating Gossip SGD with Periodic Global Averaging

arXiv 2105.09080 ↗First posted 19 May 2021cs.LG cs.DCcited by 25

Not on the map. Why?

Abstract (arXiv)

Communication overhead hinders the scalability of large-scale distributed training. Gossip SGD, where each node averages only with its neighbors, is more communication-efficient than the prevalent parallel SGD. However, its convergence rate is reversely proportional to quantity 1-β which measures the network connectivity. On large and sparse networks where 1-β → 0, Gossip SGD requires more iterations to converge, which offsets against its communication benefit. This paper introduces Gossip-PGA, which adds Periodic Global Averaging into Gossip SGD. Its transient stage, i.e., the iterations required to reach asymptotic linear speedup stage, improves from Omega(β4 n3/(1-β)4) to Omega(β4 n3 H4) for non-convex problems. The influence of network topology in Gossip-PGA can be controlled by the averaging period H. Its transient-stage complexity is also superior to Local SGD which has order Omega(n3 H4). Empirical results of large-scale training on image classification (ResNet50) and language modeling (BERT) validate our theoretical findings.

Key facts. Cited by 25 papers in the map (data through 7 Oct 2026). Builds on 37 of its 57 references that are in the map. First posted on arXiv 19 May 2021.

Builds on

37 of 57 references.

References · 37

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  3. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  4. 2017Accurate, Large Minibatch SGD: Training ImageNet in 1 Hourcited by 1,479
  5. 2019On the Convergence of FedAvg on Non-IID Datacited by 1,220
  6. 2019Large Batch Optimization for Deep Learning: Training BERT in 76 minutescited by 671
  7. 2018Local SGD Converges Fast and Communicates Littlecited by 595
  8. 2017Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descentcited by 496
  9. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 361
  10. 2018Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learningcited by 277
  11. 2019Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communicationcited by 218
  12. 2018Don't Use Large Mini-Batches, Use Local SGDcited by 201
25 more
  1. 2014EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimizationcited by 160
  2. 2017Asynchronous Decentralized Parallel Stochastic Gradient Descentcited by 159
  3. 2013On the Convergence of Decentralized Gradient Descentcited by 158
  4. 2018Demystifying Parallel and Distributed Deep Learning: An In-Depth Concurrency Analysiscited by 154
  5. 2018Stochastic Gradient Push for Distributed Deep Learningcited by 152
  6. 2016Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphscited by 149
  7. 2018D2: Decentralized Training over Decentralized Datacited by 140
  8. 2019SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentumcited by 121
  9. 2019Decentralized Deep Learning with Arbitrary Communication Compressioncited by 109
  10. 2016NEXT: In-Network Nonconvex Optimizationcited by 107
  11. 2019DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compressioncited by 98
  12. 2018LAG: Lazily Aggregated Gradient for Communication-Efficient Distributed Learningcited by 95
  13. 2017Optimal algorithms for smooth and strongly convex distributed optimization in networkscited by 81
  14. 2018Adaptive Communication Strategies to Achieve the Best Error-Runtime Trade-off in Local-Update SGDcited by 76
  15. 2013On the Linear Convergence of the ADMM in Decentralized Consensus Optimizationcited by 57
  16. 2020An improved convergence analysis for decentralized online stochastic non-convex optimizationcited by 53
  17. 2017A decentralized proximal-gradient method with network independent step-sizes and separated convergence ratescited by 51
  18. 2017Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Developmentcited by 50
  19. 2018Optimal Algorithms for Non-Smooth Distributed Optimization in Networkscited by 41
  20. 2019On the Influence of Bias-Correction on Distributed Stochastic Optimizationcited by 34
  21. 2016Parallel SGD: When does averaging help?cited by 30
  22. 2018COLA: Decentralized Linear Learningcited by 30
  23. 2018A Dual Approach for Optimal Algorithms in Distributed Optimization over Networkscited by 27
  24. 2017Balancing Communication and Computation in Distributed Optimizationcited by 23
  25. 2019Communication-Efficient Local Decentralized SGD Methodscited by 21

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 4; 2023: 8; 2024: 5; 2025: 4; 2026: 1.

25 papers.

Sort:

  1. 2021Exponential Graph is Provably Efficient for Decentralized Deep Trainingcited by 55
  2. 2022Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compressioncited by 33
  3. 2023Decentralized Gradient Tracking with Local Stepscited by 32
  4. 2022Revisiting Optimal Convergence Rate for Smooth and Non-convex Stochastic Decentralized Optimizationcited by 22
  5. 2023Epidemic Learning: Boosting Decentralized Learning with Randomized Communicationcited by 21
  6. 2021BlueFog: Make Decentralized Algorithms Practical for Optimization and Deep Learningcited by 16
  7. 2025Decentralized Low-Rank Fine-Tuning of Large Language Modelscited by 12
  8. 2021Decentralized Optimization Over the Stiefel Manifold by an Approximate Augmented Lagrangian Functioncited by 11
  9. 2022Tackling Data Heterogeneity: A New Unified Framework for Decentralized SGD with Sample-induced Topologycited by 10
  10. 2023Over-the-Air Federated Learning and Optimizationcited by 10
  11. 2023Beyond Exponential Graph: Communication-Efficient Topologies for Decentralized Learning via Finite-time Convergencecited by 8
  12. 2024The Effectiveness of Local Updates for Decentralized Learning under Data Heterogeneitycited by 7
13 more
  1. 2022Sign Bit is Enough: A Learning Synchronization Framework for Multi-hop All-reduce with Ultimate Compressioncited by 5
  2. 2024Vanishing Variance Problem in Fully Decentralized Neural-Network Systemscited by 3
  3. 2023Communication-Efficient Federated Optimization over Semi-Decentralized Networkscited by 2
  4. 2024Adjacent Leader Decentralized Stochastic Gradient Descentcited by 1
  5. 2025Distribution-Aware Mobility-Assisted Decentralized Federated Learningcited by 1
  6. 2025A Nesterov-Accelerated Byzantine-Robust Federated Learningcited by 1
  7. 2026Unifying Local Communications and Local Updates for LLM Pretrainingcited by 1
  8. 2023On the Limit Performance of Floating Gossipcited by 0
  9. 2023FedDec: Peer-to-peer Aided Federated Learningcited by 0
  10. 2023On the Communication Complexity of Decentralized Stochastic Bilevel Optimizationcited by 0
  11. 2024LAYUP: Asynchronous decentralized gradient descent with LAYer-wise UPdatescited by 0
  12. 2024EDiT: A Local-SGD-Based Efficient Distributed Training Method for Large Language Modelscited by 0
  13. 2025A Unified Convergence Analysis for Semi-Decentralized Learning: Sampled-to-Sampled vs. Sampled-to-All Communicationcited by 0