Silver Rate Is (Almost) Optimal for Gradient Descent Acceleration

arXiv:2609.09152v1 Announce Type: cross Abstract: We study how far gradient descent (GD) can be accelerated by predetermined nonnegative stepsizes in smooth convex optimization. Writing p_{sil}=log_2(1+sqrt{2}), we prove an Omegaleft(n^{-p_{sil}-O(sqrt{loglog n/log n})}right) non-anytime lower bound. In the anytime setting, every infinite nonnegative schedule has infinitely many horizons with error Omegaleft(n^{-frac{2p_{sil}}{1+p_{sil}}-O(sqrt{loglog 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.

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