Guaranteed Sufficient Decrease for Stochastic Variance Reduced
Gradient Optimization

arXiv:1802.09933v1 [stat.ML] 26 Feb 2018

Fanhua Shang, Yuanyuan Liu, Kaiwen Zhou, James Cheng, Kelvin K.W. Ng
Department of Computer Science and Engineering, The Chinese University of Hong Kong
Yuichi Yoshida
National Institute of Informatics, Tokyo, Japan

Abstract
In this paper, we propose a novel sufficient
decrease technique for stochastic variance
reduced gradient descent methods such as
SVRG and SAGA. In order to make sufficient decrease for stochastic optimization,
we design a new sufficient decrease criterion,
which yields sufficient decrease versions of
stochastic variance reduction algorithms such
as SVRG-SD and SAGA-SD as a byproduct.
We introduce a coefficient to scale current
iterate and to satisfy the sufficient decrease
property, which takes the decisions to shrink,
expand or even move in the opposite direction, and then give two specific update rules
of the coefficient for Lasso and ridge regression. Moreover, we analyze the convergence
properties of our algorithms for strongly convex problems, which show that our algorithms attain linear convergence rates. We
also provide the convergence guarantees of
our algorithms for non-strongly convex problems. Our experimental results further verify
that our algorithms achieve significantly better performance than their counterparts.

1

Introduction

Stochastic gradient descent (SGD) has been successfully applied to many large-scale machine learning
problems [1, 2], due to its low per-iteration cost, O(d).
However, standard SGD estimates the gradient from
only one or a few samples, and thus the variance of
Proceedings of the 21st International Conference on Artificial Intelligence and Statistics (AISTATS) 2018, Lanzarote,
Spain. PMLR: Volume 84. Copyright 2018 by the author(s).

the stochastic gradient estimator may be large [3, 4],
which leads to slow convergence and poor performance.
In particular, even under the strongly convex (SC) condition, the convergence rate of standard SGD is only
sub-linear [5, 6]. Recently, the convergence rate of the
standard SGD has been improved by various stochastic
variance reduction gradient methods, such as SAG [7],
SDCA [8], SVRG [3], SAGA [9], Finito [10], MISO [11],
and their proximal variants, such as [12], [13] and [14].
Under the SC condition, these stochastic variance reduction algorithms achieve linear convergence rates.
Very recently, some acceleration techniques were proposed to further speed up the stochastic variance reduction methods mentioned above. These techniques
include importance sampling [4], exploiting neighborhood structure in the training data to share and re-use
information about past stochastic gradients [15], incorporating Nesterov’s acceleration techniques [16, 17]
or momentum acceleration tricks [18], reducing the
number of gradient computations in the early iterations [19, 20, 21, 22], and the projection-free property
of the conditional gradient method [23]. In particular,
Katyusha [18] can attain the upper complexity bounds
for both SC and non-strongly convex (non-SC) composite problems, respectively, as discussed in [24].
Challenges and Main Contributions. So far
the two most popular stochastic gradient estimators
are the SVRG estimator independently introduced
by [3, 21] and the SAGA estimator [9]. All the estimators may be very different from their full gradient
counterparts, thus moving in the direction may not decrease the objective function anymore, as stated in [18].
To address this problem, inspired by the success of
sufficient decrease methods for deterministic optimization such as [25, 26], we propose a novel sufficient
decrease technique for a class of stochastic variance
reduction methods, including the widely-used SVRG
and SAGA methods. Notably, our method with partial
sufficient decrease achieves average time complexity

Guaranteed Sufficient Decrease for Stochastic Variance Reduced Gradient Optimization

per-iteration as low as the original SVRG and SAGA
methods. We summarize our main contributions below.
• For making sufficient decrease for stochastic optimization, we design a sufficient decrease strategy
to further reduce the cost function, in which we
also introduce a coefficient to take the decision to
shrink, expand or move in the opposite direction.
• We incorporate our sufficient decrease technique, together with momentum acceleration, into
two representative SVRG and SAGA algorithms,
which lead to SVRG-SD and SAGA-SD. Moreover, we give two specific update rules of the coefficient for Lasso and ridge regression problems as
notable examples.
• Moreover, we analyze the convergence property of
SVRG-SD, which shows that SVRG-SD converges
linearly for SC composite minimization problems.
Unlike most of the stochastic variance reduction
methods such as SVRG, we also provide the convergence guarantee of SVRG-SD for non-SC composite minimization problems.
• Finally, we show by experiments that SVRG-SD
and SAGA-SD achieve significantly better performance than SVRG [3] and SAGA [9]. Compared with the well-known accelerated method,
Katyusha [18], our algorithms also have much better performance in most cases.

2
2.1

Preliminary and Related Work
Notations

Throughout this paper, we use k · k to denote the ℓ2 norm (also known as the standard Euclidean norm),
Pd
and k ·k1 is the ℓ1 -norm, i.e., kxk1 = i=1 |xi |. ∇f (·)
denotes the full gradient of the function f (·) if it is
differentiable, or ∂f (·) the subgradient if f (·) is only
Lipschitz continuous.
In this paper, we consider the following unconstrained
composite convex optimization problem:
1 Xn
def
fi (x) + r(x), (1)
min F (x) = f (x) + r(x) =
i=1
n
x∈Rd

where fi (x) : Rd → R, i = 1, . . . , n are the smooth convex component functions, and r(x) is a relatively simple convex (but possibly non-differentiable) function.
We consider the problem (1) under the following standard assumptions.
Assumption 1. Each convex function fi (·) is Lsmooth, iff there exists a constant L > 0 such that for
any x, y ∈ Rd , k∇fi (x) − ∇fi (y)k ≤ Lkx − yk.

Algorithm 1 SVRG
Input: The number of epochs S, the number of iterations m per epoch, and the step size η.
Initialize: x
e0 .
1: for s = 1, 2, . . . , S do
Pn
xs−1 );
2:
µ
es−1 = n1 i=1 ∇fi (e
s
s−1
3:
x0 = x
e ;
4:
for k = 1, 2, . . . , m do
5:
Pick isk uniformly at random from [n];
e is (xs ) = ∇fis (xs ) − ∇fis (e
6:
∇f
xs−1 ) + µ
es−1 ;
k−1
k−1
k
k
k
s
s
e is (xk−1 );
7:
xk = xk−1 − η ∇f
k
8:
end for
9:
x
es = xsm ;
10: end for
Output: x
eS

Assumption 2. F (·) is µ-strongly convex, iff there
exists a constant µ > 0 such that for any x, y ∈ Rd ,
µ
F (y) ≥ F (x)+ϑT(y − x)+ ky − xk2 , ∀ϑ ∈ ∂F (x), (2)
2

where ∂F (x) is the subdifferential of F (·) at x. If F (·)
is smooth, we can revise the inequality (2) by simply
replacing the sub-gradient ϑ ∈ ∂F (x) with ∇F (x).
2.2

SVRG and SAGA

Recently, many stochastic variance reduced methods [3, 7, 14, 21] have been proposed for some special cases of Problem (1). Under smoothness and SC
assumptions, and r(x) ≡ 0, SAG [7] achieves a linear
convergence rate. A recent line of work, such as [3, 14],
has been proposed with similar convergence rates to
SAG but without the memory requirements for all gradients. SVRG [3] begins with an initial estimate x
e0 ,
1
0
s
sets x0 = x
e and then generates a sequence of xk at
the s-th epoch (k = 1, 2, . . . , m, where m is usually set
to 2n, as suggested in [3, 14]) using


xs−1 ) + µ
es−1 , (3)
xsk = xsk−1 − η ∇fisk(xsk−1 ) − ∇fisk(e

Pn
xs−1 ) is
where η > 0 is the step size, µ
es−1 = n1 i=1 ∇fi (e
s−1
the full gradient of f (·) at the snapshot x
e , and isk is
chosen uniformly at random from {1, 2, . . . , n}. After
every m stochastic iterations, we set x
es = xsm , and reset
s+1
s
k = 1 and x0 = x
e (see Algorithm 1 for details).

In particular, the stochastic gradient estimator in Line
6 of Algorithm 1, i.e., the SVRG estimator independently introduced in [3, 21], is a popular choice for
stochastic gradient estimators. Unfortunately, most of
the stochastic variance reduction methods [8, 10, 14],
including SVRG, only have convergence guarantees for
smooth and SC problems. However, F (·) may be nonSC in many machine learning applications (e.g., Lasso)

Fanhua Shang,

Yuanyuan Liu,

Kaiwen Zhou,

or non-smooth and SC problems, e.g., elastic-net. For
solving the non-smooth problem (1), a proximal variant of SVRG, i.e., Prox-SVRG [14], has been proposed
and relies on the use of the proximal operator, proxrη (·),
which is defined as:
n
o
proxrη (y) = arg min (1/2η)·kx−yk2 + r(x) .
x

[9] proposed SAGA, a fast incremental gradient
method in the spirit of SAG and SVRG, which works
for both SC and non-SC objective functions, as well
as in the proximal setting. Unlike SVRG and ProxSVRG, both of which are two-stage algorithms, SAGA
is a single-stage incremental gradient algorithm. Its
main update rules are formulated as follows:
n
X
e i (xk−1 ) = gik −g k−1 + 1
∇f
g k−1 ,
(3a)
k
ik
k
n j=1 j


e i (xk−1 ) ,
xk = proxrη xk−1 − η ∇f
(3b)
k

where gjk is updated for all j = 1, . . . , n as follows: gjk =
∇fik(xk−1 ) if ik = j, and gjk = gjk−1 otherwise (see [9, 27]
for details). Here, the stochastic gradient estimator
in (3a) is called as the SAGA estimator.
2.3

Sufficient Decrease for Deterministic
Optimization

The technique of sufficient decrease (e.g., the wellknown line search technique [28]) has been studied for
deterministic optimization [25, 26]. For example, [25]
proposed the following sufficient decrease condition:
F (xk ) ≤ F (xk−1 ) − δkyk − xk−1 k2 ,

(4)

where δ > 0 is a small constant, and yk = proxrηk(xk−1 −
ηk ∇f (xk−1 )). Inspired by the strategy for deterministic optimization, in this paper we design a novel sufficient decrease technique for stochastic optimization,
which is used to further reduce the cost function and
speed up its convergence.

3

SVRG with Sufficient Decrease

In this section, we propose a novel sufficient decrease
technique for stochastic variance reduction optimization methods, which include the widely-used SVRG
method. To make sufficient decrease for stochastic optimization, we design an effective sufficient decrease
strategy that can further reduce the cost function.
Then a coefficient θ is introduced to satisfy the sufficient decrease condition, and takes the decisions to
shrink, expand or move in the opposite direction.
Moreover, we present a variant of SVRG with sufficient
decrease and momentum acceleration (called SVRGSD). We also give two specific schemes to compute θ
for Lasso and ridge regression.

James Cheng,

Kelvin K.W. Ng

Algorithm 2 SVRG-SD
Input: the number of epochs S, the number of iterations m per epoch, and the step size η.
Initialize: x
e0 for Case of SC, or x
e0 = ye0 for Case of
non-SC.
1: for s = 1, 2, . . . , S do
2:
Case of SC: xs0 = x
bs0 = x
es−1 ;
s
3:
Case of non-SC:
x0 = x
bs0 = yes−1 ;
1 Pn
s−1
s−1
4:
µ
e
= n i=1 ∇fi (e
x );
5:
for k = 1, 2, . . . , m do
6:
Pick isk uniformly at random from [n];
e is (xs ) = ∇fis (xs ) −∇fis (e
7:
∇f
xs−1 ) + µ
es−1 ;
k−1
k−1
k
k
k
s
s
8:
Update yk , θk , and xk by (8), (5), and (7);
9:
end forP
m
1
bsk ;
10:
x
es = m
k=1 x
11:
Case of non-SC: yes = [xsm − (1−σ)b
xsm ]/σ;
12: end for
PS
es ) ≥
Output: x = x
eS (SC), or x = x
eS if F ( S1 s=1 x
P
S
1
s
S
e otherwise (non-SC)
F (e
x ) and x = S s=1 x
3.1

Our Sufficient Decrease Technique

Suppose xsk = proxrη (xsk−1 − η[∇fisk(xsk−1 ) − ∇fisk(e
xs−1 ) +
s−1
µ
e ]) for the s-th outer-iteration and the k-th inneriteration. Unlike the full gradient method, the stochastic gradient estimator is somewhat inaccurate (i.e., it
may be very different from ∇f (xsk−1 )), then further
moving in the updating direction may not decrease
the objective value anymore [18]. That is, F (xsk ) may
be larger than F (xsk−1 ) even for very small step length
η > 0. Motivated by this observation, we design a factor θ to scale the current iterate xsk−1 for the decrease
of the objective function. For SVRG-SD, the cost function with respect to θ is formulated as follows:
min F (θxsk−1 )+
θ∈R

ζ(1−θ)2
k∇fisk(xsk−1 )−∇fisk(e
xs−1 )k2, (5)
2

δη
is a trade-off parameter between the
where ζ = 1−Lη
two terms, δ is a small constant and set to 0.1. The
second term in (5) involves the norm of the residual
of stochastic gradients, and plays the same role as the
second term of the right-hand side of (4). Different
from existing sufficient decrease techniques including
(4), a varying factor θ instead of a constant is introduced to scale xsk−1 and the coefficient of the second
term of (5), and θ plays a similar role as the step-size
parameter optimized via a line-search for deterministic
optimization. However, line search techniques have a
high computational cost in general, which limits their
applicability to stochastic optimization [29].

Note that θ is a scalar and takes the decisions to shrink,
expand xsk−1 or move in the opposite direction of xsk−1 .
The detailed schemes to calculate θ for Lasso and ridge
regression are given in Section 3.3. We first present the

Guaranteed Sufficient Decrease for Stochastic Variance Reduced Gradient Optimization

following sufficient decrease condition in the statistical
sense for stochastic optimization.
Property 1. For given xsk−1 and the solution θk of
Problem (5), then the following inequality holds
F (θk xsk−1 ) ≤ F (xsk−1 ) −

ζ(1−θk )2
ke
pisk k2 ,
2

(6)

xs−1 ) for SVRG-SD.
where peisk = ∇fisk(xsk−1 )−∇fisk(e

It is not hard to verify that F (·) can be further decreased via our sufficient decrease technique, when the
current iterate xsk−1 is scaled by the coefficient θk . Indeed, for the special case when θk = 1 for some k, the
inequality in (6) can be still satisfied. Unlike the sufficient decrease condition for deterministic optimization [25, 26], θk may be a negative number, which
means to move in the opposite direction of xsk−1 .

3.2

Momentum Acceleration

In this part, we first design the update rule for the key
variable xsk with the coefficient θk as follows:
xsk − x
bsk−1 ),
xsk = yks + (1 − σ)(b

(7)

where x
bsk = θk xsk−1 , σ ∈ [0, 1] is a constant and can be
set to σ = 1/2 which also works well in practice. In fact,
the second term of the right-hand side of (7) plays a
momentum acceleration role as in stochastic and deterministic optimization [17, 18, 30, 31, 32, 33, 34]. That
is, by introducing this term, we can utilize the previous information of gradients to update xsk . Then the
update rule of yks is given by


e is (xsk−1 ) ,
yks = proxrη xsk−1 − η ∇f
(8)
k

where η = 1/(Lα), L > 0 is a Lipschitz constant (see Assumption 1), and α ≥ 1 denotes a constant. From the
update rule in (8), it is clear that SVRG-SD can tackle
the non-smooth minimization problem (1) directly as
e is(xs )
Prox-SVRG [14] and SAGA [9]. In addition, ∇f
k−1
k
can be the two most popular choices for stochastic gradient estimators: the SVRG estimator [3, 21] and the
e is(xs ) is deSAGA estimator [9]. For SVRG-SD, ∇f
k−1
k
fined as follows:
e is(xsk−1 ) = ∇fis(xsk−1 )−∇fis(e
∇f
xs−1 )+ µ
es−1 .
k
k
k

(9)

In summary, we propose a novel variant of SVRG with
sufficient decrease (called SVRG-SD) to solve both SC
and non-SC problems, as outlined in Algorithm 2.
For the case of SC, xs0 = x
bs0 = x
es−1 , while xs0 = x
bs0 =
s−1
s
s
s
ye
and ye = [xm −(1 − σ)b
xm ]/σ are set for the case
of non-SC. Note that when θk ≡ 1 and σ = 1, the
proposed SVRG-SD degenerates to the original SVRG
or its proximal variant, Prox-SVRG [14]. In this sense,
SVRG and Prox-SVRG can be seen as the special cases
of the proposed SVRG-SD algorithm.

3.3

Computing Coefficients for Lasso and
Ridge Regression

In this part, we give the closed-form solutions of the
coefficient θ for Lasso and ridge regression.
For Lasso problems and given xsk−1 , we have
n
1 X T s
(θa x −bi )2 +λkθxsk−1 k1 .
F (θxsk−1 ) =
2n i=1 i k−1

The closed-form solution of Problem (5) for SVRG-SD
can be obtained as follows:
!
1 T
s
pisk k2
n b Axk−1 + ζke
,
(10)
θk = Sτ
kAxsk−1 k2 /n + ζke
pisk k2
where A = [a1 , . . . , an ]T is the data matrix containing
n data samples, b = [b1 , . . . , bn ]T, and Sτ is the socalled soft thresholding operator [35] with the following threshold,
λkxsk−1 k1
τ=
.
kAxsk−1 k2 /n + ζke
pisk k2
For ridge regression problems, we have
n
λ
1 X T s
s
(θa x −bi )2 + kθxsk−1 k2 .
F (θxk−1 ) =
2n i=1 i k−1
2

The closed-form solution of Problem (5) for SVRG-SD
is given by
1 T
s
pisk k2
n b Axk−1 + ζke
.
(11)
θk =
kAxsk−1 k2 /n + ζke
pisk k2 + λkxsk−1 k2
We can compute the coefficient for other loss functions (e.g., logistic regression) using line search (e.g.,
Armijo’s line search [36]) or their approximations [37].

4

Convergence Analysis

In this section, we provide the convergence analysis of
SVRG-SD for solving both SC and non-SC minimization problems.
4.1

Convergence Property for SC Problems

In this part, we analyze the convergence property of
SVRG-SD for solving the SC problem (1). The first
main result is the following theorem, which provides
the convergence rate of SVRG-SD.
Theorem 1. Suppose Assumption 1 holds. Let x∗ be
the optimal solution of Problem (1), and {(xsk , yks , θk )}
be the sequence produced by SVRG-SD, η = 1/(Lα),
2
and α−1
< σ, then
!
1−σ
2


m + α−1
s
∗
E F (e
xs−1 )−F (x∗ )
E[F (e
x )−F (x )] ≤
2
+ βb
σ−
α−1

Lασ 2



s 2
 E kx∗ −z0s k2 −kx∗ −zm

+
k ,
2
+ βb
2m σ− α−1

Fanhua Shang,

Yuanyuan Liu,

Kaiwen Zhou,

s
where z0s
=
[xs0 −(1−σ)b
xs0 ] /σ,
zm
=

 s
s
s
xm −(1−σ)b
xm−1 /σ, βb = mins=1,...,S βb ≥ 0, and βbs =
Pm
Pm
k βk
E[ k=12cα−1
xsk )−F (x∗ ))].
(F (b
xsk )−F (x∗ ))]/E[ k=1(F (b

The proof of Theorem 1 and the definitions of ck and
βk are given in the Supplementary Material. The linear convergence of SVRG-SD follows immediately.

Corollary 1 (SC). Suppose each fi (·) is L-smooth,
and F (·) is µ-strongly convex. Setting α = 19, σ = 1/2,
and m sufficiently large so that
ρ=

9
b
(7+18β)m

+

2
7+18βb

+

171L
< 1,
b
(14+36β)mµ

then SVRG-SD has the geometric convergence in expectation:


x0 ) − F (x∗ ) .
E[F (x) − F (x∗ )] ≤ ρS F (e

The proof of Corollary 1 is given in the Supplementary
Material. From Corollary 1, we can see that SVRGSD has a linear convergence rate for SC problems. As
L/µ
4ν
+ 1−4ν
for the proximal
discussed in [14], ρ ≈ ν(1−4ν)m
variant of SVRG [14], where ν = 1/α. For a reasonable
comparison, we use the same parameter settings for
SVRG and SVRG-SD, e.g., α = 19 and m = 57L/µ.
Then we can see that ρSVRG ≈ 31/45 for SVRG and
b < 1/2 for SVRG-SD, that is,
ρSVRG-SD ≈ 7/(14+36β)
ρSVRG-SD is smaller than ρSVRG . Note that setting
α to 19 is for the analysis only and not necessary in
practice. That is, α can be set to a much smaller
value, e.g., α = 1, which means that SVRG-SD can
use a much larger step size, e.g., η = 1/L for SVRGSD vs. η = 1/(10L) for SVRG. Thus, SVRG-SD can
significantly improve the convergence rate of SVRG
and Prox-SVRG in practice, which will be confirmed
by our experiments in Section 6.
Convergence Property for Non-SC
Problems

Unlike most of the stochastic variance reduction methods [3, 14], including SVRG and Prox-SVRG, which
only have the convergence guarantees for some SC
problems, the convergence result of SVRG-SD for the
non-SC case is also provided, as shown below.
Theorem 2 (Non-SC). Suppose each fi (·) is Lsmooth. Setting α = 19, σ = 1/2, and m sufficiently
large, then
171L
kx∗ − x
e0 k2
b
(16+40β)mS
!


1
9
F (e
x0 )−F (x∗ ) .
+
+
b
b
(4+8β)mS
(2+4β)S

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

Kelvin K.W. Ng

Algorithm 3 SAGA-SD
Input: the number of epochs S, the number of iterations m per epoch, and the step size η.
Initialize: x
e0 .
1: for s = 1, 2, . . . S do
2:
xs0 = x
bs0 = x
es−1 ;
3:
for k = 1, . . . , m do
4:
Pick isk uniformly at random from [n];
5:
Take φkis = xsk−1 and store ∇fisk(φkis ) in the
k
k
table;
P
1
e is(xs )=∇fis(xs )−∇fis(φk−1
∇fj (φk−1
6: ∇f
j );
isk )+n
k−1
k
k
 j
k k−1
e is (xs ) ;
7:
yks = proxrη xsk−1 − η ∇f
k−1
k
2

s
s
θk = arg minθ∈R F (θxsk−1 )+ ζ(1−θ)
2 k∇fik(xk−1 )−
2
∇fisk(φk−1
isk )k ;
s
s
9:
xk = yk + (1−σ)(b
xsk − x
bsk−1 ) and x
bsk = θk xsk−1 ;
10:
end forP
m
1
11:
x
es = m
bsk ;
k=1 x
12: end for
Output: x = x
eS

8:

The proof of Theorem 2 is provided in the Supplementary Material. The constant βb ≥ 0 is from the
sufficient decrease strategy, which thus implies that
the convergence bound in Theorem 2 can be further
improved using our sufficient decrease strategy with
b Theorem 2 shows that SVRGan even larger β.
SD attains the convergence rate of O(1/S) for the
non-strongly convex objective function (1). Although
SVRG-SD is guaranteed to have a slower theoretical
convergence rate than the accelerated stochastic variance reduction method, Katyusha [18], whose convergence rate is O(1/S 2 ), SVRG-SD usually converges
much faster than Katyusha in practice (see Section 6.3
for details).

5
4.2

James Cheng,

5.1

Extensions and Implementations
SAGA-SD

As mentioned above, we can use the proposed sufficient decrease technique to accelerate other stochastic variance reduction methods, e.g., SAGA [9], and
present a novel variant of SAGA with sufficient decrease (called SAGA-SD), as shown in Algorithm 3.
Like SVRG-SD, SAGA-SD is also a two-stage algorithm, whereas the original SAGA is a single-stage
algorithm. More specifically, for SAGA-SD, the cost
function with respect to θ in (5) can be revised by
k−1
xs−1 ) with ∇fisk(φk−1
simply replacing ∇fisk(e
isk ) = gik defined in (3a). Moreover, Property 1 can be extended
for SAGA-SD by setting peisk = ∇fisk(xsk−1 )−∇fisk(φk−1
isk ),
as well as for other stochastic variance reduction algorithms such as SAG. The main differences between

Similar to Katyusha [18], SVRG-SD and SAGA-SD
trivially extend to the mini-batch setting. As suggested in [39] and [16], we can add a proximal term
into a non-strongly convex objective function F (x) as
follows: Fτ (x, y) = f (x)+ τ2 kx−yk2+r(x), where τ ≥ 0 is
a constant that can be determined as in [16, 39], and
y ∈ Rd is a proximal point. Then the condition number
of this proximal function Fτ (x, y) can be much smaller
than that of the original function F (x), if τ is sufficiently large. However, adding the proximal term may
degrade the performance of the involved algorithms
both in theory and in practice [19]. Therefore, we directly use SVRG-SD and SAGA-SD to solve the nonstrongly convex objective function (1). If some component functions in (1) are non-smooth (e.g., support
vector machine), we can use the proximal operator oracle [40] or the Nesterov’s smoothing [41] technique
to smoothen them, and thereby obtain the smoothed
approximations of the functions fi (x).
5.2

Efficient Implementations

Both (10) and (11) require the calculation of bTA, thus
we need to precompute and save bTA in the initial
stage. To further reduce the computational complexity
of kAxsk−1 k2 in (10) and (11), we use the fast partial
singular value decomposition (SVD) to obtain the best
rank-r approximation Ur Sr VrT to A and save Sr VrT .
Then kAxsk−1 k ≈ kSr VrT xsk−1 k. In practice, e.g., in our
experiments, r can be set to a small number to capture
99.5% of the spectral energy of the data matrix A, e.g.,
r = 10 for the Covtype data set, similar to inexact line
search methods [28] for deterministic optimization.
For high-dimensional sparse data A (e.g., Rcv1), we
use the lazy computing trick for the calculation of
kAxsk−1 k, as well as bTA, instead of the partial SVD.
That is, we calculate kAxsk−1 k and bTA only for the
non-zero dimensions of each sample, rather than all
dimensions. In particular, we can introduce the lazy
update tricks in [42] to our algorithms, and perform
the update steps only for the non-zero dimensions of
each example. That is, the average per-iteration complexity can be improved from O(d) to O(d′ ) as stated
below, where d′ ≤ d is the sparsity of feature vectors.
The time complexity of each inter-iteration in SVRGSD, as well as SAGA-SD, with full sufficient decrease
is O(rd), which is a little higher than that of SVRG. In
fact, we can just randomly select only a small fraction
(e.g., 1/103) of stochastic gradient iterations in each
epoch to update with sufficient decrease, while the re-

SVRG
SVRG−SD (m1=2000)

−4

10

SVRG−SD (m =1000)
1

SVRG−SD (m1=500)
−8

10

−12

10

Objective minus best

SVRG-SD and SAGA-SD are the stochastic gradient
estimators in (9) and (3a), and the update rule of the
sufficient decrease coefficient in (5). For the convergence analysis of SAGA-SD, we refer to [38].

Objective minus best

Guaranteed Sufficient Decrease for Stochastic Variance Reduced Gradient Optimization
SVRG
SVRG−SD (m1=2000)

−4

10

SVRG−SD (m1=1000)
SVRG−SD (m1=500)

−8

10

−12

0

5

10
15
20
Number of effective passes

25

(a) Gap vs. number of passes

10

0

1

2
3
4
Running time (sec)

5

6

(b) Gap vs. running time

Figure 1: Comparison of SVRG and SVRG-SD with
different values of m1 for solving ridge regression problems on the Covtype dataset.
maining iterations are executed without sufficient decrease technique, i.e., x
bsk = xsk−1 . Let m1 be the number
of iterations with our sufficient decrease technique in
each epoch. By fixing m1 = ⌊m/103 ⌋ and thus without
increasing parameters tuning difficulties, SVRG-SD1
can always converge much faster than its counterpart,
SVRG, as shown in Figure 1 (similar results are also
observed for SAGA-SD, as shown in the Supplementary Materials). It is easy to see that our algorithms
are very robust with respect to the choice of m1 , and
achieve average per-iteration time complexity as low as
the original SVRG and SAGA. Thus, we mainly consider SVRG-SD and SAGA-SD with partial sufficient
decrease for real-world machine learning applications.

6

Experiments

In this section, we evaluate the performance of SVRGSD and SAGA-SD, and compare their performance
with their counterparts including SVRG [3], its proximal variant (Prox-SVRG) [14], and SAGA [9]. Moreover, we also report the performance of the wellknown accelerated stochastic variance reduction methods, Catalyst [16] and Katyusha [18].
Table 1: Summary of dense and sparse data sets.
Data sets
Sizes n
Dimensions d Sparsity
Ijcnn1
49,990
22
59.09%
Rcv1
20,242
47,236
0.16%
Covtype
581,012
54
22.12%
SUSY
5,000,000
18
98.82%

6.1

Experimental Setup

In our experiments, we used the four publicly available data sets: Ijcnn1, Rcv1, Covtype, and SUSY, all
of which can be downloaded from the LIBSVM Data
1
Note that SVRG-SD with partial sufficient decrease
possesses the similar convergence properties as SVRG-SD
with full sufficient decrease because Property 1 still holds
in the case when θk = 1.

Fanhua Shang,

Yuanyuan Liu,

Kaiwen Zhou,

James Cheng,

Kelvin K.W. Ng

−2

−8

10

−10

−8

10

−12

0

10

20
30
Gradient evaluations / n

40

10

50

*

−8

10

−6

10

−8

10

−10

10

10

−12

−4

10

−10

−10

10
10

−6

10

−6

10

10

−12

0

10

20
30
Gradient evaluations / n

10

40

SAGA
SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

10

s

−6

10

10

SAGA
SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−4

10

F (x ) − F (x )

−4

F (xs ) − F (x* )

F (xs ) − F (x* )

−4

10

10

SAGA
SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

10

F (xs ) − F (x* )

SAGA
SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

10

−12

0

10

20
30
Gradient evaluations / n

10

40

0

10

20
30
40
Gradient evaluations / n

50

−2

−8

10

−10

10

−8

10

−12

0

0.1

0.2
0.3
Running time (sec)

0.4

(a) Ijcnn1

10

−4

10
*

−8

−6

10

10

−8

10

−10

10

−12

−6

10

−10

10

−10

10
10

−6

s

10

−4

10

10

−12

0

1

2
3
Running time (sec)

4

5

10

SAGA
SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

10

F (x ) − F (x )

−6

SAGA
SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−4

10
F (xs ) − F (x* )

F (xs ) − F (x* )

−4

10

10

SAGA
SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

10

F (xs ) − F (x* )

SAGA
SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

10

−12

0

1

(b) Rcv1

2
3
4
Running time (sec)

5

10

6

0

(c) Covtype

10

20
30
40
Running time (sec)

50

60

(d) SUSY

Figure 2: Comparison of the stochastic variance reduction methods for solving ridge regression problems (λ1 =
10−4 ) on Ijcnn1, Rcv1, Covtype, and SUSY. The vertical axis is the objective value minus the minimum, and
the horizontal axis denotes the number of effective passes over the data (top) or running time (bottom).

6.2

Ridge Regression

In this part, we focus on the following ridge regression
(i.e., λ2 ≡ 0) problem as the SC example:
n

λ1
1 X T
(ai x − bi )2 + kxk2 + λ2 kxk1 ,
min
2
x∈Rd 2n
i=1

(12)

−2

−2

10

*

−6

10

−8

10

−6

10

−8

10

−10

−10

10

10

−12

−12

10

SAGA
SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−4

10
F (xs ) − F (x* )

−4

s

10

SAGA
SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

10
F (x ) − F (x )

website. Note that each sample of all the date sets
was normalized so that they have unit length as in [14],
which leads to the same upper bound on the Lipschitz
constants Li , i.e., L = Li for all i = 1, . . . , n. This
step is for comparison only and not necessary in practice. As suggested in [3, 14, 18], the epoch length
is set to m = 2n for the stochastic variance reduced
methods, SVRG [3], Prox-SVRG [14], Catalyst [16],
and Katyusha [18], as well as SVRG-SD. In addition,
unlike SAGA [9], we fixed m = n for each epoch of
SAGA-SD. Then the only parameter we have to tune
by hand is the step size, η. More specifically, we select
step sizes from {10j , 2.5 × 10j , 5 × 10j , 7.5 × 10j , 10j+1 }
as in [18], where j ∈ {−2, −1, 0}. Each of these methods had its step size parameter chosen so as to give
the fastest convergence. Since Katyusha has a much
higher per-iteration complexity than SVRG, we compare their performance in terms of both the number
of effective passes and running time (seconds), where
computing a single full gradient or evaluating n component gradients is considered as one effective pass over
the data. For fair comparison, we implemented all the
methods in C++ with a Matlab interface (all codes
are made available, see link in the Supplementary Materials), and performed all the experiments on a PC
with an Intel i5-2400 CPU and 16GB RAM.

10
0

10

20
30
40
50
Gradient evaluations / n

60

70

0

5

10
Running time (sec)

15

Figure 3: Comparison of the stochastic variance reduction methods for solving ridge regression problems
with λ1 = 10−6 on Covtype.

where λ1 , λ2 ≥ 0 are the regularization parameters.
Figure 2 shows how the objective gap, i.e., F (xs ) −
F (x∗ ), of all these algorithms decreases for ridge regression problems with the regularization parameters
λ1 = 10−4 and λ2 ≡ 0 (more results are given in the
Supplementary Material). For SVRG-SD and SAGASD, we set σ = 1/2 on the four data sets. As seen in
Figure 2, SVRG-SD and SAGA-SD achieve consistent
speedups for all the data sets, and significantly outperform their counterparts, SVRG and SAGA, in all
the settings. This confirms that our stochastic sufficient decrease technique is able to accelerate SVRG
and SAGA. Impressively, SVRG-SD and SAGA-SD
usually converge much faster than the well-known accelerated methods, Catalyst and Katyusha, which further justifies the effectiveness of our sufficient decrease
technique. As SVRG-SD and SAGA-SD have a much
lower per-iteration complexity than Katyusha, they
have more obvious advantage over Katyusha in terms
of running time, especially for the case of sparse data
(e.g., Rcv1), as shown in Fig. 2(b).

Guaranteed Sufficient Decrease for Stochastic Variance Reduced Gradient Optimization
−2

−8

10

−8

10

−12

−12

0

10

20
30
Gradient evaluations / n

40

10

−8

10

−4

10

50
100
Gradient evaluations / n

10

150

−8

10
10

−12

0

−6

10

−10

10

10

10

−6

10

SAGA
Prox−SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

10

−10

−10

−10

10

−6

10

SAGA
Prox−SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−4

10

F (xs ) − F (x* )

−6

10

−4

10

10

F (xs ) − F (x* )

F (xs ) − F (x* )

−4

10

SAGA
Prox−SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

10

F (xs ) − F (x* )

SAGA
Prox−SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

10

−12

0

10

20
30
Gradient evaluations / n

10

40

0

10

20
30
Gradient evaluations / n

40

−2

−8

10

10

−8

10

−12

−12

0

0.1

0.2
0.3
Running time (sec)

0.4

10

−4

10

−8

*

10

2

4
6
Running time (sec)

8

10

(a) Lasso, λ2 = 10−4

10

−8

10
10

−12

0

−6

10

−10

10

10

10

−6

10

−10

−10

−10

10

−6

SAGA
Prox−SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

10

s

s

10

−4

10

SAGA
Prox−SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−4

10

F (x ) − F (x )

−6

10

F (xs ) − F (x* )

*

F (x ) − F (x )

−4

10

SAGA
Prox−SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

10

F (xs ) − F (x* )

SAGA
Prox−SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

10

−12

0

5
10
Running time (sec)

15

10

0

10

20
30
40
Running time (sec)

50

60

(b) Elastic-net, λ1 = λ2 = 10−5

Figure 4: Comparison of all the stochastic methods for solving Lasso and elastic-net problems on Ijcnn1 (first
column), Rcv1 (second column), Covtype (third column), and SUSY (last column).
We also compared the performance of all these methods, when the regularization parameter is relatively
small, as shown in Figure 3. The result shows that
Katyusha, SVRG-SD and SAGA-SD converge significantly faster than the other methods. In particular,
SVRG-SD and SAGA-SD also outperform the wellknown accelerated methods, Catalyst and Katyusha,
which further verifies the importance of our sufficient
decrease technique for stochastic optimization.
6.3

Lasso and Elastic-Net

Finally, we conducted some experiments for the generalized regression problem (12), including Lasso (i.e.,
λ1 ≡ 0) and elastic-net (i.e., λ1 6= 0 and λ2 6= 0) problems as non-SC and non-smooth examples.
We plot some representative results in Figure 4 (see the
Supplementary Material for more results), which show
that SVRG-SD and SAGA-SD significantly outperform their counterparts (i.e., Prox-SVRG and SAGA)
in all the settings, and are considerably better than the
accelerated methods, Catalyst and Katyusha, in most
cases. This empirically verifies that our sufficient decrease technique allows us to take much larger step
sizes for SVRG-SD and SAGA-SD than the original
SVRG/Prox-SVRG and SAGA (e.g., η = 1 for SVRGSD vs. η = 0.4 for SVRG), and can accelerate them for
solving both SC and non-SC objective functions.

7

Conclusions & Future Work

To the best of our knowledge, this is the first work
to design an efficient sufficient decrease technique for
stochastic optimization. Moreover, we proposed two

different schemes for Lasso and ridge regression to efficiently update the coefficient θ, which takes the important decisions to shrink, expand or move in the opposite direction. This is very different from adaptive
learning rate methods, e.g., [43], and line search methods, e.g., [29], all of which cannot address the issue
in Section 3.1 whatever value the step size is. Unlike
most stochastic variance reduction methods [3, 8, 14],
which only have convergence guarantees for SC problems2 , we provided the convergence guarantees of our
algorithm for both SC and non-SC objective functions.
Experimental results verified the effectiveness of our
sufficient decrease technique for stochastic optimization, especially for the case when the regularization
parameter is relatively small (or the condition number
κ := L/µ is relatively large). Naturally, it can also
be used to further speed up accelerated methods such
as [16, 18, 19, 44].
As each component function fi (·) may have different degrees of smoothness, to select the random index isk from a non-uniform distribution is a much better choice than simple uniform random sampling [4],
as well as without-replacement sampling vs. withreplacement sampling [45]. On the practical side, both
our algorithms tackle the non-SC and non-smooth
problems directly, without using any quadratic regularizer as in [16, 18], as well as the proximal setting.
Note that some asynchronous parallel and distributed
variants [46, 47, 48, 49] of stochastic variance reduction
methods have also been proposed for such stochastic
settings. We leave these variations out from our comparison and consider similar extensions to our stochas2
[15] proposed a simple SVRG version with convergence
guarantees for both SC and non-SC problems as in SAGA.

Fanhua Shang,

Yuanyuan Liu,

Kaiwen Zhou,

tic sufficient decrease method as future work.
Acknowledgments
We thank the reviewers for their valuable comments.
This work was supported in part by Grants (CUHK
14206715 & 14222816) from the Hong Kong RGC.

References
[1] A. Krizhevsky, I. Sutskever, and G. E. Hinton.
ImageNet classification with deep convolutional
neural networks. In NIPS, pages 1097–1105, 2012.

James Cheng,

Kelvin K.W. Ng

[12] M. Schmidt, N. Le Roux, and F. Bach. Minimizing finite sums with the stochastic average gradient. Math. Program., 162:83–112, 2017.
[13] S. Shalev-Shwartz and T. Zhang. Accelerated
proximal stochastic dual coordinate ascent for
regularized loss minimization. Math. Program.,
155:105–145, 2016.
[14] L. Xiao and T. Zhang. A proximal stochastic gradient method with progressive variance reduction.
SIAM J. Optim., 24(4):2057–2075, 2014.

[2] T. Zhang. Solving large scale linear prediction
problems using stochastic gradient descent algorithms. In ICML, pages 919–926, 2004.

[15] T. Hofmann, A. Lucchi, S. Lacoste-Julien, and
B. McWilliams. Variance reduced stochastic gradient descent with neighbors. In NIPS, pages
2296–2304, 2015.

[3] R. Johnson and T. Zhang. Accelerating stochastic
gradient descent using predictive variance reduction. In NIPS, pages 315–323, 2013.

[16] H. Lin, J. Mairal, and Z. Harchaoui. A universal catalyst for first-order optimization. In NIPS,
pages 3366–3374, 2015.

[4] P. Zhao and T. Zhang. Stochastic optimization
with importance sampling for regularized loss minimization. In ICML, pages 1–9, 2015.

[17] A. Nitanda. Stochastic proximal gradient descent
with acceleration techniques. In NIPS, pages
1574–1582, 2014.

[5] A. Rakhlin, O. Shamir, and K. Sridharan. Making gradient descent optimal for strongly convex
stochastic optimization. In ICML, pages 449–456,
2012.

[18] Z. Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. In STOC,
pages 1200–1205, 2017.

[6] O. Shamir and T. Zhang. Stochastic gradient descent for non-smooth optimization: Convergence
results and optimal averaging schemes. In ICML,
pages 71–79, 2013.
[7] N. Le Roux, M. Schmidt, and F. Bach. A stochastic gradient method with an exponential convergence rate for finite training sets. In NIPS, pages
2672–2680, 2012.
[8] S. Shalev-Shwartz and T. Zhang. Stochastic dual
coordinate ascent methods for regularized loss
minimization. J. Mach. Learn. Res., 14:567–599,
2013.
[9] A. Defazio, F. Bach, and S. Lacoste-Julien.
SAGA: A fast incremental gradient method with
support for non-strongly convex composite objectives. In NIPS, pages 1646–1654, 2014.
[10] A. Defazio, T. Caetano, and J. Domke. Finito: A
faster, permutable incremental gradient method
for big data problems. In ICML, pages 1125–1133,
2014.
[11] J. Mairal. Incremental majorization-minimization
optimization with application to large-scale machine learning. SIAM J. Optim., 25(2):829–855,
2015.

[19] Z. Allen-Zhu and Y. Yuan. Improved SVRG for
non-strongly-convex or sum-of-non-convex objectives. In ICML, pages 1080–1089, 2016.
[20] R. Babanezhad, M. O. Ahmed, A. Virani,
M. Schmidt, J. Konecny, and S. Sallinen. Stop
wasting my gradients: Practical SVRG. In NIPS,
pages 2242–2250, 2015.
[21] L. Zhang, M. Mahdavi, and R. Jin. Linear convergence with condition number independent access
of full gradients. In NIPS, pages 980–988, 2013.
[22] F. Shang, Y. Liu, J. Cheng, and J. Zhuo.
Fast stochastic variance reduced gradient method
with momentum acceleration for machine learning. arXiv:1703.07948v2, 2017.
[23] E. Hazan and H. Luo. Variance-reduced and
projection-free stochastic optimization. In ICML,
pages 1263–1271, 2016.
[24] B. Woodworth and N. Srebro. Tight complexity
bounds for optimizing composite objectives. In
NIPS, pages 3639–3647, 2016.
[25] H. Li and Z. Lin. Accelerated proximal gradient
methods for nonconvex programming. In NIPS,
pages 379–387, 2015.

Guaranteed Sufficient Decrease for Stochastic Variance Reduced Gradient Optimization

[26] P. Wolfe. Convergence conditions for ascent methods. SIAM Review, 11(2):226–235, 1969.

[41] Y. Nesterov. Smooth minimization of non-smooth
functions. Math. Program., 103:127–152, 2005.

[27] A. Defazio. A simple practical accelerated method
for finite sums. In NIPS, pages 676–684, 2016.

[42] Jakub Koneeny, Jie Liu, Peter Richtarik, , and
Martin Takae. Mini-batch semi-stochastic gradient descent in the proximal setting. IEEE J. Sel.
Top. Sign. Proces., 10(2):242–255, 2016.

[28] J. More and D. Thuente. Line search algorithms
with guaranteed sufficient decrease. ACM T.
Math. Software, 20:286–307, 1994.
[29] M. Mahsereci and P. Hennig. Probabilistic line
searches for stochastic optimization. In NIPS,
pages 181–189, 2015.
[30] Y. Liu, F. Shang, and J. Cheng. Accelerated variance reduced stochastic ADMM. In AAAI, pages
2287–2293, 2017.
[31] Y. Nesterov.
A method of solving a convex programming problem with convergence rate
O(1/k 2 ). Soviet Math. Doklady, 27:372–376, 1983.
[32] Y. Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic
Publ., Boston, 2004.
[33] A. Beck and M. Teboulle. A fast iterative
shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci., 2(1):183–
202, 2009.
[34] W. Su, S. Boyd, and E. J. Candes. A differential equation for modeling Nesterov’s accelerated
gradient method: Theory and insights. J. Mach.
Learn. Res., 17:5312–5354, 2016.
[35] D. L. Donoho. De-noising by soft-thresholding.
IEEE Trans. Inform. Theory, 41(3):613–627,
1995.
[36] L. Armijo. Minimization of functions having Lipschitz continuous first partial derivatives. Pacific
J. Math., 16(1):1–3, 1966.
[37] F. Bach and E. Moulines. Non-strongly-convex
smooth stochastic approximation with convergence rate O(1/n). In NIPS, pages 773–781, 2013.
[38] F. Shang, Y. Liu, J. Cheng, K. Ng, and
Y. Yoshida.
Guaranteed sufficient decrease
for variance reduced stochastic gradient descent.
arXiv: 1703.06807v2, 2017.
[39] R. Frostig, R. Ge, S. M. Kakade, and A. Sidford.
Un-regularizing: approximate proximal point and
faster stochastic algorithms for empirical risk minimization. In ICML, pages 2540–2548, 2015.
[40] Z. Allen-Zhu and E. Hazan. Optimal black-box
reductions between optimization objectives. In
NIPS, pages 1606–1614, 2016.

[43] D. P. Kingma and J. Ba. Adam: A method for
stochastic optimization. In ICLR, 2015.
[44] F. Shang, K. Zhou, J. Cheng, I. W. Tsang,
L. Zhang, and D. Tao. VR-SGD: A simple stochastic variance reduction method for machine learning. arXiv:1704.04966v2, 2017.
[45] O. Shamir. Without-replacement sampling for
stochastic gradient methods. In NIPS, pages 46–
54, 2016.
[46] S. Reddi, A. Hefny, S. Sra, B. Poczos, and
A. Smola. On variance reduction in stochastic
gradient descent and its asynchronous variants. In
NIPS, pages 2629–2637, 2015.
[47] H. Mania, X. Pan, D. Papailiopoulos, B. Recht,
K. Ramchandran, and M. I. Jordan. Perturbed
iterate analysis for asynchronous stochastic optimization. SIAM J. Optim., 27(4):2202–2229,
2017.
[48] F. Pedregosa, R. Leblond, and S. Lacoste-Julien.
Breaking the nonsmooth barrier: A scalable parallel method for composite optimization. In NIPS,
pages 55–64, 2017.
[49] J. D. Lee, Q. Lin, T. Ma, and T. Yang. Distributed stochastic variance reduced gradient
methods by sampling extra data with replacement. J. Mach. Learn. Res., 18:1–43, 2017.
[50] Z. Allen-Zhu and Y. Yuan. Improved SVRG for
non-strongly-convex or sum-of-non-convex objectives. arXiv: 1506.01972v3, 2016.
[51] L. Baldassarre and M. Pontil. Advanced topics
in machine learning part II: 5. Proximal methods.
University Lecture, 2013.
[52] G. Lan. An optimal method for stochastic composite optimization. Math. Program., 133:365–
397, 2012.

Fanhua Shang,

Yuanyuan Liu,

Kaiwen Zhou,

James Cheng,

Kelvin K.W. Ng

Supplementary Materials for “Guaranteed Sufficient Decrease for
Stochastic Variance Reduced Gradient Optimization”

Fanhua Shang, Yuanyuan Liu, Kaiwen Zhou, James Cheng, Kelvin K.W. Ng
Department of Computer Science and Engineering, The Chinese University of Hong Kong
Yuichi Yoshida
National Institute of Informatics, Tokyo, Japan

In this supplementary material, we give the detailed
proofs for some lemmas, theorems and corollaries
stated in the main paper. Moreover, we also report
more experimental results for both of our algorithms
on several dense and sparse data sets.

Using the above definition, our algorithms naturally
generalize to the mini-batch setting.

Appendix A: Proof of Theorem 1
Notations
Throughout this paper, k·k denotes the standard Euclidean norm, and k · k1 is the ℓ1 -norm, i.e., kxk1 =
Pd
i=1 |xi |. We denote by ∇f (x) the full gradient of
f (x) if it is differentiable, or ∂f (x) the subdifferential of f (·) at x if it is only Lipschitz continuous. Note
that Assumption 2 is the general form for the two cases
when F (x) is smooth or non-smooth3 . That is, if F (x)
is smooth, the inequality in (12) in Assumption 2 becomes the following form:
F (y) ≥ F (x) + ∇F (x)(y − x) +

µ
ky − xk2 .
2

In the main paper, we assume that all component functions have the same smoothness parameter, L. In fact,
we can extend the theoretical result for the case, when
the gradients of all component functions have the same
Lipschitz constant L, to the more general case, when
some component functions fi (·) have different degrees
of smoothness.
Definition 1. The SVRG estimator in the mini-batch
setting is defined as follows:
X

e I s (xsk ) = 1
∇fi (xsk )−∇fi (e
xs−1 ) +∇f (e
xs−1 )
∇f
k
b s
i∈Ik

where Iks ⊂ [n] is a mini-batch of size b.
3

Strictly speaking, when the function F (·) is non-

smooth, ϑ ∈ ∂F (x); while F (·) is smooth, ϑ = ∇F (x).

Although the proposed SVRG-SD algorithm is a variant of SVRG, it is non-trivial to analyze its convergence property. Before proving Theorem 1, we first
give the following lemma.
Lemma 1. Let x∗ be the optimal solution of Problem
(1), then the following inequality holds
h
E ∇fisk(xsk−1 )−∇f (xsk−1 )−∇fisk(e
xs−1 )+∇f (e
xs−1 )


xs−1 ) − F (x∗ ) .
≤ 4L F (xsk−1 ) − F (x∗ ) + F (e

2

i

Lemma 1 provides the upper bound on the expected
variance of the variance reduced gradient estimator
in (9) (i.e., the SVRG estimator independently ine is (xs )] =
troduced in [3, 21]), which satisfies E[∇f
k−1
k
s
∇f (xk−1 ). This lemma is essentially identical to Corollary 3.5 in [14] and Lemma A.2 in [50]. In addition,
e is (xs ) can be
the upper bound on the variance of ∇f
k
k
extended to the mini-batch setting as in [42].
Using Lemma 1, we immediately get the following result, which is useful in our convergence analysis.
Corollary 2. For any α ≥ β > 0, the following in-

equality holds
h
i
2
xs−1 )+∇f (e
xs−1 )
αE ∇fisk(xsk−1 ) −∇f (xsk−1 )−∇fisk(e
h
i
2
− βE ∇fisk(xsk−1 )−∇fisk(e
xs−1 )


≤ 4L(α−β) F (xsk−1 ) − F (x∗ ) + F (e
xs−1 ) − F (x∗ ) .

Guaranteed Sufficient Decrease for Stochastic Variance Reduced Gradient Optimization

Proof.
i
h
2
− βE ∇fisk(xsk−1 )−∇fisk(e
xs−1 )
i
h
i
2
2
[∇fisk(xsk−1 )−∇fisk(e
xs−1 )]−[∇f (xsk−1 )−∇f (e
xs−1 )]
xs−1 )
− βE ∇fisk(xsk−1 )−∇fisk(e
i
i
h
2
2
2
−α ∇f (xsk−1 )−∇f (e
xs−1 ) −βE ∇fisk(xsk−1 )−∇fisk(e
xs−1 )
∇fisk(xsk−1 )−∇fisk(e
xs−1 )
i
h
i
2
2
−βE ∇fisk(xsk−1 )−∇fisk(e
∇fisk(xsk−1 ) − ∇fisk(e
xs−1 )
xs−1 )
h 
i

2
= (α−β)E ∇fisk(xsk−1 ) − ∇fisk(x∗ ) − [∇fisk(e
xs−1 ) − ∇fisk(x∗ )]
io
i
h
n h
2
2
+ E ∇fisk(e
xs−1 ) − ∇fisk(x∗ )
≤ 2(α−β) E ∇fisk(xsk−1 ) − ∇fisk(x∗ )


xs−1 ) − F (x∗ ) ,
≤ 4L(α−β) F (xsk−1 ) − F (x∗ ) + F (e
h
αE
h
= αE
h
= αE
h
≤ αE

xs−1 )+∇f (e
xs−1 )
∇fisk(xsk−1 )−∇f (xsk−1 )−∇fisk(e

2

i

where the second equality holds due to the fact that E[kx−Exk2 ] = E[kxk2 ]−kExk2 ; the second inequality holds
due to the fact that ka − bk2 ≤ 2(kak2 + kbk2 ); and the last inequality follows from Lemma 3.4 in [14] (i.e.,
2

E[k∇fi (x)−∇fi (x∗ )k ] ≤ 2L[F (x)−F (x∗ )]).
Moreover, we also introduce the following lemmas [51, 52], which are useful in our convergence analysis.
Lemma 2. Let Fe(x, y) be the linear approximation of F (·) at y with respect to f , i.e.,
Fe (x, y) = f (y) + h∇f (y), x − yi + r(x).

Then

L
L
F (x) ≤ Fe (x, y) + kx − yk2 ≤ F (x) + kx − yk2 .
2
2
Lemma 3. Assume that x̂ is an optimal solution of the following problem,
min

x∈Rd

τ
kx − yk2 + g(x),
2

where g(x) is a convex function (but possibly non-differentiable). Then the following inequality holds for all
x ∈ Rd :
g(x̂) +

τ
τ
τ
kx̂ − yk2 + kx − x̂k2 ≤ g(x) + kx − yk2 .
2
2
2

Proof of Theorem 1:
Proof. Let η =

1
Lα

e is(xs ) = ∇fis(xs ) − ∇fis(e
xs−1 ) + ∇f (e
xs−1 ). Using Lemma 2, we have
and pisk = ∇f
k−1
k−1
k
k
k

Lα s
L(α−1) s
2
2
yk −xsk−1 −
yk −xsk−1 + r(yks )
2
2
Lα s
= fisk(xsk−1 ) + pisk , yks − xsk−1 + r(yks ) +
ky − xsk−1 k2
2 k
L(α−1) s
kyk − xsk−1 k2 + f (xsk−1 ) − fisk (xsk−1 ).
+ ∇f (xsk−1 ) − pisk , yks − xsk−1 −
2

(13)

L(α−1) s
kyk − xsk−1 k2
2
L(α−1) s
L(α−1) s
1
k∇f (xsk−1 ) − pisk k2 +
kyk −xsk−1 k2 −
kyk −xsk−1 k2
≤
2L(α−1)
2
2
1
k∇f (xsk−1 ) − pisk k2 ,
=
2L(α−1)

(14)

F (yks ) ≤ f (xsk−1 ) + ∇f (xsk−1 ), yks −xsk−1 +

Then
∇f (xsk−1 ) − pisk , yks − xsk−1 −

Fanhua Shang,

Yuanyuan Liu,

Kaiwen Zhou,

James Cheng,

Kelvin K.W. Ng

where the inequality follows from the Young’s inequality, i.e., aT b ≤ kak2 /(2ρ) + ρkbk2 /2 for any ρ > 0. Substituting the inequality (14) into the inequality (13), we have
F (yks ) ≤ fisk(xsk−1 ) + pisk , yks − xsk−1 + r(yks ) +

Lα s
kyk − xsk−1 k2
2

1
k∇f (xsk−1 ) − pisk k2 + f (xsk−1 ) − fisk (xsk−1 )
2L(α−1)

Lα
s
s
s
s
bk−1
−xsk−1 i
kw
bk−1
−xsk−1 k2 −kw
bk−1
−yks k2 + hpisk , w
≤ fisk(xsk−1 ) + r(w
bk−1
)+
2
1
+
k∇f (xsk−1 ) − pisk k2 + f (xsk−1 ) − fisk (xsk−1 )
2L(α−1)

Lα
s
s
s
kw
bk−1
− xsk−1 k2 − kw
bk−1
− yks k2 + f (xsk−1 ) − fisk (xsk−1 )
bk−1
)+
≤ Fisk(w
2
1
s
+
xs−1 ) + ∇f (e
xs−1 ), w
bk−1
− xsk−1
k∇f (xsk−1 ) − pisk k2 + −∇fisk (e
2L(α−1)

Lασ 2
s
≤ σFisk(x∗ ) + (1 − σ)Fisk(b
xsk−1 ) +
kx∗ − zk−1
k2 − kx∗ − zks k2
2
1
s
2
+
k∇f (xk−1 ) − pisk k + f (xsk−1 ) − fisk (xsk−1 )
2L(α−1)
+

(15)

s
+ ∇f (e
xs−1 )−∇fisk (e
xs−1 ), w
bk−1
−xsk−1 ,

s
where w
bk−1
= σx∗ + (1 − σ)b
xsk−1 , and x
bsk−1 = θk−1 xsk−2 . The second inequality follows from Lemma 3 with
s
g(x) := pisk , x−xsk−1 + r(x), τ = Lα, x̂ = yks , x = w
bk−1
and y = xsk−1 ; the third inequality holds due to the

s
s
bk−1
)); and the last
bk−1
−xsk−1 i ≤ fisk(w
convexity of the component function fisk (x) (i.e., fisk(xsk−1 )+h∇fisk(xsk−1 ), w

inequality holds due to the convexity of the function Fisk(x) := fisk(x)+r(x), and

s
zk−1
= [xsk−1 − (1−σ)b
xsk−1 ]/σ, zks = [yks − (1−σ)b
xsk−1 ]/σ,
s
s
s
which mean that w
bk−1
− xsk−1 = σ(x∗ − zk−1
) and w
bk−1
− yks = σ(x∗ − zks ).

Using Property 1 with ζ =

δη
1−Lη

and η = 1/Lα,4 we obtain

(θk −1)2
xs−1 )k2
k∇fisk(xsk−1 ) −∇fisk(e
2L(α − 1)
βk
≤ F (xsk−1 ) −
k∇fisk(xsk−1 ) −∇fisk(e
xs−1 )k2 ,
2L(α−1)

F (θk xsk−1 ) = F (b
xsk ) ≤ F (xsk−1 ) −



where βk = min 1/αk , (θk −1)2 , and αk is defined below. Then there exists β k such that




βk
βk
s−1 2
s
s
s
x )k =
xs−1 )k2 ,
k∇fik(xk−1 ) −∇fik(e
E k∇fisk(xsk−1 ) −∇fisk(e
E
2L(α−1)
2L(α−1)

(16)

(17)

where β k = E[βk k∇fisk(xsk−1 ) − ∇fisk(e
xs−1 )k2 ], and β k < (α − 1)/2. Using the
xs−1 )k2 ]/E[k∇fisk(xsk−1 ) − ∇fisk(e
inequality (16), then we have

E[F (b
xsk ) − F (x∗ )] ≤ E F (xsk−1 ) − F (x∗ ) −

4


βk
xs−1 )k2
k∇fisk(xsk−1 ) −∇fisk(e
2L(α−1)




βk
E k∇fisk(xsk−1 ) −∇fisk(e
xs−1 )k2 .
= E F (xsk−1 ) − F (x∗ ) −
2L(α−1)

(18)

Note that our fast versions of SVRG-SD (i.e., SVRG-SD with randomly partial sufficient decrease) have the similar

convergence properties as SVRG-SD because Property 1 still holds in the case when θk = 1. That is, the main difference
between their convergence properties is the different values of βk , as shown below.

Guaranteed Sufficient Decrease for Stochastic Variance Reduced Gradient Optimization



There must exist a constant αk > 0 such that E[F (yks )−F (x∗ )] = αk E F (xsk−1 )−F (x∗ ) .
Since








s
s−1
s−1
∗
∗
s
s
s
x ) = ∇f (e
x ), E Fisk(x ) = F (x ), and E Fisk(xk−1 ) = F (xk−1 ), and
E f (xk−1 )−fisk(xk−1 ) = 0, E ∇fisk (e
taking the expectation of both sides of (15), we have


αk E F (xsk−1 ) − F (x∗ ) −



ck β k
xs−1 )k2
E k∇fisk(xsk−1 ) −∇fisk(e
2L(α−1)

 Lασ 2  ∗

s
≤ (1 − σ)E F (b
xsk−1 ) − F (x∗ ) +
E kx − zk−1
k2 − kx∗ − zks k2
2


1
ck β k
+
xs−1 )k2
Ek∇f (xsk−1 ) − pisk k2 −
E k∇fisk(xsk−1 ) −∇fisk(e
2L(α−1)
2L(α−1)

 Lασ 2  ∗

s
≤(1 − σ)E F (b
xsk−1 ) − F (x∗ ) +
E kx − zk−1
k2 − kx∗ − zks k2
2

2(1 − ck β k ) 
F (xsk−1 ) − F (x∗ ) + F (e
xs−1 ) − F (x∗ ) ,
+
α−1

(19)

where the second inequality follows from Lemma 1 and Corollary 2. Here, ck = αk − [2(1−ck β k )]/(α−1), i.e.,
ck =
Since

2
α−1

αk (α − 1) − 2
.
α − 1 − 2β k

< σ with the suitable choices of α and σ, we have ck > αk −

2
α−1

> 1 − σ. Thus, (19) is rewritten as

follows:


ck β k
E kpisk −∇fisk(e
xs−1 )k2
2L(α − 1)

Lασ 2  ∗
s
E kx − zk−1
k2 − kx∗ − zks k2
≤ (1 − σ)E[F (b
xsk−1 ) − F (x∗ )] +
2

2(1 − ck β k ) 
+
E F (e
xs−1 ) − F (x∗ ) .
α−1


ck E F (xsk−1 ) − F (x∗ ) −

(20)

Combining the above two inequalities (18) and (20), we have
ck E[F (b
xsk ) − F (x∗ )]

 Lασ 2  ∗

s
≤ (1 − σ)E F (b
xsk−1 ) − F (x∗ ) +
E kx − zk−1
k2 − kx∗ − zks k2
2

2(1 − ck β k ) 
E F (e
xs−1 ) − F (x∗ ) .
+
α−1

(21)

Taking the expectation over the random choice of is1 , is2 , . . . , ism , summing up the above inequality over k =
1, . . . , m, and x
bs0 = x
es−1 , we have
"

E

m
X

[ck − (1 −

k=1

σ)] [F (b
xsk )

∗

− F (x )]

#


 Lασ 2  ∗

s 2
≤ (1 − σ)E F (e
xs−1 ) − F (x∗ ) +
E kx − z0s k2 − kx∗ − zm
k
2
"m
#
X 2(1 − ck β )
k
s−1
∗
+E
[F (e
x ) − F (x )] .
α−1
k=1

(22)

Fanhua Shang,

Yuanyuan Liu,

Kaiwen Zhou,

In addition, there exists βbs for the s-th epoch such that
"

E

m
X

[ck − (1 −

σ)] [F (b
xsk )

James Cheng,

∗

− F (x )]

k=1
"m 
X

Kelvin K.W. Ng

#

#

2ck β k
2
[F (b
xsk ) − F (x∗ )]
+
=E
σ−
α−1
α−1
k=1
#

 "X
m
2
s
s
∗
= σ−
+ βb E
[F (b
xk ) − F (x )] ,
α−1

(23)

k=1

where

Let βb = mins=1,...,S βbs . Using
(22) and (23), we have

i
hP
m
2ck βk
s
∗
[F
(b
x
)
−
F
(x
)]
E
k
k=1 α−1
P
.
βbs =
s ) − F (x∗ )]]
E[ m
[F
(b
x
k=1
k
x
es =

m
m
1 X s
1 X
x
bk , F (e
xs ) ≤
F (b
xsk ),
m
m
k=1

k=1



2
b
σ−
+ β mE[F (e
xs ) − F (x∗ )]
α−1




2m
E F (e
xs−1 ) − F (x∗ )
≤ 1−σ+
α−1

Lασ 2  ∗
s 2
+
E kx − z0s k2 − kx∗ − zm
k .
2

Therefore,

E[F (e
xs ) − F (x∗ )]

1−σ
2
 +

≤ 
2
b
σ − α−1 + β m (α−1) σ −
+

This completes the proof.

2
α−1





  E F (e
xs−1 ) − F (x∗ )
+ βb



Lασ 2
s 2
 E kx∗ − z0s k2 − kx∗ − zm

k .
2
+ βb
2m σ − α−1

Appendix B: Proofs of Corollary 1
Proof. For µ-strongly convex problems, and let xs0 = x
bs0 = x
es−1 and
z0s =

Due to the strong convexity of F (·), we have

xs0 − (1 − σ)b
xs0
=x
es−1 .
σ

µ
µ ∗
kx − z0s k2 = kx∗ − x
es−1 k2 ≤ F (e
xs−1 ) − F (x∗ ).
2
2

(24)

Guaranteed Sufficient Decrease for Stochastic Variance Reduced Gradient Optimization

Using Theorem 1, we obtain
E[F (e
xs ) − F (x∗ )]


2


1−σ
Lασ
2
s−1
∗
+
  E F (e


≤
x
)
−
F
(x
)
.
+
2
b
2
2
+ β)
m(σ− α−1
+ βb
+ βb
(α−1) σ− α−1
mµ σ− α−1

Replacing α and σ in the above inequality with 19 and 1/2, respectively, we have
E[F (e
xs ) − F (x∗ )]
≤
This completes the proof.

9

2

171L
+
+
b
b
(7 + 18β)m
7 + 18βb (14 + 36β)mµ

!



E F (e
xs−1 ) − F (x∗ ) .

Appendix C: Proofs of Theorem 2
Proof. For non-strongly convex problems, and using Theorem 1 with α = 19 and σ = 1/2, we have
i
h
171L
s 2
E kx∗ − z0s k2 − kx∗ − zm
k
E[F (e
xs ) − F (x∗ )] ≤
b
(28 + 72β)m
!


2
9
+
F (e
xs−1 ) − F (x∗ ) .
+
b
(7 + 18β)m
7 + 18βb

According to the settings of Algorithm 1 for the non-strongly convex case, and let

then we have
z0s =

s−1
s−1
xs0 = x
bs0 = [xm
− (1 − σ)b
xm
]/σ,

s−1
xs0 − (1 − σ)b
xs0
xs−1 − (1 − σ)b
xm
= m
,
σ
σ

and
s−1
zm
=

s−1
s−1
xm
− (1 − σ)b
xm
.
σ

s−1
Therefore, z0s = zm
.

Using z00 = x
e0 , and summing up the inequality (25) over all s = 1, . . . , S, then
"
!
#
S
1X s
171L
2
∗
E F
x
e − F (x ) ≤
x∗ − x
e0
b
S s=1
(16 + 40β)mS
!


1
9
+
F (e
x0 ) − F (x∗ ) .
+
b
b
(4 + 8β)mS
(2 + 4β)S

Due to the settings of Algorithm 1 for the non-strongly convex case, we have
E[F (x) − F (x∗ )] ≤

171L
x∗ − x
e0
b
(16 + 40β)mS
+

This completes the proof.

2

1
9
+
b
b
(4 + 8β)mS
(2 + 4β)S

!




F (e
x0 ) − F (x∗ ) .

(25)

Yuanyuan Liu,

Kaiwen Zhou,

SAGA
SAGA−SD (m =1000)
1

−4

10

Objective minus best

Objective minus best

Fanhua Shang,

SAGA−SD (m =500)
1

SAGA−SD (m1=250)
−8

10

−12

10

James Cheng,

Kelvin K.W. Ng

SAGA
SAGA−SD (m1=1000)

−4

10

SAGA−SD (m =500)
1

SAGA−SD (m1=250)
−8

10

−12

0

10
20
30
Number of effective passes

40

(a) Objective gap vs. number of passes

10

0

2

4
6
Running time (sec)

8

(b) Objective gap vs. running time

Figure 5: Comparison of SAGA and SAGA-SD with different values of m1 for solving ridge regression problems
on the Covtype dataset.

Appendix D: Experiment Details
The C++ code of SVRG [3] was downloaded from http://riejohnson.com/svrg_download.html. The code
of of SAGA [9] was downloaded from http://www.aarondefazio.com/software.html. For fair comparison,
we implemented the proposed SVRG-SD and SAGA-SD algorithms, SAGA [9], Prox-SVRG [14], Catalyst [16]
(which is based on SVRG and has the following three important parameters: αk , κ, and the step size, η), and
Katyusha [18] in C++ with a Matlab interface5 , and performed all the experiments on a PC with an Intel i5-2400
CPU and 16GB RAM.

Appendix E: More Experimental Results
Robustness
Figure 5 shows the performance of SAGA [9] and SAGA-SD with different values of m1 for solving ridge regression
problems on the Covtype data set, where the regularization parameter is λ1 = 10−4 . From the result, we can
observe that SAGA-SD significantly outperforms SAGA in terms of number of passes and running time. In
particular, SAGA-SD, as well as SVRG-SD, has good robustness with respect to the number of iterations with
sufficient decrease, which inspires us to use the partial sufficient decrease trick for both SVRG-SD and SAGA-SD.

Comparison of Results for Ridge Regression
In this part, we first report the experimental results of SVRG [3], SAGA [9], Catalyst [16], Katyusha [18],
SVRG-SD and SAGA-SD for solving strongly convex (SC) ridge regression problems with the regularization
parameter λ1 = 10−5 in Figure 6, where the horizontal axis denotes the number of effective passes over the data
set (evaluating n component gradients, or computing a single full gradient is considered as one effective pass)
or the running time (seconds). Moreover, we report the performance of all the stochastic variance reduction
methods for solving ridge regression problems with relative small regularization parameters (e.g., λ1 = 10−7) in
Figure 7, which shows that SVRG-SD and SAGA-SD, as well as Katyusha, converge significantly faster than
SAGA, SVRG, and Catalyst. In particular, SVRG-SD and SAGA-SD usually outperform Katyusha in terms
of both number of passes and running time, which further justifies the effectiveness of our sufficient decrease
technique for stochastic optimization.
5

The codes of some algorithms can be downloaded by the following anonymous link:
https://www.dropbox.com/s/pyjeegseht77toh/Code_SVRG_SD.zip?dl=0.

Guaranteed Sufficient Decrease for Stochastic Variance Reduced Gradient Optimization
−2

10

−6

10

−8

10

10

−4

10

−8

10

−10

−10

−12

10

20
30
40
Gradient evaluations / n

50

10

60

−8

10
10

−12

0

−6

10

−10

10

10
10

−6

SAGA
SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

10

F (xs ) − F (x* )

−4

10

SAGA
SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−4

F (xs ) − F (x* )

10

F (xs ) − F (x* )

10

SAGA
SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

−12

0

10

20
30
Gradient evaluations / n

40

10

50

0

10

20
30
40
Gradient evaluations / n

50

−2

F (xs ) − F (x* )

−4

10

−6

10

−8

10

10

−6

10

−4

10

−8

10

0.1

0.2
0.3
0.4
Running time (sec)

(a) Ijcnn1, λ1 = 10−5

0.5

0.6

10

−8

10
10

−12

0

−6

10

−10

10

−12

SAGA
SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

10

−10

−10

10
10

SAGA
SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−4

F (xs ) − F (x* )

10

10

F (xs ) − F (x* )

SAGA
SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

−12

0

2

4
6
Running time (sec)

8

(b) Covtype, λ1 = 10−5

10

10

0

10

20
30
40
Running time (sec)

50

60

(c) SUSY, λ1 = 10−5

Figure 6: Comparison of all the stochastic variance reduced gradient methods for solving strongly convex ridge
regression problems on the three dense data sets: Ijcnn1, Covtype and SUSY. The vertical axis is the objective
value minus the minimum, and the horizontal axis denotes the number of effective passes over the data (top) or
the running time (bottom).

Figure 8 shows the performance of all the methods for solving ridge regression problems with different regularization parameters on the sparse data set, Rcv1. From the results, we can observe that SVRG-SD and SAGA-SD
significantly outperform their counterparts: SVRG and SAGA in terms of both number of effective passes and
running time. The accelerated method, Catalyst, usually outperforms the non-accelerated methods, SVRG and
SAGA. Katyusha converges much faster than SAGA, SVRG, and Catalyst for the cases when the regularization
parameter is relatively small (e.g., λ1 = 10−5 ), whereas it sometime achieves similar or inferior performance when
the regularization parameter is relatively large (e.g., λ1 = 10−3 ), as shown in Figures 8(a). Moreover, SVRG-SD
and SAGA-SD achieve at least comparable performance with the accelerated stochastic method, Katyusha [18],
in terms of number of effective passes. Since SVRG-SD and SAGA-SD have much lower per-iteration complexities
than Katyusha, they have more obvious advantage over Katyusha in terms of running time.

Comparison of Results for Lasso and Elastic-Net
Finally, we report the performance of Prox-SVRG [14], SAGA [9], Catalyst [16], Katyusha [18], SVRG-SD and
SAGA-SD for solving Lasso and elastic-net problems with different regularization parameters in Figures 9 and
10, respectively, from which we can observe that SVRG-SD and SAGA-SD also achieve much faster convergence
speed than their counterparts: Prox-SVRG and SAGA, respectively. In particular, they also have comparable
or better performance than the accelerated methods, Catalyst and Katyusha for both strongly convex and nonstrongly convex problems. For the elastic-net problem, each component function fi (x) is defined as follows:

fi (x) =

λ1
1 T
(a x − bi )2 + kxk2 .
2 i
2

Fanhua Shang,

Yuanyuan Liu,

Kaiwen Zhou,

James Cheng,

Kelvin K.W. Ng

−2

F (xs ) − F (x* )

−4

10

10

−4

F (xs ) − F (x* )

10

−6

10

−8

10

−10

10

10

−6

10

−8

10

10

20
30
40
Gradient evaluations / n

50

10

60

−8

10

−10

−12

0

−6

10

10

10

−12

SAGA
SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−4

−10

10
10

10

SAGA
SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

F (xs ) − F (x* )

SAGA
SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

−12

0

10

20
30
Gradient evaluations / n

40

10

50

0

50

100
150
Gradient evaluations / n

200

−2

−6

10

−8

10

−10

−6

10

−8

10

−12

0

0.1

0.2
0.3
Running time (sec)

(a) Ijcnn1, λ1 = 10−6

0.4

0.5

10

−4

10

−6

10

−8

10

10

10

−12

SAGA
SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−10

−10

10
10

−4

10

10

F (xs ) − F (x* )

F (xs ) − F (x* )

−4

10

SAGA
SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

10

F (xs ) − F (x* )

SAGA
SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

10

−12

0

0.05

0.1

0.15 0.2 0.25
Running time (sec)

(b) Ijcnn1, λ1 = 10−7

0.3

0.35

10

0

10

20

30
40
50
Running time (sec)

60

70

(c) Covtype, λ1 = 10−7

Figure 7: Comparison of all the stochastic variance reduced gradient methods for solving strongly convex ridge
regression problems with relatively small regularization parameters. The vertical axis is the objective value minus
the minimum, and the horizontal axis denotes the number of effective passes over the data (top) or the running
time (bottom).

References
[1] A. Krizhevsky, I. Sutskever, and G. E. Hinton. ImageNet classification with deep convolutional neural
networks. In NIPS, pages 1097–1105, 2012.
[2] T. Zhang. Solving large scale linear prediction problems using stochastic gradient descent algorithms. In
ICML, pages 919–926, 2004.
[3] R. Johnson and T. Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In
NIPS, pages 315–323, 2013.
[4] P. Zhao and T. Zhang. Stochastic optimization with importance sampling for regularized loss minimization.
In ICML, pages 1–9, 2015.
[5] A. Rakhlin, O. Shamir, and K. Sridharan. Making gradient descent optimal for strongly convex stochastic
optimization. In ICML, pages 449–456, 2012.
[6] O. Shamir and T. Zhang. Stochastic gradient descent for non-smooth optimization: Convergence results
and optimal averaging schemes. In ICML, pages 71–79, 2013.
[7] N. Le Roux, M. Schmidt, and F. Bach. A stochastic gradient method with an exponential convergence rate
for finite training sets. In NIPS, pages 2672–2680, 2012.
[8] S. Shalev-Shwartz and T. Zhang. Stochastic dual coordinate ascent methods for regularized loss minimization. J. Mach. Learn. Res., 14:567–599, 2013.
[9] A. Defazio, F. Bach, and S. Lacoste-Julien. SAGA: A fast incremental gradient method with support for
non-strongly convex composite objectives. In NIPS, pages 1646–1654, 2014.

Guaranteed Sufficient Decrease for Stochastic Variance Reduced Gradient Optimization

−4

F (xs ) − F (x* )

−6

10

−8

10

−10

−8

10

10

20
30
Gradient evaluations / n

10

40

SAGA
SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−4

10

10

20
30
Gradient evaluations / n

−8

10

−10

10

40

SAGA
SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−4

−6

10

1

2
3
Running time (sec)

4

5

−6

10

−8

10

10

40
60
80
Gradient evaluations / n

100

SAGA
SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−4

10

−6

10

−8

10

−10

10

−12

−12

0

20

−2

10

−12

0

10

−10

10

−8

10

−12

0

−2

10

−6

10

−10

10

F (xs ) − F (x* )

−2

10

10

−12

0

10

F (xs ) − F (x* )

−6

10

10

−12

10

−4

−10

10
10

10

SAGA
SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

10

F (xs ) − F (x* )

F (xs ) − F (x* )

−4

10

SAGA
SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

10

F (xs ) − F (x* )

SAGA
SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

10

10
0

(a) Rcv1, λ1 = 10−3

1

2
3
Running time (sec)

(b) Rcv1, λ1 = 10−4

4

5

0

2

4
6
Running time (sec)

8

10

(c) Rcv1, λ1 = 10−5

Figure 8: Comparison of all the stochastic variance reduced gradient methods for solving strongly convex ridge
regression problems with different regularization parameters on the sparse data set, Rcv1. The vertical axis
represents the objective value minus the minimum, and the horizontal axis denotes the number of effective
passes (top) or the running time (bottom).
[10] A. Defazio, T. Caetano, and J. Domke. Finito: A faster, permutable incremental gradient method for big
data problems. In ICML, pages 1125–1133, 2014.
[11] J. Mairal. Incremental majorization-minimization optimization with application to large-scale machine
learning. SIAM J. Optim., 25(2):829–855, 2015.
[12] M. Schmidt, N. Le Roux, and F. Bach. Minimizing finite sums with the stochastic average gradient. Math.
Program., 162:83–112, 2017.
[13] S. Shalev-Shwartz and T. Zhang. Accelerated proximal stochastic dual coordinate ascent for regularized loss
minimization. Math. Program., 155:105–145, 2016.
[14] L. Xiao and T. Zhang. A proximal stochastic gradient method with progressive variance reduction. SIAM
J. Optim., 24(4):2057–2075, 2014.
[15] T. Hofmann, A. Lucchi, S. Lacoste-Julien, and B. McWilliams. Variance reduced stochastic gradient descent
with neighbors. In NIPS, pages 2296–2304, 2015.
[16] H. Lin, J. Mairal, and Z. Harchaoui. A universal catalyst for first-order optimization. In NIPS, pages
3366–3374, 2015.
[17] A. Nitanda. Stochastic proximal gradient descent with acceleration techniques. In NIPS, pages 1574–1582,
2014.
[18] Z. Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. In STOC, pages
1200–1205, 2017.
[19] Z. Allen-Zhu and Y. Yuan. Improved SVRG for non-strongly-convex or sum-of-non-convex objectives. In
ICML, pages 1080–1089, 2016.

Fanhua Shang,

Yuanyuan Liu,

Kaiwen Zhou,

James Cheng,

Kelvin K.W. Ng

[20] R. Babanezhad, M. O. Ahmed, A. Virani, M. Schmidt, J. Konecny, and S. Sallinen. Stop wasting my
gradients: Practical SVRG. In NIPS, pages 2242–2250, 2015.
[21] L. Zhang, M. Mahdavi, and R. Jin. Linear convergence with condition number independent access of full
gradients. In NIPS, pages 980–988, 2013.
[22] F. Shang, Y. Liu, J. Cheng, and J. Zhuo. Fast stochastic variance reduced gradient method with momentum
acceleration for machine learning. arXiv:1703.07948v2, 2017.
[23] E. Hazan and H. Luo. Variance-reduced and projection-free stochastic optimization. In ICML, pages 1263–
1271, 2016.
[24] B. Woodworth and N. Srebro. Tight complexity bounds for optimizing composite objectives. In NIPS, pages
3639–3647, 2016.
[25] H. Li and Z. Lin. Accelerated proximal gradient methods for nonconvex programming. In NIPS, pages
379–387, 2015.
[26] P. Wolfe. Convergence conditions for ascent methods. SIAM Review, 11(2):226–235, 1969.
[27] A. Defazio. A simple practical accelerated method for finite sums. In NIPS, pages 676–684, 2016.
[28] J. More and D. Thuente. Line search algorithms with guaranteed sufficient decrease. ACM T. Math.
Software, 20:286–307, 1994.
[29] M. Mahsereci and P. Hennig. Probabilistic line searches for stochastic optimization. In NIPS, pages 181–189,
2015.
[30] Y. Liu, F. Shang, and J. Cheng. Accelerated variance reduced stochastic ADMM. In AAAI, pages 2287–2293,
2017.
[31] Y. Nesterov. A method of solving a convex programming problem with convergence rate O(1/k 2 ). Soviet
Math. Doklady, 27:372–376, 1983.
[32] Y. Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publ.,
Boston, 2004.
[33] A. Beck and M. Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems.
SIAM J. Imaging Sci., 2(1):183–202, 2009.
[34] W. Su, S. Boyd, and E. J. Candes. A differential equation for modeling Nesterov’s accelerated gradient
method: Theory and insights. J. Mach. Learn. Res., 17:5312–5354, 2016.
[35] D. L. Donoho. De-noising by soft-thresholding. IEEE Trans. Inform. Theory, 41(3):613–627, 1995.
[36] L. Armijo. Minimization of functions having Lipschitz continuous first partial derivatives. Pacific J. Math.,
16(1):1–3, 1966.
[37] F. Bach and E. Moulines. Non-strongly-convex smooth stochastic approximation with convergence rate
O(1/n). In NIPS, pages 773–781, 2013.
[38] F. Shang, Y. Liu, J. Cheng, K. Ng, and Y. Yoshida. Guaranteed sufficient decrease for variance reduced
stochastic gradient descent. arXiv: 1703.06807v2, 2017.
[39] R. Frostig, R. Ge, S. M. Kakade, and A. Sidford. Un-regularizing: approximate proximal point and faster
stochastic algorithms for empirical risk minimization. In ICML, pages 2540–2548, 2015.
[40] Z. Allen-Zhu and E. Hazan. Optimal black-box reductions between optimization objectives. In NIPS, pages
1606–1614, 2016.
[41] Y. Nesterov. Smooth minimization of non-smooth functions. Math. Program., 103:127–152, 2005.
[42] Jakub Koneeny, Jie Liu, Peter Richtarik, , and Martin Takae. Mini-batch semi-stochastic gradient descent
in the proximal setting. IEEE J. Sel. Top. Sign. Proces., 10(2):242–255, 2016.

Guaranteed Sufficient Decrease for Stochastic Variance Reduced Gradient Optimization

[43] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
[44] F. Shang, K. Zhou, J. Cheng, I. W. Tsang, L. Zhang, and D. Tao. VR-SGD: A simple stochastic variance
reduction method for machine learning. arXiv:1704.04966v2, 2017.
[45] O. Shamir. Without-replacement sampling for stochastic gradient methods. In NIPS, pages 46–54, 2016.
[46] S. Reddi, A. Hefny, S. Sra, B. Poczos, and A. Smola. On variance reduction in stochastic gradient descent
and its asynchronous variants. In NIPS, pages 2629–2637, 2015.
[47] H. Mania, X. Pan, D. Papailiopoulos, B. Recht, K. Ramchandran, and M. I. Jordan. Perturbed iterate
analysis for asynchronous stochastic optimization. SIAM J. Optim., 27(4):2202–2229, 2017.
[48] F. Pedregosa, R. Leblond, and S. Lacoste-Julien. Breaking the nonsmooth barrier: A scalable parallel
method for composite optimization. In NIPS, pages 55–64, 2017.
[49] J. D. Lee, Q. Lin, T. Ma, and T. Yang. Distributed stochastic variance reduced gradient methods by
sampling extra data with replacement. J. Mach. Learn. Res., 18:1–43, 2017.
[50] Z. Allen-Zhu and Y. Yuan. Improved SVRG for non-strongly-convex or sum-of-non-convex objectives. arXiv:
1506.01972v3, 2016.
[51] L. Baldassarre and M. Pontil. Advanced topics in machine learning part II: 5. Proximal methods. University
Lecture, 2013.
[52] G. Lan. An optimal method for stochastic composite optimization. Math. Program., 133:365–397, 2012.

Fanhua Shang,

Yuanyuan Liu,

Kaiwen Zhou,

James Cheng,

Kelvin K.W. Ng

−2

10

−6

10

−8

10

10

−4

10

−8

10

−10

−12

10

20
30
Gradient evaluations / n

10

40

−8

10
10

−12

0

−6

10

−10

10

−10

10
10

−6

SAGA
Prox−SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

10

F (xs ) − F (x* )

−4

10

SAGA
Prox−SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−4

F (xs ) − F (x* )

10

F (xs ) − F (x* )

10

SAGA
Prox−SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

−12

0

10

20
30
Gradient evaluations / n

10

40

0

10

20
30
Gradient evaluations / n

40

−2

10

−6

10

−8

10

10

−4

10

−8

10

−10

−12

0.1

0.2
0.3
Running time (sec)

10

0.4

−8

10
10

−12

0

−6

10

−10

10

−10

10
10

−6

SAGA
Prox−SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

10

F (xs ) − F (x* )

−4

10

SAGA
Prox−SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−4

F (xs ) − F (x* )

10

F (xs ) − F (x* )

10

SAGA
Prox−SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

−12

0

(a) Ijcnn1, λ2 = 10−4

5
10
Running time (sec)

10

15

0

(b) Covtype, λ2 = 10−4

10

20
30
Running time (sec)

40

50

(c) SUSY, λ2 = 10−4

−2

−4

10

−6

10

−8

10

−6

10

−4

10

−8

10

10

20
30
Gradient evaluations / n

10

40

−8

10
10

−12

0

−6

10

−10

10

−12

SAGA
Prox−SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

10

−10

−10

10
10

SAGA
Prox−SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

F (xs ) − F (x* )

10

F (xs ) − F (x* )

−4

F (xs ) − F (x* )

10

SAGA
Prox−SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

10

−12

0

10

20
30
Gradient evaluations / n

40

10

50

0

10

20
30
Gradient evaluations / n

40

−2

−6

10

−8

10

10

−6

10

−4

10

−8

10

0.1

0.2
0.3
Running time (sec)

(d) Ijcnn1, λ2 = 10−5

0.4

10

−8

10
10

−12

0

−6

10

−10

10

−12

SAGA
Prox−SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

10

−10

−10

10
10

SAGA
Prox−SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−4

F (xs ) − F (x* )

F (xs ) − F (x* )

−4

10

10

F (xs ) − F (x* )

SAGA
Prox−SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

10

−12

0

5
10
Running time (sec)

(e) Covtype, λ2 = 10−5

15

10

0

10

20
30
Running time (sec)

40

50

(f) SUSY, λ2 = 10−5

Figure 9: Comparison of all the stochastic variance reduced gradient methods for solving non-strongly convex
Lasso problems on the three data sets. The vertical axis is the objective value minus the minimum, and the
horizontal axis denotes the number of effective passes over the data (top) or the running time (seconds, bottom).

Guaranteed Sufficient Decrease for Stochastic Variance Reduced Gradient Optimization

−2

10

−6

10

−8

10

10

−4

10

−8

10

−6

10

−8

10

−10

−10

−10

10

10

−12

10

−6

10

−12

0

10

20
30
Gradient evaluations / n

10

40

SAGA
Prox−SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

10

F (xs ) − F (x* )

−4

10

SAGA
Prox−SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−4

F (xs ) − F (x* )

10

F (xs ) − F (x* )

10

SAGA
Prox−SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

−12

0

10

20
30
Gradient evaluations / n

10

40

0

10

20
30
Gradient evaluations / n

40

−2

−8

10

10

−4

10

−6

10

−8

10

−8

10

−10

−10

−10

10

10

−12

10

−6

*

F (xs ) − F (x* )

−6

10

10

10

−12

0

0.1

0.2
0.3
0.4
Running time (sec)

0.5

10

0.6

SAGA
Prox−SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

10

s

−4

10

SAGA
Prox−SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−4

F (x ) − F (x )

10

10

F (xs ) − F (x* )

SAGA
Prox−SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

−12

0

5
10
Running time (sec)

10

15

0

10

20
30
40
Running time (sec)

50

60

(a) λ1 = 10−5 and λ2 = 10−5
−2

10

−6

10

−8

10

10

−4

10

−8

10

−6

10

−8

10

−10

−10

−10

10

10

−12

10

−6

10

−12

0

10

20
30
Gradient evaluations / n

40

10

50

SAGA
Prox−SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

10

F (xs ) − F (x* )

10

SAGA
Prox−SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−4

F (xs ) − F (x* )

−4

F (xs ) − F (x* )

10

SAGA
Prox−SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

10

−12

0

10

20
30
Gradient evaluations / n

10

40

0

10

20
30
Gradient evaluations / n

40

−2

−6

10

−8

10

−6

10

−4

10
*

−8

10

−10

−10

−12

0.1

0.2
0.3
0.4
Running time (sec)

0.5

0.6

10

−8

10
10

−12

0

−6

10

−10

10

10
10

10

SAGA
Prox−SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

10

s

F (xs ) − F (x* )

−4

10

SAGA
Prox−SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−4

F (x ) − F (x )

10

10

F (xs ) − F (x* )

SAGA
Prox−SVRG
Catalyst
Katyusha
SAGA−SD
SVRG−SD

−2

−12

0

5
10
Running time (sec)

15

10

0

10

20
30
40
Running time (sec)

50

60

(b) λ1 = 10−5 and λ2 = 10−6

Figure 10: Comparison of all the stochastic methods for solving elastic-net (i.e., (λ1 /2)k·k2 +λ2 k·k1 ) problems
on Ijcnn1 (the first column), Covtype (the second column), and SUSY (the last column). The vertical axis is
the objective value minus the minimum, and the horizontal axis denotes the number of effective passes over the
data (top) or the running time (seconds, bottom).

