# Fast Computation of Leave-One-Out Cross-Validation for k-NN Regression

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 19 references that are in the map.
- First posted on arXiv 8 May 2024.

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

- [Conditional independence testing based on a nearest-neighbor estimator of conditional mutual information](https://mlsanity.com/paper/1709.01447/) (2017)
- [Marginal Singularity, and the Benefits of Labels in Covariate-Shift](https://mlsanity.com/paper/1803.01833/) (2018)
- [Empirical Bayes mean estimation with nonparametric errors via order statistic regression on replicated data](https://mlsanity.com/paper/1911.05970/) (2019)
- [Numerical Data Imputation for Multimodal Data Sets: A Probabilistic Nearest-Neighbor Kernel Density Approach](https://mlsanity.com/paper/2306.16906/) (2023)
- [Conditional Mean and Variance Estimation via textitk-NN Algorithm with Automated Variance Selection](https://mlsanity.com/paper/2402.01635/) (2024)

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

- [kNNSampler: Stochastic Imputations for Recovering Missing Value Distributions](https://mlsanity.com/paper/2509.08366/) (2025)
- [Fast and Interpretable Machine Learning Modelling of Atmospheric Molecular Clusters](https://mlsanity.com/paper/2509.11728/) (2025)
- [Predictive Uncertainty in Short-Term PV Forecasting under Missing Data: A Multiple Imputation Approach](https://mlsanity.com/paper/2603.15564/) (2026)
- [Machine-Learning Emulation of Satellite Greenhouse Gas Retrievals: Stability over Time](https://mlsanity.com/paper/2606.09313/) (2026)

## Abstract (arXiv)

We describe a fast computation method for leave-one-out cross-validation (LOOCV) for k-nearest neighbours (k-NN) regression. We show that, under a tie-breaking condition for nearest neighbours, the LOOCV estimate of the mean square error for k-NN regression is identical to the mean square error of (k+1)-NN regression evaluated on the training data, multiplied by the scaling factor (k+1)2/k2. Therefore, to compute the LOOCV score, one only needs to fit (k+1)-NN regression only once, and does not need to repeat training-validation of k-NN regression for the number of training data. Numerical experiments confirm the validity of the fast computation method.