# Why cross-validation gives biased estimates of error?

I came across many posts on CrossValidated discussing cross-validation and nested cross-validation as an alternative (e.g. here or here). I don't quite understand why 'ordinary' K-fold cross-validation gives biased estimates of error which is the reason why we need nested cross-validation to evaluate performance of the chosen model in a reliable (unbiased) way.

In all these posts about cross-validation there is emphasis on the difference between hyperparameter tuning (model selection) and estimation of generalization performance. But what is the difference here? Why can't I use 'ordinary' K-fold cross-validation for the two tasks of model selection and estimation at once? The way I understand it is that model selection is related to estimation of performance because choosing the best model we base our assessment on some metrics such as MSE which is used to assess performance.

Where is that bias coming from? We train different models on $$K-1$$ sets and then evaluate performance on the remaining set which wasn't used for training so it should give us a good estimate of performance, shouldn't it? All $$K$$ sets used for validation are independent. We don't use the same set for training and validation. I see that in case we perform repeated cross-validation the validation sets are not independent in different repetitions and standard errors of the mean error will be too low but I can't really see how that approach would give us biased estimates.

Is there anything wrong with this reasoning? If so, why? Maybe the source of bias is somewhat tricky and I can't see it.

• Think about tuning the random seed: if you choose the one with highest cross-validation performance, then the cross-validation performance will certainly be overstated just by chance. Commented Jul 31, 2020 at 17:29
• @MichaelM But let’s say we don’t tune any hyperparameters and we have some model we have to fit to the data. We just want to check its performance. Can we use k-fold CV? Will it give unbiased estimate of error if I calculate the mean from all K validation sets? It’s the same situation but without any tuning. Maybe the problem is that to me there is no difference between model selection and performance because we select the best model assessing its performance. I just can’t see the difference. Commented Jul 31, 2020 at 18:56
• Intuitively, I'd say the x-validation performance would be unbiased for independent rows and without tuning. However, I remember an issue with leave-one-out x-validation, tending to biased results. I have never understood why, I must admit. Commented Jul 31, 2020 at 19:10
• imagine you don't do training or have any hyper parameters, but randomly initialise model each time. then in cross validation you choose the (randomly initialised) model that gives the best performance on your crossvalidation set. is the performance estimate for this model (on crossvalidation set) a good estimate of future performance? can you see that the act of choosing the best model on the crossvalidation set biases the estimation of generalisation error? Commented Aug 9, 2020 at 18:17

The CV error for the best model is optimistic because the model was chosen precisely to minimise that error. If $$\widehat{\text{Err}}_i$$ is the CV error of the $$i$$-th model, then

$$\mathbb{E}[\min\{\widehat{\text{Err}}_1, ..., \widehat{\text{Err}}_m\}] \le \mathbb{E}[\widehat{\text{Err}}_i]$$

for all $$i$$.

If you don't do model selection, then the problem is perhaps more subtle. Namely, the fact that the quantity that is approximated is not the error of the given model as trained on a fixed dataset, but the expected generalization error over all possible datasets of the given size. In other words, CV approximates

$$\text{Err} := \mathbb{E}_{D \sim \mathbb{P}^n_{X Y}} [ \mathbb{E}_{X Y}[\text{loss}(f_D(X),Y)|D]],$$

where the training set $$D$$ itself is random, instead of what one might want:

$$\text{Err}_{X Y} := \mathbb{E}_{X Y}[\text{loss}(f_D(X),Y)|D],$$

for a fixed dataset $$D$$.

But even for $$\text{Err}$$, since CV splits in, say $$K$$, folds, the actual expectation approximated is wrt to $$D \sim \mathbb{P}^{\frac{K-1}{K} n }_{X Y}$$, so there is some bias wrt. $$\text{Err}$$. Of course as $$K/n$$ decreases this can become irrelevant.

Other sources of error in CV are the dependencies in the error terms for each test sample: because of the common training split and because of the dependence among different training splits there is variance which cannot be estimated using the empirical standard error of the individual losses at each test sample. This is the reason why common confidence intervals are bogus and have poor coverage. See this recent paper [1] for a nested procedure which provides good confidence intervals using a nested procedure.

[1] Bates, Stephen, Trevor Hastie, and Robert Tibshirani. ‘Cross-Validation: What Does It Estimate and How Well Does It Do It?’, 1 April 2021.

• "Other sources of error in CV are the dependencies in the error terms for each test sample..." Are you talking about the sources of error in the performance metric estimate or the sources of error in the estimation of variance of the performance metric estimate? I believe it must be the latter. Commented May 5, 2023 at 4:39
• Yes, the latter. Here's a blog post I wrote about the paper linked above where these ideas are hopefully explained better. Commented May 9, 2023 at 10:13

Can it be related with the fact that your observations may not be independent? Imagine you are predicting if a given chemical mixture of two components will explode or not, based on the properties of the two components. A certain component A may appear in diverse observations: you can have it in a mixture of A+B, A+C, A+D, etc. Now, imagine that you use k-fold validation. When the model is predicting for the A+C mixture, maybe it was already trained with the observation "A+B", therefore, it will be biased towards the output of that observation (because half of the variables of the two observations are the same: in one you have the properties of A and the properties of C, and in the other one you gave the properties of A and the properties of B).