# A Lower Bound for the Heavy-Ball Method on Smooth Convex Functions

arXiv: https://arxiv.org/abs/2609.08656 · HTML: https://mlsanity.com/paper/2609.08656/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 17 references that are in the map.
- First posted on arXiv 8 Sep 2026.

## Builds on (most cited first, 11 of 11)

- [Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints](https://mlsanity.com/paper/1408.3595/) (2014)
- [Global convergence of the Heavy-ball method for convex optimization](https://mlsanity.com/paper/1412.7457/) (2014)
- [Provably Faster Gradient Descent via Long Steps](https://mlsanity.com/paper/2307.06324/) (2023)
- [Acceleration by Stepsize Hedging II: Silver Stepsize Schedule for Smooth Convex Optimization](https://mlsanity.com/paper/2309.16530/) (2023)
- [Non-ergodic Convergence Analysis of Heavy-Ball Algorithms](https://mlsanity.com/paper/1811.01777/) (2018)
- [Provable non-accelerations of the heavy-ball method](https://mlsanity.com/paper/2307.11291/) (2023)
- [Accelerated Objective Gap and Gradient Norm Convergence for Gradient Descent via Long Steps](https://mlsanity.com/paper/2403.14045/) (2024)
- [Accelerated Gradient Descent via Long Steps](https://mlsanity.com/paper/2309.09961/) (2023)
- [A lower bound for stepsize-based acceleration of gradient descent](https://mlsanity.com/paper/2608.10418/) (2026)
- [Improved Gradient Descent Lower Bounds Beyond Nesterov](https://mlsanity.com/paper/2609.02855/) (2026)
- [Stronger Lower Bounds for (Non-)Anytime Acceleration of Gradient Descent](https://mlsanity.com/paper/2609.04032/) (2026)

## Abstract (arXiv)

Can the classical Heavy-Ball method, with arbitrary horizon-dependent parameters chosen in advance, achieve Nesterov's O(T-2) last-iterate rate on every smooth convex objective? We provide a negative answer. For every horizon T≥2 and every predetermined schedule with nonnegative step sizes and momenta in [0,1), there exists a convex 1-smooth objective, with initialization distance at most one and zero initial velocity, for which the last iterate of the Heavy-Ball method satisfies [ f(xT)-f^star=Omega!left(frac1Tαlog Tright), qquad α=frac1+√52. ] Thus even fully nonstationary, horizon-dependent tuning cannot give the classical Heavy-Ball method a Nesterov-rate guarantee on the smooth convex class.