Expected Generalization Bounds from Uniform Stability

Why Stability Controls Expected Generalization

A learning algorithm can fit its training data closely without performing equally well on new observations. Stability gives one way to quantify how much the fitted predictor depends on any particular training observation: if replacing one observation barely changes the loss of the fitted predictor, then the expected population risk cannot greatly exceed the expected training risk.

The key feature of the expected bound is its dependence on sample size. A uniform stability parameter $\beta_n$ bounds the expected generalization gap by $\beta_n$, not by $n\beta_n$. The factor $1/n$ in the empirical risk averages $n$ leave-one-out comparisons, each controlled by the same stability bound.

Setup and Definition

Let $Z_1,\ldots,Z_n$ be independent observations with common distribution $P$, and write $S=(Z_1,\ldots,Z_n)$ for the training sample. A learning algorithm $A$ maps a sample to a predictor $A(S)$. For a loss function $\ell$, define the population risk and empirical risk by

R(A(S))=E_{Z\sim P}[\ell(A(S),Z)], \qquad \widehat R_S(A(S))=\frac{1}{n}\sum_{i=1}^n \ell(A(S),Z_i),

where the fresh observation $Z$ in the population risk is independent of $S$. We use the signed generalization gap $G(S)=R(A(S))-\widehat R_S(A(S))$. A positive value means the population risk exceeds the training risk.

Definition: The algorithm $A$ has uniform stability $\beta_n$ with respect to $\ell$ and $P$'s observation space if, for every pair of samples $s,s'$ that differ in at most one coordinate, and every observation $z$, $$ \left|\ell(A(s),z)-\ell(A(s'),z)\right|\leq \beta_n. $$ The bound is uniform over the changed coordinate, the values in the samples, and the evaluation point $z$. The parameter may depend on the sample size $n$.

This is a loss-based definition: it does not require the predictors themselves to be close in a particular metric. It also fixes the convention used here: neighboring samples have the same size and differ by replacement of one observation. With this convention, no extra factor of two is needed in the expected generalization bound.

The Leave-One-Out Representation

For each $i$, let $Z_i'$ be an independent draw from $P$, independent of the full sample, and let $S^{(i)}$ be the sample obtained by replacing $Z_i$ with $Z_i'$. The expected gap can be written as an average of loss changes evaluated at the original observation.

Proposition: Suppose the risks and expectations below are integrable. Then $$ E[G(S)] = \frac{1}{n}\sum_{i=1}^n E\!\left[\ell(A(S^{(i)}),Z_i)-\ell(A(S),Z_i)\right]. $$

Proof. Introduce an independent fresh observation $Z$ to express the expected population risk. Since $Z$ has the same distribution as each $Z_i'$,

E[R(A(S))] = \frac{1}{n}\sum_{i=1}^n E[\ell(A(S),Z_i')].

For each fixed $i$, the pair $(Z_i,Z_i')$ consists of two independent observations with the same distribution. Swapping their positions leaves the joint distribution unchanged. Under this swap, $S$ becomes $S^{(i)}$, and the evaluation point $Z_i'$ becomes $Z_i$. Therefore

E[\ell(A(S),Z_i')]=E[\ell(A(S^{(i)}),Z_i)].

Subtract the expected empirical risk, which is $\frac{1}{n}\sum_{i=1}^n E[\ell(A(S),Z_i)]$, from the expected population risk. Substitution of the preceding equality gives the proposition. $\square$

The replacement is important: $A(S)$ depends on $Z_i$, while $A(S^{(i)})$ does not. The identity compares the loss on $Z_i$ under these two predictors and thus makes the effect of that observation available to stability analysis.

Expected Generalization Bound

Theorem: Assume the observations are independent and identically distributed, the algorithm and loss are measurable, and $A$ has uniform stability $\beta_n<\infty$. If $\ell$ is bounded, these conditions ensure the needed integrability. More generally, it is enough to assume $$ E\left[|\ell(A(S),Z)|\right]<\infty, $$ where $S\sim P^n$ and $Z\sim P$ is independent of $S$. Then $$ \left|E\!\left[R(A(S))-\widehat R_S(A(S))\right]\right|\leq \beta_n. $$

Proof. Under the stated integrability condition, the population-risk expectation is integrable by Fubini's theorem. Also, $S^{(i)}$ has distribution $P^n$ and is independent of $Z_i$. Consequently, $\ell(A(S^{(i)}),Z_i)$ is integrable. Uniform stability gives \[ |\ell(A(S),Z_i)-\ell(A(S^{(i)}),Z_i)|\leq\beta_n, \] so the corresponding training loss is integrable as well. We can therefore apply the leave-one-out identity. By the triangle inequality and uniform stability,

\begin{aligned} \left|E[G(S)]\right| &\leq \frac{1}{n}\sum_{i=1}^n E\left[\left|\ell(A(S^{(i)}),Z_i)-\ell(A(S),Z_i)\right|\right]\\ &\leq \frac{1}{n}\sum_{i=1}^n \beta_n =\beta_n. \end{aligned}

There are $n$ terms, each bounded by $\beta_n$, and they are averaged rather than added without scaling. This accounts for the absence of an additional factor of $n$. $\square$

If the loss takes values in $[0,M]$, then the integrability condition is automatic. Boundedness of the loss is sufficient, but not necessary: an unbounded loss also works when the stated absolute-integrability condition holds.

How Sample Size Enters

The theorem gives a bound in terms of the algorithm's stability at the particular sample size. The theorem itself does not say how $\beta_n$ changes as $n$ grows; that must come from a separate analysis of the learning algorithm.

Corollary: Consider a sequence of algorithms with uniform stability $\beta_n$ and finite expected risks. If $\beta_n\leq Cn^{-\alpha}$ for constants $C>0$ and $\alpha>0$, then $$ \left|E[G(S)]\right|\leq Cn^{-\alpha}\xrightarrow[n\to\infty]{}0. $$ In particular, stability of order $1/n$ gives an expected generalization gap of order $1/n$.

Proof. Apply the theorem at sample size $n$ to obtain $|E[G(S)]|\leq\beta_n$. The assumed inequality then gives $|E[G(S)]|\leq Cn^{-\alpha}$. Since $C$ is fixed and $\alpha>0$, $Cn^{-\alpha}$ tends to zero as $n$ tends to infinity. $\square$

Worked Examples

Worked Example: Squared Loss for a Sample-Mean Predictor

Let $Z_1,\ldots,Z_n$ be Bernoulli observations with success probability $p$, and let the predictor be $h_S=\bar Z=n^{-1}\sum_{i=1}^n Z_i$. Use the squared loss $\ell(h,z)=(h-z)^2$. First bound the uniform stability and then calculate the expected gap.

If samples $s,s'$ differ in one coordinate, their sample means $a,b$ satisfy $|a-b|\leq 1/n$. For $a,b,z\in[0,1]$,

|(a-z)^2-(b-z)^2| =|a-b|\,|a+b-2z| \leq \frac{2}{n}.

Thus $\beta_n=2/n$ is a valid uniform stability bound. To calculate the actual expected gap, write $v=p(1-p)$. Conditional on $\bar Z$, a fresh $Z$ has mean $p$ and variance $v$, so

E[(\bar Z-Z)^2\mid \bar Z]=(\bar Z-p)^2+v.

Since $\operatorname{Var}(\bar Z)=v/n$ and $E[\bar Z]=p$, we have $E[(\bar Z-p)^2]=v/n$. Hence $E[R(h_S)]=v+v/n$. For the empirical risk,

E[\widehat R_S(h_S)] =p-E[\bar Z^2] =p-\left(p^2+\frac{v}{n}\right) =v-\frac{v}{n},

where we used $Z_i^2=Z_i$, so $n^{-1}\sum_i(Z_i-\bar Z)^2=\bar Z-\bar Z^2$. The expected gap is therefore $2v/n=2p(1-p)/n$, which is at most the stability bound $2/n$. For $p=1/2$ and $n=4$, the actual gap is $1/8$, while the bound is $1/2$.

Worked Example: A Classifier That Uses the First Label

Let the observations be independent binary labels with $P(Z_i=1)=p$. The algorithm predicts the first label $Z_1$ for every observation, and the loss is zero-one loss, $\ell(h,z)=\mathbf{1}\{h\neq z\}$. Replacing the first label can change the loss at any evaluation point by at most $1$; replacing any other label changes nothing. Thus the algorithm has uniform stability $\beta_n=1$.

For a fresh label, the prediction and the fresh label are independent Bernoulli variables. Their probability of disagreement is $p(1-p)+(1-p)p=2p(1-p)$, so $E[R(A(S))]=2p(1-p)$. The training loss on $Z_1$ is zero. For each $i\geq2$, the probability that $Z_i$ disagrees with $Z_1$ is also $2p(1-p)$. It follows that

E[\widehat R_S(A(S))] =\frac{n-1}{n}\,2p(1-p), \qquad E[G(S)]=\frac{2p(1-p)}{n}.

At $p=0.3$ and $n=5$, $2p(1-p)=0.42$, so the expected gap is $0.42/5=0.084$, below the stability bound $1$. This example shows that the theorem can be conservative: stability supplies a general upper bound, not necessarily the exact expected gap.

Worked Example: An Unbounded but Integrable Loss

Let $Z_i\sim N(0,1)$, use the predictor $a(S)=\mathbf{1}\{Z_1>0\}$, and define the loss $\ell(a,z)=z^2+a$. This loss is unbounded as a function of $z$, but it is nonnegative. Replacing one observation changes $a(S)$ by at most $1$, so the algorithm has uniform stability $\beta_n=1$.

A fresh $Z$ has $E[Z^2]=1$, and therefore $R(a(S))=1+a(S)$. The expected population risk is $1+P(Z_1>0)=3/2$. The empirical risk is \[ \widehat R_S(a(S))=\frac{1}{n}\sum_{i=1}^n Z_i^2+a(S). \] Its expectation is $1+1/2=3/2$, because each squared observation has expectation $1$. Thus $E[G(S)]=0$, which satisfies the bound $|E[G(S)]|\leq1$. Moreover, the loss is integrable since $E[Z^2+a(S)]=3/2<\infty$. Bounded loss is not required when integrability is verified.

Interpretation and a Common Pitfall

Uniform stability is useful because it turns a local perturbation property of the algorithm into a bound on the expected gap between two risks. If an algorithm's stability improves with sample size, the theorem immediately yields a corresponding expected generalization guarantee. The bound applies regardless of whether the predictor is obtained by minimizing empirical risk; the required property is stability, not a particular optimization procedure.

Common mistake: treating this as a bound on every sample's gap. The theorem bounds $|E[G(S)]|$, the absolute value of the expected signed gap. It does not, by itself, bound $E[|G(S)|]$, guarantee that the gap is small for every realized sample, or provide a high-probability statement. Those conclusions do not follow merely by moving the absolute value inside the expectation or by interpreting an expectation bound as a pointwise bound.

A second mistake is to multiply the stability parameter by $n$. The leave-one-out identity has $n$ terms, but also a factor $1/n$; applying the uniform bound to each term leaves $\beta_n$, not $n\beta_n$. Conversely, the theorem does not guarantee a useful rate unless the stability parameter itself decreases suitably with $n$.

Key takeaway: Under the stated measurability and integrability conditions, uniform stability $\beta_n$ implies $|E[R(A(S))-\widehat R_S(A(S))]|\leq\beta_n$. Bounded loss is one sufficient route to integrability, and the sample-size rate comes from how $\beta_n$ depends on $n$.

Check Your Understanding

Use the definitions and results above to answer these questions.

Under the replacement-based definition of uniform stability, what does the parameter $\beta_n$ bound?
Why does averaging the leave-one-out comparisons produce a bound of $\beta_n$, rather than $n\beta_n$?
What integrability condition allows the theorem to cover losses that are not bounded?
If $\beta_n=C/n$, what bound does the theorem give for the absolute expected signed gap?
Does the theorem imply that $E[|G(S)|]\leq\beta_n$? Explain why or why not.