Paper recorded by Signals 4 on 2026-09-02 in cs.LG. Abstract reproduced from arXiv; link to the original below.
Published 2026-09-02 on arXiv · recorded by Signals 4 on 2026-09-03
Category: cs.LG · 机器学习 · first seen 2026-09-03
We study how far gradient descent (GD) can be accelerated by predetermined stepsizes in smooth convex optimization. Going beyond the classical $Ω(n^{-2})$ first-order oracle lower bound of Nemirovsky and Yudin, we prove an $Ω(n^{-1.6342})$ non-anytime lower bound and an $Ω(n^{-1.2408})$ anytime lower bound. These improve the recent $Ω(n^{-1.932})$ non-anytime lower bound of Ma and Chen and the $Ω(