Minimax Limits of k-Fold Cross-Validation via Majority

We study the mean-squared error of 9-fold cross-validation as a risk estimator, with particular emphasis on how its accuracy depends on the number of folds 9. Despite the widespread use of cross-validation, principled guidance for choosing 9 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 $(1/