Efficient Active Learning with Abstention
Authors: Yinglun Zhu
Robert D Nowak
Venue: NeurIPS 2022 Accept (2022)

Abstract: The goal of active learning is to achieve the same accuracy achievable by passive learning, while using much fewer labels. Exponential savings in terms of label complexity have been proved in very special cases, but fundamental lower bounds show that such improvements are impossible in general. This suggests a need to explore alternative goals for active learning. Learning with abstention is one such alternative.  In this setting, the active learning algorithm may abstain from prediction and incur an error that is marginally smaller than random guessing. We develop the first computationally efficient active learning algorithm with abstention. Our algorithm provably achieves $\mathsf{polylog}(\frac{1}{\varepsilon})$ label complexity, without any low noise conditions. Such performance guarantee reduces the label complexity by an exponential factor, relative to passive learning and active learning that is not allowed to abstain. Furthermore, our algorithm is guaranteed to only abstain on hard examples (where the true label distribution is close to a fair coin), a novel property we term \emph{proper abstention} that also leads to a host of other desirable characteristics (e.g., recovering minimax guarantees in the standard setting, and avoiding the undesirable ``noise-seeking'' behavior often seen in active learning). We also provide novel extensions of our algorithm that achieve \emph{constant} label complexity and deal with model misspecification.

Efficient Active Learning with Abstention
Yinglun Zhu Department of Computer Sciences University of Wisconsin-Madiin Madison, WI 53706 yinglunêcs. wisc.ed. edu
Robert Nowak
Department of Electrical and Computer Engineering University of Wisconsin-Madison
Madison, WI 53706
rdnowakewisc.edn
Abstract
The goal of active learning is to achieve the same accuracy achievable by passive learning, while using much fewer labels. Exponential savings in terms of label complexity have been proved in very special cases, but fundamental lower bounds show that such improvements are impossible general. This suggests a need to explore alternative goals for active learning. Learning with abstention is one such alternative. In this setting, the active learning algorithm may abstain from prediction and incur an error that is marginally smaller than random guessing. We develop the first computationally efficient active learning algorithm with abstention. Our algorithm provably achieves polylog label complexity, without any low noise conditions. Such performance guarantee reduces the label complexity by exponential factor, relative to passive learning and active learning that is not allowed to abstain. Furthermore, our algorithm is guaranteed to only abstain on hard examples (where the true label distribution is close property we term proper abstention that also leads to a host of other desirable characteristics (c.g., recovering minimax guarantees in the standard setting, and avoiding the undesirable "noise-seeking" behavior often seen in active learning). We also provide novel extensions of our algorithm that achieve constant label complexity and deal with model misspecification.
fair coin), a novel
1 Introduction
Active learning aims at learning an accurate classifier with small number of labeled data points (Settles, 2009; Hanneke, 2014). Active learning has become increasingly important in modern application of machine learning, where unlabeled data points are abundant yet the labeling process requires expensive time and effort. Empirical successes of active learning have been observed in many areas (Tong and Koller, 2001; Gal et al., 2017: Sener and Savarese, 2015 18). In noise-free or certain low-noise cases (i.e., under Massart noise (Massart and Nédélec, 2006)), active learning algorithms with provable exponential savings over the passive counterpart have been developed (Balcan al., 2007: Hanneke, 2007: Dasgupta al., 2009; Hsu, 2010: Dekel et al., 2012: Hanneke, 2014: Zhang and Chaudhuri, 2014; Krishnamurthy et al.. 2019; Katz-Samuela et al., 2021). On the other hand, however, not much can be said in the general case. In fact, Kääriäinen (2006) provides 2 2(2)) lower bound by reducing active learning to a simple mean estimation problem: It takes 2 samples to distinguish n7xx) 1 + E and 77xx) = E. Even with the relatively benign Tsybakov noise (Tsybakov, 2004), Castro and Nowak (2006, 2008) derive [(poly (})) lower bound, again, indicating that exponential speedup over passive learning is not possible in general. These fundamental lower bounds lay out statistical barriers active learning, and suggests considering refinement of the label complexity goals in active learning (Kääriäinen, 2006).
Inspecting these lower bounds, that are close to the decision boundary. However, do we really require a trained classifier to do well
that active learning suffers from classifying hard examples
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

on those hard examples? In high-risk domains such as medical imaging, it makes more sense for the classifier to abstain from making the decision and leave the problem human expert. Such idea is formalized under Chow's 's error (Chow, 1970): Whenever the classifier chooses to abstain, a loss that is barely smaller than random guessing, i.e., 2 7, is incurred. The parameter 7 should be thought as a small positive quantity, e.g.- 7 0.01. The inclusion of abstention is not only practically interesting, but also provides a statistical refinement of the label complexity goal of active learning: Achieving exponential improvement under Chow's ' excess error. When abstention is allowed as action, Puchkin and Zhivotovskiy (2021) shows, for the first time, that exponential improvement in label complexity can be achieved by active learning in the general setting. However, the approach provided in Puchkin and Zhivotovskiy (2021) can not be efficiently implemented. Their algorithm follows the disagreement-busee based approach and requires maintaining version space and checking whether or not an example lies in the region of disagreement. It is not clear how to generally implement these operations besides enumeration (Beygelzimer al., 2010). Moreover, their algorithm relies on an Empirical Risk Minimization (ERM) oracle, which is known to be NP-Hard even for a simple linear hypothesis class (Guruswami and Raghavendra, 2009).
In this paper, we break the computational barrier and design an efficient active learning algorithm with exponential improvement in label complexity relative to conventional passive learning. The algorithm relies on weighted square loss regression oracle, which can be efficiently implemented in many cases (Krishnamurthy et al., 2017, 2019; Foster et al., 2018, 8, 2020). The algorithm also abstains properly, ie., abstain only when it is the optimal choice, which allows us to easily translate the guarantees to the standard excess error. Along the way, we propose new noise-seeking noise conditions and show that: uuncertainty-basedd active learners can be easily trapped, yet our algorithm provably overcome these noise-seeking conditions. As extension, we also provide the first algorithm that enjoys constant label complexity for a general set of regression functions.
1.1 Problem setting
Let X' denote the input space and y denote the label space. We focus on the binary classification problem where y = [++1,11,, The joint distribution over X x Y is denoted as Dxy. We use Dx to denote the marginal distribution over the input space X, and use Dyiz to denote the conditional distribution of y with respect any x X. We define n7()) == PyrDyy (y +1) as the conditional probability of taking positive label. We consider the standard active learning setup where (a., y) Dxy but y is observed only after label querying. We consider hypothesis class H. X -> y.
For any classifier h E H. its (standard) error is defined as err(h) == P (mx))~xx (h(x)) + v).
Function approximation. We focus on the case where the hypothesis class H is induced from a set of regression functions F: X' - [0, 1] that predicts the conditional probability ny(x). We write H = Hr == (by: : I E F} where (x)(x)= := sign(2f(a) (x) - 1). The "size" of F is measured by the well-known complexity measure: the Pseudo dimension PJ) (Pollard, 1984; Haussler, 1989, 1995). We assume Pdim(F) < Do throughout the paper.' Following existing works in active learning (Dekel et al., 2012; Krishnamurthy al., 2017, 2019) and contextual bandits (Agarwal et al., 2012: Foster et al., 2018; Foster and Rakhlin, 2020; Simchi-Lew and Xu, 2020), we make the following realizability assumption.
Assumption (Realizability). The learner is given a set of regressors F : X + [0, 1] such that there exists f* F characterize the true conditional probability, i.e., f 17.
The realizability assumption allows rich function approximation, which strictly generalizes the setting with linear function approximation studied in active learning (c.g., in (Dekel et al., 2012)). We relax Assumption in Section 4.2 to deal with model misspecification.
Regression oracle. We consider a regression oracle over F, which is extensively studied in the literature in active learning and contextual bandits (Krishnamurthy et al., 2017, 2019; Foster et al., 2018, 2020). Given any set S of weighted examples (w, 2r, y) E R x X ) as input, the regression
'See Appendix D for formal definition of the Pseudo dimension. Many function classes of practical interests have finite Pseudo dimension: (1) when F finite, we have Pdim O FF ): (2) when J is of linear funetions/generaaized linear function with non-decreasing link function, we have F Od)) (3) when JF is set of degree-r polynomial in gd have Pdim(F) O( ((7)))

---

oracle outputs
f arg min
Σ w(f(x) y))²
fEF
(w,a.))
The regression oracle solves a convex optimization problem with respect to the regression function, and admits closed-form solutions in many cases, e-g., it is reduced to least squares when f is linear. We view the implementation of the regression oracle as an efficient operation and quantify the computational complexity in terms of the number of calls the regression oracle.
Chow's excess error (Chow, 1970). Let := hy. E denote the Bayes classifier. The standard excess error of classifier h E H is defined as err(h) err(h"). Since achieving exponential improvement (of active over passive learning) with respect to the standard excess error is impossible in general (Kääriäinen, 2006), we introduce Chow's 's excess enror next. We consider classifier of the form h= X + y U } where 1 denotes the action of abstention. For any fixed 0 < Y 2. the Chow's error is defined as err, (h) P(aa))>Dx> (h(x) + y, M(xxx # 1) + (1/2 ((xx)) (h(x) = L). (2)
The parameter 7 can be chosen as a small constant, e.g., ? = 0.01, to avoid excessive abstention: The price of abstention is only marginally smaller than random guess. The Chow's excess error is then defined as err. (h) err(h") (Puchkin and Zhivotovskiy, 2021). For any fixed accuracy level > we aim at constructing a classifier h X' - Y } with E Chow's 's excess error and polylog( ) label complexity. We also relate Chow's excess error standard excess error in Section
Remark 1. Competing against the optimal Chow's error, i.e., err, inf bxf- (+11,-1.1) err- (h),
will eliminate active learning gains. As in Kääriäinen (2006), it suffices to consider simple problem with X = {z}. In order to achieve excess ervor against the optimal Chow's classifier, we need to distinguish cases TT(2)= = = - 2E and r7(z) = Y + 2E, which inevitably requires ( samples. We defer a detailed discussion (with pictorial explanations) of Chow's 's excess error in Appendix B.
1.2 Contributions and paper organization
We provide informal statements of our main results in this section. Our results depend on complexity measures such as value function disagreement coefficient and eluder dimension e (formally defined in Section and Appendix C). These complexity measures are previously analyzed in contextual bandits (Russo and Van Roy, 2013; Foster et al., 2020) and we import them to the active learning setup. These complexity measures well-bounded for many function classes of practical interests, e.g., we have 8, e (dd for linear and generalized linear functions on Rd
Our first main contribution is that we design the first computationally efficient active learning algo- rithm (Algorithm 1) that achieves exponential labeling savings, without any low noise assumptions.
Theorem (Informal). There exists algorithm that constructs classifier h X + [+1,-1, with Chow's 's excess error at most e and label complexity Ö Pdim(()) polylog( without any low noise assumptions. The algorithum can be efficiently implemented via a regression oracle: It takes 00 Pdim(()) oracle calls for general F, and Ö Pdim(F) oracle calls for convex F.
722
The formal statements are provided in Section The statistical guarantees (i.e., label complexity) in Theorem 1 is similar to the one achieved in Puchkin and Zhivotovskiy (2021), with one critical difference: The label complexity provided Puchkin and Zhivotovskiy (2021) is in terms of the classifier-baed disagreement coefficient é (Hanneke, 2014). Even for a of linear classifier, Ø is only known to be bounded in special cases, e.g., when Dx is uniform over the unit sphere (Hanneke, 2007). On the other hand, we have S for any Dx (Foster et al., 2020).
We say that a classifier X' (+1, 1 enjoys proper abstention if it abstains only if abstention is indeed the optimal choice (based on Eq. (2)). For any classifier that enjoys proper abstention, one can easily relate its standard excess error to the Chow's excess error, under commonly studied Massart/T sybakov noises (Massart and Nédélec, 2006; Tsybakov, 2004). The classifier obtained in Thcorem enjoys proper abstention, and achieves the following guarantees (formally stated in Section 3.1).
3

---

Theorem 2 (Informal). Under Massart/Tsybakov noise, with appropriate adjustments, the classifier learned in Theorem achieves the minimax optimal label complexity under standard excess error.
We also propose new noise conditions that strictly generalize the usual Massart/Tsybakov noises, which we call noise-seeking conditions. high-level, the noise-secking conditions allow abundant data points with n(æ) equal/close to 5. These points are somewhat "harmless" since it hardly matters what label is predicted that point (in terms of excess error). These seemingly "harmless" data points can, however, cause troubles for any active learning algorithm that requests the label for any point that is uncertain, i.e., the algorithm cannot decide if (n(x=) 2. is strictly greater than O. We call such algorithms suncertainty-based active learners. These algorithms could wastefully sample these "harmless" regions, ignoring other regions where erring could be much more harmful. We derive the following proposition (formally stated in Section 3.2) under these noise-seeking conditions.
Proposition 1 (Informal). For any labeling budget B 2 1/2 -polylog()), )), there exists a learning problem such that (1) any uncertainty-baaee active learner suffers standard excess error Q(B=l): yea (2) the classifier h learned in Theorem achieves standard excess error at most e.
The above result demonstrates the superiority of our algorithm over any "uncertainty-baseee active learner. Moreover, we show that, under these strictly harder noise-seeking conditions, our algorithm still achieve guarantees similar to the ones stated in Theorem 2.
next main result, first consider simple active learning problem with X' = { Under Massart noise, we have [m]])) 1 2 To for some constant To > 0. Thus, it takes no more than O(T,² log {)) labels to achieve standard excess error, no matter how small e is. This example shows that, at least in simple cases, we can expect to achieve a constant label complexity for active learning, with no dependence on at all. To the best of our knowledge, our next result provides the first generalization of such phenomenon to a general set of (finite) regression functions, long its eluder dimension is bounded.
Before presenting
Theorem 3 (Informal). Under Massart noise with parameter To and general (finite) set of regression function F. There exists an algorithm that returns a classifier with standard excess error at most and label complexity O ellog (F188) which is independent of b.
A similar constant label complexity holds with Chow's 's excess error, without any low noise assump- tions. We also provide discussion on why previous algorithms do not achieve such constant label complexity, even in the case with linear functions. We defer formal statements and discussion to Section 4.1. In Section 4.2, we relax Assumption and propose an algorithm that can deal with model misspecification.
Paper organization. The rest of this paper is organized as follows. We present our main algorithm and its guarantees in Section 2. We further analyze our algorithm under standard excess error in Section 3, and discuss other important properties of the algorithm. Extensions our algorithm, e.g., achieving constant label complexity and dealing with model misspecification, are provided in Section 4. We defer the discussion of additional related work and all proofs to the Appendix due to lack of space.
2 Efficient active learning with abstention
We provide our main algorithm (Algorithm 1) in this section. Algorithm is an adaptation of the algorithm developed in Krishnamurthy et al. (2017, 2019), which studies active learning under the standard excess error (and Massant/Tsybakov noises). We additionally take the abstention option into consideration, and manually construci classifiers using the active set of (uneliminated) regression functions (which do not belong to the original hypothesis class). These new elements allow us to achieve Chow's 's excess error with polylog( { label complexity, without any low noise assumptions.

---

Algorithm/ 1 Efficient Active Learning with Abstention
Input: Accuracy level
abstention parameter
(0, and confidence level E (0, 1).
1: Define := (
0 (P) ). M == flog2 7 and C3 := O(Pdim(F) log(T/6))-
2: Define 7m == n for m 2 1, = 0 and pm == (M - + 1) Cs.
3: for epoch mn = 1, ........................... .M do
4: Get f' == arg men
JEF Eist (z) - yy)
We Q (0. to indicate whether the label of is queried.
5: (Implicitly) Construct active set of regression functions Fm S as
Fm = 1={1EF
mm-
7m-
Σ Q((((z)) - v0 S
Qe(Fm((z)= - -yy)² + 3m
6: Construct classifier hm :' + {+1. - - as
[lcb(x;; ucb( 1 - - + +
(m) = sign fm) (x)
and construct query function Im (x) == 1 ( E (Icb(æ; Fm), ucb(x;Fmm)) 1(hm(x) (x) # 1).
7:
if epoch m M then
8: Return classifier has-
9: for time t = Tm + 1..... do
Observe 34 Dx Set Qi = Im (12).
11:
if Q2 = 1 then
Query the label ye of mt-
Algorithm 1 runs in epochs of geometrically increasing lengths. At the beginning of epoch [M]] Algorithm 1 first computes the empirical best regression function fm. that achieves the smallest cumulative square loss over previously labeled data points (fi can be selected arbitrarily); it then (implicitly) constructs an active set of regression functions Fi. where the cumulative square loss of each f Fm is not too much larger than the cumulative square loss of empirical best regression function f... For any & E X, based on the active set of regression functions, Algorithm constructs a lower bound Icb(2;
inf JEF. f (x) and an upper bound ucb(2; Fm) ) supjeF.. f(x) for the true conditional probability 7)(z). An empirical classifier 7... X' - {+1,-1) - and query function 9m X + {0, 1} are then constructed based on these confidence ranges and the abstention parameter y, For any time step within epoch m, Algorithm queries the label of the observed data point v; if and only Q: 9m (1re) 1. Algorithm returns hM the learned classifier.
We now discuss the empirical classifier h. and the query function 9m in more detail. Consider the event where f E Fi,. for all m E [M]. which can be shown to hold with high probability. The constructed confidence intervals are valid under this event, i.e., 77(x) E [lcb(a; Fm.. ucb(u:; Fm.)). First, let us examine the conditions that determine label query. The label of x is nor queried if
We have 7Tx) E [lcb(2;; Fm)) ucb(2; Fm)] S [ - 7: 1 + 7) Abstention leads to the smallest error (Herbei and Wegkamp, 2006), and no query is needed.
Case 1: hm (x) L.
Case 2: 2 E (Icb(x; ucb( We have sign (x) ) - 1) = sign - 1). Thus, excess error is incurred and there no need to query.
The only case when label query is issued, and thus when the classifier hm may suffer from excess error, is when
1 E (Icb(x;FFm)) ucb(u;; Fm)) and Fmb(
[
g 7, 2
+
(3)
2
hold simultancously. Eq. (3) necessarily leads to the condition w Fm) = ucb(x;; Icb(x; > 7. Our theoretical analysis shows that the event must [(w Fm) 7) happens in-
5

---

frequently, and its frequency is closely related to the so-called value function disagreement coefficient (Foster al., 2020), which we introduce as follows."
Definition 1 (Value function disagreement coefficient). For any f E FF and yo. Eo > 0, the value function disagreement coefficient gy (F, No. Eu) is defined as
2
PDx (35 E F: F:1(()) f² n 1f MIDx se)
sup sup Dx 72700
where II == (f
Combining the insights discussed above, we derive the following label complexity guarantee for Algorithm (we use A == e.PF 8/ 07 1/2,2,2 c) and discuss its boundedness below).
Theorem 4. With probability at least 1 - 26, Algorithm I returns classifier with Chow's excess
error at most and label complexity 0 0 Pdimm log2( (ddim())
log(
(Pdiim()) ))-
29
276
Theorem shows that Algorithm 1 achieves exponential label savings (i.e., polylog( (2)) without any low noise assumptions. We discuss the result in more detail next.
Boundedness of 9. The value function disagreement coefficient is well- rell-bounded for many function classes of practical interests. For instance, we have I for linear functions on RV and O & Clink d for generalized linear functions (where Clink is quantity related the link function). Moreover, 0 is always upper bounded by complexity measures such as (squared) star number and eluder dimension (Foster et al., 2020). See Appendix C for the detailed definitions/hounds,
Comparison to Puchkin and Zhivotovskiy (2021). The label complexity bound derived in Theorem similar the one derived in Puchkin and Zhivotovskiy (2021), with one critical difference: The bound derived in Puchkin and Zhivotovskiy (2021) is in terms of classifier-busel disagreement coefficient & (Hanneke, 2014). Even in the case with linear classifiers, 0 is only known to be bounded under additional assumptions, e.g., when Dx is uniform over the unit sphere.
Computational efficiency. We discuss how efficiently implement Algorithm 1 with the regres- sion oracle defined in Eq. (1). Our implementation relies on subroutines developed in Krishnamurthy al. (2017); Foster et al. (2018), which allow us to approximate confidence bounds ucb(x; Fm) and lcb( (r; Fm) up to approximation error with O / log A) (or Olog 4) when F is convex and closed under pointwise convergence) calls to the regression oracle. To achieve the same theoretical guarantees shown in Theorem 4 (up to changes in constant terms), we show that it suffices to (i) control the approximation error level O log T (ii) construct the approximated confidence bounds
lcb(;; Fm) and ucb(æ; Fi)) a way such that the confidence region is non-increasing with respect to the epoch m, i.e., (Icb(x; Fm); ucb(æ;; Fm)) S ((b(x;;,m->) ucb(2; Fm--)) (this ensures that the sampling region is non-inereasing even with approximated confidence bounds, which is impor- tant to our theoretical analysis), and (iii) use the approximated confidence bounds (cb(:; F.)) and ucb(x;;F.) to construct the classifier hm and the query function 9m. We provide guarantees as follows, and leave details to Appendix E (we redefine 0 == supp 072al (F, 7/4, in the Theorem 5 to account to approximation error).
Theorem 5. Algorithm 1 can be efficiently implemented via the regression oracle and enjoys the same theoretical guarantees stated in Theorem The number of oracle calls needed is Ö @ Pdim
Compared the original definition studied in contextual bandits (Foster al., 2020), our definition takes an additional "sup" over all possible marginal distributions Dx to account for distributional shifts incurred by selective querying (which do not occur in contextual bandits). Nevertheless, as we show below, our disagreement coefficient is still well-hounded for many important function classes.
It suffices to take == 07 (F, 2)2 with x VTE to derive a slightly different guarantee. See Appendix E.
*Recall that the implementation of the regression oracle should be viewed an efficient operation since it solves a convex optimization problem with respect to the regression function, and it even admits closed-form solutions in many cases, e.g., it is reduced to least squares when ff is linear. On the other hand, the ERM oracle used in Puchkin and Zhivotovskiy (2021) is NP-hard even for a set of linear classifiers (Guruswami and Raghavendra, 2009).

---

for a general set of regression functions F. and Ō _ PPdiil))) when FF is convex and closed under pointwise convergence. The per-exumple inference time of the learned hMM is O(7 log (P for general F, and Ollog )) when F is convex and closed under pointwise convergence.
EN
With Theorem 5, provide the first computationally efficient active learning algorithm that achieves exponential label savings, without any low noise assumptions.
3 Guarantees under standard excess error
We provide guarantees for Algorithm I under standard excess error. In Section 3.1, we show that Algorithm can be used to recover the usual minimax label complexity under Massart/Tsybakov noise; we also provide new learning paradigm based on Algorithm I under limited budget. In Section 3.2, we show that Algorithm provably avoid the undesired noise-seeking behavior often seen in active learning.
3.1 Recovering minimax optimal label complexity
One way to convert an abstaining classifier h X (U into a standard classifier h y by randomizing the prediction in its abstention region, i.e., M(x) = I., then its randomized version h(x) predicts +1/ 1 with equal probability (Puchkin and Zhivotovskiy,209 2021). With such randomization, the standard excess error of can be characterized as
err(h) err(hh) err, (h) err(h") + PENDX (h(x)= 1).
(4)
The standard excess error depends on the (random) abstention region of h, which is difficult to quantify in general. To give more practical characterization of the standard excess enror, introduce the concept of proper abstention in the following.
Definition 2 (Proper abstention). A classifier h X + (U(L} enjoys proper abstention and only it abstains regions where abstention is indeed the optimal choice, i.e., {x E X -((x)=()))) = =1 S {o E X: nf(x) E [ - 7. 1/2 + } =: Kzy.
Proposition 2. The classifier l returned by Algorithm I enjoys proper abstention. With randomization over the abstention region, have the following upper bound on its standard excess error
err(h) - err(h*) S cer,, (eer(()))rr(h)))
-err(h") + ..yyB. (x-Dx E M,).
(5)
The proper abstention property of h returned by Algorithm 1 is achieved via conservation: will avoid abstention unless it is absolutely sure that abstention is the optimal choice." To characterize the standard excess error of classifier with proper abstention, we only need upper bound the term
PawDx (x E X.), which does not depends on the (random) classifier h. Instead, only depends on the marginal distribution. We next introduce the common Massart/Tsybakon noise conditions.
Definition 3 (Massart noise, Massart and Nédélec (2006)). A distribution Dxy satisfies the Massart noise condition with parameter To if Pa-DD (In(2) 1/21 S To) 0.
Definition 4 (Tsybakov noise, Tsybakov (2004)). A distribution Dxy satisfies the Tsybakov noise condition with parameter 3 2 O and a universal constant e > 0 P (17(x) - 1/2| $ T) 5T for any O.
As in Balcan et al. (2007); Hanneke (2014), we assume knowledge of noise parameters (e.g.. To: 9). Together with the active learning lower established in Castro and Nowak (2006, 2008), and focusing on the dependence of s, our next theorem shows that Algorithm can be used to recover the minimax label complexity in active learning, under the standard excess error.
$ 'On other hand, however, algorithm provided Puchkin and Zhivotovskiy (2021) is very unlikely to have such property. In fact, only a small but nonzero upper bound of abstention rate is provided (Proposition 3.6 therein) under the Massart noise with y < To yet any classifier that enjoys proper abstention should have exactly zero abstention rate.

---

Theorem 6.
With an appropriate choice of the abstention parameter Y in Algorithm I and random- ization over the abstention region, Algorithm I learns a classifier h at the minimax optimal rates: To achieve standard excess error, it takes ((T labels under Massart noise and takes ( ((=-2((1+0))
labels under T'ybakovv noise.
Remark 2. In addition to recovering the minimax rates, the proper abstention property is desirable in practice: It guarantees that h will not abstain on easy examples, i.e., it will not mistakenly flag easy examples as "hard-to-clasiff" ", thus eliminating unnecessary human labeling efforts.
Algorithm 1 can also be used provide new learning paradigms in the limited budget setting, which we introduce below. No prior knowledge of noise parameters are required in this setup.
New learning paradigm under limited budget. Given any labeling budget B > O, can then choose 7 R B-1/2 in Algorithm to make sure the label complexity is never greater than B (with high probability). The learned classifier enjoys Chow's s excess error (with parameter 7) at most E; its standard excess error (with randomization over the abstention region) can be analyzed by relating the y DD (I E X,) term in Eq. (5) to the Massart/Tsybakor noise conditions, as discussed above.
3.2 Abstention to avoid noise-seeking
Active learning algorithms sometimes exhibit noise-seeking behaviors, i.e., oversampling in regions where n)(2) is close to the & level. Such noise-seeking behavior is known be a fundamental barrier to achieve low label complexity (under standard excess error), e.g., see Kääriäinen (2006). We show in this section that abstention naturally helps avoiding noise-seeking behaviors and speeding up active learning.
To better illustrate how properly abstaining classifiers avoid noise-seeking behavior, we first propose new noise conditions below, which strictly generalize the usual Massart/Tsybakee noises.
Definition (Noise-secking Massart noise). A distribution Dxy satisfies the noise-seeking Massart noise condition with parameters 0 S Ço < To I 1/2 if FeFDDxx (So < (m](z)) 1/2] S To) O.
Definition 6 (Noise-seeking Tsybakov noise). A distribution Dxy satisfies the noise-seeking Tsy- bakov noise condition with parameters 0 S Ço < 1/2, 3 2 0 and universal constant 0 if PENDx (So In(()) 1/2| S r) S CT for any Çu-
Compared to the standard Massart/Tsybakov noises, these newly proposed noise-seeking conditions allow arbitrary probability mass of data points whose conditional probability n7()) is equal/close to 1/2. As a result, they can trick standard active learning algorithms into exhibiting the noikeng bahaviors (and hence their names). We also mention that the parameter So should be considered an extremely small quantity (e.g., So < E), with the extreme case corresponding to Co = 0 (which still allow arbitrary probability for region (ar E X n/(x)= = 1/2)).
Ideally, any active learning algorithm should not be heavily affected by these noise conditions since it hardly matters (in terms of excess error) what label is predicted over region {x E X' (n(x) - 1/2] S Go). However, these scemingly benign noise-secking conditions can cause troubles for any "uncertainty-base" bbased" active learner, i.e., any active learning algorithm that requests the label for any point that is uncertain (see Definition 10 in Appendix F for formal definition). In particular, under limited budget, we derive the following result.
Proposition 3. Fix e, 5 > O. For any labeling budget B Z 4 logg( log( there exists a learning problem (with set of linear regression functions) satisfying Definition 5/Definition 6 such that (1) any suncertainty-based active learner suffers expected standard excess error Q(B-1); yet (2) with probability at least 8, Algorithm 1 returns a classifier with standard excess error at most
The above result demonstrates the superiority of our Algorithm I over any "uncertainty-basee"" active learner. Moreover, we show that Algorithm achieves similar guarantees as in Theorem 6 under the strictly harder noise- seeking conditions. Specifically, we have the following guarantees.
Theorem 7.
With an appropriate choice of the abstention parameter y in Algorithm I and random- ization over the abstention region, Algorithm I learns classifier h with e + Ço standard excess error after querying @(rr²) labels under Definition 5 or querying θ ((c-2/(1+))) labels under Definition 6.
8

---

The special case of the noise-seeking condition with So = 0 is recently studied in (Kpotufe et al., 2021), where the authors conclude that no active learners can outperform the passive counterparts in the nonparametric regime. Theorem 7 shows that, in the parametric setting (with function approximation), Algorithm 1 provably overeomes these noise-seeking conditions.
4 Extensions
We provide two adaptations of our main algorithm (Algorithm 1) that can (1) achieve constant label complexity for general set of regression functions (Section 4.1); and (2) adapt to model misspecificatioo (Section 4.2). These two adaptations can also be efficiently implemented via regression oracle and enjoy similar guarantees stated in Theorem 5, We defer computational analysis to Appendix G and Appendix H.
4.1 Constant label complexity
We start by considering simple problem instance with X' = {xx) where active learning is reduced to mean estimation of 17(2). Consider the Massart noise case where 17(2) & 1 To. + Tol No matter how small the desired accuracy level > 0 is, the learner should not spend more than O log( 118( labels to correctly classify x with probability at least 1 - 6, which ensures O excess error. In the general setting, but with Chow's 's excess error, similar result follows: It takes at most O log(1/8) samples to verify (xx) is contained in 1 7, 2 + 7 or not. Taking the optimal action within {+1, -1, (based on Eq. (2)) then leads to 0 Chow's 's excess error. This reasoning shows that, at least in simple cases, one should be able to achieve constant label complexity no matter how small e is. One natural question to ask is as follows.
TO
Is it possible to achieve constant label complexity in the general case of active learning?
We provide the first affirmative answer to the above question with general set of regression function F (finite), and under general action space X' and marginal distribution Dx- The positive result is achieved by Algorithm 2 (deferred to Appendix G.2), which differs from Algorithm 1 in two aspects: (1) we drop the epoch scheduling, and (2) apply a tighter elimination step derived from an optimal stopping theorem. Another change comes from the analysis of the algorithm: Instead of analyzing with respect to the disagreement coefficient, we work with the eluder dimension e: sup, Cy- (2). To do that, we analyze active learning from the perspective of regret minimization with selective querying (Dekel et al., 2012), which allows us to incorporate techniques developed in the field of contextual bandits (Russo and Van Roy, 2013; Foster et al., 2020). We defer a detailed discussion to Appendix G. and provide the following guarantees.
Theorem 8. With probability least 1 28, Algorithm 2 returns classifier with expected Chow's excess error at most e and label complexity O (=)oo(((//)) (61), which is independent of
Based discussion in Section 3, we can immediately translate the above results into standard excess error guarantees under the Massart noise (with replaced by TO). We next discuss why existing algorithms/analyss do not guarantee constant label complexity, even the linear case.
Epoch scheduling. Many algorithms proceed in epochs and aim at halving the excess error after each epoch (Balcan et al., 2007; Zhang and Chaudhuri, 2014; Puchkin and Zhivotovskiy, 2021). One inevitably needs log 1 e epochs to achieve = excess error.
2. Relating to disagreement coefficient. The algorithm presented in Krishnamurthy et al. (2019) does not use epoch scheduling. However, their label complexity are analyzed with disagreement coefficient, which incurs ΣV/= 1 Ollog }) term in the label complexity.
F.
Remark 3. Algorithm 2 also provides guarantees when x selected by an adaptive adversary (instead of i.i.d. sampled x Dx). In that case, simultancously upper bound the regret and the label complexity (see Theorem 10 in Appendix G.2), Our results can be viewed as a generalization of the results developed in the linear case (Dekel et al., 2012).
'We formally define eluder dimension in Appendix C. As examples, we have O(d log 2) for linear functions in Rdd and = O(Cink dlog 2 for generalized linear functions (where Cink a quantity related to the link function).

---

4.2 Dealing with model misspecification
Our main results are developed under realizability (Assumption 1), which assumes that there exists a f E F such that f* = 1). In this section, we relax that assumption and allow model misspecification. We assume the learner is given a set of regression function F : X - [0, 1] that may only approximates the conditional probability 1y. More specifically, we make the following assumption.
Assumption (Model misspecification). There exists K > 0 accuracy, i.e., supzex (x) r7(3)) s k.
FF such that f approximate 1] up to
We use a variation of Algorithm to adapt model misspecification (Algorithm 3, deferred to Appendix H.1). Compared to Algorithm I, the main change in Algorithm 3 is to apply more conservative step determining the active Fm at each epoch: We maintain a larger active set of regression function to ensure that [ not eliminated throughout all epochs. Our algorithm proceeds withou/ knowing the misspecification level k. However, the excess error bound presented next holds under the condition that k I & (i.e., it requires that the misspecification is no larger than the desired accuracy). Abbreviate 0 == sup,>o ( (/),))))))
1). ) we achieve the following guarantees.
Theorem 9. Suppose
With probubility at least 26, Algorithm 3 returns classifier with Pdlim(()) and label complexity O 0 Pddin(F). -log? (diil)))
Chow's 's excess error ( 8 log( 876 log( Pdim(F))
87
We only provide guarantee when S e, since the learned classifier suffers from additive term in the excess error (see Appendix H.2 for more discussion). On the other hand, the (inefficient) algorithm provided in Puchkin and Zhivotovskiy (2021) works without any assumption on the approximation error. An interesting future direction is to study the relation between computational efficiency and learning with general approximation error.
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for their helpful comments. This work is partially supported by NSF grant 1934612 and AFOSR grant FA9550-18-1-0166 18-1-0166.
References
Alekh Agarwal, Miroslav Dudík, Satyen Kale, John Langford, and Robert Schapire. Contextual bandit learning with predictable rewards. In Artificial Intelligence and Statistics, pages 19-26.
PMLR, 2012.
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference on Machine Learning, pages 1638-1646. PMLR, 2014.
Martin Anthony. Uniform glivenko-cantelli theorems and concentration of measure in the mathemati- cal modelling of learning. Research Report LSE-CDAM-2002-07, 2002
Maria-Florinn Balcan, Andrei Broder, and Tong Zhang. Margin based active learning. In International
Conference on Computational Learning Theory, pages 35-50. Springer, 2007.
Alina Beygelzimer, Daniel Hsu, John Langford, and Tong Zhang. Agnostic active learning without constraints. Advances in neural information processing systems, 23, 2010.
Olivier Bousquet and Nikita Zhivotovskiy. Fast classification rates without standard margin assump- tions. Information and Inference: Journal of the IMA, 10(4):1389 1111118999911111111 2021.
Rui M Castro and Robert D Nowak. Upper and lower error bounds for active learning. In The 44th Annual Allerton Conference Communication, Control and Computing, volume 2, page 1, 2006.
Rui M Castro and Robert D Nowak. Minimax bounds for active learning. IEEE Transactions Information Theory, 54(5):2339-255 23553, 2008
CK Chow, On optimum recognition error and reject tradcoff. IEEE Transactions on information theory, 16(1):41-46, 1970.
10

---

Sanjoy Dasgupta, Adam Tauman Kalai, and Adam Tauman. Analysis of perceptron-baset active learning. Journal of Machine Learning Research, 10(2). 2009.
Ofer Dekel, Claudio Gentile, and Karthik Sridharan. Selective sampling and active learning from single and multiple teachers. The Journal of Machine Learning Research, 13(1):2655-269) 2012.
Dylan Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In International Conference on Machine Learning, pages 3199-3210. PMLR, 2020.
Dylan Foster, Alekh Agarwal, Miroslav Dudík, Haipeng Luo, and Robert Schapire. Practical contextual bandits with regression oracles. In International Conference on Machine Learning, pages 1539-1548, PMLR, 2018.
Dylan Foster, Alexander Rakhlin, David Simchi-Levi, and Yunzong Xu. Instance-dependent complexity of contextual bandits and reinforcement learning: A disagreement-basse perspective. arXiv preprint urXiv:2010.03104 2020.
David A Freedman. On tail probabilities for martingales. the Annals of Probability, pages 100-118, 1975.
Yarin Gal, Riashat Islam, and Zoubin Ghahramani. Deep bayesian active learning with image data.
In International Conference on Machine Learning, pages 1183-1192. PMLR, 2017.
Venkatesan Guruswami and Prasad Raghavendra. Hardness of learning halfspaces with noise. SIAM Journal on Computing, 39(2):742 765,, 2009.
Steve Hanneke. A bound on the label complexity of agnostic active learning. In Proceedings of the 24th international conference on Machine learming, pages 353-360, 2007
Steve Hanneke. Theory of active learning. Foundations and Trends in Machine Learning, 7(2-3), 2014.
David Haussler. Decision theoretic generalizations of the pac model for neural net and other learning applications. 1989.
David Haussler. Sphere packing numbers for subsets of the boolean n-cube with bounded vapnik- chervonenkis dimension. Journal of Combinatorial Theory, Series A, 69(2)2117232,, 1995.
Radu Herbei and Marten H Wegkamp. Classification with reject option. The Canadian Journal of Statistics/Laa Revue Canadienne de Statistique, pages 709-721, 2006.
Daniel Joseph Hsu. Algoritiums for active learning. PhD thesis, UC San Diego, 2010.
Kuo Huang, Alekh Agarwal, Daniel Hsu, John Langford, and Robert E Schapire. Efficient and parsimonious agnostic active learning. Advances Neural Information Processing Systems, 28, 2015.
Matti Kääriäinen. Active learning in the non-realizable case. In International Conference Algorithmic Learning Theory, pages 63-77. Springer, 2006.
Julian Katz-Samuels, Jifan Zhang, Lalit Jain, and Kevin Jamieson. Improved algorithms for agnostic pool-based active classification. In International Conference Machine Learning, pages 5334- 5344. PMLR, 2021.
Vladimir Koltchinskii. Rademacher complexities and bounding the excess risk in active learning. The Journal of Machine Learning Research, 1 11:2457-2483 2485, 2010.
Samory Kpotufe, Gan Yuan, and Yunfan Zhao. Nuances in margin conditions determine gains in active learning. arXiv preprint arXiv:21 10::21100000 10.0:22,,,,8418,, 2021.
Akshay Krishnamurthy, Alekh Agarwal, Kuo Huang, Hal Daumé III, and John Langford. Active learning for cost-sensitive classification. In International Conference on Machine Learning, pages 1915-1924. PMLR, 2017.
Akshay Krishnamurthy, Alekh Agarwal, Tzu-Kuo Huang, Hal Daumé III, and John Langford. Active learning for cost-sensitive classification. Journal of Machine Learning Research, 20: 10:1-50,70 2019,
Tor Lattimore, Csaba Szepesvari, and Gellert Weisz. Learning with good feature representations in bandits and in rl with a generative model. In International Conference on Machine Learning. pages 5662-5670. PMLR, 2020.
11

---

Andrea Locatelli, Alexandra Carpentier, and Samory Kpotufe. Adaptivity to noise parameters in nouparametric active learning. In Proceedings of the 2017 Conference on Learning Theory, PMLR, 2017.
Pascal Massart and Élodie Nédélec. Risk bounds for statistical learning. The Annals of Statistics, 34 (5):2326-2366, 2006.
Stanislav Minsker. Plug-in approach to active learning. Journal of Machine Learning Research, 13 (1), 2012.
Pollard. Convergence of Stochastic Processes. David Pollard, 1984.
Nikita Puchkin and Nikita Zhivotovskiy. Exponential savings in agnostic active learning through abstention. arXiv preprini arXiv:2
2021.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. In NIPS, pages 2256-22666 Citeseer, 2013.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set
approach. In International Conference on Learning Representations, 2018.
Burr Settles. Active learning literature survey. 2009.
Shubhanshu Shekhar, Mohammad Ghavamzadeh, and Tara Javidi. Active learning for classification with abstention. IEEE Journal on Selected Areas in Information Theory, 2(2):705-719, 2021.
David Simchi-Levi and Yunzong Xu. Bypassing the monster: faster and simpler optimal algorithm for contextual bandits under realizability. Available at SSRN 3562765, 2020.
Simon Tong and Daphne Koller. Support vector machine active learning with applications to text classification. Journal of machine learning research, 26N6v): 2001.
Alexander B Tsybakov. Optimal aggregation of classifiers in statistical learning. The Annals of Statistics, 32(1):135-166, 2004.
Chicheng Zhang and Kamalika Chaudhuri. Beyond disagreement- based agnostic active learning. Advances in Neural Information Processing Systems, 27, 2014.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Our results in the misspecification setting (i.e., in Section 4.2) are derived under assumption. We provide discussion such assumption in Appendix H.2, and leave a comprchensive study of the problem for future work. (c) Did you discuss any potential negative societal impacts of your work? [N/A] Our paper is theoretical nature, and there no negative societal impact of our work in the foreseeable future.
(d) Have you read the ethics review guidelines and ensured that your paper conforms them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Assumptions are clearly stated in the statement of each theorem.
(b) Did you include complete proofs of all theoretical results? [Yes] Complete proofs are provided in the Appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL.) [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (c.g., with respect to the random seed after running experiments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable?
[N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board
(IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "QiZFKf9wJs", "reviewer": "Reviewer_5zzs", "summary": "The paper studies active learning of general concept classes. Lower bound is known in this regime to rule out savings in label complexity over passive learning. However, [PT21] showed that with the additional action of abstention, active learning does provide exponential savings in terms of the error rate. This work follows the research line, and the main contribution falls into a computationally efficient algorithm that archives label complexity comparable to [PT21]. The main algorithm relies on efficient implementation of regression oracles, which has been developed in prior works.\n", "questions": "\nIt is true that [PT21] runs with minimizing an empirical 0/1 loss which is NP-hard. Can you give more intuition on why the 0/1 loss is vital for their analysis, and why the regression oracle approach in the paper works as well?", "limitations": "  Yes.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n+ Active learning is a very useful tool to reduce labeling cost, and this paper studies an interesting and practical extension.\n+ The core contribution on efficient learning paradigm is important.\n+ The paper is well written and easy to follow, with right amount of reminders and pointers.\n\nWeakness:\n- The computational efficiency is phased in terms of number of calls to an oracle, yet leaving the runtime of that oracle unsettled. Please provide concrete computational cost analysis to justify the main contribution.\n- It is true that [PT21] runs with minimizing an empirical 0/1 loss which is NP-hard. Can you give more intuition on why the 0/1 loss is vital for their analysis, and why the regression oracle approach in the paper works as well?\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "FDVTnCl_hAM", "reviewer": "Reviewer_y5fo", "summary": "This paper studies the pool-based active learning problem. The main contribution is to propose a computationally efficient algorithm to train a rejection model. Under the realizable case, the model enjoys $\\epsilon$ chow's excess risk with $\\widetilde{O}(\\mathrm{polylog}(1/\\epsilon))$ label complexity. The guarantee is achieved without any low noise assumption commonly used to achieve the exponential savings label complexity in literature. Although a similar rate (for learning with abstentions) has already appeared in the literature, the proposed method is more efficient (or practical) than the previous one. Besides the main result, the authors also show that (a slight modification of) the proposed method enjoys minimax optimal label complexity for the standard excess risk with the low noise assumption. Furthermore, this paper has shown a constant label complexity in a special case (with a finite hypothesis set) and presented the guarantees with model misspecification.", "questions": "Q1: can the proposed method achieves similar Chow's excess risk without the realizable assumption when comparing with the best model in the hypothesis space $\\mathcal{F}$.\n\nQ2: how to compute the parameter $\\theta$ efficiently (please refer to the second point of the weakness for more details)\n\nQ3: what is the computational cost of ucb and lcb for a hypothesis space $\\mathcal{F}$ containing $f_\\star$", "limitations": "This paper has discussed its limitation on the realizable assumption in Section 4.2. It has shown that the same exponential saving label complexity is achieved with misspecified model space as long as $\\epsilon$ is less than the approximation error $\\kappa$. The results partially address the limitation on the assumption, but I think the paper would become even strong if the author could show a similar convergence rate for Chow's excess risk compared with the best model in the hypothesis when $f_*$ is not in $\\mathcal{F}.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strength:\nOverall, I think this is a nice paper with fruitful results. Specifically, the strengths of this paper are listed as follows,\n+ novelty& significance: although the algorithm framework shares a similar spirit as the previous work [Krishnamurthy et al. 2017] in standard active learning with abstention, the new criterion for label querying is interesting to me. A similar rate for active learning with abstention has been achieved by [Puchkin and Zhivotovskiy, 2021], but a computationally efficient algorithm is always what we desire. \n\n+ clarity: this paper is well written and clearly structured for the most part. Although there are fruitful results regarding Chow's excess risk and the standard excess risk (under different conditions), the authors have clearly organized them to make the results easy to follow.\n\n### Weakness:\nIn general, I like the results of the paper, but I have still some reservations about the assumption and the computational cost as follows,\n- about the realizable assumption: although the realizable has frequently appeared in the active learning literature,  the most related work on active learning with abstention seems not to require such an assumption (Theorem 1.1 of [Puchkin and Zhivotovskiy, 2021]). It seems to me that the realizable assumption is the price for the efficient algorithm since Algorithm 1 requires to approximate $\\eta(y=+1|\\mathbf{x})$ with the function $f(\\mathbf{x})$ (by ucb and lcb). So, I think it would be necessary to make a more clear comparison with the previous work.\n\n- about the efficient algorithm:\n\t- issue on the parameter setting: the algorithm takes the disagreement coefficient $\\theta$ as the input. I am not sure whether such a coefficient can be calculated efficiently in general? (maybe an upper bound for $\\theta$ is enough in special cases, but the realizable assumption could be violated.)\n\t- issue on the estimation of lcb and ucb: although the authors have referred to [Krishnamurthy et al. 2017] for the calculation of the lcb and ucb, I think it would be nice to discuss their computational costs since the efficiency is one of the main contributions of this paper. (for example how hard it is to compute lcb or ucb for a $\\mathcal{F}$ containing the $f_\\star$?).\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9ZJcTEYLLyD", "reviewer": "Reviewer_9njm", "summary": "The paper proposes an active learning algorithm that can avoid sampling from regions of the input space with high label noise. The algorithm satisfies two important properties: 1) it achieves exponential improvements compared to passive learning with respect to an evaluation metric that penalizes abstentions (Chow’s excess error); and 2) the algorithm is computationally tractable for finite pseudo dimension function classes.\n", "questions": "- How does the analysis of Algorithm 1 change if we assume a finite unlabeled set? Can the bound of Theorem 4 be changed to factor in the size of the unlabeled set?\n\n- Steps 5-6 of Algorithm 1 approximate the lcb/ucb over the set of functions $F_m$. For what function classes $F$ is this step tractable? How can the approximation error of the lcb/ucb influence the result of Theorem 4? For what function classes is the approximation of the lcb/ucb “reasonable”?\n\n- Algorithm 1 enjoys strong guarantees at arbitrary noise levels. This is captured in the bounds via $\\gamma$ which needs to be chosen as a function of the noise level (indeed this is explicit in the proof of Theorem 6) and $\\theta$ (which captures the disagreement compared to $f^\\star$ at a fixed level $\\gamma$). How do $\\theta$ and the bound on sample complexity change when $\\gamma$ is chosen inappropriately in Theorem 6, without knowledge of the noise level?\n\n- Can the noise-seeking noise condition be relaxed for Proposition 3? The negative result for uncertainty-based AL is similar in spirit to the one in “On the relationship between data efficiency and error for uncertainty sampling” Mussman & Liang, 2018. While the analysis here is significantly different, the result in Mussman et al only requires non-vanishing Bayes error to reveal the failure of uncertainty sampling.\n\n- Minor remark: “Noise-seeking Massart/Tsybakov noise” can be a bit confusing. Perhaps something like “Random flip-allowing Massart noise” could make it easier to grasp (although it’s a bit of a mouthful)?\n", "limitations": "The paper generally addresses some of the poignant limitations of the analysis (e.g. focus on finite pseudo dimensions function classes, realizable vs agnostic case etc). See the Questions section for other limitations that could also be discussed in the paper.\n", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The paper employs in a creative way techniques from contextual bandit literature to extend the idea of Puchkin et al and propose a computationally tractable algorithm. Moreover, the result is particularly remarkable since it does not require a condition constraining the amount of label noise, but rather captures it in the bound.\n\n- The analysis for deriving the results is non-trivial and some of the connections to quantities from the contextual bandit literature (e.g. eluder dimension, disagreement coefficient) may be of independent interest for the active learning community.\n\n- The paper contains several results that help to position the proposed algorithm in the broader active learning literature. For instance, the analysis of Section 3 confirms that the algorithm is minimax optimal (albeit not substantially better than passive learning) with respect to the standard excess risk.\n\nWeaknesses:\n\n- While the paper is generally easy to follow, certain details regarding the algorithm or the analysis could be discussed in more detail in the main text (see the Questions section)\n\n- Minor remarks: There are a few typos in the paper (e.g. lines 259, 266, 274 etc). Also the pseudocode of Algorithm 1 can be made a bit more precise and easier to follow (perhaps add a notation for the labeled set; Q_t, x_t, y_t are not defined when they appears first in step 4; unspecified how $\\hat{f}_1$ is selected etc).\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "80QUogWmHmK", "reviewer": "Reviewer_8Wbo", "summary": "Paper proposes an active learning algorithm in which labels are not acquired when the model chooses to abstain from predicting.", "questions": "N/A", "limitations": "N/A", "rating": 3, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "[note confidence score of 1 (@authors + @AC). this is largely outside my comfort zone with many proofs, of which I did not study in details. I would recommend discarding my opinion.]\n\nI think lines 35-38 already starts this paper off on the wrong foot. The objective of active learning is to the learn the decision boundary with minimal labels; what the model does with points close to the decision boundary or with high uncertainty once this is learnt could be considered another problem. If the model can the learn the decision boundary with high accuracy given more queries around the decision boundary then this is justified.\n\nStrengths\n- The introduction makes clear what the paper is trying to achieve.\n\nWeaknesses\n- The paper is not easy to read.\n- Scenario proposed does not reasonable.\n- No experimental results whatsoever.\n- Lots of propositions and theorems are stated in the paper, but all the proofs in the appendix. I have but skimmed these. \n\nOriginality:\nCertainly seems new, but a more directed related work would be appreciated.\n\nQuality:\nI find the theoretical exposition somewhat lacking in places-- e.g. for proposition 3 and the statement follows of the algorithms superiority over any uncertainty-based AL method. No experimental results.\n\nClarity:\nNeither well written nor well organised. Language is imprecise and unclear. Parts of the paper make strong statements without backing.\n\nSignificance:\nDifficult to assess the impact of the method. The impact of the paper however will be small, given the problems above.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept