Search papers, labs, and topics across Lattice.
To establish the fundamental performance limits of accelerating gradient descent solely via predetermined nonnegative stepsizes on smooth convex objectives, this work derives tight convergence lower bounds in both anytime and non-anytime regimes. The authors prove an $\Omega\left(n^{-p_{\mathrm{sil}}-o(1)}\right)$ lower bound for fixed horizons and an $\Omega\left(n^{-\frac{2p_{\mathrm{sil}}}{1+p_{\mathrm{sil}}}-o(1)}\right)$ lower bound for anytime schedules, where $p_{\mathrm{sil}}=\log_2(1+\sqrt{2})\approx 1.27$. In conjunction with recently discovered silver-rate upper bounds, these results definitively pin down the exact optimal polynomial convergence exponents achievable by memoryless gradient descent.
Vanilla gradient descent cannot beat the silver stepsize schedule, proving that predetermined learning rates hit a hard theoretical limit of $\mathcal{O}(n^{-\log_2(1+\sqrt{2})})$ without momentum.
We study how far gradient descent (GD) can be accelerated by predetermined nonnegative stepsizes in smooth convex optimization. Writing $p_{\mathrm{sil}}=\log_2(1+\sqrt{2})$, we prove an $惟\left(n^{-p_{\mathrm{sil}}-O(\sqrt{\log\log n/\log n})}\right)$ non-anytime lower bound. In the anytime setting, every infinite nonnegative schedule has infinitely many horizons with error $惟\left(n^{-\frac{2p_{\mathrm{sil}}}{1+p_{\mathrm{sil}}}-O(\sqrt{\log\log n/\log n})}\right)$. Together with the silver-schedule upper bound [Altschuler and Parrilo, 2025] and the anytime upper bound [Zhang et al., 2025], our results determine the optimal polynomial convergence exponents in both settings.
