# Local SGD With a Communication Overhead Depending Only on the Number of Workers

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jun 2020.

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

- [Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients](https://mlsanity.com/paper/2102.07053/) (2021)
- [Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond](https://mlsanity.com/paper/2110.10342/) (2021)
- [Federated Temporal Difference Learning with Linear Function Approximation under Environmental Heterogeneity](https://mlsanity.com/paper/2302.02212/) (2023)
- [Efficient Federated Learning via Local Adaptive Amended Optimizer with Linear Speedup](https://mlsanity.com/paper/2308.00522/) (2023)
- [Exploiting Heterogeneity in Robust Federated Best-Arm Identification](https://mlsanity.com/paper/2109.05700/) (2021)
- [Adversarial training in communication constrained federated learning](https://mlsanity.com/paper/2103.01319/) (2021)
- [A Communication-Efficient Adaptive Algorithm for Federated Learning under Cumulative Regret](https://mlsanity.com/paper/2301.08869/) (2023)
- [The Role of Local Steps in Local SGD](https://mlsanity.com/paper/2203.06798/) (2022)
- [FedLALR: Client-Specific Adaptive Learning Rates Achieve Linear Speedup for Non-IID Data](https://mlsanity.com/paper/2309.09719/) (2023)
- [Local SGD Accelerates Convergence by Exploiting Second Order Information of the Loss Function](https://mlsanity.com/paper/2305.15013/) (2023)
- [Characterizing the Accuracy-Communication-Privacy Trade-off in Distributed Stochastic Convex Optimization](https://mlsanity.com/paper/2501.03222/) (2025)
- [On the Stability Analysis of Open Federated Learning Systems](https://mlsanity.com/paper/2209.12307/) (2022)
- [EDiT: A Local-SGD-Based Efficient Distributed Training Method for Large Language Models](https://mlsanity.com/paper/2412.07210/) (2024)

## 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. Unfortunately, this could require 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 polynomial in log  (T) right) right) communications. In this paper, we give a new analysis of Local SGD. A consequence of our analysis is that Local SGD can achieve an error that scales as 1/(nT) with only a fixed number of communications independent of T: specifically, only Omega(n) communications are required.