# Explaining the Success of Nearest Neighbor Methods in Prediction

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 180 references that are in the map.
- First posted on arXiv 21 Feb 2025.

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

- [Practical and Optimal LSH for Angular Distance](https://mlsanity.com/paper/1509.02897/) (2015)
- [Online Clustering of Bandits](https://mlsanity.com/paper/1401.8257/) (2014)
- [Rates of Convergence for Nearest Neighbor Classification](https://mlsanity.com/paper/1407.0067/) (2014)
- [Optimal Data-Dependent Hashing for Approximate Near Neighbors](https://mlsanity.com/paper/1501.01062/) (2015)
- [Analyzing the Robustness of Nearest Neighbors to Adversarial Examples](https://mlsanity.com/paper/1706.03922/) (2017)
- [DeepNAT: Deep Convolutional Neural Network for Segmenting Neuroanatomy](https://mlsanity.com/paper/1702.08192/) (2017)
- [Linear Bandits in High Dimension and Recommendation Systems](https://mlsanity.com/paper/1301.1722/) (2013)
- [Exploring Nearest Neighbor Approaches for Image Captioning](https://mlsanity.com/paper/1505.04467/) (2015)
- [Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors](https://mlsanity.com/paper/1608.03580/) (2016)
- [Regret Guarantees for Item-Item Collaborative Filtering](https://mlsanity.com/paper/1507.05371/) (2015)
- [A Latent Source Model for Online Collaborative Filtering](https://mlsanity.com/paper/1411.6591/) (2014)
- [Regret Bounds and Regimes of Optimality for User-User and Item-Item Collaborative Filtering](https://mlsanity.com/paper/1711.02198/) (2017)
- [A Bayes consistent 1-NN classifier](https://mlsanity.com/paper/1407.0208/) (2014)
- [k*-Nearest Neighbors: From Global to Local](https://mlsanity.com/paper/1701.07266/) (2017)
- [The Boundary Forest Algorithm for Online Supervised and Unsupervised Learning](https://mlsanity.com/paper/1505.02867/) (2015)
- [A Latent Source Model for Nonparametric Time Series Classification](https://mlsanity.com/paper/1302.3639/) (2013)
- [Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing](https://mlsanity.com/paper/1507.04299/) (2015)
- [A Latent Source Model for Patch-Based Image Segmentation](https://mlsanity.com/paper/1510.01648/) (2015)
- [Learning Deep Nearest Neighbor Representations Using Differentiable Boundary Trees](https://mlsanity.com/paper/1702.08833/) (2017)

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

- [Near-Exponential Convergence Rates for kNN Classification based on Boltzmann Margin](https://mlsanity.com/paper/2606.10361/) (2026)
- [On the Oracle Complexity of Interpolation-Based Gradient Descent](https://mlsanity.com/paper/2606.19878/) (2026)

## Abstract (arXiv)

Many modern methods for prediction leverage nearest neighbor search to find past training examples most similar to a test example, an idea that dates back in text to at least the 11th century and has stood the test of time. This monograph aims to explain the success of these methods, both in theory, for which we cover foundational nonasymptotic statistical guarantees on nearest-neighbor-based regression and classification, and in practice, for which we gather prominent methods for approximate nearest neighbor search that have been essential to scaling prediction systems reliant on nearest neighbor analysis to handle massive datasets. Furthermore, we discuss connections to learning distances for use with nearest neighbor methods, including how random decision trees and ensemble methods learn nearest neighbor structure, as well as recent developments in crowdsourcing and graphons. In terms of theory, our focus is on nonasymptotic statistical guarantees, which we state in the form of how many training data and what algorithm parameters ensure that a nearest neighbor prediction method achieves a user-specified error tolerance. We begin with the most general of such results for nearest neighbor and related kernel regression and classification in general metric spaces. In such settings in which we assume very little structure, what enables successful prediction is smoothness in the function being estimated for regression, and a low probability of landing near the decision boundary for classification. In practice, these conditions could be difficult to verify for a real dataset. We then cover recent guarantees on nearest neighbor prediction in the three case studies of time series forecasting, recommending products to people over time, and delineating human organs in medical images by looking at image patches. In these case studies, clustering structure enables successful prediction.