Parallel SGD: When does averaging help?

By Jian Zhang, Christopher De Sa, Ioannis Mitliagkas, Christopher R'e. 2016

114 citations recorded by the source corpus.

Consider a number of workers running SGD independently on the same pool of data and averaging the models every once in a while -- a common but not well understood practice. We study model averaging as a variance-reducing mechanism and describe two ways in which the frequency of averaging affects convergence. For convex objectives, we show the benefit of frequent averaging depends on the gradient variance envelope. For non-convex objectives, we illustrate that this benefit depends on the presence of multiple globally optimal points. We complement our findings with multicore experiments on both synthetic and real data.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability, Optimization & Training

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 Computational Mechanics

In Statistics and Probability

In Optimization & Training

Citations in the corpus

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.”
Is Local SGD Better than Minibatch SGD? (2020, methodology): “Thus, while local SGD is frequently better than minibatch SGD—and we can now see this both in theory and in practice (see experiments by e.g. Zhang et al., 2016; Lin et al., 2018; Zhou and Cong, 2018)—our work identiﬁes regimes in which users should be wary of using local SGD without considering…”
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].”
Decentralized Deep Learning with Arbitrary Communication Compression (2019, methodology): “, 2019) or performing multiple local SGD steps before averaging (Zhang et al., 2016; McMahan et al., 2017; Lin et al., 2018a).”
Communication trade-offs for synchronized distributed SGD with large step size (2019, background): “While OSA requires only a single communication step, it typically does not perform very well in practice (Zhang et al., 2016).”
Don't Use Large Mini-Batches, Use Local SGD (2018, methodology): “, (i) generalization, and (ii) scalability to a large number of workers, we propose to leverage novel variants of local SGD (Mcdonald et al., 2009; Zinkevich et al., 2010a; Zhang et al., 2016).”
Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms (2018, methodology): “A natural idea is to allow workers to perform τ local updates to the model instead of just computing gradients, and then periodically averaging the local models (Moritz et al., 2015; Zhang et al., 2016; Povey et al., 2014; Su & Chen, 2015; Chaudhari et al., 2017).”
Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learning (2018, background): “As a remedy, (Zhang et al. 2016) suggests more frequent averaging should be used to improve the performance.”
Local SGD Converges Fast and Communicates Little (2018, methodology): “If T is unknown, then these observations seem to indicate that the technique from [46], i.”
On the convergence properties of a K-step averaging stochastic gradient descent algorithm for nonconvex optimization (2017, positive): “Zhang et al. [2016] expressed the same concern, their experimental results showed that periodic averaging tends to improve the solution quality.”
Adaptive Communication Strategies to Achieve the Best Error-Runtime Trade-off in Local-Update SGD (2018, background): “Periodic averaging has been shown to offer signiﬁcant speedup in deep neural network training (Moritz et al., 2015; Zhang et al., 2016; Su & Chen, 2015; Zhou & Cong, 2017; Lin et al., 2018).”
On the Convergence of Local Descent Methods in Federated Learning (2019, methodology): “[37] Jian Zhang, Christopher De Sa, Ioannis Mitliagkas, and Christopher Ré.”
Parallel Restarted SGD for Non-Convex Optimization with Faster Convergence and Less Communication (2018, background): “As a remedy, [15] suggests more frequent averaging should be used to improve the performance.”
Federated Learning with Compression: Unified Analysis and Sharp Guarantees (2020, background): “To significantly reduce the number of communication rounds, a practical solution is to trade-off local computation for less communication via periodic averaging [55, 69].”
Communication trade-offs for Local-SGD with large step size (2019, background): “Zhang et al. [21] empirically show that local-SGD performs well.”