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ínea de retroceso es un método de búsqueda de línea para determinar la cantidad de movimiento a lo largo de una dirección de búsqueda dada . 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, en función del tamaño del paso y el gradiente local de la función objetivo. Un criterio de detención común es la condición de Armijo-Goldstein.

La búsqueda de línea 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 para minimizar 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 en cambio para identificar una mejor dirección de búsqueda. Una vez que la búsqueda lineal ha identificado un punto de partida mejorado, normalmente se realizará otra búsqueda lineal 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ínea 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 cierta 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 escalonado desde una posición actual a una posición modificada logra una disminución correspondiente adecuada en la función objetivo. La condición se cumple, véase 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 que sea lo suficientemente pequeño satisfará la condición. ${\displaystyle \displaystyle \alpha }$

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

La búsqueda finalizará 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 y en Armijo (1966). ${\displaystyle c}$ ${\displaystyle \tau }$ ${\displaystyle c}$ ${\displaystyle \tau }$

Algoritmo

Esta condición es de Armijo (1966). Partiendo de un valor de tamaño de paso candidato máximo , utilizando 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 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 búsqueda de línea con retroceso en la práctica

En la práctica, el algoritmo anterior se suele iterar para producir una secuencia , , para converger a un mínimo, siempre que dicho mínimo exista y se seleccione de forma adecuada en cada paso. Para el 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 el que cumple la condición de Armijo–Goldstein depende de y , y por lo tanto se denota a continuación por . También depende de , , y por supuesto, aunque estas dependencias pueden dejarse implícitas si se supone que son fijas 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, véase 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 detención, 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. Regresa como la posición minimizada y como el 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 por . En términos generales, no debería estar demasiado lejos de . Una versión precisa es la siguiente (véase, 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í, es la norma euclidiana de . (Esto asegura que si , entonces también . De manera más general, 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 asegura 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 forma sistemática de encontrar un número positivo -dependiente 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 , donde es una constante de Lipschitz local para el gradiente cerca del punto (véase Continuidad de Lipschitz ). Si la función es , entonces es cercana al 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 pueden elegirse las tasas de aprendizaje en la condición de Armijo (es decir, cuando no se tiene límite en como se define en la sección "Minimización de funciones usando búsqueda de línea de retroceso en la práctica"), ya que las tasas de aprendizaje más grandes cuando está 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 desea que la secuencia construida converja a un punto crítico no degenerado , consulte Truong y Nguyen (2020): Las tasas de aprendizaje deben estar acotadas 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ínea de retroceso para funciones Morse . Tenga en cuenta que en la dimensión 1, es 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 está degenerado, entonces las tasas de aprendizaje pueden ser ilimitadas. Por ejemplo, una modificación de la búsqueda de línea de retroceso conocida como descenso de gradiente de retroceso ilimitado (ver Truong & Nguyen (2020)) permite que la tasa de aprendizaje sea la mitad del tamaño de , 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 usando la búsqueda de línea 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ínea de retroceso, en particular en la optimización a gran escala, es que satisfacer la condición de Armijo es costoso. Hay una forma (llamada retroceso bidireccional) de evitarlo, con buenas garantías teóricas y que se ha probado con buenos resultados en redes neuronales profundas , véase Truong y 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 empieza desde , se perdería mucho tiempo si resulta que la secuencia se mantiene lejos de . En cambio, se debería buscar empezando 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. Conjunto . Conjunto y contador de iteraciones . ${\displaystyle \gamma _{0}=\alpha _{n-1}}$ ${\displaystyle t=-c\,m}$ ${\displaystyle j\,=\,0}$
2. (Aumenta la tasa de aprendizaje si se cumple la condición de Armijo). Si , entonces mientras esta condición y la condición que se cumplen se establecen repetidamente y se incrementa 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 , , entonces hasta que se cumpla la condición, incremente y establezca 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 de la tasa de aprendizaje . ${\displaystyle \gamma _{j}}$ ${\displaystyle \alpha _{n}}$

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

Se puede ahorrar tiempo aún más con una mezcla híbrida entre el backtracking bidireccional y el algoritmo básico de descenso de gradiente estándar. Este procedimiento también tiene una buena garantía teórica y un buen rendimiento de prueba. En términos generales, ejecutamos el backtracking bidireccional unas cuantas veces, luego usamos la tasa de aprendizaje que obtenemos de entonces sin cambios, excepto si el valor de la función aumenta. Aquí es exactamente cómo se hace. Se elige de antemano un número y un número . ${\displaystyle N}$ ${\displaystyle m\leq N}$

1. Establezca el contador de iteración j=0.
2. En los pasos , utilice el retroceso bidireccional. ${\displaystyle jN+1,\ldots ,jN+m}$
3. En cada paso k del conjunto : Establezca . Si , entonces elija y . (Por lo tanto, en este caso, utilice la tasa de aprendizaje sin cambios). De lo contrario, si , utilice el retroceso bidireccional. Aumente k en 1 y repita. ${\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 mayor garantía teórica. De hecho, hasta ahora, la búsqueda de línea de retroceso y sus modificaciones son los métodos con mayor garantía teórica entre todos los algoritmos de optimización numérica en lo que respecta a la convergencia a puntos críticos y la evitación de puntos de silla , véase más adelante.

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 de silla son puntos críticos, en los que hay al menos una dirección donde la función es máxima (local). Por lo tanto, estos puntos están lejos de ser mínimos locales. Por ejemplo, si una función tiene al menos un punto de silla, entonces no puede ser convexa . La relevancia de los puntos de 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 de silla que mínimos, consulte Bray y Dean (2007). Por lo tanto, un buen algoritmo de optimización debería poder evitar los puntos de silla. En el entorno del aprendizaje profundo , los puntos de silla también prevalecen, consulte Dauphin et al. (2014). Por lo tanto, para aplicar 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 costo es una función analítica real , entonces se muestra en Absil, Mahony y Andrews (2005) que la convergencia está garantizada. La idea principal es utilizar la desigualdad de Łojasiewicz que disfruta una función analítica real. Para funciones no suaves que satisfacen la desigualdad de Łojasiewicz , se extiende la garantía de convergencia anterior, consulte Attouch, Bolte y Svaiter (2011). En Bertsekas (2016), hay una prueba de que para cada secuencia construida mediante búsqueda de línea de retroceso, un punto de clúster (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 de Morse ) y subniveles compactos , así como con gradiente continuo de Lipschitz donde se usa GD estándar con tasa de aprendizaje <1/L (ver la sección "Descenso de gradiente estocástico"), entonces la convergencia está garantizada, ver por ejemplo el Capítulo 12 en Lange (2013). Aquí la suposición sobre subniveles compactos es asegurarse de que uno trata solo con conjuntos compactos del espacio euclidiano. En el caso general, donde solo se supone que es y tiene como máximo un número contable de puntos críticos, la convergencia está garantizada, ver Truong & Nguyen (2020). En la misma referencia, de manera similar, la convergencia está garantizada para otras modificaciones de la búsqueda de línea de retroceso (como el descenso de gradiente de retroceso ilimitado mencionado en la sección "Límite superior para tasas de aprendizaje"), e incluso si la función tiene un número incontable de puntos críticos aún se pueden deducir algunos hechos no triviales sobre el comportamiento de convergencia. En el contexto estocástico, bajo el mismo supuesto de que el gradiente es continuo en el sentido de Lipschitz y se utiliza 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 tasa de aprendizaje decreciente (ver la sección "Descenso del gradiente estocástico") y además la función es estrictamente convexa, entonces la convergencia se establece en el conocido resultado de Robbins y Monro (1951), ver Bertsekas y Tsitsiklis (2006) para generalizaciones a versiones menos restrictivas de un esquema de tasa de aprendizaje decreciente. Ninguno de estos resultados (para funciones no convexas) ha sido probado para ningún otro algoritmo de optimización hasta el momento. ^{[ cita requerida ]} ${\displaystyle f}$ ${\displaystyle C^{1}}$

Para evitar los puntos de silla: por ejemplo, si el gradiente de la función de costo es Lipschitz continuo y se elige GD estándar con tasa de aprendizaje <1/L, entonces con una elección aleatoria del punto inicial (más precisamente, fuera de un conjunto de medida de Lebesgue cero), la secuencia construida no convergerá a un punto de 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 de silla degenerado (probado en Panageas & Piliouras (2017)). Bajo el mismo supuesto de que el gradiente es Lipschitz continuo y se usa un esquema de tasa de aprendizaje decreciente (ver la sección "Descenso de gradiente estocástico"), entonces se establece la evitación de los puntos de silla en Panageas, Piliouras & Wang (2019). ${\displaystyle \mathbf {x} _{0}}$

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

Si bien es trivial mencionarlo, si el gradiente de una función de costo es Lipschitz continuo, con Lipschitz constante L, entonces al elegir una tasa de aprendizaje constante y de tamaño , uno tiene un caso especial de búsqueda de línea de retroceso (para descenso de gradiente). Esto se ha utilizado al menos en Armijo (1966). Sin embargo, este esquema requiere que uno tenga una buena estimación para L, de lo contrario, si la tasa de aprendizaje es demasiado grande (en relación con 1/L), entonces el esquema no tiene garantía de convergencia. Uno puede ver qué saldrá mal si la función de costo 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 grandes dimensiones. Además, si el gradiente de la función no es globalmente Lipschitz continuo, 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 costo 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 ha sido utilizado mucho más antiguamente, al menos desde 1847 por Cauchy , que puede llamarse GD estándar (que no debe confundirse con el descenso de gradiente estocástico, que se abrevia aquí como SGD). En el entorno estocástico (como en el entorno de minilotes 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 continuo global, 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 de ajuste fino de las tasas de aprendizaje al aplicar GD o SGD estándar. Una forma es elegir muchas tasas de aprendizaje de una búsqueda de 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 de cuadrícula no puede ayudar). Otra forma es el llamado GD o SGD estándar adaptativo, algunos representantes son Adam, Adadelta, RMSProp, etc., consulte el artículo sobre Descenso de gradiente estocástico . En el 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 uno necesita hacer una búsqueda de bucle hasta que se satisfaga la condición de Armijo, mientras que para GD o SGD estándar adaptativos no se necesita una búsqueda de bucle. La mayoría de estos GD o SGD estándar adaptativos no tienen la propiedad de descenso , para todo n, como la búsqueda de línea de retroceso para el descenso de gradiente. Solo unos pocos tienen esta propiedad, y tienen buenas propiedades teóricas, pero resultan ser casos especiales de búsqueda de línea de retroceso o, más generalmente, la condición de Armijo Armijo (1966). El primero es cuando uno elige que la tasa de aprendizaje sea una constante <1/L, como se mencionó anteriormente, si uno puede tener una buena estimación de L. El segundo es la llamada tasa de aprendizaje decreciente, utilizada en el conocido artículo de Robbins y Monro (1951), si nuevamente la función tiene gradiente continuo de Lipschitz globalmente (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ínea de retroceso (y sus modificaciones) es un método fácil de implementar, aplicable a funciones muy generales, con muy buenas garantías teóricas (tanto para la convergencia a puntos críticos como para evitar puntos de silla) y que funciona bien en la práctica. Varios otros métodos que tienen buenas garantías teóricas, como las tasas de aprendizaje decrecientes o la GD estándar con una tasa de aprendizaje <1/L (ambos requieren que el gradiente de la función objetivo sea Lipschitz continuo), resultan ser un caso especial de búsqueda de línea de retroceso o satisfacen la condición de Armijo. Aunque a priori se necesita que la función de costo 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\}}$

Véase también

• Descenso de gradiente
• Descenso de gradiente estocástico
• Condiciones de Wolfe

Referencias

• Absil, PA; Mahony, R.; Andrews, B. (2005). "Convergencia de las iteraciones de los métodos Descent para funciones de costo analíticas". SIAM J. Optim. 16 (2): 531–547. doi :10.1137/040605266.
• Armijo, Larry (1966). "Minimización de funciones con derivadas parciales primeras continuas de Lipschitz". Pacific J. Math . 16 (1): 1–3. doi : 10.2140/pjm.1966.16.1 .
• Attouch, H.; Bolte, J.; Svaiter, BF (2011). "Convergencia de métodos de descenso para problemas semialgebraicos y dóciles: algoritmos proximales, división hacia adelante-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 gradientes con errores". SIAM J. Optim. 10 (3): 627–642. CiteSeerX  10.1.1.421.193 . doi : 10.1137/S1052623497331063 .
• Bray, AJ; Dean, DS (2007). "Estadísticas de puntos críticos de campos gaussianos en espacios de gran dimensión". Physical Review Letters . 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). "Identificación y ataque del problema del punto de silla en la optimización no convexa de alta dimensión". NeurIPS . 14 : 2933–2941. arXiv : 1406.2572 .
• Lange, K. (2013). Optimización . Nueva York: Springer-Verlag Publications. 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: SIAM Publications. ISBN 978-0-898713-64-0.
• Lee, JD; Simchowitz, M.; Jordan, MI; Recht, B. (2016). "El descenso de gradiente solo converge a minimizadores". Actas de investigación en 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 en gradiente solo converge a minimizadores: puntos críticos no aislados y regiones invariantes". 8.ª Conferencia sobre innovaciones en informática teórica (ITCS 2017) (PDF) . Leibniz International Proceedings in Informatics (LIPIcs). Vol. 67. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. 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 de silla: el caso de tamaños de paso que se desvanecen" (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 con 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)