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

Question

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?

Answer 1

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