Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper makes an interesting theoretical contribution; namely, that SGD with momentum (and with a slight modification to the step-size rule) is guaranteed to quickly converge to a second-order stationary point, implying it quickly escapes saddle points. SGD with momentum is widely used in the practice of deep learning, but a theoretical analysis has remained largely elusive. This paper sheds light theoretical properties justifying its use for deep learning.

Although the paper makes assumptions (e.g., twice differentiable, with smooth Hessian) that are not valid for the most widely-used deep learning models, the theoretical contributions of this paper should nonetheless be of interest to researchers in optimization for machine learning. I recommend it be accepted.

The experiments reported in the paper, including those used to validate the required properties, are for small toy problems. This is reasonable given that the main contribution of the paper is theoretical. However, I would have given a higher rating if some further exploration of the validity of these properties was carried out for problems closer to those of interest to the broader ICLR community. Even if the assumptions aren't satisfied everywhere for typical deep networks, they may be satisfied at most points encountered during training, which would make the contribution even more compelling. This may also help to understand some of the limitations of this analysis.

One other limitation seems to be that Theorem 1 requires using a step size which seems to be much smaller than what one may hope to use in practice. Can you comment on this?


review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: *Summary*
This paper studies the impact of momentum for escaping Saddle points with SGD (+momentum) in a non-convex optimization setting. 
They prove that using a large momentum value (i.e. close to one) provides a better constant for the convergence rate to second order stationary points.
The approach is well motivated by the current seek for a better understanding of the training methods used in practical deep learning. The related work seems to be well addressed.
 
*Decision*: 
I think that this paper is borderline for the following reasons: First I would like to acknowledge the fact that the problem of studying the impact of momentum on SGD is a very challenging problem with a plethora of open questions even in the convex setting. Thus, trying to show evidence of a significant additive value of momentum in the non-convex setting is a very hard problem. 
However, I am not fully convinced that this work provides a results that exhibits a regime where momentum helps to escape saddle point faster (or to converge faster).
Thus I am leaning toward a weak reject but I am eager to change my grade if the authors convince me that their results bring theoretical improvements.   
 
*Questions*:
- I would like to be convinced that the analysis use the momentum aspect to improve in some ways the convergence rate of SGD and does not reduce to a perturbation analysis of the SGD method. Because of the constraints on $\beta$ (for instance $1-\beta > L^{-1/3}$) , your $1-\beta$ dependance in the convergence rate cannot be better than $L^{-1/3}$. Thus, one could believe the $\beta$ in the bound is only a hidden proxy for the Lipschitz constant or for $\sigma$.  One way to be convincing about the fact that this bound is interesting would be to provide some regime where we can see improvements compared with related work. (e.g. $L >> \sigma, c’>> 1$) Or maybe if the current theoretical interest of the momentum is only in escaping saddle point better (since its convergence in the convex case is still not well understood) than regular SGD methods.
- To what extend your assumptions are comparable to the ones made in the close related work (papers presented in Table 1) ?
 
 
 
*Minor remarks*:
- You should cite something for the NP-hardness of finding local minima. 
- The definition for $(\epsilon,\epsilon)$-second order stationary point would be a bit cleared with two different epsilon $\epsilon_1,\epsilon_2$.
- I think should should put the constraints you have on $\beta$ in the main paper.
-  In definition 2 does $M_t$ depends on $k$ or is it a typo, (the summation index for $G_{s,t}$ depends on $k$ that make the definition confusing) ? Can $G_{s,t}$ be rewritten as $I- \eta (1 - \beta^s)/(1-\beta) \nabla^2f(\omega_t)$ to avoid to introduce an unnecessary sum notation ?  
- Usually footnotes are after the punctuation sign (because you want to comment the whole sentence and not its last word).
- Footnote 4 is in the wrong page.

==== After rebuttal ==== 
I have read the answers of the authors and I still think that their results are too hard to interpret.
I also think that the results are still presented in a misleading way (putting $1-\beta$ in the $O()$ while this quantity is not allowed to vanish since it has to be greater that $L^{-1/3}$). 
The interest of the momentum method should be that when using $\beta = 1 - L^{-1/3}$ the escaping time (for instance) is better. 
The author did not convince that is was the case. 

However I would tend to change my grade to 4 or 5 /10 if it was possible. (i.e. very borderline weak reject) 

review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: Summary:
The paper presents an analysis and numerical evaluation of SGD with momentum for non-convex optimization problems. In particular, the main contribution of the paper, as the authors claim in the abstract, is showing that stochastic momentum improves deep network training because it modifies SGD to escape saddle points faster. 

Comments:
SGD with heavy ball momentum (or stochastic heavy ball method) is one of the most popular methods for training neural networks. As the authors mentioned the method is widely employed in practice, especially in the area of deep learning. However, despite the popularity of the method both in convex and non-convex optimization, its convergence properties are not very well understood.  
I consider any meaningful direction for understanding the convergence of this method a nice fit to ICLR, however i find the presentation of this paper somehow confusing, especially Section 3 which is supposed to be the main contribution of the paper. 

1) I understand the motivation of the authors and what they tried to communicate but i find that there 
is no satisfactory explanation of what Theorem 1 is actually saying. For example In case that $\beta=0$ the method is the popular stochastic gradient descent method. Does the theorem covers the known results of SGD appeared in previous works? 

2) In addition, the theorem states" If SGD with momentum (Algorithm 2) has ....APAG...APCG_T...GrACE ...". How we can guarantee that the above 3 conditions is satisfied from the Algorithm 2? There is also no satisfactory explanation of why the authors analyze Algorithm 2 and not Algorithm 1. 

3) The presentation of Section 3.2.1 is also not clear. I am suggesting to the authors to explain in more details the theoretical results of their paper and highlight why the 5 lemmas of this section are important to be in the main part of the paper. I think a notation subsection will be useful for the reader.

4) I am suggesting the authors to include in the introduction the more known variant of SGD with momentum:
$$\omega_{t+1}=\omega_t-\eta \nabla f(\omega_t, \xi_t)+\beta(\omega_t-\omega_{t-1})$$
5) The authors name their methods "SGD with stochastic momentum". The method is either "SGD with momentum" or "Stochastic heavy ball method". SGD with stochastic momentum is something different (see for example [Loizou, Richtarik 2017] from paper's reference section)

Minor Comment:
page 3, bellow eq(4): the first (3) ----> Problem (3)

Missing references:
The authors did an excellent work on reviewing the literature review on SGD with momentum. Bellow find three recent related works that could be mentioned:

Aybat, Necdet Serhat, Alireza Fallah, Mert Gurbuzbalaban, and Asuman Ozdaglar. "A universally optimal multistage accelerated stochastic gradient method." arXiv preprint arXiv:1901.08022 (2019).
Loizou, Nicolas, and Peter Richtárik. "Linearly convergent stochastic heavy ball method for minimizing generalization error." arXiv preprint arXiv:1710.10737 (2017).
Loizou, Nicolas, and Peter Richtárik. "Accelerated gossip via stochastic heavy ball method." In 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 927-934. IEEE, 2018.

========= after rebuttal =============
 I would like to thank the authors for the reply. After reading their response and the comments of the other reviewers I  decide to update my score to "weak accept".

review_title: Official Blind Review #3

Meta-review: This paper studies the impact of using momentum to escape saddle points. They show that a heavy use of momentum improves the convergence rate to second order stationary points. The reviewers agreed that this type of analysis is interesting and helps understand the benefits of this standard method in deep learning. The authors were able to address most of the concerns of the reviewers during rebutal, but is borderline due to lingering concerns about the presentation of the results. We encourage the authors to give more thought to the presentation before publication.
Decision: Accept (Poster)