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

2026-06-09 · Luyuan Yang, Shayan Shafaei, Chao Lan arxiv

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.

📄 PDF Abstract BibTeX arXiv:2606.10361

Code (0)

등록된 구현이 없습니다.

Sample Space Truncation on Boltzmann Machines

2020-10-19 · NeurIPS Workshop DL-IG 2020 12 · Mahito Sugiyama, Koji Tsuda, Hiroyuki Nakahara

We present a lightweight variant of Boltzmann machines via sample space truncation, called a truncated Boltzmann machine (TBM), which has not been investigated before while can be naturally introduced from the log-linear…

A Convergent Variant of the Boltzmann Softmax Operator in Reinforcement Learning

2018-09-27 · Ling Pan, Qingpeng Cai, Qi Meng, Wei Chen 외

The Boltzmann softmax operator can trade-off well between exploration and exploitation according to current estimation in an exponential weighting scheme, which is a promising way to address the exploration-exploitation …

Atari Games Q-Learning reinforcement-learning Reinforcement Learning+1

Stochastic Gradient Descent with Exponential Convergence Rates of Expected Classification Errors

2018-06-14 · Atsushi Nitanda, Taiji Suzuki

We consider stochastic gradient descent and its averaging variant for binary classification problems in a reproducing kernel Hilbert space. In the traditional analysis using a consistency property of loss functions, it i…

Binary Classification Classification General Classification

Evolution of Gaussians in the Hellinger-Kantorovich-Boltzmann gradient flow

2025-04-29 · Matthias Liero, Alexander Mielke, Oliver Tse, Jia-Jie Zhu

This study leverages the basic insight that the gradient-flow equation associated with the relative Boltzmann entropy, in relation to a Gaussian reference measure within the Hellinger-Kantorovich (HK) geometry, preserves…

Convergence of Contrastive Divergence with Annealed Learning Rate in Exponential Family

2016-05-20 · Bai Jiang, Tung-Yu Wu, Wing H. Wong

In our recent paper, we showed that in exponential family, contrastive divergence (CD) with fixed learning rate will give asymptotically consistent estimates \cite{wu2016convergence}. In this paper, we establish consiste…