Premium
A sharp concentration inequality with applications
Author(s) -
Boucheron Stéphane,
Lugosi Gábor,
Massart Pascal
Publication year - 2000
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(200005)16:3<277::aid-rsa4>3.0.co;2-1
Subject(s) - logarithm , mathematics , inequality , concentration inequality , struct , entropy (arrow of time) , permutation (music) , measure (data warehouse) , combinatorics , discrete mathematics , computer science , physics , mathematical analysis , thermodynamics , data mining , acoustics , programming language
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. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 16: 277–292, 2000