Quickly Finding a Benign Region via Heavy Ball Momentum in Non-Convex Optimization
arXiv:2010.01449
Abstract
The Heavy Ball Method, proposed by Polyak over five decades ago, is a first-order method for optimizing continuous functions. While its stochastic counterpart has proven extremely popular in training deep networks, there are almost no known functions where deterministic Heavy Ball is provably faster than the simple and classical gradient descent algorithm in non-convex optimization. The success of Heavy Ball has thus far eluded theoretical understanding. Our goal is to address this gap, and in the present work we identify two non-convex problems where we provably show that the Heavy Ball momentum helps the iterate to enter a benign region that contains a global optimal point faster. We show that Heavy Ball exhibits simple dynamics that clearly reveal the benefit of using a larger value of momentum parameter for the problems. The first of these optimization problems is the phase retrieval problem, which has useful applications in physical science. The second of these optimization problems is the cubic-regularized minimization, a critical subroutine required by Nesterov-Polyak cubic-regularized method to find second-order stationary points in general smooth non-convex problems.
References in corpus (28)
- Decoupled Weight Decay Regularization
- Train longer, generalize better: closing the generalization gap in large batch training of neural networks
- How to Escape Saddle Points Efficiently
- Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
- When Are Nonconvex Problems Not Scary?
- 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
- From Averaging to Acceleration, There is Only a Step-size
- Neon2: Finding Local Minima via First-Order Oracles
- Gradient Descent Can Take Exponential Time to Escape Saddle Points
- On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
- Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
- Understanding the Role of Momentum in Stochastic Gradient Methods
- Hamiltonian Descent Methods
- An Improved Analysis of Stochastic Gradient Descent with Momentum
- A Generic Approach for Escaping Saddle points
- Complex Dynamics in Simple Neural Networks: Understanding Gradient Flow in Phase Retrieval
- Sharp Analysis for Nonconvex SGD Escaping from Saddle Points
- Convolutional Phase Retrieval via Gradient Descent
- Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances
- Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrieval
- Robust Recovery via Implicit Bias of Discrepant Learning Rates for Double Over-parameterization
- Escaping Saddle Points Faster with Stochastic Momentum
- Stochastic Heavy Ball
- Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond
- Global Convergence of Second-order Dynamics in Two-layer Neural Networks
- The Effects of Mild Over-parameterization on the Optimization Landscape of Shallow ReLU Neural Networks