Statistical Inference via Averaged Stochastic Approximation

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2200 papers250 conceptsfrozen 2026-10-04

In large-scale machine learning, we often treat Stochastic Gradient Descent (SGD) as a black-box optimizer: we feed it data, and it spits out a parameter estimate. However, for critical applications like medicine or finance, a single point estimate is not enough. We need to know how much to trust that estimate—we need confidence intervals.

The challenge is that the "last iterate" of a stochastic process is notoriously noisy. To solve this, a growing body of research leverages iterate averaging (specifically Polyak-Ruppert averaging) to transform noisy optimization paths into rigorous statistical tools.

The Problem with the Last Iterate

When we run SGD or Temporal Difference (TD) learning, the sequence of parameters $\theta_t$ fluctuates around the optimal solution $\theta^*$ due to the randomness of mini-batches or environment noise. If we stop the algorithm at time $T$, our final estimate $\theta_T$ is essentially a single, noisy snapshot.

As Francis Bach notes in Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression, even if the algorithm is converging, the variance of that last iterate remains high unless we use a vanishingly small learning rate, which slows down progress.

Averaging as a Low-Pass Filter

Polyak-Ruppert averaging suggests a simple fix: instead of using the last iterate $\theta_T$, use the running average of all iterates: $$\bar{\theta}_T = \frac{1}{T} \sum_{t=1}^T \theta_t$$ Intuitively, this acts as a low-pass filter. Since the noise in stochastic updates is typically zero-mean, averaging the trajectory cancels out the high-frequency oscillations, leaving behind a stable estimate.

This isn't just a heuristic for better accuracy. Aleksandr Beznosikov and colleagues in their review of Boris Polyak’s work highlight that this averaging allows stochastic methods to reach the Cramér-Rao bound—the theoretical limit of statistical efficiency. As Panos Toulis and Dustin Tran demonstrate in Towards Stability and Optimality in Stochastic Gradient Descent, combining implicit updates with averaging creates an estimator that is both numerically stable and statistically optimal.

From Optimization to the Central Limit Theorem

The breakthrough for statistical inference comes from the fact that these averaged iterates satisfy a Central Limit Theorem (CLT). Under certain conditions, the distribution of $\sqrt{T}(\bar{\theta}_T - \theta^*)$ converges to a Gaussian distribution.

Xi Chen, Xin T. Tong, and Yichen Zhang show in Statistical Inference for Model Parameters in Stochastic Gradient Descent that we can use this property to build confidence intervals in a single pass. By understanding the asymptotic normality of the averaged path, researchers can estimate the "error bars" of a model without ever needing to look at the full dataset more than once.

In the context of Reinforcement Learning, Yuting Wei and Alexey Naumov have extended these ideas to Temporal Difference learning. They prove that Polyak-Ruppert averaging smooths the Markovian noise inherent in RL, allowing the value function estimates to approach a Gaussian limit reliably.

Real-Time Uncertainty via Online Bootstrapping

While the CLT provides a theoretical foundation, calculating the actual covariance matrix (the "shape" of the uncertainty) in real-time is computationally expensive. Recent work has focused on making this inference "fully online."

  1. The Multiplier Bootstrap: Sergey Samsonov and Eric Moulines have developed "multiplier bootstrap" methods for Linear Stochastic Approximation. By running parallel, perturbed versions of the algorithm, they can simulate the sampling distribution on the fly.
  2. Random Scaling: Sokbae Lee and Yuan Liao introduced a Random Scaling approach. Instead of estimating the complex Hessian matrix, they model the entire trajectory of the averaged estimator as a scaled Wiener process. This allows them to construct test statistics using only the history of the iterates themselves.

Why It Works: The Intuition of Stability

The reason iterate averaging is so powerful for inference is that it decouples the optimization rate from the statistical rate.

In standard SGD, you often need a decaying step size to ensure the iterates don't bounce around forever. But with averaging, you can use a larger, even constant step size. As Jeongyeol Kwon explains in Two-Timescale Linear Stochastic Approximation, the iterates themselves might never settle into a single point—they might converge to a stationary distribution—but their average will converge to the truth with high precision.

By shifting our focus from the "final state" to the "average path," we gain the ability to not only find the best parameters but also to quantify exactly how much data-driven evidence supports them.

Papers in this version

Showing 60 of 200 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 90 papers
  2. Version 1 · 2026-10-04 · 200 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_polyak_ruppert_averaging_d6a068bb,
  title = {Polyak-Ruppert averaging},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/polyak-ruppert-averaging/rdr_d6a068bb69134c36b3bcd67544722efb},
  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_statistical_inference_via_averaged_stoch_d6a068bb_v1,
  title = {Statistical Inference via Averaged Stochastic Approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/statistical-inference-via-averaged-stochastic-approximation/rdr_d6a068bb69134c36b3bcd67544722efb/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}