1
$\begingroup$

I was reading some course notes here.

On Page 8, it says:

Note that strong duality holds here (Slater's condition), but the optimal value of the last problem is not necessarily the optimal lasso objective value

How is this even possible?

What they are essentially doing for establishing duality is taking an unconstrained problem and making it constrained through the use of a dummy variable. Then, the dual is taken. I don't understand why the values of the primal and dual objectives will not be the same.

Improve this question
$\endgroup$
2
  • $\begingroup$ I've got to be honest, I'm not sure, either. You should contact the author directly if possible. $\endgroup$
    – Michael Grant
    Feb 19, 2014 at 2:25
  • 1
    $\begingroup$ Isn't that just because they removed the $\|y\|_2^2$ (and of course the minus sign)? $\endgroup$
    – Cristóbal Guzmán
    Apr 11, 2014 at 16:15

1 Answer 1

Reset to default
1
$\begingroup$

The equation entitled "lasso dual" at the top of slide 8 in https://www.cs.cmu.edu/~ggordon/10725-F12/slides/17-dual-corresp.pdf DOES have the same value as the original lasso problem, by strong duality.

But then they transform to an "equivalent" problem, which will attain its optimum at the same point, but will have a different optimal value. In the equivalent version, they have dropped both the 1/2 scale factor and the norm of y term, and they have also flipped the sign of everything to transform from a maximization to a minimization problem... so of course it will have a different optimal value.

This whole slide is to illustrate the "Dual Subtleties" they describe on slide 6.

Improve this answer
$\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.