Paper #376

Title:

A sharp concentration inequality with applications

Authors:

Stéphane Boucheron, Gábor Lugosi and Pascal Massart

Date:

April 1999

Abstract:

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.

Keywords:

Concentration of measure, Vapnik-Chervonenkis dimension, logarithmic Sobolev inequalities, longest monotone subsequence, model selection

JEL codes:

C1

Area of Research:

Statistics, Econometrics and Quantitative Methods

Published in:

Random Structures and Algorithms, 16, (2000), pp. 277-292

Download the paper in PDF format