K-fold cross-validation is asymptotically consistent for model comparison even though it is first-order uninformative for risk estimation: the model-independent oracle term cancels when two prediction rules are compared (Wager 2019, making explicit a phenomenon implicit in Yang 2007), for algorithms whose root-mean-squared excess error decays as n−γn^{-\gamma} with 1/4<γ<1/21/4<\gamma<1/2 and where one of the two rules is asymptotically strictly better. The open problem, posed in Wager's discussion of Rosset and Tibshirani's random-X optimism theory, is to determine whether the covariance-penalty (optimism) framework admits a natural extension from estimating the risk of a single prediction rule to the comparison of prediction rules and, if it does, to characterize the bias incurred when cross-validated or apparent errors are used to compare rules, express it analytically as a covariance-penalty-type quantity, and construct bias-corrected comparison procedures. Wager's note poses this question in the random-X squared-error setting, for root-mean-squared excess-error decay rates n−γn^{-\gamma} with 1/4<γ<1/21/4<\gamma<1/2, and with purely asymptotic conclusions; other loss functions, other convergence-rate regimes, and finite-sample validity are territory the note leaves open rather than part of the question it asks. A 2024 survey of the area (Iyengar, Lam, and Wang) still describes the theoretical understanding of model selection as wide open; no existing work supplies the comparison-optimism theory.

Background

Suppose we observe nn independent copies (Xi,Yi)(X_i,Y_i) of a feature–response pair and fit a prediction rule (the output of an algorithm such as linear regression, the lasso (linear regression with an ℓ1\ell_1-penalty on the coefficients), or a smoothing method) that predicts YY from XX. The apparent error of a rule is its average error on the very data used to fit it, and it typically understates the rule's true prediction error on a fresh draw from the same distribution. Efron (1983, 2004) quantified this gap — called the optimism — and showed that for linear fitting rules the optimism can be written as a covariance penalty, an analytic correction proportional to the effective degrees of freedom: Mallows' CpC_p and Stein's unbiased risk estimate (SURE), derived from the trace of the 'hat' matrix mapping observed responses to fitted values, are the classical examples. Rosset and Tibshirani (2020) carried this program from the fixed-X setting (features treated as fixed by design) to the random-X setting (features drawn from an unknown distribution), where the optimism acquires new terms, and compared such covariance-penalty estimates with cross-validation.

K-fold cross-validation (CV) is the generic data-driven alternative: split the data into KK parts (folds), fit the algorithm on the data with one fold removed, average its held-out error over the folds, and repeat. Wager (2019), in a discussion of Rosset and Tibshirani (2020), analyzed K-fold CV under squared-error loss for algorithms whose root-mean-squared excess error (error above the Bayes error, the error of the best possible predictor of YY from XX) decays as n−γn^{-\gamma} with 1/4<γ<1/21/4<\gamma<1/2. Writing the CV estimate as a sum CV^n=CV^n∗+2Zn,K+Δn,K2\widehat{CV}_n=\widehat{CV}^*_n+2Z_{n,K}+\Delta^2_{n,K} — an oracle term CV^n∗\widehat{CV}^*_n that estimates the irreducible noise floor and is the same for every algorithm, a cross-term Zn,KZ_{n,K}, and the algorithm's excess error — he observed two facts. First, for risk estimation the oracle term dominates, so CV is to first order identical across algorithms and asymptotically uninformative about which rule has smaller risk. Second, when the task is model comparison — deciding which of two rules has smaller test error — the model-independent oracle term is common to both rules and cancels in their CV difference, so the CV comparison is asymptotically consistent, provided one of the two rules is asymptotically strictly better than the other (a larger rate exponent γ\gamma, or equal exponents with a smaller leading constant); near-tied or exactly matched pairs fall outside this result. This 'cancellation effect' is implicit in Yang (2007), who proved consistency of CV for comparing regression procedures; Lian (2009) extended the comparison-consistency question to multiple density estimators. What remains missing is the analytic side of the story: Efron-style covariance penalties exist for the risk of a single rule, but no analogous theory quantifies the optimism incurred when apparent or cross-validated errors are used to compare rules.

Problem Statement

Under random-X sampling with squared-error loss, the cancellation effect makes K-fold CV comparison consistent for two algorithms whose root-mean-squared excess error decays as n−γn^{-\gamma} with 1/4<γ<1/21/4<\gamma<1/2 when one of them is asymptotically strictly better — a larger rate exponent γ\gamma, or equal exponents with a smaller leading constant (Wager 2019, Proposition 2; Yang 2007). The open problem is to determine whether the optimism (covariance-penalty) framework of Rosset and Tibshirani (2020) admits a natural extension from risk estimation of a single prediction rule to model comparison, and if so to:

  1. Define and characterize the comparison optimism: the bias of the apparent or cross-validated comparison between two (or more) prediction rules relative to their true test-error comparison — the analogue, for comparisons, of the optimism of a single rule's apparent error — including an explicit identity or asymptotic formula for it in terms of covariance-penalty-type quantities under random-X sampling.
  2. Construct bias-corrected comparison procedures: estimators that subtract the estimated comparison optimism and deliver corrected model comparisons.

The objective is an analytic theory of comparison optimism paralleling the existing theory of estimation optimism, posed in the random-X squared-error setting in which Wager's question and the Rosset–Tibshirani optimism results are stated. Wager's note is confined to squared-error loss, to root-mean-squared excess-error decay rates n−γn^{-\gamma} with 1/4<γ<1/21/4<\gamma<1/2, and to purely asymptotic conclusions; establishing the reach of the cancellation effect on which such corrections build — for losses beyond squared error, for convergence-rate regimes faster than n−1/2n^{-1/2} or slower than n−1/4n^{-1/4}, and with finite-sample corrections — lies in territory the note leaves open and is a natural direction of extension rather than a requirement of the problem as posed here.

References

  1. Stefan Wager, 'Cross-Validation, Risk Estimation, and Model Selection', arXiv:1909.11696 (2019), DOI 10.48550/arXiv.1909.11696, https://arxiv.org/abs/1909.11696; published as 'Cross-Validation, Risk Estimation, and Model Selection: Comment on a Paper by Rosset and Tibshirani', Journal of the American Statistical Association 115(529):157–160 (2020), DOI 10.1080/01621459.2020.1727235
  2. Saharon Rosset and Ryan J. Tibshirani, 'From Fixed-X to Random-X Regression: Bias-Variance Decompositions, Covariance Penalties, and Prediction Error Estimation', Journal of the American Statistical Association 115(529):138–151 (2020), DOI 10.1080/01621459.2018.1424632, https://doi.org/10.1080/01621459.2018.1424632
  3. Saharon Rosset and Ryan J. Tibshirani, 'From Fixed-X to Random-X Regression: Bias-Variance Decompositions, Covariance Penalties, and Prediction Error Estimation: Rejoinder', Journal of the American Statistical Association 115(529):161–162 (2020), DOI 10.1080/01621459.2020.1727236, https://doi.org/10.1080/01621459.2020.1727236
  4. Xiaotong Shen and Hsin-Cheng Huang, 'Discussion of "From Fixed-X to Random-X Regression: Bias-Variance Decompositions, Covariance Penalties, and Prediction Error Estimation"', Journal of the American Statistical Association 115(529):152–156 (2020), DOI 10.1080/01621459.2018.1543597, https://doi.org/10.1080/01621459.2018.1543597
  5. Yuhong Yang, 'Consistency of cross validation for comparing regression procedures', The Annals of Statistics 35(6):2450–2473 (2007), DOI 10.1214/009053607000000514, https://doi.org/10.1214/009053607000000514
  6. Heng Lian, 'Cross-validation for comparing multiple density estimation procedures', Statistics & Probability Letters 79:112–115 (2009), DOI 10.1016/j.spl.2008.07.029, https://doi.org/10.1016/j.spl.2008.07.029
  7. Bradley Efron, 'Estimating the Error Rate of a Prediction Rule: Improvement on Cross-Validation', Journal of the American Statistical Association 78(382):316–331 (1983), DOI 10.1080/01621459.1983.10477973, https://doi.org/10.1080/01621459.1983.10477973
  8. Bradley Efron, 'The Estimation of Prediction Error: Covariance Penalties and Cross-Validation', Journal of the American Statistical Association 99(467):619–632 (2004), DOI 10.1198/016214504000000692, https://doi.org/10.1198/016214504000000692
  9. Stephen Bates, Trevor Hastie, and Robert Tibshirani, 'Cross-validation: what does it estimate and how well does it do it?', arXiv:2104.00673 (2021), DOI 10.48550/arXiv.2104.00673, https://arxiv.org/abs/2104.00673; published as 'Cross-Validation: What Does It Estimate and How Well Does It Do It?', Journal of the American Statistical Association 119(546):1434–1445 (2024), DOI 10.1080/01621459.2023.2197686
  10. Pierre Bayle, Alexandre Bayle, Lucas Janson, and Lester Mackey, 'Cross-validation Confidence Intervals for Test Error', arXiv:2007.12671 (2020), DOI 10.48550/arXiv.2007.12671, https://arxiv.org/abs/2007.12671
  11. Alexandre Bayle, Lucas Janson, and Lester Mackey, 'The Relative Instability of Model Comparison with Cross-validation', arXiv:2508.04409 (2025), DOI 10.48550/arXiv.2508.04409, https://arxiv.org/abs/2508.04409
  12. Morgane Austern and Wenda Zhou, 'Asymptotics of Cross-Validation', arXiv:2001.11111 (2020), DOI 10.48550/arXiv.2001.11111, https://arxiv.org/abs/2001.11111
  13. Pratik Patil, Jin-Hong Du, and Ryan J. Tibshirani, 'Revisiting Optimism and Model Complexity in the Wake of Overparameterized Machine Learning', arXiv:2410.01259 (2024), DOI 10.48550/arXiv.2410.01259, https://arxiv.org/abs/2410.01259
  14. Hengrui Luo and Yunzhang Zhu, 'Asymptotic Optimism of Random-Design Linear and Kernel Regression Models', arXiv:2502.12999 (2025), DOI 10.48550/arXiv.2502.12999, https://arxiv.org/abs/2502.12999
  15. Haoming Shi, Eric C. Chi, and Hengrui Luo, 'Asymptotic Optimism for Tensor Regression Models with Applications to Neural Network Compression', arXiv:2603.26048 (2026), DOI 10.48550/arXiv.2603.26048, https://arxiv.org/abs/2603.26048
  16. Garud Iyengar, Henry Lam, and Tianyu Wang, 'Is Cross-Validation the Gold Standard to Evaluate Model Performance?', arXiv:2407.02754 (2024), DOI 10.48550/arXiv.2407.02754, https://arxiv.org/abs/2407.02754