Venue: ICLR 2018 conference

Reviews:

final_score: rating: 9: Top 15% of accepted papers, strong accept
review_content: The paper presents three contributions: 1) it shows that the proof of convergence Adam is wrong; 2) it presents adversarial and stochastic examples on which Adam converges to the worst possible solution (i.e. there is no hope to just fix Adam's proof); 3) it proposes a variant of Adam called AMSGrad that fixes the problems in the original proof and seems to have good empirical properties.

The contribution of this paper is very relevant to ICLR and, as far as I know, novel.
The result is clearly very important for the deep learning community.
I also checked most of the proofs and they look correct to me: The arguments are quite standard, even if the proofs are very long.

One note on the generality of the results: the papers states that some of the results could apply to RMSProp too. However, it has been proved that RMSProp with a certain settings of its parameters is nothing else than AdaGrad (see Section 4 in  Mukkamala and Hein, ICML'17). Hence, at least for a certain setting of its parameters, RMSProp will converge. Of course, the proof in the ICML paper could be wrong, I did not check that...

A general note on the learning rate: The fact that most of these algorithms are used with a fixed learning rate while the analysis assume a decaying learning rate should hint to the fact that we are not using the right analysis. Indeed, all these variants of AdaGrad did not really improve the AdaGrad's regret bound. In this view, none of these algorithms contributed in any meaningful way to our understanding of the optimization of deep networks *nor* they advanced in any way the state-of-the-art for optimizing convex Lipschitz functions.
On the other hand, analysis of SGD-like algorithms with constant step sizes are known. See, for example, Zhang, ICML'04 where linear convergence is proved in a neighbourhood of the optimal solution for strongly convex problems.
So, even if I understand this is not the main objective of this paper, it would be nice to see a discussion on this point and the limitations of regret analysis to analyse SGD algorithms.

Overall, I strongly suggest to accept this paper.


Suggestions/minor things:
- To facilitate the reader, I would state from the beginning what are the common settings of beta_1 and beta_2 in Adam. This makes easier to see that, for example, the condition of Theorem 2 is verified.
- \hat{v}_{0} is undefined in Algorithm 2.
- The graphs in figure 2 would gain in readability if the setting of each one of them would be added as their titles.
- McMahan and Streeter (2010) is missing the title. (Also, kudos for citing both the independent works on AdaGrad)
- page 11, last equation, 2C-4=2C-4. Same on page 13.
- Lemma 4 contains x_1,x_2,z_1, and z_2: are x_1 and z_1 the same? also x_2 and z_2?
review_title: Review

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: This paper examines the very popular and useful ADAM optimization algorithm, and locates a mistake in its proof of convergence (for convex problems). Not only that, the authors also show a specific toy convex problem on which ADAM fails to converge. Once the problem was identified to be the decrease in v_t (and increase in learning rate), they modified the algorithm to solve that problem. They then show the modified algorithm does indeed converge and show some experimental results comparing it to ADAM.

The paper is well written, interesting  and very important given the popularity of ADAM. 

Remarks:
- The fact that your algorithm cannot increase the learning rate seems like a possible problem in practice. A large gradient at the first steps due to bad initialization can slow the rest of training. The experimental part is limited, as you state "preliminary", which is a unfortunate for a work with possibly an important practical implication. Considering how easy it is to run experiments with standard networks using open-source software, this can easily improve the paper. That being said, I understand that the focus of this work is theoretical and well deserves to be accepted based on the theoretical work.

- On page 14 the fourth inequality not is clear to me.

- On page 6 you talk about an alternative algorithm using smoothed gradients which you do not mention anywhere else and this isn't that clear (more then one way to smooth). A simple pseudo-code in the appendix would be welcome.

Minor remarks:
- After the proof of theorem 1 you jump to the proof of theorem 6 (which isn't in the paper) and then continue with theorem 2. It is a bit confusing.
- Page 16 at the bottom v_t= ... sum beta^{t-1-i}g_i should be g_i^2
- Page 19 second line, you switch between j&t and it is confusing. Better notation would help.
- The cifarnet uses LRN layer that isn't used anymore.
review_title: Theoretical (maybe practical) issues with ADAM, and an way to solve them

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: 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.

review_title: Noteworthy paper; some (fixable) issues with technical presentation

Meta-review: This paper analyzes a problem with the convergence of Adam, and presents a solution. It identifies an error in the convergence proof of Adam (which also applies to related methods such as RMSProp) and gives a simple example where it fails to converge. The paper then repairs the algorithm in a way that guarantees convergence without introducing much computational or memory overhead. There ought to be a lot of interest in this paper: Adam is a widely used algorithm, but sometimes underperforms SGD on certain problems, and this could be part of the explanation. The fix is both principled and practical. Overall, this is a strong paper, and I recommend acceptance.

Decision: Accept (Oral)