Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learning

By Hao Yu, Sen Yang, Shenghuo Zhu. 2018

686 citations recorded by the source corpus.

In distributed training of deep neural networks, parallel minibatch SGD is widely used to speed up the training process by using multiple workers. It uses multiple workers to sample local stochastic gradients in parallel, aggregates all gradients in a single server to obtain the average, and updates each worker’s local model using a SGD update with the averaged gradient. Ideally, parallel mini-batch SGD can achieve a linear speed-up of the training time (with respect to the number of workers) compared with SGD over a single worker. However, such linear scalability in practice is significantly limited by the growing demand for gradient communication as more workers are involved. Model averaging, which periodically averages individual models trained over parallel workers, is another common practice used for distributed training of deep neural networks since (Zinkevich et al. 2010) (McDonald, Hall, and Mann 2010). Compared with parallel mini-batch SGD, the communication overhead of model averaging is significantly reduced. Impressively, tremendous experimental works have verified that model averaging can still achieve a good speed-up of the training time as long as the averaging interval is carefully controlled. However, it remains a mystery in theory why such a simple heuristic works so well. This paper provides a thorough and rigorous theoretical study on why model averaging can work as well as parallel mini-batch SGD with significantly less communication overhead.

Subfields: Artificial Intelligence, Optimization & Training, ML Systems & Hardware

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

In Optimization & Training

In ML Systems & Hardware

Citations in the corpus

Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning (2020, background): “[40] Hao Yu, Sen Yang, and Shenghuo Zhu.”
Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization (2020, methodology): “This analysis was further expanded to the non-IID data partition and client sampling cases by [11–18, 23, 24].”
On the Outsized Importance of Learning Rates in Local Update Methods (2020, neutral): “• In the homogeneous setting, if Θ = Θ1:K , and γ = η, then LocalUpdate is equivalent to Local SGD with K local steps.”
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).”
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).”
Secure Federated Submodel Learning (2019, background): “[32] advanced the convergency analysis of the global model in federated averaging by imposing smooth and bounded assumptions on the loss function.”
Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization (2019, methodology): “Strategy Convergence Rate Communication Rounds (T/τ) Extra Assumption Setting [43] O (”
Communication Efficient Decentralized Training with Multiple Local Updates (2019, methodology): “[49] and Zhou and Cong [56] show that the residual error grows quadratically in I .”
SCAFFOLD: Stochastic Controlled Averaging for On-Device Federated Learning (2019, background): “Several analyses bound this drift by using a very small step-size and assuming that the local updates admit bounded magnitude (Wang et al., 2019; Yu et al., 2019; Li et al., 2019b).”
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, methodology): “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): “Federated heavy hitters discovery with diﬀerential privacy was proposed in [Zhu et al., 2019].”
First Analysis of Local GD on Heterogeneous Data (2019, background): “For this reason, almost all prior work assumed bounded dissimilarity [8, 16, 17, 18] and addressed other less challenging aspects of federated learning such as decentralized communication, nonconvexity of the objective or unbalanced data partitioning.”
On the Convergence of FedAvg on Non-IID Data (2019, methodology): “Assumptions 3 and 4 have been made by the works (Zhang et al., 2013; Stich, 2018; Stich et al., 2018; Yu et al., 2019).”
Qsparse-Local-SGD: Distributed SGD With Quantization, Sparsification, and Local Computations (2019, background): “Figure 1(i)–1(l) demonstrate the performance of our scheme in comparison with EF-SIGNSGD [32], TopK-SGD [5], [18] and local SGD [20], [23].”
On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization (2019, methodology): “…first time that a distributed momentum SGD method for non-convex stochastic optimization is proven to possess the same linear speedup property (with communication reduction) as distributed SGD (without momentum) in (Lian et al., 2017; Yu et al., 2018; Wang & Joshi, 2018a; Jiang & Agrawal, 2018).”