Knowledge Distillation: Bad Models Can Be Good Role Models
Authors: Gal Kaplun
eran malach
Preetum Nakkiran
Shai Shalev-Shwartz
Venue: NeurIPS 2022 Accept (2022)
Keywords: Knowledge Distillation
Teacher-Student
Learning Theory
Learning to Sample
Ensembling

Abstract: Large neural networks trained in the overparameterized regime are able to fit noise to zero train error. Recent work of Nakkiran and Bansal has empirically observed that such networks behave as “conditional samplers” from the noisy distribution. That is, they replicate the noise in the train data to unseen examples. We give a theoretical framework for studying this conditional sampling behavior in the context of learning theory. We relate the notion of such samplers to knowledge distillation, where a student network imitates the outputs of a teacher on unlabeled data. We show that samplers, while being bad classifiers, can be good teachers. Concretely, we prove that distillation from samplers is guaranteed to produce a student which approximates the Bayes optimal classifier. Finally, we show that some common learning algorithms (e.g., Nearest-Neighbours and Kernel Machines) can often generate samplers when applied in the overparameterized regime.

Knowledge Distillation: Bad Models Can Be Good Role Models
Gal Kaplun Harvard University & Mobileye galkaplun@g. harvard. edu
Eran Malach
Hebrew University & Mobileye eran www.mmaaaaaaalaammmmmmmmmmmmmaam hujji ac.il il
Preetum Nakkiran
Shai Shalev-Shwartz
University of California San Diego preetumlucad. edu
Hebrew University & Mobileye shaisocs huji. ac.
Abstract
Large neural networks trained in the overparameterized regime are able to fit noise to zero train error. Recent work of Nakkiran and Bansal (20] has empirically observed that such networks behave as "conditional samplers" from the noisy distribution. That is, they replicate the noise in the train data to unseen examples. We give theoretical framework for studying this conditional sampling behavior in the context of learning theory. We relate the notion of such samplers to knowledge distillation, where student network imitates the outputs of teacher on unlabeled data. We show that samplers, while being bad classifiers. can be good teachers. Concretely, we prove that distillation from samplers is guaranteed to produce student which approximates the Bayes optimal classifier. Finally, we show that some common learning algorithms (c.g.. Nearest-Neighbours and Kernel Machines) can often generate samplers when applied in the overparameterized regime.
1 Introduction
Recently, the field of supervised learning has witnessed the success of overparameterized methods: models, such deep neural networks, which large enough to fit their train sets but still achieve good test performance. even noisy training data without catastrophically overfitting [31 despite explicit regularization. The seminal work of Bartlett et al. (2) proposed the theoretical framework of benign overfitting to capture this empirical behavior. Briefly, benign overfitting studies statistically consistent methods- where models approach the Bayes optimal classifier, even in presence of noise.
core theoretical concern to understand why such models are able to fit
However, recent empirical work shows that when training deep neural networks noisy data, overfitting is neither catastrophic nor benign (20). Specifically, they propose that overfitting leads not good classifier, but good conditional sampler. For example, suppose train model on a set of images sampled from some distribution D, where 20% of the images of cats are wrongly labeled as dogs. We now train an overparameterized network to fit samples from D. Note that for the distribution D, the Bayes-optimal classifier, namely (x) = argmax,, I'D (y) x)). returns the "correct" class of every image. We can hope that if overfitting is truly "benign" in the sense of (2), the overparameterized model will be close to this optimal fz. However, this is not what occurs practice: as [20] point out, the trained model f reproduces noise in the training set at test time, labeling up to 20% of the cats in the test data as dogs. In sense, the trained model f' behaves as a conditional sample: fxx) ~ (p(())) (x) (see the leftmost confusion matrix Figure
The above example indicates that thinking about classifiers in the overparameterized regime as approximating the Bayes optimal predictor might be misleading. Therefore, it essential develop
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

ResNet- 18. Noisy C FAR 10
10 Ensemble Res 18, Noisy CIFAR- 10
Random Distilled Noisy CIFAR-10 10
1.8
0.34
08
Origina Class
0.6
5.50
0.31
0.86
0.04
9:74
1.14
0.84
0.84
0,97
0,95
0::3
Prediction Class
Prediction Class
Prediction Class
Figure 1: From Samplers to Good Models. Class confusion matrices for ResNet-18 trained on CIFAR-10 with 20% fixed and class dependent label noise (c.g., 20% of cats are labeled as dogs). Left. A ResNet-18 18 trained on this data replicates the noise to the test distribution. Middle. When ensembling 10 such models, the noise virtually disappears, at the cost of high price at inference. Right. Distilling a single model via unlabeled examples from the CIFAR-50 5m5m dataset by randomly selected a teacher for each example from a 10 teacher pool eliminates the noise as well as the inference cost. For further details on random teacher distillation see Section 3.3
the appropriate theoretical framework for describing the behavior of samplers from the conditional distribution. While the learning-theore theoretic aspects of supervised classification are well-studied, the theory of supervised conditional sampling has, to the best of our knowledge, not been systematically explored. In this work, we take the first steps towards addressing this gap. We initiate the study of conditional sampling as learning problem, and explore its relations to other kinds of learning.
Interestingly, relate the notion of samplers to knowledge distillation methods. In short, knowledge distillation the process of training a teacher network on a small labeled dataset and using its predictions to label a large unlabeled dataset, on which student network is trained imitate the output of the teacher. We find that taking an ensemble of samplers as a teacher for knowledge distillation produces student network with minimal error with respect to the Bayes optimal classifier. Finally, our theory leads to a new algorithm for knowledge distillation, where we randomly choose a teacher from a fixed pool, to label each example, which accelerates the training process in practic We show that this new algorithm is guaranteed to find a student with low error.
1.1 Our Contributions
Learning Theory of Conditional Samplers. (Section 2 We initiate the study of conditional sampling in the context of computational learning theory. We formally introduce the problem of conditional-sampliin
and define the sample complexity of learning a sampler. We then present positive and negative results in this new setting. For example, we show that there exist distributions where sampling is much easier than classification, requiring far fewer samples. However, if we allow polynomial blowup in sample-size and runtime, a sampler can be "boosted" to a good classifier, showing that if finding a classifier is computationally hard then sampling is also hard.
Theory of Knowledge Distillation. 3) One way to boost a sampler into a good classifier is to run an ensemble of samplers at inference time (see middle panel of Figure D which is costly. We show that by performing distillation from an ensemble of teachers, it is possible to find a student with low error w.r.t. the Bayes optimal. This shows that teacher networks in not be good classifiers, but just good samplers. Finally we propose new algorithm for distillation, where each example is labeled by random teacher from fixed pool (see right panel of Figure [. We study quantitative bounds on the sample complexity of teaching and learning in our setting, for both
need
just
and distillation from random teacher.
Theory of Sampler Algorithms. (Section 4 We show that several classical learning algorithms provably produce good conditional samplers, and analyze their sample complexity in terms of standard problem parameters (e.g., distributional smoothness). Specifically we show that the 1- Nearest-Neighbour algorithm is a sampler, and extend our analysis to k-Nearest-Neighbour well.
See repository http:///ss.......aaaaaaaaaaaaa/a

---

Furthermore, we show that under some distributional assumptions, Lipschitz classes such as linear methods, kernels and neural networks may also behave like samplers.
1.2 Related Work
Knowledge Distillation Knowledge Distillation for deep learning was proposed in 14] Since then.
a large body of work showed its practical benefits for various machine learning tasks [29 23 30 6
10 27 Nonetheless, from theoretical perspective, understanding why and when distillation works remains a mystery. Hinton et al. [4], attribute the success of distillation to the fact that the soft labels of the teacher passing additional information on the input. In a recent paper, Menon al. [8) claim that when the teacher approximates the Bayes class- probabiiiiss,, distillation is possible, Our results show that even when the teachers are far from the Bayes optimal prediction (i.e., when teachers are noisy samplers from the distribution), we can find student with low levels of noise through distillation. Another work by Wei et al. [28]. shows that, assuming the data distribution has good continuity within each class, self-distillation is possible. However, it is not clear when such assumption is actually satisfied. The work of Lopez-Paz et al. [77, relates the notion of privileged information to knowledge distillation. A work by Frei et al. (8), shows that self-training can boost weak learners, when the target is a linear classifier over a mixture model distribution. Other works [19 32 7 study distillation as regularization method, forcing the student learn under "smoother" loss landscape.
Learning with Noise Learning under corrupted labels a well-studied research area the literature (e.g.. (1)).. A notable examples are the works of Blum et al., and Kearns et al. [5] 15,, showing how statistical query algorithms can be leveraged to learn under noisy labels. A growing number of works study the effects of noise on deep learning, well methods to learn under label noise (see (26) for a survey). However, most of these works do not leverage distillation for label noise robustness, as we suggest in work. More related to our work is [12), showing that iterative process of training and re-labeling can combat label noise. However, this work focuses on empirical study of distillation.
2 Sampling as a Learning Problem
Let X' be the input space and y = {+1} be the label space (for simplicity, under appropriate assumptions we can extend most of our results to multiclass). hypothesis class H some class of functions from X to V. A learning algorithm A takes sequence of m samples S E (X x ) and outputs some hypothesis h : X + V. We denote by A(S) the hypothesis that outputs when observing the sample S. For some distribution D over X x V we denote its X' marginal as Dx and denote the Bayes optimal classifier by fb == arg max Pp [y|x]
When D is a distribution where the label is not deterministic function of the input, we think of D as noisy version of some clean distribution DD, where each input is correctly labeled. Naturally, we assume that the probability of sceing the right label is greater than seeing wrong one. In other words, D has the same marginal distribution over X (i.e., Dx = Dix), and is labeled by the Bayes optimal classifier of D. That is, sampling (x, y) ~ D* is given by x Dx and y = (x).
We denote the "noise" of the distribution D by (nD) := F (x. [y + fz))) We also consider the margin of the distribution, which defines the difference in probability between correct and wrong label for each example. Namely, for some 8 2 0, let yo())) be the supremum over > 0 s.t.,
P
P ((f(())xx)
max P(y)x) + <
x
Specifically, denote (D) == (D). We typically assume that the input distribution has strictly positive margin (D) > O, so for every example the probability to see the correct label is greater by 7 than the probability to a wrong label.
Our objective in this setting is to approximate the Bayes optimal classifier of D. In other words, we want to minimize the 0-1 loss on the clean distribution D":
LD- (h) == ((x.)~DD [h(x) * [5()) = P (xxx)>>>> [h(x) * y)
(1)
So, the learning algorithm has access to samples from the noisy distribution D. but needs to achieve good loss on the clean distribution D*. We define a learner in this setting to be an algorithm that minimizes
[
using finite number of samples:
We assume that ties are broken arbitrarily
3

---

Definition 1. For some learning algorithm A and some distribution 'D over X x y, we say that a learner for D if there exists function m (0, 1) + N s.t. for every E (0, 1), laking 2 m({) we get, ES LD- (A(S)) e.
In this case, we call m(.) the sample complexity of A w.r. D. Additionally, for some class P of distributions over X x Y, we say that A is learner for P there is some m(.) s.s. A is a learner with sample complexity m²)) for every D E P.
Note that this definition of learner is similar the notion of asymptotically consistent estimator. However, our definition explicitly accounts for the sample complexity. To give a concrete example, let us consider agnostic learning using the ERM rule, namely: ERMH(()) arg minGeR (h)...
For some hypothesis class H and some margin y > 0, let P(H.7) be the class of distributions such that for every D 7) we have (D) 2 7 and fo E H. Namely, P(H, 7) is the class of distributions with margin 7 for which the Bayes optimal classifier comes from H. The following theorem states that finite VC-dimension and non-zero margin form a sufficient condition for learnability with noise.
Theorem 2. There exists a constant C' > s.t. for every hypothesis class H with VC(H) < co, H is a learner for P(H,7) 7) with sample complexity míc) = C +CC(H)+
<²77
The proof of Theorem 2 is given in the appendix. The main idea is the following lemma (whose proof is also in the appendix), which shows that the margin assumption connects small relative error w.r.t. 'D to a small absolute error w.r.t. D
Lemma 3. Fix some distribution DD and let h" be the Bayes optimal classifier for DD Assume that (D) > 0. Then, for every h such that LD(h)= S LD(h") + e it holds that LD- (h) S 7B( + 5.
Combining this lemma with the Fundamental Theorem of Learning Theory (see (25)) yields The- orem From this theorem, we see that given more samples than the VC-dimension (often corre- sponding to the number of parameters), learning is possible. However, complex classifiers with large VC-dimension such as neural networks are often trained in the overparameterized regime, when the number of parameters exceeds the number of samples. In this regime, the bound of Theorem becomes vacuous. That said, this does not rule out the possibility of distribution-dependee sample complexity bounds using other measures of complexity (e.g., Rademacher complexity).
2.1 Samplers
As previously mentioned, neural networks trained on noisy data replicate the noise to unseen samples as well, behaving like samplers from the noisy distribution. We next define formally a sampler for some distribution D. giving similar definition as in 20
For some learning algorithm A, some number m E NN and some distribution D over X' x V. define the distribution A(D") over X' x Y, where (x, ~ AADDM) is given by sampling S ~ DDM sampling x Dx and setting y (x). Namely, A(Dm) is the distribution given by (re)-labeling D using hypothesis generated by A when observing a random sample of size m. Using these notations, we define a sampler algorithm for the distribution D as follows:
Definition 4. For some learning algorithm A and some distribution D over X' x Y, we say that is a sampler for 'D there exists m (0. 1) + N s.t. for every E (0, 1), taking m 2 m((c) we get,
TV(A(D")))) Se
where TV is the Total Variation Distance. Then, we call mn the sample complexity of A w.r.t. D. Additionally, for some class P of distributions over X x y. we say that A is a sampler for P if there exists m(.) s.I. A is a sampler with sample complexity for each D E P.
So, sampler for D is an algorithm that generates a distribution similar to D (the noisy input distribution) when labeling new examples. A primary example for a sampler is the 1-Nearest- Neighbour algorithm: since I-NN outputs the (possibly corrupted) label of the closest neighbour, its prediction behaves like sampling from (D(y)x (see Section[4) Figure I shows that neural networks behave similarly to samplers when trained on a noisy version of the CIFAR- 1- dataset.
Given the above definition, it can be easily shown that, instead of approximating the Bayes optimal prediction, a sampler preserves the noise rate of the original distribution.
4

---

Lemma 5. Let A be sampler 'D with sample complexity m. Then, for m 2 m(E),
(TD) E
IE LD- (A(S)) (D) + S-Di
While sampler for D is not good learner (in the sense of Definition D. it does have some favorable properties. Primarily, it can take significantly fewer samples to get a sampler than it would take to get a learner, hence making the study of samplers more suitable for the overparameterized regime. In fact, in the extreme case one could get a sampler using only a single example from the distribution, while getting a learner for the same distribution would require an arbitrarily large number of examples. Indeed, fix b E {+1] and y E (0, 1), and let Dj be the distributions concentrated on a single example x E X' with label E {+1} s.t. PD, (y = 1) = 1+bx To get a sampler from Dd it clearly suffices to take a single example (x, y). and return the constant function y. To find the Bayes optimal for the distribution Do, on the other hand, any algorithm needs S2(1/>²) examples. Using this observation,
we show the folowing result:
Theorem 6. For every M > 0, there exists a class of distributions PM such that: a) there exists a sampler for PM with sample complexity in 1, and b) any learner for PM has sample complexity satisfying m m(1/8)= 2 M.
2.2 Teachers
Motivated by the observed behavior of neural networks in the overparemeterized regime, we defined the notion of samplers. We showed that samplers can be much more sample efficient than learners, at the cost of giving noisy predictions. Next, will show that while samplers are in and of themselves bad classifiers, they can still be good teachers. That is, we can use samplers to label a large unlabeled dataset and train student classifier on this new dataset. This process is often referred to as knowledge
distillation, and it has been shown to work remarkably well in practice [29] 23 The following definition captures the notion of a (good) teacher:
Definition 7. For some learning algorithm A, some distribution D over X x V. we say that A is teacher for 'D if there exists a function (0, -> N s.s. for every G, E 1), taking m 2 m(c,T) T) the following holds:
1. LD- (FAIDM) PXWD [f(x)) + (x(om)(x)) Se
2. (e( 2 (D) T
Additionally, for some class P of distributions over X x YY, we say that A is teacher for P if there is some m s.1. A is a teacher with sample complexity m(. -) for every 'D E P.
The first condition in the above definition means that the Bayes optimal of the original distribution and the distribution induced by the teacher are close. The second condition means that the probability mass of low margin samples from the distribution labeled by the teacher is small. Intuitively, an algorithm satisfying Definition is good teacher since the distribution it induces is "similar" to the original distribution. Hence, if the student finds good hypothesis on the induued distribution, its hypothesis is also good w.r.t. the original distribution.
In Section 3 we formally study when and how teachers can be used for distillation, giving guarantees for getting students with small error with respect to the clean distribution D Before that, let us first show that samplers are indeed good teachers.
Theorem 8. Let A be a sampler for D with sample complexity m(.) and margin y. Then, A is a teacher for 'D with sample complexity m(c,T)= = mif- min(r/2,7))
The main idea behind the proof of Theorem iis that, given an example with probability mass p. the "cost" (in terms of TV) of flipping the example's 's label w.r.t. the Bayes optimal ff is at least 7 Since our TV "budget" is limited by Ey we can only flip a probability mass of & of the distribution.
Finally, before moving on to discuss the implication of our results, we show that learners are also good teachers. This is almost immediate, since learners approximate the Bayes optimal classifier, and hence can be used to train students to similarly imitate the Bayes classifier.
Theorem 9. Let A be a learner for DD with sample complexity ml-). Then, A is teacher for 'D with sample complexity m(E,T) = (P)
5

---

To conclude, Theorem and Theorem show that, to some extent, teacher an "interpolation" between sampler and learner.
3 Distillation from Teachers
We defined the notion of teacher, and showed that both samplers and learners are teachers. Now, we show how teachers (and in particular, samplers) can be used to find good learners. First, we show that an ensemble of teachers can be used to get good learner by simply outputting the majority vote of the ensemble. Next, we show that using the ensemble to label new set of unlabeled examples (i.e., performing knowledge distillation) guarantees finding student with small loss, assuming the Bayes optimal classifier comes from the hypothesis class learned by the student. Such process is favorable, since it reduces the computational cost of running the ensemble at inference time, and also allows using a different hypothesis class for the student (for example when using student network of smaller size, e.g.. [TT.. Finally, we show that distillation can also be achieved by labeling examples using teacher that is randomly chosen from a fixed set of teachers, method that has some computational benefits at training time. To the best of our knowledge, this is a novel technique for distillation that has not been previously suggested in prior work.
3.1 Ensembles of Teachers
We now show how an ensemble of teachers can be used get accurate predictions with respect to the
Bayes optimal predictor. Given some l samples Si...., S4 Dim,, each one of size m, we can use a learning algorithm A to get different hypothesis h1, ... hy. where h; := A(S.). Observe the ensemble hypothesis, which outputs the majority vote of the ensemble members:
Heus (x) = arg max DEY
Σ [1(h,(x)=3) =x)
We use the notation Aens (S Sx) == hens to denote this ensemble hypotheses. The following Theorem states that the ensemble hypothesis has a good loss on average, when using large enough ensemble of teachers:
Theorem 10. Assume that A is teacher for some distribution 'D with complexity m. Then, for all 16log(3/e)
c E (0, 1), taking m 2 m
c 7(D) 3 2
and l: 2 7(D]² we get,
S St Dm LD- (A .s)) S S
We now give sketch of the proof. For some x E X' let be the prediction of the i-th teacher, and let ÿ be the average of the predictions, namely y = f Σ ys. Observe that hens(x) sign(y). and additionally Flyy] ArD" x). Now, since A is teacher we get E A [B|x]]]]]]]]] R Ep x (with high probability over the choice of x), and by concentration bounds this implies that w.h.p. hens (x) give the Bayes optimal prediction (i.e., hens (x) (x)).
teacher for D, then Aons with A: 2 H (1/>(D)2 a learner for D. More generally, if we have teacher for some distribution D with positive margin, this implies that there exists a learner for the same distribution. The inverse of this statement gives another interesting result-if no algorithm hard. Formally, let P be a class of distributions over X' x ) s.t. for all D E P holds that (DD) 2 % Then, if there is learner for P. there is teacher sampler for P. Additionally, similar result holds for problems which are computationally hard to learn. That is, if there is no learner for P that runs in polynomial time, then there is poly-time teacher or sampler for P. Observe that the condition that ((D) 2 z for all D E P in the previous statement is necessary. Indeed, taking UM where PM the distribution class guaranteed by Theorem [ gives class P s.t. there is sampler for P with sample complexity m = 1, but there is no learner for P.
So, Theorem 10 shows that
learn some problem, then getting teacher (or sampler) is also
3.2 Distillation from Ensembles
We showed that ensemble of k 00( teachers gives classifier that approximates the Bayes optimal predictor. This, however, incurs a factor computational cost at inference time. To prevent
We use Ω hide constant and logarithmic factors.

---

this, we can instead use the ensemble label new unlabeled data, and train a new classifier to imitate the ensemble. This moves the computational burden from inference time to training time.
Fix some class H. and define the Thneeblle-seedd--Labelnn (EPL) algorithm as follows:
1. For some k, m E N. sample SI....,
S₂. ~ D"
, SR. and let hens - 3. Take S" to be a set of mn' unlabeled examples sampled from Dx, and label it using heas.
2. Run A on Si,...,
4. Denote by S the pseudo-labeled set. Run 2RM22 on the set S and return h == 2RMx
Intuitively, since hens approximates the Bayes optimal classifier (see Theorem I0 the labels for the new dataset S' are mostly correct. In other words, the pseudo-labeled set S comes from distribution that is close to the clean distribution D When using pseudo-labels, it is enough use unlabeled data, which is often abundant, so S can be much larger than our original labeled dataset. In this case, we no longer need to work in the overparameterized regime, ERMy is guaranteed to achieve good performance by standard VC bounds. This argument is captured in Theorem TT
Theorem 11. For hypothesis class H with VC(H) < oc, and let 'D & ((H,,)) v) for some Y > O. Let A be a teacher for DD with distributional sample complexity m. Then, there exists a constant
C > 0 s.t. for every E (0,1). running the EPL algorithm with parameters 2 m ( 12 2)) m'
C VCCH)+ and k 2 16lo/()2/c) returns a hypothesis h satisfying Es,...... S3 LD (h) S
3.3 Distillation from Random Teachers
While the EPL algorithm moves the computation cost from inference to training, we still suffer a k factor for labeling each example. Instead, a possible solution is to label examples by choosing a random classifier from the ensemble. Then, we only rum one classifier per example. So, we define the Randoo-PseedooLLan
(RPL) similarly to EPL, except that for each example x in the unlabeled dataset S", we pick (hi...., } and label x by lx(x).
To understand why this method works, we can think of 3 as coming from a distribution D, defined by sampling x Dx and sampling y s.t. Eg[y|x] _Bs-pe (x; By the properties of the teacher, using concentration arguments as in Theorem 10 the distribution D is close to the noisy distribution
'D. However, as mentioned before, the advantage of using S ~ D is that we can use much larger set of unlabeled data, in which case the result of Theorem 2 can be applied show that the above algorithm finds hypothesis with good error. This is stated in the following result:
Theorem 12. For hypothesis class H with VC(H) DO. let D e P(H, for 7 O. Let A be a teacher for 'D with distributional sample complexity mh Then, there exists constant 0 s.t. for every e E (0, 1), running the RPL algorithm with parameters m 2 (57 2).
m > C (C(H)+loa(
128 log 30c 77-))
and k 2
returns he satisfying E S.......33 L (h) S
27
Compare the sample complexity of the above theorem with the sample complexity achieved by the EPL algorithm, stated in Theorem I1 At first glance, it seems that the gain from using the RPL algorithm is not clear, as it increases the number of unlabeled data by a factor of 1/>(D)² (and also might increase the number of labeled examples). This is not surprising, because a dataset labeled by a random classifier can be much more noisy than dataset labeled by the ensemble, and hence more examples are required in order to learn. Note, that since k 2 ((LL7(D)) the randomized labeling takes 1/1 compute per example relative to the ensemble labeling, it will, however, need label an order of le times more examples.
We do note that there might still be computational benefits using the random approach, it allows the training and labeling to happen in parallel without a significant increase in compute (e.g.. 2 GPU cores are enough to train parallel without any loss of time). On the other hand, labeling a dataset using the ensemble requires one to either increase the compute by & (applying parallelism), or otherwise wait until the full dataset is labeled, and only then start the distillation process. Finally, our experiments show that the gain from ensemble labeling over random labeling, as captured by the final accuracy of the trained student, is not so significant (see Table This suggests that in
7

---

some particular cases (e.g., under further assumptions on the data distribution and/or the optimization algorithm), it is preferable to use the RPL algorithm.
4 Samplers Exist
So far, we showed that samplers can be good teachers. These can then be used for knowledge distillation, generating students which approximate the Bayes optimal prediction. To complete the picture, we now show that some well-known algorithmss can be used as samplers or teachers. We start by studying the k-Nearest- -eighbbuu algorithm, and show that is a teacher when the underlying distribution has some Lipschitz property. We then show that bounded-norm ReLU networks with scalar input exhibit similar behavior. In Appendix [.1 we further analyze Lipschitz classes of functions (e.g.. linear functions, kernels and neural networks), and show that when the data is well- clustered, these algorithms can be teachers as well. In all cases, the sample complexity needed for the samplers or teachers is lower than the complexity required for learning.
Nearest Neighbour Algorithm
For some set 5 = (1x1,1)).... 91),..., (xm:8m)) S X' x y we denote Sx = {xi, Xm). Fix some metric d over the space X. In this section, we assume that the metric space (X. d) satisfies the Heine-Borel property-that is, every closed and bounded set in X is compac 4 For some finite set S S X' x V. and some E X. denote d(x, S) := minx d(x, x') and T S) = arg (x (ES d(x, x'). Additionally, we define the set k-T Sx) S S to be the set of k points in S that are closest to x. That is, (-T S) is a set of size At s.t. for any (x', vy) E k--(xx, S) and (&, 5) SS) k-T(x,, 5) it holds that d(x, x') S d(xx, x 5
For some distribution D, say that D is X-Lipschitz if for all x,x' E supp(Dx) and y E y it holds that PD x] Polulx S xd(x,'').
For some odd l 2 1, define NN == arg maxgey [x', v/) k- S), y ÿ). i.e., (S) is the k-NN algorithm over sample S. We start by showing that the AI.NN is a sampler. The distributional sample complexity of AI-NN depends
the number of c-balls that can cover a 1-d ó mass of the distribution (Lemma 23 in the Appendix shows that this number is always finite). Given such cover, we can guarantee that with a large enough sample, we find a candidate example in each of the balls that have non- negligible mass. In that case, if the distribution of labels does not change significantly in each ball, AI-NN is indeed a sampler:
Theorem 13. Let DD be some X-Lipschitz distribution. Then, AI-NN is sampler for D.
Next, we study the k-NN algorithm for any odd l 2 1. Similarly to the analysis of the 1-NN case, we show that a large enough sample guarantees least & candidates in each of the b-ball covering the distribution. In this case, the prediction of the k-NN algorithm is the majority vote over the k neighbours in each ball. This will get closer to the Bayes optimal prediction as h grows, and therefore the k-NN algorithm is not a sampler for k > 1. However, we show that it is always a teacher:
Theorem 14. Let D be some X-Lischhitz distribution. Then, AK-NN is teacher for D.
The core argument for proving Theorem 14 relies on using a variant of Condorcet's Jury Theorem (CJT). Roughly speaking, CJT states that the accuracy of the majority vote of set of predictors is better than the average accuracy of the individual predictors. candidates casts a "voote,, and using CJT we show that this improves over the 1-NN prediction, which is already a sampler (and hence a teacher). Notice that this works for any k 2 1, and we do not need require 1 to be large enough, as would be required in order get a learner.
the k-NN case, each the k
Bounded-Norm Infinite-Width ReLU Networks
We continue with investigating infinite-widths neural-netwood with weights of bounded norm, following the setting studied
[24
22 We define ReLU network of width k and depth 2
by (x(x) Σi w (2)
(1)
+
(1)
+ b(2), where 0 (k, w()), (2(2),8()) (())))))) and
a is the ReLU activation. As in
24
we consider the Euclidean norm of non-biased weights:
((0) = ト
(2) w
2
Now, consider fitting a sample S S X' x y with a network
"Specifically, the Heine-Borel property holds for R= where d is induced by some norm. 'If there are multiple choices such set, we choose one arbitrarily.

---

Student Accuracy Number of Teachers
Experiment
Test Accuracy + std
Test Accuracy
0
One Teacher
0.868 +5e-3
5 Random Teachers
0.898 +22-3
9.86-
10 Random Teachers
0,900 =2c-3
5 Teacher Ensemble
0.899 =2e-3
10 Teacher Ensemble
0.902 +1e-3
0 82-
Teacher Accuracy
Ensemble
10- 10-Ennemble Inference 10-Teacher Clean Ens.
0.878
Random Teacher
0.934 =0.
Num Teachers
10
Teacher Accuracy
0.813 24.
Figure 2: The effect of the number of teachers on the performance of the student. We also include the teacher's accuracy marked as 0 teachers.
Table 1: Comparison of teachers, students and en-
sembles test performance. Note that both ensem- bling and distillation reduce the effect of noise.
he with C(0) acting as regularization. Namely, observe the following objective function:
R(S)= inf C(0) 8.t. ho(x) = y for all (x, E S
In the one-dimensional case, ie. when = R. 24 shows that R(S) gives the linear spline interpolation of the data points. Using this, we show that ReLU networks in this setting are samplers: Theorem 15. For algoritim A that takes sample S and returns h s.t. h(z) = sign (hg(z)), for i R(S). Let DD be some continuous X-Lipschitz distribution. Then, a sampler for D.
The above shows that when we don't 't limit the size of the network and use the regularization C(0), the resulting algorithm is a sampler. Observe that if we do not introduce regularization, one can construct a ReLU network ha that outputs constant value (e.g., 1) for all E R, outside of infinitesimally small neighbourhoods of the points of S, where hg interpolates the data (namely, he constant with very narrow "spikes" towards the correct labels of the examples in the sample). Thus, on new points he evaluates to 1 with high probability, so it does not behave like a sampler.
Admittedly, going beyond the one-dimensional case is more challenging, as it requires understanding the high-dimensional geometry of the function returned by R(S). While we defer this case for future work, we note that the analysis of (22) gives some technical tools for understanding the multivariate version the above problem. Specifically, [22] show that solving R(S) is equivalent to minimizing a specific norm in function-space, which controls the complexity of the learned function. Among other things, the authors show that controlling this norm prevents a "spiking" behavior as described above.
5 Experiments
To this point, saw that getting sampler (and thus a teacher) from noisy distribution be more sample efficient than getting a learner. Furthermore, we showed that we can leverage multiple independent teachers approximate the Bayes optimal classifier either via ensembling at inference time or via distillation on unlabeled data. We now complement our theoretical results with an experimental evaluation, showing the benefit of using distillation when training on noisy data. While in our theoretical setting we studied teachers that are trained on entirely disjoint training sets, in practice we find more effective train the teachers on overlapping datasets, as well as training on same dataset with different random initialization.
To get the teachers, we train a ResNet-18 [13] on CIFAR-10 with 20%-fixed and non-umiform label noise (see full details in D We see that our teachers achieve 81.3% test accuracy (see Table I
and behave closely to samplers (see Figure reproducing the results of (20). We now compare
the three methods considered before for using teachers to get learners: 1) Test time Ensembling;
Ensemble as distillation teacher and; 3) Random teacher distillation. For distillation, we train a
student network on the CIFAR-5m, large (5-million examples) dataset that resembles the CIFAR-10 dataset (2]. where the labels are provided by the previously trained teachers. We report our results

---

where the reported accuracies are on the CIFAR-10 test data. Observe that using an ensemble for inference reduces the noise significantly. and achieves test accuracy of 87 87.8% (versus 81.3% for a single teacher). When applying distillation, both random pseudo-labeling and ensemble pseudo-labeling further increase the test accuracy to about 90%. In addition, study how the number of teachers affects performance (see Figure We observe that both random pseudo-labeling and ensemble majority improve in performance when the number of teachers grow.
in Table 1
6
Acknowledgements
This work supported by Simons Investigator Fellowship. NSF grants DMS-2134157 and CCF- 1565264, DARPA grant W911NF2010021,nm DOE grant DE-SC0022199.
10

---

References
[1] Dana Angluin and Philip Laird. Learning from noisy examples. Machine Learning, 2(4):343- 370, 1988.
[2] Peter L Bartlett, Philip M Long, Gabor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117748):30033-30077) 2020.
[3] Ruth Yashar and Jacob Paroush. A nonasymptotic condorcet jury theorem. Social Choice and Welfare, 17(2):189-199) 199, 2000.
[4] Daniel Berend and Luba Sapir. Monotonicity in condorcet jury theorem. Social Choice and Welfare, 24(1):83-92, 2005.
[5] Avrim Blum, Adam Kalai, and Hal Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. Journal of the ACM 5004) 2003.
[6] Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey E. Hinton. Big sepe-supe models are strong semi- cumi-supervised learners. CoRR, abs/2006. 10029, 2020.
[7] Bin Dong, Jikai Hou, Yiping Lu, and Zhihua Zhang. Distillation early stopping? harvesting dark knowledge utilizing anisotropic information retrieval for overparameterizee neural network. arXiv preprint arviv: 191000155, 2019.
[8] Spencer Frei, Difan Zou, Zixiang Chen, and Quanquan Gu. Self-training converts weak learners strong learners in mixture models. arXiv preprint arXiv:2106./3880 2021.
[9] Benoît Frénay and Michel Verleysen. Classification in the presence of label noise: a survey, IEEE transactions neural networks and learning systems, 25(5):845 (66,, 2013.
[10] Tommaso Furlanello, Zachary C. Lipton, Michael Tschannen, Laurent Itti, and Anima Anand- kumar. Born again neural networks, 2018.
[11] Jianping Gou, Baosheng Yu, Stephen J Maybank, and Dacheng Tao. Knowledge distillation: A survey. International Journal of Computer Vision, 128(6):789-1111 2021.
[12] Christian Haase-Schütz, Rainer Stal, Heinz Hertlein, and Bernhard Sick. Iterative label im- provement: Robust training by confidence based filtering and dataset partitioning. In 2020 25th International Conference on Pattern Recognition (ICPR), pages 9483-9490. IEEE, 2021.
[13] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. CoRR, abs/1512.03385, 2015.
[14] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in a neural network, 2015.
[15] Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM 1998.
[16] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. CoRR, 2009.
[17] David Lopez-Paz, Léon Bottou, Bernhard Schölkopf, and Vladimir Vapnik. Unifying distillation and privileged information. arXiv preprint arXiv: 1XIv::5511.0345: 2015.
[18] Aditya Krishna Menon, Ankit Singh Rawat, Sashank J. Reddi, Seungyeon Kim, and Sanjiv Kumar. Why distillation helps: a statistical perspective. CoRR, abs/2005.10419, 2020.
[19] Hossein Mobahi, Mehrdad Farajtabar, and Peter Bartlett. Self-distillation amplifies regular- ization in hilbert space. Advances in Neural Information Processing Systems, 33:3351-3361, 2020.
[20] Preetum Nakkiran and Yamini Bansal. Distributional generalization: A new kind of generaliza- tion. arXiv preprint arXiv:2009.0880 08092, 2020.
11

---

[21] Preetum Nakkiran, Behnam Neyshabur, and Hanie Sedghi. The deep bootstrap: Good online learners are good offline generalizers. CoRR, abs/2010.08127, 2020.
[22] Greg Ongie, Rebecca Willett, Daniel Soudry, and Nathan Srebro. A function space view of bounded norm infinite width relu nets: The multivariate case. arXiv preprint arXiv:1910.01633, 2019.
[23] Hieu Pham, Qizhe Xie, Zihang Dai, and Quoc Le. Meta pseudo labels. CoRR, abs/2003.10580, 2020.
[24] Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look in function space? In Conference on Learning Theory, pages 2667-2690. PMLR, 2019.
[25] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory atgorithms. Cambridge university press, 2014.
[26] Hwanjun Song, Minseok Kim, Dongmin Park, Yooju Shin, and Jae-Gil Lee. Learning from noisy labels with deep neural networks: survey. arXiv preprint arXiv:2007.08199) 2020.
[27] Siqi Sun, Cheng, Zhe Gan, and Jingjing Liu. Patient knowledge distillation for BERT model compression. CoRR, hoss/998.09355. 2019.
[28] Colin Wei, Kendrick Shen, Yining Chen, and Tengyu Ma. Theoretical analysis of self-training with deep networks on unlabeled data. arXiv preprins arXiv:2010.03622, 2020.
[29] Qizhe Xie, Eduard H. Hovy, Minh- Thang Luong, and Quoc V. Le. Self-training with noisy student improves imagenet classification. CoRR, abs/1911 9.04222, 2019.
[30] I. Zeki Yalniz, Hervé Jégou, Kan Chen, Manohar Paluri, and Dhruv Mahajan. Billion-scale semi-supervised learning for image classification, 2019.
[31] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. CoRR, abs/161 103530, 2016.
[32] Shuai Zhang, Meng Wang, Sijia Liu, Pin-Yu Chen, and Jinjun Xiong, How does unlabeled data improve generalization in self self-training? one-hidden layer theoretical analysis. arXiv preprint arXiv:2201.08114 2022.
12


Reviews:
[{"review_id": "xGBF2sOZgT", "reviewer": "Reviewer_5UHV", "summary": "The paper establishes the theoretical framework for studying samplers that are defined as a learning algorithm creating models whose aggregated prediction distribution is close to the Bayes optimal via repeated training with independent samples. The authors display that the learner generate \"bad models\" when inspecting the individual models, but those bad models are data efficiently and jointly can be a good ensemble teacher giving the nearly Bayes labels for distilling a student. The paper additionally provides theoretical guarantees for the samplers and the teachers. From the practical perspective, the authors propose two methods to distill from such a sampler ensemble, and have demonstrated empirical that the distilled students achieve high performance on CIFAR-10.", "questions": "The reviewer does not have major concerns regarding the theoretical development in the paper. Here are some minor questions:\n\n1. The title and the abstract of the submission are currently misleading, as the analyses are mostly done to show the ensemble of bad models (samplers) can be a good role (ensemble) model. This on the other hand has slightly weakened the novelty of the submission, as it is a known property of an ensemble to take advantage of its weak learners in general settings. \n\n2. The theoretical analyses here assume that the sampler algorithm A has access to a large number of independent samples to train models  whose joint predicted probability is nearly Bayes optimal. This is somehow contradictory to the fact that \"bad models\" are usually a consequence of data scarcity, and that independent samples are usually hard to acquire even for ensembles which usually rely on bagging. If so the Bayes optimal would be respect to the empirical distribution, and there is another term to bridge it with the true distribution. \n\n3. Following 2, the empirical study currently reuse same training dataset for getting the ensemble teacher. It would be nice to see how a theoretically perfect setup works in practice. \n\n4. There lacks practical guidance on how to properly choose the hyperpemeters, e.g. m, k in the algorithm. These two values are admittedly related to the sample distribution, so that it would be nice to at least have some estimators. \n\n5. Although easy to follow, the submission appears to be too dense when fitting into 9 pages.\n", "limitations": "Yes. The authors have mentioned both the theoretical limitation of finding hypotheses spaces that meet the requirements of teachers, as well as some technical aspects, e.g. reusing the training datasets for the empirical study.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe paper presents clear and self contained analyses between the learners, samplers and teachers as also defined in the paper. The research question of understanding data inefficient teachers is well motivated and is very meaningful. The theoretical results are concise and sound.\n\nWeakness:\nThe empirical side of the work is relatively weak, as the practical implementation of the proposed method is costly, and the empirical study in the paper is limited. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "udGDtPp90ZQ", "reviewer": "Reviewer_Yejy", "summary": "The paper offers a theoretical framework for studying learning with label noise. It  shows how to  leverage multiple\nindependent teachers to approximate the Bayes optimal classifier either via ensembling at inference time or via distillation on unlabeled data. Specifically, it shows that ERM algorithm on noisy data produces  samplers of posterior distribution and as such it replicates the noise learned from the training to the test distribution. The paper then defines a teacher for a distribution with noisy labels. It shows that a sampler is a teacher with a sample complexity that depends on the noise. Next, it shows that ensemble of teachers applied at test time cancels noise.  To reduce the complexity in test time, the paper suggest to distill knowledge from the ensemble to a single student by labeling a new unlabeled set from the same domain by a majority vote over teachers' predictions and training the students on the resulting labeled set using ERM. The student is guaranteed to achieve good performance by standard VC bound (although to avoid overparametrized setting, the unlabeled set should be very large). To reduce the training time, they suggest to replace the ensemble with a teacher chosen an random from a fixed pool. They showed that a student trained with a random teacher will guaranteed to show good performance but with even larger sample complexity. The paper also shows that some well known algorithms are teachers under some conditions over the underlying distribution.\nThe experiments on CIFAR10 demonstrate  that an ensemble of teachers in test time improves over a single teacher.  Knowledge  distillation from ensemble of  teachers or random teacher via labeling of a large set CIFAR_5m  and training a student on it with ERM yields further improvement in test accuracy. \n", "questions": "Figure 1, when discussed early in the paper is not very clear. It becomes clear later, but maybe some amendment to the caption could be done.", "limitations": "I didn't find a discussion of limitations.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: Nice and solid theoretical paper that addresses an important problem. The empirical results support the theoretical findings. \nWeaknesses: Labeling a large external set 1) requires a larger unlabeled  data set from the same domain, which is not practical in many real life applications; 2) it significantly increases the training time.  ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ZkPyVjHxaRh", "reviewer": "Reviewer_ANZb", "summary": "This paper builds upon the observation by Nakkiran and Bansal, 2020 and proposes a theoretical framework to study conditional samplers, which are interpreted as classifiers trained over noisy labeled data. The authors formally define concepts of conditional sampling from a learning perspective. Particularly, the authors relate samplers to knowledge distillation and show that weak samplers can be used as teachers for distillation in an ensemble manner. The authors also propose an algorithm for distillation using labels generated by a random teacher from a fixed pool of samplers. Finally, they show some results for classical classification algorithms.", "questions": "1) Is the claim “neural networks trained on noisy data replicate the noise to unseen samples as well” in line 143 – 144 actually proved in the paper? If not, to what extent does this statement hold in general?\n\n2) The first condition in Definition 7 sounds very strong. I am not sure why a sampler that satisfies this condition would not be a learner, if not a “good” learner”?\n\n3) Can you say something about the two sample complexity bounds in Theorem 8 and 9, e.g., how do you compare them? What do you mean by “interpolation between a sampler and a learner”.\n\n4) From Figure 1, it is somewhat unintuitive why the ensemble and random distilled would work: each teacher is a sampler that replicates the noise to unseen data, so I find it difficult to understand why voting would result in a different and correct label to previously incorrectly classified sample.\n\n5) The experiments are conducted on CIFAR-10 with pseudo-random label noises. Please report similar metrics on the original CIFAR-10? \n", "limitations": "See the above.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nStrengths:\n+ A new theoretical formulation of learning as sampling and the connections between samplers and classifiers.\n+ Interesting implications of the formulation to knowledge distillation.\n+ A new distillation algorithm.\n\nWeakness:\n- The framework relies on an observation that might not always hold, and if so, it is not clear if one needs to distinguish between a sampler and learner in practice, so I don’t see the practicality of the proposed theory framework.\n- Lack of validation on real data (to support theory and the proposed algorithm.)\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Cq1h8BbIMcW", "reviewer": "Reviewer_mfji", "summary": "This paper supplements the empirical results of Nakkiran and Bansal by providing a theoretical framework for analyzing the conditional sampling behavior of overparameterized networks. The authors show that obtaining a noisy sampler can be more sample efficient than a good classifier, and that an ensemble of samplers suffices to train an accurate student model, even if each sampler is a bad classifier individually. They also show that common learning algorithms generate samplers given sufficient overparameterization.", "questions": "Practically speaking, does the introduced theoretical framework have the potential to explain the success of distillation in practice (when there is typically a single sampler)? Are there any practical recommendations (other than using an ensemble of teacher networks) that the theory predicts?", "limitations": "The authors stated that they provided the code, data, and instructions needed to reproduce the main experiments and that all of the training details were provided. But, to the best of my knowledge, there is no additional supplementary material containing this information.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n* The work and theoretical techniques are novel. The authors do a good job of covering related work in a concise and detailed way.\n* The paper is well-written and organized overall.\n* The proposed explanation for the success of distillation and the theoretically-derived recommendation for using an ensemble of teachers are unique and interesting contributions. Although the authors don’t show that deep neural networks are samplers, I can imagine future work building on the techniques presented in the paper.\n* The paper makes strong theoretical contributions and the techniques seem to be sound\n* The results supplement the empirical results of Nakkiran and Bansal and implicitly provide some justification (assuming that overparameterized NNs are samplers) for the success of overparameterized networks in the context of distillation. It seems likely that future work can build on the theoretical techniques presented in this work.\n\n\n## Weaknesses\n* The motivation for the theoretical framework explicitly comes from the claim that overparameterized neural networks are samplers (as stated in the abstract), but this is not formally shown in the paper. This is an understandable limitation (proving properties of NNs is hard), but the wording in Sec. 4 (“completing the picture”) and the emphasis on NNs throughout the paper (including the NN results in Sec. 5) make it seem like it is already proven\n* The experimental result on a single small-scale ML scenario is underwhelming relative to the paper’s theoretical contributions. Given the widespread success of ensembles in ML, it is not surprising that using multiple teachers to conduct distillation is beneficial. The improvements in student performance with using additional teacher models can be due to the smoothening of the training noise when multiple teachers are used, for example, and not necessarily be indicative of the presented theory in action. To that end, I am not sure what novelty lies in Fig. 2 even with the proposed algorithm of randomly selecting a teacher, which is the ensemble’s mean output in expectation\n* Minor comment, but Fig. 2 should start out with 1 teacher since the y-axis represents the student test accuracy. Without a teacher it’s not clear what the student performance after distillation even means, and it is confusing that the authors plotted the teacher accuracy for that point\n* In practice, distillation is done by training a much larger teacher model to train a small student model. More often than not, the teacher model is a good classifier and an ensemble of networks is not required. I am not sure if or how the theory applies here\n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept