mlsanityData to 14 Oct 2026

Near-Exponential Convergence Rates for kNN Classification based on Boltzmann Margin

arXiv 2606.10361 ↗First posted 9 Jun 2026stat.ML cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

Convergence-rate analysis for classifiers is often conducted under either Tsybakov margin or Massart margin. The former is a relatively weak condition that typically yields polynomial rates, while the latter is substantially stronger but can guarantee exponential rates. In this paper, we introduce a new condition, called Boltzmann margin, that bridges the gap between these two regimes. It is weaker than Massart margin, generally stronger than Tsybakov margin, and can imply many of their properties under suitable conditions. We apply Boltzmann margin to the analysis of kNN classifiers and establish the first near-exponential convergence rates for kNN classification. We also present extensions of the main results and provide numerical evidence supporting the main theoretical implications.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 18 of its 37 references that are in the map. First posted on arXiv 9 Jun 2026.

Builds on

18 of 37 references.

References · 18

  1. 2019Generalization through Memorization: Nearest Neighbor Language Modelscited by 800
  2. 2021Towards Self-Explainable Graph Neural Networkcited by 75
  3. 2014Rates of Convergence for Nearest Neighbor Classificationcited by 46
  4. 2019Universal Bayes consistency in metric spacescited by 33
  5. 2020Explaining and Improving Model Behavior with k Nearest Neighbor Representationscited by 27
  6. 2024Nearest Neighbor Speculative Decoding for LLM Generation and Attributioncited by 25
  7. 2020Universal consistency and rates of convergence of multiclass prototype algorithms in metric spacescited by 18
  8. 2019Fast Rates for a kNN Classifier Robust to Unknown Asymmetric Label Noisecited by 11
  9. 2017Achieving the time of 1-NN, but the accuracy of k-NNcited by 10
  10. 2020On Convergence of Nearest Neighbor Classifiers over Feature Transformationscited by 7
  11. 2022Multiclass learning with margin: exponential rates with no bias-variance trade-offcited by 5
  12. 2014A Bayes consistent 1-NN classifiercited by 4
6 more
  1. 2020Improved Subsampled Randomized Hadamard Transform for Linear SVMcited by 4
  2. 2019Rates of Convergence for Large-scale Nearest Neighbor Classificationcited by 3
  3. 2021Under-bagging Nearest Neighbors for Imbalanced Classificationcited by 3
  4. 2022A Case of Exponential Convergence Rates for SVMcited by 3
  5. 2025Explaining the Success of Nearest Neighbor Methods in Predictioncited by 2
  6. 2023Fast and Multiphase Rates for Nearest Neighbor Classifierscited by 1

Built on by

Not cited yet.