Global convergence of the Heavy-ball method for convex optimization

By Euhanna Ghadimi, Hamid Reza Feyzmahdavian, Mikael Johansson. 2014

337 citations recorded by the source corpus.

This paper establishes global convergence and provides global bounds of the rate of convergence for the Heavy-ball method for convex optimization. When the objective function has Lipschitz-continuous gradient, we show that the Cesáro average of the iterates converges to the optimum at a rate of O(1/k) where k is the number of iterations. When the objective function is also strongly convex, we prove that the Heavy-ball iterates converge linearly to the unique optimum. Numerical examples validate our theoretical findings.

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

In Optimization & Training

Citations in the corpus

Negative Momentum for Improved Game Dynamics (2018, background): “Ghadimi et al. (2015) analyze momentum and provide global convergence properties for functions with Lipschitz-continuous gradients.”
On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization (2019, methodology): “A similar auxiliary sequence {z̄(t)}t≥0 has been used for the convergence analysis of standard momentum methods (single node without restarting) in (Ghadimi et al., 2014) and (Yan et al., 2018).”
Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods (2017, methodology): “Our proof strategy is similar to [24] in which the first global convergence analysis of the (deterministic) heavy ball method was presented.”
Distributed stochastic optimization for deep learning (thesis) (2016, neutral): “The analysis of its global convergence property is still a very challenging problem in convex optimization literature [21].”
Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimization (2016, methodology): “Although the convergence analysis of HB has been recently extended to smooth functions for both convex (Ghadimi et al., 2014; Ochs et al., 2015) and non-convex optimization (Ochs et al., 2014), it is still under-explored for stochastic optimization, specially stochastic non-convex optimization.”
Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances (2019, positive): “There exist non-asymptotic linear convergence results for HB, but to our knowledge, known linear rate guarantees are slower than the accelerated rate ρHB ; with a rate similar to the rate of gradient descent (Ghadimi et al., 2014).”
On the Convergence of Weighted AdaGrad with Momentum for Training Deep Neural Networks (2018, background): “…Momentum acceleration mechanisms, including H eavy B all (HB) momentum [34] and N esterov A ccelerated G radient (NAG) momentum [32], have been theoretically and numerically investigated for both convex and non-convex optimization problems [32, 33, 12, 6] for constant global learning rate.”
On the Convergence Rate of Incremental Aggregated Gradient Algorithms (2015, background): “There has also been much interest in understanding its global convergence properties [9,11].”
An Improved Analysis of Stochastic Gradient Descent with Momentum (2020, methodology): “This auxiliary sequence first appeared in the analysis of deterministic heavy ball methods in [7], and later applied in the analysis of SGDM [26, 25].”
On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization (2018, methodology): “stimate. Recent works have proposed a variety of accelerated versions of GD and SGD (Nesterov, 2013). These achievements fall into three categories: a) momentum methods (Nesterov, 1983; Polyak, 1964; Ghadimi et al., 2015) which carefully design the descent direction t; b) adaptive learning rate meth”
A Unified Analysis of Stochastic Momentum Methods for Deep Learning (2018, methodology): “The convergence of HB and NAG has been established for convex optimization [Polyak, 1964; Nesterov, 1983; Nesterov, 2004; Ghadimi et al., 2014; Ochs et al., 2015].”
Bayesian Coresets: Revisiting the Nonconvex Optimization Perspective (2021, methodology): “Acceleration using momentum term (Beck & Teboulle, 2009; Ghadimi et al., 2015) allows for faster convergence of ﬁrst order methods without increasing the per iteration cost.”
Accelerating Federated Learning via Momentum Gradient Descent (2019, background): “Thus, by introducing the last iteration, which is named momentum term, momentum gradient descent (MGD) can accelerate the convergence [24] [25].”