Polylog-Tight Bounds for Step-Size Acceleration of GD under Strong Convexity

We study how much a predefined nonnegative step-size schedule can accelerate gradient descent on $L$-smooth, $\mu$-strongly convex functions. For condition number $\kappa =L/\mu \ge 2$ and $\epsilon \in (0,1/2]$, we prove lower complexity bounds of rate $\Omega ({\kappa }^{{\log }_{\rho }2}(\log \kappa {)}^{-{\gamma }_{\ast }}\log (1/\epsilon ))\approx \Omega ({\kappa }^{0.786}(\log \kappa {)}^{-0.322}\log (1/\epsilon ))$ for relative squared distance to the minimizer in both *non-anytime* and *anytime* settings. Here, $\rho =1+\sqrt{2}$ is the silver ratio. We also find that the periodic Silver step-size schedule (Altschuler & Parrilo, 2025a) achieves the *anytime* upper complexity bound $O({\kappa }^{{\log }_{\rho }2}\log (1/\epsilon ))\approx O({\kappa }^{0.786}\log (1/\epsilon ))$, extending its known bound at completed-block endpoints to every iterate beyond the accuracy threshold. Hence, our lower bounds tightly match the upper bounds up to $\mathrm{polylog}(\kappa )$. We also derive bounds for the function value gap and squared gradient norm.