Stronger Lower Bounds for (Non-)Anytime Acceleration of Gradient Descent
Abstract
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 (or barriers) up to date in the non-anytime & anytime setups are Ω(N−1.635) and Ω(N−1.241) [Ye and Liu, 2026], respectively. We narrow these gaps by establishing stronger lower bounds for GD's convergence rate in both settings: Ω(N−1.450) for the non-anytime rate bound and Ω(N−1.184) for the anytime rate barrier.
Related
- Anytime-Feasible Gradient Descent for Constrained Optimization Under Gradient Uncertainty
- Can Acceleration in Gradient-Norm Minimization Be Anytime? Sharp Last-Iterate Limits in Smooth Convex Optimization
- Improved Gradient Descent Lower Bounds Beyond Nesterov
- Lower Bounds on Inference Complexity for Polyak-Ruppert Averaged Stochastic Gradient Descent
- Broximal Gradient Descent: A Projection-Free Sister of Projected Gradient Descent
BibTeX
@misc{jung2026stronger,
title = {{Stronger Lower Bounds for (Non-)Anytime Acceleration of Gradient Descent}},
author = {Minchan Jung and Hanseul Cho and Chulhee Yun},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.04032},
eprint = {2609.04032},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.04032},
}
RIS
TY - UNPB
TI - Stronger Lower Bounds for (Non-)Anytime Acceleration of Gradient Descent
AU - Minchan Jung
AU - Hanseul Cho
AU - Chulhee Yun
PY - 2026
DA - 2026/09/04
PB - arXiv
DO - 10.48550/arxiv.2609.04032
UR - https://arxiv.org/abs/2609.04032
AB - 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 (or barriers) up to date in the non-anytime & anytime setups are Ω(N^−1.635) and Ω(N^−1.241) [Ye and Liu, 2026], respectively. We narrow these gaps by establishing stronger lower bounds for GD's convergence rate in both settings: Ω(N^−1.450) for the non-anytime rate bound and Ω(N^−1.184) for the anytime rate barrier.
ER -