A sharp concentration inequality with applications

By Stéphane Boucheron, Gábor Lugosi, Pascal Massart. 1999

We present a new general concentration-of-measure inequality and illustrate its power by applications in random combinatorics. The results find direct applications in some problems of learning theory.

How researchers see this paper

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

Citations in the corpus

NEW APPROACHES TO STATISTICAL LEARNING THEORY (2006, unknown): “(Boucheron et al. (2000)) Let Z and ( Z k ) k = 1 ..... n be as defined above.”
Extensions to McDiarmid's inequality when dierences are bounded with high probability (2002, background): “[4] discuss McDiarmid’s inequality and Talagrand’s inequality, as well as other concentration inequalities, with an emphasis on learning theory applications.”
Concentration Inequalities (2008, methodology): “In this section we focus on so-called “entropy method”, based on logarithmic Sobolev inequalities developed by Ledoux [20, 21], see also Bobkov and Ledoux [22], Massart [23], Rio [10], Boucheron, Lugosi, and Massart [25], [26], and Bousquet [27, 28].”
Oracle inequalities in empirical risk minimization and sparse recovery problems (2011, background): “I am especially thankful to Peter Bartlett, Lucien Birgé, Gilles Blanchard, Stephane Boucheron, Olivier Bousquet, Richard Dudley, Sara van de Geer, Evarist Giné, Gabor Lugosi, Pascal Massart, David Mason, Shahar Mendelson, Dmitry Panchenko, Alexandre Tsybakov, Aad van der Vaart, Jon Wellner and Jo”
Concentration inequalities using the entropy method (2003, methodology): “In this paper we follow the line of [4] to develop new easy-to-apply inequalities for general functions of independent random variables.”
New approaches to statistical learning theory (2003, unknown): “(Boucheron et al. (2002)) Let .”
Moment inequalities for functions of independent random variables (2005, background): “Such functionals were at the center of attention in [6] and [36] where they were called self-bounded functionals.”
On the Bennett–Hoeffding inequality (2009, background): “1+u)ln(1+u)−u; (1.2) see e.g. [1] concerning the importance of such bounds. Inequality (1.1) has been generalized to include cases when the X′ isare not independent and/or are not real-valued;seee.g. [12, 13, 14, 16, 18, 20, 23, 27, 28, 29, 30, 50, 35, 37, 55, 56, 57]. Inequality (1.1) is based on a”
Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies? (2004, background): “To see this, recall the Bernstein’s inequality [43] which states that if are independent random variables with mean-zero and obeying , then”
Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information (2004, background): “8) Slightly more precise estimates are possible, see [1].”
Statistical properties of kernel principal component analysis (2004, background): “4 Note that one could actually apply the inequality of [ 7 ] to this quantity to obtain a”
A Bennett concentration inequality and its application to suprema of empirical processes (2002, methodology): “In particular, many applications of this method have been exposed in [1, 2].”