8
$\begingroup$

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?

$\endgroup$
3
  • 2
    $\begingroup$ 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" $\endgroup$
    – Adrian
    Jan 31, 2023 at 22:04
  • $\begingroup$ hastie.su.domains/StatLearnSparsity the PDF is available from the author's website $\endgroup$
    – Adrian
    Jan 31, 2023 at 22:05
  • $\begingroup$ @Arian Thanks will check $\endgroup$
    – fes
    Feb 1, 2023 at 8:20

1 Answer 1

10
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ $L_0$ regression is also a hard problem because of its complexity class. stats.stackexchange.com/questions/364097/… $\endgroup$
    – Sycorax
    Jan 31, 2023 at 21:32
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 1, 2023 at 12:16

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.