Adam: A Method for Stochastic Optimization/paper/es

SummarySource

Research Paper
Authors	Diederik P. Kingma; Jimmy Ba
Year	2014
Topic area	Machine Learning
Difficulty	Research
arXiv	1412.6980
PDF	Download PDF

Publicado como artículo de conferencia en ICLR 2015 ADAM: UN MÉTODO PARA LA OPTIMIZACIÓN ESTOCÁSTICA Diederik P. Kingma* University of Amsterdam, OpenAI dpkingma@openai.com Jimmy Lei Ba∗ University of Toronto jimmy@psi.utoronto.ca ## RESUMEN Presentamos Adam, un algoritmo para la optimización basada en gradientes de primer orden de funciones objetivo estocásticas, basado en estimaciones adaptativas de momentos de orden inferior. El método es sencillo de implementar, es computacionalmente eficiente, requiere poca memoria, es invariante al reescalado diagonal de los gradientes y es muy adecuado para problemas que son grandes en términos de datos y/o parámetros. El método también es apropiado para objetivos no estacionarios y problemas con gradientes muy ruidosos y/o dispersos. Los hiperparámetros tienen interpretaciones intuitivas y normalmente requieren poco ajuste. Se discuten algunas conexiones con algoritmos relacionados, en los que Adam se inspiró. También analizamos las propiedades teóricas de convergencia del algoritmo y proporcionamos una cota de arrepentimiento sobre la tasa de convergencia que es comparable a los mejores resultados conocidos bajo el marco de optimización convexa en línea. Los resultados empíricos demuestran que Adam funciona bien en la práctica y se compara favorablemente con otros métodos de optimización estocástica. Por último, discutimos AdaMax, una variante de Adam basada en la norma infinito. 1 ## INTRODUCCIÓN La optimización estocástica basada en gradientes es de importancia práctica fundamental en muchos campos de la ciencia y la ingeniería. Muchos problemas en estos campos pueden plantearse como la optimización de alguna función objetivo escalar parametrizada que requiere maximización o minimización con respecto a sus parámetros. Si la función es diferenciable con respecto a sus parámetros, el descenso de gradiente es un método de optimización relativamente eficiente, ya que el cálculo de las derivadas parciales de primer orden con respecto a todos los parámetros tiene la misma complejidad computacional que la mera evaluación de la función. A menudo, las funciones objetivo son estocásticas. Por ejemplo, muchas funciones objetivo se componen de una suma de subfunciones evaluadas en diferentes submuestras de datos; en este caso, la optimización puede hacerse más eficiente tomando pasos de gradiente con respecto a las subfunciones individuales, es decir, descenso de gradiente estocástico (SGD) o ascenso. SGD demostró ser un método de optimización eficiente y eficaz que fue central en muchos casos de éxito del aprendizaje automático, como los avances recientes en aprendizaje profundo (Deng et al., 2013; Krizhevsky et al., 2012; Hinton & Salakhutdinov, 2006; Hinton et al., 2012a; Graves et al., 2013). Los objetivos también pueden tener otras fuentes de ruido distintas del submuestreo de datos, como la regularización con dropout (Hinton et al., 2012b). Para todos estos objetivos ruidosos, se requieren técnicas eficientes de optimización estocástica. El enfoque de este artículo está en la optimización de objetivos estocásticos con espacios de parámetros de alta dimensión. En estos casos, los métodos de optimización de orden superior no son adecuados, y la discusión en este artículo se restringirá a los métodos de primer orden. Proponemos Adam, un método para la optimización estocástica eficiente que solo requiere gradientes de primer orden con un requisito de memoria reducido. El método calcula tasas de aprendizaje adaptativas individuales para diferentes parámetros a partir de estimaciones del primer y segundo momento de los gradientes; el nombre Adam se deriva de adaptive moment estimation (estimación adaptativa de momentos). Nuestro método está diseñado para combinar las ventajas de dos métodos populares recientemente: AdaGrad (Duchi et al., 2011), que funciona bien con gradientes dispersos, y RMSProp (Tieleman & Hinton, 2012), que funciona bien en entornos en línea y no estacionarios; en la sección 5 se aclaran conexiones importantes con estos y otros métodos de optimización estocástica. Algunas de las ventajas de Adam son que las magnitudes de las actualizaciones de los parámetros son invariantes al reescalado del gradiente, sus tamaños de paso están aproximadamente acotados por el hiperparámetro de tamaño de paso, no requiere un objetivo estacionario, funciona con gradientes dispersos y realiza de forma natural una forma de templado del tamaño de paso. ∗Contribución equitativa. El orden de los autores se determinó mediante el lanzamiento de una moneda en un Google Hangout. 1 arXiv:1412.6980v9 [cs.LG] 30 Jan 2017

Publicado como artículo de conferencia en ICLR 2015 Algoritmo 1: Adam, nuestro algoritmo propuesto para la optimización estocástica. Véase la sección 2 para los detalles, y para un orden de cómputo ligeramente más eficiente (pero menos claro). g2 t indica el cuadrado elemento a elemento gt ⊙gt. Buenos valores por defecto para los problemas de aprendizaje automático evaluados son α = 0.001, β1 = 0.9, β2 = 0.999 y ϵ = 10−8. Todas las operaciones sobre vectores son elemento a elemento. Con βt 1 y βt 2 denotamos β1 y β2 elevados a la potencia t. Require: α: Tamaño de paso Require: β1, β2 ∈[0, 1): Tasas de decaimiento exponencial para las estimaciones de los momentos Require: f(θ): Función objetivo estocástica con parámetros θ Require: θ0: Vector de parámetros inicial m0 ←0 (Inicializar el vector del primer momento) v0 ←0 (Inicializar el vector del segundo momento) t ←0 (Inicializar el paso de tiempo) while θt no haya convergido do t ←t + 1 gt ←∇θft(θt−1) (Obtener gradientes con respecto al objetivo estocástico en el paso de tiempo t) mt ←β1 · mt−1 + (1 −β1) · gt (Actualizar la estimación sesgada del primer momento) vt ←β2 · vt−1 + (1 −β2) · g2 t (Actualizar la estimación sesgada del segundo momento bruto) bmt ←mt/(1 −βt 1) (Calcular la estimación corregida en sesgo del primer momento) bvt ←vt/(1 −βt 2) (Calcular la estimación corregida en sesgo del segundo momento bruto) θt ←θt−1 −α · bmt/(√bvt + ϵ) (Actualizar parámetros) end while return θt (Parámetros resultantes) En la sección 2 describimos el algoritmo y las propiedades de su regla de actualización. La sección 3 explica nuestra técnica de corrección del sesgo de inicialización, y la sección 4 proporciona un análisis teórico de la convergencia de Adam en programación convexa en línea. Empíricamente, nuestro método supera consistentemente a otros métodos para una variedad de modelos y conjuntos de datos, como se muestra en la sección 6. En general, mostramos que Adam es un algoritmo versátil que escala a problemas de aprendizaje automático de alta dimensión a gran escala. 2 ## ALGORITMO Véase el algoritmo 1 para el pseudocódigo de nuestro algoritmo propuesto Adam. Sea f(θ) una función objetivo ruidosa: una función escalar estocástica que es diferenciable con respecto a los parámetros θ. Estamos interesados en minimizar el valor esperado de esta función, E[f(θ)] con respecto a sus parámetros θ. Con f1(θ), …, , fT (θ) denotamos las realizaciones de la función estocástica en pasos de tiempo sucesivos 1, …, T. La estocasticidad puede provenir de la evaluación en submuestras aleatorias (minilotes) de puntos de datos, o surgir del ruido inherente de la función. Con gt = ∇θft(θ) denotamos el gradiente, es decir, el vector de derivadas parciales de ft, con respecto a θ evaluado en el paso de tiempo t. El algoritmo actualiza promedios móviles exponenciales del gradiente (mt) y del gradiente al cuadrado (vt) donde los hiperparámetros β1, β2 ∈[0, 1) controlan las tasas de decaimiento exponencial de estos promedios móviles. Los propios promedios móviles son estimaciones del primer momento (la media) y del segundo momento bruto (la varianza no centrada) del gradiente. Sin embargo, estos promedios móviles se inicializan como (vectores de) 0, lo que conduce a estimaciones de momentos sesgadas hacia cero, especialmente durante los pasos de tiempo iniciales, y especialmente cuando las tasas de decaimiento son pequeñas (es decir, las β están cerca de 1). La buena noticia es que este sesgo de inicialización puede contrarrestarse fácilmente, dando lugar a estimaciones corregidas en sesgo bmt y bvt. Véase la sección 3 para más detalles. Nótese que la eficiencia del algoritmo 1 puede mejorarse, a costa de la claridad, cambiando el orden de cómputo, por ejemplo, reemplazando las últimas tres líneas en el bucle por las siguientes líneas: αt = α · p 1 −βt 2/(1 −βt 1) y θt ←θt−1 −αt · mt/(√vt + ˆϵ). 2.1 LA REGLA DE ACTUALIZACIÓN DE ADAM Una propiedad importante de la regla de actualización de Adam es su elección cuidadosa de los tamaños de paso. Asumiendo ϵ = 0, el paso efectivo dado en el espacio de parámetros en el paso de tiempo t es ∆t = α · bmt/√bvt. El tamaño de paso efectivo tiene dos cotas superiores: |∆t| ≤α · (1 −β1)/√1 −β2 en el caso (1 −β1) > √1 −β2, y |∆t| ≤α 2

Publicado como artículo de conferencia en ICLR 2015 en caso contrario. El primer caso solo ocurre en el caso más severo de dispersión: cuando un gradiente ha sido cero en todos los pasos de tiempo excepto en el paso de tiempo actual. Para casos menos dispersos, el tamaño de paso efectivo será menor. Cuando (1 −β1) = √1 −β2 tenemos que | bmt/√bvt| < 1, por lo tanto |∆t| < α. En escenarios más comunes, tendremos que bmt/√bvt ≈±1 dado que |E[g]/ p E[g2]| ≤1. La magnitud efectiva de los pasos dados en el espacio de parámetros en cada paso de tiempo está aproximadamente acotada por el ajuste del tamaño de paso α, es decir, |∆t| ⪅α. Esto puede entenderse como el establecimiento de una región de confianza alrededor del valor actual del parámetro, más allá de la cual la estimación actual del gradiente no proporciona información suficiente. Esto típicamente facilita conocer la escala correcta de α de antemano. Para muchos modelos de aprendizaje automático, por ejemplo, a menudo sabemos de antemano que los buenos óptimos están con alta probabilidad dentro de alguna región establecida en el espacio de parámetros; no es raro, por ejemplo, tener una distribución a priori sobre los parámetros. Dado que α establece (una cota superior de) la magnitud de los pasos en el espacio de parámetros, a menudo podemos deducir el orden de magnitud correcto de α de modo que los óptimos puedan alcanzarse desde θ0 dentro de cierto número de iteraciones. Con un ligero abuso de terminología, llamaremos a la razón bmt/√bvt la relación señal-ruido (SNR). Con un SNR menor, el tamaño de paso efectivo ∆t estará más cerca de cero. Esta es una propiedad deseable, ya que un SNR menor significa que hay mayor incertidumbre sobre si la dirección de bmt corresponde a la dirección del gradiente verdadero. Por ejemplo, el valor del SNR típicamente se acerca a 0 hacia un óptimo, lo que conduce a pasos efectivos menores en el espacio de parámetros: una forma de templado automático. El tamaño de paso efectivo ∆t también es invariante a la escala de los gradientes; reescalar los gradientes g con un factor c escalará bmt con un factor c y bvt con un factor c2, los cuales se cancelan: (c · bmt)/(√ c2 · bvt) = bmt/√bvt. 3 ## CORRECCIÓN DEL SESGO DE INICIALIZACIÓN Como se explicó en la sección 2, Adam utiliza términos de corrección del sesgo de inicialización. Aquí derivaremos el término para la estimación del segundo momento; la derivación para la estimación del primer momento es completamente análoga. Sea g el gradiente del objetivo estocástico f, y deseamos estimar su segundo momento bruto (varianza no centrada) usando un promedio móvil exponencial del gradiente al cuadrado, con tasa de decaimiento β2. Sean g1, …, gT los gradientes en pasos de tiempo sucesivos, cada uno una extracción de una distribución de gradiente subyacente gt ∼p(gt). Inicialicemos el promedio móvil exponencial como v0 = 0 (un vector de ceros). Primero, nótese que la actualización en el paso de tiempo t del promedio móvil exponencial vt = β2 · vt−1 + (1 −β2) · g2 t (donde g2 t indica el cuadrado elemento a elemento gt ⊙gt) puede escribirse como una función de los gradientes en todos los pasos de tiempo previos: vt = (1 −β2) t X i=1 βt−i 2 · g2 i (1) Deseamos saber cómo E[vt], el valor esperado del promedio móvil exponencial en el paso de tiempo t, se relaciona con el verdadero segundo momento E[g2 t ], para poder corregir la discrepancia entre los dos. Tomando esperanzas de los lados izquierdo y derecho de la ec. (1): E[vt] = E ” (1 −β2) t X i=1 βt−i 2 · g2 i # (2) = E[g2 t ] · (1 −β2) t X i=1 βt−i 2 + ζ (3) = E[g2 t ] · (1 −βt 2) + ζ (4) donde ζ = 0 si el verdadero segundo momento E[g2 i ] es estacionario; en caso contrario, ζ puede mantenerse pequeño dado que la tasa de decaimiento exponencial β1 puede (y debería) elegirse de modo que el promedio móvil exponencial asigne pesos pequeños a gradientes demasiado lejanos en el pasado. Lo que queda es el término (1 −βt 2) que es causado por inicializar el promedio móvil con ceros. En el algoritmo 1, por lo tanto, dividimos por este término para corregir el sesgo de inicialización. En el caso de gradientes dispersos, para una estimación fiable del segundo momento es necesario promediar sobre muchos gradientes eligiendo un valor pequeño de β2; sin embargo, es exactamente este caso de β2 pequeño donde la falta de corrección del sesgo de inicialización conduciría a pasos iniciales que son mucho mayores. 3

Publicado como artículo de conferencia en ICLR 2015 4 ## ANÁLISIS DE CONVERGENCIA Analizamos la convergencia de Adam usando el marco de aprendizaje en línea propuesto en (Zinkevich, 2003). Dada una secuencia arbitraria y desconocida de funciones de costo convexas f1(θ), f2(θ),…, fT (θ). En cada tiempo t, nuestro objetivo es predecir el parámetro θt y evaluarlo en una función de costo ft previamente desconocida. Dado que la naturaleza de la secuencia es desconocida de antemano, evaluamos nuestro algoritmo usando el arrepentimiento, que es la suma de todas las diferencias previas entre la predicción en línea ft(θt) y el mejor parámetro de punto fijo ft(θ∗) de un conjunto factible X para todos los pasos previos. Concretamente, el arrepentimiento se define como: R(T) = T X t=1 [ft(θt) −ft(θ∗)] (5) donde θ∗= arg minθ∈X PT t=1 ft(θ). Mostramos que Adam tiene una cota de arrepentimiento O( √ T) y se da una demostración en el apéndice. Nuestro resultado es comparable a la mejor cota conocida para este problema general de aprendizaje convexo en línea. También usamos algunas definiciones para simplificar nuestra notación, donde gt ≜∇ft(θt) y gt,i como el i-ésimo elemento. Definimos g1:t,i ∈Rt como un vector que contiene la i-ésima dimensión de los gradientes a lo largo de todas las iteraciones hasta t, g1:t,i = [g1,i, g2,i, · · · , gt,i]. Asimismo, definimos γ ≜ β2 1 √β2 . Nuestro siguiente teorema se cumple cuando la tasa de aprendizaje αt está decayendo a una tasa de t−1 2 y el coeficiente del promedio móvil del primer momento β1,t decae exponencialmente con λ, que es típicamente cercano a 1, por ejemplo, 1 −10−8. Teorema 4.1. Asumamos que la función ft tiene gradientes acotados, ∥∇ft(θ)∥2 ≤G, ∥∇ft(θ)∥∞≤ G∞para todo θ ∈Rd y la distancia entre cualquier θt generado por Adam está acotada, ∥θn −θm∥2 ≤D, ∥θm −θn∥∞≤D∞para cualesquiera m, n ∈{1, …, T}, y β1, β2 ∈[0, 1) satisfacen β2 1 √β2 < 1. Sea αt = α √ t y β1,t = β1λt−1, λ ∈(0, 1). Adam alcanza la siguiente garantía, para todo T ≥1. R(T) ≤ D2 2α(1 −β1) d X i=1 p TbvT,i+ α(1 + β1)G∞ (1 −β1)√1 −β2(1 −γ)2 d X i=1 ∥g1:T,i∥2+ d X i=1 D2 ∞G∞ √1 −β2 2α(1 −β1)(1 −λ)2 Nuestro Teorema 4.1 implica que cuando las características de los datos son dispersas y los gradientes están acotados, el término de la sumatoria puede ser mucho menor que su cota superior Pd i=1 ∥g1:T,i∥2 << dG∞ √ T y Pd i=1 p TbvT,i << dG∞ √ T, en particular si la clase de función y las características de los datos están en la forma de la sección 1.2 en (Duchi et al., 2011). Sus resultados para el valor esperado E[Pd i=1 ∥g1:T,i∥2] también se aplican a Adam. En particular, el método adaptativo, como Adam y AdaGrad, puede alcanzar O(log d √ T), una mejora respecto a O( √ dT) del método no adaptativo. Decaer β1,t hacia cero es importante en nuestro análisis teórico y también coincide con hallazgos empíricos previos, por ejemplo, (Sutskever et al., 2013) sugiere que reducir el coeficiente de momento al final del entrenamiento puede mejorar la convergencia. Finalmente, podemos demostrar que el arrepentimiento promedio de Adam converge, Corolario 4.2. Asumamos que la función ft tiene gradientes acotados, ∥∇ft(θ)∥2 ≤G, ∥∇ft(θ)∥∞≤ G∞para todo θ ∈Rd y la distancia entre cualquier θt generado por Adam está acotada, ∥θn −θm∥2 ≤D, ∥θm −θn∥∞≤D∞para cualesquiera m, n ∈{1, …, T}. Adam alcanza la siguiente garantía, para todo T ≥1. R(T) T = O( 1 √ T ) Este resultado puede obtenerse usando el Teorema 4.1 y Pd i=1 ∥g1:T,i∥2 ≤dG∞ √ T. Por lo tanto, limT →∞ R(T ) T = 0. 5 ## TRABAJO RELACIONADO Los métodos de optimización que tienen una relación directa con Adam son RMSProp (Tieleman & Hinton, 2012; Graves, 2013) y AdaGrad (Duchi et al., 2011); estas relaciones se discuten a continuación. Otros métodos de optimización estocástica incluyen vSGD (Schaul et al., 2012), AdaDelta (Zeiler, 2012) y el método natural de Newton de Roux & Fitzgibbon (2010), todos los cuales establecen tamaños de paso estimando la curvatura 4

Publicado como artículo de conferencia en ICLR 2015 a partir de información de primer orden. El Sum-of-Functions Optimizer (SFO) (Sohl-Dickstein et al., 2014) es un método quasi-Newton basado en minilotes, pero (a diferencia de Adam) tiene requisitos de memoria lineales en el número de particiones de minilote de un conjunto de datos, lo cual es a menudo inviable en sistemas con memoria limitada como una GPU. Al igual que el descenso de gradiente natural (NGD) (Amari, 1998), Adam emplea un precondicionador que se adapta a la geometría de los datos, dado que bvt es una aproximación de la diagonal de la matriz de información de Fisher (Pascanu & Bengio, 2013); sin embargo, el precondicionador de Adam (como el de AdaGrad) es más conservador en su adaptación que el NGD vanilla, al precondicionar con la raíz cuadrada de la inversa de la aproximación de la diagonal de la matriz de información de Fisher. RMSProp: Un método de optimización estrechamente relacionado con Adam es RMSProp (Tieleman & Hinton, 2012). A veces se ha utilizado una versión con momento (Graves, 2013). Existen algunas diferencias importantes entre RMSProp con momento y Adam: RMSProp con momento genera sus actualizaciones de parámetros usando un momento sobre el gradiente reescalado, mientras que las actualizaciones de Adam se estiman directamente usando un promedio móvil del primer y segundo momento del gradiente. RMSProp también carece de un término de corrección de sesgo; esto importa más en el caso de un valor de β2 cercano a 1 (requerido en caso de gradientes dispersos), ya que en ese caso no corregir el sesgo conduce a tamaños de paso muy grandes y a menudo a divergencia, como también demostramos empíricamente en la sección 6.4. AdaGrad: Un algoritmo que funciona bien para gradientes dispersos es AdaGrad (Duchi et al., 2011). Su versión básica actualiza los parámetros como θt+1 = θt −α · gt/ qPt i=1 g2 t . Nótese que si elegimos β2 infinitesimalmente cercano a 1 desde abajo, entonces limβ2→1 bvt = t−1 · Pt i=1 g2 t . AdaGrad corresponde a una versión de Adam con β1 = 0, (1 −β2) infinitesimal y un reemplazo de α por una versión templada αt = α · t−1/2, a saber, θt −α · t−1/2 · bmt/ p limβ2→1 bvt = θt −α · t−1/2 · gt/ q t−1 · Pt i=1 g2 t = θt −α · gt/ qPt i=1 g2 t . Nótese que esta correspondencia directa entre Adam y AdaGrad no se cumple cuando se eliminan los términos de corrección de sesgo; sin corrección de sesgo, como en RMSProp, un β2 infinitesimalmente cercano a 1 conduciría a un sesgo infinitamente grande y a actualizaciones de parámetros infinitamente grandes. 6 ## EXPERIMENTOS Para evaluar empíricamente el método propuesto, investigamos diferentes modelos populares de aprendizaje automático, incluyendo regresión logística, redes neuronales totalmente conectadas multicapa y redes neuronales convolucionales profundas. Usando modelos y conjuntos de datos grandes, demostramos que Adam puede resolver eficientemente problemas prácticos de aprendizaje profundo. Usamos la misma inicialización de parámetros al comparar diferentes algoritmos de optimización. Los hiperparámetros, como la tasa de aprendizaje y el momento, se buscan sobre una rejilla densa y los resultados se reportan usando el mejor ajuste de hiperparámetro. 6.1 EXPERIMENTO: REGRESIÓN LOGÍSTICA Evaluamos nuestro método propuesto en regresión logística multiclase con regularización L2 usando el conjunto de datos MNIST. La regresión logística tiene un objetivo convexo bien estudiado, lo que la hace adecuada para la comparación de diferentes optimizadores sin preocuparse por problemas de mínimos locales. El tamaño de paso α en nuestros experimentos de regresión logística se ajusta mediante decaimiento 1/√t, a saber, αt = α √ t que coincide con nuestra predicción teórica de la sección 4. La regresión logística clasifica la etiqueta de clase directamente sobre los vectores de imagen de 784 dimensiones. Comparamos Adam con SGD acelerado con momento de Nesterov y AdaGrad usando un tamaño de minilote de 128. Según la Figura 1, encontramos que Adam produce una convergencia similar a SGD con momento y ambos convergen más rápido que AdaGrad. Como se discute en (Duchi et al., 2011), AdaGrad puede manejar eficientemente características y gradientes dispersos como uno de sus principales resultados teóricos, mientras que SGD es deficiente en aprender características raras. Adam con decaimiento 1/√t en su tamaño de paso debería, en teoría, igualar el desempeño de AdaGrad. Examinamos el problema de características dispersas usando el conjunto de datos de reseñas de películas IMDB de (Maas et al., 2011). Preprocesamos las reseñas de películas IMDB en vectores de características de bolsa de palabras (BoW) que incluyen las primeras 10.000 palabras más frecuentes. El vector de características BoW de 10.000 dimensiones para cada reseña es altamente disperso. Como se sugiere en (Wang & Manning, 2013), se puede aplicar un 50% de ruido de dropout a las características BoW durante 5

Publicado como artículo de conferencia en ICLR 2015 0 5 10 15 20 25 30 35 40 45 iteraciones sobre todo el conjunto de datos 0.2 0.3 0.4 0.5 0.6 0.7 costo de entrenamiento MNIST Regresión logística AdaGrad SGDNesterov Adam 0 20 40 60 80 100 120 140 160 iteraciones sobre todo el conjunto de datos 0.20 0.25 0.30 0.35 0.40 0.45 0.50 costo de entrenamiento IMDB BoW característica Regresión logística AdaGrad+dropout RMSProp+dropout SGDNesterov+dropout Adam+dropout Figura 1: log-verosimilitud negativa de entrenamiento de regresión logística sobre imágenes MNIST y reseñas de películas IMDB con vectores de características de bolsa de palabras (BoW) de 10.000 dimensiones. el entrenamiento para evitar el sobreajuste. En la figura 1, AdaGrad supera a SGD con momento de Nesterov por un amplio margen, tanto con como sin ruido de dropout. Adam converge tan rápido como AdaGrad. El desempeño empírico de Adam es consistente con nuestros hallazgos teóricos de las secciones 2 y 4. De manera similar a AdaGrad, Adam puede aprovechar las características dispersas y obtener una tasa de convergencia más rápida que el SGD normal con momento. 6.2 EXPERIMENTO: REDES NEURONALES MULTICAPA Las redes neuronales multicapa son modelos potentes con funciones objetivo no convexas. Aunque nuestro análisis de convergencia no se aplica a problemas no convexos, encontramos empíricamente que Adam a menudo supera a otros métodos en tales casos. En nuestros experimentos, hicimos elecciones de modelo consistentes con publicaciones previas en el área; un modelo de red neuronal con dos capas ocultas totalmente conectadas con 1000 unidades ocultas cada una y activación ReLU se utiliza para este experimento con un tamaño de minilote de 128. Primero, estudiamos diferentes optimizadores usando la función objetivo determinista estándar de entropía cruzada con decaimiento de pesos L2 sobre los parámetros para evitar el sobreajuste. El método sum-of-functions (SFO) (Sohl-Dickstein et al., 2014) es un método quasi-Newton recientemente propuesto que funciona con minilotes de datos y ha mostrado un buen desempeño en la optimización de redes neuronales multicapa. Usamos su implementación y la comparamos con Adam para entrenar tales modelos. La Figura 2 muestra que Adam avanza más rápido tanto en términos del número de iteraciones como del tiempo de reloj. Debido al costo de actualizar la información de curvatura, SFO es 5-10 veces más lento por iteración en comparación con Adam, y tiene un requisito de memoria que es lineal en el número de minilotes. Los métodos estocásticos de regularización, como dropout, son una forma efectiva de prevenir el sobreajuste y a menudo se usan en la práctica debido a su simplicidad. SFO supone subfunciones deterministas y, de hecho, no logró converger sobre funciones de costo con regularización estocástica. Comparamos la efectividad de Adam con otros métodos estocásticos de primer orden en redes neuronales multicapa entrenadas con ruido de dropout. La Figura 2 muestra nuestros resultados; Adam muestra una mejor convergencia que otros métodos. 6.3 EXPERIMENTO: REDES NEURONALES CONVOLUCIONALES Las redes neuronales convolucionales (CNN) con varias capas de convolución, pooling y unidades no lineales han mostrado un éxito considerable en tareas de visión por computador. A diferencia de la mayoría de las redes neuronales totalmente conectadas, el compartir pesos en las CNN da como resultado gradientes muy diferentes en distintas capas. A menudo se utiliza una tasa de aprendizaje más pequeña para las capas de convolución en la práctica al aplicar SGD. Mostramos la efectividad de Adam en CNN profundas. Nuestra arquitectura CNN tiene tres etapas alternantes de filtros de convolución de 5x5 y pooling máximo de 3x3 con paso de 2 que son seguidas por una capa totalmente conectada de 1000 unidades ocultas lineales rectificadas (ReLU). Las imágenes de entrada se preprocesan mediante blanqueo, y 6

Publicado como artículo de conferencia en ICLR 2015 0 50 100 150 200 iteraciones sobre todo el conjunto de datos 10 -2 10 -1 costo de entrenamiento Red neuronal multicapa MNIST + dropout AdaGrad RMSProp SGDNesterov AdaDelta Adam (a) (b) Figura 2: Entrenamiento de redes neuronales multicapa sobre imágenes MNIST. (a) Redes neuronales que usan dropout como regularización estocástica. (b) Redes neuronales con función de costo determinista. Comparamos con el optimizador sum-of-functions (SFO) (Sohl-Dickstein et al., 2014) 0.0 0.5 1.0 1.5 2.0 2.5 3.0 iteraciones sobre todo el conjunto de datos 0.5 1.0 1.5 2.0 2.5 3.0 costo de entrenamiento ConvNet CIFAR10 Primeros 3 Epoches AdaGrad AdaGrad+dropout SGDNesterov SGDNesterov+dropout Adam Adam+dropout 0 5 10 15 20 25 30 35 40 45 iteraciones sobre todo el conjunto de datos 10-4 10-3 10-2 10-1 100 101 102 costo de entrenamiento ConvNet CIFAR10 AdaGrad AdaGrad+dropout SGDNesterov SGDNesterov+dropout Adam Adam+dropout Figura 3: Costo de entrenamiento de redes neuronales convolucionales. (izquierda) Costo de entrenamiento durante las primeras tres épocas. (derecha) Costo de entrenamiento durante 45 épocas. CIFAR-10 con arquitectura c64-c64-c128-1000. Se aplica ruido de dropout a la capa de entrada y a la capa totalmente conectada. El tamaño de minilote también se establece en 128, similar a los experimentos previos. Curiosamente, aunque tanto Adam como AdaGrad progresan rápidamente reduciendo el costo en la etapa inicial del entrenamiento, mostrado en la Figura 3 (izquierda), Adam y SGD eventualmente convergen considerablemente más rápido que AdaGrad para CNN, como se muestra en la Figura 3 (derecha). Notamos que la estimación del segundo momento bvt se desvanece a ceros después de unas pocas épocas y está dominada por el ϵ en el algoritmo 1. La estimación del segundo momento es, por lo tanto, una mala aproximación a la geometría de la función de costo en CNN, en comparación con la red totalmente conectada de la Sección 6.2. Mientras que reducir la varianza del minilote a través del primer momento es más importante en las CNN y contribuye a la aceleración. Como resultado, AdaGrad converge mucho más lentamente que los demás en este experimento particular. Aunque Adam muestra una mejora marginal sobre SGD con momento, adapta la escala de la tasa de aprendizaje para diferentes capas en lugar de elegirla manualmente como en SGD. 7

Publicado como artículo de conferencia en ICLR 2015 β1=0 β1=0.9 β2=0.99 β2=0.999 β2=0.9999 β2=0.99 β2=0.999 β2=0.9999 (a) después de 10 épocas (b) después de 100 épocas log10(α) Pérdida Figura 4: Efecto de los términos de corrección de sesgo (línea roja) frente a la ausencia de términos de corrección de sesgo (línea verde) después de 10 épocas (izquierda) y 100 épocas (derecha) sobre la pérdida (eje y) al aprender un Variational Auto-Encoder (VAE) (Kingma & Welling, 2013), para diferentes ajustes del tamaño de paso α (eje x) e hiperparámetros β1 y β2. 6.4 EXPERIMENTO: TÉRMINO DE CORRECCIÓN DE SESGO También evaluamos empíricamente el efecto de los términos de corrección de sesgo explicados en las secciones 2 y 3. Como se discutió en la sección 5, la eliminación de los términos de corrección de sesgo da como resultado una versión de RMSProp (Tieleman & Hinton, 2012) con momento. Variamos β1 y β2 al entrenar un autoencoder variacional (VAE) con la misma arquitectura que en (Kingma & Welling, 2013) con una sola capa oculta de 500 unidades ocultas con no linealidades softplus y una variable latente gaussiana esférica de 50 dimensiones. Iteramos sobre un amplio rango de elecciones de hiperparámetros, es decir, β1 ∈[0, 0.9] y β2 ∈[0.99, 0.999, 0.9999], y log10(α) ∈[−5, …, −1]. Los valores de β2 cercanos a 1, requeridos para la robustez frente a gradientes dispersos, dan como resultado un mayor sesgo de inicialización; por lo tanto, esperamos que el término de corrección de sesgo sea importante en tales casos de decaimiento lento, evitando un efecto adverso en la optimización. En la Figura 4, los valores de β2 cercanos a 1 efectivamente conducen a inestabilidades en el entrenamiento cuando no había término de corrección de sesgo presente, especialmente en las primeras pocas épocas del entrenamiento. Los mejores resultados se lograron con valores pequeños de (1−β2) y corrección de sesgo; esto fue más evidente hacia el final de la optimización, cuando los gradientes tienden a volverse más dispersos a medida que las unidades ocultas se especializan en patrones específicos. En resumen, Adam se desempeñó igual o mejor que RMSProp, independientemente del ajuste del hiperparámetro. 7 ## EXTENSIONES 7.1 ## ADAMAX En Adam, la regla de actualización para los pesos individuales consiste en escalar sus gradientes inversamente proporcional a una norma L2 (escalada) de sus gradientes individuales actuales y pasados. Podemos generalizar la regla de actualización basada en la norma L2 a una regla de actualización basada en la norma Lp. Tales variantes se vuelven numéricamente inestables para p grande. Sin embargo, en el caso especial donde dejamos p →∞, surge un algoritmo sorprendentemente simple y estable; véase el algoritmo 2. Ahora derivaremos el algoritmo. Sea, en el caso de la norma Lp, el tamaño de paso en el tiempo t inversamente proporcional a v1/p t , donde: vt = βp 2vt−1 + (1 −βp 2)|gt|p (6) = (1 −βp 2) t X i=1 βp(t−i) 2 · |gi|p (7) 8

Publicado como artículo de conferencia en ICLR 2015 Algoritmo 2: AdaMax, una variante de Adam basada en la norma infinito. Véase la sección 7.1 para más detalles. Buenos valores por defecto para los problemas de aprendizaje automático evaluados son α = 0.002, β1 = 0.9 y β2 = 0.999. Con βt 1 denotamos β1 elevado a la potencia t. Aquí, (α/(1 −βt 1)) es la tasa de aprendizaje con el término de corrección de sesgo para el primer momento. Todas las operaciones sobre vectores son elemento a elemento. Require: α: Tamaño de paso Require: β1, β2 ∈[0, 1): Tasas de decaimiento exponencial Require: f(θ): Función objetivo estocástica con parámetros θ Require: θ0: Vector de parámetros inicial m0 ←0 (Inicializar el vector del primer momento) u0 ←0 (Inicializar la norma infinito ponderada exponencialmente) t ←0 (Inicializar el paso de tiempo) while θt no haya convergido do t ←t + 1 gt ←∇θft(θt−1) (Obtener gradientes con respecto al objetivo estocástico en el paso de tiempo t) mt ←β1 · mt−1 + (1 −β1) · gt (Actualizar la estimación sesgada del primer momento) ut ←max(β2 · ut−1, |gt|) (Actualizar la norma infinito ponderada exponencialmente) θt ←θt−1 −(α/(1 −βt 1)) · mt/ut (Actualizar parámetros) end while return θt (Parámetros resultantes) Nótese que el término de decaimiento se parametriza aquí equivalentemente como βp 2 en lugar de β2. Ahora dejamos p →∞, y definimos ut = limp→∞(vt)1/p, entonces: ut = lim p→∞(vt)1/p = lim p→∞

(1 −βp 2) t X i=1 βp(t−i) 2 · |gi|p !1/p (8) = lim p→∞(1 −βp 2)1/p

t X i=1 βp(t−i) 2 · |gi|p !1/p (9) = lim p→∞

t X i=1 β(t−i) 2 · |gi| p !1/p (10) = max βt−1 2 |g1|, βt−2 2 |g2|, . . . , β2|gt−1|, |gt| (11) Lo cual corresponde a la fórmula recursiva notablemente simple: ut = max(β2 · ut−1, |gt|) (12) con valor inicial u0 = 0. Nótese que, convenientemente, no necesitamos corregir el sesgo de inicialización en este caso. Nótese también que la magnitud de las actualizaciones de los parámetros tiene una cota más simple con AdaMax que con Adam, a saber: |∆t| ≤α. 7.2 PROMEDIADO TEMPORAL Dado que la última iteración es ruidosa debido a la aproximación estocástica, a menudo se logra un mejor desempeño de generalización mediante el promediado. Anteriormente, en Moulines & Bach (2011), se ha demostrado que el promediado de Polyak-Ruppert (Polyak & Juditsky, 1992; Ruppert, 1988) mejora la convergencia del SGD estándar, donde ¯θt = 1 t Pn k=1 θk. Alternativamente, se puede utilizar un promedio móvil exponencial sobre los parámetros, dando mayor peso a valores de parámetros más recientes. Esto puede implementarse trivialmente añadiendo una línea al bucle interior de los algoritmos 1 y 2: ¯θt ←β2 · ¯θt−1 +(1−β2)θt, con ¯θ0 = 0. El sesgo de inicialización puede corregirse de nuevo mediante el estimador bθt = ¯θt/(1 −βt 2). 8 ## CONCLUSIÓN Hemos presentado un algoritmo simple y computacionalmente eficiente para la optimización basada en gradientes de funciones objetivo estocásticas. Nuestro método está orientado a problemas de aprendizaje automático con 9

Publicado como artículo de conferencia en ICLR 2015 conjuntos de datos grandes y/o espacios de parámetros de alta dimensión. El método combina las ventajas de dos métodos de optimización populares recientemente: la capacidad de AdaGrad para manejar gradientes dispersos, y la capacidad de RMSProp para manejar objetivos no estacionarios. El método es sencillo de implementar y requiere poca memoria. Los experimentos confirman el análisis sobre la tasa de convergencia en problemas convexos. En general, encontramos que Adam es robusto y bien adaptado a una amplia gama de problemas de optimización no convexa en el campo del aprendizaje automático. 9 ## AGRADECIMIENTOS Este artículo probablemente no habría existido sin el apoyo de Google Deepmind. Nos gustaría agradecer especialmente a Ivo Danihelka y Tom Schaul por acuñar el nombre Adam. Gracias a Kai Fan de Duke University por detectar un error en la derivación original de AdaMax. Los experimentos en este trabajo se llevaron a cabo en parte en la infraestructura electrónica nacional holandesa con el apoyo de la SURF Foundation. Diederik Kingma cuenta con el apoyo de la Google European Doctorate Fellowship in Deep Learning. ## REFERENCIAS Amari, Shun-Ichi. Natural gradient works efficiently in learning. Neural computation, 10(2):251–276, 1998. Deng, Li, Li, Jinyu, Huang, Jui-Ting, Yao, Kaisheng, Yu, Dong, Seide, Frank, Seltzer, Michael, Zweig, Geoff, He, Xiaodong, Williams, Jason, et al. Recent advances in deep learning for speech research at microsoft. ICASSP 2013, 2013. Duchi, John, Hazan, Elad, and Singer, Yoram. Adaptive subgradient methods for online learning and stochastic optimization. The Journal of Machine Learning Research, 12:2121–2159, 2011. Graves, Alex. Generating sequences with recurrent neural networks. arXiv preprint arXiv:1308.0850, 2013. Graves, Alex, Mohamed, Abdel-rahman, and Hinton, Geoffrey. Speech recognition with deep recurrent neural networks. In Acoustics, Speech and Signal Processing (ICASSP), 2013 IEEE International Conference on, pp. 6645–6649. IEEE, 2013. Hinton, G.E. and Salakhutdinov, R.R. Reducing the dimensionality of data with neural networks. Science, 313 (5786):504–507, 2006. Hinton, Geoffrey, Deng, Li, Yu, Dong, Dahl, George E, Mohamed, Abdel-rahman, Jaitly, Navdeep, Senior, Andrew, Vanhoucke, Vincent, Nguyen, Patrick, Sainath, Tara N, et al. Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups. Signal Processing Magazine, IEEE, 29(6):82–97, 2012a. Hinton, Geoffrey E, Srivastava, Nitish, Krizhevsky, Alex, Sutskever, Ilya, and Salakhutdinov, Ruslan R. Improving neural networks by preventing co-adaptation of feature detectors. arXiv preprint arXiv:1207.0580, 2012b. Kingma, Diederik P and Welling, Max. Auto-Encoding Variational Bayes. In The 2nd International Conference on Learning Representations (ICLR), 2013. Krizhevsky, Alex, Sutskever, Ilya, and Hinton, Geoffrey E. Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems, pp. 1097–1105, 2012. Maas, Andrew L, Daly, Raymond E, Pham, Peter T, Huang, Dan, Ng, Andrew Y, and Potts, Christopher. Learning word vectors for sentiment analysis. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies-Volume 1, pp. 142–150. Association for Computational Linguistics, 2011. Moulines, Eric and Bach, Francis R. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. In Advances in Neural Information Processing Systems, pp. 451–459, 2011. Pascanu, Razvan and Bengio, Yoshua. Revisiting natural gradient for deep networks. arXiv preprint arXiv:1301.3584, 2013. Polyak, Boris T and Juditsky, Anatoli B. Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 30(4):838–855, 1992. 10

Publicado como artículo de conferencia en ICLR 2015 Roux, Nicolas L and Fitzgibbon, Andrew W. A fast natural newton method. In Proceedings of the 27th International Conference on Machine Learning (ICML-10), pp. 623–630, 2010. Ruppert, David. Efficient estimations from a slowly convergent robbins-monro process. Technical report, Cornell University Operations Research and Industrial Engineering, 1988. Schaul, Tom, Zhang, Sixin, and LeCun, Yann. No more pesky learning rates. arXiv preprint arXiv:1206.1106, 2012. Sohl-Dickstein, Jascha, Poole, Ben, and Ganguli, Surya. Fast large-scale optimization by unifying stochastic gradient and quasi-newton methods. In Proceedings of the 31st International Conference on Machine Learning (ICML-14), pp. 604–612, 2014. Sutskever, Ilya, Martens, James, Dahl, George, and Hinton, Geoffrey. On the importance of initialization and momentum in deep learning. In Proceedings of the 30th International Conference on Machine Learning (ICML-13), pp. 1139–1147, 2013. Tieleman, T. and Hinton, G. Lecture 6.5 - RMSProp, COURSERA: Neural Networks for Machine Learning. Technical report, 2012. Wang, Sida and Manning, Christopher. Fast dropout training. In Proceedings of the 30th International Conference on Machine Learning (ICML-13), pp. 118–126, 2013. Zeiler, Matthew D. Adadelta: An adaptive learning rate method. arXiv preprint arXiv:1212.5701, 2012. Zinkevich, Martin. Online convex programming and generalized infinitesimal gradient ascent. 2003. 11

Publicado como artículo de conferencia en ICLR 2015 10 ## APÉNDICE 10.1 ## DEMOSTRACIÓN DE CONVERGENCIA Definición 10.1. Una función f : Rd →R es convexa si para todo x, y ∈Rd, para todo λ ∈[0, 1], λf(x) + (1 −λ)f(y) ≥f(λx + (1 −λ)y) Asimismo, nótese que una función convexa puede acotarse inferiormente por un hiperplano en su tangente. Lema 10.2. Si una función f : Rd →R es convexa, entonces para todo x, y ∈Rd, f(y) ≥f(x) + ∇f(x)T (y −x) El lema anterior puede usarse para acotar superiormente el arrepentimiento y nuestra demostración para el teorema principal se construye sustituyendo el hiperplano por las reglas de actualización de Adam. Los siguientes dos lemas se usan para apoyar nuestro teorema principal. También usamos algunas definiciones para simplificar nuestra notación, donde gt ≜∇ft(θt) y gt,i como el i-ésimo elemento. Definimos g1:t,i ∈Rt como un vector que contiene la i-ésima dimensión de los gradientes a lo largo de todas las iteraciones hasta t, g1:t,i = [g1,i, g2,i, · · · , gt,i] Lema 10.3. Sean gt = ∇ft(θt) y g1:t definidos como antes y acotados, ∥gt∥2 ≤G, ∥gt∥∞≤ G∞. Entonces, T X t=1 s g2 t,i t ≤2G∞∥g1:T,i∥2 Demostración. Probaremos la desigualdad usando inducción sobre T. El caso base para T = 1, tenemos q g2 1,i ≤2G∞∥g1,i∥2. Para el paso inductivo, T X t=1 s g2 t,i t = T −1 X t=1 s g2 t,i t + s g2 T,i T ≤2G∞∥g1:T −1,i∥2 + s g2 T,i T = 2G∞ q ∥g1:T,i∥2 2 −g2 T + s g2 T,i T A partir de, ∥g1:T,i∥2 2 −g2 T,i + g4 T,i 4∥g1:T,i∥2 2 ≥∥g1:T,i∥2 2 −g2 T,i, podemos tomar la raíz cuadrada en ambos lados y tener, q ∥g1:T,i∥2 2 −g2 T,i ≤∥g1:T,i∥2 − g2 T,i 2∥g1:T,i∥2 ≤∥g1:T,i∥2 − g2 T,i 2 p TG2∞ Reordenando la desigualdad y sustituyendo el término q ∥g1:T,i∥2 2 −g2 T,i, G∞ q ∥g1:T,i∥2 2 −g2 T + s g2 T,i T ≤2G∞∥g1:T,i∥2 12

Publicado como artículo de conferencia en ICLR 2015 Lema 10.4. Sea γ ≜ β2 1 √β2 . Para β1, β2 ∈[0, 1) que satisfacen β2 1 √β2 < 1 y gt acotado, ∥gt∥2 ≤G, ∥gt∥∞≤G∞, se cumple la siguiente desigualdad T X t=1 bm2 t,i p tbvt,i ≤ 2 1 −γ 1 √1 −β2 ∥g1:T,i∥2 Demostración. Bajo el supuesto, √ 1−βt 2 (1−βt 1)2 ≤ 1 (1−β1)2 . Podemos expandir el último término en la sumatoria usando las reglas de actualización del Algoritmo 1, T X t=1 bm2 t,i p tbvt,i = T −1 X t=1 bm2 t,i p tbvt,i + p 1 −βT 2 (1 −βT 1 )2 (PT k=1(1 −β1)βT −k 1 gk,i)2 q ## T PT j=1(1 −β2)βT −j 2 g2 j,i ≤ T −1 X t=1 bm2 t,i p tbvt,i + p 1 −βT 2 (1 −βT 1 )2 T X k=1 T((1 −β1)βT −k 1 gk,i)2 q ## T PT j=1(1 −β2)βT −j 2 g2 j,i ≤ T −1 X t=1 bm2 t,i p tbvt,i + p 1 −βT 2 (1 −βT 1 )2 T X k=1 T((1 −β1)βT −k 1 gk,i)2 q T(1 −β2)βT −k 2 g2 k,i ≤ T −1 X t=1 bm2 t,i p tbvt,i + p 1 −βT 2 (1 −βT 1 )2 (1 −β1)2 p T(1 −β2) T X k=1 T β2 1 √β2 T −k ∥gk,i∥2 ≤ T −1 X t=1 bm2 t,i p tbvt,i + T p T(1 −β2) T X k=1 γT −k∥gk,i∥2 De manera similar, podemos acotar superiormente el resto de los términos en la sumatoria. T X t=1 bm2 t,i p tbvt,i ≤ T X t=1 ∥gt,i∥2 p t(1 −β2) T −t X j=0 tγj ≤ T X t=1 ∥gt,i∥2 p t(1 −β2) T X j=0 tγj Para γ < 1, usando la cota superior sobre la serie aritmético-geométrica, P t tγt < 1 (1−γ)2 : T X t=1 ∥gt,i∥2 p t(1 −β2) T X j=0 tγj ≤ 1 (1 −γ)2√1 −β2 T X t=1 ∥gt,i∥2 √ t Aplicando el Lema 10.3, T X t=1 bm2 t,i p tbvt,i ≤ 2G∞ (1 −γ)2√1 −β2 ∥g1:T,i∥2 Para simplificar la notación, definimos γ ≜ β2 1 √β2 . Intuitivamente, nuestro siguiente teorema se cumple cuando la tasa de aprendizaje αt está decayendo a una tasa de t−1 2 y el coeficiente del promedio móvil del primer momento β1,t decae exponencialmente con λ, que es típicamente cercano a 1, por ejemplo, 1 −10−8. Teorema 10.5. Asumamos que la función ft tiene gradientes acotados, ∥∇ft(θ)∥2 ≤G, ∥∇ft(θ)∥∞≤ G∞para todo θ ∈Rd y la distancia entre cualquier θt generado por Adam está acotada, ∥θn −θm∥2 ≤D, 13

Publicado como artículo de conferencia en ICLR 2015 ∥θm −θn∥∞≤D∞para cualesquiera m, n ∈{1, …, T}, y β1, β2 ∈[0, 1) satisfacen β2 1 √β2 < 1. Sea αt = α √ t y β1,t = β1λt−1, λ ∈(0, 1). Adam alcanza la siguiente garantía, para todo T ≥1. R(T) ≤ D2 2α(1 −β1) d X i=1 p TbvT,i+ α(β1 + 1)G∞ (1 −β1)√1 −β2(1 −γ)2 d X i=1 ∥g1:T,i∥2+ d X i=1 D2 ∞G∞ √1 −β2 2α(1 −β1)(1 −λ)2 Demostración. Usando el Lema 10.2, tenemos, ft(θt) −ft(θ∗) ≤gT t (θt −θ∗) = d X i=1 gt,i(θt,i −θ∗ ,i) De las reglas de actualización presentadas en el algoritmo 1, θt+1 = θt −αt bmt/ p bvt = θt − αt 1 −βt 1 β1,t √bvt mt−1 + (1 −β1,t) √bvt gt Nos centramos en la i-ésima dimensión del vector de parámetros θt ∈Rd. Restando el escalar θ∗ ,i y elevando al cuadrado ambos lados de la regla de actualización anterior, tenemos, (θt+1,i −θ∗ ,i)2 =(θt,i −θ∗ ,i)2 − 2αt 1 −βt 1 ( β1,t p bvt,i mt−1,i + (1 −β1,t) p bvt,i gt,i)(θt,i −θ∗ ,i) + α2 t( bmt,i p bvt,i )2 Podemos reordenar la ecuación anterior y usar la desigualdad de Young, ab ≤a2/2 + b2/2. Asimismo, puede mostrarse que p bvt,i = qPt j=1(1 −β2)βt−j 2 g2 j,i/ p 1 −βt 2 ≤∥g1:t,i∥2 y β1,t ≤β1. Entonces gt,i(θt,i −θ∗ ,i) =(1 −βt 1) p bvt,i 2αt(1 −β1,t) (θt,i −θ∗ ,t)2 −(θt+1,i −θ∗ ,i)2 + β1,t (1 −β1,t) bv 1 4 t−1,i √αt−1 (θ∗ ,i −θt,i)√αt−1 mt−1,i bv 1 4 t−1,i + αt(1 −βt 1) p bvt,i 2(1 −β1,t) ( bmt,i p bvt,i )2 ≤ 1 2αt(1 −β1) (θt,i −θ∗ ,t)2 −(θt+1,i −θ∗ ,i)2 p bvt,i + β1,t 2αt−1(1 −β1,t)(θ∗ ,i −θt,i)2p bvt−1,i + β1αt−1 2(1 −β1) m2 t−1,i p bvt−1,i + αt 2(1 −β1) bm2 t,i p bvt,i Aplicamos el Lema 10.4 a la desigualdad anterior y derivamos la cota de arrepentimiento sumando a través de todas las dimensiones para i ∈1, …, d en la cota superior de ft(θt) −ft(θ∗) y la secuencia de funciones convexas para t ∈1, …, T: R(T) ≤ d X i=1 1 2α1(1 −β1)(θ1,i −θ∗ ,i)2p bv1,i + d X i=1 T X t=2 1 2(1 −β1)(θt,i −θ∗ ,i)2( p bvt,i αt − p bvt−1,i αt−1 ) + β1αG∞ (1 −β1)√1 −β2(1 −γ)2 d X i=1 ∥g1:T,i∥2 + αG∞ (1 −β1)√1 −β2(1 −γ)2 d X i=1 ∥g1:T,i∥2 + d X i=1 T X t=1 β1,t 2αt(1 −β1,t)(θ∗ ,i −θt,i)2p bvt,i 14

Publicado como artículo de conferencia en ICLR 2015 De los supuestos, ∥θt −θ∗∥2 ≤D, ∥θm −θn∥∞≤D∞, tenemos: R(T) ≤ D2 2α(1 −β1) d X i=1 p TbvT,i + α(1 + β1)G∞ (1 −β1)√1 −β2(1 −γ)2 d X i=1 ∥g1:T,i∥2 + D2 ∞ 2α d X i=1 t X t=1 β1,t (1 −β1,t) p tbvt,i ≤ D2 2α(1 −β1) d X i=1 p TbvT,i + α(1 + β1)G∞ (1 −β1)√1 −β2(1 −γ)2 d X i=1 ∥g1:T,i∥2 + D2 ∞G∞ √1 −β2 2α d X i=1 t X t=1 β1,t (1 −β1,t) √ t Podemos usar la cota superior de la serie aritmético-geométrica para el último término: t X t=1 β1,t (1 −β1,t) √ t ≤ t X t=1 1 (1 −β1)λt−1√ t ≤ t X t=1 1 (1 −β1)λt−1t ≤ 1 (1 −β1)(1 −λ)2 Por lo tanto, tenemos la siguiente cota de arrepentimiento: R(T) ≤ D2 2α(1 −β1) d X i=1 p TbvT,i + α(1 + β1)G∞ (1 −β1)√1 −β2(1 −γ)2 d X i=1 ∥g1:T,i∥2 + d X i=1 D2 ∞G∞ √1 −β2 2αβ1(1 −λ)2 15

Figuras