Agnostic Active Learning Is Always Better Than Passive Learning
Authors: Steve Hanneke
Venue: NeurIPS 2025 oral ()
Keywords: Active learning
Agnostic learning
PAC learning
Query complexity
Minimax analysis
VC dimension
Star number
Disagreement coefficient
Primary area: theory
TL;DR: We prove that for every concept class, the optimal query complexity of agnostic active learning is strictly smaller than the sample complexity of agnostic passive learning.

Abstract: This work resolves a long-standing open question of central importance to the theory of active learning, closing a qualitative and quantitative gap in our understanding of active learning in the non-realizable case.  We provide the first sharp characterization of the optimal first-order query complexity of agnostic active learning, and propose a new general active learning algorithm which achieves it.  Remarkably, the optimal query complexity admits a leading term which is $\textit{always}$ strictly smaller than the sample complexity of passive supervised learning (by a factor proportional to the best-in-class error rate).  This was not previously known to be possible.  For comparison, in all previous general analyses, the leading term exhibits an additional factor, such as the disagreement coefficient or related complexity measures, and therefore only provides improvements over passive learning in restricted cases.  The present work completely removes such factors from the leading term, implying that $\textit{every}$ concept class benefits from active learning in the non-realizable case.  Whether such benefits are possible has been the driving question underlying the past two decades of research on the theory of agnostic active learning.  This work finally settles this fundamental question.

Agnostic Active Learning Is Always Better Than Passive Learning
Steve Hanneke
Department of Computer Science
Purdue University steve. www.eeeeeneeeaaillcccmom com
Abstract
This work resolves long-standing open question of central importance the theory of active learning, closing a qualitative and quantitative gap our under- standing of active learning in the realieale case. We provide the first sharp characterization of the optimal first-order query complexity of agnostic active learning, and propose a new general active learning algorithm which achieves it. Remarkably, the optimal query complexity admits a leading term which is always strictly smaller than the sample complexity of passive supervised learning (by factor proportional to the best-in-class error rate). This was not previously known be possible. For comparison, in all previous general analyses, the leading term exhibits an additional factor, such as the disagreement coefficient or related com- plexity measures, and therefore only provides improvements over passive learning in restricted cases. The present work completely removes such factors from the leading term, implying that every concept class benefits from active learning the non-realizable case. Whether such benefits are possible has been the driving question underlying the past two decades of research on the theory of agnostic active learning. This work finally settles this fundamental question.
1 Introduction
Active learning is a well-known powerful variant of supervised learning, in which the learning algorithm interactively participates in the process of labeling the training examples. this setting, there is a pool (or stream) of unlabeled examples, and the learning algorithm selects individual examples and queries an oracle (typically a human labeler) to observe their labels. This happens sequentially, that the learner has observed previously- to query next. The intended purpose of active learning to reduce the overall number of labels necessary for learning to given accuracy, called the query complexity. We are therefore particularly interested in using active learning in scenarios where its query complexity is significantly smaller than the number of aadomly-samplee training examples which would be needed to achieve the same accuracy, called the sample complexity of passive supervised learning.
labels before deciding which example
Active learning has not only been incredibly useful for many practical machine learning problems (e.g., Cohn et al., 1996; Tong and Koller, 2001; Zhu al., 2003; Olsson, 2009; Settle, 2012: Ren et al., 2021; Mosqueira-Rey et al., 2023) but has also given rise rich and nuanced theoretical literature (c.g., Dasgupta, 2005, 2011; 10 Balcan et al., 2009; Hanneke, 2007b, 2014; Zhang and Chaudhuri, 2014; Hanneke and Yang. 2015; see Appendix A for detailed survey). Moreover, the insights and techniques discovered this literature have had tremendous influcnce on other branches of the learning theory literature (c.g.. Awasthi et al., 2014; Foster et al., 2021; Hanneke, 2009b, 201 6a.b, 2024; Zhivotovskiy and Hanneke, 2018; Simon, 2015; Balcan and Long, 2013; EI- Yaniy and Wiener, 2010; Balcan al., 2022).
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Within the literature on the theory of active learning, a central topic which has garnered far the most interest that of agnostic active learning: that is, the study of active learning algorithms capable of providing performance guarantees even in noisy or otherwise non-realizable learning problems, without assumptions on the form of the noise. This line of work was initiated by the groundbreaking A algorithm (Agnostic Active) of Balcan, Beygelzimer, and Langford (2005, 2006, 2009) (with its general analysis later given by Hanneke, 2007b) and concurrently a lower bound analysis of Kääriäinen (2005, 2006) (later strengthened by Beygelzimer, Dasgupta, and Langford, 2009). These results were later refined and extended in numerous ways. However, throughout this two-decades long history, there has persisted significant gap between the sharpest known upper and lower bounds on the optimal query complexity. Moreover, this gap represents an important qualitative distinction: while the lower bound is always smaller than the sample complexity of passive learning, the existing upper bounds only reflect such improvements under further restrictive conditions (e.g.. bounded disagreement coefficient). Thus, the issue of resolving this gap is of central importance to this subject, since it has implications for answering the question:
Does every concept class admit benefits from using active learning instead of passive learning?
The main contribution of the present work is to establish that this is indeed true, and in fact the known lower bound is always attainable. To achieve this, we introduce new algorithmic principles for active learning (the AVID principle), improving concentration of error estimates via adaptively isolating regions where the error estimates have high variance and allocating more queries to such regions.
2 Background and Summary of the Main Result
Let C be any concept class' (a set of functions X' - {0, 1} on a set X' called the instance space) and denote by d = VC(C) the VC dimension of C ( (Vapnik and Chervonenkis, 1971; see Definition 4). Let P be (unknown) joint distribution on X' x {0, 1). and define the error rate of any classifier h : X' + {0. 1 as pr == P((x, y) h(x) + y). In the active learning problem, there is a sequence (X1, Yi)........ (X,; Y.) of i.i.d. samples from P, but the learner initially only observes the X, values (the unlabeled examples). It then has the capability to query any example X,, which reveals the corresponding true label Y., in sequential manner (i.e., it chooses its next query X after observing the label Y, of its previous query point X2). After number of such queries, the learner returns a classifier h. The goal is to achieve a small excess error rate cry(() I inffeec er (h) + while making as few queries as possible. We are particularly interested in quantifying the number of queries sufficient to achieve this, as function of e and the value of the best-in-claa error rate in inlnec er (h)), known as a first-order query complexity bound.
Specifically. for any e, 5, B E (0, 1), the optimal query complexity, QC, 8; 3,C), is defined as the minimal Q N for which there exists an active learner Aa such that (for a sufficiently large number m of unlabeled examples), for every P' with infaeс e S 3, with probability at least 1 - 8, As makes at most Q queries and returns h. satisfying (h) S infnec: ( + E. The main quantity for comparison is the sample complexity of supervised passive learning. A passive learner Ao simply trains n labeled training examples Yi), (Xn, Yn) sampled i..d. from P to produce classifier h. For e, 8, (0, 1). the optimal sample complexity of passive learning, Mp(e, 8; C). is defined as the minimal size n E N of such a training sample for which there exists a passive learner App such that, for every P with inf (h)) S B, with probability at least 1 - 5, Ap returns à satisfying (h) S infAec er (h) + e. We remark that, in both the active and passive cases, these definitions place no restrictions on the computational efficiency of the learning algorithms, but rather focus on the data efficiency, which is our primary interest in this work (see Section G).
Since both the query complexity and sample complexity concern the number of labels sufficient for learning. it is natural to compare QC, 8; 8, C) with Mp(E, 8; B, C) to quantify the benefits of active learning. Thus, the primary interest in the theory of agnostic active learning is quantifying how much smaller QC, (e, 5; S, C) is compared to Mp(e, 8; B, C). Since interest is agnostic learning, it is most interesting to focus on the regime where P is far farfrrom-realizable: that is, where 3 is much larger than s. In this regime, it is well known from the works of Vapnik and Chervonenkis (1974); Devroye and Lugosi (1995); Hanneke, Larsen, and Zhivotovskiy (2024b) that the optimal sample
'To focus on non-trivial cases, we suppose [C] 2 3. We also suppose X' is equipped with a o-algebra specifying its measurable subsets, and we adopt the standard mild measure- measure-theeoeetc restrictions on the alalgerra and the class C from empirical process theory: namely, the image admissible Suslin property (Dudley, 1999).

---

complexity of passive learning satisfies Mp(e, (: ( (d (#)) In comparison.
the known lower bound for active learning is QC 6; 2 (d+ log( (Kääriäinen, 2006; Beygelzimer, Dasgupta, and Langford, 2009). Thus, the strongest improvement we might hope from active learning is a factor of |3 (representing the best-in-class error rate).
However, in the prior literature, this 5-factor improvement has only been demonstrated in upper bounds under restrictions to C or P. Specifically, every general upper bound on (s, B, C) in the literature has the form c(3)d 2 For instance, one commonly appearing such quantity c(3) is the disagreement coefficient 0(3) of Hanneke (2007b). We refer the reader to Appendix A for detailed survey of such quantities c(3) which have appeared in the literature. Importantly, for all such upper bounds in the literature, the corresponding factor c(3) has the property that there exist simple classes C and distributions P for which c(3)= 2 2 (see Hanneke and Yang. 2015; Hanneke, 2016b, 2024): for instance, even for linear classifiers on ? or singletons on N. Note that when c(3) 2 3. query complexity c( 2 becomes no smaller than d d the sample complexity of passive learning. Moreover, one can show that avoiding such d d query complexities would require new algorithmic techniques (see Appendix A).
द (ignoring logs), where c(3) is (C, Pe-dependent quantity.
Naturally, the question of refining such c(3) factors has been a subject of much interest for many years. In particular, it has remained open whether such factors might even be avoided entirely, that the 3-factor improvement might always be achievable. In a series of talks, I conjectured that the lower bound 2 - + +lo(())) is always sharp (in the far-from-realizalee regime), and even offered a sizable prize for solution (along with lower-order terms) (e.g., Hanneke and Nowak, 2019).
Contributions of this Work: In the present work, we completely resolve this question. We prove that (in the above regime) (c,
e g' (d + log (b)) In other words, the 8-factor improvement is always achievable, the known lower bound is sharp, and there is no need for restrictions on (C, P) or additional factors c(3) as appear in all prior works.
Extending to the full range of B, the more-genert form of the bound we prove also includes an additive lower-order term to account for the small-B regime. In the simplest such bound (Theorem 1),
this lower-order term is simply Ô so that the general form is QC, (e, 6,8,C) = Ō a (Theorem 3 and Appendix F refine this lower-order term for some classes). For comparison, the general form of the passive sample complexity is (p C)- é(d + - We note that,
even in the hearly-realizable regime (8 = Ō())) is known that e is lower bound on the query complexity for many classes C (Dasgupta, 2005; Hanneke, 2014; see Appendix D of Hanneke and Yang, 2015), so that this term is sometimes unavoidable, and hence the benefits of active learning can wane in the nearly-realizable regime. Likewise, the lower bound d implies the benefits regime (8 = (())). In contrast, as discussed above. in
can also diminish in the very-high-nn the realizable regime (Vs- < B < 1), the bound is of order d reflecting a f-factor improvement over the sample complexity of passive learning d d.. Additionally, the intermediate regime of moderate- size / (i.e., E < 3 /ē) also exhibits improvements over passive learning for all C: in this regime, Mn,ee, 8; 3, C) 22 ((( whereas QC, 6; B, C) Ō( < d d
reflecting an improvement by a factor Ō ($)) Altogether, this result reveals a aheviously-unnnowe and truly remarkable fact: QC,(s, 6; B, C) < Mp(c, 5; 3, C) in all regimes e < B < 1, or in other words, in all regimes outside the really-e and very-high-noise cases, the following is true:
For every concept class C, the optimal query complexity of agnostic active learning is strictly smaller than the optimal sample complexity of agnostic passive learning.
This result resolves an important long-standing open question central to the past two decades of research on the theory of agnostic active learning.
3

---

3 Main Results
Formally, the following theorem expresses the new upper bound, together with known lower bounds for comparison (Kääriäinen, 2006; Beygelzimer, Dasgupta, and Langford, 2009; Hanneke, 2014; Hanneke and Yang, 2015). A more-detailed version of the result appears in Theorem 5 (Appendix C).
Theorem 1. For every concept class C, letting d VC(CC, VE, E (0. 1/8), AB 1)
C) 0
0
d log (1))) +
and (C,(e,6)).)) = 12 00 = (d log (1))
Moreover, for every d E N there exists C with
VC(C) = d such that QC, 8: B, C) Ω _ (d log ())
We provide a new general active learning algorithm Aavid achieving this upper bound in Section 4. Importantly, the algorithm does not need to know 3 (or anything else about P) to achieve this guarantee: i.e., it is completely adaptive to the value 3. Moreover, the number of unlabeled examples the algorithm requires is only ((d ((d 8 62 + :). of the same order as the sample complexity of passive
learning; can also adaptively determine how many unlabeled examples to use without knowing 3.
The AVID Principle: The main innovation underlying the algorithm, which enables it to achieve this query complexity, represents new principle for the design of active learning learning algorithms, which we call Adaptive Variance Isolation by Disagreements (AVID). The algorithm adaptively partitions the instance space X' into regions, with the aim of isolating a region A C X where is most challenging to learn, due to exceptionally high variance in the error estimation problem in the region (where A will be defined as a union of pairwise disagreement regions witnessing the high variance, carefully selected to ensure Px(A) = (33).. It then allocates disproportionately more queries to this challenging region compared to the (considerably-easiie
remaining region X' A. This idea has interesting connections to techniques explored in other branches of the literature (e.g., Hanneke, Larsen, and Zhivotovskiy, 2024b; Bousquet and Zhivotovskiy, 2021; Puchkin and Zhivotovskiy, 2022), discussed in Appendix A.
3.1 Refinement of the Lower-order Term for Some Classes
The AVID principle already suffices to achieve the query complexity bound in Theorem 1. Moreover, for most concept classes of interest, the query complexity bound in Theorem 1 is already optimal, matching a lower bound (up to log factors in the lower-order term): e.g., linear classifiers in &&& k > 2 (Dasgupta, 2005; Hanneke, 2014; Hanneke and Yang, 2015). However, while the lead term ga E" (d+ (o++og(5)) (og())) ) is already optimal for every concept class C, there do exist some special classes C for which further refinement of the lower-order term é is possible (e.g., threshold classifiers ((,,o)) on R). As our second main result, we provide a refinement of the upper bound in Theorem I to capture such special classes, thereby establishing query complexity bound which is nearly optimal for every concept class.
Since such refinements are only possible for some concept classes, the expression of this refinement necessarily depends on an additional complexity measure of the class C. We prove that the optimal lower-order term in the query complexity is well-captured by quantity known as the star number of C, introduced by Hanneke and Yang (2015). In particular, Hanneke and Yang (2015) showed that the star number precisely characterizes the optimal query complexity in the realizable case (3 = 0); since this a limiting case of agnostic learning, it natural that this quantity plays a crucial role in characterizing the optimal lower-order term. The formal definition is as follows.
Definition 2. For any concept class C, the star number s = s(C) is the supremum n E N for which Bri..... ... In E X and he, hi...., hn E C such that Vi.j [I....,n), n). h,(1,) # ho(a,) i = j. ......,,,,
The star number essentially describes scenario which is intuitively challenging for active learners in the realizable case, wherein there a set of instances xy and a default labeling ho(r,)) but the target concept is some ht which differs from tg at just one instance 2i, unknown to the learner (which

---

must therefore query nearly all of these 2j instances. searching for the special point I;, in order to identify the target concept h,). Hanneke and Yang (2015) provide numerous examples calculating s for various concept classes. For instance, thresholds on IE have s = 2 and decision stumps on RR have s = 2k. However, is worth noting that g is typically large (or infinite) for most concept classes of interest in learning theory (e.g., 5 = oo for linear classifiers on R2 k 2 2). This fact is important to the present work, since Hanneke and Yang (2015); Hanneke (2016b, 2024) have shown that the c(3) factors (discussed in Section 2 above) appearing in all previous general upper bounds all become no smaller than $ A 3 in the worst case over distributions (subject to the 3 constraint). Thus,
22 from the prior literature become no smaller than d in the worst case when 5 = c0. sense, this means Theorem 1 actually most interesting the (typical) case of 0o, since no previously known upper bounds offer any improvements over passive learning in this case (without further restrictions to P), in stark contrast to Theorem which has no dependence on s and provides improvements over passive learning in the lead term for every concept class.
all general upper bounds c(5)d 8
Nonetheless, the special structure of classes with < 0O turns out to provide some additional advantages for active learning, so that in order to state a general query complexity bound which is optimal for every concept class C, we need to account for this structure, via dependence on in the lower-order term. Specifically, by combining the AVID principle with existing principles for active learning (namely, disagreement -assee queries), we can take further advantage of the power of active learning. thereby enabling a refinement of the lower-order term for classes with < co. The following result presents a new general query complexity bound reflecting such refinements, together with known lower bound for comparison (due to Kääriäinen, 2006; Beygelzimer, Dasgupta, and Langford, 2009; Hanneke and Yang, 2015). The implication that this new upper bound is nearly optimal for every concept class C (including the lower-order term, up to a factor of d, which we discuss below). A more-detailed version of the result appears in Theorem of Appendix C (and distribution-depeedentt variants are presented in Appendix F, replacing with variants of the disagreement coefficient).
Theorem 3. For every C, letting VC(C) and 5 = sCC). VE, 5 E (0,1/8), AB E 1].
32
S 8 1)
(C,(6, 0
d + log
g2
1 +
!
and QC, s
d + log
c2
We may note that the upper bound in Theorem is an immediate implication of Theorem (we have stated Theorem I separately merely to emphasize that the improvements over passive learning are available without any special properties of C such as finite star number). Theorem provides refinement in the lower-order term compared to Theorem I when < 1. In particular, for < co, the asymptotic dependence on in the lower-order term is log" (t)- We leave open the question of whether this can be further refined to log log(2) (2), which would match a known lower bound on this dependence for all infinite classes (Kulkarni, Mitter, and Tsitsiklis, 1993; Hanneke and Yang, 2015). The only sigmificant difference between the upper and lower bounds in Theorem 3 the factor of in the lower-order term. I conjecture this term can be further refined to Ö(s ^ d). which is known to be sharp for some classes (Hanneke and Yang, 2015), and would fully answer question posed by Hanneke and Nowak (2019). Beyond this, is known that a gap between such lower-order terms in general upper and lower bounds is unavoidable if the only dependence on C is via d and s. Specifically, follows from arguments in Appendix D of Hanneke and Yang (2015) that for some classes E this term should be ( A 9) while for other classes C the term should be Ô(s A 1 + d). Thus, obtaining 2
matching (big-O) upper and lower bounds would require introducing a new complexity measure reflecting the distinctions between these types of classes, which we leave as an open question.
4 Algorithm and Outline of the Analysis
We next present the algorithm achieving Theorems 1 and 3 and sketch of its analysis (the complete formal proof is given in Appendix E). Before stating the algorithm, we first introduce a few additional definitions and convenient notational conventions.
5

---

Error and disagreement regions: For any function h : X + {0,1). define its error region
hR(h) == ((x,)) E X' x {0,1} h(x) y}.
In particular, note that (h) P(ER(h)) For any set V S C define the region of disagreement:
DIS(V) == {z= E X : 3f.g E f(r( + g(z)}. For any two functions f.g : X' + {0,
abbreviate by {f + g) == fr X: f(z) + g(z)} their pairwise disagreement region.
adopt convention of treating sets A C X' as For instance, for functions f.g, h X + {0, 1). we may write ER(h) n {J 4 9). which, by the above convention, is interpreted as (R()) + g) x {0, 1}). We also overload notation for set intersections to allow for intersections of sets with sequences: that is. for any set 2, sequence S = (=11,...,22m -m E 2m and set A C 2, we define SnA as the subsequence {2+ : S m, 2 E A). and likewise S¹,A A == Sn A). We also apply these conventions in combination: i... for a sequence S (X x {0. 13) and set A S X, we define S in A == S (A x 1)) and S \ A == Sn ((X \ A) x {0,13)
Overloaded set notation: For convenience,
notationally interchangeable with their labeled extension A x 10 S X x {0,
Empirical estimates: We will make use of empirical estimates of quantities such as (h)(h) and Px(f + g). For any set 2 and sequence S { {21...., 2m E 2m, for any set A 2, detine the empirical measure: (A(A) == 1 1 n Al
(X m i= 1[2 A]. Again, we also
1 E
m apply these conventions in combination: i.c., for S E
x {0,1))* and A S X, we define (A(A) :- Ps(A x {0, For any sequence S E (X' {0, and function h : X {0,
define its empirical error rate (or empirical risk): érg (h) Ps (ER())).
Decision lists: We will often express decision-list aggregations of functions f.g X - {0, 1). For instance, for any set A C X, we may write = /xxA + gla to express a function h with h(x)= = f(z) for & A and h(x)) = g(x) for x E A.
4.1 The AVID Agnostic Algorithm: Adaptive Variance Isolation by Disagreements
We are now ready to describe the algorithm achieving the upper bounds in Theorems 1 and 3 (for full formality, some additional technical minutiae for the definition are given in Section C). Fix any values 8 E (0.1) (the error and confidence parameters input to the learner). Fix
any distribution P (unknown to the learner) and let (X,, Yi),..., (Xm, Ym) be independent P- distributed random variables (for any sufficiently large m, quantified explicitly in Theorem 5). The algorithm is stated in Figure 1, expressed in terms of certain quantities and data subsets de- 11
fined as follows. 2 Let C == To N ;= (2) and for each & E N define EY == C²- and my :- ((+ + (dlog( 1 + log(+))) (see Section C for the precise constants). In Step C denotes an appropriate universal constant (see Section C). As defined in Figure I, the algorithm for different purposes, and to complete the definition of the algorithm we next specify how these data subsets are defined in the algorithm. Sxrieeeeit
makes use of different portions of the data (S), Sg. Sy St))
We first split the initial 2M, == > my examples ((X,.Y))..... Yi),.., (X2M,; Y2M,), }} into con- secutive disjoint contiguous segments S!...., St_, St...., S.... with the segments St. and S being of size mg. The algorithm also allocates disjoint segments (S%, 5g of the remaining data {(X,, Y,): : 2M1 <i m.. but does so adaptively during its execution. Specifically, if and when the algorithm reaches Step 2 with value k or reaches Step 9 (in which case let k = N + 1), for the value i and the set A,, as defined at that time in the algorithm, it constructs a data subset SZ. allocating to Sh the next m/ consecutive examples which have not yet been allocated to any data subset St. Se. $2,,0 St. fresh, meviously-unused, examples), where, letting P.: := 2P5; (A,,), we define m/ o 24 (d + log( 1oo()++=+)) (see Section C for the precise constants). Similarly, if and when Eg
the algorithm reaches Step 5 with some values of (k, i), it constructs data subset S allocating to $2 the next my consecutive examples which have not yet been allocated.
For simplicity, we have expressed the algorithm as representing a set of surviving concepts V. C C. However, it should be clear from the definition that running the algorithm does not require explicitly storing Vi. Rather, the various he), where the constraints are merely the inequalities which would define the sets Vyr, K' < k. and Step 3 is then replaced by simply adding one more constraint the constraint set.
of this set be implemented as constrained optimization problems (in Steps 4-6 and

---

Algorithm Aavid
Input: Error parameter &, Confidence parameter 6, Unlabeled data X1,..., . Xm
Output: Classifier
0. Initialize = i 0, Au Vo
1. For = ..
2. Query all examples in 5 DK-1 Ai, and S n n
3. V& h V : (h) (ha)) +
4.
V or ot (hx)) < minnev, ( - 20, Then Return h == hy
5.
While max Pst, (If + 9) A,) > EL+2
6.
(f19) argmax ('vv? Pss. (1/ + g'} \ A.) A+t1 + U + g). and update + i+1
7.
8.
f++1
9.
Query all examples s n Dy Aiy. and S2, O Divis and Return à == Pey+:
Figure 1: The AVID Agnostic algorithm. Notations N, D Sk, h2s Sh. Sg. Sk ert defined in the text.
To complete the definition of the algorithm, we define D cr and hys appearing in the algorithm, follows. For each value of k encountered in the 'For" loop, well for k = N + 1 in the case the algorithm reaches Step 9, define (where Va-1 and Ai, are as defined in the algorithm):
DR-1 = DIS(Va-1):
Yh, ( Pst (ER(H) DE-1 \AW + Psş (BR(h) nii));
(1)
V (/ + (/4ol\A, + h2l :s.g V1-1, C),
(2)
and hg ér) (h)) REV
This completes the definition of the Avvid algorithm.
We remark that the examples in Si, and St are never queried in the algorithm, and thus the algorithm (necessarily) only uses the unlabeled X; values in these data subsets (to estimate certain marginal Px probabilities), so in fact these can be regarded as unlabeled data subsets. Similarly, the algorithm only queries portion of 5% and S2. and the remaining unqueried portions are in fact never used by the algorithm. For notational simplicity, we do not make these facts explicit in the notation.
Description of the algorithm: We briefly summarize the behavior of the algorithm (with explana- tions following in Section 4.2). As the algorithm iterates over rounds it of the 'For' loop. maintains partition of the space into region Ai, and its complement X' A In each round, the algorithm refines a set V& of surviving concepts from C, aiming to prune out suboptimal concepts (Step 3). There are crucial aspects of this, both in how the estimates of c are defined, and in the choice of function hg to which we compare. For the purpose of error estimation, Step 2 queries number of random examples in X \ A., (or rather, the slightly smaller region D Air, since examples in X', \ D3-1 are uninformative for estimating error differences) and a number random examples in Ai,. It uses the examples from each of the two regions to estimate the error rate of each h in that region, and combines these two estimates into an overall error estimate er (h) as in (1). It then prunes suboptimal concepts from Vk-1, removing all Vk-1 having estimated error ( > e + G4. The reason (h)) estimates error rates the two regions separately that, it will turn out, require disproportionately larger number of samples to accurately estimate the error rates the region Aig compared to the complement X' \ A : for the latter, we use the samples in S n D \ Ai, (queried in Step 2), where S has a modest size my = = while for the former use the samples in SĀ Aig (also queried in Step 2), where S has potentially larger size m4 roughly é (Fx(A))))) The other crucial aspect in Step 3 is how we define o
the function ing to which we compare. For this, rather than (the seemingly-natural idea of) simply comparing to the smallest (i)) among / E Ve-1. we instead compare an even smaller value: the smallest 2 among more-complex class ViL defined in (2), comprised of decision list
7

---

functions which use one concept by for predictions in Ai.- and use (equivalently) majority vote of three concepts f. 9, hı for predictions in X' \ A,, h& is defined minimizer of cr in f--1 as in (3). This use of a more-complex comparator function is critical for certain parts of the proof (namely, keeping Px (A,, small). However, given that hi is chosen from a more-complex class, it becomes possible that ha may be substantially better than all h E Vi. In this event, the algorithm terminates early and returns hy (Step 4). Otherwise, if it makes it past this early sarly-stppping case, its next objective is to define the region A for use in the next iteration. This occurs in the 'While" loop (Steps 5-7).
On each round of this loop, it uses a fresh data set S of size m& - to check whether there exist f.g E V& significantly distant from each other in the region X' \ A, (Step 5). If so, it adds their pairwise disagreement region {ff + g) to the A; region to define A;+1 and increments i (Step 7). It repeats this until no such pair f, g exists, at which time it defines i = (Step 8) and proceeds to the next iteration of the 'For' loop. After N = ((log(1/E) such iterations, returns h (Step 9).
We note that the algorithm's 's returned classifier i might not an element of C (known as an improper learner), but rather can be represented as a (shallow) decision list of concepts from C. This aspect is quite important to certain parts of the proof, and we leave open the question of whether Theorems 1 and 3 are achievable by a proper learner (see Appendix G). We also remark that the DR-1 set is only needed for establishing Theorem 3: the algorithm achieves the query complexity bound in Theorem even if we replace D with the full space X' everywhere.
4.2 Principles and Outline of the Proof
Next we explain the high-level principles underlying the design of the algorithm, highlighting the two key innovations compared to previous approaches, which enable the improved query complexity guarantee (namely, separating out the A., regions, and the definition of ha).
Empirical localization: The principles underlying the design of the algorithm begin with a familiar principle from statistical learning: empirical localization (Koltchinskii, 2006; Bartlett, Bousquet, and Mendelson, 2005). Specifically, the uniform Bernstein inequality (Lemma 7) implies that for an i.i.d. data set S, the sample complexity of uniform concentration of differ- ences (fér(()) - (g) - (erp(f)- - erp(g) becomes smaller when the diameter diam supr.gec (S + g) of the concept class is small, noting that (x + g) bounds the variance of loss differences (x) * y] [[)(z) # y]. Quantitatively, for any 0 < e' < diam(C), ( d (d samples S suffice to guarantee ((rr((f) - cts( - (er - erp(g))) S This fact leads to natural well-known algorithmic principle, wherein we can prune from C con- > E (as the above inequality implies these verifi- ably have suboptimal error rates), leaving a subset Ví of surviving concepts, while preserving h* E Vi, where h" == argminpec p(h). Moreover, if these surviving concepts V have diam((1) < dCa we get an improved concentration guarantee for (fs - (g) among fig E Ví' from the uniform Bernstein inequality, which enables us to prune even more con- cepts from Ví. leaving a set Vid of surviving concepts, and so on for V2, Vi,.... Quantitatively, we can combine this with schedule of resolutions Ek. so that long as h- E V%-1 and diam (aan(V)))= S Eks an i.idd data set St of size my Ō d ā(d d (V(_1)) suffices to ot
cepts h having (h) minwec érs(h') ers
Ex
guarantee ((ērg (f) - =()(( - (erp(f) eip(a)) s gt. enabling us to further reduce to subset V/d { h Vi-1 : st (h)= minnev,_ (t's + $ } for which all h E Vid have (hr(h) (h*) < 28t, while preserving h Vi- Iterating this N (())c(()) times (recalling E = k) results subset V of concepts with cr (h) SE.
Disagreement- active learning: An additional observation, underlying many active learning algorithms (disagreement based methods), is that the above argument still holds while replacing ct (h) with Psp (ER(h)nD( where D'_1 == DIS(V( ). To see this, note that Vh, h E V/-1+ Pss (ER(h) D/_ -)- (ER(H)DD)))) = é (A) st é (h'). Thus, we may equivalently define V/ {NE 1 Pst (ER(h) DD S minweey__ Pet ( + & }. Moreover, as long as diam(V/_) < kk, we have Px (D < s5x (Hanneke and Yang, 2015). Since the quantities in V%2 only rely the labels of examples in D/_1 n.S. constructing V/d only requires
8

---

number of queries ((SEgm)))) A mg. Summing over k. these queries total to at most the claimed lower-order term in Theorem 3 (though note that even without this D refinement we still recover the lower-order term from Theorem 1). So far, this is all essentially standard reasoning commonly followed in the prior literature on active learning (e.g., Hanneke, 2009h, 2014; Koltchinskii, 2010).
Handling non-shrinking diameter: However, the above algorithmic principle breaks down if we reach k with diam(V) + ((x)). This failure can easily occur in the agnostic setting, where it is possible for the set V above to contain multiple relatively-good functions f.g which nevertheless far from each other.² This is the motivation for the first key innovation in Aavid: namely, if we ever reach such a k where the V&g set does not naturally have diam(VV) S Ek+1 (as tested in Step 5), the algorithm removes portion of the space X' to artificially reduce the diameter. Specifically, it identifies a pair f.g E Vi with Px(f & g) > Ek+1 (intuitively, an obstruction to having low diameter) and separates out their pairwise disagreement region (f + g) from the region of focus of the algorithm (Steps 5-7).* Having set aside this region, the algorithm continues, focusing the remaining set X' \ {f # g). This step is repeated, and these set-aside regions {f & 9) are altogether captured in the set A; (Step 7). Thus, we repeatedly find pairs f.g E V2 with [ A g} A.) Ek+1 (Steps 5-6) and add {f + 9} to A; (Step 7) until the diameter of V22 on X \ A; is reduced below 1R+1- At that point, the algorithm proceeds to the next round (k + + 1). On the next round k since we have (artificially) ensured the diameter of Vx-1 is at most EN in the region& X' \\ Aie. the uniform Bernstein argument implies my examples St suffice to guarantee every f.g E V have Pss (ER(f) n Da-1 \ A..) - Pss (ER(g) n D \ A..) within + fo of P(ER(f) A.,) P(ER(g) \ ). 20
Error in the As, region: There remains the issue of estimating error rates in the A., isolated region. For this, the algorithm uses data set S2 of size m' = Px (Aic) queries all examples in Sin and uses these estimate the error rates P(ER(b)nA;, ) in the Ai, region. By refinement of the uniform convergence bound of Talagrand (1994) accounting for an envelope set Di, (Lemma 8), this number m4. of examples suffices to ensure Ps (ER(h) n nA.)) - ((ER(h) n A.,)) I
Ek for 40"
every h E C. Combining this with the above error-diiferences estimates in the X' A., region, we can guarantee that the functions f.g VA-1 have [(+)]' (f) - cik - (cr (g) S &+. recalling the definition of ér! from (I), Altogether, we conclude that, as long as ht E Vk-1. + & } would contain only functions satisfying ehp(h) - (h* S 2 while preserving h²* E Vg" The actual definition of V in Step is only slightly different from this, for reasons we discuss next.
a set V/" := { E Vh-1= : ét,, (h) S minwer, erk
Bounding the size of Ai.: Since the number of queries in SAnA, is (. /EE if we hope
to achieve a query complexity with lead term Ōd (T) it is crucial to guarantee P& (A..) ) = 0(3).
This is the motivation for the second key innovation in Aavid: defining the update in V by comparison to the function hig in (3), rather than the best h' E Va-1. This turns out to be the most subtle part of the argument, requiring precise choices in the design of the algorithm. The essential argument is as follows. Suppose the algorithm reaches Step for some (k, i). so that it will add {f + g} to the A, region. We then want to argue that P(R ) n {f # g} \ A.) = [( # g) A.)): that is, each time we add to A,, we chop off a portion of ER(h") of size (under P) proportional to the increase in Px (A,). Clearly if we can show this is always the case, we will inductively maintain (A, = O(3), resulting in the claimed leading term in the query complexity. Now, to show this indeed occurs, we first note that one of f,g must eIr on at least half of {f + g} \ A w.l.o.g. suppose it is f: that is, P(ER(J) n [s & g} A., Z ( # g} \ Ai,)) Now consider a function f fl(s=9)A,, + h h
flA,, which replaces f by h- in the region (S * 9) \ Ai,. Note that, if h Vi-1, then f" Vi defined in (2). Since hg has minimal ér
$ 'For instance, for C the class of intervals 1[a.0) on R. with Px = Uniform((0) (00 1)) and P = 1 = 1 [o.//4j/B/s._((),,, the concepts 1 [0.1/4] and [[3/4,1] are both optimal among C. yet distance 1/2 apart.
"This reasoning is somewhat reminiscent of the motivation for the splitting approach active learning (Dasgupta, 2005), differing only in how we resolve the obstruction: whereas splitting would resolve with queries to eliminate one element from each obstructing pair, here we resolve it by subtracting the pairwise disagreement region from the region of focus X') A, (see Appendix A.2.3). This idea also related to a technique of Hanneke, Larsen, and Zhivotovskiy (2024b) for agnostic passive learning. discussed in Appendix A.3.

---

and f E Vy implies (f) S (hx) + & extending the above concentration of among V 1-1-
orle differences to functions in R- (with appropriate adjustment of constants in mr. m)) implies efp(f) - (fp(f) - 2 Thus, since f" and f only disagree on {f # g} \ Aig. we have
Px(Uf + g} \ A.)) - P(ER(N") n nJ + 9) \ Air)
2
Ek - - P(ER(f) n (f * a) \ A..) - ((ER(H") (f # o) \ - s 2
C"
In other words, (hER(h") n (f + g) A,)) 2 * g - This is almost what we wanted, aside from having Ai, in place of A. We then argue P(ER(h") {f + g) A.) > P(ER(A") n {5 * g}
- - + g) + + g) \ A.). which (by the above) at least Px p * g) A.) {P((( وg) A,,) 25.
Since both ʃ.9 E V we know Px( * gg) Ai,) S Ex, so that this lower-bound is at least Px[ o g) A st 2 On the other hand, for appropriate constants in my, the condition in Step 5 allows us to upper-bound & in
terms of (ff + Ar): namely, (f + g} At) 2 Ek for e with C2 < A C" Thus, we have ((ER(h")N( $ g) A.) 2 (1 (1-5 $ - 26) Px }g) A.). Since each D., is a union of such (disjoint) {s + g) A, regions (i < 3 P(ER(K")AA) 2 (1- 2 2 Px(A.,).
9.
hinges on having ht E V However, since bąg is a more-complex function than h², there is chance that h" & V2 after Step 3. For this reason, we have added the early stopping case in Step 4. By using slightly tighter concentration inequalities than used to update Vi, this step effectively tests that h2 is not so much better than all concepts in - 1 that ht might have been removed. Thus, if we make it past Step 4, we maintain h" E V so that the above argument applies on the next round, On the other hand, in the event that this test fails, we have effectively verified that iis is at least slightly better than all concepts in V (including h*), and we can safely return h4 in this case.
The early stopping case: The above argument for Px(A
Overall behavior: The effective overall behavior of the algorithm is to isolate in the region Di, the most-challenging part of the eтror estimation problem, due to the high variance (diameter) of the error differences in that region. It then allocates a disproportionately larger number of queries S Ai, to this region, toward estimating the error rates there. By comparing with the function hu (which separately optimizes errors in pairwise difference regions {f # 9} \ ) in the definition of Vn. we can maintain that A,, never grows larger than 0(3), so that the number of queries in S n Ai, does not grow excessively large. The remaining region 2' \ Ai, enjoys the property that the set Vi-1 has diameter I Ek. so that we can easily estimate error differences in this region by a uniform Bernstein inequality. Altogether, after at most N = Olog error rate, while using a number of queries as stated in the query complexity bound in Theorem 3. The formal proof is given in Appendix E.
rounds, this achieves the objective of excess
5 Conclusions and Summary of the Appendices
This work resolves a long-standing open question of central importance to the theory of active learning, proving that every concept class benefits from active learning in the non-realizable case. Quantitatively, we establish a new sharp upper bound on the optimal query complexity, with leading term that is smaller than that of passive learning by factor proportional to the best-in-class error rate.
The appendices include the formal proofs, along with additional contents. Appendix A presents a thorough summary of related work and background on the theory of active learning, as well as other works with techniques related to those used here. Appendix C presents remaining minutiae for the definition of Aavid, along with more-detailed version of Theorem 3, including formal claims regarding the number of unlabeled examples. Appendix E presents the formal proof of Theorem 3. Appendix F presents distribution distrbuution-depeneent refinements of Theorem 3. which replace the star number s with certain P-dependent complexity measures: variants of the disagreement coefficient. We further argue that the disagreement coefficient (r(e), as originally defined by Hanneke (2007b), provably cannot be attained as a replacement for in the lower-order term (by any algorithm), while on the other hand Avvid does achieve a lower-order term Ö(0r(3 + d)) We also present subregion- refinements of the algorithm and analysis, based on techniques of Zhang and Chaudhuri (2014) 4).. Appendix G presents extensions (multiclass classification, stream- based active learning), along with several open questions and future directions.
10

---

References
N. Ailon, R. Begleiter, and Ezra. Active learning using smooth relative regret approximations with applications. Journal of Machine Learning Research, 15(3):885-925 2014.
D. Angluin. Queries and concept learning. Machine Learning, 2(4):319-342, 1987. doi: 10.1007/ BF001 16828. URL https://doi 1ttg//0..007/BF000110
J. Asilis, S. Devic, S. Dughmi V. Sharan, and S.-H. Teng. Proper learnailiity and the role of unlabeled data. In Proceedings of the 36th International Conference on Algorithmic Learning Theory. 2025a.
J. Asilis, M. M. Høgsgaard, and G. Velegkas. Understanding aggregations proper learners in multiclass classification. In Proceedings of the 36th International Conference on Algorithmic Learning Theory, 2025b.
A. C. Atkinson and A. N. Donev. Optimum Experimental Designs. Clarendon Press, 1992.
P. Awasthi, V. Feldman, and V. Kanade. Learning using local membership queries. In Proceedings of the 26th Conference on Learning Theory, 2013.
Awasthi, M.-F. Balcan, and P. M. Long. The power of localization for efficiently learning linear separators with noise. In Proceedings of the 46th ACM Symposium on the Theory of Computing, 2014.
M.-F. Balcan and A. Blum. A discriminative model for semi- sumi-super learning. Journal of the ACM, 57(3):1-66, 2010.
M.-F. Balcan and Hanneke. Robust interactive learning. In Proceedings of the 25th Conference on Learning Theory, 2012.
M.-F. Balcan and P. M. Long. Active and passive learning of linear separators under log-concave distributions. In Proceedings of the 26th Conference on Learning Theory, 2013.
M.-F. Balcan and H. Zhang. Sample and computationally efficient learning algorithms under s- concave distributions. 2017.
M.-F Balcan, A. Beygelzimer, and Langford. Agnostic active learning. In NIPS Workshop on Foundations of Active Learning, 2005.
M.-F. Balcan, A. Beygelzimer, and J. Langford. Agnostic active learning. In Proceedings of the 23rd International Conference on Machine Learning, 2006.
M.F. Balcan, A. Broder, and T. Zhang. Margin based active learning. In Proceedings of the 20th Conference on Learning Theory, 2007.
M.-F. Balcan, A. Beygelzimer, and J. Langford. Agnostic active learning. Journal of Computer and System Sciences, 75(1):78-89, 2009.
M.-F. Balean, S. Hanneke, and J. Wortman Vaughan. The true sample complexity of active learning. Machine Learning, 80(2-3):111-139, 2010.
M.-F. Balcan, A. Blum, S. Hanneke, and D. Sharma. Robustly-reliable learners under poisoning attacks. In Proceedings of the 35th Conference Learning Theory, 2022.
Bartlett, M. I. Jordan, and J. McAuliffe, Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):138-156 2006.
P. L. Bartlett, O. Bousquet, and S. Mendelson. Local rademacher complexities. The Annals of Statistics, 33(4):1497-1537 2005.
E. Baum. Neural net algorithms that learn in polynomial time from examples and queries. IEEE Transactions on Neural Networks, 2(1):5-19, 1991.
E. Baum and K. Lang. Query learning can work poorly when human oracle is used. Proceedings of the International Joint Conference in Neural Networks, 1992.

---

G. Bennett. Probability inequalities for the sum of independent random variables. Journal of the American Statistical Association, 57((97):33 1962.
S. Bernstein, On a modification of Chebyshev's inequality and of the error formula of Laplace. Annales Scientifiques de I' l'Institut de la Société des Savanis d' L'Urriie, Section de Mathématiques, 1(4):38-49, 1924.
A. Beygelzimer, S. Dasgupta, and J. Langford. Importance weighted active learning. In Proceedings of the 26th International Conference on Machine Learning, 2009.
A. Beygelzimer, D. Hsu, J. Langford, and T. Zhang, Agnostic active learning without constraints, In Advances in Neural Information Processing Systems 23, 2010.
Boucheron, G. Lugosi, and P. Massart. Concentration Inequalities: Nonasymptotic Theory of Independence. Oxford University Press, 2013.
O. Bousquet. A Bennett concentration incquality and its application to suprema of empirical processes. Comptes Rendus Mathematique, 334(6):495-000, 2002.
O. Bousquet and N. Zhivotovskiy. Fast classification rates without standard margin assumptions. Information and Inference: Journal of the IMA, 10(4):1389-142) 2021.
O. Bousquet, S. Hanneke, S. Moran, and N. Zhivotovskiy. Proper learning, Helly number, and an optimal SVM bound. In Proceedings of the 33rd Conference on Learning Theory, 2020.
N. Brukhim, D. Carmon, I. Dinur, S. Moran, and A. Yehudayoff. A characterization of multiclass learnability. In Proceedings of the 63 Annual IEEE Symposium Foundations of Computer Science, 2022.
B. G. Buchanan. Scientific theory formation by computer. In Computer Oriented Learning Processes, pages 515-534. 1976.
A. D. Bull. adapivve sensing in nonparametric regression. The Annals of Statistics, 1:41-62, 2013.
G. Cavallanti, N. Cesa-Bianchi, and C. Gentile. Learning noisy linear classifiers via adaptive and selective sampling. Machine Learning, 13:71-102, 2011.
O. Chapelle, Scholkopf, and Zien. Semi-Supervised Learning. Adaptive Computation and Machine Learning Series. MIT Press, 2006.
K. Chaudhuri, S. M. Kakade, P. Netrapalli, and S. Sanghavi. Convergence rates of active learning for maximum likelihood estimation. Advances in Neural Information Processing Systems 28, 2015.
H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. The Annals of Mathematical Statistics, pages 493-507, 1952.
D. Cohn, L. Atlas, and Ladner. Improving generalization with active learning. Machine Learning, 15(2):201-22 22,,2,, 1994.
D. A. Cohn, Ghahramani, and M. I. Jordan. Active learning with statistical models. Journal of Artificial Intelligence Research, 4:129-145, 1996.
C. Cortes, G. DeSalvo, C. Gentile, M. Mohri, and N. Zhang. Active learning with region graphs. In Proceedings of the 36th International Conference on Machine Learning, 2019a.
C. Cortes, G. DeSalvo, C. Gentile, M. Mohri, and N. Zhang. Region-based active learning. In Proceedings of the n2nd International Conference on Artificial Intelligence and Statistics, 2019b.
C. Cortes, G. DeSalvo, C. Gentile, M. Mohri, and N. Zhang. Active learning with disagreement graphs. In Proceedings of the 36th International Conference on Machine Learning, 2019c.
C. Cortes, G. DeSalvo, C. Gentile, M. Mohri, and N. Zhang. Adaptive region-based active learning. In Proceedings of the 37th International Conference Machine Learning, 2020.
12

---

A. Daniely and S. Shalev-Shwarde Optimal learners for multiclass problems. In Proceedings of the 27th Conference on Learning Theory, 2014.
S. Dasgupta. Analysis of greedy active learning strategy. In Advances in Neural Information Processing Systems 17, 2004.
S. Dasgupta. Coarse sample complexity bounds for active learning. In Advances in Neural Information Processing Systems 18, 2005.
Dasgupta. The two faces of active learning. Theoretical Computer Science, 412(19), 2011.
Dasgupta, A. T. Kalai, and C. Monteleoni. Analysis of perceptron-based active learning. In Proceedings of the 18th Conference on Learning Theory, 2005.
S. Dasgupta, D. Hsu, and C. Monteleoni. A general agnostic active learning algorithm. In Advances in Neural Information Processing Systems 20, 2007.
M. DeGroot. Uncertainty, information, and sequential experiments. The Annals of Mathematcal Statistics, 33(2):004449, 1962.
O. Dekel, C. Gentile, and K. Sridharan. Selective sampling and active learning from single and multiple teachers. Journal of Machine Learning Research, 13(9):2655-266 2012.
G. DeSalvo, C. Gentile, and T. S. Thune. Online active learning with surrogate loss functions. Advances in Neural Information Processing Systems 34, 2021.
L. Devroye and G. Lugosi. Lower bounds in pattern recognition and learning. Pattern Recognition, 28: 08:1011-1018 1995.
I. Diakonikolas, D. Kane, and M. Ma. Active learning of general halfspaces: Label queries vs membership queries. In Advances Neural Information Processing Systems 37, 2024.
R. M. Dudley. Uniform Central Limit Theorems. Cambridge University Press, 1999.
S. Efromovich. Sequential design and estimation in heteroscedastic nonparametric regression. Sequential Analysis, 26(1):3-25, 2007.
B. Eisenberg. On the Sample Complexity of PAC-Learning using Random and Chosen Examples. PhD thesis, Massachusetts Institute of Technology, 1992.
B. Eisenberg and R. Rivest. On the sample complexity of PAC-leaming using random and chosen examples, In Proceedings of the 3rd Annual Workshop on Computational Learning Theory, 1990.
R. EI- Yaniv and Y. Wiener. On the foundations of noise-free selective classification. Journal of Machine Learning Research, 11(5):605-16411 2010.
R. El-Yaniv and Wiener. Active learning via perfect selective classification. Journal of Machine Learning Research, 13(2):255-273 2012.
V. V. Fedorov. Theory of Optimal Experiments. Academic Press, 1972.
R. A. Fisher. The Design of Experiments. Oliver and Boyd, 1935.
D. J. Foster, A. Rakhlin, D. Simchi-Levi, and Y. Xu. Instance -deendeed complexity of contextual bandits and reinforcement learning: A disagreement- based perspective. In Proceedings of the 34th Conference on Learning Theory, 2021.
Y. Freund, H. S. Seung, E. Shamir, and N. Tishby. Selective sampling using the query by committee algorithm. Machine Learning. 28:133-168. 1997.
E. Friedman. Active learning for smooth problems. In Proceedings of the 22nd Conference on Learning Theory, 2009.
R. Gelbhart and R. El-Yaniv. The relationship between agnostic selective classification, active learning and the disagreement coefficient. Journal of Machine Learning Research, 20(33):1-38, 2019.
13

---

E. Giné and V. Koltchinskii. Concentration inequalities and asymptotic results for ratio type empirical processes. The Annals of Probability, 34(3):1143-125 1216, 2006.
S. Goldman and M. Kearns. On the complexity of teaching. Journal of Computer and System Sciences, 50:20-31, 1995.
A. Gonen, S. Sabato, and S. Shalev-Shwarzz Efficient active learning of halfspaces: An aggressive approach. The Journal of Machine Learning Research, 14(1):2583-2615, 2013.
Hanneke. Teaching dimension and the complexity of active learning, In Proceedings of the 20th Conference on Learning Theory, 2007a.
S. Hanneke. A bound on the label complexity of agnostic active learning, In Proceedings of the 24th International Conference on Machine Learning, 2007b.
Hanneke. Adaptive rates of convergence in active learning. In Proceedings of the 22nd Conference on Learning Theory, 2009a.
S. Hanneke. Theoretical Foundations of Active Learning. PhD thesis, Machine Learning Department, School of Computer Science, Carnegie Mellon University, 2009b.
Hanneke. Rates of convergence in active learning. The Annals of Statistics, (9(1)3333-3,, 2011.
S. Hanneke. Activized learning: Transforming passive active with improved label complexity. Journal of Machine Learning Research, 136951146 2012.
S. Hanneke. Theory of disagreement- based active learning. Foundations and Trends in Machine Learning, 7(2-3):131-309, 2014.
S. Hanneke. The optimal sample complexity of PAC learning. Journal of Machine Learning Research, 17(38):1-15, 6a.
S. Hanneke. Refined error bounds for several learning algorithms. Journal of Machine Learning Research, 11(135)11555, 2016b.
S. Hanneke. The star number and eluder dimension: Elementary observations about the dimensions of disagreement. In Proceedings of the 37th Conference on Learning Theory, 2024.
S. Hanneke and A. Kontorovich. Stable sample compression schemes: New applications and an optimal SVM margin bound. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory, 2021.
Hanneke and S. Kpotufe. A no-free-lunch theorem for multitask learning. The Annals of Statistics, 50(6):3119 1943143,, 2022.
S. Hanneke and R. Nowak. Tutorial Active Learning: From Theory to Practice. In The 36th International Conference on Machine Learning, 2019. URL https:://outt: be/OTADiY71PAc? t-5865.
S. Hanneke and L. Yang. Negative results for active learning with convex losses. In Proceedings of the 13th International Conference on Artificial Intelligence and Statistics, 2010.
Hanneke and L. Yang. Minimax analysis of active learning. Journal of Machine Learning Research, 16(12):34873362, 2015.
S. Hanneke and L. Yang. Surrogate losses in passive and active learning. Electronic Journal of Statistics, 13(2)4464644788, 2019.
Hanneke, A. Karbasi, S. Moran, and G. Velegkas. Universal rates for active learning. In Advances in Neural Information Processing Systems 37, 2024a.
S. Hanneke, K. G. Larsen, and N. Zhivotovskiy. Revisiting agnostic PAC learning. In Proceedings of the thth IEEE Symposium on Foundations of Computer Science, 2024b.
HalePeled, D. Roth, and D. Zimak. Maximum margin coresets for active and noise tolerant learning. In Proceedings of the 35th International Joint Conference Artificial Intelligence, 2007.
14

---

D. Haussler. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Information and Computation, 100:78-150, 1992.
D. Haussler and P. M. Long. A generalization of Sauer's lemma. Journal of Combinatorial Theory, Series 71(2):219- 240. 1995.
T. Hegedus. Generalized teaching dimensions and the query complexity of learning. In Proceedings of the 8th Conference on Computational Learning Theory, 1995.
L. Hellerstein, K. Pillaipakkamnatt, V. Raghavan, and D. Wilkins. How many queries are needed to learn? Journal of the Association for Computing Machinery, 43(5):840-862, 1996.
M. Hopkins, D. Kane, Lovett, and G. Mahajan. Point location and active learning: Learning halfspaces almost optimally. In Proceedings of the 61 Annual IEEE Symposhum Foundations of Computer Science, 2020.
D. Hsu. Algorithms for Active Learning. PhD thesis, Department of Computer Science and Engineer- ing, School Engineering, University California, San Diego, 2010.
T.K. Huang, A. Agarwal, D. J. Hsu, J. Langford, and R. E. Schapire. Efficient and parsimonious agnostic active learning. Advances in Neural Information Processing Systems 28, 2015.
J. C. Jackson. An efficient membership query algorithm for learning DNF with respect to the uniform distribution. Journal of Computer and System Sciences, 55(3):114 1997.
M. Kääriäinen. On active learning in the non-realizable case. In NIPS Workshop on Foundations of Active Learning. 2005.
M. Kääriäinen. Active learning in the non-realizable case. In Proceedings of the 17th International Conference on Algorithmic Learning Theory, 2006.
M. J. Kearns, R. E. Schapire, and L. M. Sellie. Toward efficient agnostic learning. Machine Learning, 17:115-141, 1994.
V. Koltchinskii. Local Rademacher complexities and oracle inequalities in risk minimization. The Annals of Statistics, 34(6):2593 2006.
V. Koltchinskii. Rademacher complexities and bounding the excess risk in active learning. Journal of Machine Learning Research, 11(9):2457-2485 2010.
R. Kulkarni, S. K. Mitter, and J. N. Tsitsiklis. Active learning using arbitrary binary valued queries. Machine Learning, 11:23-35, 1993.
Lewi, Butera, and I.. Paninski. Sequential optimal design of neurophysiology experiments. Neural Computation, 21(3):619-66) 2009.
Mahalanabis. note on active learning for smooth problems. arXiv: /03.30/03.3095, 2011.
E. Mammen and A.B. Tsybakov. Smooth discrimination analysis. The Annals of Statistics, 27(6): 1829, 1999.
P. Massart and E. Nédélec. Risk bounds for statistical learning. The Annals of Statistics, 34(5): 2326-2366 2006.
T. Mitchell. Version Spaces: An Approach to Concept Learning. PhD thesis, Stanford University, 1979.
O. Montasser, Hanneke, and N. Srebro. VC classes are adversarially robustly learnable, but only improperly. In Proceedings of the n2nd Conference Learning Theory, 2019.
E. Mosqueira-Rey. E. Heméndezz-Pereira, D. Alonso-Ríos, J. Bobes-Bascaránn and Á. Fernández-Leal Human-in-the-lon machine learning: a state of the art. Artificial Intelligence Review, 56(4): 3005-3054, 2023,
15

---

M. Naghshvar and T. Javidi. Active sequential hypothesis testing. The Annals of Statistics, 41(6): 2703-2738, 2013. 2013.
B. K. Natarajan. On learning sets and functions, Machine Learning, 4:67-97, 1989.
R. D. Nowak. Generalized binary search. In Proceedings of the 46th Allerton Conference on Communication, Control, and Computing, 2008.
R. D. Nowak. The geometry of generalized binary search. IEEE Transactions on Information Theory, 57(12), 2011.
Olsson. A literature survey active machine learning in the context of natural language processing. 2009.
L. Paninski. Asymptotic theory of informmation-theortiicc experimentt design. Neural Computation, 17(7):180-1507, 2005.
C. Peirce. note the theory of the economy of research. In Report of the Superintendent of the United States Coast Survey Showing the Progress of the Work for the Fiscal Year Ending June 30, 1876, 1879.
R. J. Popplestone. An experiment in automatic induction. In Proceedings of the Fifth Annual Machine Intelligence Workshop, Edinburgh, pages 203-215, 1969.
N. Puchkin and N. Zhivotovskiy. Exponential savings in agnostic active learning through abstention. IEEE Transactions on Information Theory, 68(7):451-46655, 2022.
M. Raginsky and A. Rakhlin. Lower bounds for passive and active learning. In Advances in Neural Information Processing Systems 24, 2011.
Ren, Xiao, X. Chang, P.- Huang, Z. Li, B. B. Gupta, X. Chen, and X. Wang. A survey of deep active learning. ACM Computing Surveys (CSUR), 54(9):1-40, 2021.
B. Settles. Active Learning. Synthesis Lectures Artificial Intelligence and Machine Learning, Morgan & Claypool Publishers, 2012.
H. S. Seung, M. Opper, and H. Sompolinsky. Query by committee. In Proceedings of the 5th Anmual Workshop Computational Learning Theory, 1992.
H. Shayestehmanesh. Active learning under the Bemstein condition for general losses. Master's thesis, University of Victoria, 2020.
H. Simon. An almost optimal PAC algorithm. In Proceedings of the 28th Conference on Learning Theory, 2015.
H. A. Simon and G. Lea. Problem solving and rule induction: A unified view. In Knowledge and Cognition, pages 105-129. Lawrence Erlbaum Associates, 1974.
R. G. Smith, T. M. Mitchell, R. A. Chestek, and B. G. Buchanan. A model for learning systems. In Proceedings of the 5th International Joint Conference Artificial Intelligence, pages 338-343, 1977.
M. Talagrand. Sharper bounds for gaussian and empirical processes. The Annals of Probability, 22: 28-76, 1994.
S. Tong and D. Koller. Support vector machine active learning with applications to text classification. Journal of Machine Learning Research, 2(11):45-66, 2001.
C. Tosh and D. Hsu. Diameter-based interactive structure discovery. Proceedings of the 23rd International Conference Artificial Intelligence and Statistics, 2020.
A. B. Tsybakov. Optimal aggregation of classifiers in statistical learning. The Annals of Statistics, 32 (1):135-166, 2004.
G. Turán. Lower bounds for PAC learning with queries. In Proceedings of the 6t Annual Conference Computational Learning Theory, 1993.
16

---

L. G. Valiant. A theory of the learnable. Commumications of the ACM, 27(11):1134-144 November 1984.
A. W. van der Vaart and A. Wellner. Weak Convergence and Empirical Processes. Springer, 1996.
V. Vapnik and A. Chervonenkis. On the uniform convergence of relative frequencies events to their probabilities. Theory of Probability and its Applications, 16(2):264-28)) 1971.
V. Vapnik and A. Chervonenkis. Theory of Pattern Recognition. Nauka, Moscow, 1974.
M. Vidyasagar. Learning and Generalization with Applications Neural Networks. Ppringer-Verlaee 2nd edition, 2003.
A. Wald. Sequential Analysis. John Wiley and Sons, New York, 1947.
L. Wang. Smoothness, disagreement coefficient, and the label complexity of agnostic active learning. Journal of Machine Learning Research, (277)2269-22999 2011.
Y. Wang and A. Singh. Noise-adaptive margin- based active learning and lower bounds under Tsybakov noise condition. In Proceedings of the 30th AAAI Conference Artificial Intelligence, 2016.
Y. Wiener, S. Hanneke, and R. El- Yaniv. A compression technique for analyzing disagreement- active learning. Journal of Machine Learning Research, 16(4):713-745, 2015.
Yan, K. Chaudhuri, and T. Javidi. Active learning with logged data. In Proceedings of the 35th International Conference Machine Learning, 2018.
S. Yan, K. Chaudhuri, and T. Javidi. The label complexity of active learning from observational data. In Advances in Neural Information Processing Systems 32, 2019.
C. Zhang and K. Chaudhuri. Beyond disagreement-based agnostic active learning. In Advances in Neural Information Processing Systems 27, 2014.
T. Zhang. Statistical behavior and consistency of classification methods based on convex risk minimization. The Annals of Statistics, 32(1):56-4 85, 2004.
T. Zhang. Mathematical Analysis of Machine Learning Algorithms. Cambridge University Press, 2023.
Zhang and F. Oles. A probability analysis on the value of unlabeled data for classification problems. In International Conference on Machine Learning, 2000.
N. Zhivotovskiy and S. Hanneke. Localization of VC classes: Beyond local Rademacher complexities. Theoretical Computer Science, 742:27-49, 2018.
X. Zhu, J. Lafferty, and Z. Ghahramani. Combining active learning and semi-supervised learning using Gaussian fields and harmonic functions. ICML workshop on the Continuun from Labeled to Unlabeled Data in Machine Learning and Data Mining, 2003.
Y. Zhu and R. Nowak. Efficient active learning with abstention. In Advances in Neural Information Processing Systems 35, 2022.
17

---

A Survey of the Theory of Active Learning and Other Related Work
There is at this time quite an extensive literature on the theory of active learning. We refer the interested reader to the surveys of Hanneke (2014), Dasgupta (2011), and the 2019 ICML tutorial of Hanneke and Nowak (2019) for detailed discussions of classic works in this literature. In this section, we present brief survey of the subject, with particular emphasis on the parts most-closely related to the present work.
A.1 A Brief Historical Overview
The literature active learning has long history, dating back least the classical works on experiment design in statistics (Peirce, 1879; Fisher, 1935). wherein the analogous setting to active learning is referred as sequential design (e.g.. Wald, 1947: DeGroot, 1962; Fedorov, 1972: Atkinson and Donev, 1992; Efromovich, 2007; Zhang and Oles, 2000; Paninski, 2005; Lewi, Butera, and Paninski, 2009; Bull, 2013; Naghshvar and Javidi, 2013; Chaudhuri, Kakade, Netrapalli, and Sanghavi, 2015). Active learning has also been an important subject within the machine learning literature from the very beginning (c.g.. Popplestone, 1969; Simon and Lea, 1974; Buchanan, 1976; Smith, Mitchell, Chestek, and Buchanan, 1977; Mitchell, 1979). Below we briefly mention some of the background of the subject in the learning theory literature, before giving detailed background of the literature on agnostic active learning.
the learning theory literature, the idea of active learning also appeared as natural variant of the problem of Exact learning with queries. Specifically, in this setting, supposing there is an unknown target concept ht* E C, the objective of the learner is to exactly identify ht. To achieve this goal, the learner has access to an oracle (who knows h*), to which it may pose queries of a given type. The most relevant such queries (to the present work) are membership queries: namely, it may construct any X' and query for the value h" (x)) (in later works in machine learning, this is sometimes known as query synthesis). Early discussion of this framework and corresponding algorithmic principles appear in the seminal work of Mitchell (1979). General analyses of the number of queries necessary and sufficient to identify h* (i.e., the query complexity of Exact learning) were developed in the works of Angluin (1987); Hegedüs (1995); Hellerstein, Pillaipakkamnatt, Raghavan, and Wilkins (1996); Nowak (2008, 201 1); Hopkins, Kane, Lovett, and Mahajan (2020), and a related average-case analysis was developed by Dasgupta (2004).
Membership Queries:
Closer to the setting considered in the present work, the idea of learning with membership queries has also been extensively studied in the context of PAC learning in the realizable case. In that setting, the learner observes i.i.d. samples (X,, Y2) with unknown distribution P. under the assumption that there exists unknown target concept h" E C with (h" = 0. The learner is additionally permitted to make membership queries for this concept ht, with the goal of producing a predictor h having ph)(h) S & with high probability 1 - 8. While most of the literature on PAC learning with membership queries has focused on the benefits of such queries for the computational complexity of learning (e.g., Valiant, 1984; Baum, 1991; Jackson, 1997), the literature also contains several works the number of samples and queries for learning in this setting (e.g., Eisenberg and Rivest, 1990; Eisenberg, 1992; Scung, Opper, and Sompolinsky, 1992; Turán, 1993; Kulkarni, Mitter, and Tsitsiklis, 1993; Diakonikolas, Kane, and Ma, 2024).
Modern Active Learning with Label Queries: While the early literature on PAC learning with membership queries included several strong positive results (exhibiting advantages in both query complexity and computational complexity compared to learning from i.i.d. samples alone), when researchers implemented these algorithms and tried to use them for practical machine learning with a human labeler as the oracle, they found that the instances E X' queried by the learner often turned out be rather nonsensical, unnatural, or borderline cases between two labels (e.g.. Baum and Lang, 1992). As such, human labelers were unable to provide useful answers to the queries, leading to poor performance of the learning algorithm. To address this issue, researchers turned to studying algorithms whose queries are restricted to only natural instances x E X', which in most works (with a few notable exceptions, e.g., Awasthi, Feldman, and Kanade, 2013) essentially means x in the support of the marginal distribution Px: i.e., the types of examples that might occur naturally in the population. To actualize this restriction, researchers proposed a simple variant of active learning (which has become the standard framework in the literature, and is now essentially synonymous
18

---

with the term active learning). in which there are i..d. samples (X1,Y))... (Xm, Ym) from an unknown distribution P. but the learner initially only observes the unlabeled examples X;, and can query to observe individual labels Y; (in sequential fashion, so that it observes the label Y; of its previous query before selecting the next query X²)) (Cohn, Atlas, and Ladner, 1994; Freund, Seung, Shamir, and Tishby, 1997; Tong and Koller, 2001). Such queries can typically be answered by human experts, being of the same type as used for data annotation in standard supervised machine learning. In this scenario, the unlabeled examples X; are typically assumed to be available in abundance, while obtaining the labels Y, is considered comparably more expensive (relying on the effort of a human expert), that the primary objective is to minimize the number of label queries needed to achieve given accuracy of learned predictor h. This is the setting studied in the present work.
The theoretical literature on this subject has origins in early works discussing algorithmic principles based on version spaces (Mitchell, 1979; Cohn, Atlas, and Ladner, 1994). Many of the early works providing actual bounds on the query complexity focused on showing improvements over passive learning for special scenarios, such as linear classifiers under distribution assumptions (e.g.. Freund, Seung, Shamir, and Tishby, 1997; Dasgupta, Kalai, and Monteleoni, 2005; Har-Peled, Roth, and Zimak, 2007; Balcan, Beygelzimer, and Langford, 2006; Balcan, Broder, and Zhang, 2007: Balcan and Long, 2013; Gonen, Sabato, and Shalev-Shwards 2013; Wang and Singh, 2016; Cavallanti, Cesa-Bianchi, and Gentile, 2011; Dekel, Gentile, and Sridharan, 2012). This was followed by boom of general-case analyses. providing general theories analyzing the query complexity for any concept class (e.g.. Dasgupta, 2005; Hanneke, 2007a,b, 2009b,a, 2011 1, 2012, 2014; Dasgupta, Hsu, and Monteleoni, 2007: Balcan, Hanneke, and Vaughan, 2010; Beygelzimer, Dasgupta, and Langford, 2009; Koltchinskii, 2010; Zhang and Chaudhuri, 2014; Yaniv and Wiener, 2012; Wiener, Hanneke, and EI- Yaniv, 2015; Hanneke and Yang, 2015; Hanneke, Karbasi, Moran, and Velegkas, 2024a), some of which are discussed in more detail below.
Agnostic PAC Learning: The PAC learning framework has also been extended to allow non- realizable distributions P. that is, removing the restriction that infage ph) = O. This framework was abstractly formulated in the classic work of Vapnik and Chervonenkis (1974), with interest in the computer science literature initiated by the works of Haussler (1992); Kearns, Schapire, and Sellie (1994). Since such non-realizable distributions P might not allow for predictors h with pry(h) S E, the objective in this framework changes to merely achieving a relatively low error rate compared to the best error rate achievable by concepts in the class C. More precisely, we aim to produce a predictor h which, with probability at least 1 1-6 8, satisfies p < inf er ph) + E. The goal to achieve this objective, for every distribution P. without any restrictions. This framework is termed agnostic PAC learning, to emphasize that we do not assume any special knowledge of P when designing such a learning algorithm (Kearns, Schapire, and Sellie, 1994).
While an agnostic learning algorithm should achieve this objective for every distribution P. this need not restrict the analysis of such learners to consider only the worst case over all P. In particular, in the present work, we are primarily interested in analyzing the number of queries necessary and sufficient for agnostic active learning, as function of the best-in-class error rate inf (h), known as first query complexity bound. Precisely, as introduced in Section 2, for every E, 6, 8 E (0. 1). we denote by QC2 (e, 8; 3, C) the minimax optimal first-order query complexity: that is, the minimal Q E IN for which there exists an active learning algorithm A. such that (for a sufficiently large number m of unlabeled examples), for every distribution P' with inf (h) S B, with probability at least 1 1- 8, An makes at most Q queries and returns a predictor h satisfying ph) < inf p + e. While, in principle, this definition of QC2, (s, 6; 3, C) admits learners which explicitly depend on knowledge of 3, we will find that the optimal query complexity is achievable (up to constant factors and lower-order terms) simultaneously for all /3 by an active learner which does not require knowledge of B. Such a learner is said to be adaptive to 33. In particular, such a learner is therefore an agnostic PAC learner, and the B restriction only enters in its analysis.
The Passive Learning Baseline: Since the predictor h produced by an active learning algorithm is based on its queried subset of a given set of i.i.d. examples (X;, Yi). the natural quantity for comparison is the number of i.i.d. labeled examples necessary to obtain the same accuracy: i.e.,
the sample complexity of standard supervised learning, which in this literature is termed passive
19

---

learning. 5 Recall from Section 2 that we denote by Mp(E, 8; 3, C) the minimax optimal sample complexity of passive learning: i.e. the minimal n such that there exists a passive learning algorithm Ap that, for every P with infsecerp(h)) S 3, for 5 ~ pd and hn = AS(S), guarantees with probability at least 1 - å that er (h,( I infuec ( + E. Since we can always design an active learner that simply queries the first n examples and runs a passive learner Ay. we clearly always have QC,(e, 6; B, C) S Mpp 6; (3, C). Thus, the main question of interest is whether QC,(s, ó; B3, C) is strictly smaller than Mp(e, o; B, C). and if so, by how much. Lower bounds of Vapnik and Chervonenkis (1974); Devroye and Lugosi (1995) establish that
Mp(e,6;3,0) - ( 3 (d+ log EZ
(
1 d log
1)))
1 [
recalling that d denotes the VC dimension of C (Vapnik and Chervonenkis, 1971; see Deñi nition 4 of Appendix B). The classic analysis of Vapnik and Chervonenkis (1974) further es- tablished this lower bound can nearly be achieved by the simple method of empirical risk minimization, i.c., hn argmingec (h), providing
upper bound MM, B,C)
o( (d + log())) + 1 (e) + log()))) This has since been refined in various ways, such as via localized chaining arguments (e.g., Giné and Koltchinskii, 2006). Most re- cently, Hanneke, Larsen, and Zhivotovskiy (2024b) proved upper bound MM[e, 6; C)
o [ log()))) + Ō (d + (l+o((()))) ()), matching the lower bound (4) up log factors in the lower-order term (the problem of removing these remaining log factors remains open at this time). The algorithm achieving this is improper, meaning its returned h, is not necessarily an element of C, and Hanneke, Larsen, and Zhivotovskiy (2024b) in fact show that for some concept classes C improperness is necessary to match the lower bound (4) in the lead term, as all proper learners incur an extra log( }t) factor. In the special case of 3 = (the realizable case), the lower bound (4) was shown to be achievable by Hanneke (2016a) (also necessarily via an improper learner), so that Mp(e, o; 0, C) = O (d + logg())) The lower bound (4) will therefore serve as suitable baseline for gauging whether the query complexity (C, 5; B, C) of active learning is smaller than the sample complexity Mp 8: B, C) of passive learning.
The Need for destribution-dependere Analysis in Realizable Active Learning: Much of the early work on active learning focused on the realizable case, i.e., the special case 3 0. In this special case, it was quickly observed by Dasgupta (2004, 2005) that there are some concept classes (e.g., thresholds so) on IR) where active learning offers strong improvements over passive learning, and other concept classes (e.g., intervals 1|a,0] on E) where the (distribution-fiee minimax query complexity QC,(s, 5; 0, C) offers no significant improvements over passive learning. The essential advantage in the former case arises from kind of "binary search" behavior, where the "uncertainty" is being sequentially reduced by a careful choice of queries. In contrast, the essential challenge in the latter case is the problem of "searching in the dark" for a small- -umporttt region: e.g., the optimal concept is 1 for single unknown T; among some II,....,i 11/c. and Px = Uniform([z) (z1,...,<1// }). It turns out this hard scenario is embedded in many concept classes of interest, a fact which was formalized and quantified by Hanneke and Yang (2015) in the star number complexity measure (Definition 2) discussed below. Such concept classes C naturally exhibit a lower bound QC, (s, 0; C) 2()). Even worse, consider scenarios where the optimal concept can be 1 for any d points z; among ......, #d/(2c), and Px Uniform ((x), (f. (Fa(()). )). Hanneke and Yang (2015) show this scenario has QC, 8; 0, C) = ((f). so that QC,(e, 8; 0, C) has the same joint dependence on (d, E) as passive learning M,,e,,;000 C)- = O + (d+log( (t)). only offering
///e)
'Since the active learner also has access to the remaining (unqueried) i.i.d. unlabeled examples X., it is also natural to compare to the related framework of semi-supervised leamnnn, in which learner has access to some number n of i.i.d. labeled examples with distribution P and additionally some larger number m of i..dd unlabeled examples with distribution Px (Chapelle, Scholkopf, and Zien, 2006). While, under some favorable conditions, the labeled sample complexity of semi-supervised learning can be smaller than that of durictl-ssupervisee passive learning (see Balcan and Blum, 2010). the lower bounds on the (distribution-fiet sample complexity of passive learning discussed in this work remain valid for the labeled sample complexity of semi-sune suni-supervised learning (regardless of how many unlabeled examples are available). so that for the purpose of comparison in the present work, the distinction between supervised and semi- superviee passive learning as a baseline is not important, and we will simply compare to passive supervised learning for simplicity.
20

---

an improvement in the dependence on å (where å thus only affects the unlabeled sample complexity). Moreover, as noted by Hanneke (2014), similar scenarios are embedded (with ((C(C))) in most concept classes C of interest in learning theory (c.g., linear classifiers in Rtd, and axis-aligned rectangles in I22dd, so that such classes also exhibit no significant improvements over passive learning in their (distribution-free minimax) realizable-case query complexity QC, 6; 0, C).
Motivated by the fact that such hard scenarios are embedded in many concept classes of interest, Dasgupta (2005) suggested that, for such concept classes, the only viable way to understand the potential advantages of active learning is to focus on distribution dependen analysis, toward identi- fying special scenarios where active learning algorithms offer improvements over passive learning, by formulating appropriate assumptions on the distribution P. This narrative quickly caught on in the literature, with variety of distribution-dependenn analyses and general P-dependent complexity measures being proposed to analyze certain active learning strategies under various restrictions on the realizable distribution P (Dasgupla, 2005; Hanneke, 2007a,b, 2014; Balcan, Broder, and Zhang, 2007; Balcan and Long, 2013; Zhang and Chaudhuri, 2014; El- Yaniv and Wiener, 2012; Wiener, Hanneke, and EI- Eani, 2015). We discuss several of these in detail below.
Active Learning in the Non-realizable Case: Given the above narrative, when approaching the analysis of active learning in the non-realizable case (3 > 0), it might at first seem perfectly reasonable to expect that for many concept classes C the query complexity (e, 8; B, C) might not be much smaller than the sample complexity of passive learning Mp(E. 6; C). As such, the literature on agnostic active learning has largely focused on extending the cetrriuttiondependee analyses from the realizable case to the agnostic setting (e.g., Balcan, Beygelzimer, and Langford, 2006, 2009; Hanneke, 2007b,a, 2009b, 2011, 2014; Balcan and Hanneke, 2012: Zhang and Chaudhuri, 2014; Wiener, Hanneke, and EI- Yaniv, 2015). These upper bounds conformed to the accepted narrative, in that they offer improvements under some distributions, but for most classes C, in the worst case over distributions P (with infrec er (h) S 3) they essentially revert to the passive sample complexity Mp(s, 6; C)
However, since this narrative was born from analysis of the realizable case, there was no actual reason to believe it should remain valid in the non-realizable case. In particular, there remained an intriguing possibility that there could perhaps be other advantages of active learning specific to the non-reatizable case: that is, beyond the "binary search" type advantages known from the realizable case (as captured by the complexity measures proposed for realizable-case analysis). Some hints that such additional advantages may exist appear in the works of Efromovich (2007) and Hanneke and Yang (2015) studying certain special scenarios (noise models more-restrictive than the agnostic setting), which found that active learning can also be useful for adaptively identifying noisy regions (i.e., regions of X's where P( is close to 2 ) and allocating queries appropriately to compensate for this noisiness without wasting excessive queries in less-noisy regions (as passive learning would), This additional advantage, specific to the non-realizable case, offered quantitative advantages over passive learning under the specific conditions studied in those works (e.g., Hanneke and Yang. 2015 showed improvements in query complexity under certain noise models, namely Tsybakov noise and Benign noise, for all classes C, including those with the "searching in the dark" scenario embedded in them). However, these works left open the question of whether such advantages can be observed also in the more-challenging agnostic setting. The extension to the agnostic case is not at all clear, since in this setting (unlike the special noise models in the works above) the source of non-realizability not only the noisiness of the P(Y XX) label distribution, but also model misspecification: i.e., is possible to have 3 > 0 even when P( E {0. 1). if the Bayes classifier is not in C, in which
'The hard scenario embedded in these classes is slightly more structured. Namely, for any d E N and infinite X. partition X' into disjoint infinite subsets X,,..., Xá. and define C. = (h Vi < d. E.E h(x) < 1). which has VC(Ca) d. For such classes Ca, Hanneke and Yang (2015) show that QC2 (E, 8; 0, C.) R( (as an aside, it straightforward exereise to show matching upper bound for this class). For homogeneous línear classifiers in Rd we can construct the X; sets as circles in disjoint subspaccs: i.c., X is all (zi...., Zsa) E R 1 and Za(s-1)+a = 1 (to allow for non-homogeneous
s.l. all coordinates zj = 0 except z2 13(1-1)++1 1 + 23/3-1)42 linear classifiers on these circles, each controlled using 3 distinct weights in the 3d-dimensional linear classifier); the classifiers with boundary tangent these circles witness the d singleton problems in C.. For axis-aligned rectangles in 2d we can construct the X; sets as diagonal lines disjoint 2-dimensional subspaces: i.e., X, is all (21,... 22a) E 2d with all 2, = 0 except 22(1-1)+1 E [0, 1] and 22(1-1)+2 = 1 - 12(1-1)+1; as each X. can be classified by 2- d-dmensionnl rectangle based on 2 distinct coordinates. the classifiers with a single corner intersecting each of these diagonal lines then witness the d singleton problems in Ca.
21

---

case the idea of adapting to "noisiness" of labels is no longer useful framing of the problem. (The present work finds the appropriate re- re-framing of this capability, replacing the notion of "noisiness" by the variance of the excess-error estimation problem, and identifies algorithmic principles for isolating such hagi-variance regions, constituting the AVID principle).
Quantifying the Query Complexity (Realizable Case): As discussed above, motivated by negative results for distribution-free analysis in the realizable case, numerous works have studied the query complexity of active learning under restrictions on the distribution P. These cestriuttin-dependenr analyses are often expressed in terms of abstract I P-dependent complexity measures intended to capture favorable conditions for active learning, compared to passive learning. Quantitatively, in the realizable case (3 = 0), such P-dependent query complexity bounds are typically expressed in the form (E) d polylog( (3)) for some P-dependent complexity measure (e) Examples of such complexity measures include the splitting index (Dasgupta, 2005), disagreement coefficient (Hanneke, 2007b, 2009b, 2011), 1), empirical extended teaching dimension (Hamneke, 2007a), and a subregion variant of the disagreement coefficient (Zhang and Chaudhuri, 2014), among others (e.g.. El-Yaniv and Wiener, 2012: 2: Hanneke, 2012, 2014; Wiener, Hanneke, and EI- Vaniv, 2015; Hanneke and Yang, 2015). Some of these were accompanied by related minimax lower bounds holding for any fixed Px marginal distribution (Dasgupta, 2005; Hanneke, 2007a; Balcan and Hanneke, 2012). We discuss several of these -edependentt analyses and cp(E) complexity measures in detail in Appendix A.2.
The works of Hanneke and Yang (2015); Hanneke (2016b, 2024) later showed that all of these proposed complexity measures cp(e) have worst-case values (i.e., supp cp(e) over realizable P) precisely equal a complexity measure therein termed the star number of C (Definition 2). a quantity which abstractly formalizes and quantifies the extent to which the aforementioned "searching in the dark" scenario embedded in a given concept class C. Thus, the star number unifies all of these complexity measures in the case of distribution analysis. Moreover, Hanneke and Yang (2015) also show the star number sharply characterizes the optimal distribution-free query complexity the realizable case: namely.
QC (,,00,,) s {C
d log !
(5)
(see Hanneke and Yang, 2015, for mote-detailed bounds). Hanneke and Yang (2015) also show the upper and lower bounds in (5) represent nearly-shary dependence on s): that is, there exist concept classes Cd,s and Ca., of any given VC dimension d and star number s 2 d for which QC,(e, 6; 0, Ca.s) O(s ( + d)) and QC, 5; O, Ca.o) ( A -). Thus, the bounds in (5) are essentially miimprovbble (up to log factor) without introducing additional complexity measures for the class C. In particular, this also means any upper bound on QC, (e, 6; 0, C) depending on C only via and can be no smaller than 2(s 2).
The bounds in (5) imply that (E,00, admits an improved dependence on e compared to Mp(s, C) = O (o+(())))) if and only if s < cc. While there exist some interesting concept classes C with finite star number (e.g., threshold classifiers on IR decision stumps on RP), it turns out most concept classes of interest in learning theory have infinite (or very large) star number (e.g.. 5 oo for linear classifiers on R', p 2 2). Thus, the general bounds in (5) quantitatively reflect the fact (already observed in several cases by Dasgupta, 2004, 2005) that we should typically nor expect any significant benefits of active learning in the realizable case to be reflected in the (distribution-fre free minimax) query complexity QC, 5; O, C). Moreover, as mentioned above, the concept classes Ca., with s = oo witnessing near-sharpness of the upper bound in (5) are also embedded in many concept classes of interest learning theory (see footnote 6), further strengthening the lower bound to ( for such classes, thus matching the sample complexity Mp 6; 0, C) of passive learning in all dependencies (except 8).
Quantifying the Query Complexity (Agnostic Case): Turning to the agnostic case (B 2 0), Kääriäänen (2006) established a general lower bound QC, strengthened by Beygelzimer, Dasgupta, and Langford (2009) to
8; B, C) = 22 20 ( log())) later
QC,(E,8)3,C)) = 0 B2 -²
d + log
(6)
22

---

Comparing this to the sample complexity of passive learning (discussed above), namely Mp(e, 3, C) e + (og(())))) + 6 (d+ we see that in the regime 3 > VE, the best improvement we can hope for from active learning would be to replace the factor 33 with 3 Le., squaring the dependence on the best-in-class error rate hnf erp (h). In the regime S VE. the realizable-case lower bound from (5) becomes relevant (the realizable case being a special case, since clearly infnec erp 0 satisfies the condition irfke)erph)) I (9), which may be thought of as a lower-order additive term.
The work of Balcan, Beygelzimer, and Langford (2006) initiated the study of upper bounds on the query complexity in the agnostic case, showing that the lower bound (6) can be matched in the special cases of threshold classifiers (concepts [(,,)) on X' = R), and (in the regime 3 S e/vā) matched up factor d for homogeneous linear classifiers under Px uniform in origin-centered ball, extending these well-known examples from the realizable case. This analysis was generalized to all concept classes by Hanneke (2007b), expressing query complexity bound of the form ò (cp(( + =)d [ +1)). where the factor cp(3 + E) is based on P-dependent complexity measure 0p(3 + 8) therein termed the disagreement coefficient (Definition 25). In particular, the bound of Hanneke (2007b) matches the lower bound of Kääriäinen (2006); Beygelzimer, Dasgupta, and Langford (2009) up logs only when (r + E) Ó(1). The latter holds for threshold classifiers, and for other classes under restrictions on P. but in many other cases p + E) can be as large as 3+E due to the "searching the dark" problem discussed above; in such cases, the query complexity upper bound of Hanneke (2007b) is no smaller than the sample complexity of passive learning MMle, ó; B, C). Numerous later works (some discussed in detail below) discovered refinements and alternative P-dependent complexity measures used to express upper bounds on the query complexity (Hanneke, 2007a; Dasgupta, Hsu, and Monteleoni, 2007; Hanneke, 2009b, 2011, 1, 2014; Zhang and Chaudhuri, 2014; Wiener, Hanneke, and EI- Yaniv, 2015). However, like the bound of Hanneke (2007b), all of these results establish query complexity upper bounds of the form ò [cr(B + +)d
62 + +)) for some P-dependent complexity measure cp(B + E), all of which have the property that, in the "searching in the dark" type scenarios diseussed above, the value 1 cp(3 +) 2 3+2 so that in such scenarios these upper bounds are all no smaller than the sample complexity of passive learning Mp(e, 5; C)
188
As in the realizable case, these various analysis were later all unified under worst-case analysis over P by the star number in the work of Hanneke and Yang (2015). Indeed, these complexity measures (3 + E) are in fact the same family of complexity measures alluded to above for the realizable case. As such, by the aforementioned result of Hanneke and Yang (2015), they all satisfy cp + =) = s B+2' Thus, the upper bounds established by these works, all being of the form
O(cp(B + +e)d _ +1). unify to single upper bound of the form Ö((s ^ 3t. d +1)1 in the worst case over distributions P (satisfying inf ( S (). In particular, this also means they all fail to imply any improvements over the sample complexity of passive learning Mp(E, 8; B, C) in the worst case over such distributions P, for any concept class C with s xc." This is significant, since (as discussed above) most commonly-studies concept classes have s = co, including, for instance, linear classifiers in 12P, p 2 2. On the other hand, the lower bound (6), of the form 2 82 جي + (d+log( ). has no such factor s A g-z- The natural question is therefore which of these can be strengthened:: the upper bound or lower bound.
The above gap has a qualitative significance. If the lower bound could be strengthened to match the upper bound, would mean that (as in the realizable case) there are classes where active learning offers no advantage in its minimax query complexity compared to passive learning. On the other hand, if the upper bound can be strengthened to match the lower bound, it would mean that (unlike the realizable case) the query complexity of active learning is always smaller than the sample complexity of passive learning in the agnostic setting: i.e., for every concept class. The problem of resolving this gap has remained open until now. In the present work, we completely resolve this question,
7 "One can also show that this is not merely a result of loose analysis. The algorithms (prior the present work) can he made to hehave similarly to passive learners (meaning they query almost indiscriminately) in some scenarios constructed large star sets, resulting in number of queries zz
23

---

strengthening the upper bound to match the lower bound (6), thereby establishing that active learning always better than passive learning the agnostic case, providing an improvement by squaring the dependence on the best-in-class error rate in the leading term: i.e., replacing 3 with (82. Establishing this upper bound requires a new principle for active learning, specific to the agnostic setting, which we develop in this work (termed AVID, for Adaptive Variance Isolation by Disagreements).
Before proceeding with the presentation of our results, we first provide, in the next subsection, detailed survey of several of the prior works mentioned in the above brief historical summary.
A.2 Detailed Description of Relevant Techniques in the Prior Literature
In this subsection, provide further details of relevant works in the literature. Duc to the vastness and diversity of the literature on the theory of active learning, we will not provide an exhaustive survey here, instead focusing the techniques and results most-relevant to the present work.
A.2.1 Disagreement-basee Active Learning
By-far the most well-studied technique in the literature on the theory of active learning is disagreement- based active learning. A disagreementtbaseee active learner is given input the sequence X1, X2,..., Xm. of unlabeled examples. It maintains (either explicitly or implicitly) a set V S C of surviving concepts (known
version space), with a guarantee that the best-in-class concept h* is always retained in V. To choose its query points, it finds the next unlabeled example X; in the sequence for which 3f, g V with ((x)) + ((;), and queries for the label Y;: or more succinctly, queries the next X, E DIS(V), where
DIS(V) {ar X 3f.g E V,)(2) # 9(x));
denotes the region of disagreement of V. It then updates the set V of surviving concepts based on this new information (or, in some variants, it performs this update only periodically, rather than after every query). This is abstractly summarized in the following outline (where Step 4 can be instantiated in various ways, as discussed below).
Algorithm Outline: Disagreement-basee Active Learning Input: Unlabeled data X1,.... Xm
Output: Classifier h
0. Initialize V C
1. For i = 1,2...... m
2. If E DIS(V)
3. Query for label Y;
4. Update V
5. Return any h V
The idea is that, we seek to return a concept E V with small ery(h) - erp(h*), ). then for any X, DIS(V), since all surviving concepts agree on the classification of X,, the label Y; would provide no information that would help with this goal, so we do not bother querying for this label: that is, such a Y; cannot help to estimate the relative performances erp(f) eg) of concepts f.g E V. since regardless of Y,, we have [{)( + Yi] (X,) YYI = 0. In contrast, the next X, DIS(V) in the sequence is random sample from Px (- DIS(()), so that for any f.g E V. n[((X;) & - -Xx()), * Y.] is an unbiased estimate of the difference of error rates under the conditional distribution P(-IDIS(V)
{0. 13), which (again since f.g agree outside DIS(V)) is proportional to ( (g). By reasoning about uniform concentration of these estimates, we can define an update rule for V in Step 4 that never removes the best-in-class concept h" while pruning sub-optimal concepts from V (where the resolution of this pruning improves as grows).
In the realizable case, since we always have h (Xx) Y, the updates to V in Step 4 can simply remove all concepts incorrect on a queried example (X,, Y)): that is, V + (h E V h(X,) Y) (called the version space), which always retains ht V. The algorithmic principle of disagreement- based queries, and corresponding reasoning about correctness and potential advantages, was already
'The theory easily generalizes to cases where the infimum infrec (h) is not attained, in which case detine ht E C to have (rr(h") sufficiently close to the infimum, e.g., in (10) below.
24

---

identified in the early work of Mitchell (1979) (for the membership queries model). 9 The precise form expressed above (sequentially checking unlabeled examples for disagreements) was first explicitly studied by Cohn, Atlas, and Ladner (1994), and in their honor, this realizable-case technique is referred to as CAL the literature. As for its theoretical analysis, the original works of Mitchell (1979); Cohn, Atlas, and Ladner (1 (1994) include the observation that h is retained in V. and Cohn, Atlas, and Ladner (1994) additionally include some discussion of generalization. However, the formal analysis of the query complexity of this technique in the PAC framework only began with the later work of Balcan, Beygelzimer, and Langford (2006) (bounding the query complexity for some specific concept classes), and the general analysis of the technique (applicable to any concept class) began with the works of Hanneke (2007b, 2009b, 201 I); Dasgupta, Hsu, and Monteleoni (2007).
The idea of dissgreemeent-aseee active learning was first extended to the agnostic setting (3 2 0) by Balcan, Beygelzimer, and Langford (2006), with an instantiation of the above outline they called the A2 algorithm (for Agnostic Active). The main idea in A² is to instantiate the update to V in Step 4 using uniform concentration inequalities. In their original version, they specifically define (B) and LB(h) as high-pro hyhh-roobbiility uniform upper and lower bounds on ( (0.1]) (h) based on the queries from DVS(V) since the last update to V (where they only update V periodically in their algorithm, so that the queried examples since the last update are i.i.d. samples from P.-DDI(VV) x {0, 1 }).). They then define the update as V <- (h E V LB(h) S mingev UB(h'). The idea is that they wish to remove concept h from V if there is another concept h E V whose upper bound UB(N') on its error rate is smaller than the lower bound (B( on the error rate of h. In particular, since h, h'' agree on all x & DIS(V), we have
err(h) - (rr( x (TP((DIS(V)
- (T 2 LB(h) - UB(N),
and hence a concept can be removed from V only if c ch' > 0 for some N E V. meaning that h is verifiably suboptimal, guaranteeing that the algorithm always retains ht E V. Conversely, by querying the examples in DIS(V), we are improving the concentration inequalities UB(h), LB(h). so that suboptimal concepts are removed from V. which has two benefits: (1) we are converging to a set of relatively low-error concepts (important for the final error guarantee), and (2) by reducing V we are potentially also reducing (VS focusing the algorithm's 'ss queries to more-informative samples and decreasing the query complexity.
The original analysis of Balcan, Beygelzimer, and Langford (2006) included the above correctness guarantee (i.e., the algorithm maintains h- E V), along with a general guarantee that the 2² algorithm returns an with (h) S er"( + e, with a number of queries never significantly worse than that of passive learning. Also, as a sort of proof of concept illustrating the potential benefits of A in a simple example, they also quantified the query complexity ad advantages in the special case of threshold
classifiers (concepts 10) on X' = IR,, showing a bound Ó 8" + +1) for that class (matching the T
lower bound of Kääriäinen, 2006). They also studied the special case of learning homogeneous linear classifiers under a uniform distribution in an origin-centered ball in IR, focusing on the regime B S 8/ Vd, for which they showed the query complexity is Ódd log(?) log()))-
The first general analyses (i.e., applicable to any concept class) of the query complexity of active learning in the agnostic setting were given in the works of Hanneke (2007b,a). In particular, Hanneke (2007b) analyzed the A² disagreementt-based active learning algorithm, providing a general query complexity bound expressed in terms of a new complexity measure therein termed the disagreement coefficient. Specifically, for r > 0, denoting by Br, (h", .r) {h E C (x h(x) * h" (x)) S r) the h² centered ball (under L2 (Px)), the disagreement coefficient is defined as
(DIS( (I*,,))) r))) V1.
0r(3 +)) = sup
r>8+s
The intuitive interpretation of the relevance of this quantity is that, as the algorithm progresses, the set V of surviving concepts will become closer and closer to he (up until a distance O(5 + =)), so that the probability of querying decreases Px (DIS(VV) < (DIS(BRR (h" .r)) for an appropriate decreasing as the number of queries grows.
Hanneke (2007b) proves that, for any C and P, for B = erp(h*), the A algorithm succeeds after a number of queries ò ((0p(3 +d f
8²
+1) This matches the lower bound (6) of Kääriäinen
Mitchell (1979) also discusses some reasonable extensions of version spaces to the non-realizable case.
25

---

(2006); Beygelzimer, Dasgupta, and Langford (2009) up to logs whenever 0p +) =) 011. In particular, Hamneke (2007b) bounds 0p(3 + E) for number of scenarios P), including showing that this general query complexity upper bound recovers the examples of Balcan, Beygelzimer, and Langford (2006): ( + E) < 2 for threshold classifiers, and (r +) = O(vd) for homogeneous linear classifiers under a uniform distribution on an origin-centered sphere (thus also removing the constraints on B, e from the result of Balcan, Beygelzimer, and Langford, 2006). However, Hanneke _ (2007b) also found 0p(3 + +) can sometimes be as large as 3+e particularly for the "searching in the dark" scenarios discussed above, in which case the query complexity bound is no smaller than the sample complexity of passive learning.
Subsequently, Dasgupta, Hsu, and Monteleoni (2007) refined the dependence on ( + +) in this bound (analyzing different disagreement- based algorithm), replacing ( + +)² with (p + E). Their technique also identifies a principle enabling more-practical implementation of disagreement- based active learning, expressing the algorithm reduction to empirical risk minimization (ERM). In general (even with A²), we can always maintain the set V implicitly (i.e., without storing this large object V explicitly). by simply maintaining the set of constraints that define it, which then enable us to perform the various operations (c.g., checking whether X; E DIS(V). or computing minyev UB(h) via constraint satisfaction constrained optimization problems. The algorithm of Dasgupta, Hsu, and Montelconi (2007) takes this a step further, expressing such operations as (effectively) unconstrained optimization problems, in other words, calls to an ERM subroutine (i.e., an algorithm which returns a concept in C minimizing the number of mistakes on any given labeled data set). Specifically, they store two labeled data sets Q;, Li, where Q: are the queried examples so far (up to round i) and L, are the unqueried examples so far (with inferred labels). On round i, they consider the concepts h² h2 C of minimal érq, , (h) subject to ér,, , (h) 0 and (x;) 1, (x,,,) 0, if they exist (noting that such concepts can each be obtained by single call to an ERM oracle with appropriately high weight, or repetition, of the Li-1 and (X,, y) examples). If erq, (h*) and érq.,, (h") are of similar sizes, they query for Y; and add it Q--1 to get Qi (letting L, = Li-1), and otherwise they take an inferred label D; argmin, étq, (h²) and add (X;, 0:) to L to get L, (letting Q₂ = Q1-1). Note that this is equivalent to maintaining a set V of all concepts h E C having e,,,, (h) 0 and érq,_, (h) of similar size to miny ctq... (h') among all N' E C with ér,,,, (h') = 0. and querying X, iff X; E DIS(V). Thus, this algorithm can also be viewed as active learner (and this connection is made explicit in the analysis of Dasgupta,
a disagreement-base Hsu, and Monteleoni, 2007). (Notably, subsequent works of Beygelzimer, Hsu, Langford, and Zhang, 2010; Hsu, 2010 even further simplified this technique by dropping the 1 constraints, obtaining similar query complexity bounds).
The specific quantification of the "similar sizes" criterion for the difference of empirical error rates comes from uniform Bernstein-style concentration inequalities (related to the uniform Bernstein inequality stated in Lemma 7 of Appendix D below). In particular, letting S = {(X,, Y;): :j < i) among all pairs of concepts h, ht' E C with éI (h) LL (h') O, since they agree on examples in L,-1, we have
érq.. (h) érq. (h') x eto, (1) - ērq, (h') éts (h) ,
so that we can make use of concentration inequalities for estimating differences of error rates from the i.i.d. data set S (e-g., as in Lemma 7). Reasoning inductively, if érz,-; (h*)
such concentration incquality guarantees that among all la E C with ét (h) = 0, étq. (h*) can never be too much larger than erq.., (h), so that if the algorithm does not query X; (meaning crq._. (h' -b)) is much larger than érq. (h )), the corresponding label ÅJ must be h² hXx), so that adding (X., ūs) to L; retains that (h*) O. Conversely, if erq, 1 (h") and érq, (h²) are of similar sizes, then the algorithm has effectively verified that there exist concepts h hi' E C with (h) and er e rather close to erp(h") which nevertheless disagree on X, (h(X,) F h((),)), and querying for Y, and adding (X,, Y2) to Qi then strengthens the concentration of the érq, estimates, to help further distinguish among such small-error concepts in subsequent rounds.
Dasgupta, Hsu, and Monteleoni (2007) analyzed the query complexity of this algorithm, showing that it guarantees ery((h) S etr(h*)++ after number of queries Ó Ō (0r(3 + =]d ( +1)) Compared
to the original analysis of Hanneke (2007b), this improves the bound in its dependence on 0p(33 +)) reducing from quadratic 0r(3 + + to linear 0p +e). Again, the conclusion is that the algorithm's 's query complexity matches the lower bound (6) of Kääriäinen (2006); Beygelzimer, Dasgupta, and
26

---

Langford (2009) up to logs whenever 0p(8+ +) Ó(); however, again, in scenarios (C, P) with (3 + E) = Ω 3FF the bound offers no improvements over the sample complexity of passive learning.
The above techniques, and corresponding analysis in terms of the disagreement coefficient, seeded a vast literature, with many variations on the technique, analysis, and complexity measures, and many examples of scenarios (C, P) for which (r + E) can be favorably bounded. This branch of the literature is collectively referred to as disagreement-basee
active learning (see e.g. the works of Hanneke, 2009b, 201 1, 2012, 2014, 201 6b; Balcan, Hanneke, and Vaughan, 2010; Hsu, 2010; EI- Yaniv and Wiener, 2012; Friedman, 2009; Mahalanabis, 2011; Koltchinskii, 2010; Wang, 2011; Beygelzimer, Dasgupta, and Langford, 2009; Beygelzimer, Hsu, Langford, and Zhang, 2010; Raginsky and Rakhlin, 2011; Ailon, Begleiter, and Ezra, 2014; Huang, Agarwal, Hsu, Langford, and Schapire, 2015; Wiener, Hanneke, and El-Yvniv, 2015; Hanneke and Yang. 2010, 2015, 2019; Yan, Chaudhuri, and Javidi, 2018, 2019; Gelbhart and El-Yaniv, 2019; Cortes, DeSalvo, Gentile, Mohri, and Zhang, 201 9a; Cortes, DeSalvo, Gentile, Mohri, and Zhang, 2019b,c, 2020; DeSalvo, Gentile, and Thune, 2021; Shayestehmanesh, 2020; Puchkin and Zhivotovskiy, 2022). A detailed summary of this line of work presented in the survey of Hanneke (2014).
In the context of distribution-Fi free analysis, Hamneke and Yang (2015) showed that supp 0r(B + A 1 where is the star number of C (Definition 2), and where the sup is over realizable B+ distributions P (so that, in particular, they satisfy the condition erp < 3). Thus, in terms of their implications for the distribution-free query complexity QC, 8; B, C), these P-dependent analyses of disagreement- based active learning simplify to bound of the form (c, B, C) =
(sA))=)d(3 d(= +1)) In particular, such bounds are capable of providing improvements in S+s d
fistribution-free query complexity over the sample complexity of passive learning Mp 5; B, C) and only if < oo (which, as discussed above, is a rather strong restriction). This contrasts with Theorems 3, which provide improvements for all concept classes C, regardless of whether is finite or infinite. (The role of in Theorem 3 is merely in refining the lower-order term in the special case that s < oo). In this sense, Theorems 1, are most interesting for classes C with s = oc, since no previous techniques provide improvements over passive learning for such classes.
We note that, while the AVID Agnostic algorithm (Figure 1) itself should not be regarded disagreement- based active learner (as its primary advantage over passive learning is not based on the restriction of queries to DVS( elements of disagreement- braerreemen--beeed learning have been incorporated into it for the purpose of the refined lower-order term in the upper bound in Theorem 3. Specifically, the choice query examples in S n DA-1 Ai, in Step (and similarly Step 9) restricts to queries in Da-1 = (Vs(V This restriction is directly responsible for the lower-order term in Theorem being of the form Ō((s A () d) rather than ( as in Theorem 1. On the other hand, for the purpose of the lead term, this incorporation of disagreement-
queries is unnecessary, and indeed Theorem remains valid without this aspect of the algorithm: that is, in Steps 2 and 9, if we simply query all of St A... the algorithm still achieves the query complexity bound stated in Theorem I with its lower-order term Ō(!).
The argument leading to the refined lower-order term in Theorem 3 makes use of reasoning directly rooted in the analysis of disagreement- based methods via the disagreement coefficient (Lemma 22). and indeed we present P-dependent refinements of this lower-order term directly expressed in terms of ( + +) in Appendix F.2. In particular, we show (Corollary 28) the lower-order term Ö((s A 1) d) can be replaced by Ō(0p(3 + =d)) yielding an overall P-dependent query complexity bound of 82 (by any algorithm) to reduce this lower-order term to Ö(0p(8 + =)d) or even (00)) though we do show that other intermediate forms of the term are achievable, such as ò (0pp(8 + +)d [B+c
(d + log (1)) + (0r + a)dd). we further argue, in Appendix F.1, that it is not possible
A.2.2 Subregion-based (Margin-based)) Active Learning
Shortly after the work of Balcan, Beygelzimer, and Langford (2006), which included an analysis of homogeneous linear classifiers under a uniform distribution, Balcan, Broder, and Zhang (2007) proposed a refinement of disagreement- than querying every example in the region of disagreement DIS(V), they identified a subregion
active learning specific to linear classifiers. Rather
27

---

R S DIS(V) which suffices for the purpose of estimating differences of enror rates cfp(f) - (g) among f.g E V. The key idea is to choose R so that any f.g E have Px + 9) R) small, so that R captures most of the disagreements between concepts f.g E V that are far apart. In their case, since they were specifically focusing on homogeneous linear classifiers (i.e., concepts hhw (2) 1 [K,, 2)) 2 0] on X' IR²) under Px uniform in an origin-centered ball, they could describe this region R as a slab around the boundary of a current hypothesis hag that is, R = { E _dd ((ē, .x) S b for appropriate width b (which decreases over time as the algorithm progresses). In other words, the algorithm queries examples X; with low margin under the current hypothesis d. As such, this technique is referred to as margin- -assed active learning. They analyzed this technique for the realizable case and under a specialized noise condition (Tsybakov noise), and found it provides advantages over disagreement-basse the query complexity from d3/2. polylog( (t)) to d polylog( 1 (matching the query complexities achieved by earlier works Freund, Seung, Shamir, and Tishby, 1997; Dasgupta, Kalai, and Monteleoni, 2005; Dasgupta, 2005), while allowing for some robustness to non-realizable distributions I' (albeit not fully agnostic). The technique was later extended in various ways, including studying adaptivity to certain noise parameters (Wang and Singh, 2016) and generalizing beyond the uniform distribution, to general isotropic log-concave or s-concave distributions (Balcan and Long, 2013; Balcan and Zhang, 2017).
learning: in the realizable case, improving
This idea was extended to general concept classes C and distributions P. including the agnostic setting, in the work of Zhang and Chaudhuri (2014). Again the idea is to identify a region R C DIS(V) for which concepts f.g 9 E V have only small disagreements outside R: (xf # g) \ R) S 77 for a small 17. Rather than explicit region R (as in margin-based active learning), they simply choose a subset of the unlabeled examples via a linear program, which they show (in the analysis) can be related to an optimal choice of such a region. We discuss this technique in detail in Appendix F33.
The implication of this refinement of disagreement- based learning is a Pedependent query complexity bound, stated in terms of a subregion-base refinement of the disagreement coefficient, defined as follows (adopting some simplifications from Hanneke, 2016b). As above, define the r-ball Br, (h', r) = (h E C: (x(x h(x) + he (x)) r) for r >> 0. Also, for 17 2 0, define
1 (Brr = inf Px (R):
Px # R) S R +
3
sup BEBA (hr,))
where R and f are restricted to be measurable. Finally, for e 2 0, define the subregion disagreement coefficient (Definition 31) as
$ (Br, (h* .r), (1-((rr)))) m)/c) V1,
(p(e,n) = sup r>
r
for an appropriate universal constant c > 1. The technique of Zhang and Chaudhuri (2014) provides a P-dependent query complexity bound of the form Ō ((pp(E 23) ( gd + +1))- In particular,
follows from the definitions that (p, 2,3) < 0p(23 + E) (see Appendix F.3), and Zhang and Chaudhuri (2014) discuss some examples where the gap is large. Thus, this represents a refinement of the query complexity bounds for disagreement- based active learning discussed above.
As primary example where (e, < 0r(3 + E), consider again the scenario of homogeneous linear classifiers on Rd under Px an isotropic log- log-concave distribution (as considered in the margin- based active learning works of Balcan, Broder, and Zhang, 2007; Balcan and Long, 2013 discussed above). In this scenario, Zhang and Chaudhuri (2014) show that pr(e, 23) = O log { (based on concentration arguments from Balcan and Long, 2013). Thus, in this scenario, the query complexity bound of Zhang and Chaudhuri (2014) is Ō ( + +))) In contrast, Hanneke (2007b) showed
0p(B + +) 22 v B+C case of isotropic concaee,,,,, so that the query complexity bounds for disagreement- active learning are roughly d3/2
for Px the uniform distribution on an origin-centered sphere special
( + 1). hence are suboptimal by a factor vd.
That said, in the context of distribution-fres analysis. it is unclear whether there are advantages from this subregion technique. Specifically, Hanneke (2016b) showed that supp (r(e, 0) = A = (where the sup is restricted to realizable distributions P), which matches the worst-case value of 0p(s)
28

---

(established by Hanneke and Yang, 2015). In (54) of Appendix F3,, we further extend this to pp(E, (using the fact that (p( n) 2 (r(n + E, 0)), establishing that (for E. 17 2 with 17 + E $ 1)
1
sup sup n) - 7
where again the sup is restricted realizable distributions P. Thus, the implication of the P- dependent query complexity bound of Zhang and Chaudhuri (2014) for bounding the distribution- free query complexity QC, 8; () is merely to recover the same query complexity bound ( +1) (
o+t ((5A ular, this means that the above query complexity bound of Zhang and Chaudhuri (2014) capable of providing improvements in the distribution-fie free query complexity of active learning, compared to the sample complexity Mp(e, 6; C)) of passive learning, if and only if < oo (again, a rather strong restriction). Again, this contrasts with Theorems 1, 3, which provide improvements for all concept classes C, regardless of s, with 5 merely influencing refinements in the lower-order term in Theorem 3.
already known to hold for disagreement-base active learning. In partic-
In Appendix F.3, we give a refinement of the AVID Agnostic algorithm, which adopts this subregion technique (in combination with the AVID principle). We show this Subregion-AVID Agnostic algorithm achieves P-dependent refinement of the lower-order term compared the original AVID Agnostic algorithm. For instance, one implication of this refinement is replacing the term Ó( A 2) d) in Theorem 3 with (pp((e, 5,))d), yielding P-dependent query complexity bound 8ht क0 (d + log()))) + Ó(pp(s, dd) It follows from example in Appendix F.I that the above quadratic dependence (p 5 cannot be reduced to p 5,3) (or even (0, 0)) without introducing additional factors, though we also establish intermediate forms of the term, such as 8+z
(p 53)d
A.2.3 Other Topics and Techniques in the Theory of Active Learning
In addition to disagreement-basee active learning and its subregion- based refinement, and query complexity bounds for the agnostic setting, the active learning literature also contains numerous other techniques and topics. Though these ideas are not directly used in the present work, we briefly survey them here for completeness, and in some cases, discuss connections to the results and techniques of the present work. For brevity, we omit most of the formal definitions, algorithms, and precise statements of the results, rather summarizing the essential ideas, and referring the interested reader to the original works for the precise results and details (some of which are also surveyed by Hanneke, 2014 in detail).
The earliest general theory of active learning, providing query complexity bounds applicable to any concept class and realizable-case distribution, was proposed by Dasgupta (2005). That work proposes a (C, P)-dependent complexity measure called the splitting index P E [0, 1J. based on the property that, for any 7 > and any finite set of pairs (f.g) E C² with PJ + g) > 7, there will likely be an unlabeled example X, for which, regardless of whether Y, is or 1, are guaranteed that at least o fraction of the pairs (f.g) will have at least one function incorrect on (X,, Y2) (see Dasgupta, 2005 for the precise definition). The idea is that measures a notion of progress, from querying such X,, toward reducing the diameter of the version space below 7. The pairs (J. g) in the version space having (f g) > 7 are the obstructions to reducing the diameter of the version space. The above definition guarantees there will be an example X, can query such that, regardless of which label Y; is returned, discarding all inconsistent concepts from the version space results in reduction in the set of such obstructing pairs, leaving at most 1 - p fraction of them. If we start with an a-cover V of the concept class C of size roughly a -d (with a < & small enough guarantee all queried labels agree with some h E V), we would require most O( log (2)) such queries to eliminate all obstructing pairs, and thus reduce the diameter of the version space below y. We can then decrease 7 by constant factor and repeat, until the diameter is below e, at which time we can return any surviving concept, yielding a query complexity roughly O log (t) log (t)).
The Splitting Index:
The splitting index also provides a lower bound 2(3 on the realizable-case query complexity (where, in this case, P can be Px-dependent, but should be At -indeppendent; Dasgupta, 2005; Balcan
29

---

and Hanneke, 2012: Hanneke, 2014 for precise statements). This is particularly interesting due to being Px-dependent, and yet still providing pear-matching upper and lower bounds (in contrast, other quantities such as the disagreement coefficient and serregion-based refinement only provide upper bounds, and provably cannot yield general Px-dependent lower bounds). Since the above results reveal the Px-dependenn query complexity can be well-captured by the splitting index, whereas Hanneke and Yang (2015) have shown the optimal distribution-free realizable-case query complexity is characterized by the star number (Definition 2), it is also natural to study the relation between these quantities. Toward this end, Hanneke and Yang (2015) have in fact shown that these quantities are equivalent in the context of distribution- analysis: namely, supp 1
min( [tJ..
The splitting index analysis also provides another interesting feature, which is perhaps missing from other works on active learning in the realizable case: it quantifies trade-off' between the query complexity and the number of unlabeled examples. This is reflected in the above (imprecise) definition in the part that requires that such p-splitting example X; is likely to exist in the unlabeled data (this is made precise in Dasgupta, 2005 by another parameter T reflecting the probability of obtaining such an example). Using a larger number of unlabeled examples can increase the likelihood of including an example X, that eliminates a larger fraction of pairs, so that the splitting index P can grow larger (hence decreasing the query complexity) for larger unlabeled sample sizes. This improvement from having larger unlabeled sample sizes is not reflected in other complexity measures proposed in the literature, and in such cases the splitting-based query complexity bounds can be substantially smaller than those based on these other complexities, such as the disagreement coefficient (see Hanneke, 2014 for explicit comparisons). It is worth noting that such trade-offs are not known to be possible in the agnostic setting.
While the original work of Dasgupta (2005) was developed for the realizable case, subsequent works have explored extensions to non-realizable settings under restrictions on the types of non-realizability. Specifically, Balcan and Hanneke (2012); Hanneke (2014); Tosh and Hsu (2020) have extended the theory to allow for so-called Massart noise, wherein it is assumed P(Y = h- (X)) 2/2 is everywhere positive and bounded away from O. The extension of the splitting technique that setting merely requires that we only remove a concept from consideration upon having sufficiently many errors on queried examples. The resulting query complexity bounds are then similar to the above.
To date, the splitting technique has not been extended to the agnostic setting in any meaningful way (e.g., to obtain query complexity bounds which could not also be obtained by, say, running disagreement-baase
active learning with an (e/2)-cover of the concept class). The agnostic setting presents significant challenges for this technique, due the p-splitting examples X; being possibly in ER(h") for the best-in-class concept h², meaning such examples cannot be trusted as the sole souree of information for pruning suboptimal concepts; see the scenario in Appendix F.1 (which is constructed therein for a different reason, but also illustrates this issue).
We may remark that the AVID principle, developed in the present work and employed in A has certain aspects that are intriguingly reminiscent of the splitting technique of Dasgupta (2005). As in splitting, Aavid aims to reduce the diameter of set V of surviving concepts. Toward this end, again as in splitting, it identifies obstructing pairs: f.g. g E V with Px + g) > Exs where En is the desired diameter guarantee at that stage. However, the main difference is in how such obstructions are addressed in the algorithm. While the splitting technique would attempt to resolve this obstruction by querying eliminate at least one of J,g for many such obstructing pairs, Aavid instead simply removes (isolates) the region {f # 9}} from the space X' (adding it to the A region). and estimates error rates separately in A and X' (2 A. Thus. in this aspect, the algorithmic principle underlying Asvid is considerably different from splitting. Nevertheless, this common focus on addressing pairs (f.g) obstructing the reduction of the diameter presents an intriguing connection, which might potentially warrant further exploration.
Empirical Teaching Dimension: Another approach to agnostic active learning, based on principles seemingly distinet from disagreement-bar based methods, was proposed in the work of Hanneke (2007a). The technique there is inspired by early work on Exact learning with membership queries in the realizable case by Hegedts (1995); Hellerstein, Pillaipakkamnat,, Raghavan, and Wilkins (1996), which found interesting connections between active learning and the complexity of machine teaching (Goldman and Kearns, 1995). Hanneke (2007a) extends those ideas to the PAC setting, starting with an upper bound for the realizable case, based on Px Px-deeendent complexity measure T(E) therein
30

---

termed the extended teaching dimension growth function: for an ii.d.Pxx data set S of size T(E) (roughly) represents the minimal size of a subsample which induces the same version space (for any fixed target concept )²). The main technique is to find sets of 7(s) unlabeled examples for which the labels are guaranteed to significantly reduce the number of concepts in (a finite cover of) the version space. The work also presents a realizable-case lower bound based on modified variant of this complexity measure.
Hanneke (2007a) further extends the upper bound to the non-realizable case, establishing an upper bound Ō ( +)d (*+ +1) In particular, this matches the lower bound (6) of Kääriäinen (2006); Beygelzimer, Dasgupta, and Langford (2009) up to logs when r + Õ(1) Hanneke (2007a) provides examples where T(6 + =) is bounded, including the class of thresholds (concepts [a, on X' = IR) and axis-aligned rectangles (of at least some volume) under restrictions on Px: however, as with the previously discussed complexity measures, r(8 + E) can be large as 34g for the "searching in the dark" type scenarios discussed above, in which case the above query complexity bound is no smaller than the sample complexity of passive learning. Indeed, as with the complexity measures discussed above, results of Hanneke and Yang (2015) imply that, taking the worst case over distributions, T(e) becomes equivalent to the star number (Definition 2): supp, (e)) R min (s. }
Variants of this T(E) complexity measure were later further analyzed (for several example scenarios, and more- generelllrllly, in relation to the disagreement coefficient), under the name version space compression set size, and (interestingly) have also been found useful for studying disagreement-basse active learning. by El-Yaniv and Wiener (2010, 2012); Wiener, Hanneke, and Ylniv (2015); Hanneke and Yang (2015); Hanneke (2016b); Hanneke and Kontorovich (2021).
Restricted Noise Models: Besides the study of first-order agnostic query complexity guarantees QC,(e, 6; B, C) (the subject of the present work), the theory of active learning additionally includes many works query complexity guarantees holding under other conditions parameterizations, or in other words, under various noise models. Here we briefly survey some of this literature.
The most-similar noise model to that studied in the present work is the benign noise setting (Hanneke, 2009b), which differs from the agnostic setting only in that it makes the additional assumption that infrec p (h) = inf, ph)) where the infimum on the right hand side is over all measurable functions h: X' - {0. 13 (not necessarily in C). In other words, the benign noise setting assumes the best-in-class error B = inf (r) is also the Bayes risk of P: i.e., the error rate of the function - [P(Y 1|X z) 2 2]. Since the distributions used to establish the lower bound (4) for passive learning satisfy the benign noise condition, this still serves as a suitable comparison point for the query complexity of active learning. Similarly, the distributions used to establish the lower bound (6) for active learning also satisfy benign noise, and therefore the lower bound (6) also holds in the benign noise setting. Notably, in the special case of benign noise, Hanneke and Yang (2015) have shown a result analogous to the present work: the optimal first-order query complexity of active learning is Ö (d + min (s. ( In particular, comparing to (4), this means, under the benign noise assumption, the query complexity of active learning is always better than the sample complexity of passive learning. That work posed the question of whether such improvements are also attainable in the more-challenging agnostic setting, a question which the present work answers positively. Notably, the above result for benign noise is even slightly sharper in the lower-order term, compared to our Theorem 3 (which has ds rather than s); I conjecture this ds can also be reduced to s in the agnostic setting. There are interesting connections or analogies between the algorithm used by Hanneke and Yang (2015) and the AVID principle developed in the present work, and we discuss these connections in Appendix A.3 below. However, one noteworthy point that Agvid requires vastly fewer unlabeled examples to obtain the query complexity guarantee, compared to the method of Hanneke and Yang (2015), so that the present work also offers some benefits over the known techniques for the benign noise setting as well.
A.3 Background of the AVID Principle
Having surveyed much of the related work on agnostic active learning above, we conclude our discussion of related work by discussing previous works in the learning theory literature containing ideas related to our main technique (the AVID principle).
31

---

Arguably the main innovation involved in this work is the decomposition of the space X' into regions X' Ai, and A..: and augmenting the predictor hy to be a (shallow) decision list of concepts from C. One key inspiration for the main idea underlying the technique is rooted in the works of Bousquet and Zhivotovskiy (2021); Puchkin and Zhivotovskiy (2022) prediction with an abstention option (evaluated with the Chow loss). Interestingly, this continues a long precedent of finding useful connections and cross-inspirations between active learning and prediction with abstentions (Mitchell, 1979; EI- Yaniv and Wiener. 2010, 2012; Zhang and Chaudhuri, 2014, e.g.... Specifically, Bousquet and Zhivotovskiy (2021); Puchkin and Zhivotovskiy (2022) consider methods exhibiting kind of transition time, in which they determine that, for some f.g g E C, abstaining in a the pairwise have
disagreement region {ar f(x)) # g(x)),, and predicting with in its complement, comes smaller Chow loss than the overall loss of the best h E C. Some reasoning very much analogous to this (and directly inspired by it) can be found in one of the base cases of the arguments in the present paper (namely, concerning the "early stopping" case in the algorithm), in which we find that in the case of early stopping (Step 4), we can find f.g E V and h1, h22 C, such that predicting with h in {f + g} Ai, (rather than abstaining), with f in { 9 \ A ig. and with hy in Aig. produces smaller overall error rate in compared to the best concept h E C. Of course, the algorithm and analysis here contain many additional pieces on top of this, but it is interesting that this connection to learning with abstentions still remains present at the core (though it is noteworthy that this connection is qualitatively different from the usual one, in that here we are not replacing abstentions with queries. but rather that part of the analysis inspires part of our analysis). We remark that this analysis of learning with abstentions by Bousquet and Zhivotovskiy (2021); Puchkin and Zhivotovskiy (2022) was also inspirational for an active learning method in the work of Zhu and Nowak (2022) (though the aim in that work is different from the present work, and the setting is generally not comparable to ours).
At high level, we can view the technique as also analogous to an idea of Hanneke and Yang (2015) developed for the benign noise model: namely, the restriction of the agnostic setting to the case the Bayes classifier (x) + 1[ 1|X = æ) 2 1/2] is in the concept class C. Hanneke and Yang (2015) prove a query complexity bound for this special case which matches Theorem 3 (and indeed, refines the lower-order term's is sd dependence to simply s). In that context, since the h Bayes E C. the only source of oonrralizzaiiity is in the noisiness of the conditional label distribution YJX. Thus, if an active learner could repeatedly query a given X, to receive multiple conditionally independent samples of Y, given X,, it could use the majority vote of these samples to effectively de-noise the label of X,, thereby identifying hiiaaye (Xt). This strategy only fails
P(Y = 1|X = Xt) is very close to 1 in which case this de-noising would require too many queries 2' to be worthwhile, particularly since such noisy examples have very little effect on the excess error rate (h) er p p (ay.)) As such, if the active learner cannot identify the optimal label within some number of queries, should abandon the example X, and move on. Of course, in the model of active learning studied in this work, and in the work of Hanneke and Yang (2015), an active learner cannot actually obtain multiple conditionally independent copies of the label Y,. However, by appropriate discretization of the space X' based on the structure of the concept class C, Hanneke and Yang (2015) are able to approximate this idealized behavior. The resulting algorithm effectively adapts to the noisiness of the labels of examples X, within the equivalence classes induced by this discretization, allocating more queries to the noisier (high-label-variance) regions (and abandoning the regions it finds to be too noisy). In that sense, the high-level idea behind the AVID principle similar in nature. The goal is isolate the regions where learning is more challenging, due to higher variance in error difference estimation, and allocate disproportionately more queries to these regions. Of course, in the agnostic case, this is made much more challenging, since the source of non-realizabilityy is not merely label noise, but also model misspecification (i.c., Rayes & (C) so that de-noising the examples may sometimes have little benefit (e.g.. it is even possible to have 33 >> O while P(Y l|X) {0, 1)). As such, the AVID principle necessarily makes greater use of the structure of the concept class to isolate such regions of high variance in error difference estimation.
It is worth mentioning that other works on active learning have also considered decomposing the space X' into subregions and learning separately in each region (c.g., Cortes, DeSalvo, Gentile, Mohri, and Zhang, 2019a; Cortes, DeSalvo, Gentile, Mohri, and Zhang, 2019b, 2020). However, we note 8" that these works retain the above issue of having a query complexity of the form c(3)d zz for a complexity measure c(3) (as discussed in Section 2) such that, in the worst case over distributions P
32

---

(respecting the 3 constraint) the results become ultimately no smaller than the sample complexity of passive learning.
The idea of decomposing a predictor into a decision list based on pairwise disagreement regions has an even closer parallel in the recent work of Hanneke, Larsen, and Zhivotovskiy (2024b), which removes a log factor from the lead term in the (first-order) sample complexity of passive learning, thereby obtaining an optimal lead term of θ _ (d + log (3)) The overall approach in that work is in many ways similar to the technique in the present work, though with some important differences in the actual algorithms. In particular, since the interest in that work is merely removing a factor
log( ()) (lg())
essentially suffices for the algorithm to reduce the best-in-class ervor rate in region
X' \ A down to [1/31 (for Px(A) = 0()), so that a uniform Bernstein inequality for the error rate of ERM implies the desired result in that region X' \\ A, and uniform convergence analysis of ERM under the conditional distribution given A implies the desired result in the region A. In contrast, our interest in the present work is factor of /3 in the lead term, with lower-order term of size ( and achieve this our algorithm aims to reduce (below e) the diameter of set Vi of surviving concepts, in region X' \ A (with Px O(3). We achieve this via uniform estimation of error differences, using an appropriate number of samples from these two regions, while precisely controlling the schedule of decreases of this diameter in the algorithm (in part by increasing the region as needed to maintain this schedule of diameter decreases). Nevertheless, the essential inspiration and strategy behind these two algorithms notably related, perhaps indicating that the AVID principle might in fact be a widely useful idea.
B Additional Definitions and Notation
We provide additional definitions and notation required for the formal analysis. A fundamental quan- tity in statistical learning theory is the VC dimension (Vapnik and Chervonenkis, 1971), which plays an important role in characterizing the optimal query complexity (and optimal sample complexity of passive learning). It is defined as follows.
Definition 4. For any concept class C, the VC dimension of C, denoted by VC(C), is defined as the supremum n. E NU {0} for which there exists sequence {zi...., Tn E X such that h E C) = 13 (i.e., all 2n classifications are realizable by C).
For brevity, in all results, proofs, and discussion below (where C is clear from the context), we will simply denote by d == VC(C). In all statements below, we suppose d < oo (see Appendix G). Also note that, by our assumption that |C] > (see footnote 1), we always have d 2
Additional Notation and Conventions: For any distribution P on X x {0, 1), denote by Px the marginal distribution on X. Throughout, we refer to any sequence $ E (X' x {0, 1})" as a data set. For any R. it will be convenient to define log(x:) = In(mmxxzz e)), and for log(æ//0) = z//0- = oc and 0 (log(#/0)) = O. For o, E RU ( we use a A b or min(a. b) to denote the minimum of and b, and a V or max b} to denote the maximum of standard big-O notation (O, Ω. O effectively hide universal constant factors, while Ô Ô effectively hide log factors) to simplify theorem statements. The precise constant and log factors will always be made explicit in the formal proofs. We also adopt a convention regarding conditional probabilities: all claims involving conditional probabilities given random variable should be interpreted as holding almost surely (i.e., for version of the conditional probability), such as when claiming that an event holds with conditional probability at least 1 8 given random variable X. We also continue the notational conventions introduced in Section 4, such as ER(h). DIS(C', {f & g). overloading set notation to treat A C X' as notationally interchangeable with its labeled extension A x {0, 1]. extending notation for set-intersection to allow intersections with sequences, and defining empirical estimates (A( =
0 we define
and b. We will make use
|S 9 AI/|S]. See Section 4 for details of these conventions.
Mcasurability: We remark that, formally speaking, an active learning algorithm can be defined simply as a measurable function A : (X' x (0. 1)) x X' + {0, 1}: that is, taking as input an i..d. data set = {(X,, fsm and an independent test point X and evaluating prediction X) {0. In this view, the number of queries is merely bookkeeping, keeping track
33

---

of the dependences of this function on the labels Y, For simplicity of presentation, we have adopted the common colloquialism of referring to the function h returned by A(S), which in this view simply refers to the function A(S.)), so that (h)(h) is simply the conditional expectation [[[[A(S. X)+ * Y]IS]. The measurability of the algorithms A defined in this work follows from measurability of the individual operations involved in their execution under the standard measure- theoretic assumptions on (X, C) specified in footnote 1. To simplify the presentation, we do not explicitly discuss this in the proofs.
C
The Query Complexity of the AVID Agnostic Algorithm
This section presents a detailed version of Theorem 3, bounding the query complexity of the AVID Agnostic algorithm. Recall the definition of the algorithm and notation from Section Before stating the theorem, we first discuss few additional technical aspects of the algorithm omitted from the high-level description in Section 4, starting with an explicit specification of the quantities involved. Let Co. C1 be universal constants, defined by Lemmas 7 and 8 of Appendix D. We define"! !I
20003 2
C 10- C" (8-60T) and C' =VC For given E, E 10,1) (arguments to Auvia), 16
VC"
as in Section 4 we let N = (1)g and for & E N, let Ek = C²-*, and we then define my == 3000C"co (d log C"cco) + log
The algorithm adaptively allocates data subsets S%- s2. 12... St during its execution, as described in Section 4.1. Recall that St. Sg, and St are all of size mg (for any k, for which they exist). The data subset St is of size m'e- formally defined as follows. For the value is and the set Ai, as defined in the algorithm at the time that S is allocated (either in Step for some value of k. or in Step 9, in which case let k N 1), letting
P&= := (PPst(nn)) define m'g [= (d + log 1(3+NV N(3+
We remark that, for simplicity of presentation, we have described the algorithm without explicitly discussing what happens if the algorithm runs out of unlabeled examples while allocating examples to subsets S2 - In this event, the algorithm can simply halt and return an arbitrary predictor h, as the analysis will account for this event in the ó failure probability. To avoid excessive clutter, we do not explicitly mention this case in the description of the algorithm or allocation of data subsets used therein (i.e.. we explicitly discuss this only in the analysis, and indeed only in the final part of the proof; see the discussion at the start of Appendix E).
The following theorem provides a bound on the query complexity achieved by Awvid along with a bound on the unlabeled data set size sufficient to achieve it. This result represents a detailed version of the upper bound in Theorem 3 of Section 4 (in particular, Theorems 1 and 3 are immediate implications of this result). The constant factors the big-O will be made explicit the formal proof. The proof is given in Appendix E.
Theorem 5 (Query Complexity of AVID Agnostic). For any concept class C with VC(C) < co, letting d = VC(C), for every distribution P on X x {0, 1}, letting 3 = inf (h), for any s, (0, 1). if the algorithm Aavid is executed with parameters (E, 8), with any number m 2 M(, 8: 8:3) of
The only part requiring some care in this regard is the definition of hu in (3), where formally we require that, given Vi-1. Aig. mí. the function (S), Sg x) + (x) should be measurable function; such a measurable function can be shown to exist assuming C (and therefore 1) satisfies the conditions of footnote 1, following straightforwardyy from arguments of (Dudley, 1999).
1l For simplicity of presentation, the constant C' plays two major roles in the algorithm. First, it controls the schedule of diameter guarantees EA in the algorithm. Second, it controls certain constant factors in uniform concentration guarantees employed in the proof (Lemma 10). If we were to separate these roles, into C1 and C2. respectively, the two values exhibit a trade-off. In particular, we can admit a schedule es = C!- for any choice of < C1 < 2 by an appropriately large choice of C" (diverging as C1 + 2) and corresponding C2 > 1 sufficienlly close to 1. The source of this 2 limitation is the multiplicative factor in Lemma 20 which, in the limit as C + oc and C2 + 1, becomes 2- We also remark that have defined constants that enable the cleanest presentation of the algorithm and analysis. We leave the issue of optimizing the constants to minimize the query complexity for future work.
34

---

i..d.-P examples, for value M (E, ò; 5) (defined in Lemma 24) satisfying
( 8; B) - o 3 +
dd ( ( log
+
( (1))
-
3d d
5)
8²
then with probability at least 1 - 8, the returned predictor h satisfies cr S inc er (h) +
and the algorithm makes a number of queries at most Q( 6; (3 (defined in Lemma 23) satisfying
d + log (1)) +min s log
( ddoo (
(ee,
0
log
E2
8dd
= +
$
d)
Remark on adaptivity to 3: We emphasize that the algorithm does not need to know 3 in its exccution (i.e., it adaptively achieves the above query complexity bound for all B). A more subtle point worth noting is that we can also run the algorithm without ourselves knowing 3 (to choose m), since the guarantee
query complexity holds for any unlabeled sample size 2 M 5; B). For instance, if we run the algorithm with a ff-independent number of unlabeled examples m = (
f (d (o (t) + log ))) the query complexity bound Q(=, 6; 3) would remain valid as stated in Theorem 5. Additionally, in the proof (see Lemma 24), we show that, in sense, even the unlabeled sample complexity (e, 5; (3) is achieved adaptively, since the algorithm (with no knowledge of ()) only actually uses the first (at most) M(e, 5; (3) unlabeled examples in the sequence. This is itself an interesting feature. In particular, if we consider an alternative setting where, rather than getting the unlabeled data altogether at the start, the algorithm can adaptively sample new unlabeled examples X; ~ Px one-at-a-time during execution (i.e., it has access to an unlabeled example oracle, which it can use to construct the data subsets S%. St. S .. St. during execution). the analysis establishes that the algorithm will succeed while adaptively sampling at most M 8; (9) unlabeled examples (and querying at most Q(,, 8; () of them), all without knowing 3 (or anything else about P).
D Concentration Inequalities
This section presents a number of useful concentration inequalities, essential to the analysis. We begin with the classic multiplicative Chernoff bound (Chernoff, 1952; Bernstein, 1924). We will find the following particular form to be useful; since this slightly different from the more-typical statements of Chernoff bounds, we include a brief explanation of how this result is derived from the more-standard exponential form.
Lemma 6 (Multiplicativee Chernoff bound). Fix any p E [0 and n E N, and let Bı,..., B,, be ii.d Bernoullipp) random variables. Let B = 2. 1 B, For any 8 E (0, 1), with probability at least 1 8, the following both hold:
2
p S max
2B, In
5
2
B < max
2p,
In
Proof. We include a brief explanation, based on more well-known exponential forms of the Chernoff
bound: namely, IB < (1/2)p) e ~mp/8 and IP > 2p) S e upp/ (see e.g., Zhang, 2023).
For the first inequality in the lemma, we note that it trivially holds if < & In ll(()), and otherwise, p 2 8 (3). then by the above exponential tail bound, we have P(B < (1/2)p) S e -up/8 < $.
n
For the second claimed inequality, note that it trivially holds if 6 In } > 1, so let focus on the case (2)) < 1. Note that for p' E [0, 1] and Bi...., BA i.i.d. Bernoulliyy'), and B' 1 Σn_ B for any x R the value of IP(B' > z) is non-decreasing in p'. Thus, letting p' max P. 3 In (n)) 2 p. this monotonicity (together with the second exponential tail bound above) implies PPB >>>>> 2p')= < PPBB' > 2p') < e < Š. The lemma then follows by the union bound, so that both of these inequalities hold simultaneously with probability at least 8.
35

---

We will also rely heavily on uniform concentration inequalities. Toward stating these, we first introduce additional useful notation.
VC dimension of collections of sets: As is standard in the literature, we overload the definition of VC dimension (Vapnik and Chervonenkis, 1971) to also allow for collections of sets. Formally, for any non-empty set Z and any non-empty A C 2 (i.e., a collection of subsets of 2), the VC dimension of A, denoted by VC(A), the supremum n E N U [0} for which there exists Z Z with 2| such that {2 n A : A E A] = 24 (i.e., it is possible to pick out any subset of Z by intersection with an appropriate E A). Equivalently, VC(A) is the VC dimension (Definition 4) of the indicator functions {1A A E A}.
Uniform concentration term: For any non-empty set Z and any non-empty A S 2 for any N and 8 (0, 1), define (for universal constant cu defined by Lemma 7 below)
E(n, A) (VCKA)lOS (VC(A))
log ()))
The following result represents uniform variant of the classic Bernstein inequality (or Bennett inequality) (Bernstein, 1924; Bennett, 1962). Chervonenkis (1974) (see Hanneke and Kpotufe, 2022 for an explicit derivation, via a layered application of Massart's lemma and Bousquet's inequality). We additionally include implications providing a uniform variant of multiplicative Chernoff bounds, which are easily derived from the stated uniform Bernstein inequality (taking B O).
be derived from results proven by Vapnik and
Lemma 7 (Uniform Bemssein and multiplicative Chernoff bounds). There finite universal constant co > 1 for which the following holds. Fix any n. E N, 5 E (0, 1), any non-empty set Z, and any set A 2 with VC(A) <0.." 12 Define s(n, 5; A) in (7). Fix any distribution P on Z and let Z = /Zi....,Zy, ~ P2 (i.id. P random variables). For any measurable set A S Z, define its empirical probability Pz(A):= [=):==> == E. 12, E A). With probability at least 1 - 6, every A, B E AU {0} satisfy the following (where A + = (A U B \ A) denotes the symmetric difference)
(P)(A)) - Px()) (P(A) - P(B))
s Viiin(P(A@ B), PA B)) 8; A) + +((n, A).
Moreover, for any & 0and a E (0, 1) satisfying e (n, 6: S Sse the above inequality immediately yields the following implications: AA E A.
Px(A) 2 = P(A) > (1 - a)s, P(A) 2 = Pa(A) > (1 - a)E,
or equivalently, P(A) < (1 ax)e = Pp(A) <8 or equivalently, P2( S (1 - aie = P(A) <.
We also make use of a uniform concentration inequality which refines the classic uniform convergence bound (VC(A) log(?)) of Talagrand (1994) in the case that U has small measure under P. The lemma is well-known in the literature, and follows immediately from expectation bounds based on chaining involving an envelope function (e.g., Theorem 2.14.1 of van der Vaart and Wellner, 1996) together with Bousquet's inequality (Bousquet, 2002) to achieve high probability. For completeness, we provide brief direct proof, by simply applying the uniform convergence bound of Talagrand (1994) to the samples from the conditional distribution given a set 2 A.
Lemma 8. There is a finite universal constant e₁ 2 1 for which the following holds. Let A be as in Lemma 7, and suppose D C Z is a measurable set such that VA E A, A C D. Then for the same quantities as Lemma 7, if P(D) 2 9
n In()), then with probability at least
V.AAA.. A
P(D) (VC(A)) + log
( )
((A)) S c n
We suppose standard mild measure- measure-theoretic restrictions on A and the o-algebra of Z, from empirical process theory: namely, the annie-ldmissible Suslin condition (Dudley, 1999).
36

---

Proof. Note that the samples in Z n D are conditionally ii.d. P(-D) given 1 n D). For each A E A, denote by (2) := (A) (or 0 I2 n = 0). Applying the uniform convergence bound Talagrand (1994) to the samples in under the conditional distribution given |Z D),
together with the law of total probability, yields that, with probability at least 1 - 2.2 AA E A.
(2(A)) P(AID) & V |ZnD]
(VC(A) + log
2
(8)
for a finite universal constant oj 2 1. Moreover, by Bernstein's 's inequality (see Theorem 2.10 of Boucheron, Lugosi, and Massart, 2013), with probability at least
PPx(D 1 2P(D) In
1 In
P(D) n
+
S 2
In
where the last inequality is due to the assumption that P(D)
In ). By the union bound, these two events occur simultaneously with probability at least d. Suppose this occurs. In particular, by the assumption that P(D) 2 In( (9) further implies
P(D) In
7 DI = Px( 2 P(D) 2
2 P(D),
3
so that the right hand side of (8) is at most
3 nP(D)
(VC(A) log (7))
d
Combining this with (8) and (9) implies that VA A, since A C D.
(a(A) - P(A) ( PPDDPPP)
P(D) In
4 5
- P(D) P + PE(AID)2
3P(D)
)2) +
P(D)
4
< V
VC(A) + log
In
5
P(D)
(VC(A) + log (2))
n
where = CG + 2 In(4e) (recalling log(z) = In(x V e)).
E
Proof of Theorem 5: Query Complexity of the AVID Agnostic Algorithm
The formal proof of Theorem 5, given the end of this section, will be built up from sequence of lemmas, roughly following the outline presented in Section 4.2.
Throughout this section, we fix arbitrary concept class C (with d= VC(C) < <o) and distribution P X x (0, 1). let 3 = inf (h), fix any E, E (0,1) (where E, are inputs to the AVID algorithm), let (X,, Y1), (X2, Y2).... be independent P-distributed examples, and we let all values (N, Ek. my, myg etc.) be defined as in Appendix C, based on these values e, 6, and the examples (X1, Y1), (X2, Y2),.... .... Also let ht* C denote any concept with
E
erp(h") < inf er (h) + 10r*
(10)
REC
For full generality, we do not assume there exists minimizer achieving the infimum on the right hand side; rather, any choice of ht* satisfying this mear-minimality property will suffice for our purposes in the analysis below.
37

---

To simplify the proof, we will establish the sequence of lemmas under scenario where the algorithm executed with an inexhaustible source of examples (for the adaptive allocation of data subsets): ie.. an infinite sequence (X1, Y1); (X2, Y2)..... of independent P-distributed examples. However, it will follow from these lemmas that, with high probability, the algorithm only depends on a finite prefix M (e, 8; (8) as in Theorem 5 (see Lemma 24). At the end of the section, when combining the lemmas into a formal proof of Theorem 5, we will return to the standard setting where the algorithm has access only to such a finite prefix. In that context, the event that the algorithm attempts to access any examples (Xx: Y,) with > mn will be accounted for as part of the allowed 6- s-poobability failure event, and thus (as mentioned in Appendix C) in such a case the algorithm can simply halt and return arbitrary predictor h. As mentioned in the remark following Theorem 5, the fact that the algorithm adaptively decides how many unlabeled examples use is itself interesting feature, as it means the algorithm can be considered adaptive to 3 even in its use of unlabeled examples.
(X1, Yi).... (Xm: Y.). for a sufficiently large
Before proceeding with the proof, we first introduce some convenient notation regarding the values of k and encountered in the algorithm. If the algorithm returns in Step 9, denote by K := N + 1, and otherwise. let K be the maximum value of l reached in the 'For' loop in the algorithm; argue in Lemma 10 below that the algorithm terminates eventually, with high probability, so that this latter case coincides with the case of returning in Step 4, with K being the value of k which this occurs. Let K. := (1...., K A N): that is, the set of values of l encountered in the 'For' loop in the algorithm. Also, for each & E K., denote by I the values of encountered by the algorithm round k; in particular, for ls < K, In = (i....., 1 J. In the case K = N + 1, for convenience also denote by Ix-1 == {ix-13-
We begin with lemma which motivates our choice of sample size my for S S St. Recall 3300C" (d log C"ca) + log (t)) Also recall our convention (adopted throughout this
m. :=
Ek
work) of treating sets D C X' as notationally interchangeable with their labeled extension D x (0, 1}. such in A n D or A \ D for A X x 10.
Lemma 9. Fix any set D C X and define a family of subsets of X x 10,
A (ER()) = (ER(H) (1 Nu + \D D: Lgghec
u u(1F= # (0.1)) \ D: f.g c) u (ER(N) :D:
For any n E N and 8' E (0, let E(n, 8'; A) be defined as in (7), For each k E {l,..., N + 1}.
letting 6R = 8s
it holds that 72
Ek C"
e em,, Ax; <
(11)
Proof. We begin by bounding VC(A), as needed to evaluate e(my, dz: A). Define the following families of subsets of X' x 10;
Ao= == (FR(h) h E C) (0. (0,1)};
C) (x x (0,1)), A = {((A) C) \D:
A : (1 g) x
D: A,B e Ao, C E AI).
First note that A C A2. To see this, note that for any f,g, h E C, taking A= B=BR ER(H), C= [ + g) (0, 1}. we have that ((ER())N( = 9) (ER(()))) #
C) D E A2. Similarly, for any f.g E C. taking A= 0, B = X x 1) + g) x (0.1)
reveals (ff * g] x 10 D = ((A)O) (BnC)) \ DE E A2. Finally, for h E C, taking
A ER(h), B = 0. C = ( f3x = reveals BR(h)\D= ((ACC))(B)C)) Ag.
Next we bound VC(A2). It is immediate from the definition that VC((E((A) h CJ) = d. Moreover, this implies VC(As) < d 2 (Vidyasagar, 2003, Lemma 4.11). Also note that A S {A @ B A, E Ao), where A B == (A B) (B \ A) is the symmetric difference: that is. trivially (X' x {0, 1}) @ = X'x 10, and for any f.g E C. {f # g) x 1) = ER(f) @ ER(g). Thus, any element of A can be expressed as a fixed function of four sets A, B, A', B' E Ao: namely (A, B, A', B') + (AA)(A's @ B'))U(B (A' @ B'))) D. Based on this fact, well-known results about the effect of such combinations on the VC dimension imply VC(A2) = O(VC(A))): explicitly, Theorem 4.5 of Vidyasagar (2003) implies VC(A2) < 25VC(A)) < 25(d + 2). By the
38

---

assumption that |C] 2 3 (footnote 1) we know d 2 1, so that 25(d + 2) - 75d. Altogether, we have VC(A) < 75d. With this in mind, we may note that (also using that
2 and C" 2 9C3)
300C" co
C" cn
m& 2
d dlog
+ log
Ek
Ek
150C
Co
9C
d log
+ log
Ek
Ek
δek
20
CO
VC(AA) log
+ log
(12)
Ek
Ek
In partieular, if VC(A) 1, then by Corollary 4.1 of Vidyasagar (2003), (12) implies
mg
CmCco
VC(A) log
VC(A) log
mi
1
(13)
&k
6R
Moreover, VC(A) = 0. then recalling we define ( log(1 (1/())) 0, (12) trivially implies (13) in this case as well. Thus, regardless of the value of VC(A), by definition of e(m,, Ay; the claim in (11) follows from (13).
We continue the proof with a lemma conveniently summarizing several uniform concentration bounds which useful in various places throughout the rest of the proof. In particular, the lemma focuses on concentration inequalities in the X' Ai, region focus of the learning algorithm. It will therefore be convenient to explicitly define the portion of the functions in V specific to this region: namely, for every l {l,.... K}. define
Vi (fi(==)) + h1 f.g E V
Lemma 10. On event En of probability at least for every k E {I,..., K), holds that
Vh, h' E Vi (Psg (ER(() n D A Pss. (ER(h') 7 DD-1 A.t))
(P(EER(h) \ Aid) - P(ER(H) \ And)
< VVPx(( # W) ii))
Ek + Ek C C"
(14)
and for every lo E K. and every E Is Vf.g E C,
Pss,, (15 + g) \ A 2 Ek+2 = Px(1f + g} A.) 8643
(15)
Psg. (1f + 9) \ A.) S 6k+2 = Px(1S + g) \A,)) < <E+1l,
(16)
and moreover, max Ip S 1, In particular, the latter implies the algorithm eventually terminates (in Step 9 9f N + 1, or Step if K S N).
ex+
Proof. Consider any (1....,N + 1} having a non-zero probability of S K. Let 5g be as in Lemma 9, Recall that the data set St. is independent of all data involved in rounds k' < k in the algorithm, whereas the event < K and (in this event) the set Ai, are entirely determined by data involved in rounds k'' < k. Thus, even conditioned the data set S remains conditionally i..d..P. Therefore, letting Aş denote the set A as defined in Lemma with D Air. applying the uniform Bernstein inequality (Lemmaa 7 in Appendix D) with this A& under the conditional distribution given the event i < K and the set Ase implies that, with conditional probability least dy given the event & K and the set Aiy. holds that NA, E Ak-
the event that & < K and and the set A
( - (P(()) / /P(A @ B)e(ms, As) + s(ms, 8n; As). (17)
Since this work focuses on binary classification, V V--1h E C). where Maj(f. g. (x) = 1[f(x) + 9(x) + h(x)) 2 2] is the majority vote function. The definition of Vil above expresses more-general form, which, as we discuss in Section G, also extends to multiclass classification.
equivalently be stated as (Maj(f. h) f.g
39

---

By the law of total probability, on an event E of probability at least 1 - -ōg. if K I K (and thus Ai, and As are defined) then (17) holds AA, B E As..
In particular, on the event & supposing k v K, if we consider any h H E V then for the sets A = ER(h) \ Ai E AA and B = ER(h') \ A.. E AR. we may note that the symmetric difference A + B (ER(h) @ ER(b)) Aix = (th + h'3 (0,13) Aig. so that together with (11) of
Lemma 9, (17) implies
(Pss (ER(H) \ A..) - Pst (ER(K)) \ A.)) ((A))))(P(E(M)) (P(ER(M) \ A.,)) P(ER()) \ A..))
V Px * h' Aic)
Ek C"
+
(18)
C"
To arrive at the claim in (14), we merely note that for any J.g, E Va-1 and h E C,
letting DL(f, 9. h) == fi(s= + (170) and DL v.) == f'I(-=g) + + for any
r E X DR-1, we have g(x) = [() = (()) = g (x), so that DL( 1)(x) = =
DI. "g. (2r). Thus, any h, h E V. k-1 have h(x)) = h'(x) for all x & DR-1, and therefore
Pst
Psg (ER(H")DD--AA) = Psg (ER(M))A.)) Pst (ER(h)) (i.),
so that (14) follows from (18). To unify the discussion below, for any (1...., N + 13 with probability zero of l S K, also denote by Fo,: the event (of probability one) that k: K.
Turning now to the claims in (15) and (16), consider any (k,z) having non-zero probability that k E KC and E It. Note that, since Sy, ; is a data set of size my, allocated from the remaining unused unlabeled data upon reaching Step 5 with values (k, i) (noting this can happen at most once in the algorithm), the samples in SE are conditionally i.i.d.-P given i E K. and i Ig, and moreover, S is conditionally independent of A, given the events that k I. and i Ia. In the event that k E I. and i E Ix. let Ak,s denote the set A as defined in Lemma 9 with D = A,, Recalling again our
11 and C" 2 32C3 definition of C = To
C-I) note that for a = J. (11) of Lemma 9 implies
E(mR; ōR; AA.,)) < Cti the conditional distribution given the events that E K. and E I and the set A;, we have that with conditional probability at least 1 - ōR. Vf.9 E C, the set (ff * g) \ A,) x {0, 1] Ak,s satisfies
a² Ek+2 < 4 Ck+1- Therefore, applying Lemma 7 of Appendix D under
a²
Psr. (U + 9) A.)
2 ER42 = Px(Uf # 9} \ A.) (1 a)Ex+2 = 6k43
and
Psg. (1 + 9} A.) S (1-
Px(U + 9) A.) < Ek+1
By the law of total probability, there is an event Fo,s.; of probability at least 1 - 5s. on which, if k K. and i Iz. then the above inequalities hold Vf.g C. To unify cases, for any (k: i) with
k s N and i < 1/E243 having probability zero of satisfying& k E IC and E In. also define Eo, as the event (of probability one) that either l & KC or i $ It.
We have thus established (14) for all S K and (15 - 16) for all k E K. and i E I. with i S 1/E44S. on the event Ep == (NeşN+1 Fo,k) ) n nu Oisajemns Eo,... By the union bound, Ey fails with probability at most
N+1
N+1
N+1
26
N+1
5k +
Σ dz
1
8c
Ch-3 <
Ck+3
Ek+3
36
4'
VSI/EN+O
1=1
k=1
where the equality follows from our definition of 6₁ follows from our choice of C = -0-
(from Lemma 9) and the last inequality
72
11
Finally, we argue that, on the event Eg. for any k E K. the maximum value of i E I& satisfies i < 1/EK+3- We argue this by induction. Specifically, we will argue that, for any k K. and i E Iz, Px (X A,) < 1E8+3- For the purpose of induction, suppose that for some k E K. A, < 1 - igE++3 (which is trivially satisfied for k = 1, since in = 0, which can therefore serve base case for induction). Taking this is base case for further nested
we have (x
40

---

induction on E I& (noting that in is the minimum element of I&), suppose that for some E I we have (x \ A I 1 15k-3- Since probabilities are non-negative, this necessarily implies i < 1/Ex+3- Then note that, if i is not the maximal element of Ix. the algorithm augments A; in Step 7, so that 11+1
U & g) for (f.g) defined in Step 6. By the criterion in Step 5, we further know that Ps... (1f + 9) AA))) > Ek42- Since i Σ 1/Ex43, the event Eg implies (15) holds, which therefore implies Px (A 4) Px( # 9} A,) Ek+3, so that Px \ A1+1)= = = A.) - Px(A++1 \ A.) <1- (i 1)E4+3. thus extending the inductive hypothesis. By the principle of induction, this establishes that Px(x)) \ A.) I 1 i for every i E Ix In particular, returning to the induction on k. in the event that this k is not the maximal element of K. we have i Ig. so that (x Aig < -ii--EE- 1
1 which therefore extends the inductive hypothesis for k. By the principle of induction, we have thus established that every & K and Is satisfy Px(X) A S iER+3- In particular, since probabilities are non-negative, this immediately implies any such (ke i) satisfy i S 1/EK+3, as claimed. Thus, on the event Eg, we have established all of the claimed inequalities: (14) for all 1 E (1....,K) K), and (15 16) for all & E K. and i E Ix which further satisfy max I& S 1
5218"
The following is an obvious implication of Lemma 10, which will be useful to state explicitly for later reference.
Lemma 11. On the event Eo, for every k E K and i E Ik if the algorithm reaches Step 6 with these values (k, i), then for f. 9 as defined there,
Px(1f # g} \ A.) > Ek+3.
Moreover, on the event Eg, every E (1,...,K) with D., + 0 satisfies Px(Air) > Ex42.
Proof. By the condition in Step 5, if the algorithm reaches Step 6 then Pss (Lf # g} \ A.) > EK+2. By (15) of Lemma 10, on the event Eo, this implies (x * g) \ A.)) Ek+3-
Turning now to the second claim, suppose again that Fs occurs, and first note that this claim is trivially satisfied if Ai 0. To address the remaining case, suppose Aix * 0. and consider the minimum value k' E {1.... K} for which A, * 0. By definition we have D;, = Au = 0. which implies must have k' > 2. By minimality of K, we also know that the algorithm reaches Step 6 at least once during round k = k' - 1 of the 'For' loop, in particular with i = ig. Thus, letting (f, (f.g) be as defined in Step for these values (ks,) i) (K' i1) by the first claim in the lemma, we have (A(A 2 (J + g) Px[ # g} \. Awv_,) > -w+2- Thus, since Aig is non-decreasing in k", and minimality of k' implies all k" with Aigr * 0 have K" 2 k', we conclude that every k" E (1....,K K} with A # 0 satisfies Px (Aig.)) (x((ai)) > ck'+2 2 Ek"42-
Next we state bound on the diameters of Va-1 and = useful for Lemmas 15, 20, and 22.
Lemma 12. On the event Ev, for every t: E {l,.... KK.
sup
((f + g} Aix)) SE
(19)
and LEEVE"
sup (xf + g) Ait) < 3E
(20)
Proof. Throughout this proof, we suppose the event Eg holds. The inequality (19) is trivially satisfied for k = 1, recalling that Vo = C and 61 = C" = 1. For the remaining case, fix any k' E (2.... . K} and consider the round i k'' in the 'For' loop (noting that, by definition of K, we have k = K' - 1 E I. regardless of whether к = N + 1 or K < N). Since k + = k' < K, we know the algorithm reaches Step in round (i.e., it does not terminate carly in Step 4 during round k). In particular, this means the condition in Step 5 fails for the value i = i++1 = max Ig: that is,
max Pst, (U + 9} \ A < Ex+2. By (16) of Lemma 10, this implies
Px 9) AWn)) figEv--
sup
sup
Px(SS 49) \ Aien)) <E = EW
S.gEV
This completes the proof of (19) for every & E {l,..., K}.
41

---

To show (20), let & E fl.... . Kj, and for any f.g E V and h E C. denote by DL(f.g. == (1 + hi (1+0) E V Note that for any f. E Vi-1, h E C. and Z E X, g(x) = 1(=)= f' = (xx), then DL g, h) = ( g'. (x))). Therefore,
Px (
S PXU + # \ A..) + Px (1 + o/ (())).)+++ + Px (Ls + f A S 3Ek
where the last inequality is by (19). This completes the proof of the lemma.
The following Lemmas 13 and 14 concern concentration of empirical errors in the set Sin Ain which will be useful in establishing guarantees on the quality of hy (in Lemma 15) and of the functions in Vi (in Lemmas 16 and 17) below. We first need to argue that the p& quantities approximate Px (Arx). which leads to the data sets S being of appropriate size for concentration of empirical error rates.
Lemma 13. There is an event E1 probability at least 1 1-2 2 such that, on Eg Ak E (1,..., K}.
the quantity Pu: == 2p5 (v))) (as defined above) satisfies
Px(A..) S Pa S 4P.(
(21)
Proof. Consider any l E {1..... NN + + 1} having non-zero probability that &o I K. Note that the execution of the algorithm does not depend 9 k = N + 1), supposing this step is even reached in the algorithm (i.e., k S K). Thus, since the event that k < K and the set Ai, are both completely determined by events occurring prior to this first time the examples in 5% are used by the algorithm, we have that St is independent of these. Thus, conditioned on the event that & S K and on the random variable Diz, we have that for the sequence of my examples (X,, Y2) comprising Si. the corresponding sequence of indicator random variables 1[X, E ر are conditionally independent Bernoulli (xx (Ai))) random variables. Therefore, applying a multiplicative Chernoff bound (Lemma 6 of Appendix D) under the conditional distribution given the event l S К and the random variable Aiz. together with the law of total probability, we have that on an event F1, of probability at least
St any time prior to Step 2 of round k (or Step
dek if A: S K, then 44
8
88
Px(Ai)) S max 2P S4
(ii))
In
(22)
8ER
6
88
Ps (A)) max
2Px
In
(23)
me
dER
For simplicity, for any (1, .I.....AA N + 1} having probability zero of l: S K, simply define FL, as the event of probability one that k > K, so that the above claim also holds (vacuously) for such
values k. Define an event Ej N 0==1 Ei, and note that, by the union bound, E₁ occurs with
probability at least 1 - E k=1 44
V+1 de
We now argue these inequalities further imply the simpler inequalities stated in (21), on the additional event Eg. Suppose the event Eg n Ej holds, and let k E (1...., K]. If A., = 0, (21) trivially holds since Pa = 0- = Px ). To address the remaining case, suppose Ai, A 06. By the final claim in Lemma 11, we have Px(Aix) > Ex42 Also note that, by definition of my (and
recalling [C] 2 2, which implies d 2 1), we have 8 In
Ek+2. In particular, these imply <
my
DEk
(A,,) > 25k+2 mik
In
so that the right hand side of (23) equals 2Px (A.,) and hence
KEk
Dx < 4P (A.)). Moreover, since mig side of (22) cannot be achieved by the second term (as it is smaller than the quantity on the left hand side), so it must be achieved by the first term. Therefore, Px Px(A,,) < 22ss (Ai,.) pk-
S In
88 Deu
< Ex+2 < ( the "max" on the right hand
Using Lemma 13 to bound the size of the data set St (which is based on (k)) we now ready to establish a concentration inequality for the error rates in the Di, region in the following lemma.
Lemma 14. There is an event Eg of probability at least 1 - I such that, on the event Eo n E1 n Eg, vk E (I.....KK K),
Ssg (ER(h) n A.,) - P(ER(M) Aw)) 5k
sup heC
(24)
42

---

Proof. Consider any k E f1...., N + 1} having non-zero probability of k I K. Supposing k S K occurs, define collection of sets A₁ := (ER(h) S., h E C). Note that VC(A() S (which is immediate from the definition of VC dimension). We aim to apply Lemma 8 of Appendix D, refinement of the uniform convergence bound of Talagrand (1994), which accounts for an envelope set D 2 A' specifically, we instantiate the various sets and variables in Lemma 8 to be 2 X' x (0, 1, = m'g A = Al. envelope set D = Aig data set Z = S% and confidence parameter 6/[4(3+ + N )))),, and we apply the lemma under the conditional distribution given the event k < K and given the random variables Ai, and m/g. Since the event that k S K, and the random variables A. and m/g are all completely determined by examples allocated to data sets before allocating examples to the data set S% we may note that the my examples comprising S are conditionally independent P-distributed random variables given the event that k I K and given the random variables A., and m'- Thus, applying Lemma 8 of Appendix D under the conditional distribution given the event that k S K and given the random variables As, and m together with the law of total probability, we have that on event E2 of probability at least 4[3+N-Ry" if h: I K and
Px(4 2
9 In x)))) then m/
Px(A
4(3+N - k)2
sup ket
Psg (ER(H)NA - P(ER(H)AAW) S sai
d d+
(25)
m'k
5
For simplicity, for any l E {1, (1,...,,A) N N+1 1} having zero probability of k S K, let F2, denote the event of probability one that > K. Finally, define E2 = N
N+ Eg,k. and note that, by the union
bound, E2 holds with probability at least Ek=1 43+NNE)
2
00 2 4'
Now suppose the event Eg E E occurs, and consider any & E fl..... K}.
If "l.....,,.... = D then (24)
holds trivially since the left hand side of (24) is then zero. To address the remaining case, suppose Ai, * 0. By the final claim in Lemma 11, we have Px(A, > Ex+2. Moreover, by Lemma 13 we
have Ph 2 Px (. Recalling m/ = Ce
4(3+ -2)2 ))} these imply
8
C
1(3 + N k)2
9 In
16(3 N k:)²
m'
In
CAEK+2
Ek+2
8
where the last inequality follows from e₁ 2 1 and C" 2 1804. Thus, 9 In 16(3+N-K R)) my Ek+2 < Px(Aix) By the definition of Ez, it follows that (25) holds. Moreover, since fr: 2 Px ix))
we have that m' 2 C" C=ccPXx(d.)) (d + log [43++ (1)+ )) so that the right hand side of (25) is at most
52
thus establishing (24). VCT
Ek
Combining the concentration inequality from Lemma 14 with (14) of Lemma 10 together with (20) of Lemma 12 yields a concentration inequality for the differences er., - ei = among h h' recalling the definition from (I):
(h) == (ER(h) n Da-1 \ A..) + (ER(()) n A..)
In fact, the implication is stronger than this, admitting functions h, h' E V In particular, for any k E (1,.... K), note that V/= in (2) can equivalently be defined as
V { Milxi,, + h2lo,, :i E V Vi cC
The following lemma provides concentration inequality for (h) - (h') among functions h, h V/-11
Lemma 15. On the event Eo n Ei E2, for every k {I...., K} we have
sup
((t) (h) -
(erp(h) -rp(()))) 1 Ek
(26)
40"
e 8-1
recalling that C²
Moreover, (26) implies
erp(hv) S inf erp(h) + Ek nev
(27)
AC"
43

---

Proof. Suppose the event Eg n E1 n Eg holds and consider any k E {1..... K]. Note that for any h A + hills,, E k-1 we have (h) (() A.,) P(ER(hg) A..) and
(r)) Pst (ER(()())) ( DR-1 A Psg (ER(h2) A
Consider any h1, 11 E Vi- and any h2, h22 C, and let h hilxis, + h2ld,, and 1' MA + 11g"T By Lemma 14, we have vhς E {12 122
Pss (ER(K) )...) P(ER(N)) n AAw) &k Additionally, since (20) of Lemma 12 implies (x # K1 \ Ai,) S 3ex, the inequality (14) of Lemma 10 implies
vC"
- - PE P(ER(M)))
352 C"
Ek_
2 VC"
(28)
C"
where the last inequality follows from C" > 14. Combining these with the triangle inequality
(namely, ((a - b) - (ä' + 8)) ((a + b) (a' 8/)) S ((ā a') (a a')l + 18 bj /8/ D)
yields that
45k Ek
(er - ((') (er - erp((h)) <
VC" 4C"
To see that (26) implies (27), note that, by the definition of hg in (3), h he has minimal (r))
among all h E 1- that is, Vh E 1 e - -r (h) < 0. Together with (26), this implies that vh V/th erp (fx) erp (h) I ( ctr (h) + 10 10
In particular, Lemma 15 immediately implies the following lemma concerning the quality of the functions h in Vn. Lemma 16. On the event Eo n E1 n Eg, Vk E K. Vh E Va-1, the following implications hold:
5Ek
h e Vi = ehp(h) S erp erp(fus) (hx)
(29)
40"
crp (h) S erp (ht)
3Ea h E Va.
(30)
40'
Proof. Suppose the event Eg n Ei n Eg occurs and consider any k E K. and h E Va-1. In partieular, note that we also have h E V/ k since letting f = g h. we have h = f11/=9 + h1 [/4 E V and thus h = h1xAA,, + his,, Vi"
If h E V1, then by definition of Vi in Step 3 we have (1) of Lemma 15, this implies e erp(fu) S Et
- err S E. Together with (26)
+ e Te.. which establishes (29).
On the other hand, if erp (h) ehr(h)) < 3 et (h) - ( 1C
then (26) of Lemma 15 implies Cr. Thus, any such h is retained in Ve, which establishes (30).
35.
+ I67
The main implication of Lemma 16 pertains to the early stopping case in Step 4, which we turn to next. Recall h* denotes an (arbitrary) concept in C with er < inf cr) + 164- In the following lemma, in addition to arguing that the predictor i returned in Step 4 has low excess error rate compared ht (in fact, negative), this lemma also reveals a second major role of this early stopping case: it ensures that on all rounds & in which the algorithm does not terminate in Step 4, we retain ht* E Vk.
Lemma 17. On the event E, 0 E1 Ez, the following implications hold for every i KC
If Asvii does not return in Step 4 on round k, then h²* E Vn.
. If Aavvid returns in Step 4 round k. then exp (hx) < erp
44

---

Proof. Suppose the event Eg n E1 n Eg occurs. We will prove the first claim by induction on k. As Vo. Now, for the purpose of induction, let & E K. be such that he E VE-1- Also note (as discussed in the proof of Lemma 16) that this also implies h² E V/= If geg. In particular, this implies 4c
base case, we trivially have h*
h" & V&. then by (30) of Lemma 16, we have e (tt((h) e >
that if V& + 0, then together with (26) of Lemma 15, we have
min er. (h) ér (hx) 2 heV,
min erl. (h) NEV--1
ert (hx)
2 inf hEV-1
erp(h) erp(ha) 40"
Ek
> (h²) crr (fx
8
Ek
36
8
Ek
Ek
104
40'
4C"
10
4C
40
where the last inequality follows from érk," (hx) > f so that either way the algorithm will return in Step 4 in this case. Therefore, if the algorithm does not return in Step 4 on round k, must be that h E V/. This completes the proof of the first claim, by the principle of induction.
&
2xx
S 20. Thus, either V2, = 0 or minnev, (r)
10
10
Finally, we turn to the second claim. Suppose, for some k K, the algorithm returns in Step 4 on round k. In particular, either k = 1, in which case ht E C = Vi-1, or k > 1, in which case (since the algorithm did not return in Step 4 on round k - 1) the first claim in the lemma implies h- Va-1- Again note that this also implies h² E V k-1- If h" & Vz, then (30) of
Lemma 16 implies erp(h" > erp (fx) + . Otherwise, if h- E Vk, the condition in Step implies et (h²) (hx) > 10. Together with (26) of Lemma 15, this implies
ehr(ht) (hx((1)) 2
2r
Ek > 0. 4C"
Thus, in either case, we have e (h+) eTp (hx). which establishes the second claim.
Lemmas 15, 16, and 17 together have partieularly nice implication, which, although not strictly needed for the proof of Theorem 5, is worth noting (and will be useful in Appendix F). Specifically, we have the following corollary.
Corollary 18. On the event Eo n Ei EL E2, E.
V& c {
{ h he ( - exp((()) -
35k 20"
Proof. Suppose the event Eg n Ej n Eg occurs and consider any k E K. Since h: 1 K, Lemma 17 implies ht E V in the case k 2 2, while the case k: = has h V. by definition of
Vo = C. Together with (27) of Lemma 15, this implies crp (fx) S crp (h*) + 10 Combined with (29) of Lemma 16, we have that every h E Va satisfies e (h) & err (h.) + Seg
se
ac S err(h*) + 20"
35c
At this point, we may note that Lemmas 15 and 17 together completely address the error guarantee for the h returned by A on the event Eg n Ej n Eg. as summarized in the following lemma.
Lemma 19. On the event Eo n E1 Ez. Asvid eventually terminates, and the function h returns satisfies e (h) < infnec e (h) t..
Proof. Suppose the event Eo n Ei n Ez occurs. If the algorithm terminates in Step 4 in some round & E K. by definition cry((h) cry(h*) < infrec cry()) + 164- On the other hand, if the algorithm does not return in Step 4 on any round E IC, implies the algorithm eventually terminates), so that by definition h = hy Since in this case Lemma 17 implies h" E VN (and hence ht E ViA), (27) of Lemma 15 implies et p = (hx..) I (hr(h")
have h he and thus Lemma 17 implies
we have K = N + 1 (recalling Lemma 10
+ Ex < infree (h) + + "C" < inf er p + E. 10
With the analysis of error guarantees complete, we turn now to establishing the bound Q(e, 8; (8) on the number of queries, as claimed in Theorem 5. This will be comprised of two main parts. First,
45

---

argue that the set A., never grows too large: specifically, recalling := inffec (h) Lemma 20 (()). which in turn allows us to bound the number of queries in S n ni, on each round (in the proof of Lemma 23). Second, in the proof of Lemma 22, we bound (D \ A S sex, by reasoning in terms of the disagreement coefficient (Hanneke, 2007b), relating the latter to the star number via result of Hanneke and Yang (2015). This in turn allows us to bound the number of queries in S n Dz-1 \ Aig on each round (in the proof of Lemma 23).
:=
will establish that Px Px(A.,)
We begin with the first of these parts, stated in the following lemma. We remark that this lemma plays a special role in constraining the allowed values of the constant C, as the argument breaks down if C is taken too large. On the other hand, the proof also reveals that it is possible to decrease the factor "5" in this lemma to any value >>> 2 by taking C appropriately close to 1 and by an appropriately large choice of the constant C" (and hence C'). See footnote 11 for further discussion.
Lemma 20. On the event Eu n E1 2 Ez, for all k E (1....,K) K} and i Ix.
(x S 5 inf (hE n A.) S 58.
LEC
Proof. We will argue that, on Es n Ei n E2, for any ho E C, each region A \ A (defined in Step 7) satisfies
1 1- C 50
1 Px \ A.) = PP \A,), (31)
P(ER(ho) O n \A,) >
2
4C"
so that each addition to A ''hops off" piece of ER(ho) of measure proportional to the increase in
measure Px ( (A.)) =
Px ' \.)) The claim in the lemma then follows immediately
from (31), since holds trivially for = 0 (recalling Ag 0), and if any k E {I,...,K K} and E Ia
has i 2 1, then applying (31) inductively yields
P(ER(ho) ( nA.)
P(ER(ho) NASHI \A)) Σ 1=0
Σ
1 Px \4,) (
1
Taking the infimum over all ho E C then implies the lemma.
We proceed now with the formal proof of (31). Suppose the event Eg n F1 n E2 occurs, and for the purpose of analyzing the increases A++1 \ A, of the A, set (which only occur in Step 7), consider any k E IC and any E Is with i < max Zy (equivalently, the algorithm reaches Step 7 with this (k, Let (f,g) be as defined in Step 6 for this (k: i) so that Di+1 \ A = {s + g) \ A.
Note that {f+ g} x (0. (ER(F) 'max' by 'average')
(ER(( n {f + g}). so that (lower-bounding
max P'El/9)
A.))
(A)) P(ER(()) + 9) A..)) ( 2
1
2 # g) \ AAr))
2
where in fact the last inequality holds with equality (since, for {0, 1} labels, (ER(/) n (ʃ fg}) and (FR(g) n [ # 9}) are disjoint). Thus, 3ʃ E (1.9] with
1 P(ER(F) # 9) A. 2 Px(lf
Let W/ f'1 (s=mM\A,, + ho + f' and note that /' E Vi-1- Also recall that erk (fx) seve (h), and hence et 2 er (hx) Since we also have I' E V (as discussed in the proof of Lemma 16), Lemma 15 implies
crp(f') - crp( S o
(2 + 40"
CK S (M)
Ck
S
dek
(32)
4C"
40
where the last inequality is due to f E (f.g} S Vv, recalling the definition of V₁ in Step 3. Moreover, by definition of f' and h', we have
exp erp(h') P(ER(F') (f # o) \ A.)) P(ER(ho) n If # g) \ A
N 2
Px # g) \ A.) ) - P(ER(ho) n (f # g) \ A..)
#g)
46

---

Next we turn to the second part of the argument outlined above: bounding the number of queries in the sets St O Dz-1 \ A.. We begin by stating known fact, due to Hanneke and Yang (2015, Theorem 10): namely, that the disagreement coefficient (Hanneke, 2007b) is upper bounded by the Equivalently: P(ER(ho) n {f + g) A.d)
> Px(Ff * * A..) - (frp(f") - -
Combining this with (32), we conclude that
P(ER(ho) n (J > +)
1
5EA
(33)
40"
Also note that, since A; 2 Aig, we have
A++1 A = { H = ( A.))
so that
(hER(ho) n A++1 \ A+) 2 P(ER(ho) (..) ((0/)))nAAAA
(34)
Moreover, again since A 2 Aig. we have
Px((f + g) n 4, \A.)) = Px( - #g) 1 \A.)
(35)
Combining (34), (35), and (33) yields that
P(ER(ha) A++1 \ 2 (hoR(ho) n (f # g} A Px(U # 9) A + Px # \4,)
2 Px(If A.) 1 Px(( An)
5ER
(36)
40"
Lemma 12 and the fact that f.g E V& V- imply Px(1f + g) \. Aid) S Ek. and Lemma 11
implies Pxf + 9) A,) Ek43. Together, we have
Px ( <
+ g) A.))
Additionally, again since Px( g) \ > Ek+3, we have that See 5C Px(1f gg) A.).
TC 30
Combining these inequalities with (36), and recalling Ait1 \A; = ( + g) Ai yields that
(1- C3
5C3
P(ER(ho) n A \A,)
Px Px \ A.).
40"
Recalling that C" SC" equals Px(4 \ Ai), which establishes (31).
16 16- 1003, we have C
2
5C so that the right hand side above
2
307
5.
star number (Hanneke and Yang, 2015) (indeed, Theorem 10 of Hanneke and Yang, 2015 shows the relation is even sharp in the worst case over and distributions P²).
Lemma 21 (Hanneke and Yang, 2015). For any measurable h : X - {0, 1}, any distribution P3 on X, and any r > 0, defining the r-ball centered at h as B Bpp (h' E EC: P (N' + h) < r), holds that
P (DIS (BSp Byg (h1, r))) < sr.
Toward bounding the number of queries in the sets S n D \ A,, in the algorithm, the following lemma establishes a bound on Px (Da-1 Ai.) by straightforward application of Lemma 21 to the conditional probabilities Px (Dx=111 \ Ai.) in combination with a diameter bound supplied by (19) of Lemma 12.
Lemma 22. On the event E, 0 E1 Ez, for every & E (1, (1....,K) K), Px \ A.) S SE
Proof. Suppose the event Es n E; n E2 holds and consider any k E (1...., KJ. If Px we trivially have that Px (D A..)
0, < SEk- To address the remaining case, suppose Px Px(X') \ Ai,) O, and denote by Pk := Px ( ). By (19) of Lemma 12 we have
Pa(J # S Px A.,) f-gEV--1
sup
Sk
47

---

In particular, since k 1--44 < K, Lemma 17 implies h" E Vy-1 in the case 2 2, while the case k has ht Vo by definition of Vo C. Thus, the above inequality implies
EK V CCCAA hi, Px(x Air)
(37)
Together with Lemma 21, this implies
Ek P2(Dx-1) = Pa - Ps DIS Br hi; Px(x { An))))
Ek Px(x \
(38)
We therefore have that
Px Aix) = Px(DD And SEA.
We are ready state a lemma bounding the total number of queries in the algorithm, by combination Lemmas 13, 20, and 22 together with multiplicative Chernoff bound argument. For convenience, this lemma also supplies an upper bound on the sizes m' of the data sets Sg. which will be of further use when establishing the bound M (E, 6; 3) on the total number of unlabeled examples sufficient for the execution of the algorithm (Lemma 24 below). Specifically, in the following lemma,
for any 1 E (1....,N 1), denote by
m4 = 25C"
4(3 N 10++N-K). k:)² ~))))
))
d log
8
and M2 7000 CB
4ed
d d
5
g2
Lemma 23. There is an event Es of probability at least (1...., K}. the following claims hold: m²k S T74y.
such that on Ni= Ej. Vk
|S D Da-1 1 Air 3.
(39)
5 n
S 2Px (Axx I 10,mL..
(40)
Moreover, we have N1 m S M2, and the total number of queries by Auwid is at most ( 8; (8). where
Q(E, 8: = 10,M2 + min Mi, (3/2)sE(N + 1)m
= =0(2 32 E²
d + log 1
E d 1 + log ( 1)) (41)
+ min s log
Proof. By Lemma 13, on Eg n E₁ Ez, Vk [I,................ ...., K}. Px Px Px S (Px( Recall Thus, if A.. = 0. we have Po: hence m/ 0, and the implication m'k I mH trivially follows. Otherwise, on Es n E1 n E2, if Aig * 0, the final claim in Lemma 11 implies Px (Ai.) Ek+2, so that together mí is at most
the definition of m'g [ c of
(d+ log 4(3+
C" (A
(a+ log A(3+N-1)2
(
))
50" (C"cGPx(A.)) (d+ log
[433+N 8
2x
Since Lemma 20 implies (x < 53 on Eo n Eg n E2, we conclude that m' S m
We next turn to establishing (39). Consider any k {l...., N + 1} having non-zero probability that k < K. Given that A < K, note that V and A,, have no dependence on St. so that the samples in St. are conditionally i.i.d.-P given the event that & < K and given the random variables V4-1 and Aiç- Therefore, applying multiplicative Chernoff bound (Lemma 6 Appendix D) under the conditional distribution given the event & < K and the random variables VE-1 and Ai, with conditional probability at least 1
sk(k+1j'
St n Dx-1 Ane & 2m Px \ A.) +6 16k(k + 1)
(42)
8
48

---

In particular, by the law of total probability, this implies that for every &o E {l..... N + 1), with probability at least 1- - 8k(k+1]) if l S K then (42) holds. Letting E' denote the event that (42) holds for every k E (1,..., KJ, by the union bound, Fg holds with probability at least (42) with Lemma 22, we have that on the event Eo n E1 n E2 n Big, vk E {L,...,K)
Combining
16k(k 1)
$ DE-1 \ A.e S 24cgm, + 61n
S 3
8
where the rightmost inequality follows from recalling my := 30000 oo (d c" + log (o)(
which satisfies Eymi 2 6 (6k((et))) Thus, we have established (39).
N + 1} having non-zero We argue the left incquality in (40) similarly. Consider any l E (L....,
probability of k S K. Given k S K, note that Ai, has no dependence on St or m so that the m/, samples in S are conditionally i.i.d.-P given the event k z K and given the random variables Ai, and m'g- Therefore, applying multiplicative Chernoff bound (Lemma of Appendix D) under the conditional distribution given the event A: < K and the random variables Di and m/g, with conditional probability at least B33-NRRJ2
1 n A S max 2Px mm 6ln 16(3 + + K)² =
(43)
5
By the law of total probability, we have that for every ht E (1,..... N + 1}, with probability at least
1 8(3+ N --k=-- kj2s if l < K then (43) holds. Letting Eg denote the event that (43) holds for every
E [1...... K}. by the union bound, EY holds with probability at least - -03 2 1 4
Let Eg E'g n Eyj, and note that, by the union bound, E's holds with probability at least 6 For the remainder of the proof, let us suppose the event No=o Ey occurs.
To arrive at the simpler claimed inequalities in (40), we follow a similar argument to the final part of the proof of Lemma 14. Explicitly, we first note that for any k {I,..., KK. if A,, = 0. we trivially have |S n A., = = 22x )mk S 10,37 On the other hand, if Ai, * the final claim in Lemma 11 implies Px (A() > Ek+2, and combined with Lemma 13 this further implies Pk 2 ( > Ek+2. Therefore. in this case,
20"cG C
(d+ d
4(3 N N -1)² 2 6ln 16(3 + k)²
))
2
8
where the rightmost inequality follows from Ci 2 and C" 2 6C Thus, the left inequality in (40) follows from (43). The right inequality in (40) follows immediately from the fact (established above) that m4. < m together with the fact (from Lemma 20) that Px (Ai,) < 5,3.
The remaining claims in the lemma follow from reasoning about convergence of the relevant series. Specifically, recalling that 6 = Cl-k,
(2))(2)] and C
11
To we note that Σx
CP-I (C2(N+1) 1) < and
N+1
N
49 -²
Σ
In(3 N =2N C
C2N
2j In(2 + () CNN .10
1=0
Recalling m
230" o
(d+ 23 3+ N k)) + in( we have
N+1
250
GB
(
4
m
28d + 2- 49 In
S M2.
(44)
82
1=1
To obtain the query bound Q(s, 8; B) in (41). note that the total number of queries is precisely
Σ s n A..))
Σ stt n D 14.1))
(45)
49

---

By (40), the first term in (45) is upper bounded by 1033 ΣX=1 my and (44) implies this is at
most 10 The second term in (45) is trivially upper bounded by M1 := Ei=i my. Moreover, noting that Eymy is increasing in k. (39) implies the second term in (45) is also upper bounded by 35Ex.1 my+1 (N + 1) I (3/2)se(N + 1)mx.r- Together with the definition of Q(e, 8; (3) from (41), we have that the total number of queries (45) is at most Q(e, d; 3).
The bound on the asymptotic form of Q(e, 6; (3) in (41) follows immediately from the definitions. Specifically, by definition of M2, we have 103M2 = O 82 (d + log (1))) Moreover, since
Ev+ 2 20. we have (3/2)se(N (N + 1)m = (s log (t) (d log + log )) while (since each k I N has 2 20), M1 = Ex=1 m. I Dk=1 Ek
301C en (d lo 2CC + log(
( (dlog()) + log( ())) by evaluating the geometric series.
As final step before composing these lemmas into proof of Theorem 5, we state an explicit bound on the number of unlabeled examples used by the algorithm. Much of this analysis is already implied by the above lemmas: namely, by definition, the number of examples allocated to data sets St and sg
is precisely 2M1 = 2 N1
k= my, and Lemma 23 implies the number of examples allocated to data sets S% is at most M2- What remains is to bound the number of examples allocated to the data sets Sk.. which hinges on bounding the number of iterations of the 'While' loop for each k. We have already noted, in Lemma 10, that max I V
on the event Eg. which already suffices to establish Ex++
coarse bound Ō ((²). However, we will need a slight refinement to obtain the claimed upper bound, which will follow from a combination of Lemmas 11 and 20.
Lemma 24. On the event No-o Eg, the total number of examples allocated to data sets St. Sk (k S N + 1), St (k= I K), and S2. (k E KC, i E Ix) is at most
((E,8;3) 3M, + M2 100043m, =0 B + E²
- log
1 { 1))
ddlog
Proof. Suppose the event 1== E, occurs. By definition, the number of examples allocated to data sets St and St. is my each, for k E NN + 1}. so that the total number of such examples is Exs1 2m, = 2M,. Also, by the first claim in Lemma 23, the number m' of examples allocated to each 52 data set (for k E (1,...,
(i....,K), K}) satisfies m S m/.- Moreover, Lemma 23 also establishes that Ek= m4 S M2. Together, we have that the total number of examples allocated to data sets S2 is Ek=1 m S M2. Thus, complete the proof of Lemma 24, it suffices to bound the total number of examples allocated to data sets S (k E K, i E Zx).
Toward this end, recall that for each & E K., each Sh is of size my, and is allocated if and when the algorithm reaches Step 5 with values (k: i). Thus, if k: K (which, by the final claim in Lemma 10, occurs only if the algorithm returns in Step 4 in round k), then no examples are allocated to any SE sets in round k, whereas if l < K, then the number of St data sets allocated during round k is precisely the number of distinct values of i encountered in round k: that is, [Zx]. Moreover, note that since each time through the 'While' loop increments i, each k E K. with k < K has It follows that the total number of examples allocated to data sets Sd in the algorithm is precisely ΣEEKA mm(1x-1 is 1).
[Zx] i - i
Next we upper bound i++1 is for each lo E K. with < K. Specifically, for any such k note that Aisus \ Ai, - (Ai+1 A.), and by definition the sets Ai+1 A; are disjoint over i. Moreover, by Lemma 11 and the definition of Art1 in Step 7, any E (ix,..., fe41 - 1) has (x A.) > Ex+3- Therefore,
1
Px -
Σ imii
Px \ A.) 2 (ix+1 - i
On the other hand, by Lemma 20, Px (Dinm inequalities, conclude that (ix-1 it) ex
A,, S Px S 53. Combining these sC'8
Combined with the facts that my S my and
50

---

EKEKIcKK my S M1, altogether we have
N
5 Sk
100C* 3mxx
Σ KEKKAKK
mu(is+1- - +x S M1 + m
S M1
+
6
where the last inequality follows by evaluating the geometric series and recalling By 2 20. This completes the proof that the total number of examples allocated to data sets Sg. S Sg. St is at most (s, 5) The claimed asymptotic form of M(e, 8; () follows immediately from the definitions of the quantities involved: namely, by definition, 3M1 = O(2 (dlog + +l)(())))
M2 @ & 2² (d log()))) and (since ex 2 2C
1000 3my = e 8 ( + log log( ()))
We are now ready to combine the above lemmas into a complete proof of Theorem 5.
Proof of Theorem 5. By the union bound, the event N F. has probability at least 1 - 5. By Lemma 24, on nz= F.y. Aavid uses at most M Ms,, 6; (3) (as defined in the lemma) of the examples in the sequence; particular, this means that if we were to run the algorithm with a finite sequence Yi). (Xm: Ym.), for any m 2 (e,,5;3) then on the event No=o Ej. the behavior of the algorithm (e.g.. queries, returned h) is identical the idealized setting the above lemmas were established under (where there is an unlimited supply of examples), and hence the claims in the above lemmas remain valid. Thus, for any sample size m 2 (s, 5; 9), on the event No= E3,, by Lemma 19 we have (f) S inf (r)(h) + e. and by Lemma 23 the total number of queries is at most (e, 6; (3) defined therein.
A remark on intersecting with D in Ai, We remark that Theorem 5 remains valid if we restrict either (or both) h1, h2 to be in V4-1 in the definition (2) of V The entire proof remains valid (applying the same change to vg- 1), with the only exception being the first inequality in Lemma 20, which should then replace C by Vi-1. This change is of no consequence to the second inequality in the lemma since the proof of Lemma 17 in fact implies that h E V--1 holds simultancously (on Eo n E1 n Eg) for all functions h* E C satisfying (10) (and hence infneve_, p = 9). Moreover, with this restriction to require h2 E Vx-1 in V we can extend the intersection with DR-1 to the Ai, region: that is, instead of querying all of S n Ai, (in Step 2) or s2 7 Aix. (in Step 9), we can instead merely query the subset SR n D n Aiz (in Step 2) or Se.. O Dy n Airet (in Step 9). With this change, we must then also modify the definition of (r)) in (1) to (h) == Pst (ER(h) n Dx-1 \ A + Psg (ER(M) n D O (2)) The argument in Lemma 15 extends to this modified definition of (h),, since (as in the proof of (14) in Lemma 10) we are only interested in error differences, which, for h, h' E VR-1, satisfy Psq (BR())) - Psg ( (ER("")DD=:AA.... = Ps (ER(H)nA,, - - (ER()))),, the proof, we can then even slightly refine the query complexity analysis, since we replace the sets ER(h) n Ai with ER(h) n Da-1 n A,, in Lemma 14, the envelope set in the application of Lemma 8 in the proof of Lemma 14 can be chosen as DR-1 A . so that we can refine the definition of pa to 2P (Da- n A., ) +(x)). However, since
Indeed, with additional modifications
these changes concern only the leading term & (d+ + log( in Theorem which is already optimal (perfectly matching the lower bounds of Kääriäinen, 2006; Beygelzimer, Dasgupta, and Langford, 2009), they are completely inconsequential to the theorem. We have therefore stated the algorithm without these modifications, for simplicity. However, this modified variant would be interesting in the context of P-dependent analysis, where it can lead to refinements to the leading term the upper bound under certain favorable distributions. We leave the investigation of such refinements as an interesting direction for future work (focusing our P-dependent analysis in Appendix on refining the lower-order term).
51

---

F Distribution--eeendeett Analysis
In addition to analysis based on the star number (Hanneke and Yang. 2015), the active learning literature includes variety of distribution-dependee complexity measures which have been used to analyze the query complexity in various contexts (see Appendix A). In this section, we will add to this line of work distributionn-deeendent analysis of Aavid which replaces the star number s in Theorem 3 by a (never-larger
iestrbbttionddeeedeen quantity (Theorem 27), which can be further upper-bounded in terms of simpler and more-familiar quantity: namely, quadratic 6² dependence in the disagreement coefficient (Hanneke, 2007b; Definition 25 below). We also show (in Appendix F.1) that it is not possible (by any algorithm) to obtain a lower-order term which replaces the star number in Theorem 3 with the disagreement coefficient 0 itself, so that the aforementioned 8 quadratic dependence generally cannot be reduced linear (without introducing other factors). We will also present (in Appendix F.3) a slight refinement of Agvid= which replaces the region of disagreement D by a carefully-chosen subregion, following the technique of Zhang and Chaudhuri (2014); Balcan, Broder, and Zhang (2007), which yields corresponding refinement of the distributionndependeen query complexity bound. For instance, in the case of learning homogencous linear classifiers under uniform (or isotropic log-concave distribution, this recovers known query complexity bound Ô ((d gd works).
5e + d) (and indeed, improves log factors in the lead term compared to prior
The Disagreement Coefficient: In the context of agnostic active learning, the most commonly-used P-dependent complexity measure is the disagreement coefficient, introduced by Hanneke (2007b), defined as follows.
Definition 25. For any concept class C and distribution Px on X, for any measurable function f:X + {0, 11. for any s 2 0, the disagreement coefficient, denoted by ( is defined as
Px (D(S(((p VI,
01),(()) == sup r2E
r
where Bp (f.r) = = (he Px f) Sr) r} denotes the r-ball centered at f. and DIS(C') := {o E x:: 3h, N1' E C', h(x) & [xx)) denotes the region of disagreement (as in Section 4). For any distribution onn& X x (0. 1] and e > 0. for h² as in (10), define (p(c) := 0r (E).
There are many works establishing bounds on the disagreement coefficient for commonly-studiss classes C under various restrictions on the distribution P (see Hanneke, 2014, for detailed summary). As discussed in Appendix A, the disagreement coefficient commonly appears in analyses of the query complexity of disagreement-basee active learning methods (e-g.. Hanneke, 2007b, 2009b, 201 1, 2014; Dasgupta, Hsu, and Monteleoni, 2007). Since the lower-order term in Theorem 3 arises from the analysis of queries in the region of disagreement DIS(V,, of V one might naturally wonder whether we can replace with (p(s) in the upper bound in Theorem 3. Hanneke and Yang (2015) have shown that supp (s))) = s A for S E (0, 1]. which implies that we could replace by 0p(s) it would indeed represent a distributionnddpendenn refinement of the upper bound in Theorem 3. However, it turns out this is not possible (by any algorithm) for some classes C, as we demonstrate by example in Appendix F.I. Following this, in Appendix F.2, find that it is possible to achieve a lower-order term Odd (B + e)²), and indeed this is achieved by Aavid- This quadratic dependence unfortunately means the upper bound is sometimes loose (i.c., sometimes larger than that in Theorem 3). However, an intermediate step, also establish a query complexity bound (Theorem 27) expressed in terms of a modified disagreement coefficient which is never larger than the s e-dependent query complexity bound in Theorem 3 (though which is more difficult to evaluate due to a more-involved definition).
Whhhen h² is not uniquely defined, in principle we can define 0r(e) the infimam value among all choices of such h²" It is also possible to define h² as an e-independent fixed function, even when ( does not have a minimizer in C. by choosing it as an element of the L1 (P& -llosure of C having er (h*) = infaec er see (Hanneke, 2012) for a proof that such an h* always exists when VC(C) < co. In particular, with such an h", the limiting value 0r (r) 6F, A (0) is also dell-defined.
52

---

F1 Impossibility of Replacing with (p(s)
In this section, we present an example demonstrating that no algorithm can achieve a P-dependent query complexity bound which replaces by (p(=) in Theorem 3.
An Example: Consider the following concept class (see Hanneke, 2007b, for a related construction). Let X' = 2 (the integers) and define a concept class
Cs := (- :t e N}.
In other words, each à E Cts defines a threshold classifier on the positive integers and a singleton classifier on the negative integers, and the position -t of the singleton point mirrors the position of the threshold boundary point.
Fix any E 3 E (0, 1/3), denote by n 1-20 and for simplicity suppose n E N. Define marginal 2r
distribution Px on X' as follows: Vr E (1.....,) Px((x)) 2B and Px((-2) 2s. Note that this completely specifies Px. Now define a family of probability distributions Pi,...: Pn: for each
t E [., P; has marginal distribution Px on X' and conditional distribution Vo E X
1, r
P.(Y = 1|X = x)
0, (n)
1
otherwise
In particular, note that each Pt satisfies inf erp, (h) 3 and h* is uniquely equal 1 ((r)))t,.c) 15
Upper-bounding Op, (e): For any Pt, we will argue 0p (e) S 0p, nr (0) =O()). For any r > E Bp, (h, r), then letting kn == 1[h * h²) (1,...,,) n.]l. since each x E {1...., nn has Px((z)) = 28 we must have kn - k, = 23 m
(h",r),
Since and h- both implement threshold functions in this region {l...., n). the kn elements in (h * h3 n {l...., n) are a contiguous segment: either (t.....ts t
n
kn 1) or ft . 1}. In either case, we have (h + h² n (1.....n] S {t ky...., + k,
1 [(-r) (u .0) for some t' E N, this further implies {h & ( ..,,..., -n C {-(1- ky),.... ..)..... - (1+ k,)) ( (-1,..., -n.. Since DIS(BR (h",r) is just the union of these {h # h²) regions among all h E Bp, (h r). we have
(I........n) n... Moreover, since
DIS(BR, (h*,r) (-n,.... -1, 1.1,...,,n) n}
S (1-(1 ky), ...., -1 (1+ k.) (-1, ,..., n() kr....,
1+ ki 1) n (1 (I....; n))
Px (h' (r)) (2k, 1)2s 2k, 28
r(1
233)
+ 2 2r.
8
We also note that any < 28 has BB (h, ,r) = [/(".. Altogether,
r((1 1 //3)3) + 2$ + 2r
1 2/3
1 3
(p) Pp. (0) < sup
3 0
r22s
Lower-hounding the query complexity: On the other hand, we will argue that the query complex-
ity is ( under the assumption P E (P..... }. Note that every h X' + {0, 1] has the same
value of (ER((h) (-1,--. -n)) B. Together with the definition of P; in {-1 1,, 11...... -n), this implics any h X + 1} with {h * [--,..- -n} * @ has er (h) erp, (h*) ) > 2z. Thus, the problem of learning, an excess error (under the assumption that P {Pt :t (I.....n]] n))) is equivalent to the problem of identifying the value t E {1...., n. for which the distribution P = Pt: that is, if an algorithm returns h with erp, (h) erp, (h*) S e, the unique E .1. for which f((=x) 1 satisfies x = Moreover, in the active learning problem defined by these distribu- tions, for every x & {-,,..., -n). J. the conditional distribution P.(Y = 1|X x) of responses to queries for examples at invariant so that such queries reveal no information about which
15 Indeed, these distributions Pt even satisfy the stronger benign noise property: i.e., infacC., er (h) Bayes risk (a setting studied by Hanneke, 2009;; Hanneke and Yang. 2015). Thus. the argument in this section further implies the impossibility of using (r(s) in the lower-order term under benign noise.
53

---

t has P = Pt, and hence without loss of generality we can restrict to active learning algorithms that do not query outside : The unlabeled examples also reveal no such information. since all Pt have the same marginal distribution Px. Altogether, the active learning problem for this set of distributions the problem of actively identifying singleton classifier on {-1,...
no easier (in terms of query complexity) than
-n] in the realizable case under marginal Uniform((-1.. (I..,...,.-- -n}). It is well known that the minimax query complexity of this latter problem (with confidence parameter å 1/3) is Q(() ( (Dasgupta, 2004, 2005; Hanneke, 2014; Hanneke and Yang, 2015), which therefore serves as a lower bound on the minimax query complexity for P (Pr: :t {1. {I...., n that is, for every active learning algorithm, there exists P E (P& t E {1....nn] n}} for which, with probability at least ó, it either makes ( queries
or returns h with erp (h) > infnec. (h) + e.
Conclusion that p (E) is not achievable in the lower-order term: From the above arguments, we can conclude that for the class Cts. it is not possible to replace s by 0r(e) (or indeed (0) in the upper bound of Theorem 3 to obtain a P-dependent refinement of the upper bound. Formally, for every active learning algorithm guaranteeing that, for every P with infaec., erp(h) S 8, with probability at least 2/3 (i.e., 1/3), it returns h with (f) S inf. e + e, there exists a distribution P satisfying this for which pp(s) S 1-28 +3 = 0 (²)). yet with probability at least 1/3, the algorithm makes number of queries ()())- We have argued this conclusion for any choices of E. 3 1/3) (with n E N for simplicity). In particular, for E < B < VE (e.g. = c²/3), such distribution P has 2 ς + 0p(s) _ O()) << 1. so that replacing s with (p(s) in Theorem 3 cannot yield valid query complexity bound (holding for all P) for any active learning algorithm. Indeed, we have established that this conclusion also holds for (0) (as defined in footnote 14).
We will see Corollary 28 of Appendix F:2 that Aavid does achieve an upper-bound Ö(d + +))? on the lower-order term: quadratic dependence on the disagreement coefficient. This conclusion is compatible with the above scenario, since g² 2² + B =
=2( for the full range of B,E.
F.2 Replacing s with ( + +e)
Appendix F.1 implies the disagreement coefficient (p(E), as defined in Definition 25, cannot be used as a P-dependent substitute for the star number s in Theorem 3 (at least, not with a linear dependence). In this section, we will argue that the AVID Agnostic algorithm Aavid does achieve a P-dependent lower-order term which is at most quadratic in the disagreement coefficient: namely, ( + =)²). We will argue this by first establishing a P-dependent refinement of Theorem based on a modified disagreement coefficient (Definition 26) which is never larger than the star number. While this quantity itself is often more-difficult to calculate, compared to the original
disagreement coefficient (r()), fortunately it is always upper bounded by O 8² 0r (B + e)²) In particular, this means that for any P with (0) co, the asymptotic dependence on e, 5 in the lower-order term in Theorem 3 can be reduced to polylog( (
Specifically, the modified disagreement coefficient we consider can be expressed the value M (E) produced under a restriction of Px to a subregion X' \ A of size at least 1 - 0(3). Toward stating the definition, we first extend Definition 25 allow for general measures pr: that is, for any measure on X' and measurable ʃ X' + {0, }}. define (,, = (h E C: j(h # $ S r).
Forraaly, for any active learning algorithm A. under distributions P E {P. te fl,..., m)), we can convert & into an active learner A' for realizable-case singletons under Uniform({- (1,........ l..... ..). with at most the query complexity of A under such distributions P. Specifically, given any number m of i.idd
unlabeled examples XI....,X Xm, ~ Uniform(( ( 1,..... .a........ -n)), define independent random variables (also independent of Xa...., Xmm) Br..... Bm ~ Bernoulli(2)). Xi...., .,, X nn ~ Uniform([1,... Yf...., Y%, Bernoulli()) ). For each i S m. let X"" X. B, = 0 and X X: Bf .(, n)), and Then A runs A with unlabeled data X" ... XM; whenever A queries an X²" with B, 0, A' queries for the label Y; of X; and gives this as response the query, and whenever à queries X with B, 1, A' gives Y response to query. Note that the corresponding data sequence and responses observed by A are indeed identical to running & under 1 = Pt. where -t is the singleton location for the realizable- case singleton problem P.(-[(-I,.... -n))) Thus, the query complexity of A' identifying the for the realizable-cae case singletons distribution (-(--(1,.... -n)) is most that of & identifying this when / = P..
54

---

and for 2 O define (p.r(e) sup a region-excluded disagreement coefficient
((DIs V1. We then consider the following definition:
Definition 26. For any distribution P X' {0, } and any measurable A X, define a measure + Pa(A) = (x A). For any E, T 2 0, for ht* E EC as in (10) (under P), define
0p(E:T)= = sup (r (C)
We can equivalently define Tp( as the disagreement coefficient under worst-case conditional distribution (+ \ A): that is,
sup 0p(E:T) ACH)PH(A)ET
8 (E/xx \A)),
(46)
where we define (-IM))))) (e/Px(X) A)) = the case (x A) = 0 (which coincides with the value P (5) for such A)
We may note that (); indeed provides a refinement of the star number, in that it never larger. Specifically, since Hanneke and Yang (2015) have shown
1 E
sup 0 (s) Px AEC
(47)
for every (0, 1], the expression in (46) of (r(=;)) the disagreement coefficient under condi- tional distributions immediately implies
0p(s:T) < S 1
(48)
Thus, replacing in Theorem 3 by Op(E:T) would indeed yield a (never-larger) P-dependent refinement.
We give examples below (Appendix F.2.1) of calculating and upper-bounding 0r(e; 7) under various scenarios (C, P). We remark that, due the supremum over regions A, the quantity (r 7) is often much more involved to calculate or bound compared to the original disagreement coefficient (r(c) in Definition 25. We might therefore think of (p(E:T) as kind of intermediate complexity measure, which is useful in that it provides a P-dependent refinement of s, while also admitting general upper bounds which weak relations between 0p(e;T] r) and the more-familiar disagreement coefficient from Definition 25: namely, pp(E) < 0p(E:T) T) and
more accessible than directly calculating 0p(e; T). Concretely, there least
Px PD ( +r)))
8p(c:T) sup r>s
V1
T T+E
T T
< <pp(T
S 0p(( + 00p(T++)) +))2+
(49)
These upper bounds on 0p(E;T) are noteworthy since 0p(r + 5) is typically significantly easier to calculate compared directly calculating Or(E;T) (and there already many works deriving bounds on 0p(T + E) for various scenarios; see Hanneke, 2014).
The quantity TP( is particularly well-suited for the analysis of Aavid since the algorithm explicitly maintains low diameter of Va, under a region-excluded measure A + (x \ A Specifically, Lemma 12 implies Vi-1 Br (h*, Ex), while Lemma 20 implies Px I 58,
so that Px \ A..) < Op(EE; 5,))x. and hence the number of queries in S n D 1 Ai, is Ó(Pp(E; 5,)d). Formally, this leads to the following result, which simply replaces s with (r:(E; 5,3) in the lower-order term compared to Theorem 5. Due to (48), the query complexity bound in this is never larger than that of Theorem 5 (and below discuss scenarios where it is strictly smaller). We remark that, based on the comment preceding Lemma 20, the factor "5" in (E; 5,3) in this theorem be reduced to any value 2 by appropriately adjusting the constants C. C" in the algorithm.
(33
17 The remarks concerning the choice of h* in footnote 14 also apply here, noting that the lemmas concerning h" in Appendix E actually apply simultaneously all functions ht C satisfying (10).
55

---

Theorem 27 Iestributiondepeendee Query Complexity of AVID Agnostic), For any concepr class C with VC(C)= < oc, letting
VC(C), for every distribution on X x {0, 1}, letting B 3= hnc ())) for e, E (0, 1), if the algorithm Aavid is executed with purameters (e. 8). with any number m 2 M(e 8; B) of i...d.P examples (for Míe,b, 8; as in Theorem defined in Lemmna 24), then with probability at least 1 - 6, the returned predictor h satisfies er ( S inlnet (() + and the algorithm makes a number of queries at most Q 8; P) satisfying
)))
+ +min @r(cc: 5,3) log ()) ()) }
()) E
+ log ( ))))
(e, 6; P) = 0
d + log
d d
E²
32
= Ö
d
+ d0p(E::8))
E²
Proof. The result follows identically to Theorem 5, with only one minor change: replacing 5 with (E; 5,3) in Lemma 22. Note that this one change will suffice, since every subsequent appearance of in the proof is due its appearance in Lemma 22, and hence changing s to pC0p(e; 5,3) in this lemma allows us to make the same change in every subsequent appearance of s in the proof.
To why Lemma 22 remains valid with this change, first note that its proof establishes that, on the event Eg n E n Eg. in the non-trivial case of Px(X', \ A..) ) * O, (38) holds. Rather than relaxing the third expression in (38) using the star number, we can instead relax it using (e; 5,):: that is, for Pk as defined in that context, (38) implies
Aie) ))) (A
(D (.d) Pa(D) A.. S PA DIS Br h², Px(X 'x
Paa, DIS B (h' (()t.e))) S 0p(ec
BrA
where the last inequality follows from Definition 26, the fact that Ek > 20
e and the fact (from
Lemma 20) that (A.) S 53. We then note that (as in Corollary 7.2 of Hanneke, 2014) for any X,
PA PAIISS(Br, (h', ((())) V1 20 sup r/(2C)
PA PA (h", ())r V1,
P (E/(2C)) = suup r3c
r>e
and therefore (r(e/(2() 5B) < 2B) Altogether, we have that Lemma 22 remains valid while replacing 5 with (E:53)
We emphasize that Aavid does not need to know the value 0p(e;5,)) (or anything else about P) to achieve this query complexity: that is, it is adaptive to the value of pp( 53)..
Together with (49), the above result further implies a (sometimes loose) relaxation, in which the lower-order term has a quadratic dependence on 0p( + =), formally stated in the following corollary (compare this with Appendix F.I, which showed it is impossible to generally reduce this ( 2)² term to a linear term (3 + E) or even (0)(
Corollary 28. The query complexity bound Q(E, 8; P) in Theorem 27 (achieved by Daviaa) satisfies
g2
σ ) + Ô min d0 dBp(8+t)
3 (++
=)
((e,o;)) =
d++log log
82
) + δ min d0 dBr(B+=)2 d ))
= 0
d+ log
Proof. Due to the first two inequalities in (49), and (p3 +e) < (p(3 + E), the second term in the expression of Q(e, 6; P) in Theorem 27 at most
of min 0r(3 + E) log 2
B +
log 1 + log 5 ))
(50)
Relaxing d log ()) + log(t)) S (log(
(d log (t) and noting that
0p(B+e)log + 2)0 (1) (
3 +
) < 0p( + E)2 log (1)
(
3 +
56

---

and
(+t))
2
I 4 + 4, the quantity (50) is at most
o g2
d + log ()) min (00(( log 1
1
log )
d log (
))
5²
Adding this the first term in the expression of Q(e, 8; P), the result follows.
In particular, Corollary 28 implies that, whenever (0) < the dependence on 3, in the query complexity bound in Theorem 27 is of order 22 + polylog(?) ( For instance, see (Hanneke, 2014, Chapter 7) for some general conditions on (C, P) under which this occurs. We remark that the first bound in Corollary 28 is at least never larger than the upper bound in Theorem I, since we always have (r (33 + +)
8²
O+t S = however, we note that this is not the case for the second upper bound in
Corollary 28, Beyond these basic observations, there exist scenarios (C, P) where both upper bounds in Corollary 28 are loose compared to Theorem 27, to such extent that they are sometimes even larger than the s-dependent bound in Theorem (see Example 6 below). It is for this reason that we have chosen to express Theorem 27 in terms of the more-complicated quantity py(E; r), provide starting point for P-dependent analysis that is at least never worse than Theorem 5.
E2.1 Examples
We next present some examples illustrating the values of the lower-order terms in Theorem 27 and Corollary 28 by bounding the quantities (): and (r + =)². Specifically, Example 1 achieves this via the relation to s, Example 2 provides simple scenario with directly bound (e) Example 3 expresses a bound on p (3 s) which is known in the literature, but when combined with Corollary 28 provides an improved P-dependent query complexity bound compared to previous works. Example 5 revisits the example from Appendix F. to illustrate that pp(e; 5,9) provides a valid lower-order term for this example. In Appendix F.4, we will present additional examples of P-dependent query complexity bounds, for some classes with VC(C)= = oc, via Px d'--dependent covering numbers.
where it is possible to
Example 1 (Thresholds). Due (48), any C with finite star number s admits bounded 0 0p(e; T). A simple example this is threshold classifiers: namely, X I and C = (1(e,0)) : E RR. This class has g 2 (Hanneke and Yang, 2015), and hence (r(E; T) S for any P.
Example 2 (Linear classifiers under 1-sparse distributions). To illustrate simple example where 0p(c:7) T) = (1) while s = oc, consider the class of linear classifiers in X' = R", p 2 2: that E R", b R). This class has = do (Hanneke and Yang, 2015).
is, C = {x + ((w,))++20 However, if we consider Px as distribution supported entirely on one axis (e.g., Uniform([0, 1] x (0)+-2)), then it is a simple exercise to show that (p(=T)) S 2: the concepts in Bp, (h*, .)) are those that disagree with h* on most measure (under Pa)) either to the left or right of where the h² separator intersects the axis, so that DIS(B (h",r) r)) is simply the union of these two (at most) r-measure regions, hence has PA measure at most 2r.
While the above examples merely recover known results, the following example derives a previously- unknown P-dependent query complexity bound, which significantly improves over the best previously-knowe bound for this scenario.
Example (Rectangles). Consider the case X' R.. 2 1, and C {1 b x ((,.))) : a1 S bi....,d Og S b: : the class of axis-aligned rectangles (Mitchell, 1979). This class is known have $ = co (Hanneke and Yang, 2015). Consider Px = Uniform( [0, 1)2²) (the example trivially extends to any product distribution Px with marginals on each axis having continuous CDFs) and any P with well-defined h* E argminge ( satisfying Px (x h² (x) 1}) =; X > O. The optimal first- order query complexity under these conditions is not yet precisely known. However, Wiener, Hanneke, and El- Yaniv (2015) have shown that (p(3 + o log(d) A stc) for this scenario, and based
on this, the best known query complexity upper bound is of the form Ò min d2 (8+c)² d -+
X e²
We can derive a bound which improves over this, as follows. We first recall that Theorem I provides a query complexity bound ò ( + e which already improves over the query complexity bound
57

---

of Wiener, Hanneke, and EI- Yaniv (2015) in all regimes with E < B < 1 (for every X). However, we can further refine the lower-order term by introducing dependence on X. Specifically, the first bound in Corollary 28 provides query complexity bound Ö (d (3+e)) which offers a refinement A
over Theorem whenever À > d3 + +). Moreover, the second bound in Corollary 28 provides query complexity bound Ö d ア X In particular, for À - (1)) and 3 O(VE), this yields query complexity bound poly (oly(d)pool polylog (1)), which was only available in the bound of Wiener, Hanneke, and Yamiv (2015) in the nore-restrictive regime 3 = Ö(E). We leave open the question of identifying the optimal query complexity for this scenario. In particular, one concrete technical question toward that end would be to determine whether, for À > 2T, 0p(E;T) = =()).
Example 4 (Linear Classifiers). Consider the commonly-studicc concept class of linear classifiers, defined as: X' = -d (d 2 3) and C = ( w E _ E RR. where (w = 1 1[ x) +b Z O). This is perhaps the most well-studied concept class in the active learning literature. Its VC dimension satisfies VC(C) = d ( (Vapnik and Chervonenkis, 1974), and while its star number satisfies 20 (Hanneke and Yang, 2015), the disagreement coefficient has been shown to be bounded or sublinear under various distributional conditions (Hanneke, 2007b, 2014; Balcan, Hanneke, and Vaughan, 2010; Friedman, 2009; Mahalanabis, 2011; Wiener, Hanneke, and EI- Vaniv, 2015). These results compose directly with Corollary 28 to yield previously complexity under these same conditions. For instance, if P'x is a mixture of a finite number t of multivariate Gaussian distributions with full-rank diagonal covariance matrices, then Wiener, Hanneke, and EI- Yaniv (2015) provide a bound (r) S Cd.: log (+)) for a (d, t)-deeendntt constant Ca,t- Plugging into Corollary 28 (or rather, the explicit bounds in the proof thereof) yields a novel query (t) (d + log( More generally, if Px admits density with respect the Lebesgue measure on Rd-1 then (taking h* as in footnote 14) Hanneke (2014) argues that 0p(r) = (+) (where the specific form of this function (p(r) varies depending on P). Recalling that (as E + 0) the lower-order term becomes relevant only in the regime 3 < Ve, combining this with Corollary 28 yields a query complexity bound which often provides refinements over Theorem 1. In particular, under sufficient regularity conditions on Px (see the proof of Hanneke, 2014) to ensure this ((-) function further satisfies
bounds on the query
complexity bound of order _ (d + log())) + ca,, (dg2(d-2) (3+
(r(r) log" (+) = o()), the resulting asymptotic dependence on (e. is of the form 3 of )) Moreover, if additionally the density of Px is bounded and has finite-diameter support, and if the hyperplane boundary corresponding to h* passes through continuity point of this density in its support, then Hanneke (2014) argues (r(r) = O(1, so that Corollary 28 yields a query complexity 8² bound with asymptotic dependence on (e, of the form further restrictions (density bounded away from O, compactness of the support), Friedman (2009); Mahalanabis (2011) argue 0p(r) is asymptotically bounded by O(d) (for the precise statement, see the original works, or discussion thereof by Hanneke, 2014).
2² + log' (2). Moreover, under the
Example 5 (Coupled thresholds and singletons). Let us revisit the example from Appendix F.I, for which we argued that (e) cannot itself be used to replace the star number in Theorem 3 (for any algorithm). We will here explain how the region-excluded disagreement coefficient 0p (p(e; explicitly corrects for the issue with (p) in this example. Specifically, consider again X' = Z, and C Cts == {1(- : tt E N]. the class of coupled thresholds and singlctons. Let e,3 E 1/3). let n = 1-28 (and assume n E N), and consider again the distributions 2r
defined in Appendix F.1: that is, all P. have marginal Px on X, where for E {I,...,n} ,n]. (xx))))
Pt, t [1....,n],
(x((==)) = 2s, and for E {-1, (-1,...,-n) P.(Y 1|X 2) = -1/x = -t). while every x & (-1,....-n) has P,(Y = 1|X = x) 2. Note that, for A = =00,00, we have (A = 23. Moreover, for h" as defined under P.. we have BPa Bha 4=) CCs (since only the disagreements on the singleton part are measured by PA). This implies DIS(Br, (h*, (e)44e) )=))=> = Z {0). so that PA (DIS((Br, (h* 4s)))
29
n
2,3. Therefore, 0p(=; 53)= 2 0p(::28) 2 PA(DIT(Bp, (h' 4E))) 1-22 Since we always have (,) < } we 46
46
conclude that 0p(e; 5,3) = (()). As argued in Appendix F.I, the minimax optimal query complexity (constraining to P E (P: ((1,.... ....,,)) m))) is (()), so that, unlike (s)s,, the quantity 0r(e; 5,3) is an appropriate replacement for s Theorem 3. Of course, Theorem 27 shows this replacement is always valid, so the point here is merely to illustrate how the exclusion of the A region in the definition of
58

---

(p( 5/8) is precisely the right type of correction, compared to (p(s), for this example, as it explicitly removes the issue underlying the failure of (r()): namely, the fact that the threshold portion of the concepts (-C"ull (o) is irrelevant to the learning problem inherent in the Pt distributions. It is
also worth noting that the first upper bound 0 (p;=; I 0p (5, +E)
from (49) also yields 5,8t
value (2) (since this upper bound is never larger than !). However, the second upper bound
0p +5)3++)²++ (.++)) can be significantly looser for this example, in most regimes of e, 3 (namely, 4 (vV)).
F.2.2 The Error Disagreement Coefficient
is also possible to derive Corollary 28 via another intermediate P-dependent variant of the disagreement coefficient: namely, the enror disagreement coefficient, defined as follows. Definition 29. For any probability distribution P on X x 10,1), for any E 2 0, define
Px Px(DIS(CP(r)) v1,
0% == sup r>c
where Cp(r) = {h E C: ( - inf erp S r is known the r-minimal set.
Similarly to 0p(s; r). the quantity (E) has direct relations to the original disagreement coefficient
from Definition 25, Specifically, for h as (10), 18 since Bp, (h*, .r/2) S Cp(r) S BBp (h", 2(3 + r)) for any r > e, we immediately have
1
3 (S+E)
3 (B+E) (3++
2 0p(e/2) < (e) < (2((3(++)))
+4
(51)
By definition, we always have (s) I J. However, unlike (r((;;) r) in (48), the quantity 0% (E) is not always upper-bounded by the star number (see Example 6 below), so that we need be careful when replacing by (E) in Theorem 3.
is also worth noting that (s) is often not as easy to use for studying specific scenarios, compared to 0p(e), due to the dependence the conditional distribution Y X (whereas 0p(e) depends only on Px and lt*). Nonetheless, below we will state a query complexity bound in terms of 0% (Theorem 30) which is sometimes smaller than that in Theorem 27 (as we illustrate in examples below), and moreover (together with (51)) provides another route to proving the query complexity bound in Corollary 28.
The quantity (e) essentially arises naturally many existing analyses of disagreement- based active learning (e.g., Hanneke, 2009b, 2011 2014; Koltchinskii, 2010; Foster, Rakhlin, Simchi-Levi, and Xu, 2021), wherein certain algorithms are shown to makes queries in subset of DIS (c')) for an appropriate e' 2 E (decreasing as the algorithm runs). In those contexts, it is traditional to upper bound Px (DIS(((((()) by Op(r(e"))r(e)), where r(=') Z SuPNECr(e") (x + ):): for instance, r(=') = 2(3 + E') suffices in the agnostic setting. However, one can alternatively upper bound Px (DIS(CP(())) by (E"))' Such arguments are also valid in the context of Aavid since Corollary 18 implies (Dx-1) S (DDI((CC)())) I 0% (Ex EE,, so that the number of queries in D in round A: is of order 0f (ex)emm = ((0%)))))) )d), which will lead to a lower-order term ( (e)d). Together with reasoning similar to the proof of Theorem 27, this implies the following.
Theorem 30. Under the same conditions as Theorem 27, with probability at least 1- - 8 the predictor returned by Auaii satisfies (h) I infaec p (h) + and the algorithm makes a number of queries at most Q(E, 8; P) satisfying
Q(e, (e = 0
(180
12
( log ))) + min (E) log ()) } dlog !)) + log
1 8
E²
= δ d 82
+ (E)
18e relation sharpens to (p(c)= < (5) < (28 + + (25+2) if we take h² E argmingec ((). supposing this exists (or otherwise, taking h² as discussed in footnote 14).
59

---

Since (E) S the query complexity bound in Theorem 30 is never larger than that in Theorem 1. However, unlike Theorem 27, since the quantity (e) is not always upper-bounded by the star number s, the query complexity bound in Theorem 30 is sometimes larger than that in Theorem 3 (see Example 6 below). That said, the quantities (e) and (p(e; 5,3) are generally incomparable (see Examples 6 and 7), so that either bound may be useful depending on the scenario being studied. Moreover, in light of (51), Theorem 30 is also useful for providing another route to establishing Corollary 28, which is therefore an immediate corollary of either Theorem 27 or Theorem 30.
As mentioned, depending on (C, P), the quantitative difference between 0%) and (p(e: can be better or worse. We illustrate this in the following two examples.
Example 6 (0P(e) >> 2 5,)). As mentioned, for some scenarios, (e) can be quite large, even larger than the star number so that the bound in Theorem 30 becomes even worse than the P-independent bound in Theorem 3 (in contrast to Theorem 27, which never worse than Theorem 3). For instance, consider a singletons class: X' = (1...., }. C {1 :1 X where
3 E (0, 1/2) satisfies 2 E NN for simplicity. Let Px = Uniform(XY, P(Y 1|X x) 2(1-9)
B
for all x E X. Note that every h E C has (h) = B. Moreover, |X| 1 = 2-3 HHowever,
consider < < B. Since Cp(e) = C and DIS(C) = X, we have (e) = = e s For
instance, for =2/3, the bound in Theorem 3 (ignoring logs) of order _ + 2म13
(=). In light of (51), this example also witnesses a scenario where both of the query complexity bounds in Corollary 28 worse than the s s-dependent bound in Theorem 3; more directly, in this
5. In contrast, for any r < 8 and A C X, we have DIS(BP, (h", r)) E {0, А} (depending whether the x with h² (x) = 1 is in A or not), so that PA (DIS(((Bp, (h+, r)) O; this immediately implies (p(s;)) S 3 (indeed, by careful reasoning,
example, we have (p + +=) [++s)
observe that any 2/2 has (p(=;)) 3/8 - 1 5). More generally, by (48), the bound in Theorem 27 is never worse than that in Theorem 3.
On the other hand, there are scenarios (C, P) where the opposite occurs, so that in general neither quantity (e; 5,3) nor 0% (c) dominates the other. This is illustrated in the following example.
Example 7 (0p 5.3) >> (s)). Consider again the class from Appendix F. (and Example 5): that is, X = E and C Ct. == (1(-)) t N). Let E, 3 E (0, 1/3) with E < B, and define P with marginal Px on X' as defined in Appendix F.l: that is, n = 1-28 and for x E (l,...,,), n). Px((=)) 28 (f = 2s. However, rather than the distributions P. described there, consider the family P., (I,..., m). with PÇ 1|X = x) = B + (1 (- (x)) for every E X. These distributions represent scenario with uniform classification noise. For P = P/ for any E (1,...,,)) ,n,, letting h² = [(--)ujjt.e)) it is easy to see that er (h²) = inf er = B. Moreover, (E) = 0p(e/(1 - 235) < (p(()) < 1-28 + 3, where the last inequality was established 3
2c
in Appendix F.1. In contrast, we argued in Example 5 that 0p(e; > Thus, in this scenario, 5,3) is larger than 0%)
1-28
1-28
+ 3 > (e))
4r
A natural question is whether the gaps between (p( and (3())) in Examples 6 and 7 can also arise in cases where the smaller of the two corresponding query complexity bounds (either Theorem 27 or 30) is actually nearly-sharp (in a minimax analysis over a family of distributions). This is straightforward to obtain, by defining family of possible distributions P each obtained as uniform mixture of one of the above two scenarios and the simple 2-point construction of Kääriäinen ga (2006) giving rise to the द lower bound. For brevity, we omit the details of this.
The fact that Theorem 27 at least provides a starting point for P-dependent analysis which never worse than the P P-independent bound in Theorem 3 is desirable feature. In contrast, the bound in Theorem 30 is sometimes better and sometimes worse than that in Theorem 3, so that one should be careful when using Theorem 30. Nonetheless, as illustrated in Example 7, there are at least some scenarios where (%)(s (e) may be useful for describing favorable scenarios (particularly concerning the Y|X conditional distribution).
60

---

F33 Querying in Subregions of the Region of Disagreement
In the active learning literature, one technique for going beyond disagreement- queries is to query examples in carefully selected subregion R S DIS(V) of the region of disagreement of the set V of surviving concepts. This idea originates (2007) on margin-bused active learning of homogeneous linear classifiers under certain marginals Px in realizable and Tsybakov-noise scenarios, and was extended to a technique for general concept classes and the agnostic case by Zhang and Chaudhuri (2014) (see Appendix A for further discussion of the history). For instance, the most well-known case of this technique providing improvements over disagreement-bare
the work of Balcan, Broder, and Zhang
queries (see Example 8 below) is homogeneous linear classifiers under uniform distribution on a sphere (alternatively, any isotropic log-concave distribution), where the
query complexity of this technique is Ö (d(+t)"") (Zhang and Chaudhuri, 2014) (minimax optimal 2²
up to log factors), compared to disagreement-basde based active learning for which the best known bound is Ô d3/22_ (8+c)² (Dasgupta, Hsu, and Monteleoni, 2007).
22
In this section, we show this technique is also compatible with the AVID principle, and propose refinement of the AVID Agnostic algorithm which replaces Da-1 = DIS(( Steps and with well-chosen subregion Rg-1 S Dx-1- We argue that this change does not affect the validity of Theorem 5, and admits refined P-dependent query complexity bounds compared to those presented in Appendix F.2. In particular, this shows that the AVID principle can recover the optimal query complexity of homogencous linear classifiers under the uniform distribution, and generally any isotropic log-concave distribution (indeed, with improved log factors compared to prior works).
The basic argument (building from the original ideas of Balcan, Broder, and Zhang, 2007, and Zhang and Chaudhuri, 2014) is that, rather than querying all examples in S n Dx-1 \ Ai, in Step 2 of Avvid the algorithm identifies a subset of these examples Qx S St n Da-1 A,, which suffices for the purpose of updating V& in Step 3. Specifically, we aim to identify a subset Q+ S S DD Ai, for which, for any h, h Vk-1,
| ((h NY) (s ((h [1h+h) 17 O DK-1 \A,)) - EN 3C"
In other words, most of the significant disagreements in X' Ai, among concepts in Vi- are captured in the Q& set. In particular, this retains the guarantees Lemmas 15 and 16 with only minor adjustments to the constants in the bounds (accounting for the potential 5C probability disagreements that are lost).
Formally, consider the algorithm Asc stated in Figure 2, where the Qs data subset is defined below. The values C, C², C" N, my and data subsets St.- St are all as defined in Awvid- The data subsets S2. SR,, are defined analogously to Aavid except allocated in the corresponding steps of A that is, if and when the algorithm reaches Step 2 with a value k. or reaches Step 9 (in which case let A N + 1), then for the value ig and the set Ai, defined at that time in the algorithm, letting PA: = 2Ps4 the algorithm allocates to St the next m := CC'c [
(d log 1(3+N-A)
o consecutive examples not previously allocated to any data subset, and likewise, if and when the
algorithm reaches Step 5 with values (k: i), it allocates to S2 the next my consecutive examples which have not yet been allocated to any data subset.
We define the Qk data subset via technique analogous to the work of Zhang and Chaud- huri (2014), specified via a discrete linear program with a finite number of constraints im- posed by the set of realizable classifications of S). Let l -*-- my, and recall S == ((Xt,+1, Vi.+)),.... (X tm Ylytma)). The algorithm inductively constructs sets V2 S in .N + 1}, denote by Step 3 (analogous to the V/2 sets in Awvid). For any given &t E (1,...,N
V == {h((,, +1)...,, ,,,,,, +my )) : Va-13 S (0,1)
the set of Ve-r-rellizable classifications of St. For the set Ds, (which defined inductively based on previous rounds of the algorithm, analogously to the set Dig in Aavid), consider the following integer linear program with binary variables 19 Ç1,0: &1,1, 41, ......, Sma.0s Os Sma. qmy
For simplicity. in this work, we present a technique based on an integer linear program, to arrive at a deterministic querying strategy. It is straightffrward extend the result allow for non-integer solutions
61

---

Algorithm Asub
Input: Error parameter Confidence parameter 8, Unlabeled data X1,... Xm
Output: Classifier h
0. Initialize 1 = 0, A = 0. Vo
1. For k= 1 ,.... N
2. Query all examples in Qk and 5% Die
3. V& - { Vi-1: e (h) & (hx) + e+
4.
If Vf or (ha) min (h) 40 Then Return h = hg
5.
While max Psp. (lf + 9) A,) > Ex+2
6.
(f.g) - (f V' Psp. (1 * g \()))
7.
A+11 u g) and update i+1
8.
1++1 +
9.
Query all examples in Q and 8 n A iy.1 and Return h := h
Figure 2: The Aabregion-AVID Agnostic algorithm.
LPR:
m > gt
minimize
,. Bmm)) E ( 1 my
subject to
Σ
11 1 1( & Aing 60"
m8 t=1
11 E (1...., mx). Se,0 + Se,1 + Qt
S1,0: QI... Smg,1, 9m. {0, 1}
In particular, note that the solution only depends on the unlabeled examples Xt, -1.11..... X ma and thus the algorithm may the solution of this optimization problem when determining appropriate set Q₁ of queries in Steps and 9. Denote by ...... Img the respective values of the Q Am. variables at the solution found by LPk- Then define Q2 as a subsequence of St.
Qx = {(xu+ti Y1++)) 1 s my. q.' 1}.
Let us generalize the definition of Pst to involve intersections with the subsequence Qs: for any set
C x (0, 1}. Psp (AnQk) 1 Σm of n(((t=+t) Ye++e) A), and Pss (ER()) Qx) = my
ma
1. Em (1 ot 1(( Yo,+o) AJ. As usual, we also overload this notation for A C X, such
{f # g), interpreting such sets A as synonymous with their labeled extension A x (0,
The algorithm also relies on the following modifications to the definition of ctl
wh, er == Ps. (ER(h) n Qx) + Psp (ER(h) n..).
(52)
The definitions of V and hy are then defined as in (2) and (3) based on the set V defined in Agub and the modified definition of cr in (52). This completes the specification of the suub algorithm.
We state query complexity guarantee for this algorithm, phrased in terms of variant of subregion disagreement coefficient. As in Appendix F22, we first present known definition from the literature, which serves both as a starting point for the modified version and as more-accessible quantity useful for upper-bounding the new quantity. Specifically, the following definition (a refinement the disagreement coefficient from Definition 25) was proposed by Zhang and Chaudhuri (2014) (see also Hanneke, 2016b).20 20
SLD. G.1 E [0, 1] to the LP. resulting in randomized querying strategy (see Zhang and Chaudhuri, 2014). This makes no significant difference the query complexity bound (see Hanneke, 2016b, for related discussion), but may be more attractive from a computational perspective.
20The variant stated here is phrased slightly differently, to simplify the definition. In particular, rr. 0) is equivalent quantity so (e) studied by Hanneke (2016b), which is only slightly different than the original
62

---

Definition 31. For any measure μ on X, any V S C, and any 17 2 0, define
Pu(V,n) == -inf ((R)) sup vEV
sup + f) R) S 7, measurable R _ X and f: + 10.113.
For any distribution Px on X and any measurable h X + 10, any s, 2 0, define p (Brg (l, (r - a) a)/(3)C))) V1.
= sup roa+t
In particular, for any distribution P on X x {0, 13, letting h be as in (10) (or see footnote 14), define PPle, a) == PP,,1e (E,
The quantity P (V, identifies the smallest (R) among regions R X' for which functions E V do not disagree much outside the region R (i.c., they have at most disagreement with fixed function f on X' (t). In particular, we can upper bound pp, (V, n) by taking R DIS(V) and any f E V. which satisfies su Prlig + f} \ R) = 0 S 17, so that pp. (V, n) S Px (DIS(V)) It immediately follows that the quantity (P,,,(e, is never larger than the disagreement coefficient:
(P,,A(E,)) a) S (a.,
(53)
Indeed, there are several known examples of scenarios (C, Px. ht)) where Pr a) is substantially smaller than (p(++)) (Zhang and Chaudhuri, 2014). One example (discussed formally in Example below) is the class C of homogeneous linear classifiers in Id under Px a uniform distribution on an origin-centered sphere, where (0) = e( (vd)
=(va) and (p(s, = Olog ()t)) (Hanneke, 2007b;
Balcan, Broder, and Zhang, 2007; Zhang and Chaudhuri, 2014).
By (53) and (47), we also always have (p)(,,) S A 1 a-s for any E, 2 0 with + S 1. Indeed, with pp(e) in (47), this inequality turns out to be sharp in the worst case. Specifically, Hanneke (2016b) has shown that supr, suPhec PP,, 0) = s S 1 for E (0, 1]. Additionally, by definition we have PP,,AEE, a) 2 PP + E, 0). Since (53) implies P a) S 0p,n + +))
2
immediately follows from combining this result of Hanneke (2016b) with (47) that for any s, a 2 0 with a + S.L.
sup sup Pr, (E, = a a+E
sup Ps AEC
(54)
Due to (53) and the example in Appendix F.1, we know is not possible to replace with PP(c, a) in Theorem 3 for any a 2 O (for any algorithm). However, similarly to the modifica- tion (p(=:)) of (p(e) presented in Appendix F.2, we can modify Definition 31 appropriately to provide a quantity suitable for developing query complexity bound for A Specifically, as in Defimition 26, let us first generalize the definition of (P,,,(E, a:) to general measures μr: that is, for any measure i on X and measurable function h X + {0, 1}, for any E, 2 0, define V 1. Then consider the following definition, 5 disagreement coefficient.
Punle, a) == sup,>a+e B..B..thrrl.o-aa/3BBccCC representing a region-excluded subregion
Definition 32. For any distribution P on X' x {0, 1} and any measurable A C X, define a measure + (A == (x A). For any and a, T 2 O, for h* E C as in (10) (or see footnotes 14, 17), define
op(E,a;T)== =
sup Ax
(P,.k-(E,a))
As was the case for (r( equivalently define (p T) as the subregion disagreement coefficient under a worst-case conditional distribution Px \ A): that is,
op(E,0;T)
sup ACXSPT(A)ST
&PA(A))))))) (X a), A)),
(55)
where we define (R(IMAA) coincides with the value P (e, ar) for such A). In particular, combining this equivalent definition with (54) yields that
A), a (X A)) 1 in the case Px ((') A) = 0 (which
9p a; S a+E V1.
(56)
quantity studied by Zhang and Chaudhuri (2014) in that it considers binary functions rather than fractional values in Jo, 1]. Hanneke (2016b) has shown this change to binary values makes little quantitative difference compared to the quantity of Zhang and Chaudhuri (2014).
63

---

Thus, replacing in Theorem by (P((),;;) would yield (never-larger) P-dependent refinement.
As with 0p(e; r), the quantity Pr(é, a; itself may often be challenging to calculate. Fortunately, again as with (r( it can be upper-hounded by expressions that are more-easily calculated (though the expense of some slack, that they no longer upper-hounded by s). We might therefore think of p T) as an intermediate complexity measure (analogous to T)), which useful in providing starting point for e'ddependent refinement of s which never larger than s, and which admits general upper bounds which are more accessible than directly calculating Ppp a: T). Specifically, follows immediately from Definition 32 that we always have lower bound ()) S (p((E,;;)) a; T), and an upper bound
Pr. (Bp, (h,, T + r), (r (r=a))3360C") V1
#P(E,a;T) sup 12ate
F
sup(s,a+r)++ (atrte) aat S )
(attte) aat
S <pple,at7)
(57)
Making of the quantity pe, 7) to analyze Auub, analogously the analysis of Awvid based on (p(e:7) 7) in Theorem 27, we arrive at the following theorem.
Theorem 33 (Distibution-dependenn Query Complexity of Subregion AVID Agnostic). For any concept class with VC(C) < oo, letting d for every distribution P on x {0, 1}. letting bnc (h), for any e, E (0, 1), if the algorithm Agaid, is executed with parameters (e, 5), with any number m 2 M(e, 8; B) of i.i.d..PPP examples (for Mc, d; (3 as in Theorem 5, defined in Lemina 24), then with probability infRec er (h) + E and the algorithm makes a number of queries at most Q(E, 8; P) satisfying
least 1 8, the returned predictor h satisfies ch)(h) s
d+log ))
1 1.11
1
1
((E (; 10=00
52
+ -min (pp(,,0;53))
d
+ +log
8
=0(d d Ez
32 + d de,
Proof Sketch. The proof of this theorem follows nearly identically to the proof of Theorem 5. We will merely highlight the changes compared to the original proof. Specifically, throughout the proof, first replace all definitions from Aavid with the corresponding definitions from A avid (e.g., A,, ik. hg. Vg, D DIS(V& 1)) S2. S2,, K, K., etc.) so that all definitions the proof refer to the respective quantities in the Asuha algorithm. Since the only definitional change in Agub compared to Aavid is in the use of Q2 rather than St n Dz-1 \ Ai,, to provide the & error guarantee it will suffice to argue that the inequality (14) of Lemma 10 remains valid (only slightly larger) with this change: namely, on the event Eo.
Vh, h E 1 (Pst (ER(h) n Qk) - Psg. (BR(K')Qu))
-(P(ER(H) \ Ax) - P(ER(H)) \ Axt)
V Px Px + W/ \ Ai,))
Ek C"
+
2 C"
(58)
Note that this only larger than the bound (14) by an additive 3 (which we will argue below inconsequential to the proof). As was true of (14), we argue that (58) in fact follows immediately ck from (18), as follows. Consider the values ch. c of ....... Sh o: Sm gh at the solution of the I.P, optimization. Due to the first constraint in L.P we know every f Vx-1 has
1[x & A
5k 60"
Moreover, due to the second constraint in LPx, for every f.g Va-1, any Xtatt {f + g) has S2,1- (1)
- 11) +
oe 1, so that de 0 (1,1)(Xxu1d) S2,1 -0 = 1.
Together, we have
Psp ((tf # #g) A.,) (()
Σ
(()1-)(X))))) + 5t -
(st
Ek 1|x $ Ai, 3C"
64

---

Recall that every h E k-1 is of the form h = DL(f h² := (' + (M' for some f' E Va-1 and h E C. Consider any two such functions h, h E V k-1 where h = (1, h1)
and h' = DL(f2: 02, h2) for f1.91. f2. 92 E V and h1, h2 E C. Note that
{h + W) = (f + f2) fgr + 92) U {11 + gt}-
Therefore, the union bound implies
Psg (((h + #) ( Qx)
Pst ((th # /2) A.)) QQ) + Ps ((tg + 92) ( Qx) + Ps # 9n A.)) Q+)
Ck
O"
Also note that, due to the indicator 1[X +c & Aip in the first constraint of LPk. at the solution to LPk, every Xeate & Aig has of = 0, so that any h E Vk-1 has ER(h) nQ+ = (ER(h) ) Altogether, we have that every h, h' E V satisfy
(Ps)(ER()) ( Q+) - (FR()R()))
(Ps) \ A..) - Pst (FR(()) \ A..)) ((ER(())()))) \ A \ Qx) - Psg (EER()) \ Anr) 2x)
S (ss # N3 \ A..) \4)) S
EN
(59)
C"
Together with (18) we arrive at the claimed inequality (58).
In the context of the rest of the proof of Theorem 5, the only place (14) is used is in (28) in the proof of Lemma 15. In that context, substituting (58) yields the same conclusion: namely, for h1, hn V since (20) of Lemma 12 implies Px # M \ And) S 3Ek, (58) implies
Psp (ER(M, (Qk) Pst (ER(M) Qx) (P(ER()) A..)) P(ER(M) \ Aw.))
3c C
22H
2
S
C"
VC"
where the last inequality follows from > 100. Therefore, the conclusion of Lemma 15 remains valid (with the modified definition of er from (52)). The rest of the proof of the error bound (Lemma 19), and unlabeled sample size ( 8: 3) (Lemma 24), and size of Px (A,A.,) (Lemma 20) follow verbatim from this fact.
It remains only to establish the claimed bound Q(s, 6; P) on the number of queries. In the context of the proof of Theorem 5, this effectively means replacing (39) of Lemma 23 with a bound on [Qu] based on 9 (s, 0; 5,3), on an event E'g of probability at least 1 & (which replaces the event E defined in the proof of Lemma 23).
Toward this end, consider any 1 e [I....,N 1} having non-zero probability of is S K. Given the event that k < K and the random variables V and Ais fix a measurable function h2 X + {0, 1} and measurable set R2 C (dependent on Vk-1 and Ai, but not on St) such that
sup Px((1g # h&l \ { 9EV--1
Ek
(60)
180"
and PR \ A.,) S P (Va-1: 18C"
Ek
+
Ek
(61)
2
Such pair (hg, RR) is guaranteed to exist by the definition of (,,(,,)) .) in Definition 31.
We aim to argue that the constraints in LPx are satisfied by taking (x,,x(.,,--)) = 1[ te & Ry] and 4 = [ E R&), via a uniform multiplicative Chernoff bound (Lemma 7 of Appendix D). Toward this end, define a collection A of subsets of X::
A = {(tg + hx) \ R&) \ A. : g E Va-13-
Note that VC(A)) < d. Let dR 12 of Lemma 9. Specifically, we have
We bound e E(mu, de: As) by reasoning similar to the proof
144
m& 2
1500"co
(dlog
Cocoo
log
C"cco ))
108C
dloo
co ) + log
1
)
Ex
Ek
8E
EN
0z
65

---

C" where the last inequality is by 2 1, > 144C and Vidyasagar (2003), this implies
> 54C". By Corollary 4.1 of
c4C"co
mAk [dog
m&
d
+ log
Ek
so that
mmx oxi 54C"
Ek
(62)
Letting 3. we therefore have (mx 8g: As)
a² E...
Together with (60) and Lemma 7 of 8 given the event that k I K and
Appendix D, we have that with conditional probability at least the random variables V Rg, and Dic.
Psg (110 h&] R&) gEVA-1
sup
( Ai))= <
EK 6C"
(63)
By the law of total probability, there is an event E of probability at least 8% such that, on E k I K, then (63) holds. To unify notation, for any E (1,..., .N + 1] having probability zero of l K, define & as the event (of probability one) that k > K, so that this conclusion also vacuously holds for such values k.
In particular, for any & E {1...., N + 1}. suppose the events ES and S K occur. For each t E {I...., m let Go,0 = ((,+(X),++) = 0f1[Xu++ & (Rş \ Ax S/, = 1[hx(XXute) = +] $ (R& \ ). df 1[X R& \ Aig. Note that these values satisfy the second and third constraints Le St,1. qr in LPn. Moreover, (63) implies that Vgg E VR-1.
mk
Σ 1n) $ f Ps: (11g ho) Ra) {
A.,) <
EN 60"
ME
that the first constraint in LPx is also satisfied by this choice of Gooo, Sr,1, 9t. Since the values $t,0> Ch o the solution of L.p minimize Ees 9t among all choices of Sr,0= Sr,1 2t satisfying the constraints, we conclude that the above values of d/ satisfy
1Q Σ
le = m. Ps! (R A..).
(64)
1
Next upper bound the right hand side of (64) via multiplicative Chernoff bound (Lemma 6 of Appendix D). Consider again any f1,...,NN N + 1} having non-zero probability of k < K. Given the event is K and the random variables Rş and Ak-1. Lemma 6 of Appendix implies that, with conditional probability at least 1 5z.
6
2
2
Pss A.) < max (Rx A.))
In
max Ekh,
(65)
me
where the last inequality follows from (62) and straightforward reasoning about numerical constant factors. By the law of total probability, there is an event F!",, of probability at least 8y. on which, l < K, then (65) holds. To unify notation, for any E (I,..., N + 1} having probability zero of A K, also define Eg,, the event (of probability one) that k > K, so that this conclusion also vacuously holds for such values kt
Define F2--
By the union bound, the event EgJ fails with probability most
N-1
N-1
SEk+3
5
25
72
8'
1=1
k=
where the last inequality follows from our choice of C = 11
Altogether, on the event Ey, for every & E {1,... K.....,K. K7. (64), (65), and (61) together imply
Qu S 2m & Paik (VK-1, 18C""
εk
ma
(66)
66

---

It remains to relate the right hand side of (66) to the quantity (p 0; 53), For the remainder of the proof, suppose the event Eg n E n Eg n E3 holds (with E, in the definition of E3 from the proof of Lemma 23 replaced by the above definition of F3)) Consider any l E {,,.... K). Recall that Lemma implies h V which together with Lemma 12 implies Vk-1 C Broa 8x).
Thus, since the definition of (.(-,-) is non-decreasing in its first argument, have
Ek Pran
(Braa, (h (ER), 18C"
Prai
k 18C"
Also recall that Lemma 20 implies Px (A,)) 533 so that A, is among the sets A considered in the supremum in the definition of Pp(EE, 0: 53). Additionally, note that Ek 2 Ex.1 2C It follows that
PPik
Bran (h"ee)):
+ Pail
(BPA. (1,, (E*) 18C"
EK
18
EK
pric
BPas (h", 180
T PaiN
BP (h* 36
360
S sup r>c/2C
Ek
sup rPE
Ek
r/(2C)
① Pask
BPa.,
(h', 36C
- 2C sup
Ek S 2C;
r>e
r
Altogether, we have that every Io E {l,..., .....,, K} satisfies
1Qx1 (4C*p(E,, 0; 5,) + 1) ma=k (4C 1), 5:53
Substituting 1uxl in place of |s] n D \ Aig in the proof of Lemma 23, and using the above bound on Qu in place of (39), we arrive a bound Q(e, 6; P) on the total number of queries
4C
Q(E, 6; 103M2- + ming MI,
p (355) + 1)mxst
2
d log ()) + min (p((, log 1 ( : [dlog
( (E)
1 )))
+ log
E2
As with Auvid, the algorithm Asuh does not need to know the value (p 0; 0,5) (or anything else about P) to achieve this query complexity: that is, it adaptive to the value (s, 5,3).
Together with (57). Theorem 33 further implies (sometimes loose) relaxation in terms of Pp(E, 53). which is often easier to evaluate for given scenarios (C, P). This is stated formally in the following corollary. As mentioned above, the example in Appendix F. shows that it is not generally possible to reduce the pr, 5,)² dependence a linear (e, 5,8) (or even any (0, a)).
Corollary 34. The query complexity bound Q(c, 8; P) in Theorem 33 (achieved by Asub satisfies
Q(e, = 0
82
d + log
+ ò min d 58)
(p++
B B+
:
c²
Ba
d e)
0
d + log
+ δ min (E)
22
Proof. Due to the first two inequalities in (57), the second term in the expression of Q(s, 6; P) in Theorem 27 is at most
o min pp(e, log
1
β (+t
#) d
+ log
(1) )1
(67)
E
Relaxing d log ! + log S (lo((?)
(d log(3) ()) and noting that
(
3 +
( ( + 2
(S+t))
(p(5,53) 5,3) log?
< pp(e, 58) log"
67

---

and
[+t))
I < + 4, the quantity (67) is at most
0 8²
12
(d (
1 log ()) + min (Pp(, log" ( log ) d
(a log (5)
))))
Adding this to the first term in the expression of Q(e, 6; P), the result follows.
An immediate consequence of Corollary 34 is that, whenever suPoe]oo.] (Pp(e, a) polylog (t) the dependence on 3, in the query complexity bound in Theorem 33 is of order & + polylog ()) As true of Corollary 28, (56) implies the first upper bound in Corollary 34 is never larger than the upper bound in Theorem 1; however, this is not always the case for the second upper bound in Corollary 34. Moreover, unlike Theorem 33, both upper bounds in Corollary 34 can sometimes be loose compared to the s-dependent bound in Theorem 5 (e.g., Example 6 in Appendix F.2.2). For this reason, as with Theorem 27, Theorem 33 is useful despite having a quantity ( 0; 5,3) that is more challenging to calculate, as it provides a starting point for P-dependent analysis that is at least never worse than Theorem 5.
To illustrate a well-known scenario where the technique presented in this subsection provides improvements over the basic Avvid algorithm, consider the following example.
Example 8 (Homogeneous linear classifiers, uniform distribution). As an implication of Corollary 34, we find that Agvid recovers near-optimal query complexity bound for learning homogeneous linear classifiers under any marginal Px that is isotropic log-concave. Let d > For any x, Rd denote by (x) = k| z) 2 0]. In this scenario, we suppose X' = R C {hw E RR || = 1} (for which VC(C) d), and Px is any isotropic log-concave distribution (Balcan and Long. 2013) (for instance, Px = Uniform(12 {z ||||| = 1}) is one such distribution). In other words, C is the class of linear classifiers whose hyperplane decision boundary passes through the origin. This scenario has long history of interest in the active learning literature (see Section A), featuring prominently (with Px a uniform distribution) in the original A² paper of Balcan, Beygelzimer, and Langford (2005, 2006, 2009), which studied the case S e/Vd and showed a query complexity techniques. bound Ōd log(2) (2) log(?) in this regime. Later works refined this, via subregion-base Building on the works of Balcan, Broder, and Zhang (2007); Balcan and Long (2013) (which studied more-restrictive noise models), Zhang and Chaudhuri (2014) obtain a query complexity bound
Ó( +d). Here we argue this query complexity bound can be recovered from Corollary 34 (indeed, with improvements by log factors in the lead term). Specifically, Zhang and Chaudhuri (2014) show (based on results of Balcan and Long, 2013) that (p 5,3) = 000g(11g (2) (²)) Plugging into Corollary 34 (rather, the expression obtained in the proof thereof), we obtain a query complexity bound
of
12
d log 1)) + log" ) (t) (d+ log
Compared to the result of Zhang and Chaudhuri (2014), this improves the lead term by a fac- tor log? (8) (though at the expense of additional log factors in the lower-order term). We also note that this query complexity bound represents a refinement of what would be obtained from Corollary 28, since even for the special case of Px uniform on an origin-centered sphere, 0p(3 + = 0 @vāā B+F) (Hanneke, 2007b).
F.4 Classes with Infinite VC Dimension via Covering Numbers
As one final remark about P-dependent query complexity bounds, note that it is also possible to derive interesting query complexity improvements over passive learning even for classes with VC(C) oo under conditions on P commonly studied in the nonparametric passive learning literature: namely, bounded covering numbers.
Denote by (ee, C, (Px)) the minimal size of proper e-cover: that is, the size of the smallest C' C for which SuPлed minwee Px & h²) S e. Being able to construct such a cover from unlabeled examples requires some additional structure beyond finite covering numbers under Px (c.g..
68

---

finite expected empirical covering numbers suffices; see e.g., van der Vaart and Wellner, 1996). Let us suppose such conditions are satisfied by (C, Px). so that (since an active learner can be assumed to have access to an abundant supply of unlabeled examples) we may assume we have access to valid ( proppe--oove C./2 under L1 (Px) of size (e/(2/2, C, I, ))). Constructing this cover Ce/2 does not affect the query complexity, since it only requires the use of unlabeled examples.
We can then run Aavid using Ce/2 in place of C. Since VC(C=/2) (log(V(E/22 LI ((x))), and inf eTp(h) Σ infxec erp (h) + =: + 2. we thereby obtain from Theorem 1 Px- dependent query complexity bound
(f L
log (og(W
+ (o
This result can then he composed with bounds on the covering numbers (V of various classes C under various conditions on Px known from the literature. For instance, this provides an improved query complexity for boundary fragment classes (a class defined by smoothness conditions on the decision boundaries of concepts in ()) under near-uniform distributions Px on [o, 1]*+11 compared to the results established by Wang (2011) (see Wang, 2011; Tsybakov, 2004 for the precise definitions and covering numbers).
G Extensions and Future Directions
We conclude with some extensions and several interesting open questions and future directions.
Extension to Multiclass Classification: We can easily generalize the result hold for multiclass classification: that is, where y is a general label space, C a family of measurable functions h X - V. iss distribution The exact same upper bound extends to this setting if we replace d with max { (A), d where A in Lemma 9 (replacing {0, 1} with y there) and dg denotes the graph dimension of C (Natarajan, 1989). The star number $ is still defined as in Definition 2 (see Hanneke, 2024). The proof holds with only superficial modifications to rely solely on VC(.A) (for the X' \ Ai, concentration) and dg (for concentration in A ). We further note that this dimension max { (VC)), de) is at most O(dy (C) log(("))), where N (C) is the Natarajan dimension of C (Natarajan, 1989); this follows by similar argument as used to bound VC(A) in the proof of Lemma 9, using a generalization of Sauer's lemma for the multiclass setting proven by Haussler and Long (1995).
X' Y, and we still define (h) = P((x,, y) : h(x) & v) = (hER(h)).
For a bounded number of labels ())) this again leads to essentially optimal query complexity, as a lower bound (C) 22
based on the Natarajan dimension d (C) can be shown (similarly to the lower bound for binary classification).
However, for unbounded label spaces (D)= = oo) the learnability and optimal sample complexity of passive learning in the realizable case are known to depend on dimension called the DS dimension (Brukhim, Carmon, Dinur, Moran, and Yehudayoff, 2022; Daniely and Shalev-Shwartz, 2014) which is between the Natarajan dimension and graph dimension. This raises important question: What is the optimal query complexity for multiclass agnostic active lcarning?
Extension to Stream-based Active Learning: For simplicity, we have defined the learning model as so-called pool-based active learning, in that the learning algorithm was given the entire sequence XI,..., Xm, of unlabeled examples as input, and can query any example, in any order. However, it is also common to consider an alternative protocol called stream- basedd active learning (or selective sampling): namely, where the active learner observes the unlabeled examples X; one-at-a-time in sequence, and for each, decides whether or not to query, and can never revisit that decision later. In the literature stream- straam-based active learning, it is common to express the guarantees of the active learning in two parts: (1) a bound on the error guarantee expressed as function of the number m of unlabeled examples processed, and (2) bound on the number of queries it makes among the first m examples (e.g., Dasgupta, Hsu, and Monteleoni, 2007).
We note that Avvid can easily be re-expressed as stream-based active learner. Specifically, rather than limiting the 'For' loop in Step to N (l)og()) rounds, we can simply let the algorithm run until it has allocated as many unlabeled examples as we wish. Rather than allocating all of the
69

---

S/. St. data subsets at the start, we can simply allocate these sets if and when the algorithm reaches the hth iteration of the 'For' loop, at which point the algorithm collects the next my examples to allocate to S%. querying each of these examples X, iff X, E D ' Ai.. Likewise, then collects the next my examples to allocate to St (without making any queries), to calculate the value mi (where, in this case, we should suitably replace the value 3 + N k in the log term in mig to remove the dependence on e: for instance, replacing it with k 2 would suffice for the present discussion). then collects the next m' examples to allocate to the data subset S%. querying each of these examples X2 iff X, Dig then moves on to execute Steps 3-4. Similarly, upon each time it reaches Step 5, it simply collects the next my unlabeled examples to construct S (without making any queries), which then enables it to execute Steps 5-7. We can execute this until any number m of unlabeled
examples have been processed, and define the predictor at such a time as the h2 for the last iteration k for which Step was able completely execute. If the algorithm ever satisfies the early stopping criterion in Step for some iteration k. we can simply take hic as its final predictor. We can then derive the corresponding excess error bound and query bound from the above analysis of the query complexity and unlabeled sample complexity; namely, with probability at least 1 6, the predictor h produced after m unlabeled examples satisfies
orp(h) - inf er (1)
(
o (VV
m (m) + log )1) dog (dlog
+
1 m
d log
m (
+ log
NEC
and its number of queries is bounded by
o 3m + min
$ log
(T)
m
d log
m )
+ log
5 ))
1
m
d
m d
+ log
(1)) m }
( ).
3
md
-33m) Ō
minn sd,
Here the 3m term is where the improvements over passive learning provided by the AVID principle are reflected in the query bound (as the above excess error bound is nearly small the best achievable excess error guarantees for passive learning with m labeled examples; Vapnik and Chervonenkis, 1974; Devroye and Lugosi, 1995; Hanneke, Larsen, and Zhivotovskiy, 2024b). In particular, the above guarantees compare favorably to previous analyses of stream-based active learning (e.g.. Dasgupta, Hsu, and Monteleoni, 2007) in the regime of moderate-size B, where, for the same excess error guarantee, the bounds on the number of queries include term such ((0)(B))m), which becomes of order (s ^ T3 Bm in the worst case over P, and hence is no better than m when s co. In contrast, in this regime of moderate-size 3, where the 3m term dominates, we obtain a factor / improvement in the number of queries.
We also remark that the analysis above also supplies an "anytime" guarantee, where the algorithm can simply be executed indefinitely, and the above excess error bound and query bound hold simulta- neously for every m (where, again, if the algorithm ever satisfies the condition in Step 4, its predictor should simply be defined as the corresponding hy forevermore, and need not query any further examples in the sequence).
The Optimal Lower-Order Term: As discussed above, while the leading term in Theorem is exacty optimal (perfectly matching lower bound), the lower-order term in the upper bound in Theorem 3 presents a small gap (in the dependence on d) compared the best known lower bound (Hanneke and Yang, 2015). As discussed, some aspects of this gap (concerning _ + d vs 9) cannot be improved if the dependence on C is only expressed via d and s: that is, without introducing new complexity measures. We leave open the question of formulating such an always- sharp complexity measure, that is, the question: What is the optimal form of the query complexity e(QC,, 8; B, C)) for all classes C? However, aside from this gap, there is a gap which might be improvable even in expressions of the bound purely in terms of and namely, the term sd in the upper bound. I conjecture this can be reduced to simply s: that is, QC, (e, 6; 3, C)- of (d + log())) + Óminnss {]) for every concept class C.
70

---

Proper Learning: As noted above, the Aavid algorithm is an improper learner, meaning its returned predictor h might not be an element of the concept class C (rather, it is shallow decision list built from concepts in C). It is an interesting open question to determine whether there exist proper active learners achieving the query complexity bound in either Theorem I or 3 for every concept class C. It follows from Corollary 18 that, in the return case in Step 9, it would suffice to return h equal any element of Vx- Thus, the main challenge in obtaining a proper learner is in the early-stopping case in Step 4. In this return case, we have effectively verified that p (ha) is better than er (h*) (Lemma 17). However, the resolution of the error estimates erg 1r at this stage might not yet be
sufficient to find an E V nearly as good, Indeed, for this reason, any such early return case in an active learning algorithm may be problematic for proper learning.
On the other hand, we remark that, for all previous known separations between proper and improper sample complexities, the respective proofs break down if the learner is given access to the marginal distribution Px or a sufficiently large unlabeled data set (Bousquet, Hanneke, Moran, and Zhiv- otovskiy, 2020; Hanneke, Larsen, and Zhivotovskiy, 2024b; Daniely and Shalev-Shwarle 2014; Montasser, Hanneke, and Srebro, 2019; Asilis, Devic, Sharan, and Teng. 2025a; Asilis, Høgsgaard, and Velegkas, 2025b). Since, for the purpose of merely bounding the query complexity, we may suppose an active learner has access to a large unlabeled data set, this hints that such improvements might indeed be achievable by proper active learners, or otherwise, a novel technique is needed for establishing such a separation between proper and improper active learning.
Computational Efficiency: The focus of this work has been solely on the information-theoree query complexity of agnostic active learning, without any computational or resource constraints beyond the number of queries and unlabeled examples. However, computational considerations are of course also important to consider. To actually achieve the agnostic learning guarantee of e excess error is typically thought to be computationally intractable for many concept classes, without distribution restrictions. Nonetheless, it would be interesting to determine whether, at least at some level, the improvements in the leading term reflected in Theorems 1 and 3 might also be reflected in computationally efficient method, for some classes C (e.g.. linear classifiers) under some restrictions on the distribution P which enable computational tractability yet for which such query complexity bounds are not captured by prior results (e.g.. by (p))).
Beyond this, a classical approach to obtaining computationally efficient algorithms in practice is to introduce convex relaxations of the various optimization problems involved in a given algorithm. In the literature on passive learning, the theory of error bounds for empirical risk minimization has been extended to allow for convex relaxations of the 0-1 loss, called a surrogate loss, while still rate under appropriate assumptions on P relating excess
guaranteeing bounds on the excess surrogate risks to excess error rates (Bartlett, Jordan, and McAuliffe, 2006; Zhang, 2004). Prior work on disagreement-basse based active learning has been found to compose well with this theory of surrogate losses. Specifically, Hanneke and Yang (2019); Hanneke (2014) express disagreement-basse learning algorithms, in which the optimization problems defining the query criterion and the learner's final predictor are relaxed to convex programs expressed in terms of any given surrogate loss. For such algorithms, they derive query complexity bounds (based on the disagreement coefficient (s)s) holding under the same conditions studied by the passive learning works (Bartlett, Jordan, and McAuliffe, 2006; Zhang, 2004). thus a natural question to determine whether such theory can be made to work for the algorithmic principles underlying Aavid (i.e., the AVID principle), leading to an algorithm only requiring computationally tractable convex optimization problems based on a given surrogate loss, and expressing query complexity improvements over passive learning (of the type found in Theorems and 3) under these same conditions on P relating excess surrogate risks to the excess error rates. This approach is made challenging in the context of Awvid, due to its use of improper predictors hg, and even more-so due to the maximization in Steps 5 and 6 (whereas convex surrogate losses would typically only allow tractability of minimization problems).
active
As step toward such technique, an interesting intermediate question is whether Theorems 1 and 3 can be achieved by an active learning algorithm expressed as a reduction to an empirical risk minimization ( (ERM) oracle: that is, where the access to the concept class C is restricted to solving optimization problems of the form argminkec (h) for data sets S (or possibly a weighted ERM). This would be particularly interesting if these data sets S are only constructed from subsets of the labeled examples ( (X,, Y.) queried by the algorithm (perhaps plus one additional example (X,, y) with an artificial label y, which may be needed when deciding whether to query X₂). Previous works
71

---

by Beygelzimer, Hsu, Langford, and Zhang (2010); Hsu (2010) have expressed disagreement- based active learning algorithms as reductions to such ERM oracles. It is therefore natural question to consider whether the AVID principle can also be implemented based only on such oracles (and such an implementation could also be an important step toward enabling the above composition with the theory of surrogate losses).
Unlabeled Sample Complexity: Theorem reveals that, to achieve the stated query complexity bound with Aavid. it suffices to have access to number of unlabeled examples M(, 6; B) ( (o)) + +o))) In comparison, we can obtain an obvious lower bound on the number of unlabeled examples necessary achieve any query complexity bound by a lower bound on the sample complexity of fully-supervised passive learning (Devroye and Lugosi, 1995): i.e.,
2 s+c (d+ (o)))))) Thus, the upper bound M(,, 8; 3) in Theorem can be improved by at most (+) factor. This naturally raises the question: Is it possible to achieve a near-optimal query complexity ((QC, 6; $, C)) with an algorithm which uses a number unlabeled examples o( -+ queries and the number of unlabeled examples. To date, this is not even known to be achievable by sully-super passive learning, the best known upper bound having an additive Ö(#) term (Hanneke, Larsen, and Zhivotovskiy, 2024b). Thus, for now, a more- moor-approachaale question would be whether it is possible to match the query complexity bound in Theorem 3 using number of unlabeled examples suboptimal only in log factors in the lower-order term, that is: Is there an algorithm achieving a query complexity upper bound O g (d log ( + Ō((S 1) d) which
ex (d log log (+)) Such a result would then be optimal simultaneously in both the number of
uses a number of unlabeled examples at most O ( log())) + ) As an intermediate step, it would already be interesting to determine whether this many unlabeled examples suffices to achieve the query complexity bound in Theorem I.
Tsybakov Noise: Beyond the above directions, there are number of further extensions of this work that seem ripe for exploration. One natural direction is extending the techniques in this work to the case of Tsybakov noise (Mammen and Tsybakov, 1999; Tsybakov, 2004; Massart and Nédélec, 2006). The optimal query complexity under Tsybakov noise was already identified by Hanneke and Yang (2015) (aside from similar gaps to the vs 1 + d issue discussed above, which require introducing new complexity measure to resolve). However, the algorithmic techniques in the present work are significantly simpler, and moreover, have the potential to dramatically reduce the number of unlabeled examples required for learning, compared to the technique of Hanneke and Yang (2015). conjecture that the AVID principle is capable of yielding near-optimal query complexity guarantees under Tsybakov noise (with a number of unlabeled examples of the same order as the sample complexity of supervised learning, up to log factors); however, obtaining such guarantees may require sore-sophisticated usage of the principle, such as by the creation of multiple different regions A, coinciding with different levels of variance of excess error estimates. Indeed, an analogous tiered allocation of queries was key to the original analysis of the query complexity under Tsybakov noise by Hanneke and Yang (2015).
72

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The paper formally proves (appropriate formalizations of) the claims made in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The paper explicitly mentions number of questions left open by this work (e.g., refining a lower-order term, proper learning, expression as a reduction to ERM, efficient relaxations via surrogate losses).
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
73

---

Answer: [Yes]
Justification: The main body includes formal definitions and a proof outline, and a complete formal proof is provided in the supplemental material.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: This is a purely theoretical work, and as such does not include experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
74

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: This is purely theoretical work, and as such does not include experimental component relying on data or code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm
Pholic//giies/Codeeefe
www.ssssssslllllooo onPolicyl ply for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / /ttpp.ccpppplliippppp hopollc/ggidesss
seabbbmmsssoonPe ssiiisolicyyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This a purely theoretical work, and as such does not include an experimental component.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This is a purely theoretical work, and as such does not include experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
75

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This a purely theoretical work, and such does include experimental component relying on computer resources.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't iidn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics bttps://neurr: cwtpurip..ccppulllilee cttppblic///ccccccccctcccccccclt wwtpppbiie/ttieeeeeeeeeeeeeeeeee SthiissGuiellieess
Answer: [Yes]
Justification: guidelines.
We have reviewed the NeurIPS Code of Ethics and fully conform to the
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is purely theoretical work, and as such is not likely to have broader societal impacts.
Guidelines:
76

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negatíve societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (c.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This purely theoretical work, and as such there is no associated data or model being released.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not make use of such assets. All relevant literature is properly cited.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
77

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com comddatasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The work in this paper does not involve crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The work in this paper does not involve human subjects or crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
78

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLMs were not involved in any aspect of this research.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: /ttaaa://euurprie ct/ www.co/eeeeeecce//22222222 for what should or should not be described.
79


Reviews:
[{"review_id": "8TY4TON8Yn", "reviewer": "Reviewer_WXbZ", "summary": "This paper presents a novel agnostic active learning algorithm that aims to achieve a significantly lower query complexity than passive learning across various concept classes, without making strong assumptions about the data distribution. The core contribution is a new framework for active learning that adapts to the local variance of disagreements within the hypothesis space, allowing it to efficiently identify high-information examples to query. This approach provides improved theoretical guarantees on label complexity, often achieving exponential speedups over passive learning in settings where prior methods either offered limited gains or required specific noise assumptions. The paper details the algorithm's mechanics, provides rigorous proofs for its performance, and demonstrates its advantages over existing disagreement-based active learning methods, particularly in terms of consistency and sample complexity in the agnostic setting.", "questions": "- How do the theoretical benefits of agnostic active learning extend to and provide insights for common deep learning practices, particularly those involving highly expressive, over-parameterized models like deep neural networks that often achieve very low training error?\n- Are there plans for, or have preliminary results shown, empirical evaluations of the proposed algorithm?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper's most significant contribution is the demonstration and proof that, for any concept class and without any distributional assumptions, the query complexity of active learning can always offer improvements over the sample complexity of passive learning in the challenging non-realizable case. The proposed algorithm serves as the concrete, constructive proof of this principle, showing how such an improvement is universally achievable.\n- The paper effectively positions its contributions in relation to existing literature, highlighting the limitations of previous active learning approaches and how its new framework addresses them.\n\nWeaknesses:\n- My major concern is whether the setting of agnostic learning is so interesting in deep learning. While agnostic learning focuses on scenarios where the true data distribution is \"far-from-realizable\" by the hypothesis class, practitioners commonly employ heavily over-parameterized neural networks that are capable of achieving zero training error (or near-zero error). This prevalent practice suggests that the deep learning regime often operates closer to, or even within, a realizable setting.\n- The paper lacks empirical results or simulations. While the theoretical guarantees are strong, a lack of empirical validation could be a weakness.", "was_revised": true, "final_justification": "The clarifications on both over-parameterized models and practical considerations have fully addressed my concerns. Indeed, learning tasks can be partitioned into the realizable case, where the target labeling function is expressible within the model family and some classifier can achieve zero error, and the non-realizable case, where no member of the family can perfectly match the distribution. The latter case is important, even in the over-parameterized regime of deep learning. Overall, I thought that the main claim of the submission is significant, and I therefore maintain my positive assessment of the paper.", "rebuttal": "We thank you for your efforts in taking the time to read and review our paper.  We appreciate your positive remarks regarding the significance of the advances in this work, and the quality of presentation.\n\nWe address specific comments raised in the review below.\n\n>Overparameterized models:\n\nThe extension of the theory of active learning to overparameterized models is a very interesting and important topic for future work.  It is unclear whether we should really interpret the overparameterized regime as the \"realizable case\", since it does not necessarily admit zero population error rate (without making strong assumptions), but rather the model is complex enough (growing with sample size) to fit the training data well. As such, the techniques in this work may still be relevant even in this case.  We intend to explore in future work whether the AVID principle has implications for more specialized scenarios, including overparameterized and nonparametric learning.  For instance, as one speculative idea, it may be the case that the technique of isolating the \"high variance\" regions where two low-error classifiers disagree can instead be identified by training two predictors on independent data sets and isolating the region where these predictors disagree, and training another predictor on additional data queried in this region.  This is a possibility we intend to explore in future work.\n\nWe also remark that even overparameterized *passive* learning has only been understood theoretically in highly specialized scenarios, under distributional assumptions.  In contrast, in this work we aim for a broad general theory, applicable to any concept class, with no distribution restrictions, so the aims are quite different.  Nonetheless, there have been some works on active learning with neural networks in overparameterized and nonparametric regimes (e.g., by Nowak and others), and a factor of disagreement coefficient appears in some of those bounds (e.g., Zhu & Nowak 2022), so it is natural to wonder whether the AVID principle can again help reduce the query complexity by the factor of disagreement coefficient (as it does in the present work), and we intend to follow up this work by investigating this question.\n\n> Practicality / empirical evaluation:\n\nThe focus of this work is in developing new algorithmic principles for active learning, and identifying the optimal first-order query complexity for all concept classes.  This was a challenging problem, which took 20 years to solve.  Having resolved this question, a further step will be to develop practical methods inspired by the principles we have identified.  This follows a familiar pattern in statistical learning theory.  Initial work identifying algorithmic principles is often impractical at first, but may later evolve into practical learning methods.  For instance, the work of Vapnik and Chervonenkis in the 60s and 70s on passive learning identified the principle of empirical risk minimization and the fundamental role of the VC dimension in characterizing the sample complexity, but does not have a direct practical implication due to the 0-1 loss being computationally challenging to optimize; only later, when combined with the idea of surrogate losses to relax the non-convex 0-1 loss to a convex loss, did we arrive at practical passive learning methods (for which we may recover theoretical guarantees under assumptions relating the minimizer of the surrogate loss to that of the 0-1 loss, based on the theory of Bartlett, Jordan, & McAuliffe 2006).  A similar line has been followed in the active learning literature.  While the initial methods for disagreement-based agnostic active learning (e.g., the A^2 algorithm of Balcan, Beygelzimer, & Langford 06) involved implicit direct optimizations of the 0-1 loss (making them infeasible to run) and provided a coarse theoretical understanding of the query complexity (via the disagreement coefficient analysis of Hanneke 07), only later were these methods made practical by identifying appropriate ways to replace the optimization problems implicit in the technique with convex problems (e.g., by Beygelzimer, Dasgupta, & Langford 2009, Hanneke 2014, Hanneke & Yang 2019), recovering the theoretical guarantees under assumptions relating the minimizer under the convex surrogate loss to that of the 0-1 loss.  Following this line, a natural next step for the present line of work (mentioned in appendix G) is to investigate ways to replace the various optimization problems involved in the AVID algorithm with appropriate convex relaxations, while recovering the sharp theoretical guarantees of this work under appropriate assumptions on the surrogate loss.  This is a nontrivial extension (as was the case for disagreement-based methods, as discussed in section 6.6 of Hanneke 2014), and will require significant further research.  We have been thinking deeply about this question, and aim to develop such an extension in future work (more discussion of this in our reply to reviewer qnfZ)."}, {"review_id": "EMpSVNw6eR", "reviewer": "Reviewer_qnfZ", "summary": "This paper presents a significant theoretical advance in the field of agnostic active learning. The authors introduce a novel algorithm, AVID (Adaptive Localized Variance Isolation by Disagreements), and use it to sharply characterize the optimal query complexity for all concept classes. The key finding is that agnostic active learning is always more sample-efficient than passive supervised learning in the non-realizable case. This resolves an important open question that has been central to the field by removing the dependence on restrictive measures like the disagreement coefficient from the leading term of the complexity bound.", "questions": "see weaknesses part", "limitations": "see weaknesses part", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "# Strengths\n\n- The paper's main result -- that every concept class benefits from active learning in the agnostic setting -- is a significant achievement. It fundamentally advances the field by proving that the improvements over passive learning are not confined to restricted cases but are a general property. This work resolves a long-standing open problem by closing the gap between the upper and lower bounds.\n- The proposed AVID algorithm introduces an innovative and powerful principle of \"adaptive localized variance isolation\". The algorithm intelligently partitions the instance space to isolate high-variance \"challenging\" regions, allocates a disproportionately large number of queries there, and uses more standard disagreement-based methods on the remaining \"easier\" parts of the space. This represents a new and insightful approach to designing active learning algorithms.\n- This paper presents a great introduction that positions the work well. The authors begin by providing a comprehensive historical overview of the problem, tracing its evolution from early foundational studies to contemporary developments, which allows readers to understand how the field has progressed over time. They then systematically identify and analyze the key limitations of prior work, clearly articulating gaps in methodology, scope, or understanding that previous researchers have left unaddressed. \n\n# Weaknesses\n\nOverall, I am satisfied with this paper. However, I believe the clarity of the algorithmic description could be improved. The algorithm is difficult to follow because key components lack clear definitions and intuitive explanations, and the quantities used in equations need better conceptual background. For instance, the quantities in Equations (1), (2), and (3) are confusing without adequate conceptual background. Providing simpler, more intuitive explanations of these essential components would greatly improve readers' understanding of the algorithm's design and functionality.\nOther weaknesses include:\n\n- Improper Learning: The algorithm returns predictors that may not belong to the original concept class C. While the authors acknowledge this limitation, the question of whether proper learners can achieve the same bounds remains open.\n\n- Computational Complexity: The paper focuses solely on information-theoretic query complexity without addressing computational efficiency. The algorithm requires solving constrained optimization problems that may be intractable for many concept classes.\n\nThese limitations are discussed by the authors, and the current results are strong enough. Therefore, I would like to vote for acceptance of this paper.", "was_revised": true, "final_justification": "The authors answered my questions in detail, so I am keeping my original score.", "rebuttal": "We thank you for your efforts in taking the time to read and review our paper.  We are very happy to read your positive and supportive feedback, regarding the significance, innovation, and presentation of this work.\n\nWe answer specific questions raised in the review:\n\n>Clarity:\n\nWe truly appreciate your feedback regarding mindfulness of the conceptual background needed to understand the various quantities.  We are striving to make this work readable by a broad audience, and will take your comments to heart when making use of the additional page allowed in the camera-ready version.\n\n>Proper learning:\n\nWe find it an important question to determine whether the algorithm can be made proper (and we mention this in appendix G).  We have thought deeply about this question, but could not reach a conclusion one way or the other (yet).  While we can show the return case in Step 9 can return any element of $V_N$, the other return case, in Step 4 (the early stopping case) is quite a bit more tricky, as the returned improper hypothesis is actually better than the best-in-class concept (Lemma 17); it is unclear how to replace this improper hypothesis with a concept in the class, since at that stage we do not have a good enough resolution in $\\epsilon_k$ to identify a good concept in the class, so a proper learner simply cannot have such an early stopping case.  We intend to continue exploring this question in future work.\n\n>Computational complexity: \n\nThe focus of this work is in developing new algorithmic principles for active learning, and identifying the optimal first-order query complexity for all concept classes.  This was a challenging problem, which took 20 years to solve.  Having resolved this question, a further step will be to develop practical methods inspired by the principles we have identified.  This follows a familiar pattern in statistical learning theory.  Adopting the abstract perspective of working with general VC classes helps to identify the essential algorithmic principles.  Then in subsequent work, focusing on more specialized scenarios, those algorithmic principles may inspire practical efficient methods.  In appendix G, we discuss one possible route, involving relaxations of the non-convex optimization problems with convex optimization problems via appropriate uses of convex surrogate loss functions.  Such practical modifications have been studied theoretically for both passive learning (Bartlett, Jordan, & McAuliffe 2006) and disagreement-based active learning (Hanneke 2014, Hanneke & Yang 2019), and in future work we plan to explore whether there are appropriate variations of the AVID algorithm from the present work which make use of surrogate losses to obtain a computationally efficient method (preserving the sharp query complexity guarantees, under standard assumptions regarding alignment of the surrogate loss minimizer and the 0-1 loss minimizer, as adopted in the aforementioned prior works on surrogate losses).  This approach is made more challenging in the technique developed in this work, due to the use of improper learners (see above), and even more-so due to the maximization in Steps 5 and 6.  One speculative strategy we are currently exploring is that it might be possible to approximate this maximization by solving two minimization problems with different weightings of the data to \"push apart\" the two minimizers (i.e., in the training set of the second function, we could weight higher the examples where the first function is wrong, to force the two functions to have diverse error regions, which is the main property we require of them); if this can be made to work, it would require significant changes to parts of the proof, but we are currently trying to work with this idea as a follow-up work."}, {"review_id": "WoGniam4Uf", "reviewer": "Reviewer_sYK9", "summary": "This paper tackles the long-standing open problem of whether active learning (AL) can provably outperform passive learning in the agnostic setting, where the hypothesis class may be misspecified. The authors present a novel algorithm called AVID (Adaptive Variance Isolation by Disagreement), which leverages disagreement-based strategies and variance estimation to isolate informative samples. The core theoretical result shows that AVID achieves faster convergence rates than passive learning under broad conditions, particularly without assuming the realizability of the hypothesis class. The results are purely theoretical, with no empirical experiments.", "questions": "Does the proposed method have any concrete instantiation that is computationally feasible? Specifically, is there a known polynomial-time algorithm that can efficiently identify hypotheses that maximize disagreement within a version space?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper establishes, for the first time, that active learning is universally better than passive learning in the agnostic case, under general conditions.\n2. AVID is grounded in a principled approach to isolate high-variance disagreement regions, supported by clear theoretical analysis.\n3. The paper provides detailed and rigorous proofs of label complexity bounds, supported by extensive theoretical discussion.\n\nWeaknesses:\n1. The practicality of AVID is not explored. There is no discussion of how the method might be approximated or implemented in real systems.\n2. The paper does not provide any empirical results, simulations, or illustrative experiments to support the practical effectiveness or feasibility of AVID.\n3. While the paper includes a detailed discussion on star number as a key complexity measure, this is somewhat weakened by the fact that many commonly used hypothesis classes have infinite star numbers. This limits the practical insight offered by that part of the analysis.", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your efforts in taking the time to read and review our paper, and we appreciate your positive remarks regarding the novelty of the ideas in this work.\n\nWe address specific questions raised in the review below.\n\n> The star number: \n\nWe chose to present Theorem 1 first (which is expressed purely in terms of the VC dimension), before introducing any other complexity measures, to avoid any confusion regarding the role of the star number.  To be clear, the conclusion that the dominant term in the query complexity of active learning is smaller than the sample complexity of passive learning holds for *every* concept class, regardless of whether the star number is finite or not.  As your comment suggests, it is true that Theorem 1 already provides the sharpest possible bound for most interesting concept classes.  However, Theorem 3 offers a nearly-sharp bound for *every* concept class, offering a more complete picture of the optimal lower-order term for all classes.  Both bounds are the same in the dominant term, so the distinction is only in the lower-order term, and hence this has no bearing on the qualitative conclusions of this work: active learning can improve over passive learning for every concept class in the non-realizable case.\n\n\n> Practicality / empirical evaluation / computational complexity:\n\nThe focus of this work is in developing new algorithmic principles for active learning, and identifying the optimal first-order query complexity for all concept classes.  This was a challenging problem, which took 20 years to solve.  Having resolved this question, a further step will be to develop practical methods inspired by the principles we have identified.  This follows a familiar pattern in statistical learning theory.  Initial work identifying algorithmic principles is often impractical at first, but may later evolve into practical learning methods.  For instance, the work of Vapnik and Chervonenkis in the 60s and 70s on passive learning identified the principle of empirical risk minimization and the fundamental role of the VC dimension in characterizing the sample complexity, but does not have a direct practical implication due to the 0-1 loss being computationally challenging to optimize; only later, when combined with the idea of surrogate losses to relax the non-convex 0-1 loss to a convex loss, did we arrive at practical passive learning methods (for which we may recover theoretical guarantees under assumptions relating the minimizer of the surrogate loss to that of the 0-1 loss, based on the theory of Bartlett, Jordan, & McAuliffe 2006).  A similar line has been followed in the active learning literature.  While the initial methods for disagreement-based agnostic active learning (e.g., the A^2 algorithm of Balcan, Beygelzimer, & Langford 06) involved implicit direct optimizations of the 0-1 loss (making them infeasible to run) and provided a coarse theoretical understanding of the query complexity (via the disagreement coefficient analysis of Hanneke 07), only later were these methods made practical by identifying appropriate ways to replace the optimization problems implicit in the technique with convex problems (e.g., by Beygelzimer, Dasgupta, & Langford 2009, Hanneke 2014, Hanneke & Yang 2019), recovering the theoretical guarantees under assumptions relating the minimizer under the convex surrogate loss to that of the 0-1 loss.  Following this line, a natural next step for the present line of work (mentioned in appendix G) is to investigate ways to replace the various optimization problems involved in the AVID algorithm with appropriate convex relaxations, while still preserving the sharp theoretical guarantees of this work under appropriate assumptions on the surrogate loss. (more on this below). \n\nRegarding the specific practical issue of computational complexity: for simple concept classes (where the VC dimension $d$ is considered a constant), the optimizations can typically be performed in polynomial time in the sample size $m$, as the algorithm can simply consider a subset of $O(m^d)$ concepts witnessing all possible classifications of the $m$ examples.  For instance, for $\\mathcal{X} = \\mathbb{R}$ and $\\mathbb{C}$ as the class of \"interval concepts\" $[a,b]$, the algorithm need only consider the concepts whose endpoints $a,b$ are at data points, so just $O(m^2)$ concepts; the optimization steps can then simply search over this polynomial-size subset of concepts to find the solutions in polynomial time.\n\nMore generally, beyond such simple cases, agnostic learning (even passively) is known to be computationally hard (cryptographic hardness is known, even for linear classifiers, and NP-hardness for proper learners).  However, there are natural routes toward converting the algorithmic principles in this work into practical methods.  In appendix G, we discuss one possible route, involving relaxations of the non-convex optimization problems with convex optimization problems via appropriate uses of convex surrogate loss functions.  Such practical modifications have been studied theoretically for both passive learning (Bartlett, Jordan, & McAuliffe 2006) and disagreement-based active learning (Hanneke 2014, Hanneke & Yang 2019), and in future work we plan to explore whether there are appropriate variations of the AVID algorithm from the present work which make use of surrogate losses to obtain a computationally efficient method (preserving the sharp query complexity guarantees, under standard assumptions regarding alignment of the surrogate loss minimizer and the 0-1 loss minimizer, as adopted in the aforementioned prior works on surrogate losses).  We remark that this is not merely a matter of running essentially the same algorithm with a different loss function (as discussed in section 6.6 of Hanneke 2014, active learning can be unhelpful for optimizing a convex loss, so the surrogate loss should be used more-carefully as a mere computational tool, not an overall objective to be optimized).  This approach is made even more challenging in the technique developed in this work, due to the use of improper learners and even more-so due to the maximization in Steps 5 and 6.  One speculative strategy we are currently exploring is that it might be possible to approximate this maximization by solving two minimization problems with different weightings of the data to \"push apart\" the two minimizers (i.e., in the training set of the second function, we could weight higher the examples where the first function is wrong, to force the two functions to have diverse error regions, which is the main property we require of them); if this can be made to work, it would require significant changes to parts of the proof, but we are currently trying to work with this idea as a follow-up work."}, {"review_id": "0BY7FoN2YJ", "reviewer": "Reviewer_D9zk", "summary": "The paper examines the problem of agnostic active learning, and refine upper bounds on the optimal query sample complexity needed to reach a given error $\\epsilon$. In comparison to previous bounds, the present bound exhibits an additional factor $\\beta$ (best misclassification error in the hypothesis class), allowing the authors to match the known lower bound and show sharp results. The study proceeds through a careful analysis of a proposed algorithm achieving the sample complexity. The proposed algorithm identifies regions where function in the hypothesis class have large disagreement, and adaptatively allocates more samples.", "questions": "- I found section 4.1 to be rather hard to read, at least for a general audience. I suggest the authors make use of the extra space for the camera ready version to include additional high-level intuition on the workings of the AVID algorithm. In particular, I think the paragraph \"overall behavior\" could be moved at the beginning of the section for added clarity.\n- The bound of Theorem 3 does not depend on the data distribution $P$ explicitly. Does the effect of the latter simply appear through $\\beta$? \n- Could the authors provide an instantiation of their results in a simple case for illustration and clarity, e.g. linear classifiers for Gaussian data, with labels generated by a noisy linear rule $y_i={\\rm sign}(\\langle X_i, \\beta \\rangle)+\\epsilon_i$ for some vector $\\beta$? \n- Minor suggestion: I understand it is not the purpose of the paper, but do the authors have a rough estimation of the runtime complexity of the AVID algorithm in a simple case, just for illustration?", "limitations": "All the assumptions needed for the theoretical results to hold are clearly stated.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strength:\n- Overall, I find the submission to be a very strong technical paper. My evaluation comes with the caveat that I have very limited familiarity with the field and the proof techniques, and have not checked the detailed formal proofs in the appendix carefully. I have read in detail the proof sketches and outlines in the main text, which appear sound.\n- The result is also of sizeable significance, and establishes that active sample queries can always achieve better sample complexity than passive queries, regardless of the considered hypothesis class. It allows the establishing of a tight result, together with the previously known lower bound.\n- The paper is very clearly written and structured, with minor improvement points that I list below. In particular, the work is very well motivated by the related works section, and all important technical points are discussed.\n\nWeaknesses:\n- I have identified any particular weakness with regards to the science, although this might be due to my limited familiarity with the field. I do have a few comments on the structure and questions, which I list below.\n\nI have put a good score, but please use it sparingly, due to my limited familiarity with the topic and the techniques.", "was_revised": true, "final_justification": "I thank the authors for their clear answers to my questions.\n\nI have read the other reviews, and to my reading, all the points seem to have been satisfyingly addressed by the authors in their rebuttal. None of them challenges the fact that the paper seems to make an interesting theoretical contribution. \n\nI thus remain in favor of accepting this paper. I am not pushing for a strong accept, and keep a low confidence score, because I have very limited familiarity with the topic, related literature and proof techniques.", "rebuttal": "We thank you for your efforts in taking the time to read and review our paper.  We are very happy to read your positive and supportive feedback, regarding the strength, significance, and presentation of this work.\n\nWe answer questions raised in the review below:\n\n> Section 4.1:\n\nWe appreciate your feedback regarding section 4.1.  We agree that this subsection is particularly dense and throws a lot of notation at the reader, and we will definitely use some of the extra space in the camera-ready version to add explanations of the various quantities and an earlier description of the overall behavior of the algorithm.  We are striving to make this work readable by a broad audience, and really appreciate your feedback helping us achieve that goal. \n\n> Theorem 3:\n\nYou are correct that both Theorems 1 and 3 have no dependence on P except $\\beta$.  In other words, this is a minimax analysis where $\\beta$ is the only parameter constraining the family of distributions in the ``max''.\n\n> A simple example:\n\nFor the example you mentioned, if we suppose $\\mathbb{C}$ is the set of linear classifiers $x \\mapsto \\text{sign}(\\langle x,w\\rangle)$ on $\\mathbb{R}^d$, where $P(Y=\\text{sign}(\\langle X,w^\\star \\rangle)|X) = 1-\\epsilon(X) \\in [1/2,1]$ for some $w^\\star$, then the VC dimension is $d$, the star number is $\\infty$, and $\\beta = \\mathbb{E}_X[\\epsilon(X)]$ under the marginal $P_X$ of $X$ (e.g., this could be Gaussian or anything).  Plugging these values into the theorem provides the guarantee.  (in fact, in this scenario, under an origin-centered spherical Gaussian distribution, one can show that the lead term in the bound is sharp for a choice of $\\epsilon(x)$ that gets close to $1/2$ near the decision boundary of the $w^\\star$ classifier)\nWe will include some illustrative examples like this in the final version.\n\n> Running time:\n\nFor simple concept classes (where the VC dimension $d$ is considered a constant), \nthe optimizations can typically be performed in polynomial time in the sample size $m$, as the algorithm can simply consider a subset of $O(m^d)$ concepts witnessing all possible classifications of the $m$ examples.  For instance, for $\\mathcal{X} = \\mathbb{R}$ and $\\mathbb{C}$ as the class of \"interval concepts\" $[a,b]$, the algorithm need only consider the concepts whose endpoints $a,b$ are at data points, so just $O(m^2)$ concepts; the optimization steps can then simply search over this polynomial-size subset of concepts to find the solutions in polynomial time (in this case, naively $O(m^7)$ time, or $O(m^5)$ if we're a little clever in the optimization for $\\hat{h}_k$).\n\nMore generally, beyond such simple cases, agnostic learning (even passively) is known to be computationally hard (cryptographic hardness is known, even for linear classifiers, and NP-hardness for proper learners).  However, there are natural routes toward converting the algorithmic principles in this work into practical methods.  In appendix G, we discuss one possible route, involving relaxations of the non-convex optimization problems with convex optimization problems via appropriate uses of convex surrogate loss functions. (see the response to reviewer qnfZ for further discussion on this)"}]

Author rebuttal:

Meta-review: This paper introduces an insightful algorithm that closes a long-standing and central theoretical gap that has been under study for the past 20 years within active learning theory. In particular, the proposed and analyzed algorithm closes the gap (in most problem parameter regimes) between upper and lower bounds for agnostic active learning, for any concept class, any (unknown) data distribution, in terms of the VC dimension and best-in-class error. The reviewers appreciated the clear description of the history of the problem, its study, and its solution by the proven result. The reviewers noted that the algorithm was polynomial-time in the size of the concept class (if finite), which is intractable for most applications, though quite standard for initial results in learning theory. Given the significance of the result, I enthusiastically recommend acceptance.
Decision: Accept (oral)