Suppose I have decided to evaluate the following model selection procedure (let's call it PROC(1) )


For alpha in [0,1,2...1000]: Get the K-fold cross validation error of M(alpha) (the model parametrized by the hyperparameter alpha)

Pick alpha* such that M(alpha*) had the best cross validation error. Fit M(alpha*) on the full data.


We know the cross-validation error of M(alpha*) is going to be biased upwards compared to the true generalization error of PROC(1) because PROC(1) was used on the entire data.

Thus, we need to use nested cross validation to get an estimate of the generalization error of PROC(1). Let us supposed we apply cross validation to PROC(1) and determine that it is not a good model selection procedure. We could try another procedure, call it PROC(2) (perhaps expanding or narrowing the grid of hyperparameters, increasing or decreasing the family of models) and estimate its generalization error.

The problem is that if we select the best procedure from {PROC(1),PROC(2)...PROC(M)}, the nested cross validation applied to the select procedure, PROC(J) will no longer be unbiased. Thus it would seem like we would need to apply nested nested cross validation but this would cause another problem (which subset of PROCEDURES to use?)

And it seems unrealistic to hope to get the best PROC on the "first try," so to speak. So what are the strategies for dealing with this issue?


I had a brief exchange about this issue with Fred Shic when he was on my thesis committee. I had mentioned in passing in my thesis that I was trying only a few models because if I tried a very large number, without using an outer cross-validation loop as you've suggested or something else, then some might happen to do well by chance. Shic replied (personal correspondence, 10 Sep 2015):

The MCP issue [i.e., the multiple-comparison problem] holds strongly for independent IVs, but given that these are all classes of optimizers, they are unlikely to be completely independent, and actually are more likely to be highly correlated in terms of performance. While I agree that there is an issue of "pseudo-overfitting" due to looking at too many models, it's not the same issue as mining for a statistically significant effect[…]

In any case, this was a minor point, and you are not wrong.. you don't want to put in a trillion random fit programs because as you mentioned one of those will magically hit the great training and validation performance. In practice, this is unlikely unless you're really trying to go for it.

So I think the answer is that this should only be a real problem if you fit a very large number of PROCs. You can avoid this by adding only qualitatively different PROCs; for example, one might be a random forest and another a support vector machine. If you want to adjust a detail such as the grid of hyperparameter values, treat that as another hyperparameter for an existing PROC (or modify the PROC in place) instead of creating a new PROC and pitting it against the old one on ostensibly equal terms.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.