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 ${\widehat{L}}_{\mathrm{C}\mathrm{V}}^{(k)}$ of the population risk $L_D$ satisfies the following minimax lower bound: $$\underset{k\mid n}{\min }\underset{D}{\max }\mathbb{E}\left[\right({\widehat{L}}_{\mathrm{C}\mathrm{V}}^{(k)}-L_D{)}^2]=\mathrm{\Omega }\left(\sqrt{k^{\ast }}\mathrm{/}n\right),$$ where $n$ is the sample size, $k$ the number of folds, and $k^{\ast }$ 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\mathrm{/}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 $$\underset{D}{\max }\mathbb{E}\text{\hspace{0.17em}⁣}\left[\right({\widehat{L}}_{\mathrm{C}\mathrm{V}}^{(k)}-L_D{)}^2]=\mathrm{\Omega }(k\mathrm{/}n),$$ matching (up to constants) the accuracy of a hold-out estimator of a single fold of size $n\mathrm{/}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\mathrm{/}n$ and $\sqrt{k}\mathrm{/}n$ regimes.