A single one-dimensional problem breaks Adam's convergence proof

One step size never fit every parameter

Stochastic gradient descent moves every parameter by the same multiple of its own gradient. Pick one learning rate and every weight in the network lives with it, whether that weight's gradient runs large and steady or small and rare. Adam's answer was to give each parameter its own effective step, worked out from that parameter's own gradient history, without asking anyone to tune a separate rate per weight.

The paper's recipe is two exponential moving averages read together. One tracks the gradient itself, giving the update momentum. The other tracks the squared gradient, in the manner of RMSProp, and turns that magnitude into a per-parameter scale. A weight whose gradient has run large and noisy gets a smaller step. One whose gradient has stayed small and quiet gets a larger one.² Kingma and Ba built the combination to be, in their own words, "invariant to diagonal rescaling of the gradients" and suited to problems "large in terms of data and/or parameters," with hyperparameters that "have intuitive interpretations and typically require little tuning."¹

Two claims rode on that design: that the rule itself would be robust and well scaled in practice, and that it could be proven to converge. The first held up. The second did not.

Two moving averages and a correction for both

Call the gradient at step t simply g_t. The first average tracks its mean: m_t \leftarrow \beta_1 m_{t-1} + (1-\beta_1)g_t, with a default \beta_1 = 0.9. The second tracks its uncentered variance: v_t \leftarrow \beta_2 v_{t-1} + (1-\beta_2)g_t^2, with a default \beta_2 = 0.999.¹

Both averages start at zero, so early in training they are pulled toward zero exactly when there is the least history to average over, an effect that stays measurable for dozens of steps whenever a decay rate sits close to 1.² Kingma and Ba's correction divides each average by 1-\beta^t. That factor sits far below 1 while t is small, pulling the early estimate back up to where the same few gradients already say it should be. It rises to 1 as t grows, and the correction stops mattering. \hat{m}_t = m_t / (1-\beta_1^t) and \hat{v}_t = v_t / (1-\beta_2^t).¹

The parameter update spends both corrected estimates at once.¹

The proof and the practice Adam shipped with

Kingma and Ba did not stop at showing the rule behaves. They analyzed it as an online learner and reported a regret bound of order O(1/\sqrt{T}) over T rounds, "comparable to the best known results under the online convex optimization framework."¹ That is the standard way the online-learning literature states how fast a method catches up to the best fixed point chosen in hindsight.

With the defaults set (\beta_1=0.9,\ \beta_2=0.999,\ \epsilon=10^{-8}) and the theory attached, the algorithm shipped ready to use, and adoption followed the paper's own promise that it would need little tuning. It is now the default optimizer in both major deep learning frameworks: PyTorch's implementation matches Kingma and Ba's specification down to the same three defaults,³ and Google DeepMind's Optax library ships the equivalent for JAX.⁴

The point the proof said it could not reach

The regret bound rested on an assumption the proof used without stating it as a separate requirement: that a quantity governing the effective step size only shrinks over time. AdaGrad has that property by construction, since it accumulates the full running sum of past squared gradients, a sum that can only grow. Reddi, Kale, and Kumar showed in 2018 that Adam's exponential average carries no such guarantee.⁵⁶ They traced the break to a specific step in the original proof, one that treats a quantity measuring the change in the per-parameter learning rate as always positive when Adam's own update can drive it negative.⁵⁷ The reason is how the average forgets. Old gradients fall out of it geometrically instead of accumulating forever, so a single large gradient can dominate the estimate for a few steps and then disappear. The effective step size can then grow again exactly when the proof needs it to keep shrinking.⁶

The construction they built to demonstrate it is a one-dimensional online convex problem, simple enough to check by hand. A single coordinate is confined to [-1, 1]. It faces a sequence of linear losses whose gradient signal favors x=-1 on average but occasionally swings hard the other way. Adam's iterate does not settle near that optimum. It converges to x=+1, the single worst point the domain allows.⁵

Malladi's later analysis is careful to call the construction artificial: that exact sequence does not occur in ordinary training.⁶ But an artificial counterexample is enough to break a universal claim, and the point was never that Adam fails on every problem. It is that the proof, read as stated, does not cover the algorithm it was written for, a defect serious enough that the paper exhibiting it won ICLR's Best Paper award that year.⁸

A fix with a regret bound and no following

Reddi, Kale, and Kumar's own repair keeps Adam's two exponential averages and adds one operation. Instead of bias-correcting the second moment every step, AMSGrad first takes the running maximum of the raw second moment, then applies the bias correction once, to that maximum.⁵³

That single maximum restores the non-increasing property the proof needs, and with it a regret bound, this time proven for the algorithm as actually run rather than an idealized stand-in for it.⁵

What AMSGrad does not do is train a better network. Reddi, Kale, and Kumar's own experiments on MNIST, CIFAR-10, and comparable image benchmarks find it matching Adam at best and trailing it at worst.⁵ The maximum that repairs the proof also throws away the property Adam relies on in practice: the ability of the effective step to grow back once a spike in the gradient has passed. A guarantee built for a one-dimensional adversary bought little for a network that never meets one. PyTorch and Optax both ship AMSGrad as a boolean flag on ordinary Adam, one nearly every training run leaves off.³

The same decay rate for every weight, finally

Loshchilov and Hutter's 2019 paper starts from a complaint that has nothing to do with the convergence proof. Standard practice regularizes a network by adding an L2 penalty to the loss. For plain gradient descent that penalty is exactly equivalent to weight decay: after rescaling by the learning rate, it shrinks every weight by the same fraction at every step.⁹ Fold that penalty into Adam, though, and the equivalence breaks, because the penalty term travels through the gradient before Adam divides by its own per-parameter scale. Its effect on any given weight ends up divided by that weight's own \hat{v}_t. A weight with a large, noisy gradient history gets its penalty diluted. A weight with a small, quiet one gets it amplified.⁹

Reconstructing both update rules exactly as specified above and running them on two synthetic parameters that differ only in how large a gradient each saw before that gradient stopped computes the asymmetry directly.

Loshchilov and Hutter's fix is to stop routing the penalty through the gradient at all. Apply it directly to the weight, outside the adaptive ratio. Every parameter then loses the same fraction of itself, regardless of its own gradient history.

They reported the decoupled version improving generalization on CIFAR-10 and ImageNet32x32 over Adam's coupled L2, matching or beating plain SGD with momentum on both.⁹ On those same two benchmarks, they report the decoupled version reaching "15% relative improvement in test error compared to Adam both on CIFAR-10 and ImageNet32x32."⁹ PyTorch and Optax both ship AdamW as a named, separate optimizer.³⁴

The algorithm and its proof went separate ways

Read next to each other, the three papers split Adam's decade-plus run into a claim that held, a proof that did not, and a fix that mattered more than either. The update rule Kingma and Ba described, two corrected moving averages spending a single global rate, works about as advertised: robust across a wide range of problems, needing little of the per-parameter tuning it replaced.¹ The regret bound attached to it does not hold as stated. Reddi, Kale, and Kumar built an explicit case where the algorithm converges to the one point in a bounded domain it was supposed to avoid.⁵ Their own repair for that proof, AMSGrad, is theoretically sound and practically beside the point.⁵