Leave-One-Out Stability

An algorithm that swings wildly whenever you drop one training example is telling you it has memorized that example rather than learned a general pattern — and algorithms like that tend to generalize poorly to new data, no matter how well they fit the training set. Leave-one-out stability turns that intuition into something measurable: train the model on the full dataset, then retrain it $n$ times, each time with exactly one observation removed, and compare each retrained model's predictions to the original model's predictions. If removing any single point barely changes the predictions, the algorithm is "stable"; if removing one particular point flips the model's behavior, it's unstable at that point.

This connects directly to generalization because of a classical result: algorithms with strong enough leave-one-out stability have provable bounds on how much their training error can understate their true out-of-sample error, without needing a separate held-out validation set at all — stability itself substitutes for the usual train/test split argument.

In practice this is why heavily regularized models (ridge regression, for instance) tend to generalize more predictably than unregularized ones fit to noisy, high-dimensional data — regularization is, among other things, a direct way of forcing leave-one-out stability, shrinking the influence any single observation can have on the fitted model. It's also why leave-one-out cross-validation itself, despite being expensive to compute exactly for large datasets, is often approximated cheaply for stable linear models using a single closed-form correction rather than literally retrained $n$ times.