Non-Uniform Iterate Averaging

45 concepts32 papers2 proposals

When optimizing machine learning models with stochastic gradients, the final parameter estimate often fluctuates significantly due to inherent gradient noise. To stabilize this trajectory, a classic remedy is Ruppert-Polyak averaging, which computes a simple uniform average of all visited points:

$$\bar{\theta}_T = \frac{1}{T} \sum_{t=1}^T \theta_t$$

While uniform averaging successfully dampens stochastic variance, it introduces a severe "memory problem." It treats the highly inaccurate initial guesses from the start of optimization with the exact same importance as the highly refined parameters obtained near the end. As Ohad Shamir et al. demonstrated in Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes, retaining too much influence from poor initial estimates makes uniform averaging sub-optimal in non-smooth settings. It forces an artificial $O(\log T / T)$ penalty in convergence bounds for strongly convex optimization, missing the optimal minimax rate.

To resolve this, a powerful paradigm has emerged: non-uniform, recency-weighted iterate averaging. By systematically shifting weight toward more recent iterations, optimization algorithms can rapidly forget poor initial conditions while preserving the variance-reduction benefits of smoothing.


The Intuition: Forgetting the Past to Smooth the Present

The core mechanism of non-uniform iterate averaging is straightforward. Instead of assigning a constant weight to every iterate, we scale the importance of each iterate by a time-dependent weight $w_t$ that increases as optimization progresses:

$$\bar{\theta}_T = \frac{\sum_{t=1}^T w_t \theta_t}{\sum_{t=1}^T w_t}$$

By choosing a sequence where $w_t$ grows over time, the final solution is dominated by the most refined states of the model. As noted by Zhihan Zhu et al. in Convergence rate of projected subgradient method with time-varying step-sizes, this representational strategy prioritizes later, more accurate points while still incorporating historical information to stabilize the solution.

This simple shift fundamentally alters how an optimizer handles its initial bias. Aditya Vardhan Varre et al. showed in Accelerated SGD for Non-Strongly-Convex Least Squares that assigning higher importance to more recent iterates allows the optimizer to forget initial conditions much faster than standard uniform averaging while maintaining statistical optimality. In the finite-sample regime, this allows the algorithm to discard the influence of early, inaccurate guesses more rapidly, significantly boosting empirical performance (Kobi Cohen et al. in On Projected Stochastic Gradient Descent Algorithm with Weighted Averaging for Least Squares Regression).


Breaking the Logarithmic Barrier

The theoretical value of recency weighting becomes clear when looking at strongly convex objectives. When using uniform averaging, the lingering bias of early iterations causes a logarithmic overhead, slowing the convergence rate down to $O(\log T / T)$. Non-uniform weighting completely eliminates this penalty.

Uniform Weighting:   [w_1] == [w_2] == [w_3] == ... == [w_T]  --> Retains early bias, O(log T / T)
Linear Weighting:    [w_1] <  [w_2] <  [w_3] <  ... <  [w_T]  --> Forgets early bias, O(1/T)

Several distinct frameworks utilize this property to achieve optimal convergence rates:


Accelerating Games and Saddle-Point Problems

The utility of recency weighting extends far beyond standard minimization. In min-max saddle-point problems—such as training Generative Adversarial Networks (GANs) or computing Nash equilibria in large games—algorithms are highly prone to destructive oscillations. Here, non-uniform averaging acts as a powerful stabilizing force.

In solving Heads-Up Limit Texas Hold'em, the CFR+ algorithm introduced by Oskari Tammelin et al. (Solving Heads-Up Limit Texas Hold'em) applied linearly increasing weights to later iterations. This prioritized refined, recent strategies over early, unoptimized ones, drastically accelerating convergence toward equilibrium.

To push this further, the authors of Solving Imperfect-Information Games via Discounted Regret Minimization introduced quadratic strategy averaging, where weights grow quadratically ($w_t \propto t^2$). This aggressive non-linear weighting scheme places extreme emphasis on the most recent estimates, allowing iterative solvers to effectively "discount" early mistakes and converge significantly faster than linear alternatives.

Christian Kroer et al. formalized this behavior in Increasing Iterate Averaging for Solving Saddle-Point Problems, proving that polynomially increasing weights maintain the optimal theoretical $O(1/T)$ convergence rate while significantly reducing the practical influence of early, noisy steps.


Universality Across the Optimization Landscape

The core principle—that recent states contain more accurate local geometry and should be prioritized—manifests across several other domains:

Ultimately, non-uniform iterate averaging bridges the gap between the stability of averaging and the accuracy of the latest updates. By treating the history of optimization not as a uniform block, but as a sequence of increasing refinement, it allows algorithms to extract the maximum possible utility from their trajectory.

Key Foundational Work

Dual Averaging Method for Regularized Stochastic Learning and Online Optimization (2009) — contributed 1 concept elements to this direction.
Online Classification for Complex Problems Using Simultaneous Projections (2006) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_weighted_iterate_averaging_2f2d7544,
  title = {weighted iterate averaging},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/weighted-iterate-averaging/rdr_2f2d75444b864efc89b364160ba459c1},
  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_weighted_iterate_averaging_2f2d7544_v1,
  title = {weighted iterate averaging},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/weighted-iterate-averaging/rdr_2f2d75444b864efc89b364160ba459c1/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake