Stability

Stability measures how much a learning algorithm’s output changes when its training data are altered. In statistical learning theory, it helps bound the gap between training performance and performance on new data.

Uniform stability: A learning algorithm has uniform stability when replacing one training example changes its loss by at most a fixed amount across all examples. This strong, widely used definition yields direct bounds on expected generalization error.
Empirical risk minimization: A learning principle that selects a model minimizing average loss on the observed training examples. Stability analysis often studies algorithms that minimize empirical risk.
Generalization in machine learning: The ability of a learned model to perform well on data drawn from the same process as its training data. Stability provides one route from training behavior to expected performance on unseen examples.
Probably approximately correct learning: A framework that characterizes whether a learner can achieve low prediction error with high probability using finite data. It studies learnability through sample complexity rather than algorithmic sensitivity.
On-average stability: A stability condition that controls the average effect of changing one training example rather than requiring a uniform bound. It can establish generalization guarantees under weaker conditions than uniform stability.
Regularization: A set of methods that constrain or penalize model complexity to improve learning behavior. Regularization often reduces sensitivity to individual training examples.
Differential privacy: A formal privacy framework that limits how much an analysis reveals about any one individual’s data. Both privacy and stability constrain the effect of changing one training record, though their guarantees differ.
Rademacher complexity: A measure of how well a class of functions can fit random fluctuations in a sample. It bounds generalization through hypothesis-class richness, unlike stability’s focus on a particular algorithm.
Replace-one stability: A sensitivity measure comparing an algorithm’s outputs on datasets that differ in one example. It formalizes the single-example perturbation at the heart of many stability definitions.
Strong convexity: A curvature condition requiring a function to bend upward at least as strongly as a positive quadratic function. Strong convexity helps prove stability for regularized empirical risk minimization.

Linked from 2 pages