Variants of RMSProp and Adagrad with Logarithmic Regret Bounds

Mahesh Chandra Mukkamala 1 2 Matthias Hein 1

arXiv:1706.05507v2 [cs.LG] 28 Nov 2017

Abstract
Adaptive gradient methods have become recently
very popular, in particular as they have been
shown to be useful in the training of deep neural networks. In this paper we have analyzed
RMSProp, originally proposed for the training
of deep neural networks, in the context
of on√
line convex optimization and show T -type regret bounds. Moreover, we propose two variants SC-Adagrad and SC-RMSProp for which
we show logarithmic regret bounds for strongly
convex functions. Finally, we demonstrate in the
experiments that these new variants outperform
other adaptive gradient techniques or stochastic
gradient descent in the optimization of strongly
convex functions as well as in training of deep
neural networks.

1. Introduction
There has recently been a lot of work on adaptive gradient
algorithms such as Adagrad (Duchi et al., 2011), RMSProp
(Hinton et al., 2012), ADADELTA (Zeiler, 2012), and
Adam (Kingma & Bai, 2015). The original idea of Adagrad to have a parameter specific learning rate by analyzing the gradients observed during the optimization turned
out to be useful not only in online convex optimization
but also for training deep neural networks. The original
analysis of Adagrad (Duchi et al., 2011) was limited to the
case of all convex functions for which
√ it obtained a datadependent regret bound of order O( T ) which is known
to be optimal (Hazan, 2016) for this class. However, a lot
of learning problems have more structure in the sense that
one optimizes over the restricted class of strongly convex
functions. It has been shown in (Hazan et al., 2007) that
one can achieve much better logarithmic regret bounds for
the class of strongly convex functions.

The goal of this paper is twofold. First, we propose SCAdagrad which is a variant of Adagrad adapted to the
strongly convex case. We show that SC-Adagrad achieves
a logarithmic regret bound for the case of strongly convex
functions, which is data-dependent. It is known that such
bounds can be much better in practice than data independent bounds (Hazan et al., 2007),(McMahan, 2014). Second, we analyze RMSProp which has become one of the
standard methods to train neural networks beyond stochastic gradient descent. We show that under some conditions on the weighting scheme√of RMSProp, this algorithm
achieves a data-dependent O( T ) regret bound. In fact, it
turns out that RMSProp contains Adagrad as a special case
for a particular choice of the weighting scheme. Up to our
knowledge this is the first theoretical result justifying the
usage of RMSProp in online convex optimization and thus
can at least be seen as theoretical support for its usage in
deep learning. Similarly, we then propose the variant SCRMSProp for which we also show a data-dependent logarithmic regret bound similar to SC-Adagrad for the class of
strongly convex functions. Interestingly, SC-Adagrad has
been discussed in (Ruder, 2016), where it is said that “it
does not to work”. The reason for this is that SC-Adagrad
comes along with a damping factor which prevents potentially large steps in the beginning of the iterations. However, as our analysis shows this damping factor has to be
rather large initially to prevent large steps and should be
then monotonically decreasing as a function of the iterations in order to stay adaptive. Finally, we show in experiments on three datasets that the new methods are competitive or outperform other adaptive gradient techniques as
well as stochastic gradient descent for strongly convex optimization problem in terms of regret and training objective
but also perform very well in the training of deep neural
networks, where we show results for different networks and
datasets.

2. Problem Statement

1

Department of Mathematics and Computer Science, Saarland
University, Germany 2 IMPRS-CS, Max Planck Institute for Informatics, Saarbrücken, Germany . Correspondence to: Mahesh
Chandra Mukkamala <mmahesh.chandra873@gmail.com>.
Proceedings of the 34 th International Conference on Machine
Learning, Sydney, Australia, PMLR 70, 2017. Copyright 2017
by the author(s).

We first need some technical statements and notation and
then introduce the online convex optimization problem.

Variants of RMSProp and Adagrad with Logarithmic Regret Bounds

2.1. Notation and Technical Statements
We denote by [T ] the set {1, . . . , T }. Let A ∈ Rd×d be a
symmetric, positive definite matrix. We denote as
hx, yiA = hx, Ayi =

d
X

kxkA

Aij xi yj ,

=

q
hx, xiA

i,j=1

Note that P
the standard Euclidean inner product becomes
hx, yi =
i xi yi = hx, yiI While we use here the general notation for matrices for comparison to the literature.
All positive definite matrices A in this paper will be diagonal matrices, so that the computational effort for computing
inner products and norms is still linear in d. The CauchySchwarz inequality becomes, hx, yiA ≤ kxkA kykA . We
further introduce the element-wise product a b of two vectors. Let a, b ∈ Rd , then (a b)i = ai bi for i = 1, . . . , d.
Let A ∈ Rd×d be a symmetric, positive definite matrix,
z ∈ Rd and C ⊂ Rd a convex set. Then we define the
weighted projection PCA (z) of z onto the set C as
2

PCA (z) = arg min kx − zkA .

hx, Axi ≤ λmax (A) hx, xi ≤ tr(A) hx, xi

2.2. Problem Statement
In this paper we analyze the online convex optimization
setting, that is we have a convex set C and at each round we
get access to a (sub)-gradient of some continuous convex
function ft : C → R. At the t-th iterate we predict θt ∈ C
and suffer a loss ft (θt ). The goal is to perform well with
respect to the optimal decision in hindsight defined as
∗

θ = arg min
θ∈C

Lemma 2.1 Let A ∈ Rd×d be a symmetric, positive definite matrix and C ⊂ Rd be a convex set. Then
A

ft (θ).

t=1

T
X

(ft (θt ) − ft (θ∗ )).

t=1

We assume that the adversarial can choose from the class
of convex functions on C, for some parts we will specialize
this to the set of strongly convex functions.
Definition 2.1 Let C be a convex set. We say that a function f : C → R is µ-strongly convex, if there exists µ ∈ Rd
with µi > 0 for i = 1, . . . , d such that for all x, y ∈ C,

≤ kz − ykA .

Proof:
The first order optimality condition for the
weighted projection in (1) is given as
A(x − z) ∈ NC (x),

2

f (y) ≥ f (x) + h∇f (x), y − xi + ky − xkdiag(µ)
= f (x) + h∇f (x), y − xi +

where NC (x) denotes the normal cone of C at x. This can
be rewritten as
hz − x, y − xiA ≤ 0

T
X

The adversarial regret at time T ∈ N is then given as
R(T ) =

It is well-known that the weighted projection is unique and
non-expansive.

(2)

where λmax (A) is the maximum eigenvalue of matrix A
and tr(A) denotes the trace of matrix A .

(1)

x∈C

PCA (z) − PCA (y)

Lemma 2.2 For any symmetric, positive semi-definite matrix A ∈ Rd×d we have

∀y ∈ C.

d
X

µi (yi − xi )2 .

i=1

Let ζ = mini=1,...,d µi , then this function is ζ-strongly convex (in the usual sense), that is
2

f (y) ≥ f (x) + h∇f (x), y − xi + ζ kx − yk .

This yields
z − PCA (z), PCA (y) − PCA (z)
y−

PCA (y), PCA (z)

−

A
PCA (y) A

≤ 0,

Note that the difference between our notion of componentwise strong convexity and the usual definition of strong
convexity is indicated by the bold font versus normal font.
We have two assumptions:

≤ 0.

Adding these two inequalities yields
z − PCA (z) − y + PCA (y), PCA (y) − PCA (z)
=⇒

PCA (y)

−

2
PCA (z) A

≤ z−

y, PCA (y)

A

≤0

−

PCA (z) A

.

The result follows from the application of the weighted
Cauchy-Schwarz inequality.


• A1: It holds supt≥1 kgt k2 ≤ G which implies the
existence of a constant G∞ such that supt≥1 kgt k∞ ≤
G∞ .
• A2: It holds supt≥1 kθt − θ∗ k2 ≤ D which implies the existence of a constant D∞ such that
supt≥1 kθt − θ∗ k∞ ≤ D∞ .

Variants of RMSProp and Adagrad with Logarithmic Regret Bounds

α
1
=√ q P
T
1
2
T
t=1 gt,i +
T

Algorithm 1 Adagrad
Input: θ1 ∈ C , δ > 0, v0 = 0 ∈ Rd
for t = 1 to T do
gt ∈ ∂ft (θt )
vt = vt−1 + (gt gt )
√
At = diag( vt ) + δI

θt+1 = PCAt θt − αA−1
t gt
end for
One of the first
√ methods which achieves the optimal regret
bound of O( T ) for convex problems is online projected
gradient descent (Zinkevich, 2003), defined as
θt+1 = PC (θt − αt gt )

(3)

where αt = √αt is the step-size scheme and gt is a (sub)gradient of ft at θt . With αt = αt , online projected gradient descent method achieves the optimal O(log(T )) regret
bound for strongly-convex problems (Hazan et al., 2007).
We consider Adagrad in the next subsection which is one of
the popular adaptive alternative to online projected gradient
descent.
2.3. Adagrad for convex problems
In this section we briefly recall the main result for the Adagrad. The algorithm for Adagrad is given in Algorithm 1. If
the adversarial is allowed to choose from the set of all possible convex functions on C √
⊂ Rd , then Adagrad achieves
the regret bound of order O( T ) as shown in (Duchi et al.,
2011). This regret bound is known to be optimal for this
class, see e.g. (Hazan, 2016). For better comparison to
our results for RMSProp, we recall the result from (Duchi
et al., 2011) in our notation. For this purpose, we introduce
the notation, g1:T,i = (g1,i , g2,i , .., gT,i )T , where gt,i is the
i-th component of the gradient gt ∈ Rd of the function ft
evaluated at θt .
Theorem 2.1 (Duchi et al., 2011) Let Assumptions A1, A2
hold and let θt be the sequence generated by Adagrad in
Algorithm 1, where gt ∈ ∂ft (θt ) and ft : C → R is an
arbitrary convex function, then for stepsize α > 0 the regret
is upper bounded as
R(T ) ≤

d
d
2 X
X
D∞
kg1:T,i k2 + α
kg1:T,i k2 .
2α i=1
i=1

The effective step-length of Adagrad is on the order of √αt .
PT
2
This can be seen as follows; first note that vT,i = t=1 gt,i
1
−1
and thus (At ) is a diagonal matrix with entries √vt,i +δ .
Then one has
α
α(A−1
T )ii = qP
T
2
t=1 gt,i + δ

(4)
√δ
T

Thus an alternative point of view of Adagrad, is that it has a
decaying stepsize √αt but now the correction term becomes
the running average of the squared derivatives plus a vanishing damping term. However, the effective stepsize has
to decay faster to get a logarithmic regret bound for the
strongly convex case. This is what we analyze in the next
section, where we propose SC-Adagrad for strongly convex
functions.

3. Strongly convex Adagrad (SC-Adagrad)
The modification SC-Adagrad of Adagrad which we propose in the following can be motivated by the observation
that the online projected gradient descent (Hazan et al.,
2007) uses stepsizes of order α = O( T1 ) in order to achieve
the logarithmic regret bound for strongly convex functions.
In analogy with the
in the previous section, we
Pderivation
T
2
still have vT,i = t=1 gt,i
. But now we modify (At )−1
and set it as a diagonal matrix with entries vt,i1+δt . Then
one has
α(A−1
T )ii = PT

α

2
t=1 gt,i

+ δt

=

α
T

1
1
T

PT

2
t=1 gt,i

+

δT
T

.
(5)

Again, we have in the denominator a running average of
the observed gradients and a decaying damping factor. In
this way, we get an effective stepsize of order O( T1 ) in SCAdagrad. The formal method is presented in Algorithm
2. As just derived the only difference of Adagrad and SCAdagrad is the definition of the diagonal matrix At . Note
Algorithm 2 SC-Adagrad
Input: θ1 ∈ C , δ0 > 0, v0 = 0 ∈ Rd
for t = 1 to T do
gt ∈ ∂ft (θt )
vt = vt−1 + (gt gt )
Choose 0 < δt ≤ δt−1 element wise
At = diag(vt ) + diag(δt ) 
θt+1 = PCAt θt − αA−1
t gt
end for
also that we have defined the damping factor δt as a function of t which is also different from standard Adagrad.
The constant δ in Adagrad is mainly introduced due to numerical reasons in order to avoid problems when gt,i is
very small for some components in the first iterations and
is typically chosen quite small e.g. δ = 10−8 . For SCAdagrad the situation is different. If the first components
g1,i , g2,i , . . . are very small, say of order , then the update

is 2 +δ
which can become extremely large if δt is chosen
t

Variants of RMSProp and Adagrad with Logarithmic Regret Bounds

to be small. This would make the method very unstable
and would lead to huge constants in the bounds. This is
probably why in (Ruder, 2016), the modification of Adagrad where one “drops the square-root” did not work. A
good choice of δt should be initially
on the order
PTroughly
2
of 1 and it should decay as vt,i = t=1 gt,i
starts to grow.
This is why we propose to use
δt,i = ξ2 e−ξ1 vt,i ,

i = 1, . . . , d,

for ξ1 > 0, ξ2 > 0 as a potential decay scheme as it satisfies both properties for sufficiently large ξ1 and ξ2 chosen
on the order of 1. Also, one can achieve a constant decay scheme for ξ1 = 0 , ξ2 > 0. We will come back to
this choice after the proof. In the following we provide the
regret analysis of SC-Adagrad and show that the optimal
logarithmic regret bound can be achieved. However, as it is
data-dependent it is typically significantly better in practice
than data-independent bounds.
Note: There was initial work in (Duchi et al., 2010) where
SC-Adagrad using a constant decay scheme was already
proposed and also shown to have O(log T ) regret bounds
for strongly convex problems. Unfortunately, we were unaware of this work when we created SC-Adagrad, as it
wasn’t mentioned in journal version (Duchi et al., 2011).
Recently, there was a related work done for constant decay scheme in (Gupta et al., 2017) which gives a unified
analysis of all the adaptive algorithms and some of the results regarding logarithmic regret bounds (see for Section
4 in (Gupta et al., 2017)) closely match to that of SCAdagrad (Algorithm 2). Our new contribution is that the
decay scheme is vectorized so one need not restrict to a
constant scheme. We only require a mild condition, that
it is non-increasing element-wise in order to achieve logarithmic regret bounds.
3.1. Analysis
For any two matrices A, B ∈ Rd×d , we use
P the
P notation
• to denote the inner product i.e A • B = i j Aij Bij .
Note that A • B = tr(AT B).
Lemma 3.1 [Lemma 12 (Hazan et al., 2007)] Let A, B be
positive definite matrices, let A  B  0 then
 |A| 
(6)
A−1 • (A − B) ≤ log
|B|
where |A| denotes the determinant of the matrix A
Lemma 3.2 Let Assumptions A1, A2 hold, then for T ≥
1 and At , δt as defined in the SC-Adagrad algorithm we
have,
!
T
d
X
X
kg1:T,i k2 + δT,i
−1
gt , At gt ≤
log
δ1,i
t=1
i=1

−

d X
T
X
δt,i − δt−1,i
kg1:t,i k2 + δt,i
i=1 t=2

Proof: Consider the following summation,
T
X

gt , A−1
t gt ≤

t=1

=
+

T
X

T
A−1
t • diag(gt gt )

t=1

A−1
1
T
X

• (A1 − diag(δ1 ))

A−1
t • (At − At−1 − diag(δt ) + diag(δt−1 ))

t=2



≤ log

−

T
X

T
 |A | 
|A1 |  X
t
+
log
|diag(δ1 )|
|A
|
t−1
t=2

A−1
t • (diag(δt ) − diag(δt−1 ))

t=2
T
|AT |  X −1
−
At • (diag(δt ) − diag(δt−1 ))
|diag(δ1 )|
t=2
!
d
X
kg1:T,i k2 + δT,i
≤
log
δ1,i
i=1



= log

−

T
X

A−1
t • (diag(δt ) − diag(δt−1 ))

t=2

≤

d
X

log

i=1

kg1:T,i k2 + δT,i
δ1,i

!

d X
T
X
δt,i − δt−1,i
−
2
kg
1:t,i k + δt,i
i=1 t=2

In the first step we use hx, Axi = A • diag(xxT ) where
A is a diagonal matrix and subsequently we use ∀t > 1 ,
diag(gt gtT ) = At − At−1 − diag(δt ) + diag(δt−1 ), and
for t = 1 we have diag(g1 g1T ) = A1 − diag(δ1 ). In the
first inequality we use Lemma 3.1 also see for Lemma 12
of (Hazan et al., 2007). Note that for T = 1, the upper
bound results in 0.


Theorem 3.1 Let Assumptions A1, A2 hold and let θt be
the sequence generated by the SC-Adagrad in Algorithm
2, where gt ∈ ∂ft (θt ) and ft : C → R is an arbitrary
µ-strongly convex function (µ ∈ Rd+ ) where the stepsize
G2

fulfills α ≥ maxi=1,...,d 2µ∞i . Furthermore, let δt > 0 and
δt,i ≤ δt−1,i ∀t ∈ [T ], ∀i ∈ [d], then the regret of SCAdagrad can be upper bounded for T ≥ 1 as
d

R(T ) ≤
d

+

 kg

2
2
D∞
tr(diag(δ1 )) α X
1:T,i k + δT,i
+
log
2α
2 i=1
δ1,i

 (θ − θ∗ )2

1X
α
t,i
i
inf
−
(δT,i − δ1,i )
2 i=1 t∈[T ]
α
kg1:t,i k2 + δt,i

Variants of RMSProp and Adagrad with Logarithmic Regret Bounds

For constant δt i.e δt,i = δ > 0 ∀t ∈ [T ] and ∀i ∈ [d] then
the regret of SC-Adagrad is upper bounded as
R(T ) ≤

2
D∞
dδ
α
+
2α
2

d
X

log


2
1:T,i k + δ
δ

 kg

i=1

For ζ-strongly convex function choosing α ≥
tain the above mentioned regret bounds.

G2∞
2ζ

(7)

we ob-

Proof: We rewrite the regret bound with the definition of
µ-strongly convex functions as
R(T ) =

T
X

(ft (θt ) − ft (θ∗ ))

t=1

≤

T
X

hgt , θt − θ∗ i −

t=1

T
X

In the last step we use the equality ∀x ∈ Rn kxk2A −
kxk2B = kxk2A−B where A, B ∈ Rn x n and both are
diagonal matrices. Now, we choose α such that At −
At−1 − 2α diag(µ) 4 diag(δt ) − diag(δt−1 ) ∀t ≥ 2
and A1 − 2α diag(µ) 4 diag(δ1 ) Since At − At−1 4
G2∞ I + diag(δt ) − diag(δt−1 ) and A1 4 G2∞ I + diag(δ1 )
because at any round the difference between subsequent
squares of sub-gradients is bounded by G2∞ . Also by
Algorithm 2, δt,i ≤ δt−1,i ∀t > 1, ∀i ∈ [d] hence
diag(δt ) − diag(δt−1 )  0. Hence by choosing α ≥
G2
maxi=1,...,d 2µ∞i we have At − At−1 − 2α diag(µ) 4
diag(δt ) − diag(δt−1 ) ∀t ≥ 2 and A1 − 2αdiag(µ) 4
diag(δ1 ) which yields

2

kθt − θ∗ kdiag(µ)

R(T )

t=1

Using the non-expansiveness we have

≤

kθ1 − θ∗ k2diag(δ1 )
2α

+

PCAt

=

θt −

T

αA−1
t gt

≤ θt −

αA−1
t gt

≤ kθt −

θ∗ k2At

−



− θ∗

2

+

At

2
θ∗ A
t
∗

− 2α hgt , θt − θ i + α

gt , At−1 gt

2

This yields

=

+

hgt , θt − θ∗ i
kθt − θ∗ k2At − kθt+1 − θ∗ k2At
α
+
gt , A−1
≤
t gt
2α
2
Hence we can upper bound the regret as follows

≤

+

R(T )
T
X
kθt − θ∗ k2At − kθt+1 − θ∗ k2At
≤
2α
t=1

+

2

gt , A−1
t gt −

T
X

≤

kθ1 −
≤
2α

2

kθt − θ∗ kdiag(µ)

+

T 
X

kθt − θ∗ k2At − kθt − θ∗ k2At−1 

t=2

α
2

T
X

T
X

kθ1 − θ∗ k2A1 −2αdiag(µ)

t=2

2α

d
T X
X
(θt,i − θ∗ )2 (δt,i − δt−1,i )
i

t=2 i=1

2α

gt , A−1
t gt

t=1

2
D∞

T

tr(diag(δ1 )) α X
+
gt , A−1
t gt
2α
2 t=1

T X
d
X
(θt,i − θ∗ )2 (δt,i − δt−1,i )
i

2α

d
2
tr(diag(δ1 )) α X  kg1:T,i k2 + δT,i 
D∞
log
+
2α
2 i=1
δ1,i
d

(θt,i − θi∗ )2 (δt,i − δt−1,i ) α(δt,i − δt−1,i )
−
α
kg1:t,i k2 + δt,i

≤

d
2
D∞
tr(diag(δ1 )) α X  kg1:T,i k2 + δT,i 
+
log
2α
2 i=1
δ1,i

+

 (θ − θ∗ )2

1X
α
t,i
i
inf
−
(δT,i − δ1,i )
2 i=1 t∈[T ]
α
kg1:t,i k2 + δt,i

In the second inequality we bounded kθ1 − θ∗ k2diag(δ1 ) ≤
2
D∞
tr(diag(δ1 )). In the second last step we use the
Lemma 3.2. So under a constant δt i.e δt,i = δ > 0, ∀t ∈
[T ], ∀i ∈ [d] we have tr(diag(δ1 )) = dδ hence proving the
result (7). For ζ-strongly convex functions choosing α ≥

2

kθt − θ∗ kdiag(µ)

2α
T
X
kθt − θ∗ k2At −At−1 −2α diag(µ)

+

d

t=1

+

2α

1 XX
+
2 t=2 i=1

2α

T
kθT +1 − θ∗ k2AT
αX
+
gt , A−1
−
t gt
2α
2 t=1

≤

kθ1 − θ∗ k2diag(δ1 )

T

t=1

t=1

θ∗ k2A1

−

αX
gt , A−1
t gt
2 t=1

t=2 i=1

T
αX

2α

t=2

2

kθt+1 − θ∗ kAt

T
X
kθt − θ∗ kdiag(δt )−diag(δt−1 )

T

+

αX
gt , A−1
t gt
2 t=1

G2∞,i
2ζ

we obtain the the same results as µ-strongly convex
functions. This can be seen by setting µi = ζ, ∀i ∈ [d]. 

!

Variants of RMSProp and Adagrad with Logarithmic Regret Bounds

Note that the first and the last term in the regret bound
can be upper bounded by constants. Only the second term
2
depends on T . Note that kg1:T,i k ≤ T G2 and as δt is
monotonically decreasing, the second term is on the order
of O(log(T )) and thus we have a logarithmic regret bound.
As the bound is data-dependent, in the sense that it depends
on the observed sequence of gradients, it is much tighter
than a data-independent bound.
The bound includes also the case of a non-decaying damping factor δt = δ = ξ2 (ξ1 = 0). While a rather large
constant damping factor can work well, we have noticed
that the best results are obtained with the decay scheme
δt,i = ξ2 e−ξ1 vt,i ,

i = 1, . . . , d.

where ξ1 > 0 , ξ2 > 0 , which is what we use in the experiments. Note that this decay scheme for ξ1 , ξ2 > 0 is
adaptive to the specific dimension and thus increases the
adaptivity of the overall algorithm. For completeness we
also give the bound specialized for this decay scheme.
Corollary 3.1 In the setting of Theorem 3.1 choose δt,i =
ξ2 e−ξ1 vt,i for i = 1, . . . , d for some ξ1 > 0, ξ2 > 0 . Then
the regret of SC-Adagrad can be upper bounded for T ≥ 1
as

an interesting question for future work, if there exists an
optimal decay scheme which provably works better than
any constant one.

4. RMSProp and SC-RMSProp
RMSProp is one of the most popular adaptive gradient
algorithms used for the training of deep neural networks
(Schaul et al., 2014; Dauphin et al., 2015; Daniel et al.,
2016; Schmidhuber, 2015). It has been used frequently in
computer vision (Karpathy & Fei-Fei, 2016) e.g. to train
the latest InceptionV4 network (Szegedy et al., 2016a;b).
Note that RMSProp outperformed other adaptive methods
like Adagrad order Adadelta as well as SGD with momentum in a large number of tests in (Schaul et al., 2014). It
has been argued that if the changes in the parameter update
are approximately Gaussian distributed, then the matrix At
can be seen as a preconditioner which approximates the diagonal of the Hessian (Daniel et al., 2016). However, it is
fair to say that despite its huge empirical success in practice and some first analysis in the literature, there is so far
no rigorous theoretical analysis of RMSProp. We will analyze RMSProp given in Algorithm 3 in the framework of
of online convex optimization.
Algorithm 3 RMSProp

2
2
α
dD∞
ξ2
− log(ξ2 e−ξ1 G∞ )
2α
2
d


2
αX
log kg1:T,i k2 + ξ2 e−ξ1 kg1:T ,i k
+
2 i=1

R(T ) ≤

d


X
2
αξ1 ξ2

+
1 − e−ξ1 kg1:T ,i k
2 log(ξ2 ξ1 ) + 1 i=1
2

Proof: Note that δT,i = ξ2 e−ξ1 vT ,i = ξ2 e−ξ1 kg1:T ,i k .
Plugging this into Theorem 3.1 for ξ1 , ξ2 > 0 yields the
results for the first three terms. Using (θt,i − θi∗ )2 ≥ 0 we
have
 (θ − θ∗ )2

α
t,i
i
inf
−
α
kg1:t,i k2 + δt,i
t∈[T ]
−α
≥
inf j∈[1:T ] kg1:j,i k2 + δj,i
2

Note that kg1:j,i k + δj,i = vj,i + ξ2 e−ξ1 vj,i , in order to
find the minimum of this term we thus analyze the function f : R+ → R, f (x) = x + ξ2 e−ξ1 x . and a straightforward calculation shows that the minimum is attained at
x∗ = ξ11 log(ξ1 ξ2 ) and f (x∗ ) = ξ11 (log(ξ1 ξ2 ) + 1). This
yields the fourth term.

Unfortunately, it is not obvious that the regret bound for our
decaying damping factor is better than the one of a constant
damping factor. Note, however that the third term in the regret bound of Theorem 3.1 can be negative. It thus remains

Input: θ1 ∈ C , δ > 0, α > 0, v0 = 0 ∈ Rd
for t = 1 to T do
gt ∈ ∂ft (θt )
vt = βt vt−1 + (1 − βt )(gt gt )
Set t = √δt and αt = √αt
√
At = diag( vt ) + t I

θt+1 = PCAt θt − αt A−1
t gt
end for
First, we will show that RMSProp reduces to Adagrad for
a certain choice of its parameters. Second, we will
√ prove
for the general convex case a regret bound of O( T ) similar to the bound given in Theorem 2.1. It turns out that
the convergence analysis requires that in the update of the
weighted cumulative squared gradients (vt ) , it has to hold
1−

1
γ
≤ βt ≤ 1 − ,
t
t

for some 0 < γ ≤ 1. This is in contrast to the original
suggestion of (Hinton et al., 2012) to choose βt = 0.9.
It will turn out later in the experiments that the constant
choice of βt leads sometimes to divergence of the sequence,
whereas the choice derived from our theoretical analysis
always leads to a convergent scheme even when applied to
deep neural networks. Thus we think that the analysis in
the following is not only interesting for the convex case but
can give valuable hints how the parameters of RMSProp
should be chosen in deep learning.

Variants of RMSProp and Adagrad with Logarithmic Regret Bounds

Before we start the regret analysis we want to discuss the
sequence vt in more detail. Using the recursive definition
of vt , we get the closed form expression
vt,i =

t
X

(1 − βj )

j=1

t
Y

s

√
T −1
(T − 1)(1 − βT ) 2
vT,i −
gT,i + T T
βT
βT

s

√
T −1
(T − 1)(1 − βT ) 2
T vT,i −
gT,i + T T
T βT
βT

≤

=
2
βk gj,i
.

s

k=j+1

≤
Pt
Qt
2
With βt = 1− 1t one gets, vt,i = j=1 1j k=j+1 k−1
k gj,i ,
and
the telescoping product ones gets
Qt using
j
k−1
k=j+1 k = t and thus
Pt
2
.
vt,i = 1t j=1 gj,i
If one uses additionally the stepsize scheme αt =

α
√
t

and

√δ
T

, then we recover the update scheme of Adagrad,
t =
see (4), as a particular case of RMSProp. We are not aware
of that this correspondence of Adagrad and RMSProp has
been observed before.
The proof of the regret bound for RMSProp relies on the
following lemma.
Lemma 4.1 Let Assumptions A1 and A2 and suppose that
1 − 1t ≤ βt ≤ 1 − γt for some 0 < γ ≤ 1, and t ≥ 1. Also
p
√
for t > 1 suppose (t − 1)t−1 ≤ tt , then

T vT,i −

Note that in the last step we have used that TT −1
βT ≤ 1 and
√
√
√
the fact that x is concave and thus x − c ≤ x − 2√c x
given that x − c ≥ 0, along with √ −1 ≤ √ −1 √
T vT ,i

t=1


√
2(2 − γ) p
√
T vT,i + T T .
≤
√
γ
t vt,i + tt
2
gt,i

Proof: The lemma is proven via induction. For T = 1 we
2
have v0 = 0 and thus v1,i = (1 − β1 )g1,i
and thus
2
2
g1,i
(1 − β1 )gt,i
q

=
√
( v1,i + 1 )
2 +
(1 − β1 )
(1 − β1 )g1,i
1
q
2 +
√
(1 − β1 )g1,i
1
( v1,i + 1 )
≤
≤
.
1 − β1
γ

Note that γ1 ≤ 2(2−γ)
since 2(2 − γ) > 1 for γ ≤ 1 hence
γ
the bound holds for T = 1. For T > 1 we suppose that the
bound is true for T − 1 and get
T
−1
X

√

2
gt,i

√

t vt,i + tt
q

p
2(2 − γ) 
≤
(T − 1) vT −1,i + (T − 1)T −1 .
γ

t=1

2
We rewrite vT,i = βT vT −1,i + (1 − βT )gT,i
as vT −1,i =
p
√
1−βT 2
1
(t − 1)t−1 ≤ tt we get
βT vT,i − βT gT,i and with

q

(T − 1)vT −1,i +

p

(T − 1)T −1

T vT ,i + T t

for vt,i 6= 0 we have
q

(T − 1)vT −1,i +

≤

p

√
T vT,i +

p
(T − 1)T −1

T T −

(T − 1)(1 − βT )
2
√
(8)
 gT,i
p
2βT
T vT,i + T T

Using the above bound we have the following
T
X

√

t=1
T
X

√
(T − 1)(1 − βT ) 2
gT,i + T T
βT

2
gt,i

t vt,i +

T
−1
X

√

tt

2
gT,i
√
+p
t vt,i + tt
T vT,i + T T
t=1
q

p
2(2 − γ) 
≤
(T − 1) vT −1,i + (T − 1)T −1
γ
2
gT,i
√
+p
T vT,i + T t

√
2(2 − γ) p
≤
T vT,i + T T
γ
2

gT,i
2(2 − γ) (T − 1)(1 − βT ) 
√
+ 1−
p
γ
2βT
T vT,i + T T

=

√

2
gt,i

√

In
 the last step we use (8)
 and since for T > 1 the term
2(2−γ) (T −1)(1−βT )
1− γ
≤ 0 for 1 − 1t ≤ βt ≤ 1 − γt 
2βT

Corollary 4.1 Let Assumptions A1, A2 hold and suppose
that 1 − 1t ≤ βt ≤ 1 − γt for some 0 < γ ≤ 1, and
p
√
t ≥ 1. Also for t > 1 suppose (t − 1)t−1 ≤ tt , and
set αt = √αt , then
T
X
αt
t=1

2

d

gt , A−1
t gt ≤


√
α(2 − γ) X p
T vT,i + T T
γ
i=1

√
Proof: Using the definition of At = diag( vt ) + t I,

Variants of RMSProp and Adagrad with Logarithmic Regret Bounds

αt =

α
√
t

T
X
αt
t=1

2

along with Lemma 4.1 we get
gt , A−1
t gt =

T
d
X
αt X
t=1

2

√

i=1

≤

2
gt,i
vt,i + t

+

T 
kθt − θ∗ k2At−1 
kθ1 − θ∗ k2A1 X
kθt − θ∗ k2At
+
−
2α1
2αt
2αt−1
t=2

−

T
X
kθT +1 − θ∗ k2AT
αt
+
gt , A−1
t gt
2αt
2
t=1


With the help of Lemma 4.1 and Corollary 4.1 we can now
state the regret bound for RMSProp.

≤
+

Theorem 4.1 Let Assumptions A1, A2 hold and let θt be
the sequence generated by RMSProp in Algorithm 3, where
gt ∈ ∂ft (θt ) and ft : C → R is an arbitrary convex function and αt = √αt for some α > 0 and 1− 1t ≤ βt ≤ 1− γt
p
for
√ some 0 < γ ≤ 1. Also for t > 1 let (t − 1)t−1 ≤
tt , then the regret of RMSProp can be upper bounded
for T ≥ 1 as
d

∞

+

2α


√
α(2 − γ)  X p
T vT,i + T T
γ
i=1

Proof: Note that for every convex function ft : C → R it
holds for all x, y ∈ C and gt ∈ ∂ft (x),
ft (y) ≥ ft (x) + hgt , y − xi .

gt , A−1
t gt

2

≤

d


√
α X 2(2 − γ) p
T vT,i + T T
≤
2 i=1
γ

 D2

T
X
αt
t=1

T
d
2
gt,i
α XX
√
=
√
2 t=1 i=1 t vt,i + tt

R(T ) ≤

T
X
kθt − θ∗ k2At − kθt+1 − θ∗ k2At
2αt
t=1

kθ1 − θ∗ k2A1
2α
T kθ − θ ∗ k2
√
X
t
tA

√

t−

t−1At−1

2α

t=2

tAt −

√

T
X
αt
t=1

In the last step we used αt =
√

+

α
√
.
t

2

gt , A−1
t gt

We show that

t − 1At−1  0 ∀t ∈ [T ]

(9)

Note that At are diagonal matrices for all t ≥ 1. We note
that
√
(At )ii = vt,i + t ,
2
and vt,i = βt vt−1,i + (1 − βt )gt,i
as well as βt ≥ 1 −
which implies tβt ≥ t − 1. We get
√
√
p
t(At )ii = tvt,i + tt
q
√
2 +
tt
= tβt vt−1,i + t(1 − βt )gt,i
q
√
≥ (t − 1)vt−1,i + t − 1t−1 ,

We use this to upper bound the regret as
R(T ) =

T
X

(ft (θt ) − ft (θ∗ )) ≤

t=1

T
X

hgt , θt − θ∗ i

where
we used in the last inequality that
√
t − 1t−1 . Note that

t=1

T
X

Using the non-expansiveness of the weighted projection,
we have
2

kθt+1 − θ∗ kAt

∗
≤ θt − αt A−1
t gt − θ

≤ kθt −

θ∗ k2At

tt

≥

kθt − θ∗ k2√tAt −√t−1At−1

t=2

=


∗
= PCAt θt − αt A−1
t gt − θ

√

1
t

2

T X
d
X

(θt,i − θi∗ )2

t=2 i=1

p

At

2
At
∗

− 2αt hgt , θt − θ i +

αt2

gt , A−1
t gt

≤

tvt,i +

d
X

√

tt −

q

(t − 1)vt−1,i +

√

t − 1t−1



2
D∞

i=1

This yields

T 
X
p

hgt , θt − θ∗ i
kθt − θ∗ k2At − kθt+1 − θ∗ k2At
αt
gt , A−1
≤
+
t gt
2αt
2

tvt,i +

√

tt −

q

(t − 1)vt−1,i −

√

t − 1t−1



t=2

=

d
X

2
D∞

p

√
T vT,i +

T T −

√

v1,i − 1



i=1

Hence we can upper bound the regret as follows
R(T )

where the inequality could be done as we showed before
that the difference of the terms in vt,i is non-negative for

Variants of RMSProp and Adagrad with Logarithmic Regret Bounds

Lemma 4.2 Let αt = αt , 1 − 1t ≤ βt ≤ 1 − γt and At as
defined in SC-RMSProp, then it holds for all T ≥ 1,

Algorithm 4 SC-RMSProp
Input: θ1 ∈ C , δ0 = 1 , v0 = 0 ∈ Rd
for t = 1 to T do
gt ∈ ∂ft (θt )
vt = βt vt−1 + (1 − βt )(gt gt )
Set t = δtt where δt,i ≤ δt−1,i for i ∈ [d] and αt =
At = diag(vt + t )

θt+1 = PCAt θt − αt A−1
t gt
end for
all i ∈ [d] and t ≥ 1. As (A1 )ii =

√

T
X
αt
α
t

2

t=1

gt , A−1
t gt

d
T v +  
α X
T,i
T,i
log
≤
2γ i=1
1,i

+

T
d
α X X −tt,i + (t − 1)t−1,i
2γ t=2 i=1
tvt,i + tt,i

+

d
α X (1 − γ)(1 + log T )
2γ i=1 inf j∈[1,T ] jvj,i + jj,i

v1,i + 1 we get

2
Proof: Using hx, Axi = A • diag(xxT ) and with gt,i
=
vt,i −βt vt−1 ,i
and using that At is diagonal with (At )ii =
1−βt
vt,i + t,i , we get

d
2 X

kθ1 − θ∗ k2A1
D∞
√
≤
v1,i + 1 .
2α
2α i=1

Thus in total we have
R(T ) ≤

2
D∞

p

Pd

i=1

T vT,i +

√

T T

T
X
α



t=1

2α
+

T
X
αt

2

t=1

α
((A1 )−1 • (A1 − diag(1 )))
2(1 − β1 )
T
 A − diag( ) 
X
α
t
t
+
(tAt )−1 •
2
(1
−
β
)
t
t=2
=

gt , A−1
t gt .

Finally, with Corollary 4.1 we get the result.

((tAt )−1 • diag(gt gtT ))

2



Note that for βt = 1 − 1t , that is γ = 1, and t = Tδ where
RMSProp corresponds to Adagrad we recover the regret
bound of Adagrad in the convex case, see Theorem 2.1, up
to the damping factor. Note that in this case
v
u T
uX
p
2 = kg
T vT,i = t
gj,i
1:T,i k2 .
j=1

−

t=2

α
δt
αt = , t = ,
t
t
Pt
1
2
for which again it follows vt,i = t j=1 gj,i with the same
argument as for RMSProp. Please see Equation (5) for the
correspondence. Moreover, with the same argument as for
SC-Adagrad we use a decay scheme for the damping factor
1
βt = 1 − ,
t

t,i = ξ2

e−ξ1 t vt,i
,
t

i = 1, . . . , d. for ξ1 ≥ 0 , ξ2 > 0

The analysis of SC-RMSProp is along the lines of SCAdagrad with some overhead due to the structure of vt .

β A

t t−1 − βt diag(t−1 )
(1 − βt )

α
((A1 )−1 • (A1 − diag(1 )))
2γ
T
 tA − tβ A 
X
α
t
t t−1
(tAt )−1 •
+
2
γ
t=2
T
X
α
t=2

Similar to the extension of Adagrad to SC-Adagrad, we
present in this section SC-RMSProp which achieves a logarithmic regret bound.
Note that again there exist choices for the parameters of
SC-RMSProp such that it reduces to SC-Adagrad. The correspondence is given by the choice

2

(tAt )−1 •

≤

+

4.1. SC-RMSProp

T
X
α

≤

+

+

 −diag( ) + β diag( ) 
t
t
t−1
(1 − βt )

T
 |A | 
 |tA | 
α X
α
1
t
log
+
log
2γ
|diag(1 )|
2γ t=2
|tβt At−1 |
T
X
α
t=2

≤

2

(tAt )−1 •

2

(tAt )−1 •

 −diag( ) + β diag( ) 
t
t
t−1
(1 − βt )

T
 |A | 


α
α X
|tAt |
1
log
+
log
2γ
|diag(1 )|
2γ t=2
|(t − 1)At−1 |
T
X
α
t=2

2

(tAt )−1 •

 −diag( ) + β diag( ) 
t
t
t−1
(1 − βt )

1
In the first inequality we use 1−β
≤ γt . In the last step we
t
1
use, that ∀t > 1, tβ1t ≤ t−1
. Finally, by upper bounding
the last term with Lemma 4.3
T
X
αt
t=1

2

gt , A−1
t gt ≤

 |T A | 
α
T
log
2γ
|diag(1 )|

Variants of RMSProp and Adagrad with Logarithmic Regret Bounds
T
d
α X X −tt,i + (t − 1)t−1,i
2γ t=2 i=1
tvt,i + tt,i

+

≤

d
α X (1 − γ)(1 + log T )
+
2γ i=1 inf j∈[1,T ] jvj,i + jj,i

T
d
α X X −tt,i + (t − 1)t−1,i
2γ t=2 i=1
tvt,i + tt,i
d
1−γ
α X
(1 + log T )
+
2γ i=1 inf j∈[2,T ] jvj,i + jj,i

We note that



log(|T AT |) = log

d
Y

(T (vT,i + T,i ))



i=1

=

d
X

Theorem 4.2 Let Assumptions A1, A2 hold and let θt be
the sequence generated by SC-RMSProp in Algorithm 4,
where gt ∈ ∂ft (θt ) and ft : C → R is an arbitrary µstrongly convex function (µ ∈ Rd+ ) with αt = αt for some

log(T (vT,i + T,i )),

i=1

and similar, log(|diag(1 )|) =

Pd

i=1

log(1,i ).

Note that for γ = 1 and the choice t =
the result of Lemma 3.2.
Lemma 4.3 Let t ≤ 1t and 1 −
1 ≥ γ > 0. Then it holds,
T
X
α
t=2

≤

2

(tAt )−1 •

1
t

δt
t



this reduces to

≤ βt ≤ 1 −

γ
t

for some

 −diag( ) + β diag( ) 
t
t
t−1
(1 − βt )

d
T
α X X −tt,i + (t − 1)t−1,i
2γ t=2 i=1
tvt,i + tt,i

+

d
α X (1 − γ)(1 + log T )
2γ i=1 inf j∈[1,T ] jvj,i + jj,i

Proof: Using

γ
t

(2−γ)G2

α ≥ 2 mini µ∞i and 1 − 1t ≤ βt ≤ 1 − γt for some 0 <
γ ≤ 1. Furthermore, set t = δtt and assume 1 ≥ δt,i > 0
and δt,i ≤ δt−1,i ∀t ∈ [T ], ∀i ∈ [d], then the regret of SCRMSProp can be upper bounded for T ≥ 1 as

≤ 1 − βt ≤ 1t , we get

R(T ) ≤
d

+

 (θ − θ∗ )2

1X
α
t,i
i
inf
−
(δT,i − δ1,i )
2 i=1 t∈[T ]
α
γ(tvt,i + tt,i )

+

d
α X (1 − γ)(1 + log T )
2γ i=1 inf j∈[1,T ] jvj,i + jj,i

Proof: We rewrite the regret bound with the definition of
µ-strongly convex functions as

T
X
α
t=2

≤

2

t=2

≤

α
2γ

t=2 i=1

−tt,i + (t − 1)t−1,i + (tβt − (t − 1))t−1,i
tvt,i + tt,i

T
d
α X X −tt,i + (t − 1)t−1,i
2γ t=2 i=1
tvt,i + tt,i

+

≤

T X
d
X

T
d
α X X (1 − γ)t−1,i
2γ t=2 i=1 tvt,i + tt,i

α
2γ
+

T X
d
X
t=2 i=1

−tt,i + (t − 1)t−1,i
tvt,i + tt,i

d
T
X
α X
1−γ
1
2γ i=1 inf j∈[2,T ] jvj,i + jj,i t=2 t

T
X

(ft (θt ) − ft (θ∗ ))

t=1

≤

 −tdiag( ) + tβ diag( ) 
t
t
t−1
(tAt )−1 •
γ

T
d
α X X −tt,i + tβt t−1,i
=
2γ t=2 i=1
tvt,i + tt,i

=

R(T ) =

 −diag( ) + β diag( ) 
t
t
t−1
(tAt )−1 •
2
(1 − βt )

T
α X

d
Tv + δ 
2
α X
D∞
tr(diag(δ1 ))
T,i
T,i
+
log
2α
2γ i=1
δ1,i

T
X

hgt , θt − θ∗ i −

T
X

2

kθt − θ∗ kdiag(µ)

t=1

t=1

Using the non-expansiveness of the weighted projection,
we get
2

kθt+1 − θ∗ kAt

∗
= PCAt θt − αt A−1
t gt − θ
≤ θt −

αt A−1
t gt

−

2
At

2
θ∗ At

≤ kθt − θ∗ k2At − 2αt hgt , θt − θ∗ i + αt2 gt , A−1
t gt
This yields
hgt , θt − θ∗ i
≤

kθt − θ∗ k2At − kθt+1 − θ∗ k2At
αt
+
gt , A−1
t gt
2αt
2

Hence we can upper bound the regret as follows
R(T )

Variants of RMSProp and Adagrad with Logarithmic Regret Bounds
T
X
kθt − θ∗ k2At − kθt+1 − θ∗ k2At
2αt
t=1

≤

T
X
αt

+

t=1

2

gt , A−1
t gt

−

T
X

kθt −

The second inequality (11) holds easily with the given
choice of α. Choosing some βt = 1 − γt
2
tvt,i = tβt,i vt−1,i + t(1 − βt )gt,i

2
θ∗ kdiag(µ)

2
≥ (t − 1)vt−1,i + t(1 − βt )gt,i
≥ (t − 1)vt−1,i

t=1

≤

T 
kθt − θ∗ k2At−1 
kθt − θ∗ k2At
kθ1 − θ∗ k2A1 X
+
−
2α1
2αt
2αt−1
t=2

−

T
X
kθT +1 − θ∗ k2AT
αt
+
gt , A−1
t gt
2αt
2
t=1

−

T
X

Hence δt,i ≤ δt−1,i where δt,i = e− t vt,i for  > 0. With
δ
t,i = t,i
t we have tt ≤ (t − 1)t−1 .
R(T )
≤

kθ1 − θ∗ k2diag(δ1 )
2α

2

kθt − θ∗ kdiag(µ)

t=1
T
X

kθt −
kθ1 − θ∗ k2A1
+
≤
2α1
t=2
+

T
X
αt
t=1

2

gt , A−1
t gt −

T
X

+

θ∗ k2tAt −(t−1)At−1
=

2α

2

+

Now on imposing the following condition

A1 − 2αdiag(µ)  diag(δ1 )

≤

(11)

≤

− (t − 1)t−1,i

2
≤ (1 − γ)vt−1,i + gt,i
− 2αµi + tt,i − (t − 1)t−1,i

≤ (1 − γ)G2∞ + G2∞ − 2αµi + tt,i − (t − 1)t−1,i
= (2 − γ)G2∞ − 2αµi + tt,i − (t − 1)t−1,i
≤ tt,i − (t − 1)t−1,i ,
where the last inequality follows by choosing α ≥
G2∞
2minµi (2 − γ) and we have used that
i

t
t
X
Y
2
(1 − βj )
βk gj,i

≤

k=j+1

βk −

k=j

t


Y
≤ G2∞ 1 −
βk ≤ G2∞
k=1

2α

d

+

≤

(θt,i − θi∗ )2 (δt,i − δt−1,i ) α(δt,i − δt−1,i )
−
α
γ(tvt,i + tt,i )

d
α X (1 − γ)(1 + log T )
2γ i=1 inf j∈[1,T ] jvj,i + jj,i

d
Tv + δ 
2
α X
D∞
tr(diag(δ1 ))
T,i
T,i
log
+
2α
2γ i=1
δ1,i
d

+

 (θ − θ∗ )2

1X
α
t,i
i
inf
−
(δT,i − δ1,i )
2 i=1 t∈[T ]
α
γ(tvt,i + tt,i )

+

d
α X (1 − γ)(1 + log T )
2γ i=1 inf j∈[1,T ] jvj,i + jj,i

where we have used Lemma 4.2 in the last inequality and
δ
t,i = t,i

t for i ∈ [d] and t ≥ 1.

k=j+1

j=1

i

d
Tv + δ 
2
tr(diag(δ1 ))
D∞
α X
T,i
T,i
+
log
2α
2γ i=1
δ1,i

+ tt,i − (t − 1)t−1,i

t
Y

2α

T X
d
X
(θt,i − θ∗ )2 (δt,i − δt−1,i )

T

2
= (tβt,i − (t − 1))vt−1,i + t(1 − βt )gt,i
− 2αµi

t
Y

i

gt , A−1
t gt

2

1 XX
+
2 t=2 i=1

− (t − 1)vt−1,i − 2αµi

G2∞

T X
d
X
(θt,i − θ∗ )2 (δt,i − δt−1,i )
t=2 i=1

t=2 i=1

tvt,i + tt,i − (t − 1)vt−1,i − (t − 1)t−1,i − 2αµi

t 
X

+

2
tr(diag(δ1 )) X αt
D∞
+
gt , A−1
t gt
2α
2
t=1

+

δ

Note that with t,i = t,i
t and δt,i ≤ δt−1,i for all t ≥ 1 and
i ∈ [d], it holds tt,i ≤ (t − 1)t−1,i . We show regarding
the inequality in (10)

j=1

2α

T

(10)

 diag(δt ) − diag(δt−1 ) ∀t ≥ 2

= tβt,i vt−1,i + tt,i + t(1 −

T
X
αt
t=1

tAt − (t − 1)At−1 − 2α diag(µ)

2
βt )gt,i

t=2

kθ1 − θ∗ k2diag(δ1 )

kθt − θ∗ kdiag(µ)

T
X
kθt − θ∗ kdiag(δt )−diag(δt−1 )

gt , A−1
t gt

2

t=1

2α

t=1

vt,i =

T
X
αt

+

βk



Note that the regret bound reduces for γ = 1 to that of SCAdagrad. For 0 < γ < 1 a comparison between the bounds
is not straightforward as the vt,i terms cannot be compared.
It is an interesting future research question whether it is
possible to show that one scheme is better than the other
one potentially dependent on the problem characteristics.

!

100

10−1

1

50

100
Epoch

150

SGD
Adam
Adagrad
RMSProp
RMSProp (Ours)
SC-RMSProp
SC-Adagrad

100

10−1

200

1

50

(a) CIFAR10

100
Epoch

150

Relative Sub-optimality (log scale)

SGD
Adam
Adagrad
RMSProp
RMSProp (Ours)
SC-RMSProp
SC-Adagrad

Relative Sub-optimality (log scale)

Relative Sub-optimality (log scale)

Variants of RMSProp and Adagrad with Logarithmic Regret Bounds

SGD
Adam
Adagrad
RMSProp
RMSProp (Ours)
SC-RMSProp
SC-Adagrad

100

10−1

10−2

200

1

50

(b) CIFAR100

100
Epoch

150

200

(c) MNIST

Figure 1. Relative Suboptimality vs Number of Epoch for L2-Regularized Softmax Regression

104

SGD
Adam
Adagrad
RMSProp
RMSProp (Ours)
SC-RMSProp
SC-Adagrad

5

10

Regret (log scale)

SGD
Adam
Adagrad
RMSProp
RMSProp (Ours)
SC-RMSProp
SC-Adagrad

Regret (log scale)

Regret (log scale)

105

104
0.1

0.2

0.3

0.4
0.5
0.6
0.7
Dataset proportion

(a) CIFAR10

0.8

0.9

1.0

SGD
Adam
Adagrad
RMSProp
RMSProp (Ours)
SC-RMSProp
SC-Adagrad

104

103
0.1

0.2

0.3

0.4
0.5
0.6
0.7
Dataset proportion

(b) CIFAR100

0.8

0.9

1.0

0.1

0.2

0.3

0.4
0.5
0.6
0.7
Dataset proportion

0.8

0.9

1.0

(c) MNIST

Figure 2. Regret (log scale) vs Dataset Proportion for Online L2-Regularized Softmax Regression

5. Experiments
The idea of the experiments is to show that the proposed
algorithms are useful for standard learning problems in
both online and batch settings. We are aware of the fact
that in the strongly convex case online to batch conversion is not tight (Hazan & Kale, 2014), however that does
not necessarily imply that the algorithms behave generally suboptimal. We compare all algorithms for a strongly
convex
 problem
and present relative suboptimality plots,
f (xt )−p∗
, where p∗ is the global optimum, as well
log10
p∗
as separate regret plots, where we compare to the best optimal parameter in hindsight for the fraction of training
points seen so far. On the other hand RMSProp was originally developed by (Hinton et al., 2012) for usage in deep
learning. As discussed before the fixed choice
√ of βt is
not allowed if one wants to get the optimal O( T ) regret
bound in the convex case. Thus we think it is of interest to
the deep learning community, if the insights from the convex optimization case transfer to deep learning. Moreover,
Adagrad and RMSProp are heavily used in deep learning
and thus it is interesting to compare their counterparts SCAdagrad and SC-RMSProp developed for the strongly convex case also in deep learning. For the deep learning experiments we optimize the learning rate once for smallest

training objective as well as for best test performance after
a fixed number of epochs (typically 200 epochs).
Datasets: We use three datasets where it is easy, difficult and very difficult to achieve good test performance,
just in order to see if this influences the performance. For
this purpose we use MNIST (60000 training samples, 10
classes), CIFAR10 (50000 training samples, 10 classes)
and CIFAR100 (50000 training samples, 100 classes). We
refer to (Krizhevsky, 2009) for more details on the CIFAR
datasets.
Algorithms: We compare 1) Stochastic Gradient Descent
(SGD) (Bottou, 2010) with O(1/t) decaying step-size for
the strongly convex problems and for non-convex problems
we use a constant learning rate, 2) Adam (Kingma & Bai,
2015) , is used with step size decay of αt = √αt for strongly
convex problems and for non-convex problems we use a
constant step-size. 3) Adagrad, see Algorithm 1, remains
the same for strongly convex problems and non-convex
problems. 4) RMSProp as proposed in (Hinton et al., 2012)
is used for both strongly convex problems and non-convex
problems with βt = 0.9 ∀t ≥ 1. 5) RMSProp (Ours) is
used with step-size decay of αt = √αt and βt = 1 − γt .
In order that the parameter range is similar to the original

Variants of RMSProp and Adagrad with Logarithmic Regret Bounds
0.40
0.994

0.72
0.38

0.992
0.36

0.66

SGD
Adam
Adagrad
RMSProp
RMSProp (Ours)
SC-RMSProp
SC-Adagrad

0.64
0.62
0.60

1

50

100
Epoch

150

0.34
0.32

SGD
Adam
Adagrad
RMSProp
RMSProp (Ours)
SC-RMSProp
SC-Adagrad

0.30
0.28
0.26

200

1

50

(a) CIFAR10

100
Epoch

150

0.990

Test Accuracy

0.68

Test Accuracy

Test Accuracy

0.70

0.988
SGD
Adam
Adagrad
RMSProp
RMSProp (Ours)
SC-RMSProp
SC-Adagrad

0.986
0.984
0.982
0.980

200

1

50

(b) CIFAR100

100
Epoch

150

200

(c) MNIST

Figure 3. Test Accuracy vs Number of Epochs for 4-layer CNN
0.6

0.86

Training Objective

0.5

0.4

0.3

0.84
0.82
Test Accuracy

SGD
Adam
Adagrad
RMSProp
RMSProp (Ours)
SC-RMSProp
SC-Adagrad

0.80
0.78
SGD
Adam
Adagrad
RMSProp
RMSProp (Ours)
SC-RMSProp
SC-Adagrad

0.76
0.74

0.2
0.72
0.1

1

100

200
Epoch

300

400

(a) Training Objective

0.70

1

100

200
Epoch

300

400

(b) Test Accuracy

Figure 4. Plots of ResNet-18 on CIFAR10 dataset

RMSProp ((Hinton et al., 2012)) we fix as γ = 0.9 for all
experiment (note that for γ = 1 RMSProp (Ours) is equivalent to Adagrad), 6) SC-RMSProp is used with stepsize
αt = αt and γ = 0.9 as RMSProp (Ours) 7) SC-Adagrad
is used with a constant stepsize α. The decaying damping factor for both SC-Adagrad and SC-RMSProp is used
with ξ1 = 0.1, ξ2 = 1 for convex problems and we use
ξ1 = 0.1, ξ2 = 0.1 for non-convex deep learning problems. Finally, the numerical stability parameter δ used in
Adagrad, Adam, RMSProp is set to 10−8 as it is typically
recommended for these algorithms.
Setup: Note that all methods have only one varying parameter: the stepsize α which we choose from the set of
{1, 0.1, 0.01, 0.001, 0.0001} for all experiments. By this
setup no method has an advantage just because it has more
hyperparameters over which it can optimize. The optimal
rate is always chosen for each algorithm separately so that
one achieves either best training objective or best test performance after a fixed number of epochs.
Strongly Convex Case - Softmax Regression: Given the
training data (xi , yi )i∈[m] and let yi ∈ [K]. we fit a linear model with cross entropy loss and use as regularization
the squared Euclidean norm of the weight parameters. The

objective is then given as
m

T

1 X
eθyi xi +byi
J(θ) = −
log PK θT x +b
m i=1
ej i j
j=1

!
+λ

K
X

kθk k2

k=1

All methods are initialized with zero weights. The regularization parameter was chosen so that one achieves the
best prediction performance on the test set. The results are
shown in Figure 1. We also conduct experiments in an online setting, where we restrict the number of iterations to
the number of training samples. Here for all the algorithms,
we choose the stepsize resulting in best regret value at the
end. We plot the Regret ( in log scale ) vs dataset proportion seen, and as expected SC-Adagrad and SC-RMSProp
outperform all the other methods across all the considered
datasets. Also, RMSProp (Ours) has a lower regret values
than the original RMSProp as shown in Figure 2.
Convolutional Neural Networks: Here we test a 4-layer
CNN with two convolutional (32 filters of size 3 × 3) and
one fully connected layer (128 hidden units followed by 0.5
dropout). The activation function is ReLU and after the last
convolutional layer we use max-pooling over a 2 × 2 window and 0.25 dropout. The final layer is a softmax layer
and the final objective is cross-entropy loss. This is a pretty

Variants of RMSProp and Adagrad with Logarithmic Regret Bounds
0.19
0.41

0.18

0.926

0.17

0.40

SGD
Adam
Adagrad
RMSProp
RMSProp (Ours)
SC-RMSProp
SC-Adagrad

0.37
0.36
0.35

1

50

100
Epoch

150

0.16
0.15
0.14

SGD
Adam
Adagrad
RMSProp
RMSProp (Ours)
SC-RMSProp
SC-Adagrad

0.13
0.12
0.11
0.10

200

1

(a) CIFAR10

50

100
Epoch

150

Test Accuracy

0.38

Test Accuracy

Test Accuracy

0.924
0.39

0.922
SGD
Adam
Adagrad
RMSProp
RMSProp (Ours)
SC-RMSProp
SC-Adagrad

0.920

0.918

0.916

200

1

(b) CIFAR100

50

100
Epoch

150

200

(c) MNIST

Figure 5. Test Accuracy vs Number of Epochs for L2-Regularized Softmax Regression

1.50
1.25
1.00
0.75
0.50

3.5
3.0
2.5
2.0
1.5

0.14
SGD
Adam
Adagrad
RMSProp
RMSProp (Ours)
SC-RMSProp
SC-Adagrad

0.12

Training Objective

Training Objective

1.75

SGD
Adam
Adagrad
RMSProp
RMSProp (Ours)
SC-RMSProp
SC-Adagrad

4.0

Training Objective

SGD
Adam
Adagrad
RMSProp
RMSProp (Ours)
SC-RMSProp
SC-Adagrad

2.00

0.10
0.08
0.06
0.04
0.02

0.25
1

50

100
Epoch

(a) CIFAR10

150

200

1.0

1

50

100
Epoch

150

200

0.00

1

(b) CIFAR100

50

100
Epoch

150

200

(c) MNIST

Figure 6. Training Objective vs Number of Epoch for 4-layer CNN

simple standard architecture and we use it for all datasets.
The results are shown in Figures 3, 6. SC-RMSProp is
competitive in terms of training objective on all datasets
though SGD achieves the best performance. SC-Adagrad is
not very competitive and the reason seems to be that the numerical stability parameter is too small. RMSProp diverges
on CIFAR10 dataset whereas RMSProp (Ours) converges
on all datasets and has similar performance as Adagrad in
terms of training objective. Both RMSProp (Ours) and SCAdagrad perform better than all the other methods in terms
of test accuracy for CIFAR10 dataset. On both CIFAR100
and MNIST datasets SC-RMSProp is very competitive.
Multi-Layer Perceptron: We also conduct experiments
for a 3-layer Multi-Layer perceptron with 2 fully connected
hidden layers and a softmax layer according to the number
of classes in each dataset. For the first two hidden layers we
have 512 units in each layer with ReLU activation function
and 0.2 dropout. The final layer is a softmax layer. We
report the results in Figures 7, 8. On all the datasets, SCAdagrad and SC-RMSProp perform better in terms of Test
accuracy and also have the best training objective performance on CIFAR10 dataset. On MNIST dataset, Adagrad
and RMSProp(Ours) achieves best training objective performance however SC-Adagrad and SC-RMSProp eventu-

ally performs as good as Adagrad. Here, the performance is
not as competitive as Adagrad, because the numerical stability decay parameter of SC-Adagrad and SC-RMSProp
are too prohibitive.
Residual Network: We also conduct experiments for
ResNet-18 network proposed in (He et al., 2016a) where
the residual blocks are used with modifications proposed
in (He et al., 2016b) on CIFAR10 dataset. We report the
results in Figures 4. SC-Adagrad, SC-RMSProp and RMSProp (Ours) have the best performance in terms of test
Accuracy and RMSProp (Ours) has the best performance
in terms of training objective along with Adagrad.
Given these experiments, we think that SC-Adagrad, SCRMSProp and RMSProp (Ours) are valuable new adaptive
gradient techniques for deep learning.

6. Conclusion
We have analyzed RMSProp originally proposed in the
deep learning community in the framework of online convex optimization. We show that the conditions for convergence of RMSProp for the convex case are different than
what is used by (Hinton et al., 2012) and that this leads
to better performance in practice. We also propose vari-

Variants of RMSProp and Adagrad with Logarithmic Regret Bounds
4.0

Training Objective

1.6
1.4
1.2
1.0
0.8

0.05
SGD
Adam
Adagrad
RMSProp
RMSProp (Ours)
SC-RMSProp
SC-Adagrad

3.5
Training Objective

SGD
Adam
Adagrad
RMSProp
RMSProp (Ours)
SC-RMSProp
SC-Adagrad

1.8

0.6

3.0

2.5

2.0

SGD
Adam
Adagrad
RMSProp
RMSProp (Ours)
SC-RMSProp
SC-Adagrad

0.04
Training Objective

2.0

0.03

0.02

0.01

1.5

0.4
1

50

100
Epoch

150

1.0

200

1

(a) CIFAR10

50

100
Epoch

150

0.00

200

1

(b) CIFAR100

50

100
Epoch

150

200

(c) MNIST

Figure 7. Training Objective vs Number of Epoch for 3-layer MLP
0.58

0.988
0.30
0.986
0.28

0.52

0.26

0.50
0.48

SGD
Adam
Adagrad
RMSProp
RMSProp (Ours)
SC-RMSProp
SC-Adagrad

0.46
0.44
0.42
0.40

1

50

100
Epoch

(a) CIFAR10

150

200

0.984

0.24
SGD
Adam
Adagrad
RMSProp
RMSProp (Ours)
SC-RMSProp
SC-Adagrad

0.22
0.20
0.18
0.16
1

50

100
Epoch

150

200

Test Accuracy

0.54
Test Accuracy

Test Accuracy

0.56

0.982
SGD
Adam
Adagrad
RMSProp
RMSProp (Ours)
SC-RMSProp
SC-Adagrad

0.980
0.978
0.976
1

(b) CIFAR100

50

100
Epoch

150

200

(c) MNIST

Figure 8. Test Accuracy vs Number of Epochs for 3-layer MLP

ants SC-Adagrad and SC-RMSProp which achieve logarithmic regret bounds for the strongly convex case. Moreover, they perform very well for different network models
and datasets and thus they are an interesting alternative to
existing adaptive gradient schemes. In the future we want
to explore why these algorithms perform so well in deep
learning tasks even though they have been designed for the
strongly convex case.

Acknowledgements
We would like to thank Shweta Mahajan and all the reviewers for their insightful comments.

References
Bottou, L. Large-scale machine learning with stochastic
gradient descent. In Proceedings of COMPSTAT’2010,
pp. 177–186. Springer, 2010.
Daniel, C., Taylor, J., and Nowozin, S. Learning step size
controllers for robust neural network training. In AAAI,
2016.
Dauphin, Y., de Vries, H., and Bengio, Y. Equilibrated
adaptive learning rates for non-convex optimization. In
NIPS, 2015.

Duchi, J., Hazan, E., and Singer, Y. Adaptive subgradient
methods for online learning and stochastic optimization.
Journal of Machine Learning Research, 12:2121–2159,
2011.
Duchi, John, Hazan, Elad, and Singer, Yoram. Adaptive
subgradient methods for online learning and stochastic
optimization. COLT 2010, pp. 257, 2010.
Gupta, Vineet, Koren, Tomer, and Singer, Yoram. A
unified approach to adaptive regularization in online and stochastic optimization.
arXiv preprint
arXiv:1706.06569, 2017.
Hazan, E. Introduction to online convex optimization.
Foundations and Trends in Optimization, 2:157–325,
2016.
Hazan, E. and Kale, S. Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex
optimization. Journal of Machine Learning Research,
15(1):2489–2512, 2014.
Hazan, E., Agarwal, A., and Kale, S. Logarithmic regret algorithms for online convex optimization. Machine
Learning, 69(2-3):169–192, 2007.
He, Kaiming, Zhang, Xiangyu, Ren, Shaoqing, and Sun,
Jian. Deep residual learning for image recognition. In

Variants of RMSProp and Adagrad with Logarithmic Regret Bounds

Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 770–778, 2016a.
He, Kaiming, Zhang, Xiangyu, Ren, Shaoqing, and Sun,
Jian. Identity mappings in deep residual networks. In
European Conference on Computer Vision, pp. 630–645.
Springer, 2016b.
Hinton, G., Srivastava, N., and Swersky, K. Lecture 6d
- a separate, adaptive learning rate for each connection.
Slides of Lecture Neural Networks for Machine Learning, 2012.
Karpathy, A. and Fei-Fei, L. Deep visual-semantic alignments for generating image descriptions. In CVPR,
2016.
Kingma, D. P. and Bai, J. L. Adam: a method for stochastic
optimization. ICLR, 2015.
Krizhevsky, A. Learning multiple layers of features from
tiny images. Technical report, University of Toronto,
2009.
McMahan, H Brendan. A survey of algorithms and
analysis for adaptive online learning. arXiv preprint
arXiv:1403.3465, 2014.
Ruder, S. An overview of gradient descent optimization
algorithms. preprint, arXiv:1609.04747v1, 2016.
Schaul, T., Antonoglou, I., and Silver, D. Unit tests for
stochastic optimization. In ICLR, 2014.
Schmidhuber, J. Deep learning in neural networks: An
overview. Neural Networks, 61:85 – 117, 2015.
Szegedy, C., Ioffe, S., and Vanhoucke, V. Inception-v4,
inception-resnet and the impact of residual connections
on learning. In ICLR Workshop, 2016a.
Szegedy, C., Vanhoucke, V., Ioffe, S., Shlens, J., and Wojna, Z. Rethinking the inception architecture for computer vision. In CVPR, 2016b.
Zeiler, M. D. ADADELTA: An adaptive learning rate
method. preprint, arXiv:1212.5701v1, 2012.
Zinkevich, M. Online convex programming and generalized infinitesimal gradient ascent. In ICML, 2003.

