Iterative Teaching by Label Synthesis

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.

heading: 1 Introduction
text: Machine teaching [103, 106] studies the problem of constructing a 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, 3, 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 a teacher constructs a minimal batch set of training samples and provides it to a student in one shot without further interactions. Then the student keeps learning from this batch dataset for the target concept. The size of such a 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 is iterative machine teaching (IMT) [43, 44] where the teacher guides a 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 teaching 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( m k )n possible teaching trajectories (n is the number of iterations) if we select k samples per iteration from a pool of size m. Due to such a huge search space, the selection of teaching examples is a 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 of the dataset.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
We propose a 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 in 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 a pretrained model can generally improve generalization. Label smoothing demonstrates that the ground truth labels are not necessarily the optimal supervision for training a 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 a 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 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 to perform LAST in this case. LAST provides a unified view for understanding soft label methods, e.g., knowledge distillation [26, 53], 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.

heading: 2 Related Work
text: 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 convergence. [38] connects sequential teaching to optimal control and gains interesting insights, but it can not produce a practical teaching policy. [91] uses locality-sensitive sampling to scale IMT to largescale problems. Machine teaching is shown useful in reinforcement learning [24, 32, 63, 76], humanin-the-loop learning [9, 31, 55], crowd sourcing [72, 100, 101] and cyber security [2, 57, 96, 97, 98]. [9, 13, 21, 35, 65, 108] study machine teaching from a more theoretical point of view. Cooperative communication. Cooperative communication [69] is a mutual theory of mind reasoning between a teacher and a learner. The teacher selects data to convey a hypothesis and the learner infers a 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 a probabilistic inference framework, LAST addresses the iterative teaching with a 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 a student model, which can make the student model generalize
better than a trained-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.

heading: 3 Label Synthesis Teaching
text: 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 wi at the i-th iteration, the learning rate ηi, the loss function ` and the specific optimization algorithm (e.g., SGD). For interaction, the teacher can only communicate with the learner via examples {(xij ,yij)}j=1,··· ,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 w converge to desired parameters w∗ as fast as possible. For example, w∗ typically is arg minw E(x,y){`(x,y|w)}. Therefore, a general objective for any teaching algorithm is min{(x1,y1),··· ,(xT ,yT )} d(wT ,w∗) where T denotes the termination iteration for the teaching algorithm. We use batch size 1 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 a teaching trajectory that is terminated at the T -th step such that the discrepancy between the current learner parameters and the desired learner 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 sample selection, the LAST framework instead optimizes the teaching examples in the label space, and the corresponding objective becomes min{y1,··· ,yT } d(w
T ,w∗) where x1, · · · ,xT 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 on the ran-
domly sampled {x, ỹ} and the learner’s current and desired model (i.e., parameters). Therefore, we can formulate the corresponding label synthesis policy as y=πθ(x, ỹ,wt,w∗) where π is optionally parameterized by θ and ỹ denotes the original ground truth label. Then the teaching objective becomes arg minπθ d(w
T ,w∗). An overview of LAST is given in Fig. 2. Moreover, LAST provides a unified framework for knowledge distillation, label smoothing and self-training. Knowledge distillation [26] generates the label with the policy yi=
exp(zi(x)/ψ)∑ j exp(zj(x)/ψ) where ψ is the temperature
and zi(x) is the i-th logit output of x from a pretrained neural network. Label smoothing [73] uses y=µỹ+ 1−µK 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.

heading: 3.2 Greedy Teaching Policy
text: For the t-th iteration, we can approximately solve the original teaching problem with the optimization min{yt+1,··· ,yt+v} d(w
t+v,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 minyt d(wt+1,w∗) where wt+1 is one-step update from the current learnerwt w.r.t. the learner loss ` and example {xt,yt}. 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 xt at the t-th iteration is produced by
min yt {∥∥∥∥∥wt−1−ηt ∂`(xt,yt|wt−1)∂wt−1 −w∗ ∥∥∥∥∥ 2
2︸ ︷︷ ︸ G(xt,yt|wt−1)
} ⇒min
yt
{ η2t ∥∥∥∥∥∂`(xt,yt|wt−1)∂wt−1 ∥∥∥∥∥ 2
2︸ ︷︷ ︸ T1(xt,yt|wt−1)
−2ηt〈wt−1−w∗, ∂`(x t,yt|wt−1) ∂wt−1
〉︸ ︷︷ ︸ T2(xt,yt|wt−1)
} (1)
where `(xt,yt|wt) denotes the loss function of the learner andwt is the learner parameter in the t-th iteration. For simplicity, we consider the mini-batch size as 1. It is straightforward to write Eq. (1)
in a 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 to IMT, which aims to optimize the sample xt, the greedy teaching in LAST first randomly samples the teaching example and then optimize the label based on arg minyt η2t T1(x
t,yt|wt)−2ηtT2(xt,yt|wt). 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 1 Omniscient Greedy LAST Initialize t=1,w0, and T ; while ‖wt −w∗‖2 ≥ or t ≤ T do
Randomly select a sample xt from the pool; Solve Eq. (1) to synthesize the label yt: Use the synthesized label yt for the update:
w t = w t−1 − ηt ∂`(xt,yt|wt) ∂wt ;
Set t← t+ 1; end
One-hot constraint. For classification tasks, we can constrain the teacher to synthesize one-hot labels for x. With the one-hot constraint, label synthesis becomes a standard integer programming problem [87]. Soft constraint. A straightforward relaxation of the one-hot constraint is to constrain the labels on a probability simplex, i.e., ∑ i yi=1 and yi≥0,∀i, and it becomes a constrained optimization problem. Magnitude constraint. For regression, we can constrain the p-norm of the label vector to be smaller than a positive constant r, i.e., ‖y−〈wt,x〉‖p≤r (for constraining the synthesized label to be around the current prediction) or ‖y− ỹ‖p≤r (for constraining the synthesized label to be around the ground truth label), where we usually use p=2. A larger magnitude r indicates a more flexible and powerful teacher. For classification, we can use the same magnitude constraints (optionally) along with soft constraints ∑ i yi=1 and yi≥0,∀i. 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).

heading: 3.2.1 Teaching Linear Learners
text: 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: `LSR(x, y|w)= 12 (〈w,x〉−y)
2 for the LSR learner and `LR(x, y|w)= log(1+exp{−y〈w,x〉}) for the LR learner. {x[i], y[i]} is the i-th sample in the pool. We gain intuitions by looking at the synthesized label. Taking LSR as an concrete example, Eq (1) becomes
min y η2t 〈x,x〉y2+
( 2ηt〈w−w∗,x〉−2η2t 〈x,x〉〈w,x〉 ) y+η2t 〈x,x〉〈w,x〉−2ηt〈w,x〉〈w−w∗,x〉 (2)
from which we can obtain the closed-form solution for the synthesized label as
y∗ = 2η2t 〈x,x〉〈w,x〉 − 2ηt〈w −w∗,x〉
2η2t 〈x,x〉︸ ︷︷ ︸ Synthesized label
= (1− λ) · 〈w,x〉︸ ︷︷ ︸ Predicted label – easy +λ · 〈w∗,x〉︸ ︷︷ ︸ Optimal label – hard (3)
where λ=(ηt〈x,x〉)−1. λ is essentially a parameter that weights the importance between using the current prediction as the training label and using the (pseudo) ground truth label as the training label. Suppose that the input data lies on a hypersphere with radius γ, then we have λ= 1ηtγ2 . Typically ηt will gradually decrease during training, so λ 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 is the most difficult to 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 in 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 1 for a formal argument). This nice property implies that LAST can always converge to 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∗ is given in Fig. 3. We can observe that LAST is guaranteed to better minimize the discrepancy betweenw1 andw∗ for the first iteration if both LAST and SGD use
the same initialization and training examples. Such a guarantee leads to the teaching monotonicity under a few conditions. If the learner loss is properly designed (e.g., least square loss [43]) such that teaching monotonicity can be satisfied, then LAST will always converge faster than SGD.
Proposition 1 (Teaching Monotonicity). Given a learner ` and a randomly sampled teaching data point (x, ỹ)∼P for both LAST and a random teacher (SGD), if E{G(x, y|w1)}≤E{G(x, y|w2)} holds for anyw1,w2 that satisfy E{‖w1−w∗‖}≤E{‖w2−w∗‖}, then with the same initialization and learning rate, in expectation LAST can converge not slower than the random teacher.

heading: 3.2.2 Teaching Neural Learners
text: We extend the greedy teaching to neural learners. As an illustrative example, we teach a two-layer multi-layer perceptron (MLP): `MLP =CrossEntropy(SoftMax(W>σ(V >x)),y) whereV ∈Rd1×d2 is the weight matrix of the first layer, W ∈Rd2×K 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 are hierarchically structured, we propose a simple yet effective heuristic to teach MLP learners. The training label is generated by
min y ∥∥∥∥W t− ηt ∂`(x,y|V t,W t)∂W t −W ∗ ∥∥∥∥2 F︸ ︷︷ ︸
Discrepancy of the output layer: ‖W t+1−W ∗‖
+β ∥∥∥∥V t− ηt ∂`(x,y|V t,W t)∂P t ◦ ∂P t ∂Ut ◦ ∂Ut ∂V t − V ∗ ∥∥∥∥2 F︸ ︷︷ ︸
Discrepancy of the first layer: ‖V t+1−V ∗‖
(4)
where we are using the chain rule to compute ∂`∂V t . Both P t and U t are intermediate outputs at the t-th iteration. β is a hyperparameter that balances the importance of weights in different layers. When β=1, it becomes miny ‖[W t+1;V t+1]− [W ∗;V ∗]‖2F which is equivalent to minimizing the Euclidean distance between the concatenated weight matrices and the desired ones.

heading: 3.3 Learning a Parameterized Teaching Policy
text: The greedy policy only considers v=1 in min{yt+1,··· ,yt+v} d(wt+v,w∗) and it is by no means optimal. We take a step further by considering v>1. To approximate minyt+1,··· ,yt+v ‖wt+v−w∗‖22, we propose to learn a parameterized teaching policy πθ through minπ(θ) ‖wt+v−w∗‖22. 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 θ ‖wv(θ)−w∗‖22 s.t. w v(θ) = argmin w
E{x,ỹ} { `(x, πθ(x, ỹ,w t,w∗)|w) }
(5)
where ` is the learner loss and πθ is the parameterized teaching policy that generates the label. For gradient descent learners, wv(θ) is obtained by unrolling v steps of stochastic gradient descent w.r.t. `. Unrolling is shown useful in [12, 41, 46, 47, 58] and shares similar spirits with back-propagation through time in recurrent networks [85] and meta-learning [20]. The greedy policy is the optimal solution to Eq. (5) for v=1, and the parameterized policy aims to approximate the solution to v>1. For large v, unrolling builds a large computational graph for back-propagation and is very costly.
Optimizing the unrolled teaching policy is conceptually similar to optimizing recurrent neural networks with back-propagation through time, as illustrated in Fig. 4. Unrolling v 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 intrinsic connections to learning an optimizer [5, 39] and teaching a loss function [88] in the sense that both aim to learn better gradients. Policy gradient. We can define rt=−‖wt−w∗‖ as the reward sig-
nal and directly apply policy gradient [86] to maximize it. The final teaching objective is to maximize the expected reward: maxθ J(θ) :=E(st,at)∼πθ(a|s){ ∑T t=1 γ
trt(st, at)} where γ∈(0, 1] is the discounting factor, T is the termination iteration and (st, at) is the state-action pair at the t-th iteration. The state is characterized by the sample {x, ỹ}, current learner w and optimal learner w∗. The action space is a discretized label space. The policy gradient for updating θ is given by ∇θJ(θ)=Eπθ(at|st){R∇θ ∑T t=1 log πθ(at|st)} where R= ∑T t=1 γ
trt(st, at). 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.

heading: 3.4 Theoretical Guarantees and Justifications
text: We first study how label synthesis affects the gradients when the label is a scalar. For LSR learners, the gradient w.r.t. w of a single sample (x, ỹ) is ∇w`=(〈w,x〉− ỹ)x. For LR learners, the gradient is
∇w`= −ỹx1+exp(ỹ〈w,x〉) . 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∇′w`=g(y)∇w`where g(y) is a scalar function of y. For LSR and LR learners, we have g(y)= 〈w,x〉−y〈w,x〉−ỹ and g(y)= y(1+exp(ỹ〈w,x〉)) ỹ(1+exp(y〈w,x〉)) , respectively (ỹ is the original label for x). In general, the new gradient of linear learners (e.g., LSR, LR and SVM) in greedy LAST can be re-written as g(y)∇w` where g(y) varies for different cases. However, in the mini-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(y) to minimize the model parameter discrepancy. Here we consider the learner to have a loss function f(w)= ∑n i=1 `i(w) where `i(w)=`(x[i], y[i]|w) and n 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 g(y) in LAST:
Theorem 1 (Exponential teachability). Assume the learner loss `i has the property of interpolation, Li-Lipschitz, and convexity. f is order-1 µ strongly convex. Then LAST can achieve ET with g(y)=c1‖wt−w∗‖, i.e., E{‖wT −w∗‖2} ≤ (1−c1ηtµ̄+c21η2tLmax)T ∥∥w0 −w∗∥∥2 where Lmax = maxi Li and µ̄= ∑ i µi/n. It implies that O((log 1 c0
)−1 log( 1 )) samples are needed to achieve E{‖wT −w∗‖2} ≤ . c0 =1−c1ηtµ̄+c21η2tLmax and c1 is adjusted such that 0 < c1ηt < µ̄/Lmax. 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. We emphasize that a random teacher (i.e., vanilla SGD) cannot achieve ET and yields an optimal rate of O( 1 ) [60] (in order to reach -approximation of loss value). Additionally, we connect Theorem 1 to Armijo linear search [6, 80] by showing that ET can also be achieved by tuning g(y) in a more fine-grained way under a different set of conditions:
Theorem 2 (Exponential teachability without target parameters). Assume that the learner loss `i has the property of interpolation, Li-smoothness, convexity and f has the property of µ strongconvexity of order 2. If we adjust g(y) such that the following condition is always satisfied in each iteration: `it(w t−ηtg(y)∇`it(wt))≤`it(wt)−c2ηtg(y) ‖∇`it(wt)‖ 2, then LAST can achieve ET for iterative learners with c2 = 12 : E{‖w T −w∗‖2}≤max { (1− µ̄Lmax ), (1− µ̄η ′ max)
}T ∥∥w0−w∗∥∥2 which indicates that O(c3 log( 1 )) samples are needed to achieve E{‖w
T −w∗‖2} ≤ . 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 1 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 g(y). Because there exists a universal constant c1 for g(y)=c1‖wt−w∗‖, g(y) is much easier to set in Theorem 1. In contrast, g(y) in Theorem 2 has to satisfy a 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 is 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 1 is reasonably comparable to the theoretical results in [43, 44], but it does not require to modify x 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-dimensional learning rate that can modify the gradient in a more fine-grained fashion. As an example, for LSR learners with a vector y∈RK , we have the new gradient matrix of size d×K (after label synthesis) as ∇′w`=g(y) ·∇w` where g(y)= 1d (y−〈w,x〉) ·(1 (ỹ−〈w,x〉)) ( denotes the Hadamard division). More interestingly, Theorem 2 also validates the feasibility of black-box 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 a carefully chosen g(y):
Theorem 3 (Super-exponential teachability). Consider a learner loss f(w)= ∑n i=1 `i(w) and an optimal weight matrix w∗ such that ∇wf(w∗)=0. Assume that ∇wf(w) is L-smooth and continuously differentiable within a sufficiently small δ-neighborhood ‖w−w∗‖≤δ. In LAST, the gradient update is wt+1 =wt−ηtg(y)∇wf(w). If we have that w0 is in the δ-neighborhood, |λmin(∇2wf(w))|≥µ and Lµδ<2, then LAST can achieve super-ET with g(y)=η−1t (∇2wf(αw∗+ (1−α)w))−1 where α∈ [0, 1]. When α=0, the result reduces to Newton’s method.
Theorem 3 can be viewed as a generalization of Newton’s method. In constrast to Newton’s method, LAST takes advantages of the knowledge of the optimal learnerw∗ and reduces the requirement of the Hessian information. If we simply set α=1, then LAST only needs a single static ∇2wf(w∗) to achieve super-ET. In contrast, Newton’s method requires ∇2wf(w) 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 1|S| ∑ i∈|S|∇2w`i(w∗) 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 minx,y G(x,y|wt). Specifically, mixed teaching first solves xwith y fixed as the original ground truth label, and then solves y with x fixed. This procedure
is iterated until sufficiently small error ‖w∗−wt‖ is attained. Due to stronger flexibility, this mixed greedy teaching strategy yields a 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 as 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.

heading: 4 A Distant Look at Black-box Label Synthesis Teaching
text: 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 a black-box teacher has no access tow∗, we need to use a surrogate objective to efficiently guide the learner tow∗=arg minw E(x,y){`(x, ỹ|w)}. Such a surrogate objective can either be a 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-box 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 ‖wv−w∗‖ becomes infeasible. In order to conduct the black-box teaching, we propose to directly use the learner loss `(x, ỹ|w) as the surrogate. After removing the dependence on w∗ from Eq. (5), we obtain the objective function of BLAST:
min θ
E{x,ỹ}∼Da { `(x, ỹ|wv) } s.t. wv(θ) = argmin
w E{x,ỹ}∼Dr
{ `(x, πθ(x, ỹ,w,w ∗)|w) } (6)
where ỹ denotes the ground truth label of sample x and the output of πθ is the synthesized label y. Da denotes the validation set, and Dr denotes the training set. Sometimes we can use the same set as Da and Dr. Here we use stochastic gradient descent to solve the inner minimization. Typically we can unroll v-step gradient updates and train the teacher in an end-to-end fashion. To reduce the difficulty of learning the teacher in practice, it can be beneficial to parameterize the synthesized label to be αỹ+(1−α)y′ where α∈(0, 1) and y′=πθ(x, ỹ,w,w∗). 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. Policy gradient. We also discuss a more general variant for BLAST. We first frame black-box teaching as a reinforcement learning task. Since we have no access to the optimal modelw∗, we use a hold-out set to evaluate the performance of the learner (Fig. 6), which also serves as the surrogate learning objective. Typically the performance on the hold-out set is non-differentiable w.r.t. θ, so we leverage the policy gradient method [86] to learn the teaching policy θ. Specifically, we use the following objective function: maxθ J(θ) := E(st,at)∼πθ(a|s){ ∑T t=1 rt(st, at)} where T denotes the termination iteration, (st, at) is the state-action pair at the t-the iteration and rt(st, at) is the reward. Since we use a terminal reward R=rT (st, at) defined on a hold-out set, the objective becomes J(θ)=Eπθ{R}. Therefore, we update the teacher parameters θ with θ←θ+η ·∇θJ(θ) where ∇θJ(θ)= ∑ t∇θ log πθ(at|st)R. We take classification as an illustrative example here.
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 a preset accuracy ζ 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
state features, action space and teaching policy, we 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 an example for linear learners, we can construct the state features h(st) 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.75], [0.5, 0.5], [0.75, 0.25] and [1, 0]. For large number of classes, we need to reduce search difficulty in the label space. For example, inspired by label smoothing (LS) and knowledge distillation (KD), we can design the synthesized label to be y=µỹ+(1−µ)p where ỹ is the one-hot ground truth label. p is an all- 1K vector in LS and is a soft label vector from a pretrained model in KD (K is the number of classes). We discretize the action space µ∈ [0.5, 1] and use the reward to guide the search of state-dependent µ. The teaching policy produces µt=πθ(h(st)) where πθ can be a MLP.

heading: 5 Beyond LAST: Intriguing Insights into Iterative Teaching

heading: 5.1 Additional Discussions
text: 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 it could be infeasible for BMT to construct a minimal teaching set for guiding the learner to a 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 model to focusing on the learner’s algorithm. Iterative teaching as constrained communication. We provide an alternative perspective to look at iterative teaching. If we view the teacher as a sender and the learner as a receiver, then the task of iterative teaching is to transmit some information (i.e., the target modelw∗) 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 a 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 to 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 a 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 is not limited to training data and the effectiveness of other teaching spaces remains to be explored.
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 a 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].

heading: 5.2 A Generalized Iterative Teaching Framework
text: 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: wt+1 = Q ( {M[t]i } m i=1,w t, ` )︸ ︷︷ ︸
Iterative update function
Teacher: argmin{ {M[1]i } m i=1,··· ,{M [v] i } m i=1 } d (wt+v,w∗) (7) where M denotes the teaching material (e.g., M[j]i ={x j i ,y j i } is the i-th training sample in the mini-batch of the j-th iteration), Q is a general function to denote learner’s iterative update rule (e.g., SGD learner uses Q=wt−ηt`′(xt,yt|wt)), ` is the learner’s objective function, wt is the learner’s model parameters at the t-th iteration andw∗ is the target parameters. The teacher interacts with the learner every v iterations. Then we denote this generalized teaching problem as GIT(m, v,M,Q). For standard iterative teaching, we use training data asM and the SGD update as Q and abbreviate the problem as GIT(m, v). For the ultimate IMT problem, we aim to solve GIT(m,T ) where T is the termination iteration. Most prior studies [43, 44, 91] focus on solving GIT(1, 1), while our paper addresses GIT(1, v) where v≥1. For strongly convex learners, BMT is equivalent to finding a minimal m∗ that solves GIT(m∗,∞) under the constraint ofM[1]i =M [j] i ,∀j, and m∗ is also the teaching dimension in BMT. Alternatively, BMT also solves GIT(m∗,∞, {x,y},Q({M[1]i }m ∗
i=1,w, `)) 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.

heading: 6 Empirical Evaluation
text: 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.

heading: 6.1 Omniscient Greedy Teaching
text: Least square regression learner. We evaluate LAST on linear regression where the training data is generated by ỹ=〈w∗,x〉+ ( follows the normal distribution). We compute the training objective value and the Euclidean distance betweenwt andw∗ 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 a 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 or LAST alone, implying that alternating optimization works well.
Logistic regression learner. Next we evaluate LAST on linear classification for logistic regression learners. We teach the logistic regression learner to perform binary classification 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 efficiently 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.
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 a 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 empirically show its effectiveness for nonlinear learners. Specifically, we use LAST (β=1) to teach a 2-layer MLP with ReLU nonlinearity (the output layer is essentially a logistic 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.
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).
6.2 Omniscient Parameterized Teaching
We learn a 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 policies 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 convergence than SGD. Moreover, we evaluate two
unrolling settings (20 steps and 100 steps) and unrolling more steps show marginal benefits on convergence. 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 iteration-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.

heading: 7 Concluding Remarks
text: In this paper, we present a 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.

heading: Acknowledgments
text: WL is supported by a Cambridge-Tübingen Fellowship, an NVIDIA GPU grant, DeepMind and the Leverhulme Trust via CFI. AW acknowledges support from a 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 Electronics Co., Ldt. This work was supported by the German Federal Ministry of Education and Research (BMBF): Tübingen AI Center, FKZ: 01IS18039B, and by the Machine Learning Cluster of Excellence, EXC number 2064/1 – Project number 390727645.

Review summaries:
This paper studies the problem of iterative machine teaching with a focus on synthesizing the labels.   Specifically, 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.   For 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.   Empirical results show that the proposed methods are effective and require fewer iterations to converge than standard training (SGD).

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.