Stochastic gradient descent (SGD) with stochastic momentum is popular in nonconvex stochastic optimization and particularly for the training of deep neural networks. In standard SGD, parameters are updated by improving along the path of the gradient at the current iterate on a batch of examples, where the addition of a "momentum" term biases the update in the direction of the previous change in parameters. In non-stochastic convex optimization one can show that a momentum adjustment provably reduces convergence time in many settings, yet such results have been elusive in the stochastic and non-convex settings. At the same time, a widely-observed empirical phenomenon is that in training deep networks stochastic momentum appears to significantly improve convergence time, variants of it have flourished in the development of other popular update methods, e.g. ADAM (Kingma & Ba (2015)), AMSGrad (Reddi et al. (2018b)), etc. Yet theoretical justification for the use of stochastic momentum has remained a significant open question. In this paper we propose an answer: stochastic momentum improves deep network training because it modifies SGD to escape saddle points faster and, consequently, to more quickly find a second order stationary point. Our theoretical results also shed light on the related question of how to choose the ideal momentum parameter-our analysis suggests that β ∈ [0, 1) should be large (close to 1), which comports with empirical findings. We also provide experimental findings that further validate these conclusions.
*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)