Teaching via Best-Case Counterexamples in the Learning-with-Equivalence-Queries Paradigm
Authors: Akash Kumar
Yuxin Chen
Adish Singla
Venue: NeurIPS 2021 Poster (2021)
Keywords: teaching dimension
learning-with-equivalence-queries
best-case teacher
query complexity

Abstract: We study the sample complexity of teaching, termed as "teaching dimension" (TD) in the literature, for the learning-with-equivalence-queries (LwEQ) paradigm. More concretely, we consider a learner who asks equivalence queries (i.e., "is the queried hypothesis the target hypothesis?"), and a teacher responds either "yes" or "no" along with a counterexample to the queried hypothesis. This learning paradigm has been extensively studied when the learner receives worst-case or random counterexamples; in this paper, we consider the optimal teacher who picks best-case counterexamples to teach the target hypothesis within a hypothesis class. For this optimal teacher, we introduce LwEQ-TD, a notion of TD capturing the teaching complexity (i.e., the number of queries made) in this paradigm. We show that a significant reduction in queries can be achieved with best-case counterexamples, in contrast to worst-case or random counterexamples, for different hypothesis classes. Furthermore, we establish new connections of LwEQ-TD to the well-studied notions of TD in the learning-from-samples paradigm.

Teaching via Best-Case Counterexamples in the Learningwitt--piiilleee----uree Paradigm
Akash Kumar 1.2 akk0022ucsd, edu
Yuxin Chen chenyxxin@uchi edu
Adish Singla' adi adishs@mpi-swa org
Max Planck Institute for Software Systems (MPI-SWS),
UC San Diego,
3 University of Chicago
Abstract
We study the sample complexity of teaching, termed as "teaching dimension" (TD) in the literature, for the aeiniin-wwth-equivllenen concretely, we consider a learner who asks equivalence queries (i.c., "is the queried hypothesis the target hypothesis?"), and teacher responds either "yes" or "no" along with a counterexample to the queried hypothesis. This learning paradigm has been extensively studied when the learner receives worst-case random counterexamples; in this paper, we consider the optimal teacher who picks best- counterexamples to teach the target hypothesis within hypothesis class. For this optimal teacher, we introduce LwEQ-TD, a notion of TD capturing the teaching complexity (i.e., the number of queries made) in this paradigm. We show that significant reduction in queries can be achieved with best-case counterexamples, contrast to worst-case or random counterexamples. for different hypothesis classes. Furthermore, we establish new connections of LwEQ-TD to the well-studied notions of TD in the learning- sewhiing-rro--seee woo---rrommleee paradigm.
(LwEQ) paradigm. More
Introduction
Boorning-with-oee querris paradigm involves a learner who asks structured queries to teacher in order to locate a target hypothesis. This paradigm has been extensively studied in machine learning and formal methods research, including automata learning 2 3 4. model checking [5), oracle-guided synthesis (OGIS) (6), model learning 77, among others. Classical literature involves different kinds of queries that a learner could ask [ 8 91, such membership queries (i.c., "is the queried instance consistent with the target hypothesis?") and equivalence queries (i.c., "is the queried hypothesis the target hypothesis?"), In this paper, consider the lcarning-witt witth-equivaleneeeee queriess (LwEQ) paradigm where the learner is only asking equivalence queries and the teacher responds to query either "yes" "no" along with counterexample which the current hypothesis disagrees with the target hypothesis. LwEQ paradigm captures a variety of important problem settings, such as counterexample-guidee synthesis (CEGIS) [TO], data augmentation (CEGAR) (II) and learning regular languages from counterexamples [[2], The focus of our work is to understand the query complexity for the LwEQ paradigm, i.e., the number of equivalence queries needed by the learner for the exact identification of a target hypothesis (
The query complexity clearly depends on the learner model (i.c., the query function deciding the next hypothesis to query), as well as the informativeness of the counterexamples provided by the teacher. In the literature, the query complexity for the LwEQ paradigm has been extensively studied when the learner receives worst-case or random counterexamples I 9 13 14 15
To show worst-case bounds 1 13). classical works have studied teacher who responds with worst-case counterexamples
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

to maximize the number of equivalence queries asked by the learner. Recent work [4] has studied this query complexity when facing more benign teacher who provides counterexamples selected at random from a known probability distribution. In particular, [14] proposed a learning algorithm (i.e., a query function for the learner) that achieves O (log n) query complexity on the expected number of random counterexamples for any hypothesis class of size n. When contrasting this bound with worst-case bounds, shows that random counterexamples could lead to exponential improvement in the query complexity when compared with worst-case counterexamples [13 [4]. Along these lines, an important research question is to understand the query complexity where the counterexamples are picked by more informed and helpful teacher, instead of random worst-case counterexamples.
In this paper, we consider a more powerful teaching setting, where the optimal teacher picks best-case counterexamples to steer the learner towards a target hypothesis. Our goal is to characterize the query complexity for this optimal teacher (also, referred to as teaching complexity LwEQ paradigm. This teaching complexity has been extensively studied for binary classification in the learning-frome from-sampleee (LfS) paradigm [16 17 and is termed as "teaching dimension" "
the paper), for the
(TD) [1. 19 20 21 [22
Beyond the LIS paradigm, various notions of teaching complexity have also been studied in other learning paradigms (see Section [.] for further details). We introduce a new notion of teaching complexity for the LwEQ paradigm, namely "LwEQ teaching dimension" " (LwEQ-TIV TD), capturing the number of queries needed by the learner when best-case counterexamples
23
24
25
26
27
28
29
provided by the optimal teacher. Our study of LwEQ-TD for some prominent hypothesis classes reveals the power of teaching via best-case counterexamples we show significant reduction in query complexity when compared to that for worst-case and random counterexamples. Furthermore, we establish several new connections of LwEQ-TD to the existing notions of TD in the LfS paradigm | Table provides summary of these different teaching settings and learning paradigms; our main results and contributions are summarized below:
I. We characterize the query complexity for the optimal teacher in the LwEQ paradigm, termed as
teaching dimension (LwEQ-TD). (see Section
II. We study the query complexity in the LwEQ paradigm under different teaching settings: worst-case, random, and best-case, distinguished by the informativeness of counterexamples. We showcase the power of best-case counterexamples picked by the optimal teacher, in contrast to worst-case random counterexamples, for different hypothesis classes, including Axes-aligned hyperplanes, Monotone monomials, and Orthogonal rectangles. (see Section 4
III. We establish new connections between LwEQ-TD and LiS-TI TD by studying LwEQ-TD for different learner models based on the richness of their query functions. We show that LwEQ-TD the same as we-TD 18] RTD 22 (24,, and NCTD [27 for hypothesis class when restricting query functions to specific families. In general, LwEQ-TD is weaker than
LfS-TD, e.g., LwEQ-TD boundbbunded by local-PBTD 266 29 of the hypothesis class
when the learner's next query depends on the previous query. (see Section 5
Teaching
Worst-case Teacher
Random-case Teacher
Best-case Teacher
Learning
baaming-with-cquvvllll queries (LwEQ)
Worst-case counterexamples 30 Bl B
Random counterexamples
LwEQ-TD This work
14 32
Learning-frowe taatgg-froo--mmpppp samples (LIS)
Worst-case examples (i.e., least informative)
i.i.d learning
LfS-TD classical TD
[7]
18122 27
Table 1: An overview of different teaching settings in the context of LwEQ and LIS paradigms.
1.1 Background and Related Work
bearning-with-queriee paradigm and equivalence queries. Learning-with with-queries paradigm was introduced in [I] which proposed L* algorithm for exact identification of DFAs (determin- istic finite automaton) when the learner allowed to ask membership queries and equivalence queries. Classical work has studied different types of queries (subset, membership, equivalence, correction, among others) [ J. Among these works, learning with membership queries has been explored in
variety of problem settings, such as PAC learning [[6], active learning 33 34 35 and agnostic
We will collectively refer to these different notions of TD in the LIS paradigm as LIS-TD.

---

learning [36.. In the learning-wiid with equivalence-queries (LwEQ) paradigm, the learner can ask only equivalence queries: furthermore, our work, we consider proper queries, i.e., the queried hypothesis is within the hypothesis class (see Section 6 for discussion on improper queries). In this LwEQ paradigm. [3] studied query complexity when the teacher picks worst-case counterexamples for some key hypothesis classes (e.g., DFA, NFA, Context-free Grammars), and showed an exponential lower bound. [[4] studied random counterexamples, and proposed a learning algorithm, namely Max-Min, which achieves substantially improved bound query complexity. We will investigate the query complexity of Max-Min learner for the hypothesis class of Axes-aligned hyperplanes in Section 4
Teaching in the LfS paradigm for binary classification. Algorithmic machine teaching, first introduced by [8 37], studies the interaction between teacher and learner where the teacher's goal is to find optimal sequence of training samples to teach target hypothesis. [18] introduced a measure of teaching complexity, named teaching dimension (TD) of the hypothesis class, in the learning-frooe from-samples (LfS) paradigm. The classical notion of TD in [T8] characterized the minimum number of samples (i.e., examples) needed to teach a target hypothesis to a version-space learner who picks hypothesis within the version space arbitrarily (in adversarial way). In the past two decades, several new teaching settings have been studied, driven by the motivation to lower teaching complexity and find settings for which TD has better connections with Yapnik-Chervonenkis dimension (VCD) (38). In particular, several new teaching models and complexity measures have been proposed for both the batch teaching settings (e.g., worst-case (18), recursive 22 24), preference-basee [25] and non-clashing models (27)) and the sequential settings
(c.g.. local preference-based model 226 29 ). These teaching settings. in turn, lead to different notions of TD, that we collectively refer to as LIS-TD. In recent work, [29] has characterized these different notions of TD through a unified framework of modeling learners with preference/ranking functions. In Section 5 we will build on this framework to model the learner's ' query functions in the LwEQ paradigm through ranking functions, allowing us connect LwEQ-TD with LfS-TD.
Teaching in other learning settings. Within binary classification setting, teaching complexity results have been extended beyond version space learners, including models for gradient learners 39
40), models inspired by control theory [4] 42), and models for human- cenanneennteed applications [43] 44
45
46). Furthermore, a recent line of research has studied robust notions of teaching in settings where
the teacher has limited information about the learner's dynamies 47
48 49
Given the importance of
teacher-learner interactions in many real-world applications, teaching has also been studied in richer domains. In particular, teaching complexity has been investigated for imitation learning settings 54], and for reinforcement learning settings where the teacher provides reward feedback (55 56]. We see these works as complementary
where the teacher provides demonstrations [50 51 52 53
to ours, and we refer the reader to see (28 for an overview.
Problem Setup
Teaching framework. Let X be ground set of unlabeled instances and )' the set of labels. Let H be a finite class of hypotheses; each element h E H is a function h : X' - y. Here, we only consider boolean functions, and hence y (0, 1). Let 2 C X' x y' be the ground set of labeled examples. Each element = (xz, yz) E 2 represents a labeled example where the label is given by the target hypothesis h", i.e., y= ht (x.z). Furthermore, for any Z C 2, we define version space induced by the examples Z as the subset of hypotheses H(Z) C H that are consistent with the labels of all the examples, i.e.,
H(2) = (h E H Vz (22, E Z, M(xx) }
Equivalence queries. We consider the LwEQ paradigm where learner seeks to identify target hypothesis from the hypothesis class via equivalence queries. In an equivalence query, the learner asks if the current hypothesis, say h' E H. is equivalent to the target hypothesis h² or not. The teacher provides a response r where is either "yes" if h²' h² or "no" along with a counterexample = (Iz. Uz) E Z, such that h h((xz)) + Vz-
Learner model and query protocol. We consider a generic model of the learner that captures our assumptions about how the learner conjectures its hypothesis for equivalence queries based on the responses received from the teacher. A key aspect of this model is the learner's query function é
3

---

over the hypotheses. Based on the information encoded in the inputs of this query function (i.e., the current hypothesis and the history of counterexamples), the learner will choose one hypothesis in H. In the beginning, the learner starts with an initial hypothesis ho E H. the history is Zo = 0. and the version space Hg = H. At a time step 1 2 1, the learner first picks the hypothesis h4 as follows:
((Z--1,h-1))
h4 E H((Z-1).
(2)
where z is the history of counterexamples seen up until time and (((2-11) is the corresponding version space. The learner then queries h, for equivalence to h' and receives response rt- Then, the query protocol proceeds as follows: (i) if r, is "yes", the learner has identified h and stops; (ii) otherwise r, is "no" along with counterexample Z, Zc-1 ] and continues. We summarize this query protocol Algorithm |
using which the learner updates
Algorithm 1: Query protocol between the learner and the teacher
Learner's initial hypothesis is ho H. history is Zo 0, and version space is Ho H:
2 for / = 1,2,3 3. do
learner picks h2 E HZ based on Zı-1 and h as per Eq. (
learner performs an equivalence query with hy;
teacher provides a response rt that is either "yes" or 'no" along with a counterexample 26;
if rt is "yes" then
learner has identified h* and stops;
7
else
learner updates Z: (2:3:
We assume that both the learner and the teacher have full knowledge of X. V. and H: in addition, the teacher knows the target h as well as the learner's query function l. In this work, consider learner models which could be characterized by a specific query function & as discussed above. These include well-known learners studied in the literature, such constant query learer (denoted as (oonst) who picks the next hypothesis h2 arbitrarily in H(( without any preference [ 29 a global query learner (denoted as Eglobal) who uses global ranking over H to pick the next hypothesis hy in H (2 ) as per Eq. (2) [25 29 and the Max-Min learning algorithm (denoted as Min)
introduced in a recent work on LwEQ paradigm
[4
Complexity of teaching (i.e., the number of queries made). this paper, we study the number of equivalence queries asked by the learner to the teacher to identify target hypothesis in Algorithm [ and we call it the query complexity or teaching complexity for LwEQ paradigm interchangeably. Clearly, this query complexity depends the learner's query function e and the choice of counterex- amples by the teacher. In the following sections, we study this complexity for different teacher types depending the informativeness of the provided counterexamples, well for different families of learner types.
3 The Query Complexity with Best-Case Teacher: LWEQ-TD
In this section, we consider the optimal teacher who picks best-case counterexamples with the objective of minimizing the learner's queries for identifying h²" For this optimal teacher, we provide a formal characterization of teaching complexity, namely dimension (LwEQ-TD) paradigm, inspired by different notions of teaching dimension for the seaming-from-sapple (LIS-TD) paradigm 18 26 29
serriingwwithequiivll
queries teaching
Notation. We denote by C a family of learner poodels-alternatveeel we can think of them as a family of query functions. To begin, we fix query function é E L that the learner uses pick next hypotheses for equivalence queries. Our characterization below will be based on understanding the minimal "cost" (i.e., the number of queries needed) in steering the learner from a hypothesis h with the history of counterexamples Z to the target hypothesis /t ii Algorithm [ Z refers to Z,-1 at the beginning of time l.
h refers to ht- and
Minimal cost of steering. We begin by providing a recursive function that captures this cost of steer- ing and will be key to formalize teaching complexity in the LwEQ paradigm. As typically consid- ered in the LfS paradigm [18] 24 26 29]. we consider the "adversarial" perspective in how the learner

---

breaks ties in picking the hypothesis w.r.t. its query function in Eq. 22. The optimal cost for steering the learner from the current history (Z, h) to h" in the query protocol of Algorithm is then given by:
0,
if (( = [ (2)',1
Di(Z,,,1') -
max (E( (w.))
min
otherwise
(3)
Note that Dj in Eq. 3) has max operator w.r.t. the learner's choice and min operator with the teacher's choice (see (29). Furthermore, in this function, we are counting the last query when the learner's queried hypothesis f2 equals / (hence, the number of queries is same as the number of counterexamples received by the learner).
LwEQ-TD. Given fixed query function e E L, an initial hypothesis ha. and target hypothesis h", LwEQ-TD w.r.t. l and h² is the optimal cost for teaching the target hypothesis h":
LwEQ-TD, X, K.H. (C, De(0, ho, h²).
To characterize the teaching complexity for the hypothesis class, we consider the worst-case target hypothesis in H. given by:
LwEQ-TDx,H.M. (4) max D0, hg. h*).
(5)
h"
Finally, compare LWEQ-TD with existing notions of TD in the LIS paradigm (i.c., LfS-TD, see
Footnote I we define LwEQ-TI for a given family of query functions L. Based on [24 27 29], we define LwEQ-TD w.r.t the family as the teaching complexity w.r.t. the best E in that family:
LwEQ-TDx,HL. k. (C)
min max D2(0, bo, h"). REC.
In the following two sections, we will investigate how LwEQ-TD (the complexity of the optimal teacher in the LwEQ paradigm) compares with various other complexity notions. Section 4 investigate different teachers in the LwEQ paradigm, showcasing the power of the optimal teacher. In Section 5
we establish new connections of LwEQ-TD with LIS-TD.
The Query Complexity for Different Teachers in the LwEQ Paradigm
In this section, we study the query complexity in the LwEQ paradigm for different types of teachers. In Section [3] we characterized the query complexity for the optimal teacher who provides best-case counterexamples. The goal of this section is compare the query complexity for the optimal teacher with other variants of teachers as discussed below. We will denote the teacher as TEQ, and we consider the following four variants of teachers:
best-TEQ responds "yes" or "no" along with best-case counterexamples (see Section 3
aandom-TEQ responds "yes" or "no" along with random counterexamples (picked uniformly at random). As discussed in [14, we characterize the query complexity for random-TEQ as the expected number of counterexamples provided by random-TEQ in Algorithm !
worst-TEQ responds "yes" or "no" along with worst-case (least informative) counterexamples. We characterize query complexity for worst-TEd TEQ by replacing the min over the choice of counterexamples with a max in the function De in Eq. (3).
binary-THQ responds ""yss" "no" without any counterexamples.
In the rest of the section, we compare the query complexity for these teachers when interacting with different learners and we characterize this complexity by the richness of their query functions.
4.1 Warm-up: Query Complexity Bounds When Teaching Different Types of Learners
In this section, we study the query complexity bounds for different teachers when teaching various learner models characterized by the richness of the underlying query functions. In particular, we consider the query functions fconst: fgiobal, and f Min (see Section 2 lconst. picks the next
hypothesis hy arbitrarily in H(2,-1) without any preference [29]. Egiobal uses global ranking over
5

---

H. to pick the next hypothesis he in 1((2-1) as per Eq. (2) and is popularly studied in the LiS paradigm 25 29 Min uses a richer history-dependent query function, and was introduced for achieving better query complexity when the counterexamples are chosen randomly [14]. To study the query complexity for different settings (corresponding four teachers and three learners), we consider the hypothesis class of Axes-aligned hyperplanes, a simple yet rich hypothesis class, that generalizes the canonical hypothesis class of threshold boolean functions to higher dimensions. Next, we introduce this hypothesis class
Definition 4.1 (Axes-an (Axes-aligned hyperplanes). Fix an input space X =
in R with labels X a d-dimensional point in Rd,, i.e., x == (I1, T2,, .2....,...... Rd)
ser y = {0. }}, where an input
such that all E [1,n + 1]. We define the hypothesis class of Axes-aligned hyperplanes as:
Haxh = (4) 3is E [1, 11, j E In 11, s.t. VX h(x) = 1f x; S j. otherwise 0} (7)
We summarize the query complexity bounds for leonst, lglobal, and EMax- under different teaching scenarios in Table 2 We note that |Haxhh d (n 1). To capture the global ranking of globall we use a ranking function g Haxh + to...., |Haxh 1.. For a target hypothesis h E Haxh
and a ranking function g. the bounds for Eglabal in Table 2 are described using the following two quantities: (i) 1 : (h Haxh s.t. g(h) "g("))] and (ii) n is defined as the highest number of hypotheses aligned along one of the axis that are preferred over h as per the ranking function Note that 1 < tg < d (n + 1) and 1 S nig S + In the Appendix of the supplementary, we state the bounds from Table 2 as theorems and provide detailed proofs.
Teacher
Learner
binary-TEQ (Yes/No)
worst-
random-TBB
best- best-TEQ
fconst
d. (n +1 E (Not-Applicable)
(d (n 1)) 2 (()
O (d log(n + 1)) 2
Eglobal
O (d log mg) (log(d (n 1)))
1
EMax-Min
Ω (d. log(n + 1))
Table 2: Query complexity for the Axes-aligned hyperplanes considering different teachers and learners; see Section 4.1 for details.
4.2 Lower and Upper Bounds on Query Complexity
To establish lower bounds on the query complexity for three teachers (binary-TEQ, worst-TEQ. random-TEQ), we will consider learner models characterized with optimal query functions. In contrast these lower bounds, we establish upper bounds on the query complexity for the best-case teacher (best-TEQ) by considering a weaker learner model characterized with a global query function (see Section 2) To study the bounds in these different teaching settings, we consider two more hypothesis classes beyond Axes-aligned hyperplanes: (i) Monotone monomials [18] 37] and (ii) Orthogonal rectangles BT 1 57 58), that have been extensively studied in the LIS paradigm.
We summarize the results in Table with detailed proofs deferred to the Appendix of the supplementary. First, we state the results on query complexity for Axes-aligned hyperplanes in the theorem below.
Theorem 1. Consider the hypothesis class of Axes- Axes-eligned hyperplanes Haxh (see Eq. 77) There exists a global learner Eggobal such that best-TEC achieves LwEQ-TD(< (lobal))) of exactly 1. In contrast, for any optimal learner, random- TEEQ provides at least (log d) counterexamples "in expectation" " and worst-TEQ provides ut least Z2 (d log(n + 1)) counterexamples "in the worst-case".
The results in the above theorem are based on the following key ideas. The bound for best- Best-TEQue is based results from Section 1. where showed that specific choice of Eglohal upper bounds the query complexity for best- TEQ by 1. On the other hand, as per Theorem 25 (see [14), the query complexity for random teacher is connected to the VC dimension of hypothesis class independent of the learner model. We show that VCD(Haxh) ) is Q (log d). which entails direct lower bound on the query complexity for random-TEQ for any learner model. Furthermore, we note that the
Giivnn two positive integers and b where a < b. we use the following shorthand notation: je, b] (a, + 1,...,b- b- 1) and [b] {0, 1...., 1}.

---

Teacher
binary-TEQ (Yes/No)
worst-TEQ
random-TED
best- TEQ
Hypothesis class
Axes-aligned hyperplanes
(d (n+ +11 Q (2"))
(d + log(n 1)) Q (m) !
Ω (logg d) Q (m)
1
Monotone monomials
1
Orthogonal rectangles
Ω ((n (n + 1))")
+ 1))
(d)
2
Table 3: Lower and upper bounds on query complexity for the Axes-aligned hyperplanes, Monotone monomials, and Orthogonal rectangles when considering different teaching settings. The lower bounds for three teachers (binary-TEQ. worst-TEQ, random- TEQ) are established based on learner models characterized with optimal query functions; the upper bounds for the best-case teacher (best- TEQ) are established based on learner models characterized with a global query function. Additional details are provided in the proofs of Theorems and
worst-TEQ could force any learner to query a hypothesis in every axis addition to Ω (log(n + 1)) queries in the axis of the target hypothesis.
Now, we define the hypothesis class of Monotone monomials and then state the aforementioned query complexity bounds for this class in Theorem 2
Definition 4.2 (Monotone monomials). Fix a set of literals {wi, U2,..., Uny an input space X = {0, 13", and labels set D' {0, 1}. monotone monomial is negation-free conjunction of literals. If mono(in, i2....; ix) denotes a monotone monomial over the set of k literals {Vi ..g...., Vay ) then it canonically represents a hypothesis h(x) := Ii, A D2z A... A Zig over the input space. With these notations, we define the hypothesis class of Monotone monomials as:
........,. Hunono == {h {11, ,4, 1 S. 21. n), s.t. VX E, 1(x) Fig Fig
Nie
Consider the hypothesis class of Monotone monomials Hmono (see Eq. ( There exists a global learner Eglobal such that best-TEQ achieves LwEQ-TD(& (Eglobal) of exactly 1. contrast, for any optimal learner, random-TE3 TEQ provides at least Q (n) counterexamples "in expectation" and worst-TEQ provides least 52 (n) counterexamples "in the worst-case".
Theorem 2.
Now, we define the hypothesis class of Orthogonal rectangles and then state the aforementioned query complexity bounds for this class in Theorem
Definition 4.3 (Orthogonal rectangles). Fix an input space X = fl..... n3 in Rd with labels set y = =0, 1}. where an input x E X is a d-dimensional point in TRdd, ie,, x == (2,,,2, Fa) such that all x; [1, n 1). We define the class of Orthogonal rectangles
{1 if V Sb
Hroe = h Has.bibsellaa C [(n s.t. VX VX EX h(x)
(0 otherwise.
Theorem 3. Consider the hypothesis class Orthogonal rectangles Hroe (see Eq. (9). There exists a global learner Eglobal such that best best-TEQ achieves LwEQ-TD((<go..) of exactly 2. In contrast, for any optimal learner, random-TTe TEQ provides at least (d) counterexamples "in expectation" and worst-TEQ provides at least Ω (d log(n + 1)) coumterexamples "in the worst-case".
Similar Axes-aligned hyperplanes (see Theorem I. the lower bound results are significantly worse than the upper bound results for rich classes of Monotone monomials (see Theorem 2 and Orthogonal rectangles (see Theorem 3). thereby establishing the power of the best-case teacher. These results are
summarized in Table 3
5 Teaching Dimensions for the LwEQ and LIS Paradigms
In this section, we draw new comparisons of the notion of LwEQ-TD the LwEQ paradigm to existing notions of TD in the LfS paradigm. Based the teaching setting and the learner models, one gets different notions teaching complexity and we collectively refer to these notions as LfS-TD For comparisons with LiS-TD below, we consider the
(see Footnote
I [8] 21 22 25
27
59 29
7

---

framework of [29] that provides unified view of teaching settings by modeling the learners through preference/ranking functions. In the following, we first introduce a notation for these ranking functions and then discuss how a ranking function a, in turn, induces a learner in the LwEQ paradigm.
Learner's query function é using framework of ranking o. Consider a hypothesis class H. version space H C H. and hypotheses hi, h², h E H such that h', E H. Building on the notation for a preference function a (see (29). we define ranking function : H. x 2 H + R where (hh' H. h) signifies how h' is ranked in the version space H from the current hypothesis h. Thus, we say h ranked (or preferred) over h" in the current version space H from the current hypothesis h if or (h'; H, ht) S a(h;; H, h), and vice versa. Similar to sefference-based learners (29], a learner's query function (see Section 2) could use this ranking to pick the most preferred hypothesis for an equivalence query. In this section, we consider query functions for our learner model & (see Section 2 which use a framework of a ranking function a to pick the next hypothesis he based on the current history of counterexamples seen Z1-1 and the current hypothesis h as follows:
E(Zz-1, 1--1 - he arg min ol'; ((()-1), MEH)(Z-))
(10)
In this section, we identify learner model e with the corresponding ranking o and consequently use the notation LwEQ-TDxx x. (a) (for fixed X, H. ho) for LwEQ-TD (see Eq. (5), Section 3
for the learner model fr. We denote a family of ranking functions a as Σ. For a family of ranking
functions E. the corresponding LwEQ teaching dimension is denoted as LwEQ-TDxxHH.. (E) (see
Eq. (6). Section 3).
For families of learner models induced by specific types of ranking functions, connect LwEQ-TD to existing notions of LfS-TD. In the following, we consider ranking functions broadly categorized into classes: (i) ranking functions independent of Z and h (ii) ranking functions dependent on Z and/or hy-1.
5.1 LwEQ Learners with Ranking Functions Independent of 7 and h;-1
These ranking functions induce learners whose next equivalence query at time & (i.e., choice of the hypothesis h4) is independent of the history of counterexamples Z and independent of the hypothesis h (see Algorithm [ Section 2) In Section 4.1 we discussed these learner families under the name of contant and global learners, and we formalize these families below using the ranking functions framework of Eq. (10). In particular, we introduce two families of ranking functions: (i) Econst is a family of constant ranking functions where a E Econst ranks every hypothesis equally without any preference; (ii) Eglobal is a family of global ranking functions where Eglobal ranks hypothesis based on a global preference. These two families are given below:
E Eooust {ol 3 C E R, s.t. Vh' Z, o('; H(Z), = =c.
(11)
Egloball tol 3 g : H + R, s.t. Vh' Z, h, (H:H(Z))N) 9(h'))
(12)
Given these ranking functions, the following theorem establishes the connection of LwEQ-TD. BEEE--DD,H.A. X,H (Econst) and LwEQ-TDL -BQQ--DDxHH... (Egloba) with existing notions of LfS-TD; also
see Eq. (6) in Section 3
Theorem 4. Fix X, N,H, hy- For learners whose query function is induced by ranking function independent of Zi-1 and hi-1, the corresponding LwEQ is equivalent the notions of LfS-TD as follows:
LWEQ-TD X,H,Ao (Ecoust) = wc-TD(H)
(13)
LwEQ-TDxxxa H, (Zglohhl) = RTD(H).
(14)
When the rankings are independent of 7,_ and h1-1- Eq. 13) and Eq. 14 connect LwEQ-TD to the notions of wc-TD [18] and RTD [22 [4] in batch teaching settings (the optimal teaching sequence is invariant to its permutation) of the LIS paradigm. To show the equalities, we note that Z' C Z is a teaching sequence for fixed At" in the LiS paradigm, then there exists a per- mutation of Z' which forms a teaching sequence of counterexamples for the learer in the LwEQ
We use the notation ly for learner's query function & using a ranking o.
8

---

paradigm. Furthermore, this theorem allows us to connect LwEQ-TD, H., (Eglobal) with VCD(H)
as RTD(H) o (VCD²(H)) 24 29
A detailed proof of the theorem is in the Appendix of the
supplementary.
5.2 LwEQ Learners with Ranking Functions dependent on Zt-1 and/or he-1
Here, we consider ranking functions that induce learners whose next equivalence query at time t (i.e., choice of the hypothesis h₂) dependent on the history of counterexamples Z and/or on the
hypothesis f (see Algorithm| Section 2). We formalize these families below using the ranking functions framework of Eq. (T0) In particular, we introduce three families of ranking functions: (i) Egvs is a family of global version space ranking functions where E Egvs ranks hypotheses based on a global preference dependent on Z but independent of h;-1; (ii) Elocal is a family of local ranking functions where a E Elocal ranks hypotheses based on a local preference dependent only on h--1: (iii) Eiva is a family of local version space ranking functions where a E Eive ranks hypotheses based on local preference dependent on Z,-1 and h These three families are given below:
Egvs = {o 3 gg
H x 2 IR, s.t. Vh' h,h, oW H(Z),) = H(2))
(15)
Elocal {a 3 g HxH RR s.I. VA 2,4, OM; H()))) h) = =g(H,))
(16)
Eiss
{o g H x 2 x H R. s.t. Ah' h,h, aN: () = s(h, (((),
(17)
As discussed in the LfS paradigm, these ranking functions could lead to the learner and the teacher colluding to achieve arbitrarily low teaching complexity (2).. To avoid this, we consider a specific collusion-free behavior where the ranking is consistent with its choice of hypothesis. More formally,
Definition 5.1 (Collusion-free ranking (29)). Consider a time t where the learner's 's current hypoth- esis is he-1 and the history of inputs seen is ZI-1. Further assume that the learner's preferred hypoth- esis for time t is uniquely given by arg min EM(Z.-1) o (h'; (h';; H H( tional examples provided by an adversary from time onwards. We call ranking function collusion- free if for any S consistent with h, it holds that arg m a ; H(Z S), h) (h).
{h.. Let S be addi-
we consider subsets that satisfy Definition 5.1 and con- sequently the corresponding collusion-free families are denoted ΣCE DCF and 2Ivs' For these
For the ranking functions in Eqs. 15- 17
ranking functions, we study the connection of LwEQ-TD. X Ho (2gra) LwEQ-TD, H. (2
(2local)
and LwEQ-TD x k. (E(() with existing notions of LfS-TD, in particular NCTD [27 local-
PBTD [59| [2), and wc-TD [18 29). We state these connections in the following theorem and provide detailed proofs in the Appendix of the supplementary.
Theorem 5. Fix X, H. hg. For learners whose query function is induced by a ranking function dependent on Z:-1 and/or h the corresponding LwEQ-TD is connected to the notions of LfS-TD as:
LWEQ TOEE-TDxxRaR H, (E = NCTD(HL)
(18)
local-PBTDx,0 H.A. S LWEQ-TD X,H, (Erocal) S wc-TD(()..
(19)
Ivs- Ivs-PBTD < LWEQ-TEE TD TD (E S wC-HD(
(20)
To achieve equality in Eq. 188. we observe that the family of rankings DEr leads to batch teaching setting in the LiS paradigm. To show this equality, we establish the permutation invariance of a teaching set Z C Z in the LIS paradigm to form teaching sequence of counterexamples in the LWEQ paradigm using the callusion-freenes property of the underlying ranking function.
To show the lower bounds in Eq. (19 and Eq. (20), we note that a teaching sequence of counterexam- ples in the LwEQ paradigm forms a teaching sequence the LfS paradigm. For the upper bound of wc-TD(H), we note that a constant query learner (see Eq. (TI)) could pick any consistent hypothesis in a version space to maximize the number of counterexamples. This observation, along with the results in Theorem 4 leads to the desired upper bound.

---

Concluding Discussions
We investigated the query complexity for the teeerrrinng-iiit-uuuulllllrtnnn wiith-eqivvlenne--ueriie (LwEQ) paradigm when the counterexamples of teaching dimension, to characterize the complexity of teaching (i.e., the number queries made) for the optimal teacher. We showed the power of best-case counterexamples picked by the optimal teacher, in contrast to worst-case or random counterexamples, for different hypothesis classes, including Axes-aligned hyperplanes, Monotone monomials, and Orthogonal rectangles. We further established new connections of LwEQ-TD with existing notions of TT in the learning-wiin soaningwwith-samaee with-samples paradigm, including wc-TD, RTD, NCTD, and local-PBTD.
provided by the optimal teacher. We introduced LwEQ-TD. notion
In the Boariingwwit-queer combination of different query types [ 8 151, such membership queries, equivalence queries, among others. Building on our characterization future work is to investigate similar notions of TD when learner can ask combination of different queries, Alternatively, one could study LwEQ in the setting of improper equivalence queries where the learner pick the queried hypothesis outside the hypothesis class. [3]] considered improper cquivalence queries in the LwEQ paradigm, leading to a reduction in query complexity for various hypothesis classes. It would be important to characterize the teaching complexity for best-case counterexamples with improper equivalence queries.
paradigm, several works have analyzed the query complexity for a
LwEQ-TD, an important research direction of
Another important research direction is to further investigate LwEQ-TD for more complex hypothesis classes, including DFA (deterministic finite automaton), NEA (nondeterministic finite-state state acceptors), CFG (context-free grammars), among others. As concrete hypothesis class, one could consider DFA (i.e.. DFA with alphabet size 2 and state size s). For this hypothesis class, the query complexity exponential in s when considering worst-case counterexamples [33] [00] computed VCD for variety of hypothesis classes including DFA this result along with query complexity bounds of the Max-Min algorithm in (14) establishes the bound of θ (s log s) on the expected number of random counterexamples for DFA As future work, it would be interesting to investigate LwEQ-TD for DFA A concrete direction is to study the query complexity when providing more structured counterexamples (e.g., by picking minimal length counterexamples considered in [2] this would allow establishing an upper bound for best-case counterexamples.
References
[1] Dana Angluin. Learning Regular Sets from Queries and Counterexamples. Information and Computation, 75(2):87-106, 1987.
[2] Leonard Pitt. Inductive Inference, DFAs, and Computational Complexity. In Proceedings of the International Workshop on Analogical and Inductive Inference, All '89, page 18-44, 1989.
[3] J. Balcázar, J. Díaz, and R. Gavaldà. Algorithms for Learning Finite Automata from Queries: A Unified View. In Advances in Algorithms, Languages, and Complexity, 1997.
[4] B. Bollig, P. Habermehl, C. Kern, and M. Leucker. Angluin-Style Learning of NFA. In IJCAI, 2009.
[5] Doron Peled, Moshe Y. Vardi, and Mihalis Yannakakis. Black Box Checking, pages 225-240. 1999.
[6] Susmit Jha and Sanjit Seshia. A Theory of Formal Synthesis via Inductive Learning. Acta Informatica, 54, 2017.
[7] Frits Vaandrager. Model Learning. Communications of the ACM, 60(2):86-95, 2017.
[8] Dana Angluin. Queries Revisited. Theoretical Computer Science, 313(2):175 - 194, 2004.
[9] Dana Angluin. Queries and Concept Learning. Machine Learning, 2(4):319-342, 1988.
[10] Armando Solar-Lezama, Liviu Tancau, Rastislav Bodik, Sanjit Seshia, and Vijay Saraswat. Combinatorial Sketching for Finite Programs. SIGARCH, 3444 2006. 2006.
10

---

[11] Tommaso Dreossi, Shromona Ghosh, Xiangyu Yue, Kurt Keutzer, Alberto Sangiovanni- Vincentelli, and Sanjit A. Seshia. Counterexample-Gun Guided Data Augmentation. In IJCAI, page 2071-2078, 2018.
[12] Oscar Habarra and Tao Jiang. Learning Regular Languages from Counterexamples. Journal of Computer and System Sciences, 43(2):299-316, 1991.
[13] Dana Angluin. Negative Results for Equivalence Queries. Machine Learning, 5(2):121-150, 1990.
[14] Dana Angluin and Tyler Dohrn. The Power of Random Counterexamples. In ALT, pages 452-465, 2017.
[15] Hunter Chase and James Freitag. Bounds in Query Learning. COLT, pages 1142-1160, 2020.
[16] L. Valiant. A Theory the Learnable. Communications of ACM, 27(11):1134-1144, 1984.
[17] V. N. Vapnik. An Overview of Statistical Learning Theory. IEEE Transactions on Neural Networks, 10(5):988-99) 1999.
[18] Sally A. Goldman and Michael J. Kearns. On the Complexity of Teaching. Journal of Computer and System Sciences, 50(1):20-23 1995.
[19] Christian Kuhlmann. On Teaching and Learning Intersection-Closs Concept Classes. In European Conference on Computational Learning Theory, pages 168-182, 1999.
[20] Frank J Balbach. Measuring Teachability using Variants of the Teaching Dimension. Theoretical Computer Science, 397(1-3):94 113, 2008
[21] Sandra Zilles, Steffen Lange, Robert Holte, and Martin Zinkevich. Teaching Dimensions Based on Cooperative Learning. In COLT, pages 135-146, 2008.
[22] Sandra Zilles, Steffen Lange, Robert Holte, and Martin Zinkevich. Models of Cooperative Teaching and Learning. JMLR, 12:349-384, 2011.
[23] Xiaojin Zhu. Machine Teaching for Bayesian Learners in the Exponential Family, In NeurIPS, pages 1905-1913, 2013.
[24] Thorsten Doliwa, Gaojian Fan, Hans Ulrich Simon, and Sandra Zilles. Recursive Teaching Dimension, VC-Dimension and Sample Compression. JMLR, 151):3107-3111, 2014.
[25] Ziyuan Gao, Christoph Ries, Hans U Simon, and Sandra Zilles. Preference-Based Teaching, JMLR, 18(31):1-32, 2017.
[26] Yuxin Chen, Adish Singla, Oisin Mac Aodha, Pietro Perona, and Yisong Yue. Understanding the Role of Adaptivity in Machine Teaching: The Case of Version Space Learners. In NeurIPS, 2018.
[27] David Kirkpatrick, Hans U. Simon, and Sandra Zilles. Optimal Collusion- Teaching, In ALT, volume 98, pages 506-528, 2019.
[28] Xiaojin Zhu, Adish Singla, Sandra Zilles, and Anna N. Rafferty. An Overview of Machine Teaching. CoRR, /ts//8011.5592 2018.
[29] Farnam Mansouri, Yuxin Chen, Ara Vartanian, Xiaojin Zhu, and Adish Singla. Preference- based Batch and Sequential Teaching: Towards a Unified View of Models. In NeurlPS, pages 9195 9205, 2019.
[30] Dana Angluin, Lisa Hellerstein, and Marek Karpinski. Learning Read-Once Formulas with Queries. Technical report, USA, 1989.
[31] G. Turan and W. Maass. On the Complexity of Learning from Counterexamples. FOCS, pages 262-267, 1989.

---

[32] Jagdeep Singh Bhatia. Simple and Fast Algorithms for Interactive Machine Learning with Random Counter-examples. JMLR, 22(15):1-30, 2021.
[33] Y. Freund, Seung, E. Shamir, and Naftali Tishby. Selective Sampling Using the Query by Committee Algorithm. Machine Learning. 28:133-168, 2004.
[34] D. Cohn, L. Atlas, and R. Ladner. Improving Generalization with Active Learning. Machine Learning, 15:201-221, 1994.
[35] Sanjoy Dasgupta. Coarse Sample Complexity Bounds for Active Learning. In NeurlPS, page 235-242, 2005.
[36] Vitaly Feldman. On the Power of Membership Queries in Agnostic Learning. JMLR, 10:163-182, 2009.
[37] Ayumi Shinohara and Satoru Miyano. Teachability in Computational Learning. New Gen. Comput., 8(4)3337-347, 1991.
[38] VN Vapnik and A Ya Chervonenkis. On the Uniform Convergence of Relative Frequencies of Events to Their Probabílities. Theory of Probability and its Applications, 16(2):264, 1971.
[39] Weiyang Liu, Bo Dai, Ahmad Humayun, Charlene Tay, Chen Yu, Linda B. Smith, James M. Rehg, and Le Song. Iterative Machine Teaching. In ICML, pages 2149-2158, 2017.
[40] Weiyang Liu, Bo Dai, Xingguo Li, Zhen Liu, James M. Rehg, and Le Song. Towards Black-box Iterative Machine Teaching. In ICML, pages 3147-3155, 2018.
[41] Xiaojin Zhu, An Optimal Control View of Adversarial Machine Learning. abs/1811 1.04222, 2018.
CoRR,
[42] Laurent Lessard, Xuezhou Zhang, and Xiaojin Zhu. An Optimal Control Approach to Sequential Machine Teaching. In AISTATS, pages 2495-2503, 2019.
[43] Adish Singla, Ilija Bogunovic, G Bartók, A Karbasi, and A Krause. On Actively Teaching the Crowd to Classify. In NIPS Workshop on Data Driven Education, 2013.
[44] Adish Singla, Ilija Bogunovic, Gábor Bartók, Amin Karbasi, and Andreas Krause. Near- Optimally Teaching the Crowd Classify. In ICMI., volume 32, pages 155-162, 2014.
[45] Anette Hunziker, Yuxin Chen, Oisin Mac Aodha, Manuel Gomez Rodriguez, Andreas Krause, Pietro Perona, Yisong Yue, and Adish Singla. Teaching Multiple Concepts to a Forgetful Learner. In NeurlPS, pages 4050-4060, 2019.
[46] Oisin Mac Aodha, Shihan Su, Yuxin Chen, Pietro Perona, and Yisong Yue. Teaching Categories to Human Learners with Visual Explanations. In CVPR, pages 3820-3828, 2018
[47] Sanjoy Dasgupta, Daniel Hsu, Stefanos Poulis, and Xiaojin Zhu. Teaching a Black- -ox Learner. In ICML, pages 1547-1555, 2019.
[48] Rati Devidze, Farnam Mansouri, Luis Haug, Yuxin Chen, and Adish Singla. Understanding the Power and Limitations of Teaching with Imperfect Knowledge. In IJCAI, pages 2647-2654.
[49] Ferdinando Cicalese, Sergio Filho, Eduardo Laber, and Marco Molinaro. Teaching with Limited Information on the Leamer'' 's Behaviour. In ICML, 2020.
[50] Maya Cakmak and Manuel Lopes. Algorithmic and Human Teaching of Sequential Decision Tasks. In AAAI, volume 26, 2012.
[51] Thomas J. Walsh and Sergiu Goschin. Dynamic Teaching in Sequential Decision Making Environments. In UAI, page 863-872, 2012.
[52] Parameswaran Kamalaruban, Rati Devidze, Volkan Cevher, and Adish Singla. Interactive Teaching Algorithms for Inverse Reinforcement Learning. In IJCAI, pages 2692-2700, 2019.
[53] Daniel S Brown and Scott Niekum. Machine Teaching for Inverse Reinforcement Learning: Algorithms and Applications. In AAAI, 2019.
12

---

[54] Sebastian Tschiatschek,, Ahana Ghosh. Luis Haug, Rati Devidze, and Adish Singla. Learner- aware Teaching: Inverse Reinforcement Learning with Preferences and Constraints. In NeurIPS, 2019.
[55] Amin Rakhsha, Goran Radanovic, Rati Devidze, Xiaojin Zhu, and Adish Singla. Policy Teaching via Environment Poisoning: Training-time timeing-timeeee Adversarial Attacks against Reinforcement Learning. In ICML, 2020.
[56] Xuezhou Zhang, Shubham Kumar Bharti, Yuzhe Ma, Adish Singla, and Xiaojin Zhu. The Sample Complexity of Teaching by Reinforcement on Q-Learning. In AAAI, 2021.
[57] Kathleen Romanik. Approximate Testing and Learnability. page 327-332, 1992.
[58] Kathleen Romantik and Carl Smith. Testing Geometric Objects. Computational Geometry, 137):177-176, 1994.
[59] Yuxin Chen, Oisin Mac Aodha, Shihan Su, Pietro Perona, and Yisong Yue. Near-Optimal Machine Teaching via Explanatory Teaching Sets. In AISTATS, 2018.
[60] Y. Ishigami and Sei 'chicci Tani. The VC-Dimensions of Finite Automata with States. In ALT,
1993.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes] See Section and Section [
(b) Did you describe the limitations of your work? [Yes] We discuss how our results can be extended further future work directions in Section
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] All proofs can be found in appendices.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "T0YHyz3xcQU", "reviewer": "Reviewer_SpHM", "summary": "This paper studies the equivalence query learning model where the teacher presents counterexamples if the learner proposes an incorrect hypothesis.  Three types of teachers are considered: (1) the \"worst-case teacher\" that presents adversarial counterexamples, (2) the \"random teacher\" that presents random counterexamples and (3) the \"best-case teacher\" that presents counterexamples designed to guide the learner towards the correct hypothesis in as few learning steps as possible.  Further, the query learner is equipped with a preference function on which the choice of its query depends (if its current hypothesis is incorrect).  ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The study of equivalence query learning with helpful teachers seems to be a natural follow-up to previous work on algorithmic teaching and I think the present work is a good starting point.  \n\nComment:\n\n- Supplementary, page 17, line 642: Why does $\\ell_{max-min}$ pick the middle threshold function for querying?  I think this point needs more justification.  I tested this observation on some values, specifically for $n = 20$ and $n = 10$, and the claim seems to be almost correct except that the all-zero concept or all-one concept maximize $E(h,h')$ when the current version space contains these two concepts.  \n\nMinor comments/suggestions:\n\n\n- Page 6, Definition 4.1: Is the input space {${1,...,n}$}$^d$ or {${1,...,n+1}$}$^d$?  In the definition, $x$ is a point in this space with coordinates up to $n+1$, not $n$?\n\n\n- Page 8, line 327: collude -> colluding\n\n- Page 10, reference [17]: Missing space between 'V' and 'N'.\n\n- Supplementary, page 17, matrix between 638 and 639: Why is the subscript of h in the last row $T$ and not $n+1$?  Similarly for the matrix between lines 641 and 642.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "16"}, "extra_text": {}}, {"review_id": "Qupe7PPV2Fx", "reviewer": "Reviewer_AepY", "summary": "This work studies the sample complexity of machine teaching finite hypothesis classes with equivalence queries (EQ), a model in which the learner queries hypotheses in the concept class directly, and the “teacher” responds “yes” or “no” along with a counter-example with the goal of eventually teaching the learner some ground truth concept. \n\nThere are many formalizations of this model in the literature. This work mainly focuses on a natural regime of the problem in which the teacher is “helpful,” always choosing the best possible counter-example to help the learner, and the learner is adversarial, though generally restricted under some fixed “learning rule,” (e.g. they must always pick a hypothesis consistent with previous counter-examples).\n\nThe authors study a notion of query complexity they call “Learning with Equivalence Queries Teaching Dimension” (LwEQ-TD) that is closely related to other forms of TD used in machine teaching. They show that for a variety of fundamental concept classes (axis-aligned halfspaces, axis-aligned rectangles, and monotone monomials), a helpful teacher can always teach even the most adversarial learner in O(1) examples. On the other hand, they give lower bounds on the sample complexity when the teacher gives random or adversarial samples that scales with the size of the class.\n\nFinally, the authors give an in depth comparison between LwEQ-TD and previous notions of machine teaching in the membership query model. Indeed, for a very natural class of adversarial learner, they prove that LwEQ-TD is in fact exactly the standard teaching dimension (along with a host of other connections).\n", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work introduces an original model of machine teaching that is both combinatorially natural, and well motivated in real life. Previous work studying equivalence queries either used a “random” or “adversarial” teacher. To my knowledge, this is the first work to study the scenario of a helpful teacher and a (lightly) adversarial student in the EQ model. \n\nOverall, the results in this work should be of broad interest to the learning community. They prove non-trivial gaps between learning with a helpful and random teacher for several fundamental classes, and establish strong connections with numerous standard notions of teaching complexity such as teaching dimension and recursive teaching dimension. While none of these results alone are of great technical interest, they establish important connections to standard results in an original (and natural) model, which is a valuable contribution.\n\nOverall the paper is well written, though some details appear to be missing (see below). The proofs I checked were technically sound.\n\nA few minor comments for the authors:\n\nTypos: “less benign”  should be “less adversarial” or “more benign,” “contant” should be “constant”\n\nShould $h’$ be over should be $Z \\cup \\{z\\}$ in Eq 3?\n\nIt’d be nice to have some justification as to why the learning function can’t depend on $h_{j}$ for $j<t-1$\n\nReference to learning rules says Section 2, but probably should be app:B.1\n\nIs the learner rule stated somewhere in Table 3?\n\nLearning rules as an abstraction (rather than a specific rule) are never formally defined.\n\nThe various definitions of LfS-TD compared to need to be defined somewhere. If possible in the main body, at least informally. Definitely in an appendix.\n\nEdit: I thank the authors for their response and clarifications.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "BzSdrYasfc6", "reviewer": "Reviewer_iHcM", "summary": "The paper characterises the sample complexity of teaching in the learning with equivalence queries(LwEQ) model. The teachers can be \n1) worst, 2) average and 3) optimal. The number of samples required for the learner to reach the target hypothesis is intuitively the least in the best(3) case. This work draws a connection to the learning from samples model, specifically to the notion of teaching dimension. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written and quite readable. The definitions and the concepts are laid out cleanly.\n\n\nWeakness:\n1) The conjecture in the conclusion (regarding DFAs) needs more discussion. What is the intuition behind the suggested bound? \n2) The paper cites a number of works that study teaching complexity(TD) in the learning-from-samples(LfS) setting.  Although this shows the importance of TD in the LfS setting, it does not say much about the importance of TD in the LwEQ setting. It would be interesting to see a more thorough discussion about the same.\n3) The authors chose 3 hypothesis classes, and in all of them, the teaching complexity is in {1,2}. This does support the intuitive point of the paper that optimal teachers are powerful. However, it would be interesting to see some more complex hypothesis classes with non-trivial lower bounds on the teaching complexity. For example, as written in the conclusion, the problem of determining TD for CFGs and DFA/NFAs is quite intriguing. \n\nMinor Comments:\n1) (line 36) Do you mean a more benign teacher?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors do discuss the relevant limitations.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "7ucXrsW52VX", "reviewer": "Reviewer_ce98", "summary": "This work studied the problem of learning from equivalence queries (EQ) alone where counterexamples are selected by a helpful teacher. The paper characterizes the teaching complexity for different classes and relates the new notion (LwEQ-TD) to different notions in the literature. LwEQ-TD showed significant savings in the complexity of teaching when compared to other teaching notions in some hypothesis classes. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work proposes a new teaching notion called LwEQ-TD for learning from equivalence queries (EQ) only where counterexamples are carefully selected by a teacher. The main strength of the work is that it goes beyond the classical paradigm of *learning from samples* teaching notions (defined as LfS-TD) and characterizes LwEQ-TD when having different learners and loss functions. \n\nThe paper also discusses how LwEQ-TD is related to different notions in LfS-TD such as TD/RTD/ PBTD given a holistic view on different teaching models and notions, which is highly needed with the increase interest in the theories and applications of machine teaching. However, the paper is very condense in its content, proofs, and theorems. Indeed, the work provides new insights and results from a learning theory perspective albeit their practical implications are not very clear. Moreover, learning from EQ alone is not practical in many applications, this needs to be motivated in the context of LwEQ-TD as the cognitive burden of answering one EQ is arguably higher than other types of queries. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work is theoretical", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Throughout the discussion the reviewers agreed unanimously that the paper provides an interesting theoretical contribution and should be accepted to NeurIPS. We urge the authors to revise the paper according to the comments provided by the reviewers in the rebuttal.

Thanks for submitting your work to NeurIPS!
Decision: Accept (Poster)