24
$\begingroup$

One of the motivations for the elastic net was the following limitation of LASSO:

In the $p > n$ case, the lasso selects at most n variables before it saturates, because of the nature of the convex optimization problem. This seems to be a limiting feature for a variable selection method. Moreover, the lasso is not well defined unless the bound on the L1-norm of the coefficients is smaller than a certain value.

(http://onlinelibrary.wiley.com/doi/10.1111/j.1467-9868.2005.00503.x/full)

I understand that LASSO is a quadratic programming problem but also can be solved via LARS or element-wise gradient descent. But I do not understand where in these algorithms I encounter a problem if $p > n$ where $p$ is the number of predictors and $n$ is the sample size. And why is this problem solved using elastic net where I augment the problem to $p+n$ variables which clearly exceeds $p$.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ If lasso restricts use to keeping p<=n why is that a drawback rather than a virtue. overfitting is a serious problem that comes about when p=n. The model with p=n is a saturated model and often that model overfits because it will fit the observed data perfectly but not necessarily predcit future cases well. $\endgroup$
    – Michael R. Chernick
    Sep 30, 2012 at 12:07
  • 3
    $\begingroup$ That the lasso selects only up to $n$ variables can be seen as a consequence of the fact that it can be solved using (a slight modification of) the LARS algorithm, which only admits up to $n$ variables into the active set at any one time. That this does not hold in the elastic-net case essentially follows from the incorporation of the $\ell_2$ penalty and so behaves more like ridge regression, the latter of which normally results in all coefficients being nonzero. $\endgroup$
    – cardinal
    Sep 30, 2012 at 13:57
  • $\begingroup$ Thank you for the answers, and how would I see for gradient descent that at most n variables can selected: Presentation at cs.cmu.edu/afs/cs/project/link-3/lafferty/www/ml-stat2/talks/… Paper (section 4) at datamining.dongguk.ac.kr/papers/GLASSO_JRSSB_V1.final.pdf $\endgroup$
    – user1137731
    Sep 30, 2012 at 21:53
  • 3
    $\begingroup$ @user: I think you may be conflating the mathematical problem with its numerical solution. The LARS algorithm shows that the lasso solution will select at most $n$ variables. This is independent of the actual numerical means for arriving at the solution, i.e., the LARS algorithm gives the insight about the problem, but of course any other method that equivalently solves the problem must have the same property! :-) $\endgroup$
    – cardinal
    Oct 1, 2012 at 0:29
  • 1
    $\begingroup$ Consider a feature duplicated $p$ times. There will exist a lasso estimator with exactly $p$ nonzeroes (even if $p>n$) Therefore your statement isn't true as written. $\endgroup$
    – user795305
    Sep 14, 2017 at 2:55

2 Answers 2

Reset to default
16
$\begingroup$

As said, this is not a property of an algorithm but of the optimization problem. The KKT conditions basically give that for coefficient $\beta_j$ to be non-zero it has to correspond to a fixed correlation with the residual $|X_j^t(y-X\beta)| = \lambda$ ($\lambda$ is the regularization parameter).

After resolving the various complications with absolute value etc, you are left with a linear equation for each non-zero coefficient. Since the rank of the matrix $X$ is at most $n$ when $p>n$, this is the number of equations that can be solved, and therefore there are at most n non-zeros (unless there are redundancies).

By the way, this is true for any loss function, not only the standard lasso with $L_2$ loss. So it is in fact a property of the lasso penalty. There are many papers that show this KKT view and the resulting conclusions, I can point to our paper: Rosset and Zhu, Piecewise Linear Regularized Solutions Paths, Annals of Stats 2007 and refs therein.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ What does KKT stand for? Also, is it possible you mean L1 loss when talking about the standard lasso? $\endgroup$
    – miura
    Oct 1, 2012 at 8:58
  • $\begingroup$ Hi Saharon and welcome to the site. You can use LaTeX to make formulas neater (I did so in your answer) and you don't need to sign your posts, as a signature is added automatically. $\endgroup$
    – Peter Flom
    Oct 1, 2012 at 10:58
  • 1
    $\begingroup$ @miura: KKT stands for Karush-Kuhn-Tucker. The KKT conditions are certain equations that solutions to (sufficiently regular) optimization problems must fulfill (wikipedia article). $\endgroup$
    – mogron
    Oct 1, 2012 at 11:05
  • $\begingroup$ I just see that Ryan Tibshirani has a very relevant working paper 'The Lasso Problem and Uniqueness.': stat.cmu.edu/~ryantibs/papers/lassounique.pdf $\endgroup$
    – user1137731
    Oct 8, 2012 at 2:40
8
$\begingroup$

Another explanation is the following: if $n < p$, the rank of the data matrix $X$ is at most $n$, so the dimension of its (right) null space is at least $p - n$. Write any vector in this null space as $z$. Then at any feasible point $\beta$, one can always move in this $p - n$-dimensional null space towards the coordinate axes of the $p$-dimensional ambient space, to arrive at a $\beta+z$, where (at most) $n$ $\beta_j$s are nonzero, and the LASSO objective function

$$ \|y-X(\beta+z)\|_2^2 + \lambda \|\beta+z\|_1 = \|y-X\beta\|_2^2 + \lambda \|\beta+z\|_1 < \|y-X\beta\|_2^2 + \lambda \|\beta\|_1 $$

has decreased.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ (+1) There's a gap here: see my comment on OPs post. $\endgroup$
    – user795305
    Sep 14, 2017 at 2:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.