Accelerating Optimization with Increasing Iterate Averaging

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

Version 1 of 178 papers117 conceptsfrozen 2026-10-04

In stochastic optimization, we face a fundamental tension between stability and speed. If we use only the last iterate of an algorithm like Stochastic Gradient Descent (SGD), we benefit from the most recent "knowledge" the model has acquired, but we suffer from high variance—the last step might have been pushed off-course by a noisy gradient.

To solve this, researchers traditionally use Polyak-Ruppert averaging, which takes a uniform average of all iterates. While this provides a "safety net" of stability, it introduces a new problem: the average is permanently contaminated by the poor initial guesses from the start of training. This "memory" of early errors often forces a logarithmic penalty on convergence rates, slowing the progress of the algorithm.

A growing body of research suggests a powerful middle ground: Increasing Iterate Averaging. By assigning higher weights to more recent iterates, we can achieve the stability of averaging while maintaining the aggressive convergence speed of the most recent steps.

The Logarithmic Tax on Uniform Averaging

When optimizing strongly convex functions, the "gold standard" convergence rate is $O(1/T)$. However, as Ohad Shamir and Tong Zhang demonstrated in Stochastic Gradient Descent for Non-smooth Optimization, standard uniform averaging often hits a theoretical ceiling of $O(\log T / T)$.

The $\log T$ factor is essentially a "tax" paid for remembering the past too well. Because every iterate—including the very first, most inaccurate one—carries the same weight ($1/T$), the errors from the beginning of the optimization process take a long time to wash out.

To bypass this, Nicholas J. A. Harvey and colleagues showed in Simple and optimal high-probability bounds for strongly-convex stochastic gradient descent that a linear weighting scheme—where the weight of iterate $t$ is proportional to its index—restores the optimal $O(1/T)$ rate. This simple change ensures that the "refined" later iterates eventually dominate the "noisy" early ones.

Polynomial Weighting and the Power of Recency

The shift from uniform to non-uniform weighting isn't just a binary choice; it's a spectrum. Researchers have explored various "growth schedules" for these weights:

The intuition is that as the optimization progresses, the "signal-to-noise ratio" of the iterates improves. By using a polynomial growth function, we effectively "discount" the early exploration phase of the algorithm.

Beyond SGD: Saddle Points and Games

The benefits of increasing iterate averaging extend far beyond simple gradient descent. It has become a vital tool for solving Saddle-Point Problems (SPPs), which are central to training GANs and solving zero-sum games like Poker.

In Increasing Iterate Averaging for Solving Saddle-Point Problems, Christian Kroer and his co-authors show that while uniform averaging is the standard theoretical requirement for convergence in SPPs, it is often sluggish in practice. Their Increasing Iterate Averaging Scheme (IIAS) maintains the $O(1/T)$ theoretical guarantee while drastically improving empirical performance by prioritizing recent progress.

Interestingly, Kroer and Julien Grand-Clément later proposed in Solving optimization problems with Blackwell approachability that we can even decouple these weights. One can use linear weighting for the decision variables (to move quickly) while keeping uniform weighting for the payoffs (to maintain stability), a strategy that further optimizes the path to equilibrium.

Forgetting as a Feature

Perhaps the most surprising insight from this research is that "forgetting" is a feature, not a bug. In many complex optimization landscapes, the initial steps are not just noisy—they are often headed in the wrong direction entirely.

In Discounted Regret Minimization, Brown and Sandholm argue that "discounting" early iterations allows an algorithm to recover from early mistakes much faster. This is echoed in the work of Aaron Defazio and Robert M. Gower in The Power of Factorial Powers, where they reframe momentum itself as a recursive averaging process that controls the rate of forgetting the past.

By moving away from uniform averages, we allow our optimization algorithms to evolve. We acknowledge that an iterate produced after 1,000 steps of learning is fundamentally more valuable than one produced after 10, and our averaging schemes should reflect that reality. Whether through linear, quadratic, or polynomial weights, increasing iterate averaging provides a mathematically rigorous way to "look forward" without losing the stability of the past.

Papers in this version

Showing 60 of 78 papers.

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_accelerating_optimization_with_increasin_d04456f7,
  title = {Accelerating Optimization with Increasing Iterate Averaging},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/accelerating-optimization-with-increasing-iterate-averaging/rdr_d04456f77af1448ea3bf219b57d69534},
  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_accelerating_optimization_with_increasin_d04456f7_v1,
  title = {Accelerating Optimization with Increasing Iterate Averaging},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/accelerating-optimization-with-increasing-iterate-averaging/rdr_d04456f77af1448ea3bf219b57d69534/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}