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

Luyuan Yang, Shayan Shafaei, Chao Lan

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 polynom…