On the Insufficiency of Existing Momentum Schemes for Stochastic Optimization

By Rahul Kidambi, Praneeth Netrapalli, Prateek Jain, Sham M. Kakade. 2018

135 citations recorded by the source corpus.

Momentum based stochastic gradient methods such as heavy ball (HB) and Nesterov's accelerated gradient descent (NAG) method are widely used in practice for training deep networks and other supervised learning models, as they often provide significant improvements over stochastic gradient descent (SGD). In general, “fast gradient” methods have provable improvements over gradient descent only for the deterministic case, where the gradients are exact. In the stochastic case, the popular explanations for their wide applicability is that when these fast gradient methods are applied in the stochastic case, they partially mimic their exact gradient counterparts, resulting in some practical gain. This work provides a counterpoint to this belief by proving that there are simple problem instances where these methods cannot outperform SGD despite the best setting of its parameters. These negative problem instances are, in an informal sense, generic; they do not look like carefully constructed pathological instances. These results suggest (along with empirical evidence) that HB or NAG's practical performance gains are a by-product of minibatching. Furthermore, this work provides a viable (and provable) alternative, which, on the same set of problem instances, significantly improves over HB, NAG, and SGD's performance. This algorithm, denoted as ASGD, is a simple to implement stochastic algorithm, based on a relatively less popular version of Nesterov's AGD. Extensive empirical results in this paper show that ASGD has performance gains over HB, NAG, and SGD.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, 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 Computer Vision and Pattern Recognition

In Optimization & Training

Citations in the corpus

Measuring the Effects of Data Parallelism on Neural Network Training (2018, neutral): “Though initially surprising, this identical performance at small batch sizes is consistent with observations made in Kidambi et al. (2018).”
Which Algorithmic Choices Matter at Which Batch Sizes? Insights From a Noisy Quadratic Model (2019, background): “[2018], Kidambi et al. [2018], the performance of momentum-based optimizers matches that of the plain SGD methods in the small-batch regime, but momentum increases the critical batch size and gives substantial speedups in the large batch regime.”
On the Ineffectiveness of Variance Reduced Optimization for Deep Learning (2018, methodology): “This kind of step correlation is also seen in momentum methods, and is considered a contributing factor to their effectiveness [Kidambi et al., 2018].”
Closing the Generalization Gap of Adaptive Gradient Methods in Training Deep Neural Networks (2018, methodology): “Since our algorithm can also be seen as an interpolation between Amsgrad and SGD with momentum, we can borrow some idea from the convergence analysis of SGD with momentum (Kidambi et al., 2018) to facilitate the analysis in this direction.”
Quasi-hyperbolic momentum and Adam for deep learning (2018, methodology): “Jain et al. (2017) and Kidambi et al. (2018) point out various failures of momentum and NAG in the setting of stochastic least squares optimization.”
The Two Regimes of Deep Network Training (2020, background): “According to Kidambi et al. (2018), momentum might not be able to cope with the noise coming from the stochasticity of SGD.”
The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure (2019, background): “There are two predominant approaches in stochastic optimization: those methods which decay learning rate schedules to achieve the best performance (Krizhevsky et al., 2012; Sutskever et al., 2013; Kidambi et al., 2018) and those which rely on various forms of approximate preconditioning (Duchi et al”
Convergence Guarantees for RMSProp and ADAM in Non-Convex Optimization and an Empirical Comparison to Nesterov Acceleration (2018, background): “[19] Rahul Kidambi, Praneeth Netrapalli, Prateek Jain, and Sham M.”
Accelerating SGD with momentum for over-parameterized learning (2018, background): “[9] Rahul Kidambi, Praneeth Netrapalli, Prateek Jain, and Sham M Kakade.”
An Improved Analysis of Stochastic Gradient Descent with Momentum (2020, methodology): “In [15, 16] and [12], the behavior of SGDM on least square regression is analyzed and linear convergence is established.”
MaSS: an Accelerated Stochastic Method for Over-parametrized Learning (2018, methodology): “This proof follows the idea of the proof for stochastic Heavy Ball method in [7].”
Stochastic Gradient Descent with Polyak’s Learning Rate (2019, background): “When SGD is combined with momentum [Pol64, Nes13] empirical performance is improved, but there is still no theoretical justiﬁcation for the improvement [KNJK18].”
On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settings (2020, methodology): “The lack of general convergence guarantees for existing momentum schemes, such as Polyak’s and Nesterov’s, have led many authors to develop alternative accelerated methods specifically for use with stochastic gradients (Lan, 2012; Ghadimi & Lan, 2012; 2013; Allen-Zhu, 2017; Kidambi et al., 2018; Coh”
Accelerating Stochastic Training for Over-parametrized Learning (2018, methodology): “This proof follows the idea of the proof for stochastic Heavy Ball method in (Kidambi et al., 2018).”
NAMSG: An Efficient Method For Training Neural Networks (2019, methodology): “3 EQUIVALENCE OF CNAG AND ASGD The pseudo code of ASGD (Kidambi et al., 2018; Jain et al., 2018) is shown in Algorithm A1.”
Aggregated Momentum: Stability Through Passive Damping (2018, methodology): “The convergence of momentum methods has been studied extensively, both theoretically and empirically (Wibisono & Wilson, 2015; Wibisono et al., 2016; Wilson et al., 2016; Kidambi et al., 2018).”
Understanding the Role of Momentum in Stochastic Gradient Methods (2019, background): “In addition, Ma and Yarats [18] show that diﬀerent settings of α k , β k and ν k recover other variants such as AccSGD [12], Robust Momentum [3], and Triple Momentum [36].”
On the Generalization Benefit of Noise in Stochastic Gradient Descent (2020, unknown): “Some authors argue that SGD with Momentum significantly outperforms vanilla SGD (Sutskever et al., 2013), while others claim that SGD with and without Momentum are equivalent if one maintains a constant “effective learning rate” (Mandt et al., 2017; Kidambi et al., 2018; Liu & Belkin, 2018a).”
An Adaptive Remote Stochastic Gradient Method for Training Neural Networks (2019, background): “They further present ASGD [13, 14] and show improvement on SGD in any information-theoretically admissible regime.”