Research map / Learning theory and algorithms / Kernels and regression theory
Minimum-Norm Interpolation Under Covariate Shift
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives the first non-asymptotic excess-risk bounds for the minimum-norm interpolator under covariate shift with commuting source/target covariances, and a taxonomy of beneficial vs malignant shifts depending on mild vs severe overparameterization.
Problem
Understanding how benignly overfit minimum-norm interpolators in high-dimensional linear regression generalize under covariate shift (transfer learning), where prior results were asymptotic, minimax, or gradient-based.
Approach
Non-asymptotic instance-wise variance and bias bounds for the MNI under source/target covariance shift (commuting covariances), which yield a taxonomy of beneficial and malignant shifts determined by eigenvalue ratios on signal vs noise components and by the effective-rank overparameterization measure n/R_k (mild vs severe).
Key results
- Proves non-asymptotic upper and lower bounds on the variance term, tight up to constants when rho_k >= b, reducing to in-distribution bounds when the covariances are equal.
- Taxonomy theorem: alpha<1, beta<=1 (or alpha<=1, beta<1) gives beneficial variance shifts; alpha>1, beta>=1 gives malignant; mild vs severe overparameterization reverses the sign for alpha>1, beta<1 and alpha<1, beta>1.
- On CIFAR-10C, blur acts as beneficial shift and noise as malignant shift for the MNI on binarized CIFAR-10, with OOD accuracy matching the taxonomy in mild (n=500) vs severe (n=2k) regimes.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply blur corruption to CIFAR-10 test images | Minimum-norm interpolator · CIFAR-10C blur | OOD accuracy | Helped |
| Apply noise corruption to CIFAR-10 test images | Minimum-norm interpolator · CIFAR-10C noise | OOD accuracy | Hurt |
| Increase the level of overparameterization | Minimum-norm interpolator on CIFAR-10C corruptions · CIFAR-10C blur and noise | OOD accuracy | Helped |
| Combine blur and noise corruptions in the mildly overparameterized regime | Minimum-norm interpolator · CIFAR-10C combined blur and noise | OOD accuracy | Hurt |
| Combine blur and noise corruptions in the severely overparameterized regime | Minimum-norm interpolator · CIFAR-10C combined blur and noise | OOD accuracy | Helped |
| Apply a covariance shift with α=2.0 and β=0.1 | Minimum-norm interpolator · Synthetic spiked covariance | excess risk | Mixed |
| Apply beneficial and malignant covariance shifts | 3-layer dense ReLU network with p > n · Synthetic Gaussian | OOD excess risk | Mixed |
| Use a low-dimensional input setting, p < n | 3-layer dense ReLU network · Synthetic Gaussian | OOD excess risk | Hurt |
| Train until near-interpolation with hidden width varied | 3-layer dense ReLU network · Synthetic Gaussian, p > n and p < n | OOD excess risk | No clear effect |
Surprising findings
- Shifts that increase trace of target covariance can still be beneficial in the mildly overparameterized regime, and decreasing trace can be malignant.
- On a subset of CIFAR-10C, OOD accuracy can be better than ID accuracy for linear interpolators.
Limitations
- Requires simultaneously diagonalizable source and target covariances and well-specified linear models with subgaussian whitened features.
- Bias bounds leave a gap between lower and upper bounds; variance dominates empirically.
- Neural network experiments are limited to synthetic data and CIFAR-10 with heuristic choice of k.
Experimental setup
Datasets: CIFAR-10 CIFAR-10C synthetic spiked covariance Gaussian data
Benchmarks: CIFAR-10C blur and noise corruptions (custom variants) synthetic spiked covariance data
Metrics: excess risk classification error OOD accuracy
Baselines: in-distribution MNI ridge regression 3-layer ReLU dense networks (ID vs OOD)
Builds on: benign overfitting (Bartlett et al. 2020) ridge regression benign overfitting (Tsigler & Bartlett) CIFAR-10C
Closest papers by meaning
- Transfer Learning for Benign Overfitting in High-Dimensional Linear Regression (NeurIPS 2025 · similarity 0.94)
- Noisy Interpolation Learning with Shallow Univariate ReLU Networks (ICLR 2024 · similarity 0.88)
- Beyond Benign Overfitting in Nadaraya-Watson Interpolators (NeurIPS 2025 · similarity 0.88)
- Transfer Learning of Linear Regression with Multiple Pretrained Models: Benefiting from More Pretrained Models via Overparameterization Debiasing (NeurIPS 2026 · similarity 0.87)
- Benign Overfitting in Out-of-Distribution Generalization of Linear Models (ICLR 2025 · similarity 0.86)
- Rethinking Benign Overfitting in Two-Layer Neural Networks (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.