Empirical justification for the one standard error rule when using cross-validation

Question

Are there any empirical studies justifying the use of the one standard error rule in favour of parsimony? Obviously it depends on the data-generation process of the data, but anything which analyses a large corpus of datasets would be a very interesting read.

---

The "one standard error rule" is applied when selecting models through cross-validation (or more generally through any randomization-based procedure).

Assume we consider models $M_\tau$ indexed by a complexity parameter $\tau\in\mathbb{R}$, such that $M_\tau$ is "more complex" than $M_{\tau'}$ exactly when $\tau>\tau'$. Assume further that we assess the quality of a model $M$ by some randomization process, e.g., cross-validation. Let $q(M)$ denote the "average" quality of $M$, e.g., the mean out-of-bag prediction error across many cross-validation runs. We wish to minimize this quantity.

However, since our quality measure comes from some randomization procedure, it comes with variability. Let $s(M)$ denote the standard error of the quality of $M$ across the randomization runs, e.g., the standard deviation of the out-of-bag prediction error of $M$ over cross-validation runs.

Then we choose the model $M_\tau$, where $\tau$ is the smallest $\tau$ such that

$$q(M_\tau)\leq q(M_{\tau'})+s(M_{\tau'}),$$

where $\tau'$ indexes the (on average) best model, $q(M_{\tau'})=\min_\tau q(M_\tau)$.

That is, we choose the simplest model (the smallest $\tau$) which is no more than one standard error worse than the best model $M_{\tau'}$ in the randomization procedure.

I have found this "one standard error rule" referred to in the following places, but never with any explicit justification:

• Page 80 in Classification and Regression Trees by Breiman, Friedman, Stone & Olshen (1984)
• Page 415 in Estimating the Number of Clusters in a Data Set via the Gap Statistic by Tibshirani, Walther & Hastie (JRSS B, 2001) (referencing Breiman et al.)
• Pages 61 and 244 in Elements of Statistical Learning by Hastie, Tibshirani & Friedman (2009)
• Page 13 in Statistical Learning with Sparsity by Hastie, Tibshirani & Wainwright (2015)

Answer 1

For an empirical justification, have a look at page 12 on these Tibshirani data-mining course notes, which shows the CV error as a function of lambda for a particular modeling problem. The suggestion seems to be that, below a certain value, all lambdas give about the same CV error. This makes sense because, unlike ridge regression, LASSO is not typically used only, or even primarily, to improve prediction accuracy. Its main selling point is that it makes models simpler and more interpretable by eliminating the least relevant/valuable predictors.

Now, to understand the one standard error rule, let's think about the family of models we get from varying $\lambda$. Tibshirani's figure is telling us that we have a bunch of medium-to-high complexity models that are about the same in predictive accuracy, and a bunch of low-complexity models that are not good at prediction. What should we choose? Well, if we're using $L_1$, we're probably interested in a parsimonious model, so we'd probably prefer the simplest model that explains our data reasonably well (as Einstein supposedly said, "as simple as possible but no simpler"). So how about the lowest complexity model that is "about as good" as all those high complexity models? And what's a good way of measuring "about as good"? One standard error.

Answer 2

The following is not an empirical study, which is why I originally wanted to post it as a comment, not an answer - but it really turns out to be too long for a comment.

Cawley & Talbot (J of Machine Learning Research, 2010) draw attention to the difference between overfitting during the model selection phase and overfitting during the model fitting phase.

The second kind of overfitting is the one most people are familiar with: given a particular model, we don't want to overfit it, i.e., to fit it too closely to the particular idiosyncrasies of the single data set we typically have. (This is where shrinkage/regularization can help, by trading a small increase in bias against a large decrease in variance.)

However, Cawley & Talbot argue that we can overfit just as well during the model selection stage. After all, we still have typically only a single data set, and we are deciding between different models of varying complexity. Evaluating each candidate model in order to select one usually involves fitting that model, which can be done using regularization or not. But this evaluation in itself is again a random variable, because it depends on the specific data set we have. So our choice of an "optimal" model can in itself exhibit a bias, and will exhibit a variance, as depending on the specific data set from all data sets we could have drawn from the population.

Cawley & Talbot therefore argue that simply choosing the model that performs best in this evaluation may well be a selection rule with small bias - but it may exhibit large variance. That is, given different training datasets from the same data generating process (DGP), this rule may select very different models, which would then be fitted and used for predicting in new datasets that again follow the same DGP. In this light, restricting the variance of the model selection procedure but incurring a small bias towards simpler models may yield smaller out-of-sample errors.

Cawley & Talbot don't connect this explicitly to the one standard error rule, and their section on "regularizing model selection" is very short. However, the one standard error rule would perform exactly this regularization, and take the relationship between the variance in model selection and the variance of the out-of-bag cross-validation error into account.

For instance, below is Figure 2.3 from Statistical Learning with Sparsity by Hastie, Tibshirani & Wainwright (2015). Model selection variance is given by the convexity of the black line at its minimum. Here, the minimum is not very pronounced, and the line is rather weakly convex, so model selection is probably rather uncertain with a high variance. And the variance of the OOB CV error estimate is of course given by the multiple light blue lines indicating standard errors.

Answer 3

The number of variables selected by the Lasso estimator is decided by a penalty value $\lambda$. The larger is $\lambda$, the smaller is the set of selected variables. Let $\hat S(\lambda)$ be the set of selected variables using as penalty $\lambda$.

Let $\lambda^ \star$ be the penalty selected using the minimum of the cross validation function. It can be proved that $P(S_0 \subset \hat S(\lambda^\star))\rightarrow 1$. Where $S_0$ is the set of the variables that are really non 0. (The set of true variable is content strictly in the set estimated using as penalty the minimum of the cross-validation.)

This should be reported in Statistics for high dimensional data by Bühlmann and van de Geer.

The penalty value $\lambda$ is often chosen through cross-validation; this means that with high probability too many variables are selected. To reduce the number of selected variables the penalty is increased a little bit using the one standard error rule.