# Stronger Lower Bounds for (Non-)Anytime Acceleration of Gradient Descent

arXiv: https://arxiv.org/abs/2609.04032 · HTML: https://mlsanity.com/paper/2609.04032/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Sep 2026.

## Built on by (most cited first, 2 of 2)

- [Silver Rate Is (Almost) Optimal for Gradient Descent](https://mlsanity.com/paper/2609.09152/) (2026)
- [A Lower Bound for the Heavy-Ball Method on Smooth Convex Functions](https://mlsanity.com/paper/2609.08656/) (2026)

## Abstract (arXiv)

The rate-optimal convergence rate of gradient descent (GD) with a fixed step-size is well known to be Theta(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 Omega(N-1.635) and Omega(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: Omega(N-1.450) for the non-anytime rate bound and Omega(N-1.184) for the anytime rate barrier.