Variance Reduction for Faster Stochastic Optimization

This direction is split into other directions: stochastic-deterministic efficiency tradeoff. Its last version stays readable and citable here.

Version 1 of 1133 papers137 conceptsfrozen 2026-10-04

In large-scale machine learning, we typically face a frustrating choice between two extremes. On one hand, Full Gradient (FG) methods are precise; they use the entire dataset to calculate a perfect descent direction, leading to fast, linear convergence. However, as Mark Schmidt and Nicolas Le Roux note in Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition, processing millions of examples for a single update is computationally ruinous.

On the other hand, Stochastic Gradient Descent (SGD) is incredibly cheap. It picks one random example and moves. While this allows for rapid initial progress, the "noise" from that single sample means the algorithm eventually starts wandering aimlessly around the optimum. To actually converge, SGD must slowly shrink its step size to zero, which drags its convergence rate down to a sluggish sublinear speed ($O(1/k)$).

The research direction of Variance Reduction (VR) seeks to break this trade-off, achieving the "best of both worlds": the low per-iteration cost of SGD with the rapid linear convergence of FG methods.

The Intuition: Why SGD is Slow

The fundamental bottleneck in SGD is variance. Because a single random gradient is only a rough approximation of the true gradient, the updates are "noisy." If you keep your step size constant, this noise prevents you from ever reaching the exact minimum; you simply bounce around in a "neighborhood" of the solution.

To fix this, traditional SGD forces the step size to decay. But a decaying step size is like a runner who slows down the closer they get to the finish line—they will eventually finish, but it takes forever. Variance reduction allows us to keep the step size large and constant by systematically "cleaning" the noise out of the stochastic updates.

The Mechanism: Memory and Anchoring

How do you reduce noise without looking at the whole dataset every time? The core insight, pioneered by methods like Stochastic Average Gradient (SAG) in A Stochastic Gradient Method with an Exponential Convergence Rate, is to use memory.

Instead of throwing away the gradient information from previous iterations, VR methods store it. When you sample a new data point, you don't just use its current gradient; you use it to update an estimate of the average gradient.

There are two primary ways this is implemented:

  1. Running Averages (SAG/SAGA): You keep a table of the last seen gradient for every single data point. When you pick point $i$, you replace its old gradient in the table with the new one. As Aaron Defazio demonstrates with SAGA in New Optimisation Methods for Machine Learning, this allows the algorithm to support non-smooth regularizers while maintaining high-accuracy convergence.
  2. Periodic Anchoring (SVRG): Instead of a massive table, you occasionally compute a "full" gradient (an anchor) and then use small stochastic steps to estimate how the gradient has changed since that anchor. This approach, discussed by Clarice Poon and Jingwei Liang in Local Convergence Properties of SAGA/Prox-SVRG, is often more memory-efficient for very large models.

Why it Works: The Vanishing Error

In standard SGD, the difference between your random sample and the true gradient stays roughly constant. In VR methods, as you approach the optimum, the "error" in your stochastic estimate actually shrinks to zero.

Because the variance vanishes, you can maintain a constant step size. This is the mathematical engine that drives the jump from sublinear to linear (exponential) convergence. As Alekh Agarwal explores in A Lower Bound for the Optimization of Finite Sums, these hybrid methods are essentially the theoretical limit for how fast we can optimize finite datasets.

Expanding the Toolkit

The success of variance reduction has triggered a wave of "stochastic versions" of classic deterministic algorithms:

By treating the "noise" of stochastic sampling as a quantity that can be managed and reduced through memory, this research direction has redefined the boundaries of what is computationally possible in large-scale machine learning.

Papers in this version

Showing 60 of 133 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_variance_reduction_for_faster_stochastic_c0c33747,
  title = {Variance Reduction for Faster Stochastic Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/variance-reduction-for-faster-stochastic-optimization/rdr_c0c33747bc4e41efac98dba499d828cb},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_variance_reduction_for_faster_stochastic_c0c33747_v1,
  title = {Variance Reduction for Faster Stochastic Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/variance-reduction-for-faster-stochastic-optimization/rdr_c0c33747bc4e41efac98dba499d828cb/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}