Is Cross Validation useless unless the Hypotheses are nested?

Question

If I generate many random models (without considering the data at all) in a regression setting simply by randomly assigning coefficient values and then evaluating these models over the dataset with an error metric and choosing the best model based on this error metric would I still run into overfitting?

Eventually we will end up with the OLS solution (see comments). If this is the case how is Cross Validation different than this procedure? For example in a Ridge or Lasso regression setting I am still generating a bunch of models (indexed by $\lambda$) and evaluating them on unseen data segment and choosing the best one.

It seems to me that CV works well with standard regularization methods like Ridge and Lasso is because the tried models are somewhat nested (i.e. Ridge is ordered by Rademacher complexity). Hence the Structural Risk Minimization principle kicks in. Otherwise CV looks like a dead end effort. If we use cross validation to compare bunch of unrelated models we will end up with the random model generation scenario that I described above.

Under the Structural Risk Minimization framework, for example in SVM, one bounds the error and reduces the model complexity. So how does CV actually achieve the same effect when applied in conjunction with regularization methods? What to do when compared models are not nested?

Answer 1

My logic tells me the answer is yes.

And, as @amoeba pointed out: your logic is right.

how is Cross Validation different than this procedure? CV in itself has nothing to do with your overfitting. CV is just a scheme how to retain independent cases to test some model.

Note that if you select a model based on the CV results, this model selection procedure (including the CV) is actually part of your training.

You need to do an independent validation (rather, verification) of that final model (for which you can again use another CV as a strategy to retain cases independent of the training - see nested cross validation) in order to obtain a reliable estimate of its generalization performance.

To reiterate: the problem is not the CV, the problem is the data-driven model optimization (selection).

From this perspective random model generation should in theory overfit less than a penalized regression as my evaluation is on a bigger unseen data segment.

This I don't understand: why would the unseen data size differ?

Is there something in CV procedure that somehow mitigates the multiple testing problem?

No.

The only property of CV that slightly helps with multiple testing compared to a single split is that CV eventually tests all available cases, and is thus subject to somewhat smaller variance uncertainty due to the limited number of tested cases. This won't help much compared to limiting the search space (i.e. restricting the number of comparisons), though.

Answer 2

EDIT: Tuning or selecting a model based on cross-validation is essentially trying to minimize the prediction error (e.g., mean-squared prediction error). You select a model conditional on some subset of input data and predict the output at the left out locations. Intuitively, it is a prediction because you are evaluating the model at out of sample locations. Your question is what happens if your set of candidate models are independent of the input data (i.e., you don't use any data when randomly generating models).

This assumption is not that different than any other model fitting procedure. For example, if I start with a parameterized model, and the parameters could be any real number, then I also have an infinite set of candidate models. We both still need to select the best model from the set of possible models by minimizing some error metric. Therefore, both of our model choices are conditional on some training data (perhaps a subset of all the training data if using cross-validation). You don't specify an error metric so lets assume it is mean-squared error (MSE). I pick model parameters and thereby my model using some black box procedure assuming MSE metric conditional on training data. You pick your model from your set of random models assuming MSE metric conditional on training data.

Do we choose the same model? It depends on if you started with different sets of candidate models.

Do we overfit the data? It depends on the set of candidate models we started with and the training data.

Do we know we overfit the data? If we do cross-validation then we can check the prediction error.

ORIGINAL RESPONSE: In a broad sense, there is some signal in the data and some noise. When we overfit we are essentially fitting the noise.

In cross-validation, we leave out portions of the data when fitting and assess the error when predicting the left out points. It is similar to having training and test data in that we are measuring an out of sample error. The model must generalize well regardless of what points are omitted. If we fit the noise the model will not generalize well. The set of models we are comparing likely does not include those that try to interpolate a data point when it is omitted from the training data. If the model behaves this way (e.g., random behavior to improve fit) then it is likely we do not have a reasonable general model fitting procedure and cross-validation can't help us.

If you have an infinite set of models and an infinite amount of time then I guess in theory you could generate a model that was as good or better than any model that was generate through any other procedure. How will you know which model from your infinite set it is though? If it is the model that interpolates the training data, then yes it will overfit when the training data is noisy.