Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper proposes a teaching algorithm that uses contrastive examples to teach an active learner. Some performance guarantees are given for some special cases. Some empirical evidences are presented to support the results.
main_review: In general, I think the idea of using contrastive examples in machine teaching sounds interesting. However, what concerns me most is the significance of the problem. It seems a bit unmotivated to teach an active learner, since the active learner can already query samples from an oracle. If the teacher contains optimal information of the learner, then the problem seems to be meaningless. If the teacher is a black-box one, then the problem reduces to designing a new active learning algorithm. Either way, I find the motivation of the paper quite weak.

For the theoretical results, it doesn't seem to suggest that the teacher can indeed provably improve the sample complexity, since the guarantees are not sufficiently tight. The worst-case bound is also not informative for the teaching algorithm. The tightness of the bound (even under some assumptions) is important and also needs to be discussed. In general, I believe the theory part is not signficant enough.

The experiments show an incremental improvement over the standard active learner with some simulations on toy examples. The experiments look reasonable but not impressive. I will be interested to see some experiments on some realistic distributions (say MNIST, CIFAR-10/100).

============= post-rebuttal =============

Thanks for the response. My concerns are partially addressed. As a non-expert in machine teaching, I start to understand why making the passive learner active is useful and it also simulates the real-word education nicely. But I do think there is much room for improvement, such as stronger theoretical results and more practical experiments. 

I will increase my score from 4 to 5 (I would pick 5.5 if that is an option). I think this paper is much more boarderline than I originally thought.


limitations_and_societal_impact: They are discussed.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies a scenario combining active learning and teaching: An active learner cooperates with a teacher, which provides contrastive instances to the learner to accelerate learning. The paper is basically theoretical-oriented, the main contributions are:
>- Provide the approximation ratio of the greedy teaching algorithm;
>- Provide improved results for greedy active learners.
main_review: Originally: Good

The paper studies a new scenario combining active learning and teaching, which raises interesting theoretical and algorithmic challenges.

Quality:  Proofs seem to be incorrect.
In Equation (9) of theorem 1, there is a term $\log(\gamma^g/\gamma^g-1)$. However，$\gamma^g \leq 1$ according to the definition. I have checked the proofs in the appendix, and find that Equation (19) and (20) in the proof of theorem 1 may be incorrect. I think the correct bound for Equation (9) of theorem 1 is $T \geq \frac{\alpha}{\rho^g\gamma^g}\log(1/(1-\gamma^g)) \cdot OPT$, which can be derived from the proof process proposed in the paper. While this makes the example in theorem 2 incorrect, since \gamma^g cannot be 1 in this bound, while the proof of theorem 2 relies on this. 

Clarity: Good

Significance: If I am right, the above issue should be corrected. 

-------------------------
After rebuttal:
The above issue has been clarified. I do think the paper makes an interesting attempt towards the T+AL problem. It is expected that in the updated version, the suggestions raised in the reviewer-author discussions would be addressed. 




limitations_and_societal_impact: They are adequately addressed.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper addresses the problem of teaching an active learning with an explanatory teacher that provides contrastive examples together with the query label. They show guarantees for the greedy version with respect to GBS (Nowak 2008) and provide 2 small data sets for the validation of the advantage of the greedy teacher and demonstrating the tradeoff between the level of greed and the constraint on the search space.
main_review: The problem setting addressed is interesting and novel - teaching an active learner with contrastive examples seems to be novel to my best knowledge. The greedy learner is not a new format, and I would expect the authors to better address that on the related work section.

The submission seems technically sound, and the claims seems to be well supported although I did not go through the proofs in detail. The experimental results capture an interesting tradeoff between the different constraints and show the greedy-teacher advantage. However more experimentation and even with some benchmark data could be more convincing.  

There are still fundamental questions to be answered: in all the hypothesis reduction approaches the practical aspect is somewhat problematic in my view: for example: in Alg 2 we receive as output the target hypothesis? Can the authors bridge this setting to the practical use of their techniques? Namely, can we practically use such a techniques on real problems? How did they use these techniques on their small data sets in the experiments section? Can we approximate some target that will be of interest but can be a-priori defined on some validation set?
Additionally, there are still some details missing here: what is \Psi and how is it formally defined? Is it related to \xi in equation (4)?


Overall, the paper is clear but some parts need better clarity in particular in the experiments section see above.
Also why is there an upper script c on equation (2) on each x? is this upper script related to contrastiveness? 
I think that reporoducing the results may be hard in this case as some parts are not clear (e.g. \xi, \psi).

limitations_and_societal_impact: 
yes
review_title: null

Meta-review: This paper proposes a novel learning setup, provides some initial sample and query complexity analysis as well as an empirical evaluation on a synthetic dataset. The authors propose a merge of active learning and machine teaching. In their framework, a learner gets to query an example, and the teacher responds with a label and an additional piece of information. Here, the teacher also provides a "contrastive example", that is an example that is similar to the query but is from a different label class or one that is dissimilar but from the same label class. 

The reviewers appreciated the clarity and novelty in this submission. Some concerns regarding correctness were raised, but resolved during the discussion phase. The reviewers also raised some concerns about motivating this particular setup.

Overall, this seems to be a solid contribution, that provides a novel framework and initial analysis. The work will likely be of interest to researchers in the neurips community who focus on active learning, query learning, or machine teaching. 
Decision: Accept (Poster)