Adaptive Subgradient Methods forOnline Learning and Stochastic Optimization

John Duchi∗
University of California, Berkeley

Elad Hazan
IBM Almaden Research Center

Yoram Singer
Google Researchjduchi@cs.berkeley.edu

ehazan@cs.princeton.edu

singer@google.com

Abstract
We present a new family of subgradient methods that dynamically incorporate knowledge of thegeometry of the data observed in earlier iterations to perform more informative gradient-basedlearning. The adaptation, in essence, allows us to find needles in haystacks in the form of very
predictive yet rarely observed features. Our paradigm stems from recent advances in online learningwhich employ proximal functions to control the gradient steps of the algorithm. We describe andanalyze an apparatus for adaptively modifying the proximal function, which significantly simplifies
the task of setting a learning rate and results in regret guarantees that are provably as good as thebest proximal function that can be chosen in hindsight. We corroborate our theoretical results withexperiments on a text classification task, showing substantial improvements for classification withsparse datasets.

1

Introduction

In many applications of online and stochastic learning, the input instances are of very high dimension, yet
within any particular instance only a few features are non-zero. It is often the case, however, that the infrequently occurring features are highly informative and discriminative. The informativeness of rare features
has led practitioners to craft domain-specific feature weightings, such as TF-IDF (Salton and Buckley, 1988),
which pre-emphasize infrequently occurring features. We use this old idea as a motivation for applying modern learning-theoretic techniques to the problem of online and stochastic learning, focusing specifically on(sub)gradient methods.
Standard stochastic subgradient methods largely follow a predetermined procedural scheme that is oblivious to the characteristics of the data being observed. In contrast, our algorithms dynamically incorporate
knowledge of the geometry of the data from earlier iterations to perform more informative gradient-basedlearning. Informally, our procedures associate frequently occurring features with low learning rates and infrequent features high learning rates. This construction prompts the learner to “take notice” each time an
infrequent feature is observed. Thus, the adaptation facilitates identification and adaptation of highly predictive but comparatively rare features.
1.1

The Adaptive Gradient Algorithm

For simplicity, consider the basic online convex optimization setting. The algorithm iteratively makes aprediction xt ∈ X , where X ⊆ Rd is a closed convex set, and then receives a convex loss function ft . Define
the regret with respect to the (optimal) predictor x∗ ∈ X asR(T ) ,TX
t=1

[ft (xt ) − ft (x∗ )] .

To achieve low regret, standard subgradient algorithms move the predictor xt in the opposite direction of
the subgradient gt ∈ ∂ft (xt ) of the loss via the projected gradient update (e.g. Zinkevich, 2003)
xt+1 = ΠX (xt − ηgt ) .
∗Eligible for best student paper award

Our algorithm, called A DAG RAD, makes a second-order correction to the predictor using the previous loss
functions.
Denote the projection of a point y onto X by ΠA
X (y) = argminx∈X kx − ykA (where kxkA =phx, Axi). In this notation, our adaptation of gradient descent employs the update

1/2 
G
−1/2
(1)
xt − ηGt
gt ,xt+1 = ΠX t
Pt
where the matrix Gt = τ =1 gτ gτ⊤ is the outer product of all previous subgradients. The above algorithm
may be computationally impractical in high dimensions since it requires computation of the matrix squareroot of Gt , the outer product matrix. We therefore also analyze a version in which we use diag(Gt ), thediagonal of the outer product matrix, instead of Gt :diag(Gt )1/2
(2)
xt − η diag(Gt )−1/2 gt .
xt+1 = ΠXThis latter update rule can be computed in linear time. Moreover, as we discuss later, when the vectors gt aresparse the update can often be performed in time proportional to the support of the gradient.
Let us compare the regret bounds attained by both variants of gradient descent. Let the diameter of X
be bounded, so supx,y∈X kx − yk2 ≤ D2 . Then Zinkevich’s analysis of online gradient descent—with the
optimal choice in hindsight for the stepsize η—achieves regret
v
u T
uX
√
2
R(T ) ≤ 2D t
kg k .
(3)
2

t 2

t=1

When X is bounded via supx,y∈X kx − yk∞ ≤ D∞ , the following corollary is a consequence of our main
Theorem 5.
Corollary 1 Let the sequence {xt }√⊂ Rd be generated by the update in Eq. (6) and let maxt kx∗ − xt k∞ ≤D∞ . Then with stepsize η = D∞ / 2, for any x∗ ,
v
u
T
d
u
X
X
√
√
2
inf
kgt kdiag(s)−1 = 2D∞
kg1:T,i k2 .
R(T ) ≤ 2dD∞ ts0,h1,si≤d

t=1

i=1

The important parts of the bound are the infimum under the root, which allows us to perform better than using
the identity matrix,
and the fact that the stepsize is easy to set a priori. For example, if X = {x : kxk∞ ≤ 1},√then D2 = 2 d while D∞ = 2. In the case of learning a dense predictor over a box, the bound in Corollary 1
is thus better than Eq. (3) as the identity matrix belongs to the set over which we take the infimum.
1.2 Improvement and Motivating Examples
In Section 6, we give empirical evidence in favor of adaptive algorithms. Here we give a few theoreticalexamples that show that for sparse data—input sequences where gt has low cardinality—the adaptive methods
are likely to perform better than non-adaptive methods. In all the cases we consider in this section we use thehinge loss, ft (x) = [1 − yt hzt , xi]+ , where yt is the label of example t and zt ∈ Rd is a data vector.
To begin, consider the following example of sparse random data. Assume that at each round t, featurei appears with probability pi = min{1, ci−α } for some α ≥ 2 and a constant c. Suppose also that withprobability 1, at least one feature appears, for instance by setting p = 1. Taking the expectation of the boundin Corollary 1, we have
d
d
d q
d
q
X
X
X
X
p
E |{t : |gt,i | = 1}| ≤kg1:T,i k2 =E
E|{t : |gt,i | = 1}| =
pi T
i=1

i=1

i=1

i=1

where to obtain the inequality above we used Jensen’s inequality. Now, notice that for the rightmost sum,Pd
we have c i=1 i−α/2 = O(log d) since α ≥ 2. If the domain is a hypercube,
X = {x : kxk∞ ≤ 1}, then√D∞ = 2. Thus, the regret boundofA
DAG RAD is R(T ) = O(log d T ). In contrast, the standard regret√√
2bound from Eq. (3) has D2 = 2 d, and we know that kgt k2 ≥ 1, yielding a regret bound R(T ) = O( dT ).1
Thus, A DAG RAD’s regret guarantee is exponentially smaller than the non-adaptive regret bound as a functionof dimension for this sparse data setting.
Next we give two concrete examples for which the adaptive methods learn a perfect predictor after diterations, while standard online gradient descent (Zinkevich, 2003) suffers√much higher loss. √We assume thedomain X is compact and thus for online gradient descent we set ηt = 1/ t, which gives O( T ) regret.
1√√
For α ∈ (1, 2), A DAG RAD has regret R(T ) = O(d1−α/2 T ) = o( dT ).

Diagonal Adaptation In this first example, we consider the diagonal version of our proposed update in
Eq. (2) with X = {x : kxk∞ ≤ 1}. Evidently, this choice results in the update xt+1 = xt −η diag(Gt )−1/2 gt
followed by projection onto X . Let ei denote the ith unit basis vector, and assume that for each t, zt = ±ei
for some i. Also let yt = sign(h11, zt i) so that there exists a perfect classifier x∗ = 1 ∈ X . We initialize x1
to be the zero vector. On rounds t = 1, . . . , d, we set zt = ±et , selecting the sign at random. It is clear thatboth diagonal adaptive descent and online gradient descent suffer a unit loss on each of the first d examples.
However, the updates to parameter xi on iteration i differ and amount to1
xt+1 = xt + et (A DAG RAD)
xt+1 = xt + √ et (Gradient Descent) .
t
After the first d rounds, the adaptive predictor has xd+1 = xd+τ = 11 for all τ ≥ 1 and suffers no further losses. The magnitudeof the majority of the coordinates for gradient descent, though, is bounded by
√
√
Pt
2√ t
1
√
after
td iterations. Hence, for Ω( d) iterations, the loss suffered per coordinate is≤i=1
dd/2+id√boundedfrom zero, for a total loss of Ω(d d) (compared with O(d) for A DAG RAD). With larger stepsizes√
η/ t, gradient descent may suffer lower loss; however, an adversary can play zt = e1 indefinitely, forcing
online gradient descent to suffer Ω(d2 ) loss while A DAG RAD suffers constant regret per dimension.
Full Matrix Adaptation The above construction applies to the full matrix algorithm of Eq. (1) as well,
but in more general scenarios,√ as per the following example. When using full matrix proximal functions
we set X = {x : kxk2 ≤ d}. Let V = [v1 . . . vd ] ∈ Rd×d be an orthonormal matrix. Instead of zt
cycling through the unit vectors, we have zt cycle through the vi so that zt = ±v(t mod d)+1 . We let thePdlabel yt = sign( 11, V ⊤ zt ) = sign( i=1 hvi , zt i). We provide an elaborated explanation in the full versionof this paper (Duchi et al., 2010a). Intuitively, A DAG RAD√needs to observe each orthonormal vector vi only
once while stochastic gradient descent’s loss is again Ω(d d).
1.3 Framework and Outline of Results
Before describing our results formally, let us establish notation. Vectors and scalars are lower case italic
letters, such as x ∈ X . We denote a sequence of vectors by subscripts, i.e. xt , xt+1 , . . ., and entries of each
vector by an additional subscript, e.g. xt,j . The subdifferential set of a function f evaluated at x is denoted∂f (x), and a particular vector in the subdifferential set is denoted by f ′ (x) ∈ ∂f (x) or gt ∈ ∂ft (xt ). We
use hx, yi to denote the inner product between x and y. The Bregman divergence associated with a strongly
convex and differentiable function ψ isBψ (x, y) = ψ(x) − ψ(y) − h∇ψ(y), x − yi .

d×d

For a matrix A ∈ R, diag(A) ∈ Rd denotes its diagonal, while for a vector s ∈ Rd , diag(s) denotes
the diagonal matrix with s as its diagonal. We also make frequent use of the following two matrices. Let
g1:t = [g1 · · · gt ] denote the matrix obtained by concatenating the subgradient sequence. We denote the ith
row of this matrix, which amounts to the concatenation of thePtith component of each subgradient we observe,by g1:t,i . Lastly, we define the outer product matrix Gt = τ =1 gτ gτ⊤ .
We describe and analyze several different online learning algorithms and their stochastic convex optimization counterparts. Formally, we consider online learning with a sequence of composite functions φt .
Each function is of the form φt (x) = ft (x) + ϕ(x) where ft and ϕ are (closed) convex functions. In thelearning settings we study, ft is either an instantaneous loss or a stochastic estimate of the objective function.
The function ϕ serves as a fixed regularization function and is typically used to control the complexity of x.
At each round the algorithm makes a prediction xt ∈ X , where X ⊆ Rd is a closed convex set, and thenreceives the function ft . We define the regret with respect to the (optimal) predictor x∗ ∈ X as
Rφ (T ) ,TX
t=1

[φt (xt ) − φt (x∗ )] =

T
X
t=1

[ft (xt ) + ϕ(xt ) − ft (x∗ ) − ϕ(x∗ )] .

(4)

Our analysis applies to multiple methods for minimizing the regret defined in Eq. (4). The first is Nesterov’s primal-dual subgradient method (Nesterov, 2009), and in particular Xiao’s 2009 extension, regularized
dual averaging (RDA) (Xiao, 2009), and the follow-the-regularized-leader (FTRL) family of algorithms (e.g.
Kalai and Vempala, 2003; Hazan et al., 2006). In the primal-dual
subgradient method the algorithm makes aPt
prediction xt on round t using the average gradient ḡt = 1t τ =1 gτ . The update encompasses a trade-off between a gradient-dependent linear term, the regularizer ϕ, and a strongly-convex term ψt for well-conditioned
predictions. Here ψt is the proximal term. The update amounts to solving the problem

1
xt+1 = argmin η hḡt , xi + ηϕ(x) + ψt (x) ,
(5)
t
x∈X

where η is a step-size. The second method also has many names, such as proximal gradient, forwardbackward splitting, and composite mirror descent (Tseng, 2008; Duchi and Singer, 2009; Duchi et al., 2010b).
We use the term composite mirror descent. The composite mirror descent method employs a more immediate
trade-off between the current gradient gt , ϕ, and staying close to xt using the proximal function ψ,
xt+1 = argmin {η hgt , xi + ηϕ(x) + Bψt (x, xt )} .

(6)

x∈X

Our work focuses on temporal√adaptation of the proximal function in a data driven way, while previous work
simply sets ψt ≡ ψ, ψt (·) = tψ(·), or ψt (·) = tψ(·) for some fixed ψ.
We provide formal analyses equally applicable to the above two updates and show how to automaticallychoose the function ψt so as to achieve asymptotically small regret. We describe and analyze two algorithms.
Both algorithms use squared Mahalanobis norms as their proximal functions, setting ψt (x) = 21 hx, Ht xi fora symmetric matrix Ht  0. The first uses diagonal matrices while the second constructs full dimensional
matrices. Concretely, we set
Ht = diag(Gt )1/2 (Diagonal)

and

1/2

Ht = Gt(Full) .

(7)

Plugging the appropriate matrix from the above equation into ψt in Eq. (5) or Eq. (6) gives rise to our
A DAG RAD family of algorithms. Informally, we obtain algorithms similar to second-order gradient descentby constructing approximations to the Hessian of the functions ft . These approximations are conservative
since we rely on the root of the gradient matrices.
We now outline our results, deferring formal statements of the theorems to later sections. Recall thedefinitions of g1:t as the matrix of concatenated subgradients and Gt as the outer product matrix in theprequel. When the proximal function ψt (x) = x, diag(Gt )1/2 x , the A DAG RAD algorithm has bounds
attainable in time at most linear in the dimension d of the problem of
d
d




X
X
Rφ (T ) = O kx∗ k∞
and Rφ (T ) = O max kxt − x∗ k∞
kg1:T,i k2
kg1:T,i k2 .
t≤T

i=1

i=1

We also show that

d
X
i=1

v (
)
u
T
u
X
1/2 t
−1
hgt , diag(s) gt i : s  0, h11, si ≤ d .
kg1:T,i k2 = d
inf
s

t=1

The A DAG RAD algorithm with full matrix divergences entertains bounds of the form




1/2
1/2
Rφ (T ) = O kx∗ k2 tr(GT ) and Rφ (T ) = O max kxt − x∗ k2 tr(GT ) .
t≤T

Similar to the diagonal proximal function case, we further show that
v (
)
u
T


u
X
1/2
1/2 t
−1
tr G
=d
inf
hg , S g i : S  0, tr(S) ≤ d .
T

S

t

t

t=1

We formally state the above regret bounds in Theorems 5 and 8, respectively, and we give further discussion in their corollaries. Essentially, the theorems give oracle inequalities for online optimization. Though thespecific sequence of gradients gt received by the algorithm changes when there is adaptation, the inequalities
say that our regret bounds are as good as the best quadratic proximal function in hindsight.
1.4 Related Work
The idea of adaptation in first order (gradient) methods is by no means new and can be traced back at least to
the 1970s. There, we find Shor’s work on space dilation methods (1972) as well as variable metric methods,
such as the BFGS family of algorithms (e.g. Fletcher, 1970). This older work usually assumes that the function to be minimized is differentiable and, to our knowledge, did not consider stochastic, online, or composite
optimization. More recently, Bordes et al. (2009) proposed carefully designed Quasi-Newton stochastic gradient descent, which is similar in spirit to our methods. However, their convergence results assume a smoothobjective function whose Hessian is strictly positive definite and bounded away from 0. Our results are applicable in more general settings. In the online learning literature, there are results on adaptively choosing alearning rate ηt based on data seen so far (Auer et al., 2002; Bartlett et al., 2007). We, in contrast, actively
adapt the proximal function ψ itself.
The framework that is most related to ours is probably confidence weighted learning, whose most recent
success is the adaptive regularization of weights algorithm (AROW) of Crammer et al. (2009). Crammer et al.

give a mistake-bound analysis for online binary classification, which is similar in spirit to the second-order
Perceptron (Cesa-Bianchi et al., 2005). AROW maintains a mean prediction vector µt ∈ Rd and a covariancematrix Σt ∈ Rd×d over µt as well. At every step of the algorithm, the learner receives a pair (zt , yt ) wherezt ∈ Rd is the tth example and yt ∈ {−1, +1} is the label. Whenever the predictor µt has margin less than1, AROW performs the update
βt =1, αt = [1 − yt hzt , µt i]+ , µt+1 = µt + αt Σt yt zt , Σt+1 = Σt − βt Σt xt x⊤t Σt . (8)hzt , Σt zt i + λIn the above, one can set Σt to be diagonal, which reduces run-time and storage requirements but still gives
good performance (Crammer et al., 2009). In contrast to AROW, the A DAG RAD family uses the root of acovariance-like matrix, a consequence of our formal analysis. Crammer et al.’s algorithm and our algorithms
have similar run times—linear in the dimension d—when using diagonal matrices. However, when using fullmatrices the runtime of their algorithm is O(d2 ), which is faster than ours.
Our approach differs from previous approaches since instead of focusing on a particular loss function
or mistake bound, we view the problem of adapting the proximal function as an online (meta) learning
problem. We then obtain bounds comparable to the bound obtained using the best proximal function chosen
in hindsight. Our bounds are applicable to any convex Lipschitz loss and composite objective functions.

2

Adaptive Proximal Functions

In this section we give the template regret bounds for the family of subgradient algorithms we consider. Examining several well-known optimization bounds (e.g. Beck and Teboulle, 2003; Nesterov, 2009; Duchi et al.,2010b), we see that we can bound the regret as
Rφ (T ) ≤

T
ηX ′
1
2
Bψ (x∗ , x1 ) +kf (xt )k∗ .
η2 t=1 t(9)

Most of the regret depends on dual-norms of ft′ (xt ), where the dual norm in turn depends on the choice of
ψ. This naturally leads to the question of whether we can modify the proximal term ψ along the run of thealgorithm in order to lower the contribution of the aforementioned norms. We achieve this goal by keeping
second order information about the sequence ft .
We begin by providing two corollaries based on previous work that give the regret of our base algorithms
when the proximal function ψt is allowed to change. We assume that ψt is monotonically non-decreasing,that is, ψt+1 (x) ≥ ψt (x). We also assume that ψt is 1-strongly convex with respect to a time-dependent
seminorm k·kψt . Formally,ψt (y) ≥ ψt (x) + h∇ψt (x), y − xi +12
kx − ykψt .
22Strong convexity is guaranteed if and only if Bψt (x, y) ≥ 21 kx − ykψt . We also denote the dual norm ofk·kψt by k·kψ∗ . For completeness, we provide the proofs of following two corollaries in the long version oftthis paper (Duchi et al., 2010a), though they build straightforwardly on Duchi et al. (2010b) and Xiao (2009).
For the primal-dual subgradient update of Eq. (5), the following regret bound holds.
Corollary 2 Let the sequence {xt } be defined by the update in Eq. (5). Then for any x∗ , we haveRφ (T ) ≤

T
ηX ′
1
2
ψT (x∗ ) +kf (xt )kψ∗ .
t−1
η
2 t=1 t(10)

For composite mirror descent algorithms (Eq. (6)), under the assumption w.l.o.g. that ϕ(x1 ) = 0, we have
Corollary 3 Let the sequence {xt } be defined by the update in Eq. (6). Then for any x∗ ,
T −1
T
 ηX
1 X
1
2
∗
∗
∗
Bψt+1 (x , xt+1 ) − Bψt (x , xt+1 ) +kf ′ (xt )kψ∗ .
Rφ (T ) ≤ Bψ1 (x , x1 ) +
t
η
η t=1
2 t=1 t(11)

The above corollaries allow us to prove regret bounds for a family of algorithms that iteratively modify
the proximal functions ψt .

Algorithm 1 A DAG RAD with Diagonal Matrices
Input: η > 0, δ ≥ 0. Initialize x1 = 0, g1:0 = []for t = 1 to T do
Suffer loss ft (xt ), receive subgradient gt ∈ ∂ft (xt ) of ft at xt
Update g1:t = [g1:t−1 gt ], st,i = kg1:t,i k2
Set Ht = δI + diag(st ), ψt (x) = 12 hx, Ht xi
Primal-Dual Subgradient Update (Eq. (5)):
( * t
)
+
1X
1
xt+1 = argmin ηgτ , x + ηϕ(x) + ψt (x) .
t τ =1tx∈X
Composite Mirror Descent Update (Eq. (6)):
xt+1 = argmin {η hgt , xi + ηϕ(x) + Bψt (x, xt )} .
x∈X

end for3

Diagonal Matrix Proximal Functions

For now we restrict ourselves to using diagonal matrices to define matrix proximal functions and (semi)norms.
This restriction serves a two-fold purpose. First, the analysis for the general case is somewhat complicatedand thus the analysis of the diagonal case serves as a proxy for better understanding. Second, in problems withhigh dimension where we expect this type of modification to help, maintaining more complicated proximal
functions is likely to be prohibitively expensive. A benefit of the adaptive algorithms is that there is no need tokeep track of a learning rate as in previous algorithms, as it is implicitly given by the growth of the proximal
function. To remind the reader, g1:t,i is the ith row of the matrix obtained by concatenating the subgradientsfrom iteration 1 through t in the online algorithm.
To provide some intuition for Alg. 1, let us find the retrospectively optimal proximal function. If the2
proximal function chosen is ψ(x) = 12 hx, diag(s)xi for some s  0, then the associated norm is kxk =2hx, diag(s)xi and the dual norm is kxk∗ = x, diag(s)−1 x . Recalling Eq. (9), we consider the problem
min
s

T
X

g, diag(s)−1 g

s.t. s  0, h11, si ≤ c .

t=1This problem is solved by setting si = kg1:T,i k2 and scaling s so that hs, 11i = c. To see this, we can write
the Lagrangian of the minimization problem by introducing multipliers λ  0 and θ ≥ 0 to getL(s, λ, θ) =d
2
X
kg1:T,i k
2

i=1

si

− hλ, si + θ(h1, si − c).
2

Taking derivatives to find the infimum of L, we see that − kg1:T,i k2 /s2i −λi +θ = 0, and the complementarity
1
conditions (Boyd and Vandenberghe, 2004) on λi si imply that λi = 0. Thus we have si = θ− 2 kg1:T,i k2 ,Pdand normalizing using θ gives si = c kg1:T,i k2 / j=1 kg1:T,j k2 . As a final note, plugging si in gives
inf
s

( T d
2
X X gt,i
t=1 i=1si: s  0, h1, si ≤ c

)

1
=
c

d
X
i=1

kg1:T,i k2

!2

.

(12)

It is natural to suspect that if we use a proximal function similar to ψ(x) = 12 hx, diag(s)xi, we should dowell lowering the gradient terms in the regret in Eq. (10) and Eq. (11).
To prove a regret bound for our Alg. 1, we note that both types of updates have regret bounds including aterm dependent solely on the gradients obtained along the algorithm’s run. Thus, the following lemma, whichsays that the choice of ψt in Alg. 1 is optimal up to a multiplicative factor of 2, is applicable to both.
Lemma 4 Let gt = ft′ (xt ) and g1:t and st be defined as in Alg. 1. ThenTX
t=1

gt , diag(st )−1 gt ≤ 2

d
X
i=1

kg1:T,i k2 .

Proof: We prove the lemma by considering an arbitrary R-valued sequence {ai } and its vector representation
a1:i = [a1 · · · ai ]. We are going to show that (where we set 0/0 = 0)TX

a2t
≤ 2 ka1:T k2 .
ka1:t k2
t=1

(13)

We use induction on T . For T = 1, the inequality trivially holds. Assume Eq. (13) holds true for T − 1, then
T
−1
X
a2T
a2T
a2t
a2t
=
+
≤ 2 ka1:T −1 k2 +,ka1:t k2
ka1:t k2
ka1:T k2
ka1:T k2
t=1
t=1

T
X

PT
2
where the inequality follows from the inductive hypothesis. We now defineb=Tt and use first-order
t=1 a
p
√
2
2
inequality for concavity to obtain that so long as bT − aT ≥ 0, we have bT − aT ≤ bT − a2T 2√1b (weT
use an identical technique in the full-matrix case; see Lemma 10). Thus
q
p
a2T
a2
2 ka1:T −1 k2 += 2 bT − a2T + √ T ≤ 2 bT = 2 ka1:T k2 .
ka1:T k2bT

Having proved Eq. (13), we note that by construction st,i = kg1:t,i k2 , thus,TX

gt , diag(st )−1 gt =d
T XX
t=1 i=1

t=1

2
gt,i

kg1:t,i k2

≤2

d
X
i=1

kg1:T,i k2 .

To get a regret bound, we consider the terms consisting of the dual-norm of the subgradients in Eq. (10)2and Eq. (11). When ψt (x) = hx, (δI + diag(st ))xi, the associated dual-norm is kgkψ∗ = g, (δI + diag(st ))−1 g .
t

2

From the definition of st in Alg. 1, we clearly have kft′ (xt )kψ∗ ≤ gt , diag(st )−1 gt . We replace the inversetwith a pseudo-inverse if needed, which is well defined since gt is always in the column-space of diag(st ).
Thus, Lemma 4 gives
d
T
X
X
2
kg1:T,i k2 .
kft′ (xt )kψ∗ ≤ 2
t

t=1

i=1

2

To obtain a bound for a primal-dual subgradient method, we set δ ≥ maxt kgt k∞ , in which case kgt kψ∗

t−1

−1

≤

gt , diag(st ) gt , and follow the same lines of reasoning.
It remains to bound the various Bregman divergence terms in Corollary 3 and the term ψT (x∗ ) in Corollary 2. We focus first on composite mirror-descent updates. Examining Eq. (11) and Alg. 1, we notice that1 ∗hx − xt+1 , diag(st+1 − st )(x∗ − xt+1 )i2
1
max(x∗i − xt+1,i )2 kst+1 − st k1 .
≤2 i
PdSince kst+1 − st k1 = hst+1 − st , 1i and hsT , 1i = i=1 kg1:T,i k2 , we haveBψt+1 (x∗ , xt+1 ) − Bψt (x∗ , xt+1 )

T
−1
X
t=1

=

Bψt+1 (x∗ , xt+1 ) − Bψt (x∗ , xt+1 ) ≤

≤

T −1

1X ∗
2
kx − xt+1 k∞ hst+1 − st , 11i
2 t=1

d
X
1
1
2
2
max kx∗ − xt k∞
kg1:T,i k2 − kx∗ − x1 k∞ hs1 , 11i .
2 t≤T
2
i=1

(14)

We also have222ψT (x∗ ) = δ kx∗ k2 + hx∗ , diag(sT )x∗ i ≤ δ kx∗ k2 + kx∗ k∞

d
X
i=1

kg1:T,i k2 .

Combining the above arguments with Corollaries 2 and 3, and combining Eq. (14) with the fact that Bψ1 (x∗ , x1 ) ≤2
1∗
2 kx − x1 k∞ h1, s1 i, we have proved the following theorem.

Theorem 5 Let the sequence {xt } be defined by Algorithm 1. If we generate xt using the primal-dual
subgradient update of Eq. (5) and δ ≥ maxt kgt k∞ , then for any x∗ ∈ X we haveRφ (T ) ≤ddX
δ ∗ 2 1 ∗ 2 X
kg1:T,i k2 .
kg1:T,i k2 + η
kx k2 + kx k∞
η
η
i=1
i=1

(15)

If we use Algorithm 1 with the composite mirror-descent update of Eq. (6), then for any x∗ ∈ X
Rφ (T ) ≤

d
d
X
X
1
2
kg1:T,i k2 .
kg1:T,i k2 + η
max kx∗ − xt k∞
2η t≤T
i=1
i=1

(16)

The above theorem is a bit unwieldy. We thus perform a few algebraic simplifications to get the next corollary.
Let us assume that X is compact and set D∞ = supx∈X kx − x∗ k∞ . Furthermore, define
v (
)
u
d
d
T
u
X
X
X
t
−1
kg
k = infγ =kg
k , s0 .
hg , diag(s) g i : h1, si ≤1:T,i 2

T

s

i=1

t

1:T,i 2

t

t=1

i=1

The following corollary is immediate.

Corollary 6 Assume that D∞ and γT are defined as above. If we generate the sequence {xt } be given by
Algorithm 1 using the primal-dual subgradient update Eq. (5) with η = kx∗ k∞ , then for any x∗ ∈ X
Rφ (T ) ≤ 2 kx∗ k∞

d
X
i=1

2

kg1:T,i k2 + δkx∗ k2≤ 2 kx∗ k∞ γT + δ kx∗ k1 .
kx∗ k∞√
Using the composite mirror descent update of Eq. (6) to generate {xt } and setting η = D∞ / 2, we haveRφ (T ) ≤

d
X
√
√
2D∞
kg1:T,i k2 = 2D∞ γT .
i=1

We can also prove Corollary 1.
Proof of Corollary 1: The proof simply uses Theorem 5, Corollary 6, and the fact that
!2
)
( T d
d
2
X X gt,i
1 X: s  0, h1, si ≤ d =kg1:T,i k2
inf
s
si
d i=1
t=1 i=1

as in√Eq. (12) in the beginning of this section. Plugging the γT term in from Corollary 6 and multiplying D∞
by d completes the proof.
Intuitively, as discussed in the introduction, Alg. 1 should have good properties on sparse data. For
example, suppose that our gradient terms are based on 0/1-valued features for a logistic√ regression task. ThenPd
the gradient terms in the bound i=1 kg1:t,i k2 should all be much smaller than T . If we assume thatsome features appear much more frequently than others, then the infimal representation of γT and the infimalequality in Corollary 1 show that we can have much lower learning rates on commonly appearing featuresand higher rates on uncommon features, and this will significantly lower the bound on the regret. Further, if
we are constructing a relatively dense predictor x—as is often the case in sparse prediction problems—thenkx∗ k∞ is the best p-norm we can have in the regret.

4

Full Matrix Proximal Functions

In this section we derive and analyze new updates when we estimate a full matrix for the proximal function
ψt instead of a diagonal one. In this generalized case, the algorithm uses the the square-root of the matrix ofouter products of the gradients that observed to update the parameters. As in the diagonal case, we build on
intuition garnered from an optimization problem. We seek a matrix S that solves the minimization problem
min
S

T
X
t=1

gt , S −1 gt

s.t. S  0, tr(S) ≤ c .

Pt
The solution is obtained by defining Gt = τ =1 gτ gτ⊤ , and then setting S to be a normalized version of the
1/2
1/2
root of GT , that is, S = c GT / tr(GT ). The next proposition formalizes this statement, and also showsthat when GT is not full rank we can instead use its pseudo-inverse. The proof is in Duchi et al. (2010a).

Algorithm 2 A DAG RAD with Full Matrices
Input η > 0, δ ≥ 0. Initialize x = 0, S0 = 0, H0 = 0, G0 = 0
for t = 1 to T do
Suffer loss ft (xt ), receive subgradient gt ∈ ∂ft (xt ) of ft at xt .
1

Update Gt = Gt−1 + gt gt⊤ , St = Gt2 .
Let Ht = δI + St , ψt (x) = 21 hx, Ht xi
Primal-Dual Subgradient Update (Eq. (5))( *xt+1 = argmin η
x∈X

t

1X
gt , xt τ =1+1+ ηϕ(x) + ψt (x)t)

Composite Mirror Descent Update (Eq. (6))
xt+1 = argmin {η hgt , xi + ηϕ(x) + Bψt (x, xt )}x∈X

end for
Proposition 7 Consider the following minimization problem:
min tr(S −1 A) subject to S  0, tr(S) ≤ c where A  0 .
S

1

(17)

1

If A is of full rank, then the minimizer of Eq. (17) is S = cA 2 / tr(A 2 ). If A is not of full rank, then setting
1
1
S = cA 2 / tr(A 2 ) givestr(S † A) = inf tr(S −1 A) : S  0, tr(S) ≤ c .
S

†

1
2

2

In either case, tr(S A) = tr(A ) /c.

1/2

If we iteratively use proximal functions of the form ψt (x) = hx, Gt xi, we hope as earlier to attainlow regret and collect gradient information. We achieve our low regret goal by employing a similar doublinglemma to Lemma 4. The resulting algorithm is given in Alg. 2, and the next theorem provides a quantitative
analysis of the motivation above.
Theorem 8 Let Gt be the outer product matrix defined above. If we generate xt using the primal-dual
subgradient update of Eq. (5) and δ ≥ maxt kgt k2 , then for any x∗ ∈ X
δ ∗ 2 1 ∗ 2
1/2
1/2
kx k2 + kx k2 tr(GT ) + η tr(GT ).
ηη
If we use Algorithm 2 with the composite mirror-descent update of Eq. (6), then for any x∗ and δ ≥ 0
1
δ
1/2
1/2
2
2
max kx∗ − xt k2 tr(GT ) + η tr(GT ).
Rφ (T ) ≤ kx∗ k2 +η2η t≤TRφ (T ) ≤

(18)

(19)

Proof: To begin, we consider the difference between the divergence terms at time t + 1 and time t from
Eq. (11) in Corollary 3. Let λmax (M ) denote the largest eigenvalue of a matrix M . We haveE
1D ∗Bψt+1 (x∗ , xt+1 ) − Bψt (x∗ , xt+1 ) =x − xt+1 , (Gt+1 1/2 − Gt 1/2 )(x∗ − xt+1 )
2
1 ∗
1
1/2
1/2
1/2
1/2
2
2
≤
kx − xt+1 k2 λmax (Gt+1 − Gt ) ≤ kx∗ − xt+1 k2 tr(Gt+1 − Gt ) .
2
2
For the last inequality we used the fact that the trace of a matrix is equal to the sum of its eigenvalues
1/2
1/2
along with the property Gt+1 1/2 − Gt 1/2  0 (Davis, 1963, Example 3) and therefore tr(Gt+1 − Gt ) ≥1/2
1/2
λmax (Gt+1 − Gt ). Thus, we get
T
−1
X
t=1

Bψt+1 (x∗ , xt+1 ) − Bψt (x∗ , xt+1 ) ≤

T −1



1X ∗
1/2
1/2
2
kx − xt+1 k2 tr(Gt+1 ) − tr(Gt )
2 t=1

1
1
1/2
2
2
max kx∗ − xt k2 tr(GT 1/2 ) − kx∗ − x1 k2 tr(G1 ) . (20)2 t≤T2For the last inequality we used the fact that G1 is a rank 1 PSD matrix with non-negative trace. What remains
is to bound the gradient terms common to both updates. The following lemma is directly applicable.
≤

Lemma 9 Let St = Gt 1/2 be as defined in Alg. 2. Then, using the pseudo-inverse when necessary,TTXX
gt , ST−1 gt = 2 tr(GT 1/2 ) .
gt , St−1 gt ≤ 2
t=1

t=1

Before we prove the lemma, we state two linear-algebraic lemmas that make its proof and that of thetheorem much more straightforward. The lemmas are quite technical, so we prove them in the long version
The√first auxiliaryof this paper (Duchi et al., 2010a).
√ fact that for√ lemma is the matrix-analogue of the√nonnegative x, y with x ≥ y, x − y ≤ x − y/(2 x), a consequence of the concavity of ·.

Lemma 10 Let B  0 and B −1/2 denote the root of the inverse (or pseudo-inverse) of B. For any c suchthat B − cgg ⊤  0, the following inequality holds:
2 tr((B − cgg ⊤ )1/2 ) ≤ 2 tr(B 1/2 ) − c tr(B −1/2 gg ⊤ ) .
D1/2 Eg .
Lemma 11 Let δ ≥ kgk2 and A  0. Then g, (δI + A1/2 )−1 g ≤ g, (A + gg ⊤ )†−1/2

Proof of Lemma 9: We prove the lemma by induction. The base case is immediate, since hg1 , G1 g1 i =
hg1 ,g1 i
kg1 k = kg1 k2 ≤ 2 kg1 k2 . Now, assume the lemma is true for T − 1, so from the inductive assumption
2

T
X
t=1

gt , St−1 gt ≤ 2

T
−1
X
t=1

−1
gt , ST−1−1 gt + gT , ST gT

.



PT −1
−1/2
−1 PT −1⊤
Since ST −1 does not depend on t, t=1 gt , ST−1
= tr(GT −1 GT −1 ), where−1 gt = tr ST −1
t=1 gt gt
the right-most equality follows from the definitions of St and Gt . Therefore, we get
T
E
E
D
D
X
1/2
−1/2
−1/2
−1/2
gt , St−1 gt ≤ 2 tr(GT −1 GT −1 ) + gT , GT gT = 2 tr(GT −1 ) + gT , GT gT .
t=1

Lemma 10, which also justifies the use of pseudo-inverses, lets us exploit the concavity of the function
1/2
tr(A1/2 ) to bound the above sum by 2 tr(GT ).
N
We can now finalize our proof of the theorem. As in the diagonal case, we have that the squared dual
norm (seminorm when δ = 0) associated with ψt is2
kxkψ∗ = x, (δI + St )−1 x .
t

2Thus it is clear that kgt kψ∗ ≤ gt , St−1 gt . For the dual-averaging algorithms, we use Lemma 11 to seet2that kgt kψ∗ ≤ gt , St−1 gt so long as δ ≥ kgt k2 . The doubling inequality from Lemma 9 implies that
t−1
PT
PT
1/2
1/2
2
2
′
′
≤ 2 tr(GT ) for(x
kf∗t t )kψt∗ ≤ 2 tr(GT ) for mirror-descent algorithms and thatt=1 kft (xt )kψt−1
t=1
primal-dual subgradient algorithms.
1/2
2
Note that Bψ1 (x∗ , x1 ) ≤ 12 kx∗ − x1 k2 tr(G1 ) when δ = 0. Combining the first of the last bounds inPT −1
the previous paragraph with this and the bound on t=1 Bψt+1 (x∗ , xt+1 ) − Bψt (x∗ , xt+1 ) from Eq. (20),
we see that Corollary 3 gives the bound for the mirror-descent family of algorithms. Combining the secondof the bounds in the previous paragraph and Eq. (20) with Corollary 2 gives the desired bound on Rφ (T ) forthe primal-dual subgradient algorithms, which completes the proof of the theorem.
As before, we give a corollary that clarifies the bound implied by Theorem 8. The infimal equalities in
the corollary use Proposition 7. The corollary suggests that if there is a rotation of the space in which thegradient vectors gt have small inner products—a sparse basis for the subgradients gt —then using full-matrix
proximal functions can significantly lower the regret.
Corollary 12 The sequence {xt } generated by Alg. 2 with the primal-dual update and η = kx∗ k2 satisfies
v (
)
u
T
u
X
√
1/2
hgt , S −1 gt i : S  0, tr(S) ≤ d +δ kx∗ k2 .
Rφ (T ) ≤ 2 kx∗ k2 tr(GT )+δ kx∗ k2 = 2 d kx∗ k2 tinf
S

t=1

√
Let X be compact so that supx∈X kx − x∗ k2 ≤ D2 . Let η = D2 / 2 and {xt } be generated by Alg. 2 using
the composite mirror descent update with δ = 0. Then
v (
)
u
T
u
X
√
√
1/2
t
−1
inf
hg , S g i : S  0, tr(S) ≤ d .
R (T ) ≤ 2D tr(G ) = 2dD
φ

2

T

2

S

t

t=1

t

5

Lowering the Regret for Strongly Convex Functions

It is now well established that strong convexity of the functions ft can give significant improvements in the
regret of online convex optimization algorithms (Hazan et al., 2006; Shalev-Shwartz and Singer, 2007). We
can likewise derive lower regret bounds in the presence of strong convexity. We assume that our functions
ft + ϕ are strongly convex with respect to a norm k·k. For simplicity, we assume that each has the samestrong convexity parameter λ,ft (y) + ϕ(y) ≥ ft (x) + ϕ(x) + hft′ (x), y − xi + hϕ′ (x), y − xi +λ2kx − yk .
2

We focus on composite mirror descent algorithms, as the analysis of strongly convex variants of primal-dual
subgradient algorithms does not seem to lend itself to dynamic learning rate adaptation. The tightest analysisof the primal-dual
method for strongly-convex functions keeps the function ψ intact rather than growing it√
at a rate of t, as in standard RDA (Xiao, 2009). Allowing ψ to grow makes attaining the stronger regretbound impossible. It may be possible to analyze RDA when the regularization function ϕ is time-dependent,
but we leave this topic to future research. Without loss of generality let ϕ(x1 ) = 0 and x1 = 0. Rather thangive the proof of the lower regret, we simply state the result, as it is not difficult to prove using techniquesof Hazan et al. (2006), though we include the proof in the full version of this paper (Duchi et al., 2010a).
2

Theorem 13 Assume that ϕ is λ-strongly convex with respect to k·k2 over the set X . Assume further thatkgk∞ ≤ G∞ for all g ∈ ∂ft (x) for x ∈ X . Let {xt } be the sequence of vectors generated by Algorithm 1
2

with the diagonal proximal function ψt (x) = hx, (δI + diag(st ))xi and st,i = kg1:t,i k2 . Setting η ≥the regret is bounded by
!
 2

d
2
2 X
kg
k
2G2∞ δ
G
dG∞
1:T,i
2
∞
∗
2
Rφ (T ) ≤kx1 − x k2 ++1 =O
log(T G∞ ) .
log
λ
λ i=1
δ
λ

6

G2∞
λ ,

Experiments

In this section, we present the results of experiments with natural datasets that suggest that adaptive methods
significantly outperform related non-adaptive methods. We focus on the fully stochastic optimization setting,in which at each iteration the learning algorithm receives a single example. We measure performance using
two metrics: the online loss or error and the test set performance of the predictor the learning algorithm
outputs at the end of a single pass through the training data. We also give some results that show how imposing sparsity constraints (in the form of ℓ1 and mixed-norm regularization) affects the learning algorithm’s
performance. One benefit of the A DAG RAD framework is its ability to straightforwardly generalize to domain constraints X =6 Rd and arbitrary regularization functions ϕ, in contrast to previous adaptive online
algorithms. See Duchi et al. (2010a) for a more complete experimental evaluation.
We experiment with RDA (Xiao, 2009), F OBOS (Duchi and Singer, 2009), adaptive RDA, adaptive F O BOS , the Passive-Aggressive (PA) algorithm (Crammer et al., 2006), and AROW (Crammer et al., 2009). To
remind the reader, PA is an online learning procedure with the updatext+1 = argmin [1 − yt hzt , xi]+ +x

λ2kx − xt k2 ,2where λ is a regularization parameter. PA’s update is similar to the update employed by AROW (see Eq. (8)),
but the latter maintains second order information on x. Using the representer theorem, it is also possible toderive efficient updates for PA and AROW for the logistic loss, log(1 + exp(−yt hzt , xt i)). We thus compare
the above six algorithms using both hinge and logistic loss.
The Reuters RCV1 dataset is a collection of approximately 800,000 text articles, each of which is assigned multiple labels. There are 4 high-level categories—Economics, Commerce, Medical, and Government(ECAT, CCAT, MCAT, GCAT)—and multiple more specific categories. We focus on training binary classifiers for each of the four major categories. The input features we use are 0/1 bigram features, which (postword stemming) yield a representation of approximately 2 million dimensions. The feature vectors are very
sparse, however, and most examples have fewer than 5000 non-zero features.
We compare the twelve different algorithms mentioned in the prequel as well as variants of F OBOS and
RDA with ℓ1 -regularization. We summarize the results of the ℓ1 -regularized runs as well as AROW and PA in
Table 1. We found the results for both the hinge loss and the logistic loss to be qualitatively and quantitatively
very similar. We thus report results only for training with the hinge loss in Table 1. Each row in the table
represents the average of four different experiments in which we hold out 25% of the data for test and performa single online learning pass on the remaining 75% of the data. For RDA and F OBOS, we cross-validate the

ECAT
CCAT
GCAT
MCAT

RDA
.051 (.099).064 (.123).046 (.092).037 (.074)

FB.058 (.194).111 (.226).056 (.183).056 (.146)

A DAG RAD-RDA.044 (.086).053 (.105).040 (.080).035 (.063)

A DAG RAD-FB.044 (.238).053 (.276).040 (.225).034 (.176)

PA
.059
.107
.066
.053

AROW
.049
.061
.044
.039

Table 1: Test set error rates and proportion non-zero weights (in parenthesis) on Reuters RCV1.
stepsize parameter η by running multiple passes and then choosing the output of the learner that had thefewest mistakes during training. For PA and AROW we choose λ using the same approach. We use thesame regularization multiplier for the ℓ1 term to execute RDA and F OBOS. The regularization multiplier was
selected so that RDA yielded a weight vector with approximately 10% non-zero components.
It is evident from the results presented in Table 1 that the adaptive algorithms (AROW and A DAG RAD)are far superior to non-adaptive algorithms in terms of error rate on test data. In addition, the A DAG RAD
algorithms naturally incorporate sparsity since they were run with ℓ1 -regularization, though RDA obtained
significantly higher sparsity levels while the solutions of PA and AROW are dense. Furthermore, althoughomitted from the table for brevity, in every test with the RCV1 corpus, the adaptive algorithms outperformed
the non-adaptive algorithms. Moreover, both A DAG RAD-RDA and A DAG RAD-Fobos outperform AROWon all the classification tasks. Unregularized RDA and F OBOS attained similar results to the ℓ1 -regularizedvariants, though of course the solution of the former versions were not sparse.

7

Conclusions

We presented a paradigm that adapts subgradient methods to the geometry of the problem at hand. The
adaptation allows us to derive strong regret guarantees, which for some natural data distributions achieve
better performance guarantees than previous algorithms. Our online convergence results can be naturally
converted into rate of convergence and generalization bounds (Cesa-Bianchi et al., 2004). The A DAG RAD
family of algorithms incorporates regularization through ϕ and can thus easily generate sparse or otherwise
structured solutions. Our algorithms are straightforward to implement and can be easily specialized to many
useful constraint sets X and regularization terms ϕ. We conducted comprehensive experiments showing that
adaptive methods clearly outperform their non-adaptive counterparts. These results are available in the long
version of this paper (Duchi et al., 2010a). We believe that there are a few theoretical questions that are stillunanswered in this line of work. The first is whether we can efficiently use full matrices in the proximal
functions, as in Section 4, or whether a different algorithm is necessary. A second open issue is whether it
is possible to use non-Euclidean proximal functions. For example, is it possible to adapt the KL divergence
between distributions to characteristics of the problem at hand? We hope to investigate such extensions in thenear future.
Acknowledgments
The first author was supported by the Department of Defense (DoD) through the National Defense Scienceand Engineering Graduate Fellowship program. Part of this work was carried out while the first author was
working at Google Research.

References
J. Abernethy, P. Bartlett, A. Rakhlin, and A. Tewari. Optimal strategies and minimax lower bounds for online
convex games. In Proceedings of the Twenty First Annual Conference on Computational Learning Theory,
2008.
P. Auer, N. Cesa-Bianchi, and C. Gentile. Adaptive and self-confident on-line learning algorithms. Journalof Computer and System Sciences, 64(1):48–75, 2002.
P. L. Bartlett, E. Hazan, and A. Rakhlin. Adaptive online gradient descent. In Advances in Neural Information
Processing Systems 20, 2007.
A. Beck and M. Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31:167–175, 2003.
A. Bordes, L. Bottou, and P. Gallinari. Sgd-qn: Careful quasi-newton stochastic gradient descent. Journal of
Machine Learning Research, 10:1737–1754, 2009.
S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.

N. Cesa-Bianchi, A. Conconi, and C. Gentile. On the generalization ability of on-line learning algorithms.
IEEE Transactions on Information Theory, 50(9):2050–2057, September 2004.
N. Cesa-Bianchi, A. Conconi, , and C. Gentile. A second-order perceptron algorithm. SIAM Journal on
Computing, 34(3):640–668, 2005.
K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz, and Y. Singer. Online passive aggressive algorithms.
Journal of Machine Learning Research, 7:551–585, 2006.
K. Crammer, M. Dredze, and A. Kulesza. Adaptive regularization of weight vectors. In Advances in Neural
Information Processing Systems 23, 2009.
C. Davis. Notions generalizing convexity for functions defined on spaces of matrices. In Proceedings of the
Symposia in Pure Mathematics, volume 7, pages 187–201. American Mathematical Society, 1963.
J. Duchi and Y. Singer. Efficient online and batch learning using forward backward splitting. Journal of
Machine Learning Research, 10:2873–2908, 2009.
J. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Technical Report 2010-24, UC Berkeley Electrical Engineering and Computer Science, 2010a. URL
cs.berkeley.edu/˜jduchi/projects/DuchiHaSi10.pdf.
J. Duchi, S. Shalev-Shwartz, Y. Singer, and A. Tewari. Composite objective mirror descent. In Proceedingsof the Twenty Third Annual Conference on Computational Learning Theory, 2010b.
R. Fletcher. A new approach to variable metric algorithms. Computer Journal, 13:317–322, 1970.
E. Hazan, A. Kalai, S. Kale, and A. Agarwal. Logarithmic regret algorithms for online convex optimization.
In Proceedings of the Nineteenth Annual Conference on Computational Learning Theory, 2006.
A. Kalai and S. Vempala. Efficient algorithms for online decision problems. Journal of Computer and System
Sciences, 71(3):291–307, 2003.
Y. Nesterov. Primal-dual subgradient methods for convex problems. Mathematical Programming, 120(1):221–259, 2009.
G. Salton and C. Buckley. Term weighting approaches in automatic text retrieval. Information Processingand Management, 24(5), 1988.
S. Shalev-Shwartz and Y. Singer. Logarithmic regret algorithms for strongly convex repeated games. Technical report, The Hebrew University, 2007. URL http://www.cs.huji.ac.il/˜shais.
N. Z. Shor. Utilization of the operation of space dilation in the minimization of convex functions. Cybernetics
and Systems Analysis, 6(1):7–15, 1972. Translated from Kibernetika.
P. Tseng. On accelerated proximal gradient methods for convex-concave optimization. Technical report,
Department of Mathematics, University of Washington, 2008.
L. Xiao. Dual averaging methods for regularized stochastic learning and online optimization. In Advances in
Neural Information Processing Systems 23, 2009.
M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of
the Twentieth International Conference on Machine Learning, 2003.