# When are Shao's results on leave-one-out cross-validation applicable?

In his paper Linear Model Selection by Cross-Validation, Jun Shao shows that for the problem of variable selection in multivariate linear regression, the method of leave-one-out cross validation (LOOCV) is 'asymptotically inconsistent'. In plain English, it tends to select models with too many variables. In a simulation study, Shao shows that even for as few as 40 observations, LOOCV can underperform other cross-validation techniques.

This paper is somewhat controversial, and somewhat ignored (10 years after its publication, my chemometrics colleagues had never heard of it and were happily using LOOCV for variable selection...). There is also a belief (I am guilty of this), that it's results extend somewhat beyond the original limited scope.

The question, then: how far do these results extend? Are they applicable to the following problems?

1. Variable selection for logistic regression/GLM?
2. Variable selection for Fisher LDA classification?
3. Variable selection using SVM with finite (or infinite) kernel space?
4. Comparison of models in classification, say SVM using different kernels?
5. Comparison of models in linear regression, say comparing MLR to Ridge Regression?
6. etc.
-
 There must be something in chemometrics books; the only man I know that uses LOO is also doing it. – mbq♦ Sep 3 '10 at 17:51

You need to specify the purpose of the model before you can say whether Shao's results are applicable. For example, if the purpose is prediction, then LOOCV makes good sense and the inconsistency of variable selection is not a problem. On the other hand, if the purpose is to identify the important variables and explain how they affect the response variable, then Shao's results are obviously important and LOOCV is not appropriate.

The AIC is asymptotically LOOCV and BIC is asymptotically equivalent to a leave-$v$-out CV where $v=n[1-1/(\log(n)-1)]$ --- the BIC result for linear models only. So the BIC gives consistent model selection. Therefore a short-hand summary of Shao's result is that AIC is useful for prediction but BIC is useful for explanation.

-
I believe Shao showed that k-fold CV is inconsistent if $k$ is fixed while $n$ grows. – shabbychef Sep 4 '10 at 5:18
The BIC has k growing with n. – Rob Hyndman Sep 4 '10 at 5:56
I will just silently remind that *IC <--> *CV correspondence from Shao paper works only for linear models, and BIC is equivalent only to k-fold CV with certain k. – mbq Sep 4 '10 at 17:26
Actually, I believe Shao shows that CV is inconsistent unless $n_v/n \to 1$ as $n \to \inf$, where $n_v$ is the number of samples in the test set. Thus $k$-fold CV is always inconsistent for variable selection. Have I misunderstood? By $k$-fold CV I mean dividing the sample into $k$ groups and training on $k-1$ of them, and testing on 1 of them, then repeating $k$ times. Then $n_v/n = 1/k$ for $k$-fold CV, which never approaches 1. – shabbychef Sep 7 '10 at 16:46
I probably shouldn't have said k-fold. The BIC is equivalent to leave-v-out CV where v=n[1-1/(log(n)-1)] and so it satisfies the Shao consistency criterion. I've updated my answer accordingly. – Rob Hyndman Sep 8 '10 at 11:23

I would say: everywhere, but I haven't seen a strict proof of it. The intuition behind is such that when doing CV one must hold a balance between train large enough to build sensible model and test large enough so it would be a sensible benchmark.
When dealing with thousands of pretty homogeneous objects, picking one is connected with risk that it is pretty similar to other object that was left in the set -- and then the results would be too optimistic.
On the other hand, in case of few objects there will be no vital difference between LOO and k-fold; $10/10$ is just $1$ and we can't do anything with it.

-
Beyond proofs, I'm wondering if there have been simulation studies of any of the five cases I list, for example. – shabbychef Sep 8 '10 at 17:27
Wanna make some? – mbq Sep 8 '10 at 17:58
I do; I'm going to have to learn a lot more R, though, to share the results here, though. – shabbychef Sep 9 '10 at 21:16

This paper is somewhat controversial, and somewhat ignored

Not really, it's well regarded where the theory of model selection is concerned, though it's certainly misinterpreted. The real issue is how relevant it is to the practice of modeling in the wild. Suppose you perform the simulations for the cases you propose to investigate and determine that LOOCV is indeed inconsistent. The only reason you'd get that is because you already knew the "true" model and could hence determine that the probability of recovering the "true" model does not converge to 1. For modeling in the wild, how often is this true (that the phenomena are described by linear models and the "true" model is a subset of those in consideration)?

Shao's paper is certainly interesting for advancing the theoretical framework. It even provides some clarity: if the "true" model is indeed under consideration, then we have the consistency results to hang our hats on. But I'm not sure how interesting actual simulations for the cases you describe would be. This is largely why most books like EOSL don't focus as much on Shao's result, but instead on prediction/generalization error as a criterion for model selection.

EDIT: The very short answer to your question is: Shao's results are applicable when you're performing least squares estimation, quadratic loss function. Not any wider. (I think there was an interesting paper by Yang (2005?) which investigated whether you could have consistency and efficiency, with a negative answer.)

-
 I don't think it is relevant whether I know the true model in the wild. If there is a 'true' model, I would prefer a method which is more likely to find it. – shabbychef Sep 12 '10 at 3:49 @shabbychef: I don't disagree. But note: "If there is a 'true' model" and it's under consideration .. how would you know this a priori? – ars Sep 12 '10 at 4:08 Note also that my second paragraph actually makes the point in your comment. This is a nice property, but it's not all clear how applicable it is in the wild; even though it's comforting in some sense, it may be misguided. – ars Sep 12 '10 at 4:13 @ars - note that the "linearity" of the 'true' model is not the only way to recover the 'true' model from a linear model. If the non-linear component of the 'true' model can be well modelled by the noise term (e.g. non-linear effects tend to cancel each other out) then we could reasonably call the linear model 'true' I think. This is similar to assuming the remainder in a linear taylor series is negligible. – probabilityislogic Dec 13 '11 at 15:03 So you can re-state the results as: if there exists a reasonable linear approximation to reality, then BIC / leave-$v$-out will consistently find that approximation. AIC / leave-one-out will not consistently find it. – probabilityislogic Dec 13 '11 at 15:04