揭示交叉验证在分类任务中的根本局限性，给出误差下界
Minimax Limits of k-Fold Cross-Validation via Majority
- 用多数投票法分析交叉验证的误差行为
- 证明当折叠数随样本量增长时，误差下界为Ω(√k/n)
- 为交叉验证提供严格理论基准，适合方法研究者
我们研究了k折交叉验证作为风险估计器的均方误差，重点关注其精度如何随折叠数k变化。尽管交叉验证广泛应用，但关于k选择的合理指导几乎缺失，主要源于各折误差估计之间的复杂依赖关系。为获得精确可解释的结果，我们聚焦于二分类中的多数投票算法——一种最简非平凡的经验风险最小化方法。通过精细分析其交叉验证行为，发现即使该简单算法也表现出微妙而复杂的特性，现有理论对此仅给出松散甚至无意义的上界。基于此分析，我们引入交叉验证风险估计的极小极大框架，并证明：当折叠数随样本量n增长时，任何经验风险最小化算法都无法实现O(1/n)的极小极大均方误差；不可避免的下界为Ω(√k/n)。结果揭示了交叉验证作为数据重用策略的根本局限，澄清了先前理论工作中的差距与不准确之处，并将多数投票算法定位为任何紧致分析都必须解释的自然基准。
原文摘要 · Abstract (English)
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 $Ω(\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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。