Fast learning rates for plug-in classifiers

By Jean-Yves Audibert, Alexandre B. Tsybakov. 2005

520 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/42b928fa86ba80cfaa342c10b81a84ec2d4be36f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

The multi-armed bandit problem with covariates (2011, background): “Our policies for the problem with covariates fall into the family of “plug-in” policies as opposed “minimum contrast” policies; a detailed account of the differences and similarities between these two setups in the full information case can be found in [2].”
Optimal weighted nearest neighbour classifiers (2011, background): “More recently, Audibert and Tsybakov (2007) have discussed the relative merits of plug-in classifiers (a family to which weighted nearest neighbour classifiers belong) and classifiers based on empirical risk minimisation, such as support vector machines (Cortes and Vapnik, 1995; Blanchard, Bousquet…”
Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate (2018, background): “The regularity condition from Audibert and Tsybakov [5] is not very restrictive.”
Classification with a Reject Option using a Hinge Loss (2008, methodology): “For many binary classification methods (including empirical risk minimization, plug-in estimates, and minimization of the sample average of a suitable convex loss), the estimation error term εn approaches zero at a faster rate when the conditional probability η(X) is unlikely to be close to the crit”
Regularization in reinforcement learning (2011, unknown): “This upper bound is notable because it is the minimax rate for the regression problem when the regression function belongs to a function space F with a packing entropy in the same form as in the upper bound of Assumption A16 [Yang and Barron, 1999]. Since the regression problem is a subset of the po”
STATISTICAL INFERENCE FOR THE MEAN OUTCOME UNDER A POSSIBLY NON-UNIQUE OPTIMAL TREATMENT STRATEGY (2016, background): “This assumption is a direct restatement of Assumption (MA) from Audibert and Tsybakov (2007) and was considered earlier in Tsybakov (2004).”
Nonparametric Bandits with Covariates (2010, background): “2 Description of the problem”
Optimal rates for plug-in estimators of density level sets (2006, background): “1156 P. Rigollet and R. Vert Gayraud and Rousseau (2005) proposed a Bayesian approach to DLSE, together with interesting comparative simulations.”
Theory of Disagreement-Based Active Learning (2014, background): “This is a possibility explored by Audibert and Tsybakov [2007]. Interestingly, they find that when ` is the quadratic loss, and F is a Hölder class of functions, the label complexities achievable by a certain passive learning method under the assumption that f? ` ∈ F are indeed smaller than the know”
Classification with reject option (2006, background): “We show that very fast rates are possible under reasonable margin conditions, extending a recent result by Audibert and Tsybakov (2005) to our more general framework.”
Action-Gap Phenomenon in Reinforcement Learning (2011, methodology): “This assumption is inspired by the low-noise condition in the classification literature [5].”
Faster Rates for Policy Learning (2017, background): “Extensions of the result of [10] have previously been presented in both the reinforcement learning literature [6] and in the optimal individualized treatment literature [7, 8].”
Optimal rates and adaptation in the single-index model using aggregation (2007, background): “Note that this assumption is more general than the one considered in Audibert and Tsybakov (2007).”
Distribution Free Prediction Sets (2013, background): “As indicated in Audibert and Tsybakov (2007), A1 and A2 cannot hold simultaneously unless γ (1 ∧ β) ≤ 1.”
Distribution‐free prediction bands for non‐parametric regression (2014, background): “As mentioned in Audibert and Tsybakov (2007), the oracle band CP.”