# If $\ell_0$ regularization can be done via the proximal operator, why are people still using LASSO?

I have just learned that a general framework in constrained optimization is called "proximal gradient optimization". It is interesting that the $$\ell_0$$ "norm" is also associated with a proximal operator. Hence, one can apply iterative hard thresholding algorithm to get the sparse solution of the following

$$\min \Vert Y-X\beta\Vert_F + \lambda \vert \beta \vert_0$$

If so, why people are still using $$\ell_1$$? If you can just get the result by non-convex optimization directly, why are people still using LASSO?

I want to know what's the downside of the proximal gradient approach for $$\ell_0$$ minimization. Is it because of the non-convexity and randomness associated with? That means the initial estimator is very important.

• Using in what context?
– Neal
Commented Oct 15, 2019 at 18:24
• For example, at work, I don't really care what the scikit-learn or xgboost or statsmodels backends are doing as long as they fit a model correctly and in a reasonable amount of time.
– Neal
Commented Oct 15, 2019 at 18:48
• Commented Oct 15, 2019 at 20:10
• @Neal, yes at work I don't care either. I am just curious.. Commented Oct 16, 2019 at 13:01

## 1 Answer

The application of proximal gradient to this exact problem is considered in (equations (2) and (35) in) the Uncertainty in Artificial Intelligence (UAI) 2019 paper Fast Proximal Gradient Descent for A Class of Non-convex and Non-smooth Sparse Learning Problems, Yingzhen Yang and Jiahui Yu, with algorithm supplement at http://auai.org/uai2019/proceedings/supplements/508_supplement.pdf

Unfortunately, due to the non-convexity, there is no guarantee that the algorithm will converge to the global optimum, which is what is desired. (Note: the remainder of my answer is not covered at all in the above links.) The solution obtained will depend on the algorithm starting point (initial estimator as you refer to it). An obvious starting point which can be used is the solution of the LASSO problem.

If the proximal gradient algorithm is implemented with a line search guaranteeing decrease of the objective function, and the LASSO solution is used as starting solution, then the proximal gradient solution will be at least as good as, and hopefully better than, the LASSO solution when evaluated relative to the $$\ell_0$$ regularized objective function. So you can think of this as a post-processed LASSO solution moving it in the direction of the $$\ell_0$$ regularized optimal solution. I don't know how good a starting solution the LASSO solution will wind up being.

If you really want to find the globally optimal solution to the $$\ell_0$$ regularized problem, it can be formulated as a (Convex) Mixed-Integer Quadratic Programming problem (MIQP) and solved to global optimality using standard solvers such as CPLEX, GUROBI, XPRESS, or MOSEK. However, given that the problem is NP Hard, it might take a while. I don't know whether the following would be meritorious from an overall computation time standpoint, but you could use the proximal gradient solution as a starting point for the MIQP optimizer, which might at least speed up the MIQP optimizer. LASSO is much faster and easier to solve, so I don't think it's going to be out of business for a while.

• thanks! Currently what I do is run lasso first, then perform a truncation on small weights (needs some kind of threshold manually), then refit the remaining with a OrdinaryLeastSquare. I know it sounds stupid but it is easy to implement. Now, I just want speed actually AND multi-task lasso with sklearn implementation (I might forgot to mention I do multi-task learning) takes a really long time to compute the lasso path. Commented Dec 13, 2019 at 0:55
• @artificiallyintelligence What you do is not stupid and known under the name "debiasing". I think it's already implemented in GPSR and SpaRSA.
– Dirk
Commented Dec 13, 2019 at 6:38
• @Dirk Thanks for the info! Commented Dec 13, 2019 at 20:45