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

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

## 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 (most cited first, 18 of 18)

- [Generalization through Memorization: Nearest Neighbor Language Models](https://mlsanity.com/paper/1911.00172/) (2019)
- [Towards Self-Explainable Graph Neural Network](https://mlsanity.com/paper/2108.12055/) (2021)
- [Rates of Convergence for Nearest Neighbor Classification](https://mlsanity.com/paper/1407.0067/) (2014)
- [Universal Bayes consistency in metric spaces](https://mlsanity.com/paper/1906.09855/) (2019)
- [Explaining and Improving Model Behavior with k Nearest Neighbor Representations](https://mlsanity.com/paper/2010.09030/) (2020)
- [Nearest Neighbor Speculative Decoding for LLM Generation and Attribution](https://mlsanity.com/paper/2405.19325/) (2024)
- [Universal consistency and rates of convergence of multiclass prototype algorithms in metric spaces](https://mlsanity.com/paper/2010.00636/) (2020)
- [Fast Rates for a kNN Classifier Robust to Unknown Asymmetric Label Noise](https://mlsanity.com/paper/1906.04542/) (2019)
- [Achieving the time of 1-NN, but the accuracy of k-NN](https://mlsanity.com/paper/1712.02369/) (2017)
- [On Convergence of Nearest Neighbor Classifiers over Feature Transformations](https://mlsanity.com/paper/2010.07765/) (2020)
- [Multiclass learning with margin: exponential rates with no bias-variance trade-off](https://mlsanity.com/paper/2202.01773/) (2022)
- [A Bayes consistent 1-NN classifier](https://mlsanity.com/paper/1407.0208/) (2014)
- [Improved Subsampled Randomized Hadamard Transform for Linear SVM](https://mlsanity.com/paper/2002.01628/) (2020)
- [Rates of Convergence for Large-scale Nearest Neighbor Classification](https://mlsanity.com/paper/1909.01464/) (2019)
- [Under-bagging Nearest Neighbors for Imbalanced Classification](https://mlsanity.com/paper/2109.00531/) (2021)
- [A Case of Exponential Convergence Rates for SVM](https://mlsanity.com/paper/2205.10055/) (2022)
- [Explaining the Success of Nearest Neighbor Methods in Prediction](https://mlsanity.com/paper/2502.15900/) (2025)
- [Fast and Multiphase Rates for Nearest Neighbor Classifiers](https://mlsanity.com/paper/2308.08247/) (2023)

## 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.