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

Minchan Jung, Hanseul Cho, Chulhee Yun

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 con…