Quickly Finding a Benign Region via Heavy Ball Momentum in Non-Convex Optimization
Authors: Jun-Kun Wang
Jacob Abernethy
Venue:  (2021)

Abstract: The Heavy Ball Method, proposed by Polyak over five decades ago, is a first-order method for optimizing continuous functions. While its stochastic counterpart has proven extremely popular in training deep networks, there are almost no known functions where deterministic Heavy Ball is provably faster than the simple and classical gradient descent algorithm in non-convex optimization. The success of Heavy Ball has thus far eluded theoretical understanding.  Our goal is to address this gap, and in the present work we identify two non-convex problems where we provably show that the Heavy Ball momentum helps the iterate to enter a benign region that contains a global optimal point faster. We show that Heavy Ball exhibits simple dynamics that clearly reveal the benefit of using a larger value of momentum parameter for the problems. The first of these optimization problems is the phase retrieval problem, which has useful applications in physical science. The second of these optimization problems is the cubic-regularized minimization, a critical subroutine required by Nesterov-Polyak cubic-regularized method to find second-order stationary points in general smooth non-convex problems.

Under review as a conference paper at ICLR 2021
QUICKLY FINDING A BENIGN REGION VIA HEAVY BALL MOMENTUM IN NON-CONVEX OPTIMIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
The Heavy Ball Method PPllykk 1964). proposed by Polyak over five decades ago, is first-order method for optimizing continuous functions. While its stochas- tic counterpart has proven extremely popular in training deep networks, there are almost no known functions where deterministic Heavy Ball provably faster than the simple and classical gradient descent algorithm in non-convex optimization. The success of Heavy Ball has thus far cluded theoretical understanding. Our goal is to address this gap, and in the present work we identify two non-convex problems where we provably show that the Heavy Ball momentum helps the it- erate to enter benign region that contains global optimal point faster. We show that Heavy Ball exhibits simple dynamics that clearly reveal the benefit of using larger value of momentum parameter for the problems. The first of these optimization problems is the phase retrieval problem, which has useful ap- plications in physical science. The second of these optimization problems is the cubic-regularized minimization, a critical subroutine required by Eesterov-Polyal cubic-regularized method (Nesterov Polyak (2006)) to find second-order sta- tionary points in general smooth non-convex problems.
INTRODUCTION
Poylak's 's Heavy Ball method ( (1964) has been very popular in modern non-convex optimiza- tion and deep learning, and the stochastic version (a.k.a. SGD with momentum) has become the de facto algorithm for training neural nets. Many empirical results show that the algorithm is better than the standard SGD in deep learning (see e.g. Hoffer et al. (2017): Loshchilov & Hutter (2019); Wilson et | (2017); Sutskever et al. (201)), but there are almost no corresponding mathematical results that show a benefit relative to the more standard (stochastic) gradient descent. Despite its pop- ularity, we still have very poor justification theoretically for its success in non-convex optimization tasks, and Kidambi et al. (2018) were able establish a negative result, showing that Heavy Ball momentum cannot outperform other methods in certain problems. Furthermore, even for convex problems it appears that strongly convex, smooth, and twice differentiable functions (e.g. strongly convex quadratic functions) are one of just handful examples for which provable speedup over standard gradient descent can be shown (c.g (Lessard et al., 2016 Goh |
Ghadimi et al. 2015
Gitman et al., 2019: Loizou & Richtárik 2017 2018 Gadat al. 2016 Scieur & Pedregosa 2020
Sun et al. 2019 (Yng et al. [201 Sa] Can et al. 2019 Liu et al.) 2020) Sehbouh et al. 2020 Flam-
marion & Bach, 2015)). There are
some negative results when the function is strongly convex but not twice differentiable. That is, Heavy Ball momentum might lead to a divergence in convex
optimization (see e.g. (Ghadimi et al. 2015; Lessard et al. 2016)). The algorithm's apparent success in modern non-convex optimization has remained quite mysterious.
In this paper, we identify two non-convex optimization problems for which the use of Heavy Ball method has a provable advantage over vanilla gradient descent. The first problem is phase re- trieval. It has some useful applications in physical science such as microscopy or astronomm (see e.g. (Candés et al. 2013), (Fannjiang & Strohmer 2020), and (Shechtman et al. 2015)). The objective is
min f(w) = in Σm (1x) w)² y:)²
where I; E Idd is the design vector and y: = (x. w. ) is the label of sample i. The goal is to recover w, up to the sign that is not recoverable (Candés et al. 2013). Under the Gaussian design

---

Under review as a conference paper at ICLR 2021
setting (i.e. 2; ~ (o) is known that the empirical risk minimizer is w. or w.. long as the number of samples n exceeds the order of the dimension (see e.g. Bandeira et al. (2014). )
Therefore, solving ① allows one recover the desired vector w, IR up to the sign. Unfortunately the problem is non-convex which limits our ability to efficiently find a minimizer. For this problem, there many specialized algorithms that aim at achieving better computational complexity and/or
sample complexity to recover w. modulo the unrecoverable sign (e.g. (Cai et al. [0066] Candés & Li.
2014 Candés et al. 2015 2013; Chen & Candés 2017; Duchi & Ruan 2018 Ma al. 2001 2018
Netrapalli et al. 2013 Qu et al. 2017: Tu et al. 2016 Wang et al. 2017a b Yang et al.) 2018b;
Zhang et al. 201 b Zheng& & Lafferty 2015)). Our goal not about providing a state-of -hhthe-art
Instead, we treat this problem as a starting point of understanding Heavy Ball momentum in non-convex optimization and hope for getting some insights on why Heavy Ball (Algorithm [ and 2 can be faster than the vanilla gradient descent in non-convex optimization and deep learning in practice. If we want to understand why Heavy Ball momentum leads to accelcration for complicated non-convex problem, we should first understand it in the simplest possible setting.
algorithm for solving
We provably show that Heavy Ball recovers the desired vector w., up to a sign flip, given a random isotropic initialization. Our analysis divides the execution of the algorithm into two stages. In the first stage, the ratio of the projection of the current iterate Wi on w, to the projection of we on the perpendicular component keeps growing, which makes the iterate eventually enter a benign region which is strongly convex, smooth, twice differentiable, and contains a global optimal point. Therefore, in the second stage, Heavy Ball has a linear convergence rate. Furthermore, up value, a larger value of the momentum parameter has a faster linear convergence than the vanilla gradient descent in the second stage. Yet, most importantly, we show that Heavy Ball momentum also has an important role in reducing the number of iterations in the first stage, which is when the iterate might be in non-convex region. We show that the higher the momentum parameter J3, the fewer the iterations spent in the first stage (see also Figure D. Namely, momentum helps the iterate to enter benign region faster. Consequently, using non-zero momentum parameter leads to a speedup over the standard gradient descent (33 0). Therefore, our result shows a provable acceleration relative to the vanilla gradient descent, for computing a global optimal solution in non-convex optimization.
The second of these is solving a class of cubic-regularized problems,
min f(w) := 1 ww
TTTTAu Aw 5T w + gl
where the matrix A E TRaxd is symmetric and possibly indefinite. Problem (2) is sub-routine of the Nesterov-Polyak cubic-regularized method (Nesterov& & Polyak (2066)), which aims to minimize a non-convex objective (-) by iteratively solving
W141 = arg min (w:) T (w - we) + (w - w.) V2 (2F(()(w - wo) + I - well"),
(3)
With some additional post- post-procsssing, the iterate wA converges to an (cg. (n) second order station- ary point, defined as {w [[V((w)] S eg and (Ww) > -ea Ja} for any small Eg. En. > O. However, their algorithm needs compute matrix inverse solve (2). which is computationally expensive when the dimension is high. A very recent result due to Carmon & Duchi (2019) shows that vanilla gradient descent approximately finds the global minimum of (2) under mild conditions, which only needs a Hessian-vector product and can be computed in the same computational com- plexity as computing gradients (Pearlmutter) 1994), and hence is computationally cheaper than the matrix inversion of the Hessian. Our result shows that, similar to the case of phase retrieval, the use of Heavy Ball momentum helps the iterate enter benign region of (3) that contains a global optimal solution faster, compared to vanilla gradient descent. For certain non-convex problems, e.g. dictionary learning (Sun et al. 2015), matrix completion (Chi et al. 2019). robust PCA (Ge et al., 2017). and learning neural network (Ge et al. (2019; Bai & Lee (2020)) where it suffices to find a second-order stationary point, our result consequently might have application.
To summarize, our theoretical results of the two non-convex problems provably show the benefit of using Heavy Ball momentum. Compared to the vanilla gradient descent, the use of momentum helps to accelerate the optimization process. The key to showing the acceleration in getting into benign regions of these problems is a family of simple dynamics due to Heavy Ball momentum. We will argue that the simple dynamics are not restricted to the two main problems considered in this paper. Specifically, the dynamics also naturally arise when solving the problem of top eigenvector computation (Golub & Loan 1996) and the problem of saddle points escape (e.g. (Tin et al. 2017
2

---

Under review as a conference paper at ICLR 2021
Wang et al. ). which might imply the broad applicability of the dynamies for analyzing Heavy Ball in non-convex optimization.
Algorithm 1: Heavy Ball method
Algorithm 2: Heavy Ball method
PPllykk 1964) (Equivalent version 1)
PPolykk 1964) (Equivalent version 2)
Required: step size yi and momentum
Required: step size 1j and momentum parameter
parameter 3 E [o, 1].
3 E [0. 1].
2: Init: Wg W--1 E R
2: Init: wo E R and m--1 = 0.
3: for = to do
3: for f to T do
4: Update iterate
4: Update momentum Mī == 31m-1 + vs(w)).
Wr++1 we 7/ (wws) + B(w, w1-1).
5: Update iterate W1+1 == Wy T//l..
5: end for
6: end for
2 MORE RELATED WORKS
Heavy Ball (HB): HB has two exactly equivalent presentations in the literature (see Algorithm and 2 Given the same initialization, both algorithms generate the same sequence of {w,}. In Algorithm we note that the momentum m, be written as m, E'= 36 (w,, and can be viewed as a weighted sum of gradients. As we described in the opening paragraph, there is little theory of showing provable acceleration of the method in non-convex optimization. The only exception that we are aware of is (Wang el al. (020). They show that HB momentum can help to escape saddle points faster and find a second order stationary point faster for smooth non-convex optimization. They also observed that stochastic HB solves ① and that using higher values of the momentum parameter 33 leads to faster convergence. However, while their work focused on the stochastic setting, their main result required some assumptions on the statistical properties of the sequence of observed gradients; is not clear whether these would hold in general. In appendix [A] provide more detailed literature review of HB. To summarize, current results in the literature imply that we are still very far from understanding deterministic HB in non-convex optimization, let alone understanding the success of stochastic HB in deep learning. Hence, this work aims to make progress on a simple question: can we give precise advantage argument for the acceleration effect of Heavy Ball in the deterministic setting?
Phase retrieval: The optimization landscape of problem and its variants has been studied by (Davis et al.) 2018 Soltanolkotabi] 2014; [Sun al. 2016 White al. (016),, which shows that as long as the number of samples is sufficiently large. it has no spurious local optima. We note that the
problem can also be viewed as a special case of matrix sensing (e.g. Li et al. (2018): Gunasekar al.
2017); Li & Lin (2020); ; Li et al. b: Gidel et al. (2019): You et al. (2020): in Appendix A we provide brief summary of matrix sensing. For solving phase retrieval, Mannellia et al. (2020) study gradient flow, while Chen et al. (2018) show that the standard gradient descent with a random initialization like Gaussian initialization solves (1) and recovers w, up to the sign. Tan Vershynin (2019) show that online gradient descent with simple random initialization can converge to global optimal point in an online setting where fresh samples are required for each step. In this paper, we show that Heavy Ball converges even faster than the vanilla gradient descent. Zhou et al. (2016) propose leveraging Nesterov's 's momentum to solve phase retrieval. However, their approach requires delicate and computationally expensive initialization like spectral initialization that the initial point is already within the neighborhood of a minimizer. Similarly, Xiong et al. (2018) 2020) show local convergence of Nesterov's momentem and Heavy Ball momentum for phase retrieval. but require the initial point to be in the neighborhood of an optimal point. Jin et al. (2018) propose subroutine with perturbation for finding
an algorithm that uses Nesterov's momentum together a second- -onder stationary point, which could be applied for solving phase retrieval. Compared to (Zhou et al. 2016, Jin et al. 2018 Xiong et al. 2018 2020), we consider directly applying gradient descent with Heavy Ball momentum (i.e. HB method) to the objective function with simple random initialization, e.g. Gaussian initialization, which is what people do in practice and what we want to understand. The goals of the works are different. Finally, we note that there are some efforts in integrating the technique generative models and phase retrieval, which could help the task of image recovery (e.g. Hand al.] (2018)). Phase retrieval might also be good entry point of understanding some observations in optimization and neural net training (c.g. Mannellia et al.
2020
3

---

Under review as a conference paper at ICLR 2021
66-
61
10
13
200
Obj. value
(b) |m0] vs.
(c) 1 ||
vs. t
Figure 1: Performance of HB with different 3 = {0, 0.3,
+ 0.9} for phase retrieval. (En- larged figures are available in Appendix H) Here "1.0 + 0.9" stands for using parameter & = 1.0 in the first few iterations and then switching using 3 0.9 after that. In experiment, for the ease of implementa-
tion, we let the criteria of the switch be [ ((w))_]f (-w)) 2 0.5). i.c. if the relative change of objective value (wm)
compared to the initial value has been increased to 50%. Algorithm and Algorithm 4 Appendix H describe the procedures. All the lines are obtained by initializing the iterate at the same point Wy (0, Ia/ (10000d) and using the same step size 7) x 10 Here we set w. 61 and sample 2; (O, Ia) with dimension
10 number samples = 200. see that the higher the momentum parameter B3, the faster the algorithm enters the linear convergence regime. (a): Objective value (T) vs. iteration f. We see that the higher the momentum parameter 3, the faster the algorithm enters the linear convergence regime. (b): The size of
projection of We on w. over iterations (i.c. (oo. vs. t), which is non-decraasing throughout the iterations until reaching optimal point (here,
|| [.-| || = 1). (c): The size of the perpendicular component over iterations (i.c. |ww || vs. 1). which is increasing in the beginning and then it is decreasing towards zero after some point. We see that the slope of the curve corresponding to larger momentum parameter 3 is steeper than that of smaller one, which confirms Lemma and Lemma
PHASE RETRIEVAL
3.1 PRELIMINARIES
Following the works of Candés et al. (2013); ; Chen et al. (2018). we assume that the design vectors {æ;} (which are known priori) are from Gaussian distribution Ø; ((0 Ia). Furthermore, without loss of generality, we assume that w, = e (so that ||w.|| || = 1), where ei is the standard unit vector whose first element is 1. We also denote w!! w. [1[1] and w/ I == wr]"]] ( That is, w. the projection of the current iterate w, on w. while wi is the perpendicular component. Throughout the paper, the subscript is an index of the iterations while the subscript i is index of the samples.
Before describing the main results, would like provide preliminary analysis to show how momentum helps. Applying gradient descent with Heavy Ball momentum (Algorithm
D to ob- that the iterate is generated according wx+1 w/ 7 Σi= ((r, w,
jective (1.
(x:J we we) ) x7 + B(w, - w)-1). On the other hand, the population counterpart (i.e. when the number of samples n is infinite) of the update rule turns out to be the key to understanding momentum. The population gradient F(w)= = N (V [(w) (proof available in appendix B
V F(ww) 33
|||uz w| 1)w 2(w] w)w..
(4)
Using the population gradient W.-1), which can be decomposed as follows:
we have the population update, wi+1 = Wi - -W +(W, -
w1+1 (1 + 3 l|w, 112)) wi! + 3(w!! - w(L1)
(5)
W1+1 (1 17(1
3 w/ (2)) w. + B(w, w.-1)-
Assume that the random initialization satisfies || w <<, /.2 From the population recursive system
5). both the magnitude of the signal component w!! and the perpendicular component w.! grow exponentially in the first few iterations.
4

---

Under review as a conference paper at ICLR 2021
For positive number 0 and the momentum parameter E [0, 1]. if non-negative sequence { satisfies au 2 a-1 > and that for all t I T,
Lemma 1.
0++1 2 (1 + 0)az 3(az a2-1);
(6)
then {as} satisfies
a++1 2 (1+ (1+
B )0) de.
(7)
T+B
for every t = 1,..., +. Similarly, if non-positive sequence {ar) satisfies ao S a-1 < 0 and that for all S T, a++1 $ (1+ +0at + B(a; - a1-1), 1), then {ar} satisfies
a++1 Σ 1 + (1+ 1+0 10) oz.
(8)
for every = 1,...,, ".....TT... T
One can view a, in Lemma as the projection of the current iterate w, onto vector of interest. The lemma says that with a larger value of the momentum parameter 3, the magnitude of a, is increasing faster. It also implies that if the projection due vanilla gradient descent satisfies a++1 (1 + O)a,, then the magnitude of the projection only grows faster with the use of Heavy Ball momentum. The dynamics in the lemma are the keys to showing that Heavy Ball momentum accelerates the process of entering a benign (convex) region. The factor - in (7p and (8) represents the contribution due the use of momentum, and the contribution is larger with larger value of momentum parameter 3. Now let us apply Lemma to the recursive system (5) and pretend that the magnitude ||w Il
was a constant for a moment. Denote 0: := 37y(1 || and 6 == n71 - 3| 3/ and notice that
0, > 0, > 0 when ||,,]| <
3. We can rewrite the recursive system as
w =
+ 3(w) -wll) w (1 + O.)=, + B(w= w--1)
Since the above system is in the form of (6). the dynamics 7 and (8) in Lemma I suggest that the larger the momentum parameter B, the faster the growth rate of the magnitude of the signal compo- nent w!! and the perpendicular component wi-. Moreover, the magnitude of the signal component w!! grows faster than that of the perpendicular component w Both components will grow until the size of iterate || is sufficiently large (i.e. ||w,, > 5). After that, the magnitude of the perpendicular
component w starts decaying, while ww! keeps growing until it approaches 1. Furthermore, we have that the larger the momentum parameter 8, the faster the decay rate of the (magnitude of the) perpendicular component w In other words, |u:"| converges to 1 and w,- converges to quickly. Lemma[3in in Appendix [ which is counterpart of Lemma I can be used to explain the faster decay of the magnitude due to larger value of the momentum parameter 3.
By using the population recursive system (5) and Lemma & 3 as the tool, we obtain high-level insight on how momentum helps (see also Figure T}. The momentum helps to drive the iterate to enter the neighborhood of w. (or w..) faster.
3.2 MAIN RESULTS
We denote dist(w,, w.) == min (lw; //1:--=ll2: twr+w,,ll2 as the distance between the current iterate w, and ws, modulo the unrecoverable sign. Note that both tw, achieve zero testing errors. Further- more, as long as the number of samples is sufficiently large, i.e. 2 d log d, there exists a constant > so that the Hessian satisfies 2 f(r) ł 0T, for all w E (+-w,, with high probability, where (B((+,,) represents the balls centered at tw. with radius Ç (e.g. (Ma et al. (017)). So in this paper we consider the case that the local strong convexity holds in the neighborhood w....
We will divide the iterations into two stages. The first stage consists of those iterations that satisfy < 1 < Tę, where Te is defined as
T=:= minft: : || 1/ & and ||ll 5
(10)
and Ç > is sufficiently small so that makes WT, be in the neighborhood of w. or ww, which is smooth, twice differentiable, strongly convex, see e.g. (Ma et al. 2017 Soltanolkotabi 2014)
5

---

Under review as a conference paper at ICLR 2021
and || 5. we have that dist(w,, w.) S |ue w. S |ww + | || < Ç. The second stage consists of those iterations that satisfy > Tc. Given that dist(wr,, W+) S Ç and that the local strong convexity holds (B,(=w),, the iterate we would be in benign region at the start of this stage, which allows linear convergence to a global optimal point. That is, we have that dist(we, w.) I (1 -2)" TcÇ for all t 2 Tç. where > v > 0 is some number. Since the behavior of the momentum method in the second stage can be explained by the existing results (e.g. Section 3 of SSaunders (2018) or Xiong et al. (0200), the goal is to understand why momentum helps to drive the iterate into the benign region faster.
Observe that if ||w!|| 1|
To deal with the case that only finite samples are available in practice, we will consider some per- turbations from the population dynamics ( In particular,
consider
wi!l = (1 + (1y(1 |/0, (12) + niÉt) w!! + ((w! w(-1)) W141 [1] = (1 + 7 w/ (1²) + mp::)) w [-] + B(wB [s] w
(11)
where {Er) } and (pt,} for 1 ك < d are the perturbation terms. The perturbation terms are used to model the deviation from the population dynamics. In this paper. we assume that there exists a small number Cn > 0 such that for all iterations S Te and all j E -d- 1], max |Pt.]] S ca where the value C, should decay when the number of samples n is increasing and Gn E 0 when there are sufficiently large number of samples n.
Theorem 1. Suppose that the approximated dynamics [7p holds with maxi (pt, I Cn for all iterations t S Te and all dimensions j E |d - 11, where en I S. Suppose that the local strong convexity holds Bc(+tw.). Assume that the initial point wo satisfies |wl| ž valoga and wwoll < 3. Set the momentum parameter B E [0, Assume that the norm of the momentum ||raell is bounded for all S Té, i.e. [|mel] S. Cm for some constant Cn > O. If the step size n satisfies then Heavy Ball (Algorithm) & 2 takes at most
n S
36 (1+cc) max/fmm.1
log dl
Tc K 1)
+
C
number of iterations to enter the benign region By(w.)= or BB((w.), where on := T4m/2 S 1. Furthermore, for all t 2 Te, the distance is shrinking linearly for some values of and B < 1. That is, we have that dist(we, w.) S (1 111 -), for some number 1 1>>100000 V >y> 0.
The theorem states that the number of iterations required for gradient descent to enter the linear convergence is reduced by a factor of (1 + C,, which clearly demonstrates that momentum helps to drive the iterate into a benign region faster. The constant Gy suggests that the smaller the step size 7, the acceleration due to the use of momentum is more evident. The reduction can be about ~ 1+ B for a small v). After Tç. Heavy Ball has a locally linear convergence to w, or w. Specifically,
w 0, then will have that w for all and that the iterate will converge w.; otherwise, we will have w!! < 0 for all f and that the iterate will converge to - -.,- The proof of Theorem is in Appendix D
Remark 1: The initial point is required to satisfy (Wo, w.) 2 Vallo and |woll <
1 The first
3-
condition can be achieved by generating Wp from a Gaussian distribution or uniformly sampling from a sphere with high probability e.e Chapter of (Blum et al. 2018)). The second condition can then be satisfied by scaling the size appropriately. We note that the condition that the norm of the momentum is bounded is also assumed (Wang et al. 2020).
Our theorem indicates that in the early stage of the optimization process, the momentum parameter 3 can be as large as 1, which is also verified in the experiment (Figure [ However, to guarantee convergence after the iterate is in the neighborhood of global optimal solution, the parameter 3 must satisfy 3 < (Polyak 1964 Lessard et al. 2016).
Remark 2:
The number of the local linear convergence rate due to Heavy Ball momentum actually depends on the smoothness constant L and strongly convexity constant in the neighborhood of a global solution, well the step size 1) and the momentum parameter 3 (see e.g. Section 3 of (Saunders) 2018) the original paper (Polyak 1964)). By setting the step size 1 = 4/(vT.+ vni)²
Remark 3:

---

Under review as a conference paper at ICLR 2021
/ V/ will depend on the squared root of the condition number /k ;= / L/j μ instead of x: ;= L/μ, which means that an optimal local convergence rate is achieved (e.g. (Bubeck] 2014).. In general, up to certain threshold, a larger value 3 leads to a faster rate than that of standard gradient descent.
and the momentum parameter B max - vnLL, |1
CUBIC-REGULARIZZNN PROBLEM
4.1 NOTATIONS
We begin by introducing the notations used in this section. For the symmetric but possibly indefinite matrix A, we denote its eigenvalue in the increasing order, where any ( might be negative. We de- note the rigen-decomposition of A as A := Σ (A)e,u where each Uú E IR is orthonormal.
We also denote := -x() and 7+ = max (,, (), and || == max ((x()) (1(4) (A)]). For any vector E Rdd we denote w)( as the projection on the eigenvector of A, w.( = (w, 0z). De- note w, as a global minimizer of the cubic-regularized problem (2) and denote A. := A |/a. Previous works of Nesterov & Polyak (2006); Carmon & Duchi (2019) show that the minimizer has a characterization; it satisfies pll..] Z y and Vf(w.) = A. W. + = O. Furthermore, the
minimizer w, is unique if pllw=|l |I > %. In this paper, assume that the problem has unique minimizer so that pl [==]| > 7. The gradient of the regularege problem (2) is
V((w) = Aw + b+ p|| = A.(w w.) p(1|u_) [w/])
(12)
By applying the Heavy Ball algorithm (Algorithm I to the cubic-regularizer problem we see that it generates the iterates via
W++1 we - (ww) + B(w,- wt-1) = (Ia nd pn]120)11 - n7 + B(we wi-1).
(13)
4.2 ENTERING BENIGN REGION FASTER
For the cubic-regularized problem, we define different notion of a benign region from that for the phase retrieval. The benign region here is smooth, contains the unique global optimal point w.,
and satisfies notion of one-point strong convexity (Kleinberg et al. 2018 & Yuan 2017 Safran ct al. 2020).
TRd (w w.: V((w)) O||uc w.ll3, where 0
(14)
We note that the standard strong convexity used in the definition of a benign region for phase retrieval could imply the one- one-point strong convexity here, but not vice versa (Hinder et al. (020).
Previous work of Carmon & Duchi (2019) shows that if the norm of the iterate is sufficiently large, i.c. p||w||| 2 ò for any sufficiently small 8 >> O, the iterate is in the benign region that contains the global minimizer w.. To see this, by using the gradient expression of V (ww), we have that
(w- w. vf(w)) =(w w.) (A, + & [[]w]] - ||. Il) (w w.)
(15)
+ + (1 [I 2 [[ + [lw,,])-
The first term on the r.h.s. of the equality becomes nonnegative if the matrix A, + & (1|w|| w| l becomes PSD. Since A, > (-7 p|[w. Ta, it means that if |||w|| 2 - (ellw.] - 7): the matrix becomes PSD (note that by the characterization, p||w,|| 111l--- > 0). Furthermore, if the size of iterate e|lw||| satisfies p||w|| > 7 (pl[w=] || - -)). the matrix becomes positive definite and consequently, we have that A. + 2 (1|w]] - [ 1) > 91. for number v > 0. Therefore. (15) becomes
(w w., (w)) 2 O||w w.
1 > 0.
(16)
Therefore, the benign region the cubic regularized problem can be characterized as
B = [w Rd |||wr|| > (pllw.]| })
(17)
What we are going to show is that HB with a larger value of the momentum parameter 3 enters the benign region I faster. We have the following theorem, which shows that the size of the iterate pllwell will grow very fast to exceed any level below 7. Furthermore, the larger the momentum parameter B. the faster the growth, which shows the advantage of Heavy Ball over vanilla gradient descent.
7

---

Under review as a conference paper at ICLR 2021
Theorem 2.
Fix any number 8 that satisfies 8 > O. Define T. minft p || 2 Y 8).
Suppose that the initialization satisfies wo (0)(()) 2 O. Set the momentum parameter 3 E [0, 1]. If the step size yi satisfies 1) S [AAl=+p| then Heavy Ball (Algorithm)
&
2 takes at most
log (1 + 77 3/ + +7)))
To S n1ō(1 + B/(1 + n/6)
4ppb(2)
mumber of iterations required to enter the benign region I.
Note that the case of 3 = 0 in Theorem reduces to the result of Carmon & Duchi (2019 which analyzes vanilla gradient descent. The lemma implies that the higher the momentum parameter 33, the faster that the iterate enters the benign region for which a linear convergence is possible; see also Figure
2 for the empirical results. Specifically, reduces the number of iterations Ts by factor of (1+ 3/(1 + no)) (ignoring the 3 in the log factor as its effect is small), which also implies that for smaller step size 17, the acceleration effect due to the use of momentum is more evident. The factor
can be approximately 1 + 3 for a small 1/. Lastly, the condition w (1(1) < 0 in Theorem can be satisfied by wi = w- = -r bil
for any r > 0.
Proof. (sketch; detailed proof is available in Appendix E The theorem holds trivially when y S 0, so let us assume 7 > 0. Recall the notation that w represents the projection of w on the eigenvector of the least eigenvalue (A), i.c. w(!) = (w, v1). From the update, we have that
ue (1) 7611
with -660)
+11 + A(mr") -
(Ia + - - pn|ww|]
(18)
-1b(1)
Denote ae := spbrr and in the detailed proof we will show that de 2 0 for all t S Tg. We can rewrite 18 as a++1 = (1 + 17 - -
1 B(a, a--1) 2 (1 + 15))a 1 3(a; 04-1),
where the mequality due to that p|| S 7- 5 for I S Tg. So we can now see that the dynamics is essentially in the form of (6) except that there is an additional on the r.h.s of the inequality. Therefore, we can invoke Lemma T to show that the higher the momentum, the faster the iterate enters the benign region. In Appendix E we consider the presence of on the r.h.s and obtain tighter bound than what Lemma [ can provide.
We have shown that the simple dynamic results in entering a benign region that is one-point strongly conver to faster. However, different from the case of phase retrieval, we are not aware of any prior results of showing that the iterate generated by Heavy Ball keeps staying in a region that has the property (16) once the iterate is in the region. Carmon & Duchi (2019) show that for the cubic regularized problem, the iterate generated by vanilla gradient descent stays in the region under certain conditions, which leads to linear convergence rate after it enters the benign region. Showing that the property holds for HB is not in the scope of this paper, but we empirically observe that Heavy Ball stays in the region. Subfigure (a) on Figure 2 shows that the norm [|w:]] || is monotone increasing for a wide range of 3, which means that the iterate stays in the benign region according to (17) Assuming that the iterate stays in the region, in Appendix [F] we show locally linear convergence of HB for which up to certain threshold of B, the larger the 3 the better the convergence rate.
5 DISCUSSION AND CONCLUSION
Let us conclude by discussion about the applicability of the simple dynamics to other non-convex optimization problems. Let A be a positive semi-definite matrix. Consider applying HB to top eigenvector computations, i.e. solving minmer<:|j/]ss] - = Aw, which is a non-convex optimiza- tion problem as it is about maximizing convex function. The update of HB for this objective is Wi+11 (Ia + 7y)): + B(w, w;-1). By projecting the iterate W on an eigenvector of the matrix A, we have that
(19) We see that this is in the form of the simple dynamics in Lemma [ again. So one might be able to show that the larger the momentum parameter B, the faster the top eigenvector computation. This
(We+1, u.) = (1 + (w. u.) + 3(w,, u.) (w,- u.)).
8

---

Under review as a conference paper at ICLR 2021
109
HSH(2M0
(5-(5-0.5)
funation value gap: (
125 (0-40.4)
10"
10
10
10
10
10a
10.10
100
150
50
100
150
Berations
herations
(a) norm
| vs. iteration
(b) f(wx)) f(w=) vs. iteration
Figure 2: Solving (2) with different values of momentum parameter The empirical result shows the clear
advantage of Hcavy Ball momentum. Subfigure (a) shows that larger momentum parameter results in a faster growth rate of [|we],, which confirms Lemma and shows that it enters the benign region IB faster with larger $. Note that here we have that |.-|| || 1. It suggests that the norm is non-decreasing during the execution of the algorithm for wide range of / except very large B. For 8 0.9, the above |/w.]l Subfigure (b) show that higher also accelerates the linear convergence. Now let switch to describe the setup of the experiment. We first set step size = 0.01, dimension d' = p ||w.| = ||A||2 = 1, and are sampled uniformly random in [- + gap: [|A]]]]] We draw ú = (A + pllar- Ta)) -60, where 0 ~ >((0; Ta) (A + pl (e)])aa)) [[a)), w.. The procedure makes w. the global minimizer of problem instance (A, b, p). Patterns shown on this figure exhibit for other random problem instances as well.
starts decreasing only after it arises
= 0.2 and gap = x 10 Then we set A diag([-7; -7 gap; 033; ada)). where the entries
and log, & uniform on [-1, 1]. We set w.
[|w-I| w and
|w]
connection might be used to show that the dynamics of HB momentum implicitly helps fast saddle points escape. In Appendix G we provide further discussion and show some empirical evidence. We conjecture that if non-convex optimization problem has underlying structure like the ones in this paper, then HB might be able to exploit the structure and hence makes progress faster than vanilla gradient descent.
REFERENCES
Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma. Finding approxi- mate local minima faster than gradient descent. STOC, 2017.
Zeyuan Allen-Zhu and Yuanzhi Li. Neon2: Finding local minima via first-order oracles. NeurIPS, 2018.
Yu Bai and Jason D. Lee. Beyond linearization: On quadratic and higher-order approximation of wide neural networks. ICLR, 2020.
Afonso S. Bandeira, Jameson Cahill, Dustin G. Mixon, and Aaron A. Nelson. Saving phase: Injec- tivity and stability for phase retrieval. Applied and Computational Harmonic Analysis, 2014.
Avrim Blum, John Hopcroft, and Ravindran Kannan. Foundations of data science. Neural compu- tation, 2018
Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 2014.
T. Tony Cai, Xiaodong Li, and Zongming Ma. Optimal rates of convergence for noisy sparse phase retrieval via thresholded wirtinger flow. The Annals of Statisties, 2016.
Bugra Can, Mert Gürbüzbalaban, and Lingjiong Zhu, Accelerated linear convergence stochastic momentum methods in wasserstein distances. ICML., 2019.

---

Under review as a conference paper at ICLR 2021
Emmanuel J. Candés and Xiaodong Li. Solving quadratic equations via phaselift when there about as many equations as unknowns. Foundations of Computational Mathematics, 2014.
Emmanuel J. Candés, Thomas Strohmer, and Vladislav Voroninski. Phaselift: Exact and stable signal recovery from magnitude measurements via convex programming. Communications on Pure and Applied Mathematics, 2013.
Emmanuel Candés, Xiaodong Li, and Mahdi Soltanolkotabi. Phase retrieval via wirtinger flow:
Theory and algorithms. IEEE Transactions Information Theory, 2015.
Yair Carmon and John Duchi. Gradient descent finds cubic-regularized nonconvex newton step. SIAM Journal on Optimizatiin, 2019.
Yair Carmon, John Duchi, Oliver Hinder, and Aaron Sidford. Accelerated methods for nonconvex optimization. SIAM Journal of Optimization, 2018.
You-Lin Chen and Mladen Kolar. Understanding accelerated stochastic gradient descent via the growth condition. 0rXiv:2006.06782, 2020.
Yuxin Chen and Emmanuel J. Candés. Solving random quadratic systems of equations is nearly as easy solving linear systems. Communications on Pure and Applied Mathematics, 2017.
Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, and Yuling Yan. Gradient descent with random ini- tialization: Fast global convergence for nonconvex phase retrieval. Mathematical Programming, 2018.
Yuejie Chi, Yue M. Lu, and Yuxin Chen. Nonconvex optimization meets low-rank matrix factoriza- tion: An overview. XXXiv:8809009533 2019.
Hadi Daneshmand, Jonas Kohler, Aurelien Lucchi, and Thomas Hofmann. Escaping saddles with stochastic gradients. ICML, 2018.
Damek Davis, Dmitriy Drusvyatskiy, and Courtney Paquette. The nonsmooth landscape of phase retrieval. IMA Journal on Numerical Analysis, 2018.
Jelena Diakonikolas and Michael I. Jordan. Generalized momentum- methods: A hamiltonian perspective. arXiv: 1906:v/990.004455 2019.
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.
John Duchi and Feng Ruan. Solving (most) a set of quadratic equalities: Composite optimization for robust phase retrieval. Information and Inference, 2018.
Cong Fang, Zhouchen Lin, and Tong Zhang. Sharp analysis for nonconvex sgd escaping from saddle points. COLT, 2019.
Albert Fannjiang and Thomas Strohmer. The numerics of phase retrieval. Acta Numerica, 2020.
Nicolas Flammarion and Francis Bach. From averaging to acceleration, there is only step-size. COLT, 2015.
Sébastien Gadat, Fabien Panloup, and Sofiane Saadane. Stochastic heavy ball. arXiv:1609.04228 2016.
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points - online stochastic gradient for tensor decomposition. COLT, 2015.
Rong Ge, Chi Jin, and Yi Zheng. No spurious local minima in nonconvex low rank problems: A unified geometric analysis. 2017.
Rong Ge, Tengyu Ma, and Jason D. Lee. Learning one-hidden- layer neural networks with landscape design. ICLR, 2019.
10

---

Under review as a conference paper at ICLR 2021
Euhanna Ghadimi, Hamid Reza Feyzmahdavian, and Mikael Johansson. Global convergence of the heavy-ball method for convex optimization. ECC, 2015.
Gauthier Gidel, Francis Bach, and Simon Lacoste-Julien Implicit regularization of discrete gradient dynamics in linear neural networks. NeurIPS, 2019.
Igor Gitman, Hunter Lang, Pengchuan Zhang, and Lin Xiao. Understanding the role of momentum in stochastic gradient methods. NeurIPS, 2019.
Gabriel Goh. Why momentum really works. Distill, 2017.
Gene H. Golub and Charles F. Van Loan. Matrix computations. Johns Hopkins University Press, 1996.
Suriya Gunasekar, Blake Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nathan Sre- bro. Implicit regularization in matrix factorization. NIPS, 2017.
Paul Hand, Oscar Leong, and Vladislav Voroninsk. Phase retrieval under generative prior. NeurlPS, 2018.
Oliver Hinder, Aaron Sidford, and Nimit Sohoni. Near-optimal methods for minimizing star-convex functions and beyond. COLT, 2020.
Elad Hoffer, Itay Hubara, and Daniel Soudry. Train longer, generalize better: closing the general- ization 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.
Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M. Kakade, and Michael 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.
Robert Kleinberg, Yuanzhi Li, and Yang Yuan. An alternative view: When does sgd escape local minima? ICMI,, 2018.
Walid Krichene, Kenneth F. Caluyay, and Abhishek Halder. Global convergence of second-order dynamics in two-layer neural networks. urXiv:2006.07867, 2020.
Jason D. Lee, loannis Panageas, Georgios Piliouras, Max Simchowitz, Michael Jordan, and Ben- jamin Recht. First-order methods almost always avoid strict saddle-points. Mathematical Pro- gramming, Series B, 2019.
Laurent Lessard, Benjamin Recht, and Andrew Packard. Analysis and design of optimization algo- rithms via integral quadratic constraints. SIAM Journal on Optimization, 2016.
Kfrr Y. Levy. The power of normalization: Faster evasion of saddle points. arXiv: 1.X1::661.0083/1 2016.
Huan Li and Zhouchen Lin. Provable accelerated gradient method for nonconvex low rank opti- mization. Machine Learning, 2020.
Yuanxin Li, Cong Ma. Yuxin Chen, and Yuejie Chi. Nonconvex matrix factorization from rank-one measurements. AISTATS, 2019.
Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with relu activation. NeurIPS, 2017.
Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in pwrrpparameterized matrix sensing and neural networks with quadratic activations. COLT, 2018.

---

Under review as a conference paper at ICLR 2021
Yanli Liu, Yuan Gao, and Wotao Yin. An improved analysis of stochastic gradient descent with momentum. arXiv:2007.07889, 2020.
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.
Cong Ma, Kaizheng Wang, Yuejie Chi, and Yuxin Chen. Implicit regularization in nonconvex statis- tical estimation: Gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution. Foundations of Computational Mathematics, 2017.
Junjie Ma, Ji Xu, and Arian Maleki. Optimization-based amp for phase retrieval: The impact of initialization and 12-reullarization IEEE Transactions on Information Theory, 2018.
Chris J. Maddison, Daniel Paulin, Yee Whye Teh, Brendan O' O'Donoghue, and Arnaud Doucet.
Hamiltonian descent methods. arXiv:1809.05042 2018.
Stefano Sarao Mannellia, Giulio Birolib, Chiara Cammarotac, Florent Krzakalab, Pierfrancesco Ur- bania, and Lenka Zdeborová. Complex dynamics in simple neural networks: Understanding gradient flow in phase retrieval. 2xXiv:2006.06997 2020.
Yurii Nesterov and B.T. Polyak. Cubic regularization of newton method and its global performance. Math. Program., Ser. A 108, 177-205, 2006.
Praneeth Netrapalli, Prateek Jain, and Sujay Sanghavi. Phase retrieval using alternating minimiza- tion. NIPS, 2013.
Barak A Pearlmutter. Fast exact multiplication by the hessian. Neural computation, 1994.
B.T. Polyak. Some methods of speeding up the convergence iteration methods. USSR Computa- tional Mathematics and Mathematical Physics, 1964.
Qing Qu, Yuqian Zhang, Yonina C. Eldar, and John Wright. Convolutional phase retrieval via gradient descent. NIPS, 2017.
Sashank Reddi, Manzil Zaheer, Suvrit Sra, Barnabas Poezos, Francis Bach, Ruslan Salakhutdinov, and Alex Smola. A generic approach for escaping saddle points. AISTATS, 2018.
Itay Safran, Gilad Yehudai, and Ohad Shamir. The effects of mild over-parameterization on the optimization landscape of shallow relu neural networks. arXi::2006.01005, 2020.
Michael Saunders. Notes on first-order methods for minimizing smooth functions. Lecture note, 2018.
Damien Scieur and Fabian Pedregosa. Universal average-case optimality polyak momentum. ICML, 2020.
Othmane Sebbouh, Robert M. Gower, and Aaron Defazio. On the convergence of the stochastic heavy ball method. Stti:::00000766611 2020.
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.
Mahdi Soltanolkotabi. Algorithms and theory for clustering and nonconvex quadratic programming. Stanford University Ph. D). Dissertation, 2014.
Matthew Staib, Sashank Reddi, Satyen Kale, Sanjiv Kumar, and Suvrit Sra. Escaping saddle
points with adaptive gradient methods. ICML, 2019.
12

---

Under review as a conference paper at ICLR 2021
Ju Sun, Qing Qu, and John Wright. arXiv:1504.06785, 2015.
Complete dictionary recovery over the sphere.
Ju Sun, Qing Qu, and John Wright. A geometrical analysis of phase retrieval. International Sympo- sium on Information Theory, 2016.
Tao Sun, Penghang Yin, Dongsheng Li, Chun Huang, Lei Guan, and Hao Jiang, convergence analysis of heavy-ball algorithms. AAAI, 2019.
Non-ergodic
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initializa- tion and momentum in deep learning. ICML, 2013.
Yan Shuo Tan and Roman Vershynin. Online stochastic gradient descent with arbitrary initialization solves non-smooth, non-convex phase retrieval. arXiv:19100 12837, 2019.
Stephen Tu, Ross Boczar, Max Simchowitz, Mahdi Soltanolkotabi, and Benjamin Recht. Low-rank solutions of linear matrix equations via procrustes flow. ICML, 2016.
Gang Wang, Georgios B. Giannakis, and Yonina C. Eldar. Solving systems of random quadratic equations via truncated amplitude flow. IEEE Transactions on Information Theory, 2017a.
Gang Wang, Georgios B. Giannakis, Yousef Saad, and Yonina C. Eldar. Solving most systems of random quadratic equations. NIPS, 2017b.
Jun-Kun Wang, Chi-Heng Lin, and Jacob Abernethy. Escaping saddle points faster with stochastic momentum. ICLR, 2020.
Chris D. White, Sujay Sanghavi, and Rachel Ward. The local convexity of solving systems of quadratic equations. Results in Mathematics, 2016.
Ashia C Wilson, Rebecca Roelofs, Mitchell Stern, Nathan Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. NIPS, 2017.
Huaqing Xiong, Yuejie Chi, Bin Hu, and Wei Zhang. Convergence analysis of accelerated first-order methods for phase retrieval. MTNS, 2018.
Huaqing Xiong, Yuejie Chi, Bin Hu, and Wei Zhang. Analytical convergence regions of accelerated gradient descent in nonconvex optimization under regularity condition. Automatica, 2020.
Yi Xu, Jing Rong, and Tianbao Yang. First-order stochastic algorithms for escaping from saddle points in 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. IJCAI, 2018a.
Zhuoran Yang, Lin Yang. Ethan Fang, Tuo Zhao, Zhaoran Wang, and Matey Neykov. Misspecified nonconvex statitical optimization for sparse phase retrival. Mathematical Programming, 201 8b.
Chong You, Zhihui Zhu, Qing Qu, and Yi Ma. Robust recovery via implicit bias of discrepant learning rates for double pverpparamtterization.
vrXiv:2006.08857 2020.
Huishuai Zhang, Yuejie Chi, and Yingbin Liang. Provable non-convex phase retrieval with outliers: Median truncated wirtinger flow. ICML, 2017a
Huishuai Zhang, Yi Zhou, Yingbin I Liang, and Yuejie Chi. A nonconvex approach for phase retrieval: Reshaped wirtinger flow and incremental algorithms. .MLRR, 2017b.
Qinqing Zheng and John Lafferty. A convergent gradient descent algorithm for rank minimization and semidefinite programming from random linear measurements. NIPS, 2015.
Yi Zhou, Huishuai Zhang, and Yingbin Liang. Geometrical properties and accelerated gradient solvers of non-convex phase retrieval. IEEE Allerton Conference Communication, Control, and Computing, 2016.
13

---

Under review as a conference paper at ICLR 2021
A RELATED WORKS
A.1 HEAVY BALL
We first note that Algorithm and given the same initialization Wp, the same step size 1). and the same momentum parameter 3.
and Algorithm 2 generate the same sequence of the iterates {w,) }
Lessard et al. (2016) analyze the Heavy Ball algorithm for strongly convex quadratic functions by using tools from dynamical systems and prove its accelerated linear rate. [hhadimi et al.] (2015)
also show an (1/T) ergodic convergence rate for general smooth convex problems, while Sun ee al. (2019) show the last iterate convergence on some classes of convex problems. Nevertheless, the convergence rate of both results are not better than gradient descent. [Maddison et al. (2018)
and Diakonikolas & Jordan (2019) study a class of momentum methods which includes Heavy Ball by continuous time analysis. Can et al. (2019) prove an accelerated línear convergence stationary distribution for strongly convex quadratic functions under Wasserstein distance. Gitman al. (2019) analyze the stationary distribution of the iterate of a class of momentum methods that includes SGI with momentum for quadratic function with noise, as well as studying the condition of its asymptotic convergence. [oizou & Richtárík (2017) show linear convergence results of the Heavy Ball method for broad class of least-squares problems. [oizou & Richtárik (2018) study solving a average consensus problem by HB, which could be viewed as a strongly convex quadratic function. [Sebbouh et al. (2020) show a convergence result of stochastic HB under smooth convex setting and show that it can outperform SGD under the assumption that the data is interpolated. Chen & Kolar (2020) study stochastic HB under growth condition. Yang al. (2018a) show an O(I/VT) rate of convergence in expected gradient norm for smooth non-convex problems, but the rate is not better than SGD. et al. (2020) provide an improved analysis of SGD with momentum. They show that SGD with momentum can converge as fast as SGD for smooth nonconvex settings in terms of the expected gradient norm. Krichene et al. (020) show that in the continuous time regime, i.e infinitesimal step size is used, stochastic HB converges to a stationary solution asymptotically for training one- he-hhhdd--lleer network with infinite number of neurons, but the result does not show a clear advantage compared to standard SGD. Lastly, Wang et al.](200) show that the Heavy Ball's momentum can help to escape saddle points faster and find second order stationary point faster for smooth non-convex optimization. However, while their work focused on the stochastic setting, their main result required two assumptions the statistical properties of the sequence of observed gradients; it is not clear whether these would hold in general. Specifically, they make an assumption called APAG (Almost Positively Aligned with Gradient). i.e. [ m, ) is the deterministic gradient, 9t is the stochastic gradient, and
g.)l 2 - f where (w)) me is the stochastic momentum. They also make an assumption called APCG (Almost Positively Correlated with Gradien(), i.e. EE, [V (w:),, M,ma)] 2 ma1))mxx(MM) [V (wx where M, is PSD) matrix that is related to local optimization landscape.
We also note that there are negative results regarding Heavy Ball (see e.g. Lessard et al. 2016 Ghadimi et al. (0015): Kidambi et al. (2118).
A.2 MATRIX SENSING
Problem can also be viewed as a special case of matrix factorization matrix sensing. To see this, one can rewrite as mingreRaxi 1 En (y:- (A,, UUT))) where A, = x... E Raxd and the dot product represents the matrix trace, Li et al. (2018) show that when the matrices {Ai} satisfy restricted isometry property (RIP) and U E [a gradient descent can converge to a global solution with a toose-to-zero random initialization. Yet, if the matrix A, in the form of a rank-one matrix product, the matrix might not satisfy RIP and a modification of the algorithm might be required (Li al. (20T8)) ). Li et al. (2019), a different group of authors, show that with a carefully -desigge initialization (e.g. spectral initialization), gradient descent will be in a benign region in the beginning and will converge to a global optimal point. In our work, we do not assume that æ.,, satisfies RIP neither do we assume carefully-designel
4n
initialization like spectral initialization is available. Li & Lin (2020) show a local convergence to an optimal solution by Nesterov's 's momentum for a matrix factorization problem: the initial point needs to be in the neighborhood of an optimal solution. In contrast, we study Polyak's 's momentum and are able to establish global convergence to an optimal solution with simple random initialization. Gunasekar al. (2017); Gidel et al. (2019) You et al.
14

---

Under review as a conference paper at ICLR 2021
2020) study implicit regularization of gradient descent for the matrix sensing/matrix factorization problem. The directions are different from ours.
B POPULATION GRADIENT
Lemma 2. Assume that ||w,||
Eg~N(O.1a) [(x "))x (x: (x) (3||o]1 - 1)w -2(w- w.w.
Proof. In the following, denote
Q = E[(xx T w)
= E[(x T w. )2(x ToTwo w)z]
Now define h(w) : E[(x' T w) We have that h(w)) 3|/wo| 1 as IT ((0,|//l3) (i.e. the fourth order moment). Then,
Vh(w) = 4E[(2 T [) = 4Q.
So Q | Vh(w) = 3| Fw.
For the other term, define g(w)
[x T (xx (x=TT ?) Given that
x w x
lwe I1 w w
w w
N
(20)
w
we can write
x ~ 0,x w + 02
=I w T and 03 = ||..1
[mn] w=)
where z ~ NOO, 1), 0 ==
Then,
g(w) ([T[(( w))* 20 02 xx)² + (3r (x)
3(w, w)² + = ())
2(w, w)² + ||
So we have that
Vg(w) = 2B[(x T w. (x w)/] = 2R,
which in turn implies that
R V= Combining the above results, we have that
1 2 2 (4(w] w.w, + 22|ww|lww) = 2( w)w- + ||w. 1w..
VF(w)= = R 3 ||w,|1? 2(w. w)w, (3||w|1 1)w w 2(w w.w. (21)
C SIMPLE LEMMAS
For a positive number 0 and the momentum parameter B [0, if non-negative sequence { satisfies on 2 a-1 > and that for all 1. < T,
Lemma 1
0++1 2 (1 + f) + B(az at-1),
(22)
then {at) satisfies
a++1 2 [1+ (1+ I+8 00) ae.
(23)
for every 1,..., T 11 Similarly, i non-positive sequence {ar) satisfies ag S a_ 0 and that for all T, ac+1 < (1+ 0)a - B(aa a1-1), then {ar} satisfies
a++1 - 1 + (1+ 1+6 9 o
(24)
for every 1,..., T
15

---

Under review as a conference paper at ICLR 2021
Proof. Let first prove the first part of the statement. In the following, denote c: 140 For the base case / = 1, we have that
2 (1 + 0)1 + B(11 aa) 2 (1 + 0) + B.f01.
(25)
where the last inequality holds because a1 ao 2 8ca1 < anc nu 01 2 (1 + 8)ao
I-02 ag. Now suppose that it holds at iteration t, ac+1 2 (1 -3)00)aa. Consider iteration t ++11, 1,
we have that
att2 2 (1+ 0) + ((a++1 a1) 2 (1 - 1 Bcpar-1.
(26)
where the last incquality holds because ac+1 at 2 8ca++1 = a++1 2 1- as a++1 2
(1 + (1 + Be)0)a, Ir given the assumption at and chat := I40
The second part of the statement can be proved similarly.
Lemma 3. For a positive number 0 < and the momentum parameter 3 [0, that satisfy
(1 B 0 1, if non-negative sequence {be} satisfies bo b-1 and that for all S T,
d1+1 S - -0)b + 3(bb -b-1):
(27)
then {br} satisfies
b++1 S (1- T )0 be:
(28)
for every t = I.....TT T + 1. Similarly, if a non-positive sequence }bi} satisfies bo 2 b-1 and that for all T, b41 (1 0)b, + B(b, bt-1), then {be} satisfies
b,+1 2 (1 11-11- 1-6 00) be:
(29)
for every t 1,...,, +
Proof. Let us first prove the first part of the statement. In the following, we denote c:= the base case 1, we have that
1 For
I-7-
62 S (1 - (160)61 + 3(b 60) s (1 -06b - Be0bb,
(30)
where the last inequality holds because
1
bj bu S -Oeby > by < bo:
(31)
1
Oc
as b2 < (1-8)bb 1+8c
1 by due to that c 1-6
1 Now suppose that it holds at iteration t.
be+1 S (1- (1)))))c)))bb bc)
Consider iteration t 1, we have that
b S (1 0)bc+1 + B(b++1 b.) < (1 100bbt+1 OcBbr41
(32)
where the last inequality holds because
b - be < -0bbr+1
b 5
1 0c by
(33)
as 1 S (1- (1 Bc)0)b < 1 bt, due to the induction at and that 1-0*
The second part of the statement be proved similarly.
16

---

Under review as a conference paper at ICLR 2021
D PROOF OF THEOREM
Recall the recursive system
W1+1 (1 3 (1 ||0, (12) n/Ee) ju! + B(w! w. w " [1] = (1 + ( 3/ (1 + nP:,)) wt [)] + B(wF [i] w 11).
(34)
where {&r} and {Pts} are the perturbation terms. In the analysis, we will show that the sign of w never changes during the execution of the algorithm. Our analysis divides the iterations of the first stage to several sub-stages. We assume that the size of the initial point wp is small so that it begins in Stage 1.1.
(Stage 1.1) considers the duration when ||a,y]| || I
V $ + cn, cn. which lasts for at most To
iterations, where To is defined in Lemma A by-product of our analysis shows that WT++1
/ + Cr.
(Stage 1.2) considers the duration when the perpendicular component || || is decreasing and eventually falls below </2, which consists of all iterations To < t S To To where Ti is defined in Lemma 5
(Stage 1.3) considers the duration when wy is converging the interval [1 $ 1+ $) it was outside the interval, which consists of all iterations To + T. S t S To + To + To where T, is defined Lemma
In stage 1.1, both the signal component (w]] and ||w grow in the beginning (see also Figure The signal component grows exponentially and consequently it only takes logarithm number of iterations To + to reach |w/.+11
+ Ca. which also means that ||wT++1ll > + Cn- Moreover, the larger the momentum parameter B, the smaller the number To. After ||,, | passing the threshold, the iterate enters Stage 1.2.
log( log( log(v/++e=//el)) iterations
Lemma 4. (Stage 1.1) Denote c. =- = There will be at most To
log (1+(2+c,810)
such that w < + Cy- Furthermore, for all I in this stage, [!wlll < mu6
In stage 1.2, we have that ||
that the perpendicular component [ is decaying while the signal component |w] keeps growing before reaching 1 (see also Figure 1 In particular, the perpendicular component decays exponentially so that at most additional To iterations needed to fall below (i.e. ||w || S {)) with larger leading to a smaller number of Tb. Notice
> |w! c
that if w satisfies |//|| |-1 < & when ||w falls below 5. we immediately have that Tę < To+Ti; otherwise, the iterate enters the next stage, Stage 1.3.
Lemma 5. (Stage 1.2) Denote o := -' and w == max, |mmm || S V + c.. There will be at most
logí (.) Te < Log(1 f (1+ iterations such that v + S |ue!| and [!w! 2 S.
In stage 1.3, show that |u!| converges towards linearly, given that ||w < $. Specifically, after at most additional T2 iterations, have that |!l!|| - & and that larger reduces the number iterations T..
1 Lemma 6. (Stage 1.3) Denote Cç.9 it78 Cg.d I-78 and w = max, |uo!l v There will be at most To max /og((11c/2)) /ttco) log( 2t5/2) log(1+n 9)) log(l (g11-
10 Jem
iterations such that
| - 1| & and || S.
17

---

Under review as a conference paper at ICLR 2021
By combining the result of Lemma
4 Lemma
and Lemma 6 we have that
log(
+
log(
T $ To To +
log (1 + 7 + ca.
log 3/ + cb,3)
log( 1-5/2 V +0
log( 1+c/2)
max
log(1 1 1/2 (1 + 8)) log(1 - 175(1 + cg.a(3))
6 log( will 5 + ca
Vā+eo
6 6log( 20
2 2log( 1-(/2
log w 1+2/2
v Vota"
+
+ max
(11 + ca8)
77(1 + 3),
1/((1 + +cc,))))
log d
17 (1 + G)
(35)
where the last inequality uses that |om|| 2 Válogd due the random isotropic initialization. The detailed proof of Lemma available in the following subsections.
1
After & 2 T. the iterate enters benign region that is locally strong convex, smooth, twice differ- entiable, and contains w, (or -w-) (Ma et al. 2017 White et al. 2016), which allows us to use the existing result of gradient descent with Heavy Ball momentum for showing its linear conver- gence. In particular, the result of local landscape (e.g. |M et al. (2017); White et (2016) and the known convergence result of gradient descent with Heavy Ball momentum (e.g. [Saunders (2018); Polyak (1964): Lessard et al. (2016); Xiong et al. (2020)) can be used to show that for all / >> Tc.
dist(w,, W.) S (1 2) Tc disdt (WT W.) S (1 - 2) TA-TTC for some number 1 > V/ >
D.1 STAGE 1.1
Lemma: (Stage 1.1) Denote Ca = T There will be most To = logl (onnr/lrll))
loR (I+(++c001n))
iterations such that [| I V + Cn. Furthermore, we have that |w/++1 > V + cn. cn.
Proof. Let first assume that w!! 0 and denote at w!! By using that ||wall| S / cn in this stage, we can lower-bound the growth rate of a, as
a++1 2 (1 + ++3 - ||we|| 12) - v)(Ee))at + B(ax ac-1)
4
37(1
+ cn) -cn)at + B(a, a:-1)
9
(36)
1 0t + B(aa= a111)
(1 + (1 + ca 3n oz.
where in the last inequality we use Lemma and that
Ca
(37)
77
Observe that (1+ (1 ca > 1. Consequently, the sign of wi never change in this stage. So
for w || 2 / + Cn it takes number of iterations at most
2 log V Vātan bwed
log(
To : log (1 + (1 + ca ()))
S
(38)
(1 3)
Similar, when w! < 0. we can show that after at most To iterations, w!! falls below -1 - + on-
Since |wm]| > | it means that there will be at most To iterations such that ||wy|| S / Cn- O
18

---

Under review as a conference paper at ICLR 2021
D.2 STAGE 1.2
Lemma 5: (Stage 1.2) Denote cb r-z and w == max, 1 || S V $ + Cn. There will be at
most T3 = log(1 (1+0)))
log( (
iterations such that v + Cn S |!!! and | 2 5
Proof. Let t' be the last iteration of the previous stage. We have that || 2 | 2 V + on-
Denote 0e := |. In this stage, we have that keeps increasing until ||w || 2 1. Moreover,
wi remains the same sign as the previous stage. Now fix an element j and denote b; Iu, From Lemma 7
we know that the magnitude b, == l [i] is non-increasing in this stage.
Furthermore, we can show the decay of b, follows. w. [5]. w--lli 0.
w1+1/5] & (1 + n111 3/1w, 122) n ww ((wr [j] w
$ (1 + n1( - 3( 4
+ cw)) + np., m. + ((w) - -
(39)
$ 3) [i] + B(wrlj] - -
< (1 (1 ct,3) c.,9))mai),,
where in the last inequality used Lemma as the condition (1++ 1+-g) < is satisfied, and denote that
C6 1
(40)
1/33
On the other hand, if we [i]. w.- [b]] 0.
We+1 [i] 2 (1 + 1 - w/ 12) + nlpt. welil + 3(we [i] - wt- (5])
2 (1 + 7 3( 4
+ cn)) + nc., wi + ((w.li) w(-1(())
(41)
3 wrLi]] + B(wr [i] w))
"
2
2 (1 ? (1 cc,3) weli],
9 where in the last inequality we used Lemma as the condition (1 -- } < 1 is satisfied, and we denote that
(42)
1- n/3
The inequalities of (39 and (41) allow us to write |we+1 bill S (1 (1 [ + cxB)) (w. [.]l Taking the square of both sides and summing all dimension j * we have that
| 2 < (1 77 + c,,3)) 1w
(43)
Consequently, for [|w/- to fall below </2, it takes at most
log( </2 Twgl
log( 255
Te = log(1 1 [1 c))
1
(44)
log(1 3 co,3))
iterations.
Lastly, Lemma implies that at the time that the magnitude of w. [i] starts decreasing, ||w. + Cn. which in turn implies that w = max; || || < v + cn.
19

---

Under review as a conference paper at ICLR 2021
D.3 STAGE 1.3
Lemma (Stage 1.3) Denote c(a = 1t "g = 1
1-755 and = max, Iin! S
10 jcm
9
There will be at most To = max 1og((1-1/3)/ +cx)
log( 145/2)
iterations such that log(1 1ell--s11 -011+
log(1+n (1)
|| - 1 and ||0
Proof. Denote 5' the last iteration of the previous stage. We have that t' - To Tb. Since 1 does not change the sign in stage 1.1 and 1.2, w.l.og,, we assume that ! > 0. Denote == w. We consider ay in two cases: ae I 1 and 2 1 + 5. If ae S 1 2. then we have that for all in this stage, || s at + || 1|2 < (1 5)2 ($)
$. for any sufficiently small Ç. So a
grows as follows.
a++1 2 (1 + 3 - | | - r)EEl)at + B(ac ac-1)
C
2V (1 + 3n
ntn)) + B((c ac-1)
2
IV
(45)
(1 7/
ar + 3((c ac-1)
- (1 + 3))
(1 2
where (a) is by Ç on and (b) is due to that Lemma and that
cc.9
(46)
1 172
Consequently, takes at most
log 1-c/2
V 6m
(47)
log(1 + n/ (1 + o),
number of iterations this stage for at to rise above - $- On the other hand, if ag 2 1 +
2. then
can lower bound [[w]]] 22 in this stage ||w; 1|2 2 af (1 5)2. We have that
S (1 + 31/(1 - ||w, + w/(ll)a + B(a: ac-1)
0++1
W
(1 37pC + c..
c.) az + 3(a; az-1)
(48)
5 w
(1 n5)at ar + B(a ar-1)
(6)
(1 n1(1 + cc.a3))
where (a) uses on and (b) Lemma
1
(49)
ny
That is, a decreasing towards 2/2. Denote w = max, |
we see that takes at most
log 1+c/2
(50)
log(1-17( - ( + cc,a8))
number of iterations in this stage for a, to fall below + </2. Lastly, Lemma & implies that the time that the magnitude of w!! starts decreasing, |w,,|' 2 < 10 Ca. which in turn implies that
== max, |w!|| < + cn-
On the other hand, by Lemma 10, the magnitude of the perpendicular component is non-increasing in this stage, and hence |mw keeps staying below Ç/2.
Similar analysis holds for w! < 0. hence we omitted the details.
20

---

Under review as a conference paper at ICLR 2021
D.4 SOME SUPPORTING LEMMAS
Lemma 7. Suppose that satisfies S
36 tea) max(cm.1) Let to be the first time such that
|wwt 2 3 + Cn. Then, there exists time T such that w++1li] S w [i]. if w [il 2 0; Similarly, wi+1l5] 2 w [i], if w [}] O. Furthermore, we have that ||wto 112 S $ + Ca-
Proof. Recall that wit1li] [j] = (1 + 711 3/luxell?)) + (or))) w of [i] + (( [j] - -i)) W.l.o.g. let us consider w [j] > 0. Assume that we [5] 2 w. [D] for all t I to: otherwise, there exists a time T < to such that w [j] S wi11
Denote Ato := 7 3/ 113) + T)Pro.j- Since || 1 1 23 + Cn. we have that Aeo S 0. We can rewrite the dynamics
Who [b11 w [i]
1 Atour + B
-3
to [i] wio [i]]
=
(51)
We have that
Twttt1l0 [6]] w Gil
1 + too
-9
||2 w [i] wio-1
1
(52)
0
> 0, which means that the magnitude of w' [j] has stopped increasing. It suffices to show that the spectral norm of the matrix || 1 + Aod +
We will show that w/++1bi S - if -
-8 lla is not greater than 1.
Note that the roots of the characteristic equation of the matrix, z² (1 + Aoo + B)z + B are =()
If the roots complex conjugate, then the magnitude of the roots is at most vB; consequently the spectral norm is at most /B S 1. On the other hand, if the roots are real, to show that the larger root not larger than 1, it suffices to show that /(1 + Atoui + 3)2 43 < - Ato.j - 3, which guaranteed if Aeo I 0. To show that the smaller root is not greater than 1, we need to show that
v(1 Ata + 8)2 43 < 3 Ataii + B, which is guaranteed if Ata 2 11
By definition, || - 112
1 }. then by invoking Lemma Cn. If 7 min{ 36 - ? 18cm
have that || 2| ||wte 1 1 < y/2 and consequently, we have that || 11 S + Gn. Thus, by choosing 1) satisfies 1) S 36( 36(1/3+c.)e.. we have that ||wt, 1|2 S + Ca- Using the upper-bound of || and the constraint of 17, we have that Ato ( +
-1 11.
Similar analysis when w [J] is negative; and hence omitted.
Lemma 8. Suppose that n satisfies 1) S
Let t1 be the first time (if exist) such 36(1 (1(+ (ra) max(cm.1))
that |/we, 2|2 2 + cn Then, there exists time T S t1 such that will wit S w!! if w Similarly, w++1 2 w!!, if w!! I 0. Furthermore, have that |w,, <
10
+ Co.
Proof. Recall that whff (1 3m - | [12) + w + 3( w!L.). W.L.o.g, let consider
Wo > 0. Assume that wi!! 2 w._, for all t s f1: otherwise, there exists time 7 < ti such that wr < wh-1--
Denote >o₁ := 37y(1 - l|we, 112) + ne.. Since ||wr, 1| 2 1 + Cn, we have that d S 0. We can rewrite the dynamics as
W
1 + Ao, + 3 B
W
(53)
||
W
W
21

---

Under review as a conference paper at ICLR 2021
We have that
W
X, +B
-9
1la
W
F1
11-
(54)
0
1
The analysis essentially follows the same lines Lemma Specifically, show that w wh++1 5
"/--1 -11 it suffices ensure that λ 33y(1 || W/, (13) + S [-1,0]. We have that )a, by
the definition of t1. Furthermore, by the definition of 1 we have that [/a 1112
+
3 cr. So
1 S min 36 - T8rm }. then by invoking Lemma we have that I|w,, 1|2 wr,, 11
and consequently, we have that [|we, 1|2 < 10
9 + Thus, by choosing v) satisfies 1j S
36 1+ 11
we have that ||,,, _ <
3 Cn. Using this upper-bound of ||w,, 2| and the constraint of we have that X, 2 -nn + 2c,)) 2 -1. Therefore, we have completed the proof.
10 +
g
Lemma 9. Assume that the norm of the momentum is bounded for all S Ts. i.e. [mmell C. Vt S Then, have that
Te. Set the step size n satisfies 1) S min 36 wll|mm 186m
|| - || 12 -
9"
Proof. To see this, we will use the alternative presentation Algorithm 2 which shows that w; Wt-1 1m4-1, where the momentum m4-1 stands for the weighted sum of gradients up (and
including) iteration i.e. m4-1 Ei (0 Using the expression, can expand ||w.||" ||w,-1|1 2|2 as
|| 2| / 11| 1| |1p1 m-m- 1112
|ww-1ll 11? -21(we-1, m--1) + n7 1mm-11?
1
(55)
< w- ||| ||| 1/|1m0 1
9
where the last inequality holds if 17 S minf 36/ un 1 ilee 18em
Lemma 10. Fix an index j. Set r S
36(1+ 1 max 1) and B < Suppose that ||we|| 2 + Cz.
Wi [i]
If for number R we have that
then ||
|
s
R.
w Lo-ibl
w. [il
Proof. The proof is similar that of Lemma
7
We have that
w [ wi [i]
1
A + 3
-3
w [ w
12
||-
(56)
Denote >r. 77(1 3/1u8 31/2
+ nPt.j- As the proof of Lemma
to show that the spectral norm
1 + A
+ B
-9
of the matrix ||
||a is greater than one. It suffices to have B < and
1
0
that Xo, E [-, By the assumption, it holds that ||w/|| 2 3 + Cn. so we have that At,j S Furthermore, by Lemma if the step size 1) satisfies S 36 [1 cm)) max(cm we have that
||w/]| < 10 + J.a. Therefore, using the upper-bound of the step size and the norm, we can obtain that At.j := 711 - 3) + mP..j 2 -1. Hence, we have completed the proof.
22

---

Under review as a conference paper at ICLR 2021
E PROOF OF THEOREM 2
To prove Theorem
2 we will need the following lemma.
Lemma 11. Fix any number ê O. Define Ta minft pl w|| 2 7 8). Assume that
7 S A + Suppose that w (1) b()) & Then, we have that w ((() Σ for all 0 S $ Tg.
Proof. The lemma holds trivially when 7 S 0, so let assume 7 >>0 O.
Recall the Heavy Ball generates the iterates as
wit1 = (1 - 1 pmll pnllwal))uf myb11) + B(ww)) w
We are going to show that for all 4,
W w (1)
(()
< 0 and (w. (2) (1)-wwh (2) w1 S -ch wt (())
(57)
for any constant Cbw
0.
The initialization guarantees that w/ (1) S 0 and that (wgg (1)
w=1 (6()) = < -bn 10 (1) (2). Suppose that (7p is true at iteration L. Consider iteration L + 1.
(1) b(1) (1))0))
(1) ( (A) pmllw, (I) m 1 (()) )(b())) + 8(w, w(-1)60) )000
wi+1
< (1 - n1 pnl[well - Bcow) w ()) 7(6(1))
(58)
00
where the first inequality is by induction at iteration and the second one is true if (1 - 11-1)(1) pr]|w>]|| BCow) 2 O, which gives constraints about 17.
- () pnnl 2 Cow
(59)
Now let us switch to show that (wif1 w 16) S -cw 2 bO), which is equivalent to showing
that (1) ((1) I 1+cw
1 with (()) From 58) it suffices to show that
(1 (A) - pn) p
well )eb ( n)(61)2 S + Cbw
w. Db)))
(60)
Since w (1)()) < sufficient condition of the above inequality is
(A) - -pnllur BBb
0.
(61)
+ Cbu
Now using that pl|w;|| || < 7 - and that
1 1+z I 1 - for for I E [0, 1]. It suffices to have that
77a (A) 177 8) Bcbw
1 17 BBbb - 1 Cbw 2 17
2 Cbw
2 0. (62)
+ Cbw
By setting Chw O, we have that the inequality is satisfied. Substituting Ctw that
59 we have
1 (() + p||we|l
Recall that e||well 5 - for all S Tg. So we have that v S by using that p|[w,|| > 7, it suffices to have that n S TA
|| (1-6) Furthermore,
We have completed the proof.
Given Lemma II we are ready for proving Theorem
Proof. (of Theorem The lemma holds trivially when 7 0, so let assume ? > 0. Recall the notation that w(l) represents the projection of the cigenvector ii of the least eigenvalue (1) (A), i.e. w(1)) -(w, vi, From the update rule, we have that
B(w, 11) w (1)
(Ia 77 pml w
11
(63)
23

---

Under review as a conference paper at ICLR 2021
Denote Or = -nbay
We can rewrite (63) as
ae+1 = (1 myy pnllwell)a + + 3(ae- 04-1) 2 (1 + n0)a 04 +1 B(a 02-1),
(64)
7 8 for Ts. Now we are going to show that, a++1 2 (1+10+ + vi B)a +1 For the above inequality to hold, it suffices to show that a, dg-1 Z n6
where the inequality is due to that p/|wal| s 7
T4 dr. That is, 2 T-m8/(1+0,, "1 The base case t = 1 holds because ai (1 110000 + 2 (-78/ 40. Suppose that at iteration t, we have that 2 I- at-1- Consider t + 1, we have that d++1 2 (1 + 176)a, + + f(aat - a1-1) 2 (1 + n70Ja + 1- (t: where
the second last inequality is because at 1- d implies at 2 01-1. Therefore, (1) "Hi -x6() = (Ia + my - prll 1 +1+
have completed the induction. So we have shown that nó
8(we 1 -m
w(th 7hEaT
(1 (1+11) 170 + I+no.
3)
+ 1. Recursively expanding the inequality, we have that
w (1) 0,
2 (1 + 70 +
np
3) -nb())
+ 2 (1+ + 26 I+:8
3)
w -gb() + (1 + no +
nd 5) + 1
I+mo
I+48
((1 + n7 + T+n6 B) 1).
n8(1+ 1475)
(65)
(0) Therefore, 2-6 2 [urr || 2 |w//11
(
((1 + no + 1+n8 T) - 1) where (a) uses that
8+58/(1-0 76)
for S To, pl|well || S 7 ö, and (b) uses 655 and Lemma 11 that wi (2) ((1) < 0. Consequently,
log (1+ (0-1)0000 T3 s
الاهاا
2 mM M01+3/ (1+7))) log (1 (1-0))((+-/(++66))
log(1 +. n5 8)
||5(0]
(66)
7M(++8/1++0)) log (1 22 21(+1/1(+6))
where (a) uses that log(1 x))= 2 2 for any 10,~ 2.51]. and (b) uses 76 - 82 S 7
F CONVERGENCE HB FOR THE CUBIC- BEECC-RRULLAIZRRR PROBLEM
Theorem 3. Assume that the iterate stays in the benign region that exhibits one-point strong vexity to w., i.e. B == {w E Idd p| 2 8} for a number 5 >> O, once enters the benign region. Denote connerge ==
1-2ncs (-2ncc(pllee 11-)) where C2 and čg are some constants
28n
that satisfy 0.5 > C8 > and dg > O. Suppose that there number R, such that the size of the iterate satisfies ||w=|| < R for all during the execution of the algorithm and that llw,]l S R. Denote I. == ||A||2 2pR. Also, suppose that the momentum purameter 3 [0, 0.65) and that
dges (pllw=l] (1
the step size n satisfies 1 S min (IQTA, 1426p8) (50L++2(66)) ( [1A.
Set
wo w-1 -------- गहं for any sufficiently small > Then, in the benign region it takes most
UST
log( Al 2l
nes(plu,, [-+)(1+ conuarge
2c
number of iterations to reach an e-approximate error, where ē = 4R + nO) with = 4
3 (o 7) 3(2ocs(p)) y) + 10
Note that the constraint of 7 ensures that Tcs(ppluu, - 7) < 1 as consequence, connerge < 1. Theorem 3 indicates that up to an tpper-threshold, a larger value of 3 reduces the number of iterations to linearly converge to e-optimal point, and hence leads to a faster convergence.
Let us now make a few remarks. First, we want to emphasize that in the linear convergence rate regime, a constant factor improvement of the convergence rate (i.e. of here) means that the slope of the curve in the log plot of optimization value iteration is steeper. Our experimental result
24

---

Under review as a conference paper at ICLR 2021
(Figure 2 confirms this. In this figure, parameter & has a steeper slope than that of the smaller ones. The slope is steeper as B increases, which justifies the effectiveness of the momentum in the linear convergence regime. Our theoretical result also indicates that the acceleration due to the use of momentum is more evident for a small step size 1/. When v is sufficiently small, the number Ceonverge are close 1, which means that the number of iterations can be reduced approximately by factor of 1 + B.
see that the curve corresponds to a larger momentum
Secondly, from the theorem, one will need [b()] be non zeroe which can be guaranteed with a high probability by adding some Gaussian perturbation on b. We refer the readers to Section 4.2 of Carmon & Duchi (2019) for the technique.
To prove Theorem 3
we will need series of lemmas which is given in the following subsection.
F.1 SOME SUPPORTING LEMMAS
Lemma 12. Denote sequences de == 2 (11voal| - [/well) []]] - w..1? cx = -(wr wA) A2) w.). 9t= == -111[=111 - wlll (1[ws + ||w; (epp@l/lwel1 where cw == 1-8 and E = (1 + cw) + (1 + )2 For all t, we have that
23
t-1 g6-1-e (do + te ga).
(w/- w0:: - 1) + cw 1w wo-1l
S
Proof. We use induction for the proof. The base case 1 = 0 holds, because whp = w-1 by ini- tialization and both sides of the inequality is O. Let assume that it holds at iteration t. That is, (we- Way th w)-1) + Cur Curllu - w 22 n Ex= (d- + e, + gs). Consider iteration t+ 1. We want to prove that
(we+1 - Wt. W++1 - w/) + Car W| w;l1 S B $ (de + te + ga).
8=1
Denote A = W1+1 wi. It is equivalent to showing that (A, Wi + A - w.) + cw 1|12 1 + c, + g.).. or
17 Ei
(-1/V/ / (wr) + B(w, w(-1), we w. - (/(((( + +B(w: -w(-1)
(67)
+ cwll - V + B(wr - wi w111)11 S Σ gr (dg + c, 1o+00 ga).
which is in turn equivalent to showing that
n V (we), we w.) +n² (1 + Cwr) | [V](())]l [ 22/3(1 + Co) (V (we), wi wi-1)
(a)
(b)
(0)
+ (w, 11-1, 1, - w.) + 181, wz-1l1 2 + c.n. 3 - w1
(68)
< 17 g (ds + + 9.).
1=1
For term (a), we have that
(w) Ws, V ff((w)
= (wi w A, (wr - w.) + p(llwell - || (1( - w[ww) we)
= (wi w.) (A. + = [(1wrl - -1(w-l1) (w) - w.) + f.((110 (1w. - -1[wz 11) 2 ((((( + -I[w=ll).
= (wi w.)T (wi - w.) + o
2 (1| - [|..11D]l w. 11. + P (1|wa || - -[ 2 ([1 |l + || I))
2
(69)
Notice that A, 2 +y+ pll., I| 2 OI2, as p||wa|| 2 7. On the other hand, for term (b), we get that [V:(2))]1 = |AA(w: - w..) - p([1w=1] Il - /
(70)
S 2(wr - A. A3 - -wa)= + 2p² (1] - [! 2 2/[wa/12
25

---

Under review as a conference paper at ICLR 2021
For term (c), can bound it as
(w) 3 /u - -1
1 (2 2 = (1 + (.) 12 + B - 11-1
112 1
(71)
Combining the above, we have that
-V(V((u)) we m.) + (1 + can +wm)lll\\ -nn0( +w (v)(V)(( wt w(-1)
+ B(w, w1-1, we -.) + 3 w|l - w- + cw. 11 11
-w;))(w;) Wt w-) 1/ 2. Vf( Blwe 11-11 w/ w.) B2 c.m w.-1l 112
s -n(wre w.) T - 27/0 A?) (wr - w.)
(b(1looll - ||w;11) (|m., [. | 4mp u0 112) + 1 P (1|wal) 11 wall
+ B(ws= - 11-1, W0 w.) + (2 + Cx: |1 || - 1112
=B(w,- -1, +C0 -w---w--11
8 1- (dg + +0) n(d 6 + 9c) + n3
-=) := 17 Σ g sd, co + go).
(72)
where in the second last inequality used B(2 + cw) = cw and the last inequality we used the assumption at iteration t. So we have completed the induction.
Lemma 13. Assume that for all t. ||we|| < R for some number R. Following the notations used in
Lemma 12 we denote sequences d, := [[[ww. || - [|w,ll) w.ll3, e, == -ww; w.) (A.
A2)
W.). 9t- == - -[[[]w.]
((w) (I|w=1 || - ||w,]| 4npo:r//well (l)), where Cw := T-B
28
and ew == + cw) (1 + cwm) Let us also denote ep (2,3² 433 + LB), = ||Al2 + 2pR,
and 21 = Ei=o 3r ++ V (w,)) If satisfies: (1) n I 2pl
1+8
and (2) n S a Allla
1+3
then we have
that for all t,
|| |1+1 w
< (1 17(1 + 9) [pllwell (7 pl|w,l| " 1]) lw-- woll
+ 122 (w:-1- w.) (2c,A² 2,3 LIa + 2capp I2)) w.) + 12(cc 2c 12, (73)
L-2
+ 3 Σ gr 3r-2-s te te,+o + g.).
==
Proof. Recall that the update of heavy ball is
0++1 w. ([((w) + 3(we wt-1)=
(74)
26

---

Under review as a conference paper at ICLR 2021
So the distance term can be decomposed as
||a+11 - w.ll²
=1 -| - (ww) + B(w; - w(-1) - will
-1|W: - w.112 - 2n(wwr W. (((w)) + 17 V (1))
+ + Wr- 112 21/B(w: w.- > /
ww) wz
=1|w;- w.ll² -2n w. vf(w))) +
W1-11 + 32 |w, wt-1ll 2m/ w., v[(w))) - 2n -1 - VS(we)
+ (wr - w.) [(,; - w(-1)
= =|| - w.ll2 - 22n((1 + (3) (wi - Whr Vs(w)) +1/ [VS(mr))
(a)
+ (8 23) w 2n 11-1, V ff(w))) + 23(ww=1 -w.) W.)T(wr wt-1).
(75)
For term (a), (we - w., v.((w))). by using that ff(w) = A. - w.) pl p(112=11 ||w)))es we can
bound it as
(W² W.: ([(w))
-we -w.) A. (w: w.) + p(11uxx) - (1/,,/)(())))) (1 w. we)
= (w: -w,) [ (A. + (1ew [|w= (w:+ w.) + of
(112,11 | 2)) (1/ezzll + 1|w. II).
2
(76)
On the other hand, for term (b). [/=]( we get that
[V ||A, (w: w.) - p(l1 - | I1 1
(77)
< 2( w.) A w.) + 20² (I|u,1l || - [I (1w 11.
By combining 75 776). and 777). we can bound the distance term as
| w. 2 | w.
2m(1 + 8)ww w. vf(wx)) ff
+ +(8² + 23) We w1-1 -2n3(w: 11 ff(()))) 28 (1 wa) (wr - wt-1)
S ||++ - ww.12
2n(11 + () )w.)
w.) (A. + ? ((lleell -1- (I)x w.))
(78)
-pn(1 + ([w. |||--|ia ||w,
(1)(((((1)))) + +1|w-ll)
+ + w.) TA² A2(w: w.) + 2p² (1/wall - [[wel)) (1we,11
+ (B3 + 2/3]| we - w 2n, 14-1, (wx)) + (w:-1 w.) Tw - w;-1).
Now let us bound the terms on the last line of (78). For the second to the last term, it is equal to
2n w1-1, V (w,))
(79)
= 3 - 11 V f(w)-1)) - 2m w1-1, Vf(wx)) - vf(w,-1)).
On the other hand, the last term of (78) is equal to 2.(w; - w.) (w.- w)-1) = 2,,n - W.. Vf(w,-1)) + (w:-1 - Wx, Wh-1 - W2-2)-
(80)
By Lemma 12 for all t, we have that
t-2 (w:-1 W.y W4-1 - we S -crrl/u u/ 2/22 + 1)
gr 2-2 (ds + Gs + 9a). (81)
8=1
Therefore, by combining 779 (0). and 81 we have that
(8² + +288) Wt
11-11/ 3 w1-1, f(r))) + 18(w,-1-ws (T)T(uu [ww; - w1-1)
I (8² + 2,3[[ur - -w,-112 2n w. (1 - v)(w()) 2c,, [| - w2-211
1-2
+ 3m
Σ 31-2- + g.).
s=1
(82)
27

---

Under review as a conference paper at ICLR 2021
Combining 788 and (22) leads to the following,
||00+1 - w. 2 2 ||u w. 112 - 21y(1 + 3)((w; w.) ( (A. + 2 [[1well - (Iww=l))a)(w: w.))
pm + ()w.ll - 1| (11u0, + ||w.11)
+ (2 -w.)" A3 w.) 2p² (1|wall - -|ooeell |
+ (B² +.33|| 1/ - w (w Wa, Vf(w=-1) [[((w)))
t-2
2ew3811wr -
-0:---111111 2112 + 2n
Σ
go-2- 2- (ds - -e + g.).
(83)
Let us now bound the terms on the second to the last line 83 above,
(0² 23 we w--1ll² (n wx, Vf(wi-1) (f())).
(84)
First, note that | < A|2 + 2pl|w/||- So we know that ʃ is I= ||ll2 + 2p smooth on {w ||w||| S R}. Second, denote
(85)
we can bound 1|2, wz-1 /|| as
2-2 s > +
|/w0 W 11 = -
Vf(c))
Σ
(w.)))
==0
==0
: 17 V (w + 2-
1-2
w 11-11; 1| = || - ( 2| s [V 2n²1|
Σ
-
1
v (w,)]l
= 277 (1 | |
(86)
Using the results, we can bound (84) as
(g² + w. - 1/-1112 2113(w4-11 - w., V (w(--) - v)(w)))
22 2| 13
+ 28
2n/ BL w. w- [w: + +||+-21|)
199((v/.111-,,3++/////////1/1111 (1 w.11? ||
287²(88 23) 1| - 17 n 1)12
+ + 21
(87)
Note that
[V = =IAA, -w.) - p[[w..1 - || - 10 101t0--11)20x-111 1112
(88)
$ 2( - ww+) TA
A3 (w,-1 - -w-) + 2p² (I|wall - ||w)- 110,-1112.
Denote
C3 = (2 + 4,3 + LB).
(89)
By 87 88
we have that
(5² + 2 - w,-1l 1|2 -nn - w., vf(w,-1 - vf(w;)).
< 2 w.)] T. A3(we-1 -w. + 2np" [1w:.|1 - -| 11 I - -w=ll?
+ =
(90)
28

---

Under review as a conference paper at ICLR 2021
Let us summarize the results far, by (83) and (90) we have that
| w.ll2
$ ||u, -w,12 22n(1 + ())((w))))))) (A, 2 [(1well //,,,/1)
(1xa w.))
-pn(1 + (1)(1l - -11wal
() + 11ww-1)
+ =2((2( - w.) (wr - w.) + 2p² (1)w, - |/ ( (1wol11))
2n - w,) A2( 1011-11 w.) + 2gp²cp222 20002(111)) (Ilwall |Iwe- 11;,, + 22) [ w.
1-2
+ rfc - 20xx )| | 2| + 2m/32
8t gt-2 2- (dg + cs + gs),
==1
(91)
where we also used that W4-1 - W1-2 = = We can rewrite the inequality above further as
|| w.ll
$ 5ww, w.) (La 21(11 + B)A.
I+ 14. 2npl|wal1
"1 A.) np(1 + (1 - -1 () (we w.)
no(1 + () - |1wxl1) (11
1 + || 2 (11wa1 |I - -1[w;- 2 |w-- 1l?
20
+ 1 ww) (2cg ( 233 223211 (1a w.)
+ (cg 2c + 2n
8 2d + cx + gz),
(92)
where we used that -mp(1 + B)( - ||well)² (1/we) [[(1 satisfies
2nellwall) 14.
+ ([,,l)) I 0 for any 7 that
1+
(93)
2pR
as ||well & R for all t. Let simplify the inequality (92) further by writing it as
[e++1 w. 2
(a)
S (we- w.) ( 21)(1 + 3Ia
17
A.) - nn((1 + (1 - (a (we w.)
1+
+ 722 (wi-1 -w)) T (2cg + 23 LIa + 2cpp² R² la) w.) + n7² (co - 20 (ew)llas 21
1-2
+ +2
Σ
gr 2- (ds + +e. g.))
am1
(8)
p||wall - ()] [lu w+ll?
< (1 - 711 + [plw|| || - ((7
+ /2 [w: (w:-1 10-1--.)) (2c 2. LIa + 2cpp² R² (a) w-) + 2 - 2c =
1-2
+ 2n
Σ gr-2 2-8 (d, c + g.).
1=1
(94)
where (a) is because that [|w.,||||wx-- 11) 1|2 < 11..-wt-118100-- 11255 ||w. - - wt-1 1 22
||w||| < R for all i, while (b) is by another constraint of n,
1 1 3
? 5 4 4| 1
(95)
so that 2na.(Ia A.) = InA. = 3 p p/u.. //
29

---

Under review as a conference paper at ICLR 2021
Lemma 14. Fix some numbers co, c1 0. Denote w -'=00 B. Following the notations and
assumptions used in Lemma 12 and Lemma 13 If satisfies: (1) 17 S 2nall A. 2 (2)
Co
< (11A. for
7 S + A.IA, (3) S pga Lo nt (4) r I 4pr R2 and (5) I L 201 1 222)22) 122)
o all i, then we have that for all I,
p ||w - w.l12 2 (1- 10-171 17(1 + 3) [plluelll - -(7 -ry- p/w.||
-3 [1) - w.11 12 + 17,300 /acolll0e-- 11: w-ll
2
1-2
+ 21331 (11A-l + pl)
Σ
8r 81-2-01 3--1/2s -w-ll
==0
2-2
3m
3--2-- (ws w.)
T. (A. (1wwall w- - 1| (1xx1) Ta) w.).
Proof. From Lemma 13 we have that
||0+11 - ww.12
$ (1 - (1-7(1= + w11p - (7 pl|wa|l - 1] -w.11
2
+ (1r1 ww) (2cg + + Lla 2c0p² 18 wa) -w.) + (c 2cw 2|1
1-2
+ 2n
gr g1-2-8 (dg + 6s + gx),
(0)
(1 - 711 + ()) [pl[wr]| - -( pllw|1 -)) 1| w-1l + n,coolue-1 - w.112 + =/(cc - 20w))l
5
2-2
+ 2m18
Σ 8=1
g 2- $(dg + e, + gg));
(6)
I (1 711 + 8) [pllwell - (7 pllwall - |1:ce w. + 31Bcoller- -w.l?
1-2
+ 2n22 2c ) w
2-2 Σ 30- 95-2-e(w - w.) + p² - w+)
1-2
+ 3m
Σ g 2- 2- (dg + Es + gz),
(96)
where (a) is by a constraint of n so that ((2co||Axl) + 2,3 + 2cpp2 S co and (b) is due to the following, denote w. := >' B, we have that
gr- Σ
| 2
8 +fwx))
Vf(w.)11
==0 w/
$ 8 (w/
[Vf(w))113
(97)
w/
==0
$ 23 3
g 105--10 (W p² RR w.)).
where the first inequality of (97) is due to Jensen's 's inequality and the second inequality of (97 is
due to the following upper- bound of the gradient norm, [W,]] [A, w.) -p( w__
[|.,,]]] [|w 1 < 2(w. w.) A2 (w, w.) 2p [[.]] [w 1) [|,, 2(w, w. 1 (w.
30

---

Under review as a conference paper at ICLR 2021
w+) + 2pp|| ww= -wal? R². By the definitions of d,, Ca. we further have that
|100+1 - wa112 5(1 - (1 + [plor) [ell - -(7 - p||wa|| || - ? []] =w.12 + 1nScollue=2-- - wall?
2
21188
31-2-a 2- (w,, -wa) - P
/ [(1well -|uclll))))))) - -wa)
2-2
+ 2m
81-2 20-2-8(1) -(W' -w.) (n((2 + (cg 2o 2A w..)
1-2
+ 2nppp RR 32
2CB )0w) Σ 81-2-01| 2/2,, w=l1
W
1-2
- -182pp p _
3r-2 2- =(1u,,1 - ||0,, (1 + ||w5||| - -41ppm 1/10s 12)
==1
+ >/{cc 20 2 (11 1/2 + (RR))1100 - w.l1?
<(1 (1 + (3) [pl |w2|| || - -(7 p||wa||
|| - ))) |lu1 wr.11 + 300olllu--1--- - w
2
1-2
2n182
Σ
gr-2 2- -w-, -w.) -(A.
l (11wcl1 -11wos1) w.)
2
t-2 Σ
+ Bn
8t-2-"(ws - -w,) "AA + pRIa)(ws w.)
1-2
m13pp p _
gr-2 (11es=1 - | (1 + ||wa||| - -npppw || 1w 1/)) 12)
1=1
+ (cB 22 (1| 12 + 0² RR))1(w0 - w.l1?
(98)
where the last inequality is due to (1): B² (2 + (eg 20 2 3 20 (20 + BB 2) A) 3 2r1 A., as ca - 20 S L and that 1) S 3(22, + LBW? "I and (2) that 2n p² R2 3 (cg 2cw) S 2n d² Re L S 2np R, 1) S P3RLWG
To continue, let us bound the last two terms (98). For the second to the last term, by using that ||l/|| < R for all t and that r) S R. we have that (I/w..) + ||wall - 4npdw/1w:=1l)) 2
||w=ll Therefore, we have that the second to last term on (98) is non-positive, namely, 4mp ww, |1 ?)
-m82p p P.
2 8 20-2~x(1)) -[ (atuu,llllua 1,1l) [I[w=|++
0. For the last term on 98
01 [[))))+
by using that 17 S L, (1I (1.., we have that 17 (c3 2c,, 125 2 112 + p² R²)
w. w S 2222L - [I 113 + p² R2) [ - 112 < 2n c2 (1) + pR) w|ll - w.
Combining the above results, we have that
S (1- 17(1 + [p]) - -(y -1-- 1) p/w. 7 11) Iw2 - -w w1 + +n,330ll (ietollwe1111 - wa
||w21 - w.112 11.1--
2
1-2
+ 21 AI + pf))
Σ
8r 2
2-
|w w=l
0=0
1-2
- -2
31-2-8 (w. T.)T(A - P (11wall - 1| (w) (ws - -w.).
2
1=1
(99)
31

---

Under review as a conference paper at ICLR 2021
The following lemma will be used for getting the iteration complexity from Lemma 14 Lemma 15. For a non-negative sequence {ve)12 1220 suppose that it satisfies
Vt+1 S pit + quh-1 + r, + x3 3 2- Yu + 28 -+1 for all 1 2 T
(100)
for non-negative numbers p, 2,, 0 and 3 E [0, 1), where we denote
Dt : g ys.
(101)
Fix some numbers & 1) and th O. Define 0 -pt V +4
Suppose that
/2 +()+))
and 3 5 p + p2
+ 4(g + σ)
B r+ + +
2
2
then have that for all t 2 T,
V1 S ( p2 - 4(g + Ø) )TT Cr,B+
(102)
where Gr is an upper bound that satisfies, for any S T,
+ 0y:-1 Φūt 2 + Bubz S Cr,
(103)
Proof. For a non neg-negetive sequence (uc1e20. suppose that it satisfies
We+1 S pyt + Q + rB + x/ Σ gl-2 2- Ys + 2 for all t 126 T,
(104)
for non-negative numbers p,q. 2, and A E [0, where we denote
Dt : Σ 8 ys
(105)
0=0
Ve+1 + Byr + 1 + 222
(a)
t-2 S (p + f) + 43 + r r3g,- 2 + 07. + x3 Σ
ge- 31-2-8 2. + +68 + 1)
8=
1-2
( (p O)8 + (q + の) + 63) + x3 Σ
8r 2-8
4/ + (wb + 1)2
8=7
(q Φ)
$ + (v) +
p 0 y 1) + 8(r + + +) + (w/ + 1)28+-+++
(
8 (p + (y) + 0yt-1) + 3(r - の + x) + (w3 + 1) r+1
(
2 (p + (2) + 01h-1 + 0b. 2ズ < (p + 0)2 (v:-1 + 0y,- + -T1-3 02 s
(p 0)¹ - C.
(106)
where (a) is due to the dynamics
100 (b) is because 7t-1 = 9 + 3g, (c) is by.
+ Φ p 7 0
< 0
(107)
and (d) is by
9 < (p+ + 0)
1 4
and 3 < p + 0
(108)
r Φ +
32

---

Under review as a conference paper at ICLR 2021
Note that (07) holds if.
0 p +
12 + 4(1 + Φ)
(109)
2
Let us choose the minimal 0 -pt V p2 + +) completes the proof.
So we have p + 0 p+ V p2 +-((+)))))
which
Lemma 16. Assume that for all 4, | 1 R for some number R. Fix the numbers co, C1 > 0
in Lemma 14 so that C1 10 Suppose that the step size of satisfies (1) 1 S
20p A. 1222 +220-t2 (2) 1) +L 2111A11' (3) n S Lut 2 (4) 1 Ap" (5)
co3
C1 [[I.AI+P])
7 S L9PW," 22914.2(11A.11 (1.lAA11+++""11 (6) S
1+3 2
1+3 and ( S TI for all t, where cg = +43+ LB).
L == ||Al|2 | Cw := 1-3: Cwe == (1+cc))) )² and wl-2 == >>= 8. Furthermore, sup-
20
pose that the momentum parameter 3 satisfies 3 E min 10
π [1 - 17 + 1)6)),1111p + B)6 - 0.13.
Fix numbers 6, so that 1/2 [ol|w= 7) > 8 > 0 and
2 8' > 0. Assume that [|w,,] ll is non-
20
decreasing. If pllwelll 2 7 2 (ollu.11 7) + ā and pl|wall
2 7 8' for some L 2 l., then we have
that
[w w. 12 S (1 11 + 3)6 1 17(1 + 3)6
27,3co
t-t- C
where C3,t. is number that satisfies for any < t,. ||:0 w.ll 112 + 2 |11 - w.ll2 + m8co Ex- f- - w.1l2 2| + max ,20n E gr.-1
1 (3 - 2 211ws ||ac w..13] S C32
Proof.
From Lemma 14 we have that
|| - w.112 < (1 - 1/(1 + [elllleell - (7 p|wual -/lwal1-711 ()) |lu. -w.12 12 + 11,30 |w-- w-ll?
2
1-2
+ 2m3c1(11AA1 + pll)
Σ 3r-2-s -l w.ll?
1-2
3m
8t 2 (ws - w.) T(A -2
1 (1Iwal1 vaail-Illve -11ussl) - w.).
Using that for all / 2 4, || || || 2 7- - -/2 [ellu= - -7) + 5, we have that
[Wz41 - w.1l < (1 - 17(1 + 3)6) |/,, w. 1| +
- -w.1" w.
1-2
+ 2n (I/ + +pR)
Σ gl- 2- 2 w..11
s=0
1-2
- 2n132 Σ 1=1
31-2 (w,- -w,) (A. - (1lwal) -11 (w. - w.)
= =(1 -1- m1 3)6)
|wl 112 + 1/ =1,11
(110)
1-2
+ 21/3c1 (||l|| + pR)
Σ 3/-2 1-1--1(w, -wa11
s=0
t-2 Σ
31-2- =(w, Te) P (Ilw.] || - -1[wall) [a) (w. -w,)
4,1
32
Σ
8 2 -w, - w.) (A. P (I|wall - [I) (w - w.).
(w,-
2
We bound the second to last term of (10) as follows. Note that for 2 t., we have that p|lw,|l 2 7 8' by the assumption that ||wr]]| is non-decreasing. Therefore, once |||wa|l exceeds any level
33

---

Under review as a conference paper at ICLR 2021
blow 7 8', it will not fall below r 8'. So have that
Ax 2 (1]wa]) 2
|wsll) la =
(a)
A.
P Ellwal1
1|
7
7-88
2 la
8'
(-y + p||20,1114
P
||
IL +
8' Ia
(111)
2
(c) 8'
Ia
2
where (a) uses that pllwall 2 8' for some number 8' > 0, (b) uses the fact that A, 2 (-7 + p|| Il, and (c) uses the fact that pl[ 2 Using the result, we can bound the second to the
last term of TT0p as
1-2
2m/3
g 2- 2w- - w - 2 (1|wall - (lw - w.)
s=/.
(112)
n33 8
81-2-51|ws I|w,, -0,1-
w=1l?
s=t.
Now let us switch to the last term of 110).. Using the fact that A, 2 (-7 + pllwall) and that
p||w,||| 2 y by the characterization of the optimizer [|.,,] |l. we have that
A. - ( 2 (1|w.ll - Ims = 2
(1lw.,1 I| + || Ia 7 = (2 ||wsll (/111ssll - 2)x (113)
So we can bound the last term
2m8
g 3i-2-e(w, -w+) ( - L ( - /|/w La) ww)
2
(114)
< 2nnge-tott
8r 33.-1-1(us)) "(w, w.) (2
L
Ila (opal)((a Ia(ws w.) = 2:133-1-1 Dia:
2
where we denote Der Et- -1 8r. 11- -1 ((w, (T) - =b((wsl)) Lolw, w.). Combining 110 (12). (14), we have that
|| w.1l2 < (1 1/(1 + B)0) l/u, w. 1| + 113c0 (accoollu: fl: -wa12
1-2
+ 27,3cr (||ll, +RR Σ
8 3 *1 [w, wa112
(115)
1-2
+ nn 8'
Σ
gt-
w.112 + 2n - D
Now we are ready to use Lemma 15
Set p, q, r, in Lemma 15 as follows.
p 17(1 + +,3)8
= ni3co
2n.]I + pR)c1
x 1)38'
z Dt. 1r 2 0).
Φ = q = 113co
1 10.
34

---

Under review as a conference paper at ICLR 2021
have that
x [1-n(1 (1 +,/8+ v(1 711 + 3)8)2 + 4(22 t-t, cp.
1
||w w.ll 1
2
(116)
< (1 (1-1(1 + 8)8 + 1- 1-v(1 11(1 B)8
27,500
1-t.
CB.
where that a+t / 1444b/02
a+a(1+ 4
a for number b that satisfy 4b/a² >
2t +tv and B <
r+ト+z -1. Now let us check the conditions of Lemma 15 to see if S
pa +4(+t))
1. #
For the first condition, B(r + 0 x)
pt (g+t Φ is equivalent
2
to ((2 + pfl)e + nšco + n)88) - pt ptv n30, which can be satisfied by en 20
2
p+ +(0(()))
en C1 S 100 A- and 8 <
leading to an upper bound of 3, which is B S 11
2
Using the expression of p. q. Φ, and v, suffices to have that 10 (1 - 17(1 + 3)5). On the other hand, for the second condition, 8 v pt 1P suffices to have that
3. by using the expression of p. 9. o, and b,
7 + 3)6 0.1.
F.2 PROOF OF THEOREM 3
Proof. Let 6 cs (pllw. || - 7) for some number 6s < 0.5. Denote 668 some number 2o 0. By Lemma T6 we have that
converge
1-2 for
||w, -. 112 s (1 711 3)8 1- 71(1 (3)
t-t, cp,c.
(117)
< (1 - () + B BG (omoverg))) 1-1. C3
where Ca,t, is number that satisfies for any t t., l|0, 1 2 + 2 m8c0 E gt-2-"llw,, 1 w. 2 m0, 320m -:17 Note that obtain trivial upper-bound Cg.t for any follows. Using that || w. < 4R²
7 1)6 |1:-1 w.11 +
-1 gt. (3 2 w. II) I|u, 1) S CB.t.-
and that co + āoō and that + (pl/ 7). we can upper-bound the term as
1- n1(1 (pllwcl - nB ->) 1
2npocs (pl|w> 7))
1 ge
1-
C3 4R² (1
1 1 -100 max (0,7)
1 1-
< 4 + n)8Cp)
= Cg.
(118)
where we define Cp := (plc: 1-7) + I-B (cocs(pllu.11--) ->) + 10 maxxx(0 7)) and ōg == nBC 1-1(1+8)cd (1l(w=11->))
Now denote connerge := 1 1-2ncs (enes(lllww. (pllw-l1-7)
27g
We have that
[(Wr.++) f(w.) (a) ||Al| + 2pR
|| - w-11
(119)
(6) A|ll + 2pR
Eg exp ( --ncs(pllwwll - (1 + (onvergg)))
2
where (a) uses the [|lll2 smooesms of function f(-) in the region of {w ||w]|| S R), and (b) uses (117), ( 1118) and that 8 = es (pllw.ll 77). So that the number of iterations in the linear convergence regime is at most
7cs (pl(pl 7) + Beconverge) log (IAA + 2pR)aa )
t <<
(120)
2
35

---

Under review as a conference paper at ICLR 2021
Lastly, let check if the step size 7) satisfies the constraints of Lemma 16
Recall the notations that
28 Cw T-B. Cw (1+ (1 + cw J2. cg
and L := ||All2 + +pR.. Lemma 16
has the following constraints, (1) S 2c A. +2 (2) v 8122. -B/(1-)))AA1 -.
0o.
L [IA.] +
(3) 17 S D (4) S ApenIt (5) rj
11) (6) ll 2pHt' and (7)
1+8
7 S 1+8 T1 For the constraints of (I), using co Egg and that ó = cslplwull 7), it can be rewritten as
Oocs p u. -7)
S
(121)
2(2 + L) [A 12 p² p² + 23L
dفع For the constraints of (2), using C1 S 40 [0[lA-II+pR) and that 6 = cs (pl (ol -7) 7). it can be rewritten
Egcs (pll w. 7)
7 S 403(1IA.112 + p A, (1) (26 + LB/(11 3))
(122)
The constraints of (3) can be written as, using C1 S 301 8g8 Htrlj and that ò (pl[ww>]) -7).
Euco (1) w. || - 7)
S
(123)
40pR(IIA.1 pR) B3
The constraints of (5) translates into, using c
4011| 2nd HD and that 5 cs collllu.11 -7).
Zocs (pllw. || - 7) n S LB /2) (1 - 3)
(124)
Considering all the above constraints, suffices to let r satisfies
E9c8 (pllw>ll
17 S min
(125)
4(11A,1| + CwpR) Cp(1IAu + pR) + ||A.l| + pl) + 23L
where C3 == max (43 + 2L,
4 8032 48w).
1-8
Note that the constraint of 7) satisfies (pllww1 - -7) S c6 < 1 Using this inequality, we
can simplify the constraint regarding the parameter 3 in Lemma 16 which leads to 3 E [0, 0.65). Consequently, we can simplify and upper bound the constants C... C3 and Cg. which leads to the theorem statement.
Thus, we have completed the proof.
G
MORE DISCUSSIONS
Recall the discussion the main text, we showed that the iterate 114+ generated by HB satisfies
(we+1. u,) = (1 + 17,,) u,) + 3((w,, U²) - (w.-1. u4)),
(126)
which is in the form of dynamics shown in Lemma I Hence, one might be able to show that with the use of the momentum, the growth rate of the projection on the eigenvector (i.e. [( u,)l faster as the momentum parameter 3 increases. Furthermore, the top eigenvector projection (WE+1, Mi is the one that grows at the fastest rate. As the result, after normalization (i.e. we [
the normalized solution will converge to the top eigenvector after few iterations T.
However, we know that power iteration or Lanczos method are the standard, specialized, of the-art algorithms for computing the top cigenvector. It is true that HB is outperformed by these methods. But in the next subsection, we will show an implication of the acceleration result, com- pared to vanilla gradient descent, of top eigenvector computations.
36

---

Under review as a conference paper at ICLR 2021
P..-0-0-0
(a) 1 10
(b) 5 10-3
(c) 10-3
(d) 5X 10
Figure 3: Distance the top leading eigenvector iteration when applying HB for solving min... 3 w Aw. The acceleration effect due to the use of momentum more evident for small vj. Here we construct the matrix ABBB' E IP 10 with each entry of B E R 10x10 sampled from NN
G.1 IMPLICATION: ESCAPE SADDLE POINTS FASTER
Recent years there is growing trend in designing algorithms quickly find second order sta- tionary point in non non-convex optimization (e.g. Carmon et al. (2018);
Agarwal et al. (2017); Allen-
Zhu & Li (2018); Xu al. (2018); Ge et al. (2015): Levy (2066) Fang al. (2019); Jin et al.
[217]] 2018 2019): Daneshmand et al. (2018): Staib et al. D Wang et al. (0200) The com- mon assumptions are that the gradient is L-piscchitz: [V
ff(ii S A| y and that the Hessian is p-Lipschitz: || f(x) V f()il S e||æz wll. while some related works make some additional assumptions. All the related works agree that if the current iterate wto is in the region of strict saddle points, defined as that the gradient is small (i.e. f S cg but the least eigenvalue of the Hessian is strictly negative (i.e. Amiul (V2 (wx,)) I -6, Ta), then the eigenvector corresponding the least eigenvalue Amin ( (V2o(w)))) )) is the escape direction. To (Vf(wt)). Who+e Wt,) + (woo+ - w.,,) Vv ((wt)) - -oo)) + +gllueote - Wto 11. So wtott Wh, is in the direction
elaborate, by p-Lipschitzness of the Hessian, f f(Woo++) f(wto)
exhibit negative curvature
of the bottom eigenvector of 2 fwt,), then (Woo+t ) V f (wto) w),) S -c'E for some d' > O. Together with the fact that the gradient small when the region of saddle points and the use of sufficiently small step size can guarantee that the function value decreases sufficiently (w.e.(()t f(w:,) S -ce for some e >> 0). Therefore, many related works design fast algorithms by leveraging the problem structure to quickly compute the bottom eigenvector of the Hessian (see e.g. Carmon et al. (2018); Agarwal et al. (007);; Allen Zhu & Li (0018); Xu et al. (018
An interesting question is as follows "If the Heavy Ball algorithm is used directly to solve a non- convex optimization problem, it escape possible saddle points faster than gradient descent?" Before answering the question, let us first conduct an experiment to see if the Heavy Ball algorithm accelerate the process of escaping saddle points. Specifically, we consider problem that was consider by (Staib et al. (2019):; Reddi et al. (2018); Wang et al. (2020) for the challenge of escaping saddle points. The problem
min f(w) = EE (Ew" Hw + x. w ([
(127)
1
with H =
0.1 where x; NN0 diag((0.1, 0.000))))))))) and the small variance in the second
0
component will provide smaller component of gradient in the escape direction. At the origin, we have that the gradient is small but that the Hessian exhibits negative curvature. For this problem, Wang et al. (020) observe that SGD with momentum escapes the saddle points faster but they make strong assumptions in their analysis. We instead consider the Heavy Ball algorithm (i.e. Algo- rithm [ the deterministic version of SGD with momentum). Figure 4 shows the result and we see that the higher the momentum parameter 3, the faster the process of escaping the saddle points.
We are going to argue that the observation can be explained by our theoretical result that the Heavy Ball algorithm computes the top eigenvector faster than gradient descent. Let us denote h(w)= := >i [x] [10)- We can rewrite the objective 127b as f(w) = 1 ww Hu h(w). Then,
37

---

Under review as a conference paper at ICLR 2021
the Heavy Ball algorithm generates the iterate according to
7
wt B(wre - ---1)- (h(w)..
w++1
0
(128)
By setting 7) 1, we have that the top eigenvector of A u1 c2. which is the es- cape direction. Now observe the similarity (if one ignores the term v/Vh(wz) between the up- It suggests that a similar analysis could be used for explaining the es- In Appendix G.2 we provide detailed analysis of the observation. How- 127p has a fixed Hessian and is a synthetic objective function. For general smooth non-conver optimization, can we have similar explanation? Consider applying the Heavy Ball algorithm to ming [(w) and suppose that at time lo. the iterate is in the re- gion of strict saddle points. We have that W141+to - Wto = (la 1 (wwa) - wro) + (( - wio) - (Wi+to-1 - wio)) + n ( f(wro) (wi+do wto) - Vf(we+to) )
date (128) and
19
cape process.
ever, problem
deviation
By setting 7) S t with L being the smoothness constant of the problem, we have that the top eigenvector (la - 1/ f) is the eigenvector that corresponds to the smallest eigenvalue of the Hessian V fw,,,, which is an escape direction. Therefore, if the deviation term can be controlled, the dynamics of the Heavy Ball algorithm can be viewed as implicitly and approximately comput- ing the eigenvector, and hence should expect that higher val- ues of momentum parameter accelerate the process. To control (Ff((w,)(wtta - wt,) f (WW+tt)) one might want exploit the p-Lipschitzness assumption of the Hessian and might need further mild assumptions, as [uu al.] (2017) provide examples showing that gradient descent can take exponential time T (exp((d) to escape saddles points. Previous work of Wang et al. (2020) makes strong assumptions to avoid the result of exponential time escape. On the other hand, Lee et al. (2019) show that first order methods can escape strict saddle points almost surely. So we conjecture that under additional mild conditions, if gradient descent can escape in polynomial time, then using Heavy Ball momentum (3 o 0) will accelerate the process of escape. We leave it as future work.
.000
3.5
Figure 4: Solving 127 (with 10) by the Heavy Ball al- gorithm with different (3.
G.2 ESCAPING SADDLE POINTS 127
Recall the objective is
min f(w) EE (#w) Hw + x. w |[
(129)
with
(130)
0.1
where H; (O, (0.1, 0.001))) and the small variance in the second component will provide smaller component of gradient in the escape direction. At the origin, we have that the gradient is small but that the Hessian exhibits negative curvature. Let denote h(w) := 1/2 Σi= (z, w + [|]]]1]). We can rewrite the objective as f(w) := = H h(w). Then, the Heavy Ball algorithm generates the iterate according to
Wi+1 We nHw, 3(w: w1-1) Vh(we)
1 17
wi + 3(we wi-1) Vh(w))
(131)
0 1 1+0.1m
Aw, + B(w:
Wi-1 - -/V/w(..)
1 -
where the matrix A defined as A =
By setting 7) S 1, we have that the which is the escape direction. In the following, let us
0
1 0.1
top eigen-vector of A is U1 = =e =
38

---

Under review as a conference paper at ICLR 2021
denote U2 = E1
and denote ā = - n -im Li. Since || = (2i-) (wiPP) and that
0
a aw 0w;
p/u,| p--1 1-110 0 w.l they
plucy 10 2 we have that
Vh(w) = E + 10abs(w)* w,
(132)
where denotes element-wise product and abs(.) denotes the absolution value of its argument in the element-wise way.
By initialization wi = w-1 = 0, we have that (w) u1) )11= = (wI u1) = (w) u2) (wIIu2) = 0 and the dynamics
W *+1 U2 (1 n)w! u2 3(w, u2 w(_1 17u Vh(we)
(133)
T #1+10 11 (1 + 10
yum un + B(w, un 11) - m vh(w+),
while also have the initial condition that
0
w U2 = nun Vh(wo) = -11 Vh(
= n = -1
0
(134)
_ "1 = 1 Vh((n) = 1 Vh((
0
=
uuu _ [2]
That is,
81 = -/..
(135)
Using 132p. we can rewrite 133) as
W411 U2 (1 17) n) u2 + B(w u2 u2)) n (0n(w((+12) u2)
11+1 (1 + 10
T
17 wu in + B(w, in w.-uu pp 10n(w,,+1u))
(136)
Note that we have that
fww) Hw Vh(w)= w I 10abs(w)*
1 10 [1]]
0
(137)
0.1 + 10/w[2]
w
So the stationary points of the objective function satisfy
(1 + [0|w [w + =[1| =
(138)
(-0.1 + 10/w + = =
To check if the stationary point is a local minimum, we can use the expression of the Hessian
V H Vh)(w)
1 + 90 [1]
(139)
0.1 + 90 w [2]
Therefore, the Hessian at a stationary point is positive semi-definite as long as [w[2]| can be guaranteed by some realizations of F 2 according to (138).
1 which
900
Now let us illustrate why higher momentum 3 leads to the faster convergence in a high level way, From (188). we see that one can specify the stationary point by determining æ[1] and x[2). Fur- 1 the iterate enters the locally strongly convex and smooth region, for which the local convergence of the Heavy Ball algorithm is known (Ghadimi et al. (2015).. W.l.o.g, let us assume that x[2) is negative. From [144 we have that wi U1 > when 2 is negative. Morcover, from 136). if, before the iterate satisfies [w: [2] > 300 we have that To (w, un) 10(w, u,) 9 2 O. then the contribution of the projection on the escape direction (i.e. w(+1n)) u1) due the momentum term 3(w, u wI_nr)
thermore, from (139), once the iterate w, satisfies |2, 500
is positive, which also implies that the larger (,, the larger the contribution and hence the faster the growing rate of [w.22]. Now let check the condition, 10 (w) u1) 10(w," un) x[2] before lw: [2]s > 900 sufficient condition is that (1 (w, u1) - x[2] 0, which we immediately see that it is true given that Z[2] negative and that wi un > and that the magnitude of wT u, is increasing. A similar reasoning can be conducted the other coordinate w [1] == 1/41
39

---

Under review as a conference paper at ICLR 2021
H EMPIRICAL RESULTS
H.1
PHASE RETRIEVAL
10
dillance the true model W.
objeciree velue
0.4
10"12
HB+(50)
+BH(100)
-H8-67-0.3)
0.2
+8-(1-23)
......HB HH--(7-055
+B+(1-25)
H8-(7-0.7)
+B+(1-0.7)
(8.(7-0.9)
+B.(F-00.)
(HB+ (1 1.0
HHBr 100-3-10-0000 0.0
10
1000
2000
3000
5000
1000
2000
3000
4000
5000
Beration
itoration
Figure 5: Performance of gradient descent with Heavy Ball momentum with different values of 0.9} for solving the phase retrieval problem (1. The case of
{0, 0.3, 0.5, 0.9, 1.0 = O corresponds to the standard gradient descent. Left: we plot the convergence to the true model w... defined as min( (an(/w w+ llll ||wo + w*ll). []). as the global sign of the objective equation iis unrecoverable. Right: we plot the objective value ( vs. iteration t.
10
10
sizze of thee perpandiculer compoment
5100 of sgra componet
50
10
10 10
HB+((M)
-0.30
[BH0--077
10
HB4(0-095
+B+10
10"15
1000
2000
3000
4000
8000
1000
2000
3000
4000
5000
(a) [w!|| vs.
(b) || vs.
Figure 6: Performance HB with different {0, 0.3, 0.5,0.5,.7770... + 0.9} phase retrieval. (a): The size projection we on w. over iterations (i.c. |w] vs. t), which non-decreasing throughout the iterations until reaching an optimal point (here, || = 1). (b): size of the perpendicular component over iterations (i.c. ||w|'|
f), which is incrcasing in the beginning and then it is decreasing towards zero after some point. We see that the slope of the curve corresponding larger momentum parameter is steeper than that of smaller one, which confirms Lemma and Lemma
All the lines are obtained by initializing the iterate at the same point wh ~ (O, and using the same step size 7 = 5 10-4 Here we set with dimension = 10 and number samples n = 200. We see that the higher the momentum parameter 8, the faster the algorithm enters the linear convergence regime. For the line represented by HB+(3 = 1.0 + 0.9), it means switching to the use of 3 0.9 from 8 = after some iterations. Below, Algorithm and Algorithm 4 show equivalent presentations of this
and sample
(0
40

---

Under review as a conference paper at ICLR 2021
practice. In experiment, for the ease of implementation, we let the criteria of the switch be 1 [(w))_/(w-) 2 0.5), i.c. if the relative change of objective value compared to the initial value has been increased to 50%.
f(wa)
Algorithm 3: Switching to
Required: step size 1) and momentum parameter E [0, 1).
we R and 3 = 1. 3: for L to do
2: Init:
4: Update iterate W = wt v/ ((m)) ) + B(u - v).
5:
Update auxiliary iterate u =
6:
Update auxiliary iterate We.
7:
If [ Criteria is met
8:
3 B.
9: u Wx+1
# (reset momentum)
10: end
11: end for
Al Algorithm 4: Switching 3 = to 1.
1: Required: step size and momentum parameter 3 E [0, 1).
2: Init: wo E R m--1 0a. 3 1.
3: for I = 0 to do
4: Update momentum m. := 8m V.(ww)).
5: Update iterate w++1 Wt: mm..
6: If Criteria met
7: 3 = B.
8: m, 0.
# (reset momentum)
9:
end
10:
end for
H.2 CUBIC-REGULARIZED PROBLEM
Figure 2 shows empirical results of solving the cubic-regularized problem by Heavy Ball with dif- ferent values momentum parameter B. Subfigure (a) shows that larger momentum parameter results in faster growth rate of |[y which confirms Lemma 2 and shows that it enters the benign region IB faster with larger B. Note that here we have that || [w. non-decreasing during the execution of the algorithm for wide range of 3 except very large / For 0.9, the norm starts decreasing only after arises above ||w, ||. Subfigure (b) show that higher also accelerates the linear convergence, one can see that the slope of line that corresponds to higher 33 steeper than that of the lower one (e.g. compared to 3 = 0), which verifies Theo- remB We also observe very interesting phenomenon: when 3 is set to very large value (e.g. 0.9 here), the pattern is intrinsically different from the smaller ones. The convergence is not monotone and its behavior (bump and overshoots when decreasing): furthermore, the norm of |/w]| generated by the high /3 is larger than ||w-||| the minimizer at some time during the execution of the algo- rithm, which is different from the behavior due using smaller values of / (i.e. non-decreasing of the norm until the convergence). Our theoretical results cannot explain the behavior of such high 3, such value of 3 exceeds the upper-threshold required by the theorem. An investigation and understanding of the observation might be needed in the future.
It suggests that the norm
Now let us switch describe the setup of the experiment. We first set step size n 0.01, dimension
d = 4, p = ||w,|| = ||Al]|2 = 1, = 0.2 and gap = 5 x 10-3, Then we set A = d ( + gap: (33; (444). where the entries Ag3 and 444 are sampled uniformly random in [-> + gap:
We draw 6 (A + p|[w.,] || [a) - where 0 ~ NO;0; Ta) and log, { is uniform on 1. 1. We
[w_ v and -(A + pl|.. (.. The procedure makes w, the global minimizer of set w. |
problem instance (A, b, p). Patterns shown on this figure exhibit for other random problem instances well.
41


Reviews:
[{"review_id": "kxBwE9pXUy", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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 studies the deterministic Heavy Ball (HB) method compared with vanilla gradient descent (GD) in nonconvex optimization.\nIn particular, they consider two optimization problems, i.e., phase retrieval and cubic-regularized problem, and try to show HB is better than GD, and the larger momentum parameter $\\beta$, the better benefit of HB.\n\nThey consider two stages for these two problems. The first stage is to find/fall into a benign region (strongly-convex region) and then the second stage can directly use previous HB results for strongly convex functions (i.e., linear convergence).\nThus the main part/contribution is to show how HB could perform better than GD in the first stage. In this paper, they show this by providing Theorem 1 and 2 for these two problems respectively.\nHowever, I have some questions/concerns regarding Theorem 1 and 2.\n\nFor Theorem 1 (phase retrieval):\n1a. They first analyze the HB using the population update (i.e., Eq (5)), then they consider Eq (11) for dealing with finite samples case. The author should show/prove that Eq (11) is the update form for finite case and also satisfies the corresponding assumption in Theorem 1.\n1b. Why the initial point $\\||w_0\\||$ is not equal to 1 in Theorem 1, i.e., sampling from the unit sphere? Since they assume that $\\||w_*\\||=1$.\n1c. They claim that HB is better than GD by a factor of $1+c_\\eta \\beta$ according to Theorem 1. But what’s the result for GD, is it $T_\\zeta \\lesssim\\log d$? It looks a bit strange as it does not depend on the step-size $\\eta$.\n\nFor Theorem 2 (cubic regularized)\n2a. In general, the value of step-size $\\eta$ varies for different algorithms. So only according to their Theorem 2, I am not convinced that HB is better than GD as the authors claimed since GD may choose different step-size due to nonexistence of momentum.\n2b. Beyond Theorem 2, I have a question regarding Figure 2b. Why there are oscillations for the last two curves in Figure 2b? \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "c6Fafg0rmJB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "The authors analysed the dynamics heavy ball momentum in non-convex optimization settings (namely the phase retrieval and the cubic-regularized problems). The results show that the algorithm leads to a faster convergence rate in comparison with gradient descent without inertial contributions. Although there are results in the context of convex optimization, the result in non-convex setting is novel and very interesting. \n\nIn the phase retrieval case, following an approach analogous to [Chen et al. (2018)] the authors show that the dynamics can be reduced to the study of the parallel and perpendicular components of the weights with respect to the ground truth. \nHowever in that case, the landscape is non-convex anymore since the number of samples is infinity and the spurious minima disappear (as the authors reported in the introduction [Davis et al., 2018; Soltanolkotabi, 2014; Sun et al., 2016; White et al., 2016]).\nIn order to analysed the case with a finite number of datapoints, the authors introduced perturbation terms in the dynamical equations and hypothesized that the perturbation is bounded by a constant c_n that the they ask to be smaller than zeta. \nMy main concerns on this part are the following : \n* is the landscape still convex under this constraint?\n* is there the possibility that for some regimes for which the hypothesis break and heavy ball momentum will behave poorly compared to gradient descent? In the paper it seems that it always speed up the performances, but this is not clear from the theorem. \n\nThe authors in thm.1 and 2, give a characterization of the speed up given by the momentum parameter beta. The authors should check whether the bound is strict in simulations, and verify numerically that in fact the speed is correctly captured by the theory. \n\n**Other comments :** \n\n* There is a change of notation between the one used for Fig.1 and the one reported in the appendix (d<-m, n<-m). Furthermore those details are important and should put forward in the caption. \n* The figures need larger fonts. It is almost impossible read them in the printed paper.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "U73oEMpFqv5", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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": "#########################\nSummary: \nThis paper studies heavy ball momentum in non-convex optimization. It has provided some theory to explain the good performance of heavy ball method in some type of nonconvex problems, i.e., the phase retrieval problem and cubic-regularized problem.\n\n#########################\nReasons for score: \nOverall, I vote for rejecting. Although this paper has some contribution to explain the superiority of heavy ball method over vanilla SGD, the problem has very special structure, which makes its not very much likely to be generalized to general problems and applications.  \n\n##########################\nPros: \n1. This paper has proven the superiority of heavy ball method in some cases by showing that heavy ball momentum helps the iterate to enter a benign region that contains a global optimal point faster. \n\n\n##########################\nCons: \n1. The considered problems have very special structures, i.e., the phase retrieval problem and cubic-regularized problem, which would prevent the generalization to a broad family of problems. Even though that the authors have tried to generalize it to solve the problem of top eigenvector computation and saddle point escape problem, they still focus on special subproblems of these two. \n\n2. In terms of writing, the authors did not give enough background of the considered phase retrieval problem and cubic-regularized problem. I do not feel that the ICLR community would be familiar with these two problems.\n\n##########################\nQuestions:\n1. Why are considered problem important on their own? And how can they be connected to problems that the ICLR community would be interested in?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "JDRN__TVRj0", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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 analyzes Polyak momentum in the deterministic case for two simple but important non-convex problems: phase retrieval and finding the cubic-regularized newton step. It is shown that in both cases the problems posses a “benign region” in which the objective “looks” a bit convex. In the phase retrieval case, assuming that the data is generated from a normal distribution, it is shown that having a non-zero momentum parameter in fact allows the momentum method to find the benign region faster, after which standard convex analysis can take over to find the optimal point.\n\nFor the cubic regularization problem, a similar result showing faster convergence to the benign region is shown. The key steps appear to be observing that in both instances, the benign region is essentially just asking for the norm of the iterate to reach sufficient magnitude. Then, a technical lemma (Lemma 1) and careful analysis of the gradients of the individual losses shows that the iterates increase in magnitude very quickly, with the momentum parameter accelerating the increase.\n\nOverall I think these are interesting results. I think the major weakness (as admitted by the authors) is that for the cubic-regularization problem, there is no guarantee that the iterates will in fact stay in the benign region once they have entered it. Although it seems plausible that such behavior is in fact guaranteed, this does somewhat weaken the theoretical impact. The other issue is that as far as I can see, these results improve by at most a constant factor of about 2 over the number of iterations required by ordinary gradient descent, which is not a huge amount. However, constants are important in practice, and many analyses of Polyak momentum in the non-convex setting actually get worse when there is momentum, so at least this is going in the right direction :)\n\nI think the cubic-regularization result seems the most promising for future development as it may have some application to generally showing faster a convergence on second-order-smooth non-convex problems.\n\nMinor nit:\nIn Lemma 1, what does “the effective dynamics satisfies...” mean? It sounds cool, but I don’t actually know what effective dynamics are. Maybe you could just say “a_t satisfies...”. Similarly for the other few places that effective dynamics shows up.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers the analysis of momentum for nonconvex problems. While this is a worthy direction, as some reviewers pointed out, the examples considered are rather specialized and one can argue they are mostly "convex-like". Therefore it is not clear that these results are generalizable and whether the analysis offers insights about how momentum helps (including faster escape of saddle in nonconvex regime, and faster convergence in the convex regime). In the current form, these results have limited scopes.

Decision: Reject