Escaping Saddle Points Faster with Stochastic Momentum

Abstract

Stochastic gradient descent (SGD) with stochastic momentum is popular in nonconvex stochastic optimization and particularly for the training of deep neural networks. In standard SGD, parameters are updated by improving along the path of the gradient at the current iterate on a batch of examples, where the addition of a ``momentum'' term biases the update in the direction of the previous change in parameters. In non-stochastic convex optimization one can show that a momentum adjustment provably reduces convergence time in many settings, yet such results have been elusive in the stochastic and non-convex settings. At the same time, a widely-observed empirical phenomenon is that in training deep networks stochastic momentum appears to significantly improve convergence time, variants of it have flourished in the development of other popular update methods, e.g. ADAM [KB15], AMSGrad [RKK18], etc. Yet theoretical justification for the use of stochastic momentum has remained a significant open question. In this paper we propose an answer: stochastic momentum improves deep network training because it modifies SGD to escape saddle points faster and, consequently, to more quickly find a second order stationary point. Our theoretical results also shed light on the related question of how to choose the ideal momentum parameter--our analysis suggests that $\beta \in [0,1)$ should be large (close to 1), which comports with empirical findings. We also provide experimental findings that further validate these conclusions.

arXiv commentAccepted at ICLR 2020

References in corpus (18)

• Decoupled Weight Decay Regularization
• Deep Speech 2: End-to-End Speech Recognition in English and Mandarin
• On the Convergence of Adam and Beyond
• The Loss Surfaces of Multilayer Networks
• AutoAugment: Learning Augmentation Policies from Data
• The Marginal Value of Adaptive Gradient Methods in Machine Learning
• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
• Train longer, generalize better: closing the generalization gap in large batch training of neural networks
• How to Escape Saddle Points Efficiently
• Non-convex Finite-Sum Optimization Via SCSG Methods
• Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimization
• Escaping Saddles with Stochastic Gradients
• The Power of Normalization: Faster Evasion of Saddle Points
• Neon2: Finding Local Minima via First-Order Oracles
• Gradient Descent Can Take Exponential Time to Escape Saddle Points
• Escaping Saddle Points in Constrained Optimization
• Sharp Analysis for Nonconvex SGD Escaping from Saddle Points
• Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances

Cited by in corpus (3)

• Quickly Finding a Benign Region via Heavy Ball Momentum in Non-Convex Optimization
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network