Uniform and Hypothesis Stability

Why Compare Neighboring Samples?

A learning algorithm can respond differently to two training samples that differ in just one observation. Stability measures how much that change affects the loss on a test observation. The key distinction is whether the comparison must hold for every neighboring pair and test point, or only on average under a data distribution. Randomized learners add a further choice: compare losses for each realization of the algorithm’s randomness, or average over that randomness.

Assume the observations take values in a measurable space $\mathcal Z$, the hypotheses belong to $\mathcal H$, and the measurable loss satisfies $0\leq \ell(h,z)\leq 1$. A deterministic learner $A$ maps a sample of size $n$ to a hypothesis. A randomized learner can be represented as $A(S;R)$, where $R$ is its internal random seed. We use the same seed in both runs when making a coupled comparison; this convention will be made explicit where it matters.

Replace-One Uniform Stability

Two samples $s=(z_1,\ldots,z_n)$ and $s'=(z'_1,\ldots,z'_n)$ are neighbors if they agree in all but at most one coordinate. For a deterministic learner, compare the losses of its two fitted hypotheses at the same test point.

Definition: A deterministic learner has replace-one uniform stability at level $\beta$ if, for every pair of neighboring samples $s,s'$ and every $z\in\mathcal Z$, $$ \left|\ell(A(s),z)-\ell(A(s'),z)\right|\leq \beta. $$ The bound is pointwise in the samples and test point: it is not averaged over a data distribution.

For a randomized learner, a commonly used version averages the absolute loss change over a specified coupling of its internal randomness. With a shared seed $R$, its condition is

\sup_{\substack{s,s'\text{ neighboring}\\ z\in\mathcal Z}} E_R\left[\left|\ell(A(s;R),z)-\ell(A(s';R),z)\right|\right]\leq \beta.

This is pointwise in $s,s'$, and $z$, but expected over the algorithm’s randomness. A stronger pathwise condition requires the absolute difference to be at most $\beta$ for every seed $r$, as well as every neighboring pair and test point. The pathwise condition implies the expected-over-seeds condition, but not conversely.

One can also compare the mean losses under the two output distributions: $\left|E_R[\ell(A(s;R),z)]-E_R[\ell(A(s';R),z)]\right|$. This is no larger than the expected absolute loss difference, by the triangle inequality. Thus a bound on expected absolute change implies the same bound on mean-loss change; the converse need not hold.

Hypothesis Stability: Averaging Over the Data

Let $Z_1,\ldots,Z_n,Z_i'$ be independent observations from a distribution $P$, let $S=(Z_1,\ldots,Z_n)$, and let $S^{(i)}$ be the sample formed by replacing $Z_i$ with $Z_i'$. Let $Z\sim P$ be another independent observation. Hypothesis stability measures the loss change at $Z$, averaged over the random training sample, its replacement, and the test point.

Definition: The learner has expected absolute hypothesis stability at level $\eta_1$ if $$ E\left[\left|\ell(A(S),Z)-\ell(A(S^{(i)}),Z)\right|\right]\leq \eta_1 $$ for each $i$. For a randomized learner, include the specified joint randomness used for the two runs in this expectation.

A standard squared-difference formulation is also used: the learner has hypothesis stability at level $\eta_2$ if

E\left[\left(\ell(A(S),Z)-\ell(A(S^{(i)}),Z)\right)^2\right]\leq \eta_2^2

for each $i$. Stating which version is intended matters: $\eta_1$ bounds an expected absolute change, whereas $\eta_2$ bounds the square root of an expected squared change. Both are averages over data, unlike uniform stability. For a randomized learner, these definitions also average over its randomness under the chosen coupling.

What the Stability Notions Imply

Theorem: If a learner has replace-one uniform stability $\beta$, then it has expected absolute hypothesis stability at most $\beta$. If the loss takes values in $[0,1]$, its squared-difference stability satisfies $\eta_2\leq\sqrt{\beta}$. These conclusions hold for deterministic learners and for randomized learners whose uniform bound is on expected absolute loss change.

Proof. Fix $i$. In the deterministic case, for every realized sample $S$, replacement $Z_i'$, and test point $Z$, the samples $S$ and $S^{(i)}$ are neighbors. Uniform stability therefore gives

\left|\ell(A(S),Z)-\ell(A(S^{(i)}),Z)\right|\leq\beta.

Taking expectations over $S,Z_i'$, and $Z$ proves the absolute hypothesis stability bound. For a randomized learner, take the expectation over the specified shared randomness as well; the uniform expected-absolute bound applies for each fixed neighboring pair and test point, so averaging over those quantities again gives a bound of $\beta$.

Write $D$ for the loss difference in the squared-difference definition. Since both losses lie in $[0,1]$, $|D|\leq1$, and hence $D^2\leq|D|$. Consequently,

E[D^2]\leq E[|D|]\leq\beta, \qquad \sqrt{E[D^2]}\leq\sqrt{\beta}.

This proves both claims. $\square$

The reverse comparison does not follow from these arguments: a data-averaged expectation can be small even if a rare sample produces a large change. Also, if the loss is bounded by $M$ rather than $1$, the same proof gives $D^2\leq M|D|$, and therefore $\eta_2\leq\sqrt{M\beta}$.

Worked Examples

Worked Example: A First-Observation Classifier

Let $\mathcal Z=\{0,1\}$, let hypotheses be constant binary classifiers, and use $0$-$1$ loss. The learner returns the constant classifier with prediction $Z_1$, the first label in the sample. Suppose observations are Bernoulli with $P(Z_i=1)=p$.

Uniform stability. If two samples differ only in their first coordinate, their predictions can be different. For example, take first labels 0 and 1. At any test point $z\in\{0,1\}$, exactly one of the two constant classifiers makes an error. The absolute loss difference is therefore 1. Since $0$-$1$ loss differences cannot exceed 1, the uniform stability level is exactly $\beta=1$.

Expected absolute hypothesis stability. Replacing coordinate $i\neq1$ does not change the learner’s output. Replacing the first coordinate changes its output precisely when $Z_1\neq Z_1'$. By independence, $P(Z_1\neq Z_1')=p(1-p)+(1-p)p=2p(1-p)$. Whenever the predictions differ, their losses differ by 1 at every test point. Thus $\eta_1=2p(1-p)$. Because the loss difference is either 0 or 1, its square equals its absolute value, so $\eta_2=\sqrt{2p(1-p)}$. For $p=0.2$, these values are $0.32$ and $\sqrt{0.32}\approx0.566$, even though uniform stability is 1. The averaging is over the data distribution; it does not remove the worst-case neighboring pair from the uniform definition.

Worked Example: Randomized Stability Depends on the Comparison

Use $\mathcal Z=\{0,1\}$ and the two constant classifiers $h_0,h_1$ with $0$-$1$ loss. Define a randomized learner that outputs $h_1$ with probability $q(s)$, and $h_0$ otherwise. For neighboring samples whose first labels are 0 and 1, set $q(s)=0.2$ and $q(s')=0.7$, respectively.

Mean-loss comparison. At either test point, the two constant classifiers have complementary losses. The expected loss under $s$ is $0.2$ at $z=0$ and $0.8$ at $z=1$; under $s'$ it is $0.7$ at $z=0$ and $0.3$ at $z=1$. The absolute difference in mean loss is $0.5$ at either point.

Shared-seed expected absolute comparison. Let $U$ be uniform on $[0,1]$, and output $h_1$ when $U\leq q(s)$. The two outputs differ precisely when $0.2<U\leq0.7$, an event of probability $0.5$. On that event the absolute loss difference is 1; otherwise it is 0. Thus the expected absolute difference is $0.5$, matching the mean-loss comparison in this example.

Pathwise comparison. For seeds in $(0.2,0.7]$, the loss difference is 1. Therefore the pathwise uniform bound for this neighboring pair is 1, not $0.5$. Averaging over seeds permits a smaller stability level than demanding a bound for every seed.

Worked Example: Same Output Law, Different Couplings

Consider a data-independent randomized learner that outputs $h_0$ or $h_1$, each with probability $1/2$, at every sample. Compare two neighboring samples at a fixed test point $z$. The two hypotheses have different $0$-$1$ losses at $z$.

The marginal output distribution is identical for both samples, so their mean losses are equal and the mean-loss difference is 0. If both runs use the same fair coin, their hypotheses agree and the absolute loss difference is 0. If instead the two runs use independent fair coins, their hypotheses differ with probability $1/2$, so the expected absolute loss difference is $1/2$. The learner’s output laws alone determine the mean-loss comparison but do not specify the expected absolute comparison: that comparison also requires a coupling of the outputs.

Common Pitfall and Practical Interpretation

A common mistake is to treat “small expected change” as if it meant “small change for every neighboring sample.” For example, the first-observation classifier above has expected absolute hypothesis stability $0.32$ when $p=0.2$, but its uniform stability is still 1. The reasoning “the learner changes its output infrequently under $P$, so it is uniformly stable” is wrong: uniform stability examines all allowable samples, including ones that may be unlikely under $P$. The correction is to state which quantity is bounded and where its expectation is taken.

For randomized learners, another mistake is to report an expected absolute loss change without specifying how the two runs are coupled. Mean losses require only the two marginal output laws; absolute differences between random losses require a joint law. A shared random seed is a useful convention when the algorithm is naturally defined from a seed, but it should be stated rather than silently assumed. These distinctions identify what the stability claim actually controls without conflating a worst-case property with a distributional average.

Check Your Understanding

Answer each question by identifying whether the comparison is pointwise or averaged.

In the deterministic definition of uniform stability, which quantities are quantified over rather than averaged?
Why does a uniform bound $\beta$ imply expected absolute hypothesis stability at most $\beta$?
For a loss in $[0,1]$, explain why an expected absolute stability bound $\beta$ implies squared-difference stability at most $\sqrt{\beta}$.
In the randomized example with output probabilities $0.2$ and $0.7$, why is the pathwise bound larger than the shared-seed expected absolute bound?
What additional information is needed to define an expected absolute loss comparison for two randomized outputs when only their marginal distributions are given?