Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes an algorithm for machine teaching that relies on synthesizing labels for randomly selected examples rather than selecting ideal examples.
main_review: Strengths
- Technique comes with theoretical guarantees

Weaknesses
- Unclear motivation
- Unclear meaningfulness of results

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

In 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?

A 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?

Finally, 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?

[A] Beygelzimer et al., Agnostic Active Learning Without Constraints. NeurIPS 2010.

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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. 
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. 

Strengths: 
- (see above)
- Simple, interesting idea with a nice level of generality, effective theory, and empirical results. 

Weaknesses:
- 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. 
- 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. 

Specific questions and comments: 
- "Then the student keeps learn22 ing from this batch dataset for the target concept." What does this mean? 
- "[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?
- 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. 
- "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. 
- "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. 
- "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. 
- 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. 
- " 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. 
- The move from predicted to ground truth labels is interesting. I would be interested to hear the author's thoughts on probabilistic interpretations. 
- " 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. 
- "This implication nicely matches the conclusion in curriculum learning [5] and IM" What conclusion? 
- " 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. 
- Figure 3 didn't help me much. It would require more explaining in the caption than simply "example". 
- " 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
illustration 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. 
- " 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. 
- " 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. 
- " 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. 
- " 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. 
- "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. 
- "We can simply define rt =−kwt −w∗ k as the reward and directly apply policy gradient [59] to solve it." Please explain more. 
- Theorem 1 contains several terms that are not defined. 
- "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. 
- "We connect Theorem 1 to Armijo linear search"  A more precise term than connect would be desirable. 
- Figure 5 did not help me. The caption is inadequate. 
- "Based on [33], it is easy to verify that mixed teaching can achieve ET" Please explain. 
- "is able to achieve faster teaching empirically" please point to where this is demonstrated. 
- The discussion of the data in figure 11 is interesting! (but not convincing) I would be interested to hear more about this. 
limitations_and_societal_impact: No limitations are acknowledged and societal impact is not discussed.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.
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.

** Strengths

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

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

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

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

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

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

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

[1] Rethinking the Inception Architecture for Computer Vision, CVPR 2016
[2] DisturbLabel: Regularizing CNN on the Loss Layer, CVPR 2016
[3] Iterative Machine Teaching, ICML 2017
[4] An Optimal Control Approach to Sequential Machine Teaching, AISTATS 2019
[5] Learning to Teach, ICLR 2018


** Weaknesses

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

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

- I think unrolling generally takes a huge amount of GPU memory, which needs more discussions and justifications in the paper.

- The related work section can be improved by giving a more detailed discussion and comparison between LAST and the existing work.

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


** Additional Suggestions

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

- The connection to privileged information is very interesting but not too obvious to me. I think the authors can elaborate more on this.
limitations_and_societal_impact: See sections above.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: 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).
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. 


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


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


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


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


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


Questions:

6. 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?


7. How do your methods compare to synthesizing the inputs?


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

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


Overall, 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.

References:

[1] Raghu, Aniruddh, et al. "Teaching with commentaries." ICLR, 2021.

[2] Ren, Mengye, et al. "Learning to reweight examples for robust deep learning."  ICML, 2018
limitations_and_societal_impact: The authors discussed the societal impact and limitations in the experiments and concluding remarks.
review_title: null

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)