Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the equivalence query learning model where the teacher presents counterexamples if the learner proposes an incorrect hypothesis.  Three types of teachers are considered: (1) the "worst-case teacher" that presents adversarial counterexamples, (2) the "random teacher" that presents random counterexamples and (3) the "best-case teacher" that presents counterexamples designed to guide the learner towards the correct hypothesis in as few learning steps as possible.  Further, the query learner is equipped with a preference function on which the choice of its query depends (if its current hypothesis is incorrect).  
main_review: The study of equivalence query learning with helpful teachers seems to be a natural follow-up to previous work on algorithmic teaching and I think the present work is a good starting point.  

Comment:

- Supplementary, page 17, line 642: Why does $\ell_{max-min}$ pick the middle threshold function for querying?  I think this point needs more justification.  I tested this observation on some values, specifically for $n = 20$ and $n = 10$, and the claim seems to be almost correct except that the all-zero concept or all-one concept maximize $E(h,h')$ when the current version space contains these two concepts.  

Minor comments/suggestions:


- Page 6, Definition 4.1: Is the input space {${1,...,n}$}$^d$ or {${1,...,n+1}$}$^d$?  In the definition, $x$ is a point in this space with coordinates up to $n+1$, not $n$?


- Page 8, line 327: collude -> colluding

- Page 10, reference [17]: Missing space between 'V' and 'N'.

- Supplementary, page 17, matrix between 638 and 639: Why is the subscript of h in the last row $T$ and not $n+1$?  Similarly for the matrix between lines 641 and 642.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: 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. 
main_review: The paper is well written and quite readable. The definitions and the concepts are laid out cleanly.


Weakness:
1) The conjecture in the conclusion (regarding DFAs) needs more discussion. What is the intuition behind the suggested bound? 
2) The paper cites a number of works that study teaching complexity(TD) in the learning-from-samples(LfS) setting.  Although this shows the importance of TD in the LfS setting, it does not say much about the importance of TD in the LwEQ setting. It would be interesting to see a more thorough discussion about the same.
3) The authors chose 3 hypothesis classes, and in all of them, the teaching complexity is in {1,2}. This does support the intuitive point of the paper that optimal teachers are powerful. However, it would be interesting to see some more complex hypothesis classes with non-trivial lower bounds on the teaching complexity. For example, as written in the conclusion, the problem of determining TD for CFGs and DFA/NFAs is quite intriguing. 

Minor Comments:
1) (line 36) Do you mean a more benign teacher?
limitations_and_societal_impact: Yes, the authors do discuss the relevant limitations.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This work studied the problem of learning from equivalence queries (EQ) alone where counterexamples are selected by a helpful teacher. The paper characterizes the teaching complexity for different classes and relates the new notion (LwEQ-TD) to different notions in the literature. LwEQ-TD showed significant savings in the complexity of teaching when compared to other teaching notions in some hypothesis classes. 
main_review: This work proposes a new teaching notion called LwEQ-TD for learning from equivalence queries (EQ) only where counterexamples are carefully selected by a teacher. The main strength of the work is that it goes beyond the classical paradigm of *learning from samples* teaching notions (defined as LfS-TD) and characterizes LwEQ-TD when having different learners and loss functions. 

The paper also discusses how LwEQ-TD is related to different notions in LfS-TD such as TD/RTD/ PBTD given a holistic view on different teaching models and notions, which is highly needed with the increase interest in the theories and applications of machine teaching. However, the paper is very condense in its content, proofs, and theorems. Indeed, the work provides new insights and results from a learning theory perspective albeit their practical implications are not very clear. Moreover, learning from EQ alone is not practical in many applications, this needs to be motivated in the context of LwEQ-TD as the cognitive burden of answering one EQ is arguably higher than other types of queries. 


limitations_and_societal_impact: This work is theoretical
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This work studies the sample complexity of machine teaching finite hypothesis classes with equivalence queries (EQ), a model in which the learner queries hypotheses in the concept class directly, and the “teacher” responds “yes” or “no” along with a counter-example with the goal of eventually teaching the learner some ground truth concept. 

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

main_review: This work introduces an original model of machine teaching that is both combinatorially natural, and well motivated in real life. Previous work studying equivalence queries either used a “random” or “adversarial” teacher. To my knowledge, this is the first work to study the scenario of a helpful teacher and a (lightly) adversarial student in the EQ model. 

Overall, the results in this work should be of broad interest to the learning community. They prove non-trivial gaps between learning with a helpful and random teacher for several fundamental classes, and establish strong connections with numerous standard notions of teaching complexity such as teaching dimension and recursive teaching dimension. While none of these results alone are of great technical interest, they establish important connections to standard results in an original (and natural) model, which is a valuable contribution.

Overall the paper is well written, though some details appear to be missing (see below). The proofs I checked were technically sound.

A few minor comments for the authors:

Typos: “less benign”  should be “less adversarial” or “more benign,” “contant” should be “constant”

Should $h’$ be over should be $Z \cup \{z\}$ in Eq 3?

It’d be nice to have some justification as to why the learning function can’t depend on $h_{j}$ for $j<t-1$

Reference to learning rules says Section 2, but probably should be app:B.1

Is the learner rule stated somewhere in Table 3?

Learning rules as an abstraction (rather than a specific rule) are never formally defined.

The various definitions of LfS-TD compared to need to be defined somewhere. If possible in the main body, at least informally. Definitely in an appendix.

Edit: I thank the authors for their response and clarifications.
limitations_and_societal_impact: N/A
review_title: null

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

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