algorithmic stability

Ask of a learning algorithm: if I swap out one training example, does the trained model change much? An algorithm whose output barely moves when any single point is replaced is stable, and stability alone is enough to guarantee generalization — without ever counting hypotheses or measuring class capacity. Intuitively, if your model does not cling to any individual training point, it has not memorized them, so its training error faithfully reflects its true error.

The cleanest version, uniform stability, says that replacing one of the m training points changes the loss on any fixed test point by at most beta. A foundational theorem then bounds the expected generalization gap by beta, and high-probability versions give refined control on the order of beta times the square root of m. Crucially, this analysis targets the specific output of the algorithm, not a supremum over a class, so it can succeed where uniform convergence is vacuous. Regularization, as in ridge regression, and the step-size schedule of stochastic gradient descent both buy stability.

Stability is the theoretical backbone explaining why strongly convex, regularized objectives generalize, and a celebrated result bounds the stability of stochastic gradient descent itself in terms of how long you train and how large the steps are — a learning-theoretic reason early stopping helps. It also connects to differential privacy, which is a strong form of stability. The limitation: establishing tight stability constants for nonconvex deep learning remains hard.