Teaching via Best-Case Counterexamples in the Learning-with-Equivalence-Queries Paradigm
Year: 2021

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 bestcase 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.

heading: 1 Introduction
text: Learning-with-queries paradigm involves a learner who asks structured queries to a teacher in order to locate a target hypothesis. This paradigm has been extensively studied in machine learning and formal methods research, including automata learning [1, 2, 3, 4], model checking [5], oracle-guided synthesis (OGIS) [6], model learning [7], among others. Classical literature involves different kinds of queries that a learner could ask [1, 8, 9], such as membership queries (i.e., “is the queried instance consistent with the target hypothesis?”) and equivalence queries (i.e., “is the queried hypothesis the target hypothesis?”). In this paper, we consider the learning-with-equivalence-queries (LwEQ) paradigm where the learner is only asking equivalence queries and the teacher responds to a query either “yes" or “no" along with a counterexample on which the current hypothesis disagrees with the target hypothesis. LwEQ paradigm captures a variety of important problem settings, such as counterexample-guided synthesis (CEGIS) [10], data augmentation (CEGAR) [11], and learning regular languages from counterexamples [12]. 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 [9].
The query complexity clearly depends on the learner model (i.e., 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 [1, 9, 13, 14, 15]. To show worst-case bounds [1, 13], classical works have studied a teacher who responds with worst-case counterexamples
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
to maximize the number of equivalence queries asked by the learner. Recent work [14] has studied this query complexity when facing a 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, it shows that random counterexamples could lead to exponential improvement in the query complexity when compared with worst-case counterexamples [13, 14]. Along these lines, an important research question is to understand the query complexity where the counterexamples are picked by a more informed and helpful teacher, instead of random or 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 in the paper), for the LwEQ paradigm. This teaching complexity has been extensively studied for binary classification in the learning-from-samples (LfS) paradigm [16, 17] and is termed as “teaching dimension” (TD) [18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]. Beyond the LfS paradigm, various notions of teaching complexity have also been studied in other learning paradigms (see Section 1.1 for further details). We introduce a new notion of teaching complexity for the LwEQ paradigm, namely “LwEQ teaching dimension” (LwEQ-TD), capturing the number of queries needed by the learner when best-case counterexamples are 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 a 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.1 Table 1 provides a 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 learning-with-equivalence-queries teaching dimension (LwEQ-TD). (see Section 3)
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 or 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 LfS-TD by studying LwEQ-TD for different learner models based on the richness of their query functions. We show that LwEQ-TD is the same as wc-TD [18], RTD [22, 24], and NCTD [27] for a hypothesis class when restricting query functions to specific families. In general, LwEQ-TD is weaker than LfS-TD, e.g., LwEQ-TD is lower-bounded by local-PBTD [26, 29] of the hypothesis class when the learner’s next query depends on the previous query. (see Section 5)

heading: 1.1 Background and Related Work
text: Learning-with-queries paradigm and equivalence queries. Learning-with-queries paradigm was introduced in [1] which proposed L∗ algorithm for exact identification of DFAs (deterministic finite automaton) when the learner is allowed to ask membership queries and equivalence queries. Classical work has studied different types of queries (subset, membership, equivalence, correction, among others) [1, 8, 9]. Among these works, learning with membership queries has been explored in a variety of problem settings, such as PAC learning [16], active learning [33, 34, 35], and agnostic
1We will collectively refer to these different notions of TD in the LfS paradigm as LfS-TD.
learning [36]. In the learning-with-equivalence-queries (LwEQ) paradigm, the learner can ask only equivalence queries; furthermore, in our work, we consider proper queries, i.e., the queried hypothesis is within the hypothesis class (see Section 6 for a discussion on improper queries). In this LwEQ paradigm, [13] 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. [14] studied random counterexamples, and proposed a learning algorithm, namely Max-Min, which achieves a substantially improved bound on 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 [18, 37], studies the interaction between a teacher and a learner where the teacher’s goal is to find an optimal sequence of training samples to teach a target hypothesis. [18] introduced a measure of teaching complexity, named teaching dimension (TD) of the hypothesis class, in the learning-from-samples (LfS) paradigm. The classical notion of TD in [18] 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 an adversarial way). In the past two decades, several new teaching settings have been studied, driven by the motivation to lower teaching complexity and to find settings for which TD has better connections with Vapnik–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-based [25], and non-clashing models [27]) and the sequential settings (e.g., local preference-based model [26, 29]). These teaching settings, in turn, lead to different notions of TD, that we collectively refer to as LfS-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 to 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 [41, 42], and models for human-centered 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 dynamics [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 where the teacher provides demonstrations [50, 51, 52, 53, 54], and for reinforcement learning settings where the teacher provides reward feedback [55, 56]. We see these works as complementary to ours, and we refer the reader to see [28] for an overview.

heading: 2 Problem Setup
text: Teaching framework. Let X be a ground set of unlabeled instances and Y the set of labels. LetH be a finite class of hypotheses; each element h ∈ H is a function h : X → Y . Here, we only consider boolean functions, and hence Y = {0, 1}. Let Z ⊆ X × Y be the ground set of labeled examples. Each element z = (xz, yz) ∈ Z represents a labeled example where the label is given by the target hypothesis h∗, i.e., yz = h∗(xz). Furthermore, for any Z ⊆ Z , we define version space induced by the examples Z as the subset of hypothesesH(Z) ⊆ H that are consistent with the labels of all the examples, i.e.,
H(Z) := {h ∈ H | ∀z = (xz, yz) ∈ Z, h(xz) = yz } . (1)
Equivalence queries. We consider the LwEQ paradigm where a learner seeks to identify a target hypothesis from the hypothesis class via equivalence queries. In an equivalence query, the learner asks if the current hypothesis, say h′ ∈ H, is equivalent to the target hypothesis h∗ or not. The teacher provides a response r where r is either “yes” if h′ ≡ h∗ or “no” along with a counterexample z := (xz, yz) ∈ Z , such that h′(xz) 6= yz .
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 `
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 inH. In the beginning, the learner starts with an initial hypothesis h0 ∈ H, the history is Z0 = ∅, and the version space is H0 = H. At a time step t ≥ 1, the learner first picks the hypothesis ht as follows:
`(Zt−1, ht−1) −→ ht ∈ H(Zt−1), (2)
where Zt−1 is the history of counterexamples seen up until time t andH(Zt−1) is the corresponding version space. The learner then queries ht for equivalence to h∗ and receives a response rt. Then, the query protocol proceeds as follows: (i) if rt is “yes”, the learner has identified h∗ and stops; (ii) otherwise rt is “no” along with a counterexample zt using which the learner updates Zt = Zt−1 ∪ {zt}, and continues. We summarize this query protocol in Algorithm 1.
Algorithm 1: Query protocol between the learner and the teacher 1 Learner’s initial hypothesis is h0 ∈ H, history is Z0 = ∅, and version space isH0 = H; 2 for t = 1, 2, 3, · · · do 3 learner picks ht ∈ H(Zt−1) based on Zt−1 and ht−1 as per Eq. (2); 4 learner performs an equivalence query with ht; 5 teacher provides a response rt that is either “yes” or ‘no” along with a counterexample zt; 6 if rt is “yes” then learner has identified h∗ and stops; 7 else
learner updates Zt = Zt−1 ∪ {zt};
We assume that both the learner and the teacher have full knowledge of X , Y , and H; in addition, the teacher knows the target h∗ as well as the learner’s query function `. In this work, we 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 as a constant query learner (denoted as `const) who picks the next hypothesis ht arbitrarily inH(Zt−1) without any preference [18, 1, 29], a global query learner (denoted as `global) who uses a global ranking overH to pick the next hypothesis ht in H(Zt−1) as per Eq. (2) [25, 29], and the Max-Min learning algorithm (denoted as `Max-Min) introduced in a recent work on LwEQ paradigm [14].
Complexity of teaching (i.e., the number of queries made). In this paper, we study the number of equivalence queries asked by the learner to the teacher to identify a target hypothesis in Algorithm 1, and we call it the query complexity or teaching complexity for LwEQ paradigm interchangeably. Clearly, this query complexity depends on the learner’s query function ` and the choice of counterexamples by the teacher. In the following sections, we study this complexity for different teacher types depending on the informativeness of the provided counterexamples, as well as 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 learning-with-equivalence queries teaching dimension (LwEQ-TD) paradigm, inspired by different notions of teaching dimension for the learning-from-samples (LfS-TD) paradigm [18, 24, 26, 29].
Notation. We denote by L a family of learner models—alternatively, we can think of them as a family of query functions. To begin, we fix a query function ` ∈ L that the learner uses to 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 h∗—in Algorithm 1, h refers to ht−1 and Z refers to Zt−1 at the beginning of time t.
Minimal cost of steering. We begin by providing a recursive function that captures this cost of steering and will be key to formalize teaching complexity in the LwEQ paradigm. As is typically considered 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. (2). The optimal cost for steering the learner from the current history (Z, h) to h∗ in the query protocol of Algorithm 1 is then given by:
D`(Z, h, h ∗) = { 0, if `(Z, h) = {h∗} 1 + max
h′∈`(Z,h) min z:h′(xz)6=yz D`(Z ∪ {z}, h′, h∗), otherwise (3)
Note that D` in Eq. (3) has a 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 not counting the last query when the learner’s queried hypothesis ht equals h∗ (hence, the number of queries is same as the number of counterexamples received by the learner).
LwEQ-TD. Given a fixed query function ` ∈ L, an initial hypothesis h0, and a target hypothesis h∗, LwEQ-TD w.r.t. ` and h∗ is the optimal cost for teaching the target hypothesis h∗:
LwEQ-TDX ,H,h0(`, h ∗) = D`(∅, h0, h∗). (4)
To characterize the teaching complexity for the hypothesis class, we consider the worst-case target hypothesis inH, given by:
LwEQ-TDX ,H,h0(`) = maxh∗ D`(∅, h0, h∗). (5)
Finally, to compare LwEQ-TD with existing notions of TD in the LfS paradigm (i.e., LfS-TD, see Footnote 1), we define LwEQ-TD for a given family of query functions L. Based on [24, 27, 29], we define LwEQ-TD w.r.t the family L as the teaching complexity w.r.t. the best ` in that family:
LwEQ-TDX ,H,h0(L) = min`∈L maxh∗ D`(∅, h0, h ∗). (6)
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. In Section 4, we 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 LfS-TD.

heading: 4 The Query Complexity for Different Teachers in the LwEQ Paradigm
text: 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 to 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). • random-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 1.
• worst-TEQ responds “yes” or “no” along with worst-case (least informative) counterexamples. We characterize query complexity for worst-TEQ by replacing the min over the choice of counterexamples with a max in the function D` in Eq. (3).
• binary-TEQ responds “yes” or “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.

heading: 4.1 Warm-up: Query Complexity Bounds When Teaching Different Types of Learners
text: 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 `const, `global, and `Max-Min (see Section 2). `const picks the next hypothesis ht arbitrarily inH(Zt−1) without any preference [29]. `global uses a global ranking over
H to pick the next hypothesis ht in H(Zt−1) as per Eq. (2) and is popularly studied in the LfS paradigm [25, 29]. `Max-Min uses a richer history-dependent query function, and was introduced for achieving a better query complexity when the counterexamples are chosen randomly [14]. To study the query complexity for different settings (corresponding to 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.2
Definition 4.1 (Axes-aligned hyperplanes). Fix an input space X = {1, 2, . . . , n}d in Rd with labels set Y = {0, 1}, where an input x ∈ X is a d-dimensional point in Rd, i.e., x := (x1, x2, . . . , xd) such that all xi ∈ [1, n+ 1]. We define the hypothesis class of Axes-aligned hyperplanes as:
Haxh := {h | ∃ i ∈ [1, d+ 1], j ∈ [n+ 1], s.t. ∀x ∈ X , h(x) = 1 if xi ≤ j, otherwise 0} . (7)
We summarize the query complexity bounds for `const, `global, and `Max-Min under different teaching scenarios in Table 2. We note that |Haxh| = d · (n + 1). To capture the global ranking of `global, we use a ranking function g : Haxh → {0, . . . , |Haxh| − 1}. For a target hypothesis h∗ ∈ Haxh and a ranking function g, the bounds for `global in Table 2 are described using the following two quantities: (i) t∗g :=
∣∣{h ∈ Haxh s.t. g(h) ≤ g(h∗)}∣∣ and (ii) n∗g is defined as the highest number of hypotheses aligned along one of the axis that are preferred over h∗ as per the ranking function g. Note that 1 ≤ t∗g ≤ d · (n+ 1) and 1 ≤ n∗g ≤ n+ 1. In the Appendix of the supplementary, we state the bounds from Table 2 as theorems and provide detailed proofs.

heading: 4.2 Lower and Upper Bounds on Query Complexity
text: 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 to 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 [31, 18, 57, 58], that have been extensively studied in the LfS paradigm.
We summarize the results in Table 3 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-aligned hyperplanesHaxh (see Eq. (7)). There exists a global learner `global such that best-TEQ achieves LwEQ-TD(`global) of exactly 1. In contrast, for any optimal learner, random-TEQ provides at least Ω (log d) counterexamples “in expectation” and worst-TEQ provides at least Ω (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-TEQ is based on results from Section 4.1, where we showed that a specific choice of `global upper bounds the query complexity for best-TEQ by 1. On the other hand, as per Theorem 25 (see [14]), the query complexity for a random teacher is connected to the VC dimension of a hypothesis class independent of the learner model. We show that VCD(Haxh) is Ω (log d), which entails a direct lower bound on the query complexity for random-TEQ for any learner model. Furthermore, we note that the
2Given two positive integers a and b where a < b, we use the following shorthand notation: [a, b] = {a, a+ 1, . . . , b− 1} and [b] = {0, 1, . . . , b− 1}.
worst-TEQ could force any learner to query a hypothesis in every axis in 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 {v1, v2, . . . , vn}, an input space X = {0, 1}n, and labels set Y = {0, 1}. A monotone monomial is a negation-free conjunction of literals. If mono(i1, i2, . . . , ik) denotes a monotone monomial over the set of k literals {vi1 , vi2 , . . . , vik}, then it canonically represents a hypothesis h(x) := xi1 ∧ xi2 ∧ . . . ∧ xik over the input space. With these notations, we define the hypothesis class of Monotone monomials as:
Hmono := {h | ∃ {i1, i2, . . . , ik} ⊆ {1, 2, . . . , n}, s.t. ∀x ∈ X , h(x) = xi1 ∧ xi2 ∧ . . . ∧ xik } . (8)
Theorem 2. Consider the hypothesis class of Monotone monomialsHmono (see Eq. (8)). There exists a global learner `global such that best-TEQ achieves LwEQ-TD(`global) of exactly 1. In contrast, for any optimal learner, random-TEQ provides at least Ω (n) counterexamples “in expectation” and worst-TEQ provides at least Ω (n) counterexamples “in the worst-case”.
Now, we define the hypothesis class of Orthogonal rectangles and then state the aforementioned query complexity bounds for this class in Theorem 3.
Definition 4.3 (Orthogonal rectangles). Fix an input space X = {1, . . . , n}d in Rd with labels set Y = {0, 1}, where an input x ∈ X is a d-dimensional point in Rd, i.e, x := (x1, x2, . . . , xd) such that all xi ∈ [1, n+ 1]. We define the class of Orthogonal rectangles as:
Hrec := { h ∣∣∣∣ ∃ {aj , bj}j∈[1,d+1] ⊂ [n+ 1] , s.t. ∀x ∈ X , h(x) = {1 if ∀j, aj < xj ≤ bj0 otherwise. } .
(9)
Theorem 3. Consider the hypothesis class of Orthogonal rectanglesHrec (see Eq. (9)). There exists a global learner `global such that best-TEQ achieves LwEQ-TD(`global) of exactly 2. In contrast, for any optimal learner, random-TEQ provides at least Ω (d) counterexamples “in expectation” and worst-TEQ provides at least Ω (d · log(n+ 1)) counterexamples “in the worst-case”.
Similar to Axes-aligned hyperplanes (see Theorem 1), 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.

heading: 5 Teaching Dimensions for the LwEQ and LfS Paradigms
text: In this section, we draw new comparisons of the notion of LwEQ-TD in the LwEQ paradigm to existing notions of TD in the LfS paradigm. Based on the teaching setting and the learner models, one gets different notions of teaching complexity and we collectively refer to these notions as LfS-TD (see Footnote 1) [18, 21, 22, 25, 27, 59, 29]. For comparisons with LfS-TD below, we consider the
framework of [29] that provides a 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 σ, in turn, induces a learner in the LwEQ paradigm.
Learner’s query function ` using a framework of a ranking σ. Consider a hypothesis classH, a version space H ⊆ H, and hypotheses h′, h′′, h ∈ H such that h′, h′′ ∈ H . Building on the notation for a preference function σ (see [29]), we define a ranking function σ : H × 2H ×H → R where σ(h′;H,h) signifies how h′ is ranked in the version space H from the current hypothesis h. Thus, we say h′ is ranked (or preferred) over h′′ in the current version space H from the current hypothesis h if σ(h′;H,h) ≤ σ(h′′;H,h), and vice versa. Similar to preference-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 σ to pick the next hypothesis ht based on the current history of counterexamples seen Zt−1 and the current hypothesis ht−1 as follows:
`(Zt−1, ht−1) −→ ht ∈ arg min h′∈H(Zt−1) σ(h′;H(Zt−1), ht−1). (10)
In this section, we identify a learner model `σ3 with the corresponding ranking σ and consequently use the notation LwEQ-TDX ,H,h0(σ) (for fixed X ,H, h0) for LwEQ-TD (see Eq. (5), Section 3) for the learner model `σ. We denote a family of ranking functions σ as Σ. For a family of ranking functions Σ, the corresponding LwEQ teaching dimension is denoted as LwEQ-TDX ,H,h0(Σ) (see Eq. (6), Section 3).
For families of learner models induced by specific types of ranking functions, we connect LwEQ-TD to existing notions of LfS-TD. In the following, we consider ranking functions broadly categorized into two classes: (i) ranking functions independent of Zt−1 and ht−1; (ii) ranking functions dependent on Zt−1 and/or ht−1.

heading: 5.1 LwEQ Learners with Ranking Functions Independent of Zt−1 and ht−1
text: These ranking functions induce learners whose next equivalence query at time t (i.e., choice of the hypothesis ht) is independent of the history of counterexamples Zt−1 and independent of the hypothesis ht−1 (see Algorithm 1, 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) Σconst is a family of constant ranking functions where σ ∈ Σconst ranks every hypothesis equally without any preference; (ii) Σglobal is a family of global ranking functions where σ ∈ Σglobal ranks hypothesis based on a global preference. These two families are given below:
Σconst = {σ | ∃ c ∈ R, s.t. ∀h′, Z, h, σ(h′;H(Z), h) = c} . (11)
Σglobal = {σ | ∃ g : H → R, s.t. ∀h′, Z, h, σ(h′;H(Z), h) = g(h′)} . (12)
Given these ranking functions, the following theorem establishes the connection of LwEQ-TDX ,H,h0(Σconst) and LwEQ-TDX ,H,h0(Σglobal) with existing notions of LfS-TD; also see Eq. (6) in Section 3.
Theorem 4. Fix X ,H, h0. For learners whose query function is induced by a ranking function independent of Zt−1 and ht−1, the corresponding LwEQ-TD is equivalent to the notions of LfS-TD as follows:
LwEQ-TDX ,H,h0(Σconst) = wc-TD(H). (13) LwEQ-TDX ,H,h0(Σglobal) = RTD(H). (14)
When the rankings are independent of Zt−1 and ht−1, Eq. (13) and Eq. (14) connect LwEQ-TD to the notions of wc-TD [18] and RTD [22, 24] in batch teaching settings (the optimal teaching sequence is invariant to its permutation) of the LfS paradigm. To show the equalities, we note that if Z ′ ⊆ Z is a teaching sequence for fixed h∗ in the LfS paradigm, then there exists a permutation of Z ′ which forms a teaching sequence of counterexamples for the learner in the LwEQ
3We use the notation `σ for a learner’s query function ` using a ranking σ.
paradigm. Furthermore, this theorem allows us to connect LwEQ-TDX ,H,h0(Σglobal) with VCD(H) as RTD(H) = O ( VCD2(H) ) [24, 29]. A detailed proof of the theorem is in the Appendix of the supplementary.

heading: 5.2 LwEQ Learners with Ranking Functions dependent on Zt−1 and/or ht−1
text: Here, we consider ranking functions that induce learners whose next equivalence query at time t (i.e., choice of the hypothesis ht) is dependent on the history of counterexamples Zt−1 and/or on the hypothesis ht−1 (see Algorithm 1, Section 2). We formalize these families below using the ranking functions framework of Eq. (10). In particular, we introduce three families of ranking functions: (i) Σgvs is a family of global version space ranking functions where σ ∈ Σgvs ranks hypotheses based on a global preference dependent on Zt−1 but independent of ht−1; (ii) Σlocal is a family of local ranking functions where σ ∈ Σlocal ranks hypotheses based on a local preference dependent only on ht−1; (iii) Σlvs is a family of local version space ranking functions where σ ∈ Σlvs ranks hypotheses based on a local preference dependent on Zt−1 and ht−1. These three families are given below:
Σgvs = { σ ∣∣ ∃ g : H× 2H → R, s.t. ∀h′, Z, h, σ(h′;H(Z), h) = g(h′,H(Z))} . (15)
Σlocal = {σ | ∃ g : H×H → R, s.t.∀h′, Z, h, σ(h′;H(Z), h) = g(h′, h)} . (16)
Σlvs = { σ ∣∣ ∃ g : H× 2H ×H → R, s.t. ∀h′, Z, h, σ(h′;H(Z), h) = g(h′,H(Z), 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 [29]. 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 current hypothesis is ht−1 and the history of inputs seen is Zt−1. Further assume that the learner’s preferred hypothesis for time t is uniquely given by arg minh′∈H(Zt−1) σ(h
′;H(Zt−1), ht−1) = {ĥ}. Let S be additional examples provided by an adversary from time t onwards. We call a ranking function σ collusionfree if for any S consistent with ĥ, it holds that arg minh′∈H(Zt−1∪S) σ(h ′;H(Zt−1 ∪ S), ĥ) = {ĥ}.
For the ranking functions in Eqs. (15)-(17), we consider subsets that satisfy Definition 5.1, and consequently the corresponding collusion-free families are denoted as ΣCFgvs, Σ CF local, and Σ CF lvs. For these ranking functions, we study the connection of LwEQ-TDX ,H,h0(Σ CF gvs), LwEQ-TDX ,H,h0(Σ CF local), and LwEQ-TDX ,H,h0(Σ CF lvs) with existing notions of LfS-TD, in particular NCTD [27], localPBTD [59, 29], 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, h0. For learners whose query function is induced by a ranking function dependent on Zt−1 and/or ht−1, the corresponding LwEQ-TD is connected to the notions of LfS-TD as:
LwEQ-TDX ,H,h0 ( ΣCFgvs ) = NCTD(H). (18)
local-PBTDX ,H,h0 ≤ LwEQ-TDX ,H,h0(Σ CF local) ≤ wc-TD(H). (19)
lvs-PBTDX ,H,h0 ≤ LwEQ-TDX ,H,h0(Σ CF lvs) ≤ wc-TD(H). (20)
To achieve equality in Eq. (18), we observe that the family of rankings ΣCFgvs leads to a batch teaching setting in the LfS paradigm. To show this equality, we establish the permutation invariance of a teaching set Z ⊆ Z in the LfS paradigm to form a teaching sequence of counterexamples in the LwEQ paradigm using the collusion-freeness property of the underlying ranking function.
To show the lower bounds in Eq. (19) and Eq. (20), we note that a teaching sequence of counterexamples in the LwEQ paradigm forms a teaching sequence in the LfS paradigm. For the upper bound of wc-TD(H), we note that a constant query learner (see Eq. (11)) 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.

heading: 6 Concluding Discussions
text: We investigated the query complexity for the learning-with-equivalence-queries (LwEQ) paradigm when the counterexamples are provided by the optimal teacher. We introduced LwEQ-TD, a notion of teaching dimension, to characterize the complexity of teaching (i.e., the number of 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 TD in the learning-with-samples paradigm, including wc-TD, RTD, NCTD, and local-PBTD.
In the learning-with-queries paradigm, several works have analyzed the query complexity for a combination of different query types [1, 8, 15], such as membership queries, equivalence queries, among others. Building on our characterization of LwEQ-TD, an important research direction of future work is to investigate similar notions of TD when a learner can ask a combination of different queries. Alternatively, one could study LwEQ in the setting of improper equivalence queries where the learner can pick the queried hypothesis outside the hypothesis class. [31] considered improper equivalence 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.
Another important research direction is to further investigate LwEQ-TD for more complex hypothesis classes, including DFA (deterministic finite automaton), NFA (nondeterministic finite-state acceptors), CFG (context-free grammars), among others. As a concrete hypothesis class, one could consider DFA2s (i.e., DFA with alphabet size 2 and state size s). For this hypothesis class, the query complexity is exponential in s when considering worst-case counterexamples [13]. [60] computed VCD for a variety of hypothesis classes including DFA2s; 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 DFA2s. As future work, it would be interesting to investigate LwEQ-TD for DFA2s. A concrete direction is to study the query complexity when providing more structured counterexamples (e.g., by picking minimal length counterexamples as considered in [12]) as this would allow establishing an upper bound for best-case counterexamples.

Review summaries:
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.   There 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).  The 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.  Finally, 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). 

The paper characterises the sample complexity of teaching in the learning with equivalence queries(LwEQ) model. The teachers can be  1) 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. 

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).  

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.