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.
abstractText: 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.
authors.name: Nilesh Tripuraneni
authors.name: U.C. Berkeley
authors.name: Ben Adlam
authors.name: Jeffrey Pennington
references.authors: B. Adlam J. Levinson J. Pennington
references.title: A random matrix perspective on mixtures of nonlinearities for deep learning
references.venue: arXiv preprint arXiv:1912.00827
references.authors: B. Adlam J. Pennington
references.title: The neural tangent kernel in high dimensions: Triple descent and a multi-scale theory of generalization
references.venue: Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 74–84. PMLR
references.authors: B. Adlam J. Pennington
references.title: Understanding double descent requires a fine-grained bias-variance decomposition
references.venue: 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.
references.authors: M.S. Advani A.M. Saxe H. Sompolinsky
references.title: High-dimensional dynamics of generalization error in neural networks
references.venue: Neural Networks, 132:428–446
references.authors: M. Banna F. Merlevède M. Peligrad
references.title: On the limiting spectral distribution for a large class of symmetric random matrices with correlated entries
references.venue: Stochastic Processes and their Applications, 125(7):2700–2726
references.authors: M. Banna J. Najim J. Yao
references.title: A CLT for linear spectral statistics of large random informationplus-noise matrices
references.venue: Stochastic Processes and their Applications, 130(4):2250–2281
references.authors: P.L. Bartlett A. Montanari
references.title: and A
references.venue: Rakhlin. Deep learning: a statistical viewpoint
references.authors: C.J. Becker C.M. Christoudias P. Fua
references.title: Non-linear domain adaptation with boosting
references.venue: 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.
references.authors: M. Belkin D. Hsu S. Ma S. Mandal
references.title: Reconciling modern machine-learning practice and the classical bias–variance trade-off
references.venue: Proceedings of the National Academy of Sciences, 116(32):15849–15854
references.authors: S. Ben-David J. Blitzer K. Crammer F. Pereira
references.title: Analysis of representations for domain adaptation
references.venue: B. Schölkopf, J. Platt, and T. Hoffman, editors, Advances in Neural Information Processing Systems, volume 19. MIT Press
references.authors: C. Cortes M. Mohri
references.title: Domain adaptation and sample bias correction theory and algorithm for regression
references.venue: Theor. Comput. Sci., 519:103–126
references.authors: A. D’Amour K. Heller D. Moldovan B. Adlam B. Alipanahi A. Beutel C. Chen J. Deaton J. Eisenstein M.D. Hoffman
references.title: Underspecification presents challenges for credibility in modern machine learning
references.venue: arXiv preprint arXiv:2011.03395,
references.authors: Y. Deshpande A. Montanari
references.title: Sparse pca via covariance thresholding
references.venue: Journal of Machine Learning Research, 17(141):1–41
references.authors: E. Dobriban S. Wager
references.title: High-dimensional asymptotics of prediction: Ridge regression and classification
references.venue: The Annals of Statistics, 46(1):247 – 279
references.authors: J. Duchi T. Hashimoto
references.title: and H
references.venue: Namkoong. Distributionally robust losses for latent covariate mixtures
references.authors: J.C. Duchi H. Namkoong
references.title: Learning models with uniform performance via distributionally robust optimization
references.venue: The Annals of Statistics, 49(3):1378 – 1406
references.authors: L. Erdos
references.title: The matrix dyson equation and its applications for random matrices
references.venue: arXiv preprint arXiv:1903.10060
references.authors: L. Erdős H.-T. Yau J. Yin
references.title: Bulk universality for generalized wigner matrices
references.venue: Probability Theory and Related Fields, 154(1-2):341–407
references.authors: R.R. Far T. Oraby W. Bryc R. Speicher
references.title: Spectra of large block matrices
references.venue: arXiv preprint cs/0610045
references.authors: X. Glorot A. Bordes Y. Bengio
references.title: Domain adaptation for large-scale sentiment classification: A deep learning approach
references.venue: Proceedings of the 28th International Conference on International Conference on Machine Learning, ICML’11, page 513–520, Madison, WI, USA
references.authors: I. Goodfellow Y. Bengio A. Courville
references.title: Deep learning
references.venue: MIT press
references.authors: I.J. Goodfellow J. Shlens C. Szegedy
references.title: Explaining and harnessing adversarial examples
references.venue: 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
references.authors: G. Grimmett
references.title: Percolation
references.venue: Percolation, pages 1–31. Springer
references.authors: T. Hastie A. Montanari S. Rosset R.J. Tibshirani
references.title: Surprises in high-dimensional ridgeless least squares interpolation
references.venue: arXiv preprint arXiv:1903.08560
references.authors: J.W. Helton T. Mai R. Speicher
references.title: Applications of realizations (aka linearizations) to free probability
references.venue: Journal of Functional Analysis, 274(1):1–79
references.authors: D. Hendrycks S. Basart N. Mu S. Kadavath F. Wang E. Dorundo R. Desai T. Zhu S. Parajuli M. Guo D. Song J. Steinhardt J. Gilmer
references.title: The many faces of robustness: A critical analysis of out-of-distribution generalization
references.venue: In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV),
references.authors: D. Hendrycks T.G. Dietterich
references.title: Benchmarking neural network robustness to common corruptions and perturbations
references.venue: 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net
references.authors: S. Ioffe C. Szegedy
references.title: Batch normalization: Accelerating deep network training by reducing internal covariate shift
references.venue: Proceedings of the 32nd International Conference on International Conference on Machine Learning - Volume 37, ICML’15, page 448–456. JMLR.org
references.authors: A. Jacot F. Gabriel C. Hongler
references.title: Neural tangent kernel: Convergence and generalization in neural networks
references.venue: Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS’18, page 8580–8589, Red Hook, NY, USA
references.authors: D. Kobak J. Lomond B. Sanchez
references.title: The optimal ridge penalty for real-world highdimensional data can be zero or negative due to the implicit ridge regularization
references.venue: Journal of Machine Learning Research, 21(169):1–16
references.authors: P.W. Koh S. Sagawa H. Marklund S.M. Xie M. Zhang A. Balsubramani W. Hu M. Yasunaga R.L. Phillips I. Gao T. Lee E. David I. Stavness W. Guo B. Earnshaw I. Haque S.M. Beery J. Leskovec A. Kundaje E. Pierson S. Levine C. Finn P. Liang
references.title: Wilds: A benchmark of in-the-wild distribution shifts
references.venue: Proceedings of the 38th International Conference on Machine Learning,
references.authors: A. Kumar T. Ma P. Liang
references.title: Understanding self-training for gradual domain adaptation
references.venue: Proceedings of the 37th International Conference on Machine Learning,
references.authors: J. Lee Y. Bahri R. Novak S.S. Schoenholz J. Pennington J. Sohl-Dickstein
references.title: Deep neural networks as gaussian processes
references.venue: 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. OpenReview.net
references.authors: J. Lee S. Schoenholz J. Pennington B. Adlam L. Xiao R. Novak J. Sohl-Dickstein
references.title: Finite versus infinite neural networks: an empirical study
references.venue: 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.
references.authors: Z. Liao R. Couillet M.W. Mahoney
references.title: A random matrix analysis of random fourier features: beyond the gaussian kernel
references.venue: 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 13939–13950. Curran Associates, Inc.
references.authors: M. Long H. Zhu J. Wang M.I. Jordan
references.title: Unsupervised domain adaptation with residual transfer networks
references.venue: Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS’16, page 136–144, Red Hook, NY, USA
references.authors: M. Long H. Zhu J. Wang M.I. Jordan
references.title: Deep transfer learning with joint adaptation networks
references.venue: Proceedings of the 34th International Conference on Machine Learning,
references.authors: C. Louart Z. Liao R. Couillet
references.title: et al
references.venue: A random matrix approach to neural networks. The Annals of Applied Probability, 28(2):1190–1248
references.authors: A. Madry A. Makelov L. Schmidt D. Tsipras A. Vladu
references.title: Towards deep learning models resistant to adversarial attacks
references.venue: 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. OpenReview.net
references.authors: H. Mania S. Sra
references.title: Why do classifier accuracies show linear trends under distribution shift
references.authors: S. Mei A. Montanari
references.title: The generalization error of random features regression: Precise asymptotics and the double descent curve
references.venue: Communications on Pure and Applied Mathematics,
references.authors: G. Mel S. Ganguli
references.title: 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
references.venue: Proceedings of the 38th International Conference on Machine Learning,
references.authors: J. Miller K. Krauth B. Recht L. Schmidt
references.title: The effect of natural distribution shift on question answering models
references.venue: Proceedings of the 37th International Conference on Machine Learning,
references.authors: J.P. Miller R. Taori A. Raghunathan S. Sagawa P.W. Koh V. Shankar P. Liang Y. Carmon L. Schmidt
references.title: Accuracy on the line: on the strong correlation between out-of-distribution and in-distribution generalization
references.venue: Proceedings of the 38th International Conference on Machine Learning,
references.authors: J.A. Mingo R. Speicher
references.title: Free probability and random matrices
references.venue: volume 35. Springer
references.authors: Z. Nado S. Padhy D. Sculley
references.title: A
references.venue: D’Amour, B. Lakshminarayanan, and J. Snoek. Evaluating prediction-time batch normalization for robustness under covariate shift. arXiv preprint arXiv:2006.10963
references.authors: V. Nagarajan J.Z. Kolter
references.title: Uniform convergence may be unable to explain generalization in deep learning
references.venue: H. Wallach, H. Larochelle, A. Beygelzimer, F. d Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc.
references.authors: R.M. Neal
references.title: Priors for infinite networks
references.venue: Bayesian Learning for Neural Networks, pages 29–53. Springer
references.authors: B. Neyshabur S. Bhojanapalli D. Mcallester N. Srebro
references.title: Exploring generalization in deep learning
references.venue: 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.
references.authors: Y. Ovadia E. Fertig J. Ren Z. Nado D. Sculley S. Nowozin J. Dillon B. Lakshminarayanan J. Snoek
references.title: Can you trust your models uncertainty? evaluating predictive uncertainty under dataset shift
references.venue: H. Wallach, H. Larochelle, A. Beygelzimer, F. d Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc.
references.authors: S. Péché
references.title: A note on the pennington-worah distribution
references.venue: Electronic Communications in Probability,
references.authors: J. Pennington P. Worah
references.title: Nonlinear random matrix theory for deep learning
references.venue: 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.
references.authors: J. Pennington P. Worah
references.title: The spectrum of the fisher information matrix of a single-hiddenlayer neural network
references.venue: 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.
references.authors: A. Rahimi B. Recht
references.title: Random features for large-scale kernel machines
references.venue: J. Platt, D. Koller, Y. Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc.
references.authors: B. Recht R. Roelofs L. Schmidt
references.title: and V
references.venue: Shankar. Do cifar-10 classifiers generalize to cifar-10? arXiv preprint arXiv:1806.00451
references.authors: B. Recht R. Roelofs L. Schmidt V. Shankar
references.title: Do imagenet classifiers generalize to imagenet? In K
references.venue: Chaudhuri and R. 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 5389–5400. PMLR
references.authors: D. Richards J. Mourtada L. Rosasco
references.title: Asymptotics of ridge(less) regression under general source condition
references.venue: Proceedings of The 24th International Conference on Artificial Intelligence and Statistics,
references.authors: D.V. Rosen
references.title: On moments of the inverted wishart distribution
references.venue: Statistics, 30(3):259–278
references.authors: S. Sagawa P.W. Koh T.B. Hashimoto P. Liang
references.title: Distributionally robust neural networks
references.venue: 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net
references.authors: L. Schmidt S. Santurkar D. Tsipras K. Talwar A. Madry
references.title: Adversarially robust generalization requires more data
references.venue: 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.
references.authors: V. Shankar A. Fang W. Guo S. Fridovich-Keil J. Ragan-Kelley L. Schmidt B. Recht
references.title: Neural kernels without tangents
references.venue: Proceedings of the 37th International Conference on Machine Learning,
references.authors: M. Sugiyama M. Krauledat K.-R. Müller
references.title: Covariate shift adaptation by importance weighted cross validation
references.venue: Journal of Machine Learning Research, 8(35):985–1005
references.authors: R. Taori A. Dave V. Shankar N. Carlini B. Recht L. Schmidt
references.title: Measuring robustness to natural distribution shifts in image classification
references.venue: 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.
references.authors: N. Tripuraneni B. Adlam J. Pennington
references.title: Covariate shift in high-dimensional random feature regression
references.venue: arXiv preprint arXiv:2111.08234
references.authors: R. Vershynin
references.title: High-Dimensional Probability: An Introduction with Applications in Data Science
references.venue: Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press
references.authors: M.J. Wainwright
references.title: High-Dimensional Statistics: A Non-Asymptotic Viewpoint
references.venue: Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press
references.authors: D. Wu J. Xu
references.title: On the optimal weighted `2 regularization in overparameterized linear regression
references.venue: 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.
references.authors: Z. Yang Y. Bai S. Mei
references.title: Exact gap between generalization error and uniform convergence in random feature models
references.venue: M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 11704–11715. PMLR
references.authors: H. Zhao R.T.D. Combes K. Zhang G. Gordon
references.title: On learning invariant representations for domain adaptation
references.venue: Proceedings of the 36th International Conference on Machine Learning,
references.authors: H. Zhao S. Zhang G. Wu J.M.F. Moura J.P. Costeira G.J. Gordon
references.title: Adversarial multiple source domain adaptation
references.venue: 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.
sections.heading: 1 Introduction
sections.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].
sections.heading: 1.1 Contributions
sections.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).
sections.heading: 1.2 Related work
sections.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].
sections.heading: 2 Preliminaries
sections.heading: 2.1 Problem setup and notation
sections.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.
sections.heading: 2.2 Assumptions
sections.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.
sections.heading: 2.3 A simple family of diatomic distributions
sections.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.
sections.heading: 3 Motivating example: linear regression
sections.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.
sections.heading: 4 Definition of shift strength
sections.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].
sections.heading: 5 Covariate shift in random feature kernel regression
sections.heading: 5.1 Main results
sections.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).
sections.heading: 5.2 Harder shifts increase the bias and test error
sections.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.
sections.heading: 5.3 The benefit of overparameterization
sections.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 > .
sections.heading: 5.4 Linear trends between in-distribution and out-of-distribution generalization
sections.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.
sections.heading: 5.5 Importance of assumptions
sections.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].
sections.heading: 6 Conclusion
sections.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.
title: Overparameterization Improves Robustness to Covariate Shift in High Dimensions