# Minimax Limits of k-Fold Cross-Validation via Majority

arXiv: https://arxiv.org/abs/2605.25859 · HTML: https://mlsanity.com/paper/2605.25859/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 25 references that are in the map.
- First posted on arXiv 25 May 2026.

## Builds on (most cited first, 5 of 5)

- [Fantastic Generalization Measures and Where to Find Them](https://mlsanity.com/paper/1912.02178/) (2019)
- [In Search of Robust Measures of Generalization](https://mlsanity.com/paper/2010.11924/) (2020)
- [Cross-validation Confidence Intervals for Test Error](https://mlsanity.com/paper/2007.12671/) (2020)
- [Fantastic Generalization Measures are Nowhere to be Found](https://mlsanity.com/paper/2309.13658/) (2023)
- [Which Algorithms Have Tight Generalization Bounds?](https://mlsanity.com/paper/2410.01969/) (2024)

## Abstract (arXiv)

We study the mean-squared error of k-fold cross-validation as a risk estimator, with particular emphasis on how its accuracy depends on the number of folds k. Despite the widespread use of cross-validation, principled guidance for choosing k is largely absent, mainly due to the complex dependence between fold-wise error estimates. To obtain sharp and interpretable results, we focus on the majority algorithm in binary classification, a minimal yet nontrivial empirical risk minimization procedure. We provide a fine-grained analysis of its cross-validation behavior, showing that even this simple algorithm exhibits subtle and delicate phenomena for which existing theory provides loose and even vacuous bounds. Leveraging this analysis, we introduce a minimax framework for cross-validation risk estimation and prove that no empirical risk minimization algorithm can achieve an O(1/n) minimax mean-squared error when the number of folds grows with the number of samples n; instead, a lower bound of order Omega(√k/n) is unavoidable. Our results reveal fundamental limitations of cross-validation as a data-reuse strategy, clarify gaps and inaccuracies in prior theoretical work, and position the majority algorithm as a natural benchmark that any tight analysis of cross-validation should be able to explain.