Formal treatment of overfitting on the test set

Question

Assume that I split randomly the data into training and test sets. Suppose that I build a machine learning model using the training set. And suppose that I evaluate the accuracy of the model on the test set and it turned out to be 0.8. I think we can say that the expected accuracy of the model on future (unseen) data is 0.8. But if I try many different algorithms I will begin to overfit on the test set (which is typically the case in many Kaggle competitions). Note that this overfitting will happen even if I use a separate validation set for hyperparameter tuning.

Rather somewhat informally, we can say that for finding the accuracy if one uses the test only once then there is no problem. But if one uses it many times then there will be overfitting on the test set and the accuracy result will not be a good estimate of the true error of the model.

My question is: is there some formal treatment of this rather informal statement above. For example which says that if you try $n$ different models on the test then the estimated accuracy's confidence will decrease as a function of $n$. I'm asking this because I cannot see any way to prevent overfitting on the test set in an offline experimental setup where one tries many different algorithms to find the best model. Thanks.

Answer 1

The way to test a machine learning model, to determine the expected accuracy on different data, is to use a third set of data that has not been used for training and validating.

What is the difference between test set and validation set?

If you use the test set as some sort of second layer of cross validation, to filter different algorithms according to their performance, then it is not a valid test but acts effectively as a validation set.

• This happens indeed with Kaggle competitions or p-values in research, they are susceptible to publication bias.

  There is no real formal way to deal with this.

  The rigorous way to solve it is re-test it with a fourth test.

  A simple way is to set stricter standards (it is one of the reasons for the $5\sigma$ standard: Origin of "5$\sigma$" threshold for accepting evidence in particle physics?).

• If this happens in your own research. For selecting algorithms you could save data by selecting the algorithms along with the hyper-parameter tuning. The choice between algorithms could be seen as some sort of hyper-parameter tuning (the choice of model being the parameter).