12
$\begingroup$

I have read the that the group lasso is used for variable selection and sparsity in a group of variables. I want to know the intuition behind this claim.

  • Why is group lasso preferred to lasso?
  • Why is the group lasso solution path not piecewise linear?
$\endgroup$
  • 1
    $\begingroup$ What I understand from the Yuan and Lin (2006) that lasso is designed for selecting individual variables not factor selection. So lasso addresses the ANOVA problem where goal is to select important main effects and interactions for accurate prediction which amounts to selection of groups of variables. The other example is of addtive model with polynomial where each component is expressed as linear combination of basis functions of original measured variables $\endgroup$ – Vendetta May 25 '16 at 2:46
10
$\begingroup$

Intuitively speaking, the group lasso can be preferred to the lasso since it provides a means for us to incorporate (a certain type of) additional information into our estimate for the true coefficient $\beta^*$. As an extreme scenario, considering the following:

With $y \sim \mathcal{N} (X \beta^*, \sigma^2 I )$, put $S = \{j : \beta^*_j \neq 0 \}$ as the support of $\beta^*$. Consider the "oracle" estimator $$\hat{\beta} = \arg\min_{\beta} \|y - X \beta\|_2^2 + \lambda \left( |S|^{1/2} \|\beta_S\|_2 + (p-|S|)^{1/2} \|\beta_{S^C}\|_2 \right),$$ which is the group lasso with two groups--one the true support and one the complement. Let $\lambda_{max}$ be the smallest value of $\lambda$ that makes $\hat{\beta} = 0$. Due to the nature of the group lasso penalty, we know that at $\lambda$ moves from $\lambda_{max}$ to $\lambda_{max} - \epsilon$ (for some small $\epsilon > 0$), exactly one group will enter into support of $\hat{\beta}$, which is popularly considered as an estimate for $S$. Due do our grouping, with high probability, the selected group will be $S$, and we'll have done a perfect job.

In practice, we don't select the groups this well. However, the groups, despite being finer than the extreme scenario above, will still help us: the choice would still be made between a group of true covariates and a group of untrue covariates. We're still borrowing strength.

This is formalized here. They show, under some conditions, that the an upper bound on the prediction error of the group lasso is lower than a lower bound on the prediction error of the plain lasso. That is, they proved that the grouping makes our estimation do better.

For your second question: The (plain) lasso penalty is piecewise linear, and this gives rise to the piecewise linear solution path. Intuitively, in the group lasso case, the penalty is no longer piecewise linear, so we no longer have this property. A great reference on piecewise linearity of solution paths is here. See their proposition 1. Let $L(\beta) = \|y - X \beta\|_2^2$ and $J(\beta) = \sum_{g \in G} |g|^{1/2} \|\beta_g\|_2$. They show that the solution path of the group lasso is linear if and only if $$\left( \nabla^2L(\hat{\beta}) + \lambda \nabla^2 J(\hat{\beta}) \right)^{-1} \nabla J(\hat{\beta})$$ is piecewise constant. Of course, it isn't since our penalty $J$ has global curvature.

$\endgroup$
  • 2
    $\begingroup$ It makes a lot sense now. Thanks a lot for your answer. $\endgroup$ – Vendetta May 7 '17 at 3:57
3
$\begingroup$

Ben's answer is the most general result. But the intuitive answer to the OP is motivated by the case of categorical predictors, which are usually encoded as multiple dummy variables: one for each category. It makes sense in many analyses to consider these dummy variables (representing one categorical predictor) together rather than separately.

If you have a categorical variable with, say, five levels, a straight lasso might leave two in and three out. How do you handle this in a principled manner? Decide to vote? Literally use the dummy variables instead of the more meaningful categorical? How does your dummy encoding affect your choices?

As they say in the introduction of The group lasso for logistic regression, it mentions:

Already for the special case in linear regression when not only continuous but also categorical predictors (factors) are present, the lasso solution is not satisfactory as it only selects individ- ual dummy variables instead of whole factors. Moreover, the lasso solution depends on how the dummy variables are encoded. Choosing different contrasts for a categorical predictor will produce different solutions in general.

As Ben points out, there are also more subtle links between predictors that might indicate that they should either be in or out together. But categorical variables are the poster child for group lasso.

$\endgroup$
  • $\begingroup$ @Ben: Hmmm... I can't really understand the OP's first comment, It looks like it's a response to a now-deleted comment? The question itself and its title -- which is what most viewers will read -- seems to be a general question. I'll certainly delete my answer if the question and title are changed to something about "What non-obvious applications are there to grouped lasso beyond the case of categorical variables?" $\endgroup$ – Wayne May 6 '17 at 20:58
  • $\begingroup$ Okay. I like your point about how using (plain) lasso on factors makes the estimates depend on the coding of the factors! I previously just thought of the group lasso as giving us a kind of "measurement sparsity" instead of a "parameter sparsity" (i.e. we should have to measure the factor or not--all levels should be selected or none.) $\endgroup$ – user795305 May 6 '17 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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