# Does changing the parameter search space after nested CV introduce optimistic bias?

Suppose I am fitting a Ridge and I decide to search a parameter space for c:[1,2,3]. I perform nested CV on my whole dataset and find the performance not so great. I therefore expand my search space to c:[0.5,1,1.5,2,2.5,3,3.5,4].

Can I just repeat nested CV now and expect a fair estimate of generalization error? If not, what to do? It seems that I have changed my parameter space (which is a part of the modeling process) based on knowledge I now have from using the whole dataset in nested CV, and therefore need to evaluate on a dataset external to my current dataset rather than using nested CV on the same dataset. I am not "choosing" parameters explicitly based on the test data, but I am allowing for their choice based on the testing data. Should I perform nested CV on a subset of the data to find good parameter spaces and then repeat on the full data? It seems that doing so would still allow the algorithm to see some of the data while choosing parameters and in worst case that "some" of the data randomly finds its way into every test fold upon repeated nested CV.

For CV to give an unbiased estimate, every step of the modeling process must be repeated independently in each fold. Isn't selection of a search space for hyperparameters a "step" in the modeling process?

First of all, you are right that the choice of search space is a (though somewhat indirect) modeling choice and thus any data that you use to arrive at this choice was used for training.

However, you could have gotten around this issue by finding with the inner CV that the performance was not great, or e.g. that the optimum is at the border of your search space. In that case, you could have widened the search space in the inner CV and the outer would still have been independent of that change in the training procedure. OTOH, if the inner CV and optimization (as far as you can tell from within) look nice, but the outer CV is terrible, then you know you ran into severe overfitting. This probably means that you'd need to completely rethink your approach.

Also, you could formulate the hyperparameter tuning in a way that is still more automatic: if the apparent optimum is at the boundary of the search space, search space should be widened in that direction. Or, once you roughly locate the optimum, perform a finer search there. If you go this direction, you'll soon reinvent typical numeric optimization algorithms ;-)

However, the drawback in our context is that the variance on the performance estimates and limits the possiblity to make meaningful comparisons. Increasing the number of models that are compared, you also increase the risk of skimmig that variance, i.e. overfitting: you pick models that accidentally look well with the given test sets.

• Thanks again @cbeleites. I am assuming that in order to change the parameters based on the inner CV it is important to not change the data subjected to inner CV (eg, there must be a random seed so that new data is not selected each time the nested CV is run)? If so, my plan is to set this seed and then simply hide the outer CV results until I am satisfied with the inner CV results. However it seems that I cannot re-run another iteration of nested CV (with a different seed) since the outer cv test set may now contain cases from the inner fold used to find parameter search space.
– sjw
Jun 7, 2017 at 17:46
• yes. You may be approaching a situation where a single outer test set (kept in a separate file until finally needed) may be the more practical approach - even though it is less efficient in terms of making best use of your samples. Nested cross validation does need automation in the inner tuning. Everything else is going to be slave work. Jun 8, 2017 at 18:12
• follow up: say we perform nested CV with 10 observations. In the first fold, the inner CV uses cases 1-6 and the outer 7-10. On the first fold the optimal hp is at the border, so we expand our search space (for all the folds). In the second fold, however, the inner CV is 5-10 and the outer 1-4. The outer estimate of the second fold will now be optimistic because cases 1-4 were used to make a decision in the previous fold? Does this mean that every major fold must have it's own search space and changes to this search space must be made ignoring inner results from other folds?
– sjw
Jun 19, 2017 at 12:52
• If you just expand the search space for the one fold under consideration, you avoid this problem. Consider a function train_and_tune that does the inner CV, and, if necessary expands search space as needed. train_and_tune works independently for all outer folds. If your tuning is stable, all those independent runs of train_and_tune will result in the same (very similar) tuned models. If those models vary all over the place, you found a problem. But at least the related bad outer performance is an honest estimate of performance (i.e. a proper judgment of a failed optimization) . Jun 19, 2017 at 16:17