PaperlayerView exact revision on arXiv

Source-linked AI summary

Cross-Validation with Confidence

Jing Lei

arXiv:1703.07904v2stat.MEstat.ML

TL;DR

Traditional cross-validation can overfit because it ignores uncertainty in the testing sample. CVC accounts for that uncertainty by testing candidate models and returning a confidence set; the set has a probability guarantee for containing the best model, and its smallest model can achieve consistent variable selection in classical linear regression.

  • Problem

    Traditional cross-validation can select overfitting models because it does not account for uncertainty in the testing sample.

    Source: §1 · pp. 1–2

  • Method

    CVC tests whether each candidate has the smallest predictive risk among fitted candidates and returns the models whose null hypotheses are not rejected.

    Source: §1 · p. 2

  • Results

    At test level α, CVC's confidence set contains the best fitted model with probability at least 1 − α and, with high probability, contains only highly competitive models.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The smallest model in CVC's confidence set can achieve consistent variable selection with a conventional split ratio in classical linear regression.

    Source: §1 · p. 2, §4.2 · p. 17

    High-dimensional regression selection and theory for binary responses with heteroskedastic noise are identified as extensions for future work.

    Source: §6 · p. 25

Abstract

from arXiv · show

Cross-validation is one of the most popular model selection methods in statistics and machine learning. Despite its wide applicability, traditional cross validation methods tend to select overfitting models, due to the ignorance of the uncertainty in the testing sample. We develop a new, statistically principled inference tool based on cross-validation that takes into account the uncertainty in the testing sample. This new method outputs a set of highly competitive candidate models containing the best one with guaranteed probability. As a consequence, our method can achieve consistent variable selection in a classical linear regression setting, for which existing cross-validation methods require unconventional split ratios. When used for regularizing tuning parameter selection, the method can provide a further trade-off between prediction accuracy and model interpretability. We demonstrate the performance of the proposed method in several simulated and real data examples.

1 Introduction

Conventional cross-validation can overfit because it does not account for testing-sample uncertainty, while avoiding that problem through very small training splits can impair model fitting. The paper introduces CVC, which tests candidate models and returns a confidence set with guarantees for model selection and tuning-parameter selection.

1 Introduction

  • CVC tests whether each candidate has the smallest predictive risk among fitted candidates and retains models whose null hypotheses are not rejected.It calculates p-values by comparing cross-validated residuals across candidate models.Source: §1 · p. 2
  • Testing-sample uncertainty can make a model appear better because of random test data rather than a genuinely superior fit, contributing to cross-validation's tendency to overfit.Conventional split ratios remain popular in part because very small training splits reduce training data and can make model fitting less accurate.Source: §1 · pp. 1–2
  • The smallest model in CVC's confidence set can achieve consistent variable selection with a conventional split ratio, unlike traditional cross-validation in this setting.The paper focuses on a fixed candidate set for model selection; its consistency analysis requires assumptions including sufficiently large nonzero coefficients and weakly correlated covariates.Source: §1 · pp. 1–3
  • With each test conducted at level α, CVC's confidence set contains the best fitted model with probability at least 1 − α and, with high probability, includes only highly competitive models.The testing procedure addresses the high correlation and differing scales of cross-validated residuals using high-dimensional Gaussian comparison results.Source: §1 · pp. 2–3
  • Earlier confidence-set methods were limited to fixed candidate sets and always included the saturated model, while heuristic cross-validation corrections still returned a single model.The cited alternatives include hierarchical testing, the fence method, bias correction, and stability-based criteria.Source: §1 · p. 3
  • For tuning-parameter selection, CVC offers a set of competitive candidates from which users can choose a more parsimonious model or one containing a desired variable.The authors contrast this flexibility with risk-consistency results that select a single candidate.Source: §1 · pp. 3–4

2 Review of cross-validation

Cross-validation estimates predictive risk using held-out data, and V-fold validation averages results across repeated fits to reduce estimation uncertainty. Its validation estimates remain uncertain, however, and that uncertainty can make an inferior model appear better.

2.1 Validation by sample splitting.

  • Sample-splitting validation fits each candidate on training data and selects the model with the smallest empirical average loss on held-out test data.Conditional on the split and training data, the law of large numbers makes this validation risk close to predictive risk.Source: §2.1 · p. 5
  • Validation uncertainty comes from using test data to approximate predictive risk, separately from estimation uncertainty in fitting models on finite training data.Both sources can affect the choice of the best candidate.Source: §2.1 · p. 5

2.2 Reducing the estimation uncertainty: V-fold cross-validation.

  • V-fold cross-validation averages predictive-risk estimates across repeated training subsets, often reducing variance relative to a single split by capturing fitting-sample variability.Common defaults are 10-fold or 5-fold validation; leave-one-out is the V = n case.Source: §2.2 · p. 6

2.3 Validation uncertainty.

  • In the two-model example, random test-sample noise can make the larger model's validation error look smaller even though the zero model has lower predictive risk.The probability of this overfitting event increases as the test sample shrinks and remains bounded away from zero for V-fold validation across V in this example.Source: §2.3 · p. 7
  • A vanishing training-to-total sample ratio can address validation uncertainty for model selection, but it reduces fitting data and may mis-tune parameters later applied to the full sample.The concern arises when the optimal tuning parameter depends on sample size, as in bandwidth selection or Lasso tuning.Source: §2.3 · p. 7

3 Cross-validation with confidence

Cross-validation with confidence (CVC) tests whether each fitted candidate has the best predictive risk, accounting for validation uncertainty without sacrificing training sample size. It returns a confidence set of candidates whose null hypotheses are not rejected.

3 Cross-validation with confidence

  • CVC extends the sample-split testing procedure to V-fold cross-validation while accounting for testing-sample uncertainty without reducing training sample size.The paper presents the extension from sample-split validation to V-fold validation.Source: §3 · p. 7, §3.1 · p. 8

3.1 Sample-split validation with hypothesis testing

  • CVC retains fitted models whose null hypothesis of best predictive risk is not rejected at the chosen type I error level.For each candidate, the null says no other fitted model has strictly lower predictive risk.Source: §3.1 · p. 8

3.1.1 Calculating the p-values.

  • For sample-split CVC, studentized Gaussian multiplier bootstrap p-values address many correlated comparisons with widely varying scales.The testing problem can be high-dimensional, and underfitting can make loss-difference variance much larger than for similar well-fitting models.Source: §3.1.1 · pp. 8–9

3.2 V-fold cross-validation with confidence.

  • V-fold CVC is more complicated because fitted models and validation losses are dependent across folds.The fold-specific fitted models cannot be conditioned on as independent of the data points used for validation.Source: §3.2 · p. 9, §3.2.1 · p. 10

3.2.1 A proxy group effect model.

  • The proxy group effect approach treats cross-validated losses as approximately independent across observations, with observations within each fold sharing a conditional distribution.The losses within each fold are treated as iid from that fold’s conditional distribution, and the p-value calculation removes group mean effects.Source: §3.2.1 · p. 10, §3.2.2 · p. 11

3.2.2 Approximate p-value for V-fold CVC

  • Empirically, the standard cross-validation choice almost always has the largest CVC p-value among candidate models.The p-value construction also guarantees that the CVC confidence set is non-empty.Source: §3.2.2 · p. 12

3.3 Implementation details

  • The additional CVC computation is O(nM^2B), independent of problem dimensionality; inequality screening can avoid bootstrap comparisons for obviously inferior candidates.The reported total runtime is usually under five seconds for n in the hundreds, M = 50, and B = 200.Source: §3.3 · pp. 12–13

4 Theoretical Properties

The theory studies confidence sets for risk minimization and their use in model selection, culminating in consistency results for classical linear models under stated assumptions.

4.1.1 Sample-split validation analysis

  • Sample-split theory assumes sub-exponential tails for standardized loss differences; the condition can hold for linear squared loss with sub-Gaussian covariates and noise.Source: §4.1.1 · pp. 14–15
  • For sample-split validation, the best fitted estimate enters Ass with probability at least 1−α+o(1) under the theorem assumptions.Source: §4.1.1 · pp. 14–15

4.1.2 Analysis of the group-effect proxy model

  • The group-effect proxy gives partial theoretical justification for Acv, while V-fold CVC empirically has much better power to eliminate suboptimal estimates.Source: §4.1.2 · pp. 15–16

4.2 Model selection consistency in classical linear models.

  • Classical-linear-model consistency assumes B1–B3, including finite sixth moments and a leverage-rate condition stronger than prior cross-validation assumptions.Source: §4.2 · p. 17
  • Under B1–B3 and α_n→0 with α_n>n^-1, both sample-split and genuine CVC selectors recover m* with probability tending to one.Source: §4.2 · p. 17

5 Numerical experiments

The experiments evaluate CVC for subset selection, Lasso tuning, and diabetes prediction. They report consistent subset selection as sample size grows and competitive prediction accuracy with more parsimonious fits.

5.1 Simulation 1: Subset selection consistency in linear models.

  • By n = 320, CVC achieves a perfect correct-selection rate, while standard cross-validation remains below 1 as sample size increases.This pattern is reported across the Gaussian- and t3-noise simulations; CVC confidence sets are generally smaller than F-test sets at moderately large n except under high t3 noise.Source: §5.1 · p. 18, Figure 1 · p. 19, Figure 2 · p. 20

5.2 Simulation 2: Tuning the Lasso for risk minimization

  • CVC offers prediction accuracy competitive with standard cross-validation while using fewer predictors, and its confidence set covers the best tuning parameter almost exactly 0.95 of the time.The median size of Acv is between 4 and 5 across settings.Source: Figure 3 · p. 22, §5.2 · p. 22

5.3 The diabetes data example.

  • On diabetes data, five CVC candidate λ values include one with test error very close to standard cross-validation and a more parsimonious fit.In repeated hold-out comparisons, the most parsimonious CVC model also has very close test error to standard cross-validation with many fewer predictors; 1se is competitive with slightly larger predictive risk.Source: Figure 4 · p. 23, §5.3 · pp. 23–24, Figure 5 · p. 24

6 Discussion

The discussion identifies extensions of CVC that remain to be studied, including broader model classes and learning settings.

6 Discussion

  • Extending CVC to high-dimensional regression model selection is proposed as future work.The paper's consistency analysis for sparse linear regression considered independent noise; binary responses would require theory covering heteroskedastic noise.Source: §6 · p. 25
  • The CVC framework could also be extended to unsupervised clustering, low-rank matrix approximation, and network community detection.For K-means or model-based clustering, the passage suggests squared distance to the closest cluster center as a test-point loss.Source: §6 · p. 25
  • The authors identify broader contexts for CVC as avenues for future investigation rather than established results.These include heteroskedastic binary-response settings and the other proposed learning problems.Source: §6 · p. 25

A.1 Proof of Section 4.1

The proof develops the calibration argument for CVC's test statistic using a Gaussian comparison for maxima of studentized sample means. It also states the resulting null calibration.

A.1 Proof of Section 4.1

  • The proof's main task is to approximate the maximum studentized sample mean by the maximum of a Gaussian vector with the same covariance structure.The reference distribution uses the sample correlation matrix of the relevant test-sample quantities.Source: §A.1 · p. 25
  • For the event E defined by max_j |μ̂_j − μ_j|/σ_j ≤ c2An, under the theorem’s condition, P(E) is at least 1 − 3N^-1.Source: §A.1 · p. 27
  • When all means are zero, the proof gives P(ˆp ≤ α) = α + o(1).The argument treats the bootstrap p-value as its limiting value as the bootstrap sample size B tends to infinity.Source: §A.1 · pp. 27–28

A.2 Proofs for Section 4.2

These proofs support the model-selection consistency argument by controlling rejection of candidate models and extending the argument across folds. They also invoke consistency of least-squares estimates.

A.2 Proofs for Section 4.2

  • The proof invokes uniform consistency of the least-squares estimates across candidate models: sup_m ∥ˆβ_m − β_m∥2 = o_Ptr(1).This statement is made for the training-data randomness.Source: §A.2 · p. 29
  • For a candidate model missing at least one true variable, the rejection probability approaches 1 as sample size increases.The proof first states that the probability such a model belongs to An tends to zero.Source: §A.2 · pp. 29–30
  • The proof extends the argument to V-fold cross-validation by applying it fold by fold and using a union bound over folds.For each fold, the proof treats that fold as test data and the remaining folds as training data.Source: §A.2 · p. 32
Loading 1703.07904v2…