2021

Covariate Shift in High-Dimensional Random Feature Regression

Tripuraneni, Nilesh, Adlam, Ben, Pennington, Jeffrey

Understand

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.

Built on

Priors for infinite networks
R. M. Neal · 1996
Earlier work this paper cites.
On moments of the inverted wishart distribution
D. V. Rosen · 1997
Earlier work this paper cites.
Percolation
G. Grimmett · 1999
Earlier work this paper cites.
Analysis of representations for domain adaptation
S. Ben-David, J. Blitzer, K. Crammer, and F. Pereira · 2006
Earlier work this paper cites.
Spectra of large block matrices
R. R. Far, T. Oraby, W. Bryc, and R. Speicher · 2006
Earlier work this paper cites.
Random features for large-scale kernel machines
A. Rahimi and B. Recht · 2007
Earlier work this paper cites.
Covariate shift adaptation by importance weighted cross validation
M. Sugiyama, M. Krauledat, and K.-R. Müller · 2007
Earlier work this paper cites.
The spectrum of kernel random matrices
N. E. Karoui · 2010
Earlier work this paper cites.
Domain adaptation for large-scale sentiment classification: A deep learning approach
X. Glorot, A. Bordes, and Y. Bengio · 2011
Earlier work this paper cites.
Bulk universality for generalized wigner matrices
L. Erdős, H.-T. Yau, and J. Yin · 2012
Earlier work this paper cites.
Non-linear domain adaptation with boosting
C. J. Becker, C. M. Christoudias, and P. Fua · 2013
Earlier work this paper cites.
Domain adaptation and sample bias correction theory and algorithm for regression
C. Cortes and M. Mohri · 2013
Earlier work this paper cites.
On the limiting spectral distribution for a large class of symmetric random matrices with correlated entries
M. Banna, F. Merlevède, and M. Peligrad · 2015
Earlier work this paper cites.
Explaining and harnessing adversarial examples
Original
I. J. Goodfellow, J. Shlens, and C. Szegedy · 2015
Earlier work this paper cites.
Batch normalization: Accelerating deep network training by reducing internal covariate shift
S. Ioffe and C. Szegedy · 2015
Earlier work this paper cites.
Lecture notes on ridge regression
W. N. van Wieringen · 2015
Earlier work this paper cites.
Fast and accurate deep network learning by exponential linear units (elus)
Original
D. Clevert, T. Unterthiner, and S. Hochreiter · 2016
Earlier work this paper cites.
Sparse pca via covariance thresholding
Y. Deshpande and A. Montanari · 2016
Earlier work this paper cites.
Deep learning
I. Goodfellow, Y. Bengio, and A. Courville · 2016
Earlier work this paper cites.
Unsupervised domain adaptation with residual transfer networks
M. Long, H. Zhu, J. Wang, and M. I. Jordan · 2016
Earlier work this paper cites.
Deep transfer learning with joint adaptation networks
M. Long, H. Zhu, J. Wang, and M. I. Jordan · 2017
Earlier work this paper cites.
Free probability and random matrices , volume 35
J. A. Mingo and R. Speicher · 2017
Earlier work this paper cites.
Exploring generalization in deep learning
B. Neyshabur, S. Bhojanapalli, D. Mcallester, and N. Srebro · 2017
Earlier work this paper cites.
Nonlinear random matrix theory for deep learning
J. Pennington and P. Worah · 2017
Earlier work this paper cites.
High-dimensional asymptotics of prediction: Ridge regression and classification
E. Dobriban and S. Wager · 2018
Earlier work this paper cites.
Applications of realizations (aka linearizations) to free probability
J. W. Helton, T. Mai, and R. Speicher · 2018
Earlier work this paper cites.

Similar

Neural tangent kernel: Convergence and generalization in neural networks
A. Jacot, F. Gabriel, and C. Hongler · 2018
Cited alongside, same era.
Deep neural networks as gaussian processes
J. Lee, Y. Bahri, R. Novak, S. S. Schoenholz, J. Pennington, and J. Sohl-Dickstein · 2018
Cited alongside, same era.
A random matrix approach to neural networks
C. Louart, Z. Liao, R. Couillet, et al · 2018
Cited alongside, same era.
Towards deep learning models resistant to adversarial attacks
A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu · 2018
Cited alongside, same era.
The spectrum of the fisher information matrix of a single-hidden-layer neural network
J. Pennington and P. Worah · 2018
Cited alongside, same era.
Do cifar-10 classifiers generalize to cifar-10?
Original
B. Recht, R. Roelofs, L. Schmidt, and V. Shankar · 2018
Cited alongside, same era.
Adversarially robust generalization requires more data
L. Schmidt, S. Santurkar, D. Tsipras, K. Talwar, and A. Madry · 2018
Cited alongside, same era.
High-Dimensional Probability: An Introduction with Applications in Data Science
R. Vershynin · 2018
Cited alongside, same era.
Adversarial multiple source domain adaptation
H. Zhao, S. Zhang, G. Wu, J. M. F. Moura, J. P. Costeira, and G. J. Gordon · 2018
Cited alongside, same era.
A random matrix perspective on mixtures of nonlinearities for deep learning
Original
B. Adlam, J. Levinson, and J. Pennington · 2019
Cited alongside, same era.
Reconciling modern machine-learning practice and the classical bias–variance trade-off
M. Belkin, D. Hsu, S. Ma, and S. Mandal · 2019
Cited alongside, same era.
The matrix dyson equation and its applications for random matrices
Original
L. Erdos · 2019
Cited alongside, same era.

Then

The gaussian equivalence of generative models for learning with two-layer neural networks
S. Goldt, G. Reeves, M. Mézard, F. Krzakala, and L. Zdeborová · 2020
Later among the works it cites.
The optimal ridge penalty for real-world high-dimensional data can be zero or negative due to the implicit ridge regularization
D. Kobak, J. Lomond, and B. Sanchez · 2020
Later among the works it cites.
Understanding self-training for gradual domain adaptation
A. Kumar, T. Ma, and P. Liang · 2020
Later among the works it cites.
Finite versus infinite neural networks: an empirical study
J. Lee, S. Schoenholz, J. Pennington, B. Adlam, L. Xiao, R. Novak, and J. Sohl-Dickstein · 2020
Later among the works it cites.
A random matrix analysis of random fourier features: beyond the gaussian kernel, a precise phase transition, and the corresponding double descent
Z. Liao, R. Couillet, and M. W. Mahoney · 2020
Later among the works it cites.
What causes the test error? going beyond bias-variance via anova
L. Lin and E. Dobriban · 2020
Later among the works it cites.
The effect of natural distribution shift on question answering models
J. Miller, K. Krauth, B. Recht, and L. Schmidt · 2020
Later among the works it cites.
Evaluating prediction-time batch normalization for robustness under covariate shift
Original
Z. Nado, S. Padhy, D. Sculley, A. D’Amour, B. Lakshminarayanan, and J. Snoek · 2020
Later among the works it cites.
Distributionally robust neural networks
S. Sagawa, P. W. Koh, T. B. Hashimoto, and P. Liang · 2020
Later among the works it cites.
Neural kernels without tangents
V. Shankar, A. Fang, W. Guo, S. Fridovich-Keil, J. Ragan-Kelley, L. Schmidt, and B. Recht · 2020
Later among the works it cites.
Measuring robustness to natural distribution shifts in image classification
R. Taori, A. Dave, V. Shankar, N. Carlini, B. Recht, and L. Schmidt · 2020
Later among the works it cites.
On the optimal weighted ℓ 2 \ell_{2} regularization in overparameterized linear regression
D. Wu and J. Xu · 2020
Later among the works it cites.
Deep learning: a statistical viewpoint, 2021
P. L. Bartlett, A. Montanari, and A. Rakhlin · 2021
Closest in time.
Provable benefits of overparameterization in model compression: From double descent to pruning neural networks
X. Chang, Y. Li, S. Oymak, and C. Thrampoulidis · 2021
Closest in time.
Learning models with uniform performance via distributionally robust optimization
J. C. Duchi and H. Namkoong · 2021
Closest in time.
The many faces of robustness: A critical analysis of out-of-distribution generalization
D. Hendrycks, S. Basart, N. Mu, S. Kadavath, F. Wang, E. Dorundo, R. Desai, T. Zhu, S. Parajuli, M. Guo, D. Song, J. Steinhardt, and J. Gilmer · 2021
Closest in time.
Wilds: A benchmark of in-the-wild distribution shifts
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, and P. Liang · 2021
Closest in time.
Near-optimal linear regression under distribution shift
Q. Lei, W. Hu, and J. Lee · 2021
Closest in time.
Why do classifier accuracies show linear trends under distribution shift?, 2021
H. Mania and S. Sra · 2021
Closest in time.
The generalization error of random features regression: Precise asymptotics and the double descent curve
S. Mei and A. Montanari · 2021
Closest in time.
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
G. Mel and S. Ganguli · 2021
Closest in time.
Accuracy on the line: on the strong correlation between out-of-distribution and in-distribution generalization
J. P. Miller, R. Taori, A. Raghunathan, S. Sagawa, P. W. Koh, V. Shankar, P. Liang, Y. Carmon, and L. Schmidt · 2021
Closest in time.
Asymptotics of ridge(less) regression under general source condition
D. Richards, J. Mourtada, and L. Rosasco · 2021
Closest in time.
Overparameterization improves robustness to covariate shift in high dimensions
N. Tripuraneni, B. Adlam, and J. Pennington · 2021
Closest in time.
Exact gap between generalization error and uniform convergence in random feature models
Z. Yang, Y. Bai, and S. Mei · 2021
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…