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

En palabras de los autores

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].

Resultado principalLimitación que admiten los autores

Leer el paper PDF

Apareció: jueves, 24 de septiembre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 47 pages, 4 figures

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

En palabras de los autores

Más de Optimización ese día

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