KKT versus unconstrained formulation of lasso regression

Question

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.

Answer 1

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)$

Answer 2

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.