# Online Consistency of the Nearest Neighbor Rule

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 28 references that are in the map.
- First posted on arXiv 31 Oct 2024.

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

- [Smoothed Analysis with Adaptive Adversaries](https://mlsanity.com/paper/2102.08446/) (2021)
- [Smoothed Online Learning is as Easy as Statistical Learning](https://mlsanity.com/paper/2202.04690/) (2022)
- [Smoothed Analysis of Online and Differentially Private Learning](https://mlsanity.com/paper/2006.10129/) (2020)
- [Rates of Convergence for Nearest Neighbor Classification](https://mlsanity.com/paper/1407.0067/) (2014)
- [Learning Whenever Learning is Possible: Universal Learning under General Stochastic Processes](https://mlsanity.com/paper/1706.01418/) (2017)
- [Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games](https://mlsanity.com/paper/2102.01646/) (2021)
- [Universal Online Learning: an Optimistically Universal Learning Rule](https://mlsanity.com/paper/2201.05947/) (2022)
- [Universal Online Learning with Bounded Loss: Reduction to Binary Classification](https://mlsanity.com/paper/2112.14638/) (2021)

## Abstract (arXiv)

In the realizable online setting, a learner is tasked with making predictions for a stream of instances, where the correct answer is revealed after each prediction. A learning rule is online consistent if its mistake rate eventually vanishes. The nearest neighbor rule (Fix and Hodges, 1951) is a fundamental prediction strategy, but it is only known to be consistent under strong statistical or geometric assumptions: the instances come i.i.d. or the label classes are well-separated. We prove online consistency for all measurable functions in doubling metric spaces under the mild assumption that the instances are generated by a process that is uniformly absolutely continuous with respect to a finite, upper doubling measure.