A Competitive Algorithm for Agnostic Active Learning
Authors: Yihan Zhou
Eric Price
Venue: NeurIPS 2023 poster (2023)
Keywords: active learning
binary classification
competitive ratio
TL;DR: We propose an algorithm for agnostic active binary classification with good competitive ratio.

Abstract: For some hypothesis classes and input distributions, \emph{active}
  agnostic learning needs exponentially fewer samples than passive
  learning; for other classes and distributions, it offers little to
  no improvement.  The most popular algorithms for agnostic active
  learning express their performance in terms of a parameter called
  the disagreement coefficient, but it is known that these algorithms
  are inefficient on some inputs.

  We take a different approach to agnostic active learning, getting an
  algorithm that is \emph{competitive} with the optimal algorithm for
  any binary hypothesis class $H$ and distribution $\mathcal{D}_X$ over $X$.
  In particular, if any algorithm can use $m^*$ queries to get
  $O(\eta)$ error, then our algorithm uses $O(m^* \log H)$ queries to
  get $O(\eta)$ error.  Our algorithm lies in the vein of the
  splitting-based approach of Dasgupta [2004], which gets a similar
  result for the realizable ($\eta = 0$) setting.

  We also show that it is NP-hard to do better than our algorithm's
  $O(\log H)$ overhead in general.

A Competitive Algorithm for Agnostic Active Learning
Eric Price
Yihan Zhou
Department of Computer Science University of Texas at Austin ecprice@cs utexas. edu
Department Computer Science University of Texas at Austin joeyzhou&cs wtwxas. edu
Abstract
For some hypothesis classes and input distributions, active agnostic learning needs exponentially fewer samples than passive learning; for other classes and distribu- tions, it offers little no improvement. The most popular algorithms for agnostic active learning express their performance in terms of a parameter called the dis- agreement coefficient, but it is known that these algorithms inefficient some inputs.
We take different approach to agnostic active learning, getting an algorithm that is competirive with the optimal algorithm for any binary hypothesis class H and distribution Dx over X. In particular, if any algorithm can use m queries get (1) error, then our algorithm uses (m log [H]) queries to get O error. Our algorithm lies in the vein of the splitting-based approach of Dasgupta [2004], which gets a similar result for the realizable (n = 0) setting.
We also show that it is NP-hard to do better than our algorithm's O(log H]) overhead in general.
Introduction
Active learning is motivated by settings where unlabeled data is cheap but labeling it is expen- sive. By carefully choosing which points to label, one can often achieve significant reductions in label complexity [Cohn et al., 1994]. A canonical example with exponential improvement is one-dimensional threshold functions hrr (x) := 1227: in the noiseless setting, an active learner can use binary search to find an e-approximation solution in (log !) queries, while passive learner needs θ (!) samples [Cohn et al., 1994, Dasgupta, 2005, Nowak, 2011].
In this paper we concerned with agnostic binary classification. We are given hypothesis class H of binary hypotheses h + {0, 1} such that some E H has err(h*) S 7), where the error
err(h) = Pr (H:))~
(1(x)) + v]
measured with respect to an unknown distribution D over X' x (0, 1). our active setting, we also know the marginal distribution Dx of x, and can query any point x of our choosing to receive sample y (Y X for (X,Y) ~ D. The goal is output some h with err(h) as few queries as possible.
using
The first interesting results for agnostic active learning were shown by Balcan et al. [2006]. who gave an algorithm called Agnostic Active (A²) that gets logarithmic dependence on in some natural settings: needs Ō (log }) samples for the 1d linear threshold setting (binary search), as long as 167, and Ô (d log :) samples for d-dimensional linear thresholds when D.x is the uniform sphere and & ddn. This stands in contrast to the polynomial dependence on necessary in the passive setting. The bound's requirement that 2 n7 is quite natural given a lower bound Ω (d""
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

due to [Kääriäinen, 2006, Beygelzimer et al., 2009], where d is the VC dimension. Subsequent works have given new algorithms [Dasgupta et al., 2007, Beygelzimer al., 2010] and new analyses (Hanneke, 2007a] to get bounds for more general problems, parameterized by the "ddssagremmet coefficient" of the problem. But while these can give better bounds in specific cases, they do not give good competitive ratio to the optimum algorithm: see (Hanneke [2014), Section 8.2.5) for realizable example where O (log }) queries are possible, but disigreementt-oefficieee based bounds lead to Q (t) queries.
By contrast, in the realizable, identifialle setting (1) = 0), a simple greedy algorithm is competitive with the optimal algorithm. particular, Dasgupta [2004] shows that if any algorithm can identify the true hypothesis in queries, then the greedy algorithm that repeatedly queries the point that splits the most hypotheses will identify the true hypothesis in O(m log [H] queries. This extra factor of log [ is computationally necessary: as we will show in Theorem 1.2, avoiding it is NP-hard in general. This approach can extend [Dasgupta, 2005] to the PAC setting (so & > 0, but still 17 0), showing that if any algorithm gets error in m" queries, then this algorithm gets error 85 in roughly Ö(m* log H[ queries (but see the discussion after Theorem 8.2 of Hanneke [2014], which points out that one of the logarithmic factors is in an uncontrolled parameter т, and states that "Resolving the issue of this extra factor of log remains an important open problem in the theory of active learning.").
The natural question is: optimal one in the agnostic setting?
find an agnostic active learning algorithm that is competitive with the
Our Results. Our main result is just such competitive bound. We say an active agnostic learning algorithm solves an instance (H, Dxx 17, E, 8) with m measurements if, for every distribution DD with marginal Dx and for which some h" E H has err(h") ) I with probability 1 - 8, A uses at + E. Let m² (H, Dx, E, 6) be the optimal number of queries for this problem, i.c., the smallest m for which any A can solve (H, 1x,7, n,E,
most m queries and outputs h E H with err h s
Define N(H, Dx, a) to be the size of the smallest a-cover over H, i.e., the smallest set S S H such that for every h E H there exists h' E S with Pra=Dx [h(x) o h (x)) S a. When the context is clear, we drop the parameters and simply use N. Of course, N is at most [H].
Theorem 1.1 (Competitive Bound). There exist some constants Cı, C2 and 03 such that for any instance (H, ",,,,,, 6) with 2 C17). Algorithm solves the instance with sample complexity
99
1 8 log
N(H, Dx.
m m(H, Px.m,,,))) S m² (H, 0277 C3E,
+ log
100
and polynomial time.
Even the case of 1 = 0 is interesting, given the discussion in [Hanneke, 2014] of the gap in (Dasgupta, 2005]'s bound, but the main contribution is the ability to handle the agnostic setting of 1 0. The requirement that 2 (π)) is in line with prior work [Balcan et al., 2006, Dasgupta, 2005]. Up to constants in 7 and E, Theorem 1.1 shows that our algorithm is within log N log [H] factor of the optimal query complexity.
We show that it NP-hard to avoid this log N factor, even in the realizable = 0) case: Theorem 1.2 (Lower Bound). is NP-hard to find a query strategy for every agnostic active learning instance within an clog H for some constant > 0 factor of the optimal sample complexity.
This is a relatively simple reduction from the hardness of approximating SETCOVER [Dinur and Steurer, 2014]. The lower bound instance has 1) = ô O, although these can be relaxed being small polynomials (e.g.. E = 17 l|i| and 8 = 3|
1
Extension. We give an improved bound for our algorithm in the case of noisy binary search (i.c.,
Il consists of Id threshold functions). When 7) +(E), N (11 D) O()) ) and m (77, (,9)), Olog 2). Thus Theorem 1.1 immediately gives a bound of Ollog 1 ), which is nontrivial but not ideal. (For 17 < the same bound holds since the problem is strictly easier when 17 is smaller.) However, the bound in Theorem 1.1 is quite loose in this setting, and we can instead give bound of
1
log
0
log c0
log
6

---

for the same algorithm, Algorithm 1. This matches the bound given by disagreement coefficient based algorithms for constant 6. The proof of this improved dependence comes from bounding a new parameter measuring the complexity of an H, H, pair; this parameter is always at least !?( m= but may be much larger (and constant for 1d threshold functions). See Theorem 2.3 for details.
1.1 Related Work
Active learning is a widely studied topic, taking many forms beyond the directly related work on agnostic active learning discussed above [Settles, 2009]. Our algorithm can be viewed as similar to "uncertainty sampling" [Lewis, 1995, Lewis and Catlett, 1994]. a popular empirical approach to active learning, though we need some modifications to tolerate adversarial noise.
One problem related to the one studied this paper is noisy binary search, which corresponds to active learning of 1 thresholds. This has been extensively studied in the setting of i.i.d. noise [Burnashev and Zigangirov, 1974, Ben-Or and Hassidim, 2008, Dereniowski et al., 2021] as well as monotonic queries IKarp and Kleinberg, 2007]. Some work in this vein has extended beyond binary search to (essentially) active binary classification [Nowak, 2008, 2011]. These algorithms are all fairly similar to ours, in that they do multiplicative weights/Bayesian updates, but they query the single maximally informative point. This is fine in the i..dd noise setting, but in an agnostic setting the adversary can corrupt that query. For this reason, our algorithm needs to find a set of eigh-information points to query.
Another related problems is decision tree learning. The realizable, noiseless case 7) = & 0 of our problem can be reduced to learning a binary decision tree with minimal depth. Hegedüs [1995]
studied this problem and gave basically the same upper and lower bound as in Dasgupta [2005]. Kosaraju et al. [2002] studied a split tree problem, which is a generalization of binary decision tree learning, and also gave similar bounds. Azad et al. [2022] is monograph focusing on decision tree learning, in which many variations are studied, including learning with noise. However, this line of work usually allows different forms of queries so their results are not directly comparable from results in the active learning literature.
For much more work on the agnostic active binary classification problem, see Hanneke [2014] and references therein. Many of these papers give bounds in terms of the disagreement coefficient, but sometimes in terms of other parameters. For example, Katz-Samuels et al. [2021] has a query bound that is always competitive with the disagreement coefficient-ban based methods, and sometimes much better; still, it is not competitive with the optimum in all cases.
In terms of the lower bound, is shown in Laurent and Rivest [1976] that the problem is NP-complete, in the realizable and noiseless setting. To the best of our knowledge, our Theorem 1.2 showing hardness of approximation to within a (log [H] factor is new.
Minimax sample complexity bounds. Hanneke and Yang [2015] and Hanneke [2007b] have also given "minimax" sample complexity bounds for their algorithms, also getting sample complexity within O(log [)] of optimal. However, these results are optimal with respect to the sample complex- ity for the worst-case distribution over y and x. But the unlabeled data is given input. So one should hope for a bound with respect to optimal for the actual x and only worst-case over y, this is our bound.
We give the following example to illustrate that our bound, and indeed our algorithm, can be much better.
Example 1.3. Define a hypothesis class of N hypotheses hi,... bN and log N + N data points -i,'.-" ... , Flog N For each hypothesis h2. the labels of the first N points express j in unary and the labels of the last log N points express j in binary. We set nl = E 0 and consider the realizable case.
In the above example, the binary region is far more informative than the unary region, but disagreement coefficient-barte algorithms just note that every point has disagreement. Our algorithm will query the binary encoding region and take Ollog N) queries. Disagreement coefficient based algorithms, including those in Hanneke and Yang [2015] and Hanneke [2007b]. will rely on essentially uniform sampling for the first ( log N) queries. These algorithms are "minimax" over x, in the sense that if you didn't I see any x from the binary region, you would need almost as many samples as they use. But you do see x from the binary region, so the algorithm should make use of to get exponential improvement.
3

---

Future Work. Our upper bound assumes full knowledge of Dx and the ability to query arbitrary points z. Often in active learning, the algorithm receives large but not infinite set of unlabeled sample points æ, and can only query the labels of those points. How well our results adapt to this setting we leave as an open question.
Similarly, our bound is polynomial in the number of hypotheses and the domain size. This is hard to avoid in full generality--ff you don't evaluate most hypotheses on most data points, you might be missing the most informative points-buut perhaps it can be avoided in structured examples.
2 Algorithm Overview
Our algorithm is based on a Buyessan/muultillccttee weights type approach to the problem, and is along the lines of the splitting-base based approach of Dasgupta [2004].
We maintain a set weights whh) for each E H. starting at 1; these induce a distribution X(h)
w(h) which we can think of as posterior over the "true" ht. Σn (o(
Realizable setting, As initial intuition, consider the realizable case v = E 0 where we want to find the true h If really were drawn from prior X, and we query point æ, will see a with probability Ensa h(z). Then the most informative point to query is the one we are least confident in, i.., the point x² maximizing
r(x) min
E (1()), 1- B(O)) Am
Suppose an algorithm queries Z1. I' and receives the majority label under h each time. Then the fraction of h ~ X that agree with all the queries is at least 1 - -E r(x;) 2 1 mr(x"), m. it will be hard to uniquely identify h". It is not hard to formalize this, showing that: no single hypothesis has 75% probability under X, and any algorithm exists with sample complexity m and 90% success probability at finding h", we must have r(x") N 10m
This suggests that, if r(=") < 1
This immediately gives an algorithm for the r = set whh for all hypotheses l that disagree, and repeat. As long as at least two hypotheses remain, the maximum probability will be 50% 90% and each iteration will remove Q ()) fraction of ma the remaining hypotheses; thus after (m log H) rounds, only h" will remain. This is the basis for Dasgupta [2004].
setting: query the point æ maximizing r(x).
initial attempt. There are two obvious problems with the above algorithm in the agnostic setting, where a (possibly adversarial) yy fraction of locations æ will not match ht" First, single етrоr will cause the algorithm to forever reject the true hypothesis; and second, the algorithm makes deterministic gueries, which means adversarial noise could be placed precisely on the locations queried to make the algorithm learn nothing.
Handling noise:
To fix the first problem, we can adjust the algorithm to perform multiplicative weights: if in round we query point z; and see we set
(w)(h) (w
if (mx) = y/ if h(x,)) ) + y/s
Wi+ (h)
for a small constant a }.. To fix the second problem, we don't query the single x" of maximum r(z"), ), but instead choose x according to distribution over many points z with large r(z).
To understand this algorithm, consider how log (hh)) evolves in expectation in each step. This increases the query is correct, and decreases it has an error. A correct query increases X; in proportion to the fraction of À placed on hypotheses that get the query wrong, which is least r(z);
and the probability of an error at most 17 max, (m)) distribution g, some calculation gives that
g(z) If at iteration the algorithm uses query
E [[())) - 2.3m max q(x) z~g
E log Ar+1(h") - log (,(h))] ]] 2 0.9a
(1)
Dz

---

X(h)
Values h(x)
h1
0.9
1111
h2
0.1 - 10-6
1111 0000
hg
10-6
0000 1110
0000 III1
Figure I: An example demonstrating that the weight of the hypothesis can decrease A concentrated the wrong hall. In this example, the true labels y are closest to ha. But if the prior A on hypotheses puts far more weight on fyy and b2. the algorithm will query uniformly over where and lez disagree: the secend half points. Over this query distribution, more correct than hs. the weight of lts can actually decrease if ((ks) very large.
The algorithm can choose q maximize this bound the potential gain. There's tradeoff between concentrating the samples over the x of largest r(z), and spreading out the samples so the adversary can't 't raise the error probability too high. We show that if learning is possible by any algorithm (for constant factor larger 1)), then there exists a for which this potential gain is significant.
Lemma 2.1 (Connection to OPT). Define |
PTz=D, [h(x)) + ('())) Let À be a distribution
over H such that radius- (2n + E) ball B centered on h E H has probability at least 80%. Let
m = m HH, D.E. 106 Then there exists a query distribution over X with
99
((x)
E [r(())] z-1
TI max 10
SF (x 100m
At very high level, the proof is: imagine h" ~ X. If the algorithm only sees the majority label on every query it performs, then its output h is independent of he and cannot be valid for more than 80% of inputs by the ball assumption; hence a 99% successful algorithm must have a 19% chance of seeing a minority label. But for m" queries x drawn with marginal distribution q. without noise the expected number of minority labels seen is m [[[(x)), so [[[(=)] Z 1/m=" With noise, the adversary can corrupt the minority labels in h² back toward the majority, leading the given bound.
The query distribution optimizing (1) has a simple structure: take a threshold T for r(x), sample from D, conditioned on r(x) > T, and possibly sample with r(x) at lower rate. This means the algorithm can efficiently find the optimal q.
Except for the caveat about À not already concentrating in a small ball, applying Lemma 2.1 combined with (1) shows that log X(h*) grows by 2 ( in expectation for each query. It starts out at log A(h²)= = log H. so after O(m" log H) queries we would have X(h") being large constant in expectation (and with high probability. by Freedman's 's inequality for concentration of martingales). Of course X(h") can't 't grow past 1, which features in this argument in that once X(h*) > 80%, small ball will have large probability and Lemma 2.1 no longer applies, but at that point we can just output any hypothesis in the heavy ball.
Handling noise: the challenge. There is one omission in the above argument that is surprisingly challenging to fix, and ends up requiring significant changes to the algorithm: if at an intermediate step A; concentrates in the wrong small ball, the algorithm will not necessarily make progress. is entirely possible that X; concentrates in a small ball, even in the first iteration pernnappeehsssspp 99% of the hypotheses in H are close to each other. And if that happens, then we will have r(x) S 0..0 for most I, which could make the RHS of (1) negative for all q.
In fact, it seems like reasonable Bayesian-inspired algorithm really must allow X(h*) to decrease in some situations. Consider the setting of Figure 1. We have three hypotheses, h1, h,, and has and a prior = (0.9, 0.099999, 10 6). Because A(ha) is so tiny, the algorithm presumably should ignore hg and query essentially uniformly from the locations where hi and h2 disagree. In this example, hg agrees with ft on all but an 7) mass in those locations, so even if h² = h33 the query distribution can match b1 perfectly and not h2. Then w(h,) stays constant while w (o(h)) shrinks. w(ha) shrinks much faster, of course, but since the denominator is dominated by w(h1). X(hy) will still shrink. However, despite X(hs) shrinking, the algorithm is still making progress in this example: X(ha) is shrinking fast, and once it becomes small relative to A(ha) then the algorithm will start querying points distinguish hg from hn, which point X(ha) will start an inexorable rise.
Our solution is to "cap" the large density balls in X, dividing their probability by two, when applying Lemma 2. Our algorithm maintains set S C H of the "high-density region," such that the capped
5

---

distribution:
(((h)
h S
X(h)
1-4 Pr A(h)
h $ S
has no large ball. Then Lemma 2.1 applies to X, giving the existence of a query distribution so that the corresponding F(x) is large. We then define the potential function
<i(h²) = log (hhh)) + log (1()))
(2)
Enes, (h)
for ht* & St, and Φ; for h* E S₁. We show that di grows by O (())) in expectation in each iteration. Thus, as the example of Figure 1, either X(h*) grows as fraction of the whole distribution, or as fraction of the "low-density" region.
at any iteration we find that À has some heavy ball B(u, 27 + E) so Lemma 2.1 would not apply, we add B (μ', 6n + 3ε) S, where B (u', 2rg + E) is the heaviest ball before capping. We show that this ensures that small heavy ball exists in the capped distribution X. Expanding S only increases the potential function, and then the lack of heavy ball implies the potential will continue to grow.
Thus the potential (2) starts at -2 log [. and grows by 2 ( in each iteration. After O(m" log H) iterations, we will have Φ; 2 in expectation (and with high probability by Freedman's inequality). This is only possible if h* S. which means that one of the centers of the balls added to S is valid answer.
In fact, with some careful analysis we can show that with 1 - probability that one of the first Olog 8. balls added to S is valid answer. The algorithm can then check all the centers of these balls, using the following active agnostic learning algorithm:
= 3n with O (IH) log 44) samples.
Theorem 2.2. Active agnostic learning can be solved for =
Proof. The algorithm is the following. Take any pair h It with || 11'1| 2 3n. Sample O (log [td
observations randomly from (æ ~ Dz h(x) + h((x)). One h, h is wrong on at least half the queries; remove it from H and repeat. At the end, return any remaining h.
To analyze this, let h* H be the hypothesis with error 77. If h² is chosen must have еrror at least 2ty. Therefore the chance we remove h" is at most 5/ | In each round we remove hypothesis, so there are at most H rounds and at most probability of ever crossing off h* If we never cross off ht," at the end we output some h with ||h h" || s 3n, which gives 3n. Li
round, the other h'
The linear dependence [. makes the Theorem 2.2 algorithm quite bad in most circumstances, the dependence only on |H| makes perfect for our second stage (where we have reduced to Ollog [H] candidate hypotheses).
Overall, this argument gives an O (m" log + log log loglt 5 sample algorithm for agnostic active learning. One can simplify this bound by observing that the set of centers C added by our algorithm form a packing, and must therefore all be distinguishable by the optimal algorithm, so mn* 2 log C. This gives bound of
o (1m" log {) log
//] 5
By starting with ne-tet of size N. we can reduce | to N with constant factor increase in v)- With some properly chosen constants C4 and cs. the entire algorithm is formally described in Algorithm 1.
Remark 1: As stated, the algorithm requires knowing m to set the target sample complexity / number of rounds This restriction could be removed with the following idea. m² only enters the analysis through the fact that O (1] is lower bound on the expected increase of the potential

---

function in each iteration. However, the algorithm knows bound on its expected increase in each round is the value
C1
(xx)
max E 2- Fr.s 20
max
(x
optimized in the algorithm. Therefore, could adaptive termination criterion that stops iteration & Σ Ti 2 O(log !!! ). This will guarantee that when terminating, the potential will be above 0 with high probability so our analysis holds.
The algorithm's 's running time is polynomial in H.) This in general avoidable. since the input is truth table for H. The bottleneck of the computation is the step where the algorithm checks if the heaviest ball has mass greater than 80%. This step could be accelcrated by randomly sampling hypothesis and points to estimate and find heavy balls; this would improve the dependence nearly linear in H. the hypothesis class has some structure, like the binary search example, the algorithm can be implemented more efficiently.
Remark 2:
Algorithm Competitive Algorithm for Active Agnostic Learning
Compute a 2n maximal packing H'
Let w/ for every h H'
So + 0
C 5 0
for i 1, O (m" log ! do
Compute (i) Enen wy 14h) for every h E H
16
if there exists C477 + C5E ball with probability 80% over Xi,s. then S; 4 S B (3ann + 3csE) where B (μ', ca7) + OsE) is the heaviest radius C47) + CsE ball over X;
C+ CU {n'}
else
L
S. +- S
(1)(h))
h E St
Compute Tr.s,
1- PrANA [1ES
Ax(h)
h $ S.
T Pr NNE.
Compute Fr,s, (x) = -min E [b(r)), - E E,,, [h(x)]] for every x E X
Find a query distribution by solving
G" = max E Fi,s, (+)]
C1 17 max
q(x) Dx(x)
subject to
E [a(x)] 3n
9 2-4
20
z>xx
Query q², getting label
Set (h) (h)
if (x)) for every h E H'
-w: (h) if h(x) +
Find the best hypothesis C using the stage two algorithm in Theorem 2.2 return h
Generalization for Better Bounds. To get a better dependence for 1 threshold functions, we separate out the Lemma 2.1 bound (1) from the analysis of the algorithm given bound on (1). Then for particular instances like 1d threshold functions, we get better bound on the algorithm by giving a larger bound on (1).
Theorem 2.3. Suppose that Dr and H are such that, for any distribution X over H such that no radius- (cay c5E) ball has probability more than 80%, there exists distribution q over X such that
[r(x)]
C4
max q(x)
2
20
Dz(I)
for some 3 Then for 2 CTT ca 300, G to and > 90cs, let N N(H, Dz. ") be the size of an g-cover of H. Algorithm solves (1,,,5) active agnostic learning with O log + log log log samples.

---

Corollary 2.4. There exists a constant 01 > 1 such that, for 1d threshold functions and E > C17) Algorithm I solves e,,
samples. E, 6) active agnostic learning with (log to log 8
log
Proof. Because the problem is only harder if 17 is larger, we can raise 7 to be e/C, where C' > 1 a sufficiently large constant that Theorem 2.3 applies. Then 1d threshold functions have an 1y-ovvrr of size N = O(1/e). To get the result by Theorem 2.3, it suffices to show / = (1).
Each hypothesis is of the form h(x) I22,, and corresponds to threshold 7. So can consider À to be a distribution over т.
Let À be any distribution for which no radius- R with probability greater than 80% ball exists, for R = c47) + osE. For any percent p between 0 and 100, let Tp denote the pth percentile of under (i.e., the smallest / such that Pr(r S () 2 p/1 p/100). By the ball assumption, Ti0 and 7g0 do not lie in the same radius-Ai R. ball. Hence | hy > R. or
Pr/rio S x Tool R.
We let g denote (Dx Ti0 S < T.0). Then for all x E supp(g) we have r(x) 2 0.1 and
g(x)
1
<
(x(x)
Pr E supp(g))
R
Therefore we can set
B E (r()))
max q(x)
0.1
C47
2 1,
2-
20
Dx(x)
20(c477 cg$)
as needed.
3 Proof of Lemma 2.1
Lemma 2.1 (Connection to OPT). Define ||4- = Pre-D, [b(x) + N'(x)] Let X be a distribution
over such that no radius- (2ntuss-2n-n2n + E) ball B centered on h E H has probability at least 80%. Let m" m² (H, (H, E, 100) Then there exists a query distribution over X with
99
max ((x)
[r(x]] 2~g
10 x (x
100m
Proof. WLOG, we assume that Pra- [h(x)= = 0] 2 PEa~A [h(x) = 1] for every x E X. This means r(x) EE
[E>~|[(<>)) [b[=)]. This can be achieved by flipping all h(x) and observations y for all not satisfying this property; such an operation doesn't 't affect the lemma statement.
We will consider adversary defined by function g X [0, 1]. The adversary takes hypothesis
E H and outputs a distribution over y E {0, 1 such that 0 S y(z) S h(x) always, and y(x)] < " always. For hypothesis h, the adversary sets y(z) 0 for all x with h(x) = O, and y(x) = 0 independently with probability g(x) if h(x) = 1 inulless E. (x())(())) > v, in which the adversary instead simply outputs y h ensure the expected emror is at most always.
err(h) Se,p[h(a
We consider the agnostic learning instance where Dz, h A. and is given by this adversary. Let A be an (17, a) algorithm which uses m measurements and succeeds with 99% probability. Then it must also succeed with 99% probability over this distribution. For the algorithm to succeed sample h. its output h must have ||h Till 27 + e. By the bounded ball assumption, for any choice of adversary, no fixed output succeeds with more than 80% probability over h X.
Now, let Ao be the behavior of A if it observes y 0 for all its queries, rather than the truth; Ao independent of the input. Ay has some distribution over m queries, outputs some distribution of answers ht Let q(x)= = Pr[AA queries æ), is distribution over X. Since Ao outputs fixed distribution, by the bounded ball assumption, for h ~ À and arbitrary adversary function g.
Pr (A succeeds] 80%. hrd
8

---

But AA behaves identically to Ao until it sees its first nonzero Thus, 99% - Pr[A succeeds] < Pr[AA succeeds] + Pr[A sees non-zero y]
and so
Pr[A sees a non-zero y] 19%.
Since A behaves like Ao until the first nonzero, we have
19% I Pr[A sees non-zero y]
Pr[AA makes query z with ((z =1]
[uumbrr queries x by AD with y(x) 1]
m E IE E [[(x)]] A
As an initial note, observe that B,,,, [x)) - Ex [n[][[]]]=] = r(x) so
E [r(x)] 0.19
x~a
m
Thus the lemma statement holds for O.
Handling 77 0. Consider the behavior when the adversary's ' function g X + [0, satisfies EgwD, [())((())] (==)__9(ZZ)(())) S n/10. We denote the class of all adversary satisfying this condition as G. We have that
E kma
E [o(x))(>)]]
E [g(z)r(z)] S n/10.
I-D,
Let E,, denote the event that EEnD [g(x) < so Pr[E,] S 10%. Furthermore, the adversary is designed such that under E,, By [y(v(x)) = h(x)(1 ((r) for every x. Therefore:
0.19 < Pr[Ao makes query æ with y(r) = -]
S Fx Pr [Ao makes query with y(ι) = 1 n Ex
S 0.1 + E. [uNuber queries x by Ao with y(x) and F..
0.1 mE E h
E, E E ((:)) aaa
y
0.1 + m E
E [1(x))1 s(x))]
h
0.1 + m E
(1(h())[11-9(22)))
-
0.1 + m
E
((=))(11-g(())
zrd
Thus
9
max min E [r(=)(1 9(x))) 100m 9EG zn
over all distributions q and functions g X - [0, 1] satisfying (.-D n/10 10. We now try to understand the structure of the 9.9 optimizing the LHS of (4).
Let g" denote optimizer of the objective. First, show that the constraint is tight, i.e. EzwD, ( (x))(()] = 1//0.. Since increasing g improves the constraint, the only way this could not happen is if the maximum possible function, g(x) for all lies in G. But for this function, the LHS of (4) would be 0, which is a contradiction; hence we know increasing to improve the objective at some point hits the constraint, and hence EL-D, [g"(x) (x)r(z) n/10.
For any g, define Tq 2 0 to be the minimum threshold such that
r
r(x)
v(e) x
< 1 10.
Dr
>To
and define 9q by
9(w)
xx(2) Tq
9g (x)
[x Tq
g(a)
0
Dx
g(m)
< Tq

---

where E [0, is chosen such that BewD,1((2)9((1 1/10;; such an always exists by the choice of Tg. For any g, we claim that the optimal g in the LHS of (4) is D4- needs to maximize
(
(x(x) (1))(())
B>Dx
subject to a constraint on Dx (r())g(x)]; therefore moving mass to points of larger g(a) always improvement, and 94 is optimal.
2x(#) is
We now claim that the q maximizing (4) has max Dx
g(x) = Tq. not, some has (x Tq.
Then 3g (z²) 1, so the x' entry contributes nothing to E En (1 9y (x))]; thus decreasing g(x)
halfway towards Tq (which wouldn't change Sy), and adding the savings uniformly across all g(x) (which also doesn't change 94) would increase the objective.
So there exists satisfying (4) for which Pr
T4 = O. and therefore the set T =
Dx(=)
((x) (x(#) [ satisfies Edx (r(x)luer) 2 n// 10 and a 99 minimizing (4) is
(x(x)
1
LET
10 EDx ((())
Therefore
g(x) r(x) "
E [r(x)g(()) xma
w~Dx Dx(x)
10 ED, [r(z)
I !l
max ((x)
10 x Dx(x)
and so by (4),
E [r())]
7
max q(x)
2~4
10 x
(x
100m
as desired.
4 Conclusion
We have given an algorithm that solves agnostic active learning with (for constant 5) at most an O(log H)) factor more queries than the optimal algorithm. It is NP-hard to improve upon this Olog H factor in general, but for specific cases it can be avoided. We have shown that threshold functions, i.e. binary search with adversarial noise, one such example where our algorithm matches the performance of disagreement coefficient-based methods and is within log log factor of optimal.
Acknowledgments
Yihan Zhou and Eric Price were supported by NSF awards CCF-2008868, CCF-1751040 (CAREER), and the NSF AI Institute for Foundations of Machine Learning (IFML).
References
Mohammad Azad, Igor Chikalov, Shahid Hussain, Mikhail Moshkov, and Beata Zielosko. Decision Trees with Hypotheses. Springer International Publishing, 2022, doi: 10.11077998-33031--888 URL attps:///oo:
Maria-Florina Balcan, Alina Beygelzimer, and John Langford. Agnostic active learning. In Proceed- ings of the 23rd international conference Machine learning, pages 65-72, 2006.
Michael Oen-Or and Avinatan Hassidim. The bayesian learner is optimal for noisy binary search (and pretty good for quantum as well). In 2008 49th Annual IEFE Symposium on Foundations of Computer Science, pages 221-230, 2008. doi: 10.1109/FOCS..008..5
10

---

Alina Beygelzimer, Sanjoy Dasgupta, and John Langford. Importance weighted active learning. In Proceedings of the 26th annual international conference on machine learning, pages 49-56, 2009.
Alina Beygelzimer, Daniel Hsu, John Langford, and Tong Zhang. Agmostic active learning without constraints. Advances in neural information processing systems, 23, 2010.
Marat Valievich Burnashev and Kamil' Shamil' evich Zigangirov. An interval estimation problem for controlled observations. Problemy Peredachi Informatsii, 10(3):51-61, 1974.
David Cohn, Les Atlas, and Richard Ladner. Improving generalization with active learning. Machine learning, 15:201-221, 1994.
Sanjoy Dasgupta. Analysis of a greedy active learning strategy. Advances in neural information processing systems, 17, 2004.
Sanjoy Dasgupta. Coarse sample complexity bounds for active learning. Advances in neural information processing systems, 18, 2005.
Sanjoy Dasgupta, Daniel Hsu, and Claire Monteleoni. A general agnostic active learning algorithm. Advances in neural information processing systems, 20, 2007.
Dariusz Dereniowski, Aleksander Lukasiewicz. and Przemyslaw Uznanski. Noisy searching: simple, fast and correct. CoRR, abs/2107.05753, 2021. URL https: /tattss//arxiv... http://waxvvvaaaaaaaa// 2207 00553..
Irit Dinur and David Steurer. Analytical approach to parallel repetition. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 624-633, 2014.
Steve Hanneke. A bound on the label complexity of agnostic active learning. In Proceedings of the 24th international conference on Machine learming, pages 353-360, 2007a.
Steve Hanneke. Teaching dimension and the complexity of active learning. In International conference on computational learning theory, pages 66-81. Springer, 2007b.
Steve Hanneke. Theory of disagreement-basel active learning. Foundations and Trends in Machine Learning, 7(2-3): 13--3):111-00, 2014.
Steve Hanneke and Liu Yang. Minimax analysis of active learning. J. Mach. Learn. Res., 16(1): 3487-3602, 2015.
Tibor Hegedús. Generalized teaching dimensions and the query complexity of learning. In Pro- ceedings of the eighth annual conference Computational learning theory, pages 108-117, 1995.
Matti Kääriäinen. Active learning in the non-realizable case. In Algorithmic Learning Theory: 17th International Conference, ALT 2006, Barcelona, Spain, October 7-10, 2006. Proceedings 17, pages 63-77. Springer, 2006.
Richard M. Karp and Robert Kleinberg, Noisy binary search and its applications. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '07, page 881-890, USA, 2007. Society for Industrial and Applied Mathematics. ISBN 9780898716245.
Julian Katz-Samuels, Jifan Zhang, Lalit Jain, and Kevin Jamieson. Improved algorithms for agnostic pool-based active classification. In International Conference on Machine Learning, pages 5334- 5344. PMLR, 2021.
S Rao Kosaraju, Teresa M Przytycka, and Ryan Borgstrom. On an optimal split tree problem. In Algorithms and Data Structures: 6th International Workshop, WADS199 Vancouver, Canada, August 11-14, 1999 Proceedings, pages 157-168. Springer, 2002.
Hyafil Laurent and Ronald I. Rivest. Constructing optimal binary decision trees is np-complete. Information processing letters, 5(1):15-17, 1976.
David D Lewis. sequential algorithm for training text classifiers: Corrigendum and additional data. In Acm Sigir Forum, volume 29, pages 13-19, ACM New York, NY, USA, 1995.
11

---

David D Lewis and Jason Catlett. Heterogeneous uncertainty sampling for supervised learning. In Machine learning proceedings 1994, pages 156-156. Elsevier, 1994.
Robert Nowak. Generalized binary search. In 2008 46th Annual Allerton Conference on Communica- lion, Control, and Compuling, pages 568-574, IEEE, 2008
Robert D Nowak. The geometry of generalized binary search. IEEE Transactions Information Theory, 77602),7893-790, 2011.
Burr Settles. Active learning literature survey. Computer Sciences Technical Report 1648, University of WisconsinnMMddion 2009.
Joel Tropp. Freedman's inequality for matrix martingales. 2011.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018.
12

---

A
Query Complexity Upper Bound
In this section present the whole proof of the query complexity upper bound of Algorithm as stated in Theorem 1.1.
A.1 Notation
We remind the readers about some definitions first. Remember that w; denote the weight of
(h( hypothesis h in iteration and (,, Eves "i(h") for some S H denote the proportion of
in S. We view A distribution of hypotheses in S so for h & S, s O. For set S S H of hypotheses, we define w,(S) : Enes w(h) and (x(h) = (h..
Define r (1) Pra~A (b(x)) + h (x)), and rx(x) minye(o.1) Pra-a(h(1) + w). so ra(2)
min(rx, (z), Tx,N-(2)) (z)).
Define
1 {x((h) (h) = v (),( + ==/ (Am
1
2
h 5
(1(h))
1- PriNA [hES]
h $ 5
(5)
T-PEANA, WEST
as the "capped" distribution in iteration i. Finally, for notational convenience define Ti, = TA Tr,S, S and Fi, = T 'x,s"" The main focus of our proof would be analyzing the potential function
{ 0
log (c(h") + log (h")) h" & S:
<i(h")
h- E S,.
where h" the best hypothesis in H. We would like show that Φ++1 Φs (h²) growing at proper rate in each iteration. We pick S; to be an expanding series of sets, i.e., S, S S for any 2 However, the change of the "capped" set S, makes this task challenging. Therefore, we instead analyze the following quantity defined as
log
11LL,N (h") Aar1(h") log At,As,, (h*) A((h")
ht $ S. he S.,
(1hh)
and (1+1 (it))) A.(h") + log 211. (4')
h & S Further, we define vhe(h") == A (h') Eiek A, (h*) so by definition @& (h") = do (h') + th (h*) + Ei log A4ti, (N)) if h" & S In the following text, we will drop the parameter h²* when the context is clear and just use di, A and db instead.
(1)
A.2 Potential Growth
We will lower bound the conditional per iteration potential increase by first introducing a lemma that relates the potential change the optimization problem (3).
Lemma A.1. Assume that err(h" I then any set S of hypotheses containing ht and query
distribution q, we have
E log S++), (h,s(h))
-2.3 max ((x)
Ft 2 0.9a
E a00
[r,s,
Dx(x))
for a S 0.2. Moreover,
ActI,s(h")
max 0,
F.
s E ang ang
(z)
(1+s(h+)
Proof. For notational convenience, define F(z) = TT,...
Observe that
A1,s(h() w.(h') Eres W1+1,s(h)
wi(h')
Wi+1,s(h) wi,s
\++1,s(h*) w++1(h*) Enes (i)
wi+1 (1i*) andis
13

---

Let p(x) = Pr Pry-((1xx)U # h (x)) denote the probability of error if we query so
R
[p(x)) m.
x~Dx
Suppose we query a point z and do not get an error. Then the hypotheses that disagree with h" are downweighted by an é factor,
(h,s(h")
E
(e+ -
-1)ooo)))) 1 (1
(1- 11---------0--0-
A1+1,((h*)
On the other hand, if we do get an error then the disagreeing hypotheses are effectively upweighted by e
,rss(h)) = + (c -c)-))((())
1+11,((1*)
Therefore
log \h+1,s(h")
E y|
(hh)(h*) Fi
- (1 p(x)) log (1 (1 (1 -1-11-- - p(x) log (1 + (E" 1)F(x))
(6)
(1 p(z))(1 c -)((()) - p())(=
(1 -)((o) p(a)F(x)(e -
Using that 7(x) S 1, we have
(h+),((h))
E log
F$ 21 - a E [r(z]] - -c----0
E [p(x)]
(h+)
20d
2 0.9a E [((x) - 2.3p(x)]
201
where the last step uses a $ 0.2. Finally,
g(x) (x(x)
S max ((x)
E [p(x)]
E zx
p(x)
zmm
Dx
This proves the first desired result. For the second, note that if we query H, then conditioned on Fi
max { (0.10g si+1, 00
with probability p(x),
(1,)(h()
log((1 (1-e-9)F(x)) otherwise.
Since log(1 + (1- - e(-((())))) s (1- (1-e- ()(()) S af(x), taking the expectation over æ gives the result.
The above lemma, combined with Lemma 2.1, proves the potential will grow at desired rate at each iteration. But remember that Lemma 2.1 requires the condition that no ball has probability greater than 80%, we need to check this condition is satisfied. The following lemma shows that if we cap the set S, then the probability is not concentrated on any small balls.
Lemma A.2. In Algorithm I, for every iteration St is such that radius ca7) + CsE ball has more than 80% probubility under Xi,S:
Proof. If S, Si-1, then by the construction of S;, there are no radius C47) + CsE balls have probability greater than 80% under X,,s, X,,,, Otherwise, we have S,-1 * S; and ball B(, 3ca + 3cgE) is added to S: in this iteration. We first prove useful claim below.
Claim A.3. Ifa ball B' (μ, 3cm 3c5e) added to S, at some iteration cmm 0.6.
Proof. If B' is added to at the iteration i, then there exists some ball with radius Ca7) + C3 such that )i,s,_, 2 0.8. If a set of hypotheses gains probability after capping, the gained probability comes from the reduced probability of other hypotheses not this set. Therefore, the gained probability of any set is upper bounded by half of the probability of the complement of that set before capping. This means X; (D) 2 0.6 because otherwise after capping Se,s;-1 (D) < 0.8, which
contradiction. As result, X, (BBu, can) css)) > (D) 2 0.6.
D
14

---

20m max ((x) By Claim A.3, the probability of B(,, cayy esE) is at least 0.6 over the uncapped distribution d₁. So any ball not intersecting B(u, can C3E) has probability at most 0.4 before capping. After capping these balls will have probability no more than 0.7. At the same time, any ball intersects Bi,, (47) + (5E) would be completely inside Bu, 3r4y + 305E) so its probability would be most 0.5 after capping.
L
Now we are ready to apply Lemma A.I and Lemma 2.1 except one caution. Remember that in the beginning of the algorithm, compute 217-packing H' S H of the instance. From the well-known relationship between packing and covering (for example, see Vershynin [2018, Lemma 4.2.8J), we have |H'| & NN (H, 77). Every hypothesis in H is within 27 some hypothesis in H' there exists a hypothesis in H' with error less than 31.. This means that the best hypothesis h" E H' has error 3n instead of 17. The following lemma serves the comnrstonn of the proof of the query complexity upper bound, which states that the potential grows at rate Ω
in each iteration.
Lemma A.4. Given C4 2 300 and err(h") S 3n, there exists sampling distribution such that
((x))
[F E [A) 2am max
if h St:
Dx m (H, Dx. can CSE 2n,, 100
as well as | S always and Var[A. S a (
Proof. For the sake of bookkeeping, we let m m (H, Dx Ca7), - 217. the following text. We first bound the expectation. By Lemma A.1 applied to E H, H \ St with 3r), we have
99 in this proof and
100
q(x) 2 (x
(r,,,na()) + (.HN 13.8n max g(x) xnnq
20m max E [
20.9a
(x(x)
I Dx Dx(x)'
where g the query distribution of the algorithm iteration i. Now, by the definition of
1
1
X /
we have for any that
1 (ren- (x) + (..
(r.)..((x)
and thus
q(x)
E B 2am max
Dx (z)
g(x)
2am max q(x)
> 1.8a
E Fr.s h (x)) 6.9m max
(x))
Dx (x)
((x)
> 1.8a
E Fr.s, (x) 8. max 220
Dx(x))
Algorithm chooses the sampling distribution q maximize Ezzg [ri,s, (1)) 20 ll max, (x
o(x)
(ri,s, (x)) 15g max, (x because ea 2 300. By Lemma A.2, Nr,s, over H' has no radius-
q(x)
(cin) + csE) ball with probability larger than 80%, so by Lemma 2.1 satisfies
E 115 max q(x) zrd
20 max g(x) Dx(x) m (H', Dxx C.T, C55, 100
> E (T.s, 200
(x)]
(x(x)
99
Because H' C H is maximal 2rc-pac, every hypothesis in H is within 2n of some hypothesis in H'. The problem H, Dx, Cat), 655 21); 106 is harder than the problem (H', Dx Car), 65e, 100 because we reduce the latter to the former by simply adding more hypotheses and solve
15

---

it then map the solution back by returning the closest hypothesis in H' Hence, m 2 m (H', Dx, c47) OsE, ) Therefore.
g(x) (x 2 1.8a
E (.,, 8a max ((x) Dx(x)
a
E FAFE 2am max
m
now bound the variance. The value of A; may be positive or negative, but is bounded by A S
Thus
VarlA S E A
S <aB|||||
By Lemma A.1 and (7) we have
B|JA, Fi = E|2 max (A, 0} [
E (x)] - 1.8c E Ft.s, (z)] 8.1n max g(x))
$ 4a
Dx(x)
E [r,s,, (1)) + 6.7 g(x)
< 2.2x
Dx(x)
2.2a
((x)
((x)
<
E | F + 2.20 6.9n max
+ 2.2a 6.7n max
1.8a
(x(x))
(x(x)
+ 300m max ((x)
$ 1.3
Dx (x)
Since Egngl 1e [i]
2007) max Dx m 2 0, we have
[z) 2 1
max q(x) S E [A]F))
Dx(x)
2a a~g
and thus
A.3
Concentration of potential
We have showed that the potential will grow 52 -- per iteration, but only in expectation, while our goal is to obtain high probability bound. Let pk Eier [[; Z k/m", then
E [(t px) - (1x-11 p4- () F = E [ebk E [.)
(ax - pk-1) 0.
Apparently ldb pal is upper bounded, so the μ4 is supermartingale. To show a high probability bound, we will use Freedman's 's inequality. A version is stated in Tropp [2011]. We slighted modify so it can be applied to supermartingale as the following. (XXX Not sure if the following is correct. I can't find a version of supermartingale.)
Theorem A.5 (Y, : 0, 2.... that is adapted to the filtration Fu C Fi C F2 .... C F with difference sequence (Xg = 1.2.3..... Assume that the difference sequence is uniformly bounded:
(Freedman's Inequality). Consider
real-valued supermartingale
X S R almost surely for k: = 1,2,3,
Define the predictable quadratic variation process of the supermartingale:
k W = Σ 1=1
[x3155111 for k 1,2,3.
Then, for all and 2² >
t2
Pr (3k 2 0: Yv < -t and W s 02) < exp ( + R1/3
16

---

Then we can prove high probability bound as the following.
H Lemma A.6. With probability 6. oi for some = O (m' log x
so ht E S...
Proof. Remember we have that
S1 (h*)
Φb = Φo + 4/k
Elog
log
ick
Since S,-1 2 S₁ for all i, S (h*)
ss (h*) hf Si+1, we have
S441
0o + th
if Sk.
Let K = (mmm log / Let's assume by contradiction that ox 0 for for, then h² $ S; for
i < K. We know by Lemma A.4 that
k
P4 = B|A
272.
and that Σick Var [A.] S Hil by picking a small enough. Moreover, | S always. To use Freedman's 's inequality, let's set the RHS
f2/2 0² R2/3
exp
S 6.
Solving the above quadratic equation, solution is that t 2 log 8 + R2 log + 20 log
Let's substitute in R and 0² = Eick Var;- with 1 - 8 probability we have for any k O(m" log }) that
1
1
v/ 2 Pk
log
+
Var(A,) (A;) log
log
8
1
9
log
8
+
1 log
3
log
V2a
1
a
1 5
2
max
3
log
5' V
14 log
0
3
log
1
2
2V
k
m"
The second last inequality is because the first term outscales all of the rest. Since K
O m log ) we have
v 2 2 2og [
with - probability. Then ox 2 do + thy because do 2 log 2ा 2 - log II and this contradicts ht & SK- Therefore, with probability at least - 5, h E Sx and by definition, de = 0 for some i < K as desired.
A.4 Bounding the Size of [C]
So far we've shown that after O mm log [ thing we need to prove Theorem 1.1 is that with high probability, C is small, which is equivalent show that not many balls will be added S, after O mm log ! iterations. To show this, first need to relate the number of balls added to S; to 1/s. Let &, denote the number of ervors h² made up to iteration i (and set E, = E h² E S.) and NG, denote the number of balls added to S up to iteration (again set M; =N h" E S.).
iterations, h² will be included in the set S,, The last

---

Lemma A.7. The following inequality holds for every i:
N S 5(4; + 20E2) + 1.
Proof. We divide the iterations into phases. A new phase begins and an old phase ends if this iteration new ball is added to the set S,. We use ....... Pk: for k S i to denote phases and .1,.... 4 to denote the starting iteration of the phases. We analyse how the potential changes from the phase Pj to the phase Pj 1--1-1 Let's say the ball B2 (12, 3c47) + 3csE) is added at the beginning of Pj+1 and B1 = (M1, 3C4r) + 30s5) is the ball added at the beginning of pj- Then the ball B/ = (12 Cal) + c5E) and the ball Bi = (11, + are disjoint. Otherwise, B3 C B1 so B2 would not have been added by the algorithm. At the beginning of Pj. B3 has probability no less than 0.6 by Claim A.3. Therefore, B2 has probability no more than 0.4. Similarly, at the beginning of Pj+1. B22 has probability at least 0.6 by Claim A.3. Since during one iteration the weight of a hypothesis cannot change too much, at iteration 2-+1
B3 has weight least 0.5 by picking small enough. Therefore, 0.5 have log A1,+1- 1 (B:) log Ar. (B4) 2 log 0.4 5. Moreover, note that S; does not change from iteration 2 to iteration 1 - by the definition phases. Now we compute
8441 1
\11+1-((h") + log A (11) X1 (h²)
A log
M,, (h*)
t
Wi, wi,11-1(1"))
Enen Wi, (h)
+ log Wi W1z11-1(1"))
wi, (H Si,)) Wiz+1- (H) Si
llog-
wi, (h²)
Enen 1isti-1(h)) (h)
Wi, (hr)
The change of the weight of h² is
Wis Wis11 aEEs W/y (h*)
where Ep, is the number of errors ht made in Py. Consequently,
4
log w4, (H, (1g)) EnEN 11(4) wi 1 \ (Si,)
ΣNEH Wiy (1)
A -20E, log
1 2 22 + 5
The last step above comes from
log Enen Wiy (h)
Enen, (1)t
Σnew Wi, (h)
log X1 (B²)
1
ΣnCH W 11)11-1(h) 2 loog
ENEBY Ws, (h) ΣnEn Wi; Wit
\1s (B2)
5'
and
log Wig (H \, Siy) 01 (H) Si,)
2 0
because the weight w(h) only decreases. Summing over all phases j and we get
v 2 -2E, (N,-1)
Since i may not exactly be the end of phase, the last phase may end early we have N₁ 1 instead of Ag. Rearrange and the proof finishes.
We have already bounded th, so we just need to bound & in order to bound Nr by the following lemma.
Lemma A.8. For every k, with probability at least -
1 w'n + V2 log 2)
Ex <
a
18

---

Proof. Let q be the query distribution at iteration i 1 and p(xx) be the probability that 2' is corrupted by the adversary. Then the conditional expectation of & E
((x) ((x))
17 max g(x)
E EE E Pr [hr (x) is wrong] E [o(z]] z
E aND
p(x)
Dx
Then if h² $ S. from Lemma A.4
E|A - 201(E; - E1-1) 2 EAAAA 20m max g(x))
2 1
Dx (z)
m
Therefore, E/a (E: E [F:] S 1 [F) and E A a(E; - Fi 2 =2 B [i). This
means that V/a ac 1/2 uu is supermartingale. We then bound Var [ - a(E - E,-1 Fi]
Note
that A - a(E; - 1,- I 2a, so
Var A - a(E; - E () s E (A: - a(E: - E,-1) F.
S 2a B| - a(E; - -
Furthermore,
E E|A; a(ε; E [J S + on max g(x)
x Dx(x)
As result,
BIAMA on max max g(x)
VarlA: - a0, - E 2a
x Dx(x)
S 2a
BBJA,IF [[AAF
3a EE [A
$ a E [
By picking a small enough, Eick Var A a(E; { S 1 g/k. Moreover,
I ---at a(E; - E,-1) S 2a always. Therefore by Freedman's 's inequality, with - 5 probability we have for any that
2 2
1
2a + 2 Var A a(E; - E1-1) log g 3
4h - a 2 pk
log"
log 5
9
5
ick
2
1
1
1
2a
1
PA
9
log
2
+
UR
log
8
3
log
2
2/2
20
1
V2
2a
1
P max
log
log
log
3
8
V2 log
V2
2a
1
P
max
log
8
2
V2
1
1 Pk 2 log
2
8
2 log 8
Rearrange and we proved the lemma.
Combining Lemma A.7 and Lemma A.8, we can show C' is small with high probability as the lemma follows.
Lemma A.9. For O ( log ) with probability at least -25, h E Sa and |C| s
O (log [
at iteration k.
Proof. By union bound, with probability at least 26, Lemma A.6 and A.8 will hold at the same
time. This means h² is added to Sg. By definition, 0 2 die 2 do + t/k, so t/a S 2 log H/. Therefore,
by Lemma A.7 and A.8, the number of balls added |C| is O (log) H + log )) = (log 8
[ O
19

---

A.5 Putting Everything Together
We proved that after O (m* log 5 [ iterations, h" E St and small with high probability. Hence, running the stage two algorithm return desired hypothesis will not take much more queries. We are ready to put everything together and finally prove Theorem 1.1.
Theorem 1.1 (Competitive Bound). There exist some constants 01, and 03 such that for any instance (H, Dx. n,E,6) with c17), Algorithm solves the instance with sample complexity
99
+ log 2
log [H, D
m mHH, me,0)
m²
ese, 100
and polynomial time.
Proof. Let's pick C1, C1, as in Theorem 2.3 and pick the confidence parameter to be 3. Then by Lemma A.9, with probability - 3. the first O (log !n1 ball added to S, will contain h. Since each ball added to C' has radius 3c17 + 3cys, the best hypothesis in C' has error (3 + 3c1) + 3c By Theorem 2.2, with probability 1 3. the algorithm will return hypothesis with error (9 - 9c4)1 + 9cp5 I 1) + E. Therefore, by union bound, the algorithm will return desired hypothesis with probability 1 - 5. This proves the correctness of the algorithm.
26
The stage algorithm makes
m H,,x, cat, OgE - 2n,, 100
99
log
S m² HH,xx, call 7 E,
Cs
99
log
M
2
100
The stage two algorithm makes O (IC) (.) queries by Theorem 2.2. Note that C' is canl ese-packing because the center of added balls are least c47) eg away, so m² (H, Dx ; n. 2 100
queries.
99
Z log [C). Since |C] S log ||I by Lemma A.9, stage two algorithm
takes O ((m* (H, 2 55, 99
100 ) + log })) log queries. Picking C2 = C12 C3 = 2 we get
the desired sample complexity bound.
To compute the packing at the beginning of the algorithm, we need to compute the distance every pair of hypotheses, which takes 0( X time. Computing in each round takes O(H)) X time and solving the optimization problem takes O(1 X 1) time. Therefore, the remaining steps in stage
one takes O (m | log [#! time. Stage two takes O log |H| log log !!I
time. Therefore,
the overall running time is polynomial of the size of the problem.
Similarly, we can prove Theorem 2.3, which is a stronger and more specific version of Theorem 1.1. Theorem 2.3. Suppose that Dr and H are such that, for any distribution X over H such that no radius-(ca)) + o5=) ball has probability more than 80%. there exists distribution q over X such that
E [x)r 200
C4 max
q(x)
2 B
20 (x(
for some 3 > O. Then for E 2 C17, e1 2 300, cs = 1o and c 2 90cc, let N
((H be the size of an n-cover of H. Algorithm solves (n,,,d) active agnostic learning with O log N o + log N & log logN) samples.
1
Proof. By Lemma A.9 (with m² replaced by 1/2 and setting confidence parameter to { after O log queries, with probability at least 1
3 a hypothesis C' will be within c47 + e5 to h" and |C| O (log )) From Theorem 2.2, with probability at least 1 3... stage two algorithm then outputs hypothesis h that is 9c.y + 9css from h' err h 9c17 993E 1 by N the choice of the constants. The stage two algorithm makes O (log
26
log N ) oor
queries. Overall, queries and succeeds with probability least
log
the algorithm makes O (1 log NN + log XX2 log log 4
1 - 8.
20

---

B Query Complexity Lower Bound
In this section we derive a lower bound for the agnostic binary classification problem, which we denote by AGNOSTICLEARNING The lower bound is obtained from a reduction from minimum set cover, which we denote by SETCOVER. The problem SETCOVER consists a pair (U. S), where U is ground set and S is collection of subsets of U. The goal is to find set cover C S such that Usec S = U of minimal size |C]. We use K to denote the cardinality of the minimum set cover.
Lemma B.1 (Dinur and Steurer [2014], Corollary 1.5). There exists hard instances SETCOVER-
HARD with the property K 2 log [U] such that for every y O, is NP-hard approximate SETCOVERHARD to within (1 7) In |U].
Proof. This lemma directly follows from Dinur and Steurer [2014, Corollary 1.5]. In their proof, they constructed hard instance of SETCOVER from LABELCOVER. The size of the minimum cover K 2 [V] = Dn1 and log U = (D + 1) In I K. So the instance in their proof satisfies the desired property.
Then we prove the following lemma by giving ratio-preserving reduction from SETCOVER to AGNOSTICLEARNING.
Lemma B.2. If there exists a
deterministic a-approximation algorithm for there exists deterministic 20-approximation
AGNOSTICLEARNING HH, Da, 3 X अ| - algorithm for SETCOVERHARD.
Proof. Given an instance of SETCOVERHARD, for each s E S, number the elements u E s in an arbitrary order; let [s,, u) denote the index of in s's list (and padding to the left with the extra bit). We construct an instance of AGNOSTICLEEARNIN as the following:
1. Let the domain X' have three pieces: U. V := {(s,)) E S,j E [1 + log [s]]], and
= =1 (1,...,,log [,,, an extra set of log UU] more coordinates.
2. On this domain, we define the following set of hypotheses:
(a) For U. define hy which only evaluates on u E U and on (s, E E Vf and the j'th bit of (2,(s, - 1) is
(b) For d E D, define ha which only evaluates 1 on d.
(c) Define ho which evaluates everything to 0.
3. Let Dx be uniform distribution over X' and set 1 उ/े and -/22 Set d _
7,, so err(h*) = 0. First we show that m" H. Das 3 x x| a[оा < K + log |0% Indeed there exists a deterministic algorithm using K log U queries identify any hypothesis with probability 1. Given smallest set cover C, the algorithm first queries all (s, 0) E V for E C. If ht = h, for some u, then for the E S that covers u. (s,0) 0) will evaluate to true. The identity of can then be read out by querying (s,j) for all j. The other possibilities-hu for some d or Q-can be identified by evaluating on all of 1) with log U queries. The total number of queries is then at most K + log [U'] in all cases, so m < + log [U] < 2K.
Any two hypotheses satisfy |h_ - hall 2 X
We now show how to reconstruct good approximation to set cover from good approximate query algorithm. We feed the query algorithm y for which it queries (s,j) for some j. Also, every time the algorithm queries some u E U, we add an arbitrary set containing u to Then the size of C' is at most the number of queries. We claim that C' is set cover: if C' does not cover some element u, then h2 is zero on all queries made by algorithm, so h, is indistinguishable from ho and the algortihm would fail on either input ho or hy. Thus if A is deterministic a-approximation algorithm for AGNOSTICLEARE recover a set cover of size at most amm < (K + log (U]) & 2a so this gives deterministic 2n-approximation algorithm for SETCOVERHARD.
every query it makes, and let C' be the set of all
we will
21

---

Similar results also holds for randomized algorithms, we just need to be slightly careful about probabilities.
Lemma B.3. If there
algorithm for 1 x 3|x ((8)) there exists randomized 20-approximatton
exists
randomized
AGNOSTICLEARNING H,
algorithm for SETCOVERHARD with success probability at least 2
Proof. We use the same reduction as in Lemma B.2. Let A an algorithm solves AGNOSTICLEARNING 3
4|2 To obtain set cover using A, we keeping giving A label 0 and construct the set C' as before. Let qc be distribution over the reconstructed set C. Assume that by contradiction with probability at least 3. C' is not a set cover. Then, with probability at least 1/3, there is some element such that both h, and hgg are consistent on all queries the algorithm made; call such a query set "ambiguous".
Then what is the probability that the agnostic learning algorithm fails on the input distribution that chooses h" uniformly from H? Any given ambiguous query set is equally likely to come from any of the consistent hypotheses, so the algorithm's 's success probability on ambiguous query sets is at most 1/2. The chance the query set is ambiguous is least 3//r| 3/ chance that the true h" hg and the query set is ambiguous, and at least as much from the other hypotheses making it ambiguous. Thus the algorithm's is fails to learn the true hypothesis with least उ/स probability, contradicting the assumed T
failure probability.
Therefore,
of size at most 2a K can be recovered with probability least using the agnostic learning approximation algorithm.
The following theorem will then follow.
Theorem 1.2 (Lower Bound). It is NP-hard to find a query strategy for every agnostic active learning instance within an clog H for some constant > 0 factor of the optimal sample complexity.
Proof. Let's consider the instance of set constructed in Lemma B.2. Let 0.1 and note that
log H S 0.49 log 2
[|] !! If there exists polynomial time 0.49 log 2 approximation algorithm
for the instance, then there exists a polynomial time 0.98 log | < 0.98 log [U] approximation algorithm for SETCOVERHARD, which is a contradiction to Lemma B.I.
22


Reviews:
[{"review_id": "XJraDWom19", "reviewer": "Reviewer_wAoo", "summary": "The authors provide an algorithm for learning in the presence of agnostic noise. The algorithm finds a hypothesis that gets error $O(\\eta)$ where $\\eta$ is the noise parameter. The algorithm requires querying specific points, so it uses a stronger oracle than the standard active learning. The algorithm is possibly inefficient for many classes as it is polynomial in the number of hypotheses (or to the size of the cover). Their algorithm is optimal up to log factors, and they provide a lower bound showing that it is NP-Hard to improve this.", "questions": "N/A", "limitations": "No liomitations.", "rating": 4, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 2, "strengths": "This work provides a query-efficient algorithm with tight results (upper and lower bound) for the agnostic setting.", "weaknesses": "The setting in their analysis is not active learning but learning with queries which is a stronger oracle. So the title of the paper/abstract is misleading. In my opinion, active learning is a completely different model than the one the authors use. Also for examples the 41-46 lines, the papers there are for active learning and not for the model the authors analyze. I think the authors should be more clear about this. About the NP-Hardness result. This result makes sense when the $|H|$ is polynomial over $\\epsilon$ and the dimension. But almost always the $|H|$ is exponentially large, i.e., $d$-dimensional functions.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Definition of Active Learning\n-------\n\nYou appear to be concerned that we assume we know $D_X$ and can query\n$(Y | X = x)$, while some previous work defines active learning as:\ngiven all the $x_i$ in a dataset, pick a subset of them to see the\ncorresponding $y_i$.  However, in the limit of infinitely many\nunlabeled data points, these are equivalent: the set of all $x_i$\ngives us the distribution $D_X$, and we can sample any $x$ in our\ndataset, which means any $x$ in the support. So if we don't care about\nthe number of unlabeled examples, as the prior work also doesn't, then\nwe may as well assume our model.\n\nBounds on the unlabeled data complexity are a very interesting\nquestion which we intend to pursue in followup work.  It gets somewhat\ncomplicated, because the OPT also depends on the amount of unlabeled\ndata, so we believe focusing on labeled complexity makes sense.\n\n\n\nAbout the NP-Hardness result\n--------\n\nAs we discuss in the general response, at our level of generality one\ncannot avoid a runtime polynomial in $|H|$.  And without the\n$\\log |H|$ slack in number of samples, our NP-hardness result shows one\ncannot hope to avoid time *exponential* in $|H|$.\n\nFaster algorithms under structural assumptions on $H$ are a good\ndirection for future work, but our results here are the best one could\nhope for."}, {"review_id": "eDHgw3XcEQ", "reviewer": "Reviewer_LeWc", "summary": "The paper studies agnostic active learning by proposing a competitive algorithm that achieves at most a $\\log H$ multiplicative factor on top of the optimal query lower bound of $m^*$. While similar result was known for the realizable setting, this paper makes a step toward understanding the agnostic setting. As a complementary result, it also shows that it is NP-hard to improve the $O(\\log H)$ overhead both in realizable and agnostic settings.\n", "questions": "Can the author comment on the exact running time of the algorithm on each parameter, for example, $d, m, |H|, |X|, \\frac{1}{\\epsilon}$, (or any other important parameters)? \n", "limitations": "No concerns.\n", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper proposed a strategy that actively learns the target function in the agnostic setting with competitive sample complexity. Given that similar strategies only handle the realizable setting, it makes a significant contribution to the active learning problems in general settings. The proofs seem sound. The paper is well written.\n", "weaknesses": "The paper is clear in the description of the algorithm and the analysis of how it queries. However, the computational cost of the algorithm is vague. In Theorem 1.1, it claims that the algorithm runs in polynomial time, but it seems not so at least in the dimension parameter d.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Runtime.** We should give the runtime more precisely, and appreciate the comment.  The main cost is\nfrom checking if any $\\epsilon$-ball of hypotheses has 80\\%\nprobability, after each label seen.  Naively this takes about\n$O(|H|^2(|\\mathcal{X}| + m))$ time, because it takes $|H|^2|\\mathcal{X}|$ time to compute the\ndistances between all hypotheses and then $|H|^2 m$ time to try\nall the balls in all iterations.\n\nHowever, one should be able to optimize this by making that step\nrandomized and approximate.  This would make the analysis more\nannoying, but shouldn't change the result other than the constant\nfactors.  One could just sample $O(\\log \\frac{1}{\\delta'})$ random\nhypotheses, and $O(1/\\epsilon)$ random $x$, and see if at least 90\\%\nof the hypothesis pairs are empirically within $O(\\epsilon)$ of each\nother.\n\nWith this optimization, the algorithm should have an overall runtime\naround $\\tilde{O}(|H| m + m / \\epsilon)$: the first term is\nfor $m$ rounds of multiplicative weights over $|H|$, and the second term is\nthe optimized identification of heavy balls. Plus, if you want a net to improve the approximation from $O(\\log |H|)$ to $O(\\log |N(H, \\eta)|)$, however much time it takes to compute this net at the beginning (at most $|H|^2/\\eta$ with a greedy algorithm, but typically you would write it down explicitly for your hypothesis class).\n\nBut the analysis of this variant is a little hairy, and in our opinion\noptimizing the algorithm for generic hypothesis classes is not as interesting as getting much more significant speedups\nfor specific hypothesis classes."}, {"review_id": "NoQ85e24td", "reviewer": "Reviewer_YT5S", "summary": "This paper applied a multiplicative weight update /  generalized binary search style algorithm to solve agnostic active learning. It proposes a novel \"capping\" approach to the weight (over hypotheses) to ensure the potential function always grows by some amount, and it proves this amount is lower bounded by $\\Omega(1/m^*)$ where $m^*$ is the theoretical optimal instance-dependent label complexity. In the end, it shows that the proposed algorithm is competitive in the sense that its label complexity is at most, roughly speaking, $\\tilde{O}(m^* \\log |H|)$. And it also shows that removing the extra \"log(|H|)\" factor is NP-hard.\n\n--\n\nI've read the author's response. It addressed my major concern about related work so I increased my score to 7. I would encourage the authors to provide a comprehensive comparison with related works, including directly comparing bounds in different settings. I'm still not very convinced about the argument around computational efficiency, but that should not block this paper from being accepted.", "questions": "I would like the authors to comment on the weaknesses 1~3 I mentioned above.", "limitations": "n/a", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The proposed algorithm is a novel and nontrivial modification of the classical multiplicative weight update algorithm. The analysis from a competitive perspective also looks new to me in the setting of agnostic active learning.\n\n- I briefly checked the proof and they look sound to me.\n\n- Understanding the theoretical lower and upper bounds of instance dependent label complexity bounds for agnostic active learning is an interesting problem, and this paper makes a solid contribution by providing an algorithm whose label complexity is close to the optimal with an additional log(|H|) factor.", "weaknesses": "1. The additional factor of log(|H|) makes the label complexity of the proposed algorithm look not very strong to me: it can be worse than existing algorithms in many scenarios. The argument that getting rid of this factor is NP-hard does not look very relevant to me, since the main contribution of this paper is more on the information-theoretic side (the proposed algorithm is already by no means computationally efficient in the sense that it is polynomial in the number of hypotheses (or its epsilon cover at best) and the size of example space X), and it is known that even learning linear classifier without too much assumptions on noise is NP-hard.\n\n2. It would clearer if there were more discussion about how good the label complexity is by comparing it with known upper and lower bounds in different settings. Especially, there are a few papers (e.g. Hanneke, Steve, and Liu Yang. \"Minimax analysis of active learning.\" J. Mach. Learn. Res. 16.1 (2015): 3487-3602.) that give minimax analysis of active learning. I would like to see how your results compared with theirs. It would also be interesting if you could mention how the proposed algorithm works with noise assumptions (bounded, Tsybakov, etc.).\n\n3. This paper focuses on the case where $\\epsilon \\gtrapprox \\eta$, but it looks to me the case where $\\epsilon$ is smaller can also be interesting (though of course the label complexity won't be exponentially better w.r.t. 1/\\epsilon). It would be interesting if the theoretical results could cover that as well.\n\n4. This paper is overall clear, but some wordings are a bit confusing to me unless I check the detailed proofs. E.g., the proof sketch in line 149 - 154 (\"algorithm\", \"majority label\", \"inputs\", \"independent\").", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**1. On the relevance of time complexity.** We respectfully disagree that our contribution is mainly on the\ninformation theoretic side.  We view it as a structural observation of\nhow one can adapt a Bayes-inspired/multiplicative weights algorithm to\nget the frequentist agnostic learning guarantee.\n\nFrom an information theoretic perspective, one could do an exponential\nbrute force like \"consider all possible algorithms, and all possible\nsettings of labels, and find the minimax optimal algorithm\".  This\nwould work, optimally, without saying anything about the problem.  The\npolynomial restriction on the runtime forces us to learn something\nabout the problem.\n\nThere are interesting cases (e.g. noisy binary search) where H is\nsmall enough that the algorithm is feasible.  And beyond that, we\nbelieve it should be feasible to adapt our algorithm to some\nstructured infinite H; certainly multiplicative weights has been\nwidely adapted.\n\nSee our general response for more on why we think a polynomial\ndependence in this general problem is interesting.\n\n\n**2.  Related work.** See the general response for an example comparing our result to Hanneke-Yang '15.\n\nFor weaker noise models, the optimal complexity could be much smaller,\nand our algorithm won't always match it.  For example, suppose there\nis $\\eta/10$ probability mass on extremely informative points, with the\nrest of points being very uninformative.  In the agnostic setting, you\ncan't trust the informative points because the adversary probably\nmesses them all up, and so our algorithm won't sample them very often.\nIn the bounded noise setting, you should just sample those points many\ntimes.\n\n**3.  Another regime.** Yes, $\\varepsilon < \\eta \\ll 1$ could be interesting, where we suppose\ngiven existing bounds the goal would be to save a $\\Theta(\\eta)$\nfactor relative to the passive ERM.\n\nIt's a pretty different regime, though.  Consider the noisy binary\nsearch input (i.e., the hypothesis class is 1d threshold functions):\nfor $\\varepsilon > \\eta$, you do some robust binary search to home in\non the correct $O(\\varepsilon)$ region in $O(\\log \\frac{1}{\\eta})$\nqueries.  For $\\varepsilon < \\eta$, you start with this phase to get\nwithin $O(\\eta)$ of the truth, then do passive sampling over the\n$O(\\eta)$-size region of ambiguity.  With $N$ samples you will\ntypically get error $\\frac{\\eta}{\\sqrt{N}}$ on each hypothesis, so you\nneed about $O(\\frac{\\eta^2}{\\varepsilon^2} + \\log \\frac{1}{\\eta})$\nqueries.\n\nSo for noisy binary search there's two phases: one covered by this\npaper, and one that's no-longer-adaptive to refine $\\varepsilon$.  It\nseems plausible that general problems can be solved with such an\napproach."}, {"review_id": "9QwcVIWx3O", "reviewer": "Reviewer_orr4", "summary": "This paper studies agnostic active learning with a finite hypothesis space. The goal is to achieve a competitive query complexity with an optimal algorithm.", "questions": "The authors write $|H|$ multiple times implying that the hypothesis space is finite but also use packings / coverings of $H$. Do the results generalize to hypothesis spaces with infinite size?", "limitations": "See weaknesses.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 1, "strengths": "Interesting and important problem.\n\nThe approximation hardness based on Set-Cover is a nice addition.\n\n--- rebuttal comment ---\nAfter reviewers clarified concerns and added more results, I raised my score from 3 to 7.", "weaknesses": "The authors seem to be unaware of \"Minimax analysis of active learning\" by Steve Hanneke and Liu Yang [JMLR 2015]. Hanneke and Yang introduce the star number (a combinatorial dimension), which characterizes various active learning settings (realizable, different noise settings, including the one here) leading to near-tight lower and upper bounds. This seems to make the analyses here a special case of the achieved results. E.g., on a quick look Theorem 8 seems to have a similar competitive ratio as the proposed algorithms: roughly $d\\log (1/\\varepsilon)$ (with $d = VC$) instead of $\\log |H| \\geq d$.\n\nSimilarly, the discussed bounds $\\mathcal{O}(m\\log H)$ have been devised by Hegedűs, Tibor. \"Generalized teaching dimensions and the query complexity of learning.\" [COLT 1995] long before Dasgupta and Nowak.\n\nClaiming polynomial runtime is misleading, as one typically would mean polynomial in the instance space $X$ (or the sample, like in standard PAC) and not the hypothesis space $\\mathcal{H}$, as is here the case.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Related work.** We appreciate the additional references, which we will include in the\npaper and discuss.  But you are wrong about the relationship between our results and those of Hanneke-Yang '15. They actually give a much weaker\nform of ``optimality''.  See our general response for further\ndiscussion, and an example where their algorithm takes $H$ queries\nwhile ours takes $\\log H$.\n\n**Runtime.** For the runtime, also see our general response.  We can make the\ntheorem statement more explicit, if you feel it is misleading.\n\n**On $|H|$ vs a net, and whether H can be infinite in size.**\nThe *core* of our algorithm expects a finite hypothesis space, and\ngives an $O(\\log |H|)$ approximation.  But the algorithm does work on\ngeneral hypothesis spaces with infinite size: the very first step of\nthe algorithm is to find a $2\\eta$-packing of $H$, and thereafter only\nconsider this net.  So as long as you can compute a finite packing,\nthe algorithm applies."}]

Author rebuttal:
We thank the reviewers for their comments.  We would like to emphasize that we give the first algorithm for active agnostic learning that is competitive with the optimal algorithm for a given input (unlabeled data and hypothesis class).  There are a couple general points we would like to clarify, particularly about a prior minimax work by Hanneke and Yang which does *not* get this.

Relation to Hanneke-Yang '15
-------------------------

A couple reviewers pointed to the minimax analysis of Hanneke-Yang
'15, which we had missed.  Thanks!  The distinction is that the
Hanneke-Yang upper bound is close to the optimal complexity of the
*worst case $D_X$*, while ours is relative to the optimal complexity
of our actual $D_X$.  As a result, our algorithm can be *much* better,
as the following example shows:


Define a hypothesis class of $N$ hypotheses $h_1, \dotsc, h_N$, and $(N + \lg
N)$ data points $x_1, \dotsc, x_{N + \lg N}$, so for each hypothesis $h_j$:

 * The labels of the first $N$ points express $j$ in unary
 * The labels of the last $(\lg N)$ points express $j$ in binary

So, for example, when N = 16 then $h_6$ will have labels:

  00000100000000000110

  Now consider the realizable ($\eta = 0$) setting, and suppose that
  the $x_i$ are fairly uniform (e.g., min probability
  $\frac{1}{10 N}$) and $\epsilon = \frac{1}{20 N}$.  Then you need to
  identify $h_j$ exactly by querying the labels.

The obvious, optimal strategy is: query the last $\lg N$ bits and read
off the answer.  Our algorithm will basically do this, getting
$\Theta(\lg N)$ complexity.  RobustCAL, the algorithm analyzed in HY15,
will not: the first $O(N/\lg N)$ points it sees will be in the unary
region, and it will label almost every one of them, for $\Theta(N/\lg N)$
complexity.


So in this example, our algorithm is optimal at $O(\lg N)$, and our
general theorem's guarantee is $O(\lg^2 N)$ which is pretty close.
HY15's algorithm actually takes $\Theta(N/\lg N)$ queries, and their
general guarantee is $O(N \lg^2 N)$.


You might be confused: how can HY15 claim minimax optimality for an
algorithm with such poor behavior?  Their minimax lower bound on this
example is actually $N$.  This is because if $D_X$ happened to be
uniform on the first $N$ points (i.e., only the unary ones), you
really would need $N$ queries to recover the hypothesis.

But in active learning, you *know* your unlabeled data $x_i$.  So the
algorithm can see that it has access to the great points at the end
and should choose to query them.  Our algorithm does; RobustCAL and $A^2$
do not.


On Polynomial Running times
-----


A couple reviewers point out that usually $|H|$ is very large, so a
polynomial dependence on $|H|$ isn't great.  However:

* The problem setting we consider is fully general hypothesis classes.
Therefore the *input* has size linear in $|H|$, so one cannot hope to
avoid this dependence.

* There are interesting cases (e.g. binary search) where the
hypothesis class isn't huge, so the algorithm is feasible.

* The prior work in this setting (e.g. $A^2$) also depends polynomially
on $|H|$.

* Getting an *exponential time* optimal algorithm would be trivial by
brute force, so requiring polynomial time is what forces us to
understand something interesting about the problem.


We certainly agree that getting faster algorithms for more restrictive
hypothesis classes is an important line of future work.

Meta-review: This paper provides a general algorithm and approximation ratio analysis for the setting of agnostic active learning with an arbitrary hypothesis class. This is a significant contribution to the active learning field, though providing a simpler and more computationally efficient algorithm (perhaps some sort of oracle access to H that can be done in O(|H|) time) and an approximation ratio for the same \eta and \epsilon would be even more significant.
Decision: Accept (poster)