# Least squares problem penalising the number of non-zero coefficients

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?

• See Statistical Learning with Sparsity, by Hastie, Tibshirani and Wainwright, section 2.9 $l_q$ Penalties and Bayes Estimates: "for $q=0$, the [penalty] term counts the number of nonzero elements ... [which] amounts to best-subset selection ... a nonconvex and combinatorial optimization problem" Jan 31, 2023 at 22:04
• hastie.su.domains/StatLearnSparsity the PDF is available from the author's website Jan 31, 2023 at 22:05
• @Arian Thanks will check
– fes
Feb 1, 2023 at 8:20

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.

• $L_0$ regression is also a hard problem because of its complexity class. stats.stackexchange.com/questions/364097/…
– Sycorax
Jan 31, 2023 at 21:32
• Additional information: some efficient algorithms for best subset selection were recently proposed by Rahul Mazumder and colleagues; see publications since 2016 in his Google Scholar Profile. Feb 1, 2023 at 12:16