Risk bounds for statistical learning

By Pascal Massart, 'Elodie N'ed'elec. 2007

388 citations recorded by the source corpus.

We propose a general theorem providing upper bounds for the risk of an empirical risk minimizer (ERM).We essentially focus on the binary classification framework. We extend Tsybakov's analysis of the risk of an ERM under margin type conditions by using concentration inequalities for conveniently weighted empirical processes. This allows us to deal with ways of measuring the ``size'' of a class of classifiers other than entropy with bracketing as in Tsybakov's work. In particular, we derive new risk bounds for the ERM when the classification rules belong to some VC-class under margin conditions and discuss the optimality of these bounds in a minimax sense.

Subfields: Control and Systems Engineering, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/9cf78d8f2e124a756b7697c534340637c80dfd80

How researchers see this paper

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

In Control and Systems Engineering

In Statistics and Probability

Citations in the corpus

On the Value of Target Data in Transfer Learning (2020, background): “The first one is a so-called Bernstein Class Condition on noise [26, 27, 28, 29, 30].”
Active and passive learning of linear separators under log-concave distributions (2012, methodology): “…substantial attention in statistical learning theory, both for passive and active learning (Mammen and Tsybakov, 1999; Bartlett et al., 2005; Massart and Nedelec, 2006; Gin´e and Koltchinskii, 2006; Balcan et al., 2007; Koltchinskii, 2010; Hanneke, 2011); this includes the random…”
Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate (2018, background): “For all t ≥ 0, h -hard margin condition [31].”
Statistical performance of support vector machines (2008, methodology): “Examples are the classical VC-dimension setting using classiﬁcation loss (in this case the result of [23] is actually suﬃcient; see also the more detailed study [24]), or regularized Boosting-type procedures (see [9], where an earlier version of the model selection theorem presented here was used).”
Ranking the Best Instances (2006, background): “It has been noticed (see Mammen and Tsybakov, 1999; Tsybakov, 2004; Massart and Nédélec, 2006) that it is possible to derive such rates of convergence in the classification setup under additional assumptions on the distribution.”
A high-dimensional Wilks phenomenon (2011, methodology): “Hence, rather than resorting to omnibus results like those presented in the aforementioned references, we rely on ad hoc analysis which has already proved convenient and successful (Massart 2000b; Massart and Nedelec 2006; Massart 2007).”
Knowledge Distillation in Wide Neural Networks: Risk Bound, Data Efficiency and Imperfect Teacher (2020, methodology): “However in statistical learning, [22, 15] prove that given some criterion on the logits distribution near class boundary, this rate can approach O(1/n), instead of O(1/ √ n) given by traditional VC theory.”
ROBUST EMPIRICAL MEAN ESTIMATORS (2011, background): “…s n denote the classical empirical risk minimizer, s n = arg min t ∈ S P n γ ( t ). b b b b s n is known to have a nice behavior when the contrast γ is bounded and under some margin condition such as (see [25, 27] and the references therein), Our approach does not require a ﬁnite sup norm for γ .”
Convergence rates of least squares regression estimators with heavy-tailed errors (2017, background): “ ERRORS 3 Here we will mainly focus on measuring loss or risk in the sense of the prediction loss (b) since it corresponds to the usual choice in the language of Empirical Risk Minimization; see e.g. [8, 9, 10, 37, 38, 49, 71, 75, 77]. Thus we will (usually) measure loss or risk in L 2(P) and hence ”
Oracle inequalities in empirical risk minimization and sparse recovery problems (2011, background): “We conclude this section with a theorem by Giné and Koltchinskii [50] that refines an earlier result by Massart and Nedelec [71].”
Ranking and empirical minimization of U-statistics (2006, background): “In classiﬁcation this can be guaranteed under certain “low-noise” conditions (see Tsybakov [43], Massart and Nédélec [33], Koltchinskii [26]).”
Classification with reject option (2006, background): “This extends the result by Massart and Nédélec (2003), who obtain a similar result for the case d = 1/2 (no reject option) only and who assume in addition that the Bayes classifier f∗ 21 belongs to the set F .”