Reducción de la varianza estocástica

En el método SAGA, ^{[ 3 ]} el enfoque prototípico de promedio de tablas, una tabla de tamaño${\displaystyle n}$se mantiene que contiene el último gradiente observado para cada${\displaystyle f_{i}}$término, que denotamos${\displaystyle g_{i}}$En cada paso, un índice${\displaystyle i}$se muestrea y se obtiene un nuevo gradiente.${\displaystyle \nabla f_{i}(x_{k})}$se calcula. La iteración${\displaystyle x_{k}}$Se actualiza con:

${\displaystyle x_{k+1}=x_{k}-\gamma \left[\nabla f_{i}(x_{k})-g_{i}+{\frac {1}{n}}\sum _{i=1}^{n}g_{i}\right],}$

y después entrada a la mesa${\displaystyle i}$se actualiza con${\displaystyle g_{i}=\nabla f_{i}(x_{k})}$.

SAGA es uno de los métodos de reducción de varianza más populares debido a su simplicidad, su teoría fácilmente adaptable y su excelente rendimiento. Es el sucesor del método SAG, ^{[ 4 ]} mejorando su flexibilidad y rendimiento.

El método de gradiente reducido de varianza estocástica (SVRG), ^{[ 5 ]} el método de instantánea prototípico, utiliza una actualización similar, excepto que en lugar de usar el promedio de una tabla, utiliza un gradiente completo que se reevalúa en un punto de instantánea.${\displaystyle {\tilde {x}}}$a intervalos regulares de${\displaystyle m\geq n}$iteraciones. La actualización queda así:

${\displaystyle x_{k+1}=x_{k}-\gamma [\nabla f_{i}(x_{k})-\nabla f_{i}({\tilde {x}})+\nabla f({\tilde {x}})],}$

Este enfoque requiere dos evaluaciones de gradiente estocástico por paso, una para calcular${\displaystyle \nabla f_{i}(x_{k})}$y uno para calcular${\displaystyle \nabla f_{i}({\tilde {x}}),}$mientras que los métodos de promedio de tabla solo necesitan uno.

A pesar de su elevado coste computacional, el método SVRG es popular debido a que su sencilla teoría de convergencia se adapta fácilmente a nuevos escenarios de optimización. Además, requiere menos almacenamiento que los métodos de promedio tabular, lo que lo hace aplicable en muchos contextos donde estos últimos no pueden utilizarse.

El método SARAH (gradiente recursivo estocástico) ^{[ 6 ]} mantiene un estimador recursivo del gradiente en lugar de almacenar una tabla de gradientes pasados ​​(como en SAGA) o calcular instantáneas periódicas del gradiente completo (como en SVRG). Al comienzo de un bucle interno, se calcula un gradiente completo en un punto de referencia.${\displaystyle {\tilde {x}}}$:${\displaystyle v_{0}=\nabla f({\tilde {x}})}$Para iteraciones internas, con un índice muestreado${\displaystyle i_{k}}$, el estimador de gradiente y la iteración se actualizan mediante:

${\displaystyle v_{k}=\nabla f_{i_{k}}(x_{k})-\nabla f_{i_{k}}(x_{k-1})+v_{k-1},\qquad x_{k+1}=x_{k}-\gamma v_{k}.}$

Esta recursión requiere dos evaluaciones de gradiente de componentes por paso.${\displaystyle \nabla f_ {i_ {k}}(x_ {k})}$y${\displaystyle \nabla f_{i_{k}}(x_{k-1})}$pero no necesita almacenar gradientes por muestra, lo que resulta en un menor costo de memoria que los métodos de promedio de tablas. SARAH admite convergencia lineal para funciones fuertemente convexas y se ha extendido a problemas compuestos y no convexos más generales. ^{[ 7 ] [ 8 ]}

Aprovechar la representación dual del objetivo conduce a otro enfoque de reducción de varianza que es particularmente adecuado para sumas finitas donde cada término tiene una estructura que hace que el cálculo del conjugado convexo sea más fácil.${\displaystyle f_{i}^{*},}$o su operador proximal tratable. El método SDCA estándar ^{[ 9 ]} considera sumas finitas que tienen una estructura adicional en comparación con la configuración genérica de sumas finitas:

${\displaystyle f(x)={\frac {1}{n}}\sum _{i=1}^{n}f_{i}(x^{T}v_{i})+{\frac {\lambda }{2}}\|x\|^{2},}$

donde cada${\displaystyle f_{i}}$es unidimensional y cada${\displaystyle v_{i}}$es un punto de datos asociado con${\displaystyle f_{i}}$. SDCA resuelve el problema dual:

${\displaystyle \max _{\alpha \in \mathbb {R} ^{n}}-{\frac {1}{n}}\sum _{i=1}^{n}f_{i}^{*}(-\alpha _{i})-{\frac {\lambda }{2}}\left\|{\frac {1}{\lambda n}}\sum _{i=1}^{n}\alpha _{i}v_{i}\right\|^{2},}$

mediante un procedimiento de ascenso de coordenadas estocástico , donde en cada paso el objetivo se optimiza con respecto a una coordenada elegida aleatoriamente.${\displaystyle \alpha _{i}}$, dejando todas las demás coordenadas iguales. Una solución primal aproximada${\displaystyle x}$puede recuperarse de la${\displaystyle \alpha }$valores:

${\displaystyle x={\frac {1}{\lambda n}}\sum _{i=1}^{n}\alpha _{i}v_{i}}$.

Este método obtiene tasas de convergencia teóricas similares a otros métodos estocásticos de reducción de varianza, evitando la necesidad de especificar un parámetro de tamaño de paso. Es rápido en la práctica cuando${\displaystyle \lambda }$es grande, pero significativamente más lento que los otros enfoques cuando${\displaystyle \lambda }$es pequeño.

El marco de trabajo Catalyst ^{[ 11 ]} utiliza cualquiera de los métodos estándar anteriores como optimizador interno para resolver aproximadamente un operador proximal :

${\displaystyle x_{k}\approx {\text{argmin}}_{x}\left\{f(x)+{\frac {\kappa }{2}}\|x-y_{k-1}\|^{2}\right\}}$

Después de lo cual utiliza un paso de extrapolación para determinar el siguiente${\displaystyle y}$:

${\displaystyle y_{k}=x_{k}+\beta _{k}(x_{k}-x_{k-1})}$

La flexibilidad y simplicidad del método catalizador lo convierten en un enfoque básico muy popular. Sin embargo, no alcanza la tasa de convergencia óptima entre los métodos acelerados; puede ser hasta un factor logarítmico más lento en los hiperparámetros.

También se pueden aplicar operaciones proximales directamente a la${\displaystyle f_{i}}$términos para producir un método acelerado. El método Point-SAGA ^{[ 12 ]} reemplaza las operaciones de gradiente en SAGA con evaluaciones de operadores proximales, lo que resulta en un método de aceleración simple y directo:

${\displaystyle x_{k+1}={\text{prox}}_{j}^{\gamma }\left(z_{k}\triangleq x_{k}+\gamma \left[g_{j}-{\frac {1}{n}}\sum _{i=1}^{n}g_{i}\right]\right),}$

con la actualización de la tabla${\displaystyle g_{j}={\frac {1}{\gamma }}(z_{k}-x_{k+1})}$realizado después de cada paso. Aquí${\displaystyle {\text{prox}}_{j}^{\gamma }}$se define como el operador proximal para el${\displaystyle j}$término:

${\displaystyle {\text{prox}}_{j}^{\gamma }(y)={\text{argmin}}_{x}\left\{f_{j}(x)+{\frac {1}{2\gamma }}\|x-y\|^{2}\right\}.}$

A diferencia de otros métodos acelerados conocidos, Point-SAGA requiere solo una secuencia de iteraciones.${\displaystyle x}$debe mantenerse entre pasos, y tiene la ventaja de tener un único parámetro ajustable.${\displaystyle \gamma }$Se obtiene la tasa de convergencia acelerada óptima para la minimización de suma finita fuertemente convexa sin factores logarítmicos adicionales.