Abstract
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. Furthermore, we show that solutions obtained by solving the convex $l_1$ problem can be improved by selecting the best of the $l_1$ models (for different regularization penalties) by using an $l_0$ criterion. In other words, an approximate solution to the right problem can be better than the exact solution to the wrong problem.
Introduction
In high-dimensional linear regression, where the number of features $p$ significantly exceeds the number of observations $n$, the primary goal is to identify a sparse subset of features that maintain high predictive accuracy. The theoretically ideal approach is $l_0$ regularization, which directly penalizes the number of non-zero coefficients. However, because $l_0$ optimization is NP-hard, the machine learning community has largely adopted $l_1$ regularization (the Lasso) as a convex, computationally efficient proxy. This paper investigates the statistical cost of this computational shortcut, questioning whether the convenience of $l_1$ leads to significantly inferior models compared to $l_0$ approaches.
Methodology and Estimation Bias
The authors compare $l_0$ and $l_1$ penalties through the lens of predictive risk. A fundamental difference lies in how these penalties treat coefficients. $l_0$ regularization uses "Hard Thresholding," where small coefficients are zeroed out while others remain untouched. In contrast, $l_1$ regularization employs "Soft Thresholding," which shrinks all coefficients toward zero to achieve sparsity.
As shown in Figure 6, $l_1$ regularization introduces significant bias by shrinking the "true" signals. From a Bayesian perspective, $l_1$ corresponds to a Laplacian prior, whereas $l_0$ is more closely aligned with a Cauchy prior. The heavy tails of the Cauchy distribution allow for large, unshrunk coefficients, which often better represent real-world signals than the aggressive shrinkage of the Laplacian prior.
Risk Ratio Analysis and Key Results
The core of the paper's theoretical contribution is the minimax risk ratio analysis. The authors prove that while $l_0$ is never more than a small constant factor worse than $l_1$, the reverse is not true: $l_1$ can be arbitrarily (infinitely) worse than $l_0$ in sparse systems.
Figure 2 illustrates these bounds. The risk of an $l_1$ model grows quadratically with the penalty relative to $l_0$. Empirical tests on correlated features and NP-hard "exact cover" problems support these findings. In simulations, $l_0$-selected models consistently achieved lower Root Mean Squared Error (RMSE) and identified sparser, more accurate feature sets than the "optimal" $l_1$ solutions. Specifically, on the "3-sets" problem, greedy $l_0$ approximations (stepwise regression) found the true minimum subsets, while Lasso over-selected by 2x to 3x.
Conclusion
The findings suggest that the computational convenience of $l_1$ regularization comes at a substantial statistical price. The "Devil's Choice" of $l_1$—either keeping noise to preserve signal or shrinking signal to remove noise—is a fundamental limitation not shared by $l_0$. The authors conclude that an approximate solution to the "right" problem ($l_0$) is often superior to an exact solution to the "wrong" problem ($l_1$). A practical path forward involves using efficient $l_1$ algorithms (like LARS) to generate candidate model paths and then applying $l_0$ criteria (like RIC) to select the final model.
Summary updated