When is nested cross-validation really needed and can make a practical difference?

When using cross-validation to do model selection (such as e.g. hyperparameter tuning) and to assess the performance of the best model, one should use nested cross-validation. The outer loop is to assess the performance of the model, and the inner loop is to select the best model; the model is selected on each outer-training set (using the inner CV loop) and its performance is measured on the corresponding outer-testing set.

This has been discussed and explained in many threads (such as e.g. here Training with the full dataset after cross-validation?, see the answer by @DikranMarsupial) and is entirely clear to me. Doing only a simple (non-nested) cross-validation for both model selection & performance estimation can yield positively biased performance estimate. @DikranMarsupial has a 2010 paper on exactly this topic (On Over-fitting in Model Selection and Subsequent Selection Bias in Performance Evaluation) with Section 4.3 being called Is Over-fitting in Model Selection Really a Genuine Concern in Practice? -- and the paper shows that the answer is Yes.

All of that being said, I am now working with multivariate multiple ridge regression and I don't see any difference between simple and nested CV, and so nested CV in this particular case looks like an unnecessary computational burden. My question is: under what conditions will simple CV yield a noticeable bias that is avoided with nested CV? When does nested CV matter in practice, and when does it not matter that much? Are there any rules of thumb?

Here is an illustration using my actual dataset. Horizontal axis is $\log(\lambda)$ for ridge regression. Vertical axis is cross-validation error. Blue line corresponds to the simple (non-nested) cross-validation, with 50 random 90:10 training/test splits. Red line corresponds to the nested cross-validation with 50 random 90:10 training/test splits, where $\lambda$ is chosen with an inner cross-validation loop (also 50 random 90:10 splits). Lines are means over 50 random splits, shadings show $\pm1$ standard deviation.

Red line is flat because $\lambda$ is being selected in the inner loop and the outer-loop performance is not measured across the whole range of $\lambda$'s. If simple cross-validation were biased, then the minimum of the blue curve would be below the red line. But this is not the case.

Update

It actually is the case :-) It is just that the difference is tiny. Here is the zoom-in:

One potentially misleading thing here is that my error bars (shadings) are huge, but the nested and the simple CVs can be (and were) conducted with the same training/test splits. So the comparison between them is paired, as hinted by @Dikran in the comments. So let's take a difference between the nested CV error and the simple CV error (for the $\lambda=0.002$ that corresponds to the minimum on my blue curve); again, on each fold, these two errors are computed on the same testing set. Plotting this difference across $50$ training/test splits, I get the following:

Zeros correspond to splits where the inner CV loop also yielded $\lambda=0.002$ (it happens almost half of the times). On average, the difference tends to be positive, i.e. nested CV has a slightly higher error. In other words, simple CV demonstrates a minuscule, but optimistic bias.

(I ran the whole procedure a couple of times, and it happens every time.)

My question is, under what conditions can we expect this bias to be minuscule, and under what conditions should we not?

• I'm not too sure I understand the diagram, could you generate a scatter plot showing the estimated error from nested and non-nested cross-validation on each axis (presuming the 50 test-training splits were the same each time)? How big is the dataset you are using? Oct 23, 2015 at 13:19
• I generated the scatter plot, but all the points are very close to the diagonal and it's hard to discern any deviation from it. So instead, I subtracted simple CV error (for optimal lambda) from the nested CV error and plotted that across all training-test splits. There does seem to be a very small, but noticeable bias! I made the update. Let me know if the figures (or my explanations) are confusing, I'd like this post to be clear. Oct 23, 2015 at 16:36
• In the first paragraph, you have the model is selected on each outer-training set; should it perhaps be inner- instead? Mar 11, 2017 at 12:21
• @RichardHardy No. But I can see that this sentence is not formulated very clearly. The model is "selected" on each outer-training set. Different models (e.g. models with different lambdas) are fit on each inner-training set, tested on inner-test sets, and then one of the models is selected, based on the whole outer-training set. It's performance is then assessed using outer-testing set. Does it make sense? Mar 11, 2017 at 22:06

1 Answer

I would suggest that the bias depends on the variance of the model selection criterion, the higher the variance, the larger the bias is likely to be. The variance of the model selection criterion has two principal sources, the size of the dataset on which it is evaluated (so if you have a small dataset, the larger the bias is likely to be) and on the stability of the statistical model (if the model parameters are well estimated by the available training data, there is less flexibility for the model to over-fit the model selection criterion by tuning the hyper-parameters). The other relevant factor is the number of model choices to be made and/or hyper-parameters to be tune.

In my study, I am looking at powerful non-linear models and relatively small datasets (commonly used in machine learning studies) and both of these factors mean that nested cross-validation is absolutely neccsesary. If you increase the number of parameters (perhaps having a kernel with a scaling parameter for each attribute) the over-fitting can be "catastrophic". If you are using linear models with only a single regularisation parameter and a relatively large number of cases (relative to the number of parameters), then the difference is likely to be much smaller.

I should add that I would recommend always using nested cross-validation, provided it is computationally feasible, as it eliminates a possible source of bias so that we (and the peer-reviewers ;o) don't need to worry about whether it is negligible or not.

• If you use all of the data, then isn't it is effectively plotting the training set error? Quite often I use classification models where the best models have zero training set error but non-zero generalisation error, even though the regularisation parameter is carefully chosen. Oct 23, 2015 at 17:26
• A few thousands of training patterns or less. What kind of model are you using? As the dataset gets larger, the statistical problems diminish and the computational problems increase, as a general rule. k-fold cross-validation is only k times slower than fitting the basic model (including hyper-parameter tuning), so it rarely goes from being feasible to infeasible. k-fold cross-valdiation is also easily parallelised, which is what I usuall do. Jun 8, 2017 at 9:03
• It just gives an unbiased performance estimate. Essentially nested CV estimates the performance of a method of fitting a model including model selection via cross-validation. To get the operational model, we typically just repeat the method using the whole dataset, which gives the same model choices as the "flat" cross-validation procedure. Jun 16, 2018 at 19:22
• I also came across the issue of nested CV. Using the unbiased nested CV involves fitting models with smaller data. For 10-fold CV, it's like 81% in nested CV vs. 90% in non-nested CV. Also test fold becomes 9% vs 10% in non-nested. Does that generate extra variance in model evaluation? Especially for small datasets, like 350 samples in this post. Is this the 'disadvantage' using nested CV? If so, how should we decide whether to use nested CV vs. the size of dataset? Really appreciate opinion from expert like you on this issue. Is there any paper related to this issue? @Dikran Marsupial Jan 18, 2019 at 17:41
• @zesla Yes, that is indeed the case that there is less data for the inner cross-validation, which will raise its variance, however the final model is built using the entire dataset (including hyper-parameter estimation). There is always a tradeoff between bias and variance in performance estimation. It is most important to use nested cross-validation if the dataset is small as over-fitting in model selection & bias is more of a problem. In practical applications, where there are few hyper-parameters the difference may be of little practical significance arxiv.org/abs/1809.09446 . Jan 22, 2019 at 11:38