¿Por qué mi derivación de una solución de forma cerrada para Lasso es incorrecta?

Question

El problema del lazo $$\beta^{\text{lasso}}= \operatorname*{argmin}_\beta \| y-X\beta\|^2_2 + \alpha \| \beta\|_1$$ tiene la solución en forma cerrada: $$ \beta_j^{\text{lasso}}= \mathrm{sgn}(\beta^{\text{LS}}_j)(|\beta_j^{\text{LS}}|-\alpha)^+ $$ si $X$ tiene columnas ortogonales. Esto se demostró en este hilo: Derivation of closed form lasso solution.

Sin embargo, no entiendo por qué no hay una solución en forma cerrada en general. Utilizando subdiferenciales obtuve lo siguiente.

($X$ es una Matriz $n \times p$)

$$f(\beta)=\|{y-X\beta}\|_2^2 + \alpha\|{\beta}\|_1$$ $$ =\sum_{i=1}^n (y_i-X_i\beta)^2 + \alpha \sum_{j=1}^p |\beta_j| $$ ($X_i$ es la fila i de $X$) $$= \sum_{i=1}^n y_i^2 -2\sum_{i=1}^n y_i X_i \beta + \sum_{i=1}^n \beta^T X_i^T X_i \beta + \alpha \sum_{j=1}^p |\beta_j|$$ $$\Rightarrow \frac{\partial f}{\partial \beta_j}= -2\sum_{i=1}^ny_i X_{ij} + 2 \sum_{i=1}^n X_{ij}^2\beta_j + \frac{\partial}{\partial \beta_j}(\alpha |\beta_j|)$$ $$= \begin{cases} -2\sum_{i=1}^ny_i X_{ij} + 2 \sum_{i=1}^n X_{ij}^2\beta_j + \alpha \text{ for } \beta_j > 0 \\ -2\sum_{i=1}^ny_i X_{ij} + 2 \sum_{i=1}^n X_{ij}^2\beta_j - \alpha \text{ for } \beta_j < 0 \\ [-2\sum_{i=1}^ny_i X_{ij} - \alpha, -2\sum_{i=1}^ny_i X_{ij} + \alpha] \text{ for } \beta_j = 0 \end{cases} $$ Con $\frac{\partial f}{\partial \beta_j} = 0$ obtenemos

$$\beta_j = \begin{cases} \left( 2(\sum_{i=1}^ny_i X_{ij}) - \alpha \right)/ 2\sum_{i=1}^n X_{ij}^2 &\text{para } \sum_{i=1}^ny_i X_{ij} > \alpha \\ \left( 2(\sum_{i=1}^ny_i X_{ij}) + \alpha \right)/ 2\sum_{i=1}^n X_{ij}^2 &\text{para } \sum_{i=1}^ny_i X_{ij} < -\alpha \\ 0 &\text{para }\sum_{i=1}^ny_i X_{ij} \in [-\alpha, \alpha] \end{cases}$$

¿Alguien ve dónde me equivoqué?

Respuesta:

Si escribimos el problema en términos de matrices podemos ver fácilmente por qué una solución en forma cerrada solo existe en el caso ortonormal con $X^TX= I$:

$$ f(\beta)= \| y-X\beta\|^2_2 + \alpha \| \beta\|_1$$ $$= y^Ty -2\beta^TX^Ty + \beta^TX^TX\beta + \alpha \| \beta\|_1$$ $$\Rightarrow \nabla f(\beta)=-2X^Ty + 2X^TX\beta + \nabla(\alpha| \beta\|_1)$$ (He dado muchos pasos de una vez aquí. Sin embargo, hasta este punto es completamente análogo a la derivación de la solución de mínimos cuadrados. Así que deberías poder encontrar los pasos faltantes allí.) $$\Rightarrow \frac{\partial f}{\partial \beta_j}=-2X^T_{j} y + 2(X^TX)_j \beta + \frac{\partial}{\partial \beta_j}(\alpha |\beta_j|) $$

Con $\frac{\partial f}{\partial \beta_j} = 0$ obtenemos

$$2(X^TX)_j \beta =2X^T_{j} y - \frac{\partial}{\partial \beta_j}(\alpha |\beta_j|) $$ $$\Leftrightarrow 2(X^TX)_{jj} \beta_j = 2X^T_{j} y - \frac{\partial}{\partial \beta_j}(\alpha |\beta_j|) - 2\sum_{i=1,i\neq j}^p(X^TX)_{ji}\beta_i $$

Ahora podemos ver que nuestra solución para un $\beta_j$ depende de todos los otros $\beta_{i\neq j}$, por lo que no está claro cómo proceder desde aquí. Si $X$ es ortonormal, tenemos $2(X^TX)_j \beta = 2(I)_j \beta = 2\beta_j$ por lo tanto, definitivamente existe una solución en forma cerrada en este caso.

Gracias a Guðmundur Einarsson por su respuesta, en la cual me basé aquí. Espero que esta vez sea correcto :-)

Answer 1

Esto se hace normalmente con regresión de ángulo mínimo, puedes encontrar el documento aquí.

Disculpa mi confusión al principio, voy a intentarlo de nuevo.

Entonces, después de la expansión de tu función $f(\beta)$ obtienes

$$ f(\beta)=\sum_{i=1}^n y_i^2 -2\sum_{i=1}^n y_i X_i \beta + \sum_{i=1}^n \beta^T X_i^T X_i \beta + \alpha \sum_{j=1}^p |\beta_j| $$

Luego calculas la derivada parcial con respecto a $\beta_j$. Mi preocupación está en tu cálculo de la derivada parcial del último término antes de la norma-1, es decir, el término cuadrático. Veámoslo más detenidamente. Tenemos que:

$$ X_i\beta = \beta^T X_i^T = (\beta_1 X_{i1}+\beta_2 X_{i2}+\cdots+ \beta_p X_{ip}) $$ Entonces puedes reescribir tu término cuadrático como: $$ \sum_{i=1}^n \beta^T X_i^T X_i \beta = \sum_{i=1}^n (X_i \beta)^2 $$ Ahora podemos usar la regla de la cadena para calcular la derivada de esto con respecto a $\beta_j$: $$ \frac{\partial }{\partial \beta_j} \sum_{i=1}^n (X_i \beta)^2 = \sum_{i=1}^n \frac{\partial }{\partial \beta_j} (X_i \beta)^2 = \sum_{i=1}^n 2(X_i \beta)X_{ij} $$

Entonces ahora tu problema no se simplifica tan fácilmente, porque tienes todos los coeficientes $\beta$ presentes en cada ecuación.

Esto no responde a tu pregunta sobre por qué no hay una solución en forma cerrada de Lasso, podría añadir algo más más adelante sobre eso.