Online Consistency of the Nearest Neighbor Rule
Not on the map. Why?
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.
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
8 of 28 references.
References · 8
- 2021Smoothed Analysis with Adaptive Adversariescited by 57
- 2022Smoothed Online Learning is as Easy as Statistical Learningcited by 52
- 2020Smoothed Analysis of Online and Differentially Private Learningcited by 47
- 2014Rates of Convergence for Nearest Neighbor Classificationcited by 46
- 2017Learning Whenever Learning is Possible: Universal Learning under General Stochastic Processescited by 23
- 2021Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Gamescited by 18
- 2022Universal Online Learning: an Optimistically Universal Learning Rulecited by 12
- 2021Universal Online Learning with Bounded Loss: Reduction to Binary Classificationcited by 8
Built on by
Not cited yet.