concentration inequalities

Average enough independent random quantities and the average stops being random in any practical sense — it clamps tightly around its mean, with the odds of a large deviation falling off exponentially. Concentration inequalities make this precise and quantitative. They are the probabilistic bedrock of learning theory: every statement that empirical risk is close to true risk with high probability ultimately rests on one of them.

The toolbox forms a ladder. Hoeffding's inequality bounds the deviation of an average of bounded variables, with a Gaussian-like tail that depends only on the range. Bernstein and Bennett sharpen this when the variance is small, yielding faster rates by replacing the range with the variance — the source of fast rates. McDiarmid's bounded-differences inequality generalizes beyond sums to any function whose value changes little when one input is altered, which is exactly what symmetrization needs to control suprema over a class. Talagrand's inequality is the deep refinement for empirical processes.

Choosing the right inequality determines whether a bound carries the slow one-over-root-m rate or the fast one-over-m rate. Bernstein-type, variance-aware bounds underlie localized complexity and fast-rate learning; McDiarmid powers nearly every uniform-convergence proof. The standing assumption is independence or weak dependence; heavy tails or strong dependence require specialized tools and can degrade the exponential tails to merely polynomial ones.