Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods

By Nicolas Loizou, Peter Richtárik. 2017

236 citations recorded by the source corpus.

In this paper we study several classes of stochastic optimization algorithms enriched with heavy ball momentum. Among the methods studied are: stochastic gradient descent, stochastic Newton, stochastic proximal point and stochastic dual subspace ascent. This is the first time momentum variants of several of these methods are studied. We choose to perform our analysis in a setting in which all of the above methods are equivalent: convex quadratic problems. We prove global non-asymptotic linear convergence rates for all methods and various measures of success, including primal function values, primal iterates, and dual function values. We also show that the primal iterates converge at an accelerated linear rate in a somewhat weaker sense. This is the first time a linear rate is shown for the stochastic heavy ball method (i.e., stochastic gradient descent method with momentum). Under somewhat weaker conditions, we establish a sublinear convergence rate for Cesàro averages of primal iterates. Moreover, we propose a novel concept, which we call stochastic momentum, aimed at decreasing the cost of performing the momentum step. We prove linear convergence of several stochastic methods with stochastic momentum, and show that in some sparse data regimes and for sufficiently small momentum parameters, these methods enjoy better overall complexity than methods with deterministic momentum. Finally, we perform extensive numerical testing on artificial and real datasets, including data coming from average consensus problems.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research, 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 Computational Mechanics

In Management Science and Operations Research

In Optimization & Training

Citations in the corpus

Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, methodology): “The Consensus Optimization (CO) Algorithm is a computationally-light6 second order methods which has been introduced in Mescheder et al. [2017] and it was shown to be an effective method for training GANs in a variety of settings.”
Stochastic Hamiltonian Gradient Methods for Smooth Games (2020, methodology): “A natural extension of our results will be the proposal of accelerated Hamiltonian methods that use momentum (Loizou & Richt´arik, 2017; Assran & Rabbat, 2020) on top of the Hamiltonian gradient update.”
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].”
SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum (2019, background): “Loizou & Richtárik (2017) show that accelerated convergence rates can be achieved when the objective is a quadratic finite sum (i.e., least squares problem) that satisfies an interpolation condition.”
Hyper-Parameter Optimization: A Review of Algorithms and Applications (2020, methodology): “An improved method for solving the problem of oscillation and convergence speed is SGD with momentum (Loizou and Richtárik, 2017).”
New Insights and Perspectives on the Natural Gradient Method (2014, background): “This can happen if the model can obtain zero error on all cases in the training distribution (e.g Loizou and Richtárik, 2017), a situation which is ruled out by the hypothesis that this distribution has a density function (as is required by Cramér-Rao).”
On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settings (2020, background): “Loizou & Richt´arik (2017) study Polyak’s heavy-ball momentum method with stochastic gradients for quadratic problems and show that it converges linearly under an exactness assumption.”
Nonconvex Variance Reduced Optimization with Arbitrary Sampling (2018, background): “In recent years, tremendous effort was exerted to improve its performance, leading to various enhancements which use acceleration (Allen-Zhu, 2016), momentum (Loizou and Richtárik, 2017), minibatching (Takáč et al.”
Convergence Guarantees for RMSProp and ADAM in Non-Convex Optimization and an Empirical Comparison to Nesterov Acceleration (2018, background): “…stochastic case of the beneﬁts of NAG and HB over regular SGD in general [46, 19, 42, 32, 45, 12], unless considering specialized function classes [25]; in practice, these momentum methods, and in particular NAG, have been repeatedly shown to have good convergence and generalization on a range of…”
Linear Lower Bounds and Conditioning of Differentiable Games (2019, background): “n = 1), while linear rates are not achievable for general stochastic problems, for which the worst-case bounds are sublinear, under certain conditions linear rates are possible (Loizou and Richtárik, 2017).”
Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory (2017, methodology): “oblem in the signal processing literature. They show that our methods lead to state-of-the-art average consensus methods. Further extensions. Our results were also extended to include Polyak momentum [36], allow for inexact stochastic gradient computation [37], led to the development of the ﬁrst coo”
Stochastic quasi-gradient methods: variance reduction via Jacobian sketching (2018, methodology): “A sketch and project method with the heavy ball momentum was studied in [20].”
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, background): “Recently, accelerated and parallel stochastic optimization methods [115, 168, 192] have been proposed for solving linear systems.”
Convergence Analysis of Inexact Randomized Iterative Methods (2019, methodology): “It can be proved, [19, 29], that the iterates {xk}k≥0 of the sketch and project method (8) arise as affine images of the iterates {yk}k≥0 of the dual method (11) as follows: xk = x(yk) = x0 + B Ayk.”