Online nearest neighbor classification
Not on the map. Why?
Abstract (arXiv)
We study an instance of online non-parametric classification in the realizable setting. In particular, we consider the classical 1-nearest neighbor algorithm, and show that it achieves sublinear regret - that is, a vanishing mistake rate - against dominated or smoothed adversaries in the realizable setting.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 8 of its 32 references that are in the map. First posted on arXiv 3 Jul 2023.
Builds on
8 of 32 references.
References · 8
- 2020A Theory of Universal Learningcited by 60
- 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
- 2015A Chaining Algorithm for Online Nonparametric Regressioncited by 16
- 2015Online Nonparametric Regression with General Loss Functionscited by 14
- 2020Locally-Adaptive Nonparametric Online Learningcited by 8
Built on by
Not cited yet.