mlsanityData to 14 Oct 2026

Gradient Descent's Last Iterate is Often (slightly) Suboptimal

arXiv 2604.13870 ↗First posted 15 Apr 2026math.OC cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

We consider the well-studied setting of minimizing a convex Lipschitz function using either gradient descent (GD) or its stochastic variant (SGD), and examine the last iterate convergence. By now, it is known that standard stepsize choices lead to a last iterate convergence rate of log T/√T after T steps. A breakthrough result of Jain et al. [2019] recovered the optimal 1/√T rate by constructing a non-standard stepsize sequence. However, this sequence requires choosing T in advance, as opposed to common stepsize schedules which apply for any time horizon. Moreover, Jain et al. conjectured that without prior knowledge of T, no stepsize sequence can ensure the optimal error for SGD's last iterate, a claim which so far remained unproven. We prove this conjecture, and in fact show that even in the noiseless case of GD, it is impossible to avoid an excess poly-log factor in T when considering an anytime last iterate guarantee.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 17 of its 32 references that are in the map. First posted on arXiv 15 Apr 2026.

Builds on

17 of 32 references.

References · 17

  1. 2019Introduction to Online Convex Optimizationcited by 803
  2. 2019SGD: General Analysis and Improved Ratescited by 207
  3. 2024The Road Less Scheduledcited by 163
  4. 2018Tight Analyses for Non-Smooth Stochastic Gradient Descentcited by 97
  5. 2021Last iterate convergence of SGD for Least-Squares in the Interpolation regimecited by 42
  6. 2023Revisiting the Last-Iterate Convergence of Stochastic Gradient Methodscited by 38
  7. 2023Exact convergence rate of the last iterate in subgradient methodscited by 25
  8. 2023Acceleration by Stepsize Hedging II: Silver Stepsize Schedule for Smooth Convex Optimizationcited by 20
  9. 2019Stochastic first-order methods: non-asymptotic and computer-aided analyses via potential functionscited by 12
  10. 2025From Continual Learning to SGD and Back: Better Rates for Continual Linear Modelscited by 12
  11. 2025Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regimecited by 12
  12. 2024On the Last-Iterate Convergence of Shuffling Gradient Methodscited by 11
5 more
  1. 2024Accelerated Objective Gap and Gradient Norm Convergence for Gradient Descent via Long Stepscited by 11
  2. 2024Last Iterate Convergence of Incremental Methods and Applications in Continual Learningcited by 10
  3. 2024Anytime Acceleration of Gradient Descentcited by 7
  4. 2024Open Problem: Anytime Convergence Rate of Gradient Descentcited by 5
  5. 2025Last-Iterate Complexity of SGD for Convex and Smooth Stochastic Problemscited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 4.

4 papers.

  1. 2026New Bounds for the Last Iterate of the Stochastic subGradient Methodcited by 0
  2. 2026Dangerous Liaisons of Convex Learning and Non-Affine Aggregationcited by 0
  3. 2026WSqD: A Horizon-Free Learning Rate Schedule for Large Model Trainingcited by 0
  4. 2026Last-Iterate Convergence Rate of Normalized Gradient Descent under H"older Smoothnesscited by 0