Métodos de gradiente proximal para el aprendizaje

Una técnica importante relacionada con los métodos de gradiente proximal es la descomposición de Moreau, que descompone el operador identidad como la suma de dos operadores de proximidad. ^{[ 1 ]} Es decir, sea${\displaystyle \varphi$ Sea {\mathcal {X}}\to \mathbb {R} } unafunción semicontinua inferior y convexa en un espacio vectorial.${\displaystyle {\mathcal {X}}}$. Definimos su conjugado de Fenchel${\displaystyle \varphi ^{*}:{\mathcal {X}}\to \mathbb {R} }$ser la función

${\displaystyle \varphi ^{*}(u):=\sup _{x\in {\mathcal {X}}}\langle x,u\rangle -\varphi (x).}$

La forma general de la descomposición de Moreau establece que para cualquier${\displaystyle x\in {\mathcal {X}}}$y cualquier${\displaystyle \gamma >0}$eso

${\displaystyle x=\operatorname {prox} _{\gamma \varphi }(x)+\gamma \operatorname {prox} _{\varphi ^{*}/\gamma }(x/\gamma ),}$

que para${\displaystyle \gamma =1}$implica que${\displaystyle x=\operatorname {prox} _{\varphi }(x)+\operatorname {prox} _{\varphi ^{*}}(x)}$. ^{[ 1 ] [ 3 ]} La descomposición de Moreau puede considerarse una generalización de la descomposición ortogonal usual de un espacio vectorial , análoga al hecho de que los operadores de proximidad son generalizaciones de proyecciones. ^{[ 1 ]}

En ciertas situaciones puede ser más fácil calcular el operador de proximidad para el conjugado.${\displaystyle \varphi ^{*}}$en lugar de la función${\displaystyle \varphi }$y por lo tanto se puede aplicar la descomposición de Moreau. Este es el caso para group lasso .

Para simplificar, restringimos nuestra atención al problema donde${\displaystyle \lambda =1}$Para resolver el problema

${\displaystyle \min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-\langle w,x_{i}\rangle )^{2}+\|w\|_{1},}$

Consideramos nuestra función objetivo en dos partes: un término convexo y diferenciable.${\displaystyle F(w)={\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-\langle w,x_{i}\rangle )^{2}}$y una función convexa${\displaystyle R(w)=\|w\|_{1}}$. Tenga en cuenta que${\displaystyle R}$no es estrictamente convexa.

Calculemos el operador de proximidad para${\displaystyle R(w)}$Primero encontramos una caracterización alternativa del operador de proximidad.${\displaystyle \operatorname {prox} _{R}(x)}$como sigue:

${\displaystyle {\begin{aligned}u=\operatorname {prox} _{R}(x)\iff &0\in \partial \left(R(u)+{\frac {1}{2}}\|u-x\|_{2}^{2}\right)\\\iff &0\in \partial R(u)+u-x\\\iff &x-u\in \partial R(u).\end{aligned}}}$

Para${\displaystyle R(w)=\|w\|_{1}}$es fácil de calcular${\displaystyle \partial R(w)}$: el${\displaystyle i}$entrada de${\displaystyle \partial R(w)}$es precisamente

${\displaystyle \partial |w_{i}|={\begin{cases}1,&w_{i}>0\\-1,&w_{i}<0\\\left[-1,1\right],&w_{i}=0.\end{cases}}}$

Utilizando la recaracterización del operador de proximidad dada anteriormente, para la elección de${\displaystyle R(w)=\|w\|_{1}}$y${\displaystyle \gamma >0}$tenemos eso${\displaystyle \operatorname {prox} _{\gamma R}(x)}$se define entrada por entrada

${\displaystyle \left(\operatorname {prox} _{\gamma R}(x)\right)_{i}={\begin{cases}x_{i}-\gamma ,&x_{i}>\gamma \\0,&|x_{i}|\leq \gamma \\x_{i}+\gamma ,&x_{i}<-\gamma ,\end{cases}}}$

que se conoce como operador de umbralización suave${\displaystyle S_{\gamma }(x)=\operatorname {prox} _{\gamma \|\cdot \|_{1}}(x)}$. ^{[ 1 ] [ 6 ]}

Para resolver finalmente el problema del lazo, consideramos la ecuación del punto fijo mostrada anteriormente:

${\displaystyle x^{*}=\operatorname {prox} _{\gamma R}\left(x^{*}-\gamma \nabla F(x^{*})\right).}$

Dado que hemos calculado explícitamente la forma del operador de proximidad, podemos definir un procedimiento iterativo estándar de punto fijo. Es decir, fijamos un punto inicial.${\displaystyle w^{0}\in \mathbb {R} ^{d}}$y para${\displaystyle k=1,2,\ldots }$definir

${\displaystyle w^{k+1}=S_{\gamma }\left(w^{k}-\gamma \nabla F\left(w^{k}\right)\right).}$

Nótese aquí la compensación efectiva entre el término de error empírico.${\displaystyle F(w)}$y la penalización por regularización${\displaystyle R(w)}$. Este método de punto fijo ha desacoplado el efecto de las dos funciones convexas diferentes que componen la función objetivo en un paso de descenso de gradiente (${\displaystyle w^{k}-\gamma \nabla F\left(w^{k}\right)}$) y un paso de umbralización suave (a través de${\displaystyle S_{\gamma }}$).

La convergencia de este esquema de punto fijo está bien estudiada en la literatura ^{[ 1 ] [ 6 ]} y está garantizada bajo una elección apropiada del tamaño del paso.${\displaystyle \gamma }$y función de pérdida (como la pérdida cuadrática tomada aquí). Nesterov introdujo métodos acelerados en 1983 que mejoran la tasa de convergencia bajo ciertas suposiciones de regularidad en${\displaystyle F}$[ ^{7 ]} Estos métodos se han estudiado ampliamente en años anteriores. ^{[ 8 ]} Para problemas de aprendizaje más generales donde el operador de proximidad no se puede calcular explícitamente para algún término de ^{regularización}${\displaystyle R}$, tales esquemas de punto fijo aún pueden llevarse a cabo utilizando aproximaciones tanto al gradiente como al operador de proximidad. ^{[ 4 ] [ 9 ]}

En el esquema de iteración de punto fijo

${\displaystyle w^{k+1}=\operatorname {prox} _{\gamma R}\left(w^{k}-\gamma \nabla F\left(w^{k}\right)\right),}$

uno puede permitir un tamaño de paso variable${\displaystyle \gamma _{k}}$en lugar de una constante${\displaystyle \gamma }$Se han propuesto numerosos esquemas de tamaño de paso adaptativo a lo largo de la literatura. ^{[ 1 ] [ 4 ] [ 11 ] [ 12 ]} Las aplicaciones de estos esquemas ^{[ 2 ] [ 13 ]} sugieren que pueden ofrecer una mejora sustancial en el número de iteraciones necesarias para la convergencia de punto fijo.

La regularización de red elástica ofrece una alternativa a la pura${\displaystyle \ell _{1}}$regularización. El problema de lasso (${\displaystyle \ell _{1}}$La regularización implica el término de penalización.${\displaystyle R(w)=\|w\|_{1}}$, que no es estrictamente convexa. Por lo tanto, las soluciones a${\displaystyle \min _{w}F(w)+R(w),}$dónde${\displaystyle F}$es alguna función de pérdida empírica, no tiene por qué ser única. Esto a menudo se evita mediante la inclusión de un término estrictamente convexo adicional, como un${\displaystyle \ell _{2}}$penalización de regularización de norma. Por ejemplo, se puede considerar el problema

${\displaystyle \min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-\langle w,x_{i}\rangle )^{2}+\lambda \left((1-\mu )\|w\|_{1}+\mu \|w\|_{2}^{2}\right),}$

dónde${\displaystyle x_{i}\in \mathbb {R} ^{d}{\text{ and }}y_{i}\in \mathbb {R} .}$ Para${\displaystyle 0<\mu \leq 1}$el término de penalización${\displaystyle \lambda \left((1-\mu )\|w\|_{1}+\mu \|w\|_{2}^{2}\right)}$Ahora es estrictamente convexa y, por lo tanto, el problema de minimización ahora admite una solución única. Se ha observado que para suficientemente pequeño${\displaystyle \mu >0}$, el término de penalización adicional${\displaystyle \mu \|w\|_{2}^{2}}$actúa como un precondicionador y puede mejorar sustancialmente la convergencia sin afectar negativamente la escasez de soluciones. ^{[ 2 ] [ 14 ]}

El lasso grupal es una generalización del método lasso cuando las características se agrupan en bloques disjuntos. ^{[ 15 ]} Supongamos que las características se agrupan en bloques${\displaystyle \{w_{1},\ldots ,w_{G}\}}$Aquí tomamos como penalización de regularización

${\displaystyle R(w)=\sum _{g=1}^{G}\|w_{g}\|_{2},}$

que es la suma de la${\displaystyle \ell _{2}}$norma en los vectores de características correspondientes para los diferentes grupos. Se puede utilizar un análisis de operador de proximidad similar al anterior para calcular el operador de proximidad para esta penalización. Donde la penalización lasso tiene un operador de proximidad que es un umbral suave en cada componente individual, el operador de proximidad para el lasso de grupo es un umbral suave en cada grupo. Para el grupo${\displaystyle w_{g}}$tenemos ese operador de proximidad de${\displaystyle \lambda \gamma \left(\sum _{g=1}^{G}\|w_{g}\|_{2}\right)}$es dado por

${\displaystyle {\widetilde {S}}_{\lambda \gamma }(w_{g})={\begin{cases}w_{g}-\lambda \gamma {\frac {w_{g}}{\|w_{g}\|_{2}}},&\|w_{g}\|_{2}>\lambda \gamma \\0,&\|w_{g}\|_{2}\leq \lambda \gamma \end{cases}}}$

dónde${\displaystyle w_{g}}$es el${\displaystyle g}$el grupo.

A diferencia de lasso, la derivación del operador de proximidad para lasso grupal se basa en la descomposición de Moreau . Aquí, el operador de proximidad del conjugado de la penalización de lasso grupal se convierte en una proyección sobre la bola de una norma dual . ^{[ 2 ]}

A diferencia del problema de group lasso, donde las características se agrupan en bloques disjuntos, puede darse el caso de que las características agrupadas se superpongan o tengan una estructura anidada. Tales generalizaciones de group lasso se han considerado en diversos contextos. ^{[ 16 ] [ 17 ] [ 18 ] [ 19 ]} Para grupos superpuestos, un enfoque común es el conocido como latent group lasso , que introduce variables latentes para tener en cuenta la superposición. ^{[ 20 ] [ 21 ]} Las estructuras de grupos anidados se estudian en la predicción de estructuras jerárquicas y con grafos acíclicos dirigidos . ^{[ 18 ]}