Overparameterization Improves Robustness to Covariate Shift in High Dimensions
Year: 2022

Abstract:
A significant obstacle in the development of robust machine learning models is covariate shift, a form of distribution shift that occurs when the input distributions of the training and test sets differ while the conditional label distributions remain the same. Despite the prevalence of covariate shift in real-world applications, a theoretical understanding in the context of modern machine learning has remained lacking. In this work, we examine the exact high-dimensional asymptotics of random feature regression under covariate shift and present a precise characterization of the limiting test error, bias, and variance in this setting. Our results motivate a natural partial order over covariate shifts that provides a sufficient condition for determining when the shift will harm (or even help) test performance. We find that overparameterized models exhibit enhanced robustness to covariate shift, providing one of the first theoretical explanations for this ubiquitous empirical phenomenon. Additionally, our analysis reveals an exact linear relationship between the in-distribution and out-of-distribution generalization performance, offering an explanation for this surprising recent observation.

heading: 1 Introduction
text: Theoretical justification for almost all machine learning methods relies upon the equality of the distributions from which the training and test data are drawn. Nevertheless, in many real-world applications, this equality is violated—naturally-occurring distribution shift between the training data and the data encountered during deployment is the rule, not the exception [31]. Even non-adversarial changes in distributions can uncover the surprising fragility of modern machine learning models [55, 56, 43, 26, 12, 50]. Such shifts are distinct from adversarial examples, which require explicit poisoning attacks [22]; rather, they can result from mild corruptions, ranging from changes of camera angle or blur [26], to subtle, unintended changes in data acquisition procedures [56]. Moreover, this fragility limits the application of deep learning in certain safety-critical areas [31].
Empirical studies of distribution shift have observed several intriguing phenomena, including linear trends between model performance on shifted and unshifted test distributions [56, 26, 31], dramatic degradation in calibration [50], and surprising spurious inductive biases [12]. Theoretical understanding of why such patterns occur across a variety of real-world domains is scant. Even basic questions such as what makes a certain distribution shift likely to hurt (or help) a model’s performance,
⇤Equal contribution. †Work performed while the author was at Google.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
and by how much, are not understood. One reason that these phenomena have eluded theoretical understanding is that there is often a strong coupling between model and distribution, implying that the effect of a given shift cannot usually be understood in a model-agnostic way. Another reason that satisfactory explanations have remained lacking is that the go-to formalism for studying generalization in classical models, namely uniform convergence theory (see e.g. [66]), may be insufficient to explain the behavior of modern deep learning methods (even in the absence of distribution shift) [47, 68]. Indeed, classical measures of model complexity, such as various norms of the parameters, have been found to lead to ambiguous conclusions [49].
In this paper, we follow a different approach: instead of focusing on worst-case bounds for generic distributions, we study average-case behavior for narrowly specified distributions. While this change in perspective sacrifices generality, it allows us to derive more precise predictions, which we believe are necessary to fully capture the relevant phenomenology. We study a specific type of distribution shift called covariate shift, in which the distributions of the training and test covariates differ, while the conditional distribution of the labels given the covariates remains fixed. Using random matrix theory, we perform an asymptotically exact computation of the generalization error of random feature regression under covariate shift. The random feature model provides a useful testbed to (1) investigate the interplay between various factors such as model complexity, label noise, bias, variance, and covariate shift; (2) rigorously define a model-agnostic notion for the strength of covariate shift; and (3) provide a theoretical explanation for the linear relationships recently observed between in-distribution and out-of-distribution generalization performance [55, 56, 27].

heading: 1.1 Contributions
text: Our primary contributions are to:
1. Provide a model-agnostic partial order over covariate shifts that is sufficient to determine when a shift will increase or decrease the test error in random feature regression (see Def. 4.1);
2. Compute the test error, bias, and variance of random feature regression for general multivariate Gaussian covariates under covariate shift in the high-dimensional limit (see Sec. 5.1);
3. Prove that overparameterization enhances robustness to covariate shift, and that the error, bias, and variance are nonincreasing functions of the number of excess parameters (see Sec. 5.3);
4. Deduce an exact linear relationship between in-distribution and out-of-distribution generalization performance, offering an explanation for this surprising recent empirical observation (see Sec. 5.4).

heading: 1.2 Related work
text: There is extensive literature on the empirical analysis of distribution shift in all of its myriad forms, ranging from domain adaptation [62, 20, 8, 70, 69, 37, 36] to defenses against adversarial attacks [39, 60] to distributionally robust optimization [59, 15, 16], among many others. Interestingly, for naturally occurring distribution shifts [31, 26], standard robustness interventions provide little protection [56, 63]. Indeed, empirical risk minimization on clean, unshifted training data often performs better on out-of-distribution benchmarks than more sophisticated methods [31]. One of the most striking observations in the context of natural distribution shifts is that model robustness improves with the classifier’s accuracy [56, 63, 26, 43]. For example, if a classifier’s accuracy increases by 1.0% on the unshifted CIFAR-10 test set, this tends to increase its accuracy by 1.7% on the CIFAR-10.1 dataset (a dataset with natural distribution shift) [56]. Moreover, such linear trends between the unshifted and shifted measures of error have now been observed in several contexts [56, 63, 43, 40, 44].
The number of theoretical works studying the impact of distribution shift on generalization is far smaller. One pioneering work provides VC-dimension-based error bounds for classification that are augmented by a discrepancy measure between source and target domains [10], while another demonstrates a similar class of uniform convergence-based results in the setting of kernel regression [11]. Recent work shows that learning domain-invariant features is insufficient to guarantee generalization when the class-conditional distributions of features may shift [69]. When the source domain gradually shifts toward the target domain, non-vacuous margin-based bounds for self-training can be established [32]. In [40], assumptions based on model similarity are used to help explain why classifiers exhibit linear trends between their accuracies on shifted and unshifted test sets [56, 43].
Our technical tools build on a series of works that have studied the exact high-dimensional limit of the test error for a growing class of model families and data distributions. In the context of linear models, recent work analyzes ridge regression for general covariances and a general non-isotropic source condition on the parameters which generate the targets [57], extending earlier work studying minimum-norm interpolated least squares and ridge regression in the random design setting [9, 14, 24]. The non-isotropy of source parameter effectively induces a shift on the bias term of this model, but the phenomenon is distinct from the covariate shifts we study here. Beyond linear regression, random feature models provide a rich but tractable class of models to gain further insight into generalization phenomena [2, 3, 41, 35]. These methods are of particular interest because of their connection to neural networks, with the number of random features corresponding to the network width (or model complexity) [48, 33, 29], and because they serve as a practical method for data analysis in their own right [54, 61]. In this context, a precise characterization of the gaps between uniform convergence and the (asymptotic) exact test error as a function of the sample size and number of random features can be derived [68]. Since this paper’s publication, we released follow-up work considering unequal scales in the training and test distributions and optimal regularization [64]. From the technical perspective, our analytic techniques build upon these works and a series of recent results stemming from the literature on random matrix theory and free probability [53, 52, 1, 2, 38, 51, 19, 45].

heading: 2 Preliminaries

heading: 2.1 Problem setup and notation
text: As in prior work studying random feature regression [24, 41, 2, 1], we compute the test error in the high-dimensional, proportional asymptotics where the dataset size m, input feature dimension n0, and hidden layer size n1 all tend to infinity at the same rate, with := n0/m and := n0/n1 held fixed. We refer to / as the overparameterization ratio, which is the limit of n1/m and characterizes the normalized complexity of the (random) feature model.
Interestingly, in this high-dimensional limit, the conditional distribution of a linear labeling function is asymptotically equivalent to a wide class of nonlinear teacher functions (see [41, 2] for more details). With this in mind, we consider the task of learning an unknown function from m i.i.d. samples (xi, yi) 2 Rn0 ⇥ R for i 2 {1, . . . ,m}, where the covariates are Gaussian, xi ⇠ N (0,⌃) with positive definite covariance matrix ⌃, and the labels are generated by a linear function parameterized by 2 Rn0 , drawn from N (0, In0). In particular
y(xi) = >xi/ p n0 + ✏i, (1)
where ✏i ⇠ N (0, 2✏ ) is additive label noise on the training points. We study the class of prediction models defined by kernel ridge regression using unstructured random feature maps [54]. The random features are given by a single-layer, fully-connected neural network with random weights. Given a set of training data X = [x1, . . . ,xm] and a prospective test point x, the random features embeddings of the training and test data are given by
F := (WX/ p n0) and f := (Wx/ p n0) , (2)
for a random weight matrix W 2 Rn1⇥n0 with i.i.d. standard Gaussian entries and an activation function : R ! R applied elementwise. The induced kernel is
K(x1,x2) := 1
n1 (Wx1/
p n0) > (Wx2/ p n0) , (3)
and the model’s predictions are given by ŷ(x) = Y K 1Kx, where Y := [y(x1), . . . , y(xm)], K := K(X,X)+ Im, Kx := K(X,x), and 0 is a ridge regularization constant1. Owing to the implicit regularization effect of the nonlinear feature maps [7], in low noise settings the optimal value of can sometimes be negative [30]. For simplicity, we nevertheless make the standard assumption that 0, though we emphasize our techniques readily accommodate negative values.
1We overload the definition of K to include the additive regularization whenever no arguments are present. Also, if = 0 and K is not full-rank, K 1 should be understood as the Moore–Penrose pseudoinverse.
Our central object of study is the expected test loss for a datapoint x ⇠ N (0,⌃⇤) where ⌃⇤ may be different from the training covariance ⌃. The test error (without label noise on the test point) is
E⌃⇤ = E[( >x/ p n0 Y K 1Kx)2] (4)
= Ex, [(E[ŷ(x)] y(x))2]| {z } B⌃⇤ +Ex, [V[ŷ(x)]]| {z } V⌃⇤ , (5)
where the inner expectations defining the bias and variance are computed over W , X , and Y . We decompose the training and test covariance matrices into eigenbases as ⌃ = P n0
i=1 ivivi > and ⌃⇤ =P
n0 i=1 ⇤ i v⇤ i v⇤ i >, where the eigenvalues are in nondecreasing magnitude, i.e. 1  2  . . .  n0 and ⇤1  ⇤2  . . .  ⇤n0 . We define the overlap coefficients
ri := v > i ⌃⇤vi =
n0X
j=1
(v⇤ j · vi)2 ⇤j (6)
to measure the alignment of ⌃⇤ with the ith eigendirection of ⌃. In particular, ri is the induced norm of vi with respect to ⌃⇤. We use t̄r to denote the dimension-normalized trace: for a matrix A 2 Rn⇥n, t̄r(A) = 1
n tr(A). We use kAk1 and kAkF to denote the operator norm and Frobenius
norm of matrix A respectively. Finally, we use x to denote the Dirac delta function centered at x.

heading: 2.2 Assumptions
text: Regularity assumptions on the spectra of ⌃ and ⌃⇤ are necessary to state the limiting behavior of this system. As in [67], it is not sufficient to consider the spectra of these matrices individually; they must be considered jointly. We do this in an eigenbasis of ⌃. Assumption 1. We define the empirical joint spectral distribution (EJSD) as
µn0 := 1
n0
n0X
i=1
( i,ri) (7)
and assume it converges in distribution to some µ, a distribution on R2+ as n0 ! 1. We refer to µ as the limiting joint spectral distribution (LJSD), and emphasize that this defines the relevant limiting properties of the train and test distributions2. Additionally, we require that lim sup
n0 max(k⌃k1, k⌃⇤k1)  C for a constant C.
Often we use ( , r) for random variables sampled jointly from µ and denote the marginal of under µ with µtrain. The conditional expectation E[r| ] is an important object in our study. We frequently overload the notation E[r| ] to view it as a function of , and we assume the following for simplicity.
Assumption 2. µ is either absolutely continuous or a finite sum of delta masses. Moreover, the expectations of and r are finite.
When the eigenspaces of ⌃ and ⌃⇤ are aligned and ri = ⇤i = ( i) for some smooth function , the support of the LJSD degenerates. Here, Assump. 1 is essentially equivalent to assuming the empirical spectral distribution of ⌃ converges in distribution to some µtrain, which is a standard assumption in the regression literature [14, 41]. One special case of note is when there is no shift, i.e. is the identity, in which case the LJSD degenerates to µ; defined by
µ;( , r) := µtrain( ) (r) , i.e. ( , ) ⇠ µ; for ⇠ µtrain . (8) As our analysis will eventually take place in the high-dimensional limit, we further define the asymptotic scales of the training and test covariances as s := limn0!1 t̄r(⌃) = Eµ[ ] and s⇤ := limn0!1 t̄r(⌃
⇤) = Eµ[r] under the limiting behavior specified in Assump. 1. Throughout this paper, we also enforce the following standard regularity assumptions on the activation functions to ensure the existence of the moments and derivatives we compute. Assumption 3. The activation function : R ! R is assumed to be differentiable almost everywhere. We assume that, | (x)|, | 0(x)|  c0 exp(c1x) for constants c0, c1.
2Note that the EJSD depends not only on ⌃ and ⌃⇤ but also on a choice of eigendecomposition for ⌃ when it has repeated eigenvalues. However, all possible choices for the EJSD form an equivalence class, and the ambiguity does not affect later definitions and conclusions. See Sec. A3.

heading: 2.3 A simple family of diatomic distributions
text: As the above assumptions allow such a general class of covariance structures, it is useful to consider our results in the context of a simple family of distributions that readily admits a simple interpretation. Definition 2.1. For ↵ 1 and ✓ 2 R, we define the family of (↵, ✓)-diatomic LJSDs with ✓-powerlaw shifts as
µdiatomic ↵,✓
:= 1
↵+ 1 (↵,C↵✓) +
↵
↵+ 1 (↵ 1,C↵ ✓), (9)
where C is a normalization constant chosen so that E µ
diatomic ↵,✓
[r] = 1. Note that µdiatomic ↵,✓ is the limit of
⌃ij :=
8 ><
>: ↵ if i = j and i  b n01+↵c ↵ 1 if i = j and i > b n01+↵c 0 if i 6= j
and ⌃⇤ := 1
t̄r(⌃✓) ⌃✓ . (10)
This simple two-parameter family of distributions captures the fast eigenvalue decay observed in many datasets in machine learning, for which the covariance spectra are often dominated by several large eigenvalues and exhibit a long tail of many small eigenvalues [34]. Note that the trivial case of ↵ = 1 yields an identity covariance with no shift. For the nontrivial setting ↵ > 1, the exponent ✓ parameterizes the strength of the shift in an intuitive way: when ✓ = 1, there is no shift; when ✓ < 1, ↵✓ < ↵, so the large eigendirections of the training distribution are suppressed in the test distribution, suggesting that the shift makes learning harder; when ✓ > 1, ↵✓ > ↵, so the large eigendirections of the training distribution are further emphasized in the test distribution, suggesting that the shift makes learning easier. We will return to the notion of shift strength in Secs. 3 and 4.

heading: 3 Motivating example: linear regression
text: We first consider the relatively simple case of ridgeless linear regression (LR), which will help build some intuition for the more general analysis of random feature regression in Sec. 5.1. Assuming the labels are generated by the linear model defined above, i.e. yi = >xi/ p n0 + "i, the estimator is given by ̂ = (XX>) 1XY , and the test risk (see Eq. (4)) has the following simple form. Proposition 3.1. For fixed dimension n0 and sample size m>n0+1, the test error of LR is given by
ELR⌃⇤ = 2 ✏ n0 m n0 1 t̄r(⌃⇤⌃ 1) = 2 ✏ n0 m n0 1 1 n0
n0X
i=1
ri i . (11)
Under Assump. 1, as n0,m ! 1 with = n0/m fixed, ELR⌃⇤ ! ELRµ = 2✏ /(1 )Eµ[r/ ].
One immediate question is whether a given shift will increase or decrease the test error relative to ELR⌃ . While the precise answer is of course determined by the value of t̄r(⌃
⇤⌃ 1), it useful for the subsequent analysis to develop an understanding of the individual contributions to this term. Similar decompositions of the test error into eigenspaces have proved useful in a variety of other contexts, e.g. [42, 4]. We begin with a specific example in the setting of the finite-dimensional analog of Def. 2.1. Example 3.1. For the finite form of the (↵, ✓)-diatomic density defined in Eq. (10), the test error of LR is given by
ELR⌃⇤ = 2 ✏ n0 m n0 1 ↵+ w(↵2✓ 1 ↵) 1 + w(↵2✓ 1) for w = 1 n0
n0
1 + ↵
⌫ , (12)
and so @ @✓ ELR⌃⇤ = 2 ✏ n0 m n0 1 2(1 w)w↵2✓ 1(1 ↵2) log(↵) (1+w(↵2✓ 1))2  0, which implies E LR ⌃⇤1  ELR⌃⇤2 whenever ✓1 ✓2, in accordance with the discussion in Sec. 2.3. It follows from Eq. (10) that the condition ✓1 ✓2 not only implies t̄r(⌃⇤1⌃ 1)  t̄r(⌃⇤2⌃ 1), but also that the ratios of overlap coefficients ri,1/ri,2 form a nondecreasing sequence. It is this condition involving all the eigendirections that will generalize to the nonlinear random feature setting in Sec. 4.
The following proposition captures the essence of these considerations in the context of linear regression. See Sec. A4 for the proof.
Proposition 3.2. Let ri,1 and ri,2 denote the overlap coefficients3 of ⌃⇤1 and ⌃⇤2 relative to ⌃. If tr(⌃⇤2) tr(⌃⇤1) and the ratios ri,1/ri,2 form a nondecreasing sequence, then in the setting of Prop. 3.1, ELR⌃⇤2 E LR ⌃⇤1 .
Whereas the (↵, ✓)-diatomic LJSDs explicitly enforce the trace normalizations tr(⌃) = tr(⌃⇤1) = tr(⌃ ⇤ 2) = 1, Prop. 3.2 provides sufficient conditions for the ordering of test errors for non-unit traces. The fact that ELR⌃⇤ scales linearly with the overall scale of ⌃ ⇤ is a unique feature of linear regression and does not generalize to the nonlinear random feature setting. We return to this issue in Sec. 4.

heading: 4 Definition of shift strength
text: Deriving conditions on whether a shift will hurt or help a model’s performance is crucial to building an understanding of covariate shift. Motivated in part by the above results for linear regression, and in part by the results for random feature regression that we present in Sec. 5.3, we introduce the following definition of shift strength, which is a direct generalization of the conditions of Prop. 3.2: Definition 4.1. Let µ1 and µ2 be LJSDs with the same marginal distribution of , denoted µtrain. If the asymptotic overlap coefficients are such that Eµ1 [r| ]/Eµ2 [r| ] is nondecreasing as a function of on the support of µtrain and Eµ1 [r]  Eµ2 [r], we say µ1 is easier than µ2 (or µ2 is harder than µ1), and write µ1  µ2. Comparing against the case of no shift µ;, we say µ1 is easy when µ1  µ; and hard when µ1 µ;.
A priori, there is little reason to hope that such a model-independent definition of shift strength would adequately characterize a shift’s impact on the total error, bias, or variance of a given model. Even for the relatively simple case of random feature kernel regression, the nonlinear feature maps of Eq. (2) would seem to inextricably couple the covariance distribution to the model.
Nevertheless, as we show in Sec. 5.1, the coupling between model and shift simplifies considerably in the high-dimensional proportional asymptotics. It is characterized by a handful of constants that depend solely on the overall covariance scale Eµ[r] and a collection of functionals of µ, whose magnitudes can be bounded in terms of the ratio Eµ[r| ]/Eµ; [r| ]. The conditions that Def. 4.1 places on Eµ[r] and Eµ[r| ]/Eµ; [r| ] can be augmented by various constraints on the model to derive bounds on how the total error and bias will respond to a shift of a given strength. This perspective introduces considerable complexity and we present the details of this analysis elsewhere.
In this work, we focus on a simpler, surprising result: by merely normalizing the scales of the covariate distributions (i.e. enforcing s = s⇤), Def. 4.1 provides a model-independent definition of shift strength that determines how random feature models respond to shifts of different strength. This observation motivates the following assumption. Assumption 4. The training and test covariance scales are equal, Eµ[ ] = Eµ[r], i.e. s = s⇤.
We emphasize that Assump. 4 reflects common practice for many models and data modalities, as preprocessing techniques such as standardization are ubiquitous and many architectural components such as layer- or batch-normalization achieve a similar effect [21, 28, 46].

heading: 5 Covariate shift in random feature kernel regression

heading: 5.1 Main results
text: Our main results characterize the high-dimensional limits of the test error, bias, and variance of the nonlinear random feature model of Sec. 2. Before stating them, we first introduce some additional constants that capture the effect of the nonlinearity . For z ⇠ N (0, s), define
⌘ := V[ (z)] , ⇢:= ( 1 s E[z (z)])2 , ⇣ := s⇢ , and ! := s(⌘/⇣ 1) . (13)
Our results also depend on the covariance spectra through two sets of functionals of µ,
Ia,b(x) := Eµ ⇣ a ( + x ) b ⌘ and I⇤ a,b (x) := Eµ ⇣ r a 1 ( + x ) b ⌘ . (14)
3Recall the definition of the overlap coefficients in Eq. (6).
(d) (f)(e)
(c)(b)(a) Total error Bias Variance
Sh ift
p ow
er , θ
Overparameterization ratio, ϕ/ψ Overparameterization ratio, ϕ/ψ Overparameterization ratio, ϕ/ψ
0.01 0.10 1 10 100 -3
-2
-1
0
1
2
3
0.01 0.10 1 10 100 -3
-2
-1
0
1
2
3
0.01 0.10 1 10 100 -3
-2
-1
0
1
2
3
Sh ift
p ow
er , θ
Sh ift
p ow
er , θ
0.025
0.05
0.1
0.2
0.4
0.8
1.6
Theorem 5.1. Under Assumps. 1, 2, 3 and 4, as n0, n1,m ! 1 the test error E⌃⇤ converges to Eµ = Bµ + Vµ, with the bias Bµ and variance Vµ given by
Bµ = I⇤1,2 (15)
Vµ = ⇢
@x
@
✓ I1,1(! + I1,2)(! + I⇤1,1) + 2 ⌧̄I1,2I⇤2,2
+ ⌧I2,2(! + I⇤1,2) + 2" ⇣ (! + I1,2)(! + I⇤1,1) +
⌧̄I⇤2,2
⌘◆ , (16)
where x is the unique nonnegative real root of x = 1 ⌧ !+I1,1 , @x @ = x +⇢ (⌧ / +⌧̄)(!+ I1,2) , and
⌧ =
p ( )2 + 4x /⇢+
2 and ⌧̄ =
1
+
⌧ 1 . (17)
Numerical predictions from Thm. 5.1 can be obtained by first solving the self-consistent equation for x by fixed-point iteration, x 7! 1 ⌧
!+I1,1 , and then plugging the result into the remaining terms. Fig. 1 shows excellent agreement between these asymptotic predictions and finite-size simulations.
At times we will find it convenient to consider the ridgeless limit of Thm. 5.1. By carefully expanding x and ⌧ for small , it is straightforward to obtain the following corollary. Corollary 5.1. In the setting of Thm. 5.1, as the ridge regularization constant ! 0, Eµ = Bµ+Vµ with Bµ given in Eq. (15) and Vµ given by
Vµ = | |x( 2 " + I1,1)(! + I⇤1,1) +
8 < : x ⇣ 1 x(! 2 ") 1 x2I2,2 ⌘ I⇤2,2 x 2 I2,2
x2 I2,2
! + I⇤1,2
<
, (18)
where x is the unique positive real root of x = min(1, / ) !+I1,1 .
Taking (x) = x and ! 0 in Cor. 5.1 yields an expression for the test error of ridgeless linear regression that agrees with [24] and with the asymptotic form of Prop. 3.1 (see Sec. A4.2).

heading: 5.2 Harder shifts increase the bias and test error
text: The bias and variance in Thm. 5.1 depend on the covariate shift exclusively through I⇤ a,b — all other terms such as x, ⌧ , ⌧̄ , and Ia,b only depend on the marginal of under µ. The functionals I⇤a,b generalize the simple ratio of overlap coefficients to eigenvalues, Eµ[r/ ], that characterizes the error for linear regression (indeed, I⇤0,0 = Eµ[r/ ]). In contrast, the error in the random feature setting is a combination of multiple such terms. Nevertheless, Def. 4.1 enables comparisons of the individual I⇤ a,b
functionals, which provide sufficient conditions to order the error and bias. Proposition 5.1. Consider two LJSDs such that µ1  µ2 (see Def. 4.1). Then, in the setting of Thm. 5.1, Bµ1  Bµ2 and, if 2"  !, Eµ1  Eµ2 .
Prop. 5.1 shows that Def. 4.1 provides an essentially model-independent condition to determine the impact of covariate shift on the test error4. Interestingly, both the bias (which arises from both regularization and model misspecification) and the total error (which has additional variance contributions from the randomness induced by W , X , and ✏) respond to shifts in tandem in the regime of small label noise. (For large label noise, the variance can dominate the error and cause violations of monotonicity; see Sec. 5.5.) Prop. 5.1 is illustrated for the (↵, ✓)-diatomic LJSD in Fig. 1: following the vertical lines upward in (a), (b), or the x-axis rightward in (e) yields easier shifts and a corresponding decrease in the bias and total error.

heading: 5.3 The benefit of overparameterization
text: While Prop. 5.1 shows that harder shifts increase the error, it is natural to wonder whether this increase can be mitigated by judicious model selection. In practice, empirical investigations have shown that the performance of large, overparameterized models tends to deteriorate less under distribution shift than their smaller counterparts [26]. We obtain a number of theoretical results that formally prove the benefit of overparameterization in our random feature setting.
First, we show that the bias decreases (or stays constant) when additional random features are added, which increases the model capacity and accords with the intuition of the bias as a measure of the model’s ability to fit the data. Proposition 5.2. In the setting of Thm. 5.1, the bias Bµ is a nonincreasing function of the overparameterization ratio / .
In contrast to the bias, which is monotonic for all overparameterization ratios, the variance can exhibit nonmonotonic behavior in the underparameterized regime. On the other hand, the following proposition shows that in the overparameterized regime, the variance is also nonincreasing. Note that our proof requires the setting of ridgeless regression ( = 0), but numerical investigation suggests this condition may not be necessary (see Fig. 1). Proposition 5.3. In the setting of Cor. 5.1 and in the overparameterized regime (i.e. < ), the variance Vµ is a nonincreasing function of the overparameterization ratio / .
The explosion of variance at the interpolation threshold and then its subsequent decay have been demonstrated in previous exact asymptotic studies of random feature regression in the absence of covariate shift, in stark contrast to what classical theory would suggest [2, 41]. Prop. 5.3 confirms the existence of analogous behavior under covariate shift.
Taken together, Props. 5.2 and 5.3 imply that some of the benefits of overparameterization extend to models evaluated out-of-distribution. An additional benefit is that overparameterized models are more robust: the difference in error between unshifted and shifted test distributions is smaller for larger models. A formal statement of this enhanced robustness is given in the following result. Proposition 5.4. Consider two LJSDs such that µ1  µ2 (see Def. 4.1). Then, in the setting of Cor. 5.1 and in the overparameterized regime (i.e. < ), the generalization gap Eµ2 Eµ1 is a nonincreasing function of the overparameterization ratio / .
4The weak model-dependence arising from the condition 2" < ! can instead be regarded as a small label-noise condition that can always be satisfied for ! > 0, which is true for any nonlinear (see Sec. A1).
= -0.5 (hard) = 1.5 (easy)
Identity line
-2.0 -1.5 -1.0 -0.5 0.0 -2.0
-1.5
-1.0
-0.5
0.0
(S hi
fte d
te st
e rro r) −E μ
(Unshifted test error)−Eμ∅
ImgNetv2 Grey ImgNetv2 TopImgs Linear fit (slope = 1.37) Linear fit (slope = 0.95) Identity line
30 40 50 60 70 80 90 30
40
50
60
70
80
90
Sh ift
ed Im
ag eN
et A
cc
ImageNet Val Acc
(b)(a)
Figure 2: Linear relationship between in-distribution and out-of-distribution generalization error. (a) Asymptotic predictions for shifted versus unshifted error for models with varying degrees of overparameterization / > 1, obtained via Cor. 5.1 for the (3, ✓)-diatomic LJSD (Eq. (9)) with = n0/m = 0.5, = ReLU, 2" = 0.01 and two different values of the shift-power ✓. Markers represent simulations for n0 = 512. The negated errors are plotted so that performance improves left to right and bottom to top, in order to match the behavior of the accuracy metric. (b) Reproduction of the empirical results of [56, 63], showing the relationship between the classification accuracy of various models on the original ImageNet test set and two shifted ImageNet datasets: a “hard" dataset with greyscale corruptions, Grey, and an “easy" dataset with high inter-annotator agreement, TopImgs. In both (a) and (b), the slope is greater than one for the hard shift and less than one for the easy shift, in accordance with Prop. 5.5.
In Fig. 1, Props. 5.2, 5.3 and 5.4 are illustrated. Following the horizontal lines rightward in (a), (b), and (c) or the x-axis rightward in (d) and (f) leads to models with more parameters. The monotonicity of the bias across the whole range of parameterization is evident, as is the necessity of considering the monotonicity of the variance and generalization gap only when > .

heading: 5.4 Linear trends between in-distribution and out-of-distribution generalization
text: We have discussed how overparameterization yields improvements on both unshifted and shifted test distributions, which hints that these two quantities are positively correlated. Indeed, recent work has suggested increasing model size as a path to increased robustness [26]. Additional empirical studies have further refined this observation by discovering a linear relationship between the performance of models of varying complexity on unshifted and shifted data [56, 63]. In the context of ridgeless random feature regression, we provide a formal proof of this linear relationship. Proposition 5.5. In the setting of Cor. 5.1 and in the overparameterized regime (i.e. < ),
Eµ = E0 + ⇣! + I⇤1,1 ! + I1,1 ⌘
| {z } SLOPE
Eµ; , (19)
parametrically in the overparameterization ratio / , where E0 and SLOPE are constants independent of / , and Eµ; is the error on the unshifted distribution. Moreover, SLOPE 1 when µ is hard and SLOPE  1 when µ is easy.
Eq. (19) implies a parametrically linear relationship between Eµ and Eµ; by varying / . Prop. 5.5 also makes the nontrivial prediction that an improvement on the unshifted distribution leads to a relatively greater improvement on the shifted distribution when the shift is hard, and to a relatively smaller improvement when the shift is easy. This prediction is corroborated qualitatively in the data from [55, 56, 43]. We plot this linear behavior in Fig. 2, where (a) shows the random feature model and (b) shows an example of data from [56, 63]. The striking similarity in these plots is evident.

heading: 5.5 Importance of assumptions
text: Props. 5.1, 5.2, 5.3, 5.4 and 5.5 rely on a number of assumptions and conditions; here we show the necessity of some of these prerequisites for our results.
(a) (c)(b)
Prop. 5.1 relies on a small label-noise condition ( 2 "  !) to ensure that the total error is ordered with respect to shift strength. The reason this condition is necessary is that the variance can actually increase as shifts become easier. While Fig. 1 presented a configuration for which the bias, variance, and error all decrease for easier shifts, Fig. 3(a) shows that a decrease is not guaranteed for the variance, and that it can increase even under the small label-noise condition. Moreover, while the bias continues to decrease for large label noise ( 2
✏ > !), the variance can become so large that bias
can no longer offset it, causing the error itself to increase, as seen in Fig. 3(a).
The strict ordering of overlap coefficients in Def. 4.1 are also necessary to guarantee a complete decoupling of the model and the shift strength. In the absence of these conditions, Fig. 3(b) shows how even a single out-of-order overlap coefficient induces a violation of the monotonicity with respect to shift strength suggested by Prop. 5.1 (this example is detailed further in Sec. A8).
Finally, we note that the exact linear relationship between in-distribution and out-of-distribution generalization characterized by Prop. 5.5 in Eq. (19) relies crucially on the overparameterization condition, < , as evidenced in Fig. 3(c), which shows marked nonlinearity in the underparameterized regime. This observation is perhaps unsurprising, as severely underparameterized models tend towards chance predictions, which produce comparable errors on shifted and unshifted data. Indeed, similar nonlinear behavior is seen in the low-accuracy regime for realistic models [56, Figure 17].

heading: 6 Conclusion
text: We have presented an exact, asymptotic calculation of the test error, bias, and variance for random feature kernel regression in the presence of covariate shift. After defining a partial order over covariate shifts (motivated by the setting of linear regression), we have proved that harder shifts imply increased error. Our results capture many empirical phenomena such as the fact that overparameterization is beneficial even under covariate shift and that a linear relationship exists between the generalization error on shifted and unshifted data. Future directions include extending our results to the nonasymptotic regime, accommodating feature learning and more general neural network models, and investigating the impact of covariate shift for other loss functions.
Acknowledgments and Disclosure of Funding
The authors would like to thank Rodolphe Jenatton, Horia Mania, Ludwig Schmidt, D. Sculley, Vaishaal Shankar, Lechao Xiao, and Steve Yadlowsky for valuable discussions.
This work was performed at and funded by Google. No third party funding was used.

Review summaries:
The paper studies the test error, as well as the bias and variance, of random feature regression in the asymptotic regime, in a setting with covariate shift — i.e., when the covariance matrix of the features is different at testing time than at training time. The paper defines a partial ordering over covariance shifts, and it proves that this corresponds to increased or decreased performance compared to the case of no shift. It also obtains a few results that relate these notions to overparameterization.

This paper presents a theoretical study of covariate shift under the setting of kernel ridge regression in the asymptotic regime. They charaterize the limiting test error, bias, and variance in this setting. They relates these with a quantity named hardness. They claim that their findings agree with several interesting empirical phenomena. 

This paper studies random feature regression in high dimensional setting with the presence of covariate shift between train and test data. The authors compute the high-dimensional asymptotic limit of the test error for Gaussian covariates with a shift in the covariance matrix. They also provide results characterizing the bias and variance decomposition.

The authors study covariate shift in over-parameterized random features models.  They provide an analysis of the test error, as well as an analysis of the decomposition of the test error into the bias and variance components.  This results in a partial ordering over test errors WRT the "hardness" of the covariate shift.  Further, the theoretical results provide a concrete explanation of the linear trend that has been observed in past work between the test error on clean and corrupted error.  

This work provides theoretical insight for why overparameterized models perform well when there is some covariate shift between the training and test sets. The authors' characterize their results by introducing a notion of "relative hardness". They present empirical evidence to match their intuition, and corroborate the main results in the paper using several empirical benchmarks.