Concentration Inequalities

If $X \geq 0$, then for any $t > 0$:

$\Pr[X \geq t] \leq \frac{\mathbb{E}[X]}{t}$

If the average value of $X$ is small, then $X$ cannot be large too often. If $\mathbb{E}[X] = 1$, then $X$ can be $\geq 100$ at most 1% of the time; otherwise the average would be too high.

Markov's inequality is the foundation that all other concentration inequalities build upon. Chebyshev applies Markov to $(X - \mu)^2$. Hoeffding and Bernstein apply Markov to $e^{\lambda(X - \mu)}$. It is the weakest bound but requires the fewest assumptions.

The bound $\Pr[X \geq t] \leq \mu/t$ decays only as $1/t$, polynomially. This is far too slow for most applications. If $\mathbb{E}[X] = 1$, Markov gives $\Pr[X \geq 10] \leq 1/10$, independent of any variance or boundedness structure. For well-behaved distributions the true probability is astronomically smaller. Markov uses only $\mathbb{E}[X]$; it cannot see $\sigma$. Chebyshev is the first inequality that brings variance information into the picture. You almost always want Hoeffding or Bernstein when those assumptions hold.

For any random variable $X$ with mean $\mu$ and variance $\sigma^2$, for any $t > 0$:

$\Pr[|X - \mu| \geq t] \leq \frac{\sigma^2}{t^2}$

For the sample mean of $n$ i.i.d. variables with variance $\sigma^2$:

$\Pr[|\bar{X}_n - \mu| \geq t] \leq \frac{\sigma^2}{nt^2}$

Chebyshev uses variance information: if the spread of $X$ around its mean is small ($\sigma^2$ is small), then large deviations are unlikely. Applied to the sample mean, the variance decreases as $1/n$, giving the familiar $O(1/n)$ concentration.

Chebyshev gives the first quantitative form of the law of large numbers: with probability $\geq 1 - \delta$, $|\bar{X}_n - \mu| \leq \sigma/\sqrt{n\delta}$. This requires $n = O(\sigma^2/\epsilon^2\delta)$ for an $\epsilon$-accurate estimate. Note the $1/\delta$ dependence, not $\log(1/\delta)$.

The $1/t^2$ decay is still polynomial. Chebyshev cannot give you the $\log(1/\delta)$ dependence needed for efficient learning. For bounded random variables, Hoeffding gives exponentially better tails. Chebyshev is most useful when you know the variance but nothing about higher moments or boundedness.

Let $X_1, \ldots, X_n$ be independent random variables with $a_i \leq X_i \leq b_i$ almost surely. Then for any $t > 0$:

$\Pr\!\left[\bar{X}_n - \mu \geq t\right] \leq \exp\!\left(-\frac{2n^2t^2}{\sum_{i=1}^n (b_i - a_i)^2}\right)$

For the two-sided version:

$\Pr\!\left[|\bar{X}_n - \mu| \geq t\right] \leq 2\exp\!\left(-\frac{2n^2t^2}{\sum_{i=1}^n (b_i - a_i)^2}\right)$

Special case: If all $X_i \in [a, b]$ (identically bounded):

$\Pr[|\bar{X}_n - \mu| \geq t] \leq 2\exp\!\left(-\frac{2nt^2}{(b-a)^2}\right)$

Bounded random variables have sub-Gaussian tails. The width of the bounding interval $(b_i - a_i)$ controls the "effective variance" of each variable. The bound says: the probability of a deviation of size $t$ decays exponentially in $nt^2$, with the rate determined by how spread out the bounds are.

Hoeffding is the workhorse of learning theory. The ERM generalization bound for finite classes, the uniform convergence bound, and many other results use Hoeffding at their core. The exponential tail gives $n = O((b-a)^2 \log(1/\delta)/\epsilon^2)$. The $\log(1/\delta)$ dependence is what makes high-confidence bounds feasible.

Hoeffding uses only the range $[a_i, b_i]$, not the actual variance. If the variance is much smaller than $(b_i - a_i)^2/4$ (e.g., a variable that is usually 0 but can be as large as 1), Hoeffding is loose. Bernstein fixes this by incorporating variance information.

Let $X_1, \ldots, X_n$ be independent with $\mathbb{E}[X_i] = \mu_i$, $\text{Var}(X_i) = \sigma_i^2$, and $|X_i - \mu_i| \leq M$ almost surely. Then for any $t > 0$:

$\Pr\!\left[\sum_{i=1}^n (X_i - \mu_i) \geq t\right] \leq \exp\!\left(-\frac{t^2/2}{\sum_{i=1}^n \sigma_i^2 + Mt/3}\right)$

For the sample mean with i.i.d. variables ($\sigma^2 = \text{Var}(X_i)$):

$\Pr[|\bar{X}_n - \mu| \geq t] \leq 2\exp\!\left(-\frac{nt^2/2}{\sigma^2 + Mt/3}\right)$

Bernstein interpolates between two regimes. For small deviations ($t \ll \sigma^2/M$), the $\sigma^2$ term dominates the denominator and the bound looks like $\exp(-nt^2/2\sigma^2)$, a variance-dependent Gaussian tail. For large deviations ($t \gg \sigma^2/M$), the $Mt/3$ term dominates and the bound looks like $\exp(-3nt/2M)$, a sub-exponential tail. The variance term makes Bernstein much tighter than Hoeffding when the variance is small relative to the range.

Bernstein is the right inequality when you have variance information. In learning theory, this matters for sparse or low-noise settings. For example, if the loss is usually close to zero (low empirical risk, low variance), Bernstein gives much tighter bounds than Hoeffding, because Hoeffding only knows the loss is in $[0, 1]$ while Bernstein knows the variance is small.

Bernstein requires knowing (or bounding) the variance, which is not always available. If you only know the range $[a, b]$, Hoeffding is simpler and sufficient. In practice, you can sometimes use an empirical estimate of the variance and apply Bernstein, but this introduces additional technical complications (you need a concentration bound on the variance estimate itself).