mlsanityData to 7 Oct 2026

Provably Faster Gradient Descent via Long Steps

arXiv 2307.06324 ↗First posted 12 Jul 2023math.OC cs.LG cs.NAcited by 20

Not on the map. Why?

Abstract (arXiv)

This work establishes new convergence guarantees for gradient descent in smooth convex optimization via a computer-assisted analysis technique. Our theory allows nonconstant stepsize policies with frequent long steps potentially violating descent by analyzing the overall effect of many iterations at once rather than the typical one-iteration inductions used in most first-order method analyses. We show that long steps, which may increase the objective value in the short term, lead to provably faster convergence in the long term. A conjecture towards proving a faster O(1/Tlog T) rate for gradient descent is also motivated along with simple numerical validation.

Key facts. Cited by 20 papers in the map (data through 7 Oct 2026). Builds on 27 of its 46 references that are in the map. First posted on arXiv 12 Jul 2023.

Builds on

27 of 46 references.

References · 27

  1. 2015Cyclical Learning Rates for Training Neural Networkscited by 627
  2. 2015Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methodscited by 36
  3. 2019Scalable Semidefinite Programmingcited by 36
  4. 2014Optimized first-order methods for smooth convex minimizationcited by 18
  5. 2015Exact Worst-case Performance of First-order Methods for Composite Convex Optimizationcited by 16
  6. 2019Optimal Complexity and Certification of Bregman First-Order Methodscited by 16
  7. 2022Branch-and-Bound Performance Estimation Programming: A Unified Methodology for Constructing Optimal Optimization Methodscited by 16
  8. 2018Optimizing the Efficiency of First-Order Methods for Decreasing the Gradient of Smooth Convex Functionscited by 14
  9. 2021Super-Acceleration with Cyclical Step-sizescited by 14
  10. 2018Operator Splitting Performance Estimation: Tight contraction factors and optimal parameter selectioncited by 13
  11. 2021Acceleration via Fractal Learning Rate Schedulescited by 13
  12. 2019Stochastic first-order methods: non-asymptotic and computer-aided analyses via potential functionscited by 12
15 more
  1. 2018Lyapunov Functions for First-Order Methods: Tight Automated Convergence Guaranteescited by 11
  2. 2021Provable Super-Convergence with a Large Cyclical Learning Ratecited by 10
  3. 2016On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functionscited by 9
  4. 2021Optimal Convergence Rates for the Proximal Bundle Methodcited by 9
  5. 2021An optimal gradient method for smooth strongly convex minimizationcited by 7
  6. 2020Principled Analyses and Design of First-Order Methods with Inexact Proximal Operatorscited by 5
  7. 2020Revisiting Spectral Bundle Methods: Primal-dual (Sub)linear Convergence Ratescited by 5
  8. 2019An Optimal-Storage Approach to Semidefinite Programming using Approximate Complementaritycited by 4
  9. 2018Efficient First-order Methods for Convex Minimization: a Constructive Approachcited by 3
  10. 2018Exploiting Low-Rank Structure in Semidefinite Programming by Approximate Operator Splittingcited by 3
  11. 2018First-order algorithms converge faster than O(1/k) on convex problemscited by 3
  12. 2022Accelerated first-order methods for a class of semidefinite programscited by 2
  13. 2016SPECTRA -- a Maple library for solving linear matrix inequalities in exact arithmeticcited by 1
  14. 2019A relaxed interior point method for low-rank semidefinite programming problems with applications to matrix completioncited by 1
  15. 2021Implicit regularity and linear convergence rates for the generalized trust-region subproblemcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 3; 2024: 5; 2025: 4; 2026: 8.

20 papers.

Sort:

  1. 2023Adaptive Proximal Gradient Method for Convex Optimizationcited by 21
  2. 2023From Stability to Chaos: Analyzing Gradient Descent Dynamics in Quadratic Regressioncited by 16
  3. 2024Anytime Acceleration of Gradient Descentcited by 7
  4. 2025Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regressioncited by 7
  5. 2024Understanding the Generalization Benefits of Late Learning Rate Decaycited by 6
  6. 2024Open Problem: Anytime Convergence Rate of Gradient Descentcited by 5
  7. 2025Minimax Optimal Convergence of Gradient Descent in Logistic Regression via Large and Adaptive Stepsizescited by 5
  8. 2026A lower bound for stepsize-based acceleration of gradient descentcited by 4
  9. 2025Convergence Rates for Gradient Descent on the Edge of Stability in Overparametrised Least Squarescited by 3
  10. 2026Improved Gradient Descent Lower Bounds Beyond Nesterovcited by 2
  11. 2023ELRA: Exponential learning rate adaption gradient descent optimization methodcited by 1
  12. 2026Dynamics of Gradient Descent with Large Step Size Near a Manifold of Flat Minimacited by 1
8 more
  1. 2026Silver Rate Is (Almost) Optimal for Gradient Descentcited by 1
  2. 2024Data-induced multiscale losses and efficient multirate gradient descent schemescited by 0
  3. 2024Quantum Algorithm for Sparse Online Learning with Truncated Gradient Descentcited by 0
  4. 2025First-ish Order Methods: Hessian-aware Scalings of Gradient Descentcited by 0
  5. 2026Tight Bounds for Logistic Regression with Large Stepsize Gradient Descent in Low Dimensioncited by 0
  6. 2026A short proof of near-linear convergence of adaptive gradient descent under fourth-order growth and convexitycited by 0
  7. 2026A Lower Bound for the Heavy-Ball Method on Smooth Convex Functionscited by 0
  8. 2026The Row Normalization Puzzle in Muoncited by 0