Overfitting: No silver bullet?

Question

My understanding is that even when following proper cross validation and model selection procedures, overfitting will happen if one searches for a model hard enough, unless one imposes restrictions on model complexity, period. Moreover, often times people try to learn penalties on model complexity from the data which undermines the protection they can provide.

My question is: How much truth is there to the statement above?

I often hear ML practicioners say: "At my company/lab, we always try every model available (e.g. from libraries like caret or scikit-learn) to see which one works best". I often argue that this approach can easily overfit even if they are serious about cross-validation and keep hold-out sets in any way they want. Moreover the harder they search, the more likely they may overfit. In other words, over-optimization is a real problem and there are no heuristics that can help you systematically fight against it. Am I wrong to think this way?

Answer 1

Not a whole answer, but one thing that people overlook in this discussion is what does Cross-Validation (for example) mean, why do you use it, and what does it cover?

The problem I see with searching too hard is that the CV that people are doing is often within a single model. Easy to do by setting a folds= argument of the model fitting procedure. But when you go to multiple models, and even multiple procedures for creating multiple models, you add another layer or two which you haven't wrapped in CV.

So they should be using nested CV. And they should also be using "Target Shuffling" (resampling/permutation testing) wrapped around their whole process to see how well their procedure would do if you break the relationship between dependent and independent variables -- i.e. how much better are you doing than random considering your entire process?

Answer 2

In my 4 or so years of experience, I've found that trying out every model available in caret (or scikit-learn) doesn't necessarily lead to overfitting. I've found that if you have a sufficiently large dataset (10,000+ rows) and a more or less even balance of classes (i.e., no class imbalance like in credit risk or marketing problems), then overfitting tends to be minimal. It's worth noting that my grid search on tuning parameters tends to be no more than 30 permutations per model. At the extreme end, if you used 100 or 1,000 permutations per model, you would probably overfit.

The way you've worded your question makes the answer pretty easy: at the extreme, yes, overfitting is likely if not certain. There is no silver bullet, and I doubt anyone would suggest otherwise. However, there is still a reasonably wide spectrum where the degree of overfitting is minimal enough to be acceptable. Having a healthy amount of unseen data in your validation holdout set definitely helps. Having multiple unseen validation holdout sets is even better. I'm fortunate enough to work in a field where I have large amounts of new data coming on a daily basis.

If I'm in a position where I'm stuck with a static dataset of fewer than 2,000-3,000 observations (ex: medical data that's hard to come by), I generally only use linear models because I've frequently seen overfitting with gradient boosting and support vector machines on sufficiently small datasets. On the other hand, I've talked to a top Kaggler (top 5%) that said he builds tens of thousands of models for each competition and then ensembles them, using several thousand models in his final ensemble. He said this was the main reason for his success on the final leaderboards.

Answer 3

So much depends on scale. I wish I could count on having more than 2,000-3,000 cases like @RyanZotti typically has; I seldom have 1/10th that many. That's a big difference in perspective between "big data" machine learning folk and those working in fields like biomedicine, which might account for some of the different perspectives you will find on this site.

I'll present a heuristic explanation of my take on this problem. The basic issue in overfitting, as described on the Wikipedia page, is the relation between the number of cases and the number of parameters you are evaluating. So start with the rough idea that if you have M models you are choosing among and p parameters per model then you are evaluating something on the order of Mp parameters in total.

If there is danger of overfitting there are two general ways to pull back to a more generalizable model: reduce the number of parameters or penalize them in some way.

With adequately large data sets you might never come close to overfitting. If you have 20,000 cases and 20 different models with 100 parameters per model, then you might not be in trouble even without penalization as you still have 10 cases per effective parameter. Don't try that modeling strategy with only 200 cases.

Model averaging might be thought of as a form of penalization. In the example of the Kaggler cited by @RyanZotti, the number of cases is presumably enormous and each of the "several thousand" models in the final ensemble individually contributes only a small fraction of the final model. Any overfitting specific to a particular contributing model will not have a great influence on the final result, and the extremely large numbers of cases in a Kaggler competition further reduces the danger of overfitting.

So, as with so many issues here, the only reasonable answer is: "It depends." In this case, it depends on the relation between the number of cases and the effective number of parameters examined, together with how much penalization is being applied.

Answer 4

I agree with @ryan-zotti that searching hard enough does not necessarily lead to overfitting - or at least not to an amount so that we would call it overfitting. Let me try to state my point of view on this:

Box once said:

Remember that all models are wrong; the practical question is how wrong do they have to be to not be useful.

(Being perfect would require all the data, which in turn would eliminate the need for a model in the first place).

Models being wrong also comprises over- and underfitting$^1$. But we won't necessarily care about or even notice it. The question is which amount of the model deviating from reality can we a) measure at all and b) find acceptable to not call it over- or underfitting - because both will always apply a little to all model we will ever build. If our models in the end satisfy our requirements but e.g. over-/underfit just minimal, or over-/underfit on parts of (possible) data that is not considered in our application case we would accept it - it's not necessarily about preventing all over-/underfitting.

This boils down to a proper setup to measure/detect model error to decide if this is what we would want to have. So what we can do is make the process as robust as possible by trying to get data with minimal noise and representative+sufficient samples, to model, evaluate and select as best as possible, and to do all this in a reasonable way (e.g. few samples, many features $\rightarrow$ less complex model; select the least complex model with yet acceptable performance, etc.).

Because: in the end we will always have model error/over-/underfitting - it's the capability of detecting/measuring this error within our focus of interest to make reasonable choices that matters.

---

$^1$ a) each model has a bias and variance problem at the same time (we usually try to find the right trade-off to satisfy our needs). Models satisfying our requirements will necessarily still have bias and variance. b) Consider noisy data and non representative samples as reasons for overfitting. Each model will necessarily model noise as well as model a relation for which parts of the information is missing, so about which wrong assumptions will necessarily be made.

Answer 5

I think this is a very good question. I always want to observe the "U" shape curve in cross validation experiments with real data. However, my experience with real world data (~ 5 years in credit card transactions and education data) does not tell me over fitting can easily happen in huge amount (billion rows) real world data.

I often observe that you can try you best over fit the training set, but you cannot do too much (e.g., reduce the loss to 0), because the training set is really large and contains a lot of information and noise.

At the same time, you can try the most complicated model (without any regularization) on testing data, and it seems fine and even better than some with regularization.

Finally, I think my statements might be true only under the condition of you have billions data points in training. Intuitively, the data is much complex than you model so you will not over fit. For billion rows of data, even you are using a model with thousands of parameters, it is fine. At the same time you cannot afford the computation for building a model with million free parameters.

In my opinion this is also why neural network and deep learning got popular these days. Comparing to billions of images in Internet, any model you can afford training is not enough to over fit.

Answer 6

overfitting will happen if one searches for a model hard enough, unless one imposes restrictions on model complexity, period

I guess the simple answer is yes, if the search space (complexity of considered model class(es)) is large enough).

If data is the new oil, then note that oil is usually burnt during use. Consider training a gazillion of random forests by tuning the random seed. One of them will by chance be optimal on the test set. Cross validation won't change this result in the end.

More recently, the "double decent" was discovered, see for example [1] and the review [2]. There is a whole new regime for overparametrized models that interpolate the training data. In this regime, the notion of overfitting is not adequate anymore. If a model is very much overparametrized, it may (or may not) have a better statistical risk (generalization error) than the optimal point in the classical bias-variance-trade-off regime.

[1] Belkin, Hsu, Xu "Two Models of Double Descent for Weak Features" 2020, https://epubs.siam.org/doi/10.1137/20M1336072

[2] Dar, Muthukumar, Baraniuk "A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learning" 2021, https://arxiv.org/abs/2109.02355

Answer 7

Already existing answers are mostly fine, but I add one small aspect that I haven't seen mentioned.

Let's assume you compare lots of models by cross-validation in a correct manner (avoiding information leakage, if necessary using nested CV, see answer by Wayne), and ultimately you choose the one that gives you the best result.

As you're optimising the CV-loss, the then achieved CV-loss will be optimistic for the true loss to be achieved by that model (optimism is worse the fewer observations you have). This is usually called "overfitting". This will automatically happen, unless you do a final CV evaluating only the winning model (which may require double nesting of the CV and is rarely done).

However, the chosen model is still the model estimated to be best by the CV, and therefore your best bet of being the best model. Granted, it may in fact not be the best, but it should still be seen as a good choice (and it normally will be, unless a too small data set causes a too large variance in CV-estimated loss).

We need to distinguish between overfitting as a problem for estimating the true prediction loss, and choosing a good model. With a reasonably large data set and CV run correctly (i.e., avoiding information leakage), it may be a problem for the former (which can be amended by adding another nesting level) but not the latter.