# Nested Cross Validation: Choosing between different best hyperparameters

I know this sort of question has been asked many times, and several answers have been already provided on this platform too (e.g., here, here, and here). Still, there is something about the idea behind nested cross validation that I don't quite get.

Let me first start with the problem setting, which by the way I think is quite common across machine learning practitioners. Apologize in advance for the long message and for the notation/terminology I'm gonna use in the following, as this might be somewhat sloppy or inaccurate.

Suppose we need to solve a classical supervised learning task, and to this end we are given with a labeled dataset $\mathcal{D}$. At this stage, I am assuming $|\mathcal{D}| = n$ is "large enough" for achieving our prediction task, whatever "large enough" might mean (first sloppiness, I know!)

Suppose also that we want to evaluate in terms of some metric a set of learning models $\mathcal{M} = \{M_1, M_2, \ldots, M_{|\mathcal{M}|}\}$. Think of each $M_i$ as one among Logistic Regression, SVM, Decision Tree, etc. Moreover, each $M_i$ has also its own set of hyperparameters, e.g., let $\mathcal{P}(M_i) = \{P_{i,1}, P_{i,2}, \ldots, P_{i,|\mathcal{P}(M_i)|}\}$ be the set of all the possible combinations of hyperparameters we want to test for the learning model $M_i$. For example, if $M_i$ = Logistic Regression a possible set of hyperparameters we may want to tune is a set of different values for the regularization hyperparameter $C$.

Clearly, in a setting like the one above there are 3 things we want to achieve:

1. For each learning model $M_i$, select the actual model whose hyperparameters (specific to that model) lead to the best performance
2. Among all the best $M_i$, select the one with the best performance overall
3. Once we select the best (of the best) model - let's call this $M^*$ - we want to evaluate it, i.e., provide a less biased estimate of the generalization error.

Now, as far as I understand, the scenario above is exactly the one where nested cross validation comes into play. The thing that is not totally clear to me is the following. Suppose that I have split the original dataset $\mathcal{D}$ in two datasets: $\mathcal{D}_{train}$ and $\mathcal{D}_{test}$ (e.g., 80÷20). Let's now focus on $\mathcal{D}_{train}$, and suppose we run nested cross validation only on that portion.

$\mathcal{D}_{train}$ will be therefore used for a $k_{out}$-fold outer cross validation run, and each of the $k_{out}$-folds will be in turn used for a grid search $k_{in}$-fold inner cross validation to test every possible hyperparameter combination of a given learning model $M_i$. This also means that on each run of the $k_{out}$-fold outer cross validation, I will use a different hyperparameter set. Therefore, at the end of the $k_{out}$-fold outer cross validation I would have an estimate of the model performance, which results from the average of $k_{out}$ estimates of generalization error (each one assumed to be obtained with the best hyperparameters found).

My question is: How could I use the information above (i.e., the outer cross validation error) to select the best hyperparameters (of a single $M_i$)? Should I go back to each individual $k_{out}$ error and pick the smallest one? But if that's the case, what's the point of having a cross validation run?

According to this, it seems that "If your model is stable, these m models should all have the same hyperparameter values, and you report the average performance of this model based on the outer test folds". Is there any theoretical result which support this claim? (i.e., that all the "best" hyperparameters turn out to be the same, and therefore each $k_{out}$ fold will be actually training $M_i$ with the same hyperparameters?). What if that doesn't hold?

Again, apologize for the extremely long message. I hope, though, that my question is clear enough. To put it in the simplest way possible, I guess this would be: Given a set of learning models and their associated hyperparameters, how would you perform nested cross validation in order to:

1. Perform hyperparameter selection on each single learning model (e.g., the best value of $C$ for Logistic Regression, the best value of $K$ for K-NN, etc.)
2. Perform learning model selection (i.e., among the best models found at step 1., should I pick Logistic Regression or K-NN?)
3. Estimate the generalization error of the best learning model as chosen at step 2.