Behavior of Accelerated Gradient Methods Near Critical Points of Nonconvex Functions

Introduction

We consider methods for the smooth unconstrained optimization problem

Our particular interest here is in methods that use gradients and momentum to construct steps. In many such methods, each step is a linear combination of two components: the gradient $\nabla f$ evaluated at a point at or near the latest iterate, and a momentum term, which is the step between the current iterate and the previous iterate. There are rich convergence theories for these methods in the case in which $f$ is convex or strongly convex, along with extensive numerical experience in some important applications. However, although these methods are applied frequently to nonconvex functions, little is known from a mathematical viewpoint about their behavior in such settings. Early results showed that a certain modified accelerated gradient method achieves the same order of convergence on a nonconvex problem as gradient descent — not a faster rate, as in the convex setting.

After submission of our paper, described a method that combines accelerated gradient, perturbation at points with small gradients and explicit negative curvature detection to attain a method with worst-case complexity guarantees.

Heavy-Ball is Unlikely to Converge to Strict Saddle Points

We show in this section that the heavy-ball method is not attracted to strict saddle points, unless initialized in a very particular way, that cannot occur if the starting point is chosen at random and the algorithm is modified slightly. Following , our proof is based on the stable manifold theorem.

We make the following assumption throughout this section.

Under this assumption, the eigenvalues of the Hessian $\nabla^{2}f(x^{*})$ are bounded in magnitude by $L$.

The heavy-ball method is a prototypical momentum method (see ), which proceeds as follows from a starting point $x^{0}$:

Convergence for this method is known for the special case in which $f$ is a strongly convex quadratic. Denote by $m$ the positive lower bound on the eigenvalues of the Hessian of this quadratic, and recall that $L$ is the upper bound. For the settings

a rigorous version of the eigenvalue-based argument in [13, Section 3.2] can be applied to show R-linear convergence with rate constant $\sqrt{\beta}$, which is approximately $1-\sqrt{m/L}$ when the ratio $L/m$ is large. This suggests a complexity of $O(\sqrt{L/m}\log\epsilon)$ iterations to reduce the error $\|x^{k}-x^{*}\|$ by a factor of $\epsilon$ (where $x^{*}$ is the unique solution). Such rates are typical of accelerated gradient methods. They contrast with the $O((L/m)\log\epsilon)$ rates attained by the steepest-descent method on such functions.

We note that the eigenvalue-based argument that is “sketched” by does not extend rigorously beyond strongly convex quadratic functions. A more sophisticated argument based on Lyapunov functions is needed, like the one presented for Nesterov’s accelerated gradient method in [14, Chapter 4].

The key to our argument for non-convergence to strict saddle points lies in formulating the heavy-ball method as a mapping whose fixed points are stationary points of $f$ and to which we can apply the stable manifold theorem. Following (3), we define this mapping to be

We have the following elementary result about the relationship of critical points for (1) to fixed points for the mapping $G$.

If $x^{*}$ is a critical point of $f$, then $(z_{1}^{*},z_{2}^{*})=(x^{*},x^{*})$ is a fixed point for $G$. Conversely, if $(z_{1}^{*},z_{2}^{*})$ is a fixed point for $G$, then $x^{*}=z_{1}^{*}=z_{2}^{*}$ is a critical point for $f$.

The first claim is obvious by substitution into (5). For the second claim, we have that if $(z_{1}^{*},z_{2}^{*})$ is a fixed point for $G$, then

from which we have $z_{2}^{*}=z_{1}^{*}$ and $\nabla f(z_{1}^{*})=0$, giving the result.

We now establish that $G$ is a diffeomorphic mapping, a property needed for application of the stable manifold result.

Suppose that Assumption 1 holds. Then the mapping $G$ defined in (5) is a $C^{r}$ diffeomorphism.

We need to show that $G$ is injective and surjective, and that $G$ and its inverse are $r$ times continuously differentiable.

To show injectivity of $G$, suppose that $G(x_{1},x_{2})=G(y_{1},y_{2})$. Then, we have

demonstrating injectivity. To show that $G$ is surjective, we construct its inverse $G^{-1}$ explicitly. Let $(y_{1},y_{2})$ be such that

Then $z_{1}=y_{2}$. From the first partition in (9), we obtain $z_{2}=(z_{1}-y_{1}-\alpha\nabla f(z_{1}))/\beta+z_{1}$, which after substitution of $z_{1}=y_{2}$ leads to

Thus, $G$ is a bijection. Both $G$ and $G^{-1}$ are continuously differentiable one time less than $f$, so by Assumption 1, $G$ is a $C^{r}$-diffeomorphism.

We are now ready to state the stable manifold theorem, which provides tools to let us characterize the set of escaping points.

Let be a fixed point for the $C^{r}$ local diffeomorphism $\phi:U\rightarrow E$ where $U$ is a neighborhood of in the Banach space $E$. Suppose that $E=E_{cs}\oplus E_{u}$, where $E_{cs}$ is the invariant subspace corresponding to the eigenvalues of $D\phi(0)$ whose magnitude is less than or equal to 1, and $E_{u}$ is the invariant subspace corresponding to eigenvalues of $D\phi(0)$ whose magnitude is greater than 1. Then there exists a $C^{r}$ embedded disc $W_{loc}^{cs}$ that is tangent to $E_{cs}$ at 0 called the local stable center manifold. Additionally, there exists a neighborhood $B$ of 0 such that $\phi(W_{loc}^{cs})\cap B\subset W_{loc}^{cs}$, and that if $z$ is a point such that $\phi^{k}(z)\in B$ for all $k\geq 0$, then $z\in W_{loc}^{cs}$.

This is a similar statement of the stable manifold theorem to the one found in , except that since we have to deal with complex eigenvalues here, we emphasize that the decomposition is between the eigenvalues whose magnitude is less than or equal to $1$, and greater than $1$, respectively. It guarantees the existence of a stable center manifold of dimension equal to the number of eigenvalues of the Jacobian at the critical point that are less than or equal to 1.

We show now that the Jacobian $DG(x^{*},x^{*})$ has the properties required for application of this result, for values of $\alpha$ and $\beta$ similar to the choices (4). (Note that the conditions on $\alpha$ and $\beta$ in this result hold when $\alpha\in(0,4/L)$ and $\beta\in(-1+\alpha L/2,1)$, where $L$ is the Lipschitz constant from Assumption 1.) For purposes of this and future results in this section, we assume that at the point $x^{*}$ we have $\nabla f(x^{*})=0$ and that the eigenvalue decomposition of $\nabla^{2}f(x^{*})$ can be written as

where the eigenvalues $\lambda_{1},\lambda_{2},\dotsc,\lambda_{n}$ have

for some $p$ with $1\leq p<n$, where $\Lambda=\operatorname{diag}(\lambda_{1},\lambda_{2},\dotsc,\lambda_{n})$, and where $v_{i}$, $i=1,2,\dotsc,n$ are the orthonormal set of eigenvectors that correspond to the eigenvalues in (12). The matrix $V=[v_{1}\,|\,v_{2}\,|\,\dotsc\,|\,v_{n}]$ is orthogonal.

Suppose that Assumption 1 holds. Let $x^{*}$ be a critical point for $f$ at which $\nabla^{2}f(x^{*})$ has $p$ negative eigenvalues, where $p\geq 1$. Consider the mapping $G$ defined by (5) where

By performing a symmetric permutation $P$ on this matrix, interleaving rows/columns from the first block with rows/columns from the second block, we obtain a block diagonal matrix with $2\times 2$ blocks of the following form on the diagonals, that is,

The eigenvalues of $M_{i}$ are obtained from the following quadratic in $\mu$:

We examine first the matrices $M_{i}$ for which $\lambda_{i}<0$. We have

so both roots in (18) are real. Since $t(\cdot)$ is convex quadratic, with $t(0)=\beta>0$ and $t(1)=\alpha\lambda_{i}<0$, one root is in $(0,1)$ and the other is in $(1,\infty)$. We can thus write

where $\mu_{i}^{\text{hi}}$ is the eigenvalue of $M_{i}$ in the range $(1,\infty)$ and $\mu_{i}^{\text{lo}}$ is the eigenvalue of $M_{i}$ in the range $(0,1)$. (This claim can be verified by direct calculation of the product (19a).)

Consider now the matrices $M_{i}$ for which $\lambda_{i}=0$. From (18), we have that the roots are $1$ and $\beta$, which are distinct, since $\beta\in(0,1)$. The eigenvalue decompositions of these matrices have the form

and the $S_{i}$ are $2\times 2$ nonsingular matrices.

When $\lambda_{i}>0$, we show that the eigenvalues of $M_{i}$ both have magnitude less than $1$, under the given conditions on $\alpha$ and $\beta$. Both roots in (18) are complex exactly when the term under the square root is negative, and in this case the magnitude of both roots is

which is less than $1$ by assumption. When both roots are real, we have $(1+\beta-\alpha\lambda_{i})^{2}-4\beta\geq 0$, and we require the following to be true to ensure that both are less than $1$ in absolute value:

We deal with the right-hand inequality in (21) first. By rearranging, we show that this is implied by the following sequence of equivalent inequalities:

where the last is clearly true, because of $\alpha>0$ and $\lambda_{i}>0$. Thus the right-hand inequality in (21) is satisfied.

For the left-hand inequality in (21), we have

and the last condition holds because of the assumption that $\beta>-1+\alpha\lambda_{1}/2$. This completes our proof of the claim (21). Thus our assumptions on $\alpha$ and $\beta$ suffice to ensure that both eigenvalues of $M_{i}$ defined in (15) have magnitude less than $1$ when $\lambda_{i}>0$.

where $S_{i}$, $i=n-p+1,\dotsc,n$ are the matrices defined in (19), we have from (14) that

Suppose that the assumptions of Theorem 2.6 hold. Then the eigenvector of $DG(x^{*},x^{*})$ that corresponds to the unstable eigenvalue $\mu_{i}^{\text{hi}}>1$, $i=n-p+1,\dotsc,n$ defined in (18) is

But this is true because of (17), so (24) is an eigenvector of $DG(x^{*},x^{*})$ corresponding to the eigenvalue $\mu_{i}^{\text{hi}}$. Since the vectors $\{v_{i}\,|\,i=n-p+1,\dotsc,n\}$ form an orthogonal set, so do the vectors (24) for $i=n-p+1,\dotsc,n$, completing the proof.

Our next result is similar to [9, Theorem 4.1]. It is for a modified version of the heavy-ball method in which the initial value for $x^{-1}$ is perturbed from its usual choice of $x^{0}$.

Suppose that the assumptions of Theorem 2.6 hold. Suppose that the heavy-ball method is applied from an initial point of $(x^{0},x^{-1})=(x^{0},x^{0}+\epsilon y)$, where $x^{0}$ and $y$ are random vectors with $i.i.d.$ elements, and $\epsilon>0$ is small. We then have

where the probability is taken over the starting vectors $x^{0}$ and $y$.

Our proof tracks that of [9, Theorem 4.1]. As there, we define the stable set for $x^{*}$ to be

Theorem 2.10 does not guarantee that once the iterates leave the neighborhood of $x^{*}$, they never return. It does not exclude the possibility that the sequence $\{(x^{k+1},x^{k})\}$ returns infinitely often to a neighborhood of $(x^{*},x^{*})$.

We note that the tweak of taking $x^{-1}$ slightly different from $x^{0}$ does not affect practical performance of the heavy-ball method, and has in fact been proposed before . It also does not disturb the theory that exists for this method, which for the case of quadratic $f$ discussed in rests on an argument based on the eigendecomposition of the (linear) operator $DG$, which is not affected by the modified starting point. We note too that the accelerated gradient methods to be considered in the next section can also allow $x^{-1}\neq x^{0}$ without significantly affecting the convergence theory. A Lyapunov-function-based convergence analysis of this method (see, for example [14, Chapter 4], based on arguments in ) requires only trivial modification to accommodate $x^{-1}\neq x^{0}$.

We write $w=\sum_{i=1}^{n}\tau_{i}v_{i}$ for some coefficients $\tau_{i}$, $i=1,2,\dotsc,n$, and show that $\tau_{i}=0$ for $i=n-p+1,\dotsc,n$.

where $\sigma_{0,i}=\tau_{i}$ and $\eta_{0,i}=\tau_{i}$, $i=1,2,\dotsc,n$. To derive recurrences for $\sigma_{k,i}$ and $\eta_{k,i}$, we consider the multiplication by $DG(x^{*},x^{*})$ that takes us from stages $k$ to $k+1$. We have

where $M_{i}$ is defined in (15). Using the factorization (19), we have

Because $0<\mu_{i}^{\text{lo}}<1<\mu_{i}^{\text{hi}}$, it follows from this formula that

so if $w$ has any component in the span of $v_{i}$, $i=n-p+1,\dotsc,n$ (that is, if $\tau_{i}\neq 0$), repeated multiplications of $\left[\begin{matrix}w\\ w\end{matrix}\right]$ by $DG(x^{*},x^{*})$ will lead to divergence, so $\left[\begin{matrix}w\\ w\end{matrix}\right]$ cannot be in the subspace $E_{cs}$.

A consequence of this theorem is that for a random choice of $x^{0}$, there is probability zero that $(x^{0}-x^{*},x^{0}-x^{*})\in E_{cs}$, which is tangential to $W^{cs}_{loc}$ at $x^{*}$. Thus for $x^{0}$ close to $x^{*}$, there is probability zero that $(x^{0},x^{0})$ is in the measure-zero set $W^{cs}_{loc}$. Successive iterations of (2) are locally similar to repeated multiplications of $(x^{0}-x^{*},x^{0}-x^{*})$ by the matrix $DG(x^{*},x^{*})$, that is, for $(x^{k+1}-x^{*},x^{k}-x^{*})$ small, we have

Under the probability-one event that $x^{0}-x^{*}\notin E_{cs}$, this suggests divergence of the iteration (2) away from $(x^{*},x^{*})$.

On the other hand, we can show that if the sequence passes sufficiently close to a point $(x^{*},x^{*})$ such that $x^{*}$ satisfies second-order sufficient conditions to be a solution of (1), it subsequently converges to $(x^{*},x^{*})$. For this result we need the following variant of the stable manifold theorem.

Let be a fixed point for the $C^{r}$ local diffeomorphism $\phi:U\rightarrow E$ where $U$ is a neighborhood of in the Banach space $E$. Suppose that $E_{s}$ is the invariant subspace corresponding to the eigenvalues of $D\phi(0)$ whose magnitude is strictly less than 1. Then there exists a $C^{r}$ embedded disc $W_{loc}^{s}$ that is tangent to $E_{s}$ at , and a neighborhood $B$ of such that $W_{loc}^{s}\subset B$, and for all $z\in W_{loc}^{s}$, we have $\phi^{k}(z)\to 0$ at a linear rate.

Speed of Divergence on a Toy Problem

In this section, we investigate the rate of divergence of an accelerated method on a simple nonconvex objective function, the quadratic with $n=2$ defined by

Obviously, this function is unbounded below with a saddle point at $(0,0)^{T}$. Its gradient has Lipschitz constant $L=1$. Despite being a trivial problem, it captures the behavior of gradient algorithms near strict saddle points for indefinite quadratics of arbitrary dimension, as is apparent from the analysis below.

We have described the heavy-ball method in (2). The steepest-descent method, by contrast, takes steps of the form

for some $\alpha_{k}>0$. When $\nabla f(x)$ has Lipschitz constant $L$, the choice $\alpha_{k}\equiv 1/L$ leads to decrease in $f$ at each iteration that is consistent with convergence of $\|\nabla f(x^{k})\|$ to zero at a sublinear rate when $f$ is bounded below . (The classical theory for gradient descent says little about the case in which $f$ is unbounded below, as in this example.)

We consider a starting point that is just off the horizontal axis, that is,

For the steepest-descent method with constant steplength, we have

One measure of repulsion from the saddle point is the number of iterations required to obtain $|x^{k}_{2}|\geq 1$. Here it suffices for $k$ to be large enough that $(1+\delta\alpha)^{k}\epsilon\geq 1$, for which (using the usual bound $\log(1+\gamma)\leq\gamma$) a sufficient condition is that

Making the standard choice of steplength $\alpha=1/L=1$, we obtain

Consider now the heavy-ball method. Following (2), the iteration has the form:

(For this quadratic problem, the operator $G$ defined by (5) is linear, so that $DG$ is constant.) We can partition this recursion into $x_{1}$ and $x_{2}$ components, and write

The eigenvalues of these two matrices are given by (18), by setting $\lambda_{1}=1$ and $\lambda_{2}=-\delta$, respectively. For $\alpha$ and $\beta$ satisfying the conditions of Theorem 2.6, which translate here to

both eigenvalues of $M_{1}$ are less than $1$ in magnitude (as we show in the proof of Theorem 2.6), so the $x_{1}$ components converge to zero. Again referring to the proof of Theorem 2.6, the eigenvalues of $M_{2}$ are both real, with one of them greater than $1$, suggesting divergence in the $x_{2}$ component.

To understand rigorously the behavior of the $x_{2}$ sequence, we make some specific choices of $\alpha$ and $\beta$. Consider

for some parameter $\gamma\geq 0$. Note that for small $\delta$ and $\gamma$, these choices are consistent with (35). By substituting into (18), we see that the two eigenvalues of $M_{2}$ are

For reasonable choices of $\gamma$, we have that $\mu_{2}^{\text{hi}}=1+c\sqrt{\delta}$ for a modest positive value of $c$. For specificity (and simplicity) let us consider $\alpha=3$ and $\gamma=0$, for which we have

The formula (19) yields $M_{2}=S_{2}\Lambda_{2}S_{2}^{-1}$, where $\Lambda_{2}=\operatorname{diag}(1+\sqrt{3\delta},1-\sqrt{3\delta})$ and

From (33), and setting $x^{0}_{2}=x^{-1}_{2}=\epsilon$, we have

By substituting for $\Lambda_{2}$ and $S_{2}$, we obtain

where we simply drop the term involving $\mu_{2}^{\text{lo}}$ in the final step and use $1-\sqrt{3\delta}>0$. It follows that

It follows from this bound, by a standard argument, that a sufficient condition for $x_{2}^{k}\geq 1$ is

Thus we have confirmed that divergence from the saddle point occurs in $O(|\log\epsilon|/\sqrt{\delta})$ iterations for heavy-ball, versus $O(|\log\epsilon|/\delta)$ iterations for gradient descent.

For larger values of $\delta$, the divergence of steepest-descent and heavy-ball methods are both rapid, For appropriate choices of $\alpha$ and $\beta$, the iterates generated by both algorithms leave the vicinity of the saddle point quickly.

Figure 1 illustrates the divergence behavior of steepest descent and heavy-ball on the function (27) with $\delta=.02$. We set $\alpha=.75$ for both steepest descent and heavy-ball. For heavy-ball, we chose $\beta=1-\alpha\delta=.985$. Both methods were started from $x^{0}=(.25,.01)^{T}$. We see that the trajectory traced by steepest descent approaches the saddle point quite closely before diverging slowly along the $x_{2}$ axis. The heavy-ball method “overshoots” the $x_{2}$ axis (because of the momentum term) but quickly returns to diverging along the $x_{2}$ direction at a faster rate than for steepest descent.

General Accelerated Gradient Methods Applied to Quadratic Functions

Here we analyze the rate at which a general class of accelerated gradient methods escape the saddle point of an $n$-dimensional quadratic function:

where $H$ is a symmetric matrix with eigenvalues satisfying (12). We assume without loss of generality that $H$ is in fact diagonal, that is,

The Lipschitz constant $L$ for $\nabla f$ is $L=\max(\lambda_{1},-\lambda_{n})$.

As in Section 3, gradient descent with $\alpha\in(0,1/L)$ satisfies

It follows that for all $i\geq n-p+1$, for which $\lambda_{i}<0$, gradient descent diverges in that component at a rate of $(1-\alpha\lambda_{i})$.

Algorithm 1 describes a general accelerated gradient framework, including gradient descent when $\gamma_{k}=\beta_{k}=0$, heavy-ball when $\gamma_{k}=0$ and $\beta_{k}>0$, and accelerated gradient methods when $\gamma_{k}=\beta_{k}>0$. With $f$ defined by (38), the update formula can be written as

The following theorem describes the dynamics of $x^{k+1}_{i}$ in (41) when $\lambda_{i}<0$.

For all $i$ such that $\lambda_{i}<0$, we have from (41) that

In addition if $\gamma_{k+1}\geq\gamma_{k}$ and $\beta_{k+1}\geq\beta_{k}$ for all $k$ then,

We begin by showing that (43) holds for $k=0$ and $k=1$. The case for $k=0$ is trivial as $x^{1}=x^{0}$. In addition, for $k=1$, the update formula (41) becomes

Thus because $b_{i,0}=0$, we can make this consistent with (42) by setting $b_{i,1}=\alpha|\lambda_{i}|$ which is exactly (43) for $k=1$.

Now assume that (42) holds for all $k\leq K-1$. From (41), using the inductive hypothesis for $K-1$ and $K-2$, we need to show

by the given definition of $b_{i,K}$ in (43). Dividing both sides by $x^{0}_{i}\prod_{m=0}^{K-1}(1+b_{i,m})$, this is equivalent to

Now we assume that $\gamma_{K+1}\geq\gamma_{K}$ and $\beta_{K+1}\geq\beta_{K}$ holds for all $K\geq 1$ and show by induction that $b_{i,K+1}\geq b_{i,K}$ holds for all $K\geq 0$. This is clearly true for $K=0$ since $\alpha|\lambda_{i}|>0$. Assume now that $b_{i,k+1}\geq b_{i,k}$ holds for all $0\leq k\leq K-1$. We have

where the second inequality above follows from $\gamma_{K+1}\geq\gamma_{K}$, $\beta_{K+1}\geq\beta_{K}$ and $b_{i,K-1}\geq b_{i,0}=0$.

Since $b_{i,k}\geq\alpha|\lambda_{i}|$ for all $k\geq 1$, Theorem 4.1 shows that Algorithm 1 diverges at a faster rate than gradient descent when at least one of $\gamma_{k}>0$ or $\beta_{k}>0$ is true. Now we explore the rate of divergence by finding a limit for the sequence $\{b_{i,k}\}_{k=1,2,\dotsc}$.

Let $\gamma_{k+1}\geq\gamma_{k}$ and $\beta_{k+1}\geq\beta_{k}$ hold for all $k$ and denote $\bar{\gamma}=\lim_{k\to\infty}\gamma_{k}$ and $\bar{\beta}=\lim_{k\to\infty}\beta_{k}$. Then, for all $i$ such that $\lambda_{i}<0$, we have $\lim_{k\rightarrow\infty}b_{i,k}=\bar{b}_{i}$, where $\bar{b}_{i}$ is defined by by

Recall from Theorem 4.1 that $x_{i}^{k}=(1+b_{i,k-1})x_{i}^{k-1}$. By substituting into the equation above, we have

By matching this expression with (47), we obtain

which after division by $b_{i,k-1}$ yields

Now assume for contradiction that the nondecreasing sequence $\{b_{i,k}\}_{k=1,2,\dotsc}$ has no finite limit, that is, $b_{i,k}\rightarrow\infty$. Recalling that $\gamma_{k}$ and $\beta_{k}$ have a finite limit (as they are nondecreaseing sequences restricted to the interval $$), we have by taking the limit as$k\to\infty$in (49) that the left-hand side approaches$\left(1+\alpha|\lambda_{i}|+\bar{\beta}+\bar{\gamma}\alpha|\lambda_{i}|\right)$, while the right-hand side approaches$\infty$, a contradiction. Thus, the nondecreasing sequence$\{b_{i,k}\}_{k=1,2,\dotsc}$has a finite limit, which we denote by$\bar{b}_{i}$.

To find the value for $\bar{b}_{i}$, we take limits as $k\rightarrow\infty$ in (48) to obtain

By solving this quadratic for $\bar{b}_{i}$, we obtain

By Theorem 4.1, we know that $b_{i,k}\geq 0$ for all $k$, so that $\bar{b}_{i}\geq 0$. Therefore, $\bar{b}_{i}$ satisfies (46), as claimed.

We apply Theorem 46 to parameter choices that typically appear in accelerated gradient methods.

Let the assumptions of Theorem 46 hold, let $\gamma_{k}=\beta_{k}$ hold for all $k$ and let $\bar{\gamma}=\bar{\beta}=1$. Then,

By direct computation with $\bar{\beta}=\bar{\gamma}=1$, we have

The above corollary gives a rate of divergence for many standard choices of the extrapolation parameters found in the accelerated gradient literature. In particular, it includes the sequence $\beta_{k}=\gamma_{k}=\frac{t_{k-1}-1}{t_{k}}$ where $t_{0}=1$ and

which was used in a seminal work by Nesterov . (For completeness, we provide a proof that $t_{k}\to\infty$, so that the assumptions of Corollary 4.5 hold for this sequence in the appendix.) Another setting used in recent works $\beta_{k}=\gamma_{k}=\frac{k-1}{k+\eta+1}$ . For proper choices of $\eta>0$, this scheme has a number of impressive properties such as fast convergence of iterates for accelerated proximal gradient as well as achieving a $o(\frac{1}{k^{2}})$ of convergence in the weakly convex case.

We can also use Theorem 46 to derive a bound for the heavy-ball method. If we target the $n$-th eigenvalue and set $\gamma_{k}=0$ and $\beta_{k}=1-\alpha|\lambda_{n}|$ for all $k$, simple manipulation shows that $\bar{b}_{n}=\sqrt{\alpha|\lambda_{n}|}$, which gives us an equivalent rate to that derived in (37). Note that for $\bar{b}_{n}$ defined in (50) we also have $\bar{b}_{n}\geq\sqrt{\alpha|\lambda_{n}|}$.

The divergence rates for accelerated gradient and heavy-ball methods are significantly faster than the per-iteration rate of $(1+\alpha|\lambda_{n}|)$ obtained for steepest descent.

Experiments

Some computational experiments verify that accelerated gradient methods escape saddle points on nonconvex quadratics faster than steepest descent.

We apply these methods to a quadratic with diagonal Hessian, with $n=100$ and a single negative eigenvalue, $\lambda_{n}=-\delta=-0.01$. The nonnegative eigenvalues are i.i.d. from the uniform distribution on $$, and starting vector$x^{0}$is drawn from a uniform distribution on the unit ball. Figure 2 plots the norm of the component of$x^{k}$in the direction of the negative eigenvector$e_{n}=(0,0,\dotsc,0,1)^{T}$at each iteration$k$, for accelerated gradient, heavy-ball, and steepest descent. It also shows the divergence that would be attained if the theoretical limit$\bar{b}_{i}$from Theorem 46 applied at every iteration. Steepest descent and heavy-ball were run with$\alpha=1/L$. Heavy-ball uses (36) to calculate$\beta$, yielding$\beta=0.989$in the case of$\delta=.01$. Accelerated gradient is run with$\alpha=0.99/L$and$\beta_{k}=\gamma_{k}=\frac{t_{k}-1}{t_{k+1}}$where$t_{k}$ is defined in (51).

It is clear from Figure 2 that accelerated gradient and heavy-ball diverge at a significantly faster rate than steepest descent. In addition, there is only a small discrepancy between applying accelerated gradient and its limiting rate that is derived in Corollary 4.5, suggesting that $b_{i,k}$ approaches $\bar{b}_{i}$ rapidly as $k\to\infty$.

Next we investigate how these methods behave for various dimensions $n$ and various distributions of the eigenvalues. For two values of $n$ ($n=100$ and $n=1000$), we generate $100$ random matrices with $n-5$ eigenvalues uniformly distributed in the interval $$, with the$5$negative eigenvalues uniformly distributed in$[-2\delta,-\delta]$. The starting vector$x^{0}$is uniformly distributed on the unit ball. Algorithmic constants were the same as those used to generate Figure 2. Each trial was run until the norm of the projection of the current iterate into the negative eigenspace of the Hessian was greater than the dimension$n$. The results of these trials are shown in Table 1.

As expected, accelerated gradient outperforms gradient descent in all respects. All convergence results are slightly faster for $n=100$ than for $n=1000$, because the random choice of $x^{0}$ will, in expectation, have a smaller component in the span of the negative eigenvectors in the latter case. The eigenvalue spectrum has a much stronger effect on the divergence rate. For steepest descent, an order of magnitude decrease in the absolute value of the negative eigenvalues corresponds to an order of magnitude increase in iterations, whereas Nesterov’s accelerated gradient sees significantly less growth in the iteration count. While the accelerated gradient method diverges at a slightly slower rate than the theoretical limit, the relative difference between the two does not change much as the dimensions change. Thus, Theorem 46 provides a strong indication of the practical behavior of Nesterov’s method on these problems.

Conclusion

We have derived several results about the behavior of accelerated gradient methods on nonconvex problems, in the vicinity of critical points at which at least one of the eigenvalues of the Hessian $\nabla^{2}f(x^{*})$ is negative. Section 2 shows that the heavy-ball method does not converge to such a point when started randomly, while Sections 3 and 4 show that when $f$ is an indefinite quadratic, momentum methods diverge faster than the steepest-descent method.

It would be interesting to extend the results on speed of divergence to non-quadratic smooth functions $f$. It would also be interesting to know what can be proved about the complexity of convergence to a point satisfying second-order necessary conditions, for unadorned accelerated gradient methods. A recent work shows that gradient descent can take exponential time to escape from a set of saddle points. We believe that a similar result holds for accelerated methods as well. The report , which appeared after this paper was submitted, describes an accelerated gradient method that add noise selectively to some iterates, and exploits negative curvature search directions when they are detected in the course of the algorithm. This approach is shown to have the $O(\epsilon^{-7/4})$ rate that characterizes the best known gradient-based algorithms for finding second-order necessary points of smooth nonconvex functions.

Acknowledgments

We are grateful to Bin Hu for his advice and suggestions on the manuscript. We are also grateful to the referees and editor for helpful suggestions.

References

In this appendix we show that the following two properties hold for the sequence defined by (51):

We begin by noting two well known properties of the sequence $t_{k}$ (see for example [4, Section 3.7.2]):

To prove that $\frac{t_{k-1}-1}{t_{k}}$ is monotonically increasing, we need

Since $t_{k+1}\geq t_{k}$ (which follows immediately from (51)), it is sufficient to prove that

By manipulating this expression and using (54), we obtain the equivalent expression

Thus (56) holds, so the claim (52) is proved. The sequence $\{(t_{k-1}-1)/t_{k}\}$ is nonnegative, since $(t_{0}-1)/t_{1}=0$.

Now we prove (53). We can lower-bound $(t_{k-1}-1)/t_{k}$ as follows:

For an upper bound, we have from $t_{k}\geq t_{k-1}$ that

Since $t_{k-1}\to\infty$ (because of (55)), it follows from (A) and (58) that (53) holds.