Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Originality:

Strengths:
1. The problem studied by the paper is interesting and fundamental. 
2. 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.

Quality:
The submission appears to be technically sound. Relevant related work is included in context.

Clarity:
The submission is very well written.

Significance:
Overall 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.
questions: -
limitations: Limitations are adequately discussed in the conclusions section.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The authors present a linear bound in terms of Vapnic-Chevronenkis
dimension, or VCD, for a model of batch "teacher-student"
learning. Note that in machine teaching is not a machine learning
problem: the question is for a concept, what is the smallest sample
size (from what I gathered, from a tutorial reference). This
information can still be useful in understanding difficulty of
teaching or learning of various concept classes. Previous linear
bounds were for sequential and not batch models of interaction. One
challenge is how to formulate the constraints so that the teacher and
student cannot collude (from my understanding, allowing a teacher to
potentially cheat and somehow encode information about the target
concept to the student). In this model of batch-teacher learning, the
authors' result is to have shown the first linear bound in terms of
VCD (previous results being Quadratic for the batch case, and only linear for the sequential).

strengths_and_weaknesses: Strengths:

--  Clarity of defining the problems, and the improvements in the bound.

Weakness:

-- The paper is highly abstract and the work is completely
 theoretical.  A theoretical machine learning venue is more
 appropriate.

-- Their notion of teachability, for a concept class, seems contrived,
 and, again, appears be of purely theoretical interest, currently.




questions: -- the first mention of 'coding tricks' in the introduction was
 unclear to me (a researcher who hadn't seen this framework). The next
 sentence and rereading the firt few pages give me an idea. You can
 preface by the 'coding tricks' sentence by one that .

-- My first impression: Shouldn't teaching lower the bound from VCD?
 (instead of being quadratic or even linear) Since the teacher is
 trying to be helpful! After reaching the paper, and a bit of the
 citations, I gather here the requirement in the problem formulation is higher, and the problem
 is not even an ml problem! (but some inverse of it!)

-- Preliminaries section: please reemphasize here that the definitions
 are for batch learning. (I assume that's the case, since sets of
 examples are provided from teacher to student)

-- For a more general audience, would be good to provide some concrete
 examples of what a concept class can be, etc. early in paper.


limitations: Not applicable.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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.

First of all, there is a nice review of known teaching dimensions suggested in previous papers - TD, RTD, NCTD, STD, and their properties. 
Then, the authors suggest 3 properties that a "reasonable" teaching model should satisfy - class-monotonicity, domain-monotonicity, and antichain property.
Moreover, the suggested parameter should violate criteria called "GM-collusion-free", in order to be of size linear in the VC dimension.

Following 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.
strengths_and_weaknesses: The paper (which is full of technical details) is clearly presented.

It is well-motivated why one would search for a new teaching parameter, by carefully reviewing the known parameters and their properties.

I think that there are potential implications of the ideas in this paper on learning and teaching.

Overall I find this paper very elegant and I recommend it for acceptance.

questions: -
limitations: -
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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. 

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

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

As for weakeness, what's unclear to me is, couple of things
a) 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?
b) 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. 

With 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.
strengths_and_weaknesses: Discussed above.
questions: Discussed above.
limitations: Societal impact of this work is not applicable. It is a theory paper.
review_title: null

Meta-review: metareview: The reviewers agree that this is a solid contribution. Please do revise the paper according to the reviewers comments and the discussion.
confidence: Certain
Decision: Accept