Local SGD Converges Fast and Communicates Little
By Sebastian U. Stich. 2018
1,280 citations recorded by the source corpus.
Mini-batch stochastic gradient descent (SGD) is state of the art in large scale distributed training. The scheme can reach a linear speedup with respect to the number of workers, but this is rarely seen in practice as the scheme often suffers from large network delays and bandwidth limits. To overcome this communication bottleneck recent works propose to reduce the communication frequency. An algorithm of this type is local SGD that runs SGD independently in parallel on different workers and averages the sequences only once in a while. This scheme shows promising results in practice, but eluded thorough theoretical analysis. We prove concise convergence rates for local SGD on convex problems and show that it converges at the same rate as mini-batch SGD in terms of number of evaluated gradients, that is, the scheme achieves linear speedup in the number of workers and mini-batch size. The number of communication rounds can be reduced up to a factor of T^{1/2}---where T denotes the number of total steps---compared to mini-batch SGD. This also holds for asynchronous implementations. Local SGD can also be used for large scale training of deep learning models. The results shown here aim serving as a guideline to further explore the theoretical and practical aspects of local SGD in these applications.
Subfields: Artificial Intelligence, Electrical and Electronic Engineering, Optimization & Training, Federated & Distributed Learning
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Peter Richtárik
- Martin Jaggi
- Sebastian U. Stich
- Jakub Konecný
- Qiang Yang
- Jianyu Wang
- Virginia Smith
- Aryan Mokhtari
In Electrical and Electronic Engineering
- H. Vincent Poor
- Jianyu Wang
- Martin Jaggi
- Gauri Joshi
- Sebastian U. Stich
- Medhi Bennis
- Mingzhe Chen
- Sai Praneeth Karimireddy
In Optimization & Training
- Peter Richtárik
- Sebastian U. Stich
- Martin Jaggi
- Jakub Konecný
- Jianyu Wang
- Nicolas Loizou
- Gauri Joshi
- Aryan Mokhtari
In Federated & Distributed Learning
- Peter Richtárik
- Jianyu Wang
- Gauri Joshi
- Mehrdad Mahdavi
- Jakub Konecný
- Aryan Mokhtari
- Virginia Smith
- Zachary B. Charles
Citations in the corpus
- Advances and Open Problems in Federated Learning (2019, methodology): “References 169 [99] S. U. Stich, “Local SGD converges fast and communicates little,” in International Conference on Learning Representations (ICLR), 2019.”
- Federated Optimization in Heterogeneous Networks (2018, background): “For instance, parallel SGD and related variants (Zhang et al., 2015; Shamir et al., 2014; Reddi et al., 2016; Zhou & Cong, 2018; Stich, 2019; Wang & Joshi, 2018; Woodworth et al., 2018; Lin et al., 2020), which make local updates similar to FedAvg, have been studied in the IID setting.”
- Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning (2020, background): “In [28], and more recently in [29, 26, 16, 37], sharper and refined analyses of the same method (sometimes called local SGD) for identical functions.”
- Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization (2020, methodology): “Besides, asynchronous federated optimization algorithms proposed in [41, 9] take a different approach of allowing clients make updates to stale versions of the global model, and their analyses are limited to IID local datasets and convex local functions.”
- Attack of the Tails: Yes, You Really Can Backdoor Federated Learning (2020, methodology): “Each client usually runs a standard optimization algorithm such as SGD to update its own local model.”
- On the Outsized Importance of Learning Rates in Local Update Methods (2020, methodology): “, 2017) and (Stich, 2019) for example), these two are effectively the same algorithm.”
- A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, methodology): “…(McMahan et al., 2016; 2017) and has recently attracted the attention of the theoretical community in the seek of the best convergence rates (Stich, 2019b; Wang & Joshi, 2018; Yu et al., 2019; Basu et al., 2019; Patel & Dieuleveut, 2019; Stich & Karimireddy, 2019; Li et al., 2019; Khaled et…”
- Adaptive Federated Optimization (2020, methodology): “When the client are homogeneous, FEDAVG reduces to local SGD (Zinkevich et al., 2010), which has been analyzed theoretically by many works (Stich, 2019; Yu et al., 2019; Wang and Joshi, 2018; Stich and Karimireddy, 2019).”
- Personalized Federated Learning: A Meta-Learning Approach (2020, methodology): “This includes quantization and compression ideas (Reisizadeh et al., 2019; Dai et al., 2019) as well as performing multiple local updates before communicating with the master (Stich, 2018; Lin et al., 2018; Wang and Joshi, 2018).”
- Is Local SGD Better than Minibatch SGD? (2020, methodology): “A string of recent papers have attempted to analyze local SGD for convex objectives, (e.g. Stich, 2018; Stich and Karimireddy, 2019; Khaled et al., 2019; Dieuleveut and Patel, 2019).”
- Local AdaAlter: Communication-Efficient Stochastic Gradient Descent with Adaptive Learning Rates (2019, methodology): “, less frequent synchronization, and periodically averaging the models across the workers (Stich, 2018; Lin et al., 2018; Yu et al., 2018; Wang and Joshi, 2018; Yu et al., 2019).”
- Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization (2019, methodology): “In local SGD, the idea is to perform local updates with periodic averaging, wherein machines update their own local models, and the models of the different nodes are averaged periodically [43, 38, 51, 23, 45, 49, 33].”
- Communication Efficient Decentralized Training with Multiple Local Updates (2019, methodology): “To directly save communication, many researchers let more local updates happen before each synchronization [26, 22, 39, 44, 43].”
- SCAFFOLD: Stochastic Controlled Averaging for On-Device Federated Learning (2019, methodology): “Stich (2018) and, more recently Stich and Karimireddy (2019) and Patel and Dieuleveut (2019), gave a sharper analysis of the same method, under the name of local SGD, also for identical functions.”
- Central Server Free Federated Learning over Single-sided Trust Social Networks (2019, background): “Recent rigorous theoretical analysis (Stich, 2018; Wang and Joshi, 2018; Yu et al., 2018; Lin et al., 2018) shows that FedAvg is a special case of averaging periodic SGD (also called local SGD) which allows nodes to perform local updates and infrequent synchronization between them to communicate les”
- SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum (2019, background): “Approaches such as Local SGD reduce the frequency of communication by having workers perform multiple updates between each round of communication (McDonald et al., 2010; McMahan et al., 2017; Zhou & Cong, 2018; Stich, 2019; Yu et al., 2019b).”
- FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization (2019, background): “For ⌧ 1, Theorem 1 does not recover the result in [Stich, 2018] due to our weaker condition in Assumption 3.”