Can overfit happen in spite of validation and what to do with it?

Question

Let's consider a standard situation where we need to find a predictive model.

1. We train all the available model using a training data set.
2. We validate all the trained model using a validation data set.
3. We take a model that was the best on the validation data set and do its "final check" using a test data set.

Let's now assume that the model did not pass this "final test" (it has bad performance on the test data set). What should we do in this case?

A related question: Let's assume that the did pass the "final test" (it has good performance on the test data set), how do we know that it is not just overfit that has happened on the validation phase? For example, we have considered 10 thousand models on the validation step and one of them turned to be great just by chance.

Answer 1

Without attempting to give a full answer, and in my humble opinion, yes it can.

In practice overfit is in essence bias/variance towards the data you have in your dataset (as opposed to its source).

As an example, suppose I draw 1000 values from a Gaussian variable with mean 0. The mean of my dataset will almost never be 0, lets say it is e. I can use cross validation to reduce this error e by introducing bias.

If I make some assumption about the source of my data, (in this case if i constrain it to be a Gaussian) I impose restrictions to the model that will move the average of my estimation from its unbiased value. So (Cross Validation) I create an estimator using part of my data, and use them to predict the rest of them.

This will greatly reduce my error, but not eliminate it. Note that it might indroduce another error: I made the assumption my data was gaussian. In general, we might know the distribution or make the assumption of Ocam's Razor and try to make the weights of our estimator as small as possible. Also it is known that the sum of infinite independent variables is a Gaussian, so if you have to estimate a natural process that results from a really large number of independent factors - movement of molecules, uncoordinated decisions of a population,etc. its reasonable to expect a Gaussian. However, Ocam's Razor is a heuristic, and as such itself approximation / can be wrong.

In theory,

• For any dataset, of any size, suppose you estimate a function/estimator F/PDF after any process you want, including Cross Validation.
• Then I can increase the dataset by data that are inconsistent to F/PDF and find a function/estimator for the increased dataset (In extreme case, my estimator will be the augmented dataset itsef)
• Now I can claim this was the model from which the initial data was derived, and therefore you failed to create a perfect estimator.
• You can complain that I am not allowed to augment the dataset in this way because then getting the first data first and the augmentation set afterwards would be extremely unlikely, but to that I would answer: 'Tough Luck'...