Concentration inequalities: Chernoff, Hoeffding and sample sizes

Before this lesson: lesson 06 (Markov, Chebyshev, the law of large numbers and the CLT) and lesson 03 (moment generating functions). Convexity and Taylor's theorem from calculus (calculus 03) are used in one proof. Time: about 60 minutes, plus the notebook.

---

Why this matters #

• How big must a test set be? Hoeffding answers with a number that holds for every model and every data distribution: 1,060 examples for an error below 0.05 with probability 0.99.
• Generalisation bounds. "Training error is close to test error" is a concentration statement. For a finite set of $k$ models it follows from Hoeffding and the union bound; VC dimension and Rademacher complexity extend it to infinite model classes (deep learning 17).
• Test-set reuse and leaderboards. Each time you pick the best of $k$ models on the same test set, its score is biased upwards by about $\sqrt{\ln k / n}$. This is why benchmarks keep a hidden test set.
• Bandits and reinforcement learning. The UCB algorithm adds the Hoeffding width $\sqrt{2\ln t / n_a}$ to each arm's mean reward (reinforcement learning 03).
• Randomised algorithms in high dimension. Random projections (the Johnson–Lindenstrauss lemma), randomised SVD and sketching rely on sub-Gaussian concentration (linear algebra 18).

1. Predict first #

2. The picture #

Flip a fair coin $n = 100$ times. What is the probability of 60 or more heads, that is $\bar X_n - 0.5 \ge 0.1$? Here is the exact value next to what each tool says. Section 3 derives every bound.

method	value	kind
Markov, $\mathbb{E}[\bar X_n]/0.6$	0.833	bound
Chebyshev, $\operatorname{Var}(\bar X_n)/\varepsilon^2 = 0.0025/0.01$	0.25	bound
Cantelli (one-sided Chebyshev)	0.20	bound
Hoeffding, $e^{-2n\varepsilon^2}$	0.135	bound
Chernoff, $e^{-n\,\mathrm{KL}(0.6 \,\|\, 0.5)}$	0.134	bound
exact binomial, $P(S_{100} \ge 60)$	0.0284	exact
CLT, $P(Z \ge 2)$	0.0228	approximation

At one $n$ the differences look small. The real difference is how the bounds change with $n$. Chebyshev falls like $1/n$: a polynomial tail. Hoeffding and Chernoff fall like $e^{-cn}$: an exponential tail, the same rate as the exact probability. On a log scale an exponential tail is a straight line.

Interactive figure: loading…

Where does the exponential come from? Markov's inequality uses only the mean. It can be applied to any nonnegative increasing function of the variable. If we apply it to $e^{\lambda S}$, the bound uses the whole moment generating function, and independence makes that function a product. The free parameter $\lambda > 0$ is then chosen to make the bound as small as possible.

Interactive figure: loading…

3. Definitions and main results #

Markov and Chebyshev, and why they are loose #

Recall from lesson 06: Markov's inequality $P(X \ge a) \le \mathbb{E}[X]/a$ for $X \ge 0$, and Chebyshev's inequality $P(|X - \mu| \ge \varepsilon) \le \sigma^2/\varepsilon^2$. Both are tight for some two- or three-point distribution, so they cannot be improved without more information. But for an average of many independent variables we have much more information, and both bounds waste it.

Cantelli's inequality (one-sided Chebyshev). For $t > 0$, $P(X - \mu \ge t) \le \dfrac{\sigma^2}{\sigma^2 + t^2}$, always below $\sigma^2/t^2$.

Proof of Cantelli's inequality

1. For every $u \ge 0$: $X - \mu \ge t$ implies $X - \mu + u \ge t + u > 0$, so it implies $(X - \mu + u)^2 \ge (t + u)^2$.
2. Markov on $(X - \mu + u)^2$: $P(X - \mu \ge t) \le \dfrac{\mathbb{E}[(X - \mu + u)^2]}{(t + u)^2} = \dfrac{\sigma^2 + u^2}{(t + u)^2}$.
3. Choose $u = \sigma^2/t$, which minimises the right side. Then $\dfrac{\sigma^2 + \sigma^4/t^2}{(t + \sigma^2/t)^2} = \dfrac{\sigma^2(t^2 + \sigma^2)/t^2}{(t^2 + \sigma^2)^2/t^2} = \dfrac{\sigma^2}{\sigma^2 + t^2}$. $\blacksquare$

Chebyshev is not always sharper than Markov. Take $X \sim \text{Exp}(1)$ (mean 1, variance 1). The true tail is $P(X \ge a) = e^{-a}$.

$a$	exact $e^{-a}$	Markov $1/a$	Chebyshev $1/(a - 1)^2$	Chernoff $a\,e^{1-a}$
2	0.135	0.5	1	0.736
5	0.0067	0.2	0.0625	0.092
10	0.000045	0.1	0.0123	0.0012

(Chebyshev here uses $P(X \ge a) \le P(|X - 1| \ge a - 1)$.) At $a = 2$ Markov wins; for large $a$ Chebyshev wins; and only the exponential Chernoff bound follows the exponential decay of the truth.

The Chernoff method #

Theorem (Chernoff bound). For every random variable $S$ and every $t$,

Proof.

1. Fix $\lambda > 0$. The map $x \mapsto e^{\lambda x}$ is increasing, so the events $\{S \ge t\}$ and $\{e^{\lambda S} \ge e^{\lambda t}\}$ are the same.
2. $e^{\lambda S} \ge 0$, so Markov gives $P(S \ge t) \le \mathbb{E}[e^{\lambda S}]/e^{\lambda t}$.
3. This holds for every $\lambda > 0$, so it also holds for the infimum over $\lambda$. $\blacksquare$

Sums of independent variables. Let $S = \sum_{i=1}^n (X_i - \mu)$ with $X_i$ i.i.d. By independence, the expectation of a product is the product of the expectations, so $\mathbb{E}[e^{\lambda S}] = \big(\mathbb{E}[e^{\lambda(X - \mu)}]\big)^n$. Write $\psi(\lambda) = \ln \mathbb{E}[e^{\lambda(X - \mu)}]$ for the cumulant generating function (CGF) of the centred variable. With $S = n(\bar X_n - \mu)$ and threshold $nt$:

The exponent grows linearly in $n$: the bound decays exponentially. The function $\psi^*(t) = \sup_\lambda (\lambda t - \psi(\lambda))$ is the Legendre transform of $\psi$; it is the rate in Cramér's large-deviation theorem.

Example 1: Gaussian. For $\mathcal N(\mu, \sigma^2)$, $\psi(\lambda) = \sigma^2\lambda^2/2$. The exponent $\lambda t - \sigma^2\lambda^2/2$ is a downward parabola; its maximum is at $\lambda^* = t/\sigma^2$, with value $t^2/(2\sigma^2)$. So

For one standard Gaussian at $t = 2$: the bound is $e^{-2} = 0.135$, the truth is 0.0228. The exponent is right; the bound misses only a factor of order $1/t$.

Example 2: Bernoulli. For Bernoulli($p$) and $q = p + t < 1$, the optimal $\lambda$ is $\lambda^* = \ln\frac{q(1 - p)}{p(1 - q)}$, and the bound becomes

where $\mathrm{KL}$ is the Kullback–Leibler divergence between two Bernoulli distributions (information theory 03). This is the 0.134 in the table.

Hoeffding's inequality #

To use the Chernoff method we need an upper bound on the MGF. For bounded variables, Hoeffding's lemma gives one.

Hoeffding's lemma. If $a \le X \le b$, then for every $\lambda \in \mathbb{R}$,

A bounded variable has an MGF no larger than that of a Gaussian with variance $(b - a)^2/4$.

Proof of Hoeffding's lemma

Shift $X$ so that $\mathbb{E}X = 0$; then $a \le 0 \le b$.

1. The function $x \mapsto e^{\lambda x}$ is convex, so on $[a, b]$ it lies below its chord: $e^{\lambda x} \le \dfrac{b - x}{b - a}\,e^{\lambda a} + \dfrac{x - a}{b - a}\,e^{\lambda b}$.
2. Take expectations and use $\mathbb{E}X = 0$: $\mathbb{E}e^{\lambda X} \le \dfrac{b}{b - a}\,e^{\lambda a} - \dfrac{a}{b - a}\,e^{\lambda b}$.
3. Write $u = \lambda(b - a)$ and $p = -a/(b - a) \in [0, 1]$. The right side equals $e^{\varphi(u)}$ with $\varphi(u) = -pu + \ln(1 - p + p\,e^{u})$.
4. $\varphi(0) = 0$ and $\varphi'(0) = -p + p = 0$. The second derivative is $\varphi''(u) = q(1 - q)$ with $q = \dfrac{p\,e^u}{1 - p + p\,e^u} \in [0, 1]$, so $\varphi''(u) \le 1/4$.
5. Taylor's theorem with the remainder: $\varphi(u) = \varphi(0) + u\varphi'(0) + \tfrac{u^2}{2}\varphi''(\xi) \le u^2/8 = \lambda^2(b - a)^2/8$. $\blacksquare$

Theorem (Hoeffding's inequality). Let $X_1, \dots, X_n$ be independent with $a_i \le X_i \le b_i$, and $S = \sum_i (X_i - \mathbb{E}X_i)$. Then for every $t > 0$,

Proof.

1. Chernoff: $P(S \ge t) \le e^{-\lambda t}\,\mathbb{E}[e^{\lambda S}]$ for every $\lambda > 0$.
2. Independence: $\mathbb{E}[e^{\lambda S}] = \prod_i \mathbb{E}[e^{\lambda(X_i - \mathbb{E}X_i)}]$.
3. Hoeffding's lemma on each factor: $\mathbb{E}[e^{\lambda S}] \le \exp(\lambda^2 D/8)$, with $D = \sum_i (b_i - a_i)^2$.
4. So $P(S \ge t) \le \exp(-\lambda t + \lambda^2 D/8)$ for every $\lambda > 0$.
5. The exponent is a parabola in $\lambda$, smallest at $\lambda^* = 4t/D$, where it equals $-2t^2/D$. $\blacksquare$

For the mean of $n$ i.i.d. variables in $[a, b]$, put $t = n\varepsilon$ and $D = n(b - a)^2$, and add the same bound for the lower tail (apply the theorem to $-X_i$):

Hoeffding uses only the range $b - a$, not the variance. That makes it simple and universal, but loose for rare events. For $p = 0.01$, $n = 1000$ and $\varepsilon = 0.01$, the one-sided Hoeffding bound is 0.82, the Chernoff (KL) bound 0.020 and the exact tail 0.0033.

Bernstein's inequality: using the variance

If $|X_i - \mu| \le b$ and $\operatorname{Var}(X_i) = \sigma^2$, then

$$P(\bar X_n - \mu \ge \varepsilon) \le \exp\Big(-\frac{n\varepsilon^2}{2(\sigma^2 + b\varepsilon/3)}\Big).$$

For small $\varepsilon$ the exponent is about $n\varepsilon^2/(2\sigma^2)$: the Gaussian rate with the true variance. In the rare-event example ($\sigma^2 = 0.0099$, $b = 0.99$) Bernstein gives 0.023, close to Chernoff and far below Hoeffding's 0.82. Empirical Bernstein bounds use the sample variance instead of $\sigma^2$.

Sub-Gaussian variables #

Boundedness was used at only one place: step 3, to bound each factor by a Gaussian MGF. So the proof works for every variable with such a bound.

Definition. A random variable $X$ with mean $\mu$ is sub-Gaussian with variance proxy $\sigma^2$ if

• $\mathcal N(\mu, \sigma^2)$ is sub-Gaussian with proxy $\sigma^2$ (with equality).
• A variable in $[a, b]$ is sub-Gaussian with proxy $(b - a)^2/4$ (Hoeffding's lemma).
• A Rademacher variable (a random sign $\pm 1$) has proxy 1, because $\mathbb{E}e^{\lambda X} = \cosh\lambda \le e^{\lambda^2/2}$ (compare the Taylor series term by term: $\frac{\lambda^{2k}}{(2k)!} \le \frac{\lambda^{2k}}{2^k k!}$).
• Exponential, Poisson and gamma variables are not sub-Gaussian. For Exp(1), $\mathbb{E}e^{\lambda X} = 1/(1 - \lambda)$ is infinite for $\lambda \ge 1$. These are sub-exponential. Heavy-tailed variables (Student's $t$, Pareto) are neither.

The Chernoff method turns the definition into the tail bound $P(|X - \mu| \ge t) \le 2e^{-t^2/(2\sigma^2)}$. Variance proxies of independent variables add (multiply the MGF bounds), so the mean of $n$ i.i.d. copies has proxy $\sigma^2/n$, and

With $\sigma^2 = (b - a)^2/4$ this is exactly Hoeffding again.

Equivalent definitions

Vershynin defines sub-Gaussian variables by the norm $\|X\|_{\psi_2} = \inf\{c > 0 : \mathbb{E}\,e^{X^2/c^2} \le 2\}$. The tail definition ($P(|X| \ge t) \le 2e^{-t^2/K_1^2}$), the moment definition ($\|X\|_{L^p} \le K_2\sqrt p$), and the MGF definition above are equivalent up to absolute constants (his Proposition 2.6.1). In the same way, sub-exponential variables have tails $e^{-t/K}$, and the square of a sub-Gaussian variable is sub-exponential.

From a bound to a sample size #

Set the bound equal to $\delta$ and solve for $n$. For values in $[0, 1]$:

• Hoeffding: $2e^{-2n\varepsilon^2} \le \delta \iff n \ge \dfrac{\ln(2/\delta)}{2\varepsilon^2}$.
• Chebyshev with the worst-case variance $1/4$: $\dfrac{1}{4n\varepsilon^2} \le \delta \iff n \ge \dfrac{1}{4\delta\varepsilon^2}$.
• CLT (an approximation, not a guarantee): $n \approx \Big(\dfrac{z_{1-\delta/2} \cdot 0.5}{\varepsilon}\Big)^2$.

$\varepsilon$	$\delta$	Hoeffding	Chebyshev	CLT
0.05	0.05	738	2,000	385
0.05	0.01	1,060	10,000	664
0.05	0.001	1,521	100,000	1,083
0.01	0.05	18,445	50,000	9,604

All methods grow like $1/\varepsilon^2$: half the error costs four times the data. But in $\delta$, Hoeffding grows like $\ln(1/\delta)$ and Chebyshev like $1/\delta$. With an exponential tail, high confidence is cheap.

Interactive figure: loading…

The union bound and a generalisation bound #

Union bound. For any events $A_1, \dots, A_k$ (independent or not),

(Proof by induction on $k$. For two events, $P(A \cup B) = P(A) + P(B) - P(A \cap B)$, and the last term is $\ge 0$.)

To make $k$ statements hold at the same time with probability $1 - \delta$, give each one the failure probability $\delta/k$. With Hoeffding, this replaces $\ln(2/\delta)$ by $\ln(2k/\delta)$. The cost of $k$ statements is only an additive $\ln k$ in the numerator, because the tail is exponential.

Setting. A model (hypothesis) $h$ has a loss $\ell(h, z) \in [0, 1]$ on an example $z$ (for example, the 0/1 error). Its true risk is $R(h) = \mathbb{E}[\ell(h, Z)]$ and its empirical risk on $n$ i.i.d. examples is $\hat R(h) = \frac1n\sum_i \ell(h, z_i)$.

Theorem (finite-class generalisation bound). Let $\mathcal H$ be a finite set of $k$ models, fixed before the data are seen. With probability at least $1 - \delta$, for all $h \in \mathcal H$ at once,

Proof.

1. For one fixed $h$, $\hat R(h)$ is the mean of $n$ i.i.d. values in $[0, 1]$ with mean $R(h)$. Hoeffding: $P(|\hat R(h) - R(h)| \ge \varepsilon) \le 2e^{-2n\varepsilon^2}$.
2. Union bound over the $k$ models: $P(\exists h: |\hat R(h) - R(h)| \ge \varepsilon) \le 2k\,e^{-2n\varepsilon^2}$.
3. Set this equal to $\delta$ and solve: $\varepsilon = \sqrt{\ln(2k/\delta)/(2n)}$. $\blacksquare$

Consequence for model selection. If $\hat h$ minimises $\hat R$ over $\mathcal H$ (empirical risk minimisation, or "pick the best on the test set"), then with probability at least $1 - \delta$, $R(\hat h) \le \min_{h} R(h) + 2\sqrt{\ln(2k/\delta)/(2n)}$. Step 1 needed a model that is fixed before the data: the selected $\hat h$ depends on the data, so it is covered only through the union bound over all $k$ models.

Interactive figure: loading…

Concentration in high dimension

Let $X \sim \mathcal N(0, I_d)$. Then $\|X\|^2 = \sum_{j=1}^d X_j^2$ is a sum of $d$ independent terms with mean 1, so $\|X\|^2 \approx d$ and $\|X\| \approx \sqrt d$. Concentration says more: $\big|\|X\| - \sqrt d\big|$ is sub-Gaussian with a variance proxy that does not depend on $d$ (Vershynin, Theorem 3.1.1). A simulation gives the mean norms 3.08, 9.96 and 31.6 for $d = 10, 100, 1000$, with SD about 0.71 in each case. In high dimension a Gaussian is concentrated on a thin shell of radius $\sqrt d$, not near its mode at 0. Random projections and the Johnson–Lindenstrauss lemma use exactly this (linear algebra 18).

Answers to section 1. (1) Much less. Hoeffding needs $n \ge \ln(2/\delta)/(2\varepsilon^2)$, so $n$ grows by the factor $\ln 2000/\ln 200 = 1.43$: 43% more data (1,060 → 1,521 for $\varepsilon = 0.05$). With Chebyshev, $n \propto 1/\delta$ would grow ten times. (2) No. For Exp(1) at $a = 2$, Markov gives 0.5 and Chebyshev gives 1. Chebyshev wins only for large deviations. (3) About 0.55. A simulation gives a mean best accuracy of 0.551. The union bound says that, with probability 0.95, no classifier exceeds $0.5 + \sqrt{\ln(2000/0.05)/2000} = 0.573$.

4. Worked example #

(a) A guaranteed sample size. A web page has an unknown click rate $p$. How many visitors $n$ guarantee $P(|\hat p - p| \ge 0.05) \le 0.05$, for every $p$?

1. Clicks are 0/1 values, so $a = 0$, $b = 1$ and $(b - a)^2 = 1$.
2. Hoeffding: $2e^{-2n(0.05)^2} \le 0.05$ is the same as $e^{-0.005n} \le 0.025$, that is $n \ge \ln(40)/0.005$.
3. $\ln 40 = 3.689$, so $n \ge 737.8$: 738 visitors.
4. Compare: the CLT suggests 385 (an approximation, from lesson 06) and Chebyshev guarantees it with 2,000. Ratio CLT : Hoeffding : Chebyshev ≈ 1 : 2 : 5.

(b) The range matters. Rewards in a game lie in $[0, 10]$. With $n = 200$ episodes, bound $P(|\bar X - \mu| \ge 1)$.

1. $(b - a)^2 = 100$ and $\varepsilon = 1$.
2. Hoeffding: $2\exp(-2 \cdot 200 \cdot 1/100) = 2e^{-4} = 0.037$.
3. Forgetting the range (using $2e^{-2n\varepsilon^2} = 2e^{-400}$) would claim an absurdly small probability.

(c) A test set and a leaderboard. A test set has $n = 10{,}000$ examples, and $\delta = 0.05$.

1. One model, fixed in advance: with probability 0.95, its test accuracy is within $\sqrt{\ln(40)/20{,}000} = 0.0136$ of its true accuracy.
2. The best of $k = 100$ models on the same test set: replace $\ln 40$ by $\ln(4000)$. The width becomes $\sqrt{\ln(4000)/20{,}000} = 0.0204$.
3. 100 times more models increase the width only by the factor 1.5, but the width never goes away: a reported "best of 100" score can be optimistic by up to 0.02.

5. In code #

SciPy checks the numbers of sections 2–4. The notebook builds the bounds yourself.

import numpy as np
from scipy import stats

# coin: P(at least 60 heads in 100 flips) and five bounds
p, n, eps = 0.5, 100, 0.1
q = p + eps
kl = q * np.log(q / p) + (1 - q) * np.log((1 - q) / (1 - p))
v = p * (1 - p) / n
print(round(stats.binom.sf(59, n, p), 4), round(stats.norm.sf(2), 4))       # 0.0284 0.0228
print(round(p / q, 3), round(v / eps**2, 3), round(v / (v + eps**2), 3),
      round(np.exp(-2 * n * eps**2), 3), round(np.exp(-n * kl), 3))       # 0.833 0.25 0.2 0.135 0.134

# Hoeffding sample sizes and the union bound
hoeff_n = lambda eps, delta: int(np.ceil(np.log(2 / delta) / (2 * eps**2)))
print(hoeff_n(0.05, 0.05), hoeff_n(0.05, 0.01), hoeff_n(0.05, 0.001))    # 738 1060 1521
gap = lambda k, n, delta: np.sqrt(np.log(2 * k / delta) / (2 * n))
print(round(gap(1, 10_000, 0.05), 4), round(gap(100, 10_000, 0.05), 4))  # 0.0136 0.0204

# best of 1000 random classifiers on 1000 test examples
rng = np.random.default_rng(0)
best = rng.binomial(1000, 0.5, size=(2000, 1000)).max(axis=1) / 1000
print(round(best.mean(), 3), np.mean(best - 0.5 > gap(1000, 1000, 0.05)))  # about 0.551 and 0.0025

The last line is a simulation: the mean best accuracy has a Monte Carlo error of about 0.0003, and the fraction of runs above the bound is far below $\delta = 0.05$.

6. Where it shows up #

• Test-set size. To estimate an accuracy within $\pm 0.01$ with probability 0.95 for every model, Hoeffding asks for 18,445 test examples (the CLT suggests 9,604).
• PAC learning. The finite-class bound is the simplest probably approximately correct (PAC) statement. VC dimension and Rademacher complexity replace $\ln k$ for infinite classes (deep learning 17).
• Adaptive data analysis. Every decision based on a test set (early stopping, hyperparameter search, choosing the architecture) adds to $k$. Kaggle-style leaderboards and "test-set overfitting" are union-bound effects.
• Multi-armed bandits. UCB and successive elimination use Hoeffding intervals for each arm (reinforcement learning 03).
• Monte Carlo with a guarantee. For an integrand with values in $[a, b]$, Hoeffding gives a sample size that holds without any CLT assumption; for rare events, Chernoff or Bernstein give much smaller ones.
• High-dimensional data. Norms and distances of random vectors concentrate; random projections preserve distances (Johnson–Lindenstrauss); random matrix bounds follow the same Chernoff pattern (linear algebra 18).

7. Common mistakes #

• Treating the CLT as a bound. The CLT gave 0.0228 for the coin, below the exact 0.0284. When you need a guarantee, use a concentration inequality.
• Hoeffding with the wrong range. The exponent has $(b - a)^2$. For values in $[-1, 1]$ it is $2n\varepsilon^2/4$, not $2n\varepsilon^2$. Hoeffding does not apply to unbounded variables at all.
• Forgetting the factor 2 of the two-sided bound, or the union bound when you report many metrics or select among many models.
• Applying the bound to a model chosen on the same data. The single-model Hoeffding bound needs a model fixed before the data; after selection, use the union bound (or a fresh test set).
• "Chebyshev is always sharper than Markov." False: Exp(1) at $a = 2$ gives 0.5 for Markov and 1 for Chebyshev.
• Calling the exponential distribution sub-Gaussian. Its MGF is infinite for $\lambda \ge 1$; it is sub-exponential.
• Using Hoeffding for rare events. It ignores the variance. For $p = 0.01$ use the Chernoff (KL) or Bernstein bound.

8. Check yourself #

1. Values in $[0, 1]$, $\varepsilon = 0.01$, $\delta = 0.001$. What $n$ does Hoeffding require?
   Answer

   $n \ge \ln(2000)/(2 \cdot 10^{-4}) = 7.601/0.0002 = 38{,}004.5$, so $n = 38{,}005$.
2. Where does the proof of Hoeffding's inequality use independence, and where boundedness?
   Answer

   Independence: to write $\mathbb{E}[e^{\lambda S}]$ as a product (step 2). Boundedness: in Hoeffding's lemma, to bound each factor by $e^{\lambda^2(b_i - a_i)^2/8}$ (step 3). Any sub-Gaussian bound on the factors would do.
3. Derive the Chernoff bound for $\mathcal N(0, \sigma^2)$ at threshold $t > 0$.
   Answer

   $\mathbb{E}e^{\lambda X} = e^{\sigma^2\lambda^2/2}$, so $P(X \ge t) \le \exp(-\lambda t + \sigma^2\lambda^2/2)$. The exponent is smallest at $\lambda = t/\sigma^2$, giving $e^{-t^2/(2\sigma^2)}$.
4. 100 rolls of a fair die. Use Hoeffding to bound $P(|\bar X - 3.5| \ge 0.5)$, and compare with Chebyshev.
   Answer

   Range $[1, 6]$, so $(b - a)^2 = 25$: $2\exp(-2 \cdot 100 \cdot 0.25/25) = 2e^{-2} = 0.27$. Chebyshev with $\sigma^2 = 35/12$: $0.0292/0.25 = 0.117$. Here Chebyshev wins: the variance $2.92$ is much smaller than the worst case $25/4$ that Hoeffding assumes, and $n$ is not large.
5. Show that a random sign $X = \pm 1$ (probability $1/2$ each) is sub-Gaussian with proxy 1.
   Answer

   $\mathbb{E}e^{\lambda X} = \cosh\lambda = \sum_k \frac{\lambda^{2k}}{(2k)!} \le \sum_k \frac{\lambda^{2k}}{2^k k!} = e^{\lambda^2/2}$, because $(2k)! \ge 2^k k!$.
6. A finite class has $k = 10^6$ models. With $n = 10{,}000$ examples and $\delta = 0.05$, what is the uniform gap?
   Answer

   $\sqrt{\ln(2 \cdot 10^6/0.05)/20{,}000} = \sqrt{17.5/20{,}000} = 0.0296$. A million models cost only about twice the width of one model (0.0136).

Recall cardsAnswer in your head first, then reveal. Add the cards to your review deck to see them again just before you would forget.

1. State the Chernoff bound.

   Show answer

2. State Hoeffding's inequality for the mean of i.i.d. variables in $[a, b]$.

   Show answer

3. State Hoeffding's lemma.

   Show answer

4. Define a sub-Gaussian variable with variance proxy $\sigma^2$.

   Show answer

5. Is the exponential distribution sub-Gaussian? Why?

   Show answer

6. What sample size does Hoeffding give for error $< \varepsilon$ with probability $\ge 1 - \delta$ (values in $[0, 1]$)?

   Show answer

7. Why is high confidence cheap with Hoeffding but expensive with Chebyshev?

   Show answer

8. State the union bound.

   Show answer

9. State the finite-class generalisation bound.

   Show answer

Add these cards to my reviewOpen the review →

9. Interview angle #

• "How many samples do you need to estimate a probability within ±1% at 95% confidence?" — CLT, worst case $p = 1/2$: $(1.96 \cdot 0.5/0.01)^2 = 9604$. A guarantee from Hoeffding: $\ln(40)/(2 \cdot 10^{-4}) \approx 18{,}445$.
• "Derive Hoeffding's inequality." — Chernoff (Markov on $e^{\lambda S}$), factorise by independence, bound each factor by Hoeffding's lemma, optimise the parabola in $\lambda$.
• "Give a generalisation bound for a finite hypothesis class." — Hoeffding plus the union bound: $|R(h) - \hat R(h)| \le \sqrt{\ln(2|\mathcal H|/\delta)/(2n)}$ for all $h$, with probability $\ge 1 - \delta$.
• "Why is the best leaderboard score optimistic?" — It is the maximum of $k$ noisy estimates on one test set. The maximum is biased upwards by up to about $\sqrt{\ln k / n}$.
• "When is Hoeffding a poor choice?" — Rare events or small variance (use Chernoff/KL or Bernstein), and unbounded or heavy-tailed data (Hoeffding does not apply).

10. Practice #

The notebook for this lesson has four exercises, each with a check cell and a folded solution:

1. bernoulli_tail_bounds: Markov, Chebyshev, Cantelli, Hoeffding and Chernoff for a coin mean, checked against the exact binomial tail on a grid (every bound must stay above it).
2. A numerical Chernoff bound for any CGF, checked against the Gaussian and Bernoulli closed forms.
3. hoeffding_sample_size, with the tests $(0.05, 0.01) \to 1060$ and a range of width 2.
4. The best of $k$ random classifiers on one test set, compared with the union bound.

11. Watch and read #

Markov, Chebyshev, and ChernoffMIT OpenCourseWare · 17 min

The three inequalities in a row, with the Chernoff idea of applying Markov to an exponential.

S18.3 Hoeffding's InequalityMIT OpenCourseWare · 18 min

Hoeffding's inequality with the proof through the moment generating function, as in section 3.

Lecture 28: Inequalities | Statistics 110Harvard University · Joe Blitzstein, Statistics 110 · 47 min

Cauchy–Schwarz, Jensen, Markov and Chebyshev, with many examples of when each one is useful.

• Roman Vershynin, High-Dimensional Probability, 2nd edition (free PDF on the author's page): §2.1–2.3 (why concentration, Hoeffding, Chernoff), §2.6 (sub-Gaussian distributions), §3.1 (the norm of a Gaussian vector).
• Mehryar Mohri, Afshin Rostamizadeh and Ameet Talwalkar, Foundations of Machine Learning, 2nd edition (free PDF from the authors): ch. 2 (PAC learning, the bound for a finite hypothesis set) and appendix D (concentration inequalities).
• Joseph Blitzstein and Jessica Hwang, Introduction to Probability, 2nd edition (free PDF): §10.1 (inequalities).