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 transformed space, and (2) smoothness -- how complex this recovery function is. Based on our result, we are able to explain why some (pre-trained) feature transformations are better suited for a kNN classifier than other. We empirically validate that both properties have an impact on the kNN convergence on 30 feature transformations with 6 benchmark datasets spanning from the vision to the text domain.

References in corpus (11)

• A tutorial on conformal prediction
• Deep k-Nearest Neighbors: Towards Confident, Interpretable and Robust Deep Learning
• Fast learning rates for plug-in classifiers
• Towards Efficient Data Valuation Based on the Shapley Value
• A Large-scale Study of Representation Learning with the Visual Task Adaptation Benchmark
• Analyzing the Robustness of Nearest Neighbors to Adversarial Examples
• Rates of Convergence for Nearest Neighbor Classification
• RAB: Provable Robustness Against Backdoor Attacks
• $k$-Nearest Neighbor Augmented Neural Networks for Text Classification
• Nearest Neighbor Classifiers over Incomplete Information: From Certain Answers to Certain Predictions
• Deep k-NN for Noisy Labels