How did Cross Validation become the "Golden Standard" of Measuring the Performance of Statistical Models?

Question

I have the following question: How did Cross Validation become the "Golden Standard" of Measuring the Performance of Statistical Models?

I understand the "logical appeal" of Cross Validation (e.g. K-Fold Cross Validation, Leave One Out Cross Validation):

• Logically speaking, at some point - statistical models (e.g. linear regression models, random forest) will be required to make predictions on new data.

• Logically speaking, we will not have a lot of information about this new data - we (naturally) assume that this new data can take any value between the ranges of the data that we have already observed.

• Logically speaking, we would like to have some idea as to how our statistical model will perform on this new data, prior to this new data becoming available to us.

Thus, Cross Validation becomes the natural choice. By randomly sampling small subsets of the observed data, we can create "a series of parallel universes" (i.e. the "folds" in K-Fold Cross Validation) to see how flexible and well the statistical model performs in each one of these "parallel universes". We hope that some of these "universes" might contain "adverse and unfavorable test cases" for the statistical model, and give us an idea of how well the statistical model will perform on average when faced with new data - taking into account these "worst case scenarios".

The Cross Validation (e.g. K Fold) procedure loosely goes as follows:

• Step 1 : Randomly select 70% (I have heard that "70%" is debatable - can be made higher or lower) of your data and train the model on this 70%.

• Step 2: See how "well" (e.g. MSE, Accuracy, F-Score, etc.) the model from Step 1 performs on the remaining 30% of the data. Record this measurement.

• Step 3: Repeat Step 1 and Step 2 "many times". Each time you repeat this, keep track of the measurement.

• Step 4: Average all measurements : this average is said to represent how well your statistical model will perform on new data.

• Step 5: In the end, you re-build your statistical model using the full dataset and use this model to predict new data in the real world. This is because the Cross Validation procedure (apparently) gives you an idea if your model was overfitting the data.

My Question: Are there any mathematical proofs that highlight any theoretical "guarantees" made by the Cross Validation procedure? Just like the Central Limit Theorem "guarantees" that the mean of "n random samples" from a population will follow a Normal Distribution (as the number of random samples goes to infinity); or the Bootstrap Method "guarantees" that the confidence interval for the mean of an infinite number of random samples (with replacement) from a sufficiently large sample will "contain" the population mean - are there any theoretical guarantees that are made regarding the Error of the Cross Validation Estimator (In the above picture : E)?

Or is the popularity of the Cross Validation Procedure rooted more in its pragmatic and logical appeal (instead of theoretical results promised by the Cross Validation Estimator)?

I tried to read more about the origins, the theoretical guarantees and theoretical results of the Cross Validation Estimator :

• Who invented k-fold cross-validation?

• Proof of LOOCV formula (apparently this contains a proof that demonstrates that the Cross Validation Estimator is an unbiased estimator for the "true" MSE of polynomial regression - but I am not sure if this results extends to other statistical models such as decision trees and random forest)

• https://www.jstor.org/stable/2984809

But I have not found anything that answers my question.

Can someone please help me with this?

Thanks!

References:

• http://www.stat.cmu.edu/~larry/=sml/Boot.pdf

• https://en.wikipedia.org/wiki/Central_limit_theorem

• https://en.wikipedia.org/wiki/Cross-validation_(statistics) -https://www.researchgate.net/publication/326465007/figure/fig1/AS:649909518757888@1531961912055/Ten-fold-cross-validation-diagram-The-dataset-was-divided-into-ten-parts-and-nine-of.png

• https://www.cs.ox.ac.uk/files/11641/lecture_5.pdf

Note 1: On a side note, I have heard that the "attractive theoretical promises" made by the Central Limit Theorem and the Bootstrap Method don't tend to be as "attractive" in reality due to the following reasons:

• The sample available in the real world does always tend to be a "random" sample (i.e. not representative of the population, e.g. it might be easier to take size measurements on elephants in the zoo vs elephants in the wild - your data might contain more measurements from elephants in zoos... therefore, the average size of an elephant you calculate might contain statistical biases that might not reflect the size of all elephants in the world, thus reducing the theoretical promises made by CLT/Bootstrap).

• The sample available might not be "large enough" for the theoretical guarantees of CLT/Bootstrap to apply.

• Real world data is often "dynamic" and unobservable factors can cause the data to fundamentally change since you collected the data (e.g. if you are interested in measuring salaries, events in the economy might occur which reduce the average salary from the time that you initially collected the data.)

• Structural errors, experimental errors and measurement errors can also cause your data to be non-representative of the true population (e.g. faulty scales do not record the true weight of your subjects, medical patients intentionally understate their smoking habits)

• Common problems associated with high dimensional data (i.e. problems in univariate data are often exacerbated in multivariate data, e.g. the "curse of dimensionality" shows us that high dimensional data requires an infinite number of samples as the number of dimensions increase - or the data is probabilistically likely to be sparse and concentrated around the periphery of the "space")

References:

• https://www.inf.fu-berlin.de/inst/ag-ki/rojas_home/documents/tutorials/dimensionality.pdf

• https://www.americanscientist.org/article/an-adventure-in-the-nth-dimension

Note 2: On the Machine Learning side, a similar concept exists called the "Rademacher Complexity" (https://en.wikipedia.org/wiki/Rademacher_complexity) which in theory is able to place bounds on the Generalization Error of a Machine Learning model with respect to the probability distribution from which the training data is said to have come from:

Thus in theory, the Rademacher Complexity would allow us to know the worst possible performance of a machine learning model conditional on observing any future data. However, in practice, the error bounds derived from the Rademacher Complexity are said to be "too wide" for any tangible use.

Answer 1

Consider a population $Y|X$ that follows some distribution according to a true model, and you have a set of trained models $f(X,\theta)$ that make predictions of $Y$ given $X$ and are parameterized by $\theta$.

The goal is to find out what the error of the models is, in making predictions about samples from the population, as function of the parameter $\theta$, and to select the model with the lowest error.

To achieve this goal we can sample the population (the validation data set) and observe the performance/error of the models for the sample as function of $\theta$ and use that to estimate the performance/error for the entire population.

Now, our observations based on a sample will not be perfect, but the found empirical distribution of the performance/error (or derived quantities, e.g the average performance/error) will be close to the real value (provided a sufficiently large sample).

Or at least, according to the Glivenko-Cantelli theorem the empirical distribution can be made as close to the real distribution as we want by increasing the size of the sample size (the validation data set). Since the convergence of the empirical distribution towards the true distribution of the performance/error is uniform, any derived quantity (e.g. the mean performance/error) will also convergence towards the true value (in the case of the mean one could also use the law of large numbers).

So the 'theoretical guarantee' is the law of large numbers, or more general the Glivenko-Cantelli theorem.

---

Note 1: On a side note, I have heard that the "attractive theoretical promises" made by the Central Limit Theorem and the Bootstrap Method don't tend to be as "attractive" in reality...

That's why statistics is not simply mathematics.

Indeed this theoretical guarantee is only a guarantee that the estimates are consistent. It means that the estimates convergence to the true value, but the practical use might be low if the rate of convergence is slow, or if the initial variance is large.