The Probabilistic Engine: Concentration and Stability

Beyond Hoeffding: a toolbox

Every bound so far rested on Hoeffding's inequality — a sum of bounded independent variables concentrates around its mean with Gaussian-like tails. Graduate work needs a richer kit, because Hoeffding is wasteful: it only knows the range of each variable, never its variance. When the loss is usually tiny but occasionally large, ignoring variance throws away most of the signal, and the resulting concentration bound is loose by exactly the factor that matters in fast-rate analysis.

Hoeffding — bounded variables; tail uses only the range. The blunt default.
Bernstein — adds the variance term; sharp when the loss is usually small.
McDiarmid (bounded differences) — for any function of the sample that changes little when one point changes.
Talagrand — concentration of the supremum of an empirical process; the engine behind localization.

McDiarmid: concentration without a sum

The quantity we actually care about — the worst-case gap over a whole hypothesis class — is not a simple sum, so Hoeffding does not directly apply. McDiarmid's bounded-differences inequality rescues us: if changing any single one of the m samples shifts your function's value by at most c, then the function concentrates around its mean with tails like exp(−2ε²/(m·c²)). The supremum of an empirical process satisfies exactly this bounded-differences property — one sample swap can move the sup by at most O(1/m) — so it concentrates even though it is wildly nonlinear.

P\big(f(X_1,\dots,X_n)-\mathbb{E}f\ge t\big)\le\exp\!\left(-\frac{2t^2}{\sum_{i=1}^{n}c_i^2}\right)

McDiarmid's bounded-differences inequality: if no single coordinate can move f by more than c_i, then f concentrates — no sum required.

This is the load-bearing step in the standard Rademacher proof: McDiarmid concentrates the worst-case gap around its expectation, a symmetrization argument rewrites that expectation as a Rademacher complexity, and the uniform convergence bound from guide 2 drops out. Almost every generalization theorem you will read has McDiarmid hiding in this exact slot.

Stability: a second road to generalization

Uniform convergence asks about the whole class, but ERM only ever outputs one hypothesis. Algorithmic stability takes a completely different route: it studies the algorithm directly. An algorithm is stable if removing or replacing a single training example barely changes the hypothesis it returns — formally, the loss on any point changes by at most β when you perturb one of the m training examples. Stability never mentions a hypothesis class or its capacity; it is a property of the learning procedure.

The headline theorem is clean: if an algorithm has uniform stability β, its expected generalization gap is at most β, and a McDiarmid argument upgrades that to a high-probability bound. So you generalize if and only if you are stable — capacity never enters. This explains learners that uniform convergence cannot: a stable algorithm in an enormous hypothesis class can still generalize, because the algorithm explores only a benign sliver of that class.

\mathbb{E}_{S}\big[R(A_S)-\hat{R}_S(A_S)\big]\le\beta

The headline stability theorem: an algorithm with uniform stability β has expected generalization gap at most β.

Why your regularizer is a stabilizer

Stability is not exotic; it is what regularization buys. Strong convexity is the bridge: adding an L2 penalty makes the training objective λ-strongly convex, and the minimizer of a strongly convex objective moves by at most O(1/(λm)) when one example changes. So ridge regularization grants uniform stability on the order of 1/(λm) — turn up λ and you trade a little fit for a lot of stability, which the theorem converts directly into a generalization guarantee.

\beta\le\frac{\rho^2}{\lambda n}

Why a regularizer stabilizes: the λ-strong convexity bought by the L2 penalty bounds the uniform stability of regularized ERM by ρ²⁄(λn).

The same lens illuminates stochastic gradient descent: run for few enough steps with a modest learning rate and SGD is itself algorithmically stable, because each update touches the iterate only gently and the influence of any one example stays bounded. Stability thereby ties the dynamics of optimization to generalization without ever computing a capacity — a thread the next guide and the whole Vol II story of benign overfitting pick up.