20
$\begingroup$

L1 penalized regression (aka lasso) is presented in two formulations. Let the two objective functions be $$ Q_1 = \frac{1}{2}||Y - X\beta||_2^2 \\ Q_2 =\frac{1}{2}||Y - X\beta||_2^2 + \lambda ||\beta||_1. $$ Then the two different formulations are $$ \text{argmin}_\beta \; Q_1 $$ subject to $$ ||\beta||_1 \leq t, $$ and, equivalently $$ \text{argmin}_\beta \; Q_2. $$ Using the Karush-Kuhn-Tucker (KKT) conditions, it's easy to see how the stationarity condition for the first formulation is equivalent to taking the gradient of the second formulation and setting it equal to 0. What I can not find, nor figure out, is how the complementary slackness condition for the first formulation, $\lambda\left(||\beta||_1 - t\right) = 0$, is guaranteed to be fulfilled by the solution to the second formulation.

$\endgroup$
16
$\begingroup$

The two formulations are equivalent in the sense that for every value of $t$ in the first formulation, there exists a value of $\lambda$ for the second formulation such that the two formulations have the same minimizer $\beta$.

Here's the justification:

Consider the lasso formulation: $$f(\beta)=\frac{1}{2}||Y - X\beta||_2^2 + \lambda ||\beta||_1$$ Let the minimizer be $\beta^*$ and let $b=||\beta^*||_1$. My claim is that if you set $t=b$ in the first formulation, then the solution of the first formulation will also be $\beta^*$. Here's the proof:

Consider the first formulation $$\min \frac{1}{2}||Y - X\beta||_2^2 \text{ s.t.} ||\beta||_1\leq b$$ If possible let this second formulation have a solution $\hat{\beta}$ such that $||\hat{\beta}||_1<||\beta^*||_1=b$ (note the strictly less than sign). Then it is easy to see that $f(\hat{\beta})<f(\beta^*)$ contradicting the fact that $\beta^*$ is a solution for the lasso. Thus, the solution to the first formulation is also $\beta^*$.

Since $t=b$, the complementary slackness condition is satisfied at the solution point $\beta^*$.

So, given a lasso formulation with $\lambda$, you construct a constrained formulation using a $t$ equal to the value of the $l_1$ norm of the lasso solution. Conversely, given a constrained formulation with $t$, you find a $\lambda$ such that the solution to the lasso will be equal to the solution of the constrained formulation.

(If you know about subgradients, you can find this $\lambda$ by solving the equation $X^T(y-X\beta^*)=\lambda z^*$, where $z^* \in \partial ||\beta^*||_1)$

$\endgroup$
  • 1
    $\begingroup$ Excellent. Once you see the solution you always feel dumb for not getting there yourself. I assume you mean, in finding the contradiction, suppose we find a $\hat{\beta}$ such that $||\hat{\beta}||_1 < ||\beta^*||_1 = b$? $\endgroup$ – goodepic Apr 1 '14 at 15:55
  • $\begingroup$ Consider flaggin answer as correct $\endgroup$ – bdeonovic Apr 1 '14 at 16:40
  • 2
    $\begingroup$ can you elaborate why $f(\hat{\beta}) < f(\beta^*)$ $\endgroup$ – goofd Mar 24 '15 at 23:50
  • $\begingroup$ This proves that the solution to the first formulation must also have an l1-norm of b. How does it prove that the two solutions are indeed the same? $\endgroup$ – broncoAbierto Jun 11 '15 at 23:09
  • 1
    $\begingroup$ Additionally, the Lasso does not always have a unique solution, so we cannot refer to the minimizer. arxiv.org/pdf/1206.0313.pdf. We could, however, refer to the set of minimizers and show that some $\hat{\beta} \neq \beta^*$ must belong to that set. $\endgroup$ – broncoAbierto Jun 12 '15 at 9:12
3
$\begingroup$

I think that elexhobby's idea for this proof is a good one, but I don't think it's completely correct.

In showing that the existence of a solution for the first formulation, $\hat{\beta}$, such that $\|\hat{\beta}\| < \|\beta^*\|$ leads to a contradiction, we can only assume the necessity of $\|\hat{\beta}\| = \|\beta^*\|$, not that $\hat{\beta} = \beta^*$.

I suggest, instead, that we proceed as follows:

For convenience, let's denote by $P_1$ and $P_2$ the first and second formulation respectively. Let's assume that $P_2$ has a unique solution, $\beta^*$, with $\|\beta^*\|=b$. Let $P_1$ have a solution, $\hat{\beta} \neq \beta^*$. Then, we have that $\|\hat{\beta}\| \leq \|\beta^*\|$ (it cannot be greater because of the constraint) and therefore $f(\hat{\beta}) \leq f(\beta^*)$. If $f(\hat{\beta}) < f(\beta^*)$ then $\beta^*$ is not the solution to the $P_2$, which contradicts our assumptions. If $f(\hat{\beta}) = f(\beta^*)$ then $\hat{\beta} = \beta^*$, since we assumed the solution to be unique.

However, it may be the case that the Lasso has multiple solutions. By lemma 1 of arxiv.org/pdf/1206.0313.pdf we know that all of these solutions have the same $\ell 1$-norm (and the same minimum value, of course). We set that norm as the constraint for the $P_1$ and proceed.

Let's denote by $S$ the set of solutions to $P_2$, with $\|\beta\|=b \mbox{ } \forall \beta \in S$. Let $P_1$ have a solution, $\hat{\beta} \notin S$. Then, we have that $\|\hat{\beta}\| \leq \|\beta\| \forall \beta \in S$ and therefore $f(\hat{\beta}) \leq f(\beta) \forall \beta \in S$. If $f(\hat{\beta}) = f(\beta)$ for some $\beta \in S$ (and hence for all of them) then $\hat{\beta} \in S$, which contradicts our assumptions. If $f(\hat{\beta}) < f(\beta)$ for some $\beta \in S$ then $S$ is not the set of solutions to $P_2$. Therefore, every solution to $P_1$ is in $S$, i.e. any solution to $P_1$ is also a solution to $P_2$. It would remain to prove that the complementary holds too.

$\endgroup$

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.