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:
- Linear and Polynomial Weighting: The authors of Towards an optimal stochastic alternating direction method of multipliers proved that prioritizing recent iterates through linear weighting ($w_t \propto t$) effectively manages late-stage stochastic noise, yielding a minimax optimal $O(1/k)$ rate for strongly convex objectives. Similarly, in primal-dual frameworks, Tianyi Lin et al. (Stochastic Primal-Dual Proximal ExtraGradient descent for compositely regularized optimization) and Linbo Qiao et al. (On the Iteration Complexity Analysis of Stochastic Primal-Dual Hybrid Gradient Approach with High Probability) demonstrated that transitioning from uniform to non-uniform averaging eliminates the logarithmic penalty, accelerating the convergence rate from $O(\log t / t)$ to a clean $O(1/t)$.
- Inverse Step-Size Weighting: In practice, optimization schedules often decay the learning rate over time. Xiaoyu Wang et al. showed in On the Convergence of Step Decay Step-Size for Stochastic Optimization that weighting later iterates proportionally to the inverse of the step-size ($w_t \propto 1/\eta_t$) removes logarithmic factors in convergence bounds. This analytical framework better aligns theory with the practical observation that model quality improves dramatically during step-decay phases.
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:
- Second-Order Curvature: In stochastic Newton methods, maintaining a running average of past noisy Hessian estimates helps denoise second-order information. Sen Na et al. (Hessian averaging in stochastic Newton methods achieves superlinear convergence) and Ruichen Jiang et al. (Stochastic Newton Proximal Extragradient Method) demonstrated that non-uniformly weighting historical curvature data accelerates adaptation to local function geometry, facilitating a faster transition to superlinear convergence.
- Gradient Acceleration: Rather than weighting the iterates themselves, Kimon Antonakopoulos et al. showed in UnderGrad: A Universal Black-Box Optimization Method with Almost Dimension-Free Convergence Rate Guarantees that applying an increasing weight scheme directly to gradients achieves accelerated convergence rates in smooth optimization, proving that recency-weighted gradient information is a core driver of acceleration.
- Variance Reduction: In Almost Tune-Free Variance Reduction, Bingcong Li utilized an estimate sequence framework to derive weighted averages for inner-loop iterations. This scheme prioritizes iterations with higher gradient accuracy, outperforming traditional uniform or last-iterate methods.
- Deep Learning Checkpoint Merging: Even in large language model (LLM) pre-training, the principle holds. Qian Zhao introduced a schedule-free training framework in WSM: Decay-Free Learning Rate Schedule via Checkpoint Merging for LLM Pre-training that eliminates the learning rate decay phase by post-hoc checkpoint merging. The author found that concave weighting schemes for merging checkpoints consistently outperform linear or uniform averages, demonstrating that the mathematical shape of how we prioritize recent parameters dictates performance in complex deep learning environments.
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.