Silver Rate Is (Almost) Optimal for Gradient Descent: The Strongly Convex Case

Kaizhao Liu; Yuhan Ye

Silver Rate Is (Almost) Optimal for Gradient Descent: The Strongly Convex Case

Kaizhao Liu, Yuhan Ye

Preprint

In the authors' words

We study gradient descent with predetermined nonnegative stepsizes on smooth strongly convex functions. Let $p_{s i l} = lo g_{2} (1 + 2)$ and $κ$ be the condition number. We prove the iteration lower bound $Ω (κ^{\frac{1}{p _{s i l}} - o (1)} lo g \frac{1}{δ})$ for both relative squared distance and relative function error, uniformly over $0 < δ < 1$ and sufficiently large $κ$ . This matches the polynomial exponent of $κ$ for the Silver stepsize schedule established in [Altschuler and Parrilo, 2025].

Main resultLimitation the authors admit

Read the paper PDF

Appeared: Thursday, September 24. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 47 pages, 4 figures

Silver Rate Is (Almost) Optimal for Gradient Descent: The Strongly Convex Case

In the authors' words

More on Optimization that day

Stochastic Appointment Scheduling with Patient-and-Time-Dependent Probability Distributions

An Exact Algorithm for the Max-Min Covering Location Blocker Problem

From Frequentist to Bayesian Contextual Optimization

SWAP: A Scalable, Warm-Startable, Anytime Permutation Solver for Optimal Transport

Stochastic Augmented Lagrangian Framework with Second-Order Convergence Guarantees for Nonconvex Expectation-Constrained Optimization