Adaptive Methods and Variance Reduction

AdaGrad, RMSProp, Adam and AdamW derived from their design goals, plus SVRG and SAGA and what each one actually guarantees.

SGDGraduate⏱ 3 hours13 min readadagradrmspropadamadamwweight decay

5 problems →

AssumesSGD — Convergence Under Every Standard Assumption

Two distinct ideas are often conflated. Adaptive methods rescale the step per coordinate using observed gradient magnitudes; they change the geometry but not the noise. Variance reduction constructs a lower-variance gradient estimator; it changes the noise but not the geometry. They address different terms in the SGD bound, and they have very different theoretical status.

AdaGrad

DefinitionAdaGrad

With $G_t = \sum_{s\le t} g_s\odot g_s$ accumulated coordinatewise,

x_{t+1,i} = x_{t,i} - \frac{\eta}{\sqrt{G_{t,i}}+\epsilon}\,g_{t,i}.

TheoremAdaGrad regret bound

Let $f_1,\dots,f_T$ be convex with subgradients $g_t \in \partial f_t(x_t)$ , and suppose $\norm{x_t - x^\star}_\infty \le D_\infty$ for all $t$ . Then AdaGrad with $\eta = D_\infty/\sqrt2$ satisfies

\sum_{t=1}^T\big(f_t(x_t)-f_t(x^\star)\big) \le \sqrt2\,D_\infty\sum_{i=1}^d\sqrt{\sum_{t=1}^Tg_{t,i}^2}.

Key idea

The bound involves $\sum_i\sqrt{\sum_t g_{t,i}^2}$ , not $\sqrt{d\sum_{t}\norm{g_t}_2^2}$ . For sparse gradients — most coordinates zero most of the time, as in bag-of-words features or embedding layers — the former is far smaller. That is what AdaGrad was designed for and what it provably delivers. The dense case gives no improvement over tuned SGD, and AdaGrad's monotonically growing $G_t$ makes the effective step decay like $1/\sqrt t$ whether or not that is appropriate — which is the motivation for the exponential averaging in RMSProp and Adam.

RMSProp and Adam

DefinitionAdam

With $\beta_1 = 0.9$ , $\beta_2 = 0.999$ typically,

\begin{aligned} m_t &= \beta_1 m_{t-1} + (1-\beta_1)g_t, &\qquad \hat m_t &= \frac{m_t}{1-\beta_1^t},\\ v_t &= \beta_2 v_{t-1} + (1-\beta_2)\,g_t\odot g_t, &\qquad \hat v_t &= \frac{v_t}{1-\beta_2^t},\\ x_{t+1} &= x_t - \eta\,\frac{\hat m_t}{\sqrt{\hat v_t}+\epsilon}. && \end{aligned}

RMSProp is Adam with $\beta_1 = 0$ and no bias correction.

Why the bias correction is what it is

$m_t = (1-\beta_1)\sum_{s=1}^t \beta_1^{t-s}g_s .$
Unroll the exponential moving average from m_0 = 0.
$\E m_t = (1-\beta_1)\,\E g\sum_{s=1}^t\beta_1^{t-s} = \E g\,\big(1-\beta_1^t\big).$
Take expectations assuming the gradient distribution is stationary with mean g.
$\E \hat m_t = \E g$ . The same computation gives $\E\hat v_t = \E[g\odot g]$ .
The estimator is biased towards zero by exactly the factor (1 − β₁ᵗ), so dividing by it removes the bias.
$1-\beta_2^t \to 1$ geometrically, so the correction is negligible after a few thousand steps.
The correction matters only early: at t = 1 with β₂ = 0.999 the uncorrected v₁ is a thousand times too small, so the uncorrected step would be about thirty times too large.

TheoremAdam can fail to converge

There is a sequence of convex functions $f_t$ with bounded gradients on a bounded convex domain, and a choice of $\beta_1,\beta_2$ satisfying the conditions stated in the original Adam paper, for which Adam's average regret does not tend to zero.

Quoted from Reddi, Kale and Kumar. The counterexample is a one-dimensional problem where a large informative gradient arrives every third step and small misleading gradients arrive in between; the exponential average $v_t$ forgets the large gradient before it can be acted on, so the effective step in the informative direction is persistently too small. The proposed fix, AMSGrad, replaces $v_t$ with a running maximum, restoring the monotonicity that AdaGrad had and Adam gave up.

What this does not say

The theorem does not say Adam does not work. It says the convergence proof in the original paper is wrong, and that no such proof can exist under those hypotheses. Adam works extremely well on the problems it is used for; AMSGrad, which has a proof, is not noticeably better in practice. The honest statement is that Adam's empirical success is not currently explained by a convergence theorem, and convergence guarantees for it exist only under additional assumptions (bounded gradients plus $\beta_1 < \sqrt{\beta_2}$ , or a decaying $\beta_2$ schedule).

AdamW: why decoupling matters

PropositionL2 regularisation and weight decay differ under adaptive preconditioning

Consider adding $\lambda x$ to the gradient (L2 regularisation) versus subtracting $\eta\lambda x$ from the update (weight decay). Under SGD the two coincide. Under a diagonal preconditioner $P_t$ they do not: the first gives

x_{t+1} = x_t - \eta P_t\big(g_t + \lambda x_t\big),

the second gives

x_{t+1} = x_t - \eta P_t g_t - \eta\lambda x_t .

The effective shrinkage in the first is $\eta\lambda P_t$ , which varies by coordinate.

Key idea

Under Adam, $P_{t,ii} = 1/(\sqrt{\hat v_{t,i}}+\epsilon)$ , so L2 regularisation applies weaker shrinkage to coordinates with large gradient variance — the opposite of what a regulariser is supposed to do, since those are exactly the parameters most at risk of overfitting noise. Decoupling the decay (AdamW) makes the shrinkage uniform and, empirically, substantially improves generalisation. This is a case where a purely mathematical observation about operator ordering had a large practical effect, and it is worth keeping as a reminder that " $L_2$ penalty" and "weight decay" are only synonyms for unpreconditioned methods.

Variance reduction

The noise floor $\eta\sigma^2/\mu$ comes from $\sigma^2>0$ . For a finite sum $f = \frac1n\sum_i f_i$ the variance can be reduced to zero at the optimum, using a control variate.

Algorithm — SVRG (stochastic variance reduced gradient)

Outer loop. At epoch $s$ , set the snapshot $\tilde x = x^{(s)}$ and compute the full gradient $\tilde\mu = \nabla f(\tilde x)$ once, at cost $n$ .
Inner loop. For $k = 1,\dots,m$ : sample $i$ uniformly and take $x_{k+1} = x_k - \eta\big(\nabla f_i(x_k) - \nabla f_i(\tilde x) + \tilde\mu\big).$
Restart. Set $x^{(s+1)}$ to (an average of) the inner iterates and repeat.

PropositionThe SVRG estimator is unbiased with vanishing variance

The inner-loop direction is unbiased, and its variance is bounded by

\E\norm{\nabla f_i(x_k)-\nabla f_i(\tilde x)+\tilde\mu - \nabla f(x_k)}_2^2 \le 2L^2\left(\norm{x_k - x^\star}_2^2 + \norm{\tilde x - x^\star}_2^2\right),

so it tends to zero as both the iterate and the snapshot approach $x^\star$ .

TheoremSVRG attains a linear rate on finite sums

For $\mu$ -strongly convex $f$ with each $f_i$ being $L$ -smooth, SVRG with suitable $\eta$ and $m = \Theta(L/\mu)$ satisfies $\E\big[f(x^{(s)})-f^\star\big]\le \rho^s\big(f(x^{(0)})-f^\star\big)$ for some $\rho<1$ , at a total gradient cost of $O\big((n + L/\mu)\log(1/\eps)\big)$ .

Quoted from Johnson and Zhang. Compare the alternatives for the same problem: full gradient descent costs $O(n\kappa\log(1/\eps))$ and SGD costs $O(1/(\mu\eps))$ . SVRG's $O((n+\kappa)\log(1/\eps))$ beats both — an additive rather than multiplicative dependence on $n$ and $\kappa$ . SAGA achieves the same with a gradient table instead of periodic full passes.

Empirical observationVariance reduction does not help deep learning in practice

Empirical observation — a regularity seen in experiments. No theorem on this page establishes it in general.

Despite the clean theory, SVRG and SAGA have not produced wall-clock improvements on large neural networks, and are not used.

What this does not say

Defazio and Bottou investigated this directly and identified several reasons, none of which is a flaw in the theorems:

Data augmentation makes the objective not a finite sum — each "example" is a distribution, so there is no fixed $\nabla f_i$ to snapshot.
Batch normalisation and dropout make $\nabla f_i$ depend on the rest of the batch and on fresh randomness, again breaking the finite-sum structure.
The snapshot goes stale fast. The theory assumes $\norm{x_k-\tilde x}_2$ stays small; in deep learning the iterate moves far within an epoch, so the control variate has little correlation with the gradient it is correcting and the variance reduction largely evaporates.
Memory. SAGA's gradient table is $O(nd)$ , which is impossible at scale.

This is a good example of a gap between theory and practice where the theory is correct and the hypotheses are what fail. Identifying which hypothesis fails is more useful than concluding that theory does not apply.

Problems

The AdaGrad summation inequalityProof · Advanced · 30 min Derive Adam's bias correctionProof · Beginner · 15 min Why AdamW differs from Adam with L2Proof · Intermediate · 30 min The SVRG control variateProof · Advanced · 1 hour

References

PaperJohn Duchi, Elad Hazan and Yoram Singer (2011). Adaptive subgradient methods for online learning and stochastic optimizationAdaGrad.
PaperDiederik P. Kingma and Jimmy Ba (2015). Adam: A Method for Stochastic Optimization
PaperSashank J. Reddi, Satyen Kale and Sanjiv Kumar (2018). On the Convergence of Adam and BeyondThe non-convergence counterexample and AMSGrad.
PaperIlya Loshchilov and Frank Hutter (2019). Decoupled Weight Decay RegularizationAdamW.
PaperRie Johnson and Tong Zhang (2013). Accelerating stochastic gradient descent using predictive variance reductionSVRG.
PaperAaron Defazio and Léon Bottou (2019). On the Ineffectiveness of Variance Reduced Optimization for Deep Learning

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

TheoremAdaGrad regret boundproof includedAdaGrad attains a regret bound that adapts to the observed gradient scale per coordinate.
DefinitionAdamExponential moving averages of the gradient and its square, with bias correction.
TheoremAdam can fail to convergeThere is a convex online problem on which Adam with standard parameters has non-vanishing average regret.
PropositionL2 regularisation and weight decay differ under adaptive preconditioningproof includedAdding lambda times the weight to the gradient is not the same as shrinking the weight, once the update is rescaled per coordinate.
TheoremSVRG attains a linear rate on finite sumsVariance reduction removes the noise floor entirely for strongly convex finite-sum problems.
Empirical observationVariance reduction does not help deep learning in practiceThe methods that provably remove the noise floor for finite sums have not produced wall-clock gains on large neural networks.

Problems (5)

All problems

Papers that use this mathematics

Adam: A Method for Stochastic Optimization
Diederik P. Kingma, Jimmy Ba · 2015