New Adaptive Algorithms for Online Classification

Koby Crammer
Department of Electrical Enginering
The Technion
Haifa, 32000 Israel
koby@ee.technion.ac.il

Francesco Orabona
DSI
Università degli Studi di Milano
Milano, 20135 Italy
orabona@dsi.unimi.it

Abstract
We propose a general framework to online learning for classification problems
with time-varying potential functions in the adversarial setting. This framework
allows to design and prove relative mistake bounds for any generic loss function.
The mistake bounds can be specialized for the hinge loss, allowing to recover andimprove the bounds of known online classification algorithms. By optimizing thegeneral bound we derive a new online classification algorithm, called NAROW,
that hybridly uses adaptive- and fixed- second order information. We analyze theproperties of the algorithm and illustrate its performance using synthetic dataset.

1

Introduction

Linear discriminative online algorithms have been shown to perform very well on binary and multiclass labeling problems [10, 6, 14, 3]. These algorithms work in rounds, where at each round a
new instance is given and the algorithm makes a prediction. After the true class of the instance isrevealed, the learning algorithm updates its internal hypothesis. Often, such update is taking place
only on rounds where the online algorithm makes a prediction mistake or when the confidence inthe prediction is not sufficient. The aim of the classifier is to minimize the cumulative loss it suffers
due to its prediction, such as the total number of mistakes.
Until few years ago, most of these algorithms were using only first-order information of the input features. Recently [1, 8, 4, 12, 5, 9], researchers proposed to improve online learning algorithms by incorporating second order information. Specifically, the Second-Order-Perceptron (SOP)
proposed by Cesa-Bianchi et al. [1] builds on the famous Perceptron algorithm with an additional
data-dependent time-varying “whitening” step. Confidence weighted learning (CW) [8, 4] and theadaptive regularization of weights algorithm (AROW) [5] are motivated from an alternative view:
maintaining confidence in the weights of the linear models maintained by the algorithm. Both CW
and AROW use the input data to modify the weights as well and the confidence in them. CW and
AROW are motivated from the specific properties of natural-language-precessing (NLP) data andindeed were shown to perform very well in practice, and on NLP problems in particular. However,
the theoretical foundations of this empirical success were not known, especially when using only
the diagonal elements of the second order information matrix. Filling this gap is one contribution ofthis paper.
In this paper we extend and generalizes the framework for deriving algorithms and analyzing themthrough a potential function [2]. Our framework contains as a special case the second order Perceptron and a (variant of) AROW. While it can also be used to derive new algorithms based on otherloss functions.
For carefully designed algorithms, it is possible to bound the cumulative loss on any sequence ofsamples, even adversarially chosen [2]. In particular, many of the recent analyses are based on the
online convex optimization framework, that focuses on minimizing the sum of convex functions.
1

Two common view-points for online convex optimization are of regularization [15] or primal-dual
progress [16, 17, 13]. Recently new bounds have been proposed for time-varying regularizationsin [18, 9], focusing on the general case of regression problems. The proof technique derived fromour framework extends the work of Kakade et al. [13] to support time varying potential functions.
We also show how the use of widely used classification losses, as the hinge loss, allows us to derive
new powerful mistake bounds superior to existing bounds. Moreover the framework introduced
supports the design of aggressive algorithms, i.e. algorithms that update their hypothesis not only
when they make a prediction mistake.
Finally, current second order algorithms suffer from a common problem. All these algorithms maintain the cumulative second-moment of the input features, and its inverse, qualitatively speaking, isused as a learning rate. Thus, if there is a single feature with large second-moment in the prefix of the
input sequence, its effective learning rate would drop to a relatively low value, and the learning algorithm will take more time to update its value. When the instances are ordered such that the value of
this feature seems to be correlated with the target label, such algorithms will set the value of weightcorresponding to this feature to a wrong value and will decrease its associated learning rate to a low
value. This combination makes it hard to recover from the wrong value set to the weight associatedwith this feature. Our final contribution is a new algorithm that adapts the way the second orderinformation is used. We call this algorithm Narrow Adaptive Regularization Of Weights (NAROW).
Intuitively, it interpolates its update rule from adaptive-second-order-information to fixed-secondorder-information, to have a narrower decrease of the learning rate for common appearing features.
We derive a bound for this algorithm and illustrate its properties using synthetic data simulations.

2

Online Learning for Classification

We work in the online binary classification scenario where learning algorithms work in rounds.
At each round t, an instance xt ∈ Rd is presented to the algorithm, which then predicts a labelŷt ∈ {−1, +1}. Then, the correct label yt is revealed, and the algorithm may modify its hypothesis.
The aim of the online learning algorithm is to make as few mistakes as possible (on any sequenceof samples/labels {(xt , yt )}Tt=1 ). In this paper we focus on linear prediction functions of the formŷt = sign(wt> xt ).
We strive to design online learning algorithms for which it is possible to prove a relative mistakes
bound or a loss bound. Typical such analysis bounds the cumulative loss the algorithm suffers,PTwith the cumulative loss of any classifier u plus an additional penalty called
t=1 `(wt , xt , yt ),PT
the regret, R(u) + t=1 `(u, xt , yt ). Given that we focus on classification, we are more interested
in relative mistakes bound, where we bound the number of mistakes of the learner with R(u) +PT
t=1 `(u, xt , yt ). Since the classifier u is arbitrary, we can choose, in particular, the best classifierthat can be found in hindsight given all the samples. Often R(·) depends on a function measuring
the complexity of u and the number of samples T , and ` is a non-negative loss function. Usually `is chosen to be a convex upper bound of the 0/1 loss. We will also denote by `t (u) = `(u, xt , yt ).
In the following we denote by M to be the set of round indexes for which the algorithm performed a
mistake. We assume that the algorithm always update if it rules in such events. Similarly, we denoteby U the set of the margin error rounds, that is, rounds in which the algorithm updates its hypothesis
and the prediction is correct, but the loss `t (wt ) is different from zero. Their cardinality will be
indicated with M and U respectively. Formally, M = {t : sign(wt> xt ) 6= yt & wt 6= wt+1 },and U = {t : sign(wt> xt ) = yt & wt 6= wt+1 }. An algorithm that updates its hypothesis only on
mistake rounds is called conservative (e.g. [3]). Following previous naming convention [3], we callaggressive an algorithm that updates is rule on rounds for which the loss `t (wt ) is different fromzero, even if its prediction was correct.
We define now few basic concepts from convex analysis that will be used in the paper. Given a
convex function f : X → R, its sub-gradient ∂f (v) at v satisfies: ∀u ∈ X, f (u) − f (v) ≥ (u −v) · ∂f (v). The Fenchel conjugate of f , f ∗ : S → R, is defined by f ∗ (u) = supv∈S v · u − f (v) .
A differentiable function f : X → R is β-strongly convex w.r.t. a norm k · k if for any u, v ∈ S and2
α ∈ (0, 1), h(αu + (1 − α)v) ≤ αf (u) + (1 − α)f (v) − β2 α(1 − α) ku − vk . Strong convexity
turns out to be a key property to design online learning algorithms.
2

3

General Algorithm and Analysis

We now introduce a general framework to design online learning algorithms and a general lemma
which serves as a general tool to prove their relative regret bounds. Our algorithm builds on previous
algorithms for online convex programming with a one significant difference. Instead of using a fixed
link function as first order algorithms, we allow a sequence of link functions ft (·), one for each timet. In a nutshell, the algorithm maintains a weight vector θt . Given a new examples it uses the current
link function ft to compute a prediction weight vector wt . After the target label is received it sets
the new weight θt+1 to be the sum of θt and minus the gradient of the loss at wt . The algorithm issummarized in Fig. 1.
The following lemma is a generalization of Corollary 7 in [13] and Corollary 3 in [9], for online
learning. All the proofs can be found in the Appendix.
Lemma 1. Let ft , t = 1, . . . , T be βt -strongly convex functions with respect to the norms
k · kf1 , . . . , k · kfT over a set S and let k · kfi∗ be the respective dual norms. Let f0 (0) = 0,
and x1 , . . . , xT be an arbitrary sequence of vectors in Rd . Assume that algorithm in Fig. 1 is run
on this sequence with the functions fi . Then, for any u ∈ S, and any λ > 0 we have
!


T
T
2
2
X
1
fT (λu) X ηt kzt kft∗
1 ∗
>
∗
ηt zt
wt − u ≤++ (ft (θt ) − ft−1 (θt )) .
λ
λ
2λβt
λ
t=1
t=1
This Lemma can appear difficult to interpret, but we now show that it is straightforward to use
the lemma to recover known bounds of different online learning algorithms. In particular we
can state the following Corollary that holds for any convex loss ` that upper bounds the 0/1 loss.
1: Input: A series of strongly convex
functions f1 , . . . , fT .
2: Initialize: θ1 = 0
3: for t = 1, 2, . . . , T do
4:
Receive xt
5:
Set wt = ∇ft∗ (θt )6:
Predict ŷt = sign(wt> xt )7:
Receive yt
8:
if `t (wt ) > 0 then9:zt = ∂`t (wt )10:
θt+1 = θt − ηt zt
11:
else
12:
θt+1 = θt
13:
end if
14: end for

PT∗
Corollary 1. Define B = t=1 (ft∗ (θt ) − ft−1
(θt )). Under
the hypothesis of Lemma 1, if ` is convex and it upper bounds
the 0/1 loss, and ηt = η, then for any u ∈ S the algorithm
in Fig. 1 has the following bound on the maximum number of
mistakes M ,TTXX
kzt k2ft∗B
fT (u)
+η
.
(1)
+
M≤
`t (u) +
η
2βt
η
t=1
t=1
Moreover if ft (x) ≤ ft+1 (x), ∀x ∈ S, t = 0, . . . , T − 1 thenB ≤ 0.

A similar bound has been recently presented in [9] as a regret bound. Yet, there are two differences. First, our analysis
bounds the number of mistakes, a more natural quantity inclassification setting, rather than of a general loss function.
Figure 1: Prediction algorithm
Second, we retain the additional term B which may be negative, and thus possibly provide a better bound. Moreover, tochoose the optimal tuning of η we should know quantities that are unknown to the learner. We could
use adaptive regularization methods, as the one proposed in [16, 18], but in this way we would lose
the possibility to prove mistake bounds for second order algorithms, like the ones in [1, 5]. In thenext Section we show how to obtain bounds with an automatic tuning, using additional assumptionion on the loss function.
3.1

Better bounds for linear losses

The hinge loss, `(u, xt , yt ) = max(1 − yt u> xt , 0), is a very popular evaluation metric in classification. It has been used, for example, in Support Vector Machines [7] as well as in many online
learning algorithms [3]. It has also been extended to the multiclass case [3]. Often mistake bounds
are expressed in terms of the hinge loss. One reason is that it is a tighter upper bound of the 0/1 loss
compared to other losses, as the squared hinge loss. However, this loss is particularly interesting forus, because it allows an automatic tuning of the bound in (1). In particular it is easy to verify that it
satisfies the following condition`(u, xt , yt ) ≥ 1 + u> ∂`t (wt ), ∀u ∈ S, wt : `t (wt ) > 0 .
3(2)

Thanks to this condition we can state the following Corollary for any loss satisfying (2).
Corollary 2. Under the hypothesis of Lemma 1, if fT (λu) ≤ λ2 fT (u), and ` satisfies (2), then for
any u ∈ S, and any λ > 0 we have!
X
X  η21t
2>
ηt ≤ L + λfT (u) +B+
kzt kft∗ − ηt wt zt
,
λ
2βt
t∈M∪U
t∈M∪U
P
PT
∗
where L = t∈M∪U ηt `t (u), and B = t=1 (ft∗ (θt ) − ft−1
(θt )). In particular, choosing the
optimal λ, we obtainvuX  η2Xput(3)
kzt k2f ∗ − 2ηt wt> zt .
ηt ≤ L + 2fT (u)t2B +
t
βt
t∈M∪U

t∈M∪U

The intuition and motivation behind this Corollary is that a classification algorithm should be independent of the particular scaling of the hyperplane. In other words, wt and αwt (with α > 0) makeexactly the same predictions, because only the sign of the prediction matters. Exactly this independence in a scale factor allows us to improve the mistake bound (1) to the bound of (3). Hence, when(2) holds, the update of the algorithm becomes somehow independent from the scale factor, and wehave the better bound. Finally, note that when the hinge loss is used, the vector θt is updated as inan aggressive version of the Perceptron algorithm, with a possible variable learning rate.

4

New Bounds for Existing Algorithms

We now show the versatility of our framework, proving better bounds for some known first orderand second order algorithms.
4.1

An Aggressive p-norm Algorithm

We can use the algorithm in Fig. 1 to obtain an aggressive version of the p-norm algorithm [11]. Set
1
ft (u) = 2(q−1)
kuk2q , that is 1-strongly convex w.r.t. the norm k · kq . The dual norm of k · kq is
k · kp , where 1/p + 1/q = 1. Moreover set ηt = 1 in mistake error rounds, so using the second
bound of Corollary 2, and defining R such that kxt k2p ≤ R2 , we have
s
s X
 X
kuk2q
ηt2 kxt k2p + 2ηt yt wt> xt −
ηt
M ≤L+
q−1
t∈M∪U
t∈U
s
s
X
 X
kuk2q
ηt .
≤L+
M R2 +
ηt2 kxt k2p + 2ηt yt wt> xt −
q−1
t∈U

t∈U

Solving for M we have
1
kukq
M ≤L+
kuk2q R2 + R √2(q − 1)
q−1

s

X
1
kuk2q R2 + L + D −ηt ,(4)
4(q − 1)
t∈U


P
P
ηt2 kxt k2p +2ηt yt wt> xt
where L =
η
`
(u),
and
D
=
−
η
t . We have still thet∈M∪U t tt∈UR2
freedom to set ηt in margin error rounds. If we set ηt = 0, the algorithm of Fig.
the
 21 becomesR −2yt wt> xt
p-norm algorithm and we recover its best bound [11]. However if 0 ≤ ηt ≤ min,1
kxt k2pP
we have that D is negative, and L ≤ t∈M∪U `t (u). Hence the aggressive updates gives us a betterbound, thanks to last term that is subtracted to the bound.
In the particular case of p = q = 2 we recover the Perceptron algorithm.
 the minimum
 2 In particular
R /2−yt wt> xt
of D, under the constraint ηt ≤ 1, can be found setting ηt = min, 1 . If R is equal
kxt k2√
to 2, we recover the PA-I update rule, when C = 1. However note that the mistake bound in (4) is
better than the one proved for PA-I in [3] and the ones in [16]. Hence the bound (4) provides the first
theoretical justification to the good performance of the PA-I, and it can be seen as a general evidence
supporting the aggressive updates versus the conservative ones.
44.2

Second Order Algorithms
We show now how to derive in a simple way the bound of the
SOP [1] and the one of AROW [5]. Set ft (x) = 12 x> At x,x x>

where At = At−1 + tr t , r > 0 and A0 = I. The functions
ft are 1-strongly convex w.r.t. the norms kxk2ft = x> At x.
The dual functions of ft (x), ft∗ (x), are equal to 12 x> A−1
t x,
> −1
while kxk2ft∗ is x> A−1x.
Denote
by
χ
=
x
A
x
t
t
t
t−1 t and> −1
mt = yt xt At−1 θt . With these definitions it easy to seethat the conservative version of the algorithm corresponds directly to SOP. The aggressive version corresponds to AROW,with a minor difference. In fact, the prediction of the algor,
rithm in Fig. 1 specialized in this case is yt wt> xt = mt r+χ
t
on the other hand AROW predicts with mt . The sign of thepredictions is the same, but here the aggressive version is upr
dating when mt r+χ
≤ 1, while AROW updates if mt ≤ 1.
t

Figure 2: NLP Data: the number ofwords vs. the word-rank on two sentiment data sets.

To derive the bound, observe that using Woodbury matrix−12(x>
t At−1 θt )∗(θt ) = − 2(r+xidentity we have ft∗ (θt ) − ft−1
> A−1 x )
t
t

t−1

m2

t
= − 2(r+χ. Using the second boundt)

in Corollary 2, and setting ηt = 1 we have
v
u X 
p
u
−1
>
>
M + U ≤ L + u AT u t
x>t At xt + 2yt wt xt −
t∈M∪U

s
≤L+

1
kuk2 +
rX

m2t
r + χt



v
u
X 
u
>
2
t
(u xt )
r log(det(AT )) +2yt wt> xt −

t∈M∪U

t∈M∪U

s
s
X
X
2
>
2
≤ L + rkuk +(u xt ) log(det(AT )) +
t∈M∪U

t∈M∪U

m2t
r + χt

mt (2r − mt ).
r(r + χt )This bound recovers the SOP’s one in the conservative case, and improves slightly the one of AROWfor the aggressive case. It would be possible to improve the AROW bound even more, setting ηt to avalue different from 1 in margin error rounds. We leave the details for a longer version of this paper.
4.3

Diagonal updates for AROW

Both CW and AROW has an efficient version that use diagonal matrices instead of full ones. In thiscase the complexity of the algorithm becomes linear in dimension. Here we prove a mistake boundfor the diagonal version of AROW, using Corollary 2. We denote Dt = diag{At }, where At is
defined as in SOP and AROW, and ft (x) = 12 x> Dt x. Setting ηt = 1, and using the second boundin Corollary 2 and Lemma 12 in [9], we have1
v
!
!
u
P
d
2
u
X
X
x
t,i
t∈M∪U
M +U ≤`t (u) + tuT DT u rlog+ 1 + 2U
r
i=1
t∈M∪U
v
v
!
u d
P
u
d
2
u X
X
X
X
u
x
1
t,i
t∈M∪U
u2
x2t,i trlog
+ 1 + 2U .
=`t (u) + tkuk2 +r i=1 i
r
i=1
t∈M∪U

t∈M∪U

The presence of a mistake bound allows us to theoretically analyze the cases where this algorithm
could be advantageous respect to a simple Perceptron. In particular, for NLP data the features arebinary and it is often the case that most of the features are zero most of the time. On the other hand,1

We did not optimize the constant multiplying U in the bound.

5

these “rare” features are usually the most informative ones (e.g. [8]). Fig. 2 shows the number oftimes each feature (word) appears in two sentiment datasets vs the word rank. Clearly there are few
very frequent words and many rate words. These exact properties were used to originally derive the
CW algorithm. Our analysis justifies this derivation. Concretely, the above considerations leads us
to think that the optimal hyperplane u will be such that
d
X
i=1

u2i

X
t∈M∪U

x2t,i ≈

X

u2i

i∈I

X

x2t,i ≤t∈M∪UX

u2i s ≈ skuk2i∈I

where I is the set of the informative and rare features and s P
is the maximum
number of times thesePdfeatures appear in the sequence. In general each time that i=1 u2i t∈M∪U x2t,i ≤ skuk2 withs small enough, it is possible to show that, with an optimal tuning of r, this bound is better of thePerceptron’s one. In particular, using a proof similar to the one in [1], in the conservative version of2
R2
this algorithm, it is enough to have s < M2dR , and to set r = MsM
R2 −2sd .

5

A New Adaptive Second Order Algorithm

We now introduce a new algorithm with an update rule that interpolates from adaptive-second-orderinformation to fixed-second-order-information. We start from the first bound in Corollary 2. We set
x x>
ft (x) = 21 x> At x, where At = At−1 + trt t , and A0 = I. This is similar to the regularization used−1
in AROW and SOP, but here we have rt > 0 changing over time. Again, denote χt = x>t At−1 xt ,and set ηt = 1. With this choices, we obtain the boundX
X  λ(u> xt )2
λkuk2
mt (2rt − mt )χt rt
M +U ≤`t (u) +
+
−
,
+
2
2rt
2λ(rt + χt )2λ(rt + χt )
t∈M∪U

t∈M∪U

that holds for any λ > 0 and any choice of rt > 0. We would like to choose rt at each step to>2
rtminimize the bound, in particular to have a small value of the sum λ(u rtxt ) + λ(rχtt+χ
. Altought)>
2t
we do not know the values of (u xt ) and λ, still we can have a good trade-off setting rt = bχχt −1
when χt ≥ 1b and rt = +∞ otherwise. Here b is a parameter. With this choice we have that>xt )2 b(u> xt )2
χt rt
1= χt (u, when χt ≥ 1b . Hence we havert +χt = b , andrt
rt +χtX
λkuk2−`t (u)
2t∈M∪U
X  λbχt (u> xt )2
X mt (2rt − mt )
1
1 X
≤
+
χt −
+
2(rt + χt )2λb
2λ2λ(rt + χt )t∈M∪Ut:bχt >1
t:bχt ≤1

X mt (2rt − mt )X χt kuk2 R2
1 X
1
+
min
, χt −≤ λb2(rt + χt ) 2λb2λ(rt + χt )
t∈M∪U
t∈M∪U
t:bχt >1

X mt (2rt − mt )1
1 X
1
≤ λbR2 kuk2 log det(AT ) +min, χt −,22λb2λ(rt + χt )M +U −

t∈M∪U

t∈M∪U

where in the last inequality we used an extension of Lemma 4 in [5] to varying values of rt . Tuning
λ we have
s
r

X
X 
1
bmt (2rt − mt )M +U ≤`t (u) + kukR
+ log det(AT )min (1, bχt ) −.
bR2
rt + χt
t∈M∪U

t∈M∪U

This algorithm interpolates between a second order algorithm with adaptive second order information, like AROW, and one with a fixed second order information. Even the bound is in between
these two worlds. In particular the matrix At is updated only if χt ≥ 1b , preventing its eigenvalues
from growing too much, as in AROW/SOP. We thus call this algorithm NAROW, since its is a newadaptive algorithm, which narrows the range of possible eigenvalues of the matrix At . We illustrateempirically its properties in the next section.
6

5000

5000
25

15
3500

−5

2000

−10

1500

−15
−20

700

0

10

1000

−15

500

−20
−25

20

1200

500
400
300
200

0

10

1000

1000

2000
3000
Examples

4000

−5

−5

2000

1500

−10

1500

1000

−15

1000

−15

500

−20

500

−20

−25

20

PA
AROW
NAROW
AdaGrad

800

600

400

5000

300

Cumulative Number of Mistakes

1200

600
500
400
300
200

1000

2000
3000
Examples

4000

2000
3000
Examples

4000

5000

0

10

PA
AROW
NAROW
AdaGrad

PA
AROW
NAROW
AdaGrad

800

600

400

100

2000
3000
Examples

4000

2000
3000
Examples

4000

0

10

20

2000
3000
Examples

4000

5000

2000
3000
Examples

4000

5000

PA
AROW
NAROW
AdaGrad

250
200
150
100

5000

PA
AROW
NAROW
AdaGrad

1000

350

250
200
150
100

300

PA
AROW
NAROW
AdaGrad

250
200
150
100
50

1000

5000

300

−10

50

1000

50

1000

500
−20

350

150

300

1000

−25

20

200

5000

200

100

−10

250

350

PA
AROW
NAROW
AdaGrad

1000

−20

50

1000

2500

0

−10

200

100

700

−10

3000

5

2500

350

PA
AROW
NAROW
AdaGrad

600

800

−20

3500

10

3000

2000

Cumulative Number of Mistakes

Cumulative Number of Mistakes

800

−10

1500

3500

0

Cumulative Number of Mistakes

−20

−5
−10

4000
15

5

2500
2000

4500

20

10

3000

0

Cumulative Number of Mistakes

−25

3500

5

2500

0

5000
25

4000
15

10

3000

5

4500

20
4000

15

10

Cumulative Number of Mistakes

5000
25

4500

20
4000

Cumulative Number of Mistakes

4500

20

Cumulative Number of Mistakes

25

2000
3000
Examples

4000

5000

1000

Figure 3: Top: Four sequences used for training, the colors represents the ordering in the sequence from blue
to yellow, to red. Middle: cumulative number of mistakes of four algorithms on data with no labels noise.
Bottom: results when training using data with 10% label-noise.

6

Experiments

We illustrate the characteristics of our algorithm NAROW using a synthetic data generated in asimilar manner of previous work [4]. We repeat its properties for completeness. We generated 5, 000
points in R20 where the first two coordinates were drawn from a 45◦ rotated Gaussian distribution
with standard deviation 1 and 10. The remaining 18 coordinates were drawn from independent
Gaussian distributions N (0, 8.5). Each point’s label depended on the first two coordinates using
a separator parallel to the long axis of the ellipsoid, yielding a linearly separable set. Finally, weordered the training set in four different ways: from easy examples to hard examples (measured by
the signed distance to the separating-hyperplane), from hard examples to easy examples, ordered bytheir signed value of the first feature, and by the signed value of the third (noisy) feature - that is by
xi × y for i = 1 and i = 3 - respectively. An illustration of these ordering appears in the top row ofFig. 3, the colors code the ordering of points from blue via yellow to red (last points). We evaluatedfour algorithms: version I of the passive-aggressive (PA-I) algorithm [3], AROW [5], AdaGrad [9]and NAROW. All algorithms, except AdaGrad, have one parameter to be tuned, while AdaGrad has
two. These parameters were chosen on a single random set, and the plots summarizes the results
averaged over 100 repetitions.
The second row of Fig. 3 summarizes the cumulative number of mistakes averaged over 100 repetitions and the third row shows the cumulative number of mistakes where 10% artificial label noise
was used. (Mistakes are counted using the unnoisy labels.)
Focusing on the left plot, we observe that all the second order algorithms outperform the single
first order algorithm - PA-I. All algorithms make few mistakes when receiving the first half of thedata - the easy examples. Then all algorithms start to make more mistakes - PA-I the most, then
AdaGrad and closely following NAROW, and AROW the least. In other words, AROW was able toconverge faster to the target separating hyperplane just using “easy” examples which are far fromthe separating hyperplane, then NAROW and AdaGrad, with PA-I being the worst in this aspect.
The second plot from the left, showing the results for ordering the examples from hard to easy. All
algorithms follow a general trend of making mistakes in a linear rate and then stop making mistakes
when the data is easy and there are many possible classifiers that can predict correctly. Clearly,
7

AROW and NAROW stop making mistakes first, then AdaGrad and PA-I last. A similar trend canbe found in the noisy dataset, with each algorithm making relatively more mistakes.
The third and fourth columns tell a similar story, although the plots in the third column summarize
results when the instances are ordered using the first feature (which is informative with the second)
and the plots in the fourth column summarize when the instances are ordered using the third uninformative feature. In both cases, all algorithms do not make many mistakes in the beginning, then atsome point, close to the middle of the input sequence, they start making many mistakes for a while,and then they converge. In terms of total performance: PA-I makes more mistakes, then AdaGrad,
AROW and NAROW. However, NAROW starts to make many mistakes before the other algorithms
and takes more “examples” to converge until it stopped making mistakes. This phenomena is further
shown in the bottom plots where label noise is injected.
We hypothesize that this relation is due to the fact that NAROW does not let the eigenvalues of thematrix A to grow unbounded. Since its inverse is proportional to the effective learning rate, it meansthat it does not allow the learning rate to drop too low as opposed to AROW and even to some extent
AdaGrad.

7

Conclusion

We presented a framework for online convex classification, specializing it for particular losses, as thehinge loss. This general tool allows to design theoretical motivated online classification algorithms
and to prove their relative mistake bound. In particular it supports the analysis of aggressive updates.
Our framework also provided a missing bound for AROW for diagonal matrices. We have shown
its utility proving better bounds for known online algorithms, and proposing a new algorithm, called
NAROW. This is a hybrid between adaptive second order algorithms, like AROW and SOP, and astatic second order one. We have validated it using synthetic datasets, showing its robustness to themalicious orderings of the sample, comparing it with other state-of-art algorithms. Future work will
focus on exploring the new possibilities offered by our framework and on testing NAROW on realworld data.
Acknowledgments We thank Nicolò Cesa-Bianchi for his helpful comments. Francesco Orabona wassponsored by the PASCAL2 NoE under EC grant no. 216886. Koby Crammer is a Horev Fellow, supported by
the Taub Foundations. This work was also supported by the German-Israeli Foundation grant GIF-2209-1912.

A

Appendix∗
Proof of Lemma 1. Define by ft∗ the Fenchel dual of ft , and ∆t = ft∗ (θt+1 ) − ft−1
(θt ). We have
PT
∗
∗
∗
∗
∗
t=1 ∆t = fT (θT +1 ) − f0 (θ1 ) = fT (θT +1 ). Moreover we have that ∆t = ft (θt+1 ) − ft (θt ) +η2∗∗(θt ) − ηt zt> ∇ft∗ (θt ) + 2βtt kzt k2ft∗ , where we used Theorem 6(θt ) ≤ ft∗ (θt ) − ft−1
ft∗ (θt ) − ft−1
PT
in [13]. Moreover using the Fenchel-Young inequality, we have that λ1 t=1 ∆t = λ1 fT∗ (θT +1 ) ≥P
Tu> θT +1 − λ1 fT (λu) = − t=1 ηt u> zt − λ1 fT (λu). Hence putting all togheter we have

−

T
X
t=1

ηt u> z t −

T
T
1
1X
1X ∗
η2
∗
fT (λu) ≤∆t ≤(ft (θt ) − ft−1
(θt ) − ηt wt> zt + t kzt k2ft∗ ),
λ
λ t=1
λ t=1
2βt

where we used the definition of wt in Algorithm 1.
Proof of Corollary 1. By convexity, `(wt , xt , yt ) − `(u, xt , yt ) ≤ zt> (wt − u), so setting λ = 1
in Lemma 1 we have the stated bound. For the additional statement, using Lemma 12 in [16] and∗ft (x) ≤ ft+1 (x) we have that ft∗ (x) ≥ ft+1(x), so B ≤ 0. The additional statement on B isproved using Lemma 12 in [16]. Using it, we have that ft (x) ≤ ft+1 (x) implies that ft∗ (x) ≥∗ft+1(x), so we have that B ≤ 0.
Proof of Corollary 2. Lemma 1, the condition on the loss (2), and the hypothesis on fT gives us
!
T
T
T
2
2
X
X
1 X ηt kzt kft∗>>ηt (1 − `t (u)) ≤ −ηt u zt ≤ λfT (u) ++ B − ηt zt wt .
λ t=1
2βt
t=1
t=1
Note that λ is free, so choosing its optimal value we get the second bound.

8References[1] N. Cesa-Bianchi, A. Conconi, and C. Gentile. A second-order Perceptron algorithm. SIAM
Journal on Computing, 34(3):640–668, 2005.
[2] N. Cesa-Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge University Press,
2006.
[3] K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz, and Y. Singer. Online passive-aggressivealgorithms. Journal of Machine Learning Research, 7:551–585, 2006.
[4] K. Crammer, M. Dredze, and F. Pereira. Exact Convex Confidence-Weighted learning. Advances in Neural Information Processing Systems, 22, 2008.
[5] K. Crammer, A. Kulesza, and M. Dredze. Adaptive regularization of weight vectors. Advancesin Neural Information Processing Systems, 23, 2009.
[6] K. Crammer and Y. Singer. Ultraconservative online algorithms for multiclass problems. Journal of Machine Learning Research, 3:951–991, 2003.
[7] N. Cristianini and J. Shawe-Taylor. An Introduction to Support Vector Machines and Other
Kernel-Based Learning Methods. Cambridge University Press, 2000.
[8] M. Dredze, K. Crammer, and F. Pereira. Online Confidence-Weighted learning. Proceedingsof the 25th International Conference on Machine Learning, 2008.
[9] J. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning andstochastic optimization. Technical Report 2010-24, UC Berkeley Electrical Engineeringand Computer Science, 2010. Available at http://cs.berkeley.edu/˜jduchi/
projects/DuchiHaSi10.pdf.
[10] Y. Freund and R. E. Schapire. Large margin classification using the Perceptron algorithm.
Machine Learning, pages 277–296, 1999.
[11] C. Gentile. The robustness of the p-norm algorithms. Machine Learning, 53(3):265–299, 2003.
[12] E. Hazan and S. Kale. Extracting certainty from uncertainty: Regret bounded by variation incosts. In Proc. of the 21st Conference on Learning Theory, 2008.
[13] S. Kakade, S. Shalev-Shwartz, and A. Tewari. On the duality of strong convexity and strongsmoothness: Learning applications and matrix regularization. Technical report, TTI, 2009.
http://www.cs.huji.ac.il/ shais/papers/KakadeShalevTewari09.pdf.
[14] J. Kivinen, A. Smola, and R. Williamson. Online learning with kernels. IEEE Trans. on Signal
Processing, 52(8):2165–2176, 2004.
[15] A. Rakhlin and A. Tewari. Lecture notes on online learning. Technical report, 2008. Available at http://www-stat.wharton.upenn.edu/˜rakhlin/papers/online_
learning.pdf.
[16] S. Shalev-Shwartz. Online learning: Theory, algorithms, and applications. Technical report,
The Hebrew University, 2007. PhD thesis.
[17] S. Shalev-Shwartz and Y. Singer. A primal-dual perspective of online learning algorithms.
Machine Learning Journal, 2007.
[18] L. Xiao. Dual averaging method for regularized stochastic learning and online optimization.
In Advances in Neural Information Processing Systems 22, pages 2116–2124. 2009.

9