Silver Rate Is (Almost) Optimal for Gradient Descent
Yuhan Ye, Kaizhao Liu
原文摘要
Gradient descent (GD) is one of the most fundamental algorithms in optimization. Yet even for smooth convex objectives, the optimal rate among predetermined nonnegative stepsize schedules has remained unresolved. Altschuler and Parrilo [Mathematical Programming, 2025] showed that their recursive silver stepsize schedule achieves an $O(n^{-p_{\mathrm{sil}}})$ rate, where $p_{\mathrm{sil}}=\log_2(1+\sqrt2)\approx1.2716$, improving upon the classical $O(n^{-1})$ rate of constant-step GD. Although the optimality of $p_{\mathrm{sil}}$ has been well supported by numerical evidence for small $n$, a matching lower bound has remained missing. In this paper, we prove an $Ω(n^{-p_{\mathrm{sil}}-o(1)})$ lower bound for GD, showing that $p_{\mathrm{sil}}$ is the optimal convergence exponent. Additionally, we prove an anytime lower bound that matches the exponent $2p_{\mathrm{sil}}/(1+p_{\mathrm{sil}})\approx1.1195$ of the known upper bound [Zhang, Lee, Du, and Chen, COLT 2025]. Building on the approaches of [Ma and Chen, 2026; Jung, Cho, and Yun, 2026], we select specific iterations as checkpoints at which the GD trajectory explores a new coordinate, and we couple these coordinates using a chain of local functions. Our main technical contribution is a local hard function that bends the GD trajectory between successive checkpoints, resulting in a sharpened lower bound. For each prescribed stepsize schedule, we maximize this bound over admissible checkpoint sets. A recursive analysis of this maximum then yields a lower bound matching the silver exponent for every such schedule.
math.OC · cs.LG