KKT versus formulation non contrainte de régression au lasso

La régression pénalisée L1 (alias lasso) est présentée en deux formulations. Soit les deux fonctions objectives

Q_{1} = \frac{1}{2} | | Y - X β | |_{2}^{2} Q_{2} = \frac{1}{2} | | Y - X β | |_{2}^{2} + λ | | β | |_{1} .

$Q_1 = \frac{1}{2}||Y - X\beta||_2^2 \\ Q_2 =\frac{1}{2}||Y - X\beta||_2^2 + \lambda ||\beta||_1.$ Alors les deux formulations différentes sont

{argmin}_{β} Q_{1}

$\text{argmin}_\beta \; Q_1$ sous réserve de

| | β | |_{1} \leq t,

$||\beta||_1 \leq t,$ et, de façon équivalente

{argmin}_{β} Q_{2} .

$\text{argmin}_\beta \; Q_2.$ En utilisant les conditions de Karush-Kuhn-Tucker (KKT), il est facile de voir comment la condition de stationnarité pour la première formulation équivaut à prendre le gradient de la deuxième formulation et à le mettre égal à 0. Ce que je ne peux pas trouver, ni comprendre , est la manière dont la condition de mou complémentaire pour la première formulation,

λ (| | β | |_{1} - t) = 0

$\lambda\left(||\beta||_1 - t\right) = 0$ , est garantie d'être remplie par la solution de la deuxième formulation.

regression lasso penalized goodepic
la source

Réponses:

Les deux formulations sont équivalentes en ce sens que pour chaque valeur de dans la première formulation, il existe une valeur de pour la deuxième formulation telle que les deux formulations ont le même minimiseur . $t$ $\lambda$ $\beta$

Voici la justification:

Considérons la formulation du lasso: Soit le minimiseuret. Mon affirmation est que si vous définissezdans la première formulation, alors la solution de la première formulation sera également. Voici la preuve:

f (β) = \frac{1}{2} | | Y - X β | |_{2}^{2} + λ | | β | |_{1}

$f(\beta)=\frac{1}{2}||Y - X\beta||_2^2 + \lambda ||\beta||_1$

β^{*}

$\beta^*$

b = | | β^{*} | |_{1}

$b=||\beta^*||_1$

t = b

$t=b$

β^{*}

$\beta^*$

Considérez la première formulation Si possibleque cette seconde formulation ont une solution telle que(notez le signe strictement inférieur à). Ensuiteil est facile de voir que

min \frac{1}{2} | | Y - X β | |_{2}^{2} s.t. | | β | |_{1} \leq b

$\min \frac{1}{2}||Y - X\beta||_2^2 \text{ s.t.} ||\beta||_1\leq b$

\hat{β}

$\hat{\beta}$

| | \hat{β} | |_{1} < | | β^{*} | |_{1} = b

$||\hat{\beta}||_1<||\beta^*||_1=b$

contredisant le fait que

f (\hat{β}) < f (β^{*})

$f(\hat{\beta})<f(\beta^*)$

β^{*}

$\beta^*$ est une solution pour le lasso. Ainsi, la solution de la première formulation est également

β^{*}

$\beta^*$

Puisque , la condition de mou complémentaire est satisfaite au point de solution . $t=b$ $\beta^*$

Donc, étant donné une formulation de lasso avec , vous construisez une formulation contrainte en utilisant un égal à la valeur de la norme de la solution de lasso. Inversement, étant donné une formulation contrainte avec , vous trouvez un tel que la solution du lasso sera égale à la solution de la formulation contrainte. $\lambda$ $t$ $l_1$ $t$ $\lambda$

(Si vous connaissez les sous-gradients, vous pouvez trouver ce en résolvant l'équation , où $\lambda$ $X^T(y-X\beta^*)=\lambda z^*$ $z^* \in \partial ||\beta^*||_1)$

elexhobby
la source

Excellent. Une fois que vous voyez la solution, vous vous sentez toujours stupide de ne pas y arriver vous-même. Je suppose que vous voulez dire, à trouver la contradiction, supposons que nous trouvons un

tel que

\hat{β}

$\hat{\beta}$

| | \hat{β} | |_{1} < | | β^{*} | |_{1} = b

$||\hat{\beta}||_1 < ||\beta^*||_1 = b$

goodepic

Considérez la réponse de flaggin comme correcte

bdeonovic

Pouvez - vous expliquer pourquoi

f (\hat{β}) < f (β^{*})

$f(\hat{\beta}) < f(\beta^*)$

goofd

Cela prouve que la solution de la première formulation doit également avoir une norme l1 de b. Comment prouve-t-on que les deux solutions sont bien les mêmes?

broncoAbierto

En outre, le Lasso n'a pas toujours une solution unique, donc nous ne pouvons pas se référer à la Minimizer. arxiv.org/pdf/1206.0313.pdf . On pourrait cependant se référer à l'ensemble des minimiseurs et montrer que certains

doit appartenir à cet ensemble.

\hat{β} \neq β^{*}

$\hat{\beta} \neq \beta^*$

broncoAbierto

Je pense que l'idée d'elexhobby pour cette preuve est bonne, mais je ne pense pas qu'elle soit complètement correcte.

Pour démontrer que l'existence d'une solution pour la première , de telle sorte que conduit à une contradiction, on ne peut supposer la nécessité de , non que . $\hat{\beta}$ $\|\hat{\beta}\| < \|\beta^*\|$ $\|\hat{\beta}\| = \|\beta^*\|$ $\hat{\beta} = \beta^*$

Je suggère plutôt de procéder comme suit:

$P_1$ $P_2$ $P_2$ $\beta^*$ $\|\beta^*\|=b$ $P_1$ $\hat{\beta} \neq \beta^*$ $\|\hat{\beta}\| \leq \|\beta^*\|$ $f(\hat{\beta}) \leq f(\beta^*)$ $f(\hat{\beta}) < f(\beta^*)$ $\beta^*$ $P_2$ $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.

broncoAbierto
la source