Why cross-validation gives biased estimates of error?

Question

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.

Answer 1

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.

Answer 2

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).