Optimal number of folds in $K$-fold cross-validation: is leave-one-out CV always the best choice?

Question

Computing power considerations aside, are there any reasons to believe that increasing the number of folds in cross-validation leads to better model selection/validation (i.e. that the higher the number of folds the better)?

Taking the argument to the extreme, does leave-one-out cross-validation necessarily lead to better models than $K$-fold cross-validation?

Some background on this question: I am working on a problem with very few instances (e.g. 10 positives and 10 negatives), and am afraid that my models may not generalize well/would overfit with so little data.

Answer 1

Leave-one-out cross-validation does not generally lead to better performance than K-fold, and may be more likely to be worse, as it can have a relatively high variance (i.e. its value changes more for different samples of data than the value for k-fold cross-validation). This is bad in a model selection criterion as it means the model selection criterion can be optimised in ways that merely exploit the random variation in the particular sample of data, rather than making genuine improvements in performance, i.e. you are more likely to over-fit the model selection criterion. The reason leave-one-out cross-validation is used in practice is that for many models it can be evaluated very cheaply as a by-product of fitting the model.

If computational expense is not primarily an issue, a better approach is to perform repeated k-fold cross-validation, where the k-fold cross-validation procedure is repeated with different random partitions into k disjoint subsets each time. This reduces the variance.

If you have only 20 patterns, it is very likely that you will experience over-fitting the model selection criterion, which is a much neglected pitfall in statistics and machine learning (shameless plug: see my paper on the topic). You may be better off choosing a relatively simple model and try not to optimise it very aggressively, or adopt a Bayesian approach and average over all model choices, weighted by their plausibility. IMHO optimisation is the root of all evil in statistics, so it is better not to optimise if you don't have to, and to optimise with caution whenever you do.

Note also if you are going to perform model selection, you need to use something like nested cross-validation if you also need a performance estimate (i.e. you need to consider model selection as an integral part of the model fitting procedure and cross-validate that as well).

Answer 2

Choosing the number K folds by considering the learning curve

I would like to argue that choosing the appropriate number of $K$ folds depends a lot on the shape and position of the learning curve, mostly due to its impact on the bias. This argument, which extends to leave-one-out CV, is largely taken from the book "Elements of Statistical Learning" chapter 7.10, page 243.

For discussions on the impact of $K$ on the variance see here

To summarize, if the learning curve has a considerable slope at the given training set size, five- or tenfold cross-validation will overestimate the true prediction error. Whether this bias is a drawback in practice depends on the objective. On the other hand, leave-one-out cross-validation has low bias but can have high variance.

An intuitive visualization using a toy example

To understand this argument visually, consider the following toy example where we are fitting a degree 4 polynomial to a noisy sine curve:

Intuitively and visually, we expect this model to fare poorly for small datasets due to overfitting. This behaviour is reflected in the learning curve where we plot $1 -$ Mean Square Error vs Training size together with $\pm$ 1 standard deviation. Note that I chose to plot 1 - MSE here to reproduce the illustration used in ESL page 243

Discussing the argument

The performance of the model improves significantly as the training size increases to 50 observations. Increasing the number further to 200 for example brings only small benefits. Consider the following two cases:

1. If our training set had 200 observations, $5$ fold cross validation would estimate the performance over a training size of 160 which is virtually the same as the performance for training set size 200. Thus cross-validation would not suffer from much bias and increasing $K$ to larger values will not bring much benefit (left hand plot)

2. However if the training set had $50$ observations, $5$ fold cross-validation would estimate the performance of the model over training sets of size 40, and from the learning curve this would lead to a biased result. Hence increasing $K$ in this case will tend to reduce the bias. (right hand plot).

[Update] - Comments on the methodology

You can find the code for this simulation here. The approach was the following:

1. Generate 50,000 points from the distribution $sin(x) + \epsilon$ where the true variance of $\epsilon$ is known
2. Iterate $i$ times (e.g. 100 or 200 times). At each iteration, change the dataset by resampling $N$ points from the original distribution
3. For each data set $i$:
   • Perform K-fold cross validation for one value of $K$
   • Store the average Mean Square Error (MSE) across the K-folds
4. Once the loop over $i$ is complete, calculate the mean and standard deviation of the MSE across the $i$ datasets for the same value of $K$
5. Repeat the above steps for all $K$ in range $\{ 5,...,N\}$ all the way to LOOCV

An alternative approach is to not resample a new data set at each iteration and instead reshuffle the same dataset each time. This seems to give similar results.