ON THE CONVERGENCE OF ADAM AND BEYOND
Several recently proposed stochastic optimization methods that have been successfully used in training deep networks such as RMSPROP, ADAM, ADADELTA, NADAM are based on using gradient updates scaled by square roots of exponential moving averages of squared past gradients. In many applications, e.g. learning with large output spaces, it has been empirically observed that these algorithms fail to converge to an optimal solution (or a critical point in nonconvex settings). We show that one cause for such failures is the exponential moving average used in the algorithms. We provide an explicit example of a simple convex optimization setting where ADAM does not converge to the optimal solution, and describe the precise problems with the previous analysis of ADAM algorithm. Our analysis suggests that the convergence issues can be fixed by endowing such algorithms with "long-term memory" of past gradients, and propose new variants of the ADAM algorithm which not only fix the convergence issues but often also lead to improved empirical performance.
This work identifies a mistake in the existing proof of convergence of
Adam, which is among the most popular optimization methods in deep
learning. Moreover, it gives a simple 1-dimensional counterexample with
linear losses on which Adam does not converge. The same issue also
affects RMSprop, which may be viewed as a special case of Adam without
momentum. The problem with Adam is that the "learning rate" matrices
V_t^{1/2}/alpha_t are not monotonically decreasing. A new method, called
AMSGrad is therefore proposed, which modifies Adam by forcing these
matrices to be decreasing. It is then shown that AMSGrad does satisfy
essentially the same convergence bound as the one previously claimed for
Adam. Experiments and simulations are provided that support the
theoretical analysis.
Apart from some issues with the technical presentation (see below), the
paper is well-written.
Given the popularity of Adam, I consider this paper to make a very
interesting observation. I further believe all issues with the technical
presentation can be readily addressed.
Issues with Technical Presentation:
- All theorems should explicitly state the conditions they require
  instead of referring to "all the conditions in (Kingma & Ba, 2015)".
- Theorem 2 is a repetition of Theorem 1 (except for additional
  conditions).
- The proof of Theorem 3 assumes there are no projections, so this
  should be stated as part of its conditions. (The claim in footnote 2
  that they can be handled seems highly plausible, but you should be up
  front about the limitations of your results.)
- The regret bound Theorem 4 establishes convergence of the optimization
  method, so it plays the role of a sanity check. However, it is
  strictly worse than the regret bound O(sqrt{T}) for online gradient
  descent [Zinkevich,2003], so it cannot explain why the proposed
  AMSgrad method might be adaptive. (The method may indeed be adaptive
  in some sense; I am just saying the *bound* does not express that.
  This is also not a criticism of the current paper; the same remark
  also applies to the previously claimed regret bound for Adam.)
- The discussion following Corollary 1 suggests that sum_i
  hat{v}_{T,i}^{1/2} might be much smaller than d G_infty. This is true,
  but we should always expect it to be at least a constant, because
  hat{v}_{t,i} is monotonically increasing by definition of the
  algorithm, so the bound does not get better than O(sqrt(T)).
  It is also suggested that sum_i ||g_{1:T,i}|| = sqrt{sum_{t=1}^T
  g_{t,i}^2} might be much smaller than dG_infty, but this is very
  unlikely, because this term will typically grow like O(sqrt{T}),
  unless the data are extremely sparse, so we should at least expect
  some dependence on T.
- In the proof of Theorem 1, the initial point is taken to be x_1 = 1,
  which is perfectly fine, but it is not "without loss of generality",
  as claimed. This should be stated in the statement of the Theorem.
- The proof of Theorem 6 in appendix B only covers epsilon=1. If it is
  "easy to show" that the same construction also works for other
  epsilon, as claimed, then please provide the proof for general
  epsilon.
Other remarks:
- Theoretically, nonconvergence of Adam seems a severe problem. Can you
  speculate on why this issue has not prevented its widespread adoption?
  Which factors might mitigate the issue in practice?
- Please define g_t \circ g_t and g_{1:T,i}
- I would recommend sticking with standard linear algebra notation for
  the sqrt and the inverse of a matrix and simply using A^{-1} and
  A^{1/2} instead of 1/A and sqrt{A}.
- In theorems 1,2,3, I would recommend stating the dimension (d=1) of
  your counterexamples, which makes them very nice!
Minor issues:
- Check accent on Nicol\`o Cesa-Bianchi in bibliography.
- Near the end of the proof of Theorem 6: I believe you mean Adam
  suffers a "regret" instead of a "loss" of at least 2C-4.
  Also 2C-4=2C-4 is trivial in the second but last display.