Abstract: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(\sqrt{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.
| Subjects: | Statistics Theory (math.ST); Machine Learning (cs.LG) |
| Cite as: | arXiv:2605.25859 [math.ST] |
| (or arXiv:2605.25859v1 [math.ST] for this version) | |
| https://doi.org/10.48550/arXiv.2605.25859 arXiv-issued DOI via DataCite (pending registration) |
From: Thomas Weinberger [view email]
[v1]
Mon, 25 May 2026 13:50:05 UTC (44 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。