Source-linked AI summary
Global convergence of the Heavy-ball method for convex optimization
Euhanna Ghadimi, Hamid Reza Feyzmahdavian, Mikael Johansson
TL;DR
The paper addresses incomplete global convergence results for Heavy-ball on convex objectives that may lack twice continuous differentiability. It develops a global convergence analysis and proves O(1/k) convergence for Cesaro averages in the smooth convex case and linear convergence to the unique optimum under strong convexity.
Problem
Global convergence rates for Heavy-ball on convex objectives with Lipschitz-continuous gradients, without twice differentiability, were not well established.
Method
The paper provides a global convergence analysis of Heavy-ball with parameters chosen within specified ranges, including constant and time-varying step-sizes.
Results
The Cesaro averages converge to the optimum at O(1/k) for smooth convex objectives, while Heavy-ball iterates converge linearly to the unique optimum under strong convexity.
Takeaways & Limitations
Heavy-ball has global stability guarantees for two important classes of convex optimization problems.
Takeaways & Limitations
The authors leave constrained extensions and sharper guaranteed convergence-factor bounds for strongly convex objectives to future work.
Abstract
from arXiv · showhide
This paper establishes global convergence and provides global bounds of the convergence rate of the Heavy-ball method for convex optimization problems. When the objective function has Lipschitz-continuous gradient, we show that the Cesaro 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.
1 Introduction
First-order methods offer low per-iteration cost and strong convergence guarantees, but basic questions about achievable rates remain open. This paper analyzes whether Heavy-ball methods provide global guarantees for broadly defined convex objectives.
- First-order methods are attractive in large-scale and distributed settings because each iteration has a small cost.
- Basic questions about the achievable convergence speed of first-order convex optimization methods remain open.
- Gradient descent converges at O(1/k) for smooth convex objectives and linearly when the objective is strongly convex.
- Heavy-ball has stronger local results for twice continuously differentiable strongly convex objectives, using previous iterates while evaluating only the current gradient.
- For convex objectives that are not twice continuously differentiable, Heavy-ball convergence rates and performance relative to Nesterov and gradient descent were unclear.
- The paper provides global Heavy-ball convergence analysis with Lipschitz-continuous gradients, covering both merely convex and strongly convex objectives.
2 Background
The paper studies unconstrained convex optimization with continuously differentiable objectives and Lipschitz-continuous gradients, including strongly convex subclasses. It situates Heavy-ball among gradient and Nesterov methods and their convergence guarantees.
- The analyzed objectives are continuously differentiable convex functions, with convergence bounds developed for specified function classes.
- The class F^1,1_L consists of convex continuously differentiable functions whose gradients are Lipschitz continuous with constant L.
- The class S^1,1_{µ,L} adds strong convexity with modulus µ > 0 to the F^1,1_L conditions.
- Gradient descent is the baseline first-order method, using a positive step-size parameter α.
- For smooth convex objectives, gradient-descent objective error converges at O(1/k), while strong convexity yields linear convergence.
- Heavy-ball is a multi-step extension of gradient descent whose next iterate depends on preceding iterates.
- Polyak’s local Heavy-ball analysis gives a better convergence factor than gradient and Nesterov methods for twice continuously differentiable strongly convex functions.
3 Global analysis of Heavy-ball algorithm for the class F 1,1
The analysis establishes global convergence guarantees for Heavy-ball on convex, smooth objectives, including O(1/k) convergence for averages and individual iterates under time-varying step-sizes.
- Global convergence analysis: The Heavy-ball iterates are analyzed for convex objectives with Lipschitz-continuous gradients, using an energy-based proof over the method's iterates.The analysis introduces transformed iterates and inequalities involving convexity and smoothness.
- Global convergence analysis: The Cesàro average of Heavy-ball iterates converges to the optimum at rate O(1/k).The bound applies under suitable parameter ranges and uses the initial objective gap and distance to the optimum.
- Global convergence analysis: A similar O(1/k) rate holds for the minimum function value among the first T Heavy-ball iterates.The reported bound is f(xT)−f⋆ ≤ 1/[2ᾱ(T+1)] times the squared initial distance, for all T ∈ N0.
- Global convergence analysis: For fixed ᾱ ∈ (0,1/L], the optimal momentum parameter minimizes the Heavy-ball convergence factor, which is smaller than gradient descent's factor.At ᾱ = 1/L, the factors coincide with the best reported gradient-descent convergence factor.
- Time-varying step-sizes: With time-varying step-sizes βk = k/(k+2) and αk = α0/(k+2), individual Heavy-ball iterates converge at rate O(1/k).The step-size parameter satisfies α0 ∈ (0,1/L].
- Numerical illustration: A numerical example on a 50-dimensional Moreau proximal envelope suggests that O(1/k) accurately describes Heavy-ball and gradient-method objective progress.The example uses L = 1, β = 0.5 and α = 1/L for constant-step Heavy-ball, and α0 = 1/L for its time-varying variant.
- Comparison with related methods: The paper contrasts its Heavy-ball analysis with Nesterov-type methods that also achieve O(1/k) average convergence but require two gradient computations per iteration.The cited comparison states that the Heavy-ball iteration requires one gradient computation per iteration.
4 Global analysis of Heavy-ball algorithm for the class S 1,1
The paper establishes global linear convergence of Heavy-ball iterates for strongly convex objectives with Lipschitz-continuous gradients under new stability criteria. These criteria also cover examples where earlier criteria fail and permit broader parameter ranges.
- The analysis derives global stability criteria using a sequence-convergence lemma applied to function-value and iterate-distance terms.
- The Heavy-ball method converges linearly to a unique optimizer under the section’s global stability conditions.
- The new criteria allow wider parameter ranges than earlier conditions; as α approaches 2/L, β may reach µ/L instead of tending to zero.
- For a strongly convex, continuously differentiable counterexample, parameters satisfying the earlier criteria produce nonconvergent iterates, whereas the new criteria ensure convergence.
- The estimated convergence factor is q = 1−αµ, matching the best known gradient-method factor for this function class.
5 CONCLUSIONS
The paper establishes global stability for Heavy-ball on convex problems with Lipschitz-continuous gradients, obtaining O(1/k) convergence for Cesàro averages and linear convergence under strong convexity. Future work targets constrained problems and sharper convergence-factor bounds.
- For convex objectives with Lipschitz-continuous gradients, Cesàro averages of Heavy-ball iterates converge to the optimum at rate O(1/k).
- For strongly convex objectives, Heavy-ball iterates converge linearly to the unique optimum.
- Future work will extend the results to constrained optimization and derive sharper guaranteed convergence-factor bounds for S 1,1 µ,L.