# Computational Efficiency under Covariate Shift in Kernel Ridge Regression

arXiv: https://arxiv.org/abs/2505.14083 · HTML: https://mlsanity.com/paper/2505.14083/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 72 references that are in the map.
- First posted on arXiv 20 May 2025.

## Builds on (most cited first, 24 of 24)

- [WILDS: A Benchmark of in-the-Wild Distribution Shifts](https://mlsanity.com/paper/2012.07421/) (2020)
- [Domain Adaptation for Medical Image Analysis: A Survey](https://mlsanity.com/paper/2102.09508/) (2021)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [Generalization Properties of Learning with Random Features](https://mlsanity.com/paper/1602.04474/) (2016)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [Rethinking Importance Weighting for Deep Learning under Distribution Shift](https://mlsanity.com/paper/2006.04662/) (2020)
- [Less is More: Nystr"om Computational Regularization](https://mlsanity.com/paper/1507.04717/) (2015)
- [Kernel methods through the roof: handling billions of points efficiently](https://mlsanity.com/paper/2006.10350/) (2020)
- [FALKON: An Optimal Large Scale Kernel Method](https://mlsanity.com/paper/1705.10958/) (2017)
- [Multi-Source Deep Domain Adaptation with Weak Supervision for Time-Series Sensor Data](https://mlsanity.com/paper/2005.10996/) (2020)
- [Marginal Singularity, and the Benefits of Labels in Covariate-Shift](https://mlsanity.com/paper/1803.01833/) (2018)
- [Domain Adaptation for Time Series Under Feature and Label Shifts](https://mlsanity.com/paper/2302.03133/) (2023)
- [Optimally tackling covariate shift in RKHS-based nonparametric regression](https://mlsanity.com/paper/2205.02986/) (2022)
- [Near-Optimal Linear Regression under Distribution Shift](https://mlsanity.com/paper/2106.12108/) (2021)
- [On Fast Leverage Score Sampling and Optimal Learning](https://mlsanity.com/paper/1810.13258/) (2018)
- [A new similarity measure for covariate shift with applications to nonparametric regression](https://mlsanity.com/paper/2202.02837/) (2022)
- [Uniform Sampling for Matrix Approximation](https://mlsanity.com/paper/1408.5099/) (2014)
- [But How Does It Work in Theory? Linear SVM with Random Features](https://mlsanity.com/paper/1809.04481/) (2018)
- [Beyond Least-Squares: Fast Rates for Regularized Empirical Risk Minimization through Self-Concordance](https://mlsanity.com/paper/1902.03046/) (2019)
- [Generalization Bounds for Domain Adaptation](https://mlsanity.com/paper/1304.1574/) (2013)
- [Addressing Parameter Choice Issues in Unsupervised Domain Adaptation by Aggregation](https://mlsanity.com/paper/2305.01281/) (2023)
- [When is Importance Weighting Correction Needed for Covariate Shift Adaptation?](https://mlsanity.com/paper/2303.04020/) (2023)
- [Distributed Adaptive Sampling for Kernel Matrix Approximation](https://mlsanity.com/paper/1803.10172/) (2018)

## Built on by (most cited first, 4 of 4)

- [Towards regularized learning from functional data with covariate shift](https://mlsanity.com/paper/2601.21019/) (2026)
- [Error Propagation in Dynamic Programming: From Stochastic Control to American Option Pricing](https://mlsanity.com/paper/2509.20239/) (2025)
- [Convergence Analysis of Nystr"om Subsampling in Covariate Shift Adaptation for Misspecified case](https://mlsanity.com/paper/2606.22259/) (2026)
- [Scalable Operator Learning via Nystr"om Approximation With Denoising Applications](https://mlsanity.com/paper/2606.26652/) (2026)

## Abstract (arXiv)

This paper addresses the covariate shift problem in the context of nonparametric regression within reproducing kernel Hilbert spaces (RKHSs). Covariate shift arises in supervised learning when the input distributions of the training and test data differ, presenting additional challenges for learning. Although kernel methods have optimal statistical properties, their high computational demands in terms of time and, particularly, memory, limit their scalability to large datasets. To address this limitation, the main focus of this paper is to explore the trade-off between computational efficiency and statistical accuracy under covariate shift. We investigate the use of random projections where the hypothesis space consists of a random subspace within a given RKHS. Our results show that, even in the presence of covariate shift, significant computational savings can be achieved without compromising learning performance.