Silver Rate Is (Almost) Optimal for Gradient Descent Acceleration
New optimization theory paper proves near-optimal lower bounds for gradient descent with predetermined stepsizes, confirming silver-schedule optimality.
The paper studies the limits of accelerating gradient descent using predetermined nonnegative stepsizes in smooth convex optimization, with the key constant p_sil = log2(1 + sqrt(2)). It proves a non-anytime lower bound of Omega(n^(-p_sil - O(sqrt(log log n / log n)))) on the error achievable by any such stepsize schedule. In the anytime setting, it shows every infinite nonnegative schedule must incur error Omega(n^(-2*p_sil/(1+p_sil) - O(sqrt(log log n / log n)))) at infinitely many horizons. Combined with the silver-schedule upper bound of Altschuler and Parrilo (2025) and the anytime upper bound of Zhang et al. (2025), these results determine the optimal polynomial convergence exponents in both settings.
- Proves a near-optimal non-anytime lower bound for gradient descent with predetermined nonnegative stepsizes in smooth convex optimization.
- Identifies p_sil = log2(1 + sqrt(2)) as the constant governing optimal gradient descent acceleration rates.
- Shows every infinite nonnegative schedule incurs Omega(n^(-2*p_sil/(1+p_sil))) error at infinitely many anytime horizons.
- Results match the Altschuler-Parrilo silver-schedule and Zhang et al. anytime upper bounds, settling optimal convergence exponents.
Full article76 words · extracted from arxiv.org · click to collapse
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.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.09152