The threshold rule "diagnosed diabetes if HbA1c is at least 6.7%" misclassifies 437 of the 5,210 adults of the National Health and Nutrition Examination Survey (NHANES) of 2017 to 2018 used in Empirical Risk Minimization, an error rate of 0.0839. Suppose the rate were unknown and had to be estimated on a held-out test set of 500 adults drawn at random. The normal approximation says the test error will usually be within 0.0243 of the truth, and the exact binomial distribution confirms that 95% of test sets land within 0.0241. Neither statement is available without knowing the error rate in advance. What can be guaranteed about a test error at a given size, knowing only that each loss lies between 0 and 1, and what does the guarantee cost?
A concentration inequality bounds the probability that a function of many independent random variables, most often their average, differs from its expected value by more than a given amount, at every sample size and without a limit. For the test set of 500, Hoeffding's inequality guarantees a deviation of at most 0.0607 with probability at least 95%, whatever the distribution of the losses; Bernstein's inequality, which also uses the variance, would guarantee 0.0360 if the variance of the loss were known. This article proves both, and the bounds behind them, and measures their price on the running example.
First we say why the limit theorems do not give guarantees and recall the Chernoff method. Then we prove Hoeffding's lemma and inequality, sharpen the exponent with the Kullback–Leibler divergence, and prove Bennett's and Bernstein's inequalities, which use the variance. Next we compare all of them with the normal approximation and the exact binomial on the NHANES test sets, as widths and as test-set sizes, and look at sampling without replacement. Finally we prove McDiarmid's inequality, which extends Hoeffding's from averages to any function that no single variable can move much; Rademacher Complexity uses it. The article assumes Probability Inequalities (Markov's inequality and the Chernoff bound) and Moment Generating and Characteristic Functions.
Why a limit theorem is not a guarantee
Write the test set's losses as $X_1, \ldots, X_n$: independent and identically distributed (i.i.d.), each 1 for a mistake and 0 otherwise, with mean $p = 437/5{,}210 = 0.0839$. The unit uses $m$ for a training sample and $n$ for a test set, so the letter $n$ here; the results hold for any independent variables, and a training sample's losses are the case $n = m$. Write $S_n = X_1 + \cdots + X_n$ and $\bar X_n = S_n/n$.
The Laws of Large Numbers prove that $\bar X_n$ approaches $p$, and The Central Limit Theorem that $\sqrt{n}(\bar X_n - p)$ is approximately normal. Both are statements about $n \to \infty$. The normal approximation gives the half-width $1.96\sqrt{p(1 - p)/n} = 0.0243$ at $n = 500$, which is an approximation with no bound on its error at $n = 500$, and needs $p$. Confidence Intervals for a Proportion computes how far such intervals can miss their nominal coverage, exactly.
Chebyshev's inequality gives a guarantee: $P(\lvert\bar X_n - p\rvert \ge \varepsilon) \le \sigma^2/(n\varepsilon^2)$, with $\sigma^2 = p(1 - p)$ the variance of one loss. Setting the right side to $\delta = 0.05$ gives a half-width $\sqrt{\sigma^2/(n\delta)}$. With the true variance 0.0768 that is 0.0554 at $n = 500$; knowing nothing but that a loss lies in $[0, 1]$, whose variance is at most $1/4$ (shown below), it is 0.1000. Chebyshev's bound falls like $1/n$ and its width grows like $1/\sqrt{\delta}$, which makes high confidence expensive. The bounds of this article fall exponentially in $n$, and their widths grow like $\sqrt{\ln(1/\delta)}$.
They all start from the Chernoff bound, proved in Probability Inequalities: for any $t > 0$ at which the moment generating function is finite,
$$P(X \ge a) \le e^{-ta}\,E[e^{tX}].$$
For a sum of independent variables, $E[e^{tS_n}] = \prod_i E[e^{tX_i}]$ (Moment Generating and Characteristic Functions). The work is to bound each factor using only what is known about $X_i$, and then to choose $t$.
Hoeffding's lemma
Here is the idea: among all variables with a given range and mean zero, the moment generating function is largest for one that sits at the two ends of the range, and for that two-point variable the logarithm of the moment generating function has second derivative at most a quarter of the squared range.
Theorem 1 (Hoeffding's lemma). Let $X$ take values in $[a, b]$ with $E[X] = 0$. Then for every real $t$,
$$E[e^{tX}] \le \exp\!\Big(\frac{t^2(b - a)^2}{8}\Big).$$
Proof. Since $E[X] = 0$ and $a \le X \le b$, we have $a \le 0 \le b$. If $a = b$, then $X = 0$ and both sides equal 1, so let $a < b$. The function $x \mapsto e^{tx}$ is convex, so on $[a, b]$ it lies below the chord joining its values at the ends: writing $x$ as the weighted average $\frac{b - x}{b - a}a + \frac{x - a}{b - a}b$,
$$e^{tx} \le \frac{b - x}{b - a}e^{ta} + \frac{x - a}{b - a}e^{tb} \qquad (a \le x \le b).$$
Replace $x$ by $X$ and take expectations; since $E[X] = 0$,
$$E[e^{tX}] \le \frac{b}{b - a}e^{ta} - \frac{a}{b - a}e^{tb}.$$
Let $\theta = -a/(b - a)$, which lies in $[0, 1]$, and $u = t(b - a)$. Then $ta = -\theta u$, $\frac{b}{b - a} = 1 - \theta$, and the right side is $e^{-\theta u}(1 - \theta + \theta e^{u}) = e^{L(u)}$ with
$$L(u) = -\theta u + \ln(1 - \theta + \theta e^{u}).$$
The argument of the logarithm is positive, so $L$ is defined for every real $u$. Its derivatives are
$$L'(u) = -\theta + \frac{\theta e^{u}}{1 - \theta + \theta e^{u}}, \qquad L''(u) = \frac{\theta e^{u}(1 - \theta)}{(1 - \theta + \theta e^{u})^2} = q(1 - q), \quad q = \frac{\theta e^{u}}{1 - \theta + \theta e^{u}}.$$
Since $0 \le q \le 1$, $L''(u) \le 1/4$. Also $L(0) = 0$ and $L'(0) = 0$. By Taylor's theorem with the Lagrange remainder, $L(u) = L(0) + uL'(0) + \frac{u^2}{2}L''(\xi)$ for some $\xi$ between 0 and $u$, so $L(u) \le u^2/8 = t^2(b - a)^2/8$. $\square$
The proof follows Shalev-Shwartz and Ben-David (2014, Lemma B.7) and Mohri, Rostamizadeh and Talwalkar (2018, Lemma D.1); the second derivative is the variance of a two-point variable, which is where the quarter comes from. The bound $t^2(b - a)^2/8$ is the logarithm of the moment generating function of a normal variable with variance $(b - a)^2/4$, the largest variance a variable confined to $[a, b]$ can have: $\operatorname{Var}(X) = E[(X - E X)^2] \le E[(X - \frac{a + b}{2})^2] \le (\frac{b - a}{2})^2$, since the mean minimizes the expected squared distance and $\lvert X - \frac{a + b}{2}\rvert \le \frac{b - a}{2}$. In this sense a bounded variable is never more spread out, in its moment generating function, than the normal with the worst variance.
Example (the threshold rule's loss). For the centered loss $X - p$ of the 6.7% rule the range has length 1, and at $t = 4$ the logarithm of the moment generating function is $\ln\big((1 - p)e^{-4p} + p\,e^{4(1 - p)}\big) = 1.3685$, against Hoeffding's $t^2/8 = 2$. The lemma's bound is loose here because $p$ is far from one half and the loss's variance, 0.0768, is far below the worst case $1/4$. Bernstein's inequality below uses the variance to recover what is lost.
Hoeffding's inequality
Theorem 2 (Hoeffding's inequality). Let $X_1, \ldots, X_n$ be independent with $a_i \le X_i \le b_i$, and $\bar X_n = \frac1n\sum_i X_i$. For every $\varepsilon > 0$,
$$P\big(\bar X_n - E[\bar X_n] \ge \varepsilon\big) \le \exp\!\Big(-\frac{2n^2\varepsilon^2}{\sum_{i=1}^n (b_i - a_i)^2}\Big),$$
the same bound holds for $P(\bar X_n - E[\bar X_n] \le -\varepsilon)$, and the two-sided probability $P(\lvert\bar X_n - E[\bar X_n]\rvert \ge \varepsilon)$ is at most twice the bound. When every $X_i$ lies in $[0, 1]$ the bound is $\exp(-2n\varepsilon^2)$.
Proof. Let $Y_i = X_i - E[X_i]$, which has mean 0 and lies in $[a_i - E X_i, b_i - E X_i]$, an interval of length $b_i - a_i$. The event $\bar X_n - E[\bar X_n] \ge \varepsilon$ is the event $\sum_i Y_i \ge n\varepsilon$. For $t > 0$, the Chernoff bound, the product rule for independent variables and Theorem 1 give
$$P\Big(\sum_i Y_i \ge n\varepsilon\Big) \le e^{-tn\varepsilon}\prod_{i=1}^n E[e^{tY_i}] \le \exp\!\Big(-tn\varepsilon + \frac{t^2}{8}\sum_i (b_i - a_i)^2\Big).$$
The exponent is a quadratic in $t$, smallest at $t = 4n\varepsilon/\sum_i (b_i - a_i)^2$, where it equals $-2n^2\varepsilon^2/\sum_i (b_i - a_i)^2$. For the lower tail apply the same argument to the variables $-X_i$, which lie in $[-b_i, -a_i]$, intervals of the same lengths. The two-sided probability is the probability of the union of the two events, at most the sum of their probabilities. $\square$
The theorem is Theorem 2 of Hoeffding (1963), stated there for the mean; the case of variables in $[0, 1]$ is his inequality (2.3), the last of three bounds in his Theorem 1. The bound depends on the variables only through their ranges. It needs neither identical distributions nor knowledge of the means, which is why it can be applied before the data are seen.
Inverting the bound. Set $2\exp(-2n\varepsilon^2) = \delta$ for losses in $[0, 1]$. Then with probability at least $1 - \delta$,
$$\lvert\bar X_n - E[\bar X_n]\rvert < \sqrt{\frac{\ln(2/\delta)}{2n}}, \qquad\text{and a test set of } n \ge \frac{\ln(2/\delta)}{2\varepsilon^2} \text{ achieves } \pm\varepsilon.$$
At $\delta = 0.05$, $\ln(2/\delta) = \ln 40$, and $n = 500$ gives the half-width 0.0607 of the opening. A precision of $\pm 0.02$ needs 4,612 test examples, and $\pm 0.01$ needs 18,445: halving the width quadruples the size, and raising the confidence from 95% to 99.9% multiplies it by $\ln 2{,}000/\ln 40 = 2.06$.
For a classifier. Applied to the training losses of one rule $h$ fixed before the sample, the one-sided bound says that with probability at least $1 - \delta$,
$$L_{\mathcal{D}}(h) \le L_S(h) + \sqrt{\frac{\ln(1/\delta)}{2m}}.$$
This is the guarantee for a rule fixed in advance that Empirical Risk Minimization (Theorem 1) asked for. It does not hold for the rule chosen by minimizing $L_S$, whose losses are not a fixed rule's. Applying it to every rule of a finite class at once and adding the failure probabilities is the union bound argument of PAC Learning and Finite Hypothesis Classes.
The exact exponent for bounded variables
For losses in $[0, 1]$, Hoeffding's own first bound is sharper than $\exp(-2n\varepsilon^2)$. It is the best that the Chernoff method can give from the range and the mean, and it involves the binary Kullback–Leibler divergence
$$\mathrm{kl}(a \,\Vert\, b) = a\ln\frac{a}{b} + (1 - a)\ln\frac{1 - a}{1 - b},$$
the divergence between Bernoulli distributions with success probabilities $a$ and $b$ (Cross-Entropy and Kullback–Leibler Divergence proves it is nonnegative).
Theorem 3 (the Kullback–Leibler bound). Let $X_1, \ldots, X_n$ be independent with values in $[0, 1]$, and $\mu = E[\bar X_n]$. For $0 < \varepsilon < 1 - \mu$,
$$P(\bar X_n - \mu \ge \varepsilon) \le \exp\big(-n\,\mathrm{kl}(\mu + \varepsilon \,\Vert\, \mu)\big),$$
and $\mathrm{kl}(\mu + \varepsilon \,\Vert\, \mu) \ge 2\varepsilon^2$, so the bound is never weaker than Theorem 2's.
Proof. If $\mu = 0$, every $X_i$ is 0 with probability 1, the probability is 0, and the bound (which is then $e^{-\infty} = 0$) holds; so let $\mu > 0$. Let $\mu_i = E[X_i]$, so $\mu = \frac1n\sum_i\mu_i$. For $t > 0$ and $x \in [0, 1]$, convexity gives $e^{tx} \le (1 - x) + x e^{t}$ (the chord from 0 to 1), so $E[e^{tX_i}] \le 1 - \mu_i + \mu_i e^{t}$. The logarithm is concave, so by the finite form of Jensen's inequality (Probability Inequalities), $\frac1n\sum_i \ln(1 - \mu_i + \mu_i e^t) \le \ln(1 - \mu + \mu e^t)$, and hence $\prod_i E[e^{tX_i}] \le (1 - \mu + \mu e^t)^n$. The Chernoff bound with $a = \mu + \varepsilon$ gives
$$P(\bar X_n \ge a) \le \big(e^{-ta}(1 - \mu + \mu e^{t})\big)^n.$$
Choose $e^t = \frac{a(1 - \mu)}{\mu(1 - a)}$, which exceeds 1 because $a > \mu$, so $t > 0$. Then $1 - \mu + \mu e^t = 1 - \mu + \frac{a(1 - \mu)}{1 - a} = \frac{1 - \mu}{1 - a}$, and
$$e^{-ta}(1 - \mu + \mu e^t) = \Big(\frac{\mu(1 - a)}{a(1 - \mu)}\Big)^{a}\frac{1 - \mu}{1 - a} = \Big(\frac{\mu}{a}\Big)^{a}\Big(\frac{1 - \mu}{1 - a}\Big)^{1 - a} = e^{-\mathrm{kl}(a \Vert \mu)}.$$
For the comparison, let $g(\varepsilon) = \mathrm{kl}(\mu + \varepsilon \,\Vert\, \mu) - 2\varepsilon^2$ on $0 \le \varepsilon < 1 - \mu$. Differentiating in $\varepsilon$, $g'(\varepsilon) = \ln\frac{(\mu + \varepsilon)(1 - \mu)}{\mu(1 - \mu - \varepsilon)} - 4\varepsilon$ and $g''(\varepsilon) = \frac{1}{\mu + \varepsilon} + \frac{1}{1 - \mu - \varepsilon} - 4 = \frac{1}{a(1 - a)} - 4 \ge 0$, since $a(1 - a) \le 1/4$. With $g(0) = g'(0) = 0$, $g$ is nonnegative. $\square$
This is inequality (2.1) of Hoeffding (1963), whose Theorem 1 states it with the further bounds (2.2) and (2.3). He also notes that (2.1) is the best bound the method can give under the theorem's assumptions: it is the Chernoff bound minimized over $t$ when each $X_i$ takes only the values 0 and 1, the binomial case. For the threshold rule the gain is large: at $n = 500$ the bound's 95% half-width is 0.0337 against Hoeffding's 0.0607. The lower tail has the same form with $\mathrm{kl}(\mu - \varepsilon \,\Vert\, \mu)$, by the same theorem applied to $1 - X_i$.
Using the variance: Bennett and Bernstein
Theorem 3 still uses only the mean and the range. Bennett's inequality uses the variance instead, and needs only an upper bound on each variable.
The proof rests on one function. For real $u$, let
$$\varphi(u) = \frac{e^{u} - 1 - u}{u^2} \quad (u \ne 0), \qquad \varphi(0) = \tfrac12.$$
Lemma 1. $\varphi$ is increasing on the whole real line, and $\varphi(u) = \int_0^1 (1 - s)e^{su}\,ds$.
Proof. Taylor's theorem with the integral remainder gives $e^{u} = 1 + u + u^2\int_0^1 (1 - s)e^{su}\,ds$, which is the integral formula for $u \ne 0$; at $u = 0$ the integral is $\int_0^1 (1 - s)\,ds = \frac12$. Differentiating under the integral, which is allowed for this smooth integrand on a bounded interval, gives $\varphi'(u) = \int_0^1 s(1 - s)e^{su}\,ds > 0$. $\square$
Theorem 4 (Bennett's inequality). Let $X_1, \ldots, X_n$ be independent with finite variances, $X_i - E[X_i] \le c$ for a constant $c > 0$, and $V = \sum_i \operatorname{Var}(X_i) > 0$. For every $\varepsilon > 0$,
$$P\big(S_n - E[S_n] \ge \varepsilon\big) \le \exp\!\Big(-\frac{V}{c^2}\,h\Big(\frac{c\varepsilon}{V}\Big)\Big), \qquad h(u) = (1 + u)\ln(1 + u) - u.$$
Proof. Let $Y_i = X_i - E[X_i]$, so $Y_i \le c$, $E[Y_i] = 0$ and $E[Y_i^2] = \operatorname{Var}(X_i)$. For $t > 0$, write $e^{tY_i} = 1 + tY_i + t^2Y_i^2\varphi(tY_i)$. Since $tY_i \le tc$ and $\varphi$ is increasing (Lemma 1), $e^{tY_i} \le 1 + tY_i + t^2Y_i^2\varphi(tc)$. Taking expectations, and using $1 + x \le e^{x}$,
$$E[e^{tY_i}] \le 1 + t^2\operatorname{Var}(X_i)\varphi(tc) \le \exp\!\big(t^2\operatorname{Var}(X_i)\varphi(tc)\big) = \exp\!\Big(\frac{\operatorname{Var}(X_i)}{c^2}(e^{tc} - 1 - tc)\Big).$$
Multiplying over $i$ and applying the Chernoff bound,
$$P\Big(\sum_i Y_i \ge \varepsilon\Big) \le \exp\!\Big(-t\varepsilon + \frac{V}{c^2}(e^{tc} - 1 - tc)\Big).$$
Let $u = c\varepsilon/V$ and choose $t = \ln(1 + u)/c > 0$. Then $e^{tc} = 1 + u$, and the exponent is
$$-\frac{\varepsilon}{c}\ln(1 + u) + \frac{V}{c^2}\big(u - \ln(1 + u)\big) = \frac{V}{c^2}\big(-u\ln(1 + u) + u - \ln(1 + u)\big) = -\frac{V}{c^2}h(u),$$
using $\varepsilon/c = Vu/c^2$. $\square$
Hoeffding (1963) gives this bound as his (2.9) and credits it to Bennett (1962), noting that Bennett's second proof uses only an upper bound on the variables, as here. The bound has two regimes. When $c\varepsilon$ is small compared with $V$, $h(u) \approx u^2/2$ and the bound is about $\exp(-\varepsilon^2/(2V))$, the normal tail for a sum with variance $V$. When $c\varepsilon$ is large, $h(u)$ grows like $u\ln u$ and the bound decays like a Poisson tail. A simpler expression loses little:
Corollary (Bernstein's inequality). Under the assumptions of Theorem 4,
$$P\big(S_n - E[S_n] \ge \varepsilon\big) \le \exp\!\Big(-\frac{\varepsilon^2}{2(V + c\varepsilon/3)}\Big).$$
If the $X_i$ have common variance $\sigma^2$ and $\lvert X_i - E[X_i]\rvert \le c$, then $P(\lvert\bar X_n - \mu\rvert \ge \varepsilon) \le 2\exp\!\big(-n\varepsilon^2/(2\sigma^2 + 2c\varepsilon/3)\big)$.
Proof. It is enough to show $h(u) \ge k(u) = \frac{u^2}{2(1 + u/3)}$ for $u \ge 0$, since then $\frac{V}{c^2}h(\frac{c\varepsilon}{V}) \ge \frac{V}{c^2}\cdot\frac{c^2\varepsilon^2/V^2}{2(1 + c\varepsilon/(3V))} = \frac{\varepsilon^2}{2(V + c\varepsilon/3)}$. Both functions vanish at 0 with zero first derivative: $h'(u) = \ln(1 + u)$, and $k(u) = \frac{3u^2}{2(3 + u)}$ has $k'(u) = \frac{3}{2}\cdot\frac{u^2 + 6u}{(3 + u)^2}$. Their second derivatives are $h''(u) = \frac{1}{1 + u}$ and $k''(u) = \frac{27}{(3 + u)^3}$, and $h'' \ge k''$ on $u \ge 0$ because $(3 + u)^3 = 27 + 27u + 9u^2 + u^3 \ge 27(1 + u)$. Integrating twice from 0 gives $h \ge k$. For the second statement apply the first to $\bar X_n$, with $V = n\sigma^2$ and $\varepsilon$ replaced by $n\varepsilon$, to each of $X_i$ and $-X_i$, and add the two tails. $\square$
The proof of Theorem 4 and the corollary follows, after its first step, the route that Mohri, Rostamizadeh and Talwalkar (2018, Exercise D.6) set as an exercise, and the corollary's form is their (D.33) and the sum form of Shalev-Shwartz and Ben-David's (2014) Lemma B.9, which they state without proof. Hoeffding (1963, inequality (2.13)) gives Bernstein's bound in this form and reports Bennett's demonstration that Bennett's bound, (2.9), is always the sharper of the two. Mohri, Rostamizadeh and Talwalkar (2018, Appendix D notes) attribute the inequality to Bernstein (1927).
When does the variance pay? For losses in $[0, 1]$ with $c = 1$, Bernstein's exponent $n\varepsilon^2/(2\sigma^2 + 2\varepsilon/3)$ exceeds Hoeffding's $2n\varepsilon^2$ exactly when $\sigma^2 < 1/4 - \varepsilon/3$. For a loss with the worst variance $1/4$ Bernstein's bound is slightly weaker; for a rare event, a small variance, it is much stronger, which matters for error rates near 0 (Problem 4). The catch is that $\sigma^2 = p(1 - p)$ involves the unknown $p$. A bound on the variance known in advance, such as $p \le 0.1$, can be used in its place (Problem 1).
Widths and sample sizes compared
The 6.7% threshold rule gives a concrete comparison. Its losses on a test set of $n$ adults drawn with replacement are i.i.d. Bernoulli with $p = 437/5{,}210 = 0.0839$, standard deviation 0.2772. For each bound, the 95% half-width is the $\varepsilon$ at which the two-sided bound equals $\delta = 0.05$. Bernstein's uses the true variance and $c = 1 - p$, the largest possible $\lvert X_i - p\rvert$. The normal approximation is $1.96\sqrt{p(1 - p)/n}$, with $p$ known. The exact half-width is the smallest distance $\varepsilon$ from $p$ that a test error can take for which the exact binomial probability $P(\lvert\bar X_n - p\rvert > \varepsilon)$ is at most 0.05.
| Test set $n$ | Hoeffding | Bernstein | Kullback–Leibler | Normal approximation | Exact binomial |
|---|---|---|---|---|---|
| 100 | 0.1358 | 0.0874 | 0.0761 | 0.0543 | 0.0539 |
| 500 | 0.0607 | 0.0360 | 0.0337 | 0.0243 | 0.0241 |
| 1,000 | 0.0429 | 0.0250 | 0.0238 | 0.0172 | 0.0171 |
| 5,000 | 0.0192 | 0.0109 | 0.0106 | 0.0077 | 0.0077 |
Hoeffding's half-width is 2.5 times the normal approximation's, and about 2.5 times the exact one, at every size. The factor splits in two. A factor of 1.80, $0.5/\sqrt{0.0768}$, comes from assuming the worst variance, $1/4$, instead of 0.0768. A factor of 1.39, $\sqrt{\ln(40)/2}/0.98$, is the price of a bound valid for every distribution at every $n$, and it remains even at $p = 1/2$. Bernstein's and the Kullback–Leibler bound use the small variance and come within a factor of 1.4 to 1.6 of exact. The normal approximation is within a few ten-thousandths of exact here, but it is an approximation, not a bound.
The same comparison read the other way gives the test-set size for a target precision at 95%. The exact size is the smallest $n$ from which on, up to Hoeffding's size, the exact probability $P(\lvert\bar X_n - p\rvert \ge \varepsilon)$ stays at most 0.05. Because the binomial is discrete, that probability is not monotone in $n$, and the first $n$ at which it dips below 0.05 is smaller (given in parentheses).
| Target | Hoeffding | Bernstein | Kullback–Leibler | Normal approximation | Exact binomial |
|---|---|---|---|---|---|
| $p = 0.0839$, $\pm 0.01$ | 18,445 | 5,895 | 5,671 | 2,952 | 2,994 (2,909) |
| $p = 0.0839$, $\pm 0.02$ | 4,612 | 1,530 | 1,419 | 738 | 771 (703) |
| $p = 0.0839$, $\pm 0.05$ | 738 | 272 | 229 | 119 | 127 (105) |
| $p = 0.5$, $\pm 0.01$ | 18,445 | 18,568 | 18,444 | 9,604 | 9,701 (9,551) |
| $p = 0.5$, $\pm 0.02$ | 4,612 | 4,673 | 4,610 | 2,401 | 2,451 (2,377) |
| $p = 0.5$, $\pm 0.05$ | 738 | 763 | 737 | 385 | 401 (371) |
Three things show in the table. Hoeffding's size does not depend on $p$, which is its strength before the data are seen and its weakness after. At $p = 1/2$ Hoeffding's and the Kullback–Leibler sizes agree to within two and Bernstein's is slightly larger, since there the variance is the worst case; and every guaranteed size is about twice the exact one, the square of the factor 1.39 above, the price of a bound valid for every distribution at every $n$: $(\ln(40)/2)/(1.96^2/4) = 1.92$ in the limit of large $n$. Bernstein's and the Kullback–Leibler bounds use $p$ there and still need, at $\pm 0.01$, 1.91 and 1.90 times the exact size. At $p = 0.0839$ the variance-aware bounds cut the size by a factor of three, and the exact size is still half of theirs.
How often do the intervals miss? An interval that adds a half-width to the test error misses $p$ when the deviation exceeds the half-width. Since the test error is binomial, the probability of a miss can be computed exactly. The table gives it for three of the fixed-width intervals of the first table (Hoeffding, Bernstein and the normal approximation with $p$ known) and for the Wald interval $\bar X_n \pm 1.96\sqrt{\bar X_n(1 - \bar X_n)/n}$, which estimates the variance from the test set and needs nothing in advance. The second figure in each cell is the median over 30 seeds of the share of misses among 10,000 simulated test sets (NumPy's default_rng([20261121, seed, n])); every interquartile range over the seeds lies within 0.0020 of its median.
| $n$ | Hoeffding | Bernstein | Normal, $p$ known | Wald, $p$ estimated |
|---|---|---|---|---|
| 100 | 0.0000 / 0.0000 | 0.0016 / 0.0015 | 0.0479 / 0.0475 | 0.0798 / 0.0798 |
| 500 | 0.0000 / 0.0000 | 0.0042 / 0.0043 | 0.0431 / 0.0435 | 0.0589 / 0.0593 |
| 1,000 | 0.0000 / 0.0000 | 0.0046 / 0.0043 | 0.0456 / 0.0461 | 0.0557 / 0.0561 |
The guaranteed intervals miss far less often than the 5% they allow: Hoeffding's misses with probability below 0.0001 at every size, Bernstein's below 0.005. The Wald interval, the only one that needs no prior knowledge apart from Hoeffding's, misses more often than 5%: 8% at 100 test cases. Confidence Intervals for a Proportion explains why and gives intervals that repair it; the concentration bounds trade a wider interval for a guarantee that no such repair is needed.
Test sets drawn without replacement
A test set is usually a set of distinct cases, drawn without replacement from a finite pool, and its losses are then not independent. Hoeffding (1963, Theorem 4) proves that for a convex continuous function $f$, $E[f(\sum_i X_i)] \le E[f(\sum_i Y_i)]$, where the $X_i$ are drawn without replacement and the $Y_i$ with replacement from the same finite population. Since the Chernoff method only uses $E[e^{t\sum X_i}]$, and $e^{tx}$ is convex, every bound of the preceding sections holds for sampling without replacement too, with $\mu$ and $\sigma^2$ the mean and variance of the population. The theorem is cited here, not proved.
Sampling without replacement is in fact more concentrated: the variance of the mean is smaller by the factor $(N - n)/(N - 1)$, as Hoeffding notes in the same section. For test sets of distinct adults from the 5,210, the simulated standard deviation of the test error was 0.9903, 0.9480 and 0.8948 times that with replacement for $n = 100$, 500 and 1,000 (medians over 30 seeds, each interquartile range within 0.007 of its median), against the square roots of that factor, 0.9905, 0.9509 and 0.8990. The exact miss probabilities without replacement, from the hypergeometric distribution, are lower than in the table above: Bernstein's 0.0014, 0.0026 and 0.0016, and the Wald interval's 0.0773, 0.0474 and 0.0338.
Functions of many variables: McDiarmid's inequality
The quantities of learning theory are often not averages. The largest gap between training error and risk over all thresholds, $Z = \sup_\theta\lvert L_S(h_\theta) - L_{\mathcal{D}}(h_\theta)\rvert$, whose double bounds the estimation error in Empirical Risk Minimization (Proposition 1), is a maximum of averages. It still has the property that makes averages concentrate: changing one training example changes every $L_S(h_\theta)$ by at most $1/m$, and so changes $Z$ by at most $1/m$.
A function $f$ of $n$ arguments has bounded differences $c_1, \ldots, c_n$ if changing the $i$th argument alone, with the others held fixed, changes $f$ by at most $c_i$:
$$\lvert f(x_1, \ldots, x_i, \ldots, x_n) - f(x_1, \ldots, x_i', \ldots, x_n)\rvert \le c_i \quad\text{for all } x_1, \ldots, x_n, x_i'.$$
Here is the plan. Reveal the variables one at a time and track the average of $f$ over the variables not yet revealed. Each revelation moves this average by an amount that, with the earlier variables held fixed, has mean zero and lies in an interval of length $c_i$. Hoeffding's lemma applies to each step with the past held fixed, and the steps multiply as in Theorem 2.
The proof uses one fact about independent random vectors $U$ and $W$ of any kind. For a function $\psi \ge 0$, or one with $E\lvert\psi(U, W)\rvert$ finite,
$$E[\psi(U, W)] = E[\bar\psi(U)], \qquad \bar\psi(u) = E[\psi(u, W)]:$$
average over $W$ with $U$ held fixed, then over $U$. This is Fubini's theorem for the product of the two distributions. For discrete variables and variables with densities it is the iterated sum or integral; in general it is Fubini's theorem for product measures (Billingsley, 1995, §18), taken as given. No conditional expectation is needed, so the proof covers independent variables with any distributions. We assume that $f$ is measurable. For a supremum over a class of functions, such as the largest deviation below or the suprema of Rademacher Complexity, this is an assumption on the class, standard when the class is uncountable; for thresholds and intervals on a finite grid the supremum is over finitely many values and is measurable. A function with bounded differences is bounded: two points differ in at most $n$ coordinates, so changing them one at a time gives $\lvert f(x) - f(y)\rvert \le \sum_i c_i$, and every expectation below is finite.
Theorem 5 (McDiarmid's inequality). Let $X_1, \ldots, X_n$ be independent, and let $f$ have bounded differences $c_1, \ldots, c_n$. Then for every $\varepsilon > 0$,
$$P\big(f(X_1, \ldots, X_n) - E[f(X_1, \ldots, X_n)] \ge \varepsilon\big) \le \exp\!\Big(-\frac{2\varepsilon^2}{\sum_{i=1}^n c_i^2}\Big),$$
and the same bound holds for the lower tail.
Proof. Write $F = f(X_1, \ldots, X_n)$ and $\mathbf{x}_{1:k} = (x_1, \ldots, x_k)$. For $0 \le k \le n$ let
$$g_k(x_1, \ldots, x_k) = E[f(x_1, \ldots, x_k, X_{k+1}, \ldots, X_n)],$$
the average of $f$ over the variables not yet revealed, so that $g_n = f$ and $g_0 = E[F]$. Let $D_k = g_k(\mathbf{X}_{1:k}) - g_{k-1}(\mathbf{X}_{1:k-1})$. Then $F - E[F] = D_1 + \cdots + D_n$, a sum that telescopes.
With the past fixed, each step has mean zero. Fix $\mathbf{x}_{1:k-1}$. The variables $X_k$ and $(X_{k+1}, \ldots, X_n)$ are independent, so by the fact above, averaging $f(\mathbf{x}_{1:k-1}, X_k, \ldots, X_n)$ over $(X_{k+1}, \ldots, X_n)$ first and then over $X_k$ gives $E[g_k(\mathbf{x}_{1:k-1}, X_k)] = g_{k-1}(\mathbf{x}_{1:k-1})$. So the step $d_k(X_k) = g_k(\mathbf{x}_{1:k-1}, X_k) - g_{k-1}(\mathbf{x}_{1:k-1})$, a random variable through $X_k$ alone, has mean 0.
With the past fixed, each step lies in an interval of length $c_k$. For two values $x$ and $x'$ of the $k$th argument, the bounded difference condition holds inside the expectation for every value of $X_{k+1}, \ldots, X_n$, so $\lvert g_k(\mathbf{x}_{1:k-1}, x) - g_k(\mathbf{x}_{1:k-1}, x')\rvert \le c_k$. The values of $d_k$ therefore lie in an interval $[A, A + c_k]$, with $A = \inf_x g_k(\mathbf{x}_{1:k-1}, x) - g_{k-1}(\mathbf{x}_{1:k-1})$. By Theorem 1, $E[e^{t d_k(X_k)}] \le e^{t^2c_k^2/8}$ for every real $t$, whatever the fixed past.
The steps multiply. For $t > 0$, the variables $D_1, \ldots, D_{k-1}$ are functions of $\mathbf{X}_{1:k-1}$, and $D_k$ is the step $d_k(X_k)$ at the past $\mathbf{X}_{1:k-1}$. Apply the fact above with $U = \mathbf{X}_{1:k-1}$ and $W = X_k$, which are independent, to the nonnegative function $e^{t(D_1 + \cdots + D_k)}$:
$$E\big[e^{t(D_1 + \cdots + D_k)}\big] = E\Big[e^{t(D_1 + \cdots + D_{k-1})}\,E\big[e^{t d_k(X_k)}\big]\big|_{\text{past} = \mathbf{X}_{1:k-1}}\Big] \le e^{t^2c_k^2/8}\,E\big[e^{t(D_1 + \cdots + D_{k-1})}\big].$$
For $k = 1$ the past is empty and the bound is Theorem 1 itself. Repeating for $k = n, n - 1, \ldots, 1$ gives $E[e^{t(F - E F)}] \le \exp(t^2\sum_k c_k^2/8)$. The Chernoff bound and the choice $t = 4\varepsilon/\sum_k c_k^2$ finish the proof exactly as in Theorem 2. For the lower tail apply the result to $-f$, which has the same bounded differences. $\square$
The averages $g_k(\mathbf{X}_{1:k})$ are the conditional expectations $E[F \mid \mathbf{X}_{1:k}]$ (for discrete variables and variables with densities this is the fact about independent variables proved in Random Walks and Martingales), so the $D_k$ are the increments of a martingale (Random Walks and Martingales defines martingales), and the proof is the martingale argument written without conditional expectations. Mohri, Rostamizadeh and Talwalkar (2018, Theorem D.8) prove the inequality with conditional expectations, through a conditional form of Hoeffding's lemma (their Lemma D.6) and a bounded-differences version of Azuma's inequality (their Theorem D.7), and their chapter notes credit this version, which improves the exponent of the earlier inequality of Hoeffding (1963) and Azuma (1967) by a factor of 4, to McDiarmid (1989). Hoeffding's inequality is the case $f = \bar X_n$ with $c_i = (b_i - a_i)/n$.
Example (the largest deviation over all thresholds). With $m = 500$ training examples, $Z = \sup_\theta\lvert L_S(h_\theta) - L_{\mathcal{D}}(h_\theta)\rvert$ has bounded differences $c_i = 1/m$, so Theorem 5 gives $P(Z - E[Z] \ge \varepsilon) \le \exp(-2m\varepsilon^2)$, and with probability at least 95%, $Z < E[Z] + \sqrt{\ln 20/(2m)} = E[Z] + 0.0547$. Over 2,000 training samples for each of 30 seeds (default_rng([20261122, seed, 500])), $E[Z]$ was 0.0336 (interquartile range over the seeds 0.0335 to 0.0337) and the standard deviation of $Z$ was 0.0110 (0.0109 to 0.0111), medians over the seeds; 95% of the samples had $Z$ within 0.0204 (0.0203 to 0.0210) above its mean. Theorem 5 says nothing about $E[Z]$ itself, only that $Z$ rarely strays far above it. Bounding $E[Z]$ is the work of Rademacher Complexity and The VC Dimension; McDiarmid's inequality is the step that turns such a bound on the mean into a bound that holds with high probability.
What is proved here, what is cited, what the experiment shows
Proved here, in full: Hoeffding's lemma (Theorem 1); the variance bound $(b - a)^2/4$ for a bounded variable; Hoeffding's inequality for independent variables with different ranges, in both tails, and its inversion into widths and sample sizes (Theorem 2); the Kullback–Leibler bound for variables in $[0, 1]$ and its comparison $\mathrm{kl} \ge 2\varepsilon^2$ (Theorem 3); the monotonicity of $(e^u - 1 - u)/u^2$ (Lemma 1); Bennett's inequality (Theorem 4) and Bernstein's inequality from it (Corollary); McDiarmid's bounded-differences inequality for independent variables with any distributions, by averaging over the variables not yet revealed (Theorem 5). The proofs use the Chernoff bound and the finite Jensen inequality (Probability Inequalities), the product rule for moment generating functions of independent variables (Moment Generating and Characteristic Functions), Taylor's theorem, and, for Theorem 5, Fubini's theorem for a product of distributions, taken as given in general.
Cited: Hoeffding's (1963) Theorem 4 on sampling without replacement and his statements of which bounds are best for the method; the attributions to Bennett (1962), Bernstein (1927), Azuma (1967) and McDiarmid (1989), as given by Hoeffding (1963) and by Mohri, Rostamizadeh and Talwalkar (2018).
What the experiment shows: for the error rate 0.0839 of one threshold rule on NHANES adults, Hoeffding's guaranteed half-width was 2.5 times the exact binomial one at every test-set size, the variance-aware bounds came within a factor of 1.4 to 1.6, and the guaranteed intervals missed with probability below 0.005, computed exactly and confirmed over 30 seeds; the Wald interval missed more often than its nominal 5%. For the largest deviation over all thresholds at 500 training examples, the observed spread was well inside McDiarmid's bound. These are properties of this error rate and these sizes; the bounds themselves hold for every distribution with the stated range.
Worked problems
These problems were written for this article; none comes from a textbook. They are posed on the article's NHANES threshold rule and on small exact cases, and the script tools/experiments/statistics/concentration-inequalities.py computes every number in them and asserts it.
Problem 1 (a test set for a rare error). A classifier's error rate is to be estimated within $\pm 0.02$ with confidence at least 95%. How large a test set suffices (a) knowing nothing about the error rate, (b) knowing only that it is at most 0.1?
Solution. (a) By Theorem 2 with losses in $[0, 1]$, $2\exp(-2n\varepsilon^2) \le 0.05$ when $n \ge \ln 40/(2 \times 0.02^2)$. With $\ln 40 = 3.6889$, that is $n \ge 4{,}611.1$, so 4,612 test cases.
(b) If $p \le 0.1$, then $\sigma^2 = p(1 - p) \le 0.09$, because $p(1 - p)$ increases on $[0, 1/2]$, and $\lvert X_i - p\rvert \le 1$. Bernstein's inequality with these upper bounds, which only enlarge the right side, gives $2\exp(-n\varepsilon^2/(2 \times 0.09 + 2 \times 0.02/3)) \le 0.05$ when $n \ge \ln 40 \times (0.18 + 0.01333)/0.0004$, so 1,783 test cases. The prior bound on the error rate saves 61% of the test set.
Problem 2 (the fair coin). For a loss that is 0 or 1 with probability one half each, compute the moment generating function of the centered loss and prove Hoeffding's lemma for it directly.
Solution. The centered loss $X - \frac12$ is $\pm\frac12$ with probability one half each, so $E[e^{t(X - 1/2)}] = \frac12(e^{t/2} + e^{-t/2}) = \cosh(t/2)$. By the power series, $\cosh y = \sum_{k \ge 0} \frac{y^{2k}}{(2k)!}$ and $e^{y^2/2} = \sum_{k \ge 0}\frac{y^{2k}}{2^k k!}$. Since $(2k)! = \prod_{j=1}^{k}(2j - 1)(2j) \ge \prod_{j=1}^{k} 2j = 2^k k!$, each term of the first series is at most the matching term of the second, so $\cosh(t/2) \le e^{t^2/8}$, which is Theorem 1 with $b - a = 1$. At $t = 4$, $\ln\cosh 2 = 1.3250$ against $t^2/8 = 2$. The two agree to second order at $t = 0$, since both logarithms are $t^2/8 + O(t^4)$: for the fair coin the lemma's constant cannot be improved, because the coin has the largest variance a variable in $[0, 1]$ can have.
Problem 3 (the largest deviation over the thresholds). For $m = 500$ training examples, how far above its mean can $Z = \sup_\theta\lvert L_S(h_\theta) - L_{\mathcal{D}}(h_\theta)\rvert$ be with probability at most 5%, according to Theorem 5? Compare with the simulation.
Solution. Replacing one example changes the training error of every threshold by at most $1/500$, so $\lvert L_S(h_\theta) - L_{\mathcal{D}}(h_\theta)\rvert$ changes by at most $1/500$ for each $\theta$, and so does their supremum: if $Z$ is the supremum before the change and $Z'$ after, every term after is at most its value before plus $1/500$, so $Z' \le Z + 1/500$, and symmetrically. Theorem 5 with $c_i = 1/500$ gives $P(Z - E Z \ge \varepsilon) \le \exp(-1{,}000\,\varepsilon^2)$, which equals 0.05 at $\varepsilon = \sqrt{\ln 20/1{,}000} = 0.0547$. In the simulation the mean of $Z$ was 0.0336, its standard deviation 0.0110, and its 95th percentile only 0.0204 above the mean. At $\varepsilon = 0.02$ the bound is 0.67, while the observed share of samples with $Z - E Z \ge 0.02$ was 0.054. The bound uses only the bounded differences and holds for every distribution; for this one it is loose by a factor of about 2.7 in the deviation.
Problem 4 (when the variance pays). At $\varepsilon = 0.02$, for which error rates $p$ does Bernstein's inequality with $c = 1$ give a smaller bound than Hoeffding's?
Solution. Bernstein's two-sided bound $2\exp(-n\varepsilon^2/(2\sigma^2 + 2\varepsilon/3))$ is smaller than Hoeffding's $2\exp(-2n\varepsilon^2)$ when $2\sigma^2 + 2\varepsilon/3 < 1/2$, that is $\sigma^2 < 1/4 - \varepsilon/3 = 0.2433$. With $\sigma^2 = p(1 - p)$ this means $p(1 - p) < 0.2433$, which holds for $p < 0.418$ and, by symmetry, for $p > 0.582$. Only for error rates near one half, where the variance is near its maximum, does Hoeffding's bound win, and then only slightly, as the rows for $p = 0.5$ in the sample size table show.
Summary
| Inequality | Assumptions | Bound on the upper tail |
|---|---|---|
| Hoeffding's lemma | $X \in [a, b]$, $E X = 0$ | $E[e^{tX}] \le e^{t^2(b - a)^2/8}$ |
| Hoeffding | independent, $X_i \in [a_i, b_i]$ | $\exp(-2n^2\varepsilon^2/\sum(b_i - a_i)^2)$ |
| Kullback–Leibler | independent, $X_i \in [0, 1]$ | $\exp(-n\,\mathrm{kl}(\mu + \varepsilon \,\Vert\, \mu))$ |
| Bennett | independent, $X_i - E X_i \le c$, $V = \sum\operatorname{Var} X_i$ | $\exp(-\frac{V}{c^2}h(c\varepsilon/V))$ for the sum |
| Bernstein | as Bennett | $\exp(-\varepsilon^2/(2(V + c\varepsilon/3)))$ for the sum |
| McDiarmid | independent, bounded differences $c_i$ | $\exp(-2\varepsilon^2/\sum c_i^2)$ |
What we have learned
A mean of independent bounded variables concentrates around its expectation exponentially fast, and Hoeffding's inequality says how fast from the ranges alone: a test set of $\ln(2/\delta)/(2\varepsilon^2)$ cases estimates any error rate within $\pm\varepsilon$ with confidence $1 - \delta$. The price of knowing nothing is the worst variance and a bound that must hold for every distribution. For the 6.7% threshold rule, whose error rate is 0.0839, Hoeffding's interval is about 2.5 times as wide as the exact one, and Bernstein's inequality, which uses the variance, recovers most of the difference. McDiarmid's inequality carries the same exponential concentration from averages to any function that no single example can move much, such as the largest deviation over a class of rules.
Each of these bounds is about one fixed function of the sample. The rule chosen by empirical risk minimization depends on the sample, so a guarantee for it needs a bound that holds for every rule of the class at once. For a finite class, Hoeffding's inequality and a union bound give one, and that is the subject of PAC Learning and Finite Hypothesis Classes.
Every number in this article is computed by tools/experiments/statistics/concentration-inequalities.py in the site's repository, which downloads the NHANES files from the CDC and checks their checksums (loader tools/experiments/statistics/sltdata.py). The figure is drawn by tools/figures/concentration-inequalities.py from the script's results.
References
- Azuma, K. (1967). Weighted sums of certain dependent random variables. Tohoku Mathematical Journal, 19(3), 357–367. https://doi.org/10.2748/tmj/1178243286 (Not consulted; cited for the attribution given by Mohri, Rostamizadeh and Talwalkar, 2018.) record
- Bennett, G. (1962). Probability inequalities for the sum of independent random variables. Journal of the American Statistical Association, 57(297), 33–45. https://doi.org/10.1080/01621459.1962.10482149 (Not consulted; cited for the attribution given by Hoeffding, 1963.) record
- Bernstein, S. N. (1927). Sur l'extension du théorème limite du calcul des probabilités aux sommes de quantités dépendantes. Mathematische Annalen, 97, 1–59. (Not consulted; cited for the attribution given by Mohri, Rostamizadeh and Talwalkar, 2018.) record
- Billingsley, P. (1995). Probability and Measure (3rd ed.). Wiley. Section 18 ("Product Measure and Fubini's Theorem"). Section number and title are those of the contents of the 2012 Anniversary Edition, which reissues the third edition. record · 11 pages
- Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301), 13–30. https://doi.org/10.1080/01621459.1963.10500830 Theorem and equation numbers are those of the published paper; also circulated as Institute of Statistics Mimeo Series No. 326, University of North Carolina, May 1962. record · 2 pages
- McDiarmid, C. (1989). On the method of bounded differences. In Surveys in Combinatorics, 1989 (London Mathematical Society Lecture Note Series 141, pp. 148–188). Cambridge University Press. https://doi.org/10.1017/CBO9781107359949.008 (Not consulted; cited for the attribution given by Mohri, Rostamizadeh and Talwalkar, 2018.) record
- Mohri, M., Rostamizadeh, A., and Talwalkar, A. (2018). Foundations of Machine Learning (2nd ed.). MIT Press. Appendix D: Lemma D.1, Theorem D.2, Lemma D.6, Theorems D.7 and D.8, Exercise D.6 and the chapter notes (§D.11). record · 5 pages
- National Center for Health Statistics (2020). National Health and Nutrition Examination Survey 2017–2018: Demographic Variables and Sample Weights (DEMO_J), Glycohemoglobin (GHB_J) and Diabetes (DIQ_J) data files. Centers for Disease Control and Prevention. https://wwwn.cdc.gov/nchs/nhanes/continuousnhanes/default.aspx?BeginYear=2017 record · 106 pages
- Shalev-Shwartz, S., and Ben-David, S. (2014). Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press. Appendix B: Lemmas B.7 (Hoeffding's lemma) and B.9 (Bernstein's inequality). record · 6 pages