the bounded-differences (McDiarmid) inequality
/ mick-DAR-mid /
McDiarmid's inequality is the leap from concentration of SUMS to concentration of arbitrary FUNCTIONS of independent variables. Many quantities in statistics and learning are not sums at all — the maximum, the median, the empirical risk of a trained model, the largest eigenvalue, the size of a longest increasing subsequence — yet they concentrate sharply around their mean for the same fundamental reason a sum does: no single coordinate matters too much. McDiarmid's inequality makes that intuition precise through a 'bounded differences' condition.
The statement: let X_1, ..., X_n be independent (each taking values in some space, not necessarily real) and let f be a function satisfying the bounded-differences condition with constants c_1, ..., c_n: changing the i-th argument alone, while holding the others fixed, changes f by at most c_i. That is, sup over x and x_i' of |f(x_1,...,x_i,...,x_n) - f(x_1,...,x_i',...,x_n)| <= c_i. Then for every t > 0, P(f - E[f] >= t) <= exp(-2 t^2 / sum_i c_i^2), and the two-sided version doubles the bound. Notice the right side depends only on the bounded-differences constants, exactly as Hoeffding depends only on the ranges — McDiarmid is the Hoeffding inequality for functions, and it specializes to Hoeffding when f is the sum (then c_i = b_i - a_i). The mechanism behind it is the martingale (Azuma) method: write f - E[f] as a telescoping sum of martingale differences D_i = E[f | X_1..X_i] - E[f | X_1..X_{i-1}], each of which is bounded in range by c_i, and apply Azuma-Hoeffding to that martingale.
McDiarmid is the single most-used concentration tool in statistical learning theory, because the supremum of an empirical process (which governs generalization error) typically has bounded differences c_i ~ 1/n in each example, giving exponential concentration of order exp(-t^2 n / 2). Its honest limitation, however, is that it pays no attention to variance: like Hoeffding, its rate is set by the WORST-CASE differences sum c_i^2, even if f is usually far less sensitive. When a single coordinate can occasionally cause a large change but rarely does, the bounded-differences bound is loose, and one needs Talagrand's convex-distance inequality or the entropy method (which use a 'self-bounding' or variance-like quantity) to capture the true, smaller fluctuation.
Let f be the empirical risk (1/n) sum loss(h, Z_i) of a fixed predictor h with loss in [0,1], over independent samples Z_i. Changing one Z_i changes f by at most 1/n, so c_i = 1/n and McDiarmid gives P(|empirical risk - true risk| >= t) <= 2 exp(-2 n t^2) — the basic generalization bound for a single hypothesis, before any union bound or VC argument.
Bounded differences turn any stable function of the data into a concentrated one.
McDiarmid's rate uses the worst-case differences c_i, not the variance of f, so it is loose when f is usually insensitive but occasionally swings. It also requires independence of the X_i; bounded differences alone is not enough without it.