A Simple Convergence Proof of Adam and Adagrad

By Alexandre D'efossez, L. Eon Bottou, Francis R. Bach, Nicolas Usunier. 2020

246 citations recorded by the source corpus.

We provide a simple proof of convergence covering both the Adam and Adagrad adaptive optimization algorithms when applied to smooth (possibly non-convex) objective functions with bounded gradients. We show that in expectation, the squared norm of the objective gradient averaged over the trajectory has an upper-bound which is explicit in the constants of the problem, parameters of the optimizer and the total number of iterations $N$. This bound can be made arbitrarily small: Adam with a learning rate $\alpha=1/\sqrt{N}$ and a momentum parameter on squared gradients $\beta_2=1-1/N$ achieves the same rate of convergence $O(\ln(N)/\sqrt{N})$ as Adagrad. Finally, we obtain the tightest dependency on the heavy ball momentum among all previous convergence bounds for non-convex Adam and Adagrad, improving from $O((1-\beta_1)^{-3})$ to $O((1-\beta_1)^{-1})$. Our technique also improves the best known dependency for standard SGD by a factor $1 - \beta_1$.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

  1. Justin Gilmer
  2. Jeremy M. Cohen
  3. Shankar Krishnan
  4. Naman Agarwal
  5. George E. Dahl
  6. Daniel Suo
  7. Behrooz Ghorbani
  8. Zachary Nado

In Computational Mechanics

  1. Naman Agarwal
  2. George E. Dahl
  3. Jeremy M. Cohen
  4. Behrooz Ghorbani

In Management Science and Operations Research

  1. Justin Gilmer
  2. Naman Agarwal
  3. George E. Dahl
  4. Zachary Nado

Citations in the corpus