2
$\begingroup$

Sparse-group lasso is defined as

$$\frac{1}{2n}\left\|y-X\beta \right\| + (1-\alpha)\lambda\sum_{l=1}^m \sqrt{p_l}\left\|\beta^{(l)} \right\|_2 + \alpha \lambda \left\| \beta\right\|_1$$ In the SGL paper, the subgradient equations are shown in terms of group $k$, given by

$$\frac{1}{n}X^{(k)\top} \left(y-\sum_{l=1}^m X^{(l)} \hat{\beta}^{(l)} \right)= (1-\alpha)\lambda u + \alpha\lambda v,$$

where $u$ and $v$ are subgradients of $\| \hat{\beta}^{(k)}\|_2$ $\| \hat{\beta}^{(k)}\|_1$and respectively, given by

$$u= \begin{cases}\frac{\hat{\beta}^{(k)}}{\left\|\hat{\beta}^{(k)}\right\|_{2}} & \text { if } \hat{\beta}^{(k)} \neq \mathbf{0}, \\ \in\left\{u:\|u\|_{2} \leq 1\right\} & \text { if } \hat{\beta}^{(k)}=\mathbf{0},\end{cases}$$ and

$$v_{j}= \begin{cases}\operatorname{sign}\left(\hat{\beta}_{j}^{(k)}\right) & \text { if } \hat{\beta}_{j}^{(k)} \neq 0, \\ \in\left\{v_{j}:\left|v_{j}\right| \leq 1\right\} & \text { if } \hat{\beta}_{j}^{(k)}=0.\end{cases}$$

I have two questions about this:

  1. Can we only differentiate w.r.t. to group k because the penalty is separable between groups?
  2. What would the subgradient be if we differentiate w.r.t. to all $\beta$?
$\endgroup$
1

1 Answer 1

2
$\begingroup$

I think you have small misunderstanding of the relationship between the group penalty and the notion of a subgradient. I'll do my best to try and make the relationship clear.

In any optimization problem $\min_{x \in \mathcal{\mathbb{R}^{d}}} f(x)$ with $f$ differentiable and convex, minima can be characterized by solving $\nabla f(x) = 0$ for $x$. Moreover, when $f$ is at a minimum $x^{*}$, $f$ must be stationary with respect to every subset of variables that make up $x$, else we could decrease the objective by changing only these variables. That is, if a minimum $x^{*}$ is formed as a concatenation of two vectors $x = (w^{*}, v^{*})$, then taking the gradient with respect to $w$ must also be $0$, $$\nabla_{w} f(w,v^{*}) = 0.$$

Finally, when $f$ is convex but not differentiable, the notion of the subgradient replaces the gradient in the above discussion. So block-separability of the objective gives that minima are characterized by the necessary condition $$0 \in \partial_{w} f(w,v^{*})$$

In the subgradient equation you are referring to from the sparse group LASSO paper, the authors have simply computed the subdifferential of the sparse group LASSO objective for each group $\beta_{i}$. These play the role of $w$ in my discussion above.

Can we only differentiate w.r.t. to group k because the penalty is separable between groups?

We can sub-differentiate with respect to whatever subset of variables we want, but doing so with respect to each group is especially convenient because the penalty is separable across these groups. In my opinion the authors haven't made it very clear in their initial assumptions that the groups are non-overlapping, but this is indeed the case because of the form the differential takes.

What would the subgradient be if we differentiate w.r.t. to all 𝛽?

The concatenation of the subdifferential term for each block. This is because the objective is separable across blocks. Don't get bogged down by the subdifferential here; just think about what happens when you compute $\nabla f(x)$ where $f(x) = f(x_1, x_2) = f_{1}(x_{1}) + f_{2}(x_{2})$.

$\endgroup$

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.