{"id":"arxiv/2609.04032","url":"https://arxiv.org/abs/2609.04032","tags":["math.OC"],"score":0,"title":"Stronger Lower Bounds for (Non-)Anytime Acceleration of Gradient Descent","domain":"math.OC","source":"arxiv","authors":["Minchan Jung","Hanseul Cho","Chulhee Yun"],"reviews":0,"subject":"math.OC","summary":"The rate-optimal convergence rate of gradient descent (GD) with a fixed step-size is well known to be $Θ(N^{-1})$ for $L$-Lipschitz smooth convex objectives in the prior art in convex optimization. Surprisingly, several recent works show that we can accelerate vanilla GD by applying a nonconstant, nonadaptive, deterministic step-size schedule. The best-known upper bounds so far in the non-anytime & anytime setups are $O(N^{-1.271})$ [Altschuler and Parrilo, 2025, Grimmer et al., 2023] and $O(N^{-1.119})$ [Zhang et al., 2025], respectively. On the other hand, the best reported lower bounds…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-03","reactions":{}}