Early stopping

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 statistical learning theory. For a given input space, ${\displaystyle X}$, output space, ${\displaystyle Y}$, and samples drawn from an unknown probability measure, ${\displaystyle \rho }$, on ${\displaystyle Z=X\times Y}$, the goal of such problems is to approximate a regression function, ${\displaystyle f_{\rho }}$, given by

${\displaystyle f_{\rho }(x)={\int }_{Y}yd\rho (y\mid x),x\in X,}$

where ${\displaystyle \rho (y\mid x)}$ is the conditional distribution at ${\displaystyle x}$ induced by ${\displaystyle \rho }$. 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

(Adapted from Yao, Rosasco and Caponnetto, 2007)

Let ${\displaystyle X\subseteq {\mathbb{R}}^n}$ and ${\displaystyle Y=\mathbb{R}.}$ Given a set of samples

${\displaystyle \mathbf{z}=\left\{(x_i,y_i)\in X\times Y:i=1,\dots ,m\right\}\in Z^m,}$

drawn independently from ${\displaystyle \rho }$, minimize the functional

${\displaystyle \mathcal{E}(f)={\int }_{X\times Y}(f(x)-y{)}^{2}d\rho }$

where, ${\displaystyle f}$ is a member of the reproducing kernel Hilbert space ${\displaystyle \mathcal{H}}$. That is, minimize the expected risk for a Least-squares loss function. Since ${\displaystyle \mathcal{E}}$ depends on the unknown probability measure ${\displaystyle \rho }$, it cannot be used for computation. Instead, consider the following empirical risk

${\displaystyle {\mathcal{E}}_{\mathbf{z}}(f)=\frac{1}{m}\sum _{i=1}^m{\left(f(x_i)-y_i\right)}^2.}$

Let ${\displaystyle f_t}$ and ${\displaystyle f_t^{\mathbf{z}}}$ 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 ${\displaystyle {\gamma }_t}$. The ${\displaystyle f_t}$ form the population iteration, which converges to ${\displaystyle f_{\rho }}$, but cannot be used in computation, while the ${\displaystyle f_t^{\mathbf{z}}}$ 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:

${\displaystyle \mathcal{E}(f_t^{\mathbf{z}})-\mathcal{E}(f_{\rho })}$

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:

${\displaystyle \mathcal{E}(f_t^{\mathbf{z}})-\mathcal{E}(f_{\rho })=\left[\mathcal{E}(f_t^{\mathbf{z}})-\mathcal{E}(f_t)\right]+\left[\mathcal{E}(f_t)-\mathcal{E}(f_{\rho })\right]}$

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.

L2-boosting

Boosting methods have close ties to the gradient descent methods described above can be regarded as a boosting method based on the ${\displaystyle L_2}$ loss: L₂Boost.

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 employed in the training of many iterative machine learning algorithms including neural networks. Prechelt gives the following summary of a naive implementation of holdout-based early stopping as follows:

1. Split the training data into a training set and a validation set, e.g. in a 2-to-1 proportion.
2. Train only on the training set and evaluate the per-example error on the validation set once in a while, e.g. after every fifth epoch.
3. Stop training as soon as the error on the validation set is higher than it was the last time it was checked.
4. Use the weights the network had in that previous step as the result of the training run.

— Lutz Prechelt, Early Stopping – But When?

Cross-validation is an alternative that is applicable to non time-series scenarios. Cross-validation involves splitting 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.