The Human-AI Substitution game: active learning from a strategic labeler
Authors: Tom Yan
Chicheng Zhang
Venue: ICLR 2024 poster (2024)
Keywords: active learning
strategic learning
Primary area: learning theory

Abstract: The standard active learning setting assumes a willing labeler, who provides labels on informative examples to speed up learning. However, if the labeler wishes to be compensated for as many labels as possible before learning finishes, the labeler may benefit from actually slowing down learning. This incentive arises for instance if the labeler is to be replaced by the ML model once it is trained. In this paper, we initiate the study of learning from a strategic labeler, who may abstain from labeling to slow down learning. We first prove that strategic abstention can prolong learning, and propose a novel complexity measure and representation to analyze the query complexity of the learning game. Next, we develop a near-optimal deterministic algorithm, prove its robustness to strategic labeling, and contrast it with other active learning algorithms. We also analyze extensions that encompass more general learning goals and labeler assumptions. Finally, we characterize the query cost of multi-task active learning, with and without abstention. Our first exploration of strategic labeling aims to consolidate our theoretical understanding of the \emph{imitative} nature of ML in human-AI interaction.

Published as a conference paper at ICLR 2024
THE HUMAN-AI SUBSTITUTION GAME: ACTIVE LEARN- ING FROM A STRATEGIC LABELER
Tom Yan
Chicheng Zhang
Machine Learning Department Carnegie Mellon University tyyang cmw.cdu... edu
Department Computer Science University of Arizona ch i chengz êcs. ar zona. edu
ABSTRACT
The standard active learning setting assumes a willing labeler, who provides labels on informative examples to speed up learning. However, if the labeler wishes to be compensated for as many labels as possible before learning finishes, the labeler may benefit from actually slowing down learning. This incentive arises for instance if the labeler is to replaced by the MI. model once it trained. In this paper, we initiate the study of learning from strategic labeler, who may abstain from labeling to slow down learning. We first prove that strategic abstention can prolong learning, and propose novel complexity measure and representation to analyze the query complexity of the learning game. Next, we develop a near-optimal deterministic algorithm, prove its robustness strategic labeling, and contrast it with other active learning algorithms. We also analyze extensions that encompass more general learning goals and labeler assumptions. Finally, characterize the query cost of multi-task active learning, with and without abstention. Our first exploration of strategic labeling aims consolidate our theoretical understanding of the imitative nature of ML in human-Al interaction.
INTRODUCTION
Over the past few years, the rapid growth of Machine Learning (ML) capabilities has raised the possibility of wide-ranging automation, and consequent worker replacement. Taking step back from when these ML models are phased in, we ask a basic question on how they first come about:
Where will the training data for these ML models come from?
In many industries, domain-specific knowledge is required to perform the job. Much of this expertise is proprietary (e.g. trade secrets), and not made publicly available (e.g. on the internet). Thus, in these industries, the answer to our question is paradoxically that: the training data can only come from the workers themselves. At this point, we arrive at a clear conffict of interest.
On the hand, corporations wish to automate tasks through MI models. On the other hand, the data needed to train these models can only come from the domain experts - the workers in this case, who know full well that these models, when trained, will go on replace them at their jobs. Thus, this raises the possibility that we may see workers actually aim to slow down learning, in order to delay replacement and be compensated for as many labels as possible before then.
We note that the idea of Al job displacement is no longer rarefied topic, entertained only in academia. The possibility of AI displacement has been written about in recent articles (Benson 2023), and even surfaced in labor union negotiations. In May 2023, Hollywood screenwriters went strike to negotiate better deal. One part of their demands is for there to be limits on companies being able to train ML models the scripts produced by the writers themselves (WGA 2023). Indeed, without this protection, companies can train AI models to emulate and write as well as the writers, eventually replacing them with the trained models. In sum, we believe is now high time to develop our understanding of the replacement aspect of learning, which is what we set out to do in this paper.
Remark: Before moving on, point out that the conflict of interest described above is fairly general, and arises whenever the labeler wishes to maximize payment from labeling. Consider more broadly the interaction between any data provider (e.g. data labeling company) and learner (e.g. company

---

Published as a conference paper at ICLR 2024
needing ML models). The more informative the data labeled by the provider, the faster the learner learns, the fewer the examples the learner needs to query the provider and the lower the provider's subsequent payment. The AI automation setting we describe is one of many such instances where the labeler's objective is at odds with that of the learner: the labelers has the incentive to slow down learning, maximize their compensation from labeling before the models are fully trained and render their labeling expertise redundant.
In this paper, we study the learning game that arises when the labeler and learner's ss objective are at odds. The learner wants to learn quickly, but the labeler wants the learning to progress slowly. Notably, this requries departing from the standard assumption in learning theory that the labeler readily labels any example queried (including the informative examples). We term this game the Human-A/ Substitution game, since typically the labeler is human and the more the model trained, the less the learner needs the labeler (to label). To study the rate of learning, we turn to theory to analyze how the labeler can slow down learning.
In Section 2 we formalize the learning game and game value, developing novel representation of the game state - effective version space (henceforth abbreviated as E-V.). In Section 3] we then develop natural, efficient learning Algorithm 2 which we prove achieves near-optimal minimax query complexity. We also show that other AL algorithms may be inefficient. examine more general settings involving noisy non non-strategic labelers, showing that our algorithm can nevertheless achieve good query complexity. Finally, in Section 5 we consider the multi-task setting and analyze when strategic labeling can further enlarge the learner's query complexity beyond the sum of the individual tasks' query complexities.
Our Contributions:
In Section 4
1.1 ACTIVE LEARNING WITH A SIMPLE TWIST
We begin our investigation by adopting the standard active learning setup (Hanncke et al., 2014). with the only twist that the labeler aims to maximize the learner's query cost. We focus on perhaps the most fundamental setting: exact learning through membership queries (Angluin 1988 Hegedus 1995). As we will see, this setup is fairly general, and one may use standard reductions to reduce the PAC and noisy setting to this setting.
Setup of the Learning Game:
The learner is interested in learning hypothesis h² in hypothesis class H C (X' - { (+}, over a finite pool of unlabeled data X, collected by the learner.
The labeler knows h" and responds using labeling strategy T with response T(x) E (a)) where 1 denotes abstention.
The learner repeatedly interacts with the labeler adaptively, and makes label queries on unqueried example x, and incurs cost 1 (T(x) # for each such query
In this paper. we model the labeler as being able to strategically abstain on queried data, to slow down learming. Being the domain expert with specialized expertise, the labeler is assumed to be able to use this leverage selectively decide which data points to label. As noted Section T some data points are particularly informative, and naturally the labeler would wish to decline labeling these so that more data would need to be labeled. We also add that this strategy of slowing down the transfer of expertise is not a novel conception. It has been well-documented that in apprenticeships. for instance, teachers (master) strategically slow down the training of their apprentices (Garicano & Rayo 2017).
The interaction finishes when the termination condition is met, or the learner's 's querying strategy halts. Based on the learner's 's desired learning outcome, the termination condition is defined as when h E H. is identified, which we formalize in the following section. If the termination condition is met, the labeler gets a payoff of for every labeled data provided. If the termination condition not met, the labeler gets payoff of O. In this game, the learner aims minimize the total payoff needed to learn h", while the labeler aims for the opposite and to maximize the total payoff.
In Section 2.2 and Appendix B also study variant of the game (Protocol where the labeler choose reveal binary labels abstain adaptively.
NNote that we define the cost for all non- con-abstention label feedback to be 1 for all x. However, as we show in Appendix C our algorithm can generalize to handle varying data prices (price for non-abstention label feedback <(z) can he dependent on feature..0 .7).
2

---

Published as a conference paper at ICLR 2024
Protocol 1 Au Substitution game inter- action protocol
x'
21
12
Z3
H
Require: Instance domain X. hypothesis class
h1
+1
1
+1
H. queried examples Sx. queried dataset S
h2
-1
+1
1: V < H. 5x <
hs
+1
+1
2: Nature chooses some h" H given to the
h4
-1
+1
hs
labeler > Throughout, labeler maintains
that h* is identifiable: h² Sx).
Table I: Consider an example hypothesis class
3: while LEVV, Sx] 2 2 do
H. = [h1, h2, h3, h4. and instance space X (2, The interaction history is {a ).
4: Learner adaptively queries example X' \ Sx using learning algorithm A
S [),,, and therefore Sx
5: Labeler adaptively gives label feedback
y E (h'(x)) +} using labeling oracle T
Under we have that the VS (Definition 2.1). V == H[S]= {hi, h2, h3, h4, ht).
6: Learner updates the VS: V + V((x,))
We observe that h1 and by make identical pre- dictions on X' Sx [z2, Likewise, hg and ソ4 make identical predictions on X' Sx- Therefore, effective version space is actually (V, Sx) = { If the game reaches this stage, the learner can already identify that the target ht must be h5.
Recall Definition 2.1
7: Sx < Sx U (2), S + SU ((r,))} then 9: Learner makes total payment to the la-
8: if [E(,
beler: E(e,)es {vi }1}
Guaranteeing Learning Outcome: Before proceeding, we note that the labeler can always satisfy
the learner's objective by using the non-strategic labeling strategy T(x) h (x) as in the standard active learning setup. Since the labeler can realize the learning outcome, we assume that the learner has this guarantee (of the learning outcome) written into the contract; payment is awarded
otherwise. Indeed, if the labeler cannot guarantee the learning outcome, seems unlikely that the learner would have chosen to contract the labeler in the first place.
The key tension in this interaction is that the labeler has to label in order be paid, but any labeling results in less data that subsequently need to be labeled. With the labeler only allowed to abstain besides labeling, it is natural to ask: can abstention significantly enlarge the query complexity? Our investigation is motivated by the affirmative answer below, where we find that abstention can exponentially enlarge query complexity in some settings.
Prolonging Learning through Abstention:
Proposition 1.1 (Abstention induces exponentially higher query complexity). There exists a hypothe- sis class H. instance domain X' such that: the query complexity is O(log (x() if the labeler is unable to abstain, and (l) for any learning algorithu if the labeler is allowed abstain.
2 THE MINIMAX LEARNING GAME
2.1 REPRESENTATION OF THE LEARNING GAME STATE
To study this learning game, we first develop a useful, succinct representation of the game state, which is key contribution of our paper and allows to formalize the termination condition and the protocol. We start by defining the canonical state representation used in conventional AL without abstention, the version space (VS) (Mitchell) 1982).
Definition 2.1. Given a queried dataset and a set of hypotheses V, define version space V[S] {h E V: V(I, y) E SAY #L, h(x) = y as the subset of hypotheses in V consistent with S.
In our setting of learning with strategic abstention, some queried examples in S will not have their binary labels available to the learner, due to the labeler's 's abstention. And so, we observe that certain hypotheses may be consistent, but indistinguishable from other hypotheses, even if all the remaining unqueried data is labeled. This motivates defining a new notion of identifiability of a hypothesis under queried dataset S. Let the set of all queried examples be Sx {i (x., y) E S}.
Definition 2.2. Given the set of queried examples and their label responses S, and the queried examples Sx. hypothesis h H is said be identifiable with respect to S if:
3

---

Published as a conference paper at ICLR 2024
h is consistent with S, h H[S].
for all other consistent E H[S]:: N'(X') Sx) -(x Sx) = h' = h, where for brevity denote h₂(U) = h2(() = Yx U h1(x)) = h2(2).
In other words, identifiable with respect to S if over the remaining examples Sx, some labeling strategy (specifically, one that reveals h(r) on every E X' Xx)5x) allows h to be distinguished from all other hypotheses in H[S] With this, we may develop a new representation of the state of the game, effective version space (E-VS) The E-VS is refinement of VS, and comprises of only identifiable hypotheses given the examples queried. Please see Table T for an illustration.
Remark: The key insight here is that abstention can in fact reveal information. This is despite that abstention is used by the labeler to prevent releasing information about h" The reason why one can glean information from labeler's abstention is that hypotheses could be rendered unidentifiable by abstention on a data point, and thus be ruled out without needing further queries. We operationalize this insight to develop the effective version space representation, which we formalize below.
Definition 2.3. Given a set of classifiers V and a set of examples Sx, define
S(V,5x) {h E Wh' E EV (h) N' (x) + h(X {5x)
as the effective version space with respect V and Sx. Definition 2.4. h" E H is identified by queried dataset S if the E-VS, F(H(S), = {h²}.
With the identification criterion defined, we now formalize the interaction in Protocol [ Here, the termination states are defined as either (V,V, Sx)l = (a hypothesis is identified and the learning outcome is met), or EVV, Sx) 0 (no hypothesis can be identified).
2.2 THE MINIMAX LEARNING GAME
In this paper, analyze the minimax query complexity that of the worst-case h² E H to learn under Protocol Towards this, we formulate a related minimax learning game (see Protocol i Appendix B where both the learner queries and the labeler labels adaptively, depending on the interaction in previous rounds, with the game's 's optimal value function defined as follows:
E(V = 0
(V,S))
EEV ((V,5x)
min maxyey (1 F1) +
Ux (x)))
((V, 2
(1)
Compared to the original Protocol [ Protocol can be viewed as giving the labeler more freedom:
the labeler does not need commit to provide binary labels using given h"; it just needs to maintain the invariant that there is some h" identifiable and consistent with all examples seen. As we will see shortly, the optimal value function Cost. of Protocol serves as a useful tool in analyzing the optimal query complexity of Protoco!
In the of non-identifiability, we base-case payoff of cco encode that the labeler must ensure identification. As noted in Section [ any optimal labeler will never end up in such a state, because a positive payoff can always be achieved the strategy T h² results in positive payoff. We now turn to formalizing what an identifiable strategy is.
Definition 2.5. Given h H. define the set of labeling oracles consistent with h, as:
To x -1, V2 E X s.t #1, = h(x)).
For subset Sx C X, let T(Sx) {<x, T(x)) E Sx} be the labeled (binary abstention) examples provided by labeling oracle on the examples Sx
Definition 2.6. A labeling strategy T Th. is identifiable oracle if the VS. H[T(x)) (h).
In the learning game, the labeler's strategy is some labeling oracle, while the learner's 's strategy
corresponds some deterministic querying algorithm: A: (X'x X. where y ={+ [+1, -1, 1}. Define Cost A. (V, Sx) ) to be value of the learning game under querying strategy A and labeling strategy T. The key result of this subsection is that the game value Cost( (H. 0) can serve a useful measure of minimax query complexity. Cost(H, 0) lower bounds the corst-case query complexity of any deterministic learning algorithm in Protocol
4

---

Published as a conference paper at ICLR 2024
Proposition 2.7. For any deterministic, exact learning algorithm A,
max hEM,T'Th
Cost (,, , 0) 2 Cost.(H, 0)
This means that for every exact learning algorithm A. there is some worst-case labeling oracle Tx that induces at least Cost (H. 0) cost. Please see Appendix B for all proofs in this section.
3 E-VS BISECTION ALGORITHM ANALYSIS
In this section, we design natural and efficient algorithm based on E-VS bisection, Algorithm which prove achieves query complexity (Coost (H, 0) In [H)). Proving this guarantee allows us to use the lower bound result, Proposition 2.7 from the previous section to conclude that Algorithm 2] minimax query complexity is optimal up log factors. Towards analyzing the algorithm performance (and inspired by a related measure in [Hanneke (2006) for the conventional non- con-abstention setting), first introduce us to bridge Algorithm@2) 2]s performance to Cost.
complexity measure named global identification cost (GIC), that will allow
Definition 3.1. Given H. N, define the global identification cost Vf H. instance set Sx as: +
GIC Sx) = min(t E N: VT X Sx
EE C X Sx s.A. EI(((>) #1) SEA (LAVE((((())) Sx U2) S 1
FE
Intuitively, GIC represents the worst-case sample complexity of a clairovyant querying algorithm that knows ahead of time the labeling oracle that is used by the labeler.
The key lemma behind the analysis of Algorithm 2 is that there always exists point that significantly
bisects the current E-VS, resulting size reduction of at least a constant (1 (1- cic(Vssx) factor.
This justifies greedily querying the point that maximally bisects the E-VS.
Lemma 3.2. For any Vx8x such that GIC(V, finite, Er E X' \\ Sx such that:
(IE(V[(z,V), v),, Sx U (z})) 1) < (V Sx) 1)) GIC(V,Sx))
max VE (-++)
To analyze the algorithm's query complexity, we lower bound (V, by GIC(V,Sx)) Lemma 3.3. For any V C H and Sx X: GIC(V,Sx) s Cost(V,Sx).
With this, we can prove that Algorithm 2 a) has query complexity of O(Cost (71, 0) In ) b) identifies h² when the labeler's labeling strategy is identifiable. Please see Appendix Cfor all the proofs.
Theorem 3.4 (Algorithm 2 query complexity guarantee). If Eggorithmmiinteaaae with a labeling orucle T, then it incurs total query cost at most GIC(H, 0) In H + S Cost(H, 0) In [H] + Furthermore, if Algorithm interacts with an identifiable oracle consistent with some h H. then it identifies h².
3.1 ACCESSING THE E-VS
Algorithm 2 may be viewed as the E-VS variant of the well-known, VS bisection algorithm (Tong & Koller (00T), an "aggressive" active learning algorithm that greedily queries the informative point that maximally bisects the VS. The canonical approach for accessing the VS is sampling, by assuming access to sampling oracle O. For example, if H. is linear, the VS is a single polytope and one can use a polytope sampler to evaluate and search for the point x that maximally bisects the VS.
E-VS Structure: Maximal E-VS bisection point search is less straightforward by contrast. The following structural lemma shows that there exists setting of linear hypothesis classes in Ed with X' and S such that the E-VS comprises of an exponential number of disjoint polytopes. This means that it is computationally intractable to access the E-VS as polytopes, if one is use the sampling approach as in VS-bisection.
Proposition 3.5. There exists an instance space X C Rd. a linear hypothesis class H. and query response S such that the resultant E-VS comprises of an exponential in d number of disjoint polytopes.
5

---

Published as a conference paper at ICLR 2024
Algorithm 2 E-VS Bisection Algorithm
Algorithm 3 Bisection Point Search Sub-routine
Require: Data pool X, hypothesis class H. V < H. S 0 VS. queried dataset
Require:
Unqueried examples U = X' \ Sx. abstained examples S1. Version Space V, sampling oracle O
2: while E(V, 2 2 and Sx # X' do
3: Query: b Maximal E-VS bisection
1: for sample / ~ (VV) do
point
2: Construct Z1 = {(x -h(x)) : :I
7/2 = ((r h(x)) : x E X \st}
x = arg min max xEXi,8 1
(x),
3: Run C-ERM to obtain:
h
arg min {err(h', Z1) h' E H, err(h', 72) = 0}
4: Labeler T provides label response: E
{-1, 1-1,+1,1]
4: if + h then continue
5:
St S (Zz,g)
else P E E(V, 5x) in this case
6:
y then
6:
r. r + if h(x) = -1 else r +
7:
V (V(,
r + 1 for U, t m+1
8:
return h, the unique element in E(V,Sx)
7: return x² arg min Int ft/nn113 13 /nl
Towards tractable maximal E-VS bisection point search: To overcome this issue, we develop a novel, oracle-efficient method for accessing the E-VS. We observe that structural property of the E-VS can be used to check membership given access to constrained empirical risk minimization (C-ERM) oracle (Dasgupta al. 2007). This allows us to design an oracle-efficient subroutine, Algorithm for any general hypothesis class H. which we prove is sound.
Definition 3.6. A constrained MaaM ERM oracle for hypothesis class H. C-ERM, takes as input labeled datasets Z and Zz and outputs a classifir: h E arg min {err(h', Zi) : orr(h', Z2) 0}. where for dataset Z, err(h', Z) =(unyez ((' + y).
Proposition 3.7. Given some h E V and access to C-ERM oracle, lines 2 in Algorithm verifies whether EV,,Sx), with one call to the oracle.
3.2 COMPARING WITH THE VS BISECTION ALGORITHM
Labeling without identifiability: An advantage of the E-VS algorithm is its robustness to strategic labeling. Theorem 3.4 states that the E-VS algorithm has provable guarantees, even when the labeler does not guarantee identification. By contrast, VS-bisection is not robust this way. To concretely compare the two, we construct a learning setup without identification, wherein Algorithm incurs much smaller number of samples.
Theorem 3.8. There exists a H and X such that the number of labeled examples queried by the E-VS bisection al algorithm is Ollog (2), while the VS bisection algorithm queries 2((x)) labels.
The key observation here is that, by optimistically assuming identifiability (even when this is not guaranteed), Algorithm / can ensure small query cost. It does by using the E-VS cardinality to detect when the labeling strategy is non-identifiable and halt the interaction.
Remark:
Please refer to Appendix for all proofs in these subsections and a comparison with EPI-CAL (Huang et al.) 2016). a natural "mellow" active learning algorithm that can handle labeler abstentions. Additionally, please see Appendix [ for some toy experiments based on synthetic data.
4 EXTENSIONS TO OTHER LEARNING SETTINGS
The prior sections have assumed that the labeler (e.g. data labeling company) is resourcefully providing non-noisy, labeled data that exactly identifies A², In this section, we examine few ways in which the labeler (e.g. a human worker) may be imperfect in labeling, and extend our guarantees to show how the learner may learn in such settings. Indeed, is possible for the labeler to abstain non-stratt stateettayyy simply due to uncertainty (or lack of knowledge) about the label. As we will see, Algorithm 2 will also allow for efficient learning with non-strategic, abstaining labelers.

---

Published as a conference paper at ICLR 2024
4.1 APPROXIMATE IDENTIFIABILITY
A relaxation of the goal of exact learning is PAC learning: learning some such that its error Pra=p( (h(x)) + h² (x)) S c on distribution D supported on X' with probability (w.p.) greater than 1 1- This learning goal can arise when the learner wishes to relax the learning outcome/termination criterion, or wishes to weaken the assumption that the labeler identifies h", to only knowing a fairly accurate hypothesis E H.
Reduction: To study the PAC setting, one may use the standard PAC to exact learning reduc- tion [aanni 1999). It is well known that PAC learning can be reduced to to exact learning on sub-sampled set, Xm C X, of m O VC(H) (In In })) i.. points from DD (VC(H) denotes the
VC dimension of HD).
Then, X partitions H. into clusters of equivalent hypotheses. Let the projection of H on X be H|x= (h(X")) / E H}. For E Hixm, a cluster C'v)) of equivalent hypotheses may then be defined as C(y)= = {h E H h(X") = y}. The reduction guarantees that, w.p. over 1 - 5 over the samples XT, identifying h cluster (x"") suffices for finding h with error S..
Using this reduction, we may analyze the query complexity of approxi- mate identification in the resulting learning game. this game, the learner sets the data pool to be X (can be much smaller than X') and aims to only learn the cluster h" belongs to, C(h (X"").
Approximate Identification:
We demonstrate how our E-VS representation can be adapted to apply Algorithm 2 in this approximate identification game. We first note that the original E-VS, defined over H and X will no longer suffice as state representation. Consider some h E H such that (C((X"))) 2 with {M',} h S C(h(X"))
Then, h( h(x")) (X" = h'"X" \. ()) = ( m
(), which results in the premature elimination
of the entire C()(X")) cluster at the very start.
To address this, we define a refinement of E-VS, X EE-S.. This fix follows from observing that in this game, we should only consider non-identifiability with respect to hypotheses from other clusters.
EX" (V.Sx)
[h Vh' E V \ (h -
( ), h E V} h'""" \ (8x) * h(x m {x)
With this, we note that the -7--E-VS bisection algorithm attains analogous near-optimal guarantees. instantiated with data pool X and state representation X -E- VS. When interacting with a labeling oracle T, it incurs total query cost at most GIC (H. 0) In |H|| 1 (see Definition [.2]. Furthermore, the Xm VS bisection algorithm interacts with an identifiable oracle T consistent with some h² E H. then it identifies h".
Corollary 4.1. Consider Algorithm 2
The only remaining consideration is how efficiently search for the point that maximally bisects clusters in X Here, we show that we may adapt the membership check implemented in Algorithm (with the data pool set to X²) check hypothesis membership in the coarser Xm--EVV.. That is, we still have an oracle-efficient way of accessing the XE--E- without needing to explicitly compute and iterate through the clusters.
Proposition 4.2. h & E (V, Sx) iff h()"")) + h(X"), where h is the minimizer of the C-ERM output on Algorithm Line with X' ===a X
4.2 NOISED LABELING
In some cases, labeler can make honest mistakes simply due human error. We can model this by assuming noised queries (Castro & Nowak 2008): querying example x returns h (x) w.p. 1- 6(x). and (x) (x:) w.p. 8(z). In this setup, we may use the common approach of repeatedly query a datum to estimate its label w.h.p. (e.g. as in Yan et al. (016)). This approach thus reduces the noised-label setting to cost- sensisvnsi exact learning, where each x incurs differing cost c(ar) dependent on d(x)). In Appendix C we prove the generalized version of the results in Sectionnthar factors in example-based cost, showing that Algorithm 2 can be applied in this setting with near-optimal guarantees.
4.3 ARBITRARY LABELING
Thus far, we have assumed a labeler who can (approximately) identify h², Here, we touch on when the labeler either does not know h" (or hs cluster), or myopically labels in way that cannot
7

---

Published as a conference paper at ICLR 2024
guarantee the learning outcome. Since the labeler behaves arbitrarily, the learner now cannot be assured of any learning outcome guarantees. In this case, we note that the learner can use the E-VS to preemptively detect when the learning outcome cannot be realized, and halt the interaction. While the h² is unknown, it is possible to detect when no hypothesis/cluster is learnable. This is when the E-VS is empty, certifying that the labeler cannot realize the learning outcome. Here, our Theorem 3.4 provides guarantees on the maximum number of times that non-identifiable oracle will be queried.
guarantees bounded query complexity GIC(H, 0) In [H| + 1 even when the labeling oracle is non non-identifiabble.
Corollary 4.3 (of Theorem 3.4).
Algorithm 2
Finally, we note that our algorithm is sound in that if the labeler can identify h", then our algorithm learns h² Thus, in summary, Algorithm is both sample-efficient with respect to an identifiable labeler, and robust to a non-identifiable one. Please see Appendix E for more details on this section.
5 MULTI-TASE LEARNING FROM A STRATEGIC LABELER
Multi-task setting: In most jobs, workers in fact perform multiple roles. This motivates the study of multi-task exact learning from a strategic labeler, which we now outline:
The learner is now interested in learning multiple h H4, for tasks E [ni]. Define learner's
hypothesis class 7/ = x Hi which contains h* = (hi.... hr)) ) The learner can query
from instance domain X' S " where X; the instance domain for task
Labeler now provides multi-task labels y E y" = {+1, 11 1,, 1""" and for the label cost:
i) One natural extension of the single task payoff is: Come (y) = 13i, y *L). ii) Another variant of the multi-task labeling payoff is: (y) = 1 L(vi, #1).
We are interested asking: can the labeler use the multi-task structure to further amplify the query complexity? To answer this question, relate the multi-task query complexity to that of single-task. Single-task setting:
Definition of S given queried data Sx. define the queried data for task i, S as: Sx = (X' [x); where we use the notation that Z {ar Z) for Z X. In words, S'X are examples in X; whose label can no longer be obtained. Note that in the multi-task setting, there may exist multiple points that can label some I; X, So abstention on one of those points does not necessarily mean that x; cannot be labeled.
Example: X' = [II1.I12} x {x221, F22). Sx = {[ [212, Ø22]] }. then Sx = =0 for = 1,2. This is because it still possible for the labeler to give labels on all points, i.e.
211, T22 through [211, 222] and Æ12, Z21 through [z12, 221].
Definition of V/:: given the current multi-task version space V, naturally define the single-task version space for task i as: (V), = V2 = {h+ : :hhve
5.1 UPPER BOUND
To understand if multi-task structure can inflate query complexity, we upper bound the multi-task complexity terms of the sum of the single-task complexities. Proving an upper bound would imply that the labeler cannot increase the query complexity through the multi-task structure. We find that upper bounds only arise under certain regularity assumptions. Thus, we first provide complementary negative results without these assumptions, showing settings where the labeler can amplify the multi-task query complexity. All proofs in this section may be found in Appendix [F] where we also prove results in the non-abstention setting that may be of independent interest.
Proposition 5.1. Under both label costs, there exists a non Cartesian product version space V C H and query response S C (X x y)" such that Cost(V, S'x) 0 for all i, and: CVst(V,SS)) 2 E CV, Sxx +
Furthermore, we show that if the version space is allowed to be a Cartesian product, and the (more generous) Cone is used label cost, the labeler can still increase the query complexity.
Proposition 5.2. Assuming the version space is Cartesian product, under label cost Cone (v) = 1 yi #1). there exists V and S such that Cost Sxx) 1, but Cost(V, Sx) = |x) This implies that: CVst(V,SS Ei= Cost (o, St)-
8

---

Published as a conference paper at ICLR 2024
Thus, for the labeler be unable to increase multi-task query complexity, two necessary conditions are a) the VS is a cartesian product b) the payoff cost is Coll (and not Cone). Below, we prove the two conditions sufficient, providing a full characterization when the upper bound can be achieved.
Theorem 5.3. For all V x V2 and Sx C X, under labeling cost Caul Cal(y) (vi, ya + 1),
(V, -i=1 S'))))
For the remainder of the section, we will prove results under the (more generous) label cost, Cone-
5.2 LOWER BOUND
Through lower bounds, we illustrate that the multi-task version space structure can in fact speed up learning well. The intuition is that the structure in V may make it so that the multi-task E-VS shrinks faster due to unidentifiability. The following negative example evidences this.
Proposition 5.4. There exists a non-Cartesian product version space and query response S such that Cost (V,, 5xx 2 0 for all i, but: (V, <
max Cos
Proposition 5.5. There exists Cartesian product version space V and query response S with Cost(V, < such that: Cost(V, Sx) )x) < maXie[n] CVst(V,,35 Sx).
Thus, we have that identifiability (Cost 2 0), and V being a Cartesian product are needed to prove a lower bound.
Theorem 5.6. For all V = Xseln| V₁ and Sx S X, if Cost(V, Sx) z O, then: (V, z maXi[[m) Co,
RELATED WORKS
The theory of Active Learning (Hanneke 2009) (AL) has rich history and began with the study of realizable learning (Angluin| 1988; Hegedūs| 1995 Freund et al.) 1997: Dasgupta 2004 Dasgupta al. (005)). To the best of our knowledge, we are the first consider labeler whose objective is odds with the learner. In face of such strategic labeler, we develop an active learning algorithm with near-optimal query complexity guarantees.
A Abstaining Labeler:
The closest two papers to our work are Yan et al. (2016); Huang et al. (016)). which also study learning from an abstaining labeler. In Yan et al. (2016). the labeler can abstain or noise, where the rate of an incorrect label/abstention is fixed apriori. Our work differs from that of Yan et al. (2016) (2055) that the labeler can adaptively label (abstain) based on the full interaction history far, thus allowing for more complex, sequential labeling strategies. In Huang al. (2016), the labeler abstains when uniformed, and after number of abstentions in a region, learns to label the region (an "epiphany"",. Our setting differs in that the labeler does know the labels for all regions, but instead strategically abstains to increase query complexity. Please see Appendix [H for further discussion on related works and on alternative formulations of the learning game, including when the learner is allowed to query an example multiple times.
7 DISCUSSION
In this paper, we provide the first set of theoretical evidence that labelers can slow down learning through strategic abstentions, making even active learning algorithms sample-inefficient. Motivated by this, we study the learning game involving a strategic labeler, in both the single and multi-task setting. Our theoretical study is motivated by the broader observation that labeler's s objective may be fundamentally at odds with the learner's. This conflict in interest arises for instance in Al-automation setting, where workers have the incentive to slow down model training, order to delay replacement and to maximize compensation for their labeling services before replacement.
Societal/Broader Impact: Zooming further out, workers have an incentive to slow down training they lack financial security after being replaced. Indeed, ML offers tremendous potential in bettering our lives, automating away jobs people do not want to do. However, it can also automate away jobs that people do want to do. It is our hope that this paper adds to the important discussion whether we should always automate, once we have the ability to automate, as well as the discussion on fair labeler compensation during the automation process (De Vynck 2023)

---

Published as a conference paper at ICLR 2024
REFERENCES
Dana Angluin. Queries and concept learning. Machine learning, 2:319-342, 1988.
Thor Benson. Your boss's spyware could train ai to replace you. Wired, 2023. URL https
www. wired.
sareeeessviiilllaeetreeeee -ai/
James Brown and Robert W Rosenthal. Testing the minimax hypothesis: A re-examination of o neill''s game experiment. Econometrica: Journal of the Econometric Society, pp. 1065-1081, 1990.
Rui Castro and Robert D Nowak, Minimax bounds for active learning. IEEE Transactions on Information Theory, 54(5):2339-23555 2008.
Yiling Chen, Chara Podimata, Ariel D Procaccia, and Nisarg Shah. Strategyproof linear regression in high dimensions. In Proceedings of the 2018 ACM Conference on Economics and Computation, pp. 9-26, 2018.
Sanjoy Dasgupta. Analysis of a greedy active learning strategy. Advances in neural information processing systems, 17, 2004.
Sanjoy Dasgupta, Adam Tauman Kalai, and Claire Monteleoni. Analysis of perceptron- based active learning. In International conference on computational learning theory, pp. 249-263. Springer, 2005.
Sanjoy Dasgupta, Daniel Hsu, and Claire Monteleoni. A general agnostic active learning algorithm. Advances in neural information processing systems, 20, 2007.
Gerrit De Vynck. Ai learned from their work. now they want compensation. Washington htt/://accccoolllg/////////////0 ai si-programs training lawsuits farr-aarrr--s
Post, 2023. httpttss:: www. washi wgt.ooottttttssooo.. wwt.whhhtoogooooosooooooeoeeeeee
Ofer Dekel, Felix Fischer, and Ariel D Procaccia. Incentive compatible regression learning. Journal of Computer and System Sciences, 76(8):75--777, 2010.
Yoav Freund, Sebastian Seung, Eli Shamir, and Naftali Tishby. Selective sampling using the query by committee algorithm. Machine learning, 28: 28:133-168, 1997.
Drew Fudenberg and Luis Rayo. Training and effort dynamics in apprenticeship. American Economic Review, 109(1 1) 1:3780-3811 3812, 2019.
Luis Garicano and Luis Rayo. Relational knowledge transfers. American Economic Review, 107(9): 2695-2730, 2017.
Daniel Golovin and Andreas Krause. Adaptive submodularity: new approach to active learning and stochastic optimization. In COLT, pp. 333-345 2010.
Steve Hanneke. The cost complexity of interactive learning. Unpublished manuscript, 2006.
Steve Hanneke. Theoretical foundations of active learning. Carnegic Mellon University, 2009.
Steve Hanneke et al. Theory of disagreement-bassee active learning. Foundations and Trends@ in Machine Learning, 7(2-3):131-309) 2014.
Moritz Hardt, Nimrod Megiddo, Christos Papadimitrion, and Mary Wootters. Strategic classification. In Proceedings of the 2016 ACM conference on innovations theoretical computer science, pp- 111-122, 2016.
Tibor Hegedũs. Generalized teaching dimensions and the query complexity of learning. In Proceed- ings of the eighth annual conference on Computational learning theory, pp. 108-117, 1995.
Tzu-Kuo Huang. Lihong Li, Ara Vartanian, Saleema Amershi, and Jerry Zhu. Active learning with oracle epiphany. Advances in neural information processing systems, 29, 2016.
Tom M Mitchell. Generalization search. Artificial intelligence, 18(2):203-226, 1982.
10

---

Published as a conference paper at ICLR 2024
Javier Perote and Juan Perote-Pena. prrategy-prood estimators for simple regression. Mathematical Social Sciences, 47(2):153-17,, 2004.
Nikita Puchkin and Nikita Zhivotovskiy. Exponential savings in agnostic active learning through
abstention. In Conference Learning Theory, pp. 3806-3832. PMLR, 2021.
Sivan Sabato, Anand D Sarwate, and Nati Srebro. Auditing: Active learning with outcome-dependent query costs. Advances in Neural Information Processing Systems, 26, 2013.
Yufei Tao, Hao Wu, and Shiyuan Deng. Cross-space active learning graph convolutional networks. In International Conference on Machine Learning, pp. 21 21133-21145, PMLR, 2022.
Simon Tong and Daphne Koller. Support vector machine active learning with applications to text classification. Journal machine learning research, 26,6,) 2001.
Leslie G Valiant. theory of the learnable. Communications of the ACM, 27(11): 1142, 1984.
Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 1999.
WGA. Wga negotiations status as may 1, 2023. Writers Guild of America, info/
2023. URL https://wwwx //ww:..//wwww// wga. wrg. http:///w/.pppeeeeeeeeeeeeeeeeee
Songbai Yan, Kamalika Chaudhuri, and Tara Javidi. Active learning from noisy and abstention feedback. 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 1352-1357. IEEE, 2015.
Songbai Yan, Kamalika Chaudhuri, and Tara Javidi. Active learning from imperfect labelers. Ad- vances Neural Information Processing Systems, 29, 2016.
Yinglun Zhu and Robert Nowak. Efficient active learning with abstention. arXiv preprint 200.000330000044, 2022.

---

Published as a conference paper at ICLR 2024
Notation
S = (1,, 1/2 v2), : query responses in the interaction history
Sx
Sx = (x: (z, 5}. indexes the queried examples in S
8
5 (2: (x. S.y =1}. queried examples that were given abstention
VE, (((,)))))
Vr,,(= { V h(x)) y). updated VS (used interchangeably)
Sx)
F(V,Sx) = =fhv AW E {h) M Sx) # h(x \ {Sx)) effective VS
SAT
Interaction history between A and T
A
A, ( A}
SX
5X = 1 (x)): (xx) (V) = {h+ h
(V)s
Cone(y) (v)
Cone (V) = 1(3i, *1)
Cyuly)
Call()) = i y/i #1)
Table 2: Table of commonly used notation.
h2
h4
10
R1
h. 81'
X1
X2
1.1 is that of learning an one-to-one threshold-interval hypothesis class H = {(h;, k() setng" The learner seeks to identify (he h...). The labeler can abstain on Xi, and prevent the learner from learning through this sample-efficien part of the instance space. This forces the learner learn the interval h (instead of threshold hī) through X2, and incur much larger sample complexity.
Figure The setup behind Proposition
A PROOFS FOR SECTION
1
A.1 TECHNICAL RESULTS
Proposition A.1. There exists hypothesis class H. instance domain X' such that the exact learning sample complexity is O(log (1)) if the labeler is unable to abstain, and 22(22) for any learning algorithum if the labeler is allowed abstain.
Proof. Let the h - + (+1.-1} for E [n] denote intervals of length 1/n centered at
(2i 1)/2n for E [m], and M (1,2) [+1,-1] for [m] denote thresholds at 1 + i/n n for i [m]. Define hybrid-hypothesis class H of threshold-intervals, H (J1..., where:
f1(x) = h1(2) x E [0
(1(x)
x E (1.2)
Let x Xi U X2, where X1
2n-1 and X/ + .... 2n-1
1) When the labeler is not allowed to abstain, the learner may binary search on X to identify h/., which identifies fi- The required sample complexity is O(logn).
2) When the labeler is allowed to abstain, consider the following labeling strategy T:
T(x) =1 for all x E X
ii) T(x) = h1- (x) for all x E X1.
Note labeling strategy that allows for identification. H[T(X) [[ (fr-}.
Interacting with I' is equivalent to learning one of n disjoint intervals, which requires 2(n) samples under any learning algorithm (Dasgupta) 2004]. And so, T' induces 32n) samples, which in turn lower bounds the sample complexity induced by the minimax labeling strategy.
Remark A.2. We note that one may generalize the above result to any cross-space learning set- ting Tao et al. 2022) with significant differences in query complexity among the instance spaces.
12

---

Published as a conference paper at ICLR 2024
Protocol 4 Minimax strategic slow learning game
Require: Instance domain 2', hypothesis class 7 5 S + H
> TThroughou, the labeler needs to maintain that there is at least one classifier consistent with all labels so far and identifiable
while EVV Sx), 2 do
Learner queries example x E X' \ 5x Labeler provides label feedback y (-1,+1,1)
Learner incurs cost c(y), and updates its version space V + V
S+SU (x,8) }
Nature sets h² to be the only model E(V, Sx) EVV Sx) = Nature sides with the
labeler, sets h" to be the remaining model at the end
The labeler's optimal strategy here is simple: label only through the instance space that leads to the highest query complexity, and abstain all other (more informative) instance spaces.
Remark A.3. We also add that the labeling strategy need not be identifiable for this result to hold. One can simply define T to still abstain all of X2 and output - on all of X1, which still induces (() query complexity.
B PROOFS FOR SECTION
B. THE MINIMAX LEARNING GAME
We present Protocol which can be viewed as relaxation of the original Protocol allowing to be chosen aposteniori. This gives the labeler more freedom in answering the learner's queries, and therefore any query complexity upper bound here translates to query complexity upper bounds in Protocol [ Recall that the optimal value function of this game is given in equation (I).
B.2 PRELIMINARIES
We now come back to Protocol The game strategy for the labeler and learner now corresponds to labeling oracle, and a querying algorithm, which we formally define below.
Labeling Oracle Notation: Given h E H. recall that we define the set of labeling oracles consistent with h as,
Th :T: (+1,-1, 1a E X' s.t ((x)))))))))-----))))))))))) Mx))
Given subset Sx C X, let us define T(Sx) to be the of labeled examples induced by oracle T on the examples 5x-
Suppose V C H. let us define:
V[T(Sx)) (h Vlh(x) =
A labeling strategy T E Th is an identifiable oracle if H[T(x)) = (h).
Querying Algorithm Notation:
Formally, a deterministic learning algorithm AA consists of the
following:
Query function fquery: (X' 3)" + X
Termination function fterm (X' x y)* - (TRUE, FALSE)
Output function fout (X 3)* H
A interacts with the labeler by:
13

---

Published as a conference paper at ICLR 2024
Algorithm 5 The interaction process between A and labeler
S
while [Sarm([) = FA LSE do Query 6 [query(S)
Receive label
S UU ( (2)
return (S)
Properties of fterm:
If A is an exact learning algorithm, Sterm TRUE [V, S 1.
If A has a fixed budget N, fterm outputs
TRUE
when S such that:
(x
+
The formal interaction process between the learner using A and the labeler is summarized in Algo- rithm
Learning Game Payoff: Denote A., Sx) as the learning game payoff under exact learning querying strategy A and labeling strategy T'. Formally, let point FA,S be queried by A after seeing interaction history (corresponding to some sequentially labeled dataset) induced by labeling oracle T. With this, the value function of the learning game with strategies A and T may be recursively defined as follows:
E(V, LEVV, Sx) [EV, Sx) 2 2,
(V,
(T((AA.)) #1) + Cost (V (( U (xASS)
B.3 TECHNICAL RESULTS
Lemma B.I. Let the deterministic query algorithm A interact with labeling oracle T E The for M queries, generating the following interaction history: Sas (IM.T(aM)). Suppose there exists classifier h2 and T" E The such that for all {I1, J T(x,) (x.). Then, A generates the same interaction history, when interacting with T' for M queries.
(22,)
Proof. As defined previously, algorithm A comprises of query function fquery- termination function ftemm and output function fout- We show by induction that for steps i 0, 1,..,..44... M the interaction histories of A with and 7" agree on their first i elements for M.
Base Case: For step 0, both interaction histories empty and thus agree.
Induction Step: Suppose the statement holds up until step for some < M. That is, when A interacts with T and 7" generates the same set of queried examples:
S { ..., (I:.
Consider step i + 1. Firstly, A continues to make query and does not terminate, since (ferm(;)) FALSE for < M.
Now, for the (i + 1)-th query, A applies function fquery and queries 11+1 fquerv (S.). Since (T; T(æ,) for all j and particular for j + 1, we have that (Ii+1, T" (x:+1) = (#441, T();+1)). And so, with this and the induction hypothesis, we have that A when interact- ing with T" and generates the same set queried examples:
S = (111,1)),.... (6441,9441))
up to step 1.
Using this, we can conclude that the interaction histories after M steps of A with and T are identical.
14

---

Published as a conference paper at ICLR 2024
Remark B.2. Suppose, after the Mth step. have that TRUE fterm (SA,r) feerm (SM) And so, we have that SM = SA,T", and the interaction of A with T" also terminates at the Mith step.
Thus. for model output, we have SA. SM SATT = four
fow (SA.))
Proposition B.3. Let N denote the labeling budget. Let SA. be the interaction history of a deterministic algorithm A with oracle T up until the Nth label is given, or termination (without using all of the budget). Let (Sx) A.T ( be the unlabeled examples queried during the interaction. For any deterministic algorithm A, if N < Cost(H, 0). there exists some h E H. and identifiable oracle T E
Th such that [E(H[SN ETH (Sx)
A.T 2
Proof. Fix a deterministic algorithm A. We will show the following. A has already obtained an ordered sequence of queried examples S, and has remaining label budget N Cost(H[[S),5x Sx) then there exists h E H[S] and Th such that, A, when interacting with Tx:
obtains a sequence of queried examples S in the first [S] rounds
2. when the interaction terminates, the E-VS has cardinality at least (, 2.
two:
The theorem follow from the second point of this claim by taking 0.
We now turn to proving the above claim by induction on A's remaining label budget N.. Base Case: If then Cost(H[S), 1. By Lemma C.10 know that [E(H[S), [x)) 2.
Construction of Tz:
Let E E(H(S),Sx).
Define Ti be such that for (z) S. (x,) yı = h(x:) (the latter equality holds by definition of hi) if y, fL and (x;), =1 if ys =L, and define Ti. = h(x) for all æ E X Sx. know that 4(X' \ S1) + N'( 8 VA + h V. And so,
Since h [H Sx), H[[(x') = ( S1) {h}, which implies that T is an identifiable oracle for h.
By construction and using Lemma B.I T3 interaction with results in S, satisfying the first item. Moreover, since = 0, So S. S. And so, [E(H(S,,,, (Sx 3,4.%) (Sx)
[E(((S), Sx)
Induction Step: Suppose the claim holds for all N S for some 0 S < Cost 0) 1.
Now, suppose during the interaction, algorithm A has remaining budget N n and the obtained queried examples history S is such that Cost(H( Sx) 2 N
+ 2.
Our goal is to show the existence of h and T that satisfy the two listed properties under these two assumptions.
Define x'y for index j 2 1 to be the next example A queries such that binary label y is given (i.e v/} * as we recursively unroll the Cost expression, via the construction procedure below.
Algorithm 6 The construction procedure for (z/, 8/))
L+ S, Lx Sx.j
repeat
Query 1/
fLL using
Labeler return U'k arg
(1(y + Cost(H( (1 u ufak))
L+ L ( Lx + 1
until 1/3 #1 or Frorm (L) TRUE
There cases:
15

---

Published as a conference paper at ICLR 2024
If the final j satisfies v/J # then after querying (</ vf) 1:1" the learner has remaining budget of N nt
Next, we see that with each abstention, the Cost value is non-decreasing, as justified in the first three steps:
We have that:
Cost (x(
max nE((+1-1,11
(V1 # Cosu (z1))
1Vi *1) + Cost (H b1 (x1))
Cost(H[S U { (21, 11),),Sx {z1])
S (unroll from j- using (v/ #1) = for i < and
S 111) *1) + Cost (Hoss(HH[SS) ((),
u (mi)nn)
= + Cost Cost(Hl (0 v/) | Sx U {
(2)
(o) : We may use the non-decreasingness property to unroll, because from non- decreasingness, for all I j. Cost(H[S ((2),,)))) Cost(H[S), Sx) 2 + 2 2. Therefore, E(HiS u ( (2%, hul. U fa 2 2. and we have that:
Cost(H[S U {(2,, v4) 1.l. Sx U (x()ta)) min max (1 # Cost (H{SS ((d))))) u ((,,)) u f2t) (x))
Continuing equation we get that: n S Cost (H()) 5x) - < Cost (HS((H(SSU) ((11.1 (.g) Sx f2 1
By induction hypothesis, there exists h E H(S U (1/ v() 1ss1 and Tú. such that when A interacts with Tp (after obtaining query history S { (0 v/) 11g) and with label budget nt the final version space is of cardinality at least two:
E(H[S> (H)[s (Sx) 2
In addition, when interacting with Th. A obtains history SU { v/) ) in its first [S|+] +j rounds of interaction, which implies that obtains example sequence S in its first [S] rounds of interaction with T3. This proves the first property also holds and completes the induction.
Now, consider the the final j satisfies V/S =1. This means that the other exit condition must hold: Seerm (L) TRUE. And so, terminates with all abstentions: 1/1 =1 for E [j].
As above, iteratively the non-decreasingness of Cost with abstention of = get that:
n n < Cost(H[S],,Sx) < - (os)(H((L),xx)
for the final state L[
From this, we have that [E(H(L), Lx)] 2.
Pick some E E([ Lx). As the prior Th construction, define T₁, so that: Tx(x) for all (z, E L, and (x) h(x) for all x E X Lx.
By construction and Lemma B. Ti, interaction with induces L.
Since fterm (L) = TRUE, S = L. And so, [E(H[AA (Sx)AT)) [[H[L], Lx)l 2, satisfying the second condition.
Finally, since A's interaction with T,, generates L, the first ||| steps also matches S. This satisfies the first property.
16

---

Published as a conference paper at ICLR 2024
Proposition B.4. For any deterministic, exact learning algorithm A. Cost (H,, 2 Cost(H, 0)
max HE
Proof. From Prop. B.3 we know that for Cost(H, 9) - 1, there exists some h E H. and T E Te such that EEH (Sx) AAT)) 2.
We construct labeling strategy T" that yields least N + 1 binary labeled examples as follows:
1. Let (x) = Tx)) for x E S
2. Let (x) = h(z) for z E X SA..
Note that 7 is identifiable oracle for by construction.
And so, we have that:
max
(ostA,T(HH,0 C.st (H, 0)
AEH,TETA
N + C (HIS 1((x))
(o)
Cost H, 0) 1 1 Cost (
Cost(H, 1+1
(00)
Two steps in the above derivation are justified follows:
(o) : Since (x) T(x) for x SAT by Lemma B.I we must have that SAT S.A.T and =Sx)
(Sx) A.T A.T
In particular, note that this implies |E(H(S (Sx) ( )= (F(H)#*") (,(x)))))))))) AAT ) 2 2
(oo) Since is an exact learning algorithm, does not terminate at the s step, because IB(SAT" (8x) )) 2.
And so, AA will make at least one more query on some x E X²' X' SAA." Since T' (z) # any any x E X
SN SAA,T" and T" is identifiable (yielding terminal cost 0), we have that (H ATT 1.
(Sx) AT)
17

---

Published as a conference paper at ICLR 2024
C PROOFS FOR SECTION
C.I EXAMPLE-DEPENDENN COST SETTING: DEFINITIONS
In this section, we consider the following generalization of our learning setting that allows each binary label to have varying cost dependent on the feature x:
A cost function X' (0, +o0) is known both the learner and the labeler ahead of time.
The learner is interested in learning hypothesis h* in hypothesis class H. C (X' + {+1,-1} over a finite pool of unlabeled data N. collected by the learner. cost function The labeler knows h", and responds using labeling strategy with response T(x) (,),,,
The learner repeatedly interacts with the labeler adaptively, and makes label queries on unqueried example z, and incurs cost c(x) if (x) m and cost 0 otherwise.
Note that the setting studied in the main text is a special case with cost function = 1. We aim to analyze the following generalization of Algorithm
Algorithm 7 E- VS Bisection Algorithm
Require: Data pool X, hypothesis class H.
1: V < H. S +-g A
VS, queried dataset
2: while (VV and Sx # X do
3: Query:
D Maximal E-VS bisection point
E(V, (xx) v)]
x arg min max Sxx yet 11++
c(x)
4: Labeler T provides label response: y E 1-1,+1,,1
5: S +- S SU (z,
6: if y + then
7: V- V((2,y) y)]
8:
return h, the unique element in E(V,
For the analysis below, slightly abuse notation and let c(2, y) denote c f1), the of querying example æ and receiving label feedback y. Definition C.1 (Generalization Definition
3.T). Given H. X and cost e, define the global identifi- cation cost of version space V C H and example set S as
GIC(V,Sx) inf R VT: X Sx
11,,
EΣ C X Sx s.t. Σ
Eclx,T(x)) SA ( UE) 11}.
WEX
Definition C.2. Define l'v.sx NN- + (TRUE, FALSE] as:
L'v.sx (t) x - (-1,+1,, EE C X Sx EdI,T(<)) &tA UE) S
ZE
Note that V.Sxx is monotonically increasing: for é1, t2 E i,ff < t2, then l'v.sy (t1) - l'v.sx (62).
Also, with this notation, GIC(V, = inf {1: Tv.sx (1) = TRUE].
We have the following definition of all possible cumulative cost values that appear in the learning process.
Definition C.3. Define C = Ele Sc
18

---

Published as a conference paper at ICLR 2024
Note that C' is finite set since X' is finite.
The following lemma implies that the set {t Tv. (t) = TRUE} is left-closed interval.
Lemma C.4. If (fn) t and Tv.sx (fn) TRUE all n, then vv.s (t) TRUE.
Proof. Since {tn} $ t and C' is finite set, there exists large enough such that for any 2,
2 2ECA2 tn
2 2tt.
Importantly, since for any T X' Sx - (-1, 1,, X Sx. Exex cx, T(x)) E C, we have:
E(,
(x, (x)) S In
Σ Ed,,, T(x)) S2 BEΣ
ZEB
and therefore, for any X Sx 7 +-,,+ there exists C X \ Sx such that Exer cxx, Tx)) < to (and thus Even (I,TT(() t) and [E(V[((2), Sx U EY I 1, proving that I V, (t) TRUE.
Remark C.S. The above lemma implies that in the definition of GTC, the infimum is achieved in the set (t: Lv,sx (t) = TRUE}. In other words,
GIC(V, = min {t Tv.Sx (t) = TRUE}
And therefore,
GIC(V,Sx) N = Tvsx (N) = =TUUE
: X\ |8x + f-1, 3E Sx, Σ
c(c,T(()) S N ( [(V[T(())) Sx UΣ S
.EE
and
GIC(V,Sx) N_ - Tv.sx (N-)- FALSE
:7:2' X. 8x + f-1, +1, 11, Sx, Σ c(c,T(()) S BNNNNN--EVVVVO Sx 22
#E
C.I.1 LEMMAS
We prove several lemmas on the properties of E- VS and Cost.
Lemma C.6. For any V C H and Sx C X,
E(V,Sx U (x" E(V,S))
Proof. It suffices prove that h B(V, Sx U (x*}) + WE B(V,Sx)
To see this, let h E F(V, Sx (xx) Then, wh' E EV\ (V()). ((((((())))) Sx) \ fx² (x²))) + (((()))))
(x* = Ah' E EV (b) M(X') (x) N' \. Sx). This implies that h E F(V,Sx).
Lemma C.7. We have the following:
1. For any x E X Sx and y E [-1,1],
((V[(z,))), Sx (x})) = B(V, Sx)[(x, w)].
2. For any set of binary-labeled examples W C (X' x (-1,1)),
F(V(W), U W) F(V]Sx)(W].
19

---

Published as a conference paper at ICLR 2024
Proof.
1. We have the following equivalence:
h E Sx (z})
+ h E VI 3) A Vh' E V((x, y)1 #1= * h(x ( (z)))
- h hEVA = V E [( (xx) + (xx)
= heVAA yy E EV. ,h' ( * 1(x Sx)
h(x) =yAh E(,
- h E
where the first equality uses the definition of effective version space; the second equality uses
the fact that for h, h' E V[[2. v)l. h' (Sx (xx)) * h(X \ (Sx U {x})) is equivalent
to N'(X) 5x) * h(X Sx): ): the third equality follows from that for h such that h(x) = y-
for all h' E V such that h'(x)= * y. ((xx) & h(r) and therefore h'(2' \ (x)) & h(X' Sx)
holds trivially; the fourth equality uses the definition effective version space; the last equality uses the definition of version space with respect to labeled examples.
2. The claim follows by induction [W|:
Base case. If [ 1, the claim follows from the previous item.
Inductive case. Assume that (VV(W"), .x W") E(V,Sx [W"] holds for any W such that [W|| n;; Now consider any W of size nı; W be represented as vz) UW"
for some (Ir, E X' x [-1, and [W'|
1. We have:
E(V(W), Sx U W) =E(V[W"][<=. www U {z}) (Definition of version space)
- v]]
(item 1) (Inductive hypothesis)
=E((V =E(V,55)\["'I(<>, y)]
=E(V
(Definition of version space)
This completes the induction.
Lemma C.8. EVV, Sx) + 0 iff Cost(V, Sx) 2 0.
Proof. (=) From the first terminal condition in the definition of Cost, we know that E(V, Sx) 0 Cost(V,Sx = oo < 0. So (V, 2 E(V,Sx) #
(=) By backward induction on |Sx]-
Base case. If = X, |E(V Sx) = o 1. If EVV, Sx) = 1. we have by the base case of the
definition of Cost, Cost(V, Sx) Therefore, E(V, Sx) * 0 Cost 0.
Inductive case. Suppose E(V, Sx) ن (1 + Cost(V, 2 0 holds for any dataset Sx of size zj + Consider Sx of size j and V such that E(V, SxV * (::
If (E(E, = 1, then Cost(V,Sx) 0 0.
Otherwise, [x(V 2 2; take hn E(V, Sx); we have Cost(V,,Sx) 2 min (Cost ([))) (x]) +1)
By Lemma Cost(V h Sx
C.7 hy E (VV (n)), Sx {x))) by inductive hypothesis,
U (x)) 2 0, and therefore Cost(1 VV Sx) >2)2 1220 0.
In summary, Cost(V,S3 2 0.
This completes the induction.
20

---

Published as a conference paper at ICLR 2024
Taking the contrapositive of the above lemma obtain the following corollary. Corollary C.9. Cost(V, 5x) = -00 iff E(V, 5x)1 = O. (V, (V, 5x) 2 1.
Lemma C.10. [V,V, [x)]
Proof. (+) From the first two terminal conditions in the definition of Cost, we know that if [E(V,x) < = Co Sx) S 0 and so, (V, 2 = [x)) 2
(+) Let h1 E B(V, Sx), consider labeling strategy ((x) = hn (z) for all x E X \ S (i.e. never abstains).
Following the definition of Cost(V,Sxx) we have
CV, 2 min (Cast(V[(c..h(()))))>>> (x]) 1))
Also, note that by Lemma C.7
(z,) (z)) E h (x))) e h1
Therefore, by Lemma C.8
for every z,
0, and thus Cost Vx)
Because Cost(V, Sx) can have three possibilities: Cost(V, = = 0 2 1
and E(V, Sx) having
0
three possibilities: |E(V,Sx)
the above two lemmas yield the following simple corollary.
2 2
Corollary C.11. Cost(V, (V, Sx)
|B(V, = 1.
Proposition C.12. For any V. [EV, X0] < 1.
Proof. We consider three cases:
1. V = 0. then EVV = 0
2. If [V| 1, then E(V,X) = V
3. If [V] 2 2, then F(V,X') = 0.
This is because for any h E V, consider some N' \ (h). // trivially agrees with on X' \1 X = 0. And so, h(0) = h' h'(() = h & E(V.)).
In summary, all three cases, E(V, X)I 1
Lemma C.13. Algorithm 2 maintains the invariant that GIC(V,Sx) < GIC(H, 0).
Proof. It suffices to show that GIC(V, Sx) is nonincreasing throughout. In other words, after obtaining queried sample (x, (x)) during an iteration of the algorithm,
(IC(V U (x)) S GIC(V,Sx)
(3)
Denote by t = GIC(V,Sx) It therefore suffices to show that, for any oracle : :x (XX( {-1,+1, 1), there exists Σ' X' \ (8x U fx)) such that:
+
Σ cl T()) L ( ZED
c(,
1
(4)
Below we construct such E' for each TV
First, define oracle T: X Sx - 1-1, +1, 1) as:
f(2)= = T(x) ==r r
T'))) z
21

---

Published as a conference paper at ICLR 2024
By the definition of GIC(V,Sx). for this T, there exists E such that:
cl S B(V 1
(5)
ZE
We now construct >" by considering two cases of Σ respectively:
1. If x E Σ, we construct V" E {z} Note that Exer S de,
4, and by the definition of T,
EVTTTT (x
Sx
and therefore has size -
2. If x & Σ, we construct E' = E. Note that EzEr dx, (x)) (xe S
and:
=E(V)(()) Sx (x))
(since T'(E') = T(Σ))
CE(VITE)), Sx U
(o)
and therefore has size <. 1. Here, for the last inequality (o), we use Lemma C.7 (for when
T(x) E (+1,-1}) and Lemma C.6 (for when Txx) =1) which implies that for any FC H. and unlabeled examples U. ((F
{x}) E(F.U).
In summary, there always exists >' that satisfies equation (4. and therefore equation L3 holds for every iteration of Algorithm 2 This concludes the proof of the lemma.
C.2 MAIN RESULTS
In this section, we prove the generalized version results in Section 3 which examples may incur differing costs.
Lemma C.14. For any V,Sx such that GIC(V,Sx) is finite, Er X Sx such that:
Wx), U (x))) - ([E(V, 1) (1 (10 (--IC(VV55)
c(x)
yE 1,+1)
Proof. Recall from Lemma C.7 that we have: (VV[(x, v)1, 8x U (x})) E(V, y)].
suffices to prove that there exists E X Sx such that
max (IF(V, v) = ( -1) (1) (1- vE(-1,+1)
c(x)
GIC(V, )
Also, note that (EVV, Sx)) |E(V, 1)]1 [V( Sx)[(x, as E(V, Sx)(x,, -1)] and E(V, Sx) [(z, +1)] form a disjoint partition of Ex).
And so, equivalently, it suffices show that there exists x E \ Sx such that:
[V(V GIC(V, Sx)
min (E((V,))((z, -1),) E(V, +1)]) 2 c(x)
So, assume towards contradiction that the statement above does not hold. Then, we have that Vr E X Sx:
E(V, (x))
min - E(V, +1]]) < c(x)
(6)
GIC(V,
22

---

Published as a conference paper at ICLR 2024
Define oracle To : X |xx - (-1,+1,11 such that,
To(x) arg max mag (E (VV,S))(( yE(-1,1)
With this, for every subset Σ S X Sx such that ExEr ((, < GIC(V,Sx) we have:
[x UΣ] [ZVV)))
(Lemma C.7 item 2
[EVV - 1[h E(V, 3r E + To To(z)
(Set algebra)
2 |E(V,
Σ
E(V, Sx) -T(x)))
(Union bound)
xE
[X() - Σ
min
[(V y)]l
-
(by definition of To(x))
[E(V - Σ c(z, (T())) Fx),8x)1
GIC(V, Sx)
SES
(by Equation 6
and c(x) cx, (z))) since To(x) E (-1,+1])
EVV Sx)l (LE(V, Sx) 1) =
In summary, the constructed oracle To is such that for any Σ S X' such that Eeey c(2, [o())) S
GIC(V, Sx). [T. (E)), Sx U Σ)] > 1. Therefore, Tv,sx (GIC(V,Sx)) FALSE, which
contradicts the definition of GIC(V, Sx))
Lemma C.15. For any H and Sx C. GIC(V,Sx) < Cost(V, Sx)
Proof. Let and k: GIC(V,5x) - e. By the definition of GIC, Tv,sx (k) = FALSE. That is:
TT : x Sx + (-1, +1, 1), V4 S X A Sx. Σ E((x,((x))
T(x)) < k = (E)), Sx U UΣ) 2 2
DEE
(7)
Let T be labeling oracle that satisfies the properties in equation Let U be the output of executing the following algorithm that simulates the interaction between a specific label query strategy and the oracle T before a stopping criterion is reached:
Algorithm 8 Simulation process on letting T interacting with targeted label query strategy
U 0 while U * X') Sx and ExEU c(z, T(x)) S k do Choose example
I arg min (Ex
max
dx v) + Cost
(8)
U - (z) return U
We first claim that Exev clx, T(x)) > k. Suppose not, we have ExEU ((xTT(x)) < k. By the
stopping criterion of Algorithm 8 we must have that U = X' \ Sx. In this case, by equation (7). [E([ Sx UU) = (VV (U) 2 2. However, this contradicts Proposition C.12 that for any V. [E(V[T(U),, X'I 1. Therefore, ΣzEV c(x, T(x)) k.
Denote by T1...., Em the sequence of m examples queried by Algorithm g with this notation, U {.1,..., Fm }. Also, for i {0, 10. m.....,m............. denote by U, == (i { F.) the set of first examples queried, with the convention that Un := 0.
We make observations:
23

---

Published as a conference paper at ICLR 2024
For any i E {0. 10......,.e 1}, by the loop condition, Exeu, c(2, ((=) k, therefore by equation (VV[)(U)) U UU:) 2 2, and therefore, by the definition of Cost, Cost(ViT(UU)) - min =EXV(S)UU) vE(-1,+111) (c(x,)) +
max
UU,
(9)
((tm) #L. This is because Ei= clai, T(xi)) S < E c(z;, T(:)). implying that c(Tm; (Im)) > 0. Furthermore, by our notation that c(z, = c(z)1 #1),
m-1
Σ cl T(x:)) + d(Em. -1) Σ
c(2,, T(x)) + dam. +1) > k.
by equation 7 also have [ 2 2 and by Lemma C.10
Based on these observations, we have:
Cost(V, Sx)
min max (c(x,)) ) + Cost(V]((z, ()) Sx U {x]))
(Eq. with i 0)
=EX'(Sx -
vE(-1,+1,1) (c(x1, Cost U (x1)))
max
(Fq. g
2 201 T(x))) + Cost(V U1)
=(1,, T(xi)) + min max (c(2, Cost (VS((i()))) v),, Sx Uu U (x)))
(Eq with 1)
m-1
Cott))/))))) U U
(Repeated application of Eqs. and 8)
c(2,, ((xi))
min TEX((SxUU, vEI-1.-1.11 (c(x,)) v) Cost(V/TUU Sx U U fx)))
max
((;;)( +
max ve(-1,+1]
(c(#m: v) + Cost(V y)}, Sx U Un {xm)))
(Eq. and restricting the choice of y)
Σ daa T(x))) k
Here, in the second last inequality, we use the following observations: first, for any c(ums -1) c(xm, +1) c( T (Tmm)) second, [E(VVT(Um)))) Sx U U 1)] 2 2, which implies that there
at least one E [11 such that (FVV(T(U v)], 5x Un-1 (x))) 2 (recall
Lemma C.7). and therefore
Sx UU (ost(V([(Um= Sx
U (x)]) 2 0.
In summary, for any >> O, we have shown that Cost Vx) 2 GIC(V, - c. The lemma statement follows by letting 0.
Li
Theorem C.16. If Algorithm innteracts with labeling oracle T, then it incurs total query cost at most GTC(H, 0) In [H] + 1. Furthermore, if Algorithm interacts with an identifiable oracle T consistent with some h E H. then it identifies ht.
Proof. First, we show that Algorithm 2 terminates and correctly identifies h" when interacting with an identifiable oracle of h², Its termination can be seen by the fact that the size of Sx is increasing by for each iteration and Sx # X' is part of the stopping criterion.
We now show that when it returns, F(V,Sx)) (h*). This can be by:
24

---

Published as a conference paper at ICLR 2024
As T is identifiable oracle that is consistent with h", the algorithm maintains the invariant that h" E EVV, Sx).
This is because if some point h- & S(V.Sx) then exists some h' * h- in V x[](Sx) such that l'(X' \ 5x) = h'(X' 5x). Then, we combine with that H E H(T(Sx) get that h' E
C ((T((x))T((2)55)
H(T())),
which is in contradiction with that 7 is an identifiable oracle.
We claim that when it returns, |VV Sx)l = 1. Since the E-VS always contains h", we must have [V(V, 5x) 1.
And so, if it returns, we have the condition of the while loop being false, i.e. we either have (V(V, Sx) < - E(V 1, or Sx X = Sx)) thanks to
Proposition C.12
Next we bound the query cost complexity of Algorithm 2 when interacting with any labeling oracle.
Denote Vi and S; as the value of V and S at the i-th iteration, and denote (æz, y/) by the example (ar, y) obtained the i-th iteration. We denote (S:)x as the unlabeled part of S..
Therefore, V++1 [[(n v:]] and S441 S; U (3re, w:)}.
We claim that
(S 1) ( (FVV. (8.)x) - -1)eep ( cai, Wi)
(-
(10)
To see this, we consider two cases:
1. If y f ff-1,+11, then applying Lemma
C.14 with V = Vx (S,)x, xI Hs we have
max (VVV vE(-1,+11
(IE(V((EA))) (5+11xx) -1)
([I - (1 (1- c(x;)
GTC(V (Si)x)
(Lemma C.14 y (-1,+1)
c(ara)
(IE(), - GIC(H, 0)
(by Lemma C.13 GTC(V, (Si)x) < GTC(H,
c(a:))
< ((V, - exp
GIC(H, 0)
(since - x S a))
2. If y =L. c(2,,)) = 0. Therefore, to show Equation (10), it suffices to show that (S+1x) S E(V, (S.)x). This follows from Lemma C.6
To summarize, equation 10 holds for each iteration i.
Consider the last iteration in before the termination condition is reached; note that by the termination
criterion, the penultimate E-VS is such that E(V,, (Sto)x) 2 2. We now upper bound the total
cost up iteration ig 1. By repeatedly using equation (10) for i 1...., 20 1, we have:
1=i c(2,, v1)
1 < E(V (S..)) x
E 0) exp
GIC(H, 0)
Therefore, io-1 c(z;, vi) < GIC(H, 0) In | (since E(HL 0) = H.) and:
c(r,, v.) ct V%o + d w) < GIC(H, 0) In |7 +
25

---

Published as a conference paper at ICLR 2024
D PROOFS FOR SUBSECTIONS 3.1 AND 3.2
D.1 COMPARING VS VERSUS E-VS
[w', 11, w/ E 1) We observe that, for any set of points X, X' divide polytope W = w = [w', 1] w E [0, 1] into clusters, where every point in the cluster has the same labeling of X. Thus. without loss of generality. we can treat each cluster formed by X' as an element of H. and H comprises of all the clusters that lie in polytope W. In this setting, the (conventional) version space is single convex polytope, which we may access by sampling using any polytope sampler. The structural lemma below illustrates that, by contrast, the E-VS can be more complicated object to access.
Consider the case when H is linear: H = ( biign("aaa x)
Proposition D.1. There exists an instance space X C 12d and query responses S such that the resultant E-V is union of (id) disjoint polytopes.
Proof. Defining the Instance Space: We construct X' that allows us to easily reason about the E-VS. Consider any 3n positive reals of for [n]] E [3] such that 0 < af ag < aig
ag < 1.
Define 2/hx = [- af]] for E [d]. As a concrete example, zig [-1, 0, O.... ag).
Define the instance space to be X = fatale li E [4,. E [m], k E [3] With X' defined, we see the clusters of W formed by X (referred to as cells subsequently) consists of: x where I = {10, at), [at, ab), [a}, a.,,..., [a,,,,,,1111 1]]-
-)li ) [4.j [m], k 1o:k=22 2}. Note that then Sx Now, define the interaction history S = 1
(zfali E [d].j [m], = =2].
Characterizing the E-VS: We first claim that for any cell with one of its faces a subset a hyperplane in Sx cannot be in the E-VS. Specifically, if there 3i [d].j E [rx] such that wy E [a ag). then the cell w belongs to is not in the E-VS.
To this, WLOG w. [a ab]; the case of wa [a ag] can be analyzed analogously.
Now, construct [W1, ..., Wi-1 1, ths wi+1....1] for some w; |a ag]. Note that by construction,
w' does not lie in the same cell Then, we that (ug x:) = sign( (TTT x)), Vo X \ m
And so, since X' \ Sx S X \ 2 we have that w(X' \ Sx) w'(X' Sx) w & E(V, Sx).
This means that only the of disjoint cells x where I' 10, at), [a at ... la 1]} can be the E-VS. Next, we will argue that the E-VS all of x -=_
Consider a classifier corresponding to some cell e E XL= Consider any other cell classifier corresponding cell c' xL_1. /. Since e d', there must be at least one dimension, WLOG such that с and c' belong to different sub-intervals, when projected onto coordinate i.
We know that along dimension i, c's sub-interval is either of the form [0, atl, [a af for some j. or [ag. 1].
We see that in the first case, wi E X') \ Sx must separate e and e', since c(x) +1 + - (x). Analogously, in the second case, either z3j3 or a(1+111 must separate and c' (with both such points are in X' \ 5x). Finally, in the last case, 2/ X' Sx must separate and c'.
This shows that all of x there in total (n 1)d number of disjoint cells, corresponding to distinct classifiers.
I' is in the E-VS. And so, since I' comprises of n + disjoint intervals,
D.2 E-VS MEMBERSHIP CHECK
The key idea behind the membership check h E E(V,Sx) (lines 2 to in Algorithm 3) is that want to find hypothesis h in V, different from h, that agrees the rest of the unqueried
26

---

Published as a conference paper at ICLR 2024
Wa
Figure 2: Geometric view of the linear hypothesis class in dual space (as in Tong & Koller (2001)) p).
with examples as hyperplanes and hypotheses as cells, illustrates: (i) Abstention example 2 (hyperplane in black) renders hypotheses wa1 and W22 (cells of the same color) indistinguishable from each other. this way, abstentions can carve up the VS (single polytope) into multiple polytopes, as in Proposition 3.5 (ii) In the approximate identifiability game (Subsection (.T). if xn is not in pool X", then induces clusters merged (Wir. W:2) for E [4]. The goal then to only identify up to clusters (e.g. the blue cluster of {w21, W22 }), instead of the exact hypothesis (e.g. cell W21).
samples. If succeed in finding this h, then this means that even if all of the remaining unqueried samples X' \ Sx is labeled, and h cannot be distinguished from each other. This implies that is non-identifiable and does not belong to the E-VS.
Proposition D.2. Given some h E and access to a C-ERM oracle, lines to in Algorithm verifies whether h E Sx), with one cull to the oracle.
Proof. Firstly, note that by definition, Yh, N' E HH = h(x) 12()).
Recall that in Algorithm S denotes the set of examples in Sx which the labeler abstains. Now, we rewrite the definition of h E V not being in the E-VS:
h & Sx)
W EV \ ( (xx) = M(X Sxx
3h h'xx \. ) hh(Sx \ \S") AN # HA()) Sx) h(x 8xx)
\(x)
#3h (8x \ ) =A(Sx \
Sx) 1(2) \Sx)
A31, 3x+ E stt 1'(Sx (18)=1(( \ ( h(=+)((++))))))) A H/ (x') (Sx) = h(x2' \ Sx)
And so, we may check for the existence of such a with one C-ERM call on H. given some E V. using the following program:
min MEH #'ESL
Σ (N
(11)
s.t h'z)) h(x), Vo E X St
This may be emulated by defining data Z, {(z -(()))) nESL Ze = ((x,((x))) sEM'sL and calling C-ERM on Z1, Zz to compute arg min crr(h', Z1) : h1' E H, Z2) = 0}. It can be now seen that: if C-ERM outputs h + h, then & F(V, Sx); otherwise, h = h and therefore h E F(V,Sx).
D.3 CONTRASTING E-VS BISECTION ALGORITHM WITH VS BISECTION
D.3.1 PROOF OF THEOREM 3.8
In this section we prove Theorem 3.8 showing an exponential gap between our new E-VS bisection algorithm and the conventional VS bisection algorithm.
Setup:
Our example will revolve around hybrid hypothesis class of thresholds and inter-
vals. Let 8. Our instance space X' X' U X2. where Xi
1
2n
and
2m ....
X {1 ..... 1 2n-1] Note that X 2(n 1 1).
27

---

Published as a conference paper at ICLR 2024
Let fi (-00, (+1,-1] denote intervals of length 1/n, f(()) 1 (z E [(i 1)/n, a/nl) for
i E n -0 1].
Let f/ (00+ - [+1, -1} denote thresholds, ff(x) 1(x 2 1 i/n) for [n].
Define H = Ui=l ( he }. where (z))(()) = [(x);
x x
(xxx,
x x>
D.3.2 ALGORITHM ANALYSIS
Under the paired therrsllthresholdd setup, compare the algorithms based on the number of samples queried before termination.
In the case of the VS-bisection algorithm, it queries the point that maximally bisects the VS each time. Accordingly, the algorithm terminates when there no point that can split the VS. This arises either because the set of unqueried points is non-empty but the VS agrees all their labels, the set of unqueried points is empty.
While for the E-VS bisection algorithm, it terminates either when the E-VS is of cardinality zero of one.
Lemma D.3 (E-VS VS bisection algorithm query complexity). In the paired interval-threshole hypothesis learning setting, the E-VS algorithm incurs O(log n) sample complexity against any labeling oracle.
Proof. Define p(E((,Sx)),) min.g(++1-11) (VV,
1. Let U2 C X22 denote the unlabeled part of X such that U2
[x: p(E(V,Sx) > x E X2} (i.e. x E X2 is in the disagreement region formed by the current E-VS).
Definition D.4. A point x U2 is balanced if there exists three-point segments with x² +//n = + 1/n x.42. x
22/n x2
25 + 1/n 2 such that x?? < x < zj.
where points x; - 2it2 E U2, and x3 2 j+1 j+2 U2.
We have that, if: a) is balanced point
b) all queried points thus far have been in X2, then:
((E(V,5x), 2 2 max p(E(V,Sx)),)) x' d'Exi
This follows because if no points have been queried in Xi x², x241 2242 E U2 implies that h (f and h E Ex), Similarly, x².. 2 So and his4a15f12 E E(V,Sx)
J+1 2 E U2 implies that
Since 2f42 <x x3, the pairs of models disagree x (in the second coordinate).
And so, if there some point x E U2 that is balanced, and all points queried thus far have been in X2 then the E-VS algorithm will query a point in U2 (we assume that in tie-breaker, the E-VS algorithm will select the point in X2).
2. From Lemma D.5 we have that the E-VS algorithm will query some point in U2 S 2' so long as
Un! 2
The number of binary labeled samples needed to reach U12| < 7 is at most log This because abstention decreases [12] by while a binary label removes [|U2|/2] points from U2.
And so, since U21 n, there can be at most log n binary labeled examples before [U2
3. It remains to count the number of binary label samples needed when [Ua] < before the interaction finishes.
28

---

Published as a conference paper at ICLR 2024
We note that if [Ug] < 7, then the size of the Sx)] 2 2-26-4 6 + 2 (since it always holds that (E(V, Sx) & 2 + 2).
As each binary label point removes at least one hypothesis from the E-VS, at most 11 more binary label points are needed.
In summary, have that the E-VS algorithm incurs Olog n) samples.
Below are the deferred lemmas:
Lemma D.5. Uf2 2 7, then the E-VS algorithm will query some point x E U2 S X2.
Proof. We will show the following properties about U2, which is U2 at the tth step.
If [US] 2 7, then:
U2 is of the form {ai b1} U {b2 a2), where b1 S by {ai b1} is used to abbreviate {a1,a1 + 1/n.-.,b bi 1/n, b1
ii) Some x E 62) satisfies the following: || {2 E U3::: x 1-1-1 {a' U3 11
iii) No points T1, .1...... Iz-1 will have been queried from X2.
iv) E-VS will query some point U11 at step f.
We will see that, at step 1, proving property i), ii), iii) proves iv), which is the desired result.
We prove by induction on j. the number of queries, that i), ii), iii) and thus iv) holds.
Base Case: When j = 0, no points have been queried from X2. And so, properties i)-iti) are true with U2 (1 + 3/2n 1 + (2n 1)/2n]. Since > 8, 1U2] |22g| and so Lemma D.6 applies,
meaning iv) is satisfied.
Induction Step: Suppose that if [Ug] 2 7, properties i)-iv) holds for time step j = O,.., 1.
Now consider time step j = k. Suppose | 2 7.
This means that, at time step & 1, |1/ | 2 U (since the disagreement region only decreases in size).
From induction hypothesis, we know U satisfies i)-iv). Let U fat : & u (b, de Since iv) holds at time j k 1 (#X-1 X22), combined with that iii) applies at time k - Th-2 (Ii,,.., E X2) implies property iii) holds at time j = k (I1,
Tk-1 Tk. E 22)).
Since iv) is satisfied at time step k 1, we may WLOG xk-1 84. There are cases to consider:
If a label is given for -g then we know that U/ is either {at b1 - 11/n3 or (b2 a2). in either case, both i) and ii) are satisfied at step j = k.
If an abstention is given for 2g-1, then we know that U = {at : B1 - 1/n] u (b/ ab). which proves i).
Since -h-1 = bn. we have that {af
: d5 1.
IF 16 : d 2 Ha &1.11 picking b2 satisfies the property, else picking & - 1/n satisfies the property. And so, property ii) for Už holds.
Finally, since iii). i) and ii) holds for U using Lemma iv) holds at j k.
D.6 we have that 24 E Xz, which means that
Lemma D.6. Uf 2 7, and i)-iii) holds at step t: the E-VS algorithm will query one of by, by U..
Proof. Due to ii), we know at least one of b,,b2 satisfies 11 U3 x' < <x>>
Kx Ug xo x) || < 1.
29

---

Published as a conference paper at ICLR 2024
WLOG let this be bı (assume that br wins the E-VS algorithm tie-breaker if both b1, b2 satisfy this condition). We claim the E-VS algorithm will query b1.
For points X2 \ Uz they are not the disagreement region and ((E(VSx)) - which means they will not be queried.
For points in U2, have the following observation.
Due to i) and iii):
((EVVSx), = min(2 - Hx's U3 : <' < 1
= 2 min( { E < -f
From this, we can see that from ii),
b1 arg max min( { E U3 x' < <z E U. >>>
=EU;
arg max p =eU;
For points I E Ai.
We know that |U 2 7 min() (a' US xd < <b ( E b1)1))
Due to we know that {a' E U$ : < and fa' E U3 x'
> 61} are contiguous. And so, one can find three-poine segments to the left and right of b1, which means that by is balanced.
And so, p(E((, 2 = m (E(,,Sx),2
In conclusion, b1 is the point that maximally bisects the E-VS out of all unqueried points, and will thus be queried by the E-VS bisection algorithm.
Remark D.7. In closing, we note that the construction is nontrivial in that the same result does not hold if the hypothesis class is simply H = (o
1.fh-11-
this case, the E- E-VS-bisection algorithm will also have a linear label complexity, as abstention from U2 does not result in reduction in the size of E- E-V.. For a formal justification of this, please refer to the proof of Proposition I.]
Theorem D.8. There exists H and X such that the number of labeled examples queried by the E-VS bisection algorithm is O(log ()) while the VS bisection algorithm queries (((x)).
Proof. From Lemma D.3 we have shown the first part of the theorem. It remains to analyze the VS bisection query complexity.
VS bisection algorithm complexity: By contrast, we show that there exists labeling oracle that induces (2) sample complexity from the VS algorithm.
This labeling oracle T is as follows:
T(x) =1 for all x E X2
ii) T(x)= = - for all E X1
Under 7', we have that labeling each point X; removes two hypotheses from the version space at any step in time. Namely, labeling x! = 2n
2 0) removes h fuuffinn
And so, | 1 samples E X, will be queried. Because if there exists two unqueried points =! E X1, then h,.. and h are both in the VS. This means that the disagreement region is non-empty, and in particular contains both x/.
30

---

Published as a conference paper at ICLR 2024
Since each &r is given binary label by T. the VS bisection algorithm incurs cost 1. We note that in the end the VS will be of size 2, but the remaining sample in X1 cannot distinguish between the two.
We may also obtain a corresponding result for an identified setting, by tweaking the above setting slighty. In this setting, still find that the VS-bisection algorithm still incurs an exponentially larger sample complexity relative to E-VS bisections.
Proposition D.9. There exists a H. X. and a labeling oracle that leads to identification, and the number of labeled examples queried by the E-VS bisection algorithm is Ollog (x)), while the vs bisection algorithm incurs (1) samples.
Proof. Setup: Let X = X4 U (2), where Xi = {x] 2 x = {
{L
2n-3
}. X2
2n 3 ... 2n
{1 2 =
...,, + _ }, and i 1. 2n So | = 2(n +1
Let the f: [=1[-1,]] + {+1, -1} denote intervals of length 1/n, f((x) = 1(x E [(e - 1)/n,2/n) 2/ml)
for E [0,1,..,,0-] 1}.
Let J. (1,2) + {++1, -1} denote thresholds, f((x) = 1(x 2 1 i/m) for i E [n].
Define H Un ( kanntn Ju (Noo..). where (z)r(() f(x), x
(x), x>
Ensuring identifiability: Note that obtaining labeled example (ō, +1) identifies h == fo
E-VS bisection algorithm complexity:
Note that for any Sx, ((E((,Sx) 5) 11
And so, in the case analysis of Lemma D.6 again find that long as UU2 7, the E-VS algorithm will query some point x E U2.
Thus, the E-VS algorithm will query most log labeled samples before reaching [U2] < 6, at which point the E- contains at most 2 6 + 2 hypotheses and will thus require at most 13 more labeled examples before identification.
VS bisection algorithm complexity: We show that there exists an identifiable labeling oracle that induces ((n) samples with the VS algorithm.
This labeling oracle T goes as follows:
T(x) = for all x E X2
ii) T(x) = for all x E X1
ii) T()) =1
It is clear that M[[(()) = { and T is an identifiable oracle.
The main observation is that while [Sx n& < |&g - 1, if point in X' \ X₂ is queried, then it will be a point in Xr, and not J.
This is because & for any V.Sx, is such that p (FV,V (x),, = 1. While for any x E Xi \ Sx, p(E(V, .x) 2.
In more detail, if x! & 5x, then hy hiffe, E V[S]. whose label for x: is [1, - 1]. And when [Sx n. < |& 1, there exists least other models in V[S] that label x with [-1, 1].
Hence, since T never abstains on x E X2 11.1211-1 labels will be given, at which point the disagreement region is still non-empty. Then, the algorithm either queries the ă or the remaining element in X; depending the tie-breaker, both of which identifies h.
31

---

Published as a conference paper at ICLR 2024
D.4 COMPARISON WITH EPI-CAL
EPI-CAL (Huang et al. 2016) a "mellow" active learning algorithm that can handle labeler absten- tion in streaming setting, wherein the learner cannot control the query order (unlike Algorithm (2), and performs PAC learning (Valiant 1984). Despite the differences between this and our pool-based setup, we can nevertheless analyze what happens when the labeler strategically abstain. Our finding is that strategic labeler can again hold up learning and induce an arbitrarily large query complexity, when the data pool size This may be evidenced in the simple setting of learning thresholds, where we note that the stream samples are drawn i.i.d, from continuous distribution satisfying standard regularity condition.
finite and the query order cannot be decided by the learner.
In particular, we find that in the infinite-support case, even if the data stream is made up of i.i.d samples, EPI-CAL can incur large sample complexity. This is because the learner experiences an arbitrarily large "hold-up", which may be evidenced even in the simple threshold example in the lemma below.
Proposition D.10. Fix some constant e >> O. Consider a PAC-learning task, where the learner seeks to learn a ID threshold with at most e-risk with respect to continuous distribution D. For any m i.id samples with m sufficienlly large and D probability density bounded away from 0 there is labeling strategy under which EPI-CAL queries 92( (D/m) labeled samples, with probability at least 1/2.
Proof. Let ht- ho for the ID threshold hypothesis class H. {ho 1(x 2 0 [0, 1]3-
Let 'D be some continuous distribution with supp(D) [0. 1]. Let XI..., Xm denote the m i.id samples from D. By assumption, suppose the pdf of lower bounded by x > 0, i.e. Pr(x) 2 K, Vo E supp(D).
Then, (r E (c, = 3 (1 c) 11())
Under m 6, consider some Bo with 30 v 1
Since the CDF is continuous, there exists such
that Pr r) < So. which is such that:
Pr(vi E [m], x4 [0. r]) 2 (1 B²) 2 exp(-2mm3)
using that - x 2 exp(-2x) when x E [0, 1/2].
Define i min((, e), which also satisfies the condition above since [0, C [0,r].
Now, we proceed to defining the labeling strategy:
1. Let M mm. Using the continuity of Pro-o( < r) r, we can find 1 rı > TM TM-1 with TM+1 such that:
Pr (x E (1441 3 anD
Pr
M
Let S; = (re for i [M].
2. We make the observation that if EPI-CAL has only seen points from S,,, Si,, then any point Fa E S2 with > max(ii,...,,, iz) will be accepted (bigger index means close to t*).
This is because with labeled points only from S,,y.., Siy, the resultant VS is superset of (0, r mmxx(h....ff)
And so, Fy is in the disagreement region, since ox (5))
3. Now, describe the sequential labeling strategy.
a) Abstain on the region: [f, ej.
b) Label if X; E (), Note that labeling (0, ensures that e-PAC learning is possible.
For X₁ E (e, 1]. sequentially label as follows:
i) Divide the samples into M stages of M samples for M vm.
32

---

Published as a conference paper at ICLR 2024
ii) At the ith stage, abstain if on the jth sample of this stage, Xaj S
iii) The first time sample Xsk for [M]] such that X E St, label it and abstain for the rest of this stage.
Using our previous point, we know that any point X E S labeled will be accepted by EPI-CAL, since i is inereasing.
Intuitively, this labeling strategy slows down learning by only labeling points that shrink the VS by little.
4. To analyze the total number of labeled points, let random variable Z; denote whether point is labeled at stage i. is Bemoulli with probability:
p Pr(3j E [M]. E (r)+ = 1 - (1- (1-B 2 -xxp(-8) = 22(1)
Using one-sided Chernoff's for Binomial random variables for M sufficiently large (i.e. for M 8 4 with p constant, have:
p
Pr
Za S Mp/2) Sxp2)) $1/4
5. And so, using union bound, we have that:
Pr(z; & [0, [m] A Σ Z; 2 Mp/2)
2 21 21-Pr [m].2; E [0, Pr
Zz < Mp/2)
2 1-414-11/
= 1/2
And so, the probability that all m samples are seen (i.e. the interaction does not terminate before all m), and that at least Mp/2 Ω2 (2(mm) samples are labeled and accepted by EPI-CAL occurs with probability at least 1/2.
Remark D.11. We remark that:
Consider when there is labeler abstention. Let Z 1(x; S minje((-1)) 2.)) Then see that the expected sample complexity is:
m Σ 1 ((logm)
E
Thus, we see that this is yel another setting, where labeler abstention can significantly increase the sample complexity.
From the Tydōs-Szekeen theorem, the O(mm) result is tight in expectation.
33

---

Published as a conference paper at ICLR 2024
E ADDITIONAL MATERIAL ON SECTION 4
In this section, we examine a few ways in which the labeler (e.g. a human worker) may be imperfect in both labeling and strategy, and extend our guarantees to such settings. We elaborate on the content covered in Section
Note that in this paper, we make inroads into understanding the minimax strategies of the learning game. Analyzing minimax strategies is the canonical way of characterizing games, studying how players (e.g. data provider company) may play rationally in the learning game. However, it has been recognized that players with bounded rationality (e.g. a human worker) may play behavioral strategies that are not manimax-optimmn (Brown & Rosenthal 1990). And so, we consider allow for the labeler labeling in a way that is sub-optimal.
E. RELAXED LEARNING GOAL
In the previous section, it is assumed that the learner is interested in exact learning some ht, One may consider the relaxed goal of PAC learning some h such that PIæ=D(h(x) * h (x)) S e w.p. greater than - 6, for some distribution 'D supported on X.
Then, following the standard realizable, PAC learning (with VC class) reduction (Vapnik 1999), one may reduce the PAC setting to the exact learning by sampling m O (CCC)) (In In L..d samples from DD
Reduction:
More precisely, let this random subset be Xm C X. Xm partitions H into clusters of equivalent hypotheses. If we let the projection of H on X be H = (h(X")) : h E H. then cluster C(v)
of equivalent hypotheses is defined Cly) h(Xm)) y y H4 x m, h E H}.
The reduction guarantees that, with probability better than 1 - 5 over the samples Xm. identification of h² cluster C(h"(X") is sufficient for P-PAC learning. X is such that w.h.p (Cann(((((") I 6, where diameter of a set H is defined as diam(H) Ma Præ-D(h(a)) # 1((x)) With this, picking any one model h E CX""(X")) satisfies ProwD (h(x) # (x)) S c, and PAC learning thus reduces to identifying cluster ((h((x")
E.1.1 APPROXIMATE IDENTIFICATION GAME
Using this reduction, we may analyze the query complexity of PAC learning exact learning game, where the learner chooses the data pool to be X (in place of A). The goal is now only approximate identifiability, and identifying the cluster h² belongs to, C("((X")))
We demonstrate how our E-VS definition can be extended to develop a near optimal algorithm under this approximate identifiable game. Our first observation is that the original E-VS, defined over H and Xm will no longer suffice:
B(V,Sx = {h E V. E V (h) '(X"" Sxx + h(X \Sx)
The issue is premature climination. Consider some h E H such that (C((((m)) 2 with h' e C(h(X")), N * h. Then, h(Xm) h'(X") 3h' E H, H'"" () = h(X" 0). which results in the elimination of the entire C()(X)) cluster at the very start. E(H, 0) will not contain any clusters with cardinality more than one.
To address this degeneracy, we define a modification of the E-VS, ESVS, with relaxed elimination condition. This is coarser E-VS, and so, observe that we should only consider non-identifiability with respect to hypotheses from other clusters:
E (V. = { E V AA E V (T ((x")) M(x ), hev) M((" (Sx) + ((X" {x)]
The added constraint of V \ (h = h E v means that two h, ht' within the same cluster do not render each other un-identifiable. And so, we only consider h's from another cluster (that differs on X²) that can render h (h's cluster) un-identifiable.
Remark E.1. Through this we see that either an entire cluster is in the X ---VVVS or it is not.
34

---

Published as a conference paper at ICLR 2024
We also define the global identification cost in the approximate identification game accordingly: Definition E.2. Given H and a set of unlabeled examples X define the global identification cost of version space V C H and instance set Sx:
GIC** (V,Sx) min(t N: :NVI VT X
Sx + -1,
XCS m Sx s.t.
E1(T(>) WE
SEAIE UX 1
Under the new definitions of X and X -III we may prove that the Xm -E-S bisection algorithm similarly attains near-optimal guarantees. One may follow the same proof structure as in Lemma Cemma.C.11] and Theorem C.16 show both results also hold under X""--VVS Thus, it suffices to prove the following two lemmas, which are analogues of I Lemmas
C.6 and
Lemma E.3, For any V C. H. and Sx C.
EX E E (V,8x)
Proof. It suffices to prove that E FX (V,5x =E (V,Sx).
To this, let h EX" (V, U {x])) Then if is such that:
Vh' E V. (XX") + hh(x"")))
\ 5x) \ fx))) * N'((X' \Sx) (5)((a) {=}) + M(""), M(X) 5x) *
= VN E
+ h E Sx)
Lemma E.4. For any X Sx and y {-1,1]. Exx (Vi(z, v)l, Sx (z}) = x (V, (V,Sx)((z,v))
Proof.
The proof is identical to the one for the fine-grain E-VS:
h E E (V[(z, 5x U {z])
- h E [){ VN E v)] + (, # M(X"
+
(x)))
h E V h(x))())))))())) y VN V[( # h(X") -( U (=))) & #M(X"
h E V A h(x) A vK' V VV""(""" # A(X") (2 (x) {(x(5x)
- h(()) = Ay EXT (V,,x))
- he E (V,Sx)((z,v))
Guarantee from learning from labeler with J that approximates At: Suppose the labeler labels with h' and (z) # h" (x)) < c/2. One may consider the approximate identifiability learning game with precision e/2. Approximately-idnnity
some h E C(h((X")) will such that
Pr(f(()) # M())) < c/2. From this, we can conclude that:
Pr(h(x) + ht (x)) = Pr(h(x)= = (z(x)) A (x)))) + h² (x)) + Pr(h(a) + AN()) < PT(N'(z) h" Pr(h(=) * l((2))
Sc
E.1.2 ACCESSING THE -"-EE-V
After modifying the E-VS definition, the remaining issue is that we wish to find the maximal bisection point for coarse, X E-VS Here, we show that for the coarsened E-VS, the membership check implemented in Algorithm 3 (with the pool being X"") is still sound. That is, we still have an oracle-efficient way of accessing the coarser X m E-, and can can implicitly track clusters through calls to the C-ERM oracle.
35

---

Published as a conference paper at ICLR 2024
Proposition E.5. h &f Ex (V,Sx) iff h( & h(x"),, where h is the minimizer of the C-ERM output below:
h arg min
Σ 1 [1((a²) h((x')}
MEH e'ESL
(12)
s.l (x)) = M(x), E x.M 15t
Proof.
-(h Ex + -(VV' E V {h: - "ex.""",,V__vvvv..... -X"" Sxx + 4(X {Sx))
+ 3h' E V -()=:(x())(<"""
V) h'( \ (x) = h(X"M \Sx
+ 3h' E EV. V.N((x") *
5x) = h 18x)
+ IhE .N(5** |8+)= = - (x=))) h(x")) .h'(""m \Sx) = h(x² Sx)
+ I/ .N((s (84)= -:s==((((()- \ # h(5+), .h'(""' \(x) A(X (5x)
< VN (S+) *MS-) ( (8)) 1(X" 15t)
+ 3h Σ
1 (1'((=') - h(2)) <18 \54) = 1(xxm (88)
FES
+ + h(xm)) h(x") \. \5a = =((x" \(S))
E.2 NOISED LABELING
It may be reasonable that in some cases, labeler can make mistakes (even when they have tried their best) due to differing opinion and/or human error. For example, for medical diagnoses, doctors may hold differing opinions for the same case. This can be naturally modeled by the noised learning setting, as in (Castro& & Nowak 2008): querying example returns he (z)) with known probability 1- 6(2), and -h"(w) (x) with noise rate (x)).
In this setup, we may use the common approach of repeatedly query a datum to estimate its label w.h.p. (e.g. as (Yan et al. 2016)). This approach reduces noised-label exact learning to cost-sensitive exact learning, where for each there is some known query cost c(z) associated with determining h h*()) with high probability. With this, we may apply the results from Subsection C.2 to see that
E-VS bisection algorithm will have near-optimal guarantees in this setting with exenple-dependen costs.
E.3 MYOPIC LABELING
Some labelers may want to enlarge the query complexity, but myopically may not have a optimal identifiable strategy. Instead, the labeler may have only a heuristic, which only h labeling and can be onniideniffiale. Kon-identifiabiliiy is something neither parties want: the learner wants to learn h² and the labeler wants to be paid, which can only happen if h- learned.
In this light, we believe that the E- game representation is not only useful for the learner, but also for a labeler to reason about the game's state. For the labeler, there an oracle-efficient way through which identifiability can be checked without enumerating the entire E-VS: simply apply the membership check on h² as in Line Algorithm 3
So even if the labeler is using some sub-optimal heuristic that may lead to non-identifiability of h², the labeler can prevent the next label from leading to non-identifiabiiity by performing a membership check with single C-ERM call. We add that only verifying that ht is in E-VS, need not require enumerating all of the E- VS, and is thus tractable provided access to a C-ERM oracle.
36

---

Published as a conference paper at ICLR 2024
F PROOFS FOR SECTION 5
F.I LEMMAS USED
Lemma F.1. For all V = x x Vi and Sx.
8(V,8x) = E(,
Proof. We show both that:
1. For V = x V. X 5X, S E(V,
It suffices to show that if hy E B(V, S'x) for i E [n]. then h = (hi,,.,, ha) E Sx) for
== x V
Firstly, since h, E Vi and V = Xie(n] Vr we have that h E E.V.
Now suppose there some h E V such that l' \ Sx) 11(2' \ 5x): we would like to show that h' = h proving this would conclude that h E E(V,
Indeed, consider any i; we have (/ = (x)())))))) equivalntll, ((())5)) = (,, \ Sx
As 14 EVV, Sxx) and R4 V1, have that K4 = h4 Therefore h and are equal in all components, and H/ h.
2. For V = X V., E(V, S E(V,
Consider any h E E(V we would like to show that for any i, h4 E EVV,
Suppose not, then there exists i, A E V; and h' + h2 such that h' \ SX = h, \ Sx). This implies that N' ((( \ [xx ).) ((x( Sx);). therefore, consider
h (h1.... h4-1, h² h441..... hn)
We have that E V, * h, and agrees with h on X' \ Sx, which contradicts the assumption that h E E(V,Sx).
Lemma F2. For any data point (11, In $ 8x and y E +1,,,11,1) -1,
(Vs)) Sx (mn)) s CVs
Proof. We prove this by induction on |Sx]-
Base Case:
The base case is when |Sx = | - 1. Here Sx {x1} = X. We have two subcases:
(VV((,))))) U (xx)) 0. In this case, the inequality satisfied.
B(V((>, (())))))))))))))))))))) )1, Sx U (a1))) 1.
We will show in general that 91),))))) U (m1)) C FxV:
i) #1, we know from Lemma C.7 that U1),, U (ai)) =
E(V, Sx) [x vn)] C Ex),
ii If =1, then
vn Sx U (ar U C B(V,Sx).
And so, Sx() 1 Cost(V, (V, Sx)
Sx (x1)).
37

---

Published as a conference paper at ICLR 2024
Induction Step:
For the inductive case, suppose the induction hypothesis holds for |Sx|= = [2] - -1,.,, J + 1. Consider some Sx with [Sx] j. j.
We have three subcases:
E(V[(21, yi)l Sx U {m1]) 0
In this case, the inequality is satisfied.
(() Sx U {m) =
As shown before,
Sx (m))) Sx)
And so, we have that [E(V 2 1 = Cost(V, 2 0 = Cost(V[(21,, bi),, Sx U {z1)).
[EV [[V[(11, B1),, Sx U {a1))) 2 2.
Using similar logic as before, Define
22 22.
a' E arg min max (y #1) Cost (V (z1)) =EX1sx 7
With this definition,
Cost(V, max (1 #1) + Cost(V((z'.v)) (x'}) y
If x' Cost(V v1),, Sx U {x1)).
then the result follows since Cost(V,Sx) 2 1yy #1) +
If o' + xı, then r' E X \ S U {z1}. J. and we can write:
Cost(V v1),, Sx U (m1)) max 1 #1) Cost(V (1), (4', 5),, U (0),-())
y
(as [E(V[(2I, Sx U (z }) 2 2 so we can unroll, and x' E X (U
< max 1 (y イL) + Cost(V w)1, Sx U {2'})
(using induction hypothesis since |Sx { (2') =1)
-Cos((VSS)
Lemma E.3. For *L E X SSx
Cost (ost(V((s, Sx) = Sx U (x))
Proof. Firstly, we have that:
((V(<,.))) {h e v[(x, y) Vh e V((x,)) (k), ( + h(x) \ \5x)
{(h E Vi(z, v)l wh' E V((z,)) y) \ (h), \ (Sx U (=)) h(x' \ Sx (x}))
E(V[(Z, Sx (x))
Hence the statement holds when Sx X' {.r, or Cost(V [[z, v)], Sx) is at its base case (one implies the other due to having the same E-VS).
generally, when Cost(V[(>, v) Sx U (x))
Now, we will induct on the size of Sx since the base case of Sx X {x) is satisfied.
Base case: |Sx| = | - 1. If FVVV SV U (x)) 0. then LHS RHS -00;
38

---

Published as a conference paper at ICLR 2024
If Sx)) Sx (=}) = 1, then LHS = RHS = 0.
Induction Step: Suppose the statement holds for when |Sx = 12 1. Let [Sxl = j.
We first handle the base cases:
EVV, 5x) = EV, Sx U (x}) 0, then LHS RHS -O6;
If Sx)) [E(V, Sx U (+})) = 1, then LHS = RHS = O.
Finally, it remains to consider when |F.V 5x) |R(V, U (x})) 2 2. In this case,
Cost(V,Sx) = min Z'EX 1,1
max
(1 * + Cost s/), Sx u (x'}).
Define x' E arg mex max ( #1) Cost Sx (x)))
We will show that x² + x.
In fact, for any x' E S, x' + x² (which exists because {Ø} C X' \\ (x) we have:
max 1 * Cost(V"(a U (x+)
max(1 + Cost(V2, Sx U U= Sx {x}), Cost Sx U (x]))
= 1+ "ost U {x}))
(maximized at when y' = y)
mAx 1'E(t1,-1,1
1 #1) +
U uz x.,2
(using 2 11 x and Lemma F.2
1 *1) + Cost(VV[(2 V)1, Sx v'E(+),-1,1)
max
(using induction hypothesis since |Sx Ufz' -=
And
min Ve 1 f1) Cost(V Sx U (a'})
max 1 *1) + Cost vy [[,, w)ll, Sx U { {z'})
min
(since we have just shown that x² # x)
min vel (using induction hypothesis since |Sx U (z = 11)
max 1 #1) + Cost VY ((x, v)1l, (Sx U {ar (z')) u (x))
min
max 1 *1) + Cost(V v/ II. (Sx ( (rearranging)
(os) Sx (z))
F.2
UPPER BOUND
F.2.1 NEGATIVE RESULTS
Upper Bound when there is Identifiability:
We first observe that without assumptions on the structure of V, there exists setting, in which the upper bound does not hold.
Proposition F.4. There exists non-Cartesian product version space V C H and query response S C (X' x y)* such that Cost(V,, St) 2 for all i, but:
CV, 2
Σ
Cost (V,, 5x +
i=1
39

---

Published as a conference paper at ICLR 2024
Proof. We will construct V and S such that Cost(V,SS) 2 1, but C 0.
Hypothesis Class: Define thresholds functions fi = 1xx 2 1/4), f2 = 1(x 2 1/2), = 1xx 3/4) for [0, Define as:
f1, f2) ..., (f2, f2. :.... f1) where the jth model has its jth task model as fi instead of fz.
Define the non-Cartesian product hypothesis class as:
H'' (ff,,2,.... f2), (fz, f3, fs)....s)).
We have that H. = [/i Sa).
Data: Let 21 (ma))== and X2 = [ where au 1/3e; and T22 = 2/3e,. Let X'
X1 U.2.2
Query Responses: Suppose S = {11:2) [_.... 1)) i [n]]]
This means that Sx {a12 : i [n]], and that Sx {2/3]. since the only E X such that
I; 2/3 is T22 and T22 E Sx.
Define V M[S] H. And so, Vi f2.
We have that S = {fi, and so, Cost(V, Sx = O.
Now, it remains to show that (VV Sx) H'.
Firstly, since V = -H H. we examine each model in H.
The model (/2, J2; ...y f2) and (a,.,,. f3)'s predictions vn (for any i) both (-1.-1.... -1). Thus, they have the same predictions on {oahe()) = X' Sx, and so, (2,, f2), (fa, fa,..., fa) Ex).
With this, we see that EVV,5x) = H'' because for the ith element of H', disagrees with every other element 211-
Finally, we will show that Cost(V. (V,x)) 2 n 1
Consider labeling strategy that returns label (-1,..., -1. for any æa queried.
This strategy identifies some h E H. since each point in X; that is queried removes one model from E-VS. And so, after 1 queries on points in Xi, the E-VS has one hypothesis and the learning interaction finishes since the identification condition met.
We note that any querying algorithm will require removes only one model from the E-VS, thus n - labels are required for identification under any querying algorithm. And so, have that Cost V. Sx) 2 1.
labeled queries. Each binary labeled example
Upper Bound when there is no Identifiability:
Proposition F.5. For non- con-Cartesian product hypothesis class V, there exists V,S such that Cost(V,, 5xx = foo some i, but Cost(V, 1.
Proof. Consider H = {hi, h2): (ha, ha)).
X [[1 0j, [0, [22]2 where for 21, o O. h1(21) # ha(01) and h2(22) # h((22). h2( (0) and (0) = (O).
Consider query response 5 ([vi, [1, 11)}. Sx = [[r, Sk = {x1), S (0).
V = =[$$ = H. V1 = (hi, and 1/2 1/2,
E(V1, (m1)) E((h,, hs). (21)) 6. However, E(V, [1), H. since (h1 h2) and (hg, h4) differ on [0)
40

---

Published as a conference paper at ICLR 2024
And so, 1 = Cost(V,Sx) Ei=1 (V, cc, since Cost(Vi,, 8kx
-00
Remark F.6. In conclusion, show the upper bound, need impose Cartesian product condition.
Negative Example motivating the need to assume particular label cost definition:
When the label cost Cone: there are settings where CV can much larger i.e. Cost(V, >> Di=1 Cost(V,, S').
Proposition F.7. Assuming the version space is Cartesian product, under label cost Come (y) 13i, y1 }L), there exists V and S such that Cost(V; Sxx 1, but Cost(V, Sx) = |2 This implies that: Cost(V Ei=1 S'x)
Proof. Consider = (11,, h22) x (Th,, h4), where 11, h2 V1 are thresholds functions h1 = (x 2
0),h2 1(x 1) and ha, h4 E V2 are also thresholds h3 = 1 (xr 0) 1(x 1).
X'
m m+1
which means that X1 = X2 = { m m++
m+I
We will show that:
Cost(V, 0) > Cost(Vi, 0) + Cost (V2, 0)
We first have that Cost(V,, 0), Cost (V2, 0) 1, since only one labeled sample is needed to distin- guish between h1, h2 and between hag h4-
However, we have Cost (V, 0) 2
X with the following labeling strategy T:
1) As long as [ < m 1, for queried point . m4TI. return (L, hol m++ )).
2) Only when |Sx| m for queried point [ f. return (h1 (m 1 has (m m)
We can first that this an identifiable labeling strategy that identifies hk),
And, for any querying algorithm, h* is only identified when Sx = X.
Thus, | labeled samples need to be queried, making Cost(V, 0) = |.8
Remark F.8. To prove the above bound, need to assume the label cost to be: 1ly fL)
1 Me #1) = (y)
F.2.2 POSITIVE RESULTS
Change in Definition of the Game:
To prove the upper bound, we have a changed definition in labeling payoff, which is now:
1 ( +L) 1 y: f1)
The earlier negative example motivates requiring the assumption that V is a Cartesian product.
Theorem F.9. For all V Xie(n) V, and Sx S X, under labeling cost cau 1 1(vi, ys #1):
Cost(V,S S Σ Cost(Vi,
Proof. We prove this by induction on the size of Sx.
Base Case: When Sx = X' + 5x = X4 So for all i, JEV,, Sx $ 1.
It suffices to check that Cost (V,Sx) = 0 + Vi, Cost V;, Sxx) = 0.
Indeed, if Cost(V,S 0, then [E(V, X') 1. Denote by h the only element of F(V,
41

---

Published as a conference paper at ICLR 2024
We must have V {h), which in turn implies that for all i V, {h.}. Therefore, for all i [E(V, = {h+} = 1, which implies vi, Cost Vs, 5%) = O.
Induction Step:
Suppose the following holds for Sx C X for |Sxl = 18,,..,, + 1. Now let [5xl = j (note that
Sx C X).
We will analyze the three cases:
3i Cost(VV, 8
vi, Cost V4, 2 0 and vi, (,,
vi, Cost( V4, ) 2 and Bi, Cost Vi, Sx) 1.
1. If there is least one such that Cost(V,, -0.
It suffices verify that Bi, E(V, six) = E(V,Sx) = 0.
This follows immediately from that F(V, 8x) = x S') (Lemma R.1
2. For all i, Cost Sx) is at its base case and Cost V1, Vx, = O.
That is, we have Vi, E(V, s
From Lemma
F11 have that F(V, x"= F(V,, Six), which means that LVVV, Sx)1 1. And so, Cost(V,Sx) = 0 Σn Cost (Vi, 8x))
3. Exists such that Cost((V1,55) 2 1, and Cost (V,, 2 0 for all
Without loss of generality, = 1.
Note that if EV, Sx)] $ 1, then Cost(V, (V,Sx) 50 Σn (V St)..
And throughout the rest of the proof, focus the case that (V, [x)] 2 2. Also, recall that since Cost (Vi, Skk 2 implies that 5(V,,5k) 2.
Define
of arg min max (1 #1) Cost (V] v)1, Sx U {xj}) sEti is yEy
We may express:
Cost (V,
max 1 (y f1) wEy
Sk (xi))
And since o E 2' \. 1x,, the set Xi fa' E x Sx of = = is non-empty.
Denote Lx = {x: (I, E L}. Consider the following procedure:
repeat -=0
Query some Xi Labeler returns y::
y = arg max 1Vv #1)+ + Cost(V[LU ((,,)))), Ulx U (x))
- [x) I L. until 11 +1 Xi
Denote by di the value of yn the end of the procedure, let [Z] and, in order, interaction history L is such that L = "e,,,y",... (æ y²)} Let L { v:) (x, I, yi }1} index the binary labeled data for the ith task.
42

---

Published as a conference paper at ICLR 2024
Cost(V,Sx) s 11('' *1) + (os" Sx u (xl))
(since xt E E C X' Sx))
('a U {al))
(since y =1)
S
(unrolling according to L, which possible as Cost (V,Sx) 2 1 = (V Sx U Lx) 1)
< 1y" *1) Cost Cost (V U Lx)
< 1 * + (ost(V Sx Lx) (1 y.th *1) - (g) #1) since yf" 51)
= 18i f1) + Cost Vi Sx U Lx) (V a Cartesian product)
S 1 #1) + Cost(V (8x U
(using induction hypothesis as |Lx| 2 1)
= 11 #1) + Cost Cost (Vl((2],)))) u {aiH) + Σ Cost (Vi[") (Sx U Lx)")
(o)
n
S Cost +
Σ
Cost (V.[L'), (Sx U Lx)')
(by definition of zz)
Cost(Vi, +
(V,
(0o)
1=2
(o): For the fourth step, there are two cases:
If upon exit, Xi 0:
Then using the definition of S since Zo E X X with æ =i we have
that (5x J Lx)² = S% U (zī). Therefore, Cost(Vi[L')) (8x ULx)') Cost (()ll 5 U (zi)).
Otherwise, upon exit, Xf * 0. Then, we must have that á fL: So äx E X \ (8x U Lx) with x, x/. Therefore, (Sx U Lx)² = Sk. hence Cost(V][L2), (Sx U Lx)²)
(Vs Sk)).
From Lemma E3 we have that Cost (2t. Cost(V][(2t, S3 (21H).
(oo):
For the last step, consider each task for i E (2....,n).
Define:
T = fs': :3: E :.,;==1,, #1 Nr' E (Sx )
L {a': :dx,(z,)) 1) E L, 1, =1 Ao' E (Sx [x
L {1/: 3(x,)) v) E L, #1 Ar' & (Sx )
bx = {a': :/< 4) E -, =1 ^r' & (Sx U Lx)*}
With these definitions, we have (SXULx) S U The binary labeled examples comprise of Lix I U T.
43

---

Published as a conference paper at ICLR 2024
We have that:
Cost Cost(Vilz'), U Lx)' = Cost(ViLL', U U
Cost(V U U U U
(usngg Lemma F33 on L
= Cost(Vi(L' U u (z. 1) : e
2 1
U
S Cost(Vi, Sx) (iteratively applying Lemma F2 on L U U
F.3
LOWER BOUND
Label Cost Function: From this point onwards, assume that the label cost is (the more generous)
Cone-
F.3.1
NEGATIVE RESULTS
Lower Bound when there is Identifiability:
The following example leverages the fact that structure in the multi-task hypothesis class constrains the target hypotheses across all n tasks. And so, abstentions can lead to the multi-task setting requiring fewer samples than even the single-task setting with the highest sample complexity. Proposition F.10. There exists non- Ca--eatessian product version space V and query response S such that Cost V3, 5Xx) 2 O for all i, but:
Cost(V,SX) < max Cost
(E(m)
Proof. Hypothesis Class: Define all zero-classifier, ha(x) = 0 for all Let h; 1(x (i, for E [n] be the ith interval.
Let g1 92-93 be three distinct threshold functions, 91 [x 2 1/4), 1(x 2 1/2), 1(x 2 3/4) for x E [0, 1].
Set H to be
(ho, g1). (ho, (1ii, 93) 93))
Data: Define X' = { [T Oj....., [I 0], [0, 2211; [0, r22l] where 2ι = i 1/2 for i [n] and
121 = 1/3, F22 2/3. By construction, 91 (I21) # G2 (x21) and g2(222) * 93(222).
Define S {(10, (2)) [L, 1))} Sx {10, (2)) S 0, = (.21).
We have V H[S] H. V1 = Hi (ho, h1, h2 ha. ..., hn and V/2 Hz {g,, 92. 93).
gi ((X')) \ 5x)2) = ( \ (Sx)2)= + (ho.gi), (ho, (h))g))= & EVV,5x).
We have E(V, = {(h, 93) ) because for any * j. (h4, gs) and (hj: gs) differ on [mıg 0).
From this, we get that Cost(V, Sx) one model from the E-VS. Since the E-VS is of size n, n binary labeled examples are needed to reduce the E-VS size to at most 1.
1. Querying any point [x16, 0] at any time removes only
On the other hand, we have that for (Vs with Vi = n + 1 and S 66 Cost 5%) = n Cost(V,SX)
Lower Bound when there is no Identifiability even with Cartesian product assumption: Proposition F.11. There exists Cartesian product version space V and query response S with (V, such that:
Cost(V,Sx
< max Cost (x) (E
44

---

Published as a conference paper at ICLR 2024
Proof. Let 7/ h12) {h2 h2z), where h1 1(x 2 01, 1(x 1) are intervals,
and h21 = [(x 2 0), h22 = 1( 2 1) are intervals.
X { { , [0. m2]} where 21 1/2, 22 = 1/2.
Labeling is: S { ([11 [1, 1)) 5x = [111, 0]}. Sx = (01) S3 = {0}.
So V -[S]- H. {/11, 122 and {1211 122).
Under S, we observe that 5xV,5x] 0, since (h1,, h)) and (112, for h E V/2 = h22), predict the same on {10,02]} = X 5x. Hence, CV, Sx) = -CC.
However, CV, S = Cost (( (h21, hu2) {(}) = > Cost(V. V.Sx).
Remark F.12. To prove the lower bound, need to impose both identifiability Cost(V,Sx) 2 0 *and* Cartesian product condition.
F.3.2 POSITIVE RESULTS
Theorem F.13. For all = Xieln) Vi and Sx S X. if (Vst((V,S)) 2 0. then:
Cost(V, 2 max Cost(V;, 4E ml
Proof. We prove this by induction on the size of Sx-
Base Case: When Sx X' = S X, so for all i, Cost (V, S 0 0 CVs Sx). Induction Step: Suppose the following holds for |Sxl = .l...... + 1.
Now let [Sx] = j. Note that this implies Sx X.
First, consider the case when Cost (V = 0. We have that (E(V,Sx = 1. And so, using Lemma F.1 for all i, [V,, SX = Thus, Cost(V, S 0 for all i.
Now, we consider the case when Cost(V,,5, Sx) 2 1.
Let & arg max4e[n] Cost(V,, Sx) It suffices to verify the statement when Cost (k, Cost(VE,, 2 1.
Since X Sx non-empty due to Sx X, define:
x min
arg min max 1(y' AL) Cost(Vy', ,S zEX VEEY
Sx U (x})
We have that Xr S (x) (a' E X 3r E Sx, = 2'}. and so x E 23 1
since min E X' Sx.
Since Cost(Vi. sk) 2 1, we know there exists 0n such that:
Cost(VV,, st) < (8j 7 L + (ost((V(((]))) (.), U faminn) }).
Note in particular that [ Tx,),, Sk U Uf main 1] + 0. as otherwise Cos which would contradict assumption that Cost (V.. Sk 2
Sk) -00
45

---

Published as a conference paper at ICLR 2024
Cost(V,Sx) max (ty f1) + Cost (Vy E'E) + Cost [e(n] ginin Sx U { (ammin)
omen Sx u {aminn)
(y
(setting y' y constructed in Lemma 14 and using that Vy zmin Xve(n) (m)))
and
( - max Cost Cost mrmon (Sx U { (2.tiin))
iE/n]
(using induction hypothesis since min $ Sx. so [Sx (zmin) =
(Sx min 1)b)
2 (ūx *1) + Cost(((k)
(1 # 2 (yy *1)= lÿx *L) as yk Ts by construction)
2 (ūx 1 + Cost (V+) 5 { a }}
(note that xx zani E (X Sx)x, k. so xhti E No \ S and o)
2 V St)
(o): Either we have (Sx U {amin)) ) yields equality and the statement holds.
S U (axiin) or (Sx {m = -S The former case
For the latter case, can Lemma
F.2 (for yk =1) Lemma
F33 (for ÿN. f.) get that: gminn S Cost
Cost((Vk) ) We (Sx U { (mmin))
Cost o
Sik U {xxmin))
Lemma F.14. Suppose C(V,Sx) 2 O and min arg z maxyey [1 *1) Cost (V2, Sx {x])) ther OR such that Cost(Vi: Sk S 1 (ūn *1) + Cost (Vel(=Tiin ). S
{armin for Cost(V&, S 2 0, then there exists y such that its kth coordinate yk = ÿk such that:
Cost (ostVV((mmmm .y)l. Sx U { min } 20
Proof. We explicitly construct some y such that yı Uh and the above holds:
Firstly, Cost(V, 2 0, which implies there exists E(V,
à E V implics that Vi, h4 E V4.
Also, Cost(Vi((x (uk], S U {xpzin] }) > Cost(VR, 8x) 0. This implies that there exists some 1ig EVVV((= Tkk) S U {xffine) }).
We claim that y = (h1 (=/"i) (xxtin) ten (Immia)) satisfies the condition.
To show this, define = (h1,,.. h,,),))) Firstly, since h; E V₁ (for & k E [n]) and he E Vs, we have that h E Vi = V. Also, maii = y. Therefore, h V Vinin.
We will show that h E E(V Sx U (ammm))) which proves the result.
From Lemma
C.6 We have that:
Tie E [(V&[(( min Je),, Sk U x
min
B(Ve[[aTii J.)). (Sx U { mmmi }o0)
since 8 U (aginn) (Sx U (zmmn)) )).
For all i f k. we have:
h E B(V, + >b; E(V,, Si) + h4s E E(Vi[(a!"'n ,v)),, U f.mmin))
46

---

Published as a conference paper at ICLR 2024
since for all It' E V2 } with h' (a yi (a h must be such that ('(
(SX U {a:min) })) * (: (SX U {arpinn })). Since this holds for all h E Vil(<t vs))
{hr), have h E E(Vi[( 1:),, S U (atmin))
From Lemma C.6 We have that:
h4 E E(Vi[((?" w:l, S'x U a armiinn
}) S E(Vi(( "u), (Sx U (mmmn) (
since Sx U { {atrin) 2 (Sx U {zmin]]
Hence,
h (( 9:)1, (Sx u { famin }0') = h E(V ",),,,,),,..... .0),, Sx u {amin))
since from Lemma F.1 we have that:
F(V[(x v)), U min })) x F(V( .b:)), (Sx U (smmin)))
Remark F11. As Cost( (xee(()) p gjain Sx mi }} 0, the precondition for induction hypoth- esis holds.
F.4 MULTI-TASK ACTIVE LEARNING WITHOUT ABSTENTION
We also investigate the related multi-task, minimax active learning setting without abstention, which may be of independent interest. To knowledge, this is also open problem. Our goal is again to relate the multi-task complexity to the single-task complexity. Since abstention is the cause several of the negative examples above, one can prove more general upper bounds when labels have to be given.
F.4.1
GAME SETUP
Without abstention, the state may now be tracked simply with VS (instead of E-VS). The analogous game value may be defined as follows:
-00
V = 0
Cost(V,
0,
V 1
mis max,)(-1,+1) (1+ CVs (z]))
[V|2 2
F.4.2
LEMMAS USED
Lemma F.16. For any Sx, 2 Cost(V,Sx) 2 0.
Proof. Base Case: We prove this by induction on |Sx]. If Sx = X, then | 2 1 |V =1 (V, Sx) 0.
Induction Step: Suppose this is true for |Sxl = |X'),..,, j + 1. Now |5xl = = Le
If [ = 1, then the result holds.
Otherwise, V 2 2. We will show that VV 2 2 + Cost(V, 2:
Cost (V, Sx)
min
Cost VV, Sx U (x))
zEA'Sx sE(+1,-13
> 1 + Cost(V[(<') h(x")) Sx U {))
(for x= = arg min max 1 + Cost Sx (x)))
21 1
The last step that Cost(V((x*, //xx)]] )1 Sx U (x })) follows from induction hypothesis, whose precondition satisfied because E V + h E ((*,,((*))
(+) V 0 Cost(V,Sx)
0, hence Cost (V,
V 1.
47

---

Published as a conference paper at ICLR 2024
Corollary F.17. We have that:
[ 2. Cost(V, S 0 V =1
1. Cost(V,S,
Proof.
1. (+): Follows from that Cost Sx) <0= V + V 0.
(+)) Follows from the base case definition of Cost.
2. (+) From the above, we have that |V] 2 2 Cost SX) 2 1. And Cost V, (x) s
> |V S
The result follows since Cost 5x) = 0 -x |V] # V =1
(+): Follows from the base case definition of Cost.
Lemma F.18. For V C V and any Sx S X::
Cost(V,Sx) 2 (
Proof. We will prove this statement by induction on the size of Sx.
Base Case: 5x X. This means Cost Sx) Cost(V', (S')))) are at the base-case. [V| IV| = 1, and the statement holds. If [V*| = O, the statement holds since RHS is equal to -00.
Induction Step: Suppose the statement holds |Sxl | J. + and any V C V. Consider some Sx such that [Sx] = j.
(a) First, we examine what happens if [V| 1.
(i [V] 0 > | = 0, then Cost(V/ Sx) -00 Cost(V', SSx)
Cost(V', .x). (ii) if V 11 V 1, so Cost (V, .x)
(b) If V > 2 and
V' < 1, then since [V] 2 1, we have Cost ( V, Sx) 2 0 Cost(V",S3, using
Lemma F.
(c) The remaining case is when [V] 2 2 and V 2 2.
We have that:
Cost(V,SS)) min =x sE(+1,-1)
1 + Cost Sx (x))
(since |V] 2, we unroll)
min Sx ,E(+1,-1) (for all n, v. V CV V'[(,, v)] S V( v)), may apply induction hypothesis)
max
+ Cost((V') Sx (x})
-Cost(V',Sy
Lemma F.19. For any data point (I1, for Sx and E (+1, -1}: Cost (ost(V(((1, Sx U {x1)) < Cost(V,Sx Sx)
Proof. Base Case:
We first handle the case when [V[ 91)ll <
If [V[ 91)ll = 0, then the result holds.
If [<[ yı )ll = |V| 2 and the result holds from Lemma F.16
This covers the base case when Sx = X.
Induction Step: Suppose the statement holds for when |Sx| |X] ..... j 1. Let [Sx
48

---

Published as a conference paper at ICLR 2024
It suffices to examine the case that [v[ f1)]l 2 2, which implies that [V] 2 Define
x' E arg min max + (ost(V((2'.))))55 {2'}); =EAtSSx y
with this definition,
Cost(V, max + Cost(V[(a' 5x U {x'})
If x' -1, then the result follows.
x # 01. then x' E \ {a1], and we can write:
Cost(V[(<1. (x1)) & max Cost(V v1), (z' .)). Sx U {x1,-²})
(as [V[ vn)1 2 2 so we can unroll with x' E X' \ Sx U (z)))
s max + Cost(V (V)) Sx U {2'})
(using induction hypothesis)
Cost(V, Sx)
Lemma F20. For x E X Sx some
some E {+1,-11 -1}:
Cost(V Sx) Cost Cost(V[(z, U (z))
Proof. We show this by induction on size of Sx.
Base Case: Firstly, the version space are the same, V(( v)].
So LHS equal RHS when [V[(,, s)]l S in the base case. This covers the case when Sx X.
Induction Step: Suppose the statement holds for when |Sx = | j + 1. Let SSl j.
suffices to consider when [V 8)]l 2 We may write:
Cost(V,Sx)
min max 1 (1 U (2'}) S' ve(+1,-1
Define x² E arg min max/e/+11-1 1 + Cost(V We will show that x² # x.
Sx (x'}).
In fact, for any x' E X Sxx x' # x² (which exists because {Ø) C X (x) we have:
max 1 + Cost (V2 -E((+1,11 1]
max(1 + CVs Sx ( Sx (z)))
- Cost(Vy # Sx U {x])
(maximized at when y' = y
2 max
+ Cost V2 V2 y y')l) Sx U (2,2'))
(using Lemma E.19
1 + Cost Cost (x' y I]. Sx (z')))
max
(using induction hypothesis since |Sx U f2') =
49

---

Published as a conference paper at ICLR 2024
And so,
min
max 1+ Cost(V y'),,, u (2'{))
3'EA' 5'ext5x''((tt
min max + Cost [<., Sx u (x'))
(since x² x))
min
max 1+ Cost(V o' [ax, y)ll. (Sx (2' {2()))
(5x(()x r'
(using induction hypothesis since |Sx -
min
max 1 + Cost(VV[(<'' ./)l U
(rearranging)
= Cost(V((c, U (x))
F.4.3 UPPER BOUND
Theorem F.21. For all C and Sx C.:
Cost(V,8x) Σ CV, Sx)
Proof. We will proceed by induction on the size of Sx: Base Case: When Sx X. this case, S Xr. So all Cost's are the base-case.
It suffices to check that if Cost Sx) 0 = Vi, Cost (V, = 0.
This follows because Cost(V, V Sx) Cost(V, 0 Σ Cost V, S
+ V = 1. By definition of Vi, [V] = 1. And so,
Induction Step:
Suppose the following holds for Sx C X for [Sxl (&h..... + 1. Now let |8xl ( (with
Sx C X).
We consider three cases:
3i, Vi
Vi, [V] 2 1 and Vi, [V,|
Vi, [V| 2 1 and Ri, [.| 2 2
1. If there is such that Cost(V,, Sx) 00.
Then Vi = + V = 0, and therefore, Cost CV, Sx) = -00
2. For all i, CostCV, S. (%) = 0.
This means that for all i, VV]
1. And we wish to show that [V] S 1, which would imply that CV,t(V,Sx)) < 0 Σ Cos Sx).
Suppose not, there exists h, V. Then, h h W' + Ei such that h, # M4 = hi 14 Vi + MM| 2 2, which is contradiction.
3. Exists such that Cost(V,, Sxx 2 1, and Cost V,, Sxx > 0 for jll
Assume WLOG = 1. Note that if VI < 1, then Cost (V, 5x) 5 0 < Σn_ Cost Sx).
And so, will consider the case when [V] 2 2 and [i 2.
50

---

Published as a conference paper at ICLR 2024
Define
21 E arg min max 1 1+ Cost v)I. S U (zf))
=E ve(+I,-1)
we may express:
Sx)
max 1E(+1,-1>
1 (V U (z1})
(13)
Moreover, we have that 3e E X Sx with the first coordinate equal to zj. And so,
Cost(V,Sx) & max yE(+1,-1)"
1+ Cost(VV(("" v)), 1+Coss(V[(ar) v SxU(x=))
With this,
Cost(V,8x) 8x) - + Cost(Vi(a", ([((l=""/)),s0 /)), U {x*})
$ 1+
Cost((V[(2* // (Sx U (z*)))
(using induction hypothesis)
1 (Vx
Cost (M
< 1 + Cost Cost
(2i)) +
Cost ,')),"))))),)))))))))) (Sx U (z*})*
(using Lemma F188 and o for task 1)
S Sx, +
Cost((V[(<* V)), (Sx u (x*))²)
(using Equation
13
I Cost(V1, + Σ
Cost(Vi[(a), 14), S U {x?))
(using Lemma F.18 and for tasks 2 to m)
I Cost(V1, + Σ Cost (V,, St))
(using Lemma F.19 for tasks to n))
For any task i:
Lemma F.22. For any x. y and V,
(((x,,))); S Vi((,,, v:)
Proof. We have that hy E (V[(z, v))) - 3h E V((z, u)l, h: = h4- E Vi[( w.l, since h E V[ 8) h VA (x,)) ys (from h(x) y).
And so, we get that h² = 14 E Vı[(
Using this lemma, we may apply Lemma F.88 to get that: (ost((V((>") 2/D.. (Sx U {x*))) < Cost(V (Sx u (x*))²
We will show below that:
Cost(Vi 201, (Sx U ((*)))) = [c)) U (xt1)
(0): There tWO to consider:
51

---

Published as a conference paper at ICLR 2024
Case 1: (8x {2 ) Sx U {xt J: in this case, Cost(Vi w/)1, (Sx U ()))
Cost(Vil(az, 2/), S {=t}) holds;
Case 2: (Sx U {x*})² Sx. in this case, ( u (x*}))
Cost(Vi] v01, 5xx) Cost(Vil(a5; (/), Sx U {2; }), where the last equality
Lemma F20
F.4.4 LOWER BOUND
Example of non-Cartesian Product V can reverse inequality:
Proposition F.23. There exists a non-Cartesian product version space V and Sx such that:
Cost(V,Sx) < max (V, iE!n)
Proof. Consider H { {(i1, 91), (12, {2) h, and gj 's are thresholds.
Let X' = (1011, (22,,, [212, 02]}. where 211 separates h1, h2, x12 separates h2, hy and 22 separates
01.92-
Let = 0, so 5x = S = S3 = 0.
V = H ((11,9)). (122, 91), (h3, (h3,g2)} V1 = {h1, h2, ha). 12= {21.92}. Then, we have that Cost (V1 0) for (h1 h2, h2}. However, Cost 0) 1, since one needs to query [211, x22 only.
Remark E24. The observation is that Iı1 helps to distinguish between hı and he E V1, while T2 helps with distinguishing between gn and g2 E V2, which turn helps to distinguish between (h1, h2) and (ha) C V1.
Theorem F.25. For all = XiE(m) Vi and Sx S X such that Cost(V, 2 0:
Cost(V, 2 max Cost(V;,S')
Proof. We prove this by induction on the size of Sx.
Base Case: Sx
S X.
If Cost(V, X) 0, then V = 1 = V = 1, = Cost(V,, Sxx for all i.
Induction Step: Suppose the following holds for |Sxl = [1 ..... + 1. Now [Sx = j. note that
Sx C X.
We first handle the base cases.
If (V, (x) 0, then V [h} = Vi, V {h.} (due to the Cartesian product structure of V/)
= Cost (V, Sx) = O.
Now, if Cost 2 1 and if l: arg max Cost (V, Sx); then suffices to verify the statement when Cost(Vi, Skx 2 1.
Define:
min
arg min max 1gy #1) + Cost(Vy' Sx fz+) xxxiss W'E)
From definition, X Sk (X' Sx)x fx' E X 3r E E Sx, x'}. And so r E
X \ Sk since min X' Sx. Since Cost (V., st 2 know there exists Or such that:
Cost Cost(Ve, (V, < + Cost V2 (= Fx)), S
min
}
52

---

Published as a conference paper at ICLR 2024
Note in particular that V& Vel(a 5x)) * 0 as otherwise Cost -oo (which contradicts assumption):
Cost(V,Sx)=
min max 1 + Cost(V Sx U {2+)) (X)) Sx is non-empty, since Sx X) =E v'Ey
max 1 + Cost(Vy gman Sx U u (ominn) y'E)'
++ Cost(Xie(n)) (Vi) migui Sx u [mmmn)
(setting y' = as constructed below (f) and using that V XiE(n) (Vi) m
2 + max Co)) a:men: (Sx U { 2 min })")
iE|nl
(using induction hypothesis since wmnn & Sxx so |Sx {2min) = 1)
(oss((VV)) prmee (8x U min 3
(by construction, y/k 7Tx)
Cost (osst((Vv)) ( agrin S U "
Jmmin })
(note that oxk
E (X' Sx)R, so xt zptin Mr. \ S and o)
2 Cost(VVs SV
(t) : Claim: There exists some such that = Uh and /V gma # 0 (that is, (Vi) o for each v).
Firstly, CV (V,Sx, .x) 2 V 1. This means that there exists V, and that Vi, 3h, V,.
Since Vi[("r 0k.] + 0, there exists some hy V&((aTiinn 7x)) + 0.
We claim that = (hr (a? ( Nn (amin)) satisfies the property.
Let = (li,,.., hy, hw). Then we have h E v zmin since:
i) h, E Vi, ha E Ve implies h Vie[n]Vi =
ii) h(mmin) y-
And so, |V 2 1 = Cos mm Sx U { }) 2 0, which means we meet the precondition
needed to use the induction hypothesis.
(o): For task k, We know that (8x (o ) is either S S U (zpin), J. In the latter case, cquality holds.
In the former case, we may use Lemma F.20 to get that equality also holds:
Cost((Va (V M..... (Sx U {xmin))s) Co)) ag
Sxx Cost smains
(V S U (zxtnn)
53

---

Published as a conference paper at ICLR 2024
G MISCELLANEOUS
G. DATA-BASED GAME REPRESENTATION
We begin with defining natural state representation of the minimax learning game in Protocol 4 using the examples queried by the learner so far. motivated by the definition of identifiability for determining the termination condition.
Definition G.1. Given the set of labeled examples and their labels S, and the queried examples Sx, classifier h H. is said to be identifiable with respect to (S,Sx) (1) h is consistent with S; for all N E H consistent with S,
1' (Xxxxx)))))))) =
= h
The above definition naturally motivates the following definition of effective version space: Definition G.2. Given the set of labeled examples and their labels S, and the queried examples Sx. define its induced effective version space as
F(S,Sx) (h E H h is identifiable with respect to (x))
With this, natural recursively define the game and its optimal value function using this state representation:
-00;
F(8,Sx) = 0 IP(S, =1
f(S,5x)
e max
1+ ((, (x))
[F(S, 2 2,
1 ((s, U (x)))
Here, we use the base-case game payoffs to encode the labeler's promise of identifiability. Non- identifiability (F(S,xx) = 0) leads a terminal payoff of oo. Identifiability constrains the labeler to not provide arbitrary labels and "string along" the learner for as long as possible. As we will later see, this constraint is not crucial, as the algorithm we develop is also robust to a labeler that does not guarantee identifiability.
G.1.1 VERSION SPACE-BASER GAME REPRESENTATION
We now turn to the version space game representation, which we use throughout, and prove it is correct.
Definition G.3. Given a labeled dataset S and set of classifiers V, define version space V(S] [h V V(z, y) E S A h(x) = v the subset of classifiers in V consistent with S. Definition G.4. Given the set of labeled examples and their labels S, and the queried examples Sx. classifier h H is said be identifiable with respect Sx,)x) if:
h is consistent with S, h E H[S]..
for all other consistent h < H[S): 1(X'' =x)= Sx) = h¹' h, where for brevity we denote h1(Sx) h2(Sx) = Yx E Sx h)(()) h2(2).
Definition G.5. Given set of classifiers V and set of queried examples Sx, define
F(V,Sx) {h E AN E (h): N'(X) 5x) # h(x {x)) as the effective version space (E- (E-VS) with respect to V and Sx.
The following proposition relates the effective version space to the classical notion version space: Proposition G.6.
F(S, Sx) = SxH(
54

---

Published as a conference paper at ICLR 2024
Proof.
h E F(),xx) + h H|S] A Ah' E (' { = ルー=h =
+ h H|S] A Vh' E H|S), n #h = n'( Sx) # h(2)
(taking the contrapositive)
h F(H[S) Sx)
Thus, another potential state space representation is using the version space and the unlabeled examples that has been queried. The following structural lemma justifies that this is also valid representation.
Lemma G.7. f(S, 5x) Sxs)()
Proof. We prove this by backward induction on Sx.
Base case: Sx X. In this case, F(), E(H[S), has size 0 or 1; in both cases, J(S, Sx) = Cost (H[S), Sx) by their respective definitions the bases cases.
Inductive case. Suppose Sx) Cost(H[S). Sx) holds for any S and any Sx such that [Sx| 2 j + 1. Now consider any 5 and any Sx of size j.
If F(S, Sx) has size 0 or 1, Sx) Cost(H[S),, holds true.
Otherwise,
= [E(H[]) 2 2. By inductive hypothesis, for any x E X' \ Sx:
/(S [(, Sx U {x}) = Cost(H(SSU [() ux))
((5 U (x}) = Cost(H(S U ( ux fx])
[(5 U (x}) = Cost(H(S U U (z))
Therefore, for any æ:
Cost(HH {xx 1)]] (x))
max
1+ (()))) Ux 1+ ((r, (1)] Sx (x}))
= max
1 Cost(H((SU (1r, +1)},, Sx U (x))
+ Cost(H(S U {(z, -1)] U (x})
Taking minimum over x X \ Sx, we also have S(S, Sx) =
This completes the induction.
55

---

Published as a conference paper at ICLR 2024
H DISCUSSIONS ON ADDITIONAL RELATED WORKS AND FORMULATION
H.1 ADDITIONAL. RELATED WORKS
More related AL works: Our technical results are inspired by the minimax results on exact learning
Hanneke (2006). The noisy setup we consider is similar that of e.g. Castro & Nowak (2008).
Our algorithm belongs the class of "aggressive" learning algorithms (Dasgupta [2004] Golovin &
Krause 2010), which has been of interest for their sample-effciincy. As in (Sabato et al. 2013). we
also study label-dependent cost.
Abstaining Classifiers: Prior works have studied the task of learning a predictor with the ability to abstain (Puchkin & Zhivotovskiy 2021] Zhu & Nowak 2022). Our settings differ in that we aim to learn the true classifier that does not abstain. Rather, is the labeler that can abstain during the learning process slow-down learning.
Cross space learning: One of our constructions is related to the cross space learning (Tao et al. 2022) setup, where each sample is represented in multiple instance spaces. The key observation is that a strategic labeler can force learning on the instance space with the highest sample complexity, by abstaining on all other instance spaces.
Strategic Machine Learning: Strategic ML is a line of work concerned with agent manipulation of inputs into the MI. model (Hardt al., 2016). Much of this topic has focused on inference-time feature manipulation to influence the model output. And among this large body of work, there is a subset that deal with strategic manipulation of labels. In these settings, there are multiple agents, each of whom can (mis)rsports their data point label to manipulate the final model trained on all of their collective data (Perote & Perote-Penal 2004) Dekel al. 2010; Chen et al. 2018). This line of work largely focuses on the
setting, under various notions of strategyyroofness.
Our work differs from this body of work in considering, at training time (instead of at inference time), how a single labeler can maximize the query complexity of a learner under general hypothesis classes, which includes the linear hypothesis class.
We note that the idea of strategically slowing down the transfer of knowledge not a novel conception. It is real strategy that people have been documented to use in apprenticeships for example (Garicano & Rayo 2017; Fudenberg & Rayo 2019). spanning across several industries such as law, entertainment and culinary arts. There are two reasons that motivate the slowed transfer of expertise.
Economics of Knowledge Transfer:
Firstly, as described in (Garicano & Rayo 2017 Fudenberg & Rayo 2019), before the apprentice has learned everything and can graduate, he will be working for the teacher (or master is often used in apprenticeship parlance) and performing labor for cheap. Thus, this incentivizes the master to slowly down training, so that the apprentice takes longer to graduate and the master enjoy this cheap labor for longer.
Secondly, the master can better protect the value of his expertise by slowing down the transfer of his expertise. Overly fast transfer of the master's know-how would graduate too many apprentices too quickly, all of whom also have the same expertise and could thus reduce the value of the master's expertise.
In our setting, we consider the relationship between human teacher (labeler) and a student (machine). There is a similar incentive at play in that, while the learner has yet to learn At" the labeler is paid by the learner for the training labels provided. But once h² is identified, the student has no need for the teacher. And so, this incentivizes the labeler to slow down learning, in order to give and be paid for as many labels as possible. One difference we note is that in this setting, the transfer of expertise has more serious consequences in rendering the labeler's expertise obsolete, which is not the case in the apprenticeship setting.
H.2 ALTERNATIVE FORMULATIONS
In our formulation, the learner is not allowed to query an example multiple times and the labeler must label in way to guarantee that the learner identify h² at the end. It is reasonable to consider alternative formulations when we relax either assumption. Here we provide motivation for why both assumptions are reasonable:
56

---

Published as a conference paper at ICLR 2024
1. Learner only query example once: Allowing the learner to query would result in deadlock in the learning game. To see this, at time t, an AL algorithm would query the optimal point 2₁. If the labeler abstains and 2, is not removed from the data pool (since zy may be queried multiple times), the AI. algorithm would again query æ; at the next iteration. This is because the state has not changed. iy would still be the best point to query, and eligible to be queried since it is in the data pool.
Thus, for this alternative formulation to compile, there would have to be apt way to modify AL algorithms and ensure the process does not hang. This modification however may compromise the guarantees of the AL algorithm. By contrast, in the current formulation, a data point removed from the pool at each time step, thus always ensuring continued progress.
2. Labeler guaranteeing learning outcome: We assume guaranteed learning outcome for two reasons. The first for the purpose of analyzing minimax strategies. Indeed, in game theory, one needs to consider players who play optimally in order to study the Nash Equilibria/minimax query-complexity.
With that said, in Subsection 4.1 and 4.3 we study remedies when facing player that behaves sub-optimally, for instance due to lack of knowledge of H.
If the learner knows that the labeler may behave myopically, one idea is to loosen the "learning outcome" to approximate identifiability. In Subsection 4.1 we show how to extend our learning algorithms to the PAC learning setting.
In Subsection 4.3 we observe that the E-VS can be used to detect when an abstained point leads non-identifiability. Thus, the learner can this send certified "warning" to the labeler: if this (critical) data point is abstained upon, it will provably lead to non-identifiability. In this way, the learner can use the E-VS representation to prevent an myopic/unaware labeler from prematurely halting the learning process. Indeed, we note that non-identifiability is something neither party wants: the learner wants to learn, and the labeler needs realize the learning outcome in order to be paid.
57

---

Published as a conference paper at ICLR 2024
1
EXPERIMENTS
Jin of Piogebeee Lins
Ste wfrogobeens.oo Che
38 of www.eeeeeccc..ommmmmmmmmmm
0.0
p 0.15
= 0.3
75
p 0.45
0.6
Figure 3: The average number of examples queried by each algorithm across 50 randomly generated instances, along with its standard deviation (shaded region). For this set of plots, the labeling oracle random (and may not ensure identifiability), with varying probability of abstention p. In the plots, the lower the average, the better the algorithm (needing fewer samples).
79
15
0.0
p 0.15
P 0.3
0.45
0.6
Figure The average number of examples queried by each algorithm across 50 randomly generated instances, along with its standard deviation (shaded region). For this set of plots, the labeling oracle identifiable, with varying probability of abstention p. In the plots, the lower the average, the better the algorithm (needing fewer samples).
58

---

Published as a conference paper at ICLR 2024
To supplement our theoretical minimax analysis in the main section, we examine the performance of three learning algorithms, E- E-VS bisection, VS-bisection and randomly query (a point), in "average- case" settings by randomly generating learning instances.
Experiment Setup: We consider five sizes for the hypothesis class ranging from 15 to 40. Given a
particular hypothesis class size [H], generate 50 random learning instances by randomly generating the binary labels of hypotheses on examples x E X, where the number of data points | is varied from 30. Given learning instance, we consider setting (the underlying hypothesis) h* to be every h E H. and thus average the query complexity across random instances as well as across H. This is done to explore the average-case query complexity, where we do not focus on the query complexity of one particular h- = h E H. (as was done in some of the worst-case analyses).
We investigate two possible labeling strategies, with varying amounts of abstention p 0.15, 0.3, 0.45, 0.6. The first strategy is that given the underlying hypothesis h" E H. it abstains on labeling a point z with probability p. and outputs h" (x) otherwise (w.p. -p). This labeling strategy may be viewed as one that abstains arbitrarily, and may compromise identifiability. This models the labeling strategy of a myopic labeler. The second strategy a more careful, adaptive labeling strategy that always ensures identifiability. Given the underlying h", when is queried, it computes the resultant E-VS if x was abstained upon. If abstention leads to non-identifiabiiit.. labels and returns h" (z). Otherwise, it abstains with probability p and provides the label otherwise. This may be viewed as a more shrewd labeling strategy that always ensures identifiability, while using some abstention.
We plot results in Figure 3 and Figure 4 with Figure 3 corresponding to the first (random labeling) strategy and Figure [ corresponding to the identifiable labeling strategy.
Results:
We have a few observations. First, as a sanity check, we observe that in the absence of abstention (p 0.0), the E-VS and VS algorithm behave exactly the same and thus their performance should match, which they do as in the first plot of both Figure Band Figure 4
Next, we observe the general trend that the E-VS algorithm attains the lowest query complexity, followed by the VS algorithm and then the random querying algorithm. Moreover, the gap becomes more pronounced with the amount of abstention. This makes sense because the E-VS representation is designed to handle abstention, while the VS is not. This trend thus illustrates the effectiveness of using the E-VS representation in face of an abstaining labeler.
Finally, we see that the gap is most significant in face of a non-identifying labeler (as in plots of Figure B3. This because the E-VS algorithm can do early detection of non-identifiability and aptly halt the interaction, while the VS bisection and random querying algorithm cannot detect non-identifiability due to the use of the VS representation. We proved that the query complexity can be significantly larger in worst-case setup in Theorem 3.8 And here, see that in addition to the worst-case setting (as in Theorem 3.8). the E-VS also fares better in the average-case. Thus, this again affirms the robustness of the E-VS algorithm in face of non- non-identifying labeler.
59


Reviews:
[{"review_id": "ccNwmrli9c", "reviewer": "Reviewer_rYHN", "summary": "This paper consides strategic labelers for active learning task who may abstain to prolong the complexity of quering, such that they may be compensated with more labeling. The authors show that abstention could indeed enlarge query complexity, and present a novel minimax game as well as query complexity measure. A near-optimal algorithm based on E-VS bisection is designed to defend strategic labeling, and extensions to other active learning settings such as approximate learning, noisy labeling, multi-task learning are also discussed.", "questions": "I only have a minor question. This paper assumes \"the learner’s strategy corresponds to some deterministic, querying algorithm\". Nevertheless, non-deterministic policies such as Thompson sampling is quite common in some active learning tasks such as Bayesian optimization. How does these non-deterministic policies fit into the framework of this paper?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The strengths of this paper are its novelty of strategic learners for active learning tasks, as well as the theoretical soundness in the minmax formation and the effective version space bisection algorithm. This paper initiates the study of learning from a strategic labeler, which is original. The complexity of proposed E-VS method $O(\\log{|\\mathcal{X}|})$ clearly significantly improves existing VS algorithm of $\\Omega(\\{|\\mathcal{X}|})$.", "weaknesses": "I think the biggest concern that might weaken this paper is its lack of empirical evidence. Despite the theoretical gaurantees, some of the settings are probabilistic (PAC or noisy observations for instance), making empirical evaluation of the proposed methods valuable. I understand there are so many great results in this paper and there is a page limit, but including some simple simulation studies could be beneficial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "E7YT54DWMg", "reviewer": "Reviewer_ciAE", "summary": "This paper provides a set of theoretical evidence that labelers can slow down learning, in an active learning setting. The labelers is compensated by the number of labels that provided, and the learner wants to minimize the cost of learning. The paper proposes a maximal bisection algorithm for this setting and proves its sample complexity is optimal up to logarithmic factors. The paper further studies the noisy labels and multi-task learning, advancing its assumptions realisticity and applicability.", "questions": "Suggestions: Please consider \n1. moving table 1 after Definition 2.3 since it uses that definition.\n2. separating the notations of $V$ (see 1. in the weaknesses section)", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is very well-motivated; the problem is of increasing interest for the society by more and more ML applications in the wild.\n2. Quality: the paper flows smoothly by starting with the minimal setting of single task learning without noise and generalizes to wider settings. It proves lower bounds for the sample complexity of the problem, and proposes algorithms matching that lower bound up to logarithmic factors.\n3. Significance: this paper is introducing a new interesting setting into active learning literature and proposes near-optimal algorithms for it.", "weaknesses": "1. Clarity: the notation is convoluted; $V$ is used for both VS and a hypothesis space variable. For instance, in table 1, what is $V$? it seems introducing a specific notation for VS (e.g., $\\mathbf{V}$) or for the hypothesis space variable (e.g., $\\mathcal{V}$) could help.\n2. There is no experimental reported. It could help clarify many abstract concepts introduced in the paper using even synthetic data. Examples like Table 1 could help practitioners employ the algorithms introduced in the paper in their applications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OGKBnPAFJ8", "reviewer": "Reviewer_GuAP", "summary": "The authors study an active learning problem where the labeler can choose to give the correct label or abstain from labeling (refuse to label) for each query, in order to prolong the learner's learning process, hence get more reward. This is motivated by real-world scenarios where AI training data come from human workers who will eventually be replaced by AI once the AI is fully trained. The authors formalize this interaction as a game, propose query complexity notations to measure how long the learning process can be prolonged, and provide an active learning algorithm with a small query complexity. Extensions to approximate learning, noisy labeling, arbitrary labeling, multiple tasks, are discussed.", "questions": "**Questions:**\n\n(Q1) What is the purpose of Section 3.1 (in particular Algorithm 3 and Proposition 3.7) ? My rough understanding is that, Section 3.1 wants to show that finding the maximal E-VS bisection point $x$ (line 3) in Algorithm 2 can be done efficiently by Algorithm 3 (correct me if I am wrong). If this is the case, then what is the time-complexity of Algorithm 3? How does Proposition 3.7 shows that finding the maximal E-VS bisection point can be done efficiently?\n\n(Q2) What is the purpose of Section 3.9? The authors say that this section is to compare with EPI-CAL, but only give a formal result for EPI-CAL ($\\Omega(\\sqrt{m})$ samples in Proposition 3.9) and didn't give any formal result for the algorithm they proposed for comparison.\n\n(Q3) How is this paper's model and result related to the \"well documented\" phenomenon that \"teachers (masters) strategically slow down the training of their apprentices (Garicano & Rayo, 2017)\" ?\n\n\n**Suggestions:**\n\n(S1) The presentation of Section 5.1 and 5.2 is really confusing.\n\nSection 5.1 is about upper bound on the multi-task query complexity. Theorem 5.3 gives an upper bound under a regularity assumption and for the $c_{all}$ label cost. Proposition 5.1 is a counterexample where the upper bound doesn't hold without the regularity assumption, **but the authors didn't say which label cost this Proposition is for**. Proposition 5.2 is an example where the upper bound in Theorem 5.3 doesn't hold for the $c_{one}$ label function.\n\nSection 5.2 is about lower bound (for the $c_{one}$ cost). Theorem 5.6 gives a lower bound on the multi-task query complexity under two conditions for the $c_{one}$ cost, while Proposition 5.4 and 5.5 are counterexamples where the lower bound does not hold if the two conditions are not met.\n\n**I would suggest presenting the theorem first, and then give counterexamples.** And **can the authors give a lower bound result for $c_{all}$?**\n\n(S2) $c(T(x))$ in Definition 3.1 is undefined.  (It is mentioned later in the paper but not here.)", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "(1) The problem is well-motivated.  Although the \"teacher wants to prolong learning process\" phenomenon is not new in other literature, it is an important, new problem for the active learning community.  This paper can potentially lead to many follow-up results. \n\n(2) The various definitions of the query complexity are interesting. Theoretical results are sound.", "weaknesses": "W1: My major concern is that this paper has two really strong, restrictive assumptions. To illustrate this, let me describe the following scenario: Suppose there are two hypotheses $h_1$ and $h_2$ that give the same labels on all but one example $x^*$ (e.g., the hypotheses $h_1$ and $h_2$ in Table 1). Consider the case where the labeler correctly labels all examples except for $x^*$, and abstains from labeling $x^*$. In this case, the learner cannot tell whether the true hypothesis is $h_1$ or $h_2$. I can imagine that this scenario can easily happen in a real-world labeler-learner game where the labeler wants to prolong the learning process as long as possible. This is a key tension in the \"human-AI substitution\" game that motivates this paper. However, the authors simply disallow this scenario to happen by making two strong assumptions in their model:\n\n(1) **The learner is not allowed to query an example multiple times**. If the learner can query an example multiple times, then the labeler can first abstaining from labeling for a while and then eventually give a correct label. It is very natural in practice for a learner to query an example multiple times until he gets a label. But this is not allowed in the authors' model.\n\n(2) Under the assumption that the learner can query each example only once, the authors further assume **\"Guaranteeing Learning Outcome\"** (Section 1.1): the labeler must label in a way to guarantee that the learner can identify the hypothesis $h^*$ in the end. However, this requires the labeler to know the hypothesis space $\\mathcal H$ of the learner very well so that he will not abstain from labeling critical examples (e.g., the $x^*$ above). **This is a strong assumption -- how can an average human worker knows the hypothesis space of the sophisticated machine learner?**\n\nI might change my opinions if the authors can provide some strong motivations or real-world scenarios to support these two assumptions.\n\nW2: the presentation of this paper is not very good. See my Questions and Suggestions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Q7yBT9sFSr", "reviewer": "Reviewer_k54k", "summary": "This paper discuss the game between labeler and learning system, where the labeler's objective is to maximize profit, by following some strategy to choose abstaining labels and thus the learning is slowing down; meanwhile, the learning system's objective is thus finish learning as soon as possible, which puts higher requirements on the active query strategy, that is should be robust to abstaining. The paper theoretically analyzes the above observations and proves that absteining labels can indeed destroy the sample-efficient active learning system, base on which the authors further propose a near-optimal algorithm that is robust to absteining.", "questions": "See weaknesses above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "-  The problem this paper concerns is clearly defined, and all formalizations are clean.\n\n-  The paper is well-organized with clear writing.\n\n-  Modeling two parts of machine learning with respectively conflicting objectives by game and then it can be analyzed with some game-related techniques is novel.", "weaknesses": "- The difference between an adversarial labeler and an abstaining labeler is not discussed.The difference between the concerning problem from active learning within an adversarial environment is not clear. Meanwhile, though it is mentioned that the labeler's strategy is identifiable, it is still unclear if it is the worst case.\n\n- The motivation of the problem is too detailed, such that it can hardly be extended to other applications. It is recommended that real-world experiments should be conducted to validate the problem or it seems too artificial.\n\n- The theoretical results are does not belong too much surprising information and has limited contribution to the algorithm design, since the algorithm design is mainly based on the labeler's strategy that is already pre-defined.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)