Universality in Transfer Learning for Linear Models
Authors: Reza Ghane
Danil Akhtiamov
Babak Hassibi
Venue: NeurIPS 2024 poster (2024)
Keywords: Gaussian Universality
Transfer Learning
Linear Regression
Binary Classification
Primary area: learning_theory

Abstract: We study the problem of transfer learning and fine-tuning in linear models for both regression and binary classification. In particular, we consider the use of stochastic gradient descent (SGD) on a linear model initialized with pretrained weights and using a small training data set from the target distribution. In the asymptotic regime of large models, we provide an exact and rigorous analysis and relate the generalization errors (in regression) and classification errors (in binary classification) for the pretrained and fine-tuned models. In particular, we give conditions under which the fine-tuned model outperforms the pretrained one. An important aspect of our work is that all the results are "universal", in the sense that they depend only on the first and second order statistics of the target distribution. They thus extend well beyond the standard Gaussian assumptions commonly made in the literature. Furthermore, our universality results extend beyond standard SGD training to the test error of a classification task trained using ridge regression.

Universality in Transfer Learning for Linear Models
Reza Ghane"
Danil Akhtiamov
Department of Electrical Engineering California Institute of Technology
Department of Computing + Mathematical Sciences
California Institute of Technology
Pasadena, CA 91125 zghanekh@@alreehh.er
Pasadena, CA 91125
Bakhtiame cawehhh.caccc...a.macacccaccacc edu
Babak Hassibi
Department of Electrical Engineering
Department of Computing Mathematical Sciences
California Institute of Technology
Pasadena, CA 91125
hass bi @ ca tech.
Abstract
We study the problem of transfer learning and fine-tuning in linear models for both regression and binary classification. In particular, we consider the use of stochastic gradient descent (SGD) on a linear model initialized with pretrained weights and using a small training data set from the target distribution. In the asymptotic regime of large models, we provide an exact and rigorous analysis and relate the generalization errors (in regression) and classification errors (in binary classification) for the pretrained and fine-tuned models. particular, we give conditions under which the fine-tuned model outperforms the pretrained one. An important aspect of our work is that all the results are "universal", the sense that they depend only on the first and second order statistics of the target distribution. They thus extend well beyond the standard Gaussian assumptions commonly made in the literature. Furthermore, universality results extend beyond standard SGD training to the test error classification task trained using ridge regression.
Introduction
Deep neural networks have revolutionized the way data processing and statistical inference are conducted. Despite their ground-breaking performance, these models often require plethora of training samples, which can make the process of data acquisition expensive. Moreover, with the advent of increasingly complex deep networks and especially Large Language Models (LLMs), the process of training from scratch has also become prohibitively expensive. To alleviate the scarcity of prepared data and the high training costs, various strategies have been proposed. One such method is fine-tuning in which network previously trained on source dataset/task different from the target dataset/task is leveraged as the initialization point for training on the target dataset/task. In many practical applications, especially for networks containing billions of parameters, only a subset of weights are updated to adapt the model to the new task, particularly attractive method involves fine-tuning only the last layer of the network. A foundational question would be: How effective is this procedure? Are there fundamental limits to how much one can achieve by utilization of a model pretrained on a different distribution?
'Equal Contribution
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

In this work, we would like to investigate this problem rigorously through the lens of linear regression and binary classification in the overparametrized regime, where the number of weights/parameters exceeds the number of data points. To do so, we analyze the performance of regressors/classiiies obtained through performing SGD initialized at a weight Wo E Rd acquired through training on the source domain. It was shown in Gunasekar et al. [2018] and Azizan and Hassibi] (2018) that gradient descent (GD) and stochastic gradient (SG)) iterations converge to the optimal solution w E Ed of the following optimization problem:
min || w - wwol
(I)
w
S.I y= Xx
where Wo E Rd is the initialization point for SGD, X E Raxd is the design/data matrix which is comprised of independent rows reflecting the fact that datapoints (x, are sampled independently, and y E R" is the vector of labels. This property of SGD known as "Implicit Regularization" and will serve as the basis for our analysis the pretraining step is captured by the vector wo- Understanding this "interpolating regime" is key to the theoretical analysis of machine learning models as most of the deep neural networks, on account of their highly overparametrized nature, operate in a setting where they are able to attain negligible training error. It is noteworthy that, even for linear models, characterizing the exact performance of mee-tunnng approach has been somewhat limited and is inhibited furthermore by the Gaussianity assumption on X. One of our main contributions is to overcome this limitation. In fact, to showcase the ubiquity of our results, establish a general universality theorem that applies to a large class of data distributions and extends beyond the context of Transfer Learning. To go into more detail, we say that Gaussian universality holds for a data distribution IP and a training algorithm T' if the test error obtained by training on data sampled from F using is the same as the test error obtained by training on data sampled from the Gaussian distribution N (Hpp Σp) using T, where μ4 and Σp stand for the mean and the covariance matrix of P respectively. In the context of binary classification, we establish universality of the classification error with respect to the distribution of each class. In light of the the latter result, the problem reduces to analyzing the case of the Gaussian design matrices. We allow classes with different ooalsc covariance matrices Σn and Σ₂ and build on the results of Akhtiamov et al. [2024] to address the problem in this specific scenario.
1.1 Related Works
Transfer Learning has been an active topic of research at least since the 1970's Bozinovski (202)]. It is mainly applied in the situations where obtaining data from the true distribution, which we will refer as the target distribution, is costly but there is a cheap way to access data from a source distribution, which bears resemblance to the target distribution. The two most popular approaches to transfer learning consist of instance-based transfer learning and fine-tuning.
Instance-based transfer learning incorporates the source dataset, along with the target dataset, and trains the model on this amalgamated dataset. The key insight is that, provided that the source distribution is close enough to the target distibution and a suitable training scheme is chosen, the final performance enjoys an improvement. We refer the reader to the landmark workDat et al.] [2007] as well as to the comprehensive overviews covering the empirical advances in this area Tan et al. [2018] Zhuang et al. [2020). For theoretical analysis, we would like to emphasize a recent workJain et al.) [2024] that characterized the scaling laws for ridge regression over the union of the source and target data in the high dimensional regime.
The present manuscript focuses on fine-tuning in which a model is first pretrained on the source distribution and then fine-tuned using the target data, Dar et al. [202T] analyzes transfer learning for linear regression assuming Gaussianity of the data. The results obtained in this paper, in particular, imply that the generalization error obtained in their work is universal, in the sense that they can be immediately extended to a much broader set of target distributions, which we elaborate in much greater detail in the main body of the paper.
Gerace et al. [022) consider the problem of binary classification via a two-layer neural network in a synthetic setting. The source data and the source labels are sampled according to x = Relu( Ga) and y Sign(a (a z) respectively where G. and are i.i.d. Gaussian. The target data and labels are generated by perturbing G and a and then applying the same rules as for the source data. [Grace et al. 2022] trained the network on the source dataset and then proceeded by only fine-tuning the

---

last layer on the target domain using the tross-entropy loss with an l regularizer. The analysis was conducted using the Replica method. The authors Geraee et al. (2022) compared their results with an equivalent random feature model and observed empirically certain kind of Gaussian universality for world datasets, such as MNIST.
Extension of results obtained under Gaussianity assumptions to non-Gaussian distributions remains a pertinent research direction in which the idea of Gaussian universality plays a central role. Montanari and Nguyen 2017 proved the universality of the generalization error for the elastic net, assuming the design matrix A is i.i.d subgaussian. Panahi and Hassibi 2017 generalized the result to the problem of regularized regression with quadratic loss and a convex separable regularizer which is either f(-) = || |l (LASSO) or strongly convex. Han and Shen 2023] generalized Panahi and Hassibi [2077] s results to non-separable Lipschitz test functions and provided non- -smmmpttttticc bounds for concentration of solutions. the random geometry literature, Oymak and Tropp (2018) showed universality of the embedding dimension of randomized dimension reduction linear maps with i.i.d entries satisfying certain moment conditions. Abbass et al. (019) proved universality of the recovery threshold for minimizing strongly convex functions under linear measurements constraint, assuming the rows are iid and the norm of the mean is asymptotically negligible compared to the noise. Lahiry and Sur [2023], proved the universality of generalization error for ridge regression and LASSO when the rows are distributed iid with a specific block structure dependence per row, AD where A has zero mean iid random subgaussian vectors per row and D being diagonal.
Leveraging universality is not limited to the signal recovery literature. As an example, [Hu and Lu (2022), Bosch et al. [. Schröder et al. [203). have analyzed the performance of the random feature models by replacing nonlinear functions of Gaussians with the corresponding Gaussian distribution having the same mean and covariance in single-layer and multiple-layer scenarios, respectively, through a universality argument, referred to as the Gaussian equivalence principle. In more general setting, under subgaussianity assumption on the data, Montanari and Saeed [2022] proved the universality of the training error for general loss and regularizer and test error when the regularizer is strongly convex and the loss is convex. Hastie et al. [0022] proved universality for the the minimal fo-norm linear interpolators for the data generated via very specific rule x (WE z). where Z is i.i.d zero mean and satisfies several other technical properties and Σ is deterministic PSD matrix. Dandi et al. [2024) considered the universality of mixture distributions in a similar setting to Montanari and Saeed [022] and proved the universality of the free energy of the test error.
1.2 Outline of the Paper
In Section 2. we formally define the optimization problem for which we aim to establish universality.
Section 2.2 outlines our primary contributions. In Section 3 we present our main universality result, accompanied by several insightful remarks. Section 4 focuses on our findings related to fine-tuning in the contexts of linear regression and binary classification. In Section we validate our theoretical results through empirical experiments. Finally, we conclude with a summary and discussion in Section 6
2
Problem Formulation
2.1
The Setting
We use bold letters for vectors and matrices. We denote the i'th largest singular value of matrix A by (A). We consider the proportional regime where d = O(n) and
1. We refer to Section A.1 for the other notations and definitions necessary for the rest of this exposition.
Given training dataset { (Xr, y and model with fixed architecture, the conventional approach of learning the weights for the model consists of choosing a loss function L and finding w minimizing E L(x,, w;. yr). In this exposition we focus on linear models and loss functions of the form L((x, yi) = E(y; x w,). where E is differentiable and ((0) = 0. Azizan and Hassibi (2018) characterized behavior of a broad family of optimizers, called stochastie mirror descent (SMD) algorithms, for linear models in the over wwer-parametrized regime. For a strictly convex function g : Rd - R. the update rule of the SMD with mirror g and a learning rate n7 0 is defined
Vg(w,) = Vg(w,-1) (w)1,, 12 1,
(2)
3

---

where 17 0 is the learning rate and L, is the loss function L evaluated at point chosen at random the dataset corresponding to the r'th iteration. Due to strict convexity, Vg(() defines an invertible transformation, which is why 2 is indeed well-defined update rule. Note also that this includes SGD as a special case, which corresponds to taking g(-) -12. Azizan and Hassibi (2018) show
that applying SMD initialized at Wn to minimize 1 2 {(y; x w) yields a weight vector defined by the following optimization problem:
min D (W. Wo)
W
S. Y1 = isisn
construct the random matrix A E Raxd by setting rows equal to x, Hence, stating a more general fashion, we are interested in the analysis of the following optimization problem, with the main case interest being when f is a quadratic:
min f(w)
S.l y Aw
As the objective is comprised of minimizing a strongly convex function f over closed convex set, has a unique minimizer. By using Lagrange multiplier 2 this convex optimization problem can be written in the unconstrained form:
((A) sup min
AsO " 2 All - +
Considering the objective without the sup2>0 yields the following regularized linear regression problem for which we will also establish a universality theorem:
1 1 Aw y112 f(w) デ
(A) min
(4)
Note that (4) captures the case of explicit regularization, which is of highest importance whenever there is high amount of noise or label corruption present. Furthermore, by deliberately choosing the regularizer f, is possible to obtain solutions that exhibit certain behavior, viz being sparse or compressed. In order to tackle optimizations such as 3 we prove their equivalence to a problem with suitable Gaussian design G which is described in Definition in A.. Our approach for proving universality will be the Lindeberg approach Lindeberg 1922] Chatterjee 2006].
2.2
Our Contributions
2.2.1
Transfer Learning
Linear Regression We extend the results from Dar et al. [2021] by providing precise expressions for the generalization error in linear regression tasks. In addition, we demonstrate that the test error always lower-bounded by quantity that is attained only when the covariance matrix of the data is scalar. Furthermore, we identify specific conditions under which fine-tuning successful.
Binary Classification We present the first precise characterization of the classification eтror for linear models trained using stochastic gradient descent (SGD) on data drawn from general mixture distribution with arbitrary covariance matrices. Morcover, we delineate the regimes in which fine- tuning proves effective.
2.2.2 Universality
Proof of universality for implicit regularization. In the context of SGD and, more generally, SMD (see 2 with a mirror satisfying the assumptions of Theorem I we prove universality of the generalization error as well as of the value of the corresponding implicit regularization objective for wide range of data distributions characterized by Assumptions [ Note that this cannot be reduced to any known results on universality of constrained objectives as the latter assume that the constraints are deterministie, i.e the optimization variables belong to some determinitic set C chatacterized by the constraints. While analyze SMD one has to deal with constraints of the form Aw which represents random polytope. To the best of our knowledge, the only other paper dealing with universality in the context of implicit regularization is Hastie et al. 2022 They study minimal

---

f2-norm linear interpolators, but they work with a very specific (random feature) model for data distributions defined by or (WE where is i.idd zero mean and W is i..d. Gaussian. Our paper generalizes theirs in two non-trivial ways, as it allows for arbitrary smooth convex strongly convex mirrors f(w) well more general data distributions.
Relaxing assumptions for explicit regularization. To the best of the authors' knowledge, all previous results on universality assumed either that the data points E Rd have i..d. entries or that the rows are independent and x is subgaussian. We relax these assumptions. That is, we show that, for the quadratie loss function and any strongly convex not necessarily differentiable regularizer universality holds as long as the rows are i.i.d., all moments of the up to the 6th satisfy ex vv & K livilg du/2 for v E Rd and Var(x' Cx) - 0 for any C of bounded operator norm.
Extending universality to mixtures distributions. Since the main motivation behind this work is the study of generalization in classification tasks, we focus on data matrices sampled from mixture distributions. Note that most previous papers on universality, such as Montanari and Saeed [022 do not apply to this setting directly. As an illustration to why results of Montanari and Saeed 2022
cannot just be applied to the mixture distributions directly, consider P = 5 N I) + N
corresponding a mixture of two classes with antipodal means and the resulting classification error depends on || while P has mean 0 and covariance meaning that the matching gaussian distribution NO.. does not contain any information about the classes.
However, there is one prior paper Dandi et al. [024]] that studies universality specifically in the context of mixture distributions. It is worth mentioning that their definition of universality different. Namely, they prove universality of the expectation with respect to the Gibbs distribution, which suffices show universality of the train but not of the test error.
Allowing for non-vanishing means. In Definition 2 we assume only that E, 11l3 = O(1),
whereas in Abbasi et al. [2019] Montanari and Saced [022 and Dandi et al. [024]] they have
E. a Mll implying that the norms of the means are negligible compared to the norms of the data points average. To our knowledge, our work is the first to tackle it.
3
Main Result
In this section, we present our main universality theorem and before doing so, we list the required technical assumptions. Consider the following convex optimization problem
(A) == min A
Aww y1I + n1
- f(()
(5)
2n
Denote the solution the optimization problem above by (o,(A)- Then we assume the following:
Assumptions 1. 1. A is regular block matrix and G is its matching Gaussian matrix as in
Section A.7
2. The regularizer f() is regular also as Section A.l there exists sequence of regular fm converging uniformly to f-
3. f(-) is -tstrongly convex.
4. Eylly112 (d) with Ely, (11) E [n] and q E [6] and is independent of A.
5. Smin (AAT) ((1) with high probability.
6. Var(Iyy11)) - 0
7.
S K Ky for a constant Kj independent of A.
Theorem 1. 1/ = ①- supA Dr. suppose parts (1) (7) of Assumptions holl and for 4 = P2.
only assume parts (1) (4) of Assumptions Then
1. (Universality of the training error) For any L-Lipschitz g Rdd _ R. and every 11 > 0, 1 E R the following holds:
-FF((((P(G)) -cl t1) - 0 then ((1g(P(A) cl 12)
5

---

Furthermore, if has bounded second derivative, then
( EG.yg (V()) 71-200
lim
2. (Universality of the solution) For a function & with V 3 ql if either & is regular (Definition there is sequence of regular functions converging uniformly vr
If for every O, P()((G) cl r) - then for B {A, G), there exists 01 E R such that for any I1 > O we have (()((Ww()) - c1l (1) -
Furthermore, if & is bounded
(A EG.y (WF:)) =0 2-00
lim
To sum up, Theorem[ that the vector of weights Wa trained data sampled from non non-gaussian distribution either via SMD with a mirror f or by minimizing the least squares objective with regularizer f. shares many similar characteristies with the vector of weights wG trained data sampled from the matching GMM G via the same optimization procedure under certain technical assumptions A and f. By "similar characteristics", bounded Hessian, d A = // (WG) holds in the limit.
mean that for any v R
with
We would like to point out few remarks.
Remark 1. Note that du need not convex, in fact any linear combination of regular is also regular. An immediate result is the universality of the empirical distribution of the coordinates of solutions.
The assumption V (W)) O(yn) in Theorem 7 is satisfied for any function f with locally lipschitz gradient, ie f())l2 & K(1+ ||ull2). In particular it applies to f(.) = || Remark In both parts of Theorem the regularizer is allowed be an M-strongly convex uniform limit of differentiable convex functions, which implies that f(w) /|[w]] + M M|]] 0, M O,
Remark 2.
known as the elastic net, is also included in our results.
Remark 4. In Theorem | the optimal value of D is only achieved when à - and is not attained any finite This means that proving the results for Y = t Theorem reroorenrreuiiee additional ideas apart from the case V = Da in Theorem 7 as the latter makes use of the boundedness of a extensively. To tackle this issue, we present a uniform convergence result in A which might be of independent interest.
Remark The condition Smin (AAT) 211) can be satisfied a variety of random matrix models. If for each block of A, A; = x, where A, has iid entries and smin (E,) = Q(1), 1), then by the Bai- Yin's 's law Bai and Yin (2008) the condition is satisfied. The second family is comprised of blocks with independent and identical rows where the norm of rows have exponentrial concentration. We prove this in the Appendix. One particular instance will be the distributions satsifying LCP from Definition 3
Remark 6. The second assumption in Assumptions 7 is not restrictive and is in particular satisfied for &f (w) = P( (a"w c). We have with high probability for 4 E {12, Φ}
lim P(aa' > c) - P(a" ())(G) > c) =0
n-00
For a independent of A, G but sampled the same distribution as the rows of A, respectively. Note that by this argument we have reduced the problem of verifying CLT for at ww(A) to its Gaussian counterpart, a WyrG). Then, specifically for the applications presented in this paper, we provide proof that a G) satisfies CLT w.r.t. to randomness general the latter CLT condition has to be verified on case by case basis.
with high probability in G. However. in
Applications: Transfer Learning
4.1 Regression
We consider the classical problem of recovering the best linear regressor for the following linear model
Xw. +
(6)

---

Here, w, is the ground truth, the rows of the data matrix X are i.i.d with Ex; 0 and Ex,x =; Rx- z is centered and is independent of X and satisties B2|lz|12 o'n For given W, its generalization error is defined by:
e ggnn ww) := Bx (x' w. x) = (w+ w.) R. ( ( ww) w.)
Now in order to recover w. given observations (y. we choose to optimize the least squares objective, minw lly Xw|i 13 and do so, we leverage SGD. We would like to investigate how useful having pretrained classifier wo can be for the recovery of w.. As pointed out earlier, SGD initialized from w Wo, by implicit regularization property, converges to the solution w of I We denote ea == Egen ( hence the name "a priori error", Ca- We provide the assumptions necessary for our results on linear regression in Section A.2 In what follows we give precise characterization of the posterior error, ép. of the model after training with SGD, in terms of ea and the other parameters of the problem. In order to leverage Theorem Io establish the universality of the generalization error, it is sufficient to apply change of variable w' ;= = w/1/2w and use (/w) [[wl] as the test function.
Theorem 2. Under Assumptions 3 Section A.2 the generalization error of the SGD solution
initialized from converges in probability to
2- 1(1
1
ep- = k(1 ((1-1) x(1-1)-1 <(1 1)
With : f
Ap(r) (24r dr where 0 is found through - (- 12 And K > 1 is the proportional
constant, i.e for X Radd + K. Moreover, for any distribution p()) we have
cp k- 0²
K -
ea
(8)
The lower bound is attained if and only if p(r) 6(r ro) for some To 0
The following remark is immediate:
Remark 7. Theorem entails that, depending on the noise level present in the data, training could be even potentially harmful. Indeed, of 2 la, then ep 2 x-1 02 x-1 ea 2 o22ve= - -o) 2 ea for any 1 and it is therefore more appropriate to use vector Wa instead performing fine-tuning. Moreover, if the covariance Rx is scalar, then the converse is true. Namely, if ea 2 x², then the yea best achievable error corresponds k. -F and equals o (2 o), which less than ea- Therefore, transfer learning contributes to improving the test performance when the variance of the noise is not too high, but the model has to be fine-tuned on the correct amount of target data.
4.2 Classification
4.2.1
Problem setting
Consider a binary classification task and let X stand for the data matrix and y denote the vector of labels where each y; = +1 depending μe == Ex; and Σg = E 1er for the mean and covariance of each datapoint x,, respectively and f E 21 depending new previously unseen points according to Ynew = sign(w (
what class the i-th point falls into. We denote
the class of x, After learning linear classifier we assign labels to
Xnew). Without loss of generality we will assume that the first rows of X sampled from the first class and the remaining sampled from the second as we can permute the rows otherwise. Modulo such permutation, it is straightforward to see that X satisfies parts (1) (3) of Definition [ Since the topic of the present paper fine-tuning, we assume that the following steps are performed:
1. Obtain pre-trained classifier Wo
2. Renormalize wo obtained during the previous step using the target data via
min lly a:wooll
This yields:
y" Xw
(9)
Xw 2
7

---

After finding take == awo. This transform preserves the direction of wo, while setting
its squared magnitude to ||lll (y" Xwy) wwll?" which depends only the direction of [Xwo]*
Wo but on its magnitude anymore. We find applying this transform very meaningful, as it does not change the classification error for the source data but simplifies learning for the regression problem defined by the target data.
3. Learn the final classifier from the target data X Roxd and labels initialized at W obtained from the previous step.
R" using SGD
Section A.3 to define further details of the classification task we consider. Note that in practice the main difficulty of the classification task in the reeepparaetriized regime (n < d) arises due to the fact that μt, μ2, Σn and Σ2 are not known and cannot be estimated reliably. Nevertheless,
will use the assumptions
would like to start with characterizing the optimal performance in the scenario where these are provided to us by an oracle. Lemma in Section [A.3] provides such a characterization under certain symmetry assumptions. In view of Lemma 1 it is natural to introduce the following assumption:
Assumptions 2. The initialization point Wo satisfies
Wo I.W.
(10)
where w, +
(42) is the optimal classifier defined as Lemmal n is noise vector with ||n]| 1 and any deterministic matrix C of bounded operator norm it holds that n/ Cn
converges in probability to (1-r) Note that the smaller the ratio lq is, the better performance Wo has.
Indeed, 10 captures the closeness of the initilization point wo to the optimal classifier w., For Σ₁ Σ₂ I, if wo has the classification error ea, this means that example, in the isotropic d(I-r) 2. Finally, we would like remark that, under notation and 2 v cr"
should take in
assumptions from Theorem [ the following corollary is implied by Theorem
| moodul Theorem
presented in the Appendix along with the explanation of the implication:
Corollary 1 (Universality of the classification error for SGD and ridge regression objectives). If f(w) |[w - woll?, when [[wlll = (d) then for a. g independent of A, G but sampled from the same distribution as their rows, respectively, we have with high probability for & (12, 4)
lim ((a (w()) > 0) - Pg' (wy)) > 0) =0
4.2.2 Analysis of the Classification Error
Theorem 3. Let Wo be an initialization point that satisfies Assumption / and be a data matrix Then the classification error of the SGD solution initialized
satisfying Assumptions 4 in Section A.3
at awo for a defined by 9 and trained on X. y is given by ep =
x+2
where y and are
determined in terms of 0 solving
2v2 Byn
SE,tE,
2v2 = Oyn
whose expressions are provided the
Appendix (cf. Section equation 40 with d K > 1.
n
The expressions from Theorem can be simplified drastically in the case of scalar covariance matrices.
Corollary 2. Under the notation from Theorem assume Σ₁ En o'Le and define p = d(I-r)
Let ea be the classification error of wo initialized according to 10 Then
(e (e. Vx(x-11
(k. 3
(2x² +x2p -2((p- p)
(11)
We arrive at the following conclusion summarizing the derivations above.

---

Remark 8. = then ep(x, (o) = (ea) + e | ea and fine-
tuning always succeeds. It is observed that for ea Q(1), the worse ca is, the better ep will be.
If p +1), then the fine-tuning step may or may not succeed depending on whether (p(K.p) < not. See Section 3.2ction3522oor for further (empirical) explorations on the usefulness of the fine-tuning of the pre-trained solution for this regime.
If p= o(),, then the classification ervor of any linear classifter goes ass co since is lower bounded by 2( 2) according to Lemma I Thus, any kind of learning will fail in this regime.
An interesting regime is where the number of samples is much lower than the number of parameters, which naturally rises in the context of fine-tuning large models and corresponds letting x > 1. For this regime, we have
ep = f==e(or(es
+ (-)(ee) 3e (
We observe that if p < 1, transfer learning always fails independent of value ea for K >
I and
training would not help with improving performance. On the other hand, if ea > Q( p-1 for large enough K, transfer learning always achieves an error less than ca.
> e 2
3
5 Numerical experiments
5.1 Regression
To corroborate findings, we plotted the generalization
of the weight obtained through running SGD according to the Assumptions 3 in Section 4.1 with respect to Σ. To do fixed d = 1000 and varied n across different values. We used CVXPY (Grant and Boyd (2014), Agrawal et al. (0188) to solve (I) efficiently a Laptop CPU. To verify the universality of our results, we initially constructed a centered random matrix X' with i.id components according to the distributions (00, 1), (er(..5), and (1) and using a correlation matrix R, defined == xxR On the other hand, we generated R2 according to the following three distributions: single level p(r) == - 1), bilevel p(r) := 0.30(r 1) 0.75(r - 5) and uniform on the interval [1,5]. We specifically consider these cases as they are common in the literature and we use the parameter o² for the component-wise variance of in 6 Additionally, Wo is chosen according to Assumptions 3 in such a manner that e, 1. In both Figures I 2 the blue line represents the prediction
7 made by Theorem 2 the red line depicts the lower bound g The markers showcase the performance of weights obtained under different distributions as described earlier. can be seen that from Figures 2 for the bilevel and uniform distributions, depending learning might not be beneficial as discussed in Remark 7 In particular, in Figures Ic and [cc the generalization error is always lower bounded by ea 1 and only in the single-level distribution on R₂ is always a lower bound for the generalization error of various distributions on R,-
the value of or, transfer
can get close to 1. Finally,
5.2 Classification
Similar to the preceding subsection, we experimented with sampling the entries of X independently from three different centered distributions: normal, Bernoulli, and x². We also sampled the means μn and μ2 from N(O, (L) with cross-correlation = B| = 0.9 and added them to the corresponding rows of X. For Figures 3] we fixed p = 0.8, 2, respectively and plotted the classification error predicted by Corollary as solid red line, empirically observed classification errors for the normal, Bernoulli and x² entries as black squares, green circles and red triangles respectively. The blue lines depict the classification error at the initialization. It can be seen that there a close match between the empirical errors between points from different distributions as well as with the theoretical prediction, thus validating both Theorem and Theorem 3 Note that fixing

---

in this setting corresponds to fixing σ² as p improves performance the setting of Figure 3d but hurts for Figure 3a Moreover, note that in Figure 3b although for smaller transfer learning hurts, past certain training improves the performance. Also we observe that by increasing p across the three plots, the classification task
d(1-r) It is also worth mentioning that fine-tuning -
becomes easier and fine-tuning improves performance as supported by Remark 8
150
018
200
Generaiiaann
0.6
0.6
50
1000
10
(a) or 0.01
(b)
(c) or
Figure 1: Generalization enror for the bilevel distribution the covariance of the data
N
0.5
Geceritaatoe Eirer
0.8
Geceritaaton Eirer
100
Geterliaato
0.6
0.6
N
M
10
(a) rr 0.01
(b) or
0.15
(c) C
Figure 2: Generalization error for the uniform distribution the covariance of the data
0.3
0.25
0.4
Claditction
Cladttcatio
Clodficttin
0.30
0.24
0.35
0.22
0.3
32
10
15
70
10
15
70
10
15
(a) = 0.8. 0.9,ea = 0.3
(b) = 2,r 0.9, ca = 0.3
(0) p = 5, 0.9, ca 0.3
Figure Classification error
6 Conclusion and future work
We presented novel Gaussian universality result and used it to study the problem of transfer learning linear models, for both regression and binary classification. In particular, we were able to precisely relate the performance of the pretrained model to that of the fine-tuned model trained via SGD and, as result, identified situations where transfer learning helps and where it or does not. Possible future directions include investigating other problems where the universality result may be useful, extending the results to potential functions that are not necessarily convex nor separable, as well as exploring the implications of universality for objectives with explicit regularization.
10

---

References
E. Abbasi, Salchi, and B. Hassibi. Universality in learning from linear measurements. Advances in Neural Information Processing Systems, 32, 2019.
A. Agrawal, R. Verschueren, S. Diamond, and S. Boyd. A rewriting system for convex optimization problems. Journal of Control and Decision, 5(1):42-60, 2018.
D. Akhtiamov, D. Bosch, R. Ghane, K. N. Varma, and B. Hassibi. A novel gaussian min max theorem and its applications. arXiv preprint arXiv:2402.07335 2024.
min-max
N. Azizan and B. Hassibi. Stochastic gradient/mirror descent:
Minimax optimality and implicit regularization. In International Conference on Learning Representations, 2018.
Z.-D. Bai and Y.Q. Yin. Limit of the smallest eigenvalue of large dimensional sample covariance matrix. In Advances In Statistics, pages 108-127. World Scientific, 2008
S. G. Bobkov. On concentration of distributions of random weighted sums. Annals of probability, pages 195-215, 2003.
D. Bosch, A. Panahi, and Hassibi. Precise asymptotic analysis of deep random feature models. In The Thirty Sixth Annual Conference on Learning Theory, pages 4132-4179, PMLR, 2023.
S. Bozinovski. Reminder of the first paper on transfer learning in neural networks, 1976. Informatica, 44(3), 2020.
Chatterjee. A generalization of the lindeberg principle. 2006.
W. Dai, Q. Yang, G.-R. Xue, and Yu. Boosting for transfer learning. In Proceedings of the 24th international conference Machine learning, pages 193-200, 2007.
Y. Dandi, L. Stephan, F. Krzakala, B. Loureiro, and L. Zdeborová. Universality laws for gaussian mixtures in generalized linear models. Advances in Neural Information Processing Systems, 36, 2024.
Y. Dar, D. LeJeune, and G. Baraniuk. The common intuition transfer learning can win or lose: Case studies for linear regression. arXiv preprint arXiv:2103.06621, 2021.
F. Gerace, L. Saglietti, S. S. Mannelli, A. Saxe, and L. Zdeborová. Probing transfer learning with model of synthetic correlated datasets. Machine Learning: Science and Technology, 3(1)0015030, 2022.
M. Grant and S. Boyd. CVX: Matlab software for disciplined convex programming, version 2.1, Mar. 2014.
S. Gunasekar, J. Lee, D. Soudry, and N. Srebro. Characterizing implicit bias in terms of opti- mization geometry. In J. Dy and A. Krause, editors. Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pages 1841. PMLR, 10-15 Jul 2018. URL htttps://proceeddngg ml press/ v80 / gun.sekaaaaaaaaa 1 Ba html
Q. Han and Y. Shen. Universality of regularized regression estimators in high dimensions. The Annals of Statistics, 51(4))1799-1822 2023.
Hastie, A. Montanari, S. Rosset, and R. J. Tibshirani. Surprises high-dimensional ridgeless least squares interpolation. Annals of statistics, 50(2):949, 2022.
H. Hu and Y. M. Lu. Universality laws for high- nigh-dimensional learning with random features. IEEE Transactions on Information Theory, 6933):1932-1964, 2022.
A. Jain, A. Montanari, and E. Sasoglu. Scaling laws for learning with real and surrogate data. arXiv preprint 200:2402.04376. 2024.
Lahiry and P. Sur. Universality in block dependent linear models with applications to nonparametric regression, arXiv preprint arXiv:2401.00344 2023.

---

F. Liese and K.-J. Miescke. Statistical decision theory. In Statistical Decision Theory: Estimation, Testing, and Selection, pages 1-52. Springer, 2008.
W. Lindeberg. Eine neue herleitung des exponentialgesetees der wahnscheinlicchkeisrrchnnngg Mathematische Zeitschrift, 15(1):211-225 1922.
A. Montanari and P.-M. Nguyen. Universality of the elastic net error. In 2017 IEEE International Symposium on Information Thhoory (ISIT), pages 2338-221 2338-2342. IEEE, 2017.
A. Montanari and B. N. Saeed. Universality of empirical risk minimization. Conference on Learning Theory, pages 4310-4312. PMLR, 2022.
Oymak and Tropp. Universality laws for randomized dimension reduction, with applications. Information and Inference: A Journal of the IMA, 7(3):337-446, 2018.
A. Panahi and B. Hassibi. A universal analysis of large-scale regularized least squares solutions. Advances in Neural Information Processing Systems, 30, 2017.
D. Schröder, H. Cui, D. Dmitriev, and B. Loureiro. Deterministic equivalent and error universality of deep random features learning. In International Conference Machine Learning, pages 30285-30320. PMLR, 2023.
M. E. A. Seddik, C. Louart, M. Tamaazousti, and R. Couillet. Random matrix theory proves that deep learning representations gan-data behave gaussian mixtures. In International Conference on Machine Learning, pages 8573-8582. PMLR, 2020.
C. Tan, F. Sun, T. Kong, W. Zhang, C. Yang, and C. Liu. A survey on deep transfer learning. In Artificial Neural Networks and Machine LearningICCANN 2018: 27th International Conference on Artificial Neural Networks, Rhodes, Greece, October 4-7, 2018, Proceedings, Part III 27, pages 270-279. Springer, 2018
R. Vershynin. digh-ddimesional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018.
F. Zhuang, Z. Qi, K. Duan, D. Xi, Y. Zhu, H. Zhu, H. Xiong, and Q He. A comprehensive survey on transfer learning. Proceedings of the IEEE, 109(1):43-76, 2020.
12

---

A Notations, Definitions and Assumptions
A.1 Notations and Definitions
We call a convex function f R - R separable if f(w) E fi(w;), where fi - R are
convex. Examples of such functions include - [pp for every p 2 1. A function f R= - R is M-strongly convex for M 0 if for every w E Rd ( MM]l is convex.
Functions satisfying the following definition will be instrumental in the statements of our results: Definition 1. We call a function f : - regular if it satisfies the following conditions
1. f is convex with f(0) = O()).
2. f is three times differentiable.
3. f satisfies the following third-order condition for some Cy >
8'1
aw.dw,0wz ViVjVk & C
|v;1
L.J.e1
Note that separable functions with bounded third order derivatives satisfy the third assumption of Definition T For the description of the main results on regression and classification we recall several probability theory concepts.
Given a realevalued measure μe, its Stieltjes transform is defined as
Sp(z) ff--zulad) z E H. URR Supp(μ)
(12)
With H.. (z: (m(2)= 0}. Moreover, denote convergence in probability and weak convergence sometimes Var(X X) for the
for measures by _, and respectively. For a random variable variance X. For a convex differentiable function g, the Bregman divergence is defined by
(w, wo) == -(w) g(wo) (g( (w- (w)
Next, we will provide a description of the design matrices investigated in this paper. It will be clear soon that these assumptions are often satisfied in practice.
Definition 2. We call a random matrix A E nnd block-regular if it satisfies the following properties:
1. AT = (A] AT
AT) with k being finite and for each A; RRixdd n; = (())
2. For 1 sis S k, the rows of A; are distributed independently and identically.
3. BA; 1
4. Let a be any row of and be its mean. Then for any deterministic vector v E Rd and
||v] dotz
q E N. q S 6, there exists a constant K > such that Eal(a - μT v/9 <
5. For any deterministic matrix E dddd of bounded operator norm we have Var(a Ca)
d + 00.
6. Each || = 0(1)
Note that assumptions 1-3 from Definition are satisfied for the design matrix both in the classification and regression scenarios, and the assumption || ( is just a matter of normalization. While assumptions 4 and might appear obscure at first, any a Rd satisfying the Lipschitz Concentration Property (L.PP) also satisfies the aforementioned assumptions. Recall that the LCP is defined as follows.
"e would like to point out that in this definition and throughout this work in general, mathematically speaking, we dealing with sequences of vectors and matrices with increasing dimensions. So, for example, assumption 5 can be formally stated as follows: given any sequence of C₁ Rdixd; satisfying |[C/ K for constant K 0 and all we have that Var C,a,) 0 +
13

---

Definition 3. We say that a distribution E R satisfies LCP if the following inequality holds for any S Rd R
dr²
P((((a) - Eg((a) >) 2 exxp
21 Lip
is also worth mentioning that, shown in Seddik al. [220]] any data distribution from which one can sample using a GAN satisfies Definition 3 Since it is known that many natural datasets can be approximated well by GAN-generated data in practice, we thus find this assumption realistic. These assumptions also bear significance for the iistance-based approach to transfer learning as utilizing GANs can remedy the dearth of data. What is more, these assumptions are not limited to the subgaussians and include many other subexponential distributions, including x² which appears naturally many signal processing applications such as Phase Retrieval. order tackle we prove their equivalence to problem with a suitable Gaussian design G. For this purpose we will need the following definition:
optimizations such as 3 4
Definition 4. We call Gaussian matrix matching a regular if block-regular as well, EG; EA; = =14 and for any of G; and any row of Ai, it holds that Bgg' -Baa".
A.2 Assumptions for Theorem
2
Assumptions 3.
1. R, 0 is diagonal without loss of generality.
2. Let PN be the empirical spectral density of Rx, then PN a* p for some probability distribu- tion p.
3. Wo is white perturbation of true w. in the R2 basis. That is, wo = w. + RR,12 where
B 0, BEE" 6o for fixed ea > 0.
The third assumption from Assumptions represents the fact that Wo is a perturbation of the ground truth w. in the eigenbasis R,.
A.3 Assumptions for Theorem
Assumptions 4.
1. The data matrix X satisfies parts (4)-16) of Definition
2. The means P1 are of norm and for any deterministic matrix of bounded operator norm it holds that 1uf Cpa, 2² Cjuz and μe Cpz converge in probability to IrIC) Tr(C) and rTr() respectively. d
d
3. Σ,, Σg are diagonal.
4. Let fox be the joint empirical spectral density of Σ,, En, then PN me where the distribu- tion p is such that 52)1,82) = ((82,51) holds for all 81, $2.
For discussion of the first assumption from Assumptions 4 see the paragraph after Definition 2 The second assumption from Assumptions 4 is satisfied, for example, for any random vector of the form 12, where Σ is an arbitrary PSD matrix and z is i.i.d. The third assumption postulates that the means normalized generic d-dimensional vectors with angle arccos between them. The fourth assumption says that Σ₁ and Σ₂ are simultaneously diagonalizable and, finally, the fifth assumption simply introduces notation for the joint density function of the eigenvalues of Σ, and Σz-
Lemma 1. Assume that the feature vectors are equally likely be drawn from class or class and Assumptions 4 hold. Then the optimal classifier is given by w. = =E) + Σn) - (pp) - p2) and its classification error equal to the following, where Q(-) is the integral of the tail of the standard normal distribution.
Tr(E, + (1E,+EE)-114 -2)-
THE -1
0
0
(2)
22TH E1 E2)
14

---

B Proof of Theorem I
In this section we provide the complete proof of Theorem
B.1 Proof of part of Theorem 1 when 4 = x
We prove the universality of the objective value and then it to prove the universality of d applied to the optimal solutions, To do so, we construct the perturbed objective. Let
L1. (A)
min B1 WES,
| - yl1 + f(w) ew(
Where |e| is small enough that cv( + f(w is p-strongly convex. For such e's, we will show that Da.e (A) and &a.ee (B) converge in probability to the same value and use that deduce similar result involving & (We,o(A)), (((a))))(((.w.... (W). A key step is to reduce the proof to upper bounding the difference of expectations, to do so, the following proposition will be instrumental whose proof is given Appendix [
Proposition 1. for any sipschitz,uunctonn and for every twice differentiable g R - with bounded second derivative, we have that Bay8 2 (B)) EB.yg(DA..c (A)) 0 then for any 12 f1-
R R and r1 > 0, (lg(O
>1) O
lim P((x(01, n=000
12)
Thus suffices to prove ao ( -
for every twice differentiable
g with bounded second derivative. As stated earlier, we proceed by Lindeberg's approach. Fixing A and e, to simplify notation we use (A) for @2,c(A). For j s n, let q E N be the largest such that j Σn my and let = Σ if then
Å =
|1.1
a12
ag.r
bg.rtl byt1.1
bg.ne bg.
r < 1g+1
[a1.1
a1.
ag.r
r = 1gt1
follwos that A Ao and B Ån
Then we have by a telescopic sum
BA.B. Σ -(((())) - -(((())-)))
B Ba)g(((A))
BB,
1=0
Now define matrix by dropping the j'th row.
A
[a1.1 a1,2
ag.r-1
bq.r+
bR. nq+1
[a1.1
a1.2
aq.-1
bo+1.1
bR.
r nq+1
Note that
d
o(A,) min
11 y112 + ((W) eih
n weS,, 2
1 min
2 | w 5 (a7, w- + + MMa,)
n wcS.,. 2
((A,-))
min
-l w + f(w) Ed (w)
weS,,,
1 min
1
| 311 2 y,) f(w +cb(w) M(b,)
n w.S.,.
2
15

---

And we define M(a) == m.n (a w). So, we need to bound [x)))(((AA))
( to do so, we condition on Ay:
Let us define the optimization whose terms are shared by both of M(aj) and M(b,) |,.
B (()))((((A)) - B (0(A))) S b,y s(M(a))) {(M(b))) -(M(()))|),,))}}
+ 1
A
min 2 -1 -11 f(w) + (w))
wES,,.
Now note that since the second derivative of g is bounded, we have
g (()) g(M(a,)) g' (M) 9) ll M(a,))²
g(0) s(M(b;)) g (M(()) 3) ( M(b,))
(13)
Adding and subtracting g( (+) and taking expectation and moving inside, we have 8 g(M(a))) g(M(b,)) ,
B Bay.
(()) - g(M(())) - (M))) A). -)
, by,y
+ E x Bay b,yy
(( - s(M(b))) ( ((O)))))))) 6) A,
8 (())))()))))))))))))))))))) - M(,))
+ Bxy, by,),
Using 13 and by the independence of θ and ay. yy. we have
Bx, Bay. g(M(a,)) -gg-ggg(- g(M(b,
, BA, (o) (M(a,) M(b))))
+ l1ss Ils" ملممممم Xx
( M(aa)) + llg" 11 KyB.,,,, (0 M(b,))
B (e(())
B Byy, (M(ay) M(b,)) A,.
+ l|o"" (BA,
M(aa)) ", (0 (()))))))²
s ll&' l1 lolll 2
Bay Bay (M(a,) - M(b,)) A
( + Ilgg"l>< (BX,, (0 M(a,)) + B (0-
(14)
Thus we focus on M(aj),M(b) conditioned on A,. From now on, we drop the index j from Äy. aj. by. yy- Intuitively, we show that by dropping (a"w - y) and (bTw w y)² and approximating f. de by their second-order Taylor expansion, the objective values (',,), ((A--) would not change much. Which implies Φ ((A,) and &b ((A)) are also close in value.
Let u arg min 2 || Äw ý|ل + f(w) + eif(w) and it is unique because of strong convexity. Now we use the second order Taylor expansion of f f+ eih:
f(w) + e f(u) + (u) (f (E))))
+ -f R(w u)
Where limy-u. -u [w-ul= = 0. Let : V(f (u) (u)) H := v ((())) Moreover, let
R(w-u) u)
[(a) min ((a, w) min 1
2 jAw 3112
1
a yy
w S
n w..
2
+ fu( eu (u) + +g =((w - u) - "w-w)'H(w u)
16

---

Note that a and b match in distribution up to the second moment, which implies that
( u y)² BB,, (b.y(b'u y) E La'n-aa a B-b'
By triangle inequality we obtain
Bayy
babby
(M(a) - M(b)) A
s B Bay
(M(a) - L(a)) A, y
+ +B Bb,y (M(b) - L(b)) A.y
L(a) Q A Ba. (a u y)
1 Eb.y (b² u - y)²
+ A.s Bay
A. y
B, Bb.y
[(b) -
A,
2n + AB, 2
2n 1E,b" 52 12//221111 'b.
$ Bx.g..y
(M(a) L(a)) + B... IM(b) L(b
((a) - - d (a lauu y)²
[(b) - - a (bTu- y)²
+ BAs Bay
À. y
+ +Ba,y Eb.y
A,y
2n + 2B L -a
2n 1 + b., 1b
(M(a) - L(a)l + E A.j.b.y |M(b) L(bb]
(a' u y)
(a" u y)
2
(b'u y)²
(b" y)
+ 2n
Ba.g..
y.y.byy
11 Q l 1 a L
2n
1+ 12 b
1 IB b 'b.
(15)
First we will provide an upper bound for the third and fourth terms in 15 As the function x + I-Lipschitz and using Cauchy Schwartz we arrive at
- is
Tex
(a y)²
(a y)²
12
2n S.y.a.y 1+ la a 1 1 2-aaa la
B Biyay
(a' u 2) (aa E2a"
2n
(16)
12
$
B Bis.ayya B. (a -laa 22a 2n v
(17)
By Lemma 7 there exists constant C1 such that B A.s.a.y
(a auuu-y) Ci for any n. Furthermore,
by the assumptions, lim B -laa--- - Ega s2
aa =.
Now for the first and second terms in 15 using Lemma
obtain with probability 1.
8C f+ew - n w ella S
(M(a) [a)
18C
d (a" u
P 18C
+ 2n
>
Which implics
E MMsaylM(a)) L(a)) 8Cstem
||u --- --wlll wells S
P 18C
A.yay
n
1
B
A.j.a.y
(a ((ll-wwlll >
18C
2n
We apply Cauchy-Schward to each term:
8Cs+ew
Ei..ayMMaa L(a)]
n
d
B Biss 12 wells P 18C
JBR,s,a, (a y)
2n
V
8Cs+ew
8C
Exs..yy u wzll;
+
PA.yaayy (Ilu wella >
B BajaayaTuu (aTu-))) y)
2n
V
18C
17

---

To deal with the terms involving P, we leverage Markov's ' inequality
8Cfteu
EasaylM(a) L(a)) s
A.
w well
n
18C
3/2
B. Sll - (a'u y)d
+ 2n
P
By Lemma 7 there exists a C2 < oo such that 13 x.5.a.y
u - --llll $ a and recall that B Bxssayy (a'u
y) Ci for any n. Thus
LVC1 8C2C
18C 1312
Ca
BA..ayMMaa) L(a)l
(18)
nd
2nVd p
nVd
For some constant Č ANCI - (BC)ree) /322 + SCeC. Plugging (16) and (88
in (15), yields
Ex,y Ba.b. - (MM(a)M(b)))A.
C+C
2²C Varaaaa
1²C'
B VarVarr
nVd
2n
2n
For the other terms in (14). we have by Lemmas llg "IlaaB M(a)) 1oo Ilo b.y. (MM))))
a²
X2 Blo"lll.xx,s.b... 4n
11x 11 R.S.A.y 4n 2211g" 11 (Co (
(a' u y)² 111g"
(b' u y)
4n²
Plugging in
14 we obtain
8 (M(()) - s(M(D) A.3
Bx, Eab
C+C
+ 2²C
XC6'
Pllgg"llaoC++ C*)
$ Ilgg' 1l:
Bx, VaraVa (a'a + 2n Bi, BBxgVarr('''
nyd
2n
4n²
Therefore,
Bay8(((A)) (R)g(((())) s
Σ B),s ((
n-1 < Σ j=0
C+C' X²C
X-C'
1lo C')
11&' oo
nvd +
s Vara, ( (2) a,)+ 2n Bx,s,
Varb, (b)
2n
4n2
llg' (lo C¹),
Vd
4n
I2C
aa)) / Vara, (2 aj) +
PC
2n VEA,S, Var, (b)s2 -b,)
2n
1=
Now note that since ||Lllop $ 1 with probability I, lim Vara, (a) 52 aa) 0 from assumptions,
thus for every class [/], there exists function (n) that Vara, (a aa) s G (1) for every n E N and lim (n) = 0. Thus
(A,)8(((A)) EB (B,ye(((BB)) s Il (ColooCC (C+ +
1l1ls"Ila +22 22lle'llaa Č') (C
n;
(n)
Vd Il (I+
4n
2n
1=1
x2lls" (C+
22 1oo (C C¹)
max (z)
Vd
4n
Isisk 2n
Now since k is finite and = ((n) for every 1 S i S k, we have that lim max (n) 0.
Thus for every A, E
lim Ba.yg( P a.e (A))
and the proof of part of Theorem concluded.
18

---

B.2 Proof of part of Theorem 1 when V =
Now to prove the part of Theorem I we will combine the following lemma with the previous section. For the ease of notation, we drop the dependency on Recall that since f is p-strongly convex, we can write
1 All - y112 + 2 [1lw1β + h(w)
(A) min 2
For some convex h Rd - R.
Lemma 2. for every d > we have (A( Es ca thenfor every finscciitafunctionn g Y:R. - R, we have g(supa>o (A)) E, (sup2>>0 ca) and g(supx=0 (B)) 5 g(supaso Ca)
Proof. First note that for a given we have for every Lipschitz function
P([g( (b) g(c2)) s P( cal > +
Letting 8 = 4.- 51 0, we know that for every A 0, there exists N1 E N such that for every n Ni
P(I0 cal 8) 0
We will show that an R > 0 can be chosen in such way that there exists N2 e N such that for every 2 N₂
P(sup t 2=0
sup D > 8) 52
0<A<R;
To see this, by the monotonicity of D in 2, we have by the fundamental theorem of calculus for given Rj
P(sup 0' 1>0
sup 6 > 6) P( lim 0" 0ct<R,
0% > 0) =))=p(
84%
ds
6)
1000
ad
By Danskin's 's theorem,
Φ4 P (
P(sup t3
sup 0<A<R;
yyl
(19)
JR
Now for the gradient the main optimization have, by g := Vh(w)
2AT AAT(Aw
y) (Aw- p
Which implics w = (2ATA A + pl) (AATy g). Hence by matrix inversion lemma,
Aw - y= -1 A(AA + pl) 1A A +l)
= =-P(AAA + - A(AA pl) -a=)"g==a- ---=-p(Aa =P=AAAAAA" + +pl)-ly (AAA +pl) AA
By triangle inequality and definition of the operator norm we have
Aw + y11 s 4 + pl) -1) 112 41[AAA ( +p)- 11
Whence plugging back in 19 yields
P(sup D
sup
Φ >)
6) s P(P
P²l(SAAA + +p) 112p1111111 ||sAAA -1)- (lg(s) > 6)
1>0 0cAtR:
Ri
4p 11x11
f [[sAAA + pl) -112 > 8 =
< P
f
4 00
(
||ssAAT pl) Al? (l(s)) > ]
+
RR.
For the norm of g, by assumption, there exists Cg independent of 1, such that [((()) s Cg with high probability.
19

---

Consider the following the events
T5 |1xl12
n TA
[lg(s)]1
Tg. S C3)
Smin (AAA) 2 Ca.
We further have
4p² II(SAA" + pl)
p1) 11p > 2) s sP(T,)) +
( I(sAAA + +pl) 111 1lp 2
JR.
P(=
4
II(sAA"
Al 2) s P(Tx) + P(44G
{ IIsAAA + Al) plpps 6 2
(20)
Thus we need to focus on the operator norm of each term in 20 After diagonalizing and using the fact that for any two rectangular matrices X, Y with matching dimensions, spec spec(YX)
IIQAAA + I11 = max
IsiSH (As; (AAT) + +)) (dsmin (AA7) + p)²
s;(A)
IIAAA +11)-
ISISA (As;(AAT) + p)2
Now by the event TA Smin (AA?) CA. then for large enough R₁ such that & CA. then for every
A 2 R
1
[IAAA + pl) 1110-11ppp S
(AC +p2
CA
IIAAA T + pl) - 5
(ACA p)2
Bounding the integrals implies
I|sSAA + +pl) -1)p-112pp S
CA CARI+D
R
I[SAA +p) Allap
CARI+A +p
Summarizing.
P(sup s 1=0
sup D<.R-
44 8) S
CAlCARi p) /
4p²C,
8) +P
CARi+p +B(T)) +P(()) + +P((TT)
Cg 8)
(21)
Now we choose Ri to be large enough such that the first two terms vanish. Therefore there exists an N2 e N such that for every n 2 N2, P(T,9) + +PTT)) (P) 82. Thus for such R and N2, we have
Pssup O sup
6" > 8) = 82
2=0
0<1<R)
Now we can let R₂ > 0 be chosen in such way that:
sup Ca -
sup
C. < 5
150
0<1<R;
20

---

Take the maximum of R and R2 as R. By triangle inequality we observe
P( sup 22 sup cal 6) P(
sup
D
sup cal 6) P(sup D2 sup Dj > 6)
1s0
1>0
0ctER
.100
0cd
OctER
P(I sup 4-- - sup c,l > 8) c2
sup CΛ 6) + P(sup 15 sup 0 6) Ocd 0cdeR
0cteR
0-
1>0
0<AcR
P(I sup 07= sup cal > 6) + 0
0cteR
OcteR
S 01 + P( sup
1 cal 6)
OcdER
< 61 + P( sup [0 c2l > 6)
0sAsR
First we prove ca is concave in d. Then by appealing to the Convexity Lemma (lemma 7.75 in Liese and Miescke (2008), the result follows. Note that 4 is concave in 1 as it is the pointwise- minmuum of concave tunction in d everywhere. Now to prove the concavity ca. for a given pair of d1 E [0, R] and 0 < 8 < 1, prove the deterministic event (CoA;+(1-0)2; -C - (1 C) 0)
has probability zero. First note that
(1)=(11-)) - -00% - (1 - 0) 20
Thus by union bound for e > 0
P P(OCa,+ +(1 (1-11110000 (10c) Co))+(1-0)1; >c)
P (((A 0% + (1 (c 0%2 + Φn
(1))(1-0)d; - -Co)=+11-04 >
$ P Mcc,, <
0% + (1 - -0)cc - 0%,11 1 ( ()-1) -C01+(1--)1) >
E < P f|c,, - 0 3
+P +P((1 (1 - 0) 94 3 + C
E
3
Now by taking be large enough, the RHS can be made arbitrarily small for every e and 0, thus ca is concave. Furthermore, since [0, R] is compact set, we can appeal to the convexity lemma 7.75 in Liese and Miescke (2008 and the first claim follows. For the second claim, note that so far we have proved
2A 3. ca = sup (A
?, sup ca
120
A=0
Then since [Q,(B) +.(A) P, 0 thus (B) (B(B)) yields
2 ca. repeating the same argument this time for
PB - supca
sup
A>0
2>0
B.2.1 Sequence of Regularizers
We prove that by constraining ourselves to large enough compact set Sw. if fm - f uniformly, then the universality results also hold. Note for the O case, we have that by setting w in the optimization, we have l| ll2 I Cw for some C, > 0 with high probability, thus we can instead set Sw := Vn and consider the following equivalent constrained optimization problem
कh (A) weS,
min 5 IIlAw y11 fm(w) + (w)
Now consider a sequence of regular functions fm. converging uniformly to f on Sw. Take m large enough such that Il fullss nō for any which implies | (A) L2.0 (A)l S ō. Thus for any t
0
P((0s, (A) c2,e >
sp((0 a, (A) क. ( (A)) > 1)) +P(00T (A) The > 5
(22)
Th d,e (A) P, m c.e. then by 22 we have (A) P C2.e. A similar argument holds for
min fm(() Eub (w) (A) = n Aw
Furthermore, subsequent results also hold for df (WoT(()) (A)) and ds (Wo,(A)) ss (W)) and df (Wo(A))
21

---

B.3 Proof of Part 2 of Theorem 1
B.3.1 Proof of Part of Theorem for regular test function when D2
Since we assumed (2,0(A) converges some c2, in probability, then for a small enough E, we also have x2 (A) - Ca.e- Therefore we may write by an application of triangle inequality and the union bound
Now we prove the second part of Theorem !
① ae (A) (A)
CA.e - CC,0 > of s pp
cP(0 (A) - -2,e > 2
+ +P((O10(A)) c2.0 >
El
2
(23)
For every E,1 0, the RHS of 23
goes
zero.
Similarly
have
P (xp(A)-PA-e(A)
Cao- O.
Now observe that by triangle inequality
(M(merra))
dcr.c de
dc
dcae -1
> r
s P
P (Wo,
+1 +P y
(Woo.
c=0
de
l==
de l==
We take to small enough such that
dc2.E
CA.é c20
1
dc
C2.0 Cd.-è
de l==0
è
2'
de l==0
This implies
(Wo..ta))) dca.e
de le-0) >1 (Wo. > C20 CA.-é
(Wo)())) CA.e C20 2
1
2
And by Danskin's 's theorem, i (A) is minimum of a concave function therefore it is also concave and it is differentiable with respect to we observe that v (wo,(()) = d0 concavity over ē: (A) (x,o(A) (WW(.(())
Moreover, by
de e==
22,0(A) -A,,-(AA)
è
Whence
P p(l(woo)))) de c=0
dca.
$ (x,((A) - (A))
C2,0 CA.-é
> S
1 11 (A) (2,(AA)
C2,e C2,0
P
11o(A) (2,-e(A)
C2,0 Cd,-é
1
$ P
① (A) xx.(AA)
CA. Cao
+P
P dea. de
By 23 the RHS goes to zero, thus vs (ovll(ooo) (Wox(A))
Furthermore, we have
===
(Wo, - dc2,
① 1,0 (B)
1 (B,
C2,0 - Ca,-é
1
>1
SP
>
de c=0
è
è
2
1
4.e (B)
220(B)
CA. - C2,0
1
+P
2
el
> El
$ P
$2. (B) Ca.e
>
+ P
1D,--e (B) - C2.-e (B)-ca--e
2
2
+ 02
+ +2P
(B) -c.0
>
El
(24)
2
22

---

By the result of the first part, we know that the RHS 24 goes to zero as - co. Hence, & (B),(B)) E deac de e==
Moreover, if is bounded, by definition of convergence in distribution, [B (Wo.()))))) (B), - O.
B.3.2 Proof Part 2 of Theorem for a regular test function for Y Defining
min f(w) (W)
n W.
Since supaso0.. (A) 5. sup.>00A,e: or equivalently 6. (A) - ce. we can use the same argu- ment from previous section and Danskin's theorem, to observe that & (Wo, & de. de c=
and
d (WW de.
B.3.3 Sequences of regular test functions
By similar approach, it follows that for sequence of regular functions o.n. converging uniformly v also has // (Wo,) P, des.
dem
limm-
Indeed,
c=0
e=
P (((
dca,e
21 s P ( 3 (wox(())))
> 2/ + +P + (
dea,e
1
>
de le=0
de le=0)
2
Since we have uniform convergence, for 1. there exists an mo such that for all m 2 mg and all x E Rd.
we have (x) - (x) < Thus for such m 's, (woo. 4m (woo > = Then by triangle inequality
((WOLAA))
dca,e
de le-0 >1
SP
/P(U &
(wor(aa)
dcm
+
dca,e de
dc
de
e=0
le de
le-0)
4
By assumption follows.
det
+. 0. And by the definition of dea.e de
the claim
de le=0
e==
C Proof of Corollary
We will utilize the result of the following Theorem.
Theorem 4. (obkoo (2003]) For an isotropic random vector X Rd,, and an isotropic gaussian
g E Rd P(
V2 2 ea) s ed, thenfor all 5
sup
- sn) 4Ea + 44/318 ccdo'
rei
Where O ~ v the uniform measure on the unit sphere 3d-1
Essentially, through CGMT, we observe that when we use a quadratic regularizer or rum SGD, the solution, WY(G) converges weakly in distribution to a Gaussian vector, gAO- Whence we conclude that Wy(G) behaves the same as a generic vector. Therefore, by choosing == a Ea, row of our data matrix A, Theorem 4 enables us prove the universality of the classification error. Note that in general EW * 0, but by Assumptions 4 the means of the classes are generic which allows us to employ Theorem 4 to conclude the proof.
23

---

D Lemmata for the proof of Theorem I
Proposition for any
g R and > 0, (B)) n)
and every twice differentiable g : - B. with bounded second derivative, have that lim ( EB (x, (A)) O then for any 12 > l1.
lim P(lg(O,. cl 12)
Proof. First note that p( (B - cl r) 0. implies P(1s( (B)) -g(e) > Lr) - 0.
Thus it suffices to verify P e (B) - d f) + 0. This follows similar to Panahi and Hassibi
2017). Let ((x)
+ [1tf ([x] - 11 (- a jur 11122.0 .2) (x) ([x]
h (- (- Jule, " (x). Then we have
-
cl > = (P(E(O).e -c) 2)
Then by Markov's and triangle inequality
P Pre (A) cl 12) s A ( (A)
BA BA. (A) -c) EB., 12,e ( (B) (B) c)| + EB, BB.y5(0n,, (0.,. (B) cc)
Note that E(x) S (-00 [u] Thus #Bn.E((A., (B) -c) s p p (B) cl > nn). Moreover,
we know that g(.) has bounded second derivative derivatives almost everywhere and by assumption on g', we would have
PlI0r.c (A) - cl 12) = -Bn,)))))))BB(((0... (B) - + (B) - cl > n) -0
BA - -B,
Lemma 3. We have the following:
1 (a u
1. [(a) θ =
2n I+daa
2. WL u= y-a-u Tu
I+.ta 2--
Proof. We know for O taking derivative yields
^ÄT uu - +g=0
This implies
Note that for L(a), since the objective is quadratic in w, we solve the optimization in closed form, have
{ Aaa" +H)
y -dyayy+--- Hu) s(u) (u) g'u+ fuu Hu 415] ,2)) (
L(a)
min (WT
(-2A's -dyy+ Hu)
n
Let Ω A H. hence
L(a) n
f(u) + (u) - g ut 7" TTu Hu (1571 +y3) 2 (Suu + Aya) (Ω ( + daa") ((uu 2ya)
Using Sherman-Morriee as Ω >
1Ω 1 aa Ω 1
(Qu+22y)) Q 2
(Qu + Aya)= = (Qu + +1a)) 22 7(2
(Su 2ya)
+ la
1
Ω Ω- a + +1y 1 Pya Ω -1
= =Su++ u daT
1 + 1+ Ω la
1 2a 22 a
dya n
a a²
= (Qu + ( u+ 2
Ω a = (Sn Aya)" (u+ ((a))((++)
2-aa)
1 14247n11
+ 2
24

---

From here we obtain for the solution Thus for the first claim:
y a²
(52 + daa") "aan))""(22u dya)
2 2-
W L
1 1 1a
52
a
Hence we have for the first claim
=1 y
2 -2a
1 Aa T 12
Now we continue with the calculation of the objective value
a²u y-a'u 1+ a
a u dya' u+ d-y y --a'u a'u
u Qu d- y
2 aa
1 1a
=u'uu
+ 1a
ya'u (a'
(a'u) u) ya u Ay 2 ayyaa>
a aaaaaaaaaaaa(a"aaaaa)))
A
=uu
(2ya' u (a 2ay
1+ 1+da"2-1
Thus
A uu -g'u+ =u Hu Z (1151 y3)
L(a)
f(u) + eu gu'u
= Luu
2
1 d
(2ya' T u (a' u) (a'u)²
dy s2 a)
2 + la Ω
a
f(u) + (u) g.uu
1 -
A A uu " |1811
(a u y)
2
# Aa
Since = A y AA Au, then g" u-u 1ÿ" Au du AAu, therefore
2
A (a" u y)
L(a)=
f(u) (u) -15 Au du ÄAu =u² A
|1
2
2 1 Aa a.
1
f(u) cv)(u) + 2 ||Au -012- 5|1
2 (a u y)
(a 100-y9 y)
=0+
n
2 1 + la Ω a.
2n
+ Aa
Lemma 4. We have the following:
1. M(a) z + (a u y)²
2. ((a, w) L(a) E ||w =l?
3. (m w) C(a, w)1 5 Crice
n |ww ull
Proof. 1. By definition,
d. M(a) S ma =
(a y)²
2n
Thus M(a) - ()
The idea of the proof by strong convexity. By assumption, f(w) (w) for small enough is p-strongly convex. This implies from defintion:
((a. w) 2 L(a) + 2n
||w wzll
By Taylor remainder theorem for some 1 1:
ma, a. w) - C(a, w)
f(w) + (w) - fu) - ev(( _T (w - u)
(w - T m)
1
Σ 8 + + ((1 ((1-)) /w) (w u)a
n |a|33
a!!
25

---

Since f and ds are separable. ( + Ev) Then by assumption on the third derivative of f eV.
0 unless a = a (e is the standard basis vector in R.
(a, w) - C(a, w) = !
Σ
8 (1 - (W)
(w (w-u)" u)
at
33
d PC + Ev)( -) rwi)
(W; ui)² S n
Cstcr
|| u/l3
dw]
Now are ready to prove the following key lemma.
Lemma 5, We have (M(a) - [(a) s min tn (a' y) 8c || ul]3)
Proof. Let W arg min m (a, w). Note that since O M(a) and by Lemma we have
L(a) M(a) (a)) - - M(a) s A (a - y)
2n + 1a 'a
On the other hand, note that m (a, u) O + y) and + v L(a)
1 (a-u- y)²
M(a) - L(a) = M(a) - m (a. + m m + + [(a) s 2n
Thus as (a' y)² 2n 1+
(a-u-y)²
A_ (a' y)
(M(a) [(a)l s 2n
But will see, (a 2) is of order 0(1), which will not suffice. Thus break down M(a) - L(a) depending on the distance of u and W.
M(a) L(a) ma. wM) ma wi) ma, w C(a, w.)
Cs+ew || =ul
(a. ((aww))
For the other direction
L(a) M(a) = C(a, w () - C(a, W.) + C(a. M. ma W)) S Cster
|| ull
n Let R = || L - ulla and consider the l ball centered at w Now if [|W - wells s then [|WM- u/ls 2R by a straightforward application of triangle inequality. Which implies
L(a) M(a) 8Cy-re R². Now when does || - willa s hold? We show that for every point on the boundary, w, (a, w) 2 m (a. (a..)). w.. this implies that W. is indeed inside the ball. We have
Cf+ew l| - ull C(a, W.) n
Cs+eu
m a. w) m (a, W 2 ((a, w)
l| - u1l
n
P ||w - w wull
Cste ([[ - ull + R²)
2 2n
n
Then using Lemma
( w) (a,
Pll -well
P
Crrew (Ilw -1l3 R²)
2n
p R²
Cs+ed (8R² R²) R²(
P
9C 9Cs+em R)
2n
2n
Now if R 18c then ma w) m ( a, w w() O. Thus all in all
([(a) - M(a)) 5 8Cs+cw | ul
26

---

Lemma 6. We have the following upper bounds
1. ||ul[ O()) with high probabilty.
2. BA. 0(1)
Proof. 1. Since f + EU p-strongly convex, one can decompose f((w + cv(() -/ll ] + h(w) for some convex function h(-). Then
| 51ß2 + 2 I|lll1 h(u) & A 211111 h(0) = (n)
Thus this implies ||ul|] (n).
2. In similar fashion, have for B
A Au 511 f()) + eu)
||3 |
1 [ 2
1(0) + co)
n
Let AT {
A7
At)
Now we use the definition of Á to obtain a lower bound:
2 |lu - 5112 + f(u) (u) 2 | + 1 u f
2 A uu/u- 2 (M, +A(HT ( u()uu
n;d
Thus plugging in w = 0 in the optimization yields an upper bound, which is quadratic inequality in n4 u:
nid (1t u)² A(1 u) (A,u 2
2 -1111 ((0) (0) s
(25)
Now note that for a quadratic optimization with 20 0
- = a- Va² 4b
a+ Va² + 4b
xx
2
2
Whence
|x| |a| Va² + 4b
|a| + |a| + 2Vb
|a| vb
We apply this result to 25
2 1 (Å, - -8:1++ 2
| ul
113112 f(0)+ + +0)
n1
An;
2
2 1 3,1+ 2
1111 ||21uul
2
115112 f(0) + e4)
5
N;
n:
An;
Now taking expectation and using a combination Schwhy-Schwarz and Jensen inequalities yields
2 BA, 11 ni
2 2 n;
2
Ex,1114 ul
BA, || A An; V Bx, f(0) + (0)
Now note that EÅ, O. and by the independence of the rows:
d n
Bx T 2
Σ Jil
(A(A) =
Σ j=l
B
Ji jajil
ji
By assumption, for each row å of Å; we have that Ba, ||@:1]3 0(1), which implies 11 A (d). Therefore, by the previous part, since ||u|| < - 24((0, then By|lu|| h1(1)) A 11 = (cd) by assumption the y. Hence it can be seen that Bx O(1))
27

---

Now we are ready to conclude the proof with the following lemma.
Lemma 7. We have the following
1. EAgay (a' y) O(1) E [3]
2. Bxgayylu =
Proof. 1. First note that
24 (2
By (a" (a'u-))22 y) =BA.ya.y
2
i ((- (()a-=+))"u)))) ())))))( j=1
Moreover,
24
124
Bxs..y aaau-))a
2 1=1
I(a pa+ =1)++)))=1n
29
24
Bx.
1y1 max(1 ul. ((a 11) u/>y
1
1=1
24
2
(29)
(1)2" ul! + I(a m1))
/=1
24
2 (29)
(Bly)4n-20 (BI u22 BB u1)
/=1
By assumption Bly & C for some constant C > 0 that is inmeesion-indeeenddent Moreover, by
assumption, [a 100)1)1)1 Č
Iuull dr Also, from the previous lemma, Bluu² un] 0(1). The
claim follows.
First note that ||u - wolls = 23 Minkowski's inequality
v-aTu
||
all and since f 0, + -aaass s2 la hence by
1+.aa22
BA w s x B j,y la u 1| aal
x B say la u yf ( مa 14)
8, E
14) || 1a- 1 Hllls)
u
s 81 B u - إل + B la u - >1112=1118
s 823 BA (a - y) ,.y, A, | (a- و
+ 8,3 BA....y (a y) 1 mlll
Now since we assumed that the objective is p-strongly convex, or there exists p > 0 that || s I denoting w, as the jth row of 2- we have by the inequality between Frobenius and Operator norm, ||wxl12 S J. Now by the assumptions we have
n.
E EA 1| (a -11)113 Ez
Σ j=1
(aa u0) w))
Bx,$
Eayy((a
(a- w
Σ
Ba 10) 1 Tw
J=1
1.=1,,
|
+
Σ
Bal(a ) (a w2) s Cd
C(df -d) 5 C pad
d3
/=1
28

---

We also have for the other term:
B.S.a.y ||2 "1l B...a.,y1 1
Note that ||2221o12 uall2
||$2 ||s2-1/211 1opp ||2 1/2 pll2- Thus it is sufficient to analyze Ja p² 12-12²² Let r R
be an upper bound for 2² ",", that is 1² "t" 1. Note that by the Schur complement property, need to find the smallest > 0 such that 92 / Recall that Ω == AÄTÄ
with holds with high probability, and by assumption H > pl, thus it suffices to find the largest that AÄ Á + pl Jup² 0. Let Á == Á M be centered. This problem is equivalent having II(Á' + M) + +llv|] (n v)2 2 0 for every v E Rd
Thus we should have
(n²² v)2
[| + v) + pllvll
(H Let 1" := supy Ml M
We show 1" (n for some 0 with high probability. Let
arg max (u v
This implies
+
|1al11 1|''11
II + My IB -
On the other hand, by triangle inequality have
Mv (IIC'' My [
4
|1
v-) S nr
11 +
11
11 11
ne
Now we have
4
Iull
1|
11
4llaa1
v' II(Á' + M) 112 1|l
nr
+4 '1:2p
pllv*11
pne
We obtain quadratic inequality in 1"
A11A'112.
411pal12
s 0 pne
pme
Which implies the following upper bound
411
|ul
μ 2- nh"
min(
pnt
pur P
According to Lemma 8 ||'ll S nnt with probabiliy expectation, also observe that
C n²
loggddn)
Thus using the law of total
4nr
|
log(d d + n)
Exg.a,y 1| s Bx,,,a. ||52 "1ll s Basay (n 2- 2 u1)² s
+
+41
+ +C
pig
pize
pn
For <s f.- || 0(1) by assumption, the RHS goes zero
Lemma 8. Let A' be centered random matrix matrix following the assumptions. We have IIA'llop S Cn with probability at least (og((d)))
Proof. First, provide upper bound for the expectation Bx-llÁ'lllo, using the matrix Bernstein inequality and the symmetrization technique. First we construct a corresponding hermitian matrix:
=
1(20
0
-
-
A llop
op
1=1
29

---

E With X, == E
where Eg is the all-zere matrix except (i. -nntryy where it is equal 1.
Note that I= > En and E, essentially picks the i'th row of A', which is a." Let ( be an iid sequence of symmetric Bernoulii random variables supported (+1), independent of Xi's s/s. Then by the symmetrization lemma Vershynin 2018). we have
xx llop BA
Σ
S B
Σ
op
Now conditioning on Á' equivalently X; since eX,'s ss independent zero-mean symmetric matrices of size (d + n) x (d+ n) with bounded operator norm, we can leverage Matrix Bernstein obtain (s means up to some constant)
inequality Vershynin 2018
1/2
Bx ||'' & Vlog(d + B
Σ i-1
Beg (xX))
log ( n)B &
max |X|lop Isish
op
1/2
Vlg(( +1
log(d + n) max X
llop
1=1
lp
A En
-log d +1
Σ a a
T
log(d + B)
max Isisn
|X,
lpp
Note that for |Xillop' we have
X X
||E,A'l
A'v v
max v)2 =1
max livil==1
Moreover, using triangle inequality
Σ E,A'A
En
E AAA'A E,
7
E 8 a
lp
op
||
+
op
11
max 1srsn
||
Σ
a/a
1=1
op
Combining these results along with Jensen's inequality yields
1/2
Ex-llÄ'llop vlog(d+ m)
By max IsisH
|| + Bx
Σ
a op
log(d + n)E
max ||
isisH
Now to analyze Ex Σ "aa
we use the symmetrization trick again with iid Bernoulli (</)%
and Bernstein's similar to Vershynin's
E
Bi
Kfa
By
8
+
Σ
Bi &
i=1
lop
i=1
lop
A=1
op
n1
B
E a
+
Ba a
1/2
$ vlognE
B Be
a
log nB
max Isisn
a
llop
Biy 8 2
op
1=1
op
1/2
VlognB A
||
a
log nB
max |all Istsh
Bag a 7
op
i=1
1/2
$ VlognB x
max
|
Σ
a
+ log nB A
max Isisn
||
Σ
Eg a -T
1sisn
1=1
lp
op
30

---

Now for the first term, applying Cauchy Schwartz yields
1/2
1/2
B max
B
max
|
A
8.a:
/T
Isig
op
Isigh
1=1
lpp
Moreover, for the last term we have from our assumptions
||vl2
C
Ex 3
max
Ex,
(a
v)2
max M
C
liv|e=1
d
Thus have
1/2
X
Σ
a/a7
$
Vlog n
Bx
max 1 Isish
Σ 7/57
+ lognB
nB
Ex
max ||ā + Isisa
opp
1/2
Solving for
Bi
Σ
8/a
yields
1/2 opp
1/2
1/2
B
a,a;
Vlogn Ex max Isisn
lognBB
max ||ā;|| + C) 1sran
opp
Thus
B
a
$ lognB
x
max || C Isisn
i=1
op
Summarising, we have
1/2
Bx |lpo s vlog(d + n)
max || + C/ B max || log nB
log(d + n)B
max ||قB Isisn
Isign Thus it remains provide upper bound for B maxisisn
IsisH
|| have by Jensen's
Bx max Isisn
[
S Ex
max Isish
| S
Ex ||
Now by Definition 2 and Holder's we have
Eg 11/2/12
Σ
22 222 Exp aay ajg
Σ
Bx
1/3
Bgg
'6
1/3
Egg
1/3
Σ
C d
S
a1.0g,03
aj.02.ay
Thus
B max ||@ill2 s Cn² Isish
All all
Ex-ll''llop & log(d + n)n
Thus by Markov's inequality for >>0
E 11
C' lolgg nyn' C' C'log(d+
P P(IIA'llop 2 Cnt+r)= s
Cnf+s
n
n²
Lemma For any function v/ BR + R with bounded third derivative, ((w) = (ad w) regular
Proof.
We only need to verify the third order Taylor remainder bound,
S3
Σ Owa, Oway Oway
Σ
Eav"" (a" "W)tm Mo Vay = v)
Vo Vas
01.02.03
By Cauchy Schwartz, we have
I². Ow Ow Owas
Σ an.ora.y
Va, Va, VazVas s
/ (au""(a" w)2 /aaa
By boundedness of the third derivative of t, and assumptions
a²
||
Σ
Va VasVas S CC d3/2 Cy 1lvll
Öwa,Ow., Owa
31

---

E Generalized CGMT
After reducing the amalysis to the equivalent gaussian model, one can leverage a new generalization
of the CGMT Akhtiamov et al. [2024] to analyze ((G) which is stated follows and recover the precise asymptotic properties of the solutions.
Theorem (Generalized CGMT), Let Sw .R C RR........ Sun C I be compact convex sets. Denote S, Sv X .... x Sup let v E S, stand for (vi...., VK) E Sn x... Sv, and ((w, v) Sw X S. - R. be convex on Sw and concave on Sv. Also let Ei...., Eg E Rdxd be arbitrary PSD matrices. Furthermore, les G E Rnixd ,..., Gy R .l.....88 Bt Rd h1 ER" hg e R all have iid N(0, 1) components and G = (G)...., GR), g (g)...... gg), (hi....,hy h2) be the corresponding k-tuples. Define
Σ V.G.E SeSw VES,
P(G) == min max
(26)
(g. h) == min max wES., YES,
Ivvll2g/ 2 w || wll2h? ve (w.
(27)
Let S be arbitrary open subset of Sw and S = Sw \ S. Let &s be the optimal value of the optimization 27 when Sw is restricted to S. Assume also that there exist e, 0, o. &e such that
t s 2 + 36
(g h) + with probability least
sz > se 5 with probubility at least é
Then for the optimal solution of the optimization 26 have P(w S) -2k+1
F Proof of Theorem
By leveraging universality theorem we ready to analyze the linear regression problem descrided in 2 in full details
Proof. First note that for the ground truth we have w. = argminBB - x² = R. R.y.. By simple transformation, the constraint could also be written as
xx
X
y)
(111
w =
We would like to write for a with i.d entries:
X y) = GS
Indeed
GS STS===---= BB
X
X y) =B
R₂ Rxy R
yT
Ry
Now we can denote S
1/2
R R!/2
T/2
R,y
with RA = Ry RRyRR,x R Ray And R. T/2R.yy = -R!2 w..... w..
Thus can write the optimization as
min || - woll
R.
1/2 1/((w -w.)
8.1
G
R 1/2
= 0
32

---

we can write the optimization as
min ||w - woll
R 1/2
w -w.)
s.1 G
= 0
R 1/2
Letu: :- : Rw w.) and x= w. Wo, then
min |RR
1/2
x||
u
s.1 G R
=0
We Lagrange multiplier to bring in the constraint:
min max |R, 1/2 u+ x|| v
-R
Now we can appeal to CGMT to obtain the AO:
min max R 1/2 u+ x|| [[v]] u R/33) + (-R I
Dropping the g' R term and doing the optimization the direction of v, yields
min max R 1/2 u x/1 +Blhh////liee + RA Bg"u
820
Using the identity vx = man $
Bllbll
B|lhl|
min max |R 1/2 +20,u 620
x+
x||
(|]ul]2+ RA) + Bg'
2r
Now we obtain quadratic optimization over a which could be rewritten as
(uT
1)
BY 2T x R
R +
T/2 B
R 1/2 x
||x||
fg
1
Doing the optimization over u, we are left with
min max ||x|| +
BT
+
Bvn
RA (R
x 2 g) (R=1 1 +
BVT 1) (R
1/2 x 28)
B
r20 B20
2
2r
2r
Expanding the third term yields
min max ||x + Bryn
Byn
Rs
x²RRT11 TRR_, + B
1)
R-- -RR,1
1/2
B²
(R-1 + B 1--1-
720 $20
2
2r
2r
4
2r
Let z = R 1/2 x, we assume Ezz" = | d I, and cu = R,
||z||²
using concentration:
Bryūi
Byn RA d TiR_" "RR"
Bvn
8 d
Byn D
min max 1|x112
1)
-
R-
Tr(R,1
720 B20
2T
d
2r
Therefore
min max ||x||2 +
BTVR
+
Bin Rs ea S p(r)
Byn dr
B2
r p(r)
1 Byn dr
720 B20
2r
r(1+
Dropping the constant term ||x||2 we arrive at the following scalarized optimization
BT
BVn Rs - f p(r)
cg
B² r
min max
+
Bym dr r(1 + 27 r)
d
+20 $20
2r
33

---

Let e', := g. To analyze the optimization further, noting that the objective is differentiable w.r.t B, by taking derivatives we have the optimal point:
Tvn
VnRA
d f p(r) T( =(vir2 + 4rTB 4e'a Vn)
dr
2r
2(27 + rBB)22
By
BRAVH vn
ff p(r)
BVT(BR 4e'a)
dr =
2
2r
2(2T + +BByn)2
Rearranging
V VnRa d ff p(r) -2 PVvr2 4rrB - 4e's Vn)
dr
(2T+rBvn)
A' ViRA = 5 p(r) p()) FV Vn4eea)
dr
(2T (BT+rBun)2
Summing and subtracting:
n ==dʃ p(r) B²² + 2NTTTBB dr = d f p())
2 472
(2r (rT+) dr
(2T+BBV7)²
VnRa =d f p(r))
(2TTB VT)
dr (2T (2T+rBV7)2
Thus
d n
d = / p(r) 2nTTTB+ + 472
dr = f p(r)
2T dr
2r
2T Byn
Sp(-
+ 10)
(2T (2T+rBVm))
2T rBrn
Byn
VūRA = d S p(r)
(2TTB -4' vn)
dr
(2r + 1BBR2
If one can solve d-n yields
21 Spl
2 Byn
+ 10) to find =
8, 7, then plugging into the second equation
d Bvn
VRR = f p(r)
1220072 4e', 4c vn)
dr d f p(r) r2+ dr
2007 4e', vn
(0T+
Which yields the following equation for ?2
Vn
R^ + 4de's /
p(r)
x2 20d f p(r) (2)r)m)) dr
(2 (2+ dr
Now note that
d d-1
1 p(r)
2 dr dr= 1 p(r) +(2++ dr 2T Fr+ dr 1 p(r)
2r
d
2 2+r0
(2+r0vm)
28 S p(r) (2+ dr +4 ʃ (0+ dr
(())
Let 4 pir) (2tr0vn)z dr, a' = 20 J p()) (2tr0vnjz dr and. Then the expression for could be
written
²= n
RRA + Bea)
da'
As +a' = d-n d one can write
22 =
n
(Ra + aa.)) =
n
RR + +(ee)
n
RA +
Qn
d( d-n a))
d n ad
d(1 a)
d(1- - (r) n
Now the generalization error is
2- 2n - d(1 a))
nB
(2n d) + (dRA + ne,)a
Ra +
ea
d(1 a)
d(1 a)
n
da
34

---

With =4 4f p(r)
(2410VT)2 dr. Now note that using Cauchy Schwarz applied to vp(r) and pvp(r)
24r
2 d- d (=) p(r) 2+ r0nn dr) $ ʃ p(r)dr) ʃ
4p(r) (2+ dr =a
Thus a 2 ( )2 Now for the scalar distribution p(r) = o since 2+ 2+r 2+ カ-n カ-n then a ( 22) Thus achieves its lower bound (uniquely) for the scalar distribution. Now note that assuming n, d, eas R& are fixed, the generalization error increasing in a, thus the error expression for the generalization error in the scalar distribution case is lower bound.
2m
2d
G Useful Results
Lemma 10. Given a weight vector w, and assuming the feature vectors are equally likely be drawn from class I or class and satisfy part 2 of Assumptions 4 given by
the corresponding classification error is
M w VWT
1 W
20
20
(28)
W
VW
Lemma 11. Assume that the feature vectors are equally likely to be drawn from class or class Then the classification error corresponding
Assumptions 4 hold and Wo is defined as in Assumption to Wo is equal to
2
-I-rTr(E) Σ2)-1
vI -I- E2)
(I, + Σn) + T
+2)
T
H Proof of Lemma 1
Let us proceed prove Lemma 1 We will take the gradient of 28 w.r.t and set to 0:
Proof.
w unuee
VW
E,w w E2wWnnt - Hu2 wEzw
V
2
Σzw
4v2x
exp
2w E2w
2ig w
Ew
11, w w E2w
exp(
)
where 52
4
$2
2
VWT' Σzw
1 w
wT WHHI w
VW E
E Ej
w pi wEiw
V
2
exp
2
Vw Σ
4v2n
2w7E,w
1e w
Ew
1
1 w
14,w
exp
where 51
4 4
51
VW M
W/EW
Hence, the following equality holds any optimal w:
2 exp (- - ( s/Ziw)
1
(H222 53
$2 exp
51
Therefore, w + -1 (Tip1 1 - -2z42), where we have
2 )
$2
3 = si exp (-
32 = -22eepp (-
52
exp
)
i 82
exp
51
2
2
35

---

Now we can consider the following optimization over 4 scalar variables:
1
min 20 $2. Vw
(29)
VW
Note that since the optimization (29h is low-dimensional, by the Convexity Lemma Liese and Miescke [2008), we can interchange the limit in n and min, implying that we can analyze the concentrated optimization instead. We then arrive at the following fixed point equations using Assumptions 4
= (3
+3 (p 2rrr2r)
(30)
-T((5 Dj 1 +3222) Tzr)d
(31)
11
2
Tr(
+ 3) + 2 22(r2)
(32)
2
8 = +,222) (72 - r
(33)
Note that, since we assume p exchangeable in its arguments, the system of equations (30) is invariant under the transformation (51, $2. (-S2, 12, (1). As such, 51 =2 and fi f2 at the optimal point, implying that w. = (E, + Σg) (Ml (22 is the optimal classifier, as for the chosen linear classification procedure the performance in invariant to the rescalings of the classifier vector and therefore we can completely drop 81, $2, /1, /2 from the equations.
I Proof of Theorem 3
By Gaussian universality proved in Theorem we analyze the binary classification problem as follows
Proof. Define
Rg Bpr.ee Now (, +,,)) (1) P. B. w.w. w.w.
(1 - la 2 12
(1-
Note that the eigenvalue density of R2 captured by ((5,, s2) (1-))) 21((1-)) assuming (2) p. where p is the joint EPD function of Σ and Σn.
d (s1 + s2)
We would like start with finding a. Note that the data matrix X be decomposed as follows where G G2 are i.i.d. standard normal:
G G
1/2 + (
9
1
X =
G
2
We then have:
G 1/2
[1
0
[ wo
Xwn =
_r 2
1/2
Wo
0
1
[ez wo
(34)
36

---

It is immediate to see that the first term of (34) is a centered normally distributed random vector with covariance diag( W 2 Wo...... w/ - Wo. W 20222o Wo.
w/ W2oo),, and therefore its norm con-
centrates to (2 + wo = O Tr Σn) woll) according to our assumptions. The second term of 34 is deterministic vector of norm O V woll Similarly:
y' Xwo (1T -12)]
/ Wo G2 wo
1/2
+ -10
1
0
1 wo 1 12 wo
=11
-17)
G G//////o wo 1/2
G2 wo
+
*2(1 122
n
wo
(35)
Note that we can drop the first term of (35) compared to the second term. Indeed, the first term is centered normal random variable with variance w (E) + w2) = O(Iwwoll (rr)) Σ2)) and the
second term is deterministic quantity of order (n]] wo vI Thus
Xwo
5 (MI - (12) wo
Xwoll 12
2wo (2) + Wo + [14 wo) + 212 wo)
Moreover, by independence of n from μr drop the first term in (μ1 112) wo (,(111 122) n (11 p22'' ww and have
(M) - =2 w. (w1 - (221-22 (EI+ "M 222) - 2(1 - rTT[[ E2)
On the other hand:
o wo in 17 to w. = =, (II E2) 1100-11(4 (H1 - k22
Which implies that drop the cross term in the expansion of {1r wo)
-12) ) 1-r 1 2. - r)2
(MI wo) = 2 (E, E2)
[
(E,
d²
We can drop the first without loss of generality as l, usually does not grow with This implies that we have for a
11(1-)) 2Tr Σz)
2 2d d
a
$ Tr Σx)) + (1-rr) Ti
(E) -1)
2T< Ez) 2
(To Ex))
(((--)²
-2)
d²
Then SGD converges to
min ||w awoll
w
S.S y Xw
Introducing a Lagrange multiplier v R"
1/2
min max ||w - awoll + T
w T Mw vTy
Using Theorem 4 from Akhtiamov et al. 2024
min max - - + Σ
[|vll] x 1/2 + 112
+/114/ +/1(-1)'
1=1
37

---

Denoting Bi := l|vell and performing optimization over the direction of vy:
min max || -1 aoll +
Σ
B. /2
|1= |1 14
+ 111)
1=1
We have
min max l|w- - awoll 2 +
Σ
Br 2
w+ w+
V
12 wll + +u, 2
(-1))))
w A.02
1=1
Applying the square root trick to the norm inside the objective we arrive at:
min max ||w awoll + Σ 22, P1.0
Big |/? w +
B Br
n (
w|] + (HL w + (-1)1)3
V2
2
2T
[=1
Introducing y as the Fenchel duals for (1, w (-1) we have:
min n..220.w p1...20.11.7
lwwlf
Big B 2
w+
V 2
n BiTi
2T,
Bi
V 2
n
mm
(1
1/2 2/12 +1/ 2
Performing optimization over w yields:
min 1.m2001.220000
max
a
@@olwoll2 2 +
2
B
2
2 2T,
n
Bi
(ri( (ri(-1)'
)
4
i=1
-(-awo
1/2 gi g1+ "1
1/2
B1
n
B2
n
y22u2)
T (1+
B1
B2
g2)
+
4T
2
2
4T2
2
2T
2
2T²
(-awo+ ( gi + B g2)
1/2
1/2
+
4T
B1
2
n
4T2
B2
2 72H22
n
We drop the a² [|ooll? from the objective because it does not contain any of the variables the optimization is performed over and therefore dropping it will not change the optimal values of B1, 72,
72, TI, T2. We obtain:
min T. Bi B 2.
max
BIT
Bi
(yi(-1)'
Vi a²
2w
B1
+
B2
Σ2)
wD
2
2
22
2T
2T2
2
B3
gi
12 (I+
B1
n
Σ
B2
Σn)
-1
g1
B2
4 82
T T12
-
(1+ (1+
B1
11
Σ
+
B2
11
-1
1/2
g2
4
2T
2
2T
2
2T
2
2T2
2
nBfr
B1
n
B2
nF²y2
B1
n
B2
T (1+
+
21
En)
11
14 (1+
21 +
E2)
#2
32?7
2T
2
2T
2
32T
2T
2
2T
2m
B1
n
7law (1+
2T
B1
n
Σ
+
2m
B2
n
2
En)
+
2Tz
B2
2
n
r2awo (1+ (1+
2Tz
B2
-
n
2
+
2T
B2
2
1 Σ2)
142
nBI (1+ + 2n1
B1
Σ
B2
11
Σn)
-1
142
16T
2
2T2
2
The objective above can be rewritten in the integral form the following way:
min Ti.m020 p..220p...0000m 20.1..1
max
Σ
2
n
2
BTT
2
22
Bi
(y-(-1)²
y
(1+
2T
B
n
2T
B2
2
n
Σ
wo
nBp
ngty
dd { 52)
ds / 1 p(51. S2)
32T
32T3
ds
1+
2T
B1
51
+
2T
B3
52
1+
2r
B1
TT
+
2T2
02
T
2
52
B1
B1
B2
B2 n
82
B2
7raw (1+
Σ
+
Σn)
p1 +
2 122 (1+
+
Στ) -1
112
2T
2T
2r2
2
2r²
2rz
2
2
-2r
((S1..2)
32
ds
02
1+
2Tg
2
51
+
2r2
v
12
38

---

Note that
a2w (I+
B1
n1
-1
B2
11 Σ2)
wo
(T
RI+
B1
B2
n
-
2TI
V2
2Tz
2T
2Tz
Moreover
B1
B2
x2) 11 d f
((51, $2)
Tr(Ro(I+
p(s).
ds2
2T
2
1+
B1
v
2T.
8z
14
221
And
B1
B2
1)(1-)
B1
n
B2
w/ (I+
2T1 2
2rz
Σ2)
p1
d
TT((I+
2T V2
Ei
2T2
-2)
(E) +22)
The latter term can be derived in the integral form as:
B1 2T
B2
- (2, (()+)((+++))))))) - - (((1.)2) 52)
(si + 82)
Tr (I
ds ds
2r
1+
Pi 2m
2T: 52
l
Since p(1,, s2) is exchangeable in its arguments, under the transformation that swaps (ß1, 7I. with (B2, T2, -22). Therefore, B := B1 = B2. == Ti T2 and y y2 = -y1 holds at the optimal point. The objective then reduces to the following:
that the latter objective remains invariant
min max
n
BT
nB (y 2
2 - | p()),
da² (s), 82) + d (xite))
"B²
167
r)
ds|ds? ds2
r20 920.y
1 (s1 + 22)
(36)
BY ( + $2)
2 [ p(s), 82)
-1.((1-))
(37)
1+ 2r
52)
Note that can be found explicitly in terms of ß and r as the optimization over y is quadratic. Denote
eo |wo 2 To facilitate derivations, let introduce few notations. Let
Fi B E.m) = S S2) da
nB'y" 167 (1 r) 21. r)
2
By (s1
82)
ds dd2
1 + B
(s)
B Fe( r B) ()) d 1 S2)
ds
1+ 2r
(
Thus the objective is
B min max -F(( 220 B20.y
Fz (2(
2 B
n
BT +
nB
- x
7
4
Now taking derivatives w.r.t 7 yields
B
F.Fi .) -2
0,
0, F2 8. B
-
0,FF2xx
r
Now for B:
B
1
FgFi( (x (.FFF(x.))
T
B
2
B
1
FgF2(
B)
F2
B)
0 Fxx,B)
B
39

---

Setting the derivative of the objective w.r.t 7 to 0:
oIF + 0xF +
p
n1 B 2
x²
(V
Multiplying by 1² and dropping B yields:
0, +.
T
12
n
x2
/// =
(38)
Derivative w.r.t. B
2 0,Fi(x,)))
F
F2(
- F2 B) +
1
n1
(y
x
4 =0
=
V 2T
Multiplying by T,
B -,Fi((. - F2 ()) 0, (2x, +
n
n (
1) =0
)
2 2/2"
2
Therefore the set of equations is:
O, -
-0, - - -
Summing the equations yields
2T
n
2
F2
.) +2
TT
0
F2 - = = z
B
B
Which implies
d a 1 p()).5))
2
dslds ds2 2 n
2
1+
51 52)
V Multiplying both sides by dr and introducing 0 a we obtain:
ʃ s())
V (s1 s2)
dssdds? n
1+ 3/ (5) 52)
This can be rewritten as:
ʃ S p(S1.
2v2
ddsids2 d
2V2+ 0
We arrive at the following equation for 0:
d-
/ ((S1.)2)
2v2
ds
(39)
d
2v2+ + 0 52)
The last equation above can reformulated terms of the Stiltjes transform as follows:
2v2 Sx 0 On
2V2 d-n 0v/n
S2,tH,
d
After finding from the equation above, we proceed to identify the optimal value of y. We will do so by taking the derivative of (36) by y and setting to O:
40

---

nO'r (1 - 8
V 001 2)
n
p(5), 52)
dslds2 oo 2 p(51,,5) .2)
n
- (1.(1-r)(s) s2) 8
-
1 7 (31 52)
1+
2V 2
(51 s2)
Dividing both sides by 0, factoring vn out and using 39 we obtain:
VVn 2V2
VTo(1- r) d n
"V 2/ Hs1 /
((S1,52) 1.(1 (sl- + 52)
8
2
1+ V2 (si + +2)
Hence, we can find y via
-1
1
V2n0
r)
(1-0) ʃ
1.(1 (1) 52)
y
p(5), 52)
8d
1 8
1 [ 52)
Finally, to find r, recall (40
n (y
y²
V2
Using F2 is quadratic in its second argument have:
n
n
x
V2
12 y
4
n
n
x
2(0,F2(I.0)
5
8xFi(x,))
4
72 = (0,F((xx,) + V
n
-1
ク (r
n
x2
1 - -
We have
Fi = /
(2)
da² (s1, + mx²y²
16
(1 - r) + 21, (5)
dsidss
1 [(1 + +2)
Then
da²
[ (2511)))
n
6(51. 52) 82)
0, F,Fi(x,
dsids2
2
V 2
(1+ [(] + 52) v TT)
nxy² (1 -
[ ((81182)
dspds2
8
1 (s1 52) n
nx2 r)
n
/
(51+
(()).)2)
ds ds2
32
V
2
(1+ {(1 52) /n)
n
[ (25r15))
(s) S2) -1
-ar. (1 r)y
2
ds ds2
1 (s1 52) n
a1.(1 (1))x n
r)xy
2 {
((1
ds dd2
2
(1 (s) 52) k
41

---

Moreover
(x1+)) 0²
02 = ʃ p(51)82)
ds dsids2
V (5) 52)
Then
dd²
n
(s1 + 52)
0 0gF2(x,0)
((5)
(1+ 2 V + dspis2
8
V2
Thus, all in all:
22
11
do2
n
/ ʃ (2))
(s1 + s2)
ds dss
2 8
2
(1+ e / 52))
2 ))+
da
n
J ((5),82)
(111 82) 82)
2 (x
ds dsids2
2
(1+ 2 +22 v2)
(1 (1))
{ p(s).52) .2)
1
n ds
8
+ 281 +22
n0 n02y2(1-1)
[m I | (25)152)
(5) 52)
dsjdss
32
2
(1+ (s1 s2) V )
[ (25)
(2)
aa. - (1-r)y
ds dsids2
1+ (s) + 52) V2
a1,(1 -r)0yn [ (2)
dsb ds2
4
(1 (1+ (() 52) /
V2n (d - n)
(1- ʃ ʃ p(S), 52) 1. () 52)
y
(40)
2
8d
1 2 [ + 52)
1-3
The generalization error can be found through Q
L.1 Single direction case.
In the special case when Σ₁ = Ez = 2 we obtain as R
(1-))
d la (1)))++++)))
Xwo
((I-r) Tr(E, + E2)
Xwoll2
Tr( [Σ] + Σn)) + All-)) TT2 Σ + Σz)
d
1. -0
2 d
1
12 d' 2
(2(1 r) r) d'
We also have
1, - r) d
20F
a
2 (1-))
Ti 20r2 I+ f (1 (1- (r(
20r2 7 1- 1
((1-)) TP (22(20))) D)
d=
d (1 r) Z
L 2
1. 2
() dr:(1-r) -
12 20
2200
dr? 2
(d-r))
(12 + 2 df
2,(1 (1 r) of
4
40t
2
Act
Multiplying both sides by ('(1 - d arrive at:
42

---

d
r: at at' (1-1)
(41)
20
bn 4ot + 2) +
12 d
Note that plugging in Wo (2) + +2) - (11 (22 1n for Σ = - of La into the expression for the generalization error yields
j wo
1. (111r) 2002
ea Q
=Q
w! W
12(1 -) -0 c r1-r)
Taking Q-1 of both sides and then squaring them arrive at:
(1 de
r) d²
2od o (ea) (.(1- (1-))
+
( 201- + -r)
(2 4 or in
M-r)d
d=
This yields that by taking ;= d(l-r)
g²
d
2 P
-2
1. 20
Q (-
2(1-r) 0 (e,))
We thus obtain from 41
e (ea
(42)
(e,
(e +
(-,
We proceed to find next. From the general case we had
2v2
2v2 Byn
0 0V +
d
Now plugging for the distribution of 1 En yields
A
2
d n
0 n
11
2 d
d
d
0
(d n)n
Using 41
we can simplify the last expression above:
(2h0(1-r)(d=))
1 1 ʃ ʃ p(S)))2)
1o(1 (o(1-r)(s) +22)
y
8d
1 2 (s1 + +2)
v2n0 r) - 11)
+
2
8d
1 + e ( +2)
2
22n dv2n
(d-n) (1 - (d -n)
+
2
8d
dvzn 2
2(d-n)o V2
Thus we can write for
2 (1
r))
2
8
+ d-n
d-n
n(1 -r)
d -
d
(e.
d(1 rl)
(1
where p σ²
2
Q- (ea
4x
43

---

Furthermore, we have for ??
n
d6
ʃ p()
(1 2 (s) + sz)) dsids2
(s1 + s2)2
-1
2
8
2
Y
da²
(2), + 52)
V 2
(y
4
+
2
2 (23118))
(1+ 2 (s) + s2)
ds ds2
n0y² -r)
ʃ ʃ (21).52)
1
dsp
8
1+ 1 + 52) 7
nO (1)
n [ [ (25
(si s2)
ds ds2
32
2
(1+ (5) 52) V
2
-1t.(1 - -1)y 2 [ [ (25)..2))
n
(s1+
ds
1+ (5) 52) /
at. (1- f S ((51)32)
ds ds ds2
(1+ o (51 52) /ワ)
Simplifying furthermore yields
n²
-= |
[1-4 n
[
= [ f 52)),
(d-n)²
ds ds2
d= (d-n)²
(x- x2 /) I s d²p(s1, - (1,
12 de
20r )0
dsidss
d(1 ((1-)) 22))
n (d-n)or (1 r))
2d
/ [ 52)) 52)
1
d ds ds2
8
d-n
2nd
2 (1 rr)
2 ds dss2
n (d [d-n)-o*
/ ʃ S2) 52)
+
32
n1
(1 - ,>v) S (()))32)
d ds
J-n
at,(1 r)
(d-n) yn
2d
I ((3),82)
dspds2 =
4
d )
Further manipulation leads to
y
r
1 _
p
+ py²
ry(1 1 (1
ry
K
4
0
(ea)2
K"
4x
8k2
K
y2
r2
1 py²
4x + py²
(1- | ,
(1
(1
K
4
Q
(ew
8k2
K
P
p.
4 y² + [1 - (1 - 1 >
o (e) 1 -
r2
K
8x2
4x
Recall that ['=
and
r. Hence, we obtain:
2
p
P
z 3² ) + (1- 11-0---r)++r--D0--
(43)
K 1
8x²
4x
K
1-(1-))
On the other hand, y
and
r = (=11 combining these fact with 43 yields
1
(2xp v)
cp Q
(2x² +x2p 2x(p 1) p) + +2²)
44

---

45

---

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

---

Justification:
The theoretical results, assumptions, and definitions are provided in sections Moreover, the complete proof of arguments in the main body presented in the Appendices B
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: All the necessary details are given in Section Moreover, the code is attached to the supplementary materials.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
47

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
The code is attached to the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines
cc/
mublic/quidesn Coweeeddeeeeeeeuuuuuuuuuuueeeee ssionpolicy for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (ht
/ //nips httppss.cc/pbllc/guuucc...o
See//oooSuullll Submis as ss issiions wwwssssssiiiigoo..o for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
All the necessary details are given in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: As the main focus of the paper is the theoretical contribution, the experiments are conducted using specific data distributions whose statistics are exactly known. (x2, Bernoulli, Gaussian)
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
48

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out of range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: All the necessary details are given in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics /tttts::////uripppssss http:///wwppppccooooooocccccccad
Answer: [Yes]
Justification:
The research conducted in this paper conforms with Neurips Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Since this paper is concerned with the mathematical foundations AI.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
49

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Since this paper is concerned with the mathematical foundations of AI.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All the necessary details given in Section
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, paper thcode com dataaetteett has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
50

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Since this paper is concerned with the mathematical foundations of AI.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mooel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Since this paper is concerned with the mathematical foundations of Al.
Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Since this paper is concerned with the mathematical foundations Al.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
51


Reviews:
[{"review_id": "82zcsNab39", "reviewer": "Reviewer_vrcM", "summary": "This work considers transfer learning (fine-tuning) for linear models in the over-parameterized regime in the proportional regime $k / n \\rightarrow \\infty$.  In this setting, gradient descent converges to the solution a convex optimization problem with linear constraints. This work builds on this result to show that for a distribution $P$, the test error converges to the test error of a Gaussian distribution with mean and covariance equal to that of $P$---in other words, universality holds.", "questions": "1. Why is renormalization needed in in the classification problem setting? \n2. In definition 2, the authors claim that the assumptions are satisfied in practice. Could the authors expand on line 156-160 and explain the results of Seddik et al. ?\n3. How do I interpret quantities like $t$ and $\\theta$ in theorem 2?", "limitations": "Limitations are addressed but the authors could comment on the assumptions and their limitations.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "This work brings a fairly atypical and and relatively unexplored perspective to transfer learning. The results hold for a large family of distributions (theorem 1), although limited to linear models in the infinite width regime. Finally, the results indicate that Transfer learning depends on the noise levels of the problem, i.e., one should choose to fine-tune the model if the noise level is very high (remark 1). I unfortunately did not check all the proofs carefully but appreciate the authors attempt at distilling the results into the main paper despite the depth of results.", "weaknesses": "My main concern is that the setting is not conducive to studying transfer learning. Transfer learning is a fundamentally small-data phenemenon, i.e., the target dataset usually contains a limited number of samples. However, the results (in the proportional regime) do not include: (1) The number of samples in each task or (2) the distance between the two tasks. The only quantity that features in the equations is the noise level. \n\nI also believe the presentation could be better. For example, some text explaining theorem 1 (in english) or explaining what $\\theta$ and and $t$ represent in theorem 2 could be helpful to a reader. I also wonder why the authors chose to call in model-based transfer. I have not heard of this specific term before and it would help if the authors cited previous references to model-based transfer learning. Isn't fine-tuning a more appropriate term. \n\nFinally, the looming question is the connection to deep networks. While perhaps out of the scope of this paper, there are questions about how this affects or relates to the practice of deep learning. Are linear models in the proportional regime informative for how we should do Transfer learning in practice?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their comments and suggestions to help us improve the quality of our work. Below we address the questions and other points raised in the review one by one. \n\n**My main concern is that the setting is not conducive to studying transfer learning. Transfer learning is a fundamentally small-data phenemenon, i.e., the target dataset usually contains a limited number of samples. However, the results (in the proportional regime) do not include: (1) The number of samples in each task or (2) the distance between the two tasks. The only quantity that features in the equations is the noise level.**\n\nWe apologize for any possible lack of clarity in the exposition. We look at the problem in the following way: instead of explicitly defining the source distribution, and the number of samples from it, we capture the effect of training on the source distribution through the pre-trained solution $w_0$. We use $w_0$ as the initialization point when fine tuning on the target distribution. Then, for example, in the context of regression [Theorem 2, eq.(7)], the distance between the tasks (i.e., the source and target distributions) is essentially reflected by $e_a$, which is defined as the generalization error of the source-trained model, $w_0$, on the target distribution. The number of samples from target distribution is included in our analysis and is reflected by the quantity $\\kappa = \\frac{d}{n}$, where $d$ is the number of parameters and $n$ is the number of samples. We will do our best to introduce these clarifications in the final version of the paper.  \n\n**I also believe the presentation could be better. For example, some text explaining theorem 1 (in english) or explaining what \n $\\theta$ and $t$ and represent in theorem 2 could be helpful to a reader. I also wonder why the authors chose to call in model-based transfer. I have not heard of this specific term before and it would help if the authors cited previous references to model-based transfer learning. Isn't fine-tuning a more appropriate term.**\n\nTheorem 1 says that in a certain technical sense we can examine different properties of the weights trained on data matrix $A$ satisfying Definition 2 by relating them to the properties of the weights trained on its matching Gaussian matrix $G$ (see Definition 3). We will add an expanded version of this explanation into the final version and would like to thank the reviewer for making this point.  Please refer to the answer to the question 3 below for a discussion about $\\theta$ and $t$ from Theorem 2. \nWe learned of the terms \"instance-based transfer learning\" and \"network-based transfer learning\" from the review paper by C. Tan et al. \"A survey on deep transfer learning\". We then preferred to use \"model-based\" instead of \"network-based\" as we introduced these terms only to explain that there are two main approach to transfer learning, one of which (instance-based) mixes the target and the source distributions together and the other keeps the distributions untouched and transfers the *model* from the source to the target. This being said, we agree that calling it fine-tuning could have been a better choice and we will take it into account for the final version.  \n\n**Finally, the looming question is the connection to deep networks. While perhaps out of the scope of this paper, there are questions about how this affects or relates to the practice of deep learning. Are linear models in the proportional regime informative for how we should do Transfer learning in practice?**\n\nAs far as we understand, sometimes in practice one pre-trains a deep model and then fine-tunes only the last layer on the target distribution (see, e.g., \"Last-Layer Fairness Fine-tuning is Simple and Effective for Neural Networks\" by\nMao, Yuzhen et al.), essentially making the model linear for our purposes. This is the most straightforward potential application of our results to the real world models. Another way to extend our results to deep models could be linearizing them using the Neural Tangent Kernel approach. We leave both of these directions for future work as pursuing them requires careful verification of several technical steps. \n\n**1. Why is renormalization needed in in the classification problem setting?**\n\nWe find such a renormalization meaningful because, in the classification setting, the outputs of the model depend only on the direction of the vector of weights but not on its magnitude. More explicitly, $w_0$ and $cw_0$ for $c \\ne 0$ have the same performance making them equally good solutions. However, initializing at $w_0$ and $cw_0$ yields different solutions after training on source distributions. Putting all these remarks together, we would like to ensure that the output of the fine-tuning step depends only on the directions of $w_0$, which is exactly what the renormalization step does. \n\n**2. In definition 2, the authors claim that the assumptions are satisfied in practice. Could the authors expand on line 156-160 and explain the results of Seddik et al.?**\n\nThe Lipschitz Concentration Property (LCP) defined on line 156 says that for any Lipschitz $\\phi: \\mathbb{R}^d \\to \\mathbb{R}$ the tails of $\\phi(x)$ decay very fast, where $x \\in \\mathbb{R}^d$ comes from the data distribution. Seddik et al. show that any distribution generated from a GAN with weight matrices of bounded norm satisfies LCP. This follows from the well-known facts that Gaussian random vectors satisfy LCP and applying a Lipschitz function to a distribution satisfying LCP yields a distribution that also satisfies LCP. \n\n**3. How do I interpret quantities like $t$ and $\\theta$ in theorem 2?**\n\n It does not seem to be possible to explain what $\\theta$ and $t$ are in plain English, but these are certain scalars determined solely by the covariance matrix $R_x$ of the data. For example, if  $R_x = r_0I_d$,  then the expressions simplify to $t = ({\\frac{d-n}{d}})^2$ and $\\theta = \\frac{2\\sqrt{n}}{r_0 (d-n)}$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9ijhQC9hpd", "reviewer": "Reviewer_LHAw", "summary": "The paper studies model-based transfer learning. In this setting, a model is pre-trained on the source data, and the learner aims to fine-tune it on the target data by running SGD initialized at the pre-trained model. The paper focuses on linear regression and classification, aiming to generalize the assumption of Gaussianity to general distributions and investigate the scenarios where fine-tuning on the target data can or cannot be beneficial.", "questions": "It appears that there are some parameters in the paper that have not been defined.\n\nIn line 194, \"p\" is used without definition.\n\nIn equation (7), \\kappa is referenced without definition.\n\nIn line 206, it's unclear what \"p(r)\" represents.", "limitations": "The paper does not have any potential negative societal impact.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper derives a universality result that allows replacing Gaussian data with more general distributions. It then analyzes the generalization error in linear regression and classification for SGD initialized at a model pre-trained on the source data. The study shows that when the noise in the data is high, fine-tuning can be harmful, and just using the model pre-trained on the source data results in a lower error. Conversely, when the noise is less than the error of the model pre-trained on the source data, transfer learning improves test performance.", "weaknesses": "The paper attempts to generalize the assumption of Gaussianity but is limited to the linear model, which is inherently restrictive. Furthermore, it focuses exclusively on a specific algorithm—SGD initialized at the model pre-trained on the source data—without demonstrating the optimality of these results or determining whether better results are achievable with alternative algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their comments and suggestions to help us improve the quality of our work. Below we address the questions and other points raised in the review one by one. \n\n**The paper attempts to generalize the assumption of Gaussianity but is limited to the linear model, which is inherently restrictive. Furthermore, it focuses exclusively on a specific algorithm—SGD initialized at the model pre-trained on the source data—without demonstrating the optimality of these results or determining whether better results are achievable with alternative algorithms.**\n\nFor extending the current approach to deep architectures, one could linearize the network using the Neural Tangent Kernel approach and carefully verify all necessary technical details. We leave this as a direction for future work. We do not prove universality only for the SGD but rather for a certain class of  *objectives* (described in the statement of Theorem 1) that could potentially be optimized using other optimization methods and would still exhibit universality. Our results apply to the objective coming from the implicit regularization property of the SGD but they extend far beyond that, and also even this objective could potentially be solved by other methods. Finally, studying optimality of SGD for transfer learning goes beyond the scope of this work. We only claim to analyze rigorously a popular approach to transfer learning.\n\n**In line 194, \"p\" is used without definition.**\n\nLine $194$ was meant to say that the empirical spectral densities $\\hat{p}_N$ converge to some limit, that we will denote by $p$. That is, $p$ is the limiting spectral density.  We are sorry for the confusion it arose and will make it more clear in the final version. \n\n**In equation (7), $\\kappa$ is referenced without definition.**\n\n$\\kappa$ is defined in the beginning of  line $104$ as the ratio of the number of parameters and the number of data points in the target distribution. This being said, we understand that it's a good practice to remind the reader of the notation within the theorem itself and will do so in the final version of the paper.  We will clarify this in the final manuscript.  \n\n**In line 206, it's unclear what \"p(r)\" represents.**\n\nThis is the same limiting spectral density $p$ as in line $194$ written as a function of its argument $r$.", "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": "3nlhs931Gk", "reviewer": "Reviewer_KpbC", "summary": "The paper investigates the application of transfer learning within the framework of linear models. The authors focus on a model-based approach, where a model pre-trained on a source distribution is fine-tuned on a few samples from a target distribution. Authors extend the concept of universality, traditionally used in random matrix theory and high-dimensional statistics, to the context of transfer learning. They demonstrate that certain properties of linear models trained on large datasets can be transferred to new tasks with minimal data. They also provide a thorough theoretical analysis, establishing conditions under which the transfer learning approach achieves performance close to that of a model trained directly on the target task with abundant data.", "questions": "1. Can you provide more details on the boundary conditions under which the universality principle might fail? Are there specific cases or distributions where this principle does not hold?\n2. Can you elaborate on the choice of datasets and tasks used for empirical validation? Are there plans to test the proposed method on more diverse and complex datasets?", "limitations": "While the authors provide thorough theoretical proofs and some experimental validation, the paper lacks comparative experiments with existing methods. This makes it difficult to fully evaluate the practical advantages and limitations of the proposed approach.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "Universality has traditionally been applied in random matrix theory and high-dimensional statistics, but not in the context of transfer learning. The authors show properties of linear models trained on large datasets can effectively transfer to new tasks with limited data. The authors explore the conditions under which their transfer learning approach is effective. Combination of theoretical analysis and empirical validation provides a comprehensive exploration of this concept.", "weaknesses": "1. The empirical validation, while convincing, is somewhat limited in scope. The experiments are conducted on a few specific tasks and datasets, which may not fully capture the diversity of real-world applications. Datasets with different characteristics, such as varying levels of noise, feature distributions, and dimensionalities, could provide a more comprehensive assessment of the proposed methods. \n2. The comparison with existing transfer learning methods is limited. The paper could benefit from a more comprehensive comparison to highlight the advantages and limitations of the proposed approach relative to current state-of-the-art methods.\n3. The paper provides certain properties of linear models trained on large datasets can be transferred to new tasks with minimal data, but in real applications, is there any indication, when transfer methods are useful?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their comments and suggestions to help us improve the quality of our work. Below we address the questions and other points raised in the review one by one. \n\n**1. The empirical validation, while convincing, is somewhat limited in scope. The experiments are conducted on a few specific tasks and datasets, which may not fully capture the diversity of real-world applications. Datasets with different characteristics, such as varying levels of noise, feature distributions, and dimensionalities, could provide a more comprehensive assessment of the proposed methods.**\n\nWe varied levels of noise, feature distributions and dimensionalities in the synthetic examples presented in the paper. This being said, in the final manuscript, we will extend our experiments to some real-world datasets, showcasing that universality holds for them, too, and would like to thank the reviewer for making this point.\n\n**2. The comparison with existing transfer learning methods is limited. The paper could benefit from a more comprehensive comparison to highlight the advantages and limitations of the proposed approach relative to current state-of-the-art methods.**\n\nWe do not claim to propose a novel transfer learning method, but, rather, to analyze theoretically a popular approach to transfer learning. We apologize for any confusion and will clarify this in the final version of the manuscript.\n\n**3. The paper provides certain properties of linear models trained on large datasets can be transferred to new tasks with minimal data, but in real applications, is there any indication, when transfer methods are useful?**\n\nTo make our analyses applicable to the more real life scenarios, we would need to extend them to the deep models. We believe it should be possible to do by linearizing the networks via the Neural tangent Kernels approach but it requires verifying certain technical properties and is left as a subject for future work. \n\n**1. Can you provide more details on the boundary conditions under which the universality principle might fail? Are there specific cases or distributions where this principle does not hold?**\n\nWe provide an example from Han, Q. and Shen, Y. (2023). ``Universality of regularized regression estimators in high dimensions\", *The Annals of Statistics*. Take $x$ to be of the form $qg$, where $q$ is a Bernoulli random variable (1 with probability $p$ and 0 with probability $1-p$) and $g \\sim \\mathcal{N}(0, \\frac{I_d}{d})$, them Han and Shen show that Gaussian universality does not hold for the ridge regression objective. In terms of our assumptions, this distribution violates the variance property from Definition 2.5.    \n\n**2. Can you elaborate on the choice of datasets and tasks used for empirical validation? Are there plans to test the proposed method on more diverse and complex datasets?**\n\nWe would be happy to extend our experiments to the real-world datasets, comparing the test errors for models learned from these datasets and from the Gaussian mixtures with matching means and covariances. We will include the results in the final version of the paper and we appreciate the reviewer's suggestion.", "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": "I9d99atQ3A", "reviewer": "Reviewer_hU8n", "summary": "The paper derives a new universality result, which can be leveraged to solve a mirror descent optimization problem for a large family of data distributions by relating the solution to a Gaussian distribution with matching first and second-order statistics. This result is then applied to analyze transfer learning for linear models in the setting of regression and binary classification.", "questions": "In assumption 2.2, why should the covariance depend on the mean $\\mu$?\n\nIn assumption 2.3 and 3, how can the condition hold for any matrix of bounded operator norm? It seems possible to construct a matrix for which the condition does not hold.", "limitations": "Limitations are adequately addressed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper derives a new universality result by adapting an existing method. The universality is used to extend results about transfer learning in linear regression models to a larger class of data distributions, and further results are developed in the setting of binary classification. The paper is overall well-written and easy to follow.", "weaknesses": "Parts of Assumptions 2 and 3 seem unintuitive to me, see the questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their comments and suggestions to help us improve the quality of our work. Below we address the questions and other points raised in the review one by one. \n\n**In assumption 2.2, why should the covariance depend on the mean $\\mu$**\n\nWe apologize for the confusion. Assumption 2.2 contains a typo that we will make sure to fix in the final version. It should indeed be $\\mathcal{N}(a^T\\mu, a^T\\Sigma a)$. We would also like to remark that this typo was contained only in assumption 2.2 and did not affect our proofs and calculations. \n\n**In assumption 2.3 and 3, how can the condition hold for any matrix of bounded operator norm? It seems possible to construct a matrix for which the condition does not hold.**\n\nWe will illustrate this property in the case when $\\eta \\sim \\mathcal{N}(0, \\frac{I_d}{d})$ so that asymptotically $\\lVert \\eta \\rVert \\rightarrow 1$. One can then first replace $C$ with $\\frac{C + C^T}{2}$ making it symmetric and then diagonalize the latter, meaning we can replace $C$ by $diag(\\lambda_1, \\dots, \\lambda_d)$ where all $|\\lambda_i|$ are bounded by a constant $K>0$. Then $\\eta^TC\\eta$ has mean $\\frac{\\lambda_1 + \\dots + \\lambda_d}{d} = \\frac{Tr(C)}{d}$ and variance $\\frac{2(\\lambda_1^2 + \\dots + \\lambda_d^2)}{d^2} \\le \\frac{2K^2}{d}$. The latter implies that the variance goes to zero,  and therefore the difference $\\eta^TC\\eta - \\frac{Tr(C)}{d}$ is close to zero with high probability. As it might be a bit counter intuitive, let us consider the case of low rank $C$ in more detail , for example $C= e_1e_1^T$, where $e_1$ is the first basis vector. Then $\\eta^TC\\eta$ is a $\\chi^2$ random variable but it still converges to $0$ because of its normalization. Note that $\\frac{Tr(C)}{d} = \\frac{1}{d}$ also goes to $0$ and thus both quantities $\\eta^TC\\eta$ and $\\frac{Tr(C)}{d}$ go to zero as $d \\to \\infty$.", "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:

Meta-review: This paper studies transfer learning in the sense of finetuning an overparametrized linear model with initial weight w_0 on a target distribution P. 

Authors state a universality result as the dimensionality goes to infinity for functions of the optimal weight under assumptions on the randomness of the design matrix of input data matrix. This result uses the Lindeberg approach to show convergence of the optimal weight of a matching Gaussian to the design matrix. 

Authors uses this result to quantify the generalization error in regression and classification. 

In the regression case, they give a lower bound on the generalization error and show that depending on the noise level it may be harmful to finetune the linear model. Similar analysis is derived for classification, with similar conclusions. 

Overall this is a good paper nevertheless , it is not very pedagogic in explaining their assumption nor in explaining Theorem 1 after stating it, or stating clearly in theorem the limit is taken on the dimension. Please incorporate all the feedback from reviewers to clarify assumptions, and to back passing to limits with rigorous arguments.
Decision: Accept (poster)