Question
Suppose you want to evaluate the out-of-sample performance of $M$ unknown models with data from an $N$ (independent) observation dataset. However, $M$ are only known after comparing the out-of-sample performance of $Z$ models using the same dataset. Only a single dataset is available, but you can use up to $N$ observations at each stage and can use observations more than once as desired.
What approaches to evaluating out-of-sample performance would provide valid and reliable model comparisons at both stages? Presumably some sort of cross-validation, but what kind? Note that I don't mean model fit criteria.
A Motivating Scenario
You want to evaluate the out-of-sample performance of Z regression models. As you only have 1 dataset of N independent observations, you turn to cross-validation (CV) to determine which 1 of the Z models performs best. The CV method - let's call it X - can be any method: k-fold CV, nested CV, holdout, etc. X can be a method that uses all or only part of your data.
Reviewing the results, you find that models with a certain feature outperform all others. Given this information, you realize M other models with this feature might have performed even better! You know it's bad to evaluate the performance of these new models on the (portion of) data you just used - after all, you conditioned your choice of new models on the performance of the old models which conditioned on (some part of) the data. However, it's the only dataset you can use.
If you had known in advance that you would want to fit models conditional on a first stage of comparisons, what would you have chosen for X?
