Skip to yearly menu bar Skip to main content


Poster

Online Consistency of the Nearest Neighbor Rule

Geelon So · Sanjoy Dasgupta


Abstract:

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 is fundamental prediction strategy, but it is only known to be consistent under strong stochastic 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 instances are generated by a process that is uniformly absolutely continuous with respect to an underlying finite, upper doubling measure.

Live content is unavailable. Log in and register to view live content