Descenso de gradiente vs Adagrad vs Momentum en TensorFlow

La respuesta de Salvador Dalí ya explica las diferencias entre algunos métodos populares (es decir, optimizadores), pero trataría de desarrollarlos un poco más.
(Tenga en cuenta que nuestras respuestas no están de acuerdo sobre algunos puntos, especialmente con respecto a ADAGRAD.)

Momento clásico (CM) vs Gradiente acelerado de Nesterov (NAG)

(Basado principalmente en la sección 2 del documento Sobre la importancia de la inicialización y el impulso en aprendizaje.)

Cada paso tanto en CM como en NAG está realmente compuesto de dos sub-pasos:{[72]]}

• Un sub-paso de momento - Esto es simplemente una fracción (típicamente en el rango [0.9,1)) del último paso.
• Un sub-paso dependiente del gradiente - Esto es como el paso habitual en SGD - es el producto de la tasa de aprendizaje y el vector opuesto al gradiente, mientras que el gradiente se calcula desde donde comienza este sub-paso.

CM toma el gradiente sub-paso primero, mientras que NAG toma el impulso sub-paso primero.

Aquí hay una demostración de una respuesta sobre la intuición para CM y NAG:

Así que NAG parece ser mejor (al menos en la imagen), pero ¿por qué?

Lo importante a tener en cuenta es que no importa cuándo llegue el sub-paso de impulso - sería lo mismo de cualquier manera. Por lo tanto, también podríamos comportarnos si el sub-paso de impulso ya ha sido tomar.

Por lo tanto, la pregunta en realidad es: Suponiendo que el sub-paso del gradiente se toma después del sub-paso del momento, ¿debemos calcular el sub-paso del gradiente como si comenzara en la posición antes o después de tomar el sub-paso del momento?

"After it" parece la respuesta correcta, ya que generalmente, el gradiente en algún punto θ aproximadamente te señala en la dirección desde θ a un mínimo (con la magnitud relativamente correcta), mientras que el gradiente en algún otro punto es menos probable que te apunte en la dirección de θ a un mínimo (con la magnitud relativamente correcta).

Aquí hay una demostración (del gif de abajo):

• El mínimo es donde está la estrella, y las curvas son líneas de contorno. (Para obtener una explicación sobre las líneas de contorno y por qué son perpendiculares al gradiente, vea videos 1 y 2 por el legendario 3Blue1Brown.)
• La flecha púrpura (larga) es el sub-paso de impulso.
• La flecha roja transparente es el sub-paso del gradiente si comienza antes del sub-paso del momento.
• La flecha negra es el sub-paso del gradiente si comienza después del sub-paso del momento.
• CM terminaría en el blanco de la flecha roja oscura.
• NAG terminaría en el objetivo de la flecha negra.

Tenga en cuenta que este argumento de por qué NAG es mejor es independiente si el algoritmo está cerca de un mínimo.
En general, tanto NAG como CM a menudo tienen el problema de acumular más impulso del que es bueno para ellos, por lo que cada vez que deben cambiar de dirección, tienen un "tiempo de respuesta"embarazoso. La ventaja de REGAÑAR sobre CM que explicamos no previene el problema, pero solo hace que el "tiempo de respuesta" de REGAÑAR sea menos embarazoso (pero aún embarazoso).

Este problema de "tiempo de respuesta" está bellamente demostrado en el gif por Alec Radford (que apareció en La respuesta de Salvador Dalí):

ADAGRAD

(Basado principalmente en la sección 2.2.2 en ADADELTA: Un Método de Tasa de Aprendizaje Adaptativo (el documento original de ADADELTA), ya que lo encuentro mucho más accesible que Los Métodos de Subgradientes Adaptativos para el Aprendizaje en Línea y la Optimización Estocástica (el documento original de ADAGRAD).)

              learning_rate 
- --------------------------------------- * gradient_i_t
  norm((gradient_i_1, ..., gradient_i_t))

Mientras que:

• gradient_i_k es el componente i-ésimo del gradiente en el paso k-ésimo
• (gradient_i_1, ..., gradient_i_t) es un vector con componentes t. Esto no es intuitivo (al menos para mí) que construir tal vector tenga sentido, pero eso es lo que hace el algoritmo (conceptualmente).
• norm(vector)es la norma eucldiana (aka l2 norma) de vector, que es nuestra noción intuitiva de longitud de vector.
• Confusamente, en ADAGRAD (así como en algunos otros métodos) la expresión que se multiplica por gradient_i_t (en este caso, learning_rate / norm(...)) a menudo se llama "la tasa de aprendizaje" (de hecho, la llamé "la tasa de aprendizaje real" en el párrafo anterior). Supongo que esto es porque en SGD el learning_rate hiperparámetro y esta expresión son uno y el mismo.
• En una implementación real, se agregaría alguna constante al denominador, para evitar una división por cero.

Por ejemplo, si:

• El i-ésimo componente del gradiente en el primer paso es 1.15
• El i-ésimo componente del gradiente en el segundo paso es 1.35
• El i-ésimo componente del gradiente en el tercer paso es 0.9

Entonces la norma de (1.15, 1.35, 0.9) es la longitud de la línea amarilla, que es:
sqrt(1.15^2 + 1.35^2 + 0.9^2) = 1.989.
Y así el componente i - ésimo del tercer paso es: - learning_rate / 1.989 * 0.9

Tenga en cuenta dos cosas sobre el i-ésimo componente del paso:

1. es proporcional a learning_rate.
2. En los cálculos de la misma, la norma está aumentando, y por lo tanto la tasa de aprendizaje está disminuyendo.

Esto significa que ADAGRAD es sensible a la elección del hiperparámetro learning_rate.
En además, podría ser que después de algún tiempo los pasos se vuelven tan pequeños, que ADAGRAD prácticamente se queda atascado.

ADADELTA y RMSProp

Del documento de ADADELTA :

La idea presentada en este documento se derivó de ADAGRAD con el fin de mejorar los dos principales inconvenientes del método: 1) la decadencia continua de las tasas de aprendizaje a lo largo de la formación, y 2) la necesidad de una selección manual tasa de aprendizaje global.

El papel a continuación, explica una mejora que está destinado a abordar el primer inconveniente:

En lugar de acumular la suma de gradientes cuadrados sobre todos tiempo, restringimos la ventana de gradientes pasados que se acumulan ser un tamaño fijo w [...]. Esto asegura que el aprendizaje continúe para avanzar, incluso después de muchas iteraciones de actualizaciones hecho.
Desde almacenar w gradientes cuadrados anteriores es ineficiente, nuestros métodos implementan esta acumulación como un exponencialmente promedio en descomposición de los gradientes cuadrados.

Por "exponencialmente decayendo el promedio de los gradientes cuadrados" el documento significa que para cada i calculamos un promedio ponderado de todos los componentes cuadrados i-ésos de todos los gradientes que se calcularon.
El peso de cada componente cuadrado i-ésimo es mayor que el peso del componente cuadrado i-ésimo en el paso anterior.

Esta es una aproximación de una ventana de tamaño w porque los pesos en pasos anteriores son muy pequeños.

(Cuando pienso en un promedio en descomposición exponencial, me gusta visualizar el rastro de un cometa, que se vuelve más y más oscuro a medida que se aleja del cometa:

)

Si solo haces este cambio a ADAGRAD, entonces obtendrás RMSProp, que es un método que fue propuesto por Geoff Hinton en Conferencia 6e de su Clase Coursera.

Así que en RMSProp, el componente i-ésimo del paso t - ésimo viene dado por:

                   learning_rate
- ------------------------------------------------ * gradient_i_t
  sqrt(exp_decay_avg_of_squared_grads_i + epsilon)

Mientras que:

• epsilon es un hiperparámetro que impide una división por cero.
• exp_decay_avg_of_squared_grads_i es un promedio en descomposición exponencial de los componentes i-ésos cuadrados de todos los gradientes calculados (incluyendo gradient_i_t).

Pero como se mencionó anteriormente, ADADELTA también tiene como objetivo deshacerse del hiperparámetro learning_rate, por lo que debe haber más cosas sucediendo en él.

En ADADELTA, el componente i-ésimo del paso t - ésimo viene dado por:

  sqrt(exp_decay_avg_of_squared_steps_i + epsilon)
- ------------------------------------------------ * gradient_i_t
  sqrt(exp_decay_avg_of_squared_grads_i + epsilon) 

Mientras que exp_decay_avg_of_squared_steps_i es un promedio en descomposición exponencial de los componentes i-ésimo cuadrados de todos los pasos calculados (hasta el paso t-1-ésimo).
sqrt(exp_decay_avg_of_squared_steps_i + epsilon) es algo similar a momentum, y de acuerdo con el documento, "actúa como un término de aceleración". (El documento también da otra razón de por qué se agregó, pero mi respuesta ya es demasiado larga, así que si tienes curiosidad, echa un vistazo a la sección 3.2.)

Adam

(Basado principalmente en Adam: A Method for Stochastic Optimization, el documento original de Adam.)

Adam es la abreviatura de Adaptive Moment Estimation (ver esta respuesta para una explicación sobre el nombre).
El componente i-ésimo del paso t - ésimo viene dado por:

                   learning_rate
- ------------------------------------------------ * exp_decay_avg_of_grads_i
  sqrt(exp_decay_avg_of_squared_grads_i) + epsilon

Mientras que:

• exp_decay_avg_of_grads_i es un promedio en descomposición exponencial de los componentes i-ésos de todos los gradientes calculados (incluyendo gradient_i_t).
• En realidad, tanto exp_decay_avg_of_grads_i como exp_decay_avg_of_squared_grads_i también se corrigen para tener en cuenta un sesgo hacia 0 (para más información sobre eso, vea la sección 3 en el documento, y también una respuesta en estadísticas.stackexchange ).

Tenga en cuenta que Adam utiliza un promedio en descomposición exponencial de los componentes i-ésimo de los gradientes donde la mayoría de los métodos SGD utilizan el componente i-ésimo del gradiente actual. Esto hace que Adam se comporte como " una bola pesada con fricción", como se explica en el documento GANs Entrenados por una Regla de Actualización de Dos Escalas de Tiempo Convergen a un Equilibrio Local de Nash.
Ver esta respuesta para obtener más información sobre cómo el comportamiento similar al impulso de Adán es diferente del comportamiento similar al impulso habitual.