The Structure of Cross-Validation Error: Stability, Covariance, and Minimax Limits

Despite ongoing theoretical research on cross-validation (CV), many theoretical questions remain widely open. This motivates our investigation into how properties of algorithm-distribution pairs can affect the choice for the number of folds in k-fold CV. Our results consist of a novel decomposition of the mean-squared error of cross-validation for risk estimation, which explicitly captures the correlations of error estimates across overlapping folds and includes a novel algorithmic stability notion, squared loss stability, that is considerably weaker than the typically required hypothesis stability in other comparable works. Furthermore, we prove: 1. For any learning algorithm that minimizes empirical risk, the mean-squared error of the k-fold cross-validation estimator widehatLCV(k) of the population risk LD satisfies the following minimax lower bound: [ mink mid n maxD mathbbEleft[big(widehatLCV(k) - LDbig)2right]=Omegabig(√k^*/nbig), ] where n is the sample size, k the number of folds, and k^* denotes the number of folds attaining the minimax optimum. This shows that even under idealized conditions, for large values of k, CV cannot attain the optimum of order 1/n achievable by a validation set of size n, reflecting an inherent penalty caused by dependence between folds. 2. Complementing this, we exhibit learning rules for which [ maxDmathbbE!left[big(widehatLCV(k) - LDbig)2right]=Omega(k/n), ] matching (up to constants) the accuracy of a hold-out estimator of a single fold of size n/k. Together these results delineate the fundamental trade-off in resampling-based risk estimation: CV cannot fully exploit all n samples for unbiased risk evaluation, and its minimax performance is pinned between the k/n and √k/n regimes.