Formal Models of Active Learning from Contrastive Examples
Authors: Farnam Mansouri
Hans U. Simon
Adish Singla
Yuxin Chen
Sandra Zilles
Venue: NeurIPS 2025 poster ()
Keywords: membership queries
self-directed learning
learning boolean functions
learning from contrastive examples
Primary area: theory
TL;DR: This purely theoretical paper introduces and studies new models of query learning with contrastive examples.

Abstract: Machine learning can greatly benefit from providing learning algorithms with pairs of contrastive training examples---typically pairs of instances that differ only slightly, yet have different class labels. Intuitively, the difference in the instances helps explain the difference in the class labels. This paper proposes a theoretical framework in which the effect of various types of contrastive examples on active learners is studied formally. The focus is on the sample complexity of learning concept classes and how it is influenced by the choice of contrastive examples. We illustrate our results with geometric concept classes and classes of Boolean functions. Interestingly, we reveal a connection between learning from contrastive examples and the classical model of self-directed learning.

Formal Models of Active Learning from Contrastive Examples
Farnam Mansouri University of Waterloo
Hans U. Simon Ruhr- Universivvysstyy Bochum
15mansou@uxaterloo.co
hans. simon@rub.de
Adish Singla
Yuxin Chen
Max Planck Institute for Software Systems adishs@@piisswe.or
University of Chicago
chenyuxin@ucchicagoocoo edu
Sandra Zilles
University of Regina and Amii sandra. zi zwlzzillllllll zilles@uregina. ca
Abstract
Machine learning can greatly benefit from providing learning algorithms with pairs of contrastive training exaiples-typically pairs of instances that differ only slightly, yet have different class labels. Intuitively, the difference in the instances helps explain the difference in the class labels. This paper proposes theoretical framework in which the effect of various types of contrastive examples on active learners studied formally. The focus is on the sample complexity of learning concept classes and how it is influenced by the choice of contrastive examples. We illustrate our results with geometric concept classes and classes of Boolean functions. Interestingly, we reveal a connection between learning from contrastive examples and the classical model of self-directed learning.
Introduction
In machine learning, contrastive data has been used for various purposes, most notably in order to reduce the number of training samples needed to make high-quality predictions, or to explain the predictions of black-box models. A contrastive example for a labeled training data point (z, b) with label b {0, 1} could be, e.g., a labeled point (z', - b). such that x' fulfills some additional predefined property. This additional property could be defined in way so information for learning. For instance, a constraint on x' could be that is the closest point to x (in the given pool of data points, and with respect fixed underlying metrie) that has different label from b. Such examples are often called counterfactuals and have proven useful in various learning settings, including explanation-basee supervised learning [8] but also reinforcement learning [16 22). and learning recommender systems (24)
convey helpful
Intuitively, counterfactuals present learning algorithm with an important feature property of data object that crucially affects its classification. For example, a training data point x might be an image of a cat, together with its class label (the subspecies of cat). A counterfactual piece of information might be an image z' of cat that looks similar to the cat in x, yet belongs to a different subspecies. The main feature distinguishing x' from could be highlighted in the image, as means of explaining the classification of z. Similarly, contrastive information can be used in natural language processing and many other applications, and was applied successfully in representation learning, see,
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

for example, S 19 19 20]. Interestingly, also human learners exhibit improved classification abilities when they are taught with the help of such visual explanations (2T)
Theoretical studies have analyzed the sample complexity in specific models of learning with con- trastive examples, such as PAC-learning of distance functions [3), active learning with a greedy teacher (26). a randomized teacher [23] or an adversarial teacher [9] Other formal studies focus on specific aspects of learning with contrastive information, for instance, how negative examples influence the learning process [5 or how individual loss functions affect contrastive learning [15.
One example of the use of contrastive information, particularly relevant to our study, is counter- caample-guddds program synthesis (CEGIS) in formal methods research [2]. Consider the task of synthesizing program that satisfies a given specification S. In CEGIS, synthesizer generates candidate program P. which is then checked against the specification S by a verifier. If P violates S, the verifier returns a counterexample witesssing the violation. This process is iterated until program satisfying S is obtained. We can see each candidate program P as query to the verifier, which acts as an oracle. Importantly in this setting, the oracle follows known procedure. In particular, one can implement the oracle to return a specific counterexample (e.g., a smallest one) that acts as a contrastive example, and the synthesizer can be tailored the knowledge of how the counterexample is generated. For example, if the synthesizer knows that a smallest counterexample is generated, it can rule out all programs for which there would have been smaller counterexamples.
Motivated by such applications in program synthesis, the main goal of this paper is to introduce and analyze formal settings of learning from contrastive examples, specifically modeling situations in which the learner has knowledge of the way in which the oracle selects contrastive examples.
We propose a generic formal framework, encompassing various ways in which contrastive examples are chosen (i.e., not just as counterfactuals); this is the first contribution of our paper. We then analyze several settings in this framework w.r.t. the resulting sample complexity, i.e. the number of examples required for identifying the underlying target concept, resulting in various non-trivial upper and lower bounds on learning classes of geometric objects or Boolean functions (most notably 1-decision lists and monotone DNFs); this constitutes our second main contribution. Finally, as a third contribution, we reveal surprising connection between the sample complexity of contrastive learning and the mistake bound in the classical notion of self-directed (online) learning [13]
2 Models of Contrastive Learning
Let X' be any (finite or infinite) domain that is bounded under some metric. A concept over X' is subset of X: we will identify a concept C' C X' with its indicator function on X, given by C(x) = 1 if x C, and C(x)
0 if E X C. A concept class over X' is set of concepts over X. If C' and C' are two concepts over X, then ACC, C") refers to the symmetric difference of C and C". Moreover, 8(C, C") is the relative size of A(C, C') over X measured under the standard uniform distribution. In case X' is finite, this is just |ACC, C)I/(2')
(C) denotes the minimum corst-case number of membership queries [4] for learning concepts in C. where the worst case is taken over all concepts in C and the minimum is taken over all membership query learners. Moreover, VCD(C) denotes the VC dimension of C.
Suppose a concept class C is fixed and an active learner asks membership queries about an unknown target concept c E C. In addition to the label of the queried example, the oracle might provide a contrastive example, e.g., similar example of opposite label. We propose a more generic setting in which the active learner is aided by an oracle that provides labeled examples complementing the actively selected ones in some pre-defined form (using a so-called contrast set). The learner tries to identify an unknown target concept C* E C' in sequential rounds. In round 1, the version space (i.e., the set of possible target concepts under consideration) is C₁ := C. Round i, 2 1, is as follows:
1. The learner poses a membership query consisting of an instance 2; E X. v\)] E (0, 1) (X {0. 1}) such that: 2. The oracle's 's response is pair [ys, (æ%
y: C* (x;) and yo = (*{)), (..)), Vi and s/ are the correct labels of and x/, resp.. under the target concept,
x/ E CS Ch C.). where CS(x,, O*, C.) C X is a set of instances called the contrast set of xj wrt O* and C. The oracle is adversarial, in that it can pick any

---

r CS( CC,C,) ) as part of the response to query If CS C*, C,) is empty, the oracle returns dummy response w. to convey that no contrastive example exists.
3. The version space updated: in particular, the new version space C++1 consists of all concepts C' in C₁ for which ((x))) = yj and:
CS(zi, C.C.) = 0 in case the dummy response w is received, C(x²) v/. and x' CS C,C,) otherwise.
This definition assumes that the learner knows the function mapping any tuple (I,, C,); to the set CS(r;, C, C.). The core difference to the traditional notion of version space is that the learner can reduce the version space by knowing the contrast set mapping CS: a concept C, even if consistent with all seen labeled examples, is excluded from the version space if x & CS(r,, C,C,) for some i.
The labeled examples collected in the first n rounds, together with the corresponding version spaces, then form an interaction sequence of length n wrt CS, given by
[<21 y1). (a',, C2), (I UnJ, (4%, V.)). Ca+al.
This interaction sequence s-approximates the target concept C* C (for some 2 0) iff Co+1 S {C E C 8(C", C) < e). The sequence identifies the target concept C* E C iff C,+1 [
Accordingly, we define the following notion of sample complexity.
Definition Assume X, C, CS, and are fixed. The e-approximate contrast sample complexity of learner I, on C* wrt C, denoted by Scsl Scs(L., C E) is the largest length of any valid interaction sequence = [(x1,))), )1,, (x/, v1) C2l...., [In, Un); (I' vn)), Cn+1] that e-approximates C E and in which I, chooses Ti+1 on input of the history [[x1, V1), (2 (f):)1)).... V))....,, (I,, V.), (1/g Vol, for all i. (Here the worst case length is taken over the sequence of possible choices of x made by the oracle.) Finally, Scsl C,, For exact learning, we consider only interaction sequences that identify C*, and write Ses (C) instead of Scs(C.,,))) (c,(C.E).
supc-ee Scs(L, (L, C,E), and Scs(C, inf (os(L, C,
Our model assumes the learner has perfect knowledge of the set CS of candidates from which contrastive examples are chosen. This assumption, while often too strong in practice, is indeed realistic in program synthesis settings, where the learning algorithm knows the rules by which the oracle selects counterexamples, as discussed in Section [ for CEGIS 2 Here the designer has full control over both the oracle and the learner. In addition, model is useful for further reasons:
It can be easily modified to address additional real-world settings, e.g., one can assume that the learner's notion of CS is not identical, but similar that used by the oracle.
Lower bounds from our strong model (e.g., our bound in terms of the self-directed learning complexity, Theorem 17) immediately transfer to such weakened versions of the model.
first observation that, without limiting the choice of the contrast set CS, the contrast oracle is extremely powerful; any encoding of concepts in C subsets of X of size at most l can be used to define contrast sets witnessing a sample complexity of at most k:
Proposition 2 Let C be a countable concept class over a countable X. Let T C - 2 be any injective function that maps every concept in C to finite of instances. Then:
1. There is some CS with Scs(C) & supcee IT(C)) +1.
2. (C) & T(C') for C + C², then there is some CS such that Ses S supeec [T()).
In particular, X is finite, then there is some CS such that Scs Scs(C) < 1+ E (1x1) > [C]]. If is countably infinite, then there some CS such that Scs(C) =
Proof. (Sketch.) Let 31, ... be a repetition-free enumeration of X, and CS(2,, C) (my} for i, Iy TCC).. A learner sets receives x = Ty as a contrastive example, then j 2 n,. The learner will
j' = min(j j asks a query for Zng- then set n1+1 + 1 and proceed to iteration + 1. See the appendix for details.
and starts with iteration 1. In iteration i,
3

---

Thus, unlimited choice of the mapping CS reduces learning from contrast oracle to decoding a smallest encoding of concepts as sample sets. Therefore, the remainder of our study focuses on more natural choices of contrast sets. In particular, when fixing function d : X' x X - R220 (interpreted as a notion of distance), two natural choices of contrast set mappings are the following:
Minimum distance model. Our first contrast set mapping, dubbed the minimum distance model, makes the oracle provide an example closest to x, among those that yield a different label under C' than
I. For discrete X. this translates to CS min (z, C*) arg min ( [d(r, x') x' E X, C(z') # C(x)).
For continuous X. it can happen that no point x' E X' with C(z') + C(x) attains the infi- mum of the values d(x,,z) for such x' ! To accommodate this case, we define CS (z, C) lim;- x². for Cauchy sequence (x²); with C(2() * C(x) for all i]. (This definition may in some cases allow the oracle to return contrastive ex-
arg m ample with the same label as that of x. This is helpful when no point x' E X whose label differs from C(x) attains the infimum of the values d(xr, x') for such x'. but mostly for complete metric spaces, where the limit of a Cauchy sequence is guaranteed to exist P
x' E X, x'
Proximity model. For our second contrast set mapping, the learner also selects radius r indepen- dently at each round, allowing it to ask for a contrastive example within a certain vicinity of the query point x. For discrete X, we then define CSprrx (z, r; C) = {x' E X C(x') A C(x), d(x,xx) S r]. i... the contrast set contains all x' r-close to x that have the opposite label to Z. For continuous X, similar adaptation as for the minimum distance model yields CSd prex (ar, r, C)- = {a' e X)d(x, x') S r, x' limm; = for a Cauchy sequence (a));; with C(x,)) A C(x) for all i]. We refer to this choice of contrast set as the proximity model. Note that the oracle here need not choose a contrastive example at minimum distance; any example in CS
prox (I, r, C²) is allowed.
Since these mappings do not depend on the version space, we dropped the argument C, in CS(z, C).
The following useful observations are easy to prove; the proof of Remark 3 is given in the appendix.
Let C be concept class over complete space X with metric d, x E X, and C E C. Suppose there is some x' E X with C(x) # C(z') and d(x,,') < co. Then (i) CS (z, C) # 0, and (ii) if 2 d(x,,²) then CS prox (x. r, C) + 0.
Remark 3
Remark& 4 Suppose that CS and CS' are mappings that assign to every pair (x, C) E X x C a subset X. Suppose, for every (x, C) X x C, we have (i) CS(z, C) S CS' (a, C) and (ii) CS(a, C)- = implies CS' (z, C) = 0. Then Ses (C) < Scs (C). Moreover, for any s, e) < Ses (C,
Remark 5 Let C be a concept class over a complete space X with metric d. Then Scsd (C) S Scs4 (C) < (C).
min
prox
When X' is finite, we can extend Remark al follows.
\ x) and 8d max [a(()),, (Note that Sa S |2| - 1 for finite X). Then Sesp (C) S [log(sa) Scsy (C).
Proposition 6 Fix X and d: X x X + IR20, Let Sa(x) = (d(xx))) 1 x' E X
Proof. Let L learn any C E C with < Scsy (C) queries to the minimum distance oracle w.r.t. d. We construct a learner L' with access to the proximity oracle, using L as a subroutine. Suppose L poses a query x. Let Tmin = min (x, (x,C) d(a, x²). First, I,' sorts all numbers in Sa(x)) in increasing order and determines the median r of that list. Then L' poses the query (z, r). The contrastive example returned will be w iff d(x,,²) < mmin- Hence, with binary search using [log(sa) queries, 1. can determine an x' with opposite label to x and ((x) = Tmin- This x' is among the admissible answers to the query by L. Thus, T.' makes < [log(sa) queries for every query that L makes. M
'For instance, if C is closed interval in IR and the query point lies inside this interval, then there is no point outside the interval that has distance closer to æ than any other point outside the interval. "The definition of Cauchy sequence relies on notion of metric. In our examples in continuous domains, we will use the fi-metric both as this metric and as the function d in the superseript of CSd

---

without CS
CS prox
CS min (even for exact identification)
(a) thresholds
(log =)
(log
(b) rectangles
(log( () ((log(()) )), Oloog( ))
Table I: Asymptotic sample complexity when e-approximating (a) one-sided threshold functions,
and (b) axis-aligned rectangles in l dimensions, for various learning models, with the & -mmeric.
3 Sample Complexity Under Various Metrics
This section illustrates our notions of learning from contrast oracles under various metrics d. We begin with two examples on the { fi-metric.
Example Consider the class of one-sided threshold functions {x S 8*) for 6* E E [o, 1]. Table aa) displays the asymptotic sample complexity of various models of s-approximate learning. The result on learning without contrastive examples is known (25J. By a straightforward adversary argument, the sample complexity of the proximity model is in 22(log 1/c). As learning without contrast oracle is no stronger than learning in the proximity model, both models here have the same asymptolic complexity. In the mirimum-distance model, irrespective of the first queried instance, the contrastive example will be 0*, Thus, the target can be identified (even exactly!) with one query.
Example 2 Consider the class of all k-dimensional axis-aligned rectangles over X= the ( distance as metric. Table(bb) displays the asymptotic sample complexity of various models of E-approximate learning. The result on learning without contrastive examples is known, see, e.g., f14y. Let C* be target rectangle with the corner of lowest ( didistance from 0 (0.....,) 0) being x, and the diagonally opposed corner being y.
= [0, 1]k, with
If C* (0) 0 then the contrastive example x' will be x. Similarly, by querying 1, the learner can determine y. Thus, Scsá S 2. Also.fol determining C*, at least two distinet positively labelled
In the minimum-ddstance model, let a learner first query O. (0) = 1 then clearly
instances are required, which is impossible to acquire with one query.
To verify the upper bound in the proximity model, note that d(x, 0) S. k for any x. The learner starts by querying
= 0 and 11 k. The contrastive example will be w iff 11 < d(xx 0). Thus, the learner determines whether d(x,, 0) S rı or not. Learning continues with a binary search until finding a radius such that d(x, 0) < T₁ S d(x. 0) + = f/2 t 2 log(2k/E) + 1. Let x', be the
contrastive example. We derive d(I(, x) S d(x';. 0) d(x, 0) S rt d(xx, 0) S & (noting that d(zl, 0) d(x, 0) > at step t). Similarly with log(2k/s) + samples the learner can find E [0, 1] such that d( (z.y) y) I E/22. Therefore, the rectangle with bottom left corner xf and top right corner z has ervor less than E.
The lower bound Scisa prex (C, E) is inherited from that in Example 7 using the same argument.
The next few examples concern concept classes over the Boolean domain Bm 10, 1 and learning from a contrast oracle the minimum distance model with respect to the Hamming distance as metric. For I C [m]]. we denote by 1, the Boolean vector with Is in positions indexed by I and Os elsewhere; let 1 1 [m] The notation Oy and 0 is understood analogously.
The next two toy examples will show that a certain metric (here the Hamming distance) may be suitable in the context of specific concept class, but will become misleading the minimum distance model when a slight representational change is made to the concept class. These toy examples are merely meant to illustrate the power and limitations of our abstract model in extreme situations.
Let X {0, 13"h. Let Cm Camon consist of all monotone monomials, i.e., logical formulas of the form Us, A...AVs, for some pairwise distinct i1...., i and some l E {O....,m, m.). The concept associated with such a formula contains the boolean vector (bi.....br .b))) iff bi,
Example 3
bi.
(where the empty monomial is the constant 1 function). Let d be the Hamming distance. Then: (MM
m. (2) Ses (Cmmon) 1. (3) Sosa (Cmmon) = O(log m))
Proof. (Sketch.) (1) is folklore. For (2), learner will first query O, which has the label 0 unless the target the empty monomial. The unique positively labeled example of smallest Hamming distance to the all-zeroes vector has ones exactly in U/ Vig. where the target concept is Ui A... A Usg
5

---

Thus, a single query identifies the target. The upper bound in (3) follows from Proposition 6 while the lower bound is obtained via case distinction. Details are in the appendix.
Now, we will see how a small syntactic change from mmon to a class mmon (adding an (m + 1 ssst component to the boolean vectors) can make contrastive examples useless (see appendix for details).
Example 4 Let X" {0, 13 The concept class mmmon over X' is defined to contain, for each C E C Cimmour the concept C" E Cimmon constructed via C" C"(bi.... .......,m.... 0) = C(b,,.... Dm and C² (bi......,bu bb. 1) = 1 C(bl...... bm). No other concepts are contained in Cmmon Let d be the Hamming distance. Then S[MQ](C
S (Cmmmon) Scsd (Cmmon) m.
While the Hamming distance is useless for the class Cmmon in Example other functions d might still allow for efficient learning in this setting. Such functions, however, might be rather "unnatural" notion of distance (arguably though, the class Camon in Example also somewhat "unnatural"), We will hence focus most of our study on intuitively "natural" functions When learning Boolean functions, we consider Hamming distance a natural choice.
Let mon denote the class of monomials over the Boolean variables .i...., Um (including the empty monomial which represents the constant- I function). We assume that each Boolean variable occurs at most once (negated or not negated) in a monomial. Since monomials like v A 8 are thus excluded, the constant-() function does not belong to C A concept class dual to Cm is the class of clauses over the Boolean variables (v1,..., Um) (including the empty clause which represents the constant-O) function but excluding clauses like v; V on which represent the constant-1 I function). We denote this class by Clauss and obtain the following result, the full proof of which is given in the appendix.
(Cmo Theorem 7 Scidd min
U C claus)
2, where d is the Hamming distance.
Proof. (Sketch.) One first constructs a learner L, for Cm monn in the proof of Example and then a learner Ly for claus by dualization from L,. It suffices to describe a learner L that maintains simulations of LA and Ly and either comes in both simulations to the same conclusion about the target concept or realizes an inconsistency in one of the simulations, which can then be aborted. O
For Scs prox' prox" upper bound is obtained from Proposition 6 and Theorem 7 noting that the Hamming distance can take only m distinct values for pairs xI), with x + x'.
Corollary 8 Scsp (Cmon) ) US Sesd Cpoo prox
(Cm claus) S 2 llog mi), where d is the Hamming distance.
We conclude this subsection with an example of somewhat natural concept class for which the minimum distance model under the Hamming distance is not very powerful.
Let X = {0, 13th and let Cpar be the class of parity functions, i.e., logical formulas of the form Us L .t... @ Use for some pairwise distinct i1,.... .ig and some ls E m]. Then (Cpr)(Cpar) = m and m 1 S Sesu (Cpar) = Scsy, prexe (Cpar) S m.
Example 5
Proof. ([M))(Cpar) = is trivial, and immediately yields Scsa (Cpar) m, Sesa (Cpar) S m. prox Suppose the target concept is c* = 0i2 + .... ① Usg For any instance x, we have d(x, x') = 1 and (x()) o c* (x'), where x' results from x by flipping the value of component it. When always using a query radius rt- = 1, the proximity model is thus equivalent to the minimum distance model. The lower bound is witnessed by oracle that contrasts any x, with the example x, resulting from x, by flipping the component 11. This provides no information about variables other than V4,
mmn
O
We conclude this section with the discrete metric do. defined by do(ar, x') if x', and da(2, x²) 1 if x + x'. Now CSd min (z, C) C CSde min (Ir, C') for every (x, C) E X x C and every d: X X 20 Moreover, CSé (I, C') = 0 implies OSde (x.C) 0. Remark thus yields:
Corollary 9 For every concept class C. the term Scs. mm (C) is maximized, if the underlying function d: X X 20 equals the discrete metric do-
In what follows, if O is list of oracles, use S[0) to denote the sample complexity of learning with access to all oracles in O. Let Ex* be oracle returning a positive example x, i.., X

---

with (x)x) 1 (or dummy response if no such I exists). When called several times, the oracle may repeatedly present the same example. Let EX be the analogous oracle for negative example. The following result says that, under the metric dg, the contrast oracle does not provide significantly more information than the membership oracle (although, for some special concept classes, this small extra information can make big difference). The proof is given in the appendix.
Theorem 10 S|EX+, EX MM](CC) - < Sosta (C) S SSTEX,, "XT,MQ((),
Example 6 Consider C to be the class of all singleton concepts over finite domuin X where n == [X] 2 2. It is known that (C) = n 1. But single call of the oracle EX reveals the identity
of the target concept. follows that S|EX* S EX .MQ[(C) =Scsta (C) = 1.
4 Lower Bounds
In this section, we will derive some lower bounds on the sample complexity in our models of learning from contrastive examples. All our results here are for finite instance spaces.
4.1 A Metric-Independenn Lower Bound
Self-directed learning [3] is a model online learning, in which the sequence of data be labeled is chosen by the learner as opposed to the environment. The learner gets immediate feedback on every single prediction, which allows to adapt its data selection to the version space sequentially. is then assessed in terms of the number of incorrect predictions it makes across all data instances in X²; as usual, we consider the worst case over all concepts in the underlying class C.
Definition 11 ((13) Let C be a concept class over a funite domain X, n = |X A self-directed learner for C. interacts with an oracle in rounds. In each round, I. selects not previously selected instance E X and predicts a label for x. The oracle knows the target C E C and returns the label C* (x); b + (x), the learner incurs mistake. L proceeds the next round until all instances in X' have been labeled. The cost of L on O* is the number of mistakes made in these n rounds. The cost of L C is the maximum cost of L on any C E C.
The self-directed learning complexity of C, denoted by SD(C), is the smallest number c such that there exists celf-directer learner for C whose cost on C is c.
This complexity notion was analyzed relative to other extended to infinite concept classes and multi-class settings [10]. Interestingly, SD can be used to derive a metric-independent lower bound on the sample complexity of the minimum-distanee model.
parameters 6 and
Theorem 12 IfC is defined over finite X, and d X x X R22 then Sosa min (C) Z [SD(C)/2].
Proof. Fix d: X' + R220 and let L be a learner with access to a minimum minimum-distance oracle w.r.t. d, which makes at most Scst (C) queries to identify any C' E C. We construct a self-directed learner L' for C which calls L min After receiving feedback, L' passes on the correct label b for x to L. In addition, L' must provide contrastive example for æ, which is obtained as follows: L' sorts all instances in X' in increasing order w.r.t. their distance from x as measured by d. It then predicts the label b for instances in this ordered list until it observes the first mistake, say for x'. Then x' must be closest instance to x with a label opposite from b. Hence, x' is passed on to L as contrastive example. If no such x' is found, then L' gives the response w to L. This proceeds until all instances X' have been labeled.
subroutine. If L poses a query for x, then L' predicts 0 on
Each time L' calls L, it incurs at most two mistakes, namely one for its prediction on the instance x queried by L, and one for its prediction the contrastive instance x'. In total, thus L' makes most 2t mistakes, where t is the number of queries posed by L. We obtain the desired bound.
Remark 13 For each m E N, there is a concept class C. with VCD(Cm) = 2 and (D 2 [8I. In particular, there no relationship between VCD and SD. Thus, no matter which function d: X X R is chosen, there exists upper bound Soss as a function of VCD. min
7

---

We will see multiple cases in which the lower bound provided by Theorem 12 is not met. As a small warm-up example. there are finite classes of VC dimension 1 for which Scst (C) while every class of VC dimension satisfies SD 1 (see the appendix for proof details):
Example 7 Let X' = (z1, T2, J. Let C consist of the concepts {Iı, 13) [ra). ( 13 and {22)-
Then C satisfies SD(C) = VCD(C) 1, but Sesd (C) 2 for any d X x X R min
However, for classes of VC dimension 1, we cannot increase the gap between SD and mina Scsp...
Theorem 14 For any finite C with VCD(C) = 1 there exists metric d with Ses (C) S 2.
min
The proof (see appendix) uses the fact that every X' has at most one label b E {0, such that (z, b) "teaches" " a unique e in the model of recursive teaching [[T]. The instances in X can be partitioned according these labels. This partitioning is used to define a metric that places instances in the same part closer to one another than instances in different parts. Now a learner choosing one specific query from each of the two parts will receive enough information to identify the target.
4.2 Lower Bounds Using the Hamming Distance
Let DLm be the class of I-decision lists over the Boolean variables uI,..., Um. Each list is of shape
= [[1,, ((11,b)).... (Ce, (l2, b2+1]
(1)
where: = 2 0, l, E {(i, .i,..., Um, F and bq E (0, 1}. We assume that each variable occurs at most once in L (negated or not negated). We say that a point a Bm is absorbed by item of L if the literal 4 applied to a evaluates to 1 while the literals f,,..., , applied to a evaluate to O. The list L represents the following Boolean function fc: (i) If a absorbed by the k'th item of C, then fc(a) = bg. (ii) If a is absorbed by none of the z items of C, then fc(a) = bz+1-
The following lemma observes structural property of concept class C which allows us lower- bound the sample complexity in the minimum distance model (with the Hamming distance) using the membership query complexity of certain subclass of C.
Lemma Suppose that a concept class over Bin, and C' is a subclass of with the properties (PI) For each a E Bm with Om = Yy and each C E C', we have that C(a) = 1.
(P2) For each a with Om = Vmn and am-1 = 1m-1 and each C C', we have that C(a) = O. For i E {m, m 1}, here y: E (0, 13 is fixed, y/
Yi, and C" is the set of all concepts of shape
(a1, (........00 (0l....,mm-))) 2m- + C'ai,..., Om vm- Vm) for C E C'.
Then Sesd (C) 2 Sesd (C') S(MQ](C"), where is the Hamming distance.
min
Proof. (Sketch.) Suppose learns C' from & queries to a contrast oracle in the minimum distance model. We show that L can be transformed into L' which learns C" from at most q queries to membership oracle. To this end, let C" be the target concept in C" and let C" with C' (a)a) be the corresponding concept in C'. Note that L has not uniquely identified C" in C" as long as the subfunction C" is not uniquely identified in C" L' can therefore identify C" in C" by maintaining simulation of L until L has identified C' in C. Details given in the appendix.
=
This lemma can be used, for example, to prove Scsd (DLm) Z 2 2 1, where d is the Hamming distance. Our proof of this statement, however, establishes an even stronger result. To formulate this stronger result, we first need to introduce some notation.
Consider a decision list C of the form [.. We say that L has i label alternations if the number of distinct indices i E [z] such that 6,-1 * by cquals k. Let DL be the subclass of DLm which contains all decision lists with at most & label alternations. It is well known that (i) DL contains only the constant-1 and the constant-O) function, and (ii) DL Cm U Cm Now the proof of the following claim builds on Lemma [5] see the appendix for details.
Celaus"
Corollary 16 Sosd (DLM) 2 2 1, where d is the Hamming distance.
8

---

Interestingly, this bound on Sosé (DLm) (using Hamming distance) is not an effect of our metric- independent lower bound in terms of SD (Thm. 12). As seen below, S (DI.m) asymptotically exceeds SD(L..) Thus, the lower bound from Thm. 12 is not always asymptotically tight.
For DI we saw that the sample complexity in the minimum Hamming distance model is expo- nential in m. By contrast, SD is most quadratic in m. To prove this, let block in [(e,, 61), ..., (C,, by), bo+1] be any maximal substring (l,, bi),.... (lotjs bi+s) with by = bi+s-
Theorem 17 There exists a self-directed learner for Dem that makes, on any target list C E DLms at most 4km mistakes where k is the number of blocks in C
Proof. (Sketch.) For each of the 2m literals, 2 queries suffice to determine whether it occurs in the first block of the target list. Iteratively, one consumes I 4m queries per block; see the appendix. D
We now present a second example of a natural class of Boolean functions for which SD asymptoti- cally smaller than Sesd min (C), where d is the Hamming distance.
Definition 18 Fix 8, m E N. An s-term 2-MDNF of size m is a function f: (0, - (0. 1) of the form (11, U2, ... Um)) M1 V M2 V ... V M,, where each M, is monotone monomial with at most literals. We use MDNN to refer to the class of all s-term 2-MDNF of size m.
Cm,..
Theorem 19 (largely due to 13 Let be the Hamming distance. Then SD(C 5, while
Scsd 2 S[MQ](CMDNE
(0m-23--- 1,2-1,2-1 which is at least
(= ()(s 1) log(m - 2) +
2x-2 (5-1)/2
where a = 1=11
if 8, and a
Proof. See 13 for 3D(MMDNF)
showed the lower bound on S[MQ (CMDNF (0 1,2-1,
Let C' be the subclass of Cm. MDNF with concepts of the form M₁ V... V M V Vu where Um E M
for 1 i
1. Then C" satisfies properties (P1) and (P2) of Lemma 15 with 3m 1, and
9m-1 = 0. Then C" = MIDNFm-22t-L.-22 and the result follows from Lemma 15
Theorem 19 reveals gap between SD and the sample complexity of the minimum distance model under the Hamming distance. While we do not know of any "natural" function d X' x X - R with which to close this gap, it can be closed if we allow the learner and the contrast oracle to share a new function d after every query. By S Cs(ctt) we denote the sample complexity resulting from
interaction sequences at which, in step f, the set CS is defined using the distance function d'. The same proof as for Theorem 12 shows that our lower bound in terms of SD (and thus the lack of an upper bound in terms of VCD, of. Remark 13) persists despite this strengthening of the model.
Theorem 20 Fix (d:) 1 and over a finite domain X. Then S (ut) (C) Z [S2(
However, the dynamic distance function approach helps to overcome obstacles noted Theorem 19 One natural way to define dynamically changing functions d' is to make them dependent on the version space. Defining de (ar, x')= := IC E C² C(x) & C(I')H/IC" for any C' C C, and recalling that C, refers to the version space obtained from C after 1. queries, we get (see appendix for proof):
Theorem 21 S (dc, (CNDNE) < = SD(CDDNE) where C. = (CNDN)) for any t.
min
5 Discussion and Conclusions
We proposed and analyzed a generic framework for active learning with contrastive examples. In studying the sample complexity in two of its instantiations (the minimum distance and the proximity model), we observed interesting connections to other models of query learning, and most notably to self-directed learning, which also led to a new result on self-directed learning of decision lists (Theorem 17). Our definition allows modelling contrastive learning with multitude of contrast set rules, and it can casily be extended to encompass passive learners receiving contrastive examples.

---

Our framework allows the learner to reason with perfect knowledge about the choice of the contrast set. While this unrealistic some practical situations, has applications in formal methods, where the contrast oracle is computer program that could be simulated by the learner in order to refute hypothesis concept C' can be excluded if the oracle does not provide the same counterexamples when C' is the target). Moreover, the learner's s knowledge of the mapping CS implicitly connects our framework to ceeffsupervised learning. Consider, for example, passive learning under the minimum distance model. Here the learner is passively sampling examples (I, y). which are supplemented
with contrastive examples from CS Following our model, the learner knows that the contrastive example x' to x is the closest one to x that has a label different from y. In practice, this can be implemented
self-supervised mechanism in which the learner internally labels with y all data points that are strictly closer to x than x'.
In future work, the condition that the learner has perfect knowledge of the set CS can be softened so as to encompass more learning settings. To this end, note that contrastive examples can still be very helpful in case of mismatch between the learner's assumption on the oracle and the actual strategy of the oracle. Consider for instance the case of learning halfspaces: (a) First assume the oracle is the perfect minimum distance oracle, with respect to the &g metric. A learner with perfect knowledge of the oracle will succeed after just a single query T1. it conjectures the halfspace perpendicular to the vector 2 21 the point 2 and consistent with the observed labels for 2 and z'. This is because the decision boundary of the target concept is perpendicular to the vector 21 21 at the point x1- Note that this holds even if the learner picks the first query Ø1 at random. (b) Now, suppose the same learner still expects the minimum-distann from the true minimum-distanee counterexample may be up to y. In this case, is not hard to show that the classification error of the halfspace perpendicular to x 2 at ai is at most
oracle, but the oracle returns a point x" whose distance
COS
Here r refers to the distance from 2 to the target hyperplane. Thus, even when the initial point æ is chosen at random, the expected classification error remains linear in 7, with just single contrastive example.
There are also scenarios where receiving an instance with the exact minimum distance is not neces- sarily optimal. For example, when learning halfspace in the presence of label noise, the perfect minimum-distance oracle would provide the learner with outliers that may be far away from the decision boundary. Here softer variant of the minimum-distance model may be preferable. One such alternative is an oracle that returns the closest instance x' to the queried instance z, such that the majority of the & nearest neighbors of x' (for some parameter k) have different label than æ.
Acknowledgments and Disclosure of Funding
The authors would like to thank Valentio Iverson and Mohamadsadegh Khosravani for insightful discussions. Moreover, thanks are due to the anonymous reviewers for their helpful feedback on an earlier version of this paper.
Y. Chen acknowledges the support of the National Science Foundation under Grant no. IIS 2313131. Zilles was supported through a Canada CIFAR Al Chair at the Alberta Machine Intelligence Institute (Amíi), through a Natural Sciences and Engineering Research Council (NSERC) Canada Research Chair, through the New Frontiers in Research Fund (NFRF) under grant no. NFRFE-2003-00100 and through the NSERC Discovery Grants program under grant no. RGPIN-2017-05336.
References
[1] Hasan Abasi, Nader H. Bshouty, and Hanna Mazzawi. On exact learning monotone dnf from membership queries. In Proceedings of the 25th International Conference on Algorithmic Learning Theory (ALT), pages 11-124, 2014.
[2] Alessandro Abate, Cristina David, Pascal Kesseli, Daniel Kroening, and Elizabeth polgreen. Counterexample guided inductive synthesis modulo theories. In Proceedinsg of the 30th International Conference Computer Aided Verification (CAV), pages 270-288, 2018
10

---

[3] Noga Alon, Dmitrii Avdiukhin, Dor Elboim, OIT Fischer, and Grigory Yaroslavtsev. Optimal sample complexity of contrastive learning. ArXiv, abs/2312.00377/ 2023.
[4] Dana Angluin. Queries and concept learning. Mach. Learn., 2(4):319-342, 1988.
[5] Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Dipendra Misra. Investigating the role of negatives in contrastive representation learning. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), pages 7187-7209, 2022.
[6] Shai Ben-David, Nadav Eiron, and Eyal Kushilevitz. On self-directed learning. In Proceedings of the 8th Annual Conference on Computational Learning Theory (COLT), pages 136-143, 1995.
[7] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In Proceedings of the 37th International Conference on Machine Learning, (ICML), pages 1597-1607, 2020.
[8] Sanjoy Dasgupta, Akansha Dey, Nicholas Roberts, and Sivan Sabato. Learning from discrim- inative feature feedback. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), pages 3959-3967, 2018.
[9] Sanjoy Dasgupta and Sivan Sabato. Robust learning from discriminative feature feedback. In Proceedings of the 23rd International Conference Artificial Intelligence and Statistics (AISTATS), pages 973-982, 2020.
[10] Pramith Devulapalli and Steve Hanneke. The dimension of self-directed learning. In Proceedings of the International Conference on Algorithmic Learning Theory, (ALT), 2024.
[11] Thorsten Doliwa, Gaojian Fan, Hans Ulrich Simon, and Sandra Zilles. Recursive teaching dimension, VC-dimension and sample compression. J. Mach. Learn. Res., 15(1)331073111, 2014.
[12] Sally Floyd. Space- boundd learning and the vapnik-chervonenkis dimension. In Ronald L. Rivest, David Haussler, and Manfred K. Warmuth, editors, Proceedings of the 2nd Annual Workshop on Computational Learning Theory (COLT), pages 349-364, 1989.
[13] Sally A. Goldman and Robert H. Sloan. The power of self-directed learning. Mach. Learn., 14(1):271-294, 1994.
[14] Steve Hanneke. Theoretical Foundations of Active Learning. PhD thesis, Carnegie Mellon University, 2009.
[15] Jeff HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self- supervised deep learning with spectral contrastive loss. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), pages 5000-5011, 1, 2021.
[16] Tobias Huber, Maximilian Demmler, Silvan Mertes, Matthew L. Olson, and Elisabeth André. Ganterfactual-rl: Understanding reinforcement learning agents' strategies through visual coun- terfactual explanations. In Noa Agmon, Bo An, Alessandro Ricci, and William Ycoh, editors, Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 1097-1106, 2023.
[17] Hayato Kobayashi and Ayumi Shinohara. Complexity of teaching by a restricted number of examples. In Proceedings of the 22nd Conference on Learning Theory (COLT), 2009.
[18] Christian Kuhlmann. On teaching and learning intersection-closed concept classes. In Proceed- ings of the 4th European Conference Computational Learning Theory, EurCCOLT '99 page 168-188 182, Berlin, Heidelberg, 1999. Springer- Verlag.
[19] Weixin Liang, James Zou, and Zhou Yu. ALICE: active learning with contrastive natural language explanations. Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 4390-4391, 2020.

---

[20] Shuang Ma. Zhaoyang Zeng, Daniel McDuff, and Yale Song. Active contrastive learning of audio-visual video representations. In Proceedings of the 9th International Conference on Learning Representations (ICLR), 2021.
[21] Oisin Mac Aodha, Shihan Su, Yuxin Chen, Pietro Perona, and Yisong Yue. Teaching categories to human learners with visual explanations. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages
2018
[22] Matthew L. Olson, Roli Khanna, Lawrence Neal, Fuxin Li, and Weng- Keen Wong. Counter- factual state explanations for reinforcement learning agents via generative deep learning. Artif. Intell., 295: 103455, 2021.
[23] Stefanos Poulis and Sanjoy Dasgupta. Learning with feature feedback: from theory to practice. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS). pages 1104 1113, 2017.
[24] Yuta Saito and Thorsten Joachims. Counterfactual learning and evaluation for recommender systems: Foundations, implementations, and recent advances. In Proceedings of the 15th ACM Conference on Recommender Systems (RecSys), pages 828-830, 2021.
[25] Burr Settles. Active Learning. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers, 2012.
[26] Chaoqi Wang, Adish Singla, and Yuxin Chen. Teaching active learner with contrastive examples. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurlPS), pages 17968-17980, 2021.
12

---

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

---

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

---

Answer:
[NA]
Justification:
This is purely theoretical paper, without experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
caiiiooooolccy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ccpppp.ccppulli//uuuiu wwwiii/gguie///eeeeeeoeic CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This is purely theoretical paper, without experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This is purely theoretical paper, without experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
15

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
This is purely theoretical paper, without experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http://wwrp...cooooo..//ccccaaaa
Answer: [Yes]
Justification: This is purely theoretical paper, without any anticipated harm or socictal impact of any kind.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations in their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
We do not anticipate any broader societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: Our research does not involve data or predictive/generative models, and does not pose any risks of the mentioned kind.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the Datasets.paaersstt
package should be provided. For popular datasets, paperswi thcode. cow/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
18

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: LLMs were not used any non-standard, important, original component of this research.
Guidelines:
The answer NA means that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
19

---

A Appendix
This appendix provides the proofs omitted from the main paper.
Proposition 2 Let C be a countable concept class over countable X. Let T C - 2 be any injective function that maps every concept in C to finite set of instances. Then:
1. There is some CS with Scs(C) S supcee +T
2. If (C) & T(C') for C + C', then there is some CS such that (cs(C) S supcec [T(C))
In particular, if is finite, then there is some CS such that Scs(C) S 1+min Ex= ( 2 (C]) If X is countably infinite, then there some CS such that (C) =
Proof. Let T: - X' be such that T(C) * T(C") whenever C' + C². Let œ1, 22,... be a fixed repetition-five free enumeration of all the elements in X.
To prove statement I, define CS by CS(2; C) = {my} } for j' min | i, 23 E T(C)). Now an active learner operates as follows. Initially, it sets = 1 and starts with iteration 1. In iteration i, it asks query for Zn,- If receives z = Zy as a contrastive example, then note that j 2 n2. The learner will then set 71+1 = j + and proceed to iteration i + 1.
Upon its ith query, the learner will find out the label for Ii, (which is irrelevant) and the ith element of T(C) in the enumeration æ1, 42,42, After [T(C)] queries, the learner has seen all elements from T(C). and will receive a dummy response for its next query. From its responses, it has now inferred that its target is a concept that is mapped to T(C') by mapping T' By injectivity of T', this means that the learner has uniquely identified C. This proves statement Since an injective mapping T using all subsets of X' of size at most k= can encode E (!?") concepts, such T would yield (Cs + min(k (k| Et (12)) [C]]-
For statement 2, note that, if T(C) @ T(C") for distinct C, C' E C, then the learner can infer C correctly after having seen all elements in T(C). With this result, for countably infinite X, any
mapping T identifying each concept with different instance in X, results in (Cs(C) = 1. U
Remark 5 Let C be concept class over a complete space X with metric d. Then Sesa ScSt (C) S (C).
(C) S
min
Proof. The second inequality holds by definition. For the first inequality, consider any r > 0 and (x,C) x C. Due to Remark 3 CSd (2, C*) = 0 iff there is no x' with C(z') # C(z). Moreover, C (z, r, C)= = / iff there are no points with different label converging to a point distance at most from Therefore, either CSd prox r, C* = 0, or CS (ar, r, C) 2 CS min (I. C) * 0. In the former case, the contrastive oracle the minimum distance model also conveys that there are no points with different label converging to a point at distance at most r from x. Consequently, the contrastive oracle in the proximity model does not provide extra information. In the later case, any contrastive example given by the contrastive oracle in the minimum distance model can be also given by the contrastive oracle in the proximity model. Again, the contrastive oracle in the proximity model does not provide extra information.
Example 3 Let X {0, 13"h. Let Cimonn consist of all monotone monomials, i.e., logical formulas and some k E {O....,,, m). The concept
of the form Us, A...Aus, Us, for some pairwise distinct ii,..., i associated with such formula contains the boolean vector (bi,... -.m) ) iff bi, ... big 1 (where the emply monomial is the constant 1 function). Let d be the Hamming distance. Then:
(1) [MQ (Cmmon) = m. m. (2) Scs am (Cmmon 1. (3) Sose (Cmmon) O(log m).
Proof. It remains to prove the lower bound from Claim (3).
Let (x.r) r) be the first query point of the learner. Let w be the Hamming weight of x. The logarithmic lower bound is now obtained by an adversary argument.
If w > m/3, then the oracle returns (x, 1) and (x', 0) where x' is obtained from x by flipping one of the 1-entries in to O. Note that, f1,-.. Jw-1 denote the positions of the 1-entries in x', then the index set associated with the variables in O* could be any subset of 1Ji....,w--1
20

---

r 2 m/3 and w S m/3, then we may assume without loss of generality that I m w. The oracle returns (x, 0) and (x', 1) where x' obtained by adding r ones x, Note that, if j1 Ji.....J denote the positions of the additional ones, then the index set associated with the variables in C* could be any subset of (ir).
r < m/3 and w I m/3. then the oracle returns (x, 0) and w. Let J with |J|= = w be the set of indices j such that zj 1. Fix set K S [m]] such that [K] = r + and K KnJ 0. Let [mm \ KJ be the set of the remaining indices in [m]] Let us make the commitment that the variables I& with & E K are contained in C*. Even if the learner knew about this commitment, would still have to determine the Thee--ine I-indices of the remaining variables in C*. These indices could form an arbitrary subset of I.
In any case the learner can reduce the search space for the index set of C not more than by factor of 3. Hence the learner requires Ollog m) queries for the exact identification of C
m
Example 4 Let X" {0, 1] mm+1, The concept class mmonn X' is defined to contain, for each C E mmoo the concept C' E C.mmon constructed via C"(b,....,bm 0) = C(bi,..... bm)) and C'(b,,....bb
C(b)...... ...).. No other concepts contained in C Let d be the Hamming distance. Then [[MQ](Cmmon)) Sast min
(Cmmonn SCs prox (Cumou) m.
Proof. A membership query learner using m queries will work as described in the proof of Example yet will leave the (m + 1)st component of every queried vector equal to O. Thus, the learner will identify which vectors of the form .b, bm, 0) belong to the target concept. The latter immediately implies which vectors of the form (bI, bm, 1) belong to the target concept. Again, by a standard
information-theorent argument, fewer membership queries will not suffice the worst case. Thus S S[MQ] (Cumoon) m..
Upon asking any query (61..... .m bm+1). learner in the minimum distance model will receive the correct answer, plus the contrastive example (b1...., 6m 1 - bm+1). This contrastive example does not provide any additional information the learner. Hence, the learner has ask as many queries m.
as an MQQleerner i.e., Scsd min (Cummon)
Finally, according to Remark 5, Scad
< Scay press
< S[MQ]. Thus, Scss prox (Cimonn = m.
Remark 22 Example 4 can be generalized: each concept class C over domain X' {0, 1 can be (redundantly) extended concept class C' over X' [0,1]=+1 that renders contrastive examples in the minimum distance model useless for learning concepts in C', under the Hamming distance.
Theorem
Scidd min
(Cm...
U Cm claus
= 2, where d is the Hamming distance.
To prove this result, we begin with straightforward extension of Example
Lemma 23 Sosi miin (Cmoa) where d is the Hamming distance.
Proof. The proof is analogous to that of Example 3. just here the learner asks two queries, one for and one for 1. The two contrastive examples then determine the target monomial, by similar reasoning as for Example
By duality? Lemma 23 implies the following result:
Corollary 24 Scsa min (Crtaus) 2, where d is the Hamming distance.
We can now proceed with the proof of Theorem 7
Proof. (of Theorem 7 Let LA be the learner of C.. as it is described in the proof of Lemma 23 Let Ly be the learner of Cataus which is obtained from L,, by dualization. It suffices to describe learner L who maintains simulations of L,, and Ly and either comes in both simulations to the same
'The mapping f(v) f(v) transtorms the monomial Agr B.AAyg 0j into the clause Vser V yeu Vj. and vice versa. The same mapping can be used to dualize the proof of Lemma 23 the sense that, within this proof, every classification label is negated and every point from B... is componentwise negated. This concerns the query points chosen by the learner well as the contrastive examples returned by the oracle.
21

---

conclusion about the target concep or realizes an inconsistency in one of the simulations, which can then be aborted. Details follow.
If the target concept is representable as literal, then I. will not run into problems because both simulations lead to the same (correct) result. From now we assume that the target concept cannot be represented by literal. Remember that both learners, L, and Tny, choose the two query points 1 and O. Let us first consider the case that the target function is the I I-constant (= empty monomial). Then the oracle returns the label 1 for both query points along with an error message that there is point of opposite label in Bm After having received this error message, L can abort both simulations because it has identified the 1-constant the target function. The reasoning for the constant-O function is analogous.
Let us now consider the case that the target function can be represented by monomial M of length at least 2 resp. by a corresponding decision list. If M contains at least one negated and at least one not negated variable, then the oracle returns label 0 for both query points plus extra-point of opposite label. If the target function were a clause, then the case of label 0 for both query points can happen only if the target function would be the O-constant (so that no extra-point of opposite label could be returned by the oracle). Hence L may abort the simulation of Ly and identify the target function via LA- Let us now assume that M does not contain negated variables so that M is of the form Æye M/ for some J S [m]] with |J| 2 2. Then, upon query point O, the oracle returns label plus the extra-point 1, The learner Ty concludes from seeing label 0 that the target clause does not contain negated variable. But by would expect to see extra-point with only a single 1-component (because clause with only unnegated variables can be satisfied by single 1-bit in the right position). Hence L can abort the simulation of Lv and continue with the simulation of LA until M is identified.
All cases that we did not discuss are dual to cases that we actually have discussed. Thus the proof of the corollary is accomplished.
Theorem 10 S[EX*, EX", ,MQ((C) - S S Sas40 min
(C) S STEX*, EX-, MQ](C).
Proof. As for the second inequality, it suffices show that each call of one of the oracles EX EX" MQ can be simulated by a single call of the contrast oracle. This is clearly true for call of the MQ-oracle (because the contrast oracle is even more informative). A call of -oracle can be simulated as follows:
1. Choose an (arbitrary) instance x E X as input of the contrast oracle and get back pair (b, x') such that b = (x) 4 (x²)).
2. b 1, then return x (as the desired positive example). Otherwise return x'.
A similar reasoning shows that call of the
can be simulated by call of the contrast
oracle. Hence the second inequality is valid.
As for the first inequality, it suffices to show that g queries of the contrast oracle can be simulated by q calls of the membership oracle and two extra-calls which are addressed to the oracles providing (positive
negative) example. For i = 1,..., 94 let v; be the i-th query instance that is given as input to the contrast oracle and let (b,, 2 with b, = C* (x:) # (x²) be the pair returned by the latter. Note that xi can be any instance with label opposite to b, because the discrete metric assigns the same distance value, 1, to any such pair (x.,²). The above queries can therefore be simulated as follows:
1. Call the oracle EX" and obtaín an instance yo such that C* (310 = O.
2. Call the oracle E and obtain an instance y1 such that (1)) 1.
3. For i = 1, ....,, q. choose x; as input of the MQ-oracle and get back the label b, = C* (a;)). If 6; 0, then return (0, y)) ) as a valid answer of the contrast oracle when the latter is called with query instance xz. If by = 1, then return (1, yo) instead.
This completes the proof.
Example 7 Let X = (#), T2, 12). Let C consist of the concepts {II, T3 (xa), (I2, 13). and (12)-
Then C satisfies SD(C) = VCD(C) 1, but S Sest... (C) > 2 for any d : X x X 20
"This happens when the target concept is literal, ie., both monomial of length 1 and a clause of length 1.
22

---

Table 2: A concept class C with SD(C) VCD(C) 1, but Scsa (C) 2 2 for any metric d.
min
22
3:3
C
0
C2
0
0
C3
0
1
C4
Proof. The concept class is shown in tabular form in Table 2
Let be any distance function and let (2), be any permutation of 1,2.3. Let ((()),(2)) be the event that (L chooses query point 24(1) and d(ane)) S ((())))F((())))
(L chooses
query point T2(2)) and ((z) Fa(2)) d(za(z)) Zi(2))) )). Note that at least one of the events ( E(1,3) and (2233) must occur. It suffices therefore to show that, in any case, the oracle has a response resulting in version space of size 2. This can be achieved as follows:
In case of ((1.)), the response ((11 0), (22,, 1)} would lead to the version space (Cs, C4} In case of E1,,3, the response {(z1, 0), (23, 1)3 would lead to the version space {C2, C3
In case of (2,,3 the response [z2,, 0), (Zz. 1)) would lead to the version space [C1, C2).
Theorem 14 For any finite C with VCD(C) there exists metric d with Sest min (C) < 2.
To prove this theorem, we observe the following useful fact, which was noted by
Lemma 25 (III) Let C be any concept class with VCD(C) 1.
Then there is at least one (Ir,b) b)
X' x 1) such that there exists exactly one C E C with C(x) =
Proof. (of Theorem I4]. It is well-known that every finite concept class of VCD is contained in concept class of size X + 1 whose VCD is still I, see, e.g., [12]. Thus, may assume that = =|X| + 1. Sct n = X By an iterative application of Lemma 25 we see that there exists an order C1. ........... Cn, C.+1 of the concepts in C, order ø1, .i,...,.. Fn of the instances in X' and binary sequence by...., by such that, for i = 1...., n. C C2 is the only concept in C (C1, Ci-1) which satisfies the equation C(x,) = b; Let i (1)
< (r( and i (1) < ... < (s) with r + be given by b)-() = 1 for j = 1,..., and 6--0) ( = 0 for = 1,..., 8. In the sequel, we assume that r, 2 [ The following implications are easy to verify.
(II) Cx,)
by for all j E [n)]. then Cn-1-
(I2) If ((z+t) 0 for all [r]. and j is the smallest j E [s] with C(x:- ()) 0, then
C= C-
(I3) If ((+--() = for all E [s]. and j+ is the smallest j E [r] with C(*+()) 1, then C C
(14) If (i) j is the smallest j E [s] such that C(z; (1) = 0, (ii) jt is the smallest j E [r] such that ((z+t()) = 1, and (iii) it (++) > i (-]) then C = C:-(-)-
(15) If (ij is the smallest j [s] such that C(2, ()) 0, (i) jt is the smallest j e [r] such that and (iii) i (j-) + (j+), then C C++++)-
C(*+t))
thus suffices to choose a metric such that the oracle can be forced (with 2 minimum-distaaee queries) to make one of the above five implications applicable. To this end, define
l - jl if by by d(z Iz) = n if b * by
'The learner can take no advantage from knowing which of æ1, 02 the role of query point and which in the role of contrastive example.
'The proof will become simpler if equals O.
23

---

The two query points, chosen by the learner, are (i+(1) and 2i-(1)- (1).
Suppose first that the oracle returns the label 1 for (1) If if (1) = 1, then C = C1 and we are done. We may therefore assume that (1) > 1, which implies that (1) 1. If the oracle returns the label 0 for xi- (1) Ti, then C C1 and are done. We may therefore assume that the oracle returns the label for ø1- If there is contrastive example for (x1, 1), then (13) applies. Otherwise, let (zz. 0) be the contrastive example for (I1, 1). If j < it (1), then (14) applies. If j > xt (1), then either (I3) (in case d(x1,,,)) my) = ni or (I5) (in case d( 2z) < T) applies.
Due to symmetry, one can reason analogously the oracle returns the label 0 for D2 (1)
Finally, consider the case that the oracle returns the label 0 for (1) and the label 1 for (1)- It follows that the contrastive example for 11+(1) must be labeled and the contrastive example for =1-(1) (1) must be labeled O. The following implications are easy to verify:
1. If the contrastive example for 11+(1) is an instance H; with b, 0 and the contrastive example for =2-(1) (1) is an instance zy with by = 1, then (II) applies.
2. If the contrastive example for (1+(1) is an instance x; with b, = 0 and the contrastive example for (1)(1) is instance of the form -4-(1->, then (12) applies.
3. If the contrastive example for fz-(1) is an instance xi with b, = 1 and the contrastive example for (1) is an instance of the form Ts+(+)) then (I3) applies.
4. If (i) the contrastive example for (1)(1) is an instance of the form Tittt) (ii) the contrastive
example for o (1) is an instance of the form T; (j ). and (iii) it it()t) > i (j-). then (I4)
applies.
5. If (i) the contrastive example for a (1) is an instance of the form 24+ ()) (ii) the contrastive example for (1)(1) is an instance of the form (3-(--> and (iii) i (ーj=) > it (j+) ). then (I5) applies.
Hence each possible response of the oracle leads to the exact identification of the target concept.
Lemma Suppose that is a concept class over Bm, and C' is a subclass of with the properties (PI) For each a E Bm with Um = Vm and each C E C², we have that C(a) 1.
(P2) For each a with am = V'm and am-1 = ym-1 and each C E C', we have that C(a) = O. For i {m, m 13, here y: E 10, 1} is fixed, y
Yt, and C" is the set of all concepts of shape
(a1...... (11....,m-22) am-2) + C(ai,..., Om 2, Mn- for C C'. Then Sest (C) 2 Sesd (C") Z S(MQ)(C"), where dl is the Hamming distance.
Proof. Suppose that L learns C' from a contrast oracle in the minimum distance model at the expense of q queries. It suffices to show that L can be transformed into L' which learns C" from membership oracle at the expense of at most q queries. To this end, let C" be the target concept in C" and let C' with C" identified C' in C' as long as the subfunction C" is not uniquely identified in C". L' can therefore uniquely identify C" C" by maintaining a simulation of until L has uniquely identified C" in In order to explain how L' simulates the contrast oracle, we proceed by case distinction:
ymmm = (a) be the corresponding concept in C', Note that I. has not uniquely
If chooses a query point of the form a1/mn11'm then L' chooses the query point a and receives the label b = C" (a) from its membership oracle. Then L' returns b and the point a' to L where a' = a1'm-13m if b = and a' = a1mm-11/m if b = 1. Note that (b, a') is among the admissible answers of the contrast oracle.
If L chooses a query point of the form aym--1V'.. then L' returns the label 0 and the additional point a8mm-18m. Again, this is among the admissible answers of the contrast oracle.
If I. chooses a query point of the form ayjm 18mm then T/' returns the label and the additional point atjm-19'm Again, this is among the admissible answers of the contrast. oracle.
If chooses a query-point of the form au/m-19m 1mm then T,' chooses the query point a and receives the label b = (a) from its membership oracle. Then L' returns the label 1 and
24

---

the point a' to L where a' = ay -0/mm13'mmm if = 0 and a' = a0m--1Vm if = 1. Again, this is among the admissible answers of the contrast oracle. Here note that, in case b 1, there is no admissible answer at distance from the query point, so that contrastive example at distance 2 can chosen.
Clearly I." can maintain this simulation until it reaches exact identification of the target concept. Moreover, the number of query point chosen by T,' does not exceed the number of query points chosen by L.
Corollary 16 Soss min
(DLm) 2 2 1, where d is the Hamming distance.
Proof. Let C DL Moreover, let C" _ C be subset of DL of decision lists of the form
L = [[ums 1), (Um-1, 0), (li,bi),. (L2, b,), ba+1
E DL
-C'EDI
where : 2 0, & E {vi, 01 Um Um 2 }} and b, E 10, satisfies properties (P1) and (P2)
with mm = ym = 1 in Lemma 15
Then C" = DL m -2. m is a subclass of DL and
2m-2 2 -1 membership queries are needed for learning Con 17.
Theorem 17 There exists a self-directed learner for DL. that makes, on any target list C DL at most 4km mistakes where k is the number of blocks in C
Proof. Recall Bn = {0, 1 For any set of literals e......, li,. we use Bm (fi, = bi,...,,u, bi = -b;) to denote the (m - j) -dimensional subcube resulting from fixing the value of E,, to b, for t E [i]. We call literal é 6- 6-pure if the target list C* assigns label to every point in Bm (e =1.
The b-pureness of
v2 (resp. of é ū;)) can be checked by testing whether C' restricted to Bm. = 1) (resp. to Bm = 0)) degenerates to the constant-b function. This is done at the expense of at most mistakes per literal: The learner predicts 0 for a first point in B,, receives the correct label b (which may may not count as one mistake), and then predicts b for further points
1).
B,n (E = 1) until a mistake is made. If no mistake made on further points in = 1), then l is b-pure; otherwise it is not pure. Hence, after having made at most 4m mistakes, the learner I. knows all lute-literals, say t,,...,e,, and I, also knows the (unique) bit {0, 1} with respect to which E . l are pure.
At this point knows the first block (L1, b). .. (le, of the list C*, L can now proceed iteratively in order to learn the remaining blocks. As for the second block, all query points are taken from the (m - f) dimeensional subcube (m, first block. In this way, C* is identified blockwise at the expense of at most 4m queries per block. D
.................... l
b) so that they are not absorbed by the
Theorem 21 S lff,, ) (CNINE) S = SD(CTIONE) where C. = (CHDDE)), for any L.
The proof of this theorem makes use of the following terminology. Suppose (aI..... am am). b= (bi...., bm) E 8" for some m. We write < b if = 1 implies b, = 1. Moreover, we implicitly identify the Boolean vector with the corresponding monotone monomial.
First we introduce helpful lemma.
Lemma 26 Let a, b, E {0,1) such that a < S c. Then for any C' C mm.... de b) < (e,(a,)) (a.
we have
Proof. Consider any C E CHINN Since C' is monotone, if C(a) = 1 then we have C(b) = 1. C(C() 1. Similarly,
C(a) Similarly, if
and C'(b) then C((c) as well. This completes the proof.
The claim SD(CMDAE Theorem 19. It suffices to define a learner that witnesses S $C.. (CMDDT))
Proof. (of Theorem 27
was proven by 13] and already stated in
S s.
Define learner that asks, in each of s iterations, a query for the vector Since has label 0, all the contrastive examples have label 1. Let b' be the contrastive example for the fth query.
25

---

First, we argue that b' is a monomial in the target concept C*. Suppose b is not a monomial. Since it has label there is a monomial b' b'. Using Lemma 26 we have de, (0, b') Σ cm,
de, (0, b²). Moreover, since b² o b', there exists C E MDNF such that C(bb) 0. but C(b²) = 1. Thus, de, (0, b') < de, (0, b*). Therefore b' should have been the contrastive example, which is contradiction.
Next, we prove inductively that {b',... b*} is the set of monomials in C Let {b) b' ! be t distinct monomials in C We prove that b' is monomial in C* distinct from b b',...,b b
b ..., bb-1, We also know that all concepts give label O to the all zero vector. Thus, according to Lemma 26 for any with b9 < a for some q & [t - 1], we have de, (0, a) 2 de, (9) (maximum distance). Thus, b g b'. With an argument similar to we used for the base case, be is also monomial. This completes the proof.
Note that Ct-1 the set of concepts that have label on
26


Reviews:
[{"review_id": "QA6fUBuctK", "reviewer": "Reviewer_9itQ", "summary": "This paper proposes a general framework for active learning in which a membership query returns not only a label but also a counter-example chosen according to a rule known to the learner. The authors analyze two specific rules - a strict minimum-distance rule (the closest counter-example to the query with a different label) and a looser proximity rule (any counter-example within a certain neighborhood). They show that for simple concept classes such as one-dimensional thresholds and axis-aligned rectangles the extra feedback dramatically reduces the number of queries to a constant. Finally, they link the framework to self-directed learning, allowing them to import existing lower-bound techniques and to derive a new mistake bound for decision lists.", "questions": "How does the sample complexity change if the learner's assumed metric differs slightly from the oracle's, or if the oracle occasionally returns a non-minimal counter-example? A brief discussion would help gauge practical relevance.", "limitations": "Yes.", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "The paper's main merit is a new framework that can unify several earlier \"teacher\" settings - greedy, randomized, and adversarial - giving one vocabulary what used to be separate analyses. Coupled with complete proofs, the structural unification could facilitate future research in this area. \n\nThe work leans on a strong perfect-knowledge assumption - the learner must know the oracle's exact rule and metric - yet offers almost no guidance on robustness to noise or mis-specification. All evidence remains theoretical; without even a toy simulation it is unclear whether the constant-query gains would survive in practice. Moreover, the most striking positive results (thresholds and rectangles) are arguably obvious, leaving doubts about practical impact.", "was_revised": true, "final_justification": "The rebuttal cleared up my concerns about the idealized setting and made the scope feel reasonable for a first theoretical step. I will maintain my Borderline Accept (4) rating.", "rebuttal": "# General Response to All Reviewers\nThank you for your effort in assessing our work, and for your helpful comments and questions. In this section, we address a common concern raised by multiple reviewers: that our setting is overly idealistic, as it assumes a realizable setup (i.e., the target concept lies within the concept class) and that the learner has perfect knowledge of the oracle.\n\nWhile we agree that extending the framework to agnostic settings and scenarios involving noise or imperfect alignment between learner and oracle is an important direction for future work, we argue that the current setup still offers meaningful contributions to the literature:\n- The primary aim of this paper is to initiate a theoretical study of learning with contrastive examples. As a first step, it is natural and appropriate to begin by exploring the boundaries of idealized, tractable setups.\n- We establish that, for any distance metric, the complexity of the minimum distance model is lower bounded by the complexity of self-directed learning (a topic that has recently re-gained attention in the learning theory community). To the best of our knowledge, there are few known concept classes where self-directed learning outperforms active learning in terms of sample complexity, with the notable exception of the result by Diakonikolas et al. (2023) for halfspaces over the uniform distribution. Thus, any upper bounds from our idealized setup carry over directly to self-directed learning.\n- As we highlighted in the paper, one of the most prominent applications of our model is counterexample-guided program synthesis, where it is in many cases guaranteed that the learner has perfect knowledge of the oracle and the target concept lies in the concept class.\n\n# Individual Response\nAlthough the sample complexity can change, contrastive examples are still very helpful in case of a  mismatch between the learner and the oracle choosing the contrastive example. Let us illustrate this with the class of halfspaces. \n\n(a) Even if the learner picks $ x_1$ at random, a single contrastive example returned by the minimum-distance oracle (with respect to the $\\ell_2$ metric) is sufficient to identify the target concept. This is because the decision boundary of the target concept is perpendicular to the vector $ x'_1 - x_1 $ at the point $ x'_1 $.\n\n(b) Now, suppose the oracle returns a point $ x''_1 $ that is at most $ \\gamma $ away from the true minimum-distance counterexample. In this case, it is not hard to show that if the distance from $ x_1 $ to the target hyperplane is $ r $, then the classification error of the halfspace perpendicular to $ x''_1 - x_1 $ at $ x''_1 $ is at most\n$$\n\\frac{\\cos^{-1} \\left( \\frac{r}{r + \\gamma} \\right)}{\\pi}.\n$$\nThus, we can conclude that even when the initial point $ x_1 $ is chosen at random, the expected classification error remains linear in $ \\gamma $, even with just a single contrastive example.\n\nThere are also scenarios where receiving an instance with the exact minimum distance is not necessarily optimal. For example, when learning a halfspace in the presence of label noise, the perfect minimum-distance oracle would provide the learner with outliers that may be far away from the decision boundary. Here a softer variant of the minimum-distance model may be preferable. One such alternative is an oracle that returns the closest instance for which the majority of its k nearest neighbors have the opposite label. \n\nWhile a detailed analysis of a mismatch between the learner’s and the oracle’s definition of the set CS is beyond the scope of our paper, we will gladly add some discussion to this end in the camera-ready version.\n\n\nReferences:\n\nDiakonikolas, Ilias, et al. \"Self-directed linear classification.\" The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023."}, {"review_id": "DI7tSZIKM9", "reviewer": "Reviewer_C2ZM", "summary": "This paper introduces a formal framework for learning from contrastive examples, focusing on scenarios where the learner has prior knowledge about the oracle's strategy for selecting such examples. The first contribution is the development of a general and flexible framework that captures a variety of contrastive example generation methods, extending beyond traditional counterfactual settings. The second contribution is providing various sample complexities within this framework. The authors derive both upper and lower bounds for learning different concept classes, including geometric objects, 1-decision lists, and monotone DNFs. These results show implications of contrastive feedback on learning efficiency. The third contribution is an interesting connection between the sample complexity of contrastive learning and the mistake bound in self-directed online learning.", "questions": "I think the paper is super clear.", "limitations": "I think the major limitation of this framework is that it allows the learner to reason about the choice of the contrast set with perfect knowledge. I understand why this assumption is made in order to make the proofs work. However, it has to be relaxed for it to be really informative about what happens in practice.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I really like this paper. It makes very neat theoretical contributions (in a field that is mostly empirical). So in my opinion, the paper should be accepted.", "was_revised": false, "final_justification": "", "rebuttal": "# General Response to All Reviewers\nThank you for your effort in assessing our work, and for your helpful comments and questions. In this section, we address a common concern raised by multiple reviewers: that our setting is overly idealistic, as it assumes a realizable setup (i.e., the target concept lies within the concept class) and that the learner has perfect knowledge of the oracle.\n\nWhile we agree that extending the framework to agnostic settings and scenarios involving noise or imperfect alignment between learner and oracle is an important direction for future work, we argue that the current setup still offers meaningful contributions to the literature:\n- The primary aim of this paper is to initiate a theoretical study of learning with contrastive examples. As a first step, it is natural and appropriate to begin by exploring the boundaries of idealized, tractable setups.\n- We establish that, for any distance metric, the complexity of the minimum distance model is lower bounded by the complexity of self-directed learning (a topic that has recently re-gained attention in the learning theory community). To the best of our knowledge, there are few known concept classes where self-directed learning outperforms active learning in terms of sample complexity, with the notable exception of the result by Diakonikolas et al. (2023) for halfspaces over the uniform distribution. Thus, any upper bounds from our idealized setup carry over directly to self-directed learning.\n- As we highlighted in the paper, one of the most prominent applications of our model is counterexample-guided program synthesis, where it is in many cases guaranteed that the learner has perfect knowledge of the oracle and the target concept lies in the concept class.\n\nIn addition, we would like to point out that our framework naturally extends to setups where the learner has imperfect knowledge of how the oracle selects contrastive examples; see also our response to Reviewer 9itQ.\n\n# Individual Response\nWe have tried to address the limitations you raised in our general response to all reviewers.\n\n\nReferences:\n\nDiakonikolas, Ilias, et al. \"Self-directed linear classification.\" The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023."}, {"review_id": "l4zCWsx6lj", "reviewer": "Reviewer_MWJZ", "summary": "Formal Models of Active Learning from Contrastive Examples\nThis dense theoretical paper proposes a framework to analyze active learning where a learner, in addition to a label for a query, also receives a \"contrastive example\" which is a similar example with a different label. The authors assume such examples are drawn in a couple of different ways, using distances from the query. They show sample complexity results for different hypothesis classes, relationships to the SQ and self directed learning. In some cases, the additional contrastive examples have a significant impact on sample complexity, in other cases not so much.", "questions": "see Strengths and Weaknesses above", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "This paper is addressing an important and relevant problem. Active learning is an important research area and studying the sample complexity under contrastive examples is an interesting direction. In spite of the density of the paper, it is very well written and explained. Generally I need a linear (in the number of lemmas) number of cups of coffee to read such papers. For this paper, three cups were enough to gain some understanding of 21 theorems. That is a significant improvement!\n\nA few concerns:\n1. Such examples are called counterfactuals (l 19)--I don't understand. Is there an underlying causal model behind these choices? In what sense are they counterfactual?\n2. I was not clear on the value of the contrastive example per se. As in, what if at each round a random example was provided  with the opposite label? How much worse would the sample complexities be? Maybe this was addressed and I missed it.\n3. I believe there is work on learning with counterexamples, how does this compare to such a framework?\n4. L is overused as a symbol. Maybe lists of oracles should be called something else.\n5. What does it mean to say \"access to all oracles\"? The learner gets multiple examples one from each?\n6. What is the significance of x_{i+1} in definition 1? Why is it not enough to say sigma epsilon-approximates C*?\n\nOn the whole, this is an interesting, well written paper studying a novel setting theoretically. These results should be of interest to the community.", "was_revised": false, "final_justification": "", "rebuttal": "# General Response to All Reviewers\nThank you for your effort in assessing our work, and for your helpful comments and questions. In this section, we address a common concern raised by multiple reviewers: that our setting is overly idealistic, as it assumes a realizable setup (i.e., the target concept lies within the concept class) and that the learner has perfect knowledge of the oracle.\n\nWhile we agree that extending the framework to agnostic settings and scenarios involving noise or imperfect alignment between learner and oracle is an important direction for future work, we argue that the current setup still offers meaningful contributions to the literature:\n- The primary aim of this paper is to initiate a theoretical study of learning with contrastive examples. As a first step, it is natural and appropriate to begin by exploring the boundaries of idealized, tractable setups.\n- We establish that, for any distance metric, the complexity of the minimum distance model is lower bounded by the complexity of self-directed learning (a topic that has recently re-gained attention in the learning theory community). To the best of our knowledge, there are few known concept classes where self-directed learning outperforms active learning in terms of sample complexity, with the notable exception of the result by Diakonikolas et al. (2023) for halfspaces over the uniform distribution. Thus, any upper bounds from our idealized setup carry over directly to self-directed learning.\n- As we highlighted in the paper, one of the most prominent applications of our model is counterexample-guided program synthesis, where it is in many cases guaranteed that the learner has perfect knowledge of the oracle and the target concept lies in the concept class.\n\nIn addition, we would like to point out that our framework naturally extends to setups where the learner has imperfect knowledge of how the oracle selects contrastive examples; see also our response to Reviewer 9itQ.\n\n# Individual Response\nWe would like to address your questions below:\n1. The term counterfactual is often used to describe feedback provided in response to a query to an oracle, where the feedback contrasts with the query in some specific aspect. In this sense, there are clear similarities to our notion of a contrastive example, which has an opposite label with the original instance.\n2. One can consider the class of 1-dimensional threshold functions (Example 1 of the paper). The minimum distance model contrastive examples identifies the target concept with 1 example. However, it is not hard to see that with a random contrastive example with opposite labels the sample complexity will remain $\\Theta( \\log(1 / \\varepsilon))$ (the same as the membership query complexity).\n3. Are you referring to Alon et al. (2023)? If so, their setup is closer to representation learning than to ours. In their framework, the learner receives triplets $(x, y, z)$ and learns whether $x$ is closer to $y$ or to $z$. The goal is to correctly predict the outcome for all such triplet comparisons. They also extend this framework to more general $k$-tuple queries. \\\nIf you are referring to counterexamples used in Angluin-style learning with equivalence queries or superset/subset queries: here the queries are not data points but entire concepts (hypotheses), and the counterexamples are used to demonstrate why the hypothesis is incorrect.\n4. We will address this problem in the camera ready version, if this paper gets accepted.\n5. By access to all oracles, we mean that at each step $t$, the learner not only selects a query point $x_t$ but also chooses which oracle to query for a contrastive example. We will clarify this point in the paper.\n6. In line 99, within Definition 1, our intention was to emphasize that the learner selects each $x_{i+1}$​ based on the full interaction history observed up to that point.\n\nReferences: \\\nDiakonikolas, Ilias, et al. \"Self-directed linear classification.\" The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023. \\\nAlon, Noga, et al. \"Optimal sample complexity of contrastive learning.\" arXiv preprint arXiv:2312.00379 (2023)."}, {"review_id": "yvsKcKcMg0", "reviewer": "Reviewer_brPw", "summary": "The authors introduce a formal model for learning from contrastive examples and study contrast sample complexity for several examples. Learning goes according to the following protocol. A learner makes a query $x_i \\in \\mathcal X$. After that, a contrast oracle returns a triplet $[y_i, (x_i', y_i')]$, where $y_i$ and $y_i'$ are the labels of $x_i$ and $x_i'$, respectively and $x_i'$ belongs to the contrast set of the current version space and $x_i$. Then the learner reduces the version space and makes a new query. The authors start with an observation that they have to restrict the power of the contrast oracle (Proposition 2). Otherwise, the learning problem will be too simple. In the present submission, the authors consider two contrast oracles. The first one returns the closest element $x_i'$ with a different label while the second one is allowed to take any contrastive example $x_i'$ within a ball of radius $r$ around $x_i$. The authors derive contrast sample complexity for classes of thresholds (Example 1), axis-aligned rectangles (Example 2), monotone monomials (Example 3), and the union of the class of monomials of Boolean variables and the dual class of clauses (Theorem 7). In Example 4, the authors describe a simple scenario when the contrast oracle may be useless. Finally, they discuss connection between learning from contrastive examples and the classical model of self-directed learning.", "questions": "1. What happens to the contrast sample complexity if the target concept lies outside $\\mathcal C$?\n\n2. Is it possible extend the considered model to scenarios when labels are noisy?\n\n3. Can the authors give an example of a practical task when a contrast oracle knows the contrast class exactly?", "limitations": "Yes.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths.\n\n1. The paper introduces formal models of contrastive learning and provides its theoretical foundations.\n\n2. The authors provide several examples of contrast sample complexity for concept classes often considered in the literature on learning theory: thresholds, axis-aligned rectangles, monotone monomials.\n\n3. The authors discuss connection between learning from contrastive examples and the model of self-directed learning.\n\n\nWeaknesses.\n\n1. The contrast sample complexity in several examples of order $\\mathcal O(1)$. This means that the problem of contrastive learning in these cases is too simple.\n\n2. The setup is too ideal. First, the oracle has an access to exact contrastive set. Second, the labels are noiseless. Third, the target concept $C^*$ belongs to the concept class $\\mathcal C$.", "was_revised": true, "final_justification": "I thank the authors for their clarifications. I still think that the setup is too idealistic. However, in my initial review I underestimated the connection with self-directed learning. For this reason, I raised my score.", "rebuttal": "# General Response to All Reviewers\nThank you for your effort in assessing our work, and for your helpful comments and questions. In this section, we address a common concern raised by multiple reviewers: that our setting is overly idealistic, as it assumes a realizable setup (i.e., the target concept lies within the concept class) and that the learner has perfect knowledge of the oracle.\n\nWhile we agree that extending the framework to agnostic settings and scenarios involving noise or imperfect alignment between learner and oracle is an important direction for future work, we argue that the current setup still offers meaningful contributions to the literature:\n- The primary aim of this paper is to initiate a theoretical study of learning with contrastive examples. As a first step, it is natural and appropriate to begin by exploring the boundaries of idealized, tractable setups.\n- We establish that, for any distance metric, the complexity of the minimum distance model is lower bounded by the complexity of self-directed learning (a topic that has recently re-gained attention in the learning theory community). To the best of our knowledge, there are few known concept classes where self-directed learning outperforms active learning in terms of sample complexity, with the notable exception of the result by Diakonikolas et al. (2023) for halfspaces over the uniform distribution. Thus, any upper bounds from our idealized setup carry over directly to self-directed learning.\n- As we highlighted in the paper, one of the most prominent applications of our model is counterexample-guided program synthesis, where it is in many cases guaranteed that the learner has perfect knowledge of the oracle and the target concept lies in the concept class.\n\nIn addition, we would like to point out that our framework naturally extends to setups where the learner has imperfect knowledge of how the oracle selects contrastive examples; see also our response to Reviewer 9itQ.\n\n# Individual Response\nWe have tried to address the questions you raised in our general response to all reviewers. \n\n\nReferences:\n\nDiakonikolas, Ilias, et al. \"Self-directed linear classification.\" The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023."}, {"review_id": "ICGD1cwAZV", "reviewer": "Reviewer_W69F", "summary": "This paper considers theoretical upper and lower bounds of label complexity for a variant of active learning, where the oracle can give a \"contrastive\" example in addition to the label of the query example. It considers two specific types or oracles for contrastive examples: (1) $CS_{min}$: it always gives the example that is closest to the query example but has a different label; (2) $CS_{prox}$: it gives any example whose distance to the query example is less than $r$ and whose label is different. It assumes that the learner knows the oracle's algorithm for finding contrastive examples, and that the oracle always gives the correct label for the query example. \n\nIt mainly considers two types of concept classes: thresholds/rectangales, and variants of monotone Boolean functions, and consequently the distance metric for the contrastive oracle is l1 and hamming distance. For k-dimensional rectangles, it shows that with $CS_{prox}$ can improve the label complexity by a factor of k, and for $CS_{min}$ (which is quite strong), it improves label complexity to O(1). For Boolean functions, it shows that both $CS_{prox}$ and $CS_{min}$ reduces label complexity for some simple variants of monotone monomials, but not for others. In terms of lower bound, it shows a nice reduction from self-directed learning (to some degree a mix of online and active learning), and thus gives a metric-agnostic lower bound based on the mistake bound of self-direct learning.  It also gives some lower bounds  for $CS_{min}$ depending on the hamming distance.", "questions": "- Regarding significance, I would appreciate if the authors could comment on the limitation I mentioned in the Strengths And Weaknesses section.\n\n- (Minor) For the lower bound in section 4.1., the connection to Self-directed learning looks nice, but how strong is this result? Or is there any interesting insights from it?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Quality: The results look technically correct and sound to me (I quickly went through the proof sketches in the main text and did not check proofs in Appendix).\n\nClarity: The paper is overall well organized and written. It is pretty definition and theory heavy, but it provides plenty of explanation, examples, and proof sketches, which is helpful.\n\nSignificance: This paper considers an interesting and relatively new theoretical problem for active learning. On the downside, the setting and assumption of the paper is quite restrictive:  for concept class, only simple thresholds and boolean functions are considered; for oracle, it assumes it is noiseless, and only considers two simple \"contrastive\" types (min and prox). This limits its impact to both theory and practical community.\n\nOriginality: I'm not very familiar with the literature on contrastive learning, but it looks to me the techniques and results are novel, and related work is sufficiently cited and discussed.", "was_revised": true, "final_justification": "The author response addresses my issues: the limitations remain valid, but the results obtained are nontrivial and interesting enough. I would recommend this paper to be accepted.", "rebuttal": "# General Response to All Reviewers\nThank you for your effort in assessing our work, and for your helpful comments and questions. In this section, we address a common concern raised by multiple reviewers: that our setting is overly idealistic, as it assumes a realizable setup (i.e., the target concept lies within the concept class) and that the learner has perfect knowledge of the oracle.\n\nWhile we agree that extending the framework to agnostic settings and scenarios involving noise or imperfect alignment between learner and oracle is an important direction for future work, we argue that the current setup still offers meaningful contributions to the literature:\n- The primary aim of this paper is to initiate a theoretical study of learning with contrastive examples. As a first step, it is natural and appropriate to begin by exploring the boundaries of idealized, tractable setups.\n- We establish that, for any distance metric, the complexity of the minimum distance model is lower bounded by the complexity of self-directed learning (a topic that has recently re-gained attention in the learning theory community). To the best of our knowledge, there are few known concept classes where self-directed learning outperforms active learning in terms of sample complexity, with the notable exception of the result by Diakonikolas et al. (2023) for halfspaces over the uniform distribution. Thus, any upper bounds from our idealized setup carry over directly to self-directed learning.\n- As we highlighted in the paper, one of the most prominent applications of our model is counterexample-guided program synthesis, where it is in many cases guaranteed that the learner has perfect knowledge of the oracle and the target concept lies in the concept class.\n\nIn addition, we would like to point out that our framework naturally extends to setups where the learner has imperfect knowledge of how the oracle selects contrastive examples; see also our response to Reviewer 9itQ.\n\n# Individual Response\nWe would like to address your questions bellow:\n1. While we agree with most of the limitations raised by the reviewer—and have addressed them in our general response to all reviewers—we would like to emphasize that the concept classes introduced in Section 4, although composed of Boolean functions, are non-trivial to learn.\n2. Importantly, any lower bound established for self-directed learning directly applies to the minimum-distance model. Furthermore, self-directed learning has recently attracted renewed attention in the learning theory community (see, e.g., Devulapalli and Hanneke, 2024).\n\nReferences: \\\nDiakonikolas, Ilias, et al. \"Self-directed linear classification.\" The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.\\\nDevulapalli, Pramith, and Steve Hanneke. \"The dimension of self-directed learning.\" International Conference on Algorithmic Learning Theory. PMLR, 2024."}]

Author rebuttal:

Meta-review: The paper studies active learning with "contrastive examples", where the learner queries for the label of an example, and additionally receives as feedback another nearby example of a different label (either the closest such example, or an example in a given neighborhood).  They give several examples of natural concept classes where such queries offer advantages over basic membership queries.  They also find an interesting connection to the optimal mistake bounds in self-directed learning, in that such mistake bounds always lower-bound the optimal query complexity for contrastive queries.

The reviewers are unanimously in favor of acceptance.
They all agree that the setting is well-motivated and the results are novel and interesting.  Contrastive examples have been empirically useful, and this work provides theoretical insights regarding their power.
All reviews comment that the presentation is quite clear and easy to follow.

The main critique by reviewers is the idealized nature of the setting.  The learner has precise knowledge of the neighborhood from which the opposite-labeled example will be produced (similarly for the min-distance oracle, there is no slack in this min-distance criterion), and uses this information to inform its algorithm.  However, it is understandable that a theoretical framing of the problem should need to formalize some kind of understanding of how these examples will be produced (at least at first), as is common, for instance, in prior works such as local membership queries, adversarial examples, strategic examples, etc.

Another critique (though not raised by reviewers) is that the paper does not offer a general characterization of the optimal query complexity for all concept classes (and metrics), but rather merely gives several examples where such queries can (or cannot) offer a reduction in query complexity compared to basic membership queries.  Some of these examples are merely illustrative of the framework (e.g., thresholds and rectangles), while others are for concept classes of classical interest (e.g., monotone DNFs).

As a remark to the authors: In the special case of Exact Learning, there are classical general dimensions characterizing the optimal query complexity of any concept class, for fairly general families of queries (see e.g., Balcazar, Castro, and Guijarro, JCSS 2002, "A new abstract combinatorial dimension for exact learning via queries", and Balcazar, Castro, and Guijarro, COLT 2001, "A general dimension for exact learning").  I suggest including a discussion of whether the contrastive example queries considered in this work fit into that framework, and if so, how the results presented in this paper compare to what would be obtained from these general characterizations.
Decision: Accept (poster)