AdaGrad/es

Article
Topic area	optimization
Prerequisites	Stochastic gradient descent, Gradient, Loss function

Visión general

AdaGrad, abreviatura de Adaptive Gradient Algorithm (algoritmo de gradiente adaptativo), es un método de optimización de primer orden que adapta la tasa de aprendizaje de cada parámetro de forma individual, escalando las actualizaciones de manera inversa a la raíz cuadrada de la suma de todos los cuadrados históricos del gradiente para ese parámetro. Introducido por Duchi, Hazan y Singer en 2011, fue uno de los primeros métodos de tasa de aprendizaje adaptativa ampliamente usados y un antecesor directo de optimizadores modernos como RMSProp, Adadelta y Adam. La intuición motivadora es que las características que aparecen con frecuencia deben recibir actualizaciones más pequeñas, mientras que las características poco frecuentes deben recibir actualizaciones más grandes, lo cual resulta especialmente valioso para datos dispersos como texto en lenguaje natural o flujos de clics.

AdaGrad se sitúa entre el descenso de gradiente estocástico estándar y la familia de optimizadores adaptativos usados para entrenar redes neuronales modernas. Si bien su escalado automático por parámetro reduce la carga del ajuste de la tasa de aprendizaje, la acumulación no acotada de los cuadrados de los gradientes hace que el tamaño de paso efectivo se contraiga monótonamente hacia cero, una propiedad que a veces es deseable en problemas convexos pero que con frecuencia dificulta el entrenamiento de redes profundas. Hoy en día AdaGrad rara vez se usa como optimizador por defecto en aprendizaje profundo, pero sigue siendo importante desde el punto de vista pedagógico y continúa apareciendo en optimización convexa, aprendizaje en línea y entornos de regresión dispersa de alta dimensión.

Motivación e intuición

En el descenso de gradiente estocástico clásico (SGD), todos los parámetros se actualizan con la misma tasa de aprendizaje escalar. Esto es incómodo cuando distintos parámetros requieren magnitudes de actualización diferentes. Considérese un modelo de lenguaje entrenado sobre embeddings de palabras: el embedding de una palabra común como "el" recibe señal de gradiente en casi cada minibatch, mientras que el embedding de una palabra rara puede recibirla solo unas pocas veces a lo largo de toda una época. Usar la misma tasa de aprendizaje para ambos fuerza un compromiso: lo bastante pequeña para mantener estable la palabra común, pero demasiado pequeña entonces para progresar de manera significativa con las palabras raras.

AdaGrad aborda esto otorgando a cada parámetro su propia tasa de aprendizaje que decae en función de cuánta señal de gradiente ha recibido ya ese parámetro. Los parámetros tocados a menudo por gradientes grandes ven reducidos sus tamaños de paso; los parámetros rara vez tocados conservan pasos más grandes. El resultado es un templado implícito de la tasa de aprendizaje adaptado por coordenada, sin necesidad de que el profesional programe los decaimientos manualmente.

El efecto puede entenderse geométricamente. AdaGrad aproxima un precondicionamiento diagonal del gradiente mediante la inversa de la raíz cuadrada de un acumulador de productos exteriores de gradientes pasados. Es un sucedáneo barato de los métodos de segundo orden como el método de Newton, que precondicionan mediante la inversa de la matriz hessiana. Allí donde el método de Newton resulta demasiado costoso para problemas de alta dimensión, AdaGrad ofrece una aproximación por coordenadas que captura algunos de los mismos beneficios de invariancia de escala al coste de un acumulador adicional por parámetro.

Formulación

Sea $ \theta \in \mathbb{R}^d $ el vector de parámetros y $ g_t = \nabla_\theta L_t(\theta_{t-1}) $ el gradiente de la pérdida $ L_t $ en el paso $ t $. AdaGrad mantiene una suma acumulada de los gradientes elevados al cuadrado componente a componente

$ {\displaystyle G_t = \sum_{\tau=1}^{t} g_\tau \odot g_\tau} $

donde $ \odot $ denota el producto componente a componente (de Hadamard). La actualización de los parámetros es

$ {\displaystyle \theta_t = \theta_{t-1} - \frac{\eta}{\sqrt{G_t + \epsilon}} \odot g_t} $

donde $ \eta $ es un tamaño de paso global (a menudo denominado tasa de aprendizaje base) y $ \epsilon $ es una constante pequeña, típicamente $ 10^{-8} $, que evita la división por cero en el primer paso y atenúa las actualizaciones para parámetros cuyos acumuladores aún son pequeños. La raíz cuadrada y la división se toman componente a componente.

De forma equivalente, si escribimos $ G_t = \mathrm{diag}(s_t) $, donde $ s_t \in \mathbb{R}^d $ es la suma acumulada, la actualización para la $ i $-ésima coordenada es

$ {\displaystyle \theta_{t,i} = \theta_{t-1,i} - \frac{\eta}{\sqrt{s_{t,i} + \epsilon}} \, g_{t,i}.} $

El artículo original presenta una variante completa más general con matriz en la que $ G_t $ es el acumulador completo de productos exteriores $ \sum_\tau g_\tau g_\tau^\top $ y la actualización utiliza $ G_t^{-1/2} $. La variante con matriz completa tiene garantías teóricas más fuertes, pero rara vez se usa en la práctica porque almacenar e invertir una matriz $ d \times d $ es inviable cuando $ d $ alcanza millones o miles de millones de parámetros. La variante diagonal descrita arriba es a la que se refieren los profesionales cuando dicen "AdaGrad" sin matizar.

Algoritmo

Una implementación típica para la variante diagonal es directa:

Inicializar:
  theta  := parámetros iniciales
  s      := 0  (vector con la misma forma que theta)
  eta    := tasa de aprendizaje base (por ejemplo, 0.01)
  eps    := 1e-8

Para t = 1, 2, ... hasta la convergencia:
  Muestrear un minibatch y calcular el gradiente g_t
  s := s + g_t * g_t                # acumulación del cuadrado componente a componente
  theta := theta - eta * g_t / (sqrt(s) + eps)

El acumulador $ s $ requiere la misma memoria que el vector de parámetros, por lo que AdaGrad duplica el estado del optimizador en comparación con el SGD simple. En contraste, Adam requiere aproximadamente tres veces la memoria de los parámetros, ya que rastrea estimaciones tanto del primer como del segundo momento.

En frameworks modernos como PyTorch y TensorFlow, AdaGrad está expuesto como un optimizador integrado (torch.optim.Adagrad, tf.keras.optimizers.Adagrad) con perillas opcionales para el valor inicial del acumulador, el decaimiento de la tasa de aprendizaje y el decaimiento de pesos.

Convergencia y arrepentimiento

AdaGrad se analizó originalmente en el marco de la optimización convexa en línea. Para pérdidas convexas con gradientes acotados, la variante diagonal alcanza una cota de arrepentimiento de

$ {\displaystyle R(T) = \sum_{t=1}^{T} L_t(\theta_t) - \min_{\theta^*} \sum_{t=1}^{T} L_t(\theta^*) = O\left(\sqrt{T} \cdot \sum_{i=1}^{d} \sqrt{\sum_{t=1}^{T} g_{t,i}^2}\right).} $

Crucialmente, la suma por coordenadas en el interior hace que esta cota sea mucho más ajustada que la cota correspondiente $ O(\sqrt{dT}) $ para SGD cuando los gradientes son dispersos, porque las coordenadas que rara vez son activas contribuyen poco al total. Este es el enunciado formal de la intuición de que AdaGrad beneficia a los problemas con características dispersas.

Para objetivos no convexos, que incluyen la mayoría de las redes profundas, no existen garantías globales comparables, pero el escalado por coordenadas sigue ofreciendo beneficios prácticos de precondicionamiento, en particular al inicio del entrenamiento, antes de que el acumulador crezca demasiado.

Variantes y sucesores

La acumulación monótona de gradientes al cuadrado de AdaGrad conduce a tamaños de paso cada vez más pequeños, lo que puede detener el entrenamiento antes de que el modelo alcance un buen óptimo. Varios sucesores abordan esto directamente:

• RMSProp (Tieleman y Hinton, 2012) sustituye la suma acumulada por una media móvil exponencial de los gradientes al cuadrado, $ s_t = \rho s_{t-1} + (1-\rho) g_t \odot g_t $. Esto acota inferiormente la tasa de aprendizaje efectiva y recupera la capacidad de hacer actualizaciones grandes si las magnitudes del gradiente cambian.
• Adadelta (Zeiler, 2012) lleva más allá el promediado exponencial de RMSProp normalizando también por una media móvil de las actualizaciones de parámetros pasadas, eliminando la tasa de aprendizaje global $ \eta $ como hiperparámetro.
• Adam (Kingma y Ba, 2014) combina la media móvil de los gradientes al cuadrado de RMSProp con una media móvil separada de los propios gradientes, proporcionando un comportamiento de tipo momento además del escalado por parámetro. Adam es ahora el optimizador dominante en aprendizaje profundo.
• AdaGrad-Norm usa un único acumulador escalar $ s_t = \sum_\tau \|g_\tau\|^2 $ compartido entre todos los parámetros. Esto pierde la adaptación por parámetro pero es más sencillo de analizar y tiene garantías de convergencia limpias para la optimización no convexa.

Otra línea de investigación sobre actualizaciones de AdaGrad disperso también ha producido variantes perezosas que solo tocan las entradas del acumulador correspondientes a coordenadas con gradiente no nulo, una optimización importante para modelos dispersos de muy alta dimensión.

Comparación con otros optimizadores

En comparación con el SGD simple, AdaGrad elimina la necesidad de programaciones de la tasa de aprendizaje manuales en muchos entornos convexos y maneja con elegancia los gradientes dispersos. Su principal desventaja es el estancamiento eventual causado por el crecimiento del acumulador.

En comparación con Adam, AdaGrad es más simple, tiene menos hiperparámetros y usa menos memoria, pero generalmente es más lento y peor para entrenar redes profundas. El promediado exponencial de Adam evita el problema del estancamiento, y su término de momento ayuda a escapar de cañones estrechos en el paisaje de pérdida.

En comparación con los métodos de segundo orden como el método de Newton o L-BFGS, AdaGrad es drásticamente más barato, ya que solo requiere almacenamiento diagonal y operaciones componente a componente, pero ofrece una forma de precondicionamiento mucho más débil.

En la práctica, AdaGrad sigue apareciendo en producción para sistemas de recomendación, predicción de tasa de clics y regresión logística a gran escala, donde las características son altamente dispersas y la formulación convexa se alinea con las fortalezas teóricas de AdaGrad. El algoritmo original FTRL (Follow The Regularized Leader) de Google para la predicción de la CTR de anuncios está estrechamente relacionado y comparte la idea de la acumulación por coordenadas.

Limitaciones

La limitación definitoria de AdaGrad es el decaimiento monótono de la tasa de aprendizaje efectiva. Como $ G_t $ solo crece, el tamaño de paso $ \eta / \sqrt{G_t + \epsilon} $ solo puede contraerse. En entrenamientos largos, especialmente en problemas no convexos donde el modelo necesita hacer ajustes grandes en fases tardías del entrenamiento, este templado agresivo provoca un estancamiento prematuro. RMSProp y Adam se diseñaron precisamente para abordar este problema.

Una cuestión secundaria es la sensibilidad a la tasa de aprendizaje base $ \eta $. Aunque AdaGrad reduce la sensibilidad al escalado de la tasa de aprendizaje por parámetro, sigue siendo sensible a la escala global, y un $ \eta $ mal elegido puede provocar actualizaciones explosivas al principio o un progreso demasiado lento.

Por último, el precondicionamiento de AdaGrad es puramente diagonal: no puede dar cuenta de las correlaciones entre parámetros. Los problemas en los que las dimensiones de los parámetros están fuertemente acopladas, como los que surgen en sistemas lineales mal condicionados, pueden no beneficiarse sustancialmente de AdaGrad en relación con un SGD con momento bien ajustado.

Aplicaciones

El asidero práctico más fuerte de AdaGrad se encuentra en problemas convexos con características dispersas de alta dimensión:

• Predicción de la tasa de clics y otros modelos de regresión logística a gran escala en publicidad y sistemas de recomendación.
• Modelos dispersos de procesamiento del lenguaje natural, en particular clasificadores bolsa de palabras y de n-gramas, donde la mayoría de las características son cero en cualquier ejemplo dado.
• Entrenamiento de embeddings de palabras en las primeras implementaciones de word2vec y modelos similares, donde los embeddings de palabras raras se benefician de actualizaciones grandes.
• Aprendizaje en línea en entornos donde los datos llegan secuencialmente y la adaptación por coordenada es más importante que un diseño cuidadoso de la programación.

Para las cargas de trabajo modernas de aprendizaje profundo, AdaGrad ha sido ampliamente desplazado por Adam, AdamW y métodos relacionados, aunque sigue siendo un punto de entrada pedagógicamente útil y una línea base sensata para nuevos problemas convexos.