# Online nearest neighbor classification

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

## 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 (most cited first, 8 of 8)

- [A Theory of Universal Learning](https://mlsanity.com/paper/2011.04483/) (2020)
- [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)
- [A Chaining Algorithm for Online Nonparametric Regression](https://mlsanity.com/paper/1502.07697/) (2015)
- [Online Nonparametric Regression with General Loss Functions](https://mlsanity.com/paper/1501.06598/) (2015)
- [Locally-Adaptive Nonparametric Online Learning](https://mlsanity.com/paper/2002.01882/) (2020)

## 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.