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 $κ$ be the condition number. We prove the iteration lower bound $Ω\left(κ^{\frac{1}{p_{\mathrm{sil}}}-o(1)}\log\frac1δ\right)$ for both relative squared