High variance of leave-one-out cross-validation

I read over and over that the "Leave-one-out" cross-validation has high variance due to the large overlap of the training folds. However I do not understand why that is: Shouldn't the performance of the cross-validation be very stable (low variance) exactly because the training sets are almost identical? Or am I having a wrong understanding of the concept of "variance" altogether?

I also do not fully understand how LOO can be unbiased, but have a high variance? If the LOO estimate is equal to the true estimator value in expectancy - how can it then have high variance?

Note: I know that there is a similar question here: Why is leave-one-out cross-validation (LOOCV) variance about the mean estimate for error high? However the person who has answered says later in the comments that despite the upvotes he has realized that his answer is wrong.

• I am that person :-) but please note that, first, I have already some time ago updated my answer to remove the confusion, and, second, that whole thread is closed as a duplicate of another thread: stats.stackexchange.com/questions/61783. Did you look there? Your Q seems to me to be a duplicate of that one too. If you are unhappy with the answer given there, consider formulating your question more specifically. Right now I will vote to close, but feel free to edit your Q. – amoeba Oct 23 '15 at 16:48
• – amoeba Oct 23 '15 at 16:49
• Well, that's easy: let the true value of a parameter be $0.5$. An estimator that yields $0.49, 0.51, 0.49, 0.51...$ is unbiased and has relatively low variance, but an estimator that yields $0.1, 0.9, 0.1, 0.9...$ is also unbiased but has much higher variance. – amoeba Oct 23 '15 at 16:58
• Regarding your first paragraph: you need to think about the variance across different realizations of the whole dataset. For a given dataset, LOOCV will indeed produce very similar models for each split because training sets are intersecting so much (as you said), but these models can all together be far away from the true model; across datasets, they will be far away in different directions, hence high variance. That's how I qualitatively understand it. – amoeba Oct 23 '15 at 16:58
• @amoeba, why not turn those comments into an official answer? – gung Oct 23 '15 at 18:09

This question is probably going to end up being closed as a duplicate of Variance and bias in cross-validation: why does leave-one-out CV have higher variance?, but before it happens I think I will turn my comments into an answer.

I also do not fully understand how LOO can be unbiased, but have a high variance?

Consider a simple example. Let the true value of a parameter be $0.5$. An estimator that yields $0.49,0.51,0.49,0.51...$ is unbiased and has relatively low variance, but an estimator that yields $0.1,0.9,0.1,0.9...$ is also unbiased but has much higher variance.

Shouldn't the performance of the cross-validation be very stable (low variance) exactly because the training sets are almost identical?

You need to think about the variance across different realizations of the whole dataset. For a given dataset, leave-one-out cross-validation will indeed produce very similar models for each split because training sets are intersecting so much (as you correctly noticed), but these models can all together be far away from the true model; across datasets, they will be far away in different directions, hence high variance.

At least that's how I understand it. Please see linked threads for more discussion, and the referenced papers for even more discussion.

• So, as I understand it, low bias is given because the training set is very large - almost identical with the entire dataset (as only one data sample is left out for testing). So, for one particular dataset we can expect a very good estimation. However, because of this high correlation of the folds (the crossvalidation is almost performed on identical data in its iterations) , the estimation is also very specific for this particular dataset, resulting in high variance between the performance on different datasets from the same underlying distribution. Correct? – Pegah Oct 23 '15 at 21:24
• I think it is mostly correct, but one should be careful saying that for one particular dataset we can expect a very good estimation. I guess one can interpret it as meaning that estimation of some dataset-specific parameter will be good. But in general cross-validation is supposed to estimate a population parameter: how well a certain type of model can make predictions about the dependent variable in the population; and we can not expect a very good estimation of it by LOOCV, because of what you wrote (the estimate is very specific for this particular dataset). – amoeba Oct 23 '15 at 21:34
• I should add a caveat that all of that is my current understanding, but in general I find this topic quite tricky and my experience with cross-validation is limited. I am not an expert. – amoeba Oct 23 '15 at 21:36
• May I ask why you find it tricky? I am curious since this might teach me something about where to be careful when it comes to CV or where to deepen my knowledge – Pegah Oct 23 '15 at 21:37
• Given the accepted answer in this thread, perhaps you no longer need to mention high variance of LOOCV in this answer, namely, hence high variance? I have thought about these questions for a while and could not come up with any theoretical reason for the high variance of LOOCV in continuous ("continuous"?) regression problems, though I see Paul's point in the comments in the linked thread that LOOCV fails if your sample contains duplicates of each point. – Richard Hardy May 23 at 16:23

This high variance is with respect to the space of training sets. Here is why the LOOCV has high variance: in LOOCV, we get prediction error for each observation, say observation i, using the whole observed dataset at hand except this observation. So, the predicted value for i is very dependent on the current dataset. Now assume we observe another independent dataset and fit a model on this new dataset. If we use this new model to get a predicted value for the observation i, the predicted value is potentially very different from the one evaluated by LOOCV (although correct on average (unbiased)).

This is the intuition behind the high variance of error prediction in LOOCV.

However, if you're using LOOCV to compare results of a model with different hyperparameters, I believe you can safely use LOOCV to estimate prediction errors, provided the true value of prediction error is not of your interest, that is, you just want to compare different models having the observed training set and you don't care about the actual true error to be estimated.

That said, as a rule of thumb, if you have a small sample, use LOOCV, otherwise, use k-fold CV with a smaller value for k.