Escaping Saddle Points Faster with Stochastic Momentum
Authors: Jun-Kun Wang
Chi-Heng Lin
Jacob Abernethy
Venue:  (2020)
Keywords: SGD
momentum
escaping saddle point

Abstract: 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.

Published as a conference paper at ICLR 2020
ESCAPING SADDLE POINTS FASTER WITH STOCHASTIC MOMENTUM
Jun-Kun Wang, Chi-Heng Lin, & Jacob Abernethy Georgia Institute of Technology {j (jimwang, cl c13385,, p @gatech. edu
ABSTRACT
Stochastic gradient descent (SGD) with stochastic momentum is popular in non- convex 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 a batch of examples, where the addition of a "momentum" term biases the update in the direction of the previous change optimization one show that momentum
parameters. In non-stochastic 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 stochas- tic momentum appears 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. (2088))) etc. Yet theoretical justification for the use of stochastic momentum has remained 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 second order stationary point. Our theoretical results also shed light the related question of how choose the ideal momentum parameter-owe our analysis suggests that E [0, 1) should be large (close to 1), which comports with empirical findings. We also provide experimental findings that further validate these conclusions.
INTRODUCTION
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); CCbuk et al.] (2018) Gastaldi (2017), speech recognition (e.g. Amodei 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. ( Loshchilov & Hutter (019): Wilson et al. (2017)). Sutskever 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 stochastic momentum (Algorithm) I 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. 3 = 0.9) work well in practice. It should be noted that Algorithm i is the default momentum-method in popular software
Heavy ball momentum is the default choice of momentum method in PyTorch and Tensorflow, instead of Nesterov's 's momentum, See the manual pages https: torch/opt i m/ ht/...d.r heml and hatps: www. htwp:w/eensooo we org api secildddospppppi wwwps//pttt///....ppooo keras/ opt mi zers/ SGD

---

Published as a conference paper at ICLR 2020
Algorithm 1: SGD with stochastic heavy ball momentum
1: Required: Step size parameter and momentum parameter
2: Init: we E R and m = E R.
3: for I = 0 to T do
4: Given current iterate wt, obtain stochastic gradient ga == V (((cE)).
5: Update stochastic momentum my Bm + Gt.
6: Update iterate wr+1 := We nmm
7: end for
packages such as PyTorch and Tensorflow. In this paper we provide a theoretical analysis for SGD with momentum. We identify some mild conditions that guarantees SGD with stochastic momentum will provably escape saddle points faster than the standard SGD, which provides clear evidence for the benefit of using stochastic momentum. For stochastic heavy ball momentum, a weighted average of stochastic gradients at the visited points is maintained. The new update is computed the current update minus step in the direction of the momentum. Our analysis shows that these updates can amplify a component in an escape direction of the saddle points.
In this paper, we focus on finding a second-order stationary point for smooth non-convex optimization by SGD with stochastic heavy ball momentum. Specifically., we consider the stochastic nonconvex optimization problem. gin fw) == ff E)], where we overload the notation so that fw;; <) represents a stochastic function induced by the randomness & while f (w) is the expectation of the stochastic functions. An (c, c) -eeoonnd-rrd stationary point w satisfies
[V S 6 and V2 ł -CI.
Obtaining a second order guarantee has emerged as a desired goal in the nonconvex optimization community. Since finding global minimum or even a local minimum in general nonconvex
optimization can be NP hard (Anandkumar & Ge (2016); Nie (2015); Murty & Kabadi (1877);
Nesterov (2000), most of the papers in nonconvex optimization target at reaching
approximate second-order stationary point with additional assumptions like Lipschitzness in the gradients and the
Hessian (e.g. Allen-Zhu & Li (2018); Carmon & Duchi (0018); Curtis et al. (2017); Daneshmand
et al. (2018): Du et al. (2017) 3 Fang et al. [2018 2019); Ge et al. (2015) 5); Jin et al. (2017 2019);
:
Kohler & Lucchi (2017 y Lei al. (2017): Lee et al. (2019): Levy (0116): Mokhtari et al. (2018):
Nesterov & Polyak (2006); Reddi et al. (2018) 8a); Staib et al. (2019), Tripuraneni et al. (2010)1)) 8): Xu
jet al. (2018). We follow these related works for the goal and aim at showing the benefit of the use of the momentum in reaching an ) )-seecond-order stationary point.
We introduce a required condition, akin to a model assumption made in (Daneshmand al, (2018)) that ensures the dynamic procedure in Algorithm produces updates with suitable correlation with the negative curvature directions of the function
Definition 1. Assume, at some time t, that the Hessian H, = f(w) has some eigenvalue smaller than - and V ff S Let us be the eigenvector corresponding the smallest eigenvalue of ('n). The stochastic momentum my satisfies Correlated Negative Curvature (CNC) at t with parameter 7 > if
Ex Em vz) 1 2
As we will show, the recursive dynamics of SGD with heavy ball momentum helps in amplifying the escape signal 7, which allows it to escape saddle points faster.
We show that, under CNC assumption and some minor constraints that upper- upuer-bound parameter B, if SGD with momentum has properties called Almost Positively Aligned with Gradient (APAG), Almost Positively Correlated with Gradient (APCG), and Gradient Aligument or Curvature Exploitation (GrACE), defined in the later section, then it takes T O /)) (10 iterations to return an (e, second order stationary point. A Alternatively, one can obtain an (e, ve) second order stationary point in T O(11 3) log(1/(1 B)e result demonstrates that a larger momentum parameter 8 can help in escaping saddle points faster. As saddle points are pervasive in the loss landscape of optimization and deep learning (Dauphin et al.
Contribution:
-10)
iterations. Our theoretical
We apologize that the list is far from exhaustive.
2

---

Published as a conference paper at ICLR 2020
(2014); Choromansaa al. (2115), the result sheds light explaining why SGD with momentum enables training faster in optimization and deep learning.
Notation: In this paper use E [-] to represent conditional expectation [||[w1, W2..... wy). which is about fixing the randomness upto but not including and notice that wy was determined at 1.
2
BACKGROUND
2.1 A THOUUGIT EXPERIMENT.
Let us provide some high-level intuition about the benefit of stochastic momentum with respect escaping saddle points. In an iterative update scheme, at some time 40 the parameters Wto can enter a saddle point region, that place where Hessian V f(wr.) has non-trivial negative eigenvalue, say Aminn (V2 f(wt))) -c, and the gradient Vf(w,,) is small in norm, say [[V](,;)] I c. The challenge here is that gradient updates may drift only very slowly away from the saddle point, and may not escape this region; see (Du et al. (2017); Lee et al. (2019)) for additional details. On the other hand, if the iterates were to move in one particular direction, namely along vt, the direction of the smallest eigenvector of V [wr,)) then fast escape is guaranteed under certain constraints on the step size yy see e.g. (Carmon et al. (2018)). While the negative eigenvector could be computed directly, this 2nd-order method is prohibitively expensive and hence we typically aim to rely on gradient methods. With this in mind, Dannehmand et (2018), who study non-mone momentum SGD, make an assumption akin to our CNC property described above that each stochastic gradient 9t, is strongly orthooaglla Vs the direction of large negative curvature. This suffices to drive the updates out of the saddle point region.
recape divctton I%
Myya
S6D tralectorv
SGD momentum vejectory
Figure The trajectory of standard SGD (left) and SGD with momentum (right).
In the present paper we study stochastic momentum, and our CNC property requires that the update direction Mio is strongly non non-orthogonal to tto: more precisely, E,, [m Utg/ 12 2 >> O. We are able to take advantage of the analysis of (Daneshmand et al. (2118) to establish that updates begin to escape saddle point region for similar reasons. Further, this effect is amplified in successive iterations through the momentum update when 33 is close to Assume that at some Wt, we have m4, which possesses significant correlation with the negative curvature direction Ut then successive rounds +1 is quite close to 8m,,, + is quite close to 8 and so forth; see Figure | for an example. This provides intuitive perspective how momentum might help accelerate the escape process. Yet one might ask does this procedure provably contribute to the escape process and, if so, what the aggregate performance improvement of the momentum? We answer the first question in the affirmative, and we answer the second question essentially by showing that momentum can help speed up saddle-point escape by a multiplicative factor of B. On the negative side, we also show that /3 is constrained and may not be chosen arbitrarily close to 1.
2.2
MOMENTUM HELPS ESCAPE SADDLE POINTS: AN EMPIRICAL VIEW
Let now establish, empirically, the clear benefit of stochastic momentum the problem of saddle-point escape. We construct two stochastic optimization tasks, and each exhibits at least one significant saddle point. The two objectives are follows.
min f(w) =
Hw + 6J w + || (10)
(3)
2
1=1
min fw) = ((a w)2 - y)²
(4)
Problem 3 of these was considered by (Staib et al. 2019); Reddi et al. 2018a)) and represents a very straightforward non-convex optimization challenge, with embedded saddle given by the matrix
3

---

Published as a conference paper at ICLR 2020
10
520
520 m9
-5-
on
-60 10-2
1000
2000
3200
4000
5000
Beralions
(a) Solving objective
(b) Solving objective (phase retrieval)
Figure 2: Performance of SGD with different values of B = [0, 0.3, 0.5, 0.7.0......99). 8 corresponds to the
standard SGD. Fig. 4al We plot convergence in function value [(] given in 33. Initialization is always set as the distance the true model captures progress as the global sign of the objective is unrecoverable, All the algorithms are initialized at the
we 0. All the algorithms
step size 7/ 5 10 Fig. 4b; We plot convergence in relative w= II, ||w, =" [ which more appropriately
defined as min[[]
same point wo ~ (0, Za/ (10000))) and use the same step size 5 x 10 10-1
H = diag (11, -11-1-...0 0.1]], and stochastic gaussian perturbations given by b; ~ NO, diag 0.00)):: the small variance in the second component provides lower noise in the escape direction. Here we have set n = 10. Observe that the origin is in the neighborhood of saddle points and has objective value zero. SGD and SGD with momentum they have to escape saddle points before the convergence. The second objective (4) appears in the phase retrieval problem, that has real applications in physical sciences (Candés et al. (2013); Shechtman et al. (2015)). ). In phase retrieva one wants to find an unknown w² E R² with access but few samples y; (a, w²)² the design vector a; is known priori. Here we have sampled w" ~ (0, dd) and ~ IN) with d = 10 and n = 200.
initialized at the origin in the experiment so that
The empirical findings, displayed Figure [] are quite stark: for both objectives. convergence is significantly accelerated by larger choices of 3. In the first objective (Figure 4a), we see each optimization trajectory entering saddle point region, apparent from the "flat" progress, yet we observe that large-momentur trajectories escape the saddle much more quickly than those with smaller momentum. similar affect appears in Figure (4b] To the best of our knowledge, this the first reported empirical finding that establishes the dramatic speed up of stochastic momentum for finding an optimal solution in phase retrieval.
2.3 RELATED WORKS.
The heavy ball method was originally proposed by Polyak (1964). has been observed that this algorithm, even in the deterministic setting, provides no convergence speedup over standard gradient descent, except in some highly structure cases such as convex quadratic objectives where "accelerated" rate is possible (Lessard al. (2016); Goh (2017); Ghadimi al. (2015); Sun cct al. Loizou Richtárik (2017 2018); Gadat et al. (0016); Yang et al. (2018); ) Kidambi et al. (2018) Can al. (2019)). We provide comprehensive survey of the related works about heavy ball method in AppendixIA)
Heavy ball method:
Reaching second order stationary point: As mentioned earlier, there many works aim reaching a second order stationary point. We classify them into two categories: specialized algorithms and simple GD/SGD variants. Specialized algorithms are those designed to exploit the negative curvature explicitly and escape saddle points faster than the ones without the explicit exploitation (c.g. Carmon al. (2018); Agarwal al. (2017); Allen-Zhu & Li (2018); Xu et al. (2018)) Simple
GD/SGD variants are those with minimal tweaks of standard GD/SGD or their variants (c.g. Ge et al. (2015) Levy 2016); Fang al. 2019); Jin et al. (2017) 2018 2019); Daneshmand et al. (2018):
IIt is known that phase retrieval is nonconvex and has the so- colcalled strict saddle property: (1) every local minimizer {w" - is global up to phase, (2) each saddle exhibits negative curvature (see e.g. (Sun et al. 2015: 2016): Chen 2018))
4

---

Published as a conference paper at ICLR 2020
Staib et al. (2019)). Our work belongs to this category. In this category, perhaps the pioneer works are (Ge et al. (2013) and (Jin et al. (017)). Jii et al. (2017) show that explicitly adding isotropic noise in each iteration guarantees that GD escapes saddle points and finds a second order stationary point with high probability. Following (Jin et al. (017)), Daneshmand et al. (2018) assume that stochastic gradient inherently has component escape. Specifically, they make assumption of the Correlated Negative Curvature (CNC) for stochastic gradient 9r so that E (ge, vx) 2 y > 0. The assumption allows the algorithm avoid the procedure of perturbing the updates by adding isotropic noise. Our work is motivated by (Daneshmand et al. (2018) ) but assumes CNC for the stochastic momentum my instead. In Appendix A| we compare the results of our work with the related works.
MAIN RESULTS
We assume that the gradient V is L-Lipschitz; that is. I is L-smooth. Further, we assume that the Hessian V f is p-Lipschitz. These two properties ensure that
< Lil wwwl and that f(w) V f(w'll $ pl w- w'll. Yw, w', The L-Lipschitz gradient assumption implies that w/ - = 5 --llww' w'12,, Vw, w', while the p-Lipschitz Hessian assumption implies that [[(w')/[(w)) (V)(w,, w/ -w) (ww- (')) -w)l S & fllw-woll w''Is, Vw, w'. Furthermore, we assume that the stochastic gradient has bounded noise [V Vf(w;; E)Il < o² and that the norm of stochastic momentum is bounded so that ||vmlll S Cm We denote I1, as the
matrix product of matrices {M:} and we use maaz (M) M| == sup spectral norm of the matrix M.
(s.Ma) to denote the (2,2)
3.1 REQUIRED PROPERTIES WITH EMPIRICAL VALIDATION
Our analysis stochastic momentum relies on three properties of the stochastic momentum dynamic. These properties are somewhat unusual, but we argue they should hold in natural settings, and later we aim to demonstrate that they hold empirically couple of standard problems of interest.
Definition 2. We say that SGD with stochastic momentum satisfies Almost Positively Aligned with Gradient (APAG) F if we have
[V [(w),, m. -9:) 2 [wx))1
We say that SGD with stochastic momentum satisfies A Almost Positively Correlated with Gradient (APCG) with parameter 3d such that,
fw,,,,
-c'njo max (M))I
(6)
where the PSD matrix M, is defined as
M₁ = Gr.= sm Ga.e) with
I v/1 (11 f(r))
1-3
for any integer 1 < k < -
1, 1, and is any step size chosen that guarantees each G.,, is PSD.
Definition 3. We say that the SGD with momentum exhibits Gradient Alignment or Curvature Exploitation (GrACE) 3ch 2 0 such that
E, f(wx), 9: m.) + 5 m, (2f(w)mml S 17
(7)
APAG requires that the momentum term m, must, in expectation, not be significantly misaligned with the gradient V fwx). This is a very natural condition when one sees that the momentum term is acting biased estimate of the gradient of the deterministic f. APAG demands that the bias can not be too large relative to the size of V (we). Indeed this property is only needed in our analysis when the gradient is large (i.e. V (w:))l 2 e) it guarantees that the algorithm makes progress; our analysis does not require APAG holds when gradient is small.
APCG is a related property, but requires that the current momentum term m, is almost positively correlated with the the gradient V (wx), but measured in the Mahalanobis norm induced by M,. It
'Note that our analysis still go through if one replaces& & r.h.s. of with any larger number << 1; the resulted iteration complexity would be only constant multiple worse.
5

---

Published as a conference paper at ICLR 2020
3038
000
22-
2015
om
300
Seratore
Zaraiton
-12
(a) Gradient norm [(oe)
(b) About APAG.
About APCG.
13-
1000
20:00
1003
3022
2000
2200
-002
1002
2000
3000
analow
(d) Gradient norm V fww) )l.
(c) About APAG.
(f) About APCG.
Figure 3: Plots of the related properties. Sub-figures on the top row are regarding solving 3 and sub-figures on the bottom row are regarding solving 4 (phase retrieval). Note that the function value/relative distance to w" plotted Figure Above, sub-figures (a) and (d): We plot the gradient norms versus iterations. Sub- Sub-figures (b) and (e): We plot the values of (V m. /t)/l f (w:)] versus iterations. For (b), we only report them when the gradient is large (IlV [w=)]] 2 0.02). It shows that the value is large than -0.5 except the transition. For (c), we observe that the value is almost always nonnegative. Sub-figures (c) and (f): We plot the value of
(V (we)), M,ma)/ moz (M))l fwo))l For (c), we let M, (II 10 ...)) 3x G..c) and we only report the values when the update is in the region of saddle points. For (f), we let M, (II90) (II5) G...) and we observe that the value is almost always nonnegative. The figures implies that SGD with momentum has APAG and APCG properties the experiments. Furthermore, an interesting observation is that, for the phase retrieval problem, the expected values might actually be nonnegative.
may appear to be an unusual object, but one view the PSD matrix M, measuring something about the local curvature of the function with respect to the trajectory of the SGD with momentum dynamic. We will show that this property holds empirically on two natural problems for reasonable constant c'. APCG is only needed in our analysis when the update is in a saddle region with significant negative curvature, || [V)]l S and Amin (V²f(w) < -e. Our analysis does not require APCG holds when the gradient is large or the update is at an (c, ()-eood order stationary point.
For GrACE, the first term on Lh.s of (7) measures the aligmment between stochastic momentum my and the gradient fww)) while the second term on lhh.s measures the curvature exploitation. The first term small (or even negative) when the stochastic momentum m, is aligned with the gradient fw(,). while the second term is small (or even negative) when the stochastic momentum m, can exploit negative curvature (i.e. the subspace of eigenvectors that corresponds to the negative eigenvalues of the Hessian V fwx) if exists). Overall, a small sum of the two terms (and, consequently, small Ca.) allows one to bound the function value of the next iterate (see Lemma ()).
On Figure we report some quantities related to APAG and APCG well as the gradient norm when solving the previously discussed problems (3) and (4) using SGD with momentum. We also report quantity regarding GrACE on Figure 4 in the appendix.
3.2
CONVERGENCE RESULTS
The high level idea of our amalysis follows similar template to (Jin et al. (2017); Daneshmand et al. (2018); Staib et al. 2019)) ). Our proof is structured into three cases: either (a) [ 2 e, or (b) [V]]]]] & and Amiin 2 f(w)) & -6, or otherwise (c) | (w])] and Amin (V [(w)) 2 -6

---

Published as a conference paper at ICLR 2020
Algorithm 2: SGD with stochastic heavy ball momentum
1: Required: Step size parameters and 77, momentum parameter and period parameter Tehred-
2: Init: wg E R and m = E I..
3: for I = to do
4: Get stochastic gradient at and set stochastic momentum my == _ + gt.
5: Set learning rate: = 7) unless (t mod Tehres) 0 in which case r) ;=
6: Wr41 Wt fyme.
7: end for
meaning we have arrived in a second-order stationary region. The precise algorithm we analyze is Algorithm22 2 which identical to Algorithm D except that we boost the step size to larger value on occasion. We will show that the algorithm makes progress in cases (a) and (b). In case (c), when the goal has already been met, further execution of the algorithm only weakly hurts progress. Ultimately, we prove that a second order stationary point is arrived at with high probability. While our proof borrows tools from (Daneshmand et al. (2018); Staib et al. (2019)), much of the momentum analysis entirely novel to our knowledge.
Theorem 1. Assume that the stochastic momentum satisfies CNC. - 17 O(E)). and
Tihred = <(1-9) log( Lema" pc = O((1 - log( Lom a² pd on )c-9) for some constant C > 0. If (1-8)6re
nc
(1-8)8me
SGD with momentum (Algorithm 2 has APAG property when gradient is large f(w) || 2 e).
APCGTo property when enters a region of saddle points that exhibits a negative curvature
( S and Xmin((²) [W)) -c), and GrACE property throughout the iterations, then it
reaches an (c,c) c) second order stationary point in T = 2Tthred (f (wo) min, (eFF))(8Ftbred)) =
O(11 B) log( Lema oc'en, 1011 iterations with high probability 1 5, where Fihred O(d)).
[1-B]07e
The theorem implies the advantage of using stochastic momentum for SGD. Higher B leads to reaching a second order stationary point faster. As we will show in the following, this is due to that higher enables escaping the saddle points faster. In Subsection 3.2.1, 1, we provide some key details of the proof of Theorem 1 The interested reader can read high-level sketch of the proof, as well as the detailed version, in Appendix G
Remark 1: (constraints on 9) We also need some minor constraints on 3 so that B cannot be too close to 1. They are 1) L(1 3)3 > 1, 2) a² 3)3 > 1, 3) c((1 3)² > 1, 4) S 1-3 n S 1-9 and 6) Tehred 2 1 + 1-3- Please see Appendix E. for the details and discussions.
- 5)
Remark 2: (escaping saddle points) Note that Algorithm reduces to CNC-SGD of Daneshmand
al. 2018) when 8 = 0 (i.e. without momentum). Therefore, let compare the results. We show that the escape time of Algorithm 2 is Tihred =- Ö (1=1) (see Appendix E.3.3 especially (8) ).
On the other hand, for CNC-SGD, based Table 3 in their paper, is Tihred Ō( One can clearly that Tihred of result has a dependency 1 B, which makes it smaller than that of Daneshmand et al. (2018) for any same 17 and consequently demonstrates escaping saddle point faster with momentum.
Remark 3: (finding a second order stationary point) Denote a number such that Vt, [1::1| S E. In p200 Appendix G.3 we show that in the high momentum regime where (1 - 3) << ci
Algorithm
is strictly better than CNC-SGD of Daneshmand et al. (2018), which means that higher momentum can help find a second order stationary point faster. Empirically, we find out that c' ss 0 (Figure and Cn R 0 (Figure 4) in the phase retrieval problem, so the condition is easily satisfied for wide range of 13.
3.2.1 ESCAPING SADDLE POINTS
In this subsection, we analyze the process of escaping saddle points by SGD with momentum. Denote la any time such that (fo mod Tehred) = 0. Suppose that it enters the region exhibiting a small
*See Table 3 Appendix E for the precise expressions of the parameters. Here, we hide the parameters' dependencies on %, T., Cm, c', ai P. Ch. and 8. W.l.o.g, we also assume that Cm, I,, a² d' Ch, and p are not less than and < 1.
7

---

Published as a conference paper at ICLR 2020
gradient but a large negative eigenvalue of the Hessian (i.e. [ S and Amin (V fwwt)) S -e). We want to show that it takes at most Tihred iterations to escape the region and whenever escapes, the function value decreases at least by Fthred O(e*) on expectation, where the precise expression of Fihred will be determined later in Appendix F The technique that we use is proving by contradiction. Assume that the function value on expectation does not decrease at least Fthred in Tihred iterations. Then, we get an upper bound of the expected distance Er, (oo + Taared wt.ll S Cupper. Yet, by leveraging the negative curvature, we also show a lower bound of the Wto [| 2 Clower The analysis will show that the lower bound is larger than the upper bound (namely, Clower > Cupper), which leads to the contradiction and concludes that the function value must decrease at least Fehred Tehred iterations on expectation. Since Tihred = 0 3) log( (T- ) the dependency on 8 suggests that larger 3 can leads to smaller Tihred, which implies that larger momentum helps in escaping saddle points faster.
form B
Lemma Thelow provides an upper bound of the expected distance. The proof is in Appendix C
Lemma Denote lo any time such that (lo mod Tshred) = O. Suppose that Eng [[ [w)+ S Fthoeed for any O S S Tehred- Then, Bio Biolllrtt+ wroll²) S Cupper.t
to² Byd Fehraat2r2 cm. 8n7 (1-3)2 + 4172 (1 222 + +r2²c2
(1-8)²
We see that Cuppera in Lemma is monotone increasing with f, so we can define Capper == Cupper, Cusper,Tsteeaa Tshwedd Now let us switch to obtaining the lower bound of E,, IllWta lower bound comes from the recursive dynamics of SGD with momentum.
Wto 11 The key to get the
Lemma 2. Denote to any time such that (to mod Tehred) O. Let define quadratic ap- proximation at Wt, Q(w)= == f(wer) + (w Wes vf(W(.)) + 2ww - wt,) H(w - (ww)),,)+ where
H = 2 fw..). Also, define G. = (1 n Ei=1 H)) Then we can write Woot Wto exactly using the following decomposition.
8m
1I G - rmm))
+m
II |=8+1 G G
8-.4-1
n (-1)
mm-1
8 35-k j=x+1 Gj) Σ
N-S - VQ(Weg+s))
s=1
k=
n (-11
G3) nm -
g g f(we)) tn (
[II 141 Gj)
g Stotk ga-k
The proof of Lemma is in Appendix Qu,t-1, 9m.t-1, 4q.1-1, 1w - as defined above throughout the analysis.
D Furthermore, we will use the quantities
Lemma 3. Following the notations of Lemma we have that
EeG Be 11 2 Euolllla.--al1]) (1,,t-1 tm..mmmmmm11....m 1w..----..----//.. =: Owwer
We are going to show that the dominant term in the lower bound of E., Illwb - wto || is Esg 1..l which the critical component for ensuring that the lower bound is larger than the upper bound of the expected distance.
Lemma 4. Denote 82 := E Bi-k =
gh-1 and == -Amin(H) Following the condi- tions and notations in Lemma 1 and Lemma we have that
1l (IT (1 2,..
Proof. We know that Amin (H) < -e < Let be the eigenvector of the Hessian H with unit norm that corresponds to Amin ()) that He Amiu (H)v. We have (T-n) v qnmin (H)e
8

---

Published as a conference paper at ICLR 2020
(1 - 77min (H))u. Then,
Big (0ll - [1 (e) Ero I1l 11 [110111] 2 Ero 11 (c)
(8)
Eta [ (((TT] e)
@ Eto ((T) ,10 H) rm w) Er (1T) ,10 Amin (mmn((H)))mmmapp u)) u)
(9)
(u + n0, 7
where (a) is because is with unit norm, (b) is by Cauchy-Schwarz inequality, (c), (d) by the definitions, and (e) is by the CNC assumption so that EE, [m,, e) 2 7-
Observe that the lower bound in (8) is monotone increasing with and the momentum parameter 3. Morcover, it actually grows exponentially in t. To get the contradiction, have show that the lower bound is larger than the upper bound. By Lemma and Lemma 3 it suffices to prove the following lemma. We provide its proof in Appendix
Lemma 5. Let Fthred O)ea) and oj TeTrre 1², By following the conditions and notations in
Theorem [ Lemma and Lemma 2 we conclude that if SGD with momentum (Algorithm 2 has the
APCG property, then we have that Clower = Eig lll Terreee
[1 2ny kg,, (Theee 1 9m, Terved
qg. NgTTawraa-1 + Tw.Tsrred + qg, 11) Cupper.
4 CONCLUSION
In this paper, we identify three properties that guarantee SGD with momentum in reaching second- order stationary point faster by higher momentum, which justifies the practice of using large value of momentum parameter B. We show that greater momentum leads to escaping strict saddle points faster due that SGD with momentum recursively enlarges the projection 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 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.
ACKNOWLEDGMENTS
We gratefully acknowledge financial support from NSF IIS awards 1910077 and 1453304.
REFERENCES
Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma. Finding approximate local minima faster than gradient descent. STOC, 2017.
Zeyuan Allen-Zhu and Yuanzhi Li. Neon2: Finding local minima via first-order oracles. NeurIPS, 2018.
Dario Amodei, Sundaram Ananthanarayanan, Rishita Anubhai, and et al. Deep speech 2 End-to-end speech recognition in english and mandarin. ICML, 2016.
Anima Anandkumar and Rong Ge. Efficient approaches for escaping higher order saddle points in non-convex optimization. COLT, 2016.
Bugra Can, Mert Gürbüzzalaban, and Lingjiong Zhu. Accelerated linear convergence of stochastic momentum methods in wasserstein distances. ICML, 2019.
Emmanuel J. Candés, Yonina Eldar, Thomas Strohmer, and Vlad Voroninski. Phase retrieval via matrix completion. SIAM Journal on Imaging Sciences, 2013.
Yair Carmon and John C. Duchi. Gradient descent efficiently finds the cubie-regularized non-convex newton step. NeurIPS, 2018.

---

Published as a conference paper at ICLR 2020
Yair Carmon, John Duchi, Oliver Hinder, and Aaron Sidford. Accelerated methods for nonconvex optimization. SIAM Journal of Optimization, 2018.
Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, and Yuling Yan. Gradient descent with random initialization: Fast global convergence for nonconvex phase retrieval. Mathematical Programming, 2018.
Anna Choromanska, Mikael Henaff, Michael Mathieu, Gérard Ben Arous, and Yann LeCun. The loss surfaces of multilayer networks. AISTAT, 2015.
Ekin D Cubuk, Barret Zoph. Dandelion Mane, Vijay Vasudevan, and Quoe V Le. Autoaugment: Learning augmentation policies from data. arXin:/805.09501, 2018.
Frank E. Curtis, Daniel Robinson, and Mohammadreza Samadi. A trust region algorithm with worst-case iteration complexity of o(e-3/2) for nonconvex optimization. Mathematical Program- 2017.
ming, 2017.
Hadi Daneshmand, Jonas Kohler, Aurelien Lucchi, and Thomas Hofmann. Escaping saddles with stochastic gradients. ICMI, 2018.
Yann Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio. Identifying and attacking the saddle point problem in high-dimensional non-convex optimization. NIPS, 2014.
Simon S. Du, Chi Jin, Jason D. Lee, Michael Jordan, Barnabas Poczos, and Aarti Singh. Gradient descent can take exponential time to escape saddle points. NIPS, 2017.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic auth-integrated differential estimator. NeurIPS, 2018.
Cong Fang, Zhouchen Lin, and Tong Zhang. Sharp analysis for nonconvex sgd escaping from saddle points. COLT, 2019.
Sébastien Gadat, Fabien Panloup, and Sofiane Saadane. Stochastic heavy ball. 1609v:1609.040 04228. 2016.
Xavier Gastaldi. Shake-shake regularization. arXiv:1705.07485, 2017.
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points - online stochastic gradient for tensor decomposition. COLT, 2015.
Euhanna Ghadimi, Hamid Reza Feyzmahdavian, and Mikael Johansson. Global convergence of the heavy-ball method for convex optimization. ECC, 2015.
Saeed Ghadimi and Guanghui Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 2013.
Saced Ghadimi and Guanghui Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Mathematical Programming, 2016.
Gabriel Goh. Why momentum really works. Distill, 2017.
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image
recognition. Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
Elad Hoffer, Itay Hubara, and Daniel Soudry. Train longer, generalize better: closing the generaliza- tion gap in large batch training of neural networks. NIPS, 2017.
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M. Kakade, and Michael I. Jordan. How to escape saddle points efficiently. ICML., 2017.
Chi Jin, Praneeth Netrapalli, and Michael I. Jordan. Accelerated gradient descent escapes saddle points faster than gradient descent. COLT, 2018.
10

---

Published as a conference paper at ICLR 2020
Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M. Kakade, and Michael I. Jordan. Stochastic gradient descent escapes saddle points efficiently. arXiv:1902.04811 2019.
Rahul Kidambi, Praneeth Netrapalli, Prateek Jain, and Sham M. Kakade. On the insufficiency of existing momentum schemes for stochastic optimization. ICLR, 2018.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. ICLR, 2015.
Jonas Moritz Kohler and Aurelien Lucchi. Sub-sampled cubic regularization for non-convex opti- mization. ICML, 2017.
Alex Krizhevsky, lly Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep convolu- tional neural networks. NIPS, 2012.
Jason D. Lee, loannis Panageas, Georgios Piliouras, Max Simchowitz, Michael Jordan, and Benjamin Recht. First-order methods almost always avoid strict saddle-points. Mathematical Programming. Series B, 2019.
Lihua Lei, Cheng Ju, Jianbo Chen, and Michael I. Jordan. Nonconvex finite-sum optimization via scsg methods. NIPS, 2017.
Laurent Lessard, Benjamin Recht, and Andrew Packard. Analysis and design of optimization algorithms via integral quadratic constraints. SIAM Journal on Optimization. 2016.
Kfir Y. Levy. The power of normalization: Faster evasion of saddle points. arXiv:1611.044 161,:1611,,4,,,,,, 2016.
Nicolas Loizou and Peter Richtárik. Momentum and stochastic momentum for stochastic gradient, newton, proximal point and subspace descent methods. arXiv:1712.09677, 2017.
Nicolas Loizou and Peter Richtárik. Accelerated gossip via stochastic heavy ball method. Allerton, 2018.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. ICLR, 2019.
Aryan Mokhtari, Asuman Ozdaglar, and Ali Jadbabaie. Escaping saddle points in constrained optimization. NeurIPS, 2018.
Katta G Murty and Santosh N Kabadi. Some np-complete problems in quadratic and nonlinear programming. Mathematical programming, 1987.
Yurii Nesterov. Squared funetional systems and optimization problems. High performance optimiza- fion, Springer, 2000.
Yurii Nesterov. Introductory lectures on convex optimization: basic course. Springer, 2013.
Yurii Nesterov and B.T. Polyak. Cubic regularization of newton method and its global performance. Math. Program., Ser. A 108, 177-205, 2006.
Jiawang Nie. The hierarchy of local minimums in polynomial optimization. Mathematical program- ming, 2015.
Peter Ochs, Yunjin Chen, Thomas Brox, and Thomas Pock. ipiano: Inertial proximal algorithm for nonconvex optimization. SIAM Journal of Imaging Sciences, 2014.
B.T. Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computa- tional Mathematics and Mathematical Physics, 1964.
Sashank Reddi, Manzil Zaheer, Suvrit Sra, Barnabas Poczos, Francis Bach, Ruslan Salakhutdinov, and Alex Smola. generic approach for escaping saddle points. AISTATS, 2018a.
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. ICLR, 2018b.
Yoav Shechtman, Yonina C. Eldar, Oren Cohen, Henry Nicholas Chapman, Jianwei Miao, and Mordechai Segev. Phase retrieval with application to optical imaging: a contemporary overview. IEEE signal processing magazine, 2015.

---

Published as a conference paper at ICLR 2020
David Silver, Julian Schrittwieser, Karen Simonyan, and et al. Mastering the game of go without human knowledge. Nature, 2017.
Matthew Staib, Sashank J. Reddi, Satyen Kale, Sanjiv Kumar, and Suvrit Sra. Escaping saddle points with adaptive gradient methods. ICML, 2019.
Ju Sun, Qing Qu, and John Wright. When are nonconvex problems not scary? NIPS Workshop on Non-convex Optimization for Machine Learning: Theory and Practice, 2015.
Ju Sun, Qing Qu, and John Wright. A geometrical analysis of phase retrieval. International Symposium on Information Theory, 2016.
Tao Sun, Penghang Yin, Dongsheng Li, Chun Huang, Lei Guan, and Hao Jiang. Non-ergodic convergence analysis of heavy-ball algorithms. AAAI, 2019.
lyy Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. ICML, 2013.
T. Tieleman and G. Hinton. Rmsprop:
Divide the gradient by running average of its recent magnitude. COURSERA: Neural Networks for Machine Learning, 2012.
Nilesh Tripuraneni, Mitchell Stern, Chi Jin, Jeffrey Regier, and Michael Jordan. Stochastic cubic regularization for fast nonconvex optimization. NeurIPS, 2018
Ashish Vaswani, Noam Shazeer, Niki Parmar, and et al. Attention is all you need. NIPS, 2017.
Ashia C Wilson, Rebecca Roelofs, Mitchell Stern, Nathan Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. NIPS, 2017.
Yi Xu, Jing Rong, and Tianbao Yang. First-order stochastic algorithms for escaping from saddle points almost linear time. NeurIPS, 2018.
Tianbao Yang. Qihang Lin, and Zhe Li. Unified convergence analysis of stochastic momentum methods for convex and non-convex optimization. ICCAI, 2018.
A LITERATURE SURVEY
The heavy ball method was originally proposed by Polyak (1664). has been observed that this algorithm, even in the deterministic setting. provides no convergence speedup over standard gradient descent, except in some highly structure cases such as convex quadratic objectives where an "accelerated" rate is possible (Lessard et al. (2016); Goh (2017). In recent years, some works make some efforts in analyzing heavy ball method for other classes optimization problems besides the quadratic functions. For example, Ghadimi al. (205)) prove O(1/T) ergodic convergence rate when the problem smooth convex, while Sun et all (2019) provide a non-ergodic convergence for certain classes of convex problems. Ochs al. (2014) combine the technique of optimization problem. For stochastic heavy ball method, Loizou & Richtárik (2017) analyze class of linear regression problems and shows a linear convergence rate of stochastic momentum, in which the linear regression problems actually belongs to the case of strongly convex quadratic functions. Other works includes (Gadat et al. (2016)), which shows almost sure convergence to the critical points by stochastic heavy ball for general non-convex coereive functions. Yet, the result does not show any advantage of stochastic heavy ball over other optimization algorithms like SGD, Can et al. (2019) show an accelerated linear convergence to a stationary distribution under Wasserstein distance for strongly convex quadratic functions by SGD with stochastic heavy ball momentum. Yang et al. (2018) provide a unified analysis of stochastic heavy ball momentum and Nesterov's 's momentum for smooth non-convex objective functions. They show that the expected gradient norm converges rate O(1/L). Yet, the rate is not better than that of the standard SGD. We are also aware of the works (Ghadimi & Lan [0166] 2013)), which propose some variants of stochastic accelerated algorithms with first order stationary point guarantees. Yet, the framework in (Ghadimi & Lan (016 2013)) does not capture the stochastic heavy ball momentum used in practice. There is also negative result about the heavy ball momentum. Kidambi et al. 2018) show that for specific strongly convex and
Heavy ball method:
splitting with heavy ball method for a specific class of nonconvex
(eethod,LLizouu
12

---

Published as a conference paper at ICLR 2020
DAGE
-G0 10-2
-000
PCDICA +0.7
-800
1900
2000
3000
4000
5000
Baralons
(a) About GrACE for problem
(b) About GrACE for problem (phasc re- trieval).
Plot regarding the GrACE property. We plot the values of (e 2 2n2mm Heme versus
Figure 4:
o? iterations. An interesting observation is that the value is well upper-bounded by zero for the phase retrieval problem. The results imply that the constant o₁ is indeed small.
strongly smooth problem, SGD with heavy ball momentum fails to achieving the best convergence rate while some algorithms can.
Reaching a second order stationary point: As we mentioned earlier, there are many works aim at reaching a second order stationary point. We classify them into two categories: specialized algorithms and simple GD/SGD variants. Specialized algorithms are those designed to exploit the negative curvature explicitly and escape saddle points faster than the ones without the explicit exploitation (e.g. Carmon al. (2018); AAgawal al. (2017); AAllenZhu & Li (2018); Xu et al. (2018) Simple
GD/SGD variants are those with minimal tweaks of standard GD/SGD or their variants (e.g. Ge et al. (2015); Levy (2016); Fang al. (2019); Jin et al. (2017) 2018: 2019); Daneshmand et al. (2018);
Staib et al. (019)). Our work belongs to this category. In this category, perhaps the pioneer works are (Ge et (2115) and (Jin et al. (017 Jin et al. (2017) show that explicitly adding isotropic noise in each iteration guarantees that GD escapes saddle points and finds a second order stationary point with high probability. Following (Jin al. (2077). Daneshmand et al. (2018) assume that stochastic gradient inherently has a component to escape. Specifically, they make assumption of the Correlated Negative Curvature (CNC) for stochastic gradient ge so that R. ((ge, ex) 2 27 > 0. The assumption allows the algorithm to avoid the procedure of perturbing the updates by adding isotropic noise. Our work is motivated by (Dancshmand et al. (2018)) but assumes CNC for the stochastic momentum m, instead. Very recently, Jin et al. (019) consider perturbing the update of SGD and provide a second order guarantee. [Staib et al. 2019) consider a variant of RMSProp (Tieleman & Hinton (012)), in which the gradient 9. multiplied by a preconditioning matrix G, and the
update is W[+1 = Wi - G. 1/2 gt. The work shows that the algorithm can help in escaping saddle points faster compared to the standard SGD under certain conditions. |Fang et al. (2019) propose average-SGD, in which a suffix averaging scheme is conducted for the updates. They also assume an inherent property of stochastic gradients that allows SGD escape saddle points.
We summarize the iteration complexity results of the related works for simple SGD variants on Table The readers can see that the iteration complexity of (Fang et al. (2019) and (Jin et al. (2019) are better than (Daneshmand et al. (2018); (Staib et al. (2019) and our result. So, we want to explain the results and clarify the differences. First, we focus on explaining why the popular algorithm, SGD with heavy ball momentum, works well in practice, which is without the suffix averaging scheme used in (Fang et al.) (2019) and is without the explicit perturbation used in (Tin et al. (2019)). Specifically, we focus on studying the effect of stochastic heavy ball momentum and showing the advantage of using it. Furthermore, our analysis framework built on the work of (Daneshmand et al. (2018)). We believe that, based on the insight in our work, one can also show the advantage of stochastic momentum by modifying the assumptions and algorithms (Fang et al. (2019)) (Jin et al. (2019) and consequently get better dependency e.
We follow the work (Daneshmand al. (0118) for reaching (e, e)-stationary point, while some works for an (e, -e)-stationary point. We translate them into the complexity of getting (c, e)-stationary point.
13

---

Published as a conference paper at ICLR 2020
Algorithm
Complexity
Perturbed SGD (Ge et al.
(0155)
O 16)
Average-SGD Fang et al.
2019
Ole
Perturbed SGD (Jin et al.
2019))
O(e 3)
CNC-SGD (Daneshmand et al. (0088)
O(c-10)
Adaptive SGD (Staib et al, (
D(c-"))
SGD+momentum (this work)
O((1 - () log( (1-8)e 10)
Table 1:
Iteration complexity to find an (c, second-order stationary point.
B LEMMA 6 7 AND 8
In the following, Lemma 7 says that under the APAG property, when the gradient norm is large, on expectation SGD with momentum decreases the function value by a constant and consequently makes progress. On the other hand, Lemma 8 upper-bounds the increase of function value of the next iterate (if happens) by leveraging the GrACE property.
Lemma 6. If SGD with momentum has the APAG property, then, considering the update step W4+1 = Wt - Ti we have that [e[f(w(+)) S f(w.) 21l Ln c
Proof. By the T-smoothness assumption,
La7² ||m
f(w++1) & f( +
2
Lni²
<f(w:)-n'' (((:))><(V[(w:)..l)) V(Vf(w:) 9t) +
(10)
2
Taking the expectation on both sides. We have
Lipc cm
E,[f(wr+1) & f(w)) - me 91)]+
2
Lni²
< f(w,) - [V:((=))]
(11)
2
where we use the APAG property the last inequality.
Lemma 7. Assume that the step size n satisfies S APAG property, then, considering the update step Wt+1 W/ mi, have that E. (1((()) S f(w) 4e² when || f(w))l Ze.
8Leg If SGD with momentum has the
Lemma
(w:)) 2 (V Lup
Proof. IE, (4]f(we)))- ((w]]
4e² 0
where the last inequality is due to the constraint of 17.
Lemma 8. If SGD with momentum has the GrACE property. then, considering the update step Wr+1 Wt 1y14, we have that [e[s(wr+1) f(w:) vich en
Proof. Consider the update rule w4+1 = wt - rym, where m, represents the stochastic momentum and 1j the step size. By p-Lipschitzness of Hessian, have f(w,+1) S f(w.) - ry (w,) g.) (Vf mm) + m, f² + eg" |mm]] Taking the conditional expectation, one has
[. < ((w.) - E, [vl V [ + (.l[VV((w))) 9: m.) + n/ - m (2I(w))
pn
6 m
pm
< ((w)) + 0 + 2c,
6 cm
(12)
14

---

Published as a conference paper at ICLR 2020
C
PROOF OF LEMMA 1
Lemma [Witttt)
Denote to any time such that (fo mod Tehred) O. Suppose that Big (f
I Fihred for any 0 S t Tehred. Then,
Big alllwtttt Wto 12 2 Cupper.t
= 8nt [Fthred + c2 + g cm)
(m)))))
to
+ S1p²
+ 417
2
2
(1-
(1 3)2
(13)
Proof. Recall that the update is Wto+1 Who -rmggs and Wtott Wto+t-1 +1 We have that
for fort 1.
|Woote - wool? 2 2( Wro+t Who+ 112 + || wto wtoll S 2| Who Who+ 112 2 2r²
(14)
where the first inequality is by the triangle inequality and the second one is due to the assumption that ||mell S Cm for any t. Now let denote
a₂ = 2j=0 3
A-1 E1=1 as
and rewrite Jr ([(e)) + Ee, where & is the zero-mean noise. We have that
Ei [11o0ot w6--1111 = Exolll
mom [|2] = Ero [n
ge-3 glots) - 3 3²m=))l'
#=1
< LEol22n [2n²)
ΣΣ
80 Moo+ill + +221211
Σ M 3
#=
[-1
< Eeg 12n2
Σ
8 gto+ill 110+)1111++0 [11]+2n2 2n12
) c
1 B
=1
I-1
= Eeg 1272
Σ
aggrotel +e 11 +122" 217²(
cm
1 B
= =E,,
0. (V[(Wo++))++ + E10+ 2n²2
1- (1-1)² jm
)mmm
B
< Eeg 1472
Σ a, V W.W. 11 Eeg [4n21] Σ a +ol 11 2,72
(-B) (--
3
(15)
To proceed, we need to upper bound E,, [41)]
E!= a,
V fw(o++))11)
We have that
Eg 24
Σ a V
t-1
+))
(a)
E.o
[4nr
as
V Vf(w
A,
s=1
A
f( 1| (c)
E,,14 (4,7
V
< E, [4n
ff
1-2 3
(1 - 3)
(16)
15

---

Published as a conference paper at ICLR 2020
where (a) is by Jensen's 's inequality, (b) is by max, as I 1-8. and (c) by Ac-1 1-3. Now let us switch bound the other term.
attto + 119 = = (Bro
a,a to + Eio Σ
tattotastotal)
2cT
4n Bto
ast stoutsl..
T
(6)
la²
S 4n
(17)
(1 B)
where (a) is because Erg + = for H (6) is by that ||&.|| s 0² and max, at S Combining (14). 15). (16).
1
T-Ø
Eeglllwt++ - Wto 121 S Esp [81]
V f( w + 8n)
(1- B)2 + +47²
to 2
3
)2 Cm + 2rr2 cm.
(1- 3)2
1 1 B
(18)
Now we need to bound R., 1 |V (Wr [11] By using p-L.ipschitzness of Hessian, we have that
(wotots S ((woo ( (VV[(Wttts-))) mto + 2"/ " m (
P 6" |
(19)
By adding (V both sides, we have
W/V[((who+t-11)9900--- S (Wbo++--) [[Weott) + 7 ( 10ott0--1-1111 -10+s-1
-
17 m, T + 1 6 1 07011mooto-211
(20)
Taking conditional expectation both sides leads to
E ( I (f
- [(Wto+s)] + +17ch + p
6"
m:
(21)
where -1- ( (Wio++-1) 1), Iooto-1 m + 11/ 40 4 V [WWl[[Wo 1 5
n72ch by the GrACE property. We have that for to I to +
Es, [nl V ([ Er, Ex [1]] / ( 1)]
Er, [Eo (f -aaii-i))-f((utuu (w((++))] + 17c,
n
p
6
E. [f(Woo+s-))) ((Wto+s)] ) 772 ch
P n
(22)
6
Summing the above inequality from 3, ........ leads to
m V
1 (Wee++e) + Eio Ewooo(wo S(wb,) + ((wr)) s(wio++) + - -1)ch +
E1, (w
1)ch
P 1 (t)cm
6
6 L 1)
Rrg (s( [wrr)) + Fihred + 12(11 1)ck + 6 17 1))r
(23)
where (a) is by the assumption (made for proving by contradiction) that Er, [f f( 2
Fihred for any 0 < < Tahrea- By (2I) with = and we have
E (f(,, E, (ww.) f( + r2 c/ + p c cm.
(24)
16

---

Published as a conference paper at ICLR 2020
By 23 and 24
know that
E1o [IVos(tttts)1 (1
E.o
nl V f (woo+s))1
Fihred +
L
cm + rccc + Grric
6
(4)
2 Fihred 2r +
m + L
6¹ pr²
6
(6) 2 Fihred + cr +
L
grag mm
(25)
3
where (a) is by the constraint that n2t S 12 for S t S Tthred and (b) by the constraint that r 2 1). By combining (25) and (18)
to
B 2 222
Beg Wolote Who
121 S Eeg [81]
(1 B)3
V (w (wooo+))))1 +812
(1-3)2
+
4n/
( B
Cm + 2r
(ntrre + 2r 3r)
to
+ 811
+
217
2.2
mm + 2r
(1 - 882
(1 - 3)2
1 3
(26)
17

---

Published as a conference paper at ICLR 2020
D PROOF OF LEMMA AND LEMMA 3
Lemma 2 Denote tu any time such that (to mod Tehred) 0. Let define quadratic ap-
proximation at Wt, Q(w) == f((wr) + (w Who Vf(ww.)) + 2 (w - wt,) H(w Wt,). where
H = V2 fwro). Also, define G. = (1 Ei-i 8 (H and
Qut-11 == (1) (-rmt))
9m,t-1 == - (m)= G3) 8'm
maa-
9p1-1 1= E.-l (د Gj) Σi=1 8 (V vQ(Wio+=)).
quit=1 :o:t-:==-0
- - G3) Ex=1 8 V((wr))
96,1-1
III |= G3) E== 8 Elotk
Then, Whatt - Who = q0,t-1 + Mm + 1]g + 1/m,tt1 1 + 1---111-
Notations:
Denote to any time such that (to mod Tehred) = O. Let us define quadratic approximation at
Whgt
(ww) s(wro)) + (w wha vs(uro)) + 1 (w wro) T H(w Wto): (27)
2
where H = 22 s(Wto). Also, we denote
G. == (1 8*
Um,
3 ga (V((Weo+H) - VQ(We++s)
Ug.0 =
1=
(28)
3 kV ((wro)
Tw.
1=1
30 ge-ke
Ug
Cta+k
0₂
ga-k
km
Proof. First, rewrite ma++ for any j 2 1 as follows.
3' +
g k
Mintj
glot
km
(29)
= =33mm +
3
+ Elotk).
k=1
18

---

Published as a conference paper at ICLR 2020
We have that
Wtot!
Who
-to+t-1-
w/o
Woott-1
Wto
17555-1m4
+
81-1-k (V-(w(()() + +to+&))
k=1
t-1
8 g1-1-k (10+s-1)
Wiote-1
Wio
11
k=1
(g
mlo
+
gr 1-k
(V (V((oo++ - VQ( + (to-k)
k=1
(c)
8 (H wto) + V
Wiott-1
W/o
1)
4-1
(1(( mioo
+
ge-1- (V - VQ(W + Sto-R))
= (1
H) ( -whr wio)
k=
-n mia
g
- VQ(Wa+t-1) + Vf(w)) + Elo+k)),
(30)
where (a) is by using 29 with 1 (b) is by subtracting and adding back the same term, and (c) is by (Q(
f((wt,) H (Wtottt-1 Wto)). ).
To continue, by using the nations in we can rewrite
30 as
Whot Wto G (t 11o+t11- Wts) 17 (1mm + u + Uw + v2,--1)- (31)
Recursively expanding 31 leads
Wtott - Wto G (Woote- Wro) (mmmm--11 1g-e1 ow--1 + Vg
= =G- (Wto wro) 17 Umme-22 2 + 1g.0-2 Uwoet + vg,e-2)
1/mm,m111 + 0g.e-1 + Tw + 2/22-11)
(a) (II) Gj) (Woo+1 -woo 17
1-1
(32)
[1I j Gj) (Um,s + Ugo + owr + Ug.0):
s=1
(m+= (-rm)))
(IT- j=s+1 Gj) (vm, + Ug, Vais + Ug.e);
where (a) we use the notation that I = Go x Ge+1 x ................................ G--1 and the notation that G1 = and (b) is by the update rule. By using the definitions of {g.,--}} in the lemma statement, we complete the proof.
Lemma Following the notations of Lemma we have that
Eg, (ll Weo 12] 2 E,, pll.l...---1" + 27, (gu,t-1, Im,e-1 99.111 + Tw qc,--1)) == Clower
(33)
Proof. Following the proof of Lemma
we have
Who +t
Whg
Qu.t-1 7 7mmm2-1 + qg.t-1 1 Jurtt1 + 9g.0-1).
(34)
19

---

Published as a conference paper at ICLR 2020
Therefore, by using ||a + b1l² 2 ||a||2 + 2(a,b);
Eo |oo wt.l 2 E.o [lll,,,,-1lf 11 + Eny [ 1, 4mnt11 + 2g.t-1 + Qu,t-1 + qg1--1)]
(35)
20

---

Published as a conference paper at ICLR 2020
E PROOF OF LEMMA 5
Lemma
Let Fthred = (e))) and Tehred S. 22 By following the conditions and notations in
Theorem I Lemmaαaand Lemma 2 we conclude that SGD with momentum (Algorithm 2 has the
APCG property, then we have that Clower == Bi, Tu, Tuhree 11] + Totrerd
Tikred -
9m, Tehred
Ag.Torrea-1 + qurTere -1 + 96, Tehrea-1) Cupper.
Table 3: Constraints and choices the parameters.
Parameter
Value
Constraint origin
constant
C+ < PLo Co 1152
r-ye 2 or
644. (65 (66
6 pLotot 33
pho (1 -880p
6.Febred from (89 89h
8t on
64
S c pl
e2
24
20
11 r/v three from
39
87
89
11 min 11-81
from 45
78
Fshred
6
665
86g
Fshred
Fshred S c'r from 88
g
Tahred
Tehred 2 ol--8) 8)
log(
hemo pc
from (82
(1- 8y87e
W.l.o.g. we assume that Cm, L, 0², c' Ch. and p are not less than one and that S
E.
SOME CONSTRAINTS ON B.
We require that parameter /3 is not too close to so that the following holds,
1) L(1 8)3 > 1.
2) o - 8)$ 1.
dl 8)2
4) S 1- T.
5) 1-
6) Tebred 2 c(1-9) log( Lend pc oz 1)-8e
28 2 1 + 1-9"
The constraints upper-bound the value of B. That is, 3 cannot be too close to 1. We note that the 3 dependence on I., a, and e' are only artificial. We use these constraints in our proofs but they are mostly artefacts of the analysis. For example, if function is L-smooth, and L 1, then it is also 1-smooth, so we can assume without loss of generality that L > 1. Similarly, the dependence on is not highly relevant, since we can always increase the variance of the stochastic gradient, for example by adding an O(1) gaussian perturbation.
21

---

Published as a conference paper at ICLR 2020
E.2 SOME LEMMAS
To prove Lemma 5 we need series of lemmas with the choices of parameters on Table
Upper bounding Er, 111
Lemma 9. Following the conditions in Lemmal 1 and Lemma
we have
LL
E [_llllg---111 IIl] (1 + v0,2))
6(1 - -3
[ + 170,2)) p 8(Fehred + 2r +
(36)
--3
1762
-1-
1T 1 (1 ,)) (8
[1-3)z
"²0²
+ 4vj²
1-3
8
c. +
2r
1-3
2nc
Proof.
t-1
9. = Bx,l
[II -= Gj) Σ 8 (V VQ (((w)++))))
==1
IA (a)
Bio
-
-1 Gj) Σ
V ( (Q(wbo++))]I
x=1
IN
Bio
(
g ( (Q(w,-ss) II]
k=1
Rio
(m
( Gj)lla Σ go (V](w))+*) VQ(W)--))
(0) S E1o
Σ
I1 11 1 G.)ll
(*V - VS( ([V)(())+
+ || (wio+))) - (Q(woo+))l))
(37)
where (a), (c), (d) is by triangle inequality, (b) is by the fact that ||Ax||2 < ||A|||////| for any matrix and vector æ. Now that we have an upper bound of (W(to V[(ttt++
(6) (w V ((( )l 2 L| Wis+ - Lnn( k)
(38)
where (a) is by the assumption I.-LLipschizz gradient and (b) by applying the triangle inequality (s k) times and that l|w,- w/-1ll || m1 770m, for any We can also derive upper bound of EE, [( - (Q(ww+++))
E.G [II V ([(wr++)) (Q(Wor++))]]
(a)
(b) o 8ns( Fihred + 2r + (r3c2))
2202 (1-
Baol |ooot 11]
(1 18)2
3)2
+
2
8
m
2r2
(39)
Above, (a) by the fact that function f(-) has p Lipschitz Hessian, then
(V/(') Vf(x) - -² - x)1l < fll x]|
(40)
(c.f. Lemma 1.2.4 in Nesterov 2013 and using the definition that
1 2( wt H(w - w(a):
Q(w) == f(w),) + (w - w (.(W)))) +
2
22

---

Published as a conference paper at ICLR 2020
(b) is by Lemma Jand n/a S r² for 0 5 Tthred
Eeo Wkot wto 19 8xpt (ntteed
+ 2 + gra Cm
to?
B )²²,
+ 8np
+ 4n72
1 1-3 3)
2 cm
(1 (1- 31-
(1 3)3
(Fireed + cn + gr m
0²0²
+8 (1 - 9)
+ =/172(
)2 cm + 2r.
(1 11-
1- 3
(41)
Combing
37
38
39
we have that
Eea fealllg..-- |||
|| j=
+ Σ
8 kb (IVS - VS(w)++s)l + [|V - VQ(w+++s
39
(1) - G
Σ
go
k)Cm
k=1
(1 G3) 22 Σ
3 30-k2
xP
811s (Fehred + 2r + -rrrcm
3
cm)
+
r²o²
-nn
3
)²2, cm + 2m)
(1-
(1 -)3
1 B
1-1
= Σ E1l G;)ll
3
BnnkLnns Lnns - k) +
Σ ( Σ 3o &P
/ (v/ + v).
(42)
where on the last line we use the notation that
Ug S1js Sins( (itheed + +2r²ch + (grimmm) m
(1 (1- -)2
(43)
0²0²
V :==3 8 (1 - 3)2
+ +4n
1-33 3 cm + 2r
2
To continue, let us analyze [1T Gj)li ||2 first.
= |TT (T - 3 gi
k=1
(a) $ n - (1 + (1+
11 (1 70₂2) (0)
(1+
(44)
11 (1 + n0,A)
(1 + mE)*
Above, we use the notation that 02 = Σk=1 gi For (a), it is due to that X == -Amin (H), Amax(H) < L, and the choice of so that 1 2 1-3. or equivalently,
n4
1 1-3 n S
(45)
I
For (b), it due to that 0, 2 1 for any j and X 2 e. Therefore, we can upper-bound the first term on r.h.s of (2
110 112
8
*onKLnns k)cm Σ E G;)122
3 Lncm
k=1
3
(11 1 112
Lnnc
(1 3)2
(1 + ,)0,aa)
(1 B)
(1 + nc)
3Lmcm
BLem
(1 (1 + ))))))
(II (1 (1)))) =(1-3)3²
(46)
(1 33)² T/E
23

---

Published as a conference paper at ICLR 2020
where (a) is by that fact that Ek=1 8% 1
3
for any 0 S 3 < 1, (6) is by us-
9)-
ing (44. and (c) is by using that 2 Tt.e
Now let us switch to bound
( 112 Eim 3an (Vs + v) on 42
We have that
+ G1)ll2 Σ
8 30-kP
+V)
(0)
G;)l12 2 +v)
1- 3
m (1 + n0,1))
1
P
(II (1 + A))
1-1
p
U/
+
1-8 3
n
1 B
(1 + nyc s=1
(4) (w) (1 + n))
1
(1 + +)00)))
PV
V/ +
1 B
ne)*
1 3
2M
(m/=)) (1 + +n0011)
(m
0² (1 + +11 p(8
(1- + +4n2 (1-
(T)) cm + 222)22))
P
1- B
(1 1)
1- B
2016
(1) (1)=](1 (1 + ,)00)))
Sil(Fihred + +2r2ch + (gra(()) mm)
P
1-3 3
(116)
(1-
(m)= (1 + ,)))
p(8 ,²0²
(I-p)²
+
4nj²
An72(1=m)
[T
3
2.2
Cm + 22)
1-3 3
2nee
(47)
where (a) is by the fact that Σi=1 go-k k S 1/(1 - 3). (b) is by 44 (c) is by using that
( S (d) is by 00
2² S (T- for any |²| S and substituting = It7e lt
which leads Σ k (1=2)² (1-1/()+())= (0r)2 S (me)²
1/(1+ne)
2 in which the last inequality is
by chosen the step size 77 so that 17E S 1.
By combining
42 446 and 47 we have that
Egg E
42
(1
(m)=+++;))11++ Σ
g Ln(s k)cm
m -1
122
Σ
ge (Vs +v)
2
k=
1=
BLcm
(II [1)=1(1 n),
c(1 332
(1 + ,)0,))
P 8(Fehred + 2r
+ gr
1- B
1762
(1-
1 (1 + n)0;a)
200 p
(1-1}² + 4n2
2
+ 2r 2
-= 1 3
1-33
21
(48)
which completes the proof.
24

---

Published as a conference paper at ICLR 2020
Upper bounding l1qu,-11l::
Lemma 10. Following the conditions Lemma and Lemma we have
119, & (1 + n1, rem.
(49)
Proof.
|1,,t-1l1 & G S (TT))))G;) =|
1221l - -rm S (I) + ny (8)
(50)
where the last inequality is because is chosen so that 1 12
and the fact that Xmax (H) S L. T-B
n..
Lower bounding Er, 11
Lemma 11. Following the conditions in Lemma and Lemma
have
EA (21
2 (1 +0;))) rcm x
BLCm p 8F + 2T + Gr c
p(8 2
41/²
222
+ 2r 22
(1-B)2 B)²
1-3
<(1 - (}) ne²
(1 - 3)3
2me(11 - 33)
(51)
Proof.
By the results of Lemma and Lemma
T0
1g.t-1) 1) 2 Et,, |2 111 E1, [2 1..00
Lemma 10
E.g 22 (1)=1(11 (1 + n0,,)) rmmll.mll..
Lemmo
21 (1 + ,)0)))) 2
(52)
rem x
BLem
+ P 8(Fureed 2r cn + cm)
p(8 1302
11-30 3y
+
[- (112(1_3)
4n7
8
2/ + 2r
2
m
c(1 - 93) n??
(1 -)3
2tyc - ()
25

---

Published as a conference paper at ICLR 2020
Lower bounding Eto 217(90,0-119 92,--))))
Lemma 12. Following the conditions Lemma 7 and Lemma we have
Eto (2n/2, 19,00-11) 0.
(53)
Proof.
Etg (2 = Reo (2 (=s++ Gj) Σ
gr
ga-ke Stotk)l
k=1
(a)
Big (27
axbta+x))
Beg 12n
En -ko+k-an 1190,1101111111 (x
(54)
(c) Eeg [2n
Σ
(qu,t-1, B Beo+k (002tt11/0
R=1
E,, (2m
au (gr, Biy 15to
k=1
where (a) holds for some coefficients ag, (b) is by the tower rule, (c) is because qu,t-1 is measureable with to and (d) is by the zero mean assumption of E's.
Lower bounding EE, (2n/gu.--1 1m)
Lemma 13. Following the conditions in Lemma and Lemma 2 we have
Fro 21) (m,t-1)] 2
(55)
Proof.
Er (2 9m,t-1)1
2 ((TT mi:
( G.)l"maa
(56)
s=1
(a) 21rrEE [men Bm 11
(b)
2
0,
where (a) is by defining the matrix B (II = G; T EE= x= (If=s+1G)) ())88)) For (b), notice that
the matrix is symmetric positive semidefinite. To see that the matrix B is symmetric positive semidefinite, observe that each Gj := (I Σ - H) can be written in the form of G, = UDJUT for some orthonormal matrix and a diagonal matrix Dj. Therefore, the matrix product G)) (m;=)-,,))
D;) ( DT is symmetric positive semidefinite as long as each G, is. So, (b) is by the property of matrix being symmetric positive semidefinite.
26

---

Published as a conference paper at ICLR 2020
Lower bounding Eto
Lemma 14. Following the conditions in Lemmal 7 and Lemma 2 if SGD with momentum has the APCG property, then
21rd
2n 10
(TT +n
(57)
(1 3)
Proof. Define D2 := 13
2r [90 (0000-1,000 1, 1)] Br, 2 (rmmo)
n1 1-1
j=s++ G3)
Σ
g
(ww))))
k=1
-21/Eno (rmta
G, G3) Σ g ko-ko((u)))))
t-1
= 2np
g5-kE, Ero kmtg Dg f(w,,))
(0)
1-1
2
2n7 rd
k [..lll/
rd
[
(58)
8
where (a) is by the APCG property. We also have that
D. =
| G,
G, 11
(1 (8)
(1)=) (1 778,))² 2
(59)
(1 + 7
+ k
where (a) and (b) is by Substituting the result back to 58 we get
rd
21yEE 1qv. 9u. 1 3
| ((
27 TC
+ n))
rr -1 B)
[((())))
(11=)
I|
(1 + n))*
(60)
Using the fact that [VV/(w:))) I| S completes the proof.
E.3 PROOF OF LEMMA
Recall that the strategy is proving by contradiction. Assume that the function value does not decrease at least Fehred in Tehred iterations on expectation. Then, we can get an upper bound of the expected distance E,, [l] [tg
Wt, 2] < Cupper but, by leveraging the negative curvature, we can also show lower bound of the form Ir,, [|
Wtg [|a] Clower- The strategy is showing that the lower bound is larger than the upper bound, which leads to the contradiction and concludes that the function value must decrease at least F Fshred Tehred iterations on expectation. To get the contradiction, according to Lemma 1 and Lemma 3 we need to show that
Eeg qv, -1 [2] + 2n [gq, Fihread11 - + Qg Tshred-1 + qu, Tehradh 9 (eTeerea--)) C Cupper.
(61)
Yet, by Lemma and Lemma 12 we have that Ey (errer 1, Aebred- {
and
ET,,, (ge,Terrea 11 2, Tanreas 1 = O. So, suffices to prove that
Tehrea ill [| + 21y ((q, J 49. Tehreat- + Ow, Tnreaaa > Cuppers (62) Lo.
and it suffices to show that
27

---

Published as a conference paper at ICLR 2020
Ero Ill Faswedd 1 [1 + Bno 19 Tenned -1, 9q Fehred- -1) 0.
Bro I1 |1 + Rto Tehred Tor Tehred 1)] 2
Beo Ill
11 z Cupper.
E.3.1 PROVING THAT E gg. Tehree 11 27 [euo Fta 0:
By Lemma and Lemma I1 we have that
1
Eeo lo: [| + Eto (27/qu Tareea 99 [gTTered--1)
4
[1 Tehred -1 (1+ 22 211(1T Tuhoeed 1=1
(1 + ,)0 2 rcm
BLem
P
8(Fehred + 222 + gr mm
p(8 p(8 r²0²
(-
+ 4n2 ( 2 cm + +2 c
--3
npe
(1 - /333
21je - (3)
(63)
To show that the above is nonnegative, it suffices to show that
24nr L
, 2 c(1- -3
(64)
and
2mp 8(Fthred + 22r²ch + (rr())
n2y 2 (1 B)
(65)
(1-3y²
and
r2 2 3
24nrem
:302 p(8
(1-8)2
+ 4n7
8 (11))
2d2 cm
+
27 22 m
(66)
2tJ
Now w.L.ogg, assume that Cm. L, 0², c', and p not less than and that 1. By using the
values of parameters on Table 3 we have the following results; a sufficient condition of (64) is that
24T.c e2
Gr 2
m
(67)
Cn (1 - 3)2
sufficient condition of 65 is that
Cr 2 (1 5)3
576cmp
(68)
and
1152CmPCRCs
>
(69)
B)3
and
192ct. 222
1 12
(70)
(1 -B33
sufficient condition (66) is that
96cm 0 + 3c )ot (1 (1- B)3
(71)
and a sufficient condition for the above
71 by the assumption that both o² 2 and Cm 2 1, is
(72)
B)3
Now let us verify if 67).
(68
69
70
are satisfied. For (67). using the constraint of Using this inequality, suffices to let & 2
Oy on Table we have that
S.p 2y for getting
2
67
which holds by using the constraint that d' B)2 > 1 and < 1.
28

---

Published as a conference paper at ICLR 2020
For 6680, using the constraint of or on Table 3 we have that 1 2 LLL'Lo' Using this inequality, 3)3 > 1. For it suffices to let 2 (1 which holds by using the constraint that o²
169, it needs (1-8)a pch
2 c pLo
co
2 Cr. which hold by using the constraint that ² 11 3) > 1.
(1-8)²
2 empLoter Cr which holds by using the constraint that (1-9)² 0²(1 8)$ > 1. For 72). it suffices to let 576r partc 2 -m pLoteh 2 Gr, which holds by using the constraint that L(1 - 3) > and S 1. Therefore, by choosing the parameter values as Table 3 we can guarantee that }B,, 1. Tohreed [1 2n/Eeo Turress 1 Tehred 1)] 2 O.
For (70), it suffices to let
E.3.2 PROVING THAT E Tenrea 112]] + 2n [erred 1 qui Tehree- 2 0:
By Lemma 4 and Lemma
14 we have that
Etp [| qe 2ny Ke Tehres Iw, Terraaraa-1))
(73)
1 T (1+ n0, 2))
2nrd'
Tchred (1 + 17,, 2))
(1- B)
To show that the above is nonnegative, it suffices to show that
r2 8yre'e
(74)
3)
A sufficient condition is 2 8e'd' Eq 1-3 Using the constraint of 6, on Table 3 we have that 1
>
Cip
ci pt3oodonn So, it suffices to let Cr 2 3c 3cc_pL3 which holds by using the constraint that
cgc'
L(1 3)3 > (so that L(1 -1 3) 1) and 1.
E.3.3 PROVING THAT I (lll,, Tenred [| 2 Cupper:
From Lemma and Lemmal I we need show that
Iired (1 + ()
8nt (Fehred + -2 c/ + grr mm
+ 8 (1 332
1202
+ 4v²²
c. + {=))²
3
2.2
2r
(75)
-32
1-
1
cm
We know that (117 Tirved (1 + ())
22 2 1
(11
Tinred -1 (1+10) n0,=)) ((0)))))222 22y. It suffices to show j=1
that
T (1 (1+))))))2 222
8mt (Fehred + 22-2ch + gr cm)
1202
+ 8
3)2 + 4v7
)2 2n + 2r
(76)
(1 131
(1-
Note that the left hand side is exponentially growing in Tehred- We can choose the number of iterations Tehred large enough to get the desired result. Specifically, we claim that Tehred 2
c(l-1) log( Lcm o pd Ck) for some constant c 0. To see this, let us first apply log on both sides of ne
[1- 11-B)87e
76).
Tikeedd 1
2(
log(1 + (()e)) + log(r37) 2 log( (Sa Tehred + 8b)
(77)
where we denote a Peh +rr and == 4 + 2ny (1-1) 2 + r To
[1-8]²
proceed, we are going to use the inequality log(1 + x) 2 1 for x E 10, 2.51]. We have that
n
1 1> (1 - 3)
(78)
29

---

Published as a conference paper at ICLR 2020
guaranteed by the constraint of 17. So,
Tahered
(a) Tehrea-1
Tehred 11 1--1
2(
log(1 + +n0ee))
n0Je= =
nE me
1=1
1=1
==1 k=0
Tchred
1
T/E
(Tihred
1 - m7,.
B
1
==1
(b) Tthred
2(1- 11-33 3) 17c,
(79)
where (a) is by using the inequality log(1 + x) 2 2 with = n8,e S
and (b) is by making
Tawram11
2(1-3) [1-8yr which is equivalent the condition that
233 1 3
Ithred 1
(80)
Now let us substitute the result of 799 back to (7). We have that
Tihred 2 + 2(1
Sa Tthred + 8b
log(
(81)
T]E
7r²
which is what we need to show. By choosing Tehred large enough,
Tihred c(1 () Icmo²² pc! pclch Ch
1
log(
((11 3) log(
(1 3) )c
(82)
(1 3)
for some constant c 0, we can guarantee that the above inequality (81) holds.
F PROOF OF LEMMA 15
Lemma
15
DDanesmaadd et al. 2018 Let us define the event T₃ == { f(W )|
E or Amin ( and Amin 2 (WWKTToea)
F(WkTereas) ))
cJ. The complement is T [ ff f(WxTerred
), which suggests that WkTaaoed is an (c, <--sccondd order sta-
tionary points. Suppose that
Eff (uf(u((+)TTrra)) f(W) | A
A 2
(83)
E [ff((((+1)Trra)) f f( [ S 5
Ser 2Tthred (f(w) min (ww)
We return w uniformly randomly from Wo; Winneed W2Tnneed ... WKTnarad--... WK Tangga where K == [T/Terrea Then, with probability at least - 5, we will have chosen a Wy where Yx did not occur.
Proof. Let P& be the probability that Yg occurs.
[[s(W((++TTrrr))) [(WKTTrrea))
[[[(W((+)))Trra)) [ (WTTTTrrccc (W -WW |
| Ps)
S -APP 81/2(1 PP)
80/2 (1 8/2)APk
s 60/2 APp.
(84)
Summing over all K, we have
K
1
Ef (W((w()+))))ccc f < A
(8/2 Ps)
K
K
k=
f(wo) min f(w) (K + 1)4
Ps S 58/2+
56
(85)
+1
k=
K
(1 - P&) 2 2-88
K +
0=
30

---

Published as a conference paper at ICLR 2020
G PROOF OF THEOREM
Theorem Assume that the stochastic momentum satisfies CNC. Set O and
Tikred log( Lem pc'cn)
O((1 B) log( o' 9) for some constant e > If (1-B)ome
[1- B]8ge
SGD with momentum (Algorithm
2 has APAG property when gradient is large (I) 2 e).
T property when enters a region of saddle points that exhibits a negative curvature (IV[(()) S and Amin( (V²S(w)) -e), and GrACE property throughout the iterations, then it reaches an (c,c) E) second order stationary point in T = 2Tthred [f min, f( = O((1 - log( Lema' od (1-B)ôye )e 10) iterations with high probability 1 5, where Fihred O(e*).
G.1 PROOF SKETCH THEOREM I
In this subsection, we provide sketch of the proof of Theorem The complete proof is available in Appendix G Our proof uses a lemma in (Daneshmand et al. (2018)) which is Lemma 15 below. The lemma guarantees that uniformly sampling w from (WAsTared J. k 0, 2..,..., [T77 threal gives an (e, é -second order stationary point with high probability. We replicate the proof of Lemma 15 in Appendix
Lemma 15. Daneshmand et al. (2018)) Let us define the event Yx == [ f (Wie 1l
or Aminn
2 (WKTerea))
-]. The complement is Ys == V f (Wwrereed)
c and Auin 2
2 - c}, which suggests that WKTsared is an (c, c)-scoond order sta-
tionary points. Suppose that
El [[f((((+))Tnna) [INl) & ([f(W(++)))) - [ <
(86)
Set T = 2Tehred - min ((w)))/(A)
We return w uniformly randomly from Wo, WTanred' W2Tnrrea ..., WKTsavea W Tanraa where K == [T/Tereed] Then, with probability least 1- 8, we will have chosen Wy where Yk did occur.
8
we need to let the conditions (86) be satisfied. We can bound [WWaTinsed [Ya] < -Fthred- based on the analysis of the large gradient norm regime (Lemma 7) and the analysis for the scenario when the update is with small gradient norm but large negative curvature is available (Subsection 3.2.1). For the other condition, Bf ([f( (WiTTarra)) [r]] I 8 Exgred, it requires that the expected amortized increase of function value due to taking the large step size is limited (i.e. bounded by " when WkTnreed a second order stationary point. By having the conditions satisfied, can apply Lemma 15 and finish the proof of the theorem.
To use the result of Lemma 15
G.2 FULL PROOF OF THEOREM T
Proof. Our proof is based Lemma
15
So, let consider the events in Lemma 15 2 ((f(UTaana)) S -t}. We first show that
TE = ( Il 2 6 or Amiin
E (1f(11(41))Tnrr - ((WkTaarad) { | S Fthred-
When (WITTaal
"One use any upper bound of f(wo) min f(w f(wo) min fww in the expression of T.
31

---

Published as a conference paper at ICLR 2020
Consider that Y& is the case that V|V f (WorTar Il 2 Denote to == kTihred in the following. We have that
Tehred
Bao + - [((tt))]
( Etg [B[[(Wotte+)) - [W
1=0
Titeved
= = (( - [(wco)) +
Σ
Bio [B[[ I (woo+e)
(a)
L
Tshred-
(V(
Eig [[f((wo+r+1) - ff (w) wozto
2
(6)
- 2
/V( 111
2
Tehred-1 -1
(1ecn +
P イイ
(87)
2
6
(
2
3
mm
+
2
Ch
L cm
2
2
6
(4)
[V/(w,))) )112
+ 1²ch
2
3 =2 Lr +r
(
(g)
4 -
_
-Fiheed
2
where (a) is by using Lemma 6 with step size r. (b) is by using Lemma 8 (c) is due to the constraint
that 17 Tehred I r2 (d) is by the choice r, (e) is by [ c, (f) is by the choice of r so that r 5 The Tca and (g) is by
r 2 2 Fehred
(88)
4
When (WWTaraa) S and Amin ( 2 (W S -e:
The scenario that Y, is the case that | (uWTTrr)) S E and Amin ( [WWTTarre )) < -e has been analyzed in Appendix which guarantees that fW f(woo)] S -Fthred under the setting.
When || V (WWTTeee) S e and Amin (2f(wwenee)))) -E:
Now let us switch to show that [[ (1) f(WWTTaraa) [ < Fuggud Recall that Tg means that (V I and Amiul (V2 (V2 ((WKTanra))) 2 -c. Denote to = &eerred in the following. We have that
Tehred
Big (WWoo Tenred) [wiro)]
Eig (B[s [woott)
1=0
Tihredd
= - [(Wta))
Erg ([
(a)
S r2cn
p +
3
3
cm
+
Tehred
Eig E - [Wortt]]Wo
worro+e]]
6
(8)
p Pen
+
3
mm
+
Tehred
Σ
(npcn + 6
f
6
1=1
(6) - 2r
P
3
3
<
4r
ch
(d) öFihred
S
(89)
2
where (a) is by using Lemma with step size r. (b) is by using Lemma g with step step size 17. (c) is by setting 172h Tebred 22 and n) r, (d) is by the choice of r so that = Ct. & 5.F
32

---

Published as a conference paper at ICLR 2020
Now ready to Lemma 15 since both the conditions satisfied. According to
the lemma and the choices of parameters value on Table 3 we can set 2Tubred (f (ww)
mink / O((1 3) log( (1-8)8ye
pd ) which will return w that an (e,
second order stationary point. Thus, we have completed the proof.
G.3 COMPARISON TO DANESHMAND AL. (2018)
Theorem 2 in Daneshmand et al. 2018) states that, for CNC-SGD to find an (2/22/ stationary point, the total number of iterations is T O g log" coq. ) where l is the bound of the stochastic 8"
gradient norm ||9e|| S which can viewed as the counterpart cm in our paper. By translating their result for finding (c, stationary point, it is T O (0000, 1.pp² 1 (efh 10-)) On the other hand, 00
using the parameters value on Table 3 we have that = 2Tthred -iin) f(w)) (85Ttred) =
0( (1=a)c 1. (1)"
log( Lema (1-B)6ye )E 10) for Algorithm
Before making comparison, we note that their result does not have dependency on the variance of stochastic gradient (i.e. a²), which because they assume that the variance is also bounded by the constant e (can be seen from (86) in the supplementary of their paper where the variance terms
|| are bounded by E). Following their treatment, we assume that o² S Cm. then on 71 we can
instead replace (a² 3e with 4c and on (72 it becomes 1 2 (I (1-3)3
576c. pc., This will remove all
the parameters' dependency on o². Now by comparing Ö((1 B)c of p²
LL 54. 6t. of ours and that in the high momentum regime
T (p2p210
C ( of Daneshmand al. (2018),
where (1 3) << 02p10
eh, ch Algorithm 2 is strictly better than that of Daneshmand et al. (201)), which
means that higher momentum can help to find second order stationary point faster.
33


Reviews:
[{"review_id": "ryxDWRRaFr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThe 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. \n\nComments:\nSGD 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.  \nI 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. \n\n1) I understand the motivation of the authors and what they tried to communicate but i find that there \nis 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? \n\n2) 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. \n\n3) 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.\n\n4) I am suggesting the authors to include in the introduction the more known variant of SGD with momentum:\n$$\\omega_{t+1}=\\omega_t-\\eta \\nabla f(\\omega_t, \\xi_t)+\\beta(\\omega_t-\\omega_{t-1})$$\n5) 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)\n\nMinor Comment:\npage 3, bellow eq(4): the first (3) ----> Problem (3)\n\nMissing references:\nThe authors did an excellent work on reviewing the literature review on SGD with momentum. Bellow find three recent related works that could be mentioned:\n\nAybat, Necdet Serhat, Alireza Fallah, Mert Gurbuzbalaban, and Asuman Ozdaglar. \"A universally optimal multistage accelerated stochastic gradient method.\" arXiv preprint arXiv:1901.08022 (2019).\nLoizou, Nicolas, and Peter Richtárik. \"Linearly convergent stochastic heavy ball method for minimizing generalization error.\" arXiv preprint arXiv:1710.10737 (2017).\nLoizou, 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.\n\n========= after rebuttal =============\n 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\".\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "rJef0QxAKH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "*Summary*\nThis paper studies the impact of momentum for escaping Saddle points with SGD (+momentum) in a non-convex optimization setting. \nThey 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.\nThe 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.\n \n*Decision*: \nI 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. \nHowever, 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).\nThus 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.   \n \n*Questions*:\n- 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.\n- To what extend your assumptions are comparable to the ones made in the close related work (papers presented in Table 1) ?\n \n \n \n*Minor remarks*:\n- You should cite something for the NP-hardness of finding local minima. \n- The definition for $(\\epsilon,\\epsilon)$-second order stationary point would be a bit cleared with two different epsilon $\\epsilon_1,\\epsilon_2$.\n- I think should should put the constraints you have on $\\beta$ in the main paper.\n-  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 ?  \n- Usually footnotes are after the punctuation sign (because you want to comment the whole sentence and not its last word).\n- Footnote 4 is in the wrong page.\n\n==== After rebuttal ==== \nI have read the answers of the authors and I still think that their results are too hard to interpret.\nI 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}$). \nThe interest of the momentum method should be that when using $\\beta = 1 - L^{-1/3}$ the escaping time (for instance) is better. \nThe author did not convince that is was the case. \n\nHowever I would tend to change my grade to 4 or 5 /10 if it was possible. (i.e. very borderline weak reject) \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HyeaI6L0KB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nAlthough 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.\n\nThe 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.\n\nOne 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?\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

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)