Supervision Complexity and its Role in Knowledge Distillation
Authors: Hrayr Harutyunyan
Ankit Singh Rawat
Aditya Krishna Menon
Seungyeon Kim
Sanjiv Kumar
Venue: ICLR 2023 poster (2023)
Keywords: distillation
kernel methods
neural tangent kernel

Abstract: Despite the popularity and efficacy of knowledge distillation, there is limited understanding of why it helps. In order to study the generalization behavior of a distilled student, we propose a new theoretical framework that leverages supervision complexity: a measure of alignment between teacher-provided supervision and the student's neural tangent kernel. The framework highlights a delicate interplay among the teacher's accuracy, the student's margin with respect to the teacher predictions, and the complexity of the teacher predictions. Specifically, it provides a rigorous justification for the utility of various techniques that are prevalent in the context of distillation, such as early stopping and temperature scaling. Our analysis further suggests the use of online distillation, where a student receives increasingly more complex supervision from teachers in different stages of their training. We demonstrate efficacy of online distillation and validate the theoretical findings on a range of image classification benchmarks and model architectures.

Published as a conference paper at ICLR 2023
SUPERVISION COMPLEXITY AND ITS ROLE IN KNOWLEDGE DISTILLATION
Hrayr Harutyunyan" Ankit Singh Rawat? Aditya Krishna Menon?
Seungyeon Kim² Sanjiv Kumar"
USC Information Sciences Institute hrayrhar @usc. edu, fankitsrawat, adi eaityakmenon, otw.://phhecoo..c.ooooyoaaaaaaao htw.:///.....n...........o.oo...
2 Google Research NYC
ABSTRACT
Despite the popularity and efficacy of knowledge distillation, there is limited un- derstanding of why helps. In order to study the generalization behavior of dis- tilled student, we propose a new theoretical framework that leverages supervision complexity: measure of alignment between teacher- provided supervision and the student's ' neural tangent kernel. The framework highlights a delicate interplay among the teacher's accuracy, the student's margin with respect to the teacher pre- dictions, and the complexity of the teacher predictions. Specifically, it provides a rigorous justification for the utility of various techniques that are prevalent the context of distillation, such early stopping and temperature scaling. Our analysis further suggests the use of online distillation, where a student receives increasingly more complex supervision from teachers in different stages of their training. We demonstrate efficacy of online distillation and validate the theoretical findings on a range of image classification benchmarks and model architectures.
teacher-provided
INTRODUCTION
Knowledge distillation (KD) (Buciluă et al., 2006; Hinton et al., 2015) is a popular method of com- pressing large "teacher" model into more compact "student" model. In its most basic form, this involves training the student to fit the teacher's predicted label distribution or soft labels for each sample. There strong empirical evidence that distilled students usually perform better than stu- dents trained on raw dataset labels (Hinton et al., 2015; Furlanello et al., 2018; Stanton et al., 2021; Gou et al., 2021). Multiple works have devised novel KD procedures that further improve the student model performance (see Gou et al. (2021) and references therein). Simultaneously, several works have aimed to rigorously formalize why KD can improve the student model performance. Some prominent observations from this line of work are that optimization biases in the training objective (Phuong & Lampert, 2019; Ji & Zhu, 2020), lowers variance of the objective (Menon al., 2021; Dao et al., 2021; Ren et al., 2022), increases reg- ularization towards learning "simpler" functions (Mobahi et al., 2020), transfers information from different data views (Allen-Zhu & Li, 2020), and scales per-example gradients based on the teacher's confidence (Furlanello et al., 2018; Tang et al., 2020).
induces certain favorable
Despite this remarkable progress, there still many open problems and unexplained phenomena around knowledge distillation; to name a few:
Why do soft labels (sometimes) help? It is agreed that teacher's soft predictions carry infor- mation about class similarities (Hinton et al., 2015; Furlanello et al., 2018), and that this soft- ness of predictions has regularization effect similar to label smoothing (Yuan et al., 2020). Nevertheless, KD also works in binary classification settings with limited class similarity infor- mation (Müller al., 2020). How exactly the softness of teacher predictions (controlled by a temperature parameter) affects the student learning remains far from well understood.
The role of capacity gap. There is evidence that when there significant capacity gap be- tween the teacher and the student, the distilled model usually falls behind its teacher (Mirzadeh
Work done while interning Google Research NYC.

---

Published as a conference paper at ICLR 2023
student
0.0
(a) Offline distillation
(b) Online distillation
(c) Supervision complexity
Figure 1: Online online distillation. Figures (a) and (b) illustrate possible teacher and student function trajectories in offline and offline KD. The yellow dotted lines indicate KD. Figure (c) plots adjusted supervision complexity of various targets with respect NTKs different stages of train- ing (see $4 for more details).
et al., 2020; Cho & Hariharan, 2019; Stanton et al., 2021). It is unclear whether this is due to difficulties in optimization, or due to insufficient student capacity.
What makes a good teacher? Sometimes less accurate models are better teachers (Cho & Hari- haran, 2019; Mirzadeh et al., 2020). Moreover, early stopped or exponentially averaged models often better teachers (Ren et al., 2022). A comprehensive explanation of this remains elusive.
The aforementioned wide range of phenomena suggest that there is a complex interplay between teacher accuracy, softness of teacher-provided targets, and complexity of the distillation objective.
This paper provides a new theoretically grounded perspective on KD through the lens of supervision complexity. In nutshell, this quantifies why certain targets (e.g., temperature-scaled teacher prob- abilities) may be "easier" for a student model to learn compared to others (e.g., raw one-hot labels), owing to better alignment with the student's s neural tangent kernel (NTK) (Jacot et al., 2018; 8; Lee et al., 2019). In particular, we provide a novel theoretical analysis ($2, Thm. 3 and 4) of the role of supervision complexity on kernel classifier generalization, and use this derive new generaliza- tion bound for distillation (Prop. 5). The latter highlights how student generalization is controlled by a balance of the teacher generalization, the student's 's margin with respect the teacher predictions, and the complexity of the teacher's predictions.
Based on the preceding analysis, we establish the conceptual and practical efficacy of a simple online distillation approach ($4), wherein the student is fit to progressively more complex targets, in the form of teacher predictions at various checkpoints during its training. This method can be seen as guiding the student in the function space (see Fig. 1), and leads to better generalization compared to offline distillation. We provide empirical results on a range of image classification benchmarks confirming the value of online distillation, particularly for students with weak inductive biases.
Beyond practical benefits, the supervision complexity view yields new insights into distillation:
The role of temperature scaling and early-stopping. Temperature scaling and carly-stopping of the teacher have proven effective for KD. We show that both of these techniques reduce the supervision complexity, at the expense of also lowering the classification margin. Online distillation manages to smoothly increase teacher complexity, without degrading the margin.
Teaching a weak student. We show that for students with weak inductive biases, and/or with much less capacity than the teacher, the final teacher predictions are often as complex as dataser labels, particularly during the early stages of training. In contrast, online distillation allows the supervision complexity to progressively increase, thus allowing even a weak student to learn.
-TK and relational transfer. We show that online distillation is highly effective at matching the teacher and student NTK matrices. This transfers relational knowledge in the form of example- pair similarity, as opposed to standard distillation which only transfers per-example knowledge.
Problem setting. We focus classification problems from input domain X' to d classes. We given a training set of n labeled examples {x1,,1))...... Bi),..., (In, }n)}, with one-hot encoded labels Y E {0, 13ah Typically, model fe X - Rd is trained with the softmax cross-entropy loss:
n Σ i=1 y log (fo(x)))
Lve (fo) =
(1)
2

---

Published as a conference paper at ICLR 2023
where (-)) is the softmax function. In standard KD, given trained teacher model g X' + R that outputs logits, one trains a student model fo X' + I2 to fit the teacher predictions. Hinton et al. (2015) propose the following KD loss:
(fd-ce g.
E 1=
((((t)//T)) logo(
(2)
where temperature T > controls the softness teacher predictions. To highlight the effect of KD) and simplify exposition, we assume that the student is not trained with the dataset labels.
2 SUPERVISION COMPLEXITY AND GENERALIZATION
One apparent difference between standard training and KD (Eq. and 2) is that the latter modifies the targets that the student attempts to fit. The targets used during distillation ensure better gener- alization for the student; what the reason for this? Towards answering this question, we present new perspective on KD in terms of supervision complexity. To begin, we show how the general- ization of a kernel-based classifier is controlled by a measure of alignment between the target labels and the kernel matrix. We first treat binary kernel-based classifiers (Thm. 3), and later extend our analysis to multiclass kernel-based classifiers (Thm. 4). Finally, by leveraging the neural tangent kernel machinery, we discuss the implications of our analysis for neural classifiers in $2.2.
2.1 SUPERVISION COMPLEXITY CONTROLS KERNEL MACHINE GENERALIZATION
The notion of supervision complexity is easiest to introduce and study for kernel-based classifiers. We briefly review some necessary background (Scholkopf & Smola, 2001). Let k: X' X - R be positive semidefinite kernel defined over an ipput space X. Any such kernel uniquely determines a reproducing kernel Hilbert space (RKHS) H. of functions from A' to R. This RKHS the completion of the set of functions of form f()) Σ (Z), with E N, R. Any f(x)
E a;k(22; .)) H has (RKHS) norm || >i= Σÿ= (aakk(1); a Ka, where a = (a1,.... TT))T and Kij- = k(z,, xy)) Intuitively, I1fl measures the smoothness of f. e.g., for Gaussian kernel it measures the Fourier spectrum decay of (Scholkopf & Smola, 2001).
For simplicity, we start with the case of binary classification. Suppose {(X;, Yi)) are n i.i.d. examples sampled from some probability distribution X' y, with y RR where positive and negative labels correspond to distinct classes. Let K, = k(),,X,) denote the kernel matrix, and Y = (Y,,.... YT) be the concatenation of all training labels.
Definition 1 (Supervision complexity). The supervision complexity of targets YI...., Yn with spect to a kernel k is defined to be Y K-1Y in cases when K is invertible, and too otherwise.
We now establish how supervision complexity controls the smoothness of the optimal kernel classi- fier. Consider classifier obtained by solving a regularized kernel classification problem:
1 - e(f(x.), Yi) 1l
argmin
FEN TE
where é is loss function and À O. The following proposition shows whenever the supervision complexity is small, the RKHS norm of any optimal solution f" will also be small (see Appendix B for proof). This is an important learning bias that shall help explain certain aspects of KD. Proposition 2. Assume that K is full rank almost surely; Ely. y') 2 O, Vy. Y; and E 0, Vy E Y. Then, with probability 1, for any solution f of (3), we have [| < Y "TK" K-
Equipped with the above result, we now show how supervision complexity controls generalization. In the following, let d., 1 + j0, 1] be the margin loss (Mohri et al., 2018) with scale 7 >> O:
()(aa) = min(1, max (1- - (a/7,03)-
(4)
Theorem 3. Assume that k. sup k(2, x) co and K is full rank almost surely. Further,
assume that Ely, yf) ) 2 0, Vy, E y and Ely, v) = 0, Vy E y. Let Mo = (2/n/22/)) Then, with probability at least 1 for any solution S of problem in Eq. (3), we have
& (sign (Y;) (xx))) 2 K-1Y +2
(2Mp/5) (6)
S (X
v (K) + 3/
(5)
77
2n
3

---

Published as a conference paper at ICLR 2023
The proof is available in Appendix B. One compare Thm. 3 with the standard Rademacher bound for kernel classifiers (Bartlett & Mendelson, 2002). The latter typically consider learning over functions with RKHS norm bounded by constant M O. The corresponding complexity term then decays O( D(yM M Tr (K) /n)), which is data iataa-indepedden.. Consequently, such bound cannot adapt to the intrinsic "difficulty" of the targets Y. In contrast, Thm. considers functions with RKHS norm bounded by the data-dependent supervision complexity term. This results in more informative generalization bound, which captures the "difficulty" of the targets. Here, we note that Arora et al. (2019) characterized the generalization of an overparameterized two-layer neural network via a term closely related to the supervision complexity (see $5 for additional discussion).
The supervision complexity Y T y is small whenever Y is aligned with top eigenvectors of K and/or Y has small scale. Furthermore, one cannot make the bound close to zero by just reducing the scale of targets, as one would need small y to control the margin loss that would otherwise increase due to student predictions getting closer to zero (as the student aims to match Y,).
To better understand the role of supervision complexity, it is instructive to consider two special cases that lead a poor generalization bound: (1) uninformative features, and (2) uninformative labels.
Complexity under uninformative features. Suppose the kernel matrix K is diagonal, so that the kernel provides no information on example-pair similarity; i.e., the kernel is "uninformative". An reveals the key expression in the second term in (5) satisfies:
application of
1 KKIYYT(KK) - n V (E 1-1 Y? (X-,
1 n2.
x.),
N
Vil.
Consequently, this term is least constant in order, and does not vanish as n + DO.
Complexity under uninformative labels. Suppose the labels Y; are purely random, and inde- pendent from inputs X₁. Conditioned on {Xa}. Y T KK-1 " concentrates around its mean by the Hanson Wright inequality (Vershynin, 2018). Hence, 3 Be(K, 6, n) such that with probability 2 1-6, Y K- K-ly] - E Y? Tr(K
Y K Y 2 Eyy
c. Thus, with the same probability,
Y 2 V (KK-) - <) Tr(K) 2 72
1 2 E| - eTr(K))
where the last inequality is by Schway.S For sufficiently large n, the quantity E [X n² dominates e Tr ( (K), rendering the bound of Thm. 3 close to a constant.
2.2 EXTENSIONS: MULTICLASS CLASSIFICATION AND NEURAL NETWORKS
We now show that a result similar to Thm. 3 holds for multiclass classification as well. In addition, we also discuss how our results are instructive about the behavior of neural networks.
Extension to multiclass classification. Let {(X,, Hi be drawn i.i.d. from distribution over X' x V where ) C Rd. Let k X' x X + Rdxd be matrix-valued positive definite kernel and H be the corresponding rector-valued RKHS. As in the binary classification case, we consider a kernel problem in Eq. (3). Let Y (Y,T, ..., ,T, and K be the kernel matrix of training examples:
K (1(X1,X1) k(X,, X1) k(X,,, X,.)
X()
E Bnnxnn
(6)
For : - Rdd and a labeled example (x, v), let ( 3) = f(x), max f(r)y be the prediction margin. Then, the following analogue of Thm. 3 holds (see Appendix C for the proof). Theorem 4. Assume that
co, and K is full rank almost surely. Further, assume that Ely, v/) 2 0, vy. E E and E(y.v) = 0, Vy y. Let My = /x)) Then, with probability at least 1 for any solution f of problem in Eq. (3).
well b(x,
4d(Y K
1og(2Mo/6)
P (xx (X,Y)
Σ 10r- 51)+
(K) + 3
(7)
m
2n
4

---

Published as a conference paper at ICLR 2023
Implications for neural classifiers. Our analysis has far focused kernel- classifiers. While neural networks are not exactly kemnel methods, many aspeets of their performance can be understood via corresponding linearized neural network (sce Ortiz-Jiménez et al. (2021) and refer- ences therein). We follow this approach, and given a neural network fo with current weights fg. we consider the corresponding linearized neural network comprising the linear terms of the Taylor pansion of fo
(z) around 8n (Jacot al., 2018; Lee et al., 2019): fa)( - fao (z) + VaJa, (2)) (# 00). Let w - 0 0g. This network f (z) a linear function with respect to the parameters w, but is
generally non-linear with respect to the input J. Note that Vo (1)) acts as a feature representation, and induces the neural tangent kernel (NTK) (o(x, Vo (a) Vo.oo (x') E Rdddd
Given a labeled dataset S = {(z;, y:) hie()) and loss function L(f: S), the dynamics of gradient flow with learning rate 0 for for can be fully characterized in the function space, and depends only on the predictions at 8g and the NTK ko:
(x') = 11 Kol2', (1:a) V (
(8)
where (1 E Rnd denotes the concatenation of predictions training examples and Ko(x', F1m)) Volo, (x') VaJag (I1=)). Lee et al. (2019) show that as one increases the width of the network or when (0 0o) does not change much during training, the dynamics of the lin- carized and original neural network become close.
When fo is sufficiently overparameterized and L is convex with respect to w, then wi converges to an interpolating solution. Furthermore, for the mean squared error objective, the solution has the minimum Euclidean norm (Gunasekar et al., 2017). As the Euclidean norm of w corresponds to norm of (x) (x) in the vector-valued RKHS H corresponding to ko. training a linearized network to interpolation is equivalent solving the following with small À 0:
1 7 h = argmin - - REH
NE i=1 (J + h(xs) - yi)² + 2 |1
Therefore, the generalization bounds of Thm. and 4 apply to h" with supervision complexity of residual targets 34 - fe, (Iz). However, we are interested in the performance of fe, + h- As the proofs of these results rely on bounding the Rademacher complexity of hypothesis sets of form {h E H: ||^]|| < M). and shifting a hypothesis set by constant function does not change the Rademacher complexity (see Remark 7), these proofs can be easily modified to handle hypothe- ses shifted by the constant function fee.
KNOWLEDGE DISTILLATION: A SUPERVISION COMPLEXITY LENS
We now turn to KD, and explore how supervision complexity affects student's generalization. We show that student's generalization depends on three terms: the teacher generalization, the student's margin with respect to the teacher predictions, and the complexity of the teacher's 's predictions.
3.1 TRADE-OFF BETWEEN TEACHER ACCURACY, MARGIN, AND COMPLEXITY
Consider the binary classification setting of $2, and fixed teacher g : X R that outputs logit. Let {(X,, ())))(een be n i.idd labeled examples, where Y," E {- denotes the ground truth labels. For temperature 7 let Y, A 2 (g()))/) predictions, for sigmoid function a: z + (1 + exp(-2))-1_ Our key observation is: the teacher predictions Y, are accurate enough and have significantly lower complexity compared to ground truth labels Y;", then student kernel method (cf. Eq. (3)) trained with Y; can generalize better than the one trained with Y,. The following result quantifies the trade-off between teacher accuracy, student prediction margin, and teacher prediction complexity (see Appendix B.3 for a proof).
[-1,+1] denote the teacher's soft
Proposition 5. Assume that & = suprex k(x,)) < oo and K is full rank almost surely, (ly.v') 2 0, Vy,v' E Y, and f(y.v) 0, 0, E y. Let Y; and Y be defined as above. Let
5

---

Published as a conference paper at ICLR 2023
Mo [nTT/22/RR1 Then, with probability at least 1 6, any solution fr of problem (3) satisfies PX (X) 20)
+ - (sign (Y:) (X.))
S Pxx (Y" g g( -
student risk
teacher risk
student's 's empirical margin loss W.EL teacher predictions
+ (2 (2 + VT (K))(m)))) +3v/nn (2.3///222//////333333 (2n).
complexity of teacher's 's predictions
Note that similar result is easy to establish for multiclass classification using Thm. 4. The first term in the above accounts for the misclassification rate of the teacher. While this term is not irreducible (it is possible for a student to perform better than its teacher), generally student performs worse that its teacher, especially when there is a significant teacher-student capacity gap. The second term is student's 's empirical margin loss w.r.t. teacher predictions. This captures the price of making teacher predictions too soft. Intuitively, the softer (i.e.. closer to zero) teacher predictions are, the harder it is for the student to learn the classification rule. The third term accounts for the supervision complexity and the margin parameter y. Thus, one has to choose 7 carefully to achieve a good balance between empirical margin loss and nargin-normalized supervision complexity.
The effect of temperature. For fixed margin parameter 7 > O, increasing the temperature makes teacher's predictions Y; softer. On the one hand, the reduced scale decreases the supervision complexity Y K-IY. Moreover, we shall that in the case of neural networks the complexity decreases even further due to Y becoming more aligned with top eigenvectors of K. On the other hand, the scale of predictions of the (possibly interpolating) student f will decrease too, increasing the empirical margin loss. This suggests that setting the value of T is not trivial: the optimal value can be different based on the kernel & and teacher logits g(x.).
3.2 FROM OFFLINE TO ONLINE KNOWLEDGE DISTILLATION
We identified that supervision complexity plays key role in determining the efficacy of a distillation procedure. The supervision from a fully trained teacher model can prove to be very complex for a student model in an early stage of its training (Fig. Ic). This raises the question: is there value in providing progressively difficult supervision to the student? In this section, we describe a simple online distillation method, where the the teacher is updated during the student training.
Over the course of their training, neural models learn functions of increasing complexity (Kalimeris et al., 2019). This provides natural way to construct set of teachers with varying prediction complexities. Similar to Jin et al. (2019), for practical considerations of not training the teacher and the student simultaneously, we assume the availability of teacher checkpoints over the course of its training. Given m teacher checkpoints at times T = {ts hi][m) during the f-th step of distillation, the student receives supervision from the teacher checkpoint at time min E T :'' > 1). Note that the student is trained for the same number of epochs in total as in offline distillation. Throughout the paper we use the term "online distillation" " for this approach (cf. Algorithm of Appendix A).
Online distillation can be seen guiding the student network to follow the teacher's 's trajectory in function space (see Fig. 1). Given that NTK can be interpreted as a principled notion of ex- ample similarity and controls which examples affect each other during training (Charpiat et al., 2019), it is desirable for the student to have an NTK similar to that of its teacher at each time step. To test whether online distillation also transfers NTK, we propose measure similarity between the final student and final teacher NTKs. For computational efficiency we work with NTK matrices corresponding to a batch of examples (bd x bd matrices). Explicit computation of even batch NTK matrices can be costly, especially when the number of classes d is large. We propose to view student and teacher batch NTK matrices (denoted by K2 and Kg respec- tively) as operators and measure their similarity by comparing their behavior on random vectors: sim(K,, K₂) = E.-,) [(,yv, /,u)/ / [ to account for scale differences of K2, and Ky. The kernel-vector products appearing in this similar- ity measure above can be computed efficiently without explicitly constructing the kernel matrices. For example, v Vefe(#1.s) (Vefe (x1:))) can be computed with one vector-Jacobian prod- uct followed by a Jacobian-veetee product. The former can be computed efficiently using backprop- agation, while the latter can be computed efficiently using forward-mode differentiation.
Note that the cosine distance is used

---

Published as a conference paper at ICLR 2023
Table I: Results on CIFAR-100.
Setting
No KD
Offline KD T=
Online KD
Teacher
T=1
ResNet-56 - LeNet-5x8
47.3 0.6
50.1
59,9
6.2
66.1 0.4
72.0
ResNet-56 ResNet-20
67.7 =
68.2
71.6 0.2
6.
71.4 0.3
72.0
ResNet- + LeNet-5x8
47.2 0 0.5
4.8
59.0 0.3
60.8 0.2
65.8 0.2
73.4
ResNet- 110 -> ResNet-20
67.8 0.3
6..8
71.2 0.0
69.0
71.4 0.0
73.4
Table 2: Results Tiny ImageNet.
Setting
No KD
Offline KD
Online KD
Teacher
MobileNet-V V3-125 MobileNet-V3-35
0.2
59.2 0.1
6.22
60.7 0.2
62.3 4 0.3
62.7
ResNet-101 MobileNet-V3-35
0.2
59.4 0.5
6.2
61.1 = 0.3
62.0 1 0.3
66.0
MobileNet-V3-ie + VGG-16
0.3
54.1
594
58.9 0.7
62.3 0.3
62.7
ResNet-101 - VGG-16
4.
53.1 011:04
60.6
60.4
64.0 0.1
EXPERIMENTAL RESULTS
We present experimental results showcase the importance of supervision complexity in dis- tillation, and to establish efficacy of online distillation.
4.1 EXPERIMENTAL SETUP
We consider standard image classification benchmarks: CIFAR-10, CIFAR-100, and Tiny- ImageNet. Additionally, we derive binary classification task from CIFAR-100 by grouping the first and last 50 classes into two meta-classes. We consider teacher and student architectures that are ResNets (He et al., 2016), VGGs (Simonyan & Zisserman, 2015), and MobileNets (Howard al., 2019) of various depths. As a student architecture with relatively weaker inductive biases, we also consider the LeNet-5 (LeCun et al., 1998) with 8 times wider hidden layers. We use stan- dard hyperparameters (Appendix A) to train these models. We compare (1) regular one-hot training (without any distillation), (2) regular offline distillation using the temperature-scales softmax cross- entropy, and (3) online distillation using the same loss. For CIFAR- 10 and binary CIFAR-100, we also consider training with mean squared error (MSE) loss and its corresponding KD loss:
Emse (fo)
Σ 2n 1=1
1
|1 - fo(x;)1
T
Σ
(10)
2n
The MSE loss allows for interpolation case of one-hot labels ys, making it amenable to the analysis in $2 and $3. Moreover, Hui & Belkin (2021) show that under standard training, the CE and MSE losses perform similarly; as we shall see, the same is true for distillation as well.
As mentioned in Sec. 1, in all KD experiments student networks receive supervision only through knowledge distillation loss (i.e., dataset labels are not used). This choice help us decrease differences between the theory and experiments. Furthermore, in our preliminary experiments we observed that this choice does not result in student performance degradation (see Appendix D).
4.2 RESULTS AND DISCUSSION
Tables 1, and Table (Appendix D) present the results (mean and standard deviation of test accuracy over 3 random trials). First, we see that online distillation with proper temperature scaling typically yields the most accurate student. The gains over regular distillation are particularly pro- nounced when there is large teacher-student gap. For example, on CIFAR-100, ResNet to LeNet distillation with temperature scaling appears to hit a limit of ~ 60% accuracy. Online distillation however manages to further increase accuracy by +6%, which is 20% increase compared to standard training. Second, the similar results on binary CIFAR- 100 shows that "dark knowledge" in the form of membership information in multiple classes is not necessary for distillation succeed.
The results also demonstrate that knowledge distillation with the MSE loss of (10) has a qualita- tively similar behavior KD with CE objective. We these MSE models highlight the role of

---

Published as a conference paper at ICLR 2023
Table 3: Results on binary CIFAR-100. Every second line is MSE student.
Setting
No KD
Offline KD
Online KD
Teacher
7
T=
T=
==
ResNet-56 + LeNet-5x8
71.5 + 0.2
72.4 + 0.1
73.6 + 0.2
74.7 + 0.2
76.1 + 0.2
77.9
ResNet-56 LeNet-5x8
71.5 0.4
71.9 0.3
1.3
75.1 1 0.3
75.1 0.1.
77.9
ResNet-56 + ResNet-20
75.8 +: 0.5
76.1 0.2
77.1
77.8 + 0.3
78.1
77.9
ResNet-56 + ResNet-20
76.1 # 0.5
76.0 = 0.2
0.3
78.0 = 0.2
78.4 + 0.3
77.9
ResNet-110 10 LeNet-5x8
71.4 0.4
71.9
0..9
74.3 + 0.3
75.4 0.3
78.4
ResNet-1 10 LeNet-5x8
71.6 0.2
71.5 0.4 0.4
72.6
74.8 + 0.4
74.6 + 0.2
78.4
R 10
ResNet-20
76.0 1 0.3
76.0 1 0.2
0.10
77.3 1 0.2
78.0 1 0.4
78.4
ResNet-1 10 ResNet-20
76.1 1 0.2
76.4 1 0.3
77.6 77.6.100 0.3
77.9 + 0.2
78.1 + 0.1
78.4
canoa Soucher
Terperouu
Epodas
(a) Normalized complexity
(b) Temperature effect
(c) Teacher averaging
Figure 2: Supervision complexity for various targets. On the left: Normalized adjusted supervision complexities of various targets with respect to a LeNet-5x8 network at different stages of its training. In the middle: The effect of temperature the supervision complexity of an offline teacher for LeNet-5x8 after training for 25 epochs. On the right: The effect of averaging teacher predictions.
supervision complexity. As an instructive case, we consider a LeNet-5x8 network trained on binary CIFAR-100 with the standard MSE loss function. For a given checkpoint of this network and a given set m labeled (test) examples {(X,, X.) we compute the adjusted supervision complex- ity 1/n f(X1mm)) K-
(m))m)) Tr (K), where f denotes the current prediction function, and K is derived from the current NTK. Note that the subtraction of initial predictions is the appropriate way to measure complexity given the form the optimization problem (9), As the training NTK matrix becomes aligned with dataset labels during training (see Baratin et al. (2021) and Fig. of Appendix D), we pick {Xi to be a set of 2 test examples.
Comparison of supervision complexities. We compare the adjusted supervision complexities of random labels, dataset labels, and predictions an offline and online ResNet-56 teacher predictions with respect to various checkpoints of the LeNet-5x8 network. The results presented in Fig. Ic indicate that the dataset labels and offline teacher predictions are as complex as random labels in the beginning. After some initial decline, the complexity of these targets increases the network starts to overfit. Given the lower bound on the supervision complexity of random labels (see $2), this increase means that the NTK spectrum becomes less uniform (see Fig. 6 of Appendix D).
In contrast to these static targets, the complexity of the online teacher predictions smoothly increases, and is significantly smaller for most of the epochs. To account for softness differences of the various targets, we consider plotting the adjusted supervision complexity normalized by the target norm ym || As shown in Fig. 2a, the normalized complexity of offline and online teacher predictions is smaller compared to the dataset labels, indicating a better alignment with top eigenvectors of the LeNet NTK. Importantly, we see that the predictions of an online teacher have significantly lower normalized complexity in the critical early stages of training. Similar observations hold when complexities are measured with respect to a ResNet-20 network (see Appendix D).
Average teacher complexity. Ren et al. (2022) observed that teacher predictions fluctuate over time, and showed that using exponentially averaged teachers improves knowledge distillation. Fig. 2c demonstrates that the supervision complexity of an online teacher predictions is always slightly larger than that the average predictions of teachers of the last 10 preceding epochs.
Effect of temperature scaling. As discussed earlier, higher temperature makes the teacher predic- tions softer, decreasing their norm. This has a large effect on supervision complexity (Fig. 2b). Even when controls for the norm of the predictions, the complexity still decreases (Fig. 2b).
8

---

Published as a conference paper at ICLR 2023
corrdlalorr
N RD 318 re sp
0.55
0.994
in RD
00335
orlin
Trann danterty
KD
0.992
0.55
0:30
Tram 1M60
0.25
0.989
0.45
0:20
0.966
9.15
0.40
10-50
0.10
0.822
0.80
4%
Text
Tixil
(a) LeNet-5x8 student
(b) ResNet-20 student
(c) LxNet-5x8 student
Figure 3: Relationship between test accuracy, train NTK similarity, and train fidelity for CIFAR-100 students training with either ResNet-56 teacher (panels (a) and (c)) or ResNet-110 (panel (b)).
NTK similarity. Remarkably, we observe that across all of our experiments, the final test accuracy of the student is strongly correlated with the similarity of final teacher and student NTKs (see Figures 3,9, and 10). This cannot be explained by better matching the teacher predictions. that the final fidelity (the rate of classification agreement of a teacher-student pair) measured on training set has no clear relationship with test accuracy. Furthermore, we see that online KD results in better NTK transfer without an explicit regularization loss enforcing such transfer.
fact, we see
5 RELATED WORK
Due to space constraints, we briefly discuss the existing works that are the most closely related to our exploration in this paper (see Appendix E for a more comprehensive account related work.)
Supervision complexity. The key quantity in our work is supervision complexity T K Cris- tianini et al. (2001) introduced a related quantity Y T KY called kernel-target alignment (KTA) and derived a generalization bound with it for expected Parzen window classifiers. Deshpande et al. (2021) use KTA for model selection in transfer learning. Ortiz-Jimént et al. (2021) demonstrate that when NTK-target alignment is high, learning is faster and generalizes better. Arora et al. (2019) prove a generalization bound for overparameterized two-layer neural networks with NTK parame- terization, trained with gradient flow. Their bound is roughly (Y (K*)) 1/2 /VT, where K is the expected NTK matrix at a random initialization. Our bound of Thm. 3 can be seen as gener- alization of this result for all kernel methods. including lincarized neural networks of any depth and sufficient width, with the only difference of using the empirical NTK matrix. Belkin et al. (2018) warns that bounds based on RKHS complexity of the learned function can fail to explain the good generalization of kernel methods under label noise.
Mobahi et al. (2020) prove that for kernel methods with RKHS norm regularization, self-distillation increases regularization strength. Phuong & Lampert (2019), while studying self-distillation of deep linear networks, derive a bound of the transfer risk that depends on the distribution of the acute angle between teacher parameters and data points. This is in spirit related to supervision complexity measures an "alignment " between the distillation objective and data. Ji & Zhu (2020) extend this results to linearized neural networks, showing that A K '',,, where A, is the logit change during training, plays key role in estimating the bound. Their bound is qualitatively different than ours, and A K K becomes ill-defined for hard labels.
it
Non-static teachers. Multiple works consider various approaches that train multiple students si- multaneously to distill either from each other or from an ensemble (see, e.g., Zhang et al., 2018; Anil et al., 2018; Guo et al., 2020). Zhou et al. (2018) and Shi et al. (2021) train teacher and student together while having common architecture trunk and regularizing teacher predictions to close that of students, respectively. Jin et al. (2019) study route constrained optimization which is closest to the online distillation in $3.2. They employ few teacher checkpoints perform multi-round KD. We complement this line of work by highlighting the role of supervision complexity and by demonstrating that online distillation can be very powerful for students with weak inductive biases.

---

Published as a conference paper at ICLR 2023
REFERENCES
Zeyuan Allen-Zhu and Yuanzhi Li. Towards understanding ensemble, knowledge distillation and self-distillation in deep learning. CoRR, abs/2012.09816, 2020.
Rohan Anil, Gabriel Pereyra, Alexandre Passos, Róbert Ormándi, George Dahl, and Geof- frey E. Hinton. Large scale distributed neural network training through online distillation. CoRR, 0bss/800.032533 2018.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pp- 322-332. PMIR, 2019.
Aristide Baratin, Thomas George, César Laurent, R Devon Hjelm, Guillaume Lajoie, Pascal Vin- cent, and Simon Lacoste-Julien. Implicit regularization via neural feature alignment. Interna- tional Conference on Artificial Intelligence and Statistics, pp. 2269-2277. PMLR, 2021.
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nvv)4463448, 2002.
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to under- stand kernel learning. In International Conference Machine Learning, pp. 541-545 PMLR, 2018.
Lucas Beyer, Xiaohua Zhai, Amélie Royer, Larisa Markeeva, Rohan Anil, and Alexander Kolesnikov. Knowledge distillation: A good teacher is patient and consistent. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10925-10934) 2022.
Cristian Buciluă, Rich Caruana, and Alexandru Niculescu-Mizii. Model compression. Proceed- ings of the 12th ACM SIGKDD International Conference Knowledge Discovery and Data Min- ing. KDD '06, pp. 535-541, New York, NY, USA, 2006. Association for Computing Machinery. ISBN 1595933395. doi: 10. 10.1145/1 150402. 150464.
Guillaume Charpiat, Nicolas Girard, Loris Felardos, and Yuliya Tarabalka. Input similarity from the neural network perspective. Advances in Neural Information Processing Systems, 32, 2019.
Defang Chen, Jian-Ping Mei, Can Wang, Yan Feng, and Chun Chen. Online knowledge distillation with diverse peers. Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 3430-3437, 2020.
Defang Chen, Jian-Ping Mei, Hailin Zhang, Can Wang, Yan Feng, and Chun Chen. Knowledge distillation with the reused teacher classifier. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pp. 11933-11944 2022.
Jang Hyun Cho and Bharath Hariharan. On the efficacy of knowledge distillation. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 4794-4802, 2019.
Nello Cristianini, John Shawe-Taylor, Andre Elisseeff, and Jaz Kandola. On kernel-target alignment. Advances in neural information processing systems, 14, 2001.
Tri Dao, Govinda M Kamath, Vasilis Syrgkanis, and Lester Mackey. Knowledge distillation as semiparametric inference. In International Conference Learning Representations, 2021.
Aditya Deshpande, Alessandro Achille, Avinash Ravichandran, Hao Li, Luca Zancato, Charless Fowlkes, Rahul Bhotika, Stefano Soatto, and Pietro Perona. A lincarized framework and new benchmark for model selection for fine-tuning. arXiv preprint arXiv:2102.0008. 2021.
Tommaso Furlanello, Zachary Lipton, Michael Tschannen, Laurent Itti, and Anima Anandkumar. Born again neural networks. In International Conference on Machine Learning, pp. 1607-1616. PMLR, 2018.
Jianping Gou, Baosheng Yu, Stephen Maybank, and Dacheng Tao. Knowledge distillation: A survey. International Journal of Computer Vision, 17966):189-11899 2021.
10

---

Published as a conference paper at ICLR 2023
Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Sre- bro. Implicit regularization in matrix factorization. Advances in Neural Information Processing Systems, 30, 2017.
Qiushan Guo, Xinjiang Wang. Yichao Wu, Zhipeng Yu, Ding Liang, Xiaolin Hu, and Ping Luo. Online knowledge distillation via collaborative learning. In Proceedings of the IEEE/CVF Con- ference on Computer Vision and Pallern Recognition, pp. 11020-11029, 2020.
Bobby He and Mete Ozay. Feature kernel distillation. In International Conference on Learning Representations, 2021.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Geoffrey Hinton, Oriol Vinyals, Dean, et al. Distilling the knowledge in neural network. arXiv preprint arXiv:1503 02531, 2(7), 2015.
Andrew Howard, Mark Sandler, Grace Chu, Liang-Chieh Chen, Bo Chen, Mingxing Tan, Weijun Wang. Yukun Zhu, Ruoming Pang. Vijay Vasudevan, et al. Searching for mobilenetv3. In Pro- ceedings of the IEEE/CVF international conference on computer vision, pp. 1314-1324, 2019.
Like Hui and Mikhail Belkin. Evaluation of neural architectures trained with square loss vs cross- entropy in classification tasks. In International Conference on Learning Representations, 2021.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett (eds.), Advances Neural Information Processing Systems 31, pp. 8571- 8580. Curran Associates, Inc., 2018.
Guangda Ji and Zhanxing Zhu. Knowledge distillation in wide neural networks: Risk bound, data efficiency and imperfect teacher. Advances Neural Information Processing Systems, 33:20823- 20833, 2020.
Xiao Jin, Baoyun Peng. Yichao Wu, Yu Liu, Jiaheng Liu, Ding Liang, Junjie Yan, and Xiaolin Hu. Knowledge distillation via route constrained optimization. Proceedings of the IEEF/CVF International Conference Computer Vision (ICCV), October 2019.
Dimitris Kalimeris, Gal Kaplun, Preetum Nakkiran, Benjamin Edelman, Tristan Yang, Boaz Barak, and Haofeng Zhang. Sgd on neural networks learns functions of increasing complexity. Advances in Neural Information Processing Systems, 32, 2019.
Vitaly Kuznetsov, Mehryar Mohri, and U Syed. Rademacher complexity margin bounds for learning with a large number of classes. In ICML Workshop on Extreme Classificution: Learning with Very Large Number of Labels, volume 2, 2015.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1) (6217):27782232, 1998.
Michel Ledoux and Michel Talagrand. Probability in Banach Spaces: isoperimetry and processes, volume 23, Springer Science & Business Media, 1991.
Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve linear models under gradient descent. In Advances in neural information processing systems, pp. 8572-8583, 2019.
Aditya K Menon, Ankit Singh Rawat, Sashank Reddi, Seungyeon Kim, and Sanjiv Kumar. A statisti- cal perspective on distillation. In International Conference on Machine Learning, pp. 7632-7642.
PMLR, 2021.
Seyed Iman Mirzadeh, Mehrdad Farajtabar, Ang Li, Nir Levine, Akihiro Matsukawa, and Hassan Ghasemzadeh. Improved knowledge distillation via teacher assistant. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pp. 5191-5198, 2020.

---

Published as a conference paper at ICLR 2023
Hossein Mobahi, Mehrdad Farajtabar, and Peter Bartlett. Self-distillation amplifies regularization in hilbert space. Advances in Neural Information Processing Systems, 33:3351-3361, 2020.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning.
MIT press, 2018.
Rafael Müller, Simon Kornblith, and Geoffrey E. Hinton. abs/2002.03936, 2020.
Subclass distillation.
CoRR,
Guillermo Ortiz-Jiménez, Seyed-Mohsen Moosavi-Dezfooli, and Pascal Frossard. What can lin- earized neural networks actually say about generalization? Advances in Neural Information Processing Systems,
2021.
Wonpyo Park, Dongju Kim, Yan Lu, and Minsu Cho. Relational knowledge distillation. Proceed- ings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pp. 3967-3976, 2019.
Nikolaos Passalis and Anastasios Tefas. Learning deep representations with probabilistic knowledge transfer. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 268-284, 2018.
Mary Phuong and Christoph Lampert. Towards understanding knowledge distillation. Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pp. 5142-5151. PMLR, 09-15 Jun 2019.
Yi Ren, Shangmin Guo, and Danica Sutherland. Better supervisory signals by observing learning paths. In International Conference Learning Representations, 2022.
Mehdi Rezagholizadeh, Aref Jafari, Puneeth S.M. Saladi, Pranav Sharma, Ali Saheb Pasand, and Ghodsi. Pro-KD: Progressive distillation by following the footsteps of the teacher. In Proceedings of the 29th International Conference on Computational Linguistics, pp. 4714-4727, 2022.
Adriana Romero, Samira Ebrahimi Kahou, Polytechnique Montréal, Y. Bengio, Université De Montréal, Adriana Romero, Nicolas Ballas, Samira Ebrahimi Kahou, Antoine Chassang, Carlo Gatta, and Yoshua Bengio. Fitnets: Hints for thin deep nets. In in International Conference Learning Representations (ICLR, 2015.
Bernhard Scholkopf and Alexander J. Smola. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press, Cambridge, MA, USA, 2001. ISBN 0262194759.
Wenxian Shi, Yuxuan Song, Hao Zhou, Bohan Li, and Lei Li. Follow your path: progressive method for knowledge distillation. In Nuria Oliver, Fernando Pérez-Cruz, Stefan Kramer, Jesse Read, and Jose A. Lozano (eds.), Machine Learning and Knowledge Discovery Databases. Research Track, pp. 661,611, Cham, 2021. Springer International Publishing. ISBN 978-3-030- 86523-8.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceed- ings, 2015.
Samuel Stanton, Pavel Izmailov, Polina Kirichenko, Alexander A Alemi, and Andrew G Wilson. Does knowledge distillation really work? Advances in Neural Information Processing Systems, 34:6906-6919 2021.
Jiaxi Tang, Rakesh Shivanna, Zhe Zhao, Dong Lin, Anima Singh, Ed Chi, and Sagar Jain. Under- standing and improving knowledge distillation. arXiv preprint arXiv:2002.03332, 2020.
Yonglong Tian, Dilip Krishnan, and Phillip Isola. Contrastive representation distillation. In Inter-
national Conference Learning Representations, 2020.
12

---

Published as a conference paper at ICLR 2023
Frederick Tung and Greg Mori. Similarity-prssrvingg knowledge distillation. In Proceedings the IEEE/CVF International Conference on Computer Vision, pp. 1365-1333 1374, 2019.
Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Sci- ence. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018. doi: 1011/999 108231596.
Chenglin Yang, Lingxi Xie, Chi Su, and Alan L. Yuille. Snapshot distillation: Teacher-student optimization in one generation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 2859-2868, 2019.
Li Yuan, Francis EH Tay, Guilin Li, Tao Wang, and Jiashi Feng. Revisiting knowledge distillation via label smoothing regularization. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 3903 3911, 2020.
Sergey Zagoruyko and Nikos Komodakis. Paying more attention to attention: Improving the per- formance of convolutional neural networks via attention transfer. In International Conference on Learning Representations, 2017.
Ruixiang Zhang, Shuangfei Zhai, Etai Littwin, and Joshua M. Susskind. Learning representation from neural fisher kernel with low-rank approximation. In International Conference Learning Representations, 2022.
Ying Zhang, Tao Xiang, Timothy M Hospedales, and Huchuan Lu. Deep mutual learning. In Proceedings of the IEFE conference computer vision and pattern recognition, pp. 4320-4328, 2018.
Guorui Zhou, Ying Fan, Runpeng Cui, Weijie Bian, Xiaoqiang Zhu, and Kun Gai. Rocket launching: universal and efficient framework for training well-performing light net. In Proceedings of the AAAI Conference Artificial Intelligence, volume 32, 2018.
13

---

Published as a conference paper at ICLR 2023
Algorithm Online knowledge distillation.
Require:
Training sample S: teacher checkpoints (g(")),... .(....((m))) steps T; minibatch size
]; temperature 7 0; training
1: for tt= 1,..,.. do
2: Draw random b-sized minibatch 5' from S
3: Compute nearest teacher checkpoint t* = minfi i E [m]] t > t
4: Update student <- - 1/2 VaLad-ea coooa-eooJoo (() over S'
5: end for
6: return fe
A HYPERPARAMETERS AND IMPLEMENTATION DETAILS
Dataset
Model
Learning rate
ResNet-56 (teacher)
0.1
ResNet-1 10 (teacher)
0.1
CIFAR-10, CIFAR-100, binary CIFAR-100
ResNet-20 (CE or MSE students)
0.1
LeNet-5x8 (CE MSE students)
0.04
MobileNet- V3-125 (teacher)
0.04
Tiny ImageNet
ResNet-101 (teacher)
0.1
MobileNet-Val V3-35 (student) VGG-16 (student)
0.04
0.01
Table 4: Initial learning rates for different dataset and model pairs.
In all experiments we use stochastic gradient descent optimizer with 128 batch size and 0.9 Nesterov momentum. The starting learning rates presented in Table 4. All models for CIFAR datasets are trained for 256 epochs, with a learning schedule that divides the learning rate by 10 at epochs 96, 192, and 224. All models for Tiny ImageNet that divides the learning rate by 10 at epochs 75 and 135. The learning rate is warmed-up linearly to its initial value in the first 10 and 5 epochs for CIFAR and Tiny ImageNet models respectively. All VGG and ResNet models use 2e-4 weight decay, while MobileNet models use 1e-5 weight decay.
trained for 200 epochs, with a learning rate schedule
The LeNet-5 uses ReLU activations. We the CIFAR variants of ResNets in experiments with CIFAR-10 or (binary) CIFAR-100 datasets. Tiny ImageNet examples are resized to 224x224 res- olution suit the original ResNet, VGG and MobileNet architectures. In all experiments use standard data augmentation random cropping and random horizontal flip. In all online learning methods we consider one teacher checkpoint per epoch.
B PROOFS
In this appendix present the deferred proofs. We the following definition of Rademacher complexity (Mohri et al., 2018).
Definition (Rademacher complexity). Let G be family of functions from Z to IR and 2i,..., Zn be i.i.d. examples from a distribution P Z. Then, the empirical Rademacher complexity of G with respect to (Z,...., Z,.) is defined as
Ri (G) Erg
sup gEG m
o.g Zi)
(11)
where a; are independent Rademacher random variables (i.e., uniform random variables taking val- in (-1, 1)). The Rademacher complexity of G is then defined as
R, (g) )- = EE,,....
Pin (9)
(12)
14

---

Published as a conference paper at ICLR 2023
Remark 7. Shifting the hypothesis class g by constant function does not change the empirical Rademacher complexity:
1
R (U + 9: 9::99)) E Ba..
sup
oi (f(Z)) + +
(13)
gEg m
E oo
Σ ozf(Zz)
sup
1
Σ o:g Zi))
(14)
i=1
gEG
i=1
sup DEG m
a.g (4,)
(9).
(15)
Given the kernel classification setting described in Sec. 2.1, first prove a slightly more general variant a classical generalization gap bound in Bartleut & Mendelson (2002, Theorem 21).
Theorem 8. Assume suprex k(x, x) oo. Fix any constant M > Then with probability at least
1 - 8, every function f E H with || S M satisfies
2M
(In (2/6)
Px,x(Y < 0) S
o (sign (Y:) f(x:)) + yn
(T((K)+ + 33/
(16)
2m
Proof. Let {f E :: || - M) and consider the following class of functions:
g {(x, v) + (s)g F).
(17)
By the standard Rademacher complexity classification generalization bound (Mohri et al., 2018, Theorem 3.3), for any d > 0. with probability at least 1 8, the following holds for all f E F:
log(2/8)
Ex, (sggsig
Sy (Ysign(Y))((X))) (9) + +3
(18)
2n
Therefore, with probability at least 1 8, for all f f J
log log(2/44 (2/6)
Pxx (X) S 0) - (sign(Y)) + 22h (9) + 3/
(19)
2n
To finish the proof, we upper bound Rr, (G):
(g) Eg
sup gEg
ogg(X,,))) Yi)
(20)
1
Eg
sup fEF n
010 (sign (sign(Y))
(21)
1=1
1
E E
sup fEF n
o sign (Y)){(X)))
(22)
i=1
sup FEF n 1=1
Σ (X,)
(23)
1 Rr,
(24)
where the third line is due to Ledoux Talagrand (1991). By Lemma 22 of Bartlett & Mendelson (2002), thus conclude that
M (F)
(K).
(25)
n
n
15

---

Published as a conference paper at ICLR 2023
B.1 PROOF OF PROPOSITION 2
Proof of Proposition 2. As K is a full rank matrix almost surely, then with probability there exists vector E RR, such that Ka = Y. Consider the function f(x) E a,k(X,, H. Clearly, f(X;) = Y, Vi [n]. Furthermore, |l = a Ka Y K- The existence of such f E H with zero empirical loss and the assumptions the loss function imply that any optimal solution of problem (3) has norm at most Y K K-
B.2 PROOF OF THM..
Proof. To get generalization bound for f is tempting to use Thm. 8 with M = [[ However, ||] is random variable depending the training data and is invalid choice for the constant M. This issue can be resolved by paying small logarithmic penalty.
TVp For any M 2 Ma = 2/R
the bound of Thm. is vacuous. Let us consider the set of integers
M {1, ...., ,M and write Thm. for each element of M with M/Mo failure probability. By union bound, we have that with probability at least 1 - 6, all instances of Thm. with M chosen from M hold simultaneously.
I K-- 2 Mo. then the desired bound holds trivially, as the right-hand side becomes least 1. Otherwise, we set M = V K- E .M and consider the corresponding part of the union bound. We thus have that with at least 1 probability, every function f E F with II s M satisfies
+ 2M (K) + 3/
In (2Ma/8)
Px,(( & 50) (sign
2n
As by Prop. 2 any optimal solution f has at most Y K-IY and M V K IY +1, we have with probability at least - 5,
oy (sign (X:))((x)) 2 Y K-1Y +Y-++ +2
Px (x)
Tr TT(K)
7m
(2Mo/5)
+ 3v
2m
B.3 PROOF OF PROP. 5
Prop. 5 is a simple corollary of Thm. 3.
Proof. We have that
PY. 0) Px.r- (xx"
Pxxx (Ytgg((("XX))""))"" + (x( 5)).
The rest follows from bounding (x( < 0) using Thm.
C EXTENSION TO MULTICLASS CLASSIFICATION
Let us now consider the case of multiclass classification with d classes. Let k X x X - Rdxd be a matrix-valued positive definite kernel. For every x X' and a E Rdd let kya = k(-xz)a ) be the function from X to 2d defined the following way:
k=a(x') k(æ', x)a, for all x' E E.
(26)
For [0, 1] hounded loss functions, it also holds that || 11 2/A. This is not of direct relevance to will he interested in with small X 0.
16

---

Published as a conference paper at ICLR 2023
With any such kernel & there is unique vector-valued RKHS H. of functions from X to R This RKHS is the completion of span {Ria : E X, a E Rd with the following inner product:
m
" m ag Manzz)))o)
Σ
Kn, Ois
Ikeza
(27)
j=1
1=1
For any f E Hi the norm Il H is defined /ff.f'n Therefore, if f(z) Ei=1 K2 then
(f.f)x = Σ a I();
(28)
1==1
a T Ka,
(29)
where T _a]]..... , e Rnd and
x1( K
M(21,Tn)
Rudxnd
(30)
le (1),, T1)
Suppose {(x, Y:) are n i.i.d. examples sampled from some probability distribution on X >, where Y' C RRd As in the binary classification case, we consider the regularized kernel problem (3). Let Y (Y₁T ...... Y of Prop. in this vector-valued setting.
be the concatenation of targets. The following proposition is the analog
Proposition 9. Assume K is full rank almost surely. Assume also E(y, y¹) 2 0, Vy, y' E Y and Eyy, y) Vy E y. Then, with probability for any solution f of (3), we have that
If l S Y T---Y
(31)
Proof. With probability the kernel matrix K full rank. Therefore, there exists vector = (0 ...., an E Rnd with a; E Rd such that Ka Y. Consider the function f(x) = Σt kx,a E H. Clearly, f(X,) Y, Vi [n]. Furthermore.
| = T Ka
(32)
= K-YY.
(33)
The existence of such fx) E H with zero empirical loss and assumptions the loss function imply that any optimal solution of problem (3) has norm at most Y K-1Y.
As in the main text, for hypothesis f X - I2 and a labeled example (æ,, y). let pf(x, y) = (x), maxy+v (z)) be the prediction margin. We now restate Thm. and present proof. Theorem 10 (Thm. restated). Assume that k = sup (),, < cc, and K is full rank almost surely. Further, assume that E(y, > 0, Vy, y' E y and Ely, 4) = 0, Vy E Y. Let Mo [TVT/(AdyR)]. Then, with probability least ö, for any solution f of problem in Eq. (3),
4d(Y T K- +1) (r(
(X,) 50)
1 Hop (Xa, Y)) 2
7n
log (og(2o//))
+ +3V
(34)
2n
Proof. Consider the class of functions F ( E H |1/1|| < M) for some M > 0. By Theorem 2 of Kuznetsov et al. (2015), for any 7 and 8 0, with probability at least 1 8, the following bound holds for all f E F.?
4d RR
log(2/0)
Ex 0)
n Σ 1 Y.) < 7)
(F)+ 3
(35)
2n
Note that their result is in terms of Rademacher complexity rather than empirical Rademacher complexity. The variant we use can be proved with the same proof, with a single modification of bounding R(g) with empirical Rademacher complexity of & using Theorem 3.3 of Mohri al. (2018).
17

---

Published as a conference paper at ICLR 2023
where F ((..)) + f(x)y Fi [d]}. Next upper bound the empirical Rademacher complexity of F:
"
(F) BoI....................
sup WEld SM n
oxi((x)ly
(36)
Bo
sup
o.,((x))s
(y is the one-hot enc. of y)
(37)
SM
sup
h
oixx,y
(reproducing property)
(38)
WEI
SM
H
E An
sup wEld
Σ
oikx.y
(Cauchy-Schwaa
(39)
1=1
1
M
E Boi....on
sup yELd
(Jensen's 's inequality)
(40)
n
71
M
E Bog
o
(41)
71
M
E E.......
Σ
(42)
M
E
Σ |oo
(independence of o;))
(43)
M
XT)x Xily
y Tk(,,
(44)
M
(K).
(45)
The proof is concluded with the same reasoning of the proof of Thm. 3.
D ADDITIONAL RESULTS AND DISCUSSION
In this appendix we present additional results and discussion to support the main findings of this work.
On early stopped teachers. Cho & Hariharan (2019) observe that sometimes offline KD works bet- ter with early stopped teachers. Such teachers have worse accuracy and perhaps results smaller student margin, but they also have significantly smaller supervision complexity (see Fig. 2a), which provides a possible explanation for this phenomenon.
Teaching students with weak inductive biases. As we saw earlier, fully trained teacher can have predictions as complex as random labels for weak student at initialization. This low alignment of student NTK and teacher predictions can result in memorization. In contrast, early stopped teacher captures simple patterns and has a better alignment with the student NTK, allowing the student to learn these patterns in generalizable fashion. This feature learning improves the student NTK and allows learning more complex patterns in future iterations. We hypothesize that this the mechanism that allows online distillation outperform offline distillation in some cases.
18

---

Published as a conference paper at ICLR 2023
Table 5: Results on CIFAR-10. Every second line is an MSE student.
Setting
No KD
Offline KD
Online KD
Teacher
7
T
7 4
ResNet-55 LeNet-5x8
81.8 + 0.5
82.4 = 0.5
86.0 0.2
86.8 + 0.2
88.6 + 0.1
93.2
ResNct-56 + LcNet-5x8
83.4 + 0.3
83.1 = 0.2
84.9 = 0.1
85.6 1.1 0.1
87.1 + 0.1
93.2
ResNet-110 -> LeNet-5x8
81.7
81.9 0.5
86.5 0.1
1 87.1 1 0.2
93.9
ResNet-110- >> LeNet-5x8
83.2 1 0.4
83.2 1 0.1
85.0 1 0.3
85.6 1.11
93.9
ResNet- 110 + ResNet-20
91.4 0.2
91.4 0.1
92.8 0.0
92.2
93.1 = 0.1
93.9
ResiNet 1 10 -> ResNet-20
90.9 1 0.1
90.9 1 0.2
91.6 1 0.2
91.2 1: 0.1
92.1 1 0.2
93.9
Adjusted supervision
Adjusted supervision complexilyy target
complexity"
-3
lebek:
labes randm bbbls
random bbels
offinee teacher
offine teacher online teacher
onine teacher
50
100
150
200
250
50
100
150
200
250
Epochs
Epochs
Figure 4: Adjusted supervision complexities* of various targets with respect to a LeNet-5x8 network at different stages of its training. The experimental setup of the left and right plots matches that of Fig. Ic and Fig. 2a respectively.
CIFAR-10 results. Table 5 presents the comparison of standard training, offline distillation, and online distillation on CIFAR-IO. We see that the results are qualitatively similar CIFAR-100 results.
Comparison of supervision complexities. In the main text, we have introduced the notion of adjusted supervision complexity, which for a given neural network ((x with NTK k and set of labeled examples {(X;, Y.)) X.)) defined as:
1
V Y
f(X1mm)) Tr (K).
(46)
As discussed earlier, the subtraction of initial predictions is the appropriate way measure com- plexity given the form of the optimization problem (9). Nevertheless, it is meaningful to consider the following quantity as well:
K- (K),,
(47)
in order to measure "alignment" targets Y with the NTK We call this quantity adjusted supervision complexity*, We compare the adjusted supervision complexitie** of random labels, dataset labels, and predictions of an offline and online ResNet-56 teacher predictions with respect various checkpoints of the LeNet-5x8 network. The results presented in Fig. 4 are remarkably similar to the results with adjusted supervision complexity (Fig. ic and Fig. 2a). We therefore, focus only on adjusted supervision complexity of (46) when comparing various targets. The only other experiment where we compute adjusted supervision complexities* (i.e., without subtracting the current predictions from labels) presented Fig. 7, where the goal is to demonstrate that training labels become aligned with the training NTK matrix over the course of training.
Fig. 5 presents the comparison adjusted supervision complexities, but with respect to a ResNet-20 network, instead of LeNet-5x8 network. Again, we see that in the early epochs dataset labels and offline teacher predictions are almost as complex as random labels. Unlike the case of the LeNet- 5x8 network, random labels, dataset labels, and offline teacher predictions do not exhibit U-shaped behavior. As for the LeNet-5x8 network, the shape these curves is in agreement with the behavior of the condition number of the NTK (Fig. 6). Importantly, still observe that the complexity of
19

---

Published as a conference paper at ICLR 2023
Adjusted supervision complexity over norm
labes
lbbes
Adjusted supervision
bbsts
10a
offiien
complexity
201
10*
10"
50
100
150
200
250
50
100
150
200
250
Epochs
Epochs
Figure 5: Adjusted supervision complexities of various targets with respect to a ResNer-20 network different stages of its training. Besides the network choice, the experimental setup of the left and right plots matches that of Fig. 1c and Fig. 2a respectively. Note that the y-axes are logarithmic scale.
10a
NTK condition number
10a
NTK condition number
10a
107
10f
10f
10a
10a
50
100
150
200
250
100
150
200
250
Epochs
Epochs
(a) LeNet-5x8 student
(b) ResNet-20 student
Figure 6: Condition number of the NTK matrix of a LeNet5x8 (a) and ResNet-20 (b) students trained
with MSE loss on binary CIFAR-100. The NTK matrices are computed on 2 test examples.
the online teacher predictions is significantly smaller compared to the other targets, when account for the norm predictions.
The effect of frequency of teacher checkpoints. As mentioned earlier, throughout this paper we used one teacher checkpoint per epoch. While this served our goal of establishing efficacy of online distillation, this choice is prohibitive for large teacher networks. To understand the effect of the frequency of teacher checkpoints, we conduct an experiment on CIFAR-100 with ResNet-56 and LeNet-5x8 student with varying frequency of teacher checkpoints. In particular, checkpointing the teacher once in every {1, 2, 4, 8, 16, 32, 64, 128} epochs. The results presented in Fig. 8 show that reducing the teacher checkpointing frequency once in 16 epochs results in only a minor performance drop for online distillation with 4.
consider
On label supervision in KD. So far in all distillation methods dataset labels were not used as an additional source of supervision for students. However, in practice it is common to train student with a convex combination knowledge distillation and standard losses: (1 Lce + a Cad. To verify that the choice of a 1 does not produce unique conclusions regarding efficacy of online distillation, we do experiments on CIFAR- with varying values of a. The results presented in Table 6 confirm our main conclusions online distillation. Furthermore, observe that picking a = does not result in significant degradation of student performance.
The effect of To confirm that main conclusions regarding online distillation do not depend on the temperature value, we present additional experiments on CIFAR- 100 with 7 = in Table 7.
NTK similarity. Figures and 10 presents additional evidence that (a) training NTK similarity of the final student and the teacher is correlated with the final student test accuracy; and (b) that online distillation manages transfer teacher NTK better.
20

---

Published as a conference paper at ICLR 2023
Adjusted supervision
Adjusted supervisiin
10a
complexity"
complexity"
10
10a
50
100
150
200
250
50
100
150
200
250
Epochs
Epochs
(a) LeNet-5x8 student
(b) ResNet-20 student
Figure 7: Adjusted supervision complexity" of dataset labels measured on subset of 2 training examples of binary CIFAR-I00. Complexities are measured with respect to either LeNet-5x8 (on the left) or ResNet-20 (on the right) models trained with MSE loss and without knowledge distillation. Note that the plot on the right is in logarithmic scale.
Teacher update period in epochs
Online KD
65
1
Test accuracy
(the default value)
61.9 0.2
66.1 0.4
60
6.4
66.0 0.3
61.4
6
6.3
65.4
55
Online KD t=1
0.6
65.4 0.0
Online KD r 4
0.0
64.1 +.4
55.5 +
1
16 32 64 128 Teacher update period epochs
2
128
51.4
0.1
Figure 8: Online KD results for LeNet-5x8 student on CIFAR-100 with varying frequency of ResNet-56 teacher checkpoints.
Table 6: Knowledge distillation results on CIFAR-100 with varying loss mixture coefficient a.
Setting
a
KD
Offline KD
Online KD
Teacher
1
=
7
T 4
0.2
+
57.6
0.2
54.3
1
0.4
48.9 + 0.3
58.9
1 0.4
56.7
0.5
62.5 1 0.2
ResNet-56 +
0.6
47.3 1 0.6
49.4 + 0.5
59.7
0.0
0.0
6..1
65.3 0.2
72.0
LeNet-5x8
0.8
49.8 = 0.1
60.10..11
6.1
6.29
1.0
50.1 = 0.4
0.2
6.2
6..1
0.2
67.9 + 0.3
70.3 0.3
0.3
0.1
0.4
=
0.2
6.27
7.24
ResNet-56 +
0.6
67.7 + 0.5
68.1 = 0.3
0.1
6.66
11.5022
72.0
ResNet-20
0.8
68.3 = 0.2
71.4
0.3
71.1
1.0
68.2 - 0.3
71.6
0.3
0.3
Table 7: Results on CIFAR-100.
Setting
No KD
Offfine KD
Online KD
Teacher
==1
= 2
7=1
7 = 2
ResNet-56 + LeNet-5x8
47.3 + 0.6
50.1 0.4
55.2 + 0.1
61.9 1.9-02 0.2
64.7 1 0.2
72.0
ResNet-56 + ResNet-20
67.7 + 0.5
68.2 2 0.3
70.4 0.3
69.6 0.3
70.8 0.3 0.3
72.0
ResNet- 110 LeNet-5x8
47.2 + 0.5
48.6 0.8
54.0
63.9 6.2
73.4
ResNet- I 10 ResNet-20
67.8 + 0.3
67.8 0.2
69.3 + 0.2
0.3
70.5 0.3
73.4
21

---

Published as a conference paper at ICLR 2023
E EXPANDED DISCUSSION ON RELATED WORK
The key contributions of this work are the demonstration of the role of supervision complexity in student generalization, and the establishment of online knowledge distillation theoretically grounded and effective method. Both supervision complexity and online distillation have a number of relevant precedents in the literature that are worth comment.
Transferring knowledge beyond logits. In the seminal works of Buciluã et al. (2006); Hinton et al. (2015) transferred "knowledge" is in the form of output probabilliiies. Later works suggest other notions of "knowledge" and other ways of transferring knowledge (Gou et al., 2021). These include activations of intermediate layers (Romero et al., 2015), attention maps (Zagoruyko & Komodakis, 2017), classifier head parameters (Chen et al., 2022), and various notions of example similarity (Pas- salis & Tefas, 2018; Park et al., 2019; Tung & Mori, 2019; Tian et al., 2020; He & Ozay, 2021). Transferring teacher NTK matrix belongs to this latter category of methods. Zhang et al. (2022) propose to transfer a low-rank approximation of a feature map corresponding the teacher NTK.
Non-static teachers. Some works on KD consider non-static teachers. In order to bridge teacher- student capacity gap. Mirzadeh et al. (2020) propose to perform a few rounds of distillation with teachers of increasing capacity. In deep mutual learning (Zhang et al., 2018 8; Chen et al., 2020), codistillation (Anil et al., 2018), and collaborative learning (Guo et al., 2020), multiple students are trained simultancously, distilling from each other or from an ensemble. In Zhou al. (2018) and Shi et al. (2021), the teacher and the student are trained together. In the former they have a common architecture trunk, while in the latter the teacher is penalized keep its predictions close to the student's 's predictions. The closest method to the online distillation method of this work is route constrained optimization (Jin et al., 2019), where few teacher checkpoints are selected for multi-round distillation. Rezagholizadeh et al. (2022) employ a similar procedure but with an annealed temperature that decreases linearly with training time, followed by a phase of training with dataset labels only. The idea of distilling from checkpoints also appears in Yang et al. (2019), where a network is trained with a cosine learning rate schedule, simultancously distilling from the checkpoint of the previous learning rate cycle.
Fundamental understanding of distillation. The effects of temperature, teacher-studen capacity gap, optimization time, data augmentations, and other training details is non-trivial (Cho & Hariharan, 2019; Beyer et al., 2022; Stanton et al., 2021). It has been hypothesized and shown to some extent that teacher soft predictions capture class similarities, which is beneficial for the student (Hinton et al., 2015; Furlanello et al., 2018; Tang et al., 2020). Yuan et al. (2020) demonstrate that this softness of teacher predictions also has a regularization effect, similar to label smoothing. Menon et al. (2021) argue that teacher predictions are sometimes closer to the Bayes classifier than the hard labels of the dataset, reducing the variance of the training objective. The vanilla knowledge distillation loss also introduces some optimization biases. Mobahi et al. (2020) prove that for kernel methods with RKHS norm regularization, self-distillation increases regularization strength, resulting in smaller norm RKHS norm solutions.
Phuong & Lampert (2019) prove that in a self-distillation setting, deep linear networks trained with gradient flow converge to the projection of teacher parameters into the data span, effectively recov- ering teacher parameters when the number of training points is large than the number of parameters. They derive bound of the transfer risk that depends on the distribution of the acute angle between teacher parameters and data points. This is in spirit related to supervision complexity as it measures an "alignment" between the distillation objective and data Ji & Zhu (2020) extend this results to linearized neural networks, showing that the quantity A, K A.. where A, is the logit change dur- ing training, plays key role in estimating the bound. The resulting bound is qualitatively different compared to ours, and the AJ K-'A, 'A becomes ill-defined for hard labels.
Supervision complexity. The key quantity our work is YT K-11. Cristianini et al. (2001) in- troduced a related quantity Y KY called kernel-target alignment and derived a gemeralization bound with it for expected Parzen window classifiers. As an easy-to-compute proxy to supervi- sion complexity, Deshpande et al. (2021) use tarnelttageet alignment for model selection in transfer learning. Ortiz-Jiménez et al. (2021) demonstrate that when NTK- -ttrgett alignment is high, learning is faster and generalizes better. Arora et al. (2019) prove a generalization bound for overparameter- ized two-layer neural networks with NTK parameterization trained with gradient flow. Their bound
22

---

Published as a conference paper at ICLR 2023
is approximately / TY(T (K=))-1//// /V where k is the expected NTK matrix at random initial- generalization of this result for all kernel methods,
ization. Our bound of Thm. including linearized neural networks of any depth and sufficient width, with the only difference of using the empirical NTK matrix. Belkin et al. (2018) warns that bounds based on RKHS complexity of the learned function can fail to explain the good generalization capabilities of kernel methods in presence of label noise.
be
Future work. There are several potential directions for future work. Adaptive temperature scaling online distillation, where the teacher predictions are smoothened so as to ensure low target com- plexity, is one such direction. Another avenue is to explore alternative ways to smoothen teacher prediction besides temperature scaling: c.g., can one perform sample-dependent scaling? There is large potential for improving online KD by making more informed choices for the frequency and positions of teacher checkpoints, and controlling how much the student is trained in between teacher updates. Finally, while demonstrated that online distillation results in better alignment with the teacher's NTK matrix, understanding why this happens is an open and interesting problem.
23

---

Published as a conference paper at ICLR 2023
correlation: -0.74
correlation:
0.80
0.55
KD
x
0.90
offline KD
X
Train NTK similarity
0.50
online KD
0.88
Train fidelity
0.45
0.86
0.40
0.84
0.35
0.30
0.82
No KD
offline KD
0.25
0.80
online KD
x
0.20
#4
68
69
71
82
84
86
88
Test accuracy
Test accuracy
(a) CIFAR-100, ResNet-20 student, ResNet-
(b) CIFAR-10. 10, LeNet-5x8 student, R6sNet-56 teacher
110 teacher
correlation: 0.24
correlation: 0.90
1.000
KD
0.78
offline KD
0.998
Train NTK similarity
0.996
0.76
Train fidelity
0.994
0.74
0.992
0.72
0.990
0.988
No KD
0.70
x
offline KD
0.986
online KD
0.68
82
84
86
88
91.5
92.0
92.5
93.0
Test accuracy
Test accuracy
(c) CIFAR-10, LeNet-5x8 student, ResNet-56
(d) CIFAR-10, ResNet-20 student, ResNet- teacher
teacher
correlation: 0.71
correlation: -0.57
0.994
0.65
0.992
Train NTK similarity
Train fidelity
0.990
0.60
0.988
0.55
0.986
Woog
0.984
0.50
No
offline
0.982
offline
anline
0.45
0.980
72
76
72
74 Test accuracy
Test accuracy
(e) Binary CIFAR-100, LeNet-5x8 student, ResNet-56 teacher
(f) Binary CIFAR-100, LeNet-5x8 student, ResNet-56 teacher
Figure 9: Relationship between test accuracy, train NTK similarity, and train fidelity for various teacher, student, and dataset configurations.
24

---

Published as a conference paper at ICLR 2023
correlation: 0.40
correlation: -0.38
0.38
No KD
0.95
No
0.36
offline KD
offline KD
Train NTK similarity
online KD
online KD
0.34
0.90
Train fidelity
0.32
0.85
x
0.30
0.28
0.80
xx
0.26
0.75
0.24
59
60
61
62
60
61
62
Test accuracy
Test accuracy
(a) Tiny ImageNet, MobileNet- V3-35 student, Mo3- teacher
(b) Tiny ImageNet, MobileNet- V3-35 student, V3-112 teacher
correlation: 0.98
correlation: -0.42
No
1.00
0.55
offline KD
Train NTK similarity
0.50
0.98
Train fidelity
0.45
0.96
0.40
0.35
0.94
No KD
offline KD
online KD
0.30
50
55
60
65
50
55
60
65
Test accuracy
Test accuracy
(c) Tiny ImageNet, VGG-16 student, ResNet-
(d) Tiny ImageNet, VGG-16 student, ResNet- teacher
101 teacher
correlation: 0.99
correlation: -0.58
1.000
0.55
No KD
offline KD
Train NTK similarity
online KD
0.50
0.999
Train fidelity
0.45
0.998
0.40
0.997
No
0.35
offline
50
60
50
55
60
65
Test accuracy
Test accuracy
(e) Tiny ImageNet, VGG-16 student, MobileNet-V3-125 teacher
(f) Tiny ImageNet, VGG-16 student, MobileNet-v3-11 teacher
Figure 10: Relationship between test accuracy, train NTK similarity, and train fidelity for various teacher, student, and dataset configurations.
25


Reviews:
[{"review_id": "vXx48Ll5Ib", "reviewer": "Reviewer_jR2a", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes to view knowledge distillation from the Supervision Complexity angle, or how easy/hard is it for the student model to learn the targets. One reason why distillation has been thought to be helpful is that the soft labels additional provide information about class similarities which the one-hot labels do not provide. However, distillation has been also shown to be useful for binary classification problems where there is a limited class similarity information. The paper thus looks at other alternatives to explaining distillation, especially the reasoning behind  using soft-labels from teacher and that of using temperature smoothing. They come up with a notion of Supervision Complexity which intuitively determines how easy it is for the teacher to learn from the targets.  They theoretically show that for kernel based binary classifiers, the generalization is bounded by Supervision Complexity and then later extend it to multi-class kernel based classifiers. The Supervision complexity can be reduced by reducing the scale of the targets or by aligning the targets with the eigenvectors of the kernel. Then they finally extend their analysis for neural networks by treating them as corresponding linearized neural networks.\n\nFor distillation, the theoretical analysis reveals that for a binary classification setting, the student risk is bounded by the sum of Supervision Complexity and the Student's margin loss with teacher targets. Thus, making the targets softer in distillation reduces Supervision Complexity and correspondingly helps in better generalization. However, increasing the temperature a lot (and thus making targets softer) would also affect the margin loss and thus the temperature smoothing for distillation needs to happen carefully. \n\nThe authors also show that in the initial stages of training, the Supervision Complexity from soft-targets can be same as that of one-hot labels particularly if the gap between student and teacher is high. Thus to remedy this the authors propose (Online distillation)gradually increasing the complexity of the teacher for distillation, whereby the teacher checkpoints used for distillation are gradually increased. Empirically it is shown that Online distillation works better than offline distillation for several datasets. \n\nFinally the paper mentions that the test accuracy of the student is highly correlated with the similarity between the student and the teacher NTK matrices (computed over a batch of data), and show that the similarity is indeed higher for Online distillation as compared to Offline distillation.", "summary_of_the_review": "While I like the general direction pursued in the paper around connecting knowledge distillation with Supervision complexity, I have some concerns with the experimental settings which I have mentioned in the weakness section. I am leaning towards weak accept for now, but will update my ratings if my concerns are addressed.", "strength_and_weaknesses": "Strengths - \n\n1. The paper presents a strong theoretical understanding behind the role of knowledge distillation particularly the effect of using smoother labels and temperature smoothing for the teacher. \n\n2. The proposed Online distillation achieves strong empirical improvements over the baseline Offline distillation.\n\nWeakness - \n\n1. One thing which is unclear is for the experiments on distillation do the authors also train with the dataset labels or only train with the teacher targets? If it is the latter, can authors also show results comparing Online/Offline distillation when the dataset labels are also used for training. I can see that the dataset labels was excluded for the theoretical analysis, but for a fair comparison with the way distillation is used generally the dataset labels should be included in the training of the student model.\n\n2. While in Figure 2c) the paper compares the Supervision Complexity with  an average teacher, showing that the Supervision Complexity of  Average teacher is higher than that of Online teacher, I could not see any comparison between Online distillation and distillation done with an Average teacher. If the Supervision complexity is higher, does it mean that the Average teacher will perform better than the Online distillation?\n\n3. For the results showing high correlation between NTK similarity and the test accuracy, can the authors do further experiments to validate this. For instance, does a weaker student model (LeNet) have better similarity than a stronger student (ResNet-20)? Or does the student model trained with augmentations have better NTK similarity with the teacher than the student model trained without augmentations.\n\n4. In table 1, Online distilation from ResNet-56 to ResNet-20 performs worse than Offline distillation. Can the authors also show the student and teacher trajectories for this case (Figure 1) to better understand what is happening for this case?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "uIyXmfu5G-U", "reviewer": "Reviewer_AC7X", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a knowledge distillation (KD) framework that leverages supervision complexity to measure the alignment between teacher-provided supervision and the student’s neural tangent kernel. It first shows how supervision complexity is defined and measured for kernel-based classifiers, which is then extended to neural classifiers. Then, an online KD algorithm is proposed based on the analysis. Experimental results on real datasets show that the proposed techniques are effective. ", "summary_of_the_review": "The paper makes theoretical contributions by offering new insights into the learning process of KD including the role of temperature scaling and early-stopping, how to teach a weak student, and the effectiveness of online KD. It has the potential to lead to new studies with improved KD learning process and outcomes. \n\n=== Update after rebuttal ==\n\nThank you for the response. There are no further questions.", "strength_and_weaknesses": "Strengths:\n1. The paper offers new theoretical insights on the learning process of KD including the role of temperature scaling and early-stopping, how to teach a weak student, and the effectiveness of online KD. \n\n2. An online KD algorithm is proposed based on the analysis which is shown to be effective on real datasets.   \n\nWeakness:\n1. The theoretical analysis section is dense without examples or discussions on the intuitive ideas of the proposal. \n\n2. The experimental results are not very strong. The proposed technique shows marginal improvements on many cases in the overall result tables (Tables 1 to 3). ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Cc1jo6DLYP", "reviewer": "Reviewer_oX8Z", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work studies the generalization characteristics of Knowledge-Distillation (KD) by proposing a new theoretical framework that leverages supervision complexity: a measure of the alignment between teacher supervision and the student's neural tangent kernel. It provides a justification for the temperature scaling and early stopping often used in the KD literature for superior performance. Further, it proposes Online Distillation, where at each epoch i in training, student uses the teacher model obtained at epoch i. Thus it progressively increases the complexity of teacher supervision, where the final epoch teacher is the supervision used in the vanilla KD in all training epochs. Finally, the online KD procedure and the theoretical findings are validated on benchmark datasets.", "summary_of_the_review": "This paper introduces  supervision complexity to help explain student generalization behavior during knowledge distiilation. It provides insights into temperature scaling and early stopping, used frequently to obtain better performing student models. Novelty of the supervision complexity is somewhat lacking as there have been attempts to explain similar behavior (NTK literature has a similar term). Main bottleneck in the proposed online KD scheme is the expensive storage of intermediate teacher checkpoints which may become prohibitive once you go beyond the toy setups of CIFAR/Tiny-Imagenet problems. In addition, even the distillation gains shown for these datasets are not that significant.", "strength_and_weaknesses": "\nStrengths:\n- Generalization bound (Prop.5) on the student risk in terms of three quantities : (a) teacher  risk, (b) students empirical margin w.r.t. teacher predictions, and (c) complexity of the teacher predictions.\n- Proposed notion of supervision complexity $Y^\\top K^{-1} Y$, up to a certain extent, explains the KD behavior w.r.t. temperature scaling and early stopping\n\nWeaknesses:\n- Online KD is storage wise expensive as it stores intermediate teacher checkpoints\n- Empirically, at least in moderate capacity gap between teacher-student, it does not seem to be achieving much gains ( see Table~1, student=ResNet-20 )\n\n\nQuestions for Authors:\n\n(1) Why do some of the experiments use temperatue = 1 and 2.. while others use temperature=1 and 4?\n\n(2) Online KD seems to store all checkpoints of a teacher. This is infeasible in many real-world applications. Typically you will have access to only the final few teacher checkpoints. How do you explain this overhead and its practicality?\n\n(3) Appendix notes that you consider one teacher checkpoint per epoch. This does not seem very practical. Have you tried any ablations where relatively fewer teacher checkpoints were used. Alternatively, you could train a teacher in parallel to the student (although it is much more computationally expensive to train a large teacher), and avoid the storage overhead.\n\n(4) In Table.3, MSE loss seems to outperform the CE loss. Why is the same loss not used in the Table.1 or 2? Let me know if this exists somewhere in the supplementary.\n\n(5) Why are you using different teachers and students in CIFAR-100, Tiny-Imagenet? why not use the widely used teacher-student combinations?\n\n(6) What is the value of alpha in the KD formulation? This hyper-parameter has not been mentioned anywhere that trades off the CE and KL-divergence loss.\n\n(7) How do you explain the gains in binary classification CIFAR100 experiments, if not for the so called \"dark knowledge\"?\n\n(8) Prop.5 explains the effect of temperature on the KD generalization. How does this explain the effect of early stopping? Similarly, how does this explain the effect of teaching a weak student?\n\n(9) Why doesn't the NTK result by Arora et al (2019) directly give you the supervision complexity term? It has the form $Y^\\top (K^{\\inf})^{-1} Y$.\n\n\n(10) Why are you using different teachers and students in CIFAR-100, Tiny-Imagenet? why not use the widely used teacher-student combinations (see Sim-KD (Knowledge Distillation with the Reused Teacher Classifier https://github.com/DefangChen/SimKD) and references therein )?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster