Why does the CV estimate of Test Error Underestimate Actual Test Error?

Question

It is my understanding that the k-fold cross-validation estimate of test error usually underestimates actual test error. I’m confused why this is the case. I see why the training error is usually lower than the test error - because you are training the model on the very same data that you are estimating the error on! But that isn’t the case for cross-validation - the fold that you measure error on is specifically left out during the training process.

Also, Is it correct to say that cross-validation estimate of test error is biased downward?

Answer 1

To give an example: reporting only the CV error of a model is problematic in case you originally have multiple models (each having a certain CV error and error variance), then use this error to chose the best suited model for your application. This is problematic because with each model you still have a certain chance that you are lucky/unlucky (and obtain better/worse results) - and by choosing a model, you likely also chose the one where you were more lucky. Therefore, reporting this error as final error estimate tends to be overly optimistic.

If you want to dig deeper into the details: this answer links to some easy-to-read papers on this problem: Cross-validation misuse (reporting performance for the best hyperparameter value)

As @cbeleites points out: this is problematic in case one uses the obtained k-fold CV error to e.g. a) chose a best model out of multiple models from using e.g. different hyperparameters, which is part of the training process, and b) then reports the same error as test error instead of using a separate, held-back test set. If you instead intended to ask for the pure CV error itself - without using it to chose any model - the answer by @cbeleites is more likely what you are searching for.

Answer 2

No, if done properly, $k$-fold cross validation tends to overestimate generalization error, i.e. it has a (usually slight) pessimistic bias. That is, it gives an unbiased estimate of the generalization error for the surrogate model in question. But as the error of the model decreases with increasing training sample size (aka learning curve), the surrogate model on average has (slightly) higher true generalization error than the model trained on the whole data set - which is the model whose error is approximated by the cross validation.

Done properly roughly means that the splitting into test and training sets within the cross validation actually leads to test cases that are truly independent of the model.

However, there are a number of pitfalls that compromise this independence. Depending on how severely the test data is compromised and how much the model is overfit, this lack of independence means that the cross validation error becomes in fact a training error. I.e., all in all, you may end up with a severe optimistic bias (underestimating the actual generalization error).
IMHO it is important to understand that most of these pitfalls are not unique to cross validation but are better characterized as wrong splitting into train and test set: they can (and do) happen just the same with other validation schemes such as hold out or independent test sets that in fact are not as independent as one supposes.

Here are examples of the most common mistakes in splitting I see:

• @geekoverdose's answer gives an example of blatantly using an internal training (!) error estimate as test error.
  More general, any kind of error estimate used for data-driven model optimization is a training error as there is still training going on using this error estimate.
• Confounding variables not taken into account for the splitting.
  One row in the data matrix does not necessarily constitute an independent case, e.g.
  • Treating repeated measurements of the same case/subject/patient as "independent"
  • in general overlooking/ignoring strong clustering in the data
  • not being aware of ongoing drift in the data generating process (future unknown cases vs. just unknown cases), ...

---

Answer 3

First let me be clear the terms used in the question as I understand. We normally start with one training dataset, use k-fold cross validation to test different models (or sets of hyperparameters), and select the best model with lowest CV error. So the 'cross-validation estimate of test error' means using the lowest CV error as test error, not just a random model's CV error (which the case discussed by cbeleites , but it is not what we normally do.). The 'actual test error' in question is error we get when applying the best CV model to infinite test dataset, assuming we can get that. CV error is dependent on the particular dataset we have, and actual test error is dependent on best CV model selected , which is also dependent on the training dataset. So the difference between the CV error and test error is dependent on different training datasets. Then the question become , if we repeat above process many times with different training datasets and average the two errors respectively , why the average CV error is lower than average test error, ie CV error is biased downward? But before that , does this always happen?

Normally it is impossible get many training datasets and test dataset containing infinite rows. But it is possible to do so using data generated by simulation. In " chapter 7 Model Assessment and Selection" of the book "The Elements of Statistical Learning" by Trevor Hastie, et al. , it includes such simulation experiment.

The conclusion is that, using CV or bootstrap, "... estimation of test error for a particular training set is not easy in general, given just the data from that same training set". By 'not easy', they mean the CV error could be either underestimate or overestimate the true test error depending on different training data sets, ie variance caused by different training datasets is pretty big. How about bias? The kNN and linear model they tested are almost not biased: CV error overestimate the true test error by 0-4%, but some models "like trees, cross-validation and boot-strap can underestimate the true error by 10%, because the search for best tree is strongly affected by the validation set".

To sum up, for a particular training dataset, the CV error could be higher or lower than the true test error. For the bias, expected CV error could range from a little bit higher to much lower than expected true test error depending on the modeling methods.

The reason for the underestimation, as mentioned above, is that selection of hyperparameters for best model is ultimately dependent on the particular training dataset we get. The information in validation dataset could somehow flow into model fitting process. On the other hand, CV error could also a little bit overestimates true test error, as discussed by cbeleites. This is because k fold CV error is obtained by using a little bit less training data to train the model (for 10 fold cv, use 90% data), it is biased upward against true error, but not much. So there are two biases going different directions. For modeling method tends overfit,using less fold CV, eg 5-fold vs 10-fold,might result in less bias.

All being said, it does not help too much in practice: we usually only get one 'particular' dataset. if we hold out 15% to 30% as test data ,and select best model by CV on the rest as training data, chances are CV error will be different from test error as both differ from expected test error. We might be suspicious if the CV error is much lower than test error, but we will not know which one is closer to the true test error. The best practice might be just to present both metrics.