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.

enter image description here

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 :

But I have not found anything that answers my question.

Can someone please help me with this?



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")

enter image description here


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:

enter image description here

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.

  • 1
    $\begingroup$ In your 5 steps of cross validation you speak about training a model and recording how well it performs but nowhere do you speak about parameter/model selection which is the point of cross validation. $\endgroup$ Commented Nov 8, 2021 at 7:45
  • $\begingroup$ Your note 1 is about the limits of CV. Because CV only sees the data the model was built on it cannot predict what happens if you change any underlying properties of the data (population distributions, measurement errors, time evolution, data formats). This is not unique to CV nor multivariate analysis but the fundamental conundrum at the heart of statistics. This is my understanding of @SextusEmpiricus remark 'That's why statistics is not simply mathematics' - statistical prediction (future or generalisation) is about new variables, thus breaking the assumption implicit in the = sign $\endgroup$
    – ReneBt
    Commented Nov 8, 2021 at 9:43
  • 1
    $\begingroup$ @ReneBt what I meant by 'statistics is not mathematics' is that it is more than applying formulas to data (which might give a false impression of a very exact result). It is also about 'soft' skills like issues around generating the data, and all the stuff like 'selection bias', 'outliers', 'mixing up correlation and causation', 'getting clean data', etc. It is related to the 'all models are wrong' phrase. The mechanistic mathematics behind the models is one thing but 'making the models work' or interpreting 'how well they work' is another. $\endgroup$ Commented Nov 8, 2021 at 11:19
  • $\begingroup$ But if the question reads "Are there any mathematical proofs that..." then we place those 'other' aspects in the background and deal only with the models as if they are applied in an ideal world. Given that the question is (I thought) about mathematical prove, notes 1 and 2 might be a bit too long and distracting. $\endgroup$ Commented Nov 8, 2021 at 11:22

1 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.

  • 2
    $\begingroup$ +1 I think a lot of the justification for cross-validation has more to do with reducing variance in a small sample setting (although ironically I gather the paper used to justify leave-one-out cross-validation in ML is establishing its unbiasedness). A test-training split would also be unbiased, but higher variance. I always insist on good asymptotic properties whenever I fit a model to an infinitely large dataset! ;o) $\endgroup$ Commented Nov 8, 2021 at 8:49
  • 1
    $\begingroup$ @DikranMarsupial that's true, it is not so much purely about consistency, but more generally about reducing variance (and consistency means that we can reduce the variance to zero). The main point is that 'with increasing sample size the estimates improve', but there are many different ways to look at it (rate of improvement, asymptotic value, etc.). In my post I actually do not argue that the models are consistent (they might be biased even for larger sample sizes), but I argue that estimates about the models' properties (the distribution of the errors made by the models) are consistent. $\endgroup$ Commented Nov 8, 2021 at 9:06
  • $\begingroup$ @ Sextus Empiricus : Thank you so much for your answer! Just to clarify : The Glivenko–Cantelli theorem states that the empirical probability distribution function will converge to the true cumulative probability distribution function as the number of samples (used to create the empirical probability distribution function) goes to infinity? $\endgroup$
    – stats_noob
    Commented Nov 8, 2021 at 17:36
  • $\begingroup$ @stats555 yes, that is right, and the convergence is uniform. But, related to the other issues, like how practical this convergence is, you might want to look further and argue about the rate of convergence. The Wikipedia article linked in my post deals with several related items like 'the rate of convergence' which might be related to the central limit theorem or the functional equivalent Donsker’s theorem.... $\endgroup$ Commented Nov 8, 2021 at 17:44
  • $\begingroup$ ... I am actually not sure what your question is about, and what the big issue/problem is. Maybe I am considering it as a trivial question while it is not, but in that case, where is the problem? In most cases of statistics the situation is that more data leads to better estimates... $\endgroup$ Commented Nov 8, 2021 at 17:50

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.