# Statistical Optimality of Interpolated Nearest Neighbor Algorithms

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

## Key facts

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

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

- [Mitigating multiple descents: A model-agnostic framework for risk monotonization](https://mlsanity.com/paper/2205.12937/) (2022)
- [Benefit of Interpolation in Nearest Neighbor Algorithms](https://mlsanity.com/paper/2202.11817/) (2022)
- [Fitting Elephants](https://mlsanity.com/paper/2104.00526/) (2021)

## Abstract (arXiv)

In the era of deep learning, understanding over-fitting phenomenon becomes increasingly important. It is observed that carefully designed deep neural networks achieve small testing error even when the training error is close to zero. One possible explanation is that for many modern machine learning algorithms, over-fitting can greatly reduce the estimation bias, while not increasing the estimation variance too much. To illustrate the above idea, we prove that the proposed interpolated nearest neighbor algorithm achieves the minimax optimal rate in both regression and classification regimes, and observe that they are empirically better than the traditional k nearest neighbor method in some cases.