Online Active Learning with Surrogate Loss Functions
Authors: Giulia DeSalvo
Claudio Gentile
Tobias Sommer Thune
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: active learning
streaming
weak labels

Abstract: We derive a novel active learning algorithm in the streaming setting for binary classification tasks. The algorithm leverages 
weak labels to minimize the number of label requests, and trains a model to optimize a surrogate loss on a resulting set of labeled and 
weak-labeled points. Our algorithm jointly admits two crucial properties: theoretical guarantees in the general agnostic setting and a strong empirical performance. Our theoretical analysis shows that the algorithm attains favorable generalization and label complexity bounds, while our empirical study on 18 real-world datasets demonstrate that the algorithm outperforms standard baselines, including the Margin Algorithm, or  Uncertainty Sampling, a high-performing active learning algorithm favored by practitioners.

Online Active Learning with Surrogate Loss Functions
Giulia DeSalvo
Claudio Gentile Google Research New York, NY 10011 cgentile@google. com
Tobias Sommer Thune University of Copenhagen Copenhagen, DK tobias. thune@gmail.comm com
Google Research New York, NY 10011
com
Abstract
We derive a novel active learning algorithm in the streaming setting for binary classification tasks. The algorithm leverages weak labels to minimize the number label requests, and trains a model to optimize a surrogate loss on resulting set of labeled and weak-labeled points. Our algorithm jointly admits two crucial properties: theoretical guarantees the general agnostic setting and a strong empirical performance. Our theoretical analysis shows that the algorithm attains favorable generalization and label complexity bounds, while our empirical study on 18 real-world datasets demonstrate that the algorithm outperforms standard baselines, including the Margin Algorithm, or Uncertainty Sampling, a high- performing active learning algorithm favored by practitioners.
Introduction
While unlabeled data is generated at increasing rates, supervised learning often requires large portions of this data be annotated by human raters, which carry significant costs. Active learning seeks to significantly alleviate this problem through algorithms that attain comparable performance to passive learning (i.e., full supervision) while using considerably fewer labels. Because of the ever increasing use of labeled data in modern machine learning approaches, this calls for the development of more and more effective active learning techniques.
In this paper, we are specifically interested in binary classification problems in the so-called streaming (or online) setting of active learning. In this setting, learning proceeds in sequence of rounds, where in each round an unlabeled sample is received, and the learner decides on on-the-fly whether or not observe the associated binary label. Now, it is common practice, in active learning or machine learning in general, that even for binary classification problems, the loss used both for training and for evaluating statistical performance is not the zero-one loss, but some surrogate function thereof. This results in more tractable (e.g. convex) optimization problems in the training phase, but also in more calibrated metrics in the evaluation phase. For instance, estimates of class probabilities, say, the success rate of a given set of decisions, and thus deploy maximum posterior probability estimator for such probabilities. Then, given training set with labels E {+1} and if p(x) is an estimate of the conditional class probability P [y = 1 2)). a standard goal is to minimize the log-loss 1 log F(x) 1- log Tー In these cases, the logistic link function
may be compelled to output
p(x) = Ice- is often adopted to model conditional class probabilities where i is some (unknown) function in a given hypothesis class. In this and many other situations that arise in practice, is thus advisable resort to surrogate loss functions for both training and evaluation.
The online active learning literature contains a number of proposed algorithms that admit theoretical guarantees for both generalization eтror and label complexity, that is, the expected number of label requests. The theoretical analyses found these works are either tailored the zero-one loss or to general surrogate losses, with much more emphasis historically placed on the former. The papers that
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

analyze zero-one loss introduce novel ideas tackling important theoretical questions in active learning, but the theory does not easily extend to general loss functions see discussion in Henneke and Yang [2019]. Nevertheless, the algorithmic solutions we propose borrow several ideas from one such work, namely [Dasgupta et al. 2008]. In the agnostic setting, Dasgupta et al.) 2008 developed an algorithm for the zero-one loss based on the disagreement between functions, that carefully constructs pseudo-labels, that is, weak labels generated by the algorithm itself. We call this algorithm DHM, after the name of the three authors.
For general surrogate losses, Beygelzimer et al. 2009 designed an algorithm based on constructing importance weighted predictors with theoretical guarantees in the agnostic setting. Cortes et al. [2019A b 2020] further developed these mportance-weighter algorithms enhancing their guarantees and used them as building blocks for meta-algorithms. We refer to these algorithms as IWAL (Importance Weighted Active Learning).
On a different line of (eeneke and Yang 2019) presents a theoretical analysis of an active learning algorithm that uses surrogate loss functions for binary classification, Among the theoretically- oriented contributions in active learning, this work appears to be the closest reference to our paper when it comes to motivations. Yet, it fair to say that the authors make the very strong assumption that the Bayes optimal function for the surrogate loss at hand lies in the hypothesis class used for learning, and they explicitly state that this realizability condition cannot be relaxed without resorting to significantly different approach. Moreover, unlike our work and that of IWAL-based algorithms, Henneke and Yang 2019 are only focusing on deriving bounds on the zero-one risk. And finally, their algorithm operates in a pool-based setting of active learning, where the whole set of unlabeled points is available to the learner, which more flexible than the streaming setting analyzed here.
In practice, the Margin Algorithm, or Uncertainty Sampling, Lewis and Gale [1994] attains a substantial performance improvement compared to passive learning as well as other active learning
algorithms, and is thus often favored by practitioners (e.g. |Schohn and Cohn (2000) Tong and
Koller (00T]] Brinker [2003], Culotta and McCallum 2005].Joshi et al. 20099] Mussmann and
Liang 2018)) Moreover, the margin algorithm is flexible in that it can be used in both the pool and streaming setting. In the pool setting, several papers have recently tailored active learning algorithms to neural networks, always comparing their algorithm's 's empirical performance to that of the margin algorithm [Geifman and El- Yaniv, 2017 Gal et al., 2017 (Savarese et al.) 2018 Ducoffe and Precioso| 2018 Ash et al.] 2020 Moon et al.) 2020, Schroder and Niekler 2020] Overall, the margin algorithm often found to be a competitive contender to this new collection of practical active learning algorithms. Additionally, two extensive empirical studies found that the margin algorithm outperforms many recent active learning algorithms (Yang and Loog 2016 Chuang et al., 2019]. On the theoretical side, several authors developed active learning algorithms with theoretical guarantees for specific classes of functions (e.g., linear separators) based on sampling along the margin [Dasgupta et al., 2005 Balcan et al. 2007 Balcan and Long, 2013 Awasthi et al. 2014, 2015 Zhang 2018 Zhang et al., 2020). but the guarantees of these margin-bac based algorithms only hold algorithm that admits theoretical guarantees without relying on realizability assumptions and that, at the same time, attains in practice performance that is better than that of the margin algorithm in the streaming setting.
under strong assumptions
the realizability of the problem. Our goal is thus to derive
1.1 Contributions
In this paper, we introduce a novel active learning algorithm, called ALPS (Actively Learning over Pseudo-labels for Surrogate losses), in the streaming setting for binary classification tasks that trains a model by optimizing a surrogate loss on the joint set of labeled and self-constructed pseudo-labeles points (Section 3). Crucially, we prove that ALPS admits theoretical guarantees with respect to the surrogate loss in the general agnostic setting while at the same time surpassing the training performance of the margin algorithm as well as other baselines.
More concretely, we prove theoretical guarantees for ALPS in terms of both generalization and label complexity, under assumptions on the interplay between the function class and the data distribution which are not captured by traditional low noise assumptions often formulated active learning (Section 4). We show that ALPS is able to leverage pseudo-labels in a principled manner even though the loss function of interest not the zero-one loss, but surrogate loss thereof. We then complement our thcoretical findings with thorough experimental investigation on 18 real-world
2

---

We consider active learning framework in the streaming setting for binary classification. Learning proceeds in a sequence of rounds. In each round n, the learner receives from the environment an instance (or feature vector) Vy from instance (or feature) space X. Based observed so far, the learner can then decide whether or not to request the true label yn associated with datasets using a class of neural networks, Multi-layer Perceptrons. We test our algorithm against the IWAL algorithm of Beygelzimer al. [2009] since admits theoretical guarantees for general loss functions, and against passive learning since we want to quantify the improvement over supervised methods. Additionally, we generate as competitors pool of margin-based based uncertainty samplers by varying their label request threshold, and show that on almost all datasets our algorithm outperforms the ex ex-post best among such algorithms (Section 5
This paper follows the general research agenda of reducing the gap between theory and practice, which has been widening at a faster rate in the recent active learning literature. As outlined above, we try to bridge this disconnect by deriving an algorithm that not only works well in practice, but also admits solid theoretical guarantees. In doing so, we also introduce novel algorithmic ideas, which could independently lead to new directions of research.
1.2
Main Ideas
The main mechanism behind ALPS is to query the label of the current instance based on the disagreement between hypotheses and to construct pseudo-labels for the non-queried instances. The algorithm then trains a model on the joint set of labeled and pseudo-labeled data. The sample used for training will be unbiased with respect to marginal distribution on the instance space, but label noise will be introduced whenever the pseudo-label differs from the true (unrevealed) label. This noise affects both the generalization ability of the algorithm and its label complexity. Controlling this noise is not only crucial, but also quite challenging, for it relies on assessing the expected reliability of the pseudo-labels.
In order to control this noise, we introduce the novel idea of using requester functions: ALPS learns to query labels on instances with unreliable (that is, potentially noisy) pseudo-labels by using requester function chosen to minimize an importance-weigee weighted estimate of the noise. For the sake of assumed to lie in some generic function class. One natural
our results, the requester functions example of this class is that of margin-based functions, meaning functions that request along the margin of given prediction model. In this case, our algorithm is related the margin algorithm but, unlike the theoretical guarantees for the margin algorithm (e.g. Balcan et al. [2007] )) we do not rely on specific distributional assumptions the instance space. The requester functions are reminiscent of the abstention functions introduced in Cortes et al. 2016). but serve an entirely different purpose in active learning.
ALPS can be seen as an extension of the DHM algorithm (Dasgupta et al., 2008 to surrogate loss functions, which seeks to address the open question posed by Dasgupta al. [2008] of whether there are active learning algorithms that only require solving tractable optimization problems in agnostic scenarios. At the same time, these two algorithms differ on how they treat the label noise introduced by pseudo-labeling. In DHM, the label noise can be easily bypassed by a simple property of the zero-one loss. In contrast, for general surrogate loss functions, this noise is unavoidable, and if not controlled as is done the ALPS algorithm, the learned hypothesis can be arbitrarily far from the best-in-class.
Preliminaries and Notation
what has been
Tn- Label yn is assumed to lie in the output space y {+1) The pairs (x1, y1), (I2, y2).... are drawn i.i.d. from joint distribution L) over X x y.
In order to evaluate the statistical performance of the learner, we consider any bounded surrogate loss function f IR x y > [0, B] that upper bounds the zero-one loss, and let (.(.,)) = E(.,))BB be a [0, 1] normalizzd version of this loss.
Let H denote a hypothesis class of functions h + IR. For simplicity of exposition, we assume that H is a finite class, but our analysis can be extended to classes with finite VC dimension by standard covering arguments. The true (expected) risk of hypothesis h H defined as err(h) = ((((()) v)] and h* argminne err(h) denotes the best-in-class hypothesis.
3

---

= n. Ela.)ezz ((h(z), y) the empirical risk of h over a training set Z (m1, v1) (22,, (2),)2),,- v2),.... ...., (In, vn)).
Moreover, we denote by err(h, Z)=
Given round n 1, we denote by T, the set of labeled data points ((x,, yo)} from rounds s E [n] := [l,..., n where the label was requested by the learning algorithm, and denote by S, its complement, that is, the set of labeled data points {(T,, yo)] from rounds E [n] where the label was not requested. Unlike Tu. the set Sn is not fully known to the learner. On those rounds, the learner replaces the true unobserved label y/+ by pseudo-label Ge. which is a suitable proxy to ye generated by the learner itself. We denote by S, the set containing data points {<E, d,)} from rounds & E [n]] where the label is not requested, and the true label gets replaced by the corresponding pseudo-label.
For notational convenience (and unless otherwise specified), we set D. y, in rounds s where the true label is known to the learner. Then the following two short-hands are used for empirical risk up to round n using ground-truth labels and the empirical risk up to round n using pseudo-labels:
1 Σ ((h(os):us);
@rr(h) = err(h, UT.)) 1 Σ ((h(as))
err(h) = err(h, S. S. UT,)=
In the sequel, we will also need the following definition of consistency of hypothesis h E H. Definition 1. We say that h E H is consistent with labeled data point (z. y) E Xx (ggg((()))) y and, by extension, that h is consistent with a set of labeled data points Z if it is consistent with all data points in Z. Two hypotheses h h H are consistent with one another on set of (unlabeled) points if (isss(())) (h(z)) = sgn(h' (x)) for all x in that set of points.
At each round n, the learner is compelled to output a hypothesis h, E H, and we seek to bound its true risk, err( (h,), in terms of the true risk, err(h"), of the best-in-class hypothesis h², as a function of the total number of streamed points n thus far. In addition, we want bound on the label complexity of the learner, that is, the number of labels requested by the learner during the course of training. This bound should be provably smaller than n, which is the label complexity of a passive learner observing all labels. Further ancillary definitions will be introduced in later sections.
3 The ALPS Algorithm
At a high level, ALPS either requests the label of an instance vector 2n or assigns it pseudo- at each round n. The algorithm then selects a model h, that is consistent on the pseudo-labeled points, S.,, and that minimizes the empirical estimate of the risk, err, (h), which is defined in terms of labule-labeled and labeled points, S. U Ta. processed thus far. See pseudo-code in Algorithm
More concretely, the learned hypothesis at round n is hn = LEARN(S.,, Sn UT..) where:
Definition 2. For sets of labeled data points S and Z, LEARN Z) returns a hypothesis in H that minimizes the empirical risk err(h, 7) on the second argument 7, and is consistent with all labeled data points the first argument S, where consistency is defined in Definition] 7 LEARN raises a flag if no such hypothesis is found.
In the LEARN procedure, we only need to consider hypotheses consistent with pscudo-labeled points, S., because we can show that with high probability, the sign of the best-in-class, h² argminne h err(h), matches the sign of the pseudo-labeled points.
In order to decide whether to query the label of æn, ALPS leverages the disagreements between hypotheses, h41, h-1 E H returned by the LEARN procedure, where the label of the current instance In is assumed to be either +1 for learning hypothesis h-1 and 1 for learning hypothesis h-1. Ideally, the algorithm would use the empirical difference err,,,11) labels to assess this disagreement, but because not all labels at time n have been disclosed to the algorithm, it instead uses the pseudo-labeled version efr, observable. The algorithm compares this difference to slack term, Án. derived from our theoretical analysis. See Appendix A for all slack term definitions. If the loss difference is smaller than the
err, (h_1) based on ground-tre -toun
err,(h-1), which is indeed
'The sign of the pseudo-label ğ determined by the condition errn (1o-)) - errn-1 (leg) > A and whether h-g exist for =1. E.g. 9 = if ef (h-1) e1rm-1(1+41 > An-1 or if h-1 does not exist.

---

Algorithm 1: Actively Learning over Pscudo-labels for Surrogate losses (ALPS)
Input: LEARN(S, 2), Hypothesis class H, requester class R, and slack terms Án. An-
So = 0: To 0: F1 = H x R: for n 1,2..... N do
Receive feature vector Ing
For 1 = =1, let he LEARNN {(In 0n ((xn, 0)] UT-1): Define version space Fn and bias Pni
F, ((h,r) E Fu-1: min 1n-1hh, 2 1--1hh,) -
(R, (W,r))Fa-)
max max La(y. (( - 0) - Cb(u, (x (h))), wey
S 50}
Qn Bernoulli(p.):
if err, n-
(h- 1
err errn-1 > ( if no such h-g is found) for some ý E (+1) AND
On = 0 then
In argmin [[](((x)) 0}}, where
R₂ fr: (r: rh Fn and h consistent with S U (x))
if rn (Ir)) > 0 then
Request yn and update S. S, T, Tn-1 [(In vn)};
else
Do not request Un and use pseudo-label ý to update S, = Sn-1 U ((on 0)), =T,-1;
end if
else
Request y/. and update S. = Bn Ta-1 U ((En, Hn)];
end if
hn LLLLE( Sm, Sn UTT);
end for
Output NN = LEARN , 3N UTN);
slack, then the label is requested because the sign of best-in-class ht cannot be inferred. Otherwise, pseudo-label is constructed. In more detail, the sign of the pseudo-label is determined by the condition e (h_g) erFn > Á and whether hー exist for E +1. Note that by this construction, the LEARN procedure can always return a consistent hypothesis on all pscudo-labeled points.
To understand the next steps in the ALPS algorithm, we relate the ground-trum empirical difference err,, (h) err,, (h') to its the pseudo-labele counterpart err, (h) etr,, (h'). To this effect, we define the difference of difference of losses (n, h²) between two hypotheses h, h H time n as
A (/) == err(h) eer(hh) =er(h)))))))))
(er((h) E7P(h")
n
This idea is also adopted by Dasgupta et al. (0088) their analysis of the DHM algorithm. Yet. because they only deal with zero-one loss, in their case A, (h, ht) = for consistent h h' even when true label does not match the pseudo-label. This easily follows from the fact that if sgu(h) and sgu(h() agree on instance v, ther (I (x())) 7 y) [(sgn(h((x) + y) ((sg((h(x)) # ú} (sgn(h'(x)) + ú). irregardless of whether y = ÿ or not.
In the surrogate loss setting analyzed here, whenever the pseudo-labels do not match their correspond- ing true labels, the term An (h, ht') is typically non-zero even for consistent h'. As a consequence. the magnitude of A, (h. h') must be carefully controlled since, otherwise, it would break both gener- alization and label complexity bounds as well as the guarantee that the best-in-class h" consistent with S,- the sequel, we call A, the noise term, as captures the noise introduced during training due to the discrepancy between pseudo-labels and true labels.
Throughout, 1[-)) the indicator function of its argument.
5

---

To control the noise term, we introduce the idea of using requester functions. Specifically, we consider a set R of functions r: X I., where r(x) 0 means that the label of requested by r, and otherwise it is not requested. At each round n, the algorithm picks a requester function Yn out of
the set R. and the algorithm's final condition of whether or not to request the label is decided by the sign of r. (x))) The requester function I' thus works as the final gatekeeper of whether to use the pseudo-label.
Notice that by definition the noise term An is non-zero when the true labels do not match the pseudo- labels, ys + Ds for some [n]. By construction, since the final condition of whether to use a pseudo-label in round is determined by r.s it follows that I[ * gz I(y, * 0. (0(rr(12))) S 0}.
In addition, for any h consistent with S,, it holds that Us sgn (xx)))),)) and since the surrogate loss l upper bounds the zero-one loss, we have that for any h consistent with S.,
Iv,, + (r., s 0} s ((((x.), yy) (r) s 03 (M).)
00. (I)
The above can thus be used as an upper bound of the noise.
To estimate this upper bound of An. the algorithm constructs an unbiased importance-weighted estimate, r), of (((p(h(z). ()((((()) S <0]] as follows:
Q.
(h, r) = 71 Ps (x.)
Ln (. s 0},
where Q, is Bernoulli random variable with bias (x..) and where (=(-) is (random) function only depending the past history ((I),,)r)). Q₂ 1- The algorithm will request the label ys whenever Q. = to construct this unbiased estimate. In order not to request the label (Q, = 1) too frequently, Pa() (-) is based on shrinking version space F,, that contains only the pairs (h, r) whose empirical estimate L, (h, r) is close to the smallest one.
Given these estimates of E[eB (h(x), (r(()) < <O]], the algorithm chooses requester function Inp with the smallest request rate B[l(r(z)= > 0J] from a set of requester functions in the version space Fn. In this way, the algorithm ensures that the noise term An is kept small. This is due to the fact that the version space Fo contains pairs of function (h, that are provably close to those minimizing Effx( (h(x)) (r(x)) I O}}, combined with the fact that L (h(xx): Un (r. (I,) S 0} is upper bound on the noise at round n via (I.
Putting the above together, ALPS will request the label of I  whenever one of the following three conditions hold: 1) the loss differences of h4 and h is smaller than the slack term, in which case the revealed label is used as we cannot infer the sign of h" and cannot construct a pseudo-label 2) Qn = 1, which case the revealed label used for the empirical estimates I,, r). 3) r. (Ix,) > O, in which case the revealed label is used to control the noise term, A., introduced by pseudo-labeling. In all cases, the revealed labels are used in LEARN to find the best model at each round n.
Notice that, for the sake of argument, we have assumed in the above description to have access to large unlabeled pool of examples x so as to construct a convenient set of requester functions, that is, to estimate E[I(r(x) > 0}] accurately. Yet, our algorithm and its associated analysis can be generalized straightforwardly to the case when such a pool is available only in a streaming way. Moreover, in our experiments in Section [ we do not use an unlabeled pool to generate requester functions or to estimate the requesting rate. Instead, we define the set of requester functions to be margin-based functions with varying thresholds, and then estimate the requesting rate based on the data processed thus far. See Section 5 for details.
Theoretical Guarantees
We now present generalization and label complexity guarantees of our algorithm. These bounds will be in terms of the best-in-class hypothesis, h², whose risk err(h") will be denoted by v. For these guarantees, we consider a class R of requester functions that satisfies the following:
Assumption 1. There exists r* E R and a constans > 0 such that E Eilly, h" (x)) 5)]= 0 and [r (x) > 0H} < Cv.
If given access to large unlabeled pool of data, we can always construct a function r such that Ele(y, ((z)))(((x) 0}] = 0 for any h, since r can always be augmented in such a way to request

---

more frequently (that is, making r(z) > 0 for most r). Moreover below, we will further relax the first constraint to By {( < 0}] S for some 2 O. However, unless more information about the structure of the problem is known, proving that there exists a function r* in the set R such that (x] > 0}] S Cv holds with a favorable (i.e., reasonably small) value of C is more difficult. Nevertheless, unfavorable C' values, just like unfavorable disagreement coefficients, only impact the label complexity bound and not the generalization guarantee. After the theorems below, we present several natural examples of favorable C' values.
Note that Assumumption I does not dictate conditions on the true conditional class probability, 7(x) = Ply = 1 x²) Hence, we are not relying on low-noise assumptions often adopted in active learning in realizable scenarios. Specifically. our assumption cannot be viewed as a surrogate loss counterpart to the Tsybakov [Mammen and Tsybakov] 1999 [Tybakov]] 2004] low noise condition
in the realizable setting (Castro and Nowak] [2008] [Hanneke] 201] Koltchinskii 2010 Dekel et al.
2012] nor as an incarnation of the Bernstein condition, often invoked in statistical learning settings
to achieve fast rates in both passive and active learning [Massart and Nedelec 2006 Bartlett et al.
2006 Koltchinskii 2006 Van Erven et al. 2015 Henneke and Yang 2019].
In general, the richer the R class is, the easier Assumption D is satisfied with a small C. At the same time, since ALPS is learning over H and It simultaneously, the complexity of R affects both generalization bound and label complexity, as per usual in learning guarantees. Below, we first present the generalization bound of the ALPS algorithm. Here and in Theorem 2 hiding logarithmic factors in n, 1/6, and [ x R.
the Ô notation is
Theorem 1. Under Assumption 7 for any > O, with probability least 1 foror any n >> O.
err(hm) S V + Ô (V= #)
where b is the hypothesis computed by ALPS in round n.
This guarantee states that the risk of the hypothesis returned by the algorithm converges to the best-in-class hypothesis at a rate that matches that of standard supervised learning, despite the fact that ALPS uses less labeled points. The analysis used to derive this theorem proves that the noise introduced by the pseudo-labele is, in fact, controlled by the learned requester function so that the above bound can be attained. In passing, we observe that if the loss is convex and the Bayes optimal hypothesis is in the class H, then by using standard consistency techniques (Zhang] 2004 Bartlet al., 2006) conjunction with Theorem | above, we could also attain a bound on the excess risk of the zero-one loss.
The next theorem shows bound on the expected number of labels the algorithm requests. This bound will be in terms of a notion of disagreement coefficient derived from the one in [Hanneke] 2007). Define metric p on the space of hypotheses H as p(h, A() == ((ry)) [le(h(2)),) y) - -(h(s), Using this metric, we consider the 7-ball around the best-in-class: B,, B,()') (h: h(), S 7)-
Then, let == sup (Px [3 E (h") (g((h(x)) o sgn(h" (x:))/>> be the disagreement coef- ficient of H (for the given distribution D over X x V))
Theorem 2. Under Assumption [ for any > O, with probability 1 1- 8, the label complexity of the ALPS algorithm at time n > 0 is bounded as Ô (nw(0 +C).
Disregarding constants and C, the above bound is Ö(nv). This label complexity guarantee of ALPS in conjunction with its generalization bound matches the known lower bound ((nv) from Beygelzimer et al. 2009 up constants and is therefore optimal.
In Assumption I we considered the case when Ei((y, h² (x) < oJ} = 0 which is easy to satisfy if we have rich enough class R with functions that request more frequently. Nevertheless, we can relax this assumption if desired as follows:
Assumption 2. There exists r* E R and constants C Ble(y, h² (r)))(r((x) < 0}] S e and [[[[(r (x) > 0)] S
> 0 and
> 0 such that
Under this assumption, the label complexity guarantee in Theorem 2 remains unchanged while an c term is added to the generalization bound in Theorem when ALPS is run with slack A + e. By definition, e is most and if & v, then this term has basically no effect on generalization.
There are several natural instances where the condition stated in Assumption and Assumption 2 are satisfied with favorable C' values. Consider for example scenario where along the margin of the
7

---

Hypolhwssa
a(h*(x)) (z))
ht
Hypothes is ht
Requesting
Morgin
Requesting Pagion
[x)(2)] <T"}, where the hypothesis h", depicted by the black line, admits a conditional error of, say, 1/2. Middle: A tapered sigmoid function that equals I or 0 outside the [-?", ?"" interval. Right: An example of a requesting region (in yellow) that is not margin- based and where Assumption holdd with C < 1.
Figure 1: Left: In yellow margin requesting region far E X
best-in-class hypothesis, there are hard-to-classify examples, while further away the best-in-class hypothesis mostly classifies the examples correctly. See Figure for an illustration where there is such margin Y around the best-in-class h". This example is often used to explain why the popular margin algorithm works since this algorithm queries the label of points close to the classification surface. In case, letting r" (ar) = 1h* (=)),, it holds that B[e(y, h (x=))(((h* (+)] 2 >" S. for small e and [A" (x) < < = "[C(y."" (+)) [1)]<>>>>]]] If the expected loss of h" conditioned on the
margin region is high, say 1/2, then it follows that [[[[r" (x) > 0}} [[[[/ [ (z)) <²"] < 21, so that Assumption
2 is satisfied with C' 2. Specifically, in Figure 1 it holds that C 2 and
2/50..
When h" performs well outside the margin, then Assumption 2 holds with a small while correctly classifies all points outside the margin, then = 0 and Assumption [ holds. The c = 0 case is easily satisfied by generalized linear models, Ply = 1 [r] = (hh (z)). where is a tapered sigmoid function. Note that Assumption is not placing specific restrictions
the marginal distribution over X, other than [[[[("" (x)) < <TH== 2v. This does not imply conditions on 17(2) when x falls in the region 1/2 (z)] < 7" and hence we not relying on realizability assumptions.
With any given class of hypotheses H, one can always associate the maagin-baseed requester function class R = fr r(z)= = y [f(z)) 7 2 0, h H}. In this case, ALPS can be seen as trying to simultaneously approximate h" and the best threshold y" The resulting algorithm turns out to be related to margin- based approaches since ALPS will seek to query the label of these more difficult points along the margin, but ALPS finds this optimal pair by using different approach.
At the same time, we would like to stress that, in our framework, the function class R need not be restricted margin-based requesters: if there exists small region, (x E X (x) > 03. for some function r' X + IR such that most of the loss incurred by the best-in-class ht is coming from this region, and R is rich enough to contain such function r", then Assumption T and Assumption 2 hold. For an illustration of this situation, see Figure [ on the right.
4.1 Comparisons to IWAL and DHM
The IWAL algorithm of Beygelzimer al. 2009 constructs importance weighted estimates of the expected loss and uses them to select the prediction function. contrast, ALPS leverages importance weighted estimators select requester functions that minimize the noise term. Thus, even though both algorithms construct importance weighted estimators, they serve entirely different purposes. Both IWAL and ALPS attain generalization and label complexity bounds that are effectively of the same order, but our empirical results show that IWAL considerably underperforms compared to other active learning algorithm on all 18 datasets we tested. These empirical results are consistent with other authors' findings (c.g., Figure 2 in Cortes et al. (019b] and Figure 3 in Cortes et al. 22020).
Even though ALPS can be seen generalization of DHM [Daguptta al. 2008 to surrogate loss functions, there are several key differences. The noise introduced by the pseudo-labels does not affect DHM since by definition A, (h, h²) 0 for the zero-one loss. Thus, DHM does not resort to requester functions or other techniques to deal with unreliable pseudo-labels. Moreover, unlike in DHM, the second argument in the LEARN(...) subroutine over which ALPS minimizes error is S, U Tr, not just TR, For the zero-one loss, minimizing the error over S,, U Tr only T, is equivalent since hypothesis consistent on S, admit zero loss over the points in S,, Note that ALPS's pseudo-code
8

---

citar
UCnn
pobt Bobeeo
citar
500
300
500
1002
202
1000
portt Somerved (11
poins commroed (41
parnts oosenved
0.00
Passive
0.775
0.59
0.778
AIPS
Margin-1
250
points atsorved
200
puins stsetved
400
006
500
1000
200
parnt obsorved
450
600
Margin-2
Margin-3
LightL too
Margin-4
Margin-5
Margin
INAL
Margin-7
230
400
500
D0C
1002
200
400
625
500
1000
200
400
500
500
1000
Margin-8
Margin
Figure 2: The plots the left show the performance of ALPS, IWAL, the ex-post best margin algorithm, and passive learning with 4-layer networks for cifar and with 3-layer networks for ij cnn. For the 4-layer networks for cifar, the plot on the right shows the margin algorithms with thresholds in I n ordered from smallest to largest threshold in I m where Margin-I corresponds to the smallest threshold value in m. Margin-2 to the second smallest, etc. As function of the number of observed points (or rounds) n. the plots show the mean over the 50 repetitions and twice its standard error of the number of requested labels well as the accuracy and logistic loss on the test set of the model returned by each algorithm.
reduces to DHM's when & is the zero-one loss and is set to include only the never-requesting function, that is, r(x)= = 0 for all in which case the not constructed. We then attain the same guarantees as DHM's without resorting to Assumption Tor Assumption 2
estimates 4, 4n(h,r) are
5 Empirical Results
In this section, we present our experimental results in the streaming active learning setting that test the ALPS algorithm, the IWAL algorithm, the margin algorithm (or uncertainty sampling), and passive learning algorithm, which requests the label of all points and finds the hypothesis that attains the smallest empirical loss. We compare to IWAL since it is a principled algorithm in the general agnostic scenario with strong theoretical guarantees. We test the margin algorithm since even though its theoretical guarantees do not hold in general, it admits a strong performance in practice. We run passive learning algorithm to demonstrate the benefit of ALPS over standard supervised learning.
We tested these algorithms on 18 publicly available datasets where we used the logistic loss the surrogate loss l and used feedforward artificial neural networks as our model class. Specifically, we used the Multi-layer Perceptron algorithm in the scikit-leard library and ran two diverse network architectures, one with 3-layers and another with 4-layers. For each type of neural network, we constructed diverse finite set of hypotheses by pre-training on small random subsets while varying the 12 regularization parameter and initial weights. For each experiment, we randomly shuffled the dataset, generated the finite hypothesis set, and all the algorithmss. We repeated the experiment 50 times and averaged the results. See Appendix D for details on the datasets and model class settings.
Recall that the margin algorithm in the streaming setting first selects the hypothesis h E H with the smallest empirical loss and then requests the label of a point æ if [P = +1|=]]-Pp [B = -1(x]] < 7 where PA ly =1/x]] is the model h' 's (estimated) conditional probability of labeling the given point I either +1 or 1. We ran nine instances of the margin algorithm for all thresholds 7 E I'm where the set of thresholds 1 I'm. was chosen a result of tuning procedure that consisted of standard grid search and zooming in. For ALPS, the requester class R is also defined by margin-bases functions as r(z) Py +1[æ] py - ||x]]| I ) for each hypothesis h H and each y Ir- Note that we run ALPS with e = 0 for this class R. Unlike r mm. the set I, was not tuned since ALPS learns the best threshold in r,, For details on r., and r,, please see Appendix [
To evaluate the algorithm performance, both accuracy and logistic loss are of interest in different applications as explained in the introduction. Thus, Figure shows the accuracy and logistic loss on

---

the test set of the model returned by each algorithm at each round n. Figure 2 also plots the number of points labeled by each algorithm as a function of the number of unlabeled points (or rounds) n.
Notice, in particular, that for the passive learning algorithm, since the data is streamed in a random order the value of the curves time step n can be interpreted running the algorithm up until we gather nt queries on randomly drawn points. So, for instance, at round n 200 of the passive curve (orange line) for the ijcnn dataset, we effectively randomly sample and reveal the label of 200 points out of the training set, choose a model that corresponds to an empirical risk minimizer over these 200 points, and evaluate this model's s accuracy on the test set. The passive learning curve is then used as a baseline comparator of the active learning algorithms. That is, the best performing active learning algorithm the one that attains an accuracy and logistic loss curve that is on par or better than that of passive learning while requesting the fewest number of labels.
Figure 2 on the right shows that the accuracy and logistic loss curves of the margin algorithm varies with the threshold. In almost all datasets, there exists thresholds whose corresponding margin algorithm admits an accuracy curve that is below that of passive learning and as the threshold increases, the accuracy curve improves eventually matching that of passive learning. This indicates that a good set of threshold values was tested, since we seek an algorithm that requests the fewest number of points (i.e. having a small threshold) with an accuracy curve on par to that of passive learning. We then pick the ex-post best margin algorithm with smallest threshold that admits an learning curve area with respect to accuracy that is within one standard error of the passive learning curve area. If no algorithm admits such a curve, we pick the margin algorithm with the largest learning curve area. Choosing the ex-post best margin algorithm in this way and tuning of I'm gives the margin algorithm an unfair advantage, since both of these processes use the learning curves based on the revealed labels. Nevertheless, it provides an upper bound on the best performance of these uncertainty samplers.
The left-most plots of Figure 2 show that, for both cifar and i jjcnn datasets, the ALPS algorithm performs better than all baseline methods since out of the algorithms that attain the accuracy and logistic loss curve close to that of passive learning. it requests the fewest number of points. In Appendix D we report these figures for all 18 datasets.
Overall for the 3-layer networks, our results show that the ALPS algorithm outperforms the ex-post best margin algorithm on all but one dataset. Similarly, for the 4-layer networks, ALPS performs better than the margin algorithm on all but two dataset. Thus, despite the advantage given by the ex-post tuning of the margin algorithm, ALPS attains better performance. Moreover, ALPS outperforms both passive learning and IWAL on all datasets. On average across all datasets, ALPS requests only a mere 28% of the processed points. Since ALPS was run with e O, these experiments suggest that Assumption [T holding with favorable C' values often happens in practice or that Assumption [ is simply an artifact of our analysis.
Additionally, the ex ex-post best margin algorithm outperforms IWAL on the majority of the datasets, which is consistent with previous studies [Cortes et al.) 2020). IWAL attains higher variance across the trials for some datasets, and overall it performs better than passive learning. In general, the same empirical conclusions about the relative performance of the active learning algorithms hold for logistic loss and accuracy curves for all algorithms except for the margin algorithm. On a few datasets, the margin algorithm attains a logistic loss curve that is worse than that of passive learning while admitting an accuracy curve that is on par to that of passive learning (e.g., ijcnn).
6 Conclusion
We designed an active learning algorithm, called ALPS, for general loss functions that learns to leverage pseudo-labels by using requester functions in order to train model over a joint set of pseudo- label and labeled points. ALPS operates in the general agnostic setting; its model is guaranteed to converge to the best-in-cland prediction model at the same rate as passive learning, while achieving favorable label complexity guarantees under a mild assumption on the class of requester functions. Our comprehensive empirical study on 18 datasets shows that ALPS outperforms relevant baselines, including the margin algorithm often used practice. As next step, we will investigate how to extend our algorithm and its associated analysis to multi-class classification setting.
10

---

Acknowledgments. Most of this research was done while the Tobias Sommer Thune was visiting Google Research in New York. Tobias Sommer Thune further acknowledges partial support by the Independent Research Fund Denmark, grant number 9040-00361B B. We thank the NeurIPS anonymous reviewers whose comments helped us improve the presentation of this paper.
References
Kareem Amin, Giulia DeSalvo, and Afshin Rostamizadch. Understanding the effects of batching in online active learning. In Proceedings of AISTATs, 2020.
Jordan Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford. and Alekh Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds. In Proceedings of ICLR, 2020.
Pranjal Awasthi, Maria Florina Balcan, and Philip M Long. The power of localization for efficiently learning linear separators with noise. In Proceedings of STOC, pages 449-458. ACM, 2014.
Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, and Ruth Urner. Efficient learning of linear separators under bounded noise. Proceedings of COLT, pages 167-190, 2015.
Maria-Floring Balcan and Phil Long. Active and passive learning of linear separators under log- concave distributions. In Proceedings of COLT, pages 288-316, 2013.
Maria-Florina Balcan, Andrei Broder, and Tong Zhang. Margin based active learning. In Proceeedings of COLT, pages 35-50. Springer, 2007.
Peter Bartlett, Michael Jordan, and Jon McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101:138-1550 2006.
Alina Beygelzimer, Sanjoy Dasgupta, and John Langford. Importance weighted active learning. In Proceedings of ICML. pages 49-56. ACM, 2009.
Klaus Brinker. Incorporating diversity in active learning with support vector machines. In Proceedings of ICML, 2003.
Rui Castro and Robert Nowak. Minimax bounds for active learning. IEEE Transactions on Informa- tion Theory, 54:2339-223 2353, 2008.
Nicolò Cesa- Binnchi and Claudio Gentile. Improved risk tail bounds for on-line algorithms. 1EEE Transactions on Information Theory, 54(1):386-38) 2008
Chih-Chung Chang and Chih-Jen Lin. Libsvm : a library for support vector machines. ACM Transactions Intelligent Systems and Technology, 2011.
Galen Chuang, Giulia DeSalvo, Lazarus Karydas, Jean-francois Kagy, Afshin Rostamizadeh, and A Theeraphol. Active learning empirical study. In NeurlPS2019 LIRE Workshop, 2019.
Corinna Cortes, Spencer Greenberg, and Mehryar Mohri. Relative deviation learning bounds and generalization with unbounded loss functions. In ArXiv:1310.5790 2013.
Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri. Learning with rejection. In Proceedings of ALT, 2016.
Corinna Cortes, Giulia DeSalvo, Claudio Gentile, Mehryar Mohri, and Ningshan Zhang. Active learning with disagreement graphs. In Proceedings of ICML, 2019a.
Corinna Cortes, Giulia DeSalvo, Claudio Gentile, Mchryar Mohri, and Ningshan Zhang, Region- based active learning. In Proceedings of AISTATS, 2019b.
Corinna Cortes, Giulia DeSalvo, Claudio Gentile, Mehryar Mohri, and Ningshan Zhang. Adaptive region-based active learning. In Proceedings ICML,, 2020.
Aron Culotta and Andrew McCallum, Reducing labeling effort for structured prediction tasks. In Proceedings of AAAI, 2005.

---

Sanjoy Dasgupta, Adam Tauman Kalai, and Claire Monteleoni. Analysis of perceptron-based based active learning, In Proceedings of COLT, pages 249-263, Springer, 2005.
Sanjoy Dasgupta, Daniel Hsu, and Claire Monteleoni. A general agnostic active learning algorithm. In Proceedings of NeurIPS, pages 353-360, 2008
Ofer Dekel, Claudio Gentile, and Karthik Sridharan. Selective sampling and active learning from single and multiple teachers. Journal of Machine Learning Research, 13:2655- 2695, 2012.
Melanie Ducoffe and Frederic Precioso. Adversarial active learning for deep networks: margin
based approach. In arXiv, 2018
Yarin Gal, Riashat Islam, and Zoubin. Ghahramani. Deep bayesian active learning with image data. In Proceedings of ICML, 2017.
Yonatan Geifman and Ran EI- Yaniv. Deep active learning over the long tail. In arXiv, 2017.
Steve Hanneke. A bound on the label complexity of agnostic active learning. In Proceedings of ICML, pages 353-360. ACM, 2007.
Steve Hanneke. Rates of convergence in active learning. The Annals of Statistics, 39(1):333-361, 2011.
Steve Henneke and Liu Yang. Surrogate losses in passive and active learning. In Electronic Journal of Statistics, 2019.
Ajay Joshi, Fatih Porikli, and Nikolaos Papanikolopoulos. Multi-class active learning for image classification. In Proceedings of CVPR, 2009.
Sham Kakade and Ambuj Tewari. On the generalization ability of online strongly convex program- ming algorithms. In Proceedings of NeurIPS, pages 801-808. 2009.
Vladimir Koltchinskii. Local rademacher complexities and oracle inequalities in risk minimization. The Annals of Statistics, 3466):2593-2656 2006.
Vladimir Koltchinskii. Rademacher complexities and bounding the excess risk in active learning. Journal of Machine Learning Research, 11 11(Sep):247--2455 2010.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Tech Report, 2009.
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010. URL http:/t:://aee
lecun. wwto//edx///////////////////ete/ mnist/
David Lewis and William Gale. A sequential algorithmfor training text classifiers. In Proceedings of SIGIR, 1994.
Enno Mammen and Alexandre Tsybakov. Smooth discrimination analysis. The Annals of Statistics, 17:1808-1829 1999.
Pascal Massart and Elodie Nedelec. Risk bounds for statistical learning. The Annals of Statistics, 34(5):2326 23666,22666222 2006.
Jooyoung Moon, Jiho Kim, Younghak Shin, and Sangheum Hwan. Confidence aware learning for deep neural networks. In arXiv, 2020.
Stephen Mussmann and Percy Liang. Uncertainty sampling is preconditioned stochastic gradient descent on zero-one loss. In Proceedings of NeurlPS, 2018.
F. Pedregosa. G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss. V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825 2228825--880... 2011.
Silvio Savarese, Ozan Sener, and Zoubin. Ghahramani. Active learning for neural network a core set approach. In Proceedings of ICLR, 2018.
12

---

Greg Schohn and David Cohn. Less is more: Active learning with support vector machines. Pro- ceeedings of ICML, 2000.
Christopher Schroder and Andreas. Niekler. A survey of active learning for text classification for deep neural networks. In arXiv, 2020.
Simon Tong and Daphne Koller. Support vector machine active learning with applications text classification. Journal of Machine Learning Research, 2001.
Alexandre Tsybakov. Optimal aggregation of classifiers in statistical learning. The Annals of Statistics, 32(1):135-166, 2004.
Tim Van Erven, Peter Grunwald, Nishant Mehta, Mark Reid, and Robert Williamson. Fast rates in statistical and online learning. Journal of Machine Learning Research, 16:1793-181, 2015.
Joaquin Vanschoren, Jan N. van Rijn, Bernd Bischl, and Luis Torgo. Openml: Networked science in machine learning. SIGKDD Explorations, 15(2):9-600, 2013, doi: 10.1144/2241100 199022661190261111 198. URL http::/doi.... acm. org/10. 1et..1111//2211991111 2641198
Yazhou Yang and Marco Loog. A benchmark and comparison of active learning for logistic regression. In arXiv, 2016.
Chicheng Zhang. Efficient active learning of sparse halfspacce. In Proceedings of COLT, 2018.
Chicheng Zhang, Jie Shen, and Pranjal Awasthi. Efficient active learning of sparse halfspaces with arbitrary bounded noise. Proceedings of NeurIPS, 2020.
Tong Zhang. Statistical behavior and consistency of classification methods based on convex risk minimization. Annals of Statistics, 2004.
13


Reviews:
[{"review_id": "egQZSY4uYUE", "reviewer": "Reviewer_VTZ8", "summary": "The authors propose an active learning algorithm in the streaming setting for binary classification tasks. The algorithm leverages weak labels to minimize the number of label requests and trains a model to optimize a surrogate loss on a resulting set of labeled and weak-labeled points. The paper contains a number of theoretical results and supporting empirical results. Overall, its a very strong paper.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros of this paper:\n- Has theoretical guarantees in addition to good empirical performance. Theoretical guarantees hold in the agnostic case where the true labeling function is not realizable.\n- Furthermore, theoretical guarantees have generalization complexity and LABEL complexity\n- Has good discussion on existing work\n- Aside from its length, the introduction is very, very good. It is well-written, explains detriments in previous theoretical results in active learning, and clearly qualifies what setting it is tackling and how its solution is effective.\n- Uses a very large assortment of real-world datasets\n- Notations are good; the definition of consistency matches the usual definition\n- The explanation for ALPS naturally develops itself, making it easier to follow along.\n- Theoretical findings have bounds that match proven lower bounds up to log terms, showing near optimality.\n\nCons of the paper/questions:\n- Models used are neural networks, but they are not deep networks (they are MLPs). \n- Will the techniques work for DNNs? If yes, how and what needs to change? Will be good to add some intuition for practitioners particularly if this needs to be used in a batch setting\n- Introduction is a bit lengthy; perhaps it could be broken down into more sections\t\n- Link in Algorithm 1 (superscript 2) is broken; doesn't tab to footnote\n- Alg 1 notation for h_y could be refined to show that h_{-1} and h_{1} are both being trained as mentioned in lines 164-173\n- ALPS depends on the existence of consistent hypotheses on the relevant subsets of the data, which might not always be the case.\n- Line 203: Is the notation used for list?\n\nSummary:\nLargely, I think this paper is very well written in that it develops the delivery of its results very well in the introduction and that it explains the workings of the algorithm in a logical order. They provide an astounding amount of experiments/datasets. Hence, I would recommend that this paper be accepted for these reasons, on top of the fact that it provides the empirical edge to other similar AL works for online binary classification. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors state their work does not have any negative societal impact. The limitations discussed are mainly in the theory. I think another point worth discussing is how this approach can be used in a batch setting and for DNNs.", "review_text": "", "extra_scores": {"ethical_concerns": "Not applicable", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 - 4 hours"}, "extra_text": {}}, {"review_id": "SfCaCEscRie", "reviewer": "Reviewer_TknT", "summary": "This paper focuses on stream-based (online) active learning for training classifiers in the binary classification setting. In particular, the authors propose a strategy, the so-called ALPS*, that trains classifiers by optimizing a surrogate loss over both the labeled instances and sequentially predicted data points by the learner. Theoretical guarantees on label complexity and error of the returned model are provided, and are shown to be competitive with the existing bounds. A set of experiments are conducted on datasets using multi-layer perceptrons as classification models, where the performance of ALPS is illustrated to have good performance with small labeling cost.\n\n\n*Actively Learning over Pseudo-labels for Surrogate losses", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "-This work uses some existing techniques such as importance weighting, margin based functions in their building of final algorithm. The intuition is provided to understand the role of each component, for instance, how importance weighting helps with reducing the noise in hypothetical labels through requester functions. It is also mentioned by the authors in the paper that the proposed method is an extension of [1] to surrogate loss functions. With differences identified, the final methodology is sufficiently original in my assessment.\n\n-The theoretical results on label complexity as well as the excessive risk of returned hypothesis (over the risk of best one in the hypothesis class) are competitive, although one may argue with certain assumptions at times such as access to a large unlabeled data pool (as in, once it is the case, there already exist several competitive pool-based methods over the online approaches, which makes prediction on the pool and measure disagreement among all pool examples). Overall, together with its empirical performance, the contributions seem adequately significant.\n\n-The paper is well written and clear.\n\n-My main argument would be the experiments. Namely,\\\n--I find the experimental setting limited. That is, if the focus is active learning hence reducing the number of label requests, then I believe a better comparison would be where each model is restricted to the same labeling budget throughout the entire stream. For instance, the query probability in the IWAL approach can be linearly scaled with a constant such that it queries the same amount of labels with ALPS by the time n rounds end, then illustrating the performance of methods over the rounds would be very informative. Often times, performance may change only a little after a certain amount of requests, hence it could help to see how they compare when they are restricted to limited amount of queries. As a note, I think passive learning in active learning literature refers to _random sampling_ than querying all labels (in this paper, it would correspond to $p_n$ being fixed at each round where $Q_n\\sim Ber(p_n)$) throughout the stream, similar to label efficient prediction in online learning. As trivial as it may sound, the passive learning is shown to be very robust in the existence of noise studied in the paper. I recommend conducting experiments in which proposed approach is compared to the passive learning baseline in terms of its robustness.\\\n--The model space could be extended further than multi layer perceptrons.\\\n--There are other approaches that can be adapted/designed-for online setting [2,3] that uses disagreement among the classifiers (through measures like entropy). It would have been informative to see how ALPS performs compared to those approaches that are generally good.\n\n\n\n[1] S. Dasgupta, D. Hsu, and C. Monteleoni. A general agnostic active learning algorithm. In Proceedings of NeurIPS, pages 353—360, 2008\\\n[2] Ido Dagan and Sean P. Engelson. Committee-based sampling for training probabilistic classifiers. In Machine Learning Proceedings 1995, pages 150–157. Elsevier, 1995\\\n[3] Burr Settles. Active learning literature survey. Technical report, University of Wisconsin-Madison Department of Computer Sciences, 2009.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No discussion of societal impact, limitations on the theoretical assumptions have been addressed.", "review_text": "", "extra_scores": {"ethical_concerns": "To my assessment, I do not see any ethical concerns within this work.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "RDtYMj27uf", "reviewer": "Reviewer_AgoF", "summary": "This paper presents Actively Learning over Pseudo-Labels for Surrogate Losses (ALPS), an active learning algorithm for binary classification with surrogate losses in the streaming setting. The main idea is to generate pseudo-labels for points whose labels are not requested and train on the union of data points with ground-truth labels and those with pseudo-labels. Since the pseudo-labels may not be accurate, the authors propose requestor functions that have a final say in whether a pseudo-label is used, and in effect, enable control over the noise generated by erroneous pseudo-labeling. Under an assumption involving the requestor function class, the authors prove bounds on the generalization error and label complexity of ALPS that are roughly on the same order of prior work (e.g., IWAL). ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n\n- The paper is generally very well-written and organized, with a clear exposition.\n\n- Good coverage of related work (Sec. 1) and comparison of the proposed method to prior approaches. I also appreciate the discussion concerning the reduction of ALPS to DHM under certain conditions (Lines 107-113), which to me highlights the generality of the approach.\n\n- I found the ideas of requestor functions and the definition of the version space as a function of both the requestor function and hypothesis class to be interesting and novel. The authors were also forthright about the relation of requestor functions to similar ideas like abstention functions from prior work.\n\n- At a high level, the theoretical analysis of the generalization error and label complexity seems sound to me. I also think the relaxed assumption (Assumption 2) is relatively mild in the context of, for example, deep learning due to the high-confidence predictions that are typically produced.\n\n- The authors present compelling empirical evaluations on a wide variety of data sets and compare to IWAL and instantiations of a margin-based algorithm. \n\n\nWeaknesses\n\t\n- Relation to heuristic approaches: given that the primary appeal of the algorithm seems to be its practical effectiveness compared to prior work, e.g., IWAL (which has roughly the same guarantees), can anything be said about the performance of ALPS relative to SOTA active learning approaches like BADGE (which is actually cited in the paper as [1])? Although experimental comparisons would be best (the code for BADGE is publicly available [1]), even a qualitative discussion would be insightful.\n\n- The method seems to work only for binary classification tasks. Can it be extended to multi-class classification?\n\n- This is mostly a stylistic concern, but the introduction is quite long and the full extent of the contributions of the paper are not made clear until (roughly) page 3. I wonder whether partitioning the introduction section into two sections (intro and related work) or adding at least one subsection in the introduction for related work would improve the exposition.\n\n\n[1] https://github.com/JordanAsh/badge ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "9P9UOHFHVXc", "reviewer": "Reviewer_nx35", "summary": "This paper studies the problem of online active learning for classification. In order to learn a classification algorithm, the paper proposes to employ surrogate loss function. The error of the proposed method is analyzed and some empirical results are presented.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper focuses on a problem that has been studied extensively. However, I think the contribution of this work relevant to prior works is not clear. Firstly, the authors does not explain that whether considering surrogate loss function results in obtaining tighter bound for error or not. In fact, the paper makes two additional assumptions compared to existing algorithms such as DHM (as it is called in the paper). Thus, it is expected that under these two assumptions  a tighter regret can be obtained. Otherwise, the error bound of the proposed algorithm is not tighter than existing works under two additional assumptions. This means that the paper does not make a significant contribution compared with existing works. Therefore, more discussion on error bounds and comparison with error bounds of other algorithms is required. Also there are two minor comments. 1- It seems that the proposed algorithm needs to store previously observed data samples while one of the reasons that online learning algorithms may be used is that data cannot be stored in batch. Thus, the proposed algorithm cannot be leveraged in these cases. Hence, this can be account as a limitation of the proposed algorithm. 2- In the theorem 1, it is stated that the inequality holds with probability at least $1-\\delta$. However, there is not any $\\delta$ in the inequality. It is highly recommended presenting the upper bound of error in theorem 1 using some terms which include $\\delta$.\n\n==============Review Update===============\n\nThanks the authors for the rebuttal. The authors' responses addressed most of my concerns. I think revisions that authors want to make will improve the paper. I am happy to increase my score. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss some of limitations in their work. Also they can add that their proposed algorithm needs storing observed data samples to make decision.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a fresh approach to active learning with non zero-one losses. The proposed algorithm has theoretical guarantees that are competitive with existing works, while also performing in practice better than existing practical techniques, in a large set of experiments. This double advantage is of significant value to the advancement of the field. Moreover, the approach includes fresh ideas that could open up new avenues of investigation. Some reviewers have suggested additional experiments. We encourage the authors to add those to their final version.

Decision: Accept (Spotlight)