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

arXiv:2606.10361 · stat.ML, cs.LG · Submitted 2026-06-09 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "Near-Exponential Convergence Rates for kNN Classification based on Boltzmann Margin".

Jane: The gist The introduction introduces Boltzmann margin, a new margin condition that bridges the gap between Tsybakov and Massart margins, which enables near-exponential convergence rates for kNN classification.

Tom: First, who's behind it and why it matters.

Title and authors: Tom: So we're looking at this paper, "Near-Exponential Convergence Rates for kNN Classification based on Boltzmann Margin." The authors are Luyuan Yang, Shayan Shafaei, and Chao Lan from the School of Computer Science at the University of Oklahoma.

Jane: It sounds like they’re trying to find a better way to measure how fast our classifiers get closer to the true answer as we feed them more data. They’re looking at things like Tsybakov margin and Massart margin, which are the usual conditions we use for this kind of analysis.

Lu: Exactly, Tsybakov margin gives us polynomial rates, which is fine but not what we really want when dealing with complex data distributions. Massart margin is much stronger and gives exponential rates, but that's usually too restrictive for real-world problems.

Meng: So the central idea here seems to be introducing this new condition called Boltzmann margin that sits right in between those two extremes, trying to get us somewhere better than polynomial without needing the super strong Massart assumption.

Tom: Right. The paper introduces Boltzmann margin as a new condition that bridges the gap between Tsybakov and Massart margins, which lets them claim near-exponential convergence rates for kNN classification. It’s basically a middle ground condition that can imply properties of both other margins under certain settings, so it’s flexible.

Jane: That bridging idea is interesting because it suggests we might not always need the most restrictive assumptions to get good convergence speed in our models. It opens up a new area for analysis.

Lu: It’s about creating a more balanced framework, where the decay behavior under Boltzmann margin lies between those under Massart and Tsybakov margins, which makes it a flexible framework for convergence rate analysis <ref:2606.10361#pg5>.

Meng: I wonder if this flexibility translates into something practical when we try to actually build and deploy these kinds of classifiers at scale.

Tom: We'll see that in the next part, because the paper really focuses on how this new condition changes the convergence speed for kNN classification specifically.

The paper's summary: Jane: So what’s the actual main point they are making about this Boltzmann margin? They apply it to kNN classifiers and establish what they call "the first near-exponential convergence rates for kNN classification."

Tom: That’s the big claim. If you have a data distribution with this specific (alpha, beta, gamma) Boltzmann margin and your classifier size k scales like O(n beta + two beta + C upsilon), then the error bound looks like this: -* e is less than or equal to C alpha (-C gamma n beta + C upsilon) for training data size n greater than (C' n)one + C upsilon/beta <ref:2606.10361#pg2>.

Lu: That exponential decay with the term gamma n beta in the exponent is what makes it near-exponential, and they explicitly state that a larger beta makes that rate closer to exponential.

Meng: So for us in production, if we can find data where this margin condition holds, we get error bounds that decay exponentially with respect to the training size n, provided we tune our classifier size k correctly. That’s much better than polynomial rates.

Tom: It’s a significant jump from what you see under standard polynomial assumptions when using Tsybakov margin, which is what most of us are used to seeing for kNN error orders <ref:2606.10361#pg2>.

Jane: It sounds like they’re giving us a concrete mathematical tool to aim for faster convergence in the classification task itself, rather than just tweaking the data or the algorithm parameters.

Lu: They even show that under specific conditions, like when n at most D squared, they can reach an asymptotic rate of O(Dn-three/four) when eta is Hölder and k scales like O(n three/four), which shows how the rate can vary across different phases <ref:2606.10361#pg3>.

Meng: That variation across phases suggests that we have to be really careful about where we are in the training process when deploying this, because the convergence behavior isn't perfectly smooth.

The paper's improvements: Jane: Beyond just stating a rate, what else does this paper suggest is better? They extend these results to ensemble kNN classifiers, or ekNN.

Tom: They do have extensions for ensemble kNN using Theorem five point one <ref:2606.10361#pg3>. If you use the Boltzmann margin condition and your classifier size k scales as O(beta + two beta + C upsilon), the error bound for ekNN is e -* e is less than or equal to C alpha (-C gamma beta + C upsilon) for greater than (two two m)/C'1+C upsilon/beta <ref:2606.10361#pg2>.

Lu: That is a very clean result. It shows that the ensemble version benefits similarly, maintaining that near-exponential decay with respect to the training size, which is pretty strong for an ensemble method.

Meng: I’m interested because they also establish a strong consistency guarantee for ekNN classification under this Boltzmann margin using Theorem five point four, which means we can actually trust that the ensemble classifier will be close to the true answer with high probability <ref:2606.10361#pg3>.

Jane: That consistency guarantee is what really pushes this paper forward; it moves it from just being a theoretical rate analysis to providing actual reliability guarantees for deployment.

Tom: It’s about showing that if you use this margin condition, you can achieve not just fast convergence but also strong Bayes consistency for the ensemble classifier, which is a big step in terms of practical trust.

Conclusion: Tom: So to wrap up, the main idea of "Near-Exponential Convergence Rates for kNN Classification based on Boltzmann Margin" is that this new condition lets us achieve near-exponential convergence rates for both kNN and ekNN classifiers.

Jane: Specifically, they found that if you have a data distribution with a Boltzmann margin and your classifier size k scales appropriately, the error bound is bounded by C alpha (-C gamma n beta + C upsilon) for kNN.

Lu: And for the ensemble version, they get an error bound of C alpha (-C gamma beta + C upsilon) with a slightly different requirement on.

Meng: From my side, the main implication is that we can start identifying feature spaces that satisfy this Boltzmann margin condition while still getting near-exponential error convergence without needing the strong Massart margin.

Lalam: I’m pretty sure this approach is solid because it provides a mechanism to achieve these fast rates, and it allows for analysis that sits nicely between the Tsybakov and Massart regimes <ref:2606.10361#pg5>.

Tom: It’s about finding a way to get those fast rates without needing the strong Massart margin, which is what this paper sets up by introducing Boltzmann margin.

Jane: It’s a lot of math, but it gives us a new lens to look at how we can design classifiers that converge faster in practice.

Lu: It's about finding that balance between theoretical guarantees and the practical constraints of training data size and model complexity.

School of Computer Science, University of Oklahoma

stat.ML, cs.LG

Submitted: 2026-06-09

Updated: 2026-10-14

Comments: Conference on Uncertainty in Artificial Intelligence (UAI)

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 81/100

The gist: The gist The introduction introduces Boltzmann margin, a new margin condition that bridges the gap between Tsybakov and Massart margins, which enables near-exponential convergence rates for kNN

Key concepts

Tsybakov Margin
This is a relatively weak margin condition that assumes data decays polynomially fast towards the Bayes decision boundary. It usually leads to polynomial convergence rates for classification errors, meaning the error decreases at a rate like 1/n^p.
Massart Margin
This is a much stronger margin condition that assumes no data points exist near the decision boundary. While it guarantees exponential convergence rates, it is often too restrictive for many real-world problems.
Boltzmann Margin
This new condition bridges the gap between Tsybakov and Massart margins by assuming data decay exponentially fast towards the Bayes decision boundary. It is weaker than Massart but generally stronger than Tsybakov, offering a flexible framework for analyzing convergence rates.

Terminology

Summary

The gist The introduction introduces Boltzmann margin, a new margin condition that bridges the gap between Tsybakov and Massart margins, which enables near-exponential convergence rates for kNN classification.

What is Boltzmann Margin?

Boltzmann margin is defined as a condition where the probability of the posterior being close to 1/2 decays exponentially with respect to the distance from 1/2, specifically: PrX(1/2 − η(X) ≤ t) ≤ α exp(−γt−β) for all t > 0. The decay behavior lies between those under Massart and Tsybakov margins <ref:2606.10361#pg8>.

Convergence Rates for kNN Classification

The paper establishes the first near-exponential convergence rates for kNN classification by applying the Boltzmann margin condition. The main result states that if a data distribution has a (α, β, γ) Boltzmann margin and k = O(nβ+2β+Cυ), then yˆ − yˆ∗e ≤ Cα exp (−Cγnβ+Cυ) for n ≥ (C′ln n)1+Cυ/β. This rate is near-exponential, and larger β makes the rate closer to exponential.

Extensions and Consistency Results

The analysis extends to ensemble kNN (ekNN) classifiers using Theorem 5.1. This theorem shows that if the data distribution has a (α, β, γ) Boltzmann margin and k = O(˜nβ+2β+Cυ), then yˆe − yˆ∗e ≤ Cα exp (−Cγn˜β+Cυ) for n˜ ≥ (2 maxln ˜n, 2 ln m)/C′1+Cυ/β. Furthermore, Theorem 5.4 establishes a strong consistency guarantee for ekNN classification under Boltzmann margin.

Probabilistic Guarantees and Other Margins

The paper provides probabilistic convergence rates in Corollary 4.3, showing that er(ˆy) − er(ˆy∗) ≤ C˜αδ−1 exp (−Cγnβ+Cυ) with probability at least 1 − δ over the random choice of S. The results also hold under Tsybakov margin for a specific range of n, as shown in Corollary 4.4, which presents a multi-phase convergence rate <ref:2606.10361#pg6>.

Numerical Evidence and Implications

Numerical results are presented to empirically evaluate the theoretical implications. The construction of a Boltzmann-margin density function fb(x) is detailed in Appendix D.1. Empirical evaluation shows that as β increases, the excess error curve becomes increasingly straight, agreeing with the theoretical result that larger β implies convergence closer to exponential. The ensemble kNN error curves appear straighter than those of kNN, suggesting a potential advantage of ekNN.

Conclusion

The paper introduces Boltzmann margin to achieve near-exponential convergence rates for kNN and ekNN classifiers and provides the first strong consistency guarantee for ekNN. The study suggests that one may identify a feature space satisfying Boltzmann margin while still achieving near-exponential error convergence without needing a strong Massart margin.

--- Page 1 ---

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

Luyuan Yang1 Shayan Shafaei1 Chao Lan1

1School of Computer Science, University of Oklahoma, Norman, Oklahoma, USA

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.

1 INTRODUCTION

In machine learning, a fundamental question is how fast the classification error converges to the Bayes error as training data size increases. The convergence rate has been widely studied under two margin conditions: Tsybakov margin [Tsybakov, 2004] and Massart margin [Massart and Nédélec, 2006]. Tsybakov margin is a relatively weak condition that assumes data decay polynomially fast towards the Bayes decision boundary and typically yields polynomial rates [Chaudhuri and Dasgupta, 2014, Döring et al., 2018]. Massart margin is substantially stronger, as it assumes no data exist near the boundary, but can guarantee exponential rates [Cabannnes and Vigogna, 2023, Vigogna et al., 2022].

There remains a substantial gap between the two margins. To establish any super-polynomial convergence rate, existing analyses typically require Massart margin, which may be unnecessarily strong for many problems. Can there be a more balanced margin condition that yields super-polynomial convergence rates without assuming an absence of data near the boundary? This question motivates our study.

In this paper, we introduce Boltzmann margin, a more balanced condition that assumes data decay exponentially fast towards the Bayes decision boundary. It is weaker than Massart margin, generally stronger than Tsybakov margin, and can imply many of their properties under suitable conditions <ref:2606.10361#pg4>. In general, the decay behavior under Boltzmann margin lies between those under Massart and Tsybakov margins <ref:2606.10361#pg5>. Moreover, through suitable choices of its parameters, Boltzmann margin can resemble the decay behavior of either margin in certain regions, making it a flexible framework for convergence rate analysis <ref:2606.10361#pg5>.

We apply Boltzmann margin to analyze k-nearest-neighbor (kNN) classifiers. kNN is popular due to its flexibility and interpretability [Chen et al., 2018], and is increasingly used to enhance the explainability of complex models [Khandelwal et al., 2020, Rajani et al., 2020, Dai and Wang, 2021, Li et al. 24]. These developments motivate a deeper understanding of the fundamental properties of kNN <ref:2606.10361#pg6>.

arXiv:2606.10361v1 [stat.ML] 9 Jun 2026

--- Page 2 ---

Model Work Posterior Margin Density Error Order

kNN

[Kulkarni and Posner, 2002] Hölder x x n − 2υ D [Gyorfi, 2006] Hölderx x n − υ D [Kohler and Krzyzak, 2007] Hölder Tsybakov strong n − υ(1+β) D [Samworth, 2012b] Hölder Tsybakov min.mass n − 2(1+β) 4+D [Chaudhuri and Dasgupta, 2014] Hölderx x n − υ(1+β) D [Chaudhuri and Dasgupta, 2014] Hölderx x n − υ(1+β) D [Gadat et al. 2016] Lipschitz Tsybakov min.mass n − 1+β 2+D [Döring et al. 2018] Lipschitzx x n − 3/4

Ours Hölder Boltzmann x e−cn β β+Cυ

Ours Hölder Massart x e−cn ekNN [Biau et al. 2010] Lipschitzx x n − 2

[Samworth, 2012a] continuous Tsybakov min.mass n − 4

[Xue and Kpotufe, 2018] Hölder Tsybakov min.mass n − υ(1+β) D [Qiao et al. 2019] Hölder Boltzmann x e−cn gβ β+Cυ

Table 1: Convergence Rates for kNN Classifiers. Notations are loosely defined to cover both basic and generalized (marked by ‘) Hölder smooth posterior function η’. n is training data size; β is the main margin parameter; υ is the main Hölder parameter (for Hölder smooth posterior function η); D/d is input/intrinsic data dimension; Cυ = 2 + d/υ and c′, c, g are positive constants.

Improvements for AI systems

  1. Improved kNN Classification Convergence Rate: The system can establish the first near-exponential convergence rates for kNN classification by utilizing a new margin condition, Boltzmann margin, which is shown to bridge the gap between Tsybakov and Massart margins. This allows for faster error decay than previously guaranteed under standard polynomial assumptions.

  2. Strong Consistency Guarantee for Ensemble kNN: The improved system can provide the first such guarantee of strong Bayes consistency for ensemble kNN (ekNN) classifiers, specifically when the number of weak classifiers scales as k = O(˜n β+2 / β+Cυ) and m = O˜(e n˜).

  3. Near-Exponential Error Bounds: The system can achieve error bounds such as yˆ − yˆ∗e ≤ Cα exp −Cγn β/β+Cυ for kNN, where larger margin parameters makes the rate closer to exponential, suggesting better performance in regimes where data decay is sufficiently fast.

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.

Sources

Related papers