Accelerated Methods for Non-Convex Optimization

arXiv:1611.00756v2 [math.OC] 2 Feb 2017

Yair Carmon
John C. Duchi
Oliver Hinder
Aaron Sidford
{yairc,jduchi,ohinder,sidford}@stanford.edu
Abstract
We present an accelerated gradient method for non-convex optimization problems with Lipschitz continuous first and second derivatives. The method requires time O(−7/4 log(1/)) to
find an -stationary point, meaning a point x such that k∇f (x)k ≤ . The method improves
upon the O(−2 ) complexity of gradient descent and provides the additional second-order guarantee that ∇2 f (x)  −O(1/2 )I for the computed x. Furthermore, our method is Hessian-free,
i.e. it only requires gradient computations, and is therefore suitable for large scale applications.

1

Introduction

In this paper, we consider the optimization problem
minimize f (x),
x∈Rd

(1)

where f : Rd → R has L1 -Lipschitz continuous gradient and L2 -Lipschitz continuous Hessian, but
may be non-convex. Without further assumptions, finding a global minimum of this problem is
computationally intractable: finding an -suboptimal point for a k-times continuously differentiable
function f : Rd → R requires at least Ω((1/)d/k ) evaluations of the function and first k-derivatives,
ignoring problem-dependent constants [28, §1.6]. Consequently, we aim for a weaker guarantee,
looking for locally “optimal” points for problem (1); in particular, we seek stationary points, that
is points x with sufficiently small gradient:
k∇f (x)k ≤ .

(2)

The simplest method for obtaining a guarantee of the form (2) is gradient descent (GD). It is
well-known [32] that if GD begins from a point x1 , then for any ∆f ≥ f (x1 ) − inf x f (x) and  > 0,
it finds a point satisfying the bound (2) in O(∆f L1 −2 ) iterations. If one additionally assumes
that the function f is convex, substantially more is possible: GD then requires only O(RL1 −1 )
iterations, where R is an upper bound on the distance between x1 and the set of minimizers of f .
Moreover, in the same note [32], Nesterov also
√ shows that acceleration and regularization techniques
e RL1 −1/2 ).1
can reduce the iteration complexity to O(
In the non-convex setting, it is possible to achieve better rates of convergence to stationary points
assuming access to more than gradients, e.g. the full Hessian. Nesterov and Polyak [33] explore such
possibilities with their work on the cubic-regularized Newton method, which they show computes an
−3/2 ) iterations (i.e. gradient and Hessian calculations). However,
-stationary point in O(∆f L0.5
2 
with a naive implementation, each such iteration requires explicit calculation of the Hessian ∇2 f (x)
e 3 ).2 More recently, Birgin et al.
and the solution of multiple linear systems, with complexity O(d
1
2

e hides logarithmic factors. See Definition 5.
The notation O
e
Technically, O(dω ) where ω < 2.373 is the matrix multiplication constant [42].

1

[8] extend cubic regularization to pth order regularization, showing that iteration complexities of
O(−(p+1)/p ) are possible given evaluations of the first p derivatives of f . That is, there exist
algorithms for which −(p+1)/p calculations of the first p derivatives of f are sufficient to achieve
the guarantee (2); naturally, these bounds ignore the computational cost of each iteration. More
efficient rates are also known for various structured problems, such as finding KKT points for
indefinite quadratic optimization problems [43] or local minima of `p “norms,” p ∈ (0, 1), over
linear constraints [16].
In this paper, we ask a natural question: using only gradient information, is it possible to
improve on the −2 iteration complexity of gradient descent in terms of number of gradient calculations? We answer the question in the affirmative, providing an algorithm that requires at
most


1
1
7
1/2
1/2
−
−1
2
4
e ∆f L L  4 + ∆ L 
O
1 2
1
f
gradient and Hessian-vector product evaluations to find an x such that k∇f (x)k ≤ . For a summary
of our results in relation to other work, see Table 1.
Another advantage of the cubic-regularized Newton method is that it provides a second-order
√
guarantee of the form ∇2 f (x)  − I, thus giving a rate of convergence to points with zero gradient
and positive semi-definite Hessian. Such second-order stationary points are finer approximations
of local minima compared to first-order stationary points (with zero gradient). Our approach also
provides this guarantee, and is therefore an example of a first-order method that converges to a
second-order stationary point in time polynomial in the desired accuracy and with logarithmic
dependence on the problem dimension. A notable consequence of this approach is that for strict
saddle functions [24, 17]—with only non-degenerate stationary points—our approach converges
linearly to local minimizers. We discuss this result in detail in Section 5.
Table 1 Runtime comparisons for finding a first-order stationary point (2)

Gradient descent
(non-convex case)
Gradient descent
(convex case) [32]
Proximal accelerated
gradient descent [32]
Cubic-regularized
Newton method [33]
This paper
(Theorem 4.3)

1.1

# iterations

Hessian
free?

Gradient
Lipschitz?

Hessian
Lipschitz?

convex f ?

O ∆f L1 −2

Yes

Yes

No

No

Yes

Yes

No

Yes

Yes

Yes

No

Yes

No

Yes

Yes

No

Yes

Yes

Yes

No




−1

O RL1 


e (RL1 ) 12 − 12
O


1
e ∆f L 2 − 32
O
2


1
1
e ∆f L12 L24 − 74
O

Related work and background

In the optimization and machine learning literature, there has been substantial recent work on the
convergence properties of optimization methods for non-convex problems. One line of work investigates the types of local optima to which gradient-like methods converge, as well as convergence
rates. In this vein, under certain reasonable assumptions (related to geometric properties of saddle
points), Ge et al. [17] show that stochastic gradient descent (SGD) converges to second-order local
optima (stationary points with positive semidefinite Hessian), while Lee et al. [24] show that GD
generically converges to second-order local optima. Anandkumar and Ge [6] extend these ideas,
2

showing how to find a point that approximately satisfies the third-order necessary conditions for
local optimality in polynomial time. While these papers used second-order smoothness assumptions
to ensure convergence to stronger local minima than the simple stationary condition (2), they do
not improve rates of convergence to stationarity.
A second line of work focuses on improving the slow convergence rates of SGD to stationary points (typically O(−4 ) stochastic gradient evaluations are sufficient [18]) under appropriate
structural conditions on f . One natural condition—common in the statistics and machine learning
literature—is that f is the sum of n smooth non-convex functions. Indeed, the work of Reddi et al.
[37] and Allen-Zhu and Hazan [3] achieves a rate of convergence O(−2 ) for such problems without
performing the n gradient evaluations (one per function) that standard gradient descent requires
in each iteration. These analyses extend variance-reduction techniques that apply to incremental
convex optimization problems [22, 13]. Nonetheless, they do not improve on the O(−2 ) iteration
complexity of GD.
Additionally, a number of researchers apply accelerated gradient methods [31] to non-convex
optimization problems, though we know no theoretical guarantees giving improved performance
over standard gradient descent methods. Ghadimi and Lan [19] show how to modify Nesterov’s
accelerated gradient descent method so that it enjoys the same convergence guarantees as gradient
descent on non-convex optimization problems, while maintaining the accelerated (optimal) firstorder convergence rates for convex problems. Li and Lin [25] develop an accelerated method for
non-convex optimization and show empirically that on (non-convex) sparse logistic regression test
problems their methods outperform other methods, including gradient descent.
While the subproblem that appears in the cubic-regularized Newton method is expensive to
solve exactly, it is possible to consider methods in which such subproblems are solved only approximately by a low complexity Hessian-free procedure. A number of researchers investigate this
approach, including Cartis et al. [12] and Bianconcini et al. [7]. These works exhibit strong empirical results, but their analyses do not improve on the O(−2 ) evaluation complexity of gradient
descent. Recently, Hazan and Koren [20] and Ho-Nguyen and Kılınc-Karzan [21] have shown how to
solve the related quadratic non-convex trust-region problem using accelerated first-order methods;
both these papers use accelerated eigenvector computations as a primitive, similar to our approach.
It is therefore natural to ask whether acceleration can give faster convergence to stationary points
of general non-convex functions, a question we answer in the affirmative.
Concurrently to and independently of this paper,3 Agarwal et al. [2] also answer this question
affirmatively. They develop a method that uses fast approximate matrix inversion as a primitive to
solve cubic-regularized Newton-type steps [33], and applying additional acceleration techniques they
show how to find stationary points of general smooth non-convex objectives. Though the technical
approach is somewhat different, their convergence rates to -stationary pointsP
are identical to ours.
They also specialize their technique to problems of the finite sum form f = n1 ni=1 fi , showing that
additional improvements in terms of n are achievable.

1.2

Our approach

Our method is in the spirit of the techniques that underly accelerated gradient descent (AGD).
While Nesterov’s 1983 development of acceleration schemes may appear mysterious at first, there
are multiple interpretations of AGD as the careful combination of different routines for function
minimization. The estimate sequence ideas of Nesterov [31] and proximal point proofs [26, 40, 14]
show how to view accelerated gradient descent as a trade-off between building function lower
3

A preprint of the current paper appears on the arXiv [11].

3

bounds and directly making function progress. Bubeck et al. [10] develop an AGD algorithm with
a geometric interpretation based on shrinking spheres, while the work of Allen-Zhu and Orecchia
[5] shows that AGD may be viewed as a coupling between mirror descent [28] and gradient descent;
this perspective highlights how to trade each method’s advantages in different scenarios to achieve
faster—accelerated—running time.
We follow a similar template of leveraging two competing techniques for making progress on
computing a stationary point, but we deviate from standard analyses involving acceleration in our
coupling of the algorithms. The first technique we apply is fairly well known. If the problem is
locally non-convex, the Hessian must have a negative eigenvalue. In this case, under the assumption
that the Hessian is Lipschitz continuous, moving in the direction of the corresponding eigenvector
must make progress on the objective. Nesterov and Polyak [33] (and more broadly, the literature
on cubic regularization) use this implicitly, while other researchers [17, 6] use this more explicitly
to escape from saddle points.
The second technique is the crux of our approach. While L1 -Lipschitz continuity of ∇f ensures
that the smallest eigenvalue of the Hessian is at least −L1 , we show that any stronger bound—
any deviation from this “worst possible” negative curvature—allows us to improve upon gradient
descent. We show that if the smallest eigenvalue is at least −γ, which we call −γ-strong convexity,
we can apply proximal point techniques [35, 32] and accelerated gradient descent to a carefully
constructed regularized problem to obtain a faster running time. Our procedure proceeds by
approximately minimizing a sequence of specially constructed such functions. This procedure is
of independent interest since it can be applied in a standalone manner whenever the function is
known to be globally almost convex.
By combining these procedures, we achieve our result. We run an accelerated (single) eigenvector routine—also known as principle components analysis (PCA)—to estimate the eigenvector
corresponding to the smallest eigenvalue of the Hessian. Depending on the estimated eigenvalue we
either move along the approximate eigenvector or apply accelerated gradient descent to a regularized sub-problem, where we carefully construct the regularization based on this smallest eigenvalue.
Trading between these two cases gives our improved running time. We remark that an improvement
over gradient descent is obtainable even if we use a simpler (non-accelerated) method for estimating
eigenvectors, such as the power method. That said, an accelerated gradient descent subroutine for
the regularized sub-problems we solve appears to be crucial to achieving faster convergence rates
than gradient descent.
The remainder of the paper is structured as follows. Section 2 introduces the notation and
existing results on which our approach is based. Section 3.1 introduces our method for accelerating
gradient descent on “almost convex” functions, while Section 3.2 presents and explains our “negative
curvature descent” subroutine. Section 4 joins the two building blocks to obtain our main result,
while in Section 5, we show how our results give linear convergence to local minima for strict-saddle
functions.

2

Notation and standard results

Here, we collect our (mostly standard) notation and a few basic results. Throughout this paper,
norms k·k are the Euclidean norm; when applied to matrices k·k denotes the `2 -operator norm. All
logarithms are base-e. For a symmetric matrix A, we let λmin (A) and λmax (A) denote its minimum
and maximum eigenvalues, respectively. We also use the following definitions.
Definition 1 (Smoothness). A function f : Rd → R is L1 -smooth if its gradient is L1 -Lipschitz,
that is, k∇f (x) − ∇f (y)k ≤ L1 kx − yk for all x, y.
4

Definition 2 (Lipschitz Hessian). The Hessian of a twice differentiable function f : Rd → R is
L2 -Lipschitz continuous if ∇2 f (x) − ∇2 f (y) ≤ L2 kx − yk for all x, y.
Definition 3 (Optimality gap). A function f : Rd → R has optimality gap ∆f > 0 at point x if
f (x) − inf y∈Rd f (y) ≤ ∆f .
We assume throughout without further mention that f is L1 -smooth, has L2 -Lipschitz continuous
Hessian, and has optimality gap ∆f < ∞ at the initial search point, generally denoted z1 .
The next definition is atypical, because we allow the strong convexity parameter σ1 to be
negative. Of course, if σ1 < 0 the function may be non-convex, but we can use σ1 to bound the
extent to which the function is non-convex, similar to the ideas of lower C 2 -functions in variational
analysis [38]. As we show in Lemma 3.1 this “almost convexity” allows improvements in runtime
over gradient descent.
Definition 4 (Generalized strong convexity and almost convexity). A function f : Rd → R is σ1 strongly convex if σ21 ky−xk2 ≤ f (y)−f (x)−∇f (x)T (y−x) for some σ1 ∈ R. For γ = max{−σ1 , 0},
we call such functions γ-almost convex.
The next three results are standard but useful lemmas using the definitions above.
Lemma 2.1 (Nesterov [31], Theorem 2.1.5). Let f : Rd → R be L1 -smooth. Then for all x, y ∈ Rd
|f (y) − f (x) − ∇f (x)T (y − x)| ≤

L1
ky − xk2
2

Lemma 2.2 (Nesterov and Polyak [33], Lemma 1). Let f have L2 -Lipschitz Hessian. Then for all
x, y ∈ Rd
L2
ky − xk2
k∇f (y) − ∇f (x) − ∇2 f (x)(y − x)k ≤
2
and
1
L2
f (y) − f (x) − ∇f (x)T (y − x) − (y − x)T ∇2 f (x)(y − x) ≤
ky − xk3
2
6
Lemma 2.3 (Boyd and Vandenberghe [9], Eqs. (9.9) and (9.14)). Let f be L1 -smooth and µ-strongly
convex. Then for all x the minimizer x∗ of f satisfies
2µ[f (x) − f (x∗ )] ≤ k∇f (x)k2 ≤ 2L1 [f (x) − f (x∗ )].
Lemma 2.1 guarantees any L1 -smooth function is (−L1 )-strongly convex. A key idea in this
paper is that if a function is (−σ1 )-strongly convex with σ1 ≥ 0, standard convex proximal methods
are still applicable, provided the regularization is sufficiently large. The following trivial lemma,
stated for later reference, captures this idea.
Lemma 2.4. Suppose f : Rd → R is (−σ1 )-strongly convex, where σ1 ≥ 0. Then for any x0 ∈ Rd
the function g(x) = f (x) + σ1 kx − x0 k2 is (σ1 )-strongly convex.
Throughout this paper, we use a fully non-asymptotic big-O notation to be clear about the
convergence rates of the algorithms we analyze and to avoid confusion involving relative values of
problem-dependent constants (such as d, L1 , L2 ).
Definition 5 (Big-O notation). Let S be a set and let M1 , M2 : S → R+ . Then M1 = O(M2 ) if
there exists C ∈ R+ such that M1 (s) ≤ C · M2 (s) for all s ∈ S.
5

Throughout, we take S ⊂ [0, ∞)6 to be the set of tuples (, δ, L1 , L2 , ∆f , d); sometimes we require
e hides logarithmic factors
the tuples to meet certain assumptions that we specify. The notation O(·)
e 2 ) if M1 = O(M2 log(1+L1 +L2 +∆f +d+1/δ+1/)).
in problem parameters: we say that M1 = O(M
Because we focus on gradient-based procedures, we measure the running time of our algorithms
in terms of gradient operations, each of which we assume takes a (problem-dependent) amount of
time Tgrad . The following assumption specifies this more precisely.
Assumption A. The following operations take O(Tgrad ) time:
1. The evaluation ∇f (x) for a point x ∈ Rd .
2. The evaluation of ∇2 f (x)v for some vector v ∈ Rd and point x ∈ Rd . (See Remark 1 for
justification of this assumption.)
3. Any arithmetic operation (addition, subtraction or multiplication) of two vectors of dimension
at most d.
Based on Assumption A, we call an algorithm Hessian free if its basic operations take time at most
O(Tgrad ).
Remark 1: By definition of the Hessian, we have that limh→0 h−1 (∇f (x+hv)−∇f (x)) = ∇2 f (x)v
for any v ∈ Rd . Thus, a natural approximation to the product ∇2 f (x)v is to set
p=

∇f (x + hv) − ∇f (x)
h

for some small h > 0. By Lemma 2.2, we immediately have
p − ∇2 f (x)v ≤ h

L2 kvk2
,
2

which allows sufficiently precise calculation by taking h small.4
In a number of concrete cases, Hessians have structure that allows efficient computation of
the product v 7→ ∇2 f (x)v. For example, in neural networks, one may compute ∇2 f (x)v using a
back-propagation-like technique at the cost of at most two gradient evaluations [36, 39]. ♣

2.1

Building block 1: fast gradient methods

With the basic lemmas and definitions in place, we now recapitulate some of the classical development of accelerated methods. First, the following pseudo-code gives Nesterov’s classical accelerated
gradient descent method for strongly convex functions [31].
4

We assume infinite precision arithmetic in this paper: see discussion in Section 2.2.

6

1:
2:
3:
4:
5:

function Accelerated-gradient-descent(f , y1 , , L1 , σ1 )
Set κ = L1 /σ1 and z1 = y1
for j = 1, 2, . . . do
if k∇f (yj )k ≤  then return yj
end if
1
yj+1 = zj −
∇f (zj )
L1


√
√
κ−1
κ−1
zj+1 = 1 + √
yj+1 − √
yj
κ+1
κ+1

end for
7: end function
6:

The method Accelerated-gradient-descent enjoys the following essentially standard guarantee when initialized at any iterate z1 satisfying f (z1 ) − inf x f (x) ≤ ∆f .
Lemma 2.5. Let f : Rd → R be σ1 > 0-strongly convex and L1 -smooth. Let  > 0 and let zj denote
the jth iterate of Accelerated-gradient-descent(f , z1 , , L1 , σ1 ). If
r
 2 
4L1 ∆f
L1
log
then k∇f (zj )k ≤ .
j ≥1+
σ1
σ1 2
Proof.

Let z ∗ be the minimizer of f . If 2 ≥ 4L21 ∆f /σ1 , then
(i)

(ii)

k∇f (z1 )k2 ≤ L21 kz1 − z ∗ k2 ≤

(iii) 4L2 ∆
2L21
1 f
(f (z1 ) − f (z ∗ )) ≤
≤ 2 ,
σ1
σ1

where inequality (i) follows from smoothness of f (Def. 1), inequality (ii) by the strong convexity
of f (Lemma 2.4), and inequality (iii) by the definition of ∆f . Thus the iteration ends at j = 1.
For smaller , we let κ = L1 /σ1 ≥ 1 denote the condition number for the problem. Then
Nesterov [31, Theorem 2.2.2] shows that for k > 1

k−1
p
1
f (zk ) − f (z ∗ ) ≤ L1 1 − σ1 /L1
kz1 − z ∗ k2 ≤ 2κ exp(−(k − 1)κ− 2 )∆f .
Taking any k ≥ 1 +

√

κ log

4L1 κ∆f
2

yields
f (zk ) − f (z ∗ ) ≤

2
.
2L1

Noting that k∇f (x)k2 ≤ 2L1 (f (x) − f (z ∗ )) by Lemma 2.3, we obtain our result.

2.2

Building block 2: fast eigenvector computation

The final building block we use is accelerated approximate leading eigenvector computation. We
consider two types of approximate eigenvectors. By a relative ε-approximate leading eigenvector
of a positive semidefinite (PSD) matrix H, we mean a vector v such that kvk = 1 and v T Hv ≥
(1 − ε)λmax (H); similarly, an additive ε-approximate leading eigenvector of H satisfies kvk = 1 and
7

v T Hv ≥ λmax (H) − ε. A number of methods compute such (approximate) leading eigenvectors,
including the Lanczos method [23]. For concreteness, we state one lemma here, where in the lemma
we let Thess denote the larger of the times required to compute the matrix-vector product Hv or
to add two vectors.
Lemma 2.6 (Accelerated top eigenvector computation). Let H ∈ Rd×d be symmetric and PSD.
There exists an algorithm that on input ε, δ ∈ (0, 1) runs in O(Thess log(d/δ)ε−1/2 ) time and, with
probability at least 1 − δ, returns a relative ε-approximate leading eigenvector vb.
Notably, the Lanczos method [23, Theorem 3.2] achieves this complexity guarantee. While
Lemma 2.6 relies on infinite precision arithmetic (the stability of the Lanczos method is an active
area of research [34]), shift-and-invert preconditioning [15] also achieves the convergence guarantee to within poly-logarithmic factors in bounded precision arithmetic. This procedure reduces
computing the top eigenvector of the matrix H to solving a sequence of linear systems, and using
fast gradient descent to solve the linear systems guarantees the running time in Lemma 2.6. (See
Section 8 of [15] for the reduction and Theorem 4.1 of [4] for another statement of the result.) For
simplicity—because we do not focus on such precision issues—we use Lemma 2.6 in the sequel.
For later use, we include a corollary of Lemma 2.6 in application to finding minimum eigenvectors
of the Hessian ∇2 f (x) using matrix-vector multiplies. Recalling that f is L1 -smooth, we know that
the matrix M := L1 I − ∇2 f (x) is PSD, and its eigenvalues are {L1 I − λi }di=1 ⊂ [0, 2L1 ], where
λi is the ith eigenvalue of ∇2 f (x). The procedure referenced in Lemma 2.6 (Lanczos or another
accelerated method) applied to the matrix M thus, with probability at least 1 − δ, provides a vector
vb with kb
v k = 1 such that
L1 − vbT ∇2 f (x)b
v = vbT M vb ≥ (1 − ε)λmax (M ) ≥ (1 − ε)(L1 − λmin (∇2 f (x)))
1

in time O(Tgrad ε− 2 log dδ ). Rearranging this, we have
vbT ∇2 f (x)b
v ≤ εL1 + (1 − ε)λmin (∇2 f (x)),
and substituting /(2L1 ) for ε yields the following summarizing corollary.
Corollary 2.7 (Finding the negative curvature). In the setting of the previous paragraph, there
exists an algorithm that given x ∈ Rd computes, with 
probability
 at least 1p− δ, an
 additive 2
approximate smallest eigenvector vb of ∇ f (x) in time O Tgrad 1 + log(d/δ) L1 / .

3

Two structured non-convex problems

With our preliminary results established, in this section we turn to two methods that form the core
of our approach. Roughly, our overall algorithm will be to alternate between finding directions of
negative curvature of f and solving structured sub-problems that are nearly convex, meaning that
the smallest eigenvalue of the Hessian has a lower bound −γ, γ > 0, where γ  L1 . We turn to
each of these pieces in turn.

3.1

Accelerated gradient descent for almost convex functions

The second main component of our general accelerated method is a procedure for finding stationary
points of smooth non-convex functions that are not too non-convex. By not too non-convex, we
mean γ-almost convexity, as in Def. 4, that is, that
γ
f (y) ≥ f (x) + ∇f (x)T (y − x) − kx − yk2 for all x, y,
2
8

where γ ≥ 0. The next procedure applies to such almost convex functions, and builds off of
a suggestion of Nesterov [32] to use regularization coupled with accelerated gradient descent to
improve convergence guarantees for finding a stationary point of f . The idea, as per Lemma 2.4, is
to add a regularizing term of the form γkz − z0 k2 to make the γ-almost convex function f become
γ-strongly convex. As we describe in the sequel, we solve a sequence j = 1, 2, . . . of such proximal
sub-problems
minimize gj (z) := f (z) + γ kz − zj k2
(3)
z

quickly using accelerated gradient descent. Whenever γ  L1 , the regularized model gj of f has
better fidelity to f than the model f (z) + L21 kz − zj k2 (which is essentially what gradient descent
attempts to minimize), allowing us to make greater progress in finding stationary points of f . We
now present the Almost-convex-AGD procedure.
1:
2:
3:
4:
5:
6:
7:
8:
9:

function Almost-convex-AGD(f , z1 , , γ, L1 )
for j = 1, 2, . . . do
if k∇f (zj )k ≤  then return zj
end if
Let gjp
(z) = f (z) + γ kz − zj k2 as in model (3).
0 =  γ/(50(L1 + 2γ))
zj+1 ← Accelerated-gradient-descent(gj , zj , 0 , L1 , γ)
end for
end function
Recalling the definition ∆f ≥ f (z1 ) − inf x f (x), we have the following convergence guarantee.

Lemma 3.1. Let f : Rd → R be be min{σ1 , 0}-almost convex and L1 -smooth. Let γ ≥ σ1 and let
0 < γ ≤ L1 . Then Almost-convex-AGD(f ,z1 ,,γ,L1 ) returns a vector z such that k∇f (z)k ≤ 
and



2
f (z1 ) − f (z) ≥ min γkz − z1 k , √ kz − z1 k
(4)
10
in time
s
!
√

!
L31 ∆f
L1
γL1
+
(f (z1 ) − f (z)) log 2 + 2 2
.
(5)
O Tgrad
γ
2
γ 
Before providing the proof, we remark that the runtime guarantee (5) is an improvement over the
convergence guarantees of standard gradient descent—which scale as O(Tgrad ∆f L1 −2 )—whenever
γ  L1 .
Proof. Because f is −σ1 -strongly convex and γ ≥ σ1 , Lemma 2.4 guarantees that gj is γ-strongly
convex. This strong convexity also guarantees that gj has a unique minimizer, which we denote zj∗ .
Let j∗ be the time at which the routine terminates (we set j∗ = ∞ if this does not occur; our
analysis addresses this case). Let j ∈ [1, j∗ ) ∩ N be arbitrary. We have by Line 7 and Lemma 2.5
2γ
. Moreover, because
(recall that gj is convex and L1 + 2γ smooth) that k∇gj (zj+1 )k2 ≤ L1+2γ
j < j∗ , we have k∇gj (zj )k = k∇f (zj )k ≥  by our termination criterion and definition (3) of gj .
γ
Consequently, k∇gj (zj+1 )k2 ≤ L1 +2γ
k∇gj (zj )k2 , and applying Lemma 2.3 to the (L1 + 2γ)-smooth
and γ-strongly convex function gj yields that
gj (zj+1 ) − gj (zj∗ ) ≤

1
1
k∇gj (zj+1 )k2 ≤
k∇gj (zj )k2 ≤ gj (zj ) − gj (zj∗ ).
2γ
2(L1 + 2γ)
9

Thus we have gj (zj+1 ) ≤ gj (zj ) and
f (zj+1 ) = gj (zj+1 ) − γ kzj+1 − zj k2 ≤ gj (zj ) − γ kzj+1 − zj k2 = f (zj ) − γkzj+1 − zj k2 .
Inducting on the index j, we have
− ∆f ≤ f (zj∗ ) − f (z1 ) ≤ −γ

jX
∗ −1

kzj+1 − zj k2 .

(6)

j=1

Equation (6) shows that to bound the number of iterations of the algorithm
it suffices to lower
q
γ
1
, we have
bound the differences kzj+1 − zj k. Using the condition k∇gj (zj+1 )k ≤  50(L1 +2γ) ≤ 10
kzj+1 − zj k =

1
1 
 
k∇f (zj+1 ) − ∇gj (zj+1 )k ≥
k∇f (zj+1 )k −
,
2γ
2γ
10

where the inequality is a consequence of the triangle inequality. By our termination criterion, we

9
≥ γ√
. Substituting
know that if j + 1 < j∗ then k∇f (zj+1 )k ≥  and therefore kzj+1 − zj k ≥ 20γ
5
this bound into (6) yields
−∆f ≤ f (zj∗ ) − f (z1 ) ≤ −γ

jX
∗ −2

kzj+1 − zj k2 ≤ −(j∗ − 1) ·

j=1

2
5γ

and therefore

5γ
5γ
[f (z1 ) − f (zj∗ )] ≤ 1 + 2 ∆f .
(7)
2


Note that
p the method calls Accelerated-gradient-descent (Line 7) with accuracy parameter 0 =  γ/(50(L1 + 2γ)); using γ ≤ L1 we may apply Lemma 2.5 to bound the running time
of each call by
s
s




!
4(L1 + 2γ)2 ∆f
L31 ∆f
L1 + 2γ
L1
O Tgrad 1 +
log
= O Tgrad
log 2 + 2 2
.
γ
γ(0 )2
γ
γ 
j∗ ≤ 1 +

The method Almost-convex-AGD performs at most j ∗ iterations (Eq. (7)), and combining the
preceding display with this iteration bound yields the running time (5).
All that remains is to prove the progress bound (4). By application of the triangle inequality
and Jensen’s inequality, we have
2


2

∗ −1
jX

kzj ∗ − z1 k ≤ 

∗

kzj+1 − zj k ≤ j ·

j=1

∗ −1
jX

kzj+1 − zj k2 .

j=1

Combing this bound with the earlier progress guarantee (6) yields f (z1 ) − f (zj ∗ ) ≥
and since by (7) either j ∗ ≤ 1 or j ∗ ≤ 10 γ2 [f (z1 ) − f (zj ∗ )] the result follows.

10

γ
∗
j ∗ kzj

− z1 k2 ,

3.2

Exploiting negative curvature

Our first sub-routine either declares the problem locally “almost convex” or finds a direction of f
that has negative curvature, meaning a direction v such that v T ∇2 f (x)v < 0. The idea to make
progress on f by moving in directions of descent on the Hessian is of course well-known, and relies on
the fact that if at a point z the function f is “very” non-convex, i.e. λmin (∇2 f (z)) ≤ −α/2 for some
3
α > 0, then we can reduce the objective significantly (by a constant fraction of L−2
2 α at least) by
2
taking a step in a direction of negative curvature. Conversely, if λmin (∇ f (z)) ≥ −α/2, the function
f is “almost convex” in a neighborhood of z, suggesting that gradient-like methods on f directly
should be effective. With this in mind, we present the routine Negative-curvature-descent,
which, given a function f , initial point z1 , and a few additional tolerance parameters, returns a
vector z decreasing f substantially by moving in Hessian-based directions.
function Negative-curvature-descent(z
1 , f , L2 , α, ∆f , δ)

0
2
3
2:
Set δ = δ/ 1 + 12L2 ∆f /α
3:
for j = 1, 2, . . . do
4:
Find a vector vj such that kvj k = 1 and, with probability at least 1 − δ 0 ,
1:

λmin (∇2 f (zj )) ≥ vjT ∇2 f (zj )vj − α/2

5:

using a leading eigenvector computation
if vjT ∇2 f (zj )vj ≤ −α/2 then
zj+1 ← zj −

6:
7:
8:
9:
10:

. see Corollary 2.7
. Make at least α3 /12L22 progress

2|vjT ∇2 f (zj )vj |
sign(vjT ∇f (zj ))vj
L2
. w.h.p., λmin (∇2 f (zj )) ≥ −α

else
return zj
end if
end for
end function

We provide a formal guarantee for the method Negative-curvature-descent in the following
lemma. Before stating the lemma, we recall that f : Rd → R has L2 -Lipschitz Hessian and that
∆f ≥ f (z1 ) − inf x f (x).
Lemma 3.2. Let the function f : Rd → R be L1 -smooth and have L2 -Lipschitz continuous Hessian,
α > 0, 0 < δ < 1 and z1 ∈ Rd . If we call Negative-curvature-descent(z1 , f , L2 , α, ∆f , δ)
then the algorithm terminates at iteration j for some
j ≤1+

12L22 ∆f
12L22 (f (z1 ) − f (zj ))
≤
1
+
,
α3
α3

(8)

and with probability at least 1 − δ
λmin (∇2 f (zj )) ≥ −α.
Furthermore, each iteration requires time at most
"
r
 
#!
L22 ∆f
L1
d
O Tgrad 1 +
log
1 + 12 3
.
α
δ
α
11

(9)

(10)

Proof.

Assume that the method has not terminated at iteration k. Let
ηk =

2|vkT ∇2 f (zk )vk |
sign(vkT ∇f (zk ))
L2

denote the step size used at iteration k, so that zk+1 = zk − ηk vk as in Line 5. By the L2 -Lipschitz
continuity of the Hessian, we have
1
L2
|f (zk − ηk vk ) − f (zk ) + ηk vkT ∇f (zk ) − ηk2 vkT ∇2 f (zk )vk | ≤
kηk vk k3 .
2
6
Noting that ηk vkT ∇f (zk ) ≥ 0 by construction, we rearrange the preceding inequality to obtain


ηk2 L2
2|v T ∇2 f (zk )vk |3 (i)
α3
T 2
≤
−
,
f (zk+1 ) − f (zk ) ≤
|ηk | + vk ∇ f (zk )vk = − k
2
3
3L22
12L22
where inequality (i) uses that |vkT ∇2 f (zk )vk | > α/2, as the stopping criterion has not been met.
Telescoping the above equation for k = 1, 2, . . . , j − 1, we conclude that at the final iteration
∆f ≥ f (z1 ) − f (zj ) ≥

α3
(j − 1) ,
12L22

which gives the bound (8).
We turn to inequality (9). Recall the definition of δ 0 =
δ0

δ
,
1+12L22 ∆f /α3

which certainly satisfies

≤ δ/j if j is the final iteration of the algorithm (as the bound (8) is deterministic). Now, at
the last iteration, we have by definition of the final iterate that vjT ∇2 f (zj )vj ≥ − α2 , and thus, if vj
is an additive α/2-approximate smallest eigenvector, we have λmin (∇2 f (zj )) ≥ vjT ∇2 f (zj )vj − α.
Applying a union bound, the probability that the approximate eigenvector method fails to return
an α/2-approximate eigenvector in any iteration is bounded by δ 0 j ≤ δ, giving the result.
Finally, equation (10) is immediate by Corollary 2.7.

4

An accelerated gradient method for non-convex optimization

Now that we have provided the two subroutines Negative-curvature-descent and Almostconvex-AGD, which (respectively) find directions of negative curvature and solve nearly convex
problems, we combine them carefully to provide an accelerated gradient method for smooth nonconvex optimization. The idea behind our Accelerated-non-convex-method is as follows. At
the beginning of each iteration k we use Negative-curvature-descent to make progress until
we reach a point x
bk where the function is almost convex (Def. 4) in a neighborhood of the current
iterate. For a parameter α ≥ 0, we define the convex penalty


α 2
ρα (x) := L1 kxk −
,
(11)
L2 +
where [t]+ = max{t, 0}. We then modify the function f (x) by adding the penalty ρα and defining
fk (x) = f (x) + ρα (x − x
bk ).
The function fk (x) is globally almost convex, as we show in Lemma 4.1 to come, so that the
method Almost-convex-AGD applied to the function fk (x) quickly reduces the objective f .
12

We trade between curvature minimization and accelerated gradient using the parameter α in the
definition (11) of ρ, which governs acceptable levels of non-convexity. By carefully choosing α, the
e −7/4 ), which we we prove in Theorem 4.3.
combined method has convergence rate O(
Algorithm 1 Acceleration of smooth non-linear optimization
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:

4.1

function Accelerated-non-convex-method(x
1 , f , , L1 , L2 , α, ∆f , δ)
√
Set K := d1 + ∆f (12L22 /α3 + 10L2 /(α))e and δ 00 := Kδ
for k = 1, 2, . . . do
if α < L1 then
x
bk ← Negative-curvature-descent(xk , f , L2 , α, ∆f , δ 00 )
else
x
bk ← xk
end if
if k∇f (b
xk )k ≤  then
return x
bk
. guarantees w.h.p., λmin (∇2 f (b
xk )) ≥ −2α
end if
2
Set fk (x) = f (x) + L1 [kx − x
bk k − α/L2 ]+
xk+1 ← Almost-convex-AGD(fk , x
bk , /2, 3α, 5L1 )
end for
end function

Preliminaries: convexity and iteration bounds

Before coming to the theorem giving a formal guarantee for Accelerated-non-convex-method,
we provide two technical lemmas showing that the internal subroutines are well-behaved. The first
lemma confirms that the regularization technique (11) transforms a locally almost convex function
into a globally almost convex function (Def. 4), so we can efficiently apply Almost-convex-AGD
to it.
Lemma 4.1. Let f be L1 -smooth and have L2 -Lipschitz continuous Hessian. Let x0 ∈ Rd be such
that ∇2 f (x0 )  −αI for some α ≥ 0. The function fα (x) := f (x) + ρα (x − x0 ) is 3α-almost convex
and 5L1 -smooth.
Proof. It is clear that ρ = ρα is convex, as it is an increasing convex function of a positive
argument [9, Chapter 3.2]. We claim that ρ is 4L1 -smooth. Indeed, the gradient


x
α
∇ρ(x) = 2L1
kxk −
kxk
L2 +
is continuous by inspection and differentiable except at kxk = Lα2 . For kxk < α/L2 , we have
∇2 ρ(x) = 0, and for kxk > α/L2 we have



α xxT
I
2
∇ ρ(x) = 2L1 I +
−
,
(12)
L2 kxk3 kxk
which satisfies 0  ∇2 ρ(x)  4L1 I for all x. As ∇ρ(x) is continuous, we conclude that ρ is
4L1 -smooth. The L1 -smoothness of f then implies that the sum f (x) + ρ(x − x0 ) is 5L1 smooth.
To argue almost convexity of f + ρ, we show that ∇2 f (x) + ∇2 ρ(x − x0 )  −3αI almost
everywhere, which is equivalent to Definition 4 when the gradient is continuous. For kx − x0 k <
13

2α/L2 , we have by Lipschitz continuity of ∇2 f that
∇2 f (x)  ∇2 f (x0 ) − L2 kx − x0 kI  −3αI,
which implies the result because ρ is convex. For kx − x0 k > 2α/L2 , inspection of the Hessian (12)
shows that ∇2 ρ(x − x0 )  L1 I. Since ∇2 f (x)  −L1 I almost everywhere by the L1 -smoothness of
f , we conclude that ∇2 f (x) + ∇2 ρ(x − x0 )  0 whenever ∇2 f (x) exists.
The next lemma provides a high probability guarantee on the correctness and number of iterations of Accelerated-non-convex-method. (There is randomness in the eigenvector computation subroutine invoked within Negative-curvature-descent.) As always, we let ∆f ≥
f (x1 ) − inf x f (x).
Lemma 4.2. Let f be L1 -smooth with L2 -Lipschitz continuous Hessian,  > 0, δ ∈ (0, 1), and α ∈
[0, L1 ]. Then with probability at least 1 − δ, the method Accelerated-non-convex-method(x1 ,
f , , L1 , L2 , α, ∆f , δ) terminates after t iterations with k∇f (b
xt )k ≤ , where t satisfies
 2 √

(
12L
2
2 + ∆f α3 2 + 10L
if α < L1
α
t≤
(13)
16L1
if α = L1
2 + ∆f 32
Further, λmin (∇2 f (b
xk )) ≥ −2α for all k ≤ t.
Proof. Before beginning the proof proper, we provide a quick bound on the size of the difference
between iterates x
bk and x
bk−1 , which will imply progress in function values across iterations of
Alg. 1. In each iteration that the convergence criterion k∇f (b
xk )k ≤  is not met—that is, whenever
k∇f (b
xk )k > —we have that


(i)
(ii) 
α
 ≤ k∇f (b
xk )k ≤ k∇fk−1 (b
xk )k + k∇ρ(b
xk − x
bk−1 )k ≤ + 2L1 kb
xk − x
bk−1 k −
.
2
L2 +
In inequality (i) we used the triangle inequality and definition of fk−1 = f + ρ(· − xk−1 ) and
inequality (ii) used that the call to Almost-convex-AGD returns x
bk with k∇fk−1 (xk )k ≤ /2.
Rearranging yields



α
α
= kb
xk − x
bk−1 k −
≤ kb
xk − x
bk−1 k −
,
(14)
4L1
L2 +
L2
where the equality is implied because  > 0.
Now we consider two cases, the first the simpler case that α = L1 is large enough that we never
search for negative curvature, and the second that α < L1 so that we find directions of negative
curvature in the method.
Case 1: large α In this case, we have that α = L1 , so that xk = x
bk for all iterations k (Line 7 of
the algorithm). Assume that at iteration k that the algorithm has not terminated, so k∇f (b
xk )k ≥ .
Then inequality (14) gives 4L 1 < kb
xk − x
bk−1 k. By Lemma 4.1 we know that fk is 3L1 -almost convex
(Def. 4) and 5L1 -smooth; therefore we may apply Lemma 3.1 with γ = 3α = 3L1 to lower bound
the progress of the call to Almost-convex-AGD in Line 13 of Alg. 1 to obtain



2
f (b
xk−1 ) − f (b
xk ) ≥ min 3L1 kb
xk−1 − x
bk k , √ kb
xk−1 − x
bk k
10


2
2
2
≥ min 3
, √
≥
.
(15)
16L1 4 10L1
16L1
14

Telescoping this display, we have for any iteration s at which the algorithm has not terminated
that
s
X
32
∆f ≥
f (b
xk−1 ) − f (b
xk ) ≥ (s − 1)
16L1
k=2

which yields the second case of the bound (13). The inequality ∇2 f (b
xj )  −2αI holds trivially
because f is L1 -smooth.
12L2

√

2
Case 2: small α In this case, we assume that α < L1 . Let K = d1 + ∆f ( α3 2 + 10L
α )e and
δ
00
δ = K as in line 2 of Alg. 1. By Lemma 3.2 and a union bound, with probability at least 1 − δ,
for all k ≤ K the matrix inequality ∇2 f (b
xk )  −2αI holds, so that we perform our subsequent
analysis (for k ≤ K) conditional on this event without appealing to any randomness.
Equation (14) implies that at iteration 1 < k ≤ K exactly one of following three cases is true:

(i) The termination criterion k∇f (b
xk )k ≤  holds and Alg. 1 terminates.
(ii) Negative-curvature-descent (Line 5) constructs x
bk 6= xk , and (i) fails.
(iii) Neither (i) nor (ii) holds, and kb
xk − x
bk−1 k ≥ α/L2 .
We claim that in case (ii) or (iii), we have

f (b
xk−1 ) − f (b
xk ) ≥ min

α
α3
√ ,
L2 10 12L22


.

(16)

Deferring the proof of claim (16), we note that it immediately gives a quick proof of the result.
Assume, in order to obtain a contradiction that after K iterations the algorithm has not terminated
it follows that:


K
X
α3
α
√ ,
∆f ≥ f (b
x1 ) − f (b
xK ) =
f (b
xk ) − f (b
xk+1 ) ≥ (K − 1) min
,
12L22
L
10
2
k=2
12L2

√

2
Substituting for K = d1 + ∆f ( α3 2 + 10L
α )e as in line 2 yields a contradiction and therefore the
algorithm terminates after at most K iterations which is the first case of the bound (13).
Let us now prove the claim (16). First, assume case (ii). Then Negative-curvature-descent
requires at least two iterations, so Lemma 3.2 implies

xk ))
12L22 (f (xk ) − f (b
≥ 1.
3
α
Combining this with the fact that f (xk ) ≤ f (b
xk−1 ) by the progress bound (4) in Lemma 3.1
(Almost-convex-AGD decreases function values), we have
f (b
xk−1 ) − f (b
xk ) ≥ f (xk ) − f (b
xk ) ≥

α3
.
12L22

Let us now consider the case that (iii) holds. By Lemma 4.1 we know that the constructed function
fk is 3α-almost convex (Def. 4) and 5L1 -smooth, therefore we may apply Lemma 3.1 with γ = 3α
to lower bound the progress of the entire inner loop of Alg. 1 by


 3


3α
α
2
√
√
f (b
xk−1 ) − f (b
xk ) ≥ min γkb
xk−1 − xk k ,
kb
xk−1 − xk k ≥ min
,
L22 L2 10
10
as desired.

15

4.2

Main result

With Lemmas 4.1 and 4.2 in hand, we may finally present our main result.
Theorem 4.3. Let f : Rd → R be L1 -smooth and have L2 -Lipschitz continuous Hessian. Let
n
n
oo
1/2 1/2
α = min L1 , max 2 ∆−1
,

L
2
f
and δ ∈ (0, 1). Then with probability at least 1 − δ, Accelerated-non-convex-method(x1 , f ,
, L1 , L2 , α, ∆f , δ) returns a point x that satisfies
1/2

k∇f (x)k ≤  and λmin (∇2 f (x)) ≥ −21/2 L2
in time





1/2 1/4
1/2 1/2
O Tgrad ∆f L1 L2 −7/4 + ∆f L1 −1 + 1 log τ ,
where τ = 1 + 1/ + 1/δ + d + L1 + L2 + ∆f .
2

Proof. We split this proof into two cases: (I) small alpha when α < L1 and hence α = ∆ f or
√
L2 , this is the non-trivial case requiring solution to a reasonably small accuracy; and (II) when
α = L1 , when the algorithm is roughly equivalent to gradient descent (and  is large enough that
we do not require substantial accuracy).
Case I: Small α We proceed in two steps. First, we bound the number of eigenvector calculations
that Negative-curvature-descent performs by providing a progress guarantee for each of them
using Lemma 3.2 and arguing that making too much progress is impossible. After this, we perform
a similar calculation for the total number of gradient calculations throughout calls to Almostconvex-AGD, this time applying Lemma 3.1.
We begin by bounding the number of eigenvector calculations. When α < L1 , its defi1/2 1/2
nition implies  ≤ min{L21 /L2 , ∆f L1 }. Let jk∗ be the total number of times the method
Negative-curvature-descent invokes the eigenvector computation subroutine (Line 4 of Negativecurvature-descent) during iteration k of the method Accelerated-non-convex-method,
let k ∗Pdenote the total number of iterations of Accelerated-non-convex-method, and define
∗
q := kk=1 jk∗ as the total number of eigenvector computations. Then by telescoping the bound (8)
in Lemma 3.2 and using that f (xk ) ≤ f (b
xk−1 ) by the progress bound (4) in Lemma 3.1 (Almostconvex-AGD decreases function values), we have
∗

∗

∗

k
k
k
X
X
X
12∆f L22
12L22
12L22
∗
(jk − 1) ≤
(f
(x
)
−
f
(b
x
))
≤
(f
(b
x
)
−
f
(b
x
))
≤
.
k
k
k−1
k
α3
α3
α3
k=1

k=1

k=1

Substituting the bound on k ∗ that Lemma 4.2 supplies, we see that with probability at least 1 − δ,
!
√
12∆f L22
24L22
10L2 (i)
1/2
∗
q≤
+ k ≤ 1 + ∆f
+
≤ 1 + 28∆f L2 −3/2 ,
(17)
α3
α3
α
1/2

where inequality (i) follows by our construction that α ≥ 1/2 L2 . Inequality (17) thus provides a
bound on the total number of fast eigenvector calculations we require.

16

We use the bound (17) to bound the total cost of calls to Negative-curvature-descent.
The tolerated failure probability δ 00 defined in line 2 satisfies
1 + ∆f (12L22 /α3 +
1
=
δ 00
δ

√

10L2 /(α))

1/2

≤

1 + 16∆f L2 −3/2
,
δ

(10), the cost of each iteration during Negativeso that log δ100 = O(log τ ). By Lemma 3.2, Eq.
−1 √
2
curvature-descent is, using max{ ∆f , L2 } = α < L1 , at most
"
O Tgrad 1 +

r

L1
log
α





#!
1

2 ∆ 
2
12L
d
L1
2 f
.
1+
= O Tgrad
1 log τ
1
δ 00
α3
2
4
(L2 ) ∨ (∆f )

Multiplying this time complexity by q as bounded in expression (17) gives that the total cost of
the calls to Negative-curvature-descent is




1/2 1/4
1/2 1/2
(18)
O Tgrad ∆f L1 L2 −7/4 + L1 ∆f −1 log τ .
We now compute the total cost of calling Almost-convex-AGD. Using the time bound (5)
of Lemma 3.1, the cost of calling Almost-convex-AGD in iteration k with almost convexity
parameter γ = 3α is bounded by the sum of
s
!
√


L1
γL1
log τ
and O Tgrad 2 [fk (xk ) − fk (xk+1 )] log τ .
(19)
O Tgrad
γ

We separately bound the total computational cost of each of the terms (19).
1/2

16L

2
Using the bound k ∗ ≤ 1 + ∆f 3/2
as in expression (17) for the total number of iterations of
Alg. 1, we see that the first of the time bounds (19) yields identical total cost to the eigenvector
√
1
1
computations (18), because γ − 2 = O(α− 2 ) = O(1/ 4 L2 ). Thus we consider the second term in
expression (19). Using the fact that [fk (xk ) − fk (xk+1 )] ≤ [f (xk ) − f (xk+1 )] by definition of xk+1
and the method Almost-convex-AGD, we telescope to find
∗

∗

k
k
X
X
[fk (xk ) − fk (xk+1 )] ≤
[f (xk ) − f (xk+1 )] ≤ ∆f .
k=1

k=1

p
√
Noting that by assumption that the almost convexity parameter γ = 3α, we have γ/3 = α ≤
1/4
−1/2
L2 1/4 + ∆f , telescoping the second term of the bound (19) on the cost of Almost-convexAGD immediately gives the total computational cost bound
!
!
1/2
∆f L1

1/4 1/4
L2  + p
log τ
O Tgrad
2
∆f
over all calls of Almost-convex-AGD. This is evidently our desired result that the total computational cost when α < L1 is (18).
Case II: Large α When α = L1 , the algorithm becomes roughly equivalent to gradient descent,
because Negative-curvature-descent is not required, so that we need only bound the total
computational cost of calls to Almost-convex-AGD. The bound (19) on the computational
17

effort of each such call again applies, and noting that L1 = α = 3γ in this case, we replace the
bounds (19) with the two terms


L1
O(Tgrad log τ ) and O Tgrad 2 [f (xk ) − f (xk+1 )] log τ .

As in Case I, we may telescope the second time bound to obtain total computational effort
O(Tgrad (1 + ∆f L21 ) log τ ), while applying the iteration bound (13) of Lemma 4.2 to the first
term similarly yields the bound O(Tgrad (1 + ∆f L21 ) log τ ) on the total computational cost. To
conclude the proof we observe that α = L1 implies L1 ≤ max{(L2 )1/2 , 2 /∆f } and that L1 ≤
1/2
max{(L2 )1/4 L1 , 2 /∆f }. Therefore,
!
!




1/2 1/4
∆f L1 L2
L1
log τ ,
O Tgrad 1 + ∆f 2 log τ = O Tgrad 1 +

7/4
which gives our desired total time.
We provide a bit of discussion to help explicate this result. Much of the complication in
the statement of Theorem 4.3 is a consequence of our desire for generality in possible parameter
values. In common settings in which points reasonably close to stationarity are desired—when the
accuracy  is small enough—we may simplify the theorem substantially, as the following corollary
demonstrates.
q
Corollary 4.4. Let the conditions of Theorem 4.3 hold, and in addition assume that  ≤ 3 ∆2f /L2 .
Then the total computational cost of Alg. 1 is at most
!
1/2 1/4
L
L
1
2
e Tgrad ∆f
O
.
7/4
To elucidate the relative importance of acceleration in the approximate eigenvector or gradient
descent computation in Accelerated-non-convex-method, we may also consider replacing
them with (respectively) the power method (rather than the Lanczos method) or standard gradient
descent. We first consider the accelerated (approximate) eigenvector routine. With probability at
least 1 − δ, the power method finds an α-additive approximate maximum or minimum eigenvector
of the matrix ∇2 f (x) ∈ Rd×d , with operator norm bounded as ∇2 f (x) ≤ L1 , in time O( Lα1 log dδ )
(compare this with Corollary 2.7). In this case, substituting α  4/9 , rather than α  1/2 in
Theorem 4.3, and mimicking the preceding proof yields total time complexity of order −16/9  −2 ,
ignoring all other problem-dependent constants. That is, non-accelerated eigenvector routines can
still yield faster than −2 rates of convergence.
Conversely, it appears
that accelerated gradient descent is more central to our approach. Indeed,
√
the term involving γL1 in the bound (13) is important, as it allows us to carefully trade “almost”
convexity γ with accuracy  to achieve fast rates of convergence. Replacing the accelerated gradient
descent method with gradient descent in Almost-convex-AGD eliminates the possibility for
such optimal trading. Of course, our procedure would still produce output with the second order
1/2
guarantee ∇2 f (x)  −21/2 L2 Id×d .

18

5

Accelerated (linear) convergence to local minimizers of strictsaddle functions

In this section, we show how to apply Accelerated-non-convex-method and Theorem 4.3 to
find local minimizers for generic non-pathological
smooth optimization problems with linear rates of convergence. Of course, it is in general NP-hard
to even check if a point is a local minimizer of a smooth nonconvex optimization problem [27, 30],
so we require a few additional assumptions in this case. In general, second-order stationary points
need not be local minima; consequently, we consider strict-saddle functions, which are functions
such that all eigenvalues of the Hessian are non-zero at all critical points, so that second-order
stationary points are indeed local minima. Such structural assumptions have been important in
recent work on first-order methods for general smooth minimization [24, 17, 41], and in a sense
“random” functions generally satisfy these conditions (cf. the discussion of Morse functions in the
book [1]). To make our discussion formal, consider the following quantitative definition.
Definition 6. A twice differentiable function f : Rd → R is (ε, σ− , σ+ )-strict-saddle if for any
point x such that k∇f (x)k ≤ ε, λmin (∇2 f (x)) ∈ (−∞, σ− ] ∪ [σ+ , ∞).
Some definitions of strict-saddle include a radius R bounding the distance between any point x
satisfying k∇f (x)k ≤ ε and λmin (∇2 f (x)) ≥ σ+ and a local minimizer x+ of f , and they assume
that f is σ+ -strongly convex in a ball of radius 2R around any local minimizer. Our assumption
on the Lipschitz continuity of ∇2 f obviates the need for such conditions, allowing the following
simplified definition.
Definition 7. Let f : Rd → R have L2 -Lipschitz continuous Hessian. We call f σ1 -strict-saddle if
it is (σ12 /L2 , σ1 , σ1 )-strict-saddle.
With this definition in mind, we present Algorithm 2, which leverages Algorithm 1 to obtain
linear convergence (in the desired accuracy ) to a local minimizer of strict-saddle functions. The
algorithm proceeds in two phases, first finding a region of strong convexity, and in the second
phase solving a regularized version of resulting locally convex problem in this region. That the first
phase of Alg. 2 terminates in a neighborhood of a local optimum of f , where f is convex in this
neighborhood, is an immediate consequence of the strict-saddle property coupled with the gradient
and Hessian bounds of Theorem 4.3. We can then apply (accelerated) gradient descent to quickly
find the local optimum, which we describe rigorously in the following theorem.
Theorem 5.1. Let f : Rd → R be L1 -smooth, have L2 -Lipschitz continuous Hessian, and be
σ1 -strict-saddle. Let  ≥ 0 and δ ∈ (0, 1). With probability at least 1 − δ, Accelerated-strictsaddle-method(x1 , f , , L1 , L2 , σ1 , ∆f , δ) returns a point x that satisfies k∇f (x)k ≤  in
time
#!
"r


1/2 2
L
L
∆
L1
1
f
O Tgrad
log τ 0 +
+ 1 7/22
log τ 0
,
σ1

σ
1

where τ 0 = 1 + L1 /σ1 + 1/δ + d + L2 + ∆f . When  ≤
a local minimizer x?+ of f such that
x − x?+ ≤

σ12
16L2 ,

with the same probability there exists

2
2L1 2
and f (x) − f (x?+ ) ≤
.
σ1
σ12
19

(20)

Algorithm 2 Acceleration of smooth strict-saddle optimization
1:
2:
3:
4:
5:
6:

function Accelerated-strict-saddle-method(x1 , f , , L1 , L2 , σ1 , ∆f , δ)
Phase one
n
o
σ2
Set ε = max , 16L1 2
n
n
oo
1/2 L1/2
Set α = min L1 , max ε2 ∆−1
,
ε
. as in Theorem 4.3
2
f
x+ ← Accelerated-non-convex-method(x1 , f, ε, L1 , L2 , α, ∆f , δ)
Phase two:
if  < ε then
. non-trivial case
h
i2
σ1
Set f+ (x) = f (x) + L1 kx − x+ k − 4L2
+

7:
8:
9:
10:
11:

return Accelerated-gradient-descent(f+ , x+ , , 5L1 , σ1 /2)
else
return x+
end if
end function

Proof.

The result in the low accuracy regime in which  >
σ12
16L2 .

σ12
16L2

is immediate by Theorem 4.3,

We perform our analysis conditional on the event,
and we therefore focus on the case that  ≤
which holds with probability at least 1 − δ, that the guarantees of Theorem 4.3 hold. That is, that
x+ generated in Line 4 satisfies
k∇f (x+ )k ≤
and that it is computed in time

T1 =
(i)

σ12
σ1
and ∇2 f (x+ )  − I,
16L2
4



1/2
L1 L22 ∆f



O Tgrad
7/2
σ1

r

= O Tgrad

1/2

+

1/2

L1 L2 ∆f
σ12
!



L1 L22 ∆f
+ 1 log τ 0
σ1
σ13



(21)



+ 1 log τ 0 

,

where
τ 0 is as in the theorem statement. Equality (i) is a consequence of the inequalities 1 ≤
p
L1 /σ1 and 1 + a + a2 = O(1 + a2 ) for a ≥ 0.
In conjunction with Definition 7, the bounds (21) imply that ∇2 f (x+ )  σ1 I. Recalling
Lemma 4.1, and the bound (12) from its proof, a trivial calculation involving the Lipschitz continuity
of ∇2 f shows that f+ (x) = f (x) + L1 [kx − x+ k − σ1 /4L2 ]2+ is σ1 /2-strongly convex. Additionally,
we have immediately that f+ is 5L1 -smooth.
Let x?+ be the unique global minimizer of f+ . By the strong convexity of f+ , we may bound
the distance between x+ and x?+ (recall Lemma 2.3) by
x+ − x?+ ≤

2 k∇f+ (x+ )k
2 k∇f (x+ )k
σ1
=
≤
,
σ1
σ1
8L2

where final inequality is immediate from the gradient bound (21). By construction, f+ = f on the
ball {x : kx − x+ k ≤ σ1 /4L2 }, and as x?+ belongs to the interior of this ball, it is a local minimizer
of f .

20

Let x be the point produced by the call to Accelerated-gradient-descent. By Lemma 2.5,
x satisfies k∇f+ (x)k ≤  and is computed in time
r
r



!
200L21 ∆f
10L1
L1
1
log
= O Tgrad
log τ 0 +
.
T2 := Tgrad + Tgrad
σ1
σ1 2
σ1

The strong convexity of f+ once more (Lemma 2.3) implies
x − x?+ ≤

k∇f+ (x)k
2
σ1
≤
≤
,
σ1 /2
σ1
8L2

σ1
which gives the distance bound in expression (20). Combining x − x?+ ≤ 8L
and x+ − x?+ ≤
2
σ1
σ1
8L2 , we have that kx − x+ k ≤ 4L2 , and therefore f (x) = f+ (x) and k∇f (x)k = k∇f+ (x)k ≤ .
The functional bound (20) then follows from the L1 -smoothness of f and that ∇f (x?+ ) = 0, as

f (x) − f (x?+ ) ≤ ∇f (x?+ )T (x − x?+ ) +

L1
x − x?+
2

2

=

L1
x − x?+
2

2

.

The running time guarantee follows by summing T1 and T2 above.

Acknowledgment
OH was supported by the PACCAR INC fellowship. YC and JCD were partially supported by the
SAIL-Toyota Center for AI Research. YC was partially supported by the Stanford Graduate Fellowship and the Numerical Technologies Fellowship. JCD was partially supported by the National
Science Foundation award NSF-CAREER-1553086

21

References
[1] R. J. Adler and J. E. Taylor. Random fields and geometry. Springer, 2009.
[2] N. Agarwal, Z. Allen-Zhu, B. Bullins, E. Hazan, and T. Ma. Finding local minima for nonconvex optimization in linear time. arXiv preprint arXiv:1611.01146, 2016.
[3] Z. Allen-Zhu and E. Hazan. Variance reduction for faster non-convex optimization. arXiv
preprint arXiv:1603.05643, 2016.
[4] Z. Allen Zhu and Y. Li. Even faster SVD decomposition yet without agonizing pain. arXiv
preprint arXiv:1607.03463, 2016. URL http://arxiv.org/abs/1607.03463.
[5] Z. Allen-Zhu and L. Orecchia. Linear coupling: An ultimate unification of gradient and mirror
descent. arXiv preprint arXiv:1407.1537, 2014.
[6] A. Anandkumar and R. Ge. Efficient approaches for escaping higher order saddle points in
non-convex optimization. arXiv preprint arXiv:1602.05908, 2016.
[7] T. Bianconcini, G. Liuzzi, B. Morini, and M. Sciandrone. On the use of iterative methods in
cubic regularization for unconstrained optimization. Computational Optimization and Applications, 60(1):35–57, 2015.
[8] E. Birgin, J. Gardenghi, J. Martınez, S. Santos, and P. L. Toint. Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models. Report
naXys-05-2015, University of Namur, Belgium, 2015.
[9] S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
[10] S. Bubeck, Y. T. Lee, and M. Singh. A geometric alternative to Nesterov’s accelerated gradient
descent. arXiv preprint arXiv:1506.08187, 2015.
[11] Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford. Accelerated methods for non-convex
optimization. arXiv:1611.00756 [math.OC], 2016.
[12] C. Cartis, N. I. Gould, and P. L. Toint. Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results. Mathematical
Programming, 127(2):245–295, 2011.
[13] A. Defazio, F. Bach, and S. Lacoste-Julien. SAGA: A fast incremental gradient method with
support for non-strongly convex composite objectives. In Advances in Neural Information
Processing Systems 27, 2014.
[14] R. Frostig, R. Ge, S. M. Kakade, and A. Sidford. Un-regularizing: approximate proximal point
and faster stochastic algorithms for empirical risk minimization. In Proceedings of the 32nd
International Conference on Machine Learning (ICML), 2015.
[15] D. Garber, E. Hazan, C. Jin, S. M. Kakade, C. Musco, P. Netrapalli, and A. Sidford. Faster eigenvector computation via shift-and-invert preconditioning. arXiv preprint
arXiv:1605.08754, 2016.
[16] D. Ge, X. Jiang, and Y. Ye. A note on the complexity of lp minimization. Mathematical
programming, 129(2):285–299, 2011.
22

[17] R. Ge, F. Huang, C. Jin, and Y. Yuan. Escaping from saddle points—online stochastic gradient
for tensor decomposition. In Proceedings of The 28th Conference on Learning Theory, pages
797–842, 2015.
[18] S. Ghadimi and G. Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic
programming. SIAM Journal on Optimization, 23(4):2341–2368, 2013.
[19] S. Ghadimi and G. Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic
programming. Mathematical Programming, 156(1-2):59–99, 2016.
[20] E. Hazan and T. Koren. A linear-time algorithm for trust region problems. Mathematical
Programming, 158(1):363–381, 2016.
[21] N. Ho-Nguyen and F. Kılınc-Karzan. A second-order cone based approach for solving the
trust-region subproblem and its variants. arXiv preprint arXiv:1603.03366, 2016.
[22] R. Johnson and T. Zhang. Accelerating stochastic gradient descent using predictive variance
reduction. In Advances in Neural Information Processing Systems 26, 2013.
[23] J. Kuczynski and H. Wozniakowski. Estimating the largest eigenvalue by the power and
lanczos algorithms with a random start. SIAM journal on matrix analysis and applications,
13(4):1094–1122, 1992.
[24] J. D. Lee, M. Simchowitz, M. I. Jordan, and B. Recht. Gradient descent only converges to
minimizers. In 29th Annual Conference on Learning Theory (COLT), pages 1246—1257, 2016.
[25] H. Li and Z. Lin. Accelerated proximal gradient methods for nonconvex programming. In
Advances in Neural Information Processing Systems 28, pages 379–387, 2015.
[26] H. Lin, J. Mairal, and Z. Harchaoui. A universal catalyst for first-order optimization. In
Advances in Neural Information Processing Systems, pages 3384–3392, 2015.
[27] K. Murty and S. Kabadi. Some NP-complete problems in quadratic and nonlinear programming. Mathematical Programming, 39:117–129, 1987.
[28] A. Nemirovski and D. Yudin. Problem Complexity and Method Efficiency in Optimization.
Wiley, 1983.
[29] Y. Nesterov. A method of solving a convex programming problem with convergence rate
O(1/k 2 ). Soviet Mathematics Doklady, 27(2):372–376, 1983.
[30] Y. Nesterov. Squared functional systems and optimization problems. In High Performance
Optimization, volume 33 of Applied Optimization, pages 405–440. Springer, 2000.
[31] Y. Nesterov. Introductory Lectures on Convex Optimization. Kluwer Academic Publishers,
2004.
[32] Y. Nesterov. How to make the gradients small. Optima 88, 2012.
[33] Y. Nesterov and B. T. Polyak. Cubic regularization of Newton method and its global performance. Mathematical Programming, 108(1):177–205, 2006.
[34] L. Orecchia, S. Sachdeva, and N. K. Vishnoi. Approximating the exponential, the lanczos
method and an o (m)-time spectral algorithm for balanced separator. In Proceedings of the
forty-fourth annual ACM symposium on Theory of computing, pages 1141–1160. ACM, 2012.
23

[35] N. Parikh, S. P. Boyd, et al. Proximal algorithms. Foundations and Trends in optimization, 1
(3):127–239, 2014.
[36] B. A. Pearlmutter. Fast exact multiplication by the Hessian. Neural computation, 6(1):147–160,
1994.
[37] S. J. Reddi, A. Hefny, S. Sra, B. Póczós, and A. Smola. Stochastic variance reduction for
nonconvex optimization. arXiv preprint arXiv:1603.06160, 2016.
[38] R. T. Rockafellar and R. J. B. Wets. Variational Analysis. Springer, New York, 1998.
[39] N. N. Schraudolph. Fast curvature matrix-vector products for second-order gradient descent.
Neural computation, 14(7):1723–1738, 2002.
[40] S. Shalev-Shwartz and T. Zhang. Accelerated proximal stochastic dual coordinate ascent for
regularized loss minimization. In ICML, pages 64–72, 2014.
[41] J. Sun, Q. Qu, and J. Wright. When are nonconvex problems not scary? arXiv:1510.06096
[math.OC], 2015.
[42] V. V. Williams. Multiplying matrices faster than Coppersmith-Winograd. In Proceedings of
the forty-fourth annual ACM symposium on Theory of computing, pages 887–898. ACM, 2012.
[43] Y. Ye. On the complexity of approximating a KKT point of quadratic programming. Mathematical Programming, 80(2):195–211, 1998.

24

