When optimizing machine learning models using Stochastic Gradient Descent (SGD), the error in our parameters at any given time can be split into two distinct components: bias and variance. Bias represents the distance from our current expected position to the true optimum, heavily influenced by our initial starting guess. Variance represents the statistical noise introduced by sampling mini-batches instead of computing the full gradient over the entire dataset.
To combat variance, a classic and powerful technique is iterate averaging (Polyak-Ruppert averaging), which takes a simple uniform average of all parameter vectors computed across training. While uniform averaging is highly effective at smoothing out stochastic noise, it introduces a severe structural bottleneck: it suffers from a slow, polynomial decay of the initial bias. As noted by Prateek Jain et al. in Parallelizing Stochastic Gradient Descent for Least Squares Regression: Mini-batching, Averaging, and Model Misspecification. and Aditya Vardhan Varre et al. in Accelerated SGD for Non-Strongly-Convex Least Squares, this slow rate of forgetting the initial starting point prevents algorithms from quickly reaching high-precision solutions, especially in non-smooth or non-strongly-convex settings.
The Performance Drag of Early Iterates
To understand why uniform averaging fails, consider what happens when we compute a uniform average:
$$\bar{x}_T = \frac{1}{T}\sum_{t=1}^T x_t$$
In the early stages of optimization, the iterates $x_t$ are far from the optimal solution $x^*$ and carry massive initialization errors. Because every single iterate receives an identical weight of $1/T$, these highly inaccurate initial guesses permanently pollute the average.
As Alexander Rakhlin et al. demonstrate in Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization, this equal treatment creates a logarithmic bottleneck in convergence rates for non-smooth problems. Instead of allowing the model to rapidly forget its poor initialization, uniform averaging forces the initial error to persist for an extended period, leading to a sublinear decay of bias.
Christian Kroer et al. highlight a similar failure mode in Increasing Iterate Averaging for Solving Saddle-Point Problems, noting that the poor quality of early steps permanently degrades the calculated solution, failing to reflect the higher precision achieved in later iterations. The fundamental challenge, as framed by Rong Ge et al. in Competing with the Empirical Risk Minimizer in a Single Pass., is designing streaming algorithms that can achieve a super-polynomial rate of forgetting this initial error.
Uniform Averaging:
[ x0 (High Error) ] -> Weight: 1/T \
[ x1 (High Error) ] -> Weight: 1/T --> All iterates anchor the final estimate
[ xT (Low Error) ] -> Weight: 1/T /
Tail Averaging:
[ x0 (High Error) ] -> DISCARDED
[ x1 (High Error) ] -> DISCARDED
[ xT (Low Error) ] -> Averaged only within the final suffix window
Suffix and Tail Averaging
The most direct way to prevent early iterates from dragging down performance is to simply throw them away. Instead of averaging from the very first time step, we can average only a suffix or tail of the optimization trajectory.
Alexander Rakhlin et al. showed that by averaging only the last fraction of iterations (e.g., the final $T/2$ steps), one can completely bypass the logarithmic bottleneck and recover the theoretically optimal $O(1/T)$ convergence rate for strongly convex stochastic optimization.
This insight spans multiple domains:
- Nonparametric Optimization: Nicole Muecke et al. in Beating SGD Saturation with Tail-Averaging and Minibatching demonstrate that tail-averaging allows SGD to beat the "saturation" effect, enabling the use of more aggressive step-sizes without retaining the persistent bias of low-quality early estimates.
- Reinforcement Learning: Gandharv Patil et al. in Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisation apply tail-averaging to Temporal Difference (TD) learning, proving it achieves an optimal convergence rate while remaining robust to ill-conditioned features.
- High-Dimensional Sparse Regression: Jianqing Fan et al. in Statistical Sparse Online Regression: A Diffusion Approximation Perspective utilize a delayed trajectory averaging scheme to avoid degrading the final statistical accuracy with the initial descent trajectory.
Non-Uniform and Weighted Averaging
While tail-averaging works well, it requires choosing a discrete window or knowing the total number of iterations $T$ in advance. A more flexible alternative is to apply non-uniform weights that systematically discount early iterates on the fly.
Ohad Shamir et al. in Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes introduced polynomial-decay averaging, where the weight of iterate $t$ is proportional to $t^\eta$ for a hyperparameter $\eta > 0$. This ensures that later, more accurate iterates dominate the average, achieving optimal convergence rates without needing to know the horizon $T$ beforehand. Similarly, Kobi Cohen et al. in On Projected Stochastic Gradient Descent Algorithm with Weighted Averaging for Least Squares Regression explore weighted averaging to prevent early updates from slowing down the critical early stages of learning.
Taking this to its logical conclusion, Quanquan Gu et al. in Understanding SGD with Exponential Moving Average: A Case Study in Linear Regression analyzed SGD with an Exponential Moving Average (EMA). They proved that EMA uniquely bridges the gap between standard SGD and uniform averaging: it retains the lightning-fast, exponential bias convergence of standard SGD while simultaneously capturing the robust variance reduction benefits of iterate averaging.
Scheduled Restarts and Bias Correction
Beyond modifying the averaging weights, researchers have developed structural algorithmic wrappers to actively flush out initial iterate bias.
One approach is to periodically reset the averaging process entirely. Chris Junchi Li et al. in On the Convergence of Stochastic Extragradient for Bilinear Games using Restarted Iteration Averaging utilize a restarted iteration averaging strategy for stochastic extragradient methods in bilinear games. By scheduling restarts, the algorithm systematically discards the influence of older, high-error states, transforming an algorithm that would otherwise merely "orbit" the solution into one that converges optimally to the Nash equilibrium.
Restarted Averaging Timeline:
|--- Average Window 1 ---| Reset |--- Average Window 2 ---| Reset |--- Final Window ---|
^ Initial Bias Flushed ^ Early Window 1 Flushed ^ High Precision
Alternatively, one can explicitly calculate and subtract the asymptotic bias. Sebastian Allmeier et al. in Computing the Bias of Constant-step Stochastic Approximation with Markovian Noise show that while time-averaging suppresses variance, it leaves a predictable bias proportional to the learning rate. They introduce an extrapolation trick to cancel this bias out entirely.
For higher-order algorithms where slow bias decay causes catastrophic error accumulation, Hilal Asi et al. in Stochastic Bias-Reduced Gradient Methods leverage Multilevel Monte Carlo (MLMC) techniques to construct nearly unbiased estimators of the minimizer, achieving extremely low bias with minimal computational overhead.
Ultimately, managing the transition from forgetting the initial starting point to reaching the noise floor—as detailed by Alexandre Défossez et al. in Averaged Least-Mean-Squares: Bias-Variance Trade-offs and Optimal Sampling Distributions and Prateek Jain et al. in Accelerating Stochastic Gradient Descent for Least Squares Regression.—requires moving away from uniform treatment of history. Whether through hard truncation (tail-averaging), soft discounting (EMA and polynomial decay), or periodic resets (restarting), breaking the uniform averaging limitation is essential for optimal stochastic optimization.
Key Foundational Work
Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes (2013) — contributed 1 concept elements to this direction.
Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization (2012) — contributed 1 concept elements to this direction.