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, AMSGrad, 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 $\beta \in [0,1)$ should be large (close to 1), which comports with empirical findings. We also provide experimental findings that further validate these conclusions. SGD with stochastic momentum has been a de facto algorithm in nonconvex optimization and deep learning. It has been widely adopted for training machine learning models in various applications. Modern techniques in computer vision (e.g. Krizhevsky et al. (2012) ; He et al. (2016) ; Cubuk et al. (2018) ; Gastaldi (2017)), speech recognition (e.g. Amodei et al. (2016) ), natural language processing (e.g. Vaswani et al. (2017) ), and reinforcement learning (e.g. Silver et al. (2017) ) use SGD with stochastic momentum to train models. The advantage of SGD with stochastic momentum has been widely observed (Hoffer et al. (2017) ; Loshchilov & Hutter (2019) ; Wilson et al. (2017) ). Sutskever et al. (2013) demonstrate that training deep neural nets by SGD with stochastic momentum helps achieving in faster convergence compared with the standard SGD (i.e. without momentum). The success of momentum makes it a necessary tool for designing new optimization algorithms in optimization and deep learning. For example, all the popular variants of adaptive stochastic gradient methods like Adam (Kingma & Ba (2015) ) or AMSGrad (Reddi et al. (2018b) ) include the use of momentum. Despite the wide use of stochastic momentum (Algorithm 1) in practice, justification for the clear empirical improvements has remained elusive, as has any mathematical guidelines for actually setting the momentum parameter-it has been observed that large values (e.g. β = 0.9) work well in practice. It should be noted that Algorithm 1 is the default momentum-method in popular software packages such as PyTorch and Tensorflow. 1 In this paper we provide a theoretical analysis for SGD with 1: Required: Step size parameter η and momentum parameter β. 2: Init: w0 ∈ R d and m−1 = 0 ∈ R d . 3: for t = 0 to T do 4: Given current iterate wt, obtain stochastic gradient gt := ∇f (wt; ξt). In this paper, we identify three properties that guarantee SGD with momentum in reaching a secondorder stationary point faster by a higher momentum, which justifies the practice of using a large value of momentum parameter β. We show that a greater momentum leads to escaping strict saddle points faster due to that SGD with momentum recursively enlarges the projection to an escape direction. However, how to make sure that SGD with momentum has the three properties is not very clear. It would be interesting to identify conditions that guarantee SGD with momentum to have the properties. Perhaps a good starting point is understanding why the properties hold in phase retrieval. We believe that our results shed light on understanding the recent success of SGD with momentum in non-convex optimization and deep learning.
Higher momentum parameter $\beta$ helps for escaping saddle points faster
{"src": "scitldr-AIC_train", "paper_id": "rkeNfp4tPr"}