Tail Averaging for Optimal Stochastic Convergence

This direction is split into other directions: initial iterate bias. Its last version stays readable and citable here.

Version 1 of 136 papers38 conceptsfrozen 2026-10-04

In stochastic optimization, we face a fundamental tension between speed and stability. To find the minimum of a function using noisy data, Stochastic Gradient Descent (SGD) takes small steps based on random samples. Because these individual steps are "noisy," practitioners typically average the iterates to produce a stable final estimate.

However, a growing body of research reveals a hidden flaw in this standard practice: uniform averaging—treating the very first step with the same weight as the very last—permanently "pollutes" the solution with the errors of the initial guess. To reach theoretically optimal convergence rates, algorithms must learn to forget their past.

The Problem of Initial Guessing Bias

When we begin training a model, the initial parameters are often far from the optimal solution. In the early stages of optimization, the gradient steps are large and high-variance as the algorithm aggressively searches for the right neighborhood.

As Aurelien Lucchi, Emanuele Francazi, and Marco Baity-Jesi demonstrate in Initial Guessing Bias: How Untrained Networks Favor Some Classes, neural networks start with structural biases that require significant gradient effort to overcome. If we use a simple uniform average of all iterates, these early, "biased" guesses never truly go away. They linger in the average, slowing down the convergence rate and preventing the algorithm from reaching the high-precision regime.

Suffix Averaging and the Optimal Rate

For years, there was a gap in the theory of strongly convex optimization. While complex algorithms could achieve an optimal convergence rate of $O(1/T)$, standard SGD appeared stuck at a slower rate.

Ohad Shamir and Karthik Sridharan solved this in Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization by introducing suffix averaging. Instead of averaging every iterate from $t=1$ to $T$, they proposed averaging only the final fraction (the "suffix") of the iterations.

By discarding the early "burn-in" trajectory, the estimator effectively "forgets" the high-error initial states. This simple tweak allows standard SGD to recover the optimal $O(1/T)$ rate. Ohad Shamir and Tong Zhang further refined this in Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes, showing that polynomial-decay averaging—where later iterates are given progressively more weight—achieves similar optimality without needing to know the total number of steps in advance.

Epochs and Scheduled Restarts

Another way to discard the influence of the past is to organize the optimization into distinct stages. Satyen Kale introduced Epoch-GD in An optimal algorithm for stochastic strongly-convex optimization, which divides the training into epochs of increasing length. At the end of each epoch, the algorithm averages the current iterates and uses that average as the starting point for the next epoch, while simultaneously decreasing the learning rate.

This "restarting" logic has proven essential for more complex problems, such as bilinear games (common in GAN training). Chris Junchi Li, Yaodong Yu, and Nicolas Loizou showed in On the Convergence of Stochastic Extragradient for Bilinear Games using Restarted Iteration Averaging that without restarts, stochastic extragradient methods merely "orbit" the solution. Scheduled restarts force the algorithm to collapse its history and land precisely on the Nash equilibrium.

Beyond Standard Optimization

The intuition that "the tail is more informative than the head" extends across various domains of machine learning:

Summary of Intuition

The success of tail-averaging rests on a simple realization: The early iterates of a stochastic process contain more "bias" than "signal." By the time an algorithm has run for thousands of steps, the most recent iterates are likely hovering very close to the true optimum, buffeted only by local noise. By averaging only these recent points—or weighting them more heavily—we use the averaging to cancel out the noise without dragging the "ghosts" of the initial, distant starting point into our final result.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_tail_averaging_for_optimal_stochastic_co_b9d5adf3,
  title = {Tail Averaging for Optimal Stochastic Convergence},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/tail-averaging-for-optimal-stochastic-convergence/rdr_b9d5adf3c14145e89e3c40d746f5195a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_tail_averaging_for_optimal_stochastic_co_b9d5adf3_v1,
  title = {Tail Averaging for Optimal Stochastic Convergence},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/tail-averaging-for-optimal-stochastic-convergence/rdr_b9d5adf3c14145e89e3c40d746f5195a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}