Stratified k-Fold Cross-Validation and the Variance of the Estimate

A single holdout yields one number, and one number cannot tell whether a difference between two models is a property of the models or of the split. k-fold cross-validation replaces the single partition with k partitions and produces k scores whose spread is informative. The mechanism is a partition, k fits, and an average; the interesting parts are what the spread means and why it understates the uncertainty of the average.

The partition and the k fits

Shuffle the rows, cut them into k blocks of near-equal size, and for each block fit on the other k-1 and score on the held-out block. Every row is scored exactly once, so the k scores partition the data and the mean of the k scores is the cross-validated estimate. With k = 5 each fit uses 80 percent of the rows; with k = 10, 90 percent.

Two regimes have different behaviour. At k = n, leave-one-out, each fit differs from the full-data fit by a single row, so the estimate is nearly unbiased for the risk of the model trained on n-1 rows. The cost is n fits, and for most model families the n fits are far more expensive than the ten of 10-fold. Leave-one-out also has a variance problem: the n training sets overlap in n-2 rows, so the n scores are almost the same number repeated, and their spread carries very little information about the variability of the estimate itself. The bias-variance story for leave-one-out is famously counterintuitive; the practical summary is that it is unbiased and uninformative about its own precision, which is a poor combination.

The bias of k-fold comes from training on $(k-1)/k$ of the data. A learning curve that is still rising at that fraction means the cross-validated score underestimates the performance of the model fitted on everything. For k = 5 the deficit is larger than for k = 10, and on datasets in the low hundreds of rows the difference between 5-fold and 10-fold estimates can exceed the difference between the models being compared. This is a bias, not noise: repeating the procedure does not remove it.

What the fold-to-fold spread does and does not measure

The sample standard deviation of the k scores is routinely reported as the uncertainty of the estimate, and it is not that. The scores are dependent, because every pair of training sets shares $k-2$ of the k blocks. Dependence reduces the variance of the mean below what the naive formula $\hat\sigma/\sqrt{k}$ would give, so the reported interval is too wide; simultaneously, the k scores are measured on disjoint blocks of rows and so do not capture the variability that comes from drawing a different set of rows entirely, which makes the interval too narrow with respect to the quantity usually wanted. The two errors do not cancel in a predictable direction.

The correct statement is narrow. The fold spread estimates how much the score moves when the partition changes, holding the row set fixed. It is a diagnostic for partition sensitivity: a large spread means the estimate depends on which rows landed in which block, which usually indicates high-variance learners or a small sample. It is not a confidence interval for the risk.

Getting an interval for the risk requires repeating the whole procedure with different shuffles, which is what repeated k-fold does. Ten repetitions of 10-fold give a hundred scores, and the mean of the hundred is a lower-variance estimate than a single run. The repetitions are still not independent draws from the population, so a t-interval over the hundred is still optimistic, but the optimism shrinks as the number of repetitions grows because each repetition resamples the row set independently. Reported practice varies; the safe reading is that repetition improves the estimate and does not license a parametric interval.

The variance of the cross-validated estimate also has a floor set by the test-block size. With k = 10 each score is computed on a tenth of the data, so each individual score carries a standard error about $\sqrt{10}$ times the standard error of a full-data score. Averaging ten of them recovers much of that, but the recovered precision is bounded by the correlations between the blocks.

Stratification: what it fixes and what it does not

A plain random partition assigns class counts to blocks by sampling without replacement, so block prevalence fluctuates around the global prevalence. With a 2 percent positive class and 200 rows, four positives in total, a 10-fold split produces blocks holding zero, one, or two positives, and the score for a block with zero positives is undefined for recall and degenerate for most threshold-free ranking metrics. Stratified k-fold fixes the block composition by distributing each class across blocks in proportion, so every block has the global prevalence up to rounding.

The gain is in bias as well as variance. Under a random partition, some training sets contain no positive examples at all, and a model fitted on such a set cannot learn the positive class; its score on the matching block is not a sample from the distribution of scores of a properly trained model. Stratification removes that failure mode, which is why it matters most exactly where the class is rare.

The limit is that stratification controls the marginal class distribution and nothing else. It does not balance a continuous covariate, it does not respect group structure, and it does not respect time order. A stratified split of rows that belong to the same subject still places the subject on both sides. The group-aware alternative is covered in Grouped Splits When Observations Are Not Independent, and the time-ordered case in Blocked and Rolling-Origin Validation for Time-Ordered Data.

Stratification on a continuous target is a separate problem. Binning the target and stratifying on the bin approximates proportional allocation but introduces a discontinuity at bin edges; a row near an edge may be assigned to a block whose target distribution differs from its own neighbourhood. The usual compromise is to sort by target and assign rows to blocks in a serpentine order, which controls the target mean of each block without committing to bin boundaries.

How the fold count changes the estimate

The bias of k-fold is a function of the training fraction, and the variance is a function of the number of folds and their correlation. For a rare positive class, both effects are amplified. Each fit sees $(k-1)/k$ of the positives, so with 40 positives and 5-fold, each training block contains 32 of them; the model’s recall estimate on that block rests on 8 positives, and its variance is correspondingly large. At 10-fold, each block holds 36 positives and each test block 4, so the per-fold recall is estimated from 4 rows and the average across 10 folds from all 40.

The average across folds is what recovers the precision, and the recovery is complete in the sense that every row is scored once. This is the strongest argument for cross-validation over a single holdout on rare classes: the holdout with 20 percent of 200 rows contains 40 rows and perhaps 2 positives, while 5-fold cross-validation scores all 200 rows and every positive contributes to exactly one score.

The recovery has a limit. The folds share training data, so their scores are correlated, and the variance of the mean is larger than the independent-sampling formula suggests. With 40 positives, the number of independent units available for the recall estimate is closer to 40 than to 200, and the interval width should reflect that. Computing the interval from the positive count, not the row count, is the correction that matters.

Choosing k under a fixed compute budget

k-fold costs k fits plus, in the usual implementation, one final fit on all data. The compute budget therefore fixes the largest feasible k, and the question becomes how to spend it. For a model whose fit cost grows superlinearly in rows, larger k also means each fit is more expensive, so the total cost grows faster than k. At k = 10 with a quadratic fit cost, the total is roughly $10 \times 0.9^2 = 8.1$ times a single full fit; at k = 5 it is $5 \times 0.8^2 = 3.2$.

Below about a few hundred rows, the training-fraction bias dominates and leave-one-out or repeated 10-fold is defensible. Between hundreds and tens of thousands, 5-fold and 10-fold are the conventional range; 10-fold reduces bias at twice the cost of 5-fold, and the choice between them is usually made on cost rather than on measured difference. Above that, a single holdout large enough to resolve the differences of interest is cheaper than cross-validation and equally informative, which is the argument in Why a Held-Out Test Set Cannot Be Reused.

One further cost is easy to overlook: any preprocessing that estimates parameters from data must be re-fitted inside each fold. If scaling statistics are computed once outside the loop, the cross-validated score is optimistic by an amount that depends on how much the transformation can memorise. Wrapping the whole procedure, transformation included, in the fold loop is the only arrangement that measures what it claims to measure.