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? Commented 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. Commented 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? Commented 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? Commented Mar 11, 2017 at 22:06