Variance Reduction in Stochastic Optimization

786 concepts503 papers1 proposal

When optimizing a finite-sum objective function of the form $F(x) = \frac{1}{n} \sum_{i=1}^n f_i(x)$, machine learning practitioners face a classic dilemma. Full Gradient Descent (GD) computes the exact gradient by evaluating all $n$ functions, yielding stable, linear convergence but at an exorbitant per-iteration cost. Stochastic Gradient Descent (SGD) radically slashes this cost by sampling a single index $i$ and using $\nabla f_i(x)$ as an unbiased estimate of the true gradient.

However, this efficiency comes at a price: variance. Because individual sample gradients deviate from the true average gradient, SGD introduces stochastic noise into the optimization trajectory. As the iterates approach the true optimum $x^*$, the individual gradients $\nabla f_i(x^*)$ do not vanish; they continue to push the parameters erratically. To prevent the algorithm from bouncing around the optimum indefinitely, SGD must employ a decaying step size. This forced deceleration drops its convergence rate from linear to sublinear, creating a fundamental "noise floor" that slows down training.

The Core Intuition: Gradient Correction via Control Variates

Stochastic variance reduction breaks this bottleneck by changing how the gradient estimator behaves near the optimum. Instead of letting the variance remain constant throughout training, variance-reduced methods construct an estimator whose variance vanishes as the algorithm converges.

To understand how, consider the classic statistical technique of control variates. Suppose we want to estimate the value of a noisy random variable $X$, and we have access to another correlated random variable $Y$ whose exact expectation $\mathbb{E}[Y]$ is known. We can construct a modified estimator $\theta$:

$$ \theta = X - Y + \mathbb{E}[Y] $$

By linearity of expectation, $\mathbb{E}[\theta] = \mathbb{E}[X]$, meaning the estimator remains unbiased. Crucially, if $X$ and $Y$ are highly correlated, the variance of $\theta$ can be substantially lower than the variance of $X$ alone because the tracking errors cancel each other out.

In optimization, we apply this trick by anchoring our stochastic updates to a reference point $\tilde{x}$ where a full gradient $\nabla F(\tilde{x})$ is known or tracked. When we sample a function $f_i$ at our current iterate $x$, we replace the standard stochastic gradient $\nabla f_i(x)$ with a corrected version:

$$ g_i(x) = \nabla f_i(x) - \nabla f_i(\tilde{x}) + \nabla F(\tilde{x}) $$

This formulation works beautifully for two reasons:

  1. Unbiasedness: Since $\mathbb{E}_i[\nabla f_i(x)] = \nabla F(x)$ and $\mathbb{E}_i[\nabla f_i(\tilde{x})] = \nabla F(\tilde{x})$, the expectation of $g_i(x)$ is exactly the true gradient $\nabla F(x)$.
  2. Vanishing Variance: As the algorithm converges and $x$ approaches $\tilde{x}$, the difference $\nabla f_i(x) - \nabla f_i(\tilde{x})$ shrinks to zero for every single sample $i$. Consequently, the variance of the estimator $g_i(x)$ drops to zero as the parameters reach the optimum.

Because the noise vanishes near the optimum, we no longer need to decay the learning rate. We can maintain a large, constant step size, unlocking the fast linear convergence rates of batch gradient descent at the low per-iteration cost of stochastic methods.

Two Paradigms: Snapshots vs. Memory Tables

The literature generally splits into two operational strategies for maintaining the reference point $\tilde{x}$ and its corresponding full gradient.

Snapshot-Based Correction

In this paradigm, optimization is divided into outer epochs and inner loops. At the start of each epoch, the algorithm takes a "snapshot" of the current parameters $\tilde{x}$ and computes a complete, exact full gradient $\nabla F(\tilde{x})$. During the subsequent inner loop, updates are corrected using this fixed anchor.

As explored by Atsushi Nitanda in Stochastic Proximal Gradient Descent with Acceleration Techniques, this periodic full-gradient adjustment ensures that the variance remains bounded. This bounding mechanism stabilizes progress and allows for larger step sizes without requiring massive memory overhead, though it does require periodic full passes over the dataset.

Memory-Based Tracking

Instead of periodically pausing to compute a full gradient, memory-based approaches maintain a running table of the most recently computed gradients for all $n$ components. In each step, when a function $f_i$ is sampled, its entry in the table is updated, and the average of this table serves as the proxy for the full gradient.

As shown by Alberto Bietti et al. in Stochastic Optimization with Variance Reduction for Infinite Datasets with Finite Sum Structure, aggregating these stored gradient surrogates stabilizes the optimization trajectory. This eliminates the discrete sampling noise entirely, leaving only the continuous stochasticity of the problem itself and avoiding the need for periodic full-batch computations.

Breaking the Noise Floor

By systematically lowering the noise floor, variance reduction acts as an enabling technology that unlocks advanced optimization techniques previously incompatible with stochastic noise.

For instance, standard stochastic gradients eventually hit a noise ceiling that prevents sequence extrapolation techniques from working. However, Damien Scieur et al. demonstrate in Nonlinear Acceleration of Stochastic Algorithms that combining sequence extrapolation with variance reduction allows acceleration mechanisms to persist continuously, offering massive speedups on ill-conditioned problems.

Similarly, variance reduction expands the reach of non-Euclidean optimization. In Fast Stochastic Bregman Gradient Methods: Sharp Analysis and Variance Reduction, the authors show that maintaining a historical memory of past gradients within a Bregman divergence framework allows stochastic methods to achieve linear convergence to exact minimizers, matching the precision of specialized solvers in complex geometric settings.

Finally, this anchoring mechanism proves vital when dealing with multi-layered stochasticity. In latent variable models, optimization suffers from a "double noise" problem due to the simultaneous sampling of both data points and hidden variables. As shown by Guanhua Fang et al. in On Estimation in Latent Variable Models, using gradient snapshots to anchor updates successfully neutralizes both noise sources, guaranteeing that the variance vanishes completely as the parameters approach the optimum.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

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

Latest version (a living page):

@misc{lacuna_stochastic_variance_reduction_variance_r_0d3b12de,
  title = {stochastic variance reduction (variance-reduced stochastic optimization)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/stochastic-variance-reduction-variance-reduced-stochastic-optimization/rdr_0d3b12decf2b439bbf398c23df9dbde7},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 2, frozen text):

@misc{lacuna_stochastic_variance_reduction_variance_r_0d3b12de_v2,
  title = {stochastic variance reduction (variance-reduced stochastic optimization)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/stochastic-variance-reduction-variance-reduced-stochastic-optimization/rdr_0d3b12decf2b439bbf398c23df9dbde7/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake