validation is used must converge to zero as . The second condition, expected-to-leave-one-out error stability (also known as hypothesis stability if operating in the norm) is met if the prediction on a left-out datapoint does not change when a single data point is removed from the training dataset. These conditions can be formalized as: Leave-one-out cross-validation Stability An algorithm has stability if for each , there exists a and such that: and and go to zero as goes to infinity. Expected-leave-one-out error Stability An algorithm has stability if for each there exists a and a such that: with and going to zero for . For leave-one-out stability in the norm, this is the same as hypothesis stability: with going to zero as goes to infinity. Algorithms with proven stability A number of algorithms have been proven to be stable and as a result have bounds on their generalization error. A list of these algorithms and the papers that proved stability is available here. Relation to overfitting The concepts of generalization error and overfitting are closely related. Overfitting occurs when the learned function becomes sensitive to the noise in the sample. As a result, the function will perform well on the training set but not perform well on other data from the joint probability distribution of and . Thus, the more overfitting occurs, the larger the generalization error. The amount of overfitting can be tested using cross-validation methods, that split the sample into simulated training samples and testing samples. The model is then trained on a training sample and evaluated on the testing sample. The testing sample is previously unseen by the algorithm and so represents a random sample from the joint probability distribution of and . This test sample allows us to approximate the expected error and as a result approximate a particular form of the generalization error. Many algorithms exist to prevent overfitting. The minimization algorithm can penalize more complex functions (known as Tikhonov regularization), or the hypothesis space can be constrained, either explicitly in the form of the functions or by adding constraints to the minimization function (Ivanov regularization). The approach to finding a function that does not overfit is at odds with the goal of finding a function that is sufficiently complex to capture the particular characteristics of the data. This is known as the bias–variance tradeoff. Keeping a function simple to avoid overfitting may introduce a