Simple Algorithm
Artificial Intelligence · Deep Layer · 28 min

Optimizers in Depth

Adam, schedules, warmup and why they work.

Adam's default settings train most networks reasonably well out of the box, yet Adam provably fails to converge on a one-dimensional convex problem, and for years it was suspected of generalizing worse than plain SGD. This lesson proves what SGD guarantees, shows why learning rates must decay, takes Adam apart, and separates what is established from what is still argued.

What you’ll learn

  • State and prove the rate of SGD on smooth nonconvex objectives (Ghadimi & Lan, 2013) and the noise-floor bound under strong convexity, and explain the role of the batch size.
  • Justify decaying schedules and warmup from these bounds and from what is known about curvature early in training.
  • Analyze adaptive methods: bias correction, bounded and scale-invariant steps, sign-descent behavior, and RMSProp's period-2 orbit at a constant step.
  • Reconstruct Reddi, Kale & Kumar's counterexample to Adam's convergence, and assess AMSGrad, decoupled weight decay and the evidence on how adaptive methods generalize.

SGD, precisely

DerivationProof
  1. f(θt+1)≤f(θt)−η ∇f(θt)⊤gt+Lη22∥gt∥2f(\boldsymbol\theta_{t+1})\le f(\boldsymbol\theta_t)-\eta\,\nabla f(\boldsymbol\theta_t)^\top\mathbf g_t+\frac{L\eta^2}2\norm{\mathbf g_t}^2

    The descent lemma (from The Math Toolkit of AI) applied to the step −ηgt-\eta\mathbf g_t:

  2. Ef(θt+1)≤f(θt)−η(1−Lη2)∥∇f(θt)∥2+Lη2σ22\E f(\boldsymbol\theta_{t+1})\le f(\boldsymbol\theta_t)-\eta\Big(1-\frac{L\eta}2\Big)\norm{\nabla f(\boldsymbol\theta_t)}^2+\frac{L\eta^2\sigma^2}2

    Take the expectation over ξt\xi_t given θt\boldsymbol\theta_t. Unbiasedness gives E[gt]=∇f\E[\mathbf g_t]=\nabla f, and the variance bound gives E∥gt∥2≤∥∇f∥2+σ2\E\norm{\mathbf g_t}^2\le\norm{\nabla f}^2+\sigma^2:

  3. η2∑t=0T−1E∥∇f(θt)∥2≤Δ+TLη2σ22\frac\eta2\sum_{t=0}^{T-1}\E\norm{\nabla f(\boldsymbol\theta_t)}^2\le\Delta+\frac{TL\eta^2\sigma^2}2

    For η≤1/L\eta\le1/L the bracket is at least 12\tfrac12. Take full expectations, sum over t=0,…,T−1t=0,\dots,T-1 and telescope, using f(θT)≥f⋆f(\boldsymbol\theta_T)\ge f^\star:

  4. 1T∑t=0T−1E∥∇f(θt)∥2≤2ΔηT+Lησ2\frac1T\sum_{t=0}^{T-1}\E\norm{\nabla f(\boldsymbol\theta_t)}^2\le\frac{2\Delta}{\eta T}+L\eta\sigma^2

    Divide by ηT/2\eta T/2. The first term is optimization, which shrinks with more steps; the second is noise, which shrinks only with a smaller step or a larger batch:

Batch size. With batches of BB the bound reads 2ΔηT+Lησ2B\frac{2\Delta}{\eta T}+\frac{L\eta\sigma^2}{B}. While the noise term dominates, doubling BB and doubling η\eta (as long as η≤1/L\eta\le1/L) halves the number of steps for the same number of examples TBTB: on parallel hardware, large batches are a free speed-up, the linear scaling rule (Goyal et al., 2017). Once the optimization term dominates, larger batches only waste computation. McCandlish et al. (2018) estimated this critical batch size by the gradient noise scale tr⁡Σ/∥∇f∥2\operatorname{tr}\Sigma/\norm{\nabla f}^2, which grows during training as the gradient shrinks.

Noise floors and learning-rate schedules

With strong convexity the picture sharpens: a constant step converges fast, but only to a noise floor proportional to the step.

DerivationSGD with a constant step on a strongly convex function
  1. ∥θt+1−θ⋆∥2=∥θt−θ⋆∥2−2η gt⊤(θt−θ⋆)+η2∥gt∥2\norm{\boldsymbol\theta_{t+1}-\boldsymbol\theta^\star}^2=\norm{\boldsymbol\theta_t-\boldsymbol\theta^\star}^2-2\eta\,\mathbf g_t^\top(\boldsymbol\theta_t-\boldsymbol\theta^\star)+\eta^2\norm{\mathbf g_t}^2

    Let ff be μ\mu-strongly convex and LL-smooth with minimizer θ⋆\boldsymbol\theta^\star, and expand one step:

  2. E∥θt+1−θ⋆∥2≤∥θt−θ⋆∥2−η ∇f(θt)⊤(θt−θ⋆)+η2σ2\E\norm{\boldsymbol\theta_{t+1}-\boldsymbol\theta^\star}^2\le\norm{\boldsymbol\theta_t-\boldsymbol\theta^\star}^2-\eta\,\nabla f(\boldsymbol\theta_t)^\top(\boldsymbol\theta_t-\boldsymbol\theta^\star)+\eta^2\sigma^2

    In expectation, use E∥gt∥2≤∥∇f∥2+σ2\E\norm{\mathbf g_t}^2\le\norm{\nabla f}^2+\sigma^2 and co-coercivity, ∥∇f(θ)∥2≤L ∇f(θ)⊤(θ−θ⋆)\norm{\nabla f(\boldsymbol\theta)}^2\le L\,\nabla f(\boldsymbol\theta)^\top(\boldsymbol\theta-\boldsymbol\theta^\star). For η≤1/L\eta\le1/L:

  3. E∥θt−θ⋆∥2≤(1−ημ)t ∥θ0−θ⋆∥2+ησ2μ\E\norm{\boldsymbol\theta_t-\boldsymbol\theta^\star}^2\le(1-\eta\mu)^t\,\norm{\boldsymbol\theta_0-\boldsymbol\theta^\star}^2+\frac{\eta\sigma^2}{\mu}

    Strong convexity gives ∇f(θ)⊤(θ−θ⋆)≥μ∥θ−θ⋆∥2\nabla f(\boldsymbol\theta)^\top(\boldsymbol\theta-\boldsymbol\theta^\star)\ge\mu\norm{\boldsymbol\theta-\boldsymbol\theta^\star}^2. Unroll the resulting contraction and sum the geometric series of noise terms:

  4. η=1L  (fast, high floor)⟶ηt→0  (slower, no floor)\eta=\tfrac1L\ \ \text{(fast, high floor)}\quad\longrightarrow\quad\eta_t\to0\ \ \text{(slower, no floor)}

    A linear rate down to a floor proportional to η\eta. Halving η\eta halves the floor but also halves the rate, which is what step decay does in stages. Steps ηt=Θ(1/(μt))\eta_t=\Theta(1/(\mu t)) remove the floor and give the optimal O(σ2/(μ2t))\order{\sigma^2/(\mu^2t)}; in general, ∑tηt=∞\sum_t\eta_t=\infty with ∑tηt2<∞\sum_t\eta_t^2<\infty (Robbins & Monro, 1951) ensures convergence.

Deep-learning schedules follow this logic loosely: hold a large step for fast progress, then decay it to settle into a low-loss region, by steps, by a cosine, or with the warmup–stable–decay shape used for some language models, which can extend a run without restarting it. The theory is only a guide, since the losses are nonconvex and the noise is far from isotropic, and a large step does more than add noise: it caps the sharpness of the regions where training can stay (Loss Landscapes & Initialization).

Why warmup? Three mechanisms are documented. (1) Early on, Adam's v^t\hat{\mathbf v}_t averages only tt squared gradients, so its per-coordinate step sizes are high-variance; RAdam corrects for this analytically (Liu et al., 2020). (2) In Post-LN transformers, with layer norm after each residual addition, the gradients near the output are large at initialization, and training without warmup diverges (Xiong et al., 2020); the Pre-LN placement largely removes the need. (3) The loss can be sharper early in training than the peak step tolerates, and warmup lets the network move to flatter regions first (Gilmer et al., 2022).

Adaptive methods, analyzed

AdaGrad (Duchi, Hazan & Singer, 2011) scales coordinate ii by η/∑k≤tgk,i2\eta/\sqrt{\sum_{k\le t}g_{k,i}^2}. Its effective steps only shrink, and for online convex optimization it guarantees O(T)\order{\sqrt T} regret with constants that adapt to the gradients' geometry, far better than SGD's when gradients are sparse. In deep learning its steps shrink too fast; RMSProp replaces the sum by an exponential average, and Adam adds momentum and bias correction.

Write Adam's step as Δθi=−η m^i/(v^i+ε)\Delta\theta_i=-\eta\,\hat m_i/(\sqrt{\hat v_i}+\varepsilon). Kingma and Ba note that ∣Δθi∣≲η\abs{\Delta\theta_i}\lesssim\eta in typical cases and at most η(1−β1)/1−β2≈3.2η\eta(1-\beta_1)/\sqrt{1-\beta_2}\approx3.2\eta for the defaults: η\eta sets the step length per coordinate, much like a trust region. When a coordinate's gradients keep their sign, m^i/v^i→±1\hat m_i/\sqrt{\hat v_i}\to\pm1 and Adam becomes sign descent, Δθ=−η sign⁡(∇f)\Delta\boldsymbol\theta=-\eta\,\sign(\nabla f). When they are mostly noise, ∣m^i∣≪v^i\abs{\hat m_i}\ll\sqrt{\hat v_i} and the steps shrink automatically, like a signal-to-noise ratio.

DerivationProof, and what it means
  1. si←ρ λi2η24+(1−ρ)λi2η24=λi2η24s_i\leftarrow\rho\,\frac{\lambda_i^2\eta^2}4+(1-\rho)\frac{\lambda_i^2\eta^2}4=\frac{\lambda_i^2\eta^2}4

    On the orbit gi=λiθi=±λiη/2g_i=\lambda_i\theta_i=\pm\lambda_i\eta/2, so gi2=λi2η2/4g_i^2=\lambda_i^2\eta^2/4 at every step, and the average stays at that value:

  2. θi−η gisi=±η2−η ±λiη/2λiη/2=∓η2\theta_i-\eta\,\frac{g_i}{\sqrt{s_i}}=\pm\frac\eta2-\eta\,\frac{\pm\lambda_i\eta/2}{\lambda_i\eta/2}=\mp\frac\eta2

    The update divides the gradient by its own magnitude, so each step has length exactly η\eta and maps +η/2+\eta/2 to −η/2-\eta/2 and back:

  3. dist⁡(θt,θ⋆) → η2d(observed; d coordinates)\operatorname{dist}(\boldsymbol\theta_t,\boldsymbol\theta^\star)\ \to\ \frac\eta2\sqrt d\qquad\text{(observed; }d\text{ coordinates)}

    Gradient descent converges on this function for any η<2/max⁡iλi\eta<2/\max_i\lambda_i. RMSProp instead equalizes the coordinates and keeps moving by η\eta. In simulations the orbit attracts the iterates from typical starts: as θi→0\theta_i\to0 the short-memory average sis_i shrinks, the effective step η/si\eta/\sqrt{s_i} grows past the stability limit, and the iterate is pushed back out. Only a decaying η\eta, or a long memory, lets an adaptive method settle.

Predict before you look

Back on the bowl, set η=1.5\eta=1.5. By the proposition, how far from the minimum (Euclidean distance) does RMSProp end up?

Show the answer

1.06

Each coordinate oscillates between ±η/2=±0.75\pm\eta/2=\pm0.75, so the distance is 0.752≈1.060.75\sqrt2\approx1.06, which the widget reports when the race ends. At η=2\eta=2 it is 1.411.41. The orbit scales with η\eta, which is why adaptive methods are paired with decaying schedules.

When Adam fails, and what fixes it

DerivationWhy it drifts the wrong way (sketch)
  1. t≡1:vt≥(1−β2) C2=C41+C2⟹∣Δx∣=ηtCvt≤ηt1+C−2t\equiv1:\quad v_t\ge(1-\beta_2)\,C^2=\frac{C^4}{1+C^2}\quad\Longrightarrow\quad\abs{\Delta x}=\eta_t\frac{C}{\sqrt{v_t}}\le\eta_t\sqrt{1+C^{-2}}

    With β1=0\beta_1=0 the step is −ηtgt/vt-\eta_tg_t/\sqrt{v_t}. The large gradient arrives once per period and inflates vtv_t at that very step: since 1−β2=C2/(1+C2)1-\beta_2=C^2/(1+C^2), the update divides CC by roughly CC:

  2. t≡2,0:vt=β2vt−1+(1−β2)=O(1)⟹Δx≈+ηt2, +ηtt\equiv2,0:\quad v_t=\beta_2v_{t-1}+(1-\beta_2)=\order{1}\quad\Longrightarrow\quad\Delta x\approx+\frac{\eta_t}{\sqrt2},\ +\eta_t

    The gradients −1-1 arrive twice per period. The short memory forgets C2C^2 within a step (β2C2<1\beta_2C^2<1), so vtv_t is about 2 at the first and about 1 at the second, and each pushes xx up by a constant fraction of ηt\eta_t:

  3. Δxperiod≈ηt(−1+12+1)≈+0.7 ηt>0⟹xt→+1\Delta x_{\text{period}}\approx\eta_t\Big(-1+\tfrac1{\sqrt2}+1\Big)\approx+0.7\,\eta_t>0\quad\Longrightarrow\quad x_t\to+1

    Per period the net drift is positive, although the average gradient (C−2)/3(C-2)/3 is also positive and calls for moving down:

  4. Γt+1=vt+1ηt+1−vtηt ⪰̸ 0\Gamma_{t+1}=\frac{\sqrt{\mathbf v_{t+1}}}{\eta_{t+1}}-\frac{\sqrt{\mathbf v_t}}{\eta_t}\ \not\succeq\ 0

    The normalization has erased the information in the gradients' magnitudes: the rare large gradient is cut to the size of the frequent small ones, and the method follows the majority sign instead of the mean. Reddi et al. trace the failure to the quantity below, positive semidefinite for SGD and AdaGrad (effective steps never grow) but indefinite for Adam and RMSProp:

AMSGrad (Reddi et al., 2018) divides by the running maximum v^t=max⁡(v^t−1,vt)\hat{\mathbf v}_t=\max(\hat{\mathbf v}_{t-1},\mathbf v_t), so effective steps never grow; with ηt=η/t\eta_t=\eta/\sqrt t it has O(T)\order{\sqrt T} regret for online convex problems. On the example above it converges to −1-1, and so does Adam with β2=0.999\beta_2=0.999, whose long memory averages C2C^2 over hundreds of periods. Later analyses showed that the counterexamples choose β2\beta_2 after the problem: for a fixed problem and β2\beta_2 close enough to 1, unmodified Adam converges to a neighborhood of stationary points (Zhang et al., 2022; Défossez et al., 2022). AMSGrad has seen little use in practice.

Decoupled weight decay. Adding λ2∥θ∥2\tfrac\lambda2\norm{\boldsymbol\theta}^2 to the loss makes Adam rescale the decay term by 1/v^1/\sqrt{\hat{\mathbf v}} like everything else, so weights with large gradients are regularized less. AdamW applies the decay outside the adaptive step, θ←θ−η(m^/(v^+ε)+λθ)\boldsymbol\theta\leftarrow\boldsymbol\theta-\eta\big(\hat{\mathbf m}/(\sqrt{\hat{\mathbf v}}+\varepsilon)+\lambda\boldsymbol\theta\big); it generalizes better and is the default for transformers (Loshchilov & Hutter, 2019). For SGD the two forms coincide up to a rescaling of λ\lambda.

Check your understanding

On Reddi et al.'s example, which change makes the method converge to the minimizer x=−1x=-1?

  1. A smaller β2\beta_2, so that vtv_t tracks the latest gradient more closely
  2. Dividing by the running maximum of vtv_t (AMSGrad), or using β2\beta_2 close to 1
  3. Clipping every gradient to norm at most 1
  4. A constant step instead of η/t\eta/\sqrt t
Show the answer

B. Dividing by the running maximum of vtv_t (AMSGrad), or using β2\beta_2 close to 1

The failure comes from a short memory that forgets the rare large gradient. AMSGrad's running maximum never forgets it, and β2=0.999\beta_2=0.999 averages C2C^2 over hundreds of periods. Either way the steps become proportional to the gradients again and x→−1x\to-1, as a direct simulation confirms.

Do adaptive methods generalize worse?

Wilson, Roelofs, Stern, Srebro & Recht (2017) constructed a linearly separable classification problem, with more features than examples, on which SGD started at zero classifies new points perfectly while AdaGrad, RMSProp and Adam converge to a different interpolating solution with test error close to one half. They also reported adaptive methods generalizing worse on several image and language benchmarks. The mechanism is implicit bias: when many solutions fit the data, each optimizer selects a different one, and for gradient descent on least squares it is the minimum-ℓ2\ell_2-norm solution (Regularization Theory).

The debate has since shifted. With hyperparameters tuned equally carefully, Adam's ε\varepsilon included, more general optimizers matched or beat their special cases, so many reported gaps reflected tuning protocols (Choi et al., 2019). On transformers the gap runs the other way: SGD trains them markedly worse than Adam. Proposed explanations include heavy-tailed gradient noise (Zhang et al., 2020), Adam's resemblance to sign descent (Kunstner et al., 2023), and the heavy-tailed class imbalance of language data, where adaptive steps keep learning rare tokens that gradient descent neglects (Kunstner et al., 2024).

MethodUpdate (per coordinate)State per parameterWhat is guaranteed
SGD−ηg-\eta gnonethe rates of step 1, worst-case optimal
Heavy ballv←βv+gv\leftarrow\beta v+g; −ηv-\eta v1acceleration on quadratics only
AdaGrad−ηg/∑kgk2-\eta g/\sqrt{\sum_kg_k^2}1adaptive O(T)\order{\sqrt T} regret (online convex)
Adam−ηm^/(v^+ε)-\eta\hat m/(\sqrt{\hat v}+\varepsilon)2can fail for fixed (β1,β2)(\beta_1,\beta_2); converges near stationary points as β2→1\beta_2\to1
AMSGradAdam with the running max of vv3O(T)\order{\sqrt T} regret (online convex)
AdamWAdam step, plus −ηλθ-\eta\lambda\theta2as Adam; the default for transformers

Key takeaways

  • SGD with step η≤1/L\eta\le1/L on a smooth nonconvex ff satisfies 1T∑tE∥∇f∥2≤2ΔηT+Lησ2\frac1T\sum_t\E\norm{\nabla f}^2\le\frac{2\Delta}{\eta T}+L\eta\sigma^2, an O(1/T)\order{1/\sqrt T} rate that is worst-case optimal. Batches divide σ2\sigma^2 and allow proportionally larger steps, up to a critical batch size.
  • Under strong convexity a constant step converges linearly to a noise floor ησ2/μ\eta\sigma^2/\mu. Decaying the step trades speed for a lower floor, the logic behind step and cosine schedules; warmup protects early training from noisy second moments, large gradients and sharp regions.
  • Adam's steps are scale-invariant and roughly bounded by η\eta, close to sign descent when gradients are consistent; at a constant step, RMSProp has an orbit of size η/2\eta/2 per coordinate whatever the curvature.
  • A short-memory normalization can drive Adam to the worst point of a convex problem (Reddi et al., 2018); AMSGrad's running maximum, or β2→1\beta_2\to1, restores convergence, and AdamW decouples weight decay from the adaptive scaling.
  • Adaptive methods can pick worse-generalizing solutions on constructed problems (Wilson et al., 2017), but tuning protocols explain many reported gaps, and on transformers Adam clearly beats SGD, for reasons still debated.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

For SGD on an LL-smooth nonconvex function with gradient-noise variance σ2>0\sigma^2>0 and a tuned constant step, how does the guaranteed average of E∥∇f∥2\E\norm{\nabla f}^2 decay with the number of steps TT?

  1. O(1/T)\order{1/T}
  2. O(1/T)\order{1/\sqrt T}
  3. O(e−cT)\order{e^{-cT}}
  4. O(1/T2)\order{1/T^2}
Show the answer

B. O(1/T)\order{1/\sqrt T}

The bound 2ΔηT+Lησ2\frac{2\Delta}{\eta T}+L\eta\sigma^2 is minimized by η∝1/T\eta\propto1/\sqrt T, giving O(σLΔ/T)\order{\sigma\sqrt{L\Delta/T}} once noise dominates. Without noise (σ=0\sigma=0) it improves to O(1/T)\order{1/T}, the rate of gradient descent.

Question 2

RMSProp with a constant step η\eta (and ε=0\varepsilon=0) runs on f(x,y)=50x2+0.01y2f(x,y)=50x^2+0.01y^2. On its period-2 orbit, what is the amplitude of the oscillation in each coordinate?

  1. η/2\eta/2 in both coordinates
  2. η/2\eta/2 in xx, but almost none in yy, where the gradient is negligible
  3. 00, because RMSProp converges on quadratics
  4. η/λi\eta/\lambda_i, inversely proportional to each curvature
Show the answer

A. η/2\eta/2 in both coordinates

On the orbit gi=±λiη/2g_i=\pm\lambda_i\eta/2 and si=λiη/2\sqrt{s_i}=\lambda_i\eta/2, so every step has length exactly η\eta and each coordinate oscillates by ±η/2\pm\eta/2, whatever its curvature. Per-coordinate normalization removes curvature from the step size: that is its strength on ill-conditioned problems, and the reason η\eta must decay.

Question 3

What is the core reason Adam fails on Reddi, Kale & Kumar's sequence ft(x)=Cx,−x,−x,…f_t(x)=Cx,-x,-x,\dots?

  1. The objective is nonconvex
  2. The step size η/t\eta/\sqrt t decays too fast
  3. Momentum overshoots the minimum
  4. Normalizing by a short-memory average of squared gradients cuts the rare large gradient down to the size of the frequent small ones, so the method follows the majority sign instead of the mean
Show the answer

D. Normalizing by a short-memory average of squared gradients cuts the rare large gradient down to the size of the frequent small ones, so the method follows the majority sign instead of the mean

With β1=0\beta_1=0 there is no momentum, and every ftf_t is linear, hence convex. The large gradient inflates vtv_t exactly when it arrives, so its step is about ηt\eta_t, while each −1-1 gradient also gets a step of order ηt\eta_t: two up-steps beat one down-step. AMSGrad's maximum, or β2\beta_2 near 1, keeps vv large and restores proportional steps.

Question 4

Why does AdamW decouple weight decay from the gradient instead of adding λ2∥θ∥2\tfrac\lambda2\norm{\boldsymbol\theta}^2 to the loss?

  1. Because inside Adam the penalty's gradient is divided by v^\sqrt{\hat{\mathbf v}}, so weights with large gradients are decayed less; decoupling shrinks all weights at the same relative rate
  2. Because the L2L_2 term makes the loss nonconvex
  3. Because Adam ignores terms that do not depend on the data
  4. Because weight decay and L2L_2 regularization differ for SGD as well
Show the answer

A. Because inside Adam the penalty's gradient is divided by v^\sqrt{\hat{\mathbf v}}, so weights with large gradients are decayed less; decoupling shrinks all weights at the same relative rate

Inside Adam, λθ\lambda\boldsymbol\theta is rescaled coordinate by coordinate like the data gradient, which turns a uniform shrinkage into a gradient-dependent one. AdamW applies −ηλθ-\eta\lambda\boldsymbol\theta directly. For SGD the two forms coincide up to a rescaling of λ\lambda (Loshchilov & Hutter, 2019).

Further reading

  • S. Ghadimi & G. Lan, "Stochastic first- and zeroth-order methods for nonconvex stochastic programming," SIAM Journal on Optimization 23(4) (2013).
  • S. J. Reddi, S. Kale & S. Kumar, "On the convergence of Adam and beyond," ICLR (2018).
  • A. C. Wilson, R. Roelofs, M. Stern, N. Srebro & B. Recht, "The marginal value of adaptive gradient methods in machine learning," NeurIPS (2017).
  • I. Loshchilov & F. Hutter, "Decoupled weight decay regularization," ICLR (2019).
  • L. Bottou, F. E. Curtis & J. Nocedal, "Optimization methods for large-scale machine learning," SIAM Review 60(2) (2018).