¿Cómo obtengo el primal y dual para el estimador $\min _\beta\left[\|\beta\|^2+\sum_{i=1}^n \xi_i^2\right]$ tal que $\xi_i=y_i-h(x_i)^\top \beta$?

Question

Estoy trabajando en un ejercicio de aprendizaje estadístico que requiere cierto conocimiento de optimización convexa, del cual lamentablemente carezco.

Considera el modelo de regresión lineal $$y_i=h(x_i)^\top\beta+\epsilon_i \quad i=1,\ldots,n$$ donde $\varepsilon_i$ son errores aleatorios. Considera un núcleo simétrico y definido positivo $K(x_i, x_j)=h(x_i)^\top h(x_j)$. El estimador $\hat{\beta}$ es la solución a $$\min _\beta\left[\|\beta\|^2+\sum_{i=1}^n \xi_i^2\right]$$ sujeto a la restricción $\xi_i=y_i-h\left(x_i\right)^{\top} \beta$.

Ahora se me pide que (i) dé la función Lagrange primal, (ii) la función dual de Wolfe y (iii) derive una expresión para $\hat{\beta}$.

Para (i), al sustituir la restricción de igualdad e introducir multiplicadores de Lagrange obtengo $L_P=\beta^\top\beta+\sum_{i=1}^n \alpha_i(y_i-h(x_i)^\top\beta)^2$.

Para (ii), calculo $$\frac{\partial L_P}{\partial \beta}=\beta+2\sum_{i=1}^n\alpha_iy_ih(x_i)-2\sum_{i=1}^n\alpha_ih(x_i)^\top\beta h(x_i)=0.$$

Ahora considero que debo aislar $\beta$ en lo anterior y colocar la expresión que obtengo en el problema primal para obtener el dual. Estoy atascado aquí. Si mi derivación hasta ahora es correcta, agradecería una pista sobre cómo hacer esto. (Si no lo es, por supuesto estaría encantado de que me hicieran notar cualquier error). ¡Gracias por considerar mi pregunta!

Answer 1

Hay algunos problemas menores en las partes anteriores -- proporcionaré algunas pistas.

(i) Si recuerdo correctamente, esto es simplemente la función Lagrangiana (es decir, el objetivo del dual de Wolfe). Para un problema con restricciones de igualdad de la forma $$\underset{x}{\text{minimize}}\quad f(x) \\ \text{subject to} \quad g(x) = 0,$$ esto tomaría la forma $f(x) + \alpha g(x)$, o $f(x) + \mathbf{\alpha}^\top \mathbf{g}(x)$ si tienes múltiples restricciones como en este problema.

Sustituir la definición $\zeta_i$ en el objetivo original directamente va en contra del propósito de tener una restricción; aunque esta restricción parece vacía, a veces agregar tales restricciones puede hacer que la derivación del dual sea más fluida. Ver si (cambiando $x$ por $\beta$) puedes llevar tu problema a la forma mencionada anteriormente para obtener el primal Lagrangiano.

(ii) Tienes la idea correcta para el dual (derivada parcial del primal con respecto a $\beta$); creo que esto es sencillo una vez que (i) es correcto. Como un pequeño detalle, tu respuesta probablemente debería formularse como un problema de optimización (es decir, maximizar algo sujeto a la condición de primer orden = 0) - actualmente solo tienes una condición de primer orden.

(iii) Esta es probablemente la parte difícil si no has visto algunos trucos de álgebra lineal antes. Obtendrás algo de forma similar a la condición de primer orden que has proporcionado (la mayoría de los términos son del mismo orden). Puede ser útil notar que, dados algunos vectores $\mathbf{u}, \mathbf{v}$, $(\mathbf{u}^\top \mathbf{v}) \mathbf{u} = (\mathbf{u}\mathbf{u}^\top)\mathbf{v}$ (convéncete de que esto es cierto). Sustituye las variables por tu problema correspondientemente.

Como una comprobación de cordura, también puedes notar que esto es simplemente una formulación de regresión ridge kernelizada -- no es un gran problema (para el propósito de manejar el objetivo) ignorar el kernel por ahora, e intentar emparejar con la regresión ridge óptima. También es un buen ejercicio usar cxvpy para simular este problema y verificarlo.

En resumen, parece que tienes las ideas/intuiciones generales correctas sobre lo que necesitas hacer para (ii), (iii), pero hay algunos errores en la derivación para (i). No dudes en seguir si algo no está claro.

Answer 2

Según (i), el Lagrangiano no se define enchufando las restricciones de igualdad multiplicadas por los multiplicadores de Lagrange en la función objetivo.

Dado un problema de optimización con restricciones de igualdad $\{g_i(x) = 0 \}_{i=1}^n$, $$ \min f(x)\: s.t. \: g_i(x) = 0\:\forall i, $$ el Lagrangiano sería de la forma $\mathcal{L}(x,\alpha) = f(x)+\alpha^Tg(x)\qquad (*)$.

Asegúrate de "convertir" tus restricciones a la forma $g(x) = 0$ antes de enchufarlas en $(*)$.

Según (ii), admito que no estaba familiarizado con el concepto de Dualidad de Wolfe hasta este hilo. Sin embargo, el artículo de Wikipedia vinculado aquí no parece tener sentido para mí.

Dado que solo tienes restricciones de igualdad, el problema Dual de Lagrange tendría multiplicadores de Lagrange no restringidos. El Dual de Lagrange y el Dual de Wolfe deberían ser equivalentes. El problema Primal podría ser formulado de manera alternativa $$ \min_{\beta\in\mathbb{R}} \{ \max_{\alpha\in\mathbb{R}} \{||\beta||^2 + ||\xi||^2 + \sum_i \alpha_i \left( y_i - \beta^Th(x_i) -\xi_i \right) \}\} \equiv \min_{\beta\in\mathbb{R}} \{ \max_{\alpha\in\mathbb{R}} \{ \mathcal{L}(\beta,\alpha)\}. $$

El problema Dual de Lagrange: $\max_{\alpha\in\mathbb{R}} \{ \min_{\beta\in\mathbb{R}} \mathcal{L(\beta,\alpha)} \}$.

Por lo tanto, creo que el Dual de Wolfe tomaría más o menos la forma: $$ \max_{\alpha\in\mathbb{R}} \{ \min_{\beta\in\mathbb{R}} \mathcal{L(\beta,\alpha)} \} \\ s.t. \\ \nabla f(\beta)+\alpha^T\nabla g(\beta) = 0. $$ Observa que los multiplicadores $\alpha$ están no restringidos.

Si es una tarea, creo que tu profesor\TA apuntó a que simplificaras el término $ \min_{\beta\in\mathbb{R}} \mathcal{L(\beta,\alpha)} $ en el problema anterior para obtener un problema de maximización con solo los parámetros $\alpha$ (variables duales) para optimizar. En mi humilde opinión, deberías poder expresar los $\beta$s en términos de $\alpha$.

Espero que te ayude.