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

Luyuan Yang; Shayan Shafaei; Chao Lan

stat.MLJun 9, 2026

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

Authors: Luyuan Yang, Shayan Shafaei, Chao Lan

Organizations: School 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.

Explore similar work

Factorized AdaBoost.MH Achieves the Same Convergence Rate as AdaBoost.MH
Aug 2, 2026Xin Zou, Jingyuan XuBinary Classification Decision Trees
The Neural Tangent Kernel for Classification
May 17, 2026Jonathan Plenk, Sergio Calvo-Ordonez, Alvaro Cartea +3Neural Tangent Kernel Neural Network
Margin in Abstract Spaces
Mar 7, 2026Yair Ashlagi, Roi Livni, Shay Moran +1Metric Spaces Generalization Bounds

Aug 2, 2026 · cs.LGJ/K move · Enter open · S save

Factorized AdaBoost.MH Achieves the Same Convergence Rate as AdaBoost.MH

Xin Zou, Jingyuan Xu

{AdaBoost.MH} reduces multi-class classification to a collection of binary subproblems and enjoys the classical boosting-type convergence guarantee under a weak learning condition. A more structured variant, Factorized {AdaBoost.MH}, uses base classifiers of the form

\mathbf{h}(x)=α\mathbf{v} \bm{\varphi}(x)

, where a single binary classifier

\bm{\varphi}

is shared across all classes and the label dependence is carried by a vote vector

\mathbf{v} \in\{\pm1\}^K

. This factorization is algorithmically attractive and achieves better performance in practice, but its convergence depends on whether one can always choose a vote vector with sufficiently large induced binary weight mass. Previous work resolved this question with a lower bound

\max\{1/n,1/\sqrt{2K}\}

, which still leaves a dimension-dependent slowdown relative to the original {AdaBoost.MH} analysis. In this paper, we sharpen this combinatorial step. For the minimax quantity

\mathfrak{W}_{n,K}

governing the factorized edge, we prove

\mathfrak{W}_{n,K} = C_{\min\{n+1,K\}}

, where

C_q=1

for

q=1

C_q=q/(3q-4)

for even

q\ge2

, and

C_q=(q+1)/(3q-1)

for odd

q\ge2

. Since

C_q\downarrow 1/3

, our bounds show that

\mathfrak{W}_{n,K}=Θ(1)

uniformly over

n

and

K

. Consequently, Factorized {AdaBoost.MH} achieves the same boosting-type convergence rate as {AdaBoost.MH} up to a universal constant factor, removing the previously suggested additional dependence on

n

K

in the number of boosting rounds.

Binary Classification Decision Trees Optimal Sample Complexity Factor Convergence

Open paper Ask about it PDF

Abstract

Explore similar work

Factorized AdaBoost.MH Achieves the Same Convergence Rate as AdaBoost.MH

The Neural Tangent Kernel for Classification

Margin in Abstract Spaces