2015/10/21 by Kory D. Johnson, Dongyu Lin, Johnson, Kory D. +7 · 1 citation
Engineering · Mathematics · #Control Systems and Identification #FOS: Computer and information sciences #FOS: Mathematics #Methodology (stat.ME) #Sparse and Compressive Sensing Techniques #Statistical Methods and Inference #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.1510.06319
openalex publication_date 2015/10/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
There has been an explosion of interest in using l1-regularization in place of l0-regularization for feature selection. We present theoretical results showing that while l1-penalized linear regression never outperforms l0-regularization by more than a constant factor, in some cases using an l1 penalty is infinitely worse than using an l0 penalty. We also show that the "optimal" l1 solutions are often inferior to l0 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 l1 problem, the "optimal" l1 solutions are often inferior to l0 solutions found using greedy classic stepwise regression. Furthermore, we show that solutions obtained by solving the convex l1 problem can be improved by selecting the best of the l1 models (for different regularization penalties) by using an l0 criterion. In other words, an approximate solution to the right problem can be better than the exact solution to the wrong problem.