# Communication-efficient SGD: From Local SGD to One-Shot Averaging

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 75 references that are in the map.
- First posted on arXiv 9 Jun 2021.

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

- [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)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training](https://mlsanity.com/paper/1712.01887/) (2017)
- [Sparsified SGD with Memory](https://mlsanity.com/paper/1809.07599/) (2018)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [Horovod: fast and easy distributed deep learning in TensorFlow](https://mlsanity.com/paper/1802.05799/) (2018)
- [Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learning](https://mlsanity.com/paper/1807.06629/) (2018)
- [Tighter Theory for Local SGD on Identical and Heterogeneous Data](https://mlsanity.com/paper/1909.04746/) (2019)
- [Don't Use Large Mini-Batches, Use Local SGD](https://mlsanity.com/paper/1808.07217/) (2018)
- [Is Local SGD Better than Minibatch SGD?](https://mlsanity.com/paper/2002.07839/) (2020)
- [Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization](https://mlsanity.com/paper/1910.13598/) (2019)
- [Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms](https://mlsanity.com/paper/1808.07576/) (2018)
- [Stability and Generalization of Learning Algorithms that Converge to Global Optima](https://mlsanity.com/paper/1710.08402/) (2017)
- [On the convergence properties of a K-step averaging stochastic gradient descent algorithm for nonconvex optimization](https://mlsanity.com/paper/1708.01012/) (2017)
- [Deep learning with Elastic Averaging SGD](https://mlsanity.com/paper/1412.6651/) (2014)
- [Federated Accelerated Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08950/) (2020)
- [On the Convergence Rate of Training Recurrent Neural Networks](https://mlsanity.com/paper/1810.12065/) (2018)
- [Adaptive Communication Strategies to Achieve the Best Error-Runtime Trade-off in Local-Update SGD](https://mlsanity.com/paper/1810.08313/) (2018)
- [MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling](https://mlsanity.com/paper/1905.09435/) (2019)
- [Communication Complexity of Distributed Convex Learning and Optimization](https://mlsanity.com/paper/1506.01900/) (2015)
- [Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition](https://mlsanity.com/paper/1308.6370/) (2013)
- [Parallel SGD: When does averaging help?](https://mlsanity.com/paper/1606.07365/) (2016)
- [Communication-Efficient Distributed Deep Learning: A Comprehensive Survey](https://mlsanity.com/paper/2003.06307/) (2020)
- [Robust Asynchronous Stochastic Gradient-Push: Asymptotically Optimal and Network-Independent Performance for Strongly Convex Functions](https://mlsanity.com/paper/1811.03982/) (2018)
- [On the Optimality of Averaging in Distributed Statistical Learning](https://mlsanity.com/paper/1407.2724/) (2014)
- [An Accelerated Decentralized Stochastic Proximal Algorithm for Finite Sums](https://mlsanity.com/paper/1905.11394/) (2019)
- [Multi-GPU Training of ConvNets](https://mlsanity.com/paper/1312.5853/) (2013)

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

- [FedAvg with Fine Tuning: Local Updates Lead to Representation Learning](https://mlsanity.com/paper/2205.13692/) (2022)
- [Federated Minimax Optimization: Improved Convergence Analyses and Algorithms](https://mlsanity.com/paper/2203.04850/) (2022)
- [FusionAI: Decentralized Training and Deploying LLMs with Massive Consumer-Level GPUs](https://mlsanity.com/paper/2309.01172/) (2023)
- [Fast Composite Optimization and Statistical Recovery in Federated Learning](https://mlsanity.com/paper/2207.08204/) (2022)
- [DIGEST: Fast and Communication Efficient Decentralized Learning with Local Updates](https://mlsanity.com/paper/2307.07652/) (2023)
- [Communication-Efficient Large-Scale Distributed Deep Learning: A Comprehensive Survey](https://mlsanity.com/paper/2404.06114/) (2024)
- [WASH: Train your Ensemble with Communication-Efficient Weight Shuffling, then Average](https://mlsanity.com/paper/2405.17517/) (2024)
- [Minibatch and Local SGD: Algorithmic Stability and Linear Speedup in Generalization](https://mlsanity.com/paper/2310.01139/) (2023)
- [Clustered Federated Learning based on Nonconvex Pairwise Fusion](https://mlsanity.com/paper/2211.04218/) (2022)
- [Adaptive Federated Learning via New Entropy Approach](https://mlsanity.com/paper/2303.14966/) (2023)
- [Improving training time and GPU utilization in geo-distributed language model training](https://mlsanity.com/paper/2411.14458/) (2024)
- [The Role of Local Steps in Local SGD](https://mlsanity.com/paper/2203.06798/) (2022)
- [On Arbitrary Compression for Decentralized Consensus and Stochastic Optimization over Directed Networks](https://mlsanity.com/paper/2204.08160/) (2022)
- [Dynamic Fair Federated Learning Based on Reinforcement Learning](https://mlsanity.com/paper/2311.00959/) (2023)
- [Local SGD in Overparameterized Linear Regression](https://mlsanity.com/paper/2210.11562/) (2022)
- [On the Communication Complexity of Decentralized Stochastic Bilevel Optimization](https://mlsanity.com/paper/2311.11342/) (2023)
- [Distributed Continual Learning with CoCoA in High-dimensional Linear Regression](https://mlsanity.com/paper/2312.01795/) (2023)
- [LoDAdaC: a unified local training-based decentralized framework with adaptive gradients and compressed communication](https://mlsanity.com/paper/2604.09970/) (2026)
- [AutoLoCo: Communication Efficient Distributed LLM Training via Adaptive Synchronization](https://mlsanity.com/paper/2609.36662/) (2026)

## Abstract (arXiv)

We consider speeding up stochastic gradient descent (SGD) by parallelizing it across multiple workers. We assume the same data set is shared among N workers, who can take SGD steps and coordinate with a central server. While it is possible to obtain a linear reduction in the variance by averaging all the stochastic gradients at every step, this requires a lot of communication between the workers and the server, which can dramatically reduce the gains from parallelism. The Local SGD method, proposed and analyzed in the earlier literature, suggests machines should make many local steps between such communications. While the initial analysis of Local SGD showed it needs Omega ( √T ) communications for T local gradient steps in order for the error to scale proportionately to 1/(NT), this has been successively improved in a string of papers, with the state of the art requiring Omega left( N left( mbox poly (log T) right) right) communications. In this paper, we suggest a Local SGD scheme that communicates less overall by communicating less frequently as the number of iterations grows. Our analysis shows that this can achieve an error that scales as 1/(NT) with a number of communications that is completely independent of T. In particular, we show that Omega(N) communications are sufficient. Empirical evidence suggests this bound is close to tight as we further show that √N or N3/4 communications fail to achieve linear speed-up in simulations. Moreover, we show that under mild assumptions, the main of which is twice differentiability on any neighborhood of the optimal solution, one-shot averaging which only uses a single round of communication can also achieve the optimal convergence rate asymptotically.