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

Question

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.

Answer 1

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.