Understanding the Gains from Repeated Self-Distillation
Authors: Divyansh Pareek
Simon Shaolei Du
Sewoong Oh
Venue: NeurIPS 2024 poster (2024)
Keywords: Self-Distillation Theory
Linear Regression
Primary area: learning_theory
TL;DR: Using linear regression to characterize how large the performance gain can be from repeated applications of self-distillation

Abstract: Self-Distillation is a special type of knowledge distillation where the student model has the same architecture as the teacher model. Despite using the same architecture and the same training data, self-distillation has been empirically observed to improve performance, especially when applied repeatedly. For such a process, there is a fundamental question of interest: How much gain is possible by applying multiple steps of self-distillation? To investigate this relative gain, we propose using the simple but canonical task of linear regression. Our analysis shows that the excess risk achieved by multi-step self-distillation can significantly improve upon a single step of self-distillation, reducing the excess risk by a factor of $d$, where $d$ is the input dimension. Empirical results on regression tasks from the UCI repository show a reduction in the learnt model's risk (MSE) by up to $47$%.

Understanding the Gains from Repeated Self-Distillation
Divyansh Pareek Simon S. Du
Sewoong Oh
Paul G. Allen School of Computer Science and Engineering University of Washington, Seattle, WA {dpareek, ssdu, sewoong wwwwoogg@ccc.wassnntooo.omo
Abstract
Self-Distillation is a special type of knowledge distillation where the student model has the same architecture as the teacher model. Despite using the same architecture and the same training data, self-distillation has been empirically observed to improve performance, especially when applied repeatedly. For such a process, there is a fundamental question of interest: How much gain is possible by applying multiple steps of self-distillation? To investigate this relative gain, propose studying the simple but canonical task of linear regression. Our analysis shows that the excess risk achieved by multi-step self-distillation can significantly improve upon a single step of self-distillation, reducing the excess risk by a factor as large d, where d is the input dimension. Empirical results regression tasks from the UCI repository show a reduction in the learnt model's risk (MSE) by up to 47%.
Introduction
Knowledge distillation [12] was initially proposed as a way to transfer the knowledge learnt by larger teacher model to a smaller student model, which can then be deployed in limited resource settings. The process is as follows: Train teacher (T) model using ground-truth labels, then use its predictions to supervise the training of student (S) model via combined per-sample loss,
{ L (ūr, (0)) + (1 E) (V. (s(ss()))
(1)
where l denotes the loss function, is the ground-truth label, ûr denotes the teacher's prediction, and (f) denotes the student's prediction, parameterized by the learnable A. The extra hyperparameter g is called the imitation parameter [25], generally restricted to & E [0. 1). It gives additional freedom to the student to balance importance between labels and teacher's 's predictions. The student trained via this distillation objective (i.e., utilizing the teacher's 's predictions through & f 0) has been widely observed to generalize better than when trained only on the labels (i.e.. E = 0). This gain has been attributed to 'dark knowledge' that is (i) impossible to be directly extracted from the training data by the small model, but (1i) easily learnt by the large model and transferred to the small model.
Challenging this interpretation, Li et al. [20] and Furlanello et al. [10] empirically observed perfor- mance gains through distillation even when the teacher and student are same-sized models. One can set T' and S to have the same architecture, and S trained with the objective in Eq. (1) outperforms T. This is referred to as Born-Again Networks (BANs) or Self-Distillation (SD). Furthermore, repeatedly applying self-distillation architecture provides additional gains on benchmark datasets and architectures [10, 36, 44]. At each step, the student from the previous step acts the teacher used train new student model under the self-distillation loss of Eq. (1). For such multi- step self- distiiisill,a,onn there is a fundamental question of interest: How much more gain can we get by repeatedly applying self-distillation?
the same training data with student model having the same
Recently, Das and Sanghavi [9] provided theoretical understanding of the original one-step self- distillation. For the canonical task of fixed design linear regression, considering the standard ridge
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

estimator as both the teacher and student model, [9] showed that there is indeed regime of problem instances in which the optimal student (i.e.. with optimally tuned ridge parameter À and imitation parameter 5) can provably achieve strictly lower test error than the optimal teacher (i.e. with optimally tuned A). However, the amount of this gain has not been characterized in closed form, and can only be numerically evaluated for given problem instance. Inspired by this work, we aim to study the performance gains from multi-step self-distillation under linear regression.
Contributions. We summarize contributions below.
Under the fixed design linear regression defined in Section 3.1, we show that the optimal multi- step self-distilled model (i.c., each value each step optimized for the validation accuracy of the final multi-step self-distiledd model) can achieve test error that is a factor of d smaller than the optimal one-step self-distillation (Theorem 1), under certain assumptions on the problem parameters (Assumption 2). Here, d is the dimension of the input. Our analysis in Theorem 1 suggests that the sequence of Ç parameters provides additional freedom that can control the spectrum of eigenvalues of the linear estimator. Optimally choosing these & parameters can significantly reduce the variance of the estimator, leading to factor of (up to) difference the overall test errors of multi-step SD compared to 1-step SD. We note that Das and Sanghavi [9] also observed a bias-varianc tradeoff associated with the & parameter for 1 1sseep SD compared to the ridge, which was the reason behind 1-step SD strictly outperforming the ridge.
We demonstrate the necessity of the main assumption (Assumption 2) both theoretically (Theo- rems 2 and 3) and numerically (Figure 3). Further, we provide a lower bound for the test error that any repeated SD can achieve, and show that only steps of SD (with optimally chosen & at each step) are sufficient achieve this, when the input data matrix has rank (Theorem 4).
By capturing the functional form of the test error in & (Theorem 5), we also show a method to practically select the & parameters for real-world regression tasks. Section 5, we empirically show that this theoretical insight leads to selecting effective & values, which can indeed achieve a lower test error on real-world regression tasks.
2 Related Work
Knowledge distillation and self-distillation. Hinton et al. [12], Ba and Caruana [3] proposed knowledge distillation to transfer knowledge learnt by large teacher models into smaller student models without any substantial performance drop (e.g., [30, 31, 14, 8, 33, 24, 32] and surveys in
[11, 13). Distillation also provides interpretability [23], robustness to adversarial examples [28], and defense against backdoor attacks [39, 21, 35]. although stronger backdoor attacks have been proposed that bypass distillation defense [17]. Perhaps surprisingly, empirical observations show that performance improves when teacher model is distilled into student model with the same architecture on the same training data (self-distillation). Performance gains with one-step self- distillation of the form Eq. (1) were first demonstrated by Li et al. [20] for AlexNet on YFCC100M. Further gains can be achieved by repeating self self-distillation, as shown for the DenseNet architecture family on CIFAR1O and CIFARI00 [10, Table 2]. To empirically explain such gains, Zhang and Sabuncu [44] measured prediction uncertainty on the same multi-step experiments and offered an interpretation that soft labels capture sample-level uncertainties. Yang al. [36] also reproduced the same experiments and explained the gains as knowledge refinement on the class similarities. We will analytically study the gains that can be achieved with such repeated self-distillation.
Many variations of self deff-distillation have also been proposed. Snapshot Distillation [37] tries to treat previous checkpoints (snapshots) of the same model as the teacher. Zhang et al. [43] employ group of collaborative students with no teacher. Zhang et al. [42, 41] use it for model self-improvement, and DINO [7) adopts self-distillation for self-supervised learning. Knowledge distillation is also popular for transfer learning, where the student model is trained
different dataset than the teacher model
[38, 40, 1]. which is not a setting we address. With the recent scaling of data, [45], [22] are relevant works using teacher model for either label editing or data reweighing.
Theory of distillation and self-distillation. Theoretical understanding of distillation started with Phuong and Lampert [29] studying linear student networks. Mobahi et al. [27] studied self-distillation theoretically in the restricted setting of { (i.e. only teacher supervision, no ground-truth labels), showing that this setting, the SD process acts as regularizer, with a few steps of SD helping, but further steps hurting model performance. We study the setting where is not restricted to 1,
2

---

and show a different conclusion. In particular, we observe that more steps of SD always provide an improvement, if the Ç parameters are chosen optimally. Allen-Zhu and Li [2] analyzed stylized setting, where different view of the data is learned by different models, and show how ensemble methods can combine the views, achieving improved test accuracy. This framework used to show how self-distillation can also improve model accuracy by implicitly performing ensembling. Menon et al. [26] theoretically studied distillation in the classification setting, and also observed a bias-variancs tradeoff underlying teacher supervision. Das and Sanghavi [9] theoretically studied one-step self-distillation for fixed design linear regression and binary classification, and showed that the student can provably achieve lower test error than the teacher. We take inspiration from them and study the multi-step SD to characterize this performance gain, showing that the multi-step SD can outperform one-step SD by large factor. Borup and Andersen [4] also studied multi-stey step SD and obtained an atalytical form for the k-step SD similar to ours [4, Theorem 4.1]. The crucial difference is the freedom of the & parameters heing different each step of self-distillation. Whereas [4, Lemma 4.2 and Theorem 4.3] assume the { values at each step are equal (similar to [27]). concluding that after a point, more steps of SD will result in a poorer performing model (similar [27]); our main result (Theorem 1) is different as it says that subsequent steps of SD strictly provide more freedom, and that the best multi-step SD can outperform the best 1-step SD by an Q()) factor. Similar to us, Jeong and Chung [16] also take inspiration from [9]. [16] however aim to provide understanding of multi-step self- distilllatio in the multi-class classification setting.
3 Problem formulation and background on self-distillation
Focusing the simple but canonical task of linear regression, we investigate the performance gain from applying repeated self- eeff-istillationn
3.1 Linear regression
For the observed response Y E: IR and the covariate X e Rd, the following assumption is standard in linear regression, e.g., [9].
Assumption 1. There exist 6** E Rd and y > O such that (i) [[ = (0r, (ii) Var = 7² for all X E Rdd; and (iit) (Y - X L X, i.e. the label noise is independent of X.
The training set of size n is denoted by X E Rdxn the collection of covariates, and Y E R", the responses; Y X 8* + 77. with n satisfying E[n) = O, EE [mm ]= z The problem instance is defined by its parameters (X, 1X,0",7 7,), treating X = [X X2, ................................ .x,] as fixed but Y as random. The training set (X, Y) is one occurrence of the random noise v E R In this fixed design setup, the
excess risk of an estimator 0 is defined using the standard Σn -nomm ||ale, = =1 2/12. as
ExcessRisk(0) := E,, [10 1
(2)
where == (X is the covariance matrix, and the expectation is over the randomness in n7- Measuring the error in the Ê,,-norm ensures that the signal-to- to-se ratio uniform all directions. The popular ridge estimator serves as a baseline, using single hyperparameter À >>> 0:
0(2) = arg min (/ - X TTo + (1011) = (xx + ALa) XY BER"
We use Ω2 XX + AL throughout. We consider only X > O, but surprisingly, Kobak et al. [19] showed that the optimal penalty X (one with the lowest risk) can indeed be negative. However we will largely work in the non-overparameeterized case (n d), where X= > 0 holds.
3.2 Self-distillation
Applying the self- self-distillation loss in Eq. (1) to linear regression with hyperparameters À and &.
BERd Ó(A, E) = arg min (5 ||X 0(A)= x T0 + (1 5) Y x 011 + +111012)
(4)
(x daa)) x xx.x (()) + (1 Y
(5)
label
(1-E) La + Ω XXX
(6)
Pre conditioner: function of (X.E)
Ridge ((A)
3

---

where E IR is not restricted to the conventional [o, 1] interval. This additional freedom is meaningful
since it can result strictly better solution, as noted by Das and Sanghavi [9] both theoretically
(Remark 3.6) and empirically (Table 1). It is worth noting that the optimization problem in eq. (4) remains convex for any 5 IR, since its hessian evaluates 2-2XX +(1-))-2XX -2X 2XX 2
On the other hand, the teacher and student use the same ridge penalty for simplicity.
We call this estimator 1-step self-distillatiin. This can be interpreted as (i) assigning new labels that combine the ground-truth labels with the teacher's predictions, or (ii) pre-multiplying the usual ridge estimator with a pre-conditioner. Note that & = 0 recovers ridge. Das and Sanghavi [9, Theorem 3.8] show that under certain condition, 1-step olf-distillation strictly dominates ridge, i.e.
min En [10(2, 0' min En [1Ō(A) 01
X20.EER
where the risk is measured in the non-standard Euclidean norm. The same striet inequality can be shown under the standard -nomn under slightly modified condition stated in Proposition B.I. This naturally leads to a fundamental question: How much more gain can we get by repeatedly applying self- distillatt????n
T
S
I I-step self-distillation
S1
$2
Sk
So
S1
S2
Sx
k-step self-distillation
Figure 1: The standard 1-step self-distillation defined in Eq. (1) with parameter and k-step self-
distillation that repeatedly applies Eq. (1) with parameter g(R) = [g(4) c(k) e(k) ,,.,, R
3.3 Repeated self-distillation
The standard repeated application of seff-distillation starts with the teacher model, T (which we also refer as the zeroth model, So), and applies self-distillatio sequentially for l steps. At each step i, Eq. (1) is applied with the (i 1)th model, S;-1 as the teacher, and the ith model, St as the student,
with imitation parameter {/ i.e., 0 arg ming {s(²) el (ūs 11 11 US, (0)) +
(k) ( ys. (0))
for i E [k]. The collection of parameters is denoted by g(k) [s(*) .2 (k) ..... (k) IR..
This repeated self-distillation has been studied, for example, theoretically in [27] and empirically in [10]. We aim to understand its gain under linear regression, where we prove that
0(),
(k))
+
(k) (S (xx'XXT)²
S '
(8)
ERA
Ridge ((2)
Pro-conditioner: ((X.E(k3)
The proof that repeated SD with E(()) E # results in Eq. (8) is provided in Appendix C.2. Here c(k)) E I denote the imitation parameters, A denotes the ridge coefficient for all the models, and g(() E R² is reparametrization of (RR) E R (details in Appendix C.2). We call this k-step self-distillation. Note the increasing flexibility in the pre-conditioner matrix. The increasing powers of S2 TXXT in the above expression are still numerically stable, since, for À 0, 52 'xx is PSD with all eigenvalues in [0, 1]. As an aside, one can also consider a version of SD where the tth model receives supervision from all Szz instead of just S;-1- Appendix C.1 shows that this version provides extra representational capacity over the repeated version presented above, when all entries of (()) are optimized as free parameters. Hence, the procedure in Figure I suffices for analysis.
with E(A) = (1 ((-)))
5 for each i E [k], and we let <(xt)
Main results for linear regression
The main object of our study theoretically demonstrate the gains from repeated self-distillation. Concretely, aim show that there can be significant multiplicative separation between the

---

excess risk achieved by r-step SD Deeff-Ditiillttion), where r' is the rank of the input X; compared to the ridge estimator, as well as the 1-step SD (Section 4.1). The necessity of the two main assumptions is shown in Section 4.2. The sufficiency of steps of SD is shown in Section 4.3. In Section 4.4, we provide an exact characterization of the excess risk achieved by k-step SD (for any k).
4.1 The r-step self-distillation significantly improves upon the 1-step self-distillation
We show the desired separation under the following assumption (and two more mild technical assumptions specified fully in Appendix E).
Assumption 2. Assume the following two conditions hold on the problem instance (X, 0 ,2))
1. No two non-zero singular values of X collide, i.e. 81 > 82 > ..... >> 8r > O, where {8,} 1- denote the non-zero singular values of the input data matrix X whose rank is denoted by r.
2. For a B E [0, 1). there exists index E [r]] such that u,) (1 (1- 3) 1|0 [?: where {u, 1dd denote the eigenvectors of XX U1 being the leading one.
Assumption 2 is needed to show that r-step SD achieves small excess risk in Eq. (9). The quantity 3 captures the similarity of the (unknown) 8* to the eigenbasis directions. The case of B = entails perfect alignment of (+ with one of u,. E [r]. As will see in the result in Theorem 1, the gains provided by multi-step SD are large when / is small. In general, both these conditions are somewhat necessary for the separation, as show in Theorems 2 and 3. We now state our main result. We show that under the above assumption, there exists a family of problem instances, (X, 0" >²), such that the excess risk achieved by r-step SD is a factor of r == rank(X) smaller than that of the ridge estimator and the 1-step SD.
Theorem 1. Under the fixed design linear regression in Assumption 1, there exists a family of problem instances satisfying Assumption 2 such that for any instance (X, 6 ??) in the family, holds that
72 1+ 3 110 10~1230
AEE 0, ( ER",
ExcessRisk (B(),
(9)
n
72
ExcessRisk (0(A,E) 2
0.99
r?2
Aト 4. RR
(1 - B)
and
(10)
211
n
YA 0, ExcessRisk (B(A)) 2 0.98
1 1- 3
2
r7
(11)
0.993
n
where r == ra) n is the number of samples, 0(,, ((r) and ((), {) are the r-step and 1-step SD estimators defined in Eqs. (8) and (4) respectively, and ((A) is the ridge estimator defined in Eq. (3).
This theorem captures a general result for the gains of multi-step SD. In particular, the special case of = (i.e. 0+ being completely aligned with one of the eigenvectors U E [r] presents an 2(r) multiplicative separation between the excess risk of r-step SD and {1, -step SD. We provide precise conditions and a proof Appendix F. Since each k-step SD includes (k- - step SD as a special case with the proper choice of ((k), the hyperparameter-tunee excess risk of repeated SD is monotonically non-increasing. However, it is perhaps unexpected that the multiplicative separation between r-step SD and 1-step SD can be as large as (( demonstrating the gains of repeated SD. Figure/ illustrates this Q(r) multiplicative separation on a synthetic family of problems. Note that ((d) separation can be achieved by choosing the problem instance to have rank r = d, at the cost of requiring many more steps of SD. This ((d) factor is the largest multiplicative separation possible with self-distillation as shown by the fundamental lower bound in Theorem for any pre-conditioning based approach.
In general, if B O || (akin to the inverse signal-to- to-eoise ratio), then there exists an Q(r)
multiplicative separation between r-step SD and (1, Osttep SD. In our particular construction of the problem instance for Theorem 1, the additional technical condition (i.e. Condition #2 in the detailed theorem statement in Appendix E) effectively translates this 3 = 0(1/).
Remark 4.1. SD significantly outperforms ridge by primarily reducing the variance. For the lower bound on ridge's 's excess risk, i.e., Eq. (11), we ignored the bias term and only used the variance term. The repeated SD (Eq. (9)) primarily reduces the variance to improve the excess risk over Eq. (11).
5

---

Sy/s, 1.25
S:/5, =//5
10
Relative Gain of ritep (denated A/8)
10
Relative Gain of nste (densted A/9)
9
7
6
6
5
5
4
4
3
3
2
1
3
10
3
6
9
r rank(X)
r rank(X)
Figure 2: On synthetic problem family with dimension 100, noise variance y 0.1, and 0" (agreement with Asmp. 2.2); we set the singular values of X with power law from 81 to 8, {0.8, 0.53 (left and right panels) and vary rank(X). Both plots show linear increase of the relative gain of r-step self-distillation in excess risk, i.e. the ratio 4/B where A minA>- Excess (0()) and B minxy0,g(re ExcessRisk( (fdisk(((A,,))) <(r))): demonstrating that ststep SD outperforms ridge by factor of Q(r), with the constant inside the P (i.e. slope of the line) changing with the effective condition number, 81/s..
4.2 Necessity of Assumption 2
In Figure 3, we empirically show on synthetic tasks how violating Assumption 2.1 or 2.2 leads to higher excess risks, even for the r-step SD (r in the example). This supports the necessity of both assumptions, which we analytically investigate in the following.
Necessity of Assumption 2.1 on X. We assume that the non-zero singular values of X are unique. This allows us tightly upper bound the excess risk achieved by r-step SD in Eq. (9) via Theorem We show in the following that some version of Assumption 2. is also necessary. For more detailed explanation of why we need Assumption 2.1, we refer the reader to Remark 4.2.
Theorem 2. Under the hypotheses of Theorem I except for Assumplion 2.1, if the singular values of X satisfy 81 Sp where r = (ank(X))foo all k 2 1, x > 0, and g(k) E R2,, we have
ExcessRisk (x,{()))
r2
rq
1
(12)
Furthermore, there exists such that the ridge, ((A), achieves this lower bound with equality.
We provide proof in Appendix F. This implies that when there is no gap in the singular values of the input X, there is no separation between ridge and SD estimators (repeated or not). Intuitively, the 8j are all equal, the pre-conditioner for ridge (i.e., 1 and the pre-conditioner for the repeated SD, both restricted to have all eigenvalues to be equal. (Repeated) SD has no degrees of freedom to deviate from this. However, sj being unequal provides the freedom for the g(k) to control the SD's pre-conditioner matrix, and reduce the excess risk. This also why in Remark 4.2, we hypothesize that numerically, the optimal (g()))* depends inversely on the min-gap of the singular values. Figure 4 demonstrates this increasing relationship of the magnitude of the optimal parameters w.r.to the decreasing singular gap.
Necessity of Assumption 2.2 on #* Theorem shows that there is a large separation in the performance of repeated SD over ridge when Assumption 2.2 holds with small B. In general, this translates to l* being highly aligned with any one of the eigenvectors XXT (not necessarily the leading eigenvector). We show next that if 6* is equally (mis)aligned with all the eigenvectors then again there is no separation between ridge and repeated SD.
{u, درا of XX

---

extp
2:10
210
2
21
24
(a) 8 = [1, 1/2 4/, 1/4,,0 W1
(b) 5 = [1, 1/2,
(c) = 0.5 u: + u2 + us us)
Figure 3: On synthetic task (explained in Section 5.1), X has rank 4 with (a) 0 i and distinct 8y's; (b) 8 1, 1/al; (c) 0" = 0.5(u: + U2 + ug + u4). Each additional step of SD with optimal choice of (()) reduces Excess|Risk(00 (z( for any choice of on the z-axis. Panel (a) satisfies Asmp. and hence 4-step SD necessary to achieve the optimal excess risk. This is no longer true when Asmp. 2.1 is violated (b) Asmp. 2.2 is violated (c). Excess risk achieved by 4-step SD (i.e. the green lines) in panels (a) and (c) exactly match the numerical value given by RHS of eq. (14), i.c. the fundamental lower bound for any SD estimator. But this is not the in panel (b) [which has the same lower bound from eq. (14) as panel (a)), because Asmp. 2.1 is violated.
1-step SD
2-step
3-step SD
-dr
101
-5-
10
10a
1g
+
5
10a3
107
102
8-
-107
232
228
-10
-10
-10
-10
-30"
1--
0.50
-10-
3/4
1/x
Figure 4: On the synthetic problem from Figure 3a, fix À 0.125 and set the singular values of X as s, = {1 [j - L)e),in i.. consecutive values are separated by e. For k-step SD with & = {1, 3). we plot (5(0) (A) (i.e. optimal values the parameters) by varying E 0.1,, 0.05, 0.02, 0.01}. The magnitude of <(()) values increases the singular gap decreases, verifying Remark 4.2.
Theorem 3. Under the hypotheses of Theorem I except for Assumption 2.2, the true parameter 0*
satisfies (0", uy)² for all E [r], it holds that for all 2 > 0, k 1,> O, and {(k) E RR*,
ExcessRisk (0(),((1))
1 1+
(13)
28
Furthermore, there exists such that the ridge, (()), achieves this lower bound with equality.
We provide proof in Appendix G. Similar conditions needed when analyzing 1-step SD in [9] as well; [9, Eq. (9) in Theorem 3.8) is required for the 1-step SD to strictly outperform ridge. Observe that Eq. (9) is violated when either (i) sy 's are all equal (ii) (8*, 2's are all equal.
4.3 steps of self-distillation are sufficient
For given problem instance (X, 0* >2), the excess risk achieved by the k-step SD with parameter <(k) can be exactly characterized (Theorem 5), but it is complicated and can only be evaluated numerically in general. On the other hand, we show that there exists fundamental lower bound that holds for a linear family of estimators including all repeated SD, and this lower bound has simple characterization (Lemma 4.1). Furthermore, we show that under a mild assumption on the cigenvalues of X.X in Assumption 2.1, I, the r-step SD achieves the lower bound (Theorem 4). This allows precise characterization of the performance of r-step SD.
7

---

Theorem 4. Under the fixed design linear regression in Assumption 1, the excess risk of any k-step SD estimator on an instance (X, 8 ),), is lower bounded for all L, O, and g(6) E R by
ExcessRisk (0(1,
u,)
(14)
n
(0,, 1,)² + -
where Ug) is the 1th eigenvalue and eigenvector of X and r == rank(X). Furthermore, if Assumption 2.1 holds then there exists X > 0 and g(r) E R' such that the equality is achieved by the r-step SD estimator (r)).
Proof sketch. (Proof in Appendix H). The lower bound in Eq. (14) is an instantiation of Lemma 4.1, since
is specific linear family estimator with P = P (>, g(h)) 225 defined in Eq. (8). To show achievability, we need to show that P (A, (k)) 2 P for some value of k, X, and g(k),
This holds when the below system of linear equations admits a solution for the l parameters (i.e. (())), with an extra free parameter À > O. We show that with A and under Assumption 2.1, there exists that will ensure the existence of solution for this system of equations.
(0) )
(15)
A +
x+
(0)
1=1
Remark 4.2 (Necessity of Assumption 2.1). This assumption required for (15). Otherwise, the LHS would be the same for indices and j if 8, = 8j+1, but the RHS could still be different as (0", uz) * (0", 11+1)) generally. If Assumption 2.1 does not hold, there might not be any g(k) satisfying the set of equations for general 0* E IRd Further, the system of linear equations in Eq. (15) becomes more ill-conitiioned as the singular values 8,, E [r] get closer to each other. Capturing this dependence explicitly is outside the scope of this paper.
Lower bound for linear family. Consider linear family of estimators of the form ((P) = PP-XY, for P = U whose eigenspace coincides with that of XX (i.e., Ua - [ui..... u.)) and has d degrees of freedom represented by the eigenvalues $ diagg[1, ... ,_2]_ This is generic form of any linear estimator, albeit with the restriction of the eigenvectors matching the underlying U.- In particular, k-step SD is an instantiation of this with P = PA (()),(())52) S2 (refer to Eq (8)).
Lemma 4.1. The Excess Risk for ((P) = P. XY where = U satisfies
ExcessRisk (0(P)
(16)
(0+ 10, 12 + 22
with equality achieved
P p= U U
given by
(0'
j j r (i.e., > 0)
5j
(17)
any real value
2 (i.e., 8; =
Proof sketch. (Proof in Appendix H.I). One expand the excess risk for 0(P), which is quadratic expression in š,,j E [d]. Completing the squares gives the result immediately.
4.4 The excess risk for the k-step SD estimator is quadratic in {(K) e R²
We give an explicit formula for the excess risk achieved by for the k-step SD estimator from Eq. (8). Since (x,, (*)) is linear in each of E(*), i [k]] (recall that g(M) is reparametrization of (())), the overall excess risk is quadratic in g(k) as shown below. Appendix provides a proof and the expres- sions for (K), (k), and c. This quadratic form will be especially useful in experiments.
Theorem 5 (Informal version of Theorem 7 in Appendix I). Under the fixed design linear regression Assumption 1, the excess risk achieved by the k-step SD is quadratic in g(k) E R
ExcessRisk (0(2, (()))
(5())
(()) (5M) (5/h)
m (k) + c.
(18)
EBeck
ERA
8

---

From the detailed expressions given in Appendix I, we note that M(4) is a sum of r symmetric rank-1 matrices, which means it can have a maximum rank of r. This implies that M E R for k > rank-deficient (causing no additional decrease in the excess risk if the g(r) E R' were chosen optimally minimize the excess risk). This indicates that steps of SD might be sufficient to achieve the optimal excess risk, which is indeed what we observe in Theorem 4.
5 Experiments
In this section, we empirically show that multi-step SD can outperform the ridge and single-step SD. We first present a synthetic setting (section 5.1) to validate our theory. In section 5.2, we discuss a strategy to select & parameters based on the theoretical insight from section 4.4. In section 5.3, we implement that strategy on
regression tasks and show that it can indeed select performant & values that provide multi-step SD estimators that achieve smaller test risk.
5.1 Synthetic Experiments
We validate our theoretical results with a fixed design synthetic experiment. We consider a problem with d = 4, and set problem parameters (X, 0* >²)). Namely, X's singular values are set as 8y := 1/3 for j E [4], and 0* := U1 as in Theorem 1. Figure shows the result for 7 = 0. 0.125, along with two more settings that validate the necessity of our assumptions (validating Theorems 2 and 3). Figure 3a confirms that repeated steps of SD do provide a reduction in the excess risk, since the lowest point of the curve for each & reduces as increases. Also note that the optimal for each (one that produces lowest excess risk estimator) is different. Appendix J presents some more settings, including 0' == 1/v3(u; + U2) for comparison with [9]. An interesting phenomenon in Figure that local maxima in k-step SD's is curve coincide with local minima in (k s-sttp SD's curve, which was proven for k = 1 in [9], and we observe empirically for all values of k.
Explanation of Figures 3, 5. For the fixed design synthetic experiment in Figure 3 and the random design world experiment in Figure 5 (section 5.3), the curves plotted are with the optimal (+(*))* for each A. Hence, the curve of k-step SID will point-wise be lower/equal the curve of (k- sstep SD, since more steps of SD only provide more freedom. We say k-step SD strictly dominates (k- s)-ptep SID when the minimum value of k-step SDD' excess risk is strictly lower than that of (k: 1)-step SD. For Figure 3, the optimal (g(k) is found analytically from the problem parameters. For real-world datasets in Figure 5, we use the strategy in section 5.2 to find (g()))*
5.2 Choosing the hyperparameters & for real-world datasets
We have shown that at the cost of introducing additional hyperparameters and setting them to their optimal values, one can extract a large (upto Md)) performance gain. However, how does one select these e's for real-world datasets? The standard practice is to grid search. But this becomes infeasible for k-step SD for larger values of k, since performing a search over parameters in RR++1 (i.e ls values of g(k) and value of X) quickly becomes impractical. However, our theoretical analysis provides an insight that can be used to directly compute the optimal g(*) E RR (for chosen X) given a few evaluations on the validation set with certain chosen g (()) values. Namely, Theorem 5 tells us that the ExcessRisk is quadratic in E(A) (the reparameterized version). Now the coefficients of the quadratic depend on unknown quantities (like 6*, (²,))) however just knowing the quadratic nature of the functional, we can use the validation set to estimate these coefficients. To estimate the coefficients for k-step SD, we need A(K+33/22 + evaluations on the validation set. Appendix K provides more discussion, and detailed illustration of the above process for k = 2, Note that this feasible when the cost/time needed for a single training run of a k-step SD is small (since we need to perform it (l:2) times), which holds true for linear regression.
validation set, and perform
5.3 Real-world regression experiments
We implement multi-step SD for real-world regression tasks from the UCI repository [18), and demonstrate that 2-step SD can outperform ridge and 1-step SD. Note that for this section, the test set will contain fresh samples of X E Rdd i.c. random design linear regression instead of fixed design. Our metric for an estimator's performance will now be mean squared error (MSE) on test set of unseen examples, which is the empirical version of total risk (i.e. excess risk translated by the unknown noise variance 2²)) Using the training and validation splits, we compute (i) Optimal ridge: ((1)), (ii) Optimal 1-step SD: ((A1, E*), and (iki) Optimal 2-step SD: 0 ((2 (St. (5)) The
procedure is to plot the MSE on the validation set for grid of X values for all three estimators, and

---

choose the À that achieves the lowest eтrоr for each one (for any given X, the optimal (*(A) is chosen by the strategy described in Section 5.2). Finally, we evaluate the MSE of all three selected estimators (i.e. with the chosen optimal hyperparameters) on the test set, which serves as our performance metric (refer to Table 1). Appendix I. explains the overall methodology in greater detail. We apply this methodology on three datasets (dataset descriptions in Appendix I..1).
Table describes the results we observe. For two of the three datasets, 2-step SD can outperform both ridge and 1-step SD. For the Air Quality dataset, 2-step SD significantly outperforms both ridge and 1-step SD, reducing the MSE by 47.2% compared to the optimal ridge. In contrast, for the AEP dataset, we observe that the SD process cannot improve upon the ridge at all. The MSE curves in Figure 5 also shed light on these observations. Notice how Figures 5a, 5b show a gap in the ridge and 2-step SD (similar to Figure 3a), whereas Figure Sc shows no such gap (similar to Figure 3c).
In Appendix I.2, we explain the lack of gains from self-distillation on the AEP dataset from the lens of Assumption 2.2. Recall that Theorem says that the gains of repeated SD are most prominent with small 3 in Assumption 2.2. Figure 10 shows that the 0 for the AEP dataset is most 35% aligned with any of the eigenbasis directions, corresponding to 3 RJ 0.65. The same alignment for the other two datasets is 80%, corresponding to a much smaller 0.2. In Appendix L.3, we also verify that the strategy described in section 5.2 indeed selects performant& & values.
Table 1: Chosen hyperparameter values and the achieved test set MSE for ridge and 1, 2-set SD.
Dataset
Optimal ridge
Optimal 1-step SD
Optimal 2-step SD
Optimality hyperparameters Test MSE
Ag 102
Ai.5" = 10 -4.1
X1 (ST-40)
10 (- (-0.9, 16.2) 1.06
Air Quality
2.01
1.99
Optimality hyperparameters Test MSF
A/ = 102
A1,5" 10 66.5
Ay. (4) = 10 (-1.8, - 7788
Airfoil
1.34
1.22
1.19
Optimality hyperparameters
28 = 10223
Xi.t" = 10 0.1
Mr (4T.
102. (-2.4, - 2.3)
AEP
Text set MSE
0.62
0.62
0.63
33
32
05
0.6
155
1011
11.
321
(a) Air Quality dataset
(b) Airfoil dataset
(c) AEP dataset
Figure 5: Validation set MSE X for three estimators: Ridge, 1-step SD and 2-step SD.
Conclusion and Broader Impacts
In this paper, we theoretically studied the multi-step deff-distillation for fixed design linear regression, with the goal of characterizing its performance compared to the single-step SD. Perhaps surprisingly, we demonstrated that the optimal multi-step SD can outperform the optimal single-step SD by a factor as large as d in the estimator's 's excess risk, where d is the input dimension of the regression. Our analysis is limited by the fixed design assumption, and it would be useful to study the case of random design linear regression as well. We empirically demonstrated the gains from using 2-step SD on simple linear regression tasks. Larger scale empirical studies of multi-step SD, especially leveraging the insights of Section 5.2 on hyperparameter search, remain direction of future work.
Our contributions are largely on the theoretical understanding of multi step delf-distillation, and its potential performance gains. At a high-level, self-distillatio can use data more effectively, since it allows us to extract more knowledge from the same training dataset. In today's s age with data being one of the most important resources, this has positive potential impacts through more judicious use of data. On the other hand, we propose to use multiple steps of delf-distillation, requiring more compute and potentially contributing to higher environmental costs.
10

---

Acknowledgements
We thank Raghav Somani for numerous insightful discussions at various stages of this project. This work is supported by NSF grants no. 2019844, 2112471, 2229876, 2134106, 2143493, 2134012, and 2229881; and Microsoft Grant for Customer Experience Innovation.
References
[1] S. Ahn, S. X. Hu, A. Damianou, N. D. Lawrence, and Z. Dai. Variational information distillation for knowledge transfer. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pages 9163-9171, 2019.
[2] Z. Allen-Zhu and Y. Li. Towards understanding ensemble, knowledge distillation and self- distillation in deep learning. In The Eleventh International Conference on Learning Representa- lions, 2023.
[3] J. Ba and R. Caruana. Do deep nets really need to be deep? Advances in neural information processing systems, 27, 2014.
[4] K. Borup and L. N. Andersen. Even your teacher needs guidance: Ground-truth targets dampen regularization imposed by ceff-distillation. Advances in Neural Information Processing Systems, 34:5316-5322 2021.
[5] T. Brooks. D. Pope. and M. Marcolini. Airfoil Self-Noise. UCI Machine Learning Repository, 2014. DOI: https://b..ogg/112444///vv
[6] L. Candanedo. Appliances Energy Prediction. UCI Machine Learning Repository, 2017. DOI:
https:/dbi.orr//024444///
[7] M. Caron, H. Touvron, I.
Misra, H. Jégou, J. Mairal, P. Bojanowski, and A. Joulin. Emerging properties in self-supervised vision transformers. Proceedings of the IEEE/CVE international conference computer vision, pages 9650-9660, 2021.
[8] G. Chen, W. Choi, X. Yu, Han, and M. Chandraker. Learning efficient object detection models with knowledge distillation. Advances in neural information processing systems, 30, 2017.
[9] R. Das and S. Sanghavi. Understanding self-distillation in the presence of label noise. In Proceedings of the 40th International Conference on Machine Learning, pages 7102-7140. PMLR, 2023.
[10] Furlanello, Z. Lipton, M. Tschannen, L. Itti, and A. Anandkumar, Born again neural networks. In International Conference on Machine Learning, pages 1607-1616. PMLR, 2018.
[11] Gou, B. Yu, Maybank, and D. Tao. Knowledge distillation: A survey, International Journal of Computer Vision, 179()))789--181) 2021.
[12] G. Hinton, O. Vinyals, and J. Dean. Distilling the knowledge in a neural network. In NIPS Deep Learning and Representation Learning Workshop, 2015. URL http://ann /ttpvv/xxvvv/// org/ abs/1503 02531.
[13] C. Hu, X. Li, D. Liu, X. Chen, J. Wang, and X. Liu. Teacher-student architecture for knowledge learning: A survey, arXiv preprint arXiv:2210.17332. 2022.
[14] Z. Huang and N. Wang. Like what you like: Knowledge distill via neuron selectivity transfer. arXiv preprini arXiv: arXiv:1707.00
2017.
[15] V. Jankovic. Quadratic functions in several variables. http://elib: sanu. ac ac rs..rffflee/ journals/tm. tm/ ///5tm21.... pdf.
[16] H. Jeong and H. W. Chung. Understanding self-distillation and partial label learning in multi- class classification with label noise. arXiv preprint 204.22202.,0482, 2024.
[17] R. Jha, J. Hayase, and Oh. Label poisoning is all you need. Advances Neural Information Processing Systems, 36:71029 00271029-770522 2023.
[18] M. Kelly, Longjohn, and K. Nottingham. The uci machine learning repository. https: //archive. ics.

---

[19] D. Kobak, J. Lomond, and B. Sanchez. The optimal ridge penalty for real-world high- dimensional data can be zero or negative due the implicit ridge regularization. Journal of Machine Learning Research, 21(169): 2020.
[20] Y. Li, J. Yang, Y. Song, L. Cao, J. Luo, and Li. Learning from noisy labels with distillation. In Proceedings of the IEEE international conference on computer vision, pages 1910-1913 1918, 2017.
[21] Y. Li, X. Lyu, N. Koren, L. Lyu, B. Li, and X. Ma. Neural attention distillation: Erasing backdoor triggers from deep neural networks, 2021.
[22] Z.. Lin, Z. Gou, Y. Gong, X. Liu, Y. Shen, R. Xu, C. Lin, Y. Yang. J. Jiao, N. Duan, et al. Rho-1: Not all tokens are what you need. arXiv preprint arXiv:2404.07965, 2024.
[23] X. Liu, X. Wang, and S. Matwin. Improving the interpretabilityy of deep neural networks with knowledge distillation. In 2018 IEEE International Conference on Data Mining Workshops (ICDMW), pages 905-912. IEEE, 2018.
[24] Y. Liu, K. Chen, C. Liu, Z. Qin, Z. Luo, and J. Wang. Structured knowledge distillation for semantic segmentation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pages 2604-2613, 2019.
[25] D. Lopez-Paz, L. Bottou, B. Schölkopf, and V. Vapnik. Unifying distillation and privileged information, arXiv preprint 1xXiv:/511.03644 2015.
[26] A. K. Menon, A. S. Rawat, S. Reddi, Kim, and S. Kumar. statistical perspective on distillation. In International Conference on Machine Learning, pages 7632-7642. PMLR, 2021.
[27] H. Mobahi, M. Farajtabar, and P. Bartlett. Self-distillation amplifies regularization in hilbert space. Advances in Neural Information Processing Systems, pages 3351-3361, 2020.
[28] N. Papernot, P. McDaniel, X. Wu, S. Jha, and A. Swami. Distillation as a defense to adversarial perturbations against deep neural networks. In 2016 IEEE symposium on security and privacy (SP), pages 582-597. IEEE, 2016.
[29] M. Phuong and C. Lampert. Towards understanding knowledge distillation. In International conference on machine learning, pages 5142-5151. PMLR. PMLR, 2019.
[30] A. Romero, N. Ballas, S. E. Kahou, A. Chassang, C. Gatta, and Y. Bengio. Fitnets: Hints for thin deep nets; 2014. arXiv preprint arXiv: 1412.6550, 3, 2014.
[31] A. A. Rusu, S. G. Colmenarejo, C. Gulcehre, G. Desjardins, Kirkpatrick, R. Pascanu, V. Mnih, K. Kavukcuoglu, and R. Hadsell. Policy distillation. In International Conference on Learning Representations, 2016.
[32] S. Sun, Cheng, Z. Gan, and J. Liu. Patient knowledge distillation for bert model compression. arXiv preprint arXiv: 090./908.9999 09355, 2019.
[33] G. Urban, K. Geras, S. F. Kahou, O. Aslan, S. Wang, A. Mohamed, M. Philipose, M. Richard- son, and R. Caruana. Do deep convolutional nets really need to be deep and convolutional? In International Conference on Learning Representations, 2017.
[34] S. Vito. Air Quality. 10.24442///55KKS
UCI
Machine Learning Repository, 2016.
DOI:
[35] Xia, T. Wang. J. Ding, X. Wei, and M. Chen. Eliminating backdoor triggers for deep neural networks using attention relation graph distillation, 2022.
[36] C. Yang, L. Xie, S. Qiao, and A. L. Yuille. Training deep neural networks in generations: A more tolerant teacher educates better students. Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 5628-5635. 2019.
[37] C. Yang, L. Xie, C. Su, and A. L. Yuille. Snapshot distillation: Teacher-student optimization in one generation. In Proceedings of the IEFF/CVF Conference on Computer Vision and Pattern Recognition, pages
2019.
12

---

[38] J. Yim. D. J. Bae, and J. Kim. A gift from knowledge distillation: Fast optimization, network minimization and transfer learning. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages ,
[39] K. Yoshida and T. Fujino. Countermeasure against backdoor attack neural networks utilizing knowledge distillation. Journal of Signal Processing, 2020.
[40] S. Zagoruyko and N. Komodakis. Paying more attention to attention: Improving the performance of convolutional neural networks via attention transfer. International Conference on Learning Representations, 2017.
[41] L. Zhang, Song. A. Gao, Chen, C. Bao, and Ma. Be your own teacher: Improve the performance of convolutional neural networks via self distillation. In Proceedings of the IEFE/CVF International Conference on Computer Vision, pages 3713-3722, 2019.
[42] I.. Zhang, C. Bao, and K. Ma. Self-distillation: Towards efficient and compact neural networks. IEEE Transactions Pattern Analysis and Machine Intelligence, 44(8):4388 4404438884444,, 2021.
[43] Y. Zhang, T. Xiang, M. Hospedales, and H. Lu. Deep mutual learning. Proceedings of the IEEE conference computer vision and pattern recognition, pages 4320-4328, 2018.
[44] Z. Zhang and M. Sabuneu. Self-distillation as instacce-specifee label smoothing, Advances in Neural Information Processing Systems, 33:2184 2195, 2020.
[45] B. Zhu, M. Jordan, and J. Jiao. Iterative data smoothing: Mitigating reward overfitting and overoptimization in rlhf. arXiv preprint arXiv:2401. 16335, 2024.
13

---

A Notation
In this short section, we collect some notation used throughout the proofs.
Decomposition of X. Let rank(X) = r and the SVD of X be X E where 81 2 #2 2 &r O, and each u Rd and Vj E IR.. Further, let {1i, u2.... (ua) be the full set of left singular vectors of X (even those corresponding to zero singular values), forming an orthonormal basis of R2d Let Ua E Rdxd and U, E Rdxr denote the left singular matrix of X for the full and truncated set of left singular vectors respectively. Similarly, let Va E Ruxd and V, E Rax* denote the full and truncated right singular matrix. Let Sa R2dd and S, Rr** denote the collection of the singular values (with and without zeros respectively). Then, it holds that
X U, U2SAV
(19)
Indices. Throughout the text, the indices i lie in [k]] i.e. they denote subsequent steps of self- distillation. The indices j lie in [r] or [d], ie they denote dimensions of the d-dimensional space (aligned with vectors of U, or Ua). Uy, Vis will denote indexing into vector e, matrix V. There is one exception 2 denoting a vector's jth clement, which is the below.
Components of 0* on Ua. We will denote 0j (0", u,)²,3 j [d] as the components of (* onto
X's left singular space. Note that > 07 1 2
B Discussion on norm used in excess risk metric
We point out that Das and Sanghavi [9] used the |l.1|2 norm instead of the more natural ||-Ils. norm measure their fixed design excess risk (in eq (2)). Almost our results have an equivalent version in the |||12 norm setting also, since the only difference is in the relative weighing of the underlying dimensions of variation, i.e. with the II-Ils: norm, Vj E [d], direction u, weighed by st ///n instead of constant 1 weight (independent of j). In particular, we also present the version of [9, Eq. (9) from Theorem 3.8] that will result strict dominance like Eq. (7) under the Σ., norm, i.e.
min X20
Ey [1((A, () - 0 11
min F, [10(A) 0 1 X20
(20)
-ExcesRlek(((AAE))
=ExcesR(sk(((AA)
Proposition B.1. Let X orgmtins, Then Eq. (20) holds problem instance (X, 0- 72) when
(8)
2t (10", u&) 2 -8", 12)
<0.
(21)
k=1 (A+ + 89)² (A* + x7))
Note that this differs from [9, Eq. (9)] in just one respect: it has stst instead of s7
C Details on & parameters for general k-stepp SD
C.1 Full k-step SD is representationally no larger than Repeated k-step SD
We first illustrate the Full k-step SD in Figure 6. The repeated version introduces l extra hy- perparameters in the form of g(h) E g² parameters, whereas the full version introduces k(k+1)/2. 11/2.
So
S1
S₂
S
Repeated ks-step self-distillation
So
S
S₂
S
Full k-step self distillatin
Figure Illustrating two possible generalizations of 1-step SD to a k-step process.
Consider the case of 2, since that is the lowest value of & for which the full version and the repeated version differ. Figure 7 illustrates this difference explicitly. We will show that the freedom
14

---

o F is no more than the freedom of & E R This shows the equivalence of the full 2-step and the repeated 2-step versions, when & E R & E TR. are free parameters optimized over the entire respective spaces. Such equivalence for the general k-step case then easy see.
Nodes So So are both solving the ridge regression problem (3). Let 0o 0 Xy denote the estimator for both these nodes. Similarly Si and $1 are solving the same problem, although T with different parameters. We have (1(()) x X (5i X 0g (1 {))Y) Y) (and similarly, one can write 01 with & instead of {1). Now the node S2 is also solving parameter supervised SD
problem, so (2( 62) = 5 X (fz X (E1) + (1 E2) Y). Expanding this gives
(2(5i = {11 (2) Ia (E2 fz 1 Eife (2, () 1 (22)
But the optimization problem for S2 is 2 parameter supervised SD. evaluates
E2
E2 -
-Ea))
I Y + X +1110112
argmingeRd
x 0u x xT0122+
x X 01 XT0122
2
2
Following through a similar calculation, we observe that 02 for node 82 given by
(E, E2a) = (1 E2. E2s) Ia (Eza + E2o ElE2)) 22 1xX + E1
(2 ( 12 'XY (23)
E1
E2
So
S1
S
Repeated 2-step self- distilisttlatioon
Eza
E2
5o
S
$2
Full 2-step self-distillation
Figure 7: Repeated Full 2-step SD. We show that the extra freedom of the parameter ε2. does provide any additional freedom, when the other two Eτ, E2s are optimized as free parameters.
Equations (22) vs (23) show that the full 2-step offers the same freedom as the repeated 2-step. However the repeated version has one shortcoming. To generate the optimal 2-step SD estimator, &1 needs to be different than the value needed for generating the optimal 1-step SD estimator, That is, the repeated k-step version, with its & free parameters, allows only generate the final -tth estimator as the optimal one (i.e. if we choose the (f1,&2) values so that the 2nd estimator is the optimal 2-step SD estimator, then the 1a estimator with the chosen & won't be the optimal 1-step SD estimator). Whereas the full k-step version, with all its k:k + 1)/2 free parameters, allows us to generate a sequence of all optimal estimators.
C.2 Proof that k-step SD estimator with ((k) E g will have the form given in eq (8)
Consider Figure ((k) e TR= the set of actual imitation parameters used for running k-step (repeated) SD. Let ( denote the k-step estimator generated by using g(k) parameters. In what follows, we will prove that 0(A, g(*)) will have the form given in eq (8), with {(k) e RR* as the
described reparametrization of (kk) E j²k. Since we're re in the repeated version, the 4 step objective will be combination of losses w.r.to ground-truth labels and predictions from the (A: 1)ah step. So, the objective for the tt step is
0(), argmingerd
(k)
X ((T ((k-1))
X TTO
(1
(k) 5k
X
0012 1011
A
(24)
Note that (AA, (())) recursively depends on predictions from the previous 0(A, ((k- This objective of the form in eq (4), so similar to eq (5), we have the following expression
0(2 (M)) = (XXT + Ala) x c
(k) x xTŌ(2,e(* (k- + (())) x}
(25)
15

---

xx = ={a- x.- 'Y XY (. ' 10'xx0000 (O ((-))
(26)
Using this, we can inductively prove that the general form of this estimator is captured by Eq. (8).
Claim. With the described reparametrization, i.c., < = (1 (1-5%- [ Iii= 5/a) for each i E [k]
(where we let <6*) = 0), Eq. (8) is the solution to the recursive form Eq. (26).
Proof. We will prove this by induction.
Base Case. From eqs (8) and (26), the case for l = 1 is true (with g(1) = {())) Inductive Step. Assuming Eq. (8) captures the solution of Eq. (26) for k 1, we get
8(A,5(1) - {( {1-E1 c(4
k-1
c (--1) (o (ox'xxT)))
I.
+ c 2
XX
22 sx
This again satisfies the form in equation (8), when the following coefficients match
(K)
k-1
(1
[k 1---1 1)) = =11
<(h) - = =t Vi E (2,3,...
One can then that the described reparametrization makes the above hold true. Remark. Since
is simply the 1-step SD estimator with the form 0(), g(2) P 22 'Y for some preconditioner P. plugging this in the equation eq (26), we realize that we can factor out 2 YY (i.e. the ridge solution) from the expression on the right side. That is, ((1) = P'. S XY for some different pre- pre-conditioner P', This is why inductively we get that A(A, g (()), k 12 1 all produce a pre-conditi on the ridge solution, as shown in eq (8). Further, eq (26) also dictates why we get increasing powers of the term 22 XXX in the final expression.
'
C.3 Explicit reparametrization for 2.3
We explicitly demonstrate the reparametrizzaion for 1: 2. As noted in Section 5.2 (and Appendix K), owing to the quadratic form of excess risk in g(*), one can find the optimal g()) analytically. It can then be translated back to the original ((() as follows.
For = 2, the form is (dropping the (2) for ease)
f
& =
& = E
+ E
(27)
(5 1 62)
For = 3, the form is (dropping the (3) for ease)
E =
E E1 + E2 + Es
5 + E + Es.
(28)
E2 + Es
D Algebraic expansion of ((x, (())) from eq (8)
Lemma D.1. The estimator ((2,g(h) given in eq (8) can be expanded as
&
s7
1)
sf
8(),5(0) = Σ
St
(k)
1 -
A x
X+
sy
(0",
u,))
Uj
5=1
i=1
d
82
Z(k)
1
8j
(n) v.) uy
X + 83
X
j=1
Proof. The expansion relies on XXT U and X + AI = + U is orthonormal (U.UT I, = U Ua). which neatly cancels all occurences of Ua in the middle, and allows us to directly combine the matrices in the eigenvalue space.
16

---

E Detailed version and a proof of Theorem
We first write a detailed version the theorem that exactly characterizes the family of problem instances that admits the separation. We then present proof. We point the reader to Appendix A for notations used throughout the proof.
Theorem 6 (Detailed version). Consider the following conditions on 0* X that characterize a family of problem instances {(X, ?²)]:
1. f* satisfies 3j E [r], (0*, uz)² 1220 (1 (1-8) (107))
[Assumption 2.2]
2. ||0 2 198 (11) (#1/s.)*
3. Assumption 2.1 holds on the singular values of X
[Assumption 2.1]
4. (ff/2) S holds on the singular values of X
Under Condition #1 + Condition #3, holds that
22 (1+
11s
YE > 0, 0,3 R", ExcessRisk (0(A,E(1) S n
(Rewriting eq (9))
72
Under Condition #1 Condition #2 Condition #4, it holds that
'A>0,VES ExcessRisk (B(A,E) 2
0.99
(1
B)
(Rewriting eq (10)
211
Under Condition #1 + Condition #2, it holds that
ExcessRisk (B(2)) 2 0.98
1 8
ry²
AA 0,
(Rewriting eq (11))
1 0.99.3
Proof. We will analyze all three: k-step SD, ridge, and 1-step SD.
Let [r] be the index that corresponds to the maximum (unsigned) alignment between 0* and uy, among all j E (r) If not unique, pick any of the corresponding indices. That is, j' satisfies translates the below two inequalities,
(0', up) 2 (0', u,) for all E [r). Then, Condition
0. = (0", uuy) 2 (1 3) 110-11
(29)
Σ 0j j=1
Σ 00' u2)²² < Σ 10' -.
(30)
j=
k-step SD: Since Assumption 2.1 holds, from Theorem we directly have
07
YE > 0, (7) E R,, ExcessRisk (0 (N.5(*))
(31)
03 +
12
72
83.
87
72
03. +
12
00 + 1
(32)
0
+
(33)
n1
00 +
jm 1. 3
83
222
1 1+
Σ
(34)
2
03
17

---

1+
Σ
03
(35)
n
j= "ーl
Using eq (30) in the above, we have
$ 72 n
(1+
10m]18s7 72
(36)
This completes the proof for eq (9).
Ridge: We will now show (11), by characterizing the Excess Risk for the ridge estimator in this regime, showing that it can be upto r times worse. From Lemma I.1, we realize that the Excess Risk expression for the simple ridge estimator ((A) is given by
(X90 + 735)) 53 (A a3+3
YY > 0, ExcessRisk (B(N))
1
(37)
j=1
(38)
Just the Variance term
Inequality (38) above comes from ignoring the bias term (since it is non-negative). Note that the variance term is a decreasing function of X. And again from Lemma I.1, we get the following expression for X >> 0 that minimizes the ExcessRisk.
X 2
(39)
Σ == (A- +ra))
Σ/ 1 (x*+)3))
577
(Ignoring positive terms in the denominator above)
03
Ar (A++o3))
72
(X+ + 87,)
(Rearranging the above)
/
(X+ + 83)
72
(X* (A* 87,)
Σ
(Using eq (29))
(1- 8)110-112
(2++ $3)
72
Σ
(x++
+ Σ 8f (A+ 87,)
(1- -1-B3)10-1 1-18)110-112
(1++53) 53)
(x+ + 87)
j-3++1
(1 - -1 0-111
72
Σ
of
53)+
(Since 83' Ss for j 5')
(3++3))
j=
72
Σ
50
t1+a3 (Since X+
3 for j >> j. as X > 0)
(1- -1-11110-112 1-110-11
< o7
1=
72
5r (2)²
18

---

2
81 8r
3
110112
r
+
1
7²
2r
(40)
1-
3
|00
112
Now since the variance term in (38) is a decreasing function X, we can use the upper bound of from (40) to lower bound the ExcessRisk of optimal ridge as
ExcessRisk (0(2))
7
2
(Rewriting eq (38))
2
n
A
j=1
2
(Since 0 <8 S 83 for all j)
2
1
dr
r7
11 (Using eq (40)
+
1
2rya
1-B
110
?2
3r
r7
1
(Using Condition #2)
m
1
1
(3
r72
(99(1 - 33)
(41)
(100 99,3)
r72
.99
(1 - B)2
(42)
100
(1 0.99,3)
2
2.0.8
This completes the proof of eq (11).
1 1-step SD: To evaluate 1-step SD's ExcessRisk, make of Theorem 5. Observe that since
A 1, the ExcessRisk is simple quadratic in one variable. We will call g(3) E IR just & (similar to eq (6)). And similarly, we will call ML1, (1) as just M, m, both real-valued. We then have
ExcessRisk (B(A.E) ME² + 2m +
m²
Ag R,
(By simple quadratic min)
M
Mc m²
(43)
Note that M, m, e are all functions of X. Now we evaluate their expressions. is simply ExcessRisk of ridge, which we will fetch from Lemma I.1. Evaluate M from Theorem 5:
AP
1
M
-C1(1) CC(1)
n
(1 p.)
A0 + +72)
1
pz
(Using Cý(1) = 1 - itp,)
(1 p2)
(1 p3)
(203 + 721))
(1+
(22035f + +
(Using Pj = 4
(A+
n
19

---

Evaluate m from Theorem 5:
1
(A0] -pp)
+ (1+P))² C3(1)
m-
11 j=1
1
(A03 -72) Pj
(Using C₁(1) = 1 Itps )
n j=l
(1+ (1+
1+ Pj
(22035) )2))))
1
(Using Ps = =
(A 83
n
We now write the expressions together for comparison, before we use them. That is,
6
n n-M = 2²
+
+ 8f)4
+ sf)
0759
n. 2²
xxy² 2
+ 87)3
(A 67)
n X²
Σ
(Directly from Lemma 1.1)
(A + 2/2
(A + 22)2
1=1
j=1
With all these pieces, for the numerator in eq (43), we have
n²² (Mc m²) = Ti T2 + T3
where we use Ti, T2, T3 to capture terms of different forms. Ti will capture the 03 product terms, T2
will capture the 7² product terms, and T3 will capture the cross terms. Namely,
030
2
T= + +
(A + 5ty²
(A+ s7
(A+ (x) $f)
33
2
s7
2
x
(X+ + 82) + spp
s7)
(1 + st)
20.
s/st
1
2
T2 T2= 22
(}+ 8 5712
(A + 83)2 +
(A 8712
(A+ + 8)) + s7)
/=1
st (X+ + 03)2 + sppz
= 22 4
(A+ - (A+ s?y2
|= 1=1
20.
(t+)
Ts= X272
03 (1 + 83)4
Σ (2+ + (7)3
of
1=1
0j03
Σ a s734
39
+ +
(A + $31²
07 (A + 07)3
+ +22372
(A + s713
0 c
03 8 (a + 8312
2 2222
Σ
(A + 5
+ 3312 2
(A + 83
21
Yi
Za
Y2 (Ignoring the 3rd term)
20

---

We lower bound the terms Z1, Y1 and Z2. Y2 in the above lower bound on T3 using simple functional 3P
analysis. Consider the fact that the function fp(z) == (A+=²)" over 2 > 0 is strictly monotonically
increasing for any p E N. since f2(2) = 2pAs2p-1 20-
(A+32)ptz > for all 2 > 0. We will use the instantiation
f4 for Z1 and Y2, and f2 for Z/2 and Y1. For Z1, we get
1
21 == = Σ
07
(A
(A+3)
Σ 03
1
(Using monotone increasingness of f4)
(A + 22
8
1
Σ
0f
(Using monotone decreasingness of f(z) : 1/22)
(A + 82
81
1=1
207
8/
(1 - () 1011
(Using eq (29)
(A + 22
1
2 (1 B) 1
(44)
$7
(A + $2)
Following a similar analysis scheme, we get
Z2 2 (1 - 3)110 112
(45)
si (A s2)2
$f
2 () s2)2
(46)
1
Y2 2
(47)
8
() + s7)1
Using eqs (44), (45), (46), (47), we get an overall lower bound on T3. For the overall lower bound on the numerator of eq (43), combine this with eqs (t), (++) for the terms T₁ and T2. We get
n² (Mc m²) m2 (1 (1- (-33)100'1 12
12
x
x² +
(48)
of
(A + $2)6
s
And for the denominator in eq (43), we have
0J
$ () + s7
n M = 2
(A 53 +22g2 2
/=1
07
x2
2
(49)
(A + 83)4
(A + 87)4
j=1
Upper Bound x X2 from eq (49):
8 $
S 2
Σ
Σ 0
2
8
1=1
< X2
Σ
03
j=1
21

---

j=1
|=1
12
X²
(100112
+
(11011337
3 +m²)
(50)
77
Upper Bound x 2/x² from eq (49):
6+ g
x2
Σ
+ 7,2
Σ
j=1 X
1
Σ
0Jo9 6
+7²
Σ
X2
1
6 Σ
0z + +7 ΣΟ
(##)
X2
j=l
(100713
+r
(51)
X2
Note that we used ΣE= 03 < ンー= 10 in eqs (#. #4). Now we put together the numerator lower bound from (48), with the denominator upper bound from eq (50) for the first term, and from eq (51) for the second term. We then get
Mc- m²
(1- 131101112
12
1
n
M
2 2m2
$f
(A + 22
(1100 +
m2
+
$1
11 + my?)
110m10 11s s
1
= (1 - B) my?
+
$ (1
|2 + r2
(A + 2
(A + s2)6
$1
12
1
(1 B) rr²
(52)
A
+
my?
+ 2)
(X + 82)6
Q2
Q:
Under Condition #2, it holds that
r2
(since 8, 81). This gives
1
13
198
198
198
Q
0.99
(53)
199
And now we analyze Q2 using simple caleulus. Note that
t + 1 () + 22)
Q2
where = 8/
s
Simple caleulus shows that this function is minimized at Ā (f//(tas?)) 0.2 value of the function (evaluated at X) can be used as a lower bound for this, giving
(5
0.2
And the min
Sr
Q2 2 23 (X + $?)
5 2
(54)
1.0
25
51
81
Combining eqs (43), (52), (53) (54), we get
ExcessRisk (D(A.E) 2 (1-
ry²
0.99
Sr
12
AA 0, VV IR Using Condition #4 in the above gives the desired eq (10).
n
25
8
22

---

F Proof of Theorem 2
We point the reader to Appendix A for notations used throughout the proof.
Proof. Under the condition of Vj E [r 1. we need to analyze the ExcessRisk for both k-step SD and ridge. Denote Q : وラ= 03 for simplicity.
k-step SD: Since assumption 2.1 violated, we cannot use Theorem for the k-step SD. Instead,
we will work with the quadratic expansion of ExcessRisk from Theorem 5. We will rewrite the expressions from Appendix I for the quadratic coefs. Note that Pj X/s}
for all j [r] (1+ for all j E [r], E [k] also
becomes independent of in this case. And so Ci)
becomes independent of j. Let C(i) == (1+A) denote the coefs (t), since they're 're now
independent of Let (C(1), ((2), C(k) E R Then, we get
82) E [4] x [4]
M (k)
1
03 7
C(b) -(12)
(1 1)2
T1 j=1
1 +r?²
C(ii) -(ii))
n X1+
-
1 Q ?+m²
M
E R k becomes a rank-1 1 matrix
ww
(1 2)
Similarly, for (k) we get
1 r 26; - -?
Vi E [k]
m
(k)
- Σ
C(h))
n. ;=1
(1 112
1 XQ m2
m (1)
E ER*
w
n (1+ + 2)2
And similarly, for e we get
1 XQ +2 n A12
E ER
Using the above expressions, rewrite the overall ExcessRisk for any k-step SD (k 2 1)
1 /1/Q+1 (++m² RicessRisk (0(2.g())) n (1+A}* (w, 5w))2 + AQ m2² (1+ A)2 (w, ((l) + (1 X)2
We're aiming for lower bound the above quantity, and then analyze the remaining a function of A. Note that this is quadratic in the scalar (w, {())).
first minimize with respect to g(k)
Since q(x)= == ax? + 2hx + = c + a (x + 5)²² 2 6²
we have
X²Q rT (XQ r²7)²
Vk 2 1, (. x
ExcessRisk ((A,E(1))
2 n (1 X)2
Q+ r72
X²Qr72 Qr?² + 2XQr22
n (1+ {}²
Q r+
Qm²
Q m2
m2²
n
Note this expression is independent X. Hence the above lower bound holds Vk 2 1, 1,K((K) k AA > O. This concludes the proof of eq (12).
23

---

Ridge: For ridge, we can simply borrow the expression of from above for its ExcessRisk. That is
ExcessRisk (B(2)) = xQ+m
(1+
Let X denote its minimizer over À > Simple calculus gives X ry² the same expression
Q Plugging this in, we get
ExcessRisk (ō(x*)
ry
1
1
m
Q
This completes the proof of ridge achieving the lower bound in eq (12).
G Proof of Theorem 3
We point the reader Appendix A for notations used throughout the proof.
Proof. Under the condition of Vj [r].6] 0, we need analyze the ExcessRisk for both k-step SD and ridge.
k-step SD: Again from Theorem any s-step SD estimator's Excess is
44 1, O, Vg(A) E RRt ExcessRisk ((1.,
7
r
2
7
0 +
j=l
72
Σ
n
1 +/
j=l
(Since Vj E [r].0] = =)
This completes the proof of eq (13).
Ridge: Now for the ridge estimator, will use Lemma I.1. From eq (61), get exact expression for that minimizes the ExcessRisk. Namely
7² X+
2
Substituting this in eq (60), get
(Ar))00 + +g23)) 83
ExcessRisk (0(x))
(X+ + $
72
2
(X* + 53) 33
(Since \00; = --
=2== = 7²)
(A+ + 03)2
n
j=1
72
1
n
(1+ 3
2
(Substituting X ?
n
(1
This completes the proof of ridge achieving the lower bound in eq (13).
H Proof of Theorem
We point the reader Appendix for notations used throughout the proof.
Proof. The proof of (14) is a simple instantiation of Lemma 4.1. Since the SD estimator a particular instance of the general ((P), i.e.
0 (2, (t) = 2(pp p P (2,5(0) (2,1)
24

---

Eq (14) follows from the lower bound in Lemma 4.1.
For proving the equality being achieved, we will work with the general k-step SD estimator, and show that: Under assumption 2.1, k steps are sufficient to provide enough freedom to g(h) so that the k-step SD estimator achieves the lowest possible ExcessRisk.
Using lemma 4.1, note that the condition P (A) =25" P is sufficient to ensure that Ô (A, ((4)) 0(P*), which would mean that the k-step SD estimator admits the lowest possible EicessRisk. Since the eigenspaces for both sides of the equation are the same (Ua), we only need to ensure that the eigenvalues match on both sides. That is, we need the following condition (for indices j 2 + 1, there's s no condition since lemma 4.1 tells us that any real value of šy suffices).
Vj [r]
1
53
(55)
1
A+
A
S
87
02
[r
1
(k)
(k)
(56)
Si
A 83
À + 5
0 +
2
i=1
Let ay(a) x
Since A > 0, oj E (0, Vj E [r]. The above condition can then be written
succinctly in matrix form as
A (X) g(k) (A)
(57)
E
ERK
With the following describing the elements of A (A), a(A)
[a(A]], == 1 (A + 53) 8]
j [r] j jebiie [M]
[AL)(N]] j:i -a
The notation A ( (A), (A) explicitly denotes the dependence on A.
Now, (A) being invertible would ensure that (5(A) E R that makes equation (57) hold true
(i.e. the system of equations admits solution). For that, we need (1) k = and (2) A (X) being
full-rank. The first condition is stated in the lemma. In what follows, we will prove that 3Y > 0 such
that the second condition satisfied, i.e. (x)) being full-rank. Decompose ( as
Tai (A) a (A)2
(A)r
1
aa(A) az(2)
az(A)"
(A)= =
(A)(A) (A)2 ar (A)" PxP
Pxr
v(A)
Where W 11T T is the matrix of all ones, and V(A) akin to the square Vandermonde matrix (only difference being that the standard definition of Vandermonde also has column of ones).
Using the Matrix Determinant Lemma, we can write
det (e)( (1 (1-1 11 det(-V(A))
First note that, with the determinant expansion rule based on the first row
[
0
det V(A) = det
[
(++1)x(++1) v(A)
The matrix the right is exactly the Vandermonde matrix with dp 0, a (A), az)), (A). Using the formula for the det of a standard (with row of ones) Vandermonde matrix, we get
det V(A)=
II ogi<jSr
(())))(()))
II a((A)-
II (a,(A) ax()))
IsiST
Igisjrr
25

---

Since (A( E 10. for all E [r]. and a, (A())ss are all distinct, we conclude that det ((A) * 0, i.c. (A) is full-rank. What remains to show is that the scalar (1 - (-A) is non-zero for some À > O. With the SVD of V(A) CDE-1 where C, E are orthonormal and D is diagonal with positive entries, one can expand this term as:
I
= 1 - 1,
dmaa
Now observe that as À - 20, (1) + 0 for all [r]. which means that V(A) O,xr, which means that (1) dmaz - 0+. and (2) C ++ (since ((A) becomes closer to a symmettic matrix, allowing its left and right singular matrices approach equality each other). That is, Zmaz oo and (C- 1, 11 + ||]|? = r. This would ensure that |1 (AA) > 1, meaning that the scalar (1 - 11-1 would be non-zero. Hence YY > 0, such that (A) is full-rank.
H.1 Proof of Lemma 4.1 Proof. The estimator ((P) expands as
O(P) - U + UnŠS.VIn
Expanding the Excess Risk shows
ExcessRisk (N(P)
Σ (B.. 1) 03 wi
72
(5) 53 wz)
Bias
Variance
where wy for all j E [d]. This is simple quadratic expression in 3. Completing the squares gives the desired optimal values of 87.5 E [d].
I Quadratic ExcessRisk: detailed version of Theorem and proof
We point the reader to Appendix A for notations used throughout the proof.
Theorem 7 (Formal version of Theorem 5). The Excess Risk is quadratic in g(i) E IR Namely
ExcessRisk (0(A, (5TA)
((a)
(E())
2 (EZU)
(k)
+
(58)
ERt
ERA
where the below holds, for indices (i1, in [k]] x [k:].
07
2 r
(Kk)
C,(,,) - C,((2) +
(((i))CC(())
11,22
n 1=1
PJ(1
+ p3)²
n j=1
(1 + pz)2
((8)
1/152
A0
+ ?2
1
P5
(C((1)-C)(12)
n
(1
+ p,)
0j
x2
(-1)
m
(k)
-Cy(i)
(1 pz) c200
n1
+ (1;p)
n
j=1
(A0) -2)
-C,(i)
(1+P))²
0j (1 + p1)2
2 r
Σ
j=1 (1+
n
n
Variance
26

---

(3 + +22) (1 p2)
The B,b and V, notation is used to indicate the (squared) Bias and Variance terms respectively. Here Pf.J E [r] is used to simplify the notation, and is defined as Pj 2 E [r].
And the coefs Cj. j E [r] with i E [k] have the form
12(1) = P1+
JE i
(59)
Proof. We first use the expansion from Lemma D.1. Secondly, expand 0* = (0', u,) ()=((",u))u Using these, we can expand Excess Risk as
ExcessRisk (0)), = E, | ((0)) 8+
87
2
83
f8
1
+
2
8j
2
A + 8.
22
i=1
Σn weighing
8 (A+ + s792
A + (-+x+
o
+
(1++]
-1
(k)
E,, weighing
Writing down the above expansion and collecting the corresponding quadratic, linear and constant terms' coefficients in the g(A), give the desired expressions.
I.1 RicessRisk for ridge
Since we will compare the ridge estimator's ExcessRisk to the k-step SD estimator, we state the ExcessRisk expression for the ridge estimator (eq (3)) formally here.
Lemma L.1 The ridge estimator ((A) satisfies
(A20) + +2233) 87
AA > 0, ExcessRisk (D(A))
(60)
(A 83)²
And the optimal penalty > that minimizes this Excess satisfies
Σj=1 j=1
+*++))))
X 72
(61)
Σn 02 0
(**+a?)*
Proof. Eq (60) is simple instantiation of Theorem in the vacuous case of k: 0. Specifically, the quantity captures exactly what we need. Borrowing its expression from the detailed theorem statement (Appendix 1) gives us eq (60). Now, taking the derivative of the expression in eq (60) and setting it to zero, we get the stated expression for X > O.
Discussion on synthetic experiments
This section follows up Section 5.1 with more details and examples about the synthetic problem. Figure 8 shows four more settings, with E (0.125, 0.25) and 0* E (u,, 1/v2(ui + u2)].
Figure validates that repeated steps SD provide a reduction in the excess risk, since the steps of
lowest point of the curve for each & is reducing A increases. Observe that at k == SD, the curves Figure become flat. This is because we stated Theorem 4 with a "EÀ 0" such that step SD can achieve the lower bound, but in practice it can happen "Aλ > 0".
27

---

0.125: nm100, d 4; 16, 0*
y 0.25: 1000 d 4: 15, 0"
2
Ridge 61A)
Rigge: 51A)
1ssep
1-stp 66..8
RA.5
stop SD: (
stop SD: (A.
dtstp 6
4-stop SD: 8A.6")
PereeRoo
ExcessRok
2.14
2.1
2-11
2:11
2-4
2-2
2
2-1
2:2
2
2
Azy?
A2y²
(a) 0.125, 0
(b)
0.25, 0
16.
18.
Ridge: (1))
BAA)
2"
1ssp SD: 6
1-stop $0, 8A.E)
stpp SD: (
2tsp SD: 86.6
3ustpp (rk.g
9IA. (
RA.5M)
28
2
A/y
Azy²
(c) 7 0.125, 1/v2(u: (ui u2)
(d) 7 0.25, 1//2(u1 + U2)
Figure 8: Plot of excess risk of k-step SD with optimal g(k) for each X, for t: E (0,1,2,3,4] synthetic problem (Section 5.1).
K Discussion on choosing & parameters
For the k-step SD estimator (eq (8)), for any chosen Theorem tells us that the ExcessRisk is quadratic in (kk) R* To estimate the coefficients of this quadratic from certain chosen evaluations of (k)), need total of k(k+3)/2 + 1 evaluations. This is because the number of unknown coefficients are (i) k for square terms, (ii) k(k-1)/2 for cross-square terms, (iii) k for linear terms, and (iv) for the constant term. After estimating the coefficients of the quadratic, only need to perform a grid search over one parameter, which A. We now illustrate this in detail for h = 1,2.
K.1 Illustration for 1:
For 1-step SD, we know that the (x(es)) AÇ2 + 2BC C for unknown A, C (that depend on X). Training 3 specific 1-step SD estimators, with ç = {-1,0, 1}. and measuring each of those estimators' Risk on the validation set, lets us estimate A, B, C. We then know that E* - B/a, for the chosen value of X.
K.2 Illustration for l = 2
E1
E
So
S
S₂
Figure 9: Illustrating 2-step SD.
28

---

For 2-step SD, the ExcessRisk for chosen À has the following form
ExccesRRisk00A 5 = ACi + B& + 2C 2DE1 + 2E F
ER
where the reparametrization is E + (1 - E1), and E + εσL1 (refer to Appendix C.3 for details on this reparametrization). Let (V {i) denote the result measuring this estimator's Risk on the validation dataset. We get the below system of equations.
F = EV = 0, = 0)
A + 2D F EVAL.(E = 1,51 = 0)
A 2D + F EVAL.(E2 = -1,5i 0)
B 2 F EVAL(E2 1. =
B - 2E + F EVAL(E2 = -1, =1)
4+
+ 2
+ D + = EVAL(E2 = 1,61 = 0.5)
4
The above EVAL operations help identify all the 6 unknown coefficients. Given AB C ([15)), we will have the below Ei E minimizing the test loss (i.e. giving the optimal 2-step SD coefs for the chosen A). And using them, we calculate the actual ÇT 52 by doing the inverse mapping the reparametrization.
CE CE-DB
CD - AE
AB C
AB C
Ç (51 + 42
$
Eع E
L Details on regression experiments
We note that all experiments run on a single CPU within 60 seconds (wall-clock time). We utilize sklearn's 's implementation of the RIDGE.
Methodology. We now explain our methodology in detail, which is followed for all datasets:
1. First, split the original dataset into three parts for a Train- Validation-Tess split. We divide all datasets 30 30 40 split. Note that 30% of the data suffices for training since work with small datasets which have d on the order of ten (and total number of samples n the order of thousands). For datasets that have temporal notion (e.g. date/timestamps), we do the three-way split sequentially.
2. Perform two standard transformations all three splits of the data: (i) Remove records with missing values, and (ii) coordinate-wist wise whitening for all X features and the target, i.e., subtracting the mean (computed the train set) and dividing by the standard deviation (also computed on the train set).
3. Select a grid of À values (and ensure that it is large enough so that the optimal À lies in it). The grid has factor of /10 difference between consecutive values (c.g., {1, v10, 10, -.. .10' ,104)) Then, for all À in the grid, compute:
The ridge estimator (()) using the train
The 1-step SD estimator ((A, (*) using the train set, where for each À is found using the validation set by the strategy described in Section 5.2.
The 2-step SD estimator (A,, (g(2))*) using the train set, where (g(²))* for each is found using the validation set by the strategy described in Appendix K.2.
Let Aj denote the optimal penalty for ridge that minimizes the MSE on the validation set. Similarly, let (*j and (Xī, (Ei, (E)) denote the optimal parameters for 1-step, 2-step SD, again chosen via the validation set.
4. Evaluate the MSE on the test set (unseen as yet) for all three computed estimators: ((2)). E().,5"), 0(Ag, (E1.E)) (5).
29

---

L.1 Description of the datasets used
UCI Air Quality. The UCI Air Quality dataset [34] contains records of hourly averaged readings from 5 metal oxide chemical sensors (which serve as covariates). along with ground-truth hourly averaged concentrations of the pollutants from co-located reference certified analyzer. The recordings are from an Italian city over a one year period in 2004-2005. After removing records with missing entries, this dataset has n 6941 rows and we consider d = 8 relevant covariates (5 values of the metal oxide chemical sensor readings + 3 values of Temperature, Relative Humidity, and Absolute Humidity). We explicitly mention the field names (all real-numbered non-negative).
X covariates' names in the dataset: [PT08.S1 .1 PT08. S2 (NMHC), PT08. S3 (NOx), PTO8. 54 (ND2), PTO8.55 (03), T, RH, AH]
Y target's name in the dataset: NO2 (GT)
UCI Airfoil Self-Noise. The UCI Airfoil Self-Noise dataset [5] contains data obtained from NASA's acrodynamic and acoustic tests of airfoil blade sections. It contains 5 real-valuee covariates, which are relevant physical quantities. The target is also veal-valued, which is the sound pressure created (in dB). There are no missing entries. This dataset has n 1503 rows and d = 5 covariates. We explicitly mention the field names:
X covariates' names in the dataset: [frequency, attack-angle, chord-length, free-stream-velocityy sictiionssid--dipllaeenen---- thickness]
Y target's name in the dataset: scaled sondd---uu---peusueee
UCI Appliances Energy Prediction. The UCI AEP dataset [6] contains energy appliances' data collected at 10 min frequency for about 4.5 months. This dataset has no missing entries, and a total of 19735 instances with 28 covariates. We downsample the dataset to hourly frequency, giving = 3290 rows with d = 24 relevant covariates (removing degenerate covariates: 'date', 'lights' 'windspeed', 'visiblity"), ) The full list of covariates is 24 long, and so we do not list out here (we already mentioned the 4 we removed from the total of 28).
L.2 Measuring the alignment between 0 and the eigenbasis directions for the datasets
The goal here to compute the alignment between the 0* and the eigenbasis directions {u;) /=1 for the three real-world datasets. The eigenspace U2 is known from the design matrix X. but 0 is unknown for real-world tasks. As proxy, use the ridge solution 0x (with small A).
Methodology of choosing A: We considered using the OLS solution êoLS == (XXT)-13 ''XY as the proxy for 8*, but (XXT) ) was numerically unstable for these datasets, so we instead used the ridge solution 8 with a small A. We calculated this À methodically for all datasets as a constant fraction of the sum of squared singular values. Explicitly, we (i) computed the SVD of the design matrix X, and (ii) set X == C. Σ arbitrarily (and the above trend is stable across other reasonably small values of C).
s? using the obtained singular values. The value C := 10-b was chosen
Figure 10 shows the result. The sum of all bars in single plot is one, since (u,)}=1 are unit-norm vectors that form an orthogonal basis of Rd, We infer two things. Firstly, for multi-step SD to outperform ridge (as is the case for the Air Quality and Airfoil datasets), 0* can be well-aligned with any of the J e [d]; not necessarily u₁ Secondly, this gives insight into why multi-step SD could not outperform ridge the AEP task (Table 1). Unlike the other two datasets, the 6 for the AEP dataset is not strongly aligned with any of the J E [d]. The top component in AEP only explains 35% of the total H* norm, whereas that number close to 80% for the Air Quality and Airfoil datasets. This indicates a large 8 value for the AEP dataset in Assumption 2.2.
L.3 Observed quadratic nature of MSE w.r.t. & parameters
In this section, we show that the optimal & values given in Table 1, selected via the strategy in section 5.2, are indeed the ones that minimize the validation MSE. By inspecting the minima of each of the curves in Figure 11, we observe that the values of g* for 1-step SD Table (found through the strategy described in section 5.2) indeed coincide with the minima producing values in the below curves. Further, Figure 1I empirically demonstrates the quadratic nature of risk (MSE) vs & described in Theorem 5.
30

---

16. unee petoy for
04
2.4
(b
(1.22...)))))
(a) Air Quality dataset (A 0.167)
(b) Airfoil dataset (A 0.023)
(c) AEP dataset (A 0.237)
Figure 10: The alignment 0 to the eigenbasis directions {u, [ for the three datasets used in the experiments. The low-alignment of 0* to any of the eigenbasis directions for the AEP dataset explains why SD provides no gain over ridge in the test set MSE values observed in Table 1. Details of the methodology used to compute the alignment provided in Appendix L.2.
Quality: Validation A
Alroll Valicadion NSE 109
=1025
0.5005
3.5
0.900
5
2
08
-10
05
30
(a) Quality dataset
(b) Airfoil dataset
(c) AEP dataset
Figure 11: Observed quadratic nature of MSE (on validation set) of 1-step SD E for À \1. This agrees with Theorem 5 and validates the hyperparameter tuning strategy outlined in section 5.2.
31

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
We present transparent top-level summary of all our results in the abstract and introduction.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Wherever applicable, limitations have been discussed (e.g. Remark 4.2).
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
32

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All theorems and lemmas have been stated with the precise assumptions used, and the Appendix provides all the proofs. Further, proof sketches and main ideas have been presented the main paper.
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced
statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Details of the experiments (dataset, methodology used) are provided in the main paper and in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
33

---

(c) If the contribution is a new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g.. to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: Our main contributions are theoretical results, however we plan to release relevant code github.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips) Sewiidees/CoeeSuuiissiiii.
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: //n //iips. wttp://cccpblccccucccceeeoo gwtp///ggui////eeeee / ssiniioisiiyyyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: We specify all relevant details in the paper (especially refer to Section 5.2 for how we exactly select our hyperparameters).
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail
that is necessary to appreciate the results and make sense of them.
34

---

The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: Since our experiments don't have randomized components (estimators have closed-form solution), we do not report error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror hars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful show in tables figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Our experiments are smaller scale and all experiments run on single CPU within minute. We mention this in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
35

---

Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neuripst http://wwww......o//occcccccaaaa
Question:
Answer: [Yes]
Justification:
We uphold the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification; Although our work is largely theoretical, does contribute to the understanding of self-distillation, and we mention potential societal impacts in the Conclusion section.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out, For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification:
This work poses such risk.
Guidelines:
The answer NA means that the paper poses such risks.
36

---

Released models that have high risk for misuse or dual-use use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We write our own code. All data used is indeed permissible to use for research purposes.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. condaataeess has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We don't 't release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
37

---

14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Not relevant.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to NeurIPS Code Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Not relevant.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
38


Reviews:
[{"review_id": "xiQdeTcXUv", "reviewer": "Reviewer_BMMQ", "summary": "This paper explores self-distillation from a theoretical perspective in the context of linear regression. Distillation is when a model is trained simultaneously to predict training labels and the predictions of another model that has already been trained on the data. Self-distillation is when the trained model has the same architecture as the model being trained. There has been recent work empirically show that self-distillation can result in better models and this paper gives a theoretical understanding of multi-step self-distillation in the context of linear regression.\n\nThe starting insight of the paper is that repeated self-distillation can be thought of as a pre-conditioner matrix multiplied by the optimal solution to ridge regression. Using this insight, they prove that there is a linear regression problem where self-distillation repeated r times (the rank of the data matrix) can outperform one-step self-distillation and ridge regression by a factor of r. They measure performance in terms of \"excess risk\" which is the distance to the optimal parameters under a norm weighted by the covariance matrix.\n\nTheir example with the factor of r gap requires two assumptions: all the singular values of the data matrix are distinct and the optimal parameters are orthogonal to all but one eigenvector. They show theoretically that both assumptions are necessary for such a gap to exist. They also derive an expression for the excess risk and conjecture that using more than r steps doesn't help the self-distillation process (as long as the self-distillation parameters are chosen optimally?).\n\nThey have some experiments where they show that 2-step self-distillation is robust to the ridge regression hyperparameter lambda. Because finding optimal parameters for self-distillation is difficult on real data, they do not show the performance of 3 or more -step self-distillation.", "questions": "* You show a gap between 1- and r-step self-distillation. Is there a similar gap between 2-step and r-step self-distillation? Based on your experiments, it looks like 2-step is already very good. Maybe this is a setting where 2-steps basically gives you all the power of r-steps like e.g., load balancing and the \"power-of-2 choices\".\n\n* You justify using excess risk because it \"ensures that the signal-to-noise ratio is uniform in all directions.\" I don't understand this and I don't see a direct relationship between excess risk and MSE. Could you please tell me why I should care about excess risk? And show me where it comes from theoretically?", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "* The paper begins with a nice insight into multi-step self-distillation and leverages it to prove several theoretical results.\n\n* The paper shows a very interesting gap in performance between r-step self-distillation and ridge regression and 1-step self-distillation.\n\n* The paper shows that two assumptions in the construction are necessary for the gap.\n\n* The paper shows in practice that 2-step self-distillation works very well.", "weaknesses": "Larger weaknesses:\n\n* The paper only shows results in terms of excess risk. I'm not familiar enough with the fixed design setup to determine how useful excess risk is.\n\n* The paper shows that r-step self-distillation can be very powerful but they give no way to practically run it i.e., choose the parameters on real data.\n\nSmaller points to improve:\n\n* I'm confused by the statement of Assumption 2.1. Shouldn't this say that the optimal parameter is orthogonal to every eigenvector *except* the first one?\n\n* More generally, I was confused about the way you stated the assumptions. You referred to two necessary assumptions which I assumed would be Assumption 1 and Assumption 2 but they were actually sub-assumptions in Assumption 2. I would ask that you rework what you call these assumptions and how you refer to them for clarity.\n\n* In your appendix, you referred back to equations in the main body without reproducing them. This made it annoying to check your work e.g., you compared equation 8 and 26 but I kept having to flip between them (until I eventually copied equation 8). Since there's no page limit in the appendix, I would appreciate if you reproduced all equations when you refer to them.\n\n* Your figures are difficult to read when printed out in black and white (and, I assume, for color blind people). Could you please change the marker for each line so they're more distinguishable?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging review! Let us try to resolve some of your questions and concerns.\n\n**Question 1: Gap between $2$-step SD and $r$-step SD** \n\nThe power of two choices in load balancing is related to two choices being the first non-trivial departure from the standard one choice algorithm. Qualitatively (and intuitively), that departure happens perhaps at $1$-step SD in our setting, where the self-distillation is first used. This is why we focused on the separation between $1$-step SD and $r$-step SD in our manuscript, along with the $0$-step (i.e. ridge) versus $r$-step SD. Quantitatively, it is challenging to quantify the gap between $k$-step SD and $r$-step SD for a *general* $k > 1$. Our educated guess is that the gap between each additional step of SD can be upto $O(1)$ (and accumulating the gains over $r$ steps gives an $O(r)$ total gain), but this is not currently proved.\n\nAs a proof of concept though, we refer you to Figure 2 of the rebuttal pdf, where we run $k$-step SD upto $k=5$ on a synthetic problem. We show that for that specific example, self-distillation beyond $2$-step SD is indeed helpful. In the real-world experiments, we ran only till $2$-step SD because $3$-step SD started becoming numerically unstable for all three of the datasets. \n\n**Question 2: Justification of using excess risk as the metric**\n\nIn linear regression literature, there are two reasons why excess risk in the $\\hat{\\Sigma}_n$-norm is the preferred metric. The first is that it corresponds to the **test error** on a fresh sample, which is typically the evaluation metric of choice in many settings. The second is that it is **invariant** to the basis of the input $x$. We explain each of these reasons in detail below.\n\n*Test error calculation*\n\nIn many cases, we care about the average test error, i.e. the expected error incurred on a fresh sample drawn from the underlying joint distribution $P$. Let's write that mathematically,\n\\begin{align}\n    {\\rm TotalRisk} (\\hat{\\theta}) &= \\mathbb{E}_{(x,y) \\sim P} \\left[ \\left( \\langle \\hat{\\theta}, x\\rangle - y\\right)^2 \\right] .\n\\end{align}\n\nWe first break the joint expectation into a conditional expectation on $y \\sim P_{Y|X=x}$ followed by $x \\sim P_X$.\n\nFrom Assumption 1 of the paper, we know that $P_{Y|X=x}$ is a distribution with mean $\\langle \\theta^\\star, x \\rangle$ and variance $\\gamma^2$. So we can write that that $y = \\langle \\theta^\\star, x \\rangle + \\eta$, where $\\eta$ denotes the noise and satisfies $\\mathbb{E}[\\eta]=0, {\\rm Var}[\\eta] = \\gamma^2$. Using this in the total risk expression, we get\n\\begin{align}\n    {\\rm TotalRisk} (\\hat{\\theta}) &= \\mathbb{E}_{x \\sim P_X} \\left[ \\langle \\hat{\\theta} - \\theta^\\star, x \\rangle^2 + \\gamma^2 \\right] .\n\\end{align}\n\nThis simplifies to\n\\begin{align}\n    {\\rm TotalRisk} (\\hat{\\theta}) &= \\left( \\hat{\\theta} - \\theta^\\star \\right)^\\top \\mathbb{E}_{x \\sim P_X} \\left[ xx^\\top \\right] \\left( \\hat{\\theta} - \\theta^\\star \\right) + \\gamma^2 \\text{ }.\n\\end{align}\n\nSince $P_X$ is the density with point masses at the $n$ training points in the fixed design setting, we get $\\mathbb{E}_{x \\sim P_X} \\left[ xx^\\top \\right] = \\frac{1}{n} \\cdot \\mathbf{X} \\mathbf{X}^\\top = \\hat{\\Sigma}_n$. Using this, we obtain\n\n\\begin{align}\n    {\\rm TotalRisk} (\\hat{\\theta}) &= || \\hat{\\theta} - \\theta^\\star ||^2_{\\hat{\\Sigma}_n} + \\gamma^2 \\text{ }.\n\\end{align}\n\nThe above calculation shows that excess risk in the $\\hat{\\Sigma}_n$-norm (i.e. the first term) is the right metric that determines how good an estimator is, above the \"*noise floor*\" of $\\gamma^2$. We remark in Appendix B that some previous works have used the $\\ell_2$-norm instead of the more natural $\\hat{\\Sigma}_n$-norm.\n\n*Invariance*\n\nAnother reason is that we prefer a measure of performance that is invariant to what basis we choose for the input $x$. Precisely, we want the performance of an algorithm to be the same whether we apply it to data coming from $(\\mathbf{X}, \\theta^\\star)$ or $(A \\mathbf{X}, A^{-\\top}\\theta^\\star)$ for any $d\\times d$ invertible matrix $A$. This follows from the fact that one can always apply any $A$ to the input before feeding it to the algorithm, and if the performance changes based on $A$, then it makes it hard to draw a fair comparison. We are assuming there is no numerical instability to focus on the **invariance property**. It happens that the excess risk $|| \\hat{\\theta} - \\theta^\\star ||^2_{\\hat{\\Sigma}_n}$ is invariant to such matrix multiplication (which is the change and/or scaling of the basis). We believe this is also one of the reasons excess risk in the $\\hat{\\Sigma}_n$-norm is preferred over the $\\ell_2$ distance. This is what we meant when we said \"*ensures that the signal-to-noise ratio is uniform in all directions*.\"\n\n**Larger weaknesses**\n\n1. Please see the above justification for using excess risk as the metric.\n2. **There is a one-shot tuning method we explain in Section 5.2 (and Appendix K)**, where we delineate a principled hyperparameter selection method for the $\\xi$ parameters, leveraging the theoretical insights from section 4.4. In particular, from Theorem 5 in section 4.4, we know that the excess risk is quadratic in the $\\bar{\\xi}$ parameters (one-to-one reparameterization of the $\\xi$ parameters). Using the quadratic nature, one can evaluate optimal $\\xi$s for any regularization strength $\\lambda$, leaving only one parameter ($\\lambda$) for the grid search. \nIn practice, what was challenging for higher $k$-step SD ($k>2$) was numerical instability. In particular, from Theorem 5 we know that the optimal choice of $\\xi$ would involve computing $M^{-1}$ for the matrix $M \\in \\mathbb{R}^{k \\times k}$, which was unstable to invert for $k > 2$ in the real-world datasets of Section 5.3. There might be more stable ways to approximate the optimal solutions, which will make our approach more practical for higher order SD. We leave this as a future research direction.", "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": "", "extra_scores": {}}, {"review_id": "IVIdZLv0sl", "reviewer": "Reviewer_tBMq", "summary": "The paper tries to provide a theoretical analysis of gains from applying self-distiliation repeatedly, in particular by trying to show that it is important to optimally set the imitation paramter for each step rathen than having a fixed Value. The study is conducted on using ridge estimator for linear regressin. The authors provide a theorm on the excess risk under two assumption when multi-step SD is applied. Experimental results on synthetic data and thre real world datasets. The paper also provides insights on how to set the imitation pramter real datasets.", "questions": "- Can the authors provide any thoughts on how/challenges of expanding the analysis into more complex family of models?\n- How does the Assumption 2.2 can be interpreted as constraints on more complex models, for example for MLPs?\n- What could be the reason for drop in performance for AEP?", "limitations": "The theoretical analysis is limited in the scope of models and it is not immediately clear how it can be extended into more expressive models. Furthermore, it is not straightforward to incorporate them on large problems by optimally setting hyperparameters.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Along with the theoretical analysis, the authors provide experimental results to demonstrate the necessity of the two major assumptions they have for the theoretical gain bounds they show. The analysis on importance of properly choosing imitation factor at each step and how it relates to excess risk is insightful. The problem setting, although simplified, but is straightforward to understand and the idea and analysis is well presented.", "weaknesses": "The paper does not provide neither discussion nor experiments on how the proposed analysis can be used in more complex setting (e.g. more expressive models). On the other hand, for the experimental results the author do not provide any insight into why on AEP dataset using multi-step SD degrades the results. Could it be due to violation of the assumptions? \nIn general, the paper provide theoretical analysis for a known technique without providing much insight into how one can use it to improve experimental work, for example it could have been more interesting if the authors could provide more principled techniques for hyperparameter setting for multi-step SD.  It would be more helpful if more experimental analysis on either more datasets or in depth were conducted.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review! We address your questions and concerns below.\n\n**Question 1: Analysis of a more complex model family**\n\nWe understand that linear regression is a relatively simple task, but we believe that the $\\Omega(r)$ order-wise separation between $r$-step SD and $1$-step SD, although in the simple framework of linear regression, is an interesting and perhaps surprising result. \n\nOn extensions, kernel regression is a fairly direct extension in terms of technical tools. The challenge for more expressive models (eg. MLPs) is the introduction of $(i)$ non-linearity and $(ii$) non-convexity, which pose significant additional technical challenges for theoretical analysis. The solution of the ERM problem becomes hard to characterize. Further, there is interplay with optimization since the objective can become non-convex.\n\nBecause of these difficulties, researchers generally resort to empirical studies for more complex models. Many past works have observed the phenomenon of multi-step SD providing performance gains in various settings [1,2,3]. Our work is an attempt to theoretically characterize the gain, and it's somewhat surprising that linear regression itself exhibits a non-trivial order-wise gain from self-distillation.\n\n```\n[1] T. Furlanello, Z. Lipton, M. Tschannen, L. Itti, and A. Anandkumar. Born again neural networks. In International Conference on Machine Learning, pages 1607–1616. PMLR, 2018.\n[2] Y. Li, J. Yang, Y. Song, L. Cao, J. Luo, and L.-J. Li. Learning from noisy labels with distillation. In Proceedings of the IEEE international conference on computer vision, pages 1910–1918, 2017.\n[3] Z. Zhang and M. Sabuncu. Self-distillation as instance-specific label smoothing. Advances in Neural Information Processing Systems, 33:2184–2195, 2020.\n```\n\n**Question 2: Interpretation of Assumption 2.2 in more complex models**\n\nAt a high-level, $\\theta^\\star$ is akin to the parameterization of the ground-truth generative process (which could be non-linear in general). And $\\mathbf{u}_j$ is akin to a basis direction of the observed data (which is computed simply via SVD for the linear case, but the notion of basis could involve non-linearity for more general models). These notions are far from precise though, and it is not clear what the interpretation of their \"closeness\" (as in Assumption 2.2) would mean in a more complex regime. Characterizing this more explicitly would be a very interesting direction of future work, but falls outside the scope of our current work.\n\n**Question 3: Insight into performance on the AEP dataset**\n\nNote that $\\{1, 2\\}$-step SD achieve roughly the same test MSE as ridge on the AEP dataset (Table 1 of manuscript), so there is *no drop* in performance, it's just flat. In the attached pdf (Figure 1), we provide an explanation for why this is the case. Unlike the other two datasets, AEP happens to have a $\\theta^\\star$ which is not strongly aligned with any particular basis direction $\\mathbf{u}_j, j \\in [d]$. This violates Assumption 2.2, where we require $\\theta^\\star$ to be well-aligned with one of the $\\mathbf{u}_j$ directions for observing large gains from multi-step SD.\n> Please also refer to the shared response for a detailed discussion on Assumption 2.2. In particular, we present a relaxed version of Theorem 1 where $\\theta^\\star$ needs to be closely (and *not just exactly*) aligned with *any* of the $\\mathbf{u}_j$, and not necessarily $\\mathbf{u}_1$.\n\nTo be more explicit, let us break it into two cases:\n- **Case 1:** From the new version of Theorem 1, we know that closeness of $\\theta^\\star$ to some $\\mathbf{u}_j, j \\in [d]$ (which translates to the existence of one high peak in the Figure 1 bar chart) implies large gains from self-distillation.\n- **Case 2:** On the other hand, from Theorem 3 of the manuscript, we know that if $\\theta^\\star$ is equally aligned to all of $\\mathbf{u}_j$s (which translates to a flat distribution in the Figure 1 bar chart), it provably implies no gain from self-distillation.\n\nSince the AEP dataset happened to be closer to the second case, we see no gains from self-distillation. We thank you for this suggestion, and will aim to include this explanation in the revised manuscript.\n\n**Other Concerns: Hyperparameter selection**\n\nThe comments also raised a concern about principled hyperparameter selection methods. We would like to highlight that *there is a principled one-shot tuning method we explain in Section 5.2 (and Appendix K) for the $\\xi$ parameters*, leveraging the theoretical insights from section 4.4. In particular, from Theorem 5 in section 4.4, we know that the excess risk is quadratic in the $\\bar{\\xi}$ parameters (one-to-one reparameterization of the $\\xi$ parameters). Using the quadratic nature, one can evaluate optimal $\\xi$s for any regularization strength $\\lambda$, leaving only one parameter ($\\lambda$) for the grid search.", "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": "", "extra_scores": {}}, {"review_id": "siHiXfcH4P", "reviewer": "Reviewer_2wSn", "summary": "The paper analyzes the gains a model can achieve from multi-step self-distillation and presents a solid theory showing that the excess risk does not increase with more self-distillation steps. The synthetic task in the paper effectively proves this analysis.", "questions": "1) Please address the weaknesses mentioned.\n\n2) What networks are used in the experiments?", "limitations": "Yes, imitations have been discussed.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) The analysis of excess risk for the model trained with multi-step self-distillation is solid.\n\n2) The synthetic task and experiments on the Air Quality, Airfoil, and AEP datasets well support the proposed theory.\n\n3) The paper is well-written and easy to follow.", "weaknesses": "1) The study of self-distillation has already been explored in [1,2]. [1] shows that any distillation step can be calculated directly from the initial distillation step. Can the authors compare to [1]? In the experiments of [1], it is shown that accuracy does not always increase with more self-distillation steps. In this paper, the experiments only show results for 2-step self-distillation. How about more steps, like 5 or $\\frac{r}{2}$? The datasets used in the experiments do not seem to be widely used. How about results on widely used datasets like CIFAR-10?\n\n2) Assumption 2 is not guaranteed in real tasks. As shown in Figure 2(c), the proposed analysis heavily relies on Assumption 2.2. However, Assumption 2.2 does not seem to be satisfied in real tasks, which weakens the proposed analysis.\n\n3) The experiments are not sufficient to support the proposed theory.\n\n[1] Kenneth Borup and Lars N.Andersen. Even your Teacher Needs Guidance: Ground-Truth Targets Dampen Regularization Imposed by Self-Distillation. In Advances in neural information processing systems, 2020\n\n[2] Rudrajit Das, Sujay Sanghavi. Understanding self-distillation in the presence of label noise. In Proceedings of the 40th International Conference on Machine Learning, 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review! We address your concerns and questions below.\n\n**Concern #1.1: Comparison to another relevant paper [1]**\n\nSelf-distillation has been explored in [1,2,3], and we do provide a  comparison of our results with [2,3]. Thank you for pointing out the highly relevant reference [1] also! There are definitely similarities, but the main conclusions do differ. Let us elaborate more below.\n\nIndeed [1] also studies multi-step SD similar to us (Fig 1 in both papers are analogous), and they also obtain an analytical form for the k-step SD (Theorem 4.1 in theirs is analogous to Eq. (8) in ours). \n\nThe crucial difference is the freedom of the $\\xi$ parameters being different at each step of self-distillation. In Lemma 4.2 and Theorem 4.3, [1] assumes the $\\xi$ values at each step are equal (denoted $\\alpha^{(2)} = \\alpha^{(3)} = \\cdots = \\alpha^{(\\tau)}$ in their paper). Consequently, they conclude that subsequent steps of SD progressively sparsify the basis set of obtainable solutions. This means that after a point, running more steps of SD will result in a poorer performing model (similar to [3]), as you pointed out in your review.\n\nOur main result (Theorem 1) is different. It says that subsequent steps of SD strictly provide more freedom, and that the best multi-step SD can outperform the best 1-step SD by an $\\Omega(r)$ factor. This separation relies on the freedom of $\\xi$s being different at each step, which required careful analysis.\n\nWe believe this is a significant novel contribution since an order-wise separation of $\\Omega(r)$ (and not just an $O(1)$ difference) is somewhat surprising. But we will surely cite the contributions of [1] as they are highly relevant.\n\n```\n[1] Kenneth Borup and Lars N.Andersen. Even your Teacher Needs Guidance: Ground-Truth Targets Dampen Regularization Imposed by Self-Distillation. In Advances in neural information processing systems, 2020.\n\n[2] Rudrajit Das and Sujay Sanghavi. Understanding self-distillation in the presence of label noise. In Proceedings of the 40th International Conference on Machine Learning, 2023.\n\n[3] Hossein Mobahi, Mehrdad Farajtabar, and Peter Bartlett. Self-distillation amplifies regularization in hilbert space. In Advances in Neural Information Processing Systems, 2020.\n```\n\n\n**Concern #1.2: $k$-step SD for $k>2$**\n\nIn the regression tasks of Section 5.3, what was challenging for higher $k$-step SD ($k>2$) was numerical instability. In particular, from Theorem 5 we know that the optimal choice of $\\xi$ involves computing $M^{-1}$ for the matrix $M \\in \\mathbb{R}^{k \\times k}$, which was unstable to invert for $k > 2$ in the real-world datasets of Section 5.3. There might be more stable ways to approximate the optimal solutions, which will make our approach more practical for higher order SD. We leave this as a future research direction. \n\nAs a proof of concept though, we refer you to Figure 2 of the rebuttal pdf, where we run $k$-step SD upto $k=5$ on a synthetic problem. We show that for that specific example, self-distillation beyond $2$-step SD is indeed helpful. In the real-world experiments, we ran only till $2$-step SD because $3$-step SD started becoming numerically unstable for all three of the datasets. \n\n**Concern #2: Assumption 2.2 being too strong**\n\nWe agree that Assumption 2.2 as presented is indeed a strong condition, but we do not really need that strong condition to see the gains of multi-step SD. Let us elaborate why:\n\n1. *Theoretical argument:* In general, we require significantly weaker conditions on $\\theta^\\star$ for the separation result (Theorem 1). This is clarified in great detail in the shared response (since this was a common concern among reviewers), where we (i) note that alignment with *any* one of $\\mathbf{u}_j, j \\in [r]$ is sufficient for the separation, and (ii) also present a relaxed version of Theorem 1 with a weaker Assumption 2.2 that does not require *exact* alignment. Please refer to the shared response window for a full discussion.\n3. *Empirical argument:* The relaxed condition of Assumption 2.2 is fairly reasonable, as shown empirically on the Air Quality and Airfoil regression tasks, where $2$-step SD beats $\\{1,0\\}$-step SD (especially Air Quality where the gap in performance is significant). We included AEP dataset as a negative example where multi-step SD does not provide gains. Further, Figure 2 of the rebuttal pdf provides insight into why AEP saw no gains. It shows that the $\\theta^\\star$ is indeed strongly aligned with one of the $\\mathbf{u}_j, j \\in [d]$ for Air Quality and Airfoil datasets, but *NOT* for the AEP dataset.\n\nWe presented Assumption 2.2 as such in the interest of a clean exposition of Theorem 1. At the time of writing, the focus was on showing that there exists *a* regime where $r$-step SD can order-wise outperform $1$-step SD (i.e., not just by a $O(1)$ factor). But the above shows, both theoretically and empirically, that multi-step SD can provide gains in much more general settings.\n\n**Question #2: Models and datasets used**\n\nSince our setting is regression, CIFAR-10 is a less relevant dataset for us. We demonstrate the empirical results on regression datasets taken from the commonly used UCI repository. The experiments presented are for linear estimators of the type $\\hat{\\theta} \\in \\mathbb{R}^d$. Non-linear networks were not used to keep the experiments in accordance with the theory.", "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": "", "extra_scores": {}}, {"review_id": "pCXu7cH50F", "reviewer": "Reviewer_Uvvg", "summary": "This paper theoretically investigates the effect of multiple rounds of self-distillation (SD) in linear regression. Under some conditions on the ground truth model $\\theta^{\\ast}$ and the data matrix $X$, it is shown that multi-step SD can improve the risk bound by a factor of $r = \\text{rank}(X)$. Specifically, this happens when the non-zero singular values of $X$ are all distinct and when $\\theta^{\\ast}$ is *perfectly* parallel to $u_1$, where $u_1$ is the leading singular vector of $X$. The authors show the necessity of such conditions. The improvement yielded by multi-step SD is demonstrated empirically on some simple regression tasks.", "questions": "Please see Weakness #1.", "limitations": "Not discussed in detail.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "**1.** This paper seems to be one of the first ones to theoretically characterize *multi-step* SD. \n\n**2.** The paper is more or less well-written.", "weaknesses": "**1.** The condition of $\\theta^{\\ast}$ being *perfectly* parallel to $u_1$ is too strong and unrealistic in my opinion. This makes the results of this paper less interesting. A better result would be quantifying the gains of multi-step SD assuming the angle between $\\theta^{\\ast}$ and $u_1$ is bounded by some quantity, say $\\beta$ -- this is a more realistic setting. Then, focus on the special case of $\\beta$ being small (and so $\\beta = 0$ would be a very special case of these general results). Is it possible to do something like this?\n\n**2.** There are no practically relevant insights for multi-step SD in classification problems which are more interesting now.\n\n**3.** Overall, I'm not sure about the relevance of the results in this paper due to the above two points.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. We address your concerns below.\n\n**Concern 1: Relaxing the strong assumption of $\\theta^\\star$ being perfectly parallel to $\\mathbf{u}_1$**\n\nRegarding the condition of $\\theta^\\star$ being perfectly parallel to $\\mathbf{u}_1$, we address this in the shared response, since this was a common concern among reviewers. We agree that it is a strong assumption -- and we presented it as such in the interest of a clean exposition of Theorem 1. At the time of writing, the focus was on showing that there exists *a* regime where $r$-step SD can order-wise outperform $1$-step SD (i.e., not just by a $O(1)$ factor).\n\nBut the result does hold true more generally. This is clarified in detail in the shared response via the below two arguments, and a new version of Theorem 1 that incorporates both of these points. \n- First, we note that alignment with *any* one of $\\mathbf{u}_j, j \\in [r]$ is sufficient for the separation (as noted in lines 203-205 in the manuscript also). \n- Second, based on your valuable recommendation, we have indeed derived a version of Theorem 1 with a relaxed Assumption 2.2, where the closeness of $\\theta^\\star$ and the singular vector $\\mathbf{u}_j$ is controlled with a parameter $\\beta$, and setting $\\beta = 0$ recovers the special case that we presented. \n\nThrough the revised Theorem 1, we argue that the regime of separation is more than just an atypical corner case. Overall, we show that the separation holds whenever the ground-truth $\\theta^\\star$ is \"$\\beta$-close\" to any of the $\\mathbf{u}_j, j \\in [r]$; and for small $\\beta$. We believe this is a fairly general regime and not just a special case. We hope this provides resolution for your concern.\n\n\n**Concern 2: Insights for self-distillation applied to classification**\n\nWe understand that linear regression is a relatively simple task, but we believe that the $\\Omega(r)$ order-wise separation between $r$-step SD and $1$-step SD, although in the simple framework of linear regression, is a somewhat surprising result worth sharing with the community.\n\nThe de-facto loss for classification problems is the cross-entropy loss, which introduces non-linearity and additional technical challenges for theoretical analysis. But practically, there's a large body of work on empirically analyzing multi-step SD in classification problems. Many researchers have observed the phenomenon of multi-step SD providing performance gains in various settings [1,2,3]. Our work is an attempt to theoretically characterize the gain, and it's surprising that linear regression itself exhibits a non-trivial gain from self-distillation. A detailed analysis for classification with non-linearity falls outside the scope of this work.\n\n```\n[1] T. Furlanello, Z. Lipton, M. Tschannen, L. Itti, and A. Anandkumar. Born again neural networks. In International Conference on Machine Learning, pages 1607–1616. PMLR, 2018.\n[2] Y. Li, J. Yang, Y. Song, L. Cao, J. Luo, and L.-J. Li. Learning from noisy labels with distillation. In Proceedings of the IEEE international conference on computer vision, pages 1910–1918, 2017.\n[3] Z. Zhang and M. Sabuncu. Self-distillation as instance-specific label smoothing. Advances in Neural Information Processing Systems, 33:2184–2195, 2020.\n```", "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": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their feedback and valuable comments. Multiple reviewers (Uvvg, 2wSn) have raised **concerns about Assumption 2.2 being too strong**, which we address in this shared response. We want to emphasize two points. 

- First, as we point out in lines 203-205 in the manuscript, Theorem 1 holds as is for a larger class of problems where $\theta^\star$ is perfectly parallel to *any* one of $\mathbf{u}_j, j \in [r]$. We stated Assumption 2.2 only for $\mathbf{u}_1$ because we viewed it as a lowerbound result. That is, the focus was on showing that there exists *a* regime where the $\Omega(r)$ separation holds. Now that we realize that the result should be stated more generally, we present the following version (to be added in the revised manuscript). This version is stated for any $\mathbf{u}_j$ instead of just $\mathbf{u}_1$.
- Second, we have a new theorem capturing the dependence on the angle between $\theta^\star$ and the most aligned singular vector. Based on a suggestion from the reviewers, we generalize to the case where the angle $\measuredangle (\theta^\star, \mathbf{u}_j)$ for the most aligned $j\in[r]$ is controlled with a parameter $\beta$, instead of the angle being exactly zero. We present the following version of Theorem 1 with a relaxed Assumption 2.2 (that incorporates $\beta$), and Assumption 2.1 staying the same. This will also be added to the revised manuscript. Note that setting $\beta = 0$ exactly recovers the original claim. 

We agree that the condition of $\theta^\star$ being perfectly parallel to $\mathbf{u}_1$ was indeed a strong assumption. As mentioned, the focus was on showing *a* regime of separation. Through the above two points (both incorporated in the new theorem below), we argue that the regime of separation is more than just an atypical corner case. Overall, we show that the separation holds whenever the ground-truth $\theta^\star$ is "$\beta$-close" to any of the $\mathbf{u}_j, j \in [r]$; and for small $\beta$. We believe this is a fairly general regime of problem instances.

---

**Assumption 2'**

2'.1 No two non-zero singular values of $\mathbf{X}$ collide, i.e. $s_1 > s_2 > \cdots > s_r > 0$.

2'.2 For some $\beta \in [0, 1)$, there exists an index $j \in [r]$ such that $\langle \theta^\star, \mathbf{u}_j \rangle^2 \geq (1 - \beta) \cdot || \theta^\star ||^2$.

**Theorem 1'**

Under the fixed design linear regression in Assumption 1, there exists a family of problem instances satisfying Assumption 2' such that for any instance $(\mathbf{X}, \theta^\star, \gamma^2)$ in the family, it holds that
\begin{align}
    \exists \lambda > 0, \exists \xi^{(r)} \in \mathbb{R}^r, \hspace{10pt} &{\rm ExcessRisk} \left( \hat{\theta} (\lambda, \xi^{(r)}) \right) \leq \frac{\gamma^2}{n} \cdot \left( 1 \textcolor{red}{ + \beta \text{ } \frac{ || \theta^\star ||^2 s_1^2}{\gamma^2}} \right) , \newline
    \forall \lambda > 0, \forall \xi \in \mathbb{R}, \hspace{10pt} &{\rm ExcessRisk} \left( \hat{\theta} (\lambda, \xi) \right) \geq  \textcolor{red}{(1 - \beta)} \left( \frac{0.99}{2^{9}} \right)  \frac{r\gamma^2}{n} \text{ } , \text{ and } \newline
    \forall \lambda > 0, \hspace{10pt} &{\rm ExcessRisk} \left(\hat{\theta} (\lambda) \right) \geq \textcolor{red}{\left( \frac{1 - \beta}{1 - 0.99 \beta} \right)^2} \left( 0.98 \right)  \frac{r \gamma^2}{n} \text{ } ,
\end{align}
where $r:={\rm rank}(\mathbf{X})$, $n$ is the number of samples, $\hat{\theta}(\lambda,\xi^{(r)})$ and $\hat{\theta}(\lambda,\xi)$ are the $r$-step and $1$-step SD estimators defined in Eqs. (8) and (4) respectively, and $\hat{\theta}(\lambda)$ is the ridge estimator defined in Eq. (3).

---

In this relaxed version, there is an $\Omega(r)$ separation between $r$-step SD and ${1,0}$-step SD in the small $\beta$ regime. In particular, if $\beta$ is $O\left( \frac{\gamma^2}{ || \theta^\star ||^2 s_1^2} \right)$ (which resembles the inverse signal-to-noise ratio) and $\beta << 1$, then $r$-step SD can significantly outperform $1$-step SD. 

The proof of this follows the same structure as the proof of Theorem 1 in the paper, with relevant tracking of the inner products $\langle \theta^\star, \mathbf{u}_l \rangle$ for $l \in [r]$. 
- Earlier, we had $\langle \theta^\star, \mathbf{u}_1 \rangle^2 = || \theta^\star ||^2$, which changes to $\exists j\in[r]$, $\langle\theta^\star,\mathbf{u}_j\rangle^2\geq(1-\beta)\cdot||\theta^\star||^2$.
- And we had $\langle\theta^\star,\mathbf{u}_l\rangle=0$ for $l\geq2$, which changes to condition (C).

Here (C) is $\sum_{l=1,l\neq j}^r\langle\theta^\star,\mathbf{u}_l\rangle^2\leq\beta\cdot||\theta^\star||^2$. It is worth noting that the bounds in the theorem are tight only in the small $\beta$ regime. As $\beta$ increases above zero, the upper bound and both lower bounds become more loose.

We again thank the reviewers for the valuable suggestion regarding $\beta$-controlled analysis. We hope the above discussion provides some resolution. We will include this generalized version of the result in the revised manuscript.

**Brief note on the attached pdf**

We also upload a 1-page pdf containing two figures. 
- Figure 1 is in response to a question from reviewer tBMq about why self-distillation does not provide improvement over ridge on the AEP dataset (Table 1 of the manuscript). We show that unlike the other two datasets, the $\theta^\star$ for AEP is not well-aligned with any of the bases directions $\mathbf{u}_j, j \in [d]$. 
- Figure 2 is in response to a question from reviewers BMMQ and 2wSn about the gain from $k$-step SD for $k > 2$. We run upto $5$ steps of self-distillation on a synthetic problem and show that the relative performance gain of $k$-step SD increases beyond $k = 2$ also.

Meta-review: The authors provide a theoretical analysis of repeated (multi-step) self-distillation. This is a variation of the standard distillation setting where labels from a teacher model are used to augment the standard training objective; but this distillation is iterated for several rounds (i.e., distilled students become teachers for the next round of distillation.) For the simplified setting of ridge regression (along with additional assumptions), the authors show that if r is the rank of the data matrix, repeated self-distillation outperforms standard ridge regression by a factor of r.

The overall result is nice and rests on somewhat interesting connections between repeated self-distillation and matrix pre-conditioning in ridge regression. The authors also do a good job in justifying their additional assumptions. The major limitation (of course) is that distillation is usually done for much more complicated models and for typically classification using the cross-entropy loss, so it is as yet an open question whether any of the theoretical insights carry over to practice.
Decision: Accept (poster)