Shrinkage methods: does non-convex constraints ($q < 1$) also induce sparsity?

Question

I'm reading ESLII, in particular the chapter about shrinkage methods, lasso, and ridge regression.

The optimal model parameters for a given constraint $\sum | \beta_j |^q < \alpha $ are given by the equation

$$ \tilde{\beta} = \text{argmin}_\beta \left\{ \left(y_i - \beta_0 - \sum_{j=1}^p \beta_j x_{ij}\right)^2 + \lambda \sum_j^p |\beta_j|^q \right\} $$

The argument they made to show that lasso ($q=1$) induces sparsity is the typical diamond vs ellipse picture.

According to the book

Unlike the disk, the diamond has corners; if the solution occurs at a corner, then it has one parameter $\beta_j$ equal to zero. When $p > 2$, the diamond becomes a rhomboid, and has many corners, flat edges and faces; there are many more opportunities for the estimated parameters to be zero.

However, the same argument can be applied when $0< q < 1$, since the solution has more chances to happen in one of the spikes of the contour plot, because if $q<1$ the countour plot is no longer convex. My question is then, would it be possible to perform feature selection and induce sparsity by constraining the parameters using $q < 1$?

Answer 1

Yes, however the unique thing about the lasso relative to other $L_p$ penalties is that it both induces sparsity and leads to a convex optimization problem. For $p > 1$ you have a convex optimization but no sparsity, while for $p < 1$ you have sparsity but no convexity. Convexity is important because it implies we can optimize the objective function efficiently; without convexity it is not easy to design a robust optimization procedure that runs quickly and is guaranteed to work.