Stochastic Heavy ball

By Sébastien Gadat, Fabien Panloup, Sofiane Saadane. 2016

117 citations recorded by the source corpus.

This paper deals with a natural stochastic optimization procedure derived from the so-called Heavy-ball method differential equation, which was introduced by Polyak in the 1960s with his seminal contribution [Pol64]. The Heavy-ball method is a second-order dynamics that was investigated to minimize convex functions f. The family of second-order methods recently received a large amount of attention, until the famous contribution of Nesterov [Nes83], leading to the explosion of large-scale optimization problems. This work provides an in-depth description of the stochastic heavy-ball method, which is an adaptation of the deterministic one when only unbiased evalutions of the gradient are available and used throughout the iterations of the algorithm. We first describe some almost sure convergence results in the case of general non-convex coercive functions f. We then examine the situation of convex and strongly convex potentials and derive some non-asymptotic results about the stochastic heavy-ball method. We end our study with limit theorems on several rescaled algorithms.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/451f8b812639fa18d6c8f89d8acef2074a26e237

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. Soham De
4. Sepp Hochreiter
5. Thomas Unterthiner
6. Jakub Konecný
7. Martin Takác
8. Lin Xiao

In Computational Mechanics

1. Nicolas Loizou
2. Peter Richtárik
3. Lin Xiao
4. Martin Takác
5. Mert Gurbuzbalaban
6. Soham De
7. Jakub Konecný
8. Lingjiong Zhu

In Numerical Analysis

1. Nicolas Loizou
2. Hubert Ramsauer
3. Martin Heusel
4. Thomas Unterthiner
5. Sepp Hochreiter
6. Bernhard Nessler
7. Mert Gurbuzbalaban
8. Lingjiong Zhu

Citations in the corpus

• Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances (2019, methodology): “This method is called the stochastic HB method (Gadat et al., 2018; Loizou & Richtárik, 2018; Flåm, 2004).”
• On the rates of convergence of parallelized averaged stochastic gradient algorithms (2017, background): “c normality (see Theorem3.2). 5 Investigating the case a = 1 is a tricky question discussed before, and not necessary since optimality is already obtained. However, we point out the work of ([2] and [10]) where the specificity of this case is discussed with accurate computations. Remark that the rema”
• Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, background): “2016 [206] sublinear F(1,1) 0,L + bounded variance global, non-asymptotic Gadat et al, 2016 [60] sublinear F(1,1) μ,L + other assumptions global, non-asymptotic THIS CHAPTER see Table 2.”
• Optimal non-asymptotic bound of the Ruppert-Polyak averaging without strong convexity (2017, background): “This phenomenon also occurs for the kinetic diffusion dynamics [27, 15]) and for the Nesterov accelerated gradient descent [22] and the Heavy Ball system [8, 16] even though we do not claim that such a clear common point exists between these methods.”
• Understanding the Role of Momentum in Stochastic Gradient Methods (2019, background): “[7] extended asymptotic convergence analysis for the normalized SHB update to smooth nonconvex functions for βk → 1.”
• Linearly convergent stochastic heavy ball method for minimizing generalization error (2017, background): “In [3], a complexity analysis is provided for the case of quadratic strongly convex smooth coercive functions.”
• GANs Trained by a Two Time-Scale Update Rule Converge to a Nash Equilibrium (2017, methodology): “(6) converge for loss functions f with at most quadratic grow and stated that convergence can be proofed for ∇f that are L-Lipschitz [16].”
• Convergence Guarantees for RMSProp and ADAM in Non-Convex Optimization and an Empirical Comparison to Nesterov Acceleration (2018, background): “…there is no clear theoretical justification in the stochastic case of the benefits 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…”
• GANs Trained by a Two Time-Scale Update Rule Converge to a Local Nash Equilibrium (2017, methodology): “Gadat et al. derived a discrete and stochastic version of Polyak’s Heavy Ball method [40], the Heavy Ball with Friction (HBF) [15]: These update rules are the first moment update rules of Adam [27].”