Concentration Inequalities and Generalisation Bounds

You evaluate a model on 500 held-out examples and get 82 percent. How much of that is the model and how much is the sample? The answer is a concentration inequality, and the same machinery that answers it for one fixed model is what classical learning theory tries, and largely fails, to extend to a model chosen by training.

The ladder

Each inequality below buys a stronger tail bound by assuming more.

Markov. For \(X \ge 0\): \(\Pr[X \ge a] \le \mathbb{E}[X]/a\). Assumes only non-negativity, and is correspondingly weak. Everything else is built from it.

Chebyshev. \(\Pr[|X - \mu| \ge k\sigma] \le 1/k^2\). Adds finite variance, gives polynomial decay.

Hoeffding. For independent \(X_i \in [a_i, b_i]\) and \(\bar{X}\) their mean,

Adds boundedness and buys exponential decay. For \([0,1]\)-valued losses this simplifies to \(2e^{-2nt^2}\), which is the inequality behind almost every error bar you have ever computed on an accuracy. Inverting it: to be within \(\pm t\) with 95 percent confidence you need about \(n \ge \ln(40)/(2t^2)\) samples, so roughly 738 samples for \(\pm 5\) percent and 18,400 for \(\pm 1\) percent. That arithmetic is the entire reason small eval sets cannot distinguish close models.

Bernstein. Replaces the range with the variance in the exponent, so low-variance quantities concentrate much faster. This is why bounds on rare events should never be derived from Hoeffding.

McDiarmid. Generalises Hoeffding from means to any function of independent variables that changes by at most \(c_i\) when the \(i\)-th input changes. This is the version learning theory actually uses, because the generalisation gap is such a function.

From concentration to generalisation

For a single, fixed hypothesis, Hoeffding says test error is within \(O(1/\sqrt{n})\) of training error with high probability, and you are done. Training breaks this, because the hypothesis was chosen using the data, so the bound no longer applies to it.

The classical repair is a uniform bound: control the deviation for every hypothesis in the class simultaneously, so it holds for whichever one training picked. A union bound over a finite class of size \(|\mathcal{H}|\) gives

so the sample requirement grows like \(\log|\mathcal{H}|\). For infinite classes, VC dimension and Rademacher complexity replace \(\log|\mathcal{H}|\) with a measure of how much the class can fit arbitrary labellings, giving bounds of the form

with \(\mathfrak{R}_n\) the Rademacher complexity (Bartlett & Mendelson, 2002, JMLR 3:463-482).

Why this fails for deep networks

Zhang et al. delivered the decisive counterexample: standard image classifiers can fit ImageNet with completely random labels, to zero training error (Zhang et al., 2017, Understanding deep learning requires rethinking generalization, arXiv:1611.03530, ICLR 2017). A class that can fit arbitrary labellings of the training set has Rademacher complexity near its maximum, so the uniform bound gives a generalisation gap bound above one. The bound is vacuous: it says test error is at most 100 percent, which was known.

The failure is not a loose constant. It is structural. Uniform bounds control the worst hypothesis in the class, and the whole reason deep learning works is that SGD does not return the worst one. Any bound that ignores the algorithm cannot explain an outcome the algorithm produced.

The active repairs each restore some algorithm-dependence: PAC-Bayes bounds over the posterior a training procedure actually reaches, which have produced the first non-vacuous numerical bounds for real networks; compression-based bounds, which pay for the compressed description of the trained network rather than the class; and margin-based bounds normalised by spectral norms of the learned weights. None yet predicts observed generalisation well enough to guide design.

When it breaks

Two practical cautions carry over even where the theory does not.

Concentration bounds need independence, and evaluation sets frequently violate it. Multiple questions generated from one document, near-duplicate items, or a benchmark built by templating are all dependent, and the effective sample size is closer to the number of sources than the number of items. A Hoeffding interval computed as if items were independent is too narrow, sometimes by a large factor.

And these are bounds on a fixed evaluation. Selecting the best of twenty checkpoints against the same held-out set re-introduces exactly the multiple-hypothesis problem the union bound was invented for. The correction is the same one: pay a \(\log(\text{number of comparisons})\) factor, or hold out a set you only look at once. See eval error bars and statistics and statistical learning theory.