提出新型边界条件，让kNN分类实现接近指数级收敛速度。
Near-Exponential Convergence Rates for kNN Classification based on Boltzmann Margin
- 引入Boltzmann边界条件，介于传统两种边界之间。
- 首次证明kNN分类可达到近指数收敛速率。
- 理论严谨且有数值实验支持，适合理论研究者。
分类器的收敛速率分析通常基于Tsybakov边界或Massart边界。前者较弱，通常导致多项式速率；后者较强，可保证指数速率。本文提出一种新条件——Boltzmann边界，该条件弱于Massart边界但普遍强于Tsybakov边界，可在适当条件下继承两者特性。将Boltzmann边界应用于kNN分类器分析，首次建立kNN分类的近指数收敛速率。同时拓展主结果并提供数值证据，验证主要理论推论的合理性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。