A Sharp Concentration Inequality with Applications
Stéphane Boucheron, Gábor Lugosi, Pascal Massart · RePEc: Research Papers in Economics · 1999
We derive a new general concentration-of-measure inequality. The concentration inequality applies, among others, to configuration functions as defined by Talagrand and also to combinatorial entropies such as the logarithm of the number of increasing subsequences in a random permutation and to Vapnik-Chervonenkis (vc) entropies. The results find direct applications in statistical learning theory, substantiating the possibility to use the empirical vc-entropy in penalization techniques.