Consistency of the $k_n$-nearest neighbor rule under adaptive sampling
Robi Bhattacharjee, Geelon So, Sanjoy Dasgupta
In the adaptive sampling model of online learning, future prediction tasks can depend on the past. At every round, an adversary selects an instance to test the learner, and after a prediction is made, a noisy label is drawn from an underlying conditional label distribution and is observed by both learner and adversary. A learner is consistent if it eventually performs no worse than the Bayes optimal predictor. In particular, we study the $k_n$-nearest neighbor learner (Fix and Hodges 1951). In the worst-case setting, the $k_n$-nearest neighbor rule fails to learn because an adaptive process can generate spurious patterns out of noise; however, under the mild assumption that the process generating the instances is uniformly absolutely continuous and that the underlying conditional label distribution is continuous, we show that $k_n$-nearest neighbor rule is consistent.