Learning with Labeling Induced Abstentions
Authors: Kareem Amin
Giulia DeSalvo
Afshin Rostamizadeh
Venue: NeurIPS 2021 Poster (2021)
Keywords: active learning
abstention learning
labeling

Abstract: Consider a setting where we wish to automate an expensive task with a machine learning algorithm using a limited labeling resource. In such settings, examples routed for labeling are often out of scope for the machine learning algorithm. For example, in a spam detection setting, human reviewers not only provide labeled data but are such high-quality detectors of spam that examples routed to them no longer require machine evaluation. As a consequence, the distribution of examples routed to the machine is intimately tied to the process generating labels. We introduce a formalization of this setting, and give an algorithm that simultaneously learns a model and decides when to request a label by leveraging ideas from both the abstention and active learning literatures. We prove an upper bound on the algorithm's label complexity and a matching lower bound for any algorithm in this setting. We conduct a thorough set of experiments including an ablation study to test different components of our algorithm. We demonstrate the effectiveness of an efficient version of our algorithm over margin sampling on a variety of datasets. 

Learning with Labeling Induced Abstentions
Kareem Amin Google Research New York, NY kamin@google,com com
Giulia DeSalvo Google Research New York, NY ginliad@google.com com
Afshin Rostamizadeh Google Research New York, NY rostami@google.co
Abstract
Consider setting where we wish to automate expensive task with machine learning algorithm using a limited labeling resource. such settings, examples routed for labeling are often out of scope for the machine learning algorithm. For example, in a spam detection setting, human reviewers not only provide labeled data but are such high-qualin detectors of spam that examples routed to them no longer require machine evaluation. As a consequence, the distribution of examples routed to the machine is intimately tied to the process generating labels. We introduce formalization of this setting, and give an algorithm that simultaneously learns model and decides when to request label by leveraging ideas from both the abstention and active learning literatures. We prove an upper bound on the algorithm's label complexity and matching lower bound for any algorithm in this setting. We conduct thorough set of experiments including an ablation study to test different components of algorithm. We demonstrate the effectiveness of an efficient version of our algorithm over margin sampling on a variety of datasets.
Introduction
In this paper, we consider system that relies on automated predictions made by machine learning model. We assume this system has limited budget for requesting ground -ruth labels (e.g. from domain expert). In practice, such request can be used, among other purposes, to gather additional training data for the machine learning model. If the system asks for label for an example, then no longer needs the model's prediction for that particular example. Thus, the pattern of label queries effectively defines the distribution that the model will learn with and predict on.
Take for example a large-scale video-hosting website. The website wants to automatically detect videos that violate its community guidelines. In order acquire labels for this task, some of these videos are evaluated by finite pool of human reviewers. There are two consequences of this evaluation. Firstly, the reviewer provides training label for the model. Secondly, the human intervention makes it so that the machine learning algorithm is no longer tasked with making predictions on these examples. As result, the goal is then optimize the the model's performance the domain where it will be executed.
We take the perspective of system designer who wants to understand (and optimize for) the performance of the automated system on the examples that will be asked to evaluate. Let r X (0, 1) be a rule governing whether the system requests label for x X. Let h X R be hypothesis describing the automated system. We seek to minimize E[L(h(x); y) r(x) OJ. where L loss function. We can think of this setting as combining the objective studied in abstention
learning (minimizing (LL(h(x), y) r(z) = 0)) with the feedback model studied in active learning (labels are only available when r(z) 1). We introduce new framework. which we call dual purpose learning framework, that combines these elements.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

We first analyze the proper dual purpose labeling framework in an online setting, which proceeds as follows. At the start of each round t, the learner selects both a requester function Ty from some class Ry, where p is an upper bound on the request-rate of functions in this class, and a hypothesis hy from some class H using all the feedback available from the past. The learner's 's expected loss = 0). The function Ty also determines the feedback available to the algorithm. If (z) = I, the learner observes (a, y), which was drawn i.i.d. from an unknown distribution, and otherwise, only is revealed and is censored. The goal of the learner is to compete with the optimal choice of hypothesis and requester by minimizing the excess loss LuR r2) = (()(h,(z)) v) ra(a)) 0] (he ((b",,"))""*"""""""""""""""""">) R, E[L(h" (x),
on this round is given by E (x), v) ry(2x)
| (2) = 0].
Our first main result is the surprising fact that, under mild assumptions, bounds on the excess loss that match the O(L/Vt) generalization rates of full-feedback passive learning are not possible in the proper dual purpose labeling framework. This lower bound also suggests relaxation of the proper dual purpose labeling framework, which we call improper dual purpose labeling. In the improper setting, the learner is still interested in learning æ4, r2 that minimize Lu. However, the learner allowed to request labels using a more powerful requester class than R₂ during training. As in classical PAC-learnig results, improper learning allows the circumvention of the impossibility result.
As practical matter, the improper setting is useful when the system designer is willing to spend more resources during training. In our motivating example, the designer of the abuse-detection system might be willing to implement a more complicated system during training, which might include larger budget (in dollars or man-power) for human intervention. However, after time horizon T, training stops, and the designer commits to some hv, FT for FT R.. From then on, examples satisfyng rT (z) = O are routed to lT, and thus, we wish to characterize LH.R, (hT, PT).
In the improper setting, [Beygelzimer et al.] 2009). can be adapted to our setting into an algorithm which we call DPL-IWAL. Since our objective is no longer an expectation of some loss function, but rather, the conditional expectation evaluated on the event that r(æ) = O, IWAL's standard analysis does not apply. A key technical hurdle is proving that estimates of this conditional loss concentrate the right rate in order to attain generalization guarantees for the pair (h,r) r) returned by DPL-IWAL. We show that over time horizon T, DPLL-WAL algorithm requests ((pp + 7)T) examples where 1) (i) R,, (b(((((z),)) v) r(x)= = 0j is the optimum value of our objective. At the same time our main lower bound demonstrates that 2((e + T)) requests are in fact necessary to compete with the best policy in H x R.p
demonstrate that IWAL, algorithm from the active learning literature
Finally, we conduct a thorough exploration of these techniques on a number of datasets. We first undertake an ablation study, using finite hypothesis class, showing that DPL-IWAL outperforms baselines that either ignore the active learning or abstention learning aspects of the problem. DPL- IWAL is not computationally efficient to implement since just like IWAL, it maintains version space, that is a set of candidate hypotheses, which is non-trivial to optimize over in general. We therefore also conduct number of experiments with efficient heuristic inspired by our results using continuous hy hypothesis classes, outperforming natural baselines including margin sampling Lewis and Gale 1994 Balcan al., 2007], which admits state-of-the-art performance for active learning problems in practice (Yang and Loog 2016 Mussmann and Liang 2018 Chuang et al.
2019
1.1
Related Work
Our setting encompasses an objective considered in abstention learning (sometimes called selective classification), where the learner controls its evaluation region, that is the region of the domain where the learner is evaluated, by abstaining on the complement. In our setting, the evaluation region is where the learner does not request label and the complementing abstention region is where the learner makes a request. At the same time, our setting considers the feedback mechanism from active learning. These are tied in a specific way in our framework: feedback is only available on the abstention (i.e. requesting) region and no information is revealed about the evaluation region. Neither an abstention algorithm nor a standard active learning algorithm would work in our setting and the algorithms in these settings can lead to incorrect solutions (see Appendix C Nevertheless, we survey some of the relevant literature.
2

---

Learning with abstention was first studied by Chow 1957, 1970 for specific practical applications. Subsequently, several authors analyzed algorihmms Barllet and Wegkamp 2008 Grandvalet et al.) 2008 Yuan and Wegkamp 2010, Yuang and Wegkamp 2011] for this setting with an emphasis on developing margin-based based rules for abstention. Along different line of work, EE- Yaniy and Wiener (200 2011 IJ analyze the theoretical trade-off between the coverage of an abstention function and classifier's 's performance when not abstaining. All these works share in common the assumption that the learner has offline access to fully labeled samples, unlike the setting considered in this work.
more recent line of work Cortes et al. 2016a b 2018 considers setting where the algorithms learn over two classes of functions, a hypothesis class and an abstention class. These work either assume full feedback is always available (e.g. Cortes et al. (2016a b)), or like in Cortes et al. 2018), the feedback is only available in the evaluation region, which is the exact opposite feedback mechanism than that of our setting since we receive feedhack in the abstention region. Similarly, (Shekhar et al.
[202T] consider setting where feedback is always available.
In the active learning literature, several authors focus on analyzing margin- based active learning which requests the labels for points close to a learned model classification surface [Dasgupta et al.
2005
Balcan al., 2007| [alcan and Long 2013 Awasthi et al. 2014 2013 Zhang 2018 Huang
Ct al. 2019 Zhang el al. 2020J. Other algorithms admit generalization guarantees on the same order
as passive learning while proving that their algorithm's label complexity, i.e. the number of points requested during learning, is bounded by a favorable rate. [Beyellzimer et al.] [2009] derived an algorithm, called IWAL, for general loss functions with strong theoretical guarantees. We wish to use this algorithm for our setting with the abstention learning objective. However, the loss function we consider is in fact conditional expectation evaluated on an event, which is not amenable to standard IWAL. Our analysis and corresponding algorithm, DPL-IWAL, describes how to apply IWAL to such a setting.
Finally, ideas from the abstention framework have been applied to the active learning previously. Zhang and Chaudhuri [2014] used confidence-based predictors subroutine of an active learning algorithm. EI- Yaniv and Wiener [2012) applied an abstention strategy from EI- Yaniv and Wiener [2010] to the CAL algorithm of Cohn et al. (1994) proving theoretical guarantees, but only under specific model and distributional assumptions, which we do not make in our setting.
2 Setting and Preliminaries
In the dual purpose labeling framework, learner is given hypothesis class H with finite VC- dimension d, and a class of deterministic requester functions R C (X - {0, 1)). Nature fixes a distribution D over X x V. unknown the learner. Given the marginal over X, and p 0, we denote Rp C R as the subset of R with bounded request-rate Ex [r() 1] < for all r E R.p E, [zxz) 1] can be well estimated using unlabeled data, which generally readily available, allowing a bound on request-rate to be enforced in practice.
The interaction between the learner and nature proceeds through a sequence of rounds t. The learner first selects (h,, r2) E H. x R, as a function of the past. Nature then draws an independent sample (Ma,ye) from D, where H, is revealed to the learner. If (1xe) = 1, the learner additionally observes yt, but the performance of h, is not evaluated. If r2 (xz) = O, the learner does not observe ye, but the performance of h2 is evaluated. Thus, the choice of r, serves dual purposes: it determines whether the algorithm receives feedback, and whether its performance will be evaluated.
Formalizing this further, we suppose that the learner is given loss function L : x >' - R. The learner seeks to output h2 that generalizes well on the region where T, dictates that ht should be evaluated. We therefore seek to bound the (conditional) excess loss CH,R, (hi, = E (h) v)
(x() = 0] - inf(ge.. > R, [[ (x)) y) (x) = 0). In particular we seek O(1/ bounds on Lu.R, (he, re), matching the generalization rate of full-feedback passive learning.
The conditional loss of the best pair in H. x R, plays an important role in our lower bounds, and so it is useful to define // = (rr"
Ez,gy [LW (x), r* (xx = -].
Finally, we call this the proper dual purpose framework since the algorithm is attempting to generalize well with respect to the class H x R, and labels are generated according to functions in Rp. In the
3

---

subsequent section, we will see that ((1/vt) bounds on CH.R, (he, re) are impossible in general. This motivates the improper dual purpose framework as introduced in the following section.
3 Lower Bound
In this section, we present a lower bound stating that is impossible for any algorithm to achieve an O1I/VI) generalization rate in the proper dual purpose setting. Thus, we here introduce the notion of improper algorithms. On each round t, an improper algorithm selects hy E H and an R X - {0. 1) that is unconstrained for the purposes of showing a lower bound (e.g. R₂ is not necessarily in the set Rp). As in the proper setting, label requests are tied to the evaluation region. That is, the algorithm sees yr i.f.f. (x,),) = 1, and wishes to minimize CH.R. (he, Rt). Notice that C is still defined with respect to the reference class R., and that the proper setting is special case of the improper setting where R₂ is equal to an Tt E Rp- The lower bound below shows that any algorithm with the desired generalization rate must satisfy + - (()) > p. Thus, since E[r(x)] I p for every r E Ry. no proper algorithm can attain the desired rate.
We prove a bound that holds for almost any possible classes of functions H. R. with some restrictions on R. We say that R separates X' if given any finite set of examples in 2g. ................................ :.,. E Xx there exists a point è outside this finite set of points and a requester in R such r(ă) r(z,)) 0. This condition is much stronger than is necessary for the lower bound, but is already satisfied by simple classes such as when R contains linear separators and X' is a ball in any dimension 2 2, and becomes easier to satisfy as R. becomes more complex. We need a weaker condition that requires only the separation property hold for some set shattered by H.
while r(2o) =
Definition 1. R separates X' with respect H if d VCD(H), and there exists a set of d examples To.- Id-1 shattered by H. à E X, and r E R such that r(ē) = and r(zo) = (en))) r(.-)( = 0.
We first describe a distribution that follows the basic construction used to demonstrate lower bounds for pure active learning (Beygelzimer al., 2009). We then augment this distribution include region of mass p that contains random noise. Intuitively, one can think of an algorithm as requesting label either to solve the active learning problem to avoid loss on examples that it is uncertain on in the region of mass p. We argue that the optimal algorithm, when not solving the active learning problem, spends pil' labels requesting on the random noise.
While this is the basic idea, the proof needs to preclude the possibility that an algorithm with a suboptimal prediction h benefits from requesting labels outside the region of mass p purely for the purpose of avoiding loss (and not to solve the active learning problem). An algorithm can also request labels at rate greater than o any given round with the hope of decreasing its overall label complexity over T rounds. The proof shows that neither of these strategies benefits an algorithm enough to deviate from the optimal strategy outlined in the previous paragraph.
Definition 2.
Fix any p 2 We say that a round t is a failed round if the algorithm selects requesting strategy R² : & > {0,1}, and hypothesis ha E H satisfying B[[((h((z).v) R.(x) =
0 2 min(,.))EXXX B[I(h(z),)) r(x) = 0] +0+++++++
dn
As practical matter, we will also require that improper algorithm outputs model (hr, rT) H x RRp at the end of its time horizon, where FT comes from the reference class. This paves the way for algorithms discussed in the subsequent sections which are applicable in systems that are able to tolerate a higher labeling overhead during finite training horizon, but eventually need to converge on a model with request rate p. Crucially, the lower bound establishes the minimum additional overhead during training as 17 (defined in Section D which is matched by our upper bounds.
Theorem 1.
Let L(h(z), y) = 1[yh(x) < 0] be the misclassification loss. Given R that separates X with respect to H with = VCD(H). let R2 C. R consist of requesters with bounded request-
rate P. For any n7 < 1/4, p < 1/2, there exists a distribution on X x {-1,1} such that min,,,))EHXRR, (L)() 9) r(x) 0].
Furthermore, there exists a sufficiently large T 2 such that with probability at least 1/2 any algorithm that, (A) outputs (IT, rT) E &Hx HXRp, such that (b)(((r (x(x) = 0] S n / dnn and (B) suffers no more than T T/2 failed rounds, requires that: EE
E C R.] 2 2((n+ p)T).

---

Algorithm DPL-IWAL Algorithm
Require: Max iteration T > 0, Vi = H Rp, to be the first time L. such that / 2 16 log(1/8)
for 1 E [1, [o] do
Observe 24 in order to construct estimates
- E.= l[r(x,) = 0]
for E [to + 1, do
Te) f- argmin I (h,
Receive
if (x+)) = then Request label !/t
pr(x))+ -min (1
L(h(n vo (2 (r))) (2))=0)
max max (hhr)) NEY a Ex 1[((.))=) Ein [=,()=))=
g: Bernuuli(pp))
gt = then Request or re-use label
Ve+ < ((h,r) eV: (h, r) S min(,,)ev, (h, r) Åd} if rf;) = 0 A = 0 then Predict label using sgn (bz(1)))
Return: (rr,
The above theorem states that an algorithm must request the labels of at least (2(1 + p) examples (in expectation) if we require that the pair returned by the algorithm generalizes at rate approximating that of standard supervised learning. This then directly implies that R, must be selected outside of the class R, since this class only contains functions with requesting rate of most p. resulting in label complexity at most O(pT)) in expectation. All proofs can be found in Appendix A
Although we state the lower bound for classification loss, can be extended any loss function where mispredicting the sign of an example, yh(r) < O. implies L(h(z),, y) 2 C' for some constant C. This is true for the logistic, hinge, squared, and absolute losses.
4 Dual Purpose Labeling Algorithm
In this section, we present our algorithm, DPL-IWAL (see Algorithm I for the pseudo-code), in the improper dual purpose framework. At a high level. DPL-IWAL finds the pair (h,r) E H R, that minimizes the conditional loss, [h(.((())) [r(x) = 0). i.e. the expected loss of h conditioned on the event that the label is not requested by r. Intuitively, the best pair (h, r) requests the label of the point whenever the prediction of sgn(h (z)) is likely to be incorrect.
To find such a pair, at each round I, the algorithm first constructs an importance weighted estimate, L, (h, r). of (h)((()), 3) (z()= = 0] by using the fewest number of labeled points as possible and then chooses the pair (he, r2) that minimizes L (h. r). Ideally, the importance weighted estimates L, (h, r) could be constructed from the set of points whose labels have been requested by ri...., but these sets of points are non-trivially biased sample of the underlying distribution. Moreover, these points could reside in regions of the space that see this more clearly, consider a simple case when R, is contains just one function and the algorithm then simply finding the argmin (h)(((x), [z() = O). The points the r functions request the label for, meaning points where r(æ) = 1, do not reveal any information necessary to estimate (h(x)) v)(r(x) 0] for h E H. Thus, the algorithm must label other regions the space. Below, we describe how the algorithm uses subset of the points requested by the E R, in conjunction with some additional carefully chosen points, via a function qe outside Rp, construct unbiased estimators, (r(h,r) r). This fact thus makes DPL-IWAL an improper dual purpose algorithm.
useful for caleulating [[[((((x), y) rrx)) 0). To
Similarly to IWAL [eeyellimer et al. 2009], , the DPL-IWAL algorithm constructs importance weighted estimate, but instead of estimating the expected loss as is done in IWAL, we craft an estimate of the conditional losses for tort: > tu.
I+ ((h(z.).
L.(h.r) [ l0
Σ
P.(xx)
- Σ ([((x))
s
where a coin ys E {0, 1) is flipped with a bias probability Ps (xx)) and where ln is the first time t such that > 16 log( Note that for the first s [1, to). we simply observe the features
5

---

Is in order to construct - Ex= ( = 0] that are non-zero with high probability since these are needed in definition of the denominator of Le r). Ignoring the and (x.,) for now, the numerator T-to- Ex= ((h(z,). (r)a) = 0J is a measure of the joint expectation Oj] while the denominator contains running averages of the Efr(x) OJ. Roughly speaking. by considering the ratio of these two terms, we estimate the conditional expected loss, (()((())) ())(()) = 0J = (L [)1
E[L(h(x), v))
F(((z)
The algorithm maintains a version space, V,, as defined in Algorithm [ which it reduces at each round. We prove that it suffices to use a slack term Á, = ( log(1/6)). in order to ensure with high probability that (h", r") remain within the version space as it shrinks. The Ō(.) hides constants and log(4 x RRl) factors; see the appendix for exact constants. In order to reduce the number of labeled points used construct the
weighted estimates, the probability of requesting a point pt is defined by the (estimated) conditional loss difference between pairs of functions in this shrinking set V₁. Given the above, the algorithm's overall requesting rule, Re, is thus defined by the following condition: (x,) = 1 if and only if (24) = 1 q: = =1 where E Rp and q & Rp.
5 Generalization and Label Complexity Guarantees
In this section, we present a series of theoretical guarantees that analyze the performance of our approach as compared to different baselines as well as prove an upper bound on the expected number of label requests by the DPL-IWAL algorithm.
In our framework, we seek to select hypothesis ha which incurs minimal loss whenever label request not made. Below, we prove an upper bound on this type of loss that is in terms of the best pair of functions, (h², ,r*)= (r
(L)()(z), r))r(z) 0].
Theorem 2. Given any p < for any ō > O, with probability at least 1 - for all t 2 16 (olo(31//)) ([L(h.(z).
0] s (22 vz)) oJ + ((L(L)))
This guarantee states that the pair (he,re) chosen by the algorithm is converging to the best pair (h",r") as a function of the time with respect to the conditional loss. The assumption i > 16 10g(31/)) is mild condition, for example, if 0.0001 we then require > 104. Also, in most standard applications, only a small fraction of examples can be labeled and it is natural to assume that p 1. Nevertheless, this assumption can be reduced by increasing the constraint on in the bound.
Overall, the theoretical analysis, which is given in Appendix B departs from standard derivations since we need to carefully deal with conditional losses and the constructed estimates, (h, r). More concretely, we first must ensure that the denominator of the estimate Lh, r) is non-zero with high probability as otherwise the estimate would not be well defined. To do so, we start the labeling process of our algorithm only after to examples have been observed. After to examples have been observed and using the fact that B/r(x) = 0) > 1- P. we can then prove that the condition --1 E [m(xx)) = 0] > 0 holds with high probability (Lemma 1). Then, in order to apply Azuma's inequality on conditional losses, we need to prove that (.,
is bounded Σ (((()))==0) by favorable constant despite the variable denominator term (Lemma Azuma's inequality implies that the estimates are converging to E[L, (h, r)]. but this is not enough since we want to prove guarantees in terms of ())()()), (x) = 0]. Thus, using a series of concentration inequalities, we prove that expected value of the estimate, (h, r)). converges to the expected conditional loss, (LL()()), ())r()) 0] at the desired rate (see proof of Theorem 2
Next, we compare the quality of the predictions of our approach to that of simply predicting according to the best-in-class as measured by the non-conditional loss, hs argmin (h((()( v)]. This comparison quantifies the potential benefits of our framework as compared to that of supervised learning since h2 is the hypothesis that algorithm in the supervised setting is attempting to learn
In the next corollary, we consider the never-requester function, To, that is (rr( = 0) = 1 for all E X. The never-requester is in R, for any value of p > 0. The never-requester trivially does not increase the label complexity and since it's a single function, it also does not discernibly augment the complexity of class, R,, and so it can be included in R2 at effectively no cost.

---

Corollary 1. Given any < 2. for any > 0, with probability at least 1 - 6, for all 2 16 16lo((3//0) (I, v))r,) 0J - E[L(h)()),)) + (1/()/) log(1/0)), where 7 (1)) (x) 0] - (ha())))))))))))))))))))())))[ v)]- Furthermore, ifr. R,, then y S 0.
The above corollary states the predictions of the chosen function h2 when not requesting admit strictly fewer mistakes as compared to the predictions of hy, the best-in-class in H. whenever y クー - (0(((11))) log)) The value y characterizes the difference between the best-in-class in our setting versus the best-in-class in the supervised learning. The more negative this term is, the fewer number of mistakes are made. In an empirical study in Appendix D we show that typically ? is significantly smaller than O.
To derive label complexity guarantees, we define a disagreement coefficient for conditional losses, directly derived from the coefficient definitions in Henneke [2007]. Beygelzimer et al. (209).
Let r((,,r), (h',r')
B|| (()
(.hl)) ( be a measure of the dis-
2(r())=
3/ (+)=
tance between two pairs (h, and r'). Based on this metric, we define the ball around
the best pair (h", r") as follows: B(h", ,r,, = {(h, r) E H x Rp -(((,,)) r), (h", "0,,r" rr)) I
A}. The disagreement coefficient is the infimum value of A > 0 such that for all A 2 0:
E (arr maxy
- AA. The next theo- rem bounds the expected number of points requested needed to construct the estimates, L, r) in terms of the coefficient 0.
L(h(z) []r(=)=U
L(k (=)))))))"""""=)===)) (=)=
Theorem 3. Given any < for all 8 > O, with probability at least 1 - 6, ΣT Elp,(1)) (x.)) =
Ö(OnT + (VT)), where 0 is the disagreement coefficient.
Since the labeling rate of r. is at most p. the label complexity of the DPL-IWAL algorithm is then given
by (x,) 1] 1] (ar.)) = (((n++))T+++TT
Assume that (h,, v) (x
of S S ([L(he(z), (LL( (x) ) = 0]: intuitively, this implies using qe in addition to r; to make requests
helps reduce our conditional loss and it holds in practice as shown by our experiments in Appendix D
Then it follows, by Theorem 2 that (1) 3) R₂(x) 0J S n + Ö( (1/t) log(1/))), i.e. with high probability failed rounds do not occur. Thus, in this case, DPL-IWAL exhibits an upper
bound on the label complexity that matches the lower bound stated in the previous section, apart for
T() terms, namely VT. An even sharper bound for the o(T) term is possible, using analysis similar to that of the EIWAL algorithm in Cortes et al. 2019]. resulting in rate of VTT.
The analysis that proves the label complexity bound carefully deals with the denominator term of the estimates of the conditional loss as well as the fact that we are working with two function classes. Similarly to the generalization bound analysis, we first prove that the denominator term is well behaved and is not too far form its mean. Then, we leverage the disagreement coefficient 0 and shrinking version space over the two classes.
In this paper, we analyzed the scenario where the requesting functions r; E R2 are constrained to request at most times and minimize the conditional loss over this set of requesters. One could instead consider a Lagrangian relaxation of this constraint and pay a fixed cost c for each request. That is, consider the cost-based loss defined by I
y) cl+(z)=1- Both of these loss views are important and in fact have been analyzed in the abstention setting (e.g., see El- Yaniv and Wiener (2010] for conditional loss and see Cortes al. [2016a] for cost-based loss). Despite focusing on conditional loss over constrained requester functions, the theory and algorithms in this paper can be extended the cost-based loss. In particular, for the algorithm not to ineur too many mistakes during training and to return a pair of function that generalized well, the algorithm must select RG outside of the class of requesters. The version of DPL-IWAL for cost-based loss will thus require requesting according to both ar and rt.
Empirical Investigation
We start our empirical investigation by corroborating the theoretical insights made in the previous sections with an ablation study of DPL-IWAL. Since IWAL. needs to solve a computationally intractable constrained optimization problem over its version space, which is only made more challenging in our setting by the joint optimization over H. x Rp. we use finite classes for these initial
7

---

shutle
1:00
75
DPL-Simplified Algorithm
50
Require: Max iteration T > 0, classes H. x R2 for L [1,T] do he f argmin E Qe (eh( (s))
- argmin, E ((hr((
ereer
0.08
0.00
Σy 1(((a,))=0)
0.04
Receive if (3ra)) 1 then q: 1, request label else qi 0, predict label using sg;(h( Return: (r)
0.02
0.04
2000
4 pointa processed
+
DPL
uniform
uniform 4:
+
fully unitomm
Figure 1: On the left, the number of online mistakes made while processing a stream of data and the held-out conditional loss on non-requested points made by DPL-IWAL and baselines comparators. The plots show the mean and standard deviation over 10 trials. On the right, the pseudo-code of DPI-Siiplifiedd Algorithm.
experiments. Then, we turn to more practical algorithm inspired by the DPL-IWAL algorithm, but that leverages readily available optimization routines and empirically effective heuristics.
Ablation Study: We compare the performance of DPL-IWAL against baselines which ignore either the active learning and/or the abstention aspects of the dual purpose labeling, in order to demonstrate that indeed both aspects are necessary. To do so, compare our algorithm to several variants, defined as follows. The fully uniform baseline simply decides to request a label using a random biased coin-flip independent of the example, thereby mimicking standard passive supervised learning. The uniform r baseline uses the DPL.-WAL algorithm in conjunction with trivial requester class that fixes its output uniformly at random, independent of the input 2,. The uniform qe baseline similar to DPLLIWAL, with outcomes determined by coin- flips with a fixed bias, independent of 2t.
For this experiment, define set of requester regions near the margin of the classification surface, each covering a mass of the overall distribution. Specifically, for any set of real-valued hypotheses set H. where the classification of point made by h H. is defined as sgn(h(z)), we define margin-based requester function class as: Rp, {rx(x) > 1 [[x(r)] S (Dx)]: h H), where Dx is marginal distribution on A' and ("xx) is the largest threshold value that satisfies ED,, (x) S p. Note, the Th.p threshold can be estimated using unlabeled data.
We test six publicly available datasets [Chang and Lin and for each, we use linear logistic regression models trained using the Python scikit-learn library. For all datasets, we construct finite hypothesis class H and a matching finite margin-based requester set Rp,H-. We then stream unlabeled examples to each algorithm by sampling without replacement from training split. The process is repeated 10 times, using a different random train/test split for each trial. For details, see Appendix D
In Figure (left), compare each method using two metrics. First, we consider the number of incorrect predictions (i.e. "online mistakes") that the model makes while processing the stream of unlabeled training data, where label-requests are spared mistakes. Second, we consider the conditional loss of the currently selected pair (h,, re) by measuring the average misclassification loss on non-requested points using held-out test split. See Appendix D for our results on all datasets, which all show a similar pattern.
Overall these results show that our DPL-IWAL algorithm, with both non-trivial sampling function qe and requesting function rt. outperforms all bascline methods. This indicates that both active learning and abstention aspects of DPL-IWAL are necessary since naively applying active learning algorithm without abstention (e.g. uniform r₂) or naively applying an abstention algorithm without active learning (e.g. uniform q:) admit suboptimal results.
DPL-Simplified Algorithm: Here, we consider the DPL-Simplified Algorithm (Figure right) where, the joint optimization problem over H. x Rp is split into two separate optimizations. This piece-wise optimization may not arrive at the same solution as the joint optimization, but we find to be an empirically effective proxy. The first optimization over H is standard learning problem over the currently labeled examples and any off-the-shelf hypothesis class and training algorithm can be used. The second optimization over R2 is still non-trivial to solve. However, the objective
8

---

2000
Online Mistakes
Conditionl Test Emar (8)
dataset
KNN
MAR
MIX
KNN
MAR
MIX
1000
2017
1531
1713 51
0.33
0.44
1.33
acoustic
cifir
1854 1:
904 +: 30
1458
6:19 1 38
52
1418 51
701
+ 26
5.0 = 0.23
9.4 = 0.35
8.1 0.13
5.14
0.09
7.8 0.28
%
Pr/htx) 1jk1
0.5
1.0
ood-ma
644 + 27
360 + 13
329 + 12
3.1 = 0.111
0.06
1.5 0.07
coviype
HIGGS
3471
5862
3365
5800 90
3318
5689 69
35.2 = 0.31
16.6
02.5=0025
1913
17.8
0.20
cod
jenn
654 + 52
420 1 20
310 30
2.2 = 0.28
2.16
0.7 0.14
mnist
1489 1:
1032 1 26
958 1: 50
6.7 0.31
5.1
4.1 0.12
shotle
0.8
0.05
200
skin
61 64
662 110
36 1: 31
0.1 1 0.02
4.0
0.02 1 0.01
100
000
The left side of the table displays the mean and standard deviation over 10 trials of the number of total online mistakes after processing 20,000 examples for each of the requestor strategies (all limited to requesting labels for 20% of examples). The right side of the table shows the mean and standard deviation of the conditional misclassification loss Pr(h(x) # u|r(x) = 0), measured on the test set, for (hr, rr). On the right, histograms show the number of emros made by partially-trained linear hypothesis h as a function of the model confidence for two datasets.
Figure 2:
does provide the intuition that an optimal requester seeks to cover all of classifier h 's mistakes. This suggests an approximate solution, where we train a requester r that seeks to classify the incorrect predictions of a fixed hypothesis fú2 over the set of labeled examples thus far. At the same time, notice that the simplified algorithm fixes ge = re(e)) (and no longer needs to solve IWAL's constrained optimization problem). This makes the requester function responsible for not just sampling regions of the space that H. cannot correctly capture, but also sampling examples that are effective for training.
To cover the regions where the classifier is incorrect, we leverage what we call a KNN-Requester function. In particular, we use scikit-learn's NeeighborsClasssfie
train non-parametric model to predict hypothesis hy's training mistakes. The resulting requester is TKNN, (x) = Pra # g|ær]| < rel. where Pry(h(z) * y/æ) denotes the probability that h makes a mistake according to the KNN model and indicates the classifier's 's threshold Ta has been tuned so that the requester labels approximately p fraction examples. To select points that are effective for training the classifier, we borrow intuition from the simple yet empirically very effective margin (or uncertainty) active learning algorithm, which samples examples that the current model least confident on (i.e., example closest to the decision surface).
This leads us to the Mixture- Mixture-Requester (MIX) function which merges the margin and KNN strategies. Specifically, we uniformly combine the probability score produced by the KNN model underlying TKNN h.p and the margin score derived from (xx) as follows: (x)
1[ Præ(h(r) * y/æ)| (o(h(z)) - 0.5] < Tr.ol, where a is a normalizing function that maps the input into [0, 1]. which in our case is the output of scikit-lcamn's 's predi predict_pree ct_proba method. Thus, this requester seeks to sample points that are both covering mistakes of the classifier as well as sampling
points that are effective for training.
In addition to the above, we evaluate the simpler Margin- Requester to serve as a natural, yet effective baseline: (MAR,AA,p()) (]]o(((=)))000 005) Th.a]. This requester is essentially mimicking the behavior of using uncertainty-based active learning without any regard to the DPL setting.
In the following experiments, the hypothesis class H. is the set of linear models with bounded T--- norm, trained using seikit-leam''s 's LogisticRegres available datasets, all which we cast binary classification problems (see Appendix D for details). We execute a batch variant of DPL-Simplifidd, where at each iteration we process a batch of 5,000 examples, querying 20% of the examples for their labels and making prediction for the rest. Upon the completion of the iteration, we receive the requested labels and update the choice of (h, r). This larger batch size, more closely reflects practical learning settings, where it is impractical to re-train the model after every single label query [Amin et al., 2020). All methods are seeded with 500 randomly sampled initial examples and each experiment is for 10 trials.
implementation, and we use 10 publicly
In Figure 2 we show both the number of online errors incurred during the iterative labeling/training procedure as well as the average conditional misclassification loss of the final (h, r) pair on a test set.

---

In Appendix D we plot the full learning curves in Figure S associated with Figure Overall, MIX very effective, outperforming the baseline methods in 8 out of 10 datasets. To better understand when MIX outperforms the margin-r we present a histogram of errors function the confidence of model trained with a set of 3,500 examples sampled uniformly at random (Figure 2 right). The histogram for the HIGGS dataset, where the margin baseline performs well, shows that most of the errors are highly concentrated around the minimum model certainty region, i.c. where the model prediction score is close to 0.5. In contrast, the histogram for cod-rna, where the DPL-inspired mixture-requester excels, shows that while there are some errors concentrated around the 0.5 threshold, there are also number of errors far away from the model decision boundary.
7 Conclusion
We introduced a new setting which models the relationship between labeling and learning in real systems. We derived lower bound in terms of the abstention-rate of a reference class and the optimum value of our objective. We presented an algorithm DPL-IWAL that admits strong general- ization and label complexity guarantees and more efficient variant, DPL-Simplified. Finally, we reported experiments which corroborate our theoretical findings and demonstrate that our algorithm outperforms natural baselines, including the ubiquitous margin sampling algorithm.
References
Kareem Amin, Corinna Cortes, Giulia DeSalvo, and Afshin Rostamizadeh. Understanding the effects of batching in online active learning, In The 23nd International Conference on Artificial Intelligence and Statistics, 2020.
Pranjal Awasthi,
Balcan, and Philip M. Long. The power of localization for efficiently learning linear separators with noise. In Proceedings of the forty-sixth annual ACM symposium on theory of computing, pages 449 458. ACM, 2014.
Pranjal Awasthi, Maria-FForina Balcan, Nika Haghtalab, and Ruth Urner. Efficient learning of linear separators under bounded noise. In Conference on Learning Theory, pages 167-190, 2015.
Maria-Florina Balcan and Phil M. Long. Active and passive learning of linear separators under log-concave distributions. In Conference on Learning Theory, 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 and Marten Wegkamp. Classification with a reject option using a hinge loss. JMLR, pages 291-307, 2008.
Alina Beygelzimer, Sanjoy Dasgupta, and John Langford. Importance weighted active learning. In Proceedings of the 26th International Conference on Machine Learning, pages 49-56. ACM, 2009.
Chih-Chung Chang and Chih-Jen Lin. Libsvm. iibavttools/dattasett. Accessed: 2021-05-28.
ntu. wttp.ccsiee.tuuee..uuu//////i/ee
C.K. Chow. An optimum character recognition system using decision function. IEEE C., 1957.
C.K. Chow. On optimum recognition error and reject trade-off. IEEE T. C., 1970.
Galen Chuang, Giulia DeSalvo, Lazarus Karydas, Jean-francoll Kagy. Afshin Rostamizadeh, and A Theeraphol. Active learning empirical study. In NeurIPS2019 LIRE Workshop, 2019.
David Cohn, Les Atlas, and Richard Ladner. Improving generalization with active learning. Machine Learning, 15(2):001-221, 1994.
Corinna Cortes, Giulia DeSalvo, and Mchryar Mohri. Learning with rejection. In ALT, pages 67-82. Springer, Heidelberg. Germany, 2016a.
Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri. Boosting with abstention. In NIPS. MIT Press, 2016b.
10

---

Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri. Online learning with abstention. In ICML, 2018.
Corinna Cortes, Giulia DeSalvo, Claudio Gentile, Mehryar Mohri, and Ningshan Zhang. Region- based active learning. In International Conference on Artificial Intelligence and Statistics, 2019.
Ido Dagan and Sean P Engelson. Committee-baseer sampling for training probabilistic classifiers. In Machine Learning Proceedings 1995, pages 150-157. Elsevier, 1995.
Sanjoy Dasgupta, Adam Tauman Kalai, and Claire Monteleoni. Analysis of perceptron-based active learning. In Conference on Learning Theory, pages 249-263. Springer Berlin Heidelberg, 2005,
Sanjoy Dasgupta, Daniel Hsu, and Claire Monteleoni. general agmostic active learning algorithm. In Advances in Neural Information Processing Systems, pages 353-360, 2008.
Ran Yaniv and Yair Wiener. On the foundations of noise-free selective classification. JMLR, 2010.
Ran El- Yaniv and Yair Wiener. Agnostic selective classification. In NIPS, 2011.
Ran Yl-Yaniv and Yair Wiener. Active learning via perfect selective classification. JMLR, 2012.
Yves Grandvalet, Joseph Keshet, Alain Rakotomamonjy, and Stephane Canu. Suppport vector machines with a reject option. In NIPS, 2008
Stephen Henneke. A bound on the label complexity of agnostic active learning. In ICML, 2007.
Boshuang Huang, Sudeep Salgia, and Qing Zhao. Disagreement-basel active learning in online settings. arXiv preprint 190440990099 2019.
David Lewis and William Gale. A sequential algorithm for training text classifiers. Proceedings of SIGIR, 1994.
Stephen Mussmann and Percy Liang. Uncertainty sampling is preconditioned stochastic gradient descent on zero-one loss. In Proceedings of NeurIPS, 2018.
Shubhanshu Shekhar, Mohammad Ghavamzadeh, and Tara Javidi. Active learning for classification with abstention. IEEE Journal on Selected Areas Information Theory, 2021.
Yazhou Yang and Marco Loog. benchmark and comparison of active learning for logistic regression. In arXivpreprint 4rXiv:161.006111 2016.
Ming Yuan and Marten Wegkamp. Classification methods with reject option based on convex risk minimizations. In Journal of Machine Learning Research, 2010.
Ming Yuang and Marten Wegkamp. Support vector machines with a reject option. In Bernoulli, 2011.
Chicheng Zhang. Efficient active learning of sparse halfspaces. In Conference on Learning Theory, 2018.
Chicheng Zhang and Kamalika Chaudhuri. Beyond disagreement-basee agnostic active learning. In Advances in Neural Information Processing Systems, pages 442-450, 2014.
Chicheng Zhang, Jie Shen, and Pranjal Awasthi. Efficient active learning of sparse halfspaces with arbitrary bounded noise. Advances in Neural Information Processing Systems, 33, 2020.


Reviews:
[{"review_id": "t2oS8AXjpAI", "reviewer": "Reviewer_iNDa", "summary": "The paper introduces a formalization of an online learning setup for labeling with human annotators and machine evaluation and gives an algorithm that simultaneously learns a model and decides when to request a label. Authors prove an upper bound on the algorithm’s label complexity and a matching lower bound for any algorithm adapted to this setup. ", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "General Assessment:  The paper is well written and easy to follow. The distinction between proper and improper settings is interesting and the lower bound result for proper setting is novel and relevant. \n\nComments: \n- Empirical comparison to existing approaches in active learning is missing. Are there methods in active learning that can be adapted and compared to the proposed DPL-IWAL algorithm. \n- Is it possible to make proper dual-purpose labeling framework work in an online setting with some distributional/margin assumptions. It would be interesting to see how the lower bound can be avoided in a typical practical scenario?\n ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "o7iRjyGbeW", "reviewer": "Reviewer_vKGw", "summary": "Summary: This paper sets and explores relations between learning and labeling. The article develops a new method requesting labeling combining abstention and active learning. The authors develop a new method and detail their corresponding algorithm DPL-IWAL. They also provide asymptotic statistical guarantees concerning their approach to show the efficacy of their approach (lower and upper bounds).", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "Significance: The results are interesting and motivated. The novelty of the so-called dual purpose learning is perhaps the paper's biggest strength and applications to real-world scenario seem natural and well justified by the ablation study depicted in Section 6 of the article. The paper seems relevant to NeurIPS.\n\nClarity: I applause the author for the well-written article. Even though, Section 5 and 6 are harder to digest than the rest of the article. \nMinor typo: l. 203 \"is contains\"\n\nQuestions/concerns: \n1. DP-IWAL requires several hyper parameters and their selection seems obscure. How to set these parameters as the approach is online?\n2. I am suprised that the cardinality of the label set $\\mathcal{Y}$ does not appear in the upperbounds while it seems natural that the larger the label set, the more labels request are needed. How come the approach remains unchanged between binary classification and extreme classification?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "AgdidQOLSJs", "reviewer": "Reviewer_18hs", "summary": "The authors propose a new learning problem that combines aspects of active learning and learning with abstention. They formalize the setting, provide an algorithm. They also prove an upper bound on the algorithm’s label complexity and a matching lower bound for any algorithm in this setting. Experiments are presented, too.", "questions": "", "limitations": "", "rating": 5, "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": "In general, I like the setting introduced in the paper, which is practically motivated and nicely combines abstention with active learning. I would have appreciated a better discussion of the consequences of this combination, however, especially on an intuitive level. At first, it looks as if the learner is supposed to find a compromise, but upon closer look, that does not necessarily seem to be the case. From an active learning point of view, it makes sense to query those instances on which the uncertainty is high (except in the case pf pure noise, as used by the authors in their proofs, because nothing can be learned from it), but for the same instances it is reasonable to abstain. So where is the problem, and if the learner cannot achieve the learning rate of the standard (supervised, active) agent, what is its disadvantage? Is it because of the slightly different evaluation? \n\nUpon closer inspection, I was also puzzled by some technical details of the setting. For example, why is a complete request function R_t needed for every t if this function is only applied to a single instance x_t? What the learner needs is a rule that decides whether or not x_t is queried, given the history so far. Why should one consider the conditional accuracy given r(x)=0 and not the overall accuracy, and isn't is a problem that the request function may change from one time point to the other? If eta is the request rate and e the conditional probability of a correct prediction, then the overall accuracy is eta*1 + (1-eta)*e, so maximizing the overall accuracy is equivalent to maximizing e.  Moreover, I was puzzled by the assumption of a finite time horizon T. Is this an online setting or not? Are new examples still queried after T, using r_T, or does querying stop at that time? If it continues, there would not be a need for the finite time horizon. If it stops, that would be a bit strange from a practical point of view. \n\nThe paper is quite dense and not always easy to follow, especially since many things are moved to the appendix -- a bit too much in my opinion. For example, I'd have appreciated to see at least a sketch of the proofs in the main paper. They seem to be technically sound, but it's of course hard to check 10 pages of proofs in detail. \n\nThe title of the paper is quite unspecific and in my opinion not well chosen.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "adequately addressed ", "review_text": "", "extra_scores": {"ethical_concerns": "none", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work formally proposes a novel learning  setup, which, on a high level can be viewed as a combination of active learning and learning with abstentions. The framework works with two function classes, a function class R, that contains regions of where labels should be requested and a (standard) hypothesis class of classifiers H. The goal of the earning is set to minimize the classification loss in the regions where labels are not requested, that is, minimize classification loss conditioned on r=0 (in the regions where r=1, labels are assumed to be always requested, so the classifier does not need to get labels correct). To make this setup non trivial, the the region, where r=1 is budgeted to probability weight rho. 

This paper proposes and analyzes this setup. The submission contains upper and lower bound on the query complexity and this is compared with standard active learning. Additionally, the authors provide some experimental evaluation on an adaptation of IWAL to their setup.

This overall appears to be a solid and rounded piece of work. The reviewers have critized a lack of proper motivation as well as clarity issues in the presentation. More intuitive explanation and guidance to the readers could have been given. I agree with the reviewers on these aspects, and would therefore rate this work as borderline, with a storng tendency to accept.
Decision: Accept (Poster)