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 encontrar un mínimo local de una función multivariada diferenciable .

La idea es dar pasos repetidos en la dirección opuesta al 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, avanzar en la dirección del gradiente conducirá a un máximo local de esa función; el procedimiento se conoce entonces como ascenso en 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 de optimización .

El descenso de gradiente se atribuye generalmente 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 fue cada vez más estudiado y utilizado 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 que se utiliza 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 una vecindad de un punto , entonces disminuye más rápido si uno va 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})}$

entonces, para un tamaño de paso o tasa de aprendizaje lo suficientemente pequeño . En otras palabras, el término se resta porque queremos avanzar en contra del gradiente, hacia el mínimo local. Con esta observación en mente, se comienza con una estimación de un mínimo local de y se 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 ,}$

entonces, con suerte, la secuencia converge 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 . Estos 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 puede encontrar mediante la búsqueda de líneas ). 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á definido en el plano y que su gráfica tiene forma de cuenco . Las curvas azules son las líneas de contorno , 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. Tenga en cuenta 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 de gradientes

Niebla en las montañas

La intuición básica detrás del descenso de gradientes se puede ilustrar mediante un escenario hipotético. Una persona está atrapada en las montañas y está tratando de bajar (es decir, tratando de encontrar el mínimo global). Hay una densa niebla que hace que la visibilidad sea extremadamente baja. Por lo tanto, el camino que baja de la montaña no es visible, por lo que deben utilizar información local para encontrar el mínimo. Pueden utilizar el método de descenso en gradiente, que implica observar la pendiente 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 empinado (es decir, cuesta arriba). Usando este método, eventualmente encontrarían el camino hacia la montaña o posiblemente se quedarían atrapados en algún agujero (es decir, un mínimo local o un punto de silla ), como un lago de montaña. Sin embargo, supongamos también que la pendiente de la colina no es inmediatamente obvia con una simple observación, sino que requiere un instrumento sofisticado para medirlo, que la persona tiene en ese momento. Se necesita bastante tiempo para medir la pendiente de la colina con el instrumento, por lo que deberían minimizar el uso del instrumento si quisieran bajar de la montaña antes del atardecer. La dificultad entonces es elegir la frecuencia con la que deben medir la pendiente de la colina para no desviarse del camino.

En esta analogía, la persona representa el algoritmo y el camino tomado montaña abajo representa la secuencia de configuraciones de parámetros que explorará el algoritmo. La pendiente de la colina representa la pendiente de la función en ese punto. El instrumento utilizado para medir la pendiente es la diferenciación . La dirección 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 medición es el tamaño del paso.

Elegir el tamaño del paso y la dirección de descenso

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

Para razonar matemáticamente sobre esto, 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, dejar de denotar 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 ) podría optimizarse y elegir un tamaño y dirección de paso ó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 utilice la búsqueda de líneas 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 de líneas retrospectivas , un método que tiene buenas garantías teóricas y resultados experimentales. Tenga en cuenta que no es necesario elegir ser el degradado; 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, use 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 sea Lipschitz , use su constante de Lipschitz para limitar 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}}$
• Cree un modelo personalizado de . 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 sólidos sobre la función, 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 también son 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 real 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íneas , encontrando 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 óptimo local. ^{[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 de descenso de 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áximo y mínimo de ) , mientras que la convergencia del método de gradiente conjugado generalmente está determinada por 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 del gradiente.

Considere el sistema no lineal de ecuaciones.

${\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 suposición inicial, usemos

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

Lo sabemos

${\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 de 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 bien, 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 una variedad de algoritmos de búsqueda de líneas . También se podría 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 a 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 desde el valor del siguiente paso de ${\displaystyle F(\mathbf {0} )=58.456}$

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

es una disminución considerable en la función objetivo. Otros pasos reducirían aún más su valor hasta que se encontrara una solución aproximada al sistema.

Comentarios

El descenso de gradiente funciona en espacios de cualquier número de dimensiones, incluso en espacios de dimensiones infinitas. En el último caso, el espacio de búsqueda suele ser un espacio funcional y se calcula la derivada de Fréchet del funcional que se va a minimizar para determinar la dirección de descenso. ^[7]

El hecho de que el descenso de gradiente funcione en cualquier número de dimensiones (al menos en un número finito) puede verse como 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, eso sería cuando el vector de ajustes de variables independientes es proporcional al vector de gradiente de 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 precondicionamiento , que cambia la geometría del espacio para dar forma a los conjuntos de niveles de función como círculos concéntricos , cura la convergencia lenta. Sin embargo, construir y aplicar el precondicionamiento puede resultar costoso desde el punto de vista computacional.

El descenso de gradiente se puede combinar con una búsqueda de líneas , encontrando el tamaño de paso localmente óptimo en cada iteración. Realizar la búsqueda de líneas puede llevar mucho tiempo. Por el contrario, utilizar un valor fijo pequeño puede generar una mala convergencia y un valor grande puede conducir a una divergencia. Sin embargo, 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, estos 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 que se multiplica el vector gradiente para ir en una "mejor" dirección, combinada con un algoritmo de búsqueda lineal más sofisticado , para encontrar el "mejor" valor de Para extremadamente En problemas grandes, donde dominan los problemas de memoria de la computadora, se debe usar 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: aunque 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 solución. .

Se puede considerar que el descenso de gradiente aplica el método de Euler para resolver ecuaciones diferenciales ordinarias a un flujo de gradiente . A su vez, esta ecuación se puede derivar como un controlador óptimo ^[19] para el sistema de control 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 del gradiente puede converger a un mínimo local y desacelerarse en las proximidades de un punto de silla . Incluso para la minimización cuadrática sin restricciones, el descenso de gradiente desarrolla un patrón en zig-zag de iteraciones posteriores a medida que avanzan las iteraciones, lo que resulta en 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 y sin restricciones, el método se denomina 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 sea fuertemente convexa , entonces el error en el valor objetivo generado en cada paso por el método de descenso de gradiente estará acotado por . Utilizando 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 costos 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 óptimo de primer orden 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, la FGM de Nesterov se denomina método de gradiente proximal rápido (FPGM), una aceleración del método de gradiente proximal .

Método del momento o bola pesada

Al intentar romper el patrón en zig-zag del descenso del gradiente, el método del impulso o de la bola pesada utiliza un término de impulso en analogía con una bola pesada que se desliza sobre la superficie de los valores de la función que se minimiza, ^[6] o con el movimiento de masas en la dinámica newtoniana. a través de un medio viscoso en un campo de fuerza conservador . ^[25] El descenso de gradiente con impulso 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 de tasa de convergencia teórica del método de la bola pesada es asintóticamente el mismo que el del método de 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 la 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 ampliar para manejar restricciones incluyendo una proyección sobre el conjunto de restricciones. Este método sólo 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 hacia adelante-hacia atrás 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 de descenso de gradiente utilizada (por ejemplo, si se utiliza un paso de búsqueda de línea ). Los supuestos realizados afectan la tasa de convergencia y otras propiedades que pueden demostrarse para el descenso de gradiente. ^[30] Por ejemplo, si se supone que el objetivo es fuertemente convexo y el lipschitz suave , entonces el descenso del gradiente converge linealmente con un tamaño de paso fijo. ^[1] Los supuestos más flexibles conducen a garantías de convergencia más débiles o requieren una selección del tamaño del paso más sofisticada. ^[30]

Ver también

• Búsqueda de línea de retroceso
• Método de gradiente conjugado
• Descenso de gradiente estocástico
• Rprop
• regla delta
• condiciones de lobo
• Preacondicionamiento
• Algoritmo de Broyden-Fletcher-Goldfarb-Shanno
• Fórmula de Davidon-Fletcher-Powell
• Método Nelder-Mead
• Algoritmo de Gauss-Newton
• Montañismo
• recocido cuántico
• CLS (búsqueda local continua)
• Neuroevolución

Referencias

1. Boyd, Stephen; Vandenberghe, Lieven (8 de marzo de 2004). Optimizacion convexa. Prensa de la Universidad de Cambridge. ISBN 978-0-521-83378-3.
2. Lemaréchal, C. (2012). "Cauchy y el método del gradiente" (PDF) . Doc Matemáticas Extra : 251–254.
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 Estadounidense . 49 (1): 1–23. doi : 10.1090/S0002-9904-1943-07818-4 .
5. Curry, Haskell B. (1944). "El método de descenso más pronunciado para problemas de minimización no lineal". Cuarto de galón. Aplica. Matemáticas . 2 (3): 258–261. doi : 10.1090/qam/10667 .
6. Polyak, Boris (1987). Introducción a la Optimización.
7. Akilov, médico de cabecera; Kantorovich, LV (1982). Análisis funcional (2ª ed.). Prensa de Pérgamo. ISBN 0-08-023036-9.
8. Barzilai, Jonathan; Borwein, Jonathan M. (1988). "Métodos de gradiente de tamaño de paso de dos puntos". Revista IMA de Análisis Numérico . 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". Revisión SIAM . 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ág. 108-142, 217-242
13. Saad, Yousef (2003). Métodos iterativos para sistemas lineales dispersos (2ª ed.). Filadelfia, Pensilvania: Sociedad de Matemáticas Industriales y Aplicadas. págs.195. ISBN 978-0-89871-534-7.
14. Bouwmeester, Henricus; Dougherty, Andrés; Knyazev, Andrés V. (2015). "Precondicionamiento no simétrico para métodos de gradiente conjugado y descenso más pronunciado". Procedia Ciencias de la Computación . 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 la optimización convexa (Tesis de tesis). Instituto de Tecnología de Massachusetts.
16. Parshall, Allison (11 de agosto de 2023). "Pasos gigantes y arriesgados pueden resolver problemas de optimización más rápido". Revista Quanta . Consultado el 11 de agosto de 2023 .
17. Presione, WH ; Teukolsky, SA ; Vetterling, WT; Flannery, BP (1992). Recetas numéricas en C: el arte de la informática 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 (2ª ed.). Springer Vieweg. ISBN 978-3-658-11455-8.
19. Ross, IM (julio de 2019). "Una teoría de control óptimo para la 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). Conferencias introductorias sobre optimización convexa: un curso básico . Saltador. 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 la optimización convexa". Revisión SIAM . 65 (2): 539–562. doi :10.1137/21M1390037. ISSN  0036-1445.
23. Kim, D.; Fessler, JA (2016). "Métodos optimizados de primer orden para una 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 exacta basada en información de la minimización convexa suave". Revista de Complejidad . 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 de impulso 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. "Adaptación del impulso y la tasa de aprendizaje". Universidad de Willamette . Consultado el 17 de octubre de 2014 .
27. Geoffrey Hinton ; Nitish Srivastava; Kevin Swersky. "El método del impulso". 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 el 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.; Lucas, 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 de espejos".
30. Bubeck, S. (2014). Teoría de la optimización convexa para el aprendizaje automático. ArXiv, abs/1405.4980.

Otras lecturas

• Boyd, Esteban ; Vandenberghe, Lieven (2004). "Minimización sin restricciones" (PDF) . Optimizacion convexa . Nueva York: Cambridge University Press. págs. 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 ed.). Hoboken: Wiley. págs. 131-160. ISBN 978-1-118-27901-4.
• Himmelblau, David M. (1972). "Procedimientos de minimización sin restricciones mediante derivados". Programación no lineal aplicada . Nueva York: McGraw-Hill. págs. 63-132. ISBN 0-07-028921-2.

enlaces externos

• Uso del descenso de gradiente en C++, Boost, Ublas para regresión lineal
• Una serie de vídeos de Khan Academy analiza el ascenso del gradiente
• Libro en línea que enseña el descenso de gradientes en el contexto de redes neuronales profundas
• Archivado en Ghostarchive y Wayback Machine: "Descenso de gradiente, cómo aprenden las redes neuronales". 3Azul1Marrón . 16 de octubre de 2017 - vía YouTube .
• Manual de teoremas de convergencia para métodos de gradiente (estocásticos)