Finding Approximate Local Minima
Faster than Gradient Descent

arXiv:1611.01146v4 [math.OC] 24 Apr 2017

Naman Agarwal

Zeyuan Allen-Zhu

Brian Bullins

namana@cs.princeton.edu

zeyuan@csail.mit.edu

bbullins@cs.princeton.edu

Princeton University

Institute for Advanced Study

Princeton University

Elad Hazan

Tengyu Ma

ehazan@cs.princeton.edu

tengyu@cs.princeton.edu

Princeton University

Princeton University

November 3, 2016
Abstract
We design a non-convex second-order optimization algorithm that is guaranteed to return
an approximate local minimum in time which scales linearly in the underlying dimension and
the number of training examples. The time complexity of our algorithm to find an approximate
local minimum is even faster than that of gradient descent to find a critical point. Our algorithm
applies to a general class of optimization problems including training a neural network and other
non-convex objectives arising in machine learning.

1

Introduction

Finding a global minimizer of a non-convex optimization problem is NP-hard. Thus, the standard
goal of efficient non-convex optimization algorithms is instead to find a local minimum. This
problem has become increasingly important as the state-of-the-art in machine learning is attained
by non-convex models, many of which are variants of deep neural networks. Experiments in [10,
11, 21] suggest that fast convergence to a local minimum is sufficient for training neural nets, while
convergence to critical points (points with vanishing gradients) is not. Theoretical works have also
affirmed the same phenomenon for other machine learning problems (see [5, 6, 18, 19] and the
references therein).
In this paper we give a provable linear-time algorithm for finding an approximate local minimum
in smooth non-convex optimization. It applies to a general setting of machine learning optimization,
and in particular to the optimization problem of training deep neural networks. Furthermore, the
running time bound of our algorithm is the fastest known even for the more lenient task of computing
a point with vanishing gradient (called a critical point), for a wide range of parameters.
Formally, the problem of unconstrained mathematical optimization is stated in general terms
as that of finding the minimum value that a function attains over Euclidean space, i.e.
min f (x) .

x∈Rd

(1.1)

If f is convex, the above formulation is convex optimization and is solvable in (randomized)
polynomial time even if only a valuation oracle to f is provided. A crucial property of convex
functions is that “local optimality implies global optimality”, allowing for greedy algorithms to
reach the global optimum efficiently. Unfortunately, this is no longer the case if f is nonconvex;
indeed, even a degree four polynomial can be NP-hard to optimize [23], or even just to check
whether a point is not a local minimum [25]. Thus, for non-convex optimization one has to settle
for the more modest goal of reaching approximate local optimality efficiently.
Note that a particular interest to machine learning is the optimization of functions f : Rd 7→ R
of the finite-sum form
n
1X
f (x) =
fi (x) .
(1.2)
n
i=1

Such functions arise when minimizing loss over a training set, where each example i in the set
corresponds to one loss function fi in the summation.

We say that the function f is second-order smooth if it has Lipschitz continuous gradient and
Lipschitz continuous Hessian. We say that a point x is an ε-approximate local minimum if it
satisfies (following the tradition of [28]):
√
k∇f (x)k ≤ ε and ∇2 f (x)  − εI ,

where k · k denotes the Euclidean norm of a vector. We say that a point x is an ε-critical point
if it satisfies the gradient condition above, but not necessarily the second-order condition. Critical
points include saddle points in addition to local minima. We remark that ε-approximate local
minima (even with ε = 0) are not necessarily close to any local minimum, neither in domain nor in
function value. However, if we assume in addition the function satisfies the (robust) strict-saddle
property [15, 24] (see Section 2 for the precise definition), then an ε-approximate local minimum
is guaranteed to be close to a local minimum for sufficiently small ε.
Our main theorem below states the time required for the proposed algorithm FastCubic to find
an ε-approximate local minimum for second-order smooth functions.
1

Theorem (informal). Ignoring smoothness parameters, the running time of FastCubic to return
an ε-approximate local minimum is
!


 n
n3/4 
1
+ 7/4 · Th,1 for (1.2) or Õ
· Th for the general (1.1).
Õ
ε3/2
ε
ε7/4

Above, Th is the time to compute Hessian-vector product for ∇2 f (x) and Th,1 is that for an
arbitrary ∇2 fi (x).
The full statement of Theorem 1 can be found in Section 2.

Hessian-vector products can be computed in linear time —meaning Th,1 = O(d) and Th =
O(nd)— for many machine learning problems such as generalized linear models and training neural
networks [1, 29]. We explain this more generally in Appendix A. Therefore,
Corollary 1.1. Algorithm FastCubic returns an ε-approximate local minimum for the optimization problem of training a neural network in time
!
nd
n3/4 d
Õ
+ 7/4
.
ε3/2
ε
Another important aspect of our algorithm is that even in terms of just reaching an ε-critical
point, i.e. a point that satisfies k∇f (x)k ≤ ε without any second-order guarantee, FastCubic is
faster than all previous results (see Table 1 for a comparison).
The fastest methods to find critical points for a smooth non-convex function are gradient descent
and its extensions, jointly known as first-order methods. These methods are extremely efficient in
terms of per-iteration complexity; however, they necessarily suffer from a 1/ε2 convergence rate [27],
to the best of our knowledge, in previous results only higher-order methods seem capable of breaking
this 1/ε2 bottleneck [28]. For certain ranges of parameters, our FastCubic finds local minima even
faster than first-order methods, even though they only find critical points. This is depicted in
Table 1.
Paper
Gradient Descent (GD)
SVRG [2]
SGD [20]
noisy SGD [16]

a

cubic regularization [28]

Total Time Achieving k∇f (x)k ≤ ε

O nd
ε2
2/3 
O nd + n ε2 d

O εd4
O

Õ

this paper
this paper



ndω−1 +dω
ε3/2

Õ
Õ

dC1
ε4

nd
ε3/2

nd
ε7/4

+





n3/4 d
ε7/4

Second-Order Guarantee
n/a
n/a
n/a
∇2 f (x)  −ε1/C2 I
∇2 f (x)  −ε1/2 I



Table 1: Comparison of known methods.
a

Here C1 , C2 are two constants that are not explicitly written. We believe C1 ≥ 4.

2

∇2 f (x)  −ε1/2 I
∇2 f (x)  −ε1/2 I

1.1

Related work

Methods that Provably Reach Critical Points. Recall that only a gradient oracle is needed
to reach a critical point. The most commonly used algorithm in practice for training non-convex
learning machines such as deep neural networks is stochastic gradient descent (SGD), also known
as stochastic approximation [30] and its derivatives. Some practical enhancements widely used in
practice are based on Nesterov’s acceleration [26] and adaptive regularization [12]. The variance
reduction technique, introduced in [32], was extremely successful in convex optimization, but only
recently there was a non-convex counterpart with theoretical benefits introduced [2].
Methods that Provably Reach Local Minima. The recent work of Ge et al. [17] showed
that a noise-injected version of SGD in fact converges to local minima instead of critical points,
as long as the underlying non-convex function is strict-saddle. Their theoretical running time is a
large polynomial in the dimension and not competitive with our method (see Table 1).
The work of Lee et al. [24] shows that gradient descent, starting from a random point, almost
surely converges to a local minimum of a strict-saddle function. The rates of convergence and
precise step-sizes that are required are, however, yet unknown.
If second-order information (i.e., the Hessian oracle) is provided, the cubic-regularization method
1
of Nesterov and Polyak [28] converges in O( ε3/2
) iterations. However, each iteration of NesterovPolyak requires solving a cubic function which, in general, takes time super-linear in the input
representation.
One natural direction is to apply an approximate trust region solver, such as the linear-time
solver of [22], to approximately solve the cubic regularization subroutine of Nesterov-Polyak. However, the approximation needed by a naive calculation makes this approach even slower than vanilla
gradient descent. Our main challenge is to obtain approximate second-order local-minima and simultaneously improve upon gradient descent.
Independently of this paper and concurrently1 , Carmon et al. [7] develop an accelerated gradient
descent method that achieves the same running time for finding an approximate local minimum as
in our paper. Remarkably, the same running time is obtained via a very different technique.

1.2

Our Techniques

Our algorithm is based on the cubic regularization method of Nesterov and Polyak [8, 9, 28]. At
a high level, cubic regularization states that if we can minimize a cubic function m(h) , g > h +
1 >
L
3
2
2 h Hh + 6 khk exactly, where g = ∇f (x), H = ∇ f (x), and L is the second-order smoothness of
the function f , then we can iteratively perform updates x0 ← x + h, and this algorithm converges
to an ε-approximate local minimum in O(1/ε3/2 ) iterations. Unfortunately, solving this cubic
minimization problem exactly, to the best of our knowledge, requires a running time of O(dω )
where ω is the matrix multiplication constant. Getting around this requires five observations.
The first observation is that, minimizing m(h) up to a constant multiplicative approximation
(plus a few other constraints) is sufficient for showing an iteration complexity of O(1/ε3/2 ).2 The
proof techniques to show this observation are based on extending Nesterov and Polyak.
The second observation is that the minimizer h∗ of m(h) must be of the form h∗ = (H+λ∗ I)+ g+
v, where λ∗ ≥ 0 is some constant satisfying H + λ∗ I  0, and v is the smallest eigenvector of H
and + denotes the pseudo-inverse of a matrix. This can be viewed as moving in a mixture direction
1

To be precise, their manuscript appeared online approximately 24 hours before ours.
More specifically, we need mt (h) ≤ C1 minh {mt (h)} for some constant C. In addition, we need to have good
bounds on khk and k∇m(h)k.
2

3

between choosing h ← v, and choosing h to follow a shifted Newton’s direction h ← (H + λ∗ I)+ g.
Intuitively, we wish to reduce both the computation of (H+λ∗ I)+ g and v to Hessian-vector products.
The first task of computing (H + λ∗ I)+ g can be slow, and even if H + λ∗ I is strictly positivedefinite, computing it has a complexity depending on the (possibly huge) condition number of
H + λ∗ I [34]. The third observation is that it suffices to pick some λ0 > λ∗ so both (1) the condition
number of H + λ0 I is small and (2) the vectors (H + λ∗ I)−1 g and (H + λ0 I)−1 g are close. This relies
on the structure of m(h).
√
The second task of computing v has a complexity depending on 1/ δ where δ is the target
√
additive error [13, 14]. The fourth observation is that the choice δ = ε suffices for the outer loop
of cubic regularization to make sufficient progress. This reduces the complexity to compute v.
Finally, finding the correct value λ∗ itself is as hard as minimizing mt (h). The fifth step is to
design an iterative scheme that makes only logarithmic number of guesses on λ∗ . This procedure
either finds the correct one (via binary search), or finds an approximate one, λ0 , but satisfying
(H + λ∗ I)−1 g and (H + λ0 I)−1 g being sufficiently close.
Putting all the observations together, and balancing all the parameters, we can obtain a cubic
minimization subroutine (see FastCubicMin in Algorithm 2) that runs in time O(nd + n3/4 d/ε1/4 ).

2

Preliminaries and Main Theorem

We use k · k to denote the Euclidean norm of a vector and the spectral norm of a matrix. For a
symmetric matrix M we denote by λmax (M) and λmin (M) respectively the maximum and minimum
eigenvalues of M. We denote by A  B that A − B is positive semidefinite (PSD). For a PSD
matrix M, we denote by M+ its pseudo-inverse if M is not strictly positive definite.
We make the following Lipschitz continuity assumptions for the gradient and Hessian of the
target function f . Namely, there exist L2 , L > 0 such that
∀x, y ∈ Rd :

k∇2 f (x)k ≤ L2

and

k∇2 f (x) − ∇2 f (y)k ≤ Lkx − yk.

(2.1)

Definition 2.1. We assume the following complexity parameters on the access to f (x):
• Let Tg ∈ R∗ be the time complexity to compute ∇f (x) for any x ∈ Rd .

• Let Th ∈ R∗ be the time complexity to compute ∇2 f (x) v for any x, v ∈ Rd .
P
Definition 2.2. We say that f is of finite-sum form if f = n1 ni=1 fi (x) and k∇2 fi (x)k ≤ L2
for each i ∈ [n]. In this case, we define Th,1 to be the time complexity to compute ∇2 fi (x) v for
arbitrary x, v ∈ Rd and i ∈ [n].
Next we define the strict-saddle function for which an ε-approximate local minimum is almost
equivalent to a local minimum [15, 24].
Definition 2.3 (strict saddle). Suppose f (·) : Rd → R is twice differentiable. For α, β, γ ≥ 0, we
say f is (α, β, γ)-strict saddle if every x ∈ Rd satisfies at least one of the following three conditions:
1. k∇f (x)k ≥ α.
2. λmin (∇2 f ) ≤ −β.
3. There exists a local minimum x? that is γ-close to x in Euclidean distance.
We see that if a function is (α, β, γ)-strict saddle, then for ε < min{α, β 2 } an ε-approximate
local minimum is γ-close to some local minimum.

4

Algorithm 1 FastCubic(f, x0 , ε, L, L2 )
Input: f (x) that satisfies (2.1) with L2 and L; a starting vector x0 ; a target accuracy ε.
1/2
1: κ ← 900
.
εL
2: for t = 0 to ∞ do
> 2
3:
mt (h) , ∇f (xt )> h + h ∇ 2f(xt )h + L6 khk3

4:
(λ, v, vmin ) ← FastCubicMin ∇f (xt ), ∇2 f (xt ), L, L2 , κ

min
whichever gives smaller value for mt (h);
h0 ← either v or λv2L
0
6:
Set xt+1 , xt + h
3/2
 c is a constant; we proved c = 2.4 ∗ 106 works
7:
if mt (h0 ) > − cε√L then return xt+1 .
8: end for

5:

2.1

Main Results

The finite-sum setting captures much of supervised learning, including Neural Networks and Generalized Linear Models. The main theorem which we show in our paper is as follows:
Theorem 1. FastCubic (Algorithm 1) starts from a point x0 and outputs a point x such that
√
k∇f (x)k ≤ ε and λmin (∇2 f (x)) ≥ − Lε

in total time (denoting by D , f (x0 ) − f (x∗ ))
 √

√
1/4
• Õ Dε3/2L · Tg + DLε7/4 L2 · Th , or
 √

√

3/4 1/4
• Õ Dε3/2L · Tg + nTh,1 + Dn εL7/4 L2 · Th,1 in the finite-sum setting (see Definition 2.2).

Here Õ hides logarithmic factors in L, L2 , 1/ε, d, and in maxx k∇f (x)k .

Two Known Subroutines. Our running time of FastCubic relies on the following recent results
for approximate matrix inverse and approximate PCA:
Theorem 2.4 (Approximate Matrix Inverse). Suppose matrix M ∈ Rd×d satisfies kMk ≤ L2 and
2
λI + M  δI for constants λ, δ, L2 > 0. Let κ , λ+L
δ . Then, we can compute vector x satisfying

(2.2)
x − (λI + M)−1 b ≤ εkbk,

using Accelerated gradient descent (AGD) in O κ1/2 log(κ/ε) iterations, each requiring O(d) time
plus the time needed to multiply M with a vector.
P
Moreover, suppose M = n1 ni=1 Mi where each Mi is symmetric and satisfies kMi k ≤ L2 . If
Mi b can be computed in time O(d0 ) for each i and vector b, then accelerated SVRG [4,
 33] computes
a vector x that satisfies equation (2.2) in time O max{n, n3/4 κ1/2 } · d0 · log2 (κ/ε) .
We refer to the running time for this computation as Tinverse (κ, ε) and the algorithm as A.

Above, the SVRG based running time shall be used only towards our finite-sum case in Definition 2.2.
Theorem 2.5 (AppxPCA [3, 13, 14]). Let M ∈ Rd×d be a symmetric matrix with eigenvalues
1 ≥ λ1 ≥ · · · ≥ λd ≥ 0. With probability at least 1−p, AppxPCA produces a unit vector w satisfying
w> M w ≥ (1 − δ× )(1 − ε)λmax (M) . The total running time is Õ(Tinverse (1/δ× , εδ× )).

3

Our Fast Cubic Regularization Algorithm

Recall that the cubic regularization method of Nesterov and Polyak [28] studies the following upper
bound on the change in objective value as we move from a point xt to xt + h: (it follows simply
5

from the Taylor series truncated to the third order)
∀h ∈ Rd :

f (xt + h) − f (xt ) ≤ mt (h) , ∇f (xt )> h +

h> ∇2 f (xt )h L
+ khk3 .
2
6

(3.1)

Denote by h∗ an arbitrary minimizer of mt (h). We propose in this paper a subroutine FastCubicMin
to minimizes mt (h) approximately. Note that FastCubicMin returns two vectors v and vmin . We
min
then choose h0 to be either v or λv2L
, whichever gives a smaller value for mt (h).
Before discussing the details of FastCubicMin, let us first state a main theorem for FastCubicMin:3
Theorem 2 (Guarantees of FastCubicMin). The algorithm FastCubicMin finds a vector h0 that
satisfies
(a) It produces a vector h0 satisfying mt (h0 ) ≤ 0 and
either
3/2

3000mt (h0 ) ≤ mt (h∗ )

ε √
(b) If m(h∗ ) ≥ − 300
, then kh0 k ≤ kh∗ k +
L

√
√ε
4 L

or
and

mt (h∗ ) ≥ −

ε3/2
√ .
800 L

k∇mt (h0 )k ≤

ε
2

.

(c) FastCubicMin runs in time: (using Õ to hide logarithmic factors in L, L2 , 1/ε, d, k∇f (xt )k)
 √

2
• Õ (εL)L1/4
· Th where Th is the time to multiply ∇2 f (xt ) to a vector;


√

2
• Õ max n, n3/4 (εL)L1/4
· Th,1 where Th,1 is the time to multiply ∇2 fi (xt ) with a vector.

Above, the first guarantee promises that we are either done (because mt (h∗ ) is close to zero), or
we obtain a 1/3000 multiplicative approximation to mt (h∗ ). Our second guarantee in Theorem 2
promises that when we are done (because mt (h∗ ) is close to zero), the output vector h0 and h∗ are
roughly similar in Euclidean norm and have a small gradient k∇mt (h0 )k. Our third guarantee gives
the time complexity of FastCubicMin.
Now, our final algorithm FastCubic for finding the ε-approximate local minimum of f (x) is
included in Algorithm 1. It simply iteratively calls FastCubicMin to find an approximate minimizer,
3/2
and it then stops whenever mt (h0 ) > − cε√L for some large constant c.
Roadmap. In Section 4 we show why Theorem 2 implies Theorem 1. All the remaining sections
are for the purpose of proving Theorem 2. Because our FastCubicMin is very technical, instead
of stating what the algorithm is right away, we decide to take a different path. In Section 5, we
first state a lemma characterizing “what h∗ looks like”. In Section 6, we provide a set of sufficient
conditions which “look similar” to the characterization of h∗ , and show that as long as these
conditions are met, Theorem 2-a and 2-b follow easily. Finally, in Section 7, we state FastCubicMin
and explain why it satisfies these sufficient conditions and why it runs in the aforementioned time.

4

Theorem 2 implies Theorem 1

In this section, we show that Theorem 2 implies Theorem 1. It relies on the following lemma
(proved in Appendix B) regarding the sufficient condition for us to reach an ε-approximate local
minimum.
3

To present the simplest result, we have not tried to improve the constant dependency in this paper.

6

3/2

ε √
Lemma 4.1. If mt (h∗ ) ≥ − 800
and h0 is an approximate minimizer of mt (h) satisfying
L
√
√ε
4 L

k∇mt (h0 )k ≤ 2ε ,
√
then we have that k∇f (xt + h0 )k ≤ ε and λmin (∇2 f (xt + h0 )) ≥ − Lε.
kh0 k ≤ kh∗ k +

and

3/2

Proof of Theorem 1 from Theorem 2. When FastCubic terminates, we have mt (h0 ) > − cε√L ; there3/2

ε √
fore, it satisfies mt (h∗ ) ≥ − 800
according to Theorem 2-a. Combining this with Theorem 2-b and
L
Corollary 4.1, we conclude that
in the last iteration of FastCubic, our output satisfies k∇f (xt +h0 )k ≤
√
ε and λmin (∇2 f (xt + h0 )) ≥ − Lε. This finishes the proof with respect to the accuracy conditions.

As for the running time, in every iteration except for the last one, FastCubic satisfies mt (h0 ) ≤
3/2 
3/2 
√
√
. Therefore by (3.1), we must have decreased the objective by at least Ω −ε
in this
−Ω −ε
L
L
√
(f (x0 )−f ∗ ) L 
round, and this cannot happen for more than O
iterations. The final running time
ε3/2
of FastCubic follows from this bound together with Theorem 2-c.
Therefore, in the rest of the paper it suffices to study FastCubicMin and prove Theorem 2.

5

Characterization Lemma of the Minimizer h∗

For notational simplicity in this and the subsequent sections we focus on the following problem:
minimize

h> Hh L
+ khk3
2
6
where H is a symmetric matrix with kHk2 ≤ L2 .
m(h) , g > h +

Recall from the previous section that we have denoted by h∗ an arbitrary minimizer of m(h).
We have the following lemma which characterizes h∗ : (a variant of this lemma has appeared in [8],
and we prove it in the appendix for the sake of completeness)
Lemma 5.1. We have h∗ is a minimizer of m(h) if and only if there exists λ∗ ≥ 0 such that
2λ∗
.
H + λ∗ I  0 ,
(H + λ∗ I)h∗ = −g ,
kh∗ k =
L
The objective value in this case is given by
1
2(λ∗ )3
m(h∗ ) = − g > (H + λ∗ I)+ g −
≤0 .
2
3L2
The following corollary comes from Lemma 5.1 and its proof:
Corollary 5.2. The value λ∗ in Lemma 5.1 is unique, and for every λ satisfying H + λI  0, we
have
2λ
2λ
k(H + λI)−1 gk >
⇐⇒ λ∗ > λ and k(H + λI)−1 gk <
⇐⇒ λ∗ < λ .
L
L
In the above characterization, we have a crude upper bound on λ∗ :
p

Proposition 5.3. We have λ∗ ≤ B , max 2L2 + Lkgk, 1 with λ∗ defined in Lemma 5.1.

Proof. We have Lk(H + BI)−1 gk ≤
Corollary 5.2.

Lkgk
λmin (H+BI)

7

≤

Lkgk
B−L2

< 2B and therefore λ∗ ≤ B due to

6

Sufficient Conditions for Theorem 2-a and 2-b

Without worrying about the design of FastCubicMin at this moment, let us first state a set of
sufficient conditions under which the assumptions in Theorem 2-a can be satisfied.
Main Lemma 1. Consider an algorithm that outputs a real λ ∈ [0, 2B], a vector v ∈ Rd , and a
unit vector vmin ∈ Rd . Additionally, suppose numbers κ, ε̃ ≥ 0 satisfying the following conditions:
1
1
(6.1)
ε̃ ≤
10000 (max {κ, L, L2 , kgk, k(H + λI)−1 k, B})20

(H + (λ − Lε̃)I)−1  0
Moreover, suppose that the outputs (λ, v, vmin ) satisfy one of the following two cases:
Case 1: Lk(H + λI)−1 gk ∈ [2λ − 2Lε̃, 2λ + 2Lε̃]

kv + (H + λI)−1 gk ≤ ε̃

and

Case 2: The following conditions are satisfied:

(a) λ ≥ λ∗ and λ + λmin (H) ≤ κ1
(b) Lk(H + λI)−1 gk ≤ 2λ and kv + (H + λI)−1 gk ≤ ε̃
1
> Hv
(c) vmin
min ≤ λmin (H) + 10κ

min
Then, at least one of the two choices h0 ∈ v, λv2L
satisfy
either

m(h∗ ) ≥ 3000m(h0 )

or

(6.2)

m(h∗ ) ≥ −

32
.
κ3 L2

Let us compare such sufficient conditions to the characterization Lemma 5.1.
• In Case 1, up to a very small error ε̃, we have essentially found a vector v that satisfies
∗
v ≈ −(H + λI)−1 g and kvk ≈ 2λ
L . Therefore, this v should be close to h for obvious reason.
(This is the simple case.)
• In Case 2, we have only found a vector v that satisfies v ≈ −(H + λI)−1 g and kvk . 2λ
L .
In this case, we also compute an approximate lowest eigenvector vmin of λmin (H) up to an
additive 1/10κ accuracy (see case 2-c). We will make sure that, as long as the conditions in
min
2-a hold, then either v or λv2L
will be an approximate minimizer for mt (h).
(This is the hard case.)
Proof of Main Lemma 1. We first consider Case 1. According to Corollary 5.2, if ε̃ = 0 then v is a
minimizer of m(h). The following claim extends this argument to the setting when ε̃ > 0:
Claim 6.1. If λ and v satisfy Case 1 and ε̃ satisfies (6.1), then m(v) ≤ m(h∗ ) +

1
250κ3 L2

From the above lemma it follows that either m(h∗ ) ≥ − κ38L2 otherwise m(h∗ ) ≥ 1.1m(v) which
satisfies the conditions of the theorem.
We now consider Case 2, and in this case we make the following two claims:
n

o
min
Claim 6.2. If λmin (H) ≤ − κ1 then m(h∗ ) ≥ 1500 min m(v), m λv2L
− 500κ13 L2 .
Claim 6.3. If λmin (H) ≥ − κ1 then m(h∗ ) ≥ 2m(v) −

16
κ3 L2

.

Lemma 1 now follows from the two claims because we can output the vector h0 which has the
min
lowest value of m(h0 ) amongst the two choices h0 ∈ v, λ v2d
. This satisfies either m(h∗ ) ≥
3000m(h0 ) or m(h∗ ) ≥ − κ332L2 .
The missing proofs of the three claims are deferred to Appendix D.
8

The next main lemma shows that, under the same sufficient conditions as Main Lemma 1, we
also have that Theorem 2-b holds. (Its proof is contained in Appendix E.)
3/2

ε √
Main Lemma 2. In the same setting as Main Lemma 1, suppose m(h∗ ) ≥ − 300
. Then the
L
output vector v satisfies the following conditions:
3
ε
15
kvk ≤ kh∗ k +
and k∇m(v)k ≤ + 2 .
κL
4 κ L

7

Main Algorithms for Theorem 2

We are now ready to state our main algorithm FastCubicMin and sketch why it satisfies the sufficient
conditions in Main Lemma 1. As described in Algorithm 2, our algorithm starts with a very large
choice λ0 ← 2B and decreases it gradually. At each iteration i, it computes an approximate inverse
v satisfying kv + (H + λi I)−1 gk ≤ ε̃ with respect to the current λi . Then there are three cases,
depending on whether Lkvk is approximately equal to, larger than, or smaller than 2λi . At a high
level, if it is “equal”, then we have met Case 1 in Main Lemma 1; if it is “larger”, then we can
binary search the correct value of λ∗ in the interval [λi , λi−1 ]; and if it is “smaller”, then we need
to compute an approximate eigenvector and carefully choose the next point λi+1 .
We state our main lemma below regarding the correctness and running time of FastCubicMin.
Main Lemma 3. FastCubicMin in Algorithm 2 outputs a real λ ∈ [0, 2B], a vector v ∈ Rd , and
a unit vector vmin ∈ Rd satisfying one of the two sufficient conditions in Main Lemma 1. We also
have that the procedure can be implemented in a total running time of

√
• Õ κL2 · Th if Accelerated Gradient Descent is used in Theorem 2.4 to invert matrices.

√
• Õ max{n, n3/4 κL2 }·Th,1 if we use accelerated SVRG as the subprocedure A in Theorem 2.4.

Here Õ hides logarithmic factors in L, L2 , κ, d, B.

We prove the correctness half of Main Lemma 3, and defer its running time analysis to Appendix G.

7.1

Correctness Half of Main Lemma 3

We will now establish the correctness of our algorithm. We first observe that the BinarySearch
subroutine returns (λ, v, ∅) that satisfies Case 1 of Main Lemma 1.
Fact 7.1. BinarySearch outputs a pair λ and v such that
Lk(H + λI)−1 gk ∈ [2λ − 2Lε̃, 2λ + 2Lε̃]

and

kv + (H + λI)−1 gk ≤ ε̃ .

Proof. The latter is guaranteed by line 3 in BinarySearch, and the former is implied by the latter
because

 

Lk(H + λI)−1 gk ∈ Lkvk − Lε̃/2, Lkvk + Lε̃/2 ⊆ 2λ − 2Lε̃, 2λ + 2Lε̃ .
We also establish the following invariants regarding the values λi . (Proof in Appendix F.)

Lemma 7.2. The following statements hold for all i until FastCubicMin terminates
(a) λi ∈ [0, 2B], λi + λmax (H) ≤ 3B
(b) λi + λmin (H) ≥

(c) λi+1 + λmin (H)

3
10κ
≤ 34 (λi

+ λmin (H)) unless λi+1 = 0

Moreover when FastCubicMin terminates at Line 20 we have λi + λmin (H) ≤ κ1 .
We now prove the output (λ, v, vmin ) of FastCubicMin satisfies the sufficient conditions of Main Lemma 1.
9

Algorithm 2 FastCubicMin(g, H, L, L2 , κ) (main algorithm for cubic minimization)
Input: g a vector, H a symmetric matrix, parameters κ, L and L2 which satisfies −L2 I  H  L2 I.
Output: (λ, v,p
vmin )
1
1: B ← L2 + Lkgk + κ
.


20 
2: ε̃ ← 1/ 10000 max L, kgk, 3κ
,
B,
1
10
3: λ0 ← 2B.
4: for i = 0 to ∞ do
5:
Compute v such that kv + (H + λi I)−1 gk ≤ ε̃.
6:
if Lkvk ∈ [2λi − Lε̃, 2λi + Lε̃] then
7:
return (λi , v, ∅).
8:
else if Lkvk > 2λi + Lε̃ then
9:
return BinarySearch(λ1 = λi−1 , λ2 = λi , ε̃).
10:
else if Lkvk < 2λi − Lε̃ then
11:
Let Power Method find vector w that is 9/10-appx leading eigenvector of (H + λi I)−1 :
9
10 λmax ((H

12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:

+ λi I)−1 ) ≤ w> (H + λi I)−1 w ≤ λmax ((H + λi I)−1 ) .

1
Compute a vector w̃ such that kw̃ − (H + λi I)−1 wk ≤ ε̂ , 60B
.
1
∆ ← 21 w̃> w−ε̂
.
1
if ∆ > 2κ
then
λ̃i+1 ← λi − ∆
2.
if λ̃i+1 > 0 then λi+1 ← λ̃i+1 else λi+1 ← 0
else
> Hv
Use AppxPCA to find any unit vector vmin such that vmin
min ≤ λmin (H) +
>
Flip the sign of vmin so that g vmin ≤ 0.
return (λi , v, vmin ).
end if
end if
end for

Algorithm 3 BinarySearch(λ1 , λ2 , ε̃) (binary search subroutine)
Input: λ1 ≥ λ2 , Lk(H + λ1 I)−1 gk ≤ 2λ1 , Lk(H + λ2 I)−1 gk ≥ 2λ2 , λ2 + λmin (H) > 0
Output: (λ, v, ∅)
1: for t = 1 to ∞ do
2
2:
λmid ← λ1 +λ
2
3:
Compute vector v such that kv + (H + λmid I)−1 gk ≤ ε̃/2
4:
if Lkvk ∈ [2λmid − Lε̃, 2λmid + Lε̃] then
5:
return (λmid , v, ∅)
6:
else if Lkvk + Lε̃ ≤ 2λmid then
7:
λ1 ← λmid
8:
else if Lkvk − Lε̃ ≥ 2λmid then
9:
λ2 ← λmid
10:
end if
11: end for
10

1
10κ .

Correctness Proof of Main Lemma 3. We carefully verify these sufficient conditions:
• Lemma 7.2 implies λi ∈ [0, 2B].

3
from Lemma 7.2 implies k(H + λi I)−1 k ≤ 4κ. It is now immediate that
• λi + λmin (H) ≥ 10κ
the choice of ε̃ on Line 2 satisfies the Condition (6.1) in the assumption of Main Lemma 1.

1
• Since ε̃ ≤ 10κL
and λi + λmin (H) ≥
Condition (6.2) in Main Lemma 1.

3
10κ

it follows that (H + (λi − Lε̃)I)−1  0 which proves

• We now verify Case 1 and 2 in the assumption of Main Lemma 1. At the beginning of the
algorithm, our choice λ0 = 2B ensures (using Proposition 5.3) that Lk(H + λ0 I)−1 gk < 2λ0 .
Let us now consider the various places where the algorithm outputs:
– If FastCubicMin terminates at Line 7, then we have kv + (H + λi I)−1 gk ≤ ε̃ and additionally


Lk(H + λi I)−1 gk ∈ Lkvk − Lε̃, Lkvk + Lε̃ ⊆ [2λi − 2Lε̃, 2λi + 2Lε̃] .

Therefore, the output meets Case 1 requirement of Main Lemma 1 with λ = λi .
– If FastCubicMin terminates at Line 9, then Lk(H + λi I)−1 gk > Lkvk − Lε̃ ≥ 2λi . Obviously,
we must have i ≥ 1 in this case because Lk(H + λ0 I)−1 gk < 2λ0 . Therefore, Line 10 must
have been reached at the previous iteration, so it implies Lk(H + λi−1 I)−1 gk < 2λi−1 .
Together, these two imply that we can call BinarySearch with (λi−1 , λi ). Owing to Fact 7.1,
the subroutine outputs a pair (λ, v) satisfying the Case 1 requirement of Main Lemma 1.
– If FastCubicMin terminates on Line 20, we verify that Case 2 of Main Lemma 1 with λ = λi
holds. We first have
Lk(H + λi I)−1 gk ≤ Lkvk + Lε̃ ≤ 2λi .
By Corollary 5.2, we also have that λi ≥ λ∗ . Lemma 7.2 tells us λi satisfies λi +λmin (H) ≤ κ1 .
1
> Hv
Vector v satisfies kv + (H + λi I)−1 gk ≤ ε̃. Vector vmin satisfies vmin
min ≤ λmin (H) + 10κ .

In sum, we have verified that all the assumptions of Main Lemma 1 hold.

Final Proof of Theorem 2. Theorem 2 is a direct corollary of our main lemmas. Main Lemma 3
ensures that the assumptions of Main Lemma 1 and Main Lemma 2 both hold. Now, using the special choice of κ in FastCubic, Theorem 2-a immediately comes from Main Lemma 1; Theorem 2-b
immediately comes from Main Lemma 2; and Theorem 2-c immediately comes from Main Lemma 3.
This finishes the proof of Theorem 2.

Acknowledgements
We thank Ben Recht for very helpful suggestions and corrections to a previous version. Z. Allen-Zhu
is supported by an NSF Grant, no. CCF-1412958, and a Microsoft Research Grant, no. 0518584.
Any opinions, findings and conclusions or recommendations expressed in this material are those of
the author(s) and do not necessarily reflect the views of NSF or Microsoft.

Appendix
A

Computing Hessian-Vector Product in Linear Time

In this section we sketch the intuition regarding why Hessian-vector products can be computed in
linear time in many interesting (especially machine learning) problems. We start by showing that
the gradient can be computed in linear time. The algorithm is often referred to as back-propagation,
11

which dates back to Werbos’s PhD thesis [35], and has been popularized by Rumelharte et al. [31]
for training neural networks.
Claim A.1 (back-propagation, informally stated). Suppose a real-valued function f : Rd → R can
be evaluated by a differentiable circuit of size N . Then, the gradient ∇f can be computed in time
O(N + d) (using a circuit of size O(N + d)). 4
The claim follows from simple induction and chain-rule, and is left to the readers. In the training
of neural networks, often the size of circuits that computes the objective f is proportional to (or
equal to) the number of parameters d. Thus the gradient ∇f can be computed in time O(d) using
a circuit of size d.
Next, we consider computing ∇2 f (x) · v where v ∈ Rd . Let g(x) := h∇f (x), vi be a function
from Rd to R. Then, we see that if suffices to compute the gradient of g, since
∇2 f (x) · v = ∇g(x) .

We observe that g(x) can be evaluated in linear time using circuit of size O(d) since we’ve shown
∇f (x) can. Thus, using Claim A.1 again on function g, 5 we conclude that ∇g(x) can also be
computed in linear time.

B

Proof of Lemma B.1 and Corollary 4.1

Lemma B.1. For all h0 ∈ Rd , it satisfies
k∇f (xt +h0 )k ≤ Lkh0 k2 +k∇mt (h0 )k

and

λmin (∇2 f (xt +h0 )) ≥ −



3L2 max{0,−mt (h∗ )}
2

1/3

−Lkh0 k .

Proof of Lemma B.1. Let us denote by g = ∇f (xt ) and H = ∇2 f (xt ) in this proof. We begin by
proving the first order condition. Note that we have
∇mt (h) = g + Hh + L2 khkh .

Recall h∗ is a minimizer of argmin mt (h). The characterization result in Lemma 5.1 shows H +
Lkh∗ k
2 I  0, and thus
L
g > h∗ + (h∗ )> Hh∗ + kh∗ k3 = ∇mt (h∗ )> h∗ = 0
(B.1)
2


Lkh∗ k
L
3
∗ >
∗ >
∗
(h ) Hh + khk = (h )
H+
I h∗ ≥ 0 .
(B.2)
2
2
They imply
(h∗ )> Hh∗ Lkh∗ k3 ¬ (h∗ )> Hh∗ L ∗ 3
+
=−
− kh k
2
6
2
3
­ L
L
L
≤ kh∗ k3 − kh∗ k3 = − kh∗ k3
4
3
12
where ¬ uses (B.1) and ­ uses (B.2).
mt (h∗ ) = g > h∗ +

We compute the norm of the gradient at a point xt + h0 for any h0 ∈ Rd :

k∇f (xt + h0 )k ≤ k∇f (xt + h0 ) − ∇mt (h0 )k + k∇mt (h0 )k
Z 1


L
= ∇f (xt ) +
∇2 f (xt + τ h0 )h0 dτ − g + Hh0 + kh0 kh0 + k∇mt (h0 )k
2
0

4
5

Technically, we assume that the gradient of each gate can be computed in O(1) time
We assume here that the original circuits are twice differentiable

12

(B.3)

Z

1


L
∇2 f (xt + τ h0 ) − H h0 dτ + kh0 k2 + k∇mt (h0 )k
2
0
Z 1
®
L
τ dτ + kh0 k2 + k∇mt (h0 )k = Lkh0 k2 + k∇mt (h0 )k
≤ Lkh0 k2
(B.4)
2
0
where ® follows from the Lipschitz continuity on the Hessian (2.1). This proves the first conclusion
of the lemma.
≤

As for the second-order condition, we first note that for all h0 ∈ Rd , by the Lipschitz continuity
on the Hessian (2.1), we have k∇2 f (xt + h0 ) − ∇2 f (xt )k ≤ Lkh0 k. However, this implies
λmin (∇2 f (xt + h0 )) ≥ λmin (∇2 f (xt )) − Lkh0 k .

(B.5)

λmin (∇2 f (xt + h0 )) ≥ −Lkh0 k .

(B.6)

because if two matrices A and B satisfies kA−Bk ≤ p, then it must satisfy λmin (A)−λmin (B) ≤ p
as well. We consider two cases: if λmin (∇2 f (xt )) ≥ 0, then we have
Otherwise, we consider the case where λmin (∇2 f (xt )) = λmin (H) < 0. Let νd be the normalized
eigenvector corresponding to λmin (H), and define
2λmin (H)
h̃ , sign(g > νd ) ·
νd .
L
We calculate mt (h̃) as follows:

h̃> Hh̃ L
4|λmin (H)|3
h̃> Hh̃ L
2(λmin (H))2 >
Hν
+
+ kh̃k3 ≤
+ kh̃k3 =
ν
d
d
2
6
2
6
L2
3L2
3
3
3
4|λmin (H)| ­ 2(λmin (H))
¬ 2(λmin (H))
+
=
,
(B.7)
=
L2
3L2
3L2
where ¬ uses νd> Hνd = λmin (H) < 0, and ­ uses the assumption that λmin (H) < 0. Since by
definition mt (h∗ ) ≤ mt (h̃), we can deduce from inequality (B.7) that
 2
1/3
3L |mt (h∗ )|
2
λmin (∇ f (xt )) = λmin (H) ≥ −
.
(B.8)
2
Now we put together inequalities (B.5) and (B.8), and obtain
 2
1/3
3L |mt (h∗ )|
2
0
λmin (∇ f (xt + h )) ≥ −
− Lkh0 k .
(B.9)
2
Combining (B.6) and (B.9) we finish the proof of Lemma B.1.
mt (h̃) = g > h̃ +

3/2

ε √
Corollary 4.1. If mt (h∗ ) ≥ − 800
and h0 is an approximate minimizer of mt (h) satisfying
L
√
√ε
4 L

k∇mt (h0 )k ≤ 2ε ,
√
then we have that k∇f (xt + h0 )k ≤ ε and λmin (∇2 f (xt + h0 )) ≥ − Lε.
kh0 k ≤ kh∗ k +

and

3/2

ε √
, along with inequality
Proof of Corollary 4.1. First of all, our assumption that mt (h∗ ) ≥ − 800
L
√

√

(B.3), tells us that kh∗ k ≤ 4√εL . This, together with our assumption on kh0 k, implies kh0 k ≤ 2√εL .
Since we also assume k∇mt (h0 )k ≤ 2ε , we have from Lemma B.1 that
ε ε
k∇f (xt + h0 )k ≤ Lkh0 k2 + k∇mt (h0 )k ≤ + ≤ ε .
4 2
For the second-order condition, we can again apply Lemma B.1 to get
!1/3 √
 2
1/3
√
3L max{0, −mt (h∗ )}
Lε
3L3/2 ε3/2
2
0
0
λmin (∇ f (xt + h )) ≥ −
− Lkh k ≥ −
−
≥ − Lε .
2
1600
2
13

C

Proof of Lemma 5.1 and Corollary 5.2

We begin by proving a few lemmas that characterize the system of equations.
Lemma C.1. Consider the following system of equations/inequalities in variables λ, h:
2λ
H + λI  0 ,
(H + λI)h = −g ,
khk =
.
L
The following statements hold for any solution (λ0 , h0 ) of the above system:

(C.1)

• There is a unique value λ0 that satisfies the above equations. λ0 is such that λ0 ≥ −λmin (H).

• If λ0 > −λmin (H), then the corresponding h0 is also unique and is given by h0 = −(H + λI)−1 g.
• If λ0 = −λmin (H) then g > v = 0 for any vector v belonging to the eigenspace corresponding to
λmin (H). Subsequently we also have that the corresponding h0 is of the form
h0 = −(H + λI)+ g + γv

for some γ and v in the lowest eigenspace of H.

Proof of Lemma C.1. Note that H + λI  0 ensures that for any solution λ0 , we have λ0 ≥
−λmin (H). Furthermore, for any λ0 > −λmin (H), the corresponding h is uniquely defined by
h = (H + λI)−1 g since H + λ0 I is invertible. If indeed λ0 = −λmin (H), then we have that the
equation (H − λmin (H)I)h = −g has a solution. This implies that g has no component in the null
space of H − λmin (H)I, or equivalently that it has no component in the eigenspace corresponding
to λmin (H). We also have that every solution of (H − λmin (H)I)h = −g is necessarily of the form
h = −(H − λmin I)+ g + γv

for some γ and v in the lowest eigenspace of H.

We will now prove the uniqueness of λ0 by contradiction. Consider two distinct values of λ1 , λ2
that satisfy the system (C.1). If both λ1 , λ2 > −λmin (H) we get that
2λ2
2λ1
and k(H + λ2 I)−1 gk =
.
k(H + λ1 I)−1 gk =
L
L
Now note that k(H + λI)−1 gk is a strictly decreasing function over the domain λ ∈ (−λmin (H), ∞)
and 2λ
L is strictly increasing over the same domain. Therefore the above two equations cannot be
satisfied for two distinct λ1 , λ2 > −λmin (H) which is a contradiction. Suppose now without loss of
generality that λ1 = −λmin (H). Then we have that the corresponding solution is of the form
h = −(H + λI)+ g + γv

for some γ and v in the lowest eigenspace of H and g has no component in the lowest eigenspace
of H. It follows that k(H − λmin (H)I)+ gk ≥ k(H + λI)−1 gk for any λ > −λmin (H). By a similar
argument as in the first case, we can now see that the following conditions,
2λ1
2λ2
k(H + λ1 I)+ g + γvmin (H)k =
and k(H + λ2 I)−1 gk =
,
L
L
cannot both be satisfied for λ2 > λ1 = −λmin (H), giving us a contradiction. This finishes the proof
of Lemma C.1.
Lemma C.2. Let (λ, h) be a solution of the system (C.1). Then we have that
1
2λ3
m(h) = − g > (H + λI)+ g −
.
2
3L2
14

Proof of Lemma C.2. By the definition of the system (C.1), any solution λ, h to the system should
be such that there exists some γ such that
h = (H + λI)+ g + γv0
where v0 is in the null space of H + λI if it exists; otherwise γ = 0. This gives us the following:
h> Hh L
m(h) = g > h +
+ khk3
2
6
1 >
λ
L
¬
= − h (H + λI)h − khk2 + khk3
2
2
6
3
2λ
1
­
.
= − g > (H + λI)+ g −
2
3L2
Equality ¬ follows because (H + λI)h = −g. Equality ­ follows because h = (H + λI)+ g + γv0
and khk = 2λ
L.
Lemma 5.1. h∗ is a minimizer of m(h) if and only if there exists λ∗ ≥ 0 such that
2λ∗
.
H + λ∗ I  0 ,
(H + λ∗ I)h∗ = −g ,
kh∗ k =
L
The objective value in this case is given by
1
2(λ∗ )3
m(h∗ ) = − g > (H + λ∗ I)+ g −
≤0 .
2
3L2
Proof of Lemma 5.1. We first compute that
∇m(h) = g + Hh +

L
L
L
khkh and ∇2 m(h) = H + khkI + khk
2
2
2



h
khk



h
khk

>

.

For the forward direction, suppose h∗ is a minimizer of m(h). Let λ∗ = L2 kh∗ k. Then, the necessary
conditions ∇m(h∗ ) = 0 and ∇2 m(h∗ )  0 can be written as
 ∗   ∗ > !
h
h
∗
∗
>
∗
∗
g + (H + λ I)h = 0 and w
H+λ I+λ
w ≥ 0, ∀w ∈ Rn .
(C.2)
kh∗ k
kh∗ k
From this we see (H + λ∗ I)h∗ = −g and kh∗ k =

2λ∗
L ,

and the only thing left to verify is H + λ∗ I  0.

Note that if h∗ = 0, then the second inquality in (C.2) directly implies H + λ∗ I  0. Thus, we
only need to focus on h∗ 6= 0. We want to show that w> (H + λ∗ I)w ≥ 0 for every w ∈ Rd . Now,
if w> h∗ = 0 then this trivially follows from (C.2), so it suffices to focus on those w that satisfies
w> h∗ 6= 0.
Since w and h∗ are not orthogonal, there exists γ ∈ R\{0} such that kh∗ + γwk = kh∗ k. (This
can be done by squaring both sides and solving the linear system in λ.) Squaring both sides we
have
γ 2 kwk2
=0 .
(C.3)
(γw)> h∗ +
2
Now we bound the difference
(h∗ + γw)> H(h∗ + γw) h∗ Hh∗
m(h∗ + γw) − m(h∗ ) = g > ((h∗ + γw) − h∗ ) +
−
2
2
∗ + γw)> H(h∗ + γw)
h∗ Hh∗
(h
¬
−
= (h∗ − (h∗ + γw))> (H + λ∗ I)h∗ +
2
2
∗ 2
∗ + γw)> H(h∗ + γw)
(h
h∗ Hh∗
­ λ γ
=
kwk2 + (h∗ − (h∗ + γw))> Hh∗ +
−
2
2
2
∗ Hh∗
∗ + γw)> H(h∗ + γw)
λ∗ γ 2
h
(h
=
kwk2 +
− (h∗ + γw)> Hh∗ +
2
2
2
15

λ∗ γ 2
γ2
γ2 >
kwk2 + w> Hw =
w (H + λ∗ I)w ,
(C.4)
2
2
2
where ¬ and ­ follow from (C.2) and (C.3), respectively. Since h∗ is a minimizer of m(h), we
immediately have
γ2 >
m(h∗ + γw) − m(h∗ ) =
w (H + λ∗ I)w ≥ 0,
2
and we conclude that (H + λ∗ I)  0.
=

For the backward direction, we will make use Lemma C.1 and Lemma C.2. First we note that
the function m(h) is continuous and bounded from below, and there exists at least one minimizer
h∗ . Suppose now there exists a λ∗ and a corresponding h∗ such that (λ∗ , h∗ ) is a solution to the
system C.1. The backward direction requires us to prove that h∗ must be a minimizer of m(h). By
Lemma C.1 we get the following two cases.
We prove the backward direction by showing that the conditions in Equation C.2 determine the
minimizer up to its norm. To this end we will use Lemma C.1 and Lemma C.2.

First we note that the function m(h) is continuous, bounded from below, and tends to +∞
when khk → ∞, so there exists at least one minimizer h∗ .

Suppose now there exists a λ∗ and a corresponding h∗ such that (λ∗ , h∗ ) is a solution to the
system (C.1). The backward direction requires us to prove that h∗ must be a minimizer of m(h).
By Lemma C.1 we get the following two cases.
• If λ∗ > −λmin (H) then (λ∗ , h∗ ) is the only solution to the system (C.1). By the proof of the
forward direction we see that any minimizer of m(h) must satisfy system (C.1) and therefore
h∗ must be the minimizer.
• If above is not the case, then λ∗ = −λmin (H). Let h0 be any minimizer of m(h). Lemma C.1
and the proof of the forward direction ensures that (λ∗ , h0 ) also satisfies the system (C.1). By
Lemma C.2 we get m(h∗ ) = m(h0 ) and therefore h∗ is a minimizer too.

Corollary 5.2. This value λ∗ is unique, and for every λ satisfying H + λI  0, we have
2λ
2λ
k(H + λI)−1 gk >
⇐⇒ λ∗ > λ and k(H + λI)−1 gk <
⇐⇒ λ∗ < λ .
L
L
Proof of Corollary 5.2. The uniqueness of λ∗ follows from Lemma C.1. To prove the second part
we first make some observations about the function
2y
p(y) ,
− k(H + yI)−1 gk
L
defined on the domain y ∈ (−λmin (H), ∞). Note that p(y) is continuous and strictly increasing
over the domain and p(y) → ∞ as y → ∞.
The corollary requires us to show that

p(λ) < 0 ⇐⇒ λ∗ > λ

and

p(λ) > 0 ⇐⇒ λ∗ < λ .

We begin by showing the first equivalence. To see the backward direction note that if λ∗ > λ >
∗
−λmin (H), by the characterization of λ∗ in Lemma C.1 we have that k(H + λ∗ I)−1 gk = 2λL i.e.
p(λ∗ ) = 0 which implies that p(λ) < 0 as p(y) is a strictly increasing function. For the forward
direction note that since p(y) is continuous and strictly increasing we see that the range of the
function contains [p(λ), ∞). Since p(λ) < 0 there must exist a λ∗ > λ such that p(λ∗ ) = 0 which
by the characterization in Lemma C.1 finishes the proof.
Now we will prove that p(λ) > 0 ⇐⇒ λ∗ < λ. To see the forward direction note that if λ∗ ≥ λ
then p(λ∗ ) = 0 and p(λ) > 0 which contradicts the fact that p(y) is strictly increasing. For the
16

backward direction we consider two cases. Firstly if λ∗ > −λmin (H) the conclusion follows similarly
by the monotonicity of p(y). If λ∗ = −λmin then by Lemma C.1, we have that g has no component
in the lowest eigenspace of H and therefore if we extend p(y) to −λmin (H) by defining
−2λmin (H)
p(−λmin (H)) ,
− k(H − λmin (H)I)+ gk
L
we get that p(y) is increasing in the domain y ∈ [−λmin (H), ∞). Now from the characterization
of the solution in Lemma C.1 we can see that p(−λmin (H)) ≥ 0 and therefore by monotonicity
p(λ) > 0. This finishes the proof.

D

Proof of Main Lemma 1

D.1

Proof of Claim 6.1

Claim 6.1. If λ and v satisfy Case 1 and ε̃ satisfies (6.1), then m(v) ≤ m(h∗ ) +

1
250κ3 L2

Proof of Claim 6.1. Note that by the conditions of the theorem we have that (H+(λ−Lε̃)I)−1  eq
and
Lk(H + (λ − Lε̃)I)−1 gk ≥ 2λ − 2Lε̃ and Lk(H + (λ + Lε̃)I)−1 gk ≤ 2λ − 2Lε̃ ,
according to Corollary 5.2 we must have
λ∗ ∈ [λ − Lε̃, λ + Lε̃]

(D.1)

This also implies (using our assumption on ε̃)
Next, consider the value m(v)

Lkvk ≤ [2λ∗ − 5Lε̃, 2λ∗ + 5Lε̃] .



v > Hv L
v > (H + λI)v
λ Lkvk
+ kvk3 = g > v +
− kvk2
−
.
2
6
2
2
6
We bound the two parts on the right hand side of (D.2) separately. The first part
m(v) = g > v +

(D.2)

v > (H + λI)v
g > (H + λI)−1 g
k(H + λI)−1 kε̃2
≤−
+ kgkε̃ + k(H + λI)−1 gkε̃ +
2
2
2
>
−1
¬
g (H + λI) g
1
≤−
+
(D.3)
2
1000κ3 L2
­
g > (H + λ∗ I)−1 g
1
+ Lkgk2 k(H + λI)−1 kk(H + (λ + 2Lε̃)I)−1 kε̃ +
≤−
2
1000κ3 L2
>
∗
−1
®
g (H + λ I) g
1
≤−
+
2
500κ3 L2
Above, inequalities ¬ and ® use the assumption on ε̃ in (6.1), and inequality ­ uses

g>v +

−(H + λI)−1  −(H + (λ∗ + Lε̃)I)−1

= −(H + λ∗ I)−1 − Lε̃(H + λ∗ I)−1 (H + (λ∗ + Lε̃)I)−1

Note that (H + λ∗ I)−1  0 by Equations (D.1) and (6.2). The second part of (D.2) can be bounded
as follows




Lkvk
(2λ∗ − 5Lε̃)2 λ∗ − Lε̃ 2λ∗ + 5Lε̃
2 λ
kvk
−
≥
−
2
6
L2
2
6
∗
3
∗
3
¬
2(λ )
2(λ )
1
≥
− 1000ε̃L(λ∗ )2 ≥
−
3L2
3L2
500κ3 L2
17

Above, inequality ¬ uses λ∗ ≤ B (owing to Proposition 5.3) and our assumption on ε̃ from (6.1).
Putting these together we get that
1
m(v) ≤ m(h∗ ) +
.
250κ3 L2

D.2

Proofs for Claims 6.2 and 6.3

For notational simplicity, let us rotate the space into the basis in the eigenspace of H; let the i-th
dimension correspond to the i-th largest eigenvalue λi of H. We have λ1 ≥ λ2 . . . ≥ λd = λmin . Let
gi denote the i-th coordinate of g in this basis.
Lemma 5.1 implies
m(h∗ ) = −
where we denote by
S1 = −

1 X gi2
2(λ∗ )3
2(λ∗ )3
−
=:
S
+
S
−
.
1
2
2
λi + λ∗
3L2
3L2

(D.4)

i

X

1
i:λi +λ∗ ≥ κ

gi2
λi + λ∗

From Corollary 5.2 we can also obtain
X

i:λi +λ∗ >0

Now the assumption k(H + λI)−1 gk ≤

S2 = −

X

1
i:0<λi +λ∗ ≤ κ

gi2
λi + λ∗

gi2
4(λ∗ )2
≤
.
(λi + λ∗ )2
L2

(D.5)

2λ
L

is equivalent to
X
gi2
4λ2
≤
(λi + λ)2
L2

(D.6)

i

We begin with a few auxiliary claims.
Claim D.1. If λmin (H) ≤ − κ1 then S2 ≥ 1000 · m
Proof of Claim D.1. We compute that
X
gi2
S2 = −
=−
λi + λ∗
∗ 1
i:0<λi +λ ≤ κ

X

1
i:0<λi +λ∗ ≤ κ



λvmin
2L



gi2 (λi + λ∗ )
1
≥−
∗
2
(λi + λ )
κ

X

1
i:0<λi +λ∗ ≤ κ

gi2
(λi + λ∗ )2

­
4
|λmin |3
∗ 2
(λ
)
≥
−16
.
(D.7)
κL2
L2
Above, ¬ uses (D.5), and ­ follows because we have λmin (H) ≤ − κ1 in the assumption and have
λ∗ ≤ −λmin (H) + κ1 in the assumption of Case 2 of Main Lemma 1.
¬

≥−

min
Let us now consider the value of the vector λv2L
. We have that


> Hv
λvmin
λg > vmin λ2 vmin
λ3 ¬ λg > vmin λ2 λmin
λ3
min
m
=
+
+
≤
+
+
2L
2L
8L2
48L2
2L
16L2
48L2
­ λg > vmin
λ2 λmin λ2 λmin
λg > vmin λ2 λmin
≤
+
−
≤
+
2L
16L2
24L2
2L
48L2
1
Above, ¬ is because our assumption λmin (H) ≤ − κ and assumption vmin Hvmin ≤ λmin (H) +
1
1
together imply vmin Hvmin ≤ λmin
2 . ­ follows from λmin (H) ≤ − κ and λ ≤ −λmin (H) + κ .

1
10κ

Now, recall that the sign of vmin is chosen so g > vmin is non-positive, and therefore by our
18

assumptions λmin (H) ≤ − κ1 and λ ≤ −λmin (H) + κ1 , we get the following inequality:


λvmin
|λmin |3
m
≤−
2L
48L2
Putting inequalities (D.8) and (D.7) together finishes the proof of Claim D.1.

(D.8)

We also show the following lemma, the proof of which can be seen from inequality (D.3), as
part of the proof of Claim 6.1 above.
Lemma D.2. If we have λ, v such that
Lk(H + λI)−1 gk ≤ 2λ

and

with ε̃ satisfying condition (6.1) then we have that
g>v +
Claim D.3. S1 ≥ 4m(v) −

kv + (H + λI)−1 gk ≤ ε̃

v > (H + λI)v
g > (H + λI)−1 g
1
≤−
+
2
2
1000κ3 L2
1
250κ3 L2

Proof of Claim D.3. We have that
v > (H + λI)v λ
L
m(v) = g > v +
− kvk2 + kvk3
2
2
6


>
−1
g (H + λI) g
L
1
¬
2 λ
=−
− kvk
− kvk +
2
2
6
1000κ3 L2




­
g > (H + λI)−1 g
2λ − 3Lε̃ 2 λ Lε̃
1
≤−
−
+
+
2
L
6
3
1000κ3 L2
®
2λ3
1
g > (H + λI)−1 g
−
+
≤−
2
3L2 500κ3 L2
g > (H + λI)−1 g
1
≤−
+
(D.9)
2
500κ3 L2
Above, ¬ is due to Lemma D.2; ­ uses our condition on v which gives Lkvk ∈ [2λ − 3Lε̃, 2λ + 3Lε̃];
® uses our condition (6.1) on ε̃.
We now bound S1 . For this purpose first we note that if λi + λ∗ ≥
2(λi + λ∗ ) ≥ 1/κ + λi + λ∗ ≥ λi + λ .

Therefore, the sum S1 satisfies
X
gi2
S1 = −
≥ −2
λi + λ∗
∗ 1
i:λi +λ ≥ κ

X

1
i:0<λi +λ∗ ≤ κ

1
κ

and λ − λ∗ ≤

1
κ

then

gi2
1
≥ −2(g > (H + λI)−1 g) ≥ 4m(v) −
(λi + λ)
250κ3 L2

(Note that we have H + λI  0.) This finishes the proof of Claim D.3.
n

o
min
Claim 6.2. If λmin (H) ≤ − κ1 then m(h∗ ) ≥ 1500 min m(v), m λv2L
−

1
500κ3 L2

Proof of Claim 6.2. We derive that
2(λ∗ )3 ­ 1
16|λmin |3
¬ 1
m(h∗ ) = (S1 + S2 ) −
≥
(S
+
S
)
−
1
2
2
2
3L2
2 
 3L
®
1
λvmin
16|λmin |3
≥ 2m(v) −
+
500
·
m
−
500κ3 L2
2L
3L2


¯
1
λvmin
≥ 2m(v) −
+ 1500 · m
3
2
500κ L
2L
19




1
λvmin
−
≥ 1500 min m(v), m
2L
500κ3 L2

Above, ¬ uses equation (D.4), inequality ­ follows because we have λmin (H) ≤ − κ1 in the assumption and have λ∗ ≤ −λmin (H) + κ1 in the assumption of Case 2 of Main Lemma 1; inequality ® uses
Claim D.3 and Claim D.1; and inequality ¯ uses (D.8). This finishes the proof of Claim 6.2.
Claim 6.3. If λmin (H) ≥ − κ1 then m(h∗ ) ≥ 2m(v) −

16
κ3 L2

Proof of Claim 6.3. This time we lower bound S2 slightly differently:
¬
­
4
16
S2 ≥ − 2 (λ∗ )2 ≥ − 3 2
(D.10)
κL
κ L
where ¬ comes from the second to last inequality from (D.7) and ­ comes from λ∗ ≤ λ ≤
−λmin (H) + κ1 ≤ κ2 using our assumption in Case 2 of Main Lemma 1.
Putting these together we get that
2(λ∗ )3 ­
1
15
16
¬ 1
≥ 2m(v) −
− 3 2 ≥ 2m(v) − 3 2 .
m(h∗ ) = (S1 + S2 ) −
2
3
2
2
3L
500κ L
κ L
κ L

Above, ¬ comes from (D.4), ­ uses Claim D.3, lower bound (D.10) and

E

2(λ∗ )3
3L2

≤

16
3κ3 L2

Proof of Main Lemma 2
3/2

ε √
. Then the
Main Lemma 2. In the same setting as Main Lemma 1, suppose m(h∗ ) ≥ − 300
L
output vector v satisfies the following conditions:
3
ε
15
kvk ≤ kh∗ k +
and k∇m(v)k ≤ + 2 .
κL
4 κ L

Proof of Main Lemma 2. Let’s first note that from the value given in Lemma 5.1,
(λ∗ )3 ≤

L3/2 ε3/2
3L2 |m(h∗ )|
≤
.
2
200

(E.1)

If Case 1 occurs, we have
® 2λ∗
¯
2λ + 2Lε̃
1
+ ε̃ ≤
+ 5ε̃ ≤ kh∗ k +
.
L
L
20κL
Above, inequalities ¬ and ­ both use the assumptions of Case 1; inequality ® uses the fact that
λ∗ ∈ [λ − Lε̃, λ + Lε̃] which again follows from the assumptions of Case 1 (see (D.1)); inequality ¯
∗
uses kh∗ k = 2λL from Lemma 5.1 as well as our assumption (6.1) on ε̃.
¬

­

kvk ≤ k(H + λI)−1 gk + ε̃ ≤

As for the quantity k∇m(v)k, we bound it as follows
¬
Lkvk
k∇m(v)k = g + Hv +
v ≤ kg + (H + λI)vk + λkvk + Lkvk2
2
­
®
λ(2λ + 3Lε̃) + (2λ + 3Lε̃)2
≤ kH + λIkε̃ + λkvk + Lkvk2 ≤ (L2 + 2B)ε̃ +
L
2
∗
2
¯
6λ
6(λ + Lε̃)
= (L2 + 2B)ε̃ +
+ 15ε̃λ + 9Lε̃2 ≤
+ (L2 + 32B)ε̃ + 9Lε̃2
L
L
° 6(λ∗ )2
± ε
15
≤
+ (L2 + 56B)ε̃ + 15Lε̃2 ≤ + 2 .
L
4 κ L
Above, inequality ¬ uses triangle inequality; inequality ­ uses kv + (H + λI)−1 gk ≤ ε̃; inequality ®
uses kH + λIk ≤ L2 + 2B and Lkvk ≤ 2λ + 3Lε̃ which comes from our upper bound on kvk above;
¯ uses the fact that λ∗ ∈ [λ − Lε̃, λ + Lε̃] which again follows from the assumptions of Case 1 (see
20

(D.1)); inequality ° uses λ∗ ≤ 2B; and inequality ± uses (E.1) together with our assumption (6.1)
on ε̃.
If Case 2 occurs, we have
® 2(λ∗ + 1/κ)
2λ
3
+ ε̃ ≤
+ ε̃ ≤ kh∗ k +
.
(E.2)
L
L
κL
Above, inequalities ¬ and ­ both use the assumptions of Case 2; inequality ® uses λ ≤ −λmin (H)+
1/κ from our assumption of Case 2 as well as −λmin (H) ≤ λ∗ which comes from Lemma 5.1;
∗
inequality ¯ uses kh∗ k = 2λL from Lemma 5.1 as well as our assumption (6.1) on ε̃.
¬

­

kvk ≤ k(H + λI)−1 gk + ε̃ ≤

The quantity k∇m(v)k can be bounded in an analogous manner as Case 1:

λ(2λ + Lε̃) + (2λ + Lε̃)2
L
∗ + 1 )2
∗
2
¬ 6λ2
­
6(λ
1
1
12(λ )
15 ® ε
15
κ
+
+
≤
+ 2 ≤ + 2 .
≤
≤
2
2
L
10κ L
L
10κ L
L
κ L
4 κ L
Above, inequality ¬ uses our assumption (6.1) on ε̃; inequality ­ uses λ ≤ λ∗ + κ1 which appeared
in (E.2); inequality ® uses (E.1).
k∇m(v)k ≤ kH + λIkε̃ + λkvk + Lkvk2 ≤ (L2 + 2B)ε̃ +

F

Proof of Lemma 7.2

Lemma 7.2. The following statements hold for all i until FastCubicMin terminates
(a) λi ∈ [0, 2B], λi + λmax (H) ≤ 3B
(b) λi + λmin (H) ≥

(c) λi+1 + λmin (H)

3
10κ
≤ 34 (λi

+ λmin (H)) unless λi+1 = 0

Moreover when FastCubicMin terminates at Line 20 we have λi + λmin (H) ≤ κ1 .
Proof of Lemma 7.2. The lemma follows via induction.
To see (a) and (b) at the base case i = 0, recall that the definitions of B and L2 together ensure
3
λ0 + λmax (H) ≤ 3B and λ0 + λmin (H) ≥ 10κ
. Also λ0 ∈ [0, 2B].

Suppose now for some i ≥ 0 properties (a) and (b) hold. It is easy to check that λi ≤ λi−1
and thus we have λi + λmax (H) ≤ 2B and λi ≤ 2B. This implies property (a) at iteration i + 1
also hold. We now proceed to show property (c) at iteration i and property (b) at iteration i + 1.
Recall that the algorithm ensures
9
λmax ((H + λi I)−1 ) ≤ w> (H + λi I)−1 w ≤ λmax ((H + λi I)−1 ) ,
10
and by the definition of w̃ we have
9
λmax ((H + λi I)−1 ) − 2ε̂ ≤ w̃> w − ε̂ ≤ λmax ((H + λi I)−1 ) .
(F.1)
10
3
≤ λi + λmin (H) ≤ 3B from the inductive assumption, it follows from the choice of
Now, since 10κ
ε̂ that
1
1
λmax ((H + λi I)−1 )
2ε̂ ≤
≤
=
.
(F.2)
30B
10(λi + λmin (H))
10
Plugging Equation (F.2) into Equation (F.1) we get
8
1
8
1
= λmax ((H + λi I)−1 ) ≤ w̃> w − ε̂ ≤ λmax ((H + λi I)−1 ) =
.
10 λi + λmin (H)
10
λi + λmin (H)
21

Inverting this chain of inequalities, we have
λi + λmin (H)
5(λi + λmin (H))
≤∆≤
.
(F.3)
2
8
From this we derive the following implications:
1
1
∆≤
=⇒ (λi + λmin (H)) ≤
(F.4)
2κ
κ
1
4
∆>
=⇒ (λi + λmin (H)) >
(F.5)
2κ
5κ
If Condition (F.4) happens, our algorithm FastCubicMin outputs on Line 20; in such a case (F.4)
implies our desired inequality λi + λmin (H) ≤ κ1 . If Condition (F.5) happens, our choice λ̃i+1 ←
λi − ∆
2 and Equation (F.3) together imply that
3
11
(λi + λmin (H)) ≥ λ̃i+1 + λmin (H) ≥ (λi + λmin (H))
4
16
Combining this with (F.5) we get that
 
3
11 4
3
(λi + λmin (H)) ≥ λ̃i+1 + λmin (H) ≥
≥
.
4
16 5κ
10κ
Therefore, we conclude that property (c) at iteration i holds and property (b) at iteration i + 1
hold because λi+1 ≥ λ̃i+1 . This finishes the proof of Lemma 7.2.

G

Proof of Main Lemma 3: Running Time Half

Having proven the correctness of the algorithm, we now aim to bound the overall running time
of FastCubicMin, completing the proof of Main Lemma 3. We prove in Appendix H the following
lemma:

2 )B
Lemma G.1. If λ2 +λmin (H) ≥ c1 ∈ (0, 1) then BinarySearch ends in O log( (λc11−λ
·L·ε̃ ) iterations.

3
Since in our FastCubicMin algorithm, it satisfies λi ≤ 2B and λi +λmin (H) ≥ 10κ
(see Lemma 7.2),
taken together with our choice of ε̃ we have:

Claim G.2. Each invocation of BinarySearch ends in O log(1/ε̃) iterations.

Claim G.3. FastCubicMin ends in at most O(log(Bκ)) outer loops.

Proof. According to Lemma 7.2 we have 43 (λi−1 + λmin (H)) ≥ λi + λmin (H) so the quantity λi +
λmin (H) decreases by a constant factor per iteration (except possibly λi = 0 the last outer loop
in which case we shall terminate in one more iteration). On one hand, we have began with λ0 +
3
according to Lemma 7.2.
λmin (H) ≤ 3B. On the other hand, we always have λi + λmin (H) ≥ 10κ
Therefore, the total number of outer loops is at most O(log(Bκ)).

G.1

Matrix Inverse

Since the key component of the running time is the computation of (H+λi I)−1 b for different vectors
b we will first bound the condition number of the matrix (H + λi I)−1 via the following lemma
Claim G.4. Through out the execution of FastCubicMin and BinarySearch whenever we compute
λi +L2
(H + λi I)−1 b for some vector b it satisfies λi +λ
≤ 10κL2 .
min (H)
Proof of Claim G.4. We first focus on Line 5 and Line 11 of FastCubicMin. There are two cases. If
λi +L2
λi ≥ 2L2 , then according to −L2 I  H  L2 I we can bound λi +λ
≤ 3 because the left hand
min (H)
22

side is the largest when λi = 2L2 . If λi < 2L2 , then by Lemma 7.2 we know λi + λmin (H) ≥
λi +L2
This implies λi +λ
≤ 10κL2 .
min (H)

3
10κ .

We now focus on Line 3 of BinarySearch. We claim that all values λmid iterated over BinarySearch
3
3
also satisfy λmid + λmin (H) ≥ 10κ
(because the values λmid ≥ λi and λi satisfies λi + λmin (H) ≥ 10κ
according to Lemma 7.2). Therefore, the same case analysis (with respect to λmid ≥ 2L2 and
λi +L2
λmid < 2L2 ) also gives λi +λ
≤ 10κL2 .
min (H)
Claim G.5. Line 5 of FastCubicMin and Line 3 of BinarySearch runs in time Õ(Tinverse (κL2 , ε̃)).
Proof. Whenever we compute (H + λi I)−1 b for some vector v it satisfies kbk ≤ 1/ε̃; therefore to
find v satisfying kv + (H + λi I)−1 bk ≤ ε̃ it suffices to find kv + (H + λi I)−1 bk ≤ ε̃2 kbk. This costs
a total running time Õ(Tinverse (κL2 , ε̃)) according to Theorem 2.4.
Therefore by Theorem 2.4, every time we need to multiply a vector v to (H + λI)−1 to error
δ, the time required to approximately solve such a system is Tinverse (O(κL2 ), δ). We will state our
running time with respect to Tinverse as it is the dominant operation in the algorithm.

G.2

Power Method

We now bound the running time of Power Method in Line 11 of FastCubicMin. It is a folklore (cf. [3,
Appendix A]) that getting any constant multiplicative approximation to the leading eigenvector
of any PSD matrix M ∈ Rd×d requires only O(log d) iterations, each computing Mb for some
vector b. In our case, we have M = (H + λi I)−1 so we cannot compute Mb exactly. Fortunately,
folklore results on inaccurate power method suggests that, as long as each Mb is computed to a
very good accuracy such as ε̃−Ω(log d) , then we can still get a constant multiplicative approximate
leading eigenvector that satisfies Line 11 of FastCubicMin. Ignoring all the details (which are quite
standard and can be found for instance in [3, Appendix A]), we claim that

Claim G.6. Line 11 of FastCubicMin runs in time Õ Tinverse κL2 , ε−Θ(log(d)) = Õ (Tinverse (κL2 , ε)).

G.3

Lowest Eigenvector

We will now focus on the running time for the computation of the lowest eigenvector of the Hessian
which is required in Line 18. We recall Theorem 2.5 from Section 2 which uses Shift and Invert to
compute the largest eigenvalue of a matrix.
Since we are concerned with the lowest eigenvector of H and by assumption −L2 I  H  L2 I,
2I
we can equivalently compute the largest eigenvector of M , I − H+L
which satisfies 0  M  I.
2L2
Note that computing Mv is of the same time complexity as computing Hv. By setting ε = δ× = 0.01
κL2
in Theorem 2.5 and running AppxPCA, we obtain a unit vector w such that
¬
λmin (H) + L2
w> Hw + L2
= w> Mw ≥ (1 − 2δ× )λmax (M) ≥ λmax (M) − 2δ× ≥ 1 −
− 2δ×
2L2
2L2
Above, ¬ uses λmax (M) ≤ 1. Rearranging the terms we obtain w> Hw ≤ λmin (H) + 0.05κ as
desired. In sum,

1−

Claim G.7. The approximate lowest eigenvector computation on Line 18 runs in time Õ (Tinverse (κL2 , ε̃)).

G.4

Putting It All Together

Running-Time Proof of Main Lemma 3. Putting together our bounds in Claim G.2 and Claim G.2
which bound the number of iterations, as well as our bounds in Claim G.6, Claim G.5, and
Claim G.7 for power method, matrix inverse, and lowest eigenvectors, we conclude that our total
23

running time of FastCubicMin is at most Õ (Tinverse (κL2 , ε̃)), where Õ contains factors polylogarithmic in κ, L, L2 , B, d.
By putting together our choice of ε̃ in Line 2 as well as the running time of either accelerated
gradient descent or accelerated SVRG from Theorem 2.4 into formula O(κL2 , ε̃), we finish the proof
of the running time part for Main Lemma 3.

H

Proof of Lemma G.1


2 )B
Lemma G.1. If λ2 +λmin (H) ≥ c1 ∈ (0, 1) then BinarySearch ends in O log( (λc11−λ
·L·ε̃ ) iterations.
Proof of Lemma G.1. We first note that in all iterations of BinarySearch it always satisfies
Lk(H + λ1 I)−1 gk ≤ 2λ1

and

Lk(H + λ2 I)−1 gk ≥ 2λ2 .

(H.1)

This is true at the beginning. In each of the follow-up iterations, if we have set λ1 ← λmid then it
must satisfy Lkvk + Lε̃ ≤ 2λmid but this implies Lk(H + λmid I)−1 gk ≤ 2λmid according to triangle
inequality and kv + (H + λmid I)−1 gk ≤ Lε̃; similarly, if we have set λ2 ← λmid then it must satisfy
Lk(H + λmid I)−1 gk ≥ 2λmid .
2
Suppose now the loop has run for at least log2 ( λ1 −λ
ε̂ ) iterations where ε̂ ,
satisfy λ1 − λ2 ≤ ε̂. At this point, we compute

and therefore

Lε̃c1
40B .

Then, it must

(H + λ1 I)−1 = (H + λ2 I)−1 − (λ1 − λ2 )(H + λ2 I)−1 (H + λ1 I)−1

Lk(H + λ1 I)−1 gk ≥ Lk(H + λ2 I)−1 gk − Lk(λ1 − λ2 )(H + λ2 I)−1 (H + λ1 I)−1 gk
­

¬

≥ 2λ2 − ε̂k(H + λ2 I)−1 k · 2λ1 ≥ 2λ1 − 2ε̂ − ε̂k(H + λ2 I)−1 k · 2λ1

Above, inequality ¬ uses (H.1) and λ1 − λ2 ≤ ε̂; inequality ­ uses again λ1 − λ2 ≤ ε̂.

Now, we notice that k(H + λ2 I)−1 k ≤ c11 and λ1 ≤ 2B because λ2 only increases and λ1 only
ε̃c1
decreases through the execution of the algorithm. Therefore by the choice of ε̂ = 40B
, we get
Lk(H + λ1 I)−1 gk ≥ 2λ1 − Lε̃/5 .

A completely analogous argument also shows that

Lk(H + λ2 I)−1 gk ≤ 2λ2 + Lε̃/5 .

Therefore, in the immediate next iteration when picking λmid ← (λ1 + λ2 )/2, it must satisfy
2λmid − Lε̃/2 ≤ 2λ − Lε̃/5 ≤ Lk(H + λmid I)−1 gk ≤ 2λ2 + Lε̃/5 ≤ 2λmid + Lε̃/2 .

Then, at this iteration when v is computed to satisfy kv + (H + λmid I)−1 gk ≤ ε̃/2, we also have
2λmid − Lε̃ ≤ Lkvk ≤ 2λmid + Lε̃

which means BinarySearch will stop in this iteration. In sum, we have concluded that there will be
2 )B
no more than O log( (λc11−λ
·L·ε̃ ) iterations.

Acknowledgements

We thank Ben Recht for helpful suggestions and corrections to a previous version.

References
[1] Naman Agarwal, Brian Bullins, and Elad Hazan. Second order stochastic optimization for
machine learning in linear time. arXiv preprint arXiv:1602.03943, 2016.
24

[2] Zeyuan Allen-Zhu and Elad Hazan. Variance Reduction for Faster Non-Convex Optimization.
In ICML, 2016.
[3] Zeyuan Allen-Zhu and Yuanzhi Li. Even Faster SVD Decomposition Yet Without Agonizing
Pain. In NIPS, 2016.
[4] Zeyuan Allen-Zhu and Yang Yuan. Improved SVRG for Non-Strongly-Convex or Sum-of-NonConvex Objectives. In ICML, 2016.
[5] Afonso S Bandeira, Nicolas Boumal, and Vladislav Voroninski. On the low-rank approach
for semidefinite programs arising in synchronization and community detection. arXiv preprint
arXiv:1602.04426, 2016.
[6] S. Bhojanapalli, B. Neyshabur, and N. Srebro. Global Optimality of Local Search for Low
Rank Matrix Recovery. ArXiv e-prints, May 2016.
[7] Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. Accelerated methods for
non-convex optimization. arXiv preprint 1611.00756, 2016.
[8] Coralia Cartis, Nicholas IM Gould, and Philippe L Toint. Adaptive cubic regularisation methods for unconstrained optimization. part i: motivation, convergence and numerical results.
Mathematical Programming, 127(2):245–295, 2011.
[9] Coralia Cartis, Nicholas IM Gould, and Philippe L Toint. Adaptive cubic regularisation methods for unconstrained optimization. part ii: worst-case function-and derivative-evaluation complexity. Mathematical Programming, 130(2):295–319, 2011.
[10] Anna Choromanska, Mikael Henaff, Michael Mathieu, Gérard Ben Arous, and Yann LeCun.
The loss surfaces of multilayer networks. In AISTATS, 2015.
[11] Yann N Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and
Yoshua Bengio. Identifying and attacking the saddle point problem in high-dimensional nonconvex optimization. In Advances in neural information processing systems, pages 2933–2941,
2014.
[12] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning
and stochastic optimization. The Journal of Machine Learning Research, 12:2121–2159, 2011.
[13] Dan Garber and Elad Hazan. Fast and simple PCA via convex optimization. ArXiv e-prints,
September 2015.
[14] Dan Garber, Elad Hazan, Chi Jin, Sham M. Kakade, Cameron Musco, Praneeth Netrapalli,
and Aaron Sidford. Robust shift-and-invert preconditioning: Faster and more sample efficient
algorithms for eigenvector computation. In ICML, 2016.
[15] Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points—online
stochastic gradient for tensor decomposition. arXiv:1503.02101, 2015.
[16] Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points—online
stochastic gradient for tensor decomposition. In Proceedings of the 28th Annual Conference
on Learning Theory, COLT 2015, 2015.
25

[17] Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points - online
stochastic gradient for tensor decomposition. In Proceedings of The 28th Conference on Learning Theory, COLT 2015, Paris, France, July 3-6, 2015, pages 797–842, 2015.
[18] Rong Ge, Jason Lee, and Tengyu Ma. Matrix Completion has No Spurious Local Minimum.
ArXiv e-prints, May 2016.
[19] Rong Ge and Tengyu Ma. On the optimization landscape of tensor decompositions, 2016.
[20] Saeed Ghadimi and Guanghui Lan. Accelerated gradient methods for nonconvex nonlinear
and stochastic programming. Mathematical Programming, pages 1–26, feb 2015.
[21] I. J. Goodfellow, O. Vinyals, and A. M. Saxe. Qualitatively characterizing neural network
optimization problems. ArXiv e-prints, December 2014.
[22] Elad Hazan and Tomer Koren. A linear-time algorithm for trust region problems. Mathematical
Programming, pages 1–19, 2015.
[23] Christopher J. Hillar and Lek-Heng Lim. Most tensor problems are np-hard. J. ACM, 60(6):45,
2013.
[24] Jason D. Lee, Max Simchowitz, Michael I. Jordan, and Benjamin Recht. Gradient descent only
converges to minimizers. In Proceedings of the 29th Conference on Learning Theory, COLT
2016, New York, USA, June 23-26, 2016, pages 1246–1257, 2016.
[25] Katta G Murty and Santosh N Kabadi. Some np-complete problems in quadratic and nonlinear
programming. Mathematical programming, 39(2):117–129, 1987.
[26] Yurii Nesterov. A method of solving a convex programming problem with convergence rate
O(1/k 2 ). In Doklady AN SSSR (translated as Soviet Mathematics Doklady), volume 269, pages
543–547, 1983.
[27] Yurii Nesterov. Introductory Lectures on Convex Programming Volume: A Basic course, volume I. Kluwer Academic Publishers, 2004.
[28] Yurii Nesterov and Boris T Polyak. Cubic regularization of newton method and its global
performance. Mathematical Programming, 108(1):177–205, 2006.
[29] Barak A Pearlmutter. Fast exact multiplication by the hessian. Neural computation, 6(1):147–
160, 1994.
[30] Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of
mathematical statistics, pages 400–407, 1951.
[31] David E Rumelhart, Geoffrey E Hinton, and Ronald J Williams. Learning representations by
back-propagating errors. Cognitive modeling, 5(3):1, 1988.
[32] Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic
average gradient. arXiv preprint arXiv:1309.2388, pages 1–45, 2013. Preliminary version
appeared in NIPS 2012.
[33] Shai Shalev-Shwartz. SDCA without Duality, Regularization, and Individual Convexity. In
ICML, 2016.
26

[34] Jonathan Richard Shewchuk. An introduction to the conjugate gradient method without the
agonizing pain, 1994.
[35] Paul Werbos. Beyond regression: New tools for prediction and analysis in the behavioral
sciences. 1974.

27

