Cross-Validation for Model Selection Under Misspecification

What Does “Best Model” Mean Under Misspecification?

A candidate model can be useful without being a correct description of the data-generating process. If every candidate is misspecified, model selection cannot discover a correct model among them. It can still choose the candidate with the smallest prediction risk, which is often the practical objective.

The word best therefore needs care. It may mean that the selected procedure has risk close to the smallest available risk, or it may mean that the procedure selects one particular model with probability approaching one. These are different properties. The first concerns prediction performance; the second concerns identifying a model label.

For example, under squared-error prediction, the target is often the conditional mean \(E[Y\mid X]\). If that function is not in any candidate class, each class can still have a best approximation in mean squared error. Cross-validation compares the predictive risks of procedures trained from the data; it does not test whether a candidate model is literally true.

To state selection claims precisely, suppose there are a fixed, finite number \(J\) of candidate procedures. With a sample of size \(n\), let \(\hat R_{j,n}\) be the cross-validation estimate for candidate \(j\), and let \(R_{j,n}\) be its prediction risk when trained at the relevant full-sample size. The selected index is \(\hat j_n\in\operatorname*{arg\,min}_{1\leq j\leq J}\hat R_{j,n}\), with any ties resolved by a fixed rule. The best available risk is \(\min_j R_{j,n}\).

Why Accuracy of Risk Estimates Is Enough for Risk Consistency

The key condition for a finite candidate set is that cross-validation estimates all candidate risks accurately enough at once. This is a condition on the maximum estimation error, not just on the error for a candidate fixed in advance. Write \(\delta_n=\max_{1\leq j\leq J}|\hat R_{j,n}-R_{j,n}|\).

Proof. Let \(j_n^*\) be any index minimizing \(R_{j,n}\). By the definition of \(\delta_n\), and because \(\hat j_n\) minimizes the cross-validation estimates,

Subtracting the minimum risk gives a nonnegative excess risk bounded above by \(2\delta_n\). Since \(\delta_n\xrightarrow{p}0\), the excess risk converges in probability to zero. \(\square\)

This argument does not require any candidate to be correctly specified. It only requires the risk estimates to approximate the risks that matter for the comparison. In a fixed-\(K\) cross-validation design, the estimates evaluate fits trained on fold-specific samples, while deployment may use a fit trained on all \(n\) observations. Thus a condition used in practice is that the fold-trained and full-sample procedures have risks that become asymptotically equivalent. If that difference does not vanish, cross-validation may accurately rank the fold-trained procedures but target a different comparison from the full-sample one.

When Does Risk Consistency Become Exact Selection?

Risk consistency alone does not guarantee that the selected model label converges to one particular index. Exact selection requires a unique best candidate separated from the others by a positive risk gap. A difference that shrinks toward zero may be too small for the validation estimates to distinguish reliably.

Proof. Since the risks converge and there are finitely many candidates, for all sufficiently large \(n\), every \(j\ne j^*\) satisfies \(R_{j,n}-R_{j^*,n}\geq 2\Delta/3\). On the event \(\delta_n<\Delta/3\), for every such \(j\),

Thus \(j^*\) is the unique minimizer of the estimated risks on that event. The probability of the event tends to one because \(\delta_n\xrightarrow{p}0\), proving the claim. \(\square\)

The gap condition explains why exact selection is stronger: it asks the estimated risk differences to preserve the identity of the winner, not merely to yield small excess risk. If limiting risks tie, there is no unique index to recover. A fixed tie-breaking rule can select one tied model consistently, but that result reflects the rule, not evidence that the tied model has better predictive risk.

A Useful Sufficient Condition for Cross-Validation

The uniform risk-accuracy condition above is a direct route to the selection conclusions. One transparent sufficient setting is when each candidate procedure approaches a fixed limiting predictor, and the loss is not too sensitive to small prediction changes. Here is a precise version for fixed \(K\)-fold cross-validation.

Justification. For candidate \(j\), compare its cross-validation estimate with the full-sample average \(n^{-1}\sum_{i=1}^n\ell(Y_i,f_j(X_i))\). Their absolute difference is bounded by the assumed average fold-loss discrepancy, which converges to zero in probability. Because the observations are identically distributed and the fixed-predictor loss is bounded, the law of large numbers gives \(n^{-1}\sum_i\ell(Y_i,f_j(X_i))\xrightarrow{p}R_j\). The full-sample risk also converges to \(R_j\) by assumption, so \(|\hat R_{j,n}-R_{j,n}|\xrightarrow{p}0\) for each \(j\). There are only finitely many candidates, hence the maximum of these errors converges to zero in probability. The preceding theorems then give risk consistency, and exact selection as well if the limiting risk minimizer is unique and separated. \(\square\)

This is a sufficient condition, not a claim that every cross-validation scheme or every learner satisfies it. Unstable fitting procedures, changing candidate sets, or a mismatch between fold-training and full-training risks may require different arguments. For the finite, fixed candidate setting, the essential points are that the estimates compare the intended risks and that their errors vanish uniformly across candidates.

Common Mistake and Practical Interpretation

A common mistake is to interpret a risk-consistent selection as proof that cross-validation has identified the true model. That conclusion does not follow. Risk consistency says the selected candidate’s risk approaches the smallest risk available in the candidate set. When all candidates are misspecified, that smallest risk is still an approximation risk, not the risk of a correctly specified model.

A second mistake is to infer exact selection from accurate risk estimates without checking for a gap. If two candidate risks tie, or their difference becomes negligible relative to estimation error, model labels can remain uncertain even while the selected risk is near-optimal. In reporting results, distinguish the claim about predictive risk from the stronger claim about recovering a particular model.