Whether horizon-dependent Heavy-Ball schedules achieve Nesterov’s O(T^-2) rate
For each horizon , consider the Heavy-Ball iteration , with predetermined horizon-dependent parameters satisfying and , and with zero initial velocity . Does there exist such a parameter schedule for which, for every convex -smooth function and every initialization satisfying for some minimizer , the last iterate satisfies ? The cited lower-bound claim asserts that for every such schedule there is a convex -smooth objective, with the stated initialization condition, for which , where , thereby ruling out the target rate for this class if the claim is correct.
References
Primary source
Additional references
Progress summary
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 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
- arxiv.org
- trungvietvu.github.io
- arxiv.org
- sciencedirect.com
- hal.science
- par.nsf.gov
- ww3.math.ucla.edu
- pubmed.ncbi.nlm.nih.gov
- researchgate.net
- ar5iv.labs.arxiv.org
- export.arxiv.org
- arxiv.org
- ar5iv.labs.arxiv.org
- export.arxiv.org
- mathstodon.xyz
- mathstodon.xyz
- mathstodon.xyz
- mathstodon.xyz
- mathstodon.xyz
- deepmind.google
- deepmind.google
- community.openai.com
Solutions 0
No solutions have been posted yet.