Research map / Learning theory and algorithms / Kernels and regression theory
Computational Efficiency under Covariate Shift in Kernel Ridge Regression
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.
Studies Nyström-subsampled importance-weighted kernel ridge regression under covariate shift, showing it matches full IW-KRR's optimal rates with much lower time and memory cost.
Problem
Kernel ridge regression under covariate shift (train and test input marginals differ) is costly in time and memory (O(n^3), O(n^2)), so scalable alternatives must preserve statistical accuracy under importance-weighting correction.
Approach
Apply importance-weighted KRR restricted to a random Nyström subspace (with approximate leverage score sampling), proving excess-risk bounds that match full weighted KRR rates even for unbounded importance weights, via a moment-based weight assumption.
Key results
- On HAR70+ (n=20000), W-Nyström KRR reaches MSE 5.1±0.2 vs 5.0±0.2 for full W-KRR, with training time 89 s vs 1785 s, using m=1100 Nyström centers.
- On HARChildren, HHAR, and WISDM, W-Nyström KRR matches W-KRR MSE (13.2 vs 13.5; 1.8 vs 1.8; 4.7 vs 4.8) while training in roughly 8 s, 6.5 s, and 9.9 s versus about 809 s, 1034 s, and 3364 s for W-KRR.
- Theory: with ALS sampling and m ~ n^{γ/(2r+γ)} log n, the Nyström IW-KRR attains the same rate as full IW-KRR, O((||w||_∞/n)^{2r/(2r+γ)}) for bounded weights; for unbounded weights (q=1) the rate is O(n^{-2r/(2r+1)}).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Nyström approximation for importance-weighted KRR | KRR · HAR70+ | MSE: 5.0\pm 0.2 -> 5.1\pm 0.2 | No clear effect |
| Use Nyström approximation for importance-weighted KRR | KRR · HARChildren | MSE: 13.5\pm 0.8 -> 13.2\pm 0.6 | No clear effect |
| Use Nyström approximation for importance-weighted KRR | KRR · HHAR | MSE: 1.8\pm 0.3 -> 1.8\pm 0.1 | No clear effect |
| Use Nyström approximation for importance-weighted KRR | KRR · WISDM | MSE: 4.8\pm 0.2 -> 4.7\pm 0.3 | No clear effect |
| Use Nyström approximation for importance-weighted KRR | KRR · HAR70+ | training time (s): 1785\pm 2 -> 89\pm 19 | Helped |
| Use Nyström approximation for importance-weighted KRR | KRR · HARChildren | training time (s): 809\pm 26 -> 8.0\pm 0.2 | Helped |
| Use Nyström approximation for importance-weighted KRR | KRR · HHAR | training time (s): 1034\pm 93 -> 6.5\pm 0.4 | Helped |
| Use Nyström approximation for importance-weighted KRR | KRR · WISDM | training time (s): 3364\pm 30 -> 9.9\pm 0.4 | Helped |
| Use Nyström approximation for importance-weighted KRR | KRR · HAR70+ | prediction time (s): 15.1\pm 0.3 -> 1.0\pm 0.1 | Helped |
| Use Nyström approximation for importance-weighted KRR | KRR · HARChildren | prediction time (s): 9.0\pm 0.1 -> 1.6\pm 0.1 | Helped |
| Use Nyström approximation for importance-weighted KRR | KRR · HHAR | prediction time (s): 9.9\pm 0.1 -> 1.1\pm 0.1 | Helped |
| Use Nyström approximation for importance-weighted KRR | KRR · WISDM | prediction time (s): 33\pm 2 -> 1.4\pm 0.1 | Helped |
Surprising findings
- Under well-specified targets, the unweighted Nyström KRR (v≡1) attains the same rate in n as the importance-weighted variant, though the constant depends on ||w||_∞.
Limitations
- Misspecified case: the bias term ||f_v - f_H|| can be large when the weight-estimate distribution differs from the test distribution, so guarantees are weaker.
- Bounds depend on ||w||_∞ or unbounded-weight moments, and weights are assumed known in theory; real experiments use RuLSIF estimates.
- Real-data experiments reduce dataset sizes due to memory limits of full KRR, and use a single source-target user split.
Experimental setup
Datasets: HHAR WISDM HAR70+ HARChildren synthetic Gaussian regression data
Benchmarks: HAR70+ HARChildren HHAR WISDM synthetic Gaussian regression
Metrics: MSE training time prediction time
Baselines: KRR W-KRR
Builds on: Kernel ridge regression under covariate shift with importance weighting (Kpotufe Nyström KRR with leverage scores (Rudi et al.) RuLSIF density ratio estimation
Closest papers by meaning
- Towards a Unified Analysis of Kernel-based Methods Under Covariate Shift (NeurIPS 2023 · similarity 0.93)
- High-Dimensional Kernel Methods under Covariate Shift: Data-Dependent Implicit Regularization (ICML 2024 · similarity 0.91)
- A Comprehensive Analysis on the Learning Curve in Kernel Ridge Regression (NeurIPS 2024 · similarity 0.87)
- Towards Theoretical Understanding of Learning Large-scale Dependent Data via Random Features (ICML 2024 · similarity 0.86)
- Out of the Ordinary: Spectrally Adapting Regression for Covariate Shift (ICML 2024 · similarity 0.86)
- Optimal Ridge Regularization for Out-of-Distribution Prediction (ICML 2024 · similarity 0.85)
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.