Stability (learning theory)

A central goal in designing a machine learning system is to guarantee that the learning algorithm will generalize, or perform accurately on new examples after being trained on a finite number of them. In the 1990s, milestones were reached in obtaining generalization bounds for supervised learning algorithms. The technique historically used to prove generalization was to show that an algorithm was consistent, using the uniform convergence properties of empirical quantities to their means. This technique was used to obtain generalization bounds for the large class of empirical risk minimization (ERM) algorithms. An ERM algorithm is one that selects a solution from a hypothesis space H in such a way to minimize the empirical error on a training set S. A general result, proved by Vladimir Vapnik for an ERM binary classification algorithms, is that for any target function and input distribution, any hypothesis space H with VC-dimension d, and n training examples, the algorithm is consistent and will produce a training error that is at most O\left(\sqrt{\frac{d}{n}}\right) (plus logarithmic factors) from the true error. The result was later extended to almost-ERM algorithms with function classes that do not have unique minimizers. Vapnik's work, using what became known as VC theory, established a relationship between generalization of a learning algorithm and properties of the hypothesis space H of functions being learned. However, these results could not be applied to algorithms with hypothesis spaces of unbounded VC-dimension. Put another way, these results could not be applied when the information being learned had a complexity that was too large to measure. Some of the simplest machine learning algorithms—for instance, for regression—have hypothesis spaces with unbounded VC-dimension. Another example is language learning algorithms that can produce sentences of arbitrary length. Stability analysis was developed in the 2000s for computational learning theory and is an alternative method for obtaining generalization bounds. The stability of an algorithm is a property of the learning process, rather than a direct property of the hypothesis space H, and it can be assessed in algorithms that have hypothesis spaces with unbounded or undefined VC-dimension such as nearest neighbor. A stable learning algorithm is one for which the learned function does not change much when the training set is slightly modified, for instance by leaving out an example. A measure of Leave one out error is used in a Cross Validation Leave One Out (CVloo) algorithm to evaluate a learning algorithm's stability with respect to the loss function. As such, stability analysis is the application of sensitivity analysis to machine learning. == Summary of classic results ==

• Early 1900s - Stability in learning theory was earliest described in terms of continuity of the learning map L, traced to Andrey Nikolayevich Tikhonov. • 1979 - Devroye and Wagner observed that the leave-one-out behavior of an algorithm is related to its sensitivity to small changes in the sample. • 1999 - Kearns and Ron discovered a connection between finite VC-dimension and stability. • 2002 - In a landmark paper, Bousquet and Elisseeff proposed the notion of uniform hypothesis stability of a learning algorithm and showed that it implies low generalization error. Uniform hypothesis stability, however, is a strong condition that does not apply to large classes of algorithms, including ERM algorithms with a hypothesis space of only two functions. • 2002 - Kutin and Niyogi extended Bousquet and Elisseeff's results by providing generalization bounds for several weaker forms of stability which they called almost-everywhere stability. Furthermore, they took an initial step in establishing the relationship between stability and consistency in ERM algorithms in the Probably Approximately Correct (PAC) setting. • 2004 - Poggio et al. proved a general relationship between stability and ERM consistency. They proposed a statistical form of leave-one-out-stability which they called CVEEEloo stability, and showed that it is a) sufficient for generalization in bounded loss classes, and b) necessary and sufficient for consistency (and thus generalization) of ERM algorithms for certain loss functions such as the square loss, the absolute value and the binary classification loss. • 2010 - Shalev Shwartz et al. noticed problems with the original results of Vapnik due to the complex relations between hypothesis space and loss class. They discuss stability notions that capture different loss classes and different types of learning, supervised and unsupervised. • 2016 - Moritz Hardt et al. proved stability of gradient descent given certain assumption on the hypothesis and number of times each instance is used to update the model. == Preliminary definitions ==

We define several terms related to learning algorithms training sets, so that we can then define stability in multiple ways and present theorems from the field. A machine learning algorithm, also known as a learning map L, maps a training data set, which is a set of labeled examples (x,y), onto a function f from X to Y, where X and Y are in the same space of the training examples. The functions f are selected from a hypothesis space of functions called H. The training set from which an algorithm learns is defined as S = \{z_1 = (x_1,\ y_1)\ ,..,\ z_m = (x_m,\ y_m)\} and is of size m in Z = X \times Y drawn i.i.d. from an unknown distribution D. Thus, the learning map L is defined as a mapping from Z_m into H, mapping a training set S onto a function f_S from X to Y. Here, we consider only deterministic algorithms where L is symmetric with respect to S, i.e. it does not depend on the order of the elements in the training set. Furthermore, we assume that all functions are measurable and all sets are countable. The loss V of a hypothesis f with respect to an example z = (x,y) is then defined as V(f,z) = V(f(x),y). The empirical error of f is I_S[f] = \frac{1}{n}\sum V(f,z_i). The true error of f is I[f] = \mathbb{E}_z V(f,z) Given a training set S of size m, we will build, for all i = 1....,m, modified training sets as follows: • By removing the i-th element S^{|i} = \{z_1 ,...,\ z_{i-1},\ z_{i+1},...,\ z_m\} • By replacing the i-th element S^i = \{z_1 ,...,\ z_{i-1},\ z_i',\ z_{i+1},...,\ z_m\} == Definitions of stability ==

Hypothesis Stability An algorithm L has hypothesis stability β with respect to the loss function V if the following holds: \forall i\in \{1,...,m\}, \mathbb{E}_{S,z} [|V(f_S,z)-V(f_{S^{|i}},z)|]\leq\beta. Point-wise Hypothesis Stability An algorithm L has point-wise hypothesis stability β with respect to the loss function V if the following holds: \forall i\in\ \{1,...,m\}, \mathbb{E}_{S} [|V(f_S,z_i)-V(f_{S^{|i}},z_i)|]\leq\beta. Error Stability An algorithm L has error stability β with respect to the loss function V if the following holds: \forall S\in Z^m, \forall i\in\{1,...,m\}, |\mathbb{E}_z[V(f_S,z)]-\mathbb{E}_z[V(f_{S^{|i}},z)]|\leq\beta Uniform Stability An algorithm L has uniform stability β with respect to the loss function V if the following holds: \forall S\in Z^m, \forall i\in\{1,...,m\}, \sup_{z\in Z}|V(f_S,z)-V(f_{S^{|i}},z)|\leq\beta A probabilistic version of uniform stability β is: \forall S\in Z^m, \forall i\in\{1,...,m\}, \mathbb{P}_S\{\sup_{z\in Z}|V(f_S,z)-V(f_{S^{|i}},z)|\leq\beta\}\geq1-\delta An algorithm is said to be stable, when the value of \beta decreases as O(\frac{1}{m}). Leave-one-out cross-validation (CVloo) Stability An algorithm L has CVloo stability β with respect to the loss function V if the following holds: \forall i\in\{1,...,m\}, \mathbb{P}_S\{ |V(f_S,z_i) - V(f_{S^{|i}},z_i)|\leq\beta_{CV}\}\geq1 - \delta_{CV} The definition of (CVloo) Stability is equivalent to Pointwise-hypothesis stability seen earlier. Expected-leave-one-out error (Eloo_{err}) Stability An algorithm L has Eloo_{err} stability if for each n there exists a \beta_{EL}^m and a \delta_{EL}^m such that: \forall i\in\{1,...,m\}, \mathbb{P}_S\{|I[f_S]-\frac{1}{m}\sum_{i=1}^m V(f_{S^{|i}},z_i)|\leq\beta_{EL}^m\}\geq1-\delta_{EL}^m, with \beta_{EL}^m and \delta_{EL}^m going to zero for m,\rightarrow\infty == 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 (Eloo_{err}) 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. • Multi-class SVM classification. == References ==