{"id":"arxiv/2605.25859","url":"https://arxiv.org/abs/2605.25859","tags":["math.ST","cs.LG"],"score":0,"title":"Minimax Limits of k-Fold Cross-Validation via Majority","domain":"math.ST","source":"arxiv","authors":["Ido Nachum","Rüdiger Urbanke","Thomas Weinberger"],"reviews":0,"subject":"math.ST","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-25","reactions":{}}