Heavy-ball Algorithms Always Escape Saddle Points

1 Introduction

We consider the smooth nonconvex optimization problem

where f is a differentiable closed function whose gradient is L-Lipschitz continuous (may be nonconvex). And more we assume f is C 2 over RN , that is, f is twice-differentiable and ∇2 f(x) is continuous. This paper is devoted to the study of two heavy-ball algorithms for minimizing f with random initializations. Specifically, we focus on whether these two algorithms escape the saddle points.

1.1 Heavy-ball Algorithms

We consider the Heavy-Ball Gradient Descent (HBGD) with random initializations x0 , x1 presented as

∗Corresponding Author.

where γ is the stepsize and β is the inertial parameter. If β = 0, the algorithm then reduces to the basic gradient descent. The heavy-ball method is also named as momentum method and has been widely used in different cases to accelerate the gradient descent iteration. Theoretically, it has been proved that HBGD enjoys better convergence factor than both the gradient and Nesterov's accelerated gradient method with linear convergence rates under the condition that the objective function is twice continuously differentiable, strongly convex and has Lipschitz continuous gradient. With the convex and smooth assumption on the objective function, the ergodic O(1/k) rate in terms of the objective value, i.e., f (∑ki=1 xi k ) - minf = O ( 1k ), is proved by [Ghadimi et al., 2015]. HBGD was proved to converge linearly in the strongly convex case by [Ghadimi et al., 2015]. But the authors used a somehow restrictive assumption on the parameter β, which leads to a small range values of choose for β when the strongly convex constant is tiny. Due to the inertial term β(xk - xk-1 ), HBGD breaks Fej´er monotonicity that gradient descent obeys. Consequently, it is difficult to prove its non-ergodic convergence rates. To this end, [Sun et al., 2019] designed a novel Lyapunov analysis and derived better convergence results like non-ergodic sublinear convergence rate (f (xk ) - min f = O ( 1k )) and larger stepsize for linear convergence. [Combettes and Glaudin, 2017] developed and studied heavy-ball methods for operator research. In the nonconvex case, if the objective function is nonconvex but Lipschitz differentiable, [Zavriev and Kostyuk, 1993] proved that the sequence generated by the heavy-ball gradient descent is convergent to a critical point, but without specifying related convergence rates. With semi-algebraic assumption on the objective function, [Ochs et al., 2014] proved the sequence generated by HBGD is convergent to some critical point. Actually, [Ochs et al., 2014] also extended HBGD to a nonsmooth composite optimization problem. [Xu and Yin, 2013] developed and analyzed the Heavy-ball algorithm for tensor minimization problems. [Loizou and Richt´arik, 2017a; Loizou and Richt´arik, 2017b] introduced the stochastic versions of heavy-ball algorithms and its relations with existing methods.

On the other hand, [Alvarez, 2000] studied a secondorder ODE whose implicit discretization yields the HeavyBall Proximal Point Algorithm (HBPPA) mathematically described as

which admits the acceleration of the proximal point algorithm. In fact, the setting β = 0 will push the scheme back to be the basic proximal point algorithm. The convergence of HBPPA is studied by [Alvarez, 2000] with several assumptions on the parameters γ and β when f is convex. Noticing the fact that ∇f is actually the maximal monotone operator in the convex case, [Alvarez and Attouch, 2001] extended HBPPA to solve the inclusion problem. The inexact HBPPA was proposed and studied by [Moudafi and Elizabeth, 2003]. Existing works on HBPPA are all based on the convex assumption on the f. In this paper, we will present the convergence of nonconvex HBPPA including the gradient convergence under smooth assumption and sequence convergence under semialgebraic assumption.

The performances of HBGD and HBPPA with convex settings exclude the interest of this paper. What we care is that can these two algorithms escape the saddle points when f is nonconvex? This paper answers this problem.

1.2 First-order Algorithms Escape Saddle Points

In the community of nonconvex continuous optimization, saddle points, which are usually unavoidable and outnumber the cardinality of local minima, have long been regarded as a major obstacle. In many applications like tensor decomposition [Ge et al., 2015], matrix completion [Ge et al., 2016] and dictionary learning [Sun et al., 2017], all local optima are also globally optimal. In some networks, under several conditions, local optimas are close to the global optima [Chaudhari et al., 2016]. Although these conditions are barely satisfied by many networks, the conclusion coincides with existing experimental observations. Thus if all local minimizers are relatively good, we just need to push the iterations to escape the saddle points. And how to escape the saddle points has been a hot topic recently for firstorder optimization algorithms. [Pemantle, 1990] established the convergence of the Robbins-Monro stochastic approximation to local minimizers by introducing sufficiently large unbiased noise. For tensor problem, [Ge et al., 2015] provided the quantitative rates on the convergence of noisy gradient descent. For general smooth nonconvex functions, the analysis of noisy gradient descent is established by [Jin et al., 2017a]. In a latter paper, [Jin et al., 2017b] considered the noisy accelerated gradient descent and established related convergence theory. Another technique to escape the saddle points is using random initializations. It has been shown that, even without any random perturbations, a good initialization can make gradient descent converge to the global minimum for various non-convex problems like matrix factorization [Keshavan et al., 2010] , phase retrieval [Cai et al., 2016], dictionary learning [Arora et al., 2015]. [Lee et al., 2016; Lee et al., 2017] proved that for plenty of first-order nonconvex optimization algorithms, with random initializations, they can converge to local minima with probability 1. In the perspective of mathematics, the core techniques consist of two parts: 1). they reformulate the algorithms as mapping iterations; 2). the stable manifold theorem [Shub, 2013] is employed. In this paper, we establish the theoretical guarantees for heavy-ball algorithms escaping the saddle points.

1.3 Difficulty in Analyzing Heavy-ball Iterations

The difficulty of study on the performance of heavy-ball with random initializations lies in how to reformulate the algorithm as iterations under a mapping. Taking the gradient descent for example, one can use g := I - γ∇f with γ being the stepsize. And then, the gradient descent can be represented as xk+1 = g(xk ). Constructing the mapping for gradient descent is obvious and easy. But for heavy-ball ones, the construction tasks are quite different due to the inertial term β(xk - xk-1 ). Point xk+1 is generated by both the current variable xk and the last one xk-1 . Thus, it is impossible to find a mapping g to rewrite the heavy-ball as xk+1 = g(xk ).

1.4 Contribution

Due to that the analysis of nonconvex HBPPA is still blank, we establish related theory in this paper. And with the recently developed techniques in variational analysis, the sequence convergence of nonconvex HBPPA is also studied. But our main interests are still the analysis of HBGD and HBPPA with random initializations. We prove guarantees for both algorithms to escape saddle points under mild assumptions. Direct using the existing method is unapplicable for heavyball algorithms. Thus, we propose a novel construction technique. It can be proved that heavy-ball gradient descent enjoys larger stepsize than gradient descent to escape the saddle points with random starting points, which somehow indicates the advantages of heavy-ball methods.

2 Preliminaries

In this part, we introduce several basic definitions and tool lemmas. For a closed function J (not necessary to be convex), the proximal map is defined as

Under the condition that J is differentiable, if y = ProxJ(z), the K.K.T. condition can yields that ∇J(y) + y - z = 0. Given another point arbitrary x ∈ RN , it holds that

For matrices A and B, A ∼ B denotes that there exist perturbation matrices P,Q such that A = PBQ. We use IN and 0N to denote the N ×N unit and zero matrix, respectively. det(A) is determinant of matrix A. It is easy to see if A ∼ B, det(A) = 0 ⇔ det(B) = 0.

Definition 1 (Strict Saddle) We present the following two definitions,

1. A point x∗ is a critical point of f if ∇f(x∗ ) = 0. x∗ is isolated if there is a neighborhood U around x∗ , and x∗ is the only critical point in U.
2. A point x∗ is a strict saddle point of f if x∗ is a critical point and λmin(∇2 f(x∗ )) < 0. Let χ∗f denote the set of strict saddle points of function f.

Let g be a mapping; and its domain is defined as dom(g) := {x | g(x) ̸= ∅}. And gk denotes the k-fold composition of g. Our interest is the sequence generated by

Definition 2 (Global Stable Set) The global stable set of the strict saddles is the set of initial conditions where iteration of the mapping g converges to a strict saddle, i.e., Wg := {x0 : limk gk (x0) ∈ χ∗ }. For an iterative algorithm M, WM := {x0 : limk xk ∈ χ∗ } and {x1 , . . .} is generated by Mwith starting point x0 .

Definition 3 (Unstable fixed point) The differential of the mapping g, denoted as Dg(x), is a linear operator from T (x) → T (g(x)), where T (x) is the tangent space of X at point x. Given a curve γ in X with γ(0) = x and dγ dt (0) := v ∈ T (x), the linear operator is defined as Dg(x)v = d(g◦γ) dt (0) ∈ T (g(x)). Let

be the set of fixed points where the differential has at least a single real eigenvalue with magnitude greater than one. These are the unstable fixed points.

With previous definitions, the authors in [Lee et al., 2017] presented the following result. The core technique is employing the stable manifold theorem given in [Shub, 2013].

Lemma 1 Let g be a C 1 mapping and det(Dg(x)) ̸= 0 for all x ∈ dom(g). Assume the sequence (xk )k≥0 is generated by scheme (6). Then the set of initial points that converge to an unstable fixed point has measure zero, µ({x0 : limxk ∈ A∗g }) = 0. Further if X ∗ ⊂ A∗g , µ(Wg) = 0.

3 Main Results

In this section, we present the theoretical guarantees to escape the saddle points for the heavy-ball algorithms presented before. We need a smooth assumption on the objective function.

Assumption 1 The objective function f is twicedifferentiable and ‖∇2 f(x)‖2 ≤ L, where ‖ · ‖2 denotes the spectral norm of a matrix. Otherwise the objective function satisfies that limx∈RN f(x) > -∞.

The smooth assumption is used to derive the differential of the designed mapping. And the lower bounded assumption is used to provide a lower bound for the descent variables.

Lemma 2 Let (xk )k≥0 be generated by the HBGD (2) with 0 < β < 1. If the stepsize is selected as

we have µ{(x0 , x1 ) : limk xk ∈ χ∗f } = 0 and µ{WHBGD} = 0.

It is easy to see that if β < 1 2 the upper bound of the stepsize is therefore larger than 1L for HBGDwith random initializations. And the upper bound is closed to 2L provided that β is sufficiently small. [Lee et al., 2016] proved that the stepsize for the GD with random initializations is required to be smaller than 1L . Lemma 2 means a larger stepsize can be used under the heavy-ball scheme, which somehow demonstrates the advantage of heavy-ball method.

The difficulty of the analysis for HBGD has been presented in Sec. 1: it is impossible to find to a mapping such that xk+1 = g(xk ) directly. Noticing the kth iteration involves with xk and xk-1 , we turn to consider combining the these two points together, i.e., (xk , xk-1 ). And then, the task then turns to find a mapping such that (xk+1 , xk ) = ˆ g(xk , xk-1 ). The mapping ˆ g is fromR2N to R2N . After building the relations between the unstable fixed point of ˆ g and the strict saddle points, the theorem then can be proved. Different from existing results in [Lemma 1,[Sun et al., 2019]], β ̸= 0 here. This is to make sure that the differential of the constructed mapping in the proofs is invertible. And the differential is non-symmetric.

Lemma 2 actually means Prob(x0 ∈ WHBGD) = 0, that is, HBGD always escapes saddle points provided the stepsize is set properly. Lemma 2 just means that (xk )k≥0 will not fall into a saddle point. But whether the sequence converges or not is out of scope of this lemma. In the nonconvex optimization community, such a problem is answered by posing the semi-algebracity assumption on the objective function [Łojasiewicz, 1993; Kurdyka, 1998] or the isolated assumption on the critical point [Lange, 2013]. Thus, we can derive the following result.

Theorem 1 Assume that conditions of Lemma 2 hold and f is coercive 1 . Suppose the starting points x0 and x1 are totally random and one of the following conditions is satisfied.

1. f is semi-algebraic.
2. All critical points of f are isolated points.

Then, for HBGD, limk xk exists and that limit x∗ is a local minimizer of f with probability 1.

Now, we study the HBPPA. First, we provide the convergence in the nonconvex settings.

Lemma 3 Let (xk )k≥0 be generated by scheme (3) with 0 < β < 1 2 and γ > 0. Then, we have limk ‖∇f(xk )‖ = 0. Further more, if the function f is semi-algebraic and coercive, (xk )k≥0 is convergent to some critical point x∗ .

To obtain the sequence convergence of HBPPA, besides the semi-algebraicity, the coercivity is also needed, which is used to guarantee the boundedness of the generated sequence. In Lemma 3, f is set to be differentiable. Actually, the smooth setting can be removed. Alternatively, we need to use the notion about subdifferentials of closed functions [Rockafellar and Wets, 2009] which are frequently used in the variational analysis. Specifically, in the smooth case, subdifferential is actually the gradient. With the same parameters, the sequence of HBPPA is still provably to converge to a critical point of f .

1 We say function coercive if f(x) → +∞ as ‖x‖ → +∞.

We are prepared to present the guarantee for HBPPA to escape the saddle point.

Lemma 4 Let (xk )k≥0 be generated by scheme (3) with 0 < β < 12 , if the stepsize is selected as

we have µ{(x0 , x1 ) : limk xk ∈ χ∗f } = 0 and µ{WHBPPA} = 0.

For HBPPA, the stepsize requirement coincides with existing result [Lee et al., 2017]. Main idea of proof of Lemma 4 is similar to Lemma 2, but more complicated in details.

Theorem 2 Assume that conditions of Lemma 4 hold and f is coercive. Suppose the starting points x0 and x1 are totally random and one of the following conditions is satisfied.

1. f is semi-algebraic.
2. All critical points of f are isolated points.

Then, for HBPPA, limk xk exists and that limit x∗ is a local minimizer of f with probability 1.

4 Proofs

This section collects the proofs for the this paper.

4.1 Proof of Lemma 2

To guarantee the convergence of HBGD, from [Lemma 1,[Sun et al., 2019]], we need 0 ≤ β < 1 and 0 < γ < 2(1-β) L . Let y, z ∈ RN and w := (y, z), denote a map as

It is easy to check that if F(w) = 0 =⇒ y = z. We further denote wk := (xk , xk-1 ) ∈ R2N . It can be easily verified that the Heavy-ball methods can be reformulated as

To use Lemma 1, we turn to the proofs of two facts:

1. det(DF(w)) ̸= 0 for all w ∈ R2N .

Proof of fact 1: Direct calculations give us

We use the short-hand notation A(y) := (1 + β)IN - γ∇2 f(y). We can obtain the following relation

Therefore, we can derive det (DF(w)) ̸= 0 for any w ∈ R2N .

Proof of fact 2: For any x∗ being a strict saddle, with the symmetry of ∇2 f(x∗ ), then

For λ ∈ R and λ ̸= 0 2 , denoting w∗ = (x∗ , x∗ ), we consider

After simplifications, we can get

That indicates det(λI2N - DF(w∗ )) = 0 ⇐⇒ det(λIN + βλ IN -A(x∗ )) = 0. Denote function s(t) := t + βt , t > 0. All the eigenvalues of DF(w∗ ) are the roots of the equation above. We exploit the two roots of λ+ βλ = λmax(A(x∗ )). It is easy to check that λmax(A(x∗ ))2 - 4β > (1 - β)2 ≥ 0, which means this equation has two real roots denoted as 0 < λ < λ. Noting λmax(A(x∗ )) > 1 + β, that is s(λ) > s(1). We can see that s(t) is increasing on [√β,+∞). With the fact 0 ≤ β < 1, s(t) is increasing on [1,+∞). Thus, there exists some real number λ0 > 1 such that λ > λ0. Thus, we get λmax(DF(w∗ )) ≥ λ ≥ λ0 > 1, i.e., w∗ ∈ A∗F . That is also

Using Lemma 1, µ{w0 : limk wk ∈ A∗F } = 0 and then

On the other hand, due to the nonnegativity of the measurement,

4.2 Proof of Theorem 1

The first case has been proved in [Ochs et al., 2014], in which (xk )k≥0 is convergent to some critical point x∗ . For the second case, [Proposition 12.4.1, [Lange, 2013]] and equation (10) means that the stationary set of (xk )k≥0 is finite. Otherwise, the stationary set is connected which contradicts with the fact all critical points are isolated. Once using [Proposition 12.4.1, [Lange, 2013]], the stationary set has only one element x∗ ; and then, (xk )k≥0 → x∗ .

Therefore, in both cases, it can be proved that (xk )k≥0 → x∗ ∈ RN . With Lemma 2, x∗ is a local minimizer with probability 1 if the starting points x0 , x1 are random. The theorem is then proved.

4.3 Proof of Lemma 3

This subsection contains two parts. Part 1 is to prove the gradient convergence, while Part 2 contains the sequence convergence proof.

2 We have proved that DF(w) is nonsingular.

xk-1 ), x ← xk , J ← γf ,

After simplifications, we then get

Denote a novel function as

and sequence wk := (xk , xk-1 ). Thus, inequality (8) offers the descent as

With the fact infx∈RN f(x) > -∞, infk H(wk ) > -∞. The setting 0 < β < 1 2 gives

On the other hand, from the property of the proximal map,

which can derive

Part 2. We prove that H(x, y) is coercive provided f is coercive. If this claim fails to hold, there exists some C > 0

With the coercivity of f, there exists some C1 > 0 such that ‖x‖ ≤ C1. On the other hand, ‖x - y‖ is bounded due to the lower boundedness of f; thus, ‖y‖ is bounded, which contradicts the fact ‖(x, y)‖ → +∞.

From (9), we see that (wk )k≥1 is bounded; and then, (xk )k≥0 is bounded. The descent property of (H(wk ))k≥1 and the continuity of function H directly give that

That means the sequence has a stationary point x∗ ; (12) means x∗ admits the critical point of f. It is easy to see w∗ := (x∗ , x∗ ) is the critical point of H. Without loss of generality, we assume wk ̸= w∗ as k ≥ 1.

Noting polynomial functions are semi-algebraic and the fact that sum of semi-algebraic functions is still semialgebraic, H(w) is then semi-algebraic. Denote the set of all stationary points of (wk )k≥0 as Ω. From [Lemma 3.6, [Bolte et al., 2014]], there exist η, ε ∈ (0,+∞] and a continuous concave function ϕ : [0, η) → R+ such that

For the η, ε given above, as k is large enough, wk will fall into the set {w|H(w∗ ) < H(w) < H(w∗ ) + η} ⋂{w|dist(w, Ω) < ε}. The concavity of ϕ gives

where ν = 1-2β 2γ , and a) uses 9, and b) comes from (14). The gradient of H satisfies

where c) depends on (11) and, we used the fact 0 < β < 1 2 . Combining (15) and (16),

where d) employs the Schwarz inequality 2(xy) 12 ≤ x + y with x = 2√ ζν √ϕ(H(wk ) - H(w∗ )) - ϕ(H(wk+1 ) - H(w∗ )), and y = 1 2 √‖xk+1 -xk ‖+‖xk -xk-1 ‖. Summing both sides of (17) from sufficiently large k to K, we have

Letting K → +∞, from (10), (13), ϕ(0) = 0 and the continuity of ϕ, (18) then yields ∑+∞ i=k ‖xi+1 - xi ‖ ≤ 16 ‖xk - xk-1 ‖ + 4 νγ ϕ(H(wk ) - H(w∗ )) < +∞. We are then led to ∑+∞ i=k ‖xi+1 - xi ‖ < +∞ ⇒ ∑+∞ i=0 ‖xi+1 - xi ‖ < +∞. That means (xk )k≥0 is convergent to some point. With the fact, x∗ is a stationary point, (xk )k≥0 → x∗ .

4.4 Proof of Lemma 4

In this proof, we denote the mapping as

To calculate the differential of F , we denote

It is easy to see that

The definition of the proximal map then gives

By implicit differentiation on variable y, we can get

Due to that 0 < γ < 1L , γ∇2 f[g(y, z)]+IN is invertible. We use a shorthand notation

For z, by the same procedure, then we can derive

With (19) and (21), we are then led to

That means for any w ∈ R2N , det(DF(w)) ̸= 0. On the other hand, if x∗ is a strict saddle, g(x∗ , x∗ ) = x∗ , λmax(A(x∗ , x∗ )) > 1. For λ ∈ R, denoting w∗ = (x∗ , x∗ ), we consider

After simplifications, we can derive

With direct computations, we turn to

We consider the following equation

Direct calculations give

Thus, the equation enjoys two real roots denoted by λ < λ. It is easy to see that λ > 0. Noticing that H(1) < 0 and limλ→+∞H(λ) = +∞, we have λ > 1. That means λmax(DF(w∗ )) ≥ λ > 1, thus, w∗ ∈ A∗F . Consequently, the proof is proved by Lemma 1.

4.5 Proof of Theorem 2

This proof is similar to the one of Theorem 1 and will not be reproduced.

5 Conclusion

In this paper, we proved that HBGD and HBPPA always escape the saddle points with random initializations. This paper also established the convergence of nonconvex HBPPA. The core part in the proofs is bundling current and the last point as one point in an enlarged space. The heavy algorithms then can be represented as an iteration after a mapping. An interesting finding is that the HBGD can enjoy larger stepsize than the gradient descent to escape saddle points.

Acknowledgments

This work is sponsored in part by National Key R&D Program of China (2018YFB0204300), and Major State Research Development Program (2016YFB0201305), and National Natural Science Foundation of Hunan Province in China (2018JJ3616), and National Natural Science Foundation for the Youth of China (61602166), and Natural Science Foundation of Hunan (806175290082), and Natural Science Foundation of NUDT (ZK18-03-01), and National Natural Science Foundation of China (11401580).