The Lasso Problem and Uniqueness

By Robert Tibshirani. 2012

595 citations recorded by the source corpus.

The lasso is a popular tool for sparse linear regression, especially for problems in which the number of variables p exceeds the number of observations n. But when p > n, the lasso criterion is not strictly convex, and hence it may not have a unique minimum. An important question is: when is the lasso solution well-defined (unique)? We review results from the literature, which show that if the predictor variables are drawn from a continuous probability distribution, then there is a unique lasso solution with probability one, regardless of the sizes of n and p. We also show that this result extends easily to l1 penalized minimization problems over a wide range of loss functions. A second important question is: how can we manage the case of non-uniqueness in lasso solutions? In light of the aforementioned result, this case really only arises when some of the predictor variables are discrete, or when some post-processing has been performed on continuous predictor measurements. Though we certainly cannot claim to provide a complete answer to such a broad question, we do present progress towards understanding some aspects of non- uniqueness. First, we extend the LARS algorithm for computing the lasso solution path to cover the non-unique case, so that this path algorithm works for any predictor matrix. Next, we derive a simple method for computing the component-wise uncertainty in lasso solutions of any given problem instance, based on linear programming. Finally, we review results from the literature on some of the unifying properties of lasso solutions, and also point out particular forms of solutions that have distinctive properties.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

Extended Comparisons of Best Subset Selection, Forward Stepwise Selection, and the Lasso (2017, neutral): “Recall (Tibshirani, 2013) that when the columns of X are in general position (a weak condition occurring almost surely for continuously distributed pedictors, regardless of n, p), it holds that: • the lasso solution is unique; • the submatrix XAλ of active predictors has full column rank, thus β̂ Aλ”
Multi-Stage Multi-Task Feature Learning (2012, neutral): “Therefore, both zero mean Gaussian and zero mean bounded random variables are sub-Gaussians.”
Exact post-selection inference with the lasso (2013, unknown): “We consider the equicorrelation set (Tibshirani, 2013)”
On cross-validated Lasso in high dimensions (2016, background): “In principle, the optimization problem in (2) may have multiple solutions, but to simplify presentation and to avoid unnecessary technicalities, we assume throughout the paper, without further notice, that the distribution of X is absolutely continuous with respect to Lebesgue measure on Rp, in whic”
Improving Mean Variance Optimization through Sparse Hedging Restrictions (2015, background): “In this case, however, lasso has only one unique solution as long as the regressors are continuous random variables, regardless of which specific numbers N and T are (Tibshirani (2013)).”
The Generalized Lasso Problem and Uniqueness (2018, background): “This effectively generalizes previous uniqueness results for the lasso problem (Tibshirani, 2013) (which corresponds to the special case D = I).”
Dykstra's Algorithm, ADMM, and Coordinate Descent: Connections, Insights, and Extensions (2017, background): “See Tibshirani (2013) for a precise deﬁnition of general position and proofs of these facts.”
Learning Transferable Knowledge Through Embedding Spaces (2019, background): “In the attribute-agnostic formulation, we first find the sparse representation αi of the unseen image x′i by solving the following LASSO problem, αi = argmina { 1 p ‖xi −Dxa‖22 + λ r ‖a‖1 } .”
Degrees of freedom and model search (2014, background): “The identity in (5) shows that [for uncorrelated, homoskedastic regression errors as in (1)] the optimism of f is just a positive constant times its degrees of freedom; in other words, fitting procedures with a higher degrees of freedom will have higher a optimism.”
Goodness‐of‐fit tests for high dimensional linear models (2015, background): “Note that, although the lasso solution may potentially be non-unique, the residuals are always uniquely defined, as the fitted values from a lasso fit are unique (see Tibshirani (2013), for example).”
Exact Post-Selection Inference for Sequential Regression Procedures (2014, background): “Even more recently, van de Geer et al. (2013), Javanmard & Montanari (2013a), and Javanmard & Montanari (2013b) all present approaches for debiasing the lasso estimate based on estimates of the inverse covariance matrix of the predictors.”
A significance test for forward stepwise model selection (2014, unknown): “Recall the LASSO estimator is given by β̂(λ) = argmin β∈Rp 1 2 ‖y −Xβ‖22 + λ‖β‖1 (4) The following facts are summarized in Lockhart et al. (2013); Tibshirani (2012).”
A SIGNIFICANCE TEST FOR THE LASSO (2013, background): “In this analysis, shrinkage plays a key role: though additional variables are chosen adaptively, the coefficients of lasso active variables are shrunken due to the ℓ1 penalty.”
A crowdsourcing triage algorithm for geopolitical event forecasting (2018, background): “When L is fixed, the optimization for α j reduces to a LASSO problem [5, 15] for each α j : ˆ α j = argmin where ⊤ denotes transpose of a matrix.”