Fast learning rates for plug-in classifiers

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, that is, rates faster than $n^{-1/2}$. The work on this subject has 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 more slowly 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 fast, but also super-fast rates, that is, rates faster than $n^{-1}$. We establish minimax lower bounds showing that the obtained rates cannot be improved.

Published at http://dx.doi.org/10.1214/009053606000001217 in the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (3)

• Fast learning rates for plug-in classifiers
• Fast rates for support vector machines using Gaussian kernels
• Statistical performance of support vector machines

Cited by in corpus (6)

• Choice of neighbor order in nearest-neighbor classification
• Fast learning rates for plug-in classifiers
• Fast learning rates in statistical inference through aggregation
• Selection of variables and dimension reduction in high-dimensional non-parametric regression
• Asymptotic distribution and sparsistency for l1-penalized parametric M-estimators with applications to linear SVM and logistic regression
• Discussion of ``2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization'' by V. Koltchinskii