PreprintarXiv licencearXiv
A Lower Bound for the Heavy-Ball Method on Smooth Convex Functions
Abstract
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⋆=Ω (1/(Tαlog T)), α=(1+√5)/2. Thus even fully nonstationary, horizon-dependent tuning cannot give the classical Heavy-Ball method a Nesterov-rate guarantee on the smooth convex class.
Related
- A sharp lower bound for torsional rigidity of convex domains
- A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model
- CRANDALL-PAZY RIGIDITY FOR LOWER SEMICONTINUOUS CONVEX FUNCTIONS: A BALANCED MEDIAN-FLOW ARGUMENT
- An Inexact Augmented Lagrangian Method for (L0, L1)-Smooth Convex Optimization
- On the Optimal Linear Minimization Oracle Complexity of Active-Hull Methods for Minimizing Convex Hölder Smooth Functions
BibTeX
@misc{ma2026lower,
title = {{A Lower Bound for the Heavy-Ball Method on Smooth Convex Functions}},
author = {Jianhao Ma and Jingzhao Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.08656},
eprint = {2609.08656},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.08656},
}
RIS
TY - UNPB
TI - A Lower Bound for the Heavy-Ball Method on Smooth Convex Functions
AU - Jianhao Ma
AU - Jingzhao Zhang
PY - 2026
DA - 2026/09/08
PB - arXiv
DO - 10.48550/arxiv.2609.08656
UR - https://arxiv.org/abs/2609.08656
AB - 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(x_T)−f^⋆=Ω (1/(T^αlog T)), α=(1+√5)/2. Thus even fully nonstationary, horizon-dependent tuning cannot give the classical Heavy-Ball method a Nesterov-rate guarantee on the smooth convex class.
ER -