# A Bayes consistent 1-NN classifier

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jul 2014.

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

- [Optimal Binary Classification Beyond Accuracy](https://mlsanity.com/paper/2107.01777/) (2021)
- [Metric-valued regression](https://mlsanity.com/paper/2202.03045/) (2022)
- [Explaining the Success of Nearest Neighbor Methods in Prediction](https://mlsanity.com/paper/2502.15900/) (2025)
- [Near-Exponential Convergence Rates for kNN Classification based on Boltzmann Margin](https://mlsanity.com/paper/2606.10361/) (2026)

## Abstract (arXiv)

We show that a simple modification of the 1-nearest neighbor classifier yields a strongly Bayes consistent learner. Prior to this work, the only strongly Bayes consistent proximity-based method was the k-nearest neighbor classifier, for k growing appropriately with sample size. We will argue that a margin-regularized 1-NN enjoys considerable statistical and algorithmic advantages over the k-NN classifier. These include user-friendly finite-sample error bounds, as well as time- and memory-efficient learning and test-point evaluation algorithms with a principled speed-accuracy tradeoff. Encouraging empirical results are reported.