Búsqueda de línea de retroceso

Método de optimización matemática.

En la optimización matemática (sin restricciones) , una búsqueda de líneas de retroceso es un método de búsqueda de líneas para determinar la cantidad a moverse a lo largo de una dirección de búsqueda determinada . Su uso requiere que la función objetivo sea diferenciable y que se conozca su gradiente .

El método implica comenzar con una estimación relativamente grande del tamaño del paso para el movimiento a lo largo de la dirección de búsqueda de la línea, y reducir iterativamente el tamaño del paso (es decir, "retroceder") hasta que se observe una disminución de la función objetivo que corresponda adecuadamente a la cantidad de disminución que se espera, según el tamaño del paso y el gradiente local de la función objetivo. Un criterio de interrupción común es la condición de Armijo-Goldstein.

La búsqueda de líneas de retroceso se utiliza normalmente para el descenso de gradiente (GD), pero también se puede utilizar en otros contextos. Por ejemplo, se puede utilizar con el método de Newton si la matriz de Hesse es definida positiva .

Motivación

Dada una posición inicial y una dirección de búsqueda , la tarea de una búsqueda lineal es determinar un tamaño de paso que reduzca adecuadamente la función objetivo (supuesta , es decir, continuamente diferenciable ), es decir, encontrar un valor de que se reduzca en relación con . Sin embargo, normalmente no es deseable dedicar recursos sustanciales a encontrar un valor de que minimice con precisión . Esto se debe a que los recursos informáticos necesarios para encontrar un mínimo más preciso a lo largo de una dirección particular podrían emplearse para identificar una mejor dirección de búsqueda. Una vez que la búsqueda de línea ha identificado un punto de partida mejorado, normalmente se realizará otra búsqueda de línea posterior en una nueva dirección. El objetivo, entonces, es simplemente identificar un valor de que proporcione una cantidad razonable de mejora en la función objetivo, en lugar de encontrar el valor minimizador real de . ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {p} }$ ${\displaystyle \alpha >0}$ ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$ ${\displaystyle C^{1}}$ ${\displaystyle \alpha }$ ${\displaystyle f(\mathbf {x} +\alpha \,\mathbf {p} )}$ ${\displaystyle f(\mathbf {x} )}$ ${\displaystyle \alpha }$ ${\displaystyle f}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$

La búsqueda de líneas de retroceso comienza con una estimación grande y la reduce iterativamente. La reducción continúa hasta que se encuentra un valor que es lo suficientemente pequeño como para proporcionar una disminución en la función objetivo que coincida adecuadamente con la disminución que se espera lograr, según el gradiente de la función local. ${\displaystyle \alpha }$ ${\displaystyle \nabla f(\mathbf {x} )\,.}$

Defina la pendiente local de la función de a lo largo de la dirección de búsqueda como (donde denota el producto escalar ). Se supone que es un vector para el cual es posible alguna disminución local, es decir, se supone que . ${\displaystyle \alpha }$ ${\displaystyle \mathbf {p} }$ ${\displaystyle m=\nabla f(\mathbf {x} )^{\mathrm {T} }\,\mathbf {p} =\langle \nabla f(\mathbf {x} ),\mathbf {p} \rangle }$ ${\displaystyle \langle \cdot ,\cdot \rangle }$ ${\displaystyle \mathbf {p} }$ ${\displaystyle m<0}$

Basándose en un parámetro de control seleccionado , la condición de Armijo-Goldstein prueba si un movimiento gradual desde una posición actual a una posición modificada logra una disminución adecuadamente correspondiente en la función objetivo. La condición se cumple, ver Armijo (1966), si ${\displaystyle c\,\in \,(0,1)}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {x} +\alpha \,\mathbf {p} }$ ${\displaystyle f(\mathbf {x} +\alpha \,\mathbf {p} )\leq f(\mathbf {x} )+\alpha \,c\,m\,.}$

Esta condición, cuando se utiliza adecuadamente como parte de una búsqueda de línea, puede garantizar que el tamaño del paso no sea excesivamente grande. Sin embargo, esta condición no es suficiente por sí sola para garantizar que el tamaño del paso sea casi óptimo, ya que cualquier valor de éste que sea suficientemente pequeño satisfará la condición. ${\displaystyle \displaystyle \alpha }$

Por lo tanto, la estrategia de búsqueda de líneas de retroceso comienza con un tamaño de paso relativamente grande y lo reduce repetidamente en un factor hasta que se cumple la condición de Armijo-Goldstein. ${\displaystyle \tau \,\in \,(0,1)}$

La búsqueda terminará después de un número finito de pasos para cualquier valor positivo de y que sea menor que 1. Por ejemplo, Armijo usó 1 ⁄ 2 para ambos y en Armijo (1966). ${\displaystyle c}$ ${\displaystyle \tau }$ ${\displaystyle c}$ ${\displaystyle \tau }$

Algoritmo

Esta condición es de Armijo (1966). Comenzando con un valor de tamaño de paso candidato máximo , utilizando los parámetros de control de búsqueda y , el algoritmo de búsqueda de línea de retroceso se puede expresar de la siguiente manera: ${\displaystyle \alpha _{0}>0\,}$ ${\displaystyle \tau \,\in \,(0,1)}$ ${\displaystyle c\,\in \,(0,1)}$

1. Conjunto y contador de iteraciones . ${\displaystyle t=-c\,m}$ ${\displaystyle j\,=\,0}$
2. Hasta que se cumpla la condición de que se incremente y establezca repetidamente ${\displaystyle f(\mathbf {x} )-f(\mathbf {x} +\alpha _{j}\,\mathbf {p} )\geq \alpha _{j}\,t,}$ ${\displaystyle j}$ ${\displaystyle \alpha _{j}=\tau \,\alpha _{j-1}\,.}$
3. Regresar como la solución. ${\displaystyle \alpha _{j}}$

En otras palabras, reducir por un factor de en cada iteración hasta que se cumpla la condición de Armijo-Goldstein. ${\displaystyle \alpha _{0}}$ ${\displaystyle \tau \,}$

Minimización de funciones mediante la búsqueda de líneas de retroceso en la práctica

En la práctica, el algoritmo anterior normalmente se itera para producir una secuencia , , para converger a un mínimo, siempre que dicho mínimo exista y se seleccione adecuadamente en cada paso. Para descenso de gradiente, se selecciona como . ${\displaystyle \mathbf {x} _{n}}$ ${\displaystyle n=1,2,...}$ ${\displaystyle \mathbf {p} _{n}}$ ${\displaystyle \mathbf {p} _{n}}$ ${\displaystyle -\nabla f(\mathbf {x} _{n})}$

El valor de para que cumple la condición de Armijo-Goldstein depende de y , por lo que a continuación se denota por . También depende de , y por supuesto, aunque estas dependencias pueden dejarse implícitas si se supone que están solucionadas con respecto al problema de optimización. ${\displaystyle \alpha _{j}}$ ${\displaystyle j}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {p} }$ ${\displaystyle \alpha (\mathbf {x} ,\mathbf {p} )}$ ${\displaystyle f}$ ${\displaystyle \alpha _{0}}$ ${\displaystyle \tau }$ ${\displaystyle c}$

Los pasos detallados son los siguientes, ver Armijo (1966), Bertsekas (2016):

1. Elija un punto de partida inicial y configure el contador de iteraciones . ${\displaystyle \mathbf {x} _{0}}$ ${\displaystyle n=0}$
2. Hasta que se cumpla alguna condición de parada, elija una dirección de descenso , actualice la posición a e incremente . ${\displaystyle \mathbf {p} _{n}}$ ${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}+\alpha (\mathbf {x} _{n},\mathbf {p} _{n})\,\mathbf {p} _{n}}$ ${\displaystyle n}$
3. Retorna como posición minimizadora y como mínimo de la función. ${\displaystyle \mathbf {x} _{n}}$ ${\displaystyle f(\mathbf {x} _{n})}$

Para asegurar un buen comportamiento, es necesario que se cumplan algunas condiciones . En términos generales, no debería estar demasiado lejos de . Una versión precisa es la siguiente (ver, por ejemplo, Bertsekas (2016)). Hay constantes para que se cumplan las dos condiciones siguientes: ${\displaystyle \mathbf {p} _{n}}$ ${\displaystyle \mathbf {p} _{n}}$ ${\displaystyle \nabla f(\mathbf {x} _{n})}$ ${\displaystyle C_{1},C_{2}>0}$

1. Para todo n, . Aquí está la norma euclidiana de . (Esto asegura que si , entonces también . Más generalmente, si , entonces también .) Una versión más estricta requiere también la desigualdad inversa: para una constante positiva . ${\displaystyle \|\mathbf {p} _{n}\|\geq C_{1}\,\|\nabla f(\mathbf {x} _{n})\|}$ ${\displaystyle \|y\|}$ ${\displaystyle y}$ ${\displaystyle \mathbf {p} _{n}=0}$ ${\displaystyle \nabla f(\mathbf {x} _{n})=0}$ ${\displaystyle \lim _{n\rightarrow \infty }\mathbf {p} _{n}=0}$ ${\displaystyle \lim _{n\rightarrow \infty }\nabla f(\mathbf {x} _{n})=0}$ ${\displaystyle \|\mathbf {p} _{n}\|\leq C_{3}\,\|\nabla f(\mathbf {x} _{n})\|}$ ${\displaystyle C_{3}>0}$
2. Para todo n, . (Esta condición garantiza que las direcciones de y sean similares). ${\displaystyle \|\mathbf {p} _{n}\|\,\|\nabla f(\mathbf {x} _{n})\|\leq -C_{2}\,\langle \mathbf {p} _{n},\nabla f(\mathbf {x} _{n})\rangle }$ ${\displaystyle \mathbf {p} _{n}}$ ${\displaystyle -\nabla f(\mathbf {x} _{n})}$

Límite inferior para las tasas de aprendizaje

Esto aborda la cuestión de si existe una manera sistemática de encontrar un número positivo , dependiendo de la función f, el punto y la dirección de descenso , de modo que todas las tasas de aprendizaje satisfagan la condición de Armijo. Cuando , podemos elegir en el orden de , dónde es una constante de Lipschitz local para el gradiente cerca del punto (ver Continuidad de Lipschitz ). Si la función es , entonces está cerca del hessiano de la función en el punto . Véase Armijo (1966) para más detalles. ${\displaystyle \beta (\mathbf {x} ,\mathbf {p} )}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {p} }$ ${\displaystyle \alpha \leq \beta (\mathbf {x} ,\mathbf {p} )}$ ${\displaystyle \mathbf {p} =-\nabla f(\mathbf {x} )}$ ${\displaystyle \beta (\mathbf {x} ,\mathbf {p} )}$ ${\displaystyle 1/L(\mathbf {x} )\,}$ ${\displaystyle L(\mathbf {x} )\,}$ ${\displaystyle \nabla f\,}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle C^{2}}$ ${\displaystyle L(\mathbf {x} )\,}$ ${\displaystyle \mathbf {x} }$

Límite superior para las tasas de aprendizaje

En la misma situación en la que , una pregunta interesante es qué tan grandes se pueden elegir tasas de aprendizaje en la condición de Armijo (es decir, cuando no se tiene límite como se define en la sección "Minimización de funciones mediante la búsqueda de líneas de retroceso en la práctica"), ya que el aprendizaje más grande Las tasas cuando están más cerca del punto límite (si existe) pueden hacer que la convergencia sea más rápida. Por ejemplo, en las condiciones de Wolfe , no se menciona pero se introduce otra condición llamada condición de curvatura. ${\displaystyle \mathbf {p} =-\nabla f(\mathbf {x} )}$ ${\displaystyle \alpha _{0}}$ ${\displaystyle \mathbf {x} _{n}}$ ${\displaystyle \alpha _{0}}$

Se muestra que existe un límite superior para las tasas de aprendizaje si se quiere que la secuencia construida converja a un punto crítico no degenerado , consulte Truong y Nguyen (2020): Las tasas de aprendizaje deben estar limitadas desde arriba aproximadamente por . Aquí H es el hessiano de la función en el punto límite, es su inversa y es la norma de un operador lineal . Por lo tanto, este resultado se aplica, por ejemplo, cuando se utiliza la búsqueda de líneas de retroceso para funciones Morse . Tenga en cuenta que en la dimensión 1, hay un número y, por lo tanto, este límite superior es del mismo tamaño que el límite inferior en la sección "Límite inferior para las tasas de aprendizaje". ${\displaystyle \mathbf {x} _{n}}$ ${\displaystyle ||H||\times ||H^{-1}||^{2}}$ ${\displaystyle H^{-1}}$ ${\displaystyle ||.||}$ ${\displaystyle H}$

Por otro lado, si el punto límite es degenerado, entonces las tasas de aprendizaje pueden ser ilimitadas. Por ejemplo, una modificación de la búsqueda de líneas de retroceso conocida como descenso de gradiente de retroceso ilimitado (ver Truong y Nguyen (2020)) permite que la tasa de aprendizaje sea la mitad del tamaño , donde es una constante. Los experimentos con funciones simples como muestran que el descenso de gradiente de retroceso ilimitado converge mucho más rápido que la versión básica descrita en la sección "Minimización de funciones mediante la búsqueda de líneas de retroceso en la práctica". ${\displaystyle ||\nabla f(\mathbf {x} _{n})||^{-\gamma }}$ ${\displaystyle 1>\gamma >0}$ ${\displaystyle f(x,y)=x^{4}+y^{4}}$

Eficiencia de tiempo

Un argumento en contra del uso de la búsqueda de líneas de retroceso, en particular en la optimización a gran escala, es que satisfacer la condición de Armijo es costoso. Existe una forma (el llamado retroceso bidireccional) de dar la vuelta, con buenas garantías teóricas y que ha sido probada con buenos resultados en redes neuronales profundas , ver Truong & Nguyen (2020). (Allí también se pueden encontrar implementaciones buenas/estables de la condición de Armijo y su combinación con algunos algoritmos populares como Momentum y NAG, en conjuntos de datos como Cifar10 y Cifar100). Se observa que si la secuencia converge (como se desea cuando se hace uso de un método de optimización iterativo), entonces la secuencia de tasas de aprendizaje debería variar poco cuando n es lo suficientemente grande. Por lo tanto, en la búsqueda de , si siempre se parte de , se perdería mucho tiempo si resulta que la secuencia queda alejada de . En lugar de ello, se debe buscar comenzando desde . La segunda observación es que podría ser mayor que y, por lo tanto, se debería permitir aumentar la tasa de aprendizaje (y no solo disminuirla como en la sección Algoritmo). Aquí está el algoritmo detallado para el retroceso bidireccional: en el paso n ${\displaystyle \mathbf {x} _{n}}$ ${\displaystyle \alpha _{n}}$ ${\displaystyle \alpha _{n}}$ ${\displaystyle \alpha _{0}}$ ${\displaystyle \alpha _{n}}$ ${\displaystyle \alpha _{0}}$ ${\displaystyle \alpha _{n}}$ ${\displaystyle \alpha _{n-1}}$ ${\displaystyle \alpha _{n}}$ ${\displaystyle \alpha _{n-1}}$

1. Colocar . Conjunto y contador de iteraciones . ${\displaystyle \gamma _{0}=\alpha _{n-1}}$ ${\displaystyle t=-c\,m}$ ${\displaystyle j\,=\,0}$
2. (Aumente la tasa de aprendizaje si se cumple la condición de Armijo). Si , mientras esta condición y la condición que se cumplen, establezca y aumente repetidamente j. ${\displaystyle f(\mathbf {x} )-f(\mathbf {x} +\gamma _{j}\,\mathbf {p} )\geq \gamma _{j}\,t,}$ ${\displaystyle \gamma _{j}\leq \alpha _{0}}$ ${\displaystyle \gamma _{j+1}=\gamma _{j}/\tau }$
3. (De lo contrario, reduzca la tasa de aprendizaje si no se cumple la condición de Armijo). Si, por el contrario , hasta que se cumpla la condición, se incrementará y establecerá repetidamente ${\displaystyle f(\mathbf {x} )-f(\mathbf {x} +\gamma _{0}\,\mathbf {p} )<\gamma _{j}\,t,}$ ${\displaystyle f(\mathbf {x} )-f(\mathbf {x} +\gamma _{j}\,\mathbf {p} )\geq \gamma _{j}\,t,}$ ${\displaystyle j}$ ${\displaystyle \gamma _{j}=\tau \,\gamma _{j-1}\,.}$
4. Retorno por la tasa de aprendizaje . ${\displaystyle \gamma _{j}}$ ${\displaystyle \alpha _{n}}$

(En Nocedal y Wright (2000) se puede encontrar una descripción de un algoritmo con los puntos 1), 3) y 4) anteriores, que no se probó en redes neuronales profundas antes del artículo citado).

Se puede ahorrar aún más tiempo mediante una combinación híbrida entre el retroceso bidireccional y el algoritmo básico estándar de descenso de gradiente. Este procedimiento también tiene una buena garantía teórica y un buen rendimiento en las pruebas. En términos generales, ejecutamos el retroceso bidireccional varias veces y luego usamos la tasa de aprendizaje que obtenemos sin cambios, excepto si el valor de la función aumenta. Así es precisamente como se hace. Uno elige de antemano un número , y un número . ${\displaystyle N}$ ${\displaystyle m\leq N}$

1. Establezca el contador de iteraciones j=0.
2. En los pasos , utilice el retroceso bidireccional. ${\displaystyle jN+1,\ldots ,jN+m}$
3. En cada paso k del conjunto : Establecer . Si , entonces elija y . (Entonces, en este caso, use la tasa de aprendizaje sin cambios). De lo contrario, si , use el retroceso bidireccional. Aumenta k en 1 y repite. ${\displaystyle jN+m+1,\ldots ,jN+N-1}$ ${\displaystyle \alpha =\alpha _{k-2}}$ ${\displaystyle f(x_{k-1})-f(x_{k-1}+\alpha p_{k-1})\geq 0}$ ${\displaystyle \alpha _{k-1}=\alpha _{k-2}}$ ${\displaystyle x_{k}=x_{k-1}+\alpha _{k-1}p_{k-1}}$ ${\displaystyle \alpha _{k-2}}$ ${\displaystyle f(x_{k-1})-f(x_{k-1}+\alpha p_{k-1})<0}$
4. Aumenta j en 1.

Garantía teórica (para descenso de gradiente)

En comparación con las condiciones de Wolfe, que son más complicadas, la condición de Armijo tiene una mejor garantía teórica. De hecho, hasta ahora la búsqueda de líneas hacia atrás y sus modificaciones son los métodos más garantizados teóricamente entre todos los algoritmos de optimización numérica relacionados con la convergencia a puntos críticos y la evitación de puntos silla , ver más abajo.

Los puntos críticos son puntos donde el gradiente de la función objetivo es 0. Los mínimos locales son puntos críticos, pero hay puntos críticos que no son mínimos locales. Un ejemplo son los puntos de silla. Los puntos silla son puntos críticos, en los que hay al menos una dirección donde la función es máxima (local). Por tanto, estos puntos están lejos de ser mínimos locales. Por ejemplo, si una función tiene al menos un punto silla, entonces no puede ser convexa . La relevancia de los puntos silla para los algoritmos de optimización es que en la optimización a gran escala (es decir, de alta dimensión), es probable que se vean más puntos silla que mínimos, ver Bray y Dean (2007). Por lo tanto, un buen algoritmo de optimización debería poder evitar los puntos de silla. En el contexto del aprendizaje profundo , los puntos de silla también prevalecen, ver Dauphin et al. (2014). Por lo tanto, para aplicarlo en el aprendizaje profundo, se necesitan resultados para funciones no convexas.

Para la convergencia a puntos críticos: por ejemplo, si la función de costos es una función analítica real , Absil, Mahony y Andrews (2005) muestran que la convergencia está garantizada. La idea principal es utilizar la desigualdad de Łojasiewicz de la que disfruta una función analítica real. Para funciones no suaves que satisfacen la desigualdad de Łojasiewicz , la garantía de convergencia anterior se amplía; consulte Attouch, Bolte y Svaiter (2011). En Bertsekas (2016), hay una prueba de que para cada secuencia construida mediante búsqueda de líneas de retroceso, un punto de grupo (es decir, el límite de una subsecuencia , si la subsecuencia converge) es un punto crítico. Para el caso de una función con como máximo un número contable de puntos críticos (como una función Morse ) y subniveles compactos , así como con gradiente continuo de Lipschitz donde se usa GD estándar con tasa de aprendizaje <1/L (consulte la sección "Gradiente estocástico descenso"), entonces la convergencia está garantizada; véase, por ejemplo, el capítulo 12 de Lange (2013). Aquí, el supuesto sobre los subniveles compactos es garantizar que se trate únicamente de conjuntos compactos del espacio euclidiano. En el caso general, donde solo se supone que hay y tienen, como máximo, un número contable de puntos críticos, la convergencia está garantizada, véase Truong y Nguyen (2020). En la misma referencia, se garantiza una convergencia similar para otras modificaciones de la búsqueda de líneas de retroceso (como el descenso de gradiente de retroceso ilimitado mencionado en la sección "Límite superior para las tasas de aprendizaje"), e incluso si la función tiene innumerables puntos críticos, aún se pueden deducir algunos hechos no triviales sobre el comportamiento de convergencia. En el entorno estocástico, bajo el mismo supuesto de que el gradiente es continuo de Lipschitz y se usa una versión más restrictiva (que requiere además que la suma de las tasas de aprendizaje sea infinita y la suma de los cuadrados de las tasas de aprendizaje sea finita) del esquema de tasas de aprendizaje decrecientes. (ver sección "Descenso de gradiente estocástico") y además la función es estrictamente convexa, entonces la convergencia se establece en el conocido resultado Robbins & Monro (1951), ver Bertsekas & Tsitsiklis (2006) para generalizaciones a versiones menos restrictivas de una esquema de tasa de aprendizaje decreciente. Ninguno de estos resultados (para funciones no convexas) se ha probado hasta ahora para ningún otro algoritmo de optimización. ^{[ cita necesaria ]} ${\displaystyle f}$ ${\displaystyle C^{1}}$

Para evitar puntos silla: por ejemplo, si el gradiente de la función de costos es continuo de Lipschitz y se elige GD estándar con una tasa de aprendizaje <1/L, entonces con una elección aleatoria del punto inicial (más precisamente, fuera de un conjunto de medidas de Lebesgue cero), la secuencia construida no convergerá a un punto silla no degenerado (probado en Lee et al. (2016)) y, de manera más general, también es cierto que la secuencia construida no convergerá a un punto silla degenerado (probado en Panageas y Piliouras (2017)). Bajo el mismo supuesto de que el gradiente es continuo de Lipschitz y se utiliza un esquema de tasa de aprendizaje decreciente (consulte la sección "Descenso de gradiente estocástico"), en Panageas, Piliouras y Wang (2019) se establece la evitación de los puntos silla. ${\displaystyle \mathbf {x} _{0}}$

Un caso especial: descenso de gradiente estocástico (SGD) (estándar)

Si bien es trivial mencionarlo, si el gradiente de una función de costos es continuo de Lipschitz, con la constante de Lipschitz L, entonces al elegir que la tasa de aprendizaje sea constante y del tamaño , uno tiene un caso especial de búsqueda de línea de retroceso (para descenso de gradiente) . Esto ha sido utilizado al menos en Armijo (1966). Sin embargo, este esquema requiere que se tenga una buena estimación de L; de lo contrario, si la tasa de aprendizaje es demasiado grande (en relación con 1/L), el esquema no tiene garantía de convergencia. Se puede ver qué saldrá mal si la función de costos es un suavizado (cerca del punto 0) de la función f(t)=|t|. Sin embargo, una estimación tan buena es difícil y laboriosa en dimensiones grandes. Además, si el gradiente de la función no es globalmente continuo de Lipschitz, entonces este esquema no tiene garantía de convergencia. Por ejemplo, esto es similar a un ejercicio de Bertsekas (2016), para la función de costos y para cualquier tasa de aprendizaje constante que se elija, con un punto inicial aleatorio la secuencia construida por este esquema especial no converge al mínimo global 0. ${\displaystyle 1/L}$ ${\displaystyle f(t)=|t|^{1.5}\,}$

Si a uno no le importa la condición de que la tasa de aprendizaje debe estar limitada por 1/L, entonces este esquema especial se ha utilizado mucho antes, al menos desde 1847 por Cauchy , que puede denominarse GD estándar (no debe confundirse con el gradiente estocástico). descendencia, que en este documento se abrevia como SGD). En la configuración estocástica (como en la configuración de mini lotes en el aprendizaje profundo), el GD estándar se llama descenso de gradiente estocástico o SGD.

Incluso si la función de costo tiene un gradiente globalmente continuo, una buena estimación de la constante de Lipschitz para las funciones de costo en el aprendizaje profundo puede no ser factible o deseable, dadas las dimensiones muy altas de las redes neuronales profundas . Por lo tanto, existe una técnica para ajustar las tasas de aprendizaje al aplicar GD o SGD estándar. Una forma es elegir muchas tasas de aprendizaje de una búsqueda en la cuadrícula, con la esperanza de que algunas de las tasas de aprendizaje puedan dar buenos resultados. (Sin embargo, si la función de pérdida no tiene un gradiente continuo global de Lipschitz, entonces el ejemplo anterior muestra que la búsqueda en cuadrícula no puede ayudar). Otra forma es el llamado estándar adaptativo GD o SGD, algunos representantes son Adam, Adadelta, RMSProp y y así sucesivamente, consulte el artículo sobre el descenso del gradiente estocástico . En GD o SGD estándar adaptativo, se permite que las tasas de aprendizaje varíen en cada paso de iteración n, pero de una manera diferente a la búsqueda de línea de retroceso para el descenso de gradiente. Aparentemente, sería más costoso usar la búsqueda de línea de retroceso para el descenso de gradiente, ya que es necesario realizar una búsqueda en bucle hasta que se cumpla la condición de Armijo, mientras que para el GD o SGD estándar adaptativo no se necesita una búsqueda en bucle. La mayoría de estos GD o SGD estándar adaptativos no tienen la propiedad de descenso , para todos los n, como búsqueda de línea de retroceso para el descenso de gradiente. Sólo unos pocos tienen esta propiedad y tienen buenas propiedades teóricas, pero resultan ser casos especiales de búsqueda de líneas de retroceso o, más generalmente, la condición de Armijo (1966). La primera es cuando se elige que la tasa de aprendizaje sea una constante <1/L, como se mencionó anteriormente, si se puede tener una buena estimación de L. La segunda es la llamada tasa de aprendizaje decreciente, utilizada en el conocido artículo de Robbins y Monro (1951), si nuevamente la función tiene un gradiente global continuo de Lipschitz (pero la constante de Lipschitz puede ser desconocida) y las tasas de aprendizaje convergen a 0. ${\displaystyle f(t)=|t|^{1.5}\,}$ ${\displaystyle f(x_{n+1})\leq f(x_{n})}$

Resumen

En resumen, la búsqueda de líneas de retroceso (y sus modificaciones) es un método fácil de implementar, aplicable a funciones muy generales, tiene muy buena garantía teórica (tanto para la convergencia a puntos críticos como para evitar puntos silla) y funciona bien en la práctica. . Varios otros métodos que tienen una buena garantía teórica, como tasas de aprendizaje decrecientes o GD estándar con una tasa de aprendizaje <1/L (ambos requieren que el gradiente de la función objetivo sea continuo de Lipschitz), resultan ser un caso especial de búsqueda de línea de retroceso o satisfacer la condición de Armijo. Aunque a priori se necesita que la función de costos sea continuamente diferenciable para aplicar este método, en la práctica se puede aplicar este método con éxito también para funciones que son continuamente diferenciables en un subconjunto abierto denso como o . ${\displaystyle f(t)=|t|}$ ${\displaystyle f(t)=ReLu(t)=\max\{t,0\}}$

Ver también

• Descenso de gradiente
• Descenso de gradiente estocástico
• condiciones de lobo

Referencias

• Absil, PA; Mahony, R.; Andrews, B. (2005). "Convergencia de las iteraciones de métodos de descenso para funciones analíticas de costos". SIAM J. Optim. 16 (2): 531–547. doi :10.1137/040605266.
• Armijo, Larry (1966). "Minimización de funciones que tienen primeras derivadas parciales continuas de Lipschitz". Pacífico J. Matemáticas . 16 (1): 1–3. doi : 10.2140/pjm.1966.16.1 .
• Attouch, H.; Bolté, J.; Svaiter, BF (2011). "Convergencia de métodos de descenso para problemas semialgebraicos y sencillos: algoritmos proximales, división hacia adelante y hacia atrás y métodos regularizados de Gauss-Seidel". Programación Matemática . 137 (1–2): 91–129. doi : 10.1007/s10107-011-0484-9 .
• Bertsekas, Dimitri P. (2016), Programación no lineal, Athena Scientific , ISBN 978-1886529052
• Bertsekas, DP; Tsitsiklis, JN (2006). "Convergencia de gradientes en métodos de gradiente con errores". SIAM J. Optim. 10 (3): 627–642. CiteSeerX  10.1.1.421.193 . doi : 10.1137/S1052623497331063 .
• Bray, AJ; Decano, DS (2007). "Estadísticas de puntos críticos de campos gaussianos en espacios de grandes dimensiones". Cartas de revisión física . 98 (15): 150-201. arXiv : cond-mat/0611023 . Código bibliográfico : 2007PhRvL..98o0201B. doi : 10.1103/PhysRevLett.98.150201 . PMID  17501322.
• Dauphin, YN; Pascanu, R.; Gulcehre, C.; Cho, K.; Ganguli, S.; Bengio, Y. (2014). "Identificar y atacar el problema del punto de silla en optimización no convexa de alta dimensión". NeurIPS . 14 : 2933–2941. arXiv : 1406.2572 .
• Lange, K. (2013). Optimización . Nueva York: Publicaciones Springer-Verlag . ISBN 978-1-4614-5838-8.
• Dennis, JE ; Schnabel, RB (1996). Métodos numéricos para optimización sin restricciones y ecuaciones no lineales . Filadelfia: Publicaciones SIAM . ISBN 978-0-898713-64-0.
• Lee, JD; Simchowitz, M.; Jordania, Michigan; Recht, B. (2016). "El descenso de gradiente sólo converge hacia los minimizadores". Actas de investigación sobre aprendizaje automático . 49 : 1246-1257.
• Nocedal, Jorge ; Wright, Stephen J. (2000), Optimización numérica, Springer-Verlag , ISBN 0-387-98793-2
• Panageas, I.; Piliouras, G. (2017). "El descenso de gradiente sólo converge hacia minimizadores: puntos críticos no aislados y regiones invariantes". 8.° Congreso de Innovaciones en Informática Teórica (ITCS 2017) (PDF) . Procedimientos internacionales de informática de Leibniz (LIPIcs). vol. 67. págs. 2:1–2:12. doi : 10.4230/LIPIcs.ITCS.2017.2 . ISBN 9783959770293.
• Panageas, I.; Piliouras, G.; Wang, X. (2019). "Los métodos de primer orden casi siempre evitan los puntos silla: el caso de la desaparición de los tamaños de paso" (PDF) . NeurIPS . arXiv : 1906.07772 .
• Robbins, H.; Monro, S. (1951). "Un método de aproximación estocástica". Anales de estadística matemática . 22 (3): 400–407. doi : 10.1214/aoms/1177729586 .
• Truong, TT; Nguyen, H.-T. (6 de septiembre de 2020). "Método de descenso de gradiente de retroceso y algunas aplicaciones en optimización a gran escala. Parte 2: algoritmos y experimentos". Matemáticas Aplicadas y Optimización . 84 (3): 2557–2586. doi : 10.1007/s00245-020-09718-8 . hdl : 10852/79322 .{{cite journal}}: CS1 maint: date and year (link)