2
$\begingroup$

I'm testing out an algorithm for the lasso. That is, the problem is to find the $\beta$ which solves the following:

$$\min\frac{1}{2} \left\| y-X\beta\right\|_2^2 + \lambda \|\beta\|_1$$

How can I verify that the $\beta$ I find with my algorithm is the minimum? A few ideas I had:

  • I could try several values of $\beta$ in a random search, but as $\beta$ is normally a vector (normally sized 100 and above) this is very computationally expensive
  • Checking how the convex cost changes. I've looked at how the evaluation of the convex optimisation problem changes throughout the algorithm, and it does indeed decrease until it flattens out. I'm not sure this is sufficient proof though.
  • Can I generate data where I know what the minimum is?
$\endgroup$
7
  • 2
    $\begingroup$ You could compare your results with that of an existing algorithm $\endgroup$
    – Henry
    Sep 16, 2022 at 8:32
  • $\begingroup$ @Henry In terms of the obtained $\beta$ or the convex function cost? I've done this and achieved a lower minimum, but the $\beta$ values don't really match. $\endgroup$
    – user19904
    Sep 16, 2022 at 9:32
  • $\begingroup$ I was thinking you could take $y,X,\lambda$ and compare the $\beta$ results, perhaps several times with different $y,X,\lambda$ $\endgroup$
    – Henry
    Sep 16, 2022 at 9:44
  • $\begingroup$ @Henry I have done that and whilst there is some agreement with $\beta$, it's not that strong. But like I mentioned, the $\beta$ obtained from my algorithm achieves a lower minimum. So I'm not sure what to make of it. $\endgroup$
    – user19904
    Sep 16, 2022 at 9:46
  • $\begingroup$ If you can reduce that to a small example, it might be worth editing your question to show what $y,X,λ$ you used and what $\beta$ results you get from the two algorithms $\endgroup$
    – Henry
    Sep 16, 2022 at 9:51

1 Answer 1

2
$\begingroup$

The safest way to test an algorithm of this kind is to compute your results in cases where you can derive the minimum exactly through analytic methods (i.e., without relying on comparison with another algorithm that might also fail). Thus, I would recommend you examine whether there are cases of this optimisation where the minimising value can be obtained in closed form from standard calculus techniques. If you can find some cases of this kind then you can compare the results of your algorithm to the known minima in these cases.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.