On Batch Teaching with Sample Complexity Bounded by VCD
Authors: Farnam Mansouri
Hans U. Simon
Adish Singla
Sandra Zilles
Venue: NeurIPS 2022 Accept (2022)
Keywords: Machine Teaching
VC Dimension
Collusion-Freeness

Abstract: In machine teaching, a concept is represented by (and inferred from) a small number of labeled examples. Various teaching models in the literature cast the interaction between teacher and learner in a way to obtain a small complexity (in terms of the number of examples required for teaching a concept) while obeying certain constraints that are meant to prevent unfair collusion between teacher and learner. In recent years, one major research goal has been to show interesting relationships between teaching complexity and the VC-dimension (VCD). So far, the only interesting relationship known from batch teaching settings is an upper bound quadratic in the VCD, on a parameter called recursive teaching dimension. The only known upper bound on teaching complexity that is linear in VCD was obtained in a model of teaching with sequences rather than batches.
This paper is the first to provide an upper bound of VCD on a batch teaching complexity parameter. This parameter, called STDmin, is introduced here as a model of teaching that intuitively incorporates a notion of ``importance'' of an  example for a concept. In designing the STDmin teaching model, we argue that the standard notion of collusion-freeness from the literature may be inadequate for certain applications; we hence propose three desirable properties of teaching complexity and demonstrate that they are satisfied by STDmin.

On Batch Teaching with Sample Complexity Bounded by VCD
Farnam Mansouri University of Toronto
Hans U. Simon
Max Planck Institute for Informatics hsimon@mpi- inf mpg.
frnm. www.mmannnsssieemm maansour@@gmall.commmm com
Adish Singla
Sandra Zilles University of Regina zi zillesccs. urwgina. ca
Max Planck Institute for Software Systems adi stssmiissssss.... org
Abstract
In machine teaching, a concept is represented by (and inferred from) a small number of labeled examples. Various teaching models in the literature cast the interaction between teacher and learner in a way to obtain a small complexity (in terms of the number of examples required for teaching concept) while obeying certain constraints that are meant to prevent unfair collusion between teacher and learner. In recent years, one major research goal has been show interesting relationships between teaching complexity and the VC-dimension (VCD). So far, the only interesting relationship known from batch teaching settings an upper bound quadratic in the VCD, on parameter called recursive teaching dimension. The only known upper bound on teaching complexity that is linear VCD was obtained in model of teaching with sequences rather than batches. This paper is the first to provide an upper bound of VCD on a batch teaching complexity parameter. This parameter, called STDmin. min- is introduced here as model of teaching that intuitively incorporates notion of "importance" of an example for concept. In designing the STDmin teaching model, we argue that the standard notion of collusion-freatt applications; we hence propose three desirable properties of teaching complexity and demonstrate that they are satisfied by STDmin-
from the literature may be inadequate for certain
Introduction
The notion of machine teaching refers to the selection of helpful training examples that aid the learner in identifying a target concept (Zhu et al. 2018). Such processes can make machine learning fcasible or economical situations when it is diffiultt or expensive to acquire large amounts of training data, Cluman-in-the-iie settings [Wang et al. 2020) or inverse reinforcement learning [Kamalaruban et al. 2019] are potential application areas of machine teaching. Formal studies teaching consider various teaching models, each of which has corresponding complexity parameter referring to the worst-case number of examples required to teach any concept given concept class [Goldman and Kearns 1995 Shinohara and Miyano 1991 Zilles et al.) 2011 Gao al. 2017b Kirkpatrick al. 2019 Mansouri al. 2019]. Each model has to adhere to rules that prevent teacher and learner from using unwanted "coding tricks", such as, for instance, agrecing
indexing of concepts and an indexing of data points, and then allowing the teacher to simply teach the concept indexed using the data point with index i. While no general notion of coding trick is agreed upon in the literature, Goldman and Mathias (1996) provided a notion of collusion-freeness (which we call GM-coollusoon-frcennss for short) that is often used underlying constraint in teaching models.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

One major line of research addresses the question of how teaching complexity parameters relate to one another and to other parameters of interest in computational learning theory, such as, for instance, the VC-dimension (VCD. Vapnik and Chervonenkis, 1971), the self-directed learning complexity [Goldman and Sloan, 1994]. the optimal mistake bound from online learning [Littlestone] [988]. or the size of sample compression schemes [Littlestone and Warmuth 1986]. Of particular interest is the question how teaching complexity relates to the complexity of learning from randomly chosen examples, and thus to the VCD [Blumer et al. 1989). Answers to this question provide insights into structural properties that make a concept class easy or hard to teach, and have implications on the design and analysis of teaching and learning algorithms. For example, it was established that the Recursive Teaching Dimension (RTD, Zilles et al.. (011) is upper- bounded by a function quadratic in VCD HHu et al. 2017]. While RTD may exceed VCD, it remains open whether it is in O(VCD). Connections between RTD and the size of an optimal sample compression scheme were also made [Doliwa al. 2014, Darnstädt et al., 2016). More recently, [Kirkpatrick al. [2099] introduced the No-Clash Teaching Dimension (NCTD), which is the optimal complexity of teachers satisfying En-coollsioo-frreness
Since the RTD model also satisfies GM-collusion- - NCTD is upper-
bounded by RTD and thus trivially inherits Hu et al.s upper bound quadratic in VCD. It remains unresolved whether or not NCTD S VCD holds in general; no counter-example has been found yet.
The models of RTD and NCTD represent teaching with batches (sets of examples). Naturally, a smaller complexity can be obtained when teachers encode concepts in sequences of examples. So far, the only known teaching complexity upper- boguded by VCD stems from a sequential model (Mansouri et al. 2019]. The main problem we address in this paper is to design a reasonable batch model of teaching that has a complexity upper-bounded by VCD.
While GM--ollusion-fii -rrenness- is often considered very natural condition on teaching, it has recently been argued that there are application settings in which this condition is not natural [Ferri et al. 2022) In addition, since the question whether NCTD S VCD is not yet resolved, and NCTD is the optimal complexity of GM-collusion-free teaching, our approach is to consider batch models that do not satisfy inl-collusion-freeeess but instead satisfy minimum postulates of teaching without "coding tricks". Our first contribution is to formally define three such postulates and to analyze some teaching models from the literature with respect to these postulates. We then define new batch teaching model that is not GM-collusion- free but provably satisfies our three postulates of teaching without coding tricks. Our main results that the corresponding complexity parameter is apper-bounded by both RTD and VCD. This makes our paper the first to provide an upper bound of VCD or O(CCD) on complexity parameter for batch teaching.
All proofs or parts of proofs omitted from the paper are provided in the appendix.
2 Preliminaries
Throughout this paper, the symbol X is used to denote any finite domain over which concepts, i.c.. subsets of X, are defined. A concept class over X is then a finite set of concepts over X. In the literature, any kind of finite or infinite set system can serve as a concept class; examples of finite concept classes are given in the form of tables throughout this paper. Often the concept classes studied are highly structured classes of Boolean functions, such as, for instance the class of all monomials over a fixed set of variables [Zilles et al., 201T]. Infinite classes of geometric concepts, such as hyperplanes in the Euclidean space, are often studied as concept classes as well; see, e.g., [Gao et al. b).7a|b)
If C' is any concept over X and & E X, then C(x) is the label of C for x, i.e., C(x) = 1 if E C, while C(x)) 0 if C. A labeled example for C is a pair (I, ((x)) for x E X. As this paper focuses on batch teaching rather than sequential teaching. teachers and learners are designed to operate with sets of labeled examples. Any set of labeled examples for C' is called a sample set for C. If C is concept class, C' E C, and S is a sample set for C, we say that 5 is a teaching ser for C' (wrt C) if it is not a sample set for any C' # C, C' E C. A teacher for C is a mapping T that assigns to every concept C E C sample set for C. Its order ord(T) is the size of the largest set in its range, i.e., ord(T)- = maxcec T(C)). J. A learner is a (not necessarily total) mapping that assigns concept to each sample set in its domain. A learner L and a teacher T are said to match on a concept class C, if L(T((C)) = C for every concept C E C. If C is a concept class over X and X" C X is any subset of the domain, then we use C( to denote the restriction of C to X', i...
2

---

Clx (Clx,] 1 C C), where C4x² is the projection of C' onto X'. We say that X' preserves C if C C2 implies Cixx C2lx whenever C₁ C2 E C. A concept class over X is succinct if is not preserved by any proper subset of X.
We now define various notions of batch teaching that have been studied in the literature, beginning with the classical notion of teaching dimension.
Definition 1 (Shinohara and Miyano| [191],, Goldman and Kearns 1995)) Let C be concept
class over a domain X and C E C be a concept. The teuching dimension of in C, denoted by TD(C,C) C), is the size of the smallest teaching set for C wrl C. The Teaching Dimension of C is defined as TD(C) := max max(TD(C,C)
C E C}. Moreover, TD I'min(C) == min(TD(C, C) C E C}. A TD-teacher for C is teacher that maps any C' & C to smallest teaching set for C.
TD-teacher matches every learner that outputs concepts consistent with the given sample set. The more recent literature proposes models in which "smarter" learners can be used. In recursive teaching, one exploits a canonical partial order over the concepts in the class: first, the concepts with smallest teaching dimension wrt C are encoded with their minimum teaching sets, then one removes these concepts from C and proceeds recursively with the remaining concepts, always encoding and removing the concepts that are "easiest to teach".
Definition 2 (Zilles et al. (201T) Let C. be a concept class over domain X. Let Cn C and recursively define C = -I E C. TD(C,C) = mT.)) as well as Ci+1 = Ci C.inn An RTD-teacher for C is a teacher T with the following property: for C E C.min, the set T(C) is teaching set for C wrt Ci. Then the Recursive Teaching Dimension of is defined as RTD(C) == max (TD (C.) i 0}, which equals the smallest possible order of any RTD-teacher for C. A recursive teaching plan for C is any sequence
((C,,) ( )...., (CK,,, .... ( T(C))))))
where T is an RTD-teacher, Ciuin (Ci, Cin. } for all i, and C C U U Criin
For finite concept classes, the notion of RTD coincides with the Preference-Bel Based Teaching Dimen- sion (PBTD) [Gao et al., 2017b), so our results will similarly apply to PBTD.
No-clash teaching is strictly more powerful than recursive teaching; here the only constraint on the teacher that no two concepts agree on the union of the two sample sets encoding them.
Definition (Kirkpatrick et al. [2019] Let C be a concept class over a domain X and T be a teacher for C. We call T non- clashing teacher -eeccere on C iff there are no two distinct C, C" E C such that T(C) is a sample set for C' and T(C') is a sample set for C. The No- Clash Teaching Dimension of C is defined as NCTD(C) min (T) T is an NCTDD-eacher on C).
not hard to show that TD 2 RTD 2 NCTD KKirkpttrick et al., 2019]. A batch teaching parameter that is incomparable to both RTD and NCTD is the so-called subset teaching dimension. In subset teaching, one considers all minimum-sii size teaching sets for each concept, and iteratively reduces them to minimum-size subsets that are not contained in any of the sets assigned to other concepts. The underlying idea that a learner can recognize a concept even by a subset S of a smallest teaching set if S is not subset of a set used for teaching another concept.
Definition 4 (Zilles et al. (211)) Let C be a concept class over a domain X, and C C. Define STS" (C,C) (1 C(z)) subset teaching sets as the collection that contains all smallest-size sets S that satisfy the following:
X}). For k N, iteratively define collection ST C) of
1. S' for some S' ESTS*(CCC):
2. S 2 S' for all S STS CC) where C' EC, C'
Let k* be minimal with STS* (Č,C) STS* (Cr all k > k2, CE C. An STD-teacher for C any teacher T for C with T(C) E STS** (C,C) for all I E The Subset Teaching Dimension of C, denoted by STD(C), is defined as STD(C) (Td(T) where T is any STD-teacher for C.
3

---

STD is well-defined since every STD-teacher for a class C has the same order, with all sets in STS* (C, being of the same size for any fixed C. Note that STS (C, C') consists of all minimum- size teaching sets for wrt C. In general, TD 2 STD. while STD and RTD are incomparable and either one of them can be larger than the other by an arbitrary factor [Zilles et al. 201T
STD is well-defined since every STD-teacher for a class C has the same order, with all sets in STS* (C, C) being of the same size for any fixed C. Note that STS (C, C) consists of all minimum- size teaching sets for C' wrt C. In general, TD > STD, while STD and RTD are incomparable and either one of them can be larger than the other by an arbitrary factor [iiles et al. 201T].
These teaching notions are illustrated with the help of Table which shows a concept class C3 Cpair with 16 concepts over a domain of size 11. We claim that TD(Cgur)) = 4, RTD(Cg = 3. NCTD(C) = 2, STD(C for any nwen-ne concept C2: contains only one example, namely for the instance zy; thus TD TDmin min (C 1. By contrast, the smallest teaching set for any odd-numbered concept C2i-1 1 contains labeled examples for the instances I;, Zy, I10, and 211- The last three instances are needed to distinguish C2i-1 1 from all other odd-numbered concepts, and x; is needed to distinguish C2i-1 from Czi. Hence TD(Cgar)) = 4. To see that RTD(C = 3, observe that a recursive teaching plan will first list all even-numbered concepts (whose TD is 1), and then has only the odd-numbered ones left, which correspond to the powerset on {Ig, T10, T11 J; clearly these will require a teacher to use sets of size 3. A non-clashing teacher of order 2 is indicated by the boldface labels in the table. One can argue (see the proof of Proposition [7p that no non-clashing teacher of smaller order exists, i.e, NCTD(C3 iteration of subset teaching, even-numbered concepts are assigned their unique teaching sets of size 1, while odd-numee concepts C2i-1 are assigned four-element teaching sets containing the example (xt, O). Since the latter not contained in a minimum teaching set of any other concept, in the next iteration, C2i-1 is assigned the subset teaching set { 0)}.
1, and TD TDmin (C3 1. Note that the smallest teaching set
2. Finally, SCD(C) = was shown by Zilles et al. [201] J; in the first
concept C3
Chass
J22
233
.4
255
2266
407
28
29
F10
2'11
C
0
C2
1
0
0
0
0
0
0
0
Css
0
0
0
0
0
0
0
0
1
Ca
0
Cs
0
0
0
0
0
0
0
0
0
1
0
Cs
0
0
0
0
0
0
C7
0
Cs
0
0
0
0
0
0
0
Co
0
C1o
0
0
0
0
0
C1
0
0
0
0
0
0
0
0
0
C12
0
0
0
0
C1a
0
0
0
0
C14
0
0
0
0
Cis
0
0
Cr6
0
0
Table 1: The concept class Chair [Zilles et al. 2011], for the case u = 3. The subset teaching sets
witnessing STD(C 1 are highlighted in blue. Non-clashing sets that witness NCTD(C S
2 are in bold font. The proof of Proposition 17 shows that NCTD(C = 2.
3 Desirable Properties of Teaching Models
Our goal find a "reasonable" batch teaching complexity measure that upper-bounded by VCD. Even an upper bound linear in VCD would be of significance; the best known upper bound on batch teaching complexity, terms of VCD, is the quadratic upper bound on RTD (and thus on NCTD) that was established by Hu et al. (017)) One important aspect in the design of "reasonable" teaching models how much to constrain the information exchange between teacher and learner. In an attempt to prevent unfair collusion between teacher and a learner, one limits their interaction by certain

---

constraints. While there is no general definition of what constitutes collusion, Goldman and Mathias [996] proposed a notion of collusion-freenes, that is often adopted in the literature:
Definition 5 (Goldman and Mathias (1996]) A teacher T and a learner L are Goldman-Mathitn (GM) collusion-free concept class C if. for every C' E C. and every sample set S for C, we have U(T(C)US)= C.
The intuition behind this notion is that the learner is not distracted when presented with additional information on the target concept, beyond the minimum information needed to identify the target concept. At the same time, this prevents certain "unfair coding tricks". For every concept class C, all TD-teachers, RTD-teachers, and -CTT--eacchrs can be matched with a learner in a GM- collusion-free way [Zilles et al. 2011 Kirkpatrick et al. 2019). In particular, NCTD(C)) corresponds to the smallest order of any teacher for C. that can be matched with a learner without GM-collusion [Kirkpatrick et al.] 2019]. By contrast, teachers and learners using subset teaching usually are not in general GM-collusion-free [Zilles et al. 2011].
As long as it is open whether NCTD is upper-bounded by (a function linear in) VCD, any quest for a measure of batch teaching complexity that is upper-boundeds by (a function linear in) VCD is forced to take a new route: it must consider batch teaching notions that violate the definition of ceoollusion-rreeeese since NCTD the optimal complexity of GM-collusion-fre teaching.
Ignoring GMMccollsionn-rreeeee has some practical motivation. The notion of wewolllusiooffreeesss is inherently limited in that it excludes learners that expect teachers to use only "important" informa- tion (for some notion of importance). If TCC) contains only "important" examples for C, while the sample S for C' contains "unimportant" examples, then a learner may be confused by the presence of S in its input T(C) U.S. If we want to permit superfluous information to have adverse effects in teaching, then we should not require GM-collusion -freeesssssi---eeeesss. As an illustration of the naturalness of such effects, consider a typical form of information exchange between a human teacher and learner in classroom. Suppose a teacher asks a student to prove Theorem X under premises A, B, and C. and suppose further the student comes up with proof of Theorem X that uses only premises A and B, but not the (consistent yet unnecessary) premise C. The student may then doubt their own proof, since they assume all the information provided by the teacher to be "important". This is in line with recent research on machine teaching. Ferri et al.) 2022] argued that it not in general unnatural for a learner to change its mind when receiving data that is consistent with the previous hypothesis. Their model allows additional information to decrease the probability that the current hypothesis is really correct, and to make an alternate consistent hypothesis appear more likely. This point of view challenges the widely-held belief that natural teaching and learning should be GM-collusion-fre
Consider for example the class in Table Here, C1 and C2 differ only in ø1. The smallest teaching set for C1 uses four instances (I1, Zg. F10- and In1). but a learner expecting the teacher use "important" examples might infer C1 from the information (x1, 0): while there are 15 concepts consistent with this example, C1 the only one for which this information is "important", as it the only concept in the class for which this example occurs in smallest teaching set. An STD-teache will use the singleton set { 0)} to teach Ci, and has an order of on this concept class. By contrast, no GM-collusion-free teacher/learner pair can succeed with just a single example, since the NCTD, which is known to be optimal in terms of GMM-cllusion-frre teaching, is greater than 1.
Rather than defining a weaker notion of callusion-frreness we propose to consider desirable properties of teachers and learners, which could be used as postulates for reasonable models of teaching and learning. Depending on the application setting, one may require additional properties.
Two of our intuitive postulates concern monotonicity of a teaching complexity measure. First, for every concept class C one might want every superset of to be at least as hard to teach as C, i.e., the teaching complexity of concept class should be no smaller than that of any of its subclasses. Second, one might require that removing instances from X without reducing the number of concepts should not decrease teaching complexity, because the removed instances may have been helpful but not harmful in teaching. Both these monotonicity postulates are captured in the following definition.
Let Z be any function that assigns a non-negative integer to any concept class. We say that 2 is class- monotonic, if Z(C') 2 ZC) whenever C, C' are concept classes over the same domain X, and
Definition 6 (Postulate 1 (Class-Monotoniccts and Postulate 2 Doomain-Monotonicin
5

---

C C C. We say that Z is a domain X, and X X a subset that preserves C.
if Z(C)x) 2 Z(C) whenever C is concepr class over
Our third postulate at first glance appears similar to GM-collusion-freenees It states that a teaching set for a concept C should not be contained a teaching set for another concept C'. Intuitively, teaching set TC)) for C' must contain enough "important" examples for C such that any concept C" + that is consistent with T(C) will be missing at least one of these "important" examples its own teaching set. In other words, for every C' * C at least one example in the teaching set for C' is "unimportant" for C" or inconsistent with C².
Definition 7 (Postulate 3 (Antichain Property)) A teacher T has the antichain property (is antichain teacher) for a concept class C if C, C" E and C C = T(C) & T(C').
We will sometimes say that a teaching complexity notion satisfies the antichain property if all teachers following the corresponding model are antichain teachers. For example, since every TD-teacher is an antichain teacher, we say that TD satisfies the antichain property. easy to see that also STD satisfies the antichain property. Moreover, every RTD-teacher (NCTD-teache)) can be normalized an -tacher see the supplementary material for proof.
resp.) of the same order that also satisfies the antichain property;
Proposition 8 Let C be any concept class, E (RTD, NCTD), and T any Z-teacher for C. Then there is Z-teacher T' for C with ord(T') = (Td such that T' has the antichain property.
An interesting natural (yet non- non-trivial) property of optimal antichain teachers that their order for the powerset Pn, n instances is linear in n. (The proof, given in the supplementary material, relies on the theory of bipartite matching.)
Theorem Let T be antichain teacher Pn and suppose (Td) S <Tr for all antichain teachers T for Pa- Then, for all but finitely many n,, we have 0.22 n < ord((T") < 0.23 n.
When teaching with sequences, the sample complexity for Pn may be as low as O log al. 2019]; "natural" batch teaching models thus need strictly larger sample sets.
Mansouri
To sum up. our goal is to design a measure of batch teaching complexity that is upper-bounded by (a function linear in) VCD and satisfies the postulates of (i) domain monotonicity, (ii) class- monotonicity and (ii) the antichain property. Since we need to focus on complexity notions violating first natural candidate is STD. However, STD not even upper-bounded by polynomial in VCD [Ziles et af.] 2011]. Moreover, while it satisfies Postulate 3, violates both Postulates and 2. The class in Table 1 witnesses that STD is not dass-monotonie satisfies STD = 1, while its subclass of odd-numbered concepts has STD = 3. This generalizes as follows:
CMM-collusion-freenss
Proposition 10 Ziilles et (2011) STD is not class-monotonic. In particular, for every n > there is concept class C with a sub-class C' such that STD(C) = 1, while STD(C") = n.
Proposition 11 STD not domain-monotonic. In particular, for every n 3, there concept class C over domain X = U'UX" X" such that STD(C) = - while STD(CLx)) =
4 A Variant of STD
Our main contribution is introduce built on the idea of STD, yet satisfies the two postulates defined Section 3 Moreover, we will show that it is upper-bounded by VCD. This makes STD the first known complexity parameter for batch teaching that is proven to be upper-bounded by (a function linear in) VCD.
teaching complexity parameter called STD which
In calculating STD(C,C) C), at stage k- + 1 one maintains the collection of all minimum-size subsets of sets for C' from stage that are not subsets of sets for any other C' at stage k. STD at every stage we pick only one subset, but do not require it to be minimal.

---

Definition 12 Let be a concept class over a domain X. A sequence T = (Tk)keN of teachers for is called subset teaching sequence for C if. for all C C and all & N:
To(C) {(x, C(x)) ( xE
(C) C Tx(C),
Tk+1 (C) & ( for all C' E C, CC.
Let k2 N be minimal with Tc(C)= = (C-(C)
((C))e for all k k- and all C. Then Ty- is an STDmin -teccer for C and we define the order Tf C as ord(T) ord(Tx-). Finally, define
STD min(ord(T) T is subset teaching sequence for C}.
Definition 13 Let C be concept class domain X. sequence T (Tk))EN of teachers for is called subset teaching sequence for C if. for all C C and all l N:
To(C) = {(x, C(x)) x xE
TC+1(C) c Tx(C),
TC+1(C) E Tx(C') for all C' EC, CC
Let ke E M be minimal with (c(C) = Tk- (C) for all k > k and all E C. Then Tg. is an STD mieecheteache for C and define the order T C as ord(T) = oTd(TT-)) Finally, define
STD min (C) min T is subsel teaching sequence for Cj.
Observation 1 Every subset teaching sequence of order d can be transformed into a normalized sequence (Th keN of the same order, where normalized subset teaching sequence has the property that, for every k <, k* and every C E C, we have (i) Ta+1 differs from T3 on exactly one concept, (ii) (Tx+ E (IT&(C) - Ta (C)),, (ii) (T&(C)) 2 d, which implies that (Te. (C) = d.
Before showing that STDmin satisfies our desired properties, we claim that STD is upper-bounded by STD and can be arbitrarily smaller than STD (the proof is in the supplementary material);
Proposition 14 STD min (C) < STD(C), and for all n E N there is some succinct C, such that STD min (Cn) and STD(C)
Since STDmin STD and STD can be smaller than NCTD, which is the best possible complexity of GM-collusion-free teaching and learning, we immediately obtain:
Corollary 15 There are concept classes for which no teacher of order STDmin can be matched with learner GM-collllle MMM-collssion-rre way.
Next, we claim that STDmin also meets Postulates and 2, and thus greatly improves on STD in terms of the postulates defined in Section 3 see the supplementary material for proof.
Proposition 16 STD is class-monotonic, domain- and satisfies the antichain property.
5 Relationship of STD, min to Other Complexity Parameters
We already know that STD min is upper-bounded by TD and STD. Subsequently, will show that, for finite concept classes, it is also upper-bounded by RTD and by VCD, but not by NCTD. Most importantly, our results make STD min the first known parameter for batch teaching complexity that known to be upper-bounded by VCD (or even by a function linear in VCD), for finite classes. We first show that STDmmi be arbitrarily smaller than NCTD, but also by factor of 2 larger than NCTD. The proof, which is detailed in Appendix ??, uses generalization of Cpair from Table
Proposition 17 For every NCTD(C) nı (ūi) a concept class C with STD(C) = STD (C) and NCTD(C) =
there is (i) a concept class with STD(C) STD min (C) 1 and
Theorem 18 Let C be any concept class. Then STD min (C) < RTD(C).
7

---

Proof. Let ((C1, (C,, ......... (Cn, T(C.)) be recursive teaching plan for C. In particular, we have C (C....., G. [C| n, and, for all i fI.....n.. n), the set T(C;) is a teaching set for C₁ with respect to (C, j 2 i]. Moreover, max; (T(])] = RTD(C). We will use this recursive teaching plan to construct a subset teaching sequence of order at most RTD(C) for C.
First, for all C' E C, define To (C') as per Definition 13 Second, define Ti by setting Ti (i = T(C1)
and Ti (C2) [C;) for all j > Since T(C a teaching set for C1 wrt [C; 1 1]. we have that Ti (C1) @ To(C;) for all j + 1, so that T'i satisfies the requirements of Definition 13 Moreover, [Ti [Ci(C)) S RTD(C). Next, we define Ta for & > 1 by the following algorithm.
1. For j k, let
= 1
2. To define Ty. (Cx), initialize Tx(Ck) := T(C+).
3. Let J/z := [j * k (Cx) (T,))(C))).
4. If JA = 0. then stop and output (Ck)).
5. Let == min JR. Pick any (e. E (T.)(CG))) such that (x #
6. Let (C+) := (Cx)) U [Ir, Cx(x))
7. Goto step 3.
Obviously, Ta (Ck) C (CE))(C)) To complete the proof of Theorem (C) for all C + CR. C' C and that [Cx(C S RTD(C).
18 we show that (Cx) g
Note that [T(C)] < <RTD(C) for all j; thus [Ti(Ci) S RTD(C). If JR is initially empty, then also [T&(C < RTD(C), and, by definition of J3 we have (Ck) g Tk-1(C) for all C' * Cs.. So suppose Jg not initially empty. Since Ti (C+) 2 T(C2) at any point in time during the construction, and T(C₁) is a teaching set for Cs wrt {C, J 2 k),, we have j < k for all E J/. at any point in T(C,-): in particular, (C,) is a teaching set for Cj- wrt {C; 1 2 5n). Hence there exists some (x,1) E (C,)(C)-) such that (x) + 1. Thus, step guarantees that (Cx) & the next iteration of step 3. This way, eventually (Cx) & (C) for all C & Cz.
time. Now let j" == min Jg. By construction, Tc-1(C,-))
(C,)(C and at least j removed from J3 at
All that remains to be shown is that [Tx (Cx) S RTD(C). We do this by proving inductively for all k: that (Tx(C,) < RTD(C) for all j S k. Note that the latter holds true for h: = 1. Assuming we have proven Tx (C,) < RTD(C) for all j S k- 1, we claim that step 6 will only add an element to (Cx) < RTD(C)- - 1. For step 6 to add an element to T3 (C&),, there must be (at that if (Cx)
such that (Cx) _ [C,)( Since (C is a teaching set for Cy- wrt {C, j 2 j" j") the set T (C,) ) is inconsistent with Cs. In particular, (Ck) is a proper subset of Tf (C--). By induction hypothesis, (C,)) RTD(C). Hence, (Cx)) S RTD(C) 1 before step 6 adds an element to TC(C)..
point in time) jj"
In the sum, we have verified that (Ths )EEN is subset teaching sequence for C and that its order is most RCD(C). Thus STDmin (C) < RTD(C).
The main result of this section establishes STDmin as the first notion of batch teaching complexity for which VCD is provably an upper bound.
Our proof of this result relies on the recursive decomposition of a concept class, as exploited by (Floyd and Warmuth 1995] and in the proof that VCD can upper-bound the sample complexity of sequential teaching Mansouri et al. 2019). If is a concept class over X and x E X any element of the domain, then we use C₂ denote Cl (x]. (x)) and C* to denote {C E C. CU E C and C C).
Floyd and Warmuth call C₂ the restriction and C the reduction of C wrt x. It is easy to see that VCD(C,) VCD(C) and VCD(C*) VCD(C) - 1 (Floyd and Warmuth 1995..
Theorem 19 Let C be any concept class. Then STDmin (C) S VCD(C).
Proof. Let = VCD(C) 1. Pick some x= X. We may assume inductively that the assertion of the theorem is true for the classes Cz. and C=" Let Trest = ) be any subset teaching sequence for Cg- with ord() = d. Here kiest denotes the maximum number of iterations red takes converge on any concept in Cy., Further, let 7 = ) be any subset teaching sequence for C=" with ord(7 = 1. Here kind denotes the maximum number of iterations ' takes to converge. Since any subset teaching sequence can be normalized, it can be assumed in the sequel that the sequences T and Tnd have the normalization properties (i) (i)- as in Observation I Now define subset teaching sequence T = (Ti) (EN) for C as follows.
8

---

I }). From now on, we use C :X to denote the set of concepts C' C for which there is some C' E C such that C' and C" differ only in the value of x². (Note that C= has twice as many concepts as C* and its restriction wrt x" yields C*
For all C' E C initialize To(C): :- [2,, C(x))
((x)(())
Stage 1. Let k E [1, kiee + 11. For all C' E C=*, .X set Ta(C)) T (Clx)(e))) 1) C(x")))
For all C E C C" set (C(C)= == {(11, C(x)) | x E {x")]]
Stage 2. Let & E [Kred + +2 kined + kirest + 11. For all C E C let Ta(C)= Tc-1(C). For all C' CEC\ C 'X, let (e(()(C)== T k- - (Cbx)((+)))
We claim that (aa) is subset teaching sequence for C and has order at most d.
First, we show that the partial sequence defined in Stage is valid, i.e., for all k S kred + 1 and all
C, E C with C' * C' we have (c) S TC) and T3 (C) & Tk-1 (C"). The fact (C)) S
TC-1 is inherited from the same fact for the sequence 7 To show that (C) & (C") consider multiple cases, If C, C² E C²= ,X this property again inherited from 7 If C X
and C² & C²',X" then (a", O(x*)) E (C) \ TK-1 (C") when A >> 1, while for k == 1 the property Tc(C) E (C") is valid because [C) = (C).). If C' & C then C' and C' must differ on some instance x & x"; since Ti(C)) contains (z, C(z)), again we obtain (C') g TC"1(C").
Second, we show that the partial sequence defined in Stage 2 is valid extension of that defined in Stage 1, i.e. for kred + 2 S k I kied + Arest + 1 and all C, C' E C with C" + C we have (C) S Tk- (C) and (C) E (C"). So, fix C and C" * C. For C E C ,X the sets defined in Stage 1 do not get updated in Stage 2. Hence we may safely assume that C & C . (C) S (C) is inherited from the same property for T If C' & c²",", then the analogous remark applies to Ty (C) E (C"). Suppose now that C² E C" X Here we make use of the normalization properties (ii). In Stage 2, all sets (C") with C' C ,X are of size d while all sets (C) with C & C='.X are of size at least d. Since Ti-1 (C') contains (x", C(x*))) it is not subset of Te (C). Together with [T&(C)] 2 (T- (C"),, it now follows that (C) g T (C"). Consequently, T is a subset teaching sequence for C. The identity ord(T) = d is obvious.
6 A Note on Unambiguity in Teaching
While STD meets our objectives outlined earlier, it loses one potentially desirable property of STD that has not been addressed in the literature before. For every teaching model defined above, there are concept classes which can be taught with more than one teacher satisfying the requirements of the model. Suppose Teacher I teaches concept Ci E C using sample set S, while Teacher teaches concept C2 E C, C2 & C1. with S. If the learner knows that she is interacting with some teacher of a given model, but doesn't know which one, she then cannot disambiguate between C1 and C2 when given input S. In unambiguou teaching models, the learner can infer the target concept from the given sample set without being told with which of the multiple valid teachers she interacting.
Definition 20 Let Z E (TD, RTD, NCTD, STD,STDmin } be a teaching complexity parameter. We say that Z is unambiguous concept E C such that some Z-teacher T of order ZC) satisfies TCC) = S.
concept class C, if. for every sample set S, there is at most one
If Z is ambiguous on a concept class, then one would have to normalize Z --teachers or use disam- biguating information. One disadvantage of STDmin compared to STD is the loss of unambiguity.
Theorem 21 TD, RTD, and STD are unambiguous on every concept class, while there are concept classes on which NCTD and STD min are not unambiguous.
Proof. Let C be any concept class and S sample set. If a TD-teacher T maps C to S, then S is a teaching set for C and thus cannot be mapped to any other concept by any TD-teacher T". If an RTD-teacher T maps C to S and C' E Cumin then S is inconsistent with the concepts in C' E C. \ (C) and thus cannot be mapped to the latter. The concepts in C \ C, cannot be mapped to S by any RTD-teacher either, since they must be mapped to sample sets that are inconsistent with all concepts
Note that, for all C C=' we have that (C) still equals (C).
9

---

in C' E C. which includes C. If an STD- T maps C' to S, then S E STS* (C,C). Since the latter is disjoint from S E STS** (C", C) for all C' + C. no STD-teacher can map such C' to S.
of order for P2 that even have the same range, one maps 0 to ( ( and { to {(12, 0)}, the other one does the opposite. A concept class on which STDmin is ambiguous is Warmuth's class (Doliwa et al.) [014], which is known as the smallest class which RTD exceeds VCD. For details, we refer to the supplementary material. D
is easy to see that there are two
The ambiguity observed for Z (NCTD, STDmin) stronger than the negation of the condition in Definition 20 Ambiguity means that multiple optimal Z-teachers map two different concepts to the same teaching set. But even happens that two optimal Z-teachers Ti * T3 have exactly the same range R = (C) C E C = (T2(C) C C). while assigning the sample sets in R differently to the concepts in C. The ambiguity of STDmin can take extreme forms for artificially created concept classes that have many redundant instances, as discussed in the supplementary material.
7 Conclusions
In an abstract setting, devoid of any specific application, it is not straightforward to define what makes a teaching/learning model "natural". We addressed this problem by considering various properties of teaching that one might find desirable; one can then design models that possess (some of) these properties as seen fit in an underlying application setting. We have introduced some such properties, here called "postulates", which are fulfilled by STDmin- Another property of STD that is not fulfilled by TD, RTD or NCTD, is that it allows the learner to discard a hypothesis because the given data is not important for that hypothesis (even if it is consistent). We argue that learner who knows that data comes from a helpful teacher, has reasons to reject hypotheses for which the data is not important/helpful. Of course, there may be other natural properties that are not fulfilled by STD An interesting research question is what natural properties can (or cannot) be fulfilled by teaching models whose parameter is upper-bounded by VCD.
This paper is the first to provide an upper bound of VCD on batch teaching complexity. Our results and proofs may have implications on the design and analysis of teaching and learning algorithms. For an overview of most of our results, see Table 2 While we diverted from the notion of GM- collusion-freeness, we hope that the postulates
teaching that we defined, as well our notion of unambiguity, will be useful for future studies on machine teaching. In particular, noting that neither NCTD nor STD min satisfy the notion of unambiguity, one may ask the question whether ambiguity is inherent in "natural" teaching models that yield a complexity upper-bounded by VCD. All unambiguous models studied in this paper have complexity that sometimes exceeds VCD.
Property
TD
RTD
NCTD
STD
STD min
GM-collusion-freee freeness (Goldman and Mathias 1996
yes
yes
yes
no
no
P1 class-monotonicity
yes
yes
yes
no
yes
P2-
yes
yes
yes
yes
P3 antichain property
yes
yes
yes"
yes
yes
unambiguity
yes yes
no
yes
no
RTD
yes yes
yes
VCD
no
no
no
yes
polynomial in VCD
no
yes yes
no
yes
Table Comparison of teaching complexity notions. Contributions from this paper are highlighted in bold. Note that class-mmnttonicity was already discussed by Zilles et al. [2011]. The asterisks indicate that RTD- and NCTD-teache can be normalized to antichain teachers, see Prop. g
Acknowledgments and Disclosure of F Funding
This research was conducted while S. Zilles was visiting scientist at the Max Planck Institute for Software Systems. Further, S. Zilles acknowledges financial support by the Natural Sciences and Engineering Research Council (NSERC) of Canada, both through the Canada Research Chairs program and the Discovery Grants program. She was also supported through the Canada CIFAR Al Chairs program Affiliate Chair with the Alberta Machine Intelligence Institute (Ami)).
10

---

References
A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Learnability and the Vapnik- Chhrik-Chevvoenniis dimension. JACM, 36(4):229-963 1989.
M. Darnstädt, I. Kiss, H. U. Simon, and S. Zilles. Order compression schemes. Theor Comput. Sci., 620:73 90, 2016.
Doliwa, G. Fan, H. U. Simon, and Zilles. Recursive teaching dimension, VC-dimension and sample compression. J. Mach. Learn. Res., 15:3107-31311 2014.
C. Ferri, Hernández-Oralle and Telle. Non-cheating teaching revisited: A new probabilistic machine teaching model. In Proceedings of International Joint Conference on Artificial Intelligence (IJCAI). 2022.
Floyd and M. Warmuth. Sample compression, learnability, and the Vapmik-Chervonenkis dimension. Machine Learning, 21(3):1-36, 1995.
Z. Gao, D. G. Kirkpatrick, Ries, H. Simon, and S. Zilles. Preference-basel teaching of unions of geometric objects. In Proceedings of the International Conference on Algorithmic Learning Theury, ALT 2017, pages 185-207,,20 2017a.
Gao, Ries, H. U. Simon, and Zilles. Preference- based teaching. J. Mach. Learn. Res., 18(31)11-32, 2017b.
A. Goldman and M. Kearns. the complexity teaching. J. Comput. Syst. Set., 50(1):20-3,, 1995.
A. Goldman and H. D. Mathias. Teaching smarter learner, J. Comput. Syst. Sci., 52(2):255-267, 1996.
S. A. Goldman and R. H. Sloan. The power of self-directed learning. Machine Learning, 14(1):271-294, 1994.
L. Hu, R. Wu, T. Li, and L.. Wang. Quadratic upper bound for recursive teaching dimension of finite VC classes. In Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017, pages 1147-1156, 2017.
P. Kamalaruhan, R. Devidze, V. Cevher, and A. Singla. Interactive teaching algorithms for inverse reinforcement learning. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (ICCAI), pages 2692-2700, 2019.
Kirkpatrick, U. Simon, and Zilles. Optimal collusion-free tcaching. In Proceedings of Machine Learning Research (ALT2019), volume 98, 2019.
N. Littletonee. Learning quickly when irrelevant attributes abound: new linear threshold algorithm. Mackine Learning, 2(4):245-318 1988.
N. Littlestone and M. K. Warmuth. Relating data compression and learnability. Technical Report, UC Santa Cruz, 1986.
Mansouri, Chen, A. Vartanian, J. Zhu, and A. Singla. Preference-basee batch and sequential teaching: Towards a unified view models. Advances Neural Information Processing Systems 32, pages 9199-9209, 2019.
A. Shinohara and Miyano. Teachability computational learning. New Gen. Comput., 8:337-348, 1991.
N. Vapnik and A. Chervonenkis. the uniform convergence of relative frequencies of events to their probabilities. Theor. Probability and Appl., 16(2):264-288 1971.
Wang, Wang, P. Paranamana, and P. Shafto. mathematical theory of cooperative communication. In Advances Neural Information Processing Systems, volume 33, pages 17582-17593, 2020.
Zhu, A. Singla, Zilles, and A. Rafferty. overview of machine teaching. CoRR, abs/1801.05927, 2018.
Zilles, Lange, Holte, and M. Zinkevich. Models of cooperative teaching and learning. Mach. Learn. Res., 12:349 384, 2011.


Reviews:
[{"review_id": "fcfHhTO26n_", "reviewer": "Reviewer_Rn8w", "summary": "The paper discusses the model of batch teaching, and seeks a reasonable batch teaching complexity measure that is upper bounded by a linear function of the VC dimension, which is a parameter that controls the sample complexity of learning in the PAC model.\n\nFirst of all, there is a nice review of known teaching dimensions suggested in previous papers - TD, RTD, NCTD, STD, and their properties. \nThen, the authors suggest 3 properties that a \"reasonable\" teaching model should satisfy - class-monotonicity, domain-monotonicity, and antichain property.\nMoreover, the suggested parameter should violate criteria called \"GM-collusion-free\", in order to be of size linear in the VC dimension.\n\nFollowing the above, the authors suggest a parameter called STD_min (and explain why the other parameters \"fail\"). This parameter satisfies the 3 criteria and is of the size of the VC dimension. On the negative side, this parameter loses a desirable property of unambiguity.", "questions": "-", "limitations": "-", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper (which is full of technical details) is clearly presented.\n\nIt is well-motivated why one would search for a new teaching parameter, by carefully reviewing the known parameters and their properties.\n\nI think that there are potential implications of the ideas in this paper on learning and teaching.\n\nOverall I find this paper very elegant and I recommend it for acceptance.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "VEvB_dp5Dwh", "reviewer": "Reviewer_nVaX", "summary": "The authors present a linear bound in terms of Vapnic-Chevronenkis\ndimension, or VCD, for a model of batch \"teacher-student\"\nlearning. Note that in machine teaching is not a machine learning\nproblem: the question is for a concept, what is the smallest sample\nsize (from what I gathered, from a tutorial reference). This\ninformation can still be useful in understanding difficulty of\nteaching or learning of various concept classes. Previous linear\nbounds were for sequential and not batch models of interaction. One\nchallenge is how to formulate the constraints so that the teacher and\nstudent cannot collude (from my understanding, allowing a teacher to\npotentially cheat and somehow encode information about the target\nconcept to the student). In this model of batch-teacher learning, the\nauthors' result is to have shown the first linear bound in terms of\nVCD (previous results being Quadratic for the batch case, and only linear for the sequential).\n", "questions": "-- the first mention of 'coding tricks' in the introduction was\n unclear to me (a researcher who hadn't seen this framework). The next\n sentence and rereading the firt few pages give me an idea. You can\n preface by the 'coding tricks' sentence by one that .\n\n-- My first impression: Shouldn't teaching lower the bound from VCD?\n (instead of being quadratic or even linear) Since the teacher is\n trying to be helpful! After reaching the paper, and a bit of the\n citations, I gather here the requirement in the problem formulation is higher, and the problem\n is not even an ml problem! (but some inverse of it!)\n\n-- Preliminaries section: please reemphasize here that the definitions\n are for batch learning. (I assume that's the case, since sets of\n examples are provided from teacher to student)\n\n-- For a more general audience, would be good to provide some concrete\n examples of what a concept class can be, etc. early in paper.\n\n", "limitations": "Not applicable.", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n--  Clarity of defining the problems, and the improvements in the bound.\n\nWeakness:\n\n-- The paper is highly abstract and the work is completely\n theoretical.  A theoretical machine learning venue is more\n appropriate.\n\n-- Their notion of teachability, for a concept class, seems contrived,\n and, again, appears be of purely theoretical interest, currently.\n\n\n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "SKCFJrL5Oou", "reviewer": "Reviewer_47WT", "summary": "The paper investigates the problem of machine teaching - the ability to cast the interaction by a teacher (who is using labelled instances to teach a concept) and a learner in a way that obtains small complexity in terms of the required labelled examples. The authors suggest and analyzes a new batch teaching complexity measure they term STD_min, and show that while having several desirable properties (instead of the standard in the literature requirement of collusion-freeness), it may be upper bounded by the VC-dimension of the concept class being taught. In doing so, the paper provides the first measure of teaching complexity that is bounded (or is even linear in) the VC-dimension of the concept class.", "questions": "-", "limitations": "Limitations are adequately discussed in the conclusions section.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality:\n\nStrengths:\n1. The problem studied by the paper is interesting and fundamental. \n2. The work suggests a new measure of the teaching complexity, while showing it has desirable properties (which replace the standard in the literature collusion-freeness assumption, for which the authors also provide practical motivation), showing an upper bound of it by the VC-dimension.\n\nQuality:\nThe submission appears to be technically sound. Relevant related work is included in context.\n\nClarity:\nThe submission is very well written.\n\nSignificance:\nOverall I feel this is a strong paper. I do not actively conduct research in this sub-area, so very accurate assessment of the impact is a bit difficult for me. However, by reading and understanding the related work as it appears in the submission, and the suggested contributions, the results seem novel and significant.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "DZ84dxOzPtJ", "reviewer": "Reviewer_hi6B", "summary": "In this paper the authors make progress towards the question of relating passive learning and active learning. A long-standing open question in this area is the relation between recursive teaching dimension (RTD), which in a way characterizes the number of labelled examples sufficient to learn a concept class, and VC dimension (VC) which characterizes the number of random labelled examples sufficient to PAC learn the concept class. The best known upper bound in this direction is RTD < VC^2 for every concept class and we do know of some small-sized concept classes (say on 10 bits) for which RTD >= 2 VC. The opimal relation remains open and has applications to sample compression of learning. \n\nIn a single line, the main result of the paper is proposing a new combinatorial quantum STD_min, which is smaller than RTD and for this new quantity they show that STD_min <= VC. \n\nThe main strength of this paper is, the authors have been able to understand this property called GM Collusion freeness (here GM stands for initials of authors in a prior paper) which is a property of learning. In this direction there has been one combinatorial parameter  NCDIM which satisfies GM collusion freeness and its open if NCDIM <= VC. It was so far believed that GM collusion freeness is a necessary property in order to for a parameter to be upper bounded by VC. In this paper the parameter constructed by the authors STD_min is  not GM-collusion-free and yet is upper bounded by VC dimension. I find this a cute structural property that the authors have observed.\n\nAs for weakeness, what's unclear to me is, couple of things\na) How artificial is STD_min? In the sense, is it such a restricted model of active learning which *allows* to be upper bounded by VC dimension or is there something natural about this combinatorial parameter?\nb) One of the solid motivations of understanding RTD versus VC is sample compression schemes for learning. Its not at all clear to me if this new relation of STD_min < VC can help understand sample compression or not. \n\nWith this in mind, I think this paper would be a boderline/weak accept for NeurIPS: it makes a nice contribution in a hard open question but the main contribution might be overall contrived and not help resolve the open question completely.", "questions": "Discussed above.", "limitations": "Societal impact of this work is not applicable. It is a theory paper. ", "rating": 7, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Discussed above.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["Responsible Research Practice (e.g., IRB, documentation, research ethics)"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept