The Structure of Cross-Validation Error: Stability, Covariance, and Minimax Limits
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909984760004608 |
|---|---|
| author | Nachum, Ido Urbanke, Rüdiger Weinberger, Thomas |
| author_facet | Nachum, Ido Urbanke, Rüdiger Weinberger, Thomas |
| contents | 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{CV}}^{(k)}$ of the population risk $L_{D}$ satisfies the following minimax lower bound: \[ \min_{k \mid n} \max_{D} \mathbb{E}\left[\big(\widehat{L}_{\mathrm{CV}}^{(k)} - L_{D}\big)^{2}\right]=Ω\big(\sqrt{k^*}/n\big), \] 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 \[ \max_{D}\mathbb{E}\!\left[\big(\widehat{L}_{\mathrm{CV}}^{(k)} - L_{D}\big)^{2}\right]=Ω(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 $\sqrt{k}/n$ regimes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_03554 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Structure of Cross-Validation Error: Stability, Covariance, and Minimax Limits Nachum, Ido Urbanke, Rüdiger Weinberger, Thomas Statistics Theory Machine Learning 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{CV}}^{(k)}$ of the population risk $L_{D}$ satisfies the following minimax lower bound: \[ \min_{k \mid n} \max_{D} \mathbb{E}\left[\big(\widehat{L}_{\mathrm{CV}}^{(k)} - L_{D}\big)^{2}\right]=Ω\big(\sqrt{k^*}/n\big), \] 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 \[ \max_{D}\mathbb{E}\!\left[\big(\widehat{L}_{\mathrm{CV}}^{(k)} - L_{D}\big)^{2}\right]=Ω(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 $\sqrt{k}/n$ regimes. |
| title | The Structure of Cross-Validation Error: Stability, Covariance, and Minimax Limits |
| topic | Statistics Theory Machine Learning |
| url | https://arxiv.org/abs/2511.03554 |