Linearly convergent stochastic heavy ball method for minimizing generalization error
arXiv:1710.10737
Abstract
In this work we establish the first linear convergence result for the stochastic heavy ball method. The method performs SGD steps with a fixed stepsize, amended by a heavy ball momentum term. In the analysis, we focus on minimizing the expected loss and not on finite-sum minimization, which is typically a much harder problem. While in the analysis we constrain ourselves to quadratic loss, the overall objective is not necessarily strongly convex.
NIPS 2017, Workshop on Optimization for Machine Learning (camera ready version)
References in corpus (4)
Cited by in corpus (16)
- An Improved Analysis of Stochastic Gradient Descent with Momentum
- Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates
- Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances
- Taming Momentum in a Distributed Asynchronous Environment
- Distributed Second Order Methods with Fast Rates and Compressed Communication
- On Convergence of Distributed Approximate Newton Methods: Globalization, Sharper Bounds and Beyond
- On the fast convergence of minibatch heavy ball momentum
- Distributed heavy-ball: A generalization and acceleration of first-order methods with gradient tracking
- A Privacy Preserving Randomized Gossip Algorithm via Controlled Noise Insertion
- Non-ergodic Convergence Analysis of Heavy-Ball Algorithms
- AI-SARAH: Adaptive and Implicit Stochastic Recursive Gradient Methods
- Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip
- Heavy-ball Algorithms Always Escape Saddle Points
- SAGA with Arbitrary Sampling
- Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters
- Non-ergodic Complexity of Convex Proximal Inertial Gradient Descents