Error Stability An algorithm has error stability β with respect to the loss function V if the following holds: Uniform Stability An algorithm has uniform stability β with respect to the loss function V if the following holds: A probabilistic version of uniform stability β is: An algorithm is said to be stable, when the value of decreases as . Leave-one-out cross-validation (CVloo) Stability An algorithm has CVloo stability β with respect to the loss function V if the following holds: The definition of (CVloo) Stability is equivalent to Pointwise-hypothesis stability seen earlier. Expected-leave-one-out error () Stability An algorithm has stability if for each n there exists a and a such that: , with and going to zero for Classic theorems From Bousquet and Elisseeff (02): For symmetric learning algorithms with bounded loss, if the algorithm has Uniform Stability with the probabilistic definition above, then the algorithm generalizes. Uniform Stability is a strong condition which is not met by all algorithms but is, surprisingly, met by the large and important class of Regularization algorithms. The generalization bound is given in the article. From Mukherjee et al. (06): For symmetric learning algorithms with bounded loss, if the algorithm has both Leave-one-out cross-validation (CVloo) Stability and Expected-leave-one-out error () Stability as defined above, then the algorithm generalizes. Neither condition alone is sufficient for generalization. However, both together ensure generalization (while the converse is not true). For ERM algorithms specifically (say for the square loss), Leave-one-out cross-validation (CVloo) Stability is both necessary and sufficient for consistency and generalization. This is an important result for the foundations of learning theory, because it shows that two previously unrelated properties of an algorithm, stability and consistency, are equivalent for ERM (and certain loss functions). The generalization bound is given in the article. Algorithms that are stable This is a list of algorithms that have been shown to be stable, and the article where the associated generalization bounds are provided. Linear regression k-NN classifier with a {0-1} loss function. Support Vector Machine (SVM) classification with a bounded kernel and where the regularizer is a norm in a Reproducing Kernel Hilbert Space. A large regularization constant leads to good stability. Soft margin SVM classification. Regularized Least Squares regression. The minimum relative entropy algorithm for classification. A version of bagging regularizers with the number of regressors increasing with . Multi-class SVM classification. All learning algorithms with Tikhonov regularization satisfies