# Nearest Neighbor Sampling for Covariate Shift Adaptation

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 48 references that are in the map.
- First posted on arXiv 15 Dec 2023.

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

- [Fastfood: Approximate Kernel Expansions in Loglinear Time](https://mlsanity.com/paper/1408.3060/) (2014)
- [Marginal Singularity, and the Benefits of Labels in Covariate-Shift](https://mlsanity.com/paper/1803.01833/) (2018)
- [Optimally tackling covariate shift in RKHS-based nonparametric regression](https://mlsanity.com/paper/2205.02986/) (2022)
- [Efficient multivariate entropy estimation via k-nearest neighbour distances](https://mlsanity.com/paper/1606.00304/) (2016)
- [A One-step Approach to Covariate Shift Adaptation](https://mlsanity.com/paper/2007.04043/) (2020)
- [Estimating and Explaining Model Performance When Both Covariates and Labels Shift](https://mlsanity.com/paper/2209.08436/) (2022)
- [An Information-theoretical Approach to Semi-supervised Learning under Covariate-shift](https://mlsanity.com/paper/2202.12123/) (2022)
- [Local nearest neighbour classification with applications to semi-supervised learning](https://mlsanity.com/paper/1704.00642/) (2017)
- [Pseudo-Labeling for Kernel Ridge Regression under Covariate Shift](https://mlsanity.com/paper/2302.10160/) (2023)
- [ADAPT : Awesome Domain Adaptation Python Toolbox](https://mlsanity.com/paper/2107.03049/) (2021)
- [When can Regression-Adjusted Control Variates Help? Rare Events, Sobolev Embedding and Minimax Optimality](https://mlsanity.com/paper/2305.16527/) (2023)

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

- [Concentration and excess risk bounds for imbalanced classification with synthetic oversampling](https://mlsanity.com/paper/2510.20472/) (2025)
- [Smooth Sailing: Lipschitz-Driven Uncertainty Quantification for Spatial Association](https://mlsanity.com/paper/2502.06067/) (2025)
- [Minimum Wasserstein distance estimator under covariate shift: closed-form, super-efficiency and irregularity](https://mlsanity.com/paper/2601.07282/) (2026)
- [Target-Aware Linear Regression Under Distribution Shift](https://mlsanity.com/paper/2606.22775/) (2026)
- [Local polynomial density ratio estimation](https://mlsanity.com/paper/2609.38412/) (2026)

## Abstract (arXiv)

Many existing covariate shift adaptation methods estimate sample weights given to loss values to mitigate the gap between the source and the target distribution. However, estimating the optimal weights typically involves computationally expensive matrix inversion and hyper-parameter tuning. In this paper, we propose a new covariate shift adaptation method which avoids estimating the weights. The basic idea is to directly work on unlabeled target data, labeled according to the k-nearest neighbors in the source dataset. Our analysis reveals that setting k = 1 is an optimal choice. This property removes the necessity of tuning the only hyper-parameter k and leads to a running time quasi-linear in the sample size. Our results include sharp rates of convergence for our estimator, with a tight control of the mean square error and explicit constants. In particular, the variance of our estimators has the same rate of convergence as for standard parametric estimation despite their non-parametric nature. The proposed estimator shares similarities with some matching-based treatment effect estimators used, e.g., in biostatistics, econometrics, and epidemiology. Our experiments show that it achieves drastic reduction in the running time with remarkable accuracy.