  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 study adopts a different approach:
studying momentum through the lens of quadratic invariants of simple harmonic
oscillators. By utilizing the modified Hamiltonian of Stormer-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. This is
a promising first step towards potentially proving the acceleration of Polyak's
momentum method and we hope it inspires further research in this field.
