2023/07/03 by Sanjoy Dasgupta, Dasgupta, Sanjoy, Geelon So +1
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Anomaly Detection Techniques and Applications #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2307.01170
openalex publication_date 2023/07/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.