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

Luyuan Yang, Shayan Shafaei, Chao Lan
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:7818-7837, 2026.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-yang26e, title = {Near-Exponential Convergence Rates for kNN Classifications based on Boltzmann Margin}, author = {Yang, Luyuan and Shafaei, Shayan and Lan, Chao}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {7818--7837}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/yang26e/yang26e.pdf}, url = {https://proceedings.mlr.press/v337/yang26e.html}, 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.} }
Endnote
%0 Conference Paper %T Near-Exponential Convergence Rates for kNN Classifications based on Boltzmann Margin %A Luyuan Yang %A Shayan Shafaei %A Chao Lan %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-yang26e %I PMLR %P 7818--7837 %U https://proceedings.mlr.press/v337/yang26e.html %V 337 %X 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.
APA
Yang, L., Shafaei, S. & Lan, C.. (2026). Near-Exponential Convergence Rates for kNN Classifications based on Boltzmann Margin. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:7818-7837 Available from https://proceedings.mlr.press/v337/yang26e.html.

Related Material