Local SGD With a Communication Overhead Depending Only on the Number of Workers
Not on the map. Why?
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.
Key facts. Cited by 13 papers in the map (data through 7 Oct 2026). First posted on arXiv 3 Jun 2020.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 4; 2022: 2; 2023: 5; 2024: 1; 2025: 1.
13 papers.
Sort:
- 2021Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradientscited by 122
- 2021Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyondcited by 35
- 2023Federated Temporal Difference Learning with Linear Function Approximation under Environmental Heterogeneitycited by 25
- 2023Efficient Federated Learning via Local Adaptive Amended Optimizer with Linear Speedupcited by 23
- 2021Exploiting Heterogeneity in Robust Federated Best-Arm Identificationcited by 20
- 2021Adversarial training in communication constrained federated learningcited by 17
- 2023A Communication-Efficient Adaptive Algorithm for Federated Learning under Cumulative Regretcited by 7
- 2022The Role of Local Steps in Local SGDcited by 2
- 2023FedLALR: Client-Specific Adaptive Learning Rates Achieve Linear Speedup for Non-IID Datacited by 2
- 2023Local SGD Accelerates Convergence by Exploiting Second Order Information of the Loss Functioncited by 1
- 2025Characterizing the Accuracy-Communication-Privacy Trade-off in Distributed Stochastic Convex Optimizationcited by 1
- 2022On the Stability Analysis of Open Federated Learning Systemscited by 0
- 2025Characterizing the Accuracy-Communication-Privacy Trade-off in Distributed Stochastic Convex Optimization6 Jan 2025
- 2024EDiT: A Local-SGD-Based Efficient Distributed Training Method for Large Language Models10 Dec 2024
- 2023FedLALR: Client-Specific Adaptive Learning Rates Achieve Linear Speedup for Non-IID Data18 Sep 2023
- 2023Efficient Federated Learning via Local Adaptive Amended Optimizer with Linear Speedup30 Jul 2023
- 2023Local SGD Accelerates Convergence by Exploiting Second Order Information of the Loss Function24 May 2023
- 2023Federated Temporal Difference Learning with Linear Function Approximation under Environmental Heterogeneity4 Feb 2023
- 2023A Communication-Efficient Adaptive Algorithm for Federated Learning under Cumulative Regret21 Jan 2023
- 2022On the Stability Analysis of Open Federated Learning Systems25 Sep 2022
- 2022The Role of Local Steps in Local SGD14 Mar 2022
- 2021Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond20 Oct 2021
- 2021Exploiting Heterogeneity in Robust Federated Best-Arm Identification13 Sep 2021
- 2021Adversarial training in communication constrained federated learning1 Mar 2021
- 2021Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradientscited by 122
- 2021Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyondcited by 35
- 2023Federated Temporal Difference Learning with Linear Function Approximation under Environmental Heterogeneitycited by 25
- 2023Efficient Federated Learning via Local Adaptive Amended Optimizer with Linear Speedupcited by 23
- 2021Exploiting Heterogeneity in Robust Federated Best-Arm Identificationcited by 20
- 2021Adversarial training in communication constrained federated learningcited by 17
- 2023A Communication-Efficient Adaptive Algorithm for Federated Learning under Cumulative Regretcited by 7
- 2022The Role of Local Steps in Local SGDcited by 2
- 2023FedLALR: Client-Specific Adaptive Learning Rates Achieve Linear Speedup for Non-IID Datacited by 2
- 2023Local SGD Accelerates Convergence by Exploiting Second Order Information of the Loss Functioncited by 1
- 2025Characterizing the Accuracy-Communication-Privacy Trade-off in Distributed Stochastic Convex Optimizationcited by 1
- 2022On the Stability Analysis of Open Federated Learning Systemscited by 0
12 most cited of 13 All 13 (JSON)
- 2025Characterizing the Accuracy-Communication-Privacy Trade-off in Distributed Stochastic Convex Optimization6 Jan 2025
- 2024EDiT: A Local-SGD-Based Efficient Distributed Training Method for Large Language Models10 Dec 2024
- 2023FedLALR: Client-Specific Adaptive Learning Rates Achieve Linear Speedup for Non-IID Data18 Sep 2023
- 2023Efficient Federated Learning via Local Adaptive Amended Optimizer with Linear Speedup30 Jul 2023
- 2023Local SGD Accelerates Convergence by Exploiting Second Order Information of the Loss Function24 May 2023
- 2023Federated Temporal Difference Learning with Linear Function Approximation under Environmental Heterogeneity4 Feb 2023
- 2023A Communication-Efficient Adaptive Algorithm for Federated Learning under Cumulative Regret21 Jan 2023
- 2022On the Stability Analysis of Open Federated Learning Systems25 Sep 2022
- 2022The Role of Local Steps in Local SGD14 Mar 2022
- 2021Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond20 Oct 2021
- 2021Exploiting Heterogeneity in Robust Federated Best-Arm Identification13 Sep 2021
- 2021Adversarial training in communication constrained federated learning1 Mar 2021
12 newest of 13 All 13 (JSON)