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?

  • 4
    $\begingroup$ Generating random models and choosing the one with least error is asymptotically (if you do this long enough) equivalent to OLS regression because OLS solution minimizes squared error. $\endgroup$
    – amoeba
    Commented May 17, 2018 at 13:59
  • $\begingroup$ @CagdasOzgenc: this is like the monkeys typing Shakespeare/the Bible/whatever text you choose: if you produce many random model, eventually the least squares solution will be among them. Eventualy even a sequence of $k$ times the least squares solution of the CV test cases. And that will then be selected [if you use squared error as performance criterion]. $\endgroup$
    – cbeleites
    Commented May 17, 2018 at 18:39
  • $\begingroup$ Random feature learning is also a thing (see the Random Vector Functional-Link network, which the controversial Extreme Learning Machine is derived from). $\endgroup$
    – Firebug
    Commented May 17, 2018 at 18:48
  • 1
    $\begingroup$ The premise of this question is very confusing. CV can sometimes be ineffective, but I don't see (1) how its failure modes have anything to do with nested vs. non-nested hypotheses or Rademacher complexity, or (2) how comparing non-nested models has anything to do with comparing randomly generated models. $\endgroup$
    – Paul
    Commented Jun 19, 2018 at 12:36
  • $\begingroup$ @Paul The implicit assumption behind CV is that the number of hypotheses compared is low. If we have a lot of models to compare it will overfit. Usually in a Ridge setting we have plenty of lambda settings, hence quite many hypotheses. However the reason it works in this scenario is because the hypotheses are nested. $\endgroup$ Commented Jun 19, 2018 at 12:46

2 Answers 2


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?


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.

  • $\begingroup$ When not much training data is available fitting a model through cross-validation alone is reasonable. I think the tradeoff between using all the data for fitting or saving a portion just for validation is not that clear cut in many circumstances $\endgroup$
    – Nat
    Commented May 17, 2018 at 19:07
  • $\begingroup$ @Nat: when not much training data is available, I'd recommend to use as much expert domain knowledge as possible and try to avoid any data-driven tuning by cross validation (or an internal single split): few cases mean the CV estimates are uncertain, which will hamper the optimization anyways. CV is better than a single split, but it cannot work miracles. $\endgroup$
    – cbeleites
    Commented May 18, 2018 at 6:09
  • $\begingroup$ What would non-data driven model selection look like? Is that like non-data-driven decision making? If I minimize MSE is that data-driven? What if I minimize MSPE? $\endgroup$
    – Nat
    Commented May 18, 2018 at 14:10
  • 1
    $\begingroup$ @Nat: Example for not data-driven model selection: Deciding pre-processing and possibly also model complexity by knowledge about the application at hand, such as: the processes that generate the data and the information to be retrieved, other information or confounding factors involved. Minimizing errors is data-driven: you minimize some error you observe within your available data. This is necessary for fitting model parameters, but it is in my experience often possible to limit the the number of so-called hyperparameters/restrict the hyperparameter search space. (I typically <100 cases) $\endgroup$
    – cbeleites
    Commented May 20, 2018 at 10:28

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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