El descenso de gradiente proximal follow-the-regularized-leader utiliza este paso de actualización:
$$ w_ {t + 1} = argmin_w (w \ cdot \ sum_ {s = 1} ^ t g_s + \ frac {1} {2} \ sum_ {s = 1} ^ t \ sigma_s (w-w_s) ^ 2 + \ lambda_1 | w |) $$
-
Estamos en la ronda $ t + 1 $, ya hemos visto puntos de datos $ t $ .
-
$ g_s $ es el gradiente de la muestra $ s $.
-
$ \ sigma_s $ es una tasa de aprendizaje que no aumenta, definida como $ \ sum_ {s = 1} ^ t \ sigma_s = \ sqrt {t} $
-
y finalmente $ \ lambda_1 $ es un término de regularización.
¿Puede darnos una intuición simple geométrica / física / de otro tipo de lo que estamos haciendo con los primeros 2 términos? ¿El primero representa algún tipo de impulso? ¿El segundo requiere que nuestra nueva ubicación sea diferente a nuestras ubicaciones anteriores?
Tenga paciencia si esto le parece un intento de simplificar demasiado una teoría pesada …
Respuesta
Siguiendo McMahan» Seguir al líder regularizado y descendencia espejo: teoremas de equivalencia .
El artículo muestra que la regla de actualización de descenso de gradiente simple se puede escribir de una manera muy similar a la regla anterior.
La regla de actualización intuitiva de FOBOS (una variante de descenso de gradiente) es:
$$ x_ {t + 1} = argmin_x [g_tx + \ frac {1} {2 \ mu_t} | x-x_t | ^ 2] $$
donde
- $ g_t $ es el gradiente de la muestra anterior $ t $ – queremos movernos en esa dirección ya que disminuye la pérdida de nuestra hipótesis en esa muestra.
- Sin embargo, no queremos cambiar nuestra hipótesis $ x_t $ demasiado (por temor a predecir mal en ejemplos que ya hemos visto). $ \ mu_t $ es un tamaño de paso para esta muestra, y debería hacer que cada paso sea más conservador.
Podemos encontrar dónde la derivada es 0 y obtener una regla de actualización explícita:
$$ x_ {t + 1} = x_t- \ mu_tg_t $$
El documento continúa mostrando que la misma regla de actualización intuitiva anterior también se puede escribir como:
$$ x_ {t + 1} = argmin_x [g_ {1: t} x + \ phi_ {1: t-1} x + \ psi (x) + \ frac {1} {2} \ sum_ {s = 1} ^ t {| x-x_s | ^ 2}] $$
Que es bastante similar a la formulación proximal de FTRL. De hecho, la parte del gradiente (1er término) y la convexidad fuerte proximal (3er término) son las mismas, y estas fueron las partes interesantes para mí.
Comentarios
- A medida que el documento entra en detalles técnicos que estaban fuera de mi alcance, me complacería que alguien pudiera verificar esta respuesta y asegurarse de que esta explicación tiene sentido …
Respuesta
para FOBOS, la formulación original es básicamente una extensión de SGD: http://stanford.edu/~jduchi/projects/DuchiSi09c_slides.pdf
el documento FTRL intenta brindar una vista unificada formulando el formato cerrado de Duchi actualizar de manera similar a FTRL. el término g * x (también mencionado en la respuesta de ihadanny) es un poco extraño, pero si trabaja desde el pdf anterior, es bastante claro:
en la página 8 del pdf anterior, si ignoramos el término de regularización R por ahora,
$$ \ begin {eqnarray} \ mathbf {w} _ {t + 1} & = & argmin _ {\ mathbf {w}} \ {\ frac {1} {2} \ | \ mathbf {w} – \ mathbf {w} _ {t + 1/2} \ | ^ 2 \} \\ & = & argmin _ {\ mathbf {w}} \ {\ frac {1} {2} \ | \ mathbf {w} – (\ mathbf {w} _ {t} – \ eta \ mathbf {g} _t) \ | ^ 2 \} \ mbox {considerando la página 7 del pdf de Duchi} \\ & = & (\ mathbf {w} – \ mathbf {w} _t) ^ t (\ mathbf {w} – \ mathbf {w} _t) + 2 \ eta (\ mathbf {w} – \ mathbf {w} _t) ^ t \ mathbf {g} _t + \ eta ^ 2 \ mathbf {g} _t ^ t \ mathbf {g} _t \ end {eqnarray} $$
$ \ mathbf {w} _t $ y $ \ mathbf {g} _t $ anteriores son todas constantes para el argmin, por lo que se ignoran, entonces tienes la forma dada por ihadanny
la forma $ \ mathbf {w} \ mathbf {g} _t $ tiene sentido (después de la derivación de equivalencia anterior de la forma Duchi), pero en esta forma es muy poco intuitiva, y aún más lo es la forma $ \ mathbf {g} _ {1: t} \ mathbf {w} $ formulario en el papel FTRL. para comprender la fórmula FTRL en la forma más intuitiva de Duchi, tenga en cuenta que la principal diferencia entre FTRL y FOBOS es simplemente $ \ mathbf {g} _ {1: t} $ -> $ \ mathbf {g} _ {t} $ (vea https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37013.pdf nota que en realidad hay un error tipográfico para FOBOS en la tabla de la página 2, debe consultar el ecuaciones en los párrafos) luego simplemente cambie $ \ mathbf {g} _ {t} $ a $ \ mathbf {g} _ {1: t} $ en la derivación de equivalencia anterior, y encontrará que FTRL es básicamente el cerrado- formule la actualización de FOBOS con un valor más «conservador» para el valor de $ \ mathbf {g} _ {t} $ utilizando el promedio de $ \ mathbf {g} _ {1: t} $