Return to Answer

The original version of this answer was missing the point (that's when the answer got a couple of downvotes). The answer was fixed in October 2015.

This is a somewhat controversial topic.

It is often claimed that LOOCV has higher variance than $k$-fold CV, and that it is so because the training sets in LOOCV have more overlap. This makes the estimates from different folds more dependent than in the $k$-fold CV, the reasoning goes, and hence increases the overall variance. See for example a quote from The Elements of Statistical Learning by Hastie et al. (Section 7.10.1):

What value should we choose for $K$? With $K = N$, the cross-validation estimator is approximately unbiased for the true (expected) prediction error, but can have high variance because the N "training sets" are so similar to one another.

See also a similar quote in the answer by @BrashEquilibrium (+1). The accepted and the most upvoted answers in Bias and variance in leave-one-out vs K-fold cross validation give the same reasoning.

However, note that Hastie et al. do not give any citations, and while this reasoning does sound plausible, I would like to see some direct evidence that this is indeed the case. One reference that is sometimes cited is Kohavi 1995 but I don't find it very convincing in this particular claim.

This question seems to be very amenable to simulations. Here is one simulation that does show high variance of LOOCV: https://stats.stackexchange.com/a/357572.

But here is one simulation that shows low (!) variance of LOOCV: Variance of $K$-fold cross-validation estimates as $f(K)$: what is the role of "stability"?. See also the paper linked in https://stats.stackexchange.com/a/252031.

So it seems that there is disagreement about whether LOOCV does indeed have high variance; let alone about why.

The original version of this answer was missing the point (that's when the answer got a couple of downvotes). The answer was fixed in October 2015.

This is a somewhat controversial topic.

It is often claimed that LOOCV has higher variance than $k$-fold CV, and that it is so because the training sets in LOOCV have more overlap. This makes the estimates from different folds more dependent than in the $k$-fold CV, the reasoning goes, and hence increases the overall variance. See for example a quote from The Elements of Statistical Learning by Hastie et al. (Section 7.10.1):

What value should we choose for $K$? With $K = N$, the cross-validation estimator is approximately unbiased for the true (expected) prediction error, but can have high variance because the $N$ "training sets" are so similar to one another.

See also a similar quote in the answer by @BrashEquilibrium (+1). The accepted and the most upvoted answers in Bias and variance in leave-one-out vs K-fold cross validation give the same reasoning.

HOWEVER, note that Hastie et al. do not give any citations, and while this reasoning does sound plausible, I would like to see some direct evidence that this is indeed the case. One reference that is sometimes cited is Kohavi 1995 but I don't find it very convincing in this particular claim.

MOREOVER, here are two simulations that show that LOOCV either has the same or even a bit lower variance than 10-fold CV:

• https://stats.stackexchange.com/a/357572.
• Variance of $K$-fold cross-validation estimates as $f(K)$: what is the role of "stability"?.
• See also the paper linked in https://stats.stackexchange.com/a/252031. It says that it is a "misconception" that LOOCV has high variance.

Oct 2015. My original answer here was irrelevant, as pointed out in the comments below and in a couple of downvotes. I replace it with a new answer now (but save my original answer below).

This is a complicated topic, and I must admit that I don't have a full understanding of it. It is often claimed that LOOCV has higher variance than $k$-fold CV, and that it is because the training sets in LOOCV have more overlap. This makes the estimates from different folds more dependent than in the $k$-fold CV, the reasoning goes, and hence increases the overall variance.

  See for example a quote from The Elements of Statistical Learning by Hastie et al. (Section 7.10.1):

See also a similar quote in the answer by @BrashEquilibrium (+1). However, note that Hastie et al. do not give any citations here, and while this reasoning sounds plausible, I would like to see some more convincing evidence that this is the case.

This topic has previously been discussed on CrossValidated, and in fact I believe that this question is an exact duplicate of this one:

• Bias and variance in leave-one-out vs K-fold cross validation

See also

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

Original answer

The answer below was irrelevant, because it discusses the variance over folds and not the overall variance over datasets.

Consider a dataset of size $N$ and probability of misclassification $p$. Let's compare LOOCV and 10-fold CV. For simplicity let's assume that they both correctly estimate the error rate.

If we do LOOCV, then each of the $N$ samples will be misclassified with probability $p$. So the number of misclassifications in each test set (each consisting of 1 element) is a Bernoulli random variable with mean $p$ and variance [over folds] $p(1-p)$. The error rate is equal to the number of misclassifications.

If we do 10-fold CV, then in each test set the number of misclassifications is a binomial random variable with mean $\frac{N}{10}p$ and variance $\frac{N}{10}p(1-p)$. The error rate is equal to the number of misclassifications divided by the size of the test set, i.e. by $\frac{N}{10}$. So the error rate will have mean $p$ and variance [over folds] $\frac{10}{N}p(1-p)$.

We see that mean error rate in both cases is $p$, but variance [over folds] is $\frac{N}{10}$ times smaller in cases of 10-fold CV. If for example $N=100$, then it's a 10-fold decrease. The intuition here is that in LOOCV on each fold there is only one test sample and so you can only estimate error rate as either $0$ or $1$. This is a very noisy estimate of $p$ and it will therefore have high variance [over folds].

The original version of this answer was missing the point (that's when the answer got a couple of downvotes). The answer was fixed in October 2015.

This is a somewhat controversial topic. 

It is often claimed that LOOCV has higher variance than $k$-fold CV, and that it is so because the training sets in LOOCV have more overlap. This makes the estimates from different folds more dependent than in the $k$-fold CV, the reasoning goes, and hence increases the overall variance. See for example a quote from The Elements of Statistical Learning by Hastie et al. (Section 7.10.1):

See also a similar quote in the answer by @BrashEquilibrium (+1). The accepted and the most upvoted answers in Bias and variance in leave-one-out vs K-fold cross validation give the same reasoning.

However, note that Hastie et al. do not give any citations, and while this reasoning does sound plausible, I would like to see some direct evidence that this is indeed the case. One reference that is sometimes cited is Kohavi 1995 but I don't find it very convincing in this particular claim.

This question seems to be very amenable to simulations. Here is one simulation that does show high variance of LOOCV: https://stats.stackexchange.com/a/357572.

But here is one simulation that shows low (!) variance of LOOCV: Variance of $K$-fold cross-validation estimates as $f(K)$: what is the role of "stability"?. See also the paper linked in https://stats.stackexchange.com/a/252031.

So it seems that there is disagreement about whether LOOCV does indeed have high variance; let alone about why.

Oct 2015. My original answer here was irrelevant, as pointed out in the comments below and in a couple of downvotes. I replace it with a new answer now (but save my original answer below).

This is a complicated topic, and I must admit that I don't have a full understanding of it. It is often claimed that LOOCV has higher variance than $k$-fold CV, and that it is because the training sets in LOOCV have more overlap. This makes the estimates from different folds more dependent than in the $k$-fold CV, the reasoning goes, and hence increases the overall variance.

See for example a quote from The Elements of Statistical Learning by Hastie et al. (Section 7.10.1):

What value should we choose for $K$? With $K = N$, the cross-validation estimator is approximately unbiased for the true (expected) prediction error, but can have high variance because the N "training sets" are so similar to one another.

See also a similar quote in the answer by @BrashEquilibrium (+1). However, note that Hastie et al. do not give any citations here, and while this reasoning sounds plausible, I would like to see some more convincing evidence that this is the case.

This topic has previously been discussed on CrossValidated, and in fact I believe that this question is an exact duplicate of this one:

• Bias and variance in leave-one-out vs K-fold cross validation

See also

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

Original answer

The answer below was irrelevant, because it discusses the variance over folds and not the overall variance over datasets.

Consider a dataset of size $N$ and probability of misclassification $p$. Let's compare LOOCV and 10-fold CV. For simplicity let's assume that they both correctly estimate the error rate.

If we do LOOCV, then each of the $N$ samples will be misclassified with probability $p$. So the number of misclassifications in each test set (each consisting of 1 element) is a Bernoulli random variable with mean $p$ and variance [over folds] $p(1-p)$. The error rate is equal to the number of misclassifications.

If we do 10-fold CV, then in each test set the number of misclassifications is a binomial random variable with mean $\frac{N}{10}p$ and variance $\frac{N}{10}p(1-p)$. The error rate is equal to the number of misclassifications divided by the size of the test set, i.e. by $\frac{N}{10}$. So the error rate will have mean $p$ and variance [over folds] $\frac{10}{N}p(1-p)$.

We see that mean error rate in both cases is $p$, but variance [over folds] is $\frac{N}{10}$ times smaller in cases of 10-fold CV. If for example $N=100$, then it's a 10-fold decrease. The intuition here is that in LOOCV on each fold there is only one test sample and so you can only estimate error rate as either $0$ or $1$. This is a very noisy estimate of $p$ and it will therefore have high variance [over folds].

Oct 2015. My original answer here was irrelevant, as pointed out in the comments below and in a couple of downvotes. I replace it with a new answer now (but save my original answer below).

This is a complicated topic, and I must admit that I don't have a full understanding of it. It is often claimed that LOOCV has higher variance than $k$-fold CV, and that it is because the training sets in LOOCV have more overlap. This makes the estimates from different folds more dependent than in the $k$-fold CV, the reasoning goes, and hence increases the overall variance.

See for example a quote from The Elements of Statistical Learning by Hastie et al. (Section 7.10.1):

What value should we choose for $K$? With $K = N$, the cross-validation estimator is approximately unbiased for the true (expected) prediction error, but can have high variance because the N "training sets" are so similar to one another.

See also a similar quote in the answer by @BrashEquilibrium (+1). However, note that Hastie et al. do not give any citations here, and while this reasoning sounds plausible, I would like to see some more convincing evidence that this is the case.

This topic has previously been discussed on CrossValidated, and in fact I believe that this question is an exact duplicate of this one:

• Bias and variance in leave-one-out vs K-fold cross validation

See also

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

Original answer

The answer below was irrelevant, because it discusses the variance over folds and not the overall variance over datasets.

Consider a dataset of size $N$ and probability of misclassification $p$. Let's compare LOOCV and 10-fold CV. For simplicity let's assume that they both correctly estimate the error rate.

If we do LOOCV, then each of the $N$ samples will be misclassified with probability $p$. So the number of misclassifications in each test set (each consisting of 1 element) is a Bernoulli random variable with mean $p$ and variance [over folds] $p(1-p)$. The error rate is equal to the number of misclassifications.

If we do 10-fold CV, then in each test set the number of misclassifications is a binomial random variable with mean $\frac{N}{10}p$ and variance $\frac{N}{10}p(1-p)$. The error rate is equal to the number of misclassifications divided by the size of the test set, i.e. by $\frac{N}{10}$. So the error rate will have mean $p$ and variance [over folds] $\frac{10}{N}p(1-p)$.

We see that mean error rate in both cases is $p$, but variance [over folds] is $\frac{N}{10}$ times smaller in cases of 10-fold CV. If for example $N=100$, then it's a 10-fold decrease. The intuition here is that in LOOCV on each fold there is only one test sample and so you can only estimate error rate as either $0$ or $1$. This is a very noisy estimate of $p$ and it will therefore have high variance [over folds].