Online nearest neighbor classification
Online nearest neighbor classification
S. Dasgupta,Geelon So
2023 · DOI: 10.48550/arXiv.2307.01170
arXiv.org · 0 Citations
TLDR
The classical 1-nearest neighbor algorithm is considered, and it is shown that it achieves sublinear regret - that is, a vanishing mistake rate - against dominated or smoothed adversaries in the realizable setting.
Abstract
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.