Asynchrony begets momentum, with an application to deep learning

By Ioannis Mitliagkas, Ce Zhang, Stefan Hadjis, Christopher R'e. 2016

155 citations recorded by the source corpus.

Asynchronous methods are widely used in deep learning, but have limited theoretical justification when applied to non-convex problems. We show that running stochastic gradient descent (SGD) in an asynchronous manner can be viewed as adding a momentum-like term to the SGD iteration. Our result does not assume convexity of the objective function, so it is applicable to deep learning systems. We observe that a standard queuing model of asynchrony results in a form of momentum that is commonly used by deep learning practitioners. This forges a link between queuing theory and asynchrony in deep learning systems, which could be useful for systems builders. For convolutional neural networks, we experimentally validate that the degree of asynchrony directly correlates with the momentum, confirming our main result. An important implication is that tuning the momentum parameter is important when considering different levels of asynchrony. Furthermore, our theory suggests ways of counter-acting the adverse effects of asynchrony. We see that a simple mechanism like using negative algorithmic momentum can be beneficial under high asynchrony. Since asynchronous methods have better hardware efficiency, this result may shed light on when asynchronous execution is more efficient for deep learning systems.

Subfields: 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 Optimization & Training

Citations in the corpus

Negative Momentum for Improved Game Dynamics (2018, background): “Mitliagkas et al. (2016) considered negative momentum in the context of asynchronous single-objective minimization.”
Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms (2018, background): “Synchronization delays can be alleviated via asynchronous gradient aggregation (Recht et al., 2011; Cui et al., 2014; Gupta et al., 2016; Mitliagkas et al., 2016; Dutta et al., 2018).”
Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD (2018, neutral): “• [Mitliagkas et al., 2016] assumes that Xi’s are exponentially distributed.”
Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training (2017, methodology): “Mitliagkas et al. (2016) discussed the staleness caused by asynchrony and attributed it to a term described as implicit momentum .”
Large scale distributed neural network training through online distillation (2018, background): “All of our experiments on ImageNet followed the setup of Goyal et al. (2017) as closely as possible and also used fully-synchronous SGD.”
Adaptive Communication Strategies to Achieve the Best Error-Runtime Trade-off in Local-Update SGD (2018, methodology): “A popular distributed SGD implementation is the parameter server framework [7, 4, 14, 10, 18] where in each iteration, worker nodes compute gradients on one mini-batch of data and a central parameter server aggregates these gradients (synchronously or asynchronously) and updates the parameter vector”
YellowFin and the Art of Momentum Tuning (2017, background): “It uses a novel component for measuring the total momentum in a running system, including any asynchrony-induced momentum, a phenomenon described in (Mitliagkas et al., 2016).”
PipeMare: Asynchronous Pipeline Parallel DNN Training (2019, methodology): “-style gradient delay τ i , we sample from truncated exponential distributions following the existing study in asynchronous training (Mitliagkas et al., 2016); this truncated exponential distribution is the maximum entropy distribution.”
Asynchronous Stochastic Gradient Descent with Delay Compensation (2016, background): “Researchers have tried to improve ASGD from different perspectives (Ho et al., 2013; McMahan & Streeter, 2014; Zhang et al., 2015; Sra et al., 2015; Mitliagkas et al., 2016), however, to the best of our knowledge, there is still no solution that can compensate the delayed gradient while keeping the ”
Analysis of DAWNBench, a Time-to-Accuracy Machine Learning Performance Benchmark (2018, background): “Asynchronous SGD can remove this synchronization at the cost of data efﬁciency [42,49].”
ImageNet Training in Minutes (2017, background): “A variety of asynchronous approaches have been proposed [19, 24, 27, 34].”
The Reactor: A fast and sample-efficient Actor-Critic agent for Reinforcement Learning (2017, methodology): “ a function of training time in hours. Rainbow learning curve provided by Hessel et al. (2017). with a learning rate of 5 10 5 and zero momentum because asynchronous updates induce implicit momentum (Mitliagkas et al., 2016). Further discussion of hyperparameters and their optimization can be found ”
On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settings (2020, background): “Previous work has found negative momentum to be useful in asynchronous distributed optimization Mitliagkas et al. (2016) and for stabilizing adversarial training Gidel et al. (2018).”
Toward Understanding the Impact of Staleness in Distributed Machine Learning (2018, background): “(2012) and has minimal impact on convergence (Mitliagkas et al., 2016; Hadjis et al., 2016; Lian et al., 2015).”
Gradient Coding: Avoiding Stragglers in Distributed Learning (2017, background): “Recognizing that, some recent work has advocated asynchronous approaches (Li et al., 2014; Ho et al., 2013; Mitliagkas et al., 2016) to learning.”
Fast Deep Neural Network Training on Distributed Systems and Cloud TPUs (2019, background): “A variety of asynchronous approaches have been proposed [8], [9], [10], [11].”
100-epoch ImageNet Training with AlexNet in 24 Minutes (2017, background): “A variety of asynchronous approaches have been proposed (Recht et al. 2011) (Zhang, Choromanska, and LeCun 2015a) (Jin et al. 2016) (Mitliagkas et al. 2016).”
The Convergence of Stochastic Gradient Descent in Asynchronous Shared Memory (2018, background): “An alternative approach, which we did not consider here, would be to introduce a “momentum” term by which the current model value is multiplied [20].”
DAWNBench : An End-to-End Deep Learning Benchmark and Competition (2017, background): “These approaches also interact in nontrivial ways and may require updating the underlying optimization algorithm [15, 26, 29], further affecting performance.”