Benign Overfitting in Out-of-Distribution Generalization of Linear Models
Authors: Shange Tang
Jiayun Wu
Jianqing Fan
Chi Jin
Venue: ICLR 2025 Poster (2025)
Keywords: Over-parameterization
benign overfitting
OOD generalization
principal component regression
minimum norm interpolation
ridge regression
Primary area: learning theory
TL;DR: We provide non-asymptotic guarantees of over-parameterized ridge regression under general covariate shift.

Abstract: Benign overfitting refers to the phenomenon where an over-parameterized model fits the training data perfectly, including noise in the data, but still generalizes well to the unseen test data. While prior work provides some theoretical understanding of this phenomenon under the in-distribution setup, modern machine learning often operates in a more challenging Out-of-Distribution (OOD) regime, where the target (test) distribution can be rather different from the source (training) distribution. In this work, we take an initial step towards understanding benign overfitting in the OOD regime by focusing on the basic setup of over-parameterized linear models under covariate shift. We provide non-asymptotic guarantees proving that benign overfitting occurs in standard ridge regression, even under the OOD regime when the target covariance satisfies certain structural conditions. We identify several vital quantities relating to source and target covariance, which govern the performance of OOD generalization. Our result is sharp, which provably recovers prior in-distribution benign overfitting guarantee (Tsigler & Bartlett, 2023), as well as under-parameterized OOD guarantee (Ge et al., 2024) when specializing to each setup. Moreover, we also present theoretical results for a more general family of target covariance matrix, where standard ridge regression only achieves a slow statistical rate of $\mathcal{O}(1/\sqrt{n})$ for the excess risk, while Principal Component Regression (PCR) is guaranteed to achieve the fast rate $\mathcal{O}(1/n)$, where $n$ is the number of samples.

Published as a conference paper at ICLR 2025
BENIGN OVERFITTING IN OUT-OF-DISTRIBUTION GENERALIZATION OF LINEAR MODELS
Shange Tang*
Jiayun Wu
Jianqing Fan
Chi Jin
ABSTRACT
Benign overfitting refers to the phenomenon where wer-paramettrrize model fits the training data perfectly, including noise in the data, but still generalizes well the unseen test data. While prior work provides some theoretical understanding of this phenomenon under the in-distribution setup, modern machine learning of- ten operates more challenging Out-of-Distribune target (test) distribution can be rather different from the source (training) distribu- tion. In this work, we take an initial step towards understanding benign overfitting in the OOD regime by focusing models under covariate shift. We provide non-asymptotic guarantees proving that benign overfitting occurs in standard ridge regression, even under the OOD regime when the target covariance satisfies certain structural conditions. We identify sev- eral vital quantities relating to source and target covariance, which govern the performance of OOD generalization. Our result is sharp, which provably recov- ers prior in-distribution benign overfitting guarantec (Tsigler & Bartlett, 2023), as well as paddr-pprameterizedd OOD guarantee (Ge et al., 2024) when specializing to each setup. Moreover, we also present theoretical results for a more general family of target covariance matrix, where standard ridge regression only achieves a slow statistical rate of ((1//n) for the excess risk, while Principal Component Regression (PCR) is guaranteed to achieve the fast rate O(1/n), where is the number of samples.
(OOD) regime, where the
the basic setup of perrpaartttteeeedd linear
INTRODUCTION
In modern machine learning, distribution shift has become a ubiquitous challenge where models trained on source data distribution are tested on different target distribution (Zou et al., 2018; Hendrycks Dietterich, 2019; Guan & Liu, 2021; Koh et al., 2021). Generalization under distribu- tion shift, known as Dutttf-Distribution (OOD) generalization. remains a fundamental issue in the practical application of machine learning (Recht al., 2019; Hendrycks et al., 2021; Miller et al., 2021; Wenzel et al., 2022). While there has been extensive work on the theoretical understanding of OOD generalization, most it has focused on mnder-parameterizes models (Shimodaira, 2000; Lei et al., 2021; Ge et al., 2024; Zhang et al., 2022). However, wee-parameteriied models, such as deep neural networks and large language models (LLMMs) in the fine-tuning stage, which have more parameters than training samples, are widely used in modern machine learning. Surprisingly, despite the classic bias- variance tradeoff for under-paramne mnder-parameterized models, over- pwe-paaramteriie models tend overfit the data while still achieving strong in-distribution generalization, phenomenon known as benign overfitting (Hastie et al., 2022; Shamir, 2023) or harmless interpolation (Muthukumar al., 2020). Therefore, it crucial to theoretically understand how benign overfitting shapes OOD generalization in over parameterized models.
is established in wverparaaettrrieer models that "benign overfitting" occurs when the data essen- tially resides on low-dimensional manifold. The manifold assumption (Belkin & Niyogi, 2003) is widely applicable across image, speech, and language data, where although features are embedded
They contributed equally and are listed alphabetical order.
Department of Operations Research and Financial Engineering, Princeton University:
(shangetang, iqfan] @princeton.edu Department of Computer Science and Technology, Tsinghua University; jiayun ftayun.wu.wok wo. @ gmail.com 6 Department of Electrical and Computer Engineering, Princeton University; chij @princeton.edu

---

Published as a conference paper at ICLR 2025
in digh-dimennional ambient space, their generation is governed by a few degrees of freedom im- posed by physical constraints (Niyogi, 2013). Specifically, the covariance matrix of the data should be characterized by several major directions corresponding large eigenvalues, while the remaining directions are high-dimensional but associated with small eigenvalues. In this setting, even though the estimator may overfit the noise in the low-variance directions, it can still capture the signal along the major directions while the noise is dampened in the minor directions. Recent -on-asymiiotic analyses have provided upper bounds on the excess risk for the minimum-norm interpolant and over- parameterized ridge estimator under this framework (Bartlett et al., 2020; Hastie et al., 2022; Tsigler & Bartlett, 2023).
However, a theoretical understanding of OOD generalization in pwrrpparaeeterized models remains elusive. In this paper, we take an initial step towards characterizing OOD generalization over- parameterized models under general covariate shift, a standard assumption in the OOD regime (Ben- David et al., 2006), where the conditional distribution of the outcome given the covariates remains invariant. We derive the first vanishing, non-asymptotic excess risk bound for ridge regression and minimum-norm interpolation, assuming that the source covariance is dominated by a few major eigenvalues. which satisfies the in-distribution benign overfitting condition. Notably, target covariance to be arbitrary. This result stands in contrast to recent work that either addresses only restrictive type of target covariance matrices (Hao al., 2024; Mallinar al., 2024) or provides excess risk bounds that are non-vanishing (Tripuraneni et al., 2021a; Hao et al., 2024).
allow the
In summary, our excess risk bound identifies several key quantities that relate the source and target covariance. We show that "benign overfitting" occurs in case 1 where the target distribution data lies on the low-dimensional manifold of the source distribution, that these key quantities are well controlled. In the opposite case 2, where the target distribution data falls outside of the low- dimensional manifold of the source. ridge regression may incur large excess risk, lower bounded by the slow statistical rate of (l1/vn). In contrast, we show that Principal Component Regression (PCR) achieves the fast rate of ((1nn) in case 2. The non-asymptotic rates of both ridge regression and PCR are validated through simulation experiments on multivariate Gaussian data in Appendix A.
Our contributions.
1. We provide a sharp, instance-dependent excess risk bound for over-parameterried ridge regres- sion under covariate shift (Theorem 2). Our result applies to any target distribution, requiring only that the source covariance be dominated by few major eigenvectors and that the minor components are high-dimensional. Our results shows that when certain key quantities relating to the source and target distributions are bounded (case 1), ridge regression exhibits "benign over- fitting", achieving excess risk comparable to the in-distribution case. Importantly, this condition requires that the overall magnitude of the target covariance along the minor directions scales similarly to, or smaller than, that of the source, but it does not depend on the spectral structure of the target covariance on the minor directions. Our results recover the in-distribution bound from Tsigler& & Bartlett (2023) when the source and target match and also recover the sharp bound from Ge et al. (2024) for under-parameterized linear regression under covariate shift when the minor components vanish.
2. For case 2 where the "benign-overfftting" of ridge regression is not guaranteed (when target distribution exhibits significant variance in the minor directions), we further show that ridge regression incurs a higher error rate compared the in-distribution case, lower bounded by the slow statistical rate of O /R) in certain instances (Theorem 4). However, we demonstrate that Principal Component Regression ensures a fast rate of O(1 (1//)) in these cases, provided that the true signal primarily lies in the major directions of the source (Theorem 5). Additionally, PCR does not rely on the minor directions of the source distribution being high-dimensional, highlighting its advantage over ridge regression in such settings.
1.1 RELATED WORK
Over- paramaeerizaaiionn The success of over-parameterizee models in machine learning has sparked significant research on their theoretical foundations. Harmless interpolation (Muthukumar et al.. 2020) or benign overfitting (Shamir, 2023) describes cases where linear models interpolate noise yet still generalize well. Double descent in prediction error is also observed as the ambient dimension surpasses the number of training samples (Nakkiran, 2019; Xu & Hsu, 2019).
2

---

Published as a conference paper at ICLR 2025
Research in this field can be divided into two categories based assumptions about the spectral structure of the sample covariance. The first category assumes an almost isotropic sample covari- ance matrix with a bounded condition number or an isotropic prior distribution of parameters (Belkin et al., 2020), allowing for asymptotic risk bounds (Dobriban & Wager, 2018; Richards et al., 2021). However, ridgeless regression is sub-optimal in this setting unless the signal-to-noise ratio is in- finite (Wu & Xu, 2020), and non-asympiotic error bounds are lacking. Our work falls into the second category, focusing on the covariance model where a small number of eigenvalues dominate the sample covariance, and the signal is concentrated in the subspace spanned by the leading eigen- vectors (Bibas et al., 2019; Chinot & Lerasle, 2022; Hastie et al., 2022: Silin & Fan, 2022). Linear regression can be optimal without regularization under this covariance structure (Kobak et al., 2020), which is of practical interest because ridgeless regression is equivalent as gradient descent from zero initialization (Zhou et al., 2020). Sharp non-asymptotic bounds for variance and bias in ridge and ridgeless regression have been derived (Bartlett et al., 2020; Tsigler & Bartlett, 2023).
Extending the analysis of ridgeless estimators (i.e., minimum norm interpolants), uniform conver- gence bounds for generalization error have been studied for all interpolants with arbitrary norms. However, uniformly bounding the difference between population and empirical enrors generally fails to ensure a consistent predictor (Zhou et al., 2020), necessitating strong assumptions on dis- tributions (Koehler et al., 2021) or hypothesis classes (Negrea et al., 2020). Over-paramettriizatoon theory for linear models has also been applied to two-layer neural networks approximated via kernel ridge regression (Liang et al., 2020: Ghorbani et al., 2020: 2021: Bartlett et al., 2021; Mei & Monta- nari, 2022; Mei et al., 2022; Montanari & Zhong, 2022: Simon et al., 2023), though this lies beyond the scope of the present work.
Out-of-Distributiin generalization. Out-of-distribution generalization is well studied for under- parameterized models, especially under the setup of covariate shift. Shimodaira (2000) pointed out that vanilla MLE (Empirical Risk Minimization, ERM) is asymptotically optimal among all the weighted likelihood estimators when the model is well-speeified. For non-asymptotic results, Cortes et al. (2010); Agapiou et al. (2017), provide risk bounds for importance weighting. Another line of work provides non-asymptotic analyses for covariate shift, focusing on linear regression or a few specific models such as one-hidden layer neural network (Mousavi Kalan et al., 2020; Lei et al., 2021; Zhang et al., 2022). Most recently Ge et al. (2024) provides tight non-asymptotic analysis for general well-specified parametric models, showing that even without target data, vanilla MLE (Empirical Risk Minimization, ERM) is minimax optimal with a sharp 1/n excess risk bound based on Fisher information.
Research on over-parameterinn models under distribution shift has largely focused on covariate shifts in linear regression. Importance weighting for over- rrre-paramtteiieed models (Chen et al., 2024) and general sample reweighting offer no advantage over ERM since both converge to the same esti- mator via gradient descent (Zhai al., 2022). Consequently, much literature focuses on minimum- norm interpolation as the natural ERM solution. For isotropic covariance structure, Tripuraneni et al. (2021a) derive an asymptotic generalization bound decreasing with d/n where d represents the data dimension. Most related to our work, line of work also consider the covariance model dominated by several major eigenvectors, however, they only address a restrictive form of covariate shift or obtaining non-vanishing bound: Kausik et al. (2024) study a linear model with additive noise on covariates when data strictly lies in a low-dimensional subspace, showing a non-vanishing bound. Hao et al. (2024) give a non-vanishing bound for the case where features are translated by a con- stant and the covariance matrix is preserved. Mallinar et al. (2024) investigate the special case with independent covariates and simultaneously diagonal source and target covariance matrices, under which the in-distribution analysis of Bartlett et al. (2020); Tsigler & Bartlett (2023) can be directly extended. Still, their estimation bias bound is looser than ours, as exhibits gap compared to Tsigler & Bartlett (2023)'s sharp bound even when the source and target distributions are aligned. In contrast, our work achieves the first vanishing aon-asympootic error bound for general covariate shift, assuming only finite second moments for the target covariance matrix.
Another line of research considers non-parametric models under covariate shift (Kpotufe & Mar- tinet, 2018; Hanneke & Kpotufe, 2019; Pathak et al., 2022; Ma et al., 2023), presenting minimax results governed by transfer- expsoet- that measures the similarity between source and target dis- tributions. However, this falls outside the scope of our work.
3

---

Published as a conference paper at ICLR 2025
Principal Component Regression. Principal Component Regression (PCR) has been designed to treat multicollinearity in high-dimensional linear regression, where the covariates possess a latent, Low-dimensional representation (Massy, 1965; Jeffers, 1967; Jolliffe, 1982; Jeffers, 1981). PCR has been widely used in statistics (Liu et al., 2003; Fan et al., 2021; Fan & Gu, 2023), econometrics (Stock & Watson, 2002; Bai & Ng, 2002; Fan al., 2020), chemometries (Næs & Martens, 1988; Sun, 1995; Vigneau et al., 1997; Depczynski et al., 2000; Keithley et al., 2009), construction man- agement (Chan & Park, 2005), environmental science (Kumar & Goyal, 2011; Hidalgo al., 2000), signal processing (Huang & Yang, 2012) and etc.
Regarding the theory of PCR, Hadi & Ling (1998) identify conditions under which PCR will fail. Bair et al. (2006) suggest selecting principal components based on their association with the outcome and provide corresponding asymptotic consisteney results. Xu & Hsu (2019) establish asymptotic risk bounds for PCR with varying numbers of selected components k. They show that the "double descent" behavior also happens in PCR as k/d increases. Most relevant our work, Agarwal et al. (2019) derive non-asymptotic error bounds for PCR, and show that the error decays at a rate of (n) (n is the sample size), assuming all singular values of the data matrix are of similar magnitude. Agarwal et al. (2020) further improves this rate (11/n). However, both results consider a fixed design with strict low-rank assumptions, making them inapplicable to our setting of OOD generalization.
COVARIATE SHIFT SETUP UNDER OVER PARAMETERIZATION
2.1 DATA WITH COVARIATE SHIFT
We address the out-of-distribttinn (OOD) generalization of wer-pprrameterized models under variate shift, where the covariates, denoted by a random vector x E RR, follow different distribu- tions during training and evaluation. Specifically, we assume that the training data is sampled from a source distribution Ps. and the learned model is subsequently applied to data from an unknown target distribution Pr. Let the covariates be zero-mean on the source distribution, and define the covariance matrix as Σg == EpwPs xxx² Since we can always choose an orthonormal basis such that Eg becomes diagonal, we express Es = <diag(A,, ... , ,Ax) without loss of generality, where arranged in non-increasing order: A 2 > Aa 0. Moreover, we assume
the eigenvalues sub gabbssansssttyy of the source covariates, i.e., >/1/2 x is -u o-sub-gaussian where the precise definition of the sub- Gaussian norm is given in section B. We consider a general covariate distribution for the target, assuming only that it has a finite second moment, denoted by En == Eg-Py [xx'", which is not necessarily diagonal.
We consider a linear response model that remains consistent across the source and target distribu- tions. The outcome follows y x 3 + e, where 3* Rd represents the true parameter, and is an independent noise with zero-mean and variance 2
2.2 LEARNING PROCEDURE AND EVALUATION
The learning procedure involves training a linear model with n i.idd samples {(x,, y1 } drawn from the source distribution. Define X := (x,) E R Y := (y1...., yvo)" and E == (GI....,G,TT. We focus on models 3(Y') that are linear in Y, allowing us to write 3(Y) ((x 3(e). We consider ridge regression and Principal Component Regression to be two examples of such algorithms. With a regularization coefficient À 2 0, the ridge estimator is defined as
3(Y) xxxx + AIn)-'Y.
The estimator is assessed on the target distribution by its excess risk relative to the true model, expressed as the following equation:
R(3())) = F( [(V x - 1|3(Y) -1
(w-
where we define || == VxT Ar for any positive semi-defing matrix A. The metric of interest is the expected excess risk with respect to the noise, given by R.c [R(()) Following from the lin-
4

---

Published as a conference paper at ICLR 2025
earity of the model, the expected excess risk can be decomposed into bias and variance components:
(3(()) = E. 1e) + 113(x8)) - Ex'
-
where we define the variance as V == E assume the shifts only in the distribution of covariates; the regression coefficients remain the same.
| (()))
and the bias as B == ||x(x))) -33 || Here,
2.3 THE STRUCTURE OF COVARIANCE IN BENIGN OVERFITTING
Throughout this paper, we follow the convention of Tsigler & Bartlett (2023) and consider the source covariance matrix Es as characterized by a few numbers of high-variance directions and large number of low-variance directions of similar magnitude. We refer the high-variance direc- tions as "major directions" and the low-variance directions as "minor directions". We denote the number of major directions as k. For the remaining d - k minor directions, we use the following notions of effective rank to approximate the number of directions with similar scale. For the ridge regularization coefficient 2 0, we define:
X ++En
Ra = (A+ (A+ E)>
=
Ac+1
Σj>k 23
We have 1 S Th < Rg. When À = 0, it further holds that Rs S d k. We denote the first k columns X as X5 and the remaining d - columns as X- Correspondingly, we partion 3 into St and 3 The covariance matrix blocks along the diagonals denoted by Σg,k, Σs.-kr Σイ, A and Σr.-k- We define the following quantities to facilitate our presentation, which are crucial in our analysis.
T = Eg u Es,.AtETT--R V Lg
3 OVER-PARAMETERIZER RIDGE REGRESSION
In the context of in-distribution generalization, where Es Σy, for over-parameterized linear models, Bartlett et al. (2020) and Tsigler Bartlett (2023) demonstrate that the ridge estimator (with the minimum-norm interpolant as a special case) can effectively learn the signal from the subspace of data spanned by the major eigenvectors, while benignly overfitting the noise in the minor directions under certain scenarios. They argue that benign overfitting occurs when the true signal predominantly lies in the major directions, and the minor directions have a small scale but highly effective rank. This section explores whether this mechanism still holds under covariate shift. We derive upper bounds (Theorem 2) for the excess risk of the over-parameterized ridge estimator in the context of OOD generalization, demonstrating that "benign overfitting" also happens under covariate shift, given that the target distribution's is covariance remains dominated by the first dimensions. Specifically, we show that characterizes the shift in the major directions, while the overall magnitude of Σr,-k, which captures the shift in the minor directions, is crucial for benign overfitting. When the overall magnitude of Στ,- scales similarly to or smaller than those of the source, ridge regression achieves the same non-asymptotic enror rate under covariate shift as in the in-distribution setting. Surprisingly, although high effective rank the minor directions of the souree is essential for benign overfitting, only the overall magnitude matters for the target distribution.
3.1 WARM-UP: IN-DISTRIBUTION BENIGN OVERFITTING
As a warm-up, we introduce Tsigler Bartlett (2023)'s in-distribution result on benign overfitting in ridge regression. When the data dimension d exceeds the sample size n, the ridgeless estimator interpolates the training data, fitting the noise. In this case, the estimator 3 lies within the subspace spanned by the covariates the n samples. likely to be orthogonal to this subspace, ameliorating noise from affecting the prediction. Therefore, the minor components of the covariance matrix actually provide implicit regularization. Tsigler & Bartlett (2023) assume that the data lies in space with k major directions and d k weak
is much larger than n. a new test point is highly
5

---

Published as a conference paper at ICLR 2025
but essentially high-dimensional minor directions, allowing for benign overfitting. This intuition is formalized through an assumption that controls the condition number of the Gram matrix for the remaining d - k dimensions.
Assumption 1 (CondNum(k;; 6, L) (Tsigler & Bartlett, 2023)). Define matrix A AI, + X- With probability at least 1 - 8, Ag is positive definite and has a condition number no greater than L, i.e.,
(A() S SL
Phe (Ag)
where the i-th largest eigenvalue matrix is denoted by pa(().
Remark 1. This assumption essentially posits that the minor directions of the source covariance have an effective rank significantly greater than n. As evidence, Tsigler & Bartlett (2023) prove that if CondNum holds, the effective rank rh is lower bounded by n//,, up to a constant. Conversely, lower bound on the effective rank T3 also implies an upper bound of the condition number of Ag. For more details, refer to Tsigler& & Bartlett (2023, Lemma 3).
Assuming CondNum, Tsigler & Bartlett (2023) obtain sharp upper bounds for both the variance and bias of the ridge estimator, with matching lower bounds (see their Theorem 2). To facilitate the presentation, we define X = A Ej>e >j to represent the combined regularization term from both ridge and implicit regularization.
Theorem 1 (Tsigler & Bartlett (2023)). There exists constant that only depends on L, such that for any n > ck, if the assumption condNum(k; L) (Assumption is satisfied, then holds that n < crk, and with probability least
ce n/co
S
BID == 11 13
+ +1182
CU
R
where v denotes the standard deviation of the noise E.
The first variance term arises from estimating the k major signal dimensions, corresponding to the classic variance k-dimensional ordinary least squares. The second variance term, n/ Rg. vanishes when the minor directions sufficiently nigh-dimensional, i.c., when Rg >>>>>>>>>>> However, the signal in the minor directions, ||stn|ls__ is nearly lost when projected from the nigh-diimnsional ambient space onto the oow-iieesionna sample space, contributing to the second bias term. Finally, the first bias term relates to the signal estimation in the first dimensions and is introduced by the overall regularization from both ridge and implicit regularization imposed by the minor components.
3.2 CUT-O--DISTRIBUTION BENIGN OVERFITTING
We now investigate the -iitt--iistiitttion performance of the ridge estimator. Intuitively, when the minor components vanish for both the source and target distributions, weerpparameterized ridge re- gression essentially reduces to ander-parameterizee ridge regression in the major directions, achiev- ing a rate of (tr[TT) /n), as demonstrated by Ge et al. (2024). When the minor components do not vanish, high effective rank of the minor components in the source distribution is essential for "benign overfitting", as shown by Tsigler& & Bartlett (2023). However, we argue that for the target distribution, only the overall magnitude of the minor components is critical for benign overfitting. This is because when the source's 's minor directions have an effective rank much larger than n, the n-dimensional subspace spanned by the training samples is already almost orthogonal to any test point with high probability. As a result, the spectral structure of the target becomes irrelevant-only a small overall magnitude of the target's minor components is required.
We formalize those intuitive claims by deriving upper bounds for both the variance and bias of ridge regression under covariate shift, assuming a source distribution similar to the in-distribution case. Our upper bound is sharp and can be applied to any target distributions, reducing to Tsigler & Bartlett (2023)'s 's bound (Theorem 1) when the target and source distributions are aligned. Additionally, we recover Ge et al. (2024)'s sharp bound for mnder-parameterizee linear regression under a covariate shift when the high-dimensions
minor components vanish.
Theorem 2. There exists a constant >>> 2 depending only on o, L. such that for any cN < n < Tk. if the assumption condNum(k; (, 5, L) (Assumption 1) is satisfied, then with probability at least -3,,
V
k
[]
n
[r
CV2
k
R tr

---

Published as a conference paper at ICLR 2025
B s BID
(17TI)
n 12=,,=11] [2s
Tk
where T,4, V are defined in Equation (I), N Poly(k lm(1/6), X AAz"). and Poly(-) denotes a polynomial function.
Recall that BID is the bias upper bound from Theorem 1. Theorem 2 establishes an upper bound for the excess risk of ridge regression under general covariate shift, expressed in a multiplicative form based on Theorem 1. This formulation enables a straightforward comparison of the impact of covariate shifts on the bias and variance of ridge estimators relative the in-distribution case. The first conclusion is that Theorem 2 well reduces to the corresponding result in Theorem 1 when no distribution shift occurs-ie.. Es- Σr. This connection follows directly from the condition
The second conclusion that covariate shift the first l dimensions and last d A: dimensions introduce multiplicative factors of k. |[T] and te[4
[|Er-=*ll tr(V] nr 1| xll' respectively, on the excess risk. Therefore, as long as these factors are bounded by constants, over-parameterized ridge regres- sion achieves the same non-asymptotic rate of excess risk under covariate shift as the in-distribution setting. This scenario, well addressed by ridge regression, occurs when the target distribution's 's co- variance structure remains dominated by the first k dimensions. In the following, we analyze the impact of the factors introduced by covariate shifts on both the major and minor directions.
1. T characterizes the shift in the major directions. Under covariate shift within the first k di- mensions, we obtain the same non-asymptotic error rate as in Theorem I, only if [[]]] bounded by constant, / < |T||- The matrix T plays central role in Theorem 2 to quan- tify covariate shift within the first & dimensions, matching our intuition. This echoes with Ge al. (2024)'s finding that tr captures the difficulty of covariate shift for mnder-parameterizer ridgeless regression (MLE). They establish a sharp upper bound on excess risk using Fisher in- formation (see their Theorem 3.1). which simplifies to rate of ((tr[T//n) for linear models. Theorem 2 recovers this result when applied to a k-dimensional under-parameterized setting where all high-dimensional minor components vanish, specifically when Σs.-k = Dr, k O. Under the same condition as Theorem 2, for a constant depending only on a, TT, with high probability, the variance and bias terms are bounded by:
[r[T]
B
1
18
The variance bound aligns with Ge al. (2024)'s result while the bias vanishes À - 0. 2. The overall magnitude of Σr,- is crucial for benign overfitting, Under covariate shift within the last dimensions, when both achieve the same non-asymptotic eтror rate as in Theorem 1. Note that trK |EE.--ll In T
tr and n Vr
- are bounded by constants, we [[s
ir[v
other words, matching our intuition, if the overall magnitude of the minor components of tar- get covariance scales similarly to or smaller than those of the source, in terms of the covariance norms, "benign overfitting" also happens under covariate shift. Importantly, this condition does not impose constraints on the internal spectral structure of the minor components of the target covariance. For example, we do not force each eigenvalue of Σr, scale with its correspond- ing eigenvalue of Ss in decreasing order, assumed in prior work (Mallinar et al., 2024). Surprisingly, for benign overfitting to happen, the source distribution must have a high effective rank in the minor directions. However, for the target distribution, only the overall magnitude of the minor components is relevant.
Another observation is that the bias scales with nr
|Er_ meaning that we only re- [
PT. +l quire [ES O(ra/n), which is less restrictive condition for larger Tk- Thus, over- parameterization improves the robustness of the estimation bias against covariate shift in the minor direction.
Remark 2 (Sample complexity). We have assumed cN in Theorem 2. The explicit formula for N deferred to Theorem 25 and Remark Here we summarize the sample complexity required for the bound to hold. The dependence on varies between 2(k) and ((k-)), depending the
7

---

Published as a conference paper at ICLR 2025
degree of covariate shift. The optimal case, aligning with the sample complexity of classic linear regression, occurs when Σs, & Σy.x- The worst case arises when there is a significant covariate shift in the first l dimensions, such when the test data lies predominantly in the subspace of the first dimension. This variation in sample complexity under covariate shift parallels the analysis of Ge et al. (2024) (see their Theorem 4.2) for the pander-parameterizeed setting. Additionally, we require n > X + Σラ>n Aj. ensuring that the regularization is not too strong to introduce a bias exceeding a constant (as reflected in the first term of BID). On the other hand, we assume n. < Th in the theorem, consistent with the over-parameterized regime and Assumption 1, where the last d components are considered to be essentially high-dimensional.
Remark (Dependence on L). Theorem 2 does not explicitly show how the excess risk depends on the condition number L of Ag. However, we demonstrate in Theorem 25 that the upper bounds scale at most as 1.2. Notably, we maintain the same order of dependence on L. in each term of the upper bounds as in the analysis by Tsigler & Bartlett (2023) (see their Theorem 5).
Finally, Theorem 2 suggests (L//n) vanishing error under several conditions that naturally fol- low from the previous discussions, which we now state rigorously. First, the covariate space decom- poses into subspaces spanned by low-dimensional major directions and high-dimensional minor directions, with k = (1) and R2 = =-(n²). Second, the low-rank covariance structure is preserved after covariate shift, such that |[T tr|t4] - || alll
[r[2] nT'k [[g. x O(1). Third, the signal lies predomi- nantly in the major directions, with || ((1) and ||@":|| = =O(1//n) Lastly, the
regularization is not excessively strong to introduce a significant bias, with Ā = A + Ej>e = ((vn)
4 LARGE SHIFT IN MINOR DIRECTIONS
In the previous section, we established an upper bound for prrmterramteri ridge regression under covariate shift. We showed that when the shift in the minor directions is controlled spcilliciiscc.icllll..... when the overall magnitude of ΣT,- is small-""enign overfitting" also occurs under covariate shift. However, when the shift in minor directions is significant, meaning the target covariance ma- trix has many large eigenvalues with corresponding eigenveetors outside the major directions, the excess risk for ridge regression deteriorates. In this section, we further illustrate the limitations of ridge regression in such cases by providing lower bound for its performance for large distribu- tion shifts in the minor directions. We show that, in certain instances, ridge regression can only achieve the slow statistical rate of ((1/Vn) for the excess risk. On the other hand, it is natural to consider alternative algorithms to ridge regression. We demonstrate that even with large shift in the minor directions, Principal Component Regression (PCR) is guaranteed to achieve the fast statistical rate (11/n) in the same instances, provided that the signal 3* lies primarily within the subspace spanned by the major directions. Moreover, PCR does not require the minor directions to have a high effective rank in the source distribution, highlighting its advantage over ridge regres- sion in such cases. Throughout this section, we maintain the setup and source covariance structure described in Section 2. However, Assumption 1 is no longer required.
4.1 SLOW RATE FOR RIDGE REGRESSION
In this subsection, we demonstrate the limitations of ridge regression when the overall magnitude of Σy.-& is large. Consider an instance where Eg has its first l components as ((1), while the minor directions have eigenvalues of (1). If we set En Ta. in contrast to the "benign overfitting" regime described in Theorem 2, ridge regression will have a large excess risk for this instance. Although the signal from the major directions is effectively captured, the signal in the minor directions is nearly lost. Unlike the case in Section 3. here, the estimation error in the minor directions is crucial because the target distribution has significant components in these directions. We formalize this intuitive example through the following theorems:
Corollary 3. For some absolute constants C₁, C2, consider the following instance of Es:
C1 Vn
A d== 1, \+11=
A
d 0.
8

---

Published as a conference paper at ICLR 2025
Assume Σr,-k Er Ig. and 3 = O. By choosing À Vn, under the same conditions of Theorem 2, we can bound the excess risk of the ridge estimator with probability at least 36:
2 k + 1
Ee (+()))
Remark 4. Corollary is direct application of Theorem 2.
Theorem 4. Consider the same instance of Eg as in Corollary 3. Assume Ey = la and = vn.
There exists an absolute constant C' O, such that for some 0 8 1, N₂ 0 and for any n > N2, with probability at least - 8, we have V Cv²
For any X 0, with probability at least 6, the excess risk of the ridge estimator satisfies:
E. R (((3)) C An vn
From Theorem 4, we observe that when Er Ta. the performance of ridge regression deteriorates compared to the case where Στ,- constant excess risk under covariate shift while achieving Furthermore, Theorem shows no matter how we choose the regularization parameter X, the excess risk is always lower bounded by the slow statistical rate O (T), which is worse than the fast rate (11nn). However, as we will prove in the next subsection, Principal Component Regression (PCR) achieve excess risk of (11nn) under this instance, even with Ex = ld-
If we set X vn in Corollary 3, ridge regression incurs
in-distribution error rate of (1/nn).
4.2 FAST RATE FOR PRINCIPAL COMPONENT REGRESSION
Ridge regression faces significant limitations when there is large shift in the minor directions. In Section 3. was shown that the signal in the minor directions, 8 is nearly lost when projected from the high-dimensions ambient space onto the low-dimensional sample space. In other words, learning the true signal from the minor directions essentially impossible. Therefore, in this sub- section, we continue to focus on the scenario where the true signal ( primarily resides in the major directions. In this case, Principal Component Regression (PCR) emerges as a natural algorithm that estimates the space spanned by the major directions and performs regression that subspace.
Principal Component Regression (PCR).
Step Obtain an estimator Ū of the top-k subspace E.s. For simplicity, we assume a sample size 2n and use the first half the data to compute i by principal component analysis (PCA) on the sample covariance matrix Eg = 1 x. Specifically, (#i,""* .. Ux) where ū2 is the i-th eigenvector of Eg.
Step 2: Use the data projected on û to conduct linear regression. With a little abuse of notation, X E Raaxd to denote the data matrix (In+1, x2n)² and Y R denote (yn+1, yy2)) we let = xi E Bank be the projected data matrix, the estimator 3 we obtained is given by
Ü - -
Consider the scenario where the last d Is components of the true signal 8 is exactly zero, i.e., 3t, = 0. In this case, if the subspace represented by Ü perfectly matches the subspace represented
by U Ix
Rddk corresponding to the first components, then PCR performs linear regres-
sion using only the first A components of the covariates. As result, the excess risk would just be the usual variance of linear regression in the major directions. In this scenario, regardless the norm |Er,- the PCR estimator assigns coefficients of zero the last d k components, thus avoiding any large excess risk. Furthermore, if the distance between Ū and is nonzero, an additional term in the excess risk will arise due to the estimation error of Ú. We formalize this intuition with the following upper bound for the excess risk of PCR. To facilitate the presentation, measure of the estimation accuracy of t. We define A dist(U, U) = |UUT Ô ||. which represents the distance between the subspaces spanned by the columns Ú and U. Then we present the following theorem.
introduce

---

Published as a conference paper at ICLR 2025
Theorem 5. Assume 8* = If I θ, for any 0 < 8 and any N1, bound the
excess risk of PCR estimator with probability 1 ò:
Ee [T( S O
tr((T + || 1
A1
| 112)
n
where 0- 1 Po |ET||AR , (tr(()-)) and (
Ni A, Remark 5. Theorem 5 is special case of Lemma 31. For explicit formulas of θ and N1, as well upper bound for cases where 3" * 0, refer to Lemma 31 for details.
The excess risk upper bound provided by Theorem consists of two terms. The variance term tr(T)/n is incurred by the nature of linear regression on the major directions and remains unavoid- able even when the subspace estimation exact (i.e., = 0). This term also appears as the first vari- for nuderrpprrmetterized linear regression under covariate shift (Ge et al., 2024). The second term ||,3* 11 | represents the bias induced by the subspace estimation enror in Step 1, which exhibits quadratic dependence on A. By combining Theorem with a bound on A, we can derive an end-to-end excess risk upper bound of PCR. We present the following lemma control A.
ance term in Theorem 2, and exactly matches the sharp rate Lr tr|25
Er]/n 1r|>g'Er]/n
Lemma 6. With probability at least
8, if 2 r + (1/66)) we have r+1
A ASO
0 A
AA. PR--RR1
where r r =T= A is the effective rank of the entire covariance matrix Es. Remark 6. Lemma 6 shows that A depends on several quantities: the eigenvalue gap between the major and minor directions, i.e., A A and the effective rank r. We observe that A will be small if the major and minor directions are well separated, meaning λ AR+1 is large, and the minor directions relatively small compared \j-
Combining Theorem with Lemma 6, an end-to-end error bound for PCR directly follows (see The- orem 29 for detailed statement), suggesting that PCR will achieve small excess risk long the major and minor directions are well separated, and the effective rank the entire source covariance matrix is small. In contrast to ridge regression, PCR does not rely on the minor components having high effective rank. This highlights the superiority of PCR over ridge regression in certain scenarios.
As example, consider the instance in Theorem 4, where k, || A₁ A are all @ In this case, the variance term scales as 1/n, and the bias term scales as ((A2). Since r = +(1) in this instance, have A ((1/ /n). Consequently, PCR achieves ( rate in this instance, when Σ = la. Compared with the excess risk for ridge regression, which is at least 1/Vn, PCR shows its superiority against ridge regression when there is large shift in the minor directions.
5 CONCLUSION AND DISCUSSION
In conclusion, we provide an instance-dependent upper bound on the excess risk for ridge regression under general covariate shift. Our findings demonstrate that "benign overfitting" also occurs in OOD generalization when the shift in the minor directions is well controlled. We also investigate the regime with a large shift in the minor directions. where ridge regression may incur a large excess risk, whereas Principal Component Regression (PCR) exhibits superior performance.
Our work opens several directions for future research. First, while we have established a lower bound for ridge regression in certain instances, key challenge remains in deriving general lower bound that matches our upper bounds, offering more precise characterization of the excess risk under covariate shift. Second, our analysis has focused on linear models as initial step in understand- ing over-parametes parammtteette OOD problems. Extending this investigation to more complex, non-linear models would be intriguing direction for future exploration.
ACKNOWLEDGMENTSS
This work is partially supported by the National Science Foundation CAREER grant NSF-IIS- 2239297 and NSF grants DMS-2210833 and DMMS2412009,
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Sergios Agapiou, Omiros Papaspiliopoulos, Daniel Sanz-Alonso, and Andrew M Stuart. Importance sampling: Intrinsic dimension and computational cost. Statistical Science, pp. 405-431, 2017.
Anish Agarwal, Devavrat Shah, Dennis Shen, and Dogyoon Song. On robustness principal com- ponent regression. Advances in Neural Information Processing Systems, 32, 2019.
Anish Agarwal, Devavrat Shah, and Dennis Shen. On model identification and out-of-sample pre- diction of principal component regression: Applications to synthetic controls. arXiv preprint arXiv:2010.14442 2020.
Jushan Bai and Serena Ng. Determining the number of factors in approximate factor models. Econo- metrica, 10(1):191 191-221,, 2002.
Eric Bair, Trevor Hastie, Debashis Paul, and Robert Tibshirani. Prediction by supervised principal components. Journal of the American Statistical Association, 101(473):119-13,, 2006.
Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear
regression. Proceedings of the National Academy of Sciences, 117(499:30033330077 2020.
Peter L Bartlett, Andrea Montanari, and Alexander Rakhlin. Deep learning: statistical viewpoint.
Acta numerica, 30:87-201, 2021.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation, 15(6):1373- 2003.
Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. SIAM Journal on Mathematics of Data Science, 1677:186, 2020.
Shai Ben- Dev-David, John Blitzer, Koby Crammer, and Fernando Pereira. Analysis of representations for domain adaptation. Advances neural information processing systems, 19, 2006.
Koby Bibas, Yaniv Fogel, and Meir Feder. A new look at an old problem: A universal learning approach to linear regression. In 2019 IEEE International Symposium on Information Theory (ISIT), pp. 2308. IEEE, 2019.
Swee Lean Chan and Moonseo Park. Project cost estimation using principal component regression. Construction Management and Economics, 23(3):295-30) 304, 2005.
Yihang Chen, Fanghui Liu, Taiji Suzuki, and Volkan Cevher. High-dimennionall kernel methods under covariate shift: Data-dependent implicit regularization. In Forty-first International Con- ference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024. URL https: openreview net wtt.///oddnm//p/eeeeeeeeeeeeeeee
Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, et al. Spectral methods for data science: A statistical perspective. Foundations and Trends@ Machine Learning, 14(5):566-806, 2021.
Geoffrey Chinot and Matthicu Lerasle. On the robustness of the minimim 12 interpolator. Bernoulli, 2022.
Corinna Cortes, Yishay Mansour, and Mehryar Mohri. Learning bounds for importance weighting. Advances in neural information processing systems, 23, 2010.
Uwe Depczynski, VJ Frost, and K Molt. Genetic algorithms applied to the selection of factors in principal component regression. Analytica Chimica Acta, 420(2):217-25) 2000.
Edgar Dobriban and Stefan Wager. High-dimensional asymptotics of prediction: Ridge regression and classification. The Annals of Statistics, 46(1):247-279, 2018.
Jianqing Fan and Yihong Gu. Factor augmented sparse throughput deep relu neural networks for high dimensional regression. Journal of the American Statistical Association, pp. 1-15, 2023.
Jianqing Fan, Yuan Ke, and Kaizheng Wang. Factor cactor-adjjsted regularized model selection. Journal
of Econometrics, 216(1):71-88 2020.
11

---

Published as a conference paper at ICLR 2025
Jianqing Fan, Kaizheng Wang, Yiqiao Zhong, and Ziwei Zhu. Robust high dimensional factor models with applications to statistical machine learning. Statistical science: a review journal of the Institute of Mathematical Statistics, 36(2):303, 2021.
Jiawei Ge, Shange Tang, Jianqing Fan, and Chi Jin. On the provable advantage of unsupervised pretraining. arXiv preprini arXiv:2303.01566 2023.
Jiawei Ge, Shange Tang, Jianqing Fan, Cong Ma, and Chi Jin. Maximum likelihood estimation is all you need for well-specified covariate shift. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024. URL net [orum?Ld=ecTCcKO0
uttps://openrewe
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. When do neural networks outperform kernel methods? Advances in Neural Information Processing Systems, 33: 14820-14830, 2020.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari, Linearized two-layers neural networks in high dimension. The Annals of Statistics, 49(2), 2021.
Hao Guan and Mingxia Liu. Domain adaptation for medical image analysis: survey. IEEE Trans- actions Biomedical Engineering, 69(3): 2021.
Ali S Hadi and Robert Ling. Some cautionary notes on the use of principal components regression. The American Statistician, 52(1):15-19, 1998.
Steve Hanneke and Samory Kpotufe. On the value of target data in transfer learning. Advances in Neural Information Processing Systems, 32, 2019.
Yifan Hao, Yong Lin, Difan Zou, and Tong Zhang. On the benefits of over-parameterizaaion for out- of-distribution generalization. CoRR, abs/2403. 2024. doi: 1048550ARXXW.248811339
URL https: /oi.....////// httpe//.//////.////...........
(wt.55//arxiiv.. 2403. 1799.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high-
dimensional ridgeless least squares interpolation. Annals of statistics, 50(2):949, 2022.
Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness to common ruptions and perturbations. arXiv preprint arXiv 2019.
Dan Hendrycks, Steven Basart, Norman Mu, Saurav Kadavath, Frank Wang, Evan Dorundo, Rahul Desai, Tyler Zhu, Samyak Parajuli, Mike Guo, et al. The many faces of robustness: A criti- cal analysis of out-of-distribution generalization. In Proceedings of the IEEE/CVF international conference on computer vision, pp.
2021.
Hugo G Hidalgo, Thomas C Piechota, and John A Dracup. Alternative principal components re- gression procedures for dendrohydrologie reconstructions, Water Resources Research, 36(11) 1): 3241-3249, 2000.
Shih-Ming Huang and Jar-Ferr Yang. Improved principal component regression for face recognition under illumination variations. IEEE signal processing letters, 19(4):179-182 2012.
JNR Jeffers. Investigation of alternative regressions: Some practical examples. Journal of the Royal Statistical Society. Series D (The Statistician), 30(2):79-88, 1981.
John NR Jeffers. Two case studies in the application of principal component analysis. Journal of the Royal Statistical Society: Series C (Applied Statistics), 16(3):225 1967.
Ian T Jolliffe. A note the of principal components in regression. Journal of the Royal Statistical Society Series C: Applied Statistics, 31(3):300-333 1982.
Chinmaya Kausik, Kashvi Srivastava, and Rishi Sonthalia. Double descent and overfitting under noisy inputs and distribution shift for linear denoisers. Trans. Mach. Learn. Res., 2024, 2024. URL httpss///ppereve/ net forum?
net/forumm ddd.
12

---

Published as a conference paper at ICLR 2025
Richard B Keithley, R Mark Wightman, and Michael L Heien. Multivariate concentration determi- nation using principal component regression with residual analysis. TrAC Trends in Analytical Chemistry, 28(9))1112228
2009.
Dmitry Kobak, Jonathan Lomond, and Benoit Sanchez. The optimal ridge penalty for real-world high-dimensional data can be zero or negative due to the implicit ridge regularization. Journal of Machine Learning Research, 21 21(169):1-16, 2020.
Frederic Koehler, Lijia Zhou, Danica J Sutherland, and Nathan Srebro. Uniform convergence of interpolators: Gaussian width, norm bounds and benign overfitting. Advances in Neural Informa- tion Processing Systems, 34:20657-20666 2021.
Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Bal- subramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, et al. Wilds: A benchmark of in willhe-wild distribution shifts. In International conference machine learning, pp. 5637-5664. PMLR, 2021.
Samory Kpotufe and Guillaume Martinet. Marginal singularity, and the benefits of labels in covariate-shift. Conference On Leurning Theory, pp. 1882-1886. PMLR, 2018.
Anikender Kumar and Pramila Goyal. Forecasting of air quality in delhi using principal component regression technique. Atmospheric Pollution Research, 2(4):436-444, 2011.
Qi Lei, Wei Hu, and Jason Lee. Near-optimal linear regression under distribution shift. Interna- tional Conference on Machine Learning, pp. 6164-6174. PMLR, 2021.
Tengyuan Liang, Alexander Rakhlin, and Xiyu Zhai. On the multiple descent of minimum-norm interpolants and restricted lower isometry of kernels. In Conference on Learning Theory, pp. 2683-2711. PMLR, 2020.
RX Liu, Kuang, Qiong Gong, and XL Hou. Principal component regression analysis with spss. Computer methods and programs in biomedicine, 71(2):141-147, 2003.
Cong Ma, Reese Pathak, and Martin Wainwright. Optimally tackling covariate shift in rkhs-based nonparametric regression. The Annals of Statistics, 51(2):738-761, 2023.
Neil Mallinar, Austin Zane, Spencer Frei, and Bin Yu. Minimum-norm interpolation under covariate shift. In Forty-first International Conference on Machine Learning, (CML.2024 Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024. URL https: /ttp///ppeevveeeeeee ew net. forum? ferrmmidi dd= 2w7 ZwTTenTmHj.
William F Massy. Principal components regression in exploratory statistical research. Journal of the American Statistical Association, 60(309):234-256, 1965.
Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75(4)6667-766, 2022.
Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Generalization error of random feature and kernel methods: hypercontractivity and kernel matrix concentration. Applied and Computa- fional Harmonic Analysis, 59:3 84, 2022.
John Miller, Rohan Taori, Aditi Raghunathan, Shiori Sagawa, Pang Wei Koh, Vaishaal Shankar, Percy Liang, Yair Carmon, and Ludwig Schmidt. Accuracy on the line: the strong correlation between out-of-distribution and in-distribution generalization. In International conference on machine learning, pp. 7721-7735. PMLR, 2021.
Andrea Montanari and Yiqiao Zhong. The interpolation phase transition neural networks: Memo- rization and generalization under lazy training. The Annals of Statistics, 50(5):2816 18--247777 2022.
Mohammadreza Mousavi Kalan, Zalan Fabian, Salman Avestimehr, and Mahdi Soltanolkotabi. Min- imax lower bounds for transfer learning with linear and me-hidden layer neural networks. Ad- vances in Neural Information Processing Systems, 33:1959-1199 1969, 2020.
13

---

Published as a conference paper at ICLR 2025
Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai. Harmless interpo- lation of noisy data in regression. IEEE Journal on Selected Areas in Information Theory, 1(1): 67-83, 2020.
Tormod Næs and Harald Martens. Principal component regression in nir analysis: viewpoints, background details and selection of components. Journal of chemometrics, 2(2):155-167, 1988.
Preetum Nakkiran. More data can hurt for linear regression: Sample-wise double descent. arXiv preprint 1rXiv:19/2.07722, 2019.
Jeffrey Negrea, Gintare Karolina Dziugaite, and Daniel Roy. In defense of uniform convergence: Generalization via derandomization with application to interpolating predictors. In Interna- tional Conference on Machine Learning, pp. 7263-7272. PMLR, 2020.
Partha Niyogi. Manifold regularization and seni-supervised learning: Some theoretical analyses. Journal of Machine Learning Research, 14(5), 2013.
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, pp. 17517-17530. PMLR. 2022.
Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do imagenet classifiers generalize to imagenet? In International conference on machine learning, pp. 5389-5400 PMLR, 2019.
Dominic Richards, Jaouad Mourtada, and Lorenzo Rosasco. Asymptotics of ridge (less) regres- sion under general source condition. In International Conference Artificial Intelligence and Statistics, pp. 3889-3897. PMLR, 2021.
Ohad Shamir. The implicit bias of benign overfitting. Journal of Machine Learning Research, 24 (113):1-40, 2023.
Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log- likelihood function. Journal of statistical planning and inference, 90(2):227-244, 2000.
Igor Silin and Jianqing Fan. Canonical thresholding for non-sparse high-dimensional linear regres- sion. Annals of statistics, 50(1):460, 2022.
James Simon, Dhruva Karkada, Nikhil Ghosh, and Mikhail Belkin. More is better in modern machine learning: when infinite overparameterization is optimal and overfitting is obligatory. arXiv preprint arXiv:231 14646, 2023.
James H Stock and Mark W Watson. Forecasting using principal components from a large number of predictors. Journal of the American statistical association, 17(460):1667-1177) 2002.
Jianguo Sun. correlation principal component regression analysis of nir data. Journal of Chemo- metrics, 91):211-2, 1995.
Nilesh Tripuraneni. Ben Adlam, and Jeffrey Pennington. Overparameterrizatio improves bustness to covariate shift in high dimensions. In Mare' Aurelio Ranzato, Alina Beygelz- imer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Informa- tion Processing Systems 2021, NewrIPS 2021, December 6-14, 2021, virtual, pp. 13883- 13897, 2021a. URL https: /ttpc//eicocccece/seeeo..s/ wttpssss.cc..ppppppeeee////ee cc//pappr/222//hastt 73fed7764722502d8- EEA4890879488 Abstrrrat......aatttttt......... html.
Nilesh Tripuraneni, Chi Jin, and Michael Jordan. Provable meta-learning of linear representations. PMLR, 2021b.
In International Conference on Machine Learning, pp.
Alexander Tsigler and Peter L. Bartlett. Benign overfitting in ridge regression. J. Mach. Learn. Res., 24:123:1-23::7, 2023, URL http::://ni...oog///apeeeeeee/
1398. .htll.
J Leo van Hemmen and Tsuneya Ando. An inequality for trace idcals. Communications in Mathe- matical Physics, 16:143-148, 1980.
14

---

Published as a conference paper at ICLR 2025
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. abs/1011.3027, 2010. URL httpt/:://aaxii.oo//bbb.o..//
CoRR,
Roman Vershynin. Hligh-iimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
Evelyne Vigneau, MF Devaux, EM Qannari, and P Robert. Principal component regression, ridge re- gression and ridge principal component regression in spectroscopy calibration. Journal of Chemo- metrics: A Journal of the Chemometries Sociery, 11(3):239 229999999,9 1997.
Per-Ake Wedin. Perturbation theory for pseudo-inverses. BIT Numerical Mathematics, 13:217-232, 1973.
Florian Wenzel, Andrea Dittadi, Peter Gehler, Carl-Johann Simon-Gabriel, Max Horn, Dominik Zietlow, David Kernert, Chris Russell, Thomas Brox, Bernt Schicle, et al. Assaying out-of- distribution generalization transfer learning. Advances in Neural Information Processing Sys- tems, 35:7181-7198, 2022.
Denny Wu and Ji Xu. On the optimal weighted 12 regularization in overparameterized linear regres- sion. Advances Neural Information Processing Systems, 33:10112-1000 2020.
Xu and Daniel J Hsu. On the number of variables to use in principal component regression. Advances in neural information processing systems, 32, 2019.
Runtian Zhai, Chen Dan, Zico Kolter, and Pradeep Ravikumar. Understanding why generalized reweighting does not improve over erm. arXiv preprint arXiv:2201. 12293, 2022.
Xuhui Zhang, Jose Blanchet, Soumyadip Ghosh, and Mark S Squillante. A class of geometric structures in transfer learning: Minimax bounds and optimality. In International Conference on Artificial Intelligence and Statistics, pp. 3794-3820. PMLR, 2022.
Lijia Zhou, Danica Sutherland, and Nati Srebro. On uniform convergence and low-norm interpo- lation learning. Advances in Neural Information Processing Systems, 33:6867-6877, 2020.
Yang Zou, Zhiding Yu, BVK Kumar, and Jinsong Wang, Unsupervised domain adaptation for se- mantic segmentation via class-balanced self-training. In Proceedings of the European conference on computer vision (ECCV), pp. 289-305, 2018.
15

---

Published as a conference paper at ICLR 2025
A SIMULATION
trU] utV]
---
Ridgeless
t/U1/ [ 25
M =5
Ridgs, n9.
tr(U]/ tr[v]
7 100
Ridgs, 11.75
Ridgo,
00.03
Risk
Log Eocess
0.998
Log
-1100
0..5
1.000
-1177
-1,12
-8
Log
Log
Log
(a)
(b)
(c)
Simulation results for excess risks across varying training sample sizes. The shaded regions represent standard errors runs, using different samples of training and test sets. The slope of the fitted OLS model is marked along each curve. (a)(b) Minimum norm interpolation under distinct target covariance matrices with small shifts minor directions. The source covariance matrix remains constant. (a) Various magnitudes of shifts in minor directions, with || 1. (b) Various magnitudes of shifts major directions, with tr(4] tr[V] = 1. (c) Ridge and PCR under large shifts in minor directions, following the setting of Theorem 4.
Figure I:
A.1 BENIGN-OVERFITTING SMALL SHIFT MINOR DIRECTIONS
We simulate the covariate shift discussed in section 3, where the overall magnitude of the target covariance matrix's 's minor directions is comparable to that of the source. Theorem establishes an O(1/n) excess risk rate for ridge regression under certain benign-overfitiing conditions. Specifi- cally, for the training data, we assume k O(1). R 22n2),, |8% S.
= O(1), || [Er
(1///n), and = O(vn). For the test data, we assume || experiment, data is generated according to these conditions.
tr ir
nr
[Es--ell = O(1). In the
y= x 3 +
where 3* E RR+*², with 93 - .... JE )d 8 0 and k = 10. The noise follows a centered gaussian distribution with variance 0.1, and x is drawn from multivariate normal distribution with zero mean and a source covariance matrix Ds = diag( n -1155,,,)) The target covariance matrix Dr diag(2ir -T,,k) where ΣT,A and Σr,-k are randomly generated and scaled achieve specific values for ||T]] and wil t.("" respectively. At the same time, we do not explicitly control [Er.- nrk Es. all because it equals [Er.-kll in this setting and is typically bounded for randomly [[a.-
generated ΣT. We run minimum norm interpolation (ridgeless regression) with À
The source covariance matrix Eg is fixed for all experiments while we vary the target covariance matrices. To study covariate shifts in major directions, we vary [|] among 5, 25, 100 and keep
trfe tr[V] = 1. To study covariate shifts in minor directions, we vary tr[ = 1 among 5, 25, 100 and
trft
keep |T| 1. For each pair of T|| and
generate training samples of various sizes and [x
16

---

Published as a conference paper at ICLR 2025
1000 test samples. For each target covariance matrix En is randomly generated to satisfy the tr(0 specified || and tr[p]. We run 10 experiments for each set of (Eis, 2r, n)), using independently sampled training sets and test sets, and the mean and standard enror of the excess risks are reported.
The results are shown in Figure la, 1b. The fast rate (11) of minimum norm interpolation is confirmed, as the log-log plot of excess risk versus n has a slope near -1 across all combinations tr|M
tr(t/ of ||7|| and tr(v-- The excess risk increases with larger tr(vi, indicating greater shift in minor directions. Similarly, the excess risk increases with larger ||T||, indicating greater shift in major directions.
A.2 RIDGE V.S. PCR: LARGE SHIFT IN MINOR DIRECTIONS
Theorem identifies a setting where large covariate shifts occur in minor directions of the covariance matrix, leading to lower bound of O(1/ /n) on the excess risk for ridge regression, while Principal Component Regression (PCR) achieves the fast rate of O(1). We design simulation experiment under the same instance of the source and target covariance matrices. Specifically, data is generated as:
_ B" te,
y ==
where 8* TV+. with 3 T ... v ,. = 0. and k 10. The noise is drawn
from centered gaussian distribution with variance 0.1, and æ follows multivariate normal distri- bution with zero mean. The source covariance matrix is Es = diag(Is n -0.5 [vmj), and the target covariance matrix is En IK+LVR
We evaluate ridge regression with various regularization strengths: 10-8 0.5 0.75 n. Here, we use À = 10- to approximate ridgeless regression, which has a singular solution under this setup. We compare PCR to ridge regression for different training sample sizes n. The test set contains 1000 samples. For each n, 10 experiments conducted with independently sampled training and test sets. We report the mean and standard eиror of the excess risks.
Figure Ic present the results. As expected, PCR nearly achieves the fast rate of O11nn), with the log-log slope of excess risk versus n being -0.99. In contrast, the optimal rate of ridge regression On 00.4)., achieved with À 0.75 This aligns with the lower bound of ((1/vn) from The- orem 4, and its proof also suggests À = n 0.75 as the optimal regularization strength. Additionally, ridge regression exhibits excess risks above a constant for certain choices of X.
B RIDGE REGRESSION
Let X = XT,,) Raaxd,Y- Y (y)...., "oi.-..,aaa"" yT. R and (e1...., RR. We denote the first l columns of X as X₂ and the remaining d columns as X_ Similarly, B and 8** represent the corresponding components of 6+. Es.. Vs are the corresponding blocks on the diagonal of Es. The i-th eigenvalue of a matrix is denoted by p4(-). Define Z = XΣ 1/2 where the rows of 7 are i.i.d. centered isotropic random vectors. Additionally, we assume the rows of Z are o-sub-gaussian where the sub-gaussian norm is defined as follows.
For random variable s, the sub- gaussian norm ||s||o is given by:
| inf
0:
cxp t2
S $2
For a random vector S, the sub-gaussian norm ||S|| sz is given by:
(| v) We
|| ssup v
|
For A 2 0, consider the ridge estimator:
3(Y) x" x (XX* -x
17

---

Published as a conference paper at ICLR 2025
=x"(x" + -(x3))+B(
x"XXX + +
where we define define 3(x = + and 3(e) X² -.e Addition- ally, define Σg = Es + Ta. The effective rank of Σs, is defined T + Az)-
Assumption 2 (CondNum(k; 6, L)). Define matrix A& = MI + X With probability at least 1 5, Ag is positive definite and has condition number no greater than L, i.e.
J41 (Ax) Mn (A&) S L.
B.1 CONCENTRATION INEQUALITIES
Denote the element of matrix in the i-th row and the j-th column as [[. and the i-th row of the matrix X as X #].
Lemma 7 (Lemma
of Tsigler Bartlett (2023)). |= I and consider Σ = diag(A1,..... Ap) where the sequence {2,] is positive and non- increasing. Then there exists some absolute constant c, for any t > O, with probability at least 1 2e t//;
be sub-gaussian vector in RP with
P Σ j=1
2| S co22
+tt+ tλ1 +
Lemma (Lemma 23 of Tsigler& Bartlett (2023)). Let A represent the matrix X_ with its diagonal elements set to zero:
A = (1 xZxx)
Then there exists some absolute constant c, for any > O, with probability at least 4e 1/00
|| S co2
((+
12 (1++ + Σ x2
Lemma 9 (Lemma 21 of Tsigler& & Bartlett (2023)). Suppose {2 is a sequence of independent Ap) represent
isotropic sub-gaussian random vectors, where || S a. Let Σ. = diagonal matrix with a positive, non-increasing sequence {A: [A Then there exists some absolute constant c, for any E n). with probability at least - -tt
(n 2
1///22211 (n v Vnta²)
A
Lemma 10. There exists a constant depending only on a,, such that for any satisfying ndp+1 < (X + E5>z 29), under the assumption CondNum(K 6, L) (Assumption 2), with probability least
1 - 5 3-66 3-c.6-n/e nn/ee/
A Σ> A+
< (n((A SM((AN Sx
CaL
jock
mi MI(X S
ndR+1 +
Σn1 3>N
Proof. This result follows from the proof of Lemma Tsigler & Bartlett (2023), which estab- lishes both upper and lower bounds of μu (Ax). By combining the lower bound with the assumption CondNum, we derive lower bound of pm ( (Ax). For completeness, we restate the entire proof here.
According to lemma and lemma 8, there exists absolute constant c, such that for any > 0:
18

---

Published as a conference paper at ICLR 2025
1. for all s i n, with probability at least - 2e t/e;
| +]| S co?
(NetI Σny
53k
2. with probability at least 1 4e-1/o;
|| |1 S co² (t (t+m) (t+ +
Σ 23
52
Since (1(AAs) & A || + max; || (ē, |11 by setting = n, we have with probability at least
1 (2n + -/c-
(1(aa) S x co² ndR+1 + Σ>5 +
(2n +2 2n
Σ A3
53b
SA+co
nd++1 + Σ
Aj + 2n1x+1 +
2n A3
5>k
S x co²
nd++1 + Σ
Aj + 2nde+1 + 2nda+1
Σ
Ajj
5>k
fz
S co²
nd++1 + Σ
Aj 2ndE+11 + +NARI1 +
A3
5>k
5>k
S S + 400
ndi+1+ + Σn
j3k
< max (1,4c02}
A + Σ
Xrg + nd++1
jick
< maxx {1, 4co"}
x Σ N/
(2)
jok
The last inequality follows from ndx+1 S (A+ Ey>h )z). Similarly,
mx(X+xX,,) S 4co2
IndA+I+ Σn ,1
(3)
j>kk
On the other hand, by applying Lemma 9 with t = Tou, there exists an absolute constant c', such that with probability at least 1 - 2 exp 10
1
Σ xx x1|2
2
n2 Ay.
j2k
On this event,
(Ax) 2 X 1
tr x x
= - n
X x (1, 12
19

---

Published as a conference paper at ICLR 2025
1
2
By the assumption CondNum(k; 6, L), with probability at least 1 2cxp
{-
-
4ere
Pn (Ax) 2 (Av) 2
A
(4)
2T
jok
Combining Equation 2, and 4, there exists constant Ce depending only o, such that with probability least 1 - Cze -n/ez;
A
Σ X1
I (n((AN) Sc.
CaL
jzb
52b
ΣN
m Co
nde+1 +
Lemma 11. There exists a constant e, depending only on a, such that with probability at least 1 1 6, i k ln(/8),
X Xx - Esa S codig
k + In
Proof. This follows directly from Theorem 5.39 and Remark 5.40 of Vershynin (2010), which shows there exists a constant ég depending only on o, such that for any 2 O, with probability at least
1 - 2expl_19/cc)
1 x Xx EsS S AI max & V
& V
Vn
Vn
Taking t V 12/8)) completes the proof.
Corollary 12. Under the same conditions as in Lemma 11, and on the same event, the following holds:
[xTxx)) $ Vn s cz k In A1
Proof. According Proposition 3.2 of van Hemmen & Ando (1980), for any positive semi-definite matrix A, B E R we have
I
B
2
ue (At)
+ ua ( (Bt)) |
B$]
Therefore,
(xf
VnIs.Al
1
|| Nx. nE
ue (vnxtt
= -nn
x Xx - Σs.k
By applying Lemma 11, the proof is complete.
20

---

Published as a conference paper at ICLR 2025
Lemma 13. There exists a constant c₂ depending only o, such that for any n > cak, with probability at least 1 2e- 2e-n/
1 n S ue (Egix(x)Ns) s i (2g C.n. Ce
Proof. According to Theorem 5.39 of Vershynin (2010), there exists a constant &e depending only on a, such that for any & 0, with probability least 1 exp( -12 /c)):
> [ 2 (v - 1)²
J11 [ x (Vn+ ca Vk + +)) t)²
Let Vnn For 16(c,) with probability at least 2exp (-1/
Vn 4 Vn 2/n)
16 n.
#1 - x & V _ nn + Vn
49
16 n.
By taking C2 = max (6((2)) 4d 16), the proof complete.
Remark 7. On the same event, the following inequalities also hold:
mx & |SS X X cadim.
Au (x{ 2 (Es,))) ( xx x
Agn.
Cx
Lemma 14. There exists constant c₂ depending only on o, with probability least 1 2e 2n/e//;;
Ir &T centr [E, - ET, E..
Proof. According to -rison-Wright Inequality (Vershynin, 2018), there exists an absolute constant such that for any sig n,
2 (i,
Er. 2 2 /
S sco2
|
| م - Er
-
11
S < lr E Er
By Bernstein Inequality (Proposition 5.16 of Vershynin (2010)) there exists an absolute constant d' for any / 2 0,
1
a Z Z=
* E _
7- 2 x 23
ET,
211 - 1r (E)) - - -r.
21
n
12
-c'n min
< 2xexp
K2 K
where K = max;
Z [= * 1 Ex,
-
7 11i
Lett cr
- Er,- _ : Then, with probability at least 2e 2'nn
tr (X = Σ
Ez Z 2T - - #)T
s + co ir
Dr. -T
By taking Cz max (1 + co2 2 } the proof is complete.
21

---

Published as a conference paper at ICLR 2025
Lemma 15. There exists constant C₂ depending only with probablity least 1 -2 -/emn/e;
(8'x)" x=, I
Proof. The result follows from the proof of Lemma in Tsigler & Bartlett (2023), which we restate here for completeness. Consider the isotropic vector -ES, " 1/2 X- For the i-th component.
[(s x- 11 [(81x) Es,
7ー 12, * | 3
S [(3 Es,
o.
By applying Lemma 9 for the sequence ( -1/2 X x|1, 4|;
there exists
si=1"
an absolute constant c, for any t E (0, n), with probability at least 2e ct
($2x) x S n Vnto². ( "'
Let = n/4, with probability at least 1 2e cn/4.
(3"x) (x $ (1 - = (32x) -s
By taking c = max {1 + 1 0 } the proof is complete.
B.2 BLOCK DECOMPOSITION OF X
Let X = UMVV, where U E g2xx and V E Idxdd are orthogonal matrices representing the left and right singular vectors, respectively, The matrix M is defined as:
mi
M
E Raak
m
O k)
Therefore, we have X UMU where M diag (m ... my, O,..., 0) E guxa, Similarly, X Xx VT M&V. where M& diag(m,, ... mp) Rixk
Let A TJ X X and write A in block matrix form
A 11
A12
A
T
A22
12
where An R A12 ( and Az2 R
((n-k)x(nnk))
We will repeatedly use the first rows of (M + AI, + A)-1, which we compute here. Because M AI, + A and AIn-k Azz invertible when A is positive definite, by block matrix inverse,
(M + NI + A) lk. *]
(5)
= -MM+ + A4 + An A12(Ann+ + A22) (4. (4.--Ap(Mnn+ A22)
Corollary 16 (Corollary of Lemma 10). There exists constant depending only on a. such that for any n < Ax+1 (X + Σy>x Xz), the assumption condNum(k; 6, L) is satisfied, the following
inequalities hold with probability at least
C nn/e, on the same event as in Lemma 10.
| A < ||
S
cv
A
Σ A
j>k
22

---

Published as a conference paper at ICLR 2025
422) S |4 caL
A Σn
A/
j3k
(11(Al) A L
A2) Te - 1
x Σ A1
jok
An A12(Ann + -22))
cz
A Σ
Proof.
1. The first inequality.
S ||||| |412l - IAA c
2. The second inequality.
[( 112) (1 -I || S 1z
A +>EN> j3b
where the first inequality holds because Al, + A is positive definite.
3. The third inequality.
A12 A22) - S | + S C.
4. The fourth inequality.
A12(Anxx + 222)-1127 S + C.t
A 1 A+
j>b
5. The last inequality.
An A12(An + A22)
A + AI. (12(Ann + - -
< Ann + Nx -
AAnll
I Cv
1
j>k
The first inequality holds because An1 + A1x A12(Nnn + A22)-1AT is the Schur complement of the block An1 + Alx of the matrix A Al. which positive definite. Therefore, we have
A Alk An + Al A1z(A A22)
Lemma 17. There exists constant eg > 2 depending only on o, such that for any N1 < N2. the assumption condNum (k, 6, L) is satisfied, the following holds with probability at least 1 - be n/t=, on both events from Lemma 10 and Lemma 11,
X X2 Nk + VT (An A2 + -22)-1A77 v] v--' - (nnS..s) 11
23

---

Published as a conference paper at ICLR 2025
c (Vn((+ in + + (A+Esse \n)
(A+ m2
where
17
N1 max
4ct + 1n(1/8))
20 Tut
X2
N2
1
A Σトラ
AR+1
j>b
Proof.
|X] + NT& + VT (A An) V] -1 V1- (nSis.e)
[ + Alx + rT (An A -b V ||-1||
<
[x + N14 + V (An - 42) v] - (nis.))
(nÉiSA)
||[X]
Xx X2 Al. + V (An1 A1e(Ann + 422) -1 A7) V]
À + mdg
|| n.s + VT (An - A + -A2 VII-
According to Lemma 11, Corollary 16, there exists a constant Cx > 2 depending only on a, such
that for any k + ln(1/5) < N₁ < n < N2 = deti(A (1 + Ej>k Xz), with probability at least
1 - 28- c/emness on both events in Lemma 10 and Lemma 11.
X - ΣSH
k + In 1
scadip
8
| + -Aall S L
A Σ> jzk
A1
(An 1. XXX, - n.S + +V (An - D12(An + A22) - T2) Vll-
|| |X Xx n. + VT (A11 A12(A k + A22) -1 A22) Vl
$ || Xx - n..s. || + || - -A12(An + + A22) -1 1AT2
S cz / n(k + In 1 )) + EL { >++E> X/
jzb
2. |xfxx + Alx + VT (A11 - A12(A + A22) - -272) vi v--1|
X (An - A12(AIn + A2)) - (T)) Vll
x +
c (//n(k+ In 1n + E ( (N=I*))
ndk
jzk -1
Since n > 40 (k+ + In(1/8))
)2 x
coy
n(k + In 1)
A + nn / n(k + In 1 j)az s
1
nd
24

---

Published as a conference paper at ICLR 2025
Ce / (K + In $)
Vndu
1
2Cz
Since n > 1 + Ejstda), Az);
L (x+
E)>k 2q)
L
A I+
S
A + ndx
ndx
jzk
1
20g
Therefore, we have
1 X n. +V V - A Vl <
1 Cr
n2
Now we derive the upper bound for our target.
[x Xx + A1x + VT (An1 + 1
|nSss.+ + Xxxxx Xx n.ss + VI (An1 - A12(N 222) A2) V/
(nÊS..) -|| 1 1 (nSSaa) -
|| Xx + A1x + V (A11 A12(AIn A22) v] -|]
S 1
(1-2)
1 -
+ nd
Cxe
Ca
< A nd
The first inequality follows from the result [I(A + +TT) < ||A-I| (1 (1- 11--|1--1100 |I] -. provided that both and A + T are invertible and ||A-I|||T|| < (see Lemma 3.1 in Wedin (1973)).
Combining the above two inequalities,
V (nES..)" )-1
|x[Xx Ala VT (An A12(AIn- + Aoz) -1TT
Cx A A A n
Co co nlks + in 2ine + cGL
(x
5>k
2 (V
n(kk + In f) + 2 (1 E Ejsx>2)) 21))
() a n2x)2
B.3 BIAS VARIANCE DECOMPOSITION
We consider the expection of the excess risk R (B(Y)) = R (B(X + B(e)) with respect to the distribution of the noise e.
E. |R (B(Y)) = E. ( -8²) T Ex (ā(V)- - xT)]
25

---

Published as a conference paper at ICLR 2025
Es E.
((())=TT
ET (Te) - ET (8(XB))
We decompose the expected excess risk into variance and bias terms.
= Ee ((t) Bre
s 2E (3(e) x 3(c)x
+ +2E
B (B(X - 83) T Ex (3(X8)) - 3t)
< (3(((x8)) - -B) T
ΣT (3(x8*) (%%)
+2 + -())) Er.-k
( 3"x
The inequalities follow from the result for a positive definite block quadratic form:
x BT
21 of Az + 20 Bxz + of Dai,
D
22
where the positive definiteness implies xf Ax, + Dz1 2z Brz
Lemma 18. There exists constant Cz > 2 depending only on o, such that for any N1
N2. if the assumption condNum(k; 6, L) (Assumption 2) is satisfied, then with probability at least
1 28- ce-n/ce, the following inequalities hold simultaneously:
(n((A))
1 CII.
A Σ
N1
j>k
m1(A)) S cx
x +
Xj
j>l
11 (I S co
nd++1 +
Aj
5>k
1 x X X2 ΣSA
h: h+ In 1
I c
(x Xx) $ vn
S c 1
4: + Im 11
1 n
&
) S n.
m (x Xx) 1 c.d1n.
1 Nan.
(x(x 2 C2
tr (X S c.n tr
(B2,) T XI X BB² S c=n(3"n)
T T -
| |b| 1| ||||||| S co
X Σ A1
j>k
[[A + 422) -11. 11 |1 S caL
A [++ A1
g>k
26

---

Published as a conference paper at ICLR 2025
Ara(Min A22) - s c.L.
A1a()n-++ A - ليعه
> A1)
| A A2) S
+ Σ A/
And,
||xx Xx + AR + V2 (An1 A12(ANn=+ v-- - -(nSS...) -1
2 (yn(k+ f)d1 2 E1z
nA+
N1 and N₂ are defined as follows:
N1 = max
4ct + (1(66))
2c L
5>k
1 AR+1
N2
A +
j>k
Proof. The lemma is direct corollary from Lemma 10, Lemma 11, Corollary 12, Lemma 13, Lemma 14, Lemma 15, Corollary 16, Lemma 17.
B.3.1 VARIANCE IN THE FIRST DIMENSIONS
Lemma 19. Under the same conditions as in Lemma 18, and on the same event, for any N1 < n < N2.
[(c) 160 + d13) 1 tr [=SStEnAEg))
Ec
where
1
N1 max
4c
k In
8)
LA
A ++ Σ A1
)
 -2
4e
k + In 5)
1a>,5 $1=,,
12
s.
20 LXf
A Σ 23
|ET,NIK tr
5>N
1
1++ I A1
N2
Au+t1
j2k
Proof.
Ez ((c) (T,
= =R. tr |ee" (XXx
(XX
(XX* =1
27

---

Published as a conference paper at ICLR 2025
= = tr [XX" +XX*+A,)) - "X + [
= -2 (UMUT +UA UUN
''T VT( (M:) T U"MMMU" +UA + A
-v² ir
(M²) AM+A+NN)-UU
(MTA) T (M=AAMa-
= ir
v² [ + NI A -1 (Ik. -12(NNn= + 112)
(4s, + (Mxx + + A11 - 112(Nn + A22) -A2)) M
VVTAVTT
= tr M (Ms + +
+ - A12 + AA2))
(T& + A12(A A2)) (M& + Al + An A12(A + 422) -1A)2) M
VVT
= v22tr tr (Is + A12
(M + AAx + +11 - A12(A + 422) A2))
-M VET VT M (Ma + A1x + A11 A12(N 422) -1
<1² 1 + AI A22) TaTl tr [M: + + +n A12 A22) A2a)
M VET VTT ME (M& + AIx + An1 A12(A A22)-1AAa -1
S d tr (AM A4 An1 A12 222) -1A
-MEVE VT VT M (Ma + AAx An A12 AATT)) -1]
= o ( tr (V (M& + AA + An AIc(Aln 42) A722 V
VTMAV ET. VTMÆV (VT (M+ + + A 4 v) "]
= = + + A tr (XfX* + AA + VT (An 12l--A(M++++ v)
(xXx)) TT. (xFxx) 1
(xfX* Ale + VT (A11 A12(A + A22) v) v)-
The sixth equation follows from Equation 5. The first inequality follows from the result tr[AB] < |||||| [r] where the matrix B is positive semi-definite.
We define two quantities that represent concentration error terms:
|XX + AI V (An A12(AI (1 (nEss)"'1
E1
Eg (X Xx) (nEs,))*
Since n 4ed (k + In ) A6 $1 DTTT 2222 (tr " -2
and n > L A + \y) X²2
|ET || (Ir
(ンンン ))
E n (1āS.a - [
|||||ا
|لمددر||| ( (m=s,)م (15Ssa) 11
28

---

Published as a conference paper at ICLR 2025
2/ ( W + in f)41 + 2 (A+ Eni) (A (A+
nd1
|Er
(A + n2x}²
(2 ndx))
22
(Vn(k n(k + In 2 + r.g. (A+ Σソ>h)1) 21))
X2
n²
X
c2 // (b: In ()
og (A+ Σns 2z)
|xT +
nyn
X
n²
1 tr
E 8
Er
tr ( (
2nk
2nk
1
tr
nk
Since n > 4ct (I+ + In (t) x and n > L (}+Eize 21) X1 2122²
|
n....
2
V nukk + In f\h1 + 22 (A+ Eisos (A + nd))
()+ n2x1)²
2 (v f)l + & (^+Er d1
(6)
2
EL [i+E) A1 /(= + In 1)) X²
Vn
X/
1
<
2
+
2
= 1.
(tr (=
Since n > 2 (k + In 2) 212 1
|E
(nIis))
- - (1Sisn)
-| -|[n22200 || |لم [n>is)=||| (nāis)) 11
|22
||
S Scy/
k+ + In J jiiik
2/2 (nde)
(A (A+ n2 ETr
nd1
S Cx / h: In 1
X2
1/ |ET,Ell
nV"
s 1 tr [
nk
Since n > 2 (ks + In }) x
| |1
(niisK))
4: + In 8 d (ndx)) 3/2
S Sca
Ca
k + In A
vn
< 1.
Combing the above four inequalities, we have
Ir (X Xx + Nl + vT (An1 -
+ V)=
29

---

Published as a conference paper at ICLR 2025
(xXXx) & Dr (X Xx)$ (X Xx + Alx + V (A11 A12(AIn + A2) V) -
(nEsa) " (nEs,)) ET. (mEs,)) (nESS.))
tr
Ei (nEs,a)² à ETE (nEs,)) (nāiS..)
+ 2 ur
(nESS)) EDDTA (nEisn) (nSis.))
+ 2r
Ei (nZiss)) à MT. (nZis.)) Eij
+ tr
(nāS.)) E2ET (nIis.))
+ tr
Ei (nEs,a) Er (nis.))
2r
ETETTT (mEs,)) 3 (nES.))
2
ELEaErA (mIs,k) ) Ei
+ 2tr
11 ET Es (nSis..)
2
+ tr E E2 EzE1
In particular,
(nIs,a)* ET (nEsx)* (nεs..) -17
tr
Ir
1
5.
Ex -
< tr
E-1
Σ
S
5.
n
The inequality follows from the fact that BAAB tr[A s tr(AACA = tr(CAC,, [CCAAC, where A. B, C are positive semi-definite matrices, and C B, which implies that A!CA > A B.A.
ir ET,
tr EinEs, (nāS..) Es (nIs..)) - (mīs.)) $
ET (nESs.)) -
(nEis.)) 1 EinEs,A (nEis.) -17
In..s... 1)
|Pall (nS.s..) -3 11)
S k (1
|
(nSis.))
(nSS..))
|||| || (nšee)
< - tr (
n
The other terms can be similarly bounded. Therefore,
Ir (X Xu + Mr + VT (An1 - + V)
30

---

Published as a conference paper at ICLR 2025
(xF Dr (X Xx)3
(X + x + V (An1 A12(An- Am)) ) V) - -
16 tr | م
n
The proof is complete by combing all the inequalities above.
L
B.3.2
VARIANCE IN THE LAST d DIMENSIONS
Lemma 20. Under the same conditions as in Lemma 18, and on the same event, for any Ni < n <
N2.
Ee (())) s de
+ E+E 21
tr N
52k
where N1, No defined as in Lemma 18.
Proof.
Ec -T,
tr lr [ee (XX* Na) (XX +
-f + +(A)) - (XX* + !
502]1(XX + +1)) - tr X DT. -
S <0211(X= -x_xx xxxxxxx + Ala) - X A Ex. x
1
A + Σ Aj
Cnttr Do. 5.
Dx
Cab
j>k
-2
Σ
A
tr
j>k
The first inequality follows from the result tr(ABA tr[A²B] < ||A2| tr(B] where the matrix B
is positive semi-definite. The second incquality follows from XX" + +d, x X X + Aln-
B.3.3 BIAS IN THE FIRST K DIMENSIONS
The bias the first &s dimensions can be decomposed into two terms.
(B(X8))- - Bk) T = -XX + +
ET (3(X3)) - 8%)
-Bt)² 22 (1A) -Ix) Xx - (1) En (X. (XXT + +1,) - Xx.3 3% +2
T Σx, (X (XX" + AIJ 11m) X3-- - X33- -1x'-
ΣT. (X (XXx + - 3²)
The inequality follows from the result 27 Az + 2 Arz 2 2x Ar where is positive semi- definite.
Lemma 21. Under the same conditions as in Lemma 18, and on the same event, for any N1 < n <
N₂.
(X AIn) -x B2)² Erg
18)
16c4 n2
A
Σ
21
(82) (3))""100 33 1
jzk
31

---

Published as a conference paper at ICLR 2025
where
N1 max (x + ENIADIEE?
4c + +m((1/8))AR>/
A Σ 21. }.
20 Lix
jok
N₂ =
x Σ A/}
Au+1
Proof.
(XX + +b, Xn3 - - ΣT& (XT (XX* + +NN))- B%)
(82) (X (xx" + + - 11) T ET (X7 (XX* + +1ln) Xx 1x) B%
T 1gsk
(xx" + 1 - -g,
D (2 x + + - Es,,) 2
s <88) 0/ | 2T اللل
| x (Xx + Alm) - Es.t
Subsequently,
X (XX" + (aa) - - ΣSA -
VT (M+) UTU(M + Na + U - -Es.
= V ME (M&+NA Xl= + An A A2) -1 "M V EsS
= ES.K (VTME' (M&+ A2) 2v) -1
ΣS
Esseel
I [Ix + AVV+ (Al + An - + M $v)
$
-1
=
S,k
EssAell
(T&+VTTE (A&++An - + Mr 2v) -1
Σ S.K
1/
| VT VTM (Al + - - AAO M &v
=
(Ix + VT Mr 1 (Al + - -N AIe Mj vv)
S.
- ESS VT ME 1/ - AA(A Mf VV x ||
<
+ V
VT M 1 MM++An-ANNN
M àv
[1T VT MT 3/2 (AT&+ A12( M 2v)
- ES
32

---

Published as a conference paper at ICLR 2025
The second equation follows from Equation 5.
We will derive upper bounds for both terms in the last equation above.
1. The first term.
23,6 VT..TTM M 3 (AI& + An A12(A + A22) -22) -22) Mr 3 3V
$ Aa + D11 A ||
| VT M3 /
( (xxxx) -
= | A11 - +22) - ||
+ ++E>, 211 21)
_
Cx Cz
71
jonk
20 S
A + Σ
jok
The inequality follows from Gr > 2.
2. The second term.
Since n > 20 (A + Eン>kAb)ABs
ME 3 (ATx= Au1 + M 1
M| ||
+ +An - A12 A
Co_ 2cs
A + Σ A1
ndx
j>b
1
Cx
Therefore,
1k + VT +1+VeM²+ 2 (AT + An - + A2)) -1 M
2 :v) -1 -7a
(1++VTM (ATx An Am) Mr $V) -1
|T 1 (>tx + An - AA Mj $v|l
1
|TTM 1 (AL + AuI - A12(An + A2) A17) M 1 vl
<
1
Cs
Cz 20z
A Σ A1
S Cr
n.4k
53
2 A
Σ j>b
Ej>e
dj
The second inequality follows from |[(47))-1| < ||~-1| (1 - -1A--11[77]] -1 where
both A and A + T are invertible and ||||||| < 1. Note that c₂ > 2.
Since n > 20 (A + Ej>k Ag)A
E S.K
M (Atx + An - A12(AAn + Az) -m))-1A7) -AAPe) M kv
33

---

Published as a conference paper at ICLR 2025
(1 (1&+VTMM (A4 + AnL - +
M 2 vV -1
-x ESS
< |Es | + An +12(2 T21l
|[ + +VMME (Al + An1 A12(NIn + 4 Mr 2v) -1
-14 11
20 A + Ejsk A32
S X1
Cx
2cr
A + Σ X/
nA
AR
jzk
1
4c
A Σ X/
11
n
jzb
20
X + Σ>
>/g
n
j>kk
Combining both terms above, we have
| +A - Es.
12
(
S
Therefore,
(x + + 1x, - 0;) T Er (X + - -
(82) 3k | 2
| X (XX + Ala) 1 X - _ss,a | 2
2 x A+ΣNy X1
1602 n²
(3 |
j>b
Lemma 22. Under the same conditions as in Lemma 18, and on the same event, for any N₁ < n N₂.
(xT + - )² ETT (XX(XX* + -
< 16cz - (
3 (8'x)² -s
where
N₂ max
4o2 [R+Inn)
8
Af2Æ"
20 Lo 2
A Σ \j
j>k
kk (++1n [
1ct
>1> $1 112
2
x Σ 23)
1
x+ E+
Nº A
j>
34

---

Published as a conference paper at ICLR 2025
Proof.
(XF ( T (XF + -x)))1xx+811)
||(XX" + X (XX' + + (5*x)) )2x)xxx0 X -
From Lemma 18,
x x +b S con(3"n) " "
In the following, derive upper bound for the other term.
1Xx" + ) X (Xx" + +Aa))=1
(M+ Mn + A) MAVET VT (M) T (M (M+
+
VT (M T (M Nh + A) ~
= | VTM (M& + Vr + An A12 + A22) -1
(Ix + (12 A22) (Mx + N1 + +n - + -
MAVE T
< 1/4e + +
||(MM + Ale Au1 A2)
M VET
V (Mx + AI + +11 AI -1) -1
S (11+ + +(,) | + Al + An - Aig(M A22) A22) ATT) -1 VET
M² (M& + A1 + A11 - (12(A TT)
= = (VT (Ma + + - -1o + 422) V)
VTMAVVETUTMÉN
-(V" (M/ Ale + +11 - + V) ||
= (X Xx + (An And + A22) V)
(xTxx) ET. (xxxx)² 3
(X X + Al& + (An A1 + AA)) -
The third equation follows from Equation 5.
We define two quantities that represent concentration error terms:
E X + Ale + V (An + v - (nESSA) -
E2 (X X2) 3 (nEs.))
Since n > 4ct (k + In }) 1a25 8 11 -
and n > 2c L ( + En>r 23) Ap X²25 1 |
|| | 
| | (nES.)) ) - -|((AA|)))) $
||STUع|| [ (1ESS)) 1|
F
(vn(k+ + In f) 2 I. (A+ E)> () (1+) nd1
(1 ndda Er.
(1 + n2
35

---

Published as a conference paper at ICLR 2025
2 (n) E (1 (A+En En)a>>)))
xp
112,,al
n²
2/
/
(k: + 1n
x²
Th ( +
Σj>s 21)
27
D NT +
n
k
n²
X
1
-g ST
+ 2n
2n
1
n
Similar to Equation 6, since n > 4c2 (k: + In }) 21
and n > 20 (a + Ejse>s) 23) A12F3
|
| k
<1.
DT 3. ?
-2
Since n > 2 (k: + In 2) 22g 1 || 12
|لمل i
E2
(nEsss))
- (nāS.)) )
|| $1
|ET,Bll
[nESS)>|| (nāSS)) -1
k + In 1
nd1
S cr//
d1 (ndd)
(A n |22
Cx +++h In
1
X7
Erall
n/n
2/
ス 5 n
Similar to Equation 7, since n > oa (k+ + x) 1i2=²
| (nāss) -3 $11 <1.
<1
Combining the four incqualities above,
(xXxx= + Ale + VT - - ATo)))) -1
(xXXx) $ ETA xx)x }/2
(X + AUx= + (T(Ai: - 112 A2)) - V) -1
< (niss)) " (nISN)) $ ETA (nEss) } (nSs..) -1
Ei (MISsN)² ΣT (nESs)) (nÊS..)
+2 2
(nSSS) -1 EςΣTT (nEss) à (nSis.))
+2
En (nDis,)+ ) ET. (nLis,)) ) Ej (n5....
+
(nESS) F2 Fz
+
+2 +
Ei (nIs,a) Er (nīs.))
+2
FF (nDs,))
(n5s..)
+2
E, EEE (nEs,,) En
36

---

Published as a conference paper at ICLR 2025
+ E, , E2 (nE.S..) E ExEll.
In particular,
(nIs,e) & Iy (nEsu)* (nās**) |
n n.
1
E5 S
E
71
1
1
Dr
The inequality follows from the fact that |BAB| || S | ||CAC|| where A, B, C are positive semi-definite matrices, and C > B, which implies that A²CA > A BA
(niis.)) -1 Eg (nās..)) 1 (nIS..) $ EinEis (nSis.))
(nEss.)) $
(nZis.))
)) |B2ll (nES..)) )=1)
< (lEil)
n 1
|
(nSis.))
$1 (nSi..) -1 / ((2SSN)) |ET.All
|| [(مiis)) ||| (nāis) 1
s ; n
The other terms can be similarly bounded. Therefore,
(X + Ale + V= - A20)
(xFXx) Σx, xx)* 1/2
(X Xx + A1x + v yiA - ( A12 + A22) 11
16
Eg
n
B.3.4 BIAS IN THE LAST d DIMENSIONS
The upper bound for the bias in the last d' k dimensions is extended from Tsigler & Bartlett (2023)'s Lemma 28. The bias can be decomposed into three terms.
-t)) ΣT.-K (
< "(
3( XX + + 3(0)) (XX" + "
+ AAT) -1X
-
Lemma 23. Under the same conditions as in Lemma 18, and on the same event, for any N₁ < n <
N₂.
( XXXXX
+ +x
37

---

Published as a conference paper at ICLR 2025
S & A 1+ 2/
n| "
where N1, N2 are defined as in Lemma 18.
Proof.
+ MA X
< E - (XX" + XX +
< xIx
+XX)(XX + < 1 |XXx N "X,,,
& ||T xll x + M,,
x x+ Σ 21 ++ ))
-1
S | xll
(coT) c2t1
()n()t))
= E x+ {
n||ET, nl|ET,- EE,,
The fourth inequality follows from XXT + XI, > X X + Xi..
Lemma 24. Under the same conditions as in Lemma 18, and on the same event, for any N₁ < n <
N2.
XT + XX (XX" + -
x+ Σ N1
j>k
where N1, N2 are defined as in Lemma 18.
Proof. It can be verified by Woodbury matrix identity that:
(XXT + +La)) = (X_
(Is + (X + -xx) -1
Therefore,
(B)) (XX" + +
- + -1a) Xa
x (X + Xx + Xx) 81
< |E
X
+ Aaa)
X (Ix + X
34
|E || (X
X 105 + 2ل
+ -
< |E || (X= X + \Ra)
X x
(5sh+ + X (X NT, 21,) -x,x,,x
In particular,
(SSS) + X - 111
38

---

Published as a conference paper at ICLR 2025
(X XX_ +
x + الملا
218
S C2
j>k
x E
π
The second inequality follows from Mmin (ABAT) 2 positive definite.
Munin ( Hoinn (AA7) where the matrix B is
Therefore,
(gt) (XXT X
+ +1a)
< | IX + Aaa)
X
- (8:) D5
Dgsle + _ (X x + Na) -x+
))
)
2
1
Σ
<
|
T,
x
C
n
A
5>k
cx
L
+
Σ Xj
|Ex, x11 -
j>b
B.4 MAIN RESULTS
Theorem 25. Let T - & s. and u depending only on o. such that for any eN < n < rkk if the assumption condNum(k, L) (As- sumption 2) is satisfied, then with probability at least 28- ce/e
x-- There exists constant 2
V
Lr [
ntr (4]
1
T
c02
(A+ + ΣS>h>,) 2
n1
B
A
n2|2 #1l |1T|| + L X Ejsk
||3||
2
c
n1
2 + 9
1,2 [|]
+ I,
12/ TT|EET,-A)
Es,
X + Σラze A3.
N is defined as follows:
(k: + In )) $ 1|T (tr (T])-
N = max
LA Σ [1 (tr (T1)
Remark 8 (Sample complexity). We have assumed n > cN in the theorem. The first condition on N indicates n > k. From the inequality X < ||ET,.112 (tr [7])-2 < 122,, it follows that 2(k) in the best case, consistent with the sample complexity of classic linear regression.
39

---

Published as a conference paper at ICLR 2025
This optimal case occurs when Σs, Σy. In the worst case, (2(k2) where covariate shift is significant in the first & dimensions-e.g when the test data lies predominantly in the subspace of the first dimension. This shift in sample complexity under varying degrees of covariate shift parallels the analysis of Ge et al. (2024) (see theire Theorem 4.2) for the under-parameterizze setting. The second condition implies n > À Σj>k ^3. such that the regularization is not too strong introduce bias greater than constant (as shown in the first bias term). On the other hand, we assume n < rkk in the theorem, which is consistent with the over perammaamteri regime and Assumption 1, where the last d k components are considered to be essentially high-dimensional.
Proof. The theorem follows from Lemma 18, Lemma 19, Lemma 20, Lemma 21, Lemma 22, Lemma 23 and Lemma 24. For constant d, > 2 depending only o, these lemmas hold for values of n that satisfy the following inequalities:
n > 4c (k+ + In(1/8))A72=
n > 2c LXTe 2e
A Σ4
X3
jzk
n > 4c
k (k+ In σ)
\i>
n > LAIN
A + Σ X1
n > 4c
k k In (k+lnz)) ()
AP1% 8 ||T
(tr
-2
n > 2cA'LA
A
Σ 2/
| (tr
[
j>b
n > 2c +
n> 4c
k (k+11 g
1
|ETT, 1|2
n1 > L
x+ Σ Xj
j>k
n < Am1
x Σ
j>k
sufficient condition for all the inequalities above is given by 4c, N1 < n < rk. This follows from the following facts:
A1 11 1,
<> 2,
1,21,
1: (tr S -
)
-1 2
Σ E s
5,
E||ET (Ir
1 ET. x 5, )
-1
Then, with probability at least 28 d - u//c;
V/2 < 16x 2 (1 + ott 2) tr [
n
40

---

Published as a conference paper at ICLR 2025
+ LLn
A x+
tr -
12k
1 tr
S 320
n
-2
+ 1
A >
++EM
tr T
53k
2
16c4 B/2 <
A + Σ Aj
(8t) (D)D55
,,,
T s.
n²
+ 32d (1 + (4
Ds,k TT 5.6 ($1x) -
+ 322L
t
Σ 11
+11 7 -ES
16 I + n
x Σ >/
|
+ +33(mM)
2
S 16c2
1
A Σソ
S. E
n2
j>k
+ 64
| 2T A
(8*x)² (8'x)²''3 1'
+ LL
+ I++ Aj
|ET,-NI ("t
+ +3cLL= 1
x+ Σ Ng
|
j>k
+ +3(02k) )2
2
< 116/4
x
Σ
\1
(8:)
x ni
s.
j>k
+ 64
(B'*,) TES,
+ LcLLa
x Σn
Xj
|Et,- ES.
j>b
+ 3c 18
1
X Σ X j>kk
n + 12
Egg ΣJ E
The last inequality follows from:
(Btx) - = (B*,))
T - D5. ET, E ンン 18xx
<
- Σx. IT. 05 1
( "'
k k
41

---

Published as a conference paper at ICLR 2025
By taking 134cf. the proof is complete.
Corollary 26 (Restatement of Theorem 2). Let T - - and
- There exists a constant e > 2 depending only on o, L. such that for any e.V < n < Tke if the assumption condNum(K. (k. 6, L) (Assumption 2) is satisfied, then with probability at least 36,
V
1 tr [T]
tr(4]
CO2
2
n
h
R tr[v]
|1
A (A+ )=
+ 11 Ex.- ) |
+ n -r.-k
-
g
Th
ES, k
N is polynomial function of l + In(1/8), A 1+ (A+ Σj>x 1/)
Proof. The first variance term follows directly from Theorem 25. For the second variance term, by plugging in the definition of Rg.
ntr 24
L2 tr [Es, -s.-
2
(A E
Rx Σj>e X3
L n Lr Rg [r
For the first bias term, by plugging in the definition of rk.
A + jock Ag
11 12 xll
||
Σj>k 23.
n
A+ Σラsk A3
2 |
Eg Eg.k
[
L
rk Ak+1
Similarly, the second bias term can be transformed into:
| | 2 - L |T
n A + Σ Ej>e 2
| Es.-
L |||||
|| - x
Tkk
Aut1
Since the statement of Theorem 25 holds with probability least 1 25 ce c/e we only require ce-n/e < 8, which is equivalent n clnc cIn(1/8). Combining the lower bounds of in Theorem 25, we should have:
max elnc+ cln 8¹
1 c(k + In 5) ) |ET, (tr [T))
cLAG> (A+ + Σ x))
j>b
For the first term in the maximum argument,
< a + ccln 1
clnc cln x
S c 2 k (n+ 1
The second term:
c(k: + In J EET | (ur [7])
< c(k + I 1192
||
(Mx (E tr -2
42

---

Published as a conference paper at ICLR 2025
s c(k + In 3 19 11312x11
= =((k + In 8) 19
The first inequality follows from tr[MN] 2 Mmin (M) tr(N] for postive semi-definite matrices M, N.
Similar, for the third term:
CLARA Σ X3) [T)[[T[(
j>k
<CLAR> (2+ X
jok
S cLL + J (X+ Σ X1).
jzk
The proof is complete by taking c as e² and N = (I: + In 2)) (22 (A+
C LARGE SHIFT IN MINOR DIRECTIONS
In this section, consider the scenario where the signal 8 mainly concentrate on the first k components (here we choose the basis to be the eigenvectors of Es), but the target covariance Ey may not be small on the last d - k components.
C.I LOWER BOUND FOR RIDGE REGRESSION
In this subsection, we will show that the original ridge regression algorithm will not work under this scenario.
Recall our model:
y = ==T x +
(8)
We write our data
Y= = X,8 +E,
(9)
where Y (y11. Brx) R=x1, (z)..... =T)"² E Raxd e= (e....., ".) denote by Egg = ====x= - the sample covariance matrix.
T E pax1 We
Assume the same assumptions as in our previous section still holds. We let Eg = 1[ be the following: its eigenvalues '1, Aa satisfies X =... A 1, Ac+1
A++lva/Ca
C1/V7 for sufficiently large constants C1 Cg., and the remaining eigenvalues are all set to zero. We let Ey = Ia. Then the excess risk is E, [ - 3 - 3] = E, 1 g1 We will show that under this scenario, ridge regression can not obtain error rate of O ())). To this, explicitly write out the ridge solution:
8 = (XT X + Ala) -Xx
= (Es + -1)-1/ xTy)
(Es + - 14) (= (X8* +c)
-1
(Ss + - Ia) 1a)
-1
x X3* + -
1 xTxe
= (Îs + 1a) 1
+
n
43

---

Published as a conference paper at ICLR 2025
(Es
~ E500 (Es + L -aa)
-ax
(10)
"
"
n
Therefore
3- 8r =f$= +
X Iaa) -Es3 8* + (Es X
- Ia) - -
n
n
n
=(5s + -aa) -1)=~E533 - (Es + - -a) - + -a))8* + (Ess
A
"
71
X [Es + X -a) 8r + (Es + - Id] - _
Taking expectation with respect to
X²
tr(e (ifee(((s) + A -aa)
E.113 - 1²
[Cis + - 1a) 1a) 3r
112
n
X²
I(Ss + - -a)-1
+ 12 tr((2, -5s)
n2
B V
(11)
where B = 2 [(Es + 1113-13111 is the bias, V= - tr(is + Ia) - is the variance. We
state the formal version of Theorem in the following:
Theorem 27. Under the instance consider, namely AI, da satisfies A
A 1,
Ak+Lvn/Cal = Ci/V, Ak+LyR/CaJ+1 = ... A = 0. WLOG assume o = 1, C2 (()) k log ) ) 1 for some absolute constant C. and マ y With probability
AR+1
1- 8, when = CVT, we have Y 2 C", where C" > is some absolute constant. When 3/4
we have y 2 C Vn When 2 n 3/4
118 !|2
9/n
Proof. We will use the following concentration lemma modified from (Vershynin, 2018, Exercise 9.2.5):
Lemma 28. Let {=:j_ be i.i.d. d-dimensional random vectors, satisfying: 2q is mean zero, E|rx" = Σ and is
in the sense that
[10221/0011
Elexp(u" (a))p( s exp
X (.1,"", ,n)"² E Raax Then with probability
r + log
+ log |ز|||
S Σ|| S Co
n
n
where r == tr(E) | is the stable rank of E, C an absolute constant.
Applying Lemma 28, we have
r+ r log 2
log
1 - EC
n
n
where r= Σi \ k IVT/C21 ct < + C1/C2. When n 2 C1/C2 + Ie + log 3. we have
Ci/C2 + log
EEg Esll S /
n
We denote by Â, > ... > Λa the eigenvalues of Eg. Then by Weyl's inequality (Chen et al.,
2021, Lemma 2.2), [3 -All E5 Es|l- Combining with previous inequalities, we have
44

---

Published as a conference paper at ICLR 2025
20 / /w/cuthttoot Six S 20 /
/c/C for sisk, k. S. 20 / 2
"
n
n
N s C. +20% / / 1 for k + 1 kis /
If we take C2 2 Ci(( )² - -
vn
log ()= then 201
C//Cttbtlos < C 2
Therefore we have S i -
for k + +1sis 3 2
n
k + Lvn//22 When x = evn,, we have
V
A Ia))
tr((Es
u2
n
n
d
(7+ +
-2
2 11
Σ
(x,+ +
2
-5
n
k=+1
Σ
(x++ () -
vn
K+LVT/O21
Σ
301
+ c م
C1
2/n
2/n
i=k+1
- [V/
1
C1
C1,301
303
+ -)-²v/ V/
2
2
C1 3C1
2
+ +c)-2
(12)
4C2 2
Similarly, A S n2/4.
k+Lvn/Oal
Σ
(3+ + -
N
+++1
k+L/n/Cal
Σ
(A: + 11/1)-212 11/4--
a++1
++|T//C2
3C1
-2 Ci
Σ
+ n 1111441-2
2/n
2/n
*
C1
301
LV/
+ n -2
2
2
> Ci 1/2
(13)
16C₂
when n 2 (3C )4
As for the bias term, assume X 2 n3/4, Using the same concentration argument, we have 2 >>> 2, >
1/2, for 1 i < k. When x n, Amax REs Aaa) I 2 + X/n I 3, therefore Amin ( (Es +
-1) 2
1 This implies
3-
2 n
X
B
11Ss
+
Ia) -1
n
3/2
1[S5 + A
-a) -18-11
n²
((Ss + Ia) - ) 1
Vn
9/7²
45

---

Published as a conference paper at ICLR 2025
When À > n, Amax Ama Ia) S 2 1/n v implies
3A which means Amia (C9 A + AIa) 2
This
3A
X B
(Es + X [a) 13111
n²
n² minl ((Es - (|) 3112
aa)
X² n²
n 9r2 11
|
9
C.2 UPPER BOUND FOR PCR
In this subsection, will give the following upper bound for Principal Component Regression.
Theorem 29. When 2 (r + log 1/2 (x, d 2011
)²
xg ((((Ss)))'Ez)
d1 )
)2( ول
r + log 11,32112 + Lo2 ((EExx))--TT
E. 3 0
A Ac+1
Er 3= 11 - -T
Ab
Σd A1
where r
Proof. For simplicity, we assume we have a sample size of 2n, and in the first step we obtain an estimator Ū Rdd of the top-k subspace U
Ix
Baxk by using principal component anal- ysis on the sample covariance matrix Eg == x = E namely i = (w,, ... 0x)
0
where is the i-th eigenvector of Eg.. We denote the distance between the estimated subspace and the original one by A == dist(U, Ū) - Ø. For controlling A, we have the following lemma (Lemma 6):
Lemma 30. With probability at least 1 - 8,
(V
r
log
r + log
A d
A Cod
n
n
Au
2 Az X
where r
In the second step, we do linear regression the projected (second half) data. With little abuse of notation, we still use E xx to denote the data matrix indexed from n + to 2n. The data here independent from the data in step 1, and therefore independent of A. we Z = Xu E Bank be the projected data matrix, the estimator we obtained is given by
3 =
-000
(14)
We aim to bound the excess risk on target, which given by 11 3 = (3
|+ We introduce the following notations: suppose 8 = (Bt,... "2)"". We let B7 == (8f.... fr, O.... .TTT. S = (O.... 0, B ,87) = 3r - 33. Here we present an in- termediate result for bounding the excess risk:
46

---

Published as a conference paper at ICLR 2025
X (u((ESs))
" 12 log(1/6) X tr((Es.)) 1Era) then with probabil-
Lemma 31. Assume A ity 1--d 8,
When n
42, [2rl
X | + _
3.113- - 1 S 0(113)114
ET ||1| +1 | #1 + +
A
If further n 2 A log(1/8),
E. 1 - 12, & 0(1 (1 (1 TTo
) ) -111 (
+ v² tr( (Es,,) 'E,,x)= + |E ||1=,1111==* xll
+ -
A
From Lemma 30, when
= log
-i di
log 5: have
A
A1
r + log 1
A 20
04
d
Ac+1
Therefore when n 2 (r + log 1 )000 (x Lemma 31 will be both satisfied. We can thus apply Lemma 31 to get
xa 1
Er the assumption for A and n in
A
At tr((
E, 11 B 0000
A
)²(
A1 3
|
r log n
1 _o2 (r((Es,)) -1 'TT,))
d
dc+1
A
|1|
12 -kll
+
A
Ed where r
A
C.3 PROOFS FOR LEMMA 31
In the following we will prove Lemma 31.
Proof for Lemma 31. The proof idea is similar to (Ge et al., 2023, Theorem 4.4) and (Tripuraneni et al., 2021b, Theorem 4).
We can decompose
3 3* as
8 - 8* = - X"X""XXXX) 3*
-010"""""(00=0"""XX"""""" + -
+ +X31 +6) -80 + Bi)
= = A2 43 -
where A = x000xx=xx)-10
X - Big A2 Xx Aa
0 x²0 X" Therefore
- S | + 1 + +1 ||
(15)
We give three lemmas for bounding the related terms. The first lemma considers the bias term A and 2 maxfo $ d lokkoog1/8)) o lologl/ (og()))), then with probability at
Lemma 32. If A < TN
least 1 5,
47

---

Published as a conference paper at ICLR 2025
A A1 )|
|| 11 S 011 A
(
If we further have 2 -AA- - log(1 (1/6), then with probability least 8,
| & 1O11 P + A + (T & 0(11 (11101
The second lemma considers the variance term As:
((lEEs,)""'pp and
o11 " 1 log(1/6)
Lemma 33. If A < least 1 - 6,
then with probability
Af (=( -2nra))
E. As s 0 (r(("s,))
For bounding A2, we actually have similar result bounding Ag:
Lemma 34. If n E o 2 log((18)) and A < min
[| 2|p2
As. 4X1
}. then with probability at least
5
11 112|EE x11
A 12 < 0
(16)
A6
By Lemma 32, 33, 34, together with the decomposition (15), we have with probability - 6, when Ni,
3 1- S 0(113) 2~ >I!ET!
-
(17)
n
ET. |1| 211l~11' Ess =ll
(18)
If further 2 0'A - log(1/8),
A1 > E, 13 < 0(113 (2
A ET, + 111E=)])
(19)
A
1 - (r(((s,))) +
[T ||133~11111110 11
(r - +
+
(20)
A
C.4 TECHNICAL PROOFS
In the sequel, we give the proofs of Lemma 32, 33, 34 and 30. We first prove some additional technical lemmas. The following lemma, which is simple corollary of (Tripuraneni et al., 2021b, Lemma 20), shows the concentration property of empirical covariance matrix.
Lemma 35. Let {a,) be i.i.d. d-dimensional random vectors, satisfying: 2; mean zero, Eirz?) such that max (E) < Cmax and - Sub-b--aausi,n, in the sense that
E Elexp(u 21)] S exp [100>/2011
X (01,... "2,)" gaxd Then for any A, pa have with probability least 1
TAT X n
k k +
1og(1/8)
log(1/5), (21)
B EB S ( ||]|
n n
72
n
48

---

Published as a conference paper at ICLR 2025
Proof. We write the SVD of A and B: A = UAAVT, B = U2A2V where U1 R A2, V1, V2 E Rixa, Then
X |
X B A = I
12AAV/2 EVAL
x n X )02
2 |V
1U UT
- ||AIIIBIIUU
EU2l-
(22)
Now since U1, U2 dg are projection matrices, can apply Tripuraneni al. (2021b) Lemma 20, therefore
X X U12 - |IU
k log(1/6)
(og(1/0)
(23)
n
n
m
which gives what we want.
The following lemma is basic matrix perturbation result (see Tripuraneni et al. (2021b) Lemma 25).
Lemma 36. Let be a positive definite matrix and E another matrix which satisfies ||A-1 $ 4
then F' : (A + E) - A satisfies || S #
||
With these two technical lemmas, we are able to prove Lemma 32, 33.
Proof of Lemma 32. Notice that by the definition of U and By we have UUT By = Br. We denote a = UTB 37, then we also have B = Ua* Therefore
A = xO x00 Bi
=(00TxTX0)=00x">>> - Uaa
= -000 - U)aa
We consider Ū Bddk and Of (dd(dd)) orthonormal projection matrices spanning orthogo- nal subspaces which are rank it and rank d - k respectively. so that range(ū) @ range(UA) Rd. Then A = dist(Ū, | 2l.. Notice that La 00T Ü, we have
x,0"x""x))==xx'''''xx"x U -
-00"""1000000XXXX0000000000000"0 x² """00""""0"""""""0"000"""""""""" 0000:"10000011xxxx00000000000100 -000""""10000"""X000000000000000
(24)
Thus
|| ATIAAI
-0000000000000000303000000001110 -U)"
< 111111100"""xx00000"X00000011111 -0,000,
< "1a 100
+ 11 (1(0TU))
(25)
Here the notation
|
VIMTT, M| for matrix M.
49

---

Published as a conference paper at ICLR 2025
For the second term,
10:0 S
A
(26)
For the first term,
X²
X'x -0000 -00 10) =110(0T "
110TEş0,00U" +"""(("" ((""E,))
+ Ei)l
s $10"EşL00U " +
10 130)~111 1FII)
(27)
F ( " aim to show that || S 10TEşŪLŪTU" and ||F]| S I((Txşt)~1 = C- for suffi-
where Ei =
We
ciently large n, therefore the term (27) can be bounded well. First we need a careful analysis of JÜTEşÜ __U_-[UU I. It is obvious that
TT'ESOLUTUM S MII A:0
(28)
As for I ||. notice that if without the "hat", we have UT by the definition of U and Es is diagonal. By definition of distance between two subspaces, there exist R E O and Q E ((d-R)x(d-R)) such that | - UI A 1111 Ull- Then we have
Eا-لl = -IRTŪTESÚQQI
UT الااو
- -
=
S 10==000000000000 -
< OR -10"""/00000000010>000000000
< 2A||Es|I.
(29)
Combine (28) and (29), we have
10 13$0100U0 U* S 0(A
(30)
In order to bound [I] let E xxxxx 1 Ss then by Lemma 35, with probability at least
1 8- 8,
+ k log (1/5)
log(1/6)
| < <00731ESs|((
(31)
Therefore,
EE(TTSÜ)~-! | 1-8)-11
< | min
k 00220=i 1 I1(
log(1/0)
log(1/5) )),
+
(32)
n
n
n
where Cmin == Amin Eg). Notice that 2 o -
EEs 2 log(1/0) implies V k
+
V log(1/6)
log(1/8)
S o 2 [Dssl Thus, we show that when is large enough, we have 1 Therefore we can apply Lemma 36, which gives
n
n
E(TT) -s s 4.
||]|| = 3
50

---

Published as a conference paper at ICLR 2025
4
7 210
1
(33)
min
As for |ill, directly applying Lemma 35, when 2 a
we get
k +
log(1/6)
(og(1
|Bil & 0
VV
))
k <
log(1 1/6)
log(1/ (0)))
+
(34)
when n 2 d'Allo((1/0) we have
Eill s Essl)
(35)
if further we have Z o04 - log (1))), then
|| S [ss))
(36)
Combining (27), (30), (33) and (36), we have
s 11 < |0> I0
s 004 C min Σ+|l)
(37)
Combining (25).226) and (37), we get
| 12, - T +1000000
0 ||00://0044|100120HC0000~0111110
(38)
with probability at least - 6. Also, similar to (29), we have
101Σ,0111 = 1QTūTT=Ō1Q0 Q1I
< 111 UTTULI
< [1 1
(39)
Similarly, we can further know that Cmin close to Upi
Cinn = >x
2 - UTEUUI
2 de -
Ak:
(40)
where the last inequality holds when A <
de. 4x1
Finally, combining (38), (39), (40), we have
| <o(1la" 50(11011?(A' d 21
d
d To
<001187
(41)
51

---

Published as a conference paper at ICLR 2025
when A < Ak and n 2 maxfo log(1/6)), ( log(/))) If the previous proofs replace (36) by (35), we have
AI >l + + AR
| < <011)
(A
(42)
0 1 ET|
(43)
when A < Ae and n 2 m AL ) log(1/0), o log(1/6)). Notice that by definition of U,
x
4A
UTETU1= -T. therefore the result is exactly what we want.
Proof of Lemma 33. Recall : = 00==000""00000""' Therefore
|| = =11000011""0001,0000000000001110
= =xN","1(001,1,,,,,,,,,:0xx00,,,"
Taking expectation with respect e, using B[ee"] 12 we have
Aa E[tr(ce' XOO x"
= -F
=
(44)
Here we actually need bound stronger than (33) for ||||: recall (32), we have with probability
1
k k + IEs
log(1/5)
log(1/5)
EE('"ESÜ)~ =
)).
(45)
n
n
n
Applying Lemma 36, which gives
F Σ "S"""s()" -10 -0)
k - Iis 11
l18(1/8)
log(1/0)
s 00000
n
n
1
< 0
EsU) T ΣT)'
(46)
when n 2 -'C-4 milll
Es |
2 log(1/0). Therefore we have (0
E, A1
(
,
n
((((
-0'
" 1 102 12 tr( 1 -
$
n
< 2 (((t((((""
-
(47)
n
n
The
remaining thing -() U).
is to show that indeed ((((())))~(((
is
close
to
In fact, -(77,111)))
Notice that
52

---

Published as a conference paper at ICLR 2025
have
(48)
s SHuu0117755000117033001241111113
s E +
U) trU "
(49)
when $ Au (n EgU) [1y71
Also, we have
2kll
|| -2ESU)
S =
therefore
((("""""s z ",,
EYU)
< 2r((="";U>~~0>>>4
(50)
X if < 4A1 ()(
ErU)
Combining (47), (48) and (50) we have
E, |1 3 S O - 12 tr((UT ESU) -3U)~1""E,U)
whenever A < tr [T S min
A tn( S1 -1 ds E, Un
4A tr(
4k Exll
and n 2 O'C-1 1 1-5. Notice that UT EsU = Σz,t and EUU = Σr,k, therefore the result is exactly what we want.
min 1 -,,)) log(1 1/8), with probability at least
Proof of Lemma 34. Recall A₂ = :0:000TT00 xTx) - Also we have
100 -IR
< -1 + OR
I 10'ESU1+221E311
(51)
Therefore
|| X 11111100000000100000000000000000
< ",000"""""""00000"""""""""10"""" "" < |AICII -
2 A||A ビ 1|
(52)
when A < 10 U
where we let A = 1 XX
vn If we define B xū E
21
vn
Raxr, then A = LBB" -)2 Bd. Let the SVD of B be B = PMO" where P E Baxk
M, O E Raxk then
||||2
|B By BT ll
n
(MMO 7
1PM-2pT
53

---

Published as a conference paper at ICLR 2025
M -112
71
(B 112
(53)
Let F 0) - -1 Recall (33), which states that with probability at least 1 6,
we have |F]|
1 0
min 1 f when n 2 o
min [e 1 (1/6) and A S ds.
Therefore
Ax,"
||||| v |1 x X
0) 1|
E(( Fll
E5) ||]
n x
(54)
Thus ||||| < () As for || 112 notice that the first-k entries 39 are zero, therefore x = =X-18= x. by Lemma 35,
||: X x B
1 +
log(1/8)
log(1/5)
n
n (55)
Therefore we have
XT X )
|| = m8:
X7 X ) - -1.
S 113311-ss + -13
n
- 0 8 1131
(56)
Combining (52)54) and (56), we have
| 00 |1 ΣT 111 ||]
(57)
dk
when n 2 -C I log (1/8) and A minf
E,,"" U|| dg +4x1
}.
min
2|2r
Finally we prove Lemma 30 in the following.
Proof of Lemma 30. In the first step, obtain Ô Rd by selecting the top- eigenvectors of the sample covariance matrix Σg 1xxT theorem (Chen et al., 2021, Corollary 2.8).
1 E. xzae" using PCA. Then by Davis-Kahan n
2 21S Esll
(58)
d A6+1
Therefore it remains to bound |وS Es|l Applying Lemma 28, we immediately have
1 (v
r log 1
r + log
1$S Esll S Cod
A
where Σe A, Together with (58), have with probability least 1 - 6, Ag
(V++ log
r log 1
A
A < Co
71
n
As
Au+1
54


Reviews:
[{"review_id": "cWIYsPK3jO", "reviewer": "Reviewer_R8Hj", "summary": "The paper provides an analysis of benign overfitting in the out-of-distribution regime. Both ridge regression and PCR are analyzed and have rates $O(\\frac{1}{\\sqrt{n}})$ and $O(\\frac{1}{n})$.", "questions": "- Does the result in PCR requires the number of relevant components k to be known in advance? What is the effect if the number is mispecified", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The paper is very well written. It presents complex results with clarity and cohesion. The results are novel to the best of my knowledge and the setup under analysis is very interesting.\n\nI didn't thoroughly check all the proofs. But the steps in the main text seem logical to me.\n\nThe differences between rates for Principal Components Regression and Ridge Regression are surprising and interesting.", "weaknesses": "I believe the paper could benefit from some simulation experiments confirming the theoretical results.\n\nFor instance, verifying the rates  $O(\\frac{1}{\\sqrt{n}})$ and $O(\\frac{1}{n})$ hold for a small Gaussian example would strengthen the claim, and help to support that the mathematical proofs are correct.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sT1Zltko4r", "reviewer": "Reviewer_NDnK", "summary": "This manuscript investigate benign overfitting in out-of-distribution (OOD) generalization, focusing on over-parameterized linear models under covariate shift. It extends the concept of benign overfitting from in-distribution cases to settings where the target distribution differs from the training (source) distribution. The authors provide non-asymptotic excess risk upper bounds for ridge and principal component regression under specific structural conditions on the target covariance. More precisely, the main contribution is an instance dependent upper bound on the bias and variance terms of the excess risk of ridge regression under OOD. In particular, this upper bound shows that benign overfitting transfers from the in-distribution to the OOD setting when the target distribution’s covariance along the high-variance (or \"major\") directions aligns well with the source distribution’s major directions.\n\nThe authors also provide a discussion of an example with significant shifts in the minor directions, showing that in this case ridge regression incur a high excess risk, despite overfitting being benign in-distribution. Finally, the authors show that doing principal component regression (i.e. ridge regression only on the major directions) can mitigate this phenomena, since it avoids the excess error contributions from misaligned minor directions.", "questions": "- What are the main challenges in proving a matching lower bound for ODD similar to the in-distribution case?\n- The fact that the analysis of OOD boils down only to the alignements of the covariance of the source and target distribution is closely to the square loss and linear estimator. How much should we expect this to transfer to other tasks, such as linear classification for instance?  \n\n- L39-42:\n> \"*However, over-parameterized models, such as deep neural networks and large language models (LLMs), which have more parameters than training samples, are widely used in modern machine learning.*\"\n\nThis sentence is misleading and overly general. In fact, most of modern LLMs use more tokens than parameters for training. See for example Table 2.1 in [1].  \n\n- L11 in the abstract: \"over-paramterized\"\n\n**References**\n\n- [1] Brown et al. [Language Models are Few-Shot Learners](https://arxiv.org/pdf/2005.14165). NeurIPS 2020", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The manuscript is well written and easy to follow. It contains a nice balance of formal and intuitive discussion. The review of the in-distribution benign overfitting results is a nice addition that helps highlighting the contributions. Overall, I think it is a good contribution on a topic of interest to the theoretical community at ICLR.", "weaknesses": "The lack of a matching lower bound as in the in-distribution case of [Tsigler & Bartlett, 2023] is a weak point of the manuscript. Another minor weakness is that the technical contribution is also somehow limited, as it mostly relies mostly on extending existing results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fHo48DJst0", "reviewer": "Reviewer_ZYgW", "summary": "This paper considers a model to study benign overfitting in the context of out-of-distribution (OOD) generalisation for overparameterized linear models. The authors focus on covariate shift. \n\nThe authors prove the following results\n* The paper derives an excess risk upper bound the above setting. This bound generalizes directly the one in [Tsigler&Bartlett 2023].\n* The authors consider specific choices of covariance matrices to consider two opposite cases:\n  * If the major directions of the shifted model are the same and the minor directions remain small the begning overfitting still is present reaching a $O(1/n)$ bound for the excess risk.\n  * For any ridge parameter $\\lambda >0$, under a different covariance model, the authors show a lower bound on the excess risk as $O(1/\\sqrt{n})$.\n* To mitigate this problem the authors also consider principal component regression and show that under specific conditions it always achieves the $O(1/n)$ rate.", "questions": "* Are the conditions considered in Section 3.1 the most general ones for which the rate of the excess risk is slow?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* First work to provide non-asymptotic guarantees for benign overfitting under general covariate shift\n* Provides practical insights into when ridge regression vs PCR should be used.\n* Results generalize and recover previous known bounds as special cases fitting in nicely with the literature on the topics.", "weaknesses": "* The clarity of the paper could be improved. While it is very clear the discussion about previous results and how the current result generalise the old ones I feel that the assumptions for the original contributions are hidden in the appendix. The paper would greatly benefit from a clear statement of the assumptions at the beginning or just a discussion of them. A specific instance of this Theorem 5 where the result depends on the additional assumptions that $\\beta^{\\star}_{-k} = 0$ and the fact that the overlap gap between major and minor directions is large.\n* Another problem that I find, connected to the previous one, is the lack of simulation studies to illustrate the theoretical findings. As the setting of linear regression with general covariances is generic enough one could back up the claim with experimental validation on real datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1oax1Ydshe", "reviewer": "Reviewer_MgYk", "summary": "The authors study the over-paramterized ridge regression under covariate shift assumption. Specifically,\n\n1. The manuscript shows the ridge regression exhibits “benign overfitting” given the shifts in minor direction for target domain is smaller than source domains’ counterpart.\n2. When there is significant components in the minor directions, the manuscript shows ridge regression only achieves a lower rate, e.g. $n^{-\\frac{1}{2}}$. It also show using the PCR can achieve the fast rate $n^{-1}$ as in-distribution learning.", "questions": "1. As the comment I raised in W3, is it possible to provide adaptive rate for PCR?\n2. While the lower bound for ridge regression is instance-specified, the general intuition is that ridge regression typically fit the space in the whole scale. However, I would like to know if there is any special case that ridge regression can attain fast rate in large shifts.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "1. The authors provide extensive context to introduce the background and problem, making the logic very easy to follow.\n2. Clear discussion about the role of $\\mathcal{T}$ and the overall magnitude of $\\Sigma_{T,-K}$. \n3. The instance-specified lower bound for ridge regression for large shift in minor direction scenario.", "weaknesses": "## \n\n1. For the large shifts in minor direction case, while I really appreciate the instance-specified lower bound for ridge regression, the result for PCR is more like “Shoot The Arrow, Then Draw The Target.” Given the assumption that the true signal primarily lies in the major directions of the source, it is not surprising that PCR works well as one has priorly excluded those un-handleable/irreducible parts in covariate shift, which eventually works like the process in Section 3. \n2. The lower bound is instance specified. Although this is already a good example to show ridge regression is not a generic good choice for large shifts, but having the lower bound for general case make the contribution of the manuscript more convincing. Can authors elaborate more on the main obstacle for the lower bound in general case? \n3. The fast rate in PCR is not adaptive. Similar to (1), if you know the true cut-off $k$, you pick the correct number of eigenvectors, this degrades the technical contribution of this manuscript. It is desired to have adaptive estimator/learner to adapt to the unknown $k$ and achieve fast rate.\n4. (Potentially) Reviewer is not coming from the research area that working on over-parameterized models. Therefore, the reviewer cannot assert the technical contribution or novelty of this manuscript (although I see a detailed discussion on OOD in the over-parameterized model in related work ). I would like to leave this judgment to my peer reviewers, who are more familiar with this area.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)