Generalization for Least Squares Regression with Simple Spiked Covariances

## Abstract

Abstract Random matrix theory has proven to be a valuable tool in analyzing the generalization of linear models. However, the generalization properties of even two-layer neural networks trained by gradient descent remain poorly understood. To understand the generalization performance of such networks, it is crucial to characterize the spectrum of the feature matrix at the hidden layer. Recent work has made progress in this direction by describing the spectrum after a single gradient step, revealing a spiked covariance structure. Yet, the generalization error for linear models with spiked covariances has not been previously determined. This paper addresses this gap by examining two simple models exhibiting spiked covariances. We derive their generalization error in the asymptotic proportional regime. Our analysis demonstrates that the eigenvector and eigenvalue corresponding to the spike significantly influence the generalization error.

## 1 Introduction

Significant theoretical work has been dedicated to understanding generalization in linear regression models (Dobriban & Wager, ; Advani et al., ; Mel & Ganguli, ; Derezinski et al., ; Hastie et al., ; Kausik et al., ; Wang et al., ). In an effort to extend this understanding to two-layer neural networks, researchers have explored various approximations, including the random features model (Mei et al., ; Mei & Montanari, ; Jacot et al., ), the mean-field limit of two-layer networks (Mei et al., ), the neural tangent kernel (Jacot et al., ; Adlam & Pennington, ), and kernelized ridge regression (Barzilai & Shamir, ; Liang et al., ; Xiao et al., ; Hu et al., ).

For the random features approximation, the first layer of the neural network is considered fixed, and only the outer layer is trained. Concretely, consider a two-layer neural network

$$ $f(x)=\sum_{i=1}^{m}\zeta_{i}\sigma(w_{i}^{T}x)=\operatorname{\mathbf{\zeta}}^{ T}\sigma(W^{T}x),$ $$

where $x\in\mathbb{R}^{d}$ is a data point, $[\zeta_{1},\ldots,\zeta_{m}]^{T}=\operatorname{\mathbf{\zeta}}\in\mathbb{R}^{m}$ are the outer layer weights, and $w_{i}\in\mathbb{R}^{d}$ for $i=1,\ldots,m$ ($W\in\mathbb{R}^{d\times m}$) are the inner layer weights. Let us define $F=\sigma(XW)$ as the feature matrix, where $X\in\mathbb{R}^{n\times d}$ is the data matrix. It has been shown that to understand the generalization, we need to analyze the distribution of singular values of $F$. Works such as Pennington & Worah (); Adlam et al. (); Benigni & Péché (); Fan & Wang (); Wang & Zhu (); Péché (); Piccolo & Schröder () have studied the spectrum of $F$ in the asymptotic limit, enabling us to understand the generalization. However, random feature models do not leverage the feature learning capabilities of neural networks. To gain further insights into the performance of two-layer neural networks and their feature learning capabilities, we need to train the inner layer.

Recent studies such as Ba et al. (); Moniri et al. () have examined the effects on $F$ of taking one gradient step for the inner layer. Specifically, Ba et al. () showed that with a sufficiently large step size $\eta$, two-layer models can already outperform random feature models after just one step. Moniri et al. () extended this work to study many different scales for the step size. Concretely, let $(x_{1},y_{1}),\ldots,(x_{n},y_{n})$ be $n$ data points and let $\eta\approx n^{\alpha}$ be the step size with $\alpha\in\left(\frac{\ell-1}{2\ell},\frac{\ell}{2\ell+2}\right)$ for $\ell\in Z_{\geq 0}$. Perform one gradient step with the following loss function

$$ $\mathcal{L}_{tr}=\frac{1}{n}\sum_{i=1}^{n}\left(y_{i}-\operatorname{\mathbf{ \zeta}}^{T}\sigma(W^{T}x_{i})\right)^{2}$ $$

to get $W_{1}$. Then, they showed that there exists a rank $\ell$ matrix $P$ such that

$$ $\sigma(XW_{1})=:F_{1}=F_{0}+P+o(\sqrt{n}),$ $$

where $F_{0}$ represents the features at initialization and $X\in R^{n\times d}$ is the data matrix. As shown in Figure 1.1, the singular values of $F_{0}+P$ consist of two parts: the *bulk* corresponds primarily to the singular values of $F_{0}$, and the *spikes* correspond to the isolated singular values due to $P$. Hence, the sample covariance $\frac{1}{n}F_{1}^{T}F_{1}$ has a spiked structure.

Furthermore, they demonstrated that if

$$ $\mathcal{L}_{te}(\operatorname{\mathbf{\zeta}})=\mathbb{E}_{x,y}\|y- \operatorname{\mathbf{\zeta}}^{T}\sigma(W_{1}^{T}x)\|^{2}$ $$

is the expected mean squared generalization error, where $y=[y_{1}\ldots y_{n}]$. Then for some regimes, $\mathcal{L}_{te}(\operatorname{\mathbf{\zeta}}^{*}(F_{1}))$ is asymptotically equal to $\mathcal{L}_{te}(\operatorname{\mathbf{\zeta}}^{*}(F_{0}+P))$, where $\operatorname{\mathbf{\zeta}}^{*}(F)$ is the minimum norm solution to the ridge regularized problem with features $F$,

$$ $\operatorname{\mathbf{\zeta}}^{*}(F):=\operatorname*{arg\,min}_{\operatorname{ \mathbf{\zeta}}}\frac{1}{n}\left\|y-F\operatorname{\mathbf{\zeta}}\right\|^{2} +\lambda\|\operatorname{\mathbf{\zeta}}\|^{2}.$ $$

*However, they did not quantify $\mathcal{L}_{te}(\operatorname{\mathbf{\zeta}}^{*}(F_{0}+P))$.* The challenge with quantifying the effect of the spike on the generalization error is that since we have a fixed number of spikes, *the asymptotic spectrum does not see the spike.* This paper takes a step towards quantifying such errors.

Figure: Figure 1.1: Figure from Moniri et al. () showing the singular values of $F_{0}+P$. The bulk corresponds to $F_{0}$, while the spikes represent the effect of $P$.
Refer to caption: x1.png

#### Contributions

This paper considers linear regression where the data $x$ has a spiked covariance model. The main contributions of the paper are as follows.

- (i)
We consider two linear regression problems that capture some of the challenges present in Moniri et al. () spiked covariance model. These regression problems extend prior models from Hastie et al. () and Li & Sonthalia (). In particular, we introduce two regression targets, providing a more comprehensive understanding of how the learned features interact with the target function.
- (ii)
We derive closed-form expressions for the generalization error for both models (Theorem 3 and Theorem 4), offering precise quantification of the generalization error.
- (iii)
We show that the risk can be decomposed into the asymptotic risk for the unspiked case plus a correction term that depends on the eigenvector and eigenvalue corresponding to the spike. We show that for finite matrices, if the variance for the distribution of the bulk eigenvalues is small enough, then the correction is significant.

#### Other Related Works

Spiked covariance models have gotten significant attention. Prior work such as Benaych-Georges & Nadakuditi (); Baik & Silverstein () have examined the largest eigenvalue and its corresponding eigenvector in the asymptotic limit. Spiked covariances can be seen when denoising low rank signals (Nadakuditi, ; Sonthalia & Nadakuditi, ; Kausik et al., ). Additionally, recent work Li & Sonthalia () also consider two particular spiked covariance models and show interesting double descent phenomena. See Couillet & Liao () for more applications where spiked covariance models appear.

Recent work has also sought to understand the features of the spectrum beyond a single step (Wang et al., ) and for three layer neural networks (Wang et al., ; Nichani et al., ).

#### Paper structure

The rest of the paper is organized as follows. Section 2 provides a brief introduction to random matrix theory and how it can be used to understand the generalization error of the models. This section also highlights the difficulty in understanding the generalization error for spiked covariance models. Section 3 sets up the problem formulation we analyze, and Section 4 presents our theoretical results. Finally, Section 5 represents some limitations of our work and avenues for future work.

## 2 Challenges With Spiked Covariances

In this section, we identify and elaborate on the specific challenges the spiked covariances from Moniri et al. () introduce in analyzing generalization errors.

### 2.1 Random Matrix Theory Background

We need to define a few important objects for this discussion and, more broadly, for the paper. Let $\mathcal{D}$ be a distribution on $\mathbb{R}^{d}$ with uncentered covariance $\Sigma=\mathbb{E}_{x\sim\mathcal{D}}\left[xx^{T}\right]$ and let $X=[x_{1},\ldots,x_{n}]^{T}$ be I.I.D. samples from $\mathcal{D}$. Let $\hat{\Sigma}=\frac{1}{n}X^{T}X$ be the sample covariance matrix.

###### Definition 1 (Empirical Spectral Distribution (e.s.d.) .

Let $\lambda_{1},\ldots,\lambda_{n}$ be the eigenvalues of a matrix $\Sigma$. Then, the empirical spectral distribution of $\Sigma$ is

$$ $\nu_{\Sigma}(\lambda):=\frac{1}{d}\sum_{i=1}^{d}\delta_{\lambda_{i}}(\lambda).$ $$

One of the most common assumptions made in this field is that as $d\to\infty$, we have that $\nu_{\Sigma}$ converges almost surely to a deterministic measure $\nu_{H}$ at every point of continuity of $\nu_{H}$(^1^11Note a measure is continuous at $x$ if and only if $\nu(\{x\})=0$.). Once we know that the e.s.d. for the population covariance, we can express the limiting risk for ride regression as a function of the deterministic quantity $\nu_{H}$ (Dobriban & Wager, ; Hastie et al., ). One of the most common ways of describing $\nu_{H}$ is via its Stieltjes transform.

###### Definition 2 (Stieltjes Transform) .

Given a measure $\nu$ on $\mathbb{R}$ or its corresponding density function $f_{\nu}$, the Stieltjes transform $m_{\nu}:\mathbb{C}\setminus\operatorname{supp}(\nu)\to\mathbb{C}$ of $\nu$ is defined by

$$ $m_{\nu}(z):=\int\frac{1}{\lambda-z}d\nu(\lambda)=\int\frac{1}{\lambda-z}f_{\nu }(\lambda)d\lambda.$ $$

For the sample covariance, we see that

$$ $m_{\nu_{\hat{\Sigma}}}(z)=\frac{1}{d}\sum_{i=1}^{d}\frac{1}{\lambda_{i}(\hat{ \Sigma})-z}=\frac{1}{d}\operatorname{Tr}\left[\left(\hat{\Sigma}-zI\right)^{-1 }\right].$ $$

One of the seminal results in random matrix theory develops a connection between the limiting e.s.d. for the *population* covariance matrix and the limiting e.s.d. for the *sample* covariance matrix. Marchenko & Pastur () showed that under some mild assumptions, the following theorem holds:

###### Theorem 1 ( Marchenko & Pastur ( 1967 ) ) .

Let $\{(n_{k},d_{k})\}_{k\in\mathbb{N}}$ be a sequence of pairs of integers such that $d_{k}/n_{k}\to c$ as $k\to\infty$. Suppose $\Sigma(d_{k})$ and $X_{k}\in\mathbb{R}^{n_{k}\times d_{k}}$ has $n_{k}$ I.I.D. samples from $\mathcal{N}(0,\Sigma(d_{k}))$. If $\nu_{\Sigma}$ converges almost surely to $\nu_{H}$, then there exists a deterministic $\nu_{F}$ such that the e.s.d. of the sample covariance matrix $\nu_{\hat{\Sigma}}$ converges almost surely to $\nu_{F}$ at all points of continuity of $\nu_{F}$ and for all $z\in\mathbb{C}^{+}$, we have that $m_{\nu_{\hat{\Sigma}}}(z)\to m_{\nu_{F}}(z),$
where

$$ $m_{\nu_{F}}(z)=\int\frac{1}{t\left(1-c-czm_{\nu_{F}}(z)\right)-z}d\nu_{H}(t).$ $$

The result is more general, but we provide a simplified version here.

###### Example 1 .

Suppose $\Sigma(d)=I$. Then we see that e.s.d. of $\Sigma$ is a Dirac delta measure at 1. Hence, its limiting e.s.d. $\nu_{H}$ is $\delta_{1}$. Hence, in this case, if we apply Theorem 1, we get that the Stieljtes transform of the limiting e.s.d. $\nu_{F}$ for the sample covariance satisfies the following

$$ $m_{\nu_{F}}(z)=\frac{1}{\left(1-c-czm_{\nu_{F}}(z)\right)-z}.$ $$

Such distributions $\nu_{F}$ are called the Marchenko-Pastur distribution with shape $c$.

Results such as the above theorem from Marchenko & Pastur () and Theorem 1.1 Bai & Zhou () are qualitative results about the limit. Prior work such as Dobriban & Wager (); Wu & Xu (); Advani et al. (); Xiao et al. () use these results to understand the limiting generalization error. However, there are also quantitative versions. Specifically, works such as Hastie et al. () use results from Knowles & Yin () to provide more nuanced results.

###### Definition 1 (Empirical Spectral Distribution (e.s.d.) .

###### Definition 2 (Stieltjes Transform) .

###### Theorem 1 ( Marchenko & Pastur ( 1967 ) ) .

###### Example 1 .

### 2.2 Challenges with Spiked Covariance

Let us recall the setup from Moniri et al. (). Specifically, they assume that the outer layer weight $\zeta\sim\mathcal{N}(0,\frac{1}{m}I)$ and inner layer weights $w_{i}\sim\text{Unif}(\mathbb{S}^{d-1})$ with $W_{0}=[w_{1}\ldots w_{m}]^{T}\in\mathbb{R}^{m\times d}$. Additionally, they assume that the training data $(x_{1},y_{1}),\ldots,(x_{n},y_{n})$ is of the following form:

$$ $x_{i}\sim\mathcal{N}(0,I)\text{ and }y_{i}=\sigma_{*}(w^{T}x)+\varepsilon_{i}.$ $$

Here $\varepsilon\sim\mathcal{N}(0,1)$, $w\sim\mathcal{N}(0,\frac{1}{d}I)$, and $\sigma_{*}$ is $\Theta(1)$-Lipschitz. Then $W_{1}$ is obtained after taking one gradient step. Let $\tilde{X}$ and $\tilde{y}$ be new independent data and let $F_{1}=\sigma(\tilde{X}W_{1})$, and $F_{0}=\sigma(\tilde{X}W_{0})$. Then, in the proportional asymptotic regime, with some additional technical assumptions on the student networks activation $\sigma$, Moniri et al. () show that

$$ $F_{1}=F_{0}+C(\sigma,\eta)(\tilde{X}w)\cdot\operatorname{\mathbf{\zeta}}^{T}+o (\sqrt{n}),$ $$

where $C(\sigma,\eta)$ is a constant.
After taking one gradient step for the inner layer, we train the outer layer using least squares ridge regression. Hence, to understand the generalization performance of such networks, we need to understand the generalization error for the following problem.

$$ $\operatorname{\mathbf{\zeta}}^{*}(F):=\operatorname*{arg\,min}_{\operatorname{ \mathbf{\zeta}}}\frac{1}{n}\left\|y-F\operatorname{\mathbf{\zeta}}\right\|^{2} +\lambda\|\operatorname{\mathbf{\zeta}}\|^{2}.$ $$

The standard approach to do this is by understanding the spectrum of $F_{1}^{T}F_{1}$. We break $F_{1}^{T}F_{1}$ up into three terms – the diagonal terms $F_{0}^{T}F_{0}$ and $C(\sigma,\eta)^{2}\|(\tilde{X}w)\|^{2}\operatorname{\mathbf{\zeta}}
\operatorname{\mathbf{\zeta}}^{T}$ and the cross term $F_{0}\tilde{X}w\operatorname{\mathbf{\zeta}}^{T}$.

#### Spectrum of C ⁢ ( σ , η ) 2 ⁢ ‖ ( X ~ ⁢ w ) ‖ 2 ⁢ ζ ⁡ ζ T 𝐶 superscript 𝜎 𝜂 2 superscript norm ~ 𝑋 𝑤 2 𝜁 superscript 𝜁 𝑇 C(\sigma,\eta)^{2}\|(\tilde{X}w)\|^{2}\operatorname{\mathbf{\zeta}}%
\operatorname{\mathbf{\zeta}}^{T} italic_C ( italic_σ , italic_η ) start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT ∥ ( over~ start_ARG italic_X end_ARG italic_w ) ∥ start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT italic_ζ italic_ζ start_POSTSUPERSCRIPT italic_T end_POSTSUPERSCRIPT :

This term is important for understanding the feature learning capabilities of neural networks, as it is the new term that appeared after taking one gradient step.
*However, the issue is that the limiting e.s.d. for the population covariance does not see this spike.* For example, suppose the population covariance matrix is

$$ $\Sigma=I+\ell uu^{T}.$ $$

Then we see that the e.s.d. for $\Sigma$ is given by $\displaystyle\frac{1}{d}\delta_{\ell+1}+\frac{d-1}{d}\delta_{1}$.

Hence, as we send $d\to\infty$, this converges to $\delta_{1}$. Hence, the limiting spectrum does not see the spike. However, if we consider the value of the largest eigenvalue of the sample covariance, then it can converge to something outside of the support (Baik & Silverstein, ; Benaych-Georges & Nadakuditi, ; Couillet & Liao, ).

###### Theorem 2 ( Baik & Silverstein ( 2006 ) Theorem 1.1) .

Under the same setting as Theorem 1, and let
$\Sigma=I+\ell uu^{T}$. Denoting $\hat{\lambda}_{1}$ the largest eigenvalue of $\frac{1}{n}X^{T}X$, as $n,d\to\infty$ with $d/n\to c\in(0,1)$, we have that

$$ $\hat{\lambda}_{1}\to\begin{cases}\ell_{j}+c\frac{\ell_{j}}{\ell_{j}-1}&\ell>1+ \sqrt{c}\\ (1+\sqrt{c})^{2}&\ell\leq 1+\sqrt{c}\end{cases}.$ $$

From Theorem 1, we have that the limiting spectrum for the eigenvalues for the sample covariance matrix is the Marchenko-Pastur distribution, whose support is $[(1-\sqrt{c})^{2},(1+\sqrt{c})^{2}]$. However, we see that if $\ell$ is big enough, then the largest eigenvalue escapes from the continuous bulk on $[(1-\sqrt{c})^{2},(1+\sqrt{c})^{2}]$ and creates a spike. This spike is from a set of measure zero. Hence, its effect on the generalization error cannot be detected in the asymptotic limit. However, in the finite case, this spike affects the generalization error. In Section 4 we provide a concrete example for this.

###### Theorem 2 ( Baik & Silverstein ( 2006 ) Theorem 1.1) .

#### Spectrum of F 0 T ⁢ F 0 superscript subscript 𝐹 0 𝑇 subscript 𝐹 0 F_{0}^{T}F_{0} italic_F start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_T end_POSTSUPERSCRIPT italic_F start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT

For this, we can use Theorem 1.4 from Péché (), to see that the spectrum of $\frac{1}{n}F_{0}F_{0}^{T}$ can be approximated by the spectrum of

$$ $\frac{1}{n}\Big{(}\phi_{2}\tilde{X}W_{0}+\phi_{1}\Xi\Big{)}^{T}\Big{(}\phi_{2} \tilde{X}W_{0}+\phi_{1}\Xi\Big{)},$ $$

where $\Xi$ has IID standard Gaussian entries and $\phi_{1},\phi_{2}$ are constants that only depend on $\sigma$. Here $\tilde{X}$ and $W_{0}$ are freely independent, and the asymptotic spectrum of $\frac{1}{n}XX^{T}$ and $W_{0}^{T}W_{0}$ are described by appropriate Marchenko-Pastur distributions. Prior work such as Nadakuditi & Edelman () can be used to analytically determine the spectrum of the product.

#### Spectrum of Cross Term - F 0 ⁢ X ~ ⁢ w ⁢ ζ T subscript 𝐹 0 ~ 𝑋 𝑤 superscript 𝜁 𝑇 F_{0}\tilde{X}w\operatorname{\mathbf{\zeta}}^{T} italic_F start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT over~ start_ARG italic_X end_ARG italic_w italic_ζ start_POSTSUPERSCRIPT italic_T end_POSTSUPERSCRIPT

This term is also particularly challenging as $F_{0}$ and $\tilde{X}$ are both functions of $\tilde{X}$ and hence are dependent. This paper shall not consider this dependence.

## 3 Problem Setting

Building upon the challenges identified in Section 2, we explore two spiked covariance settings. We aim to understand the generalization error of least squares regression in such data models.

### 3.1 Data Model

We consider a data matrix $X\in\mathbb{R}^{n\times d}$, whose rows are the data points, that is generated as the sum of a rank-one signal component corresponding to the spike and a full rank component corresponding to the bulk. *Since we are interested in the effect of the spike on the risk, we call the spike component the signal and we shall refer to the bulk as the noise*. This is the signal plus noise spiked covariance model from Couillet & Liao ().

$$ $X=Z+A.$ $$

The *signal (spike) component* is represented by $Z$. Let $u\in\mathbb{R}^{d}$ be a fixed unit-norm vector representing the direction of the spike in the covariance matrix(^2^22This is not the exact eigenvector for the spike, as we have perturbed it by the noise matrix). We generate $Z$ as:

$$ $Z=\theta vu^{T},$ $$

where $\theta$ scales the norm of the matrix, and $v\in\mathbb{R}^{n}$ has unit norm.

The *noise (bulk) component* is represented by $A$. The noise matrix $A\in\mathbb{R}^{n\times d}$ has entries $A_{ij}$ that are independent and identically distributed (i.i.d.) with mean zero and variance $\tau_{A}^{2}/d$.
Additionally:

- •
The entries of $A$ are uncorrelated.
- •
The distribution of $A$ is rotationally bi-invariant; it remains the same under orthogonal transformations from both the left and the right.
- •
$A$ is full rank with probability 1, and empirical spectral distribution of $\frac{1}{\tau^{2}_{A}}AA^{T}$ converges to the Marchenko-Pastur distribution as $n,d\to\infty$ with $n/d\to c$.

Note that the isotropic Gaussian satisfies all of the noise assumptions. For a larger family of distributions that satisfy the assumptions, see Sonthalia & Nadakuditi ().

#### Connection to two-layer model

In the setting of Moniri et al. () we can think of $A$ as the representing $F_{0}$(^3^33Note that this is note exact as the limiting e.s.d. for $F_{0}$ is not necessarily the Marchenko-Pastur distribution, only true of $\phi_{2}=0$. This difference is not too important, as instead of using the Stieltjes transform for the Marchenko-Pastur distribution in our paper, we could use the result from Péché (); Piccolo & Schröder () instead.). We can also think of $u$ as being $Aw$ for some isotropic Gaussian vector $w$. In this situation, $A$ and $Z$ should be dependent. We shall not consider this dependence and assume that $Z,A$ are independent. This difference is significant. However, understanding the generalization error while ignoring this dependence is still an important step.

### 3.2 Target Functions

We study two different scenarios for the target vector $y\in\mathbb{R}^{n}$, depending on whether the target depends solely on the signal or on both the signal and the noise:

#### Signal-Only Model:

The target depends only on the signal (spike) component $Z$:

$$ $y_{i}=z_{i}^{T}\beta_{*}+\varepsilon_{i},$ $$

where $\beta_{*}\in\mathbb{R}^{d}$ is the true parameter vector we aim to estimate and $\varepsilon_{i}$ is the observation noise, independent of $Z$ and $A$, with $\mathbb{E}[\varepsilon_{i}]=0$ and $\mathbb{E}[\varepsilon_{i}^{2}]=\tau_{\varepsilon}^{2}$. If we consider our analogy of $u=Aw$, then we see that $y_{i}$ is similar to a quadratic function of the data.

#### Signal-and-Noise Model:

The target depends on both the signal (spike) component $Z$ and the noise (bulk) component $A$:

$$ $y_{i}=(z_{i}+a_{i})^{T}\beta_{*}+\varepsilon_{i},$ $$

where $a_{i}\in\mathbb{R}^{d}$ is the $i$-th row of $A$.

### 3.3 Least Squares Estimation and Risk

We consider least squares regression to estimate the parameter vector $\beta\in\mathbb{R}^{d}$, with regularization parameter $\mu>0$.

For the *signal-only problem*, we solve:

$$ $\beta_{so}=\arg\min_{\beta}\left\|y-X\beta\right\|_{2}^{2}+\mu^{2}\|\beta\|_{2 }^{2},$ (3.1) $$

For the *signal-plus-noise problem*, we solve:

$$ $\beta_{spn}=\arg\min_{\beta}\left\|y-X\beta\right\|_{2}^{2},$ (3.2) $$

#### Instance-Specific Risk:

We consider on the *instance-specific risk*. That is the error obtained when evaluating performance on a specific test dataset. We introduce test data $X_{{tst}}=Z_{{tst}}+A_{{tst}}$, generated similarly to the training data but potentially with different variances.

To account for possible differences between training and test data, we distinguish: $\theta_{{trn}}^{2},\theta_{{tst}}^{2}$ as the strengths of the signal (spike) component during training and testing and $\tau_{A_{{trn}}}^{2},\tau_{A_{{tst}}}^{2}$ as the variances of the noise (bulk) component during training and testing. Additionally, $\tau_{\varepsilon_{\text{trn}}}^{2}$ will denote the variance in the observation noise during training.

The instance-specific risk for the *signal-only model* is:

$$ $\mathcal{R}_{so}(c;\mu,\tau,\theta)=\frac{1}{n_{\text{tst}}}\mathbb{E}\left[ \left\|Z_{\text{tst}}\beta_{*}-X_{\text{tst}}\beta_{so}\right\|_{2}^{2}\right],$ (3.3) $$

where the expectation is over the randomness in $A_{\text{trn}},A_{\text{tst}},\varepsilon_{\text{trn}}$. $\tau$ collectively represents all the variances involved and $\theta$ represents both $\theta_{trn}$ and $\theta_{tst}$.

The instance-specific risk for the *signal-and-noise model* is:

$$ $\mathcal{R}_{spn}(c;\tau,\theta)=\frac{1}{n_{\text{tst}}}\mathbb{E}\left[\left \|X_{\text{tst}}\beta_{*}-X_{\text{tst}}\beta_{spn}\right\|_{2}^{2}\right].$ (3.4) $$

By analyzing these two settings, we aim to understand how the spike in the covariance matrix affects the generalization performance. The distinction between the signal-only and signal-and-noise models allows us to explore how the inclusion of the noise (bulk) in the target function influences the estimator’s ability to generalize.

## 4 Generalization Error

This section presents the generalization errors for the two models. The detailed proof can be found in Appendix A and B. We present a proof sketch at the end of the section. We begin by considering the signal-plus-noise model first.

###### Theorem 3 (Risk for Signal Plus Noise Problem) .

Let $\tau_{\varepsilon_{trn}}\asymp 1$, $d/n=c+o(1)$ and $d/n_{tst}=c+o(1)$. Then, any for data $X\in\mathbb{R}^{n\times d},y\in\mathbb{R}^{n}$ from the signal-plus-noise model that satisfy: $1\ll\tau_{A_{trn}}^{2},\tau_{A_{tst}}^{2}\ll d$, $\theta_{trn}^{2}/\tau_{A_{trn}}^{2}\ll n$, $\theta_{tst}^{2}/\tau_{A_{tst}}^{2}\ll n_{tst}$. Then for $c<1$, the instance specific risk is given by

$$ $\displaystyle\mathcal{R}_{spn}(c,0,\tau)$ $\displaystyle=\left[\frac{\theta_{tst}^{2}}{n_{tst}}\frac{1}{(\theta_{trn}^{2} c+\tau_{A_{trn}}^{2})}+\frac{\tau_{A_{tst}}^{2}}{\tau_{A_{trn}}^{2}}\left(1- \frac{\theta_{trn}^{2}c}{d(\theta_{trn}^{2}c+\tau_{A_{trn}}^{2})}\right)\right ]\frac{c\tau_{\varepsilon_{trn}}^{2}}{1-c}+o\left(\frac{1}{d}\right).$ $$

For $c>1$, it is given by

$$ $\displaystyle\mathcal{R}_{spn}(c,0,\tau)=\|\beta_{*}\|^{2}\left(1-\frac{1}{c} \right)\frac{\tau_{A_{tst}}^{2}}{d}+\frac{\tau_{A_{tst}}^{2}\tau_{\varepsilon_ {trn}}^{2}}{\tau_{A_{trn}}^{2}}\left(1-\frac{\theta_{trn}^{2}c}{d(\theta_{trn} ^{2}+\tau_{A_{trn}}^{2})}\right)\frac{1}{c-1}+o\left(\frac{1}{d}\right)$ $\displaystyle+\frac{\theta_{tst}^{2}\tau^{4}_{A_{trn}}}{n_{tst}\left(\theta_{ trn}^{2}+\tau_{A_{trn}}^{2}\right)^{2}}\left[\left(1-\frac{1}{c}\right)\left(( \beta_{*}^{T}u)^{2}+\|\beta_{*}\|^{2}\frac{\theta_{trn}^{2}}{d\tau_{A_{trn}}^{ 2}}\right)+\frac{\tau_{\varepsilon_{trn}}^{2}}{\tau_{A_{trn}}^{4}}\left(\frac{ \theta_{trn}^{2}c+\tau_{A_{trn}}^{2}}{c-1}\right)\right].$ $$

Theorem 3 can be seen as an extension of Theorem 1 from Hastie et al. (). Specifically, if we set $\tau_{A_{trn}}^{2}=\tau_{A_{tst}}^{2}=d$, $\theta_{trn}=\tau_{A_{trn}}^{2}n$, and $\theta_{tst}=\tau_{A_{tst}}^{2}n_{tst}$, and send $d/n\to c$, from Theorem 3 we obtain,

$$ $\mathcal{R}_{spn}=\begin{cases}\tau_{\varepsilon_{trn}}^{2}\frac{c}{1-c}&c<1\\ \|\beta_{*}\|^{2}\left(1-\frac{1}{c}\right)+\tau_{\varepsilon_{trn}}^{2}\frac{ 1}{c-1}&c>1\end{cases}.$ (4.1) $$

This is the risk from Hastie et al. ().
Hence, we can see that Theorem 3 lets us interpolate between a prior model that does not have the spike and spiked models smoothly.

Theorem 3 shows that the presence of the spike affects the risk in the non-asymptotic case. To see this, let $\theta_{tst}=\tau_{A_{tst}}\sqrt{n_{tst}}$ and $\theta_{trn}=\tau_{A_{trn}}\sqrt{n}$. This results in the $Z$ and $A$ matrices having the same expected norm. Then, in the underparameterized ($c<1$) case, we can see that this risk simplifies to

$$ $\frac{\tau_{A_{tst}}^{2}}{\tau_{A_{trn}}^{2}}\cdot\tau_{\varepsilon_{trn}}^{2} \cdot\frac{c}{1-c}+o\left(\frac{1}{d}\right).$ $$

Here we see that spike does not effect the risk. Hence not seeing the spike in the asymptotic limit is not an issue. On the other hand, for the overparameterized ($c>1$) case, we see that with the same simplification ($\theta_{tst}=\tau_{tst}\sqrt{n_{tst}}$ and $\theta_{trn}=\tau_{A_{trn}}\sqrt{n}$), we get that the risk is

$$ $\|\beta_{*}\|^{2}\left(1-\frac{1}{c}\right)\frac{\tau^{2}_{A_{tst}}}{d}+\tau_{ \varepsilon_{trn}}^{2}\left[\frac{1}{c-1}+\frac{\theta_{trn}^{2}}{(\theta_{trn }^{2}+\tau_{A_{trn}}^{2})^{2}}\right]+o\left(\frac{1}{d}\right).$ (4.2) $$

Here, compared to the unspiked case, we see a correction term $\frac{\tau^{2}_{\varepsilon_{trn}}\theta_{trn}^{2}}{(\theta_{trn}^{2}+\tau_{A_
{trn}}^{2})^{2}}$ that depends on the relative strength of the spike ($\theta_{trn}$) to the bulk ($\tau^{2}_{A_{trn}}$). If we assume large bulk strength, that is, $\tau_{A_{trn}}=\tau_{A_{tst}}=d$. Then we see that this term is of order $O(1/d^{2})$. Hence, it can be ignored, and the spike does not affect the risk.

However, if $\tau_{A_{trn}}=\Theta(1)$, then the correction term is of order $\Theta(1/d)$. Hence, the spike does not have an effect in the asymptotic case, but does in the finite case. We verify this empirically.

Figure 4.1 shows four lines. The blue line corresponds to the true risk computed by empirically training the model. The orange line is the risk predicted by Theorem 3 or, more specifically, Equation 4.2. The green line is the correction term $\frac{\tau_{\varepsilon_{trn}}^{2}\theta_{trn}^{2}}{(\theta_{trn}^{2}+\tau_{A_
{trn}}^{2})^{2}}$. Finally, the red line is the asymptotic risk which does not have the correction term.

Figure: Figure 4.1: Figure showing the affect of the spike on the generalization error for finite matrices. Left: when the strength of the spike is large compared to the bulk, we see an affect that this is not detected by asymptotic risk. Right: the bulk and the spike have the same strength and we do not see any effects of the spike on the risk.
Refer to caption: x2.png

We consider two settings. For the left hand side figure, we let $\tau_{\varepsilon_{trn}}=5$, $\tau_{A_{trn}}=\tau_{A_{tst}}=1$ and $d=5000$. We then varied $n$ from 50 to 200. Here, we can see that the spike correction term is significant and affects the risk. For the second setting, we consider the case when $\tau_{A_{trn}}=\tau_{A_{tst}}=d=500$ is large. In this case, we see that the correction term has a small magnitude, and both the asymptotic risk formula and Equation 4.2 match the true empirical risk.

Hence, we see that if the target vector $y$ has a smaller dependence on the noise (bulk) component $A$, then we see that the spike affects the generalization error. To better understand this, we can consider the extreme case where the targets $y$ only depend on the signal (spike) component $Z$. This is exactly the signal-only model.

###### Theorem 4 (Risk for Signal Only Problem) .

Let $\mu\geq 0$ be fixed. Let $\tau_{\varepsilon_{trn}}\asymp 0$, $d/n=c+o(1)$ and $d/n_{tst}=c+o(1)$. Then, any for data $X\in\mathbb{R}^{n\times d},y\in\mathbb{R}^{n}$ from the signal-only model that satisfy: $1\ll\tau_{A_{trn}}^{2},\tau_{A_{tst}}^{2}\ll d$, $\theta_{trn}^{2}/\tau_{A_{trn}}^{2}\ll n$, $\theta_{tst}^{2}/\tau_{A_{tst}}^{2}\ll n_{tst}$. Then for $c<1$, the instance specific risk is given by

$$ $\mathcal{R}(c,\mu,\tau,\theta)=\mathbf{Bias}+\mathbf{Variance_{A_{trn}}}+ \mathbf{Variance_{A_{trn},\varepsilon_{trn}}}+o\left(\frac{1}{d}\right)$ $$

with

$$ $\displaystyle\mathbf{Bias}$ $\displaystyle=\frac{\theta_{tst}^{2}}{n_{tst}}\frac{1}{\gamma^{2}}\left[(\beta _{*}^{T}u)^{2}+\frac{\tau_{\varepsilon_{trn}}^{2}}{2\tau_{A_{trn}}^{4}}\left( \theta_{trn}^{2}c+\tau_{A_{trn}}^{2}\right)\left(T_{2}-1\right)\right],$ $\displaystyle\mathbf{Variance_{A_{trn}}}$ $\displaystyle=\frac{\theta_{trn}^{2}\tau_{A_{tst}}^{2}}{d}\frac{1}{\gamma^{2}} (\beta_{*}^{T}u)^{2}\left[\frac{c\left(\theta_{trn}^{2}+\tau_{A_{trn}}^{2} \right)}{2\tau_{A_{trn}}^{4}}\left(T_{2}-1\right)\right],$ $\displaystyle\mathbf{Variance_{A_{trn},\varepsilon_{trn}}}$ $\displaystyle=\frac{\tau_{\varepsilon_{trn}}^{2}\tau_{A_{tst}}^{2}}{2\tau_{A_{ trn}}^{2}}\left[1+\frac{c\theta_{trn}^{2}}{\tau_{A_{trn}}^{2}}\frac{T_{2}}{d \gamma^{2}}\left(\frac{(c+1)\theta_{trn}^{2}}{\tau_{A_{trn}}^{2}}+1\right) \right](T_{2}-1)$ $\displaystyle-\frac{c^{2}(c+1)\theta_{trn}^{4}\tau_{\varepsilon_{trn}}^{2}\tau _{A_{tst}}^{2}}{d\tau_{A_{trn}}^{2}}\frac{1}{\gamma^{2}T_{1}^{2}}-\frac{2c^{2} \theta_{trn}^{2}\tau_{\varepsilon_{trn}}^{2}\tau_{A_{tst}}^{2}}{d\gamma}\left( \frac{1}{T_{1}^{2}}-\frac{c\mu^{2}}{T_{1}^{3}}\right),$ $$

where

$$ $T_{1}=\sqrt{\left(\tau_{A_{trn}}^{2}+\mu^{2}c-c\tau_{A_{trn}}^{2}\right)^{2}+4 \mu^{2}c^{2}\tau_{A_{trn}}^{2}},\text{ }T_{2}=\frac{\mu^{2}c+\tau_{A_{trn}}^{2 }+c\tau_{A_{trn}}^{2}}{T_{1}},$ $$

$$ $\text{and }\gamma=1+\frac{\theta_{trn}^{2}}{2\tau_{A_{trn}}^{4}}\left(\tau_{A_ {trn}}^{2}+c\tau_{A_{trn}}^{2}+\mu^{2}c-T_{1}\right).$ $$

For $c>1$, the same formula holds except
$T_{1}=\sqrt{\left(-\tau_{A_{trn}}^{2}+\mu^{2}c+c\tau_{A_{trn}}^{2}\right)^{2}+
4\mu^{2}c\tau_{A_{trn}}^{2}}$.

Theorem 4 breaks the risk into three terms – the bias, the variance due to bulk, and the variance due to the bulk and the observation noise. To further interpret the expression, we consider some simplifications. First, setting $\tau_{\varepsilon}$ to zero, recovers Theorem 1 from Li & Sonthalia (). Second, let us consider the unregularized problem, that is $\mu=0$.

###### Corollary 1 (Non-Regularized Error) .

For the same setting as Theorem 4, for $c<1$, we have that

$$ $\mathcal{R}_{so}(c,0,\tau,\theta)=\mathbf{Bias}+\mathbf{Variance}+o\left(\frac {1}{d}\right),$ $$

$$ $\mathbf{Bias}=\frac{\theta_{tst}^{2}}{n_{tst}\left(\theta_{trn}^{2}c+\tau_{A_{ trn}}^{2}\right)^{2}}\left(\tau_{A_{trn}}^{4}(\beta_{*}^{T}u)^{2}+\tau_{ \varepsilon_{trn}}^{2}\left(\frac{\theta_{trn}^{2}c^{2}+\tau_{A_{trn}}^{2}c}{1 -c}\right)\right),$ $$

$$ $\mathbf{Variance}=\frac{\tau_{A_{tst}}^{2}\tau_{\varepsilon_{trn}}^{2}c}{\tau_ {A_{trn}}^{2}(1-c)}+\left((\beta_{*}^{T}u)^{2}\frac{\theta_{trn}^{2}+\tau_{A_{ trn}}^{2}}{\theta_{trn}^{2}c+\tau_{A_{trn}}^{2}}-\frac{\tau_{\varepsilon_{trn} }^{2}}{\tau_{A_{trn}}^{2}}\right)\frac{\theta_{trn}^{2}\tau_{A_{tst}}^{2}}{d \left(\tau_{A_{trn}}^{2}+\theta_{trn}^{2}c\right)}\frac{c^{2}}{1-c}.$ $$

For $c>1$, the bias and variance become

$$ $\mathbf{Bias}=\frac{\theta_{tst}^{2}}{n_{tst}\left(\theta_{trn}^{2}+\tau_{A_{ trn}}^{2}\right)^{2}}\left(\tau_{A_{trn}}^{4}(\beta_{*}^{T}u)^{2}+\tau_{ \varepsilon_{trn}}^{2}\left(\frac{\theta_{trn}^{2}c+\tau_{A_{trn}}^{2}}{c-1} \right)\right),$ $$

$$ $\mathbf{Variance}=\frac{\tau_{A_{tst}}^{2}\tau_{\varepsilon_{trn}}^{2}}{\tau_{ A_{trn}}^{2}(c-1)}+\left((\beta_{*}^{T}u)^{2}-\frac{\tau_{\varepsilon_{trn}}^{ 2}}{\tau_{A_{trn}}^{2}}\right)\frac{\theta_{trn}^{2}\tau_{A_{tst}}^{2}}{d\left (\tau_{A_{trn}}^{2}+\theta_{trn}^{2}\right)}\frac{c}{c-1}.$ $$

Here, we see that both bias and variance terms have been simplified and become more interpretable. For example, we can see the $1-c$ and $c-1$ in the denominator, which shows that the error blows up as we near the interpolation point ($c=1$), and hence, we have double descent. Suppose that $\theta_{trn}=\tau_{A_{trn}}\sqrt{n}$, $\tau_{A_{trn}}^{2}=d$, and $d,n\to\infty$. Then we see that in the underparameterized case ($c<1$), the asymptotic risk becomes

$$ $\tau_{\varepsilon_{trn}}^{2}\frac{c}{1-c}+(\beta_{*}^{T}u)\frac{1}{1-c}.$ $$

For the overparameterized case ($c>1$), we get that the asymptotic risk is

$$ $\tau_{\varepsilon_{trn}}^{2}\frac{1}{c-1}+(\beta_{*}^{T}u)\frac{c}{c-1}.$ $$

Here, we see a correction term appears and that the asymptotic risk is also dependent on the spike. Specifically, the correction term depends on the alignment between the eigenvector $u$ corresponding to the spike and the target function $\beta$. We see that this correction term also exhibits double descent. Finally, we see that we do not get the $\|\beta_{*}\|^{2}(1-1/c)$ term present in Equation 4.1 as $\beta_{*}$ is independent of the noise.

Alignment terms such as $\beta_{*}^{T}u$ have been seen before. For example, Wei et al. () considers estimating the generalization error for least squares regression for data with non-identity covariance. They show that the risk depends on the weighted alignment between the target $\beta_{*}$ and the eigenvectors of the covariance matrix.

Figure: Figure 4.2: The peak for generalization error versus $c$ curve has a peak at $c=\frac{\tau^{2}_{A_{trn}}}{\tau^{2}_{A_{trn}}+\mu^{2}}$. For both figures $\mu=\tau_{\varepsilon_{trn}}=\theta_{trn}=\theta_{tst}=1$ and $d=1000$. Left: We set $\tau_{A_{trn}}=1$, hence the peak should occur at $c=1/2$. Right: We set $\tau_{A_{trn}}=2$, hence the peak should occur at $c=4/5$.
Refer to caption: x4.png

###### Theorem 3 (Risk for Signal Plus Noise Problem) .

###### Theorem 4 (Risk for Signal Only Problem) .

###### Corollary 1 (Non-Regularized Error) .

#### Double Descent Peak Location Depends on Variance of the Bulk:

While we obtained interpretable results in the unregularized case, we would also like to understand the regularized case. One common feature of generalization risks for least squares regression in the proportional regime is that the asymptotic risk exhibits double descent. As seen from Theorem 3 and Corollary 1, we have double descent, and the peak occurs at $c=1$. However, looking at the formula in Theorem 4, it is unclear if the risk exhibits double descent. Empirically, examining the risk shows us that the model does exhibit double descent. However, the peak is no longer at $c=1$ and occurs at

$$ $c=\frac{\tau_{A_{trn}}^{2}}{\tau_{A_{trn}}^{2}+\mu^{2}}.$ $$

Figure 4.2 empirically verify this in two cases.

#### Proof Idea

In this section, we provide a brief discussion of the proofs of the two theorems, particularly focusing on how we handle the spike in the covariance matrix. The proof relies on the asymptotic limiting spectrum but only for the noise matrix $A$, not for $A+Z$. This is why we cannot let $\tau_{A_{trn}},\tau_{A_{tst}}$ go to zero. The proof builds upon ideas from Sonthalia & Nadakuditi (); Li & Sonthalia (). The main idea is that the solution $\beta_{so}$ or $\beta_{spn}$ is of the form:

$$ $X^{\dagger}y=(Z+A)^{\dagger}y.$ $$

Here, instead of using the spectrum of $Z+A$ to quantify the error, we expand $(Z+A)^{\dagger}$ using the result from Meyer () into sums of terms where we only invert $A$, not $A+Z$. Thus, we only care about the Stieltjes transform of $A$.

Let $\beta_{0}$ be the solution to the signal-only problem when $\tau_{\varepsilon_{trn}}^{2}=0$. Then we see that

$$ $\beta_{so}=\beta_{0}+(Z+A)^{\dagger}\varepsilon_{trn},\quad\text{and}\quad \beta_{spn}=\beta_{so}+(Z+A)^{\dagger}A\beta_{*}.$ $$

We compute a bias-variance type decomposition for the risk. For example, for the signal-plus-noise problem, we decompose it as

$$ $\|Z_{tst}\beta_{*}-Z_{tst}\beta_{spn}\|_{F}^{2}+\|A_{tst}\beta_{spn}\|_{F}^{2} +\|A_{tst}\beta_{*}\|_{F}^{2}-2\beta_{*}^{T}A_{tst}^{T}A_{tst}\beta_{spn}.$ $$

Then we show that each of these can be expressed as the product of *dependent* quadratic forms that are mostly of the form $\omega_{1}^{T}(A_{trn}^{T}A_{trn})^{\dagger}\omega_{2}$ or $\omega_{1}^{T}(A_{trn}^{T}A_{trn})^{\dagger}(A_{trn}^{T}A_{trn})^{\dagger}
\omega_{2}$ for some vectors $\omega_{1},\omega_{2}$. We use the almost sure weak convergence of the spectrum of $A$ to express these as $m(-\mu^{2})$, i.e., the Stieltjes transform of the limiting e.s.d for $A$ at $-\mu^{2}$. Additionally, we show that these terms concentrate and bound the variance. See lemmas numbered 10 through 22 in the Appendix. As such, we can estimate the expectation of the product using the product of the expectations. We need to keep track of two forms of error: first, from the approximation of the finite expectation using the asymptotic version, and second, from using the product of expectations to approximate the expectation of the product. These result in the $o(1/d)$ error in the theorems.

## 5 Limitation and Future Work

While this work takes an important step in understanding the generalization error for data with spiked covariances, significant work remains to be done.

#### Discrepancies with Moniri et al. ( 2023 )

There are a few discrepancies between the model considered here and the spiked covariance model from Moniri et al. (). Specifically:

- (i)
The distribution of the spectrum for $F_{0}$ versus that of $A$.
- (ii)
The dependency between $F_{0}$ (for us $A$) and $\tilde{X}w$ (for us $Z$).

We believe the distribution of the spectrum of $F_{0}$ is solvable using the techniques presented here. We need to use the appropriate Stieltjes transform, which has been studied in prior work (Péché, ). The dependency between $F_{0}$ and $\tilde{X}w$ also appears tractable but would introduce some additional quadratic forms that would need bounding. While these two problems are approachable, they require significant work and are avenues for future research.

#### Multiple Spikes and Steps

This paper only considers the model where there is a singular spike. However, depending on the step size, we may see multiple spikes. We believe that the manner in which Kausik et al. () generalizes Sonthalia & Nadakuditi () from rank one to generic low rank could be adapted to study the problem with multiple spikes. Additionally, we only consider the case where we take one step.

## 6 Conclusion

The feature matrix of a two-layer neural network has been shown to have spiked covariance with finitely many spikes. However, these spikes cannot be detected when we look at the asymptotic proportional limit. Nevertheless, the spikes are crucial as they arise due to the feature learning capabilities of neural networks. This paper considers linear regression with data that has a simplified spiked covariance. We show that the models here are natural extensions of prior work and quantify the generalization error. We show that for the signal-plus-noise model, the spike has an effect for finite matrices, but this effect disappears in the asymptotic limit. For the signal-only problem, we show that the dependence on the spike appears even in the asymptotic limit.

## Appendix A Proof of Theorem 4 (Signal Only)

In order to take advantage of previous results, we reformulate the problem in Equation 3.4 to make it align better with those settings. In particular, we consider

$$ $\beta_{so}^{T}=\arg\min_{\beta^{T}}\lVert\beta_{*}^{T}Z_{trn}+\varepsilon_{trn }^{T}-\beta^{T}(Z_{trn}+A_{trn})\rVert_{F}^{2}+\mu^{2}\|\beta\|_{F}^{2},$ (A.1) $$

$$ $\mathcal{R}_{so}(c,\mu,\tau)=\frac{1}{n_{tst}}\mathbb{E}_{A_{trn},A_{tst}, \varepsilon_{trn}}\left[\left\|\beta_{*}^{T}Z_{tst}-\beta_{so}^{T}(Z_{tst}+A_{ tst})\right\|_{F}^{2}\right],$ (A.2) $$

where $A_{trn}\in\mathbb{R}^{d\times n}$, $Z_{trn}=\theta_{trn}uv_{trn}^{T}\in\mathbb{R}^{d\times n}$, $\beta,\beta_{*},\varepsilon_{trn}\in\mathbb{R}^{d}$. Here we simply transpose everything and adjust the matrix dimensions accordingly. We also change the dimensions of the test data in the same way. This is equivalent to Equation 3.4 but allows us to match previous settings, from which we derive important results. Now we present the full proof in five steps.

### A.1 Step 1: Decompose the error term into bias and variance

This step is foundational and relies on Lemma 1. The key idea here is to separate the error into two components: bias and variance. This decomposition is crucial because it allows us to analyze these two sources of error independently. The first term represents the bias (error due to the model’s systematic deviation from the true function), and the second term represents the variance (error due to the model’s sensitivity to fluctuations in the training data).

###### Lemma 1 .

Suppose entries of $A_{tst}\in\mathbb{R}^{d\times n_{tst}}$ have mean 0 and variance $\tau_{A_{tst}}^{2}/$d. Then

$$ $\displaystyle\mathbb{E}_{\begin{subarray}{c}A_{trn},A_{tst},\varepsilon_{trn} \end{subarray}}\left[\lVert\beta_{*}^{T}Z_{tst}-\beta_{so}^{T}(Z_{tst}+A_{tst} )\rVert_{F}^{2}\right]$ $\displaystyle=$ $\displaystyle\underbrace{\mathbb{E}_{\begin{subarray}{c}A_{trn},A_{tst}, \varepsilon_{trn}\end{subarray}}\left[\lVert\beta_{*}^{T}Z_{tst}-\beta_{so}^{T }Z_{tst}\rVert_{F}^{2}\right]}_{Bias}+\underbrace{\mathbb{E}_{\begin{subarray} {c}A_{trn},A_{tst},\varepsilon_{trn}\end{subarray}}\left[\lVert\beta_{so}^{T}A _{tst}\rVert_{F}^{2}\right]}_{Variance}.$ $$

###### Proof.

This lemma is a direct extension of Lemma 1 in Sonthalia & Nadakuditi (). It follows from the fact that the cross term is zero in expectation because the entries of $A_{tst}$ are zero in expectation.
∎

###### Lemma 1 .

###### Proof.

### A.2 Step 2: Obtain preliminary expansions for bias and variance

This step involves deriving expressions for $\beta_{so}$ and then using these to expand the bias and variance terms.

We start by reformulating the ridge-regularized regression problem:

$$ $\beta_{so}^{T}=\arg\min_{\beta^{T}}\|\beta_{*}^{T}Z_{trn}+\varepsilon_{trn}^{T }-\beta^{T}(Z_{trn}+A_{trn})\|_{F}^{2}+\mu^{2}\|\beta\|_{F}^{2}.$ (A.3) $$

This can be rewritten using augmented matrices:

$$ $\displaystyle\beta_{so}^{T}$ $\displaystyle=\arg\min_{\beta^{T}}\lVert\beta_{*}^{T}Z_{trn}+\varepsilon_{trn} ^{T}-\beta^{T}(Z_{trn}+A_{trn})\rVert_{F}^{2}+\mu^{2}\|\beta\|_{F}^{2}$ $\displaystyle=\arg\min_{\beta^{T}}\lVert\beta_{*}^{T}\hat{Z}_{trn}+\hat{ \varepsilon}_{trn}^{T}-\beta^{T}(\hat{Z}_{trn}+\hat{A}_{trn})\rVert_{F}^{2},$ $$

where $\hat{A}_{trn}=\left[A_{trn}\quad\mu I\right]$, $\hat{Z}_{trn}=\left[Z_{trn}\quad 0\right]$, $\hat{\varepsilon}_{trn}^{T}=\left[\varepsilon_{trn}^{T}\quad 0\right]$.

The solution to this problem is given by:

$$ $\beta_{so}^{T}=(\beta_{*}^{T}\hat{Z}_{trn}+\hat{\varepsilon}_{trn}^{T})(\hat{Z }_{trn}+\hat{A}_{trn})^{{\dagger}},$ (A.4) $$

where ${\dagger}$ denotes the Moore-Penrose pseudoinverse.

Let $\hat{u}=u$, $\hat{v}_{trn}=\left[v_{trn}\quad 0\right]$, $\hat{v}_{tst}=\left[v_{tst}\quad 0\right]$ such that $\hat{Z}_{trn}=\theta_{trn}u\hat{v}_{trn}^{T}$ and $\hat{Z}_{tst}=\theta_{tst}u\hat{v}_{tst}^{T}$. We then define several helper variables ($\hat{h}$, $\hat{k}$, $\hat{s}$, $\hat{t}$, $\hat{\xi}$, $\gamma$, $\hat{p}$, $\hat{q}$) to simplify our expressions. These variables capture different aspects of the data and the solution, such as projections onto the signal and noise spaces.

$$ $\displaystyle\begin{aligned} &\hat{h}=\hat{v}_{trn}^{T}\hat{A}_{trn}^{\dagger} ,&&\hat{k}=\hat{A}_{trn}^{\dagger}u,\\ &\hat{s}=(I-\hat{A}_{trn}\hat{A}_{trn}^{\dagger})u,&&\hat{t}=\hat{v}_{trn}^{T} (I-\hat{A}_{trn}^{\dagger}\hat{A}_{trn}),\\ &\hat{\xi}=1+\theta_{trn}\hat{v}_{trn}^{T}\hat{A}_{trn}^{{\dagger}}u,&&\gamma= \theta_{trn}^{2}\|\hat{t}\|^{2}\|\hat{k}\|^{2}+\hat{\xi}^{2},\\ &\hat{p}=-\frac{\theta_{trn}^{2}\|\hat{k}\|^{2}}{\hat{\xi}}\hat{t}^{T}-\theta_ {trn}\hat{k},&\\ &\hat{q}^{T}=-\frac{\theta_{trn}\|\hat{t}\|^{2}}{\hat{\xi}}\hat{k}^{T}\hat{A}_ {trn}^{\dagger}-\hat{h}.&\end{aligned}$ $$

Our main objective is to compute the expectations in Lemma 1 in terms of the regularization constant $\mu$, the asymptotic ratio or Marchenko-Pastur shape $c$, the data parameters ($\theta_{trn}$, $\theta_{tst}$, $d$, $n_{tst}$), the noise parameters ($\tau_{A_{trn}},\tau_{A_{tst}},\tau_{\varepsilon_{trn}},\tau_{\varepsilon_{tst}}$), and the ground-truth parameters, in particular $\beta_{*}^{T}u$.

Note that in practice, we only assume access to $Z_{trn}+A_{trn}$, $\beta_{*}^{T}Z_{trn}+\varepsilon_{trn}$, and noise distributions during training.

###### Lemma 2 .

Suppose $\gamma\neq 0$. Under our assumptions,

$$ $\beta_{so}^{T}=\frac{\theta_{trn}\hat{\xi}}{\gamma}\beta_{*}^{T}u\hat{h}+\frac {\theta_{trn}^{2}\|\hat{t}\|^{2}}{\gamma}\beta_{*}^{T}u\hat{k}^{T}\hat{A}_{trn }^{\dagger}+\hat{\varepsilon}_{trn}^{T}\left(\hat{A}_{trn}^{\dagger}+\frac{ \theta_{trn}}{\hat{\xi}}\hat{t}^{T}\hat{k}^{T}\hat{A}_{trn}^{\dagger}-\frac{ \hat{\xi}}{\gamma}\hat{p}\hat{q}^{T}\right).$ $$

###### Proof.

From our optimization setting, it is clear that the optimal solution is given by

$$ $\displaystyle\beta_{so}^{T}$ $\displaystyle=(\beta_{*}^{T}\hat{Z}_{trn}+\hat{\varepsilon}_{trn}^{T})(\hat{Z} _{trn}+\hat{A}_{trn})^{\dagger}$ $\displaystyle=(\theta_{trn}\beta_{*}^{T}u\hat{v}_{trn}+\hat{\varepsilon}_{trn} ^{T})(\theta_{trn}u\hat{v}_{trn}+\hat{A}_{trn})^{\dagger}$ $\displaystyle=\theta_{trn}\beta_{*}^{T}u\hat{v}_{trn}(\theta_{trn}u\hat{v}_{ trn}+\hat{A}_{trn})^{\dagger}+\hat{\varepsilon}_{trn}^{T}(\theta_{trn}u\hat{v} _{trn}+\hat{A}_{trn})^{\dagger}.$ $$

By Theorem 3 in Meyer (), the pseudoinverse is

$$ $(\hat{A}_{trn}+\theta_{trn}u\hat{v}_{trn})^{\dagger}=\hat{A}_{trn}^{\dagger}+ \frac{\theta_{trn}}{\hat{\xi}}\hat{t}^{T}\hat{k}^{T}\hat{A}_{trn}^{\dagger}- \frac{\hat{\xi}}{\gamma}\hat{p}\hat{q}^{T}.$ (A.5) $$

By Lemma 2 in Li & Sonthalia (), the first term is

$$ $\theta_{trn}\beta_{*}^{T}u\hat{v}_{trn}\left(\hat{A}_{trn}^{\dagger}+\frac{ \theta_{trn}}{\hat{\xi}}\hat{t}^{T}\hat{k}^{T}\hat{A}_{trn}^{\dagger}-\frac{ \hat{\xi}}{\gamma}\hat{p}\hat{q}^{T}\right)=\frac{\theta_{trn}\hat{\xi}}{ \gamma}\beta_{*}^{T}u\hat{h}+\frac{\theta_{trn}^{2}\|\hat{t}\|^{2}}{\gamma} \beta_{*}^{T}u\hat{k}^{T}\hat{A}_{trn}^{\dagger}.$ $$

We then combine these results.
∎

###### Lemma 3 .

Suppose $\gamma\neq 0$. Under our assumptions,

$$ $y-\beta_{so}^{T}Z_{tst}=\beta_{*}^{T}Z_{tst}-\beta_{so}^{T}Z_{tst}=\frac{\hat{ \xi}}{\gamma}\beta_{*}^{T}Z_{tst}+\frac{\theta_{tst}\hat{\xi}}{\theta_{trn} \gamma}\hat{\varepsilon}_{trn}^{T}\hat{p}{v}_{tst}^{T}.$ $$

###### Proof.

From Lemma 2, we know that

$$ $\displaystyle\beta_{*}^{T}Z_{tst}-\beta_{so}^{T}Z_{tst}$ $\displaystyle=\beta_{*}^{T}Z_{tst}-\left(\frac{\theta_{trn}\hat{\xi}}{\gamma} \beta_{*}^{T}u\hat{h}+\frac{\theta_{trn}^{2}\|\hat{t}\|^{2}}{\gamma}\beta_{*}^ {T}u\hat{k}^{T}\hat{A}_{trn}^{\dagger}\right)Z_{tst}$ $\displaystyle\quad-\hat{\varepsilon}_{trn}^{T}\left(\hat{A}_{trn}^{\dagger}+ \frac{\theta_{trn}}{\hat{\xi}}\hat{t}^{T}\hat{k}^{T}\hat{A}_{trn}^{\dagger}- \frac{\hat{\xi}}{\gamma}\hat{p}\hat{q}^{T}\right)Z_{tst}.$ $$

Substitute $Z_{tst}=\theta_{tst}uv_{tst}^{T}$. The first two terms can be rewritten as

$$ $\displaystyle\theta_{tst}\beta_{*}^{T}\left(uv_{tst}^{T}-\frac{\theta_{trn} \hat{\xi}}{\gamma}u\hat{h}uv_{tst}^{T}+\frac{\theta_{trn}^{2}\|\hat{t}\|^{2}}{ \gamma}u\hat{k}^{T}\hat{A}_{trn}^{\dagger}uv_{tst}^{T}\right)$ $\displaystyle=\hskip 2.84544pt$ $\displaystyle\theta_{tst}\beta_{*}^{T}\left(uv_{tst}^{T}-\frac{\theta_{trn} \hat{\xi}}{\gamma}u\hat{v}_{trn}^{T}\hat{A}_{trn}^{\dagger}uv_{tst}^{T}+\frac{ \theta_{trn}^{2}\|\hat{t}\|^{2}}{\gamma}u\hat{k}^{T}\hat{A}_{trn}^{\dagger}uv_ {tst}^{T}\right).$ $$

Note $\hat{\xi}-1=\theta_{trn}\hat{v}_{trn}^{T}\hat{A}_{trn}^{{\dagger}}u$, $\hat{k}^{T}\hat{A}_{trn}^{\dagger}u=\hat{k}^{T}\hat{k}=\|\hat{k}\|^{2}$. The above equation becomes

$$ $\theta_{tst}\beta_{*}^{T}\left(uv_{tst}^{T}-\frac{\hat{\xi}(\hat{\xi}-1)}{ \gamma}uv_{tst}^{T}-\frac{\theta_{trn}^{2}\|\hat{t}\|^{2}\|\hat{k}\|^{2}}{ \gamma}uv_{tst}^{T}\right).$ $$

Using $\gamma=\theta_{trn}^{2}\|\hat{t}\|^{2}\|\hat{k}\|^{2}+\hat{\xi}^{2}$ to combine the coefficients, we have that

$$ $1-\frac{\hat{\xi}(\hat{\xi}-1)}{\gamma}-\frac{\theta_{trn}^{2}\|\hat{t}\|^{2} \|\hat{k}\|^{2}}{\gamma}\\ =\frac{\gamma+\hat{\xi}-\hat{\xi}^{2}-\theta_{trn}^{2}\|\hat{t}\|^{2}\|\hat{k} \|^{2}}{\gamma}=\frac{\hat{\xi}}{\gamma}.$ $$

Finally, the first two terms are nothing but

$$ $\frac{\hat{\xi}}{\gamma}\beta_{*}^{T}\theta_{tst}uv_{tst}^{T}=\frac{\hat{\xi}} {\gamma}\beta_{*}^{T}Z_{tst}.$ $$

Additionally, after substitutions, the last term can be simplified as

$$ $\displaystyle\hat{\varepsilon}_{trn}^{T}\left(\hat{A}_{trn}^{\dagger}+\frac{ \theta_{trn}}{\hat{\xi}}\hat{t}^{T}\hat{k}^{T}\hat{A}_{trn}^{\dagger}-\frac{ \hat{\xi}}{\gamma}\hat{p}\left(-\frac{\theta_{trn}\|\hat{t}\|^{2}}{\hat{\xi}} \hat{h}^{T}\hat{A}_{trn}^{\dagger}-\hat{h}\right)\right)Z_{tst}$ ( $\star$ ) $\displaystyle=\hskip 2.84544pt$ $\displaystyle\theta_{tst}\hat{\varepsilon}_{trn}^{T}\left(\hat{A}_{trn}^{ \dagger}uv_{tst}^{T}+\frac{\theta_{trn}}{\hat{\xi}}\hat{t}^{T}\hat{k}^{T}\hat{ A}_{trn}^{\dagger}uv_{tst}^{T}+\frac{\hat{\xi}}{\gamma}\hat{p}\left(\frac{ \theta_{trn}\|\hat{t}\|^{2}}{\hat{\xi}}\hat{k}^{T}\hat{A}_{trn}^{\dagger}u+ \hat{h}u\right)v_{tst}^{T}\right).$ $$

Since $\hat{k}=\hat{A}_{trn}^{\dagger}u$ and $\hat{h}u=\hat{v}_{trn}^{T}\hat{A}_{trn}^{\dagger}u=\frac{\hat{\xi}-1}{\theta_{
trn}}$, we then have that

$$ $\displaystyle(\star)$ $\displaystyle=\theta_{tst}\hat{\varepsilon}_{trn}^{T}\left(\hat{k}v_{tst}^{T}+ \frac{\theta_{trn}\|\hat{k}\|^{2}}{\hat{\xi}}\hat{t}^{T}v_{tst}^{T}+\frac{\hat {\xi}}{\gamma}\hat{p}\left(\frac{\theta_{trn}\|\hat{t}\|^{2}\|\hat{k}\|^{2}}{ \hat{\xi}}+\frac{\hat{\xi}-1}{\theta_{trn}}\right)v_{tst}^{T}\right)$ $\displaystyle=\theta_{tst}\hat{\varepsilon}_{trn}^{T}\left(\hat{k}v_{tst}^{T}+ \frac{\theta_{trn}\|\hat{k}\|^{2}}{\hat{\xi}}\hat{t}^{T}v_{tst}^{T}+\frac{\hat {\xi}}{\gamma}\hat{p}\left(\frac{\theta_{trn}^{2}\|\hat{t}\|^{2}\|\hat{k}\|^{2 }+\hat{\xi}^{2}-\hat{\xi}}{\hat{\xi}\theta_{trn}}\right)v_{tst}^{T}\right)$ $\displaystyle=\theta_{tst}\hat{\varepsilon}_{trn}^{T}\left(\hat{k}v_{tst}^{T}+ \frac{\theta_{trn}\|\hat{k}\|^{2}}{\hat{\xi}}\hat{t}^{T}v_{tst}^{T}+\frac{1}{ \gamma}\hat{p}\left(\frac{\gamma-\hat{\xi}}{\theta_{trn}}\right)v_{tst}^{T}\right)$ $\displaystyle=\theta_{tst}\hat{\varepsilon}_{trn}^{T}\left(\frac{1}{\theta_{ trn}}\left(\frac{\theta_{trn}^{2}\|\hat{k}\|^{2}}{\hat{\xi}}\hat{t}^{T}+\theta _{trn}\hat{k}\right)v_{tst}^{T}+\frac{1}{\theta_{trn}}\hat{p}v_{tst}^{T}-\frac {\hat{\xi}}{\theta_{trn}\gamma}\hat{p}v_{tst}^{T}\right)$ $\displaystyle=\hat{\varepsilon}_{trn}^{T}\left(-\frac{\theta_{tst}}{\theta_{ trn}}\hat{p}v_{tst}^{T}+\frac{\theta_{tst}}{\theta_{trn}}\hat{p}v_{tst}^{T}- \frac{\theta_{tst}\hat{\xi}}{\theta_{trn}\gamma}\hat{p}v_{tst}^{T}\right)=- \frac{\theta_{tst}\hat{\xi}}{\theta_{trn}\gamma}\hat{\varepsilon}_{trn}^{T} \hat{p}v_{tst}^{T},$ $$

where we recall the expression of $\hat{p}$ for the second to last equality. We then obtain the result.
∎

###### Lemma 4 .

If $A_{tst}$ has independent entries of mean 0 and variance $\tau_{A_{tst}}^{2}/{d}$, then $\mathbb{E}_{A_{tst}}[\|\beta_{so}^{T}A_{tst}\|_{F}^{2}]=\frac{\tau_{A_{tst}}^{
2}n_{tst}}{d}\|\beta_{so}\|_{F}^{2}$.

###### Proof.

Consider $\tilde{A}_{tst}=\frac{1}{\tau_{A_{tst}}}A_{tst}$, which has entries with variance $1/d$. We have that

$$ $\mathbb{E}_{A_{tst}}[\|\beta_{so}^{T}A_{tst}\|^{2}]=\tau_{A_{tst}}^{2}\mathbb{ E}_{A_{tst}}[\|\beta_{so}^{T}\tilde{A}_{tst}\|^{2}]=\frac{\tau_{A_{tst}}^{2}n_ {tst}}{d}\|\beta_{so}\|_{F}^{2}.$ $$

The last equality directly follows from Lemma 3 in Sonthalia & Nadakuditi ().
∎

###### Lemma 5 .

In the above setting,

$$ $\displaystyle\|\beta_{so}^{T}\|_{F}^{2}$ $\displaystyle=(\beta_{*}^{T}u)^{2}\|\tilde{\beta}\|_{F}^{2}+2\beta_{*}^{T} \tilde{W}_{opt}^{T}(\hat{Z}_{trn}+\hat{A}_{trn})^{{\dagger}T}\hat{\varepsilon} _{trn}$ $\displaystyle+\hat{\varepsilon}_{trn}^{T}(\hat{Z}_{trn}+\hat{A}_{trn})^{ \dagger}(\hat{Z}_{trn}+\hat{A}_{trn})^{{\dagger}T}\hat{\varepsilon}_{trn},$ $$

where $\tilde{\beta}^{T}=\hat{Z}_{trn}(\hat{Z}_{trn}+\hat{A}_{trn})^{\dagger}$, the optimal solution to the rank 1 denoising problem $\arg\min_{\beta_{*}^{T}}\|\hat{Z}_{trn}-\beta_{*}^{T}(\hat{Z}_{trn}+\hat{A}_{
trn})\|_{F}^{2}.$

###### Proof.

A direct expansion of $\|\beta_{so}\|_{F}^{2}$ yields

$$ $\displaystyle\|\beta_{so}^{T}\|_{F}^{2}$ $\displaystyle=(\beta_{*}^{T}\hat{Z}_{trn}+\hat{\varepsilon}_{trn}^{T})(\hat{Z} _{trn}+\hat{A}_{trn})^{\dagger}(\hat{Z}_{trn}+\hat{A}_{trn})^{{\dagger}T}( \beta_{*}^{T}\hat{Z}_{trn}+\hat{\varepsilon}_{trn}^{T})^{T}$ $\displaystyle=\beta_{*}^{T}\hat{Z}_{trn}(\hat{Z}_{trn}+\hat{A}_{trn})^{\dagger }(\hat{Z}_{trn}+\hat{A}_{trn})^{{\dagger}T}\hat{Z}_{trn}^{T}\beta_{*}$ $\displaystyle\ \ +2\beta_{*}^{T}\hat{Z}_{trn}(\hat{Z}_{trn}+\hat{A}_{trn})^{ \dagger}(\hat{Z}_{trn}+\hat{A}_{trn})^{{\dagger}T}\hat{\varepsilon}_{trn}$ $\displaystyle\ \ +\hat{\varepsilon}_{trn}^{T}(\hat{Z}_{trn}+\hat{A}_{trn})^{ \dagger}(\hat{Z}_{trn}+\hat{A}_{trn})^{{\dagger}T}\hat{\varepsilon}_{trn}.$ $$

Using $\tilde{\beta}^{T}=\hat{Z}_{trn}(\hat{Z}_{trn}+\hat{A}_{trn})^{\dagger}$ and $\hat{Z}_{trn}=\theta_{trn}u\hat{v}_{trn}$, we have that

$$ $\displaystyle\beta_{*}^{T}\hat{Z}_{trn}(\hat{Z}_{trn}+\hat{A}_{trn})^{\dagger} (\hat{Z}_{trn}+\hat{A}_{trn})^{{\dagger}T}\hat{Z}_{trn}^{T}W$ $\displaystyle=\$ $\displaystyle\beta_{*}^{T}u\operatorname{Tr}\left(\theta_{trn}^{2}\hat{v}_{trn }^{T}(\hat{Z}_{trn}+\hat{A}_{trn})^{\dagger}(\hat{Z}_{trn}+\hat{A}_{trn})^{{ \dagger}T}\hat{v}_{trn}\right)u^{T}W$ $\displaystyle=\$ $\displaystyle\beta_{*}^{T}u\operatorname{Tr}\left(\underbrace{\theta_{trn}u \hat{v}_{trn}^{T}}_{\hat{Z}_{trn}}(\hat{Z}_{trn}+\hat{A}_{trn})^{\dagger}(\hat {Z}_{trn}+\hat{A}_{trn})^{{\dagger}T}\underbrace{\theta_{trn}\hat{v}_{trn}u^{T }}_{\hat{Z}_{trn}}\right)u^{T}W$ $\displaystyle=\$ $\displaystyle(\beta_{*}^{T}u)^{2}\|\tilde{\beta}\|_{F}^{2},$ $$

where the second to last equality is since $u$ is a unit vector, and inserting it on both sides of the trace does not change the value. The other two terms follow.
∎

Note that these expressions in Lemma 4, 5 can be expanded even further. We will come back to them once we have the necessary expectations in the next step.

###### Lemma 2 .

###### Proof.

###### Lemma 3 .

###### Proof.

###### Lemma 4 .

###### Proof.

###### Lemma 5 .

###### Proof.

### A.3 Step 3: Compute expectations of important terms

Now we leverage techniques from random matrix theory to establish the following lemmas.

###### Lemma 6 ( Li & Sonthalia ( 2024 ) ) .

Let $A\in\mathbb{R}^{d\times n}$ and $\hat{A}=\left[A_{trn}\quad\mu I\right]\in\mathbb{R}^{d\times(n+d)}$. Suppose $A=U\Sigma V^{T}$ and $\hat{A}=\hat{U}\hat{\Sigma}\hat{V}^{T}$ are the respective singular value decompositions, then $\hat{U}=U$, and

- (a)
If $d<n$ (underparameterized regime),
$\hat{\Sigma}=\begin{bmatrix}\sqrt{\sigma_{1}(A)^{2}+\mu^{2}}&0&\cdots&0\\
0&\sqrt{\sigma_{2}(A)^{2}+\mu^{2}}&&0\\
\vdots&&\ddots&\vdots\\
0&0&\cdots&\sqrt{\sigma_{d}(A)^{2}+\mu^{2}}\end{bmatrix}\in\mathbb{R}^{d\times
d},$
and
$\hat{V}=\begin{bmatrix}V_{1:d}\Sigma\hat{\Sigma}^{-1}\\
\mu U\hat{\Sigma}^{-1}\end{bmatrix}\in\mathbb{R}^{(d+n)\times n}.$
- (b)
If $d>n$ (overparameterized regime),
$\hat{\Sigma}=\begin{bmatrix}\sqrt{\sigma_{1}(A)^{2}+\mu^{2}}&0&\cdots&0&&
\cdots&0\\
0&\sqrt{\sigma_{2}(A)^{2}+\mu^{2}}&&0&&&\\
\vdots&&\ddots&\vdots&&&\vdots\\
0&0&\cdots&\sqrt{\sigma_{n}(A)^{2}+\mu^{2}}&&&0\\
&&&&\mu&&\\
\vdots&&&&&\ddots&0\\
0&0&\cdots&0&\cdots&0&\mu\end{bmatrix}\in\mathbb{R}^{d\times d},$
and
$\hat{V}=\begin{bmatrix}V\Sigma_{1:n,1:n}^{T}C^{-1}&0\\
\mu U_{1:n}C^{-1}&U_{(n+1):d}\end{bmatrix}\in\mathbb{R}^{(d+n)\times d},$
where C is the upper left $n\times n$ submatrix of $\hat{\Sigma}$.

The following Lemmas are in Li & Sonthalia () for the case when $\tau^{2}=1$. We need the lemmas for general $\tau^{2}$ and so we present them here. The proofs are very similar to the proof in Li & Sonthalia () with the appropriate rescaling.

###### Lemma 7 .

Suppose $A\in\mathbb{R}^{d\times n}$ such that $d<n$, where the entries of $A$ are independent and have mean 0, variance $\tau^{2}/d$, and bounded fourth moment. Let $c=d/n$, $\hat{A}=[A\quad\mu I]\in\mathbb{R}^{d\times(n+d)}$, $W_{d}=\hat{A}\hat{A}^{T}$, and $W_{n}=\hat{A}^{T}\hat{A}$. Suppose $\lambda_{d}$ is a random non-zero eigenvalue of $W_{d}$, and $\lambda_{n}$ is a random non-zero eigenvalue of the largest $n$ eigenvalues of $W_{n}$. Then

- (i)
$\mathbb{E}\left[\frac{1}{\lambda_{d}}\right]=\mathbb{E}\left[\frac{1}{\lambda_
{n}}\right]=\frac{\sqrt{(\tau^{2}+\mu^{2}c-c\tau^{2})^{2}+4\mu^{2}c^{2}\tau^{2
}}-\tau^{2}-\mu^{2}c+c\tau^{2}}{2\mu^{2}\tau^{2}c}+o(1/\tau^{2})$.
- (ii)
$\mathbb{E}\left[\frac{1}{\lambda_{d}^{2}}\right]=\mathbb{E}\left[\frac{1}{
\lambda_{n}^{2}}\right]=\frac{\mu^{2}c^{2}+\mu^{2}c+(c-1)^{2}\tau^{2}}{2\mu^{4
}c\sqrt{(\tau^{2}+\mu^{2}c-c\tau^{2})^{2}+4\mu^{2}c^{2}\tau^{2}}}+\frac{1}{2
\mu^{4}}\left(1-\frac{1}{c}\right)+o(1/\tau^{2}).$
- (iii)
$\mathbb{E}\left[\frac{1}{\lambda_{d}^{3}}\right]=\mathbb{E}\left[\frac{1}{
\lambda_{n}^{3}}\right]=\frac{c^{3}}{2\tau^{6}}m_{c}^{\prime\prime}(-\frac{cu^
{2}}{\tau^{2}})+o(1/\tau^{2}),$

where $m_{c}(z)=-\frac{1-z-c-\sqrt{(1-z-c)^{2}-4cz}}{-2zc}$ is the Stieltjes transform.

###### Proof.

First, it is trivial to see that $1/\lambda_{d}=1/\lambda_{n}$ in expectation since $W_{d}$ and $W_{n}$ share the same set of eigenvalues from which we sample. Here we consider $W_{d}$ and define $\tilde{\mu}=\mu/\tau$, $\tilde{A}=A/\tau$. Note $\tilde{A}$ then has entries with mean 0 and variance $1/d$.

By the definition of $W_{d}$, $\frac{c}{\tau^{2}}W_{d}$ is the correct normalization to turn it into a Wishart matrix. Also, by assumptions on $A$, the eigenvalues of $\frac{c}{\tau^{2}}AA^{T}=c\tilde{A}\tilde{A}^{T}$ converge to the Marchenko-Pastur distribution with shape c. With these results, we have that

$$ $\displaystyle cW_{d}$ $\displaystyle=c\begin{bmatrix}A&\mu I\end{bmatrix}\begin{bmatrix}A^{T}\\ \mu I\end{bmatrix}=cAA^{T}+c\mu^{2}I$ $\displaystyle\rightarrow(c\lambda_{d})_{i}=c\sigma_{i}(A)^{2}+c\mu^{2}$ $\displaystyle\rightarrow(c\lambda_{d})_{i}=c\tau^{2}\sigma_{i}(\tilde{A})^{2}+ c\tau^{2}\tilde{\mu}^{2}$ $\displaystyle\rightarrow\left(\frac{c\lambda_{d}}{\tau^{2}}\right)_{i}=c\sigma _{i}(\tilde{A})^{2}+c\tilde{\mu}^{2}.$ $$

The rest of the proof follows the same fashion as in Li & Sonthalia (), with additional care on the general variances. We provide a sketch here: we consider the Stieltjes transform for computing the expectation of inversed eigenvalues, which is given by

$$ $m_{c}(z)=\mathbb{E}_{\lambda}\left[\frac{1}{\lambda-z}\right]=-\frac{1-z-c- \sqrt{(1-z-c)^{2}-4cz}}{-2zc}.$ $$

We plug in $z=-c\tilde{\mu}^{2}$ to obtain the needed result,

$$ $\mathbb{E}\left[\frac{\tau^{2}}{c\lambda_{d}}\right]=m_{c}(-c\tilde{\mu}^{2}) \longrightarrow\mathbb{E}\left[\frac{1}{\lambda_{d}}\right]=\frac{c}{\tau^{2}} m_{c}(-c\tilde{\mu}^{2}).$ $$

Simplifying and plugging in $\tilde{\mu}=\mu/\tau$, we have that

$$ $\mathbb{E}\left[\frac{1}{\lambda_{d}}\right]=\mathbb{E}\left[\frac{1}{\lambda+ \mu^{2}}\right]=\frac{\sqrt{(\tau^{2}+\mu^{2}c-c\tau^{2})^{2}+4\mu^{2}c^{2} \tau^{2}}-\tau^{2}-\mu^{2}c+c\tau^{2}}{2\mu^{2}\tau^{2}c}.$ $$

To get expectations for the squared and cubed inverse, we need to compute the derivatives of $m_{c}(z)$:

$$ $m_{c}^{\prime}(z)=\mathbb{E}_{\lambda}\left[\frac{1}{(\lambda-z)^{2}}\right]= \frac{(c-z+\sqrt{-4cz+(1-c-z)^{2}}-1)(c+z+\sqrt{-4cz+(1-c-z)^{2}}-1)}{4cz^{2} \sqrt{-4cz+(1-c-z)^{2}}}.$ $$

$$ $\displaystyle m_{c}^{\prime\prime}(z)=\mathbb{E}_{\lambda}\left[\frac{2}{( \lambda-z)^{3}}\right]$ $\displaystyle=\frac{z(c+1)(z^{2}+3(c-1)^{2})-3z^{2}(c^{2}+1)-(c-1)^{4}}{cz^{3} (-4cz+(1-c-z)^{2})^{3/2}}$ $\displaystyle\ \ +\frac{(c-1)(2z(c+1)-z^{2}-(c-1)^{2})}{cz^{3}(-4cz+(1-c-z)^{2 })}.$ $$

Then we have

$$ $\displaystyle\mathbb{E}\left[\frac{\tau^{4}}{c^{2}\lambda_{d}^{2}}\right]$ $\displaystyle=m_{c}^{\prime}(-c\tilde{\mu}^{2})\longrightarrow\mathbb{E}\left[ \frac{1}{\lambda_{d}^{2}}\right]=\frac{c^{2}}{\tau^{4}}m_{c}^{\prime}\left(- \frac{c\mu^{2}}{\tau^{2}}\right),$ $\displaystyle\mathbb{E}\left[\frac{2\tau^{6}}{c^{3}\lambda_{d}^{3}}\right]$ $\displaystyle=m_{c}^{\prime\prime}(-c\tilde{\mu}^{2})\longrightarrow\mathbb{E} \left[\frac{1}{\lambda_{d}^{3}}\right]=\frac{c^{3}}{2\tau^{6}}m_{c}^{\prime \prime}\left(-\frac{c\mu^{2}}{\tau^{2}}\right).$ $$

Similarly, we simplify these results to get the conclusion. Note for $\mathbb{E}\left[\frac{1}{\lambda_{d}^{3}}\right]$, the formula becomes extremely complicated. Hence, we only provide a heuristic formula in the lemma statement and use Sympy to simplify further computations when needed.
∎

Next we have similar Lemma for $c>1$.

###### Lemma 8 .

Suppose $A\in\mathbb{R}^{d\times n}$ such that $d>n$, where the entries of $A$ are independent and have mean 0, variance $\tau^{2}/d$, and bounded fourth moment. Let $c=d/n$, $\hat{A}=[A\quad\mu I]\in\mathbb{R}^{d\times(d+n)}$, $W_{d}=\hat{A}\hat{A}^{T}$, and $W_{n}=\hat{A}^{T}\hat{A}$. Suppose $\lambda_{n}$ is a random non-zero eigenvalue of $W_{n}$, and $\lambda_{d}$ is a random non-zero eigenvalue of the largest $d$ eigenvalues of $W_{d}$. Then

- (i)
$\mathbb{E}\left[\frac{1}{\lambda_{d}}\right]=\mathbb{E}\left[\frac{1}{\lambda_
{n}}\right]=\frac{\sqrt{(-\tau^{2}+\mu^{2}c+c\tau^{2})^{2}+4\mu^{2}c\tau^{2}}-
\tau^{2}-\mu^{2}c+c\tau^{2}}{2\mu^{2}\tau^{2}}+o(1/\tau^{2})$.
- (ii)
$\mathbb{E}\left[\frac{1}{\lambda_{d}^{2}}\right]=\mathbb{E}\left[\frac{1}{
\lambda_{n}^{2}}\right]=\frac{\mu^{2}c^{2}+\mu^{2}c+(c-1)^{2}\tau^{2}}{2\mu^{4
}\sqrt{(-\tau^{2}+\mu^{2}c+c\tau^{2})^{2}+4\mu^{2}c\tau^{2}}}+\frac{1}{2\mu^{4
}}\left(1-c\right)+o(1/\tau^{2}).$
- (iii)
$\mathbb{E}\left[\frac{1}{\lambda_{d}^{3}}\right]=\mathbb{E}\left[\frac{1}{
\lambda_{n}^{3}}\right]=\frac{1}{2\tau^{6}}m_{1/c}^{\prime\prime}(-\frac{u^{2}
}{\tau^{2}})+o(1/\tau^{2})$,

where $m_{1/c}(z)=-\frac{1-z-1/c-\sqrt{(1-z-1/c)^{2}-4z/c}}{-2z/c}$ is the Stieltjes transform.

###### Proof.

The proof is analogous to the $c<1$ case. We consider $W_{n}$ and define $\tilde{\mu}=\mu/\tau$, $\tilde{A}=A/\tau$. By assumptions on $A$, the eigenvalues of $\frac{1}{\tau^{2}}A^{T}A=\tilde{A}^{T}\tilde{A}$ converge to the Marchenko-Pastur distribution with shape $1/c$, and

$$ $\displaystyle(\lambda_{n})_{i}$ $\displaystyle=\sigma_{i}(A)^{2}+\mu^{2}$ $\displaystyle\rightarrow(\lambda_{n})_{i}=\tau^{2}\sigma_{i}(\tilde{A})^{2}+ \tau^{2}\tilde{\mu}^{2}$ $\displaystyle\rightarrow\left(\frac{\lambda_{n}}{\tau^{2}}\right)_{i}=\sigma_{ i}(\tilde{A})^{2}+\tilde{\mu}^{2}.$ $$

The Stieltjes transform becomes

$$ $m_{1/c}(z)=-\frac{1-z-1/c-\sqrt{(1-z-1/c)^{2}-4z/c}}{-2z/c}.$ (A.6) $$

Similar to Lemma 7, we need to plug in $z=-\tilde{\mu}^{2}$ here and compute necessary derivatives:

$$ $\displaystyle\mathbb{E}\left[\frac{\tau^{2}}{\lambda_{n}}\right]$ $\displaystyle=m_{1/c}(-\tilde{\mu}^{2})\longrightarrow\mathbb{E}\left[\frac{1} {\lambda_{n}}\right]=\frac{1}{\tau^{2}}m_{1/c}(-\tilde{\mu}^{2})=\frac{1}{\tau ^{2}}m_{1/c}\left(-\frac{\mu^{2}}{\tau^{2}}\right).$ $\displaystyle\mathbb{E}\left[\frac{\tau^{4}}{\lambda_{n}^{2}}\right]$ $\displaystyle=m_{1/c}^{\prime}(-\tilde{\mu}^{2})\longrightarrow\mathbb{E}\left [\frac{1}{\lambda_{n}^{2}}\right]=\frac{1}{\tau^{4}}m_{1/c}^{\prime}\left(- \frac{\mu^{2}}{\tau^{2}}\right).$ $\displaystyle\mathbb{E}\left[\frac{2\tau^{6}}{\lambda_{n}^{3}}\right]$ $\displaystyle=m_{1/c}^{\prime\prime}(-\tilde{\mu}^{2})\longrightarrow\mathbb{E }\left[\frac{1}{\lambda_{n}^{3}}\right]=\frac{1}{2\tau^{6}}m_{1/c}^{\prime \prime}\left(-\frac{\mu^{2}}{\tau^{2}}\right).$ $$

We simplify these terms to get the results. Again we skip the full formula for the cubed inverse.
∎

Finally, we shall need the following estimates as well.

###### Lemma 9 .

Suppose $A\in\mathbb{R}^{d\times n}$, where the entries of $A$ are independent and have mean 0, variance $\tau^{2}/d$, and bounded fourth moment. Let $c=d/n$. Suppose $\lambda$ is a random eigenvalue of A. Then

- (i)
If $d>n$, $\mathbb{E}\left[\frac{\lambda}{\lambda+\mu^{2}}\right]=c\left(\frac{1}{2}+
\frac{\tau^{2}+\mu^{2}c-\sqrt{(-\tau^{2}+\mu^{2}c+c\tau^{2})^{2}+4\mu^{2}c\tau
^{2}}}{2c\tau^{2}}\right)+o(1/\tau^{2})$.
- (ii)
If $d<n$, $\mathbb{E}\left[\frac{\lambda}{\lambda+\mu^{2}}\right]=\frac{1}{2}+\frac{\tau^
{2}+\mu^{2}c-\sqrt{(\tau^{2}+\mu^{2}c-c\tau^{2})^{2}+4\mu^{2}c^{2}\tau^{2}}}{2
c\tau^{2}}+o(1/\tau^{2})$.
- (iii)
If $d>n$, $\mathbb{E}\left[\frac{\lambda}{(\lambda+\mu^{2})^{2}}\right]=c\left(\frac{\tau
^{2}+c\tau^{2}+\mu^{2}c}{2\tau^{2}\sqrt{(-\tau^{2}+\mu^{2}c+c\tau^{2})^{2}+4
\mu^{2}c\tau^{2}}}-\frac{1}{2\tau^{2}}\right)+o(1/\tau^{2})$.
- (iv)
If $d<n$, $\mathbb{E}\left[\frac{\lambda}{(\lambda+\mu^{2})^{2}}\right]=\frac{\tau^{2}+c
\tau^{2}+\mu^{2}c}{2\tau^{2}\sqrt{(\tau^{2}+\mu^{2}c-c\tau^{2})^{2}+4\mu^{2}c^
{2}\tau^{2}}}-\frac{1}{2\tau^{2}}+o(1/\tau^{2})$.
- (v)
If $d>n$, $\mathbb{E}\left[\frac{\lambda^{2}}{(\lambda+\mu^{2})^{2}}\right]=\frac{c\tau^{
2}+\tau^{2}+2\mu^{2}c}{2\tau^{2}}-\frac{c^{2}\tau^{4}+3c^{2}\tau^{2}\mu^{2}-2c
^{2}\mu^{4}+2c\tau^{4}+3c\tau^{2}\mu^{2}-\tau^{4}}{2\tau^{2}\sqrt{(-\tau^{2}+
\mu^{2}c+c\tau^{2})^{2}+4\mu^{2}c\tau^{2}}}+o(1/\tau^{2})$.
- (vi)
If $d<n$, $\mathbb{E}\left[\frac{\lambda^{2}}{(\lambda+\mu^{2})^{2}}\right]=\frac{c\tau^{
2}+\tau^{2}+2\mu^{2}c}{2c\tau^{2}}-\frac{c^{2}\tau^{4}+3c^{2}\tau^{2}\mu^{2}-2
c^{2}\mu^{4}+2c\tau^{4}+3c\tau^{2}\mu^{2}-\tau^{4}}{2c\tau^{2}\sqrt{(\tau^{2}+
\mu^{2}c-c\tau^{2})^{2}+4\mu^{2}c^{2}\tau^{2}}}+o(1/\tau^{2})$.

###### Proof.

The results immediately follow from Lemmas 7, 8 by

$$ $\mathbb{E}\left[\frac{\lambda}{\lambda+\mu^{2}}\right]=1-\mu^{2}\mathbb{E} \left[\frac{1}{\lambda+\mu^{2}}\right]=1-\mu^{2}\mathbb{E}\left[\frac{1}{ \lambda_{d}}\right],$ $$

$$ $\mathbb{E}\left[\frac{\lambda}{(\lambda+\mu^{2})^{2}}\right]=\mathbb{E}\left[ \frac{1}{\lambda+\mu^{2}}\right]-\mu^{2}\mathbb{E}\left[\frac{1}{(\lambda+\mu^ {2})^{2}}\right],$ $$

$$ $\mathbb{E}\left[\frac{\lambda^{2}}{(\lambda+\mu^{2})^{2}}\right]=\mathbb{E} \left[\frac{\lambda}{\lambda+\mu^{2}}\right]-\mu^{2}\mathbb{E}\left[\frac{ \lambda}{(\lambda+\mu^{2})^{2}}\right].$ $$

∎

###### Remark 1 .

We can also evaluate the following expectations:

$$ $\mathbb{E}\left[\frac{\lambda}{(\lambda+\mu^{2})^{3}}\right]=\mathbb{E}\left[ \frac{1}{(\lambda+\mu^{2})^{2}}\right]-\mu^{2}\mathbb{E}\left[\frac{1}{( \lambda+\mu^{2})^{3}}\right],$ $$

$$ $\mathbb{E}\left[\frac{\lambda^{2}}{(\lambda+\mu^{2})^{3}}\right]=\mathbb{E} \left[\frac{\lambda}{(\lambda+\mu^{2})^{2}}\right]-\mu^{2}\mathbb{E}\left[ \frac{\lambda}{(\lambda+\mu^{2})^{3}}\right].$ $$

However, they are too complicated to be presented here and are not always useful. We will use Sympy when these terms show up.

A note on bounded variances: Previous works in Li & Sonthalia (), Sonthalia & Nadakuditi (), and Kausik et al. () have established proofs that bound variances of terms present in our $\beta_{so}^{T}$ formula, which implies that their variances asymptotically decay to 0. In our setting, since the variance parameters $\tau_{A}$ is at most $O(n)$ and we normalize by $\tau_{A}$ to get the appropriate limits. However this means that when $\tau_{A}$ grows we actually get faster convergence. $\tau_{\varepsilon}$ has finite value. Hence they only induce a multiplicative change in the total variance of terms and do not affect the asymptotic decaying phenomena. In other words, these terms are still highly concentrated, and we can treat them as almost independent when $d,n_{trn}\rightarrow\infty$. A direct consequence of this is that we can compute the expectation of a product as the product of its individual expectations.

###### Lemma 6 ( Li & Sonthalia ( 2024 ) ) .

###### Lemma 7 .

###### Proof.

###### Lemma 8 .

###### Proof.

###### Lemma 9 .

###### Proof.

###### Remark 1 .

### A.4 Step 4: Estimate Quantities Using Random Matrix Estimates

The following lemmas compute the mean and variance of terms in the $\beta_{so}^{T}$ formula. The proofs are similar to Lemmas 13-18 in Li & Sonthalia (); we repeat it for Lemma 10 and provide a sketch for the rest.

###### Lemma 10 .

Under our assumptions, we have that

$$ $\mathbb{E}_{A_{trn}}\left[\|\hat{h}\|^{2}\right]=\begin{cases}c\left(\frac{ \tau_{A_{trn}}^{2}+c\tau_{A_{trn}}^{2}+\mu^{2}c}{2\tau_{A_{trn}}^{2}\sqrt{ \left(\tau_{A_{trn}}^{2}+\mu^{2}c-c\tau_{A_{trn}}^{2}\right)^{2}+4\mu^{2}c^{2} \tau_{A_{trn}}^{2}}}-\frac{1}{2\tau_{A_{trn}}^{2}}\right)+o(1/\tau^{2}_{A_{trn }})&c<1\\ c\left(\frac{\tau_{A_{trn}}^{2}+c\tau_{A_{trn}}^{2}+\mu^{2}c}{2\tau_{A_{trn}}^ {2}\sqrt{\left(-\tau_{A_{trn}}^{2}+\mu^{2}c+c\tau_{A_{trn}}^{2}\right)^{2}+4 \mu^{2}c\tau_{A_{trn}}^{2}}}-\frac{1}{2\tau_{A_{trn}}^{2}}\right)+o(1/\tau^{2} _{A_{trn}})&c>1\end{cases}$ $$

and $Var(\|\hat{h}\|^{2})=o(1/\tau^{2}_{A_{trn}})$.

###### Proof.

Recall that $\hat{h}=\hat{v}_{trn}^{T}\hat{A}_{trn}^{\dagger}$, where $\hat{v}_{trn}=\begin{bmatrix}v_{trn}\ \mathbf{0}_{d}\end{bmatrix}\in\mathbb{R}
^{n_{trn}+d}$, with $v_{trn}\in\mathbb{R}^{n_{trn}}$ being a unit vector. We aim to compute $\mathbb{E}_{A_{trn}}[\|\hat{h}\|^{2}]$. First, consider the singular value decomposition (SVD) of $\hat{A}_{trn}$:

$$ $\hat{A}_{trn}=U\hat{\Sigma}\hat{V}^{T},$ $$

where $U\in\mathbb{R}^{d\times d}$ is orthogonal, $\hat{\Sigma}\in\mathbb{R}^{d\times d}$ is diagonal with non-negative entries, and $\hat{V}\in\mathbb{R}^{(n_{trn}+d)\times d}$ has orthonormal columns. Then, the pseudoinverse of $\hat{A}_{trn}$ is given by

$$ $\hat{A}_{trn}^{\dagger}=\hat{V}\hat{\Sigma}^{-1}U^{T}$ $$

and

$$ $\hat{h}=\hat{v}_{trn}^{T}\hat{A}_{trn}^{\dagger}.$ $$

Therefore, we have

$$ $\|\hat{h}\|^{2}=\hat{h}\hat{h}^{T}=\hat{v}_{trn}^{T}\hat{A}_{trn}^{\dagger} \hat{A}_{trn}^{{\dagger}T}\hat{v}_{trn}=\hat{v}_{trn}^{T}\hat{V}\hat{\Sigma}^{ -2}\hat{V}^{T}\hat{v}_{trn}.$ $$

Assume $c<1$. We can partition $\hat{V}$ and $\hat{v}_{trn}$ to reflect the structure of $\hat{A}_{trn}$. Using Lemma 6 let us write $\hat{V}$ as

$$ $\hat{V}=\begin{bmatrix}V_{1:d}\Sigma\hat{\Sigma}^{-1}\\ \mu U\hat{\Sigma}^{-1}\end{bmatrix}.$ $$

Since the last $d$ elements of $\hat{v}_{trn}$ are 0, we get that

$$ $\hat{v}_{trn}^{T}\hat{V}=v_{trn}^{T}V_{1:d}\Sigma\hat{\Sigma}^{-1}.$ $$

Thus, we see that

$$ $\displaystyle\mathbb{E}\|\hat{h}\|^{2}$ $\displaystyle=v_{trn}^{T}V_{1:d}\Sigma\hat{\Sigma}^{-4}\Sigma V_{1:d}^{T}v_{trn}$ $\displaystyle=\sum_{i=1}^{d}(v_{trn}^{T}V_{1:d})_{i}^{2}\frac{\lambda_{i}}{( \lambda_{i}+\mu^{2})^{2}}.$ $$

Note $v_{trn}^{T}V_{1:d}$ is a uniformly random unit vector in $\mathbb{R}^{n_{trn}}$ by the rotational bi-invariance assumption on $A_{trn}$. Thus, when we take expectations, this becomes $1/n_{trn}$.
We then see that

$$ $\mathbb{E}\left[\|\hat{h}\|^{2}\right]=\mathbb{E}\left[\sum_{i=1}^{d}\frac{1}{ n_{trn}}\frac{\lambda_{i}}{(\lambda_{i}+\mu^{2})^{2}}\right]$ $$

The term inside the expectation is another expectation and we can use weak convergence. Thus, in expectation, this term by Lemma 7 becomes

$$ $\mathbb{E}_{A_{trn}}\left[\frac{\lambda}{(\lambda+\mu^{2})^{2}}\right]=c\left( \frac{\tau_{A_{trn}}^{2}+c\tau_{A_{trn}}^{2}+\mu^{2}c}{2\tau_{A_{trn}}^{2} \sqrt{\left(\tau_{A_{trn}}^{2}+\mu^{2}c-c\tau_{A_{trn}}^{2}\right)^{2}+4\mu^{2 }c^{2}\tau_{A_{trn}}^{2}}}-\frac{1}{2\tau_{A_{trn}}^{2}}\right)+o(1/\tau^{2}_{ A_{trn}}),$ $$

where the additional factor of $c$ comes from projecting $d$ entries onto the $n_{trn}$ coordinates of the randomly uniform vector.

For $c>1$, we use the corresponding SVD in Lemma 6 and the expectation in Lemma 8. We get

$$ $\mathbb{E}_{A_{trn}}\left[\frac{\lambda}{(\lambda+\mu^{2})^{2}}\right]=c\left( \frac{\tau_{A_{trn}}^{2}+c\tau_{A_{trn}}^{2}+\mu^{2}c}{2\tau_{A_{trn}}^{2} \sqrt{\left(-\tau_{A_{trn}}^{2}+\mu^{2}c+c\tau_{A_{trn}}^{2}\right)^{2}+4\mu^{ 2}c\tau_{A_{trn}}^{2}}}-\frac{1}{2\tau_{A_{trn}}^{2}}\right)+o(1/\tau^{2}_{A_{ trn}}).$ $$

∎

###### Lemma 11 .

Under our assumptions, we have that

$$ $\mathbb{E}_{A_{trn}}\left[\|\hat{k}\|^{2}\right]=\begin{cases}\frac{\sqrt{ \left(\tau_{A_{trn}}^{2}+\mu^{2}c-c\tau_{A_{trn}}^{2}\right)^{2}+4\mu^{2}c^{2} \tau_{A_{trn}}^{2}}-\tau_{A_{trn}}^{2}-\mu^{2}c+c\tau_{A_{trn}}^{2}}{2\mu^{2} \tau_{A_{trn}}^{2}}+o(1/\tau^{2}_{A_{trn}})&c<1\\ \frac{\sqrt{\left(-\tau_{A_{trn}}^{2}+\mu^{2}c+c\tau_{A_{trn}}^{2}\right)^{2}+ 4\mu^{2}c\tau_{A_{trn}}^{2}}-\tau_{A_{trn}}^{2}-\mu^{2}c+c\tau^{2}}{2\mu^{2} \tau_{A_{trn}}^{2}}+o(1/\tau^{2}_{A_{trn}})&c>1\end{cases}$ $$

and $Var(\|\hat{k}\|^{2})=o(1/\tau^{2}_{A_{trn}})$.

###### Proof.

(Sketch)
Recall that $k=\hat{A}_{trn}^{{\dagger}}u$. Using SVD of $\hat{A}_{trn}$ and a similar argument, we have

$$ $\mathbb{E}_{A_{trn}}\left[u^{T}\hat{A}_{trn}^{{\dagger}T}\hat{A}_{trn}^{{ \dagger}}u\right]=\begin{cases}\mathbb{E}_{A_{trn}}\left[\frac{1}{\lambda+\mu^ {2}}\right]&c<1\\ \frac{1}{c}\mathbb{E}_{A_{trn}}\left[\frac{1}{\lambda+\mu^{2}}\right]+\left(1- \frac{1}{c}\right)\frac{1}{\mu^{2}}&c>1\end{cases}$ $$

where for $c>1$, $1/c$ of the eigenvalues follow the expectation and the rest equals $1/\mu^{2}$.
∎

###### Lemma 12 .

Under our assumptions, we have that

$$ $\mathbb{E}_{A_{trn}}\left[\|\hat{t}\|^{2}\right]=\begin{cases}\frac{1}{2\tau_{ A_{trn}}^{2}}\left(\tau_{A_{trn}}^{2}-c\tau_{A_{trn}}^{2}-\mu^{2}c+\sqrt{\left (\tau_{A_{trn}}^{2}-c\tau_{A_{trn}}^{2}+\mu^{2}c\right)^{2}+4c^{2}\mu^{2}\tau_ {A_{trn}}^{2}}\right)+o(1/\tau^{2}_{A_{trn}})&c<1\\ \frac{1}{2\tau_{A_{trn}}^{2}}\left(-\tau_{A_{trn}}^{2}+c\tau_{A_{trn}}^{2}-\mu ^{2}c+\sqrt{\left(-\tau_{A_{trn}}^{2}+c\tau_{A_{trn}}^{2}+\mu^{2}c\right)^{2}+ 4c\mu^{2}\tau_{A_{trn}}^{2}}\right)+o(1/\tau^{2}_{A_{trn}})&c>1\end{cases}$ $$

and $Var(\|\hat{t}\|^{2})=o(1/\tau^{2}_{A_{trn}})$.

###### Proof.

(Sketch) Recall that $\hat{t}=\hat{v}_{trn}^{T}(I-\hat{A}_{trn}^{\dagger}\hat{A}_{trn})$. Since $(I-\hat{A}_{trn}^{\dagger}\hat{A}_{trn})$ is a projection matrix, we have $\|\hat{t}\|^{2}=1-\hat{v}_{trn}^{T}\hat{A}_{trn}^{\dagger}\hat{A}_{trn}\hat{v}
_{trn}$, and with SVD of $\hat{A}_{trn}$,

$$ $1-\mathbb{E}_{A_{trn}}\left[\hat{v}_{trn}^{T}\hat{V}\hat{\Sigma}^{-2}\hat{V}^{ T}\hat{v}_{trn}\right]=\begin{cases}1-c\mathbb{E}_{A_{trn}}\left[\frac{\lambda }{\lambda+\mu^{2}}\right]&c<1\\ 1-\mathbb{E}_{A_{trn}}\left[\frac{\lambda}{\lambda+\mu^{2}}\right]&c>1\end{ cases}.$ $$

∎

###### Lemma 13 .

Under our assumptions, we have that $\mathbb{E}_{A_{trn}}\left[\hat{\xi}\right]=1$
and $Var(\hat{\xi})=O(\theta_{trn}^{2}/(d\tau^{2}_{A_{trn}}))$.

###### Proof.

Recall that $\hat{\xi}=1+\theta_{trn}\hat{v}_{trn}^{T}\hat{A}_{trn}^{{\dagger}}u$. Using the SVD of $\hat{A}_{trn}$, we have that

$$ $\mathbb{E}_{A_{trn}}\left[\hat{\xi}\right]=1+\mathbb{E}_{A_{trn}}\left[\theta_ {trn}\hat{v}_{trn}^{T}\hat{V}\hat{\Sigma}U^{T}u\right]=1.$ $$

because $U$ is a uniformly random orthogonal matrix, which makes $U^{T}u$ a uniformly random vector that is independent of $\hat{V}$ and $\hat{\Sigma}$. We similarly compute $\mathbb{E}_{A_{trn}}\left[\hat{\xi}^{2}\right]$ for the variance.
∎

###### Lemma 14 .

Under our assumptions, we have that

$$ $\mathbb{E}_{A_{trn}}\left[\gamma\right]=\begin{cases}1+\frac{\theta_{trn}^{2}} {2\tau_{A_{trn}}^{4}}\left(\tau_{A_{trn}}^{2}+c\tau_{A_{trn}}^{2}+\mu^{2}c- \sqrt{\left(\tau_{A_{trn}}^{2}-c\tau_{A_{trn}}^{2}+\mu^{2}c\right)^{2}+4c^{2} \mu^{2}\tau_{A_{trn}}^{2}}\right)+o(1/\tau^{2}_{A_{trn}})&c<1\\ 1+\frac{\theta_{trn}^{2}}{2\tau_{A_{trn}}^{4}}\left(\tau_{A_{trn}}^{2}+c\tau_{ A_{trn}}^{2}+\mu^{2}c-\sqrt{\left(-\tau_{A_{trn}}^{2}+c\tau_{A_{trn}}^{2}+\mu^ {2}c\right)^{2}+4c\mu^{2}\tau_{A_{trn}}^{2}}\right)+o(1/\tau^{2}_{A_{trn}})&c> 1\end{cases}$ $$

with $Var(\gamma/\theta_{trn}^{2})=o(1/(\tau^{2}_{A_{trn}})).$

###### Proof.

Recall that $\gamma=\theta_{trn}^{2}\|\hat{t}\|^{2}\|\hat{k}\|^{2}+\hat{\xi}^{2}$. The expectation of the individual terms were computed in Lemmas 11, 12, and 13.

The difference between product of the expectations and the expectation of the product can be bounded by the square root of the product of the variances. Hence in the this case, we see that the product of the expectations has an error term of $o(1/\tau^{2}_{A_{trn}})$ and the square root of the product of the variances is also $o(1/\tau^{2}_{A_{trn}})$. Hence, we see that the error in the expectation is $o(1/\tau^{2}_{A_{trn}})$.

We also need to compute the variance. The variance of the product of two dependent random variables $\mathcal{X}$ and $\mathcal{Y}$ is given by

$$ $Cov(\mathcal{X}^{2},\mathcal{Y}^{2})+\left[Var(\mathcal{X})+\mathbb{E}[ \mathcal{X}]^{2}\right]\left[Var(\mathcal{Y})+\mathbb{E}[\mathcal{Y}]^{2} \right]-\left[Cov(\mathcal{X},\mathcal{Y})+\mathbb{E}[\mathcal{X}]\mathbb{E}[ \mathcal{Y}]\right]^{2}.$ $$

Note that for both variances decay at order $o(1/\tau^{2}_{A_{trn}})$ additionally, we see that the constant order term represented by $(\mathbb{E}[\mathcal{X}]\mathbb{E}[\mathcal{Y}])^{2}$ cancels out. Hence we see that

$$ $Var(\gamma)=\theta_{trn}^{2}\left[Cov(\|\hat{t}\|^{4},\|\hat{k}\|^{4})+o(1/ \tau^{2}_{A_{trn}})\right].$ $$

Similar to before, we can compute and check that $Cov(\|\hat{t}\|^{4},\|\hat{k}\|^{4})$ is $o(1/\tau^{2}_{A_{trn}})$.
∎

###### Lemma 15 .

Under our assumptions, we have that

$$ $\mathbb{E}_{A_{trn}}\left[\hat{k}^{T}\hat{A}_{trn}^{\dagger}\hat{A}_{trn}^{{ \dagger}T}\hat{k}\right]=\begin{cases}\frac{\mu^{2}c^{2}+\mu^{2}c+(c-1)^{2} \tau_{A_{trn}}^{2}}{2\mu^{4}c\sqrt{\left(\tau_{A_{trn}}^{2}+\mu^{2}c-c\tau_{A_ {trn}}^{2}\right)^{2}+4\mu^{2}c^{2}\tau_{A_{trn}}^{2}}}+\frac{1}{2\mu^{4}} \left(1-\frac{1}{c}\right)+o(1/\tau^{2}_{A_{trn}})&c<1\\ \frac{\mu^{2}c^{2}+\mu^{2}c+(c-1)^{2}\tau_{A_{trn}}^{2}}{2\mu^{4}c\sqrt{\left( -\tau_{A_{trn}}^{2}+\mu^{2}c+c\tau_{A_{trn}}^{2}\right)^{2}+4\mu^{2}c\tau_{A_{ trn}}^{2}}}+\frac{1}{2\mu^{4}}\left(1-\frac{1}{c}\right)+o(1/\tau^{2}_{A_{trn} })&c>1\end{cases}$ $$

and that $Var(\hat{k}^{T}\hat{A}_{trn}^{\dagger}\hat{A}_{trn}^{{\dagger}T}\hat{k})=o(1/
\tau^{2}_{A_{trn}})$.

###### Proof.

(Sketch)
Using $\hat{k}=\hat{A}_{trn}^{{\dagger}}u$ and the SVD, we have

$$ $\mathbb{E}_{A_{trn}}\left[u^{T}U\hat{\Sigma}^{-4}U^{T}u\right]=\begin{cases} \mathbb{E}_{A_{trn}}\left[\frac{1}{(\lambda+\mu^{2})^{2}}\right]&c<1\\ \frac{1}{c}\mathbb{E}_{A_{trn}}\left[\frac{1}{(\lambda+\mu^{2})^{2}}\right]+ \left(1-\frac{1}{c}\right)\frac{1}{\mu^{4}}&c>1\end{cases}$ $$

where for $c>1$, $1/c$ of the eigenvalues follow the expectation and the rest equals $1/\mu^{4}$.
∎

Details of the above expectations have been discussed in Li & Sonthalia (). The following lemmas establish expectations unique to this setting.

###### Lemma 16 .

Suppose $\varepsilon\in\mathbb{R}^{n}$ whose entries have mean 0, variance $\tau_{\varepsilon}$, and follow our noise assumptions. Then for any random matrix $Q\in\mathbb{R}^{n\times n}$ independent, we have

$$ $\mathbb{E}_{\varepsilon,Q}\left[\varepsilon^{T}Q\varepsilon\right]=\tau_{ \varepsilon}^{2}\mathbb{E}\left[\operatorname{Tr}(Q)\right].$ $$

###### Proof.

We have that

$$ $\varepsilon^{T}Q\varepsilon=\sum_{i=1}^{n}\sum_{j=1}^{n}\varepsilon_{i} \varepsilon_{j}q_{ij}.$ $$

We take the expectation of this sum. By the independence assumption and assumption $\mathbb{E}[\varepsilon_{i}\varepsilon_{j}]=0\ \text{when}\ i\neq j$, we then have

$$ $\mathbb{E}_{\varepsilon,Q}\left[\varepsilon^{T}Q\varepsilon\right]=\sum_{i=1}^ {n}\mathbb{E}\left[\varepsilon_{i}^{2}\right]\mathbb{E}\left[q_{ij}\right]= \tau_{\varepsilon}^{2}\mathbb{E}\left[\sum_{i=1}^{n}q_{ij}\right]=\tau_{ \varepsilon}^{2}\mathbb{E}\left[\operatorname{Tr}(Q)\right].$ $$

∎

For the following Lemmas 17, 18, 19, 20, 21, 22 we need that variance with respect to $A_{trn}$ is bounded. We do not need it to decay. All of the expressions can be expressed as bounded functions of the non-zero eigenvalues of $A_{trn}$. Hence, due to weak convergence, they converge to some random variable on a compact measure space (the measure is the Marchenko-Pastur measure). Hence, these random variables have finite moments. Some of the variances do actually decay, but it is not too important.

###### Lemma 17 .

Under our assumptions, the following terms have zero expectation w.r.t. $A_{trn}$ and $\varepsilon_{trn}$ $\forall c\in(0,\infty)$

- (i)
$\mathbb{E}_{A_{trn}}\left[\hat{k}^{T}\hat{A}_{trn}^{\dagger}\hat{h}^{T}\right]
=0.$
- (ii)
$\mathbb{E}_{A_{trn}}\left[\hat{\varepsilon}^{T}_{trn}\hat{k}\hat{t}\hat{
\varepsilon}_{trn}\right]=0.$
- (iii)
$\mathbb{E}_{A_{trn}}\left[\hat{\varepsilon}^{T}_{trn}\hat{A}_{trm}^{\dagger}
\hat{A}^{{\dagger}T}\hat{k}\hat{t}\hat{\varepsilon}_{trn}\right]=0.$
- (iv)
$\mathbb{E}_{A_{trn}}\left[\hat{\varepsilon}^{T}_{trn}\hat{A}_{trn}^{\dagger}
\hat{h}^{T}\hat{k}\hat{\varepsilon}_{trn}\right]=0.$

###### Proof.

The heuristics for this proof will be the following: if the term contains an odd number of a uniformly random vector centered around 0 (call it $a\in\mathbb{R}^{N}$) that is independent of the rest, then by matrix multiplication, the expectation can be written as

$$ $\sum_{i=1}^{N}\mathbb{E}\left[a_{i}^{2k+1}\right]\mathbb{E}\left[\text{other terms}\right]\text{for some }k\in\mathbb{N}.$ $$

This becomes 0 since the expectation of an odd moment is 0 for a centered uniform distribution.

We use this idea to expand these 4 terms for $c<1$:

- (i)
The term $\hat{k}^{T}\hat{A}_{trn}^{\dagger}\hat{h}^{T}$ follows directly from Lemma 18 in Li & Sonthalia ().
- (ii)
$\hat{\varepsilon}^{T}_{trn}\hat{k}\hat{t}\hat{\varepsilon}_{trn}=\hat{
\varepsilon}^{T}_{trn}\hat{A}_{trn}^{\dagger}u\hat{v}_{trn}^{T}(I-\hat{A}_{trn
}^{\dagger}\hat{A}_{trn})\hat{\varepsilon}_{trn}.$
Using the SVD $\hat{A}=U\hat{\Sigma}\hat{V}^{T}$ and the fact that the last d entries of $\hat{v}_{trn}$, $\hat{\varepsilon}_{trn}$ are 0, we have
$\displaystyle\hat{\varepsilon}^{T}_{trn}\hat{V}\hat{\Sigma}^{-1}U^{T}u\hat{v}_
{trn}^{T}(I-\hat{V}\hat{V}^{T})\hat{\varepsilon}_{trn}$
$\displaystyle=$
$\displaystyle\begin{bmatrix}\varepsilon_{trn}^{T}&0_{d}^{T}\end{bmatrix}\begin
{bmatrix}V_{1:d}\Sigma\hat{\Sigma}^{-1}\\
\mu U\hat{\Sigma}^{-1}\end{bmatrix}\hat{\Sigma}^{-1}U^{T}u\begin{bmatrix}v_{
trn}^{T}&0_{d}^{T}\end{bmatrix}\left(I-\begin{bmatrix}V_{1:d}\Sigma\hat{\Sigma
}^{-1}\\
\mu U\hat{\Sigma}^{-1}\end{bmatrix}\begin{bmatrix}\hat{\Sigma}^{-1}\Sigma V_{1
:d}^{T}&\mu\hat{\Sigma}^{-1}U^{T}\end{bmatrix}\right)\begin{bmatrix}
\varepsilon_{trn}\\
0_{d}\end{bmatrix}$
$\displaystyle=$
$\displaystyle\varepsilon_{trn}^{T}V_{1:d}\Sigma\hat{\Sigma}^{-2}\underbrace{U^
{T}u}v_{trn}^{T}(I-V_{1:d}\Sigma\hat{\Sigma}^{-2}\Sigma V_{1:d}^{T})
\varepsilon_{trn}.$
We notice the vector $U^{T}u$ is uniformly random and centered by the rotational bi-invariance assumption. Hence, the expectation equals 0.
- (iii)
$\hat{\varepsilon}^{T}_{trn}\hat{A}^{\dagger}\hat{A}^{{\dagger}T}\hat{k}\hat{t}
\hat{\varepsilon}_{trn}=\hat{\varepsilon}^{T}_{trn}\hat{A}_{trn}^{\dagger}\hat
{A}_{trn}^{{\dagger}T}\hat{A}_{trn}^{\dagger}u\hat{v}_{trn}^{T}(I-\hat{A}_{trn
}^{\dagger}\hat{A}_{trn})\hat{\varepsilon}_{trn}.$
Similarly, with SVD this is just
$\displaystyle\hat{\varepsilon}^{T}_{trn}\hat{V}\hat{\Sigma}^{-2}\hat{V}^{T}
\hat{V}\hat{\Sigma}^{-1}U^{T}u\hat{v}_{trn}^{T}(I-\hat{V}\hat{V}^{T})\hat{
\varepsilon}_{trn}$
$\displaystyle=$
$\displaystyle\varepsilon_{trn}^{T}V_{1:d}\Sigma\hat{\Sigma}^{-3}\left(\hat{
\Sigma}^{-1}\Sigma^{2}\hat{\Sigma}^{-1}+\mu^{2}\hat{\Sigma}^{-2}\right)\hat{
\Sigma}^{-1}\underbrace{U^{T}u}v_{trn}^{T}(I-V_{1:d}\Sigma\hat{\Sigma}^{-2}
\Sigma V_{1:d}^{T})\varepsilon_{trn}.$
Again we use the explicit form of $\hat{V}$ and note $\hat{V}^{T}\hat{V}=\hat{\Sigma}^{-1}\Sigma^{2}\hat{\Sigma}^{-1}+\mu^{2}\hat{
\Sigma}^{-2}$.
The vector $U^{T}u$ is uniformly random, so we have zero expectation.
- (iv)
$\hat{\varepsilon}^{T}_{trn}\hat{A}^{\dagger}\hat{h}^{T}\hat{k}^{T}\hat{
\varepsilon}_{trn}=\hat{\varepsilon}^{T}_{trn}\hat{A}_{trn}^{\dagger}\hat{A}_{
trn}^{{\dagger}T}\hat{v}_{trn}u^{T}\hat{A}_{trn}^{{\dagger}T}\hat{\varepsilon}
_{trn}.$
We then have
$\displaystyle\hat{\varepsilon}^{T}_{trn}\hat{V}\hat{\Sigma}^{-2}\hat{V}^{T}
\hat{v}_{trn}u^{T}U\hat{\Sigma}^{-1}\hat{V}^{T}\hat{\varepsilon}_{trn}=
\varepsilon_{trn}^{T}V_{1:d}\Sigma\hat{\Sigma}^{-4}\Sigma V_{1:d}^{T}v_{trn}
\underbrace{u^{T}U}\hat{\Sigma}^{-1}\Sigma V_{1:d}^{T}\varepsilon_{trn}.$
The vector $u^{T}U$ is uniformly random, so we have zero expectation.

Similarly, for the $c>1$ case, we can prove it using the corresponding SVD, and the same results hold.
∎

It is important to note that Lemma 16 does not directly apply due to the zeros in $\hat{\varepsilon}$. For the following Lemmas we only need that the variance is bounded. We do not need the variance to decay.

###### Lemma 18 .

Under our assumptions, we have that

$$ $\mathbb{E}_{\varepsilon_{trn},A_{trn}}\left[\hat{\varepsilon}_{trn}^{T}\hat{k} \hat{k}^{T}\hat{\varepsilon}_{trn}\right]=\begin{cases}\tau_{\varepsilon_{trn} }^{2}\left(\frac{\tau_{A_{trn}}^{2}+c\tau_{A_{trn}}^{2}+\mu^{2}c}{2\tau_{A_{ trn}}^{2}\sqrt{\left(\tau_{A_{trn}}^{2}+\mu^{2}c-c\tau_{A_{trn}}^{2}\right)^{2 }+4\mu^{2}c^{2}\tau_{A_{trn}}^{2}}}-\frac{1}{2\tau_{A_{trn}}^{2}}\right)+o(1/ \tau^{2}_{A_{trn}})&c<1\\ \tau_{\varepsilon_{trn}}^{2}\left(\frac{\tau_{A_{trn}}^{2}+c\tau_{A_{trn}}^{2} +\mu^{2}c}{2\tau_{A_{trn}}^{2}\sqrt{\left(-\tau_{A_{trn}}^{2}+\mu^{2}c+c\tau_{ A_{trn}}^{2}\right)^{2}+4\mu^{2}c\tau_{A_{trn}}^{2}}}-\frac{1}{2\tau_{A_{trn}} ^{2}}\right)+o(1/\tau^{2}_{A_{trn}})&c>1\end{cases}.$ $$

###### Proof.

Suppose $c<1$. We expand this term using SVD and have

$$ $\displaystyle\hat{\varepsilon}_{trn}^{T}\hat{k}\hat{k}^{T}\hat{\varepsilon}_{trn}$ $\displaystyle=\hat{\varepsilon}_{trn}^{T}\hat{A}_{trn}^{\dagger}uu^{T}\hat{A}_ {trn}^{{\dagger}T}\hat{\varepsilon}_{trn}$ $\displaystyle=\hat{\varepsilon}_{trn}^{T}\begin{bmatrix}V_{1:d}\Sigma\hat{ \Sigma}^{-1}\\ \mu U\hat{\Sigma}^{-1}\end{bmatrix}\hat{\Sigma}^{-1}U^{T}uu^{T}U\hat{\Sigma}^{ -1}\begin{bmatrix}\hat{\Sigma}^{-1}\Sigma V_{1:d}^{T}&\mu\hat{\Sigma}^{-1}U^{T }\end{bmatrix}\hat{\varepsilon}_{trn}$ $\displaystyle=\varepsilon^{T}V_{1:d}\Sigma\hat{\Sigma}^{-2}U^{T}uu^{T}U\hat{ \Sigma}^{-2}\Sigma V_{1:d}^{T}\varepsilon.$ $$

We take its expectation and by Lemma 16, we have

$$ $\displaystyle\mathbb{E}_{\varepsilon_{trn},A_{trn}}\left[\hat{\varepsilon}_{ trn}^{T}\hat{k}\hat{k}^{T}\hat{\varepsilon}_{trn}\right]$ $\displaystyle=\tau_{\varepsilon_{trn}}^{2}\mathbb{E}_{A_{trn}}\left[ \operatorname{Tr}\left(V_{1:d}\Sigma\hat{\Sigma}^{-2}U^{T}uu^{T}U\hat{\Sigma}^ {-2}\Sigma V_{1:d}^{T}\right)\right]$ $\displaystyle=\tau_{\varepsilon_{trn}}^{2}\mathbb{E}_{A_{trn}}\left[u^{T}U\hat {\Sigma}^{-2}\Sigma\cancel{V_{1:d}^{T}V_{1:d}}\Sigma\hat{\Sigma}^{-2}U^{T}u\right]$ $\displaystyle=\tau_{\varepsilon_{trn}}^{2}\mathbb{E}_{A_{trn}}\left[\frac{ \lambda}{(\lambda+\mu^{2})^{2}}\right].$ $$

The rest follows from Lemma 9. For $c>1$, we use the same approach and get

$$ $\mathbb{E}_{\varepsilon_{trn},A_{trn}}\left[\hat{\varepsilon}_{trn}^{T}\hat{k} \hat{k}^{T}\hat{\varepsilon}_{trn}\right]=\frac{\tau_{\varepsilon_{trn}}^{2}}{ c}\mathbb{E}_{A_{trn}}\left[\frac{\lambda}{(\lambda+\mu^{2})^{2}}\right].$ $$

where the additional factor of $1/c$ comes from projecting $n_{trn}$ entries onto the $d$ coordinates of the randomly uniform vector.
∎

###### Lemma 19 .

Under our assumptions, we have that

$$ $\mathbb{E}_{\varepsilon_{trn},A_{trn}}\left[\hat{\varepsilon}_{trn}^{T}\hat{t} ^{T}\hat{t}\hat{\varepsilon}_{trn}\right]=\begin{cases}\tau_{\varepsilon_{trn} }^{2}\left(\frac{\mu^{2}c^{2}+\mu^{2}c+(c-1)^{2}\tau_{A_{trn}}^{2}}{2\sqrt{( \tau_{A_{trn}}^{2}+\mu^{2}c-c\tau_{A_{trn}}^{2})^{2}+4\mu^{2}c^{2}\tau_{A_{trn }}^{2}}}+\frac{1}{2}(1-c)\right)+o(1/\tau^{2}_{A_{trn}})&c<1\\ \tau_{\varepsilon_{trn}}^{2}\left(\frac{\mu^{2}c^{2}+\mu^{2}c+(c-1)^{2}\tau_{A _{trn}}^{2}}{2\sqrt{(-\tau_{A_{trn}}^{2}+\mu^{2}c+c\tau_{A_{trn}}^{2})^{2}+4 \mu^{2}c\tau_{A_{trn}}^{2}}}+\frac{1}{2}(1-c)\right)+o(1/\tau^{2}_{A_{trn}})&c >1\end{cases}.$ $$

###### Proof.

Suppose $c<1$. We expand this term using SVD and have

$$ $\displaystyle\hat{\varepsilon}_{trn}^{T}\hat{t}^{T}\hat{t}\hat{\varepsilon}_{trn}$ $\displaystyle=\hat{\varepsilon}_{trn}^{T}(I-\hat{A}_{trn}^{T}\hat{A}_{trn}^{{ \dagger}T})\hat{v}_{trn}\hat{v}_{trn}^{T}(I-\hat{A}_{trn}^{\dagger}\hat{A}_{ trn})\hat{\varepsilon}_{trn}$ $\displaystyle=\hat{\varepsilon}_{trn}^{T}(I-\hat{V}\hat{V}^{T})\hat{v}_{trn} \hat{v}_{trn}^{T}(I-\hat{V}\hat{V}^{T})\hat{\varepsilon}_{trn}$ $\displaystyle=\varepsilon_{trn}^{T}(I-V_{1:d}\Sigma\hat{\Sigma}^{-2}\Sigma V_{ 1:d}^{T})v_{trn}v_{trn}^{T}(I-V_{1:d}\Sigma\hat{\Sigma}^{-2}\Sigma V_{1:d}^{T} )\varepsilon_{trn}.$ $$

We take its expectation and by Lemma 16, we have

$$ $\displaystyle\mathbb{E}_{\begin{subarray}{c}\varepsilon_{trn},\\ A_{trn}\end{subarray}}\left[\hat{\varepsilon}_{trn}^{T}\hat{t}^{T}\hat{t}\hat{ \varepsilon}_{trn}\right]$ $\displaystyle=\tau_{\varepsilon_{trn}}^{2}\mathbb{E}_{A_{trn}}\left[ \operatorname{Tr}\left((I-V_{1:d}\Sigma\hat{\Sigma}^{-2}\Sigma V_{1:d}^{T})v_{ trn}v_{trn}^{T}(I-V_{1:d}\Sigma\hat{\Sigma}^{-2}\Sigma V_{1:d}^{T})\right)\right]$ $\displaystyle=\tau_{\varepsilon_{trn}}^{2}\mathbb{E}_{A_{trn}}\left[v_{trn}^{T }(I-V_{1:d}\Sigma\hat{\Sigma}^{-2}\Sigma V_{1:d}^{T})^{2}v_{trn}\right]$ $\displaystyle=\tau_{\varepsilon_{trn}}^{2}\mathbb{E}_{A_{trn}}\left[v_{trn}^{T }v_{trn}-2v_{trn}^{T}V_{1:d}\Sigma\hat{\Sigma}^{-2}\Sigma V_{1:d}^{T}v_{trn}\right.$ $\displaystyle\hskip 60.0pt\left.+v_{trn}^{T}V_{1:d}\Sigma\hat{\Sigma}^{-2} \Sigma^{2}\hat{\Sigma}^{-2}\Sigma V_{1:d}^{T}v_{trn}\right]$ $\displaystyle=\tau_{\varepsilon_{trn}}^{2}\left(1+c\mathbb{E}_{A_{trn}}\left[ \frac{\lambda^{2}}{(\lambda+\mu^{2})^{2}}\right]-2c\mathbb{E}_{A_{trn}}\left[ \frac{\lambda}{\lambda+\mu^{2}}\right]\right).$ $$

The factor of $c$ comes from projecting $d$ entries onto the $n_{trn}$ coordinates of the uniformly random vector.

The rest follows from Lemma 9. For $c>1$, we use the same approach and get

$$ $\mathbb{E}_{\begin{subarray}{c}\varepsilon_{trn},\\ A_{trn}\end{subarray}}\left[\hat{\varepsilon}_{trn}^{T}\hat{t}^{T}\hat{t}\hat{ \varepsilon}_{trn}\right]=\tau_{\varepsilon_{trn}}^{2}\left(1+\mathbb{E}_{A_{ trn}}\left[\frac{\lambda^{2}}{(\lambda+\mu^{2})^{2}}\right]-2\mathbb{E}_{A_{ trn}}\left[\frac{\lambda}{\lambda+\mu^{2}}\right]\right).$ $$

The variance directly follows from concentration.
∎

###### Lemma 20 .

Under our assumptions, we have that

$$ $\mathbb{E}_{\begin{subarray}{c}\varepsilon_{trn},\\ A_{trn}\end{subarray}}\left[\hat{\varepsilon}_{trn}^{T}\hat{A}_{trn}^{\dagger} \hat{A}_{trn}^{{\dagger}T}\hat{\varepsilon}_{trn}\right]=\begin{cases}\tau_{ \varepsilon_{trn}}^{2}d\left(\frac{\tau_{A_{trn}}^{2}+c\tau_{A_{trn}}^{2}+\mu^ {2}c}{2\tau_{A_{trn}}^{2}\sqrt{(\tau_{A_{trn}}^{2}+\mu^{2}c-c\tau_{A_{trn}}^{2 })^{2}+4\mu^{2}c^{2}\tau_{A_{trn}}^{2}}}-\frac{1}{2\tau_{A_{trn}}^{2}}\right)+ o(1/\tau^{2}_{A_{trn}})&c<1\\ \tau_{\varepsilon_{trn}}^{2}d\left(\frac{\tau_{A_{trn}}^{2}+c\tau_{A_{trn}}^{2 }+\mu^{2}c}{2\tau_{A_{trn}}^{2}\sqrt{(-\tau_{A_{trn}}^{2}+\mu^{2}c+c\tau_{A_{ trn}}^{2})^{2}+4\mu^{2}c\tau_{A_{trn}}^{2}}}-\frac{1}{2\tau_{A_{trn}}^{2}} \right)+o(1/\tau^{2}_{A_{trn}})&c>1\end{cases}.$ $$

###### Proof.

Suppose $c<1$. We expand this term using SVD and have

$$ $\hat{\varepsilon}_{trn}^{T}\hat{A}_{trn}^{\dagger}\hat{A}_{trn}^{{\dagger}T} \hat{\varepsilon}_{trn}=\hat{\varepsilon}_{trn}^{T}\hat{V}\hat{\Sigma}^{-2} \hat{V}^{T}\hat{\varepsilon}_{trn}=\varepsilon_{trn}^{T}V_{1:d}\Sigma\hat{ \Sigma}^{-4}\Sigma V_{1:d}^{T}\varepsilon_{trn}.$ $$

Again taking the expectation, we have

$$ $\displaystyle\mathbb{E}_{\varepsilon_{trn},A_{trn}}\left[\hat{\varepsilon}_{ trn}^{T}\hat{A}_{trn}^{\dagger}\hat{A}_{trn}^{{\dagger}T}\hat{\varepsilon}_{ trn}\right]$ $\displaystyle=\tau_{\varepsilon_{trn}}^{2}\mathbb{E}_{A_{trn}}\left[ \operatorname{Tr}\left(V_{1:d}\Sigma\hat{\Sigma}^{-4}\Sigma V_{1:d}^{T}\right)\right]$ $\displaystyle=\tau_{\varepsilon_{trn}}^{2}\mathbb{E}_{A_{trn}}\left[ \operatorname{Tr}\left(\Sigma\hat{\Sigma}^{-4}\Sigma\right)\right]$ $\displaystyle=\tau_{\varepsilon_{trn}}^{2}d\mathbb{E}_{A_{trn}}\left[\frac{ \lambda}{(\lambda+\mu^{2})^{2}}\right].$ $$

where the factor of $d$ comes from summing up the $d$ diagonal elements.

The rest follows from Lemma 9. For $c>1$, we use the same approach and get

$$ $\mathbb{E}_{\varepsilon_{trn},A_{trn}}\left[\hat{\varepsilon}_{trn}^{T}\hat{A} _{trn}^{\dagger}\hat{A}_{trn}^{{\dagger}T}\hat{\varepsilon}_{trn}\right]=\tau_ {\varepsilon_{trn}}^{2}N_{trn}\mathbb{E}_{A_{trn}}\left[\frac{\lambda}{( \lambda+\mu^{2})^{2}}\right]=\tau_{\varepsilon_{trn}}^{2}\frac{M}{c}\mathbb{E} _{A_{trn}}\left[\frac{\lambda}{(\lambda+\mu^{2})^{2}}\right].$ $$

∎

###### Lemma 21 .

Under our assumptions, we have that

$$ $\mathbb{E}_{\varepsilon_{trn},A_{trn}}\left[\hat{\varepsilon}_{trn}^{T}\hat{A} _{trn}^{\dagger}\hat{h}^{T}\hat{t}\hat{\varepsilon}_{trn}\right]=\begin{cases} \frac{\tau_{\varepsilon_{trn}}^{2}c^{3}\mu^{2}\tau_{A_{trn}}^{2}}{\left((\tau_ {A_{trn}}^{2}+\mu^{2}c-c\tau_{A_{trn}}^{2})^{2}+4\mu^{2}c^{2}\tau_{A_{trn}}^{2 }\right)^{3/2}}+o(1/\tau^{2}_{A_{trn}})&c<1\\ \frac{\tau_{\varepsilon_{trn}}^{2}c^{3}\mu^{2}\tau_{A_{trn}}^{2}}{\left((-\tau _{A_{trn}}^{2}+\mu^{2}c+c\tau_{A_{trn}}^{2})^{2}+4\mu^{2}c\tau_{A_{trn}}^{2} \right)^{3/2}}+o(1/\tau^{2}_{A_{trn}})&c>1\end{cases}.$ $$

###### Proof.

Suppose $c<1$. We expand this term using SVD and have

$$ $\displaystyle\hat{\varepsilon}_{trn}^{T}\hat{A}_{trn}^{\dagger}\hat{h}^{T}\hat {t}\hat{\varepsilon}_{trn}$ $\displaystyle=\hat{\varepsilon}_{trn}^{T}\hat{A}_{trn}^{\dagger}\hat{A}_{trn}^ {{\dagger}T}\hat{v}_{trn}\hat{v}_{trn}^{T}(I-\hat{A}_{trn}^{\dagger}\hat{A}_{ trn})\hat{\varepsilon}_{trn}$ $\displaystyle=\hat{\varepsilon}_{trn}^{T}\hat{V}\hat{\Sigma}^{-2}\hat{V}^{T} \hat{v}_{trn}\hat{v}_{trn}^{T}(I-\hat{V}\hat{V}^{T})\hat{\varepsilon}_{trn}$ $\displaystyle=\varepsilon_{trn}^{T}V_{1:d}\Sigma\hat{\Sigma}^{-4}\Sigma V_{1:d }^{T}v_{trn}v_{trn}^{T}(I-V_{1:d}\Sigma\hat{\Sigma}^{-2}\Sigma V_{1:d}^{T}) \varepsilon_{trn}.$ $$

We take its expectation and by Lemma 16, we have

$$ $\displaystyle\mathbb{E}_{\begin{subarray}{c}\varepsilon_{trn},\\ A_{trn}\end{subarray}}\left[\hat{\varepsilon}_{trn}^{T}\hat{A}_{trn}^{\dagger} \hat{h}^{T}\hat{t}\hat{\varepsilon}_{trn}\right]$ $\displaystyle=\tau_{\varepsilon_{trn}}^{2}\mathbb{E}_{A_{trn}}\left[ \operatorname{Tr}\left(v_{trn}^{T}(I-V_{1:d}\Sigma\hat{\Sigma}^{-2}\Sigma V_{1 :d}^{T})V_{1:d}\Sigma\hat{\Sigma}^{-4}\Sigma V_{1:d}^{T}v_{trn}\right)\right]$ $\displaystyle=\tau_{\varepsilon_{trn}}^{2}\mathbb{E}_{A_{trn}}\left[v_{trn}^{T }V_{1:d}\Sigma\hat{\Sigma}^{-4}\Sigma V_{1:d}^{T}v_{trn}-v_{trn}^{T}V_{1:d} \Sigma\hat{\Sigma}^{-2}\Sigma^{2}\hat{\Sigma}^{-4}\Sigma V_{1:d}^{T}v_{trn}\right]$ $\displaystyle=\tau_{\varepsilon_{trn}}^{2}\left(c\mathbb{E}_{A_{trn}}\left[ \frac{\lambda}{(\lambda+\mu^{2})^{2}}\right]-c\mathbb{E}_{A_{trn}}\left[\frac{ \lambda^{2}}{(\lambda+\mu^{2})^{3}}\right]\right)$ $\displaystyle=\tau_{\varepsilon_{trn}}^{2}\left(c\mu^{2}\mathbb{E}_{A_{trn}} \left[\frac{1}{(\lambda+\mu^{2})^{2}}\right]-c\mu^{4}\mathbb{E}_{A_{trn}}\left [\frac{1}{(\lambda+\mu^{2})^{3}}\right]\right).$ $$

The factor of $c$ comes from projecting $d$ entries onto the $n_{trn}$ coordinates of the uniformly random vector.
The rest follows from Lemma 7. For $c>1$, we use the same approach and get

$$ $\mathbb{E}_{\begin{subarray}{c}\varepsilon_{trn},\\ A_{trn}\end{subarray}}\left[\hat{\varepsilon}_{trn}^{T}\hat{A}_{trn}^{\dagger} \hat{h}^{T}\hat{t}\hat{\varepsilon}_{trn}\right]=\tau_{\varepsilon_{trn}}^{2} \left(\mu^{2}\mathbb{E}_{A_{trn}}\left[\frac{1}{(\lambda+\mu^{2})^{2}}\right]- \mu^{4}\mathbb{E}_{A_{trn}}\left[\frac{1}{(\lambda+\mu^{2})^{3}}\right]\right).$ $$

∎

###### Lemma 22 .

Under our assumptions, we have that

$$ $\mathbb{E}_{\varepsilon_{trn},A_{trn}}\left[\hat{\varepsilon}_{trn}^{T}\hat{A} _{trn}^{\dagger}\hat{A}_{trn}^{{\dagger}T}\hat{k}\hat{k}^{T}\hat{\varepsilon}_ {trn}\right]=\begin{cases}\frac{\tau_{\varepsilon_{trn}}^{2}c^{2}\tau_{A_{trn} }^{2}}{\left((\tau_{A_{trn}}^{2}+\mu^{2}c-c\tau_{A_{trn}}^{2})^{2}+4\mu^{2}c^{ 2}\tau_{A_{trn}}^{2}\right)^{3/2}}+o(1)&c<1\\ \frac{\tau_{\varepsilon_{trn}}^{2}c^{2}\tau_{A_{trn}}^{2}}{\left((-\tau_{A_{ trn}}^{2}+\mu^{2}c+c\tau_{A_{trn}}^{2})^{2}+4\mu^{2}c\tau_{A_{trn}}^{2}\right) ^{3/2}}+o(1)&c>1\end{cases}$ $$

and that $Var(\hat{\varepsilon}_{trn}^{T}\hat{A}_{trn}^{\dagger}\hat{A}_{trn}^{{\dagger}
T}\hat{k}\hat{k}^{T}\hat{\varepsilon}_{trn})=o(1)$.

###### Proof.

Suppose $c<1$. We expand this term using SVD and have

$$ $\displaystyle\hat{\varepsilon}_{trn}^{T}\hat{A}_{trn}^{\dagger}\hat{A}_{trn}^{ {\dagger}T}\hat{k}\hat{k}^{T}\hat{\varepsilon}_{trn}$ $\displaystyle=\hat{\varepsilon}_{trn}^{T}\hat{A}_{trn}^{\dagger}\hat{A}_{trn}^ {{\dagger}T}\hat{A}_{trn}^{\dagger}uu^{T}\hat{A}_{trn}^{{\dagger}T}\hat{ \varepsilon}_{trn}$ $\displaystyle=\hat{\varepsilon}_{trn}^{T}\hat{V}\hat{\Sigma}^{-2}\hat{V}^{T} \hat{V}\hat{\Sigma}^{-1}U^{T}uu^{T}U\hat{\Sigma}^{-1}\hat{V}^{T}\hat{ \varepsilon}_{trn}$ $\displaystyle=\varepsilon_{trn}^{T}V_{1:d}\Sigma\hat{\Sigma}^{-3}\left(\hat{ \Sigma}^{-1}\Sigma^{2}\hat{\Sigma}^{-1}+\mu^{2}\hat{\Sigma}^{-2}\right)\hat{ \Sigma}^{-1}U^{T}uu^{T}U\hat{\Sigma}^{-2}\Sigma V_{1:d}^{T}\varepsilon_{trn}.$ $$

We take its expectation and by Lemma 16, we have

$$ $\displaystyle\mathbb{E}_{\begin{subarray}{c}\varepsilon_{trn},\\ A_{trn}\end{subarray}}\left[\hat{\varepsilon}_{trn}^{T}\hat{A}_{trn}^{\dagger} \hat{A}_{trn}^{{\dagger}T}\hat{k}\hat{k}^{T}\hat{\varepsilon}_{trn}\right]$ $\displaystyle=\tau_{\varepsilon_{trn}}^{2}\mathbb{E}_{A_{trn}}\left[u^{T}U\hat {\Sigma}^{-2}\Sigma\cancel{V_{1:d}^{T}V_{1:d}}\Sigma\hat{\Sigma}^{-3}\left( \hat{\Sigma}^{-1}\Sigma^{2}\hat{\Sigma}^{-1}+\mu^{2}\hat{\Sigma}^{-2}\right) \hat{\Sigma}^{-1}U^{T}u\right]$ $\displaystyle=\tau_{\varepsilon_{trn}}^{2}\mathbb{E}_{A_{trn}}\left[u^{T}U\hat {\Sigma}^{-2}\Sigma^{2}\hat{\Sigma}^{-4}\Sigma^{2}\hat{\Sigma}^{-2}U^{T}u-\mu^ {2}u^{T}U\hat{\Sigma}^{-2}\Sigma^{2}\hat{\Sigma}^{-6}U^{T}u\right]$ $\displaystyle=\tau_{\varepsilon_{trn}}^{2}\left(\mathbb{E}_{A_{trn}}\left[ \frac{\lambda^{2}}{(\lambda+\mu^{2})^{4}}\right]-\mathbb{E}_{A_{trn}}\left[\mu ^{2}\frac{\lambda}{(\lambda+\mu^{2})^{4}}\right]\right)$ $\displaystyle=\tau_{\varepsilon_{trn}}^{2}\left(\mathbb{E}_{A_{trn}}\left[ \frac{\lambda}{(\lambda+\mu^{2})^{3}}\right]\right)$ $\displaystyle=\tau_{\varepsilon_{trn}}^{2}\left(\mathbb{E}_{A_{trn}}\left[ \frac{1}{(\lambda+\mu^{2})^{2}}\right]-\mu^{2}\mathbb{E}_{A_{trn}}\left[\frac{ 1}{(\lambda+\mu^{2})^{3}}\right]\right).$ $$

The rest follows from Lemma 7. For $c>1$, we use the same approach and get

$$ $\mathbb{E}_{\begin{subarray}{c}\varepsilon_{trn},\\ A_{trn}\end{subarray}}\left[\hat{\varepsilon}_{trn}^{T}\hat{A}_{trn}^{\dagger} \hat{h}^{T}\hat{t}\hat{\varepsilon}_{trn}\right]=\tau_{\varepsilon_{trn}}^{2} \left(\frac{1}{c}\mathbb{E}_{A_{trn}}\left[\frac{1}{(\lambda+\mu^{2})^{2}} \right]-\frac{\mu^{2}}{c}\mathbb{E}_{A_{trn}}\left[\frac{1}{(\lambda+\mu^{2})^ {3}}\right]\right).$ $$

∎

These are all the expectations we need for the final derivation of the error formula. We present the full results here, but readers might have noticed a substantial similarity in each pair of cases: the two formulas only differ in the radical. This observation will allow us to present the final formula in a more concise way.

###### Lemma 10 .

###### Proof.

###### Lemma 11 .

###### Proof.

###### Lemma 12 .

###### Proof.

###### Lemma 13 .

###### Proof.

###### Lemma 14 .

###### Proof.

###### Lemma 15 .

###### Proof.

###### Lemma 16 .

###### Proof.

###### Lemma 17 .

###### Proof.

###### Lemma 18 .

###### Proof.

###### Lemma 19 .

###### Proof.

###### Lemma 20 .

###### Proof.

###### Lemma 21 .

###### Proof.

###### Lemma 22 .

###### Proof.

### A.5 Step 5: Put things together

###### Proposition 1 .

Under our assumptions, we have that for the bias term, if $c<1$,

$$ $\mathbb{E}_{\varepsilon_{trn},A_{trn}}\left\|\beta_{*}^{T}Z_{tst}-\beta_{so}^{ T}Z_{tst}\right\|_{F}^{2}=\frac{\theta_{tst}^{2}}{\gamma^{2}}\left[(\beta_{*}^ {T}u)^{2}+\frac{\tau_{\varepsilon_{trn}}^{2}}{2\tau_{A_{trn}}^{4}}\left(\theta _{trn}^{2}c+\tau_{A_{trn}}^{2}\right)\left(T_{2}-1\right)\right]+o\left(\frac{ \theta_{tst}^{2}}{\theta_{trn}^{2}}\right)$ $$

where

$$ $T_{1}=\sqrt{\left(\tau_{A_{trn}}^{2}+\mu^{2}c-c\tau_{A_{trn}}^{2}\right)^{2}+4 \mu^{2}c^{2}\tau_{A_{trn}}^{2}},\text{ }T_{2}=\frac{\mu^{2}c+\tau_{A_{trn}}^{2 }+c\tau_{A_{trn}}^{2}}{T_{1}},$ $$

$$ $\text{and }\gamma=1+\frac{\theta_{trn}^{2}}{2\tau_{A_{trn}}^{4}}\left(\tau_{A_ {trn}}^{2}+c\tau_{A_{trn}}^{2}+\mu^{2}c-T_{1}\right).$ $$

For $c>1$, the same formula holds except

$$ $T_{1}=\sqrt{\left(-\tau_{A_{trn}}^{2}+\mu^{2}c+c\tau_{A_{trn}}^{2}\right)^{2}+ 4\mu^{2}c\tau_{A_{trn}}^{2}}.$ $$

###### Proof.

By Lemma 3, we can rewrite the bias term as

$$ $\displaystyle\left\|\beta_{*}^{T}Z_{tst}-\beta_{so}^{T}Z_{tst}\right\|_{F}^{2}$ $\displaystyle=\left\|\frac{\hat{\xi}}{\gamma}\beta_{*}^{T}Z_{tst}+\frac{\theta _{tst}\hat{\xi}}{\theta_{trn}\gamma}\hat{\varepsilon}_{trn}^{T}\hat{p}v_{tst}^ {T}\right\|_{F}^{2}$ $\displaystyle=\left\|\frac{\hat{\xi}}{\gamma}\beta_{*}^{T}Z_{tst}\right\|_{F}^ {2}+\left\|\frac{\theta_{tst}\hat{\xi}}{\theta_{trn}\gamma}\hat{\varepsilon}_{ trn}^{T}\hat{p}v_{tst}^{T}\right\|_{F}^{2}+2\operatorname{Tr}\left(\frac{ \theta_{tst}\hat{\xi}^{2}}{\theta_{trn}\gamma^{2}}Z_{tst}^{T}W\hat{\varepsilon }_{trn}^{T}\hat{p}v_{tst}^{T}\right).$ $$

Note the last term is zero in expectation since $\hat{\varepsilon}_{trn}$ has mean 0 entries. We go ahead and expand the other two terms.

Using $Z_{tst}=\theta_{tst}uv_{tst}^{T}$, we first have

$$ $\left\|\frac{\hat{\xi}}{\gamma}\beta_{*}^{T}Z_{tst}\right\|_{F}^{2}=\frac{ \theta_{tst}^{2}\hat{\xi}^{2}}{\gamma^{2}}\beta_{*}^{T}uv_{tst}^{T}v_{tst}u^{T }\beta_{*}=\frac{\theta_{tst}^{2}\hat{\xi}^{2}}{\gamma^{2}}(\beta_{*}^{T}u)^{2}$ $$

since $v_{tst}^{T}v_{tst}=\|v_{tst}\|^{2}=1$.
We also have

$$ $\left\|\frac{\theta_{tst}\hat{\xi}}{\theta_{trn}\gamma}\hat{\varepsilon}_{trn} ^{T}\hat{p}v_{tst}^{T}\right\|_{F}^{2}=\frac{\theta_{tst}^{2}\hat{\xi}^{2}}{ \theta_{trn}^{2}\gamma^{2}}\operatorname{Tr}\left(\hat{\varepsilon}_{trn}^{T} \hat{p}v_{tst}^{T}v_{tst}\hat{p}^{T}\hat{\varepsilon}_{trn}\right)=\frac{ \theta_{tst}^{2}\hat{\xi}^{2}}{\theta_{trn}^{2}\gamma^{2}}\hat{\varepsilon}_{ trn}^{T}\hat{p}\hat{p}^{T}\hat{\varepsilon}_{trn}.$ $$

We plug in $\hat{p}=-\frac{\theta_{trn}^{2}\|\hat{k}\|^{2}}{\hat{\xi}}\hat{t}^{T}-\theta_{
trn}\hat{k}$ and expand. We get

$$ $\frac{\theta_{tst}^{2}\hat{\xi}^{2}}{\theta_{trn}^{2}\gamma^{2}}\left(\frac{ \theta_{trn}^{4}\|\hat{k}\|^{4}}{\hat{\xi}^{2}}\hat{\varepsilon}_{trn}^{T}\hat {t}^{T}\hat{t}\hat{\varepsilon}_{trn}+\frac{2\theta_{trn}^{3}\|\hat{k}\|^{2}}{ \hat{\xi}}\underbrace{\hat{\varepsilon}_{trn}^{T}\hat{k}\hat{t}\hat{ \varepsilon}_{trn}}_{0}+\theta_{trn}^{2}\hat{\varepsilon}_{trn}^{T}\hat{k}\hat {k}^{T}\hat{\varepsilon}_{trn}\right).$ $$

Since the term has mean zero and $\theta_{trn}$ is a constant it doesn’t effect the mean. Hence can divide and multiply by $\theta_{trn}^{2}$ so that we get a factor of $\theta_{trn}^{2}/\gamma^{2}$ which then has the appropriate variance. Hence, the second term equals 0 + $o(1)$ in expectation. We then have that w.r.t. $A_{trn}$ and $\varepsilon_{trn}$,

$$ $\mathbb{E}\left\|\beta_{*}^{T}Z_{tst}-\beta_{so}^{T}Z_{tst}\right\|_{F}^{2}= \theta_{tst}^{2}(\beta_{*}^{T}u)^{2}\mathbb{E}\left[\frac{\hat{\xi}^{2}}{ \gamma^{2}}\right]+\theta_{tst}^{2}\theta_{trn}^{2}\mathbb{E}\left[\frac{\| \hat{k}\|^{4}}{\gamma^{2}}\hat{\varepsilon}_{trn}^{T}\hat{t}^{T}\hat{t}\hat{ \varepsilon}_{trn}\right]+\theta_{tst}^{2}\mathbb{E}\left[\frac{1}{\gamma^{2}} \hat{\varepsilon}_{trn}^{T}\hat{k}\hat{k}^{T}\hat{\varepsilon}_{trn}\right].$ $$

By concentration and Lemmas 11, 13, 14, 18, 19, we use SymPy to directly multiply individual expectations and get the results.
∎

###### Proposition 2 .

Under our assumptions, with $\tilde{\beta}^{T}=\hat{Z}_{trn}(\hat{Z}_{trn}+\hat{A}_{trn})^{\dagger}$, we have that if $c<1$,

$$ $\mathbb{E}_{A_{trn}}\left[(\beta_{*}^{T}u)^{2}\|\tilde{\beta}\|^{2}\right]= \frac{\theta_{trn}^{2}}{\gamma^{2}}(\beta_{*}^{T}u)^{2}\left[\frac{c\left( \theta_{trn}^{2}+\tau_{A_{trn}}^{2}\right)}{2\tau_{A_{trn}}^{4}}\left(T_{2}-1 \right)\right]+o(1),$ $$

where

$$ $T_{1}=\sqrt{\left(\tau_{A_{trn}}^{2}+\mu^{2}c-c\tau_{A_{trn}}^{2}\right)^{2}+4 \mu^{2}c^{2}\tau_{A_{trn}}^{2}},\text{ }T_{2}=\frac{\mu^{2}c+\tau_{A_{trn}}^{2 }+c\tau_{A_{trn}}^{2}}{T_{1}},$ $$

$$ $\text{and }\gamma=1+\frac{\theta_{trn}^{2}}{2\tau_{A_{trn}}^{4}}\left(\tau_{A_ {trn}}^{2}+c\tau_{A_{trn}}^{2}+\mu^{2}c-T_{1}\right).$ $$

For $c>1$, the same formula holds except

$$ $T_{1}=\sqrt{\left(-\tau_{A_{trn}}^{2}+\mu^{2}c+c\tau_{A_{trn}}^{2}\right)^{2}+ 4\mu^{2}c\tau_{A_{trn}}^{2}}.$ $$

Proof. Li & Sonthalia () studies the ridge-regularized denoising setting. By its Lemma 4, with our notations,

$$ $\|\tilde{W}_{opt}\|^{2}=\frac{\theta_{trn}^{2}\hat{\xi}^{2}}{\gamma^{2}}\|\hat {h}\|^{2}+2\frac{\theta_{trn}^{3}\|\hat{t}\|^{2}\hat{\xi}}{\gamma^{2}}\hat{k}^ {T}\hat{A}_{trn}^{\dagger}\hat{h}^{T}+\frac{\theta_{trn}^{4}\|\hat{t}\|^{4}}{ \gamma^{2}}\hat{k}^{T}\hat{A}_{trn}^{\dagger}\hat{A}_{trn}^{{\dagger}T}\hat{k}.$ $$

The rest follows from concentration and our Lemmas 10, 12, 13, 14, 15, 17.

###### Proposition 3 .

Under our assumptions, we have that if $c<1$,

$$ $\displaystyle\mathbb{E}_{\varepsilon_{trn},A_{trn}}\left[\hat{\varepsilon}_{ trn}^{T}(\hat{Z}_{trn}+\hat{A}_{trn})^{\dagger}(\hat{Z}_{trn}+\hat{A}_{trn})^{ {\dagger}T}\hat{\varepsilon}_{trn}\right]$ $\displaystyle=\ \$ $\displaystyle\frac{\tau_{\varepsilon_{trn}}^{2}}{2\tau_{A_{trn}}^{2}}\left[d+ \frac{c\theta_{trn}^{2}}{\tau_{A_{trn}}^{2}}\frac{T_{2}}{\gamma^{2}}\left( \frac{(c+1)\theta_{trn}^{2}}{\tau_{A_{trn}}^{2}}+1\right)\right](T_{2}-1)$ $\displaystyle-\frac{c^{2}(c+1)\theta_{trn}^{4}\tau_{\varepsilon_{trn}}^{2}}{ \tau_{A_{trn}}^{2}}\frac{1}{\gamma^{2}T_{1}^{2}}-\frac{2\theta_{trn}^{2}c^{2} \tau_{\varepsilon_{trn}}^{2}}{\gamma}\left(\frac{1}{T_{1}^{2}}-\frac{c\mu^{2}} {T_{1}^{3}}\right),$ $$

where

$$ $T_{1}=\sqrt{\left(\tau_{A_{trn}}^{2}+\mu^{2}c-c\tau_{A_{trn}}^{2}\right)^{2}+4 \mu^{2}c^{2}\tau_{A_{trn}}^{2}},\text{ }T_{2}=\frac{\mu^{2}c+\tau_{A_{trn}}^{2 }+c\tau_{A_{trn}}^{2}}{T_{1}},$ $$

$$ $\text{and }\gamma=1+\frac{\theta_{trn}^{2}}{2\tau_{A_{trn}}^{4}}\left(\tau_{A_ {trn}}^{2}+c\tau_{A_{trn}}^{2}+\mu^{2}c-T_{1}\right).$ $$

For $c>1$, the same formula holds except

$$ $T_{1}=\sqrt{\left(-\tau_{A_{trn}}^{2}+\mu^{2}c+c\tau_{A_{trn}}^{2}\right)^{2}+ 4\mu^{2}c\tau_{A_{trn}}^{2}}.$ $$

Remark: This term corresponds to the part of variance further induced by $\varepsilon_{trn}$.

###### Proof.

We first expand this term and cross out individual terms with zero expectation, denoting them accordingly.

$$ $\displaystyle\hat{\varepsilon}_{trn}^{T}(\hat{Z}_{trn}+\hat{A}_{trn})^{\dagger }(\hat{Z}_{trn}+\hat{A}_{trn})^{{\dagger}T}\hat{\varepsilon}_{trn}$ $\displaystyle=\$ $\displaystyle\hat{\varepsilon}_{trn}^{T}\left(\hat{A}_{trn}^{\dagger}+\frac{ \theta_{trn}}{\hat{\xi}}\hat{t}^{T}\hat{k}^{T}\hat{A}_{trn}^{\dagger}-\frac{ \hat{\xi}}{\gamma}\hat{p}\hat{q}^{T}\right)\left(\hat{A}_{trn}^{\dagger}+\frac {\theta_{trn}}{\hat{\xi}}\hat{t}^{T}\hat{k}^{T}\hat{A}_{trn}^{\dagger}-\frac{ \hat{\xi}}{\gamma}\hat{p}\hat{q}^{T}\right)^{T}\hat{\varepsilon}_{trn}$ $\displaystyle=\$ $\displaystyle\hat{\varepsilon}_{trn}^{T}\hat{A}_{trn}^{\dagger}\hat{A}_{trn}^{ {\dagger}T}\hat{\varepsilon}_{trn}+\frac{2\theta_{trn}}{\hat{\xi}}\underbrace{ \hat{\varepsilon}_{trn}^{T}\hat{A}_{trn}^{\dagger}\hat{A}_{trn}^{{\dagger}T} \hat{k}\hat{t}\hat{\varepsilon}_{trn}}_{0}-\frac{2\hat{\xi}}{\gamma}\hat{ \varepsilon}_{trn}^{T}\hat{A}_{trn}^{\dagger}\hat{q}\hat{p}^{T}\hat{ \varepsilon}_{trn}$ $\displaystyle+\frac{\theta_{trn}^{2}}{\hat{\xi}^{2}}\left(\hat{k}^{T}\hat{A}_{ trn}^{{\dagger}}\hat{A}_{trn}^{{\dagger}T}\hat{k}\right)\hat{\varepsilon}_{trn }^{T}\hat{t}^{T}\hat{t}\hat{\varepsilon}_{trn}-\frac{2\theta_{trn}}{\gamma} \hat{\varepsilon}_{trn}^{T}\hat{t}^{T}\hat{k}^{T}\hat{A}_{trn}^{\dagger}\hat{q }\hat{p}^{T}\hat{\varepsilon}_{trn}+\frac{\hat{\xi}^{2}}{\gamma^{2}}\hat{ \varepsilon}_{trn}^{T}\hat{p}\hat{q}^{T}\hat{q}\hat{p}^{T}\hat{\varepsilon}_{trn}$ $$

We know the expectation of the first term from Lemma. Here the second term equals 0 in expectation by Lemma 17. We expand the other terms one by one, marking those with zero expectations:

$$ $\displaystyle-\frac{2\hat{\xi}}{\gamma}\hat{\varepsilon}_{trn}^{T}\hat{A}_{trn }^{\dagger}\hat{q}\hat{p}^{T}\hat{\varepsilon}_{trn}$ $\displaystyle=-\frac{2\hat{\xi}}{\gamma}\hat{\varepsilon}_{trn}^{T}\hat{A}_{ trn}^{\dagger}\left(-\frac{\theta_{trn}\|\hat{t}\|^{2}}{\hat{\xi}}\hat{A}_{trn }^{{\dagger}T}\hat{k}-\hat{h}^{T}\right)\left(-\frac{\theta_{trn}^{2}\|\hat{k} \|^{2}}{\hat{\xi}}\hat{t}-\theta_{trn}\hat{k}^{T}\right)\hat{\varepsilon}_{trn}$ $\displaystyle=-\frac{2\theta_{trn}^{3}\|\hat{t}\|^{2}\|\hat{k}\|^{2}}{\gamma \hat{\xi}}\underbrace{\hat{\varepsilon}_{trn}^{T}\hat{A}_{trn}^{\dagger}\hat{A }_{trn}^{{\dagger}T}\hat{k}\hat{t}\hat{\varepsilon}_{trn}}_{0}-\frac{2\theta_{ trn}^{2}\|\hat{t}\|^{2}}{\gamma}\hat{\varepsilon}_{trn}^{T}\hat{A}_{trn}^{ \dagger}\hat{A}_{trn}^{{\dagger}T}\hat{k}\hat{k}^{T}\hat{\varepsilon}_{trn}$ $\displaystyle\ \ \ \ \ -\frac{2\theta_{trn}^{2}\|\hat{k}\|^{2}}{\gamma}\hat{ \varepsilon}_{trn}^{T}\hat{A}_{trn}^{\dagger}\hat{h}^{T}\hat{t}\hat{ \varepsilon}_{trn}-\frac{2\theta_{trn}}{\gamma}\underbrace{\hat{\varepsilon}_{ trn}^{T}\hat{A}_{trn}^{\dagger}\hat{h}^{T}\hat{k}^{T}\hat{\varepsilon}_{trn}}_ {0}.$ $$

$$ $\displaystyle-\frac{2\theta_{trn}}{\gamma}\hat{\varepsilon}_{trn}^{T}\hat{t}^{ T}\hat{k}^{T}\hat{A}_{trn}^{\dagger}\hat{q}\hat{p}^{T}\hat{\varepsilon}_{trn}$ $\displaystyle=-\frac{2\theta_{trn}}{\gamma}\hat{\varepsilon}_{trn}^{T}\hat{t}^ {T}\hat{k}^{T}\hat{A}_{trn}^{\dagger}\left(-\frac{\theta_{trn}\|\hat{t}\|^{2}} {\hat{\xi}}\hat{A}_{trn}^{{\dagger}T}\hat{k}-\hat{h}^{T}\right)\left(-\frac{ \theta_{trn}^{2}\|\hat{k}\|^{2}}{\hat{\xi}}\hat{t}-\theta_{trn}\hat{k}^{T} \right)\hat{\varepsilon}_{trn}$ $\displaystyle=-\frac{2\theta_{trn}^{4}\|\hat{t}\|^{2}\|\hat{k}\|^{2}}{\gamma \hat{\xi}^{2}}\left(\hat{k}^{T}\hat{A}_{trn}^{{\dagger}}\hat{A}_{trn}^{{ \dagger}T}\hat{k}\right)\hat{\varepsilon}_{trn}^{T}\hat{t}^{T}\hat{t}\hat{ \varepsilon}_{trn}$ $\displaystyle\ \ \ \ \ -\frac{2\theta_{trn}^{3}\|\hat{t}\|^{2}}{\gamma\hat{\xi }}\left(\hat{k}^{T}\hat{A}_{trn}^{{\dagger}}\hat{A}_{trn}^{{\dagger}T}\hat{k} \right)\underbrace{\hat{\varepsilon}_{trn}^{T}\hat{t}^{T}\hat{k}^{T}\hat{ \varepsilon}_{trn}}_{0}$ $\displaystyle\ \ \ \ \ -\frac{2\theta_{trn}^{3}\|\hat{k}\|^{2}}{\gamma\hat{\xi }}\hat{\varepsilon}_{trn}^{T}\hat{t}^{T}\underbrace{\hat{k}^{T}\hat{A}_{trn}^{ \dagger}\hat{h}^{T}}_{0}\hat{t}\hat{\varepsilon}_{trn}-\frac{2\theta_{trn}^{2} }{\gamma}\hat{\varepsilon}_{trn}^{T}\hat{t}^{T}\underbrace{\hat{k}^{T}\hat{A}_ {trn}^{\dagger}\hat{h}^{T}}_{0}\hat{k}^{T}\hat{\varepsilon}_{trn}.$ $$

We further denote

$$ $Q=\hat{p}\hat{q}^{T}=\frac{\theta_{trn}^{3}\|\hat{k}\|^{2}\|\hat{t}\|^{2}}{ \hat{\xi}^{2}}\hat{t}^{T}\hat{k}^{T}\hat{A}_{trn}^{\dagger}+\frac{\theta_{trn} ^{2}\|\hat{k}\|^{2}}{\hat{\xi}}\hat{t}^{T}\hat{h}+\frac{\theta_{trn}^{2}\|\hat {t}\|^{2}}{\hat{\xi}}\hat{k}\hat{k}^{T}\hat{A}_{trn}^{\dagger}+\theta_{trn} \hat{k}\hat{h}$ (A.7) $$

Then using this result, we expand the last term

$$ $\displaystyle\frac{\hat{\xi}^{2}}{\gamma^{2}}\hat{\varepsilon}_{trn}^{T}\hat{p }\hat{q}^{T}\hat{q}\hat{p}^{T}\hat{\varepsilon}_{trn}$ $\displaystyle=\frac{\hat{\xi}^{2}}{\gamma^{2}}\hat{\varepsilon}_{trn}^{T}QQ^{T }\hat{\varepsilon}_{trn}$ $\displaystyle=\frac{\theta_{trn}^{6}\|\hat{t}\|^{4}\|\hat{k}\|^{4}}{\gamma^{2} \hat{\xi}^{2}}\left(\hat{k}^{T}\hat{A}_{trn}^{{\dagger}}\hat{A}_{trn}^{{ \dagger}T}\hat{k}\right)\hat{\varepsilon}_{trn}^{T}\hat{t}^{T}\hat{t}\hat{ \varepsilon}_{trn}+\frac{2\theta_{trn}^{5}\|\hat{k}\|^{4}\|\hat{t}\|^{2}}{ \gamma^{2}\hat{\xi}}\hat{\varepsilon}_{trn}^{T}\hat{t}^{T}\underbrace{\hat{k}^ {T}\hat{A}_{trn}^{\dagger}\hat{h}^{T}}_{0}\hat{t}\hat{\varepsilon}_{trn}$ $\displaystyle\ \ \ \ \ +\frac{2\theta_{trn}^{5}\|\hat{k}\|^{2}\|\hat{t}\|^{4}} {\gamma^{2}\hat{\xi}}\left(\hat{k}^{T}\hat{A}_{trn}^{{\dagger}}\hat{A}_{trn}^{ {\dagger}T}\hat{k}\right)\underbrace{\hat{\varepsilon}_{trn}^{T}\hat{k}\hat{t} \hat{\varepsilon}_{trn}}_{0}+\frac{2\theta_{trn}^{4}\|\hat{k}\|^{2}\|\hat{t}\| ^{2}}{\gamma^{2}}\hat{\varepsilon}_{trn}^{T}\hat{k}\underbrace{\hat{k}^{T}\hat {A}_{trn}^{\dagger}\hat{h}^{T}}_{0}\hat{t}\hat{\varepsilon}_{trn}$ $\displaystyle\ \ \ \ \ +\frac{\theta_{trn}^{4}\|\hat{k}\|^{4}\|\hat{h}\|^{2}}{ \gamma^{2}}\hat{\varepsilon}_{trn}^{T}\hat{t}^{T}\hat{t}\hat{\varepsilon}_{trn }+\frac{4\theta_{trn}^{4}\|\hat{k}\|^{2}\|\hat{t}\|^{2}}{\gamma^{2}}\hat{ \varepsilon}_{trn}^{T}\hat{t}^{T}\underbrace{\hat{k}^{T}\hat{A}_{trn}^{\dagger }\hat{h}^{T}}_{0}\hat{t}\hat{\varepsilon}_{trn}$ $\displaystyle\ \ \ \ \ +\frac{2\theta_{trn}^{3}\|\hat{k}\|^{2}\|\hat{h}\|^{2} \hat{\xi}}{\gamma^{2}}\underbrace{\hat{\varepsilon}_{trn}^{T}\hat{k}\hat{t} \hat{\varepsilon}_{trn}}_{0}+\frac{\theta_{trn}^{4}\|\hat{t}\|^{4}}{\gamma^{2} }\left(\hat{k}^{T}\hat{A}_{trn}^{{\dagger}}\hat{A}_{trn}^{{\dagger}T}\hat{k} \right)\hat{\varepsilon}_{trn}^{T}\hat{k}\hat{k}^{T}\hat{\varepsilon}_{trn}$ $\displaystyle\ \ \ \ \ +\frac{2\theta_{trn}^{3}\|\hat{t}\|^{2}\hat{\xi}}{ \gamma^{2}}\hat{\varepsilon}_{trn}^{T}\hat{k}\underbrace{\hat{k}^{T}\hat{A}_{ trn}^{\dagger}\hat{h}^{T}}_{0}\hat{k}^{T}\hat{\varepsilon}_{trn}+\frac{\theta_ {trn}^{2}\|\hat{h}\|^{2}\hat{\xi}^{2}}{\gamma^{2}}\hat{\varepsilon}_{trn}^{T} \hat{k}\hat{k}^{T}\hat{\varepsilon}_{trn}.$ $$

All the cross terms will have zero expectation here.

Now the only terms with nonzero expectation are

- (i)
$\hat{\varepsilon}_{trn}^{T}\hat{A}_{trn}^{\dagger}\hat{A}_{trn}^{{\dagger}T}
\hat{\varepsilon}_{trn}$.
- (ii)
$-\dfrac{2\theta_{trn}^{2}}{\gamma}\left(\|\hat{t}\|^{2}\hat{\varepsilon}_{trn}
^{T}\hat{A}_{trn}^{\dagger}\hat{A}_{trn}^{{\dagger}T}\hat{k}\hat{k}^{T}\hat{
\varepsilon}_{trn}+\|\hat{k}\|^{2}\hat{\varepsilon}_{trn}^{T}\hat{A}_{trn}^{
\dagger}\hat{h}^{T}\hat{t}\hat{\varepsilon}_{trn}\right)$.
- (iii)
$\dfrac{\theta_{trn}^{4}}{\gamma^{2}}\left(\|\hat{t}\|^{4}\left(\hat{k}^{T}\hat
{A}_{trn}^{{\dagger}}\hat{A}_{trn}^{{\dagger}T}\hat{k}\right)\hat{\varepsilon}
_{trn}^{T}\hat{k}\hat{k}^{T}\hat{\varepsilon}_{trn}+\|\hat{k}\|^{4}\|\hat{h}\|
^{2}\hat{\varepsilon}_{trn}^{T}\hat{t}^{T}\hat{t}\hat{\varepsilon}_{trn}\right)$.
- (iv)
$\displaystyle\left(\frac{\theta_{trn}^{6}\|\hat{t}\|^{4}\|\hat{k}\|^{4}}{
\gamma^{2}\hat{\xi}^{2}}-\frac{2\theta_{trn}^{4}\|\hat{t}\|^{2}\|\hat{k}\|^{2}
}{\gamma\hat{\xi}^{2}}+\frac{\theta_{trn}^{2}}{\hat{\xi}^{2}}\right)\left(\hat
{k}^{T}\hat{A}_{trn}^{{\dagger}}\hat{A}_{trn}^{{\dagger}T}\hat{k}\right)\hat{
\varepsilon}_{trn}^{T}\hat{t}^{T}\hat{t}\hat{\varepsilon}_{trn}+\frac{\theta_{
trn}^{2}\|\hat{h}\|^{2}\hat{\xi}^{2}}{\gamma^{2}}\hat{\varepsilon}_{trn}^{T}
\hat{k}\hat{k}^{T}\hat{\varepsilon}_{trn}$
$\displaystyle=\ \$
$\displaystyle\frac{\left(\theta_{trn}^{3}\|\hat{t}\|^{2}\|\hat{k}\|^{2}-\theta
_{trn}\gamma\right)^{2}}{\gamma^{2}\hat{\xi}^{2}}\left(\hat{k}^{T}\hat{A}_{trn
}^{{\dagger}}\hat{A}_{trn}^{{\dagger}T}\hat{k}\right)\hat{\varepsilon}_{trn}^{
T}\hat{t}^{T}\hat{t}\hat{\varepsilon}_{trn}+\frac{\theta_{trn}^{2}\|\hat{h}\|^
{2}\hat{\xi}^{2}}{\gamma^{2}}\hat{\varepsilon}_{trn}^{T}\hat{k}\hat{k}^{T}\hat
{\varepsilon}_{trn}$
$\displaystyle=\ \$
$\displaystyle\frac{\theta_{trn}^{2}}{\gamma^{2}}\left(\left(\hat{k}^{T}\hat{A}
_{trn}^{{\dagger}}\hat{A}_{trn}^{{\dagger}T}\hat{k}\right)\hat{\varepsilon}_{
trn}^{T}\hat{t}^{T}\hat{t}\hat{\varepsilon}_{trn}+\|\hat{h}\|^{2}\hat{\xi}^{2}
\hat{\varepsilon}_{trn}^{T}\hat{k}\hat{k}^{T}\hat{\varepsilon}_{trn}\right).$

In the last step, the cancellation follows from $\gamma=\theta_{trn}^{2}\|\hat{t}\|^{2}\|\hat{k}\|^{2}+\hat{\xi}^{2}$.
We use Lemmas 10, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21, 22, to multiply these expectations with SymPy. In particular, with the numbering above, we get

$$ $\mathbb{E}_{{}_{\varepsilon_{trn},A_{trn}}}[(i)]=\frac{d\tau_{\varepsilon_{trn }}^{2}}{2\tau_{A_{trn}}^{2}}(T_{2}-1),\text{ }\mathbb{E}_{{}_{\varepsilon_{trn },A_{trn}}}[(ii)]=-\frac{2\theta_{trn}^{2}c^{2}\tau_{\varepsilon_{trn}}^{2}}{ \gamma}\left(\frac{T_{1}-c\mu^{2}}{T_{1}^{3}}\right),$ $$

$$ $\mathbb{E}_{{}_{\varepsilon_{trn},A_{trn}}}[(iii)]=\frac{c(c+1)\theta_{trn}^{4 }\tau_{\varepsilon_{trn}}^{2}}{2\tau_{A_{trn}}^{6}\gamma^{2}}\left(T_{2}^{2}-T _{2}-\frac{2c\tau_{A_{trn}}^{4}}{T_{1}^{2}}\right),$ $$

$$ $\mathbb{E}_{{}_{\varepsilon_{trn},A_{trn}}}[(iv)]=\frac{c\theta_{trn}^{2}\tau_ {\varepsilon_{trn}}^{2}}{2\tau_{A_{trn}}^{4}\gamma^{2}}T_{2}(T_{2}-1).$ $$

We combine these terms to get the results. The variance follows from concentration.
∎

See 4

###### Proof.

The proof follows from the decomposition in Lemma 1.

$$ $\frac{1}{n_{tst}}\mathbb{E}_{\varepsilon_{trn},A_{trn}}\left\|\beta_{*}^{T}Z_{ tst}-\beta_{so}^{T}Z_{tst}\right\|_{F}^{2}\text{ gives the bias in Proposition \ref{prop:bias}.}$ $$

Furthermore,

$$ $\frac{1}{n_{tst}}\frac{\tau_{A_{tst}}^{2}n_{tst}}{M}\mathbb{E}_{\varepsilon_{ trn},A_{trn}}\|\beta_{so}\|_{F}^{2}\text{ gives the variance, }$ $$

where by Lemma 5,

$$ $\|\beta_{so}\|_{F}^{2}=(\beta_{*}^{T}u)^{2}\|\tilde{W}_{opt}\|_{F}^{2}+2\beta_ {*}^{T}\tilde{W}_{opt}^{T}(\hat{Z}_{trn}+\hat{A}_{trn})^{{\dagger}T}\hat{ \varepsilon}_{trn}+\hat{\varepsilon}_{trn}^{T}(\hat{Z}_{trn}+\hat{A}_{trn})^{ \dagger}(\hat{Z}_{trn}+\hat{A}_{trn})^{{\dagger}T}\hat{\varepsilon}_{trn},$ $$

The second term equals 0 in expectation due to entries of $\varepsilon_{trn}$ having mean 0. The other two terms have expectations given in Propositions 2, 3.
∎

###### Proposition 1 .

###### Proof.

###### Proposition 2 .

###### Proposition 3 .

###### Proof.

###### Proof.

## Appendix B Proof of Theorem 3 (Signal Plus Noise)

Now with a similar reformulation as A, we can rewrite the signal plus noise problem (no regularization) as follows:

$$ $\beta_{spn}^{T}=\arg\min_{\beta^{T}}\lVert\beta_{*}^{T}(Z_{trn}+A_{trn})+ \varepsilon_{trn}^{T}-\beta^{T}(Z_{trn}+A_{trn})\rVert_{F}^{2}$ $$

We are interested in the error:

$$ $\mathcal{R}_{so}(c,\mu,\tau)=\frac{1}{n_{tst}}\mathbb{E}_{A_{trn},A_{tst}, \varepsilon_{trn}}\left[\left\|\beta_{*}^{T}(Z_{tst}+A_{tst})-\beta_{spn}^{T}( Z_{tst}+A_{tst})\right\|_{F}^{2}\right].$ $$

See 3

###### Proof.

The proof techniques will be similar to A. For simplicity, here we say $A\overset{\text{E}}{=}B$ when their expectations with respect to the random variables are equal. We also suppress the error terms for brevity.

$$ $\displaystyle\left\|\beta_{*}^{T}(Z_{tst}+A_{tst})-\beta_{spn}^{T}(Z_{tst}+A_{ tst})\right\|_{F}^{2}$ $\displaystyle\overset{\text{E}}{=}$ $\displaystyle\left\|\beta_{*}^{T}Z_{tst}-\beta_{spn}^{T}Z_{tst}\right\|_{F}^{2 }+\left\|\beta_{*}^{T}A_{tst}-\beta_{spn}^{T}A_{tst}\right\|_{F}^{2}-0$ $\displaystyle\overset{\text{E}}{=}$ $\displaystyle\underbrace{\left\|\beta_{*}^{T}Z_{tst}-\beta_{spn}^{T}Z_{tst} \right\|_{F}^{2}}_{bias}+\underbrace{\left\|\beta_{spn}^{T}A_{tst}\right\|_{F} ^{2}}_{variance}+\underbrace{\left\|\beta_{*}^{T}A_{tst}\right\|_{F}^{2}-2 \beta_{*}^{T}A_{tst}A_{tst}^{T}\beta_{spn}}_{adjustment}$ $$

In the first equality, the cross term equals 0 in expectation since $A_{tst}$ has mean 0 entries. There is an extra term due to the existence of noise in the signal.

In this setting, the optimal set of parameters is now given by

$$ $\beta_{spn}^{T}=(\beta_{*}^{T}(Z_{trn}+A_{trn})+\varepsilon_{trn}^{T})(Z_{trn} +A_{trn})^{\dagger}=\beta_{so}^{T}+\beta_{*}^{T}A_{trn}(Z_{trn}+A_{trn})^{ \dagger}.$ $$

With this in mind, we revisit the expectations of terms in the decomposition separately.

Signal-and-noise Bias: For $c<1$, we adopt similar notations from A (since when we consider $\hat{A}_{trn}\in\mathbb{R}^{n\times(d+n)}$, naturally $n<d+n$ and we are in this case). We define $h=v_{trn}^{T}A_{trm}^{\dagger}$, $k=A_{trn}^{\dagger}u$, $t=v_{trn}^{T}(I-A_{trn}^{\dagger}A_{trn})$, $\xi=1+\theta_{trn}v_{trn}^{T}A_{trn}^{\dagger}u$, $\gamma_{1}=\theta_{trn}^{2}\|t\|^{2}\|k\|^{2}+\xi^{2}$, and

$$ $p_{1}=-\frac{\theta_{trn}^{2}\|k\|^{2}}{\xi}t^{T}-\theta_{trn}k,\text{ }q_{1}= -\frac{\theta_{trn}\|t\|^{2}}{\xi}k^{T}A_{trn}^{\dagger}-h.$ $$

The same results hold:

$$ $\displaystyle\beta_{*}^{T}Z_{tst}-\beta_{spn}^{T}Z_{tst}=$ $\displaystyle\beta_{*}^{T}Z_{tst}-\beta_{so}^{T}Z_{tst}-\beta_{*}^{T}A_{trn}(Z _{trn}+A_{trn})^{\dagger}Z_{tst}$ $\displaystyle=$ $\displaystyle\frac{\xi}{\gamma_{1}}\beta_{*}^{T}Z_{tst}+\frac{\theta_{tst}\xi} {\theta_{trn}\gamma_{1}}\varepsilon_{trn}^{T}p_{1}v_{tst}^{T}-\beta_{*}^{T}A_{ trn}(Z_{trn}+A_{trn})^{\dagger}Z_{tst}$ $$

by Lemma 3. We then look at the third term. Combining the pseudo-inverse formula A.5, the expansion of $\hat{p}\hat{q}^{T}$ A.7, and $\hat{A}_{trn}$, we can use a similar approach as in 3 and have some nice cancellations:

$$ $\displaystyle-\beta_{*}^{T}A_{trn}(Z_{trn}+A_{trn})^{\dagger}Z_{tst}$ $\displaystyle=-\beta_{*}^{T}A_{trn}\left(A_{trn}^{\dagger}+\frac{\theta_{trn}} {\xi}t^{T}k^{T}A_{trn}^{\dagger}-\frac{\xi}{\gamma_{1}}p_{1}q_{1}^{T}\right)Z_ {tst}$ $\displaystyle=-\theta_{tst}\beta_{*}^{T}A_{trn}\left(A_{trn}^{\dagger}-\frac{ \theta_{trn}^{2}\|t\|^{2}}{\gamma_{1}}kk^{T}A_{trn}^{\dagger}-\frac{\theta_{ trn}\xi}{\gamma_{1}}kh\right)uv_{tst}^{T}$ $\displaystyle=-\theta_{tst}\beta_{*}^{T}A_{trn}\left(kv_{tst}^{T}-\frac{\theta _{trn}^{2}\|t\|^{2}\|k\|^{2}}{\gamma_{1}}kv_{tst}^{T}-\frac{\theta_{trn}\xi}{ \gamma_{1}}khuv_{tst}^{T}\right)$ $\displaystyle=-\theta_{tst}\beta_{*}^{T}A_{trn}\left(1-\frac{\theta_{trn}^{2} \|t\|^{2}\|k\|^{2}}{\gamma_{1}}-\frac{\theta_{trn}\xi}{\gamma_{1}}\frac{\xi-1} {\theta_{trn}}\right)kv_{tst}^{T}$ $\displaystyle=-\theta_{tst}\frac{\xi}{\gamma_{1}}\beta_{*}^{T}A_{trn}A_{trn}^{ \dagger}uv_{tst}^{T}=-\frac{\xi}{\gamma_{1}}\beta_{*}^{T}Z_{tst}.$ $$

Hence, with $\mu=0$ (see Corollary 1), if $c<1$, the bias equals

$$ $\frac{1}{n_{tst}}\left\|\beta_{*}^{T}Z_{tst}-\beta_{spn}^{T}Z_{tst}\right\|_{F }^{2}=\frac{1}{n_{tst}}\left\|\frac{\theta_{tst}\hat{\xi}}{\theta_{trn}\gamma} \varepsilon_{trn}^{T}p_{1}v_{tst}^{T}\right\|_{F}^{2}\overset{\text{E}}{=} \frac{\theta_{tst}^{2}\tau_{\varepsilon_{trn}}^{2}}{n_{tst}\left(\theta_{trn}^ {2}c+\tau_{A_{trn}}^{2}\right)}\left(\frac{c}{1-c}\right).$ $$

If $c>1$, now we have dimension $d>n$ and need to further define $s=(I-A_{trn}A_{trn}^{\dagger})u$, $\gamma_{2}=\theta_{trn}^{2}\|s\|^{2}\|h\|^{2}+\xi^{2}$, and

$$ $p_{2}=-\frac{\theta_{trn}^{2}\|s\|^{2}}{\xi}A_{trn}^{\dagger}h^{T}-\theta_{trn }k,\text{ }q_{2}^{T}=-\frac{\theta_{trn}\|h\|^{2}}{\xi}s^{T}-h.$ $$

We note $s^{T}u=\|s\|^{2}$. By Theorem 5 from Meyer (), the following pseudo-inverse holds:

$$ $(Z_{trn}+A_{trn})^{\dagger}=A_{trn}^{\dagger}+\frac{\theta_{trn}}{\xi}A_{trn}^ {\dagger}h^{T}s^{T}-\frac{\xi}{\gamma_{2}}p_{2}q_{2}^{T}.$ $$

With a similar simplification, we have

$$ $\displaystyle\beta_{*}^{T}Z_{tst}-\beta_{spn}^{T}Z_{tst}=$ $\displaystyle\beta_{*}^{T}Z_{tst}-\beta_{so}^{T}Z_{tst}-\beta_{*}^{T}A_{trn}(Z _{trn}+A_{trn})^{\dagger}Z_{tst}$ $\displaystyle=$ $\displaystyle\frac{\xi}{\gamma_{2}}\beta_{*}^{T}Z_{tst}+\frac{\theta_{tst}\xi} {\theta_{trn}\gamma_{2}}\varepsilon_{trn}^{T}p_{2}v_{tst}^{T}-\beta_{*}^{T}A_{ trn}(Z_{trn}+A_{trn})^{\dagger}Z_{tst}.$ $$

Furthermore, we recall expressions of the defined variables, and the third become can be simplified as:

$$ $\displaystyle\beta_{*}^{T}A_{trn}(Z_{trn}+A_{trn})^{\dagger}Z_{tst}$ $\displaystyle=\theta_{tst}\beta_{*}^{T}A_{trn}\left(A_{trn}^{\dagger}uv_{tst}^ {T}+\frac{\theta_{trn}}{\xi}A_{trn}^{\dagger}h^{T}s^{T}uv_{tst}^{T}-\frac{\xi} {\gamma_{2}}p_{2}q_{2}^{T}uv_{tst}^{T}\right)$ $\displaystyle=\theta_{tst}\beta_{*}^{T}A_{trn}\left(kv_{tst}^{T}+\frac{\theta_ {trn}\|s\|^{2}}{\xi}A_{trn}^{\dagger}h^{T}v_{tst}^{T}-\frac{\xi}{\gamma_{2}}p_ {2}q_{2}^{T}uv_{tst}^{T}\right)$ $\displaystyle=\theta_{tst}\beta_{*}^{T}A_{trn}\left(-\frac{1}{\theta_{trn}}p_{ 2}v_{tst}^{T}-\frac{\xi}{\gamma_{2}}p_{2}\left(-\frac{\theta_{trn}\|h\|^{2}}{ \xi}s^{T}-h\right)uv_{tst}^{T}\right)$ $\displaystyle=\theta_{tst}\beta_{*}^{T}A_{trn}\left(-\frac{1}{\theta_{trn}}p_{ 2}v_{tst}^{T}+\frac{\xi}{\gamma_{2}}p_{2}\left(\frac{\theta_{trn}\|s\|^{2}\|h \|^{2}}{\xi}+\frac{\xi-1}{\theta_{trn}}\right)v_{tst}^{T}\right)$ $\displaystyle=\theta_{tst}\beta_{*}^{T}A_{trn}\left(-\frac{1}{\theta_{trn}}p_{ 2}v_{tst}^{T}+\frac{\xi}{\gamma_{2}}p_{2}\left(\frac{\theta_{trn}^{2}\|s\|^{2} \|h\|^{2}+\xi^{2}-\xi}{\xi\theta_{trn}}\right)v_{tst}^{T}\right)$ $\displaystyle=\theta_{tst}\beta_{*}^{T}A_{trn}\left(-\frac{1}{\theta_{trn}}p_{ 2}v_{tst}^{T}+\frac{\xi}{\gamma_{2}}p_{2}\left(\frac{\gamma_{2}-\xi}{\xi\theta _{trn}}\right)v_{tst}^{T}\right)$ $\displaystyle=-\frac{\theta_{tst}\xi}{\theta_{trn}\gamma_{2}}\beta_{*}^{T}A_{ trn}p_{2}v_{tst}^{T}.$ $$

Hence, we have that

$$ $\displaystyle\left\|\beta_{*}^{T}Z_{tst}-\beta_{spn}^{T}Z_{tst}\right\|_{F}^{2}=$ $\displaystyle\left\|\frac{\xi}{\gamma_{2}}\beta_{*}^{T}Z_{tst}+\frac{\theta_{ tst}\xi}{\theta_{trn}\gamma_{2}}(\beta_{*}^{T}A_{trn}+\varepsilon_{trn}^{T})p_ {2}v_{tst}^{T}\right\|_{F}^{2}$ $\displaystyle\overset{E}{=}$ $\displaystyle\left\|\frac{\xi}{\gamma_{2}}\beta_{*}^{T}Z_{tst}\right\|_{F}^{2} +\left\|\frac{\theta_{tst}\xi}{\theta_{trn}\gamma_{2}}\varepsilon_{trn}^{T}p_{ 2}v_{tst}^{T}\right\|_{F}^{2}+\left\|\frac{\theta_{tst}\xi}{\theta_{trn}\gamma _{2}}\beta_{*}^{T}A_{trn}p_{2}v_{tst}^{T}\right\|_{F}^{2}$ $\displaystyle+\frac{2\theta_{tst}\xi^{2}}{\theta_{trn}\gamma_{2}^{2}}\beta_{*} ^{T}A_{trn}p_{2}v_{tst}^{T}Z_{tst}^{T}\beta_{*}.$ $$

The first two expectations are given in Corollary 1 (the bias). We compute expectations for the last two additional terms here. Similar to Lemma 17, we have $kA_{trn}^{\dagger}h^{T}\overset{E}{=}0$ in this case. We recall the expression of $p_{2}$, $q_{2}$ and obtain

$$ $\displaystyle\left\|\frac{\theta_{tst}\xi}{\theta_{trn}\gamma_{2}}\beta_{*}^{T }A_{trn}p_{2}v_{tst}^{T}\right\|_{F}^{2}$ $\displaystyle=\frac{\theta_{tst}^{2}\xi^{2}}{\theta_{trn}^{2}\gamma_{2}^{2}} \beta_{*}^{T}A_{trn}p_{2}p_{2}^{T}A_{trn}^{T}\beta_{*}$ $\displaystyle\overset{E}{=}\frac{\theta_{tst}^{2}\xi^{2}}{\theta_{trn}^{2} \gamma_{2}^{2}}\beta_{*}^{T}A_{trn}\left(\frac{\theta_{trn}^{4}\|s\|^{4}}{\xi^ {2}}A_{trn}^{\dagger}h^{T}hA_{trn}^{{\dagger}T}+\theta_{trn}^{2}kk^{T}\right)A _{trn}^{T}\beta_{*}$ $\displaystyle\overset{E}{=}\frac{\theta_{tst}^{2}\theta_{trn}^{2}\|s\|^{4}}{ \gamma_{2}^{2}}\beta_{*}^{T}A_{trn}A_{trn}^{\dagger}h^{T}hA_{trn}^{{\dagger}T} A_{trn}^{T}\beta_{*}+\frac{\theta_{tst}^{2}\xi^{2}}{\gamma_{2}^{2}}\beta_{*}^{ T}A_{trn}kk^{T}A_{trn}^{T}\beta_{*}$ $$

where the cross terms have zero expectation. Taking general variances into account, from Lemma from Sonthalia & Nadakuditi (), we have that

$$ $\|s\|^{2}\overset{E}{=}\frac{c-1}{c},\text{ }\xi\overset{E}{=}1,\text{ }\gamma _{2}\overset{E}{=}\frac{\theta_{trn}^{2}+\tau_{A_{trn}}^{2}}{\tau_{A_{trn}}^{2 }},\text{ }\frac{1}{\lambda}\overset{E}{=}\frac{c}{\tau_{A_{trn}}^{2}(c-1)}.$ $$

Furthermore, we turn to the SVD of the noise matrix ($A_{trn}=U\Sigma V^{T}$, $\Sigma\in\mathbb{R}^{d\times n_{trn}}$) to evaluate these expectations. We define $a=U^{T}u$, $b=U^{T}\beta_{*}$, $c=V^{T}v_{trn}$. Since $U$ and $V$ are uniformly random orthogonal matrices independent from each other, these vectors are centered and uniformly random. $a$, $b$ are unit vectors, and $c$ has length $\|\beta_{*}\|$. We expand the following two terms using SVD:

$$ $\displaystyle\beta_{*}^{T}A_{trn}A_{trn}^{\dagger}h^{T}hA_{trn}^{{\dagger}T}A_ {trn}^{T}\beta_{*}$ $\displaystyle=(\beta_{*}^{T}U\Sigma\Sigma^{\dagger}\Sigma^{{\dagger}T}V^{T}v_{ trn})^{2}$ $\displaystyle=\left(\beta_{*}^{T}U\begin{bmatrix}I_{n_{trn}}&0\\ 0&0\\ \end{bmatrix}\Sigma^{{\dagger}T}V^{T}v_{trn}\right)^{2}$ $\displaystyle=\sum_{i=1}^{n_{trn}}a_{i}^{2}b_{i}^{2}\frac{1}{\sigma_{i}^{2}}+ \text{ cross terms}$ $\displaystyle\overset{E}{=}n_{trn}\frac{\|\beta_{*}\|^{2}}{d}\frac{1}{n_{trn}} \frac{c}{\tau_{A_{trn}}^{2}(c-1)}=\frac{\|\beta_{*}\|^{2}}{d}\frac{c}{\tau_{A_ {trn}}^{2}(c-1)}$ $$

$$ $\beta_{*}^{T}A_{trn}kk^{T}A_{trn}^{T}\beta_{*}=(\beta_{*}^{T}U\Sigma\Sigma^{ \dagger}U^{T}u)^{2}=\left(\beta_{*}^{T}U\begin{bmatrix}I_{n_{trn}}&0\\ 0&0\\ \end{bmatrix}U^{T}u\right)^{2}\overset{E}{=}\frac{(\beta_{*}^{T}u)^{2}}{c}$ $$

In the first term, the cross terms have zero expectation due to the centered uniform vectors. In the second term, the terms in the middle do not change the alignment between $W$ and $u$, so we have $W^{T}u$.
Putting everything together, we have

$$ $\left\|\frac{\theta_{tst}\xi}{\theta_{trn}\gamma_{2}}\beta_{*}^{T}A_{trn}p_{2} v_{tst}^{T}\right\|_{F}^{2}\overset{E}{=}\frac{\theta_{tst}^{2}\tau_{A_{trn}}^ {4}}{c(\theta_{trn}^{2}+\tau_{A_{trn}}^{2})^{2}}(\beta_{*}^{T}u)^{2}+\frac{ \theta_{tst}^{2}\theta_{trn}^{2}\tau_{A_{trn}}^{2}}{(\theta_{trn}^{2}+\tau_{A_ {trn}}^{2})^{2}}\left(1-\frac{1}{c}\right)\frac{\|\beta_{*}\|^{2}}{d}.$ $$

With a similar approach, we now look at the last term:

$$ $\displaystyle\frac{2\theta_{tst}\xi^{2}}{\theta_{trn}\gamma_{2}^{2}}\beta_{*}^ {T}A_{trn}p_{2}v_{tst}^{T}Z_{tst}^{T}\beta_{*}$ $\displaystyle=\frac{2\theta_{tst}^{2}\xi^{2}}{\theta_{trn}\gamma_{2}^{2}}\beta _{*}^{T}A_{trn}\left(-\frac{\theta_{trn}^{2}\|s\|^{2}}{\xi}A_{trn}^{\dagger}h^ {T}-\theta_{trn}k\right)u^{T}\beta_{*}$ $\displaystyle\overset{E}{=}-\frac{2\theta_{tst}^{2}\xi^{2}}{\gamma_{2}^{2}} \beta_{*}^{T}A_{trn}ku^{T}\beta_{*}.$ $$

Here the first term becomes 0 in expectation since

$$ $\beta_{*}^{T}A_{trn}A_{trn}^{\dagger}h^{T}u^{T}\beta_{*}=\beta_{*}^{T}\beta_{* }^{T}U\Sigma\Sigma^{\dagger}\Sigma^{{\dagger}T}V^{T}v_{trn}u^{T}\beta_{*},$ $$

where $V^{T}v_{trn}^{T}$ is centered and uniformly random. Lastly,

$$ $\beta_{*}^{T}A_{trn}ku^{T}\beta_{*}=\beta_{*}^{T}U\Sigma\Sigma^{\dagger}U^{T} uu^{T}\beta_{*}\overset{E}{=}\frac{(\beta_{*}^{T}u)^{2}}{c},$ $$

$$ $\rightarrow\frac{2\theta_{tst}\xi^{2}}{\theta_{trn}\gamma_{2}^{2}}\beta_{*}^{T }A_{trn}p_{2}v_{tst}^{T}Z_{tst}^{T}\beta_{*}\overset{E}{=}-\frac{2\theta_{tst} ^{2}\tau_{A_{trn}}^{4}}{c(\theta_{trn}^{2}+\tau_{A_{trn}}^{2})^{2}}(\beta_{*}^ {T}u)^{2}.$ $$

Now we have all these terms. If $c>1$, the bias equals

$$ $\frac{1}{n_{tst}}\left\|\beta_{*}^{T}Z_{tst}-\beta_{spn}^{T}Z_{tst}\right\|_{F }^{2}\overset{E}{=}$ $$

$$ $\frac{\theta_{tst}^{2}}{n_{tst}\left(\theta_{trn}^{2}+\tau_{A_{trn}}^{2}\right )^{2}}\left(\tau_{A_{trn}}^{2}\left(1-\frac{1}{c}\right)\left(\tau_{A_{trn}}^{ 2}(\beta_{*}^{T}u)^{2}+\theta_{trn}^{2}\frac{\|\beta_{*}\|^{2}}{d}\right)+\tau _{\varepsilon_{trn}}^{2}\left(\frac{\theta_{trn}^{2}c+\tau_{A_{trn}}^{2}}{c-1} \right)\right).$ $$

Signal-and-noise Variance: By Lemma 4,

$$ $\displaystyle\hskip 10.0pt\left\|\beta_{spn}^{T}A_{tst}\right\|_{F}^{2} \overset{\text{E}}{=}\frac{\tau_{A_{tst}}^{2}n_{tst}}{d}\|\beta_{spn}\|_{F}^{2}$ $\displaystyle=\frac{\tau_{A_{tst}}^{2}n_{tst}}{d}(\beta_{*}^{T}(Z_{trn}+A_{trn })+\hat{\varepsilon}_{trn}^{T})(Z_{trn}+A_{trn})^{\dagger}(Z_{trn}+A_{trn})^{{ \dagger}T}(\beta_{*}^{T}(Z_{trn}+A_{trn})+\hat{\varepsilon}_{trn}^{T})^{T}$ $\displaystyle\overset{\text{E}}{=}\frac{\tau_{A_{tst}}^{2}n_{tst}}{d}\beta_{*} ^{T}(Z_{trn}+A_{trn})(Z_{trn}+A_{trn})^{\dagger}(Z_{trn}+A_{trn})^{{\dagger}T} (Z_{trn}+A_{trn})^{T}\beta_{*}$ $\displaystyle\hskip 10.0pt+\frac{\tau_{A_{tst}}^{2}n_{tst}}{d}\hat{\varepsilon }_{trn}^{T}(Z_{trn}+A_{trn})^{\dagger}(Z_{trn}+A_{trn})^{{\dagger}T}\hat{ \varepsilon}_{trn}.$ $$

Again the cross term is 0 in expectation due to mean 0 entries of $\varepsilon_{trn}$. Proposition 2 gives the expectation of the second term (we make $\mu\to 0$). The first expectation is

$$ $\beta_{*}^{T}(Z_{trn}+A_{trn})(Z_{trn}+A_{trn})^{\dagger}(Z_{trn}+\hat{A}_{trn })^{{\dagger}T}(\hat{Z}_{trn}+\hat{A}_{trn})^{T}\beta_{*}\overset{\text{E}}{=} \min\left(1,\frac{1}{c}\right)\|\beta_{*}\|^{2}.$ $$

With $\mu=0$ results (see Corollary 1),
If c < 1, the variance equals

$$ $\frac{1}{n_{tst}}\left\|\beta_{spn}^{T}A_{tst}\right\|_{F}^{2}\overset{\text{E }}{=}\frac{\tau_{A_{tst}}^{2}\tau_{\varepsilon_{trn}}^{2}c}{\tau_{A_{trn}}^{2} (1-c)}\left(1-\frac{\theta_{trn}^{2}c}{d\left(\tau_{A_{trn}}^{2}+\theta_{trn}^ {2}c\right)}\right)+\frac{\tau_{A_{tst}}^{2}}{d}\|\beta_{*}\|^{2}.$ $$

If c > 1, the variance equals

$$ $\frac{1}{n_{tst}}\left\|\beta_{spn}^{T}A_{tst}\right\|_{F}^{2}\overset{\text{E }}{=}\frac{\tau_{A_{tst}}^{2}\tau_{\varepsilon_{trn}}^{2}}{\tau_{A_{trn}}^{2}( c-1)}\left(1-\frac{\theta_{trn}^{2}c}{d\left(\tau_{A_{trn}}^{2}+\theta_{trn}^{ 2}\right)}\right)+\frac{1}{c}\frac{\tau_{A_{tst}}^{2}}{d}\|\beta_{*}\|^{2}.$ $$

Further Adjustment: By Lemma 4, we see that

$$ $\|\beta_{*}^{T}A_{tst}\|_{F}^{2}\overset{\text{E}}{=}\frac{\tau_{A_{tst}}^{2}n _{tst}}{d}\|\beta_{*}\|^{2},\text{ and }$ $$

$$ $\beta_{*}^{T}A_{tst}A_{tst}^{T}\beta_{spn}\overset{\text{E}}{=}\beta_{*}^{T}A_ {tst}A_{tst}^{T}(\hat{Z}_{trn}+\hat{A}_{trn})^{{\dagger}T}(\hat{Z}_{trn}+\hat{ A}_{trn})^{T}\beta_{*}\overset{\text{E}}{=}\min\left(1,\frac{1}{c}\right)\frac {\tau_{A_{tst}}^{2}n_{tst}}{d}\|\beta_{*}\|^{2},$ $$

If c < 1, the adjustment equals

$$ $\frac{1}{n_{tst}}\left(\left\|\beta_{*}^{T}A_{tst}\right\|_{F}^{2}-2\beta_{*}^ {T}A_{tst}A_{tst}^{T}\beta_{spn}\right)\overset{\text{E}}{=}-\frac{\tau_{A_{ tst}}^{2}}{d}\|\beta_{*}\|^{2}.$ $$

If c > 1, the adjustment equals

$$ $\frac{1}{n_{tst}}\left(\left\|\beta_{*}^{T}A_{tst}\right\|_{F}^{2}-2\beta_{*}^ {T}A_{tst}A_{tst}^{T}\beta_{spn}\right)\overset{\text{E}}{=}\left(1-\frac{2}{c }\right)\frac{\tau_{A_{tst}}^{2}}{d}\|\beta_{*}\|^{2}.$ $$

Putting things together from the three separate terms, we get the results.

∎

###### Proof.

## Peer Reviews

confidence: 3
contribution: 1
initial_rating: 5
presentation: 3
questions: As hinted above my main concern on this manuscript is the close relationship with previous works, namely (Ba et al., 2022; Moniri et al., 2024). 

Could the authors comment on the link between their results and (Ba et al. 2022) in the context of Gaussian Universality (see e.g. [1]) ? From my understanding of their paper, i.e. a single spike in the feature matrix, they show that in the learning rate regime considered in this paper Gaussian Universality should hold. There is indeed an extensive regime of learning rates after the BBP transition that still falls under the umbrella of Gaussian models, resulting in effectively "linear" generalization properties. 

One additional weakness of this submission is the related works coverage. The authors do a great job in covering the random matrix theory literature, while many manuscripts that analyze learned representations with gradient descent with different tools are not properly mentioned, see e.g. [2,3,4]. Although in these works the authors do not focus on the exact asymptotic calculation of the test error, many insights should translate to the present setting. On the other hand, [5] precisely characterize the generalization error using non-rigorous methods; what is the relationship with the present work?

The results in the present submission should relate directly to the ones in Section 4 of (Moniri et al. 2024), albeit the differences correctly reported by the authors in the two settings. Could the author elaborate on this? 

What is the bottleneck for the present thereotcial tools to analyze multiple spikes (corresponding to higher learning rate scaling in Moniri et al. 2024)? 

Closely related to the above, [5] worked along the lines of (Moniri et al. 2024) to provide the equivalent description in the regime where the spikes recombine with the bulk (maximal scaling regime). Do the authors see a possible extension of their analysis to this scaling? 


- [1] Hu & Lu 2022, Universality laws for high-dimensional learning with random features. 
- [2] Damian et al. 2022, Neural networks can learn representations with gradient descent. 
- [3] Dandi et al. 2023, How two-layer neural networks learn, one (giant) step at a time.
- [4] Ba et al. 2023, Learning in the presence of low-dimensional structure: a spiked random matrix perspective.
- [5] Cui et al. 2024, Asymptotics of feature learning in two-layer networks after one gradient-step.
soundness: 2
strengths: The paper is nicely written. The mathematical claims are correctly phrased and the numerical illustrations are coherent with the main text. The research problem is relevant in the theoretical machine learning community.
summary: The authors analyze the generalization properties of spiked covariate models. The theoretical analysis is motivated by recent works on two-layer networks trained with a single gradient step that showed how the feature matrix possesses different spikes associated with the learning rate scaling used in the optimization step. The proof scheme uses tools coming from random matrix theory that enables the asymptotic computation of the generalization error. The theoretical claims are accompanied by coherent numerical illustrations.
weaknesses: My main concern with the present submission is the lack of clear elements of novelty. The paper heavily relies on results coming from related works and it restricts their setting in many ways (as fairly reported by the authors at the end of the manuscript). More details are provided below.

---

confidence: 4
contribution: 1
initial_rating: 3
presentation: 1
questions: 1. In Line 178, $F_1$ denotes the case with a single spike (as shown by Moniri et al., 2023). However, Moniri et al., 2023 showed that $F_1$ can include multiple spikes, and the number of spikes depends on the step size of the gradient step. Where is the discussion about the effect of step size in this paper? Similarly, where is the discussion on the impact of $o(\sqrt{n})$ term for $F_1$?

2. What is $l_j$ in Theorem 2 (Line 204)? Do the authors mean $l$?

3. In footnote 3 (Line 266), the authors say "... the limiting e.s.d for $F_0$ is not necessarily Marchenko-Pastur distribution ... This difference is not too important, as instead of using the Stieltjes transform for the Marchenko-Pastur distribution in our paper, we could use the result from Péché (2019); Piccolo & Schröder (2021) instead." Why wouldn't the authors directly use the mentioned result directly?

4. Why is there no regularization for the signal-plus-noise problem when there is regularization for the signal-only problem (Line 278-285)?

5. Typo in Line 285: "We consider on the instance-specific risk.". Typo in Line 313: " Then, any for data ...". 

6. Undefined symbols in Theorem 3 (Line 312 - 324): $\asymp$ and $<<$.

7. How do the authors arrive at "Hence, we see that if the target vector y has a smaller dependence on the noise (bulk) component A, then we see that the spike affects the generalization error." in Line 380? Its connection to the previous part seems to be missing.

8. How do the authors come up with the equation for the peak point of double descent in Line 477? Is it an empirical observation or a theoretical result?
soundness: 2
strengths: * The motivation for this paper is good since the recent line of work studying two-layer neural networks after one gradient step (Ba et al., 2022; Moniri et al., 2023) has received significant attention.
* The authors precisely characterize generalization errors (risk) for two linear regression problems with spiked covariance data, while the problems differ regarding the target function.
   + They provide bias and variance decomposition of the risk.
   + They illustrate the "double-descent phenomenon" and provide a formula for the peak location (a.k.a interpolation threshold) of the double-descent phenomenon, which is beneficial for understanding the phenomenon.
   + The authors specifically focus on the impact of the spike (in the data model) on the risk for different cases. Thus, they show when and how the spike affects the generalization error.
summary: Motivated by a recent work studying two-layer neural networks (Moniri et al., 2023), the paper studies linear regression under a data model with a spiked covariance (Couillet & Liao, 2022). The spiked covariance consists of a spike component (signal) and a bulk component (noise). Thus, the authors characterize the risk (a.k.a generalization error) with a specific focus on the effect of the spike. They find that the spike does not impact the risk in the underparameterized case. In contrast, the spike introduces an additional term (called "correction term") in the risk for the overparameterized case. However, they mention that the correction term is of order $O(1/d)$, which vanishes in the asymptotic case. Thus, the spike does not affect the risk in the asymptotic case but does in the finite case. Then, the authors focus on a case where the targets $y$ only depend on the signal (spike) component of inputs $\mathbf{x}$ in order to highlight the effect of the spike on the risk. In this case, the correction term depends on the alignment between the spiked eigenvector $\mathbf{u}$ corresponding to the spike and the target function $\boldsymbol{\beta}$. Furthermore, the paper illustrates how the generalization error for this setting exhibits the so-called double-descent phenomenon with a formula for the peak location (a.k.a interpolation threshold).
weaknesses: * The presentation in this paper is not good
  + Although the paper is motivated by Moniri et al. (2023), there are significant discrepancies between the setting of this paper and that of Moniri et al. (2023), as the authors mention in Section 5. While Moniri et al. (2023) considered two-layer neural networks after one gradient step under isotropic data assumption, this work considers linear regression under spiked covariance data assumption. There exists a relationship between these two, but they are not exactly the same. For example, there is a difference between the target $y$ generation of the two settings. Furthermore, $\mathbf{A}$ (noise component) and $\mathbf{Z}$ (spike component) are dependent in the case of Moniri et al. (2023), while the dependence is ignored here (see lines 251-255).
  + Some notations are used without definition (e.g, $\delta_{\lambda_i}(\lambda)$ in Line 126, or $\Sigma(d_k)$ in Line 147).
  + There are significant typos in equations. For example, $y$ should be a scaler in Line 76, but it is written as a vector, which makes the equation wrong. Another example is that $l_j$ in Theorem 2 (Line 204) is not defined, and I think the authors meant $l$ instead of $l_j$. A third example is that the function $R_{spn}(c;\tau,\theta)$ defined in Line 301 and its usage $R_{spn}(c,0,\tau)$ in Theorem 3 (Line 317-321) are different in terms of parameters.

* Limited contribution/novelty
  + Most of the results in this paper are trivial extensions of the results by Hastie et al. (2022) and Li & Sonthalia (2024), which significantly limits the novelty and originality of the paper. Note that Hastie et al. (2022) studied linear regression under a generic covariance assumption with bounded eigenvalues. Here, some eigenvalues can diverge as dimensions go to infinity, but this case is also covered by Li & Sonthalia (2024).
  + There exists a related work (Cui et al., 2024) that is not mentioned in this paper. Cui et al. (2024) characterized the generalization error (risk) for two-layer neural networks after one gradient step under isotropic data (same setting as that of Moniri et al. (2023)). Although there exist methodological differences between (Cui et al., 2024) and this paper, the motivations are the same, and their settings are similar.
  + During the review period of this paper, a related work (Dandi et al., 2024) that can be considered as follow-up of (Cui et al., 2024) was appeared on arXiv. While Cui et al. (2024) used (non-rigorous) replica method from statistical physics for their analysis, Dandi et al. (2024) studied the same setting with random matrix theory, which is also the main tool in this paper. Therefore, this paper and (Dandi et al. 2024) studied similar settings with similar methodologies. Note that since (Dandi et al., 2024) appeared after the submission of this paper, I am only mentioning it for the sake of completeness.

Overall, I think this paper should be rewritten with more focus on the impacts of the spike covariance on the generalization error of linear regression, and the new presentation should clearly differentiate the current work from the work by Hastie et al. (2022), Li & Sonthalia (2024), Cui et al. (2024), and Dandi et al. (2024).

Cui et al. (2024): Asymptotics of feature learning in two-layer networks after one gradient-step. (ICML 2024)

Dandi et al. (2024): A Random Matrix Theory Perspective on the Spectrum of Learned Features and Asymptotic Generalization Capabilities.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 3
questions: 1. Could you provide a reference for the statement, 'It has been shown that to understand the generalization...' on line 39?
2. Is your generalization analysis very different from the work  of Li & Sonthalia (2024)?
soundness: 3
strengths: 1. They construct two linear regression problems with spiked covariance.
2. They well explain the previous work of Moniri et al. (2023).
3. Precise quantification of the generalization errors are also provided for both model.
summary: The paper considers the linear least squares regression for data with simple spiked covariance. They quantify the empirical risk of test data.
weaknesses: 1. They reference the work of Moniri et al., but this work is unrelated to neural networks or gradient descent; it addresses a purely linear regression problem for data with simple spiked covariances.

2. They do not account for the generalization ability of neural networks after a single gradient step, as they bypass the gradient step entirely by assuming the W1 matrix directly, which does not reflect the full process of neural network training.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: Regarding the weaknesses mentioned above, I would like to ask:

1. What novel results could the authors conclude in the feature learning setting in neural networks using the main theorems 3,4?

2. How could the authors show the assumption on the dependence does not affect the result? Is there any experimental validation?

3. From Figure 4.1, we can see that the effect of the spike correction term is small when $n$ is large. Is the main theorem still useful to explain the phenomenon we see from feature learning?
soundness: 2
strengths: This paper provides a detailed proof of their main theorems with clearly stated definitions. It extends over previous results like [1,2].


[1]: Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in highdimensional
ridgeless least squares interpolation. Annals of statistics, 50(2):949, 2022.
[2]: Xinyue Li and Rishi Sonthalia. Least squares regression can exhibit under-parameterized double
descent. Advances in Neural Information Processing Systems, 2024.
summary: This paper analyses the generalization error of linear regression with spiked covariance. Previous literature has been using asymptotic limit of the empirical spectral density to analyse the generalization error of linear regression. At the limit, the effect of the spike vanishes. However, it is not the case for finite sample size. This paper fills the gap by showing there is a correction term for finite sample size $n$.
weaknesses: However, this paper has some obvious weaknesses:

1. The paper is motivated by the spiked covariance from the one-step gradient feature learning in neural networks (Section 1). However, it did not show how the results can be applied to the feature learning scenario. I question the amount of contribution this paper provides.
2. The assumption in line 2221-222 and 253-255 is too strong. The analysis breaks down if there is dependency in the cross term. However, the paper did not show how big the difference the predicted result would be when there is dependence in the cross term. It is questionable if the result in this paper is applicable in realistic machine learning settings.
3. This paper has problems with the wordings, even in main theorems. This makes the reading difficult. For instance:

> Theorem 3 (line 313): ...Then, any for data $X\in\mathbb{R}^{n\times d}, y\in\mathbb{R}^n$ from the signal-plus-noise model that satisfy: $1\ll \tau\_{A_{trn}}^2,\tau_{A_{tst}}^2\ll d, \theta_{trn}^2/\tau_{A_{trn}}^2<<n, \theta_{tst}^2/\tau_{A_{tst}}^2 << n_{tst}$. Then for $c<1$,...

The first sentence needs to be rephrased and the symbol $\ll$ is not consistent. Also, there are some typos like:
> line 350: Hence the spike has does not have an effect...

> line 372, ... we see an affect that...

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 4
questions: - In the discussion above 4.1, the assumption $\theta=\tau^2 n$ seems again to contradict the assumption $\theta^2/\tau^2\ll n$ in the statement of the Theorem. Furthermore, this seems to correspond to a strong spike regime, how can the authors recover the spikeless results of Hastie et al. (2022) in this case? This might be a misunderstanding on my side, but more discussion would be beneficial.

Minor:

- l.074, 347 : incomplete sentences
- l.203 I think $\ell_j$ is not defined
- In 3.3, more discussion in the main text about why only the unregularized case is considered for the spn case, while generic $\mu$ is considered for the signal-only model, would be helpful for intuition, whether it is for technical reasons or because it is not interesting.
soundness: 3
strengths: The paper is well written, clearly motivating the study, and describing in simple terms the model considered. Sufficient intuition is provided at most steps of the discussion. The technical results are clearly exposed and sufficiently discussed. Although I did not go through the proof in detail, the technical results seem scientifically sound.
summary: Motivated by the problem of training the readout of a two-layer network after on large gradient step on the first layer, the authors consider the problem of linear regression on a spiked data model. They provide a characterization of the test error, for two linear target functions, respectively depending on only the spike part or the complete input. They discuss how for the latter, the spike does not asymptotically influence the test error, but does non-asymptotically.
weaknesses: I have a number of concerns related to the technical discussions, and the relation to previous works, which I detail below, and in the question section. These concerns regard the discussion of the main theorems, and not the theorems themselves, although I have not carefully verified the proof. These concerns prevent me from giving a higher score to this submission. On the other hand, I would be very happy to increase my score, were those concerns to be addressed by the authors.

- The authors claim l.083 that Moniri et al. (2023) do not quantify the test error after one gradient step. To the best of my understanding, they do provide such a tight characterization (Theorem 4.5). Could the authors clarify their claim, and emphasize how their work is positioned with respect to Moniri et al. (2023)?

- I find the discussion l.332-355 somewhat confusing, as they discuss the specialization of Theorem 3 for $\theta=\tau\sqrt{n}$. Doesn't this directly contradict the assumption $\theta^2/\tau^2\ll n$ stated in the Theorem? Since this specialization leads to one of the main qualitative results of the paper (namely the spike only affects the test error in non-asymptotic cases), this point would gain to be clarified.  The same holds for l.452 with respect to Theorem 4.

- I believe more intuition about the different scaling considered would help solidify the intuition for the spn case, regarding when the spike matters. In particular, the authors could for instance recall the scaling of the terms $z_i^\top\beta_*$, $a_i^\top \beta_*$, and emphasize their respective strengths in the different scalings of $\theta, \tau$ considered. I am curious if the signal part is much smaller than the second term when the spike has no effect, or if the argument is more subtle.

Meta-review: Summary of Scientific Claims and Findings:
The paper investigates the generalization properties of least squares regression with spiked covariance matrices, motivated by neural network training dynamics after one gradient step. The authors provide asymptotic analyses and derive corrections for finite-sample generalization errors, introducing a novel parameter that interpolates between "signal-only" and "signal-plus-noise" regimes. The findings highlight the impact of spike-target alignment on generalization and demonstrate phenomena like double descent.

Strengths:
Well-Explained Setup: The authors offer a clear motivation by connecting spiked covariance to neural network dynamics post-training.
Finite-Sample Corrections: The inclusion of finite-sample effects extends beyond prior asymptotic-focused works.
Novel Interpolation Parameter: The introduction of a parameter to interpolate between different models is a thoughtful addition.
Mathematical Rigor: The proofs are detailed and provide bias-variance decompositions and characterizations of risk.


Weaknesses:
Limited Novelty: The paper heavily relies on extensions of prior works (e.g., Moniri et al. and Li & Sonthalia) without sufficiently differentiating its contributions.
Weak Connection to Neural Networks: While motivated by neural networks, the setting deviates significantly, and the connection to practical feature learning scenarios is tenuous.
Clarity and Presentation Issues: Ambiguities in notation, numerous typos, and inconsistencies reduce readability and undermine clarity.
Assumptions: The paper relies on strong assumptions, such as independence of cross terms, which may limit applicability to realistic machine learning settings.
Impact on the Field: Despite deriving finite-sample corrections, the theoretical advancements and insights remain incremental.

Decision:
Given the identified strengths and weaknesses, the paper is marginally below the acceptance threshold. While it offers an interesting exploration of spiked covariance effects on generalization, it lacks sufficient novelty and clarity to merit acceptance. However, I encourage the authors to address these concerns in future submissions, particularly improving clarity and rigorously connecting the results to neural networks and practical scenarios.

Decision: Reject