Optimal Fold Selection in Cross Validation

This direction is no longer present in the current build. Its last version stays readable and citable here.

Version 1 of 111 papers19 conceptsfrozen 2026-10-04

In machine learning, $k$-fold cross-validation is the standard tool for estimating how well a model will generalize to unseen data. For decades, practitioners have relied on a "rule of thumb," typically setting $k=5$ or $k=10$. While these values often work well in practice, they are frequently applied without a clear understanding of the underlying trade-offs.

Recent research has moved beyond these heuristics, providing a rigorous mathematical foundation for choosing $k$. The choice of $k$ is not just a computational preference; it is a mechanism to balance the bias and variance of the error estimate based on the stability of the learning algorithm and the size of the dataset.

The Bias of Small $k$

When we use a small number of folds (e.g., $k=2$), each training set is only half the size of the total available data. Because most learning algorithms perform worse with less data, the error measured on the test fold will be higher than the error the model would achieve if trained on the full dataset. This creates a negative bias, where cross-validation underestimates the model's true performance.

As Nikolaus Kriegeskorte notes, this bias is the primary reason to avoid very small $k$ values in fields like brain imaging, where data is scarce and every sample counts toward a representative training set. Jian Hong and Timothy S. Fisher formalize this in their work on Generalization Ability, showing that the bias decreases as $k$ increases because the training subsets become more representative of the total population.

The Variance of Large $k$

It is tempting to think that more folds are always better. If $k=10$ is good, wouldn't $k=N$ (Leave-One-Out) be perfect? Surprisingly, the answer is often no.

As $k$ increases, the training sets in each fold begin to overlap significantly. For example, in 10-fold CV, any two training sets share 80% of the same data. In Leave-One-Out, they share nearly 100%. This high overlap makes the performance estimates across folds highly correlated. Ron Kohavi demonstrated that this correlation leads to higher variance in the final estimate, meaning the result is more sensitive to the specific "luck of the draw" in the dataset.

Ido Nachum and colleagues explain in The Structure of Cross-Validation Error that the optimal $k$ depends on the algorithm's sensitivity. If an algorithm is "stable"—meaning its output doesn't change much when one data point is replaced—the correlation between folds is less problematic. However, for unstable algorithms, a smaller $k$ can actually produce a more reliable estimate by reducing this inter-fold correlation.

The Diminishing Returns of $k$

The relationship between $k$ and the quality of the estimate follows a pattern of diminishing returns. Matthieu Lerasle and Sylvain Arlot derived a variance formula for least-squares density estimation that follows a $1 + 4/(k-1)$ pattern.

This formula provides a theoretical justification for the "Rule of 10":

  • Increasing $k$ from 2 to 5 significantly reduces variance.
  • Increasing $k$ from 5 to 10 provides a smaller but still meaningful improvement.
  • Increasing $k$ beyond 10 yields very little benefit relative to the increased computational cost.

Optimizing $k$ as a Hyperparameter

Rather than treating $k$ as a fixed constant, some researchers suggest it should be optimized for the specific task at hand. Alessandro Ghio and his co-authors argue in The 'K' in K-fold Cross Validation that $k$ can be treated as a tunable hyperparameter. They found that for obtaining tight, statistically rigorous upper bounds on error, the optimal $k$ is often lower than 10—frequently falling between 3 and 4.

Hong and Fisher propose a unified framework called Generalization Error Minimization (GEM). Instead of relying on heuristics, GEM uses analytical generalization bounds to find a "minimax-optimal" $k$. This approach mathematically balances the bias (from smaller training sets) and the variance (from overlapping sets) to minimize the total expected error of the performance estimate.

Summary of the Trade-off

Fold Count ($k$) Training Set Size Bias Variance (Correlation) Computational Cost
Low (e.g., 2-3) Small High (Pessimistic) Low Low
Medium (e.g., 5-10) Large Low Moderate Moderate
High (e.g., N) Max Minimal High High

The "correct" $k$ is the one that sits at the valley of the total error curve for your specific algorithm and data size. While 10-fold stratified CV remains a robust default for model selection as Kohavi showed, modern theory suggests that for rigorous error bounding or highly unstable models, a smaller $k$ may actually be more precise.

Papers in this version

History & citationVersion 1 · 2026-10-04

No longer present in the current build · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_optimal_fold_selection_in_cross_validati_dc704272,
  title = {Optimal Fold Selection in Cross Validation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/optimal-fold-selection-in-cross-validation/rdr_dc704272ae194985aa0c91f98ef33088},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_optimal_fold_selection_in_cross_validati_dc704272_v1,
  title = {Optimal Fold Selection in Cross Validation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/optimal-fold-selection-in-cross-validation/rdr_dc704272ae194985aa0c91f98ef33088/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}