Overparameterization Improves Robustness to Covariate Shift in High Dimensions
Authors: Nilesh Tripuraneni
Ben Adlam
Jeffrey Pennington
Venue: NeurIPS 2021 Poster (2021)
Keywords: Deep Learning Theory
Distribution Shift
Random Matrices
High-Dimensional Statistics

Abstract: A significant obstacle in the development of robust machine learning models is \emph{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.

Overparameterization Improves Robustness to Covariate Shift in High Dimensions
Nilesh Tripuraneni'
Ben Adlam" Brain Team, Google Research adlam@ google. com.
U.C. Berkeley!
Jeffrey Pennington"
Brain Team, Google Research
jpenninggoogle com
Abstract
A significant obstacle in the development of robust machine learning models is covariate shift, form 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- nigh-dimensional asymptotics of ran- dom feature regression under covariate shift and present a precise characterization the limiting test error, bias, and variance in this setting. Our results motivate natural partial order over covariate shifts that provides sufficient condition for determining when the shift will harm (or even help) test performance. We find that overparameterized models exhibit enhanced robustness covariate shift, providing one of the first theoretical explanations for this ubiquitous empirical phe- nomenon. Additionally, our analysis reveals exact linear relationship between the in-distribution and out-of-distribution generalization performance, offering an explanation for this surprising recent observation.
Introduction
Theoretical justification for almost all machine learning methods relies upon the equality of the distributions from which the training and test data drawn. Nevertheless, in many real-world applications, this equality is violated molated-nnturrally: naturally-occurring distribution shift between the training data and the data encountered during deployment is the rule, not the exception [Т]. Even non-adversarial changes in distributions can uncover the surprising fragility of modern machine learning models [55 16656 26
12 50 Such shifts distinct from adversarial examples, which require explicit
poisoning attacks [22]; rather, they can result from mild corruptions, ranging from changes of camera angle 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 BT, dramatic
degradation in calibration [50]. and surprising spurious inductive biases [2]. Thcoretical under- standing of why such patterns occur across variety real-world domains is scant. Even basic questions such as what makes certain distribution shift likely to hurt (or help) model's performance.
Equual contribution.
Work performed while the author was at Google.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

and by how much, are not understood. One reason that these phenomena have eluded theoretical understanding that there is often 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 general- ization in classical models, namely uniform convergence theory (see e.g. (66) ) may be insufficient to explain the behavior of modern deep learning methods (even the absence of distribution shift)
Indeed, classical measures of model complexity, such as various norms of the parameters, have been found to lead to ambiguous conclusions 49,
47 68
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 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 theoretical explanation for the linear relationships recently observed between in-distribution and out-of -iitiiibbittttinnnnnn generalization performance [55 56
1.1 Contributions
Our primary contributions are to:
1. Provide model-agnostic partial order over covariate shifts that is sufficient determine when a shift will increase or decrease the test error in random feature regression (see Def. 4.D:
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 overparametcrization 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)
1.2 Related work
There is extensive literature on the empirical analysis of distribution shift in all of its myriad forms, ranging from domain adaptation [62 20
36 defenses against adversarial among many others. Interestingly, for naturally occurring distribution shifts 31 26 standard robustness interventions provide little
70
69
37
attacks [39
60
to distributionally robust optimization 559
15
16
Indeed, empirical risk minimization on clean, unshifted training data often performs better on nut-of-distribution benchmarks than more sophisticated methods [TI. One of the most striking observations in the context of natural distribution shifts is that model robustmess improves with the classifier's 's accuracy 56
protection [5 [3
- For example, if a classifier's accuracy increases by 1.0% on the unshifted CIFAR-10 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
The number of theoretical works studying the impact of distribution shift on generalization is far smaller. One pioneering work provides VC-dimension-basee error bounds for classification that are augmented by discrepancy measure between source and target domains [10), while another demonstrates similar class of uniform convergence- based results in the setting of kernel regres- sion [1I. Recent work shows that learning domain-invarian features is insufficient to guarantee generalization when the class-conditional distributions of features may shift 669 When the source domain gradually shifts toward the target domain, non-vacuous margin-based bounds for self-training can be established + In 40 assumptions based on model similarity are used to help explain why
classifiers exhibit linear trends between their accuracies shifted and unshifted test sets [56] [R]

---

Our technical tools build on a series of works that have studied the exact high- nigh-dimensional limit of the test error for 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 y 14 22]..
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 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) 4
phenomena 2
41l (35].
22 and because they serve 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 function of the sample size and number of random features be derived (68] Since this paper's '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 series of recent results stemming from the
X
literature on random matrix theory and free probability [33 52
2 Preliminaries
2.1 Problem setup and notation
As in prior work studying random feature regression 24 41 2 1. we compute the test error in the nigh-dimensional, proportional asymptotics where the dataset size m, input feature dimension ng. and hidden layer size nı all tend to infinity at the same rate, with øi no/m and to == no/nn held fixed. We refer to 6/v/ as the overpurameterizatio ratio, which is the limit of nı //m /mm and characterizes the normalized complexity of the (random) feature model.
Interestingly, in this high-dimensionas limit, the conditional distribution of a linear labeling function is asymptotically equivalent to a wide class of nonlinear teacher functions (see A1 2 for more details). With this in mind, we consider the task of learning an unknown function from m i.i.d. samples (xx, yi) E Re x R for i E f1..... m), where the covariates are Gaussian, x; ~ (0, Σ) with positive definite covariance matrix Σ, and the labels are generated by a linear function parameterized by B E R"o drawn from N (0, J. In particular
y(x,) = BT x4/ no +
(1)
where e (O o²) 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 given by a single-layer, fully-connected neural network with random weights. Given a set of training data X = [x1...., xmm and a prospective test point x, the random features embeddings of the training and test data are given by
F == OW and f == (:=o/W///n))
(2)
for a random weight matrix W E R with i..dd standard Gaussian entries and an activation function o R + R applied elementwise. The induced kernel is
1 K(X,, x2) _ o(Wx VTo) n1
and the model's predictions are given by 0(x) = Y where Y
[y(x (x ]]
K := K(X, x) Kx := K(X, x), and 2 0 is ridge regularization constan Owing to the implicit regularization effect of the nonlinear feature maps 07 in low noise settings the optimal value of y can sometimes be negative B0 For simplicity, we nevertheless make the standard assumption that 7 2 0, though we emphasize our techniques readily accommodate negative values.
We 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 should be understood as the Moore Penrose pseudoinverse.
3

---

Our central object of study is the expected test loss for a datapoint x ~ N (0, (0,E, Σ*) where Σ* may be different from the training covariance E. The test error (without label noise on the test point) is
Ex.
[[( s/vno- - Xx)
(4)
Ex,0 [[[[((() - x(x)) + Ex (VX(
(5)
By*
Vig-
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 E = Lim1 A,v, and E* =
Eie
no X
v where the eigenvalues are in nondecreasing magnitude, i.e. X S A2 .... Ano
and 2 S ... S Amo We define the overlap coefficients
v V'v,
Σ
(6)
to measure the alignment of 2 with the ith eigendirection of E. In particular, T2 is the induced norm of with respect to E", We use tr to denote the dimension-normalizze trace: for matrix A E RR*,, tr(A) = a tt)( We use || and || to denote the operator norm and Frobenius norm of matrix A respectively. Finally, use 8x to denote the Dirac delta function centered at x.
2.2 Assumptions
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
1
Pno
8(x55)
and assume converges in distribution to some μt, a distribution on R23 as Ti + 00. We re- fer μ as the limiting joint spectral distribution (LISD), and emphasize that this defines the relevant limiting properties of the train and test distribution Additionally, we require that lim supa max([]e]ler [[x) S C for constant C.
Often we use rX,r) for random variables sampled jointly from j and denote the marginal of under with Maaii- The conditional expectation E[r[X] is important object in our study. We frequently overload the notation [E] to view it as a function of X, and we assume the following for simplicity.
Assumption 2. J is either absolutely continuous or a finite sum of delta masses. Moreover, the expectations of X and are finite.
When the eigenspaces of Σ and E* are aligned and r; A = (Ax) for some smooth function 4 the support of the LJSD degenerates. Here, Assump. [ is essentially equivalent to assuming the empirical spectral distribution of Σ converges distribution to some Purann which is a standard assumption in the regression literature [14 A1]. One special case of note is when there is no shift, i.e. + is the identity, in which case the LJSD degenerates to Aa defined by
(8) As our analysis will eventually take place in the high-dimensional limit, we further define
Po(A, r) = Mrain ())6 i.e. (A, ~ pi for À ~ Pariin
the asymptotic scales of the training and test covariances as 1im tr(E) E,,[A] and
8, := lim ti E*) = [r] under the limiting behavior specified in Assump.
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 o R + IR is assumed to be differentiable almost everywhere. We assume that, [x(x)], |o ox(x) S co exp( (1xx) for constants co C1.
Note that the EISD depends not only on Σ and n but also on a choice of cigendecomposition 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

---

2.3 A simple family of diatomic distributions
As the above assumptions allow such general class of covariance structures, it is useful to consider our results in the context of simple family of distributions that readily admits simple interpretation.
Definition 2.1. For 2 1 and 0 E R. we define the family of (ax, -)-ditoomic LJSDs with O-power- law shifts as
1
Alazonic Pa.9
a (a.Co') + a + 8(a 1,Ca ")>
where C' a normalization constant chosen so that pay [r] 1. Note that Altoomic is the limit of pa
if = j and i 1 no
1-a
Eij ==
a
if j and i >
and
E (Ea)
E.
(10)
if + j
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 cigenvalues and exhibit a long tail of many small eigenvalues 14 Note that the trivial case of yields an identity covariance with no shift. For the nontrivial setting a 1, the exponent parameterizes the strength of the shift in an intuitive way: when 0 = 1. there is no shift; when 0 < 1, a < a, so the large eigendirections of the training distribution are suppressed in the test distribution, suggesting that the shift makes learning harder; when 0 > 1, a a. 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 the notion of shift strength in Secs. 3 and M
3 Motivating example: linear regression
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.T, Assuming the labels are generated by the linear model defined above, i.e. yi = 3 / / + εss the estimator given by 5 (x xY, and the test risk (see Eq. 4 has the following simple form.
Proposition 3.1. For fixed dimension no and sample size m >> nu 1, the test error of LR is given by
E 0
Tip
0 m
(11)
m 71g
1g 1
A
1=1
Under Assump. as no, m + 5o with Φ = no fixed, E E/. = 0/ (1-6)),((r// Br
One immediate question is whether given shift will increase decrease the test error relative to ELR. While the precise answer is of course determined by the value of E-(E-E-1), 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
We begin with a specific example in the setting of the inite-dimensional analog of Def. 2.1
Example 3.1. For the finite form of the (ax, O) ---dittomic density defined in Eq.
10
the test error of
LR is given by
+ w(a20-1 a)
DLR
0ee
710
for
w
n2
(12)
m
110
+ w(a20 1)
rip
and so 0 ELR = 0² m-
no
2(1 w) wa w0 29-1 (1 (1-a") log(a)
< 0, which implies E < EER whenever
36
(1+w(a -I]1²
0, Oz in accordance with the discussion in Sec. 2.3
It follows from Eq. (10) that the condition
0, 2 02 not only implies GrEEE < Gr(Eg- ), but also that the ratios of overlup coefficients Tr.//riaform a nondecreasing sequence. this condition involving all the eigendirections that will generalize to the nonlinear random feature setting in Sec.
The following proposition captures the essence of these considerations the context of linear regression. See Sec. A4 for the proof.
5

---

Proposition 3.2. Let Ti1 and T222 denote the overlap coefficients of Σ and Σa2 relative to E. If (r(25)
tr( and the ratios / form a nondecreasing sequence, then the setting of S
Prop.
3.7
2
Whereas the (a, -iiittooi LJSDs explicitly enforce the trace normalizations ir(E) = tr(2)) = (r(E))= 1, Prop. 3.2
provides sufficient conditions for the ordering of test errors for non-unit traces. The fact that ES scales linearly with the overall scale of Σ* is a unique feature of linear regression and does generalize to the nonlinear random feature setting.
We return to this issue in Sec. !
4 Definition of shift strength
Deriving conditions on whether shift will hurt or help 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 a direct generalization of the conditions of Prop. 3.2
Let μr and μz be LJSDs with the same marginal distribution of X, denoted Pirain- If the asymptotic overlap coefficients are such that E,, [r| /rp (r A] is nondecreasing as function of on the support of Prriin and Eyg [r] S Egg [r], we say b4 is easier than p2 (or #2 harder than (.y).
Definition 4.1.
and write μ1 S u12- Comparing against the case of no shift pgg we say μa is easy when jn S. 110 and hard when μ1 2 pig-
A priori, there is little reason to hope that such 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. would seem to inextricably couple the covariance distribution to the model.
Nevertheless, as we show in Sec. 5.I the coupling between model and shift simplifies considerably in the sigh-dimensional proportional asymptotics. It is characterized by a handful constants that depend solely the overall covariance scale E, [r] and a collection of functionals of μ., whose magnitudes can be bounded in terms of the ratio E, [r|A]/E,, [r[A]. The conditions that Def. 4.1 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.
places E, [r] and Ep [r]]]EE [r| can be augmented by various constraints
In this work, we focus on a simpler, surprising result: by merely normalizing the scales of the covariate distributions (i.e. enforcing = s.). Def. I provides a modell-nddeeeden 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 [A] [r, i.e. s =
We emphasize that Assump. 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 46
Covariate shift in random feature kernel regression
5.1
Main results
Our main results characterize the high- digeessiinni limits of the test eтror, bias, and variance of the nonlinear random feature model of Sec. g Before stating them, we first introduce some additional constants that capture the effect of the nonlinearity a. For ~ NO, s), define
1 = V[o(2),, p= (=))))) ç: sp, and
- 1).
(13)
Our results also depend on the covariance spectra through two sets of functionals of μr,
In,s(z) = En (X* (6 (6+ x2)=*) and [z,(z) o E,, (rxa-1 (o x2) x)) b).
(14)
Recall the definition of the overlap coefficients in Eq.

---

(a)
Total error
[6]
Srelt poose. e
power
Shift power. I
0
overaremsteriaaaonnn rallo, dhyy
Cvorparandtertaaiss ratio, 6/v
Overperameteriaalis ratio, 4//p
(6)
09
2.0
Tritk wndr
Tood ene
0.00
0
Emor component
1.0
Ba 11?
6o
Emorr compareett
0.0
dig 116
Varawes
0255
020
1.0
0.10
0.0
0.0
aco
Overatramaeeriaaaioo ralio, dayy
SHitt power, 0
Overpenmmaterbalii ralio, 60/
Figure 1:
The asymptotic predictions of Thm. 5.1 as a function the overparameterizaaton ratio (b/0 /m) and the shift power (f) for the (2, diatomic LJSD (Eq. 2 with 6 no/m 0.5, = ReLU, 7 0.001, and o² 0.1. (a) The test error exhibits the characteristic double descent behavior for all shift powers. (b) The bias
nonincreasing function of Φ/vb for all shift powers, as in Prop. 5.2 (c) The variance is the source of the double-descent peak, and is a nonincreasing function of / d for all shift powers in the overparameteriized regime, in Prop. 5.3 In (a.b), the total етrоr and bias are nonincreasing functions of 0, as in Prop. 5.1
(d) ID horizontal slices of (a.b.c)
demonstrate the monotonicity in //v predicted by Props. 5.2 and 5.3
ID vertical slices of (a.b.c)
demonstrate the monotonicity in 0 predicted by Prop. 5. (the variance also appears monotonic, but it need not be in general). (f) The generalization gap between the error on shifted and unshifted distributions is nonincreasing function of Φ/v² in the overparameterized regime, as in Prop. 5.4 Markers in (d.e,f) show simulations for no 512 and agree well with the asymptotic predictions.
Theorem 5.1. Under Assumps. D 2
no, n1, the test error Eg converges to E, = Bn + Va with the bias B, and variance Vú given by
and 4
B₁ o
(15)
vo Ör
In,1(w + (II,)) + +I,,)) + Ø²
VA = - p o Oy
2
+ + + xI+z)) + o²' ( (w
(I + IT,1) + 1
(TT22))
(16)
where x is the unique nonnegative real root of 1- dr w+T,11 By
and
(v 23² + 4mbdn/p
and == (-
(17)
2
Numerical predictions from Thm. 5.1 can be obtained by first solving the self-consistent equation for x by fixed-point iteration, & + Zi.i and then plugging the result into the remaining terms. Fig.
shows excellent agreement between these asymptotic predictions and finite-size simulations.
At times will find convenient consider the ridgeless limit of Thm. 5.1 By carefully expanding x and 7 for small 7, it is straightforward to obtain the following corollary.
Corollary 5.1. In the setting of Thm. 5.7 as the ridge regularization constant y - O, E, = =B,, V/ with B, given in Eq. (5) and Vn given by
s(w- Iz
22
VA
2l0² Iw,)(w I7,)+
(18)
1
0
(w xIt Φ<
where r is the unique positive real root of m/vl1.6/w)
w+I1,1

---

Taking a(x) = x and db - 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)
5.2 Harder shifts increase the bias and test error
The bias and variance in Thm. 5.1 depend on the covariate shift exclusively through I2 - all other terms such as 2, T, F, and Za,h only depend on the marginal of under μ. The functionals T사,6 generalize the simple ratio of overlap coefficients to cigenvalues, [y that characterizes the error for linear regression (indeed, To (r, (r/)). In contrast, the error in the random feature setting is a combination of multiple such terms. Nevertheless, Def. A.]. J.J.leneeee comparisons of the individual Ta functionals, which provide sufficient conditions to order the error and bias.
Proposition 5.1. Consider two LJSDs such that μ1 μ22 (see Def. 4.7 Then, in the setting of Bp I Bpa and, if of S w. Em S Epp-
Thm.
5.7
Prop. 5.1 shows that Def. 4.1 provides an essentially model-independent condition to determine the impact of covariate shift on the test erroi 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 c) 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 (a, d)-diatomic LJSD in Fig. | following the vertical lines upward in (a), (b), or the x-axis rightward in (e) yields easier shifts and corresponding decrease the bias and total error.
5.3 The benefit of overparameterization
While Prop. | 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, show that the bias decreases (or stays constant) when additional random features added, which increases the model capacity and accords with the intuition of the bias as a measure of the model's '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 overpa- rameterization ratio 6/1).
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 also nonincreasing. Note that proof requires the setting of ridgeless regression (7 0), but numerical investigation suggests this condition may not be necessary (see Fig. D...
Proposition 5.3. In the setting of Cor. 5.1 and in the overparameterized regime (i.e. vb Φ), the variance Vi 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 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 models evaluated auttof-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 μn S #2 (see Def. 4.7v. Then, in the setting of Cor 5.7 and in the overparameterized regime (i.e. vé < 6), the generalization gap E Epp is ratio $/v0
nonincresiigg function of the overparameterizatte
'The weak model-de depeedddeee arising from the condition o² < w can instead be regarded as small label-noise condition that always be satisfied for O. which true for any nonlinear (see Sec. Al

---

(b)
0.0
90
I Grey
EE, (Shifted test error)
-0.5
Identity line
0 1.5
-0.5 (hard)
Shifted ImageNet Acc
80
ImgNetv22 Toplmgs
Linear fit (slope 1.37)
Linear (slope 0.95)
Identity line
-1.0
60
50
40
-2.0
30
-2.0
-1.5
-1.0
-0.5
0.0
40
50
60
70
80
90
Eyy (Unshifted test error)
ImageNet Val Acc
Figure 2: Linear relationship between in in-distribution and out-of-distribution generalization enror (a) Asymptotic predictions for shifted versus unshifted error for models with varying degrees of overparameterization Φ/v² > 1, obtained via Cor. 5.1 for the (3, d)-dittomic LJSD (Eq. (9) with = no/m = 0.5, / = ReL.U, o² 0.01 and two different values of the shift-power 0. Markers represent simulations for no 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 "easy" dataset with high inter-annotan agreement, Toplmgs. In both (a) and (b), the slope is greater than one for the hard shift and less than one for the easy shift, accordance with Prop. 5.5
In Fig. D 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 the variance and generalization gap only when á > vb.
5.4 Linear trends between in-distribution and out-of-distribution generalization
We have discussed how overparameterriation 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 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 unshifted and shifted data
[56 ( In the context of ridgeless random feature regression, we provide formal proof this linear relationship.
Proposition 5.5. In the setting of Cor. and the overparameterized regime (i.e. 1 < Φ).
+
E. Eo +
Eps
(19)
I1,1
SLOPE
parametrically in the overparameterizatto ratio &/ where En and SLOPE are constants indepen- dent of 1/ and Epg is the error on the unshifted distribution. Moreover, SLOPE when μ is hard and SLOPE < when p is easy.
Eq. 19 implies parametrically linear relationship between E, and Eus by varying d/ Prop. 5.5 also makes the nontrivial prediction that improvement on the unshifted distribution leads relatively greater improvement on the shifted distribution when the shift is hard, and to a relatively smaller improvement when the shift easy. This prediction is corroborated qualitatively in the data from [55 56 4 We plot this linear behavior in Fig. 2 where (a) shows the random feature model
and (b) shows example of data from 156 68
The striking similarity in these plots is evident.
5.5
Importance of assumptions
Props.
and 5.5 rely on number of assumptions and conditions; here we show the
necessity of some these prerequisites for our results.

---

(8)
(b)
[0]
2.0
14
(Shilled test erron
-0.2
6.0
8rg (ooppammeeetired burceepannnetttooe Hlrrity liw
Eree comporen
Total ame
0..4
Bise
1.0
Variancc
0.-
114 o
0.5
1.00
0.0
0.0 0.01 0.10
50
100
1.0
0.8
0..5
0.4
0.2
0.
Shi powsr
Oveparsamtteriaatoon rafio. 6//v
-Bag (Umshhitte emroy)
Figure 3: Relaxing the assumptions and conditions can lead to counterexamples to the propositions. (a) Asymptotic predictions (solid lines) and simulations with no = 4096 (markers) for the total error, bias, and variance for the (4, O)-diatomic LJSD with ó = 4, 1 0.25, ? = 10-4, and a = ReLU (implying w = 1
=z 0.36) as function of increasing shift power B. When of < w (dashed
curves), the bias and total eπror are nonincreasing, as predicted by Prop. L.1 though the variance not. When o² > w (solid curves), the total error no longer nonincreasing. (b) Asymptotic predictions (solid lines) and simulations with 7g = 256 (markers) for the total error with Φ = 0.5, y = 0.1, a ReL.U and o² 0.01 as function of the overparameterization ratio d/v) for four different LJSDDs ........ -. f44, chosen such that the only comparable pairs of LJSDs under the partial order Def. 4. are 14 2 14 and u12 2 P4, and the strict ordering of the error for those pairs is seen for all values of ø/ti. The orange (122) and green (4²) curves cross one another, illustrating how nonmonotonicity of overlap ratios in Def. 4. can induce model-dependence in the ordering of the error. (c) Asymptotic predictions (solid lines) and simulations for no 512 (markers) for shifted versus unshifted error for models with varying values of the overparameterizztton ratio 6/1/. obtained via Thm. 5.1 for the (3, - 1/2)-diatomic LJSD with é 0.5, ReLU, of 0.01, and y 0.005. While the relationship is nearly linear in the overparameterized regime, it is markedly nonlinear in the underparameterizedd regime, highlighting the importance of overparamettrrizaton in Prop. 5.5
relies on small label-noise condition (a² < w) to ensure that the total error is ordered Prop. 5.1
with respect to shift strength. The reason this condition is necessary that the variance can actually increase as shifts become easier. While Fig. presented configuration for which the bias, variance, and error all decrease for easier shifts, Fig. 3 a) shows that 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 (a? > w), the variance can become so large that bias no longer offset it, causing the error itself to increase,
in Fig, aa.
The strict ordering of overlap coefficients in Def. are also necessary to guarantee complete decoupling of the model and the shift strength. In the absence of these conditions, Fig. B]b shows how even a single out-of-order overlap coefficient induces violation of the monotonicity with respect to shift strength suggested by Prop. 5. (this example is detailed further in Sec. A8) 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, s d, evidenced in Fig. C(.) which shows marked nonlinearity in the underparameter- ized 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].
6
Conclusion
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 partial order over covariate shifts (motivated by the setting of linear regression), we have proved that harder shifts imply increased eтror. Our results capture many empirical phenomena such as the fact that overparameterization is beneficial even under covariate shift and that a línear relationship exists between the generalization error on shifted and unshifted data. Future directions include extending our results to the non- asymptotic regime, accommodating feature learning and more general neural network models, and investigating the impact of covariate shift for other loss functions.
10

---

Acknowledgments and Disclosure of Funding
The authors would like thank Rodolphe Jenatton, Horia Mania, Ludwig Schmidt, D. Sculley, Vaishaal Shankar, Lechao Xiao, and Steve Yadlowsky for valuable discussions.
This work was performed and funded by Google. No third party funding used.
References
[1] B. Adlam, J. Levinson, and J. Pennington. A random matrix perspective on mixtures of nonlinearities for deep learning. arXiv preprint arXiv:1912.0082. 2019.
[2] B. Adlam and J. Pennington. The neural tangent kernel in high dimensions: Triple descent and multi-scale theory of generalization. In Proceedings of the 37th International Conference Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 74-84. PMLR, 2020.
[3] B. Adlam and J. Pennington. Understanding double descent requires fine- tiee-grained bias-varians variance decomposition. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 11022- 11032. Curran Associates, Inc., 2020.
[4] M. S. Advani, A. M. Saxe, and H. Sompolinsky, High-dimensional dynamics of generalization in neural networks. Neural Networks, 132:428 446, 2020.
[5] M. Banna, Merlevède, and M. Peligrad. On the limiting spectral distribution for large class of symmetric random matrices with correlated entries. Stochustic Processes and their Applications, 125(7):2700-2) 2726, 2015.
[6] M. Banna, Najim, and Yao. CLT for linear spectral statistics of large random information- plus-noise matrices. Stochastic Processes and their Applications, 130(4):2250-222) 2020.
[7] P. L. Bartlett, A. Montanari, and A. Rakhlin. Deep learning: statistical viewpoint, 2021.
[8] C. J. Becker, C. M. Christoudias, and P. Fua. Non-linear domain adaptation with boosting, In
C. J. C. Burges, L.. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
[9] M. Belkin, D. Hsu, S. Ma, and S. Mandal. Reconciling modern machine-learning practice and the classical biai-nar trade-off. Proceedings of the National Academy of Sciences, 1 116(32):15449-155 15854, 2019.
[10] S. Ben-David, J. Blitzer, K. Crammer, and F. Pereira. Analysis of representations for domain adaptation. In B. Schölkopf, Platt, and T. Hoffman, editors, Advances in Neural Information Processing Systems, volume 19. MIT Press, 2007.
[11] C. Cortes and M. Mohri. Domain adaptation and sample bias correction theory and algorithm for regression. Theor. Comput. Sci., 519:1033-166 2014.
[12] A. D'Amuur, K. Heller, D. Moldovan, B. Adlam, B. Alipanahi, A. Beutel, C. Chen, J. Deaton, J. Eisenstein, M. D. Hoffman, al. Underspecification presents challenges for credibility in modern machine learning. arXiv preprint arXiv:2011.03300 2020.
[13] Y. Deshpande and A. Montanari. Sparse pea via covariance thresholding. Journal of Machine Learning Research, 17(141):1-41, 2016.
[14] E. Dobriban and Wager. figh-dimensional asymptotics of prediction: Ridge regression and classification. The Annals of Statistics, 46(1):247 279, 2018.
[15] J. Duchi, T. Hashimoto, and H. Namkoong. Distributionally robust losses for latent covariate mixtures, 2020.
[16] C. Duchi and Namkoong. Learning models with uniform performance via distributionally robust optimization. The Annals of Statistics, 49(3):1378 1406, 2021.

---

[17] L. Erdos. The matrix dyson equation and its applications for random matrices. arXiv preprint 10000 2019.
[18] L. Erdös, H.-T. Yau, and J. Yin. Bulk universality for generalized wigner matrices. Probability Theory and Related Fields, 154(1-2):341-44 1077 2012.
[19] R. Far, I. Oraby, W. Bryc, and Speicher. Spectra of large block matrices. arXiv preprint cs/0610045, 2006.
[20] X. Glorot, A. Bordes, and Y. Bengio. Domain adaptation for large-scale sentiment classification: A deep learning approach. In Proceedings of the 28th International Conference Interna- tional Conference on Machine Learning, ICML'11, page 513-520, Madison, WI, USA, 2011. Omnipress.
[21] I. Goodfellow, Y. Bengio, and A. Courville. Deep learning. MIT press, 2016.
[22] I. J. Goodfellow, J. Shlens, and C. Szegedy. Explaining and harnessing adversarial examples. In Y. Bengio and Y. LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
[23] G. Grimmett. Percolation. In Percolation, pages 1-31. Springer, 1999.
[24] T. Hastie, A. Montanari, S. Rosset, and R. J. Tibshirani. Surprises in high- -igh-dimensionl ridgeless least squares interpolation. arXiv preprint arXiv: 083.08560, 2019.
[25] J. W. Helton, T. Mai, and R. Speicher. Applications of realizations (aka linearizations) to free probability. Journal of Functional Analysis, 274(1):1-79, 2018.
[26] D. Hendrycks, Basart, N. Mu, S. Kadavath, Wang. E. Dorundo, Desai, T. Zhu, S. Parajuli, M. Guo, D. Song, J. Steinhardt, and J. Gilmer. The many faces of robustness: A critical analysis of outtof-distribution generalization. In Proceedings of the IEEE/CVE International Conference on Computer Vision (ICCV), pages 8340 October 2021.
[27] D. Hendrycks and T. G. Dietterich. Benchmarking neural network robustness to common corruptions and perturbations. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
[28] S. Ioffe and Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Proceedings of the 32nd International Conference on International Conference on Machine Learning Volume 37, ICML' 15, page 448 456. JMLR.org, 2015.
[29] A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS'18 18, page 8580-8589, Red Hook, NY, USA, 2018. Curran Associates Inc.
[30] D. Kobak, J. Lomond, and B. Sanchez. The optimal ridge penalty for real-world high- dimensional data can be zero or negative due to the implicit ridge regularization. Journal of Machine Learning Research, 21 21(169):1-16, 2020.
[31] P. W. Koh, S. Sagawa, H. Marklund, S. M. Xie, M. Zhang, A. Balsubramani, W. Hu, M. Ya- sunaga, R. L. Phillips, I. Gao, T. Lee, E. David, I. Stavness, W. Guo, B. Earnshaw, Haque, S. M. Beery, J. Leskovec, A. Kundaje, E. Pierson, S. Levine, C. Finn, and P. Liang. Wilds: A benchmark of in-the-wild distribution shifts. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 5637-5664. PMLR, 18-24 Jul 2021.
[32] A. Kumar, T. Ma, and Liang. Understanding self-training for gradual domain adaptation. In H. D. III and A. Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 5468-5479. PMLR, 13-18 Jul 2020.
12

---

[33] J. Lee, Y. Bahri, R. Novak, S. S. Schoenholz, J. Pennington, and J. networks as gaussian processes. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018
Deep neural
[34] J. Lee. S. Schoenholz, J. Pennington, B. Adlam, L. Xiao, R. Novak, and J. Sohl- Sohl-Dickstein. Finite versus infinite neural networks: empirical study. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 15156-15172. Curran Associates, Inc., 2020.
[35] Z. Liao, R. Couillet, and M. W. Mahoney. A random matrix analysis of random fourier features: beyond the gaussian kernel, a precise phase transition, and the corresponding double descent. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 23939-13950 Curran Associates, Inc., 2020.
[36] M. Long, H. Zhu, Wang, and M. Jordan. Unsupervised domain adaptation with residual transfer networks. In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS' 16, page 136-144, Red Hook, NY, USA, 2016. Curran Associates Inc.
[37] M. Long, H. Zhu, J. Wang, and M. I. Jordan. Deep transfer learning with joint adaptation networks. In D. Precup and Y. W. Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 2208- 2217, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMIR.
[38] C. Louart, Z. Liao, R. Couillet, et al. A random matrix approach to neural networks. The Annals of Applied Probability, 28(2): 190-1248, 2018.
[39] A. Madry, A. Makelov, Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant to adversarial attacks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 2018, Conference Track Proceedings. OpenReview.net, 2018.
[40] H. Mania and S. Sra. Why do classifier accuracies show linear trends under distribution shift?, 2021.
[41] S. Mei and A. Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 06 2021.
[42] G. Mel and S. Ganguli. A theory of high dimensional regression with arbitrary correlations between input features and target functions: sample complexity, multiple descent curves and a hierarchy of phase transitions. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages
PMLR, 18-24 Jul 2021.
[43] J. Miller, K. Krauth, B. Recht, and L. Schmidt. The effect of natural distribution shift question answering models. In H. D. III and A. Singh, editors, Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 6905-6916. PMLR, 13-18 Jul 2020.
[44] J. P. Miller, R. Taori, A. Raghunathan, S. Sagawa, P. W. Koh, V. Shankar, P. Liang, Y. Carmon, and L. Schmidt. Accuracy the line: the strong correlation between oftto--diit and in-distribution generalization. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 7721-7735. PMLR, 18-24 Jul 2021.
[45] J. A. Mingo and R. Speicher. Free probability and random matrices, volume 35. Springer, 2017.
[46] Z. Nado, S. Padhy, D. Sculley, A. D' Amour, B. Lakshminarayanan, and J. Snoek. Evaluat- ing prediction-tine batch normalization for robustness under covariate shift, arXiv preprint arXiv:2006.109 2020.
13

---

[47] V. Nagarajan and J. Z. Kolter. Uniform convergence may be unable to explain generalization in deep learning. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d Alché-Buee Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[48] R. M. Neal. Priors for infinite networks. In Bayesian Learning for Neural Networks, pages 29 53. Springer, 1996.
[49] B. Neyshabur, S. Bhojanapalli, D. Mcallester, and N. Srebro. Exploring generalization in deep learning. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[50] Y. Ovadia, E. Fertig, J. Ren, Z. Nado, D. Sculley, S. Nowozin, J. Dillon, B. Lakshminarayanan, and J. Snoek. Can you trust your models uncertainty? evaluating predictive uncertainty under dataset shift. In H. Wallach, H. Larochelle. A. Beygelzimer, F. Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[51] S. Péché et al. note on the pennington worah distribution. Electronic Communications in Probability, 24, 2019.
[52] J. Pennington and P. Worah. Nonlinear random matrix theory for deep learning. In I. Guyon, U. V. Luxburg. S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[53] J. Pennington and P. Worah. The spectrum of the fisher information matrix of single-hidden- layer neural network. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garneut editors, Advances Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[54] A. Rahimi and B. Recht. Random features for large-scale kernel machines. In J. Platt, D. Koller, Y. Singer, and S. Roweis editors, Advances in Neural Information Processing Systems, vol- ume 20. Curran Associates, Inc., 2008.
[55] B. Recht, R. Roelofs, L. Schmidt, and V. Shankar. Do cifar- 10 classifiers generalize to cifar-10? arXiv preprint arXiv: 180.0005,, 2018.
[56] B. Recht, R. Roelofs, L. Schmidt, and V. Shankar. Do imagenet classifiers generalize to imagenet? In K. Chaudhuri and Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 54800 PMLR, 2019.
[57] D. Richards, J. Mourtada, and L. Rosasco. Asymptotics of ridge(less) regression under general source condition. In A. Banerjec and K. Fukumizu, editors, Proceedings of The 24th Inter- national Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 3897. PMLR, 13 Apr 2021.
[58] D. V. Rosen. On moments of the inverted wishart distribution. Statistics, 30(3):259-21 1997.
[59] Sagawa, P. W. Koh, T. B. Hashimoto, and P. Liang. Distributionally robust neural networks. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 30, 2020. OpenReview.net, 2020.
[60] L. Schmidt, S. Santurkar, D. Tsipras, K. Talwar, and A. Madry. Adversarially robust generaliza- tion requires more data. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
[61] V. Shankar, A. Fang, W. Guo. S. Fridovich-Keil.. J. Regan-Kelley, L. Schmidt, and B. Recht. Neural kernels without tangents. In H. D. III and A. Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 8614-8623, PMLR, 13-18 Jul 2020.
14

---

[62] M. Sugiyama, M. Krauledat, and K.-R. Müller. Covariate shift adaptation by importance weighted cross validation. Journal of Machine Learning Research, 8(35):985-1055 2007.
[63] R. Taori, A. Dave, V. Shankar, N. Carlini, B. Recht, and L. Schmidt. Measuring robustness to natural distribution shifts in image classification. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 18583-18599, Curran Associates, Inc., 2020.
[64] N. Tripuraneni, B. Adlam, and J. Pennington. Covariate shift in high-dimensional random feature regression. arXiv preprint arXiv:2111.08234, 2021.
[65] R. Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
[66] M. J. Wainwright. High-Dimennional Statistics: A Non-Asymptotic Viewpoint. Cambridge Series Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
[67] D. Wu and J. Xu. On the optimal weighted & regularization in overparameterized linear regression. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 10112-10123. Curran Associates, Inc., 2020.
[68] Z. Yang. Y. Bai, and S. Mei. Exact gap between generalization and uniform convergence in random feature models. In M. Meila and T. Zhang, editors, Proceedings the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 11 11704-11715. PMLR, 2021.
[69] H. Zhao, R. T. D. Combes, K. Zhang, and G. Gordon. On learning invariant representations for domain adaptation. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 7523-7532. PMLR, 09-15 Jun 2019.
[70] H. Zhao, S. Zhang, G. Wu, J. M. Moura, P. Costeira, and G. J. Gordon. Adversarial multiple source domain adaptation. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- -isnnhi, and R. Gamnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
15


Reviews:
[{"review_id": "tz1ZHhukyQy", "reviewer": "Reviewer_9Mq1", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "One concern is whether the partial ordering in Definition 1 can capture interesting shifts. Most of the results depend on the partial ordering, so it is crucial for this to be the case. However, at first sight, the definition looks very restrictive: it requires ratios of overlap coefficients and eigenvalues to form a non-increasing sequence. It’s not obvious at all when this should be the case. The only example given, Example 1, is unfortunately trivial in this respect: the covariance matrices are diagonal (so the eigenspaces are aligned, which makes the definition much easier) and they have only two different eigenvalues. I feel that it would be crucial to give examples of more interesting families of covariate shifts for which the definition is meaningful; in particular, ones where the eigenspaces are not aligned and where the eigenvalues are more different. I feel that it would also be important to explicitly mention common shifts that cannot be captured by the definition; e.g., unless I am mistaken, this is the case with rotations, which seems an important limitation, given how common such transformations are.\n\nAnother concern is that Theorem 2 and even Corollary 1 are extremely complicated. I understand that the advantage of presenting them like this is that they are exact. But it also makes the results very difficult to understand and interpret. \n\nIn fact, the paper does not give any explanation of the intuition or of the proof techniques for the result in the random feature regression setting. The only explanation, given in Section 2.1, is about linear regression — but, based on the related work section, it seems that this setting has already been studied. The contribution of this paper is supposed to be to extend such results to the random feature regression setting. So, I can only conclude that the paper gives no explanation at all for its actual contribution — i.e., for the extension from linear regression to random feature regression.\n\nThe lack of an explanation also makes it more difficult to trust the results. This is particularly true because the proofs are very calculation-heavy; e.g. section F consists of 20 pages of pure calculations. A good explanation of the intuition or of the proof techniques would help alleviate some of these worries.\n\nThe results in propositions 3-6 do seem actually interesting, assuming that the partial ordering is actually interesting. \n\nIn my opinion the experiments included in the main text are not particularly interesting (and similar results have been known about overparameterization for some time). I would have been more interested to see experiments that illuminate aspects of the theory, even if only synthetic (e.g., a check of proposition 3 for common covariance shifts, some of which may respect the partial ordering and some of which may not).\n\nOther comments:\n\nIt is also unclear to me how standard Assumption 1 is. If it is standard, or if it applies to a wide range of common distributions, this could be stated. If not, then it should definitely be stated.\n\nAt line 78 there’s an unnecessary comma.\n\n----\n\nUPDATE: My concerns about the partial ordering are addressed. For some of the other concerns, the answer boils down to \"this is what other papers in this area do too\". Unfortunately, I am less familiar with this area than I initially thought. I increased my rating to 6 while decreasing my confidence to 1.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper seems fine to me in this regard.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "TVOfWW_7Bdh", "reviewer": "Reviewer_oyKe", "summary": "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.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The paper is original. They proposed a way to quantify the hardness of covariate shift and related this to the Bayes risk in kernel ridge regression.\n\nQuality: The quality is good. Theoretical results have solid proof as far as I can tell. \n\nClarity: There is some room for improvement. Specifically, the paper is a little hard to read because there is not enough explanation/intuition for the presented theorems, especially for thm2 and coro1. It is unclear what those many terms in the expressions mean. It might be better to add some explanation or point out to the readers where/which terms/what they should focus on.\n\nSignificance: This is a good contribution to an important problem.\n\n\nSpecific comments:\n1. Is there any literature/computation/examples that can justify the spectral assumptions? Specifically, I find the assumptions in the part from line 125 to line 151 not sufficiently justified or explained. For example, it might be better to provide some nontrivial cases in which the limit LJSD exists, or r_2/r_1 is monotonic, etc.\n2. There are several closely related works regarding generalization. First, the kernel regression setting studied in this paper seems closely related to arxiv.org/abs/1908.10292. It would be good to see a discussion about the relation/comparison with that work. Also, the study of the Bayes risk is close to that in https://arxiv.org/abs/2008.01036. \n3. This paper consider the Bayes risk (i.e. expectation w.r.t. \\beta). Is it possible to consider the case here each dimension of \\beta is pre-fixed?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I feel some assumptions of the papers are not sufficiently justified/explained. Please see specific comment 1.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "J0R5Vy00Ai", "reviewer": "Reviewer_rcgs", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Originality\nI am not too familiar with works related to analysing test error when there is covariate shift. Nonetheless, I find the results and the technique of working with random features interesting.\n\n### Quality\nIntroduction is well written, and the motivation of the problem is sufficiently detailed. The notion of a class of covariate shifts is an interesting generalization theoretically, and subsequent results are empirically verified using simply experimental setups. The submission is technically sound, and complete, with a few future directions that are beyond the scope of this submission.\n\n### Clarity\nSection 2.2 could generally be simplified, as there are plenty of equations or perhaps it would be better if the authors introduced these equations in a sequential manner and explain the purpose or intuition behind them. For instance the authors claim that $\\eta, \\eta\\_{\\*}$ capture the effect of activation non-linearity (these seem to be $\\text{Var}(\\sigma(\\sqrt{s} z)), \\text{Var}(\\sigma(\\sqrt{s\\_{\\*}} z))$ respectively). There is also some undefined notation: $\\mathbb{C}^{+}$ (complex numbers with real positive parts?), $\\gamma$, $\\mathfrak{R}$ (real part map?). Additionally what does it mean for $E\\_{\\Sigma^{\\*}} \\to E\\_{\\mu}$ to be equal to another limit? Unfortunately, a majority of Page 6 seems to be hard to understand: while Theorem 2 is general, it is not immediately clear what the apparent purpose of the Theorem is, and the authors could have added a prologue regarding this.\n\n### Significance\nWhile mathematically interesting, the asymptotic setting is not very useful practically. For instance, it would be better to obtain non-asymptotic rates, and this might also help corroborate empirical phenomena. The authors also highlight this in the final section of the paper.\n\n-----\n\nSome additional detailed comments / questions:\n\n- The model being discussed here is covariate shift where distribution of the $X_{train} \\neq$ distribution of $X_{test}$, but distribution $y | X_{train} =$ distribution $y | X_{test}$ . Specifically, here the authors are looking at the following model: $X_{train} \\overset{i.i.d}\\sim \\mathcal{N}(0, \\Sigma)$ whereas $X^{\\star} \\sim \\mathcal{N}(0, \\Sigma^{\\star})$. Why not study: $X_{train} \\overset{i.i.d}\\sim \\mathcal{N}(\\mu, \\Sigma)$ whereas $X^{\\star} \\sim \\mathcal{N}(\\mu^{\\star}, \\Sigma^{\\star})$. Is it because centering the data effectively reduces the aforementioned scenario to the one studied in the paper?\n\n- The notion of a class of covariate shifts is an interesting generalization theoretically. However, in definition 1, it is not particularly clear how monotonicity with respect to a random variable is defined (in this case, w.r.t. $\\lambda$) [Line 175/176].\n\n- Line 115 / 150: $\\sigma : \\mathbb{R}^{n_{0}} \\to \\mathbb{R}^{n_{0}}$ or $\\sigma : \\mathbb{R} \\to \\mathbb{R}$ since it's an elementwise operation.\n\n- Line 132: dimension-normalized trace: this appears to be $tr(A) / n$ if $A \\in \\mathbb{R}^{n \\times n}$ but could help to specify directly early on?\n\n- Equation 7: $\\delta_{a,b}$ is undefined. Is this $\\infty$ if $a = b$ and $0$ otherwise?\n\n- In assumption 1, are we considering asymptotic convergence of the empirical measures as the dimension tends to $\\infty$, because $n_{0}$ is also the size of the covariance in the model. If so, any convergence results also would only make sense if the dimensionality of the inputs increased towards $\\infty$, correct?\n\n- The remarks regarding the implications of Proposition 1 are interesting and make sense, and it is also encouraging to see this partial ordering being satisfied empirical for the identity covariances (and scaled versions) in Fig 1a. Naturally this gives rise to Definition 1 which characterizes difficulty. The family of power-law distributional shifts is well motivated.\n\n- Figure 1b seems to be in agreement with Proposition 3 (similar to Figure 1a with the scaling), and it is again encouraging to see that such patterns can be quantified.\n\n- Proposition 4 is very interesting and non-trivial as the authors remark, but what does the hardness of $\\mu$ mean? Is it with respect to $\\mu_{\\emptyset}$?\n\n- Proposition 5 also provides an explanation of phenomena observed in Figures 3a and 3b. This proposition is also useful and practically applicable with the proliferation of over parameterized methods, again as noted by the authors.\n\n- In conclusion, drawing from the random feature model, the authors have presented an explanation for why overparameterized models perform well in covariate shift. Large scale experiments on CIFAR-10 corroborate their theory: larger shift is hard to work with, but can be partially alleviated with the use of higher number of parameters. While this is not an accurate representation of the input scenario (neural networks), the random feature regression model seems to produce conclusions that are also applicable to such large scale models.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have pointed out some limitations of their analysis in the conclusion section of this submission.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "8fmBk1-_vDB", "reviewer": "Reviewer_i3Dq", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors did hard work to derive analytically the asymptotic limit of the test error for random feature regression with covariate shift, and the experimental results seem to agree with the theory well. However, I found the paper hard to follow and the writing of the paper needs to be improved. Even after several attempts, I still cannot parse the theoretical results in Section 2 and gain useful intuitions from them. This prevents me from evaluating the usefulness and significance of the work. I have no choice but vote rejection.\n\nBelow are several comments/questions I have that may help improve the readability of the paper:\n1. The term \"naturally occurring shift\" is not explained in the paper. Also, I would like to know why the shift considered in the paper only happens in the covariance matrix. Is the shift in mean not natural?\n1. Do you have intuition that could help understand $r_i$, i.e., overlap coefficients, defined on line 131?\n1. Theorem 2 and Corollary 1 are too complicated. It is nice to have the exact (although implicit) form of the test error, but perhaps a more important question is: what intuition/knowledge can we gain from them besides the complicated expressions? It would be largely appreciated if a paragraph parsing these results was provided. Also, the symbol under the limit in (12) is not defined.\n1. On line 225, the authors claim that \"Proposition 3 corroborate the intuitions obtained from linear regression\". The intuition obtained from linear regression is in Definition 1 and the paragraph above it. It is unclear to me how the condition $\\xi \\le 1$ is connected to that.\n1. In Proposition 4, It is said that \"When $\\mu$ is hard, SLOPE $\\ge 1$\". What do you mean by $\\mu$ is hard?\n\nOther comments:\n1. I would like to see references supporting the claim on line 89.\n1. On line 115: should $R^{n_0}$ be $R$?\n1. In Assumption 2, should $\\lVert \\sigma(x) \\rVert$ be $|\\sigma(x)|$?\n\n\n----------------------------------------------------------------------------\n\nUpdates: after reading the authors' response and other reviewers' comments, most of my questions are answered. The partial ordering  characterizing the hardness of distribution shifts is indeed an interesting contribution. However, I do think Th. 2 and Cor. 1 are too complicated and lack explanations. Based on these considerations, I have increased my score to 6.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See comments above for suggestions.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "1Qo7dAh5n4N", "reviewer": "Reviewer_X5kM", "summary": "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.  ", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n### Positive aspects\n\n**Problem setting.**  The setting is very interesting here.  I haven't seen any theoretical work that has done much of anything with this setting.  As covariate shift is known to occur quite often in ML datasets, it's extremely important that we understand how covariate shift impacts test error.  So I think that any theoretical insights toward understanding the impact of covariate shift are quite valuable.\n\n**Results in the linear setting.**  The result of Cor. 1 seems quite interesting.  In particular, it seems that the test error depends on the ratios of the \"projected eigenvalues\" $r_i$ and the $\\lambda_i$.  This is cool, since it gives us a quantitive way (in the admittedly simple case of LR) to think about different magnitudes of covariate shift and their impact on test error.  And it seems to have the nice property that if there is no shift, we get the intuitive asymptotics $\\sigma_\\epsilon^2 \\phi/(1-\\phi)$.  \n\n**Corroboration of the linear trend between clean and corrupted test error.**  There has indeed been a growing recent discussion about the relationship between the clean and corrupted test error of deep models.  Along with [25], this is the first paper I have seen that has sought to theoretically explain the empirically-observed linear relationship between these quantities.  This is a significant contribution.\n\n**A formal way of quantifying how \"hard\" a distribution shift is.**  I liked this notion of \"hardness\" of distribution shifts, which allows us to explicitly quantify the relationship between two distributions, where for example one distribution is the clean data and another is the shifted data.\n\n**Experiments.**  The experiments were a nice touch.  I think that even without the CIFAR-10/CIFAR-10-C experiments, this paper would merit acceptance.  It was interesting (although perhaps unsurprising to see that as the corruption level increased, test accuracy (resp. error) went up (resp. down), and that over-parameterization seemed to improve the accuracy/error.  A small point of confusion was the notation involving $c$.  Is $c$ is the so-called \"challenge-level\" for these datasets?  As far as I can tell, $c$ is never defined.\n\n---\n\n### Notational confusion and lack of intuition\n\nIn my opinion, the notational section has a number of imprecise statements/definitions that make the rest of the paper harder to follow.  In what follows, I'll list the things that tripped me up:\n\n**On the definition of $\\sigma$.**  The activation function $\\sigma$ seems to be defined differently in two separate locations, and I think that both of them are incorrect.  In line 115, we have $\\sigma:\\mathbb{R}^{n_0}\\to\\mathbb{R}$ and in line 150, we have $\\sigma:\\mathbb{R}\\to\\mathbb{R}$.  However, neither of these really make sense.  In the line 115 definition, it is said that $\\sigma$ is applied elementwise.  How can a function mapping to $\\mathbb{R}$ be applied elementwise?  Furthermore, if this is the definition, then we don't need a transpose in the definition of the kernel (3), since $\\sigma(W_1 x_1/\\sqrt{n_0})$ will already be real-valued.  And earlier on, the features $F$ and $f$ would reduce to a single scalar.  But following the standard literature (e.g. [35]), the feature map should be $\\sigma: x\\mapsto \\sigma(Wx)$, which $\\sigma(W\\cdot)$ is an embedding of $x$ into some higher-dimensional feature space.  On the other hand, following the line 150 definition, we place a norm on $\\sigma(x)$, i.e. we write $||\\sigma(x)||$.  If $\\sigma$ is real-valued, why would we need a norm?  The absolute value should suffice.  Similarly, if $\\sigma:\\mathbb{R}\\to\\mathbb{R}$, the gradient will be a scalar, so we also don't need a norm on the derivative $||\\sigma'(x)||$.  \n\nFrom what I can tell, $\\sigma$ should be such that $\\sigma:\\mathbb{R}^{n_1}\\to\\mathbb{R}^{n_1}$.  In this way, it's argument is an element of $\\mathbb{R}^{n_1}$, which couples with the fact that $W_1x_1\\in\\mathbb{R}^{n_1}$.  Further, this $\\sigma$ maps to $\\mathbb{R}^{n_1}$, so its operation (e.g. ReLU, tanh, sigmoid, etc.) can be applied \"elementwise\" in the expected way.  However, if this is incorrect and this is all completely incorrect (which is possible), we can definitely clear things up in the discussion.\n\n**On expectation notation.**  I find it extremely confusing when I cannot tell what the randomness in an expectation is over.  This is the case in the definitions in (6).  First of all, the authors at first say that the randomness in the innermost expectation in (5) is over $W$, $X$, and $\\epsilon$.  But the randomness in $\\epsilon$ should not matter here, because the authors pulled out the label noise, which is evinced by the trailing $\\sigma_{\\epsilon}^2$ term.  Then in (6), I'm unsure of what the randomness in $\\mathbb{E}[\\hat{y}(\\mathbf{x})]$ and $\\mathbb{V}[\\hat{y}(\\mathbf{x})]$ is over.  I thought it might be $\\beta$, but the authors say that we supress the randomness in $\\beta$ due to the assumption that $\\beta$ is sub-Gaussian and therefore concentrates super fast around its mean.  So it's not $\\beta$.  And the middle expectation is apparently over $W_1$, $X$, and $\\epsilon$ (the latter of which is now apparently included despite the fact that it was explicitly factored out in $E_{\\Sigma^\\star}$).  If this is the case, then (as far as I can tell) there is no randomness left!  To summarize, it would help a lot if in these notational sections the authors could explicitly write which expectations correspond to which sources of randomness.\n\n**On the trace notation.**  The authors say that $\\bar{\\text{tr}}$ denotes the \"normalized\" trace.  For an $n\\times n$ matrix, does this mean we normalize by $n$ or by $\\sqrt{n}$?\n\n**Intuition for the overlap coefficients.**  I had a bit of trouble interpreting the overlap coefficients $r_i$.  To me, it seems that for each $i \\in\\{1, \\dots, n_0\\}$, we are projecting the eigenvector $v_i$ of $\\Sigma$ onto the eigenspace spanned by the eigenvectors of $\\Sigma^\\star$.  So $r_i$ is kind of like the an \"eigenvalue\" for $v_i$ in this projected space induced by $\\Sigma^\\star$.  This doesn't agree with the statement that we should consider the spectra of $\\Sigma$ and $\\Sigma^\\star$ in joint eigenbasis of $\\Sigma$ (rather than $\\Sigma^\\star$), as stated on line 134.  Is this the right way to think about it, or have I misunderstood?  This seems like a fundamental quantity in this paper, so I think it would be helpful to build some intuition for the reader.  \n\nAs a side note, it's a bit confusing to use $\\nu$ and $v$ here.  With the wide world of characters open to you, perhaps there is a better choice of symbols that do not look so similar?\n\n**Figure 1.**  It's hard to disentangle the relationship between the plots in Figure 1.  Two things are varying between (a) and (b): the activation and the composition of the covariance matrix.  It would be easier to understand if tanh was used for both, or there were four plots.  In essence, I can't disentangle the impact of the activation and the data mechanism based on this figure.  (Although putting that aside, it is quite interesting that we see this kind of \"double descent\" phenomena with over-parameterization!)\n\n**The behemoth that is Theorem 2.** I was with the authors until around theorem 2, which hit me like a truck.  I think I could spend a full day trying to unpack and intuitively understand this result and the associated quantities in full generality, but reviewing 7 papers in 3 weeks makes such a commitment impossible.  To this end, I think that a gaping hole in the paper is an intuitive explanation of theorem 2.  What is the main takeaway?  While Corollary 1 illustrates this for the ridgeless linear regression (LR) setting, I am still left feeling that I don't understand what most of the associated quantities represent.  For instance, the authors tell us that \n\n\"The structural form of Theorem 2 implies the generalization error under covariate shift exclusively factors through $\\mathcal{I}^\\star$.\"\n\nBut what **is** $\\mathcal{I}^\\star$.  How can I interpret the definition\n\n$$\\mathcal{I}^\\star_{a,b} \\triangleq \\phi\\mathbb{E}_\\mu \\left[ r\\lambda^a(\\phi + x\\lambda)^{-b}\\right]$$\n\nin an intuitive way?  I've stared at this for some time and still have very little idea.  Overall, I think that this lack of intuition is what makes this paper just a \"good\" paper instead of a \"great\" paper.\n\n---\n\n### Final Thoughts\n\nI think that this a good paper that should be accepted.  The results addressing a crucial setting.  And the corollaries of theorem 2 tell us about (1) an ordering on test errors as a function of how \"hard\" the covariate shift is, and (2) an explanation of why over-parameterized models display a linear trend in test error under distribution shift.  The experiments on CIFAR-10 are also quite informative.  I think that as written, this paper is a \"good\" paper that could be made a \"great\" paper if more intuition was added throughout so that a broader class of readers could understand the results.  Also, I think some notational bugs should be sorted out.  But to summarize, I liked the paper a lot, and enjoyed reading it!\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't think that this applies to this paper.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the robustness of overparametrized models to covariate shift between train and test data. The authors study this in the sandbox of random feature regression, by computing the high-dimensional asymptotic limit of the test error in the presence of a shift in the covariance matrix. In this model, they provide analytic solutions, and they corroborate the theory with empirical evidence. 

The reviewers concluded the paper makes a value contribution and should be accepted, but noted that the paper could use improvements to the presentation. In particular, Theorem 2 is rather hard to parse/interpret, and some of the proofs are essentially long calculations that are difficult to follow. This was partially addressed in the discussions, and some of these techniques are standard in the literature. We strongly suggest that the authors address these concerns for the camera ready version. 
Decision: Accept (Poster)