advanced29 min studyLesson 756 in Mathematics

Algorithmic stability and generalization

Bound the change caused by replacing one observation and distinguish signed expected gaps from high probability control.

Before you begin

On this page

The question for today

What you’ll understand

State replacement uniform stability for bounded losses and an explicit algorithm.
Derive an expected signed generalization-gap bound by replacing one training example.
Use bounded differences to add a confidence penalty without confusing deletion and replacement constants.

A hypothesis class can be large while a particular algorithm changes little when one example is replaced. Stability studies that algorithm-dependent behavior rather than every function in the class. The definition’s quantifiers and neighboring-sample convention matter. An expected signed generalization bound is also weaker than a bound on its absolute value or a high-probability event, so those conclusions must be kept separate.

Choose a neighboring-sample convention

Let A be a measurable deterministic learning rule on samples of size n, and assume losses lie in[0,1]. Replacement uniform stability with parameter beta means that for every pair of size-n samples differing in at most one example, and every test point z, their output losses differ by at most beta. This is a worst-case requirement over samples and test points, not an empirical average of changes on a validation set. Any dependence of beta on n should be made explicit.

Deletion stability compares a size-n output with a size-(n−1) output and is a different definition. Passing through the common deleted sample can turn a deletion bound beta into a replacement bound 2beta. We use replacement stability throughout this lesson, so no hidden factor of two should be imported from a deletion-based source. Randomized algorithms require a stated convention for averaging over or coupling their randomness; keeping A deterministic makes the replace-one proof and its conditioning transparent.

\sup_z|\ell(A(S),z)-\ell(A(S'),z)|\le\beta_n\qquad\text{whenever }S,S'\text{ differ in one coordinate}

This is replacement uniform stability for a measurable deterministic algorithm and losses in[0,1].↔ Scroll wide equations horizontally.

A ghost example controls the signed average gap

Define the generalization gap as population risk of the trained rule minus its training empirical risk. Replace one training example by an independent fresh example. By exchangeability, evaluating the replaced-sample output at the removed observation has the same average as evaluating the original output at an independent test point. Uniform stability bounds the loss change when the sample is restored. Averaging over sample coordinates gives absolute value of the expected signed gap at most beta. It does not directly give expected absolute gap at most beta.

For high probability, view the signed gap itself as a function of n independent observations. Replacing one observation changes its population-risk part by at most beta. In the empirical-risk part, the other n−1 loss terms change by at most beta each and the changed term by at most one. Thus a valid coordinate sensitivity is 2beta+1/n. Applying bounded differences and then the expected-gap upper bound produces the displayed one-sided certificate; its larger confidence penalty can dominate a very small mean gap.

|\mathbb E_S g(S)|\le\beta_n,\qquad g(S)\le\beta_n+\left(2\beta_n+\frac1n\right)\sqrt{\frac n2\log\frac1\delta}\quad\text{with probability at least }1-\delta

Here g(S)=R_P(A(S))−Rhat_S(A(S)); iid examples, bounded loss and replacement uniform stability are assumed.↔ Scroll wide equations horizontally.

Regularization and averaging can stabilize different ways

A regularized strongly convex empirical objective often controls the distance between solutions when a loss term is replaced; a Lipschitz loss then turns that parameter bound into a stability bound. This requires the stated curvature, regularization convention and Lipschitz domain. An optimization routine’s numerical convergence alone is not stability with respect to the dataset. Conversely, a simple sample mean is stable without solving a complicated optimization problem, because one bounded observation has only a one-over-n influence on the average.

For labels in[0,1], predict their sample mean and use squared loss on[0,1]. Replacing one label changes the prediction by at most 1/n. The squared loss is 2-Lipschitz in its prediction on this interval, giving replacement stability at most 2/n. For Bernoulli labels the signed expected gap can be computed exactly and is much smaller than this worst-case certificate. This example also shows why stability is a generalization tool, not a guarantee of a small population risk or a rich enough prediction class.

Work it through

A stable mean predictor still has sampling noise

Take one hundred iid Bernoulli(1/2) labels and predict their sample mean under squared loss. Compute expected population risk, expected training risk and the signed expected gap; verify a concrete replacement.

The label variance is 1/4 and the sample mean variance is 1/400. A fresh independent label gives expected population squared loss $1/4+1/400=0.2525$ .
The training average squared deviation from the sample mean has expectation $(1-1/100)/4=0.2475$ . The signed expected generalization gap is therefore 0.005, below the replacement stability bound 2/100=0.02.
For a sample with fifty zeros and fifty ones, replace one zero by one. The prediction moves from 0.50 to 0.51; at test label zero the loss moves from 0.25 to 0.2601, a change 0.0101, within 0.02.

The result

The expected signed gap is 0.005, while 0.02 is a worst-case replacement-loss certificate. Neither quantity is an automatic pointwise or absolute-gap guarantee.

The living notebook

Explore the model

Interactive lab

Interactive lab · sampling

An empirical mean is stable and still random

Pause and Reset, then set p = 0.50 and n = 100. Predict the sample-mean variance 0.25/100=0.0025. Reset and set both p = 0.50 and n = 50 to double that variance. For bounded labels, replacing one observation moves the mean by at most 1/n; this is a deterministic sensitivity statement rather than the displayed sampling variance. Playback highlights exact binomial outcomes and does not replace a dataset entry.

Exact binomial massNormal interval massHighlighted outcome / mean

Mean sample proportion: 0.5
Sample-mean variance: 0.0125
Uniform CDF error bound: ≤ 0.1062

Success probability p0.5Independent samples n20

t = 0 s

Exact binomial masses for the mean of n independent Bernoulli trials, compared with normal mass between adjacent half-count boundaries; normal tails outside the finite support remain outside the bars. Playback highlights outcomes, not random samples. The Berry–Esseen bound applies to standardized CDFs, not individual bars or continuity-corrected errors. At p = 0 or 1, normal comparison and that bound are disabled. Normal-CDF evaluation uses a numerical approximation with absolute error below 7.5×10⁻⁸ (at most 1.5×10⁻⁷ per interval, before rounding). Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.

Look forSmall replace-one sensitivity and nonzero sampling variability can coexist.

Pause & reason

Check your understanding

Interactive checks need JavaScript. You can still read the explanation.

Read the checkpoint explanation

The ghost-sample argument controls |E g|. Absolute deviations, individual samples and the size of the population risk need additional arguments.

Your turn

Try it yourself

For n=1000, replacement stability beta=0.0001 and delta=0.05, evaluate the displayed one-sided high-probability gap bound. Compare it with the expected signed-gap certificate.

Take a moment to make a prediction or work it out on paper. Open a hint when you need one.

Give me a hint

The coordinate sensitivity is 2beta+1/n=0.0012. Keep the square-root confidence factor separate from beta.

Compare with the solution

The bound is $0.0001+0.0012\sqrt{500\log20}\approx0.0465427$ . The expected signed-gap certificate is only $|\mathbb E g|\le0.0001$ . The larger 0.0465 quantity applies to a one-sided sample event with confidence at least 0.95; it does not estimate the mean gap. A lower-tail counterpart could be derived separately, and a two-sided certificate would need its own allocation of failure probability. Replacing this calculation with a deletion-stability constant without converting conventions could change its coefficients and invalidate the stated number.

Keep the idea

Take it with you

Replacement and deletion stability have different neighboring-sample definitions.
Uniform stability controls the expected signed gap, not automatically the expected absolute gap.
High-probability stability bounds add a separate concentration penalty under iid bounded-loss assumptions.

Read further

Original sources and deeper explanations to follow at your own pace.

Optional progress, saved in this browser when available. Revisit any lesson at any time.

Lesson not marked complete.