Abstract

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

Keywords

LogarithmMathematicsInequalityConcentration inequalitystructEntropy (arrow of time)Permutation (music)Measure (data warehouse)CombinatoricsDiscrete mathematicsComputer sciencePhysicsMathematical analysisThermodynamicsData mining

Affiliated Institutions

Related Publications

Publication Info

Year
2000
Type
article
Volume
16
Issue
3
Pages
277-292
Citations
184
Access
Closed

External Links

Social Impact

Social media, news, blog, policy document mentions

Citation Metrics

184
OpenAlex

Cite This

Stéphane Boucheron, G�bor Lugosi, Pascal Massart (2000). A sharp concentration inequality with applications. Random Structures and Algorithms , 16 (3) , 277-292. https://doi.org/10.1002/(sici)1098-2418(200005)16:3<277::aid-rsa4>3.0.co;2-1

Identifiers

DOI
10.1002/(sici)1098-2418(200005)16:3<277::aid-rsa4>3.0.co;2-1