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

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$$?

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.