Distributional Stability for Randomized Learners

Why Compare Output Distributions?

A randomized learner can return different hypotheses when run twice on the same data. Comparing two particular outputs may therefore confuse the learner's built-in randomness with the effect of changing one observation. Distributional stability instead compares the laws of the outputs: if two data sets differ in one observation, how much can the learner's output distribution change?

This distinction is useful for randomized algorithms whose randomness is part of their design. The relevant question is not whether every pair of runs produces nearly identical hypotheses. It is whether neighboring data sets lead to similar output distributions, so that bounded losses have similar expectations. That comparison leads directly to a bound on expected generalization error.

Definition and a Loss Comparison

Let $Z_1,\ldots,Z_n$ be independent observations from a distribution $P$ on a measurable data space $\mathcal Z$, and write $S=(Z_1,\ldots,Z_n)$. A randomized learner with output space $\mathcal H$ is described by a probability kernel $A$: for each data set $s$, $A(s,\cdot)$ is the probability distribution of the learner's output. Assume the relevant loss and kernel integrals are measurable. Two data sets are neighbors if they agree in all but at most one coordinate.

Definition: For probability measures $Q,Q'$ on $\mathcal H$, their total variation distance is $$ \operatorname{TV}(Q,Q')=\sup_{B} |Q(B)-Q'(B)|, $$ where the supremum is over measurable subsets $B$ of $\mathcal H$. The learner $A$ has replace-one distributional stability at level $\beta$ if $$ \sup_{s,s'\ \mathrm{neighbors}}\operatorname{TV}\bigl(A(s,\cdot),A(s',\cdot)\bigr)\leq \beta. $$

The supremum is over data sets in the domain under consideration, not just over typical samples. Total variation lies between zero and one. It is zero for identical output laws and one for mutually singular output laws.

The connection to loss follows from a basic property of total variation. For any measurable function $g:\mathcal H\to[0,1]$,

Lemma: For probability measures $Q,Q'$ and measurable $g:\mathcal H\to[0,1]$, $$ \left|\int g\,dQ-\int g\,dQ'\right|\leq \operatorname{TV}(Q,Q'). $$ If $g$ takes values in $[a,b]$, the right side can be replaced by $(b-a)\operatorname{TV}(Q,Q')$.

To prove the lemma for $g\in[0,1]$, use the pointwise identity $g(h)=\int_0^1 \mathbf{1}\{g(h)>t\}\,dt$. Tonelli's theorem applies because the integrand is nonnegative and measurable. Therefore,

\int g\,dQ-\int g\,dQ' =\int_0^1\bigl[Q\{g>t\}-Q'\{g>t\}\bigr]\,dt.

Each integrand has absolute value at most $\operatorname{TV}(Q,Q')$. Taking absolute values and integrating over an interval of length one proves the claim. For $g\in[a,b]$ with $a<b$, apply the result to $(g-a)/(b-a)$; the constant $a$ cancels because both measures have total mass one. If $a=b$, both integrals are equal. $\square$

In particular, if the loss $\ell(h,z)$ lies in $[0,1]$, then for every fixed observation $z$, changing the learner's output law from $Q$ to $Q'$ changes expected loss by at most $\operatorname{TV}(Q,Q')$. For a loss in $[a,b]$, the bound is multiplied by its range $b-a$.

Worked Example: Comparing Two Bernoulli Output Laws

Suppose the learner outputs one of two hypotheses, $h_0$ and $h_1$. On a fixed observation $z$, let $\ell(h_0,z)=0$ and $\ell(h_1,z)=1$. For two neighboring data sets, suppose the probability of outputting $h_1$ is $0.2$ for the first and $0.5$ for the second.

The two output laws are Bernoulli distributions on $\{h_0,h_1\}$. Their total variation distance is the largest difference in probability over subsets. The singleton $\{h_1\}$ gives difference $0.5-0.2=0.3$; the singleton $\{h_0\}$ gives the same absolute difference, and the empty and full sets give zero. Thus the distance is $0.3$.

The expected losses are $0.2$ and $0.5$, respectively, because only $h_1$ has loss one. Their difference is $0.3$, exactly the total variation distance in this example. This verifies both the comparison and the fact that its constant cannot be reduced for all $[0,1]$-valued losses.

Expected Generalization Bound

For a fixed hypothesis $h$, define its population risk by $R(h)=E_{Z\sim P}[\ell(h,Z)]$, and define the empirical risk on $S$ by $\widehat R_S(h)=n^{-1}\sum_{i=1}^n\ell(h,Z_i)$. Suppose $0\leq \ell(h,z)\leq 1$ for every $h,z$, and assume the expectations below exist. The learner's expected generalization gap includes expectation over both the sample and its randomized output.

Theorem: If $A$ has replace-one distributional stability at level $\beta$, then $$ \left|E_{S}\,E_{H\sim A(S)} \left[R(H)-\widehat R_S(H)\right]\right|\leq \beta. $$ For a loss in $[a,b]$, the upper bound is $(b-a)\beta$.

Proof. Let $Z_i'$ be an independent draw from $P$, independent of $S$, and let $S^{(i)}$ be $S$ with coordinate $i$ replaced by $Z_i'$. For each $i$, the data set $S^{(i)}$ has distribution $P^n$ and is independent of $Z_i$. Consequently,

E_S E_{H\sim A(S)}[R(H)] = E_{S,Z_i'}E_{H\sim A(S^{(i)})}[\ell(H,Z_i)].

Indeed, conditional on $S^{(i)}$, the independent observation $Z_i$ has distribution $P$, so the conditional expected loss on the right is $R(H)$; averaging over $S^{(i)}$ gives the left side because $S^{(i)}$ has the same distribution as $S$. Subtract the empirical-risk term and average over $i$. The expected gap is

\frac{1}{n}\sum_{i=1}^n E_{S,Z_i'} \left[ \int \ell(h,Z_i)\,A(S^{(i)},dh) - \int \ell(h,Z_i)\,A(S,dh) \right].

For each fixed $S,Z_i'$, the data sets $S$ and $S^{(i)}$ are neighbors. For each fixed $Z_i$, the loss as a function of $h$ takes values in $[0,1]$. The lemma therefore bounds the absolute value of the bracket by $\operatorname{TV}(A(S^{(i)},\cdot),A(S,\cdot))\leq\beta$. The absolute value of the average is at most the average of the absolute values, hence at most $\beta$. For a loss in $[a,b]$, use the range-scaled version of the lemma. $\square$

The conclusion is an expected generalization bound. It does not assert that every sample or every realized output has a small gap. It controls the signed average gap over repeated samples and learner randomness; taking an absolute value outside that expectation does not give a bound on the expected absolute gap.

Worked Example: A Count-Based Randomized Classifier

Let $Z_i\in\{0,1\}$ be independent Bernoulli observations with $P(Z_i=1)=1/2$. The learner outputs $h_1$ with probability $k/n$, where $k=\sum_{i=1}^n Z_i$, and otherwise outputs $h_0$. Use the loss $\ell(h,z)=\mathbf{1}\{h\neq z\}$.

Replacing one binary observation changes $k$ by at most one. Thus the probability of outputting $h_1$ changes by at most $1/n$. For Bernoulli laws, total variation is the absolute difference in the probabilities of $h_1$, so this learner has stability $\beta=1/n$.

We can also calculate its expected generalization gap. Write $q=k/n$. Each constant classifier has population risk $1/2$, so the randomized learner's population risk is $1/2$. Its empirical risk is $k/n=q$ under $h_0$ and $(n-k)/n=1-q$ under $h_1$. Averaging over the learner's output gives

E[\widehat R_S(H)\mid S]=(1-q)q+q(1-q)=2q(1-q).

Since $k\sim\operatorname{Binomial}(n,1/2)$, $E[q]=1/2$ and $\operatorname{Var}(q)=1/(4n)$. Hence $E[q^2]=\operatorname{Var}(q)+(E[q])^2=1/(4n)+1/4$, and

E[R(H)-\widehat R_S(H)] =\frac12-2E[q(1-q)] =\frac12-2\left(\frac12-E[q^2]\right) =\frac{1}{2n}.

The exact gap $1/(2n)$ is no greater than the distributional-stability bound $1/n$, as the theorem requires.

Stability from Overlapping Gaussian Outputs

Randomization can make output laws overlap even when their means respond to the data. The following calculation illustrates how that overlap affects total variation. Let $\Phi$ denote the standard normal distribution function.

Worked Example: A Gaussian Output Based on the Sample Mean

Suppose the data lie in $[0,1]$. The learner outputs a real number drawn from $N(\overline Z_S,\sigma^2)$, where $\overline Z_S=n^{-1}\sum_{i=1}^n Z_i$ and $\sigma>0$. For neighboring data sets, their sample means differ by some $\delta$ with $|\delta|\leq 1/n$. The output laws are normal distributions with equal variance and means separated by $|\delta|$.

For $\delta\geq0$, their densities cross at the midpoint $\delta/2$. The distribution with mean $\delta$ has the larger density to the right of this point, so total variation is the difference in right-tail probabilities:

\operatorname{TV}\bigl(N(0,\sigma^2),N(\delta,\sigma^2)\bigr) = P_{N(\delta,\sigma^2)}(X\geq\delta/2) - P_{N(0,\sigma^2)}(X\geq\delta/2) = 2\Phi\left(\frac{\delta}{2\sigma}\right)-1.

For negative $\delta$, symmetry gives the same expression with $|\delta|$. Since $\Phi$ is increasing, the learner's replace-one stability is at most $2\Phi(1/(2n\sigma))-1$. Thus every loss bounded in $[0,1]$ has expected generalization gap at most this quantity. Increasing $\sigma$ makes the neighboring output laws overlap more and reduces this bound; the formula does not say that their means become equal.

Interpretation and a Common Pitfall

Distributional stability concerns the entire probability law produced by the learner, not the distance between two sampled outputs. For example, if an algorithm outputs a fresh fair coin result independently of the data, its output law is unchanged across data sets, so its distributional stability is zero. Its realized outputs can nevertheless differ between two runs. Conversely, a deterministic learner that selects different hypotheses on neighboring data sets has point-mass output laws; if the hypotheses differ, those laws have total variation one.

Common mistake: “The learner is randomized, and two runs gave different hypotheses, so it is unstable.” This compares realized outputs rather than output distributions and ignores randomness that would remain even with the data fixed. The correction is to define the two conditional output laws, one for each neighboring data set, and compare those laws using total variation. The generalization theorem then follows because bounded loss is a bounded function of the output.

Key takeaway: Replace-one total variation stability at level $\beta$ limits the change in expected bounded loss under every one-coordinate data change. For losses in $[0,1]$, the same $\beta$ bounds the absolute expected generalization gap.

Check Your Understanding

Try these questions using the definitions and results above.

For two Bernoulli output laws with probabilities $p$ and $q$ of outputting $h_1$, what is their total variation distance?
Why must the replacement observation $Z_i'$ be independent of $Z_i$ in the proof of the expected generalization bound?
If the loss takes values in $[-2,3]$ and distributional stability is $\beta$, what bound does the theorem give?
For the count-based classifier, verify that replacing one binary observation changes its output probability by at most $1/n$.
Explain why a zero expected generalization gap does not by itself imply that every realized output has zero generalization gap.