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 f(X1,…,Xn)f(X_1, \dots, X_n) by the expected effect of resampling one coordinate at a time:

Var⁡f(X)≤12∑i=1nE[(f(X)−f(X(i)))2],\operatorname{Var} f(X) \le \frac{1}{2}\sum_{i=1}^{n} \mathbb{E}\left[\big(f(X) - f(X^{(i)})\big)^2\right],

where X(i)X^{(i)} replaces XiX_i with an independent copy. Poincaré inequalities express the same idea with gradients. For the standard Gaussian measure, Var⁡f≤E∥∇f∥2\operatorname{Var} f \le \mathbb{E}\lVert \nabla f \rVert^2, 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

P(f(X)−Ef(X)≥t)≤e−t2/2,\mathbb{P}\big(f(X) - \mathbb{E}f(X) \ge t\big) \le e^{-t^2/2},

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 TT, a union bound over points is far too crude. Chaining instead approximates TT at finer and finer scales, which leads to Dudley’s entropy integral, a bound in terms of the covering numbers N(T,d,ε)N(T, d, \varepsilon):

Esup⁡t∈TXt≲∫0∞log⁡N(T,d,ε) dε.\mathbb{E}\sup_{t \in T} X_t \lesssim \int_0^\infty \sqrt{\log N(T, d, \varepsilon)}\, d\varepsilon.

Bounds like this drive the generalization guarantees of learning theory and the error rates of high-dimensional estimators.

← All collections