Whether horizon-dependent Heavy-Ball schedules achieve Nesterov’s O(T^-2) rate

For each horizon T≥2T\ge 2, consider the Heavy-Ball iteration xt+1=xt−ηt∇f(xt)+βt(xt−xt−1)x_{t+1}=x_t-\eta_t\nabla f(x_t)+\beta_t(x_t-x_{t-1}), with predetermined horizon-dependent parameters satisfying ηt≥0\eta_t\ge 0 and 0≤βt<10\le\beta_t<1, and with zero initial velocity x−1=x0x_{-1}=x_0. Does there exist such a parameter schedule for which, for every convex 11-smooth function ff and every initialization satisfying ∥x0−x⋆∥≤1\|x_0-x^\star\|\le 1 for some minimizer x⋆x^\star, the last iterate satisfies f(xT)−f⋆=O(T−2)f(x_T)-f^\star=O(T^{-2})? The cited lower-bound claim asserts that for every such schedule there is a convex 11-smooth objective, with the stated initialization condition, for which f(xT)−f⋆=Ω ⁣(1Tαlog⁡T)f(x_T)-f^\star=\Omega\!\left(\frac{1}{T^\alpha\log T}\right), where α=1+52\alpha=\frac{1+\sqrt{5}}{2}, thereby ruling out the target rate for this class if the claim is correct.

References

Progress summary

Refreshed
Claimed solved

A September 2026 lower-bound claim says no allowed Heavy-Ball schedule can match Nesterov’s rate, but the claim has not been independently verified.

The problem asks whether Heavy-Ball methods with schedules depending on the time horizon can achieve Nesterov’s classical rate O(T−2)O(T^{-2}) under the stated restrictions. No proposer or original date is identified in the retrieved material.

September 8, 2026 lower bound

A report concerning A Lower Bound for the Heavy-Ball Method on Smooth Convex Functions claims to construct, for every allowed schedule, a smooth convex objective with a slower last-iterate lower bound. If correct, this rules out the target rate for the specified Heavy-Ball class, but the result is unverified.

Current status (as of September 2026): A claimed lower bound settles the stated Heavy-Ball question negatively, subject to verification; broader accelerated methods remain outside its scope.

Sources

Solutions 0

No solutions have been posted yet.