Blog · Collection
Concentration inequalities
Why functions of many independent variables are nearly constant: variance bounds, Poincaré and log-Sobolev inequalities, transportation, and suprema of random processes via chaining.
A function of many independent random variables that does not depend too much on any one of them is nearly constant. This principle, called concentration of measure, sits underneath much of modern high-dimensional statistics and learning theory.
Variance bounds
The Efron–Stein inequality bounds the variance of by the expected effect of resampling one coordinate at a time:
where replaces with an independent copy. Poincaré inequalities express the same idea with gradients. For the standard Gaussian measure, , with a constant that does not depend on the dimension.
Exponential concentration
Variance bounds only give Chebyshev-type tails. Much stronger, Gaussian-type tails come from controlling the moment generating function, and entropy methods do this systematically. A log-Sobolev inequality, combined with Herbst’s argument, shows that every 1-Lipschitz function of a standard Gaussian vector satisfies
whatever the dimension. Transportation inequalities give an equivalent route, comparing relative entropy with the cost of moving one distribution onto another.
Suprema of random processes
Many statistical questions are about the worst case, such as the largest deviation of an empirical average over a whole class of functions. To bound the expected supremum of a process indexed by a set , a union bound over points is far too crude. Chaining instead approximates at finer and finer scales, which leads to Dudley’s entropy integral, a bound in terms of the covering numbers :
Bounds like this drive the generalization guarantees of learning theory and the error rates of high-dimensional estimators.