Optimal penalty selection for lasso 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.
 A: 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.
A: 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}$.
A: 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".
A: 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.
