# On Convergence of Nearest Neighbor Classifiers over Feature Transformations

arXiv: https://arxiv.org/abs/2010.07765 · HTML: https://mlsanity.com/paper/2010.07765/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Oct 2020.

## Built on by (most cited first, 7 of 7)

- [A Data Quality-Driven View of MLOps](https://mlsanity.com/paper/2102.07750/) (2021)
- [Emergence and Effectiveness of Task Vectors in In-Context Learning: An Encoder Decoder Perspective](https://mlsanity.com/paper/2412.12276/) (2024)
- [Evaluating Bayes Error Estimators on Real-World Datasets with FeeBee](https://mlsanity.com/paper/2108.13034/) (2021)
- [SHiFT: An Efficient, Flexible Search Engine for Transfer Learning](https://mlsanity.com/paper/2204.01457/) (2022)
- [Matched Machine Learning: A Generalized Framework for Treatment Effect Inference With Learned Metrics](https://mlsanity.com/paper/2304.01316/) (2023)
- [Fast and Multiphase Rates for Nearest Neighbor Classifiers](https://mlsanity.com/paper/2308.08247/) (2023)
- [Near-Exponential Convergence Rates for kNN Classification based on Boltzmann Margin](https://mlsanity.com/paper/2606.10361/) (2026)

## Abstract (arXiv)

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.