# Rates of Convergence for Nearest Neighbor Classification

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

## Key facts

- Cited by 46 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jun 2014.

## Built on by (most cited first, 30 of 46)

- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)
- [Benign, Tempered, or Catastrophic: A Taxonomy of Overfitting](https://mlsanity.com/paper/2207.06569/) (2022)
- [Neural Active Learning with Performance Guarantees](https://mlsanity.com/paper/2106.03243/) (2021)
- [One-Layer Transformer Provably Learns One-Nearest Neighbor In Context](https://mlsanity.com/paper/2411.10830/) (2024)
- [ResMem: Learn what you can and memorize the rest](https://mlsanity.com/paper/2302.01576/) (2023)
- [Universal Online Learning: an Optimistically Universal Learning Rule](https://mlsanity.com/paper/2201.05947/) (2022)
- [Fast rates in structured prediction](https://mlsanity.com/paper/2102.00760/) (2021)
- [DNNR: Differential Nearest Neighbors Regression](https://mlsanity.com/paper/2205.08434/) (2022)
- [Beyond Distribution Shift: Spurious Features Through the Lens of Training Dynamics](https://mlsanity.com/paper/2302.09344/) (2023)
- [Contextual Bandits for Unbounded Context Distributions](https://mlsanity.com/paper/2408.09655/) (2024)
- [Locally Adaptive Label Smoothing for Predictive Churn](https://mlsanity.com/paper/2102.05140/) (2021)
- [Consistent Non-Parametric Methods for Maximizing Robustness](https://mlsanity.com/paper/2102.09086/) (2021)
- [Optimal Binary Classification Beyond Accuracy](https://mlsanity.com/paper/2107.01777/) (2021)
- [Adaptive transfer learning](https://mlsanity.com/paper/2106.04455/) (2021)
- [Near-optimal learning with average H"older smoothness](https://mlsanity.com/paper/2302.06005/) (2023)
- [Self-Supervised Metric Learning in Multi-View Data: A Downstream Task Perspective](https://mlsanity.com/paper/2106.07138/) (2021)
- [Under-bagging Nearest Neighbors for Imbalanced Classification](https://mlsanity.com/paper/2109.00531/) (2021)
- [Distortion-Aware Brushing for Reliable Cluster Analysis in Multidimensional Projections](https://mlsanity.com/paper/2201.06379/) (2022)
- [Learning with User-Level Local Differential Privacy](https://mlsanity.com/paper/2405.17079/) (2024)
- [Nonparametric adaptive active learning under local smoothness condition](https://mlsanity.com/paper/2102.11077/) (2021)
- [Enhancing Learning with Label Differential Privacy by Vector Approximation](https://mlsanity.com/paper/2405.15150/) (2024)
- [Explaining the Success of Nearest Neighbor Methods in Prediction](https://mlsanity.com/paper/2502.15900/) (2025)
- [Exploring Adversarial Examples for Efficient Active Learning in Machine Learning Classifiers](https://mlsanity.com/paper/2109.10770/) (2021)
- [Benefit of Interpolation in Nearest Neighbor Algorithms](https://mlsanity.com/paper/2202.11817/) (2022)
- [On Error and Compression Rates for Prototype Rules](https://mlsanity.com/paper/2206.08014/) (2022)
- [A Two-Stage Active Learning Algorithm for k-Nearest Neighbors](https://mlsanity.com/paper/2211.10773/) (2022)
- [Fast and Multiphase Rates for Nearest Neighbor Classifiers](https://mlsanity.com/paper/2308.08247/) (2023)
- [On Theoretical Limits of Learning with Label Differential Privacy](https://mlsanity.com/paper/2502.14309/) (2025)
- [Distributed Adaptive Nearest Neighbor Classifier: Algorithm and Theory](https://mlsanity.com/paper/2105.09788/) (2021)
- [On the (Un-)Avoidability of Adversarial Examples](https://mlsanity.com/paper/2106.13326/) (2021)

## Abstract (arXiv)

Nearest neighbor methods are a popular class of nonparametric estimators with several desirable properties, such as adaptivity to different distance scales in different regions of space. Prior work on convergence rates for nearest neighbor classification has not fully reflected these subtle properties. We analyze the behavior of these estimators in metric spaces and provide finite-sample, distribution-dependent rates of convergence under minimal assumptions. As a by-product, we are able to establish the universal consistency of nearest neighbor in a broader range of data spaces than was previously known. We illustrate our upper and lower bounds by introducing smoothness classes that are customized for nearest neighbor classification.