variance-reduced SGD

A stochastic gradient computed from one example or mini-batch is a noisy estimate of the true gradient, and that noise never vanishes even at the optimum. So plain SGD with a fixed step size only settles into a 'noise ball' around the minimum, forcing a decaying learning rate and a slow convergence rate of order one over t. Variance reduction asks: can we cancel most of that noise and recover the fast linear convergence that full-batch gradient descent enjoys on a finite sum of functions?

SVRG does it with a stale anchor. It periodically computes the exact full gradient at a snapshot point w-hat, then uses the corrected estimate grad f_i(w) minus grad f_i(w-hat) plus the full gradient at w-hat. This estimate is still unbiased, but its variance shrinks to zero as the iterates approach the optimum, because the per-example term and its snapshot counterpart nearly cancel. SAGA achieves the same end differently, by storing and incrementally updating a table of the most recent gradient for every sample.

For strongly convex finite-sum problems these methods provably converge linearly, a beautiful result that makes them excellent on convex machine-learning objectives. In deep networks the advantage largely evaporates: non-convex landscapes, data augmentation, enormous dataset sizes, and the fact that the snapshot keeps moving all conspire against it, so in practice plain SGD or Adam usually win on neural nets.