Spurious Correlations in High Dimensional Regression: The Roles of Regularization, Simplicity Bias and Over-Parameterization
Authors: Simone Bombari
Marco Mondelli
Venue: ICML 2025 poster (2025)
Keywords: high-dimensional statistics
empirical risk minimization
spurious correlations
linear regression
random features
Primary area: deep_learning->theory
TL;DR: We provide a quantitative characterization of how spurious correlations are learned in high-dimensional linear and random features models. We analyze the effects of regularization, simplicity of the spurious features and over-parameterization.

Abstract: Learning models have been shown to rely on spurious correlations between non-predictive features and the associated labels in the training data, with negative implications on robustness, bias and fairness.
In this work, we provide a statistical characterization of this phenomenon for high-dimensional regression, when the data contains a predictive *core* feature $x$ and a *spurious* feature $y$. Specifically, we quantify the amount of spurious correlations $\mathcal C$ learned via linear regression, in terms of the data covariance and the strength $\lambda$ of the ridge regularization.
As a consequence, we first capture the simplicity of $y$ through the spectrum of its covariance, and its correlation with $x$ through the Schur complement of the full data covariance. Next, we prove a trade-off between $\mathcal C$ and the in-distribution test loss $\mathcal L$, by showing that the value of $\lambda$ that minimizes $\mathcal L$ lies in an interval where $\mathcal C$ is increasing. Finally, we investigate the effects of over-parameterization via the random features model, by showing its equivalence to regularized linear regression.
Our theoretical results are supported by numerical experiments on Gaussian, Color-MNIST, and CIFAR-10 datasets.

Spurious Correlations in High Dimensional Regression: The Roles of Regularization, Simplicity Bias and Over-Parameetrrizaion
Simone Bombari
Marco Mondelli
Abstract
has investigated the extent to which deep learning models manifest this behavior (Geirhos et al., 2019; Xiao al., 2021) and has proposed different mitigation approaches (Sagawa et al., 2020a; Liu al., 2021), given its implica- tions to robustness, bias, and fairness (Zliobaite, 2015; Zhou et al., 2021). The phenomenon, also referred to as shortcut learning, is often attributed to the relative "simplicity" of spurious features (Geirhos et al., 2020; Shah et al., 2020; Hermann Lampinen, 2020) and to the implicit bias of wver-parameterized models toward learning simpler patterns (Belkin et al., 2019; Rahaman et al., 2019; Kalimeris et al., 2019). Consequently, the core features that are informative about the task (e.g., the boat in the foreground) may be neglected, as spurious features (e.g., the blue background) provide an easier shortcut to minimize the loss function.
Learning models have been shown to rely on spurious correlations between non-predictive fea- tures and the associated labels in the training data, with negative implications on robustness, bias and fairness. In this work, we provide a statisti- cal characterization of this phenomenon for high- dimensional regression, when the data contains a predictive core feature and spurious feature y. Specifically, we quantify the amount of spuri- ous correlations C. learned via linear regression, in terms of the data covariance and the strength X of the ridge regularization. As a consequence, we first capture the simplicity of y through the spec- trum of its covariance, and its correlation with x through the Schur complement of the full data covariance. Next, we prove a trade-off between C and the in-distribution test loss L, by showing that the value of À that minimizes L lies in inter- val where C is increasing. Finally, we investigate the effects of over-paramettrization via the ran- dom features model, by showing its equivalence to regularized linear regression. Our theoretical results are supported by numerical experiments on Gaussian, Color-MNIST and CIFAR-10 datasets.
Prior work has attempted to formalize the simplicity bias re- lying boolean functions (Qiu et al., 2024), model-specific biases (Morwani et al., 2023), one-dimensional features (Shah et al., 2020) and their pairwise interactions (Pezeshki et al., 2. However, when considering high-dimensional natural data (e.g., the boat and its background in Figure 1), remains unclear, based on these notions, what ex- actly makes the features easy or difficult learn, and to what extent trained model relies spurious correlations. Furthermore, while Sagawa et al. (2020b) show that over- parameterization can exacerbate spurious correlations when re-weighting the objective on minority groups (e.g., boats with a green background), its effect on models trained via empirical risk minimization (ERM) less understood. This is critical point when additional group membership anno- tations too expensive obtain, and ERM is key part of training (Liu et al., 2021; Ahmed et al., 2021).
1. Introduction
Machine learning systems have been shown to learn from patterns that are statistically correlated with the intended task, despite not being causally predictive (Geirhos al., 2020; Xiao et al., 2021). As concrete example, blue background in picture might be positively correlated with the presence of a boat in the foreground, and while not being a predictive feature per se, a trained deep learning model could use this information to bias its prediction. In the literature, this statistical (but non causal) connection is referred to as a spurious correlation between a feature and the learning task. A recent and extensive line of research
Our work tackles these issues: we provide a rigorous char- acterization of the statistical mechanisms behind learning spurious correlations high-dimensional data, focusing on the solution obtained via ERM. Formally, we model the input sample as composed by two distinct features, i.e., [ar, v). where E Rd is the core feature and y Rd the spurious one. The first panel of Figure I provides an illustration with boat in the foreground (x) and its blue background (z). Then, we quantify spurious correlations via the covariance C (see (3)) between the label g ("boat") and the model output given [ y) as input. Here, & (a
'Institute of Science and Technology, Austria. Correspondence to: Simone Bombari bombari @ @st>
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Spurious Correlations in High Dimensional Regression
truck in the foreground) is a new core feature independent of everything else, see the second panel of Figure 1. Now, if C is positive, it means that the model is biased towards only because of y, since F' is independent from x' and g. More precisely, we provide a sharp, non-asymptotic charac- terization of C for linear regression (Theorem 4.3), Armed with such a characterization, we then:
Figure 1. Left two panels: pictorial representation of the core (spu- rious) feature x (y) and an independent core feature ă, taken from an image of a boat and a truck in the CIFAR-10 datasct. Right two panels: examples from a binary Color-MNIST dataset, where the labels correspond to the number shapes, and the zeros (ones) are colored blue (red) with prohability (1 + x)/2.
Interpret C via upper bounds on its magnitude (Proposition 5. This highlights the role of the regularization strength and of the data covariance via (i) its Schur complement with respect to the covariance of the core feature x, and (ii) the covariance of the spurious feature y. Specifically, we link the smallest eigenvalue of the Schur complement to the strength of the correlation between y and x, and the largest eigenvalue of the spurious covariance to the simplicity of y-
distribution shift; and Chang et al. (2021a); Plumb et al. (2022) mitigate the problem via data augmentation.
Simplicity bias. Recent work has shown that deep learn- ing models have bias towards learning from "easier" pat- terns (Belkin et al., 2019; Rahaman et al., 2019; Kalimeris et al., 2019). In shortcut learning. this property is formalized in different ways across the literature. The difficulty of a feature is defined in terms of the minimum complexity of network that learns it by Hermann & Lampinen (2020) and in terms of the smallest amount of linear segments that sep- arate different classes by Shah et al. (2020). Moayeri et al. (2022) connect the simplicity to the position and size of the features in an image. Morwani et al. (2023) define the sim- plicity bias in 1-hidden layer neural networks via the rank of projection operator that does not alter them substantially, and they focus on a dataset generated via an independent features model learned via the NTK. The NTK is also used to analyze gradient starvation (Pezeshki et al., 2021) and feature availability (Hermann et al., 2024), regarded as ex- planations of the simplicity bias. Qiu et al. (2024) focus on parity functions and staircases, analyzing the learning dynamics of features having different complexity.
Prove a trade-off between C and the test loss (Propo- sition 5.3), which implies that spurious correlations can be beneficial to performance when learning in-distribution. Specifically, we show that the optimal regularization min- imizing the test loss lies in an interval where C is positive and monotonically increasing.
Investigate the role of over-parameteriizatonn via a random features (RF) model. Specifically, we show that the RF model is equivalent to linear regression with an effective regularization that depends on the over-parameetrizzaioon (Theorem 6.4). This allows to leverage the earlier anal- ysis on regularized linear regression to quantify spurious correlations in over- wer-parameterized, non-linear models.
Throughout the paper, the theoretical results are supported by numerical experiments on synthetic Gaussian data, Color- MNIST, and CIFAR-IO, which validates our analysis even in settings not strictly following the modeling choices. Our code is publicly available at the GitHub repository sim -mone-bembari/spue http://pprrooooaorraaaa....o....
nigh-dimenssioal regression. The test loss of linear re- gression when the input dimension d scales proportionally with the sample size n has been characterized precisely both in on-distribution (Hastie et al., 2022; Cheng & Montanari, 2024) and under covariate shift (Yang et al., 2023; Mallinar et al., 2024; Song et al., 2024). Furthermore, Montanari et al. (2019): Chang et al. (2021b); Han & Xu (2023) have studied the distribution of the ERM solution via the convex Gaussian min-max Theorem (Thrampoulidis et al., 2015). Specifically, our work builds on the non-asymptotic charac- terization provided by Han & Xu (2023).
2. Related Work
Spurious correlations. Learning from spurious correla- tions in training dataset is rather common (Geirhos al.,, 2019; Arjovsky et al., 2020; Geirhos et al., 2020; Sagawa et al., 2020a; Xiao et al., 2021; Singla & Feizi, 2022) and it has unwanted consequences, e.g., lack of robustness towards domain shift, prediction bias and compromised algorithmic fairness (Zliobaite, 2015; Geirhos et al., 2019; Zhou et al., 2021; Veitch et al., 2021; Seo et al., 2022). Thus, multiple mitigation approaches have been proposed, with (Sagawa et al., 2020a; Zhang al., 2021) or without (Liu et al., 2021; Ahmed et al., 2021) available annotations. Specifi- cally, Tiwari & Shenoy (2023) exploit the difference in the features learned at different layers of a deep neural network; Izmailov et al. (2022); Kirichenko et al. (2023) re-train the last layer of the ERM solution to adapt the features to the
In contrast with linear regression where the number of pa- rameters equals the input dimension, random features mod- els (Rahimi & Recht, 2007) capture the effects of over- parameterization as the number of parameters is indepen- dent of d and n. Mei & Montanari (2022) have characterized the test loss of random features, showing that it displays a double descent (Belkin et al., 2019). Furthermore, the RF model has been used to understand a wide family of phe-
2

---

Spurious Correlations in High Dimensional Regression
nomena such as feature learning (Ba al., 2022; Damian et al., 2022; Moniri al., 2024), robustness under adver- sarial attacks (Dohmatob & Bietti, 2022; Bombari et al., 2023; Hassani & Javanmard, 2024), and distribution shift (Tripuraneni et al., 2021; Lee et al., 2023). This model has been also considered in the setting where the data has two dependent components (Loureiro et al., 2021), although it was used to study the training and generalization error when only partial information is available. The equivalence be- tween an over- parameterized RF model and a regularized linear one has also been studied in detail (Goldt et al., 2022; 2020; Hu & Lu, 2023; Montanari & Saced, 2022). However, existing rigorous results show the equivalence at the level of training and test error. In contrast, we are interested in the covariance defined in (3) and, for this reason, we prove an equivalence the level of the predictor (Theorem 6.4).
background, see Figure 1.
In this setup, the training data is used to learn (z) through parametric model f 2) via regularized empirical risk
minimization (ERM). Specifically, we perform the follow-
ing optimization in parameter space:
l (F(O, 2), + (1(00.2).)++111133 +110113
Ø= arg ming
(1)
for some regularization term X 2 O, where is a loss func- tion'. We define the test loss associated to the model f(0,-) as
[()) = BExxPPxx [ (1(0.))..)
(2)
We note that this test loss is in distribution.
Spurious correlations. We express the extent to which a model f(0.-) learns spurious correlations between the spurious feature y and the label g as
3. Preliminaries
Notation. Given vector v, we denote by ||||| its Eu- clidean norm. Given matrix A, we denote by tr(A) and [l its trace and operator (spectral) norm. Given sym- metric matrix A, we denote by Amin (A) (Amax (A)) its smallest (largest) eigenvalue. We denote by À (without sub-script) the &a regularization term in ridge regression. All complexity notations (2.)), O()), w()), o(-) and @(.) are understood for large data size n, input dimension d, and number of parameters p. We indicate with C, > 0 nu- merical constants, independent of n, d. p. whose value may change from line to line.
c(0) = Cov (s (0,, 1 .y (T))
:9)
where the covariance is computed on the probability space of [x .v ~ -xx, g = (z) and of the independent core feature f Pxx In words, C(0) expresses how the out- put of the model f(0,-) evaluated on an out-of-distribution sample [ [y''" (where the two features are sampled in- dependently from the marginal distributions Px and Py) correlates to the label associated to the in in-distribution sam- ple g = fz) = (z)) We highlight that, if the model [( -) does not rely on the spurious feature y, then C(O) = 0 as x and I are independent.
Setting. We consider supervised learning with n training samples {(21,91) .i),...), (zn. } and labels defined by a (not necessarily deterministic) function of the inputs gi = (=)), where z E 2d denotes the i-th training input and gi E IR the corresponding label. Input samples are composed by two distinct parts (or features), i.e., a," [x.T .v, J. with Ki E IRd, and they are sampled i.i.d. from the distribution Pxy. We further denote with Px (Py) the marginal distribution of the r;-S (y:-s). The features a and y have the same dimension d to ease the presentation. We opted to focus on the setting = [ar, y] due to its connection with the motivating example of images with background, but the analysis could be extended to other cases, such as + y, briefly discussed in Appendix D.
We note that (3) formalizes to the regression setting the def- inition in the survey (Ye et al., 2024) and the fairness metric in (Zliobaite, 2015) (when interpreting y as the protected variable). Furthermore, in the context of classification, it can be connected to the worst group accuracy (Sagawa et al., 2020a;b). In fact, our definition (3) is also related to the ont-of-distribution test loss; assuming [ [ w))² = (+))) 1 and [[ [ w))] B (7) = 0 for
simplicity and considering a quadratic loss, we have
vl) -=()) 2 22 2/ c(0)3. Ea v (T0
We focus on the setting where the labels gi depend only on Iy, i.e. g: = (2+) = (x:) for some (not necessarily de- terministic) function f² Hence, y is independent from gi. after conditioning on 2;. We highlight that the independence between I/ and g; is conditional on I,, and that the covari- ance between y4 and T; is in general non-zero. We refer to y; as the spurious feature of the i-th sample, and to I; as its core feature. As an example, I, may represent the main object in an image and yi the (not necessarily independent)
(4) This implies that increase in C(²) hurts the performance of the model when core and spurious features are sam- pled independently (and, thus, the model is tested out-of- distribution). The proof of (4) is in Appendix E.
'In general, existence and uniqueness of depend on the choice of the model /00 2). the loss function é and the regularization term X. For the purposes of our work, we will precisely define 0 for linear regression (Section 4) and for random features (Section 6).
3

---

Spurious Correlations in High Dimensional Regression
4. Precise Analysis for Linear Regression To study C()) as defined in (3), we focus on a high- dimensional lineur regression model, i.e.
Synthetic
Calor-MNIST
0.8
c ((0), n 1000
((8,,(A), 2008
C(êLn(A)), n 1000
f0, 2) = =
(5)
0.4
c(),a(A)) 2000
where A Rdd, The data also follows linear model, i.e.
02
0.0
gi 2. 0" + x.
10 10'
10" 10"
10"
10"
where 0* R2dd 0- R and e; is label noise. The second equality in (6) implies that 0 = 10; T ,O]]_ where or, O₂ E R$ and each entry of Oa is O. We set ||01|| = |16 = and let the 6,-8 be i.i.d. (and independent from the s,, mean-0, sub-Gaussian, with variance o² > O.
Figure 2. Test loss [(*Lx(A)) (black) and spurious correlations (())x(A) (red) as a function of the regularization term for two values of the number of samples n. Left: synthetic Gaussian dataset, with = 400 (additional details Appendix F); right: binary Color-MNIST dataset with correlation v1 a² 0.25 between color and digit (see Figure 1).
We introduce the shorthands Z = [2T ........ ,...,,27]] I E Rax2d G [.t,... |n] )T IR"", and 3 (1, ........ Gp]
R to indicate the data matrix, the labels, and the noise vector respectively. Then, using quadratic loss, (1) reads
In words, fLK (0L (0): does not learn any spurious corre- lation between the spurious feature y and the label g. This is also clear from Figure where we report in red the value of C(ôrR (A)), which approaches 0 as À becomes small.
θLR(A) (A) = arg ming L 20 - G 11013).
(7)
The idea of the argument is to write explicitly the solution
which admits the unique solution
O2R(0) - (z- Z - 0- +++ 2z _T (11)
(A) = (zT Z + +nI) -1 ZTG,
(8)
where in the second step we separate the ground truth 0* (which does not capture any dependence on y) from a term only depending on the label noise, which is mean-O and independent from y. This directly gives (9). Then, the bound in (10) is obtained via standard concentration results Amin (Z" Z). The details in Appendix B.
for X > 0 and, if TT Z is invertible, also for À ==0 O.
Assumption 4.1 (Data distribution). {zi) are i.i.d.
samples from the multivariate, mean-O, Gaussian distribu- tion Pxy, such that its covariance Σ == E [22" E 2dx2d
invertible, with Amax (Σ) = O (1). Amin (Σ) Q(1). and tr())= 2d.
General case with regularization (A > 0). Setting a regularizer À >> 0 often reduces the test loss, see the black curve in Figure 2. However, it also leads to non-trivial spurious correlations, and our main result provides a non- asymptotic characterization of this phenomenon.
This requirement could be relaxed to having sub-Gaussian data. We focus on the Gaussian case for simplicity, deferring the discussion on the generalization Appendix B.2.
Theorem 4.3. Let Assumption 4.1 hold, n = ((d) and C(O)R(A)) be the amount of spurious correlations learned by the model FLR fiR(OLR(A),) -) for X > 0. Denote by Ps 2ddx2 the projector on the last d elements of the canonical basis in R22d, and set
Warm-up: regularization (A 0). Our first result concerns the amount of spurious correlations learned in the un-regularized setting.
Proposition 4.2. Let À = 0 and TT Z E Rd2xxdd be invert- ible?. Let ((LL(())) be the amount of spurious correlations learned by the model fiR FiR(OLR(0), Then, we have that
PyE0", where T == (()) is implicitly defined as the unique positive solution of
(12)
Ee [=]C((L(()))
Furthermore, if Assumption 4.1 holds and n w(d),
1 1 A 1 --t ((E((TT1)
(13)
(C((LR = (log d/vd),
(10)
Then, for every t E 10,1/2).
with probability at least 2 exp((cloog' d) over Z and
E, where is an absolute constant.
Pz,8 ((((LR(()) (²) 2t)= Cdexp (-dt+/C).
Under Assumption 4.1, this holds with probability for n
2d.
where C is an absolute constant.

---

Spurious Correlations in High Dimensional Regression
In words, Theorem 4.3 guarantees that (((OL(A))
if the digit on the image is (0); and the spurious feature is y = +1 (-1) if the color is red (blue). If the digits and the colors have correlation of a, then Enz = Eny 1 and Eny = Σ = a. Thus, S. = 1 - a². which becomes 0 if |a|| = 1 (full correlation), and it is maximized in the setting of independence between colors and parity (a- = 0).
(A)l o(1) with high probability (e.g., setting & = d d-1//). Thus, for large d, n, we can theoretically analyze C(fLR(A)) via the deterministic quantity (A), which, as highlighted by (12), depends on 0", the covariance of the data >. and the regularization À via the parameter T (A) in- troduced in (13). We further analyze the object C (A) in
At this point, leveraging the decomposition of Σ in (14) and the Schur complement in (15), we provide the following bounds on C² (A), which are proved in Appendix B.
Section 5 that immediately follows.
Note that, since ÖLR (A) is given by (8), when À >>0 0 it can- not be decomposed as 0* + (Z 2) z" & (as in the proof of Proposition 4.2 for À = 0). Thus, we rely on the non- asymptotic characterization of (A) recently provided by Han & Xu (2023). In particular, their analysis focuses on the proportional regime n = (d) (as opposed to the regime w(d), considered in (10)), and it allows provide con- centration bounds on a certain family of low-dimensional functions of (A), which includes C. as defined in (3). The details are in Appendix B.
Proposition 5.1. Let (2) and S be defined in (12) and (15), respectively. Then,
Amax (2))
|C² S min |Enyrllop x(2)
(17)
+(A) Var(g) - 0² Amax (Eyy) - Amiu (5
Amin (S v Amin (Egz)
We discuss the three upper bounds in (17) below.
5. Roles of Regularization and Simplicity Bias We now interpret (A), which characterizes the spurious correlations via Theorem 4.3, in terms of the data covariance Σ and the regularization A. To do so, express E as
(i): (C=(A)] S || E lopp" The off-diagonal blocks Eyer Elyx' J and Exy S describe the correlation between y and x. In the limit case || lop = 0, we have that and y are uncorrelated and, therefore, (²)) = 0, as there is no spurious correlation that the model can learn.
Egpor Σ Eggrr
Exyy Enyg
Σ
(14)
(ii): [C=( S Amax (E)²/T(M) /T(A). From (13), one obtains that 7(A) + 00 as x + 00. Thus, the bound implies that (*) approaches O as À grows large. This captures the intuition that, when the regularization A is large, the minimization in (7) is biased towards solutions with small norm and, therefore, the output of the model small, which drives to 0 the spurious correlations as defined in (3). The behavior is confirmed by Figure 2: (((OR(A)) is decreasing for large values of X and it eventually vanishes; at the same time, large values of X make the output of the model small, which in turn increases the test loss [( (A)).
where the block Exx = EanPx | E Rdd (Eny Ey-Py [wvT] E Rdxd) denotes the covariance of the
core (spurious) feature sampled from its marginal dis- tribution. The off-diagonal blocks are Eny = -
EiTT, wy IT [xyT] E Raxd, Let us denote by
Sh = Eny Enyz I- Eaay
(15)
the Schur complement of E with respect to the top-left d x d block Ers. In our setting, Sh offers helpful statistical interpretation. In fact, for multivariate Gaussian data, it corresponds to the conditional covariance of y given x, i.e.,
(iii): The third bound in (17) can be rewritten as
I=2 Amin (Eez) VVar(g)- - o² S TA) Amax (Egy) Amia ($
5 = Cov (y/x = T)
Amin (S²)
= Eyla== (H (y-Eyle=aa Eyle=m w)) (u Eylos (v) J.
(16)
(18)
where we have isolated on the LHS the terms depending on the covariance of the core feature x (v/ /mmin (Erw)) )) and the scaling of the labels (vVar(g) o²). We now dis- cuss the dependence of the RHS of (18) w.r.t. (a) r(A), (b) Amin (SF). and (c) Amax (Eny). As for (a), we note that (A)) approaches 0 for small values of A. In fact, the RHS of (13) is smaller or equal to 2d/r2 thus, if we consider 2d < n, we also get S X - 2d/n) which implies TA) + 0 as X + O. This is in agreement with Proposi- tion 4.2, which handles the case without regularization, and also with the numerical experiments of Figure 2. As for
Therefore, the spectrum of S describes the degree of depen- dence between y and x: on the one hand, if its eigenvalues small, the feature y is close to be determined by the knowledge of the feature z (i.e., y is highly correlated with r)); on the other hand, if its eigenvalues are large, the two features tend to be independent.
As an intuitive example, let us interpret classification for
the binary Color-MNIST dataset (see Figure 1) as a 2- dimensional problem: the core feature is x = +1 (-1)
5

---

Spurious Correlations in High Dimensional Regression
Synthetlc
Synthetic
CIFAR- 10 (spurious background)
((0
((1rr(11)
(00r(A))
c(0,a(A)
((6xx(A))
0.4
((0)r(A))
0.2
0.0
0.0
0.2
0.1
0.2
0.3
Amax Amax(Epp)
Arou (Bny) (yyy
Increasing level of whitening
Figure 3. Test loss [(]) (black) and spurious correla- tions ((OLR/R((A) (red) as a function of Amax (Eny) (left) and Amin (5%) (right) on synthetic Gaussian dataset, for both linear regression and random features, with À = 1 (additional details in Appendix F).
Figure 4. Test loss L(01 (black) and spurious correlations (( (red) as function of Xmax (Nig)/ / tr(2gg)) on a CIFAR- 10 dataset for different levels of whitening (details on the whitening process in Appendix
F). We restrict to the classes "boat" and "truck" (n = 10000) and consider both linear regression and random features, with À = 1.
(b), we note that the bound is decreasing with Amin (5 This is in agreement with the earlier discussion on how the spectrum of the Schur complement S measures the degree of independence between the spurious feature y and the core feature x. Finally, as for (c), we note that the bound is increasing with Amaa (Egy), which is connected below to the simplicity of the spurious feature y. The increasing (decreasing) trend of (A) w.r.t. Amax (Eny) (Amin (S²) clearly displayed in Figure for Gaussian data.
ct al. (2021); Qiu et al. (2024), which focus on how spu- rious correlations evolve during training. On the other hand, in linear regression, solving the gradient flow equa- tion di V Lx (0)dt, where (x) is defined as the argument of the arg min in (1), gives
((t) = (1 - exp (-2 (X X/n + A1) t)) 0.
exp
(19)
Thus, the components of i aligned with the top eigen-spaces of X X converge earlier than the others. Hence, from a dynamical point of view, if X "X ~ nE, our results suggest that spurious features are learned faster the easier they are.
The connection between Xmaa (Eyg) and the simplicity bias of ERM can be illustrated via our initial image recognition example. The (spurious) background feature is intuitively an easy pattern to learn from the model: the pixels corre- sponding to the spurious feature behave consistently across the training data. This in turn skews the spectrum of Enyy which has few dominant directions with eigenvalues much larger than the others. Note that this interpretation is similar to the modelldependdent definition of simplicity in (Morwani et al., 2023). An empirical verification is provided in Figure 4, where we consider the CIFAR-10 10 dataset, restricted to the "boat" and "truck" classes. Before training regression model, we whiten up some level the background feature (as defined in Figure 1) to make it harder to learn, see the right side of Figure 4. Then, for different levels of whiten- ing, we report (A)) as a function of Amax (Egy). We normalize Amax (Eny) by the trace tr tr(En)) to exclude the size of the pattern from our experiment*. The red curve shows an increasing trend analogous to that displayed in Figure 3 for Gaussian data: small values of Amax (Zig) correspond to significant whitening and, hence, small spurious correlations, as predicted by Proposition 5.
Trade-off between L(LLR (A)) and C()LR(A)). Figure 2 shows that there is an interval of values for the regularization (A ~ 10-1) where the test loss [(O (A)) is decreasing in X, while the spurious correlations C(f)R(A)) are increasing. This evidence suggests a natural trade-off between these two quantities, mediated by A. To theoretically capture such trade-off, we first provide a aoy-tsympi concentration bound for L(OLR (A)).
Proposition 5.2. Let Assumption 4.1 hold, O(d)
and ((OLR())) be the in-distribution test loss of the model fLR (RL (A), for x >>0 O. Set
2 (² 0² + +AA2
[ + T(A)T) x//
(20)
1 (((E+T(A))) PEP) -E3²)
where T T(X) is defined via (13). Then, for every E 10,1
Pz, - c -
- Cdeep (-dt"/O)
We remark that our results concern the parameter Ô as de- fined in (I), which can be interpreted as the convergence point of an optimization algorithm such as gradient descent. This perspective differs from the prior work of Pezeshki
where C is an absolute constant.
In words, Proposition 5.2 guarantees that (C((LR(A)) C (A)) = o(1) with high probability. Its proof is an adapta- tion of Theorem 3.1 in (Han & Xu, 2023), and the details are in Appendix B.
'If y has O-mean, then Elyy| = tr(E.w), i.e., the trace cap- tures the size the pattern.
6

---

Spurious Correlations in High Dimensional Regression
Armed with the non-asymptotic bounds of Theorem 4.3 and Proposition 5.2, we characterize the trade-off between C(OIR(A) and C(ŌLR(A)) by studying the monotonicity of (*) and (A).
width 300
Synthetic p = 20000
1.0
116w(A CANNIST
216r/A0) tanh
0.8
(16,991) CIFAR 10
0.6
c16w//t) CANNIST
clor/(A)) tanh
C10w CIFAR-10
(log(Al), &
Proposition 5.3. Let (X) and (X) be defined as in (12) and (20). Then, 2d <. n. we have that (X) is 2d
0.4
02
monotonically decreasing in a right neighborhood of X O, and there exists x > O such that (x) is monotonically increasing for X 2 Xc. Furthermore, if E-ux = I, then (A) is non-negative and there exists de such that (2) is monotonically increasing for X S dc. Finally, as long as
0.0
10"
10'
10"
10"
A
Figure 5. Test loss ((()N)/=(A)) (black) and spurious correlations ((BNN/R((A (red) as function of X. Left: 2-layer fully connected ReLU network, trained on the binary color(C)-MNIST and CIFAR- 10 (boats and trucks). Right: RF model with tanh and Φ1 h + 0.1 hg activation. Implementation details are in Appendix F.
Amin (E) min (1, 2xmmxx 2Xmaax(E)/00 (E)/o²
2d. n
1, 4 (11 (Amax (E)/ Xmmnn (2) + 1)²
(21)
6. Role of Over-parameetriration
we have that de 2 Ac-
Our analysis has so far focused on linear regression, high- lighting the role of data covariance and regularization. How- ever, moving to complex predictive models, such as neural networks, may lead to differences in the degree to which spurious correlations are learned. As an example, in the left panel of Figure 5, we train an over- over-parameterized two-layer neural network on the binary Color-MNIST and CIFAR-10 datasets, for different values of the regularizer X. While for high values of X the results are qualitatively similar to the ones in Figure 2, a striking difference is that spurious correlations remain significant even when there is little to no regularization (i.e., X Rz 0), in sharp contrast with Propo- sition 4.2. We also note that the phenomenon is in line with previous empirical work (Sagawa et 2020a).
In words, Proposition 5.3 shows that (A) grows with À at least until the regularization equals a value Ae. For example, in Figure 2, A ~ 1 for a Gaussian data and A ~ 10 for COlOT-MNIST. Furthermore, in this interval, (2) is initially decreasing and then increasing as À 2 Ac. These trends in turn imply that the optimal value X2 that minimizes the test loss is s.t. X E (0, Ac] an interval where the spurious correlations are strictly positive and increasing.
The proof of Proposition 5.3 (whose details are in Appendix B) relies on the monotonicity of (A)) in X, and the last state- ment follows from showing that 7 rAc)) 2 Amiu (S)) 2 Amin (Σ)= 2 T()c). The upper bound on 2d/n in (21) is required to prove that Amin (Σ)= 2 r(xc) and, due As- sumption 4.1, is implied by taking n = w(d). We note that the latter scaling holds in standard datasets, e.g., MNIST (n = 6 1 2d R 2 - 103 when considering the 3 color channels) and CI (n = 5 10 2d R 3 103).
We bridge the gap between linear regression and over- parameterized models by focusing on random features:
far 2) = TV
(22)
where V is a x 2d matrix s.t. Vi, PLid. N (O, 1/(2d), and & is an activation applied component-wise The number of parameters of this model is p. as V is fixed random matrix and I E RD contains trainable parameters. The scaling of input data (tr(E) 2d) and the variance of the entries of V guarantee that the pre-activations of the model (i.e., the entries of the vector Vz E IR) are of constant order.
We conclude the section by noting that learning spurious cor- relations can be beneficial to minimize the (in-disributiin) test loss. In fact, the spurious features in y are effectively correlated with the labels, due to their correlation with the core feature x, and hence they can be helpful at prediction time. This phenomenon is numerically supported by Figures 3 and 4, where for a fixed value of X, easier spurious fea- tures (or higher correlations) generate both higher values of C(ORR( (A)) and lower values of L(0r (A)). In words, while
We consider the ERM in (1) with a quadratic loss
a blue background cannot strictly predict the label "boat", it is useful feature in prediction long as the boats in the test data tend to have a blue background.
ŌRF(A) = arg mine
L
1 11000 n
+ -100-G(+++11000 +110133. (23)
The same conclusion does not hold for the out-of- distribution test loss, where the features x and are sam- pled independently: the lower bound in (4) increases with C. Figure 6 in Appendix E provides an additional numerical validation of this statement.
E RTx,, When À = 0, if T is invertible, the minimization above does not necessarily have a unique solution. In that case, we set (R) to be the solution obtained via gradient descent
where we set 1 =
7

---

Spurious Correlations in High Dimensional Regression
with 0 initialization, which corresponds the min-norm interpolator (see equation (33) in (Bartlett al., 2021))- Then', we can write, for À 2 0,
with probability at least Cvalogg d/ C'log d/d where the effective regularization Ā
is given by
2 2d pîn
(A) = Φ (D-D + -nA) G.
(24)
= +
pip x
(26)
Assumption 6.1 (Activation functionn, The activation Φ : IR IR is non-linear, odd, Lipschitz function, such that
and j1² = Euze ph with pk denoting the k-th Hermite coefficient of Φ.
its first Hermite coefficient μ1 # O.
In words, Theorem 6.4 shows that the over parepparaeterizee RF model, when evaluated on a new test sample (not nec- essarily from the same distribution as the input data), is asymptotically equivalent to linear regression with regular- ization À given by (26). In particular, even in the ridgeless case (A = 0), the RF model is equivalent to linear regression with strictly positive regularization. Thus, we expect the presence of spurious correlations, just like in Figure 5, since C (((R=(0)) approaches (²) with Ā > 0 Notably, the effective regularization À depends on the activation & via its Hermite coefficients, and it increases with the ratio z²² /v².
This choice is motivated by theoretical convenience and is similar to the one considered in (Hu & Lu, 2023). We believe that our result can be extended to more gen- eral setting, as the ones in (Mei & Montanari, 2022; Mei et al., 2022), with a more involved analysis. We refer to (O' Donnell, 2014) for background on Hermite coefficients.
Assumption 6.2 ODeerparammeteriaaion)) We let p grow s.t. p = w (n log" n) and logp = m(logn).
This requires the width of the model (and, hence, its number of parameters) to grow faster (by at least poly-log factor) than the number of training samples.
We point out some differences between Theorem 6.4 and earlier work on the equivalence of random features with regularized linear regression (Goldt et al., 2020; 2022; Hu & Lu, 2023; Montanari & Saeed, 2022). First, as mentioned in Section 2, existing results prove equivalence of training and test loss, which does not imply either the equivalence of the covariance in (3) nor the point-wise guarantce of (25). Second, existing results focus on the regime where p and n are proportional, while Assumption 6.2 requires p == w (n log" n). This reflects on the third difference which is in the proof technique: existing results use Lindeberg method, while our strategy (summarized below) relies on concentration tools.
Finally, our requirements the data are less restrictive than those coming from Assumption 4.1.
Assumption 6.3 (Data distribution, less restrictive).
{=) are n i.i.d. samples from a mean-0, Lipschitz con- centrated distribution Pxy, with covariance ) s.t. tr(2:) = 2d. Furthermore, the labels 9r are i.i.d. uub-Gaussian ran- dom variables.
Note that the labels Is are not required to follow a linear model 9 =, 10*00==, +e.. The Lipschitz concentration property (see Appendix A for details) corresponds to data having well-behaved tails, it includes the distributions considered in Assumption 4. as well as the uniform distribution on the sphere or the hypercube (Vershynin, 2018), and it is common requirement in the related literature (Nguyen et al., 2021; Bubeck & Sellke, 2021; Bombari et al., 2022).
Proof sketch:
The proof builds on core steps.
Step 1: We show that, with high probability,
ΦΦ
ZZ
1121
(
Amin ( T)
Theorem 6.4. Let Assumptions 6.1, 6.2, and 6.3 hold, (d)), and E Rd be sampled from a distribution satisfying Assumption 6.3, not necessarily with the same covariance as Pxv, independent from everything else. Let fur (A), 2) be the RF model defined in (22) with BRr(X) (X) given by (24), and fix (BLRx()) 2) be the linear regression model defined in (5) with θLR ()) given by (8). Then, for X 2
p
11
2d
lpp
p
which a consequence of the concentration of Φ T to its expectation with respect to V. then expressed in terms of the Hermite coefficients of di (Lemmas C.2 and C.3).
Step 2: In Lemma C.5 we upper bound the term | [ (V))))V (where set 2)-) = ((-)-m(())) which is then used to show that
(Rr( (A), 2)= - fLR f(R(OLR(A)))2)
1/4 log d
log 3/2 log
(25)
[oVV)) Tu - 2i V ORF = o(1),
= 11/1
o(),
di/8
with high probability, due to Markov inequality. This means that the non- non-linear component of <(V2) has a negligible effect on the output (see (149) in Lemma C.7).
T is proved to be invertible with high probability in Lemma C.3.
8

---

Spurious Correlations in High Dimensional Regression
Step 3: Using a similar intuition, we use matrix Bernstein inequality (Lemma C.6) show that II( Pr ZVT) V is small with high probability, so that
Acknovledgements
Marco Mondelli is funded by the European Union (ERC, INF2, project number 101161364). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. Simone Bombari is supported by a Google PhD fellowship. The authors would like to thank GuanWen Qiu for helpful discussions.
uiz V (T - VIV (Φ + +nAr) G =1))
i.e., the non-linear component of TT in (24) is also negligi- ble (see (145)).
Finally, by combining Step 2 and Step 3 with standard con- centration arguments, we conclude that
Impact Statement
o(V2) ORF- - 12.0= x TT
(44 T + +nd) G = o(1),
This paper presents work whose goal is to advance the field of machine learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
2d
and the thesis follows from Step I and Woodbury matrix identity for the inverse.
Ll
The right panel of Figure 5 presents the test loss ((fRF(X))
References
(in black) and the spurious correlations C(OR=(A)) (A)) (in red)
Ahmed, F., Bengio, Y., van Seijen, H., and Courville, A. Sys- tematic generalisation with group invariant predictions. International Conference on Learning Representations, 2021.
for two activation functions: tanh and Φ1 h2 + 0.1 where h and ha denote the first and third Hermite poly- nomials, respectively. Notice that this gives /²²/m² ~ 0.1 for tanh. /² /22 ~ 0.01 for Φ1, and we take d = 400 and 2000. As expected, C(ORF(O)) > 0 for the tanh activation function, since Ā ~ 0.05 (which matches the corresponding value in Figure 2). On the other hand, (0) ~ O for the activation Φ1, since Ā ~ 0.005. As À grows, (A)) goes to O faster for the tanh activation function (which has higher )), as predicted by the second upper bound in Proposition 5.1. These results match the qualitative behavior of the 2-layer neural network trained on the Color-MNIST dataset (left panel).
Arjovsky, M., Bottou, L., Gulrajani. I., and Lopez- Paz, D. Invariant risk minimization. arXiv preprint arXiv: 1907.02893, 2020.
Ba, J., Erdogdu, M. A., Suzuki, T., Wang, Z., Wu, D., and Yang, G. High-dimensional asymptotics of feature learn- ing: How one gradient step improves the representation. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Bartlett, L.,, Montanari, A., and Rakhlin, A. Deep learning: a statistical viewpoint. Acta numerica, 30:87-201, 2021.
7. Conclusions
Belkin, M., Hsu, D., Ma, S., and Mandal, S. Reconcil- ing modern machine- practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences, 116(32):15849 15854,, 2019.
Our work provides a rigorous study of spurious correlations in high-dimennn gigh-dimensional regression models, with the purpose of connecting the statistical foundation of this phenomenon with its practical intuition. Specifically, we translate the problem into characterizing the deterministic object C* which allows to quantitatively capture the roles of ridge regularization, data covariance and over- parameterizzaton.
Bombari, S. and Mondelli, M. Privacy for free in the over- parameterized regime, arXiv preprint arXiv:2410. 14787, 2024.
An interesting future direction is to employ our principled approach to design algorithms that go beyond ERM to miti- gate spurious correlations. In that regard, let us mention the usage of multiple models with different ridge regularization or early stopping (connected to ridge penalties, see (Raskutti et al., 2014)), in order to generate additional supervision. Here, having quantitative control on which features (core or spurious) are learned by which model would allow to op- timally use the extra labels (c.g.. for weightttting minority groups, as in (Liu et al., 2021)).
Bombari, S., Amani, M. H., and Mondelli, M. Memo- rization and optimization in deep neural networks with minimum wverparrameterization. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Bombari, S., Kiyani, S., and Mondelli, M. Beyond the universal law of robustness: Sharper laws for random features and neural tangent kernels. In Proceedings of the 40th International Conference on Machine Learning, 2023.
9

---

Spurious Correlations in High Dimensional Regression
Bubeck, S. and Sellke, M. A universal law of robustness via isoperimetry. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Hastie, T. J., Montanari, A., Rosset, S., and Tibshirani, J. Surprises in high-dimensional ridgeless least squares interpolation. Annals of statistics, 50 2:949-986, 2022.
Chang, C., Adam, G., and Goldenberg, A. Towards robust classification model by counterfactual and invariant data generation. In JEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2021a.
Hermann, K. and Lampinen, A. What shapes feature repre- sentations? Exploring datasets, architectures, and training, In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Chang, X., Li, Y., Oymak, S., and Thrampoulidis, C. Prov- able benefits of overparameterization in model compres- sion: From double descent to pruning neural networks. In Proceedings of the AAAI Conference on Artificial In- telligence, volume 35, pp. 6974 6983, 2021b.
Hermann, K., Mobahi, H., FEI., T., and Mozer, M. C. On the foundations of shortcut learning. In The Twelfth Inter- national Conference on Learning Representations, 2024.
Hu, H. and Y. M. Universality laws for high- high-dimensional learning with random features. IEEE Trunsactions on Information Theory, 69(3):1932-1964) 2023.
Cheng, C. and Montanari, A. Dimension free ridge regres- sion. The Annals of Statistics, 52(6):2879- 2912, 2024. doi: 10.1214/24AAS22449
Izmailov, P., Kirichenko, P., Gruver, N., and Wilson, A. G. On feature learning in the presence of spurious correla- tions. In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K. (eds.), Advances in Neural Information Processing Systems, 2022.
Damian, A., Lee, J., and Soltanolkotabi, M. Neural net- works can learn representations with gradient descent. In Conference on Learning T'heory (COLT), 2022.
Kalimeris, D., Kaplun, G., Nakkiran, P., Edelman, B., Yang, T., Barak, B., and Zhang, H. Sgd on neural networks learns functions of increasing complexity, Advances in Neural Information Processing Systems, 2019.
Dohmatob, E. and Bietti, A. On the (non-) robustness of two-layer neural networks in different learning regimes. arXiv preprini arXiv:2203.I /864, 2022.
Geirhos, R., Rubisch, P., Michaelis, C., Bethge, M., Wich- mann, F. A., and Brendel, W. Imagenet-trained CNNs are biased towards texture; increasing shape bias improves accuracy and robustness. In International Conference on Learning Representations (ICLR), 2019.
Kirichenko, P., Izmailov, P., and Wilson, A. G. Last layer re-training is sufficient for robustness to spurious corre- lations. In The Eleventh International Conference on Learning Representations, 2023.
Lee, D., Moniri, B., Huang, X.. Dobriban, E., and Has- sani, H. Demystifying disagreement-on-theer dimensions. Proceedings of the 40th International Conference on Machine Learning, 2023.
Geirhos, R., Jacobsen, J.-H., Michaelis, C., Zemel, R., Bren- del, W., Bethge, M., and Wichmann, F. A. Shorteut learn- ing in deep neural networks. Nature Machine Intelligence, 2(1 ((11):665-67, 2020. ISSN 2522-5839.
in high
Liu, E. Z., Haghgoo, B., Chen, A. S., Raghunathan, A., Koh, P. W., Sagawa, S., Liang, P., and Finn, C. Just train twice: Improving group robustness without training group information. In Proceedings of the 38th International Conference on Machine Learning, 2021.
Goldt, S., Mézard, M., Krzakala, F., and Zdeborová, L. Modeling the influence of data structure on learning in neural networks: The hidden manifold model. Physical Review X, 10(4):041044, 2020.
Goldt, S., Loureiro, B., Reeves, G., Krzakala, F., Mézard, M., and Zdeborová, L. The gaussian equivalence of gen- erative models for learning with shallow neural networks. In Mathematical and Scientific Machine Learning, pp- 426-471. PMLR, 2022.
Liu, S., Zhang, X., Sekhar, N., Wu, Y., Singhal, P., and Fernandez- Granda,, C. Avoiding spurious correlations via logit correction. In The Eleventh International Confer- ence on Learning Representations, 2023.
Loureiro, B., Gerbelot, C., Cui, H., Goldt, S., Krzakala, F., Mezard, M., and Zdeborová, L. Learning curves of generic features maps for realistic datasets with teacher- student model. In Advances in Neural Information Pro- cessing Systems, 2021.
Han, Q. and Xu, X. The distribution of ridgeless least squares interpolators. arXiv preprint arXiv:2307.0204. 2023.
Hassani, H. and Javanmard, A. The curse of over- parametrization in adversarial training: Precise analysis of robust generalization for random features regression. The Annals of Statistics, 52(2):411 465, 2024.
Mallinar, N. R., Zane, A., Frei, S., and Yu, B. Minimum- norm interpolation under covariate shift. In Forty-first International Conference on Machine Learning, 2024.
10

---

Spurious Correlations in High Dimensional Regression
Mei, S. and Montanari, A. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75(4):667-766, 2022.
Rahaman, N., Baratin, A., Arpit, D., Draxler, F., Lin, M., Hamprecht, F., Bengio, Y., and Courville, A. On the spec- tral bias of neural networks. In Proceedings of the 36th International Conference on Machine Learning, 2019.
Mei, S., Misiakiewicz, T., and Montanari, A. Generalization error of random feature and kernel methods: Hypercon- tractivity and kernel matrix concentration. Applied and Computational Harmonic Analysis, 59:3-84, 2022. ISSN 1063-5203. Special Issue Harmonic Analysis and Machine Learning.
Rahimi, and Recht, B. Random features for large-scate kernel machines. In Advances in Neural Information Processing Systems, 2007.
Raskutti, G., Wainwright, M. and Yu, B. Early stop- ping and non non-parametric regression: an optimal data- dependent stopping rule. The Journal of Machine Learn- ing Research, 15(1):335-366, 2014.
Moayeri, M., Singla, S., and Feizi, S. Hard imagenet: Seg- mentations for objects with strong spurious cues. In Ad- vances Neural Information Processing Systems, 2022.
Sagawa, S., Koh, W., Hashimoto, T. B., and Liang, P. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case gen- eralization. In International Conference Learning Representations, 2020a.
Moniri, B., Lee, D., Hassani, H., and Dobriban, A theory of non-linear feature learning with gradient step in two-layer neural networks. In International Conference on Machine Learning (ICMI), 2024.
Sagawa, S., Raghunathan, A., Koh, P. W., and Liang, An investigation of why overparameterization exacerbates spurious correlations. In Proceedings of the 37th Inter- national Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 8346- 8356, 2020b.
Montanari, A. and Saeed, B. N. Universality of empirical risk minimization. In Conference on Learning Theory, pp. 4310 4312. PMLR, 2022.
Montanari, A., Ruan, F,, Sohn, Y., and Yan, J. The gener- alization eπrоr of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the over- parametrized regime. arXiv preprint arXiv:1911.01544, 2019.
Seo, S., Lee, J.-Y., and Han, B. cntemmattoo-thhorette bias reduction via causal view of spurious correlation. AAAI Conference on Artificial Intelligence, 2022.
Shah, H., Tamuly, K., Raghunathan, A., Jain, P., and Netra- palli, P. The pitfalls of simplicity bias in neural networks. In Advances in Neural Information Processing Systems, 2020.
Morwani, D., jatin batra, Jain, P., and Netrapalli, Sim- plicity bias in 1-hidden layer neural networks. In Thirty- seventh Conference on Neural Information Processing Systems, 2023.
Singla, S. and Feizi, S. Salient imagenet:
How discover spurious features in deep learning? In International Conference on Learning Representations, 2022.
Nguyen, Q., Mondelli, M., and Montufar, G. Tight bounds on the smallest eigenvalue of the neural tangent kernel for deep ReLU networks. In International Conference on Machine Learning (ICMI., 2021.
Song, Y., Bhattacharya, S., and Sur, P. Generalization error of min-norm interpolators transfer learning. arXiv preprint arXiv:2406. 13944, 2024.
O'Donnell, R. Analysis of Boolean Functions. Cambridge University Press, 2014.
Thrampoulidis, C., Oymak, S., and Hassibi, B. Regularized linear regression: A precise analysis of the estimation error. In Conference on Learning Theory, pp. 1683-1709. PMLR, 2015.
Pezeshki, M., Kaba, S.-O., Bengio, Y., Courville, A., Pre- cup, D., and Lajoie, G. Gradient starvation: A learning proclivity in neural networks. In Advances in Neural Information Processing Systems, 2021.
Tiwari, R. and Shenoy, P. Overcoming simplicity bias in deep networks using a feature sieve. In Proceedings of the 40th International Conference on Machine Learning, 2023.
Plumb, G., Ribeiro, M. T., and Talwalkar, A. Finding and fixing spurious patterns with explanations. Transactions Machine Learning Research, 2022.
Qiu, G., Kuang, D., and Goel, S. Complexity matters: Dynamics of feature learning in the presence of spurious correlations. In International Conference on Machine Learning (ICML), 2024.
Tripuraneni. N., Adlam, B., and Pennington, J. Overpa- rameterization improves robustness to covariate shift in high dimensions. Advances in Neural Information Processing Systems, 2021.

---

Spurious Correlations in High Dimensional Regression
Veitch, V., D' A'mour, A., Yadlowsky, S., and Eisenstein, J. Counterfactual invariance to spurious correlations in text classification. In Advances in Neural Information Processing Systems, 2021.
Vershynin, R. Introduction the non-asymptotic analysis of random matrices, pp. 210-268. Cambridge University Press, 2012.
Vershynin, R. High-dimensional probability: An introduc- tion with applications in data science. Cambridge univer- sity press, 2018.
Xiao, K. Y., Engstrom, L., Ilyas, A., and Madry, A. Noise or signal: The role of image backgrounds in object recog- nition. In International Conference on Learning Repre- sentations (ICLR), 2021.
Yang, F., Zhang, H. R., Wu, S., Ré, C., and Su, W. Precise high-dimensional asymptoties for quantifying heteroge- neous transfers. arXiv preprint arXiv:2010.1 11500, 2023.
Ye, W., Zheng, G., Cao, X., Ma, Y., and Zhang, A. Spurious correlations in machine learning: A survey, arXiv preprint arXiv:2402.12715, 2024.
Zhang, J., Menon, A. K., Veit, A., Bhojanapalli, S., Kumar, S., and Sra, S. Coping with label shift via distribution- ally robust optimisation. In International Conference on Learning Representations, 2021.
Zhou, C., Ma, X., Michel, P., and Neubig, G. Examining and combating spurious features under distribution shift. In International Conference on Machine Learning (ICML), 2021.
Zliobaite, I. On the relation between accuracy and faimess in binary classification. In 2nd ICML Workshop on Fairness, Accountability, and Transparency in Machine Learning (FATML), 2015.
12

---

Spurious Correlations in High Dimensional Regression
A. Additional Notation
We define a sub- Gaussian random variable according to Proposition 2.5.2 in (Vershynin, 2018), and || 1y == inf >
E [exp(X22 / I 2}. X E R is random vector, then || y02 [ || XII tha When we state that random
variable or vector X is sub-Gaussian, we implicitly mean || II = O (1), L.e. its sub-Gaussian norm does not increase with the scalings of the problem.
We say that X respects the Lipschitz concentration property if, for all 1-Lipschitz continuous functions y; have [xxp E [x))) O (1). Notice that then, if X is Lipschitz concentrated, then X [[ is sub-Gaussian.
Given two symmetric matrices A, B, we use the notation A = B if A B is p.s.d. Notice that if A = B > O, then we also have B-1 ž A-1, We denote with || the Frobenius norm of A, and with ker(A) its kernel space. If A is square matrix, we use the notation diag(A) to denote a matrix identical to on the diagonal, and 0 everywhere else. We let B denote the Hadamard (component-wer wise) product between matrices, and A denote A A o.... A, where appears h times.
B. Proofs for Linear Regression Proof of Proposition 4.2. Note that
(LR(O) = -0 (zT GTG.
(27)
Since have gi 2 00 + es (27) reads
(L) 2z 2 (20' E) 0" + 1z 7TE.
(28)
Then, we can plug this result in the definition of C(0) in (3) to obtain
Ee [C(ALR
= Eg [Cov I 9x= (FIR (fIR(0), 1ēT, .. 12 .9)]
Eg Cov(=T "T] JTTTTP Bxxx ( ,y (0RR(0), x T0:)) 02)
Egg
(ooy ExPx (i 0 t (2 2) z ETE,2 TT
(29)
Poy. PmPy (a 0% TT,)
0,
where in the second line we used that & is independent from everything else, in fourth line we used E [8] and that independent from all the other random variables, and the last step holds since is independent from æ.
For the second part of the statement we have that
C(LLR(0)) = Cov TTT.TTJJJPPPP..
Z E 0% 2 (z (zT -1 p₂ y IT [ . T10))
[ .y (ZT
Cov "TT[ T 2mxx
(30)
= =Z 2) PyΣo"
where in the second line we introduced Py E 1ddxdd, defined as the projector on the last d elements of the canonical basis in 2d Then, since & is sub-Gaussian vector (the entries mean-0, i..dd lab-Gaussian) independent from everything else, we have that, with probability at least 1 2exp (-c1 log" d).
log d 1|01
((()R(0)) s log dl 2 (z 2)
P,500
< log <oogd| (2 2) |
| |E 110" 5
(31)
/mmia 2ZTZ)
where we used ||Pyll and ||0 1l = Since is n 2d matrix with independent rows having second moment Σ, by Theorem 5.39 in (Vershynin, 2012) (see Remark 5.40), we have that
Z T
d
Σ
O
= o(1),
(32)
op
13

---

Spurious Correlations in High Dimensional Regression
with probability at least
2 exp (-czd). Hence, with this probability, by Weyl's inequality, also have
Amin (7 7) 2 ndmin ( | %
n (m),
(33)
where the last step holds because of Assumption 4.1. Thus, we have that (31) reads
|((6R((0))
log |E|lop =0
(
log vn
(34)
Amin (Z (Z)
with probability at least - exxp (-og log d) over Z and E, which gives the desired result.
Proof of Theorem 4.3. As in (Han & Xu, 2023), we define the Gaussian sequence model 0 E RR2d as
hr ( (())
/ +
7P
(35)
V2d
where p is standard Gaussian vector in I222d (the Gaussian sequence model is defined in Equation (1.5) in (Han & Xu, 2023), via the different notation (S.uo)) and our Gaussian vector p denoted g in the same equation). In the equation above, > 0 is implicitly defined via
ny² 0² + Ep
||>1 (ir--0) )[]
(36)
2d
On the other hand, following similar argument the one in (29), have that, for every A E R22d
C(0) Cov IT
([ y 10, x 87)
8 UTENT Bn TT 5~ Px | y 1 x 0
0 D'EE IT
[00 .y | [x:" 0 ]] 0"
(37)
0 Py w T [Ix y [[
[xT,
0 P2D0,
where the third line holds since 7 has 0 mean and independent from æ and y. and by definition of 0 and the fourth line holds because Py [xx" .y _
T y I and because the last d entries of 0* are (i.e., P.,0 0). Thus, since we have that 10 ll S |l op 100 I |>'llop because of Assumption 4.1 (and since ||@ S 1), we have that C(-): R2d - IR is |Σ -Lipschitz function.
Now, since Pxy is multivariate Gaussian, Theorem 2.3 of (Han Xu, 2023) gives that, for any 1-Lipschitz function 2d + (denoted as g in (Han & Xu, 2023)), and any E (0, 1/2),
Fz, (1 ((((OR(()) - IE, (0e) [00) 2 1) s Cidexp (-dt² /Ci)/
(38)
where C₁ a constant depending on Amin (E), |>حلات 0², and n/d d = (1). Since C(-) is linear, notice that we have
Ep c (80) = (E, ( = ((E Σ
a T Σ E
P,E0 C²)
(39)
where we used (37) in the third step, and the definition of (2 in (12) in the last one. Thus, setting sp.)) to C(-)/ | and plugging (39) (38) we obtain
(((LR(A)) - C
Pz.
21 (ddeep((dte
(40)
|F|lop
which gives the thesis after absorbing the constant [Ellop in i,, and noticing that the bound is still true for / E (0, 1/2) since | 2 tr(E)/2d 1 by Assumption 4.1.
14

---

Spurious Correlations in High Dimensional Regression
Proposition B.1. Let (X) be defined (12), and let Sg (ATT be the Schur complement of E. + T(A] with respect to the top-left d block. Then, we have that
-1 (Ezx + -(A)T) Eay (Sx (SEA-TA)))
Ey
(41)
Proof. During the proof, to ease the notation, we will often leave implicit the dependence of T on A. Then, we can write
(A) = Rr I -
(E+ (E 110-1111-11 P4Eæ
(42)
--00 (E++1)- PyE00" +0 Pg500* - (I+
where the last step holds since P = 0. This expression be further manipulated using the notation introduced in (14). We also introduce the following notation
(I (1) -1 ( +I)
[ + r!)
( (-+
xy M9
(43)
( rI)
where we divided (C (E++1))+ in four d x blocks. Notice that, the expression in (42) only depends on (E+ F1) i.e.
T1)
-() P,E0 - [E+ 11) -1] xy
Eyx
(44)
where we denoted the projector on the first d elements of the canonical basis Rd2d as Pa Rd2xxd Exploiting the Schur complement. SE+rl, holds that
[S5 (
+I) -EErr Exy (S
(Erw +
(45)
which combined with (44) proves (41).
Proof' of Proposition 5.1. During the proof, to ease the notation, we will often leave implicit the dependence of 7 on X. Then, according to (12), we have that
(²((a) = 00 TE -.ET))
<1001]
|P < |Egeelopp
(46)
and
[cb(2)] = 0- T 22 -1) 1,,0
< ||0* |>ا| Amin (E)
1
Amax (
(47)
15

---

Spurious Correlations in High Dimensional Regression
Then, using (41), we get
(A) 0- (Eez + +TT)= -xny
Ery (5ttT1) -1
0-1 (Eoz + +rI)=
(Enz rI) 1 1/2
Eny (S Dne (En + T1) -12-1122 11 + TT) 83
T (Zizz + +11)-1/20 0%
(Dixx 1/2
0z 2
(Nio + =1) 1/2 Dzz (52+r1) - 2nzo (Zizz + =1) -1)-1/2/ 1/2
S T v Amin (Eazr) +
V
0= Exx0 + [Eiss + T() 1/2 Ezy (5 -1 Eyz (Ezz + r1) -1/2
+11-
op
ExxPx (xT))a)
1/2 May + (Eiz + + +1)--1/
12
op
7
Ammin (Eez)) +
Amin (S
R 02 [02)
+T
Amnax Eye (Eru + =1) -1 Exy
V /mmia (Ezz) +
Amin Eyg TI Eye (Ziv + Tf) Eay
Eg 1
+
Amax ( Emyy
V Amiu (Exz) +
Amin (Eng + TI En Enrl Eay)
By [9a] 0² + Amax (Ean)
Amin (5H)
Amiu (Exz)
+ Amin (S +
S STVVar(g) o² Amax (Eny) - Amin (5%)
Aminn (S%) Amin (Ewe)
(48)
where in the fifth line denoted with Px the marginal distribution of the feature x. and Ey [-] from the sixth line on denotes an expectation with respect to y distributed as the labels of the model. The last step simplifies the expression with respect to and it holds since Var(g) o² = 0 En 2 Amin (Ez.). This, together with (46) and (47) gives the desired result.
Proof of Proposition 5.2. During the proof, to ease the notation, we will often leave implicit the dependence of on X. Then, as in (Han & Xu, 2023) and in the proof of Theorem 4.3, we define the Gaussian sequence model 0e E R2dd as (35) where p is a standard Gaussian vector in R2d and > 0 is implicitly defined via
ny² = 0² + 1E,
|| (or -0>)1 o² x²+
+//21/2 (1)+ 3 - 0r
72 tr (1)+ 2 -
r1)
(49)
2d
2d
which also reads
o² + 72
+++T]] - 521/200
ny2
(50)
2d
u((E+11)~
Then, due to Theorem 3.1 of (Han & Xu, 2023) the prediction risk, since Pxy is multivariate Gaussian due to Assumption 4.1, we have that, for any t E 1/2),
Pz. (E((LR(A)) 2² 2t) < Cdexp (-dt* /C),
(51)
where C' is a positive constant depending on Amin (2), ||>)lap 0², and n/d = n/d= O(1)
Proof of Proposition 5.3 As T(A) is an increasing function of X, all the statements on the monotonicity of (*) and (X) can be proved by showing monotonicity w.r.t. 7 (whose dependence w.r.t. is left implicit throughout the argument)..
16

---

Spurious Correlations in High Dimensional Regression
In particular, have
72 (2 +T)
1
tx (x(())))) =
(2)
dr
dr
tx (=((E+r1))22z))
(52)
(((E++1)--E')
[ (I) 01/20" 0² +r²
dr
tr (-++11)
To study the sign of the above expression, it suffices focus on the numerators, the denominator always positive.
Note that the RHS of (13) smaller or equal to 2d/n; thus, as 2d < n, we also get S A - 2d/n) which implies T(A) + as
Hence, show that (A) is monotonically decreasing in a right neighborhood of À O, it suffices to show that (52) evaluated in is strictly negative. For 0, the first factor the numerator of the first term in (52) is the following chain of equalities holds:
d dr
[+ -1) - -0-///20011
:)) d
2) dr (11//++)>1'"> 11/2//
0r T d
(E/r + 1)- Eg
dr
-0- (E/T 1)-2 EE/T+18/ 110 (5/T +1)-
(53)
- 100T(1//++4)))000110000011 (2/T+1)) 1)-²
(- (2/T+1)) - 200
2Σ
2T0 (I+ "0.
Furthermore, the second term gives
2 d
(E++1) rI) - x²)
0² d
2d X k= (Ae 7)2
20
2d
X
< 0,
(54)
dr
n
dr
(Ax + T)
k=
where d denotes the k-th eigenvalue of Σ. This gives the first claim.
To show that there exists Ag 0 such that (*) is monotonically increasing for À > Ac will show that the derivative of (A) with respect to r is positive for all 2 Tc := r(Ac). For simplicity, in the rest of the argument we use the notation Amax and Amin to indicate the largest and smallest eigenvalues of Σ. respectively. Instead, the notation Amin (-) still represents the smallest eigenvalue of its argument. For the first factor of the first term of (52), continuing from (53), we have
d dr ( -1) -
11)) 22 Amax (E/T + 1)3 Amin (E/T)²= 72 (Amax/ T + 1)
1
212
min
(55)
For the second factor of the first term of (52), we have
tr (I + rT) -I) x2
2dA2
1
max n/72
(56)
n
(AR + 7)
For the first factor of the second term of (52), we have
72 -T
S2
Amax
(57)
(Dmin 7)²
17

---

Spurious Correlations in High Dimensional Regression
For the second factor of the second term of (52), we have
dr ( 1 (=+++1))
d
1d d
2d
X
2
2d
X
4d
max
(58)
dr
(As
+ +)
n
(Ax
+ r)
n73
km
kml
Thus, putting together (52), (55), (56), (57), and (58), the monotonicity of (*) is implied by
212
min
1
2d
max
0² +2
Amax
4d
max
(59)
22 (Amax/ T + 1)3
nr²
(Amin + +)²
nT3
Now, we have that the above inequality holds for sufficiently large т: the LHS is @(1/+²) (considering fixed the other quantities), while the RHS (11/r)); and the desired statement is therefore proved.
Next, we set Tc == =(Ac)= v Ami (5 and show that (A) monotonically increasing for T E [0, rc]. Plugging
Egs = I in (41) we get
(A))= T (Ex + Eay (S -1 Eyn - 1
T
0% Exy Eggy TI Myyelisy
Eyar
(60)
F'p 1++
By the product rule, and introducing the shorthand A(T) Enye rI
we have
dC
00 T N
(
d
(0z
-zy -2:
dr
dr
I (I+T
+
1+
dr
1
0" ExyA(T)~
07 +
8 T A(T))
(- A(T) ''TT 07
(1 + r)3
(1
MTyy D
8% ATy (iTr)~IITTT
'I 0-
0 Σ T A(T)
I+
(1+T)²
1+
(1 + r)²
[A(T)
Σ Ezy sxy
6 A(7)
1
A(T) -12; 0
(61)
(1+T)
1+T
[1+++²
Eny +Tl
DTy Eag
ΣT Exzy
(1+ Or A(7)
TI T (1 71+
Byy
A(T) A 02
1
(1+T)²
7)2 O" Eny A(T (Eyg - DI Een - 1)
(1+ & E A(T) (5 1²) A 0I
where in the second line we used the identity d (A(7)- (- A(7)) A(7- Then, if S / Amin (8 we have that (S 721) is p.s.d., which in turn implies CD (A) readily follows from (60).
Te.
dA) dr > 0, thus giving the desired claim. The non-negativity of
For the last statement, setting TC = Ammin (Σ) we show that (*)( is monotonically increasing for all 7 E [T2, +00) as long the additional bound on 2d/n nn holds. As Amin (52) S Amin (Eyn) S ir (E /d ir (E (E=xga) /d also have
Te
Amin (ST) 2 Amin (S 2 Amin (E) = TC,
(62)
where the second inequality follows from Lemma B.3. Thus, from the monotonicity of T(A) in X, the final result readily follows.
remains to prove the monotonicity of (* in [Amin (E), +oo).
To do so, we again study the sign of (52).
18

---

Spurious Correlations in High Dimensional Regression
For the first factor of the first term of (52), have
dr (1
11:)
20 (2/T +)/ (2/T+1) (2//7)
20 // (E+ 11 0/20
(63)
2 Amia
(E(I+))
-
2 Amin
=² | [3 +1) -1) x
Amin
For the second factor of the first term of (52), have
tr ( + rI) 52
2d
2
2d
k
2 2 1
(64)
(Ak + r)
k=
For the second factor of the second term of (52), we have
d
( tr (E (I)+ x
2 2d
X
4d
1
Au + r) S
(65)
dr
n2
π
n1 T (Amin +
(AB +
no (Amin + +
Thus, putting together (52), (63), (64), and (65), the monotonicity of (² is implied by
Amin
02 | (1
"2/20- 12)
4d
72
(I+
2
0² + 72
E + rI) -1
12)
(66)
Amin
(Amiu + T)
Since we assumed that 2d/n= S Amin/4 E 1/4, we have
2 Xmin
(1 (1-2))
2d
4d nT (Amin + T)
2 Amin
1- 2d
2d
1 Amin
(67)
Amiu
n
Amin + 7
7
ndmnin
Amiin
and
72 (E++T) r1) _1//2/ 2 Amiu
(E
72\x
ming
(Ax + 7)²
A
-ming
(Ak/T + 1)²
(68)
A
ming
(Ak/ + 1)²
Ax/ Ammn
Amiu ming
(Ae/ Aae/Amin 1)²
Amax
(A Amin + +1)
where in the fourth line we used that + Amins and the last step we used that f(x) = 1/(x 1)² is decreasing for
1.
Thus, using (67) and (68) gives that (66) is implied by
Amax
1
Amin
4d nET (Amin + T)
2 0²
(69)
(Amax/ Amin + 1) T Amin +
which holds since we assumed
2d
1
Amare Amiu
(70)
n
20²
(Amax/ Amin + 1)²
19

---

Spurious Correlations in High Dimensional Regression
B.1. Proofs on S For completeness, in this section we prove two known results about S
Lemma B.2. Let = [x [xT,y]] Pxy be distributed according to a mean-O, multivariate Gaussian distribution with covariance Σ, such that E. is invertible. Then, the Schur complement S of E with respect to the top left block Eza (see (14)) corresponds the conditional covariance of y given i.c.
S Cov (y = Ø) = BBlz== [v Eyl bb]) (y Eyjz== (y1) 7
(71)
Proof. Consider the expression - According to the notation in (14) and in (43), we have
Fx x y "I Iwv y + xx [x= y y² [2 x.
(72)
Then, the formulas for the inverse of a block matrix give
=x (Ded Diz S St Eyz 2 + T St
S v+
(-DIEE y + 8T (-S 2ige x
(73)
= x Endl (y- x0 5 Ey a
Then, denoting with p(x, y) and p(x) the probability density functions of "J and respectively, get that the probability density function of conditioned on x takes the form
p(x;1) y) p(x)
plylz)
v (2Tx) )ad det (Exx) exp [-[xT, [ITTy'l [ - x .2 _ /2)
V (2T)* 2d det (Σ)
exp (-x Exs (5/02/222 22/2)
1
exp (- [x. T .v _u I-1 [x. 11 TJ 12 + T x2222/2)
(74)
(2x) Sngdder det (8H)
exp (- (y Eiy 5oz- (y Miz 2i x) /2)
(2T)² det (SF)
where we used Schur formula for the determinants in the third line, and (73) in the last step. Thus, we have that p(y|ær describes the density of a multivariate Gaussian random variable, with covariance S..
Lemma B.3, Let Σ E 2dx2d be a p.s.d., invertible matrix. Then, the Schur complement S E Rdxd of with respect to the top left block Eez (see (14)) is such that
Amin (5 Amin (Σ)-
(75)
Proof. Let I e pddxd be the rank-d matrix defined as
1/2 2xx 1/2 Lyx Zage
(76)
and S E [R2dx2d as the matrix containing S its bottom-right d block, and everywhere else. Then, we have that
Σ S=S+ITT,
(77)
where both S and T are rank-d p.s.d. matrices.
Denoting by (S) the k-th largest eigenvalue of S, by the Courant-Fischer-Wey min-max principle, we can write
A (S) maxw, dW> min [|x],== (u' Su)
(78)
20

---

Spurious Correlations in High Dimensional Regression
where with W we denote generic k-dimensional subspace of R2dd Thus, the desired result follows from
Ami [ = Amiu (S + I
minjjullg=11 T. (S 1ITTT)
S min 11ulll==1111 u. (S + (T+TTT a
(, u Su
(79)
I
|| u T Su
Aa(S)
Amin
(S
where the last step holds since the d smallest eigenvalues S are equal 0, and the d largest correspond to the ones of S
B.2. Remarks on Assumption 4.1
Our results on linear regression rely on Assumption 4. and in particular on the training samples be normally distributed. This assumption is made for technical convenience, as the concentration results in Theorem 4.3 and Proposition 5.2 still hold under the following milder requirement.
Assumption B.4 (Data distribution). The input samples {2] are n i.i.d. samples from a mean-0, sub-Gaussian distribution Pxy, such that
1. its covariance E E Rddx2d is invertible, with Amax (I) = 0 (1), Amin (Σ) 2(1), and tr(E)= 2d;
2. for z ~ Pz, the random variable - 1/22 z has independent, mean-0, unit variance, sub-Gaussian entries.
This assumption resembles the requirements A-B in Section 2.2 in (Han & Xu, 2023), where we also included the scaling of the trace. To formally state the equivalent of Theorem 4.3 and Proposition 5.2, one also has to enforce the following technical condition on the true parameter 0*
Assumption B.5, Let = 1/72, then we assume that
0 s.t. 10"") < Co6-1122
(80)
In Proposition 10.3 in (Han & Xu, 2023), it is shown that this condition excludes negligible fraction (Ce-n² of the 6* on the unit ball. Since we set 5 = 1/722, following the same arguments of the proofs of Theorem 4.3 and Proposition 5.2, we have that Theorems 2.4 and 3.1 in (Han & Xu, 2023) imply the results below.
Theorem B.6. Let Assumptions 6.3 and B.5 hold, and let n O(d). Let (rR(A) be defined as in (8), and let C(ÔLR (A)) be the amount of spurious correlations learned by the model fLR (BIR(A).)) as defined in (3). Then, for any X >> 0, we have that, for every t E (0,1/2)
Pz. ((C(OL((A)) - (=(N)/1)))))) 21) S St--13 1/8
(81)
where C (X) is defined in (12), and C is absolute constant.
Proposition B.7. Let Assumptions 6.3 and B.5 hold, and let = (d). Let (LR(A) be defined as in (8), and let C(OLR (A)) be the in-distributton test loss of the model Fi (L)())(()))))) as defined in (5). Then, for any > O, we have that, for every t E (0. 1/2),
PZN ()((hR(A))
((faR(A))===000) - /² --0))) 21) S 9
(82)
where (x) is defined in (20), and C and are positive absolute constants.
C. Proofs for Random Features Lemma C.I. We have that
[IVI = (v
(83)
21

---

Spurious Correlations in High Dimensional Regression
1z = -
(84)
with probability at least 1 - 2 exp (-ed) over V and Z, where c is an absolute constant. Furthermore, for every E [n], we huve
||il||2 22d +/2
= (1).
(85)
Proof. V has independent, mean-O, unit variance, Sub-Gaussian entries. Then, the first statement is a direct consequences of Theorem 4.4.5 of (Vershynin, 2018) and of the scaling d = o(p).
By Assumption 6.3, have that Z has i..d. mean-0, Lipschitz concentrated rows. This property also implies that the rows are i.i.d. sub-Gaussian. Thus, by Remark 5.40 in (Vershynin, 2012), we have that
| z n 0
(d).
(86)
nt
with probability at least 1 - exp (-cid). Then, conditioning on this high probability event, by Weyl's inequality, we have
| Z -|lop op S |n + || 7 - nxll = O (d),
(87)
where the last step follows from the argument used to prove |sE||ap (1) in Lemma C.I in (Bombari & Mondelli, 2024). For the last statement, we have
2d = tr()) = ir E [=2 1) = E. [tr (zz } R [tr (=T=)] E [1=11]]
(88)
where we used the cyclic property of the trace. Furthermore, we have
|||=||| E [|= = (1),
(89)
since z is Lipschitz concentrated. Then,
0 5 2d
E [||=1|2] 12 = E [1|=1|] E [| Ci.
(90)
for some absolute constant C1. Thus, vI 2 1 for
[0. 1]. obtain
C1 $
C1
E ||=1||1
S
S 1.
(91)
2d
2d
2d
Plugging this last result in (89) gives the desired claim.
Lemma C.2. We have that, denoting with ji² = Ekze ub with μi denoting the k-th Hermite coefficient of é,
2d Ev [00 J -p (ni² ZZ + +1221
(
log d Vd
=0
(92)
up
with probability at least 1 - 2exp (-clog² d) over Z, where e an absolute constant.
Proof. For all i E [n]], we define the functions ((() R + R as (1) = o /V2d). Note that (5(() is odd, since & (i)
odd by Assumption 6.1. Thus, denoting with H the k-th Hermite coefficient of ((9) for every i E [m], we have that (1)
Mi for all even k. This implies that, by denoting with v random vector distributed as the rows of V, i.e. 22d is standard Gaussian vector, we have
Ey ④ II., = E.
[o(xTv)o(2] b)]
TT-
22d 256)) /
2j
p.
(5(1)
2d0
||21||2
||2|1|2
2, 2z
(93)
p Σ
(3) ())
Mk Mk
||:1|12 1|=5|122
2T 2j ||
2T1 2j ||3i||2 | 112
=pp(") (1) (1)
+ >
(4) ()
Mk Pk
|12/112
A23
22

---

Spurious Correlations in High Dimensional Regression
Then, denoting with D2 R the diagonal matrix containing Pa /||/||2 its i-th entry, we can write
D1 + Σ D₁ ( ok DR-
Ev ④
(94)
R23
Notice that, due to the last statement Lemma 1.1, we have that, jointly for all E [x].
1
log d
(95)
/2d
vd
with probability least 1 exp log² d). Then, conditioning on such high probability event and denoting with p a standard Gaussian random variable, for all E [nx]
we have
(8) 141
11
=
E post (p)
E
[p(()]]
- -b(p) )]
Ep
22
11al12
B
1 + p Q(p)
/2d
1
<
Ep
p+
(96)
V2d
|2:1|2
LIE,
|pl
lpl
V2d
1 112
1 EE, [p21
/2d
log d
Vd
where used Jensen's inequality in the fourth line, the T-Lipschitzness of Φb in the fifth line, and (95) in the last step. With similar approach, denoting with I|-liza the L norm with respect to the Gaussian measure, we have that for all i E [n]
11
S 0000 1:00-60
$1
L2
(0) - -b(p)) 1/2
Ep
- - 271/2
(0) ((
[lalle - 11) p+p)
Ep
(97)
/2d
|| ll
E, [ 1/2
T
1
/2d
log d
Vd
which directly implies that, for all E [n]. |0000|| 1-
Exso (44 (10))
+(1), and that
(8)
<
600)
2
1
+ (2) (14)) -M² = 00(40
log d
(98)
Vd
A23
123
23

---

Spurious Correlations in High Dimensional Regression
Thus, we ready estimate the operator norm of the off-diagonal part of the second term the RHS of (94), specifically
Du (2ZJ) ok Dr. - Diidiag
Σ Du (ZZT) of DE A23
123
D (ZZT)
Dr= diag
DD (ZZ ) DE)
k3
1/2
2/J 23
Σ
10
)
(99)
max
Mk MK
1zill2 1
R23
(E(M)NE(M
3
Σ
(8) 2
< max
|2úll2 |2z/|22/
123
(Log')
loo' d vd
0 log dn
=
d3/2
where in the first step we replaced the operator norm with the Frobenius norm, and used triangle inequality; in the fifth line we used that ||æl|2 = ((vd) for all E [x]] (true because of (95)), and that jointly for all * j we have 2. 2// //|/||=|||2 = (log d) with probability least 2 cxp(-c2 log² d) since the 2,-8 are independent sub- uub-Gaussian vectors (since they mean-O and Lipschitz concentrated). The diagonal part of the second term the RHS of (94) respects
diag Σ DE (ZZT) ok DE - 1221 R23
maxi(()
Σ
1
(1) 2
=
O
log vd
(100)
223
op
because of (98). Lastly, notice that,
Tz
ZZ
D2zz D1 - 111 2d
u T DDZZ DRu - 1L
sup
U
op
|| 1 =1
2d
ZT
| Diul -MP
sup || =1
22
2
T
Z
(ITDDuull Diulls
T Diu - P1
sup || =1
+ 14
2d 41
sup
2
(101)
||u||==1
v 2d
2
zT
Z
|| D2
lopp + 141
Z D1
11
22d up
2d
|| op
llpp
Dillppp
111
|| op
D1
11
22d
2d
By Lemma C.1, have that 11
with probability least 1 exxp (-o2d), and since ||= O(vd) and ( O (1) for all i [n] (true because (95) and (96) respectively), we have that ||Dillop O (1/Vd) Furthermore,
0
(va)
we have
11
P1
D1
= max;
2d
|| 1l
22d
op
< max;
12ill2
(|p5") (8)
P1
+
1
2/
2d
(102)
log
0
d
24

---

Spurious Correlations in High Dimensional Regression where the last step is consequence of (95) and (96). Then, we have that (101) reads
p D1 pi
zz
log d Vd
(103)
2d
op
standard application of the triangle inequality to (99), (100) and (103) gives
log d Vd
Di27 D1 + Σ
Dj (
+
p22
0
(104)
2d
k23
op
with probability least 1 - 2 exp (-cg log d) over Z (where used μl 0 since e is odd), which readily gives the thesis when plugged in (94). Lemma C.3. We have that
10llopp = 0 (vP),
(105)
④Φ T Ey [$ 1 11.pp =0 (Vid)
(106)
Amia (Dob) = [
(107)
with probability at least 1 2exp (-clog² d) over Z and V, where e an absolute constant.
Proof. Φ a matrix with i.i.d. rows in the probability space of V. In particular, its i-th row takes the form
à: Φ (ZV..) = (ZV:) Ey (Ø (ZV:))),
(108)
where the last step holds since the (Gaussian) distribution of V₁ is symmetric and & is an odd function by Assumption 6.1. Then, since v/2 Ve is standard Gaussian (and hence Lipschitz concentrated) random vector, and ø is a Lipschitz continuous function, we have that
11 Vd
Jullos =
op
O (1),
(109)
where the 11-1ly, meant on the probability space of V, and the second step holds with probability at least 1 2 exp (-cid) over Z due to Lemma C. Conditioning on this high probability event, & is p matrix whose rows are i.i.d. mean-0) sub-Gaussian random vectors in R" Then, by Lemma B.7 in (Bombari et al., 2022), we have
opp = O ( (Vr+ vp) = 0 (vp),
(110)
with probability at least 2 exxp(c22)) over V, where the second step holds because n o(p).
For the second part of the proof, again follow the argument in Lemma B.7 in (Bombari al., 2022), which in turn exploits the discussion in Remark 5.40 in (Vershynin, 2012), and conclude that
(Φ - Ey [ op = =0
7 (Pv
= O (vmm) = (V(vd)
(111)
with probability at least - 2 2exp(-caa)) over and V.
For the last statement, Lemma C.2 and Weyl's inequality imply that, with probability at least 1 2exp (-e2 log* d) over we have
Amin ( T) 2 Amin [1
22
+ (121) - Fy [ T -pppp (111222 Z2
+ 1211
Ev [T J op
-
2d
2d
op
(112)
p plog d
1)
2 pj? - O
0 (Vid) = 2(p),
Vd
where the last step is true since ji + as Φ is non-linear by Assumption 6.1.
25

---

Spurious Correlations in High Dimensional Regression
Lemma C.4. Let Ø IR + lR be defined as Ø(-) (6(-) 101 and set
d3/2
n' min
(113)
"log* p
log
Let {2i)i=1 be i..dd random variables sampled from a distribution respecting Assumption 6.3, not necessarily with the same covariance as Pxy, and independent from V. Then, if in E B is defined as the matrix containing 6(V&, 2,) in its i-th row, we have that
[ = (VD);
(114)
with probability at least 2exp (-clog² d) over (2: and V, where e. is an absolute constant.
Proof. The proof follows the same strategy as Lemma C.8 in (Bombari & Mondelli, 2024), with the only difference that they work under their Assumption 1.2, i.e. that the data is normalized as || /2d (in our notation). This difference, however, does not affect the result. We can in fact condition the high probability event that all & are such that || @(vd), which holds with probability least 1 2 exp (-ed) by Lemma C.I, and proceed in the same way (as their Equation (C.78) now holds) until their Equation (C.81), which requires their Lemma C.7, i.e. that
Ey
T n
= (p).
(115)
op
This holds also in our case, as it can be proven following the argument in (99) and (100), line of (99) has be replaced with n', making the RHS there being O (1), as n' O the normalization of the data is used one more time in their Equation (C.91), but it is not critical to obtain the result, as || = @(vd) is sufficient. We remark that Assumption 1.2 in (Bombari & Mondelli, 2024) also requires the covariance of the distribution to be well-conditioned, which however not required for the purposes of the above mentioned lemmas.
where now the n in the last a/22
by definition. Lastly,
log
from Lemma C.5. Let क RR + R be defined as Φ(-) == <(-) pı(.), and let E IR2d be sampled from distribution respecting
Assumption 6.3, not necessarily with the same covariance as Pxv, and independent from V. Then we have that
E ((V=))(V=2
=o (1os'd+ d+
(100s'
log d d3/2
(116)
with probability at least 1 - 2p² exp (x (-clog² d) over V, where e is an absolute constant.
Proof. The proof follows similar path the one in Lemma C.15 in (Bombari & Mondelli, 2024). In particular,
n' min (1
p log p_ log" d )
d3/2
N N= p'nn
(117)
and let T RR. Nxp be a matrix containing ((V2,) in its i-th row, where every {2: 1 sampled independently from the same distribution of z. Thus, x can be seen as the vertical stacking of p² matrices with size n' p. All these matrices respect the hypotheses of Lemma C.4, and hence have their operator norm bounded by O (vp) with probability least 1 --2exp (-e1 log² d). Thus, performing a union bound over these p² matrices, we get
Np n'
=0 ON log" p+ Nplog d d3/2
1 1 lop
00ppp) =
(118)
with probability at least 2p exp (-c1 log" d) over V and (NN
Via the same argument used for the last statement of Lemma C.1, denoting with E 2d the k-th row of V, we have that ||ull|, O (1) uniformly for every & with probability at least - 2p e22( Conditioning on such event, we have that each entry of 21) is Sub-Gaussian (with uniformly bounded uub-Gaussian norm), since 21 is sub- Gaussian (as it is mean-O and Lipschitz concentrated) and Ø is Lipschitz function. Thus, we have that each entry of Es, ( is O (1)
26

---

Spurious Correlations in High Dimensional Regression
L.,, [o(vá)] ||
= { ( - (VD))
(see Proposition 2.5.2 in (Vershynin, 2018)), and therefore that
viz Then, conditioning on the high probability event ||V = O ( (vp/d) given by Lemma C.I, we have
s < Es, [
+ || [
11,0 22
= vV)
(119)
where the second step holds because 2 is Lipschitz concentrated and ă is Lipschitz. Since the rows of ΦN are identically distributed, this also holds jointly for all other 2,-8, for i [M.] Then, 2 /p is matrix with independent sub- Gaussian rows, and by Theorem 5.39 in (Vershynin, 2012) (see their Remark 5,40 and Equation (5.25)), we have that
$ T ΦN p
1
E,
(((2))(V=))
= (V op
=
(120)
N
with probability at least - 2exp (-cap) over { Then, we have
PN
1 Φ
E (VV2))
E2 (((=))(V22)
+
op
N
N
lpp
+ O ( log'' p plog*
N
d3/2
(121)
log + VD VDV
log*
log p + plog" d
VP
+ 0
d33/2
d3/2
log d d3/2
0 log' p
where the first step follows from the triangle inequality, the second step a consequence of (120) and (118), and the third step follows from the definition of N.
Taking the intersection between the high probability events in (118), (119) and (120), the previous equation then holds with probability at least 1 - 2p² exp (-cy log² d) over V and {&) Also note that its LHS does not depend on { )= i== which were introduced as auxiliary random variables. Thus, the high probability bound holds restricted to the probability space of V, and the desired result follows.
Lemma C.6. Let Φ= + IR be defined as 3(.) = (() - (x()) and & RRux as the matrix containing ((Vz,) in i-th row. Then, we have
- (VDlogd++ plog
Φv op
(122)
d
with probability at least 1 exp (-clog" 2 d) over Z and V, where e is an absolute constant.
Proof. Note that ő is Lipschitz (since @ is Lipschitz by Assumption 6.1). During all the proof, we condition on the event || = d and 1|2 θ vdd for all i [n]. which holds with probability at least 1 exp (-cid) by Lemma
C. During the proof we also use the shorthand v E 2d to denote a random vector such that v /2d is a standard Gaussian vector, Le.. has the same distribution as the rows of V. This implies
E.
(vnn.
(z -E. | = (1),
(123)
and
|||el12 - E. [1lllllp, = =0 (2))
E, [[|||]]]] 0
(124)
27

---

Spurious Correlations in High Dimensional Regression
where both Sub-Gaussian norms are meant on the probability space of v, and where the very first equation follows from the discussion in Lemma C.3 in (Bombari al., 2022). Then, there exists absolute constant C1 such that we jointly have
| Siva.
||l|a C1
(125)
with probability at least 2 exp (-o2d) over v.
Let Eg be the indicator defined on the high probability event above with respect to the random variable dy = Vi (the k-thh row of V), i.e.
E = (1oxll22 - C2
and [ - Civo).
(126)
and we define E E RPxP as the diagonal matrix containing Ej in its k-th entry. Notice that we have || - -Ellop = 0 with probability at least 1 - exp (-c2d), and Ey
[|I
E olop
2p (-c2d).
Thus, we have
By
@ F.)
V
11
F
Filop
VVllup
op
up
1/2
| 1/2
EV
4
IVIC
Ev
op
1/4
(127)
< BV
Ey
(2pexp (-c2d))
1/4 By
< Ev
(2pexp(-cad)) (-c2d))
(1),
where the last step holds because of our initial conditioning on Z: the first two terms are the sum of finite powers of sub- Gabbsannsi random variables (the entries of & and V), and thus (see Proposition 2.5.2 in (Vershynin, 2018)) the first two factors in the third line of the previous equation will be O (p*) for some finite a, which gives the last line due to Assumption 6.2.
As in Lemma C.2, we introduce the notation (for all i E (m)) ((0) IR - IR such that (0)(() ~1|== /V2d). Thus, denoting with 2d random vector such that /2dv standard Gaussian (i.e., distributed as the rows of V), we can write
Ey EV
P E. ((Zo)u")
]]
2d E,
(00)
2, V2du) (c) (v2do)) V2d
p
2
(128)
||2:||
||
where 2(0) the first Hermite coefficient of (60, Then, denoting with D ux the diagonal matrix containing ū1()) || la in its i-th entry, we can write
Ey
ΦV I,p
Dz
S
P
D
|
(129)
22d
up
2d
up
Then, since we conditioned on || = θ (va) for all E [m)] following the same argument in (96), and since the first Hermite coefficient of Ō is 0 by definition, we have
( p log Va d
=o coploy d
Ey
=
vā
(130)
d
op
with probability least 1 2 eex (-cg cg log* d) over Z. A standard application of the triangle inequality to this last equation and (127) then gives
-0200 (plog d )
Ey
<
Ev
T
By
E) E
=
(131)
d
0p
0p
28

---

Spurious Correlations in High Dimensional Regression
with probability at least 2 exp (-ca log d) over Z.
Let's now look at
ŒEV Ev
ΦEV
ò( (Zux) Eur (elZzu))Ex
WE.
(132)
where we defined the shorthand Wa = 1 - Eug Exu (132) is the sum of p i.idd. mean-O random matrices We (in the probability space of V), such that
sup 6(Zoz) Eive [o(Zez)Ezu)
s 2uu
op
= 2 sup 6(
|10/12 Es
(133)
220
because of (126). Then, by matrix Bernstein's 's inequality for rectangular matrices (see Exercise 5.4.15 in (Vershynin, 2018)), we have that
Pv (|ēEV- Ey D
f2/2
2t)
s (n d) exp
(134)
02 + V
where o² is defined as For every matrix A, we have IE (A (A- ] [AAA B[AJE[AT] 3E AA
0² = pmax (I [W& W 11app ||B., [W Wi] l.p))
(135)
Thus.
Brn, W
# 1l - Ey (8(Z))) ELUD vs Fae(( (Zuk)
E.,
(((zz))( (Zek))
7 sup
Eg 110x 112)
(136)
- c?
Er. (Ø(Zvz) 71
0 (1),
where the last step is direct consequence of Lemma C.2, applied to & instead of to 4, and holds with probability at least 1 - 2exp (-os log" d) over Z. For the other argument in the max in (135) we similarly have
E WT WA
1l < Eua uy Eyō(
T ((Zvk) (
Ex /6 Zuu) 22)
< || Bun. [nrul] 11
sup vx
(137)
< Ofd
o (1).
Then, plugging these last two equations in (134) we get
Py (
- Ev
T || op
2 VPlogd I (n + expp
exp
plog² d/2 (Coppt 201 v dd d/3
I 2exp (-co log d).
(138)
where we used Assumption 6.2. Then, applying triangle inequality and using (131) and (138), we get
=0
(oV log d plogd
(139)
op
d
29

---

Spurious Correlations in High Dimensional Regression
with probability at least 2 exp (-07 log² d) over V. using Assumption 6.2 get the desired result.
V. Then, since E /with probability at least 2p exp (-ezd),
Lemma C.7. Let 2 E IR22 be sampled from a distribution respecting Assumption 6.3, not necessarily with the same covariance as Pxy, independent from everything else, and let fur(ORr (A), be the RF model defined (22) with (RE()) defined in (24), with À 2 Then, we have that
(FO) +nAI) -1 -1 G (d//4 (p/4logd logd
(
log"/2 d d2/8
(KT(ORF(2)) (2); 11p0
pp1/4 p11/
o(])
(140)
2d
with probability 1 - CVdlog" VD C Clog' d/d²/4 over Z, G, V and 2, where C' is an absolute constant
Proof. Let o R + IR be defined as 0(-) =- d(.) mi (-), and let & E Ruxp be defined as the matrix containing ø (Vz;) in
its i-th row. Then, introducing the shorthand G = (D + +ndl) -1 G. we can write
fRF (RF(ORE(A), = +V (HIVZ + + + G
(141)
z TT
= =pip=
G + n² (vTV- ) z ZT m12 V T 4G.
2d
Notice that since every entry of G is sub-Gaussian and independent by Assumption 6.3, Theorem 3.1.1 in (Vershynin, 2018) with probability at least 2exp(-c1d) over Then, conditioning on the high probability event described by Lemma C.3, get
readily gives |G||2 O (vn) o
(vd
| < (Amin (D- + +nf)) ||G]l2 S (Ausin ($ () ||]|| = O Vdd
(142)
with probability least 1 2 exp (-o2 log" d) over V, Z and G. We will condition this high probability event until the end of the proof. Let's then investigate the last 3 terms on the RHS of (141) separately:
(i) A direct application of Theorem 5.39 of (Vershynin, 2012) (see their Equation 5.23) gives
2d V V
1
=
(V
d
(143)
p
op
with probability at least 1 - exp c3dd over V. Then, since is sub-Gaussian and independent from everything else, with probability 1 - 2cxp (-ca log" d) over itself we have
|+i== T (VTV=
P 1) 2d
2 G
< log d
|| (VTV-
p
7
G
2d
2
< log
VTV
P
|1
lop
G
2d
2
(144)
p
Vd
Vd
=0 log d
va
0
V
p
vp
where the third step holds with probability least 1 exp (-c5d) over Z due to Lemma C.I.
iii) As before, since is sub-Gaussian and independent from everything else, with probability 1 - 2exp (-ca log² d) we
have
MI T T &G < log d
V $ | 6
=o 10 log (Vologd d plog d d
Vd
-o (1og" (VE=+ v12)
(145)
p
where the second step holds because of Lemma C.6, and holds with probability at least 1 - 2exp (-co log² d) over Z and V.
30

---

Spurious Correlations in High Dimensional Regression
(iii) For the last term of the RHS of (141), its second moment in the probability space of reads
E2 G
(V=)
&6 < Ez (V=) (V=)
| 1
G
(146)
=0 (10g" d
p log d d3/2
vdl
(dlog' d
log d' vd
vd
p
where the second step follows from Lemmas C.5 and C.3, and holds with probability at least - 2 exp (-07 log d) over and V. Then, by Markov inequality, we have that there exists a constant C1 such that
(V)2)) 2c) <ci
[dlog*
log" d vd
+
4
(147)
P
with probability at least 1 1/t over 2. Setting
vp min Vdlog* d d1/4 w(1,
(148)
since p w (dlog* d) by Assumption 6.2, we have
d=//logg d2/4 1ollogd d p1/4
log d d1/8
(V(2)) &G =0
(149)
with probability at least 1 vdlog? VD log d/d'/4
Then, plugging (i), (ii) and (iii) (141) gives
2 TT
[dV/Alogd
dd'/4
logd
log d. d1/8
fRu (R)( -2ā0"
G
0
(150)
2d
p1/4
with probability at least
vdlog" d vp
C8
log" d//
which gives the desired result.
Proof of Theorem 6.4 Let E E Raxx be the matrix defined as
2Φ - D ( TT
(1) + 121))
E
(151)
2d
Note that
777
= -0 =0
([( log d Vd
loged)
))
|Blppp <
||
-Ev
[T 111
+
Ey [T
-p
+ j1TT)
(152)
2d
with probability at least cxx (-c, log? d) over Z, V due to Lemmas C.2 and C.3. By the Woodbury matrix identity (or Hua's identity), we have
(0D + +nn1) -1
TT
1121)
+E+nN))
Mi 2d
pip 7.7
+ (102 + I 1+ I+E
2d
(153)
pip ZZT
+ (i-2 + +2
2d
11pp TZ
1i Zz
+ (ji'p
(1'2+
E
+
(13p+n)) T+
2d
2d
31

---

Spurious Correlations in High Dimensional Regression
which gives
pip
2 TT
(DD) T +ndl) -1 G- G-Hi --rip-
ZT
(
2
+ ((ip+nA)1) G
2d
2d
2d
TT
T2
22
-1
$ 11.0
MiP
2
+ (1i2p (1²p+n2)1)
E
MiP
2
+
(10p+ I F.
G
2d
2d
2d
ZZ
$ <log d
ZT
HiP
+ (1p' ((p++n)]1)
E
+ (1²p+
G
2d
2d
2d
(154)
< logd
P
1|
1
||Bilog
op Amin ($LD) T)
|G112
2d
f:221
log d
P
Vi
(1d
log d 1 vd
pVp"" p
+
d
p
vd p
-0 log d
d
log'd d Vd
Here, the second step holds with probability at least 2exp (-c2 log d) since is sub-Gaussian and independent from everything else; the fourth step is consequence of Lemma C.I. (152), Lemma C.3, and |G = (vd) (see the argument prior to (142)), and as whole holds with probability - 2 exp (-03 log² d) over Z, G, and V. Note that the second term in the LHS of (154) can be written as
12p =
_T
Tz
(j p
m2) ((pp+n))
G= ===T TT
777 +
2
+ Hip
2d X
1) G
2d
2d
p
= +
= 2T
22p²d
( ())
2d
2 T
(155)
1.:n
{IR(OeR(A);,))
where the second line is due to the classical identity T (AAT +xl) -1 (A A + kI) -1 AT, and the third line uses the definition in (5), with (A) defined in (8) and
2 2d
X =
X.
(156)
17 ppp
Furthermore, the first term of the LHS of (154) satisfies
TT
( p1/4
(al/4 1olgogd (dl/4log d
log d d1/8
pīp
(Φ-T T +nAI)= G FRF((F
- (RF( =
(157)
2d
with probability 1 - log d/ 4p - C1 log d/dl/1 over 7, G. V and z, due to Lemma C.7. Thus, an application of the triangle inequality together with (154), (155) and (157) gives the desired result.
D. Features Composed as 2 x y
In this work, we consider the data to be composed as z = |xT,, y TJ. However, some of the high level results we obtain can be recovered for settings where the features are composed differently. As an example, let us consider the model
z= z x V
g == x=xTo- xT +E.
(158)
Then, according (3), we have
C(θ) Cov
(5 TO,x To²) = 0T E'zz00'
(159)
32

---

Spurious Correlations in High Dimensional Regression
Synthetic
Synthetic
CIFAR-10 (spurious background)
1.50
Cau (8)(A))
1.25
Cous (A))
Eas (Oar(A))
1.00
C/ alAM)
0.6
0.75
C(0xp(AM)
0.4
c(0p=(A)
0.25
0.00
5
10
15 0.0
02
0.4
0.8
0.8
0.2 EtyadeE
Azy)
Antn(S))
Increasing level of whitening
Figure 6. Out-of-distribution test loss L(OLR/RP (A)) (black) and spurious correlations C(OLR/RF (A) (red) a function of Amax (Syy) (first panel) Amin (5%) (second panel) on a Gaussian synthetic dataset, and for CIFAR-10 experiment (third panel). We consider the same set-up as Figures 3 and 4, for Gaussian and CTFAR- 10 data, respectively.
which provides quantity that could be studied again via the analysis in (Han & Xu, 2023). In this new setup, remark that the full data covariance takes the form
E2 Exx + Eyy + Ezy + Egg.
(160)
In a nutshell, we expect the analysis for this setting to provide qualitative behavior similar to that unveiled by the case In fact, the experiments on Color-MNIST (which does not strictly follow the model x = [x" JJT as the color overlaps with the core feature pattern as the model 2 = x + y) suggest that our conclusions hold beyond the setting of "orthogonal features". We further remark that in the setting
2 = =[x [xT.y"] [
[x y " the optimal solution 6 gives C
while this is not necessarily the case in the setting = x + y-
E. Proof of (4): Connection with Let æ and [x .y JT be sampled independently from Px and Pxy respectively. For simplicity, assume that [(O, [ET
Loss
(TT .0)) = [f=[ = 1 and E f(O,, [TT. .v)] = E [ff = 0. Thus, for the quadratic loss, we read-
ily get
-Coww Ey,y -(0)) = 22 [( 1ot ,0) =2 - 2Cov (S(0, [+T fo).
(161)
Denoting with S the covariance matrix of the three random variables f(0, T.T .y)). (3). and f fi(x), we have
P C
== P
(162)
C
1
where introduced the shorthands = Cov (5(O, T ,l),,,,, (0)),(((z)) f2()))
and p Cov (T)) ..)).
Since S is
p.s.d., its determinant has to be non-negative, hence
- p² C 2 0,
(163)
which, when plugged in (161), gives (4).
This bound suggests the close connection between and the out-of disttiibbttnnn test loss. In Figure 6, we repeat the same experiments of Figures 3-4 and report black the out-of-distribution loss. The plots clearly show that C and the out-of-distribution test loss follow similar trend, for both linear regression and random features.
F. Experimental Details
All the plots in the figures report the average over 10 independent trials, with a shaded area describing a confidence interval of standard deviation. For the Gaussian and Color-MNIST datasets, every iteration involves re- re-generating (or re-coloring) the data, while for the CIFAR-10 10 dataset the randomness comes from the model and the training algorithm.
33

---

Spurious Correlations in High Dimensional Regression
width 300, 1 a-a²
width 0.75
Color-MNIST c(x(n(A))
Color-MNIST c(),a(A)
1.0
(( C-MMET
c10me(A)), C-MMST
0.2
0.8
0.3
0.4
0.5
0.2
0.0
0.0
10" 10
10"
10'
10 10
10"
16"
10" 10"
10
A
Figure 7. Test loss C(ONN /LK (A)) (black) and spurious correlations C( (red) as function of X. First and second panel: 2-layer fully connected ReLU network, trained on the multi-class color(C)-MNIST, for two different values a. Thirl and fourth panel: Same setup in Figure 2, for the binary C-MNIST dataset, with multiple values of a.
Synthetic Gaussian data generation. This follows the same model across all the numerical experiments presented in the paper. In particular, we fix d 400 and set Ezz I. Mig diagonal matrix, such that its first entry equals Amax (2iy) and all the other entries equal (d - Amax (Eny)) ) /(d 1). In this way, tr(E) = 2d. Then, we set the off- off-diagonal blocks Eny and yu to the same diagonal matrix, so that
Ezy Eyz (Eny - 31)
(164)
which implies that the Schur complement S 3I and, therefore, Amin (5 = B. To conclude, we set the ground truth 0% e1, i.e., the first element of the canonical basis in Rd. This design choice is motivated by our interest in capturing the role of Amax (May) and to have easy control on the Schur complement S (which is therefore chosen to be proportional to the identity).
Unless differently stated in the figure, n = 2000, Amax (Fwy) = 2, 3 = 0.5, and À = 1. Furthermore, to generate the labels, we add an independent noise with variance o² 0.25, and we subtract this quantity from the test loss, so that the optimal predictor 0* has test loss equal to
RF model, on every dataset, unless differently stated in the figure, use tanh activation function, with p 20000 neurons.
When
Binary color MNIST. This dataset is graphically shown in Figure 1. To generate it, we take subset of the MNIST training dataset (n 1000 samples default, unless differently specified) made only of zeros and ones. Then, for every training image, we color the white portion in blue (red) with probability (1 + n)/2 if the digit is a zero (one), and red (blue) otherwise. For the test set, we proceed in the same way, but setting a = 0, to make the core feature (the digit) effectively independent from the spurious one (the color). For all the experiments, we set
a² = 0.25.
CIFAR-10. For the experiments on CIFAR-10, we implicitly suppose that the middle 22 x square contains the core, predictive feature æ. Thus, we sum to all the channels of the outer region white noise with increasing variance, and we later clamp the pixels to ensure their value between 0 and 1. Increasing the variance of the noise, this progressively makes the outer portion being dominated by random noise, thus reducing its value of Amax (Eyx) / tr(2ng) when estimating the covariance on the perturbed training set. At test time, we take the images from the CIFAR- 10 test set, and we add the same level of noise. To compute C, we create an duitrf-distribution dataset where the core features are randomly permuted across different backgrounds. We always consider the subset of boats and trucks, which contains n = 10000 images.
2-layer neural network. In the experiments shown in Figure 5, we consider a 2-layer neural network trained with gradient descent and quadratic loss on the Color-MNIST and CIFAR-10 datasets. For both datasets, we train for 1000 epochs, with learning rate 0.003, and batch size 1000.
F.1. Additional Experiments
In the left two panels of Figure 7 we consider Color-MNIST including all 10 digits. We train 2-layer network on all classes with one-hot encoding and MSE loss. Odd (even) digits are red (blue) with probability (1 + a)/2, and blue (red) with
34

---

Spurious Correlations in High Dimensional Regression
probability (1 o2/2. To compute at test time we consider the parity of the logit with the highest value, with respect to the color of the image. The first and the second panel correspond to values of a-s and follow similar profile as Figure 5 (left), showing the same qualitative behavior of L and C with respect to À for the full Color-MNIST dataset (i.e., in the multi-class setting). In the third and fourth panel of Figure 7 we repeat the experiment in Figure 2 (right) for multiple and C with respect to À for linear regression. The curves behave as expected: for any value of X, as a decreases, C decreases. Furthermore, the (in-distribution) test loss decreases as a increases, in agreement with our discussion at the end of Section 5.
values of o, reporting L.
NN width = 1000
RF p 20000
In Figure 8 we train a 2-layer network and random feature model the classes "trucks" and "boats" from the Corrupted CIFAR-I6 10 dataset (used in the context of spurious correlations in (Liu et al., 2023)), enforcing correlation in the training set with respectively the tex- tures "brightness" and "glass blur", with a correlation = 0.95. In both panels, we see mild increase in as initially increases, until the later decrease predicted by Proposition 5.1. The profiles also qualitatively similar to the ones of Figure 5 (left).
1.0
C1oudAA), GFAR-10 clêw(Al), CIFAR-10
0.8
cluy (A)),
0.6
0.2
0.0
10"
Figure 8. Test loss [(0Nw/RF (X)) (black) and spurious correlations C(0NN/RP(A) (red) as a function of X. Left: 2-layer fully connected ReLU network, trained the Corrupted CIFAR-10 dataset (boats and trucks, with added textures "brightness" and "glass blur"). Right: RF model with tanh.
35


Reviews:
[{"review_id": "U6QfI3Gr2X", "reviewer": "Reviewer_gx6Q", "summary": "The paper characterizes the learning of spurious features in linear regression as function of $\\ell_2$ regularization strength and spurious feature simplicity. They also show that under overparametrization incurred by random features the effect of regularization is modified in a way that explains empirical results obtained from neural networks. The paper tests these hypotheses on synthetic and semi-synthetic datasets.\n\n## Update after rebuttal\nI thank the authors for their response and maintain my recommendation for acceptance.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive evaluation and helpful comments. We address concerns below.\n\n---\n\n**Improving experimentation**:\n\nFollowing the reviewer’s suggestion, we will add the following experiments to the revision.\n\nIn https://ibb.co/21W8qbLJ, we consider Color-MNIST including all digits (rather than a subset). We train a 2-layer network on all classes with one-hot encoding and MSE loss. Odd (even) digits are red (blue) with probability $(1+\\alpha)/2$, and blue (red) with probability \n$(1-\\alpha)/2$. To compute $\\mathcal C$, at test time we consider the parity of the logit with the highest value, with respect to the color of the image. The two figures correspond to two values of $\\alpha$-s and follow a similar profile as Figure 5 (left), showing the same qualitative behaviour of $\\mathcal L$ and $\\mathcal C$ with respect to $\\lambda$ for the full Color-MNIST dataset (i.e., in the multi-class setting).\n\nIn https://ibb.co/zWKBHk5k, we repeat the experiment in Figure 2 (right) for multiple values of $\\alpha$, reporting $\\mathcal L$ and $\\mathcal C$ with respect to $\\lambda$ for linear regression. The curves behave as expected: for any value of $\\lambda$, as $\\alpha$ decreases, $\\mathcal C$ decreases. Furthermore, the (in-distribution) test loss decreases as $\\alpha$ increases, in agreement with our discussion at lines 347-350 (left).\n\n\nWe note that the choice of considering a data split in predictive and spurious features is conceptually similar to Section 5.1 of “Invariant risk minimization” by Arjovsky et al. As for our CIFAR-10 implementation, our experiment is designed to verify our claims on the simplicity bias in a controllable setting. In fact, introducing a tunable amount of noise allows us to modify $\\lambda_{\\max}(\\Sigma_{yy})$ and use it as an independent variable in Figure 4. Nevertheless, considering image backgrounds as spurious features was done in the seminal cited work by Xiao&al.2020. Besides, the theoretical results suggesting that higher values of the regularizer $\\lambda$ can be associated with higher values of $\\mathcal C$ are also supported by the numerical evidence in Table 1 of Sagawa2020a. \n\n\nWe thank the reviewer for mentioning the Corrupted CIFAR-10 dataset considered e.g. in “Avoiding spurious correlations via logit correction” by Liu et al. In https://ibb.co/TBg7Khwn, we train a 2-layer network and a random feature model on the classes ‘trucks’ and 'boats’, enforcing a correlation in the training set with respectively the textures ‘brightness’ and ‘glass_blur’, as in the available data for C-CIFAR-10 (here we use correlation $\\alpha = 0.95$). In both figures, we see a mild increase in $\\mathcal C$ as $\\lambda$ initially increases, until the later decrease predicted by Proposition 5.1. The profiles are also qualitatively similar to the ones of Figure 5 (left).\n\n---\n\n**More discussion in light of literature**:\n\nThe main difference with (Qiu et al., 2024; Pezeshki et al., 2011) is that these works mainly focus on how spurious correlations evolve during training, while our work studies spurious correlations at convergence. \n\nTo further connect with (Qiu et al., 2024; Pezeshki et al., 2011), we briefly discuss the intuition coming from our results from a dynamical perspective. In Section 5, we argue that $\\lambda_{\\max}(\\Sigma_{yy})$ is related to $\\mathcal C$, suggesting a measure of the simplicity of the feature $y$. In linear regression, solving gradient flow ($d \\theta = - \\nabla_\\theta \\mathcal L(\\theta)dt$) gives\n\n\n$$\\theta(t) = (1 - e^{ - (X^\\top X + n \\lambda I ) t}) \\hat \\theta.$$\n\n\nThus, the components of $\\hat \\theta$ aligned with the top eigenspaces of $X^\\top X$ converge earlier than the others. Hence, if $X^\\top X \\sim n \\Sigma$, it is natural to expect that spurious features are learned faster the easier they are, and that they would prevail with respect to the core features (according to our bound in Proposition 5.1).\n\n\n---\n\n**Other comments/suggestions**:\n\nWe thank the reviewer for the detailed comments, which will improve the clarity of the revision: \n\n- We will explicitly note that the test loss is in distribution after Equation (2).\n- We will clarify the usage of the notation $\\lambda$, as well as of $y$ to denote spurious features and $g$ to denote labels.\n- We will fix the typo in line 34L.\n- We will add the suggested remark before Theorem 4.3.\n- We will discuss the difference between the two different scaling regimes considered in Theorem 4.3 and Proposition 4.2.", "claims_and_evidence": "The authors support their claim of characterizing learning in linear regression under spurious correlations theoretically in a convincing manner, with some additional empirical support.", "methods_and_evaluation_criteria": "This is the weakest part of the paper, since the paper does not evaluate its predictions on any real bona fide regression task, but rather repurposes two classification tasks for this.", "theoretical_claims": "I have checked the proofs of Proposition 4.2 and Theorem 4.3, and did not see any problems.", "experimental_designs_or_analyses": "In addition to not using a original high-dimensional regression task, the authors' use of Colored MNIST and CIFAR-10 tasks diverge from the way they are commonly used, without explicit justification (and previous uses are not cited, . For binary Colored MNIST dataset the authors only work with a subset of the dataset, and experiment only with a single value of correlation between core and spurious features. They also create a spurious correlation dataset out of CIFAR-10, without referencing or reusing a very common variant of CIFAR-10 that's frequently used in the literature called Corrupted CIFAR-10.", "relation_to_broader_scientific_literature": "The paper is positioned appropriately within the relevant literature, and the paper's motivations are clearly presented. However, I would appreciate a more involved discussion of their results in relation the existing results in the literature, especially the implications of their work regarding feature learning order and interference between features based on difficulty and spurious correlation strength (c.f. Pezeshki et al. 2021, Qiu et al. 2024)", "essential_references_not_discussed": "I am not aware of any major, relevant papers that the current paper fails to cite.", "other_strengths_and_weaknesses": "The paper sets out a clear motivation and proceeds to systematically demonstrate its claims, supported by the fact that the paper is well-written, making the authors' arguments easier to follow.", "other_comments_or_suggestions": "- Given the fact that \"test loss\" can often refer to loss under an unbiased test distribution (i.e. OOD risk) when studying spurious correlations, the authors should take care to remind the reader that their test loss is ID. The difference between the two can be reinforced by assigning a designated notation for OOD test loss.\n- Overloading of $\\lambda$ for eigenvalues and regularization coefficient is somewhat confusing, please change the notation for one if possible.\n- Use of $y$ to denote spurious features and $g$ to denote labels creates an unnecessary cognitive load since it directly contradicts common usage in the previous work. I would recommend using $s$ and $y$ respectively, but ultimately it's in authors' discretion.\n- 034L: \"Gaussian dataset\" -> \"synthetic Gaussian dataset\"?\n- Theorem 4.3: Please alert the reader _beforehand_ that they are not supposed to have an intuition re. $\\mathcal{C}^{\\Sigma}(\\lambda)$, and that this property will be studied in the following section. Otherwise Theorem 4.3 is needlessly confusing to digest in the first read.\n- Please explicitly mention and discuss the implications of the fact that Proposition 4.2 and Theorem 4.3 have different assumptions regarding the data and sample dimensionality relationship.", "questions_for_authors": "Not a question per se, but to summarize my points above: Improving experimentation (see above) and a more in-depth discussion of the results in light of literature would improve the paper the most.", "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": "NYkWfruIXd", "reviewer": "Reviewer_8UVc", "summary": "This paper investigates spurious correlations in high-dimensional regression, focusing on the effects of regularization, simplicity bias, and over-parameterization. Using linear regression, the study quantifies how regularization influences the reliance on spurious correlations, revealing a trade-off where increasing regularization reduces test loss but strengthens spurious dependencies. It also demonstrates that models exhibit simplicity bias, favoring spurious features with dominant eigenvalues in their covariance structure, as these features offer an easier shortcut for prediction. The analysis introduces a formal measure of spurious correlations and links it to data covariance properties, particularly through the Schur complement, which captures the statistical dependence between core and spurious features.\n\nTo examine over-parameterization, the paper extends its analysis to random feature regression, showing that such models behave like regularized linear regression, even in the absence of explicit regularization. This result explains why spurious correlations persist in over-parameterized models, as the implicit regularization effect does not eliminate them. Theoretical results are complemented by numerical experiments on Gaussian synthetic data, Color-MNIST, and CIFAR-10, validating the key claims. The findings provide a rigorous statistical foundation for understanding spurious correlations and their interaction with model complexity, offering insights that can inform mitigation strategies for improving robustness and fairness in machine learning.\n\n## Update after rebuttal\nThank you for the detailed rebuttal and thoughtful clarifications. I acknowledge the authors' responses and appreciate the effort in addressing the distinctions with related work, the discussion of applicability to deep networks, and the consideration of potential extensions. After reviewing the rebuttal, I will keep my original score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments and the several interesting suggestions for extensions. We answer questions and address concerns below. We will incorporate the discussions in the revision.\n\n---\n\n**Comparison with (Bombari et al., 2024):**\n\nOur work concerns the problem of spurious correlations, where a trained model is tested on a **newly sampled** data-point independent from training data, and we crucially use the independence between $\\tilde x$, $x$, $y$ and $\\hat \\theta$ (see Proposition 4.2 and Theorem 4.3). In contrast, **(Bombari et al., 2024) do not consider the problem of spurious correlations**, but rather the setting where spurious features in the training set are memorized by an over-parameterized model. This is discussed in the first paragraph of their introduction, and it is quantitatively apparent in their definition of memorization in Equation (3.7), where the covariance is computed comparing the trained model evaluated on a spurious feature **contained in the training set** $y_i$ and the corresponding label $g_i$.\n\nIn other words, the setting of our work is related to **robustness to distribution shift**, while (Bombari et al., 2024) focus on a setting where the individual training data are **memorized**, raising potential **privacy concerns**. Thus, the two works look at qualitatively very different problems. \n\nThis difference is reflected in the proof strategies. While our work shares with (Bombari et al., 2024) an approach based on concentration of measure (and, consequently, also technical lemmas), the proof techniques are fundamentally different. Our work relies on the characterization of the ridge estimator $\\hat \\theta$ provided by Han&Xu2023 for linear regression, and it transfers the insights to random features via a point-wise equivalence principle. In contrast, the argument of (Bombari et al., 2024) is based on showing concentration of the auxiliary quantity $\\mathcal F(z_i^s, z_i)$ that serves as a proxy to characterize the amount of memorization for an individual sample.\n\n---\n\n**Setting might not capture the behaviour of deep neural networks**:\n\nWhile it is true that our analysis covers only high-dimensional regression, Figure 5 (left) shows a degree of similarity for shallow networks. For more complex and deep models, we point to the empirical results in Sagawa&al.2020, where higher penalty terms are shown to decrease test accuracy on ResNet50 and Bert. While it is hard to provide an exact predictive theory for deep models, we do believe our approach to capture important statistical aspects of the phenomenon of spurious correlations in more general settings than the one we precisely study.\n\n---\n\n**Extension to feature learning**:\n\nFollowing Ba&al.2022 and Moniri&al.2023, one could extend our results to the setting where the target is not a linear function of the inputs and one step of gradient descent on the feature map improves the representation. We also note that our experiments with neural networks show concordance in the qualitative behavior of high-dimensional regression and 2-layer networks with both layers being trained.\n\n---\n\n**Heavy tailed data**:\n\nThe recent work by Adomaityte&al.2024 (“High-dimensional robust regression under heavy-tailed data: asymptotics and universality”) considers heavy tailed data in high-dimensional regression: the covariates are isotropic Gaussian with variance sampled from a distribution with heavy tails. Note that our problem setup requires a non-isotropic covariance, so one would have to first generalize their analysis accordingly. Then, a possible direction would be to investigate how different tail weights (between core and spurious features) favor learning of spurious correlations. \n\n---\n\n**Different training objectives**:\n\nEmpirically, the identified trade-off between regularization and spurious correlations has been verified in prior work (Sagawa&al.2020) looking at models trained on classification tasks.\n\nTheoretically, work by Montanari&al.2023 (“The generalization error of max-margin linear classifiers”) and Deng&al.2020 (“A model of double descent for high-dimensional binary linear classification”) provides the asymptotics for the generalization error of max-margin linear classifiers, also in the setting where classification is performed on a set of random features. For classification, we could define $\\mathcal C$ as in our Equation (3), taking the $\\text{sign}$ of the output of the model (which for classification represents the prediction of the model at test time).  \n\nEquation (5.6) in Montanari&al.2023 provides a set of fixed point equations giving the limit deterministic value of the maximum margin and the prediction error (see their Theorem 3), also for non-isotropic covariates. Then, to extend our results to this setting, one approach could be to follow the strategy as in part c) of the proof technique in their Section 5.3, with the difference of computing $\\mathcal C$ instead of the generalization error.", "claims_and_evidence": "The claims in the submission are largely supported by rigorous theoretical analysis and numerical experiments, making the evidence clear and convincing in most cases. The authors derive precise mathematical characterizations of spurious correlations, leveraging results from high-dimensional statistics, regularized linear regression, and random feature models. Their theoretical findings, such as the trade-off between regularization and spurious correlations and the equivalence between over-parameterized models and regularized regression, are well-grounded in established techniques. Additionally, the numerical experiments on Gaussian synthetic data, Color-MNIST, and CIFAR-10 align with the theoretical results, further strengthening their validity.", "methods_and_evaluation_criteria": "Yes, they are reasonable. The paper employs linear regression and random feature models, which are well-suited for studying spurious correlations in high-dimensional settings. The evaluation is based on both theoretical analysis and numerical experiments, using Gaussian synthetic data, Color-MNIST, and CIFAR-10, which are appropriate for validating the claims. While the analysis focuses on simplified models, the chosen methods effectively capture the core statistical phenomena under investigation.", "theoretical_claims": "Skimmed through it; they look sound at a high level. The proofs follow standard techniques in high-dimensional statistics, leveraging tools like Schur complements, concentration inequalities, and random matrix theory. Key results, such as the trade-off between regularization and spurious correlations and the equivalence between random feature models and regularized regression, appear well-structured and logically derived. A more detailed verification would be needed to confirm full correctness, but no obvious issues stand out.", "experimental_designs_or_analyses": "They look sound at a high level. The experiments on Gaussian synthetic data, Color-MNIST, and CIFAR-10 align well with the theoretical claims, providing empirical validation for key results. The analyses appear thorough, with appropriate comparisons and visualizations. While the study focuses on relatively simple models, the chosen datasets and methodologies effectively illustrate the impact of regularization, simplicity bias, and over-parameterization on spurious correlations.", "relation_to_broader_scientific_literature": "The key contribution is quantifying the amount of spurious correlations learned in high-dimensional regression with respect to regularization, simplicity bias, and over-parameterization. This builds on prior work in machine learning robustness, generalization in over-parameterized models, and implicit bias in deep learning, extending these ideas with a rigorous statistical characterization. The study connects to research on shortcut learning, generalization in empirical risk minimization (ERM), and random feature models, providing a more precise understanding of how spurious correlations emerge and persist. By linking these phenomena to covariance structures and regularization effects, the paper contributes valuable insights to ongoing discussions on fairness, bias mitigation, and model interpretability in modern machine learning.", "essential_references_not_discussed": "Yes, the following work is not cited and discussed while it also studies a similar setting. Furthermore, the paper significantly relates to other papers of Bombari et al. Even many of the proofs (e.g., see Lemma C.3-C.5) rely on the mentioned papers. There should be a more apparent discussion of how the current work is distinguished from the mentioned work.\n\n> Bombari et al., 2024: \"How Spurious Features are Memorized: Precise Analysis for Random and NTK Features\"\n\n—This work also investigates the role of spurious correlations in over-parameterized models, particularly focusing on random features and Neural Tangent Kernel (NTK) models. Given the conceptual overlap and shared proof techniques, the current paper should clarify how its contributions extend or differ from Bombari et al.'s findings.", "other_strengths_and_weaknesses": "Strengths\n1. The paper is well-written and easy to follow, presenting complex statistical concepts in a clear and structured manner.  \n2. By characterizing a deterministic object $\\( \\mathcal{C}^\\Sigma(\\lambda) \\)$ to quantify spurious correlations, the paper provides a rigorous analysis of how regularization strength $\\( \\lambda \\)$, data covariance $\\( \\Sigma \\)$, and over-parameterization influence the learning of spurious features.  \n\nWeaknesses\n1. The analysis primarily focuses on linear regression and random feature regression, making the setting simplistic and potentially limited in capturing the behavior of more complex models like deep neural networks.  \n2. The paper lacks a detailed comparison with prior work by Bombari et al., making it difficult to fully assess its technical contributions and novel challenges addressed. A clearer distinction from existing literature would strengthen the paper’s positioning.", "other_comments_or_suggestions": "-", "questions_for_authors": "- Is it possible to extend the current findings to settings with feature learning (e.g., two-layer neural networks with both layers trained) rather than using fixed random features? Would the implicit bias of gradient-based optimization affect the spurious correlation analysis?\n\n- Can the analysis be extended beyond the given data assumptions? Many real-world datasets exhibit heavy-tailed or structured dependencies—how would this impact the theoretical guarantees?\n\n- How does this work differ fundamentally from Bombari et al. (2024)? Several proofs (e.g., Lemmas C.3–C.5) rely on techniques from Bombari et al., but a direct comparison is missing. Could you clarify the key distinctions and novel contributions?\n\n- Does the identified trade-off between regularization and spurious correlations hold across different training objectives?", "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": "mpPVyKoPvX", "reviewer": "Reviewer_BGwm", "summary": "This paper quantifies the notion of spurious correlations -- where the feature of an image which determines it's classification correlates with another feature which does not determine the label -- and sudies the effect of spurious correlations for linear ridge regression and random-feature ridge regression.  Precisely, they define spurious correlations as the covariance between the spurious feature and the label when the informative feature is sampled independently.  They first demonstrate that with enough training data and zero ridge, the spurious correlations learned by a linear regression model will become small.  Increasing the ridge parameter, they observe that spurious correlations can improve test error when sampling in-distribution, and a proof is provided in the special case of isotropic covariance for the informative feature.  They then study spurious correlations in an over-parameterized random feature model.  By proving that the random feature model converges to a linear model with an increased ridge parameter, they show that spurious correlations are larger, but similar in their behavior, for random-feature models.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for recognizing the rigor, clarity and importance of our results. We address concerns below.\n\n---\n\n**Joint requirements $p = \\omega(n)$ and $\\log p = \\Theta(\\log n)$**:\n\nWe note that the regime $p = \\omega(n)$ and $\\log p = \\Theta(\\log n)$ formally includes all scalings where $p \\sim n^q$ for q > 1, as the latter is equivalent to $\\log p = q \\log n$. Thus, our assumptions include the faster scalings mentioned in the **claims and evidence** section of the review.\n\nIn case the reviewer referred to a polynomial regime also between $d$ and $n$ (if $n = \\Omega(d^l)$, with $l \\geq 2$, the RF model learns more than the linear component of the target as indicated in Hu&al.2024 – the paper referenced by the reviewer), it is indeed true that the higher order component of the features would behave qualitatively differently, making the RF model qualitatively different from a regularized linear regression. We have opted to focus on the proportional regime $n = \\Theta(d)$ due to its popularity in the literature (see e.g. Mei&Montanari2020, Hastie&al.2020) and due to its closeness to standard datasets in deep learning.\n\n---\n\n**Relation to work on linear regression with (possibly) noisy feature maps**:\n\nWe thank the reviewer for bringing to our attention the paper by Loureiro et al. (\"Learning curves of generic features maps for realistic datasets with a teacher-student model\"), which has indeed a similar setting to ours. Using the notation $z = [x, y]$ as in our paper, they consider a teacher-student setting where the labels are defined as a function of the feature $x$ (see their Eq. (1.2)), while the estimator $\\hat \\theta$ is obtained via ERM using only the (correlated) features $y$ (see their Eq. (1.3)). Then, their work is focused on studying the training and generalization error of the model that has access only to the partial information. Our setting, instead, looks at the ERM on both features, where the model has direct access also to the core features $x$. Due to the similarity with their setting, we will mention this related work and remark the differences in the revision of the paper.\n\n---\n\n**Setting where $z = x + y$ instead of $z = [x, y]$**:\n\nWe thank the reviewer for the insightful comment. Let us consider the model\n\n$$z = x + y, g = x^\\top \\theta^* + \\varepsilon.$$\n\nThen, we have\n\n$$\\mathcal C = \\text{Cov} \\left( (\\tilde x + y)^\\top \\hat \\theta, x^\\top \\theta^* \\right) = \\hat \\theta^\\top \\Sigma_{yx} \\theta^*,$$\n\nand this quantity could be studied via the analysis in Han&Xu2023 as in our current setting, considering that the covariance of the data will take the form\n\n$$\\Sigma_{zz} = \\Sigma_{xx} + \\Sigma_{yy} + \\Sigma_{xy} + \\Sigma_{yx}.$$\n\nIn a nutshell, we expect the analysis for this setting to provide a qualitative behaviour similar to that unveiled in the current version of our work. In fact, the experiments on Color-MNIST (which does not strictly follow the model $z = [x, y]$, as the color overlaps with the core feature pattern as in the model $z = x + y$) suggest that our conclusions hold beyond the setting of orthogonal features. We remark that in the setting $z = [x, y]$ the optimal solution $\\hat \\theta = \\theta^*$ gives $\\mathcal C = 0$, while this is not necessarily the case in the setting $z = x + y$. \n\nWe will add a discussion on this point in the revision.", "claims_and_evidence": "The claims made in this paper regarding spurious correlations in linear regression are well-supported by theoretical proofs and numerical experiments.  The claim I take issue with is the claim that over-parameterization increases spurious correlations.  This is because the scaling limit used to study the random feature model here is very limited.  The joint requirements that $p = \\omega (n \\log^4(n))$ and $\\log(p) = \\Theta (\\log n)$ restrict the scaling to a very narrow regime where p grows only slightly faster than linearly with n.  This can also be recovered effectively by taking the proportional limit $p, n  \\to \\Infinity$ with $p/n = \\gamma$ and then taking the limit $\\gamma \\to \\infty$,  This second limit will destroy the variance induced by the random projection to a set of random features, which might have interesting effects on the spurious correlations learned.  In this limit, the higher-order Hermite coefficients of the nonlinearity (captured by $\\tilde{\\mu}$) have an identical effect as random i.i.d. noise applied to the features would have.  This additional contribution doesn't really interact with the structure of the data in a meaningful way\n\nAlso, in other scaling limits, such as $p \\sim n^q$ as studied by Lu et. al in (https://arxiv.org/abs/2403.08160), the learning curves no longer reduce to the linear case with a renormalized ridge parameter.  To fully answer the question of how overparameterization affects spurious correlations, these faster scaling limits would need to be examined.", "methods_and_evaluation_criteria": "yes", "theoretical_claims": "I did not check the proofs, but the results are reasonable and consistent with the existing literature.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "Spurious correlations are a universal problem in machine learning.  Thus, this relates broadly to the scientific literature on machine learning.  The technical contributions in this paper are also closely related to recent work on deterministic equivalents and random matrix methods for linear and random feature regression models.", "essential_references_not_discussed": "Random feature models beyond the proportional regime: https://arxiv.org/abs/2403.08160\n\nThese results also relate to work on linear regression with (possibly) noisy feature maps.  See, for example,\nhttps://arxiv.org/abs/2102.08127", "other_strengths_and_weaknesses": "Strengths: Rigor, clarity of exposition, addresses an important, universal problem in the \n\nWeakness: The main weakness is the novelty of the results. All follow from known estimates of the in-distribution and out-of-distribution prediction error for the proportional limit of linear and random feature models, except for some additional pointwise concentration guarantees in a narrow scaling regime.", "other_comments_or_suggestions": "none", "questions_for_authors": "Is it necessarily correct to assume that the informative feature and spurious feature live in orthogonal subspaces of the input space?  How would your results change if instead of setting z = [x, y], you set z = x + y?", "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": "V5wajh7XZA", "reviewer": "Reviewer_mVaN", "summary": "This submission investigates the extent to which spurious correlations are used for learning in two models, linear ridge regression and random feature models, under the setting that the input dimension grows proportionally with the sample size. The key definition is $\\mathcal{C}(\\hat{\\theta})$ in (3), and for $\\hat{\\theta}$ with and without regularisation, its non-asymptotic concentration results are proven (Theorems 4.1, 4.2). Section 5 is dedicated to investigating the role of regularisation in the behaviour of the above quantity and the test loss, and Section 6 is dedicated to showing an asymptotic similarity of random feature models with regularised linear ridge regression with a specific regularisation parameter.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the remarkable care in reviewing our work and for the positive evaluation. We address concerns below.\n\n---\n\n**Lack of clarity when citing (Han&Xu2023)**:\n\nTo address this and ease the comparison of our claims with the results in Han&Xu2023, we will add to the appendix a discussion about the notation in the proof of Theorem 4.3. Specifically, we will connect our definition of the Gaussian sequence model $\\hat\\theta^\\rho$ with the definition in Equation (1.5) in Han&Xu2023, and our definition for the test function $\\varphi$ (see our line 693) with their notation ($\\textup{g}$) in their Theorem 2.3.\n\n---\n\n**Other Comments**:\n\n- 102R, 146L, 136R: Thanks for pointing these typos out, we will fix them in the revision.\n\n- 242L: While, in general, the conditional covariance depends on the particular value of $\\bar x$, the definition of the Schur complement of the matrix $\\Sigma$ does not rely on any specific instance of the random variable $x$. In the multivariate Gaussian case, it turns out that the conditional covariance is also independent of the particular instance $\\bar x$, but we opted for leaving this notation at first as we did not consider it a trivial fact. If the reviewer finds this confusing, we are happy to remove this notation in the revision.\n\n- The arguments of $f(\\theta, x)$ are sometimes swapped: Thanks for spotting this, we will fix it.\n\n- 625, 677, 683, 688: Thanks for pointing out these typos, we will fix them in the revision.\n\n- 647: Thanks for noticing this. While it is true that the notation of $P_y$ also appears in the body in line 188R, in line 647 we are providing the proof for a statement prior to that part, and we opted for redundancy to avoid confusion.\n\n- 690: Thanks for spotting this typo. Also, when we write that $\\mathcal C(\\cdot)$ is $\\|| \\Sigma \\|| _{op}$-Lipschitz, we mean that the Lipschitz constant of $\\mathcal C(\\cdot)$ is upper bounded by the value of $\\|| \\Sigma \\|| _{op}$. If the reviewer finds this notation confusing, we can elaborate more on this statement in the revision of the work.\n \n- Hastie&al.2022: thanks for noticing the typo, we will fix it in the revision.\n\n---\n\n**Questions for Authors**:\n\n- 146L: We thank the reviewer for pointing this out. While the implication holds for Gaussian distributions, in 146L we still did not state Assumption 4.1 and the wording at this point could be misleading. We will fix it in the revision.\n\n- 662: We thank the reviewer for the question. Let us consider the inequality taken from the wikipedia page on Weyl’s inequality: \n$$ \\lambda_{i+j-1}(A+B) \\leq \\lambda_{i}(A) + \\lambda_{j}(B),$$ \nwhere $A$ and $B$ are two $d \\times d$ symmetric matrices and $\\lambda_{j}(\\cdot)$ denotes the $j$-th largest eigenvalue. Then, one could set $A = n \\Sigma - Z^\\top Z$ and $B = Z^\\top Z$. Taking $i = 1$ and $j = d$ gives our Equation (32).\n\n- 206R: We thank the reviewer for pointing this out. Indeed the sentence might lead to confusing interpretations. We propose to rephrase it as: “Thus, for large $d, n$, we can theoretically analyze $\\mathcal C(\\hat \\theta_{\\textup{LR}}(\\lambda))$ via the deterministic quantity $\\mathcal C^\\Sigma(\\lambda)$, which, as highlighted by Equation (12), depends on $\\theta^*$, the covariance of the data $\\Sigma$, and the regularization $\\lambda$ via the parameter $\\tau(\\lambda)$ introduced in (13).”", "claims_and_evidence": "The claims are supported by proofs in the Appendix and experiments. The experiments are well-aligned with the claims, and even though I couldn't go through all of the proofs, I couldn't find any errors. I had a question in one of the proofs, and it is written in the \"Questions for Authors\" section, and I would be grateful if the authors could answer it.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I checked the proofs of Theorems in Section 4, and some in Section 5. I couldn't find any errors. The only problem was that some proofs were very hard to follow, as they refer to (Han and Xu, 2023) without citing any of their notations and results, and I had to spend a lot of time looking into that paper, because the results are in that paper are not how it is used in the proofs here. I think it would be better if the authors cited the results precisely, stating precisely what simplifications were made. \n\nSome minor comments are listed in the \"Other Comments or Suggestions\" section.", "experimental_designs_or_analyses": "The experiments look good.", "relation_to_broader_scientific_literature": "The related literature is discussed. This paper takes a slightly different aim at the problem of spurious correlations, in that the previous works seem to have focused on how to mitigate this problem, but this paper aims to characterise the extent of learning from spurious correlations and what role the regularisation parameter plays. Compared to what I imagine approaches like data augmentation does, which should not be model-specific, the results in this paper are specific for linear regression.", "essential_references_not_discussed": "Not anything that I know of!", "other_strengths_and_weaknesses": "The paper was a pleasure to read - very well written (except some minor comments listed in the next section). I loved the fact that after every result, there was a paragraph starting with \"In words\", explaining clearly the significance of the result.", "other_comments_or_suggestions": "102R: \"is independently\" -> \"is independent\" or \"is chosen independently\"\n\n146L: \"conditional to\" -> \"conditional on\"\n\n136R: \"it can connected\" -> \"it can be connected\"\n\n242L: In (16), I don't think there is any need for bars, I think $S^\\Sigma_x=\\text{Cov}(y\\mid x)=E_{y|x}[(y-E_{y|x}[y])(y-E_{y|x}[y])^\\top]$ suffices. If you insist on using $\\bar{x}$ to denote a particular value of the variable $x$, then I think it should also be $S^\\Sigma_{\\bar{x}}$ on the left-hand side. \n\nIn Section 3, in $f(\\theta,z)$, the parameter $\\theta$ comes before the input $z$, but in Section 6, this is reversed. Moreover, in Section 4, $f(\\theta)$ is used without the input argument. I think it would be good to make this consistent, and even when the input argument is not explicitly present, write $f(\\theta,\\cdot)$. \n\n625: $\\epsilon$ should be $\\mathcal{E}$. \n\n188R: The projection operator $P_y$ is introduced here and again on 647. Perhaps redundant?\n\n677: Full stop missing in (35). \n\n683: In (36), in going from the second line to the third, $x^\\top\\theta^*_x$ turns into $[x^\\top,\\mathbf{0}^\\top]^\\top\\theta^*$, but the second transpose shouldn't be there, it should be $[x^\\top,\\mathbf{0}^\\top]\\theta^*$. \n\n688: \"independent with\" -> \"independent from\" \n\n690: $\\lVert\\theta^*\\rVert_2\\leq1$ is not in Assumption 4.1, but on 166L. Also, you probably don't mean $\\lVert\\Sigma\\rVert_\\text{op}$-Lipschitz, but that you have $\\lVert\\mathcal{C}(\\cdot)\\rVert_\\text{op}\\leq\\lVert\\Sigma\\rVert_\\text{op}$? Slightly strange to talk about Lipschitz continuity of linear maps, as they are always Lipschitz continuous. \n\n[Hastie et al., 2019] should be [Hastie et al., 2022].", "questions_for_authors": "146L: Covariance being zero does not imply independence either. Perhaps better to replace \"as the covariance between $y_i$ and $x_i$ is in general non-zero\" to \"as $y_i$ and $x_i$ are in general not independent\"?\n\n662: In (32), could you please cite which exact form of Weyl's inequality you used, and how? I tried to derive (32) from the basic form of Weyl's inequality on wikipedia but I couldn't immediately get there. \n\n206R: This sentence sounds strange, as it says it will \"estimate\" the empirical value by the \"true\" value, although I think I see what the authors mean, as the quantity of interest is actually $\\mathcal{C}(\\hat{\\theta}_\\text{LR}(\\lambda))$, the amount of spurious correlation learned by the trained model $\\hat{\\theta}$. Still, I don't think it's the right choice of words, especially because we do not have access to the true value $\\mathcal{C}^\\Sigma(\\lambda)$.", "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:

Meta-review: This work characterizes the effect of spurious features in high-dimensional ridge-regularized linear regression, evaluated by the covariance between the target value and the predicted score on an altered feature vector with the core features replaced with independent copies. This spurious covariance attains zero in the ridge-less case, and has a non-trivial value with regularization. The analysis reveals an interesting regime where the spurious covariance increases and the test error decreases, as the regularization strength varies. An asymptotic equivalence is established between ridge-regularized linear regression and overparametrized random feature models, allowing for an alternative interpretation of the analysis with respect to overparametrization. 

The analysis is well-motivated and clearly presented, revealing interesting theoretical consequences supported by empirical results. The authors’ rebuttal effectively addressed the reviewers’ comments concerning the discussion with respect to related work, the implication of the theoretical result, and the experimentation, which is strengthened with added experiments. A weak point raised in the reviews is the technical novelty, as the analysis build upon the existing sharp results of linear regression, but with a different focus on the quantification of spurious correlation.
Decision: Accept (poster)