In the previous page, we established the union bound as the mechanism for extending guarantees from individual hypotheses to entire hypothesis classes. But the union bound merely combines probability bounds—it doesn't create them. We need a tool that bounds how far an empirical average can deviate from its expectation.

Enter Hoeffding's inequality, one of the most important results in probability theory and the mathematical engine that powers PAC learning bounds. Named after the Finnish statistician Wassily Hoeffding, this inequality establishes that empirical averages of bounded random variables concentrate exponentially fast around their expectations.

The implications are profound: with only $m$ samples, the empirical risk of a hypothesis converges to its true risk at a rate of $1/\sqrt{m}$, with exponentially small probability of large deviations. This exponential decay is what makes learning from finite samples mathematically tractable.

In this page, we develop Hoeffding's inequality from first principles, building through Markov's inequality, Chernoff bounds, and the moment generating function technique. We then apply it to derive rigorous generalization bounds that complete the foundation of PAC learning.

Hoeffding's inequality belongs to a family of probability bounds that exploit exponential tail decay. To appreciate its power, we trace the development from the basic Markov inequality through progressively stronger bounds.

Markov's Inequality (The Foundation):

For any non-negative random variable $X$ and $a > 0$:

$$\mathbb{P}(X \geq a) \leq \frac{\mathbb{E}[X]}{a}$$

Proof: Let $\mathbf{1}{X \geq a}$ be the indicator of ${X \geq a}$. Since $X \geq 0$ and $X \geq a$ implies $X \geq a \cdot \mathbf{1}{X \geq a}$: $$\mathbb{E}[X] \geq \mathbb{E}[a \cdot \mathbf{1}_{X \geq a}] = a \cdot \mathbb{P}(X \geq a)$$

$\square$

Markov's inequality is weak (linear decay) but applies to any non-negative random variable with finite expectation. Its power comes from what we choose to plug in for $X$.

Chebyshev's Inequality (Using Variance):

Applying Markov to $(X - \mu)^2$ where $\mu = \mathbb{E}[X]$:

$$\mathbb{P}(|X - \mu| \geq a) = \mathbb{P}((X - \mu)^2 \geq a^2) \leq \frac{\mathbb{E}[(X-\mu)^2]}{a^2} = \frac{\text{Var}(X)}{a^2}$$

Chebyshev provides $1/a^2$ (quadratic) decay, an improvement over Markov's linear decay. But for sums of many random variables, we can do exponentially better.

The Chernoff Bound Technique (Exponential Decay):

The key insight: instead of applying Markov to $X$ directly, apply it to $e^{\lambda X}$ for suitable $\lambda > 0$.

For any $\lambda > 0$: $$\mathbb{P}(X \geq a) = \mathbb{P}(e^{\lambda X} \geq e^{\lambda a}) \leq \frac{\mathbb{E}[e^{\lambda X}]}{e^{\lambda a}}$$

The quantity $M_X(\lambda) = \mathbb{E}[e^{\lambda X}]$ is the moment generating function (MGF) of $X$. The Chernoff technique minimizes the bound over $\lambda > 0$:

$$\mathbb{P}(X \geq a) \leq \inf_{\lambda > 0} e^{-\lambda a} M_X(\lambda)$$

To apply the Chernoff technique to bounded random variables, we need to control the moment generating function. Hoeffding's lemma provides this control.

Hoeffding's Lemma: Let $X$ be a random variable with $\mathbb{E}[X] = 0$ and $a \leq X \leq b$ almost surely. Then for all $\lambda \in \mathbb{R}$:

$$\mathbb{E}[e^{\lambda X}] \leq \exp\left(\frac{\lambda^2 (b-a)^2}{8}\right)$$

This bound is remarkable: the MGF of any zero-mean bounded random variable is controlled solely by the range $b - a$, regardless of the distribution's shape within that range.

Proof of Hoeffding's Lemma:

We present a rigorous proof exploiting the convexity of the exponential function.

Step 1: By convexity of $e^{\lambda x}$, for any $x \in [a, b]$: $$e^{\lambda x} \leq \frac{b - x}{b - a} e^{\lambda a} + \frac{x - a}{b - a} e^{\lambda b}$$

This expresses $e^{\lambda x}$ as a linear interpolation between the endpoint values.

Step 2: Taking expectations (using $\mathbb{E}[X] = 0$): $$\mathbb{E}[e^{\lambda X}] \leq \frac{b - \mathbb{E}[X]}{b - a} e^{\lambda a} + \frac{\mathbb{E}[X] - a}{b - a} e^{\lambda b} = \frac{b}{b-a} e^{\lambda a} + \frac{-a}{b-a} e^{\lambda b}$$

Step 3: Let $p = -a/(b-a)$, so $1-p = b/(b-a)$. Then: $$\mathbb{E}[e^{\lambda X}] \leq (1-p) e^{\lambda a} + p \cdot e^{\lambda b}$$

Step 4: Define $h = \lambda(b-a)$ and $L(h) = -p \cdot h + \ln((1-p) + p \cdot e^h)$. Then: $$\mathbb{E}[e^{\lambda X}] \leq e^{L(h)}$$

Step 5: We bound $L(h) \leq h^2/8$ using Taylor expansion.

$L(0) = 0$, $L'(0) = -p + \frac{p}{1} = 0$, and: $$L''(h) = \frac{p(1-p)e^h}{((1-p) + pe^h)^2} \leq \frac{1}{4}$$

The last inequality uses $ab \leq (a+b)^2/4$ for $a, b \geq 0$.

By Taylor's theorem with Lagrange remainder: $$L(h) = L(0) + L'(0) \cdot h + \frac{L''(\xi)}{2} h^2 \leq \frac{h^2}{8}$$

Substituting $h = \lambda(b-a)$: $$\mathbb{E}[e^{\lambda X}] \leq \exp\left(\frac{\lambda^2(b-a)^2}{8}\right)$$

$\square$

We now state and prove Hoeffding's inequality in its full generality, then specialize to the forms most useful for machine learning.

Theorem (Hoeffding's Inequality): Let $X_1, \ldots, X_m$ be independent random variables with $a_i \leq X_i \leq b_i$ almost surely. Let $S_m = \sum_{i=1}^m X_i$ and $\mu = \mathbb{E}[S_m] = \sum_{i=1}^m \mathbb{E}[X_i]$. Then for any $t > 0$:

$$\mathbb{P}(S_m - \mu \geq t) \leq \exp\left(-\frac{2t^2}{\sum_{i=1}^m (b_i - a_i)^2}\right)$$

$$\mathbb{P}(\mu - S_m \geq t) \leq \exp\left(-\frac{2t^2}{\sum_{i=1}^m (b_i - a_i)^2}\right)$$

Combining these (union bound): $$\mathbb{P}(|S_m - \mu| \geq t) \leq 2\exp\left(-\frac{2t^2}{\sum_{i=1}^m (b_i - a_i)^2}\right)$$

Proof:

We prove the upper tail bound; the lower tail follows by symmetry (applying the same argument to $-X_i$).

Step 1 (Chernoff Technique): For any $\lambda > 0$: $$\mathbb{P}(S_m - \mu \geq t) = \mathbb{P}(e^{\lambda(S_m - \mu)} \geq e^{\lambda t}) \leq e^{-\lambda t} \mathbb{E}[e^{\lambda(S_m - \mu)}]$$

Step 2 (Independence): Since the $X_i$ are independent: $$\mathbb{E}[e^{\lambda(S_m - \mu)}] = \mathbb{E}\left[\prod_{i=1}^m e^{\lambda(X_i - \mathbb{E}[X_i])}\right] = \prod_{i=1}^m \mathbb{E}[e^{\lambda(X_i - \mathbb{E}[X_i])}]$$

Step 3 (Apply Hoeffding's Lemma): Let $Y_i = X_i - \mathbb{E}[X_i]$. Then $\mathbb{E}[Y_i] = 0$ and $Y_i \in [a_i - \mathbb{E}[X_i], b_i - \mathbb{E}[X_i]]$, which has length $b_i - a_i$.

By Hoeffding's lemma: $$\mathbb{E}[e^{\lambda Y_i}] \leq \exp\left(\frac{\lambda^2(b_i - a_i)^2}{8}\right)$$

Step 4 (Combine): $$\mathbb{P}(S_m - \mu \geq t) \leq e^{-\lambda t} \prod_{i=1}^m \exp\left(\frac{\lambda^2(b_i - a_i)^2}{8}\right) = \exp\left(-\lambda t + \frac{\lambda^2}{8} \sum_{i=1}^m (b_i - a_i)^2\right)$$

Step 5 (Optimize over λ): Let $c = \sum_{i=1}^m (b_i - a_i)^2$. Minimize $f(\lambda) = -\lambda t + \lambda^2 c/8$: $$f'(\lambda) = -t + \frac{\lambda c}{4} = 0 \implies \lambda^* = \frac{4t}{c}$$

Substituting: $$f(\lambda^*) = -\frac{4t^2}{c} + \frac{16t^2}{8c} = -\frac{4t^2}{c} + \frac{2t^2}{c} = -\frac{2t^2}{c}$$

Thus: $$\mathbb{P}(S_m - \mu \geq t) \leq \exp\left(-\frac{2t^2}{\sum_{i=1}^m (b_i - a_i)^2}\right)$$

$\square$

Let us develop deep intuition for what Hoeffding's inequality tells us and why it has the form it does.

The Exponential Decay:

The bound $2e^{-2m\epsilon^2}$ decays exponentially in $m\epsilon^2$. This means:

• Probability of deviation $\epsilon$ decreases exponentially fast with sample size $m$
• For fixed $m$, probability of larger deviations decreases exponentially fast
• The product $m\epsilon^2$ captures the 'signal-to-noise ratio' of detection

Rate of Concentration:

To achieve deviation at most $\epsilon$ with probability at least $1 - \delta$: $$2e^{-2m\epsilon^2} \leq \delta \implies m \geq \frac{\ln(2/\delta)}{2\epsilon^2}$$

Alternatively, with $m$ samples, with probability $\geq 1 - \delta$: $$|\hat{\mu} - \mu| \leq \sqrt{\frac{\ln(2/\delta)}{2m}}$$

Why $1/\epsilon^2$ and Not $1/\epsilon$?

The $1/\epsilon^2$ dependence arises from the Central Limit Theorem. For i.i.d. random variables:

• The sample mean $\hat{\mu}_m$ has standard deviation $\sigma/\sqrt{m}$
• To achieve deviation $\epsilon$, we need $\sigma/\sqrt{m} \propto \epsilon$
• Thus $m \propto 1/\epsilon^2$

Hoeffding's inequality captures this CLT-like behavior with explicit, non-asymptotic bounds.

Comparison to CLT:

The CLT tells us $\sqrt{m}(\hat{\mu}_m - \mu) \xrightarrow{d} \mathcal{N}(0, \sigma^2)$, implying: $$\mathbb{P}(|\hat{\mu}_m - \mu| \geq \epsilon) \approx 2\Phi(-\epsilon\sqrt{m}/\sigma)$$

For large deviations, Hoeffding can be tighter or looser than the CLT approximation:

• Hoeffding is distribution-free (holds for any bounded distribution)
• Hoeffding is non-asymptotic (exact for any $m$, not just large $m$)
• CLT can be tighter when the true variance is much smaller than $(b-a)^2/4$

We now apply Hoeffding's inequality to the core concern of statistical learning theory: bounding the generalization gap between empirical and true risk.

Setting:

Let $h$ be a hypothesis, $\ell$ a loss function taking values in $[0, 1]$ (e.g., 0-1 loss for classification). Given i.i.d. samples $(x_1, y_1), \ldots, (x_m, y_m) \sim \mathcal{D}$, define:

• True Risk: $R(h) = \mathbb{E}_{(x,y) \sim \mathcal{D}}[\ell(h(x), y)]$
• Empirical Risk: $\hat{R}(h) = \frac{1}{m} \sum_{i=1}^m \ell(h(x_i), y_i)$

The random variables $Z_i = \ell(h(x_i), y_i)$ are i.i.d. with $Z_i \in [0, 1]$ and $\mathbb{E}[Z_i] = R(h)$.

Applying Hoeffding:

For a fixed hypothesis $h$: $$\mathbb{P}(|\hat{R}(h) - R(h)| \geq \epsilon) \leq 2e^{-2m\epsilon^2}$$

With probability at least $1 - \delta$: $$|\hat{R}(h) - R(h)| \leq \sqrt{\frac{\ln(2/\delta)}{2m}}$$

Combining with Union Bound:

For a finite hypothesis class $\mathcal{H} = {h_1, \ldots, h_M}$, apply the union bound:

$$\mathbb{P}(\exists h \in \mathcal{H}: |\hat{R}(h) - R(h)| > \epsilon) \leq \sum_{i=1}^M \mathbb{P}(|\hat{R}(h_i) - R(h_i)| > \epsilon) \leq 2Me^{-2m\epsilon^2}$$

Theorem (Uniform Convergence for Finite Hypothesis Classes):

With probability at least $1 - \delta$, simultaneously for all $h \in \mathcal{H}$:

$$|\hat{R}(h) - R(h)| \leq \sqrt{\frac{\ln(2|\mathcal{H}|/\delta)}{2m}}$$

Proof: Set $2|\mathcal{H}|e^{-2m\epsilon^2} = \delta$ and solve for $\epsilon$: $$\epsilon = \sqrt{\frac{\ln(2|\mathcal{H}|/\delta)}{2m}}$$

$\square$

Generalization Bound for ERM:

Let $\hat{h}$ be the empirical risk minimizer over $\mathcal{H}$: $$\hat{h} = \arg\min_{h \in \mathcal{H}} \hat{R}(h)$$

Let $h^* = \arg\min_{h \in \mathcal{H}} R(h)$ be the optimal hypothesis in $\mathcal{H}$.

With probability at least $1 - \delta$: $$R(\hat{h}) \leq R(h^*) + 2\sqrt{\frac{\ln(2|\mathcal{H}|/\delta)}{2m}}$$

Proof: \begin{align*} R(\hat{h}) &\leq \hat{R}(\hat{h}) + \epsilon \quad \text{(uniform convergence)} \ &\leq \hat{R}(h^) + \epsilon \quad \text{(definition of ERM)} \ &\leq R(h^) + 2\epsilon \quad \text{(uniform convergence)} \end{align*}

$\square$

This is the foundational PAC learning guarantee: ERM over a finite hypothesis class generalizes, with excess risk scaling as $O(\sqrt{(\ln|\mathcal{H}|)/m})$.

Hoeffding's inequality, while powerful, admits several refinements that provide tighter bounds in special cases.

Bennett's Inequality (Variance-Aware):

For independent random variables with $X_i - \mathbb{E}[X_i] \leq b$ and variance $\sigma_i^2$:

$$\mathbb{P}(S_m - \mu \geq t) \leq \exp\left(-\frac{v}{b^2} \cdot h\left(\frac{bt}{v}\right)\right)$$

where $v = \sum_i \sigma_i^2$ and $h(u) = (1+u)\ln(1+u) - u$.

Bennett's bound is tighter when variance is small relative to the range.

Bernstein's Inequality (Simplified):

A simpler approximation to Bennett: $$\mathbb{P}(S_m - \mu \geq t) \leq \exp\left(-\frac{t^2/2}{v + bt/3}\right)$$

For small $t$ (small deviations), this is approximately $\exp(-t^2/(2v))$—a Gaussian-like bound with the actual variance.

For large $t$ (large deviations), this is approximately $\exp(-3t/(2b))$—exponential in $t$ with rate depending on the bound $b$.

McDiarmid's Inequality (Bounded Differences):

A powerful generalization for functions of independent random variables.

Theorem: Let $X_1, \ldots, X_m$ be independent random variables taking values in sets $\mathcal{X}_1, \ldots, \mathcal{X}_m$. Let $f: \mathcal{X}_1 \times \ldots \times \mathcal{X}_m \to \mathbb{R}$ satisfy the bounded differences property:

$$\sup_{x_1,\ldots,x_m, x'_i} |f(x_1,\ldots,x_i,\ldots,x_m) - f(x_1,\ldots,x'_i,\ldots,x_m)| \leq c_i$$

Then: $$\mathbb{P}(f(X_1,\ldots,X_m) - \mathbb{E}[f] \geq t) \leq \exp\left(-\frac{2t^2}{\sum_{i=1}^m c_i^2}\right)$$

Application to Learning Theory:

Consider the empirical risk $\hat{R}(h) = \frac{1}{m}\sum_{i=1}^m \ell(h(x_i), y_i)$.

Changing a single sample $(x_i, y_i)$ changes $\hat{R}(h)$ by at most $1/m$ (for $[0,1]$-bounded loss).

By McDiarmid: $$\mathbb{P}(|\hat{R}(h) - \mathbb{E}[\hat{R}(h)]| \geq t) \leq 2\exp\left(-\frac{2t^2}{m \cdot (1/m)^2}\right) = 2\exp(-2mt^2)$$

This recovers Hoeffding for empirical averages!

Let us implement Hoeffding's inequality and visualize how concentration improves with sample size.

We have developed Hoeffding's inequality—the mathematical engine powering concentration bounds in statistical learning theory.

What's Next:

With the union bound + Hoeffding's inequality, we can bound generalization for finite hypothesis classes. But what about infinite classes like linear classifiers or neural networks? The next page introduces Rademacher complexity—a data-dependent complexity measure that provides generalization bounds for infinite hypothesis classes by measuring how well the class can fit random noise.