On-Average Stability and Expected Risk

Why Average Stability Gives an Expected-Risk Bound

A learning rule can react sharply to a small number of unusual data sets and still behave stably on the data sets that are typical under the sampling distribution. A worst-case stability bound records the largest possible change in loss over all neighboring data sets. An on-average bound instead measures the expected change under the data-generating distribution. This distinction matters when the exceptional data sets are possible but rare.

The target here is the expected generalization gap: the difference between a learner’s expected risk on a new observation and its empirical risk on its training sample. We will connect that gap exactly to changes caused by replacing one training observation, then bound it using an average of those changes.

Setup and Definition

Let $Z_1,\ldots,Z_n$ be independent and identically distributed observations from a distribution $P$, and write $S=(Z_1,\ldots,Z_n)$. A learning algorithm $A$ maps a sample to a predictor $A(S)$. For a predictor $h$, let $\ell(h,z)$ be its loss at observation $z$. Assume the loss is measurable and takes values in $[0,1]$; this boundedness ensures all expectations below exist. Define the population risk and empirical risk by

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

For each index $i$, let $Z_i'$ be an independent draw from $P$, also independent of $S$, and let $S^{(i)}$ be the sample obtained by replacing $Z_i$ with $Z_i'$. In the definition below, the loss is evaluated at the replacement observation $Z_i'$. This pairing is essential to the exact identity proved next.

Definition: The on-average replace-one stability of $A$, for loss $\ell$ and distribution $P$, is $$ \beta_{\mathrm{on}}(A) = \frac{1}{n}\sum_{i=1}^n E\left[ \left| \ell(A(S),Z_i')-\ell(A(S^{(i)}),Z_i') \right| \right]. $$ The expectation is over the sample and the independent replacement observations. Stability is therefore averaged over the index, the sampled data, and the replacement, rather than maximized over all possible neighboring samples.

The replacement observation is part of $S^{(i)}$, and so is not an independent test observation relative to that modified sample. This is intentional: it is the evaluation point that makes the replace-one identity exact. A different stability definition that evaluates both predictors at a fresh independent test point is not interchangeable with this one without an additional argument.

Worked Example: A Learner That Memorizes One Binary Observation

Let $n=1$, let $Z$ be Bernoulli with $P(Z=1)=p$, and let the learner predict the observed value: $A(Z)=Z$. Use binary classification loss $\ell(h,z)=\mathbf{1}\{h\ne z\}$, where the prediction $h$ is either 0 or 1.

After replacement, the learner predicts $Z'$, so its loss at the replacement observation $Z'$ is zero. The original learner’s loss at $Z'$ is one exactly when $Z\ne Z'$. Thus $$ \beta_{\mathrm{on}}(A)=P(Z\ne Z') =p(1-p)+(1-p)p=2p(1-p). $$ The population risk of either constant prediction is the probability that it disagrees with a fresh Bernoulli observation. Conditional on the training observation, that risk is $p$ if $Z=0$ and $1-p$ if $Z=1$. Its expectation is $$ (1-p)p+p(1-p)=2p(1-p). $$ The empirical risk is always zero because the learner predicts its only training observation. The expected generalization gap is therefore $2p(1-p)$, exactly the on-average stability in this example.

The Replace-One Identity

Write the expected generalization gap as the expected population risk minus the expected empirical risk. Since a fresh observation $Z$ is independent of $S$, conditioning on $S$ gives $E[R(A(S))]=E[\ell(A(S),Z)]$. Exchangeability of the sample coordinates then yields the following identity.

Theorem: Under the setup above, $$ E[R(A(S))-R_S(A(S))] = \frac{1}{n}\sum_{i=1}^n E\left[ \ell(A(S),Z_i')-\ell(A(S^{(i)}),Z_i') \right]. $$

Proof. By the definition of population and empirical risk, and because $Z_i'$ has distribution $P$ and is independent of $S$,

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

For each fixed $i$, the pair $(S^{(i)},Z_i')$ has the same distribution as $(S,Z_i)$: the $i$th coordinate of $S^{(i)}$ is $Z_i'$, and all its coordinates are independent draws from $P$. Consequently, $$ E[\ell(A(S),Z_i)] = E[\ell(A(S^{(i)}),Z_i')]. $$ Substitute this equality into each summand of the previous display. The stated identity follows. $\square$

The identity is signed: positive and negative changes in loss can cancel. Taking absolute values term by term gives an immediate bound that does not rely on such cancellation.

Corollary: The absolute expected generalization gap is bounded by on-average replace-one stability: $$ \left|E[R(A(S))-R_S(A(S))]\right| \le \beta_{\mathrm{on}}(A). $$ In particular, $$ E[R(A(S))] \le E[R_S(A(S))]+\beta_{\mathrm{on}}(A). $$ Proof. Apply the triangle inequality to the replace-one identity: $$ \left| \frac{1}{n}\sum_{i=1}^n E[\Delta_i] \right| \le \frac{1}{n}\sum_{i=1}^n E[|\Delta_i|] =\beta_{\mathrm{on}}(A), $$ where $\Delta_i=\ell(A(S),Z_i')-\ell(A(S^{(i)}),Z_i')$. The one-sided inequality follows from $x\le |x|$. $\square$

This is a bound on the expected risk gap. It does not by itself say that the realized gap for a particular sample is small, nor does it give a probability statement about that gap. Such conclusions require additional results and assumptions.

Worked Example: A First-Observation Classifier

Let $Z_1,Z_2$ be independent Bernoulli observations with success probability $p$. The learner predicts $A(S)=Z_1$ and uses binary classification loss $\ell(h,z)=\mathbf{1}\{h\ne z\}$. Replacing the second observation does not change the predictor, so its contribution to on-average stability is zero.

Replacing the first observation changes the prediction exactly when $Z_1\ne Z_1'$. At the replacement point $Z_1'$, the original prediction then makes an error and the replacement predictor makes none. Hence the expected absolute loss change for index 1 is $2p(1-p)$, and $$ \beta_{\mathrm{on}}(A) =\frac{1}{2}\left(2p(1-p)+0\right) =p(1-p). $$ We can check the expected risk gap directly. The learner’s expected population risk is $P(Z_1\ne Z)=2p(1-p)$, where $Z$ is a fresh draw. Its first training loss is zero, while its second training loss has expectation $P(Z_1\ne Z_2)=2p(1-p)$. Thus its expected empirical risk is $p(1-p)$, and the gap is $$ 2p(1-p)-p(1-p)=p(1-p)=\beta_{\mathrm{on}}(A). $$ Only one of the two sample positions affects this learner, so averaging over positions halves the one-position sensitivity.

Why the Average Can Be Smaller Than a Worst-Case Bound

Uniform stability takes a supremum over every pair of neighboring samples and every evaluation point. For losses in $[0,1]$, a uniform stability bound $\beta_{\mathrm{unif}}$ means that the loss changes by at most $\beta_{\mathrm{unif}}$ whenever one observation is replaced, regardless of which sample occurs or where the loss is evaluated. Since every realization in the definition of $\beta_{\mathrm{on}}$ is among the cases controlled by that supremum,

\beta_{\mathrm{on}}(A)\le \beta_{\mathrm{unif}}(A).

The inequality can be strict: the supremum may be attained only on a small-probability event, while the on-average quantity weights changes by their actual sampling probabilities. In either case, the expected generalization bound follows from the on-average quantity itself, not from a requirement that every data set be stable.

Worked Example: A Rare Trigger With a Large Worst-Case Change

Let $n=2$, let $Z_1,Z_2$ be Bernoulli with success probability $p$, and let the learner predict 1 if at least one training observation is 1; otherwise it predicts 0. Again use binary classification loss. A replacement can change the prediction only if the other observation is 0 and the old and replacement observations differ.

For a fixed index, the other observation is 0 with probability $1-p$. Conditional on this, the two replacement values differ with probability $2p(1-p)$. Whenever the prediction changes, the loss difference at the replacement observation is exactly 1: if the replacement is 1, the new learner predicts 1 and the old one predicts 0; if the replacement is 0, the old learner predicts 1 and the new one predicts 0. Thus the expected absolute change for each index, and hence the average stability, is $$ \beta_{\mathrm{on}}(A)=2p(1-p)^2. $$ For $p=0.1$, this is $2(0.1)(0.9)^2=0.162$. The uniform bound is 1, because a neighboring pair can change the prediction and produce a unit loss difference. Such a pair exists, for example, when the other observation is 0 and the replaced values are 0 and 1.

For a direct check of the expected gap, let $K=Z_1+Z_2$. The probability that the learner predicts 1 is $q=P(K\ge1)=2p-p^2$. Its expected population risk is $q(1-p)+(1-q)p=p+q(1-2p)$. Its empirical risk is $1/2$ when $K=1$, and zero when $K=0$ or $K=2$, so its expected empirical risk is $p(1-p)$. Subtracting gives $$ p+(2p-p^2)(1-2p)-p(1-p)=2p(1-p)^2. $$ The average bound is exact here, while the worst-case stability bound remains 1.

Common Pitfall and Interpretation

A frequent mistake is to define the replacement experiment but evaluate both predictors at a fresh independent test point, then apply the replace-one identity as though that were the same quantity. In the identity, the modified learner $A(S^{(i)})$ is paired with the replacement observation $Z_i'$, which is part of its training sample. The event and loss change in that pairing need not have the same expectation as a comparison at an independent test point. Always match the stability definition to the identity being used.

Another mistake is to claim that average stability is always small merely because it is an average. Its value depends on the data distribution, the learning rule, the loss, and the sample size. Rare but influential events can still contribute substantially if their loss change is large or their probability is not very small. Conversely, a large uniform bound alone may be uninformative when the configurations attaining it have negligible probability.

Key takeaway: On-average replace-one stability averages the absolute loss change caused by replacing one observation, evaluated at that replacement. The replace-one identity converts the signed changes into the expected generalization gap; the triangle inequality then bounds its absolute value by $\beta_{\mathrm{on}}(A)$. Because it averages over the sampling distribution, this guarantee can be sharper than a worst-case uniform stability bound.

Check Your Understanding

Answer each question using the definitions and identity above.

In the replace-one identity, why does $(S^{(i)},Z_i')$ have the same distribution as $(S,Z_i)$?
For the first-observation classifier with two Bernoulli training observations, why does replacing the second observation contribute zero stability?
What does the triangle inequality add when moving from the signed replace-one identity to an absolute generalization bound?
Why can on-average stability be strictly smaller than uniform stability?
In the rare-trigger example, which event must occur for replacing one observation to change the learner’s prediction?