Fast learning rates for plug-in classifiers under the margin condition

Abstract

It has been recently shown that, under the margin (or low noise) assumption, there exist classifiers attaining fast rates of convergence of the excess Bayes risk, i.e., the rates faster than $n^{-1/2}$. The works on this subject suggested the following two conjectures: (i) the best achievable fast rate is of the order $n^{-1}$, and (ii) the plug-in classifiers generally converge slower than the classifiers based on empirical risk minimization. We show that both conjectures are not correct. In particular, we construct plug-in classifiers that can achieve not only the fast, but also the {\it super-fast} rates, i.e., the rates faster than $n^{-1}$. We establish minimax lower bounds showing that the obtained rates cannot be improved.

36 pages

References in corpus (3)

• 2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization
• Risk bounds for statistical learning
• Statistical performance of support vector machines

Cited by in corpus (13)

• Choice of neighbor order in nearest-neighbor classification
• Fast learning rates for plug-in classifiers
• Generalization error bounds in semi-supervised classification under the cluster assumption
• Optimal rates for plug-in estimators of density level sets
• Fast learning rates in statistical inference through aggregation
• Selection of variables and dimension reduction in high-dimensional non-parametric regression
• SemiFL: Semi-Supervised Federated Learning for Unlabeled Clients with Alternate Training
• Simultaneous adaptation to the margin and to complexity in classification
• Discussion of ``2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization'' by V. Koltchinskii
• Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimes
• A flexible model-free prediction-based framework for feature ranking
• High dimensional gaussian classification
• Fast rate of convergence in high dimensional linear discriminant analysis