Linearly convergent stochastic heavy ball method for minimizing generalization error

By Nicolas Loizou, Peter Richtárik. 2017

47 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, 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

1. Nicolas Loizou
2. Peter Richtárik
3. Simon Lacoste-Julien
4. Sham M. Kakade
5. Issam Hadj Laradji
6. Gauthier Gidel
7. Praneeth Netrapalli
8. Prateek Jain

In Computational Mechanics

1. Nicolas Loizou
2. Peter Richtárik
3. Simon Lacoste-Julien
4. Gauthier Gidel
5. Prateek Jain
6. Sham M. Kakade
7. Issam Hadj Laradji
8. Praneeth Netrapalli

In Computer Vision and Pattern Recognition

1. Nicolas Loizou
2. Peter Richtárik
3. Prateek Jain
4. Simon Lacoste-Julien
5. Gauthier Gidel
6. Praneeth Netrapalli
7. Mark W. Schmidt
8. Issam Hadj Laradji

In Optimization & Training

1. Nicolas Loizou
2. Simon Lacoste-Julien
3. Peter Richtárik
4. Issam Hadj Laradji
5. Gauthier Gidel
6. Sharan Vaswani
7. Sham M. Kakade
8. Praneeth Netrapalli

Citations in the corpus

• Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates (2019, methodology): “This update rule has been used with a constant step-size and proven to obtain linear convergence rates on the generalization error for quadratic functions under an interpolation condition [48, 49].”
• Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods (2017, background): “This result sparked renewed interest in design of randomized methods for solving linear systems [19,49,51,53,55,57,58,81,97].”
• Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, methodology): “This result sparked renewed interest in design of randomized methods for solving linear systems [132, 134, 49, 120, 216, 135, 175, 114].”
• Convergence Analysis of Inexact Randomized Iterative Methods (2019, methodology): “For more papers related to Kaczmarz method (randomized, greedy, cyclic update rules) we refer the interested reader to [23, 28, 38, 5, 37, 39, 9, 33, 34, 13, 31, 59, 35, 50].”
• An Improved Analysis of Stochastic Gradient Descent with Momentum (2020, unknown): “In [15, 16] and [12], the behavior of SGDM on least square regression is analyzed and linear convergence is established.”
• Revisiting Randomized Gossip Algorithms: General Framework, Convergence Rates and Novel Block and Accelerated Protocols (2019, methodology): “[47, 48] were the first works that prove linear convergence of SHB in any setting.”
• On the Insufficiency of Existing Momentum Schemes for Stochastic Optimization (2018, methodology): “Loizou and Richtárik (2017) state their method as Stochastic HB but require stochastic gradients that nearly behave as exact gradients; indeed, their rates match that of the standard HB method (Polyak, 1964).”
• Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances (2019, background): “[LR17] Nicolas Loizou and Peter Richtárik.”