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

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.