1
$\begingroup$

I am trying to get from Equation (4) to (5) in Model selection through sparse maximum likelihood estimation for multivariate gaussian or binary data by Banerjee et. al [http://www.jmlr.org/papers/volume9/banerjee08a/banerjee08a.pdf][1]. The problem to derive the dual of the following problem: $$ \text{argmin}_{y} \{y'Wy: ||y-S_j||_{\infty} \leq \lambda \} $$ which turns out to be $$ \text{min}_{x} \{x'Wx -S_j'x + \lambda ||x||_{1}\} $$ How does one do this?

$\endgroup$
0
$\begingroup$

I've typed up a proof for you on Google Drive.

I have an extra leading constant. However, that doesn't change the nature of the result. If we start off the original optimization problem with a leading constant of (1/4) we get the same result as the paper.

I'll write the part about Strong Duality if I get a chance, but I think it should be approached using Slater's condition.

Update #1:

In the linked PDF file, I use the standard process for formulating the dual problem:

  1. Construct the Lagrangian
  2. Minimize the Lagrangian with respect to the original variable to arrive at the dual problem

The key insight is to reparametrize the dual problem so constructed using a single variable $$x$$ which lets us arrive at the dual problem suggested in the paper.

$\endgroup$
5
  • 1
    $\begingroup$ Welcome to Cross Validated! We are trying to build a permanent repository of high-quality statistical information in the form of questions & answers. We try to avoid link-only answers which are subject to link-rot and may become useless. As such this is currently more of a comment than an answer in its own right. If you're able, could you expand it, perhaps by giving a summary or an outline of the information at the link? $\endgroup$
    – Glen_b
    Nov 3 '16 at 5:30
  • $\begingroup$ Is there any reason a more detailed summary of the actual argument could not be given here? Indeed it's not so long that you couldn't put the entire thing in. $\endgroup$
    – Glen_b
    Nov 5 '16 at 6:22
  • $\begingroup$ @Glen_b That's true - I provided a link to the proof since it seemed useful to me and others if it was possible to share a link to a document, or a document itself, with the proof. $\endgroup$ Nov 6 '16 at 0:39
  • $\begingroup$ @Glen_b It's quite easy to paste the entire thing here though, with some slight modifications. Let me do that right now. $\endgroup$ Nov 6 '16 at 0:39
  • $\begingroup$ @Glen_b On second thoughts, the formatting and structure I've used in latex is actually a lot more comprehensive. I think it's harder to transcribe the same thing in MathJax+Markdown which is much more limited that full-fledged latex. Could we leave the link as is? $\endgroup$ Nov 6 '16 at 0:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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