How to avoid overfitting bias when both hyperparameter tuning and model selecting? Say I have 4 or more algorithm types (logistic, random forest, neural net, svm, etc) each of which I want to try out on my dataset, and each of which I need to tune hyperparameters on.
I would typically use cross validation to try and tune my hyperparameters, but once tuned, how do I avoid generalization error from selecting the model family?
It would seem to me that the scores for each family would now have information leakage as the averaged tuned cv score has in a way seen the whole train set.
What is good practice here then? And how would it look differently between say a nested cross validation run or a simple cross validation with a final holdout?
Thanks!
 A: As @DikranMarsupial say, you need a nested validation procedure. In the inner e.g. cross validation, you do all the tuning of your model - that includes both choosing hyperparameters and model family.
In principle, you could also have a triply nested validation structure, with the innermost tuning the respective model family hyperparameters, the middle one choosing the model family and the outer as usual to obtain a generalization error estimate for the final model.
The disadvantage with this, however, is that splitting more often than necessary means that the data partitions become rather small and thus the whole procedure may become more unstable (small optimization/validation/test set mean uncertain performance estimates).

Update:
Nesting vs. cross validation or hold-out
Nesting is independent of the question what splitting scheme you employ at each level of the nested set-up. You can do cross validation at each level, single split at each level or any mixture you deem suitable for your task.
2 nested levels and both CV is what is often referred to as nested cross validation, 2 nested levels and  both single split is equivalent to the famous train - validation [optimization] - test [verification] setup. Mixes are less common, but are a perfectly valid design choice as well.
If you have sufficient data so that single splits are a sensible option, you may also have sufficient data to do three such splits, i.e. work with 4 subsets of your data.
One thing you need to keep in mind, though, is: a single split in the optimization steps* you deprive yourself of a very easy and important means of checking whether your optimization is stable which cross validation (or doing several splits) provides.
* whether combined hyperparameter with model family or model family choice plus "normal" hyperparameter optimization
Triply nested vs. "normal" nested
This would be convenient in that it is easy to implement in a way that guards against accidental data leaks - and which I suspect is what you were originally after with your question:

*

*estimate_generalization_error() which splits the data into test and train and on its train data calls

*choose_model_family() which employs another internal split to guide the choice and calls and on its training split calls the various

*optimize_model_*() which implement another internal split to optimize the usual hyperparameters for each model family (*), and on its training split calls the respective low-level model fitting function.

Here, choose_model_family() and optimize_model_*() are an alternative to a combined tuning function that does the work of both in one split. Since both are training steps, it is allowed to combine them. If you do grid search for hyperparameter tuning, you can think of this as a sparse grid
with model family x all possible hyperparameters where evaluate only combinations that happen to exist (e.g. skip mtry for SVM).
Or you look at the search space as a list of plausible hyperparamter combinations that you check out:
- logistic regression
- SVM with cost = 1, gamma = 10
- SVM with cost = 0.1, gamma = 100
...
- random forest with ...

to find the global optimum across model families and model family specific hyperparameters.
There is nothing special about model_family - it is a hyperparameter for the final model like cost or gamma are for SVMs.
In order to wrap your head around the equivalence, consider optimizing gamma and cost for an SVM.

*

*Method one: set up a grid or a list of all plausible cost; gamma combinations and search that for the optimum. This is the analogue to the "normal" nested approach.


*Method two:

*

*set up a list of all plausible cost values.

*for each cost value, optimize gamma.

*select the cost with best optimized gamma

This is the analogue to the triply nested approach.
In both cases, we can "flatten" the nested structure into a single loop iterating over a list or grid (I'm sorry, I lack the proper English terms - maybe someone can help?).
This is also vaguely similar to "flattening" a recursive structure into an iterative one [though the triply nested is not recursive, since we have different functions f(g(h()))].
This flattening approach potentially has the further advantage that it may be better suited to advanced optimization heuristics. As an example, consider moving from "select the observed optimum" to the one-standard-deviation rule. With the flattened approach, you can now look across model families which model is least complex not more than 1 sd worse than the observed optimum.
A: Just to add to @cbeleites answer (which I tend to agree with), there is nothing inherently different about nested cross validation that it will stop the issue in the OP. Nested cross validation is simply the cross validated analog to a train/test split with cross validation performed on the training set. All this serves to do is reduce variance in your estimate of the generalization error by averaging splits. That said, obviously reducing variance in your estimate is a good thing, and nested CV should be done over a single train/test split if time allows.
For the OP as I see it there are two solutions (I will describe it under a single train/test split instead of nested CV but it could obviously be applied to nested CV as well).
The first solution would be to perform a train/test split and then split the training set into train/test again. You now have a training set and two sets. For each model family perform cross validation on the training set to determine hyper-parameters. For each model-family select the best performing hyper-parameters and obtain an estimate of generalization error from test set 1. Then compare the error rates of each model family to select the best and obtain its generalization error on test set 2. This would eliminate your issue of optimistic bias due to selecting the model using data that was used for training however would add more pessimistic bias as you have to remove data from training for test set 2.
The other solution as cbeleites described, is to simply treat model selection as hyper-paramters. When you are determining the best hyper-parameters, include model-family in this selection. That is, you aren't just comparing a random forest with mtry = 1 to a random forest with mtry = 2... you are comparing random forest with mtry = 1 to mtry = 2 and to SVM with cost = 1 etc.
Finally I suppose the other option is to live with the optimistic bias of the method in the OP. From what I understand one of the main reasons leading to the requirement of a test set is that as the hyper-parameter search space grows so to does the likelihood of selecting an over-fit model. If model selection is done using the test set but only between 3 or 4 model families I wonder how much optimistic bias this actually causes. In fact, I would not be surprised if this was the largely predominate method used in practice, particularly for those who use pre-built functionality a la sci-kit learn or caret. After all these packages allow a grid search of a single model-family, not multiple at the same time.
