Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: This paper studies Adam and proves that under strong convexity assumption, it obtains the improved regret bound $O(log(T))$. The regret bound is data-dependent, thus as a side-effect it also improves previous known result for strongly convex RMSProp (SC-RMSProp).

The paper is clear and well-written and I also think that theoretical results are correct and new. However, I have some concerns on the possible impacts of the results especially in the context of ICLR:

- First of all, the assumption to show improved regret is strong convexity of all functions $f_t$. However, this is very restrictive and much stronger than the assumption that the sum of functions is strongly convex. In addition, from what I see, in the proof of Theorem 1, the authors use strong convexity with the $x^\star$, so they can maybe replace global strong convexity to strong convexity restricted to the path towards the solution. A reference where these restricted strong convexity type assumptions are studied:

Necoara, Nesterov, Glineur, “Linear convergence of first order methods for non-strongly convex optimization”, Math. Prog. 2019.

- To show improved regret, consistent with previous work SC-Adagrad and SC-RMSProp, the authors modify the algorithm to use $V_t^{-1}$ in page 3 in the step size, instead of $V_t^{-1/2}$ of regular Adam. It is easy to see that this is to make sure step size has a faster decrease, which is needed also to show standard SGD gets $1/k$ rate for strongly convex problems. However, given that one might not now if the problem has strong convexity (there might exist cases where this property only exists locally), it is not clear if one should apply Adam or SAdam. 

- Another remark related to the previous one is the following. Standard SGD uses step size $\alpha_0/\sqrt{k}$ for convex optimization without strong convexity and $\alpha_0/k$ for strongly convex optimization. If one uses $alpha_0/k $for convex optimization without strong convexity, one gets a very bad rate $1/log(k)$ and very bad practical performance. So, given SAdam gives step sizes suited for strongly convex optimization (similar to SGD for strongly convex optimization), I would expect SAdam's step sizes to be not very suitable when there is no strong convexity.

- An additional point is that the step size of SAdam depends on the global strong convexity parameter $\lambda$ which further restricts the applicability of the method. For the theoretical results to hold, the step size should be set according to $\lambda$, and when the step size is not selected that way, one loses the fast convergence rate.

- In the experiments, the authors show the performance of SAdam for neural network training and related to my previous remarks, I have the following concerns. First of all, how do the authors pick step sizes now since it depends on strong convexity constant as in eq. (7). In addition, given that neural networks are certainly non-strongly convex, I would expect that the fast decreasing step size caused by using $V_t^{-1}$ might also hurt the performance considerably, which happens as I discussed above even for convex but non-strongly convex losses. I would suspect that much worse effects can be seen for non-convex optimization. Of course, the authors can argue that if the loss landscape of neural network has some local strong convexity parameters, SAdam would adapt and get faster convergence. But unfortunately, I would not agree with such a statement, because the analysis is not made to adapt to local strong convexity and a dependence to strong convexity constant is present due to eq. (7), so if one does not know the constant, the theoretical guarantees would not apply. In addition, the provided experiments for neural network training is not extensive enough to convince practitioners to use SAdam instead of Adam which has been used for years.

Overall, I think that it is interesting to see that a variant of Adam can be shown to obtain improved regret under strong convexity, I find the assumptions strong and the impact for neural network training, therefore for ICLR, quite questionable.
review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: In this paper, the authors propose a variant of Adam, named as SAdam, and establish a data-dependent O(log T) regret bound. The key idea is using a faster decaying yet under controlled step size to exploit strong convexity. Some experiments are carried out to demonstrate the effectiveness of the proposed algorithm. The idea seems interesting, the writing is well-written, and the analysis seems correct (I did not fully check all steps, but the key steps seems ok to me). 

Probs:
1. The proposed SAdam is an effective variant of Adam designed for strongly convex functions. The algorithm is a natural extension of Adam, and SC-RMSprop could be regarded as a special case.
2. The authors establish a data-dependent O(log T) regret bound for SAdam, and as a byproduct, they present the first data-dependent logarithmic regret for SC-RMSprop. The authors also fix a small bug in the analysis of AMSgrad. The theoretical result is the key technical contribution of this paper.
3. The experimental results shows that Aadam can be used to minimize strongly convex functions, as well as neural networks, which is believed to be non-convex.

Cons:
1. As the authors mentioned in Remark 2, the main limitation of their analysis is that the role of the first-order momentum is unclear. Although the first-order momentum can accelerate the convergence in practice, proving this in theory remains an open problem. Is there some contribution on this aspect? 

2. The 4-layer CNN in Section 4.2 is a bit small. It would be better if the authors test their algorithm on larger and more popular neural networks.

In summary, this paper contributes the theoretical studies of ADAM-type algorithm, although the algorithm is somehow incremental. To me, a bit surprising result is that the step size originally designed for strongly convex functions also works well for training CNN.

review_title: Official Blind Review #2

final_score: rating: 8: Accept
review_content: In the setting of online convex optimization, this paper investigates the question of whether adaptive gradient methods can achieve “data dependent” logarithmic regret bounds when the class of loss functions is strongly convex. To this end, the authors propose a variant of Adam - called SAdam - which indeed satisfies such a desired bound. Importantly, SAdam is an extension of SC-RMSprop (a variant of RMSprop) for which a “data independent” logarithmic bound was found. Experiments on optimizing strongly convex functions and training deep networks show that SAdam outperforms other adaptive gradient methods (and SGD).  

The paper is very well-written, well-motivated and well-positioned with respect to related work. The regret analysis of SAdam is conceptually simple and elegant. The experimental protocol is well-detailed, and the results look promising. In a nutshell, this is an excellent piece of work.

I have just a minor comment. In the experiments, SAdam was tested using $\beta_1 = 0.9$ and $\beta_{2t} = 1 - \frac{0.9}{t}$. Since Corollary 2 covers a wide range of admissible values for these parameters, it would be interesting to report (for example in Appendix) a sensitivity analysis of SAdam, using different choices of $\beta_1$ and $\beta_{2t}$. 

review_title: Official Blind Review #3

Meta-review: The reviewers all appreciated the results. They expressed doubts regarding the discrepancy between the assumptions made and the reality of the loss of deep networks.

I share these concerns with the reviewers but also believe that, due to the popularity of Adam, a careful analysis of a variant is worthy of publication.
Decision: Accept (Poster)