# Are cross-validated prediction errors i.i.d?

Say, we test an arbitrary regression or classification procedure on $n$ independent samples with leave-one-out cross-validation. This results in an estimate of the prediction error $e_n$ for each sample $n$.

Can these $e_n$ be assumed to be independent draws of a (probably unknown) distribution?

My intuition says no, because (1) the training set is almost the same for each test sample, and (2) samples are used for both, training and testing.

If my intuition is wrong, and errors are independent, what about k-fold cross-validation, where the same training set is used for groups of $n/k$ samples?

Disclaimer: I tried to ask this question as concisely and generally as possible. If it lacks detail or specifity, please comment and I will update the question accordingly.

I think you need to be clear what distribution you need to represent. This differers according to what the cross validation is meant for.

• In the case that the cross validation is meant to measure (approximate) the performance of the model obtained from this particular training set, the corresponding distribution would be the distribution of cases in the training set at hand. From that perspective, you draw almost the entire population, though without replacement.

• In contrast, if you are asking about the distribution of $n$ cases drawn from the population the training set was drawn from, then the cross validation resampled surrogate training sets are correlated. See e.g. Bengio, Y. and Grandvalet, Y.: No Unbiased Estimator of the Variance of K-Fold Cross-Validation Journal of Machine Learning Research, 2004, 5, 1089-1105.
This is important for comparisons which algorithm performs better for a particular type of data.

• I was not aware of this difference. Thanks for the link to the paper, I will read it. Did I understand this correctly so far: To measure the performance of a specific data set no specific care needs to be taken other than sampling without replacement (e.g. hypergeometric distribution for classification results). If, however, we want to get an idea of the performance on the whole population the situation is more complicated? Also, I suppose that the second case applies if I want to know how the model will perform on unseen samples?
– MB-F
Jan 24, 2015 at 9:11
• a) You need to take more care, but those considerations were not the topic here. b) prediction about training on completely other samples is more complicated, yes. c) how the model will perform on unseen samples: no, this is case 1: that's bwhat resampling is for. Jan 24, 2015 at 19:05
• Thanks for the clarification. So basically results are dependent in both cases - in case 1 because of sampling without replacement, and in case 2 because of complicated?
– MB-F
Jan 25, 2015 at 8:59
• I'd have said in case 1 because sampling > half the population will create dependence - but notice that this dependence is in favor of being representative, wheras the usual concern about dependence is about not being representative. Case 2 is complicated, but it is IMHO actually a good example of the "dependent" one is afraid of: in the end this dependence is one way of realizing that there is no way around the fact that only $n$ real cases are available. Jan 26, 2015 at 9:01

They can't be independent. Consider adding one extreme outlier sample, then many of your cross validation folds will be skewed in a correlated way.

• +1 straight and to the point. Sounds reasonable too. Yet, I could imagine that the outlier simply changes the distribution of $e$ without making the samples correlated. Could you elaborate on that?
– MB-F
Jan 23, 2015 at 16:08