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 , maps a training data set, which is a set of labeled examples , onto a function from to , where and are in the same space of the training examples. The functions are selected from a hypothesis space of functions called . The training set from which an algorithm learns is defined as and is of size in drawn i.i.d. from an unknown distribution D. Thus, the learning map is defined as a mapping from into , mapping a training set onto a function from to . Here, we consider only deterministic algorithms where is symmetric with respect to , 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 of a hypothesis with respect to an example is then defined as . The empirical error of is . The true error of is 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 By replacing the i-th element Definitions of stability Hypothesis Stability An algorithm has hypothesis stability β with respect to the loss function V if the following holds: Point-wise Hypothesis Stability An algorithm has point-wise hypothesis stability β with respect to the loss function V if the following holds: