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