Iterative Teaching by Label Synthesis
Authors: Weiyang Liu
Zhen Liu
Hanchen Wang
Liam Paull
Bernhard Schölkopf
Adrian Weller
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Iterative Machine Teaching
Reinforcement Learning
Unrolling
Label

Abstract: In this paper, we consider the problem of iterative machine teaching, where a teacher provides examples sequentially based on the current iterative learner. In contrast to previous methods that have to scan over the entire pool and select teaching examples from it in each iteration, we propose a label synthesis teaching framework where the teacher randomly selects input teaching examples (e.g., images) and then synthesizes suitable outputs (e.g., labels) for them. We show that this framework can avoid costly example selection while still provably achieving exponential teachability. We propose multiple novel teaching algorithms in this framework. Finally, we empirically demonstrate the value of our framework.

Iterative Teaching by Label Synthesis
Weiyang Liu
Zhen Liu
Hanchen Wang' Liam Paull Bernhard Schölkopf Adrian Weller
University of Cambridge 2MPI for Intelligent Systems, Tübingen "Mila, Université de Montraal 'CIFAR Al Chair 'The Alan Turing Institute
"Equal Contribation
E /w13968cam ac. uk, zhen liu. 20umontreal.co
Abstract
In this paper, we consider the problem of iterative machine teaching, where a teacher provides examples sequentially based on the current iterative learner. In contrast to previous methods that have to sean over the entire pool and select teaching examples from it in each iteration, propose a label synthesis teaching framework where the teacher randomly selects input teaching examples (e.g., images) and then synthesizes suitable outputs (e.g., labels) for them. We show that this framework can avoid costly example selection while still provably achieving exponential teachability. We propose multiple novel teaching algorithms in this framework. Finally, we empirically demonstrate the value of our framework.
Introduction
Machine teaching [103, 106] studies the problem of constructing minimal dataset for a target concept such that a learner can learn the concept based on this dataset. Machine teaching has diverse applications ranging from crowd sourcing [71, 72, 100, 101] to model robustness [2, 54, 63].
Machine teaching also has nice connections with curriculum learning [7] and coresets [1, 28].
Based on the learner, machine teaching can be performed in either batch or sequential fashion. The majority of prior work studies batch machine teaching [42, 56, 102, 103], where teacher con- structs a minimal batch set of training samples and provides it to a student in one shot without further interactions. Then the student keeps learn- ing from this batch dataset for the target concept. The size of such minimal batch set is called teaching dimension [22]. Differently, sequential machine teaching [38, 43, 44, 61] bridges the gap between machine teaching and practical learning algorithms by studying the sequential (i.e., itera- tive) learner such as neural networks. A typical example iterative machine teaching (IMT) [43, 44] where the teacher guides learner to a target concept by interacting with the learner (e.g.. feeding training samples) in every iteration. The minimum number of such iterations is called the iterative teaching dimension. One of the largest challenges in sequential tcaching is how to effectively and efficiently provide teaching examples to the iterative learner. Usually we are mostly interested in the pool-based teaching in IMT since it well matches the setting of modern machine learning. However, exploring all the possible teaching trajectories is computationally prohibitive. For example, there are (1t) possible teaching trajectories (n the number of iterations) if we select samples per iteration from pool of size Due such huge search space, the selection of teaching examples is combinatorial problem that is inherently difficult to solve. IMT [43] performs the teaching sample selection with a greedy policy, but it could be substantially sub-optimal in certain cases [38] and its computational complexity also scales linearly with the size the dataset.
(a) Vanilla Itenative Teaching
Select Teaching Examples
Teucher
Leanne
Randomly Sample Examples
Teacher
(b) I Label Synthesis Teaching
Comparison of vanilla iterative machine teaching and label synthesis teaching. The red dotted frames indicate the teacher's 's efforts.
Figure 1:
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

We propose general teaching framework called LAbel Synthesis Teaching (LAST), which in its standard version avoids the problems of sample selection - though we will later discuss how sample selection can be combined with our approach. In the standard version of LAST, teaching examples are randomly sampled (similar to SGD) in the pool and the teacher synthesizes their labels order to quickly guide the learner to the desired model. A brief comparison between IMT and LAST is given in Fig. 1. LAST restricts the teaching to the label space and bypasses the selection of teaching samples. Therefore, LAST avoids the high complexity of selecting teaching samples in a large pool.
Intuition for why LAST is able to achieve promising teaching performance comes from the empirical success of knowledge distillation [26] and label smoothing [73]. Knowledge distillation shows that training neural networks with soft labels from pretrained model can generally improve generalization. Label smoothing demonstrates that the ground truth labels are not necessarily the optimal supervision for training model. Instead, smoothing the label with uniform distribution can calibrate the model and lead to better generalization. Both methods can be viewed as providing an alternative label (instead of the ground truth) to the learner in order to improve its generalizability. Moreover, [77, 78] show that there exists privileged information beyond the ground truth labels that can significantly improve the convergence rate of learning algorithms. Therefore, now we can safely argue that the ground truth labels are not always optimal learning signals. Motivated by these work, we aim to construct teacher model that can adaptively synthesize suitable labels for a learner (with the hope to implicitly encode priviledged information) in order to improve the learner's 's convergence.
Specifically, we study LAST primarily under the omniscient scenario where the teacher knows everything about the learner (e.g., the optimal learner parameters). To perform omniscient teaching, we consider a greedy teacher and a parameterized teacher. We show that greedy teaching can achieve exponential teachability (ET) [43] without selecting teaching examples. Additionally, we touch upon the black- box teaching scenario where the teacher knows less about the learner (e.g., the optimal learner parameters are unavailable), and discuss how perform LAST in this case.
LAST provides unified view for understanding soft label methods, e.g., knowledge distillation [26, 53J, label smoothing [11, 59, 73], and self-training [104]. All these methods can be interpreted as modifying the labels to achieve desirable learning behavior and outcome. With LAST, we can connect iterative machine teaching to many classic learning algorithms and shed novel light on them.
2 Related Work
Machine teaching. Batch machine teaching [42, 56, 102, 103] has drawn increasing more attention
recently. Different learners typically exhibit distinct behaviors during teaching. [10, 74] focus on how to teach version space learners. The teaching dimension of linear learners [42]. kernel learners [36] and reinforcement learner [95] is extensively studied. Teaching a forgetful learner is explored in [29, 44]. [94, 105] consider how to teach multiple learners simultaneously. Sequential machine teaching [38, 43, 44, 91] studies iterative learners by considering the specific optimization algorithm that the learner adopts. Unlike batch scenario, the teaching quality is evaluated by the learner's s convergence. [38] connects sequential teaching to optimal control and gains interesting insights, but it can not produce a practical teaching policy. [91 uses
sampling to scale IMT to large- scale problems. Machine teaching is shown useful in reinforcement learning [24, 32, 63, 76), human- in-the-loop learning [9, 31, 55], crowd soureing [72, 100, 101] and cyber security [2. 57, 96, 97, 98]. [9, 13, 21, 35, 65, 108] study machine teaching from more theoretical point of view.
Cooperative communication. Cooperative communication [69] is mutual theory of mind reasoning between teacher and a learner. The teacher selects data to convey a hypothesis and the learner infers hypothesis given the selected data. Both agents have the shared goal of successfully transmitting beliefs. [84] formulates cooperative communication with the framework of optimal transport. In this framework, pedagogical reasoning [66, 67, 68), cooperative inference [82, 83, 93] and Bayesian teaching [15, 16, 92] can all be viewed as special cases. Among this line of research, cooperative inference [82] shares many similarities to our work and also adopts an iterative teaching paradigm. While [82] formulates the teaching problem with probabilistic inference framework, LAST addresses the iterative teaching with nested optimization framework.
Soft-supervised learning. It has been shown that supervising the model with soft labels can be
beneficial to generalization [73, 89] and robustness [75, 107]. Label smoothing [73] replaces one-hot label vector with a mixture of itself and the uniform distribution, achieving stronger generalization in training neural networks. Knowledge distillation [26] uses the soft predicted label from a pretrained model to supervise the training of student model, which can make the student model generalize
2

---

better than trained- woonoddffo--ssee from-scratch one. [89] perturbs the one-hot label vector with random noise and also observes better generalization. Large-margin softmax [45, 50, 51, 52] can be approximately viewed as training learners with dynamic soft labels (Appendix E). Self-training [8, 90, 104] also uses dynamic soft labels to iteratively train the learner. In constrast to the empirical nature of soft-supervised learning, LAST formulates it as a unified and principled iterative teaching framework.
3 Label Synthesis Teaching
Teaching protocol. We first consider the simplest teaching protocol following [43]. Both the teacher and the learner observe the same sample A and share the same feature space by representing A as x with the label y. The teacher has access to all the information about the learner such as the model parameter w' at the i-th iteration, the learning rate 7)s the loss function l and the specific optimization algorithm (e.g.. SGD). For interaction, the teacher can only communicate with the leamer via examples { {2] Vÿ) M=],", , in the i-th iteration, where m denotes the batch size.
Teaching objective. The goal of the teacher is to provide examples in each iteration such that the learner parameters converge desired parameters w" as fast as possible. For example, w" typically is arg minw B(m.y)) y) {f( y/w)). Therefore, a general objective for any teaching algorithm is min((=) ""),,..("""" (a"", "² d(w"", w²) where I denotes the termination iteration for the teaching algorithm. We use batch size here, but it is straightforward to extend the batch size to arbitrary m. d(:,-) denotes some discrepancy measure (e.g., Euclidean distance). This objective aims to find teaching trajectory that is terminated at the 7-th step such that the discrepancy between the current learner parameters and the desired learer parameters is the smallest. This is very challenging given the enormous search space. To simplify the problem, [43] proposes a greedy policy to generate the teaching curriculum, but it is computationally expensive when dealing with a large pool.
3.1 The LAST Framework
Unlike the general teaching objective that optimizes the sequential sam- ple selection, the LAST framework instead optimizes the teaching ex- amples in the label space, and the corresponding objective becomes mi...""...."""" d(w" w²) where ........ xx are sampled uniformly from the pool (same as SGD). Such a teaching objective is general and does not make any assumption on the optimal structure in the teaching trajectory, making the problem intractable. To simplify the problem, we can assume that the teaching signal (i.e., label y in LAST) only depends domly sampled { (x. ÿ and the learner's 's current and desired model (i.e., parameters). Therefore, we can formulate the corresponding label synthesis policy as y= no to(a y: w², u0"") where ' is optionally parameterized by 0 and /t denotes the original ground truth label. Then the teaching objective becomes arg min d(w." w²)) An overview of LAST is given in Fig. 2. Moreover, LAST pro- vides a unified framework for knowledge distillation, label smoothing and self-training. Knowledge exp(=;(=)/1) distillation [26] generates the label with the policy y: Σ, (m]/v where vb is the temperature and (x) is the i-th logit output of x from pretrained neural network. Label smoothing [73] uses = nD- 1 1=11 1 (K is the number of classes) as the label synthesis policy. Self-training [104] feeds the learner with the pseudo-label predicted by the learner from the last iteration. All these methods can be viewed as using some form of customized label synthesis policies.
Teacher
gynchesize
Label
Example
Learner
Figure 2: Overview.
the ran-
3.2 Greedy Teaching Policy
For the 1-th iteration, we can approximately solve the original teaching problem with the optimization mitt(tt)),....""" (( w²) where v T is the number of steps being considered. By using v=1 and the gradient descent update in LAST, we obtain a greedy policy arg miny' d(w=+I,,") w²) where w'+1, is one-step update from the current learner w w.r.t. the learner loss E and example {x", y²}. The greedy policy minimizes the Euclidean distance between the current learner parameters and the desired parameters in each iteration by learning a suitable label. We apply the greedy policy to each iteration for generating labels. The label for the example x' at the t-th iteration is produced by
at(w", s (w (w/
min (12)
06(x'' "
86(20' v 1000
min
w (-1 T
0w--1 w
Ow
2 1-1
0wi-1
Ty (an 10f
(1n" y (a0 (mo
where f(xx, yd (ur') denotes the loss function of the learner and und the learner parameter in the 1-th iteration. For simplicity, we consider the mini-batch size as 1. It is straightforward to write Eq. (1)
3

---

in a mini- mini-batch form. According to the decomposition of the parameter discrepancy, the teacher optimizes the labels such that the parameter discrepancy can be minimized. In contrast IMT, which aims to optimize the sample x², the greedy teaching in LAST first randomly samples the teaching example and then optimize the label based on arg miny' T) (xr, y²'wn") 2n, T2 (a'; y (lu)). The overall procedure is given in Algorithm 1. Depending on the teacher's capability, we can optionally consider a few constraints for the synthesized labels.
Algorithm I Omniscient Greedy LAST
One-hot constraint. For classification tasks, we can constrain the teacher to synthesize one-hot labels for æ. With the one-hot constraint, label synthesis becomes a standard integer programming problem [87].
Initialize 1= w., e and T:
while |/''' - w 1l2 2 e or t S T do
Randomly select a sample x from the pool: Solve Eq. (1) to synthesize the label y': Use the synthesized label y for the update:
Soft constraint. A straightforward relaxation of the one-hot constraint to constrain the labels on a prob- ability simplex, i.e., E: V: = 1 and y; 2 0, Vi, and it becomes a constrained optimization problem.
0f(n', v² I Own
w = =
Set t t t ++
end
Magnitude constraint. For regression, we can con- strain the p-norm of the label vector be smaller than positive constant r, i.e., 11y (w', x) 1p Sr (for constraining the synthesized label to be around the current prediction) or ly - Ul1p S (for constraining the synthesized label to be around the ground truth label), where we usually use p= A larger magnitude indicates more flexible and powerful teacher. For classification, we can use the same magnitude constraints (optionally) along with soft constraints E, y: = and y; 2 0, Vi.
No constraint. The most powerful teacher has no constraint on the synthesized labels and can synthesize any label vector, making it easy to solve the unconstrained optimization in Eq. (1).
3.2.1 Teaching Linear Learners
We start by discussing how to use greedy LAST to teach representative linear learners such as linear least square regression (LSR) and logistic regression (LR), and then give theoretical analyses on their iterative teaching dimension (i.e., convergence properties). Specifically, we consider the following standard objective function: f y y/w) ((w, .)- y)² for the LSR learner and LL (<x y (/)= = log(1+ + cxp -y(w, }))) for the LR learner. { y1a] } is the i-th sample in the pool. We gain intuitions by looking at the synthesized label. Taking LSR an concrete example, Eq (1) becomes
min v/ 2 (2rje (w w", .)) - 2n (ar, (a).))))())))) (wr, m))y y + n (ar, .)) (w, x) 2m (w,, a) (w w .)) (2)
from which we can obtain the closed-form solution for the synthesized label as 2nf (2x, x) (w, x) 2 w", x²)
A) (w, x)
(w ,x)
2nf (ax
Predicted label - easy
Optimal label bard
Synthesized label
where x= (1)e (xx x X is essentially parameter that weights the importance between using the current prediction as the training label and using the (pscudo) ground truth label as the training label. Suppose that the input data lies a hypersphere with radius y, then we have X _12-- -u-2- Typically ne
will gradually decrease during training, À will gradually increase. Interestingly. this implies that the training label should be gradually shifted from the current predicted label to the ground truth label during training. This result validates our argument that it is not always optimal to feed the learner with ground truth labels. The predicted label is trivial to learn for the current learner (since the learner can output this same prediction without any update) and the optimal label the most difficult learn, revealing a principle that a learner should be taught in an easy-to-hard fashion in order to learn a concept efficiently. This implication nicely matches the conclusions drawn curriculum learning [7], self-paced learning [37], cognitive shaping [17, 34, 62], continuation methods [4] and IMT [43, 44].
Moreover, greedy LAST has the property of teaching monotonicity [43] if the learner loss satisfies certain conditions (See Proposition I for a formal argument). This nice property implies that LAST can always converge w= faster than a random teacher (i.e., SGD) if both of them sample teaching examples uniformly from the pool. An illustration of why LAST yields better convergence to w" given in Fig. 3. We can observe that LAST is guaranteed to better minimize the discrepancy between w and wt for the first iteration both LAST and SGD use the same initialization and training examples. Such guarantee leads to the teaching monotonicity under a few conditions. the learner loss properly designed (e.g., least square loss [43]) such that teaching monotonicity can be satisfied, then LAST will always converge faster than SGD.
Mps
Ias connsr
SGD
L'ST
Figure 3: Example.

---

Proposition 1 (Teaching Monotonicity). Given a learner and randomly sampled teaching data point (x, 9) P for both LAST and a random teacher (SGD), if Ef y w <EG(( y [22) holds for any ; 22 that satisfy TEA [| - -w"ll < <B(1 w [],, then with the same initialization and learning rate, in expectation LAST can converge not slower than the random teacher.
3.2.2 Teaching Neural Learners
We extend the greedy teaching to neural learners. As an illustrative example, we teach two-layer multi-layer perceptron (MLP): /MLP = Erosspy Max W WTo xx)), y) where V IR Xda is the weight matrix of the first layer, W E dR is the weight matrix of the output layer, (+) denotes an element-wise nonlinear function (e.g., ReLU), CrossEntropy(,,? --) is the cross-entropy loss and SoftMax(-) is the softmax function. We denote the intermediate outputs as U=V x and P=)(U). Because the weights for the MLP hierarchically structured, we propose simple yet effective heuristic to teach MLP learners. The training label is generated by
min
W' - 0f(m, vIV', w
aw
1/ ap
0f(m, vlV', W ap aU"
aU
ov
v.
(4)
Discropancy of the output layor: [ -I
Discropancy of the first layer: IVV
where we are using the chain rule to compute TV.. Both P and U are intermediate outputs at the t-th iteration. is a hyperparameter that balances the importance of weights in different layers. When 8 1, it becomes miny [[ yt+ [W*; V*IIl which is equivalent to minimizing the Euclidean distance between the concatenated weight matrices and the desired ones.
3.3 Learning a Parameterized Teaching Policy
The greedy policy only considers v=1 in min min - d(wr++y w²) and it is by no means optimal. We take a step further by considering >>> 1. To approximate mingeti,-.. ,-r 20 tv
w" 1|.
we propose to learn a parameterized teaching policy тe through (i) || w 112.
Unrolling. We can unroll the optimization algorithm of the learner into the teaching objective. In general, we aim to solve the following bi-level nested optimization objective for the teacher:
min w R (0) w 1 s.t. ur (0) = arg F( {f( (o U, w²; ==="" [w))
(5)
where l is the learner loss and To is the parameterized teaching policy that generates the label. For gradient descent learners, w" (0) obtained by unrolling steps of stochastic gradient descent w.s. f. Unrolling is shown useful in [12, 41, 46, 47, 58] and shares similar spirits with
through time recurrent networks [85] and meta-learning [20]. The greedy policy the optimal solution to Eq. (5) for == 1, and the parameterized policy aims to approximate the solution to e>> 1. For large v, unrolling builds a large computational graph for back pook-propagttion and very costly.
Optimizing the unrolled teaching policy is conceptually similar optimizing recurrent neural networks with poopppropagation through time, as illustrated in Fig. 4. Unrolling steps is equivalent to seeking a teaching policy that best minimizes the weight discrepancy after v-step gradient descent. Broadly speaking, our method also has intrin- sic connections to learning an optimizer [5, 39] and teaching a loss function [88] in the sense that both aim to learn better gradients.
Yoi
Lomner Tondder
Wau
Figure 4: Unrolling the teacher.
Policy gradient. We can define r;= - l|w u> the reward sig-
nal and directly apply policy gradient [86] to maximize it. The final teaching objective is to max- imize the expected reward: max, J(Ø): ((0))=EEp J( (=) (als) (- 7"r, at)} where 7 (0. 1] is the discounting factor, T is the termination iteration and (st, ar) is the state-action pair at the f-th iteration. The state is characterized by the sample {x, ÿ) current learner w and optimal learner w'. The action space is a discretized label space. The policy gradient for updating 0 is given by (oJ = ( (a.le))) ) {RVo o Σ'r log To (a: (x)] where R= -'=1 (Se, az). Appendix G gives the details for the state and action. Note that we stick to the simplest policy gradient for demonstration.
Parameterization of the teacher. The teaching policy can be parameterized as any neural network, such as MLP, CNN [25, 27, 33, 49, 52, 70] and transformer [14, 79]. It may also be beneficial to use dynamic networks [23, 30, 48], since the optimal teacher parameters for different input may vary.
3.4 Theoretical Guarantees and Justifications
We first study how label synthesis affects the gradients when the label is a scalar. For LSR learners, the gradient w.r.t. of a single sample (x, (7) is Voll= = ((w, x) V. For LR Iearners, the gradient is
5

---

Vwl= 1+exp(((ww2) Modifying the label is essentially to re-scale the gradient without changing the direction. We denote the new gradient after modifying the label to y as V- (y) w l where g(v) is
(w [) a scalar function of y. For LSR LR learners, we have ( = (ww (o and g = v( (xl+ x))) respectively (ÿ is the original label for æ). In general, the new gradient of linear learners (e.g.. LSR,
w(1+expl g:w a=)) LR and SVM) in greedy LAST can be re- re-written as g(y) w where g(y) varies for different cases. However, in the mini- Mani-batch case, modifying labels will become much more flexible than adjusting the learning rate, since g(y) is generally sample-specific and learning rate is not.
We discuss how g(y) determines the exponential teachability, since LAST can be viewed as modifying g(v) to minimize the model parameter discrepancy. Here we consider the learner to have a loss function f(w) - - (ww) where (,w)) (( - w)) and is the number of samples. We show in Theorem 1 that exponential teachability [43, 44] (i.e. the teacher guides the learner to converge to w" at an exponential speed) can be achieved by intelligently tuning ( in LAST:
Theorem (Exponential teachability). Assume the learner loss E, has the property of interpolation. Li-Lipschitz, and convexity. f is order-1 strongly convex. Then LAST can achieve ET with o(y)=ail c/ll//'- =0 I|, i.e, E [.[[1 w" 11²} S (1 (1-c111jg) -11)) Imaxx )" ||000
= where T'max =
max; L, and μ= h=Σ; Ps/n. It implies that O ) log())) samples are needed to achieve B[ll"" w0] S e. Co =0=1 1===--cimp -1mA++ ozn Lmaxx and C1 is adjusted such that 0 < C1T < Lmax-
Theorem 1 shows that g(y) plays critical role, similar in spirit to the way that in line search, the step size is adaptively adjusted. We emphasize that a random teacher (i.e., vanilla SGD) cannot achieve ET and yields an optimal rate of ( [60] (in order to reach e-approximation of loss value). Additionally, we connect Theorem to Armijo linear search [6, 80] by showing that ET can also be achieved by tuning ( in a more ine-grained way under a different set of conditions:
Theorem (Exponential teachability without target parameters). Assume that the learner loss l, has the property of interpolation, Ls-smoothness, convexity and I hus the property of μ. strong- convexity of order 2. If we adijsst g(y) such that the following condition is always satisfied in each
iteration: li, (w- - nn. Vii, (w")) S. Li, (w') c221.9()) [[V,,,("'] then LAST can achieve ET
for iterative learners with C2 = 1.: B[[l -----w"11 100 S max {(1- p ), (1-jimmax) }} } ||2000 w0'l
which indicates that ((cs log())) samples are needed to achieve B(ll w0' S..
Remark 1 (Meaningfulness of omniscient teaching). A natural question arises: what is the point of the target parameters w if we can achieve ET without it? First of all, both Theorem and Theorem 2 merely consider the case where the synthesized label is a scaler, while labels are usually high-dimensional vectors in practice. When labels are vectors, LAST is much more flexible than tuning the learning rate. Second, the advantages of LAST is reflected in the easiness of setting gly). Because there exists a universal constant ei for -ci] /w''w"',,, g(y) is much easier to set in Theorem 1. In contrast, g(y) in Theorem 2 has to satisfy dynamically changing inequality, which is highly nontrivial. Third, Theorem 2 also shows that Theorem 1 can still be substantially improved and the current lower bound on iterative teaching dimension not necessarily tight.
When the label y is a scalar, LAST can also be viewed as a method that intelligently controls the step size in order to improve convergence to a desired model w". Theorem I is reasonably comparable to the theoretical results in [43, 44], but it does not require to modify æ to achieve ET. In contrast to deterministic ET in [43], LAST achieves probabilistic ET due to the randomness in data sampling. When y becomes a vector, then LAST essentially controls a multi- muutti-dimensioall learning rate that can modify the gradient in more fine- -raiied fashion. As an example, for LSR learners with vector y RRK we have the new gradient matrix of size d x K (after label synthesis) as Vi -Vw. where g(y)= = Hy - (ur,.)) ar)) (1 @ (ÿ- - (ur, x))) (2 denotes the Hadamard division). More interestingly, Theorem 2 also validates the feasibility of black- LAST teaching, since the convergence can be improved even without target parameters. We show in Theorem 3 that super-exponential teachability can be achieved under certain conditions and carefully chosen ggy):
and an optimal weight matrix w" such that V [wf(w")=0, Assume that v [ww) is L-smooth and continuously differentiable within a sufficiently small 8-neighborhood ||w w" <6.. In LAST, the gradient update is wi+11 =w" - ( w (w)). If we have that wo is in the d-neighborhood. Pemin (2' [un))) 2 and Luu <2, then LAST can achieve SUper-ET with g(y)= = (V& (aw"" -
Theorem 3 (Super-exponentia teachability). Consider learner loss [w) = -
(1 a) a)w)) where a [0, 1]. When a 0, the result reduces to Newton's 's method.

---

Theorem 3 can be viewed as generalization of Newton's 's method. In constrast to Newton's 's method, LAST takes advantages of the knowledge of the optimal learner w" and reduces the requirement of the Hessian information. If we simply set a= 1, then LAST only needs a single static (ww" to achieve super-ET. In contrast, Newton's 's method requires ( in every iteration (i.e., Hessian information of a local neighborhood). In the light of [64], we can easily extend Theorem 3 to work with sub-sampled Hessian [ Eia[s) (ww") where S is a subset of indices.
3.5 The Best of Both Worlds? Combining Sample Selection to LAST
It is natural to further consider combining sample selection with LAST. A straightforward approach is to first perform the teaching sample selection in IMT and then run LAST to synthesize the labels for the selected samples. This can be viewed as applying alternating optimization to approximately solve ming,y G(v,, y w²). Specifically, mixed teaching first solves x with y fixed as the original ground truth label, and then solves y with æ fixed. This procedure
SGD
Space
LAST
Mixed
Figure 5: Comparison.
is iterated until sufficiently small error I|w--w" ww'l || is attained. Due to stronger flexibility, this mixed greedy teaching strategy yields more powerful policy than LAST. Based on [43], it is easy to verify that mixed teaching can achieve ET. Fig. 5 gives an illustrative comparison of SGD, LAST and mixed teaching. Unlike LAST that tends to follow the largest gradient direction (same SGD), mixed teaching finds the closest point to w" in the gradient space. Mixed teaching combines label synthesis in LAST with example selection in IMT, and is able to achieve faster teaching empirically.
4 A Distant Look at Black- Label Synthesis Teaching
The previous section considers omniscient teaching where everything about the learner is accessible. However, the optimal learner parameters (w") are often unavailable in practice. This motivates us to study black-box teaching [18, 19, 44, 88] where the teacher knows much less information about the learner. This problem is extremely challenging, but for completeness, we briefly discuss some potential strategies for black-box LAST (BLAST) to tackle this difficult problem and also provide some preliminary experiments in Appendix F.8. Because black-box teacher has no access to w", we need a surrogate objective to efficiently guide the learner to w" arg min E { {((xr ý [- Such a surrogate objective can either be differentiable criterion on a validation set (e.g., some learner loss function) or a non-differentiable performance metric on a validation set (e.g.. validation accuracy). For the former, we can unroll the teacher into the optimization of the learner. For the latter, we can define the performance metric as the reward signal and formulate black- fax teaching as a reinforcement learning problem. Then we utilize the policy gradient method to solve it.
Unrolling. We start with a fully differentiable variant for BLAST. Because w" is no longer available in the black-box scenario, the objective ||w" =w"ll || becomes infeasible. In order to conduct the black-box teaching, we propose to directly use the learner loss ((x, ğ w)) as the surrogate. After removing the dependence on w" from Eq. (5), we obtain the objective function of BLAST:
min E(an))- {f(=, }( s.t. w w² arg min (( (f(zz ( J. w. w [[w)] #
(6)
where ÿ denotes the ground truth label of sample x and the output of тe is the synthesized label y. Da denotes the validation set, and D, denotes the training set. Sometimes as Da and D,,. Here we use stochastic gradient descent to solve the inner minimization. Typically we can unroll e-step gradient updates and train the teacher in an end-to-ent fashion. To reduce the difficulty of learning the teacher in practice, it can be beneficial to parameterize the synthesized label be orÿ + (1 - -a)y'' where E (0, 1) and y =o= (ar, D, w. un"). This is essentially to learn a residue between the synthesized label and the ground truth label. The intuition behind is to constrain the space of synthesized labels such that the black-box teaching can be easier.
can the same set
Policy gradient. We also discuss more general variant for BLAST. We first frame black-box teaching as a reinforcement learning task. Since we have no access to the optimal model w", we use hold-out set to evaluate the performance of the learner (Fig. 6), which also serves the surrogate learning objective. Typically the performance on the hold-out set is non-differentiable w.r.t. O, so we leverage the policy gradient method [86] to learn the teaching policy O. Specifically, we use Saiiingolllii T at)) where T denotes the following objective function: maxe J (() := aa)paa))=p(aaa) (E (s
the termination iteration, (st, az) is the state-action pair at the t-the iteration and re(se, at) is the reward. Since we use a terminal reward R R= (St, az) defined on hold-out set, the objective becomes ((0)= = Emp {R). Therefore, we update the teacher parameters O with 0 VoJ (0) where (oJ = -e Vo log To To(a,)s) We take classification as an illustrative example here.
7

---

Specifically, there are many ways to define the terminal reward, for example, (i) the accuracy after T iterations on the hold-out set, and (ii) the number of iterations to achieve preset accuracy C on the hold-out set (T is the maximal iteration number). We can parameterize the teacher as any approximation method, such as linear classifier or neural network. The learner optimizes its weights by cross-entropy loss and SGD. The teaching policy aims to generate suitable labels for input samples so that the learner can converge efficiently. Fig. 6 illustrates the reinforcement learning formulation. Since there are many choices to design
Reward Signal r
Original Label
Teacher Ae
Synthesize Label
State
Hold-out Data
Action
Randomly Sampled
Learner for
Evaluate
Figure 6: RL formulation for BLAST.
state features, action space and teaching policy, aim to demonstrate the feasibility of applying reinforcement learning to perform black-box teaching instead of enumerating all the design choices.
State. State features are the input for the teacher model and are crucial for learning a good teaching policy. As example for linear learners, we can construct the state features h(s;) with the current learner w. the optimal learner w", the input sample x and the original ground truth label y. For nonlinear learners, it remains an open problem to design informative state features [7, 18, 37].
Action. For small number of classes, we can uniformly discretize the label space (i.e., simplex) into a set of vectors. For example. the binary label space can be discretized into [0, 1]. [0.25, 0. 0.75). [0.5, 0.5]. [0.75, 0.25] and [1,0] 0j. For large number of classes, we need to reduce search difficulty in the label space. For example, inspired by label smoothing (L.S) and knowledge distillation (KD), we can design the synthesized label to be y= μğ +1 (1- H) where ÿ is the one-hot ground truth label. p an all- K vector in LS and is a soft label vector from pretrained model KD (K is the number of classes). We discretize the action space μ E [0.5, 1] and use the reward to guide the search of state-dependent js. The teaching policy produces μ = To (h()))) where To can MLP.
5
Beyond LAST: Intriguing Insights into Iterative Teaching
5.1 Additional Discussions
Practicality of iterative teaching. One of the most significant differences between batch machine teaching (BMT) and IMT is whether learner's optimization algorithm is taken into consideration or not. More generally, IMT views the learner as a specific procedure or algorithm, while BMT views the learner as an objective function. When the objective function becomes non-convex and has multiple equivalent global minima, then could be infeasible for BMT construct a minimal teaching set for guiding the learner to particular target model w". In contrast, IMT can still guide the learner to a specific model by considering the parameter update in every iteration. Overall, IMT makes a paradigm shift from focusing on the learner's 's model to focusing on the learner's 's algorithm.
Iterative teaching as constrained communication. We provide an alternative perspective to look iterative teaching. If we view the teacher as sender and the learner receiver, then the task of iterative teaching is to transmit some information (i.e., the target model w²) from the sender to the receiver. Such information can only be transmitted under a constrained channel. For example, vanilla IMT [43] uses a communication channel that can only transmit teaching examples and LAST uses a channel that only transmits labels. The teacher encodes the target model into teaching examples or labels, and the learner uses a decoder (i.e., its learning algorithm) to recover the target model. The constraints on the communication channel determine the difficulty of iterative teaching.
What makes iterative teaching interesting? First of all, iterative teaching provides a theoretically grounded framework to study how different sequences of training samples (i.e., different data sampling schemes) affects the convergence of learner. More broadly, iterative teaching could help us better understand to what extent the inductive bias can be affected by different sequences of training samples. This has immediate connections curriculum learning [7], self-paced learning [37] and importance sampling [99]. Second, iterative teaching can inspire new heuristics to improve convergence and generalization for complex nonlinear learners (e.g., neural networks) in practice. For example, both vanilla IMT and LAST imply that training a learner with easy samples first and hard samples later can improve convergence. Such an implication can be used to design practical training heuristics. Moreover, black-box iterative teaching is studied to bridge the gap between omniscient iterative teaching and practical machine learning. Third, iterative teaching yields unified framework where the definition of teaching medium is very flexible. We have studied sample selection [43, 44, 91], label synthesis (this paper) and the combination of both ([43] and this paper). Iterative teaching not limited to training data and the efffectiveness of other teaching spaces remains to be explored.
8

---

Open problems. Iterative teaching is still in its infancy and there are numerous open problems in its theory, algorithm and practice. From the theory side, we can only obtain lower bound for the iterative teaching dimension for now. The tightness of such lower bounds remains unknown. Moreover, a upper bound for the iterative teaching dimension and how to loosen assumptions on learners are also important open problems. From the algorithm side, better algorithms to perform omniscient, gray-box or black-box teaching are yet to be designed. In practice, the scalability and efficiency of iterative teaching is also a major bottleneck for large-scale applications [91].
5.2 A Generalized Iterative Teaching Framework
We present a generalized iterative teaching (GIT) framework that considers a broader class of iterative learners (not limited to first-order gradient learners). At the t-th iteration, GIT is formulated as
Learner:
w
(((MM))) Ji w')) Teacher:
arg min {Cmp")mm (1
d (w"+. www
Iterative upuatee function
where M denotes the teaching material (e.g., -M!1 u²) is the i-th training sample in the mini-batch of the j-th iteration), 2 is a general function to denote learner's iterative update rule (e.g., SGD learner uses Q w² nel (ar', y² /'un")) )) l is the learner's objective function, w²' is the learner's model parameters at the t-th iteration and wn is the target parameters. The teacher interacts with the learner every y iterations. Then we denote this generalized teaching problem as GIT v, M, Q). For standard iterative teaching, we use training data as M and the SGD update as Q and abbreviate the problem as (m,, v). For the ultimate IMT problem, we aim to solve GIT 7) where I is the termination iteration. Most prior studies [43, 44, 91] focus on solving GIT(1, 1). while our paper ad- dresses GIT v) where v 2 For strongly convex learners, BMT is equivalent to finding minimal m that solves GIT(m", 0o) under the constraint of M, MM]], Vj. and m² is also the teaching ("MM!'mm"
dimension BMT. Alternatively, BMT also solves GIT(m", 00; {ar, y): (((M) Ji=1, w, f)) where the learner always uses the mini-batch in the first iteration to update itself (and ignores mini-batches in the other iteration). The first mini-batch is the same as the minimal teaching set in BMT.
6 Empirical Evaluation
This section comprehensively evaluates LAST in the omniscient teaching scenario. Experimental details and more results (including BLAST) are given in Appendix G and Appendix F, respectively.
6.1 Omniscient Greedy Teaching
Least square regression learner. We eval- uate LAST on linear regression where the training data is generated by "=ww", x) + (E follows the normal distribution). We compute the training objective value and the Euclidean distance between w' and wn in Fig. 7 to evaluate empirical convergence. For LAST, we test "no constraint" (denoted as "NC") and "magnitude constraint". The results show that LAST generally converges better with a more flexible teacher, and outperforms IMT with magnitude coefficient r 2- This suggests that suitable label may sometimes be more crucial than a suitable input example. We also observe that mixed teaching (LAST+IMT) converges significantly faster than IMT LAST alone. implying that alternating optimization works well.
LAST puit
124
Ttonstin
Figure 7: Convergence curves for linear regression. LAST (x=0.5) denotes LAST with magnitude constraint of r- 0.5.
Logistic regression learner. Next we eval- uate LAST on linear classification for logis- tie regression learners. We teach the logistic regression learner to perform binary clas- sification on both synthetic data and real image data. For synthetic data, we use 2D half moon data and Gaussian cluster data (in Appendix F). For real image data, we use 3/5 digits in MNIST. From Fig. 8, we observe that mixed teaching converges ef- ficiently and consistently achieves the best performance. All variants of LAST significantly outperform SGD. Without constraints, LAST is comparable to IMT in terms of convergence but does not require any costly example selection.
Objanive Volte
ART
LAST cual
300
Hecratin
Figure 8: Binary classification for logistic regression. One- Hot: one-hot constraint, Soft: soft constraints.

---

(a)
Ground Truth
Figure 9: Synthesized labels on half-moon data with 1-hot constraint. (a) ground truth labels. (b,c,d) synthesized
labels by LAST. The purple line the current classifier and the green dotted line the optimal classifier.
Fig. 9 shows how synthesized labels change depending on the learner's parameters. We observe that LAST synthesizes labels adaptively based on the current learner. Our results connect well to the VC theory that the convergence rate depends on how well classifier can separate the data [77]. The synthesized labels are always linearly separable, which effectively improves convergence.
Multi-layer perceptron learner. We apply LAST to neural networks in order to empir- ically show its effectiveness for nonlinear learners. Specifically, we use LAST (3=1) to teach 2-layer MLP with ReLU nonlin- carity (the output layer is essentially a logis- tic regression classifier). We perform binary classification of digit 3 and 5 on MNIST. Results in Fig. 10 show that all the variants of LAST achieve significantly better conver- gence than SGD. With a teacher that generates labels without constraints, both LAST and mixed teaching achieve far better convergence than IMT. LAST is also much more efficient than IMT.
LAST AICM
Darrzee benwees wirdd
Oue
Obiestive 8
Burnttonn
Figure 10: Binary classification for MLP leareers.
Fig. 11 presents some teaching examples for MLP learners in 3/5 MNIST digit classification, where the one-hot labels synthesized by LAST differ from the ground truth. The synthesized labels depend on the learner status and may vary across different iterations. We can observe that most of the examples whose synthesized labels are different from the ground truth ones are semantically ambiguous to humans, suggesting that labels of hard samples near the decision boundary are very crucial for convergence. Moreover, such a observation is consistent for linear learners (see Appendix F.4).
3
GE: LANT:
S
GE& LASE
5
GE:
LAND
lieration 56
lteration 169
lteration 317
3
G
J
GT:S
5
GT:5 LASTE3 590
LAST:S
LAST:3
Ieeration
Iecratinn
Figure 11: Ground truth vs. LAST.
6.2 Omniscient Parameterized Teaching
We learn parameterized teaching policy for logistic regression classifier learners using both unrolling and policy gradient. We parameterize the teacher model with a MLP. Experimental details are given in Appendix G. We evaluate the learned poli- cies on binary classification of digit 3/5 in MNIST. Fig. 12 shows that both unrolling and policy gradient can learn an effective teaching policy that achieves better conver- gence than SGD. Moreover, we evaluate two unrolling settings (20 steps and 100 steps) and unrolling more steps show marginal benefits on con- vergence. On time-wise convergence, we can observe that all variants of LAST performs significantly faster than IMT. because no costly example selection is needed. On tteration-wise convergence, we can see that IMT still achieves the fastest convergence due to its strong flexibility from example selection. LAST with either unrolling or policy gradient converges much faster than SGD, and policy gradient yields slightly better convergence than unrolling in the experiments.
LAST de
201
LAS raad by (00 m0r
Time 60
Tocotoon
Figure 12: Omniscient parameterized teaching on Binary
classification for logistic regression learners. Left: time-wise convergence. Right: iteration- wise convergence.
7 Concluding Remarks
In this paper, we present novel iterative teaching framework via label synthesis. We consider both the omniscient scenario where the teacher has access to the optimal learner parameters and the black-box scenario where the teacher has no access to the optimal learner parameters. We propose greedy teaching and parameterized teaching, and provide theoretical insights on why they can guide the learner to converge quickly. Extensive experiments demonstrate the effectiveness of our methods.
10

---

Acknowledgments
WL is supported by Cumbrrdge-Tübbngeee Fellowship, an NVIDIA GPU grant, DeepMind and the Leverhulme Trust via CFI. AW acknowledges support from Turing AI Fellowship under grant EP/V025379/1, The Alan Turing Institute, and the Leverhulme Trust via CFI. LP is supported by CIFAR AI Chair Program and acknowledges support from Samsung Electronies Co., Ldt. This work was supported by the German Federal Ministry of Education and Research (BMBF): Tübingen AI Center, FKZ: 011$18039B, and by the Machine Learning Cluster of Excellence, EXC number 2064/1
Projecc number 390727645.
References
[1] Pankaj K Agarwal, Sariel Har-Peled, Kasturi R Varadarajan, et al. Geometric approximation via coresets. Combinatorial and computational geometry, 2005,
[2] Scott Alfeld, Xiaojin Zhu, and Paul Barford. Data poisoning attacks against autoregressive models. In AAAL, 2016. 1,2
[3] Scott Alfeld, Xiaojin Zhu, and Paul Barford. Explicit defense actions against test-set attacks. In AAAI, 2017.
[4] Eugene I. Allgower and Kurt Georg. Numerical continuation methods: an introduction, volume 13. Springer Science & Business Media, 2012. 4
[5] Marcin Andrychowicz, Misha Demil, Sergio Gómez Colmenarejo, Matthew Hoffman, David Pfau, Tom Schaul, Brendan Shillingford, and Nando de Freitas. Learning to learn by gradient descent by gradient descent. In NeurlPS, 2016.
[6] Larry Armijo. Minimization of functions having lipschitz continuous first partial derivatives. Pacific Journal of mathematics, 1966.
[7] Yoshua Bengio, Jérôme Louradour, Ronan Collobert, Jason Weston. Curriculum learning. In ICML. 2009. 1, 1,4.8 8
[8] Beidi Chen, Weiyang Liu, Zhiding Yu, Jan Kautz, Anshumali Shrivastava, Animesh Garg, and Animashree Anandkumar. Angular visual hardness. In JCML, 2020.
[9] Yuxin Chen, Oisin Mac Aodha, Shihan Su, Pietro Perona, and Yisong Yue. Near-optimal machine teaching via explanatory teaching sets. In AISTATS, 2018. 2
[10] Yuxin Chen, Adish Singla, Oisin Mac Aodha, Pictro Perona, and Yisong Yue. Understanding the role of adaptivity in machine teaching: The case of version space leamers. In NeurlPS, 2018. 2
[11] Jan Chorowski and Navdeep Jaitly. Towards better decoding and language model integration in sequence to sequence models. arXiv preprint arXiv:1612.02699 2016. 2
[12] Bo Dai, Hanjun Dai, Niao He, Weiyang Liu, Zhen Liu, Jianshu Chen, Lin Xiao, and Le Song, Coupled variational bayes via optimization embedding. In NeurIPS, 2018. 5
[13] Thorsten Doliwa, Gaojian Fan, Hans Ulrich Simon, and Sandra Zilles. Recursive teaching dimension, ve-dimension and sample compression. JMLR, 2014. 2
[14] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition scale. In ICLR, 2020. 5
[15] Baxter S Eaves Jr. Naomi H Feldman. Thomas L Griffiths, and Patrick Shafto. Infant- speech is consistent with teaching. Psychological review, 2016.
[16] Baxter Eaves and Patrick Shafto. Toward general. scaleable framework for bayesian teaching with applications to topic models. arXiv preprint wxXvv1605.007999 2016. 2
[17] Jeffrey L Elman. Learning and development in neural networks: The importance of starting small. Cognition, 1993,
[18] Yang Fan, Fei Tian, Tao Qin, Xiang- Yang Li, and Tie-Yan Liu. Learning teach. In ICLR, 2018. 7,
11

---

[19] Yang Fan, Yingce Xia, Lijun Wu, Shufang Xie, Weiqing Liu, Jiang Bian, Tao Qin, and Xiang-Yang Li. Learning reweight with deep interactions. In AAAI, 2021. 7
[20] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In ICMI., 5
[21] Ziyuan Gao, Hans Ulrich Simon, and Sandra Zilles. On the teaching complexity of linear sets. In ALT, 2015.
[22] S.A. Goldman and M.J. Kearns. On the complexity of teaching. Journal of Computer and System Sciences, 1995.
[23] David Ha, Andrew Dai, and Quoe Le. Hypernetworks. In ICLR, 2016. 5
[24] Luis Haug, Schastian Tschiatschek, and Adish Singla. Teaching inverse reinforcement learners via features and demonstrations. In NeurIPS, 2018.
[25] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. arXiv preprint arXiv: 1512.0388,, 2015.
[26] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge a neural network. arXiv preprint 1roXiv:153.002. 02531, 2015. 2,3
[27] Gao Huang. Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In CVPR, 2017. 5
[28] Jonathan H Huggins, Trevor Campbell, and Tamara Broderick. Coresets for scalable bayesian logistic regression. In NIPS, 2016. I
[29] Anette Hunziker, Yuxin Chen, Oisin Mac Aodha, Manuel Gomez Rodriguez, Andreas Krause, Pietro Perona, Yisong Yue, and Adish Singla. Teaching multiple concepts to forgetful learner. In NeurlPS, 2019.
[30] Xu Jia, Bert De Brabandere, Tinne Tuytelaars, and Lue Van Gool. Dynamic filter networks. In NIPS, 2016.
[31] Edward Johns, Oisin Mac Aodha, and Gabriel J Brostow. Becoming the expert-interactive multi-class machine teaching. CVPR, 2015.
[32] Parameswaran Kamalaruban, Rati Devidze, Volkan Cevher, and Adish Singla. Interactive teaching algorithms for inverse reinforcement learning. arXiv preprint 19X.x:1905.1/800 2019. 2
[33] Alex Krizhevsky, Ila Sutskever. and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In NewrIPS, 2012.
[34] Kai A Krueger and Peter Dayan. Flexible shaping: How learning in small steps helps. Cognition, 2009,
[35] Akash Kumar, Adish Singla, Yisong Yue, and Yuxin Chen, Average-case complexity of teaching convex polytopes via halfspace queries. arXiv preprint arXiv:2006. 14677, 2020.
[36] Akash Kumar, Hanqi Zhang, Adish Singla, and Yuxin Chen. The teaching dimension kemel perceptron. arXiv preprint vrXiv:2010.1404: 2020.
[37] Pawan Kumar, Benjamin Packer, and Daphne Koller. Self-paced learning for latent variable models. In
NeurIPS, 2010. 4, 8
[38] Laurent Lessard, Xuezhou Zhang, and Xiaojin Zhu. An optimal control approach to sequential machine teaching. In AISTATS, 2019. 1,2
[39] Ke Li and Jitendra Malik. Learning to optimize. arXiv preprint arXiv: 2016. 5
[40] Gui-Hua Lin and M Fukushima. Some exact penalty results for nonlinear programs and mathematical programs with equilibrium constraints. Journal of Optimization Theory and Applications. 2003, 18
[41] Rongmei Lin, Weiyang Liu, Zhen Liu, Chen Feng, Zhiding Yu, James M Rehg. Li Xiong, and Le Song. Regularizing neural networks via minimizing hyperspherical energy. In CVPR, 2020. 5
[42] Ji Liu, Xiaojin Zhu, and H Gorune Ohannessian. The teaching dimension of linear learners. In ICML, 2016. 2
12

---

[43] Weiyang Liu, Bo Dai, Ahmad Humayun, Charlene Tay. Chen Yu, Linda B. Smith, James M. Rehg, and Le Song. Iterative machine teaching. In ICML, 2017. 1, 2, 3.4, 4, 6, 8, 27
[44] Weiyang Liu, Bo Dai, Xingguo Li, Zhen Liu, James Rehg, and Le Song. Towards black-box iterative machine teaching. In ICML, 2018. 1, 4, 6, 7. 8,9
[45] Weiyang Liu, Rongmei Lin, Zhen Liu, Lixin Liu, Zhiding Yu, Bo Dai, and Le Song. Learning towards minimum hyperspherical energy. In NeurlPS, 2018.
[46] Weiyang Liu, Rongmei Lin, Zhen Liu, James M Rebg. Liam Paull, Li Xiong, Le Song, and Adrian Weller. Orthogonal over parameterized training. In CVPR, 2021. 5
[47] Weiyang Liu, Rongmei Lin, Zhen Liu, Li Xiong, Bernhard Schölkopf, and Adrian Weller. Learning with hyperspherical uniformity. In AISTATS, 2021. 5
[48] Weiyang Liu, Zhen Liu, James M Rehg, and Le Song. Neural similarity learning. NeurlPS, 2019.
[49] Weiyang Liu, Zhen Liu, Zhiding Yu, Bo Dai, Rongmei Lin, Yisen Wang, James M Rehg, and Le Song. Decoupled networks. In CVPR, 2018. 5
[50] Weiyang Liu, Yandong Wen, Zhiding Yu, Ming Li, Bhiksha Raj, and Le Song. Sphereface: Deep hypersphere embedding for face recognition. CVPR, 2017. 3,23
[51] Weiyang Liu, Yandong Wen, Zhiding Yu, and Meng Yang. Large-margin softmax loss for convolutional neural networks. In ICMI, 2016. 3, 23
[52] Weiyang Liu, Yan-Ming Zhang, Xingguo Li, Zhen Liu, Bo Dai, Tuo Zhao, and Le Song. Deep hyper- spherical learning. In NIPS, 2017. 3,5
[53] David Lopez-Paz, I Léon Bottou, Bernhard Schölkopf, and Vladimir Vapnik. Unifying distillation and privileged information. arXiv preprint arXiv: 1511:01511.0364.. 2015. 2
[54] Yuzhe Ma, Xuezhou Zhang, Wen Sun, and Jerry Zhu. Policy poisoning in batch reinforcement learning and control. NeurlPS, 2019.
[55] Oisin Mac Aodha, Shihan Su. Yuxin Chen, Pietro Perona, and Yisong Yue. Teaching categories to human learners with visual explanations. In CVPR, 2018. 2
[56] Farnam Mansouri, Yuxin Chen, Ara Vartanian, Jerry Zhu, and Adish Singla. Preferenee-basee batch and sequential teaching: Towards unified view of models. In NeurlPS, 2019. 1,2
[57] Shike Mei and Xiaojin Zhu. Using machine teaching to identify optimal training set attacks machine learners. In AAAI, 2015. 2
[58] Vishal Monga, Yuclong Li, and Yonina C Eldar. Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing. IEEE Signal Processing Magazine, 2021.
[59] Rafael Müller, Simon Korbliihh, and Geoffrey E. Hinton. When does label smoothing help? In NeurlPS, 2019.
[60] Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approxi- mation approach to stochastic programming. SIAM Journal on optimization, 2009. 6
[61] Tomi Peltola, Mustafa Mert Çelikok, Pedram Dace, and Samuel Kaski. Machine teaching of active sequential learners. In NeurlPS, 2019.
[62] Gail B Peterson. A day of great illumination: Bf skinner's discovery of shaping. Journal of the experimental analysis of behavior, 2004. 4
[63] Amin Rakhsha, Goran Radanovic, Rati Devidze, Xiaojin Zhu, and Adish Singla. Policy teaching via environment poisoning: Training- time adversarial attacks against reinforcement learning. In ICML, 2020.
1.2
[64] Farbod Khorssan and Michael W Mahoney. Sub-sampled newton methods ii: Local convergence rates, arXiv preprint arXiv:
2016. 7
[65] Rahim Samei, Pavel Semukhin, Boting Yang, and Sandra Zilles. Algebraic methods proving sauer's bound for teaching complexity. Theoretical Computer Science, 2014. 2
13

---

[66] Patrick Shafto and Noah Goodman. Teaching games: Statistical sampling assumptions for learning in pedagogical situations. In CogSci, 2008. 2
[67] Patrick Shafto, Noah D Goodman, and Michael C Frank. Learning from others: The consequences of psychological reasoning for human learning. Perspectives on Psychological Science, 2012.
[68] Patrick Shafto, Noah D Goodman, Thomas Griffiths. A rational account pedagogical reasoning: Teaching by, and learning from, examples. Cognitive psychology, 2014, 2
[69] Patrick Shafto, Junqi Wang. and Pei Wang. Cooperative communication as belief transport. Trends in Cognitive Sciences, 2021. 2
[70] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1556, 2014. 5
[71] Adish Singla, Iija Bogunovic, G Bartók, A Karbasi, and A Krause. On actively teaching the crowd to classify. In NeurlPS Workshop on Data Driven Education, 2013.
[72] Adish Singla, Iija Bogunovic, Gabor Bartok, Amin Karbasi, and Andreas Krause. Ncar-optimally teaching the crowd to classify. In ICML, 2014, 1,2
[73] Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jon Shlens, and Zhigniew Wojna. Rethinking the inception architecture for computer vision. In CVPR, 2016. 2,
[74] Behzad Tabibian, Utkarsh Upadhyay, Abir De, Ali Zarezade, Bernhard Schölkopf, and Manuel Gomez- Rodriguez. Enhancing human learning via spaced repetition optimization. Proceedings of the National Academy of Sciences, 2019. 2
[75] Christian Thiel. Classification on soft labels robust against label noise. In International Conference on Knowledge- Based and Intelligent Information and Engineering Systems, pages 65-73. Springer, 2008.
[76] Sebastian Tschiatschek, Ahana Ghosh, Luis Haug, Rati Devidze, and Adish Singla. Learer-aware teaching: Inverse reinforcement learning with preferences and constraints. In NewrlPS, 2019. 2
[77] Vladimir Vapnik and Rauf Izmailov. Learning using privileged information: similarity control and knowledge transfer. JMLR, 2015. 2, 10
[78] Vladimir Vapnik and Akshay Vashist, A new learning paradigm: Learning using privileged information.
Neural Networks, 22(5):544-555 557, 2009. 2
[79] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkorcit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. arXiv preprint 1oXiv:/706.03760) 2017. 5
[80] Sharan Vaswami, Aaron Mishkin, Issam Laradji, Mark Schmidt, Gauthier Gidel, and Simon Lacoste-Julien. Painless stochastic gradient: Interpolation, line-search, and convergence rates. In NeurlPS, 2019. 6, 18
[81] Feng Wang, Weiyang Liu, Haijun Liu, and Jian Cheng. Additive margin softmax for face verification. arXiv preprint 1801,v188000550000 2018. 23
[82] Junqi Wang, Pei Wang, and Patrick Shafto. Sequential cooperative bayesian inference. In ICMI,, 2020. 2
[83] Pei Wang, Pushpi Paranamana, and Patrick Shafto. Generalizing the theory of cooperative inference. In AISTATS, 2019. 2
[84] Pei Wang. Junqi Wang, Pushpi Paranamana, and Patrick Shafto. A mathematical theory of cooperative communication. In NewrIPS, 2020. 2
[85] Paul J Werbos. Generalization of backpropagation with application recurrent gas market model. Neural networks, 1988. 5
[86] Ronald Williams. Simple statistical gradient- algorithms connectionist reinforcement learning. Machine learning, 1992. 5,7
[87] Laurence A Wolsey and George L Nemhauser. Integer and combinatorial Sons, 1999, 4
combiinaoriallootimizttoon optimization. John Wiley &
[88] Lijun Wu, Fei Tian, Yingee Xia, Yang Fan, Tao Qin, Jianhuang Lai, and Tie- Yan Liu. Learning to teach with dynamic loss functions. In NewrIPS, 2010. 5.7
14

---

[89] Lingxi Xie, Jingdong Wang, Zhen Wei, Meng Wang, and Qi Tian. Disturblabel: Regularizing cnn on the loss layer. In CVPR, 2016. 3.
[90] Qizhe Xie, Minh-Thang Luong, Eduard Hovy, and Quoc V Le. Self-training with noisy student improves imagenet classification. In CVPR, 2020. 3
[91] Zhaozhuo Xu, Beidi Chen, Chaojian Li, Weiyang Liu, Le Song, Yingyan Lin, and Anshumali Shrivastava. Locality sensitive teaching. In NeurlPS, 2021. 2, 8,9
[92] Scott Cheng-Hsae Hsin Yang and Patrick Shafto. Explainable artificial intelligence via bayesian teaching. In NIPS 2017 workshop on Teaching Machines, Robots, and Humans, 2017. 2
[93] Scott Cheng-Hsin Yang. Yue Yu, Pei Wang, Wai Keen Vong, Patrick Shafto, et al. Optimal cooperative inference. In AISTATS, 2018. 2
[94] Teresa Yco, Parameswaran Kamalaruban, Adish Singla, Arpit Merchant, Thibault Asselbom, Louis Faucon, Pierre Dillenbourg, and Volkan Cevher. Iterative classroom teaching. In AAAI, 2019.
[95] Xuezhou Zhang. Shubham Kumar Bharti, Yuzhe Ma, Adish Singla, and Xiaojin Zhu. The teaching dimension of q-learning. arXiv preprint 2rXiv:2006.09324 2020. 2
[96] Xuezhou Zhang, Yuzhe Ma, Adish Singla, and Xiaojin Zhu, Adaptive reward- poisoning attacks against reinforcement leaming. In ICML, 2020.
[97] Xuezhou Zhang, Xiaojin Zhu, and Laurent Lessard. Online data poisoning attacks. In L4DC, 2020. 2
[98] Xuezhou Zhang, Xiaojin Zhu, and Stephen Wright. Training set debugging using trusted items. In AAAI, 2018.
[99] Peilin Zhao and Tong Zhang. Stochastic optimization with importance sampling for regularized loss minimization. In ICML, 2015. 8
[100] Yao Zhou, Arun Reddy Nelakurthi, and Jingrui He. Unlearn what you have learned: Adaptive crowd teaching with exponentially decayed memory learners. In KDD, 2018. 1,
[101] Yao Zhou, Arun Reddy Nelakurthi, Ross Macicjewski, Wei Fan, and Jingrui He. Crowd teaching with imperfect labels. In WWW, 2020. 1.2
[102] Xiaojin Zhu Machine teaching for bayesian learners in the exponential family. In NeurlPS, 2013. 1.2
[103] Xiaojin Zhu. Machine teaching: An inverse problem to machine learning and an approach toward optimal education. In AAAI, 2015. 1,2
[104] Xiaojin Zhu and Andrew Goldberg. Introduction to semi-supervised learning. Synthesis lectures on artificial intelligence and machine learning, 2009. 2,
[105] Xiaojin Zhu, Ji Liu, and Manuel Lopes. No learner left behind: On the complexity of teaching multiple learners simultaneously. In IJCAI, 2017. 2
[106] Xiaojin Zhu, Adish Singla, Sandra Zilles, and Anna N Rafferty. An overview of machine teaching. arXiv preprint arXiv: 005927, 2018.
[107] Bojia Zi, Shihao Zhao, Xingjun Ma, and Yu-Gang Jiang. Revisiting adversarial robustness distillation: Robust soft labels make student better. In ICCV, 2021.
[108] Sandra Zilles, Steffen Lange, Robert Holte, and Martin Zinkevich. Teaching dimensions based on cooperative learning. In COLT, 2008. 2
15


Reviews:
[{"review_id": "sT9OBtLkYs", "reviewer": "Reviewer_7M1p", "summary": "This paper studies the problem of iterative machine teaching with a focus on synthesizing the labels. \n\nSpecifically, the authors deal with the white-box (w* is known, the target parameter) and black-box teaching settings (w* is unknown). For the white-box setting, the authors propose a simple greedy teaching algorithm LAST, which is myopic. To incorporate the long-horizon information, the authors further present two methods: 1) unrolling the gradient steps and 2) learn a teaching policy with RL. These two methods are also applied to deal with the black-box setting.  \nFor the theoretical analysis, the authors cast the effect of label synthesis/teaching as smartly tuning the learning rates, which also enjoys the exponential teachability under the convex and Lipschitz assumptions on the loss functions. \n\nEmpirical results show that the proposed methods are effective and require fewer iterations to converge than standard training (SGD).", "questions": "", "limitations": "", "rating": 7, "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": "This paper proposes three different algorithms for iterative machine teaching based on label synthesis. After reading the paper, I believe the main contribution is that this paper provides another angle to tackle the teaching problem with better computational efficiency compared to prior works. Overall, the proposed algorithms and the theoretical analysis are straightforward and incremental. In addition, the empirical results show that the proposed methods are more efficient than baselines, though there could be further improvements, e.g., the evaluation metric can be improved, the current one may not be suitable to support some of the claims. See detailed comments below. \n\n\n1. Theorem 1 only bounds the expected difference between the learner's parameter w and the target parameter w*, rather than a worst-case bound or a probabilistic bounds. If the variance of the underlying distribution of w is large, then the bound on the expected difference is not informative. Therefore, I believe a probabilistic bound will be necessary.\n\n\n2. In IMT [33], their bound is for the worst-case scenario, whereas your bound is for the average-case scenario. Therefore, I believe the argument \"Theorem 1 is also stronger than the theoretical results in [33, 34],...\" (Line235-236) is misleading. \n\n\n3. Theorem 1 implies a linear convergence rate of LAST, which is the same for first-order optimization methods, such as stochastic gradient descent. Though the teaching monotonicity guarantees that LAST converges faster than SGD, it's still unclear how significant is the gain in terms of iterations? I believe some justifications on this point are essential, as LAST needs extra computational overheads for synthesizing the labels compared to vanilla SGD. \n\n\n4. I think label synthesis is not relatively new and has been studied extensively in the literature. The following closely related works can serve as baselines in the experiments, e.g., Raghu et al. (2021) and Ren et al. (2018).  In particular, in your analysis, the effect of label synthesis can be regarded as tuning the learning rates for each teaching example, which is also equivalent to change the importance/weights of each sample. This perspective is related to Ren et al. (2018), where they also use the validation loss to learn the importance weight of each example by backpropagation (though for a different purpose). I believe it is the same idea as Eqn. (5) and Eqn. (6) in your paper.\n\n\n5. A comparison in terms of the wall-clock time will be helpful. The comparisons using *iterations* are not fair to SGD as it has little overheads compared to your algorithms.\n\n\nQuestions:\n\n6. Why is the cumulative reward not discounted by $\\gamma$ for further steps in BLAST (Line 301)? However, for LAST, the reward is discounted (Line 204). Could you comment on this?\n\n\n7. How do your methods compare to synthesizing the inputs?\n\n\n8. In the introduction (Line 58), you mentioned \"improving the generalization,\" how is this reflected in your analysis? I think this argument is not well-supported, especially for the white-box setting.\n\n9. For parameterized teaching policy, is the teaching policy sensitive to different initializations, optimizers, learning rate and its schedule? Some ablation studies are necessary. In addition, it would be great to have one-standard error in the figure plot. (E.g., sample multiple w that have the same distance to w*, and the run your algorithms).\n\n\nOverall, I think this paper attacks an exciting and essential problem. However, due to the above concerns on the theoretical results, the similarity of the proposed algorithms to prior works, and some of the arguments are not well-supported, I vote for weak rejection. I will increase my score if the authors can address my raised questions&concerns properly.\n\nReferences:\n\n[1] Raghu, Aniruddh, et al. \"Teaching with commentaries.\" ICLR, 2021.\n\n[2] Ren, Mengye, et al. \"Learning to reweight examples for robust deep learning.\"  ICML, 2018", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discussed the societal impact and limitations in the experiments and concluding remarks.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "qxbcwY680gP", "reviewer": "Reviewer_we7s", "summary": "This paper proposes an algorithm for machine teaching that relies on synthesizing labels for randomly selected examples rather than selecting ideal examples.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "Strengths\n- Technique comes with theoretical guarantees\n\nWeaknesses\n- Unclear motivation\n- Unclear meaningfulness of results\n\nThe problem of label synthesis is intriguing due to the effectiveness of using “soft labels” in practice. However, I’m not sure whether this paper provides useful answers to these questions.\n\nIn general, the results in this paper are not sufficiently motivated and explained. For instance, one key question I have is how this approach compares with a naive strategy that both randomly samples examples *and* uses the true labels (instead of the synthesized labels). This seems like a particularly important point of comparison. Under the assumptions made by the authors, how well does this approach perform? Is it provably worse than the proposed approach?\n\nA related issue is that the paper generally does not do a good job of explaining how their results differ from the existing literature on machine teaching. For instance, are the convergence rates the same? Do they make the same assumptions about knowledge of the student loss function and optimal parameters?\n\nFinally, another question I have is about the connection to active learning. There are many active learning algorithms that only make a single pass over the training data -- for instance, [A]. This appears to be applicable to the problem studied in this paper -- basically, only use examples selected by the active learning algorithm for teaching. How do the results in this paper compare to this strategy?\n\n[A] Beygelzimer et al., Agnostic Active Learning Without Constraints. NeurIPS 2010.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "I8q2BnXiMK", "reviewer": "Reviewer_KxBd", "summary": "The manuscript introduces LAST, an iterative approach to teaching by label synthesis. The authors develop an algorithmic framework, derive some theoretical results, and provide empirical analysis of the approach as compared to stochastic gradients, and prior iterative machine teaching methods based on example selection. ", "questions": "", "limitations": "", "rating": 8, "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 paper presents a new approach to machine teaching based on label synthesis. The idea is simple and interesting: instead of selecting examples, which is a hard search problem through the database of examples, the authors propose to randomly select examples an optimize the labels. The resulting approach is flexible and general, as the authors demonstrate through consideration of different types of problems and models. Theoretical results show that the approach allows accelerated convergence as one would hope. Empirical results provide several demonstrations with interesting examples of when and why the approach would deviate from providing ground truth. \n\nStrengths: \n- (see above)\n- Simple, interesting idea with a nice level of generality, effective theory, and empirical results. \n\nWeaknesses:\n- The approach is connected to a large number of literatures, most of which were not reviewed. Given space, it would be hard to do so. However, current discussion of related work omits several literatures mentioned by the authors. Other possible connections include soft supervised approaches and probabilistic versions of teaching / cooperation. \n- The exposition is frustratingly vague at many points. Examples are supplied below. This is the largest weakness of the paper, which is that it is nowhere near self-encapsulated or even clear at many points. I would strongly implore the authors to adjust the exposition as the paper could be much more approachable for the broad audience who might find it interesting. \n\nSpecific questions and comments: \n- \"Then the student keeps learn22 ing from this batch dataset for the target concept.\" What does this mean? \n- \"[29] connects sequential teaching to optimal control and gains interesting insights, but it can not produce a practical teaching policy.\" This is not an adequate discussion of prior work. What constitutes interesting insights? What does \"practical teaching policy\" mean?\n- There are several related literatures that are not discussed. Soft supervised learning is one that comes to mind. A second that is more closely related is the probabilistic literature on teaching and cooperation, e.g. Sequential cooperative bayesian inference. \n- \"Machine teaching is shown useful in reinforcement learning [53, 24, 45, 17], human-in the-loop learning [23, 6, 40], crowd sourcing [50, 67, 68] and cyber security [42, 2, 66, 64, 65]. [10, 14, 74, 47, 6, 26] study machine teaching from a more theoretical aspect.\" Please re-read this sentence. \n- \"We first consider the cleanest teaching protocol following\" What does this mean? Why is it the cleanest? One should provide an explanation for a strong statement. \n- \"All these methods can be viewed as using a customized label synthesis policy in the black-box teaching scenario\" It would be nice to have a more precise statement of this claim. \n- Given that the approach unifies knowledge distillation, label smoothing, and self-training, it would be good to review at least some work in those literatures too. \n- \" This result validates our argument that it is not always optimal to feed the learner with ground truth label\" I am not sure validates is the word you want here. Validation seems best provided by empirical demonstrations that it works on real data. \"Is consistent with\" may be a more suitable choice. \n- The move from predicted to ground truth labels is interesting. I would be interested to hear the author's thoughts on probabilistic interpretations. \n- \" The predicted label is usually easy to learn for the current learner and the optimal label is more difficult to learn, implying that the learner should be taught in an easy-to-hard fashion.\" It would be helpful to explain why the predicted label is usually easy. \n- \"This implication nicely matches the conclusion in curriculum learning [5] and IM\" What conclusion? \n- \" Moreover, greedy LAST also has the property of teaching monotonicity [33] if the learner loss satisfies certain conditions (Appendix C).\" The conditions should be stated in the main text. \n- Figure 3 didn't help me much. It would require more explaining in the caption than simply \"example\". \n- \" This nice property implies that LAST always converges to w∗ faster than a random teacher (i.e., SGD) if both of them sample teaching examples uniformly from the pool. An\nillustration of how LAST works and why LAST yields better convergence to w∗ is given in Fig. 3. If the learner loss is properly designed, LAST can converge faster than SGD\" These passages are repetitive and do not effectively explain. \n- \" The teaching monotonicity comes from the first iteration where the gradient update in LAST is guaranteed to better minimize the discrepancy between w1 and w∗.\" A more precise derivation/comparison would be helpful. \n- \" we propose a simple yet effective heuristic to teach MLP learners.\" How do we know this is an effective heuristic? A more detailed exposition here would be nice. \n- \" This shares similar spirits with back-propagation through time in recurrent networks and meta-learning\" What does this mean? A more precise statement would be desirable. \n- \" The greedy policy is in fact the optimal solution to Eq. (5) for T = 1. For larger T, unrolling builds a larger computational graph for back-propagation and is more costly\". It is helpful for the reader to provide a clear statement of why optimality is obtained. Also, given that computational considerations are one of the arguments in favor of LAST, an analysis of computational complexity here would clarify the argument. \n- \"Optimizing the unrolled teaching policy is conceptually similar to optimizing recurrent neural networks with back-propagation through time, as illustrated in Fig. 4. Unrolling T steps is equivalent to seeking a teaching policy that best minimizes the weight discrepancy after T-step gradient descent. Broadly speaking, our method also has intrinsic connections to learning an optimizer [4, 30] and teaching a loss function [61] in the sense that both aim to learn better gradients.\" Again, more precise statements would be helpful. \n- \"We can simply define rt =−kwt −w∗ k as the reward and directly apply policy gradient [59] to solve it.\" Please explain more. \n- Theorem 1 contains several terms that are not defined. \n- \"Theorem 1 shows that g(y) plays a critical role, similar in spirit to the way that in line search, the step size is adaptively adjusted.\" Please re-read the sentence. \n- \"We connect Theorem 1 to Armijo linear search\"  A more precise term than connect would be desirable. \n- Figure 5 did not help me. The caption is inadequate. \n- \"Based on [33], it is easy to verify that mixed teaching can achieve ET\" Please explain. \n- \"is able to achieve faster teaching empirically\" please point to where this is demonstrated. \n- The discussion of the data in figure 11 is interesting! (but not convincing) I would be interested to hear more about this. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No limitations are acknowledged and societal impact is not discussed. ", "review_text": "", "extra_scores": {"ethical_concerns": "None. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "-YemWRsFe2N", "reviewer": "Reviewer_vxUV", "summary": "This paper proposes to address the sequential machine teaching problem by synthesizing labels. The proposed method is termed LAST. LAST avoids the expensive data selection and still provably improves the convergence of the learner. Specifically, LAST considers two types of teacher models: greedy teacher and parameterized teacher. For the parameterized teacher, the paper proposes unrolling and policy gradients to learn it. The theoretical justification is thorough and convincing. The experiments are comprehensive and well designed. They cover almost every setting one can think of. The empirical performance shows sufficient gains to support the major argument that LAST can effectively improve convergence.", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "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": "This paper is an interesting and enjoyable read. I like the overall idea of label synthesis teaching and how the paper executes the idea in a rather comprehensive way. More importantly, I find this paper quite inspiring and I have also learned a few useful insights from this paper. I summarize the strengths and potential weaknesses below.\n\n** Strengths\n\n- The proposed teaching framework is novel and well motivated. The paper studies a number of interesting variants under this framework. I believe this may be one of the first works that comprehensively study how modifying labels can affect convergence (in the supervised learning context). And this framework could potentially bridge the gap between sequential machine teaching and practical applications, since data selection is obviously not scalable enough for modern large-scale datasets.\n\n- In general, labels are typically treated as a static learning signal in supervised learning. I think the proposed teaching framework suggests making such a static learning signal to be dynamically dependent on data and the learner model. This is conceptually novel and convincing to me, since uniform [1] and random [2] perturbation of the label can contribute to generalization, why not learn a teacher model to do this perturbation automatically in a data-driven way. I am convinced by this conceptual motivation (as mentioned in the introduction of the paper).\n\n- While the proposed greedy LAST algorithm is simple and straightforward, the interpretation in Eq.(3) is super interesting and inspiring. The finding essentially suggests that in the linear setting, the optimal synthesized label for greedy teaching is a linear interpolation between the predicted label and the optimal label. I think this finding makes intuitive sense but there could be much more going on behind. In practice, I think this also gives us some guidance for how we can augment our labels to improve convergence and generalization.\n\n- The idea of parameterizing the teacher with a neural network is novel and appealing in practice, as it makes the teacher much more scalable in terms of inference and also easier to train. In order to learn such a parameterized teacher, the paper proposes to use either unrolling or policy gradients. I think both are natural and effective choices. Unrolling could be more sample-efficient when the number of unrolling steps is sufficiently large.\n\n- The paper also provides theoretical justifications of why LAST can achieve better convergence. They managed to achieve the same convergence rate as [2] by only modifying the labels, which seems to be a stronger result than [3].\n\n- The experiments are well conducted and are very comprehensive. The LAST teaching framework generally shows consistently better convergence and generalization compared to the other methods. I like the fact that this paper uses quite a practice setting for sequential machine teaching, compared to prior work [3,4]. In the case of black-box teaching, the paper also compares a practical method L2T [5] (a RL-based data selection method), and shows better results. I believe this is quite encouraging and impressive.\n\n- Figure 9 in the paper gives some empirical evidence and insights of how the synthesized labels look like. This is actually reflecting what the second point of strengths mentioned -- dynamic labels could potentially be better than static labels.\n\n[1] Rethinking the Inception Architecture for Computer Vision, CVPR 2016\n[2] DisturbLabel: Regularizing CNN on the Loss Layer, CVPR 2016\n[3] Iterative Machine Teaching, ICML 2017\n[4] An Optimal Control Approach to Sequential Machine Teaching, AISTATS 2019\n[5] Learning to Teach, ICLR 2018\n\n\n** Weaknesses\n\n- Similar to most papers in machine teaching, the experimental setting is still far away from practical use and can only serve as a proof of concept. Although this paper already employs more practical experimental settings and relatively realistic datasets, the gap could be still further minimized.\n\n- It will be more informative to test the convergence with respect to time in order to show the *real* convergence that people will care about in practice.\n\n- I think unrolling generally takes a huge amount of GPU memory, which needs more discussions and justifications in the paper.\n\n- The related work section can be improved by giving a more detailed discussion and comparison between LAST and the existing work.\n\n- The paper is written in a dense manner and proposes a number of things. This is by no means a critical weakness, but making the paper too dense could distract the reader from understanding the essential idea of the paper. I would suggest authors try to restructure the content a bit. Maybe put some of the less important content to the appendix. Some of the content in the current appendix seems quite interesting (e.g. the connection to Armijo line search) and may be worth taking to the main paper.\n\n\n** Additional Suggestions\n\n- This paper actually raises a very interesting question “what are the best possible labels for supervised learning?”. I believe constructing dynamic data-model-dependent labels is actually a promising direction to explore. Beyond this, I think the label teaching is closely connected to information theory (mutual information, coding theory and data compression). Although I don’t have a clear picture of how these things are connected, it is obvious that a learner model tries to bridge the information encoded in the input and the labels. I suggest the authors dig deeper into this.\n\n- The connection to privileged information is very interesting but not too obvious to me. I think the authors can elaborate more on this.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See sections above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "25"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studied an interesting yet challenging problem in machine teaching and provided an intuitive teaching algorithm for synthesizing labels for teaching with theoretical analysis and justifications. All reviewers agree that the problem studied in this paper is practically relevant, with rigorous theoretical analysis and justifications. Empirical results on several large data sets seem promising. 

Meanwhile, there were common concerns in the positioning of the work, in particular in the lack of discussion of connections to related work, and some reviews concern the clarity of the presentation (e.g. missing some details in experimental results such as computation time), and the significance of the theoretical contribution (e.g. whether the average-case bound is significant for practical scenarios). The authors provided effective feedback during the discussion phase, which helped clarify many of the above concerns. Should these concerns be addressed in the revision, it would make a solid paper. The authors are encouraged to take into account the feedback from the discussion phase to further improve the discussion of the proposed algorithm.

Decision: Accept (Spotlight)