Online Nearest Neighbor Classification

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.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keydasgupta2023online

Related papers

• On High-dimensional Modifications Of The Nearest Neighbor Classifier (2024)0.00
• Certifiable Robustness For Nearest Neighbor Classifiers (2022)0.00
• An Adaptive Nearest Neighbor Rule For Classification (2019)0.00
• A Two-stage Active Learning Algorithm For \(k\)-nearest Neighbors (2022)0.00
• Fast Nearest-neighbor Classification Using RNN In Domains With Large Number Of Classes (2017)0.00
• Adaptive Nearest Neighbor: A General Framework For Distance Metric Learning (2019)0.00
• Fast And Bayes-consistent Nearest Neighbors (2019)0.00
• Explaining The Success Of Nearest Neighbor Methods In Prediction (2025)18.63