Are there any analytical results or experimental papers regarding the optimal choice of the coefficient of the $\ell_1$ penalty term. By optimal, I mean a parameter that maximizes the probability of selecting the best model, or that minimizes the expected loss. I am asking because often it is impractical to choose the parameter by cross-validation or bootstrap, either because of a large number of instances of the problem, or because of the size of the problem at hand. The only positive result I am aware of is Candes and Plan, Near-ideal model selection by $\ell_1$ minimization.
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ Are you aware of papers establishing consistency results for the lasso? Knight & Fu (2000), Yu & Zhao (2006), and various papers by Meinshausen. $\endgroup$– cardinalCommented May 7, 2011 at 23:27
-
$\begingroup$ Yes, but my question in not about asymptotic consistency, which is the subject of the papers you mentioned. $\endgroup$– gappyCommented May 8, 2011 at 11:09
-
1$\begingroup$ Those papers are (primarily) about model selection consistency, which I'd say is very related to the question you asked. :) $\endgroup$– cardinalCommented May 8, 2011 at 13:05
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
1
Checkout Theorem 5.1 of this Bickel et al.. A statistically optimal choice in terms of the error $\|y-\hat{y}(\lambda)\|_2^2$ is $\lambda = A \sigma_{\text{noise}} \sqrt{\dfrac{\log p}{n}}$ (with high probability), for a constant $A > 2\sqrt{2}$.
-
1$\begingroup$ This doesn't quite seem to fit the bill since it requires knowing $\sigma_\mathrm{noise}$. In fact, it's exactly this problem that motivates the square root lasso (arxiv.org/pdf/1009.5689.pdf) $\endgroup$ Commented Jun 7, 2017 at 16:03
$\begingroup$
$\endgroup$
2
I take it that you are mostly interested in regression, as in the cited paper, and not other applications of the $\ell_1$-penalty (graphical lasso, say).
I then believe that some answers can be found in the paper On the “degrees of freedom” of the lasso by Zou et al. Briefly, it gives an analytic formula for the effective degrees of freedom, which for the squared error loss allows you to replace CV by an analytic $C_p$-type statistic, say.
Another place to look is in The Dantzig selector: Statistical estimation when p is much larger than n and the discussion papers in the same issue of Annals of Statistics. My understanding is that they solve a problem closely related to lasso regression but with a fixed choice of penalty coefficient. But please take a look at the discussion papers too.
If you are not interested in prediction, but in model selection, I am not aware of similar results. Prediction optimal models often result in too many selected variables in regression models. In the paper Stability selection Meinshausen and Bühlmann presents a subsampling technique more useful for model selection, but it may be too computationally demanding for your needs.
-
$\begingroup$ (+1) All three of those papers are worth a careful reading for those interested in this subject. The Dantzig selector paper has some very nice math; however, I have not seen it get much traction in applications, nor do I expect it to. I think, among other things, the very noisy regularization paths make people nervous and so, with no obvious benefit over the lasso, make it a hard sell. $\endgroup$– cardinalCommented May 8, 2011 at 13:08
-
$\begingroup$ Hum, note that though the number of nonzero coefficients for a given value of the regularization parameter is an unbiased estimate for the DoFs at that value, this estimate is extremely high-variance. $\endgroup$– dohmatobCommented May 1, 2017 at 21:38
$\begingroup$
$\endgroup$
Since this question has been asked, interesting progress has been made. For instance, consider this paper
Chichignoud, M., Lederer, J., & Wainwright, M. (2016). A Practical Scheme and Fast Algorithm to Tune the Lasso With Optimality Guarantees. Journal of Machine Learning Research, 17, 1–17.
They propose a method to select the LASSO tuning parameter with provable finite sample guarantees for model selection. As they say in the paper, "For standard calibration schemes, among them Cross-Validation, no comparable guarantees are available in the literature. In fact, we are not aware of any finite sample guarantees for standard calibration schemes".
answered Jun 7, 2017 at 15:59
$\begingroup$
$\endgroup$
This does not answer your question, but: in a large data setting, it may be fine to tune the regularizer using a single train/test split, instead of doing it 10 or so times in cross-validation (or more for bootstrap). The size and representativeness of the sample chosen for the devset determines the accuracy of the estimation of the optimal regularizer.
In my experience the held-out loss is relatively flat over a substantial regularizer range. I'm sure this fact may not hold for other problems.
