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.

  • 1
    $\begingroup$ What is the goal for which you consider lasso vs. proximal gradient approach to $l_0$ minimization as solutions? $\endgroup$ Oct 15, 2019 at 18:25
  • $\begingroup$ @RichardHardy the goal is to understand what are the pros and cons. If one thing doesn't eliminate the other, it must be the case that both has advantages over certain problems. $\endgroup$ Oct 16, 2019 at 12:59
  • 1
    $\begingroup$ It is difficult to discuss pros and cons when there is no goal of applying the methods. If you do not have a concrete goal, how do you eveluate whether a method has performed well or poorly? $\endgroup$ Oct 16, 2019 at 16:28
  • $\begingroup$ @RichardHardy say for instance, the computational efficency, convergence property... is it giving false positive over a set of exmaples... $\endgroup$ Oct 16, 2019 at 23:46
  • 1
    $\begingroup$ Thank you, finally the question is becoming clearer to me. Since the primary goal of lasso is not variable selection, I wonder if it should be used for that at all. But of course, the optimality of any procedure is always defined w.r.t. a specific goal. Given a concrete goal and a concrete loss function, methods could be compared under some assumptions about the data generating process. $\endgroup$ Oct 18, 2019 at 7:22


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.