Least squares problem penalising the number of non-zero coefficients

Question

Consider a constrained least squares problem of minimizing $(y-X\beta)^T(y-X\beta)$ subject to a constraint or penalty on the number of non-zero coefficients $\beta_i$. This seems related to LASSO or Ridge regression but is different from either of these. It seems also related to AIC/BIC type criteria but again is not the same. Does this type of problem or something similar appear somewhere in the literature?

Answer 1

If ridge regression is considered to penalize the usual (square) loss according to the $L_2$ norm of the parameter vector and LASSO regression is considered to penalize the loss according to the $L_1$ norm of the parameter vector, then this would be a penalty according to the $L_0$ "norm" of the parameter vector, which is a count of the nonzero elements. I put "norm" in quotes because $L_0$ is not really a norm, but it is norm-ish.

$$ L\bigg(\hat\beta\bigg\vert X, y,\lambda\bigg) = \overset{N}{\underset{i=1}{\sum}} \left( y_i - \overset{p}{\underset{j=0}{\sum}}\left( \hat\beta_j^TX_{ij} \right) \right)^2 + \lambda\left\vert\left\vert \hat\beta\right\vert\right\vert_0 $$

Ridge and LASSO regression would use $\lambda\left\vert\left\vert \hat\beta\right\vert\right\vert_2$ and $\lambda\left\vert\left\vert \hat\beta\right\vert\right\vert_1$, respectively.

Some of the trouble you might encounter with this is that the above loss function will not be a continuous function of $\hat\beta$ unless $\lambda=0$ (which is just ordinary least squares), since the $L_0$ "norm" abruptly changes as a vector component changes its status of zero or nonzero. Another issue is that computers have trouble declaring a value as being truly zero. For instance, run the following code in R: (sqrt(2))^2 - 2 == 0. We all know that $\left(\sqrt 2\right)^2-2=0$, yet my computer says the statement is false. Finally, as is pointed out in the comments, $L_0$ regularization is $NP$-hard.

For a reference in the literature:

Louizos, Christos, Max Welling, and Diederik P. Kingma. "Learning sparse neural networks through $ L_0 $ regularization." arXiv preprint arXiv:1712.01312 (2017).

I found that by running a Google search for "l0 regularization" and would expect that and similar searches to turn up more hits.