In leave-one-out cross-validation (LOOCV), each of the training sets looks very similar to the others, differing in only one observation. When you want to estimate the test error, you take the average of the errors over the folds. That average has a high variance.
Is there a mathematical formula, visual, or intuitive way to understand why that average has a higher variance compared with the $k$-fold cross validation?
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 Variance and bias in cross-validation: why does leave-one-out CV have higher variance? 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:
From An Introduction to Statistical Learning
When we perform LOOCV, we are in effect averaging the outputs of $n$ fitted models, each of which is trained on an almost identical set of observations; therefore, these ouputs are highly (positively) correlated with each other. In contrast, when we perform $k$-fold CV with $k<n$, we are averaging the outputs of $k$ fitted models that are somewhat less correlated with each other, since the overlap between the training sets in each model is smaller. Since the mean of many highly correlated quantities has higher variance than does the mean of many quantities that are not as highly correlated, the test error estimate resulting from LOOCV tends to have higher variance than does the test error estimate resulting from $k$-fold CV.
To summarize, there is a bias-variance trade-off associated with the choice of $k$ in $k$-fold cross-validation. Typically, given these considerations, one performs $k$-fold cross-validation with $k=5$ or $k=10$, as these values have been shown empirically to yield test error rate estimates that suffer neither from excessively high bias nor from very high variance.
In simple cases I think the answer is: the grand mean (over all test cases and all folds) has the same variance for $k$-fold and LOO validation.
Simple means here: models are stable, so each of the $k$ or $n$ surrogate models yields the same predicion for the same sample (thought experiment: test surrogate models with large independent test set).
If the models are not stable, the situation gets more complex: each of the surrogate models has its own performance, so you have additional variance. In that case, all bets are open whether LOO or $k$-fold has more additional variance*. But you can iterate the $k$-fold CV and taking the grand mean over all test cases and all $i \times k$ surrogate models can mitigate that additional variance. There is no such possibility for LOO: the $n$ surrogate models are all possible surrogate models.
The large variance is usually due to two factors:
For classification errors, there's a number of papers that looks at the properties of different resampling validation schemes in which you also see variances, e.g.:
(I guess similar papers may exist for regression errors as well, but I'm not aware of them)
* one may expect LOO to have less variance because the surrogate models are trained with more cases, but at least for certain types of classification models, LOO doesn't behave very well.
There are no folds in LOOCV like k-Fold Cross validation(actually they can be name as folds but meaningless). in LOOCV what it does is leave one Instance from the whole dataset for test data and use all other instances for training. So in each iteration it will leave one instance from the dataset to test.So in a particular iteration of evaluation there is only one instance in the test data and rest are in training data.that is why you saw all the training data sets equal all the time.
In K-fold Cross validation by using Stratification(an advanced method use to balance the data set ensuring that each class represents approximately in equal proportion in all the samples) we can reduce the variance of the estimates.
as LOOCV is using only one instance for testing, it cannot apply Stratification.So LOOCV has a higher variance in error estimates than k-fold cross validation.
It's like taking a test with just one question - it's a lot more hit-and-miss.
This is an intuitive explanation of the standard deviation of an instance versus that of a mean - the score on a batch of instances has less variance.
Here are some more details.
