A Risk Ratio Comparison of $l_0$ and $l_1$ Penalized Regression

Understand

There has been an explosion of interest in using $l_1$-regularization in place of $l_0$-regularization for feature selection.

• We present theoretical results showing that while $l_1$-penalized linear regression never outperforms $l_0$-regularization by more than a constant factor, in some cases using an $l_1$ penalty is infinitely worse than using an $l_0$ penalty.
• We also show that the "optimal" $l_1$ solutions are often inferior to $l_0$ solutions found using stepwise regression.
• We also compare algorithms for solving these two problems and show that although solutions can be found efficiently for the $l_1$ problem, the "optimal" $l_1$ solutions are often inferior to $l_0$ solutions found using greedy classic stepwise regression.