PaperlayerView exact revision on arXiv

Source-linked AI summary

Cross-validation: what does it estimate and how well does it do it?

Stephen Bates, Trevor Hastie, Robert Tibshirani

arXiv:2104.00673v4stat.MEmath.STstat.COstat.ML

TL;DR

Cross-validation’s estimand and confidence-interval coverage are not fully understood. This paper analyzes these issues and introduces nested cross-validation, finding that common error estimates target average prediction error and that nested intervals achieve superior coverage.

  • Problem

    The paper asks what prediction error cross-validation estimates and whether its confidence intervals achieve reliable coverage.

  • Method

    The authors prove cross-validation’s estimand for ordinary least squares, examine related estimators, and introduce nested cross-validation to estimate uncertainty more accurately.

  • Results

    Common prediction-error estimates target average error across hypothetical training sets, while nested cross-validation consistently provides superior confidence-interval coverage to naïve cross-validation.

  • Takeaways & Limitations

    Cross-validation should be interpreted as estimating average prediction error, and nested cross-validation is an appealing approach for prediction-error confidence intervals.

  • Takeaways & Limitations

    The conditions under which standard cross-validation intervals require nested computations remain an open question, particularly across sample sizes, dimensions, and regularization levels.

Abstract

from arXiv · show

Cross-validation is a widely-used technique to estimate prediction error, but its behavior is complex and not fully understood. Ideally, one would like to think that cross-validation estimates the prediction error for the model at hand, fit to the training data. We prove that this is not the case for the linear model fit by ordinary least squares; rather it estimates the average prediction error of models fit on other unseen training sets drawn from the same population. We further show that this phenomenon occurs for most popular estimates of prediction error, including data splitting, bootstrapping, and Mallow's Cp. Next, the standard confidence intervals for prediction error derived from cross-validation may have coverage far below the desired level. Because each data point is used for both training and testing, there are correlations among the measured accuracies for each fold, and so the usual estimate of variance is too small. We introduce a nested cross-validation scheme to estimate this variance more accurately, and we show empirically that this modification leads to intervals with approximately correct coverage in many examples where traditional cross-validation intervals fail.

1 Introduction

This work examines what cross-validation estimates and how reliably it supports prediction-error inference. It shows that CV targets average error across unseen training sets rather than the observed-data fit, while nested CV improves confidence-interval coverage over standard CV.

  • Estimand: CV’s estimand is difficult to state precisely, but evidence suggests it tracks average prediction error across training sets rather than the observed-data model’s accuracy.The paper proves this distinction for linear models using finite-sample conditional independence and supporting asymptotic results.
  • Inference: The paper introduces nested cross-validation to estimate prediction-error variance more accurately than standard CV.The method addresses covariance among fold-level accuracies caused by reusing each observation for both training and testing.
  • Results: Extensive numerical experiments show that the proposed method has consistently better confidence-interval coverage than standard cross-validation.The paper reports approximately correct coverage in examples where traditional CV intervals fail.

2 Setting and notation

The section formalizes supervised learning with i.i.d. training data, a loss function, and a model-fitting algorithm. It distinguishes the fitted model’s random out-of-sample error from its average across possible training sets.

  • Data and generalization: Training examples (X_i, Y_i) are assumed i.i.d. from a population distribution P, and generalization is evaluated on unseen data.The framework uses features X = (X_1, …, X_n) and responses Y = (Y_1, …, Y_n).
  • Loss and models: Prediction performance is measured with a nonnegative loss function, including squared error, misclassification error, and deviance.The loss satisfies ℓ(y, y) = 0.
  • Loss and models: A model-fitting algorithm A maps observed data to fitted parameters ˆθ, which define predictions through the parameterized model ˆf(x, θ).The parameter vector belongs to the model’s parameter space Θ.
  • Error targets: The out-of-sample error Err_XY is the loss averaged over an independent test point from P and is therefore random because it depends on the training data.Its expectation over possible training sets provides a separate population-level target.

3 What prediction error are we estimating?

Cross-validation estimates average prediction error across new same-sized training sets (Err) more accurately than the error of the model fit to the observed training data (ErrXY). This distinction extends beyond cross-validation, while finite-sample bias depends on the asymptotic regime and can be reduced with more folds.

  • Other estimators: The same distinction applies to other prediction-error estimators: data splitting, bootstrapping, covariance penalties, and Mallows’ Cp generally target Err or ErrX more closely than ErrXY.Mallows’ Cp is explicitly described as unable to estimate ErrXY and instead estimating Errin, Err, or ErrX.
  • Prediction-error estimands: ErrXY measures the error of the model fit to the observed training set, whereas Err averages errors from fitting on new same-sized datasets drawn from P.ErrXY is most relevant for deploying a specific model; Err may be useful for comparing fitting algorithms.
  • Cross-validation’s target: For OLS, cross-validation has lower MSE when estimating Err than ErrXY, so it should be viewed primarily as an estimator of Err.The result is established under the homoskedastic linear model and follows because cross-validation is linearly invariant.
  • Cross-validation’s target: Cross-validation is estimating average error Err more than specific error ErrXY, with ErrX serving as an intermediate target whose variability is closer to Err’s.The fluctuations of ErrXY and the cross-validation estimate are asymptotically uncorrelated, and cross-validation has larger error for estimating ErrXY than Err or ErrX.
  • Bias and asymptotic regimes: Bias depends on the asymptotic regime: it is typically O(1/n) in the parametric regime, can approach a nonzero constant in proportional dense settings, and may be appreciable for sparse regression.Increasing the number of folds as n grows can mitigate bias in all three regimes.

4 Confidence intervals with nested cross-validation

This section explains why naïve cross-validation confidence intervals are too narrow and develops nested cross-validation to estimate prediction-error MSE and achieve approximately valid coverage. The method accounts for dependence among fold errors and can also estimate sample-size bias.

  • Nested cross-validation: The proposed procedure estimates the mean-squared error of the cross-validation point estimate to construct confidence intervals for ErrXY.MSE incorporates both bias and variance, making it suitable for intervals around a potentially biased point estimate.
  • Why naïve intervals fail: In one example, the estimated variance is approximately 2.65 times too small, making naïve confidence intervals approximately 1.6 times too small.Positive within- and between-fold covariances explain why the independent-error approximation fails.
  • Why naïve intervals fail: Naïve cross-validation intervals underestimate variance because using each point for both training and testing induces dependence among observed errors.The usual variance estimate implicitly assumes zero covariance among errors in the same and different folds.
  • Coverage improvement: By avoiding the faulty independence approximation, nested cross-validation produces intervals with superior coverage.It empirically estimates how much intervals must be widened to cover holdout error averages before converting the calibrated prediction interval into a confidence interval.
  • Nested cross-validation: Nested cross-validation estimates MSE by applying (K −1)-fold cross-validation across many random outer splits and averaging the resulting error estimates.The procedure uses nested sample splitting to estimate the components of the MSE and obtain a point estimate of error.
  • Bias correction: Nested cross-validation can estimate sample-size bias by comparing models fit with n(K −2)/K and n(K −1)/K data points.The paper identifies this bias comparison as noncritical to the core MSE estimation proposal.

5 Simulation experiments

Across logistic-regression, OLS, and lasso simulations, nested cross-validation generally achieved coverage closer to the nominal target than naïve cross-validation, though performance varied by setting. The simulations also examined estimand precision, interval widths, and invariance to signal and feature transformations.

  • Low-dimensional logistic regression: Nested cross-validation gave coverage much closer to the nominal target than naïve cross-validation in the low-dimensional logistic-regression experiment.The nominal total error rate was 10%, with 5% miscoverage in each tail.
  • Estimands: In logistic regression, the cross-validation point estimate was slightly more precise for Err than for ErrXY, while their correlation was small but larger than in the OLS case.These findings came from simulations with Bayes error rate 22.5% while varying n and p.
  • High-dimensional logistic regression: In the high-dimensional sparse logistic-regression experiment, nested cross-validation again produced better coverage than naïve cross-validation.The experiment used n ∈ {90, 200}, p = 1000, and sparse logistic regression with four nonzero covariance entries.
  • OLS: In the OLS simulations, the coverage of both cross-validation methods was unaffected by the choice of θ and remained unchanged under full-rank linear transformations of Gaussian features.The analysis therefore set θ to 0 without loss of generality and extended to Gaussian features with any full-rank correlation structure.
  • High-dimensional linear regression: For high-dimensional lasso regression, nested cross-validation had better coverage than naïve cross-validation, although both struggled when n = 50.The ratio of nested to naïve interval width was relatively stable across observations.

6 Real data examples

On UCI real-data examples, nested cross-validation was evaluated by repeatedly subsampling observations and checking fitted-model accuracy on the remaining data. Nested CV generally achieved coverage closer to nominal levels than naïve CV, while data splitting performed poorly with small samples.

  • Evaluation design: Nested CV was evaluated by repeatedly subsampling observations, applying the procedure, and assessing fitted-model accuracy on the many remaining observations.The evaluation used real datasets from the UCI repository.
  • Data and models: The experiments used sparse linear or logistic regression on real-data prediction tasks.Tasks included crime-rate prediction and binary crop classification.
  • Coverage results: Nested CV generally had coverage much closer to the nominal rate than naïve CV.This was the main coverage result across the real-data examples.
  • Coverage results: Data splitting had poor coverage with small samples, but was significantly better with 100 samples than with n = 50 samples.The passage attributes the poor performance to the small sample size.

7 Discussion

The discussion concludes that common prediction-error estimates target average error across hypothetical training sets, while nested cross-validation provides more reliable inference than naïve cross-validation intervals. Nested cross-validation is computationally costly, and standard intervals can substantially undercover, especially when n/p is smaller or regularization is limited.

  • Point estimation: Common prediction-error estimates should be interpreted as average prediction error across other hypothetical data sets from the same distribution.This formal result applies to cross-validation, bootstrap, data splitting, and covariance penalties for unregularized ordinary least squares.
  • Inference: Nested cross-validation has consistently superior coverage to naïve cross-validation confidence intervals for prediction error.It estimates the mean squared error of the cross-validation point estimate.
  • Inference: Nested cross-validation uses about 1000 times more model fits per example than standard cross-validation because of repeated splitting.In the logistic regression example, nested cross-validation takes about 10 seconds on a personal computer.
  • Limitations: In experiments, standard cross-validation’s miscoverage rate was about 50% larger than the nominal rate even for a linear model with n/p = 10.The violation decreases as n increases, and standard intervals are expected to perform better with larger n/p and more regularization.
  • Future directions: Future directions include adapting nested cross-validation to dependent data and using leave-out strategies to fill in data for downstream applications.Examples include pre-validation and cross-fitting.

A Results for bootstrap estimates of prediction error · B Data splitting · B.1 Data splitting without refitting

For OLS, bootstrap prediction-error estimators are linearly invariant and estimate Err or ErrX rather than ErrXY. Data splitting without refitting supports valid inference for the subset-trained model but is less precise because it uses only held-out observations.

  • A Results for bootstrap estimates of prediction error: The bootstrap results analyze the .632 and out-of-bag (OOB) prediction-error estimators.Both estimators are considered with OLS as the underlying model-fitting routine.
  • A Results for bootstrap estimates of prediction error: Under OLS, the bootstrap estimators are linearly invariant.
  • A Results for bootstrap estimates of prediction error: Bootstrap should be viewed as estimating Err or ErrX rather than ErrXY.
  • A Results for bootstrap estimates of prediction error: Nested cross-validation is also expected to be linearly invariant, suggesting this property extends beyond the explicitly analyzed resampling estimators.
  • B Data splitting: Data splitting without refitting partitions observations into disjoint training and held-out sets, fits on the training set, and evaluates losses on held-out observations.
  • B.1 Data splitting without refitting: This approach accurately estimates prediction error and provides valid inference, but only for the model trained on I(train).
  • B.1 Data splitting without refitting: The resulting split estimate is unbiased for the prediction error of the model trained on the training subset.
  • B.1 Data splitting without refitting: Because the estimates rely only on I(out), they have reduced precision and may yield much wider prediction-error confidence intervals.

B.2 Data splitting with refitting · C Bias estimation

Data splitting with refitting deploys a model refit on the full dataset, and the paper’s cross-validation results extend to this setting. However, its standard-error estimate is asymptotically too small, while nested cross-validation enables bias correction for differing training-sample sizes.

  • B.2 Data splitting with refitting: Data splitting with refitting evaluates a model on a training split, then refits and deploys the model using the full data.The full-data fit is viewed as superior to the model trained only on the subset.
  • B.2 Data splitting with refitting: Refitting makes the usual data-splitting standard-error estimate asymptotically too small, causing confidence intervals to have insufficient coverage.This remains true even without the component attributable to the different sample sizes used for fitting.
  • B.2 Data splitting with refitting: In the proportional asymptotic limit, all terms in the relevant bound are order 1/n except the final term, which is constant when the test set is a constant fraction of n.The constant-order term reflects the sample-size difference between split and full-data fits.
  • B.2 Data splitting with refitting: Choosing the test-set fraction to converge to 0 can reduce the constant-order term, but then data splitting fails to achieve a 1/√n precision rate.Thus, improving this aspect of the bound creates a loss in precision.
  • B.2 Data splitting with refitting: Data-splitting intervals do not approach nominal coverage as n and p grow, whereas without-replacement intervals are closer because they avoid cross-fold data-reuse correlations.Naïve cross-validation exhibits a similar miscoverage problem.
  • C Bias estimation: Nested cross-validation is unbiased for prediction error at sample size n(K −2)/K, but typically overestimates the full-sample prediction error slightly.Running both standard and nested cross-validation estimates the discrepancy between their training-sample sizes.
  • C Bias estimation: Assuming prediction error scales as a + b/n, the bias adjustment combines differences from n(K −2)/K to n(K −1)/K and from n(K −1)/K to n.Combined with the preceding MSE estimate, this produces the confidence intervals in (10).

D Proofs

The proofs establish that linearly invariant OLS prediction-error estimators depend only on residuals, making cross-validation unchanged under suitable response shifts. They also decompose prediction-error variance into contributions from Y | X and X, with the latter becoming negligible asymptotically.

  • Residual-based invariance: Linearly invariant prediction-error estimators fitted by OLS are functions of the residual vector r = Y − Xθ̂.This follows from applying the invariance property after subtracting the fitted values.
  • Cross-validation invariance: Cross-validation prediction-error estimates remain identical when the responses are shifted in the proof’s specified way.The argument uses identical cross-validation residuals and the fact that the estimate is their mean squared value.
  • Variance decomposition: The total variance of ErrXY decomposes as E[var(ErrXY | X)] + var(E[ErrXY | X]), representing randomness from Y | X and X.The proof explicitly labels the two terms as variance due to Y | X and variance due to X.
  • Asymptotic variance: var(ErrX) / var(ErrXY) → 0 as n → ∞, so feature randomness contributes a vanishing share of total prediction-error variance.This is the first claim established in the proof of Corollary 2.
  • Asymptotic variance: The analogous ratio var(ErrX) / var(g(ErrX, U)) also tends to 0 as n → ∞ for invariant estimators represented as g(ErrX, U).Here U is an independent uniform random variable and d Err is treated as a random function of ErrX.

E Additional technical results … F.5 CV in the proportional region

Additional analyses show that CV’s variance, fold count, and target error affect its inflation and coverage, while nested CV addresses interval-width problems at additional computational cost. In proportional regimes, CV intervals remain too narrow and substantially miscalibrated even when centered correctly.

  • E Additional technical results: In the proportional asymptotic limit, all terms on both sides of (16) are order 1/n except one O(1/n2) term on the right.
  • F.1 The bias of CV in the proportional asymptotic regime.: For considered sample sizes, CV variance is much larger than squared bias, but constant bias would dominate for larger n.Increasing the number of folds is suggested as one way to address the eventual bias issue.
  • F.2 Compute times: Table F.5 reports approximate computation times for one run of CV and NCV across the experimental settings.
  • F.3 Additional details on experiments from Section 5: The additional-results section reports further experiments from Section 5.
  • F.4 Number of folds: With p = 20 and n ranging from 50 to 400, fold count has minimal impact on CV inflation, while more folds moderately improve coverage for small n.Even at n/p = 20, appreciable CV inflation remains.
  • F.5 CV in the proportional region: CV estimates Err with higher accuracy than ErrXY by a constant fraction as n, p →∞.ErrXY and d Err (CV) are essentially uncorrelated.
  • F.5 CV in the proportional region: Figures F.2–F.4 compare nested and naïve CV interval sizes or widths across low-dimensional logistic regression, experiment, and high-dimensional sparse regression settings.
  • F.5 CV in the proportional region: CV coverage is far from nominal even as n and p grow, despite oracle debiasing that centers intervals around the correct value.The intervals are too narrow, with higher-than-nominal miscoverage in both tails.

F.6 Coverage of data splitting in proportional regime … G Variance stabilizing transformation for 0-1 loss

The supplementary experiments show that data-splitting intervals can miss nominal coverage, nested cross-validation requires many repeated splits for stable standard-error estimates, and alternative standard-error and variance-stabilization methods are investigated. The analyses also examine bootstrap confidence intervals, regularization, and transformed intervals for 0-1 loss.

  • F.7 .632 bootstrap empirical influence function CIs: The .632 bootstrap analysis uses empirical influence functions to estimate standard errors for out-of-bag and .632 prediction-error estimates.The cited procedure uses Efron and Tibshirani’s point estimate from (24) and standard-error estimate from (36).
  • F.8 Number of Repeated Splits: About 200 random splits of nested cross-validation were needed to obtain stable standard-error estimates in the reported logistic-regression example.The experiment tracks inflation relative to the naïve cross-validation estimate as repetitions increase.
  • F.9 The Austern and Zhou estimate of Standard Error: The Austern–Zhou estimator is evaluated because it is asymptotically correct under certain stability conditions through a triangular-array central limit theorem.The study investigates this estimator in the ordinary-least-squares setup and compares confidence-interval sizes based on its standard-error estimate.
  • F.10 The effect of regularization: Regularization experiments examine how ridge-regression strength changes the correlation between d Err and ErrXY, which is nearly zero without regularization.The ridge analyses vary regularization strength and report results in Figure F.12.
  • G Variance stabilizing transformation for 0-1 loss: For classification with 0-1 loss, a variance-stabilizing transformation can produce improved confidence intervals by transforming empirical miscoverage and then inverting the transformation.With nested cross-validation, transformed intervals are inflated using the ratio between naïve and nested cross-validation estimates.

H A low-dimensional asymptotic analysis

In the fixed-p, n→∞ regime, ErrX is close to Err, while differences among estimands are smaller than the CV estimator’s variance at sufficiently large n. Consequently, CV is expected to estimate Err more accurately than ErrXY but does not track ErrXY asymptotically.

  • Fixed-p asymptotics: With p fixed and n→∞, ErrX is close to Err, so CV is expected to have better accuracy for Err than for ErrXY.The differences among the various estimands are of order higher than 1/√n.
  • Fixed-p asymptotics: Theorem 4 analyzes the homoskedastic Gaussian linear model with squared-error loss and Gaussian full-rank feature covariance as n→∞ with p fixed.The result can be extended beyond Gaussian features, but that extension is not pursued here.
  • Fixed-p asymptotics: cor(ErrXY, d Err) → 0 as n →∞ for any linearly invariant estimator d Err.The result implies that CV is not tracking ErrXY in this asymptotic regime.

I Connection with results about the k-fold test error

The k-fold test error is the average accuracy of the k submodels fit during cross-validation. In an OLS experiment, cross-validation estimates Err better than Errk-fold, while its point estimate correlates 8.5% with Errk-fold and less than 1% with ErrXY.

  • Definition: The k-fold test error is the average accuracy of the k submodels fit during cross-validation.It is defined with expectation over a fresh test point while holding the training data fixed.
  • Empirical comparison: In the OLS experiment, cross-validation is a better estimate of Err than of Errk-fold and a worse estimate of Errk-fold than of ErrXY.The comparison is reported from a numerical experiment revisiting the OLS setting of Figure 3.
  • Empirical comparison: Less than 1% is the reported correlation between the CV point estimate and ErrXY.Figure I.15 displays the correlations of the CV point estimate with ErrXY and Errk-fold.
  • Empirical comparison: 8.5% is the correlation between the CV point estimate and Errk-fold in this setting.The paper interprets this as the CV point estimate tracking variation in Errk-fold in a non-negligible way.
Loading 2104.00673v4…