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

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})$ and $O(N^{-1.119})$, 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})$, 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.