Last Iterate Convergence in Stochastic Optimization

This direction is merged into another direction: last-iterate convergence (last-iterate convergence guarantee). Its last version stays readable and citable here.

Version 1 of 162 papers79 conceptsfrozen 2026-10-04

In the world of machine learning, there is a curious disconnect between how we prove algorithms work and how we actually use them. If you look at a classic textbook on Stochastic Gradient Descent (SGD), the convergence proofs often rely on iterate averaging (or "ergodic" convergence). The theory tells us to track every single model state during training and then deploy their average.

In practice, almost no one does this. Engineers simply take the last iterate—the very final set of weights after the last epoch—and ship it to production. For years, this was a "practitioner's secret" that lacked rigorous support in non-smooth or stochastic settings. Recent research has finally closed this gap, proving that the last iterate is not just a heuristic, but a theoretically optimal strategy.

The Burden of the Average

The traditional preference for averaging stems from the Online-to-Batch conversion recipe. As Ashok Cutkosky explains, online learning algorithms are designed to minimize regret over a sequence. To turn these into a single stable model, you average the iterates to "smooth out" the noise inherent in stochastic gradients.

However, averaging has three major flaws:

  1. Memory Overhead: Storing a running average of millions of parameters is expensive.
  2. Sparsity Destruction: If your iterates are sparse (many zeros), their average likely won't be, ruining the efficiency of the final model.
  3. Early Iterate Pollution: The average is "polluted" by the initial, low-quality guesses from the start of training.

To solve this, Ohad Shamir and Tong Zhang introduced polynomial-decay averaging in Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes. This scheme weights later iterates more heavily, providing a bridge toward last-iterate guarantees without needing to know the total number of steps in advance.

Why the Last Iterate Succeeds

Why does the last iterate actually converge? Intuition suggests that as the learning rate shrinks, the "noise" in the stochastic updates also shrinks, allowing the final state to settle into a minimum.

Guillaume Garrigos and Juan Peypouquet recently showed in Last-Iterate Complexity of SGD for Convex and Smooth Stochastic Problems that the last iterate of plain SGD converges at a rate of $\tilde{O}(1/\sqrt{T})$ for smooth convex problems. Crucially, they achieved this without the unrealistic assumption of "uniformly bounded gradients," which had long been a crutch in earlier proofs.

In non-convex landscapes, the intuition is even more striking. Aritra Dutta and colleagues found that high-quality solutions (stationary points) are not randomly distributed; they actually cluster in the tail of the training run Demystifying the Myths and Legends of Nonconvex Convergence of SGD. By the end of training, almost the entire "tail" of the trajectory consists of good solutions, making the last iterate a highly reliable proxy for the optimum.

Optimal Scheduling and Refinement

The choice of learning rate is the "secret sauce" for last-iterate success. While theory often suggests $1/\sqrt{t}$ schedules, practitioners prefer linear or cosine decay.

Aaron Defazio and Ashok Cutkosky proved in When, Why and How Much? Adaptive Learning Rate Scheduling by Refinement that the humble linear decay schedule is actually theoretically optimal for last-iterate convergence. They introduced a "refinement" method that allows any schedule to be tuned specifically to ensure the final model state is the best possible one.

Beyond Standard SGD: Shuffling and Minimax

The push for last-iterate guarantees has extended into more complex optimization domains:

The Practical Upshot

The shift toward non-ergodic (last-iterate) analysis simplifies the machine learning pipeline. It justifies the use of the final model weights, validates early stopping as a form of iterative regularization Junhong Lin, and provides a rigorous foundation for modern adaptive optimizers like Adam Ruinan Jin. By focusing on the destination rather than the average of the journey, researchers have aligned optimization theory with the reality of deep learning.

Papers in this version

Showing 60 of 62 papers.

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_last_iterate_convergence_in_stochastic_o_052622ae,
  title = {Last Iterate Convergence in Stochastic Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/last-iterate-convergence-in-stochastic-optimization/rdr_052622ae31714741ab40d22b18afed52},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_last_iterate_convergence_in_stochastic_o_052622ae_v1,
  title = {Last Iterate Convergence in Stochastic Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/last-iterate-convergence-in-stochastic-optimization/rdr_052622ae31714741ab40d22b18afed52/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}