Convergence-rate analysis for classifiers typically relies on one of two margin conditions. The Tsybakov margin is weak and usually leads to polynomial rates, while the Massart margin is much stronger and can guarantee exponential rates. In this paper, the authors introduce a new condition, the Boltzmann margin, that sits between these two: it is weaker than Massart, generally stronger than Tsybakov, and can reproduce many of their properties under suitable settings.

Using this new margin, the authors analyze k-nearest-neighbour (kNN) classifiers and prove the first near-exponential convergence rates for this method. They also extend the main results to broader settings and provide numerical experiments that support the theoretical findings. The work offers a way to obtain faster-rate guarantees without requiring the full strength of the Massart assumption.