Research map / Learning theory and algorithms / Kernels and regression theory
High-Dimensional Kernel Methods under Covariate Shift: Data-Dependent Implicit Regularization
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.
Theoretical analysis of kernel ridge regression in high dimensions under covariate shift, showing importance re-weighting acts as data-dependent implicit regularization that can reduce variance while bias splits into intrinsic and re-weighting terms.
Problem
Understanding how importance re-weighting affects the bias-variance trade-off of kernel ridge regression under covariate shift in the high-dimensional regime (n/d tends to a constant).
Approach
Derives asymptotic (linearized) expansions of inner-product and radial kernels under covariate shift, showing the re-weighting matrix enters the variance and bias through the spectrum of a data-dependent regularized kernel, so re-weighting acts as data-dependent regularization.
Key results
- Variance is upper bounded by a data-dependent effective dimension N(XX^T/d + (lambda n/beta_p) W̄^{-1}; gamma_p/beta_p), so suitable re-weighting can decrease variance.
- Bias splits into an intrinsic term Tr(K^lin W)/n that does not depend on the re-weighting choice plus a re-weighting bias that vanishes as lambda goes to 0.
- Under a well-chosen polynomial decay lambda ~ n^{-c}, the bias converges to zero at rate n^{-r c_lambda + c_H} under the stated source and capacity conditions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply importance re-weighting to high-dimensional kernel ridge regression | Kernel ridge regression under covariate shift · Covariate shift | variance | Helped |
| Use a data-dependent regularized kernel induced by re-weighting | Importance-weighted kernel ridge regression · Covariate shift | variance bound | Helped |
| Choose re-weighting weights that reduce the effective dimension of the data-dependent regularized kernel | Importance-weighted kernel ridge regression · Covariate shift | variance | Helped |
| Choose the re-weighting function as the importance ratio and let regularization tend to zero | Importance-weighted kernel ridge regression · Covariate shift | bias | Mixed |
| Use a well-chosen regularization parameter that decays with sample size | Importance-weighted kernel ridge regression · Covariate shift | bias | Helped |
| Use a sufficiently small regularization parameter | Importance-weighted kernel ridge regression · Covariate shift | re-weighting bias | Helped |
| Use importance re-weighting in the interpolation setting | Kernel interpolation · Covariate shift | estimator | No clear effect |
| Use importance re-weighting to reduce variance while accounting for its effect on intrinsic bias | Importance-weighted kernel ridge regression · Covariate shift | excess risk | Mixed |
Surprising findings
- Intrinsic bias from covariate shift cannot be reduced by any choice of re-weighting matrix, only the variance and re-weighting bias can be reduced.
Limitations
- Results are only upper bounds plus empirical validation; no exact asymptotic formulas for bias and variance.
- Analysis restricted mainly to inner-product kernels; radial kernel results require extra terms not handled.
- Requires covariate shift similarity condition c_pq < 2 theta_q - 1/2 to control kernel approximation residuals.
Experimental setup
Metrics: bias variance excess risk
Builds on: El Karoui kernel random matrix expansion importance weighting for covariate shift source condition / capacity condition analyses of kernel ridge regression
Closest papers by meaning
- Computational Efficiency under Covariate Shift in Kernel Ridge Regression (NeurIPS 2025 · similarity 0.91)
- A Comprehensive Analysis on the Learning Curve in Kernel Ridge Regression (NeurIPS 2024 · similarity 0.87)
- Generalization in Kernel Regression Under Realistic Assumptions (ICML 2024 · similarity 0.87)
- Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionality (NeurIPS 2024 · similarity 0.86)
- Optimal Ridge Regularization for Out-of-Distribution Prediction (ICML 2024 · similarity 0.86)
- Kernel Regression in Structured Non-IID Settings: Theory and Implications for Denoising Score Learning (NeurIPS 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.