Improved Gradient Descent Lower Bounds Beyond Nesterov

We study how far gradient descent (GD) can be accelerated by predetermined stepsizes in smooth convex optimization.

We study how far gradient descent (GD) can be accelerated by predetermined stepsizes in smooth convex optimization. Going beyond the classical $Ω(n^{-2})$ first-order oracle lower bound of Nemirovsky and Yudin, we prove an $Ω(n^{-1.6342})$ non-anytime lower bound and an…