Better Algorithms for Selective Sampling

Francesco Orabona
Nicolò Cesa-Bianchi
DSI, Università degli Studi di Milano, Italy

Abstract
We study online algorithms for selective sampling that use regularized least squares (RLS)
as base classifier. These algorithms typically
perform well in practice, and some of them
have formal guarantees on their mistake andquery rates. We refine and extend these guarantees in various ways, proposing algorithmic variants that exhibit better empirical behavior while enjoying performance guarantees under much more general conditions. We
also show a simple way of coupling a generic
gradient-based classifier with a specific RLSbased selective sampler, obtaining hybrid algorithms with combined performance guarantees.

1. Introduction
Online selective sampling is an active variant of online
learning in which the learner is allowed to adaptively
subsample the labels of an observed sequence of feature vectors. The learner’s goal is to achieve a goodtrade-off between mistakes rate and number of sampled labels. This can viewed as an abstract protocol
for interactive learning applications. For example, asystem for categorizing stories in a newsfeed asks forhuman supervision whenever it feels that more training examples are needed to keep the desired accuracy.
Linear classifiers lend themselves well to selective sampling settings. The margin of the classifier on the current instance can be viewed as a measure of confidence
for the classification of the instance’s label. If this confidence is deemed too low, then the selective sampler
queries the label and uses it, along with the instance,
to adjust the underlying linear model. The selective
sampler performance is evaluated both in terms of pre-francesco@orabona.com
nicolo.cesa-bianchi@unimi.it

dictive accuracy over the entire sequence of examples
and in terms of the overall number of sampled labels.
In this work we consider kernel-based linear classifiers that compute their margins using the regularized
least squares (RLS) estimate. When used for selective
sampling, these algorithms offer a good compromise
between theoretical robustness and empirical performance. More specifically, we focus on two RLS-based
selective samplers: BBQ (Cesa-Bianchi et al., 2009)
and the single teacher version of the algorithm proposed in (Dekel et al., 2010), which we call DGS. As
far as we know, these are the only two examples of efficient online algorithms that offer simultaneous guarantees on mistake and query rate without stringent assumptions on the data process (such as i.i.d. or linear
separability). Both algorithms make the same stochastic assumption on the process generating labels: theBayes classifier belongs to the RKHS induced by the
kernel with which the algorithm is run. On the contrary, no assumptions are made on the generation of
the instances sequence1 . BBQ and DGS base theirquery decisions on a quantity, called rt , which estimates the variance of the RLS margin at the current
time step t. Intuitively, if the variance of the RLS
linear estimate is high in the direction of the feature
vector observed at time t, then the label of that vector
gets sampled. BBQ compares rt with a threshold polynomial in 1/t, where the degree of the polynomial is afree parameter. The threshold used by DGS, instead,is the squared margin returned by the RLS estimate
on the current instance divided by a logarithmic quantity. In both cases, the label is sampled if rt is bigger
than the threshold.
In this work we refine and extend the theoretical analysis of both algorithms, and provide empirical evidence
about differences in their behavior. In particular:
1. While previous analyses could only handle unit
1

Appearing in Proceedings of the 28 th International Conference on Machine Learning, Bellevue, WA, USA, 2011.
Copyright 2011 by the author(s)/owner(s).

Although the analyses of both algorithms work for adversarially chosen instance sequences, DGS assumptions
are weaker, as they allow each instance to be adversarially chosen as a function of past label realizations.

Better Algorithms for Selective Sampling

norm Bayes classifiers, we remove this assumption andexplicit the dependence of regret and queries on theunknown norm of the Bayes classifier. This is especially important when RLS is run in the RKHS induced by a universal kernel (Steinwart, 2001), since
now the Bayes classifier can be any continuous functionof the instances. As a consequence, we can virtually
drop any assumption about the way labels stochastically depend on each instance.
2. Most selective samplers, including BBQ, have aparameter to control the sampling rate. The original
version of DGS, instead, is parameterless. This makes
the algorithm rather awkward to use. Indeed, in someexperiments we observed that DGS keeps sampling alllabels for a long initial stretch of the instance sequence.
We thus introduced a tunable parameter in DGS sampling rule and derived new bounds on mistakes andqueries that take this parameter into account (further
modifications of the original rule were necessary in order to prove these bounds, we call DGS-Mod the DGS
algorithm using the modified rule). Experiments showthat DGS-Mod performs much better than DGS, andin some case better than all other baselines we considered.
3. We have improved the analysis of BBQ by deriving
a tighter upper bound on the regret. The improvement
is significant in the following sense. If the instanceprocess is i.i.d. and satisfies the well-known MammenTsybakov low noise condition, then —provided BBQ
parameter is properly tuned— the instantaneous re1+α

gret per sampled label vanishes at rate N − 2 , where
α is the exponent in the low noise condition. Thisis asymptotically better than the previous rate andmatches the rate achieved by DGS/DGS-Mod under
the same assumptions.
4. In many situations, one would like to run a selective
sampler using an underlying linear classifier different
than RLS. For example, one might be interested in
specific regularizers that promote certain patterns in
the data, such as sparsity. Unfortunately, to the bestof our knowledge, there are no simultaneous bounds onregret and queries for arbitrary online linear classifiers
run in selective sampling mode. In this paper we showthat one can combine any gradient-based online classifier based on strongly convex regularizers with the
DGS-Mod algorithm and obtain a selective sampler
with the same query rate as DGS-Mod and the same
mistake bound as the online classifier (plus a constantterm).
5. Our experiments reveal that both BBQ and DGSMod generally perform well when run with linear kernels. With nonlinear kernels, instead, DGS-Mod suf-

fers badly while BBQ keeps a very good performance.
This fact is apparently caused by a bad dependence of
DGS/DGS-Mod query bound on the determinant of
the Gram matrix. Finally, if data are generated according to the stochastic assumptions underlying bothalgorithms, then BBQ outperforms all other baselines.

2. Preliminaries
Selective sampling is a modification of the online learning protocol for binary classification. At each stept = 1, 2, . . . the learner receives and instance x ∈ Rd
and outputs a binary prediction for the instance’s binary label yt ∈ {−1, +1}. After each prediction, thelearner may observe the true label yt only by querying for it. Hence, if no query is issued at time t, thenyt remains unknown. Since the learner’s performanceis expected to improve as more labels are observed,
the goal in selective sampling is to trade off predictive
accuracy against number of queries.
Given a RKHS H with feature map φ and inner product h· , ·i, we make the following assumptions on thedata-generating process: the sequence x1 , x2 , · · · ∈ Rdof instances is such that there exists f ∈ H for which
hf , φ(xt )i ≤ 1 for all t. Moreover, we assume labels yt are realizations of independent random variables Yt such that
E[Yt | xt ] = hf , φ(xt )i. Hencesgn hf , φ(xt )i , is the Bayes optimal classification forthis noise model. Note that we do not make any as2
sumption on kf k = hf , f i. In particular, we assume
that this quantity is not known to the algorithm.
Note that if H has a universal kernel (Steinwart, 2001),
then any continuous function g(xt ) = E[Yt | xt ] is wellapproximated by some f ∈ H. Hence, with universal kernels our noise model becomes quite general. In
fact it only requires the labels to be generated by astochastic source with a probability density function,
which must be continuous w.r.t. the input space. For
simplicity, in the sequel we always use the linear kernel
and write E[Yt | xt ] = u> xt for some u ∈ Rd . Hereu ∈ Rd is the Bayes classifier of unknown norm kuk
which satisfies u> xt ≤ 1 for all t. We also use thenotation ∆t = u> xt .
The trade-off addressed by the learner concerns the simultaneous control of the number NT of queried labels
and the cumulative regret
RT =

T 

X
b t < 0) − P(Yt ∆t < 0)P(Yt ∆(1)t=1

uniformly over the number T of prediction steps. Following previous papers (Cesa-Bianchi et al., 2009;
Dekel et al., 2010), our bounds can depend on theBetter Algorithms for Selective Sampling

number of steps where the labels Yt are close to being
random. According to our noise model, this is captured by ε Tε , where Tε = {1 ≤ t ≤ T : |∆t | < ε} .
We consider
selective sampling algorithms that useb t to predict yt , where ∆b t ∈ R is an estimate ofsgn ∆∆t . Let Zt be the indicator function of the event thatyt is queried at time t. Then the cumulative regret canbe decomposed as follows (we often use { · } to denotethe indicator function of an event).
Lemma 1. (Dekel et al., 2010) For any ε > 0,
RT ≤ ε Tε +TXb t < 0, |∆t | > ε}Z̄t {∆t ∆

t=1

+

T
X

b t < 0, |∆t | > ε}|∆t | .
Zt {∆t ∆t=1

A different regret decomposition, which we later use,is the one below here.
Lemma 2. (Cesa-Bianchi et al., 2009)
RT ≤ ε Tε +TXb t − ∆t ≥ ε .
P ∆t=1

b t = w>
Our algorithms predict with the margin ∆t xt ,
where wt is computed via the familiar RLS estimate2
−1>
wt = I + St−1 St−1
+ xt x>St−1 Y t−1 . (2)t
The random matrix St−1 = x01 , . . . , x0Nt−1 contains
the Nt−1 queried instances up to time t − 1. The random vector Y t−1 = Y10 , . . . , YN0 t−1 contains the observed labels (so that Yk0 is the label of x0k ), and I
is the d × d identity matrix (whenever it is possible,
we avoid expressing our quantities using dual-variable
notation).
>Introduce the notation At = I + St−1 St−1
, Bt =>> −1>>
u I + xt xt (At + xt xt ) xt , rt = xt (At +−1
xt x>
xt . The following are standard properties oft )the RLS estimate (2), see for example (Cesa-Bianchi
et al., 2009).
Lemma 3. For each t = 1, 2, . . . the following inequalities hold:b t = ∆t − Bt , where |Bt | ≤ kuk √rt + rt ;1. E ∆
2. For all ε > 0,




2
b t + Bt − ∆t ≥ ε St−1 ≤ 2 exp − ε
P ∆
.
2rt
2
Note that the sign of the prediction does not change if
xt x>
t is removed from the expression in parenthesis.

3. If NT is the total number of queries issued in thefirst T steps, then
!
PNT
T
2
X
i=1 kxi k
Zt rt ≤ ln |AT +1 | ≤ d ln 1 +.
dt=1Using Lemma 3 we can prove the following.
Lemma 4. For all ε, p > 0,b t − ∆t ≥ ε St−1
P ∆




2
2p
ε
ε
≤ 2 exp −+ exp 1 −  p  .
2
8rt
4rt kuk + ε
b t − ∆t ≥ ε by
Proof. We expand the indicator of ∆introducing the bias term Bto nnob t + B t − ∆t ≥ εb t − ∆t ≥ ε ≤ ∆∆2nεo+ |Bt | >.
2
The first term is bounded with Lemma 3(2). For thesecond term, note that
n
√
εo n
εo
|Bt | >≤ kuk rt + rt >
2
2
(
) (
!p )
2
ε
ε2
p
≤ rt >
 = rt >
22
4 kuk + ε
4 kuk + ε2pε
≤ exp 1 −  p  .
2
4rt kuk + ε
The first inequality is obtained from Lemma 3(1). The
last one uses {b < 1} ≤ e1−b ∀ b.

3. A new bound for the BBQ algorithm
In this section we improve the regret bound of the BBQ
selective sampler (Algorithm 1). The proof is basedon applying techniques from (Dekel et al., 2010) to
the original BBQ proof of (Cesa-Bianchi et al., 2009).
Here we only show the main differences.
Theorem 1. If BBQ is run with input κ ∈ [0, 1] then,after any number T of steps, NT ≤ T κ ln |AT +1 | withprobability 1. Moreover, the cumulative regret satisfies 
2
8 kuk + 1
5NT
RT ≤ min ε Tε +lnln |AT +1 |
0<ε<1
ε
δ
 !1/κ !
 1/κ
2
4 kuk + ε8
+ 2 d1/κe! 2+eεε2with probability at least 1 − δ uniformly over T .

Better Algorithms for Selective Sampling

Algorithm 1 The BBQ selective sampler
Parameter: 0 ≤ κ ≤ 1
Initialization: Vector w = 0, matrix A1 = I
for each time step t = 1, 2, . . . do
Observe instance xt ∈ Rd
Predict label yt ∈ {−1, +1} with sgn(w>t xt )
if rt > t−κ thenQuery label yt
At+1 = At + xt x>t
wt+1 = A−1
t+1 (At w t + yt xt )else
At+1 = At , wt+1 = wt
end ifend for

where in the last step we used Lemma 3(3). For therounds when a label is not asked we use the following
inequality from (Cesa-Bianchi et al., 2009),
TX
t=1

t : rt ≤t−κ
≤ 2d1/κe!

Proof. We use Lemma 1 when Zt = 1 and Lemma 2
when Zt = 0,TX
b t < 0) − P(Yt ∆t < 0)P(Yt ∆t=1Xb t − ∆t ≥ εP ∆t : rt ≤t−κnob t ∆t ≤ 0, |∆t | ≥ ε |∆t | .
∆X+ 1/κ
1.
aLemma 4 with p = 1/κ now impliesX
b t − ∆t ≥ εP ∆Note that when the dimension d is finite, Lemma3(3)shows that NT is of order d T κ ln T + ln ln T .

≤ ε{|∆t | < ε} +exp (−atκ ) ≤ d1/κe!

t : rt >t−κ

Proceeding as in (Dekel et al., 2010), we can write

8
ε2

1/κ
+e

 !1/κ
2
4 kuk + ε.
ε2

The bound on the number NT of queried labels is thesame as in (Cesa-Bianchi et al., 2009).
This bound, beside showing explicitly the dependency
on the norm of u, has a better dependency on ε in the
regret bound, compared to the one proved in (CesaBianchi et al., 2009). This allows us to prove an optimal rate in the i.i.d. case. In fact, consider the casewhen the instances xt are i.i.d. random variables X t
with fixed but unknown distribution. We model the
distribution of the instances around the hyperplaneu> x = 0 using the popular Mammen-Tsybakov low
noise condition (Tsybakov, 2004):
There exist c > 0 and α ≥ 0 such that

for all ε > 0.
P u> X < ε ≤ c εαnob 2b t ∆t ≤ 0, |∆t | ≥ ε |∆t | ≤ (∆t − ∆t ) .
∆εNote that, when the noise exponent α is 0, this condition is vacuous.

We now use the fact that in BBQ St , and consequently Nt , are deterministic quantities for all t. From
Lemma 4, overapproximating and setting p = 1, it follows that with probability at least 1 − NδT we have
2(2 + e)NT2b∆t − ∆t ≤ 8(U + 1)rt ln.
δ

It is easy to show that a proper choice of κ as a functionof α gives that the regret of BBQ, when expressed interms of the number N of queries, vanishes at rate1+α
N − 2 excluding log factors. This is the same rate
as the one obtained by the DGS algorithm under thesame low noise condition, although DGS requires notuning.

Hence we have that, with probability at least 1 − δ,oX nb t ∆t ≤ 0, |∆t | ≥ ε |∆t |∆4. A modified DGS algorithmt : rt >t−κ

≤

1
ε

X
t : rt >t−κ8(U 2 + 1)rt ln(2 + e)NT
δ

 
 X
2
8 kuk + 1
5NT
≤
ln
rt
ε
δ
t : rt >t−κ 
2
8 kuk + 1
5NT≤
ln
ln |AT +1 |εδIn this section we propose and analyze a modificationof the DGS selective sampler, called DGS-Mod (Algorithm 2), where we introduce a parameter α > 0
in the query rule. This parameter, which appears inboth regret and query bounds, allows us to trade off
regret against queries in a smooth way. In addition
to that, we also change the query rule to make the algorithm independent from the unknown norm of theBayes optimal classifier u (which in previous analyses
was assumed to be known and set to 1).

Better Algorithms for Selective Sampling

Algorithm 2 The DGS-Mod algorithm
Parameter: α > 0
Initialization: Vector w1 = 0, matrix A1 = I
for each time step t = 1, 2, . . . do
Observe instance xt ∈ Rd
ˆ t = w > xt
Set ∆
t
ˆ t)
Predict label yt ∈ {−1,+1} with sgn(∆
2> −1
θt = 2α xt At xt hδ (t) log t
ˆ 2t ≤ θt2 thenif ∆Query label yt
ˆ t |−1ˆ t ) |>∆
At−1 xt
wt+1/2 = wt − sign(∆
x A−1 x
t

t

t

+

−1
At+1 = At + xt x>
and rt = x>tt At+1 xt
wt+1 = A−1
t+1 (At w t+1/2 + yt xt )else
At+1 = At , wt+1 = wt
end ifend forPt−1
Let hδ (t) = 4 s=1 Zs rs + 36 ln(t/δ), the DGS-Mod
strategy (Algorithm 2) decides whether to query bycomparing the square of the current margin to the−1threshold θt2 = 2α x>t At xt hδ (t) ln t. This strategy
is motivated by the following Lemmas, that prove thatin this way the regret on rounds when no label is asked
sum to a constant factor that depends on the ratio between the unknown squared norm of u and α.
Lemma 5. (Dekel et al., 2010) Withat probability
2
2
> −1
ˆ
least 1 − δ, (∆t − ∆t ) ≤ xt At xt kuk + hδ (t)holds simultaneously for all t ≥ 1.
Lemma 6. With probability at least 1 − δ uniformly
over T we have
!!
T
2
n
o
X
2
1
kuk
b t < 0 ≤ 1 + exp+1.
Z̄t ∆t ∆3α24
t=1
Proof. Using Lemma 5, for each t ≥ 2 we can writeno nob t < 0 ≤ (∆t − ∆b t )2 > ∆b 2t , ∆b 2t > θt2
Z̄t ∆t ∆
n


o
2
−1
2
≤ x>
t At xt kuk + hδ (t) > θt
)
!
(
2
2
1
kuk + hδ (t)kuk + hδ (t)> 2 ln t ≤ 2 exp=
αhδ (t)tαhδ (t)
!!
2
1
1
kuk
≤ 2 exp+1.
t
α 36 ln(2/δ)
Since the above chain of inequalities holds for all t ≥ 2with probability at least 1 − δ, by summing over t =1, . . . , T we obtain the desired result.
We can now prove the regret bound for DGS-Mod andits bound on the number of queries.

Theorem 2. After any number T of steps, with probability at least 1 − δ, the cumulative regret RT of themodified DGS algorithm run with input α > 0 satisfies
"
!#
2
2
1 kuk
RT ≤ min 1 + ε Tε + exp
+1
0<ε<1
3
α
24

!
1
T
2
+
2 kuk + 8 ln |AT +1 | + 144 lnεδ
and for X ≥ maxt kxt k the number NT of queries satisfies
4(1 + X 2 )ln |AT +1 |NT ≤ 1 + Tε +
ε2




T
2
× kuk + 1 + 2α ln T 4 ln |AT +1 | + 36 ln.
δ
Proof. By Lemma 1, in norder to bound RoT isPTbenough bounding
via
t=1 Z̄t ∆t ∆t < 0, |∆t | > εLemma 6, and then using the boundTX

b t < 0, |∆t | > ε}|∆2t |Zt {∆t ∆

t=1

≤

1
ε



2

2 kuk + 8 ln |AT +1 | + 144 lnTδ

obtained via an obvious modification of the corresponding result in (Dekel et al., 2010). In order to22α ln tbound NT , define βt = ε4 1+2α
ln t . Then 2
 2
Zt = Zt θt < βt + Zt θt ≥ βtnoˆ 2 ≤ θ2 , θ2 < βt + Zt θ2 ≥ βt . (3)= Zt ∆ttttConsider the first term in (3). Using Lemma 1,q
2−1
ˆ t | + x>|∆t | ≤ |∆t At xt kuk + hδ (t)holds for each t ≥ 2 with probability at least 1 − δ.
Hence, using (a + b)2 ≤ 2a2 + 2b2 we have thatno
ˆ 2t ≤ θt2 , θt2 < βt
∆
n
o
 2
2
−1
≤ ∆2t ≤ 2θt2 + 2x>
t At xt kuk + hδ (t) , θt < βt
2 > −12
2 1 + 2α ln t
2
+ 2 kuk xt At xt , θt < βt
= ∆t ≤ 2θt
2α ln t

1 + 2α ln t
2 > −12≤ ∆t ≤ 2βt+ 2 kuk xt At xt
2α ln tε22 > −12+ 2 kuk xt At xt= ∆t ≤
2



ε2
2
−1
≤ ∆2t ≤ ε2 + 2 kuk x>
A
x
>
t
t
t
2
2
2
 2
4(1 + kxt k ) kuk rt≤ ∆ t ≤ ε2 +ε2Better Algorithms for Selective Samplingholds for each t ≥ 2 with probability at least 1 − δ. In−1
2
the last inequality we used x>
t At xt ≤ (1 + kxt k )rt .
For the second term in (3) we have
 2


−1
2
θ t ≥ βt = 4 x >t At xt (1 + 2α ln t)hδ (t) ≥ ε

4−1≤ 2 x>t At xt (1 + 2α ln t)hδ (t)ε4rt≤ 2 (1 + X 2 )(1 + 2α ln T )hδ (T ) .
εSumming rt over t = 1, . . . , T and using hδ (T ) ≤4 ln |AT +1 | + 36 ln Tδ concludes the proof.
Comparing DGS-Mod and DGS bound, we can seethat the independence on the norm of u comes atthe cost of an additional constant term in the regretbound, and term 1 + 2α ln T multiplying the second
part of the bound on the number of queries. We now
compare the bounds for BBQ and DGS-Mod. Bothregret bounds have a term that takes into accountthe rounds in which no label is asked, and depends
on the unknown squared norm of the Bayes classifier u. In BBQ this term has a polynomial dependence on kuk, whereas in DGS-Mod this dependence
is exponential. However, the main difference between
the two algorithms is in the query bounds. Whereas
in BBQ the query bound is deterministic and controlled by T κ , DGS-Mod has a probabilistic querybound which depends, through Tε , on the number ofsmall margin instances —a far less controllable quantity. Moreover, DGS-Mod query bound contains theterm ln2 |AT +1 |. This can grow fast when the RKHS
is infinite-dimensional, as in the case of universal kernels. Indeed, in Section 6 we observe a super-linear
growth of this term in case of Gaussian kernels, and acorresponding bad empirical behavior of DGS-Mod.

5. A hybrid algorithm
In this section we address the question of designing selective samplers whose underlying online classifier is not based on RLS. For example, consider thegradient-based online classifier that predicts the label of xt ∈ Rd with sgn(v>t xt ), where v 1 = 0 andv t+1 = ∇f ∗ ∇f (v t ) − yt xt . Here f is any differentiable function which is strongly convex w.r.t. a norm
k·k. The function f acts as a regularizer, promoting specific structures in the data sequence such assparsity. One can derive randomized selective samplers from gradient-based classifiers using the technique of (Cesa-Bianchi et al., 2006). However, via thistechnique one only bounds the regret and not the number of queries. We now show a way of combining the
DGS-Mod algorithm with any gradient-based online

Algorithm 3 The hybrid DGS selective sampler
Parameters: α > 0 (used by DGS-Mod)
Initialization: Weight vectors v 1 = 0, w1 = 0
for each time step t = 1, 2, . . . do
Observe instance xt ∈ Rd
ˆ t = w>Set ∆t xt
b 2t ≤ θt2 thenif ∆Predict label yt ∈ {−1, +1} with sgn(v >t xt )
Query label yt
Update wt using the DGS-Mod
algorithm

v t+1 = ∇f ∗ ∇f (v t ) − yt xt
else
ˆ t)
Predict label yt ∈ {−1, +1} with sgn(∆
end ifend forclassifier so that the resulting selective sampler enjoys
a simultaneous bound on regret and number of queries.
Consider the hybrid DGS (Algorithm 3). This selective sampler runs in parallel the gradient-based classifier and the DGS-Mod algorithm. If DGS-Mod issues
a query on the current instance, then the predictionof the gradient-based classifier is used; otherwise, theprediction of DGS-Mod is used. When a query is issued, both algorithms use the label to make an update.
Using the framework of (Orabona & Crammer, 2010),
we get that any gradient-based classifier, using a βstrongly convex function f such that f (av) ≤ a2 f (v)for all a ∈ R+ , has a mistake bounds!
2f (v)MT < inf LT (v) + X
Tβv∈Rdon any sequence (xt , yt ), . . . , (xT , yT ) ∈ Rd ×{−1, +1}
PTof examples. Here LT (v) = t=1 `t (v) is the cumulative hinge loss of v and maxt kxt k∗ ≤ X. This can beused to prove the following result (proof omitted).
Theorem 3. If the hybrid DGS algorithm is run on
an arbitrary sequence of instances with labels generated
according to the model of Section 2, then with probability at least 1−δ the number MT of mistakes satisfiess
2f (u)NT + O(1)MT ≤ LT (u) + X
βwhere u ∈ Rd defines the Bayes classifier. NT is thenumber of queries issued on the same sequence by the
DGS-Mod algorithm, which also bounds the number ofqueries made by the hybrid DGS algorithm.
This bound differs from the previous ones (Theorem 1
and 2) in a few aspects. There, the probability of mak-

Better Algorithms for Selective Sampling

Figure 1. Accuracy against number of examples on the synthetic dataset when the query rate is ∼0.135 (averages over
5 random permutations).

Figure 2. Accuracy against fraction of queried labels on thesynthetic dataset (averages over 5 random permutations).

ing a mistake is bounded as a function of the probability of u making a mistake. Here, we compare mistakesof the algorithm to hinge loss of u. √In the bound,
the only term that depends on time is NT , which issmall when DGS-Mod issues few
p queries. Moreover,this term is proportional to X f (u). So, if the regularizer f matches the properties of u and the data,
through the dual norm k · k∗ , we can expect fewer mistakes. We see this experimentally in Section 6.

6. Experiments
In this section we compare the average accuracy (total number of correct online classifications divided
by the number of examples) of BBQ and DGS-Mod
against two baselines, both using RLS as base classifier. We use synthetic and real-world datasetswith linear and Gaussian kernels. Our baselines are:
SOLE from (Cesa-Bianchi et al., 2006), SS and SSMD
from (Cavallanti et al., 2008). All algorithms have atunable parameter to trade-off performance vs. number of queried labels.
Synthetic dataset with linear kernel. In our firstexperiment we use a synthetic dataset with 10,000 examples drawn from a uniform distribution in 100 dimensions, with instances xt such that kxt k∞ ≤ 1. The
hyperplane u generating the labels has all coefficients
set to zero but the first two, which are chosen at random under the constraint kuk = 1. The labels are
generated stochastically according to the noise model
described in Section 2. Instances with margin bigger than one in absolute value are discarded. In thisexperiment, we also test the hybrid algorithm of Section 5 using a p-norm Perceptron (Gentile, 2003) as

Figure 3. Accuracy against fraction of queried labels forthe task of classifying the most frequent category of RCV1(linear kernel, averages over 5 random permutations).

gradient-based classifier. Cross-validation is used tochoose p. Figure 1 shows average accuracy vs. numberof examples when the parameter of each algorithm ischosen so that the query rate is ∼0.135. In this casethe best algorithm is BBQ, while DGS-Mod exhibits
a much lower accuracy. The hybrid algorithm, whichtakes advantage of the sparse u, performs also quite
well, although not as well as BBQ. Figure 2 shows
the trade-off between average accuracy and fraction ofqueried labels. The behavior over a large spectrum ofquery rates is qualitatively similar to the one observedin Figure 1. In the following experiments the Hybridalgorithm is omitted because its performance remains
very close to that of DGS-Mod.
Real-world data with linear kernel. Our second
experiment uses the first 40,000 newswire stories fromthe Reuters Corpus Volume 1 dataset (RCV1). Each

Better Algorithms for Selective Sampling

Figure 4. Accuracy against fraction of queried labels fora9a (Gaussian kernel, averages over 5 random permutations).

newsstory of this corpus is tagged with one or morelabels from a set of 102 categories. A standard TFIDF bag-of-words encoding is used to obtain 138,860
features. We use a linear kernel and train one-vs-all
based on the most frequent class. Figure 3 shows theaverage accuracy vs. the average fraction of queriedlabels. In this experiment the best performer is SS,
with BBQ and DGS-Mod performing similarly well.
Real-world data with Gaussian kernel. For ourthird and last experiment we use a9a3 , a subset of thecensus-income (Adult) database with 32,561 binarylabeled examples and 123 features. We use a Gaussian kernel with σ 2 = 12.5, chosen by cross-validation.
Here the performance of DGS-Mod is extremely poor,
while BBQ performs best —see Figure 4. In an
attempt to explain DGS-Mod behavior, we plot in2
Figure 5 the value of 1t ln |At | against the number of the examples on a given permutation of data.
2
The term ln |AT +1 | appears in the query bound of
DGS/DGS-Mod —see Theorem 2. While in the linear case this quantity is O(ln T ), in a generic RKHS it
can grow much faster. On this dataset, we observe that2
ln |At | is superlinear in t, implying that DGS/DGSMod query bound becomes vacuous. In fact, in thiscase DGS queries at all time steps, while DGS-Mod
does not perform well no matter how the parameter α
is chosen.

7. Conclusions
In this work we derived improved regret bounds for
RLS-based algorithms in the online selective sampling3

www.csie.ntu.edu.tw/∼cjlin/libsvmtools/

2
Figure 5. Behavior of 1t ln |At | as a function of t in a runof DGS-Mod.

setting. We also conducted experiments to test the
behavior of our algorithms against other RLS-based
samplers. We plan to extend our empirical comparison by including algorithms developed under different
assumptions on the data process, such as the recent
work (Beygelzimer et al., 2010).
Acknowledgments
The authors acknowledge partial support by the PASCAL2 NoE under EC grant FP7-216886.

References
Beygelzimer, A., Hsu, D., Langford, J, and Zhang, T. Agnostic active learning without constraints. In NIPS,
2010.
Cavallanti, G., Cesa-Bianchi, N., and Gentile, C. Linear
classification and selective sampling under low noise conditions. In NIPS, pp. 249–256, 2008.
Cesa-Bianchi, N., Gentile, C., and Zaniboni, L. Worstcase analysis of selective sampling for linear classification. JMLR, 7:1025–1230, 2006.
Cesa-Bianchi, N., Gentile, C., and Orabona, F. Robust bounds for classification via selective sampling. In
ICML, pp. 121–128. Omnipress, June 2009.
Dekel, O., Gentile, C., and Sridharan, K. Robust selective
sampling from single and multiple teachers. In COLT.
MIT Press, 2010.
Gentile, C. The robustness of the p-norm algorithms. Machine Learning, 53(3):265–299, 2003.
Orabona, F. and Crammer, K. New adaptive algorithms
for online classification. In NIPS, pp. 1840–1848. 2010.
Steinwart, I. On the influence of the kernel on the consistency of support vector machines. JMLR, 2:67–93,
2001.
Tsybakov, A. Optimal aggregation of classifiers in statistical learning. The Annals of Statistics, 32(1):135–166,
2004.