Bernstein's inequality
/ BERN-shtine /
Bernstein's inequality is the variance-aware concentration bound: it controls a sum of independent variables using their actual variance and a single bound on their scale, recovering the Gaussian rate for small deviations and an exponential rate for large ones. It is the inequality you reach for when Hoeffding's variance proxy is wastefully large — bounded variables with small variance, or sub-exponential variables like squares of Gaussians, where a proxy-based bound throws away most of the available concentration.
There are two standard forms. The bounded form: if X_1, ..., X_n are independent, centered, with |X_i| <= b almost surely and total variance sigma^2 = sum Var(X_i), then P(sum X_i >= t) <= exp(-t^2 / (2(sigma^2 + bt/3))). The sub-exponential form: if the X_i are centered sub-exponential with parameters (nu_i, b) (meaning E[exp(lambda X_i)] <= exp(nu_i^2 lambda^2 / 2) only for |lambda| < 1/b), then P(sum X_i >= t) <= exp(-(1/2) min(t^2 / sum nu_i^2, t / b)). Both display the characteristic two-regime behaviour. For small t the denominator is dominated by sigma^2, giving the Gaussian tail exp(-t^2 / 2 sigma^2) — the right answer, scaled by the TRUE variance, not a proxy. For large t the bt/3 term (or the t/b regime) takes over, giving a Poissonian exponential tail exp(-3t / 2b) that reflects the bounded scale. The proof is again Chernoff, but the MGF is bounded more carefully: instead of dumping everything into a quadratic, one keeps the power series e^(lambda x) = 1 + lambda x + (lambda x)^2/2 + ... and bounds the higher terms by a geometric series in lambda b, which is exactly what produces the two regimes.
Bernstein is the workhorse of high-dimensional statistics precisely because the small-deviation regime uses the variance. When you estimate a mean from bounded data whose variance is much smaller than its range, Bernstein gives a rate scaling with sigma^2 rather than b^2 — often a dramatic improvement. The honest caveat: the crossover point between the two regimes is where the two terms in the min are equal, t ~ sigma^2/b, and where exactly the bound is tight matters for applications. Bennett's inequality is strictly sharper than Bernstein (Bennett implies Bernstein after a convexity bound on its rate function), and for the Poisson-like extreme tail Bennett gives the exact log-rate that Bernstein only approximates.
Estimate a probability p ~ 0.01 from n Bernoulli(p) samples. Each centered indicator has |X_i| <= 1 but variance p(1-p) ~ 0.01, far below 1. Hoeffding needs n ~ log(1/delta)/t^2; Bernstein, using sigma^2 = p(1-p), needs only n ~ p log(1/delta)/t^2 in the small-t regime — a 100-fold reduction when p = 0.01.
For rare events Bernstein's variance term beats Hoeffding by a factor 1/p.
Bernstein needs a bound on the scale (boundedness, or the sub-exponential parameter b); without any moment-generating-function control beyond polynomial moments, the two-regime bound need not hold. Bernstein is implied by, and slightly weaker than, Bennett.