Algorithmic Stability

A catalogue of stabilities: uniform, hypothesis, leave-one-out and SGD stability each bound a different gap. Pick the variant matching the claim you want about test error.

Uniform stability caps every swap at 0.001 while SGD stability grows with steps, reaching 0.05 after 500 updates

Why Does This Exist?

Stability is not one definition. Uniform stability controls the worst test point under the worst swap and gives high-probability bounds. Hypothesis stability averages over the swapped example and suits squared error. Leave-one-out stability tracks retraining without each point and connects to cross-validation. SGD stability grows with steps and learning rate, explaining early stopping. Using the wrong variant proves the wrong gap.

This page separates the four so the companion page can use them. Stability-based generalization turns these definitions into test-error guarantees; here the job is precise meanings, standard rates and which algorithm earns which variant.

Prerequisite in one paragraph. You need training sets $S$ and $S^i$ differing in example $i$ , plus outputs $f_S$ and $f_{S^i}$ . Loss $\ell$ measures one prediction's error. Background is in sampling distributions and stochastic gradient descent variants.

Think of It Like This

Four ways to test a recipe

Uniform stability tastes every dish after swapping any ingredient: the worst change anywhere must be small. Hypothesis stability tastes the average dish after an average swap. Leave-one-out recooks the meal missing each ingredient in turn and compares. SGD stability watches the cook stir: each extra stir lets one ingredient spread further.

All four test insensitivity, but the strictness differs wildly. The uniform taste test fails recipes the average test passes, and the stir count explains why a briefly stirred soup is stable while an overnight stew is not.

Where the analogy stops: recipes mix ingredients physically while algorithms mix them through optimisation geometry. Only convexity or step limits make the stir count quantitative.

How It Actually Works

Uniform stability: $\sup_{S, S^i, z} |\ell(f_S, z) - \ell(f_{S^i}, z)| \le \beta$ , the worst swap and worst test point move loss by at most $\beta$ . Hypothesis stability takes expectation over the swap. Leave-one-out stability bounds $| \ell(f_S, z_i) - \ell(f_{S^i}, z_i)|$ on the held-out point. On-average stability bounds the mean over $i$ .

Standard rates: $\lambda$ -strongly convex regularised ERM has uniform $\beta \le 2G^2/\lambda n$ for $G$ -Lipschitz loss. SGD with $T$ steps, rate $\eta$ and smooth loss has uniform $\beta \lesssim \eta T/n$ up to logs. With $\eta = 0.01$ , $T = 500$ and $n = 2000$ , $\beta \approx 0.01 \times 500/2000 = 0.0025$ times smoothness constants near $20$ , giving about $0.05$ in the diagram. Halve the steps and stability halves; double the rate and it doubles.

Worked example

Ridge with $G = 1$ , $\lambda = 1$ , $n = 2000$ gives uniform $\beta = 0.001$ as on the companion page. Its leave-one-out error then estimates test error within $0.001$ in expectation, so $5$ -fold CV at $400$ per fold tracks truth tightly.

SGD on a smooth convex loss with $\eta = 0.01$ for $T = 500$ steps on the same $n$ gives $\beta \approx 0.05$ . Train at $0.15$ and the stability gap alone allows test up to $0.20$ . Train for $5{,}000$ steps and $\beta$ grows toward $0.5$ , vacuous: the bound itself recommends early stopping, which matches practice.

Watch Out For

Quoting uniform rates for a hypothesis-stable algorithm

kNN has good hypothesis stability but poor uniform stability: one swap can flip a neighbourhood and move one test loss a lot while the average barely moves. The uniform bound goes vacuous while the hypothesis bound stays meaningful. Demanding uniform stability everywhere rejects algorithms that generalise fine on average.

Fix: match variant to loss. Bounded regression can use hypothesis stability; high-probability claims need uniform.

Ignoring the step count in SGD stability

SGD stability grows with $T$ , so the bound at step $500$ says nothing about step $50{,}000$ . Reporting the early $\beta = 0.05$ beside final-epoch test accuracy borrows a guarantee the run already spent.

Fix: state $(T, \eta, n)$ with every SGD stability number. No steps, no claim.

The Quick Version

Uniform caps the worst swap on the worst test point; hypothesis and leave-one-out average instead.
Strongly convex ERM gets uniform $2G^2/\lambda n$ , which is 0.001 for ridge at 2000 samples.
SGD gets about $\eta T/n$ , which is 0.05 at 500 steps of 0.01 on 2000 samples.
Early stopping is a stability decision: fewer steps mean smaller $\beta$ .
Always state steps and variant; uniform, average and SGD numbers are not interchangeable.