LGJul 3, 2023
Online nearest neighbor classification
arXiv:2307.01170v1h-index: 47
Originality Synthesis-oriented
AI Analysis
This provides theoretical guarantees for a classical algorithm in online learning, but it is incremental as it extends known results to specific adversarial settings.
The paper tackled the problem of online non-parametric classification in the realizable setting by analyzing the 1-nearest neighbor algorithm, showing it achieves sublinear regret with a vanishing mistake rate against dominated or smoothed adversaries.
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.