{"id":"arxiv/2609.02855","url":"https://arxiv.org/abs/2609.02855","tags":["math.OC","cs.LG","stat.ML"],"score":0,"title":"Improved Gradient Descent Lower Bounds Beyond Nesterov","domain":"math.OC","source":"arxiv","authors":["Yuhan Ye","Kaizhao Liu"],"reviews":0,"subject":"math.OC","summary":"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 (1983), 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 (2026) and the $Ω(n^{-4/3})$ anytime lower bound of Tsai et al. (2026), respectively. Both results continue to hold when the stepsizes may be negative. Our anytime lower bound also shows that the…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-02","reactions":{}}