Algorithmic Stability

A stable algorithm barely changes its predictions when one training example is swapped. That insensitivity is what lets test error track training error, with tighter numbers for ridge and early-stopped SGD.

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

Why Does This Exist?

Test error is what you pay and training error is what you see, and the gap between them needs a guarantee. On 2,000 samples a ridge gap of $0.001$ means cross-validation tracks truth tightly, while an SGD gap of $0.05$ after 500 steps means early stopping is not folklore but arithmetic. Without a stability number you cannot tell which regime you are in.

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 swap 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, which explains early stopping.

This page separates the four variants with their standard rates. Sampling background lives in sampling distributions, resampling in bootstrap and resampling, the SGD loop in stochastic gradient descent variants, and neighbouring guarantees in bias variance decomposition and PAC Bayes bounds.

The one idea you need first

You need training sets $S$ and $S^i$ differing in example $i$ , where $S$ is the full sample and $S^i$ is $S$ with example $i$ swapped, plus outputs $f_S$ and $f_{S^i}$ , where $f$ is the trained predictor. Loss $\ell$ measures one prediction 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, where each extra stir lets one ingredient spread further.

All four test insensitivity, but 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 it stops: recipes mix physically while algorithms mix through optimisation geometry. Only convexity or step limits make the stir count quantitative.

How It Actually Works

Uniform stability requires $\sup_{S, S^i, z} \lvert \ell(f_S, z) - \ell(f_{S^i}, z) \rvert \le \beta$ , where the supremum runs over all datasets, swaps, and test points $z$ , and $\beta$ is the stability number. Hypothesis stability takes expectation over the swap. Leave-one-out stability bounds $\lvert \ell(f_S, z_i) - \ell(f_{S^i}, z_i) \rvert$ on the held-out point $z_i$ . On-average stability bounds the mean over $i$ .

Standard rates, where $G$ is the Lipschitz constant bounding loss slope, $\lambda$ is the strong-convexity from regularization, $n$ is sample size, $\eta$ is learning rate, and $T$ is step count: $\lambda$ -strongly convex regularised ERM has uniform $\beta \le 2G^2/\lambda n$ , and smooth convex SGD has uniform $\beta \lesssim 2L^2\eta T/n$ with $L$ the Lipschitz constant, up to logs. Halve the steps and stability halves, and double the rate and it doubles.

Worked example

Ridge with $G = 1$ , $\lambda = 1$ , and $n = 2000$ gives uniform $\beta = 2 \times 1/(1 \times 2000) = 0.001$ . Its leave-one-out error then estimates test error within $0.001$ in expectation, so $5$ -fold cross-validation at $400$ per fold tracks truth tightly. Training at $0.150$ allows test up to about $0.151$ from stability alone.

SGD on a smooth convex loss with $L = 1$ , $\eta = 0.01$ , $T = 500$ , and $n = 200$ gives $\beta \le 2 \times 0.01 \times 500/200 = 10/200 = 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$ , which is vacuous: the bound itself recommends early stopping, which matches practice.

Code

The point is the check: the same $0.001$ and $0.05$ numbers, in plain Python.

1def beta_ridge(G: float, lam: float, n: int) -> float:2    return 2.0 * G * G / (lam * n)3
4
5def beta_sgd(eta: float, T: int, n: int) -> float:6    return 2.0 * eta * T / n7
8
9b_ridge: float = beta_ridge(1.0, 1.0, 2000)10b_sgd: float = beta_sgd(0.01, 500, 200)11print((round(b_ridge, 4), round(b_sgd, 4)))  # -> (0.001, 0.05)12print(round(0.15 + b_sgd, 2))  # -> 0.2

Ridge holds every swap to $0.001$ on $2{,}000$ samples, while $500$ SGD steps at $0.01$ on $200$ samples hold to $0.05$ . Training at $0.15$ plus $0.05$ gives the $0.20$ test ceiling above.

Watch Out For

Quoting uniform rates for a hypothesis-stable algorithm

Nearest neighbours have 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.

Symptom is rejecting an algorithm that generalises fine on average because its worst-swap $\beta$ looks large. Match variant to loss: bounded regression can use hypothesis stability, while high-probability claims need uniform.

Ignoring the step count in SGD stability

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

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

The Quick Version

Uniform stability caps the worst swap on the worst test point, while 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.
Smooth SGD gets about $2\eta T/n$ , which is $0.05$ at $500$ steps of $0.01$ on $200$ samples.
Early stopping is a stability decision because fewer steps mean smaller $\beta$ .
Training at $0.15$ with $\beta = 0.05$ allows test up to $0.20$ .
Always state steps and variant, since uniform, average, and SGD numbers are not interchangeable.