Teaching an Active Learner with Contrastive Examples
Authors: Chaoqi Wang
Adish Singla
Yuxin Chen
Venue: NeurIPS 2021 Poster (2021)
Keywords: Active Learning
Machine Teaching
Contrastive Examples
Sequence Optimization

Abstract: We study the problem of active learning with the added twist that the learner is assisted by a helpful teacher. We consider the following natural interaction protocol: At each round, the learner proposes a query asking for the label of an instance $x^q$, the teacher provides the requested label $\{x^q, y^q\}$ along with explanatory information to guide the learning process. In this paper, we view this information in the form of an additional contrastive example ($\{x^c, y^c\}$) where $x^c$ is picked from a set constrained by $x^q$ (e.g., dissimilar instances with the same label). Our focus is to design a teaching algorithm that can provide an informative sequence of contrastive examples to the learner to speed up the learning process. We show that this leads to a challenging sequence optimization problem where the algorithm's choices at a given round depend on the history of interactions. We investigate an efficient teaching algorithm that adaptively picks these contrastive examples. We derive strong performance guarantees for our algorithm based on two problem-dependent parameters and further show that for specific types of active learners (e.g., a generalized binary search learner), the proposed teaching algorithm exhibits strong approximation guarantees. Finally, we illustrate our bounds and demonstrate the effectiveness of our teaching framework via two numerical case studies.

Teaching an Active Learner with
Contrastive Examples
Chaoqi Wang
Adish Singla
Yuxin Chen University of Chicago
University of Chicago chaoqi cuchicago
MPI-SWS
@dishs@mpi-svs.orr
chenyuzinbuuchiaago. edu
Abstract
We study the problem active learning with the added twist that the learner is assisted by a helpful teacher. We consider the following natural interaction protocol: At each round, the learner proposes a query asking for the label of an instance x the teacher provides the requested label {2 y²} along with explanatory informa- tion to guide the learning process. In this paper, we view this information in the form of an additional contrastive example ((x", y }) where x is picked from set constrained by x (e.g., dissimilar instances with the same label). Our focus is to design teaching algorithm that can provide informative sequence of contrastive examples to the learner to speed up the learning process. We show that this leads a challenging sequence optimization problem where the algorithm's 's choices a given round depend on the history of interactions. We investigate an efficient teaching algorithm that adaptively picks these contrastive examples. We derive strong performance guarantees for our algorithm based on two problem-dependent parameters and further show that for specific types of active learners (e.g., a gen- eralized binary search leareer), the proposed teaching algorithm exhibits strong approximation guarantees. Finally, we illustrate our bounds and demonstrate the effectiveness of our teaching framework via two numerical case studies.
1 Introduction
Active learning characterizes a natural learning paradigm where learner actively engages in the learning process, and has demonstrated great success both the educational domain [Prince, 2004] and the machine learning literature [Settles, 2012]. In the context of machine learning, active learning has traditionally been studied as the active instance labeling problem, where the goal of an active learner is to learn a concept by selectively querying the labels of a sequence of data points [Kosaraju al., 1999; Dasgupta, 2004; Nowak, 2008; Balcan et al., 2006; Gonen al., 2013: Hanneke and Yang. 2014; Yan and Zhang, 2017]. Recently, active learning has been investigated under richer interaction protocols, including learning from feature feedback [Poulis and Dasgupta, 2017: Dasgupta and Sabato, 2020] or from demonstrations [Chernova and Thomaz, 2014; Silver et al., 2012]. Typically, these works assume that the rich feedback obtained from the teacher is adversarial [Dasgupta and Sabato, 2020] stochastic [Poulis and Dasgupta, 2017]. While these results have shown promising improvements in sample complexity by leveraging more expressive feedback, the assumptions of an adversarial or stochastic teacher could fall short in characterizing many real-world interactive learning systems (e.g. automated tutoring or multi-agent learning systems) where the teacher cooperates with the leamer to achieve the learning objective [Zilles et al., 2011: Zhu et al., 2018].
Motivated by real-world cooperative learning and teaching scenarios [Chen al., 201 20:8a; Teso and Kersting, 2019], we consider an optimistic yet natural interaction protocol between an active learner and a helpful teacher (see Figure/ (c)): each round, the learner proposes query asking for the label of an instance zº; the teacher then provides the requested label {x", y²) along with explanatory
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Answer with explanations, (e.g., another related question with answer)
Question
Answer
Raise & answer question
Question
(a) Active leamning
(b) Teeaching passive learnery
(c) Teaching active learners
Figure 1: The difference between (a) active learning. (b) classic machine teaching and (c) our problem.
information to guide the learning process. this paper, we consider this information in the form of an additional contrastive example ((x9,y)) where xf is picked from a set constrained by 2² (e.g.. dissimilar instances with the same label, or similar instances with opposite labels). In contrast to existing work in active learning with contrastive examples [Abe et al., 2006; Liang et al., 2020; Ma et al., 2021] I] or with comparison queries [Jamieson and Nowak, 2011; Kane et al., 2017] which focus on developing active learning algorithms, we assume that the learner's ' querying and learning strategy is fixed and known to the teacher, and focus on designing a teaching algorithm that can provide an informative sequence of contrastive examples to the learner to speed up the learning process.
Note that in the absence of the learner's query, this problem reduces to the classical machine teaching problem [Goldman and Kearns, 1995]. When teaching a (passive) version space learner [Goldman and Kearns, 1995], classical machine teaching can be viewed as a set cover problem, and the greedy algorithm is known to compute cover that is within logarithmic factor of the minimum cover [Chvatal, 1979]. However, as we show section 3.3, an active learner actively trying to reduce the label cost could actually hurt the performance of greedy teacher.
Given active version space learner specified by an acquisition function, we show that the design of an optimal teaching algorithm induces a challenging sequence optimization problem, where the teacher's available choices of constrastive examples interactions. We study the greedy teacher that adaptively picks contrastive examples in response to the learner's queries. Specifically, we introduce several natural problen-dependent parameters to characterize (1) the constraints imposed by the active learner and (2) the structure of the coverage function resulting from the hypothesis space. Based on these characterizations, we explore the theoretical properties for the greedy teacher, and demonstrate the power and limitations of the interactive teaching framework. Our main technical contributions are summarized are:
given round depend on the history of
I. We consider novel interactive protocol for teaching an active learner, and derive a general performance guarantee for the greedy teacher, regardless of the choice of acquisition function by the active learner. Our result generalizes existing near-optimality guarantees for the greedy teacher under the classical teaching [Goldman and Kearns, 1995] to the more challenging sequence optimization problem (section 3).
II. We then show that, perhaps surprisingly, a greedy teacher may fail badly when interacting with an active learner compared to the optimal teacher, due to the constrained choices contrastive examples imposed by the learner's query (section 3). In fact, there exist pessimistic scenarios where an active learner alone is better off without the help of a greedy teacher (section 4).
III. When interacting with generalized binary search (GBS) learner [Dasgupta, 2004; Nowak, 2008], we provide a strong performance guarantee for the greedy teacher, and show that it cannot perform arbitrarily badly (section 4). Our bound establishes rigorous connection between the condition and coherence parameter which are widely used in the active learning literature [Nowak, 2008, 201 I; Mussmann and Liang, 2018].
parameters introduced in section to the classical k-neighborly
IV. We empirically illustrate our bounds via two experiments. These examples illustrate the intuitive sequential teaching process and demonstrate the effectiveness of our teaching framework.

---

1.1 Related Work
Teaching a sequential learner Machine teaching has shown significant development in the past two decades in both theoretical and practical domains. In a quest to achieve rich teacher-learner interactions, various different models for machine teaching have been proposed under the sequential teaching setting (e.g., local refference-bssee model for version space learners [Chen et al., 2018b), models for gradient learners [Liu et al., 2017, 2018; Kamalaruban et al., 2019]. models inspired by control theory [Zhu, 2018; Lessard al., 2019], models for sequential tasks [Cakmak and Lopes, 2012; Haug et al., 2018; Tschiatschek et al., 2019], and models for human-centered applications that require adaptivity [Singla al., 2013; Hunziker et al., 2019]). Compared to setting, in these works, the teacher is responsible for designing all of the learning data. Recently, Peltola et al. [2019] investigated the task of teaching sequential learners such multi-armed bandits active learners where the learners also pose query. but they formulate the problem as a variant of reward shaping, and allow the teacher to provide teaching examples that inconsistent with the true data distribution. While our work falls into the category of teaching sequential learners, it could be viewed as form of explanation-bast based machine teaching, and hence inherits different teaching constraints and objectives from the above settings.
Explanation-based teaching and learning Explanation- based teaching captures a rich class of teaching protocols where labels are coupled with additional information (such as highlighting regions or features on an image). Having an additional mode in the feedback allows the learner to perceive more intuitive explanations of the target hypothesis. and hence dramatically improves the learner's ability to learn a new concept. Explanations were shown to be effective in helping a human student to improve classification performance by steering the student's s attention [Grant and Spivey, 2003; Roads et al., 2016; Chen et al., 201 8a; Aodha et al., 2018]; likewise, they also play an important role in helping machine learners to efficiently learn some concept classes that would otherwise form intractable learning problems [Poulis and Dasgupta. 2017; Dasgupta and Sabato, 2020]. Our work learning, and consider contrastive examples as a
motivated by the success of explanation-basee simple yet effective form of explanations. In comparison with existing work on explanation-han teaching, our work has an additional twist featured by the interaction with an active learner.
Submodular set and sequence optimization Our theoretical framework in section 3 is inspired by recent results on sequence submodular function maximization [Zhang et al., 2015; Tschiatschek al., 2017; Hunziker al., 2019]. In partieular, Zhang et al. [2015] introduced the notion of string submodular functions, which, analogous to the classical notion of submodular set functions [Krause and Golovin, 2014], enjoy similar performance guarantees for maximization of deterministic sequence functions. Our setting has three key differences in that (1) we focus
constrained planning problem where the set of available actions is dynamic (i.e. depending on the learner's 's query), (2) our objective function no longer exhibits diminishing returns properties and (3) we consider a min-cost coverage problem as opposed to the budgeted maximization problem.
2 Active Learning with a Teacher: Problem Formulation
In this section, we formally introduce the new problem of active learning with helpful teacher along with the corresponding interaction protocol. Then, we formulate the problem of teaching an active learner constrained sequential optimization problem. Throughout the entire paper, we use X' to denote the ground set of unlabeled instances. We consider a finite class of hypothesis H. where each hypothesis h E H is binary classifier with its output being either +1 or - (i.e., h(x) E {+1, -1)).
2.1 Learner-Teacher Interaction Protocol
We study the problem of teaching an active version space learner with teacher. In contrast to the standard active learning protocol, our framework not only allows the learner ask questions but also enables the teacher to provide additional explanatory information to guide the learning process. Specifically, we model the explanatory information using a contrastive example picked from a set constrained by the learner's s query (e.g., dissimilar instances with the same label, or similar instances with opposite labels). The full interaction protocol presented in Protocol 1. At each round the learner asks a query x g( 2 2i H(",) with query function g conditioning on the received
3

---

Protocol An interaction protocol between the teacher and the active learner
1: An active learner with query function g; Initial version space Hi Hi: Constraint function for the contrastive example; Target hypothesis h².
2: for t 1, 2, ............. do
3: learner asks query =i = -(ff:1-11 1f..-- H
4: teacher provides the label vž for the query 27 teacher provides contrastive example (2 yf) from a constrained set E(x)).
5:
6: learner computes the updated version space Hy"
7: if H² {h*) then teaching process terminates.
contrastive examples (+f=-1) and version space H Then the teacher returns the ground-truth label vf for at and also provides contrastive example (2ef, vf). Under this setting, the version space at iteration & with teaching sequence oi.t = { can be computed by (we omitted y for clarity)
(a H. (US()))
where H is the initial version space of the active learner and S(x) = (h E H(h(x) + h*(x)) denotes the hypotheses covered by x (i.e., the hypotheses that predict different labels on x than h*).
2.2 Optimization Objective
Our goal is to reduce the learner's version space such that only h+ (the target hypothesis) is left with minimal cost (e.g., # of interaction rounds of samples). The definition of cost can be problem-dependent. For the general case, we consider the following form of the cost function
(= (xf) + c (2²),
where zi., is the teaching sequence given by the teacher, and c X' - R2 computes the cost of the example. We don't write the dependencies the learner's query sequence explicitly, as the queries are induced by the teaching sequence and the query function q accordingly.
Given the active learner, we seek the optimal teaching sequence that achieves minimal cost by solving the following optimization problem.
min (X) XEX.
s.t.
( {h*} and 2, E( Vt E [|]]]
where we use X' to denote the set of all possible sequences of teaching examples, and [n]] denotes all the integers in [1, n). At every iteration, can compute the constraint set by the function E: X' given the learner's ' query. Then, the teacher must select the contrastive example from the constrained set. This a natural consideration, since without the constraint, the teacher might have selected some contrastive examples that are not interpretable to the learner. In practice, the constrained set could be the instances that are dissimilar the learner's query but with the same label or the instances that are similar to the learner's ' query but with different label.
To be noted, since the order of the teaching sequence matters in our problem, it expands the search space exponentially. This makes solving the above sequence optimization problem far more difficult than solving the corresponding set optimization problem (e.g., classical machine teaching problem), which is NP-hard. Hence, we turn to approximation algorithms with polynomial time complexity.
3 Greedy Teaching Algorithm and Analysis: A General Complexity Bound
In this section, we propose simple yet effective greedy algorithm for solving the sequential optimization problem defined in the last section. Then, we further provide theoretical results to upper and lower bound the number of rounds of the interaction between the learner and the teacher or the sample complexity, for the general cases (i.e., we don't 't have any assumptions on the active learner).
All the proof's are deferred to the Appendix due page limit.

---

OPT
OPT T+AL
OPT
2 OPT
(log (Hl) OPT"
Figure Relationship between the teaching dimension (OPT"), the optimal sample complexity for active learning (OPT*)), ), and the sample complexity for active learning with an optimal teacher (OPTT-AL).
Algorithm 2 Greedy teaching algorithm for active leaner
1: An active learner with query function g; Initial version space H H: Constraint function for the contrastive example; Target hypothesis h²"
2: for t 1, 2, 3. do
3: learner asks query z² = -( 11-11 H
4: teacher provides the label vf = h (x)))
5: teacher provides a contrastive example oं arg max me((xe(= A H) (equation 5).
6:
Update learner's version space by equation 1.
7:
if H = {h*) then teaching process terminates.
3.1 Analysis on the Optimal Teacher
To demonstrate the effectiveness of our framework, we first conduct analysis on the relationship between the teaching dimension (OPT"), the optimal sample complexity for active learning (OPT4L), and the sample complexity for active learning with an optimal and unconstrained teacher (OPT
First of all, is fact that the optimal teacher cannot perform worse than such teacher, which mimics the query selection strategy of the active learner. More importantly, this result also implies that the optimal teacher is always helpful for the active learner. In addition, by the following Lemma I, we have that OPTT, which lower and upper bounds OPTT-AL
hard to show that OPTT+AL < OPTAL, This result can be proved by the
OPTT & OPTT-AL
Lemma 1. For any (X, H.) and active learner with query function q. we have OPT $ OPT < 2 OPT". where OPT* is the classic teaching complexity.
Lastly, to further understand the relationship between OPT and OPT4L, we borrow the results from Hanneke [2007]. As proved in Hanneke [2007], have OPT OPT < log [H] OPT". Therefore, OPTAL can potentially be as large as log H OPT", while O-T is upper bounded by 2 OPT". This distinction shows that the gap between OPTT+AL and OPT can be arbitrarily large, hence demonstrates the advantage incorporating the teacher in active learning. visual illustration provided in Figure 2. Throughout the entire paper, use OPT to denote the sample complexity of active learning with an initial hypothesis class H. and an optimal and unconstrained teacher.
3.2 Greedy Teaching Policy
We now present simple yet effective greedy teaching algorithm for teaching an active learner (see Algorithm 2). For clarity of presentation, we focus on unit cost case, i.c., c(x) = for all æ, which is equivalent minimizing the number of rounds of interactions between the teacher and active learner. The extension to more general cost will be discussed in the Appendix.
Therefore, obtain the teaching sequence, will solve the following minimum-coss cover problem
min
[X] s.t. H²(X) {h*} and E {(a)) Vt E [[x]].
(4)
XEX
For iteration t + 1 with teaching history zf:t= we define the marginal gain as the following
A< q, H) = f(ff. @ x q. H. f( q. H) (xf.)) \ ( e x))
(5)
where /x1 /g, H) = (7 (21:)) the number of hypotheses removed from the version by the teaching examples I together with the corresponding learner's queries (defined by equation 1), and
5

---

① denotes the concatenation between two sequences, To be noted, when the function f is maximized, is equivalent that only the target hypothesis h" is left in the version space.
For the greedy teaching algorithm, as described Algorithm 2, at each round, selects the contrastive example from the constrained set that maximizes the marginal gain defined in equation 5. Such process will be repeated until the function f is maximized or the budget is used up.
3.3 Theoretical Guarantees for Greedy Teaching Policy
We now turn to analyzing the theoretical performance of the greedy algorithm. In general, for active learning, there is no guarantee for the sample complexity of arbitrary learners, and sometimes, the worst case complexity can be up to O(IHl) [Dasgupta, 2004], which is uninformative.
To understand the role of the greedy teacher in active learning, we rely on the following two properties of the objective function f. These two properties are usually used in the characterizing the submodularity or string submodularity of a function [Zhang al., 2015; Hunziker et al., 2019].
Definition (Pointwise submodularity ratio). For any sequence function J. the pointwise submod- ularity ratio with respect to any sequences 0, o' and query function q and hypothesis class H is defined as
PH(a, min A H) ZE A o' q, H)
(6)
Definition (Pointwise backward curvature). For any sequence function f. the pointwise back- ward curvature with respect to any sequences of and query function and hypothesis class H is defined as
f(o' 1 0 H) f(olg, H) = = f(a' 4. H) (0 H)
TH(a, .))
The submodularity ratio measures the degree of diminishing returns of the underlying sequence function by computing the ratio between the marginal gains. When the sequence function f is string/sequence submodular [Zhang et al., 2015; Alaei al., 2010], the minimum pointwise submod- ularity ratio over all possible sequences is 1. By contrast, the pointwise backward curvature measures the degree of diminishing returns of the difference between marginal gains. For postfix monotone sequence functions, the pointwise backward curvature is greater than 1 [Zhang al., 2015].
In addition, at each round, the teacher can only select examples from a constrained set, which limits its power. To accommodate such limitations, we can view the teacher as an o-approximate greedy teacher in the analysis. The parameter characterizes the ratio between the marginal gain of an unconstrained greedy teacher and that of the constrained greedy teacher. For an active learner with query function g, constraint ç, and version space H H. we can compute the corresponding a by
m A(r -1
= max t maxxe((22) A Ax H)
(8)
In general, the parameter a measures how strict the constraint is. When a becomes large, the effectiveness of the greedy teacher will correspondingly decrease.
The following theorem summarizes our first theoretical result, which provides a problem-dependent upper bound for the sample complexity of greedy teaching algorithms.
Theorem 1.
The sample complexity of the a-approximate greedy algorithu for any active learner with initial hypothesis class H is at most
a O (log [H| log (1H1//9)) a O (log (1H1/799)
APT
p999 log(>9 ((79 - 1))
p0-9
where 7 = maxHEhH 74t and pa = mingeH Ph with H
7 = max (o 21
1.1. 9), P = min (H 1:j q),
(10)
+,20
which are computed with respect to the greedy teaching sequence H and the optimal teaching sequence H for the corresponding active learner with a initial hypothesis class E H' {H*(X) X A ()) 2 2} and query function q.

---

Remark 1. For any active learner, 1 S - < [7] 1 and pa I 1. When yy - 1, the Lh..s. term in the parentheses of equation will vanish. When 7.9 + [H] 1, the r.h.s. term will vanish.
Theorem 1 bounds the worst case sample complexity of greedy teaching algorithms. To be noted, both 70 and 1 are computed with respect to the greedy teaching sequence and the optimal teaching sequence for the active learner with some initial hypothesis class H C H. rather than two arbitrary sequences. Therefore, based on Remark and Zhang et al. [2015], if the objective function is postfix monotone, then we will have 70 = 1, otherwise, we can only conclude that 7 2 L. In particular, when 75 + 1, the r.h.s. term in equation will dominate, whereas when 7 + [H] - 1, the hh..s. term will become dominating. Informally, 7 can be measure of the difficulty of the underlying sequence optimization problem, and a larger 7 will be likely to imply that the problem is more difficult. In what follows, we further argue that the linear dependency Theorem is non-vacuous.
cannot be avoided, showing that
Theorem 2. There exists a constraint function &, version space H and active learner with query function q, such that the sample complexity of the greedy teacher is at least ((v/HH)) OPT
Theorem 2 shows that the linear dependency on a cannot be improved when without any assumptions on the constraint function &, hypotheses space and the active learner. To porve Theorem 2, we constructed a special case, detailed in the Appendix. In the example, the optimal teacher only uses constant number of examples teach the active learner, while the greedy teacher needs to provide all the examples, whose number is of the order S2 (
Teaching Greedy Active Learners
In this section, we consider the problem of teaching greedy active learner, concretely, the Generalized Binary Search (GBS) [Nowak, 2008], which selects the query in a greedy manner (i.e., the one that maximizes the utility). At each iteration t + 1 with the version space H,, the GBS learner selects the query according to the expected number of hypotheses that can be covered by the query (i.e., the utility of the query). Specifically, for binary classification problem, for each query x, the utility can be computed as
H.)
2 H&l
Σ 1[h(z) (1(())=-11) M.H.
-I [[h())= (11())=1)
(11)
NEH.
The above utility function measures how discriminative the selected query is. GBS selects the query that maximizes the utility, and hence it lower bounds the minimal number of hypotheses to be removed after the query. As pointed out Dasgupta [2004], the worst case sample complexity for the GBS learner is O(H!)). However, for practical problems, there are usually some structures in the hypotheses space and the sample space we can exploit to get a tighter bound. Specifically, we consider problems with the k-neighborly structure [Nowak, 2008; Mussmann and Liang, 2018].
Definition 3 (k-neighborly). Consider the graph E) with vertex set V = X. and edge set E {(I,, I')ldH (I,x') S. k, 'v xx x' E X), where The query and hypotheses space (X, H.) is k-neighborly if the induced graph is connected.
= Kh E H and h(z)) * h(z')}
Intuitively, the k- k-neighborly structure ensures that for any two points x, x' X, there is a path formed by similar pairs connecting them. With such structures, Nowak [2011] further introduces the coherence parameter, which plays an important role bounding the worst case complexity of GBS.
Definition 4 (Coherence parameter). The coherence parameter for (X, H) is defined
ct (X, H) = min max
Σ h(x)dP(x) TEX
(12)
DET
where we minimize over all possible distributions X.
The coherence parameter c* measures how evenly the query selected by GBS bisects the hypotheses. With the above assumptions, Nowak [2008] shows that the sample complexity of GBS can be upper bounded by (log((()) ( log(1 (1/)), where 7) max ((1 + e* //2, (k + 1)/ + 2)}. This implies
that, the smaller c² and k, the more efficient GBS is.
7

---

Next. we seek to understand the sample complexity when pairing GBS with a greedy teacher. Can we also upper bound its sample complexity. even though the interaction between the learner and the teacher introduces extra complexity? The result is summarized in the following theorem.
Theorem 3. For the GBS learner with a initial hypothesis class H and ground set X, if (X, , H) is k-neighborly and with coherence parameter e², then the sample complexity of the greedy leaching algorithm with any constraint function & is at most
-.0 (log (171)) OPT
(13)
where e min ((1-((11))))) ((1-))((L+ (1 )}), and a & (,x(k//C22(11-C))))
Theorem 3 gives near-optimal bound for the greedy teaching algorithm for GBS learners, which guarantees that its performance cannot be arbitrarily bad. However, the bound cannot be directly compared to that of GBS alone, as we don't know OPTT Unfortunately, shows that the sample complexity of GBS with a greedy teacher is not guaranteed to be smaller compared to GBS alone, and for some extreme cases, it can be even larger.
following remark
Remark 2. The sample complexity of GBS with greedy teacher (even without the constraints) is not guaranteed to be smaller than that of GBS alone.
The bad news from Remark 2 shows that the greedy teacher may not be satisfactory for teaching GBS learner under some circumstances, though the greedy teaching algorithm performs very well in classic machine teaching problems. For better understanding of the failure of greedy teachers, we provide a realizable example (see Appendix), where the GBS with a greedy teacher will requires more samples than that of GBS alone. We hope that this example can motivate improved teaching algorithms for active learners, beyond the greedy heuristics.
Numerical Experiments
In this section, empirically evaluate the greedy teaching algorithm with 8-greedy active learners (a rich class of active learners including GBS) in a simulated environment. We seek to understand how the type of active learner (i.e., varying 3) and the constraint on contrastive examples affect the performance of the greedy teacher. To dig deeper, we further demonstrate how these two factors affect the value of and pº, which plays an important role in our theoretical results.
5.1 Experimental Setup
9-greedy active learners: In the experiments, we consider the class of 3-greedy active learners, for which the selected query 2/41 satisfies
1
u(0
2
H. 2
mmx u(x H₂).
(14)
3 x
We can interpolate / from 1 to +oo to cover a broad range of active learners with different properties. recover the GBS active learner, whereas, when 3 +oo, we recover
Specifically, when 3 the random active leaner. In general, as 33 increases, the strategy becomes less greedy. For the 8-greedy active leaner, the query function q returns a query that satisfies inequality (14).
We conducted experiments on two datasets: Pespula-Weevils and Butterfly-Moth, which were adopted by Singla et al. [2013, 2014] for verifying the algorithm for teaching the crowd to classify images. Specifically, Vespula-Weevin is a synthesized dataset with 200 images, which generated by sampling 2-d features from two bi-variate Gaussian distributions. The dataset Butterfly-Mon -Moh consists of 160 real images with the two categories Butterfly and Moth. The 2-d embedding of each image is inferred from the annotation process using generative Bayesian model proposed in Welinder et al. [2010]. More details about the datasets can be found in the Appendix.
Datasets:
Hypothesis space: Following Singla et al. [2014], for the Vesvula-Weevil dataset, we generate the hypotheses by randomly sampling from eight multivariate Gaussian distributions, with mean :4 [T/4 i, OJ. and covariance Σ; 2, 0: 0, 5e -3. where is varying from 0 to 7. For the Butterfly-Mon dataset, the hypotheses are inferred from the annotation process with the same generative Bayesian model for inferring the 2-d embedding.
8

---

Vespula- Weevil
Vespula-Weevwe (w 0.5)
Butterfly-Moth (W 0.01)
Butterfy-MMtth
(IU 0.01)
(4 = 0.5)
5.5
14
Average Cost
5.0
AL
10
4.5
AL-GTICF))
AL-GRO)
4.0
$100
10a
10?
10a
10"
10a
10?
10a
10"
10a
107
10a
10"
107
107
10a
B
8
B
B
Figure The average cost different active leamers constraints. AL denotes the setting of active learner alone. AL-GT corresponds to active learner with an unconstrained greedy teacher, and C, F, C+F correspond to different constraints on the constrastive examples. & E [0, 1] is parameter controlling the size of the search space, which only affects AL-GT(C), AL-GT(F), and AL-GT(C+F). The shaded area is the one-standard error.
AL-GT(C++F)
AL-GT(C)
AL-GT(F)
Average Cost
12.5
12.5
3.5
7.5
7,5
=
0,02
5.0
4 0.04
g
15
15
15
Average
= 1.0
10
10
10
1000
10a
102
10a
10a
10a
10a
10a
900
10a
102
10
B
B
Figure 4: How do active learners (9) and constraints (w) affect the teaching cost (top row) and (bottom row). The three columns corresponding to the results of AT-GTTC++F) AL-GT(C) and AL-GT(F) respectively. The results obtained the Butterfly-Mo dataset. We don't display the standard for clarity.
5.2 Effects Active Learners and Constraints
We first study how does the active learner (AL) affects the teaching performance under different constraints. Specifically, we vary (3 in [1, 5, 10, 100, 1, 000) to model different learners. terms of the constraint the teacher's example, examples that are close to the learner's query but with different label (denoted by C); 2) examples that are far away from the learner's 's query but with the same label(denoted by F); 3) the union of 1)& 2) (denoted by C+F). For each constraint, we also adopt parameter yó E [0. 1] to control the size of the search space (i.e., the closest furthest tà portion of the points with different the same label as the query). We also include the unconstrained teacher, which can freely select examples.
consider the following three types of the constraints: 1)
To obtain more robust results, we iterate through all the hypotheses to serve the target hypothesis once, and compute the averaged cost for identifying the target hypothesis, accompanied by the standard error. The results are presented in Figure 3. We observe that for both datasets, AL with greedy teacher (AL-GT, unconstrained) always achieves the best performance terms the average cost. When 3 becomes larger, the average cost of AL-GT increase very slightly. For the others, when v is small, they usually perform worse than AL along. This because when & is small, the candidate points in the constrained set are too restrictive and they are usually redundant to the query, making the contrastive example uninformative. By contrast, when v is large enough, AL-GT(C+F) significantly outperform AL alone, showing that the teacher is helpful in this case. In summary, when 3 becomes large and the constraint not too strict, the teacher will be more helpful (i.e., the gap between AL and AL with teacher becomes larger).
further study how the constraints and 3 affect the parameters a. The results are provided in Figure 4. In general, we can observe that the constraints become stricter (i.c., v becomes smaller),

---

color
size
(1) Weevil
(2) Vespula
(3) Weevil
(4) Weevil
Figure visualization teaching sequence. (1)&(3) are learner's queries and (2)&(4) are contrastive examples provided by the teacher (i.c., AL+)).(C+F).
will correspondingly increase well as the cost for teaching the active Iearner. This consistent with our Theorem and Theorem in Section and Section 4. In addition, when 3 becomes larger, is also increasing, which is consistent with the trend in the cost plots (top row Figure 4). Besides, we also compute the empirical values of p", finding that for different 3 and constraints, p stays very close to According our theoretical bounds, this may also explain why the trends in the cost plots are mostly consistent with those in the plots of a (bottom row in Figure 4).
5.3 Visualization of the Teaching Sequence
Lastly, we visualize teaching sequence of AL-GT(C+F) in Figure 5. The results are obtained with = and vi = 0.5 on the -eevvl dataset. The first and third examples are the learner's queries and the second and fourth ones are the teacher's 's provided contrastive examples. In general, weevils have relatively short heads with similar color to the body. In contrast, vespula have big and contrasting heads. From Figure 5, we can observe that at the first round, the teacher selects an image of vespula with similar body size to the learner's query, but with head that is in relatively larger and of different color. This highlights the key features (i.e., the color and size of the head) to distinguishing weevil and vespula. Subsequently, the teacher provides another image of weevil which is visually very different from the query in terms the size of body and head, but is in the same category.
6 Conclusion
We introduced a novel interactive protocol for teaching an active leaner. We first derived a general performance guarantee for the greedy teacher with arbitrary active learners, and then provided stronger performance bound for teaching GBS learners with a greedy teacher under mild assump- tions. In addition, we also demonstrated the limitations of greedy teachers by showing that 1) the performance of the greedy teacher can be arbitrarily worse than that of the optimal teacher due to the constrained choices of contrastive examples; and 2) the greedy teaching strategy for the GBS learner is not guaranteed to be better than GBS alone. Lastly, we provided empirical results to demonstrate the effectiveness and limitations of the greedy teachers. We believe that our results have taken significant step in bringing active learning and machine teaching closer to real-world settings in which the teacher collaborates with the learner achieve the learning goal.
Social Impact
In this work, we provided an greedy teaching algorithm for active learners with theoretical guarantees. Our algorithm is derived for teaching an active leaner collaborative setting to achieve some learning goal, which can be potentially helpful for improving many real-world interactive learning systems, e.g., automated tutoring or multi-agent learning system.
However, just coin has two sides, our algorithm can be easily extended to poisoning the active learner by change the objective of the teacher. This can potentially threaten the safety of deploying machine learning models in online products.
10

---

Acknowledgments and Disclosure of Funding
We thank Sandra Zilles for the helpful discussion and valuable feedback. This work supported in part by NSF IIS-2040989, and a C3.ai DTI Research Award 049755.
References
Naoki Abe, Bianca Zadrozny, and John Langford. Outlier detection by active learning, In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. 2006.
Saeed Alaci, Ali Makhdoumi, and Azarakhsh Malckian. Maximizing Sequence- Subbooula Func- tions and its Application to Online Advertising. arXiv e-prints, art. 1009::000.4453.. 2010.
Oisin Mac Aodha, Shihan Su, Yuxin Chen, Pietro Perona, and Yisong Yue. Teaching categories to human learners with visual explanations. In 2018 IEEE Conference on Computer Vision and Pattern Recognition, 2018
Maria-Florina Balcan, Alina Beygelzimer, and John Langford. Agnostic active learning. In Ma- chine Learning, Proceedings of the Twenty-Third International Conference, volume 148 ACM International Conference Proceeding Series, 2006.
Maya Cakmak and Manuel Lopes. Algorithmic and human teaching of sequential decision tasks, In Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence. 2012.
Yuxin Chen, Oisin Mac Aodha, Shihan Su, Pietro Perona, and Yisong Yue. Near-optimal machine teaching via explanatory teaching sets. In International Conference on Artificial Intelligence and Staristics, volume 84 of Proceedings of Machine Learning Research, 2018a.
Yuxin Chen, Adish Singla, Oisin Mac Aodha, Pietro Perona, and Yisong Yue. Understanding the role of adaptivity in machine teaching: The case of version space learners. In Advances in Neural Information Processing Systems 31, 2018b.
Sonia Chernova and Andrea L Thomaz. Robot learning from human teachers. Synthesis Lectures on Artificial Intelligence and Machine Learning, 8(3), 2014.
Vasek Chvatal. A greedy heuristic for the set-covering problem. Mathematics of operations research, 4(3), 1979.
Sanjoy Dasgupta. Analysis of greedy active learning strategy. In Advances in Neural Information Processing Systems 17, 2004.
Sanjoy Dasgupta and Sivan Sabato. Robust learning from discriminative feature feedback. In The 23rd International Conference Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, 2020.
Sally A Goldman and Michael Kearns On the complexity of teaching. Journal of Computer and System Sciences, 50(1), 1995.
Alon Gonen, Sivan Sabato, and Shai Shalev-Shward Efficient active learning of halfspaces: an aggressive approach. In Proceedings the 30th International Conference Machine Learning, volume 28 of JMLR Workshop and Conference Proceedings, 2013.
Elizabeth R Grant and Michael Spivey. Eye movements and problem solving: Guiding attention guides thought. Psychological Science, 2003.
Steve Hanneke. Teaching dimension and the complexity of active learning. In International Confer- on Computational Learning Theory, 2007.
Steve Hanneke and Liu Yang. Minimax analysis of active learning. CoRR, abs/1410.0996, 2014.
Luis Haug, Sebastian Tschiatschek, and Adish Singla. Teaching inverse reinforcement learners via
features and demonstrations, In Advances in Neural Information Processing Systems 31, 2018.

---

Anette Hunziker, Yuxin Chen, Oisin Mac Aodha, Manuel Gomez Rodriguez, Andreas Krause, Pietro Perona, Yisong Yue, and Adish Singla. Teaching multiple concepts a forgetful learner. In Advances in Neural Information Processing Systems 32, 2019.
Kevin G Jamieson and Robert Nowak. Active ranking using pairwise comparisons. In Advances in Neural Information Processing Systems, 2011.
Parameswaran Kamalaruban, Rati Devidze, Volkan Cevher, and Adish Singla. Interactive teaching algorithms for inverse reinforcement learning. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, 2019.
Daniel M Kane, Shachar Lovett, Shay Moran, and Jiapeng Zhang. Active classification with comparison queries. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2017.
Rao Kosaraju, Teresa Przytycka, and Ryan Borgstrom. On an optimal split tree problem. In Algorithms and Data Structures. 1999.
Andreas Krause and Daniel Golovin. Submodular function maximization. In Tractability: Practical Approaches to Hard Problems. 2014.
Laurent Lessard, Xuezhou Zhang, and Xiaojin Zhu. An optimal control approach to sequential machine teaching. In The 22nd International Conference on Artificial Intelligence and Statistics, volume of Proceedings of Machine Learning Research, 2019.
Weixin Liang, James Zou, and Zhou Yu. ALICE: Active learning with contrastive natural language explanations. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), 2020.
Weiyang Liu, Bo Dai, Ahmad Humayun, Charlene Tay, Chen Yu, Linda B. Smith, James M. Rehg, and Le Song. Iterative machine teaching. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Muchine Learning Research, 2017.
Weiyang Liu, Bo Dai, Xingguo Li, Zhen Liu, James M. Rehg, and Le Song. Towards black-box iterative machine teaching. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, 2018.
Shuang Ma, Zhaoyang Zeng, Daniel McDuff, and Yale Song. Active contrastive learning of audio- visual video representations. In International Conference on Learning Representations, 2021.
Stephen Mussmann and Percy Liang. Generalized binary search for split-neighborly problems. In Proceedings of the Twenty-Firy International Conference on Artificial Intelligence and Statistics, 2018.
Robert Nowak. Generalized binary search. In 2008 46th Annual Allerton Conference Communica- lion, Control, and Computing. IEEE, 2008
Robert Nowak. The geometry of generalized binary search. IEEE Transactions on Information Theory, 57(12), 2011.
Tomi Peltola, Mustafa Mert Çelikok, Pedram Daee, and Samuel Kaski. Machine teaching of active sequential learners. In Advances in Neural Information Processing Systems 32, 2019.
Stefanos Poulis and Sanjoy Dasgupta. Learning with feature feedback: from theory to practice. In Proceedings of the 20th International Conference Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, 2017.
Michael Prince. Does active learning work? a review of the research. Journal of engineering education, 93(3), 2004.
Brett Roads, Michael C Mozer, and Thomas A Busey. Using highlighting to train attentional expertise. PloS one, 2016.
Burr Settles. Active learning. Synthesis lectures on artificial intelligence and machine learning, 6(1), 2012.
12

---

David Silver, Andrew Bagnell, and Anthony Stentz. Active learning from demonstration for robust autonomous navigation. In IEEE International Conference on Roboties and Automation. IEEE, 2012.
Adish Singla, Ilija Bogunovic, Gabor Bartók, Amin Karbasi, and Andreas Krause. On actively teaching the crowd to classify. In NIPS Workshop on Data Driven Education, 2013.
Adish Singla, Iija Bogunovic, Gábor Bartók, Amin Karbasi, and Andreas Krause. Near-optimally teaching the crowd to classify. In Proceedings of the 31th International Conference Machine Learning, volume 32 of JMLR Workshop and Conference Proceedings, 2014.
Stefano Teso and Kristian Kersting, Explanatory interactive machine learning. In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, 2019.
Sebastian Tschiatschek, Adish Singla, and Andreas Krause. Selecting sequences of items via submodular maximization. In Proceedings of the T'hirty-Frrst AAAI Conference on Artificial Intelligence, 2017.
Sebastian Tschiatschek, Ahana Ghosh, Luis Haug, Rati Devidze, and Adish Singla. Learner- aware teaching: Inverse reinforcement learning with preferences and constraints. In Advances in Neural Information Processing Systems 32, 2019.
Peter Welinder, Steve Branson, Serge J. Belongie, and Pietro Perona. The multidimensional wisdom of crowds. In Advances in Neural Information Processing Systems 23, 2010.
Songbai Yan and Chicheng Zhang. Revisiting perceptron: Efficient and label-optimal learning of halfspaces. In Advances in Neural Information Processing Systems 30, 2017.
Zhenliang Zhang, Edwin KP Chong, Ali Pezeshki, and William Moran. String submodular functions with curvature constraints. IEEE Transactions on Automatic Control, 61(3), 2015.
Xiaojin Zhu. An optimal control view of adversarial machine learning. arXiv preprint 1rX1v:1811.04422, 2018.
Xiaojin Zhu, Adish Singla, Sandra Zilles, and Anna N. Rafferty. An overview of machine teaching. CoRR, 0as//801.05999 2018.
Sandra Zilles, Steffen Lange. Robert Holte, and Martin Zinkevich. Models of cooperative teaching and learning. Journal of Machine Learning Research, 12(Feb), 2011.
13


Reviews:
[{"review_id": "UwWzRDWBFkY", "reviewer": "Reviewer_NhnX", "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:\n>- Provide the approximation ratio of the greedy teaching algorithm;\n>- Provide improved results for greedy active learners.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Originally: Good\n\nThe paper studies a new scenario combining active learning and teaching, which raises interesting theoretical and algorithmic challenges.\n\nQuality:  Proofs seem to be incorrect.\nIn 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. \n\nClarity: Good\n\nSignificance: If I am right, the above issue should be corrected. \n\n-------------------------\nAfter rebuttal:\nThe 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. \n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "They are adequately addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "UaYTp0LkXWF", "reviewer": "Reviewer_PbTC", "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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.\n\nFor 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.\n\nThe 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).\n\n============= post-rebuttal =============\n\nThanks 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. \n\nI 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.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "They are discussed.", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "HXt32dHSBP", "reviewer": "Reviewer_j9HW", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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.\n\nThe 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.  \n\nThere 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?\nAdditionally, there are still some details missing here: what is \\Psi and how is it formally defined? Is it related to \\xi in equation (4)?\n\n\nOverall, the paper is clear but some parts need better clarity in particular in the experiments section see above.\nAlso why is there an upper script c on equation (2) on each x? is this upper script related to contrastiveness? \nI think that reporoducing the results may be hard in this case as some parts are not clear (e.g. \\xi, \\psi).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "\nyes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

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)