Katyusha X: Practical Momentum Method for
Stochastic Sum-of-Nonconvex Optimization

arXiv:1802.03866v1 [cs.LG] 12 Feb 2018

(version 1)
Zeyuan Allen-Zhu
zeyuan@csail.mit.edu
Microsoft Research AI
February 9, 2018
Abstract
The problem of minimizing sum-of-nonconvex functions (i.e., convex functions that are average of non-convex ones) is becoming increasingly important in machine learning, and is the core
machinery for PCA, SVD, regularized Newton’s method, accelerated non-convex optimization,
and more.
We show how to provably obtain an accelerated stochastic algorithm for minimizing sumof-nonconvex functions, by adding one additional line to the well-known SVRG method. This
line corresponds to momentum, and shows how to directly apply momentum to the finite-sum
stochastic minimization of sum-of-nonconvex functions. As a side result, our method enjoys
linear parallel speed-up using mini-batch.

1

Introduction

The diverse world of non-convex machine learning tasks have given rise to numerous non-convex
optimization problems. Some of them are perhaps as hard as minimizing general non-convex objectives (such as deep learning), but some others may be only slightly harder than convex optimization
(such as matrix completion, principal component analysis, dictionary learning, etc). Therefore, it is
both interesting and challenging to identify classes of optimization problems that interplay between
non-convex and convex optimization, and (hopefully) optimally and practically solving them.
At least tracing back to 2015, Shalev-Shwartz [27] identified a class of functions that are convex,
but can be written as finite average of non-convex functions. That is,1
n

1X
min f (x) =
fi (x)
n
x∈Rd

(1.1)

i=1

P
where each fi (x) is smooth and non-convex, but their average f (x) = n1 ni=1 fi (x) is convex.
We say f (x) a sum-of-nonconvex (but convex) function following [11, 14].
In this paper, we show how to provably obtain an accelerated and stochastic method for minimizing (1.1). Our new method is based on adding only one additional line to the well-known
SVRG (stochastic variance-reduction gradient) method [16, 32]. This additional line corresponds
to momentum. To the best of our knowledge, this explains for the first time how to directly apply

P
def
In fact, we study a more general composite minimization setting minx∈Rd F (x) = ψ(x) + n1 i∈[n] fi (x) where
ψ(x) is some proper convex function. In this high-level introduction, we ignore the ψ(·) term for simplicity.
1

1

momentum to the stochastic minimization of sum-of-nonconvex functions. We hope this new algorithm and the new insight of this paper could facilitate our understanding towards how to correctly
and provably apply momentum to non-convex machine learning tasks.

1.1

Motivating Examples

There is an increasing number of machine learning tasks that are found reducible to minimizing sumof-nonconvex functions. For most such tasks, the only known approach for achieving accelerated
stochastic performance relies on solving Problem (1.1).
Perhaps
example is the shift-and-invert approach to solve PCA [26]. Let
P the most famous
d×d be some covariance matrix and λ be its largest eigenvalue. Then,
A = n1 ni=1 ai a>
∈
R
i
computing A’s top eigenvector reduces to applying power method to a new matrix B = (µI − A)−1
with µ = λmax (A) · (1 + δ) for some approximation parameter δ > 0 [14]. In other words, PCA
def
reduces to repeatedly minimizing convex functions f (x) = 12 x> (µI − A)x + b> x for different vectors
def
>
b. If one defines fi (x) = 12 x> (µI − ai a>
i )x + b x, then fi (x) is smooth and non-convex, but f (x)
is convex.
• High Accuracy Needed. In the above reduction, we need very high accuracy (e.g., 10−10 )
when minimizing f (x), because we need to apply power method on B so the error blows up.
This is very different from classical empirical minimization problems (such as Lasso, SVM),
where we only need to minimize the training objective to some accuracy such as 10−3 .
• Necessity of Problem (1.1) While there are many algorithms to solve PCA, to the best
of our knowledge, the only known stochastic method which gives a provable accelerated rate
requires solving Problem (1.1). We discuss more in Related Works.
Other problems that reduce to Problem (1.1) include:
• The accelerated stochastic algorithms for computing top k principle components (k-PCA) and
top k singular vectors (k-SVD) require solving Problem (1.1) [7].
• The fastest way to compute the near-optimal strategy for the online eigenvector problem
(against an adversarial opponent) is by solving Problem (1.1) [9].
• Up to this date, the fastest finite-sum stochastic algorithm for finding approximate local minima of a general non-convex smooth function is either based on cubic regularized Newton’s
method [1] or a special reduction [12]. Both approaches require solving Problem (1.1).
• In certain parameter regimes, the fastest finite-sum stochastic algorithm for minimizing “approximately convex functions” is based on solving Problem (1.1) [3, 12].

1.2

Known Approaches

In the online stochastic setting (i.e., when n is infinite), there is hardly any difference between fi (x)
being convex or not. The stochastic gradient descent (SGD) method gives a T ∝ ε−2 convergence
rate to Problem (1.1), or a T ∝ (σε)−1 rate if f (x) is σ-strongly convex. Both rates are optimal,
regardless of fi (x) being convex or not. Even in the case of finding a point with small gradient,
there is no difference between fi (x) being convex or not [4].
Variance Reduction. In the finite-sum stochastic setting (i.e., when n is finite), it was discovered
by Shalev-Shwartz [27] and Garber et al. [14] that one can solve (1.1) using variance reduction: for
instance, using the SVRG method that was originally designed for convex optimization [16, 32].

2

Specifically, if f (x) is σ-strongly convex and each fi (x) is L-smooth, then the SVRG method
converges to an ε-minimizer of Problem (1.1) using Tgrad stochastic gradient computations, where
√
√ 


1
nL 
1
nL
Tgrad = O n +
log
if σ > 0 or Tgrad = O n log +
if σ = 0 .
(1.2)
σ
ε
ε
ε
Both rates outperform their corresponding counterparts in the SGD case.

Remark 1.1. The two complexity bounds in (1.2) do not seem to be recorded anywhere. In particu
2
lar, Shalev-Shwartz [27] and Garber et al. [14] showed Tgrad = O (n+ Lσ2 ) log 1ε in the case of σ > 0;
2
and Allen-Zhu and Yuan [11] showed Tgrad = O n log 1ε + Lε2 in the case of σ = 0. Both complexity
bounds are worse than (1.2). We prove (1.2) as a side result of this paper in Appendix D.
How to Accelerate. If Nesterov’s accelerated gradient
method [22, 23] (also √known as the
√


n√ L
momentum method) is used, one can achieve Tgrad = O
log 1ε and Tgrad = O n√εL in the two
σ
cases. This square-root dependence on σ or ε is known as the accelerated convergence rate.
However, Nesterov’s method is not stochastic and its Tgrad linearly scales with n. Can we design
a stochastic first-order method that also has an accelerated convergence rate?
Remark 1.2. Obtaining accelerated rates is crucial for Problem (1.1), because high accuracy is
usually needed as we discussed in Section 1.1.
This can be partially answered by the APPA [13] and Catalyst [18] reduction, that we both refer
to as Catalyst.2 Mathematically, Catalyst turns any non-accelerated method into an accelerated
one. For instance, when σ > 0, Catalyst on SVRG (often referred to as AccSVRG) uses the
following logic:

√
0
— Define a “new problem” arg minx f (x) + L2 kx − x
bk2 for some x
b ∈ Rd and L0 = L/ n.
√ 
e 1+ √L0
— Use Nesterov’s method to minimize f (x), which requires solving the “new problem” O
σ
times.
√

e n + nL
e
— Solve each “new problem” by SVRG: (1.2) gives T 0 = O
= O(n).
0
grad

L

√ 

e 1 + √L0 × T 0
. In
In total, this requires Tgrad stochastic gradient computations for Tgrad = O
grad
σ
3
other words, AccSVRG requires
√
√


n3/4 L  2 1 
n3/4 L 
1
Tgrad = O n+ √
log
if σ > 0 or Tgrad = O n+ √
log
if σ = 0 . (1.3)
ε
ε
σ
ε

Unfortunately, the practicality of AccSVRG remains somewhat unsettled. To mention a few issues:
• Since error propagates, one needs to run each SVRG until a very accurate point is obtained.

• To optimize the complexity, one needs to terminate each call of SVRG at a different accuracy.
• One needs to tune three parameters: (1) the regularizer weight L0 , (2) the learning rate of
SVRG, and (3) the weight of the momentum.
When all of these factors are putting together, the practical performance of AccSVRG may be even
worse than the non-accelerated SVRG.4
2

Both reductions are based on an outer-inner loop structure first proposed by Shalev-Shwartz and Zhang [28].
The application of Catalyst to solving Problem (1.1) first appeared in [14, 27] in the context of PCA.
3
For why these logarithmic factors show up, we refer readers to the journal version of Catalyst [19]. In particular,
one of the two log factors in the case of σ > 0 is because SVRG is a randomized algorithm.
4
This is so already in the easier case where each fi (x) is convex [2]. In this simpler case, direct acceleration
(without applying the Catalyst reduction) is more practical and already known (see Katyusha [2] and DASVRDA [21]).

3

KatyushaX-s

1E-3

KatyushaX-w

parallel speedup

objective error

SVRG
1.E-01
1.E-02
1.E-03
1.E-04
1.E-05
1.E-06
1.E-07
1.E-08
1.E-09
1.E-10
0

20

40

60

80

100

120

140

160

0

180

1E-5

1E-7

1E-9

400
350
300
250
200
150
100
50
0
100

200

300

400

500

mini-batch size b

Tgrad / n

(a) SVRG vs. KatyushaXs vs. KatyushaXw

(b) mini-batch performance of KatyushaXs

Figure 1: A simple illustration on minimizing f (x) = 12 (µI − BB > where B ∈ R1000×1000 is a random ±1 matrix,

and µ = λ1 (BB > ) + 0.5 λ1 (BB > ) − λ2 (BB > ) . Such f (x) is a typical instance in stochastic PCA [14].
Remark 1. In SVRG, the best learning rate is η = 0.4/L after tuning.
Remark 2. We used η = 0.4/L for KatyushaXw . We used η = 0.4/L and τ = 0.1 for KatyushaXs .
Remark 3. In the mini-batch experiment, we used η = 0.4b
and τ = 0.1. The parallel speed-up is in terms
L
of achieving objective error 10−3 , 10−5 , 10−7 , 10−9 .

1.3

Our Main Result

In this paper, we propose a new method KatyushaX which, copying the original SVRG method but
adding only one additional line, achieves the accelerated stochastic convergence rate. We give two
different specifications, KatyushaXs and KatyushaXw , where
• KatyushaXs needs a momentum parameter in addition to the learning rate for SVRG; and
• KatyushaXw needs no additional parameter whatsoever on top of SVRG.

We explain how they work below, and Figure 1(a) gives a quick performance comparison between
SVRG, KatyushaXs and KatyushaXw on some synthetic dataset.
We first recall how SVRG works. Each epoch of SVRG consists of n iterations. Each epoch
starts with a point w0 (known as the snapshot) where the full gradient ∇f (w0 ) is computed exactly.
e t where
Then, in each iteration t = 0, 1, . . . , n − 1 of this epoch, SVRG updates wt+1 ← wt − η ∇
e t = ∇fi (wt ) − ∇fi (w0 ) + ∇f (w0 ) for some random i ∈ [n], and η > 0 is
the gradient estimator ∇
the learning rate.
def
If we summarize the above one epoch process of SVRG as SVRG1ep (w0 , η) = wn , then
• The classical SVRG method can be described by the iterative update
xk+1 = SVRG1ep (xk , η) .
• Our KatyushaXs , parameterized by a momentum parameter τ ∈ (0, 1), is
yk ← SVRG1ep (xk , η)

and xk+1 ←

3
2 yk

+ 21 xk − (1 − τ )yk−1
.
1+τ

• Our KatyushaXw is
yk ← SVRG1ep (xk , η) and xk+1 ←

(3k + 1)yk + (k + 1)xk − (2k − 2)yk−1
.
2k + 4

Remark 1.3. When choosing τ = 1/2, KatyushaXs is exactly identical to SVRG and yk ≡ xk+1 .

Remark 1.4. In KatyushaXs , if we replace 23 yk + 12 xk with 2yk , then the update becomes xk+1 ←
4


yk + 1−τ
1+τ yk − yk−1 . This corresponds to a classical momentum scheme by Nesterov [22]. The
smaller τ > 0 is the “stronger” the momentum behaves.
Remark 1.5. KatyushaXw is in fact KatyushaXs with τ =

2
k+2

decreasing in k. See Fact 4.5.

Our main theorems are the following:
Theorem 1 (informal). If f (x) is σ-strongly
convex and each fi (x) is L-smooth, then KatyushaXs
√

1/4
with η = Θ √1nL and τ = min{ 12 , Θ( n √L σ ) outputs a point x with E[f (x) − f (x∗ )] ≤ ε using
√

n3/4 L 
1
Tgrad = O n + √
log
stochastic gradient computations.
ε
σ
Theorem 2 (informal). If f (x) is convex and each fi (x) is L-smooth, then KatyushaXw with
η = Θ √1nL outputs a point x with E[f (x) − f (x∗ )] ≤ ε using
√

n3/4 L 
Tgrad = O n + √
stochastic gradient computations.
ε

In sum, we have not only tightened the complexity bounds by removing a logarithmic factor
each (comparing to AccSVRG (1.3)), but also obtained a much simpler, practical acceleration (i.e.,
momentum) scheme for minimizing sum-of-nonconvex functions stochastically.

1.4

Our Side Results

To demonstrate the strength of KatyushaX, we prove our main theorem in several more general
settings.
(1) Upper and Lower Smoothness. For non-convex functions, its upper and lower smoothness
parameters (i.e., maximum eigenvalue vs. negated minimum eigenvalue of Hessian) may be very
different. This is especially true for all PCA and SVD related applications [7, 8, 14], where fi (x) =
µ
2
2
2
2 kxk − hai , xi so its upper smoothness is µ and lower smoothness is 2kai k . (It usually happens
that kai k2  µ.)
Assuming fi (x) is `1 -upper and `2 -lower smooth (and `2 ≥ `1 ), it is known that by simply
√
changing the learning rate of SVRG, its runs in a worst-case complexity proportional to `1 `2
instead of L [11].
We show KatyushaX enjoys this speed up as well.
KatyushaX runs in a complexity proportional to (`1 `2 )1/4 instead of L1/2 .
P
(2) Composite Minimization. Consider objective F (x) = ψ(x) + n1 ni=1 fi (x) where ψ(x) is
some proper convex (not necessarily smooth) function, usually referred to as the proximal term.5
Then, most stochastic gradient methods can be extended to minimize
composite objectives, if we

e t with wt+1 ← arg minz∈Rd 1 kz − wt k2 + h∇
e t , zi + ψ(z) .
replace the update wt+1 ← wt − η ∇
2
2η
KatyushaX also extends to the composite minimization setting.

(3) Parallelism / Mini-batch. Instead of using a single stochastic gradient ∇fi (·) per
P iteration,
for any stochastic method, one can replace it with the average of b stochastic gradients 1b i∈S ∇fi (·)
5

Examples of proximal terms include ψ(x) = kxk1 or ψ(x) =

5



0,
+∞,

x ∈ X;
x 6∈ X .

for some convex set X ⊆ Rd .

where S is a random subset of [n] with cardinality b. This is known as the mini-batch technique and
it allows the stochastic gradients to be computed in a distributed manner, using up to b processors.
Our KatyushaX methods extends to this mini-batch setting too. Using mini-batch size b,

√
O(b),
if b ≤ n;
√
√
the worst-case # parallel iterations of KatyushaX reduces by
O( b), if b ∈ [ n, n].
√
Therefore, at least for small b ∈ {1, 2, . . . , d ne}, KatyushaX enjoys a linear speed-up in the parallel
worst-case running time. We do not find such result recorded before this work.
(4) Non-Uniform Sampling. When functions fi (x) are of non-uniform hardness (say, with
different smoothness parameters), instead of sampling each function fi (x) uniformly at random, one
can sample i with a probability proportional to its “hardness.” This can improve the performance
of stochastic gradient methods.
KatyushaX also enjoys non-uniform sampling benefits.
2
If each function fP
i (x) is Li -smooth, one can sample i with probability proportional to Li . If we
2
1/2
denote by L = ( i Li /n) , then the worst-case complexities can be improved to depend on L
instead of maxi {Li }.

1.5

Other Related Works

Since sum-of-nonconvex optimization is closely related to PCA, let us mention the most standard
variants of PCA and their relationships to Problem (1.1).
P
Offline Stochastic PCA. In the offline setting, we assume A = n1 ni=1 ai a>
i and a stochastic
method can compute hai , xi for some vector x in each iteration.
To approximate the top eigenvector of A (i.e., 1-PCA), the first variance reduction method is by
Shamir [29] and does not need sum-of-nonconvex optimization. Unfortunately, his method is not
gap-free6 and not accelerated. Garber et al. [14] obtained a stochastic, gap-free, and accelerated
method by reducing 1-PCA to minimizing sum-of-nonconvex functions using shift-and-invert. To
this date, this seems to be the only approach to obtain a stochastic and accelerated method for
1-PCA.
To approximate the top k eigenvectors of A (i.e., k-PCA), the first variance reduction method is
by Shamir [30] and does not need sum-of-nonconvex optimization. His method is not gap-free, not
accelerated, and has a slow worst-case complexity. Allen-Zhu and Li [7] obtained a stochastic, gapfree, and accelerated method for k-PCA by reducing the problem to minimizing sum-of-nonconvex
functions. To this date, this seems to be the only approach to obtain a stochastic and accelerated
method for k-PCA.
Online Stochastic PCA. In the online setting, we assume A = Ei [ai a>
i ] where there may be
infinitely many vectors ai so the complexity of the stochastic method cannot depend on n.
In the case of online 1-PCA, the optimal algorithm is Oja’s method [24], whose first optimal
analysis was due to Jain et al. [15] and first optimal gap-free analysis was due to Allen-Zhu and Li
[9]. In the case of online k-PCA, the optimal algorithm is a block variant of Oja’s method, whose
first optimal analysis was due to Allen-Zhu and Li [8].
In the online stochastic setting, due to information-theoretic lower bounds [8, 9], one cannot
apply variance reduction or acceleration to improve the worst-case complexity.
Online Adversarial PCA. In an online learning scenario where the player chooses a unit vector vt
at round t and the adversary chooses a matrix At , one can design regret-minimizing strategy for the
6

We say a method is gap-free if it does not need an eigengap assumption between the top two eigenvalues.

6

P
player in terms of maximizing t vt> At v t . In this game, the regret-optimal strategy for the player
is follow-the-regularized-leader (FTRL) but it runs very slow; an efficient strategy for the player
is follow-the-perturbed-leader (FTPL) but it gives a poor regret [20]. The recent result followthe-compressed-leader (FTCL) gives a strategy that is both regret near-optimal and efficiently
computable [9]. Both strategies FTCL and FTPL rely on minimizing sum-of-nonconvex functions.
P
Stochastic Nonconvex Optimization. In the harder problem where f (x) = n1 ni=1 fi (x) is
also non-convex, variance reduction is also proven useful, both in terms of finding approximate
stationary points and approximate local minima.
In the finite-sum case (i.e., when n is finite), the SVRG method finds an ε-approximate stationary point in Tgrad = O(n2/3 /ε2 ) where in contrast SGD needs O(1/ε4 ) and full gradient descent needs O(n/ε2 ).7 This was first shown independently by Reddi et al. [25] and Allen-Zhu
and Hazan [5]. To find an ε-approximate local minima, one needs an additional second-order
smoothness assumption, and the two independent works Agarwal et al. [1], Carmon et al. [12] need
3/4 
n
Tgrad = O ε1.5
+ εn1.75 . Both these two algorithms rely on minimizing sum-of-nonconvex functions.
In the online case (i.e., when n is infinite), the SCSG method (which is a variant of SVRG) finds
an ε-approximate stationary point in Tgrad = O(1/ε3.333 ), and this was first discovered by Lei et al.
[17]. To find an ε-approximate local minima, one needs an additional second-order smoothness
assumption and the convergence rate can be improved to Tgrad = O(1/ε3.25 ) [3]. Neither algorithm
relies on sum-of-nonconvex functions, and momentum is not known to be helpful in the online
setting.
Relationship to Katyusha. We have borrowed the algorithm name from [2], where the author
obtained a direct accelerated stochastic method Katyusha for minimizing a function f (x) that is a
finite average of convex functions fi (x). The two algorithms are different:
• Katyusha applies a momentum step every iteration, but KatyushaX applies a momentum step
every epoch (i.e., every n iterations).
• KatyushaX applies to a more general class of sum-of-nonconvex functions than Katyusha.
• Katyusha gives a better complexity than KatyushaX when restricted to convex fi (x).
The two works also share some similarity.
• Both works provably and directly add momentum to a stochastic method. This can have
practical impacts.
• Both works introduces some “negative momentum” on top of SVRG. In every iteration of
Katyusha, the point retracts towards the most recent snapshot (this is achieved by a three-point
linear coupling [2]). In KatyushaX, after each epoch we applied xk+1 ←

which is different from the classical update xk+1 ←
retracting yk towards the most recent snapshot xk .

1.6

2yk −(1−τ )yk−1
.
1+τ

3
y + 1 x −(1−τ )yk−1
2 k 2 k

1+τ

This can also be viewed as

Roadmap

We give preliminaries and formalize the problem in Section 2. We give a new analyze of one epoch
of SVRG in Section 3, and then accelerate it in Section 4. We prove our main theorems in the
uniform sampling setting, and defer the non-uniform variant to Section 5.
7

In this high-level summary, we have hidden the smoothness and variance parameters inside the big-O notion.

7

2

Preliminaries

Throughout this paper, we denote by k · k the Euclidean norm. We use i ∈R [n] to denote that i
is generated from [n] = {1, 2, . . . , n} uniformly at random. We denote by ∇f (x) the gradient of
function f if it is differentiable, and ∂f (x) any subgradient if f is only Lipschitz continuous. Recall
some definitions on strong convexity and smoothness — they have other equivalent definitions, see
textbook [22].
Definition 2.1. For a function f : Rd → R,
• f is σ-strongly convex if ∀x, y ∈ Rd , it satisfies f (y) ≥ f (x) + h∂f (x), y − xi + σ2 kx − yk2 .
• f is L-Lipschitz smooth (or L-smooth for short) if ∀x, y ∈ Rd , k∇f (x) − ∇f (y)k ≤ Lkx − yk.
• f is (`1 , `2 )-smooth if for every ∀x, y ∈ Rd

− `22 kx − yk2 ≤ f (y) − f (x) + h∇f (x), y − xi ≤ `21 kx − yk2 .

A convex L-smooth function is (L, 0)-smooth; a non-convex L-smooth function is (L, L)-smooth.

2.1

Problem Formulation

Throughout this paper, we minimize the following convex stochastic composite objective over x ∈
Rd :
1 X
def
F (x) = ψ(x) + f (x) = ψ(x) +
fi (x) ,
(2.1)
n
i∈[n]

where

1. ψ(x) is proper convex (a.k.a. the proximal term).
2. Each fi (x) is differentiable and (`1 , `2 )-smooth (for `2 ≥ `1 ); and f (x) is convex and L-smooth.
3. f (x) is σf -strongly convex and ψ(x) is σψ -strongly convex,
def

Remark 2.2. Both σf , σψ can be zero, and only σ = σf + σψ needs to be known by the algorithm.
Also, we use the (`1 , `2 )-smoothness notion to provide the tightest bound possible. In a first reading,
one can simply view “`1 = `2 = L” and this case is sufficiently interesting.
In the rest of the paper, we define Tgrad , the gradient complexity, as the number of computations
of ∇fi (x); and in the mini-batch setting, we define Titer as the number of parallel iterations (where
in each iteration we can compute b stochastic gradients in parallel).

2.2

Geometric Distribution

We say N follows from geometric distribution with parameter p ∈ (0, 1], denoted by Geom(p), if
N = k with probability (1 − p)k p for each k ∈ {0, 1, 2, . . . }. We know E[N ] = 1−p
p . We have:
Fact 2.3. Given any sequence D0 , D1 , . . . of reals, if N ∼ Geom(p), then
• EN [DN − DN +1 ] =

p
1−p E[D0

− DN ], and

• EN [DN ] = (1 − p)E[DN +1 ] + pD0

2.3

Proximal Mirror Descent

We recall the following classical lemma for proximal mirror descent, and its proof is classical (see
Appendix A).
8

Algorithm 1 SVRG1ep (F, w0 , b, η)
P
Input: F (x) = ψ(x)+ n1 ni=1 fi (x), starting vector w0 , mini-batch size b ∈ [n], learning rate η > 0.
Output: vector w+ .
1
1: m ← min{d nb e, 2}; M ∼ Geom( m
);
 E[M ] = m − 1, in practice just let M ← m − 1
2: µ = ∇f (w0 );
3: for t ← 0 to M do
4:
Let St be b i.i.d.
uniform random indices
 from [n] with replacement;
et ← µ + 1 P
5:
∇
∇f
(w
)
−
∇f
(w
)
t
i
0 ;
i∈St  i
b
1
e t , yi
6:
wt+1 = arg miny∈Rd ψ(y) + 2η ky − wt k2 + h∇
7: end for
8: return w + ← wM +1 .
1
Lemma 2.4. If h(·) is proper convex and σ-strongly convex and zk+1 = arg minz∈Rd { 2α
kz − zk k2 +
hξ, zi + h(z)}, then for every u ∈ Rd , we have

ku − zk k2 (1 + σα)ku − zk+1 k2 kzk − zk+1 k2
−
−
2α
2α
2α
2
2
α
ku
−
z
(1
+
σα)ku
−
z
k
k
k
k+1
≤ kξk2 +
−
.
2
2α
2α

hξ, zk − ui + h(zk+1 ) − h(u) ≤ hξ, zk − zk+1 i +

3

New Analysis of SVRG

In this section, we propose a new analysis for one epoch of SVRG specialized sum-of-nonconvex
optimization (2.1).
Recall the original design of SVRG is due to [16, 32] and its the first proximal analysis is due
to [31]. The first sum-of-nonconvex analysis for SVRG is due to [27] and its proximal analysis
seems to be due to [11]. Our analysis is going to be different from all of these cited results.
We formally specify the one epoch instance of SVRG in Algorithm 1 and call it SVRG1ep . To
provide the most general statement, we have allowed a mini-batch size b ∈ [n] to be specified as
input to SVRG1ep (and thus an epoch corresponds to ≈ nb iterations), and have allowed a proximal
term ψ(x) to exist in the stochastic gradient updates.
We define SVRG1ep so that it randomly stops in M iterations where M follows from a geometric distribution whose expectation equals ≈ nb . This is for the purpose of simplifying analysis
(motivated by Lei et al. [17]). Random stopping is not necessary in practice.8
Our main theorem of this section is:
Theorem 3.1. Let b ∈ [n] be the mini-batch size and
m = min{d nb e, 2} be the epoch length of

1
SVRG1ep . If w+ = SVRG1ep (F, w0 , b, η) where η ≤ min 2L
, √ 1
, then
2

∀u ∈ Rd :

h


E F (w+ ) − F (u) ≤ E −

Interpretation.
Denoting by G =

8

`1 `2 m/b

i
1
hw0 − w+ , w0 − ui σ +
kw+ − w0 k2 +
− kw − uk2 .
4mη
mη
4

We can interpret Theorem 3.1 as gradient descent for the following reason.
then it satisfies
h mη
i


σ
E F (w+ ) − F (u) ≤ E −
kGk2 + hG, w0 − ui − kw+ − uk2 .
(3.1)
4
4
w0 −w+
mη ,

In practice, one can simply choose M =

n
b

as fixed. This is how our experiments in Figure 1 are performed.

9


In comparison, if a full proximal gradient descent with step length L1 is applied y + = arg minz ψ(z)+
L
2
+
2 kz −yk +h∇f (y), zi}, and denote by G = L(y −y ) the so-called gradient mapping, then classical
9
theory essentially tells us:
h
i


1
σ
E F (y + ) − F (u) ≤ E −
kGk2 + hG, y − ui − ky + − uk2 .
(3.2)
2L
2
By comparing (3.1) and (3.2), we see that up to a constant factor of 2, SVRG1ep can be viewed as a
full gradient descent with a “virtual” step length mη.
We shall later use SVRG1ep (and thus Theorem 3.1) in a black-box way to obtain both accelerated
methods in Section 4 and non-accelerated ones in Appendix D.

3.1

Proof Details

Using the convexity and smoothness of our objective, as well as the definition of our stochastic
gradient step, we obtain the following standard lemma (see Appendix ??):
1
e t , yi for some random vector ∇
e t ∈ Rd
Lemma 3.2. If wt+1 = arg miny∈Rd 2η
ky−wt k2 +ψ(y)+h∇
e t ] = ∇f (wt ), then for every u ∈ Rd , we have
satisfying E[∇
h


E F (wt+1 )−F (u) ≤ E

2
2i
η
2 (1 − σf η)ku − wt k − (1 + σψ η)ku − wt+1 k
e
.
k∇t −∇f (wt )k +
2(1 − ηL)
2η

The next lemma is one of our main contributions, and can be proved by telescoping Lemma 3.2
(see Appendix B).


e t satisfies E[∇
e t ] = ∇f (wt ) and E k∇
e t − ∇f (wt )k2 ≤
Lemma 3.3. If the gradient estimator ∇
1
Qkw0 − wt k2 for every t for some universal constant Q > 0, then as long as η ≤ min 2L
, 2√1Qm ,
it satisfies
i
h


1
hw0 − w+ , w0 − ui σf + σψ +
∀u ∈ Rd : E F (w+ ) − F (u) ≤ E −
kw+ − w0 k2 +
−
kw − uk2 .
4mη
mη
4
Our next lemma (to be proved in Appendix C) shows that one can choose Q =
Lemma 3.3, and this concludes the proof of Theorem 3.1.

`1 `2
b

in

Lemma 3.4. If each fi (x) is (`1 , `2 )-smooth for `2 ≥ `1 , and the gradient estimator

et = µ + 1 P
∇
i∈St ∇fi (wt ) − ∇fi (w0 )
b

e t] =
where St consists of b i.i.d. uniform
indices from [n] with replacement. Then, ESt [∇
 `random
2
2
1 `2
e
∇f (wt ) and ESt k∇t − ∇f (wt )k ≤ b kwt − w0 k .

4

Acceleration

We give some intuitions why direct acceleration is possible using SVRG1ep in the context of σ > 0
— the σ = 0 case is similar.
Recall Nesterov’s momentum turns gradient descent with step length L1 into an algorithm with
p

O (1 + L/σ) log 1ε iterations. Since SVRG1ep can be viewed as gradient descent with a “virtual”
step length mη (see Section 3), one should hope that perhaps Nesterov’s momentum can also turn
9
See for instance [31, Lemma 3.7]. In fact, the exact statement from [31, Lemma 3.7] is by replacing
σ
σ
with 2ψ ky + − uk2 + 2f ky − uk2 . We ignore this subtle issue in this high-level interpretation.

10

σ
ky +
2

− uk2

p

SVRG1ep into an algorithm with O (1+ 1/ηmσ) log 1ε iterations. Since each call to SVRG1ep requires
computing O(n) stochastic gradients, this “wishful thinking” gives
√


p

1
Lbn + (`1 `2 )1/4 n3/4 
1
√
Tgrad = n × O 1 + 1/ηmσ log
=O n+
log
.
ε
ε
σ

This is exactly what we hope
In the case of b = 1 and `1 = `2 = L, it gives the desired
√ to3/4obtain.


−1 in Theorem 1.
√
log
ε
complexity Tgrad = O n + Ln
σ
Unfortunately, some technical issue arises. To the best of our knowledge, the constant 4 in (3.1)
—as opposed to 2 in the true gradient descent (3.2)— actually prevents the classical Nesterov’s
momentum from being applied in the worst case. In symbols, this means the standard choice
2y −(1−τ )y
xk+1 = k 1+τ k−1 does not seem to work.
3

y + 1 x −(1−τ )y

k−1
In KatyushaXs , we use xk+1 = 2 k 2 k1+τ
. Intuitively, this replaces one copy of yk with
yk +xk
in the original Nesterov’s momentum. Since xk is the last point where the full gradient is
2
exactly computed, retracting towards xk stabilizes the algorithm.
On the mathematical side, this new choice of momentum is motivated by the linear-coupling
analysis of accelerated methods [10]. In their language, we consider the following class of accelerated
methods.
General Framework

Starting from z0 = y0 = x0 , then in each iteration k = 0, 1, . . . , K − 1,
• xk+1 ← τk zk + (1 − τk )yk for some τk ∈ [0, 1];

x

(4.1)

−y

• yk+1 = SVRG1ep (F, xk+1 , b, η) and let Gk+1 = k+1mη k+1 be the gradient mapping;

• zk+1 ← arg minz∈Rd 2α1k+1 kz − zk k2 + hGk+1 , zi + σ4 kz − yk+1 k2 for some αk+1 > 0.

We will show that KatyushaXs and KatyushaXw are two instantiations of this general class of
methods, after choosing αk+1 and τk appropriately.

4.1

The Core Lemma

Our next lemma is the core lemma to show accelerated convergence rates. It is based on the linearcoupling idea of [10, Lemma 4.3], which combines analyses of gradient descent and mirror descent.
In particular, we view SVRG1ep as gradient descent (see Section 3), and view the update sequence
on {zk }k as mirror descent (see Lemma 2.4). We include its half-paged proof in Appendix ??.
αk+1
τk

mη
2τk

in the General Framework (4.1), then for every u ∈ Rd :

 (1 − τk )αk+1
 1
1 + αk+1 σ/2
F (yk+1 ) − F (u) ≤
F (yk ) − F (u) +
kzk − uk2 −
kzk+1 − uk2
τk
2
2

Lemma 4.1. If αk+1 ≤

x

−y

Proof. Denoting by Gk+1 = k+1mη k+1 , then Lemma 3.3 implies
h mη
i


σ
∀u ∈ Rd : E F (yk+1 ) − F (u) ≤ E −
kGk+1 k2 + hGk+1 , xk+1 − ui − kyk+1 − uk2 . (4.2)
4
4

11

Therefore,
¬
αk+1 mη
αk+1 σ
αk+1 F (yk+1 ) − F (u) ≤ αk+1 hGk+1 , xk+1 − ui −
kGk+1 k2 −
kyk+1 − uk2
4
4


αk+1 mη
σ
kGk+1 k2 + αk+1 hGk+1 , zk − ui − kyk+1 − uk2
= αk+1 hGk+1 , xk+1 − zk i −
4
4


(1
−
τ
)α
α
mη
σ
­
k k+1
k+1
=
hGk+1 , yk − xk+1 i −
kGk+1 k2 + αk+1 hGk+1 , zk − ui − kyk+1 − uk2
τk
4
4

® (1 − τk )αk+1 
mη
αk+1 mη
≤
F (yk ) − F (yk+1 ) −
kGk+1 k2 −
kGk+1 k2
τk
4
4
 α2

1
1 + αk+1 σ/2
k+1
+
kGk+1 k2 + kzk − uk2 −
kzk+1 − uk2
2
2
2
Above, inequality ¬ applies (4.2); equality
­ uses the definition xk+1 ← τk zk + (1 − τk )yk ; and in
x
−y
equality ® uses zk+1 = arg minz∈Rd 2α1k+1 kz−zk k2 +h k+1mη k+1 , zi+ σ4 kz−yk+1 k2 and Lemma 2.4.
Finally, rearranging terms, we have
2
 (1 − τk )αk+1
  αk+1
αk+1
αk+1 mη 
−
kGk+1 k2
F (yk+1 ) − F (u) ≤
F (yk ) − F (u) +
τk
τk
2
4τk

1
1 + αk+1 σ/2
kzk − uk2 −
kzk+1 − uk2 .

+
2
2

4.2

Strongly Convex Theorem

Algorithm 2 KatyushaXs (F, x0 , b, η, τ, K)
P
Input: function F (x) = ψ(x) + n1 ni=1 fi (x), starting vector x0 , mini-batch size b ∈ [n], learning
rate η > 0, momentum weight τ ∈ (0, 1], K number of epochs;
Output: vector xout .
1: y−1 = y0 ← x0 ;
2: for k ← 0 to K − 1 do
3
y + 1 x −(1−τ )yk−1
3:
xk+1 ← 2 k 2 k1+τ
;
1ep
4:
yk+1 ← SVRG (F, xk+1 , b, η);
5: end for
 if τ = 12 then KatyushaXs = SVRG
6: return yK .
 smaller τ > 0 means larger momentum
We formally state KatyushaXs in Algorithm 2 and observe:
Fact 4.2. The updates of KatyushaXs can be equivalently written as follows. Starting from z0 =
y0 = x0 . Then, in each iteration k = 0, 1, . . . , K − 1,
• xk+1 ← τ zk + (1 − τ )yk ;

• yk+1 ← SVRG1ep (F, xk+1 , b, η);

x
−y
• zk+1 ← arg minz∈Rd 21 kz − zk k2 + h k+12τ k+1 , zi + τ2 kz − yk+1 k2 =

1
zk +τ yk+1 − 2τ
(xk+1 −yk+1 )
.
1+τ

Proof. Can be seen by eliminating the sequence {zk }k from the recurrence.
√

mησ



2τ
If we choose τk = τ =
and αk+1 = mη
2
2τ = σ for all k ≥ 0, then Fact 4.2 tells us
s
KatyushaX falls into General Framework (4.1). One can thus telescope Lemma 4.1 carefully to
obtain:
def

12

Theorem 4.3. Let b ∈ [n] be the mini-batch size and m = min{d nb e, 2} be the epoch length of
def
SVRG1ep . If f (·) is σf -strongly convex and ψ(·) is σψ -strongly
convex for some σ = σf + σψ > 0,
√
1

mησ
then selecting η = min 2L
and τ = min 21 , 2
, √ 1
∈ (0, 12 ] in KatyushaXs , we have
2

`1 `2 m/b

F (yK ) − F (x∗ ) ≤


2
∗
F
(y
)
−
F
(x
)
.
0
(1 + τ )K

Proof. We only prove the case when mησ ≤ 1. If mησ > 1, then we can replace σ (for analysis
1
purpose only) with a smaller value mη
and the rest of the proof still holds.
√

mησ

2τ
Let us choose τk = τ = 2 and αk+1 = mη
2τ = σ for all k ≥ 0. Now, Fact 4.2 tells us that
KatyushaXs falls into General Framework (4.1) with αk+1 and τk . Using Lemma 4.1 with u = x∗
we have

 2(1 − τ )
 1
1+τ
2
F (yk+1 ) − F (x∗ ) ≤
F (yk ) − F (x∗ ) +
kzk − x∗ k2 −
kzk+1 − x∗ k2 .
σ
σ
2
2
def

Using 1 − τ ≤

1
1+τ ,

we can telescope the above inequality and get



2
1
(1 + τ )σ
∗ 2
∗
∗
kz
−
x
k
≤
F
(y
)
−
F
(x
)
F (yK ) − F (x∗ ) ≤
F
(y
)
−
F
(x
)
+
0
0
0
(1 + τ )K
4
(1 + τ )K

where the last inequality uses x0 = y0 = z0 and the strong convexity of F (·).



Corollary 4.4. If σ > 0, KatyushaXs finds a point xout satisfying E[F (xout ) − F (x∗ )] ≤ ε in
√

Lbn (`1 `2 )1/4 n3/4 
F (x0 ) − F (x∗ )
√
Tgrad = O n + √ +
· log
ε
σ
σ
computations of stochastic gradients (in expectation), or equivalently
 n √Ln (` ` )1/4 n3/4 
F (x0 ) − F (x∗ )
1 2
√
Titer = O
+ √ +
· log
b
ε
σb
σb
parallel iterations (in expectation).

In the case b = 1 and `1 = `2 = L, this implies Theorem 1.

4.3

Weakly Convex Case

Algorithm 3 KatyushaXw (F, x0 , b, η, K)
P
Input: function F (x) = ψ(x) + n1 ni=1 fi (x), starting vector x0 , mini-batch size b ∈ [n], learning
rate η > 0, K number of epochs;
Output: vector xout .
1: y−1 = y0 ← x0 ;
2: for k ← 0 to K − 1 do
(3k+1)yk +(k+1)xk −(2k−2)yk−1
;
3:
xk+1 ←
2k+4
1ep
4:
yk+1 ← SVRG (F, xk+1 , b, η);
5: end for
 momentum is auto-computed
6: return yK .
We state KatyushaXw in Algorithm 3 and observe:
13

Fact 4.5. The updates of KatyushaXw can be equivalently written as follows. Starting from z0 =
y0 = x0 . Then, in each iteration k = 0, 1, . . . , K − 1,
def

• xk+1 ← τk zk + (1 − τk )yk for τk =

2
k+2 ;

• yk+1 ← SVRG1ep (F, xk+1 , b, η);
• zk+1 ← zk −

1
2τk (xk+1

− yk+1 ) = arg minz∈Rd

1

2 kz

− z k k2 + h

xk+1 −yk+1
, zi
2τk

.

Proof. Can be seen by eliminating the sequence {zk }k from the recurrence.



mη
for all k ≥ 0 and σ = 0, then Fact 4.2 tells us KatyushaXw falls into
If we choose αk+1 = 2τ
k
General Framework (4.1). One can thus telescope Lemma 4.1 carefully to obtain:

Theorem 4.6. Let b ∈ [n] be the mini-batch size and m = min{d nb e, 2} be the epoch length of
1
SVRG1ep . Selecting η = min 2L
in KatyushaXw , we have
, √ 1
2

`1 `2 m/b

E[F (yK ) − F (x∗ )] ≤

4
kx0 − x∗ k2 .
(K + 1)2 mη

mη
2
and αk+1 = 2τ
for all k ≥ 0. Now, Lemma 4.1 with u = x∗ and
Proof. Let us choose τk = k+2
k
σ = 0 becomes

 (1 − τk )mη
 1
mη
1
∗
∗
∗ 2
∗ 2
.
F
(y
)
−
F
(x
)
≤
F
(y
)
−
F
(x
)
+
kz
−
x
k
−
kz
−
x
k
k+1
k
k
k+1
2
2
2τk2
2τk2

Using the fact that

1−τk
τk2

<

1
2
τk−1

and τ0 = 1, we can telescope the above inequality and obtain

 1
mη
F (yK ) − F (x∗ ) ≤ kz0 − x∗ k2 .
2
2
2τK−1



Corollary 4.7. KatyushaXw finds a point xout satisfying E[F (xout ) − F (x∗ )] ≤ ε in


kx0 − x∗ k √
√
Tgrad = O n +
Lbn + (`1 `2 )1/4 n3/4
·
ε
computations of stochastic gradients (in expectation), or equivalently
 n kx − x∗ k √Ln (` ` )1/4 n3/4 
0
1 2
√
Titer = O
+
· √ +
b
b
ε
b
parallel iterations (in expectation).

In the case b = 1 and `1 = `2 = L, this implies Theorem 2.

5

KatyushaX Using Non-Uniform Sampling

In this section, we consider a simple variant of Problem (2.1). Instead of assuming all functions
fi (x) have the same (`1 , `2 )-smoothness, we want to assume each fi (x) is Li -smooth for some
possibly different value Li > 0. In practical problems (such as PCA) such parameters Li may be
easily computable.10 In this setting, √
the same KatyushaXs and KatyushaXw methods still apply but
their convergence rates will scale in maxi Li .
We improve such rates by introducing non-uniform sampling. This requires only one simple
e t as follows:
change to SVRG1ep which redefines the gradient estimator ∇
10

In principle, one can more generally assume each fi (x) is (`1,i , `2,i )-smooth. Unfortunately, we do not have a
clean complexity statement for this case, so have simply assumed `1,i = `2,i = Li .

14

def

• Let distribution D be to select i ∈ [n] with probability pi =

L2
P i 2;
j Lj

• Let St be b i.i.d. samples from D with replacement;

1
et ← 1 P
• ∇
i∈St npi ∇fi (wt ) − ∇fi (w0 ) .
b
P 2 1/2
def
n
Denoting by L =
, it is easy to derive that L ≥ L1 +···+L
≥ L where L is the
i Li /n
n
smoothness of L.
e t , we have the following new variance upper bound (proved
Using this new gradient estimator ∇
in Appendix C).


e t ] = ∇f (wt ) and E k∇
e t − ∇f (wt )k2 ≤
Lemma 5.1. ESt [∇

2

L
b

kwt − w0 k2 .

2

Therefore, one can replace Q = `1b`2 as used for Lemma 3.3 with this new choice Q = Lb . The
exact same proof shows that KatyushaXs now finds a point xout satisfying E[F (xout ) − F (x∗ )] ≤ ε
in
√
1/2

Lbn L n3/4 
F (x0 ) − F (x∗ )
· log
Tgrad = O n + √ + √
ε
σ
σ
computations of stochastic gradients (in expectation), and KatyushaXw now finds a point xout
satisfying E[F (xout ) − F (x∗ )] ≤ ε in


kx0 − x∗ k √
1/2
√
Tgrad = O n +
·
Lbn + L n3/4
ε
computations of stochastic gradients (in expectation).

Appendix
A

Proofs for Section 2

Fact 2.3. Given any sequence D0 , D1 , . . . of reals, if N ∼ Geom(p), then
• EN [DN − DN +1 ] =

p
1−p E[D0

− DN ], and

• EN [DN ] = (1 − p)E[DN +1 ] + pD0

Proof. We only prove the first item since the second is by rearranging the first.
X
X

E[DN − DN +1 ] =
(Dk − Dk+1 )(1 − p)k p = pD0 +
Dk (1 − p)k p − (1 − p)k−1 p
k≥0

k≥1

p X
p
p X
p
= pD0 −
Dk (1 − p)k p =
D0 −
Dk (1 − p)k p =
E[D0 − DN ] .
1−p
1−p
1−p
1−p
k≥1



k≥0

1
Lemma 2.4. If h(·) is proper convex and σ-strongly convex and zk+1 = arg minz∈Rd { 2α
kz − zk k2 +
d
hξ, zi + h(z)}, then for every u ∈ R , we have

ku − zk k2 (1 + σα)ku − zk+1 k2 kzk − zk+1 k2
−
−
2α
2α
2α
2
2
α
ku
−
z
k
(1
+
σα)ku
−
z
k
k
k+1
≤ kξk2 +
−
.
2
2α
2α

hξ, zk − ui + h(zk+1 ) − h(u) ≤ hξ, zk − zk+1 i +

15

Proof. Recall that the minimality of zk+1 implies the existence of some subgradient g ∈ ∂h(zk+1 )
which satisfies α1 (zk+1 − zk ) + ξ + g = 0 . Combining this with h(u) − h(zk+1 ) ≥ hg, u − zk+1 i +
σ
2
2 ku − zk+1 k , which is due to the strong convexity of h(·), we immediately have
1
σ
1
h(u) − h(zk+1 ) + h (u − zk+1 ) + ξ, u − zk+1 i − ku − zk+1 k2 ≥ h (zk+1 − zk ) + ξ + g, u − zk+1 i ≥ 0 .
α
2
α
Therefore,
hξ, zk − ui + h(zk+1 ) − h(u) = hξ, zk − zk+1 i + hξ, zk+1 − ui + h(zk+1 ) − h(u)

¬
1
σ
≤ hξ, zk − zk+1 i + h− (zk+1 − zk ), zk+1 − ui − ku − zk+1 k2
α
2
ku − zk k2 (1 + σα)ku − zk+1 k2 kzk+1 − zk k2
­
−
−
= hξ, zk − zk+1 i +
2α
2α
2α
® α
ku − zk k2 (1 + σα)ku − zk+1 k2
2
≤ kξk +
−
.
2
2α
2α
Above, inequality ¬ holds for the reasons explained above; equality ­ can be verified by expanding
out the terms; and inequality ® is due to Young’s inequality.


B

Proofs for Section 3

1
e t , yi for some random vector ∇
e t ∈ Rd
Lemma 3.2. If wt+1 = arg miny∈Rd 2η
ky−wt k2 +ψ(y)+h∇
e t ] = ∇f (wt ), then for every u ∈ Rd , we have
satisfying E[∇
h
2
2i


η
e t −∇f (wt )k2 + (1 − σf η)ku − wt k − (1 + σψ η)ku − wt+1 k
k∇
.
E F (wt+1 )−F (u) ≤ E
2(1 − ηL)
2η

Proof. We first upper bound the left hand side:




E F (wt+1 ) − F (u) = E f (wt+1 ) − f (u) + ψ(wt+1 ) − ψ(u)
¬ 

≤ E f (wt ) + h∇f (wt ), wt+1 − wt i + L2 kwt − wt+1 k2 − f (u) + ψ(wt+1 ) − ψ(u)
­ 

σf
ku − wt k2 + h∇f (wt ), wt+1 − wt i + L2 kwt − wt+1 k2 + ψ(wt+1 ) − ψ(u)
≤ E h∇f (wt ), wt − ui −
2

σf
®  e
= E h∇t , wt − ui −
ku − wt k2 + h∇f (wt ), wt+1 − wt i + L2 kwt − wt+1 k2 + ψ(wt+1 ) − ψ(u) .
2
Above, inequalities ¬ and ­ are respectively due to the smoothness and strong-convexity of f (·),
e t ] = ∇f (wt ). Next, using Lemma 2.4 (with zk = wt , zk+1 = wt+1 , h(·) = ψ(·),
and ® is because E[∇
e t ) we have
ξ=∇

2
2
2
e t , wt − ui + ψ(wt+1 ) − ψ(u) ≤ h∇
e t , wt − wt+1 i + ku − wt k − (1 + σψ η)ku − wt+1 k − kwt+1 − wt k .
h∇
2η
2η
2η

Combining the above two inequalities, we have


E F (wt+1 ) − F (u)
h
2
2i
e t − ∇f (wt ), wt − wt+1 i − 1 − ηL kwt − wt+1 k2 + (1 − σf η)ku − wt k − (1 + σψ η)ku − wt+1 k
≤ E h∇
2η
2η
i
2
2
¯ h
η
e t − ∇f (wt )k2 + (1 − σf η)ku − wt k − (1 + σψ η)ku − wt+1 k
≤E
k∇
.
2(1 − ηL)
2η



Above, ¯ is by Young’s inequality.

16



e t satisfies E[∇
e t ] = ∇f (wt ) and E k∇
e t − ∇f (wt )k2 ≤
Lemma 3.3. If the gradient estimator ∇

1
Qkw0 − wt k2 for every t for some universal constant Q > 0, then as long as η ≤ min 2L
, 2√1Qm ,
it satisfies
i
h


hw0 − w+ , w0 − ui σf + σψ +
1
kw+ − w0 k2 +
−
kw − uk2 .
∀u ∈ Rd : E F (w+ ) − F (u) ≤ E −
4mη
mη
4
1
Proof. Since η ≤ 2L
, we can write Lemma 3.2 as


E F (wt+1 ) − F (u)
h
i
2
2
e t − ∇f (wt )k2 + ku − wt k − ku − wt+1 k − σf ku − wt k2 − σψ ku − wt+1 k2
≤ E ηk∇
2η
2
2
h
i
2
2
σf
σψ
ku − wt k − ku − wt+1 k
≤ E ηQkwt − w0 k2 +
−
ku − wt k2 −
ku − wt+1 k2 .
2η
2
2

(B.1)

1
) follows from the geometric distribution, we have
Taking t = M where M ∼ Geom( m


E F (wM +1 ) − F (u)
i
¬ h
σψ
ku − w0 k2 − ku − wM k2 σf
≤ E ηQkwM − w0 k2 +
−
ku − wM k2 −
ku − wM +1 k2
2(m − 1)η
2
2
hm − 1
2
2
ku − w0 k − ku − wM +1 k
­
=E
ηQkwM +1 − w0 k2 +
m
2mη
i
σf
σf (m − 1)
σψ
−
ku − w0 k2 −
ku − wM +1 k2 −
ku − wM +1 k2
2m
2m
2
i
2 − ku − w
2
® h
σf + σψ
ku
−
w
k
k
0
M +1
≤ E ηQkwM +1 − w0 k2 +
−
ku − wM +1 k2
2mη
4
i
2
2
¯ h
1
ku − w0 k − ku − wM +1 k + kw0 − wM +1 k2 σf + σψ
≤E −
kw0 − wM +1 k2 +
−
kwM +1 − uk2
4mη
2mη
4
i
h
1
hw0 − wM +1 , w0 − ui σf + σψ
°
=E −
kwM +1 − w0 k2 +
−
kwM +1 − uk2
4mη
mη
4

Above, inequality ¬ is by substituting t = M into (B.1) and applying Fact 2.3; equality ­ is by
applying Fact 2.3; inequality ® uses m ≥ 2; inequality ¯ uses our assumption η ≤ 2√1Qm ; and
equality ° can be verified by expanding out the norms.

C



Variance Bonds for Gradient Estimators



e t − ∇f (wt )k2 ≤
In this section, we provide two types of variance upper bound of the form E k∇
Qkwt − w0 k2 . The first type is for uniform sampling over the stochastic gradients, and the second
type is for non-uniform sampling. Both of them are not hard to prove.

C.1

Uniform Sampling

Lemma 3.4. If each fi (x) is (`1 , `2 )-smooth for `2 ≥ `1 , and the gradient estimator

et = µ + 1 P
∇
i∈St ∇fi (wt ) − ∇fi (w0 )
b

e t] =
where St consists of b i.i.d. uniform
indices from [n] with replacement. Then, ESt [∇
 `random
`
2
2
1
2
e t − ∇f (wt )k ≤
∇f (wt ) and ESt k∇
b kwt − w0 k .
17

Proof. We calculate that
h 1 X 

2i


e t − ∇f (wt )k2 = ESt
E k∇
∇f (w0 ) + ∇fi (wt ) − ∇fi (w0 ) − ∇f (wt )
b
i∈St
h


2i
¬ 1
= Ei∈R [n]
∇f (w0 ) + ∇fi (wt ) − ∇fi (w0 ) − ∇f (wt )
b
h

 2i
1
= Ei∈R [n]
∇fi (wt ) − ∇fi (w0 ) − ∇f (wt ) − f (w0 )
b
h
­ 1
 2i
∇fi (wt ) − ∇fi (w0 )
≤ Ei∈R [n]
b

® 1
(`1 − `2 )h∇f (wt ) − ∇f (w0 ), wt − w0 i + `1 `2 kwt − w0 k2
≤
b
¯ `1 `2
kwt − w0 k2 .
≤
b
 P
Above, equality ¬ follows because for i.i.d. random vectors ζ1 , . . . , ζb , we have E 1b j∈[b] ζj −
2
E[ζj ]
= 1b E[kζ1 − E[ζ1 ]k2 ]; inequality ­ is because for any random vector ζ ∈ Rd , it holds that
Ekζ − Eζk2 = Ekζk2 − kEζk2 ; inequality ® is due to Claim C.1 below and Ei∈R [n] [∇fi (x)] = ∇f (x);
and inequality ¯ follows because `1 ≤ `2 and for any convex function g(·), we have h∇g(x) −
∇g(y), x − yi ≥ (g(x) − g(y)) + (g(y) − g(x)) = 0.

Claim C.1. If fi (·) is an (`1 , `2 )-smooth function, then
k∇fi (x) − ∇fi (y)k2 ≤ (`1 − `2 )h∇fi (x) − ∇fi (y), x − yi + `1 `2 ky − xk2 .
def

Proof. Define φi (z) = −fi (z) + h∇fi (x), zi + `21 kz − xk2 for each i ∈ [n]. It is clear that φi (y) is
a convex, (`1 + `2 )-smooth function that has a minimizer z = x (which can be seen by taking the
derivative). For this reason, we claim that

∇φi (z) 
1
φi (x) ≤ φi z −
≤ φi (z) −
k∇φi (z)k2 ,
(C.1)
`1 + `2
2(`1 + `2 )

for each z, and this inequality is classical for smooth functions (see for instance Theorem 2.1.5
in the textbook [22]). By expanding out the definition of φi (·) and choosing z = y in (C.1), we
immediately have
− fi (x) + h∇fi (x), xi ≤ −fi (y) + h∇fi (x), yi +

`1
ky − xk2
2
1
−
k∇fi (y) − ∇fi (x) − `1 (y − x)k2 .
2(`1 + `2 )

Summing up the above inequality with itself but swapping x and y, we have
1
h∇fi (x) − ∇fi (y), x − yi ≤ `1 ky − xk2 −
k∇fi (y) − ∇fi (x) − `1 (y − x)k2 .
`1 + `2
Or equivalently
`2 − `1
1
`21
h∇fi (x) − ∇fi (y), x − yi ≤ `1 ky − xk2 −
k∇fi (y) − ∇fi (x)k2 −
ky − xk2 .
`1 + `2
`1 + `2
`1 + `2



18

C.2

Non-Uniform Sampling

Lemma 5.1. Suppose each fi (x) is Li -smooth for some possibly different parameter Li , and let
P 2 1/2
def
e t as follows:
L=
. Then, we can define ∇
i Li /n
def

• Let distribution D be to select i ∈ [n] with probability pi =

L2
P i 2;
j Lj

• Let St be b i.i.d. samples from D with replacement;

1
et ← 1 P
• ∇
i∈St npi ∇fi (wt ) − ∇fi (w0 ) .
b
2


e t ] = ∇f (wt ) and E k∇
e t − ∇f (wt )k2 ≤ L kwt − w0 k2 .
Then, ESt [∇
b
Proof.

h 1 X 
2i



1
e t − ∇f (wt )k2 = ESt
∇fi (wt ) − ∇fi (w0 )
− ∇f (wt )
E k∇
∇f (w0 ) +
b
npi
i∈St
h

2i

1
¬ 1
= Ei∼D
∇fi (wt ) − ∇fi (w0 ) − ∇f (wt )
∇f (w0 ) +
b
npi
h 1

 2i
1
= Ei∼D
∇fi (wt ) − ∇fi (w0 ) − ∇f (wt ) − f (w0 )
b
npi
h 1
­ 1
 2i
∇fi (wt ) − ∇fi (w0 )
≤ Ei∼D
b
npi
2
­ 1 X L2
L
2
i
≤ ·
kwt − w0 k =
kwt − w0 k2 .
b
n2 p i
b
i∈[n]

 P
Above, equality ¬ follows because for i.i.d. random vectors ζ1 , . . . , ζb , we have E 1b j∈[b] ζj −
2
E[ζj ]
= 1b E[kζ1 − E[ζ1 ]k2 ]; inequality ­ is because for any random vector ζ ∈ Rd , it holds that
Ekζ − Eζk2 = Ekζk2 − kEζk2 ; and inequality ® uses the smoothness definition of fi (·).


D

Improved SVRG Convergence Rate

In this section we consider a simple SVRG algorithm that, starting from x0 ∈ Rd , repeatedly
performs updates xk+1 ← SVRG1ep (F, xk , b, η). We refer to this algorithm as SVRG in this section.

1
and
Theorem D.1. If σ > 0 and η > 0 satisfies Theorem 3.1, then setting τ = min mησ
2 ,2
(1+τ )K −1 PK−1
k
x=
k=0 (1 + τ ) xk+1 , we have
τ

E[F (x) − F (x∗ )] ≤ O((1 + τ )−K ) F (x0 ) − F (x∗ ) .
1
In other words, choosing η = min 2L
, √ 1
, SVRG finds E[F (x) − F (x∗ )] ≤ ε in
2

Tgrad = O



n+

`1 `2 m/b

bL +

√

`1 `2 n 

log

F (x0 ) − F (x∗ ) 
ε

σ
stochastic gradient computations, or equivalently
 n L + √` ` n/b 
F (x0 ) − F (x∗ ) 
1 2
Tgrad = O
+
log
b
σ
ε
parallel iterations.

19

Proof of Theorem D.1. To analyze SVRG, we rewrite Theorem 3.1 equivalently as:
h 1
i


1
1
σ
E F (w+ ) − F (u) ≤ E
kw+ − w0 k2 +
kw0 − uk2 −
kw+ − uk2 − kw+ − uk2 .
4mη
2mη
2mη
4
(D.1)
We now apply (D.1) twice, once with w0 = xk , w+ = xk+1 , u = x∗ and once with w0 = xk ,
w+ = xk+1 , u = xk . Summing them up, we get
h 1
i


1
σ
E 2F (xk+1 ) − F (x∗ ) − F (xk ) ≤ E
kxk − x∗ k2 −
kxk+1 − x∗ k2 − kxk+1 − x∗ k2 .
2mη
2mη
4
(D.2)
 mησ 1
Let τ = min 2 , 2 . Multiplying both sides of (D.2) by (1 + τ )k , we obtain


E 2(1 + τ )k (F (xk+1 ) − F (x∗ )) − (1 + τ )k (F (xk ) − F (x∗ ))
h (1 + τ )k
i
(1 + τ )k+1
≤E
kxk − x∗ k2 −
kxk+1 − x∗ k2 .
2mη
2mη
Telescoping it for k = 0, 1, . . . , K − 1, we have

X
 K−1

E
(1 − τ )(1 + τ )k (F (xk+1 ) − F (x∗ )) ≤ F (x0 ) − F (x∗ ) +
k=0

1
kx0 − x∗ k2
2mη


1 
F (x0 ) − F (x∗ )
mησ


1
=
+ 1 F (x0 ) − F (x∗ ) .
2τ
≤ 1+

Using the definition x =
conclude that

(1+τ )K −1
τ

PK−1
k=0

(1 + τ )k xk+1 and the convexity of f (x), we immediately


F (x) − F (x∗ ) ≤ O((1 + τ )−K ) F (x0 ) − F (x∗ ) .



Theorem D.2. In the case of σ = 0, a variant of SVRG achieves the following complexity:

√

bL + `1 `2 n kx0 − x∗ k2 
F (x0 ) − F (x∗ )
Tgrad = O n log
+
ε
ε
stochastic gradient computations, or equivalently

√
n
L + `1 `2 n/b kx0 − x∗ k2 
F (x0 ) − F (x∗ )
log
+
Tgrad = O
b
ε
ε
parallel iterations.
Proof sketch. The simplest way to show this result is by applying the optimal reduction [6] to
reduce the problem to the strongly convex case (and thus Theorem D.1). One can also design a
direct method with such complexity by doubling the epoch length m from epoch to epoch, following
a similar analysis from [11]. Since the main focus of this paper is to design accelerated method, we
ignore the details here.


References
[1] Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma. Finding Approximate
Local Minima for Nonconvex Optimization in Linear Time. In STOC, 2017. Full version available at
http://arxiv.org/abs/1611.01146.

20

[2] Zeyuan Allen-Zhu. Katyusha: The First Direct Acceleration of Stochastic Gradient Methods. In STOC,
2017. Full version available at http://arxiv.org/abs/1603.05953.
[3] Zeyuan Allen-Zhu. Natasha: Faster Non-Convex Stochastic Optimization via Strongly Non-Convex
Parameter. In ICML, 2017. Full version available at http://arxiv.org/abs/1702.00763.
[4] Zeyuan Allen-Zhu. How To Make the Gradients Small Stochastically. ArXiv e-prints, abs/1801.02982,
January 2018.
[5] Zeyuan Allen-Zhu and Elad Hazan. Variance Reduction for Faster Non-Convex Optimization. In ICML,
2016. Full version available at http://arxiv.org/abs/1603.05643.
[6] Zeyuan Allen-Zhu and Elad Hazan. Optimal Black-Box Reductions Between Optimization Objectives.
In NIPS, 2016.
[7] Zeyuan Allen-Zhu and Yuanzhi Li. LazySVD: Even Faster SVD Decomposition Yet Without Agonizing
Pain. In NIPS, 2016. Full version available at http://arxiv.org/abs/1607.03463.
[8] Zeyuan Allen-Zhu and Yuanzhi Li. First Efficient Convergence for Streaming k-PCA: a Global, GapFree, and Near-Optimal Rate. In FOCS, 2017. Full version available at http://arxiv.org/abs/1607.
07837.
[9] Zeyuan Allen-Zhu and Yuanzhi Li. Follow the Compressed Leader: Faster Online Learning of Eigenvectors and Faster MMWU. In ICML, 2017. Full version available at http://arxiv.org/abs/1701.01722.
[10] Zeyuan Allen-Zhu and Lorenzo Orecchia. Linear Coupling: An Ultimate Unification of Gradient and
Mirror Descent. In Proceedings of the 8th Innovations in Theoretical Computer Science, ITCS ’17, 2017.
Full version available at http://arxiv.org/abs/1407.1537.
[11] Zeyuan Allen-Zhu and Yang Yuan. Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex
Objectives. In ICML, 2016.
[12] Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. Accelerated Methods for Non-Convex
Optimization. ArXiv e-prints, abs/1611.00756, November 2016.
[13] Roy Frostig, Rong Ge, Sham M. Kakade, and Aaron Sidford. Un-regularizing: approximate proximal
point and faster stochastic algorithms for empirical risk minimization. In ICML, 2015. URL http:
//arxiv.org/abs/1506.07512.
[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] Prateek Jain, Chi Jin, Sham M. Kakade, Praneeth Netrapalli, and Aaron Sidford. Streaming PCA:
Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja’s Algorithm. In COLT,
2016.
[16] Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems, NIPS 2013, pages 315–323, 2013.
[17] Lihua Lei, Cheng Ju, Jianbo Chen, and Michael I Jordan. Nonconvex Finite-Sum Optimization Via
SCSG Methods. In NIPS, 2017.
[18] Hongzhou Lin, Julien Mairal, and Zaid Harchaoui. A Universal Catalyst for First-Order Optimization.
In NIPS, 2015. URL http://arxiv.org/pdf/1506.02186v1.pdf.
[19] Hongzhou Lin, Julien Mairal, and Zaid Harchaoui. Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice. ArXiv e-prints, abs/1712.05654, 2017.
[20] Zhuang Ma, Yichao Lu, and Dean Foster. Finding linear structure in large datasets with scalable
canonical correlation analysis. In ICML, pages 169–178, 2015.
[21] Tomoya Murata and Taiji Suzuki. Doubly accelerated stochastic variance reduced dual averaging method
for regularized empirical risk minimization. In NIPS, 2017.
[22] Yurii Nesterov. Introductory Lectures on Convex Programming Volume: A Basic course, volume I.
Kluwer Academic Publishers, 2004. ISBN 1402075537.
[23] Yurii Nesterov. Smooth minimization of non-smooth functions. Mathematical Programming, 103(1):
127–152, December 2005. ISSN 0025-5610. doi: 10.1007/s10107-004-0552-5.

21

[24] Erkki Oja. Simplified neuron model as a principal component analyzer. Journal of mathematical biology,
15(3):267–273, 1982.
[25] Sashank J. Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance
reduction for nonconvex optimization. In ICML, 2016.
[26] Youcef Saad. Numerical methods for large eigenvalue problems. Manchester University Press, 1992.
[27] Shai Shalev-Shwartz. SDCA without Duality, Regularization, and Individual Convexity. In ICML,
2016.
[28] Shai Shalev-Shwartz and Tong Zhang. Accelerated Proximal Stochastic Dual Coordinate Ascent for
Regularized Loss Minimization. In Proceedings of the 31st International Conference on Machine Learning, ICML 2014, pages 64–72, 2014.
[29] Ohad Shamir. A Stochastic PCA and SVD Algorithm with an Exponential Convergence Rate. In ICML,
pages 144—-153, 2015.
[30] Ohad Shamir. Fast stochastic algorithms for svd and pca: Convergence properties and convexity. In
ICML, 2016.
[31] Lin Xiao and Tong Zhang. A Proximal Stochastic Gradient Method with Progressive Variance Reduction. SIAM Journal on Optimization, 24(4):2057—-2075, 2014.
[32] Lijun Zhang, Mehrdad Mahdavi, and Rong Jin. Linear convergence with condition number independent
access of full gradients. In Advances in Neural Information Processing Systems, pages 980–988, 2013.

22

