High-Probability Generalization from Stability

From Expected Generalization to a Probability Guarantee

An algorithm can have a small expected difference between population risk and training risk without that difference being small on every sample. A high-probability statement addresses the sample-to-sample fluctuation: it says that, except on an event of specified probability, the population risk is no more than the observed training risk plus an explicit allowance. Uniform stability supplies one part of that allowance; concentration of the sample-dependent gap supplies the other.

We consider a fixed learning algorithm and independent observations. The loss is bounded, so changing a single observation cannot cause an arbitrarily large direct change in the training loss. Stability also controls how much the fitted rule changes when one observation is replaced. Together these facts make the generalization gap concentrate around its expectation.

Setup and Uniform Stability

Let \(Z_1,\ldots,Z_n\) be independent observations with common distribution \(P\), and write \(S=(Z_1,\ldots,Z_n)\). A deterministic learning algorithm \(A\) maps a sample to a prediction rule \(A(S)\). Let \(\ell(h,z)\) be the loss of rule \(h\) on observation \(z\), and suppose it is measurable and takes values in \([0,1]\). Define the population and empirical risks by

The generalization gap of the fitted rule is \(G(S)=R(A(S))-\widehat R_S(A(S))\). A positive gap means the population risk exceeds the training risk. The expectation in \(R(A(S))\) is over a fresh observation \(Z\) independent of the training sample, while \(A(S)\) is held fixed.

The bound is uniform over both the replaced sample coordinate and the test observation. Stability controls the change in loss caused by changing the fitted rule; it does not say that the loss itself is small. We assume throughout that the risks and random quantities used below are measurable and integrable. For the concentration argument, the observations are independent as stated above.

Expected Generalization Gap

First, stability bounds the expected signed gap. The argument compares a training observation with an independent replacement and uses the fact that the replaced sample has the same distribution as the original sample.

To verify the result, let \(Z_i'\) be an independent draw from \(P\), and let \(S^{(i)}\) be \(S\) with coordinate \(i\) replaced by \(Z_i'\). By independence and identical distributions, the pair consisting of \(S^{(i)}\) and \(Z_i\) has the same distribution as the pair consisting of \(S\) and a fresh test observation. Therefore,

The samples \(S^{(i)}\) and \(S\) differ in at most one coordinate. Uniform stability bounds the absolute value of each difference inside the expectation by \(\beta\). Hence each expectation has absolute value at most \(\beta\), and the absolute value of their average is also at most \(\beta\). This proves the result. \(\square\)

The expected-gap result alone is not a high-probability guarantee: a random variable can have a small expectation while still taking relatively large values on some samples. The next step controls how much \(G(S)\) can change when one input observation changes.

Bounded Differences and the High-Probability Bound

We use the bounded-differences inequality, also called McDiarmid’s inequality. If \(W_1,\ldots,W_n\) are independent and a measurable function \(F(W_1,\ldots,W_n)\) changes by at most \(c_i\) whenever only coordinate \(i\) is replaced, then, for \(t>0\),

For the generalization gap, replace coordinate \(i\) of \(S\) to obtain \(S'\). The population-risk term changes by at most \(\beta\): for every test observation the losses differ by at most \(\beta\), and taking expectations preserves that bound. For the empirical-risk term, each of the \(n-1\) unchanged observations contributes a loss change of at most \(\beta\). The remaining observation can change both its value and the fitted rule, but both losses are in \([0,1]\), so their difference is at most \(1\). Consequently,

Combining the two changes gives a coordinate bound for \(G\):

Thus we can use \(c_i=2\beta+1/n\) for each coordinate. Applying the bounded-differences inequality and the expected-gap result gives the following theorem.

Indeed, \(\sum_i c_i^2=n(2\beta+1/n)^2=(2n\beta+1)^2/n\). Set \[ t=(2n\beta+1)\sqrt{\frac{\log(1/\delta)}{2n}}. \] The bounded-differences inequality then gives \(P(G-EG\geq t)\leq\delta\). Since \(E[G]\leq\beta\), outside an event of probability at most \(\delta\), \(G\leq\beta+t\). Substituting \(G=R(A(S))-\widehat R_S(A(S))\) proves the stated risk bound. \(\square\)

The first term, \(\beta\), comes from the expected generalization gap. The remaining term is the sampling fluctuation allowed at confidence level \(1-\delta\). In particular, decreasing \(\delta\) makes the guarantee more conservative. Since a population risk is at most \(1\), the right-hand side can always be capped at \(1\); if the displayed bound exceeds \(1\), it is valid but may not be informative.

Common Pitfall and Interpretation

A common mistake is to treat \(\beta\) as a high-probability bound on the generalization gap. That reasoning confuses the expected-gap result with concentration: \(|E[G]|\leq\beta\) controls an expectation, not the realized value of \(G(S)\) for most samples. The correction is to add a fluctuation term obtained from bounded differences, as in the theorem. Conversely, using only the fluctuation term and dropping \(\beta\) also needs justification; the theorem’s proof controls deviations around \(E[G]\), so the expected-gap contribution must be included.

The result concerns the generalization gap of the algorithm’s output, not a bound on excess risk relative to an optimal rule. Its usefulness depends on the size of both terms. If stability is weak, or the sample is small, the confidence allowance can be large—even when the observed training risk is small. For losses bounded by a constant other than \(1\), one can rescale the loss to \([0,1]\), apply the theorem, and scale the resulting risk bound back.