LIT-018: On the Convergence of Adam and Beyond

Reddi et al. (2018) — ARXIV-1904.09237

Key takeaways

• Constructs an explicit one-dimensional convex problem on which Adam converges to x = +1 when the minimiser is x = −1 — the opposite end of the feasible set — and proves it by induction on the iterates
• Locates the error in the original Adam convergence proof: the quantity Γ_t, the per-step change in effective learning rate, is assumed to have a sign it need not have
• The cause is the exponential moving average itself. A large informative gradient arriving once every three steps is divided down before it acts, and is permanently outvoted by frequent small ones. Any method scaling updates by a fixed-size window of past gradients has this failure mode; Adagrad, which never forgets, does not
• Proposes AMSGrad — keep v̂_t = max(v̂_{t−1}, v_t) so the effective learning rate is non-increasing — recovering an O(√T) regret bound, and AdamNC, which drives β₂ toward 1 over training
• The empirical section is, in the authors’ own words, “a preliminary empirical study”: logistic regression, a small net, CIFARNET

Standing in the anthology

Read — NOTE-073. ICLR 2018 best paper, and almost nobody runs AMSGrad.

Nothing is sourced to this paper and the reading files no practice — which is the right outcome and the interesting one. SOTA-001 says use Adam by default; this paper proves Adam can fail on a convex problem. Both stand, and the gap between them is the anthology’s own premise in one line: what people do and what is provably correct are different questions, and this record tracks the first. Kept visible rather than resolved.

Every result is in online convex optimisation, a setting Adam is not used in, and the counterexample is adversarial — nobody has shown the mechanism firing in a real run.