High-dimensional Analysis of Knowledge Distillation: Weak-to-Strong Generalization and Scaling Laws
Authors: Muhammed Emrullah Ildiz
Halil Alperen Gozeten
Ege Onur Taga
Marco Mondelli
Samet Oymak
Venue: ICLR 2025 Spotlight (2025)
Keywords: empirical risk minimization
high-dimensional statistics
scaling laws
weak to strong generalization
knowledge distillation
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: This paper provides a sharp characterization of a two-stage learning process, where the first-stage (surrogate) model's output supervises the second stage, thus revealing the form of optimal surrogates and when it is beneficial to discard features.

Abstract: A growing number of machine learning scenarios rely on knowledge distillation where one uses the output of a surrogate model as labels to supervise the training of a target model. In this work, we provide a sharp characterization of this process for ridgeless, high-dimensional regression, under two settings: *(i)* model shift, where the surrogate model is arbitrary, and *(ii)* distribution shift, where the surrogate model is the solution of empirical risk minimization with out-of-distribution data. In both cases, we characterize the precise risk of the target model through non-asymptotic bounds in terms of sample size and data distribution under mild conditions. As a consequence, we identify the form of the optimal surrogate model, which reveals the benefits and limitations of discarding weak features in a data-dependent fashion. In the context of weak-to-strong (W2S) generalization, this has the interpretation that *(i)* W2S training, with the surrogate as the weak model, can provably outperform training with strong labels under the same data budget, but *(ii)* it is unable to improve the data scaling law. We validate our results on numerical experiments both on ridgeless regression and on neural network architectures.

Published as conference paper at ICLR 2025
HIGH-DIMENSIONAL ANALYSIS OF KNOWLEDGE DISTILLATION: WEAK-TO- GENERALIZATION AND SCALING LAWS
M. Emrullah Ildiz'
Halil Alperen Gozeten' Ege Onur Taga
University of Michigan, Ann Arbor
{eildiz, alperen, egetaga)@umi ch. edu
Marco Mondelli
Samet Oymak"
Institute of Science and Technology Austria harco.mondee wi@ist..c..........
University of Michigan, Ann Arbor oymakθumi ch. edu
ABSTRACT
growing number of machine learning scenarios rely on knowledge distillation where one uses the output of a surrogate model as labels to supervise the training of target model. this work, we provide sharp characterization of this process for ridgeless, high-dimensional regression, under two settings: (i) model shift, where the surrogate model is arbitrary, and (ii) distribution shift, where the surrogate model the solution empirical risk minimization with diito---ittirbution data. In both cases, characterize the precise risk of the target model through non-asymptotic bounds in terms of sample size and data distribution under mild conditions. As consequence, we identify the form of the optimal surrogate model, which reveals the benefits and limitations of discarding weak features in a data-dependent fashion. In the context of weak-to-strong (W2S) generalization, this has the interpretation that (i) W2S training, with the surrogate as the weak model, can provably outperform training with strong labels under the same data budget, but (ii) it unable improve the data scaling law. We validate our results on numerical experiments both on ridgeless regression and on neural network architectures.
INTRODUCTION
The increasing number and diversity of machine learning models has motivated the development of techniques that leverage the output of one model to train a different one a process known as knowledge distillation (Hinton et al., 2015). Variations of this approach include generating synthetic data from powerful language models (Wang et al., 2023; Gunasekar et al., 2023; Abdin et al., 2024), weak-to-strong generalization to obtain stronger models under weak supervision (Burns al., 2023), and filtering/curating ML datasets via smaller model to train a larger model (Fang et al., 2023; Lin et al., 2024b). The diversity of these applications motivates deeper understanding of the statistical properties and limits of the distillation process.
In this work, we focus on the scenario where target/student model is trained on the labels of a surrogate/teacher model. Let D, denote the target distribution, (x; y:) be sampled i.i.d. from this distribution, and p denote the dimension of the features x; Given a surrogate model we create the synthetic labels y s(x;) and obtain the target model by minimizing the empirical risk, i.e.,
Σ lml
= arg min feF
where denotes the hypothesis class and & the loss function. This procedure motivates few fundamental questions regarding (1): (i) What is the excess risk of f compared to that of the minimizer of the population
"Equal Contribution
"Equal Advising

---

Published as a conference paper at ICLR 2025
0.16
Torget Risk
7 =11-
Empirical larget
4
2-
0.14
Optimal Masked Surrogate to To-Target Risk
Empirical Optinal Masked Surroaaeeto-Targe Risk
True P.
0.12
Optimal Surrogate to-Target Risk
3
Optimal Masked Surrogate Model
Test Risk
0.10
Empirical Optimal Surrogate-to to-Taiget Risk
Optimal Surrogate Model
12
2-
0.06
1-
0.04
0.02
0-
0.00
100
400
500
Index / (ordered in decreasing eigenvalues)
Sample Size (n)
(a) Ground-truth and surrogate model weights
(b) Test risks as function of sample size
Figure I: Structure and performance of optimal surrogate models. (a): We compare the weights of the optimal surrogate model (green) with the ground-truth (blue). This reveals a transition from amplification to shrinkage as we move from principal to tail eigenvalues. The yellow curve displays the optimal 0-1 masking of the ground-truth where we either keep or discard feature. (h): Associated test risks as function of sample size. The theoretical bounds (full lines) match the experiments (markers). Setting: The feature size is p = 500; the sample size is 200 in (a) and variable in (b): the feature covariance follows the power-law structure A, =-2 A.8 = 115 <: is the covariance statistics (see Corollary 1) governing the optimal surrogate's 's structure.
risk f. = arg min Bug f(x)]? (ii) What is the optimal surrogate model s that minimizes such excess risk? (iii) Can the optimal strictly outperform using true labels y; or setting s = f. in (1)? Furthermore, in practice, itself is the outcome of an empirical risk minimization (ERM) procedure. Specifically, let D, be the surrogate distribution, (R,, 51) be sampled i.i.d. from D, (having feature dimension p), and assume
1 Σ (6..
== arg min JES m
where S denotes the surrogate hypothesis class. Thus, as a final (and more challenging question), one may ask: (iv) How do the sample sizes n, m and the data distributions D,, affect the performance of f?
Main contributions. We address these questions in the context of high-dimensional ridgeless regression, where F,S are the class of linear models and é is the quadratic loss. We provide a sharp non-asymptotic characterization of the test risk of f in two core settings:
1. The surrogate is provided and solve ff via (1), which addresses the first three questions above; 2. f is obtained via two stages of ERM, i.e., (2) followed by (1), which addresses the last question.
We focus on the regime where the sample sizes n, m and the feature dimension p are all proportional and also allow for a distribution shift between D, and D,, which correspond to the two ERM stages. Our theoretical guarantees in Section 3 precisely characterize the regression coefficients B, of the optimal surrogate model in terms of the corresponding coefficients B. of the population risk minimizer and the feature covariance. This is depicted in Figure Ia where B. and B, are displayed by blue and green curves, respectively. This unveils a remarkable phenomenology in the process of knowledge distillation, that can be described follows. Define the per-feature 'gain' of the optimal surrogate as gain = B./B. where the division is entrywise, which corresponds to the ratio between green and blue curves. We show that the gain vector is entirely controlled by the covariance statistics, denoted by (6))_ that summarize the role of feature covariance and finite sample size n in the test risk. There is well-defined transition point, 4 = 1 in Fig. 1a, where the gain passes from strict amplification (gain, > 1) to strict shrinkage (gain, 1) as we move from principal eigendirections to tail. Our theory also clarifies when we are better off discarding the weak features. The yellow curve shows the optimal surrogate when B, is restricted to be a 0-1 mask the entries of B. so that the surrogate has the direct interpretation of feature pruning. We show that beyond the transition point 2? - Ω truncating the weak features that lie on the tail of the spectrum is strictly beneficial to distillation. This masked surrogate model can be viewed as a weak supervisor as contains strictly fewer features compared to the target, revealing a success mechanism for weak-to-strong supervision.
2

---

Published as conference paper at ICLR 2025
Notably, as the sample size n decreases, the optimal surrogate provably becomes sparser (transition points shift the left) under a power-law decay covariance model. In Section 4, under this power-law model, we also quantify the performance gain that arises from the optimal surrogate and show that while the surrogate can strictly improve the test risk, it does not alter the exponent of the scaling law. This is depicted in Figure lb where the surrogate risks are smaller but behave similarly to the toound-truth. Finally, in Section 5, we study the more intricate problem of two-stage ERM ((2) followed by (1)) and establish a non-asymptotic risk characterization that precisely captures the influences of the sample sizes m, n and of the surrogate/target covariance matrices.
1.1 RELATED WORK
Our work relates to the topics of high-dimensional learning, distribution shift, scaling laws, and distillation.
High-dimensional risk characterization. There is large body of literature dedicated to the study of linear regression in over- and study the test risk and various associated phenomena, such as benign overfitting (Bartlett et al., 2020) or double descent (Belkin et al., 2019). Specifically, asymptotic and non-asymplotic risk characterizations for the minimum lz fo-norm interpolator (i.e., ridgeless regression with p 2 n) have been provided in a recent line of work (Hastie et al., 2020; Cheng & Montanari, 2024; Han & Xu, 2023; Wu & Xu, 2020; Richards et al., 2021; Loureiro et al., 2022).
regimes. Via random matrix theory tools, one can precisely
While the standard ERM formulation is well studied, the analysis of the distillation problem necessitates fine- grained characterization of the ERM process. A series of papers (Chang et al., 2021; Montanari et al., 2023; Han & Xu, 2023) utilize Gaussian process theory (Thrampoulidis al., 2015) characterize the distribution of ridgeless estimators. Our theory builds on these to precisely characterize the distillation performance by (i) accounting for model and covariate shift and (ii) tracking the distribution across the two-stage problem where (2) is followed by (1). Our setting strictly subsumes the problem of characterizing the test risk under distribution shift, which relates to the recent papers (Patil et al., 2024; Song et al., 2024; Yang et al., 2023; Mallinar et al., 2024). A distinguishing feature of our work is that we precisely characterize the optimal surrogate model that minimizes the downstream target risk, as highlighted in Figure
generalization. Mobahi et al. (2020) provide theoretical analysis of self- distillation, whereas Menon et al. (2020); Nagarajan et al. (2023); Harutyunyan et al. (2023) study knowledge distillation in teacher-student setting. A related problem is self-training which relies on progressively generating pseudo-labels for unlabeled data (Frei et al., 2022; Oymak & Guleu, 2021; Wei et al., 2022b), While these works consider din-einnnil settings or provide loose bounds, our study provides sharp analysis of ridgeless over- peeerrarrmeterzeed regression. Closer to us, Jain et al. (2024) investigate the benefit of surrogate data by employing both real and surrogate data in single step of ERM, but the analysis is limited to isotropic covariance. Kolossov et al. (2023) consider the problem of surrogate- based data selection. Finally, Charikar et al. (2024); Lang et al. (2024) aim to demystify weak-to-strong generalization by formalizing the intuition that W2S generalization occurs when the strong model avoids fitting the mistakes of the weak teacher. In contrast, our theory reveals that the strong student can benignly overfit the weak teacher, and in fact, carefully crafted weak teacher provably outperforms strong labels, see again Figure 1.
Distillation and
Scaling laws. The dependence of the performance on the available statistical and computational resources is often empirically well well-captured by a power-law (Hestness et al., 2017; Kaplan et al., 2020). This experimental evidence has led to flurry of theoretical work aimed at characterizing the emergence of scaling laws, mostly focusing on linear regression (Spigler et al., 2020; Simon et al., 2023; Bahri et al., 2024; Paquette et al., 2024; Bordelon et al., 2024b; Lin et al., 2024a; Maloney et al., 2022). Bordelon et al. (2024a) analyze a random feature model trained with gradient descent via dynamical mean field theory. Jain et al. (2024) consider scaling laws with surrogate data, whereas Sorscher et al. (2022) study the benefits of data pruning.
PROBLEM SETUP
Notation. Let [p] denote the set (1, p)) for integer p 2 1. We use lower-case and upper-case bold letters (e.g., x, X) to represent vectors and matrices, respectively; x; denotes the i-th entry of the vector x, X the pseudo-inverse of the matrix X, and tr (X) the trace of X. For further notations, please see Table 1.
3

---

Published as conference paper at ICLR 2025
We consider a two-stage linear learning problem. In the first stage, pairs of labels and input features from the distribution D, are used produce an estimate of the ground-truth parameter, which is then used generate labels along with input features from a different distribution D, The second stage uses these generated labels to obtain the final estimate of the ground-truth parameter. The models trained in the first and second stages are referred to as surrogate and target models, respectively.
Stage 1: Surrogate model. We consider a data distribution (X. ~ D, following the linear model B.+ + where B. E RR, x ~ N(O, Σ.) and Σ ~ N(O. is independent of æ. Let [(E; ".). be the dataset for the surrogate model drawn i...d. from Dz- We analyze both under- and over-parametrize settings: in the former, we estimate B. by minimizing the quadratic loss; in the latter, we estimate B. as the minimum norm interpolator. As a result, the estimator of the surrogate model can be written as follows:
aarg ming 11 XBI,.
if 2 p. if < p.
B' Est(X. arrg ming |1112 XB = 5).
where X = [.FT...... J E RM and ý = [ym........l E R...
Stage 2: Target model. Given B e R?, we consider another data distribution (x. D.(B") following the linear model yd = =x B + where x ~ N(0, 2,) and z ~ NOO, Let (Xx,)) be the dataset for the target model drawn i..dd from (B"). As for the surrogate model, the estimator for the target model is defined as Bdd = Est(X.y'),
(4)
where X = [x] ...... 1 Rx and y" bf...... = E R". Our analysis will generally apply to arbitrary B choice and will not require it to be the outcome of (3). Finally, we define the excess (population) risk for given estimator B E R' as
R(B) = Bx. x =T - / BB
(5)
Throughout the paper, we compare the surrogate-to-target model with two different reference models.
Reference 1: Standard target model. We study the generalization performance of 8 with respect to the standard target model, which has access to the ground-truth parameter through laheling. Specifically, consider the dataset (xx, drawn i.i.d. from D,B,): ); then, the estimation is
B' Est(X.y).
(6)
where X [xT..... .,, target model R(B with that of the standard target model R(B")
I IT R"XP and y = [yr, [yI.....) ytJ E R.. We compare the excess risks of the surrogate-to-
Reference 2: Covariance shift model (Mallinar et al., 2024; Patil et al., 2024). Given B. E RP, let
((x,, be a dataset drawn i.idd from Djr where x; ~ NO, E,), z ~ NOO, oi), and y, = B, + z then, using the same notation X [x] E R=xp and y = [y, E R", the estimation is 8es := Est(X.y). y). The test risk of 3 is calculated under covariance shift. Let (x.y) ~ D, be distribution such that x ~ N(0. E,), z ~ N(O, of). and y x x=B. 2 Then, the excess transfer risk is R(P") == Bu.))-2 x 1
We discuss the equivalence between the aurrogate-to-targe model and the covariance shift model in Section 3.
3 ANALYSIS FOR MODEL SHIFT
We start by examining the behavior of the surrogate-to to-tte--ttttrree model when there is model shift B * B.. First, we provide a msppottii bound on the risk conditioned on B", and then we optimize this quantity with respect to 8 (finding also a closed- form expression of the corresponding optimal value of B*). In addition, we build a connection between our surrogate-to-targe model and knowledge distillation (Hinton et al., 2015), as well as weak-to-strong generalization (Burns et al., 2023). Finally, we extend our analysis to ridge regression in Appendix A.I.
We note that when 8 = B.. the calculations in this section simplify to the non-asymptotic risk characterization of the minimum fz-nrr interpolator, recently studied by Hastie et al. (2020); Cheng & Montanari (2024); Han & Xu (2023). When B * B.. the problem is instead equivalent to covariance shift in transfer learning, as formalized by the following observation whose proof is deferred to Appendix A.
4

---

Published as a conference paper at ICLR 2025
Observation 1. The model shift in the surrogate-to-targe model is equivalent to the covariance shift model (Mallinar al., 2024). Formally, given any B. BP and any jointly diagonalizable covariance matrices m. 2, E RRXX, there exists unique B E RR such that the risk of the surrogateto-largel problem RiB221 with (B.. md) is equivalent to the risk of the covariance shift model R (B) with (Bx, Es, 2,).
The joint diagonalizability of Σ, and Σ, is also required by Mallinar et al. (2024) (see their Assumption 2.1), where upper and lower bounds for the bias and variance are provided by adapting results from (Bartlett et al., 2020: Tsigler& & Bartlett, 2022). In contrast, our approach utilizes the non-asymptotic characterization of the 4--orm interpolator by Han & Xu (2023). This allows us to directly characterize the non-asymptotic risk (instead of giving upper and lower bounds, as in (Mallinar et al., 2024)) and, thus, to obtain the optimal surrogate parameter B". We begin by defining the asymptotic risk of the surrogate-tr turrogate-to-target model, given the surrogate parameter B³, in the proportional regime where p.n co and the ratio K; = p/n > I is kept fixed.
Definition 1. Let K, p/n and T, E R be the unique solution of the following equation
1 Cr + +.,)"
K
Let 01 = C,, and 02 C=, T,)) - where g, N(O.Ip). Now, define the asymptotic characterization of the minimum tz-norm interpolator and the function y : Rp - R as the following fixed point equation based on the asymptotic risk
vp
x
B.. ..) = BB yi 02..
(8)
r,BB) == Ks (0 + R.t. C2,, BB,BBBBB)).
(9)
where the asymptotic risk is defined as
R (E,, B.. BO) Eg.
|/=//2(X' s,m?
(x' (E, g,) - BB)
= (0, - BBI1 + (B") Bp.10 1,
(10)
(0)
(8)
= (B' - BB) 0 I (B' - -B.) r2 (B") Eg 10,10,1100 2,02] + 01) - -01)B- 2B. (I (1-61
(T (B' - BB).
In the asymptotic risk, the term (a) corresponds to part of the bias risk caused by the model shift (B"), and the implicit regularization term where the eigenvalues of 0 are less than 1. The term (b) corresponds to the remaining part of the bias and variance risks. We now state our non-asymptotic characterization of the risk.
Theorem 1. Suppose that, for some constant M, > 1, we have 1 1/M, S K,, of M, and [/ ||2 s M,
Recall from (5) that R(B represents the risk of the surrogate-to-targe model given B Then, there exists constant C(M,) such that, for any & E (0, 1/21, the following holds with R 1 < M,;
P(RBB - Rell, (E..B.BB)) 22)222 8) S Cpe pdtc
sup B.B'
(11)
The proof of Theorem utilizes the non asymptotiiicc characterization of the minimum norm interpolator in Han & Xu (2023), which is based on the convex Gaussian min-max theorem (Gordon, 1988; Thrampoulidis et al., 2015). The proof is deferred to Appendix A.
The surrogate parameter B that minimizes the individual term (a) in (10) is B.) On the other hand, the surrogate parameter 8e that minimizes the individual term (b) in (10) is the zero vector, which follows from (16) in Appendix A. Now, we are going to jointly minimize the asymptotic risk in the next proposition. The optimal surrogate parameter is visualized as the green curve in Figure 1.
Proposition 1. Let Ω
The optimal surrogate B minimizing the asymptotic risk in (10) is
Dt2 8 ( +,,+ 1-Q ,,'(E, (E, +T.00") B..
5

---

Published as conference paper at ICLR 2025
Note that, under the setting of Theorem 1, Proposition 1 can be extended to the non-asymptotic risk by applying (1)). The corollary below then offers direct interpretation of the optimal surrogate parameter 8 The proof's of both Corollary and Proposition I are in Appendix A.
Corollary 1. Without loss of generality, suppose that In is diagonal.' ! Let (2),a) be the eigenvalues of Σ, in In
non-increasing order and let (:
- sor i E [p]. Then, the following results hold:
ž,,,
1. 6,- = (B.): ((1 - ()) + +1 1-21 5 for every e [p].
--)00 ()) for every i e [p].
2. 18, > ((B)dll if and only if & Ω
3. 8 =p if and only if the covariance matrix 2 = cl for some C R.
The first part shows that the optimal surrogate parameter is fully characterized by (Ci) which only depends on the covariance spectrum (via 4,) and the sample size n (via T,). Note that the spectrum (4))=1 characterizes the risk in both linear regression and random features regression, shown in lldiz et al. (2024) and Simon et al. (2023), respectively. As the eigenvalues (2) are ordered, the č/s are ordered as well, and the second part of the corollary identifies threshold behavior: before the transition point 1 - 52, the entries of the surrogate are amplified w.r.t. the ground-truth parameter B.. while they experience shrinkage after the transition. The threshold corresponds to the ratio of the sample second moment to the sample first moment of the random variable whose realization is given by (1 - 4)), and it arises from the optimization of the trade-off between the bias and variance terms in (10). Finally, the third part of the corollary shows that, unless the eigenvalues of the covariance matrix are constant, there is potential for improvement by tuning the surrogate parameter.
The intuition behind improving the performance of the standard target model by utilizing a surrogate parameter 8 different from B. is associated with the implicit regularization of the minimum norm interpolator in the over-parametrized region (p n). As long as the covariance matrix eigenvalues are not constant, there is way to mitigate the bias risk caused by the implicit regularization. This implicit regularization term is specific to the over over-vvvaaeeee per-parametrized region. Indeed, in the next proposition (proved in Appendix A), we will show that the optimal surrogate parameter B¹ is B. when the target model is under- aadder-prrametrized:
The optimal surrogate parameter 8 that minimizes the asymptotic risk in the under- parametrized region (n p) is equivalent to the ground truth parameter B.. In other words, for any 8", the parrogate-to-taree model cannol outperform the standard target model in the asymptotic risk.
Proposition 2.
In other words, the result above shows that the improvement in the surrogate-to-targ model compared to the standard target model is special to the over-parameterrize region.
3.1 WEAK-TO TLAK-TO-STRONG GENERALIZATION
To connect with knowledge distillation (Hinton et al., 2015) and weak-to-strong generalization (Burns et al., 2023), we allow the surrogate model to use fewer features, Ps p, by introducing mask operation M(x), where M(x) E R selects P, features from the full set of features in x E R". Alongside this mask, we adjust the distributions for both the surrogate and target models as
(M({).)) ~ DJ' follows 5 M E., where B. E ERR, 8- E., o(), M(B.)
(x.y²) (B') follows y" M(x) B z, where B E R x N.). N(O.
Then, 8 is estimated based on the samples from D."(B") and the risk R(B still calculated with respect to the standard target model distribution D.(..) ) as defined in (5). As we focus on analyzing the model shift case, we assume that the covariance matrices Σ, and Σ, are identical.
In this formulation, the surrogate model is considered weak because it has access to fewer features, while the target model is the strong model. We now address the following question: Can the surrogate-to-targ model outperform the standard target model, provided in (6), in the absence of model shift (M(B.) =
If not, there exists orthogonal matrix U RP s.t. UE,U" is diagonal. Then, can consider the covariance matrix as U and the ground truth parameter as UB., which behaves the same the original parameters, see Observation 2.
6

---

Published as a conference paper at ICLR 2025
The absence of model shift corresponds to the case where the surrogate model has infinitely many data. The next proposition provides a sufficient condition to answer the question above in the affirmative, and derives the optimal selection of features.
Proposition 3. Consider the target model in (6), assume that ,, diagonal, and recall the definitions of Li and Q. Then, the following results hold:
1. If the mask operation M selects all the features that satisfy 1- 1-2, S2 then the surrogate-to-target model outperforms the standard target model in the asymptotic risk in (10).
2. Let M represent the set of all possible M, where IM] = - The optimal M for the asymptotic risk in (10) within M is the one that selects all features satisfying 1 2 > Ω
The proof of Proposition 3 is provided in Appendix A, and the result can be extended to the non-asymptotie risk by applying Theorem 1. Similarly to Corollary 1, the result above identifies a threshold behavior: the entries of the surrogate are masked (i.e., set to 0) after the transition point 1 - 2, 2 while they coincide with the ground-truth parameter B. otherwise. The transition point changes with respect to Corollary and, G, it is shifted to the right: the optimal mask includes not only features whose magnitude
as 1 1 -f increases, but also features whose magnitude decreases while selecting the optimal surrogate B
In Figure la, we illustrate the optimal M and B", showing that the threshold associated with the optimal M is larger than the threshold associated with the transition from amplification to shrinkage in the optimal B". In addition, we note that the ratio between the green curve and the blue curve in Figure la is not monotone with respect to dj. In Figure b, we also present a comparison of their associated risks.
In Figure 2a, we examine the surrogate-te to-ttet-tttt-tttt-te model in the context of image classification. Specifically, we fine-tune pretrained ResNet-50 model (He et al., 2015) using both ground-truth labels and predictions from surrogate (weak) model on the CIFAR-10 10 dataset (Krizhevsky Hinton, 2009). The surrogate models are shallow, 3-layer convolutional neural networks with varying parameter sizes. In all cases, models consistently outperform surrogate models across different model sizes. However, in this setting, sarrogate-t-targe models do not outperform the standard target (strong) model. This is in agreement with the weak-to- to-st-og- results in Burns et al. (2023), where the GPT-4 model trained with GPT-2 labels performs comparably to GPT-3.5. The reason why the surrogate-to-targe model is the surrogate model is not able to follow the feature selection mechanism characterized in Proposition 3. This suggests that the feature selection mechanism is crucial for surpassing the performance of the standard target model. We provide further experimental details in Appendix A.2.
prrogatt--t--trgeer
model underperforms the standard target
4 FUNDAMENTAL LIMITS AND SCALING LAWS
We now study the fundamental limits of the surrogate-to-targ model with the optimal surrogate parameter 8t (see Proposition I) and the optimal mask operator M (see Proposition 3). Our analysis shows that, when cigenvalues (2,) and signal coefficients (1,8;) follow a power law, the risk of the surrogate-to-taree to-tageet model under the optimal selection of the parameters 8 and M scales the same as that of the target model (even though there is strict improvement in the risk, as per Corollary 1). By Observation 1, this also indicates that the gain obtained by the covariance shift model, as outlined in Mallinar et al. (2024), does not change the scaling law. We start our analysis with the definition of the omniscient test risk estimate.
Definition 2 (Omniscient test risk estimate). Fix p > 2 1. Given a covariance Σ = U diag(A))U .B.. and the noise term o,, set B = UT and define T E R as the unique non-negative solution of n Σn A+r the omniscient excess test risk estimate is the following:
2_ Then,
Rom = 10-D x B) 0²= +22+BBB)
(12)
1-Ω
1 P
where S
T +T
- - -1)-
B(B)
1=1
The above test risk estimate yields exact results (and, hence, in (12) becomes =) in the proportional limit via the analysis of Section 3. In other words, the omniscient test risk estimate is identical to (2.......... which can be derived by substituting B² =B, into Equation 10. Specifically, suppose that the empirical distributions
7

---

Published conference paper at ICLR 2025
20
Exsinett 2-05
Expotnerta r-13
Thanakall
75
Test Riak
0.6
66-
0.0
20
100
Epech
Sample Size (m)m))
(a) Weak-to-strong on CIFAR-10
(b) Comparison of theoretical and experimental risks
Figure 2: (a): On the CIFAR-10 10 dataset, fine-tune ResNet50 model using the ground-truth labels (target) and the predictions three weak convolutional models (surrogate) with different capacities: big (b), medium (m), and small (s). We observe that surrogate-te -o-teett models consistently outperform surrogate models' accuracies, even though they are trained on the surrogate models' predictions. (b): We compare the experimental two-stage risk with estimated theoretical risk. In the experimental setup, p 100, and vary from I to 100. Both feature covariances follow the power-law structure 2, = r- for a = 0.5, 1, 1.5 and 2; the ground truth parameter B, is specified B,
of B and d converge as p co having fixed the ratio p/n K. Then, the risk obtained in Theorem 1 converges to the omniscient risk estimate given in (12), as proved in Appendix B. We will use this omniscient risk estimate in the limit of p - co, as considered in several papers (Cui al., 2022; Simon al., 2024; Wei et al., 2022a). Yet, our empirical validations in Figure demonstrate that this framework yields consistent results even when applied to scenarios with moderately sized p and n.
Throughout the section, we analyze the case where the surrogate parameter B' is given, therefore we need to take into account only the target covariance matrix Σ. Without loss of generality, we assume that the covariance matrix Σ, is diagonal by Observation 2. From now on, we will consider the particular case of power-law eigenstructure, that Σn = 2, = i". The omniscient risk under this structure still depends on the parameters T, and Ω and the next proposition analyzes them asymptotically. Its proof is in Appendix B.
Proposition 4 (Asymptotic analysis of and Q). Let the covariance matrix E e RexP be diagonal and Σn d2 = -= for 1 a. Recall from Definition that, as p - 00, T₁ and are given by the equations
4 n.
nn
T+ E
ja j
F
Then, the following results hold
T, cn +1+00 O(
for
a sis (T/a)
(13)
Ω a-1 -(n-). 1l a
Recall from Corollary and Proposition that the cut-off indices for the optimal surrogate parameter 3 and the optimal mask operation M are respectively & Ω and & < Ω which depend Ω2 Armed with the asymptotic expressions in (13), we now identify the cut-off indices as a function of the sample size n.
sin (I/aa
sin (z/a)
Proposition 5. Set the constants C₁ л(a - 1) and C2 π Va 1) and assume the power-law
eigenstructure Σn A; = i-a for a. Let T, and Q be the solutions given by Proposition 4 and define To C A+.. Then, the indices i for which 4 < Q are < nC1 + 0(1;; while the indices i for which is
2 < are i nC2 + 0(1).
8

---

Published as conference paper at ICLR 2025
The result above is proved in Appendix B, and it shows that, as the sample size n decreases, the cut-off indices of both the optimal surrogate parameter 8 and the optimal mask M' shift to the left linearly in n. This also implies that, with less data, optimal surrogate models tend to be more sparse.
Next, we address the question of how the excess test risk scales with respect to the sample size n, when the surrogate parameter is the optimal B².. Specifically, Proposition 6 below shows that, under a power- law decay of both the eigenvalues (24) and the signal coefficients (2/63), the excess test risk of the optimal surrogate-t-taagee model scales the same as the standard target model.
Before stating the result, we make a comment on the noise assumption needed ensure that the scaling law of the excess test risk remains unaffected by the introduction of noise, which allows us to analyze the model's inherent error. Specifically, we choose the variance of the noise term of to be most of the order of the scaling law of the excess test risks when of = 0. This corresponds to of '),"), where y is the exponent of the scaling law in the noiseless setting. Conversely, fixed noise variance or @(1) that does not decay with would cause the noise to overshadow the uncaptured part of the signal, which scales down with In this unintended scenario, the noise would dominate our observations.
Proposition 6 (Scaling law). Let the covariance matrix Σ, be diagonal with eigenvalues 2, and let the ground-truth parameter B. have components B, corresponding to each feature. Assume that both eigenvalues A and signal coefficients 2.8, follow a power-law decay, i.e., AB;; i and A; ===i= = for a, B > 1. Let the optimal surrogate parameter 8 be given by Proposition I and define the minimum surrogate-to-tan attained by 8 as Ram min Bom( where (B is described in Definition 2. Then, in the limit of p - co, the excess test risk of the porogate-to-taryy model with an optimal surrogate parameter scales the same that of the standard target model. Specifically, we have
risk
RBt) On 11-))) (B),
if < 2a + 1. if 20 1.
R (B O(n (0))= (B',
Since (B is a lower bound on R (B we have that the scaling law of the excess test risk of the ourrogate-to-tagee model cannot be improved beyond that of the standard target model, even with the freedom to choose B², This also indicates that the optimal selection of the mask does not improve the scaling law, see Proposition 7 in Appendix for details.
The proof of Proposition 6 is deferred to Appendix B. Here, we note that we utilize the expression P (Eer (())))()) as lower bound for the risk, while proving the scaling law for the optimal surrogate-to- target model. Although this expression alone is insufficient to determine an asymptotic lower bound for an arbitrary Br, it becomes particularly useful when considering the optimal surrogate parameter 3 provided in Proposition 1. We then leverage the fact that the optimal surrogate parameter yields the minimum test risk to characterize its asymptotic behavior.
Finally, we provide in Appendix B also non-asymptotic analysis of 7, and Ω (see Propositions 8 and 9, respectively). which complements the asymptotic one in Proposition 4 above. This allows us to characterize region with finite and p where the surrogate-to-target model strictly outperforms the standard target model, see Proposition 10.
5 RISK CHARACTERIZATTIN FOR THE TWO-STAGE MODEL
Until now, we have examined the behavior of the surrogate- to-taget model when is given. In this section, we characterize the non-asymptotic risk of the aurrogate-to-taree model when Be is the solution of the surrogate problem (3) where K. p/m 1. Our analysis includes two cases: (i) the target model has infinitely many data (n = oo), and (ii) the target model is overparametrized. i.e., K; = p/n > 1.
When the target model has infinitely many data, the estimate of the surrogate-tor posrsatttttttargee to-target model 8 is equal to the estimate of the surrogate model B². This means that the correct ground-truth parameter B. is estimated under distribution D, and tested under another distribution D,B,.), which is equivalent to the covariance shift model by definition. By Observation 1, the model shift in the surrogate-to- to-target model is equivalent to the covariance shift model and, hence, the analysis in Sections and 4 is valid for this case.
9

---

Published as conference paper at ICLR 2025
Finally, we consider the case where the target model is overparametrized and begin with the following asymptotic risk definition.
Definition 3. Recall the definition of T, and y in Theorem 1. Let K; = p/m > and define T2 E similarly to Tr We define the random variable X* based on 8s" N(0, 1) and the function RR _ R as follows: K,0;
B. I, 1-1/2 y,(B.)g
X K,00 (.., g.) == (2, + +T,
VP
r(BB)) == k, (0,, + Bg. 112 (x. 2, ( B., g.) B. B.)l1).
Let k= K)), == =Z,, ) and G o.). Then, we define the asymptotic risk estimate as
(x. = =12 1/ (1 - (-= + 1 1) ト + 2,) Ex mu?
Ix:(B)
tr
(2, +,,)
(,B.) + tr ( 1/2 (,, +T, 2 r, T r11)
-T) 111
p
The non-asymptotic characterization of the risk is stated below and proved in Appendix C, which also contains closed-form expression for Ex-x ... bx
[x,(B)) (x- (see Lemma 1).
Theorem 2. Suppose that, for some constant M, > 1, we have 1/M, S Ks, K,,0 of S M, and [Eollop |اا ll.p IIE || 1lpp S M,, Consider the prrogate-to-targe model defined in Section 2, and let R( represent its risk when B. is given. Recall the definition L k, & and Re,o in Definition 3. Then, there exists constant C = C(M)) such that for any & E (0, 1/2), the following holds when R + 1 < M,:
sup - - -e. (2...) B.EB,18)
2 8) S Cpe
In the proof of Theorem 2, we apply the distributional characterization of the minimum norm interpolator (Han & Xu, 2023) twice. The main technical difficulty is satisfy the Lipschitz condition of the distributional characterization in the second step, which is handled by bounding the intermediate step's 's interpolator in ball.
We implement the surrogate-to-taree model with synthetic dataset and demonstrate that our risk characteri- zation agrees well with the experimental two-stage linear regression in Figure 2b. Furthermore, we extend our analysis of the two-stage model to the padde-parametrizee region in Appendix C.I. This extension enables us to analyze Section 3.1 thoroughly because this analysis allows the surrogate model to have finite data.
6 CONCLUDING REMARKS
We have provided sharp characterization of knowledge distillation for high-dimensional linear regression when labels are generated by a surrogate model and, additionally, characterized the risk of the two-stage process where the surrogate model is the outcome of an initial ERM. These results shed light on the form of the optimal surrogate model, reveal an amplify-to-shrink phase transition as a function of the eigenspectrum, and draw connections to weak-to-strong generalization. Specifically, we have shown that the labels coming from the optimal surrogate model strictly allow for improving the performance of the target model, unless the covariance a multiple of the identity. However, even though there strict improvement in the risk, the scaling behavior of the two-stage process with labels coming from the optimal surrogate model remains unchanged compared to the standard target model that utilizes ground- truth labels.
We outline three interesting directions for future research. The first is to extend the two-stage process to multiple stages, establishing whether this further improves the risk. The second is to apply the two-stage learning to data pruning, using the surrogate model to decide whether to keep or discard each (x, y) pair during the training of the target model. The third to go beyond linear regression towards neural network models. In this regard, the precise asymptotics of the test error of the ERM solution were provided by (Mci & Montanari, 2022) for the random features model and by (Montanari & Zhong, 2022) for two-layer neural networks in the NTK regime. However, a non-asymptotic characterization (similar to that given by (Han & Xu, 2023) for linear regression) remains an open problem. The resolution of this open problem, as well as the analysis of the phenomena of knowledge distillation and weak-to-strong generalization, represent exciting future directions.
10

---

Published as conference paper at ICLR 2025
ACKNOWLEDGEMENTS
M.E.I,, H.A.G., E.O.T., S.O. are supported by the NSF grants CCF-2046816, CCF-2403075, the Office of Naval Research grant N00014241 1000114412289, an OpenAl Agentic AT Systems grant, and gifts by Open Philanthropy and Google Research. M. M. funded by the European Union (ERC, INF?, project number 101161364). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority be held responsible for them.
REFERENCES
Marah Abdin, Sam Ade Jacobs, Ammar Ahmad Awan, Jyoti Aneja, Ahmed Awadallah, Hany Awadalla, Nguyen Bach, Amit Bahree, Arash Bakhtiari, Harkirat Behl, et al. Phi-3 technical report: A highly capable language model locally on your phone, 2024. URL //axxii http://aaxi...o/ab///////ae/
14219.
Yasaman Bahri, Ethan Dyer, Jared Kaplan, Jaehoon Lee, and Utkarsh Sharma. Explaining neural scaling laws. Proceedings of the National Academy of Sciences, 121((7):e2311188111 2024.
Peter L. Bartlett Philip M. Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(49):30033-30777 2020.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences, 116(32): 15844, 2019.
Blake Bordelon, Alexander Atanasov, and Cengiz Pehlevan. A dynamical model of neural scaling laws, 2024a. 01092.
URL htt.aass/aarxii..orraaa/////////
Blake Bordelon, Alexander Atanasov, and Cengiz Pehlevan. How feature learning can improve neural scaling laws, 2024b. URL https:::aawwi..rrg///////// http://bb/2299.1111
Collin Burns, Pavel Izmailov, Jan Hendrik Kirchner, Bowen Baker, Leo Gao, Leopold Aschenbrenner, Yining Chen, Adrien Ecoffet, Manas Joglekar, Jan Leike, Ilya Sutskever, and Jeff Wu. Weak-to-strong generalization: Eliciting strong capabilities with weak supervision, 2023. URL ttttps://ariiv /ttp///iiv..oog/b///1/211 ab3.a//0.233......... 09390.
Xiangyu Chang, Yingcong Li, Samet Oymak, and Christos Thrampoulidis. Provable benefits overparame- terization in model compression: From double descent to pruning neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 6974-6983, 2021.
Moses Charikar, Chirag Pabbaraju, and Kirankumar Shiragur. Quantifying the gain in weak-to-strong generalization, 2024. URL https://arxiv wwtpe/iv.org/bbs////// org/abs//4055.0.. 15116.
Chen Cheng and Andrea Montanari. Dimension free ridge regression, 2024. URL UtLpstps://axxiiorrg abs/2210.0857 085711
Hugo Cui, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Generalization error rates in kernel regression: the crossover from the noiseless to noisy regime. Journal of Statistical Mechanics: Theory and Experiment,
2022.
Alex Fang, Albin Madappally Jose, Amit Jain, Ludwig Schmidt, Alexander Toshev, and Vaishaal Shankar. 17425.
Data filtering networks, 2023. URL http:://xxivv.og/aabsssoso
Spencer Frei, Difan Zou, Zixiang Chen, and Quanquan Gu. Self-training converts weak learners to strong learners in mixture models. In International Conference on Artificial Intelligence and Statistics, pp. 8003-8021. PMLR, 2022.
Y. Gordon. On milman's 's inequality and random subspaces which escape through a mesh in m. In Geometric Aspects of Functional Analysis, pp. 84-106, Berlin, Heidelberg, 1988. Springer Berlin Heidelberg.
11

---

Published as conference paper at ICLR 2025
Suriya Gunasekar, Yi Zhang. Jyoti Aneja, Caio César Teodoro Mendes, Allie Del Giorno, Sivakanth Gopi, Mojan Javaheripi. Piero Kauffmann, Gustavo de Rosa, Olli Saarikivi, Adil Salim, Shital Shah, Harkirat Singh Behl, Xin Wang, Sébastien Bubeck, Ronen Eldan, Adam Tauman Kalai, Yin Tat Lee, and Yuanzhi Li. Textbooks are all you need, 2023. URL https://arxii org/ abs/ 11644.
Qiyang Han and Xiaocong Xu. The distribution of ridgeless least squares interpolators. 2023, URL https: //arxiv. org/ httpii..rrgabb///33// 02044.
Hrayr Harutyunyan, Ankit Singh Rawat, Aditya Krishna Menon, Seungyeon Kim, and Sanjiv Kumar. Su- pervision complexity and its role in knowledge distillation, 2023. URL httpps:s/aaaii..og///aa//a 12245.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J. Tibshirani. Surprises in high-dimensional ridgeless least squares interpolation, 2020. URL httpp://arre oog.ooggg//........ aaaaaas// 1
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition, 2015. URL /ttps://aaxiv..r wwwrxiiv.orggaaae wrw. 1b..1512..3385.
Joel Hestness, Sharan Narang, Newsha Ardalani, Gregory Diamos, Heewoo Jun. Hassan Kianinejad, Md. Mostofa Ali Patwary, Yang Yang, and Yanqi Zhou. Deep learning scaling is predictable, empirically, 2017.
URL htt.https//aaxii.orrgg/////
00409.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network, 2015. URL https://arxiv.. http://axxiivooggbb//////a abt/aa///.//../... 02531.
Muhammed E. Ildiz, Zhe Zhao, and Samet Oymak. Understanding inverse scaling and emergence in multitask representation learning. In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Reseurch, pp. 4726-4734. PMLR, 02-04 May 2024. URL https::/proceedingggg
mlr press/v238/ild/ /i12/iiiai22aa .ttll.
Ayush Jain, Andrea Montanari, and Eren Sasoglu. Scaling laws for learning with real and surrogate data, 2024. URL https::p://a wtt.:orggg/bb/////eeee 2ttp/242..0000 04376.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models, 2020. URL
Germain Kolossov, Andrea Montanari, and Pulkit Tandon. Towards a statistical theory of data selection under weak supervision, 2023. URL https://arxiv.. wwtrrrii..rggbbb//.eee
14563.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical Report 0, University of Toronto, Toronto, Ontario, 2009. URL htthh://w//ww..... ws.. toronto. toronto.eduu/-krrzz. learning- features-2009- 2009-TR.pdf.
Hunter Lang, David Sontag, and Aravindan Vijayaraghavan. Theoretical analysis of weak-to-strong general- ization, 2024. URL
http:/aawwa.....a//a/a...... 16043.
Licong Lin, Jingfeng Wu, Sham M. Kakade, Peter L. Bartlett, and Jason D. Lec. Scaling laws in linear regression: Compute, parameters, and data, 2024a. URL https://arxiv.ot www.orggggg..oo...//////
Zhenghao Lin, Zhibin Gou, Yeyun Gong, Xiao Liu, Yelong Shen, Ruochen Xu, Chen Lin, Yujiu Yang. Jian Jiao, Nan Duan, and Weizhu Chen. Rho-1: Not all tokens are what you need, 2024b. URL https:
//arxiv. orgg htrgg/bb//aa 20../2404.777 07965.
Bruno Loureiro, Cédric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Mare Mézard, and Lenka Zdeborová. Learning curves of generic features maps for realistic datasets with a student model* Journal of Statistical Mechanics: Theory and Experiment, 2022(1 14001, November 2022. ISSN 1742- 5468. doi: 10. 10.1088/1780
URL http: doip:o///xx/oioooo////oooo//ooot doi org/10. 10. 1088/ 5468/ac9825.
Neil Mallinar, Austin Zane, Spencer Frei, and Bin Yu. Minimum-nove norm interpolation under covariate shift, 2024. URL httph::/t/aaaae www.orggg/a....o...... hwtgg/bb//04..... 00522.
12

---

Published conference paper at ICLR 2025
Alexander Maloney, Daniel A. Roberts, and James Sully. A solvable model of neural scaling laws, 2022. URL https://arxiv.om org/ abw//bss/2000 16859
Song Mei and Andrea Montanari. The generalization enror of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75(4):667-766, 2022.
Aditya Krishna Menon, Ankit Singh Rawat, Sashank J. Reddi, Seungyeon Kim, and Sanjiv Kumar. Why distillation helps: a statistical perspective, 2020.
http://arrii..oo//a//0/00// 10419.
Hossein Mobahi, Mehrdad Farajtabar, and Peter Bartlett. Self-distillation amplifies regularization in hilbert space. Advances in Neural Information Processing Systems, 33:3351-3361, 2020.
Andrea Montanari and Yiqiao Zhong. The interpolation phase transition in neural networks: Memorization and generalization under lazy training. The Annals of Statistics, 50(5):2816-2888 2022.
Andrea Montanari, Feng Ruan, Youngtak Sohn, and Jun Yan. The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime, 2023.
URL htttt://aaxxiii org/ /a// 1111199111111 01544.
Vaishnavh Nagarajan, Aditya K Menon, Srinadh Bhojanapalli, Hossein Mobahi, and Sanjiv Kumar. On student- teacher deviations in distillation: does it pay to disobey? Advances in Neural Information Processing Systems, 36:5961-6000, 2023.
Samet Oymak and Talha Cihad Gulcu. A theoretical characterization of semi-supervised learning with self- training for gaussian mixture models. International Conference on Artificial Intelligence and Statistics, pp. 3601-3609, PMLR, 2021.
Elliot Paquette, Courtney Paquette, Lechao Xiao, and Jeffrey Pennington. 4+3 phases of compute-optimal neural scaling laws, 2024. URL
15074.
Pratik Patil, Jin-Hong Du, and Ryan J. Tibshirani. Optimal ridge regularization for out-of-distribution prediction, 2024. URL https: http://rgggbbb//////eeee 01233.
Dominic Richards, Jaouad Mourtada, and Lorenzo Rosasco. Asymptotics of ridge (less) regression under general source condition. International Conference on Artificial Intelligence and Statistics, pp. 3889-3897. PMLR, 2021.
Mark Rudelson and Roman Vershynin. The smallest singular value of a random rectangular matrix, 2009. URL /ttps::/arxxiv.. wttpl//.rrgabbb//////e /bs/0802.000 3956.
James B Simon, Madeline Dickens, Dhruva Karkada, and Michael Deweese. The eigenlearning framework: A conservation law perspective on kernel ridge regression and wide neural networks. Transactions on Machine Learning Research, 2023.
James B. Simon, Dhruva Karkada, Nikhil Ghosh, and Mikhail Belkin. More is better in modern machine learning: when infinite overparameteriizatonn is optimal and overfitting is obligatory, 2024. URL https:
14646...
Yanke Song, Sohom Bhattacharya, and Pragya Sur. Generalization error of min-norm interpolators in transfer learning, 2024. URL https://arxiv. www. httgg/bb//2400 13944.
Ben Sorscher, Robert Geirhos, Shashank Shekhar, Surya Ganguli, and Ari Morcos. Beyond neural scaling laws: beating power law scaling via data pruning. Advances in Neural Information Processing Systems, 35: 19523-19536, 2022.
Stefano Spigler, Mario Geiger, and Matthieu Wyart. Asymptotic learning curves of kernel methods: empirical data versus saacher-studem paradigm. Journal of Statistical Mechanics: Theory and Experiment, 2020(12): 124001, 2020.
13

---

Published conference paper at ICLR 2025
Christos Thrampoulidis, Samet Oymak, and Babak Hassibi. Regularized linear regression: A precise analysis of the estimation error. Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pp. 1683-1709, Paris, France, 03-06 Jul 2015. PMLR.
A. Tsigler and P. L.. Bartlett. Benign overfitting in ridge regression, 2022. UtL.https:/aaxxi..om /rwg/////g//////////////oo/// 2009. 14286.
Yizhong Wang. Yeganch Kordi, Swaroop Mishra, Alisa Liu, Noah Smith, Daniel Khashabi, and Hannanch Hajishirzi. Self-instruct: Aligning language models with self-generated instructions. In Proceedings of the 61 Anmual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pp. 13484-13508, 2023.
Alexander Wei, Wei Hu, and Jacob Steinhardt. More than a toy: Random matrix models predict how real-world neural representations generalize, 2022a. URL https://arxiv. org/ a2s/
Colin Wei, Kendrick Shen, Yining Chen, and Tengyu Ma. Theoretical analysis of self-training with deep networks on unlabeled data, 2022b. URL URL httLLattps//aaxii.or/////////// 03622.
Denny Wu and Xu. On the optimal weighted f_2 regulariization in overparameterized linear regression. 2020.
Advances in Neural Information Processing Systems,
Fan Yang, Hongyang R. Zhang, Sen Wu, Christopher Ré, and Weijie Su. Precise high-dimensional asymptotics for quantifying heterogeneous transfers, 2023. URL https: //arxivv.ivv/////aa orggabs//0110 11750.
14

---

Published conference paper at ICLR 2025
A
PROoFS FOR SECTION 3
Below, summarize the notations used throughout this paper:
Category
Symbol
Description
R(-)
Excess population test risk.
R(-)
Asymptotic excess test risk.
Risk
Ram()
Asymptotic omniscient excess test risk, which is equivalent to the two-stage risk when 8 B.
B'
Estimator of the surrogate model after the stage Estimator of the target model after the stage 2. Estimator of the standard target model.
B
Parameters
B
B.
Ground truth parameter.
Σ,
Covariance matrix of the data distribution used in surrogate model. Covariance matrix of the data distribution used in target and standard target models.
Covariances
Σ,
A
i'th eigenvalue of the covariance matrix Σ, in decreasing order.
The unique solution the fixed point equation: K," 1tr (2, T,I) (2,
T
The unique solution to the fixed point equation: K, tr (2, + T, Covariance statisties given by &
T,
Si
d,+,,
Q= (( (1-2) (1-()
Variables
Q
X K,
(2, B..B.. g.)
Asymptotic characterization of the minimum & interpolator obtained after training surrogate model. Asymptotic characterization of the minimum l interpolator obtained after training target model.
X
(I,,
(B,)
(B.)) Ks (o² Eg, /
(X' k,,0, -.).B..g)BB.lppp
(E..B.. g.) B. B.)1
r.B²) = K, (o, R.,,, (I,
Table 1: Summary of notations used in the paper.
Observation 1. The model shift the surrogate-to-turgel model equivalent to the covariance shift model (Mallinar et al., 2024). Formally, given any B. R2' and any jointly diagonalizable covariance matrices Σ,, L, E RPKP, there exists unique B RR such that the risk of the surrogate to-target problem RiB with (B..B'. Σ,) equivalent to the risk of the covariance shift model R (B) with (B.. Σ,, E,).
Proof. By Observation 2, we assume that Σ, and Σ, are diagonal matrices. As E, and Σ, are jointly diagonaliz- able, there exists unique diagonal matrix A E RPX such that
Σ, = A E,A.
Then, consider the model shift discussed in Section Take the case where B AB, and labels are generated y x B z, where x N(O, Σ,) and y= = (xx A A)_ + x B. + z such that x N/0, Σ,) and z N/O, o?). Note that (i) the transformed inputs and the labels are identical in both scenarios, and (ii) the estimators are computed in the same way. Thus, it follows that the risks 2)) and RT*(B are equivalent. The other way follows from an almost identical argument.
N(O, o?)). This is equivalent to the where
Observation 2. For any covariance matrix Σ E RM there exists an orthonormal matrix U E R such that the transformation of - X and B U does not affect the labels y but ensures that the covariance matrix is diagonal.
Proof. Since the covariance matrix Σ is PSD, its unit-norm eigenvectors are orthogonal. Consider the matrix U whose columns are the eigenvectors of Σ. Then, can be expressed as Σ UAUT, where A is the diagonal
15

---

Published conference paper at ICLR 2025
matrix containing the eigenvalues of Σ. Consider now the transformation
z 2=
2 = E
xx - - UUU'AUUUU
U
In this way, the covariance matrix is diagonalized. Thus, the transformation (x. (U*x,U* works as intended since the labels are preserved.
Definition 1. Let K, p/n and T, E R be the unique solution of the following equation
Ki (C, T,I)
Let 01 == ( and 02 : T,
1/ 12 gy where gr N().Ip). Now, define the asymptotic
vp
characterization of the minimum n--nomm interpolator and the function Y, Rp - R as the following fixed point equation based on the asymplotic risk
X K
C2, g.) == 0.8² yB2
(8)
rBB²') = Kr (,² + R (..
(9)
where the asymptotic risk is defined as
R (C,.B. B*) :BBy. (x' kut (2, g.) B.)1
= =112, - BB) + (f Eg, 10 Σ,02]
(10)
(0)
(8)
= (B' - -,) (B' + r) Eg I, 0D).- 2B. T( -1-0,) - E,0 BB)-
+
Theorem 1. Suppose that, some constant M, 1, we have 1/M, K,, of M, and || ||
M,
Recall from (5) that R) represents the risk of the surrogate-to-targe model given B². Then, there exists constant C(M,) such that, for any & (0, 1/21, the following holds with R < M,:
sup BB,RR
P(R(BB))
R B... B²) S -p
(11)
Proof. Even though the claim readily follows from Theorem 2, we give a proof for the sake of completeness.
Define a function fi R R as fi(x) = | (x B1) The gradient of this function is
(x)ll = 12 BB) s 21/ ||x -B1122
Using Corollary 2, there exists event E with P(A") S PiC- where C, C,M,. MyB) (with the definition of M, in Corollary 2), such that (B is 2.Mf-Lipschiie if B.. B (R). Applying Theorem 4 on the target model, there exists constant C, C,,,) such that for any E (0. 1/2], we obtain
sup B Man
(11881) 4 B. g.))
z é Cpe-né'c
(14)
where /(B = R1) and
E, 1/ ()(B)) g:
X 4.o
(2..Br Bi) = (E, + T,1) -, B"
vp
Furthermore,
Eg, f(x k.o (I, (E,, B"))B)
=Bg. [1Z_ (B' - - (1- + 02r,B' m1
(B' -BB'-B.)TTpp 2,0 - 7B) E,00
+ (I (1- 01) "T( -0,8. -BB. 0 B.).
(15)
where 0 ;= (2, -E, and 0 = (E, -1 1/2 g This completes the proof.
16

---

Published conference paper at ICLR 2025
Proposition Let t=(2)
The optimal surrogate 8 minimizing the asymptotic risk in (10) is
Qt E +z1011 B..
1-Q B (2, (2,
Proof. We have that
BR 5(x
B",
= BB. [ (B,( - + +.x,BB ||1]
=B' -B8'-Ba) -f,0 (f) 1,01
+I. (1--0-0 01) Σ,( 01)..-291 -1- (1- 0,) EB' B.).
where 01 (2, + +,I) 02 (2, T,1) -
i. Vp
Recall from (9) that
r,(8") = K. (,7 + Ree (2, (2,
= Kr (0? + 1, B 10, (0000))00000000000)000000000-000
This implies that
of (B') - O1) 0,8
(16)
1 - 10
o7 ?/11 -,I) B
1 ! (r, +T,,
where (a) follows from the fact that I - 0 (L, + T, ' = T, + T,Z)-1 and K, 1,,10,2,0 E,0,] tt + 2z))
In order to optimize this with respect to B", let's take the derivative:
E F(x N,00 (E, g.)) aß
s.
tr (E + +
=, -B,) 2, 01). +2 K,T?
T-Q E, + 3B²
p
=00T2,010' 2E,0BB +2 KI. 1-Q E, +.))
tr (E, +12)
KTT 1-Ω EE T, 2B A
2, 22,0B +
Qr?
E,0 - E,0 +
E, (E, + T,I) 28"
1-Ω Ω
Dr?
I, 1-Ω 0 T.I) x Σ,O,B
Hence, the claimed result follows.
Corollary 1. Without loss of generality, suppose that E, is diagonal." Let (A1)- be the eigenvalues of E, in io non-increasing order and let & 2i,,, for i E [p]. Then, the following results hold:
1. = (1)- (1-)
for every i [p].
"If not, there exists orthogonal matrix U R s.t. UT, is diagonal. Then, consider the covariance matrix UE,U" and the ground truth parameter UB., which behaves the same as the original parameters, see Observation 2.
17

---

Published as conference paper at ICLR 2025
-=00= 2. | > 1(B))l if and only -
-p for every i [p].
3. 8 =B, and only the covariance matrix I. cl for some c R.
Proof. When the definition of L and plugged Proposition 1, the first claim is obtained. Using the diagonalization assumption on L, let's analyze only the i-th component of the optimal surrogate given in Proposition
(B.):
4;
0
1,47
T-Q
A+t
(B-)
d
1ett,
1-f
1ett
(1)
g = (B.).
(1 (i)²
R 2
1-12%
- p = (B.).
(1 (1-2) +
1-1
It's now clear that & 1 Q if and only (B² ((B))l-
Let's now check when the ratio between them is 1. Algebraic manipulations give:
(1-4)
(1 (1-1)² 4)) 72
1-251
Ω (1- (1- Ω
Σ/ (1 {i)
4=1 1 Ω = 1 - = Q where Q
2% (1-4)
This gives that 8 BB if all G's are equal, which implies that all dj's 's are equal. Concluding, the covariance matrix is multiple of the identity if and only if 8 =B,
Proposition 3. Consider the target model in (6), assume that Σ, diagonal, and recall the definitions of Li and Q. Then, the following results hold:
1. If the mask operation M selects all the features that satisfy 1- S2 then the surrogate-to to-trggt model outperforms the standard target model in the asymptotic risk in (10).
2. Let M represent the set of all possible M, where [M] = 2P. The optimal M for the asymptotic risk in (10)
within M is the one that selects all features satisfying 1 23 Ω
improve clarity by explicitly stating all intermediate steps. For the purposes of analysis, we assume, without loss of generality, that the first ps dimensions are selected from B. M(B.) = B R Based on this, we no longer need have the decreasing order for the corresponding A; ss. Let RiB") and R(B.) represent the asymptotic risk of the target and the surrogate-to-targe models, respectively. From the excess test risk formula in Definition we have that
Proof. The proof for Proposition was correct, yet we made changes
R(B') B -x)xxxx)0--0 B(B.) + +0
(17)
1-Q
B'
where B(B.) EP_ A.S.P. Now. consider the zero-padded vector f
ER.. This way, consider
0 0p-p.
the labels in the second training phase as y" x B z, where o7). Next, using the asymptotic risk
18

---

Published conference paper at ICLR 2025
estimate in Equation (10), we write the excess test risk formula for the surrogate-to-targer model with respect to the original ground truth labels:
Rel KedT
B.. =
+ 01 - 2B. (0,00)_,,006 -B.)
where 0, == (2, + T L, 02 == (2, + T,,1- /!
& vp
and 8, N(0, p)) Algebraic manipulations give:
R = B (y x B 2 o7
2
R Ko
BL,BB.P
of + ( E, +T,)
(2, + x1
(B' B.) 2,' B.)
1-Q
p
+B. (1 0,) 0DB. TB.TTI 0,) -B-
of.
+ 18
1
A
Ai
+ +2
1itT
1 + T
B
7
2
Σ
P
2
2 + T1
(4+ + T1)
i=p+t
o + ΣE 2
Σ
1B3
1-Q Q
imp,-1
B(B)) 0f
A.P.
(18)
Ω
i=p,+1
Thus, the risk difference between the target and surrogate-to-target models is
R(B') R(B B(B+)- B(B
1-
ippt1
Σ i-pp-1 - 2,?70p
P
Σ
B.
1-
t=p,+1
We observe that each dimension's 's contribution to the excess test risk can be analyzed individually. Therefore,
2 > 1 Ω
(19)
excluding feature i in the feature selection reduces the overall risk R(B Along the same lines, the projection M that selects all the features i that satisfy 2 < 1 - Ω minimizes the asymptotic excess test risk.
O
Proposition The optimal surrogate parameter 8 that minimizes the asymptotic risk in the under- parametrized region (n > p) is equivalent to the ground truth parameter B.. In other words, for any 8r, the aurogate-to-targel model cannot outperform the standard target model in the asymptotic risk.
Proof. According to Theorem 3 of Chang et al. (2021), when the second stage is in the under-parameteerized regime, the estimator 8e2r can be expressed asymptotically as:
Σ
1/2 g
B = B + O,
(K,1
19

---

Published conference paper at ICLR 2025
where 8,~ N(0, p). Then, the excess test risk estimate this estimate is:
B4002000)) x p of = E
(B
B
x g:
2
1/1 g1
Egg B' Oi
Bx
I B' + +
B.
Vp(K5'- -1)
v (K(x]) -11
0,
(B')),)) I, (B' -B+)
) is non non-negative and takes its minimum value at B² = B.. Note that at B B. the expression corresponds to the risk of the standard target model. Hence, we conclude that it is not possible to surpass the performance of the standard target model with the curogate-to-targe model when the target model is under- muder-parameterizer (n p).
As Σ, is positive semi-definie the expression (B' BB.) 2, (B' (B.)
A.1 ANALYSIS FOR MODEL. SHIFT UNDER RIDGE REGRESSION
In this subsection, analyze the behavior of the aurrogate-to-taree model under ridge regression. First, redefine the surrogate and target models below.
Stage 1: Surrogate model. We consider data distribution (š. () f) D, following the linear model ý BTB. + where B. E RR, I ~ N(0, Σ.) and ž ~ N(O, ()) is independent of I. Let ((E,,))) So be the dataset for the surrogate model drawn i.i.d. from D,. The estimator of the surrogate model can be written as follows:
A.
- (
B arg min BER
| Xp1
2dl 8
(20)
2p
2
where X = [E] I E mx and j = Ym R
Stage 2: Target model. Given B eR,, we consider another data distribution (x,y*) D,( following the linear model yd = x B + z, where x NO0 Σ.) and N(O, of)),ff). Let ((x,, y/ be the dataset for the target model drawn i.i.d. from D. As for the surrogate model, the estimator for the target model defined as
d, LUn = 1 ( 2.1 X"y.
BTTh == arg min BER
lly
XBI2
(21)
2p
2
where X [x]...... I',' E R and y" = yJJ E R.. Our analysis will generally apply to an arbitrary B choice and will not require it to be the outcome of (20). Finally, we define the excess (population) risk for given estimator B E R as defined (5). Throughout the section, we compare the surrogate-to-target model with the following reference model.
Standard target model. We study the generalization performance B with respect to the standard target model, which has access to the ground-truth parameter through labeling. Specifically, drawn i.i.d. from D,B,): ); then, the estimation is
Reference Model:
consider the dataset (x))))))
- 11013 = 1 +11
d
B = arg min BEr
bly XBI1
8 8yy.
(22)
2p
2
p
where Ix....... IT
RNXP and y [y [y...... y,. E R., We compare the excess risks of the surrogate-to- target model R(B;2)) with that of the standard target model R(B)).
Now, we will obtain result similar to Theorem 1 under ridge regression. For this purpose, we have the following definition:
Definition 4. Let K, p/n > and T,, R be the unique solution of the following equation
-- +T,
de
(23)
Tir
Then, define Xt
n. 2. E.,B" 81). the function y, and the asymptotic risk Rny, B...B.BB) as in Definition based
on Ttr-
20

---

Published conference paper at ICLR 2025
Theorem 3. Suppose that, for some constant M, > 1, we have 1/M, S K,, K. S M, and [ 1 Ilap S M, Then, there exists constant C = C(M,) such that, for any (0, 1/2), the following holds with R + M,;
sup P( sup BR)
|RB R2 B.. E) Cpe
(24)
&.U.M.
Proof. The proof directly follows from the proof of Theorem with only one modification (14):
sup B Meet
sup Mc(o.M..
| B 1f 6,0 C..B 8M 2 26/
Cpe P6'
(25)
In Propositions 1, and Corollary 1, we treat T, as variable, which is a fixed point equation based on the covariance matrix and ratio between numbers of features and samples under ridgeless regression. However, under ridge regression, we modify the parameter Tur and define the asymptotic risk the same as we define under ridgeless regression based on this parameter. This means that can directly apply the results of Propositions 1, 3 and Corollary to ridge regression by only modifying the parameter r. Similarly, Theorem can also be extended ridge regression.
A.2 EXPERIMENTAL DETAILS
In the CIFAR- 10 experiment, we initially trained the surrogate models the training portion of the CIFAR-10 dataset. While training the surrogate-to-target models, we employed the predictions from the surrogate models. Conversely, when training the standard target model, all models were evaluated using the test portion of the CIFAR-10 dataset. It is important to note that the distributions for both surrogate and target are identical since trained and tested the models on the same training and testing sets.
utilized the ground truth labels. During testing,
We employ three distinct surrogate model sizes: big, medium, and small. The big model contains 127,094 parameters, the medium model 58,342 parameters, and the small model 28,286 parameters. All three models shallow, three-layer convolutional networks that follow the same architectural specifications. For the small model, x = 4; for the medium model, x = 8; and for the big model, x = 16.
Layer Type Conv2d
Input Channels
Output Channels
Kernel/Stride/Pad
3
3 3
ReLU
MaxPool2d
2/2
Conv2d
x
2xx
3
ReLU
MaxPool2d
2/2/0/0
Conv2d
2x
4x
3
ReLU
MaxPool2d
2/2/00
Flatten
Linear
64x
100
ReLU
Linear
100
We initialize the optimizer for our model using stochastic gradient descent (SGD) provided by the optim module of Py Torch. The optimizer is configured with the following parameters: learning rate set to 0.01, momentum to 0.9, and weight decay to x 10-4, Additionally, a cosine annealing scheduler, which adjusts the learning rate using a cosine function over 200 iterations, denoted T_ max. We batch size of 32 and trained all models over 60 epochs.
define learning rate scheduler, specifically
21

---

Published conference paper at ICLR 2025
B PROOFS FOR SECTION 4
Definition 2 (Omniscient test risk estimate). Fix p n Given a covariance Σ = U diag())UU) BB. and Then,
the noise term or, B B² Bx and define R. the unique non-negative solution of Σ 2, the omniscient excess test risk estimate is the following:
__
Rom(B) = BB-DXB.) 10- 1 o2= o222+
(12)
1-Ω
1 2 Σ (1-
T A
Ω=
where $
B(B)
In the following proof, we suppose that the empirical distributions of B and A converge as p having fixed the ratio p/n Then, we will prove that the omniscient risk converges to the asymptotic risk defined in (10).
Proof the proportional asymptotic case. follows:
Using Theorem 2.3 of Han & Xu (2023), we can estimate f as
E 1-12y,BB)B
B - B.
vp
where
σ 0 7 +1) B.1
1 A;
8~ I(0,pp,),
r2(B.) =
T is the solution to
tr ((E 7l) 22)
Let
(2 (-+ 21
xi = x;
vp
Using this estimate, we can calculate the excess test risk as
Rom(B) = B ((X) B) X2g) ((X; 1) + X28)
= B. (X1 - 1) I(X; - 1B. + "2xx X,7xX28
= - - -I) - IB. + tr XX,Xx)
(26)
Then by recalling the eigendecomposition for the covariance matrix UAUT, we have
X (UAU UAUT
= U(A -I) UT UAUT
1
= U diag
1+T
Using the diagonalization of I, X - -I can now be computed as
X I =Udiag
U
1+
Let's now compute
-T
I1B BB TU diag
U UUU U diag
U B.
1+ T A72
B.. As B U UTB., obtain that the RHS of the previous expression equals
= =B. U diag
(1 + r)2
1r23
(4+ B(B)
22

---

Published conference paper at ICLR 2025
Next, we write more compactly the terms tr (xx_xx, and (B,)). By defining the short-hand notation
Q = n -1)
E/=n (1 <i)², we have
B.BB))
B.BBm
tr tx(x;Xx;)
p
14
+
P
E=1
ATP + ΣE
BB,)) o² + -
-1)
0²
+²+
(1iTT)
Ω
Ω
1-
where 2. Hence, putting it all together in (26) gives the desired result.
Proposition 4 (Asymptotic analysis of T, and Q2). Let the covariance matrix E E B be diagonal and E 2, -- for 1 a. Recall from Definition that, as p 00, T₁ and are given by the equations
Σ
A 1 +1
n = Σ
n,
j
Then, the following results hold
T, cn (1 + O(=)))
for
ar (T/
(13)
Q - -O a
Proof. We start with the asymptotic analysis of T.. Along the same lines as Simon al. (2024), since monotonically decreasing function, we have:
_ is 7-+.
dx
1/a
+ +1
sin
Furthermore,
1/0
x
dx - 1 5
x
dx 5
sin (T/Oa)
0
x T,
x T
1-a T₁
1=l
Hence, combining these two facts gives
π
1/10 l
sin (T/a) T, 1/a
sin (z/ar)
(n + 1) (T/A)
na sin (T/a)
STS
π
which leads to the desired result.
Next, move to the asymptotic analysis of Ω. We have that
dx a(a 1)
nΩ
a² sin (x/ar) T,
+
IT,
Besides, since the summand is monotonically decreasing, we also have 1(a - 1)
1 2
a² sin (T/a) T, 1/0
-1
dx- 15
dx S
=n
30
r + T1
x +
7-a
+
T,
mm]
Hence,
1(a 1)
7,
1// 1 2ns
1a 1)
1/a
(27)
a² sin (T/a)
a² sin (Λ/
By the hypothesis on T,, have that
a sin (x/a) (1 (1-0(1)))
(28)
π
and plugging this in (27) gives the desired result.
23

---

Published conference paper at ICLR 2025
Proposition 5. Set the constants C₁ := a a'sin (x/a)
л(a 1)1/a and C2 := a sin (Z/O)
Λ va 1)1/a and assume the power-law eigenstructure Ln = === for < a. Let T, and Q be the solutions given by Proposition and define Tt_ A+t.' Then, the indices i for which 4 Q are nCi O(1); while the indices i for which is
2, < <11-9 Craeei i nC2 + 0(1).
Proof. Recall from Proposition 3 that we should identify indices which satisfy the condition 2, > 1 to decide if we' re better off not selecting this dimension i in the surrogate model. Furthermore, Proposition 4
gives that Ω Q-1 O) Putting these together, have
a
G 1- Ω
G > d where c' c'= 1 =
+
7720
(T, + inp
(T,i" + 1)
TTpp 2,' +c¹
c' 2
c'
c'T,T"
>
vT-c
c-c
ve
7/(1 Ve)
Ve
1/a
i> r,
1/a
Ve
As c' 1 + O, we get
v
1/0
(vo-1ata (1 O)n Incorporating (28), we achieve that
[-
Ve
1/e
sin (z/a)
1/u
= π Va- - 1)1/ (1 O0n = nC2 O(1).
Similarly, by following the same procedure with the initial inequality & > Q2 we get
sin (z/ar
4 > 1-Q = i> nC + 0(1, where C
π(a 1)
In Figure 3, we compare the empirical results with theoretical predictions for the number of features that meet a sin (π/O²
the selection criteria in the optimal mask M C < 1 Q2. The theoretical value, calculated πς( Va 1)1/a
ignoring the 0(1) term, aligns well with the experimental data and the accuracy in estimation increases with a. Notably, our theoretical estimate also closely matches the empirical results when the sample size is small relative to the feature size p.
Proposition 7 (Scaling law for masked surrogate-to-tare model). Together with the eigenvalues, also assume now power-law form for B. that is 1B i for B > 1. Then, in the limit of co, the excess test risk for the masked surrogate- to-teee model with the optimal dimensionality has the same scaling law as the reference (target) model:
Rom 2 O(n (B-1) ifß < 2a + 1.
and
Rom BB ) O(n 220)
iʃB> 2a
24

---

Published conference paper at ICLR 2025
Features in Optimal Mask M
500
Empinical g=1.5
Thearetical g=1.5
400
Empinical e=3.0
3.3.0
Empirical
300
Theoretical 4.4.5
200
100
50
100
150
200
250
300
350
400
450
Sample Size
Figure 3: Comparison of the empirical and theoretical number of features satisfying the feature selection sin (st/ar)
condition in the optimal mask M (2) < 12).. The theoretical value is calculated as n πí va 1) ignoring
the O(1) in Proposition 5. Setting: The feature size is 500, and the feature covariance follows the power-law structure 2; 1- for 1.0, and 4.5.
Proof. As discussed in Section 4, in order to analyze the model's inherent error, we need to set o7 O(n where y the exponent characterizing the scaling law of the test risk in the noiseless setting. We will work this proof in two cases depending on f and 2a
Case 1: 2a 1. In this case, it is previously stated by Cui et al. (2022); Simon et al. (2024) that the test risk of ridgeless overparameterized linear regression can be described in the scaling sense as err = O(n 00=)) when B 2a 1. Consider the optimal mask operation M mentioned in Proposition 3 that selects all features satisfying - 2 > Ω. Let Ps be the number of selected features. We can then decompose the risk estimate in Definition 2 as follows:
B(B 022
ΣE AG,9; + EP A2,,, + +0,2 errl err2 + +/2
1-
1
- Ω
where errl and err2 are the contributions to the total risk the target model from dimensions selected and omitted in the surrogate model, respectively. Therefore, we express the total error as:
errl err2 of
err O(n
1
Going back to Proposition 5, know that, as p - oo, the criterion for selecting feature in the optimal masked surrogate model is given by
a sin (T/Or
i<nC2 + 0(1,, where C₁ π( Va 1)1/a"
err2
Define now σn = nC2 + 0(1). The equation (18) tells us that after the optimal mask operation M, replaced by err2', which calculated as follows
is
1- Ω
err2' Σ 1
P
Since 8 is monotonically decreasing function, we can bound the summation by the following two integrals:
p--1
x
dx
5
8
x
dx
w.+1
wh
(w,, + 1) 1)-
(p+ 1)-
(wn) Bp+l
p+1
8
B-1
B
u1+1
25

---

Published as conference paper at ICLR 2025
In the limit of p - oo, we obtain
err2' = B(1
Thus, we have tightly estimated err2'. Using the fact from Proposition 4 that 52 @(1), and our assumption the noise variance o7 = O(n-+t)), ), we conclude that the scaling law doesn't 't change for the surrogate- to to-target model as
(B errl + + + err2' O(n 811).
1- 5
Case 2: > 2α 1. In this case, we show that the scaling law is determined by errl, hence changing err2 to err2' has no effect in the scaling sense. From Proposition 4, we have the asymptotic expression
1
T = cn (1 + O)n for c sin (x/aa)
We can argue that there exists positive constants C < < c
c
1
such that cn11 = T
S c2n". We have that
i-8
errl
(1 + iam)
fa-B
We
pa-
(itt + cintt
en
1=1
This implies errl = 2(n-20) At the same time,
1-8
2a-8
errl=
( + c2
T
po-B
pa-B
(ww)) + c2nur
n 20 (wwn/)) + c2)
Using wn/n @(1) gives errl = 20) and we can conclude that errl O( -2), From Cui et al. (2022), we already know that err = Onn-2a when B > 2a 1. Using Ω @(1), and our assumption on the noise variance o- 0(r-2a) allows us to conclude that the scaling is dominated by errl, and thus, the scaling law remains unchanged.
Proposition 6 (Scaling law). Let the covariance matrix Σ, be diagonal with eigenvalues 2, and let the ground-truth parameter B. have components B, corresponding to each feature. Assume that both eigenvalues d and signal coefficients 2,8; follow a power-law decay, i.e., AB; 8 and 2; = for a, B > 1. Let the optimal surrogate parameter 8 be given by Proposition I and define the minimum surrogate-to-target risk attained by 8 as RB,.((()) min (B where Rom(B is described in Definition 2. Then, in the limit
of p + co, the excess test risk of the surrogate-to-- -totarrg- model with an optimal surrogate parameter scales the same as that of the standard target model. Specifically, we have
(B On Rom(BB)
if < 2a + 1. ifB> 2a
Rem 2B On 22) Rom (B')
Proof. From asymptotic risk decomposition in (34), write
Bg, F(X' o B., g())
(8" -B) 0 E,0 - BB) (
+B. 0,) 0 E, E, - 2B, (1)-0)))) -B.) E0,,,),,100
26

---

Published as conference paper at ICLR 2025
Target Risk
2x10
Target Risk
Optimal Masked Surragate-to larget Risk
Optimal Masked Surrogate-to-Taee Risk
Optimall to Risk
Optirall Surrogate-to Targeet Risk
10
x:10
10-2
40
10a
10a
Sample
Sample Size
(a) Test risks log-log scale when p 500
(b) Test risks in log-log scale when p 5000 > n
Figure 4: Scaling law behavior of the test risks of optimal surrogate models. (a): Associated test risks function of sample size in log-log scale. Setting: The feature size is p = 500; the sample size n changes from 50 to 450 with increments of 50; the feature covariance follows the power-law structure A; 1 1.8 i (b): Associated test risks as a function of sample size in log-log scale when p > n. Setting: Same as in (a) except that p 5000.
since we can put in the form of (a b)2 c c. At the same time, know that
of + +i T.1) B.IB tr (E, + +1)
x2(8") Bg,0),,,0
K
1 tr (2, + +,,)-
n
of + 12, +,,)- B112 nΩ
1- Ω
P
0f
Recall the optimal surrogate vector discussed in Proposition and the corresponding minimal surrogate-to- target risk R.m (B.2). In this case, we can write
Σ A 2
(1 (1-5)
AB. (a1 (1- -
Similar to the previous proposition and as discussed Section 4, to analyze the model's inherent error, we set of = 7 where y is the exponent characterizing the scaling law of the test risk in the noiseless setting. It is previously stated by Cui et al. (2022): Simon et al. (2024) that the test risk of ridgeless overparameterized linear regression can be described in the scaling sense err O(n f+1) when B 2a + 1. We will proceed by considering two cases based on the relationship between B and 2a + 1.
Case 1: 2a
Consider the interval of i's satisfying &i > 1 Q and 27 <
Q. By Proposition 5, we have
a sin (π/a)
4 >> 1 Ω i nC + O(1), where C π(a 1)
sin (T/a)
1-
nC2 + 0(1), where C2 π²( Va 1)1/a"
Let wn, be defined as in the previous proposition and define d, = nC, + O(1). Then, the interval of interest corresponds to the set of indices such that On < < wn. Within this interval, we observe
(1 - (1-6)
V(1 (2) (1 1) = kj
Ω
Ω
(1 (1-2)
2 <
k2
1 Ω
1- Ω
27

---

Published as conference paper at ICLR 2025
Using the fact from Proposition 4 that Ω = a-1 bounds, we obtain
O(n tells us k +(1) and k O()) Utilizing these
Ω
(1-2))
(1 2
Re om (Ba2t)
2
AB ((1 ((1-
2
Ω
{i> + (-25))
1-
Ω
(1 (1-2)) ki>
1-0 2
[=]
Ω
6
-
ki
2 1- 0
k2
2 n -+1 kj
Ω
(dn/n) /--1
(wwn/n) (w)//))B++1 BB1
k2
B
On -811)
where (a) follows from the fact on/n = (1), /./n//nnnn / ()), and Ω = (1). This implies that
R (B 22(
Recall that the optimal surrogate-to-target improves over the risk of the standard target model, thus R (B:r)) We therefore conclude (Bx = O(n B+1) for this case.
Case 2:
2x 1
In this case, we have
Ω Ω
Σ
(1 4
Ω
(1- -i)
R. am BB
2
A
((1 (11 + -.))))
1- Ω
((1 (11 + F
1m1
2
8
P2
(1
2 1-0 (1 (1-
El
where k3
ql )1+)) (1-)) = @(1). From Case 2 in Proposition 7, we already know that the same summation
with upper bound Wn rather than on scales as Onn Yet, since dn and w, have the same order O(n), the result remains. This gives (B Q(n 22), which eventually yields
Ru 21 S Rom O(n -0) = Rum (B = O(n O(n-2).
Hence, this allows us say that the scaling law doesn't 't improve even with the freedom to choose any B
In Figures 4 and 5, we illustrate the scaling-law behavior of the test risk. In Figure 4a, the sample size n varies from small values up to values close to p. Even though a linear trend is observable for smaller values of when p = 500 in the log-log scale, as n approaches p, it is less apparent due to finite-sample effects of p. We note that the asymptotic approximations in Propositions 4 and 5 rely on p being significantly large compared to n. Thus, Figure 4b considers the same experiment with larger dimension (p 5000) and the same range of n values to satisfy n & p. In this scenario, we observe a clear linear behavior in the log-log plot, which is consistent with the scaling-law results presented in Proposition 6.
In Figure 5, we analyze the scaling-law behavior of the test risk under a two-stage framework where the sample sizes m vary relative fixed dimension p = 1000. In this scenario, observe similar linear behavior in the log-log scale when m = n is sufficiently small compared to p = 1000. Whereas, as the gap between
and p diminishes, the linearity in the figure disappears as the asymptotic approximations in Propositions 4 and 5 require p to be significantly larger compared to n. These observations align well with our expectations and results in Section 4. Proposition aNon-asymptotic analysis of T). Suppose that E E RPKP is diagonal and Ens = d; = 1- for 3+ 2-a
1 < a. Assume that n for
4 2- 2) ITT satisfies
A n,
4 + T,
28

---

Published as conference paper at ICLR 2025
Thsoratica 2
EEper martal aw
10-1
Exper mental
Thsoratical arm
Lper mental
10-
10a
10
Sample Size (n=
Figure 5: We compare the experimental two-stage risk with our estimated theoretical risk in log-log scale to demonstrate the scaling law, Setting: The feature size is p 1000; the sample sizes change from 50 to 900 with increments of 50; both feature covariances follow the power-law structure 2; = i- for a = 0, 1.5 and 2; the ground truth parameter B. is specified B: 1.
then on S c((n + 1+ ) for c= aa (TT/a) "
π
Proof. In similar vein Simon al. (2024), have:
L" x
n=
dx
J0 x" + dx=
T lia
sin (M/a)
Since the summand is decreasing, we bound the Riemann sum by integral, thus:
11 nptl
x
dx
x
x
x
x
dx
dx
dx
J0
x + T,
x= + Ti
pp- x- T
π
1//0
x
dx
p+l x dx
x
a sin (TT/a)
0
x +
π
1//
dx
sin (TT/a
p+1 + Tyx
π
1//1
T22" dx
sin (T/a)
7, m-1
π a sin (T/a)
-1/u
at + T (p 1)+11
π a sin (T/a)
1/a
a --1
Recalling that 1 and assuming T, < p", we derive:
π
1/a
p+1
$ n S
π
1/a
sin (T/
a-1
a sin (T/
na sin (T/a)
nn + l
p+l a-1
a sin (TT/a)
|.-
π
π
29

---

Published as conference paper at ICLR 2025
We conclude by proving that 77 < pp. For the sake of contradiction, assume that r, 2 p". Then,
2/2
T
T
I T
ipp2+1
p/2
1
2
1
1 +
F=
+
1=p/2+1
2a
1
3 +
2
4+ 2
which contradicts our assumption that n < pk.
Proposition (Non-asymptotic analysis of Q2). Suppose that Σ RPXP diagonal and Dns = 2; 1 for
a²
1 < a. Let T, be defined as Proposition 8 and assume that pkı
n < for kn (a 1)
and
(a- 1)2
3+2
Let Q be the solution to k2 2-2-1-22
P
d
n
T
Then,
p-1 20-1
Ω> -
1
n 1+11 1
a-1
a p+1
Proof. Since the summand is monotonically decreasing, we can lower bound the sum by the following integral and manipulate:
pp+
x
n
dx
Ti
x-
+ T,
x"a
x
x
xp
xp -
dx
0
x T,
0O
x
1+4
1/1
X
dx
000
x
dx
a² sin (T/a)
0
- T,
p+d
x +
a(a 1)
1/10
dx
a² sin (T/O)
1
p+l
æ(a-1 1) a² sin (T/aa
1//
dx
(T pel
a(a
x 20+1
1/u
a² sin (T/a)
-2x + p+1
T, (p 1) 1)-20+1
1/a
T,
a² sin (T/a)
2a
30

---

Published conference paper at ICLR 2025
Let's now utilize the upper and lower bounds for r, from Proposition 8. Substituting, we have
n2 a(a- 1) sin (X//O)
(p 1)-2011
a² sin (T/a)
π
2a
s(a T, 2 1)-2a+1
a
20
n1a 1(a-1)
12 1+ p+l
a (T/a)
20
p 1 2
+ x(p+1)
Dividing both left and right-hand side by n gives:
1 p+l
ar sin (T//O)
Ω a-1
+
a
x(p+ + 1)
n22r 1)
n1
a
1
1
g-1
ptl
a-1
p+l
20-1
2
+
2n-1
11
0-1
a
p
since sin (T/O) 1 for > 1 and n
1
p+1 o-1
20-1
by our assumption on
Proposition 10. Under the assumption that
1/0
(
max 2a. p Paa-13 1)2
a² (a 1)2
min
(p + 1) 2
a D
4
3+2
1+22-0
2-0-2
.P
a sin (1/a)
a
p
and 4 < a, we can find a masked surroaatett--trgee setting that improves over the risk of the standard target model by selecting all features i such that 27 1 Ω
Proof. From Proposition 9, we have
p-l
20-1
1
Ω
a-1
It's then enough to show that we can find a set of i's such that
p+l
20-1
2
p+1
From the proof of Proposition 5, we know that
Vc
1/a
G>C -isr, 1/a
Hence, using the bound on ,, from Proposition 8, it's enough to find indices such that
sin (IT/O)
p+1
1/e
( n
pel
2a-1
n +
where d'
(29)
π
a
ve
p+1
31

---

Published conference paper at ICLR 2025
vF 1/a
By assumption p + > n when 0 S x & 1, we have
p+l o-T
and > 2a, we obtain that 2/2
c' Since
is increasing with
1-
1/a
Ve
1/a
2
vc
Then, to ensure the existence of interval of i's satisfying the above inequality, choose
sin (TTaa
sin (T/a)
p (p + 1)
2 (n
alar 1)
2x
π
1/a
p+ n
sin (Z//)
which follows from our assumption on n. Thus, discarding the features provided in the interval (29) will strictly improve the test risk of the masked surrogate-to-targel model over the standard target model. O
One can verify that our assumptions are coherent because they ensure non-empty interval for when a 4 as the coefficients of p are positive and is smaller compared the other three coefficients of p in the
(a - I)²
minimum function.
C PROOFS FOR SECTION 5
Theorem 4 (Distributional characterization, Han & Xu (2023)). Let K, = p/m > and suppose that, for some M 1, 1/M K, s M and [|E.llop || 1l.p M. Let T, R be the unique solution of the following equation:
dg - tr + +T,)
(30)
p
We define the random variable X x. 8:) based on N(0. 1) and the function follows:
RR - R as
Kn, B.. == (I, T,I) B. + Σ, y,'22y((448,,
VP
(31)
r.B.) == K, (07 Bg, (X² koo ( Bs) B.)
Then, for any I.piischtt function funcciioo f: TR R where I. < I.M), there exists constant C = C(M) such that for any 1021/2], have the following:
|1( If(" (lf(xx,,;(00an (E..Br g:D]] 8) Cpe Pétic B.BBUR A,4[0,M]
sup P( sup
(32)
where R M.
Definition 3. Recall the definition of T, and y, in Theorem 1. Let K, p/m > 1 and define T E B. similarly to Tr We define the random variable Xs based on g. ~ N(0, 1) and the function RR - R as follows: k,o
B...B..g == (E, TG+ - B, Σ. 2,112y,(B.)8.
X k,,r
VP
(²(B.) == (0? + Bg, 11
(E. Br, B.) BB)113)
32

---

Published as conference paper at ICLR 2025
=k, Σ (2,, L,), and o = o.). Then, we define the asymptotic risk estimate as Let == =
(x. = 11 (1 (2, + 1 E + T, -1) Bull + Eg [x((
P tr (Z,
+ B2(B)) tr tr(2! + L T,) L, + T.) (T,
Theorem 2. Suppose that, for some constant M, > 1, we have 1/M, S K. Kr of I M, and [ES/lop || 11E ||==11 II.pp I M. Consider the surrogate-to-turyg to-ter model defined in Section 2, and let RiB represent its risk when B. is given. Recall the definition of k, and Re in Definition 3. Then, there exists constant C = C(M)) such that for any & (0, 1/2), the following holds when R 1 < M2;
- - - (2. 2 8) & Cpe
sup B.EB,l8)
Proof. Define function - R as (x(x 12 (x B.)l The gradient of this function is [xx(ll) = (x B. )ll s 2 21/2 ||x Ballz-
Using Proposition 12, there exists an event E with P(E") S G, where C, = C,(M, "x²) with the definition of M, in Proposition 12, such that 21 is 2M,-Lipschitz if B. E (R) Applying Theorem 4 on the target model, there exists a constant C, (M,) such that for any E (0. 1/21, we obtain
sup
P ([1(02) - Bg, K B., B.)1 (..BB..))11
2 E
Cpe Cpe-
(33)
e M
where /( R(B: and
Σ, 1/2 Σ- x(')) g:
x xo (Z. - (E, + B k
vp
Furthermore,
Eg f(x Nio,
(I, g:))
BB [1E] - (1-))(10,))811 + (B'
=B' -B) -B))+ xB 1
+ (I-T(I-)) E1 0DB, - (1-0,) BB).
(34)
Let E(M,, M be the event defined in Proposition 11. Let f2 RP R be defined as fxx) == -B) 0 (x - B.). By Proposition 13, the function fa is
where 0, := -E, + T and 0 = (E, 1
12 & vD
- if B. E (R) on the event E(M,, M- ). Applying Theorem 4 on the surrogate model, there
- exists constant C,, = C.., such that for any & (0, 1/21, we obtain
01 (1- sup P ((5(B) B. TI ()) B,
1 (.B.) Eg 100000000000 8) s Cw,ipe pet
(35)
where 1 == (E, + +,,I)'1, and O2 : (E, + T,I) د 1/2 g.
VP
Let f : R R be defined as fx(x) (x E,00, By Proposition 14 and Proposition 2.1 in Han & Xu (2023), the function fa is 4.ps-ipse if B. E BR( on the event E(M,, Mr-R ). Applying Theorem 4 on the surrogate model, there exists a constant C..2 = C,, (M, such that for any & E (0, 1/2], we obtain
sup 8,
E) S pettpee
(36)
33

---

Published conference paper at ICLR 2025
Let f4 :R as /4(x - (x) BB). By Proposition 15 and Proposition 2.1 Han & Xu (2023), the function fa is -Lipscht if B. E B((R) on the event E(M, M,-R Applying Theorem on the surrogate model, there exists a constant Cw.3 = Cw.3(M,) such that for any & (0, 1/2], we obtain
2
- (I (,) nB.]] > 5 C...ee po (C...
sup B,EB,(R)
(37)
By the definition of these functions, we have
(.. Ezi s(x Kor (E, 8.))
01). -2(B') (108))+((B)))) fa(B"
(38)
By the definition 0,, 02. 11, and 22 we have
(E.B.) - ( " 0.p. = B. - -:--001000000000-0000-0000111000
xx 10,1,01 (I- L,D -B.
(39)
Using (38)-(39) and applying union bound on (33), (35), (36), and (37), we obtain the advertised claim. Proposition 11. Suppose that, for some M, > I, 1/M, s K,. M, and |E ||=5 s M, For every C > 0, there exists an event E(M,, c₂) with P(EE(M, c,)) s C,e where C, C,(M,, c,) such that
1l N 11a112 + c, and I|B" - B-ll2 s [B + cx.
Proof. By the definition of B", we have
B' = 8'=XXXXXT' ('
= =XXXXX XB. X (XX")-
(40)
where غ I)), By triangle inequality, we obtain
11 = | XBall2 + 1| (XXT)-
1Ba112
(XX y žll2.
(41)
where (a) in above follows from the fact that X (XXX)) y X is projection matrix, and so all of its eigenvalues are either 0 or 1. Focusing on the second term of the RHS, we derive
2
XX
(X 211 =
vp
VP
(0)
&
XX
(42)
p
P
where (a) in the above inequality follows from Cauchy-Sehie Sehcaa- inequality. Using Berstein's inequality, there exists an absolute constant Co > 0 that depends on o such that
z p
pr pr
|
P
0² >1 s exp
mimnn
|C,
2C,
On the other hand, let 7 XΣ, with zero mean and unit variance. Then,
which means that the entries of Ž are independent and normally distributed
XX
žΣ,2
72
=
$ Σ
(43)
P
p
34

---

Published conference paper at ICLR 2025
Using Theorem 1.1 in Rudelson & Vershynin (2009), there exist absolute constants C1, C2 > O such that we have the following for every 0
22
_
P
$ E²
1-
2 (C₁E)--mtl t
(44)
Ks
By combining (42), (43), and (44), we obtain that
(11'1l2 s ll2 + e(1
( (pg)
K2
-emin N² "0
S {CGE))- te e te
The advertised claim for [B'1l2 follows when e is selected as Cic. For l1B" -Bxl22. using the definition of B", we write follows:
118 B+ll2 IXT Xp. 8
$ [X'" /1121BBl12 + (XX"()
1B+112 11 )
(45)
where (a) in the above inequalities follows from the fact that the eigenvalues of X X are either or 0 as the eigenvalues of X (XXT)-1 X are either or O. The remaining part this proof is identical to the previous part.
Corollary 2. Suppose that B RPP is given, and for some M, 1, we have 1/M, z o, s M, and |_ || M, For every c, > O, there exists an event E(M,, c.) with P((E(M, c,))) s C. where C, C,,M, c,) such that
1 1110112 +
and 1 BB'll 11 +
Proof. The result directly follows from the proof of Proposition 11.
Proposition 12. Suppose that, for some M, 1/M, K, M, and lopp || IIpp S M, For every
> O, there exists event E(M,, with c())(M s C,e where C. C,(M,, c,) such that we have the following on this event c,),
11 S 11 + and 1 Ball2 s 1Bal2 +
Proof. By the definition of 8 we have the following:
8 x(XXT)" XB + + + (XXT)-1z
(46)
where z N(0, o. Plugging (40) into (46), we obtain
Bdd = X(XX)) x
(47)
Note that X(XXT--XX X and X & are projection matrices. Multiplication of two projection matrices results in a projection matrix. Using the fact that the eigenvalues of a projection matrix are either or 0 in (47), have
1 z 1B4112
1| [ + |X (XX(XX")-'2 z/12
(48)
By a similar reasoning used in (42).(43), and (44); there exist absolute constants Co. C1, C2,0 > 0 such that have the following for every 6, 0:
P (IIXT s a(1
K
(Ci + pcs -emin x2 x
(49)
35

---

Published conference paper at ICLR 2025
Similarly, for every & > O, there exist absolute constants Co. C1, C22 > such that we have the following for every f:
((IX)(XX)) s 8(1 - (
min
(Caa)mml + -op +
(50)
Note that X, z. X, and ج are independent of each other. Therefore, we can apply union bound on (49) and (50) with selecting e, E, and such that < Eie² a(1 2 ( (t + | loop & T. and
< a(1 - 1.) ( o -ام 1lop As result, there exists an event E with P(E) S C, G,) such that
11 s 113.112 + c,. Using similar argument in (45), derive the following the event Ej
1B BBll2 s 1l
This completes the proof.
Proposition 13. Let - R be function such that
g(B") := 1 (E, +T,I) E,, -Ba11
22]
Then, on the same event E(M, c,) in Proposition 11, the function g (1BB cs) (s),)" Lipschitz where d the largest eigenvalue of Σ..
Proof. We take the gradient of the function g:
(V2( 2|1,,E, + T, EE, +T,I
BBDll
21
max
(4: 2,)
T;
|88 - B.ll2 max 24: 1
22
11' Ball2 (Λ1 T,)
Combining Proposition 11 on the event E(M, c2) with the above inequality provides the advertised claim.
Proposition 14. Let RP - R be a function such that
s(B')
|
P
Then, the same event c,,,,c, in Proposition 11, the function is L-Lipschitz where (2) are the eigenvalues of E, with a descending order and
4T²
1
IBall2 + C,
L
m (di
T
EP_ (1,tT))
Proof. We take the gradient of the function
Vg(B">
2 22/
+. (
- +x7,1,
p
36

---

Published as conference paper at ICLR 2025
Note that
x²(8) =
k. k.
Bx, 1/ (X xx B Bx)l())
= K3 of + r,, -,,1) 1T1
1 -r (Z, + +T,1) 22,)
Then, we have
- (E, + r,1) 1B8 1 tr (Z,, + T11)-
Vyi(²) 2x;
Plugging (B) into Vg(B"), ) we obtain that
VVg(B'112= = 4T, =// (2, + +T,1) +T,) + 11
1- -- +,
s 4 27
118 l12
(41 7,)²
ΣP (1++7
m
Combining Proposition 11 on the event E(M, c2) with the above inequality provides the advertised claim.
Proposition 15. Let getg: ""->> R be function such that
&(B') 2B." (1-(2)) + E(C -B.).
Then, the function is 211T
A
-Lipschitz where di is the largest eigenvalue of L,
Proof. We take the gradient of the function g:
IVg( 2E, + T,I) (1 (1- (E, r,1) -,,))',,) Bul12
<21 1l,T, max
1- 1; + Ti
d
12TT,
21 T,
and the desired result readily follows.
Lemma 1. We have that
of 7,,1(E, ((E, ((E, 7, 'E,
Ex-x b bx:(')) = =;-- 1- -tr ( +1) xス?
(B.) tr tr(x!/ + 1/2 (Σ, + +
(E, + + 1x!
tr (E, + T, 2
37

---

Published as conference paper at ICLR 2025
Proof.
The desired claim follows from the following manipulations using the definition of X in (14):
4,00
K of + +, +,,1
Bp-xx wny
Bxx
m
-- - (
of + T7 T, //2 (2, + T 1I (2, (Z)+ ys(B))g// vD)
g
K
1 tr (,,+
o7 + T, T, 1 (EE + +,,1) -E,I1,,,,,11
= Kg
tr tr (E, + +
(B.) tr [2! (I, + T, - 1 (2, + 7, 3
(2, + 7, +, 11!
p
1 tr (Z, + T,I) )
C.I ANALYSIS OF TWO-STAGE MODEL IN UNDER- UNDER-PARAMETER PARAMETRIZED REGION
Proposition 16. Consider the two-stage model where the surrogate model is under-parameterized with ps S p features (m < Pa) and the target model is over perammaamtteiiee (n > p) with p features. Then, the difference in the asymptotic risks of surrogate- to -attarget and standard target models is:
of K. +
(B.) 0 (B.)'
tr +((B)) (I- -,0,) (B.)
Ω o:
- 2 (I, + 1,11) 1 (B.Y11)
+ 1
where 0, = (E, 1) 'E, Ω 1 tr 2 (2, + .) and (B.Y = 000 ... Bp Bp,t Bp] E ERP.
Proof. Let == (I,+T,1)- - |22² & where g, N(O. Ip). Then, by Equation (10), the asymptotic risk estimate
vp for the single-stage linear regression is given as:
R.do B..BB (B' B.) O, - -B.)
B, + - 0,). 2B. (1) E,,,,, [ -B" BB.)
(51)
For the ease of the analysis, define
5-1/2
1/2
OpM(P-P) ((p-p)x(p-p))
E PRP
B
B 0p-ps
E ER.
g.
g: Pp-p
E RP.
0 Ppppp
Let B. = B. (B.) be obtained by setting the last p Ps entries of B. to 0. Then, by Theorem of Chang et (2021), since the surrogate model under- panderraaameterized,, the following asymptotic estimate for the surrogate model obtained after this stage holds:
Σ 1/1 B,
B + +o,
(K --
where g, ~ NN0, Ip). Let = (K,, Σ = (,, M,, and (03 o?). Thus, plugging this surrogate parameter in the asymptotic risk estimate for the second stage gives:
Σ
1112 8
1-122 g, Σ, (B+)' -0,
tr 1r(2/E,, + -
Re, = Bx, (B.)' U.
+
(B9)
vp (K=1
vp(x, -
p
1- 8,
+ +B. TI - (1-0)) E1, 0, BB. Ex,
2B. T(I
E,,
0 Vp(K1' -1)
(Ba)'
38

---

Published conference paper at ICLR 2025
where
++)) P
0T, 1,1/ 8. 112
xB- of + r,11(2, + 7,1)"12)
vp(1,--11
tr (I, 771))
1-Q
Further modifications give:
of tr (2,1,2,,,,0, |,0,
= (2.(( 0 (B.)+ + p(, -
1-Q Eg P + +()) |-/1111/ + 0 VK 1)
Ω
Σ, 8, 11
+ + I[ -0).. + 2B. (1-
- (1) '2,', 1,0 (B.)
(B.)" 00 (B.) p(,---1)
tr (0) (,T,,1
Ω of + 1, + T,1) 1! B.ll; + (K, - 1) 7 (I, T, -,,;,,,,,,))
1 Q
+ B. (1 - E - 2BB)) (I (1-01) 1--0,)',0 (B.)
Then, using the fact that since (B.)' is orthogonal to B. (thus, their supports do not overlap), it follows that the difference between this surrogate-to-tate risk and the standard target model risk is:
of (k, - tr (0 2,0,, 2 (1 E,0,
Difference = (B.)* 0 0 (B.)
(52)
Ω
of 7 tr
-,11 .. 2 (B.Y113)
1 Ω p (Kg
This completes the proof.
Proposition 17. Consider the two-stage model where the surrogate model is uuaaee-urrameterized with p features (m < p) and the second stage is pverpparameterized (n p) with features. Under this setting, the perrogate-to-targe model cannot outperform the standard target model in terms of asymptotic risk.
Proof. Let 0, == T,,+ and 0: := T,,) 1/2 &. where g; N(0, Ip). Then, by Equation (10), the asymptotic risk estimate for the single-stage linear regression is given
Riys B..B..B' - 0,),0.0000008 BB) 72 1, 10,001
(53)
+ - 0,)8. 2p. (1..((-60 01- ( -B.).
When the surrogate model is under-parameterriee, we can use the following asymptotic estimate for the surrogate model obtained after this stage by Theorem 3 of Chang et al. (2021):
Σ, 1/2 8,
B' = B. a (K (
where g, I,O, Let k = (K,, k)), E ,,,, E,, and x = (o, Then, by plugging this in Equation (53),
the asymptotic risk estimate the following:
tr (I7 + +,1))
R2. Ey,
- ",000,,,,, g, (3")
p(x]1
p
+ +B, T (I (1-00) 0,
-Bg,
0,
B. (I 01) Σ, 1/2 8,
Vp(K.' 1)
39

---

Published conference paper at ICLR 2025
where
7, 1 0 E g 21
xB')) = + T, +T
vp(
tr (I, 7,1)-
1-Q
Further simplifications give:
of Re (2, p(K,1 tr (2,,000010001111
Ω
of Bg,
H,C,, T,1 (B, t
Σ,
11
1- Ω
Vp
+ +B. (1 - 2, 01 of
P. p(k
)]
o 1 Ω tr [z, -,,0000
Σ
Σ An22
(K,) - 1)
o + >1=1 2r1
1-Q
which the asymptotic risk estimate of the standard target model (follows from Definition 2 or by simply plugging B" = B. in Equation (53)). Hence, we conclude that improvement over the excess test risk is not possible when the first stage is muder-parameterinee with p-dimensions.
Corollary 3. Consider the setting of Proposition 3. Let E, be the covariance malrix the target model and let M be the mask such that the surrogate-to-targe model with Σ, and M oulperforms the standard target model in the asymptotic risk. Let Σ M(x(") where N(O. Σ,). Then, for any B. RR,, there exists K E N such that the surrogate-to-targe model with two stages given I, E, Ba. and m K outperforms the standard target model.
Proof. We make the following three observations. First, the expression in (52) is continuous with respect to m R when m > p. Note that m a natural number in our setting, but we consider the expression in (52) function of where E R. Second, the expression in (52) monotone with respect to since tr (0 E,,, 2 and T f/ (C, + 7,f) ",,,') 2 Third, by definition, target model with Σ, and M outperforms the standard target model the asymptotic setting. This means that the standard target model with two stages given I, E, and B. while mr approaches oo outperforms the standard target model. By combining these three observations, the desired result follows.
know that the standard
40


Reviews:
[{"review_id": "UDmNf2ZgZ1", "reviewer": "Reviewer_E9SJ", "summary": "In this paper, the authors propose a precise characterization of the benefits of knowledge distillation, mostly in the context of gaussian linear regression. In particular, the main set-up considers the excess risk of linear regression on a given distribution, but with the learner only able to access pseudolabels generated by a surrogate model instead of the true labels. Notably, the authors show that under a covariance-shift model (i.e. the distribution of covariates $x$ may change between the surrogate and target stages, but the underlying predictor $\\beta_\\star$ remains the same in between), then the optimal surrogate predictor minimizing the (asymptotic) excess risk on the target distribution is a weighted version of the ground-truth predictor $\\beta_\\star$, which which amplifies entries corresponding to large eigenvalues of the (diagonal) covariance matrix above a certain threshold, and shrinks entries below a threshold. Furthermore, in a masked setting, where the surrogate model is restricted to selecting a subset of the full set of features, then similarly the optimal surrogate predictor selects predictor entries above a certain threshold of covariance eigenvalues. Lastly, the authors show that in a certain asymptotic regime, an optimal surrogate-to-target model (i.e. a model trained on target distribution covariates with surrogate model pseudolabels) has the same excess risk as the least-squares target model trained with the true labels, demonstrating that knowledge distillation in a sense cannot beat out ERM with access to true labels.", "questions": "In addition to the points above that should be clarified, I have one following question: how is the CIFAR-10 experiment performed? Notably, how are the surrogate and target distributions generated? This is worth expanding in the paper.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper is rather well-written and contains quite a few interesting theoretical insights. The results draw clear delineations on how knowledge distillation through a surrogate model can help. As someone who hasn't thought about overparameterized linear regression in a while, Proposition 1 and Corollary 1 were rather surprising results, demonstrating that for a dataset size proportional (but smaller) than the number of parameters, the optimal surrogate predictor to use for generating pseudolabels is actually not the ground truth predictor, and that there is (in theory) always room for benefit as long as the covariance is non-isotropic, which implies that a learner benefits from using something other than the actual distribution of labels. \n\nIn addition to the theory, the numerical results on CIFAR-10 also counterintuitively support that a learner only trained on surrogate pseudolabels on the target domain actually outperform the surrogate model itself, which has access to true labels (albeit with a different covariate distribution...?).", "weaknesses": "Though the theoretical results are interesting, there are a few aspects that are worth clarifying. Notably, even though it is demonstrated that there can exist a surrogate model that induces better risk on the target model than using the true labels, in general a surrogate model is typically not trained with foreknowledge of the task distribution. I believe this is what Section 5 is trying to convey, but it is not clear to me after reading that section how to interpret the result therein. In particular, it should be explained how this relates to, for example, a target model that is trained using strong labels to demonstrate the marginal gain (or loss).\n\nIn general, the paper accrues a lot of jargon and notation; it would be very helpful to either create a table containing the different set-ups/regimes considered and the summary conclusion of the relative gain/suboptimality of knowledge distillation and/or a notation table that summarizes what the various risks denote. This would help clarify how to place the scaling law (Proposition 5) and Section 5 with respect to the results of the prior sections.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vZZEmim13t", "reviewer": "Reviewer_GbMC", "summary": "This paper studies the problem of knowledge distillation under linear regression. In the first stage, data are collected from a surrogate model. In the second stage, a target model is trained using the data generated in the first stage. The authors characterize the non-asymptotic excess risk of the target model under \"model shift\" setting and \"distribution shift\" setting. Numerical results are provided, justifying their theory on ridgeless regression and on neural network architectures.", "questions": "1. Can you provide intuition why the risk of the surrogate-to-target model under the optimal selection of the parameters scales the same as that of the target model (even though there is a strict improvement in the risk)? I am wondering why improvement is possible. Is it because, for example, if the tail components of the covariance is zero, then features on these components are essentially useless, therefore an surrogate that omits those components will be better? \n\n2. your equation (8) involves $\\beta^{s2t}$. Does it mean that your asymptotic risk estimate (9) also involves $\\beta^{s2t}$ and thus can not be directly computed? I think in the final bound $\\beta^{s2t}$ should not appear; otherwise I can just claim the definition of the excess risk of $\\beta^{s2t}$ is already an exact characterization of itself.\n\n3. In observation1, you assume jointly diagonalizability. Is there fundamental hardness to remove this assumption?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The authors provide comprehensive theoretical results for weak-to-strong generalization, giving a exact characterization of the excess risk of the weak-to-strong estimator. This knowledge distillation problem is important in modern machine learning, indicating the significance of this work.", "weaknesses": "The presentation of this paper is in general not very satisfactory, in the sense that this paper is lack of necessary intuition and explanation. For example, how to interpret the non-asymptotic bounds and what does each term stand for? Why it is possible that weak-to-strong estimator is even better than purely using the strong model?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yBhRGyTtsj", "reviewer": "Reviewer_pg8p", "summary": "The paper provides a sharp characterization for knowledge distillation in the high-dimensional regression setting, including both model shift and distribution shift, cases. Concretely, the paper characterizes the precise risk of the target model in both cases through non-asymptotic bounds in terms of sample size and data distribution under mild conditions. As a consequence, the paper identifies the form of the optimal surrogate model, which reveals the benefits and limitations of such processes. Finally, the paper validates the results by numerical experiments.", "questions": "1. Can you give me some insights to extend the theory to neural networks (even if two-layer neural network)? I think the authors should also discuss this in the refined version.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. Knowledge distillation and weak-to-strong generalization are significant topics today, and their theory is very poor. Therefore, this is a meaningful paper for me.\n2. The theory is complete and well-written.\n3. The derived bounds seem tight because they are matched with empirical results.", "weaknesses": "1. The theory only focuses the high-dimensional linear regression setting, which is well-studied in the literature. Besides, the results can not be extended to neural networks directly.\n2. A typo in line 134.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gUpOynC1NJ", "reviewer": "Reviewer_vDyf", "summary": "This paper considers the problem of knowledge distillation under the setting of linear ridge-less regression in the teacher student scenario.\n\nThe setting considered in this paper is the the proportional regime where $p,n\\to\\infty$ and their ratio $\\kappa_t = p/n$ is kept fixed. They consider $\\kappa_t > 1$ in the overparametrised regime.\n\nThe models considered in the paper are three:\n* _The Surrogate-to-Target model_ where the data is generated from a dataset $\\mathcal{D}$ with input $x\\in\\mathbb{R}^d$ and output $y = x^\\top \\beta_\\star + z$ with $ \\beta_\\star$ a teacher vector. This data is used to estimate a min norm estimator called $\\beta^s$ and generate a second data set $y^s = x^\\top \\beta^s + z$ and the final estimation is done as $\\beta^{s2t}$ from $(x,y^s)$.\n* _The Standard Target model_ where the model is evaluated on the generated data $(x, y)$\n* _The Covariance Shift model_ here the dataset is generated with a certain choice of covariance and then the population risk evaluated on a different covariance model.\n\nThe first part of the paper is devoted to finding the performance conditioned on a specific teacher while the second to last section considers the full _Surrogate-to-Target_ setup.\nThe authors also consider the procedure of Masking for the surrogate model. In this case the surrogate model has been trained on a masked version of the data and the new labels are generated from the original inputs and the labels of the surrogate model.\n\nThe main technical results presented in the main are the characterisation of the population risk for the model conditioned on $\\beta^s$ and then for the _Surrogate-to-Target_ model.\n\nFor the case conditioned on the target the authors are able to precisely derive the effect of the surrogate model on the final student, showing specific conditions (depending on the covariates and $\\beta^\\star$) under which a $\\beta^{s2t}$ performs better than a _The Standard Target model_. The same is true for the masking.", "questions": "* I would love to see Figure 1b and Figure 2b in LogLog Scale. One of the main points of the authors in Section 4 (Proposition 5) concerns the learning rates in the high-dimensional limit. It would be nice to see them in Figure 1b.\n* Is it possible to generalise the result of Section 3.1 to the case where the chosen features are chosen with a matrix $A$ which has a non zero kernel? The masking seems a specific case of this.\n\n\n* There is a broken citation on page 3.\n* On line 334 is it \"omniscent test risk estimate\"?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper is mathematically sound and considers an interesting setting. The main strengths are\n* The derivations of the different transition values for the covariates is sharp and to my knowledge is a novel finding.\n* The theory match with simulations also work at finite dimension even if the result is high-dimensional.\n* The model introduced and studied is expressive enough to show different behaviour that characterise performances.", "weaknesses": "* Right now the mathematical result is introduced in generality without explaining the idea behind the proof. The authors could briefly explain that to derive the results one should apply the theory from [Han&Xu2023] that relies on the use of of the convex gordon min max theorem.\n* The authors provide some numerical simulations on ResNet-50 on a CIFAR10 classification showing a result that qualitatively differs from the theory. Either this limitation is explained in detail or I don't think it is necessary to be shown.\n* Is there any reason why the authors consider in their technical results the ridgeless estimator instead of the ridge one? A long series of works (e.g. [Hastie2020, Louriero2022]) considers general loss and provides similar bounds.\n* _(Minor)_ Section 4 is presented unclearly. The settings for the propositions are not well explained and need to be introduced more clearly.\n\n[Hastie 2020] Surprises in High-Dimensional Ridgeless Least Squares Interpolation. Annals of Stats 2020\n\n[Loureiro2022] Learning curves of generic features maps for realistic datasets with a teacher-student model. Neurips 2022", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)