The optimizer with the broken proof, read closely

Plain gradient descent takes the same-sized step in every direction. That is a bad deal when some parameters see huge, spiky gradients and others see tiny, steady ones — one global step size can't suit both. Adam (Kingma & Ba, 2015) fixes this by giving every parameter its own step size, learned on the fly. It keeps two running averages of the gradients it has seen:

• m — an exponential moving average of the gradient itself (momentum: which way have we been heading?).
• v — an exponential moving average of the gradient squared (how big have the gradients been?).

The update is m / √v: head in the momentum direction, but divide by the typical gradient magnitude so a parameter with wild gradients takes small, cautious steps and a parameter with gentle gradients takes big ones. That single idea — a per-parameter learning rate that adapts to the data — is why Adam became the default. Here is the whole step, with plain SGD and the paper's fix folded in for later:

import math

# One optimizer step on a scalar problem, given the current gradient g.
# beta1, beta2 are the usual EMA decays; alpha_t = alpha / sqrt(t) is the schedule.
def step(kind, s, g, cfg, t):
    alpha_t = cfg.alpha / math.sqrt(t)
    if kind == "sgd":
        return clamp(s.x - alpha_t * g)          # plain gradient descent
    s.m = cfg.beta1 * s.m + (1 - cfg.beta1) * g   # 1st moment (momentum)
    s.v = cfg.beta2 * s.v + (1 - cfg.beta2) * g*g # 2nd moment (EMA of g^2)
    if kind == "amsgrad":
        s.vhat = max(s.vhat, s.v)                 # <-- the one-line fix
        denom = math.sqrt(s.vhat)
    else:                                          # plain Adam
        denom = math.sqrt(s.v)                     # denom can SHRINK step to step
    return clamp(s.x - alpha_t * s.m / (denom + cfg.eps))

The site runs the TypeScript above (Python and C++ are line-for-line translations). Notice the divisor √v: v is a decaying average, so it goes up when gradients are large and comes back down when they are small. Hold that thought — the entire failure lives in that one word, down.

Adam shipped with a theorem: run it long enough on a convex problem and its average regret goes to zero. Regret is the honest scorecard for an online learner — how much worse your running decisions did than the single best fixed choice made with hindsight. Average regret → 0 means “in the long run you do as well as the best constant answer.” It is the minimum you should ask of an optimizer.

Reddi, Kale & Kumar found the proof leaned on a quantity staying non-negative that doesn't. Their diagnosis, in one sentence: because Adam's √v can shrink from one step to the next, a rare but informative large gradient can get divided by a big number once, then be forgotten before it moves you — while the frequent small gradients, divided by a number that has since shrunk, quietly take over. The adaptive denominator, the very thing that makes Adam Adam, is what breaks it.

To make it undeniable they hand you the smallest possible problem — one variable, straight lines, fully convex:

# Reddi, Kale & Kumar (2018), the deterministic counterexample, C > 2:
#   f_t(x) = C*x   if t mod 3 == 1
#          = -x     otherwise            feasible set F = [-1, 1]
# Over each 3-step period the net slope is (C - 1 - 1) = C - 2 > 0, so the
# objective sum_t f_t is minimised at x* = -1. A "good" optimizer should go there.
def gradients(C, T):
    return [C if (t % 3 == 1) else -1 for t in range(1, T + 1)]

Read the objective: two steps out of every three the loss is −x (wants x bigger), but the third step it is 5x (wants x much smaller). The big pull wins on balance — the net slope per period is 5 − 2 = 3 > 0 — so the loss over time is smallest at x* = −1. A working optimizer should drift left to −1 and stay. Let's run all three and see.

Same starting point (x₀ = 0), same step schedule, same gradients — the only difference is the update rule. Here is the iterate over 600 steps:

That is not slow convergence or a tuning artefact — it is the wrong direction. And because it is convex and one-dimensional, there is no local minimum to blame and nowhere to hide. The scorecard says the same thing. Average regret should fall to zero; Adam's flatlines above it:

The mechanism is worth seeing in numbers, because it is the whole paper. Look at one steady 3-step period late in the run, and track the denominator √v each optimizer divides by, and the resulting step (per unit step size — sign tells you the direction x moves):

There it is. After the big +5 gradient, Adam's v spikes and √v is large (4.91), so that informative gradient produces only a modest step. Two steps later, v has decayed, √v has shrunk to 1.02, and the small, misleading gradients get divided by that smaller number — so they push harder. The optimizer systematically under-weights the gradient it should trust and over-weights the ones it shouldn't.

Reddi et al.'s remedy is almost anticlimactic. Keep everything about Adam, but never let the denominator shrink: carry v̂ = max(v̂, v) and divide by √v̂ instead of √v. That is AMSGrad — the highlighted line in the first code block, and the only difference from Adam.

• This does not mean “Adam is broken, stop using it.” The counterexample is adversarial: it uses β₂ = 1/(1+C²) = 0.038, a far faster-decaying average than the β₂ = 0.999 everyone actually runs, so the denominator forgets aggressively. On real problems Adam usually works beautifully. The paper's point is narrower and sharper: the guarantee was false, so any comfort you took from “it's proven to converge” was unearned.
• The failure is not only adversarial, though. The authors give a second, stochastic version — a large gradient with probability 0.01, a small opposite one otherwise — where Adam still misbehaves even at recommended settings. The rare-but-large gradient is the general trigger; the periodic version just makes it visible.
• AMSGrad is not a free lunch. Its monotone denominator can only ever grow, so if one early minibatch throws a freak gradient, every later step is divided by that spike forever — AMSGrad can be needlessly timid. In practice it did not dethrone Adam; decoupled weight decay (AdamW) and simply tuning β₂ and the ε floor proved more useful day to day. The lasting contribution is the diagnosis, not the drop-in replacement.
• We reduced a neural-net optimizer to one scalar. Real Adam runs this exact update per weight over millions of coordinates. The pathology is per-coordinate, so a scalar is enough to exhibit it faithfully — but “converges on this line” and “converges on a loss landscape” are different promises, and the paper is about the online-convex one.

• Sweep β₂ toward 1 and watch the failure fade. Slide β₂ from 0.038 up to 0.999 and plot Adam's final x: there is a threshold where the denominator remembers long enough that the big gradient survives, and Adam quietly starts converging again. That threshold is the honest boundary of the counterexample.
• Turn the counterexample into a training curve. Bolt this update onto a real net on the neural-net page with a deliberately spiky gradient (a rare hard class, a heavy-tailed feature) and see whether the loss stalls with Adam and un-stalls with AMSGrad — the 2D echo of Fig 1.
• Race AMSGrad against AdamW. On the same spiky task, does freezing the denominator (AMSGrad) or decoupling weight decay (AdamW) help more? The field mostly voted AdamW; reproducing why on a toy is a clean afternoon.

The Adam paper is one of the most cited in all of machine learning, and for three years its convergence theorem sat in it, quietly false. What I like about this result is how small the wrong assumption was — a denominator that everyone pictured as only growing can, in fact, shrink — and how small the fix is: one max. Go add a few layers on the neural-net page and remember that the optimizer turning those gradients into steps is a moving average that can forget the one gradient that mattered.