On Convergence Of Nearest Neighbor Classifiers Over Feature Transformations

Abstract

The k-Nearest Neighbors (kNN) classifier is a fundamental non-parametric machine learning algorithm. However, it is well known that it suffers from the curse of dimensionality, which is why in practice one often applies a kNN classifier on top of a (pre-trained) feature transformation. From a theoretical perspective, most, if not all theoretical results aimed at understanding the kNN classifier are derived for the raw feature space. This leads to an emerging gap between our theoretical understanding of kNN and its practical applications. In this paper, we take a first step towards bridging this gap. We provide a novel analysis on the convergence rates of a kNN classifier over transformed features. This analysis requires in-depth understanding of the properties that connect both the transformed space and the raw feature space. More precisely, we build our convergence bound upon two key properties of the transformed space: (1) safety -- how well can one recover the raw posterior from the

Stats

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

Related papers

• An Adaptive Nearest Neighbor Rule For Classification (2019)0.00
• On High-dimensional Modifications Of The Nearest Neighbor Classifier (2024)0.00
• Minimax Rate Optimal Adaptive Nearest Neighbor Classification And Regression (2019)8.35
• A Fast And Easy Regression Technique For K-nn Classification Without Using Negative Pairs (2018)0.00
• Distance And Similarity Measures Effect On The Performance Of K-nearest Neighbor Classifier -- A Review (2017)20.24
• Adaptive Nearest Neighbor: A General Framework For Distance Metric Learning (2019)0.00
• A Theory-based Evaluation Of Nearest Neighbor Models Put Into Practice (2018)0.00
• Distributionally Robust Weighted \(k\)-nearest Neighbors (2020)0.00