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.

If $X \in [0, 1]$ almost surely with $\mathbb{E}[X] = \mu$, then for any $a \in (0, 1)$:

$\Pr[X > 1 - a] \geq \frac{\mu - (1 - a)}{a}.$

Markov bounds the upper tail of a nonnegative variable. The same idea applied to $1 - X$ bounds the lower tail of $X$. The lemma is most useful when $X$ is something like an accuracy in $[0, 1]$ and you want a guarantee that $X$ is rarely far below its mean.

This is the form of Markov used in the Shalev-Shwartz and Ben-David proof of agnostic PAC learnability of finite hypothesis classes. The argument needs a lower bound on the probability that the empirical risk is not too far below the true risk; Lemma B.1 supplies that bound from a one-sided expectation control.

The bound is informative only when $\mu > 1 - a$. If $\mu \leq 1 - a$, the right-hand side is non-positive and the lemma reduces to the trivial bound $\Pr[\cdot] \geq 0$. Like Markov itself, the bound uses only the mean and the boundedness range; it cannot see variance.

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

$\Pr[|X - \mu| \geq t] \leq \frac{\sigma^2}{t^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. For i.i.d. $Z_1, \ldots, Z_m$ with mean $\mu$ and $\operatorname{Var}(Z_i) = \sigma^2$, the sample mean $\bar Z_m = \frac{1}{m}\sum_i Z_i$ has variance

$\operatorname{Var}(\bar Z_m) = \frac{1}{m^2}\sum_{i=1}^m \operatorname{Var}(Z_i) = \frac{\sigma^2}{m}$

(by independence the cross-terms vanish). Combining this with Chebyshev gives $\Pr[|\bar Z_m - \mu| \geq t] \leq \sigma^2/(m t^2)$. Equivalently, with probability $\geq 1 - \delta$, $|\bar Z_m - \mu| \leq \sigma/\sqrt{m\delta}$. 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 $Z_1, \ldots, Z_m$ be i.i.d. with $\mathbb{E}[Z_i] = \mu$ and $\operatorname{Var}(Z_i) \leq 1$. For any $\delta \in (0, 1)$, with probability at least $1 - \delta$:

$\left|\frac{1}{m}\sum_{i=1}^m Z_i - \mu\right| \leq \sqrt{\frac{1}{\delta m}}.$

Solve Chebyshev for the deviation. Setting the failure probability $\sigma^2/(m t^2) = \delta$ and inverting for $t$ gives $t = \sigma/\sqrt{m \delta}$. With the normalization $\sigma^2 \leq 1$, the radius is $1/\sqrt{m \delta}$.

This is the explicit finite-$m$ form behind "the sample mean is close to $\mu$." It is the version of Chebyshev quoted as Lemma B.2 in Shalev-Shwartz and Ben-David, Understanding Machine Learning, Appendix B, where it sets up the polynomial sample-complexity baseline that exponential bounds later improve. The decay rate of the radius is $1/\sqrt{\delta m}$: polynomial in $m$, with a $1/\sqrt{\delta}$ dependence on the confidence parameter.

The $1/\sqrt{\delta m}$ rate is too slow for PAC-style sample complexity. For confidence $\delta = 0.05$ and target accuracy $\varepsilon = 0.01$, the lemma needs $m \geq 1/(\delta \varepsilon^2) = 200{,}000$ samples; Hoeffding under the same boundedness assumption needs roughly $\log(2/\delta)/(2\varepsilon^2) \approx 18{,}500$, an order of magnitude fewer. The $1/\delta$ dependence is the bottleneck.

Let $(Y_i)_{i \in I}$ be a finite independent family of centered sub-Gaussian random variables with MGF parameters $c_i$. Then for any $\epsilon \geq 0$:

Sub-Gaussian MGF control behaves like variance under independent sums: the parameters add. Markov's inequality applied to $\exp(\lambda \sum_i Y_i)$ then converts that MGF bound into an exponential tail bound.

This is the exact formal bridge between concentration and finite-class learning bounds. Hoeffding for bounded losses first proves sub-Gaussian MGF control; the finite union bound then lifts the single-hypothesis tail bound to all hypotheses.

The conclusion is a one-sided tail bound for a finite independent sum. It does not by itself prove the bounded-variable Hoeffding theorem or a uniform convergence theorem; those need additional assumptions and a union-bound step.

Let $(X_i)_{i \in I}$ be a finite independent family of real random variables with $a_i \leq X_i \leq b_i$ almost surely. Then for $\epsilon \geq 0$:

Bounded variables are sub-Gaussian after centering. Once each centered variable has sub-Gaussian MGF parameter $((b_i-a_i)/2)^2$, independence lets those parameters add across the finite sum.

This is the claim-facing bridge between bounded losses and finite-class uniform convergence. Setting $\epsilon = nt$ gives the one-sided average Hoeffding form; applying the same argument to $-X_i$ and union-bounding the two tails gives the common two-sided display.

This statement covers the one-sided centered finite-sum bound. It does not by itself verify the two-sided display, the identical-bound special case, or a uniform convergence theorem; those need their own scoped claims or corollaries.

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).