An accelerated lyapunov function for Polyak's Heavy-ball on convex quadratics

Antonio OrvietoOptim. Lett 2025 · OpenReview

Abstract

In 1964, Polyak showed that the Heavy-ball method, the simplest momentum technique, accelerates convergence of strongly-convex problems in the vicinity of the solution. While Nesterov later developed a globally accelerated version, Polyak’s original algorithm remains simpler and more widely used in applications such as deep learning. Despite this popularity, the question of whether Heavy-ball is also globally accelerated or not has not been fully answered yet, and no convincing counterexample has been provided. This is largely due to the difficulty in finding an effective Lyapunov function: indeed, most proofs of Heavy-ball acceleration in the strongly-convex quadratic setting rely on eigenvalue arguments. Our work adopts a different approach: studying momentum through the lens of quadratic invariants of simple harmonic oscillators. By utilizing the modified Hamiltonian of Störmer-Verlet integrators, we are able to construct a Lyapunov function that demonstrates an $O(1/k^2)$ rate for Heavy-ball in the case of convex quadratic problems. Our novel proof technique, though restricted to linear regression, is found to work well empirically also on non-quadratic convex problems, and thus provides insights on the structure of Lyapunov functions to be used in the general convex case.

Introduction: The 60-Year Enigma of Momentum

In the world of optimization, "momentum" is the essential mechanism that allows algorithms to navigate complex loss landscapes efficiently. There are two primary paradigms:

  1. Polyak’s Heavy-ball (HB): Introduced in 1964, this is the original momentum method. It is computationally simple—adding a fraction of the previous step to the current gradient descent update—and remains the industry standard in deep learning frameworks.
  2. Nesterov’s Accelerated Gradient Descent (AGD): A 1982 refinement that evaluates the gradient at a "look-ahead" position.

While AGD has a rigorous proof of global acceleration (converging at a rate of $1/k^2$), the Heavy-ball method has remained a theoretical mystery. We know it works locally and performs exceptionally well in practice, but proving it achieves the same $1/k^2$ rate globally for all convex functions has been an open challenge for decades. This difficulty stems from the fact that the mathematical tools used to prove AGD do not naturally fit the simpler structure of Polyak's Heavy-ball.

Methods: Bridging Optimization and Physics

To bridge this gap, this research takes a detour through classical mechanics. Optimization algorithms can be modeled as physical systems—specifically, a ball rolling down a potential well with friction. The paper identifies that the Heavy-ball method is essentially a Störmer-Verlet integrator, a mathematical tool used in physics to simulate harmonic oscillators, such as pendulums or planetary orbits.

The Novel Lyapunov Function

Proving algorithm convergence typically requires a Lyapunov function—a mathematical "energy" function that must decrease monotonically as the algorithm progresses.

  • The Standard Approach: Researchers usually combine the objective function value with a kinetic energy term. However, in discrete-time systems, this energy often oscillates, making a formal proof of convergence impossible.
  • The Innovation: By deriving a "modified Hamiltonian," the author introduces a specific cross-term. This mathematical correction accounts for the "jitter" or discretization error of taking finite steps. This results in a Lyapunov function that is guaranteed to be non-increasing.

This approach allows for the first Lyapunov-based proof of an $O(1/k^2)$ convergence rate for a generalized version of the Heavy-ball method ($HB_r$) on quadratic functions.

Key Results

The theoretical framework was validated using both synthetic quadratic problems and real-world benchmarks from the LIBSVM library (Wine and Breast Cancer datasets).

Theoretical and Empirical Convergence

The paper formally proves that for convex quadratics, the Heavy-ball method achieves the optimal $O(1/k^2)$ rate, provided the step size $h^2$ is less than $4/L$ (where $L$ is the smoothness constant). As shown in the empirical results, the Heavy-ball method matches the performance of Nesterov’s AGD on difficult, ill-conditioned quadratic problems.

Convergence of Heavy-ball (HB) vs. Nesterov's AGD on a linear regression problem, demonstrating the $O(k^{-2})$ rate.

Furthermore, when compared against the theoretical lower bounds established in Nesterov’s literature, the Heavy-ball method tracks the accelerated rate closely, confirming its efficiency.

Performance of optimization methods compared against the theoretical lower bound from Nesterov's literature.

Generalization Beyond Quadratics

Even on non-quadratic problems like logistic regression, the proposed Lyapunov function remains empirically effective. This suggests that the "shifted gradient" used in Nesterov's AGD might be a mathematical convenience for easier proofs rather than a strict requirement for acceleration.

Limitations and Future Work

While this work marks a significant milestone, some limitations remain:

  • Quadratic Restriction: The formal proof is currently limited to quadratic functions (e.g., linear regression).
  • Damping Requirements: On non-quadratic problems, the algorithm requires higher damping parameters to maintain the stability of the Lyapunov function.

The ultimate goal is to extend this "modified Hamiltonian" approach to provide a universal proof for Polyak’s momentum on all $C^2$ convex functions, finally resolving one of the longest-standing questions in optimization theory.

Summary updated

Abstract

In 1964, Polyak showed that the Heavy-ball method, the simplest momentum technique, accelerates convergence of strongly-convex problems in the vicinity of the solution. While Nesterov later developed a globally accelerated version, Polyak’s original algorithm remains simpler and more widely used in applications such as deep learning. Despite this popularity, the question of whether Heavy-ball is also globally accelerated or not has not been fully answered yet, and no convincing counterexample has been provided. This is largely due to the difficulty in finding an effective Lyapunov function: indeed, most proofs of Heavy-ball acceleration in the strongly-convex quadratic setting rely on eigenvalue arguments. Our work adopts a different approach: studying momentum through the lens of quadratic invariants of simple harmonic oscillators. By utilizing the modified Hamiltonian of Störmer-Verlet integrators, we are able to construct a Lyapunov function that demonstrates an \(O(1/k^2)\) rate for Heavy-ball in the case of convex quadratic problems. Our novel proof technique, though restricted to linear regression, is found to work well empirically also on non-quadratic convex problems, and thus provides insights on the structure of Lyapunov functions to be used in the general convex case. As such, our paper makes a promising first step towards potentially proving the acceleration of Polyak’s momentum method and we hope it inspires further research around this question.
BibTeX
@inproceedings{orvieto2025accelerated,
  author = {Antonio Orvieto},
  title = {{An accelerated lyapunov function for Polyak's Heavy-ball on convex quadratics}},
  booktitle = {Optim. Lett},
  year = {2025},
  url = {https://openreview.net/forum?id=QNXzwBo8IO},
}
Figure