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:
- 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.
- 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:
- Dual Methods: Shai Shalev-Shwartz and Tong Zhang introduced Prox-SDCA in Proximal Stochastic Dual Coordinate Ascent, showing that optimizing one random coordinate in the dual space can also achieve linear convergence.
- Acceleration: Researchers like Yuanyuan Liu and James Cheng have combined VR with Nesterov-style momentum in Accelerated Variance Reduced Stochastic ADMM to speed up convergence even further.
- Bayesian Inference: The principle has even moved beyond optimization. Max Welling and Yee Whye Teh utilized similar stochastic logic in Stochastic Gradient Langevin Dynamics to scale Bayesian posterior sampling to massive datasets.
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.