Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper focuses on the understanding of the effects of adaptive learning rate and momentum. In particular it proves that the adaptive learning rate can escape saddle points efficiently and cannot select flat minima as SGD does. It also shows that momentum helps the training process by passing through saddle points and without affecting the minima selection.The paper also proposes a new adaptive algorithm, named Adai (Algorithm 2), which uses parameter-wise adaptive intertia to accelerate the training and finds flat minima as well as SGD.  Finally, the paper provides extensive numerical testing showing the benefits of Adai.
main_review: I believe that the main ideas of the paper are interesting. However I find that the presentation of this work is not very clear and somehow confusing. In particular, the structure of the paper and the results presented in sections 2 and 3 are difficult to absorb. See my comments below.

I understand the motivation of the authors and what they tried to communicate but i find that there is no satisfactory explanation of the results presented in sections 2 and 3. The authors assumed that the reader is familiar with the closely related recent work on the SGD diffusion theory and do not provide enough details on the framework. For example they use terminology like "Fokker-Planck equation",  "divergence operator", and "diffusion matrix" that are not really standard in the area of adaptive methods. In addition, Assumption 1 on the second order Taylor approximation near critical points, is given without providing some interesting problems where it is satisfied.

Also in section 3, Assumptions 2 and 3 are used without further explanation of what exactly they mean. The authors provide a few details in the appendix on what is the quasi-equilibrium approximation and low temperature approximation but this is not sufficient.  How these assumptions are related to standard concepts in the area? What are the mathematical expressions of these assumptions? how are related to stochastic gradients and the noise? 

Also i find it a bit surprising that there is no formal presentation of the problem that we are interested to solve and the assumptions that one requires to be able to prove convergence. A statement of the minimization (or maximation) problem under study with the main assumptions is missing from the paper. 

One of the most important contributions of the paper is the analysis of the new algorithm, Adaptive Inertia Optimization (Adai) proposed in Section 5. However if one focuses on Theorem 4 which provides the convergence guarantees of the Adai it is clear that the analysis hold under very strong conditions / assumptions. For example the authors assumed both bounded variance, and bounded gradient of the objective function, which rarely hold in practical scenarios. Note that these conditions have already been proved to contradict special classes of non-convex problems like functions satisfying the Polyak-Lojasiewicz condition (the combination of these assumptions lead to an empty set of problems). Thus the theorem cannot hold for all non-convex smooth problems.
summary_of_the_review: As i mentioned in the main review, I believe that the main ideas of the paper are interesting. However I find that the presentation of this work is not very clear and somehow confusing. In particular, the structure of the paper and the results presented in sections 2 and 3 are difficult to absorb. See my comments below.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper disentangles the effects of adaptive learning rate and momentum in Adam learning dynamics, and proves that adaptive learning rate is good at escaping saddle points but not good at selecting ﬂat minima, while momentum helps escape saddle point and matters little to escaping sharp minima. Based on the analysis, the authors propose a novel optimizer, Adai. Compared to SGDM, Adai parameter-wisely adapts the momentum hyperparameter to the (approximated) Hessians of saddle points, and is proved to fast escape saddle points and sharp minima.
main_review: The theoretical analysis of the Adam optimizer is based on the SGD diffusion theory, and the results confirms and explains the observation that Adam can sometimes converge faster but generalize worse than SGDM. The proposed Adai optimizer is theoretically sound, and demonstrates slightly better generalization performance than SGDM (and significantly better than Adam) on image classification tasks.

Despite estimating the moments in a similar way as Adam, the proposed Adai optimizer seems more akin to SGDM, with the only difference being its adaptive momentum; and it doesn't use adaptive learning rates, which is a main feature of Adam. Moreover, as shown in Figs. 1 to 3, and 10, the training curves of Adai very much resemble those of SGDM. Therefore, to further improve this work, more comparisons should be made between Adai and SGDM rather than between Adai and Adam. In particular, it would be interesting to see if the performance gap between Adai and SGDM results from faster convergence (as suggested by the theory), and therefore a convergence comparison between Adai and SGDM as the one conducted between Adai and Adam (Fig. 11) should be helpful.
summary_of_the_review: This paper provides new insights into the performance of Adam, and proposes a novel optimizer that both converges fast and generalizes well. Further improvements can be made by comparing the proposed method to SGDM more thoroughly.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work analyzes the dynamics of momentum SGD and Adam on escaping saddle points and sharp minima, which is based on the diffusion theoretical framework proposed in (Xie et al. 2021b). The authors prove that momentum provides a drift effect around saddle points and does not affect flat minima selection (for SGD), and while Adam escapes saddle points efficiently, it does not favor flat minima as well as SGD. The analysis explains some empirical observation of SGDM and Adam. Motivated by the analysis, the authors propose adaptive inertia (Adai) method, which can approximately achieve Hessian-independent momentum drift (escapes saddle points fast) and favors flat minima as well as (momentum) SGD.  
main_review: This paper is generally well-written. The diffusion theoretical analysis does provide some insight on the empirical performance of momentum SGD and Adam. The authors also put in efforts to conduct numerical verifications to their theoretical statements, which is highly appreciated. However, I think that this work does not completed ''disentangle'' the effects of adaptive learning rate and momentum since the work analyzes Adam, which fuses these two algorithmic components. It would be better to discuss the effect of each component in Adam separately (probably by setting some parameters to zero). 

The authors then propose Adai, which achieves approximately Hessian-independent momentum drift without damaging flat minima selection (BTW, the proof of Proposition 3 is missing, if it is a direct consequence of Theorem 2, it is better to mention it somehow). The construction of Adai is interesting, and its effectiveness is justified by the empirical experiments. However, it seems to me that this contribution is a bit disconnected to the main story as Adai does not use adaptive learning rate. Some revision (probably changing the title?) might be good to make the story clearer and more fluent.

Typos:
- Missing reference on page 7, "Note that an existing “adaptive momentum” method (?) "
- The last sentence "better than popular Adam and SGD".
summary_of_the_review: This work provides some new theoretical insights for momentum SGD and Adam, which are interesting and important. The authors then propose adaptive inertia based on the insights, which shows good performance. Some revision is needed to make the story clearer (see main review).
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies the behaviors of some algorithms when the iterate is at a critical point via SDEs. A variant of Adam is given in the end. The paper draws some conclusions about adaptive learning rate and momentum, claiming that 

- QUOTE momentum matters little to escaping sharp minima UNQUOTE
- QUOTE adaptive learning rate is not good at selecting flat minima UNQUOTE

main_review: Here are some of the questions and concerns:

From my perspective, the theoretical analysis is not rigorous and skips a lot of details. For example, in Section 4 (Page 5), the paper claims that the continuous-time dynamic of Adam can be written as equation (6). However, a detail derivation to support the claim and the proof of showing that the SDE is a valid one for Adam are missing in the paper. Indeed, it can be seen from Page 5, where the authors said they are analyzing an "idealized" Adam. It is not clear why this is an idealized one and the writing is like hiding something under the rug. We can see that some statements about Adam are made, but these conclusions are drawn from a SDE which does not really correspond to Adam. On the other hand, the SDE of Adam does exist in the literature, e.g. https://arxiv.org/pdf/2010.05627.pdf. If this paper really wants to claim/argue something about Adam, then a careful analysis regarding the discretization error between the solution of the proposed SDE and the discrete-time Adam should be provided in the paper. 

For another example, on page 3, it states QUOTE the diffusion matrix D is independent of $\theta$ near critical points UNQUOTE. But the proof is not provided. How is it independent? It looks like some approximations were used there. The paper should prove the "independence".

Another concern is about (8). The paper should provide a detailed derivation of showing that (8) is really about how the distribution evolves when the underlying dynamic is (7). Currently the equation (8) is like jumping out of nowhere. How does Assumption 1 help to show (8)?

Also, some places in the paper are not clear:

(a) (Second paragraph on Page 1) QUOTE all previous works have not touched the saddle-point escaping property of the dynamics UNQUOTE Apparently there are quite a few works regarding saddle-point escaping by SGD, SGD with momentum, and Adam. The authors might want to explain what they meant here.

(b) There are two approximations on (3). But it would be more helpful to explain how the approximations are made in detail. There are some descriptions below (3) but are not very clear. 

(c) (Last paragraph in Section 3) QUOTE The momentum does not affect flat minima selection in terms of the escape time UNQUOTE This is another confusing statement. What does "momentum does not affect flat minima selection" mean? Does it mean momentum and SGD without momentum converge to the same point? What is the definition of "flat minima"?

(d) (Second to last paragraph in Section 4) QUOTE Adam has $\log(\tau)=O(H_{ae}^{-1/2})$ ... SGD and SGD+momentum both have $log(\tau) = O(H_{ae}^{-1})$ UNQUOTE It seems that the conclusion right below this sentence would be reversed if $|H_{ae}|>1$. Something wrong?

(e) (Theorem 1 and 2) The authors show some guarantees about the variance at time $t$ when the iterate of the algorithm follows the Gaussian distribution. But does a higher variance of the Gaussian distribution imply a faster saddle point escape? The authors might want to add some discussions about the connection to the notion of saddle point escape in the literature (e.g  Jin et al. 2017).

(f) After reading the paper, I am still not sure how the effect of the learning rate and momentum was "disentangled" in the analysis. I see some analysis about the behavior of SGD, ADAM, SGD+momentum at critical points.  It would be more helpful if the authors can explain why the effect of the learning rate and momentum can be isolated.


summary_of_the_review: The presentation and statements are confusing in my opinion. Some steps in the analysis are not transparent.
review_title: null

Meta-review: The paper is aimed at providing an explaining the perceived lack of generalization results for Adam as compared to SGD. To this end the paper decouples the effect of adaptive per parameter learning rate and the momentum aspect of Adam. The paper shows that the while adaptive rates help escape saddle points faster - they are worse when consider the flatness of minima being selected. Further momentum has no effect on the flatness of minima but again leads to better optimization by providing a drift leading to saddle point evasion. They also provide a new algorithm Adai (based on inertia) targeted at better generalization of adaptive methods. 

The paper definitely provides an interesting perspective and the approach to decouple the effect of momentum and adaptive LR and study their efficacy in escaping saddle points and flatness of minima seems a very useful perspective. The primary reason for my recommendation is the presentation of the paper in terms of the rigor its assumptions to establish the results. These aspects have been highlighted by the reviewers in detail. I suggest the authors to carefully revisit the paper and improve the presentation of the assumptions, adding rigor to the presentation as well as adding justifications where appropriate especially in light of non-standardness of these assumptions in optimization literature.
Decision: Reject