Near-Exponential Convergence Rates for kNN Classification based on Boltzmann Margin
Abstract
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.
Related
- Combining Exponential and Polynomial Convergence Rates for Accelerated Extremum Seeking: A High-Order Lie Bracket Approach
- Strong convergence rates of tamed exponential Euler schemes for superlinear hyperbolic SPDEs
- Critical Markov Branching-Immigration Systems: Complete Classification of the State Space and Exact Rates of Convergence
- Generalized Logarithmic Sobolev inequalities on Bounded Domains and exponential decay to Boltzmann states for Nernst--Planck--Navier--Stokes systems
- Incompressible Navier-Stokes Limit of the Relativistic Boltzmann Equation with the Optimal Convergence Rate
BibTeX
@misc{yang2026nearexponential,
title = {{Near-Exponential Convergence Rates for kNN Classification based on Boltzmann Margin}},
author = {Luyuan Yang and Shayan Shafaei and Chao Lan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2606.10361},
eprint = {2606.10361},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.10361},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Near-Exponential Convergence Rates for kNN Classification based on Boltzmann Margin
AU - Luyuan Yang
AU - Shayan Shafaei
AU - Chao Lan
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2606.10361
UR - https://arxiv.org/abs/2606.10361
AB - 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.
ER -