Overfitting the (non-nested) cross validation set

Question

This is a follow up query to this query

In one line: I wish to understand why is it that we will severely over fit the cross validation set (and hence need nested cross validation to correctly account for the optimism in non-nested cross validation procedure) if we keep on increasing model complexity.

Here is a paper which talks about non-nested (flat) cross validation and nested cross-validation:

Jacques Wainer, Gavin Cawley, "Nested cross-validation when selecting classifiers is overzealous for most practical applications", Expert Systems with Applications, Volume 182, 2021. (www)

Background:

1. Reason for training optimism: This one is easy. If we train on a set by making the model more and more complicated we will perfectly learn the noise in the dataset and the learning curve will monotonically decrease to 0.
2. Reason for validation set optimism: This one is harder to comprehend and is explained in the query I pointed to at the beginning of this query. Basically, the validation set may have the same kind of noise as is learned by one of the candidate models. This may lead to over or under fitting the original data set.
3. Reason for cross validation set optimism: This is my main query. We do k fold cross validation. We split the data into k folds - we train on k-1 folds and test on the k-th fold. This has a signature like Training optimism (please see simulation below). What do I mean by that? The learning curve of the training error on the trained cross validation folds (k in number) is monotonically decreasing to zero just like in Case 1. Can someone please show me how to convince myself that the CV procedure will overfit the training set of k folds ?

There is a simulation here:

Figure 2 of:

Gavin C. Cawley, Nicola L. C. Talbot, "On Over-fitting in Model Selection and Subsequent Selection Bias in Performance Evaluation", Journal of Machine Learning Research, 11(70):2079−2107, 2010. (www)

My attempt: We train on k-1 folds and as we increase the complexity of the model we will completely learn the noise in the k-1 folds, but as we increase the complexity, how do I say that we will completely learn the noise in the k-th fold? Maybe we have the same kind of sample in the kth fold as learnt by a model in the k-1 folds, but that will happen only for some folds. How can I mix the reasoning in 1 and 2 to create the reason for item 3?

Also, a related query, Section 2.1 of the above paper by Cawley and Talbot says:

The average of the generalisation performance observed over all k folds provides an estimate (with a slightly pessimistic bias) of the generalisation performance of a model trained on the entire sample.

How do I prove the above ?

Edit:

I am trying to understand why we need Nested cross validation and the reason for optimism in flat cross validation. I do see that the hyper parameters are tuned on a certain set and the accuracy on the same set is being reported by flat cross validation. I wish to work it out for a small example. Suppose I have decided to fit polynomials to a data set. I have one hyper parameter which is the degree of the polynomial. We do 6 random splits - train/test of 50% each. We train models from n=1 to n=10. Suppose the true n=5. We may by chance have data in ALL the test splits from the model with n=3(too simple a sample)/n=7(too complicated a sample) (unlikely but with non-zero probability). Hence the model chosen by flat cross validation will underfit / overfit(it will learn the same kind of noise). This may be discovered by taking an extra sample as nested-cross validation does and measuring the error on that. Query : Is there any difference in optimism due to model selection vs optimism due to hyperparameter tuning ? They seem the same to me.

Answer 1

We may do model selection OR hyper-parameter tuning using non-nested cross validation.

1. Model selection vs Hyper Parameter tuning.

Suppose we are doing model selection. Then we train on k-1 folds and select on the kth fold. In that case the kth fold may have the "same kind of noise in the parameters" as learned by one of the candidate models and we will overfit the kth fold.

Suppose we are doing hyper parameter tuning. In that case, as you say in the comments above, the chosen hyper parameter may work only on the kth fold.

In this can I say that the kth fold has the "same kind of noise in the hyper parameters" as that of one of the models(namely the chosen model) ?

2. Over-fitting the non-nested cross-validation set.

In either case above, since we over-fit the k-th fold we will have an optimistic view of the error in the k-th fold.

The above will happen for each k and when we average the error over all k folds then the average will again be optimistic.

That is why we over fit the non-nested cross validation set.

Hence we need nested cross validation to find the true error rate.

Did I understand right ?