Double Descent and Overfitting under Noisy Inputs and Distribution Shift for Linear Denoisers
Authors: Chinmaya Kausik
Kashvi Srivastava
Rishi Sonthalia
Venue: Accepted by TMLR ()

Abstract: Despite the importance of denoising in modern machine learning and ample empirical work on supervised denoising, its theoretical understanding is still relatively scarce. One concern about studying supervised denoising is that one might not always have noiseless training data from the test distribution. It is more reasonable to have access to noiseless training data from a different dataset than the test dataset. Motivated by this, we study supervised denoising and noisy-input regression under distribution shift. We add three considerations to increase the applicability of our theoretical insights to real-life data and modern machine learning. First, while most past theoretical work assumes that the data covariance matrix is full-rank and well-conditioned, empirical studies have shown that real-life data is approximately low-rank. Thus, we assume that our data matrices are low-rank. Second, we drop independence assumptions on our data. Third, the rise in computational power and dimensionality of data have made it important to study non-classical regimes of learning. Thus, we work in the non-classical proportional regime, where data dimension $d$ and number of samples $N$ grow as $d/N =  c + o(1)$. 

For this setting, we derive \rishi{data-dependent, instance specific} expressions for the test error for both denoising and noisy-input regression, and study when overfitting the noise is benign, tempered or catastrophic. We show that the test error exhibits double descent under general distribution shift, providing insights for data augmentation and the role of noise as an implicit regularizer. We also perform experiments using real-life data, where we match the theoretical predictions with under 1\% MSE error for low-rank data.

Published in Transactions on Machine Learning Research (03/2024)
Double Descent and Overfitting under Noisy Inputs and Distribution Shift for Linear Denoisers
Chinmaya Kausik
ckausik.Bumich.com edu
Deportment of Mothematics University of Michigan, Ann Arbor
Kashvi Srivastava
fashwiCCumicck edu
Department of Mathemalics
University of Michigan, Ann Arbor
Rishi Sonthalia
rsonthal@matth ucla edu
Department of Mathematics
University of Colifornia, Los Angeles (UCLA)
Reviewed on OpenReview: // oppnreevee.. net/ forum? id- Haf TIL.IF
Abstract
Despite the importance of denoising in modern machine learning and ample empirical work supervised denoising, its theoretical understanding is still relatively scarce. One concern about studying supervised denoising is that might not always have noiseless training data from the test distribution. It is more reasonable to have access to noiscless training data from a different dataset than the test dataset. Motivated by this, we study supervised denoising and noisy-input regression under distribution shift. We add three considerations to increase the applicability of our theoretical insights to real-life data and modern machine learning. First, while most past theoretical work assumes that the data covariance matrix full-rank and well-conditioned, empirical studies have shown that real-life data is approximately low- rank. Thus, assume that our data matricos low-rank. Second, drop independence assumptions on our data. Third, the rise in computational power and dimensionality of data. have made it important to study non-classical regimes of learning. Thus, we work in the non-classical proportional regime, where data dimension d and number of samples grow as d/N = c o(1)
For this setting, we derive data-dependent, instance specific expressions for the test error for both denoising and noisy-input regression, and study when overfitting the noise benign, tempered or catastrophic. We show that the test error exhibits double descent under general distribution shift, providing insights for data augmentation and the role of noise implicit regularizer. We also perform experiments using real-life data, where match the theoretical predictions with under 1% MSE error for low-rank data.
1 Introduction
Denoising and noisy-input problems have rich history in machine learning and signal processing (Vincent et al. 2010a Tian et al. 2020 Elad et al. 2023). Aside from its natural application to noisy input data, the idea. of noise regularizer has led to denoising being tied to many arcas of modern machine lcarning, such as pretraining and feature extraction (Krizhevsky et al. 2012), data-augmentation for representation learning Chen et al. 22220). and generative modeling (Rombach et al. 2022 While unsupervised methods like PCA F.R.S. 1901) and low rank matrix recovery (Davenport Romberg 2016) have been addressed prior theoretical work (Baldi & Hormik 1989), supervised methods like denoising autoencoders are theoretically less well-understood.

---

Published in Transactions on Machine Learning Research (03/2024)
One of the biggest practical qualms to studying supervised setting is that learner needs access to noiseless data sampled from the test distribution. This is resolved by considering distribution shift, which is when the training and test data can come from different distributions. As a toy example, one might have access to noiscless dog pictures containing mostly German shepherds and collies, but would want to denoise noisy dog pictures containing mostly pomeranians and poodles. As long as the training data "spans" the structured subset of features containing dog pictures, meaningful learning is possible. The same argument can be made for regression with noisy inputs, say for predicting click-rates for these pictures. Given this practical motivation, we study supervised denoising and noisy-input regression under distribution shift.
It is well understood that non-trivial denoising is made possible by the presence of additional structure in the data (see, for example, section 3.2 of Vincent et al. (2010a)). One of the most natural such structures is low rank, specifically the idea that the true inputs live in low dimensional space. In fact, past work (Udel Townsend] 2019) has demonstrated that a lot of real-life data approrimately low-rank: that is, covariance matrix only has a few significant eigenvalues.
In this paper we look at the following error in variables regression task Hirshberg 2021 Let Xtrn E RaXN be a noiseless data matrix of N samples in d dimensional space. Let B E gdxk be target multivariate linear regressor, and let Yrrn = 3 Xtrn. Note that when 3 = I, our target is the noiseless data Xern itself. Let Arm E RddxN be a d x noise matrix. For this paper, we assume that we have access to Ytrn and Xtrn + Atrn while training. The goal is to study the test error of the minimum norm linear function Wopt that minimizes the MSE braining error. The MSE training error is a natural choice it is one of the most common targets for non-linear denoising autoencoders (Vincent et al. 2010a). We formalize the definition of Wopt below.
[|W1 W arg min |Yern W(Xern + A1r
Wope arg min
W
W
Given test data Xest E R and Yret = Xtatt we formally define the test error for arbitrary linear functions W by X(st) below. Since we are not assuming anything about the distribution of the training test. data, we only take the expectation over the training and test noise. The error is dependent the specific Xtrn and Xast that are given.
|| Yea - W(X + Asst )1?
RWW, R(W, = E Aera
(1)
Nest
The classical theory of learning problems would keep the data dimension d fixed and lets the number of samples N grow to oo. These can be theoretically analysed using elementary tools. However, with growing access to computational power and richness of data, it has become important study non-classical regimes. One important and popular example is the proportional regime, where d x N and so d is comparable to N. Phenomena like double-descent and benign overfitting discovered in noiseless-inpe -nnuuss---tututte settings demonstrate the surprising ad advantages of this kind of high dimensionality. There has been a lot of recent work on whether overfitting output noise is beneficial or harmful in these regimes (aallnnrr et al. 2022).
Testing on real data is a challenging issue. As argued above and in Cheng Montanari 2022 a big reason for this issue is that past work assumes that the data covariance matrix well-conditioned, while low-rank assumptions better model real-life data covariance matrices. In real life, one has little control over the independence or even the distribution of the data (Kirchler et al.
2023 ). There is also growing need to be
robust to adversarially chosen data in machine learning (Kotyan 2023 Some recent work has dropped IID Specifically, Nakakita
assumptions by looking at time scries data Naaaakita & Imaizumi (2022), shows benign overfitting when the given dala æi,..., Tn come from a lime dependent stochastic process. However, in many cases, we have dependent data, without the data forming a time series. We would thus like drop the assumption that the data is IID or even independent without assuming a particular dependence structure. However, to account for this, we would need to have data-dependent theoretical results. We thus aim to address the following question:
2022
PaakkaiallyyNNaaaittaa & Imaizumi
2

---

Published in Transactions on Machine Learning Research (03/2024)
Q.1. Can we derive test error expressions for linear denoising and regression with noisy inputs that:
(a) work with data from a low-dimensional subspace under a non-classical regime,
(b) make minimal assumptions on the training data, test data and how they are related,
(c) match experiments that use real-life data distributions?
Q.2. What insights can obtain from these?
Contributions.
The major contributions of the paper are as follows.
Q.1 (a) (Low-Rank Data, Proportional Regime) We work with low-rank data instead of needing full-rank data. This better models the approximate low-rank structure empirically seen in real-life data. Q.1 (b) (Dropping Independence Assumptions, Arbitrary Test Data) We do not assume that the training data is IID even independent, and we work with arbitrary test data from our low- dimensional subspace. Specifically, we obtain theoretical expressions that depend on the singular values of the given instantiation of the training and Lest data as well as the alignment between their left singular vectors.
Q.1 (c) (Experiments using Real-Life Like Data) We have a relative crror of under 1% in experiments using real-life like data, establishing that our theoretical results can be used with data similar real data
Q.2 (i) (Double Descent and Overfitting Under Distribution Shift) We show theoretically and empirically that our test error curves exhibit double descent, even for general distribution shifts. We relate this to the role of noise as an implicit regularizer. Further, we generalize ideas about overfitting to our setting and examine what conditions lead to benign, tempered, or catastrophic overfitting. Q.2 (ii) (Data Augmentation) We examine when data augmentation improves in-distribution and out-of- distribution generalization, giving theoretical results and practical insights.
Paper Structure. Section 2 provides details and theoretical assumptions for the model we analyze. Section discusscs our main theoretical results for the denoising problem as well as experiments verifying these $ discusses insights obtained from these results for double descent, data augmentation, and overfitting paradigms.
results. Sention
Denoising. Significant work has also been done to understand the role of noise as a regularizer and its impact generalization (Bishop 1995 Camuto al. 2020 Hu et al. 2020 Neelakantan et al 2015 Sonthalia & Nadakuditi 2023). Other related works include the use of noise to learn features (Chen et al.
2020;
Vincent et al. 2010b Poole et al. 2014 Srivastava et al. 2014). to improve robustness (Ben- Tal et al.
) 2009 Rakin et al. 2019 Bertsimas et al. 2011). ; to prevent adversarial attacks (Chakraborty et al.. 2021]
and the connection to training dynamics Pretorius et al.) 2018). There has also been work to understand
Bayes optimal denoiser using matrix factorization (Nadakuditi 2014 Lelarge & MMollnne 2017 Lesicur et al,, 2017 Maillard et al., 22022 Troiani et al. 2022). Finally, there has been some preliminary recent work on the learning dynamics of supervised denoising (Cui et al.) 2021 Pretorius et al. 2018). In this paper, continue
the study of understanding supervised denoising from the lens of test error.
Theoretical Work on Generalization in Con-Classical Regimes. There has been significant work in understanding the generalization error and benign overfitting. Most prior work looks the case where x D, for some data distribution D and we have y 3 x + where & (N, The following least squares problem is commonly considered
Bopt arg min 8
||31|2 3 arg min mig |Yim Etrn + 8 X X
The above setting was analyzed in Dobriban & Wager (0018): ; Mel & Ganguli (2021): Muthukunar al.
2001 Bartlett et al. (2020); Belkin et al. (2020); Derezinski et al. (0200) ; Hastie et al. (0022); Loureiro et al.
2021b). The version for kernelized regression was studied in Mei et al. (022 Mei & Montanari (2021]
Mei et al. (0018): Tripuraneni et al. (2021a): Gerace et al. (2020) Woodworth et al. 2020
Loureiro et al.
20) Ghorbani el al. [2019 2020).
TTe code for the experiments can he found the following anonymized repository
Link
3

---

Published in Transactions on Machine Learning Research (03/2024)
We note that our setup is similar to prior work. However, the major difference is the placement of the noise. That is, we have error in our independent variables z while prior work assumes error in the dependent variables y. While standard error in variables (Hirshberg 2021 assumes error in both, we simplify to only assume error in x.
The above prior work assumes full dimensional data. Generalization for low dimensional data is partially addressed by work on Principal Component Regression (Huang et al. 2022 Xu & Hsu, 2019), although they do not test real data. These works use PCA-based low-rank approximation of the data and provide theoretical results in terms of the effective rank or eigenvalue decay of the data covariance matrix. In this paper, we continue the study of linear models and their test ervors in mon-classical regimes. However, we do so in the context of denoising and low rank data.
Testing on Real-Life Data. Some past theoretical work in the digh-dimensional regime tests on real data Paquette et al.] (2022); Lourciro et al. (2021b a): Wei et al. (2022). Lourciro et al. (2021b) assumes that the data distribution is given by Gaussian mixture model. Loureiro et al.] (2021a) uses a Gaussian equivalence principle to argue that their teacher-student model can capture realistic data assumptions. Finally, Wei et al. (2022) show that their appropriately rescaled training error asymptotically converges to the true risk under some assumptions. Cheng & Montanari (2022) also study a more general model of ill-conditioned covariances. All of the results require that the training data is I.I.D. and that the test data is from the same distribution as the training data. Further, they do not do this in the denoising setup considered in this paper. However, in contrast to us, they provide data-independent theoretical results.
1: Recht, ct al. 2 Miller et al. 22200g McCoy et al. (2020) have noticed that there is strong lincar correlation
OOD Generalization and Distribution Shift. Empirically, studies such as Miller et al.
(022
between in-distribution accuracy and out-of-distribution accuracy. There has been some theoretical work
Tripuraneni et al.) 2021a bl Mania & Sra. 2020 Wu & Xu. 2020 Darestani et al. 2021 LeJeune et al.)
2022) that has looked into this phenomenon. In other examples, Ben-David et al. (2006) approaches this
from a domain adaptation perspective and computes bounds dependent on an abstract notion of distribution
distance; [ei et al. (2021) provides analysis for the minimax risk; and Lampinen & Ganguli (2019) studies the generalization when training models with gradient descent. In this paper, we continue theoretically understanding distribution shift. We do so in the novel setting of denoising. While past results usually only depend some measure of distance between the two distributions. We provide instance-specific results that depend on the data.
Double Descent and Implicit Regularization. The gencralization curves in our paper display double descent (Opper & Kinzel 1996 Belkin et al. 2019). which is believed to occur due to implicit. bias due to some form of regularization. There has been significant thcoretical work on understanding implicit biases (Jacot et al., 2020 Shamir 2022. Neyshabur 2017) and gradient descent (Soudry et al. 2018 Ji & Telgarsky) 2019 Du et al.] 2019a bb. However, there is little work on double descent under distribution shift or for noisy inputs, which we establish in this work in relation to implicit regularization due to input noise.
1.1 Limitations
While we provide new results, our work still has limitations. As with most prior work in the area, our work is limited to linear models. Extensions to shallow non-linear models for very different data assumptions have been considered Cui & Zdeborová (2023). However, extensions to deep networks with realistic data assumptions are still quite challenging. One possible way to exlend to non-linear models is to study kernel methods. The kernel most closely associated with deep neural networks is the Neural Tangent Kernel (NTK). It has been shown that the feature vectors obtained from the NTK kernel are approximately low rank.
While we make progress loward more realistic data assumptions, another limitation is that the theory needs exactly low rank data. This is not quite true for real data, which is only approzimately low rank or lives in some non-lincar low dimensional space. Approximately low-rank data is difficult to deal with due to the ill-conditioning of the covariance matrix. Recent work such as Cheng & Montanari (022); Wang et al. 2024 have started studying ill-conditioned covariance matrices.
4

---

Published in Transactions on Machine Learning Research (03/2024)
Another limitation is our theoretical result for the over- wer-pparamterized regime has non-trivial error only if one assumes that t| |/ of (Nerra). That is, the norm of the data points must. decay as Ntrn grows. This is not concern for many prior works (Hastie et al. 2022 Bartlett et al. 2020 Cheng & Montanari 2022 However, we study the problem in a different sctup.
2 Problem Setup and Notation
Recall the problem setup, Let Xtrn E RdxN N be a noiseless data matrix of N samples in d dimensional space. Let B E BRdo be a target multivariate linear regressor, and let Yrr = 3 Xtrn- Note that when / 1, our target is the noiseless data Xtyn itself. Let Atr E Rd be d N noise matrix. For this paper, we assume that we have access to Yrr and Xtrn + Atm while training. We then solve the following problem.
|| W E arg arg |Yen - W(Xern + A Waps = arg min
W
W
Given test data Xsst E RexN and Yest = Xeat, we have the following test error.
Yest W(Xest + Aest)
= Aesr
Nist
We would like to study the test error R(W Xtst) of Wopt in terms of propertics of the data matricos Xtrn and Xtst as well as the noise dist ributions. All prior work besides Sonthalia & Nadakuditi (2023): Cui & Zdeborová (2023); Pretorius et al. (2018) only considers models where we have access to noisy outputs Y and noiscless inputs X, while consider the case where we have noisy inputs X. For simplicity, we assume access noiseless outputs Y. It is easy see from elementary linear algebra that Wopt Yorn(Xero + Atm)*. Notice that when 3 = T, we are studying the linear denoising problem, and when 3 E Rd, we are studying real-valued regression with noisy imputs. We work in the proportional regime, where d/N = c c o(1) as N grows, for some constant с > O. Notice that we are not in the limit N > oc; we will in fact bound the deviation from our estimates by o(1/N) as N grows. We now detail our assumptions on data and noise.
Assumptions about the data. The assumptions below formalize three natural requirements on the data (1) that it lies in a low-dimensional subspace as argued above; (2) that the norm of the training data does not grow too much faster than the norm of the training noise, otherwise there will not be enough noise to train on; (3) that the training data "sees enough" of the subspace containing the data.
Assumption 1. We have d-dimensional data Xtrn E R and Xest E Rdx so that
Low-rank: There is a fized r > 0 so that Xten and Xest have data-points lying in an r-dimensional subspace V Rdd and the column span of Xtrn V.
2. Data growth: (| O(N).
3. Low-rank coll-conditioninn:: For the r singulor values a; of Xtrn, o. O(1) and + a. o(1) as N grows, for any i.j.
Notice that we don't assume that Xtm is IID or even independent, and Xiæt is completely arbitrary, besides lying in the subspace V. In our results, we will characterize the dependence of the error on Xtea and Xist using their singular values. These intuitively measure "how much each direction is sampled," and don't depend on the distribution of the data, Finally, let Xtrn = UEtra ViT. be the SVD Xtrn with U E Rdxr, Etrn E Rrxx and Vir E R Note that the columns of U span V. Then there exists matrix L such that X(s UL. For Theorem
2 we will relax our assumption on X say that there exists L and a > 0
that 1xstt UL|| <
Comparison with assumptions in prior work. Most prior works on thcoretical regression assume that the data comes from a Gaussian or Gaussian-like distribution. Specifically, TTripuraneni el al. (2021a); Dobriban & Wager (2018) ; Mel & Ganguli (2021) Belkin et al. (2020); Mei & Montanari (2021) ; Huang et al.
(2022); Xu & Hsu (2019) Tripuraneni et al. (2021b) assume that NNO, Σ). Most real data cannot be
modeled as Gaussian data. Another common assumption that E1/2z where the coordinates of 2 are independent, centered, and have variance of 1. This setting is a little bit more general than the previous
5

---

Published in Transactions on Machine Learning Research (03/2024)
setting. The independence of data is still limiting assumption that prevents it from modeling real-life data well. In addition, as the dimension increases, due to the (Tyapunov's) central limit theorem, the data's 's higher moments tend towards those of a Gaussian distribution again. This makes this assumption nearly as limiting as the first onc. Papers with this (or very similar) assumption include Wu & Xu (2020); Bartlett et al. (2020);
Hastie el al. (2022): ; Cheng Montanari (2022). These papers have many important and seminal results and
provide the foundation for our study.
We provide results on test error in very different low-rank sctting inspired by real-life data, and drop many restrictive assumptions. A small number of papers (Huang et al.) 2022 Xu & Hsu 2019 Sonthalia & Nadakuditi 2023) that do assume a low-rank structure. However, the first two further assume that the data is low-rank Gaussian, while the third only provides results for one-dimensional data.
Assumptions about the training noise. We recall the definition of the Marchenko-Pase Pastur distribution with shape c, for completeness.
Definition Let c (0, so) be a shape paramter. Then the Marchenko- PaashenkkoPastur distribution with shape e. is the measure Pe supported on [c,, where c+ = =1 + v0)² is such that
21 u0 +u e>1
He
1
c cs1
where has density dv(x) 1
2aze V(4 - 2x
Our assumptions on noise are fairly natural and general. Informally, require the training noise to (1) have finite second moments, (2) be uncorrelated across entries, (3) be isotropic, and (4) follow natural limit theorem. On the other hand, the test noise only needs (1) finite second moments and (2) uncorrelated entries. Our assumptions include a broad class of noise distributions (see Proposition of (Sonthalia & Nadakuditi 2023)) ). One the many examples of noise distributions satisfying these is Gaussian noise, with each coordinate having variance 1/d. Formally, we assume the following.
Assumption 2. Let the train and test noise matrices Atr, Aest E RdxNN be sampled from distributions Dtrn and Dest such that Atrn salisfies points 4 below and Atst salisfies points 1,2.
1. For all i, Ep[An]] =0, and [D[A]]] = /d/d. Here == ((1) N grows.
2. For all (11,11} } + j22. Eo(A Aisjal = Epl ED(Ai, ED [D[[Agja]-
3. D is a rolationally bi-invariant distribution and A ~ D is full rank with probability one.
4. Suppose Ad.N is a sequence of matrices such that with d/N = c + o(1) as N grows, for c >> O. Let be the eigenvolues of (At.N)T AdN Let pa,N = E, 8,4. be the sum of dirac delta measures for the eigenvalues. Then we shall assume that pa,N converges weakly in probability to the Marchenko- Pastur measure with shape e as N grows.
x .
Nd.N
Assumption 2.4 may seem odd, but the Marchenko Pastur is the natural universal limiting distribution for many classes of random matrices.
Comparison with assumptions in prior work. There are three papers in denoising to compare to, namely (Sonthalia & Nadakuditi (2023); Cui & Zdeborová (2023) Pretorius et al. (2018). Our assumptions on noise are strictly more general than the first two. However, the model for Cui et al. (202T) more general than ours. [Pretorius al. (2018) has the same assumptions as ours, except that they do not require rotational invariance of noise. In contrast to our general closed form results, they analyse learning dynamics for denoising by choosing specific orthogonal initialization for the coupled ODE that they derive.
Terminology. We introduce some terminology that we will use throughout the paper.
Definition 2. We call linear model overparametrized if d > N and underparametrized if d < N. In-subspace distribulions refer to lest data distribulions whose support is in V, while out-of-subspace distributions are test data distributions whose support is not contained in V.
PAA distribution over matrices C Rmx= rotationally bi-invariant if for all orthogonal U1 mm and all orthogonal U2 R=X", Un AU2 has the same distribution A. Another way to phrase rotational bi-invariance if the SVD of A is given by A U...V. then UA and VA are uniformly random orthogonal matrices and independent of F.A and each other.
6

---

Published in Transactions on Machine Learning Research (03/2024)
A curve ezhibits double descent if it has local mazimum a peak. By test error we mean R(W opt: Xtst); and by generalization error we mean Ex,,, (R(Wop. opt, Xest)), assuming that Xist is sampled (possibly dependently) from some distribution.
We now define the overfitting paradigms that we will study. Motivated by past work on benign overfitting, we present reasonable generalization of overfitting paradigms (benign, tempered and catastrophic, see Maalinar
et al. (2022) to our setting. Consider the minimum norm denoiser that minimizes expected MSE training error, similar in spirit to 0* in Bartlett et al. 2222
W = arg min W
| 1 W E arg min E,... [| - W(X + Atr))l?)
W
Recall that we obtain Wopt by instead minimizing the MSE error for a single noise instance Atra which means that Wopt overfits Arr in the overparametrized regime. We would like to see this overfitting is benign, tempered or catastrophic for test error. Following the definition of overfitting paradigms in Mallinar let al. (2022), we want to take N + co. Since we are in the proportional regime, we must let d maintaining the relation d/N c + o(1). For studying overfitting, natural goal would be to study how R(W Xtst) behaves as d, N + co. This is analogous to the excess risk studied in overfitting for noiscless imputs [Bartlett et al. 2020). However, we will see that both errors in our difference individually (end lo zero as d, N + 00, making this a somewhat meaningless criterion. As noted in Shamir 2022), benign overfitting is traditionally restricted to scenarios where the minimum possible error is non-zcro. natural generalization to consider then to instead study the limit of relative excess error
as well,
the excess error ([Woott
R(Wopi opt, Xtst) R(W", Xese) R(W*, Xtst)
as N + do with = Definition 3. We say that overfilting is benign when this limit is 0, tempered when it is finile and positive, and catastrophic when it is co.
2.1 Models Captured
In this section, we explore various scenarios captured by our assumptions, demonstrating the wide applicability of our theoretical results.
Denoising Low Dimensional Data The simplest setting is when X lives in some low dimensional subspace V. Let B I. Then, this models the least squares supervised denoising problem.
Error in Variables Regression Suppose 3 E Rdd Recall that Yuon = 3d Xten- In this case, the standard linear regression problem to find 3 that minimizes [| - 38 Xirn 1.p. For crror variables regression, we have noise on the independent variable Xten- Hence, we would be solving the following problem.
Yern 3T (Xtrn + Aer
This situation satisfies our assumptions. Note that the situation extends to multivariate regressions, i.e., when B E dRdc for k > 1.
Remark 1. While this is not the full variables regression, our proof techniques can also cover cases with errors in Yemn-
Gaussian Mixture Models Classification Our assumptions also capture classification problems for Gaussian mixtures. Specifically, let MI...., ue be the k mean vectors. Let us also assume that the mean vectors are pairwise orthogonal. Let 2f be the ith data point and assume that z belongs to the jth cluster. Then we know that z¹ - My ~ /0, I).
Thus, we can see that we can write our data as Z = X + A, where A is a Gaussian random matrix, X is a low rank matrix whose columns live in (4... Hence, our data can be modeled at low rank (rank k) plus Gaussian noise. We also need to see that Y can be modeled as 8T X for some ,3. Let the label for the jth cluster be k-dimensional vector with a one in the jth coordinate and let B = [p1... pk], we get that Y ==8 8T X. Hence, we model specific classification problems.
7

---

Published in Transactions on Machine Learning Research (03/2024)
Remark 2. The training and test metrics differ from typical classification settings, utilizing MSE instead of cross-enbropy and accuracy, respeclinely. However, the two are related in many instances. See Mulhukwmart et al. 2021) for more in-depth theoretical study of the two loss functions.
Spiked Covariance Models Another common model is the spiked covariance model. This model assumes that the covariance matrix for data has (much smaller than and d) large eigenvalues, and the rest of the eigenvalues are of smaller order (Ke al., (023). Tf we consider data values of are much bigger than the singular values of Z, then we see that
+ A, where the singular
B|zz"| = E[(X () A) EXXX" + AA7
Hence, see that Z has spiked covariance structure. In this case, can think of the principal K eigenspace as providing the relevant signal and the rest being noise. Hence, if our regression targets only
depend on the principal K eigenvectors (i.e. Y = = =) then our model captures this scenario. Spiked covariance models have been studied in prior theoretical works on generalization (Liang et al. 2020 Ba et al,
2023
3 Theoretical Results
This section presents our main result Theorem 1 We present the results here and discuss insights section All proofs are in Appendix C
Theorem 1 (In-Subspace Test Error). Let (d- NJ. Let the SVD of Xtrn be Usen Vir let L U Xests
By = U B, and d/N. Under setup and Assumptions and the test error (Equation is given by the following. If < (under-pante pinnterpprammterizee regime)
R.W
oot, opt, UL) = Vtrn
11 1hr 1)
Nist
nhat c²
Tr
(Bu E2rn +
_1) Mirn
(E) (Emmc Nem! ))² + N
d c-c
If e >>> (over-parumelerizedd regime)
R(W opt, UL)
Mern
110 11 (E? + !)mm!)-
Nist
Thst
E 1|2
+ d c-1 Tr(BupT (1 + Thrn 2 +0
N2
N
Proof Sketch: The proof can be broken into multiple steps. First, the generalization error can be decomposed as follows [Sonthalia & Nadakuditi 2023).
That
R(W, = V - W Weeeell 2
Nest
d
Bias
Variance
Second, we solve for W Wopt- From classical theory we know that W Wapt Yern (Nern + Atrn)!. Using Wei and some careful linear algebraic observations, we expand these to get
2001
-P- (P - HH "H ZPP
<> c << 1
W opt -UEtrn " A + UDrr H1 1" 12 (QQ")-111.
The exact expression for the variables in the expansion can be found in Appendix
Third, we substitute this back into our expressions for the bias and variance and expand the norms in terms of trace. Then, we group quadratic terms together. Specifically, we shall see that for 1, the error is decomposed in the sums and products of the following terms HHT pT P. and Z.

---

Published in Transactions on Machine Learning Research (03/2024)
Finally, we estimate these terms using random matrix theory. We compute both their expectations and variances and show that the terms concentrate to values that only depend on the spectrum of Atrn- Then, using assumption 2.4, we approximate the spectrum of Atrn using the Marchenko Pastur distribution. Then, since the terms concentrate, we can approximate the expectation of the product with the product of the expectation.
Comments on Expression. The asymmetry between e <> 1 and < comes from the asymmetry in the expressions for Wopt and the need for renormalizing things in the case when c > 1. We further note that, in general, the expression does not depend
the right singular vectors of Xtra as Xtrn only appears as its gram matrix X Xtm trn Finally, L is the coordinates of Xest in the basis given by U. Then suppose Xist = UtstEnat Vist. Then we see that I. = Uss EestVist Vist. Then, using the unitary invariance of the norm, we have that
BE triec + mo__rrn1 1 11 (Eom +
Uest Uest
Hence, the error depends on alignment term Uest and the singular values Eist- Let also examine the scale of the terms in the test error expressions. In Theorem 1 the bias is the norm term, and the variance is the trace term. Consider the setting where Die grows as fast as possible and is ((N). This is also what happens when Xten is low-rank Gaussian (Huang et al., 2022). Then, the bias term is O(1/N?,, while the variance term is O(1/d) = O(1NN). The estimation error is (1/N)) in the underparametrized case, so the only significant term, in this case; the variance term. In the overparametrized case, the only significant. terms are the variance term and the O(]Eeral|' 0()EernlP/N²²) deviation from the estimate. If [| 11 = o(N) instead of (NV), then the variance term is the only significant term again. Specific instantiations of Theorem | can be found in Appendix A and Appendix B It. is important to note that while the result may seem involved at. first, we do in fact use it to develop insights in Section
Theorem is significant for various reasons. First, it can be considered the noisy-input counterpart to Dobriban & Wager )2018): Hastie et al. (2022), which works with noisy outputs instead. Second, it one of the few results that do not require high dimensional well-conditioned covariance (Cheng Montanari 2022).
Third, it generalizes [Sothhaia & Nadakuditi (2023) to higher rank settings. Further, Theorem | estirmates the test error in terms of the test instance instead of the generalization error. The latter is the expectation of the test error over a distribution of test instances. This is significant since it allows us to work with arbitrary test data in V. provide results for distribution shift, and provide insights for data augmentation.
and Out-of-Subspace Generalization. Theorem I can be used to understand OOD and out-of-subspace test error. For the former, Corollary [ below bounds the change in generalization error in terms of in-subspace distribution shift.
Out-of-Distributte
Corollary 1 (Distribution Shift Bound). Consider linear denoiser W trained on training data Xtro U'nrn Via. Let it be tested on test data Xest1 = U L1 and X1 = U2 generated possibly dependently from distributions supported in the span of U with mean Ups and covariance Eu,- = UE,UT respectively. Then, the difference in generalization errors G = Ex.,, RR(Wopts X1st,)] is bounded for c < 1 by
01 (3) GG2 G1 (o, ffc() + min 12 |E -E-Ei En + Hapl MIHTlle +o
where f(c)= = for c <1 1 and f(c) otherwise. We add O(IEtra 1l N23) when e 2 1.
Corollary 1 is interesting as it implics that out-of-distribution error is primarily governed by the different between the means and covariances of the two distributions. Since these are relatively constant (population means and covariance changes slightly based on the data), this implies that in practice the error curves versus c are very similar. So far, we have considered in-subspace distributional shifts. However, the distributional shift can take the test data out of the low-dimensional subspace V.
Theorem 2 (Out-of-Subspace Shift Bound). If we have the same training data and solution opp assumptions as in Theorem 1 Then, for any Xist for which there exists an L and an O such that |x UT. S a, and Acst that satisfies 1,2 from Assumption 2. we have that the generalization ervor R(W opt, Xest) satisfies
IR(Wopt opt, Xest) R(W opt, UL) S a (Wop + 1)2
9

---

Published in Transactions on Machine Learning Research (03/2024)
Theorem 2 shows the surprising result that even if our test data is not in the subspace, we exhibit double descent. This is also verified experimentally in the next section.
Transfer Learning. So far, we have considered the case where we have a covariate shift. That is, we have distribution shift for X. However, we still assumed that the targets were given by the same function of X. That is, B did not change. We now consider the scenario where 3 can change to Best- Concretely, we are in the scenario where we train model with Xtrn Atrr and Ytrn 3 Xtrn and test the model with data Xest + Aest and Y Bist In this case, we have the following theorem.
Theorem 3 (Transfer Learning). Let r < ld N Let the SVD of Xtra be UEtra trm By = U 3, BtætU = U Best, and e == d/N. Under our selup and Assumplions and 2 the test error
VT let == Xest,
(Equation ! is given by the following. If c < 1 (under-pon podder-prumeterized regime)
1
1
E AAran Aeat
Yest W Wopt (Xest + Asst) 1/:
- -()) B
Nest
Nist
27st Tr(3 (2 + Mirn!) LL (Best.U BB))
Nist
Mest c²
Tr B1,3t222
2trn + -
(2 + mbm!!)
d 1-c
Virn
Mtrn || C+ 1 1 + N
Nest
cf (over-parramtterized regime)
E AseriAssa
(ess
W Wope + Arst)l??
= (Brsttu- - -B)
Nest
Nist
21hat
T + Thrn I)- LI" (Bro,B - -Bu))
Niet
Whst
| 112
Tr(Br Wern D )) +0 +
+ d c-1
N2
+ Tern
| +
+o
1
Nist
N
Proof. Note that.
1 Neet
1 Neoe
Eurrn:Aut
|Yst
Wopt (Xest + Aest) 12: Avern
Yest
Xest + Xist Wope + Ated)l?
Then, expand the norm twice to get the above result.
Here it is easy to see that since 3, Bret are constant and X = || terms in both expressions are Oe(1) as a function of Hence, we see that as a function of e, this error also has double descent.
O(Nea),, we see that the first two
Overfitting Paradigms. We now compute the test error from W in Theorem from which we compute the limit of the relative excess error in Corollary 2 when data does not grow too slowly.
Theorem 4 (Test Error for W*). In the same setling as Theorem 1 we have that W UT and
of (T+ Meen 2
mer N2
E + Thrm -1
nhst Tr +
Mhmn N I )
-2
R(W* UL)
37
I L
I+
Na
d
d
d
Corollary 2 (Relative Excess Error). Let | = ((N1/++)). As d + oo with d/N + e, the relative ercess error tends to C in the underporametrized regime. In the overparametrized regime, when || 11 o(N), il lends to -
1 and to - + k for some constant k when || 11 O(N).
10

---

Published in Transactions on Machine Learning Research (03/2024)
r 25
f= 25
r 25
Generalization Error
50
Generalization Error
50
Generalization Error
(= 100
100
r= 100
20
10
0.5
1.0
1.5
2.0
2.5
3.0
3.5
0.5
1.0
1.5
2.0
2.5
3.0
3.5
0.5
1.0
1.5
2.0
2.5
3.0
3.5
1/c
N/d
1/C
N/d
1/C
N/d
(a) CIFAR Dataset
(b) STL10 Dataset
(c) SVHN Dataset
Figure 1: Figures showing the test error for Linear Regression vs 1/c- N/d. Training data from the CIFAR dataset is projected onto its first principal components for r= 25, 50, 100, 150. 2500 test data points from CIFAR, STL10, and SVHN datasets are projected onto the same low-dimensional subspace. For empirical data points, shown by markers, we report the mean test error over at least. 200 trials.
Experimental Verification To experimentally verify our test error predictions using real-life data with distribution shift, we train linear function W CIFAR (Krizhevsky) 2009) and test on CIFAR, STL10 (Coates et al. 2011), and SVHN (Netzer et al. 2011p. We emphasize that we run all experiments in the covariate shift case. That is, all models are trained on CIFAR, but then test posted different datasets. For computing test error, we simply compute Wopt and plot the empirical average of Ne., [X over 200 trials. We run three main kinds of experiments. (a) First, we enforce the low-rank assumption isolate the effect of distribution shift. To do this, we use principal component regression or PCR (Xu & Hsu 2019 Huang et al. 2022). In PCR, instead of working with the true (and approcimately low-rank) training data matrices Xtst, find the best low-rank approximation Xern of the training data by projecting it to embedded subspace of the highest principal components. When testing, we project the test datasets to the same subspace to enforce the low-rank assumption before computing the empirical test error. (b) Second, to explicitly control the amount of deviation a from the low-rank assumption, we perturb the low-rank testing data from setting (a) and test using Xist := X,st + Kist, where K,st is Gaussian noise with covariance designed control a. (c) In the third case, we do not try to artificially enforce the low-rank assumption, relying the approximate low-rank nature of real-life data. To do this, we report the test error for the matrices Xtst themselves. Since d is fixed, vary by varying N. Figure 2 shows that the theoretical curves and the empirical results align perfectly for experimental setup (a) and that we have tight bounds for experimental setup (b). Numerically, we find that the relative error between the generalization error estimate and the average empirical error in experimental sctup (a) is under 1% on average. For setup (c), since real-life data is only approzimalely low rank, we see a non-negligible error. However, the predictions still align well with the empirical results. This shows that our low-rank assumption is meaningful, and aligns well with the bchaviour of real-life data.
(Xeer Wor Ars)
Single-variable Regression Theorem is for any B E Rdxk Above, we presented figures for when 3 = Ta- Here, we present a similar figure for the single variable regression case. That is when & E Rdx1, Figure shows the results. As before, we train all models on CIFAR and then test on CIFAR, SVHN, and STL10 with the same target B. As we can see the theory closely matches the empirical results.
Classification We verify our thcoretical predictions the case of classification via two experiments. For the first experiment, we have two datasets. First, we have two Gaussian clusters with means =y and have labels +1. Second, we have three clusters with mutually orthogonal means and labels e1, e3. For this model, we train the model using mean squared error and then plot the test mean squared error and the test classification accuracy. Figure shows that our theoretical prediction of the MSE exactly aligns with the empirical observations. Further, we see that the double descent in the MSE results in double descent in the classification error.
Since we are also interested in showing these phenomena also occur during transfer learning, we conduct the following experiment. We again have three mean vectors pl, 22, Mg that mutually orthogonal. We also
11

---

Published in Transactions on Machine Learning Research (03/2024)
104
104
150
126
10"
Test Error
101
Test Error
107
Test
10
10
10-1
10-1
10-2
10-2
3.0
0.5
1.5
2.0
2.5
3.0
3.5
0.5
1.0
1.5
2.0
2.5
3.0
3.5
1/c
N/d
1/c
N/d
1/c
N/d
(a) In-subspace test
10a
100
10f
25
50
Test Error
Test Error
10-1
10-1
20-1
0.5
1.0
1.5
2.0
2.5
3.5
1.0
1.5
2.0
3.0
3.5
1/c
N/d
1/c
N/d
1/c
=
N/d
(b) For the out-of-subapace curves, we add full-dimensional Gaussian noise such that a = 0.1. The upper and lower bounds for the empirical markers are given by Theorem
Thecretical Rezult
Thecretical Result
Theoretical
Empirical Resalt
Empirical
Empirica Result
Test Error
Test Error
Test Error
10Pt
10%
10a
1.0
1.5
2.0
2.5
2.0
2.5
3.0
3.5
0.5
1.0
2.5
3.0
3.5
1/c
N/d
1/c N/d
1/c
N/d
(c) Test error estimated without projecting data, relying on the approximate low-rank structure of real-life data.
Figures showing the test error for 3 = I vs 1/c= N/d. In (a) and (b), training data from the CIFAR dataset is projected onto its first r principal components for 25, 50, 100, 150. 2500 test data points from CIFAR (Green, Left col.), STL10 (Blue, Middle col.), and SVHN (Red, Right col.) datasets are projected onto the same low-dimensional subspace. (a) is in-subspace test error and (b) is out-of-subspace test error. (c), we don't project the test data and report the standard test error, relying on the approximate low-rank structure data instoad of imposing it. For empirical data points, shown by markers, we report the mean lest error over at least, 200 trials. Similar results obtained for single-variable regression with Rdd.
Figure 2:
have that the target for μı is the vector e,, Then, during the test time, assume that the means vectors for the three clusters have moved to Ptst1 Ptst2, Pest3 and we interested in mapping Ptst,i to Hence, we have both covariale shifts, and the larget function has changed. Thus, we are predicting the error for transfer learning with covariates shift. Figure shows that Theorem D exactlly predicts the error. Again, we see double descent the test mean squared error. However, this case, this double descent doesn't 't always translate to double descent in the classification accuracy (for the new classes). Two different shifts, with different trends, can be in Figure
12

---

Published in Transactions on Machine Learning Research (03/2024)
1.0
Non Squed Eret
0.55
0.54
6.6-
0.5
0.90
0.09
0.25 3.0 0.5 1,60 125
3.50
1.75 2,00
0.25 0.50 035
125
1.50
1.55
2/0
0.03 925 0.50 0.75
1.50
1.25 1.50
1.75 2.50
6.00 0.59 1.5 1.75
1-9
1-5
(a) 2 Cluster MSE
(b) Cluster Accuracy
(c) 3 Cluster MSE
(d) 3 Cluster Accuracy
Figure 3: MSE and Accuracy when we only have covariate shift and Best = B.
1.0
Mean Sqaured Error
0.36
0.525
0.6-
0.34
0.500
Accuracy
0.32
0.4
0.450
0.28
0.400
0.375
0.00 0.25 0.50 0.75 1.00 1.25 1.50
1.75 2.00
0.26
x-
0.00
0.25 0.50 0.75
1.00
1.25 1.50 1.75 2.00
0.00
1.50 1.75 2.00 0.25
0.30 0.75
1.00
125
1-8
(a) MSE for classification for three Gaussian clusters with covariates shift (b) Accuracy for first covariate shift (c) Accuracy for second covariate shift and transfer learning
Figure 4: Experiment when we have both covariate shift and a shift in the target function.
4 Insights For Noisy-Input Problems
Double Descent under Distribution Shift Notice that all our curves plotting test error against 1/c have a similar shape they rise when e approaches from either side, and there is a peak at c c= 1. This matches our theoretical results and establishes that denoising test error curves exhibit double descent, even for arbitrary test data in V. To understand why this is happening, consider the denoising target, given by the MSE error below.
E Yrr WXT + Atra) I| WX + 2Trrrrrrn W WXtrn) T Aerr)) I 11.
Notice that minimizing this sum forces us to reduce both || - WXera l| and |[W]],, due to the third term (the "variance" term). We see that the noise is regularizing ||||e through the variance term Tr(WTW Arr)))ra) This is the implicit regularization of W due noise. However, the strength of regularization due to the noise instance Atrn not the same across different values of c. When close to 1, the distribution of the spectrum of Atr (the Marchenko- Pastur distribution) has support very close to zero. On the other hand, for e far from 1, the non-zero cigenvalues of AT are all bounded away from zero. This establishes that the effect of regularization weakens most near c= leadinn to spike in the test error coming from the large norm of the learnt Wopt- This explanation is similar in spirit to the explanations for double descent in Xu & Hsu 2019) and others, but crucially adapts to implicit regularization due to noise.
Amount of Training noise It was highlighted in Sonthalia Nadakuditi] (2023) that optimally picking the training noise level does not mitigate the double-descent phenomena observed in the generalization error for linear model. In this section, support this claim using our result from Theorem [ Figure 5 shows the double descent curve of Men and Figure 0 shows the generalization error when using the optimal amount
Thhe eigenvalues that exactly do contribute weakening of the regularization. This is because the minimum-norm optimizer W' for expected MSE error, and more zcro cigenvalues increases flexibility, creating larger set of optimizers minimize the over. This helps decrease components of W by spreading them into dimensions. This is identical in spirit arguments about variance overparametrizet regimes in section 1.1 Hastie al. (2022)
choosing
13

---

Published in Transactions on Machine Learning Research (03/2024)
Optmalnn
Optimaa 0
Optioaal 0
201
Optirnal
-21
0.25 035
0.75
105
125
1.0
1/5
025
930
0.5
3.50
125
230 0.15
1.60
1.0
2.5
923 830
1.00 C-
125
1,57
1.5
cmg
cm
(a) Training Data with New Noise
(b) CIFAR Dataset
(c) STL10 Dataset
(d) SVHN Dataset
Figure 5: Optimal Ten that minimizes the test error given in Theorem
versus d/Nern-
19
Test Emor
Textt Enror
Test
20-1
3.00
030
0.3
175
1.0 cm
(a) Training Data with New
(b) CIFAR Dataset
(c) STL10 Dataset
(d) SVHN Dataset
Noise
Figure 6: Test Error using Theorem versus 1/c with optimal Tern-
of training noise, As in other works such as Sonthalia & Nadakuditi 2023 Yilmaz & Heckel (022 we see double descent in the regularization strength.
Data Augmentation to Reduce Test Error. In contrast with Nakkiran et al. (2020), but similar to Sonthalia & Nadakuditi (2023), optimally picking the noise parameter will not remove the peak in the test error. Instead, we use data augmentation and increase N to try to move away from the peak, studying Theorem [ to understand how this will aflect lest error. We take two approaches to data augmentation that individually exploit the absence of the IID assumptions. Since the data does not have to be independent, we can take the same training data and add fresh noise to increase N. Alternatively, since the data does not have to be sampled from specific distribution, we can combine two different datasets into larger training dataset to increase N. The subtlety to account for is that while increasing N this way decreases c, it also increases Eten- However, recall from the insights the scale of terms above that the variance term is commonly the dominant one, and note that the variance term is roughly constant as Eurn growe When < 1, applying data augmentation increases N, thus decreasing further away from the peak at 1 and decreasing test error. When e > 1, applying data augmentation increases N, decreasing e towards the peak at and increasing test error. Of course, the latter phenomenon could mitigated by adding other regularizers or by further augmenting the data. Figures 7d and Yh empirically verify the validity of Theorem [ for the training data obtained from data augmentation. We also see that increasing the number of in- in-distribution training data points reduces the
test error.
Overfitting Paradigms. Recall from Corollary 2 that the relative excess error is given by I for the underparameterized regime. This means that we approach benign overfitting as c becomes arbitrarily small (which is essentially the classical regime). On the other hand, for the overparameterized case, we have that the relative excess error is given by I-c when || 2| o(N). Then as becomes arbitrarily large we again approach benign overfitting. This is interesting as this the case when the norm of the signal grows slower than the norm of the noise. Hence we see benign overfilling when the signal-to-noise ratio goes to zero. If had ||Err|]' O(N), then results suggest that the relative excess error may increase by constant, leading to no benign overfitting. However, we believe that this is an artifact of the proof technique.
4The bias decreases stays constant with Fayn, but the bias irrelevant common scales of Farn-
14

---

Published in Transactions on Machine Learning Research (03/2024)
50
50
100
100
100
Test Error
10'
150
Test Error
10f
150
Test Error
10'
150
10-1
10-1
10-4
10-2.
10-2
10:2
0.25
0.50
0.55
1.00
1.25
1.50
175
2.00
0.25
0.50
0.75
1.00
1.25
1.75
2.00
0.25
0.50
0.55
1.00
1.25
1.50
1
2.00
1/c = Nid
1/C =
N/d
1/C = N/d
(a) CTFAR Dataset
(b) STL.10 Dataset.
(c) SVHN Dataset.
(d) Data augmentation exploiting non-independence. For different Ner the training data is formed by repeating the
same 1000 images from the CIFAR dataset.
10a
10a
10c
r= 25
== 25
r= 25
Generalization Emor
Generalization Erro
Generalization Eror
r- 100
r= 100
r- 100
20-3
10-1
10-1
10-2
10-2
10-2
0.5
1.0
1.5
2.0
2.5
3.0
3.5
0.5
1.0
1.5
2.0
2.5
3.0
3.5
0.5
1.0
1.5
2.0
2.5
3.0
3.5
1/c
N/d
1/c
N/d
1/c
N/d
(u) CIFAR Datasel
(I) STL10 Dalaset
(H) SVHN Dalaset
(h) Data augmentation exploiting non-identicality the distribution. The training data is formed by mixing CIFAR train split with STL10 train split dataset.
Figure 7: Data augmentation exploiting non-independence. For different Now the training data is formed by repeating the same 1000 images from the CIFAR dataset.
Notice we don't observe benign overfitting except in the limit of arbitrarily large or arbitrarily small c. We make sense of this phenomenon using the following argument. Recall that while W is the minimmm-norm matrix minimizing the MSE error for single noise instance, W is the minimum-norm matrix minimizing its expectation over noise. We can use this observation to view W as Wopt over an augmented datasct. Taking the expectation over noise in the training (arget is in spirit like augmenting the data with "infinitely many" copies itself, each with fresh noise. So, W' can be viewed as the outcome training Wopt over an augmented dataset with a "changed c," where e replaced with a vanishingly small value while keeping Etm /N Eirne/ constant.
5 Conclusion and Future Work
We studied the problem of denoising cov-dimensional input data perturbed with high-dimensionall noise. Under very general assumptions, provided estimated test error in terms of the specific instantiations of the training data and test data. This result is significant, there is scarce prior work in the area of generalization for noisy inpuls as well as generalization for low-rank data. Further, we lested our results with real data and achieved a relative MSE of 1%. Finally, the instance-specific estimate lets us provide many insights that would be harder get with results on generalization error, such as showing double descent for arbitrary test data in our dow-dimensi subspace, theoretically understanding data augmentation, and provably demonstrating well explaining the lack of benign overfitting.
15

---

Published in Transactions on Machine Learning Research (03/2024)
References
Jimmy Ba, Murat A Erdogdu, Taiji Suzuki, Zhichao Wang, and Denny Wu. Learning in the presence of now-dimensional structure: A spiked random matrix perspective. In Conference on Parsimony and Learning (Recent Spollight Track), 2023. URL httts::/opperrevies net/forumn?d==00Bjxxr333
Z. Bai, Baiqi. Miao, and Jian-Feng. Yao. Convergence Rates of Spectral Distributions of Large Sample Covariance Matrices. STAM Journal on Matriz Analysis and Applications, 2003.
Pierre Baldi and Kurt Hornik. Neural networks and principal component analysis: Learning from examples without local minima. Neural Networks, 2:53 58, 1989. URL http:///ppp..mmmnnccccccco..... org/ Corpus ID: 14333248
Peter Bartlett, Philip M. Long, Gabor Lugosi, and Alexander Tsigler. Benign Overfitting in Linear Regression. Proceedings of the National Academy of Sciences, 2020.
Mikhail Belkin, Daniel J. Hsu, Siyuan Ma, and Soumik Mandal. Reconciling Modern Machine- Learning Practice and the Classical Bias Variance Trade-off. Proceedings of the National Acodemy of Sciences, 2019.
Mikhail Belkin, Daniel J. Hsu, and Ji Xu. Two Models of Double Descent for Weak Features. SIAM Journal on Mathematics of Data Science, 2020.
Shai Ben-David, John Blitzer, Koby Crammer, and Fernando Pereira. Analysis of Representations for Domain Adaptation. In Advonces in Neural Information Processing Systems, 2006.
Aharon. Ben-Tal, Laurent E. Ghaoui, and Arkadi Nemirovski. Robust Optimization. Princcton Series in Applied Mathernatics. Princeton University Press, 2009. ISBN 9781400831053
Dimitris Bertsimas, David Brown, and Constatine Caramanis. Theory and Applications of Robust Optimiza- tion. STAM Rev., 53:464-501, 2011.
Chris M. Bishop. Training with Noise is Equivalent Tikhonov Regularization. Nearal Compulation, 1995.
George W. Bohrnstedt and Arthur S. Goldberger. On the exact covariance of products of random variables. Journal of the American Statistical Association, 64(3288:1439-1444 1442, 1969. ISSN 01621459. URL http:
//www. jstor wtttto.orrttttteeeeeeeeeeeeoooee httg//ttable2228660
Alexander Camuto, Matthew Willetts, Umut Simsekli, Stephen J Roberts, and Chris C Holmes. Explicit Regularisation in Gaussian Noise Injections. In Advances in Neural Information Processing Systems, 2020.
Anirban Chakraborty, Manaar Alam, Vishal Dey, Anupam Chatlopadlyay, and Debdeep Mukhopadhyay. A Survey on Adversarial Attacks and Defences. CAAI Transactions on Intelligence Technology, 6(1):25 45, 2021. doi: https:://oo..org// 11///10001111/i11 1049/citt. 12028.88....
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A Simple Framework for Contrastive Learning of Visual Representations. In Proceedings of the 37th International Conference on Machine Learning, Proceedings of Machine Learning Research, pp. 1597-1607 PMLR, 2020.
Chen Cheng and Andrea Montanari. Dimension Free Ridge Regression. arXiv preprint arXio:2210.08571 2022.
Adam Coates, A. Ng, and Honglak Lee. An Analysis of Single-Layer Networks in Unsupervised Feature Learning. In Proceedings of the 14th International Conference on Artificial Intelligence and Statistics, 2011.
Hugo Cui and Lenka Zdeborová. High-dimensional asymptotics of denoising autoencoders. arXie preprint 3rXih:2305.11044 2023.
Hugo Cui, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime. In Advances in Neural Information Processing Systems, 2021.
16

---

Published in Transactions on Machine Learning Research (03/2024)
Mohammad Zalbagi Darestani, Akshay S. Chaudhari, and Reinhard Heckel. Measuring Robustness in Deep Learning Based Compressive Sensing. In Proceedings of the 38th International Conference on Machine Learning, 2021.
Mark A. Davenport and Justin K. Romberg. An overview of low-rank matrix recovery from incomplete observations. CoRR, abs/1601.06422,, 2016. URL
Michal Derezinski, Feynman T Liang, and Michael W Mahonoy. Exact Exprcssions for Double Descent and Implicit Regularization Via Surrogate Random Design. In Advunces in Neurul Information Processing Systems, 2020.
Edgar Dobriban and Stefan Wager. High-dimensional asymptotics of prediction: Ridge regression and classification. The Annals of Statistics, 2018.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient Descent Finds Global Minima of Deep Neural Networks. In Proceedings of the 36th International Conference Machine Learning, 2019a.
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient Descent Provably Optimizes Over- parameterized Neural Networks. In International Conference on Learning Represenlations, 2019b.
Michael Elad, Bahjat Kawar, and Gregory Vaksman. Image denoising: The deep learning revolution and beyond- survey paper. STAM Journal on Imaging Sciences, 16(3):1594-15) 1654, 2023. doi: 10.1137/
23M1545859. URL https://ddo /ttt::://oo.orr/1...o 11//1.00.13/72334455555
Karl Pearson F F.R.S. Liii. on lines and planes of closest fit systems of points in space. Philosophical Magazine Series 1, 2:559-572 572, 1901. URL httpes//aap..ssmatticccoooa www.llaarrrr//ooppuuie arg./orrpusD::155877785
Federica Gerace, Bruno Loureiro, Florent Krzakala, Marc Mezard, and Lenka Zdeborova. Generalisation Error in Learning with Random Features and the Hidden Manifold Model. In Proceedings of the 37th International Conference on Machine Learning, 2020.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Limitations of Lazy Training of Two-layers Neural Network. In Advances in Neural Information Processing Systems, 2019.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. When Do Neural Networks Outperform Kernel Mothods? In Advances in Neural Information Processing Systems, 2020.
Friedrich Götze and A. Tikhomirov. On the Rate of Convergence to the Marchenko-Pastter Distribution.
arXiv: Probability, 2011.
Friedrich Götze and Alexander Tikhomirov. Rate of Convergence to the Semi-Cireular Law. Probability Theory and Related Fields, 2003.
Friedrich Götze and Alexander Tikhomirov. Rate of Convergence in Probability to the Marchenko-Paae Law. Bernoulli, 2004.
Friedrich Götze and Alexander Tikhomirov. The Rate of Convergence for Spectra of GUE and LUE Matrix Ensembles. Central European Journal of Mathematics, 2005.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J. Tibshirani. Surprises in High-Dimensional Ridgeless Least Squares Interpolation. The Annals of Statistics, 2022.
David Hirshberg. Least squares with error in variables. arXie preprint orXiv:210,.0899. 2021.
Wei Hu, Zhiyuan Li, and Dingli Yu. Simple and Effective Regularization Methods for Training Noisily Labeled Data with Generalization Guarantee. In International Conference on Learning Representations, 2020.
Ningyuan Huang, David W. Hogg, and Soledad Villar. Dimensionality Reduction, Regularization, and Generalization in Overparameteriized Regressions. STAM Journal on Mathematics of Dala Science, 2022.
17

---

Published in Transactions on Machine Learning Research (03/2024)
Arthur Jacot, Berfin Simsek, Francesco Spadaro, Clement Hongler, and Franck Gabriel. Implicit Regularization of Random Feature Models. In Proceedings of the 37th International Conference on Machine Learning, 2020.
Ziwei and Matus Telgarsky. The Implicit Bias of Gradient Descent on Nonseparable Data. Proceedings of the 32nd Conference Learning Theory, 2019.
Zheng Tracy Ke, Yucong Ma, and Xihong Lin. Estimation of the number of spiked eigenvalues in a covariance matrix by bulk eigenvalue matching analysis. Journal of the American Slatistical Associalion, 118(541): 374-392, 2023.
Matthias Kirchler, Christoph Lippert, and Marius Kloft. Training normalizing flows from dependent data. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 17105-1712) PMLR, 23-29 29 Jul 2023. URL https: httpp://procceedings mml.eiiinnns.mi.....mmmmm.r wwtps/ss.w...r...122a11
html
Shashank Kotyan. A reading survey on adversarial machine learning: Adversarial attacks and their under- standing, 2023.
Alex Krizhevsky. Learning Multiple Layers of Features from Tiny Images. 2009.
Alex Krizhevsky, llya Sutskever, and Geoffrey E. Hinton. Imagenet Classification with Deep Convolutional Neural Networks. Communications of the ACM, 2012.
Andrew K. Lampinen and Surya Ganguli. An Analytic Theory of Generalization Dynamics and Transfer Learning in Deep Linear Networks. In International Conference on Learning Representations, 2019.
Qi Lei, Wei Hu, and Jason Lee. Near-Optimal Linear Regression under Distribution Shift. In Proceedings of the 38th International Conference Machine Learning, 2021.
Daniel LeJeune, Jiayu Liu, and Reinhard Heckel. Monotonic Risk Relationships under Distribution Shifts for Regularized Risk Minimization. arXiv preprint arXiw:2210.11588, 2022.
Mare Lelarge and Léo Miolane. Fundamental Limits of Symmetric Low-Rank Matrix Estimation. In Proceedings of the 29th Conference on Learning Theory, 2017.
Thibault Lesieur, Florent Krzakala, and Lenka Zdeborová. Constrained Low-Rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications. Journal of Statistical Mechanics: Theory and Experiment, 2017.
Tengyuan Liang, A. Rakhlin, and Xiyu Zhai. On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels. In Proceedings of the 33rd Conference On Learning Theory, 2020.
Bruno Loureiro, C'edric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Marc M'ezard, and Lenka Zdeborov'a. Learning Curves of Generic Features Maps for Realistic Datasets with Teacher-Student Model. In Advances in Neural Information Processing Systems, 2021a.
Bruno Loureiro, Gabriele Sicuro, Cedric Gerbelot, Alessandro Pacco, Florent Krzakala, and Lenka Zdeborova.
Learning Gaussian Mixtures with Generalized Lincar Models: Precise Asymptotics High-dimensions. Advances in Neural Information Processing Systems, 2021b.
Antoine Maillard, Florent Krzakala, Marc Mézard, and Lenka Zdeborová. Perturbative Construction of Mean-Field Equations in Extensive-Rank Matrix Factorization and Denoising. Journal of Statistical Mechanics: Theory and Experiment, 2022.
Neil Mallinar, James B. Simon, Amirhesam Abodsoltan, Parthe Pandit, Mikhail Belkin, and Prectum Nakkiran. Benign, tempered, or catastrophic: A taxonomy of overfitting, 2022. URL sttps://arxiv.org abs/ aba/2207.0m 06569
18

---

Published in Transactions on Machine Learning Research (03/2024)
Horia Mania and Suvrit Sra. Why Do Classifier Accuracies Show Linear Trends Under Distribution Shift? arXiv preprint Xrx:::01 15483, 2020.
Vladimir Marcenko and Leonid Pastur. Distribution of Eigenvalues for Some Sets of Random Matrices. Mathematics of The Ussr-sbornak, 1967.
R. Thomas McCoy, Junghyun Min, and Tal Linzen. BERTs of a feather do not generalize together: Large variability in generalization across models with similar test set performance. In Proceedings of the Third BlackbozNLP Workshop on Analyzing and Interpreting Neural Networks for NLP, 2020.
Song Mei and Andrea Montanari. The Generalization Error of Random Features Regression: Preciso Asymptotics and the Double Descent. Curve. Communicalions on Pure and Applied Mathemalics, 2021.
Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A Mean Field View of the Landscape of Two-layer Neural Networks. Proceedings of the National Academy of Sciences of the Uniled States of America, 2018.
Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Generalization Error of Random Feature and Kernel Methods: Hypercontractivity and Kernel Matrix Concentration. Applied and Computational Hormonic Analysis, 2022.
Gabriel Mel and Surya Ganguli. A Theory of High Dimensional Regression with Arbitrary Correlations Between Input Features and Target Functions: Sample Complexity, Multiple Descent Curves and a Hierarchy of Phase Transitions. In Proceedings of the 38th International Conference on Machine Learning, 2021.
John Miller, Karl Krauth, Benjamin Recht, and Ludwig Schmidt. The Effect of Natural Distribution Shift on Question Answering Models. In Proceedings of the 37th International Conference on Machine Learning, 2020.
John P Miller, Rohan Taori, Aditi Raghunathan, Shiori Sagawa, Pang Wei Koh, Vaishaal Shankar, Percy Liang, Yair Carmon, and Ludwig Schmidt. Accuracy on the Line: on the Strong Correlation Between Diittt--iitiiiutiion and In-Distribution Generalization. In Proceedings of the 38th International Conference on Machine Learning, 2021.
Vidhya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai. Harmless Interpolation of Noisy Data in Regression. IEEE International Symposium on Information Theory, 2019.
Vidya Muthukumar, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Danicl Hsu, and Anant Sahai. Classification vs regression in overparameterized regimes: Does the loss function matter? The Journal of Machine Learning Research, 2211):1014410117, 2021.
Raj. R. Nadakuditi. OptShrink: An Algorithm for Improved Low-Rank Signal Matrix Denoising by Optimal, Data-Driven Singular Value Shrinkage. IEFE Transactions Information Theory, 2014.
Shogo Nakakita and Masaaki Tmaizumi. Benign overfitting in time series linear model with over- parameterization. arXie preprint or orXiv2204.00300 08369, 2022.
Preetum Nakkiran, Prayaag Venkat, Sham M. Kakade, and Tengyu Ma. Optimal Regularization can Mitigate Double Descent. In International Conference on Learning Representations, 2020.
Arvind Neelakantan, L. Vilnis, Quoc V. Le, Ilya Sutskever, L. Kaiser, Karol Kurach, and J. Martens. Adding Gradient Noise Improves Learning for Very Deep Networks. ArXiv, abs/1511.06807, 2015.
Yuval Netzer, Tao Wang, Adam Coates, A. Bissacco, Bo Wu, and A. Ng. Reading Digits in Natural Images with Unsupervised Feature Learning. 2011.
Behnam Neyshabur. Implicit Regularization in Deep Learning. ArXio, abs/ 1109.99999 2017.
Manfred Opper and Wolfgang Kinzel. Statistical Mechanics of Generalization. Models of Neural Networks III: Association, Generalization, and Represenlation, 1996.
19

---

Published in Transactions on Machine Learning Research (03/2024)
Courtney Paquette, Elliot Paquette, Ben Adlam, and Jeffrey Pennington. Homogenization of SGD in High-dimensions: Exact Dynamics and Generalization Properties. 2022.
Ben Poole, Jascha Narain Sohl-Dickstein, and Surya Ganguli. Analyzing Noise in Autoencoders and Deep Networks. ArXiu, 2014.
Arnu Pretorius, Steve Kroon, and Herman Kamper. Learning Dynamics of Linear Denoising Autoencoders.
In Proceedings for the 35th International Conference on Machine Learning, 2018.
Adnan Siraj Rakin, Zhezhi He, and Deliang Fan. Parametric Noise Injection: Trainable Randomness Improve Deep Neural Network Robustness Against Adversarial Attack. 2019 IEEE/CVF Conference Computer Vision and Pattern Recognition (CVPR), 2019.
Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do Imagenet Classifiers Generalize to Imagenet? In Proceedings of the 36th International Conference on Machine Learning, 2019.
Robin Rombach, A. Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer. Hiighttnoouttion Image Synthesis with Latent Diffusion Modcls. 2022 IEEE/CV /CFF Conference on Computer Vision and Pottern Recognition (CVPR), 2022.
Ohad Shamir. The Implicit Bias of Benign Overfitting, In Proceedings of 35th Conference on Learning Theory, 2022.
Rishi Sonthalia and Raj Rao Nadakuditi. Training Data Size Induced Double Descent For Denoising Feedforward Neural Networks and the Role of Training Noise. Transactions on Machine Learwing Research, 2023.
Rishi Sonthalia, Xinyue Li, and Bochao Gu. Under- Parame-araeeterize Double Descent for Ridge Regularized Least Squares Denoising of Data Line. 2023.
Daniel Soudry, Elad Hoffer, Suriya Gunasekar, and Nathan Srebro. The Implicit Bias of Gradient Descent on Separable Data. Journal of Machine Learning Research, 2018.
Nitish Srivastava, GeofTrey Hinton, Alex Krizhevsky, Πlya Sutskever, and Ruslan Salakhutdinov. Dropout: A Simple Way Prevent Neural Networks from Overfitting. Journal of Machine Learning Research, 2014.
Chunwei Tian, Lunke Fei, Wenxian Zheng, Yong Xu, Wangmeng Zuo, and Chia-Was Lin. Deep learning on image denoising: An overview. Neural Networks, 131:251-275, 2020. ISSN 0893-6080. doi: https:
URL httph: 1ttp://000000/....eeee0000000000 http:///s..ttt///////eeeaaaaaaaa http://wwwwaaacccccccccooooaaaaa 50893608020302665
Nilesh Tripuraneni, Ben Adlam, and Jeffrey Pennington. Covariate Shift in High-Dimensional Random Feature Regression. ArXiv, 2021a.
Nilesh Tripuraneni, Ben Adlam, and Jeffrey Pennington. Overparamcterization Improves Robustness Covariate Shift in High Dimensions. In Advances in Neural Information Processing Systems, 2021b.
Emanuele Troiani, Vittorio Erba, Florent Krzakala, Antoine Maillard, and Lenka Zdeborov's a. Optimal Denoising of Rotationally Invariant Rectangular Matrices. ArXio, 2022.
Madeleine Udell and Alex Townsend. Why Are Big Data Matrices Approximately Low Rank? SIAM Journal on Mathematics of Data Science, 2019.
Pascal Vincent, Hugo Larochelle, Isabelle Lajoic, Yoshua Bengio, and Pierro-Antoine Manzagol. Stacked Learning useful representations in a deep network with a local denoising criterion. Journal of Machine Learning Research, 11(110):3371 3371-3408,, 2010a. URL htttp://jmlr htt.tttpp///////ooooooo///////// http://rrr..r/ppppp////////
denoising autoencoders:
vincent html
Pascal Vincent, Hugo Larochelle, Isabelle Lajoic, Yoshua Bengio, and Pierro-Antoine Manzagol. Stacked Denoising Autoencoders: Learning Useful Representations in Deep Network with a Local Denoising Criterion. Journal of Machine Learning Research, 2010b.
20

---

Published in Transactions on Machine Learning Research (03/2024)
Yutong Wang, Rishi Sonthalia, and Wei Hu. Near-interpolators: Rapid norm growth and the trade-off between interpolation and generalization. ATSTATS, 2024.
Alexander Wei, Wei Hu, and Jacob Steinhardt. More Than Toy: Random Matrix Models Predict How Real-World Neural Representations Generalize. In Proceedings of the 39th International Conference Machine Learning, 2022.
Yimin Wei. The Weighted Moore Penrose Inverse of Modified Matrices. Applied Mathematics and Computa- tion, 2001.
Blake Woodworth, Suriya Gunasekar, Jason D. Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and Rich Regimes in Overparametrized Models. In Proceedings of 33rd Conference on Learning Theory, 2020.
Denny Wu and Ji Xu. On the Optimal Weighted & Regularization in Overparameterized Linear Regression. Advances in Neural Information Processing Systems, 2020.
Ji Xu and Daniel J Hsu. On the Number of Variables to Use in Principal Component Regression. Advances in Neural Information Processing Systems, 2019.
Fatih Furkan Yilmaz and Reinhard Heckel. Regularization- Wise Double Descent: Why it Occurs and How to Eliminate it. IEEE International Symposium on Information Theory, 2022.
21

---

Published in Transactions on Machine Learning Research (03/2024)
A Additional Theoretical Results
A.1 Test Error and Generalization Error
Recall from the introduction that the work LeJenee et al. (2022) requires the simultaneous diagonalizability of the covariance matrices of training and test data. a similar spirit, if we assume that the training and test data have the same left singular vectors, we recover the conjectured formula in (Sonthalia & Nadakuditi
2023) as an immediate consequence of Theorem [
Corollary 3 (Conjecture of Sonthalia & Nadakuditi (2023)): ) Let the SVD of Xtst be Usst Vite In Theorem if further assume that U Utst I, then cf<< 1 (wnder-pprremelerized regime)
R(Wops: UL) = 1 11 +hrn (emm))=Ssslll
+
Mest
e²
Tr
Bu. Etrn + 1 =111) (Eime mira!)- +
(N
1
d
Merr
If c <>1
regime)
R(W opts UL) Tern || (22 | 1)mn)) 1ist 1|2
+ That d c Tr(Bu (I + Mern Di1)) +0
[ 1|2
1
N2
N
Additionally, we can use Theorem to give an expression for generalization error when the test data points are drawn from a distribution, possibly dependently.
Corollary 4 (Generalization Error). Let r < Id - N|- Let the SVD of Xtrn be UEtrn VTT let I:= U X By := U and c = d/N. Under our setup and Assumptions ] and & with the further assumption that the columns of L are drawn IID from distribution with meon p and Covariance E, the test error (Equation is given by the following.
If Lunder-parameterizedd regime)
E2 (R( opt, UL)
Vern | 1) + pup1" 1417))/22
Dist c²
Tr (80 i2nm + 1 =111 (2ime (irn!) + ( N
1
+
d c
If e (over-parameterized regime)
(E + + - + 1411 (4122)1122 1
E, Eg(R(Woptt opt, UL] = Mern
Nhst
| 13)
1
Tr(3u + - +0
+o
d c-1
N2
N
A.2 Out- of Distribution Generalization
Consider the following theorem bounding the difference in generalization error in terms of the change in the test set. Our main distribution shift result is corollary of its proof.
Theorem 5 (Test Set Shift Bound). Under the assumptions of Theorem consider linear regressor Wopt trained on training data Xtrn = UEtr VT with Errn such that ox( M, and tested on test data X1st,1 = UL and Xtst = UL2 with noise Atst, A with the same variance Mia / dd Then, the generulization errors Ri and R2 differ for e << by
R2 R1l 5
(3)2
Ten
1T |F
1 N
Nest (X, inn) (f + m
where f(c) = for e< 1 and f(c) for e 2 1. We add O(IEerm 1/2/ to the bound when 1.
22

---

Published in Transactions on Machine Learning Research (03/2024)
B Additional Implications of our Results
B.1
Out-of-Subspace Generalization
Theoretical Result Empitiall Resut
10a
Thecretical
Empirical
10a
Empiniall
Test Erro
Test Error
Test Error
109
10
1.5
2.0
0.5
1.0
2.0
3.5
0.5
1.0
1.3
2.0
2.5
3.0
3.5
1/C
N/d
1/c
N/d
1/C
N/d
(a.) CIFAR Dataset
(b) STL10 Dataset
(c) SVHN Dataset
(d) 50; We find that is approximately 54, 75 and 31 for (a)-(c) respectively.
Therratial Empriical
Theonoical
Thworaiial Emphiical
Test Error
Test Error
Test Error
20*
10a
0.5
1.5
2.0
2.5
3.0
3.5
2.0
2.5
3.0
35
0.5
1.5
2.0
2.5
3.0
3.5
1/c
N/d
1/c
1/c
N/d
(e) CIFAR Dataset
(f) STL10 Dataset
(g) SVHN Dataset
(h) r 100; We find that approximately 44, 66 and 20 for (a)-(c) respectively.
Theoretical
Thooretical Empirical
Theoretical
mpiricl
Empirical
Test Error
Test Error
Test Error
10*
30a
100
15 2.0
2.5
3.0
3.5
0.5
1.5
2.0
2.5
3,0
3.5
0.5
1.0
2.0
2.5
3.0
3.5
1/c
N/d
1/c
N/d
1/c N/d
(i) CIFAR Datasel
(i) STL10 Dataset
(k) SVHN Dataset
(1 150; We find that is approximately 37, 60 and 15 for (a)-(c) respectively.
Figure 8: Figure showing the test error 1/c when the test datasets retain their high dimensions. The training data is projected onto its first r principal components. The markers denote the square root of test error obtained from empirical experiments. The dashed black lines, which act as the upper bounds for the empirical results, are given by /R(UL) + ao (Wonp opt + 7) where RUU)) is the theoretical generalization error (refer Theorem 2 The dashed black lines, which act as the lower bounds, are given by VR(UL).
As mentioned in Section 3 we numerically verify Theorem 2 in two ont-of-distributtion setups namely small a and large a. The application of our result to the small a case was already presented in the main paper; see Figure 2b] Here, we present the additional numerical results when the value of a is relatively large. We do not project the test datasets onto the low-dimensional subspace for this. The training dataset from the CIFAR train split is projected onto its first. principal components where 25, 50, 100 and 150. Figure 8
23

---

Published in Transactions on Machine Learning Research (03/2024)
shows the theoretical bounds the generalization error from Theorem 2 Unfortunately, for the large case, the proposed lower bound in Theorem 2 is negative. However, we conjecture that RUUT) is lower bound instead. The results for the large case, shown in Figure g suggest the same. However, these bounds do not tell us anything about the shape of the generalization error curve.
The following corollary follows immediately from Theorem and Theorem
Corollary 5. If X and 2 are two different test datasets and Xtrn = UVen Vinn is the training data such that there erists L3 with a; = || - U,,,, then for R2 = R(Wopd X(st.)
IR2 R1 s (a (1)) +12
(1(3
nern"
1
L2 LI F +
Nest (or(Xtm)33(00 + vtn )2
B.2 Independent Identical Test data
100
25
Generalization Error
r 50
100
150
10-1
10
0.50
0.75
1.00
1.25
1.50
1.75 2.00
1/c = N/d
Figure 9: Figure showing the generalization error vs 1/c obtained for IID) test data for r = 25, 50, 100, 150. The theoretical solid line curve given by Corollary 0 We report the mean generalization error over at least 200 trials for empirical data points, shown by markers.
Let us assume that the test. data is identically and independently drawn from some distribution Dist with mcan zero and covariance Σ. Then the generalization error is given by the following corollary.
Corollary 6 (IID Test Data). Let < ld - NY. Let the SVD of Xtrn be UEtrn let L U Xists Bu == U² B, and c: d/N. Under our setup and Assumptions A and with the further assumption that the columns of T, are drawm IID from distribution with mean zero and Covariance E, the test error (Equation 7 is given by the following.
If c
paadeer-prmmetrrieee regime)
Eg R(W oopt UL)] = Wern
| H c 1)
Tist
Tr
BU 2222
1 1
(2 +
1/ra!)-²) to N
d 1-c
If e (over-parameterized regime)
31 1 + + 1) -1121/1
Er, (R(W opt, UT.)] Vern
nhst
|Errn 1
+
Tr (T+ + vin 2-22 +
+
d
1
N2
Nv
24

---

Published in Transactions on Machine Learning Research (03/2024)
Remark 3. Given any distribution V, can consider the diffcomorphism that changes the basis to U. Hence, making assumplions on the distribulion of I, versus the distribulion of Xist does not cost us any generulity.
Figure shows that the theoretical error aligns perfectly with the empirical result. The model is trained the CIFAR dataset and tested data drawn from an anisotropic Gaussian. The case of IID training data is presented in Appendix B.3
B.3 Independent Isotropic Identical Training Data
Empircall Besul:
Emprical
Empiical
Test Erro
Test Error
Test Error
10-4
10-1
20-1
0.5
10
15
2.0
2.5
3.0
3.5
0.5
1.0
1.5
2.0
25
3.0
3.5
0.5
1.0
15
2.0
2.5
3.0
3.5
1/C
N/d
1/C
N/d
1/c
N/d
(a) CIFAR Dataset
(b) STL10 Dataset
(c) SVHN Dataset
Figure 10: Figure showing the test error vs 1/c for I.I.D. training data. The theoretical solid curves are obtained from the formula in Theorem We report the mean test error over at least 200 trials for empirical data points, shown by markers.
Next, we consider the case of I.I.D training data. Let U Rdxr be matrix whose columns form orthonormal basis for an r-dimensional space V. Suppose the data is of the form Us for E R' such that the coordinates of are sampled independently, have mean 0, variance 1/r, and have bounded forth moments. Hence, in this case, we get the following theorem. Proof in Section C.8
Theorem 6 (I..D. Training Data With Isotropic Covariance). Let d/N and c, r/N. Then if
A
Ex.,n [R] =
|| c + 1)
Nost
2 1
Ti Trmn/))
To(cr, (hml)) +
natt
d 11- c
Tern
and if
E Ex..n [
Atrr 1(22 + 1 L1? 1 + nhst
C Tolcr, 12 +
Nist
d
N
where 21(cr,2) Ts((r,,)) (T2(cr,22) 2), and
1 1 + ((1 Tz(c,,2) 21(11 c, + c22)2 + 4c2z 2 T)((,,2)=
+ + zc₁
Gr
xc,) )2 4e
2c,
Figure 10 shows that the theoretical curves align perfectly with the empirical results where the training data is I.I.D. from a Gaussian with dimension 50. The test datasets from CIFAR, STL10, and SVHN datasets are also projected onto the low-dimensional subspace.
I.I.D Test and Training Data We can combine the two cases where training and test data are I.I.D.. Specifically, for the case when Xtst has sī the covariance and X as in the previous instantiation Section. Then the generalization error is given by the following corollary.
25

---

Published in Transactions on Machine Learning Research (03/2024)
Corollary 7 (LLDD. Train and Tests Data With Isotropic Covariance). Let d/N and c. r/N. Then if
C<)
Exem [ Mtrn - Ta(cr, Temm///
1 T2(cr, T2(cr: mon//e) +
+
Ti /cm
Mern
and of
To(cr, Itrn) + + +0
1
E X [ Iten" r k.
Ty(Cr, Veen) + dc
N
where Ti () T3(,,
==T2(Cr: 2), and
1 Cr + 2Cr
1 1 20, - v(1
C, + z0,) )2 + 4e22
2) 2/(1 Gr 22 + +4
2' Ty(c,, 2)
-+
20r
20p c + 2c, 20, +
- -
Ta(Gr,
2 /(1 c. 22)² 4c,
2x
Figure 11 shows that the theoretical error aligns perfectly with the empirical result.
Theoretical Result
Generalization Error
Empirical Result
10
10
0.25
0.50
0.75
1.00
1.50
1.75
1/c = N/d
Figure 11: Figure showing the generalization error vs 1/c where training and test datascts are both I.I.D. The theoretical solid curve obtained from Corollary 7 The empirical generalization error, shown by markers, is averaged over 50 trials.
C Proofs
In all proofs, WLOG we assume d/N = since even though d/N = c o(1), the relative error we will accumulate from this assumption be o(1). For instance, this means that the absolute error from this assumption Theorem will be o(1/N), which can be absorbed into the o(1/N) estimation error in the theorem.
C.1 Proof for Theorem 1 Test Error
C.1.1 The Overparametrized Regime, > N
We derive test error bounds for 3 I in problem setting. We also denote W Wopt by W in this subsection, for ease of notation. We begin by defining some notation. Let Xtra U. tyn Here U is d x with UTU = T, Ei is r x r, and Vaa is N. All of the following matrices are full rank.
26

---

Published in Transactions on Machine Learning Research (03/2024)
1. P -(I (mn) ER
5. U is dxn with U Ixx--
H V " Rrxd
6. Etrn is r x xr, with rank r.
= I V A Uten E R
7. Atr MtrUEV" with is d x unitary and Σ is N.
K1 H (PT P) E RRxx
We will henceforth drop the subscript Atrn in the expectation A
Lemma If d N and Atrn has full column rank, then
W = Xtrn (Xtrn + Atra)* UEtrr P) K"
TattkT17Pp 1pi.
(2)
Proof.
Note that has full column rank and Aum has rank N. Thus, we can use corollary 2.2 from Wei to obtain
2001
(Atra + USen ViTT Alr + Afr UErn (A H² (P'
ZPI).
We are interested in simiplifying the expression. Multiplying this through, we obtain
W = USen V Alr + UErr V A Utrrp
-UE Ver (Alrn H" +
(H +ZP)..
Replacing VT A = H,
W = UEmm + UEmn Htr - Uerr Vor (AIm K
H² Kj H + A/r H KT Zpt
Alm UEmm (P" 1)-1pppp 7" K H A US UE
p
Through further simplification, oblain
= U'ern H Etrn HU pl U UE HH H - - zpt
HUE P)- TT KJ- -- HUE p) K ZP
Setting HUEmm 7 - yields
W = -UEmm H + Eur 2P U. UE,,, HH - UU HH k zpl
-UE 2 2(" p)- H 1
- Z ( 1 K- + UE (P" -) K zpt.
Combining terms and replacing HHT + Z(P p) -T = K1, we prove
-PP W -UEm pt + U' PT p 1 KJ KJ 11 + (P" pp ZP",
UEtrn (DT P) 1 7d K-- 1 UE,,, 1(K] z) zPi,
UEErr (PT p) K-- - - "HHHHHH1KK11 12tt
Lemma 2. For d> N +r, X1st WXtst (P 1
2trm L.
Proof. Here, Xest = UL and W given by Equation 2
Substituting this, we get
X WXas UL USar (P -)- KT HUL UKr,, - K- 1PtUT.
27

---

Published in Transactions on Machine Learning Research (03/2024)
Note that PtU= -Ein and HUE Am UE E trm Etst (Z - I) Eest which yields
Xtt WXist UL - U 12-
UE 7 HH Ki ZE L,
UEtrrn 2 1 (Z - Z(P" P) P)- K -1) H1H KJ -) L
UEern 2 (2 - -)) + - -HH KT 2) 2)
UEtrm Z (K1 HH ) K E
UEtra (2 P) 7 k-1 L.
Lemma 3. Let abbb = O, and Q is a Haar uniformly random orthogonal matrix. Let ā = Qa, and = Qb, then E[a,b]] = 0.
Proof. We note that b[ = B[a"b] = 0. Then we get the result from symmetry.
Lemma 4. For > 1, we have that E[HH"]
Vern (c - 1) Lr + o(1) and the variance of each entry is
2
OL), For < 1, we have that E[HH*)
I, + o(1) and the variance is ((1((Thrm d)).
Mern
c)
Proof. Here we see that HHT Vir At (A )T Virn = VT Asrn) A Venn Thus, if Ven = [U] ... vy].
Then we see that HHT is an x r matrix such that
(H = o/ (ATr Atmm))))) o. 1 2-
Tem
Since V is Haar uniformly random and independent of Σ, using Lemma 3 for i + j. we see that the expectation is O. On the other hand if i = j, then using Lemma 6 from Sonthalia & Nadakuditi (2023), with N, d and I Atrn, we get that for e > we have that EloT (A Arrn) ( nirm (c - 1)
o11.. while for
2
c 1, El A = Min (1 c)
+ o(1). For the variance, let Aern = -mra Muru USVT, then we have that
0f Auru))
VVV -
2VT
a T
Tern of a,b.
Wern
1ern
1=1
28

---

Published in Transactions on Machine Learning Research (03/2024)
Where a, b are orthogonal vectors (when i + j). Then for computing the variance when 1,
2 asbs
i=1
N
N
abbjanby
M
0703
j=l
Σ arbs )
N
N
Mhm (c- - 1)2 +
+
E
Σ
Eashs)
i=1
o²
+
Menlc- - 1)2 + o(1))
Bla
Mrn (e 101--11- 1)3
1=1
0
Wern (c 1)3 + (0(1)
Σ
+
1
N
N
1=1
1 Tern (c 1 + t
Here even though a are not independent, because of the smaller variance in the entries, the error is absorbed
in the o (+) term. When i = j. we use the same proof Sonthalia & Nadakuditi (2023). to see that the variance is at most O
Teen N A very similar computation follows for the variance when <<< 1.
J
We prove a general result on inverses matrices that whose expected norms are I2(1).
Lemma 5. If [[[[)]]|| (21) as N grows and Var((XN)s) SN, then E[xy'] [[X,] O(sx). Additionally, if Var((Xx [[[x))) O(xx), then Var((X );) O(SN + IN).
);))
Proof. Let 8XN = [[ Notice that 8X = (p(s)) and [[6XN] = Additionally, by the Taylor expansion (Y + 50) - 1--88-------- 0(822) 0 we have that
x [[Xx]]1+++ 1X -0(0X))
In particular, since [[X,]-1 =(1), we have
0(E[X B[Xx] -1 (VVar((X)))))= + 0sN)).
Finally, note that Var((6X))s)) = O(tN) by assumption. So,
since Var((X>')b)) = Var( - -xx + + = + (x)
Lemma 6. For > we claim that E PT Pr -11-) Lr, each entry has variance O (t), and
c- + 0 (
E[Erra P) P
with element-wise variance O(1/d).
29

---

Published in Transactions on Machine Learning Research (03/2024)
Proof. Recall that P -II Arn UtEn Thus, have that
p p "im (1 - A UEer.
Enm Etrn U" A A A UEin
ET PnnEtr Eim UUSSEUU
IN
EL Etrn ΣT R
R Etrn.
08-N
Where R is a uniformly random r x unitary matrix. Then by symmetry (of the sign of rows of R), we have that
Etmn (-/1) Eirn = -1-2) E
E[P" P Etmn
So, we have that
E P" pT PE = U
[I-E(AmAAmn]])
(1- 4.
Thus compute the variance, we first compute the variance of (Atra Alru)ig. For this, we first note that
LIN
0 0 -UISSTTT =E (1m Alro =E Arm
=E
0
The first equality follows from the symmetry of the signs the rows of Ü. Then we can see that
L isN N
Σ ( Arm Pa
i>
From Lemmn 14 in Sonthalia Nadakuditi (202)), we have that [E[(Arn Alrw)al + + 2 + +(1). Then combining this with the computation above and using symmetry, we have that for # j and min(i.j) $ N
1 E[(Atrn N
(
-1 δ cd -01))
1 -
Now consider the other (full) SVD of Xtrn given by ÕaxaLax VT NxN. Note that the top left x block of E is Etrns and we can choose Ü so that the first r columns of Ú give U. Note that since ÔTü is still uniformly random, the symmetry argument above follows for iT Atrn Air Ü. Additionally, for i, $ r, (ÜT AurnA 0)g = (UT Ammn)),n U); Thus, we see that for i.j rr
E E AurTAmi = N c
1-11 2
+ d()),
2 cd
while for i i= j, we get that it is O (+) by Lemma 14 of Sonthalia & Nadakuditi (023) Thus, finally, we have that arranged as matrix
E [(Er] pd PEr1) o (Erhh p PErT) =0 (
0
By an analogous symmetry argument, since (Arm-lrn) = A Aimn Alr,, for any i, we can show that
Var (OU Atro Atm = (
30

---

Published in Transactions on Machine Learning Research (03/2024)
We can in principle show faster decay for this with more involved argument, but this is enough for our purposes. We can now apply Lemma with XN = 1 - (U² A A U) to see that
E[ (P 1)-1 = c-
c - 1,
(
and has element-wise variance O(1/d).
Lemma We have that [[Z] and Var Var(Zi;) = ( and each element has variance O (H). Finally,
| Further, E|ZEgrn E(En 21 Σx1
Thrn
= [2Zmmll2) with Var((Z- =
[ 1| (0(1mm)))) d +
12
dc
Proof. The clement-wise variance and expectation Z can be computed exactly as the proof of Lemma in Sonthalia & Nadakuditi (2023). Specifically, by considering the row uj of U and the row o; of V, treating Zaz 3, and replacing Otrn by оj- The expressions for the element-wise expectation and variance of Z and 2 Z immediately follow from those of Z and the fact that 01/0, +(1) by Assumption
min(d.N)
For Z-1, we continue the computation using Zij = Tig with Tij =
Σ
-agbe with a and obtained Ak
1
k=
Errol
using 8y and u; respectively, and A singular value of Atm It is easy to check that Var(T3)= =0
N2
using symmetry argument for a and by and the fact that [[1/ O(1) by Lemma 5 of Sonthalia & Nadakuditi (023 Now we can use Lemma to conclude that
[2iral
d (
|>
[ |1
=
with Var((Z-1)s)-
d2
Lemma 8. For > [[Ki]
- + - Di2 + o(1) with element-wise variance O(1/d). Further, -
Vern
E|K |1 = Thrn (1- (Trn Dir + +1) + o(1)
=
with element-wise variance O(1/d).
Proof. From Lemma we have that E[ P) P -- 0 (
c- ---
Recall that
K1 HH + Z(P" -HH + ZΣ (Eern (PT (pT p) (xr.) ZT.
Then recall from Lemma that
E[HHT]
o(1)
2
Mern
For the second term in the expression for K1, we want to use Lemmas 6 and 7 but they give expectations of each term separately. Note that
E - E = (Coo(XXY) < VVr((X)
and also note the following fact, from Bohrnstedt & Goldberger (1969)
Cov(XY, WZ) = E.XEWCoo1 BY w) EXEZZOo(Y, W)+ Eow Z) Cov(X, C)o WW)
Cov(Y, -
31

---

Published in Transactions on Machine Learning Research (03/2024)
We use the facts above along with Lemmas 6 and 7 to compute the expectation. Specifically, the second term in K is the product of three terms 75 (Sern (P' P))1 and D Hence we need the first fact to replace the expectation of the product of two terins with the product of the expectation of the two terms. To use this again, we would need to bound the variance of the product. Hence we need the second fact. Doing this computation, we get that
B[Ki] Tir c I +
c Syn + +0
(1) + o(1)
c-1
For the element-wiss wise variance, consider 8K1 Ki-E[Ki]. We cover the + j case. The i = case analogous.
From the proofs of Lemmas 4 6 and 7 we have Zig = + Tiy and (Eern (P' p) D2-llee = U Atrn U)i-.
The expanding the product, we get that
(6K1)is = (us(AATm Alm )z;) + A Almntiin)
+ +0 AlUTAmmtn + +O(Ti)
( ALm +
N
+0
Σ
UUT Cu Abmn) +0
Σ 1=1
Tu
+0
Tu" ConnllnDaal +0
Σ
TU Tem AtonAton
11/=1
Then since
Var(XY)= = Cou(X22 + (Var(X)+ +
- (Coo(X,Y)
using this for terms five through nine, we get that Var ((0()))) 0 (1).
For the inverse, we cover the i * j case again. The i = j case is analogous. We can perform an analogous computation to the one in the proof of Lemma g to get that
Var Amm)),)))))))))))))))))))))))))) (N)
using the fact that E [++]= Atrn for any and symmetry argument analogous to the one in the proof of Lemma 6 to note that
= 0()) for a random eigenvalue 0 of Atrn- We also use the fact that (Arr Atrm)
E [T A UU UYg] =0 ())
p= 2- 8.
One can also check by the arguments in the proof of Lemma that
" o
E
T 2p
0
O(1)
de
These together with the facts about Var(XY) and Cou(XY, ZW) above establish after tedious but straightforward computation that
Var((6K))3)=0 (
We can now use Lemma to establish that
(
(Rra Di + 1,) 1,) +0 ( 1
E|K 11 = -
-
+ o(1)
C
d
nrm
1
1)
2- + 1,) + o(1)
c
and Var((KT )(²) 0t))
32

---

Published in Transactions on Machine Learning Research (03/2024)
Lemma 9. When > 1, we have for W Woy Wopt that
Tr( Eir nirn 1) (Iemml)) d
B [
O
o(1)
Proof. We first use the estimates for the expectations from Lemmas 1 and to get an estimate for the expectation of || We get this estimate by treating various matrices in the product as independent. We then bound the deviation of the true expectation from this estimate using the variance estimates above. We begin the calculation as
| 2 Tr(W"W)
Using Lemnaa we see that the trace has three lerms. The first term is
Tr (H² ((P)) Stm UZ U (P'
Here have that U is d with orthonormal columns. Hence we get. that U T. Then since the trace is invariant under cyclic permutations, we get the following term
Tr (Cerr (eDeem(P' (P
H H (I (ZE (P" ")=n)))
Now we use our random matrix theory estimates for various terms in the product. From Lemma 7 we have that E EAr.. [2 Etrn Thus, that first term's expectation can be estimated by
Tr ((erm P) D KT HH (KT E (Cemn (P P) Eirn))
Then using Lemma 1 we can further estimate this by
Tr ((Drra (1 P)-1 ) K (KT () 1 2i (Dern(P' (p + o(1).
Nem
Here, the error contribution of the o1) error from Lemma estimates are ((1). Then we use Lemma to replace Eern PT P) Eern to get
is still o(1) since will see that all the other
1 "--)
Tr (E K
(Ki ( + o(1)
Mern c
Finally, Lemma g to replace the last term and get
c
Tt Eiittio (1-2) (1r thm
+ +
Vtrn
This immediately simplifies to
Mrrn
Tr (D (E2,,, + 1 + o(1).
(3)
The sccond term in Tr(WTW) is
2T
UEm ZP!).
We can rearrange this using cyclic invariance to -2 ((K) ST z xm (Eern ( (PT p) - ( Z-1 HH ZP*HT).
Let us focus on the P HT term. Since pTP is invertible, we have that has full column rank. Hence we have that
pi (P" 1p-1
33

---

Published in Transactions on Machine Learning Research (03/2024)
Further, since p=
-II A and H Venn Abn. we have that pt1²" (PTP)) - u ( Arm (A " Veen.
Finally, we notice that Thus, we have that Finally, the last term in Tr(WWW)
A Alm = =(Alrn)²
P (P" Epm UT Aern Aern Atrm) "
Vern = O.
(4)
Tr (((PTTTZ"(KT H /f
"HI = (PP))=1
We note that
We use this observation along with cyclic invariance to get that the last term is the same as
Tr ((KT)) - - (Etra (P P) ) z²)
We again use Lemmas
and to get that its expectation is estimated by
1
2
Tr ((KT)) T 2 KJ Eirh (Eern (P*
pp Etrn) ( +0 d
[1emmll²) + o(1).
Tern
c
The contribution of the O [Eee error from Lemma is still [ 11
since the estimate for the expectation is O(1) We now use Lemma G and to see that the final term's expectation can be estimated by
1 )
Itrm (c-1)
(I, + Uern Syrnn + 0 (1emmll²) + o(1)
(1
-
Vern
c (c-1)
d
hr Thmn 2) + (Arrall?)) o(1).
Tr(Eira
c-1
Finally, to bound the deviation from this estimate, note that for real valued random variables X, Y we have that
= [Cou(X, YY] / Varr( and for real valued random variables X, Y. 2,2, W, we have the following fact, from Bohrnstedt & Goldberger (1969).
Cou(XY, = EoX Z) EYEZCor(X, W) + EXEZCoo(Y, EYEWCou(X. X, Z) Cou(X, (Y Z) Cov(Y, C)),
We repeatedly apply these two to upper bound the deviation between the product of the expectations in the estimates above and the expectation of the product. It is then straightforward to see that since all variances are ((1/d) except for those of Z and Z, which are both O(1) whenever Σtro O(vd), the estimation error is ((1vVd) = o(1.
So, we can conclude that cach of the estimates in equations and have error o(1). Combining the terms together, we get from equations and that
Tr E Err Thrn (Eimn n [,) 1-)- + +0 [E=mlll o(1)
| c-1
Tr (Etra nrra 111 + |Eemall + o(1).
1-1
d
34

---

Published in Transactions on Machine Learning Research (03/2024)
Theorem 7. When d > N + and 3 I, then the test error R(W, Xtst) for W Wops is given by
Mern Ntat
(2om + 1) LIle +
Tist
1r(22mn227 Mirn ( +0
[1emlll))
+ 0 21)
d c
d2
Proof.
From Lemmas
and 2 have that
R(W, X = E
1 Nist
[[Eern (""""
LI + Tist
[W]]
d
To compute the expectation of the first term, we observe that it is given by
Tr(UEtm (P" 1 - LL'LLLE Ki 2(P2')) P) E(mu))))))) E Nest
We apply cyclic invariance to get that it is the same as
1
Tr(
Tr(Eih
Ki ZEih (Eorn (P" P) EErr (Eern (PT PP [ -T Ki ' LL").
Nest
We finally use Lemmas 6 and to estimate it by
c c-1 (-1)²
2
1 -2
LL* + t0(2)
Tr
Egrn
Etr
+
E
Ni
Thrn
Thrn Tr (EE) + 1) LIT,"
+o
Nist
Thrn
(Etm, + nern L + (1)
||
Nist
Since test and train data decoupled, can treat LL" LLT/Nts /Nts constant N grows, noting that due the Eim, the final estimate is o(1). So, repeating the deviation argument at the end of the proof of Lemma above, we then have that the deviation from this estimate is o (2).
Combining this with Lemma g. we get that
Mern
(Eimn + 1) L1B + Nea
West
d c-1 Tr(22m (22m + (irn!)-1) +
(
[ d3
0 2
C.1.2 The Underparametrized Regime, < N
We derive test error bounds for 3 = I in our problem setting. We also denote Wopt by W in this subsection, for case of notation.
We begin by defining some notation. Let Xtr = U. VT Here is dxr with UTU = I, Exro r and Virn is r N. All of the following matrices are full rank.
1. Q = VT(T- - Atrn) E Nxr.
5. H, = KTK + 2F (=(QQ")-12 Rerr
H VT2 Virnt E Brxd
6. U is d x with UT = 1rx
= 1 VT A USm E xxx
7. Σrrn is r x r, with rank r.
K Al UErr E NNx.
8. Atm = Meen ÜEVT with 0 is unitary
and Σ d N.
We will henceforth drop the subscript Agrn in the expectation EA
35

---

Published in Transactions on Machine Learning Research (03/2024)
Lemma 10. When d N we have that
W USnn Hi KJ A/ro + UUttrH (Q"")""0"""""1
Proof. We know that W- x(X + Atra). By Corollary 2.3 of Wei 2001 setting X = -CB with
C -UEra and B = VT, we have that
(X + Atra)* = Atra - -Q - (K+
- z² ='(QQ")--11),
So, using the facts that X = UEtrr VT, k= =- Uiin: Unnnnn
have that
W = -x(x + Afr)
UEtra V VTAtr - UUE Q UEtra V UEm Alm
UEtrn V-QQ 2 KT Atmm UE V Aym UEtn 1 (QQ"")
+ UEer V (Q0))
Using the fact that H = V - Atros we get that
UE US Q + UE HU Hj H KT Alm UEem V2 V'Q'HH Alm
- -UEtrHHEE HJ's zT --Z-- H + UEern VT ZH,
Using the fact that Z = I+ A trm
UEno = I + HUEtrn we get that
W- UEtra H - UEtr Q1 H UE (7 1)H Art V A
-'z- UDern (Z - H1 100:z(((00 (Q00))="~~'10 U2mm V" V' (
Using the fact that H1 = KTK + 2 (QQ we gel that
Ummll - Umm Q + UV 1HT KTT Atr, - UEim H 1 KT At
-UEI 1 Q' ZH, KTT A -UEinn ZH, (H1 KTT -
+ +UE - nd (QQ²) 1H + U.Ar V2 Q¹ 2 |H, (H1
K2 Kyz-1H
UEmm H U. Q H + UE, ZH, KT KTA' Arn - UE H KT Atm
-UEm Deshnv.VT VTQ' (01"2H111000 A U.rrr H1 + UE.,, KTT T KZ-1H
+ HUm zd (QQ")) Umm 1² - Q² ZH, 1 KZ-'H.
Cancelling terms, get that
W US 7H, KT Alm - UE KT KT - UEmm V V Q' A
+ U.r. Z HH KT KTKK-- KZ--H + U'Er (QQ)))
UEnr VT Qi ZH KTKZ-1 H.
And we rearrange to get that.
W -UEm H KT Atm + U.mm -H
Atm
+ UErr (1 V (")2)2HH"")" KT (0-KK-11
-H K Atm + Utrm H 2 (TQQ"))-1
where the last equality is because Q = VT A A has full rank, so Q Q-(QQ")-110-) VTQ+= VT(T- V V)
7
36

---

Published in Transactions on Machine Learning Research (03/2024)
Lemma 11. For d < N r, with notation as in Lemma 10 have that Xest UStrh H (QQ"))-1"n I..
W Wist
Proof. Note that X WXist UT US 2m H KT AI, USem (Q0") Remember that K -Arr U2, AtruUSttt Esst KEin E and HUEsst (HUE) (Z T) Esst This gives us the following equality,
Xst - Wtst = UL - U. H K2 K UE H. 1 ("00"""-QQ22-110
+ +Utr i - (Q0))=====)))) -1 I
+ Eimllli''" - - -1inn) -U( Lin (K" K -" (0(0)))--
Using the fact that H1 = KTK + - (QQ2)-122 we gel that
Nist - W West = UL - tw H H1 Eir L + UStr HT z" 22 (QQ")- - UE UE (QQ") -1 L..
1 c
Lemma 12. For < 1, we have that E|E 1 K KE is (2))
Mirn 1 - +o(1) and the variance of the ifth entry
Proof. Note that KJ K = Eim U (Amm A So, K)₃ = auu? (Atrn A ) Jujay Using ideas from Sonthalia & Nadakuditi (2023), we see that if i + j. then the expectation is 0. On the other hand if = j, then using Lemma 6 from Sonthalia & Nadakuditi (002)). with p = N, = d, A AT we get that
B[ K" K KETh))]
Wern 1-c + o())
The result on the expectation follows immediately from this.
For the variance, pick arbitrary i j and fix them. Consider Ü un and b Ütyy. They are uniformly random orthogonal unit vectors, not necessarily independent. Now note that
(Eihh (KT K)E
uu "'EiE:"") (EE"
=a"(ES>)0
d
1=1 0k
So, we get that
d
E E E trn
(K* K)
)ig ) =1=B E
a bbbbabbi
k=
1=1
2²
+
o(11)
E
Σ anbr
cJ
o²
+ t
E
Σ
c)3
(1- 0)2
+ +((1)
Σ
(1
c)3
(t)
E
3
k=1
37

---

Published in Transactions on Machine Learning Research (03/2024)
where the last line holds due to the following reasoning, even though and b are not independent. We then use the fact that
Ela 1 E & Var(aa)
(g) So, by symmetry of and Lemma 13 of Sonthalia & Nadakuditi 2023), get that Var (Ei- oB -0
coordinates, Var(a = 0 The same holds for by, giving us that
Bla E
S 0
d2
This gives us that
c²
Var (Cird (K² K) K)
7
i j.
d(1 -) c)3
For i = we use Sonthalia & Nadakuditi (2023) to see that the variance is 0 0 = - since d = c..
c²
Lemma 13. For < 1, have that B[E 1 K KTAi, Apr (Atrm) K KErrll
+ +0l and the variance
1/ro (1 c)3
of the th entry is O (N)
Proof. Let M == Enyh K Almn (Atmn) KKT, and note that
E-I Apr (A Y KE-L tra
Exrn (Atrn ( (Atra ttu U
So, My ouue (Atrn (Atrt AT Jrm uyoy- Using ideas from Sonthalia & Nadakuditi (2023). we see that if j, then the expectation is O. On the other hand if i J, then using Lemma 6 from Sonthalia & Nadakuditi (2023), with N, d, we get that
of c²
E M
Vern (1 c)3 o(1)
For the variance, pick arbitrary * j and fix them. Consider a = Ü us and b = Ünuy. They are uniformly random orthogonal unit vectors, not necessarily independent. Now note that
My = uf (Atrn (ArrnAff
"TUSE" E5 a" (EE:EE))
bsbr.
1=
38

---

Published in Transactions on Machine Learning Research (03/2024)
So, we get that
1
B
=
E
1=1
E
ag babba
k= oko
c* (c² + 22/66c 1)
Σ ba 1
+x00 (x(()) +(]])
+ o(1)) E
Σ a
(1 (1-c)
(x(c) + [[]]
= (x(c) +
x(c) Σ B
where the last line holds due to the argument in the proof of Lemma 12 Here x(e) is some function of This gives us that Var[My = fx(c) + + for i # For i j. we use Sonthalia Nadakuditi (2023)
see that the variance is O (t).
Lemma 14. For e < 1, we have that B[QQT] (1 T) and the variance of each entry is O (2). Further,
B((QQT)-1] = 1 I 0 (
and each element has variance ((1/d)
Proof. Recall that Q = =T - Arr Atrn). We thus have that
QQ" = =VT(1 - Alrn Atm)).
-TV - VT At A V
VTA
I. V'İSIEV"
la 1, R
0
RT.
ON
Where is a uniformly random r N unitary matrix. Then by symmetry (of the sign of rows of R), we have that
B[QQ I. ct, (1
Next notice that
=[QQ")=v*(1' VT ( Atrn))
thus to compute the variance, first compute the variance of Aemd)es- For this, we first note that
cJa 0
0 ElAAtt E[A) Arr Airn
Since Alry Atr is symmetric, we can that
fe isd
Σ ((AtrnAer A
00 i> d
39

---

Published in Transactions on Machine Learning Research (03/2024)
o(1). Then combining this with the computation above and using symmetry, we have that for + j and min(i,)) S
From Lemma 15 in Sonthalia & Nadakuditi (023)) we have that B[((A A(rn)as
E [| Aern) d -
+ + o(())
3 ed
c²
Now consider the other (full) SVD of Xtrn given by Uaxa V2 Note that the top left x r block of E Etrn, and the first rows of V give V. Note that since VTV is still uniformly random, the variance argument. above follows for VT A AtraV. Additionally, for i.j r, (VT Thus, that for i,j rr
V)s (VT A Aer Vin
[ A V)a) d-1 c- cd + +o(1).
= ( By an analogous symmetry Thus, finally, we have that arranged as matrix E[QQ" @ = argument, we can show that Var ((VT A Atm V) = 0 (अ) In principle, one can get a faster decay bound with a more sophisticated argument, but this is sulficient for our purposes. Now, by Lemma we get that
((VTAl
E((QQT)-11 - o (
I
and each element has variance (11d)).
Lemma 15. For c < 1,
1
E Err H1
Eyp
Tern 1 I, + o(1)
1
and the variance of each element is O (1) Additionally
E H Etrnl (1 -))/rr (Trm Enp + - o(1),
and the variance of each term is (2) Proof. Recall that
H ===KK Zd (2Q")) = (QQ") - ) Z.
Using Lemmas 12 and 14 along with an argument analogous to the one in Lemma g
we get that
E mir 1 - I, +0 1
H1 Ei 1-
o(1)
and the variance of each element is 0 (2).
For the inverse, define 8H1 H1 B[H,] and by argument analogous to the one in the proof of Lemma 8 we get that
E
Eumn [ = (1 - e) (nim D + cl,) + o(1)
and the variance of each term is O (H)
Lemma 16. When < 1, we have for W = Wopt that
c²
Tr
E2
+
3 _1
( nan 1,nn 1,) + o(1).
1-c
Marn
40

---

Published in Transactions on Machine Learning Research (03/2024)
first use the estimates for the expectations from the lemmas above to get estimate for the expectation of [[ and then bound the deviation from it using the variance estimates in this section. We see that the first term in Tr(WTW) is
Proof. Again, like in Lemma
Tr((A) ( 2rm H K" Atrm) = Tr(K" Tr(K"A (Arr(A "( "(mm
Then using Lemma 13 along with cyclic invariance of traces, we see that this is estimated by
nrn (1 c)s Tr (H( (2 Hi + o1))
Then using Lemma.
15 we get that this is estimated by
2²
Mer (1 c)3 (1 e) + Vern E + o(1)
Mn - Tr (Zitmn (2 nim-r) 2-) ))= +
o(1.
The second term is We rewrite this TN((QQ0"~))²(11)))) (100))))111
Tr(((QQ")11) 2 (Ceen )
( Eero) Hy Eern ) (00
Using Lemmas and 7 we can estimate its expectation by
Tr (((QQ)) E P " (Etr ( o(1)
Nrr 1
Then using Lemma
14 and the fact that HT H1, we get that this be further estimated by
c²
Tr Eor((H) ()mm )2 + o(1).
Menn
c)s
Then using Lemma. 15 we simplify this estimate to
phn (1 - c)3 cj((1= (l1-c)2naee () + D o(1)
c²
Tr (Etmm (Enma e + 1,rn o(1).
Inm
The cross term in Tr(WTW)
Here the term (after cyclically permuting) that we should focus on is
(A(t)())))) - Ai (Atrm) A Emm
Here since Apn = Tt ÜSVT and Ü, V are independent of each other, we see that using ideas from Lemma in Sonthalia & Nadakuditi (2023) and extending them rank as before, the expectation of this term with (1/d)) variance. Thus, the whole cross-term has an expectation equal
Again, to bound the deviation from this estimate, note that for real valued random variables X, Y we have For real valued random variables X, Y,
that [[[[X]] [[]] = [Cou(X, < / we have the following fact, from Bohrnstedt & Goldberger (1969).
Coo(XY, EXEW OY W) EXEZCoo(Y, + WC)o(XX))
(E 2) Cov(X, W) Co
41

---

Published in Transactions on Machine Learning Research (03/2024)
We repeatedly apply these two to upper bound the deviation between the product of the expectations in the estimates above and the expectation of the product. It is then straightforward to see that since all variances are O(1/d), the estimation error is O(1/d) = o(1).
Finally, combining the terms, we get that
c² Tr
Bi|
Elm
Elmm
I,)
(Emmc (onlt)- + o(1).
1 --6
nern
Thcorem 8. When d < N r and B = I, then the test error R(W, Xest) for W Wops is given by
A
Menn Neat
(2em + Virn!)
L||
Nist
c²
Tr
Etrn
Eim + _
(Ein C+ Mim + +0(2)
1 1
M/rn
Proof. Note that R(W, Xtst)
Nea |UDern '2"
1
brn L1B + Reg W W|
To compute the first term, we observe that is given by
Ntat Tr(UE 2 (QQ0") E LL" "
(Thh"""))))))) ZHZ 'Hi'' Exrn U²).
This can be rewritten using cyclic invariance
1 UEm Eir - LL Eith (QQ")- 11Ern Etrn 2 Eern).
Nest
We apply Lemmas
and to get that its expectation can be estimated by
Tr Tr
((c- Dymr (nira (2mm))
1 c
LL "
+ +o(l/d)
Nist
Minnyy Tr (222 Thr!!) LLT) o(1/d)
Nost
Mirn || (E2 + !)r!!) Ll + o(1/d).
Niat
We get o (5) due to the En term. Again, we can argue as in the proof Lemma 16 to bound the deviation of the true expectation from this estimate by o(1/d), noting that since train and Lest data assumptions are decoupled, L...) /Nest can be treated as constant as N grows.
Combining this with Lemma 9 we get that
Ttrn Nest
(Eg + Virn! 1) 1 T
Nist c² +
Ezm (xim + 1 _ (2ime+ + (irnlr) + ( hn) 1/rnn
Tr
1-c
Theorem 1 (In-Subspace Test Error). Let r < [dd NJ. Let the SVD of X be Uter Vir let L U X By UTB. B, and = d/N. Under setup and Assumptions and the test error (Equation 1 is given by the following. 1f c < (under-pareel paaute-parumetrrizeed regime)
R.W opt, UL) = Mhnn
|| 1)
Nest
niat c²
_1) (5gm Winn 1) ) +
+ d -
Tr
Eum +
m
NV.
42

---

Published in Transactions on Machine Learning Research (03/2024)
If (over- pauemeerraeterr regime)
4
R(Wops. opt, UL) = 1130 (Sira + -hrn()--L(l
Nost
That
| 1? N2 + o
+ d c-1 Tr(Bu (I + Vern I +0
N
Proof. The version for = 7 follows immediately from Theorem and Theorem
We demonstrate how the the general version is straightforward repetition of the proofs of the two theorems. First denote by Zopt the minimum norm solution to the denoising problem (where B I). Then Zopt = Xtrn (Xtrn + Atr and note that
Wopt Viro (Xtrn + Atrn) = TT XXem + Atrr) = BT Zopt
We present the adaptation of Lemma 9 the other lemmas can be adapted accordingly.
We first use the estimates for the expectations from the lemmas to get estimate for [| = =18 llp: and then bound the deviation from it using the variance estimates above. We begin the calculation as
1 oope || = Tr(Zo B83 Zops)
Using Lemma we see that the trace has three terms. The first term
P)-1)?? U U US (P" (P
Using Bf = Uupu Then since the trace is invariant under cyclic permutations, we get the following term
Tr P)-1 P)-t"" 'H'
The rest of the proof for this term is the same Lemma The second term in Tr(WT W) is
((P"(((PP))))))) TH (""")""""("""""""""""""""""""""" By By Atm
ZPt) 7P)
Then the rest of the proof for this term is identical to the in the proof of Lemma Finally, the last term in Tr(WT TT(WT35TW) is
Tr((P!)' z" (KT H (Z-1)" (2->)) Bu 3f H
The rest of the proof is the same again, after using the cyelic invariance of the trace.
C.2 Proof of Corollary 1 The Distribution Shift Bound
We first prove Theorem 5 bounding the difference in generalization error in terms of the change in the test set. Recall the theorem below.
Theorem 5 (Test Set Shift Bound). Under the assumptions of Theorem consider kinear regressor Wopt Irained on training dala Xtrm UEtr VT with Etrn such that (X(r)))) M, and tested on test data Xtst11 = UL and Xtst = UL2 with noise Atst,1, A with the same variance That /d. Then, the generulization errors R, and R2 differ for e e< by
RR R1 5
(3))
Ten
12Lا L
Nos (om()))))2
+ 2
N
where f(c) for < 1 and f(c) for e 1. We add O(I[Ern 11//N2) to the bound when 1.
43

---

Published in Transactions on Machine Learning Research (03/2024)
Proof. We will first show this for < 1. Let R, R(W opt X(st,)). Remember that the test error is given by
R₂
Mrn Ntst
|st
1)
c
1 _11 (Eim ( (iml!) + Mern
1 N
+ her
2 2
Tr
B1
Dim +
di dl-c
Note that the second term above has no dependence on Xist,i so the difference is given by
Mern Nest
(I - n ()rnt)-'22 12 11111100mmmmm !imm!) L1 l12)
R2 - R1
N
Vern Tr (1=2mn c - (2 c+ (L2L) b,1 +o
Nest
N
(4)
Mhrn
|| + whrn 1) 9u 90 E e v 1 - L, ||
Ntst
N
Mtrn
130000 8T (-2mn 1 L1 N
Neat
(1))
Uer
|3, 12
+ 1) |r L, (L L 1
Nist
where (i) above is by the Cauchy-Schwar Schwarz incquality for the Frobenius norm and (it) above holds since ||BB| r
||A|||||||| So, for Eurn with lower bounded diagonal entries a; M, have that
1
R2 RRll Nest (r (Xtr)(X Vern )
B 112lllll(aaa
[alll L, 1,D
NV
Vera
1
-UB U11"Ul12llLaa L,
(Xtm)) Mern!
N
Tera
1135 [| L +
(orr(e,(Aern) ec menn )
N
(3)2
nern"
L22T - La L +
Nest
(Xr(Nera) Pe nan )
N
Similarly, for c <> 1, we have that
R2 - R2 s (8)²
nenr Nest (a, (Xr(X) + m
1
LzLا - L
+0
+
N2
N
We now prove our corollary below.
Corollary 1 (Distribution Shift Bound). Consider linear denoiser W opt trained on training data Xtrn UEirvV. VT Let it be tested on test data Xtst.1 = UL1 and X1s = UL2 generated possibly dependently from distribulions supporled in the span of with mean Up, and covariance Eu,- = UE,UT respectively. Then, the difference in generalization errors G. = Exx., [R( Xtst,)) is bounded for c < 1 by
T1 (
IG2 S (o, f(c) + +
De E1 + Hnse HIu || +
N
where f(c) for c < 1 and f(c) otherwise. We add O(I l2:/N2) when e 1.
44

---

Published in Transactions on Machine Learning Research (03/2024)
Proof. Let LG == L; [pa M4 ... ps] be the centered version of the test data matrix. In that case, Ex [Li]
Ex.,, (UTTUUttX Xest,i 0 and
Ex Ex.,, = Ex... Xes, = Nost
Now note the following elementary computation.
(K = Ex... [(Ls + 1
pd)( [ms ue m())
Ex.,. . [L,Lg]]] + + + Nist4414
Nern + Nestlliu
We can now follow the initial part of the proof of Theorem to get the following for 1.
92 91
Men Tr (Bv (E (Bu:S
vern 1) 2(B (Ex [22 2 E Ex
to
Nist
N
T (3v By (Eim + nir 1) 2E2 - E1 + uapa - mmxh)) + o
Now, we follow the rest of the proof of Theorem to complete the proof.
7
C.3 Proofs for Theorem 2 Out-of-Subspace Generalization
Theorem 2 (Out-of-Subspace Shift Bound). If we have the same training data and solution opp assumptions in Theorem | Then, for any X1st for which there cxists an L and and Aest that satisfies 1,2 from Assumption 3 we have that the generalization error R(W Wopt. satisfies
O such that || ULII S a,
RR(Wopt: opt, Xear) R(W ope, UL) S a² a²0 (W opt + +)
Proof. Here that
[I W)X --WUL = |1(1
W) UL)1
1 ULI =a -W (W- 1)2
The inoquality is due to Cauchy-Schwarz incquality. Then using the reverse triangle incquality, we have that
[I(T - WxX Xest
II(T - WyU S aaaa + 1)2.
C.4 Proofs for Corollary 4 Generalization Error
Corollary 4 (Generalization Error). Let Id- -N. Let the SVD of Xirn be UErrn VT.. let L U Xist By UTB, B, and d/N. Under our selup and Assumptions) 1 and g with the further assumplion that the cotumns of L are drawn IID from distribution with mean p and Covariance E, the test error (Equation 1 is given by the following.
IJ c
<
regime)
| 12m 1) pu47 )
Ey, [R( opt, UT)
Vern
Nist +
1-c Tr
c²
(30 (80
Eirm + 3
11)
1
(Iime
c Wima
+ )-2)))
1 N
d
45

---

Published in Transactions on Machine Learning Research (03/2024)
If c (ouer-paromettriized regime)
EL EL|R(Wopt opt, UL) = M/mm
3 + 1) + 14 )1/2)
Mest
| 11 N2
1 N
+
Tr(Su + - +
to
d c-1
Proof. We begin by noting that the variance term is independent of Xtst- Hence we only need to focus on the bias term. Let L == L [M p ji be the centered version of the test data matrix. In that case, E Ex,a, [I] Ex,,s, (UT xest,a] = and
Ex (LIF'= Ex... 10 Xest,e tst,
UJ
Nea
Now note the following elementary computation.
Ex,.,, Ext.,,(LLL') Ex.., [(L + 11 p))( + Iu ... 14)²1
Ex [LL"] + + 0 Nestp1
Neat Nestlup"
Consider the following sequence computations about the bias term.
Exx
E
Tern
1 c 1mm
Nest
Mira Tr (5 1) x... [T.T.' (( (imm))-1Bu)
Nest
Tern Tr (3) (Etrne c nern 1) + ) ) e + mern (0a
(oT'
Nist
Mirn
31 (E2 Thmn 1) 1) + uu T' 1/2
Nist
This establishes our claim.
C.5 Proof for Theorem 4 Test Error for W
Theorem 4 (Test Error for W*). In the same setting as Theorem we have that W
TT [+ Tie 2
U and
R(W* UL))
N2 N₂ d
87 E2 + Tern
-1
nest Tr +
[+
2 Bern.N Eerm
-2
d
d
Proof. To prove the first part of the theorem, we first note that
Mum N d
E [ WXern + Arrm) = (Yen
W WXemll
||
Solving this equivalent to solving
Vern 0] W [Xem nT] 112.
where 122 Ni,, We know from classical linear algebra that the solution to the above is
W [3 Xemm 0] [Nem an]t.
46

---

Published in Transactions on Machine Learning Research (03/2024)
Using Lemmas 5 and 6 from Sonthalia et al. (2023), have that if Xern UEern Vern where U is d by d, Eten is d by d and Venn is N x d, then
V (oi(M))))² + 2
0
07
0
Virn Etrn --17
[Xrm plj=U =U U
or Xtrn )2
+ 4ra
pV'- -1
0
μq
Thus, have that
Ven Etrn 5-17 uUE
W" = 18 Vir
0]
UT.
Vor(Xera 1+p
0
0
0
Simplifying, get
W' = BT 22
2-20
Irn
(Xmm))
(Xeen
de (Xmm p
= BT
UT
or (Xeex +
BT 2i brn
+ (22
-
D2gn + Mirn-
-1
Thrn N 5-2
-1
= BT [+
Hence we have finished proving the first part.
For the second part, we note that similar to before, we need to calculate
Wist ||**
EAn [[]Yese W' + Arse)] Nest
||Yest
W Xesel1
Nest
For the first term recall that X1st UL and Yist I Xest- Hence have that
Mrrn N
1
n N2
Dirm N
Yest Wa Xesell
3 T [ 1+
5-2
L
B
I.
Nest
Newt
Nest
d
47

---

Published in Transactions on Machine Learning Research (03/2024)
For the second term, we have that
Nist
Tist Tr d
-Vn
-2
N Mirn
W W
I+
Etrn
Br
Nist Tr
Br 1+
d 2
d
d
C.6 Proof for Corollary 2 Relative Excess Error
Corollary 2 (Relative Excess Error). Let |Etrall 2(N1/2+)) As d, - co with d/N - c, the relative ercess error lends to [-c in the underparametriza regime. In the overparametrized regime, when | = (N), it tends to c-1 and - + k for some constant k when || 1|3- O(N).
Proof. Recall from Theorem that the test error for W is given by
R(W", R(W*,UL)
Mirn N2 d²
Mern N B7 tirn + d 11)
L Thet
BBBBt [+
Mirn N 20
We prove this for > 1, the proof for e < is analogous and in fact simpler. Notice that when Eeen l1 ((N1/2+))) in both R(W opts Xist) and R(W", Xist), the bias terms are O(1/d while the variance terms are (L/d)), In particular, d, N + oc, with d/N + c, the limit of the excess risk given by only considering the variance terms and the estimation errors.
R(W opt: Xest) -R(W* Xest)
lim d.N-toc.d/N+ d/N-+c
R(W+XXesl
Boe Tr d
BB (I+ Dien
N S
-2)
Tie
d - Tr(BurBf(1
lim
d,N d/N-
TuuTr
BuusT (I
Been Imm
d
0 [Eern 13) 1 + (
lim
d.N d/N uf Tr Bu.ST [
Biny x vm? -2
Tr Pooft
(1+
Tim 2
-2) - - Tr 31 + nhr Emeii)))) -1)
lim
d.N L.N-toc,de d/N
Tr 3018 [I+ Timm Eir -2
0 (dlSemalli + (c)
lim
d.N d/
WesTr Tr (8u88 (T (T+
Whem E
-2
Tr (Bu
o-1 Tr(Bu,s)
0
cl Eim 1
N
+ o(1)
lim
lim
d.N LoNNoo,dNN--0
Tr (Be,3t)
m Tr (Bu.3))
|
=1
lim
0
d.N doo. +c
N
Etrn 11 =(NN)
+ b
Exrnli 112 ((V)
48

---

Published in Transactions on Machine Learning Research (03/2024)
for some unknown problem-dependent constant k. This establishes the claim for 1, and the proof for when e < is analogous and in fact simpler.
C.7 Proof for Corollary 6
Corollary 6 (IID Test Data). Let r < <N Let the SVD of Xtrn be UEtrn Vin let L == U Xests By := UU B, and c == d/N. Under our setup and Assumptions / and & with the further assumption that the columns of are drawm ITD from distribulion with mean zero and Covariance E, the test error (Equation) is given by the following.
If c <<
paadee--rrameeeriieeed regime)
Eg ((( opt, UL)] Mern (f c+ I) 1
Hitt
c²
Dino + _11
(Einec + vir!!) + N
d -
Vmm
If <>>> (over-purameterizedd regime)
Er[R[Wopt. UL) = Mtrn 1 + thrn ( 15112
Mist
| 13
1 to
+
d c-1 Tr(By + 2 11 +0
N2
N
Proof. Follows immediately from Corollary
C.8 Proofs for Theorem 6. IID Training Data With Isotropic Covariance
Theorem 6 (I..D. Training Data With Isotropic Covariance). Let d/N and c, = r/N. Then if c <
Ex,,, [
Thrn Nest
[ - 1) ->-
r 1
Ca(Cr,nern// + Telcr, vhrn +o Tern
1
+ Most d c
and c
E Exer [
Mten
(Eim
+ 1) LI + +hst de
Tyler, Tern +
N1st
where 21(cr, = (cr,
=TT 2), and
+ Gr + zCr
26, v(1 Gr + 20,)2 + 4e22
Tz(cr,2)= 21 (1 22 4c72
2' Ts(c,, 2) = + 2
2cr
Proof. Then if Xmm is the data matrix, the singular values squared for Xtrn are the cigenvalues of X zTuTuz=
Then Z is a x N matrix, and due to the normalization of the variance of the entries, this is a Wishart Matrix. Further, we know that the eigenvalue distribution can be approximated by the Marchenko Pastur
distribution with shape parameter r/N Marcenko & Pastur 1967 Götze & Tikhomirov 2011 2003 2004
2005 Bai al. 2003)..
Then we have that for the < 1 case, we have the variance is
Σ c² d - 1=1
c
of
1 of + orn (of + o
(of + 20)
49

---

Published in Transactions on Machine Learning Research (03/2024)
Then we simplify this the following.
r 1
of
1
o +
R
+
B
d c(1 c)
(o
c)2
(o
irn
If À is an eigenvalue of the training data gram matrix, then the variance term of the generalization error has terms of the following form.
X
A
(A+ 1/c)2 AA+1/af A+1
The value of these for the Marchenko Pastur distribution can be found in Sonthalia et al. 2023
À
1 Crn v(1 Gr + T C,
4c2
E
M
2c,
1+ Cr + Mire
E
+011)
+
+ Mern )2
2/(1
Cr crrlern) ) 4c7
2
X²
E
E
Vtrn
E
(A
Vern!
A Bern
2
G = r//N
The proofs for the rest of the terms are similar.
C.9 Proofs for Corollary 7 IID Training and Test Data With Isotropic Covariance
Corollary 7 (L.LD. Train and Tests Data With Isotropic Covariance). Let d/N and Gr = r/N. Then if
e<1
Ex.., [R] = Vtrn - Ti Rtm/
Ti(cr, +
1 T2(cr, vimnle) +o
+
1
Thrn
N
and if c
1
Ex... R
Mtrn r
Ta(Cr, Whrn) + de
Tolcr, (ern +
N
where 21(Gr = -Ts(cr, 2) (Cr 2), and
1 c, + 2Cr
1 20,
(11
G, 20, )2
1c
T2(c,,z)= = 21 Cr 222)2 2 + 46,2
2 2a(c,;2)= =
2c,
20 c 2C, 20, +
1- 1111
Ta(or,))
2x²c, /
cr + c2 1022
2x
Cr
Proof. For the bias, we get
Dern Nest
|
c²
Co? + h
The value of these for the Marchenko Pastur distribution can be found in Southalia et al. (2023)
Mern c4 + c + 12 2cr +
1- 1
E
(A 11mm )2
2 Cr Ani c. + (1 Cr + nhr
2m
Gr
50

---

Published in Transactions on Machine Learning Research (03/2024)
D Numerical Details
In this section, we include the computational details required to reproduce the data and figures in the paper. The code for the experiments can be found in the following anonymized repository Link
Data For our transfer learning results, we use real datasets namely CIFAR Krizhevsky (009), STL10 Coates et al. (2011) and SVHN Netzer et al. (2011). We will mostly be working with the training and test split of CIFAR, training split of STL10 and training split. of SVHN. We will also use the test split of STL10
for our data augmentation results, refer figure 7h and section D.3 to avoid overlaps between training and test data.
To verify the application of our results to I.I.D. data, we generate datasets from certain distributions, the details of which are presented in the upcoming sections.
The test data normalized so that each coordinate has mean zero and standard deviation of This is done before we do any other pre-processing.
Compute Time For figures 2 1 and g use the same training data from CIFAR train split. Thus, we combine our code implementation for these figures. This saves up compute time for mean empirical error since inversion of the matrix Xtrn + A for obtaining Wapt, occurs once for each empirical run for all 4 figures. The code was implemented using Google Colab with A100 Nvidia GPU which took approximately hour for the 200 trials for cach value of Since the results are computed for 4 values of r, the entire experiment was completed within approximately 4 hours.
Figures 7 and 7h took approximately 4 hours each using A100 Nvidia GPU on Google Colab. Figures 5 and G were computed together in approximately 40 minutes. Figure 10 took approximately 1 hour to compute. only took around 10 minutes due to less number of N values and only 50 trials. All the above was implemented using A100 GPU on Colab. Figure 2c took approximately 4.5 hours using T4 Nvidia GPU on
Figure I
Google Colab.
D.1 Principal Component Regression
We use four datasets for the set of results obtained through principal component regression namely, CIFAR train split, CIFAR test split, STL10 dataset and SVHN dataset.
In-Subspace For figure 2a] the test data lies in the same low-dimensional subspace as the training dataset. The experimental setting is as follows.
Training data, of order d x N, is sampled from flattened CTFAR train split such that d = 3072 and N ranges between 1050 and 10500 with an increment of 550 for the results.
We project our training data over the first r principal components where r refers to the rank and varies as 25, 50, 100 and 150.
Test datasets, of order d Nist, are sampled from CIFAR test split, STL10 train split and SVHN train split where d = 3072 and Nest 2500.
We also project these test datasets onto the low-dimensional subspace using the projection matrices. For denoising, we generate Gaussian noise matrix Atm with norm VN for the training data and A with norm VNeat for the test datasets.
The theoretical error is calculated using the formula in Theorem [ and the empirical error is the mean squared error.
Out-of-Subspace Next, we Lest our formulas for test datasets which lie outside the training distribution space.
Small a We detail the numerical setup required to generate figure 2b
Training data, of order d x N, is sampled from flattened CIFAR train split such that d = 3072 and N ranges between 1050 and 10500 with an increment of 550 for the results.
We project our training data over the first r principal components where refers to the rank and varies 25, 50, 100 and 150.
51

---

Published in Transactions on Machine Learning Research (03/2024)
Test datasets, of order d Ntat, are sampled from CIFAR test split, STL10 train split and SVHN train split where d = 3072 and Nist 2500.
We project these test datasets onto the low-dimensional subspace using the projection matrices. We add a small amount of full-dimensional Gaussian noise to the projected datascts to generate out-of- subspace datasets with small a. Here, we consider the case where 0.1.
For denoising, we generate Gaussian noise matrix Atr with norm vN for the training data and Asst with norm Visat for the test datasets.
The empirical error shown in figure 2b is the square root of the mean squared error. The theoretical bounds on the error are calculated using Theorem 2
Large a. For figure S the experimental setup is as follows.
Training data, of order d x N, is sampled from flattened CIFAR train split such that d 3072 and N ranges between 1050 and 10500 with an increment of 550 for the results.
We project our training data over the first principal components where refers to the rank and varies 25, 50, 100 and 150.
Test datasets, of order d x Neat are sampled from CIFAR test split, STL10 train split and SVHN train split where d = 3072 and Nest = 2500.
We do not project these test datasets onto the low-dimensional subspace. We retain their high dimensions.
The values of a for different values are provided in figure g
For denoising, we generate Gaussian noise matrix Air with norm VN for the training data and Alst with VNeae for the test datasets.
D.2 Linear Regression
To consider the linear regression case for figure !
Training data, of order d x N, is sampled from flattened CIFAR train split such that d = 3072 and N ranges between 1050 and 10500 with an increment of 550 for the results.
We project our training data over the first r principal components where r refers to the rank and varies as 25, 50, 100 and 150.
Gaussian noise matrix with norm VN is added to the training data.
We generate
Sopt of order d x 1 with norm 1. The learned estimator is computed as 3 = S W where W is the minimum norm solution to the least squares denoising problem. For theoretical error, we compute 3T = U.
Test datasets, of order d Nest; are sampled from CIFAR test split, STL10 train split and SVHN train split where d = 3072 and Ni.: 2500.
We also project these test datasets onto the low-dimensional subspace using the projection matrices.
Gaussian noise matrix with norm VNeat is added to the test datasets.
Finally, the test datasets, Xest, are replaced with 3T Xtst to compute the error for the linear regression problem.
D.3 Data Augmentation
To emphasize the application our results to non-L.LD, data, we consider two cases of data augmentation to our training data.
Without Independence
The experimental setting to obtain the empirical generalization error is as follows. We sample 1000 images from the CIFAR train split as the first batch of our training data. For experimental results
We augment the above batch with the same batch to vary N between 1000 and 6000 with an increment of 1000. We project the dataset onto its first r principal components where r = 25, 50, 100 and 150.
We add gaussian noise with norm / the training data as before. Note that the noise on augmented batches would be independent of the noise the original batch. This is the only assumption required for result.
52

---

Published in Transactions on Machine Learning Research (03/2024)
Test datasets, of order d x Nist, sampled from CIFAR test split, STL10 train split and SVHN train split where d = 3072 and Nist = 2500 are also projected onto the low-dimensional subspace.
We calculate the theoretical generalization error for more values of e to obtain smoother curves. Note that the left singular vectors i.c., the columns of matrix U, do not change when we augment our training batches. We utilize this to speed-up our computation for theoretical curves.
We sample 1000 images from the CIFAR train split as the first batch of our training data. We obtain the projection matrix P = UU and the matrix L U Xtst from the SVD of the first batch itself.
The generalization error is computed from the formula in Theorem | for values of N between 1000 and 6000 with an increment of 50.
We scale the singular values by a factor of N/2000 to account for the augmenting.
Without Identicality To generate figure 7h
We use training data, of order d x N,, such that d 3072 and N ranges between 1050 and 10500 with increment of 550 for the results.
We use N/2 images from the CIFAR training split and N/2 images from the STL10 training split concatenated logether for our training data.
We project our training data over the first r principal components where r refers to the rank and varies as 25, 50, 100 and 150.
Test datasets, of order d x Nist are sampled from CIFAR test split, STL10 test split and SVHN train split where d = 3072 and Nest 2500. This is done avoid any overlaps between training and test data.
We also project these test datasets onto the low-dimensional subspace using the projection matrices.
For denoising, we generate Gaussian noise matrix Atrn with norm /N for the training data and Alst with norm /Nest for the test datasets.
D.4
I.I.D. Data
We also perform experiments to verify our results in cases where training and test datasets are L.I.D The numerical details for those experiments are presented in this section.
I.I... Test Data To generate figure
Training data, of order d x N, is sampled from flattened CIFAR train split such that d = 3072 and N ranges between 1050 and 10500 with increment of 550 for the results.
We project our training data over the first r principal components where refers to the rank and varies 25, 50, 100 and 150.
We generate L from Gaussian distribution of norm Vist where Neat = 2500.
We obtain our I.LD. test data of order x Nis as Xtst = UL where contains the left singular vectors of the projected training data.
For denoising, we generate Gaussian noise matrix Aum with norm VN for the training data and Aust with norm VNist for the test datasets.
I.I.D. Train Data To generate figure 10
We generate the left singular matrix U from the SVD of a Gaussian matrix of order d x r where M = 3072 and r= 50.
We generate the training matrix Xern UZ where Z of order r x N such that cach column is normally distributed with mean 0 and variance 1/r.
Here, N varies from 1050 to 10500 with increment of 550.
Test datasets, of order d Ntst, are sampled from CIFAR test split, STL10 train split and SVHN train split where d = 3072 and Nist = 2500.
We also project these test datasets onto the v-dimensional subspace using projection matrices.
For denoising, we generate Gaussian noise matrix Arn with norm VN for the training data and Aest with norm VNest for the test datasets.
LLI.D Train and Test Data To generate figure
53

---

Published in Transactions on Machine Learning Research (03/2024)
We generate the left singular matrix U from the SVD of a Gaussian matrix of order d x where M 3072 and r= 50.
We generate the training matrix Xtrn UZ where Z is of order r x N such that each column is normally distributed with mean 0 and variance 1/r.
Here, N varies from 500 6010 with an increment 550 for the empirical markers and with an increment of 55 for theoretical values on the solid curve.
We generate L from Gaussian distribution of norm Visat where Nest 5000.
We obtain our L.D.. test data of order d x Nist Xtst UL where U contains the left singular vectors of the projected training data. For demoising, we generate Gaussian noise matrix Atr with norm vN for the training data and Aise with norm VNtst for the Lest datasets.
D.5 Full Dimensional Denoising
To generate figure 2c
Training data, of order d x N, is sampled from flattened CIFAR train split such that d = 3072 and ranges between 1050 and 10500 with an increment 550 for the results.
We project our training data over the first r principal components where is the minimum of and N.
This implies that the data is full dimensional.
Test datasets, of order d Ntat, sampled from CIFAR test split, STL10 train split and SVHN train split where d = 3072 and Nist 2500.
We also project these test datasets onto the low-dimensional subspace using the projection matrices.
For denoising, we generate Gaussian noise matrix Atr with norm vN for the training data and Arst with norm /Neat for the test datasets.
D.6 Optimal 7)r
To generate figures 5 and 6
Training data, of order d x N, is sampled from flattened CIFAR train split such that d = 3072 and ranges between 500 and 5500 {500, 750, 1000, 1250, 1500, 1750, 2000, 2250, 2500, 2600, 2700, 2800, 2900, 3000, 3020, 3130, 3200, 3300, 3400, 3500, 3750, 4000, 4250, 4500, 4750, 5000, 5250, 5500}.
We project training data over the first principal components where
50.
Test datasets, of order d x Nest, are the training dataset with new noise and sampled from CIFAR test split, STL10 train split and SVHN train split where d = 3072 and Nist = N.
We compute generalization error for 2000 Men values ranging from 1/3.5 to 100 for each N from our formula in Theorem |
We report the optimal 1tm found to minimise the generalization error figure 5 and the optimal generalization error in figure
54


Reviews:
[{"review_id": "z1JEq1SxNs", "reviewer": "Reviewer_5Zxt", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Weakness: \nMy main concern is the wording of the claims. In the abstract and the introduction, the authors are trying to claim that they obtain a very strong bound with relaxed conditions (even without iid assumption) and the results are also verified by real-data experiment, but never mention wordings like \"data-dependent\". When reading these parts, I was surprised at their result. \n\nHowever, after reading the main theorems, I realized that they are able to relax some strong distributional conditions because they directly put the data matrix into the bound. It then becomes much less surprising: when people add distributional assumptions, they actually try to remove the data-dependent terms from their error bound. For example, in Hastie et. al. (2021), when deriving the asymptotic formula of tr(Xn^{\\top}Xn) (Xn is the data matrix), they start from data-dependent representation tr(Xn^{\\top}Xn).\n\nThe authors are strongly suggested to rewrite their abstract and introduction to help readers build a more concrete expectation on this paper.\n\nStrengths:\nWhile the weakness mentioned above makes the reading experience less pleasant, the paper still provides solid theoretical contributions. The derivations are non-trivial, and the assumptions are relaxed to the best. The technical sections are clear and easy to understand.\n\nHastie, Trevor, et al. \"Surprises in high-dimensional ridgeless least squares interpolation.\" Annals of statistics 50.2 (2022): 949.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the data-dependent generalization bound for low-rank regression problem. While relaxing some conditions in the theorems, they also conduct numerical experiments of real data to verify the correctness of the theoretical results.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the weakness section. I also selected \"No\" in Claims and Evidence because the descriptions of the contributions are inaccurate.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "3ouxRXMmQY", "reviewer": "Reviewer_3dcE", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\nThe setting of *noisy* data but noiseless labels is relatively rarely studied in the literature. The role of noise in the data has not been well understood. It is an interesting topic to theoretically analyze the effect of data noise, including its effect on the test error/loss as discussed in this paper.\n\nThe test error bound exhibits a perfect double descent curve. It is also well matched by numerical verification on some real data. \n\nThe observation of the data noise having a regularization effect is interesting.\n\nWeaknesses:\n\nThe analysis is limited to the very simple linear regression problem. It remains unclear in non-linear problems. The analysis techniques seem not to extend to more complicated problems.\n\nThe title of the paper should be more precise to reflect the setting of linear regression.\n\nThe assumption of data in a low-dimensional subspace seems too strong. It is believable that the data lies in a low-dimensional *manifold*, but I don’t see any reason to restrict the data to a subspace (it is much stronger to let the manifold to be “straight”).\n\nQuestions:\n\nAs discussed in the beginning of Page 13, minimizing the MSE error itself may have the effect of regularizing the weights $||W||_F$. In addition, in the optimization problem (first equation of page 4) there is also an explicit minimization of $||W||_F$ after minimizing the MSE error. I am wondering: is it necessary to have the latter minimization (as in page 4)? What is the relation between these two types of regularization of weights? Or more precisely, does the regularization effect of noise (as discussed in page 13) really have any impact on the analysis, as the minimization of $||W||_F$ (in page 4) already had the effect?\n\nWhat is the technical novelty of this paper when compared with the paper “Benign overfitting in linear regression” (by Bartlett et al)?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper provides a theoretical upper bound on the test error of linear regression problems in the scenario of noisy data but noiseless labels. The curve of the upper bound shows a double-descent-like shape. The paper also provides numerical verification on the test error bound, as well as some insights on the role of data noise and data augmentation.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See \"weaknesses\" and \"questions\"", "broader_impact_concerns": "no concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "0FPWVC1Nez", "reviewer": "Reviewer_brba", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper clearly presents the mathematical formulations of different problems and their required assumptions, with detailed discussions and related work comparisons. The proposed theoretical framework is general and seems applicable to a broad family of denoising and regression problems. Under distribution shifts, the paper proves the generalization error bound and how it implies the double descent phenomenon. The paper mainly focuses on theoretical topics but also provides experimental results on image benchmark datasets to verify their theoretical findings.\n\nAlthough I can see a connection between regression tasks and denoising tasks, why they can be unified in a single framework requires further clarification. While reading the paper, I sometimes find it difficult to switch between regression and denoising tasks, as they are motivated from different perspectives and applied to different applications. In particular, for linear regression tasks, it is typical to consider that arbitrary or structured noises corrupt the outputs. However, you mainly focus on the setting with noisy inputs but clean outputs, so I'd like to know whether this setting is worth studying for regression tasks. For denoising tasks, it needs to be clarified why we should restrict the relationship between the noisy inputs and their clean counterparts to be linear. \n\nMoreover, I have the following questions about the imposed assumptions and theoretical results. Regarding the low-rank condition of the data under distribution shift scenarios specified in Assumption 1, it is unclear why the training data and testing data should share the same (or almost similar) linear subspace. In addition, the last condition specified regarding noise requires $d/N = c + o(1)$ as $N$ grows, whereas $d$ is usually a constant for real-world denoising tasks. So, I’m not sure if this is a realistic assumption for modeling the noises. For the theoretical results presented in Theorem 2 and Theorem 3, I fail to understand why they imply a double descent phenomenon. Can you elaborate further?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the machine-learning problem of supervised denoising and noisy-input regression under distribution shifts. Based on a couple of assumptions about the training/testing data distributions (e.g., low-rank) and noise distributions (e.g., Marchenko-Pastur distribution), the paper presents a sequence of theoretical results regarding the generalization error bound. Empirically, the paper demonstrates the double-descent phenomenon on image denoising tasks using benchmark datasets, which verifies their theoretical results when there is a distribution shift.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Clarify why assuming noisy inputs and clean outputs for regression tasks.\n\n2. Clarify why restricting to linear relationship for denoising tasks.\n\n3. Provide clarifications to my questions related to the imposed assumptions and theoretical results.\n\n4. Minor concerns about presentations: The theoretical results are not easy to parse - it would be helpful to provide more intuitive (informal) statements of your main theoretical results for better understanding.\n\n5. A typo: On page 3, there is a question mark.", "broader_impact_concerns": "No ethical concerns since the paper is mainly theoretical.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers seem to agree that the theoretical contributions are solid and correct: [5Zxt: the paper still provides solid theoretical contributions. The derivations are non-trivial, and the assumptions are relaxed to the best], and that the theory is clear and easy to follow: [brba: The paper clearly presents the mathematical formulations of different problems and their required assumptions] [5Zxt: The technical sections are clear and easy to understand].

The main criticism was about the limitations of the framework (linear denoisers, etc). Reviewers [brba,5Zxt] requested the authors to make these limitations more explicit in the paper, especially in the abstract and introduction. The authors updated the paper accordingly. Ultimately, [5Zxt] and [3dcE] recommended to accept the paper, but [brba] was still in favor of rejection because of these limitations. To be honest, while I share the opinion that there are strong restrictions in the applicability of these results, one must also note that this is the case of most papers studying the theoretical aspects of benign overfitting: most are in the framework of linear regression or 2-layers neural network. The theory is of course far to be able to explain the double descent phenomenon in very complex models. Yet, these papers shine a new light on the tradeoffs in high-dimensional machine learning, and this paper extends on existing works in various relevant directions (non iid data, distribuction shift, etc.). Thus, I support its publication in TMLR.

Note that [brba] actually mentioned he/she would not oppose publication, on the condition that the authors would add more discussions on the limitations of their theoretical findings, I suggest to respect the reviewer's opinion here. The authors could maybe mention what would be desirable extensions of their results to deal with more realistic settings (non-linear denoisers, see also the comment by [3dcE] that the data might be in a low-dimensional manifold, not necessarily a subspace, etc.). Also, I note that the authors discuss extensively the existing literature on benign overfitting in the iid case, but they missed an earlier work on time-dependent observations: Nakakita and Imaizumi, Benign Overfitting in Time Series Linear Model with Over-Parameterization, https://arxiv.org/abs/2204.08369. The nature of the dependence seems different in Nakakita and Imaizumi's paper, so it should not remove any novelty from this submission, but this should be discussed by the authors. Thus, I will request a minor revision before publication.
Decision: Accept (poster)