Pith. sign in

REVIEW 6 cited by

Accelerated Gradient Descent via Long Steps

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.09961 v2 pith:4OWQMVTJ submitted 2023-09-18 math.OC

Benjamin Grimmer , Kevin Shu , Alex L. Wang This is my paper · ORCID
classification math.OC
keywords rategradientacceleratedconvergenceconvexdescentstepsbig-o
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

Recently Grimmer [1] showed for smooth convex optimization by utilizing longer steps periodically, gradient descent's textbook $LD^2/2T$ convergence guarantees can be improved by constant factors, conjecturing an accelerated rate strictly faster than $O(1/T)$ could be possible. Here we prove such a big-O gain, establishing gradient descent's first accelerated convergence rate in this setting. Namely, we prove a $O(1/T^{1.0564})$ rate for smooth convex minimization by utilizing a nonconstant nonperiodic sequence of increasingly large stepsizes. It remains open if one can achieve the $O(1/T^{1.178})$ rate conjectured by Das Gupta et. al. [2] or the optimal gradient method rate of $O(1/T^2)$. Big-O convergence rate accelerations from long steps follow from our theory for strongly convex optimization, similar to but somewhat weaker than those concurrently developed by Altschuler and Parrilo [3].

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 6 Pith papers

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

  1. Accelerating Proximal Gradient Descent via Silver Stepsizes

    math.OC 2024-12 conditional novelty 8.0 of 10

    Proximal and projected gradient descent using the silver stepsize schedule achieve the silver convergence rate O(ε^{-log_ρ 2}) for composite convex optimization, matching the rate known only for unconstrained smooth g...

  2. Dynamics of Gradient Descent with Large Step Size Near a Manifold of Flat Minima

    cs.LG 2026-07 conditional novelty 7.0 of 10

    Large-step GD near a flat-minima manifold of overparametrised least squares has a normal form that yields subcritical, critical, and supercritical convergence theorems, including for deep matrix factorisation.

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

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

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

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