Concentration Inequalities

Every inequality on this page bounds the same kind of quantity — the probability that a random variable is far from its mean — and each pays for its conclusion with a different hypothesis. The table is the summary; the rest of the page is the proofs.

| Inequality | Hypothesis | Tail bound on $\P(|Z - \E Z| \ge t)$ | Decay | | --- | --- | --- | --- | | Markov | $Z \ge 0$ | $\E Z/t$ (one-sided, about 0) | $1/t$ | | Chebyshev | $\Var Z < \infty$ | $\sigma^2/t^2$ | $1/t^2$ | | Chernoff | MGF finite | $e^{-\sup_\lambda(\lambda t - \psi(\lambda))}$ | shape of $\psi^*$ | | Hoeffding | $Z = \sum X_i$, independent, $X_i \in [a_i,b_i]$ | $2\exp\!\big(-2t^2/\sum(b_i-a_i)^2\big)$ | Gaussian | | Bernstein | as Hoeffding, plus variance $\sigma^2$ | $2\exp\!\big(-t^2/(2\sigma^2 + 2Mt/3)\big)$ | Gaussian then exponential | | Azuma | martingale, increments in $[-c_i,c_i]$ | $2\exp\!\big(-t^2/(2\sum c_i^2)\big)$ | Gaussian | | McDiarmid | $f$ with bounded differences $c_i$ | $2\exp\!\big(-2t^2/\sum c_i^2\big)$ | Gaussian | | Gaussian concentration | $f$ $K$-Lipschitz, $X\sim\Ncal(0,I_d)$ | $2\exp\!\big(-t^2/(2K^2)\big)$ | Gaussian, dimension-free |

Run it: Concentration inequalities, side by sideEmpirical tail probabilities of a sample mean against the Markov, Chebyshev, Hoeffding and Bernstein bounds.

The two moment inequalities

TheoremMarkov's inequality

Let $Z \ge 0$ be a random variable and $t > 0$. Then

$$\P(Z \ge t) \le \frac{\E Z}{t}.$$

ProofReveal

CorollaryChebyshev's inequality

If $\E Z^2 < \infty$ then for all $t>0$,

$$\P\big(|Z - \E Z| \ge t\big) \le \frac{\Var(Z)}{t^2}.$$

ProofReveal

More generally, applying Markov to $|Z - \E Z|^p$ gives $\P(|Z-\E Z| \ge t) \le \E|Z-\E Z|^p/t^p$, so each finite moment buys one more power of $t$. Sub-Gaussianity is, in this light, exactly the statement that all moments are available with the right growth, which is what upgrades polynomial decay to Gaussian decay.

PropositionMarkov and Chebyshev are attained

Both bounds are achieved with equality by explicit distributions, so neither can be improved without strengthening its hypotheses.

ProofReveal

The Chernoff method

PropositionThe Chernoff method

Let $Z$ have cumulant generating function $\psi(\lambda) = \log \E e^{\lambda Z}$, finite on an interval containing $0$. Then for every $t$,

$$\P(Z \ge t) \le \exp\big(-\psi^*(t)\big), \qquad \psi^*(t) = \sup_{\lambda > 0}\big(\lambda t - \psi(\lambda)\big),$$

where $\psi^*$ is the Legendre transform of $\psi$.

ProofReveal

Hoeffding's inequality

TheoremHoeffding's inequality

Let $X_1,\dots,X_n$ be independent with $X_i \in [a_i,b_i]$ almost surely, and let $S = \sum_{i=1}^n X_i$. Then for every $t \ge 0$,

$$\P\big(S - \E S \ge t\big) \le \exp\left(-\frac{2t^2}{\sum_{i=1}^n (b_i-a_i)^2}\right),$$

and the two-sided bound holds with an extra factor $2$. In particular, for i.i.d. $X_i \in [0,1]$ and $\bar X_n = S/n$,

$$\P\big(|\bar X_n - \mu| \ge t\big) \le 2e^{-2nt^2}.$$

ProofReveal

Inverting the bound is the form used in practice. Setting the right-hand side to $\delta$ and solving for $t$: with probability at least $1-\delta$,

$$|\bar X_n - \mu| \le \sqrt{\frac{\log(2/\delta)}{2n}}\qquad\text{for } X_i \in [0,1].$$

Note the shape: the dependence on the confidence level is $\sqrt{\log(1/\delta)}$, which is extremely mild — buying three more orders of magnitude of confidence costs a factor of about $1.6$ in the bound. This is the practical content of exponential concentration.

Bernstein's inequality

TheoremBernstein's inequality

Let $X_1,\dots,X_n$ be independent and centred with $|X_i| \le M$ almost surely, and set $\sigma^2 = \sum_{i=1}^n \E X_i^2$. Then for all $t \ge 0$,

$$\P\left(\sum_i X_i \ge t\right) \le \exp\left(-\frac{t^2}{2\sigma^2 + \tfrac{2}{3}Mt}\right).$$

ProofReveal

Beyond independence: Azuma and McDiarmid

DefinitionMartingale

A sequence $(Z_0, Z_1, \dots, Z_n)$ adapted to a filtration $\mathcal{F}_0 \subseteq \dots \subseteq \mathcal{F}_n$ is a martingale if each $Z_k$ is integrable and $\E[Z_k \mid \mathcal{F}_{k-1}] = Z_{k-1}$ for all $k$. Its increments are $D_k = Z_k - Z_{k-1}$, which satisfy $\E[D_k\mid\mathcal{F}_{k-1}] = 0$.

TheoremAzuma–Hoeffding inequality

Let $(Z_k)_{k\le n}$ be a martingale whose increments satisfy $|D_k| \le c_k$ almost surely. Then for all $t\ge0$,

$$\P\big(Z_n - Z_0 \ge t\big) \le \exp\left(-\frac{t^2}{2\sum_{k=1}^n c_k^2}\right).$$

ProofReveal

TheoremMcDiarmid's bounded differences inequality

Let $X_1,\dots,X_n$ be independent random variables with $X_i$ taking values in a set $\Xcal_i$, and let $f : \prod_i \Xcal_i \to \R$ satisfy the bounded differences condition: for each $i$ there is $c_i$ with

$$\big|f(x_1,\dots,x_i,\dots,x_n) - f(x_1,\dots,x_i',\dots,x_n)\big| \le c_i$$

for all $x \in \prod_j \Xcal_j$ and all $x_i' \in \Xcal_i$. Then for $Z = f(X_1,\dots,X_n)$ and every $t \ge 0$,

$$\P\big(Z - \E Z \ge t\big) \le \exp\left(-\frac{2t^2}{\sum_{i=1}^n c_i^2}\right).$$

ProofReveal

Gaussian concentration

TheoremGaussian concentration for Lipschitz functions

Let $X \sim \Ncal(0, I_d)$ and let $f : \R^d \to \R$ be $K$-Lipschitz with respect to $\norm{\cdot}_2$. Then

$$\P\big(|f(X) - \E f(X)| \ge t\big) \le 2\exp\left(-\frac{t^2}{2K^2}\right) \qquad\text{for all } t\ge0 ,$$

equivalently $\norm{f(X) - \E f(X)}_{\psi_2} \le CK$ for an absolute constant $C$.

Proof (sketch)Reveal

CorollaryImmediate consequence: the norm concentrates

$f(x) = \norm{x}_2$ is $1$-Lipschitz, so for $X \sim \Ncal(0,I_d)$,

$$\P\big(|\norm{X}_2 - \E\norm{X}_2| \ge t\big) \le 2e^{-t^2/2},$$

with no dependence on $d$ whatsoever. Since $\E\norm{X}_2 = \sqrt d\,(1 + O(1/d))$, this is the statement explored numerically on the norm concentration page.

Problems

Markov and Chebyshev are attainedProof · Foundation · 15 min Derive Hoeffding's inequality from Hoeffding's lemmaProof · Intermediate · 30 min Locating the Bernstein crossoverNumerical · Intermediate · 30 min Applying McDiarmid to a medianProof · Advanced · 30 min Azuma for a random walk with driftProof · Intermediate · 30 min Simulate and compare the concentration inequalitiesCoding · Intermediate · 1 hour The Chernoff exponent is a Legendre transformProof · Advanced · 1 hour