Dependence in Repeated Cross-Validation

Why Repeating Cross-Validation Does Not Create New Data Sets

Repeated $K$-fold cross-validation changes the partition of the observations, but it usually reuses the same observed data each time. That distinction matters when quantifying uncertainty. A collection of scores from different partitions can show how much the result depends on the partition, but it does not behave like the same number of independently sampled data sets.

Let $D=(Z_1,\ldots,Z_n)$ be the observed data, with independent observations from a population. In each repetition $r$, a randomized partition assigns observations to $K$ folds. A learning procedure is trained on the other $K-1$ folds, and losses on the held-out fold are combined to produce a score $S_r$. Thus, each score uses the same $D$, although the training and validation roles may change. For clarity, assume initially that the learning procedure is deterministic given its training data and that each repetition uses an independent random partition.

Definition: The partition-conditional mean and partition-conditional variance of a repeated cross-validation score are $m(D)=E[S_r\mid D]$ and $v(D)=\operatorname{Var}(S_r\mid D)$. They describe variation over the random partition while holding the observed data fixed. They are not, by themselves, the sampling variance of an estimator of population risk.

The target might be the expected predictive risk of a procedure trained on $m=n(K-1)/K$ observations, averaged over possible training data sets. A repeated cross-validation score is an estimate aimed at a risk target of this kind; its bias relative to the target is a separate issue. Here the question is what its repeated scores reveal about uncertainty. In particular, variation due to changing partitions is not the same source of variation as variation due to drawing a new data set.

Dependence Between Repetitions

Two repetitions share all the observed outcomes and predictors. Their partitions may differ, but both scores are functions of the same $D$. If the partitions are drawn independently, the scores are independent conditional on $D$, not generally independent without that conditioning.

Theorem: Suppose $S_1$ and $S_2$ are conditionally independent and identically distributed given $D$, and have finite second moments. Then $$ \operatorname{Cov}(S_1,S_2)=\operatorname{Var}\{m(D)\}\geq 0. $$ In particular, unconditional independence requires $\operatorname{Var}\{m(D)\}=0$.

Proof. Apply the law of total covariance: $$ \operatorname{Cov}(S_1,S_2) = E\{\operatorname{Cov}(S_1,S_2\mid D)\} + \operatorname{Cov}\{E[S_1\mid D],E[S_2\mid D]\}. $$ Conditional independence makes the first term zero. The identical conditional distribution gives $E[S_1\mid D]=E[S_2\mid D]=m(D)$, so the second term is $\operatorname{Var}\{m(D)\}$, which is nonnegative. If this variance is positive, the covariance is positive and the scores cannot be independent. $\square$

The theorem isolates a shared-data contribution: data sets on which the conditional average score is high tend to produce high scores across repetitions; data sets on which it is low tend to produce low scores. The result does not say that every pair of scores must be strongly correlated. The covariance can be small if $m(D)$ barely varies across possible data sets. Nor does the theorem apply unchanged if repetitions share additional randomization or the partitions are dependent: then a conditional covariance term may remain.

Worked Example: Shared Data Create Positive Covariance

Consider the simple score model $S_r=A+\varepsilon_r$, where the data-dependent component $A$ takes values $0.2$ and $0.6$ with equal probability, and each partition-specific term $\varepsilon_r$ independently takes values $-0.1$ and $0.1$ with equal probability. All $\varepsilon_r$ are independent of $A$. Scores lie between $0.1$ and $0.7$.

The mean of $A$ is $0.4$, and $$ \operatorname{Var}(A)=\tfrac12(0.2-0.4)^2+\tfrac12(0.6-0.4)^2=0.04. $$ Each $\varepsilon_r$ has mean zero and variance $0.01$. Therefore $E[S_r]=0.4$ and $\operatorname{Var}(S_r)=0.04+0.01=0.05$.

For two repetitions, the shared component is $A$, while the partition-specific terms are independent. Hence $$ \operatorname{Cov}(S_1,S_2)=\operatorname{Var}(A)=0.04, \qquad \operatorname{Corr}(S_1,S_2)=\frac{0.04}{\sqrt{0.05\cdot0.05}}=0.8. $$ The scores are highly correlated even though the partitions are independently randomized. Randomizing the partition again does not remove the common data-dependent component.

What the Spread Across Repetitions Measures

For $R$ repetitions, write $\bar S_R=R^{-1}\sum_{r=1}^R S_r$, and let $s_R$ be the usual sample standard deviation of the $R$ scores, using divisor $R-1$ for the sample variance. Conditional on $D$, independent repetitions provide repeated draws from the partition distribution. Thus $s_R$ describes partition-to-partition spread, and $s_R/\sqrt R$ estimates the conditional Monte Carlo standard error of $\bar S_R$ as an estimate of $m(D)$.

That conditional standard error answers a limited question: how much would the average score change if the partition randomization were repeated on this same data set? It does not answer how much the average would change if a new sample from the population were collected. The distinction is not a technicality; increasing $R$ can reduce the first uncertainty while leaving the second essentially untouched.

Theorem: If the scores are conditionally independent and identically distributed given $D$, and have finite second moments, then $$ \operatorname{Var}(\bar S_R) = \operatorname{Var}\{m(D)\}+\frac{E[v(D)]}{R}. $$

Derivation. Conditional on $D$, the mean of $\bar S_R$ is $m(D)$, and its variance is $v(D)/R$, by conditional independence. Applying the law of total variance gives $$ \operatorname{Var}(\bar S_R) = \operatorname{Var}\{E[\bar S_R\mid D]\} + E\{\operatorname{Var}(\bar S_R\mid D)\} = \operatorname{Var}\{m(D)\}+\frac{E[v(D)]}{R}. $$ The first term is data-sampling variation in the conditional mean score. Only the second term decreases with the number of repetitions. $\square$

This is a variance decomposition for the score, not a claim that its variance equals the mean squared error for a particular population-risk target. If the score is biased for that target, the bias must also be considered. The formula nevertheless shows why treating all $R$ scores as independent observations from the population can understate uncertainty: that calculation effectively ignores the first term.

Worked Example: A Small Partition Standard Error Can Hide Sampling Variation

Suppose repeated scores have the form $S_r=A+\varepsilon_r$. Let $A$ equal $0.3$ or $0.7$, each with probability one half, and let each independent partition term $\varepsilon_r$ equal $-0.05$ or $0.05$, each with probability one half. The score remains between $0.25$ and $0.75$.

Here $E[A]=0.5$, $\operatorname{Var}(A)=0.04$, and $v(D)=\operatorname{Var}(\varepsilon_r)=0.0025$. For $R=25$, the variance of the repeated-score average over both data and partitions is $$ \operatorname{Var}(\bar S_{25})=0.04+\frac{0.0025}{25}=0.0401. $$ Its standard deviation is $\sqrt{0.0401}\approx0.20025$.

Within a fixed data set, however, the partition standard deviation is $0.05$, so the conditional Monte Carlo standard error of the 25-score average is $0.05/\sqrt{25}=0.01$. This is a valid answer to the conditional partition-randomization question. It is not an estimate of the $0.20025$ unconditional standard deviation: most of that variation comes from $A$, which changes across data sets, not across partitions of one data set.

Why Fold-Level Standard Errors Need Caution

A single $K$-fold run produces $K$ fold scores, but these are not generally independent replicates either. The training sets overlap, the validation sets partition the same observations, and all scores arise from one data set. Consequently, the formula “standard deviation of fold scores divided by $\sqrt K$” is not automatically a standard error for population risk. It treats the fold scores as independent observations from a common sampling distribution without establishing that assumption.

Repeated partitions do not fix this issue merely by increasing the number of scores. Fold scores within a run and whole-run scores across repetitions are different collections, but neither collection becomes a set of independent population samples just because it contains many entries. A valid uncertainty calculation needs to match the randomness it claims to quantify and account for the dependence in the design.

Worked Example: The Arithmetic of a Fold Formula Is Not Its Justification

Suppose a five-fold run gives fold losses $0.20, 0.25, 0.30, 0.35, 0.40$. Their mean is $$ \bar L_{\mathrm{fold}}=\frac{0.20+0.25+0.30+0.35+0.40}{5}=0.30. $$ The deviations from the mean are $-0.10,-0.05,0,0.05,0.10$, whose squared sum is $0.025$. The sample standard deviation is therefore $$ s_{\mathrm{fold}}=\sqrt{\frac{0.025}{5-1}}=\sqrt{0.00625}\approx0.0791. $$

Dividing this number by $\sqrt5$ gives approximately $0.0354$. That calculation is arithmetically correct, but the result is not thereby a justified standard error for population risk. Its usual independent-sample interpretation would require an appropriate independence and sampling argument for the five fold scores. Overlapping training sets and the shared data do not supply that argument. Without a dependence-aware justification, report the fold spread as descriptive rather than presenting this quotient as a calibrated population-risk standard error.

Common Mistakes and Practical Interpretation

Mistaking partition spread for population uncertainty. The standard deviation across repeated scores measures sensitivity to randomized partitions on the observed data. It does not measure all the variation that would arise from collecting new data.
Treating repetitions as independent data sets. Independent partition randomization does not make the scores unconditionally independent. The shared-data covariance is $\operatorname{Var}\{m(D)\}$ under the conditions of the theorem.
Assuming more repetitions solve every uncertainty problem. More repetitions can reduce Monte Carlo error in estimating $m(D)$. They do not create new observations or eliminate data-sampling variation.
Calling $s_R/\sqrt R$ a standard error for risk without qualification. It is a conditional Monte Carlo standard error for the repeated-score average, under independent partition draws and finite conditional variance. A population-risk interpretation needs additional justification.

In practice, state which randomness an uncertainty summary concerns. If the aim is to assess sensitivity to the choice of folds, report the repeated-score distribution or its spread with that interpretation. If the aim is uncertainty about a population-risk target, do not substitute the spread across partitions as though each repetition were an independent sample. The target, the source of randomness, and the dependence structure all matter.

Check Your Understanding

Answer each question by identifying both the relevant randomness and the quantity being estimated.

Under what conditions are repeated cross-validation scores independent conditional on the observed data?
Why can two scores from independently randomized partitions have positive unconditional covariance?
What uncertainty does $s_R/\sqrt R$ describe when calculated from repeated scores?
In the variance decomposition for $\bar S_R$, which term decreases as the number of repetitions grows, and which term does not?
Why does dividing the standard deviation of $K$ fold scores by $\sqrt K$ not, on its own, establish a standard error for population risk?