# Benefit of Interpolation in Nearest Neighbor Algorithms

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Sep 2019.

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

- [Machine learning for modelling unstructured grid data in computational physics: a review](https://mlsanity.com/paper/2502.09346/) (2025)
- [A Diffusion-Based Framework for Terrain-Aware Remote Sensing Image Reconstruction](https://mlsanity.com/paper/2504.12112/) (2025)
- [Locally Adaptive and Differentiable Regression](https://mlsanity.com/paper/2308.07418/) (2023)
- [On damage of interpolation to adversarial robustness in regression](https://mlsanity.com/paper/2601.16070/) (2026)
- [Fitting Elephants](https://mlsanity.com/paper/2104.00526/) (2021)

## Abstract (arXiv)

The over-parameterized models attract much attention in the era of data science and deep learning. It is empirically observed that although these models, e.g. deep neural networks, over-fit the training data, they can still achieve small testing error, and sometimes even em outperform traditional algorithms which are designed to avoid over-fitting. The major goal of this work is to sharply quantify the benefit of data interpolation in the context of nearest neighbors (NN) algorithm. Specifically, we consider a class of interpolated weighting schemes and then carefully characterize their asymptotic performances. Our analysis reveals a U-shaped performance curve with respect to the level of data interpolation, and proves that a mild degree of data interpolation em strictly improves the prediction accuracy and statistical stability over those of the (un-interpolated) optimal kNN algorithm. This theoretically justifies (predicts) the existence of the second U-shaped curve in the recently discovered double descent phenomenon. Note that our goal in this study is not to promote the use of interpolated-NN method, but to obtain theoretical insights on data interpolation inspired by the aforementioned phenomenon.