A lower bound for stepsize-based acceleration of gradient descent

Jianhao Ma, Yuxin Chen

Recent work has shown that, for smooth convex optimization, plain gradient descent can be accelerated from its textbook convergence rate of $O(T^{-1})$ (where $T$ denotes the numbe…