# Accelerating Gossip SGD with Periodic Global Averaging

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

## Key facts

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

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour](https://mlsanity.com/paper/1706.02677/) (2017)
- [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019)
- [Large Batch Optimization for Deep Learning: Training BERT in 76 minutes](https://mlsanity.com/paper/1904.00962/) (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)
- [Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learning](https://mlsanity.com/paper/1807.06629/) (2018)
- [Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication](https://mlsanity.com/paper/1902.00340/) (2019)
- [Don't Use Large Mini-Batches, Use Local SGD](https://mlsanity.com/paper/1808.07217/) (2018)
- [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)
- [Demystifying Parallel and Distributed Deep Learning: An In-Depth Concurrency Analysis](https://mlsanity.com/paper/1802.09941/) (2018)
- [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)
- [SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum](https://mlsanity.com/paper/1910.00643/) (2019)
- [Decentralized Deep Learning with Arbitrary Communication Compression](https://mlsanity.com/paper/1907.09356/) (2019)
- [NEXT: In-Network Nonconvex Optimization](https://mlsanity.com/paper/1602.00591/) (2016)
- [DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression](https://mlsanity.com/paper/1905.05957/) (2019)
- [LAG: Lazily Aggregated Gradient for Communication-Efficient Distributed Learning](https://mlsanity.com/paper/1805.09965/) (2018)
- [Optimal algorithms for smooth and strongly convex distributed optimization in networks](https://mlsanity.com/paper/1702.08704/) (2017)
- [Adaptive Communication Strategies to Achieve the Best Error-Runtime Trade-off in Local-Update SGD](https://mlsanity.com/paper/1810.08313/) (2018)
- [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)

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

- [Exponential Graph is Provably Efficient for Decentralized Deep Training](https://mlsanity.com/paper/2110.13363/) (2021)
- [Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compression](https://mlsanity.com/paper/2206.03665/) (2022)
- [Decentralized Gradient Tracking with Local Steps](https://mlsanity.com/paper/2301.01313/) (2023)
- [Revisiting Optimal Convergence Rate for Smooth and Non-convex Stochastic Decentralized Optimization](https://mlsanity.com/paper/2210.07863/) (2022)
- [Epidemic Learning: Boosting Decentralized Learning with Randomized Communication](https://mlsanity.com/paper/2310.01972/) (2023)
- [BlueFog: Make Decentralized Algorithms Practical for Optimization and Deep Learning](https://mlsanity.com/paper/2111.04287/) (2021)
- [Decentralized Low-Rank Fine-Tuning of Large Language Models](https://mlsanity.com/paper/2501.15361/) (2025)
- [Decentralized Optimization Over the Stiefel Manifold by an Approximate Augmented Lagrangian Function](https://mlsanity.com/paper/2112.14949/) (2021)
- [Tackling Data Heterogeneity: A New Unified Framework for Decentralized SGD with Sample-induced Topology](https://mlsanity.com/paper/2207.03730/) (2022)
- [Over-the-Air Federated Learning and Optimization](https://mlsanity.com/paper/2310.10089/) (2023)
- [Beyond Exponential Graph: Communication-Efficient Topologies for Decentralized Learning via Finite-time Convergence](https://mlsanity.com/paper/2305.11420/) (2023)
- [The Effectiveness of Local Updates for Decentralized Learning under Data Heterogeneity](https://mlsanity.com/paper/2403.15654/) (2024)
- [Sign Bit is Enough: A Learning Synchronization Framework for Multi-hop All-reduce with Ultimate Compression](https://mlsanity.com/paper/2204.06787/) (2022)
- [Vanishing Variance Problem in Fully Decentralized Neural-Network Systems](https://mlsanity.com/paper/2404.04616/) (2024)
- [Communication-Efficient Federated Optimization over Semi-Decentralized Networks](https://mlsanity.com/paper/2311.18787/) (2023)
- [Adjacent Leader Decentralized Stochastic Gradient Descent](https://mlsanity.com/paper/2405.11389/) (2024)
- [Distribution-Aware Mobility-Assisted Decentralized Federated Learning](https://mlsanity.com/paper/2505.18866/) (2025)
- [A Byzantine-Robust Federated Learning with Nesterov Momentum](https://mlsanity.com/paper/2511.02657/) (2025)
- [Unifying Local Communications and Local Updates for LLM Pretraining](https://mlsanity.com/paper/2606.11081/) (2026)
- [On the Limit Performance of Floating Gossip](https://mlsanity.com/paper/2302.08413/) (2023)
- [FedDec: Peer-to-peer Aided Federated Learning](https://mlsanity.com/paper/2306.06715/) (2023)
- [On the Communication Complexity of Decentralized Stochastic Bilevel Optimization](https://mlsanity.com/paper/2311.11342/) (2023)
- [LAYUP: Asynchronous decentralized gradient descent with LAYer-wise UPdates](https://mlsanity.com/paper/2410.05985/) (2024)
- [EDiT: A Local-SGD-Based Efficient Distributed Training Method for Large Language Models](https://mlsanity.com/paper/2412.07210/) (2024)
- [A Unified Convergence Analysis for Semi-Decentralized Learning: Sampled-to-Sampled vs. Sampled-to-All Communication](https://mlsanity.com/paper/2511.11560/) (2025)

## 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.