Silver Rate Is (Almost) Optimal for Gradient Descent: The Strongly Convex Case
\(\)
We study gradient descent with predetermined nonnegative stepsizes on smooth strongly convex functions. Let \(p_{\mathrm{sil}}=\log_2(1+\sqrt2)\) and \(\kappa\) be the condition number. We prove the iteration lower bound \(\Omega\left(\kappa^{\frac{1}{p_{\mathrm{sil}}}-o(1)}\log\frac1\delta\right)\)for both relative squared distance and relative function error, uniformly over \(0<\delta<1\) and sufficiently large \(\kappa\). This matches the polynomial exponent of \(\kappa\) for the Silver stepsize schedule established in [Altschuler and Parrilo, 2025].