Near-Exponential Convergence Rates for kNN Classification based on Boltzmann Margin
The paper introduces 'Boltzmann margin,' a new condition between Tsybakov and Massart margins, to analyze kNN classifiers. This condition allows for establishing near-exponential convergence rates for kNN classification, which are faster than polynomial rates typically achieved under weaker conditions. The results also extend to ensemble kNN (ekNN) classifiers.