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

• URL: http://arxiv.org/abs/2606.10361v1
• Date: Tue, 09 Jun 2026 03:21:48 GMT
• Title: Near-Exponential Convergence Rates for kNN Classification based on Boltzmann Margin
• Abstract summary: Boltzmann margin is a new condition that bridges the gap between Tsybakov margin and Massart margin.<n>We establish the first near-exponential convergence rates for kNN classification.
• Score: 6.244816393907942
• License: http://creativecommons.org/licenses/by/4.0/
• 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 papers

• Tight Contraction Rates for Primitive Channels under Quantum $f$-Divergences [10.960289997471085]
  We show that quantum $f$-divergences satisfy a local reverse Pinsker inequality.<n>We apply these results to Petz, Matsumoto, and Hirche-Tomamichel $f$-divergences.
  arXiv  Detail & Related papers  (2026-05-07T15:48:23Z)
• Byzantine Machine Learning: MultiKrum and an optimal notion of robustness [10.810599663861476]
  We provide the first proof that MultiKrum is a robust aggregation rule, and bound its robustness coefficient.<n>We show that MultiKrum's bounds are never worse than Krum's, and better in realistic regimes.
  arXiv  Detail & Related papers  (2026-02-03T09:07:03Z)
• Unregularized Linear Convergence in Zero-Sum Game from Preference Feedback [50.89125374999765]
  We provide the first convergence guarantee for Optimistic Multiplicative Weights Update ($mathtOMWU$) in NLHF.<n>Our analysis identifies a novel marginal convergence behavior, where the probability of rarely played actions grows exponentially from exponentially small values.
  arXiv  Detail & Related papers  (2025-12-31T12:08:29Z)
• Exponential Convergence Guarantees for Iterative Markovian Fitting [15.697611355182005]
  We provide the first non-asymptotic exponential convergence guarantees for Iterative Proportional Fitting (IMF)<n>Our results encompass two key regimes: one where the marginals are log-concave, and another where they are weakly log-concave.<n>The analysis relies on new contraction results for the Markovian projection operator and paves the way to theoretical guarantees for DSBM.
  arXiv  Detail & Related papers  (2025-10-23T08:34:04Z)
• Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation [51.248784084461334]
  We prove new convergence rates for a generalized version of Nesterov acceleration underrho conditions.<n>Our analysis reduces the dependence on the strong growth constant from $$ to $sqrt$ as compared to prior work.
  arXiv  Detail & Related papers  (2024-04-03T00:41:19Z)
• A Case of Exponential Convergence Rates for SVM [1.52292571922932]
  Generalization guarantees of classification have historically been offered by Vapnik-Chervonenkis theory. We show that SVM can exhibit exponential convergence rates even without assuming the hard Tsybakov margin condition.
  arXiv  Detail & Related papers  (2022-05-20T09:49:27Z)
• What Are Bayesian Neural Network Posteriors Really Like? [63.950151520585024]
  We show that Hamiltonian Monte Carlo can achieve significant performance gains over standard and deep ensembles. We also show that deep distributions are similarly close to HMC as standard SGLD, and closer than standard variational inference.
  arXiv  Detail & Related papers  (2021-04-29T15:38:46Z)
• Super fast rates in structured prediction [88.99819200562784]
  We show how we can leverage the fact that discrete problems are essentially predicting a discrete output when continuous problems are predicting a continuous value. We first illustrate it for predictors based on nearest neighbors, generalizing rates known for binary classification to any discrete problem within the framework of structured prediction. We then consider kernel ridge regression where we improve known rates in $n-1/4$ to arbitrarily fast rates, depending on a parameter characterizing the hardness of the problem.
  arXiv  Detail & Related papers  (2021-02-01T10:50:04Z)
• Provable tradeoffs in adversarially robust classification [96.48180210364893]
  We develop and leverage new tools, including recent breakthroughs from probability theory on robust isoperimetry. Our results reveal fundamental tradeoffs between standard and robust accuracy that grow when data is imbalanced.
  arXiv  Detail & Related papers  (2020-06-09T09:58:19Z)
• Fractional norms and quasinorms do not help to overcome the curse of dimensionality [62.997667081978825]
  Using of the Manhattan distance and even fractional quasinorms lp can help to overcome the curse of dimensionality in classification problems. A systematic comparison shows that the difference of the performance of kNN based on lp for p=2, 1, and 0.5 is statistically insignificant.
  arXiv  Detail & Related papers  (2020-04-29T14:30:12Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.