Group Lasso with intersecting groups?

Question

Let's say I want to model $\vec{y}$ based on $\vec{x}_1$, $\vec{x}_2$, ... $\vec{x}_m$ as:

$$\vec{y} ~~\approx~~ \beta_1 \vec{x}_1 ~+~ ... ~+~ \beta_m\vec{x}_m$$

Now, I could use Lasso to encourage most of the $\beta_j$ to be zero.

But let's say instead I have sets of variables, $G_1$ ... $G_p$, each $G_k \subset \lbrace 1 ... m \rbrace$, and I want to apply a penalty $\alpha_k$ for $G_k$ if any $\beta_j \ne 0$, $j \in G_k$. i.e., I want to encourage sparse participation of the groups of variables.

Now, I could solve this as a quadratic programming problem, that is,

$$\min||\beta_1 \vec{x}_1 ~+~ ... ~+~ \beta_m\vec{x}_m - \vec{y}||_2^2 ~~+~~ \alpha_1\max(|\beta_j|\text{ for }j \in G_1) ~+~ ... ~+~ \alpha_p\max(|\beta_j|\text{ for }j \in G_p)$$

where $\max(|...|)$ can be modeled as linear constraints.

Unfortunately, my anecdotal experience is that this does not scale nearly as well as the Lasso algorithm in glmnet, which, for reasons that I don't understand, seems to be vastly more efficient than solving the equivalent QP problem using IPOPT.

Do there exist algorithms, or even better implementations thereof, that solve the sort of intersecting-group-Lasso problem as I have described it above?

Answer 1

As you mention in your comment, these sort of problems form part of the structured sparsity research field. All the code I know of for this problem is in matlab, for instance this library supports overlapping groups, through the method overlappingLeastR. Mark Schmidt has some code also.

These problems can be solved using general purpose convex optimization libraries as well, such as cvx, although that will be much slower. Discussion here.