Cross-Validation and When It Is Overkill

Cross-validation is taught as a best practice, which is how it ends up applied to a million-row dataset where it costs five times as much and changes nothing. It is not a practice, it is a variance-reduction technique, and whether you need it is a calculation.

The error bar on one split

Hold out n examples and measure accuracy p. Each held-out example is a Bernoulli trial — correct or not — so the count of correct predictions is binomial and the standard error of the proportion is:

SE(p) = √( p(1 − p) / n )

n = 100    p = 0.90   →  SE = 3.00 points
n = 500    p = 0.90   →  SE = 1.34 points
n = 2,000  p = 0.90   →  SE = 0.67 points
n = 10,000 p = 0.90   →  SE = 0.30 points

Assumptions: the held-out examples are independent draws from the population you care about, and the model is fixed before measurement. Both fail in ways worth knowing — correlated examples (multiple rows per customer) inflate the true error beyond this, and measuring after selecting inflates the estimate itself, as the best-of-k arithmetic shows.

Now the decision has a shape. A 95% interval is roughly ±2 SE, so at n = 100 your accuracy is 90% ± 6 points. Two models that differ by 3 points are not distinguishable. If that ambiguity is unacceptable and you cannot get more data, cross-validation is what you reach for.

What k-fold buys

Split the data into k parts. Train k times, each time holding out a different part, and average the scores. Every example is tested exactly once, so the final estimate is computed over all N rows rather than over a fraction of them, and each model is trained on (k−1)/k of the data rather than on, say, 80%.

Two real gains. The estimate is averaged over k different held-out sets, so it is far less sensitive to one unlucky split. And the spread across folds is itself information: five folds reporting 0.81, 0.83, 0.82, 0.84, 0.82 is a stable model, while 0.71, 0.88, 0.79, 0.91, 0.74 says the result depends heavily on which rows landed where, and you should go and find out why before tuning anything.

The cost is exactly k times the training compute, and it is linear with no discount. That is the entire trade.

Choosing k is itself a bias-variance question, which is why the conventional answers are 5 and 10 rather than something derived. A small k means each model trains on a smaller fraction of the data — at k = 2, on half of it — so the scores are pessimistic relative to the model you will finally fit on everything. A large k removes that bias, because each training set is nearly the full dataset, but the fold scores become more variable and the compute bill grows linearly. Five folds trains on 80% and costs five runs; ten folds trains on 90% and costs ten. If the choice between them changes your conclusion, the conclusion was not robust enough to act on.

Repeated k-fold — running the whole procedure several times with different random partitions and averaging — is the cheap way to see whether a result depends on the partition. It does not fix the variance problem below, but a mean that moves by two points between repetitions has told you something useful for the price of one more run.

The variance k-fold does not fix

Here is the part that is usually left out. The k fold scores are not independent, because their training sets overlap heavily — any two folds share (k−2)/(k−1) of their training data. So the usual move of computing a standard error from the fold scores as if they were k independent measurements understates the uncertainty.

This is not a technicality that someone might tidy up later. Bengio and Grandvalet showed (JMLR, 2004, “No unbiased estimator of the variance of k-fold cross-validation”) that no unbiased estimator of that variance exists in general. The practical reading: treat the fold spread as a qualitative stability signal, not as a confidence interval, and be suspicious of any “significant improvement” claimed from cross-validated means alone. When you need a defensible interval, a genuinely untouched test set is the honest instrument.

When one split is enough

• The held-out set is already large. At n = 10,000 the error bar is 0.3 points. Five-fold cross-validation would spend five times the compute to shave a fraction of that. Skip it.
• Training is expensive. Anything involving a GPU for hours makes k training runs a real budget line. Use a single large split and spend the saved compute on more configurations or more data.
• Time matters. For time-ordered data, ordinary k-fold is not conservative-but-fine, it is wrong — it trains on the future. Use forward chaining or nothing.
• The data are small. Under a few thousand rows, cross-validation is not optional; a single split throws away too much and estimates too little.

The variants that are not optional