# Minimum-Norm Interpolation Under Covariate Shift

Neil Mallinar∗
UC San Diego
<EMAIL_ADDRESS>
Austin Zane∗
UC Berkeley
<EMAIL_ADDRESS>
Spencer Frei
UC Davis
<EMAIL_ADDRESS>
Bin Yu
UC Berkeley
<EMAIL_ADDRESS>
###### Abstract

Transfer learning is a critical part of real-world machine learning
deployments and has been extensively studied in experimental works with
overparameterized neural networks. However, even in the simplest setting of
linear regression a notable gap still exists in the theoretical understanding
of transfer learning. In-distribution research on high-dimensional linear
regression has led to the identification of a phenomenon known as benign
overfitting, in which linear interpolators overfit to noisy training labels
and yet still generalize well. This behavior occurs under specific conditions
on the source covariance matrix and input data dimension. Therefore, it is
natural to wonder how such high-dimensional linear models behave under
transfer learning. We prove the first non-asymptotic excess risk bounds for
benignly-overfit linear interpolators in the transfer learning setting. From
our analysis, we propose a taxonomy of beneficial and malignant covariate
shifts based on the degree of overparameterization. We follow our analysis
with empirical studies that show these beneficial and malignant covariate
shifts for linear interpolators on real image data, and for fully-connected
neural networks in settings where the input data dimension is larger than the
training sample size.

**footnotetext: Equal contribution.

##  1 Introduction

Practical deployments of machine learning models are almost always in a
transfer learning setting, where models trained on a source data distribution
with noisy labels are expected to perform well on a different target data
distribution, referred to as the “out-of-distribution” (OOD) dataset [Ogl+22,
DAm+22]. There have been many experimental works on transfer learning with
complex models and datasets [Rec+19, Koh+21, Mil+21, Hen+21, Wen+22, Lia+23],
but remarkably fewer attempts to study it theoretically, even in the simplest
case of linear models which have been of great interest in recent years
[Dwi+20, Bar+20, Has+22, TB23].

There has been an extensive “in-distribution” (ID) theoretical interest in
high-dimensional linear regression and specifically interpolation, meaning a
model reaches zero training loss. Frameworks such as “benign overfitting”, or
“harmless interpolation” [Bar+20, Mut+20] emerged as an attempt to explain why
interpolating neural networks often do not overfit catastrophically [Zha+17].
They found that, in specific cases, overfitting can be “benign”, meaning that
a model interpolates noisy training labels and yet has vanishing excess risk.
In linear regression, this occurs if and only if the training (source)
covariance matrix satisfies very specific conditions. Under these conditions,
the minimum-norm interpolator (MNI) approximately acts like a ridge regression
solution.

This sparked an initial wave of in-distribution theoretical research into
benign overfitting in high-dimensional linear models [CLB22, TB23, CL23],
kernel regression [RZ19, Haa+23, BS23], and even some shallow neural networks
[FCB22, Kou+23, KYS23, Xu+24]. Although these works were motivated by a desire
to understand overfitting in modern deep learning, recent works have shown
that in many practical settings of interest, overfitting is not benign
[Mal+22, Haa+23, Lai+23]. Thus, deeper investigations into the generalization
behavior of overfit models are warranted.

Given the increasing prevalence of overparameterized models, it is natural to
ask how such models perform in the transfer learning setting. There have been
some efforts to answer this in the theoretically tractable cases of linear
regression and random feature and kernel regression [PMW22, Wan23]. However,
these works either provide asymptotic bounds that require the training sample
size and data dimension to go to infinity at the same rate [TAP21], study
minimax settings which only considers worst-case risk [LHL21], or focus on
augmented gradient-based training algorithms, like importance weighting
[Wan+22].

#### Summary of contributions.

In this paper, we investigate the generalization behavior of the minimum
$\ell_{2}$-norm linear interpolator (MNI) under distribution shifts when the
source distribution satisfies the conditions necessary for benign overfitting.
We summarize our main contributions as follows.

  * •

We provide the first non-asymptotic, instance-wise risk bounds for covariate
shifts in interpolating linear regression when the source covariance matrix
satisfies benign overfitting conditions and commutes with the target
covariance matrix.

  * •

We use our risk bounds to propose a taxonomy of covariate shifts for the MNI.
We show how the ratio of target eigenvalues to source eigenvalues and the
degree of overparameterization affect whether a shift is beneficial or
malignant, meaning OOD risk is better or worse than ID risk, respectively.

  * •

We empirically show that our taxonomy of shifts holds: (1) for the MNI on real
image data under natural shifts like blur (a beneficial shift) and noise (a
malignant shift), underscoring the significance of our findings beyond the
idealized source and target covariances for which our theory is applicable;
(2) for neural networks in settings where the input data dimension is larger
than the training sample size, showing that our findings for the MNI are also
reflective of the behavior of more complex models.

###  1.1 Prior work and comparisons to this work

Excess risk analysis under distribution shifts:  [TAP21] give an asymptotic
analysis of high-dimensional random feature regression in covariate shift.
They require the number of samples, $n$, data dimension, $p$, and random
feature dimension to go to $\infty$ at the same rate. In contrast, our non-
asymptotic analysis considers finite sample cases and differing rates. This
allows us to draw new conclusions about how the degree of overparameterization
changes the way in which interpolating linear models exhibit out-of-
distribution (OOD) generalization. Additionally, our bounds let us analyze any
sequence of eigenvalues for the target feature covariance matrix, which is not
possible within their framework.

[LHL21] study linear regression under distribution shifts in the minimax
setting. Their minimax bounds consider the worst-case risk over an
$\ell_{2}$-ball of target models, whereas we compute risk bounds specific to
any model instantiation, with no restriction on the target model class.
Furthermore, their experimental results only consider the underparameterized
regime.

Several other works study OOD generalization in more distant settings.
[Wan+22] study linear interpolators for classification, when trained with
gradient descent and importance weighting, whereas we consider the closed-form
MNI for linear regression. [Sim+23] study covariate shifts when the target
function class is the sum of two other function classes, and shifts are
defined with regard to metric entropy between classes, whereas we focus on
well-specified linear models. [PMW22, MPW23, Fen+23] consider covariate shift
in kernel regression based on likelihood (“importance”) ratios between source
and target distributions while we consider source and target eigenvalue ratios
which offer granular insights into feature scale changes whereas likelihood
ratios capture shifts that affect the global data distribution. [PMW22, MPW23]
also analyze worst-case, minimax risk for nonparametric function classes.
Finally, we note that risk bounds in these prior works do not sufficiently
account for the behavior of the high-rank covariance tail that benign
overfitting requires.

Experimental work on distribution shifts: [HD19] propose the CIFAR-10C dataset
as an OOD counterpart to CIFAR-10, featuring test set images corrupted by
visual filters like blurs and noises. [Koh+21] present benchmarks on more
realistic datasets with modern models that can be seen “in-the-wild”. [Mil+21]
experimentally show a linear relationship between ID accuracy and OOD accuracy
for a wide range of modern neural networks and datasets, though their results
show ID accuracy is almost always better than OOD accuracy. On a subset of
CIFAR-10C, we find settings in which OOD accuracy is better than ID accuracy
for linear interpolators.

Benign overfitting “in-distribution”: [Bar+20] propose benign overfitting,
give a non-asymptotic analysis of the MNI, and show specific, necessary
conditions under which the MNI achieves zero excess risk in-distribution.
[TB23] extend this work by considering benign overfitting in the case of ridge
regression. Our proof techniques follow most closely to the ideas presented in
these two papers for the in-distribution setting. [FCB22] show benign
overfitting in shallow non-linear MLPs trained with gradient descent on the
logistic loss if the data dimension grows faster than the number of training
samples. [Mal+22] experimentally show that interpolating neural networks do
not benignly overfit due to the low input data dimension. Our experiments
build on this by looking at settings in which $p>n$ and $n<p$ where $n$ is the
training sample size and $p$ is the input data dimension. Other works study
benign overfitting under a variety of conditions [Kou+23, CL23, Fre+23].

##  2 Preliminaries

We extend notations in [Bar+20] and [TB23] to the transfer learning setting
with OOD generalization risk as our performance metric. Appendix A formalizes
our setting of linear regression under distribution shift, and we provide
necessary details here.

###  2.1 Covariate assumptions

Consider source and target distributions, $\mathcal{D}_{\mathsf{s}}$ and
$\mathcal{D}_{\mathsf{t}}$, both over
$(x,y)\in\mathbb{R}^{p}\times\mathbb{R}$. The source design matrix,
$X\in\mathbb{R}^{n\times p}$, has rows $x\stackrel{{\scriptstyle
iid}}{{\sim}}\mathcal{D}_{\mathsf{s}}$ such that
$\operatorname*{\mathbb{E}}_{\mathcal{D}_{\mathsf{s}}}[x]=0.$ We consider the
overparameterized regime with $n<p$ (see e.g. [Bar+20]).

Denote the source and target population covariance matrices by
$\Sigma_{\mathsf{s}}$ and $\Sigma_{\mathsf{t}}\in\mathbb{R}^{p\times p}$. We
assume that there exists an orthonormal basis in which both matrices are
diagonal, but show in Section 4 with experiments that our results hold even
when this is violated. Formally,

$\displaystyle\Sigma_{\mathsf{s}}$
$\displaystyle=\operatorname*{\mathbb{E}}_{\mathcal{D}_{\mathsf{s}}}[xx^{T}]=\mathrm{diag}(\lambda_{1},...,\lambda_{p}),$
$\displaystyle\Sigma_{\mathsf{t}}$
$\displaystyle=\operatorname*{\mathbb{E}}_{\mathcal{D}_{\mathsf{t}}}[xx^{T}]=\mathrm{diag}(\tilde{\lambda}_{1},...,\tilde{\lambda}_{p}),$

where $\lambda_{1}\geq...\geq\lambda_{p}>0$, $\tilde{\lambda}_{i}\geq 0$ for
all $i$, and $\sum_{i}\lambda_{i}\tilde{\lambda}_{i}<\infty$.

Assume further that the rows of the whitened data matrix
$Z:=X\Sigma_{\mathsf{s}}^{-1/2}$ are mean-zero i.i.d.
$\sigma_{x}^{2}$-subgaussian random vectors with independent components.
Subgaussianity is a common assumption in statistical learning theory that
encompasses a wide array of distributions of interest [Ver18].

###  2.2 Linear regression models for source and target data

Denote the source response vector by $\bm{y}_{\mathsf{s}}\in\mathbb{R}^{n}$.
Assume a linear regression model
$\bm{y}_{\mathsf{s}}=X{\theta_{\mathsf{s}}^{*}}+\bm{\varepsilon}_{\mathsf{s}}$,
where the noise vector $\bm{\varepsilon}_{\mathsf{s}}$ has independent
components with mean 0 and variance $v^{2}_{\bm{\varepsilon}_{\mathsf{s}}}$.
For an observation pair $(x,y)\sim\mathcal{D}_{\mathsf{t}}$, the target
responses are defined as
$y=x^{T}{\theta_{\mathsf{t}}^{*}}+\mathbf{\varepsilon}_{\mathsf{t}}$, where
${\theta_{\mathsf{t}}^{*}}\in\mathbb{R}^{p}$ and the noise vector
$\mathbf{\varepsilon}_{\mathsf{t}}$ has mean 0 and variance
$v_{\mathbf{\varepsilon}_{\mathsf{t}}}^{2}$. Note that we use the same $(x,y)$
for source and target data, but will differentiate between the two by
explicitly denoting the distribution from which the pair is drawn.

###  2.3 Minimum-norm interpolator and target excess risk

Given a source data matrix $X$, the minimum-norm interpolator (MNI) for any
vector $\xi\in\mathbb{R}^{n}$ is defined as

$\displaystyle\widehat{\theta}(\xi)$
$\displaystyle:=\operatorname*{argmin}\left\\{\left\|\theta\right\|^{2}:X\theta=\xi\right\\}$
$\displaystyle=X^{T}(XX^{T})^{-1}\xi.$

If we consider $\xi=\bm{y}_{\mathsf{s}}$, then we recover the MNI for the
labels given by the response model, but our analysis will also involve
implicit MNIs for different label vectors in $\mathbb{R}^{n}.$

The quantity that we seek to bound is the excess risk on the target
distribution, which we define for an estimator $\theta\in\mathbb{R}^{p}$ as,

$\displaystyle
R(\theta,\mathcal{D}_{\mathsf{t}}):=\operatorname*{\mathbb{E}}_{(x,y)\sim\mathcal{D}_{\mathsf{t}}}\left[\left(y-x^{T}\theta\right)^{2}-\left(y-x^{T}{\theta_{\mathsf{t}}^{*}}\right)^{2}\right].$
(1)

We now derive bounds for the target excess risk and its expectation over the
source response noise. The proof of the following can be found in Appendix C.

######  Theorem 2.1.

(Target excess risk decomposition) The excess risk of the MNI trained on the
source data, when evaluated on the target distribution, satisfies

$\displaystyle
R(\widehat{\theta}(\bm{y}_{\mathsf{s}}),\mathcal{D}_{\mathsf{t}})\leq$
$\displaystyle 4B_{1}+4B_{2}+2V_{\bm{\varepsilon}_{\mathsf{s}}},$ (2)

and

$\displaystyle\operatorname*{\mathbb{E}}_{\bm{\varepsilon}_{\mathsf{s}}}R(\widehat{\theta}(\bm{y}_{\mathsf{s}}),\mathcal{D}_{\mathsf{t}})$
$\displaystyle=B_{1}+B_{2}+\operatorname*{\mathbb{E}}_{\bm{\varepsilon}_{\mathsf{s}}}V_{\bm{\varepsilon}_{\mathsf{s}}}+2({\theta_{\mathsf{t}}^{*}}-{\theta_{\mathsf{s}}^{*}})^{\top}\Sigma_{\mathsf{t}}({\theta_{\mathsf{s}}^{*}}-\widehat{\theta}(X{\theta_{\mathsf{s}}^{*}})),$

where we define

$\displaystyle B_{1}$
$\displaystyle:=\|{\theta_{\mathsf{s}}^{*}}-{\theta_{\mathsf{t}}^{*}}\|_{\Sigma_{\mathsf{t}}}^{2},$
(3) $\displaystyle B_{2}$
$\displaystyle:=\|{\theta_{\mathsf{s}}^{*}}-\widehat{\theta}(X{\theta_{\mathsf{s}}^{*}})\|_{\Sigma_{\mathsf{t}}}^{2},$
(4) $\displaystyle V_{\bm{\varepsilon}_{\mathsf{s}}}$
$\displaystyle:=\|\widehat{\theta}(\bm{\varepsilon}_{\mathsf{s}})\|_{\Sigma_{\mathsf{t}}}^{2},$
(5)

and $\left\|x\right\|_{M}^{2}:=x^{\top}Mx$.

We observe that $B_{1}$ is a deterministic model shift term and that no
further analysis can improve its dependency on ${\theta_{\mathsf{s}}^{*}}$,
${\theta_{\mathsf{t}}^{*}}$, or $\Sigma_{\mathsf{t}}$. The cross-term,
$({\theta_{\mathsf{t}}^{*}}-{\theta_{\mathsf{s}}^{*}})^{\top}\Sigma_{\mathsf{t}}({\theta_{\mathsf{s}}^{*}}-\widehat{\theta}(X{\theta_{\mathsf{s}}^{*}}))$,
is dominated by the bias and variance as evidenced by the upper bound.
Therefore we focus our analysis on $B_{2}$ and
$V_{\bm{\varepsilon}_{\mathsf{s}}}$. A useful normalized version of
$V_{\bm{\varepsilon}_{\mathsf{s}}}$ is defined by

$\displaystyle
V=\operatorname*{\mathbb{E}}_{\bm{\varepsilon}_{\mathsf{s}}}\left[V_{\bm{\varepsilon}_{\mathsf{s}}}/v_{\bm{\varepsilon}_{\mathsf{s}}}^{2}\right].$
(6)

Note that $B_{2},V$ are reminiscent of the ID bias and variance in prior work
[Bar+20, TB23].

###  2.4 Separation of components and effective ranks

For an index $k$, we define the following quantities related to the effective
rank of the tail of $\Sigma_{\mathsf{s}}$ [TB23]:

$\displaystyle\rho_{k}=\frac{\sum_{i>k}\lambda_{i}}{n\lambda_{k+1}},\qquad
R_{k}=\frac{(\sum_{i>k}\lambda_{i})^{2}}{\sum_{i>k}\lambda_{i}^{2}}.$

$\rho_{k}$ measures the ratio of the energy of the source covariance tail to
the number of training data observations, after normalizing the tail
eigenvalues. $R_{k}$ measures the quantity of noisy features and how evenly
distributed their eigenvalues are. It is minimized when there is only one
nonzero eigenvalue and maximized when there are many equal eigenvalues.

Benign overfitting occurs if the MNI is overfit to noisy training labels and
yet ID excess risk decays to zero. The central finding of [Bar+20] is that the
only way benign overfitting happens for the MNI is if the following occurs:
(1) there exists a $k^{*}=\min\\{k\ :\ \rho_{k}\geq b\\}$ for a universal
constant $b>1$, meaning that the last $p-k^{*}$ components of
$\Sigma_{\mathsf{s}}$ have a high effective rank relative to the number of
training samples, $n$; (2) the magnitudes of the bottom $p-k^{*}$ eigenvalues
are small relative to the top $k^{*}$; and (3) $k^{*}\ll n$. More formally,
consider quantities $p=p(n)$, a sequence of source covariance matrices
$\Sigma_{n}=\mathrm{diag}(\lambda_{1},\cdots,\lambda_{p})$, $k^{*}=k^{*}(n)$
as defined above, $R_{k^{*}}=R_{k*}(\Sigma_{n})$, and
$\rho_{k}=\rho_{k}(\Sigma_{n})$. A sufficient condition for benign overfitting
is,

$\displaystyle\lim_{n\rightarrow\infty}\rho_{0}=\lim_{n\to\infty}\frac{k^{*}}{n}=\lim_{n\to\infty}\frac{n}{R_{k^{*}}}=0.$
(7)

If this occurs, then the MNI behaves similarly to an estimator with two
components. One component has variance similar to the ordinary least squares
(OLS) estimator in $k^{*}$ dimensions and bias similar to the ridge regression
solution with ridge parameter proportional to $\sum_{i>k}\lambda_{i}$, a sort
of data-induced regularization. The other component is a high-dimensional
component, which has vanishing variance when the data is sufficiently high-
dimensional and a bias which is proportional to
$\sum_{i>k}\lambda_{i}({\theta_{\mathsf{s}}^{*}})_{i}^{2}$ [TB23]. From these
conditions, we see that the top $k^{*}$ components are like “signal”
components of the data and the bottom $p-k^{*}$ components are “noise”
components.

###  2.5 Spiked covariance models

We will consider a special case of the $(k,\epsilon)$-spike model, a canonical
covariance structure that exhibits benign overfitting for the MNI [CLB22,
CL23], to experimentally show properties of interest.

######  Definition 1 ($(k,\delta,\epsilon)$-spike model).

For a source distribution $\mathcal{D}_{\mathsf{s}}$, $\delta>0$ and
$\epsilon>0$ such that $\delta\gg\epsilon$, let

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim\mathcal{D}_{\mathsf{s}}}[xx^{T}]$
$\displaystyle=\mathrm{diag}(\underbrace{\lambda_{1},\cdots,\lambda_{k}}_{=\delta},\underbrace{\lambda_{k+1},\cdots,\lambda_{p}}_{=\epsilon}).$

In this simplified setting, there are $k$ high-energy “signal” directions and
$p-k$ low-energy “noise” directions. For a target distribution
$\mathcal{D}_{\mathsf{t}}$, we use different hyperparameters
$\tilde{k},\tilde{\delta},\tilde{\epsilon}$ to similarly characterize a
shifted covariance matrix.

##  3 Main Theorems

This section provides upper and lower bounds for the variance and bias terms
in Equation 6 and Equation 4, respectively. We start with the bounds for the
variance term. Appendix D gives a high-level overview of our proof techniques.
Subsequent appendices provide complete proofs. Appendix E contains a proof of
the following theorem.

######  Theorem 3.1.

(Upper and lower bounds for the variance term) There exist universal constants
$b,c_{1}>1$ given in Lemma B.1, a universal constant $c_{2}$ given in Lemma
B.4 and a constant $c>1$ that only depends on $\sigma_{x},c_{1},c_{2}$, such
that for $k\in(0,n/c)$, with probability at least $1-10e^{-n/c}$,

$\displaystyle V$
$\displaystyle\geq\frac{1}{cn}\sum_{i=1}^{p}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}\min\left(1,\frac{\lambda_{i}^{2}}{\lambda_{k+1}^{2}(\rho_{k}+1)^{2}}\right):=\underline{V}.$
(8)

If in addition $\rho_{k}\geq b$, with probability $1-7e^{-n/c}$,

$\displaystyle V/c$
$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{k}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}+n\frac{\sum_{i>k}\tilde{\lambda}_{i}\lambda_{i}}{(\sum_{i>k}\lambda_{i})^{2}}:=\overline{V}.$
(9)

We first note that the variance lower bound does not depend on $\rho_{k}\geq
b$ and so it holds for any interpolating linear model, even when benign source
conditions are not satisfied. However, we will see that if $\rho_{k}\geq b$
for some $k$, then the upper and lower bounds are tight. In the case where
$\Sigma_{\mathsf{t}}=\Sigma_{\mathsf{s}}$, these bounds reduce to their in-
distribution counterparts [Bar+20]. Our variance bounds show that the excess
risk contribution of each feature is scaled by the ratio of the target and
source eigenvalues, $\tilde{\lambda}_{i}/\lambda_{i}$. We immediately see that
scaling down the target eigenvalues will lessen the overall contribution to
variance and that scaling up the target eigenvalues will increase the
contribution. We investigate these scaling factors and the separation of the
first $k$ components and last $p-k$ components in Section 3.1.

We now state upper and lower bounds for the bias term, $B_{2}$, given in
Equation 4. The proof of the following theorem can be found in Appendix F.

######  Theorem 3.2.

(Upper and lower bounds for the bias term) For the lower bound only, assume
that random models $\overline{\theta}$ are obtained from the underlying
${\theta_{\mathsf{s}}^{*}}$ as
$(\overline{\theta})_{i}=\gamma_{i}({\theta_{\mathsf{s}}^{*}})_{i}$, where
each $\gamma_{i}$ is an independent Rademacher random variable. There exists a
universal constant $b>1$, constants $c,C$ that depend only on $b$ and
$\sigma_{x}$, and $k<n/C$ such that if $\rho_{k}\geq b$, then with probability
at least $1-10e^{-n/c},$

$\displaystyle\operatorname*{\mathbb{E}}_{\bar{\theta}}[B_{2}]$
$\displaystyle\geq\frac{1}{c}\left(\sum_{i=1}^{k}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}\frac{\lambda_{i}({\theta_{\mathsf{s}}^{*}})_{i}^{2}}{(1+\frac{\lambda_{i}}{\lambda_{k+1}\rho_{k}})^{2}}+\sum_{i>k}\tilde{\lambda}_{i}({\theta_{\mathsf{s}}^{*}})_{i}^{2}\right):=\underline{B_{2}}.$

If we assume that $p$ is at most exponential in $n$, then with probability
$1-5e^{-n/c}$,

$\displaystyle
B_{2}/c\leq\|{\theta_{\mathsf{s}}^{*}}\|^{2}\sum_{i=1}^{p}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}\frac{\lambda_{i}}{\big{(}1+\frac{\lambda_{i}}{\lambda_{k+1}\rho_{k}}\big{)}}:=\overline{B_{2}}.$

Note that while the lower bound is in expectation over the random models
$\bar{\theta}$, the resulting expression only depends on the ground-truth
${\theta_{\mathsf{s}}^{*}}$. This Bayesian approach also appears in prior
work, i.e. [TB23]. In studying the bias lower bound, we observe a similar
separation of signal and noise components and depence on eigenvalue ratios as
in the variance bounds.

To show tightness of our bounds, we assume there exists a $k$ such that
$\rho_{k}\geq b$ for some universal constant $b>1$. When this condition is
satisfied, the variance bounds are tight up to constant factors. The bias
bounds leave a model-dependent and source covariance-dependent gap, which we
discuss in the proof overview in Appendix D and in the complete proof found in
Appendix G.

######  Theorem 3.3.

(Tightness of variance and bias bounds) Let the lower bound and upper bound of
$V$ be given by $\underline{V}$ and $\overline{V}$, respectively. There exists
a universal constant $b\geq 1$, and constant $c$ as defined in Theorem 3.1,
and $k\in(0,n/c)$ such that if $\rho_{k}\geq b$, then

$\displaystyle\underline{V}/\overline{V}\in\left[b^{-2}(1+b)^{-2}/c^{2},1\right].$

Let the lower bound and upper bound of $B_{2}$ be given by $\underline{B_{2}}$
and $\overline{B_{2}}$, respectively, and the assumptions of Theorem 3.2 be
satisfied. Then

$\displaystyle\underline{B_{2}}/\overline{B_{2}}$
$\displaystyle\in\left[\frac{\min_{i}\left\\{({\theta_{\mathsf{s}}^{*}})_{i}^{2}\
:\ ({\theta_{\mathsf{s}}^{*}})_{i}\neq
0\right\\}}{\|{\theta_{\mathsf{s}}^{*}}\|^{2}\left(1+b^{-1}\frac{\lambda_{1}}{\lambda_{k+1}}\right)},1\right].$

Note that the gap between our bias upper and lower bounds is independent of
the target distribution.

###  3.1 A Taxonomy of Shifts

We now present a taxonomy of covariate shifts on the target distribution
inspired by our prior analysis. We first consider OOD generalization and
formally categorize shifts as beneficial or malignant.

######  Definition 2 (Beneficial and Malignant shifts).

For a source distribution, ${\mathcal{D}}_{s}$, a target distribution,
${\mathcal{D}}_{t}$, excess risk, $R$, and MNI, $\widehat{\theta}$, we say
that a shift is

  1. 1.

beneficial if
$R(\widehat{\theta},\mathcal{D}_{s})>R(\widehat{\theta},{\mathcal{D}}_{t})$,

  2. 2.

malignant if
$R(\widehat{\theta},\mathcal{D}_{s})<R(\widehat{\theta},{\mathcal{D}}_{t})$.

We define these shifts for excess risk and note in Appendix J.1 that,
empirically, the variance is the primary contributor to excess risk and the
bias contributions are negligible when $\Sigma_{\mathsf{s}}$ satisfies benign
overfitting conditions. This is in keeping with prior literature that focuses
on studying variance in interpolating methods [Bar+20]. We will thus focus on
variance in the following discussion.

Prior work shows that if $n,p\to\infty$ at the same rate,
$\mathrm{tr}(\Sigma_{\mathsf{s}})<\mathrm{tr}(\Sigma_{\mathsf{t}})$ results in
malignant shifts on excess risk and
$\mathrm{tr}(\Sigma_{\mathsf{s}})>\mathrm{tr}(\Sigma_{\mathsf{t}})$ results in
beneficial shifts on excess risk [TAP21]. In this section we generalize these
conditions by considering differing rates of $n,p\to\infty$ and measuring
overparameterization by the modified “effective rank” measure $R_{k}/n$ rather
than $p$. This leads us to a novel characterization of the role of
overparameterization in covariate shifts. For completeness, we describe their
trace conditions in terms of our shifts in Appendix H.1.

We first consider separate multiplicative shifts on the signal components and
noise components. Let $\Sigma_{\mathsf{s}}$ be a covariance matrix that
satisfes benign source conditions. Define $\Sigma_{\mathsf{t}}$ by,
$\tilde{\lambda}_{i}=\alpha\lambda_{i}$ for $i\leq k$, and
$\tilde{\lambda}_{i}=\beta\lambda_{i}$ for $i>k$ with $\alpha,\beta\geq 0$.
While these are simple multiplicative shifts, they are instructive with regard
to understanding the dynamics of overparameterization and covariate shift. In
Appendix H.3 we generalize this analysis to allow for arbitrary multiplicative
shifts in every direction.

By Theorem 3.1, up to constants,

$\displaystyle V_{ood}\approx\alpha\frac{k}{n}+\beta\frac{n}{R_{k}}$ (10)

where $R_{k}=(\sum_{i>k}\lambda_{i})^{2}/(\sum_{i>k}\lambda_{i}^{2})$.

It is clear that if $V_{ood}-V_{id}>0$ then we have a malignant shift on the
variance, and if $V_{ood}-V_{id}<0$ then we have a beneficial shift on the
variance. Observe that,

$\displaystyle
V_{ood}-V_{id}\approx(\alpha-1)\frac{k}{n}+(\beta-1)\frac{n}{R_{k}}.$ (11)

In this expression, we see that the scales of signal and noise shifts,
$\alpha$ and $\beta$, are important, as is the relationship between $k/n$ (the
“classical” rate) and $n/R_{k}$ (the “high-dimensional” rate). The quantity
$n/R_{k}$ can be interpreted as an inverse measure of overparameterization,
where smaller values correspond to higher levels of overparameterization. The
rate of overparameterization relative to the classical rate of $k/n$
determines whether the shift on the first $k$ components ($\alpha$) or the
shift on the last $p-k$ components ($\beta$) contributes more to the
difference in excess risk.

Figure 1: We experiment with the $(k,\delta,\epsilon)$ spiked covariance
models and examine conditions for beneficial and malignant shifts as given in
Theorem 3.4. We take
$n=60,k=10,\delta=1.0,\epsilon=1e^{-6},\tilde{\delta}=2.0,\tilde{\epsilon}=1e^{-7}$,
and vary $p$. We see a cross-over from mild to severe overparameterization on
the right side of $p=n$ where both OOD shifts swap between beneficial and
malignant. For both ID and OOD curves, we observe that excess risk is a
decreasing function if input dimension. Curves are averaged over 100
independent runs.

Based on this intuition, we define two regimes of overparameterization: mild
and severe.

######  Definition 3 (Mild and severe overparameterization for multiplicative
shifts).

Let $\Sigma_{\mathsf{s}}$ be a source covariance that satisfies benign source
conditions and let $k\leq n$. Define $\Sigma_{\mathsf{t}}$ as,
$\tilde{\lambda}_{i}=\alpha\lambda_{i}$ for $i\leq k$ and
$\tilde{\lambda}_{i}=\beta\lambda_{i}$ for $i>k$, with $\alpha,\beta\geq 0$.
Let $C_{\alpha\beta}:=\left|\frac{\alpha-1}{1-\beta}\right|$.

We are in the mildly overparameterized regime if

$\frac{n}{R_{k}}=\omega\left(C_{\alpha\beta}\cdot\frac{k}{n}\right).$ (12)

We are in the severely overparameterized regime if

$\frac{n}{R_{k}}=o\left(C_{\alpha\beta}\cdot\frac{k}{n}\right).$ (13)

For $\beta=1$ we define $C_{\alpha\beta}=\infty$ and thus are effectively in
the severely overparameterized regime with regard to the types of shift we
observe.

It is clear that $k$ is important in defining regimes of overparameterization.
The aforementioned definitions hold for any $k<n$, however we derive our
taxonomy of shifts in the case in which $\exists\ k<n$ such that $\rho_{k}\geq
b$ for a universal constant $b>1$. We note that even for non-linear models or
settings that do not exhibit benign overfitting we can still think about a
notion of a “$k$” akin to the intrinsic dimension of the data. We empirically
show in Figures 6 and 7 that our taxonomy of shifts is reflective of shift
behavior in realistic settings by heuristically taking $k$ small enough to
sufficiently capture the low-dimensional signal in the data.

In Equation 11, we see that the limit of the severe overparameterization
regime would take $R_{k}\to\infty$ first, while holding other problem
parameters fixed. In this case, we are only left with $\alpha$ shifts on the
top $k$ components, as any shift on the bottom components is suppressed by the
high rank covariance tail. This leads to behaviors akin to classical
intuitions for an underparameterized linear regression estimator where
$k=p<n$. In this case, $\alpha>1$ leads to more variance and thus harder
learning, whereas $\alpha<1$ leads to less variance and thus easier learning.
These notions of hard vs. easy learning naturally correspond to
$\mathrm{tr}(\Sigma_{\mathsf{t}})>\mathrm{tr}(\Sigma_{\mathsf{s}})$ and
$\mathrm{tr}(\Sigma_{\mathsf{t}})<\mathrm{tr}(\Sigma_{\mathsf{s}})$,
respectively. This is shown experimentally in Figs. 1 and 7 by looking at the
left and right sides of the figures.

On the other hand, in the mildly overparameterized regime covariance tail
shifts are not sufficiently suppressed and lead to non-negligible interactions
with shifts on the signal components. An increase in energy in the signal
components can be counteracted by a decrease in energy in the noise
components, effectively increasing the contrast between signal and noise in
favor of the signal. Similarly, a decrease in energy in the signal components
can be harmfully counteracted by an increase in energy in the noise
components. This is visible in Figs. 1 and 7 just above the threshold of
interpolation. Interestingly, in the mildly overparameterized regime we can
also define settings in which
$\mathrm{tr}(\Sigma_{\mathsf{t}})>\mathrm{tr}(\Sigma_{\mathsf{s}})$ and yet
still obtain a beneficial shift, and settings in which
$\mathrm{tr}(\Sigma_{\mathsf{t}})<\mathrm{tr}(\Sigma_{\mathsf{s}})$ and yet
still obtain malignant shifts.

(a) $n=200,p=20,h=512$ (b) $n=200,p=20,h=2048$ (c) $n=200,p=2k,h=512$ (d)
$n=200,p=2k,h=2048$

Figure 2: We train 3 layer ReLU dense neural networks with hidden width, $h$,
on $n$ samples from $p$-dimensional Gaussians. ID test data is sampled from
the same distribution and OOD test sets are constructed based on beneficial
and malignant covariate shifts in our theory. Ground truth models are sampled
as ${\theta_{\mathsf{s}}^{*}}\sim\mathcal{S}^{p-1}$, no model shift is
invoked. For training data, $X$, train labels are given by
$\bm{y}_{\mathsf{s}}=X{\theta_{\mathsf{s}}^{*}}+\bm{\varepsilon}_{\mathsf{s}}$
with label noise $\bm{\varepsilon}_{\mathsf{s}}\sim\mathcal{N}(0,\sigma^{2})$.
All runs reach train loss $<5e^{-6}$. Points are averaged over 20 independent
runs with standard error bars reported.

We formalize these observations in the following theorem, the proof of which
can be found in Appendix H.2.

######  Theorem 3.4.

(Beneficial and Malignant Multiplicative Shifts on Variance) Let
$\Sigma_{\mathsf{s}}$ be a source covariance that satisfies benign source
conditions. That is, $\exists\ k$ such that $\rho_{k}\geq b$ for a universal
constant $b>1$. Define $\Sigma_{\mathsf{t}}$ as
$\tilde{\lambda}_{i}=\alpha\lambda_{i}$ for $i\leq k$ and
$\tilde{\lambda}_{i}=\beta\lambda_{i}$ for $i>k$, with $\alpha,\beta\geq 0$.

  1. 1.

If $\alpha<1,\beta\leq 1$ or $\alpha\leq 1,\beta<1$ then we obtain a
beneficial shift in variance.

  2. 2.

If $\alpha>1,\beta\geq 1$ or $\alpha\geq 1,\beta>1$ then we obtain a malignant
shift in variance.

  3. 3.

If we are in the mildly overparameterized regime:

     * •

$\alpha>1$ and $\beta<1$ leads to beneficial shifts;

     * •

$\alpha<1$ and $\beta>1$ leads to malignant shifts.

  4. 4.

If we are in the severely overparameterized regime:

     * •

$\alpha>1$ and $\beta<1$ leads to malignant shifts;

     * •

$\alpha<1$ and $\beta>1$ leads to beneficial shifts.

Figs. 1 and 5 demonstrate the relationship between the $n/R_{k}$ and $k/n$
rates in the case of $C_{\alpha\beta}=1.11,C_{\alpha\beta}=1$, respectively,
for spiked covariance models. In both, we clearly see a cross-over from
beneficial to malignant shifts when we transition from mild to severely
overparameterized.

#### Overparameterization improves OOD robustness

Focusing on just the target excess risk, let $\alpha=\alpha(n)$ and
$\beta=\beta(n,p)$. We say that the benignly-overfit MNI is robust if its
excess risk decays to zero despite the presence of multiplicative covariate
shifts. In order for the variance upper bound to decay to 0, it is sufficient
to have the shifts in the signal and noise components satisfy,
$\alpha=o(n/k),\;\beta=o(R_{k}/n).$ The condition $\beta=o(R_{k}/n)$ allows
the shift strength to increase at a rate determined by the level of
overparameterization, so we conclude that increasing the amount of
overparameterization improves robustness to multiplicative distribution
shifts. Note that $\alpha$ has no dependence on $R_{k}$ and so robustness to
shifts on the signal components is independent of the degree of
overparameterization.

##  4 Experiments

Our theoretical results have provided insight into distribution shifts in
high-dimensional linear regression. We now present experiments with linear
models and neural networks, relaxing many of the assumptions used for
theoretical results. Specifically, we empirically: (1) observe beneficial and
malignant shifts on synthetic and real data for linear models (benignly
overfit and otherwise) and even high-dimensional dense neural networks; (2)
show the benefit of overparameterization in covariate shift for interpolating
linear estimators; (3) validate that our findings hold when the source and
target covariance matrices are not simultaneously diagonalizable, as well as
under model misspecification; (4) provide experimental insight that high-
dimensional neural networks, i.e. when the input data dimension is large
relative to the training sample size, act similarly to the MNI whereas low-
dimensional neural networks do not, regardless of the level of
overparameterization. Details of experimental setup, data, and models are
given in Appendix I. We now discuss key observations and takeaways from the
experiments.

(a) Blur Covariance (b) Noise Covariance (c) MNI tested on Blur (d) MNI tested
on Noise

Figure 3: We fit the MNI to binary CIFAR-10 (dog vs. truck) and test on binary
CIFAR-10C under Gaussian blur and noise corruptions. In (a), (b) we plot the
eigenvalues of the covariance matrices for ID test data and on test sets for
each severity. To ensure $p>n$ we subsample the training set to $n=1k$ and
average curves over 50 independent runs. We evaluate the MNI against all 5
corruption severities and plot excess classification error vs training label
noise, which is class label flip probability. We see that the eigenspectra of
the OOD datasets is directly correlated to the OOD performance of the MNI.

###  4.1 Synthetic Data Experiments

Fig. 1 shows excess risk vs. input dimension for data sampled from the
$(k,\delta,\epsilon)$-spike covariance model with $k=10$, $\delta=1.0$, and
$\epsilon=1e^{-6}$. Beneficial and malignant shifts are seen in the setting of
Theorem 3.4 with $\alpha=2.0,\beta=0.1$. That is, we see two cross-over
points: one in the underparameterized regime and one in the overparameterized
regime (going from mild to severe). This suggests that non-negligible
covariance tail effects are a property of shifting when a model is in a region
around the double descent peak. The further we are from the double descent
peak, the more “classical” our behavior is, in that the top $k$ components are
the only ones that influence shift and the bottom $p-k$ components either
don’t exist or have negligible effects. Appendix J.1 explores this setup for
different values of $\alpha,\beta$ and interpolating linear models for
eigendecay rates that lead to harmful interpolation, i.e. tempered or
catastrophic overfitting [Mal+22].

Figs. 2 and 8 show similar results for 3-layer dense ReLU neural networks
trained until near-interpolation (train MSE $<5e^{-6}$) on synthetic data with
benign overfitting eigendecay rates [Bar+20]. For the neural network, we
consider $p$ to be the dimension of the input data, rather than the number of
network parameters. From Fig. 2 we observe similar trends predicted by our
theory for beneficial and malignant shifts when $p>n$, indicating that while
our theory is developed for linear models we are able to extrapolate to more
complex models. In both the $p>n$ and $p<n$ experiments, our results are
agnostic to the hidden width of the network, further suggesting that
overparameterization is qualitatively different from high-dimensionality. When
$p>n$, a neural network appears to act like the interpolating MNI under
distribution shifts. For $p<n$ the interpolating dense net does not exhibit
the properties of an interpolating MNI under distribution shift and the ID
excess error is better than both “beneficial” and “malignant” OOD excess
errors. However, the relative difference between beneficial and malignant
shifts is still preserved. Note that we observe the exact same behavior in
Fig. 10 when training ResNets to interpolation on CIFAR-10 and testing on
CIFAR-10C blur and noise corruptions [HD19].

###  4.2 CIFAR-10 Experiments

Next, we consider experiments with linear interpolators on a binarized
CIFAR-10 and CIFAR-10C with Gaussian noise and blur corruptions at varying
levels of corruption severity. For details, see Appendix I. This experiment
breaks the assumption of simultaneous diagonalizability, and the well-
specified assumption as the labels for CIFAR are not obtained by a ground-
truth linear model.

Fig. 3 shows empirical results on the MNI fit to this problem. We plot the
eigenspectra of the blur and noise covariances from CIFAR-10C compared to the
eigenspectra of CIFAR-10 in Figs. 3a, 3b. We identified these two shifts due
to their eigenspectra reflecting what we expect to lead to beneficial and
malignant shifts based on Theorem 3.4. We observe a tight relationship between
changes in the eigenspectra of the target data and excess classification error
when evaluated by the MNI. We notice that blurs reduce covariance energy with
increased blurring, like a “denoising”-style operation. Experimentally this
leads to improved OOD accuracy. In contrast, noise corruptions add energy to
the covariance tail and lead to worsened OOD accuracy. Fig. 9 also shows that
further overparameterization in this setting leads to improved behavior of the
MNI on both corruptions.

##  5 Conclusion and future work

Our work provides the first finite-sample, instance-wise analysis of the MNI
under transfer learning with high-dimensional linear models. We show a
taxonomy of beneficial and malignant covariate shifts depending on whether we
are in a mild or severely overparameterized regime. In the mildly
overparameterized regime, variance contributions on the top $k$ components
interact with that of the bottom $p-k$ components in non-negligible ways,
leading to non-standard shifts. In the severely overparameterized regime, the
high-rank covariance tail suppresses variance contributions in the bottom
$p-k$ components and so OOD generalization acts more “classical”, akin to
underparameterized linear regression where $k=p<n$.

Benign overfitting literature commonly claims to be motivated by
“overparameterized” neural networks, referring to the number of parameters in
the network rather than the dimension of the data. However recent works have
challenged this, suggesting the role of the ambient dimension and source
covariance is more important than parameter count in determining whether
overfitting is benign or catastrophic in neural networks [FCB23, KYS23]. Prior
work has also shown that gradient descent on 2-layer neural networks has an
implicit bias towards linear decision boundaries when $p\gg n$, independent of
the degree of overparameterization [Fre+22].

Our experiments further support the view that high-dimensional neural networks
behave similarly to high-dimensional linear models, whereas low-dimensional
neural networks do not. They provide a new and important perspective on the
difference between high-dimensionality and overparameterization in neural
networks in the case of distribution shift, which has yet to be appreciated in
the literature. While dimensionality and degree of overparameterization are
inextricably linked in linear regression, practical deep learning tends to
operate in the overparameterized setting, not the high-dimensional one.

An important future direction is to investigate the extent to which our
results hold for distribution shifts on more complex high-dimensional
datasets. It is also of interest to extend our finite-sample theoretical
analysis to shallow ReLU neural networks, other nonlinear models, and learning
algorithms that overfit in a tempered manner [Mal+22]. Finally, future work
might seek to extend our understanding of neural networks by carefully
studying the interplay between the data dimension, number of network
parameters, number of training samples, and the optimization algorithm and
loss function, and how this interplay can affect ID & OOD generalization.

## Acknowledgements

The authors thank Alexander Tsigler, Peter Bartlett, Emmanuel Abbe and Libin
Zhu for useful discussion and feedback on the manuscript.

We gratefully acknowledge partial support from NSF grants DMS-2209975,
2015341, NSF grant 2023505 on Collaborative Research: Foundations of Data
Science Institute (FODSI), the NSF and the Simons Foundation for the
Collaboration on the Theoretical Foundations of Deep Learning through awards
DMS-2031883 and 814639, and NSF grant MC2378 to the Institute for Artificial
CyberThreat Intelligence and OperatioN (ACTION). NM gratefully acknowledges
funding and support for this research from the Eric and Wendy Schmidt Center
at The Broad Institute of MIT & Harvard. AZ additionally acknowledges support
from NSF RTG Grant #1745640.

This work used Delta GPU compute nodes at NCSA and HPE and Expanse GPU compute
nodes at Dell and SDSC through allocation CIS220009 from the Advanced
Cyberinfrastructure Coordination Ecosystem: Services & Support (ACCESS)
program, which is supported by National Science Foundation grants #2138259,
#2138286, #2138307, #2137603, and #2138296 [Boe+23].

## References

  * [Bar+20] Peter L. Bartlett, Philip M. Long, Gábor Lugosi and Alexander Tsigler  “Benign Overfitting in Linear Regression”  In _Proceedings of the National Academy of Sciences_ 117.48, 2020, pp. 30063–30070
  * [BS23] Daniel Barzilai and Ohad Shamir  “Generalization in Kernel Regression Under Realistic Assumptions”  In _Preprint, arXiv:2312.15995_ , 2023
  * [Boe+23] Timothy J. Boerner, Stephen Deems, Thomas R. Furlani, Shelley L. Knuth and John Towns  “ACCESS: Advancing Innovation: NSF’s Advanced Cyberinfrastructure Coordination Ecosystem: Services & Support”  In _In Practice and Experience in Advanced Research Computing (PEARC ’23)_ , 2023  DOI: 10.1145/3569951.3597559
  * [CL23] Niladri S. Chatterji and Philip M. Long  “Deep Linear Networks can Benignly Overfit when Shallow Ones Do”  In _Journal of Machine Learning Research_ 24.117, 2023, pp. 1–39
  * [CLB22] Niladri S. Chatterji, Philip M. Long and Peter L. Bartlett  “The Interplay Between Implicit Bias and Benign Overfitting in Two-Layer Linear Networks”  In _Journal of Machine Learning Research_ 23.263, 2022, pp. 1–48
  * [DAm+22] Alexander D’Amour  “Underspecification Presents Challenges for Credibility in Modern Machine Learning”  In _Journal of Machine Learning Research_ 23.226, 2022, pp. 1–61
  * [Dwi+20] Raaz Dwivedi, Chandan Singh, Bin Yu and Martin J. Wainwright  “Revisiting minimum description length complexity in overparameterized models”  In _Preprint, arXiv:2006.10189_ , 2020
  * [Fen+23] Xingdong Feng, Xin He, Caixing Wang, Chao Wang and Jingnan Zhang  “Towards a Unified Analysis of Kernel-based Methods Under Covariate Shift”  In _Conference on Neural Information Processing Systems (NeurIPS)_ , 2023
  * [FCB23] Spencer Frei, Niladri S. Chatterji and Peter L. Bartlett  “Random Feature Amplification: Feature Learning and Generalization in Neural Networks”  In _Journal of Machine Learning Research_ 24.303, 2023, pp. 1–49
  * [FCB22] Spencer Frei, Niladri S Chatterji and Peter Bartlett  “Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Data”  In _Conference on Learning Theory (COLT)_ , 2022
  * [Fre+23] Spencer Frei, Gal Vardi, Peter L. Bartlett and Nathan Srebro  “Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximization”  In _Conference on Learning Theory (COLT)_ , 2023
  * [Fre+22] Spencer Frei, Gal Vardi, Peter L. Bartlett, Nathan Srebro and Wei Hu  “Implicit Bias in Leaky ReLU Networks Trained on High-Dimensional Data”  In _International Conference on Learning Representations (ICLR)_ , 2022
  * [Haa+23] Moritz Haas, David Holzmüller, Ulrike Luxburg and Ingo Steinwart  “Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimension”  In _Conference on Neural Information Processing Systems (NeurIPS)_ , 2023
  * [Has+22] Trevor Hastie, Andrea Montanari, Saharon Rosset and Ryan J. Tibshirani  “Surprises in High-Dimensional Ridgeless Least Squares Interpolation”  In _Annals of Statistics_ 50.2, 2022, pp. 949–986
  * [Hen+21] Dan Hendrycks, Steven Basart, Norman Mu, Saurav Kadavath, Frank Wang, Evan Dorundo, Rahul Desai, Tyler Zhu, Samyak Parajuli, Mike Guo, Dawn Song, Jacob Steinhardt and Justin Gilmer  “The Many Faces of Robustness: A Critical Analysis of Out-of-Distribution Generalization”  In _International Conference on Computer Vision (ICCV)_ , 2021
  * [HD19] Dan Hendrycks and Thomas G. Dietterich  “Benchmarking neural network robustness to common corruptions and perturbations”  In _International Conference on Learning Representations (ICLR)_ , 2019
  * [Koh+21] Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsubramani, Weihua Hu, Michihiro Yasunaga, Richard L. Phillips and Ian Gao  “Wilds: A benchmark of in-the-wild distribution shifts”  In _International Conference on Machine Learning (ICML)_ , 2021
  * [KYS23] Guy Kornowski, Gilad Yehudai and Ohad Shamir  “From Tempered to Benign Overfitting in ReLU Neural Networks”  In _Conference on Neural Information Processing Systems (NeurIPS)_ , 2023
  * [Kou+23] Yiwen Kou, Zixiang Chen, Yuanzhou Chen and Quanquan Gu  “Benign Overfitting in Two-layer ReLU Convolutional Neural Networks”  In _International Conference on Machine Learning (ICML)_ , 2023
  * [Lai+23] Jianfa Lai, Zixiong Yu, Songtao Tian and Qian Lin  “Generalization Ability of Wide Residual Networks”  In _Preprint, arXiv:2305.18506_ , 2023
  * [LHL21] Qi Lei, Wei Hu and Jason D. Lee  “Near-Optimal Linear Regression under Distribution Shift”  In _International Conference on Machine Learning (ICML)_ , 2021
  * [Lia+23] Weixin Liang, Yining Mao, Yongchan Kwon, Xinyu Yang and James Y. Zou  “Accuracy on the Curve: On the Nonlinear Correlation of ML Performance Between Data Subpopulations”  In _International Conference on Machine Learning (ICML)_ , 2023
  * [MPW23] Cong Ma, Reese Pathak and Martin J. Wainwright  “Optimally tackling covariate shift in RKHS-based nonparametric regression”  In _Annals of Statistics_ 51.2, 2023, pp. 738–761
  * [Mal+22] Neil Mallinar, James Simon, Amirhesam Abedsoltan, Parthe Pandit, Mikhail Belkin and Preetum Nakkiran  “Benign, Tempered, or Catastrophic: Toward a Refined Taxonomy of Overfitting”  In _Conference on Neural Information Processing Systems (NeurIPS)_ , 2022
  * [Mil+21] John P Miller, Rohan Taori, Aditi Raghunathan, Shiori Sagawa, Pang Wei Koh, Vaishaal Shankar, Percy Liang, Yair Carmon and Ludwig Schmidt  “Accuracy on the Line: on the Strong Correlation Between Out-of-Distribution and In-Distribution Generalization”  In _International Conference on Machine Learning (ICML)_ , 2021
  * [Mut+20] Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian and Anant Sahai  “Harmless interpolation of noisy data in regression”  In _IEEE Journal on Selected Areas in Information Theory_ 1.1, 2020, pp. 67–83
  * [Ogl+22] Dino Oglic, Zoran Cvetkovic, Peter Sollich, Steve Renals and Bin Yu  “Towards Robust Waveform-Based Acoustic Models”  In _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ 30, 2022, pp. 1977–1992
  * [PMW22] Reese Pathak, Cong Ma and Martin Wainwright  “A new similarity measure for covariate shift with applications to nonparametric regression”  In _International Conference on Machine Learning (ICML)_ , 2022
  * [RZ19] Alexander Rakhlin and Xiyu Zhai  “Consistency of Interpolation with Laplace Kernels is a High-Dimensional Phenomenon”  In _Conference on Learning Theory (COLT)_ , 2019
  * [Rec+19] Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt and Vaishaal Shankar  “Do ImageNet Classifiers Generalize to ImageNet?”  In _International Conference on Machine Learning (ICML)_ , 2019
  * [Sim+23] Max Simchowitz, Anurag Ajay, Pulkit Agrawal and Akshay Krishnamurthy  “Statistical Learning under Heterogeneous Distribution Shift”  In _International Conference on Machine Learning (ICML)_ , 2023
  * [TAP21] Nilesh Tripuraneni, Ben Adlam and Jeffrey Pennington  “Overparameterization Improves Robustness to Covariate Shift in High Dimensions”  In _Conference on Neural Information Processing Systems (NeurIPS)_ , 2021
  * [TB23] Alexander Tsigler and Peter L. Bartlet  “Benign overfitting in ridge regression”  In _Journal of Machine Learning Research_ 24.123, 2023, pp. 1–76
  * [Ver18] Roman Vershynin  “High-dimensional probability”  Cambridge University Press, 2018
  * [Wan23] Kaizheng Wang  “Pseudo-Labeling for Kernel Ridge Regression under Covariate Shift”  In _Preprint, arXiv:2302.10160_ , 2023
  * [Wan+22] Ke Alexander Wang, Niladri S Chatterji, Saminul Haque and Tatsunori Hashimoto  “Is Importance Weighting Incompatible with Interpolating Classifiers?”  In _International Conference on Learning Representations (ICLR)_ , 2022
  * [Wen+22] F. Wenzel, Andrea Dittadi, Peter Gehler, Carl-Johann Simon-Gabriel, Max Horn, Dominik Zietlow, David Kernert, Chris Russell, Thomas Brox, Bernt Schiele, Bernhard Scholkopf and Francesco Locatello  “Assaying Out-Of-Distribution Generalization in Transfer Learning”  In _Conference on Neural Information Processing Systems (NeurIPS)_ , 2022
  * [Xu+24] Zhiwei Xu, Yutong Wang, Spencer Frei, Gal Vardi and Wei Hu  “Benign Overfitting and Grokking in ReLU Networks for XOR Cluster Data”  In _International Conference on Learning Representations (ICLR)_ , 2024
  * [Zha+17] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht and Oriol Vinyals  “Understanding deep learning requires rethinking generalization”  In _International Conference on Learning Representations (ICLR)_ , 2017

##  Appendix A Formal assumptions

######  Definition 4 (Linear regression under distribution shift).

We consider a training dataset comprised of $n$ i.i.d. pairs
$(\bm{x}^{i},y^{i})_{i=1}^{n}\sim\mathcal{D}_{\mathsf{s}}^{n}$ concatenated
into a data matrix $X\in\mathbb{R}^{n\times p}$ and a response vector
$\bm{y}_{\mathsf{s}}\in\mathbb{R}^{n}$. In the overparameterized setting,
$p>n$ meaning we have more input features than training samples.

We define

  1. 1.

the covariance matrix
$\Sigma_{\mathsf{s}}=\operatorname*{\mathbb{E}}_{\mathcal{D}_{\mathsf{s}}}[\bm{x}\bm{x}^{\top}]$,

  2. 2.

the optimal parameter vector $\theta_{src}^{*}\in\mathbb{R}^{p}$, satisfying

$\operatorname*{\mathbb{E}}_{\mathcal{D}_{\mathsf{s}}}\big{[}(y-x^{\top}\theta^{*}_{src})^{2}\big{]}=\textrm{min}_{\theta}\operatorname*{\mathbb{E}}_{\mathcal{D}_{\mathsf{s}}}\big{[}(y-x^{\top}\theta)^{2}\big{]}.$

We test on the distribution $\mathcal{D}_{\mathsf{t}}$ with
$\Sigma_{\mathsf{t}}$ and ${\theta_{\mathsf{t}}^{*}}$ defined in the same way.
We assume

  1. 1.

(centered rows)
$\operatorname*{\mathbb{E}}_{\mathcal{D}_{\mathsf{s}}}[\bm{x}]=0;$

  2. 2.

(well-specified - source) For $(X,\bm{y})\subseteq\mathcal{D}_{\mathsf{s}}$,
$\bm{y}=X{\theta_{\mathsf{s}}^{*}}+\bm{\varepsilon}_{\mathsf{s}}$. We assume
that the components of the source noise vector $\bm{\varepsilon}_{\mathsf{s}}$
are i.i.d. centered random variables with positive variance
$v_{\varepsilon_{s}^{2}}$ and that
$\operatorname*{\mathbb{E}}_{\mathcal{D}_{\mathsf{s}}}[y|x]=x^{T}{\theta_{\mathsf{s}}^{*}}$;

  3. 3.

(well-specified - target) For $(X,\bm{y})\subseteq\mathcal{D}_{\mathsf{t}}$,
$\bm{y}=X{\theta_{\mathsf{t}}^{*}}+\bm{\varepsilon}_{\mathsf{t}}$. We assume
that the components of the target noise vector $\bm{\varepsilon}_{\mathsf{t}}$
are i.i.d. centered random variables with noise variance,
$v_{\varepsilon_{t}^{2}}$, and that
$\operatorname*{\mathbb{E}}_{\mathcal{D}_{\mathsf{t}}}[y|x]=x^{T}{\theta_{\mathsf{t}}^{*}}$;

  4. 4.

(simultaneously diagonalizability) $\Sigma_{\mathsf{s}}$ and
$\Sigma_{\mathsf{t}}$ commute; that is, there exists an orthogonal matrix
$V\in\mathbb{R}^{p}$ such that $V^{\top}\Sigma_{\mathsf{s}}V$ and
$V^{\top}\Sigma_{\mathsf{t}}V$ are both diagonal. This allows us to fix an
orthonormal basis in which we can express the covariance matrices as

$\displaystyle\Sigma_{\mathsf{s}}$
$\displaystyle=\operatorname*{\mathbb{E}}_{x\sim\mathcal{D}_{\mathsf{s}}}[xx^{T}]=\textrm{diag}(\lambda_{1},\lambda_{2},...,\lambda_{p}),$
$\displaystyle\Sigma_{\mathsf{t}}$
$\displaystyle=\operatorname*{\mathbb{E}}_{x\sim\mathcal{D}_{\mathsf{t}}}[xx^{T}]=\textrm{diag}(\tilde{\lambda}_{1},\tilde{\lambda}_{2},...,\tilde{\lambda}_{p}),$

where the source eigenvalues are a non-increasing sequence,
$\lambda_{1}\geq\lambda_{2}\cdots\geq\lambda_{p}$. Note that we do not require
the target eigenvalues to be a non-increasing sequence, however we require
that $\tilde{\lambda_{i}}\lambda_{i}\geq 0$ for all $i$;

  5. 5.

(subgaussianity) the whitened data matrix, denoted
$Z=X\Sigma_{\mathsf{s}}^{-1/2}$, has centered i.i.d. row vectors with
independent coordinates. We assume that the rows are subgaussian with
subgaussian norm $\sigma_{x}$; that is, for all $\gamma\in\mathbb{R}^{p},$

$\operatorname*{\mathbb{E}}[\exp(\gamma^{\top}z)]\leq\exp(\sigma_{x}^{2}||\gamma||^{2}/2).$

##  Appendix B Key results from prior work and technical lemmas

For ease on the reader, we replicate some key lemma statements from [Bar+20]
and [TB23] and provide new lemmas and corollaries that we use in our work.

Recall that $\rho_{k}=\frac{1}{n\lambda_{k+1}}\sum_{i>k}\lambda_{i}$,
$X\in\mathbb{R}^{n\times p}$, and $\Sigma_{\mathsf{s}}\in\mathbb{R}^{p\times
p}=\text{diag}(\lambda_{1},\cdots,\lambda_{p})$. Let
$X_{0:k}\in\mathbb{R}^{n\times k}$ denote the matrix comprised of the first
$k$ feature columns. Similarly, $X_{k:p}\in\mathbb{R}^{n\times(p-k)}$ denote
the matrix of the last $p-k$ feature columns. The Gram matrix of the data,
denoted here by

$\displaystyle A=XX^{T},$

plays a central role in the investigation of high-dimensional linear
regression. Analogous to the above, we express
$A_{0:k}=X_{0:k}X_{0:k}^{T}\in\mathbb{R}^{n\times n}$ and similarly for
$A_{k:p}\in\mathbb{R}^{n\times n}$.

Letting $Z=X\Sigma_{\mathsf{s}}^{-1/2}\in\mathbb{R}^{n\times p}$ and denoting
the independent column vectors of $Z$ by $z_{i}\in\mathbb{R}^{n}$, we have the
following expressions:

$\displaystyle A=\sum_{i}\lambda_{i}z_{i}z_{i}^{T},$ $\displaystyle
A_{-i}=\sum_{j\neq i}\lambda_{j}z_{j}z_{j}^{T},$ $\displaystyle
A_{k}=\sum_{i>k}\lambda_{i}z_{i}z_{i}^{T}.$

The following lemma from [Bar+20] is key in controlling the largest and
smallest eigenvalues of the data Gram matrix and its variants $A_{-i}$ and
$A_{k}$. Importantly, it also shows that if the energy in the bottom $p-k$
components of the covariance matrix is sufficiently large ($\rho_{k}$ is lower
bounded by a constant), then the largest and smallest eigenvalues of $A_{k}$
are equal up to constants.

######  Lemma B.1 (Lemma 5 from [Bar+20]).

There are constants $b,c\geq 1$ such that for any $k\geq 0$, with probability
at least $1-2e^{-n/c}$,

  1. 1.

for all $i\geq 1$,

$\mu_{k+1}(A_{-i})\leq\mu_{k+1}(A)\leq\mu_{1}(A_{k})\leq
c\Bigg{(}\sum_{j>k}\lambda_{j}+\lambda_{k+1}n\Bigg{)},$

  2. 2.

for all $1\leq i\leq k$,

$\mu_{n}(A)\geq\mu_{n}(A_{-i})\geq\mu_{n}(A_{k})\geq\frac{1}{c}\sum_{j>k}\lambda_{j}-c\lambda_{k+1}n,$

  3. 3.

if $\rho_{k}\geq b$, then

$\frac{1}{c}\lambda_{k+1}\rho_{k}n\leq\mu_{n}(A_{k})\leq\mu_{1}(A_{k})\leq
c\lambda_{k+1}\rho_{k}n.$

A consequence of the prior eigenvalue bounds is that when $\rho_{k}$ is lower
bounded by a constant, the condition number of $A_{k}$ is upper bounded by a
constant. Therefore even as problem parameters such as training sample size
and input dimension grow to $\infty$, $A_{k}$ is still well-conditioned. This
is important as non-benign overfitting occurs when the condition number bound
on $A_{k}$ grows with problem parameters. This would happen if the lower bound
on the smallest eigenvalue of $A_{k}$ decays to zero too quickly which would
cause the condition number of $A_{k}$ to diverge. If this occurs then the
excess risk of the MNI would be lower bounded. This is shown for the in-
distribution case in [Bar+20].

######  Corollary B.2.

Following from Lemma B.1, there are constants $b,c\geq 1$ such that for any
$k\geq 0$, with probability at least $1-2e^{-n/c}$, if $\rho_{k}\geq b$ then

$\frac{\mu_{1}(A_{k})}{\mu_{n}(A_{k})}\leq c^{2}$ (14)

which is the equivalent of the assumption CondNum$(k,2e^{-n/c},c^{2})$ as
defined in [TB23].

The following definition and lemma omit all references to NonCritReg and the
ridge parameter in [TB23].

######  Definition 5 (StableLowerEig$(k,\delta,L)$ from [TB23]).

Assume that for any $j\in\\{1,2,\cdots,p\\}$ with probability (separate for
every $j$) at least $1-\delta$,

$\mu_{n}(A_{-j})\geq\mu_{n}(\operatorname*{\mathbb{E}}A_{k})/L=(\sum_{i>k}\lambda_{i})/L.$
(15)

We now state key assumptions that are necessary in order to obtain an explicit
bias lower bound. Exchangeable coordinates (ExchCoord) is a weaker assumption
than independent components of the data vector. It is used in [TB23] instead
of independent components. We assume that components of $Z$ are independent
and so we immediately satisfy the ExchCoord, which we define here.

######  Definition 6 (ExchCoord).

Assume the sequence of coordinates of $\Sigma_{\mathsf{s}}^{-1/2}x$, for any
$x\in X$, is exchangable (any deterministic permutation of the coordinates of
whitened data vectors doesn’t change their distribution).

The PriorSigns assumption is necessary to obtain lower bounds on the bias
term. It allows us to use bounds on the expectation of a quadratic form,
$\operatorname*{\mathbb{E}}_{v}[v^{T}Mv]$, in order to separately analyze the
contributions of $v$ and $M$. As the bias takes the form
${\theta_{\mathsf{s}}^{*}}^{T}(I-X^{T}A^{-1}X)\Sigma_{\mathsf{t}}(I-X^{T}A^{-1}X){\theta_{\mathsf{s}}^{*}}$
we see that such a bound would separate the contributions of the model from
that of data-dependent matrix expressions.

######  Definition 7 (PriorSigns).

Assume that $\theta^{*}$ is sampled from a prior distribution in the following
way: one starts with vector $\overline{\theta}$ and flips signs of all its
coordinates with probability 0.5 independently.

Under PriorSigns, the random model vector is obtained by flipping signs on the
components of the ground-truth model vector. This does not affect our bounds
as we see in Theorem 3.2 that our bias lower bound only relies on squared
components of the random model vector which are equivalent to the squared
components of the ground truth model.

An important consequence of having a bounded condition number and independent
coordinates is that with high probability the smallest eigenvalue of $A_{-i}$
for all $i\geq 1$ is lower bounded by $n\lambda_{k+1}\rho_{k}$ up to
constants. These assumptions allow [Bar+20] to prove Lemma B.1, which in turn
allows us to derive the StableLowerEig condition. This is a simple consequence
of B.1 and we provide details here for completeness.

######  Corollary B.3 (Our variant of StableLowerEig from [TB23]).

For all $i\geq 1$, with probability at least $1-2e^{-n/c_{2}}$

$\mu_{n}(A_{-i})\geq\frac{1}{c_{2}}\mu_{n}(\operatorname*{\mathbb{E}}A_{k})=\frac{1}{c_{2}}\sum_{j>k}\lambda_{j}.$

###### Proof.

By Lemma B.1, for some absolute constant $c_{1}\geq 1$ with probability at
least $1-2e^{-n/c_{1}}$

$\mu_{n}(A_{k})\geq\frac{1}{c_{1}}\sum_{i>k}\lambda_{i}-c_{1}\lambda_{k+1}n.$

The assumption $\rho_{k}\geq b$ for some $b\geq 1$ gives us

$\displaystyle\frac{1}{c_{1}}\sum_{i>k}\lambda_{i}-c_{1}\lambda_{k+1}n$
$\displaystyle=\frac{1}{c_{1}}\lambda_{k+1}n\rho_{k}-c_{1}\lambda_{k+1}n$
$\displaystyle\geq\bigg{(}\frac{1}{c_{1}}-\frac{c_{1}}{b}\bigg{)}\lambda_{k+1}n\rho_{k}$
$\displaystyle=\bigg{(}\frac{1}{c_{1}}-\frac{c_{1}}{b}\bigg{)}\sum_{i>k}\lambda_{i}.$

Choosing $b>c_{1}^{2}$ and $c_{2}=\max\\{c_{1},(1/c_{1}-c_{1}/b)^{-1}\\}$, we
get that with probability at least $1-2e^{-n/c_{2}}$

$\mu_{n}(A_{k})\geq\frac{1}{c_{2}}\sum_{i>k}\lambda_{i}.$

The next step is to extend this result to $A_{-i}$ for all $i$.

For $i\leq k$, observe that $A_{-i}\succeq A_{k}$ gives us
$\mu_{n}(A_{-i})\geq\mu_{n}(A_{k}).$ For the case of $i>k,$ we have

$\displaystyle A_{-i}$ $\displaystyle=\sum_{j\neq
i}\lambda_{j}z_{j}z_{j}^{\top}$ $\displaystyle=\sum_{j\leq
k}\lambda_{j}z_{j}z_{j}^{\top}+\sum_{j>k,j\neq i}\lambda_{j}z_{j}z_{j}^{\top}$
$\displaystyle\succeq\lambda_{1}z_{1}z_{1}^{\top}+\sum_{j>k,j\neq
i}\lambda_{j}z_{j}z_{j}^{\top}$
$\displaystyle\succeq\lambda_{i}z_{1}z_{1}^{\top}+\sum_{j>k,j\neq
i}\lambda_{j}z_{j}z_{j}^{\top}.$

We assume that the features are independent and $z_{i}$ is centered and
whitened, so $\lambda_{i}z_{1}z_{1}^{\top}+\sum_{j>k,j\neq
i}\lambda_{j}z_{j}z_{j}^{\top}$ has the same distribution as
$A_{k}=\sum_{j>k}\lambda_{j}z_{j}z_{j}^{\top}$. Therefore,

$\displaystyle\mathbb{P}\Bigg{(}\mu_{n}(A_{-i})\geq\frac{1}{c_{2}}\sum_{i>k}\lambda_{i}\Bigg{)}$
$\displaystyle\geq$
$\displaystyle\mathbb{P}\Bigg{(}\mu_{n}\Bigg{(}\lambda_{i}z_{1}z_{1}^{\top}+\sum_{j>k,j\neq
i}\lambda_{j}z_{j}z_{j}^{\top}\Bigg{)}\geq\frac{1}{c_{2}}\sum_{i>k}\lambda_{i}\Bigg{)}$
$\displaystyle=$
$\displaystyle\mathbb{P}\Bigg{(}\mu_{n}(A_{k})\geq\frac{1}{c_{2}}\sum_{i>k}\lambda_{i}\Bigg{)}$
$\displaystyle\geq$ $\displaystyle 1-2e^{-n/c}.$

∎

The following corollaries provide high-probability bounds on random
subgaussian vectors with independent coordinates.

######  Corollary B.4 (Corollary 1 from [Bar+20]).

There is a universal constant $c$ such that for any centered random vector
$z\in\mathbb{R}^{n}$ with independent $\sigma^{2}$-subgaussian coordinates
with unit variances, any random subspace $\mathscr{L}$ of $\mathbb{R}^{n}$ of
codimension $k$ that is independent of $z$, and any $t>0$, with probability at
least $1-3e^{-t}$,

$\displaystyle\|z\|^{2}$ $\displaystyle\leq n+c\sigma^{2}(t+\sqrt{nt}),$
$\displaystyle\|\Pi_{\mathscr{L}}z\|^{2}$ $\displaystyle\geq
n-c\sigma^{2}(k+t+\sqrt{nt}),$

where $\Pi_{\mathscr{L}}$ is the orthogonal projection on $\mathscr{L}$.

In our proofs, we will need to control the norm of $z_{i}$ for all $i\leq p$
on the same high-probability event. In these cases we need to apply a union
bound over the events in the summation. The following corollary shows how to
invoke a union bound over $\ell$ of these events in such a way that the
probability over the union of all such events holds with high probability that
depends $n$.

######  Corollary B.5.

There is a universal constant $c$ as defined in Corollary B.4. Let
$z\in\mathbb{R}^{n}$ be a centered random vector with $\sigma^{2}$-subgaussian
coordinates and unit variances. Let $\mathscr{L}$ be a random subspace of
$\mathbb{R}^{n}$ of codimension $k$ that is independent of $z$.

For $0<t<n/c_{0}$ and $k\in(0,n/c_{1})$ for $c_{1}>c_{0}$ with $c_{0}$
sufficiently large, with probability $1-3e^{-t}$,

$\displaystyle\|z\|^{2}$ $\displaystyle\leq c_{2}n$
$\displaystyle\|\Pi_{\mathscr{L}}z\|^{2}$ $\displaystyle\geq n/c_{3}$

where $c_{2},c_{3}$ only depends on $c,c_{0},\sigma$.

We obtain a union bound over the intersection of $\ell$ of these events so
long as $\ln(\ell)\leq n/c_{0}\Rightarrow\ell\leq e^{n/c_{0}}$. Then for
$k\in(0,n/c_{1})$ for $c_{1}>c_{0}$ with $c_{0}$ sufficiently large, if
$\ell\leq e^{n/c_{0}}$, with probability at least $1-3e^{-n/c_{0}}$, $\ell$ of
the above events independently hold.

###### Proof.

Let Corollary B.4 hold with universal constant $c$. Then, with probability
$1-3e^{-t}$ for $t>0$,

$\displaystyle\|z\|^{2}$ $\displaystyle\leq n+c\sigma^{2}(t+\sqrt{nt})$
$\displaystyle\|\Pi_{\mathscr{L}}z\|^{2}$ $\displaystyle\geq
n-c\sigma^{2}(k+t+\sqrt{nt}).$

Let $t\leq\frac{n}{c_{0}}$. Then we have that,

$\displaystyle-\frac{n}{c_{0}}\leq-t\qquad-\frac{n}{\sqrt{c_{0}}}\leq-\sqrt{nt}.$

Plugging in for $\|z\|^{2}$,

$\displaystyle\|z\|^{2}$ $\displaystyle\leq n+c\sigma^{2}(t+\sqrt{nt})$
$\displaystyle\leq n+c\sigma^{2}(\frac{n}{c_{0}}+\frac{n}{\sqrt{c_{0}}})$
$\displaystyle=n(1+c\sigma^{2}(c_{0}^{-1}+c_{0}^{-1/2}))$
$\displaystyle=c_{1}n$

for $c_{1}$ only dependent on $c,c_{0},\sigma$. Now, plugging in for
$\|\Pi_{\mathscr{L}}z\|^{2}$,

$\displaystyle\|\Pi_{\mathscr{L}}z\|^{2}$ $\displaystyle\geq
n-c\sigma^{2}(k+t+\sqrt{nt})$ $\displaystyle\geq
n-c\sigma^{2}(k+\frac{n}{c_{0}}+\frac{n}{\sqrt{c_{0}}})$
$\displaystyle=n(1-c\sigma^{2}(\frac{k}{n}+c_{0}^{-1}+c_{0}^{-1/2})).$

Let $k<\frac{n}{c_{2}}$ for $c_{2}>c_{0}$. Then it is clear that
$-\frac{k}{n}>-\frac{1}{c_{2}}$ and,

$\displaystyle n(1-c\sigma^{2}(\frac{k}{n}+c_{0}^{-1}+c_{0}^{-1/2}))$
$\displaystyle\geq n(1-c\sigma^{2}(c_{2}^{-1}+c_{0}^{-1}+c_{0}^{-1/2}))$
$\displaystyle=n/c_{3}$

for constant $c_{3}$ that only depends on $c,\sigma^{2},c_{0}$. We finally
require that $1-c\sigma^{2}(c_{1}^{-1}+c_{0}^{-1}+c_{0}^{-1/2})>0$ which we
can achieve by taking $c_{0}$ sufficiently large.

We now proceed to bound the union of $\ell$ of the complement events, in order
to obtain a bound over the intersection of $\ell$ of these events.

For multiple $z_{i}$’s, define by $A_{i}$ the events shown above, that
$\|z_{i}\|^{2}\leq c_{2}n$ and $\|\Pi_{\mathscr{L}_{i}}z_{i}\|^{2}\geq
n/c_{3}$ where $z_{i}$ and $\mathscr{L}_{i}$ are defined analogous to
$z,\mathscr{L}$ above. Then

$\displaystyle P(\cup_{i=1}^{\ell}(A_{i})^{c})$
$\displaystyle\leq\sum_{i=1}^{\ell}P((A_{i})^{c})$
$\displaystyle\leq\sum_{i=1}^{\ell}3e^{-t}$ $\displaystyle=3\ell e^{-t}.$

Then $P(\cap_{i=1}^{\ell}A_{i})\geq 1-3\ell e^{-t}$. Observing that $3\ell
e^{-t}=3e^{\ln(\ell)}e^{-t}=3e^{-t+\ln(\ell)}=3e^{-(t-\ln(\ell))}$ we can set
the per-event $t$ accordingly and obtain the necessary bound. We want
$0<t-\ln(\ell)\leq n/c_{0}$ to complete the bound. Therefore, we need that,
per-event, $\ln(\ell)<t\leq n/c_{0}+\ln(\ell)$. If $\ln(\ell)\leq n/c_{0}$
then this reduces to needing $\ln(\ell)<t\leq 2n/c_{0}$. Since each event is
defined for $t\in(0,n/c_{0}]$ the union bound proof is complete by taking
$t=n/c_{0}$ and requiring that $\ln(\ell)\leq n/c_{0}$.

∎

The following lemma is necessary in order to extend a summation over random
variables, each lower bounded by a real number with equal probability, to a
unified lower bound over the entire summation.

######  Lemma B.6 (Lemma 9 from [Bar+20]).

Suppose $n\leq\infty$ and $\\{\eta_{i}\\}_{i=1}^{n}$ is a sequence of non-
negative random variables, $\\{t_{i}\\}_{i=1}^{n}$ is a sequence of non-
negative real numbers (at least one of which is strictly positive) such that
for some $\delta\in(0,1)$ and any $i\leq n$, $P(\eta_{i}>t_{i})\geq 1-\delta$.
Then,

$\displaystyle
P\left(\sum_{i=1}^{n}\eta_{i}\geq\frac{1}{2}\sum_{i=1}^{n}t_{i}\right)\geq
1-2\delta.$

We now provide a minor generalization of Corollary S.6 in [Bar+20] that comes
from replacing $a_{1}$ in a non-increasing sequence of non-negative numbers
$\\{a_{i}\\}_{i=1}^{p}$ with $\max_{i}a_{i}$ and only requiring that
$\\{a_{i}\\}_{i=1}^{p}$ is a sequence of non-negative numbers.

######  Corollary B.7.

There is a universal constant $c$ such that for any sequence
$\\{a_{i}\\}_{i=1}^{p}$ of non-negative numbers such that
$\sum_{i=1}^{p}a_{i}<\infty$, and any independent, centered,
$\sigma$-subexponential random variables $\\{\xi_{i}\\}_{i=1}^{p}$, and any
$x>0$, with probability at least $1-2e^{-cx}$,

$\displaystyle|\sum_{i}a_{i}\xi_{i}|\leq\sigma\max\left(x\max_{i}a_{i},\sqrt{x\sum_{i=1}^{p}a_{i}^{2}}\right).$

Lastly, the following identity will allow us to use the PriorSigns assumption
to derive a new form for the bias term, which will be used for the proof of
the lower bound.

######  Lemma B.8 (Identity for expectation of a quadratic form).

Assume $M\in\mathbb{R}^{p\times p}$ is a symmetric matrix. For a random vector
$x\in\mathbb{R}^{p}$ with mean $\operatorname*{\mathbb{E}}[x]$ and covariance
$\mathrm{Cov}(x)$,

$\displaystyle\operatorname*{\mathbb{E}}_{x}[x^{T}Mx]=\operatorname*{\mathbb{E}}[x]^{T}M\operatorname*{\mathbb{E}}[x]+\mathrm{tr}(M\textrm{Cov}(x)).$

###### Proof.

$\displaystyle\operatorname*{\mathbb{E}}_{x}[x^{T}Mx]$
$\displaystyle=\operatorname*{\mathbb{E}}[\mathrm{tr}(x^{T}Mx)]$
$\displaystyle=\operatorname*{\mathbb{E}}[\mathrm{tr}(Mxx^{T})]$
$\displaystyle=\mathrm{tr}(M\operatorname*{\mathbb{E}}[xx^{T}])$
$\displaystyle=\mathrm{tr}(M\textrm{Cov}(x)+M\operatorname*{\mathbb{E}}[x]\operatorname*{\mathbb{E}}[x]^{T})$
$\displaystyle=\mathrm{tr}(M\textrm{Cov}(x))+\mathrm{tr}(\operatorname*{\mathbb{E}}[x]M\operatorname*{\mathbb{E}}[x]^{T})$
$\displaystyle=\mathrm{tr}(M\textrm{Cov}(x))+\operatorname*{\mathbb{E}}[x]M\operatorname*{\mathbb{E}}[x]^{T}.$

∎

##  Appendix C Proof of excess risk bound

We start by restating Theorem 2.1. See 2.1

###### Proof.

Let us begin by noting that the excess risk of any $\theta$ is given by,

$\displaystyle R(\theta)$
$\displaystyle=\operatorname*{\mathbb{E}}_{(x,y)\sim\mathcal{D}_{\mathsf{t}}}\left[\left(y-x^{\top}\theta\right)^{2}\right]-\operatorname*{\mathbb{E}}_{(x,y)\sim\mathcal{D}_{\mathsf{t}}}\left[\left(y-x^{\top}{\theta_{\mathsf{t}}^{*}}\right)^{2}\right]$
$\displaystyle=\operatorname*{\mathbb{E}}_{(x,y)\sim\mathcal{D}_{\mathsf{t}}}\left[\left(y-x^{\top}{\theta_{\mathsf{t}}^{*}}+x^{\top}{\theta_{\mathsf{t}}^{*}}-x^{\top}\theta\right)^{2}\right]-\operatorname*{\mathbb{E}}_{(x,y)\sim\mathcal{D}_{\mathsf{t}}}\left[\left(y-x^{\top}{\theta_{\mathsf{t}}^{*}}\right)^{2}\right]$
$\displaystyle=\operatorname*{\mathbb{E}}_{(x,y)\sim\mathcal{D}_{\mathsf{t}}}\left[\left(x^{\top}{\theta_{\mathsf{t}}^{*}}-x^{\top}\theta\right)^{2}\right]+2\operatorname*{\mathbb{E}}_{(x,y)\sim\mathcal{D}_{\mathsf{t}}}\left[\left(y-x^{\top}{\theta_{\mathsf{t}}^{*}}\right)\left(x^{\top}{\theta_{\mathsf{t}}^{*}}-x^{\top}\theta\right)\right]$
$\displaystyle\overset{(i)}{=}\operatorname*{\mathbb{E}}_{x\sim\mathcal{D}_{\mathsf{t}}}\left[\left(x^{\top}{\theta_{\mathsf{t}}^{*}}-x^{\top}\theta\right)^{2}\right].$
(16)

Equality $(i)$ uses that, conditional on $x$,
$y-x^{\top}{\theta_{\mathsf{t}}^{*}}|x$ is mean-zero, which is given in
Assumption 3 (well-specified - target). So that

$\operatorname*{\mathbb{E}}_{(x,y)\sim\mathcal{D}_{\mathsf{t}}}\left[\left(y-x^{\top}{\theta_{\mathsf{t}}^{*}}\right)\left(x^{\top}{\theta_{\mathsf{t}}^{*}}-x^{\top}\theta\right)\right]=\operatorname*{\mathbb{E}}\left[\left(x^{\top}{\theta_{\mathsf{t}}^{*}}-x^{\top}\theta\right)\operatorname*{\mathbb{E}}\left[\left(y-x^{\top}{\theta_{\mathsf{t}}^{*}}\right)\big{|}x\right]\right]=0.$

We now note that the source-data MNI can be decomposed as follows,

$\displaystyle\widehat{\theta}(\bm{y}_{\mathsf{s}})$
$\displaystyle=X^{\top}(X_{\mathsf{s}}X_{\mathsf{s}}^{\top})^{-1}\bm{y}_{\mathsf{s}}$
$\displaystyle=X^{\top}(X_{\mathsf{s}}X_{\mathsf{s}}^{\top})^{-1}(X{\theta_{\mathsf{s}}^{*}}+\bm{\varepsilon}_{\mathsf{s}})$
$\displaystyle=\widehat{\theta}(X{\theta_{\mathsf{s}}^{*}})+\widehat{\theta}(\bm{\varepsilon}_{\mathsf{s}})$

We can thus continue from 16 to characterize the excess risk of the source-
data MNI as

$\displaystyle R(\widehat{\theta}(\bm{y}_{\mathsf{s}}))$
$\displaystyle=\operatorname*{\mathbb{E}}_{x\sim\mathcal{D}_{\mathsf{t}}}\left[\left(x^{\top}{\theta_{\mathsf{t}}^{*}}-x^{\top}\widehat{\theta}(\bm{y}_{\mathsf{s}})\right)^{2}\right]$
$\displaystyle=\operatorname*{\mathbb{E}}_{x\sim\mathcal{D}_{\mathsf{t}}}\left[\left(x^{\top}{\theta_{\mathsf{t}}^{*}}-x^{\top}(\widehat{\theta}(X{\theta_{\mathsf{s}}^{*}})+\widehat{\theta}(\bm{\varepsilon}_{\mathsf{s}}))\right)^{2}\right]$
$\displaystyle=\operatorname*{\mathbb{E}}_{x\sim\mathcal{D}_{\mathsf{t}}}\left[\left(x^{\top}({\theta_{\mathsf{t}}^{*}}-\widehat{\theta}(X{\theta_{\mathsf{s}}^{*}}))-x^{\top}\widehat{\theta}(\bm{\varepsilon}_{\mathsf{s}})\right)^{2}\right]$
$\displaystyle\overset{(i)}{\leq}\operatorname*{\mathbb{E}}_{x\sim\mathcal{D}_{\mathsf{t}}}\left[2\left(x^{\top}({\theta_{\mathsf{t}}^{*}}-\widehat{\theta}(X{\theta_{\mathsf{s}}^{*}}))\right)^{2}+2\left(x^{\top}\widehat{\theta}(\bm{\varepsilon}_{\mathsf{s}})\right)^{2}\right]$
$\displaystyle=\operatorname*{\mathbb{E}}_{x\sim\mathcal{D}_{\mathsf{t}}}\left[2\left(x^{\top}({\theta_{\mathsf{t}}^{*}}-{\theta_{\mathsf{s}}^{*}}+{\theta_{\mathsf{s}}^{*}}-\widehat{\theta}(X{\theta_{\mathsf{s}}^{*}}))\right)^{2}+2\left(x^{\top}\widehat{\theta}(\bm{\varepsilon}_{\mathsf{s}})\right)^{2}\right]$
$\displaystyle\overset{(ii)}{\leq}\operatorname*{\mathbb{E}}_{x\sim\mathcal{D}_{\mathsf{t}}}\left[4\left(x^{\top}({\theta_{\mathsf{t}}^{*}}-{\theta_{\mathsf{s}}^{*}})\right)^{2}+4\left(x^{\top}({\theta_{\mathsf{s}}^{*}}-\widehat{\theta}(X{\theta_{\mathsf{s}}^{*}}))\right)^{2}+2\left(x^{\top}\widehat{\theta}(\bm{\varepsilon}_{\mathsf{s}})\right)^{2}\right].$
(17)

In inequalities $(i)$ and $(ii)$, we have used Young’s inequality, which
implies $(a-b)^{2}\leq 2(a-c)^{2}+2(b-c)^{2}$ for any $a,b,c\in\mathbb{R}$.
Recalling that

$\|x\|_{M}^{2}:=x^{\top}Mx,$

it is apparent that the first term is just the weighted distance between the
source and target vectors,

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim\mathcal{D}_{\mathsf{t}}}\left[\left(x^{\top}({\theta_{\mathsf{t}}^{*}}-{\theta_{\mathsf{s}}^{*}})\right)^{2}\right]=({\theta_{\mathsf{t}}^{*}}-{\theta_{\mathsf{s}}^{*}})^{\top}\operatorname*{\mathbb{E}}_{x\sim\mathcal{D}_{\mathsf{t}}}\left[xx^{\top}\right]({\theta_{\mathsf{t}}^{*}}-{\theta_{\mathsf{s}}^{*}})=\|{\theta_{\mathsf{s}}^{*}}-{\theta_{\mathsf{t}}^{*}}\|_{\Sigma_{\mathsf{t}}}^{2}.$
(18)

The second term looks quite similar to the bias term, $B$, in [Bar+20] and
[TB23].

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim\mathcal{D}_{\mathsf{t}}}\left[\left(x^{\top}({\theta_{\mathsf{s}}^{*}}-\widehat{\theta}(X{\theta_{\mathsf{s}}^{*}}))\right)^{2}\right]$
$\displaystyle\qquad=\left({\theta_{\mathsf{s}}^{*}}-\widehat{\theta}\left(X{\theta_{\mathsf{s}}^{*}}\right)\right)\operatorname*{\mathbb{E}}_{x\sim\mathcal{D}_{\mathsf{t}}}[xx^{\top}]\left({\theta_{\mathsf{s}}^{*}}-\widehat{\theta}\left(X{\theta_{\mathsf{s}}^{*}}\right)\right)$
$\displaystyle\qquad=\|{\theta_{\mathsf{s}}^{*}}-\widehat{\theta}\left(X{\theta_{\mathsf{s}}^{*}}\right)\|_{\Sigma_{\mathsf{t}}}^{2}.$
(19)

The key difference with the standard supervised setting is that now the
quantitiy in the middle is $\Sigma_{\mathsf{t}}$, not $\Sigma_{\mathsf{s}}$.
Equivalently, the norm on
${\theta_{\mathsf{s}}^{*}}-\widehat{\theta}(X{\theta_{\mathsf{s}}^{*}})$ is
induced by $\Sigma_{\mathsf{t}}$ rather than $\Sigma_{\mathsf{s}}$.

And finally, the third term is similar to the variance term, $C$, in [Bar+20]:

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim\mathcal{D}_{\mathsf{t}}}\left[\left(x^{\top}\widehat{\theta}(\bm{\varepsilon}_{\mathsf{s}})\right)^{2}\right]$
$\displaystyle=\widehat{\theta}(\bm{\varepsilon}_{\mathsf{s}})^{\top}\operatorname*{\mathbb{E}}_{x\sim\mathcal{D}_{\mathsf{t}}}[xx^{\top}]\widehat{\theta}(\bm{\varepsilon}_{\mathsf{s}})$
$\displaystyle=\widehat{\theta}(\bm{\varepsilon}_{\mathsf{s}})^{\top}\Sigma_{\mathsf{t}}\widehat{\theta}(\bm{\varepsilon}_{\mathsf{s}})$
$\displaystyle=\|\widehat{\theta}(\bm{\varepsilon}_{\mathsf{s}})\|_{\Sigma_{\mathsf{t}}}^{2}.$
(20)

As in the bias term, the only difference is that the middle term is
$\Sigma_{\mathsf{t}}$ rather than $\Sigma_{\mathsf{s}}$. Equivalently, the
norm on $\widehat{\theta}(\bm{\varepsilon}_{\mathsf{s}})$ is induced by
$\Sigma_{\mathsf{t}}$ rather than $\Sigma_{\mathsf{s}}$.

Putting it all together, we get the following upper bound for the excess risk
of the minimum-norm interpolator on the training data,

$\displaystyle R(\widehat{\theta}(\bm{y}_{\mathsf{s}}))$ $\displaystyle\leq
4\|{\theta_{\mathsf{s}}^{*}}-{\theta_{\mathsf{t}}^{*}}\|_{\Sigma_{\mathsf{t}}}^{2}+4\|{\theta_{\mathsf{s}}^{*}}-\widehat{\theta}(X{\theta_{\mathsf{s}}^{*}})\|_{\Sigma_{\mathsf{t}}}^{2}+2\|\widehat{\theta}(\bm{\varepsilon}_{\mathsf{s}})\|_{\Sigma_{\mathsf{t}}}^{2}.$

This completes the upper bound for the risk.

For the lower bound, we have

$\displaystyle\operatorname*{\mathbb{E}}_{\bm{\varepsilon}_{\mathsf{s}}}R(\widehat{\theta}(\bm{y}_{\mathsf{s}}))$
$\displaystyle=\operatorname*{\mathbb{E}}_{\bm{\varepsilon}_{\mathsf{s}},x\sim\mathcal{D}_{\mathsf{t}}}\left[\left(x^{\top}{\theta_{\mathsf{t}}^{*}}-x^{\top}\widehat{\theta}(\bm{y}_{\mathsf{s}})\right)^{2}\right]$
$\displaystyle=\operatorname*{\mathbb{E}}_{\bm{\varepsilon}_{\mathsf{s}},x\sim\mathcal{D}_{\mathsf{t}}}\left[\left(x^{\top}({\theta_{\mathsf{t}}^{*}}-\widehat{\theta}(X{\theta_{\mathsf{s}}^{*}}))-x^{\top}\widehat{\theta}(\bm{\varepsilon}_{\mathsf{s}})\right)^{2}\right]$
$\displaystyle=\operatorname*{\mathbb{E}}_{\bm{\varepsilon}_{\mathsf{s}},x\sim\mathcal{D}_{\mathsf{t}}}\bigg{[}\left(x^{\top}({\theta_{\mathsf{t}}^{*}}-\widehat{\theta}(X{\theta_{\mathsf{s}}^{*}}))\right)^{2}-2\cdot
x^{\top}({\theta_{\mathsf{t}}^{*}}-\widehat{\theta}(X{\theta_{\mathsf{s}}^{*}}))\cdot
x^{\top}\widehat{\theta}(\bm{\varepsilon}_{\mathsf{s}})$
$\displaystyle\qquad+\left(x^{\top}\widehat{\theta}(\bm{\varepsilon}_{\mathsf{s}})\right)^{2}\bigg{]}$
$\displaystyle\overset{(i)}{=}\operatorname*{\mathbb{E}}_{x\sim\mathcal{D}_{\mathsf{t}}}\left[\left(x^{\top}({\theta_{\mathsf{t}}^{*}}-\widehat{\theta}(X{\theta_{\mathsf{s}}^{*}}))\right)^{2}\right]+\operatorname*{\mathbb{E}}_{\bm{\varepsilon}_{\mathsf{s}},x\sim\mathcal{D}_{\mathsf{t}}}\left[\left(x^{\top}\widehat{\theta}(\bm{\varepsilon}_{\mathsf{s}})\right)^{2}\right]$

The equality $(i)$ uses that, conditional on $X$,
$\bm{\varepsilon}_{\mathsf{s}}$ is zero-mean. Note that the second term above
is just
$\operatorname*{\mathbb{E}}_{\bm{\varepsilon}_{\mathsf{s}}}\|\widehat{\theta}(\bm{\varepsilon}_{\mathsf{s}})\|_{\Sigma_{\mathsf{t}}}^{2}$,
so we need only deal with the first term. Adding and subtracting
${\theta_{\mathsf{s}}^{*}}$ inside the square and expanding, we have

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim\mathcal{D}_{\mathsf{t}}}\left[\left(x^{\top}({\theta_{\mathsf{t}}^{*}}-\widehat{\theta}(X{\theta_{\mathsf{s}}^{*}}))\right)^{2}\right]$
$\displaystyle\quad=\operatorname*{\mathbb{E}}_{x\sim\mathcal{D}_{\mathsf{t}}}\left[\left(x^{\top}({\theta_{\mathsf{t}}^{*}}-{\theta_{\mathsf{s}}^{*}})\right)^{2}\right]+\operatorname*{\mathbb{E}}_{x\sim\mathcal{D}_{\mathsf{t}}}\left[\left(x^{\top}({\theta_{\mathsf{s}}^{*}}-\widehat{\theta}(X{\theta_{\mathsf{s}}^{*}}))\right)^{2}\right]$
$\displaystyle\qquad+2\operatorname*{\mathbb{E}}_{x\sim\mathcal{D}_{\mathsf{t}}}\left[({\theta_{\mathsf{t}}^{*}}-{\theta_{\mathsf{s}}^{*}})^{\top}xx^{\top}({\theta_{\mathsf{s}}^{*}}-\widehat{\theta}(X{\theta_{\mathsf{s}}^{*}}))\right]$
$\displaystyle\quad=\|{\theta_{\mathsf{t}}^{*}}-{\theta_{\mathsf{s}}^{*}}\|_{\Sigma_{\mathsf{t}}}^{2}+\|{\theta_{\mathsf{s}}^{*}}-\widehat{\theta}(X{\theta_{\mathsf{s}}^{*}})\|_{\Sigma_{\mathsf{t}}}^{2}+2({\theta_{\mathsf{t}}^{*}}-{\theta_{\mathsf{s}}^{*}})^{\top}\Sigma_{\mathsf{t}}({\theta_{\mathsf{s}}^{*}}-\widehat{\theta}(X{\theta_{\mathsf{s}}^{*}})).$

∎

##  Appendix D Overview of variance and bias proof techniques

The central pillar of both proofs is controlling the eigenvalues of $A_{k}$,
which in turn provides certain bounds on the eigenvalues of $A$ and $A_{-i}$.
A key finding of [Bar+20] is that once $\rho_{k}$ is large enough, all
eigenvalues of $A_{k}$ are identical up to a constant factor. Specifically,

$\displaystyle z^{T}Az\approx n^{2}\lambda_{k+1}\rho_{k},$ $\displaystyle
z^{T}A^{-1}z\approx n(n\lambda_{k+1}\rho_{k})^{-1}.$

###  D.1 Variance

Due to independence between the components of $\bm{\varepsilon}_{\mathsf{s}}$,
the variance term from Eqn. 6 can be expressed as

$\displaystyle V$
$\displaystyle=\operatorname*{\mathbb{E}}_{\varepsilon_{\mathsf{s}}}[V_{\varepsilon_{\mathsf{s}}}/v_{\varepsilon}^{2}]$
$\displaystyle=\mathrm{tr}(A^{-1}X\tilde{\Sigma}X^{\top}A^{-1})$
$\displaystyle=\sum_{i=1}^{p}\tilde{\lambda_{i}}\lambda_{i}z_{i}^{T}A^{-2}z_{i}.$

Now that we are dealing with a sum of quadratic forms, we consider the first
$k^{*}$ signal and last $p-k^{*}$ noise components separately. Using the
Sherman-Morrison formula the former can be written as

$\displaystyle\sum_{i\leq
k^{*}}\tilde{\lambda_{i}}\lambda_{i}z_{i}^{T}A^{-2}z_{i}$
$\displaystyle=\sum_{i\leq
k^{*}}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}\frac{\lambda_{i}^{2}z_{i}^{T}A_{-i}^{-2}z_{i}}{(1+\lambda_{i}z_{i}^{T}A_{-i}^{-1}z_{i})^{2}}$
$\displaystyle\approx\sum_{i\leq
k^{*}}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}\frac{\lambda_{i}^{2}n(n\lambda_{k+1}\rho_{k})^{-2}}{\lambda_{i}^{2}n^{2}(n\lambda_{k+1}\rho_{k})^{-2}}$
$\displaystyle=\sum_{i\leq
k^{*}}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}\frac{1}{n},$

where $\lambda_{i}z_{i}^{T}A_{-i}^{-1}z_{i}$ dominates $1$ for $i\leq k^{*}$.
For the sum over the noise components the $1$ in the denominator dominates the
other term and so we directly analyze the tail contributions as,

$\displaystyle\sum_{i>k^{*}}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}\lambda_{i}^{2}z_{i}^{T}A^{-2}z_{i}$
$\displaystyle\approx\sum_{i>k^{*}}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}\lambda_{i}^{2}n(n\lambda_{k+1}\rho_{k})^{-2}.$

The result is that the variance term is upper and lower bounded by

$\displaystyle\frac{1}{n}\sum_{i=1}^{k}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}+\sum_{i>k}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}\left(\frac{\lambda_{i}^{2}}{n\lambda_{k+1}^{2}\rho_{k}^{2}}\right)$

times constant factors.

###  D.2 Bias

As in Eqn. 4, the bias term is given by

$\displaystyle B_{2}$
$\displaystyle=\|{\theta_{\mathsf{s}}^{*}}-X^{T}A^{-1}X{\theta_{\mathsf{s}}^{*}}\|_{\Sigma_{\mathsf{t}}}^{2}$
$\displaystyle=\mathrm{tr}({\theta_{\mathsf{s}}^{*}}^{T}(I-X^{T}A^{-1}X)\Sigma_{\mathsf{t}}(I-X^{T}A^{-1}X){\theta_{\mathsf{s}}^{*}})$
$\displaystyle\leq\mathrm{tr}({\theta_{\mathsf{s}}^{*}}{\theta_{\mathsf{s}}^{*}}^{T})\cdot\mathrm{tr}((I-X^{T}A^{-1}X)\Sigma_{\mathsf{t}}(I-X^{T}A^{-1}X))$
$\displaystyle=\|{\theta_{\mathsf{s}}^{*}}\|^{2}\sum_{i=1}^{p}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}\sum_{j=1}^{p}\Big{(}e_{i}[j]-\sqrt{\lambda_{i}\lambda_{j}}z_{i}^{\top}A^{-1}z_{j}\Big{)}^{2},$

where we use the Cauchy-Scharwz inequality to separate the parameter vector
from the quadratic form. A quick application of the Sherman-Morrison formula
allows us to write

$\displaystyle B_{2}$
$\displaystyle\leq\|{\theta_{\mathsf{s}}^{*}}\|^{2}\sum_{i=1}^{p}\tilde{\lambda}_{i}\frac{1}{1+\lambda_{i}z_{i}^{T}A_{-i}^{-1}z_{i}}.$

From here, we once again exert control over the eigenvalues of $A_{-i}$ to get

$\displaystyle\frac{1}{1+\lambda_{i}z_{i}^{T}A_{-i}^{-1}z_{i}}$
$\displaystyle\approx\frac{1}{1+\frac{\lambda_{i}}{\lambda_{k+1}\rho_{k}}},$

which completes the upper bound proof sketch.

Note that the looseness of the bias bounds largely stems from the application
of the Cauchy-Schwarz inequality. The only situations in which the bound
becomes an equality are when

$\displaystyle
c{\theta_{\mathsf{s}}^{*}}=(I-X^{T}A^{-1}X)\Sigma_{\mathsf{t}}^{1/2}$

for some scalar $c\in\mathbb{R}$ or when ${\theta_{\mathsf{s}}^{*}}$ is the
zero vector.

Between the upper and lower bounds, the latter is likely tighter due to the
use of the PriorSigns assumption. As detailed in Appendix F.2, it allows us to
write

$\displaystyle
B\geq{\theta_{\mathsf{s}}^{*}}^{T}(I-\textrm{diag}(X^{T}A^{-1}X))\Sigma_{\mathsf{t}}(I-\textrm{diag}(X^{T}A^{-1}X)){\theta_{\mathsf{s}}^{*}},$

where for a matrix $Q\in\mathbb{R}^{m\times m}$, we use
$\textrm{diag}(Q)\in\mathbb{R}^{m\times m}$ to denote zeroed off-diagonal
entries. The contribution of the off-diagonal entries is non-negative and
dominated by the diagonals, so they can be dropped in the lower bound while
preserving tightness under the PriorSigns assumption. In general, non-negative
terms cannot be discarded in the proof of an upper bound, so we resort to the
Cauchy-Schwarz inequality in order to avoid addressing the off-diagonals
directly. However, decoupling the model vector ${\theta_{\mathsf{s}}^{*}}$
from the matrix $(I-X^{T}A^{-1}X)\Sigma_{\mathsf{t}}^{1/2}$ introduces another
degree of looseness, contributing to the gap between our bounds. Improving our
upper bound will require controlling the off-diagonals of this matrix product
with a technique more appropriate than Cauchy-Schwarz.

##  Appendix E Proof of variance bounds

See 3.1

###### Proof.

We derive the variance terms necessary here and finish the proof of the upper
bound in Appendix E.1 and the lower bound in Appendix E.2.

We follow the proof techniques in [Bar+20, TB23]. Observe that we can express
the variance term as follows,

$\displaystyle V$
$\displaystyle=\operatorname*{\mathbb{E}}_{\varepsilon_{\mathsf{s}}}[V_{\varepsilon_{\mathsf{s}}}/v_{\varepsilon}^{2}]$
$\displaystyle=\operatorname*{\mathbb{E}}_{\varepsilon_{\mathsf{s}}}[\|X^{\top}(XX^{\top})^{-1}\varepsilon_{\mathsf{s}}\|_{\Sigma_{\mathsf{t}}}^{2}/v_{\varepsilon}^{2}].$

Defining $A=XX^{\top}$,

$\displaystyle V$
$\displaystyle=\operatorname*{\mathbb{E}}_{\varepsilon_{\mathsf{s}}}[\|X^{\top}A^{-1}\varepsilon_{\mathsf{s}}\|_{\Sigma_{\mathsf{t}}}^{2}/v_{\varepsilon}^{2}]$
$\displaystyle=\operatorname*{\mathbb{E}}_{\varepsilon_{\mathsf{s}}}[(\varepsilon_{\mathsf{s}}^{\top}A^{-1}X\Sigma_{\mathsf{t}}X^{\top}A^{-1}\varepsilon_{\mathsf{s}})/v_{\varepsilon}^{2}]$
$\displaystyle=\operatorname*{\mathbb{E}}_{\varepsilon_{\mathsf{s}}}[\mathrm{tr}(\varepsilon_{\mathsf{s}}^{\top}A^{-1}X\Sigma_{\mathsf{t}}X^{\top}A^{-1}\varepsilon_{\mathsf{s}})/v_{\varepsilon}^{2}].$

Using the trace trick,

$\displaystyle V$
$\displaystyle=\mathrm{tr}(A^{-1}X\Sigma_{\mathsf{t}}X^{\top}A^{-1}\operatorname*{\mathbb{E}}_{\varepsilon_{\mathsf{s}}}[\varepsilon_{\mathsf{s}}\varepsilon_{\mathsf{s}}^{\top}])/v_{\epsilon}^{2}$
$\displaystyle=\mathrm{tr}(A^{-1}X\Sigma_{\mathsf{t}}X^{\top}A^{-1}v_{\epsilon}^{2}I_{n})/v_{\epsilon}^{2}$
$\displaystyle=\mathrm{tr}(A^{-1}X\Sigma_{\mathsf{t}}X^{\top}A^{-1})$
$\displaystyle=\mathrm{tr}(X\Sigma_{\mathsf{t}}X^{\top}A^{-2})$
$\displaystyle=\mathrm{tr}((\sum_{i=1}^{p}\tilde{\lambda_{i}}x^{i}(x^{i})^{\top})A^{-2})$
$\displaystyle=\mathrm{tr}((\sum_{i=1}^{p}\tilde{\lambda_{i}}\lambda_{i}z_{i}z_{i}^{\top})A^{-2})$

where $x^{i}\in\mathbb{R}^{n}$ and
$\frac{x^{i}}{\sqrt{\lambda_{i}}}=z_{i}\in\mathbb{R}^{n}$ are columns of
$X\in\mathbb{R}^{n\times p}$ and
$X\Sigma_{\mathsf{s}}^{-1/2}\in\mathbb{R}^{n\times p}$, respectively.
Continuing the calculation, we have that

$\displaystyle V$
$\displaystyle=\sum_{i=1}^{p}\tilde{\lambda_{i}}\lambda_{i}\mathrm{tr}(z_{i}^{T}A^{-2}z_{i})$
$\displaystyle=\sum_{i=1}^{p}\tilde{\lambda_{i}}\lambda_{i}\mathrm{tr}(z_{i}^{T}(A_{-i}+z_{i}z_{i}^{T}\lambda_{i})^{-2}z_{i})$
$\displaystyle=\sum_{i=1}^{p}\tilde{\lambda_{i}}\lambda_{i}\frac{z_{i}^{T}A_{-i}^{-2}z_{i}}{(1+\lambda_{i}z_{i}^{T}A_{-i}^{-1}z_{i})^{2}}$

where $A_{-i}=XX^{T}-\lambda_{i}z_{i}z_{i}^{T}=\sum_{j\neq
i}\lambda_{j}z_{j}z_{j}^{T}$. This expression will serve as the starting point
for the variance term, which we will now proceed to upper and lower bound.

∎

###  E.1 Upper bound

After isolating the contribution of $\frac{\tilde{\lambda_{i}}}{\lambda_{i}}$,
most of the components of this proof are as given in the proof of Lemma 6 in
[Bar+20]. For completeness, we replicate them here and refer the reader to
their paper for further details and intuitions.

We start by separating the variance term into the top $k$ components and the
bottom $p-k$ components as follows,

$\displaystyle
V=\sum_{i=1}^{k}\frac{\tilde{\lambda_{i}}}{\lambda_{i}}\frac{\lambda_{i}^{2}z_{i}^{T}A_{-i}^{-2}z_{i}}{(1+\lambda_{i}z_{i}^{T}A_{-i}^{-1}z_{i})^{2}}+\sum_{i>k}\frac{\tilde{\lambda_{i}}}{\lambda_{i}}(\lambda_{i}^{2}z_{i}^{T}A^{-2}z_{i}).$

Fix constants $b,c_{1}\geq 1$ as defined in Lemma B.1. Then, with probability
$1-2e^{-n/c_{1}}$, if $\rho_{k}\geq b$ then for all $z\in\mathbb{R}^{n}$ and
$i\in[1,k]$,

$\displaystyle z_{i}^{T}A_{-i}^{-2}z_{i}$
$\displaystyle\leq\mu_{1}(A_{-i}^{-2})\|z_{i}\|^{2}$
$\displaystyle\leq\mu_{n}(A_{-i})^{-2}\|z_{i}\|^{2}$
$\displaystyle\leq\frac{c_{1}^{2}\|z_{i}\|^{2}}{(n\lambda_{k+1}\rho_{k})^{2}}$

and on the same event,

$\displaystyle z_{i}^{T}A_{-i}^{-1}z_{i}$
$\displaystyle\geq(\Pi_{\mathcal{L}_{i}}z_{i})^{T}A_{-i}^{-1}(\Pi_{\mathcal{L}_{i}}z_{i})$
$\displaystyle\geq\mu_{n}(A_{-i}^{-1})\|\Pi_{\mathcal{L}_{i}}z_{i}\|^{2}$
$\displaystyle\geq\mu_{k+1}(A_{-i})^{-1}\|\Pi_{\mathcal{L}_{i}}z_{i}\|^{2}$
$\displaystyle\geq\frac{\|\Pi_{\mathcal{L}_{i}}z_{i}\|^{2}}{nc_{1}\lambda_{k+1}\rho_{k}}$

where $\Pi_{\mathcal{L}_{i}}$ is the orthogonal projection onto the span of
the bottom $n-k$ eigenvectors of $A_{-i}$. It is important to use the
projection onto the bottom eigenvectors of $A_{-i}$ in lower bounding the
denominator term because we have to use the fact that
$\mu_{n}(A_{-i}^{-1})\geq\mu_{1}(A_{-i})^{-1}$. When we don’t do the
projection, then $z_{i}$ is affected by all of $A_{-i}$ and so the largest
eigenvalue that affects this expression is $\mu_{1}(A_{-i})=\lambda_{1}$.
After doing this projection, we no longer have contributions from the top $k$
eigenvectors / eigenvalues in the summation of $z_{i}^{T}A_{-i}^{-1}z_{i}$.
Therefore, the largest eigenvalue that affects this summation is now
$\lambda_{k+1}$ instead of $\lambda_{1}$, and so we can use this in our lower
bound instead, as desired.

Putting it together, for $i\leq k$,

$\displaystyle\frac{\lambda_{i}^{2}z_{i}^{T}A_{-i}^{-2}z_{i}}{(1+\lambda_{i}z_{i}^{T}A_{-i}^{-1}z_{i})^{2}}$
$\displaystyle\leq\frac{z_{i}^{T}A_{-i}^{-2}z_{i}}{(z_{i}^{T}A_{-i}^{-1}z_{i})^{2}}$
$\displaystyle\leq
c_{1}^{4}\frac{\|z_{i}\|^{2}}{\|\Pi_{\mathcal{L}_{i}}z_{i}\|^{4}}.$

We now invoke Corollary B.5 with a union bound over $k$ events. Let
$t<n/c_{0}$ and $k\in(0,n/c)$ for $c>c_{0}$ and $c_{0}$ sufficiently large.
Since $k<n/c$ we also satisfy the union bound condition that $\ln(k)<n/c$.
Then, with probability at least $1-3e^{-t}$,

$\displaystyle\|z_{i}\|^{2}$ $\displaystyle\leq c_{2}n$
$\displaystyle\|\Pi_{\mathcal{L}_{i}}z_{i}\|^{2}$ $\displaystyle\geq n/c_{3}$

for constants $c_{2},c_{3}$ that only depend on $\sigma_{x},c_{0}$, and a
universal constant $c$ as defined in Corollary B.4.

Altogether, with probability $1-5e^{-n/c_{0}}$ for $c_{0}$ sufficiently large,

$\displaystyle\sum_{i=1}^{k}\frac{\tilde{\lambda_{i}}}{\lambda_{i}}\Bigg{(}\frac{\lambda_{i}^{2}z_{i}^{T}A_{-i}^{-2}z_{i}}{(1+\lambda_{i}z_{i}^{T}A_{-i}^{-1}z_{i})^{2}}\Bigg{)}$
$\displaystyle\leq\sum_{i=1}^{k}\frac{\tilde{\lambda_{i}}}{\lambda_{i}}c_{1}^{4}\frac{\|z_{i}\|^{2}}{\|\Pi_{\mathcal{L}_{i}}z_{i}\|^{4}}$
$\displaystyle\leq\sum_{i=1}^{k}\frac{\tilde{\lambda_{i}}}{\lambda_{i}}c_{1}^{4}\frac{c_{2}c_{3}^{2}}{n}$
$\displaystyle=c_{4}\sum_{i=1}^{k}\frac{\tilde{\lambda_{i}}}{\lambda_{i}}\frac{1}{n}.$

On the same event we use to bound $\mu_{k+1}(A_{-i})$ via Lemma B.1, we also
have that $\mu_{1}(A^{-2})\leq\mu_{n}(A)^{-2}$. As such,

$\displaystyle\sum_{i>k}\frac{\tilde{\lambda_{i}}}{\lambda_{i}}(\lambda_{i}^{2}z_{i}^{T}A^{-2}z_{i})\leq\frac{c_{1}^{2}\sum_{i>k}\frac{\tilde{\lambda_{i}}}{\lambda_{i}}\lambda_{i}^{2}\|z_{i}\|^{2}}{(n\lambda_{k+1}\rho_{k})^{2}}.$

Then by Corollary B.7, there is a universal constant $a$ such that with
probability at least $1-2e^{-t}$ for $t<n/c_{0}$ and $c_{0}>a^{-1}$,

$\displaystyle\sum_{i>k}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}\lambda_{i}^{2}\|z_{i}\|^{2}$
$\displaystyle\leq\sigma_{x}^{2}\max(t\max_{i>k}(\tilde{\lambda}_{i}\lambda_{i}),\sqrt{t\sum_{i>k}(\tilde{\lambda_{i}}\lambda_{i})^{2}})$
$\displaystyle\leq
n\sum_{i>k}\tilde{\lambda}_{i}\lambda_{i}+\sigma_{x}^{2}\max(t\max_{i>k}(\tilde{\lambda}_{i}\lambda_{i}),\sqrt{tn\sum_{i>k}(\tilde{\lambda_{i}}\lambda_{i})^{2}})$
$\displaystyle\leq
n\sum_{i>k}\tilde{\lambda}_{i}\lambda_{i}+\sigma_{x}^{2}\max(t\sum_{i>k}\tilde{\lambda}_{i}\lambda_{i},\sqrt{tn}\sum_{i>k}\tilde{\lambda}_{i}\lambda_{i})$
$\displaystyle\leq c_{5}n\sum_{i>k}\tilde{\lambda}_{i}\lambda_{i}$
$\displaystyle=c_{5}n\sum_{i>k}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}\lambda_{i}^{2}.$

Altogether,

$\displaystyle\sum_{i>k}\frac{\tilde{\lambda_{i}}}{\lambda_{i}}(\lambda_{i}^{2}z_{i}^{T}A^{-2}z_{i})$
$\displaystyle\leq\frac{c_{1}^{2}\sum_{i>k}\frac{\tilde{\lambda_{i}}}{\lambda_{i}}\lambda_{i}^{2}\|z_{i}\|^{2}}{(n\lambda_{k+1}\rho_{k})^{2}}$
$\displaystyle\leq\frac{c_{1}^{2}c_{5}n}{(n\lambda_{k+1}\rho_{k})^{2}}\sum_{i>k}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}\lambda_{i}^{2}$
$\displaystyle=c_{6}\sum_{i>k}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}\left(\frac{\lambda_{i}^{2}}{n\lambda_{k+1}^{2}\rho_{k}^{2}}\right).$

By taking $c>\max(c_{0},c_{4},c_{6})$ we have that with probability
$1-7e^{-n/c}$,

$\displaystyle V$ $\displaystyle\leq
c\left(\sum_{i=1}^{k}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}\frac{1}{n}+\sum_{i>k}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}\left(\frac{\lambda_{i}^{2}}{n\lambda_{k+1}^{2}\rho_{k}^{2}}\right)\right)$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{k}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}+n\frac{\sum_{i>k}\tilde{\lambda}_{i}\lambda_{i}}{(\sum_{i>k}\lambda_{i})^{2}}.$

###  E.2 Lower bound

Recall that the variance takes the form,

$\displaystyle
V=\sum_{i=1}^{p}\tilde{\lambda_{i}}\lambda_{i}\frac{z_{i}^{T}A_{-i}^{-2}z_{i}}{(1+\lambda_{i}z_{i}^{T}A_{-i}^{-1}z_{i})^{2}}.$

By Cauchy-Schwartz,

$\displaystyle(z_{i}^{T}A_{-i}^{-1}z_{i})^{2}=|\langle
z_{i},A_{-i}^{-1}z_{i}\rangle|^{2}\leq\|z_{i}\|^{2}\cdot(z_{i}^{T}A_{-i}^{-2}z_{i}).$

We plug this identity into our lower bound, and further multiply by
$\frac{\lambda_{i}}{\lambda_{i}}$, resulting in

$\displaystyle V$
$\displaystyle=\sum_{i=1}^{p}\tilde{\lambda_{i}}\lambda_{i}\frac{z_{i}^{T}A_{-i}^{-2}z_{i}}{(1+\lambda_{i}z_{i}^{T}A_{-i}^{-1}z_{i})^{2}}$
$\displaystyle=\sum_{i=1}^{p}(\frac{\tilde{\lambda_{i}}}{\lambda_{i}})\frac{\lambda_{i}^{2}z_{i}^{T}A_{-i}^{-2}z_{i}}{(1+\lambda_{i}z_{i}^{T}A_{-i}^{-1}z_{i})^{2}}$
$\displaystyle\geq\sum_{i=1}^{p}(\frac{\tilde{\lambda_{i}}}{\lambda_{i}})\frac{\lambda_{i}^{2}(z_{i}^{T}A_{-i}^{-1}z_{i})^{2}}{||z_{i}||^{2}(1+\lambda_{i}z_{i}^{T}A_{-i}^{-1}z_{i})^{2}}$
$\displaystyle=\sum_{i=1}^{p}(\frac{\tilde{\lambda_{i}}}{\lambda_{i}})\frac{1}{||z_{i}||^{2}(1+\lambda_{i}z_{i}^{T}A_{-i}^{-1}z_{i})^{2}(\lambda_{i}z_{i}^{T}A_{-i}^{-1}z_{i})^{-2}}$
$\displaystyle=\sum_{i=1}^{p}(\frac{\tilde{\lambda_{i}}}{\lambda_{i}})\frac{1}{||z_{i}||^{2}(1+(\lambda_{i}z_{i}^{T}A_{-i}^{-1}z_{i})^{-1})^{2}}.$

Then, let $k\in(0,n)$ and $\mathscr{L}_{i}$ be the span of the bottom $n-k$
eigenvectors of $A_{-i}$ and $\Pi_{\mathscr{L}_{i}}$ be the projection onto
the orthogonal complement of $\mathscr{L}_{i}$. We have that

$\displaystyle z_{i}^{T}A_{-i}^{-1}z_{i}$
$\displaystyle\geq(\Pi_{\mathscr{L}_{i}}z_{i})^{T}A_{-i}^{-1}(\Pi_{\mathscr{L}_{i}}z_{i})$
$\displaystyle\geq\|\Pi_{\mathscr{L}_{i}}z_{i}\|^{2}\mu_{k+1}(A_{-i})^{-1}.$

From Lemma B.1, there is a constant $c_{1}\geq 1$, such that for any $k\geq
0$, with probability $1-2e^{-n/c_{1}}$, $\mu_{k+1}(A_{-i})\leq
c_{1}(\sum_{j>k}\lambda_{j}+\lambda_{k+1}n)$. Additionally, by Corollary B.5,
let $t<n/c_{3}$ and $k\in(0,n/c)$ for $c>c_{3}$ and $c_{3}$ sufficiently
large. Then, with probability at least $1-3e^{-t}$

$\displaystyle\|\Pi_{\mathscr{L}_{i}}z_{i}\|^{2}\geq n/c_{4}$

where $c_{4}$ only depends on $c_{3},\sigma_{x}$ and the universal constant
given in Corollary B.4.

Then, for $c\geq\max\\{c_{1},c_{3}\\}$, with probability $1-5e^{-n/c}$,

$\displaystyle z_{i}^{T}A_{-i}^{-1}z_{i}$
$\displaystyle\geq\|\Pi_{\mathscr{L}_{i}}z_{i}\|^{2}\mu_{k+1}(A_{-i})^{-1}$
$\displaystyle\geq\frac{n}{c_{4}(\sum_{j>k}\lambda_{j}+\lambda_{k+1}n)}.$

By again applying Corollary B.5 on the same event we have

$\displaystyle\|z_{i}\|^{2}$ $\displaystyle\leq c_{5}n.$

where $c_{5}$ has the same dependencies as $c_{4}$.

Altogether, we have for each $i$, with probability $1-5e^{-n/c}$,

$\displaystyle\frac{1}{||z_{i}||^{2}(1+(\lambda_{i}z_{i}^{T}A_{-i}^{-1}z_{i})^{-1})^{2}}$
$\displaystyle\geq\frac{1}{c_{5}n(1+(\frac{c_{4}(\sum_{j>k}\lambda_{j}+\lambda_{k+1}n)}{\lambda_{i}n}))^{2}}$
$\displaystyle=\frac{1}{c_{5}n(1+\frac{c_{4}\lambda_{k+1}}{\lambda_{i}}(\frac{\sum_{j>k}\lambda_{j}}{\lambda_{k+1}n}+1))^{2}}$
$\displaystyle=\frac{1}{c_{5}c_{4}^{2}n(1/c_{4}+\frac{\lambda_{k+1}}{\lambda_{i}}(\rho_{k}+1))^{2}}$
$\displaystyle\geq\frac{1}{c_{6}n(1+\frac{\lambda_{k+1}}{\lambda_{i}}(\rho_{k}+1))^{2}}$

where $c_{6}=c_{5}c_{4}^{2}$ and $c>\max\\{c_{1},c_{3}\\}$ as defined above.

Finally, we invoke Lemma B.6 and that $1/(a+b)^{2}\geq\min(a^{-2},b^{-2})/4$
to get that, with probability $1-10e^{-n/c}$,

$\displaystyle
V\geq\frac{1}{8c_{6}n}\sum_{i=1}^{p}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}\min(1,\frac{\lambda_{i}^{2}}{\lambda_{k+1}^{2}(\rho_{k}+1)^{2}}).$

For $c_{7}\geq\max\\{8c_{6},c\\}$ we have that with probability
$1-10e^{-n/c_{7}}$,

$\displaystyle
V\geq\frac{1}{c_{7}n}\sum_{i=1}^{p}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}\min(1,\frac{\lambda_{i}^{2}}{\lambda_{k+1}^{2}(\rho_{k}+1)^{2}}).$

##  Appendix F Proof of bias bounds

See 3.2

###  F.1 Upper bound

###### Proof.

As defined in Eqn. 4,

$\displaystyle B_{2}$
$\displaystyle=\|{\theta_{\mathsf{s}}^{*}}-\widehat{\theta}(X{\theta_{\mathsf{s}}^{*}})\|_{\Sigma_{\mathsf{t}}}^{2}$
$\displaystyle=\|{\theta_{\mathsf{s}}^{*}}-X^{T}A^{-1}X{\theta_{\mathsf{s}}^{*}}\|_{\Sigma_{\mathsf{t}}}^{2}$
$\displaystyle={\theta_{\mathsf{s}}^{*}}^{T}(I-X^{T}A^{-1}X)\Sigma_{\mathsf{t}}(I-X^{T}A^{-1}X){\theta_{\mathsf{s}}^{*}}.$
(21)

The $i^{\text{th}}$ row of $I_{p}-X^{T}A^{-1}X$ is given by
$e_{i}-\sqrt{\lambda_{i}}z_{i}^{T}A^{-1}X$. It follows that

$\displaystyle(\theta^{*})^{T}M\theta^{*}$
$\displaystyle=\begin{pmatrix}\vdots\\\
\sum_{j=1}^{p}\theta_{j}(e_{i}[j]-\sqrt{\lambda_{i}\lambda_{j}}z_{i}^{\top}A^{-1}z_{j})\\\
\vdots\end{pmatrix}^{\top}\Sigma_{\mathsf{t}}\begin{pmatrix}\vdots\\\
\sum_{j=1}^{p}\theta_{j}(e_{i}[j]-\sqrt{\lambda_{i}\lambda_{j}}z_{i}^{\top}A^{-1}z_{j})\\\
\vdots\end{pmatrix}\;\;\textit{$i^{\text{th}}$ row shown}$
$\displaystyle=\sum_{i=1}^{p}\tilde{\lambda}_{i}\Big{(}\sum_{j=1}^{p}\theta_{j}(e_{i}[j]-\sqrt{\lambda_{i}\lambda_{j}}z_{i}^{\top}A^{-1}z_{j})\Big{)}^{2}$
$\displaystyle\leq\sum_{i=1}^{p}\tilde{\lambda}_{i}\Big{(}\sum_{j=1}^{p}\theta^{2}_{j}\Big{)}\sum_{j=1}^{p}\Big{(}e_{i}[j]-\sqrt{\lambda_{i}\lambda_{j}}z_{i}^{\top}A^{-1}z_{j}\Big{)}^{2}$
$\displaystyle=\|\theta^{*}\|^{2}\sum_{i=1}^{p}\tilde{\lambda}_{i}\sum_{j=1}^{p}\Big{(}e_{i}[j]-\sqrt{\lambda_{i}\lambda_{j}}z_{i}^{\top}A^{-1}z_{j}\Big{)}^{2}.$

Next we look at $i^{\text{th}}$ term in the outer sum.

$\displaystyle\tilde{\lambda}_{i}\sum_{j=1}^{p}(e_{i}[j]-\sqrt{\lambda_{i}\lambda_{j}}z_{i}^{\top}A^{-1}z_{j})^{2}$
$\displaystyle=\tilde{\lambda}_{i}(1-\lambda_{i}z_{i}^{\top}A^{-1}z_{i})^{2}+\tilde{\lambda}_{i}\sum_{j\neq
i}\lambda_{i}\lambda_{j}(z_{i}^{\top}A^{-1}z_{j})^{2}$
$\displaystyle=\tilde{\lambda}_{i}(1-2\lambda_{i}z_{i}^{T}A^{-1}z_{i}+\lambda_{i}^{2}(z_{i}^{T}A^{-1}z_{i})^{2}+\sum_{j\neq
i}\lambda_{i}\lambda_{j}(z_{i}^{\top}A^{-1}z_{j})^{2})$
$\displaystyle=\tilde{\lambda}_{i}(1-2\lambda_{i}z_{i}^{T}A^{-1}z_{i}+\sum_{i=1}^{p}\lambda_{i}\lambda_{j}(z_{i}^{\top}A^{-1}z_{j})^{2})$
$\displaystyle=\tilde{\lambda}_{i}(1-2\lambda_{i}z_{i}^{T}A^{-1}z_{i}+\lambda_{i}z_{i}^{\top}A^{-1}\Big{(}\sum_{i=1}^{p}\lambda_{j}z_{j}z_{j}^{T}\Big{)}A^{-1}z_{i})$
$\displaystyle=\tilde{\lambda}_{i}\left(1-2\lambda_{i}z_{i}^{T}A^{-1}z_{i}+\lambda_{i}z_{i}^{\top}A^{-1}AA^{-1}z_{i}\right)$
$\displaystyle=\tilde{\lambda}_{i}\left(1-2\lambda_{i}z_{i}^{T}A^{-1}z_{i}+\lambda_{i}z_{i}^{\top}A^{-1}z_{i}\right)$
$\displaystyle=\tilde{\lambda}_{i}\left(1-\lambda_{i}z_{i}^{T}A^{-1}z_{i}\right).$

Using the Sherman-Morrison formula, we get that

$\displaystyle 1-\lambda_{i}z_{i}^{T}A^{-1}z_{i}$
$\displaystyle=1-\lambda_{i}z_{i}^{T}\big{(}A_{-i}+\lambda_{i}z_{i}z_{i}^{T}\big{)}^{-1}z_{i}$
$\displaystyle=1-\lambda_{i}z_{i}^{T}\Big{(}A^{-1}_{-i}-\lambda_{i}A^{-1}_{-i}z_{i}(1+\lambda_{i}z_{i}^{T}A^{-1}_{-i}z_{i})^{-1}z_{i}^{T}A^{-1}_{-i}\Big{)}z_{i}$
$\displaystyle=1-\lambda_{i}z_{i}^{T}A^{-1}_{-i}z_{i}+\frac{(\lambda_{i}z_{i}^{T}A^{-1}_{-i}z_{i})^{2}}{1+\lambda_{i}z_{i}^{T}A^{-1}_{-i}z_{i}}$
$\displaystyle=\frac{1}{1+\lambda_{i}z_{i}^{T}A_{-i}^{-1}z_{i}}.$

We now provide an upper bound for the remaining term. Let
$\Pi_{\mathcal{L}_{i}}$ be the orthogonal projection onto the bottom $n-k$
eigenvectors of $A_{-i}.$ By Lemma B.1, there exist constants $b,c_{0}\geq 1$
such that if $\rho_{k}\geq b$, then with probability at least
$1-2e^{-n/c_{0}},$

$\displaystyle\mu_{k+1}(A_{-i})\leq c_{0}\lambda_{k+1}\rho_{k}n,$

so we get

$\displaystyle 1+\lambda_{i}z_{i}^{T}A_{-i}^{-1}z_{i}$ $\displaystyle\geq
1+\lambda_{i}(\Pi_{\mathcal{L}_{i}}z_{i})^{T}A_{-i}^{-1}(\Pi_{\mathcal{L}_{i}}z_{i})$
$\displaystyle\geq
1+\frac{\lambda_{i}\left\|\Pi_{\mathcal{L}_{i}}z_{i}\right\|^{2}}{c_{0}\lambda_{k+1}n\rho_{k}}.$

By Corollary B.5, there exist constants $c_{1}$ and $c_{2}$ with $c_{2}>c_{1}$
and $c_{1}$ sufficiently large such that for $0<k<n/c_{2}$, we have with
probability at least $1-3e^{-n/c_{1}}$,

$\displaystyle\left\|\Pi_{\mathcal{L}_{i}}z_{i}\right\|^{2}\geq n/c_{3},$

where $c_{3}$ depends only on $c_{1}$ and $\sigma$.

Plugging these in gives us with probability at least $1-5e^{-n/c_{4}}$,

$\displaystyle\tilde{\lambda}_{i}\left(1-\lambda_{i}z_{i}^{T}A^{-1}z_{i}\right)$
$\displaystyle\leq\frac{\tilde{\lambda}_{i}}{\big{(}1+\frac{c_{5}^{2}\lambda_{i}}{\lambda_{k+1}\rho_{k}}\big{)}}$
$\displaystyle=\frac{\tilde{\lambda}_{i}}{\lambda_{i}}\frac{\lambda_{i}}{\big{(}1+\frac{c_{5}^{2}\lambda_{i}}{\lambda_{k+1}\rho_{k}}\big{)}},$

where $c_{4}=\max(c_{0},c_{1})$ and $c_{5}=\min(c_{0},c_{3}).$

Therefore by union bound over the application of Corollary B.5,

$\displaystyle B$
$\displaystyle\leq\|\theta^{*}\|^{2}\sum_{i=1}^{p}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}\frac{\lambda_{i}}{\big{(}1+\frac{c_{5}^{2}\lambda_{i}}{\lambda_{k+1}\rho_{k}}\big{)}}$
$\displaystyle\leq\frac{1}{c_{6}}\|\theta^{*}\|^{2}\sum_{i=1}^{p}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}\frac{\lambda_{i}}{\big{(}1+\frac{\lambda_{i}}{\lambda_{k+1}\rho_{k}}\big{)}},$

where $c_{6}=\min(c_{5}^{2},1)$. Taking $c=\max(c_{6}^{-1},c_{4})$ gives us
the result.

∎

###  F.2 Lower bound

After isolating the contribution of $\frac{\tilde{\lambda}_{i}}{\lambda_{i}}$,
many of the components of this proof are as given in [TB23]. For completeness,
we replicate them here.

###### Proof.

Assume that the vector ${\theta_{\mathsf{s}}^{*}}$ is randomly distributed
according to the PriorSigns($\overline{\theta}_{\mathsf{s}}$) assumption.
Using Lemma B.8, the bias term can be rewritten as

$\displaystyle B$
$\displaystyle=\operatorname*{\mathbb{E}}_{{\theta_{\mathsf{s}}^{*}}}[B_{\theta_{\mathsf{s}}^{*}}]$
$\displaystyle=\operatorname*{\mathbb{E}}_{{\theta_{\mathsf{s}}^{*}}}[\lVert{\theta_{\mathsf{s}}^{*}}-\widehat{\theta}(X{\theta_{\mathsf{s}}^{*}})\rVert_{\Sigma_{\mathsf{t}}}^{2}]$
$\displaystyle=\operatorname*{\mathbb{E}}_{{\theta_{\mathsf{s}}^{*}}}[({\theta_{\mathsf{s}}^{*}})^{T}(I_{p}-X^{T}(XX^{T})^{-1}X)\Sigma_{\mathsf{t}}(I_{p}-X^{T}(XX^{T})^{-1}X){\theta_{\mathsf{s}}^{*}}]$
$\displaystyle=\operatorname*{\mathbb{E}}_{{\theta_{\mathsf{s}}^{*}}}[({\theta_{\mathsf{s}}^{*}})^{T}M{\theta_{\mathsf{s}}^{*}}]$
$\displaystyle=\operatorname*{\mathbb{E}}_{{\theta_{\mathsf{s}}^{*}}}[{\theta_{\mathsf{s}}^{*}}]^{T}M\operatorname*{\mathbb{E}}_{{\theta_{\mathsf{s}}^{*}}}[{\theta_{\mathsf{s}}^{*}}]+\mathrm{tr}(M\mathrm{Cov}({\theta_{\mathsf{s}}^{*}}))$
$\displaystyle=\mathrm{tr}(M\mathrm{Cov}({\theta_{\mathsf{s}}^{*}})).$

where
$M=(I_{p}-X^{T}(XX^{T})^{-1}X)\Sigma_{\mathsf{t}}(I_{p}-X^{T}(XX^{T})^{-1}X).$
The last equality follows from the assumption
$\operatorname*{\mathbb{E}}_{{\theta_{\mathsf{s}}^{*}}}[({\theta_{\mathsf{s}}^{*}})]=0.$
The diagonal elements of Cov(${\theta_{\mathsf{s}}^{*}}$) are the component-
wise variances of ${\theta_{\mathsf{s}}^{*}}$, which are given by
$({\theta_{\mathsf{s}}^{*}})_{i}^{2}=(\overline{\theta}_{\mathsf{s}})_{i}^{2}$.
The off-diagonal elements are 0 since the components of
${\theta_{\mathsf{s}}^{*}}$ are independent. As such, we need only consider
the diagonal elements of $M$.

Note that the $i^{th}$ row of $I_{p}-X^{T}(XX^{T})^{-1}X$ is equal to
$e_{i}-\sqrt{\lambda_{i}}z_{i}^{T}(XX^{T})^{-1}X$, where $e_{i}$ is the
$i^{th}$ vector of the standard orthonormal basis. It follows that the
$i^{th}$ diagonal element of $M$ is given by

$\displaystyle M_{ii}$
$\displaystyle=\sum_{j=1}^{p}\tilde{\lambda}_{j}(e_{i}[j]-\sqrt{\lambda_{i}\lambda_{j}}z_{i}^{T}A^{-1}z_{j})^{2}$
$\displaystyle=\tilde{\lambda}_{i}(1-\lambda_{i}z_{i}^{T}A^{-1}z_{i})^{2}+\sum_{j\neq
i}\tilde{\lambda}_{j}\lambda_{i}\lambda_{j}(z_{i}^{T}A^{-1}z_{j})^{2}.$

Hence, we can express the bias term as

$\displaystyle B$
$\displaystyle=\sum_{i=1}^{p}(\overline{\theta}_{\mathsf{s}})_{i}^{2}\big{[}\tilde{\lambda}_{i}(1-\lambda_{i}z_{i}^{T}A^{-1}z_{i})^{2}+\sum_{j\neq
i}\tilde{\lambda}_{j}\lambda_{i}\lambda_{j}(z_{i}^{T}A^{-1}z_{j})^{2}\big{]}$
$\displaystyle\geq\sum_{i=1}^{p}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}\lambda_{i}(\overline{\theta}_{\mathsf{s}})_{i}^{2}(1-\lambda_{i}z_{i}^{T}A^{-1}z_{i})^{2}.$

We are able to eliminate the second term because it is non-negative.
Substituting $A=A_{-i}+\lambda_{i}z_{i}z_{i}^{T}$ and using the Sherman-
Morrison identity, we have that
$1-\lambda_{i}z_{i}^{T}A^{-1}z_{i}=\frac{1}{1+\lambda_{i}z_{i}^{T}A_{-i}^{-1}z_{i}}$
(see proof of bias upper bound in Appendix F.1). Then,

$\displaystyle B$
$\displaystyle\geq\sum_{i=1}^{p}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}\frac{\lambda_{i}(\overline{\theta}_{\mathsf{s}})_{i}^{2}}{(1+\lambda_{i}z_{i}^{T}A_{-i}^{-1}z_{i})^{2}}$

Let’s bound each term in that sum from below with high probability. By
Corollary B.3, there exist constants $b,c_{0}\geq 1$ such that for any $i\geq
0$ with probability at least $1-2e^{-n/c_{0}}$, if $\rho_{k}\geq b$, then

$\displaystyle\mu_{n}(A_{-i})\geq\frac{1}{c_{0}}n\lambda_{k+1}\rho_{k}.$

Next,

$\displaystyle\frac{\lambda_{i}}{(1+\lambda_{i}z_{i}^{T}A_{-i}^{-1}z_{i})^{2}}\geq\frac{\lambda_{i}}{(1+\lambda_{i}\mu_{n}(A_{-i})^{-1}\left\|z_{i}\right\|^{2})^{2}}.$

By Corollary B.5, for constants $c_{1},c_{2}$ such that $k<n/c_{2}$ with
$c_{2}>c_{1}$ for sufficiently large $c_{1}$ with probability at least
$1-3e^{-n/c_{1}}$ we have $\left\|z_{i}\right\|^{2}\leq c_{3}n$, where $c_{3}$
depends only on $c_{1}$ and $\sigma.$

We obtain that w.p. at least $1-5e^{-n/c_{4}}$,

$\displaystyle\frac{\lambda_{i}\bar{\theta}_{i}^{2}}{(1+\lambda_{i}z_{i}^{T}A_{-i}^{-1}z_{i})^{2}}\geq\frac{\lambda_{i}\bar{\theta}_{i}^{2}}{\left(1+\frac{c_{4}^{2}\lambda_{i}}{\lambda_{k+1}\rho_{k}}\right)^{2}},$

where $c_{4}=\max(c_{0},c_{1},c_{3}).$ All the terms are non-negative so Lemma
B.6 provides a lower bound on their sum. With probability at least
$1-10e^{-n/c_{4}},$

$\displaystyle B$
$\displaystyle\geq\frac{1}{2}\sum_{i=1}^{p}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}\frac{\lambda_{i}\bar{\theta}_{i}^{2}}{(1+\frac{c_{4}^{2}\lambda_{i}}{\lambda_{k+1}\rho_{k}})^{2}}$
$\displaystyle\geq\frac{1}{c_{5}}\sum_{i=1}^{p}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}\frac{\lambda_{i}\bar{\theta}_{i}^{2}}{(1+\frac{\lambda_{i}}{\lambda_{k+1}\rho_{k}})^{2}},$

where $c_{5}=2\max(c_{4}^{2},1).$

Finally, we notice that on $i>k$ we have $\rho_{k}\geq b>1$ and
$\lambda_{i}\leq\lambda_{k+1}$ giving us,

$\displaystyle\sum_{i>k}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}\frac{\lambda_{i}\bar{\theta}_{i}^{2}}{(1+\frac{\lambda_{i}}{\lambda_{k+1}\rho_{k}})^{2}}$
$\displaystyle\geq\sum_{i>k}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}\frac{\lambda_{i}\bar{\theta}_{i}^{2}}{(1+\frac{\lambda_{i}}{\lambda{k+1}})^{2}}$
$\displaystyle\geq\sum_{i>k}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}\frac{\lambda_{i}\bar{\theta}_{i}^{2}}{4}$
$\displaystyle=\frac{1}{4}\sum_{i>k}\tilde{\lambda}_{i}\bar{\theta}_{i}^{2}.$

Letting $c=4\max(c_{4},c_{5})$ gives us the result.

∎

##  Appendix G Proof of tightness of bounds

See 3.3

###### Proof.

We split the proof into the variance proof in Appendix G.1 and the bias proof
in Appendix G.2. ∎

###  G.1 Variance Proof

###### Proof.

Recall that

$\displaystyle\underline{V}$
$\displaystyle=\frac{1}{8c_{6}n}\sum_{i=1}^{p}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}\min\left(1,\frac{\lambda_{i}^{2}}{\lambda_{k+1}^{2}(\rho_{k}+1)^{2}}\right)$
$\displaystyle\overline{V}$
$\displaystyle=c\left(\sum_{i=1}^{k}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}\frac{1}{n}+\sum_{i>k}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}\left(\frac{\lambda_{i}^{2}}{n\lambda_{k+1}^{2}\rho_{k}^{2}}\right)\right).$

Since $k$ is the smallest $\ell$ such that $\rho_{\ell}\geq b$, it is clear by
definition that $\rho_{k-1}<b$. Then we observe that

$\displaystyle\rho_{k-1}=\frac{1}{n\lambda_{k}}\sum_{j>k-1}\lambda_{j}=\frac{\lambda_{k}+\sum_{j>k}\lambda_{j}}{n\lambda_{k}}=\frac{\lambda_{k}+n\lambda_{k+1}\rho_{k}}{n\lambda_{k}}<b$
$\displaystyle\therefore\lambda_{k}+n\lambda_{k+1}\rho_{k}<nb\lambda_{k}\Rightarrow\lambda_{k}>\frac{\lambda_{k}+n\lambda_{k+1}\rho_{k}}{nb}>\frac{n\lambda_{k+1}\rho_{k}}{nb}=\frac{\lambda_{k+1}\rho_{k}}{b}.$

On $i\leq k$,

$\displaystyle\underline{V}:\overline{V}$
$\displaystyle=\frac{1}{8c_{6}n}\sum_{i=1}^{k}\frac{\tilde{\lambda_{i}}}{\lambda_{i}}\min\Bigg{(}1,\frac{\lambda_{i}^{2}}{\lambda_{k+1}^{2}(\rho_{k}+1)^{2}}\Bigg{)}:\frac{\tilde{\lambda_{i}}}{\lambda_{i}}\frac{c}{n}$
$\displaystyle\geq\frac{1}{8c_{6}c}\sum_{i=1}^{k}\min\Bigg{(}1,\frac{\lambda_{i}^{2}}{\lambda_{k+1}^{2}(\rho_{k}+1)^{2}}\Bigg{)}:1.$

If the min is $1$ then we are okay otherwise, using the identity above and
that fact that $\lambda_{i}\geq\lambda_{k}$, we have that

$\displaystyle\frac{\lambda_{i}^{2}}{\lambda_{k+1}^{2}(\rho_{k}+1)^{2}}$
$\displaystyle>\frac{(\lambda_{k+1}\rho_{k})^{2}}{b^{2}\lambda_{k+1}^{2}(\rho_{k}+1)^{2}}$
$\displaystyle=\frac{\rho_{k}^{2}}{b^{2}(\rho_{k}+1)^{2}}.$

Examining the $\rho_{k}$ terms:

$\displaystyle\frac{\rho_{k}^{2}}{(\rho_{k}+1)^{2}}$
$\displaystyle=\frac{1}{\rho_{k}^{-2}(\rho_{k}+1)^{2}}$
$\displaystyle=\frac{1}{(1+\rho_{k}^{-1})^{2}}.$

As $\rho_{k}\geq b$ we have that $\rho_{k}^{-1}\leq b\Rightarrow
1+\rho_{k}^{-1}\leq 1+b\Rightarrow(1+\rho_{k}^{-1})^{-2}\geq(1+b)^{-2}$.

Putting it together we get that

$\displaystyle\frac{1}{8c_{6}c}\sum_{i=1}^{k}\frac{\lambda_{i}^{2}}{\lambda_{k+1}^{2}(\rho_{k}+1)^{2}}$
$\displaystyle\geq\frac{1}{8c_{6}c}\sum_{i=1}^{k}\frac{1}{b^{2}(1+b)^{2}}$
$\displaystyle=\frac{k}{8c_{6}c\cdot b^{2}(1+b)^{2}}$
$\displaystyle\geq\frac{1}{8c_{6}c\cdot b^{2}(1+b)^{2}}.$

On $i>k$, it is clear that the $\min$ is always given by the second term, as
$\lambda_{i}\leq\lambda_{k+1}$, so we get

$\displaystyle\underline{V}:\overline{V}$
$\displaystyle=\frac{1}{8c_{6}n}\sum_{i>k}\frac{\tilde{\lambda_{i}}}{\lambda_{i}}\min\Bigg{(}1,\frac{\lambda_{i}^{2}}{\lambda_{k+1}^{2}(\rho_{k}+1)^{2}}\Bigg{)}:c\frac{\tilde{\lambda_{i}}}{\lambda_{i}}\frac{\lambda_{i}^{2}}{n\lambda_{k+1}^{2}\rho_{k}^{2}}$
$\displaystyle=\frac{1}{8c_{6}c}\sum_{i>k}\frac{\rho_{k}^{2}}{(\rho_{k}+1)^{2}}$
$\displaystyle\geq\frac{1}{8c_{6}c}\sum_{i>k}\frac{1}{(1+b)^{2}}=\frac{1}{8c_{6}c}\frac{p-k}{(1+b)^{2}}>\frac{1}{8c_{6}c(1+b)^{2}}.$

Finally we note that for $b\geq 1$ it is clear that
$\min(b^{-2}(1+b)^{-2},(1+b)^{-2})=b^{-2}(1+b)^{-2}$. Therefore,

$\displaystyle\underline{V}:\overline{V}\geq\frac{1}{8c_{6}c}b^{-2}(1+b)^{-2}.$

By setting $c$ in the upper bound such that $c>8c_{6}$, we get

$\displaystyle\underline{V}:\overline{V}\geq\frac{1}{c^{2}}b^{-2}(1+b)^{-2}.$

∎

###  G.2 Bias proof

###### Proof.

We will bound the ratio of the lower and upper bounds by bounding the ratios
of the corresponding terms in each sum. Observe that for all $i$, the ratio of
the terms is equal to

$\displaystyle\frac{(\theta^{*}_{i})^{2}}{\|\theta^{*}\|^{2}}\cdot\frac{1}{\left(1+\frac{\lambda_{i}}{\lambda_{k+1}\rho_{k}}\right)}.$

On $i\leq k,$

$\displaystyle\frac{(\theta^{*}_{i})^{2}}{\|\theta^{*}\|^{2}}\cdot\frac{1}{\left(1+\frac{\lambda_{i}}{\lambda_{k+1}\rho_{k}}\right)}$
$\displaystyle\geq\min_{i}\frac{(\theta^{*}_{i})^{2}}{\|\theta^{*}\|^{2}}\cdot\frac{1}{\left(1+\frac{\lambda_{1}}{\lambda_{k+1}}b^{-1}\right)}.$

On $i>k$, we have $\lambda_{i}/\lambda_{k+1}\leq 1$, so

$\displaystyle\frac{(\theta^{*}_{i})^{2}}{\|\theta^{*}\|^{2}}\cdot\frac{1}{\left(1+\frac{\lambda_{i}}{\lambda_{k+1}\rho_{k}}\right)}$
$\displaystyle\geq\min_{i}\frac{(\theta^{*}_{i})^{2}}{\|\theta^{*}\|^{2}}\cdot\frac{1}{\left(1+b^{-1}\right)}.$

Unfortunately, the looseness in the top $k$ components coming from the gap
$\lambda_{1}/\lambda_{k+1}$ dominates the tighter ratios in the bottom $p-k$
components which only contain a model-dependent gap,
$\min_{i}\theta_{i}^{2}/\|\theta\|^{2}$. Future work would seek to resolve
this and provide tight upper and lower bounds for the bias terms.

∎

##  Appendix H Proof of beneficial and malignant shifts

###  H.1 Trace conditions for simple shifts

Let $\Sigma_{\mathsf{s}}$ be any source covariance and define
$\Sigma_{\mathsf{t}}$ as $\tilde{\lambda}_{i}=\alpha\lambda_{i}$ for $i\leq k$
and $\tilde{\lambda}_{i}=\beta\lambda_{i}$ for $i>k$ with $\alpha,\beta\geq
0$.

Then
$\mathrm{tr}(\Sigma_{\mathsf{s}})=\sum_{i=1}^{k}\lambda_{i}+\sum_{i>k}\lambda_{i}$
and
$\mathrm{tr}(\Sigma_{\mathsf{t}})=\alpha(\sum_{i=1}^{k}\tilde{\lambda}_{i})+\beta(\sum_{i>k}\tilde{\lambda}_{i})$.

For $\alpha>1,\beta<1$, if

$\displaystyle\frac{\sum_{i>k}\lambda_{i}}{\sum_{i=1}^{k}\lambda_{i}}<\frac{\alpha-1}{1-\beta}$

then we have that
$\mathrm{tr}(\Sigma_{\mathsf{s}})<\mathrm{tr}(\Sigma_{\mathsf{t}})$ and if the
inequality is flipped then we obtain
$\mathrm{tr}(\Sigma_{\mathsf{s}})>\mathrm{tr}(\Sigma_{\mathsf{t}})$.

For $\alpha<1,\beta>1$, if

$\displaystyle\frac{\sum_{i=1}^{k}\lambda_{i}}{\sum_{i>k}\lambda_{i}}<\frac{\beta-1}{1-\alpha}$

then we have that
$\mathrm{tr}(\Sigma_{\mathsf{s}})<\mathrm{tr}(\Sigma_{\mathsf{t}})$ and if the
inequality is flipped then we obtain
$\mathrm{tr}(\Sigma_{\mathsf{s}})>\mathrm{tr}(\Sigma_{\mathsf{t}})$.

###  H.2 Proof of beneficial and malignant shifts for simple shifts

We restate the theorem for ease. See 3.4

###### Proof.

From Theorem 3.1 and Theorem 3.3, we have that for a universal constant $b>1$
if $\rho_{k}\geq b$ we get the following upper and lower bounds on the out-of-
distribution variance for some constants $c_{1}$, $c_{2}$,

$\displaystyle V_{ood}$ $\displaystyle\leq
c_{1}\left(\frac{1}{n}\sum_{i=1}^{k}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}+n\frac{\sum_{i>k}\tilde{\lambda}_{i}\lambda_{i}}{(\sum_{i>k}\lambda_{i})^{2}}\right)$
$\displaystyle V_{ood}$ $\displaystyle\geq
c_{2}\left(\frac{1}{n}\sum_{i=1}^{k}\frac{\tilde{\lambda}_{i}}{\lambda_{i}}+n\frac{\sum_{i>k}\tilde{\lambda}_{i}\lambda_{i}}{(\sum_{i>k}\lambda_{i})^{2}}\right).$

Analogously, the in-distribution variance is upper and lower bounded by,

$\displaystyle V_{id}$ $\displaystyle\leq
c_{1}\left(\frac{k}{n}+\frac{n}{R_{k}}\right)$ $\displaystyle V_{id}$
$\displaystyle\geq c_{2}\left(\frac{k}{n}+\frac{n}{R_{k}}\right)$

where $R_{k}=(\sum_{i>k}\lambda_{i})^{2}/\sum_{i>k}\lambda_{i}^{2}$.

Let $\Sigma_{\mathsf{s}}$ be any source covariance model that satisfies benign
source conditions. Define $\Sigma_{\mathsf{t}}$ by,

$\displaystyle\tilde{\lambda}_{i}=\begin{cases}\alpha\lambda_{i},\quad i\leq
k\\\ \beta\lambda_{i},\quad i>k\end{cases}$

for $\alpha,\beta\geq 0$.

#### Beneficial shifts.

We use the upper bound to specify requirements for the beneficial shifts.

$\displaystyle V_{ood}$ $\displaystyle\leq
c_{1}\left(\alpha\frac{k}{n}+\beta\frac{n}{R_{k}}\right)$
$\displaystyle=V_{id}+c_{1}\left(\frac{k}{n}(\alpha-1)+\frac{n}{R_{k}}(\beta-1)\right).$

Let $\alpha>1,\beta<1$. To obtain a beneficial shift in this setting we need,

$\displaystyle\frac{n}{R_{k}}(1-\beta)$ $\displaystyle>\frac{k}{n}(\alpha-1)$
$\displaystyle\Rightarrow\frac{n}{R_{k}}$
$\displaystyle>\frac{k}{n}\left(\frac{\alpha-1}{1-\beta}\right).$

In the case $\alpha<1,\beta>1$, to obtain a beneficial shift we need,

$\displaystyle\frac{n}{R_{k}}(\beta-1)$ $\displaystyle<\frac{k}{n}(1-\alpha)$
$\displaystyle\Rightarrow\frac{n}{R_{k}}$
$\displaystyle<\frac{k}{n}\left(\frac{1-\alpha}{\beta-1}\right).$

In the case where $\alpha=1$ then any $\beta<1$ leads to beneficial shifts.
Similarly when $\beta=1$, any $\alpha<1$ leads to beneficial shifts.

#### Malignant shifts.

We use the lower bound to specify requirements for the malignant shift.

$\displaystyle V_{ood}$ $\displaystyle\geq
c_{2}\left(\alpha\frac{k}{n}+\beta\frac{n}{R_{k}}\right)$
$\displaystyle=V_{id}+c_{2}\left(\frac{k}{n}(\alpha-1)+\frac{n}{R_{k}}(\beta-1)\right).$

Let $\alpha<1$ and $\beta>1$. To obtain a malignant shift in this setting we
need,

$\displaystyle\frac{n}{R_{k}}>\frac{k}{n}\left(\frac{1-\alpha}{\beta-1}\right).$

In the case of $\alpha>1,\beta<1$, to obtain a malignant shift we need,

$\displaystyle\frac{n}{R_{k}}<\frac{k}{n}\left(\frac{\alpha-1}{1-\beta}\right).$

In the case where $\alpha=1$ then any $\beta>1$ leads to malignant shifts.
Similarly when $\beta=1$, any $\alpha>1$ leads to malignant shifts.

#### Mild and severe overparameterization.

We see that the four cases separate into settings in which we are mildly
overparameterized, meaning

$\displaystyle\frac{n}{R_{k}}>\frac{k}{n}\left|\frac{\alpha-1}{1-\beta}\right|,$

and settings in which we are severely overparamterized, meaning

$\displaystyle\frac{n}{R_{k}}<\frac{k}{n}\left|\frac{\alpha-1}{1-\beta}\right|.$

In each of these regimes of overparameterization, the above proof has
delineated whether we achieve beneficial or malignant shifts in all settings
of $\alpha,\beta$. ∎

###  H.3 Generalized (necessary) conditions for beneficial and malignant
shifts

Let $\Sigma_{\mathsf{s}}$ be any source covariance matrix that satisfies
benign source conditions and define $\Sigma_{\mathsf{t}}$ as

$\displaystyle\tilde{\lambda}_{i}=\begin{cases}\alpha_{i}\lambda_{i}\qquad
i\leq k,\\\ \beta_{i}\lambda_{i}\qquad i>k\end{cases}$

with $\alpha_{i},\beta_{i}\geq 0$ for all $i$.

Then the OOD variance upper bound is given by,

$\displaystyle V_{ood}$ $\displaystyle\leq
c_{1}\left(\frac{1}{n}\sum_{i=1}^{k}\alpha_{i}+n\frac{\sum_{i>k}\beta_{i}\lambda_{i}^{2}}{(\sum_{i>k}\lambda_{i})^{2}}\right)$
$\displaystyle=V_{id}+c_{1}\left(\frac{(\sum_{i=1}^{k}\alpha_{i})-k}{n}+n\frac{\sum_{i>k}\lambda_{i}^{2}(\beta_{i}-1)}{(\sum_{i>k}\lambda_{i})^{2}}\right)$
$\displaystyle=V_{id}+c_{1}\left(\frac{k}{n}\left(\frac{\sum_{i=1}^{k}\alpha_{i}}{k}-1\right)+\frac{n}{R_{k}}\left(\frac{\sum_{i>k}\beta_{i}\lambda_{i}^{2}}{\sum_{i>k}\lambda_{i}^{2}}-1\right)\right),$

and the OOD variance lower bound is given by,

$\displaystyle V_{ood}$ $\displaystyle\geq
c_{2}\left(\frac{1}{n}\sum_{i=1}^{k}\alpha_{i}+n\frac{\sum_{i>k}\beta_{i}\lambda_{i}^{2}}{(\sum_{i>k}\lambda_{i})^{2}}\right)$
$\displaystyle=V_{id}+c_{2}\left(\frac{(\sum_{i=1}^{k}\alpha_{i})-k}{n}+n\frac{\sum_{i>k}\lambda_{i}^{2}(\beta_{i}-1)}{(\sum_{i>k}\lambda_{i})^{2}}\right)$
$\displaystyle=V_{id}+c_{2}\left(\frac{k}{n}\left(\frac{\sum_{i=1}^{k}\alpha_{i}}{k}-1\right)+\frac{n}{R_{k}}\left(\frac{\sum_{i>k}\beta_{i}\lambda_{i}^{2}}{\sum_{i>k}\lambda_{i}^{2}}-1\right)\right),$

where $V_{id}$ is the ID variance bound.

Again, we use the upper bounds to prove conditions for beneficial shifts and
the lower bounds to prove conditions for malignant shifts.

#### Beneficial shifts.

From the upper bound we consider two separate cases for non-trivial beneficial
shifts:

  1. 1.

$\sum_{i=1}^{k}\alpha_{i}<k$ and
$\sum_{i>k}\beta_{i}\lambda_{i}^{2}>\sum_{i>k}\lambda_{i}^{2}$,

  2. 2.

$\sum_{i=1}^{k}\alpha_{i}>k$ and
$\sum_{i>k}\beta_{i}\lambda_{i}^{2}<\sum_{i>k}\lambda_{i}^{2}$.

We start with the case of $\sum_{i=1}^{k}\alpha_{i}<k$ and
$\sum_{i>k}\beta_{i}\lambda_{i}^{2}>\sum_{i>k}\lambda_{i}^{2}$. If this is
satisfied, the only way to achieve a beneficial shift is if

$\displaystyle\frac{n}{R_{k}}\left(\frac{\sum_{i>k}\beta_{i}\lambda_{i}^{2}}{\sum_{i>k}\lambda_{i}^{2}}-1\right)<\frac{k}{n}\left(1-\frac{\sum_{i=1}^{k}\alpha_{i}}{k}\right).$
(22)

We also have in this setting that,

$\displaystyle 0<1-\frac{\sum_{i=1}^{k}\alpha_{i}}{k}\leq 1.$

In Equation 22 we see a notion of severe overparameterization that leads to
beneficial shifts. For instance as $R_{k}\to\infty$ we see the left-hand-side
(LHS) of Equation 22 $\to 0$. So as $R_{k}\to\infty$ we have that finite $n$
always leads to a beneficial shift in this setting. We note that equivalently
if $\beta_{i}=1$ for all $i$ then we also have the LHS $\to 0$, just as in the
case of severe overparameterization. We will return to the definitions of mild
and severe overparameterization for arbitrary shifts after showing the
remaining conditions for beneficial and malignant shifts.

Now consider the case of $\sum_{i=1}^{k}\alpha_{i}>k$ and
$\sum_{i>k}\beta_{i}\lambda_{i}^{2}<\sum_{i>k}\lambda_{i}^{2}$. If this is
satisfied, the only way to achieve a beneficial shift is if

$\displaystyle\frac{n}{R_{k}}\left(1-\frac{\sum_{i>k}\beta_{i}\lambda_{i}^{2}}{\sum_{i>k}\lambda_{i}^{2}}\right)>\frac{k}{n}\left(\frac{\sum_{i=1}^{k}\alpha_{i}}{k}-1\right).$
(23)

In this setting it is clear that

$\displaystyle
0<1-\frac{\sum_{i>k}\beta_{i}\lambda_{i}^{2}}{\sum_{i>k}\lambda_{i}^{2}}\leq
1.$

In Equation 23, it is clear that we have a notion of mild overparameterization
that leads to beneficial shifts. As above if $\alpha_{i}=1$ for all $i$ then
we always obtain a beneficial shift in this setting. Otherwise if $R_{k}$ does
not grow too quickly (as in the case with mild overparameterization) then this
is a necessary condition to achieve beneficial shifts when
$\sum_{i>k}\beta_{i}\lambda_{i}^{2}<\sum_{i>k}\lambda_{i}^{2}$.

#### Malignant shifts.

From the lower bound we once again consider two separate cases for non-trivial
malignant shifts:

  1. 1.

$\sum_{i=1}^{k}\alpha_{i}>k$ and
$\sum_{i>k}\beta_{i}\lambda_{i}^{2}<\sum_{i>k}\lambda_{i}^{2}$,

  2. 2.

$\sum_{i=1}^{k}\alpha_{i}<k$ and
$\sum_{i>k}\beta_{i}\lambda_{i}^{2}>\sum_{i>k}\lambda_{i}^{2}$.

We start with the case of $\sum_{i=1}^{k}\alpha_{i}>k$ and
$\sum_{i>k}\beta_{i}\lambda_{i}^{2}<\sum_{i>k}\lambda_{i}^{2}$. If this is
satisfied then the only way to achieve a malignant shift is if,

$\displaystyle\frac{n}{R_{k}}\left(1-\frac{\sum_{i>k}\beta_{i}\lambda_{i}^{2}}{\sum_{i>k}\lambda_{i}^{2}}\right)<\frac{k}{n}\left(\frac{\sum_{i=1}^{k}\alpha_{i}}{k}-1\right).$
(24)

In the case of $\sum_{i=1}^{k}\alpha_{i}<k$ and
$\sum_{i>k}\beta_{i}\lambda_{i}^{2}>\sum_{i>k}\lambda_{i}^{2}$ the only way to
achieve a malignant shift is if,

$\displaystyle\frac{n}{R_{k}}\left(\frac{\sum_{i>k}\beta_{i}\lambda_{i}^{2}}{\sum_{i>k}\lambda_{i}^{2}}-1\right)>\frac{k}{n}\left(1-\frac{\sum_{i=1}^{k}\alpha_{i}}{k}\right).$
(25)

We now are ready to define mild and severe overparameterization for arbitrary
multiplicative shifts.

######  Theorem H.1.

(Mild and severe overparameterization for arbitrary multiplicative shifts) Let
$\Sigma_{\mathsf{s}}$ be any source covariance matrix that satisfies benign
source conditions, meaning $\exists\ k$ such that $\rho_{k}\geq b$ for a
universal constant $b>1$. Furthermore, let $\Sigma_{\mathsf{t}}$ be defined by
$\tilde{\lambda}_{i}=\alpha_{i}\lambda_{i}$ for $i\leq k$ and
$\tilde{\lambda}_{i}=\beta_{i}\lambda_{i}$ for $i>k$.

We will define

$\displaystyle
C:=\left|\left(\frac{\sum_{i=1}^{k}\alpha_{i}}{k}-1\right)\left(1-\frac{\sum_{i>k}\beta_{i}\lambda_{i}^{2}}{\sum_{i>k}\lambda_{i}^{2}}\right)^{-1}\right|.$

Then we are mildly overparameterized if

$\displaystyle\frac{n}{R_{k}}=\omega\left(C\frac{k}{n}\right)$

and we are severely overparameterized if

$\displaystyle\frac{n}{R_{k}}=o\left(C\frac{k}{n}\right).$

We now state our taxonomy of covariate shifts for arbitrary multiplicative
shifts.

######  Theorem H.2.

(Beneficial and Malignant (Arbitrary) Multiplicative Shifts on Variance) Let
$\Sigma_{\mathsf{s}}$ be any source covariance matrix that satisfies benign
source conditions, meaning $\exists\ k$ such that $\rho_{k}\geq b$ for a
universal constant $b>1$. Furthermore, let $\Sigma_{\mathsf{t}}$ be defined by
$\tilde{\lambda}_{i}=\alpha_{i}\lambda_{i}$ for $i\leq k$ and
$\tilde{\lambda}_{i}=\beta_{i}\lambda_{i}$ for $i>k$.

  1. 1.

If $\sum_{i=1}^{k}\alpha_{i}\leq k$ and
$\sum_{i>k}\beta_{i}\lambda_{i}^{2}<\sum_{i>k}\lambda_{i}^{2}$ then we obtain
a beneficial shift.

  2. 2.

If $\sum_{i=1}^{k}\alpha_{i}<k$ and
$\sum_{i>k}\beta_{i}\lambda_{i}^{2}\leq\sum_{i>k}\lambda_{i}^{2}$ then we
obtain a beneficial shift.

  3. 3.

If $\sum_{i=1}^{k}\alpha_{i}\geq k$ and
$\sum_{i>k}\beta_{i}\lambda_{i}^{2}>\sum_{i>k}\lambda_{i}^{2}$ then we obtain
a malignant shift.

  4. 4.

If $\sum_{i=1}^{k}\alpha_{i}>k$ and
$\sum_{i>k}\beta_{i}\lambda_{i}^{2}\geq\sum_{i>k}\lambda_{i}^{2}$ then we
obtain a malignant shift.

  5. 5.

If we are in the mildly overparameterized regime:

     * •

$\sum_{i=1}^{k}\alpha_{i}>k$ and
$\sum_{i>k}\beta_{i}\lambda_{i}^{2}<\sum_{i>k}\lambda_{i}^{2}$ leads to
beneficial shifts,

     * •

$\sum_{i=1}^{k}\alpha_{i}<k$ and
$\sum_{i>k}\beta_{i}\lambda_{i}^{2}>\sum_{i>k}\lambda_{i}^{2}$ leads to
malignant shifts.

  6. 6.

If we are in the severely overparameterized regime:

     * •

$\sum_{i=1}^{k}\alpha_{i}<k$ and
$\sum_{i>k}\beta_{i}\lambda_{i}^{2}>\sum_{i>k}\lambda_{i}^{2}$ leads to
beneficial shifts,

     * •

$\sum_{i=1}^{k}\alpha_{i}>k$ and
$\sum_{i>k}\beta_{i}\lambda_{i}^{2}<\sum_{i>k}\lambda_{i}^{2}$ leads to
malignant shifts.

##  Appendix I Experiment details

###  I.1 Synthetic data experiments

Our synthetic data experiments use source data generated from random Gaussians
with covariance structures that are known to exhibit benign overfitting. These