# Double Descent and Overfitting under Noisy Inputs and Distribution Shift for
Linear Denoisers

Chinmaya Kausik<EMAIL_ADDRESS>
Department of Mathematics
University of Michigan, Ann Arbor Kashvi Srivastava<EMAIL_ADDRESS>
Department of Mathematics
University of Michigan, Ann Arbor Rishi Sonthalia<EMAIL_ADDRESS>
Department of Mathematics
UCLA

###### 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 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.

##  1 Introduction

Denoising and noisy-input problems have a 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 as a regularizer has led to denoising being tied to many areas of modern
machine learning, such as pretraining and feature extraction (Krizhevsky et
al., 2012), data-augmentation for representation learning Chen et al. (2020),
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 in prior theoretical work (Baldi & Hornik, 1989),
supervised methods like denoising autoencoders are theoretically less well-
understood.

One of the biggest practical qualms to studying a supervised setting is that a
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 noiseless 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 a low dimensional space. In
fact, past work (Udell & Townsend, 2019) has demonstrated that a lot of real-
life data is approximately low-rank – that is, its covariance matrix only has
a few significant eigenvalues.

In this paper we look at the following error in variables regression task
(Hirshberg, 2021). Let $X_{trn}\in\mathbb{R}^{d\times N}$ be a noiseless data
matrix of $N$ samples in $d$ dimensional space. Let
$\beta\in\mathbb{R}^{d\times k}$ be a target multivariate linear regressor,
and let $Y_{trn}=\beta^{T}X_{trn}$. Note that when $\beta=I$, our target is
the noiseless data $X_{trn}$ itself. Let $A_{trn}\in\mathbb{R}^{d\times N}$ be
a $d\times N$ noise matrix. For this paper, we assume that we have access to
$Y_{trn}$ and $X_{trn}+A_{trn}$ while training. The goal is to study the test
error of the minimum norm linear function $W_{opt}$ that minimizes the MSE
training 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 $W_{opt}$ below.

$W_{opt}=\operatorname*{arg\,min}_{W}\left\\{\|W\|_{F}^{2}\middle|W\in\operatorname*{arg\,min}_{W}\|Y_{trn}-W(X_{trn}+A_{trn})\|_{F}^{2}\right\\}$

Given test data $X_{tst}\in\mathbb{R}^{d\times N_{tst}}$ and
$Y_{tst}=\beta^{T}X_{tst}$, we formally define the test error for arbitrary
linear functions $W$ by $\mathcal{R}(W,X_{tst})$ below. Since we are not
assuming anything about the distribution of the training or test data, we only
take the expectation over the training and test noise. The error is dependent
on the specific $X_{trn}$ and $X_{tst}$ that are given.

$\begin{split}\mathcal{R}(W,X_{tst}):=\mathbb{E}_{A_{trn},A_{tst}}\left[\frac{\|Y_{tst}-W(X_{tst}+A_{tst})\|_{F}^{2}}{N_{tst}}\right].\end{split}$
(1)

The classical theory of learning problems would keep the data dimension $d$
fixed and lets the number of samples $N$ grow to $\infty$. These can be
theoretically analysed using elementary tools. However, with growing access to
computational power and richness of data, it has become important to study
non-classical regimes. One important and popular example is the proportional
regime, where $d\propto N$ and so $d$ is comparable to N. Phenomena like
double-descent and benign overfitting discovered in noiseless-input settings
demonstrate the surprising 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 (Mallinar 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 is 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 a growing need to be robust to adversarially
chosen data in machine learning (Kotyan, 2023). We would thus like to drop the
assumption that the data is IID or even independent. However, to account for
this, we would need to have data-dependent theoretical results. We thus aim to
address the following question:

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 we obtain from these?

##### Contributions.

The major contributions of the paper are as follows.

  1. 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.

  2. Q.1 (b)

(Dropping Independence Assumptions, Arbitrary Test Data) We do not assume that
the training data is IID or 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 test data as well as the alignment between their left
singular vectors.

  3. Q.1 (c)

(Experiments using Real-Life Like Data) We have a relative error of under 1%
in experiments using real-life like data, establishing that our theoretical
results can be used with data similar to real data.111The code for the
experiments can be found in the following anonymized repository [Link].

  4. 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.

  5. 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 3 discusses our main theoretical results for the denoising
problem as well as experiments verifying these results. Section 4 discusses
insights obtained from these results for double descent, data augmentation,
and overfitting paradigms.

##### Denoising.

Significant work has also been done to understand the role of noise as a
regularizer and its impact on generalization (Bishop, 1995; Camuto et 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 & Miolane, 2017; Lesieur et al.,
2017; Maillard et al., 2022; 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, we continue the
study of understanding supervised denoising from the lens of test error._

##### Theoretical Work on Generalization in Non-Classical Regimes.

There has been significant work in understanding the generalization error and
benign overfitting. Most prior work looks at the case where
$x\sim\mathcal{D}$, for some data distribution $\mathcal{D}$ and we have
$y=\beta_{*}^{T}x+\xi$ where $\xi\sim\mathcal{N}(0,\tau^{2})$. The following
least squares problem is commonly considered

$\beta_{opt}=\operatorname*{arg\,min}_{\beta}\left\\{\|\hat{\beta}\|_{F}^{2}\middle|\hat{\beta}\in\operatorname*{arg\,min}_{\hat{\beta}}\|Y_{trn}-\Xi_{trn}+\hat{\beta}^{T}X_{trn}\|_{F}^{2}\right\\}$

The above setting was analyzed in Dobriban & Wager (2018); Mel & Ganguli
(2021); Muthukumar et al. (2019); Bartlett et al. (2020); Belkin et al.
(2020); Derezinski et al. (2020); Hastie et al. (2022); Loureiro et al.
(2021b). The version for kernelized regression was studied in Mei et al.
(2022); Mei & Montanari (2021); Mei et al. (2018); Tripuraneni et al. (2021a);
Gerace et al. (2020); Woodworth et al. (2020); Loureiro et al. (2021a);
Ghorbani et al. (2019; 2020).

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 $x$ 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 on
real data. These works use a 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 errors in non-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 high-dimensional regime tests on real data
Paquette et al. (2022); Loureiro et al. (2021b; a); Wei et al. (2022).
Loureiro et al. (2021b) assumes that the data distribution is given by a
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.

##### OOD Generalization and Distribution Shift.

Empirically, studies such as Miller et al. (2021); Recht et al. (2019); Miller
et al. (2020); McCoy et al. (2020) have noticed that there is a strong linear
correlation between in-distribution accuracy and out-of-distribution accuracy.
There has been some theoretical work (Tripuraneni et al., 2021a; b; 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; Lei 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 on some
measure of distance between the two distributions. We provide instance-
specific results that depend on the data.

##### Double Descent and Implicit Regularization.

The generalization 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 theoretical
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; b). 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.

##### Limitations

While we do make progress, our work still has limitations. The first is that
the theory needs exactly low rank data. This is not quite true for real data,
which is only _approximately_ low rank or lives in some non-linear low
dimensional space. Another limitation is our theoretical result for the over-
parameterized regime has non-trivial error only if one assumes that
$\|X_{trn}\|_{F}^{2}=o(N_{trn})$. That is, the norm of the data points must
decay as $N_{trn}$ grows. This is not a concern for many prior works (Hastie
et al., 2022; Bartlett et al., 2020; Cheng & Montanari, 2022). However, we
study the problem in a different setup. Another limitation is the simplicity
of the model. Prior work such as Cui & Zdeborová (2023) have results, for
different data assumptions, but more general models. We study the problem for
significantly different data assumptions.

##  2 Problem Setup and Notation

Recall the problem setup. Let $X_{trn}\in\mathbb{R}^{d\times N}$ be a
noiseless data matrix of $N$ samples in $d$ dimensional space. Let
$\beta\in\mathbb{R}^{d\times k}$ be a target multivariate linear regressor,
and let $Y_{trn}=\beta^{T}X_{trn}$. Note that when $\beta=I$, our target is
the noiseless data $X_{trn}$ itself. Let $A_{trn}\in\mathbb{R}^{d\times N}$ be
a $d\times N$ noise matrix. For this paper, we assume that we have access to
$Y_{trn}$ and $X_{trn}+A_{trn}$ while training. We then solve the following
problem.

$W_{opt}=\operatorname*{arg\,min}_{W}\left\\{\|W\|_{F}^{2}\middle|W\in\operatorname*{arg\,min}_{W}\|Y_{trn}-W(X_{trn}+A_{trn})\|_{F}^{2}\right\\}$

Given test data $X_{tst}\in\mathbb{R}^{d\times N_{tst}}$ and
$Y_{tst}=\beta^{T}X_{tst}$, we have the following test error.

$\begin{split}\mathcal{R}(W,X_{tst}):=\mathbb{E}_{A_{trn},A_{tst}}\left[\frac{\|Y_{tst}-W(X_{tst}+A_{tst})\|_{F}^{2}}{N_{tst}}\right].\end{split}$

We would like to study the test error $\mathcal{R}(W_{opt},X_{tst})$ of
$W_{opt}$ in terms of properties of the data matrices $X_{trn}$ and $X_{tst}$
as well as the noise distributions. 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 noiseless
inputs $X$, while we consider the case where we have noisy inputs $X$. For
simplicity, we assume access to noiseless outputs $Y$. It is easy to see from
elementary linear algebra that $W_{opt}=Y_{trn}(X_{trn}+A_{trn})^{\dagger}$.
Notice that when $\beta=I$, we are studying the linear denoising problem, and
when $\beta\in\mathbb{R}^{d}$, we are studying real-valued regression with
noisy inputs. We work in the proportional regime, where $d/N=c+o(1)$ as $N$
grows, for some constant $c>0$. Notice that we are not _in_ the limit
$N\to\infty$; 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 $X_{trn}\in\mathbb{R}^{d\times N}$ and
$X_{tst}\in\mathbb{R}^{d\times N_{tst}}$ so that

  1. 1.

Low-rank: There is a fixed $r>0$ so that $X_{trn}$ and $X_{tst}$ have data-
points lying in an $r$-dimensional subspace
$\mathcal{V}\subset\mathbb{R}^{d}$, and the column span of $X_{trn}$ is
$\mathcal{V}$.

  2. 2.

Data growth: $\|X_{trn}\|_{F}^{2}=O(N)$.

  3. 3.

Low-rank well-conditioning: For the $r$ singular values $\sigma_{i}$ of
$X_{trn}$, $\frac{\sigma_{j}}{\sigma_{i}}=\Theta(1)$ and
$\frac{1}{\sigma_{i}}=o(1)$ as $N$ grows, for any $i,j$.

Notice that we don’t assume that $X_{trn}$ is IID or even independent, and
$X_{tst}$ is completely arbitrary, besides lying in the subspace
$\mathcal{V}$. In our results, we will characterize the dependence of the
error on $X_{trn}$ and $X_{tst}$ 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 $X_{trn}=U\Sigma_{trn}V_{trn}^{T}$
be the SVD of $X_{trn}$ with $U\in\mathbb{R}^{d\times r}$,
$\Sigma_{trn}\in\mathbb{R}^{r\times r}$ and $V_{trn}^{T}\in\mathbb{R}^{r\times
N}$. Note that the columns of $U$ span $\mathcal{V}$. Then there exists a
matrix $L$ such that $X_{tst}=UL$. For Theorem 2, we will relax our assumption
on $X_{tst}$ to say that there exists $L$ and $\alpha>0$ so that
$\|X_{tst}-UL\|<\alpha$.

##### Comparison with assumptions in prior work.

Most prior works on theoretical regression assume that the data comes from a
Gaussian or Gaussian-like distribution. Specifically, Tripuraneni et 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 $x\sim\mathcal{N}(0,\Sigma)$. Most real data cannot be
modeled as Gaussian data. Another common assumption is that $x=\Sigma^{1/2}z$
where the coordinates of $z$ are independent, centered, and have a variance of
1. This setting is a little bit more general than the previous setting. The
independence of data is still a limiting assumption that prevents it from
modeling real-life data well. In addition, as the dimension increases, due to
the (Lyapunov’s) central limit theorem, the data’s higher moments tend towards
those of a Gaussian distribution again. This makes this assumption nearly as
limiting as the first one. Papers with this (or very similar) assumption
include Wu & Xu (2020); Bartlett et al. (2020); Hastie et 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 a very different low-rank setting 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-Pastur distribution with shape $c$,
for completeness.

######  Definition 1.

Let $c\in(0,\infty)$ be a shape paramter. Then the Marchenko-Pastur
distribution with shape $c$ is the measure $\mu_{c}$ supported on
$[c_{-},c_{+}]$, where $c_{\pm}=(1\pm\sqrt{c})^{2}$ is such that

$\mu_{c}=\begin{cases}\left(1-\frac{1}{c}\right)\delta_{0}+\nu&c>1\\\
\nu&c\leq 1\end{cases}$

where $\nu$ has density $d\nu(x)=\frac{1}{2\pi xc}\sqrt{(c_{+}-x)(x-c_{-})}.$

Our assumptions on noise are fairly natural and general. Informally, we
require the training noise to (1) have finite second moments, (2) be
uncorrelated across entries, (3) be isotropic, and (4) follow a 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 1 of (Sonthalia & Nadakuditi, 2023)). One
of 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 $A_{trn},A_{tst}\in\mathbb{R}^{d\times
N}$ be sampled from distributions $\mathcal{D}_{trn}$ and $\mathcal{D}_{tst}$
such that $A_{trn}$ satisfies points $1-4$ below and $A_{tst}$ satisfies
points $1,2$.

  1. 1.

For all $i,j$, $\mathbb{E}_{\mathcal{D}}[A_{ij}]=0$, and
$\mathbb{E}_{\mathcal{D}}[A_{ij}^{2}]=\eta^{2}/d$. Here $\eta=\Theta(1)$ as
$N$ grows.

  2. 2.

For all $\\{i_{1},j_{1}\\}\neq\\{i_{2},j_{2}\\}$,
$\mathbb{E}_{\mathcal{D}}[A_{i_{1}j_{1}}A_{i_{2}j_{2}}]=\mathbb{E}_{\mathcal{D}}[A_{i_{1}j_{1}}]\mathbb{E}_{\mathcal{D}}[A_{i_{2}j_{2}}]$.

  3. 3.

$\mathcal{D}$ is a rotationally bi-invariant distribution222A distribution
over matrices $A\in\mathbb{R}^{m\times n}$ is rotationally bi-invariant if for
all orthogonal $U_{1}\in\mathbb{R}^{m\times m}$ and all orthogonal
$U_{2}\in\mathbb{R}^{n\times n}$, $U_{1}AU_{2}$ has the same distribution as
$A$. Another way to phrase rotational bi-invariance is if the SVD of $A$ is
given by $A=U_{A}\Sigma_{A}V_{A}^{T}$, then $U_{A}$ and $V_{A}$ are uniformly
random orthogonal matrices and are independent of $\Sigma_{A}$ and each other.
and $A\sim\mathcal{D}$ is full rank with probability one.

  4. 4.

Suppose $A^{d,N}$ is a sequence of matrices such that with $d/N=c+o(1)$ as $N$
grows, for $c>0$. Let $\lambda_{1}^{d,N},\ldots,\lambda_{N}^{d,N}$ be the
eigenvalues of $(A^{d,N})^{T}A^{d,N}$. Let
$\mu_{d,N}=\sum_{i}\delta_{\lambda_{i}^{d,N}}$ be the sum of dirac delta
measures for the eigenvalues. Then we shall assume that $\mu_{d,N}$ converges
weakly in probability to the Marchenko-Pastur measure with shape c as $N$
grows.

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. (2021) is more general than ours. Pretorius et 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 a 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 a linear model _overparametrized_ if $d>N$ and _underparametrized_ if
$d<N$.

  * •

_In-subspace_ distributions refer to test data distributions whose support is
in $\mathcal{V}$, while _out-of-subspace_ distributions are test data
distributions whose support is not contained in $\mathcal{V}$.

  * •

A curve exhibits _double descent_ if it has a local maximum or a peak.

  * •

By _test error_ we mean $\mathcal{R}(W_{opt},X_{tst})$, and by _generalization
error_ we mean $\mathbb{E}_{X_{tst}}[\mathcal{R}(W_{opt},X_{tst})]$, assuming
that $X_{tst}$ 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 a reasonable generalization of
overfitting paradigms (benign, tempered and catastrophic, see Mallinar et al.
(2022)) to our setting. Consider the minimum norm denoiser that minimizes
expected MSE training error, similar in spirit to $\theta^{*}$ in Bartlett et
al. (2020).

$W^{*}=\operatorname*{arg\,min}_{W}\left\\{\|W\|_{F}^{2}\middle|W\in\operatorname*{arg\,min}_{W}\mathbb{E}_{A_{trn}}[\|Y_{trn}-W(X_{trn}+A_{trn})\|_{F}^{2}]\right\\}$

Recall that we obtain $W_{opt}$ by instead minimizing the MSE error for a
single noise instance $A_{trn}$, which means that $W_{opt}$ overfits $A_{trn}$
in the overparametrized regime. We would like to see if this overfitting is
benign, tempered or catastrophic for test error. Following the definition of
overfitting paradigms in Mallinar et al. (2022), we want to take $N\to\infty$.
Since we are in the proportional regime, we must let $d\to\infty$ as well,
maintaining the relation $d/N=c+o(1)$. For studying overfitting, a natural
goal would be to study how the excess error
$\mathcal{R}(W_{opt},X_{tst})-\mathcal{R}(W^{*},X_{tst})$ behaves as
$d,N\to\infty$. This is analogous to the excess risk studied in overfitting
for noiseless inputs (Bartlett et al., 2020). However, we will see that both
errors in our difference individually tend to zero as $d,N\to\infty$, 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-zero. A natural generalization to consider then is to
instead study the limit of _relative excess error_

$\frac{\mathcal{R}(W_{opt},X_{tst})-\mathcal{R}(W^{*},X_{tst})}{\mathcal{R}(W^{*},X_{tst})}$

as $d,N\to\infty$ with $d/N=c+o(1)$.

######  Definition 3.

We say that overfitting is _benign_ when this limit is $0$, _tempered_ when it
is finite and positive, and _catastrophic_ when it is $\infty$.

###  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 $\beta=I$. Then, this models the least squares supervised denoising
problem.

##### Error in Variables Regression

Suppose $\beta\in\mathbb{R}^{d}$. Recall that $Y_{trn}=\beta^{T}X_{trn}$. In
this case, the standard linear regression problem is to find $\hat{\beta}$
that minimizes $\|Y_{trn}-\hat{\beta}^{T}X_{trn}\|_{F}^{2}$. For error in
variables regression, we have noise on the independent variable $X_{trn}$.
Hence, we would be solving the following problem.

$\|Y_{trn}-\hat{\beta}^{T}(X_{trn}+A_{trn})\|_{F}^{2}.$

This situation satisfies our assumptions. Note that the situation extends to
multivariate regressions, i.e., when $\beta\in\mathbb{R}^{d\times k}$ for
$k>1$.

######  Remark 1.

While this is not the full error-in-variables regression, our proof techniques
can also cover cases with errors in $Y_{trn}$.

##### Gaussian Mixture Models Classification

Our assumptions also capture classification problems for Gaussian mixtures.
Specifically, let $\mu_{1},\ldots,\mu_{k}$ be the $k$ mean vectors. Let us
also assume that the mean vectors are pairwise orthogonal. Let $z^{i}$ be the
$i$th data point and assume that $z^{i}$ belongs to the $j$th cluster. Then we
know that $z^{i}-\mu_{j}\sim\mathcal{N}(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
$\\{\mu_{1},\ldots,\mu_{k}\\}$. 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
$\beta^{T}X$ for some $\beta$. Let the label for the $j$th cluster be a
$k$-dimensional vector with a one in the $j$th coordinate and let
$\beta=[\mu_{1}\ldots\mu_{k}]$, we get that $Y=\beta^{T}X$. Hence, we can
model specific classification problems.

######  Remark 2.

The training and test metrics differ from typical classification settings,
utilizing MSE instead of cross-entropy and accuracy, respectively. However,
the two are related in many instances. See Muthukumar et al. (2021) for a 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 $K$ (much smaller than $N$ and $d$) large
eigenvalues, and the rest of the eigenvalues are of smaller order (Ke et al.,
2023). If we consider data $Z=X+A$, where the singular values of $X$ are much
bigger than the singular values of $Z$, then we see that

$\mathbb{E}[ZZ^{T}]=\mathbb{E}[(X+A)(X+A)^{T}]=\mathbb{E}[XX^{T}+AA^{T}].$

Hence, we see that $Z$ has a spiked covariance structure. In this case, we 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=\beta^{T}X$), 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 in section 4. All proofs are in Appendix C.

######  Theorem 1 (In-Subspace Test Error).

Let $r<|d-N|$. Let the SVD of $X_{trn}$ be $U\Sigma_{trn}V_{trn}^{T}$, let
$L:=U^{T}X_{tst}$, $\beta_{U}:=U^{T}\beta$, and $c:=d/N$. Under our setup and
Assumptions 1 and 2, the test error (Equation 1) is given by the following. If
$c<1$ (under-parameterized regime)

$\begin{split}\mathcal{R}(W_{opt},UL)&=\frac{\eta_{trn}^{4}}{N_{tst}}\left\|\beta_{U}^{T}(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I)^{-1}L\right\|_{F}^{2}\hskip
221.93158pt\\\
&+\frac{\eta_{tst}^{2}}{d}\frac{c^{2}}{1-c}\operatorname{Tr}\left(\beta_{U}\beta_{U}^{T}\Sigma_{trn}^{2}\left(\Sigma_{trn}^{2}+\frac{1}{\eta_{trn}^{2}}I\right)\left(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I\right)^{-2}\right)+o\left(\frac{1}{N}\right)\end{split}$

If $c>1$ (over-parameterized regime)

$\begin{split}\mathcal{R}(W_{opt},UL)&=\frac{\eta_{trn}^{4}}{N_{tst}}\left\|\beta_{U}^{T}(\Sigma_{trn}^{2}+\eta_{trn}^{2}I)^{-1}L\right\|_{F}^{2}\\\
&+\frac{\eta_{tst}^{2}}{d}\frac{c}{c-1}\operatorname{Tr}(\beta_{U}\beta_{U}^{T}(I+\eta_{trn}^{2}\Sigma_{trn}^{-2})^{-1})+O\left(\frac{\|\Sigma_{trn}\|^{2}}{N^{2}}\right)+o\left(\frac{1}{N}\right)\end{split}$

###### Proof Sketch:.

The proof can be broken into multiple steps. First, the generalization error
can be decomposed as follows (Sonthalia & Nadakuditi, 2023).

$\mathcal{R}(W,X_{tst})=\underbrace{\frac{1}{N_{tst}}\|Y_{tst}-WX_{tst}\|_{F}^{2}}_{\text{Bias}}+\underbrace{\frac{\eta_{tst}^{2}}{d}\|W\|_{F}^{2}}_{\text{Variance}}.$

Second, we solve for $W_{opt}$. From classical theory we know that
$W_{opt}=Y_{trn}(X_{trn}+A_{trn})^{\dagger}$. Using Wei (2001) and some
careful linear algebraic observations, we expand these to get

$W_{opt}=\begin{cases}U\Sigma_{trn}(P^{T}P)^{-1}Z^{T}K_{1}^{-1}H-U\Sigma_{trn}Z^{-1}HH^{T}K_{1}^{-1}ZP^{+}&c>1\\\
-U\Sigma_{trn}H_{1}^{-1}K^{T}A_{trn}^{+}+U\Sigma_{trn}H_{1}^{-1}Z^{T}(QQ^{T})^{-1}H.&c<1\end{cases}$

The exact expression for the variables in the expansion can be found in
Appendix C.

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 $c>1$, the error is decomposed
in the sums and products of the following terms - $HH^{T}$, $P^{T}P$, and $Z$.

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 $A_{trn}$. Then, using assumption 2.4, we
approximate the spectrum of $A_{trn}$ 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 $c>1$ and $c<1$ comes from the asymmetry in the
expressions for $W_{opt}$ and the need for renormalizing things in the case
when $c>1$. We further note that, in general, the expression does not depend
on the right singular vectors of $X_{trn}$ as $X_{trn}$ only appears as its
gram matrix $X_{trn}X_{trn}^{T}$. Finally, $L$ is the coordinates of $X_{tst}$
in the basis given by $U$. Then suppose
$X_{tst}=U_{tst}\Sigma_{tst}V_{tst}^{T}$. Then we see that
$L=U^{T}U_{tst}\Sigma_{tst}V_{tst}^{T}$. Then, using the unitary invariance of
the norm, we have that

$\|\beta_{U}^{T}(\Sigma\\_{trn}^{2}c+\eta\\_{trn}^{2}I)^{-1}L\|_{F}^{2}=\|\beta_{U}^{T}(\Sigma_{trn}^{2}c+\eta\\_{trn}^{2}I)^{-1}U^{T}U_{tst}\Sigma_{tst}\|_{F}^{2}.$

Hence, the error depends on an alignment term $U^{T}U_{tst}$ and the singular
values $\Sigma_{tst}$. Let us 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 $\Sigma_{trn}^{2}$ grows as fast
as possible and is $\Theta(N)$. This is also what happens when $X_{trn}$ is
low-rank Gaussian (Huang et al., 2022). Then, the bias term is $O(1/N^{2})$,
while the variance term is $O(1/d)=O(1/N)$. The estimation error is $o(1/N)$
in the underparametrized case, so the only significant term, in this case, is
the variance term. In the overparametrized case, the only significant terms
are the variance term and the $O(\|\Sigma_{trn}\|^{2}/N^{2})$ deviation from
the estimate. If $\|X_{trn}\|_{F}^{2}=o(N)$ instead of $\Theta(N)$, then the
variance term is the only significant term again. Specific instantiations of
Theorem 1 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 4.

Theorem 1 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 is one of the few results
that do not require high dimensional well-conditioned covariance (Cheng &
Montanari, 2022). Third, it generalizes Sonthalia & Nadakuditi (2023) to
higher rank settings. Further, Theorem 1 estimates 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
$\mathcal{V}$, provide results for distribution shift, and provide insights
for data augmentation.

##### Out-of-Distribution and Out-of-Subspace Generalization.

Theorem 1 can be used to understand OOD and out-of-subspace test error. For
the former, Corollary 1 below bounds the change in generalization error in
terms of in-subspace distribution shift.

######  Corollary 1 (Distribution Shift Bound).

Consider a linear denoiser $W_{opt}$ trained on training data
$X_{trn}=U\Sigma_{trn}V_{trn}^{T}$. Let it be tested on test data
$X_{tst,1}=UL_{1}$ and $X_{tst,2}=UL_{2}$ generated possibly dependently from
distributions supported in the span of $U$ with mean $U\mu_{i}$ and covariance
$\Sigma_{U,i}=U\Sigma_{i}U^{T}$ respectively. Then, the difference in
_generalization errors_
$\mathcal{G}_{i}:=\mathbb{E}_{X_{tst,i}}[\mathcal{R}(W_{opt},X_{tst,i})]$ is
bounded for $c<1$ by

$|\mathcal{G}_{2}-\mathcal{G}_{1}|\leq\frac{\sigma_{1}(\beta)^{2}\eta_{trn}^{4}r}{(\sigma_{r}(X_{trn})^{2}f(c)+\eta_{trn}^{2})^{2}}\|\Sigma_{2}-\Sigma_{1}+\mu_{2}\mu_{2}^{T}-\mu_{1}\mu_{1}^{T}\|_{F}+o\left(\frac{1}{N}\right)$

where $f(c)=c$ for $c<1$ and $f(c)=1$ otherwise. We add
$O(\|\Sigma_{trn}\|_{F}^{2}/N^{2})$ when $c\geq 1$.

Corollary 1 is interesting as it implies 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 $\mathcal{V}$.

######  Theorem 2 (Out-of-Subspace Shift Bound).

If we have the same training data and solution $W_{opt}$ assumptions as in
Theorem 1. Then, for _any_ $X_{tst}$ for which there exists an $L$ and an
$\alpha>0$ such that $\|X_{tst}-UL\|_{F}\leq\alpha$, and $A_{tst}$ that
satisfies 1,2 from Assumption 2, we have that the generalization error
$\mathcal{R}(W_{opt},X_{tst})$ satisfies

$|\mathcal{R}(W_{opt},X_{tst})-\mathcal{R}(W_{opt},UL)|\leq\alpha^{2}\sigma_{1}(W_{opt}+I)^{2}.$

Theorem 2 shows us the surprising result that even if our test data is not in
the subspace, we can 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 a distribution shift for $X$. However, we still assumed that the
targets were given by the same function of $X$. That is, $\beta$ did not
change. We now consider the scenario where $\beta$ can change to
$\beta_{tst}$. Concretely, we are in the scenario where we train our model
with $X_{trn}+A_{trn}$ and $Y_{trn}=\beta^{T}X_{trn}$ and test the model with
data $X_{tst}+A_{tst}$ and $Y_{tst}=\beta_{tst}^{T}X_{tst}$. In this case, we
have the following theorem.

######  Theorem 3 (Transfer Learning).

Let $r<|d-N|$. Let the SVD of $X_{trn}$ be $U\Sigma_{trn}V_{trn}^{T}$, let
$L:=U^{T}X_{tst}$, $\beta_{U}:=U^{T}\beta$, $\beta_{tst,U}=U^{T}\beta_{tst}$,
and $c:=d/N$. Under our setup and Assumptions 1 and 2, the test error
(Equation 1) is given by the following. If $c<1$ (under-parameterized regime)

$\begin{split}\mathbb{E}_{A_{trn},A_{tst}}\left[\frac{1}{N_{tst}}\|Y_{tst}-W_{opt}(X_{tst}+A_{tst})\|_{F}^{2}\right]&=\frac{1}{N_{tst}}\|(\beta_{tst,U}-\beta_{U})^{T}L\|_{F}^{2}\\\
&-\frac{2\eta_{tst}^{2}}{N_{tst}}\operatorname{Tr}(\beta_{U}^{T}(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I)^{-1}LL^{T}(\beta_{tst,U}-\beta_{U}))\\\
&+\frac{\eta_{tst}^{2}}{d}\frac{c^{2}}{1-c}\operatorname{Tr}\left(\beta_{U}\beta_{U}^{T}\Sigma_{trn}^{2}\left(\Sigma_{trn}^{2}+\frac{1}{\eta_{trn}^{2}}I\right)\left(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I\right)^{-2}\right)\\\
&+\frac{\eta_{trn}^{4}}{N_{tst}}\left\|\beta_{U}^{T}(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I)^{-1}L\right\|_{F}^{2}+o\left(\frac{1}{N}\right)\end{split}$

If $c>1$ (over-parameterized regime)

$\begin{split}\mathbb{E}_{A_{trn},A_{tst}}\left[\frac{1}{N_{tst}}\|Y_{tst}-W_{opt}(X_{tst}+A_{tst})\|_{F}^{2}\right]&=\frac{1}{N_{tst}}\|(\beta_{tst,U}-\beta_{U})^{T}L\|_{F}^{2}\\\
&-\frac{2\eta_{tst}^{2}}{N_{tst}}\operatorname{Tr}(\beta_{U}^{T}(\Sigma_{trn}^{2}+\eta_{trn}^{2}I)^{-1}LL^{T}(\beta_{tst,U}-\beta_{U}))\\\
&+\frac{\eta_{tst}^{2}}{d}\frac{c}{c-1}\operatorname{Tr}(\beta_{U}\beta_{U}^{T}(I+\eta_{trn}^{2}\Sigma_{trn}^{-2})^{-1})+O\left(\frac{\|\Sigma_{trn}\|^{2}}{N^{2}}\right)\\\
&+\frac{\eta_{trn}^{4}}{N_{tst}}\left\|\beta_{U}^{T}(\Sigma_{trn}^{2}+\eta_{trn}^{2}I)^{-1}L\right\|_{F}^{2}+o\left(\frac{1}{N}\right)\end{split}$

###### Proof.

Note that

$\mathbb{E}_{A_{trn},A_{tst}}\left[\frac{1}{N_{tst}}\|Y_{tst}-W_{opt}(X_{tst}+A_{tst})\|_{F}^{2}\right]=\mathbb{E}_{A_{trn},A_{tst}}\left[\frac{1}{N_{tst}}Y_{tst}-\beta^{T}X_{tst}+\beta^{T}X_{tst}-W_{opt}(X_{tst}+A_{tst})\|_{F}^{2}\right].$

Then, expand the norm twice to get the above result. ∎

Here it is easy to see that since $\beta,\beta_{tst}$ are constant and
$\|X_{tst}\|^{2}=\|L\|^{2}=O(N_{tst})$, we see that the first two terms in
both expressions are $O_{c}(1)$ as a function of $c$. Hence, we see that as a
function of $c$, this error also has double descent.

##### Overfitting Paradigms.

We now compute the test error from $W^{*}$ in Theorem 4, 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 setting as Theorem 1, we have that
$W^{*}=\beta_{U}^{T}\left(I+\frac{\eta_{trn}^{2}}{c}\Sigma_{trn}^{-2}\right)^{-1}U^{T}$
and

$\mathcal{R}(W^{*},UL)=\frac{\eta_{trn}^{4}N^{2}}{{N_{tst}}d^{2}}\left\|\beta_{U}^{T}\left(\Sigma_{trn}^{2}+\frac{\eta_{trn}^{2}N}{d}I\right)^{-1}L\right\|_{F}^{2}+\frac{\eta_{tst}^{2}}{d}Tr\left(\beta_{U}\beta_{U}^{T}\left(I+\frac{\eta_{trn}^{2}N}{d}\Sigma_{trn}^{-2}\right)^{-2}\right).$

######  Corollary 2 (Relative Excess Error).

Let $\|\Sigma_{trn}\|_{F}^{2}=\Omega(N^{1/2+\epsilon})$. As $d,N\to\infty$
with $d/N\to c$, the relative excess error tends to $\frac{c}{1-c}$ in the
underparametrized regime. In the overparametrized regime, when
$\|\Sigma_{trn}\|_{F}^{2}=o(N)$, it tends to $\frac{1}{c-1}$ and to
$\frac{1}{c-1}+k$ for some constant $k$ when
$\|\Sigma_{trn}\|_{F}^{2}=\Theta(N)$.

(a)

(b)

(c)

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 $r$ 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 a linear function $W_{opt}$ on CIFAR (Krizhevsky,
2009) and test on CIFAR, STL10 (Coates et al., 2011), and SVHN (Netzer et al.,
2011). 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 $W_{opt}$ and plot the
empirical average of
$\frac{1}{N_{tst}}\|X_{tst}-W_{opt}(X_{tst}+A_{tst})\|_{F}^{2}$ over 200
trials. We run three main kinds of experiments. (a) First, we enforce the low-
rank assumption to 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 approximately low-rank)
training data matrices $X_{tst}$, we find the best low-rank approximation
$\hat{X}_{trn}$ of the training data by projecting it to an 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 $\alpha$ from the low-rank assumption, we perturb the low-
rank testing data from setting (a) and test using
$\tilde{X}_{tst}:=\hat{X}_{tst}+K_{tst}$, where $K_{tst}$ is Gaussian noise
with covariance designed to control $\alpha$. (c) In the third case, we do not
try to artificially enforce the low-rank assumption, relying on the
approximate low-rank nature of real-life data. To do this, we report the test
error for the matrices $X_{tst}$ themselves. Since $d$ is fixed, we vary $c$
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 setup (a) is under $1\%$ on average. For setup (c),
since real-life data is only _approximately_ 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 behaviour of real-life data.

(a) In-subspace test error.

(b) For the out-of-subspace curves, we add full-dimensional Gaussian noise
such that $\alpha=0.1$. The upper and lower bounds for the empirical markers
are given by Theorem 2).

(c) Test error estimated without projecting data, relying on the approximate
low-rank structure of real-life data.

Figure 2: Figures showing the test error for $\beta=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 $r=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. In (c), we don’t
project the test data and report the standard test error, relying on the
approximate low-rank structure in data instead of imposing it. For empirical
data points, shown by markers, we report the mean test error over at least 200
trials. Similar results are obtained for single-variable regression with
$\beta\in\mathbb{R}^{d}$.

##### Single-variable Regression

Theorem 1 is for any $\beta\in\mathbb{R}^{d\times k}$. Above, we presented
figures for when $\beta=I_{d}$. Here, we present a similar figure for the
single variable regression case. That is when $\beta\in\mathbb{R}^{d\times
1}$. Figure 1 shows the results. As before, we train all models on CIFAR and
then test on CIFAR, SVHN, and STL10 with the same target $\beta$. As we can
see the theory closely matches the empirical results.

##### Classification

We verify our theoretical predictions in the case of classification via two
experiments. For the first experiment, we have two datasets. First, we have
two Gaussian clusters with means $\pm\mu$ and have labels $\pm 1$. Second, we
have three clusters with mutually orthogonal means and labels
$e_{1},e_{2},e_{3}$. 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 3 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.

(a) 2 Cluster MSE

(b) 2 Cluster Accuracy

(c) 3 Cluster MSE

(d) 3 Cluster Accuracy

Figure 3: MSE and Accuracy when we only have covariate shift and
$\beta_{tst}=\beta$.

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 $\mu_{1},\mu_{2},\mu_{3}$ that are mutually orthogonal. We also
have that the target for $\mu_{i}$ is the vector $e_{i}$. Then, during the
test time, we assume that the means vectors for the three clusters have moved
to $\mu_{tst,1},\mu_{tst,2},\mu_{tst,3}$ and we interested in mapping
$\mu_{tst,i}$ to $e_{i}$. Hence, we have both covariate shifts, and the target
function has changed. Thus, we are predicting the error for transfer learning
with covariates shift. Figure 4 shows that Theorem 3 exactly predicts the
error. _Again, we see double descent in the test mean squared error._ However,
in this case, this double descent doesn’t always translate to double descent
in the classification accuracy (for the new classes). Two different shifts,
with different trends, can be seen in Figure 4.

(a) MSE for classification for three Gaussian clusters with covariates shift
and transfer learning

(b) Accuracy for first covariate shift

(c) Accuracy for second covariate shift

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 $c$ approaches $1$ from either side, and there is a
peak at $c=1$. This matches our theoretical results and establishes that
denoising test error curves exhibit double descent, even for arbitrary test
data in $\mathcal{V}$. To understand why this is happening, consider the
denoising target, given by the MSE error below.

$\mathbb{E}_{A_{tst}}[\|Y_{trn}-W(X_{trn}+A_{trn})\|_{F}^{2}]=\|Y_{trn}-WX_{trn}\|_{F}^{2}+2Tr(Y_{trn}-WX_{trn})^{T}A_{trn})+\|WA_{trn}\|_{F}^{2}.$

Notice that minimizing this sum forces us to reduce _both_
$\|Y_{trn}-WX_{trn}\|_{F}$ and $\|W\|_{F}$, due to the third term (the
"variance" term). We see that the noise is regularizing $\|W\|_{F}$ through
the variance term $Tr(W^{T}WA_{trn}A_{trn}^{T})$. This is the implicit
regularization of $W$ due to noise. However, the strength of regularization
due to the noise instance $A_{trn}$ is not the same across different values of
$c$. When $c$ is close to $1$, the distribution of the spectrum of
$A_{trn}A_{trn}^{T}$ (the Marchenko-Pastur distribution) has support very
close to zero. On the other hand, for $c$ far from $1$, the non-zero
eigenvalues of $A_{trn}A_{trn}^{T}$ are all bounded away from zero. This
establishes that the effect of regularization weakens most near $c=1$,333The
eigenvalues that are exactly zero do not contribute to weakening of the
regularization. This is because we are choosing the minimum-norm optimizer
$W^{*}$ for expected MSE error, and more zero eigenvalues increases
flexibility, creating a larger set of optimizers to minimize the norm over.
This helps decrease the components of $W^{*}$ by spreading them into more
dimensions. This is identical in spirit to arguments about variance in
overparametrized regimes in section 1.1 of Hastie et al. (2022). leading to a
spike in the test error coming from the large norm of the learnt $W_{opt}$.
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

(a)

(b)

(c)

(d)

Figure 5: Optimal $\eta_{trn}$ that minimizes the test error given in Theorem
1 versus $c=d/N_{trn}$.

(a)

(b)

(c)

(d)

Figure 6: Test Error using Theorem 1 versus $1/c$ with optimal $\eta_{trn}$.

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 a linear model. In this section, we support
this claim using our result from Theorem 1. Figure 5 shows the double descent
curve of $\eta_{trn}$ and Figure 6 shows the generalization error when using
the optimal amount of training noise. As in other works such as Sonthalia &
Nadakuditi (2023); Yilmaz & Heckel (2022), 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 1 to understand how this will affect test
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
a specific distribution_ , we can combine two different datasets into a larger
training dataset to increase $N$. The subtlety to account for is that while
increasing $N$ this way decreases $c$, it also increases $\Sigma_{trn}$.
However, recall from the insights on the scale of terms above that the
variance term is commonly the dominant one, and note that the variance term is
roughly constant as $\Sigma_{trn}$ grows444The bias term decreases or stays
constant with $\Sigma_{trn}$, but the bias term is irrelevant at common scales
of $\Sigma_{trn}$.. When $c<1$, applying data augmentation increases $N$, thus
decreasing $c$ further away from the peak at $1$ and decreasing test error.
When $c>1$, applying data augmentation increases $N$, decreasing $c$ towards
the peak at $1$ and increasing test error. Of course, the latter phenomenon
could be mitigated by adding other regularizers or by further augmenting the
data. Figures 8(d) and 8(h) empirically verify the validity of Theorem 1 for
the training data obtained from data augmentation. _We also see that
increasing the number of in-distribution training data points reduces the out-
of-distribution test error._

(a)

(b)

(c)

(d) Data augmentation exploiting non-independence. For different $N_{trn}$ the
training data is formed by repeating the same 1000 images from the CIFAR
dataset.

(e)

(f)

(g)

(h) Data augmentation exploiting non-identicality of the distribution. The
training data is formed by mixing CIFAR train split with STL10 train split
dataset.

Figure 8: Data augmentation exploiting non-independence. For different
$N_{trn}$ the training data is formed by repeating the same 1000 images from
the CIFAR dataset.

##### Overfitting Paradigms.

Recall from Corollary 2 that the relative excess error is given by
$\frac{c}{1-c}$ 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 $\frac{1}{1-c}$ when
$\|\Sigma_{trn}\|^{2}=o(N)$. Then as $c$ becomes arbitrarily large we again
approach benign overfitting. This is interesting as this is 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 we had
$\|\Sigma_{trn}\|^{2}=\Theta(N)$, then our results suggest that the relative
excess error _may_ increase by a constant, leading to no benign overfitting.
However, we believe that this is an artifact of the proof technique.

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_{opt}$ is the minimum-norm matrix
minimizing the MSE error for a single noise instance, $W^{*}$ is the minimum-
norm matrix minimizing its expectation over noise. We can use this observation
to view $W^{*}$ as $W_{opt}$ over an augmented dataset. Taking the expectation
over noise in the training target is in spirit like augmenting the data with
“infinitely many” copies of itself, each with fresh noise. So, $W^{*}$ can be
viewed as the outcome of training $W_{opt}$ over an augmented dataset with a
“changed $c$,” where $c$ is replaced with a vanishingly small value while
keeping $\Sigma_{trn}^{2}/N=\Sigma_{trn}^{2}c/d$ constant.

##  5 Conclusion and Future Work

We studied the problem of denoising low-dimensional input data perturbed with
high-dimensional noise. Under very general assumptions, we provided estimated
test error in terms of the specific instantiations of the training data and
test data. This result is significant, as there is scarce prior work in the
area of generalization for noisy inputs as well as generalization for low-rank
data. Further, we tested 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 to get with results on generalization error,
such as showing double descent for arbitrary test data in our low-dimensional
subspace, theoretically understanding data augmentation, and provably
demonstrating as well as explaining the lack of benign overfitting.

## References

  * Ba et al. (2023) Jimmy Ba, Murat A Erdogdu, Taiji Suzuki, Zhichao Wang, and Denny Wu.  Learning in the presence of low-dimensional structure: A spiked random matrix perspective.  In _Conference on Parsimony and Learning (Recent Spotlight Track)_ , 2023.  URL https://openreview.net/forum?id=sDBBjwc73g.
  * Bai et al. (2003) Z. Bai, Baiqi. Miao, and Jian-Feng. Yao.  Convergence Rates of Spectral Distributions of Large Sample Covariance Matrices.  _SIAM Journal on Matrix Analysis and Applications_ , 2003.
  * Baldi & Hornik (1989) Pierre Baldi and Kurt Hornik.  Neural networks and principal component analysis: Learning from examples without local minima.  _Neural Networks_ , 2:53–58, 1989.  URL https://api.semanticscholar.org/CorpusID:14333248.
  * Bartlett et al. (2020) Peter Bartlett, Philip M. Long, Gabor Lugosi, and Alexander Tsigler.  Benign Overfitting in Linear Regression.  _Proceedings of the National Academy of Sciences_ , 2020.
  * Belkin et al. (2019) 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 Academy of Sciences_ , 2019.
  * Belkin et al. (2020) Mikhail Belkin, Daniel J. Hsu, and Ji Xu.  Two Models of Double Descent for Weak Features.  _SIAM Journal on Mathematics of Data Science_ , 2020.
  * Ben-David et al. (2006) Shai Ben-David, John Blitzer, Koby Crammer, and Fernando Pereira.  Analysis of Representations for Domain Adaptation.  In _Advances in Neural Information Processing Systems_ , 2006.
  * Ben-Tal et al. (2009) Aharon. Ben-Tal, Laurent E. Ghaoui, and Arkadi Nemirovski.  _Robust Optimization_.  Princeton Series in Applied Mathematics. Princeton University Press, 2009\.  ISBN 9781400831050.
  * Bertsimas et al. (2011) Dimitris Bertsimas, David Brown, and Constatine Caramanis.  Theory and Applications of Robust Optimization.  _SIAM Rev._ , 53:464–501, 2011.
  * Bishop (1995) Chris M. Bishop.  Training with Noise is Equivalent to Tikhonov Regularization.  _Neural Computation_ , 1995.
  * Bohrnstedt & Goldberger (1969) George W. Bohrnstedt and Arthur S. Goldberger.  On the exact covariance of products of random variables.  _Journal of the American Statistical Association_ , 64(328):1439–1442, 1969.  ISSN 01621459.  URL http://www.jstor.org/stable/2286081.
  * Camuto et al. (2020) 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.
  * Chakraborty et al. (2021) Anirban Chakraborty, Manaar Alam, Vishal Dey, Anupam Chattopadhyay, and Debdeep Mukhopadhyay.  A Survey on Adversarial Attacks and Defences.  _CAAI Transactions on Intelligence Technology_ , 6(1):25–45, 2021.  doi: https://doi.org/10.1049/cit2.12028.
  * Chen et al. (2020) 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\.
  * Cheng & Montanari (2022) Chen Cheng and Andrea Montanari.  Dimension Free Ridge Regression.  _arXiv preprint arXiv:2210.08571_ , 2022.
  * Coates et al. (2011) 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.
  * Cui & Zdeborová (2023) Hugo Cui and Lenka Zdeborová.  High-dimensional asymptotics of denoising autoencoders.  _arXiv preprint arXiv:2305.11041_ , 2023.
  * Cui et al. (2021) 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.
  * Darestani et al. (2021) 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.
  * Davenport & Romberg (2016) Mark A. Davenport and Justin K. Romberg.  An overview of low-rank matrix recovery from incomplete observations.  _CoRR_ , abs/1601.06422, 2016.  URL http://arxiv.org/abs/1601.06422.
  * Derezinski et al. (2020) Michal Derezinski, Feynman T Liang, and Michael W Mahoney.  Exact Expressions for Double Descent and Implicit Regularization Via Surrogate Random Design.  In _Advances in Neural Information Processing Systems_ , 2020.
  * Dobriban & Wager (2018) Edgar Dobriban and Stefan Wager.  High-dimensional asymptotics of prediction: Ridge regression and classification.  _The Annals of Statistics_ , 2018.
  * Du et al. (2019a) 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 on Machine Learning_ , 2019a.
  * Du et al. (2019b) Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh.  Gradient Descent Provably Optimizes Over-parameterized Neural Networks.  In _International Conference on Learning Representations_ , 2019b.
  * Elad et al. (2023) Michael Elad, Bahjat Kawar, and Gregory Vaksman.  Image denoising: The deep learning revolution and beyond—a survey paper.  _SIAM Journal on Imaging Sciences_ , 16(3):1594–1654, 2023.  doi: 10.1137/23M1545859.  URL https://doi.org/10.1137/23M1545859.
  * F.R.S. (1901) Karl Pearson F.R.S.  Liii. on lines and planes of closest fit to systems of points in space.  _Philosophical Magazine Series 1_ , 2:559–572, 1901.  URL https://api.semanticscholar.org/CorpusID:125037489.
  * Gerace et al. (2020) 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.
  * Ghorbani et al. (2019) 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.
  * Ghorbani et al. (2020) Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari.  When Do Neural Networks Outperform Kernel Methods?  In _Advances in Neural Information Processing Systems_ , 2020.
  * Götze & Tikhomirov (2011) Friedrich Götze and A. Tikhomirov.  On the Rate of Convergence to the Marchenko–Pastur Distribution.  _arXiv: Probability_ , 2011.
  * Götze & Tikhomirov (2003) Friedrich Götze and Alexander Tikhomirov.  Rate of Convergence to the Semi-Circular Law.  _Probability Theory and Related Fields_ , 2003.
  * Götze & Tikhomirov (2004) Friedrich Götze and Alexander Tikhomirov.  Rate of Convergence in Probability to the Marchenko-Pastur Law.  _Bernoulli_ , 2004.
  * Götze & Tikhomirov (2005) Friedrich Götze and Alexander Tikhomirov.  The Rate of Convergence for Spectra of GUE and LUE Matrix Ensembles.  _Central European Journal of Mathematics_ , 2005.
  * Hastie et al. (2022) Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J. Tibshirani.  Surprises in High-Dimensional Ridgeless Least Squares Interpolation.  _The Annals of Statistics_ , 2022.
  * Hirshberg (2021) David A Hirshberg.  Least squares with error in variables.  _arXiv preprint arXiv:2104.08931_ , 2021.
  * Hu et al. (2020) Wei Hu, Zhiyuan Li, and Dingli Yu.  Simple and Effective Regularization Methods for Training on Noisily Labeled Data with Generalization Guarantee.  In _International Conference on Learning Representations_ , 2020.
  * Huang et al. (2022) Ningyuan Huang, David W. Hogg, and Soledad Villar.  Dimensionality Reduction, Regularization, and Generalization in Overparameterized Regressions.  _SIAM Journal on Mathematics of Data Science_ , 2022.
  * Jacot et al. (2020) 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.
  * Ji & Telgarsky (2019) Ziwei Ji and Matus Telgarsky.  The Implicit Bias of Gradient Descent on Nonseparable Data.  In _Proceedings of the 32nd Conference on Learning Theory_ , 2019\.
  * Ke et al. (2023) 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 Statistical Association_ , 118(541):374–392, 2023.
  * Kirchler et al. (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–17121. PMLR, 23–29 Jul 2023.  URL https://proceedings.mlr.press/v202/kirchler23a.html.
  * Kotyan (2023) Shashank Kotyan.  A reading survey on adversarial machine learning: Adversarial attacks and their understanding, 2023.
  * Krizhevsky (2009) Alex Krizhevsky.  Learning Multiple Layers of Features from Tiny Images.  2009\.
  * Krizhevsky et al. (2012) Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton.  Imagenet Classification with Deep Convolutional Neural Networks.  _Communications of the ACM_ , 2012.
  * Lampinen & Ganguli (2019) 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.
  * Lei et al. (2021) Qi Lei, Wei Hu, and Jason Lee.  Near-Optimal Linear Regression under Distribution Shift.  In _Proceedings of the 38th International Conference on Machine Learning_ , 2021.
  * LeJeune et al. (2022) Daniel LeJeune, Jiayu Liu, and Reinhard Heckel.  Monotonic Risk Relationships under Distribution Shifts for Regularized Risk Minimization.  _arXiv preprint arXiv:2210.11589_ , 2022.
  * Lelarge & Miolane (2017) Marc Lelarge and Léo Miolane.  Fundamental Limits of Symmetric Low-Rank Matrix Estimation.  In _Proceedings of the 29th Conference on Learning Theory_ , 2017\.
  * Lesieur et al. (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.
  * Liang et al. (2020) 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\.
  * Loureiro et al. (2021a) 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 a Teacher-Student Model.  In _Advances in Neural Information Processing Systems_ , 2021a.
  * Loureiro et al. (2021b) Bruno Loureiro, Gabriele Sicuro, Cedric Gerbelot, Alessandro Pacco, Florent Krzakala, and Lenka Zdeborova.  Learning Gaussian Mixtures with Generalized Linear Models: Precise Asymptotics in High-dimensions.  In _Advances in Neural Information Processing Systems_ , 2021b.
  * Maillard et al. (2022) 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.
  * Mallinar et al. (2022) Neil Mallinar, James B. Simon, Amirhesam Abedsoltan, Parthe Pandit, Mikhail Belkin, and Preetum Nakkiran.  Benign, tempered, or catastrophic: A taxonomy of overfitting, 2022.  URL https://arxiv.org/abs/2207.06569.
  * Mania & Sra (2020) Horia Mania and Suvrit Sra.  Why Do Classifier Accuracies Show Linear Trends Under Distribution Shift?  _arXiv preprint arXiv:2012.15483_ , 2020.
  * Marcenko & Pastur (1967) Vladimir Marcenko and Leonid Pastur.  Distribution of Eigenvalues for Some Sets of Random Matrices.  _Mathematics of The Ussr-sbornik_ , 1967.
  * McCoy et al. (2020) 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 BlackboxNLP Workshop on Analyzing and Interpreting Neural Networks for NLP_ , 2020.
  * Mei & Montanari (2021) Song Mei and Andrea Montanari.  The Generalization Error of Random Features Regression: Precise Asymptotics and the Double Descent Curve.  _Communications on Pure and Applied Mathematics_ , 2021.
  * Mei et al. (2018) 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 United States of America_ , 2018.
  * Mei et al. (2022) Song Mei, Theodor Misiakiewicz, and Andrea Montanari.  Generalization Error of Random Feature and Kernel Methods: Hypercontractivity and Kernel Matrix Concentration.  _Applied and Computational Harmonic Analysis_ , 2022.
  * Mel & Ganguli (2021) 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.
  * Miller et al. (2020) 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.
  * Miller et al. (2021) 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 Out-Of-Distribution and In-Distribution Generalization.  In _Proceedings of the 38th International Conference on Machine Learning_ , 2021.
  * Muthukumar et al. (2019) Vidhya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai.  Harmless Interpolation of Noisy Data in Regression.  _IEEE International Symposium on Information Theory_ , 2019.
  * Muthukumar et al. (2021) Vidya Muthukumar, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel Hsu, and Anant Sahai.  Classification vs regression in overparameterized regimes: Does the loss function matter?  _The Journal of Machine Learning Research_ , 22(1):10104–10172, 2021.
  * Nadakuditi (2014) Raj. R. Nadakuditi.  OptShrink: An Algorithm for Improved Low-Rank Signal Matrix Denoising by Optimal, Data-Driven Singular Value Shrinkage.  _IEEE Transactions on Information Theory_ , 2014.
  * Nakkiran et al. (2020) Preetum Nakkiran, Prayaag Venkat, Sham M. Kakade, and Tengyu Ma.  Optimal Regularization can Mitigate Double Descent.  In _International Conference on Learning Representations_ , 2020.
  * Neelakantan et al. (2015) 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.
  * Netzer et al. (2011) Yuval Netzer, Tao Wang, Adam Coates, A. Bissacco, Bo Wu, and A. Ng.  Reading Digits in Natural Images with Unsupervised Feature Learning.  2011\.
  * Neyshabur (2017) Behnam Neyshabur.  Implicit Regularization in Deep Learning.  _ArXiv_ , abs/1709.01953, 2017.
  * Opper & Kinzel (1996) Manfred Opper and Wolfgang Kinzel.  Statistical Mechanics of Generalization.  _Models of Neural Networks III: Association, Generalization, and Representation_ , 1996.
  * Paquette et al. (2022) Courtney Paquette, Elliot Paquette, Ben Adlam, and Jeffrey Pennington.  Homogenization of SGD in High-dimensions: Exact Dynamics and Generalization Properties.  2022\.
  * Poole et al. (2014) Ben Poole, Jascha Narain Sohl-Dickstein, and Surya Ganguli.  Analyzing Noise in Autoencoders and Deep Networks.  _ArXiv_ , 2014.
  * Pretorius et al. (2018) Arnu Pretorius, Steve Kroon, and Herman Kamper.  Learning Dynamics of Linear Denoising Autoencoders.  In _Proceedings for the 35th International Conference on Machine Learning_ , 2018.
  * Rakin et al. (2019) Adnan Siraj Rakin, Zhezhi He, and Deliang Fan.  Parametric Noise Injection: Trainable Randomness to Improve Deep Neural Network Robustness Against Adversarial Attack.  _2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019.
  * Recht et al. (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.
  * Rombach et al. (2022) Robin Rombach, A. Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer.  High-Resolution Image Synthesis with Latent Diffusion Models.  _2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2022.
  * Shamir (2022) Ohad Shamir.  The Implicit Bias of Benign Overfitting.  In _Proceedings of 35th Conference on Learning Theory_ , 2022.
  * Sonthalia & Nadakuditi (2023) 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 Learning Research_ , 2023.
  * Sonthalia et al. (2023) Rishi Sonthalia, Xinyue Li, and Bochao Gu.  Under-Parameterized Double Descent for Ridge Regularized Least Squares Denoising of Data on a Line.  2023\.
  * Soudry et al. (2018) Daniel Soudry, Elad Hoffer, Suriya Gunasekar, and Nathan Srebro.  The Implicit Bias of Gradient Descent on Separable Data.  _Journal of Machine Learning Research_ , 2018.
  * Srivastava et al. (2014) Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov.  Dropout: A Simple Way to Prevent Neural Networks from Overfitting.  _Journal of Machine Learning Research_ , 2014.
  * Tian et al. (2020) Chunwei Tian, Lunke Fei, Wenxian Zheng, Yong Xu, Wangmeng Zuo, and Chia-Wen Lin.  Deep learning on image denoising: An overview.  _Neural Networks_ , 131:251–275, 2020.  ISSN 0893-6080.  doi: https://doi.org/10.1016/j.neunet.2020.07.025.  URL https://www.sciencedirect.com/science/article/pii/S0893608020302665.
  * Tripuraneni et al. (2021a) Nilesh Tripuraneni, Ben Adlam, and Jeffrey Pennington.  Covariate Shift in High-Dimensional Random Feature Regression.  _ArXiv_ , 2021a.
  * Tripuraneni et al. (2021b) Nilesh Tripuraneni, Ben Adlam, and Jeffrey Pennington.  Overparameterization Improves Robustness to Covariate Shift in High Dimensions.  In _Advances in Neural Information Processing Systems_ , 2021b.
  * Troiani et al. (2022) Emanuele Troiani, Vittorio Erba, Florent Krzakala, Antoine Maillard, and Lenka Zdeborov’a.  Optimal Denoising of Rotationally Invariant Rectangular Matrices.  _ArXiv_ , 2022.
  * Udell & Townsend (2019) Madeleine Udell and Alex Townsend.  Why Are Big Data Matrices Approximately Low Rank?  _SIAM Journal on Mathematics of Data Science_ , 2019.
  * Vincent et al. (2010a) Pascal Vincent, Hugo Larochelle, Isabelle Lajoie, Yoshua Bengio, and Pierre-Antoine Manzagol.  Stacked denoising autoencoders: Learning useful representations in a deep network with a local denoising criterion.  _Journal of Machine Learning Research_ , 11(110):3371–3408, 2010a.  URL http://jmlr.org/papers/v11/vincent10a.html.
  * Vincent et al. (2010b) Pascal Vincent, Hugo Larochelle, Isabelle Lajoie, Yoshua Bengio, and Pierre-Antoine Manzagol.  Stacked Denoising Autoencoders: Learning Useful Representations in a Deep Network with a Local Denoising Criterion.  _Journal of Machine Learning Research_ , 2010b.
  * Wei et al. (2022) Alexander Wei, Wei Hu, and Jacob Steinhardt.  More Than a Toy: Random Matrix Models Predict How Real-World Neural Representations Generalize.  In _Proceedings of the 39th International Conference on Machine Learning_ , 2022.
  * Wei (2001) Yimin Wei.  The Weighted Moore–Penrose Inverse of Modified Matrices.  _Applied Mathematics and Computation_ , 2001.
  * Woodworth et al. (2020) 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.
  * Wu & Xu (2020) Denny Wu and Ji Xu.  On the Optimal Weighted $\ell_{2}$ Regularization in Overparameterized Linear Regression.  _Advances in Neural Information Processing Systems_ , 2020.
  * Xu & Hsu (2019) Ji Xu and Daniel J Hsu.  On the Number of Variables to Use in Principal Component Regression.  _Advances in Neural Information Processing Systems_ , 2019.
  * Yilmaz & Heckel (2022) Fatih Furkan Yilmaz and Reinhard Heckel.  Regularization-Wise Double Descent: Why it Occurs and How to Eliminate it.  In _IEEE International Symposium on Information Theory_ , 2022.

##  Appendix A Additional Theoretical Results

###  A.1 Test Error and Generalization Error

Recall from the introduction that the work of LeJeune et al. (2022) requires
the simultaneous diagonalizability of the covariance matrices of training and
test data. In 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 1.

######  Corollary 3 (Conjecture of Sonthalia & Nadakuditi (2023)).

Let the SVD of $X_{tst}$ be $U_{tst}\Sigma_{tst}V_{tst}^{T}$. In Theorem 1, if
we further assume that $U^{T}U_{tst}=I$, then If $c<1$ (under-parameterized
regime)

$\begin{split}\mathcal{R}(W_{opt},UL)&=\eta_{trn}^{4}\left\|\beta_{U}^{T}(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I)^{-1}\Sigma_{tst}\right\|_{F}^{2}\hskip
221.93158pt\\\
&+\frac{\eta_{tst}^{2}}{d}\frac{c^{2}}{1-c}\operatorname{Tr}\left(\beta_{U}\beta_{U}^{T}\Sigma_{trn}^{2}\left(\Sigma_{trn}^{2}+\frac{1}{\eta_{trn}^{2}}I\right)\left(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I\right)^{-2}\right)+o\left(\frac{1}{N}\right)\end{split}$

If $c>1$ (over-parameterized regime)

$\begin{split}\mathcal{R}(W_{opt},UL)&=\eta_{trn}^{4}\left\|\beta_{U}^{T}(\Sigma_{trn}^{2}+\eta_{trn}^{2}I)^{-1}\Sigma_{tst}\right\|_{F}^{2}\\\
&+\frac{\eta_{tst}^{2}}{d}\frac{c}{c-1}\operatorname{Tr}(\beta_{U}\beta_{U}^{T}(I+\eta_{trn}^{2}\Sigma_{trn}^{-2})^{-1})+O\left(\frac{\|\Sigma_{trn}\|^{2}}{N^{2}}\right)+o\left(\frac{1}{N}\right)\end{split}$

Additionally, we can use Theorem 1 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<|d-N|$. Let the SVD of $X_{trn}$ be $U\Sigma_{trn}V_{trn}^{T}$, let
$L:=U^{T}X_{tst}$, $\beta_{U}:=U^{T}\beta$, and $c:=d/N$. Under our setup and
Assumptions 1 and 2, with the further assumption that the columns of $L$ are
drawn IID from a distribution with mean $\mu$ and Covariance $\Sigma$, the
test error (Equation 1) is given by the following.
If $c<1$ (under-parameterized regime)

$\begin{split}\mathbb{E}_{L}[\mathcal{R}(W_{opt},UL)]&=\eta_{trn}^{4}\left\|\beta_{U}^{T}(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I)^{-1}(\Sigma+\mu\mu^{T})^{1/2}\right\|_{F}^{2}\hskip
221.93158pt\\\
&+\frac{\eta_{tst}^{2}}{d}\frac{c^{2}}{1-c}\operatorname{Tr}\left(\beta_{U}\beta_{U}^{T}\Sigma_{trn}^{2}\left(\Sigma_{trn}^{2}+\frac{1}{\eta_{trn}^{2}}I\right)\left(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I\right)^{-2}\right)+o\left(\frac{1}{N}\right)\end{split}$

If $c>1$ (over-parameterized regime)

$\begin{split}\mathbb{E}_{L}[\mathcal{R}(W_{opt},UL)]&=\eta_{trn}^{4}\left\|\beta_{U}^{T}(\Sigma_{trn}^{2}+\eta_{trn}^{2}I)^{-1}(\Sigma+\mu\mu^{T})^{1/2}\right\|_{F}^{2}\\\
&+\frac{\eta_{tst}^{2}}{d}\frac{c}{c-1}\operatorname{Tr}(\beta_{U}\beta_{U}^{T}(I+\eta_{trn}^{2}\Sigma_{trn}^{-2})^{-1})+O\left(\frac{\|\Sigma_{trn}\|^{2}}{N^{2}}\right)+o\left(\frac{1}{N}\right)\end{split}$

###  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
a corollary of its proof.

######  Theorem 5 (Test Set Shift Bound).

Under the assumptions of Theorem 1, consider a linear regressor $W_{opt}$
trained on training data $X_{trn}=U\Sigma_{trn}V_{trn}^{T}$ with
$\Sigma_{trn}$ such that $\sigma_{r}(X_{trn})>M$, and tested on test data
$X_{tst,1}=UL_{1}$ and $X_{tst,2}=UL_{2}$ with noise $A_{tst,1},A_{tst,2}$
with the same variance $\eta_{tst^{2}}/d$. Then, the generalization errors
$\mathcal{R}_{1}$ and $\mathcal{R}_{2}$ differ for $c<1$ by

$|\mathcal{R}_{2}-\mathcal{R}_{1}|\leq\frac{\sigma_{1}(\beta)^{2}}{N_{tst}}\frac{\eta_{trn}^{4}r}{(\sigma_{r}(X_{trn})^{2}f(c)+\eta_{trn}^{2})^{2}}\|L_{2}L_{2}^{T}-L_{1}L_{1}^{T}\|_{F}+o\left(\frac{1}{N}\right)\\\
$

where $f(c)=c$ for $c<1$ and $f(c)=1$ for $c\geq 1$. We add
$O(\|\Sigma_{trn}\|_{F}^{2}/N^{2})$ to the bound when $c>1$.

##  Appendix B Additional Implications of our Results

###  B.1 Out-of-Subspace Generalization

(a)

(b)

(c)

(d) $r$ = 50; We find that $\alpha$ is approximately 54, 75 and 31 for (a)-(c)
respectively.

(e)

(f)

(g)

(h) $r$ = 100; We find that $\alpha$ is approximately 44, 66 and 20 for
(a)-(c) respectively.

(i)

(j)

(k)

(l) $r$ = 150; We find that $\alpha$ is approximately 37, 60 and 15 for
(a)-(c) respectively.

Figure 10: Figure showing the test error vs $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
$\sqrt{\mathcal{R}(UL)}+\alpha\sigma_{1}(W_{opt}+I)$ where $\mathcal{R}(UL)$
is the theoretical generalization error (refer Theorem 2). The dashed black
lines, which act as the lower bounds, are given by $\sqrt{\mathcal{R}(UL)}$.

As mentioned in Section 3, we numerically verify Theorem 2 in two out-of-
distribution setups namely small $\alpha$ and large $\alpha$. The application
of our result to the small $\alpha$ case was already presented in the main
paper; see Figure 2(b). Here, we present the additional numerical results when
the value of $\alpha$ 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 $r$ principal components where
$r=25,50,100$ and 150. Figure 10 shows the theoretical bounds on the
generalization error from Theorem 2. Unfortunately, for the large $\alpha$
case, the proposed lower bound in Theorem 2 is negative. However, we
conjecture that $\mathcal{R}(UL)$ is a lower bound instead. The results for
the large $\alpha$ case, shown in Figure 10, 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 2 and Theorem 5.

######  Corollary 5.

If $X_{tst,1}$ and $X_{tst,2}$ are two different test datasets and
$X_{trn}=U\Sigma_{trn}V_{trn}^{T}$ is the training data such that there exists
$L_{i}$ with $\alpha_{i}=\|X_{tst,i}-UL_{i}\|_{F}$, then for
$\mathcal{R}_{i}:=\mathcal{R}(W_{opt},X_{tst,i})$

$\displaystyle|\mathcal{R}_{2}-\mathcal{R}_{1}|$
$\displaystyle\leq(\alpha_{1}^{2}+\alpha_{2}^{2})\sigma_{1}(W_{opt}+I)^{2}$
$\displaystyle\qquad+\frac{\sigma_{1}(\beta)^{2}}{N_{tst}}\frac{\eta_{trn}^{4}r}{(\sigma_{r}(X_{trn})^{2}f(c)+\eta_{trn}^{2})^{2}}\|L_{2}L_{2}^{T}-L_{1}L_{1}^{T}\|_{F}+o\left(\frac{1}{N}\right)$

###  B.2 Independent Identical Test data

Figure 11: Figure showing the generalization error vs 1/c obtained for IID
test data for $r=25,50,100,150$. The theoretical solid line curve is given by
Corollary 6. 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 $\mathcal{D}_{tst}$ with mean zero and covariance $\Sigma$.
Then the generalization error is given by the following corollary.

######  Corollary 6 (IID Test Data).

Let $r<|d-N|$. Let the SVD of $X_{trn}$ be $U\Sigma_{trn}V_{trn}^{T}$, let
$L:=U^{T}X_{tst}$, $\beta_{U}:=U^{T}\beta$, and $c:=d/N$. Under our setup and
Assumptions 1 and 2, with the further assumption that the columns of $L$ are
drawn IID from a distribution with mean zero and Covariance $\Sigma$, the test
error (Equation 1) is given by the following.
If $c<1$ (under-parameterized regime)

$\begin{split}\mathbb{E}_{L}[\mathcal{R}(W_{opt},UL)]&=\eta_{trn}^{4}\left\|\beta_{U}^{T}(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I)^{-1}\Sigma^{1/2}\right\|_{F}^{2}\hskip
221.93158pt\\\
&+\frac{\eta_{tst}^{2}}{d}\frac{c^{2}}{1-c}\operatorname{Tr}\left(\beta_{U}\beta_{U}^{T}\Sigma_{trn}^{2}\left(\Sigma_{trn}^{2}+\frac{1}{\eta_{trn}^{2}}I\right)\left(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I\right)^{-2}\right)+o\left(\frac{1}{N}\right)\end{split}$

If $c>1$ (over-parameterized regime)

$\begin{split}\mathbb{E}_{L}[\mathcal{R}(W_{opt},UL)]&=\eta_{trn}^{4}\left\|\beta_{U}^{T}(\Sigma_{trn}^{2}+\eta_{trn}^{2}I)^{-1}\Sigma^{1/2}\right\|_{F}^{2}\\\
&+\frac{\eta_{tst}^{2}}{d}\frac{c}{c-1}\operatorname{Tr}(\beta_{U}\beta_{U}^{T}(I+\eta_{trn}^{2}\Sigma_{trn}^{-2})^{-1})+O\left(\frac{\|\Sigma_{trn}\|^{2}}{N^{2}}\right)+o\left(\frac{1}{N}\right)\end{split}$

######  Remark 3.

Given any distribution on $\mathcal{V}$, we can consider the diffeomorphism
that changes the basis to $U$. Hence, making assumptions on the distribution
of $L$ versus the distribution of $X_{tst}$ does not cost us any generality.

Figure 11, shows that the theoretical error aligns perfectly with the
empirical result. The model is trained on the CIFAR dataset and tested on 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

(a)

(b)

(c)

Figure 12: 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 6. 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\in\mathbb{R}^{d\times r}$ be a matrix whose columns form an orthonormal
basis for an $r$-dimensional space $\mathcal{V}$. Suppose the data is of the
form $Uz$ for $z\in\mathbb{R}^{r}$ such that the coordinates of $z$ 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.I.D. Training Data With Isotropic Covariance).

Let $c=d/N$ and $c_{r}=r/N$. Then if $c<1$

$\displaystyle\mathbb{E}_{X_{trn}}[\mathcal{R}]$
$\displaystyle=\frac{\eta_{trn}^{4}}{N_{tst}}\|(\Sigma_{trn}^{2}c+\eta_{trn}^{2}I)^{-1}L\|_{F}^{2}$
$\displaystyle\qquad+\eta_{tst}^{2}\frac{r}{d}\frac{1}{1-c}\left(T_{1}(c_{r},\eta_{trn}^{2}/c)+\frac{1}{\eta_{trn}^{2}}T_{2}(c_{r},\eta_{trn}^{2}/c)\right)+o\left(\frac{1}{N}\right)$

and if $c>1$

$\mathbb{E}_{X_{trn}}[\mathcal{R}]=\frac{\eta_{trn}^{4}}{N_{tst}}\|(\Sigma_{trn}^{2}+\eta_{trn}^{2}I)^{-1}L\|_{F}^{2}+\eta_{tst}^{2}\frac{r}{d}\frac{c}{c-1}T_{3}(c_{r},\eta_{trn}^{2})+O\left(\frac{1}{N}\right)$

where $T_{1}(c_{r},z)=T_{3}(cr,z)-zT_{2}(cr,z)$, and

$T_{2}(c_{r},z)=\frac{1+c_{r}+zc_{r}}{2\sqrt{(1-c_{r}+c_{r}z)^{2}+4c_{r}^{2}z}}-\frac{1}{2},\
T_{3}(c_{r},z)=\frac{1}{2}+\frac{1+zc_{r}-\sqrt{(1-c_{r}+zc_{r})^{2}+4c_{r}^{2}z}}{2c_{r}}.$

Figure 12 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 $X_{tst}$ has $\kappa I$ as the covariance and
$X_{trn}$ is as in the previous instantiation Section. Then the generalization
error is given by the following corollary.

######  Corollary 7 (I.I.D. Train and Tests Data With Isotropic Covariance).

Let $c=d/N$ and $c_{r}=r/N$. Then if $c<1$

$\displaystyle\mathbb{E}_{X_{trn}}[\mathcal{R}]$
$\displaystyle=\eta_{trn}^{4}\cdot r\cdot\kappa\cdot
T_{4}(c_{r},\eta_{trn}^{2}/c)$
$\displaystyle\qquad+\frac{r}{d}\frac{1}{1-c}\left(T_{1}(c_{r},\eta_{trn}^{2}/c)+\frac{1}{\eta_{trn}^{2}}T_{2}(c_{r},\eta_{trn}^{2}/c)\right)+o\left(\frac{1}{N}\right)$

and if $c>1$

$\mathbb{E}_{X_{trn}}[\mathcal{R}]=\eta_{trn}^{4}\cdot r\cdot\kappa\cdot
T_{4}(c_{r},\eta_{trn}^{2})+\frac{r}{d}\frac{c}{c-1}T_{3}(c_{r},\eta_{trn}^{2})+O\left(\frac{1}{N}\right)$

where $T_{1}(c_{r},z)=T_{3}(c_{r},z)-zT_{2}(c_{r},z)$, and

$T_{2}(c_{r},z)=\frac{1+c_{r}+zc_{r}}{2\sqrt{(1-c_{r}+c_{r}z)^{2}+4c_{r}^{2}z}}-\frac{1}{2},\
T_{3}(c_{r},z)=\frac{1}{2}+\frac{1+zc_{r}-\sqrt{(1-c_{r}+zc_{r})^{2}+4c_{r}^{2}z}}{2c_{r}},$
$T_{4}(c_{r},z)=\frac{zc_{r}^{2}+c_{r}^{2}+zc_{r}-2c_{r}+1}{2z^{2}c_{r}\sqrt{(1-c_{r}+c_{r}z)^{2}+4c_{r}^{2}z}}-\frac{1}{2z^{2}}\left(1-\frac{1}{c_{r}}\right).$

Figure 13 shows that the theoretical error aligns perfectly with the empirical
result.

Figure 13: Figure showing the generalization error vs 1/c where training and
test datasets are both I.I.D. The theoretical solid curve is obtained from
Corollary 7. The empirical generalization error, shown by markers, is averaged
over 50 trials.

##  Appendix C Proofs

In all proofs, WLOG we assume $d/N=c$ 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 in Theorem 1
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, $d>N$

We derive test error bounds for $\beta=I$ in our problem setting. We also
denote $W_{opt}$ by $W$ in this subsection, for ease of notation. We begin by
defining some notation. Let $X_{trn}=U\Sigma_{trn}V_{trn}^{T}$. Here $U$ is
$d\times r$ with $U^{T}U=I$, $\Sigma_{trn}$ is $r\times r$, and $V_{trn}$ is
$r\times N$. All of the following matrices are full rank.

  1. 1.

$P=-(I-A_{trn}A_{trn}^{\dagger})U\Sigma_{trn}\in\mathbb{R}^{d\times r}$.

  2. 2.

$H=V_{trn}^{T}A_{trn}^{\dagger}\in\mathbb{R}^{r\times d}$

  3. 3.

$Z=I+V_{trn}^{T}A_{trn}^{\dagger}U\Sigma_{trn}\in\mathbb{R}^{r\times r}$

  4. 4.

$K_{1}=HH^{T}+Z(P^{T}P)^{-1}Z^{T}\in\mathbb{R}^{r\times r}$.

  1. 5.

$U$ is $d\times r$ with $U^{T}U=I_{r\times r}$.

  2. 6.

$\Sigma_{trn}$ is $r\times r$, with rank $r$.

  3. 7.

$A_{trn}=\eta_{trn}\tilde{U}\tilde{\Sigma}\tilde{V}^{T}$ with $\tilde{U}$ is
$d\times d$ unitary and $\tilde{\Sigma}$ is $d\times N$.

We will henceforth drop the subscript $A_{trn}$ in the expectation
$\mathbb{E}_{A_{trn}}$.

######  Lemma 1.

If $d>N$ and $A_{trn}$ has full column rank, then

$W:=X_{trn}(X_{trn}+A_{trn})^{\dagger}=U\Sigma_{trn}(P^{T}P)^{-1}Z^{T}K_{1}^{-1}H-U\Sigma_{trn}Z^{-1}HH^{T}K_{1}^{-1}ZP^{\dagger}.$
(2)

###### Proof.

Note that $P$ has full column rank and $A_{trn}$ has rank $N$. Thus, we can
use corollary 2.2 from Wei (2001) to obtain

$(A_{trn}+U\Sigma_{trn}V_{trn}^{T})^{\dagger}=A_{trn}^{\dagger}+A_{trn}^{\dagger}U\Sigma_{trn}P^{\dagger}-(A_{trn}^{\dagger}H^{T}+A_{trn}^{\dagger}U\Sigma_{trn}(P^{T}P)^{-1}Z^{T})K_{1}^{-1}(H+ZP^{\dagger}).$

We are interested in simiplifying the expression. Multiplying this through, we
obtain

$\displaystyle
W=U\Sigma_{trn}V_{trn}^{T}A_{trn}^{\dagger}+U\Sigma_{trn}V_{trn}^{T}A_{trn}^{\dagger}U\Sigma_{trn}P^{\dagger}\\\
\qquad-U\Sigma_{trn}V_{trn}^{T}(A_{trn}^{\dagger}H^{T}+A_{trn}^{\dagger}U\Sigma_{trn}(P^{T}P)^{-1}Z^{T})K_{1}^{-1}(H+ZP^{\dagger}).$

Replacing $V_{trn}^{T}A_{trn}=H$,

$\displaystyle
W=U\Sigma_{trn}H+U\Sigma_{trn}HU\Sigma_{trn}P^{\dagger}-U\Sigma_{trn}V_{trn}^{T}(A_{trn}^{\dagger}H^{T}K_{1}^{-1}H+A_{trn}^{\dagger}H^{T}K_{1}^{-1}ZP^{\dagger}\\\
\qquad+A_{trn}^{\dagger}U\Sigma_{trn}(P^{T}P)^{-1}Z^{T}K_{1}^{-1}H+A_{trn}^{\dagger}U\Sigma_{trn}(P^{T}P)^{-1}Z^{T}K_{1}^{-1}ZP^{\dagger}).$

Through further simplification, we obtain

$\displaystyle\displaystyle W$
$\displaystyle=U\Sigma_{trn}H+U\Sigma_{trn}HU\Sigma_{trn}P^{\dagger}-U\Sigma_{trn}HH^{T}K_{1}^{-1}H-U\Sigma_{trn}HH^{T}K_{1}^{-1}ZP^{\dagger}$
$\displaystyle\qquad\qquad-U\Sigma_{trn}HU\Sigma_{trn}(P^{T}P)^{-1}Z^{T}K_{1}^{-1}H-U\Sigma_{trn}HU\Sigma_{trn}(P^{T}P)^{-1}Z^{T}K_{1}^{-1}ZP^{\dagger}.$

Setting $HU\Sigma_{trn}=Z-I$ yields

$\displaystyle\displaystyle W$
$\displaystyle=U\Sigma_{trn}H+U\Sigma_{trn}ZP^{\dagger}-U\Sigma_{trn}P^{\dagger}-U\Sigma_{trn}HH^{T}K_{1}^{-1}H-U\Sigma_{trn}HH^{T}K_{1}^{-1}ZP^{\dagger}$
$\displaystyle\qquad\qquad-U\Sigma_{trn}Z(P^{T}P)^{-1}Z^{T}K_{1}^{-1}H+U\Sigma_{trn}(P^{T}P)^{-1}Z^{T}K_{1}^{-1}H$
$\displaystyle\quad\qquad\qquad-U\Sigma_{trn}Z(P^{T}P)^{-1}Z^{T}K_{1}^{-1}ZP^{\dagger}+U\Sigma_{trn}(P^{T}P)^{-1}Z^{T}K_{1}^{-1}ZP^{\dagger}.$

Combining terms and replacing $HH^{T}+Z(P^{T}P)^{-1}Z^{T}=K_{1}$, we prove

$\displaystyle\displaystyle W$
$\displaystyle=-U\Sigma_{trn}P^{\dagger}+U\Sigma_{trn}(P^{T}P)^{-1}Z^{T}K_{1}^{-1}H+U\Sigma_{trn}(P^{T}P)^{-1}Z^{T}K_{1}^{-1}ZP^{\dagger},$
$\displaystyle=U\Sigma_{trn}(P^{T}P)^{-1}Z^{T}K_{1}^{-1}H-U\Sigma_{trn}Z^{-1}(K_{1}-Z(P^{T}P)^{-1}Z^{T})K_{1}^{-1}ZP^{\dagger},$
$\displaystyle=U\Sigma_{trn}(P^{T}P)^{-1}Z^{T}K_{1}^{-1}H-U\Sigma_{trn}Z^{-1}HH^{T}K_{1}^{-1}ZP^{\dagger}.$

∎

######  Lemma 2.

For $d>N+r$,
$X_{tst}-WX_{tst}=U\Sigma_{trn}(P^{T}P)^{-1}Z^{T}K_{1}^{-1}\Sigma_{trn}^{-1}L$.

###### Proof.

Here, $X_{tst}=UL$ and $W$ is given by Equation 2. Substituting this, we get

$X_{tst}-WX_{tst}=UL-U\Sigma_{trn}(P^{T}P)^{-1}Z^{T}K_{1}^{-1}HUL+U\Sigma_{trn}Z^{-1}HH^{T}K_{1}^{-1}ZP^{\dagger}UL.$

Note that $P^{\dagger}U=-\Sigma_{trn}^{-1}$ and
$HU\Sigma_{tst}=V_{trn}^{T}A_{trn}^{\dagger}U\Sigma_{trn}\Sigma_{trn}^{-1}\Sigma_{tst}=(Z-I)\Sigma_{trn}^{-1}\Sigma_{tst}$
which yields

$\displaystyle X_{tst}-WX_{tst}$
$\displaystyle=UL-U\Sigma_{trn}(P^{T}P)^{-1}Z^{T}K_{1}^{-1}(Z-I)\Sigma_{trn}^{-1}L-U\Sigma_{trn}Z^{-1}HH^{T}K_{1}^{-1}Z\Sigma_{trn}^{-1}L,$
$\displaystyle=U\Sigma_{trn}Z^{-1}(Z-Z(P^{T}P)^{-1}Z^{T}K_{1}^{-1}(Z-I)-HH^{T}K_{1}^{-1}Z)\Sigma_{trn}^{-1}L,$
$\displaystyle=U\Sigma_{trn}Z^{-1}(Z-(Z-I)+HH^{T}K_{1}^{-1}(Z-I)-HH^{T}K_{1}^{-1}Z)\Sigma_{trn}^{-1}L,$
$\displaystyle=U\Sigma_{trn}Z^{-1}(K_{1}-HH^{T})K_{1}^{-1}\Sigma_{trn}^{-1}L,$
$\displaystyle=U\Sigma_{trn}(P^{T}P)^{-1}Z^{T}K_{1}^{-1}\Sigma_{trn}^{-1}L.$

∎

######  Lemma 3.

Let $a^{T}b=0$, and $Q$ is a Haar uniformly random orthogonal matrix. Let
$\tilde{a}=Qa$, and $\tilde{b}=Qb$, then
$\mathbb{E}[\tilde{a}_{i}\tilde{b}_{i}]=0$.

###### Proof.

We note that $\mathbb{E}[\tilde{a}^{T}\tilde{b}]=\mathbb{E}[a^{T}b]=0$. Then
we get the result from symmetry. ∎

######  Lemma 4.

For $c>1$, we have that
$\displaystyle\mathbb{E}[HH^{T}]=\frac{c}{\eta_{trn}^{2}(c-1)}I_{r}+o(1)$ and
the variance of each entry is $O(1/(\eta_{trn}^{4}N))$. For $c<1$, we have
that
$\displaystyle\mathbb{E}[HH^{T}]=\frac{c^{2}}{\eta_{trn}^{2}(1-c)}I_{r}+o(1)$
and the variance is $O(1/(\eta_{trn}^{4}d))$.

###### Proof.

Here we see that
$HH^{T}=V_{trn}^{T}A_{trn}^{\dagger}(A_{trn}^{\dagger})^{T}V_{trn}=V_{trn}^{T}(A_{trn}^{T}A_{trn})^{\dagger}V_{trn}.$
Thus, if $V_{trn}=[v_{1}\cdots v_{r}]$. Then we see that $HH^{T}$ is an
$r\times r$ matrix such that

$(HH^{T})_{ij}=v_{i}^{T}(A_{trn}^{T}A_{trn})^{\dagger}v_{j}=v_{i}^{T}\tilde{V}\frac{1}{\eta_{trn}^{2}}\tilde{\Sigma}^{-2}\tilde{V}^{T}v_{j}^{T}.$

Since $\tilde{V}$ is Haar uniformly random and independent of
$\tilde{\Sigma}$, using Lemma 3 for $i\neq j$, we see that the expectation is
0. On the other hand if $i=j$, then using Lemma 6 from Sonthalia & Nadakuditi
(2023), with $p=N$, $q=d$ and $A=\frac{1}{\eta_{trn}}A_{trn}$, we get that for
$c>1$ we have that
$\displaystyle\mathbb{E}[v_{i}^{T}(A_{trn}^{T}A_{trn})^{\dagger}v_{i}]=\frac{c}{\eta_{trn}^{2}(c-1)}+o(1).$
while for $c<1$,
$\displaystyle\mathbb{E}[v_{i}^{T}(A_{trn}^{T}A_{trn})^{\dagger}v_{i}]=\frac{c^{2}}{\eta_{trn}^{2}(1-c)}+o(1).$
For the variance, let
$A_{trn}=\eta_{trn}\tilde{U}\tilde{\Sigma}\tilde{V}^{T}$, then we have that

$\displaystyle v_{i}^{T}(A_{trn}^{T}A_{trn})^{\dagger}v_{j}$
$\displaystyle=\frac{1}{\eta_{trn}^{2}}v_{i}^{T}\tilde{V}\tilde{\Sigma}^{-2}\tilde{V}^{T}v_{j}=\frac{1}{\eta_{trn}^{2}}a^{T}\tilde{\Sigma}^{-2}b=\sum_{i=1}^{N}\frac{1}{\eta_{trn}^{2}}\frac{1}{\tilde{\sigma}_{i}^{2}}a_{i}b_{i}.$

Where $a,b$ are orthogonal vectors (when $i\neq j$). Then for computing the
variance when $c>1$,

$\displaystyle\mathbb{E}\left[\left(v_{i}^{T}(A_{trn}^{T}A_{trn})^{\dagger}v_{j}\right)^{2}\right]$
$\displaystyle=\mathbb{E}\left[\left(\frac{1}{\eta_{trn}^{2}}\sum_{i=1}^{N}\frac{1}{\tilde{\sigma}_{i}^{2}}a_{i}b_{i}\right)^{2}\right]$
$\displaystyle=\frac{1}{\eta_{trn}^{4}}\mathbb{E}\left[\sum_{i=1}^{N}\sum_{j=1}^{N}\frac{1}{\tilde{\sigma}_{i}^{2}\tilde{\sigma}_{j}^{2}}a_{i}b_{i}a_{j}b_{j}\right]$
$\displaystyle=\left(\frac{c^{2}}{\eta_{trn}^{4}(c-1)^{2}}+o(1)\right)\mathbb{E}\left[\left(\sum_{i=1}^{N}a_{i}b_{i}\right)\left(\sum_{j=1}^{N}a_{j}b_{j}\right)\right]$
$\displaystyle\qquad+\left(\frac{c^{3}}{\eta_{trn}^{4}(c-1)^{3}}-\frac{c^{2}}{\eta_{trn}^{4}(c-1)^{2}}+o(1)\right)\sum_{i=1}^{N}\mathbb{E}[a_{i}^{2}b_{i}^{2}]$
$\displaystyle=0+\left(\frac{c^{2}}{\eta_{trn}^{4}(c-1)^{3}}+o(1)\right)\sum_{i=1}^{N}\frac{1}{N^{2}}+o\left(\frac{1}{N}\right)$
$\displaystyle=\frac{c^{2}}{\eta_{trn}^{4}(c-1)^{3}}\frac{1}{N}+o\left(\frac{1}{N}\right).$

Here even though $a,b$ are not independent, because of the smaller variance in
the entries, the error is absorbed in the $o\left(\frac{1}{N}\right)$ term.
When $i=j$, we use the same proof Sonthalia & Nadakuditi (2023), to see that
the variance is at most $O\left(\frac{1}{\eta^{4}_{trn}N}\right)$. A very
similar computation follows for the variance when $c<1$. ∎

We prove a general result on inverses of matrices that whose expected norms
are $\Omega(1)$.

######  Lemma 5.

If $\|\mathbb{E}[X_{N}]\|=\Omega(1)$ as $N$ grows and
$\mathrm{Var}((X_{N})_{ij})=s_{N}$, then
$\mathbb{E}[X_{N}^{-1}]=\mathbb{E}[X_{N}]^{-1}+O(s_{N})$. Additionally, if
$\mathrm{Var}((X_{N}-\mathbb{E}[X_{N}])_{ij}^{2})=O(t_{N})$, then
$\mathrm{Var}((X_{N}^{-1})_{ij})=O(s_{N}+t_{N})$.

###### Proof.

Let $\delta X_{N}=X_{N}-\mathbb{E}[X_{n}]$. Notice that $\delta
X_{N}=O_{P}(s_{N})$ and $\mathbb{E}[\delta X_{N}]=0$. Additionally, by the
Taylor expansion $(Y+\delta Y)^{-1}=Y^{-1}+Y^{-1}\delta YY^{-1}+O(\delta
Y^{2})$ we have that

$X_{N}^{-1}=\mathbb{E}[X_{N}]^{-1}+\mathbb{E}[X_{N}]^{-1}\delta
X_{N}\mathbb{E}[X_{N}]^{-1}+O(\delta X_{N}^{2}).$

In particular, since $\mathbb{E}[X_{n}]^{-1}=O(1)$, we have

$O(\mathbb{E}[X_{N}^{-1}]=\mathbb{E}[X_{N}]^{-1}+O(\mathrm{Var}((X_{N})_{ij}))=\mathbb{E}[X_{N}]^{-1}+O(s_{N}).$

Finally, note that $\mathrm{Var}((\delta X_{N}^{2})_{ij})=O(t_{N})$ by
assumption. So,

$\mathrm{Var}((X_{N}^{-1})_{ij})=\mathrm{Var}((\mathbb{E}[X_{N}]^{-1}\delta
X_{N}\mathbb{E}[X_{N}]^{-1})_{ij})+O(\mathrm{Var}((\delta
X_{N}^{2})_{ij}))=O(s_{N}+t_{N})$

since $\mathbb{E}[X_{N}]^{-1}=O(1)$. ∎

######  Lemma 6.

For $c>1$, we claim that
$\mathbb{E}[\Sigma_{trn}^{-1}P^{T}P\Sigma_{trn}^{-1}]=\left(1-\frac{1}{c}\right)I_{r}$,
each entry has variance $O\left(\frac{1}{d}\right)$, and

$\mathbb{E}[\Sigma_{trn}(P^{T}P)^{-1}\Sigma_{trn}]=\frac{c}{c-1}I_{r}+O\left(\frac{1}{{d}}\right).$

with element-wise variance $O(1/d)$.

###### Proof.

Recall that $P=-(I-A_{trn}A_{trn}^{\dagger})U\Sigma_{trn}$ Thus, we have that

$\displaystyle P^{T}P$
$\displaystyle=\Sigma_{trn}^{T}U^{T}(I-A_{trn}A_{trn}^{\dagger})U\Sigma_{trn}.$
$\displaystyle=\Sigma_{trn}^{T}\Sigma_{trn}-\Sigma_{trn}^{T}U^{T}A_{trn}A_{trn}^{\dagger}U\Sigma_{trn}$
$\displaystyle=\Sigma_{trn}^{T}\Sigma_{trn}-\Sigma_{trn}^{T}U^{T}\tilde{U}\tilde{\Sigma}\tilde{\Sigma}^{\dagger}\tilde{U}^{T}U\Sigma_{trn}$
$\displaystyle=\Sigma_{trn}^{T}\Sigma_{trn}-\Sigma_{trn}^{T}R\begin{bmatrix}I_{N}&0\\\
0&0_{d-N}\end{bmatrix}R^{T}\Sigma_{trn}.$

Where $R$ is a uniformly random $r\times d$ unitary matrix. Then by symmetry
(of the sign of rows of $R$), we have that

$\mathbb{E}[P^{T}P]=\Sigma_{trn}^{2}-\Sigma_{trn}^{T}\left(\frac{1}{c}I_{r}\right)\Sigma_{trn}=\left(1-\frac{1}{c}\right)\Sigma_{trn}^{2}.$

So, we have that

$\mathbb{E}\left[\Sigma_{trn}^{-1}P^{T}P\Sigma_{trn}^{-1}\right]=U^{T}\left(I-\mathbb{E}\left[A_{trn}A_{trn}^{\dagger}\right]\right)U=\left(1-\frac{1}{c}\right)I_{r}.$

Thus to compute the variance, we first compute the variance of
$(A_{trn}A_{trn}^{\dagger})_{ij}$. For this, we first note that

$\begin{bmatrix}\frac{1}{c}I_{N}&0\\\
0&0\end{bmatrix}=\mathbb{E}\left[\tilde{U}\tilde{\Sigma}\tilde{\Sigma}^{\dagger}\tilde{U}^{T}\right]=\mathbb{E}\left[A_{trn}A_{trn}^{\dagger}\right]=\mathbb{E}\left[A_{trn}A_{trn}^{\dagger}A_{trn}A_{trn}^{\dagger}\right].$

The first equality follows from the symmetry of the signs of the rows of
$\tilde{U}$. Then we can see that

$\sum_{k}^{d}(A_{trn}A_{trn}^{\dagger})_{ik}^{2}=\begin{cases}\frac{1}{c}&i\leq
N\\\ 0&i>N\end{cases}.$

From Lemma 14 in Sonthalia & Nadakuditi (2023), we have that
$\mathbb{E}[(A_{trn}A_{trn}^{\dagger})^{2}_{ii}]=\frac{1}{c^{2}}+\frac{2}{cd}+o(1)$.
Then combining this with the computation above and using symmetry, we have
that for $i\neq j$ and $\min(i,j)\leq N$

$\mathbb{E}[(A_{trn}A_{trn}^{\dagger})^{2}_{ij}]=\frac{1}{N-1}\left(\frac{1}{c}-\frac{1}{c^{2}}+\frac{2}{cd}+o(1)\right).$

Now consider the other (full) SVD of $X_{trn}$ given by $\hat{U}_{d\times
d}\hat{\Sigma}_{d\times N}\hat{V}^{T}_{N\times N}$. Note that the top left
$r\times r$ block of $\hat{\Sigma}$ is $\Sigma_{trn}$, and we can choose
$\hat{U}$ so that the first $r$ columns of $\hat{U}$ give $U$. Note that since
$\hat{U}^{T}\tilde{U}$ is still uniformly random, the symmetry argument above
follows for $\hat{U}^{T}A_{trn}A_{trn}^{\dagger}\hat{U}$. Additionally, for
$i,j\leq r$,
$(\hat{U}^{T}A_{trn}A_{trn}^{\dagger}\hat{U})_{ij}=(U^{T}A_{trn}A_{trn}^{\dagger}U)_{ij}$
Thus, we see that for $i,j\leq r$

$\mathbb{E}\left[(U^{T}A_{trn}A_{trn}^{\dagger}U)_{ij}^{2}\right]=\frac{1}{N-1}\left(\frac{1}{c}-\frac{1}{c^{2}}+\frac{2}{cd}+o(1)\right),$

while for $i=j$, we get that it is $O\left(\frac{1}{N}\right)$ by Lemma 14 of
Sonthalia & Nadakuditi (2023). Thus, finally, we have that arranged as a
matrix

$\mathbb{E}\left[(\Sigma_{trn}^{-1}P^{T}P\Sigma_{trn}^{-1})\odot(\Sigma_{trn}^{-1}P^{T}P\Sigma_{trn}^{-1})\right]=O\left(\frac{1}{d}\right).$

By an analogous symmetry argument, since
$(A_{trn}A_{trn}^{\dagger})^{i}=A_{trn}A_{trn}^{\dagger}$ for any $i$, we can
show that

$\mathrm{Var}\left((U^{T}A_{trn}A_{trn}^{\dagger}U)_{ij}^{2}\right)=O\left(\frac{1}{d}\right).$

We can in principle show a faster decay for this with a more involved
argument, but this is enough for our purposes. We can now apply Lemma 5 with
$X_{N}=I-(U^{T}A_{trn}A_{trn}^{\dagger}U)$ to see that

$\mathbb{E}[\Sigma_{trn}(P^{T}P)^{-1}\Sigma_{trn}]=\frac{c}{c-1}I_{r}+O\left(\frac{1}{d}\right)$

and has element-wise variance $O(1/d)$. ∎

######  Lemma 7.

We have that $\displaystyle\mathbb{E}[Z]=I\text{ and
}\mathrm{Var}(Z_{ij})=O\left(\frac{\|\Sigma_{trn}\|^{2}}{\eta_{trn}^{2}d}\right).$
Further, $E[Z\Sigma_{trn}^{-1}]=E[\Sigma_{trn}^{-1}Z]=\Sigma_{trn}^{-1}$ and
each element has variance $O\left(\frac{1}{d}\right)$. Finally,

$\mathbb{E}[Z^{-1}]=I+O\left(\frac{\|\Sigma_{trn}\|^{2}}{d}\right)\text{ with
}\mathrm{Var}((Z^{-1})_{ij})=O\left(\frac{\|\Sigma_{trn}\|^{2}}{d}+\frac{\|\Sigma_{trn}\|^{4}}{d^{2}}\right).$

###### Proof.

The element-wise variance and expectation of $Z$ can be computed exactly as in
the proof of Lemma 11 in Sonthalia & Nadakuditi (2023). Specifically, by
considering the row $u_{j}$ of $U$ and the row $v_{i}$ of $V$, treating
$Z_{ij}$ as $\beta$, and replacing $\theta_{trn}$ by $\sigma_{j}$. The
expressions for the element-wise expectation and variance of
$Z\Sigma_{trn}^{-1}$ and $\Sigma_{trn}^{-1}Z$ immediately follow from those of
$Z$ and the fact that $\sigma_{i}/\sigma_{j}=\Theta(1)$ by Assumption 1.

For $Z^{-1}$, we continue the computation using $Z_{ij}=1+T_{ij}$ with
$\displaystyle
T_{ij}=\sigma_{j}\sum_{k=1}^{\min(d,N)}\frac{1}{\lambda_{k}}a_{k}b_{k}$ with
$a$ and $b$ obtained using $v_{j}$ and $u_{i}$ respectively, and $\lambda_{k}$
a singular value of $A_{trn}$. It is easy to check that
$\displaystyle\mathrm{Var}(T_{ij}^{2})=O\left(\frac{\|\Sigma_{trn}\|^{4}}{N^{2}}\right)$
using a symmetry argument for $a_{k}$ and $b_{k}$ and the fact that
$\mathbb{E}[1/\lambda_{k}^{4}]=O(1)$ by Lemma 5 of Sonthalia & Nadakuditi
(2023). Now we can use Lemma 5 to conclude that

$\mathbb{E}[Z^{-1}]=I+O\left(\frac{\|\Sigma_{trn}\|^{2}}{d}\right)\text{ with
}\mathrm{Var}((Z^{-1})_{ij})=O\left(\frac{\|\Sigma_{trn}\|^{2}}{d}+\frac{\|\Sigma_{trn}\|^{4}}{d^{2}}\right).$

∎

######  Lemma 8.

For $c>1$,
$\mathbb{E}[K_{1}]=\frac{1}{\eta_{trn}^{2}}\frac{c}{c-1}I_{r}+\frac{c}{c-1}\Sigma_{trn}^{-2}+o(1)$
with element-wise variance $O(1/d)$. Further,

$\mathbb{E}[K_{1}^{-1}]=\eta_{trn}^{2}\left(1-\frac{1}{c}\right)\left({\eta_{trn}^{2}}\Sigma_{trn}^{-2}+I_{r}\right)^{-1}+o(1)$

with element-wise variance $O(1/d)$.

###### Proof.

From Lemma 6, we have that
$\displaystyle\mathbb{E}[\Sigma_{trn}(P^{T}P)^{-1}\Sigma_{trn}]=\frac{c}{c-1}I_{r}+O\left(\frac{1}{d}\right).$
Recall that

$K_{1}=HH^{T}+Z(P^{T}P)^{-1}Z^{T}=HH^{T}+Z\Sigma_{trn}^{-1}(\Sigma_{trn}(P^{T}P)^{-1}\Sigma_{trn})\Sigma_{trn}^{-1}Z^{T}.$

Then recall from Lemma 4 that

$\mathbb{E}[HH^{T}]=\frac{1}{\eta_{trn}^{2}}\frac{c}{c-1}I_{r}+o(1).$

For the second term in the expression for $K_{1}$, we want to use Lemmas 6 and
7, but they give expectations of each term separately. Note that

$|\mathbb{E}[XY]-\mathbb{E}[X]\mathbb{E}[Y]|=|Cov(X,Y)|\leq\sqrt{\mathrm{Var}(X)\mathrm{Var}(Y)}$

and also note the following fact, from Bohrnstedt & Goldberger (1969).

$\displaystyle Cov(XY,WZ)$
$\displaystyle=\mathbb{E}X\mathbb{E}WCov(Y,Z)+\mathbb{E}Y\mathbb{E}ZCov(X,W)+\mathbb{E}X\mathbb{E}ZCov(Y,W)+$
$\displaystyle\qquad\mathbb{E}Y\mathbb{E}WCov(X,Z)+Cov(X,W)Cov(Y,Z)+Cov(Y,W)Cov(X,Z)$

We use the facts above along with Lemmas 6 and 7 to compute the expectation.
Specifically, the second term in $K_{1}$ is the product of three terms
$Z\Sigma_{trn}^{-1}$, $(\Sigma_{trn}(P^{T}P)^{-1}\Sigma_{trn})$, and
$\Sigma_{trn}^{-1}Z^{T}$. Hence we need the first fact to replace the
expectation of the product of two terms 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

$\mathbb{E}[K_{1}]=\frac{1}{\eta_{trn}^{2}}\frac{c}{c-1}I_{r}+\frac{c}{c-1}\Sigma_{trn}^{-2}+O\left(\frac{1}{d}\right)+o(1)$

For the element-wise variance, consider $\delta
K_{1}=K_{1}-\mathbb{E}[K_{1}]$. We cover the $i\neq j$ case. The $i=j$ case is
analogous. From the proofs of Lemmas 4, 6, and 7, we have $Z_{ij}=I+T_{ij}$
and
$(\Sigma_{trn}(P^{T}P)^{-1}\Sigma_{trn})_{ij}=U^{T}A_{trn}A_{trn}^{\dagger}U)_{ij}$.
The expanding the product, we get that

$\displaystyle(\delta K_{1})_{ij}$
$\displaystyle=\left(v_{i}(A_{trn}^{T}A_{trn})^{\dagger}v_{j}\right)+O\left((U^{T}A_{trn}A_{trn}^{\dagger}U)_{ij}\right)+O\left((U^{T}A_{trn}A_{trn}^{\dagger}U)_{ij}^{2}\right)+O(T_{ij})$
$\displaystyle+O\left(\sum_{k=1}^{N}T_{ik}(U^{T}A_{trn}A_{trn}^{\dagger}U)_{kj}\right)+O\left(\sum_{k=1}^{N}T_{ik}(U^{T}A_{trn}A_{trn}^{\dagger}U)_{kj}^{2}\right)+O\left(\sum_{k=1}^{N}T_{ik}T_{kj}\right)$
$\displaystyle+O\left(\sum_{k,l=1}^{d}T_{ik}(U^{T}A_{trn}A_{trn}^{\dagger}U)_{kl}T_{lj}\right)+O\left(\sum_{k,l=1}^{d}T_{ik}(U^{T}A_{trn}A_{trn}^{\dagger}U)_{kl}^{2}T_{lj}\right)$

Then since

$\mathrm{Var}(XY)=Cov(X^{2},Y^{2})+(\mathrm{Var}(X)+(\mathbb{E}X)^{2})(\mathrm{Var}(Y)+(\mathbb{E}Y)^{2})-(Cov(X,Y)+\mathbb{E}X\mathbb{E}Y)^{2}$

using this for terms five through nine, we get that $\mathrm{Var}\left((\delta
K_{1})_{ij}\right)=O\left(\frac{1}{d}\right).$

For the inverse, we cover the $i\neq j$ case again. The $i=j$ case is
analogous. We can perform an analogous computation to the one in the proof of
Lemma 4 to get that

$\mathrm{Var}\left((v_{i}(A_{trn}^{T}A_{trn})^{\dagger}v_{j})^{2}\right)=O\left(\frac{1}{N}\right),$

using the fact that $\mathbb{E}\left[\frac{1}{\lambda^{4}}\right]=O(1)$ for a
random eigenvalue $\lambda_{k}$ of $A_{trn}$. We also use the fact that
$(A_{trn}A_{trn}^{\dagger})^{p}=A_{trn}A_{trn}^{\dagger}$ for any $p$ and a
symmetry argument analogous to the one in the proof of Lemma 6 to note that

$\mathbb{E}\left[(U^{T}A_{trn}A_{trn}^{\dagger}U)_{ij}^{p}\right]=O\left(\frac{1}{d}\right)\qquad
p=2,\ldots,8.$

One can also check by the arguments in the proof of Lemma 7 that

$\mathbb{E}\left[T_{ij}^{2p}\right]=O\left(\frac{\sigma_{i}^{p}\sigma_{j}^{p}}{d^{p}}\right)=O(1).$

These together with the facts about $\mathrm{Var}(XY)$ and $Cov(XY,ZW)$ above
establish after a tedious but straightforward computation that

$\mathrm{Var}((\delta K_{1})_{ij}^{2})=O\left(\frac{1}{d}\right).$

We can now use Lemma 5 to establish that

$\displaystyle\mathbb{E}[K_{1}^{-1}]$
$\displaystyle=\eta_{trn}^{2}\left(1-\frac{1}{c}\right)\left({\eta_{trn}^{2}}\Sigma_{trn}^{-2}+I_{r}\right)^{-1}+O\left(\frac{1}{d}\right)+o(1)$
$\displaystyle=\eta_{trn}^{2}\left(1-\frac{1}{c}\right)\left({\eta_{trn}^{2}}\Sigma_{trn}^{-2}+I_{r}\right)^{-1}+o(1)$

and $\mathrm{Var}((K_{1}^{-1})_{ij})=O\left(\frac{1}{d}\right).$

∎

######  Lemma 9.

When $c>1$, we have for $W=W_{opt}$ that

$\mathbb{E}[\|W\|_{F}^{2}]=\frac{c}{c-1}\operatorname{Tr}(\Sigma_{trn}^{2}(\Sigma_{trn}^{2}+\eta_{trn}^{2}I)^{-1})+O\left(\frac{\|\Sigma_{trn}\|^{2}}{{d}}\right)+o(1).$

###### Proof.

We first use the estimates for the expectations from Lemmas 4, 6, 7, and 8 to
get an estimate for the expectation of $\|W\|_{F}^{2}$. 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

$\|W\|_{F}^{2}=\operatorname{Tr}(W^{T}W)$

Using Lemma 1, we see that the trace has three terms. The first term is

$\operatorname{Tr}\left(H^{T}(K_{1}^{-1})^{T}Z((P^{T}P)^{-1})^{T}\Sigma_{trn}^{T}U^{T}U\Sigma_{trn}(P^{T}P)^{-1}Z^{T}K_{1}^{-1}H\right).$

Here we have that $U$ is $d\times r$ with orthonormal columns. Hence we get
that $U^{T}U=I$. Then since the trace is invariant under cyclic permutations,
we get the following term

$\operatorname{Tr}\left((\Sigma_{trn}(P^{T}P)^{-1}\Sigma_{trn})(\Sigma_{trn}^{-1}Z^{T})K_{1}^{-1}HH^{T}(K_{1}^{-1})^{T}(Z\Sigma_{trn}^{-1})(\Sigma_{trn}(P^{T}P)^{-1}\Sigma_{trn})^{T}\right).$

Now we use our random matrix theory estimates for various terms in the
product. From Lemma 7, we have that
$\mathbb{E}_{A_{trn}}[Z\Sigma_{trn}^{-1}]=\Sigma_{trn}^{-1}$. Thus, that first
term’s expectation can be estimated by

$\operatorname{Tr}\left((\Sigma_{trn}(P^{T}P)^{-1}\Sigma_{trn})\Sigma_{trn}^{-1}K_{1}^{-1}HH^{T}(K_{1}^{-1})^{T}\Sigma_{trn}^{-1}(\Sigma_{trn}(P^{T}P)^{-1}\Sigma_{trn})^{T}\right).$

Then using Lemma 4, we can further estimate this by

$\frac{1}{\eta_{trn}^{2}}\frac{c}{c-1}\operatorname{Tr}\left((\Sigma_{trn}(P^{T}P)^{-1}\Sigma_{trn})\Sigma_{trn}^{-1}K_{1}^{-1}(K_{1}^{-1})^{T}\Sigma_{trn}^{-1}(\Sigma_{trn}(P^{T}P)^{-1}\Sigma_{trn})^{T}\right)+o(1).$

Here, the error contribution of the $o(1)$ error from Lemma 4 is still $o(1)$
since we will see that all the other estimates are $O(1)$. Then we use Lemma
6, to replace $\Sigma_{trn}(P^{T}P)^{-1}\Sigma_{trn}$ to get

$\frac{1}{\eta_{trn}^{2}}\frac{c}{c-1}\left(1-\frac{1}{c}\right)^{-2}\operatorname{Tr}\left(\Sigma_{trn}^{-1}K_{1}^{-1}(K_{1}^{-1})^{T}(\Sigma_{trn}^{T})^{-1}\right)+o(1).$

Finally, we use Lemma 8 to replace the last term and get

$\frac{1}{\eta_{trn}^{2}}\frac{c}{c-1}\left(\frac{c}{c-1}\right)^{2}\operatorname{Tr}\left(\Sigma_{trn}^{-2}\eta_{trn}^{4}\left(1-\frac{1}{c}\right)^{2}\left(I_{r}+\eta_{trn}^{2}\Sigma_{trn}^{-2}\right)^{-2}\right)+o(1).$

This immediately simplifies to

$\displaystyle\eta_{trn}^{2}\frac{c}{c-1}\operatorname{Tr}\left(\Sigma_{trn}^{2}(\Sigma_{trn}^{2}+\eta_{trn}^{2}I_{r})^{-2}\right)+o(1).$
(3)

The second term in $\operatorname{Tr}(W^{T}W)$ is

$-2\operatorname{Tr}\left(H^{T}(K_{1}^{-1})^{T}Z^{T}((P^{T}P)^{-1})^{T}\Sigma_{trn}^{T}U^{T}U\Sigma_{trn}Z^{-1}HH^{T}ZP^{\dagger}\right).$

We can rearrange this using cyclic invariance to

$-2\operatorname{Tr}\left((K_{1}^{-1})^{T}Z^{T}\Sigma_{trn}^{-1}(\Sigma_{trn}(P^{T}P)^{-1}\Sigma_{trn})^{T}\Sigma_{trn}Z^{-1}HH^{T}ZP^{\dagger}H^{T}\right).$

Let us focus on the $P^{\dagger}H^{T}$ term. Since $P^{T}P$ is invertible, we
have that $P$ has full column rank. Hence we have that

$P^{\dagger}=(P^{T}P)^{-1}P^{T}.$

Further, since $P=-(I-A_{trn}A_{trn}^{\dagger})U\Sigma_{trn}$ and
$H=V_{trn}^{T}A_{trn}^{\dagger}$, we have that

$P^{\dagger}H^{T}=(P^{T}P)^{-1}\Sigma_{trn}^{T}U^{T}(I-A_{trn}A_{trn}^{\dagger})(A_{trn}^{\dagger})^{T}V_{trn}.$

Finally, we notice that

$A_{trn}A_{trn}^{\dagger}(A_{trn}^{\dagger})^{T}=(A_{trn}^{\dagger})^{T}.$

Thus, we have that

$P^{\dagger}H^{T}=(P^{T}P)^{-1}\Sigma_{trn}^{T}U^{T}(I-A_{trn}A_{trn}^{\dagger})(A_{trn}^{\dagger})^{T}V_{trn}=0.$

Finally, the last term in $\operatorname{Tr}(W^{T}W)$ is

$\operatorname{Tr}\left((P^{\dagger})^{T}Z^{T}(K_{1}^{-1})^{T}HH^{T}(Z^{-1})^{T}\Sigma_{trn}^{T}U^{T}U\Sigma_{trn}Z^{-1}HH^{T}K_{1}^{-1}ZP^{\dagger}\right).$

We note that

$P^{\dagger}(P^{\dagger})^{T}=(P^{T}P)^{\dagger}=(P^{T}P)^{-1}.$

We use this observation along with cyclic invariance to get that the last term
is the same as

$\operatorname{Tr}\left((K_{1}^{-1})^{T}HH^{T}\Sigma_{trn}^{2}Z^{-1}HH^{T}K_{1}^{-1}Z\Sigma_{trn}^{-1}(\Sigma_{trn}(P^{T}P)^{-1}\Sigma_{trn})\Sigma_{trn}^{-1}Z^{T}\right).$

We again use Lemmas 4 and 7 to get that its expectation is estimated by

$\frac{1}{\eta_{trn}^{4}}\left(\frac{c}{c-1}\right)^{2}\operatorname{Tr}\left((K_{1}^{-1})^{T}\Sigma_{trn}^{2}K_{1}^{-1}\Sigma_{trn}^{-1}(\Sigma_{trn}(P^{T}P)^{-1}\Sigma_{trn})\Sigma_{trn}^{-1}\right)+O\left(\frac{\|\Sigma_{trn}\|^{2}}{d}\right)+o(1).$

The contribution of the $O\left(\frac{\|\Sigma_{trn}\|^{2}}{d}\right)$ error
from Lemma 7 is still $O\left(\frac{\|\Sigma_{trn}\|^{2}}{d}\right)$ since the
estimate for the expectation is $O(1)$. We now use Lemma 6, and 8 to see that
the final term’s expectation can be estimated by

$\displaystyle\frac{1}{\eta_{trn}^{4}}\left(\frac{c}{c-1}\right)^{3}\eta_{trn}^{4}\left(\frac{c-1}{c}\right)^{-2}(I_{r}+\eta_{trn}\Sigma_{trn}^{-2})^{-2}+O\left(\frac{\|\Sigma_{trn}\|^{2}}{d}\right)+o(1)$
$\displaystyle=$
$\displaystyle\frac{c}{c-1}\operatorname{Tr}(\Sigma_{trn}^{4}(\Sigma_{trn}^{2}+\eta_{trn}^{2}I_{r})^{-2})+O\left(\frac{\|\Sigma_{trn}\|^{2}}{d}\right)+o(1).$
(5)

Finally, to bound the deviation from this estimate, note that for real valued
random variables $X,Y$ we have that
$|\mathbb{E}[XY]-\mathbb{E}[X]\mathbb{E}[Y]|=|Cov(X,Y)|\leq\sqrt{\mathrm{Var}(X)\mathrm{Var}(Y)}$
and for real valued random variables $X,Y,Z,W$, we have the following fact,
from Bohrnstedt & Goldberger (1969).

$\displaystyle Cov(XY,WZ)$
$\displaystyle=\mathbb{E}X\mathbb{E}WCov(Y,Z)+\mathbb{E}Y\mathbb{E}ZCov(X,W)+\mathbb{E}X\mathbb{E}ZCov(Y,W)+$
$\displaystyle\qquad\mathbb{E}Y\mathbb{E}WCov(X,Z)+Cov(X,W)Cov(Y,Z)+Cov(Y,W)Cov(X,Z)$

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)$ except
for those of $Z^{-1}$ and $Z$, which are both $O(1)$ whenever
$\Sigma_{trn}=O(\sqrt{d})$, the estimation error is $O(1/\sqrt{d})=o(1)$.

So, we can conclude that each of the estimates in equations 3, C.1.1 and 5
have error $o(1)$. Combining the terms together, we get from equations 3,
C.1.1 and 5 that

$\displaystyle\|W\|_{F}^{2}$
$\displaystyle=\frac{c}{c-1}\operatorname{Tr}\left(\Sigma_{trn}^{2}(\Sigma_{trn}^{2}+\eta_{trn}^{2}I_{r})(\Sigma_{trn}+\eta_{trn}^{2}I_{r})^{-2}\right)+O\left(\frac{\|\Sigma_{trn}\|^{2}}{d}\right)+o(1)$
$\displaystyle=\frac{c}{c-1}\operatorname{Tr}(\Sigma_{trn}^{2}(\Sigma_{trn}^{2}+\eta_{trn}^{2}I)^{-1})+O\left(\frac{\|\Sigma_{trn}\|^{2}}{d}\right)+o(1).$

∎

######  Theorem 7.

When $d>N+r$ and $\beta=I$, then the test error $\mathcal{R}(W,X_{tst})$ for
$W=W_{opt}$ is given by

$\frac{\eta_{trn}^{4}}{N_{tst}}\|\left(\Sigma_{trn}^{2}+\eta_{trn}^{2}I\right)^{-1}L\|_{F}^{2}+\frac{\eta_{tst}^{2}}{d}\frac{c}{c-1}\operatorname{Tr}(\Sigma_{trn}^{2}(\Sigma_{trn}^{2}+\eta_{trn}^{2}I)^{-1})+O\left(\frac{\|\Sigma_{trn}\|^{2}}{d^{2}}\right)+o\left(\frac{1}{d}\right).$

###### Proof.

From Lemmas 1 and 2, we have that

$\mathcal{R}(W,X_{tst})=\mathbb{E}\left[\frac{1}{N_{tst}}\|U\Sigma_{trn}(P^{T}P)^{-1}Z^{T}K_{1}^{-1}\Sigma_{trn}^{-1}L\|_{F}^{2}+\frac{\eta_{tst}^{2}}{d}\|W\|_{F}^{2}\right]$

To compute the expectation of the first term, we observe that it is given by

$\frac{1}{N_{tst}}Tr(U\Sigma_{trn}(P^{T}P)^{-1}Z^{T}K_{1}^{-1}\Sigma_{trn}^{-1}LL^{T}\Sigma_{trn}^{-1}K_{1}^{-1}Z(P^{T}P)^{-1}\Sigma_{trn}U^{T}).$

We apply cyclic invariance to get that it is the same as

$\frac{1}{N_{tst}}Tr(\Sigma_{trn}^{-1}K_{1}^{-1}Z\Sigma_{trn}^{-1}(\Sigma_{trn}(P^{T}P)^{-1}\Sigma_{trn})(\Sigma_{trn}(P^{T}P)^{-1}\Sigma_{trn})\Sigma_{trn}^{-1}Z^{T}K_{1}^{-1}\Sigma_{trn}^{-1}LL^{T}).$

We finally use Lemmas 6, 7, and 8 to estimate it by

$\displaystyle\frac{1}{N_{tst}}Tr\left(\Sigma_{trn}^{-2}\left(\frac{c}{c-1}\right)^{2}\left(\frac{c-1}{c}\right)^{2}\left(\Sigma_{trn}^{-2}+\frac{1}{\eta_{trn}^{2}}I\right)^{-2}\Sigma_{trn}^{-2}LL^{T}\right)+o\left(\frac{1}{d}\right)$
$\displaystyle=\frac{\eta_{trn}^{4}}{N_{tst}}Tr\left((\Sigma_{trn}^{2}+\eta_{trn}^{2}I)^{-2}LL^{T}\right)+o\left(\frac{1}{d}\right)$
$\displaystyle=\frac{\eta_{trn}^{4}}{N_{tst}}\|\left(\Sigma_{trn}^{2}+\eta_{trn}^{2}I\right)^{-1}L\|_{F}^{2}+o\left(\frac{1}{d}\right)$

Since test and train data are decoupled, we can treat $LL^{T}/N_{tst}$ as a
constant as $N$ grows, noting that due the $\Sigma_{trn}^{-2}$, the final
estimate is $o(1)$. So, repeating the deviation argument at the end of the
proof of Lemma 9 above, we then have that the deviation from this estimate is
$o\left(\frac{1}{d}\right)$.

Combining this with Lemma 9, we get that

$\frac{\eta_{trn}^{4}}{N_{tst}}\|\left(\Sigma_{trn}^{2}+\eta_{trn}^{2}I\right)^{-1}L\|_{F}^{2}+\frac{\eta_{tst}^{2}}{d}\frac{c}{c-1}\operatorname{Tr}(\Sigma_{trn}^{2}(\Sigma_{trn}^{2}+\eta_{trn}^{2}I)^{-1})+O\left(\frac{\|\Sigma_{trn}^{2}\|}{{d}^{2}}\right)+o\left(\frac{1}{d}\right).$

∎

####  C.1.2 The Underparametrized Regime, $d<N$

We derive test error bounds for $\beta=I$ in our problem setting. We also
denote $W_{opt}$ by $W$ in this subsection, for ease of notation.

We begin by defining some notation. Let $X_{trn}=U\Sigma_{trn}V_{trn}^{T}$.
Here $U$ is $d\times r$ with $U^{T}U=I$, $\Sigma_{trn}$ is $r\times r$, and
$V_{trn}$ is $r\times N$. All of the following matrices are full rank.

  1. 1.

$Q=V^{T}(I-A_{trn}^{\dagger}A_{trn})\in\mathbb{R}^{N\times r}$.

  2. 2.

$H=V_{trn}^{T}A_{trn}^{\dagger}\in\mathbb{R}^{r\times d}$

  3. 3.

$Z=I+V_{trn}^{T}A_{trn}^{\dagger}U\Sigma_{trn}\in\mathbb{R}^{r\times r}$

  4. 4.

$K=-A_{trn}^{\dagger}U\Sigma_{trn}\in\mathbb{R}^{N\times r}$.

  1. 5.

$H_{1}=K^{T}K+Z^{T}(QQ^{T})^{-1}Z\in\mathbb{R}^{r\times r}$.

  2. 6.

$U$ is $d\times r$ with $U^{T}U=I_{r\times r}$.

  3. 7.

$\Sigma_{trn}$ is $r\times r$, with rank $r$.

  4. 8.

$A_{trn}=\eta_{trn}\tilde{U}\tilde{\Sigma}\tilde{V}^{T}$ with $\tilde{U}$ is
$d\times d$ unitary and $\tilde{\Sigma}$ is $d\times N$.

We will henceforth drop the subscript $A_{trn}$ in the expectation
$\mathbb{E}_{A_{trn}}$.

######  Lemma 10.

When $d<N-r$, we have that

$W=-U\Sigma_{trn}H_{1}^{-1}K^{T}A_{trn}^{\dagger}+U\Sigma_{trn}H_{1}^{-1}Z^{T}(QQ^{T})^{-1}H.$

###### Proof.

We know that $W=X(X+A_{trn})^{\dagger}$. By Corollary 2.3 of Wei (2001),
setting $X=-CB$ with $C=-U\Sigma_{trn}$ and $B=V^{T}$, we have that

$(X+A_{trn})^{\dagger}=A_{trn}^{\dagger}-Q^{\dagger}H-(K+Q^{\dagger}Z)H_{1}^{-1}(K^{T}A_{trn}^{\dagger}-Z^{T}(QQ^{T})^{-1}H).$

So, using the facts that $X=U\Sigma_{trn}V^{T}$,
$K=-A_{trn}^{\dagger}U\Sigma_{trn}$, we have that

$\displaystyle W$ $\displaystyle=X(X+A_{trn}^{\dagger})$
$\displaystyle=U\Sigma_{trn}V^{T}A_{trn}^{\dagger}-U\Sigma_{trn}Q^{\dagger}H+U\Sigma_{trn}V^{T}A_{trn}^{\dagger}U\Sigma_{trn}H_{1}^{-1}K^{T}A_{trn}^{\dagger}$
$\displaystyle\qquad-U\Sigma_{trn}V^{T}Q^{\dagger}ZH_{1}^{-1}K^{T}A_{trn}^{\dagger}-U\Sigma_{trn}V^{T}A_{trn}^{\dagger}U\Sigma_{trn}H_{1}^{-1}Z^{T}(QQ^{T})^{-1}H$
$\displaystyle\qquad+U\Sigma_{trn}V^{T}Q^{\dagger}ZH_{1}^{-1}Z^{T}(QQ^{T})^{-1}H.$

Using the fact that $H=V^{T}A_{trn}^{\dagger}$, we get that

$\displaystyle W$
$\displaystyle=U\Sigma_{trn}H-U\Sigma_{trn}Q^{\dagger}H+U\Sigma_{trn}HU\Sigma_{trn}H_{1}^{-1}K^{T}A_{trn}^{\dagger}-U\Sigma_{trn}V^{T}Q^{\dagger}ZH_{1}^{-1}K^{T}A_{trn}^{\dagger}$
$\displaystyle\qquad-U\Sigma_{trn}HU\Sigma_{trn}H_{1}^{-1}Z^{T}(QQ^{T})^{-1}ZZ^{-1}H+U\Sigma_{trn}V^{T}Q^{\dagger}ZH_{1}^{-1}Z^{T}(QQ^{T})^{-1}ZZ^{-1}H.$

Using the fact that
$Z=I+V^{T}A_{trn}^{\dagger}U\Sigma_{trn}=I+HU\Sigma_{trn}$, we get that

$\displaystyle W$
$\displaystyle=U\Sigma_{trn}H-U\Sigma_{trn}Q^{\dagger}H+U\Sigma_{trn}(Z-I)H_{1}^{-1}K^{T}A_{trn}^{\dagger}-U\Sigma_{trn}V^{T}Q^{\dagger}ZH_{1}^{-1}K^{T}A_{trn}^{\dagger}$
$\displaystyle\qquad-U\Sigma_{trn}(Z-I)H_{1}^{-1}Z^{T}(QQ^{T})^{-1}ZZ^{-1}H+U\Sigma_{trn}V^{T}Q^{\dagger}ZH_{1}^{-1}Z^{T}(QQ^{T})^{-1}ZZ^{-1}H.$

Using the fact that $H_{1}=K^{T}K+Z^{T}(QQ^{T})^{-1}Z$, we get that

$\displaystyle W$
$\displaystyle=U\Sigma_{trn}H-U\Sigma_{trn}Q^{\dagger}H+U\Sigma_{trn}ZH_{1}^{-1}K^{T}A_{trn}^{\dagger}-U\Sigma_{trn}H_{1}^{-1}K^{T}A_{trn}^{\dagger}$
$\displaystyle\qquad-U\Sigma_{trn}V^{T}Q^{\dagger}ZH_{1}^{-1}K^{T}A_{trn}^{\dagger}-U\Sigma_{trn}ZH_{1}^{-1}(H_{1}-K^{T}K)Z^{-1}H$
$\displaystyle\qquad+U\Sigma_{trn}H_{1}^{-1}Z^{T}(QQ^{T})^{-1}H+U\Sigma_{trn}V^{T}Q^{\dagger}ZH_{1}^{-1}(H_{1}-K^{T}K)Z^{-1}H$
$\displaystyle=U\Sigma_{trn}H-U\Sigma_{trn}Q^{\dagger}H+U\Sigma_{trn}ZH_{1}^{-1}K^{T}A_{trn}^{\dagger}-U\Sigma_{trn}H_{1}^{-1}K^{T}A_{trn}^{\dagger}$
$\displaystyle\qquad-U\Sigma_{trn}V^{T}Q^{\dagger}ZH_{1}^{-1}K^{T}A_{trn}^{\dagger}-U\Sigma_{trn}H+U\Sigma_{trn}ZH_{1}^{-1}K^{T}KZ^{-1}H$
$\displaystyle\qquad+U\Sigma_{trn}H_{1}^{-1}Z^{T}(QQ^{T})^{-1}H+U\Sigma_{trn}V^{T}Q^{\dagger}H-U\Sigma_{trn}V^{T}Q^{\dagger}ZH_{1}^{-1}K^{T}KZ^{-1}H.$

Cancelling terms, we get that

$\displaystyle W$
$\displaystyle=U\Sigma_{trn}ZH_{1}^{-1}K^{T}A_{trn}^{\dagger}-U\Sigma_{trn}H_{1}^{-1}K^{T}A_{trn}^{\dagger}-U\Sigma_{trn}V^{T}Q^{\dagger}ZH_{1}^{-1}K^{T}A_{trn}^{\dagger}$
$\displaystyle\qquad+U\Sigma_{trn}ZH_{1}^{-1}K^{T}KZ^{-1}H+U\Sigma_{trn}H_{1}^{-1}Z^{T}(QQ^{T})^{-1}H$
$\displaystyle\qquad-U\Sigma_{trn}V^{T}Q^{\dagger}ZH_{1}^{-1}K^{T}KZ^{-1}H.$

And we rearrange to get that

$\displaystyle W$
$\displaystyle=-U\Sigma_{trn}H_{1}^{-1}K^{T}A_{trn}^{\dagger}+U\Sigma_{trn}H_{1}^{-1}Z^{T}(QQ^{T})^{-1}H+U\Sigma_{trn}(I-V^{T}Q^{\dagger})ZH_{1}^{-1}K^{T}A_{trn}^{\dagger}$
$\displaystyle\quad+U\Sigma_{trn}(I-V^{T}Q^{\dagger})ZH_{1}^{-1}K^{T}KZ^{-1}H$
$\displaystyle=-U\Sigma_{trn}H_{1}^{-1}K^{T}A_{trn}^{\dagger}+U\Sigma_{trn}H_{1}^{-1}Z^{T}(QQ^{T})^{-1}H,$

where the last equality is because $Q=V^{T}(I-A_{trn}^{\dagger}A_{trn})$ has
full rank, so $Q^{\dagger}=Q^{T}(QQ^{T})^{-1}$, so
$V^{T}Q^{\dagger}=V^{T}(I-A_{trn}^{\dagger}A_{trn})V(V^{T}(I-A_{trn}^{\dagger}A_{trn})V)^{-1}=I$.
∎

######  Lemma 11.

For $d<N-r$, with notation as in Lemma 10 have that $\displaystyle
X_{tst}-WX_{tst}=U\Sigma_{trn}H_{1}^{-1}Z^{T}(QQ^{T})^{-1}\Sigma_{trn}^{-1}L.$

###### Proof.

Note that
$X_{tst}-WX_{tst}=UL-U\Sigma_{trn}H_{1}^{-1}K^{T}A_{trn}^{\dagger}UL-U\Sigma_{trn}H_{1}^{-1}Z^{T}(QQ^{T})^{-1}HUL.$
Remember that $K=-A_{trn}U\Sigma$, so
$A_{trn}U\Sigma_{tst}=-K\Sigma_{trn}^{-1}\Sigma_{tst}$ and
$HU\Sigma_{tst}=(HU\Sigma)\Sigma_{trn}^{-1}\Sigma_{tst}=(Z-I)\Sigma_{trn}^{-1}\Sigma_{tst}$
This gives us the following equality.

$\displaystyle X_{tst}-WX_{tst}$
$\displaystyle=UL-U\Sigma_{trn}H_{1}^{-1}K^{T}K\Sigma_{trn}^{-1}L-U\Sigma_{trn}H_{1}^{-1}Z^{T}(QQ^{T})^{-1}Z\Sigma_{trn}^{-1}L$
$\displaystyle\qquad+U\Sigma_{trn}H_{1}^{-1}Z^{T}(QQ^{T})^{-1}\Sigma_{trn}^{-1}L$
$\displaystyle=U(I-\Sigma_{trn}H_{1}^{-1}(K^{T}K+Z^{T}(QQ^{T})^{-1}Z)\Sigma_{trn}^{-1}+\Sigma_{trn}H_{1}^{-1}Z^{T}(QQ^{T})^{-1}\Sigma_{trn}^{-1})L.$

Using the fact that $H_{1}=K^{T}K+Z^{T}(QQ^{T})^{-1}Z$, we get that

$\displaystyle
X_{tst}-WX_{tst}=UL-U\Sigma_{trn}H_{1}^{-1}H_{1}\Sigma_{trn}^{-1}L+U\Sigma_{trn}H_{1}^{-1}Z^{T}(QQ^{T})^{-1}\Sigma_{trn}^{-1}L=U\Sigma_{trn}H_{1}^{-1}Z^{T}(QQ^{T})^{-1}\Sigma_{trn}^{-1}L.$

∎

######  Lemma 12.

For $c<1$, we have that
$\displaystyle\mathbb{E}[\Sigma_{trn}^{-1}K^{T}K\Sigma_{trn}^{-1}]=\frac{1}{\eta_{trn}^{2}}\frac{c}{1-c}+o(1)$
and the variance of the $ij^{th}$ entry is $O\left(\frac{1}{N}\right)$.

###### Proof.

Note that
$K^{T}K=\Sigma_{trn}U^{T}(A_{trn}A_{trn}^{T})^{\dagger}U\Sigma_{trn}$. So,
$(K^{T}K)_{ij}=\sigma_{i}u_{i}^{T}(A_{trn}A_{trn}^{T})^{\dagger}u_{j}\sigma_{j}$.
Using ideas from Sonthalia & Nadakuditi (2023), we see that if $i\neq j$, then
the expectation is 0. On the other hand if $i=j$, then using Lemma 6 from
Sonthalia & Nadakuditi (2023), with $p=N$, $q=d$,
$A=\frac{1}{\eta_{trn}}A_{trn}^{T}$, we get that

$\mathbb{E}[(\Sigma_{trn}^{-1}K^{T}K\Sigma_{trn}^{-1})_{ii}]=\frac{1}{\eta_{trn}^{2}}\frac{c}{1-c}+o(1).$

The result on the expectation follows immediately from this.

For the variance, pick arbitrary $i\neq j$ and fix them. Consider