# An adaptive nearest neighbor rule for classification

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 May 2019.

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

- [Simple and near-optimal algorithms for hidden stratification and multi-group learning](https://mlsanity.com/paper/2112.12181/) (2021)
- [DNNR: Differential Nearest Neighbors Regression](https://mlsanity.com/paper/2205.08434/) (2022)
- [Multi-group Learning for Hierarchical Groups](https://mlsanity.com/paper/2402.00258/) (2024)
- [ASK: Adversarial Soft k-Nearest Neighbor Attack and Defense](https://mlsanity.com/paper/2106.14300/) (2021)
- [Beyond kNN: Adaptive, Sparse Neighborhood Graphs via Optimal Transport](https://mlsanity.com/paper/2208.00604/) (2022)
- [A Two-Stage Active Learning Algorithm for k-Nearest Neighbors](https://mlsanity.com/paper/2211.10773/) (2022)
- [Distributed Adaptive Nearest Neighbor Classifier: Algorithm and Theory](https://mlsanity.com/paper/2105.09788/) (2021)
- [Out of distribution detection for skin and malaria images](https://mlsanity.com/paper/2111.01505/) (2021)
- [Theory of Machine Learning with Limited Data](https://mlsanity.com/paper/2206.07586/) (2022)
- [Weighted Distance Nearest Neighbor Condensing](https://mlsanity.com/paper/2310.15951/) (2023)
- [Learning Conditional Averages](https://mlsanity.com/paper/2602.11920/) (2026)
- [Learnability with Partial Labels and Adaptive Nearest Neighbors](https://mlsanity.com/paper/2603.15781/) (2026)
- [Estimation of the Label-Noise Transition Matrix with Performance Guarantees via Selective Classification](https://mlsanity.com/paper/2609.39829/) (2026)

## Abstract (arXiv)

We introduce a variant of the k-nearest neighbor classifier in which k is chosen adaptively for each query, rather than supplied as a parameter. The choice of k depends on properties of each neighborhood, and therefore may significantly vary between different points. (For example, the algorithm will use larger k for predicting the labels of points in noisy regions.) We provide theory and experiments that demonstrate that the algorithm performs comparably to, and sometimes better than, k-NN with an optimal choice of k. In particular, we derive bounds on the convergence rates of our classifier that depend on a local quantity we call the `advantage' which is significantly weaker than the Lipschitz conditions used in previous convergence rate proofs. These generalization bounds hinge on a variant of the seminal Uniform Convergence Theorem due to Vapnik and Chervonenkis; this variant concerns conditional probabilities and may be of independent interest.