mlsanityData to 7 Oct 2026

Rates of Convergence for Nearest Neighbor Classification

arXiv 1407.0067 ↗First posted 30 Jun 2014cs.LG math.ST stat.MLcited by 45

Not on the map. Why?

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.

Key facts. Cited by 45 papers in the map (data through 7 Oct 2026). First posted on arXiv 30 Jun 2014.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 14; 2022: 9; 2023: 5; 2024: 7; 2025: 4; 2026: 6.

45 papers.

Sort:

  1. 2021A Theory of PAC Learnability of Partial Concept Classescited by 59
  2. 2022Benign, Tempered, or Catastrophic: A Taxonomy of Overfittingcited by 36
  3. 2021Neural Active Learning with Performance Guaranteescited by 22
  4. 2024One-Layer Transformer Provably Learns One-Nearest Neighbor In Contextcited by 14
  5. 2023ResMem: Learn what you can and memorize the restcited by 13
  6. 2022Universal Online Learning: an Optimistically Universal Learning Rulecited by 12
  7. 2021Fast rates in structured predictioncited by 11
  8. 2022DNNR: Differential Nearest Neighbors Regressioncited by 11
  9. 2023Beyond Distribution Shift: Spurious Features Through the Lens of Training Dynamicscited by 11
  10. 2024Contextual Bandits for Unbounded Context Distributionscited by 8
  11. 2021Locally Adaptive Label Smoothing for Predictive Churncited by 7
  12. 2021Consistent Non-Parametric Methods for Maximizing Robustnesscited by 7
33 more
  1. 2021Optimal Binary Classification Beyond Accuracycited by 5
  2. 2021Adaptive transfer learningcited by 4
  3. 2023Near-optimal learning with average H"older smoothnesscited by 4
  4. 2021Self-Supervised Metric Learning in Multi-View Data: A Downstream Task Perspectivecited by 3
  5. 2021Under-bagging Nearest Neighbors for Imbalanced Classificationcited by 3
  6. 2022Distortion-Aware Brushing for Reliable Cluster Analysis in Multidimensional Projectionscited by 3
  7. 2024Learning with User-Level Local Differential Privacycited by 3
  8. 2021Nonparametric adaptive active learning under local smoothness conditioncited by 2
  9. 2024Enhancing Learning with Label Differential Privacy by Vector Approximationcited by 2
  10. 2025Explaining the Success of Nearest Neighbor Methods in Predictioncited by 2
  11. 2021Exploring Adversarial Examples for Efficient Active Learning in Machine Learning Classifierscited by 1
  12. 2022Benefit of Interpolation in Nearest Neighbor Algorithmscited by 1
  13. 2022On Error and Compression Rates for Prototype Rulescited by 1
  14. 2022A Two-Stage Active Learning Algorithm for k-Nearest Neighborscited by 1
  15. 2023Fast and Multiphase Rates for Nearest Neighbor Classifierscited by 1
  16. 2021Distributed Adaptive Nearest Neighbor Classifier: Algorithm and Theorycited by 0
  17. 2021On the (Un-)Avoidability of Adversarial Examplescited by 0
  18. 2021Improving Nonparametric Classification via Local Radial Regression with an Application to Stock Predictioncited by 0
  19. 2022Enhanced Nearest Neighbor Classification for Crowdsourcingcited by 0
  20. 2022Indirect Active Learningcited by 0
  21. 2023Online nearest neighbor classificationcited by 0
  22. 2024An adaptive transfer learning perspective on classification in non-stationary environmentscited by 0
  23. 2024Beyond Discrepancy: A Closer Look at the Theory of Distribution Shiftcited by 0
  24. 2024Online Consistency of the Nearest Neighbor Rulecited by 0
  25. 2025On Theoretical Limits of Learning with Label Differential Privacycited by 0
  26. 2025Locally Private Nonparametric Contextual Multi-armed Banditscited by 0
  27. 2025Topology-Driven Clustering: Enhancing Performance with Betti Number Filtrationcited by 0
  28. 2026Learnability with Partial Labels and Adaptive Nearest Neighborscited by 0
  29. 2026Leveraging Data Symmetries to Select an Optimal Subset of Training Data under Label Noisecited by 0
  30. 2026On public and private binary classification with metric space valued predictorscited by 0
  31. 2026k-Nearest Neighbors in Gromov--Wasserstein Spacecited by 0
  32. 2026Near-Exponential Convergence Rates for kNN Classification based on Boltzmann Margincited by 0
  33. 2026One-Layer Transformer Provably Learns Multiclass One-Nearest Neighbor in Contextcited by 0