La regresión penalizada L1 (también conocida como lasso) se presenta en dos formulaciones. Sean las dos funciones objetivo $$ Q_1 = \frac{1}{2}||Y - X\beta||_2^2 \\ Q_2 =\frac{1}{2}||Y - X\beta||_2^2 + \lambda ||\beta||_1. $$ Entonces las dos formulaciones diferentes son $$ \text{argmin}_\beta \; Q_1 $$ sujeto a $$ ||\beta||_1 \leq t, $$ y, equivalentemente $$ \text{argmin}_\beta \; Q_2. $$ Utilizando las condiciones de Karush-Kuhn-Tucker (KKT), es fácil ver cómo la condición de estacionariedad para la primera formulación es equivalente a tomar el gradiente de la segunda formulación y fijarlo igual a 0. Lo que no puedo encontrar, ni averiguar, es cómo la condición de holgura complementaria para la primera formulación, $\lambda\left(||\beta||_1 - t\right) = 0$ está garantizado que se cumple en la solución de la segunda formulación.
Respuestas
¿Demasiados anuncios?
Las dos formulaciones son equivalentes en el sentido de que para cada valor de $t$ en la primera formulación, existe un valor de $\lambda$ para la segunda formulación de forma que las dos formulaciones tengan el mismo minimizador $\beta$ .
He aquí la justificación:
Consideremos la formulación del lazo: $$f(\beta)=\frac{1}{2}||Y - X\beta||_2^2 + \lambda ||\beta||_1$$ Sea el minimizador $\beta^*$ y que $b=||\beta^*||_1$ . Mi afirmación es que si se establece $t=b$ en la primera formulación, entonces la solución de la primera formulación también será $\beta^*$ . He aquí la prueba:
Consideremos la primera formulación $$\min \frac{1}{2}||Y - X\beta||_2^2 \text{ s.t.} ||\beta||_1\leq b$$ Si es posible que esta segunda formulación tenga solución $\hat{\beta}$ tal que $||\hat{\beta}||_1<||\beta^*||_1=b$ (nótese el signo estrictamente menor que). Entonces es fácil ver que $f(\hat{\beta})<f(\beta^*)$ contradiciendo el hecho de que $\beta^*$ es una solución para el lazo. Por lo tanto, la solución de la primera formulación es también $\beta^*$ .
Desde $t=b$ la condición de holgura complementaria se cumple en el punto de solución $\beta^*$ .
Así pues, dada una formulación lasso con $\lambda$ se construye una formulación restringida utilizando un $t$ igual al valor del $l_1$ de la solución del lazo. A la inversa, dada una formulación restringida con $t$ , se encuentra un $\lambda$ tal que la solución del lazo sea igual a la solución de la formulación restringida.
(Si conoce los subgradientes, puede encontrar esto $\lambda$ resolviendo la ecuación $X^T(y-X\beta^*)=\lambda z^*$ donde $z^* \in \partial ||\beta^*||_1)$
Creo que la idea de elexhobby para esta prueba es buena, pero no creo que sea del todo correcta.
Al demostrar que la existencia de una solución para la primera formulación, $\hat{\beta}$ tal que $\|\hat{\beta}\| < \|\beta^*\|$ conduce a una contradicción, sólo podemos suponer la necesidad de $\|\hat{\beta}\| = \|\beta^*\|$ no es que $\hat{\beta} = \beta^*$ .
Sugiero, en cambio, que procedamos del siguiente modo:
Por comodidad, vamos a denotar por $P_1$ y $P_2$ la primera y la segunda formulación, respectivamente. Supongamos que $P_2$ tiene una solución única, $\beta^*$ con $\|\beta^*\|=b$ . Sea $P_1$ tienen una solución, $\hat{\beta} \neq \beta^*$ . Entonces, tenemos que $\|\hat{\beta}\| \leq \|\beta^*\|$ (no puede ser mayor debido a la restricción) y por lo tanto $f(\hat{\beta}) \leq f(\beta^*)$ . Si $f(\hat{\beta}) < f(\beta^*)$ entonces $\beta^*$ no es la solución al $P_2$ lo que contradice nuestras suposiciones. Si $f(\hat{\beta}) = f(\beta^*)$ entonces $\hat{\beta} = \beta^*$ ya que suponemos que la solución es única.
Sin embargo, puede darse el caso de que el Lasso tenga múltiples soluciones. Por el lema 1 de arxiv.org/pdf/1206.0313.pdf sabemos que todas estas soluciones tienen el mismo $\ell 1$ -norma (y el mismo valor mínimo, por supuesto). Establecemos esa norma como la restricción para la $P_1$ y proceder.
Denotemos por $S$ el conjunto de soluciones de $P_2$ con $\|\beta\|=b \mbox{ } \forall \beta \in S$ . Sea $P_1$ tienen una solución, $\hat{\beta} \notin S$ . Entonces, tenemos que $\|\hat{\beta}\| \leq \|\beta\| \forall \beta \in S$ y por lo tanto $f(\hat{\beta}) \leq f(\beta) \forall \beta \in S$ . Si $f(\hat{\beta}) = f(\beta)$ para algunos $\beta \in S$ (y por tanto para todas ellas) entonces $\hat{\beta} \in S$ lo que contradice nuestras suposiciones. Si $f(\hat{\beta}) < f(\beta)$ para algunos $\beta \in S$ entonces $S$ no es el conjunto de soluciones de $P_2$ . Por lo tanto, toda solución de $P_1$ está en $S$ es decir, cualquier solución de $P_1$ también es una solución para $P_2$ . Quedaría por demostrar que lo complementario también se cumple.
