the bounded-differences (McDiarmid) inequality
/ mək-DAR-mid /
Often what we care about is not a simple sum but a complicated function of many independent inputs — the error rate of a trained model, the largest cluster in a random network, the length of the longest common subsequence of two random strings. Could such a tangled quantity still be sharply concentrated near its average? McDiarmid's inequality says yes, provided no single input can change the output too much.
Setup: let f(X_1, ..., X_n) be any function of independent inputs, and suppose it has the bounded-differences property — changing only the i-th input, while holding all others fixed, can move the output by at most c_i. Then f concentrates exactly like a Hoeffding sum: P(f - E[f] >= t) <= exp( -2 t^2 / sum of c_i^2 ), with the same bound on the lower tail. The function can be wildly nonlinear and entangle the inputs in any way at all; only the per-input sensitivities c_i matter. The proof builds a Doob martingale — reveal the inputs one at a time and track the conditional expectation of f — and then applies the Azuma-Hoeffding inequality to it.
This is the engine of modern concentration for complex statistics, and a pillar of statistical learning theory: it shows that an empirical risk, a Rademacher complexity, or a kernel statistic stays close to its mean when no single data point dominates. The whole burden of the analysis reduces to one check — bound how much one input can swing the output. The honest caveat: McDiarmid is only as good as your bounds c_i. If even one input can drastically change f (a large c_i), the bound becomes useless, and functions dominated by a single coordinate (like a maximum that can jump a lot) are exactly the cases where it fails to help.
Let f be the proportion of misclassified points by a model trained on n independent examples. Swapping one training example can change this proportion by at most c = 1/n. McDiarmid then gives P(|f - E[f]| >= t) <= 2 exp(-2 t^2 / (n (1/n)^2)) = 2 exp(-2 n t^2): the test error concentrates around its mean.
Any function of independent inputs concentrates if no single input swings it by much.
McDiarmid's strength is entirely set by the difference bounds c_i. One coordinate with a large c_i (a function a single input can swing wildly) makes the bound useless.