Inequalities and concentration

Most measured numbers in machine learning are averages over a sample: a validation accuracy, a mean loss, a click-through rate. How far can such an average be from the expectation it estimates? The distribution is usually unknown, so the useful answers are inequalities that hold for every distribution with some property: a known mean, a known variance, a bounded range. This note derives the three that matter, Markov’s, Chebyshev’s and Hoeffding’s, compares them with the exact answer, and uses the last one with the union bound to get a first guarantee about a model chosen on a validation set.

Notation. $X_1, \dots, X_n$ are independent with mean $\mu$; $\bar X_n$ is their average. $\varepsilon > 0$ is a deviation and $\delta$ a small failure probability.

Markov’s inequality#

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

$$P(X \ge a) \le \frac{E[X]}{a} .$$

The proof is one comparison: $a \mathbb 1_{\{X \ge a\}} \le X$ for every outcome, and taking expectations gives $a P(X \ge a) \le E[X]$. A mean alone limits how much probability can sit far out. If requests take 0.2 s on average, at most 10% of them can take 2 s or more, whatever the distribution. The bound is often loose: for an exponential response time with that mean the true share is $e^{-10} = 4.5 \cdot 10^{-5}$. It cannot be improved without more information, though: a variable equal to $a$ with probability $E[X]/a$ and to 0 otherwise attains it.

Chebyshev’s inequality#

Applying Markov’s inequality to $(X - \mu)^2$ uses the variance as well:

$$P(\lvert X - \mu \rvert \ge k\sigma) \le \frac{1}{k^2} .$$

Any distribution with a finite variance has at most 25% of its probability two standard deviations or more from the mean, and at most 11.1% three or more. A normal distribution has $4.55\%$ and $0.27\%$; again the bound holds for every distribution and is far from the typical one.

Applied to an average, whose variance is $\sigma^2 / n$, Chebyshev’s inequality gives

$$P(\lvert \bar X_n - \mu \rvert \ge \varepsilon) \le \frac{\sigma^2}{n \varepsilon^2} \to 0 ,$$

which is already the weak law of large numbers: averages approach the mean. The rate, $1/n$, is too pessimistic.

Hoeffding’s inequality#

If the variables are also bounded, $a \le X_i \le b$, the probability of a deviation falls exponentially:

$$P(\lvert \bar X_n - \mu \rvert \ge \varepsilon) \le 2 \exp\Big(-\frac{2 n \varepsilon^2}{(b - a)^2}\Big) .$$

Losses in $[0, 1]$, correct-or-not indicators and clicks are all bounded, which is why this inequality is the standard tool of learning theory. For the share of heads in $n$ fair coin flips and a deviation of $0.1$, the two bounds and the exact binomial probability compare as follows:

Figure

Two tail bounds and the exact probability

Turned around, Hoeffding’s inequality gives a sample size. To estimate an accuracy within $\pm 0.02$ with probability at least $0.95$, set $2 e^{-2n \cdot 0.02^2} \le 0.05$:

Method	Examples needed	Assumes
Chebyshev, with $\sigma^2 \le 1/4$	12,500	a finite variance
Hoeffding	4,612	independent, bounded
Normal approximation	2,401	$n$ large enough for the central limit theorem

The normal approximation needs the fewest examples and is what confidence intervals use; Hoeffding’s bound costs about twice as many and in return is guaranteed for every $n$.

Where the exponent comes from#

Optional depth: a proof sketch of Hoeffding’s inequality. The rest of the note does not depend on it.

The proof is Markov’s inequality applied to an exponential, the Chernoff method. For any $t > 0$,

$$P(\bar X_n - \mu \ge \varepsilon) = P\big(e^{t n (\bar X_n - \mu)} \ge e^{t n \varepsilon}\big) \le e^{-t n \varepsilon}\, E\big[e^{t n (\bar X_n - \mu)}\big] = e^{-t n \varepsilon} \prod_{i=1}^n E\big[e^{t (X_i - \mu)}\big] ,$$

where independence turned the expectation of a product into a product of expectations, the moment generating functions of the expectation note. For a variable in $[a, b]$, Hoeffding’s lemma bounds each factor by $e^{t^2 (b-a)^2 / 8}$. Boundedness is what makes the exponent quadratic. Let $\psi(t) = \log E[e^{t(X - \mu)}]$. Then $\psi(0) = 0$ and $\psi'(0) = E[X - \mu] = 0$, and $\psi''(t)$ is the variance of $X$ under its distribution reweighted by the factor $e^{tx}$ and renormalized, which still lives on $[a, b]$; a variable on $[a, b]$ has variance at most $(b - a)^2/4$. Taylor’s theorem with these three facts gives $\psi(t) \le \frac{t^2}{2} \cdot \frac{(b-a)^2}{4} = t^2 (b-a)^2/8$. The bound $\exp(-tn\varepsilon + n t^2 (b-a)^2/8)$ is smallest at $t = 4\varepsilon/(b-a)^2$, which gives $\exp(-2n\varepsilon^2/(b-a)^2)$; the same argument for the lower tail supplies the factor 2. Markov’s inequality applied to $X^k$ gives polynomial tails; applied to $e^{tX}$ it gives exponential ones, as long as the moment generating function exists.

A first generalization bound#

A model’s risk $R(h)$ is its expected loss on new data, and its validation loss $\hat R(h)$ is the average over $n$ independent validation examples. For one model fixed in advance, Hoeffding’s inequality with losses in $[0, 1]$ gives $P(\lvert \hat R(h) - R(h) \rvert \ge \varepsilon) \le 2 e^{-2n\varepsilon^2}$. But the model is usually chosen on the validation set, the best of $K$ candidates from a hyperparameter search. The union bound over the $K$ events “model $k$ deviates by $\varepsilon$” gives, for all $K$ models simultaneously,

$$P\big(\exists k : \lvert \hat R(h_k) - R(h_k) \rvert \ge \varepsilon\big) \le 2K e^{-2n\varepsilon^2} .$$

Setting the right-hand side to $\delta$: with probability at least $1 - \delta$, every one of the $K$ models, and so also the chosen one, has

$$\lvert \hat R(h) - R(h) \rvert \le \sqrt{\frac{\ln K + \ln(2/\delta)}{2n}} .$$

For $K = 1{,}000$ models and $n = 10{,}000$ validation examples at $\delta = 0.05$ the margin is $0.023$. The number of candidates enters only through $\ln K$, so a thousand times more candidates costs only a few times more data. The figure shows the margin next to the typical effect of selection when all $K$ models are in truth equally good:

Figure

How much better the best of K equally good models looks than it is

The best of 1,000 equally accurate models, with independent errors on the validation set, looks on average 1.3 accuracy points better than it is. That is the mechanism of overfitting to a validation set, and the reason a final model is reported on a test set that played no part in choosing it. The argument assumes that the $K$ candidates are fixed before the validation data are seen; a search that proposes new candidates from validation scores, such as Bayesian optimization, needs more care. For infinitely many candidates, such as all the weight settings of a network, $\ln K$ is replaced by measures of the capacity of the model class; in practice the machine learning course estimates the error on held-out data instead.

What changed#

	Without inequalities	With them
Error of an average	“small for large $n$”	Chebyshev: $P \le \sigma^2/(n\varepsilon^2)$; Hoeffding: $P \le 2e^{-2n\varepsilon^2/(b-a)^2}$
Sample size for $\pm 0.02$ at 95%	a guess	4,612 guaranteed (Hoeffding), 2,401 approximately (normal)
A model chosen among $K$	its validation score taken at face value	margin $\sqrt{(\ln K + \ln(2/\delta))/(2n)}$ for all $K$ at once

Limitations#

• The bounds are worst-case. They hold for every distribution with the stated property and so are loose for any particular one; Chebyshev’s is off by orders of magnitude for normal tails.
• Hoeffding needs boundedness and independence. Heavy-tailed losses, or examples that come in correlated groups (several from one user, near-duplicates), break the assumptions; then other tools are needed: median-of-means estimators for heavy tails, bounds over independent blocks for grouped data, and Bernstein’s inequality when the variance is much smaller than the range.
• The union bound ignores how similar the candidates are. Models from a hyperparameter search make highly correlated predictions, so the real selection effect is smaller than the $\ln K$ bound suggests.

What you should remember#

• Markov: $P(X \ge a) \le E[X]/a$ for $X \ge 0$. Chebyshev: $P(\lvert X - \mu \rvert \ge k\sigma) \le 1/k^2$.
• Hoeffding: for independent $X_i \in [a, b]$, $P(\lvert \bar X_n - \mu \rvert \ge \varepsilon) \le 2e^{-2n\varepsilon^2/(b-a)^2}$, exponentially small in $n$.
• All three are Markov’s inequality applied to a function of $X$: itself, its square, its exponential.
• To estimate a proportion within $\pm 0.02$ at 95%: 4,612 examples by Hoeffding, about 2,401 by the normal approximation.
• With $K$ candidates, every validation score is within $\sqrt{(\ln K + \ln(2/\delta))/(2n)}$ of the truth with probability at least $1 - \delta$; the best of many looks better than it is.

Code#

The bounds against exact values, the sample sizes, and the selection effect by simulation:

import numpy as np, math
from scipy import stats

# Markov and Chebyshev against the truth
print(round(0.2 / 2, 2), f'{math.exp(-10):.1e}')                  # 0.1 4.5e-05: Markov's bound vs Exp(mean 0.2)
print([round(1 / k**2, 3) for k in (2, 3)], [round(float(2 * stats.norm.sf(k)), 4) for k in (2, 3)])   # [0.25, 0.111] [0.0455, 0.0027]

# the share of heads in n flips off by at least 0.1: exact, Chebyshev, Hoeffding
for n in (100, 1000):
    S = stats.binom(n, 0.5)
    exact = S.cdf(int(0.4 * n)) + S.sf(int(0.6 * n) - 1)
    print(n, f'{exact:.1e}', 25 / n, f'{2 * math.exp(-0.02 * n):.1e}')
# 100 5.7e-02 0.25 2.7e-01
# 1000 2.7e-10 0.025 4.1e-09

# examples needed to estimate an accuracy within 0.02 with probability 0.95: Hoeffding, Chebyshev, normal approximation
print(math.ceil(math.log(2 / 0.05) / (2 * 0.02**2)), math.ceil(0.25 / (0.02**2 * 0.05)), math.ceil((1.96 * 0.5 / 0.02) ** 2))   # 4612 12500 2401

# the best of K = 1,000 identical models (true accuracy 0.8), each on 10,000 validation examples, 2,000 times
rng = np.random.default_rng(0)
best = (rng.binomial(10_000, 0.8, size=(2000, 1000)) / 10_000).max(axis=1)
eps = math.sqrt((math.log(1000) + math.log(40)) / (2 * 10_000))
print(round(float(best.mean()), 4), round(eps, 4), float((best - 0.8 > eps).mean()))   # 0.8129 0.023 0.0

Next#

Chebyshev’s inequality already showed that averages approach the mean in probability. The next note states the law of large numbers in its weak and strong forms, explains the difference between the two kinds of convergence, and turns the law into a computational method: Monte Carlo estimation of any expectation by averaging samples.

References#

• W. Hoeffding. Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association, 58(301), 1963.
• S. Boucheron, G. Lugosi, P. Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 2013. Chapter 2 (basic inequalities, the Chernoff method, Hoeffding’s lemma).
• S. Shalev-Shwartz, S. Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014. Chapters 2–4 (finite hypothesis classes and uniform convergence).
• J. K. Blitzstein, J. Hwang. Introduction to Probability, 2nd ed. CRC Press, 2019. Chapter 10 (inequalities and limit theorems).