Descenso de gradiente

Algoritmo de optimización

Descenso de gradiente en 2D

El descenso de gradiente es un método de optimización matemática sin restricciones . Es un algoritmo iterativo de primer orden para minimizar una función multivariable diferenciable .

La idea es dar pasos repetidos en la dirección opuesta del gradiente (o gradiente aproximado) de la función en el punto actual, porque esta es la dirección del descenso más pronunciado. Por el contrario, dar pasos en la dirección del gradiente conducirá a una trayectoria que maximiza esa función; el procedimiento se conoce entonces como ascenso de gradiente . Es particularmente útil en el aprendizaje automático para minimizar la función de costo o pérdida. ^[1] El descenso de gradiente no debe confundirse con los algoritmos de búsqueda local , aunque ambos son métodos iterativos para la optimización .

El descenso de gradiente generalmente se atribuye a Augustin-Louis Cauchy , quien lo sugirió por primera vez en 1847. ^[2] Jacques Hadamard propuso de forma independiente un método similar en 1907. ^{[3] [4]} Sus propiedades de convergencia para problemas de optimización no lineal fueron estudiadas por primera vez por Haskell Curry en 1944, ^[5] y el método se fue estudiando y utilizando cada vez más en las décadas siguientes. ^{[6] [7]}

Una extensión simple del descenso de gradiente, el descenso de gradiente estocástico , sirve como el algoritmo más básico utilizado para entrenar la mayoría de las redes profundas en la actualidad.

Descripción

Ilustración del descenso de gradiente en una serie de conjuntos de niveles

El descenso de gradiente se basa en la observación de que si la función multivariable está definida y es diferenciable en un entorno de un punto , entonces decrece más rápidamente si se va desde en la dirección del gradiente negativo de en . De ello se deduce que, si ${\displaystyle F(\mathbf {x} )}$ ${\displaystyle \mathbf {a} }$ ${\displaystyle F(\mathbf {x} )}$ ${\displaystyle \mathbf {a} }$ ${\displaystyle F}$ ${\displaystyle \mathbf {a} ,-\nabla F(\mathbf {a} )}$

${\displaystyle \mathbf {a} _{n+1}=\mathbf {a} _{n}-\gamma \nabla F(\mathbf {a} _{n})}$

para un tamaño de paso o una tasa de aprendizaje suficientemente pequeños , entonces . En otras palabras, el término se resta de porque queremos movernos en contra del gradiente, hacia el mínimo local. Con esta observación en mente, uno comienza con una estimación de un mínimo local de , y considera la secuencia tal que ${\displaystyle \gamma \in \mathbb {R} _{+}}$ ${\displaystyle F(\mathbf {a_{n}} )\geq F(\mathbf {a_{n+1}} )}$ ${\displaystyle \gamma \nabla F(\mathbf {a} )}$ ${\displaystyle \mathbf {a} }$ ${\displaystyle \mathbf {x} _{0}}$ ${\displaystyle F}$ ${\displaystyle \mathbf {x} _{0},\mathbf {x} _{1},\mathbf {x} _{2},\ldots }$

${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}\nabla F(\mathbf {x} _{n}),\ n\geq 0.}$

Tenemos una secuencia monótona

${\displaystyle F(\mathbf {x} _{0})\geq F(\mathbf {x} _{1})\geq F(\mathbf {x} _{2})\geq \cdots ,}$

Por lo tanto, es de esperar que la secuencia converja al mínimo local deseado. Tenga en cuenta que el valor del tamaño del paso puede cambiar en cada iteración. ${\displaystyle (\mathbf {x} _{n})}$ ${\displaystyle \gamma }$

Es posible garantizar la convergencia a un mínimo local bajo ciertos supuestos sobre la función (por ejemplo, convexa y Lipschitz ) y elecciones particulares de . Estas incluyen la secuencia ${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle \nabla F}$ ${\displaystyle \gamma }$

${\displaystyle \gamma _{n}={\frac {\left|\left(\mathbf {x} _{n}-\mathbf {x} _{n-1}\right)^{T}\left[\nabla F(\mathbf {x} _{n})-\nabla F(\mathbf {x} _{n-1})\right]\right|}{\left\|\nabla F(\mathbf {x} _{n})-\nabla F(\mathbf {x} _{n-1})\right\|^{2}}}}$

como en el método de Barzilai-Borwein , ^{[8] [9]} o una secuencia que satisface las condiciones de Wolfe (que se pueden encontrar mediante búsqueda lineal ). Cuando la función es convexa , todos los mínimos locales también son mínimos globales, por lo que en este caso el descenso del gradiente puede converger a la solución global. ${\displaystyle \gamma _{n}}$ ${\displaystyle F}$

Este proceso se ilustra en la imagen adyacente. Aquí, se supone que está definida en el plano y que su gráfica tiene forma de cuenco . Las curvas azules son las curvas de nivel , es decir, las regiones en las que el valor de es constante. Una flecha roja que se origina en un punto muestra la dirección del gradiente negativo en ese punto. Observe que el gradiente (negativo) en un punto es ortogonal a la línea de contorno que pasa por ese punto. Vemos que el descenso del gradiente nos lleva al fondo del cuenco, es decir, al punto donde el valor de la función es mínimo. ${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle F}$

Una analogía para comprender el descenso del gradiente

Niebla en las montañas

La intuición básica detrás del descenso de gradiente se puede ilustrar con un escenario hipotético. Las personas están atrapadas en las montañas y están tratando de bajar (es decir, tratando de encontrar el mínimo global). Hay una niebla espesa, por lo que la visibilidad es extremadamente baja. Por lo tanto, el camino hacia abajo de la montaña no es visible, por lo que deben usar información local para encontrar el mínimo. Pueden usar el método de descenso de gradiente, que implica observar la inclinación de la colina en su posición actual y luego proceder en la dirección con el descenso más pronunciado (es decir, cuesta abajo). Si estuvieran tratando de encontrar la cima de la montaña (es decir, el máximo), entonces procederían en la dirección del ascenso más pronunciado (es decir, cuesta arriba). Usando este método, eventualmente encontrarían su camino hacia abajo de la montaña o posiblemente se quedarían atrapados en algún agujero (es decir, mínimo local o punto de silla de montar ), como un lago de montaña. Sin embargo, supongamos también que la inclinación de la colina no es inmediatamente obvia con una simple observación, sino que requiere un instrumento sofisticado para medir, que las personas tienen en ese momento. Se necesita bastante tiempo para medir la inclinación de la colina con el instrumento, por lo que deben minimizar el uso del instrumento si quieren bajar de la montaña antes del atardecer. La dificultad es entonces elegir la frecuencia con la que deben medir la inclinación de la colina para no salirse del camino.

En esta analogía, las personas representan el algoritmo y el camino que siguen al descender la montaña representa la secuencia de ajustes de parámetros que explorará el algoritmo. La inclinación de la colina representa la pendiente de la función en ese punto. El instrumento utilizado para medir la inclinación es la diferenciación . La dirección en la que eligen viajar se alinea con el gradiente de la función en ese punto. La cantidad de tiempo que viajan antes de tomar otra medida es el tamaño del paso. Si saltan de un acantilado en la niebla, habrán optimizado su camino de descenso.

Elección del tamaño del paso y dirección de descenso

Dado que el uso de un tamaño de paso demasiado pequeño ralentizaría la convergencia y uno demasiado grande provocaría un exceso de velocidad y divergencia, encontrar un buen ajuste es un problema práctico importante. Philip Wolfe también abogó por utilizar "elecciones inteligentes de la dirección [de descenso]" en la práctica. ^[10] Si bien el uso de una dirección que se desvíe de la dirección de descenso más pronunciada puede parecer contraintuitivo, la idea es que la pendiente más pequeña se puede compensar al mantenerse a lo largo de una distancia mucho más larga. ${\displaystyle \gamma }$ ${\displaystyle \gamma }$ ${\displaystyle \gamma }$

Para razonar sobre esto matemáticamente, considere una dirección y un tamaño de paso y considere la actualización más general: ${\displaystyle \mathbf {p} _{n}}$ ${\displaystyle \gamma _{n}}$

${\displaystyle \mathbf {a} _{n+1}=\mathbf {a} _{n}-\gamma _{n}\,\mathbf {p} _{n}}$.

Encontrar buenos ajustes de y requiere algo de reflexión. En primer lugar, nos gustaría que la dirección de actualización apunte cuesta abajo. Matemáticamente, dejando que denote el ángulo entre y , esto requiere que Para decir más, necesitamos más información sobre la función objetivo que estamos optimizando. Bajo el supuesto bastante débil de que es continuamente diferenciable, podemos demostrar que: ^[11] ${\displaystyle \mathbf {p} _{n}}$ ${\displaystyle \gamma _{n}}$ ${\displaystyle \theta _{n}}$ ${\displaystyle -\nabla F(\mathbf {a_{n}} )}$ ${\displaystyle \mathbf {p} _{n}}$ ${\displaystyle \cos \theta _{n}>0.}$ ${\displaystyle F}$

Esta desigualdad implica que la cantidad en la que podemos estar seguros de que la función disminuye depende de un equilibrio entre los dos términos entre corchetes. El primer término entre corchetes mide el ángulo entre la dirección de descenso y el gradiente negativo. El segundo término mide la rapidez con la que cambia el gradiente a lo largo de la dirección de descenso. ${\displaystyle F}$

En principio, la desigualdad ( 1 ) se podría optimizar sobre y para elegir un tamaño de paso y una dirección óptimos. El problema es que evaluar el segundo término entre corchetes requiere evaluar , y las evaluaciones de gradiente adicionales son generalmente costosas e indeseables. Algunas formas de solucionar este problema son: ${\displaystyle \mathbf {p} _{n}}$ ${\displaystyle \gamma _{n}}$ ${\displaystyle \nabla F(\mathbf {a} _{n}-t\gamma _{n}\mathbf {p} _{n})}$

• Renuncie a los beneficios de una dirección de descenso inteligente estableciendo , y use la búsqueda lineal para encontrar un tamaño de paso adecuado , como uno que satisfaga las condiciones de Wolfe . Una forma más económica de elegir las tasas de aprendizaje es la búsqueda lineal de retroceso , un método que tiene buenas garantías teóricas y resultados experimentales. Tenga en cuenta que no es necesario elegir ser el gradiente; cualquier dirección que tenga un producto de intersección positivo con el gradiente dará como resultado una reducción del valor de la función (para un valor suficientemente pequeño de ). ${\displaystyle \mathbf {p} _{n}=\nabla F(\mathbf {a_{n}} )}$ ${\displaystyle \gamma _{n}}$ ${\displaystyle \mathbf {p} _{n}}$ ${\displaystyle \gamma _{n}}$
• Suponiendo que es dos veces diferenciable, utilice su hessiano para estimar Luego elija y optimizando la desigualdad ( 1 ). ${\displaystyle F}$ ${\displaystyle \nabla ^{2}F}$ ${\displaystyle \|\nabla F(\mathbf {a} _{n}-t\gamma _{n}\mathbf {p} _{n})-\nabla F(\mathbf {a} _{n})\|_{2}\approx \|t\gamma _{n}\nabla ^{2}F(\mathbf {a} _{n})\mathbf {p} _{n}\|.}$ ${\displaystyle \mathbf {p} _{n}}$ ${\displaystyle \gamma _{n}}$
• Suponiendo que es Lipschitz , use su constante de Lipschitz para acotar. Luego elija y optimizando la desigualdad ( 1 ). ${\displaystyle \nabla F}$ ${\displaystyle L}$ ${\displaystyle \|\nabla F(\mathbf {a} _{n}-t\gamma _{n}\mathbf {p} _{n})-\nabla F(\mathbf {a} _{n})\|_{2}\leq Lt\gamma _{n}\|\mathbf {p} _{n}\|.}$ ${\displaystyle \mathbf {p} _{n}}$ ${\displaystyle \gamma _{n}}$
• Construya un modelo personalizado de para . Luego elija y optimizando la desigualdad ( 1 ). ${\displaystyle \max _{t\in [0,1]}{\frac {\|\nabla F(\mathbf {a} _{n}-t\gamma _{n}\mathbf {p} _{n})-\nabla F(\mathbf {a} _{n})\|_{2}}{\|\nabla F(\mathbf {a} _{n})\|_{2}}}}$ ${\displaystyle F}$ ${\displaystyle \mathbf {p} _{n}}$ ${\displaystyle \gamma _{n}}$
• Bajo supuestos más fuertes sobre la función, tales como la convexidad , pueden ser posibles técnicas más avanzadas. ${\displaystyle F}$

Generalmente, siguiendo una de las recetas anteriores, se puede garantizar la convergencia a un mínimo local. Cuando la función es convexa , todos los mínimos locales son también mínimos globales, por lo que en este caso el descenso del gradiente puede converger a la solución global. ${\displaystyle F}$

Solución de un sistema lineal

El algoritmo de descenso más pronunciado aplicado al filtro de Wiener ^[12]

El descenso de gradiente se puede utilizar para resolver un sistema de ecuaciones lineales.

${\displaystyle A\mathbf {x} -\mathbf {b} =0}$

reformulado como un problema de minimización cuadrática. Si la matriz del sistema es simétrica real y definida positiva , una función objetivo se define como la función cuadrática, con minimización de ${\displaystyle A}$

${\displaystyle F(\mathbf {x} )=\mathbf {x} ^{T}A\mathbf {x} -2\mathbf {x} ^{T}\mathbf {b} ,}$

de modo que

${\displaystyle \nabla F(\mathbf {x} )=2(A\mathbf {x} -\mathbf {b} ).}$

Para una matriz real general , los mínimos cuadrados lineales definen ${\displaystyle A}$

${\displaystyle F(\mathbf {x} )=\left\|A\mathbf {x} -\mathbf {b} \right\|^{2}.}$

En los mínimos cuadrados lineales tradicionales para números reales y se utiliza la norma euclidiana , en cuyo caso ${\displaystyle A}$ ${\displaystyle \mathbf {b} }$

${\displaystyle \nabla F(\mathbf {x} )=2A^{T}(A\mathbf {x} -\mathbf {b} ).}$

La minimización de la búsqueda de línea , que consiste en encontrar el tamaño de paso localmente óptimo en cada iteración, se puede realizar analíticamente para funciones cuadráticas, y se conocen fórmulas explícitas para el tamaño localmente óptimo. ^{[6] [13]} ${\displaystyle \gamma }$ ${\displaystyle \gamma }$

Por ejemplo, para una matriz real simétrica y definida positiva , un algoritmo simple puede ser el siguiente: ^[6] ${\displaystyle A}$

${\displaystyle {\begin{aligned}&{\text{repeat in the loop:}}\\&\qquad \mathbf {r} :=\mathbf {b} -\mathbf {Ax} \\&\qquad \gamma :={\mathbf {r} ^{\mathsf {T}}\mathbf {r} }/{\mathbf {r} ^{\mathsf {T}}\mathbf {Ar} }\\&\qquad \mathbf {x} :=\mathbf {x} +\gamma \mathbf {r} \\&\qquad {\hbox{if }}\mathbf {r} ^{\mathsf {T}}\mathbf {r} {\text{ is sufficiently small, then exit loop}}\\&{\text{end repeat loop}}\\&{\text{return }}\mathbf {x} {\text{ as the result}}\end{aligned}}}$

Para evitar multiplicar por dos veces por iteración, observamos que implica , lo que da el algoritmo tradicional, ^[14] ${\displaystyle A}$ ${\displaystyle \mathbf {x} :=\mathbf {x} +\gamma \mathbf {r} }$ ${\displaystyle \mathbf {r} :=\mathbf {r} -\gamma \mathbf {Ar} }$

${\displaystyle {\begin{aligned}&\mathbf {r} :=\mathbf {b} -\mathbf {Ax} \\&{\text{repeat in the loop:}}\\&\qquad \gamma :={\mathbf {r} ^{\mathsf {T}}\mathbf {r} }/{\mathbf {r} ^{\mathsf {T}}\mathbf {Ar} }\\&\qquad \mathbf {x} :=\mathbf {x} +\gamma \mathbf {r} \\&\qquad {\hbox{if }}\mathbf {r} ^{\mathsf {T}}\mathbf {r} {\text{ is sufficiently small, then exit loop}}\\&\qquad \mathbf {r} :=\mathbf {r} -\gamma \mathbf {Ar} \\&{\text{end repeat loop}}\\&{\text{return }}\mathbf {x} {\text{ as the result}}\end{aligned}}}$

El método rara vez se utiliza para resolver ecuaciones lineales, siendo el método del gradiente conjugado una de las alternativas más populares. El número de iteraciones del descenso del gradiente es comúnmente proporcional al número de condición espectral de la matriz del sistema (la relación entre los valores propios máximos y mínimos de ) , mientras que la convergencia del método del gradiente conjugado normalmente se determina mediante una raíz cuadrada del número de condición, es decir, es mucho más rápido. Ambos métodos pueden beneficiarse del preacondicionamiento , donde el descenso del gradiente puede requerir menos suposiciones sobre el preacondicionador. ^[14] ${\displaystyle \kappa (A)}$ ${\displaystyle A}$ ${\displaystyle A^{T}A}$

Solución de un sistema no lineal

El descenso de gradiente también se puede utilizar para resolver un sistema de ecuaciones no lineales . A continuación, se muestra un ejemplo que muestra cómo utilizar el descenso de gradiente para resolver tres variables desconocidas, x ₁ , x ₂ y x ₃ . Este ejemplo muestra una iteración del descenso de gradiente.

Consideremos el sistema de ecuaciones no lineales

${\displaystyle {\begin{cases}3x_{1}-\cos(x_{2}x_{3})-{\tfrac {3}{2}}=0\\4x_{1}^{2}-625x_{2}^{2}+2x_{2}-1=0\\\exp(-x_{1}x_{2})+20x_{3}+{\tfrac {10\pi -3}{3}}=0\end{cases}}}$

Introduzcamos la función asociada

${\displaystyle G(\mathbf {x} )={\begin{bmatrix}3x_{1}-\cos(x_{2}x_{3})-{\tfrac {3}{2}}\\4x_{1}^{2}-625x_{2}^{2}+2x_{2}-1\\\exp(-x_{1}x_{2})+20x_{3}+{\tfrac {10\pi -3}{3}}\\\end{bmatrix}},}$

dónde

${\displaystyle \mathbf {x} ={\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\\end{bmatrix}}.}$

Ahora se podría definir la función objetivo

${\displaystyle {\begin{aligned}F(\mathbf {x} )&={\frac {1}{2}}G^{\mathrm {T} }(\mathbf {x} )G(\mathbf {x} )\\&={\frac {1}{2}}\left[\left(3x_{1}-\cos(x_{2}x_{3})-{\frac {3}{2}}\right)^{2}+\left(4x_{1}^{2}-625x_{2}^{2}+2x_{2}-1\right)^{2}+\right.\\&{}\qquad \left.\left(\exp(-x_{1}x_{2})+20x_{3}+{\frac {10\pi -3}{3}}\right)^{2}\right],\end{aligned}}}$

que intentaremos minimizar. Como estimación inicial, utilicemos

${\displaystyle \mathbf {x} ^{(0)}=\mathbf {0} ={\begin{bmatrix}0\\0\\0\\\end{bmatrix}}.}$

Sabemos que

${\displaystyle \mathbf {x} ^{(1)}=\mathbf {0} -\gamma _{0}\nabla F(\mathbf {0} )=\mathbf {0} -\gamma _{0}J_{G}(\mathbf {0} )^{\mathrm {T} }G(\mathbf {0} ),}$

donde la matriz jacobiana está dada por ${\displaystyle J_{G}}$

${\displaystyle J_{G}(\mathbf {x} )={\begin{bmatrix}3&\sin(x_{2}x_{3})x_{3}&\sin(x_{2}x_{3})x_{2}\\8x_{1}&-1250x_{2}+2&0\\-x_{2}\exp {(-x_{1}x_{2})}&-x_{1}\exp(-x_{1}x_{2})&20\\\end{bmatrix}}.}$

Calculamos:

${\displaystyle J_{G}(\mathbf {0} )={\begin{bmatrix}3&0&0\\0&2&0\\0&0&20\end{bmatrix}},\qquad G(\mathbf {0} )={\begin{bmatrix}-2.5\\-1\\10.472\end{bmatrix}}.}$

De este modo

${\displaystyle \mathbf {x} ^{(1)}=\mathbf {0} -\gamma _{0}{\begin{bmatrix}-7.5\\-2\\209.44\end{bmatrix}},}$

y

${\displaystyle F(\mathbf {0} )=0.5\left((-2.5)^{2}+(-1)^{2}+(10.472)^{2}\right)=58.456.}$

Una animación que muestra las primeras 83 iteraciones del descenso de gradiente aplicadas a este ejemplo. Las superficies son isosuperficies de la estimación actual y las flechas muestran la dirección del descenso. Debido a un tamaño de paso pequeño y constante, la convergencia es lenta. ${\displaystyle F(\mathbf {x} ^{(n)})}$ ${\displaystyle \mathbf {x} ^{(n)}}$

Ahora, se debe encontrar un adecuado tal que ${\displaystyle \gamma _{0}}$

${\displaystyle F\left(\mathbf {x} ^{(1)}\right)\leq F\left(\mathbf {x} ^{(0)}\right)=F(\mathbf {0} ).}$

Esto se puede hacer con cualquiera de los diversos algoritmos de búsqueda de línea . También se puede simplemente adivinar cuál da ${\displaystyle \gamma _{0}=0.001,}$

${\displaystyle \mathbf {x} ^{(1)}={\begin{bmatrix}0.0075\\0.002\\-0.20944\\\end{bmatrix}}.}$

Al evaluar la función objetivo en este valor, se obtiene

${\displaystyle F\left(\mathbf {x} ^{(1)}\right)=0.5\left((-2.48)^{2}+(-1.00)^{2}+(6.28)^{2}\right)=23.306.}$

La disminución del valor del siguiente paso ${\displaystyle F(\mathbf {0} )=58.456}$

${\displaystyle F\left(\mathbf {x} ^{(1)}\right)=23.306}$

es una disminución considerable de la función objetivo. Los pasos posteriores reducirían aún más su valor hasta que se encontrara una solución aproximada para el sistema.

Comentarios

El descenso de gradiente funciona en espacios de cualquier número de dimensiones, incluso en aquellos de dimensión infinita. En este último caso, el espacio de búsqueda es típicamente un espacio de funciones y se calcula la derivada de Fréchet de la función que se va a minimizar para determinar la dirección del descenso. ^[7]

El hecho de que el descenso de gradiente funcione en cualquier número de dimensiones (al menos un número finito) se puede considerar una consecuencia de la desigualdad de Cauchy-Schwarz , es decir, la magnitud del producto interno (punto) de dos vectores de cualquier dimensión se maximiza cuando son colineales . En el caso del descenso de gradiente, esto ocurriría cuando el vector de ajustes de la variable independiente es proporcional al vector de gradiente de las derivadas parciales.

El descenso del gradiente puede requerir muchas iteraciones para calcular un mínimo local con la precisión requerida , si la curvatura en diferentes direcciones es muy diferente para la función dada. Para tales funciones, el preacondicionamiento , que cambia la geometría del espacio para dar forma a los conjuntos de niveles de función como círculos concéntricos , soluciona la convergencia lenta. Sin embargo, construir y aplicar el preacondicionamiento puede ser costoso desde el punto de vista computacional.

El descenso de gradiente se puede combinar con una búsqueda lineal , encontrando el tamaño de paso óptimo localmente en cada iteración. Realizar la búsqueda lineal puede llevar mucho tiempo. Por el contrario, usar un tamaño de paso fijo pequeño puede generar una convergencia deficiente, y un tamaño de paso grande puede generar divergencia. No obstante, se pueden alternar tamaños de paso pequeños y grandes para mejorar la tasa de convergencia. ^{[15] [16]} ${\displaystyle \gamma }$ ${\displaystyle \gamma }$ ${\displaystyle \gamma }$

Los métodos basados ​​en el método de Newton y la inversión del hessiano utilizando técnicas de gradiente conjugado pueden ser mejores alternativas. ^{[17] [18]} Generalmente, tales métodos convergen en menos iteraciones, pero el costo de cada iteración es mayor. Un ejemplo es el método BFGS que consiste en calcular en cada paso una matriz por la cual se multiplica el vector de gradiente para ir en una dirección "mejor", combinado con un algoritmo de búsqueda de línea más sofisticado , para encontrar el "mejor" valor de Para problemas extremadamente grandes, donde dominan los problemas de memoria de la computadora, se debe utilizar un método de memoria limitada como L-BFGS en lugar de BFGS o el descenso más pronunciado. ${\displaystyle \gamma .}$

Si bien a veces es posible sustituir el descenso de gradiente por un algoritmo de búsqueda local , el descenso de gradiente no pertenece a la misma familia: si bien es un método iterativo para la optimización local , se basa en el gradiente de una función objetivo en lugar de una exploración explícita de un espacio de soluciones .

El descenso de gradiente puede verse como la aplicación del método de Euler para resolver ecuaciones diferenciales ordinarias a un flujo de gradiente . A su vez, esta ecuación puede derivarse como un controlador óptimo ^[19] para el sistema de control con dado en forma de retroalimentación . ${\displaystyle x'(t)=-\nabla f(x(t))}$ ${\displaystyle x'(t)=u(t)}$ ${\displaystyle u(t)}$ ${\displaystyle u(t)=-\nabla f(x(t))}$

Modificaciones

El descenso de gradiente puede converger a un mínimo local y desacelerarse en las proximidades de un punto de silla . Incluso en el caso de la minimización cuadrática sin restricciones, el descenso de gradiente desarrolla un patrón en zigzag de iteraciones subsiguientes a medida que avanzan las iteraciones, lo que da como resultado una convergencia lenta. Se han propuesto múltiples modificaciones del descenso de gradiente para abordar estas deficiencias.

Métodos de gradiente rápido

Yurii Nesterov ha propuesto ^[20] una modificación simple que permite una convergencia más rápida para problemas convexos y desde entonces se ha generalizado aún más. Para problemas suaves sin restricciones, el método se llama método de gradiente rápido (FGM) o método de gradiente acelerado (AGM). Específicamente, si la función diferenciable es convexa y es Lipschitz , y no se supone que es fuertemente convexa , entonces el error en el valor objetivo generado en cada paso por el método de descenso de gradiente estará limitado por . Usando la técnica de aceleración de Nesterov, el error disminuye en . ^{[21] [22]} Se sabe que la tasa de disminución de la función de costo es óptima para los métodos de optimización de primer orden. Sin embargo, existe la oportunidad de mejorar el algoritmo reduciendo el factor constante. El método de gradiente optimizado (OGM) ^[23] reduce esa constante por un factor de dos y es un método de primer orden óptimo para problemas a gran escala. ^[24] ${\displaystyle F}$ ${\displaystyle \nabla F}$ ${\displaystyle F}$ ${\displaystyle k}$ ${\textstyle {\mathcal {O}}\left({\tfrac {1}{k}}\right)}$ ${\textstyle {\mathcal {O}}\left({\tfrac {1}{k^{2}}}\right)}$ ${\displaystyle {\mathcal {O}}\left({k^{-2}}\right)}$

Para problemas restringidos o no suaves, el FGM de Nesterov se denomina método de gradiente proximal rápido (FPGM), una aceleración del método de gradiente proximal .

Impulso obola pesadamétodo

En un intento por romper el patrón en zigzag del descenso del gradiente, el método del momento o de la bola pesada utiliza un término de momento en analogía con una bola pesada que se desliza sobre la superficie de los valores de la función que se está minimizando, ^[6] o con el movimiento de masa en la dinámica newtoniana a través de un medio viscoso en un campo de fuerza conservativo . ^[25] El descenso del gradiente con momento recuerda la actualización de la solución en cada iteración y determina la siguiente actualización como una combinación lineal del gradiente y la actualización anterior. Para la minimización cuadrática sin restricciones, un límite teórico de la tasa de convergencia del método de la bola pesada es asintóticamente el mismo que el del método del gradiente conjugado óptimo . ^[6]

Esta técnica se utiliza en el descenso de gradiente estocástico y como una extensión de los algoritmos de retropropagación utilizados para entrenar redes neuronales artificiales . ^{[26] [27]} En la dirección de actualización, el descenso de gradiente estocástico agrega una propiedad estocástica. Los pesos se pueden utilizar para calcular las derivadas.

Extensiones

El descenso de gradiente se puede extender para manejar restricciones mediante la inclusión de una proyección sobre el conjunto de restricciones. Este método solo es factible cuando la proyección se puede calcular de manera eficiente en una computadora. Bajo supuestos adecuados, este método converge. Este método es un caso específico del algoritmo de avance-retroceso para inclusiones monótonas (que incluye programación convexa y desigualdades variacionales ). ^[28]

El descenso de gradiente es un caso especial de descenso de espejo que utiliza la distancia euclidiana al cuadrado como la divergencia de Bregman dada . ^[29]

Propiedades teóricas

Las propiedades del descenso de gradiente dependen de las propiedades de la función objetivo y de la variante del descenso de gradiente utilizada (por ejemplo, si se utiliza un paso de búsqueda lineal ). Las suposiciones realizadas afectan la tasa de convergencia y otras propiedades que se pueden demostrar para el descenso de gradiente. ^[30] Por ejemplo, si se supone que el objetivo es fuertemente convexo y suave en Lipschitz , entonces el descenso de gradiente converge linealmente con un tamaño de paso fijo. ^[1] Las suposiciones más laxas conducen a garantías de convergencia más débiles o requieren una selección de tamaño de paso más sofisticada. ^[30]

Véase también

• Búsqueda de línea de retroceso
• Método del gradiente conjugado
• Descenso de gradiente estocástico
• Rprop
• Regla delta
• Condiciones de Wolfe
• Preacondicionamiento
• Algoritmo de Broyden-Fletcher-Goldfarb-Shanno
• Fórmula de Davidon-Fletcher-Powell
• Método Nelder-Mead
• Algoritmo de Gauss-Newton
• Escalada de colinas
• Recocido cuántico
• CLS (búsqueda local continua)
• Neuroevolución

Referencias

1. Boyd, Stephen; Vandenberghe, Lieven (8 de marzo de 2004). Optimización convexa. Cambridge University Press. ISBN 978-0-521-83378-3.
2. Lemaréchal, C. (2012). "Cauchy y el método del gradiente" (PDF) . Doc Math Extra : 251–254. Archivado desde el original (PDF) el 2018-12-29 . Consultado el 2020-01-26 .
3. Hadamard, Jacques (1908). "Mémoire sur le problème d'analyse relatif à l'équilibre des plaques élastiques encastrées". Mémoires présentés par divers savants éstrangers à l'Académie des Sciences de l'Institut de France . 33 .
4. Courant, R. (1943). "Métodos variacionales para la solución de problemas de equilibrio y vibraciones". Boletín de la Sociedad Matemática Americana . 49 (1): 1–23. doi : 10.1090/S0002-9904-1943-07818-4 .
5. Curry, Haskell B. (1944). "El método del descenso más pronunciado para problemas de minimización no lineal". Quart. Appl. Math . 2 (3): 258–261. doi : 10.1090/qam/10667 .
6. Polyak, Boris (1987). Introducción a la optimización.
7. Akilov, GP; Kantorovich, LV (1982). Análisis funcional (2.ª ed.). Pergamon Press. ISBN 0-08-023036-9.
8. Barzilai, Jonathan; Borwein, Jonathan M. (1988). "Métodos de gradiente de tamaño de paso de dos puntos". IMA Journal of Numerical Analysis . 8 (1): 141–148. doi :10.1093/imanum/8.1.141.
9. Fletcher, R. (2005). "Sobre el método Barzilai–Borwein". En Qi, L.; Teo, K.; Yang, X. (eds.). Optimización y control con aplicaciones . Optimización aplicada. Vol. 96. Boston: Springer. págs. 235–256. ISBN . 0-387-24254-6.
10. Wolfe, Philip (abril de 1969). "Condiciones de convergencia para métodos de ascenso". SIAM Review . 11 (2): 226–235. doi :10.1137/1011036.
11. Bernstein, Jeremy; Vahdat, Arash; Yue, Yisong; Liu, Ming-Yu (12 de junio de 2020). "Sobre la distancia entre dos redes neuronales y la estabilidad del aprendizaje". arXiv : 2002.03432 [cs.LG].
12. Haykin, Simon S. Teoría del filtro adaptativo. Pearson Education India, 2008. - págs. 108-142, 217-242
13. Saad, Yousef (2003). Métodos iterativos para sistemas lineales dispersos (2.ª ed.). Filadelfia, Pensilvania: Society for Industrial and Applied Mathematics. pp. 195. ISBN 978-0-89871-534-7.
14. Bouwmeester, Henricus; Dougherty, Andrew; Knyazev, Andrew V. (2015). "Preacondicionamiento no simétrico para métodos de gradiente conjugado y descenso más pronunciado". Procedia Computer Science . 51 : 276–285. arXiv : 1212.6680 . doi : 10.1016/j.procs.2015.05.241 .
15. Altschuler, Jason (Jason M.) (2018). Avaricia, cobertura y aceleración en optimización convexa (Tesis). Instituto Tecnológico de Massachusetts.
16. Parshall, Allison (11 de agosto de 2023). «Los pasos gigantes arriesgados pueden resolver los problemas de optimización más rápidamente». Revista Quanta . Consultado el 11 de agosto de 2023 .
17. Press, WH ; Teukolsky, SA ; Vetterling, WT; Flannery, BP (1992). Recetas numéricas en C: el arte de la computación científica (2.ª ed.). Nueva York: Cambridge University Press . ISBN 0-521-43108-5.
18. Strutz, T. (2016). Ajuste de datos e incertidumbre: una introducción práctica a los mínimos cuadrados ponderados y más allá (2.ª ed.). Springer Vieweg. ISBN 978-3-658-11455-8.
19. Ross, IM (julio de 2019). "Una teoría de control óptima para optimización no lineal". Revista de Matemática Computacional y Aplicada . 354 : 39–51. doi : 10.1016/j.cam.2018.12.044 . S2CID  127649426.
20. Nesterov, Yurii (2004). Lecciones introductorias sobre optimización convexa: un curso básico . Springer. ISBN 1-4020-7553-7.
21. Vandenberghe, Lieven (2019). "Métodos de gradiente rápido" (PDF) . Apuntes de conferencias para EE236C en UCLA .
22. Walkington, Noel J. (2023). "Método de Nesterov para optimización convexa". SIAM Review . 65 (2): 539–562. doi :10.1137/21M1390037. ISSN  0036-1445.
23. Kim, D.; Fessler, JA (2016). "Métodos optimizados de primer orden para la minimización convexa suave". Programación matemática . 151 (1–2): 81–107. arXiv : 1406.5468 . doi :10.1007/s10107-015-0949-3. PMC 5067109 . PMID  27765996. S2CID  207055414. 
24. Drori, Yoel (2017). "La complejidad basada en información exacta de la minimización convexa suave". Journal of Complexity . 39 : 1–16. arXiv : 1606.01424 . doi :10.1016/j.jco.2016.11.001. S2CID  205861966.
25. Qian, Ning (enero de 1999). "Sobre el término momentum en algoritmos de aprendizaje de descenso de gradiente". Redes neuronales . 12 (1): 145–151. CiteSeerX 10.1.1.57.5612 . doi :10.1016/S0893-6080(98)00116-6. PMID  12662723. S2CID  2783597. 
26. "Momentum and Learning Rate Adaptation" (Adaptación del ritmo de aprendizaje y del impulso). Universidad de Willamette . Consultado el 17 de octubre de 2014 .
27. Geoffrey Hinton ; Nitish Srivastava; Kevin Swersky. "El método del momento". Coursera . Consultado el 2 de octubre de 2018 .Parte de una serie de conferencias para el curso en línea de Coursera Redes neuronales para aprendizaje automático Archivado el 31 de diciembre de 2016 en Wayback Machine .
28. Combettes, PL; Pesquet, J.-C. (2011). "Métodos de división proximal en el procesamiento de señales". En Bauschke, HH; Burachik, RS ; Combettes, PL; Elser, V.; Luke, DR; Wolkowicz, H. (eds.). Algoritmos de punto fijo para problemas inversos en ciencia e ingeniería . Nueva York: Springer. págs. 185–212. arXiv : 0912.3522 . ISBN 978-1-4419-9568-1.
29. "Algoritmo de descenso del espejo".
30. Bubeck, S. (2014). Teoría de optimización convexa para aprendizaje automático. ArXiv, abs/1405.4980.

Lectura adicional

• Boyd, Stephen ; Vandenberghe, Lieven (2004). "Minimización sin restricciones" (PDF) . Optimización convexa . Nueva York: Cambridge University Press. pp. 457–520. ISBN 0-521-83378-7.
• Chong, Edwin KP; Żak, Stanislaw H. (2013). "Métodos de gradiente". Introducción a la optimización (cuarta edición). Hoboken: Wiley. págs. 131–160. ISBN 978-1-118-27901-4.
• Himmelblau, David M. (1972). "Procedimientos de minimización sin restricciones utilizando derivadas". Programación no lineal aplicada . Nueva York: McGraw-Hill. pp. 63–132. ISBN 0-07-028921-2.

Enlaces externos

• Uso del descenso de gradiente en C++, Boost y Ublas para regresión lineal
• Una serie de vídeos de Khan Academy analiza el ascenso de gradientes
• Libro en línea que enseña el descenso de gradientes en el contexto de redes neuronales profundas
• Archivado en Ghostarchive y Wayback Machine: «Gradient Descent, How Neural Networks Learn». 3Blue1Brown . 16 de octubre de 2017, a través de YouTube .
• Manual de teoremas de convergencia para métodos de gradiente (estocástico)