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

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:

• Although I know what you're referring to by "One Standard Error Rule", I strongly suspect that a lot of people won't, but would be interested in this question if they did. Maybe you could edit to add a couple of explanatory sentences? (Just a suggestion...) Dec 21 '13 at 0:41
• @jbowman: I just edited the question to explain the one standard error rule, bumping it since I'm also pretty interested in this... and the answer below does not really answer my questions. Anyone, please feel free to improve. Apr 9 '15 at 14:52
• Feb 6 '17 at 20:59
• It would make a nice topic for a paper. It seems like a sensible engineering heuristic, but not all SEHs work in practice, so a study over a large number of datasets would be interesting. I do wonder if there is a multiple hypothesis testing issue involved that may mean it isn't very well calibrated, but it I would have thought it would be better than doing nothing on datasets where this sort of over-tuning is likely to be a problem. The question is does it make performance much worse on datasets where it isn't an issue? Feb 11 '17 at 13:45

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, to paraphrase Einstein. 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.

• I don't get the logic of this answer. E.g.: "unlike ridge regression, LASSO is not a mechanism for improving prediction accuracy" - why? Why is L1 so different from L2? In the next sentence you describe what happens with L1 for low lambdas, but I think the same things happens with L2 for low lambdas. Feb 12 '17 at 22:48
• Note that this is a heuristic explanation and relies on some unstated assumptions, like all predictors are informative. If you have a ton of noise predictors and a few informative ones, there might indeed be a value of lambda which clearly and markedly optimizes the CV metric: the one that corresponds to selecting the subset of informative predictors. As lambda decreases below that value you're just letting noise in and hurting the model.
– Paul
Feb 13 '17 at 0:25
• I think the argument works equally well for ridge and lasso, if you use a broad definition of parsimony in which more regularization -> simpler model. However, it's easier to motivate for L1 than for L2 due to the different types of problems and datasets they are used on. People who use L1 are more interested in having a simple model, and they are more likely to encounter the kind of CV error curve exhibited by Tibshirani.
– Paul
Mar 27 '17 at 20:19
• From the classic ESL text, p. 224: "Often a “one-standard error” rule is used with cross-validation, in which we choose the most parsimonious model whose error is no more than one standard error above the error of the best model." The example given is subset regression and a knee-shaped curve vs. number of predictors is shown. The curve is flat above the correct # of predictors, which is again consistent with the explanation I've given above. No rigorous or mathematical justification is mentioned.
– Paul
Mar 28 '17 at 17:37
• So I think the main issue here is that the minimum is poorly determined, but the most-regularized model within one sigma of the minimum is well-defined.
– Paul
Mar 28 '17 at 17:49

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. • Haha, try this search (or put a hyphen in your query). Feb 6 '17 at 16:31
• If you only have one regularisation parameter, then that sort of over-fitting tends not to be too problematic (as the optimisation problem only has one degree of freedom), but if you have many regularisation parameters (e.g. automatic relevance determination for neural nets) then it can quickly end up being very substantial. The one sd method is a nice heuristic for avoiding over-optimising the regularisation parameter, but it would be nice to try and have something with a bit more justification (1/2) Feb 11 '17 at 13:29
• The two approaches that we (Mrs Marsupial and I) have investigated is to regularise the hyper-parameters with a hyper-hyper-parameter that is integrated out analytically (jmlr.csail.mit.edu/papers/volume8/cawley07a/cawley07a.pdf) or to convert some of the hyper-parameters into parameters and fit them directly to the data as well, at the expense of adding an extra regularisation parameter (but that still reduces the degrees of freedom for model selection, so it still helps) (theoval.cmp.uea.ac.uk/publications/pdf/nn2014a.pdf) (2/2) Feb 11 '17 at 13:33
• Incidentally, over-fitting in model selection can result in the model over-fitting or under-fitting the training set, which can make the problem a bit more tricky to diagnose. From a Bayesian perspective, the best thing to do is not to optimise, but to marginalise over $\lambda$, but that is computationally expensive or tricky or both. A big advantage of the 1sd rule is that it is at the other end of that spectrum, and being an engineer, I like simple things that work ;o) (3/2) Feb 11 '17 at 13:37
• One thread about optimizing-lambda-vs-marginalizing-over-lambda topic that @DikranMarsupial mentioned is stats.stackexchange.com/questions/24799. That discussion is about ridge regression, and marginalizing is probably (?) trickier for lasso / elastic net / etc, whereas the beauty of CV is that it's so easy to implement. Feb 12 '17 at 15:53

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.

• Can you go into a bit more detail here? This seems fascinating. Apr 9 '14 at 21:07
• this means that with high probability too much variables are selected. -- to me it is not obvious why, and why with high probability too few variables could not be selected. After all, cross-validated selection should give an estimate of $\lambda$ that has little bias but probably high variance, as noted in the answer by Stephen Kolassa. Feb 12 '17 at 14:27
• I think the fact is that selecting more variables than required will reduce the prediction performance less than selecting not enough variables. For this reason CV tends to select more variables. Feb 12 '17 at 14:53
• have a look at this book springer.com/gp/book/9783642201912 and to the lasso chapter here drive.google.com/open?id=0B3FIuCA5bZUaT2ZLWFBIZ1JYbHM Feb 12 '17 at 15:58
• With underfitting, there is no corresponding increase in variance that could accidentally compensate the average loss in performance. So all in all, you run a certain risk to pick a too complex model, but a much lower risk to pick a too simple model. Together, you get a bias in direction of too complex models. May 17 '18 at 18:57