Improved Gradient Descent Lower Bounds Beyond Nesterov

arXiv:2609.02855v1 Announce Type: cross Abstract: We study how far gradient descent (GD) can be accelerated by predetermined stepsizes in smooth convex optimization. Going beyond the classical Omega(n^{-2}) first-order oracle lower bound of Nemirovsky and Yudin, we prove an Omega(n^{-1.6342}) non-anytime lower bound and an Omega(n^{-1.2408}) anytime lower bound. These improve the recent Omega(n^{-1.932}) non-anytime lower bound of Ma and Chen and the Omega(n^{-4/3}) anytime lower bound of Tsai et al., respectively. Together with the non-anytime O(n^{-log_2(1+sqrt{2})}) rate achieved by silver schedules, our anytime lower bound establishes a strict separation between the achievable convergence exponents in the two settings.

Source: arXiv cs.LG | 2026-09-03