Pith. sign in

REVIEW 4 cited by

Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedule

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2309.07879 v1 pith:WGLV5PLL submitted 2023-09-14 math.OC cs.DS

Jason M. Altschuler , Pablo A. Parrilo This is my paper · ORCID
classification math.OCcs.DS
keywords stepsizeratesilverscheduleacceleratedaccelerationapproxconvergence
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

Can we accelerate convergence of gradient descent without changing the algorithm -- just by carefully choosing stepsizes? Surprisingly, we show that the answer is yes. Our proposed Silver Stepsize Schedule optimizes strongly convex functions in $k^{\log_{\rho} 2} \approx k^{0.7864}$ iterations, where $\rho=1+\sqrt{2}$ is the silver ratio and $k$ is the condition number. This is intermediate between the textbook unaccelerated rate $k$ and the accelerated rate $\sqrt{k}$ due to Nesterov in 1983. The non-strongly convex setting is conceptually identical, and standard black-box reductions imply an analogous accelerated rate $\varepsilon^{-\log_{\rho} 2} \approx \varepsilon^{-0.7864}$. We conjecture and provide partial evidence that these rates are optimal among all possible stepsize schedules. The Silver Stepsize Schedule is constructed recursively in a fully explicit way. It is non-monotonic, fractal-like, and approximately periodic of period $k^{\log_{\rho} 2}$. This leads to a phase transition in the convergence rate: initially super-exponential (acceleration regime), then exponential (saturation regime).

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Anytime Acceleration of Gradient Descent

    cs.LG 2024-11 conditional novelty 7.0 of 10

    Gradient descent with a recursively repeated silver stepsize schedule achieves an anytime convergence rate of O(T^{-1.119}) for smooth convex functions, and exp(-Omega(T/kappa^{0.893})) for strongly convex functions.

  2. Learning Algorithm Hyperparameters for Fast Parametric Convex Optimization

    math.OC 2024-11 conditional novelty 7.0 of 10

    A machine-learning framework that learns a shared hyperparameter sequence for first-order optimization solvers, achieving order-of-magnitude speedups with only 10 training instances.

  3. Finite Horizon Optimization: Framework and Applications

    math.OC 2024-12 reject novelty 6.0 of 10

    A finite-horizon stepsize rule for the primal-dual method on LP, found via a 4x4 SDP, is claimed to accelerate convergence at the T-th iteration and to give about 3.9x speedup on Netlib instances.

  4. Acceleration by Random Stepsizes: Hedging, Equalization, and the Arcsine Stepsize Schedule

    math.OC 2024-12 accept novelty 4.0 of 10

    For m-strongly convex, M-smooth separable objectives, GD with i.i.d. inverse stepsizes from the Arcsine(m,M) distribution converges almost surely at rate (√κ−1)/(√κ+1), the optimal accelerated rate.

Pith tools