How bad is hyperparameter tuning outside cross-validation? I know that performing hyperparameter tuning outside of cross-validation can lead to biased-high estimates of external validity, because the dataset that you use to measure performance is the same one you used to tune the features.
What I'm wondering is how bad of a problem this is. I can understand how it would be really bad for feature selection, since this gives you a huge number of parameters to tune. But what if you're using something like LASSO (which has only one parameter, the regularization strength), or a random forest without feature selection (which can have a few parameters but nothing as dramatic as adding/dropping noise features)?
In these scenarios, how badly optimistic could you expect your estimate of training error to be?
I'd appreciate any info on this--case studies, papers, anecdata, etc. Thanks!
EDIT: To clarify, I'm not talking about estimating model performance on training data (i.e., not using cross validation at all). By "hyperparameter tuning outside of cross-validation" I mean using cross-validation only to estimate the performance of each individual model, but not including an outer, second cross-validation loop to correct for overfitting within the hyperparameter tuning procedure (as distinct from overfitting during the training procedure). See e.g. the answer here.
 A: *

*The bias you are talking about is still mainly connected to overfitting. 

*You can keep the risk low by evaluating only very few models for fixing the regularization hyperparameter plus going for a low complexity within the plausible choice. 

*As @MarcClaesen points out, you have the learning curve working for you, which will somewhat mitigate the bias. But the learning curve is typically steep only for very few cases, and then also overfitting is much more of a problem. 
In the end, I'd expect the bias to depend much on 


*

*the data (it's hard to overfit a univariate problem...) and 

*your experience and modeling behaviour: I think it is possible that you'd decide on a roughly appropriate complexity for your model if you have enough experience with both the type of model and the application and if you are extremely well behaved and do not yield to the temptation for more complex models. But of course, we don't know you and therefore cannot judge how conservative your modeling is.
Also, admitting that your fancy statistical model is highly subjective and you don't have cases left to do a validation is typically not what you want. (Not even in situations where the overall outcome is expected to be better.)


I don't use LASSO (as variable selection does not make much sense for my data for physical reasons), but PCA or PLS usually work well. A ridge would be an alternative that is close to LASSO and more appropriate for the kind of data. 
With these data I have seen an order of magnitude more misclassifications on the "shortcut-validation" vs. proper independent (outer) cross validation. In these extreme situations, however, my experience says that the shortcut-validation looked suspiciously good, e.g. 2 % misclassifications => 20 % with proper cross validation. 
I cannot give you real numbers that directly apply to your question, though: 


*

*So far, I did care more about other types of "shortcuts" that happen in my field and lead to data leaks, e.g. cross validating spectra instead of patients (huge bias! I can show you 10% misclassification -> 70% = guessing among 3 classes), or not including the PCA in the cross validation (2 - 5% -> 20 - 30%). 

*In situations where I have to decide whether the one cross validation I can afford should be spent on model optimization or on validation, I always decide for validation and fix the complexity parameter by experience. PCA and PLS work well as regularization techniques is that respect because the complexity parameter (# components) is directly related to physical/chemical properties of the problem (e.g. I may have a good guess how many chemically different substance groups I expect to matter). Also, for physico-chemical reasons I know that the components should look somewhat like spectra and if they are noisy, I'm overfitting. But experience may also be optimizing model complexity on an old data set from a previous experiment that is similar enough in general to justify transferring hyperparameters and then just use the regularization parameter for the new data.
That way, I cannot claim to have the optimal model, but I can claim to have reasonable estimate of the performance I can get.
And with the patient number I have, it is anyways impossible to do statistically meaningful model comparisons (remember, my total patient number is below the recommended sample size for estimating a single proportion [according to the rule of thumb @FrankHarrell gives here]).


Why don't you run some simulations that are as close as possible to your data and let us know what happens?  

About my data: I work with spectroscopic data. Data sets are typically wide: a few tens of independent cases (patients; though typically lots of measurements per case. Ca. 10³ variates in the raw data, which I may be able to reduce to say 250 by applying domain knowledge to cut uninformative areas out of my spectra and to reduce spectral resolution. 
A: If you are only selecting the hyperparameter for the LASSO, there is no need for a nested CV. Hyper-parameter selection is done in a single/flat CV interaction. 
Given that you have already decided to use LASSO and given that you have already decided which features to keep and give to the algorithm (the LASSO will likely remove some of the features but that is the LASSO optimization not your decision) the only thing left is to choose the $\lambda$ hyperparameter, and that you will do with a flat/single CV:
1) divide the data into training\learning sets $L_i$ and test sets $T_i$ and chose the $\lambda^*$ that minimizes the mean error for all $T_i$ when trained with the corresponding $L_i$. 
2)  $\lambda^*$ is your choice of hyperparameter. DONE.
(This is not the only method to select hyperparameters but it is the most common one - there is also the "median" procedure discussed and criticized  by G. C. Cawley and N. L. C. Talbot (2010), "Over-fitting in model selection and subsequent selection bias in performance evaluation", Journal of Machine Learning Research, 11, p.2079, section 5.2.)
What I understand you are asking is: how bad is to use the error I computed in step 1 above (the minimal error that allow me to select $\lambda^*$) as an estimate of the generalization error of the classified with that $\lambda^*$ for future data? Here you are talking about estimation not hyper-parameter selection!!
I know of two experimental results in measuring the bias of this estimate (in comparison to a true generalization error for synthetic datasets)


*

*the Cawley and Talbot paper above

*Varna and Simon (2006), "Bias in error estimation when using cross-validation for model selection", BMC Bioinformatics, 7, 91.
both open access.
You need a nested CV if:
a) you want to choose between a LASSO and some other algorithms, specially if they also have hyperparameters
b) if you want to report a unbiased estimate of the expected generalization error/accuracy of your final classifier (LASSO with $\lambda^*$).
In fact nested CV is used to compute an unbiased estimate of the generalization error of a classifier (with the best choice of hyperparameters - but you dont get to know which are the values of the hyperparameters). This is what allows you to decide between the LASSO and say an SVM-RBF - the one with the best generalization error should be chosen. And this generalization error  is the one you use to report b) (which is surprising, in b) you already know the value of the best hyperparameter - $\lambda ^*$ - but the nested CV procedure does not make use of that information).
Finally, nested CV is not the only way to calculate a reasonable unbiased estimate of the expected generalizationn error. There has been at least three other proposals 


*

*Ding et al. Bias correction for selecting the minimal-error classifier from many machine learning models BioInformatics 30(22) has their one proposal and compare it with two others the weighted mean correction and Tibshirani-Tibshirani procedure.(see references in the paper)

A: The effects of this bias can be very great.  A good demonstration of this is given by the open machine learning competitions that feature in some machine learning conferences.  These generally have a training set, a validation set and a test set.  The competitors don't get to see the labels for either the validation set or the test set (obviously).  The validation set is used to determine the ranking of competitors on a leaderboard that everyone can see while the competition is in progress.  It is very common for those at the head of the leaderboard at the end of the competition to be very low in the final ranking based on the test data.  This is because they have tuned the hyper-parameters for their learning systems to maximise their performance on the leaderboard and in doing so have over-fitted the validation data by tuning their model.  More experienced users pay little or no attention to the leaderboard and adopt more rigorous unbiased performance estimates to guide their methodology.
The example in my paper (mentioned by Jacques) shows that the effects of this kind of bias can be of the same sort of size as the difference between learning algorithms, so the short answer is don't used biased performance evaluation protocols if you are genuinely interested in finding out what works and what doesn't.  The basic rule is "treat model selection (e.g. hyper-parameter tuning) as an integral part of the model fitting procedure, and include that in each fold of the cross-validation used for performance evaluation).
The fact that regularisation is less prone to over-fitting than feature selection is precisely the reason that LASSO etc. are good ways of performing feature selection.  However, the size of the bias depends on the number of features, size of dataset and the nature of the learning task (i.e. there is an element that depends on the a particular dataset and will vary from application to application).  The data-dependent nature of this means that you are better off estimating the size of the bias by using an unbiased protocol and comparing the difference (reporting that the method is robust to over-fitting in model selection in this particular case may be of interest in itself).
G. C. Cawley and N. L. C. Talbot (2010), "Over-fitting in model selection and subsequent selection bias in performance evaluation", Journal of Machine Learning Research, 11, p.2079, section 5.2.)
A: Any complex learning algorithm, like SVM, neural networks, random forest, ... can attain 100% training accuracy if you let them (for instance through weak/no regularization), with absolutely horrible generalization performance as a result. 
For instance, lets use an SVM with RBF kernel $\kappa(\mathbf{x}_i,\mathbf{x}_j) = \exp(-\gamma\|\mathbf{x}_i-\mathbf{x}_j\|^2)$. For $\gamma=\infty$ (or some ridiculously high number), the kernel matrix becomes the unit matrix. This results into a model with $100\%$ training set accuracy and constant test set predictions (e.g. all positive or all negative, depending on the bias term).
In short, you can easily end up with a perfect classifier on your training set that learned absolutely nothing useful on an independent test set. That is how bad it is.
