Why in general is early stopping a good regularisation technique?

Question

Early stopping means stopping gradient descent when the validation error starts to increase.

This is commonly used for neural networks, but can also be used for any model trained by gradient descent, such as a high degree polynomial.

Usually when we regularise, we put some kind of penalty on the parameters, and then look for the optimum of this modified cost function. We think of this as balancing goodness of fit, and high variance, which is controlled by the original cost function, against model simplicity, and high bias, which is controlled by the penalty.

But this isn't what we do with early stopping. We're not seeking the optimum of anything -- by definition we are stopping only "part way" to the optimum of the cost function. And we don't seem to have made the model any simpler; we initialise the model randomly, so we can end up anywhere in the parameter space, not in some restricted "simpler" region. Why then is this a good choice of parameters for reducing overfitting? How, intuitively, should we conceptualise what early stopping is doing?

Answer 1

This is not a rigorous answer, but just to try to give some intuition behind the concept of early stopping.

We know that neural networks have a very high flexibility, which means that they can model extremely complex functions. The more complex a function gets, the more likely is that it will overfit the data.

Searching for that perfect minimum increases the complexity of the function. You start with a relatively smooth function and start tweaking every point of it until it gets you the best performance on the training data. Which means you have overfitted it.

Instead, you can stop early, to a simpler function. Think of it as something in between a smooth function and a highly complex function. It still gets the general shape you want, but didn't have time to fine tune all the small variations needed for a perfect error.

Answer 2

Early stopping is very similar to regularisation like Lasso or Ridge. It is similarly reducing the size of the parameters.

Below is a sketch for the situation of ordinary least squares (OLS) regression. It shows the cost as function of parameters $\beta_1$ and $\beta_2$ which has a shape of ellipses around the optimal OLS solution.

The sets of potential solutions for Lasso, Ridge and gradient descent are similarly creating a descending path towards the optimal OLS solution. In the case of LASSO one of the algorithms to solve the problem, least angle regression (LARS), is even literally following a path down towards the OLS solution.

The reason that early stopping is mostly used with Neural Networks is probably practical. The optimisation is anyways using gradient descent.

The reason that LASSO and Ridge regression are mostly used with linear regression is probably because these methods are more particularly punishing the inclusion of multiple regressor variables (especially LASSO prefers a sparse solution). This can relate to plausible prior assumptions that a solution with few parameters should be preferable (one does not know which regressors are important, but one may have the idea that only a few should be sufficient andany others are just rubbish).