Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: This work revisits a famous counterexample on the convergence of Adam (originally presented in Reddi 2018). The authors show that, if the EMA parameter beta2 in RMSprop and Adam is chosen high enough, then both methods converge to a bounded region in the stochastic setting. In addition, the authors provide some results for the full-batch case. Crucially, and differently from many other papers on the topic, the gradients are not assumed to be bounded and the beta2 hyperparameter is not chosen to increase to 1.

The paper is well written and the logic of it is convincing. I like the introduction and Figure 1 (this nicely illustrates the relevance of this paper). It is also very well organized. Unfortunately, I did not have the time I wish I had to dig into the proofs (just had a quick check), but the methodology of the authors and the results are convincing.

This is overall a very nice paper, with clean and easy to read results, that clarifies an important point: it is misleading to claim that “Adam does not converge” (which was pointed out in Reddi 2018 to introduce AMSgrad). I have heard this (wrong) claim many times in the optimization community – hence I think this paper deserves attention (therefore my clear accept). This work truly does merge the gap between theory and practice in non-convex stochastic optimization.

Just a few suggestions: I think the authors should cite and discuss the results in Defossez et al. 2019 (On the convergence of Adam and Adagrad). Also, I think Figure 1 deserves better quality. It's done in matlab so in the xlabel command you can put 'interpreter','latex' and 'fontsize',20. Finally, I spotted 1 typo: in Remark2 “cases of non-divergence cases”.

review_title: Very interesting work on classical adaptive methods

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: The paper starts off from the recent realization that there exists divergent examples for any set of hyperparameters for algorithms in the Adam family, such as RMSProp. It sets out to study the effect of the beta2 parameter on convergence for a fixed specific problem. The analysis shows that there exists a beta2 < 1 that leads to convergence for realizable problems, and to convergence to a bounded region of interest for non-realizable problems, without requiring a bounded-gradient assumption. Experiments confirm this new theory.

Overall, the paper is well-written, clear and easy to read. One of its strongest points is how well the analysis and the relevance of the results is motived. For instance, the importance of removing the assumption on the bounds on the gradient because it effectively removes one of the convergence/divergence regimes is well executed.
There is also significant efforts on providing clear simplified examples from rather complex theorems, which is very appreciated (e.g. Corollary 4.1).
Further, there is a real effort to contrast the results with the previous work, and to explain how it complements them, resolving clearly what initially appears as direct contradictions.

The results are relevant, both from the point of view of the theory, where it adds to a body of work explaining how and why the Adam family of algorithm performs well on modern machine learning taskloads, and from the point of view of the practitioner, outlining what hyperparameter tuning is necessary to achieve convergence. They are also original, in the sense that they provide novel insights, while removing problematic assumptions that permeate most of the related work.

A couple of things could be improved:
- as pointed out in the paper, if beta2 = 1, the algorithm degenerates to SGD. While there is a remark explaining why as long as beta2 < 1 the two algorithms differ, it would be informative to compare the convergence regimes with high beta2 to SGD directly, to validate that there exists a set of hyperparameters that not only provide convergence, but improved convergence properties compared to SGD (otherwise the results are a lot less relevant), as well as give an order of magnitude of what value is typically necessary for beta2.
- condition (4) in theorem 4.3 is quite difficult to apprehend, with a slightly worrying beta2^n term. More exegesis would be beneficial for reader comprehension.

Overall, this is a nice, well-written and relevant paper that clears the bar for publication in its current version.
review_title: Interesting analysis of the role of the beta2 parameter in RMSProp convergence behaviour

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary:

The paper studies one of the most popular algorithms in machine learning: RMSprop. More specifically, it investigates the relation between the hyper-parameters and the convergence of the algorithm. By proving the convergence without using "bounded gradient" assumption, the authors establish a phase transition from divergence to non-divergence for RMSProp.

Pros:

1. The paper concerns one of the most important algorithms in machine learning. In my opinion, the problem is practical and of interest in machine learning community.

2. The results of the paper provide explicit conditions for the hyper-parameters of RMSprop/Adam that ensure the convergence of the algorithms. These results provide basic guidelines for tuning hyper-parameters of the algorithms in practice.

Cons:

Apart from the strong points, I still have some concerns about the clarity of the paper. I hope the authors can address my concerns to improve the quality of the paper.

1. The parameter $\beta_2$ is the most important subject of the paper. Until algorithm 1, the paper discusses $\beta_2$ without defining it clearly. It would be more clear if $\beta_2$ is mentioned from the beginning of the paper that it comes form algorithm 1.

2. The authors divide the problems into 2 sub-classes to investigate: realizable and non-realizable, which are not clearly defined. It would be better if the authors can define these 2 sub-classes more formally.

3. The experiments supporting the theoretical results are comprehensible. However, I would suggest the authors provide a figure with x-axis to be epochs and y-axis to be accuracy so that the readers can have better idea upon how SGD and RMSProp behave during training.
review_title: The paper studies one of the most popular algorithms in machine learning: RMSprop. The proposed problem is practical. Overall, I vote for accepting the paper. 

Meta-review: The paper shows convergence results for RMSprop in certain regimes. The reviews are uniformly positive about this paper and I recommend acceptance.
Decision: Accept (Spotlight)