Do out-of-sample fitting methods solve the problem of over-fitting?

Question

Suppose we have a regression model, and we want to fit this to training data, and then make predictions on test data. There is a well-known danger that out-of-sample predictions will be poor, due to "over-fitting" of the model to the training data.$^\dagger$ If I understand it correctly, the phenomenon of over-fitting occurs because (1) the fitting method involves optimisation of in-sample prediction taken over the training data, and thus conforms excessively to this data; or (2) the model selection method does not adequately penalise complexity. Some analysts use cross-validation on a "validation set" to deal with over-fitting, which still involves an optimisation, but the optimisation is now done using out-of-sample predictions (i.e., the regression model is fit with the training data, but the prediction errors are obtained from the validation data).

It occurs to me that there are already well-known methods for fitting a regression model on a "leave-one-out" basis (e.g., for linear regression we can minimise the LOOCV statistic instead of minimising the residual-sum-of-squares). So the obvious question is, why bother with a "validation" step. Why not just use this leave-one-out fitting method on the training data to begin with, so that we optimise out-of-sample prediction? In combination with an appropriate way to penalise model complexity (e.g., by using partial F-tests for model terms), that would seem to deal with over-fitting, since while still using all available data points for the fit in each case (by only leaving one out, rather than leaving out a whole "validation set").

My questions: Am I right that over-fitting is caused by the fact that we optimise based on errors from in-sample predictions? If so, then does the use of optimisation based on errors from out-of-sample prediction avoid over-fitting? For example, if we fit a linear regression by minimising LOOCV (and with model selection that tests inclusion of model terms), is that enough to avoid over-fitting?

---

$^\dagger$ There is an excellent discussion of over-fitting in Chapter 7 of Hastie, Tibshirani and Friedman (2016), examined within the context of a linear regression model with prediction error measured by squared-error loss. For this loss function they link the phenomenon of over-fitting to the bias-variance trade-off. There are also some answers on this site (e.g., here) that discuss over-fitting in terms of the bias-variance trade-off.

Answer 1

Validation sets and overfitting

Let us start with your question about why we use a validation set. We use this to get an estimate of the true out-of-sample error of our model. We use a separate set here because, as you know, looking at in-sample residuals will give us a too optimistic idea of our performance.

Now, suppose we apply our model $M_1$ to the validation set and obtain an error that does not make us happy... but then we notice something about that validation set that $M_1$ didn't catch very well. Which gives us an idea of how to improve the model. So we go back to our training and test set, tweak the model, optimize it a bit more, finally apply the resulting model $M_2$ to the validation set, and success! $M_2$ performs better on the validation set than $M_1$! Hurray! And since we didn't use the validation set in training the model, everything is fine, right?

Except, of course, it isn't. We have used the validation set, since it informed our modification of $M_1$ to $M_2$. We have already started down the slippery slope towards overfitting on the validation set, and we can happily slide down that slope some more by tweaking our model yet more to $M_3$, $M_4$, ...

Which gives my answer to your question: overfitting is caused by using observations to inform the model (whether through fitting the model to the training set, evaluating the fit on the test set, or "being inspired" by the validation set as in the previous paragraphs), and then expecting the model's performance on these observations to predict its performance on new data.

Cross-validation won't help

By now, you know that CV won't help us here, because by definition, the data point(s) left out are used in model selection. In fact, it's pretty easy to overfit to LOOCV. Here are some random data with no relationship whatsoever:

I'll fit (orthogonal) polynomials, starting with a zero degree horizontal line, up through a 6th degree one:

Let's apply LOOCV to these models. Below, I'll plot the LOOCV sums of squared (out-of-bag) errors.

As we see, the 5th degree polynomial "performs best", so here is the "best model":

As I said, there is actually no structure at all in these data, so anything beyond the horizontal line is pure overfitting. So we see that it's easy to overfit to LOOCV (it only took me running three different random seeds to get this example), and of course it would be easy to construct a somewhat more complicated example of "overfitting to the validation set" in the sense above.

The bottom line

If you want an estimate of your model's performance on new data, then apply it to previously unseen data... and resist the temptation to tweak the model based on the results. (Or, do tweak it, but then evaluate the tweaked model on new data. And don't be surprised if the un-tweaked model performs better on this new data than the tweaked one.)

R code

nn <- 30

set.seed(3)
predictor <- sort(runif(nn))
response <- runif(nn)

plot(predictor,response,pch=19,xlab="Predictor",ylab="Response")

max_degree <- 6

cv_sse <- rep(0,max_degree+1)

for ( ii in 0:max_degree ) {
    for ( jj in 1:nn ) {
        if ( ii == 0 ) {
         cv_sse[1] <- cv_sse[1]+(response[jj]-mean(response[-jj]))^2
         lines(c(min(predictor),max(predictor)),rep(mean(predictor),2))
        } else {
            model_predictor <- predictor[-jj]
            model <- lm(response[-jj]~poly(model_predictor,ii))
            prediction <- predict(model,newdata=data.frame(model_predictor=predictor[jj]))
            cv_sse[ii+1] <- cv_sse[ii+1]+(response[jj]-prediction)^2
            lines(predictor,predict(lm(response~poly(predictor,ii))))
        }
    }
}
lines(predictor,predict(lm(response~poly(predictor,which.min(cv_sse)-1))),col="red",lwd=2)

plot(0:max_degree,cv_sse,type="o",pch=19,xlab="Degree",ylab="CV SSE")