Early stopping
In machine learning, early stopping is a form of regularization used to avoid overfitting when training a learner with an iterative method, such as gradient descent. Such methods update the learner so as to make it better fit the training data with each iteration. Up to a point, this improves the learner's performance on data outside of the training set. Past that point, however, improving the learner's fit to the training data comes at the expense of increased generalization error. Early stopping rules provide guidance as to how many iterations can be run before the learner  begins to over-fit. Early stopping rules have been employed in many different machine learning methods, with varying amounts of theoretical foundation. Background. This section presents some of the basic machine-learning concepts required for a description of early stopping methods. Overfitting. Machine learning algorithms train a model based on a finite set of training data. During this training, the model is evaluated based on how well it predicts the observations contained in the training set. In general, however, the goal of a machine learning scheme is to produce a model that generalizes, that is, that predicts previously unseen observations . Overfitting occurs when a model fits the data in the training set well, while incurring larger generalization error. Regularization. Regularization, in the context of machine learning, refers to the process of modifying a learning algorithm so as to prevent overfitting. This generally involves imposing some sort of smoothness constraint on the learned model. This smoothness may be enforced explicitly, by fixing the number of parameters in the model, or by augmenting the cost function as in Tikhonov regularization. Tikhonov regularization, along with principal component regression and many other regularization schemes, fall under the umbrella of spectral regularization, regularization characterized by  the application of a filter. Early stopping also belongs to this class of methods. Gradient descent methods. Gradient descent methods are first-order, iterative, optimization methods. Each iteration updates an approximate solution to the optimization problem by taking a step in the direction of the negative of the gradient of the objective function. By choosing the step-size appropriately, such a method can be made to converge to a local minimum of the objective function. Gradient descent is used in machine-learning by defining a "loss function" that reflects the error of the learner on the training set and then  minimizing that function. Early stopping based on analytical results. Early stopping in statistical learning theory. Early-stopping can be used to regularize non-parametric regression problems encountered in machine learning. For a given input space, formula_1, output space, formula_2, and samples drawn from an unknown probability measure, formula_3, on formula_4, the goal of such problems is to approximate a "regression function", formula_5, given by where formula_7 is the conditional distribution at formula_8 induced by formula_3. One common choice for approximating the regression function is to use functions from a reproducing kernel Hilbert space. These spaces can be infinite dimensional, in  which they can supply solutions that overfit training sets of arbitrary size. Regularization is, therefore, especially important for these methods. One way to regularize non-parametric regression problems is to apply an early stopping rule to an iterative procedure such as gradient descent. The early stopping rules proposed for these problems are based on analysis of upper bounds on the generalization error as a function of the iteration number. They yield prescriptions for the number of iterations to run that can be computed prior to starting the solution process. Example: Least-squares loss. Let formula_10 and formula_11 Given a set  of samples drawn independently from formula_3, minimize the functional where, formula_15 is a member of the reproducing kernel Hilbert space formula_16. That is, minimize the expected risk for a Least-squares loss function. Since formula_17 depends on the unknown probability measure formula_3, it cannot be used for computation. Instead, consider the following empirical risk Let formula_20 and formula_21 be the "t"-th iterates of gradient descent applied to the expected and empirical risks, respectively, where both iterations are initialized at the origin, and both use the step size formula_22. The formula_20 form the "population iteration", which converges to formula_5, but  cannot be used in computation, while the formula_21 form the "sample iteration" which usually converges to an overfitting solution. We want to control the difference between the expected risk of the sample iteration and the minimum expected risk, that is, the expected risk of the regression function: This difference can be rewritten as the sum of two terms: the difference in expected risk between the sample and population iterations and that between the population iteration and the regression function: This equation presents a bias-variance tradeoff, which is then solved to give an optimal stopping rule that may depend  on the unknown probability distribution. That rule has associated probabilistic bounds on the generalization error. For the analysis leading to the early stopping rule and bounds, the reader is referred to the original article. In practice, data-driven methods, e.g. cross-validation can be used to obtain an adaptive stopping rule. Early stopping in boosting. Boosting refers to a family of algorithms in which a set of weak learners (learners that are only slightly correlated with the true process) are combined to produce a strong learner. It has been shown, for several boosting algorithms (including AdaBoost), that regularization via early  stopping can provide guarantees of consistency, that is, that the result of the algorithm approaches the true solution as the number of samples goes to infinity. L-boosting. Boosting methods have close ties to the gradient descent methods described above can be regarded as a boosting method based on the formula_28 loss: "LBoost". Validation-based early stopping. These early stopping rules work by splitting the original training set into a new training set and a validation set. The error on the validation set is used as a proxy for the generalization error in determining when overfitting has begun. These methods  are most commonly employed in the training of neural networks. Prechelt gives the following summary of a naive implementation of holdout-based early stopping as follows: More sophisticated forms use cross-validation – multiple partitions of the data into training set and validation set – instead of a single partition into a training set and validation set. Even this simple procedure is complicated in practice by the fact that the validation error may fluctuate during training, producing multiple local minima. This complication has led to the creation of many ad hoc rules for deciding when overfitting has truly begun. Early stopping In