¿El descenso del gradiente siempre converge a un óptimo?

Me pregunto si hay algún escenario en el que el descenso de gradiente no converja al mínimo.

Soy consciente de que no siempre se garantiza que el descenso de gradiente converja a un óptimo global. También soy consciente de que podría diferir de un óptimo si, por ejemplo, el tamaño del paso es demasiado grande. Sin embargo, me parece que, si difiere de algún óptimo, eventualmente irá a otro óptimo.

Por lo tanto, se garantizaría que el descenso de gradiente converja a un óptimo local o global. ¿Está bien? Si no es así, ¿podría proporcionar un contraejemplo aproximado?

Gradient Descent es un algoritmo diseñado para encontrar los puntos óptimos, pero estos puntos óptimos no son necesariamente globales. Y sí, si sucede que diverge de una ubicación local, puede converger a otro punto óptimo, pero su probabilidad no es demasiado. La razón es que el tamaño del paso puede ser demasiado grande, lo que hace que retroceda un punto óptimo y la probabilidad de que oscile es mucho más que convergencia.

Sobre el descenso por gradiente hay dos perspectivas principales, la era del aprendizaje automático y la era del aprendizaje profundo. Durante la era de aprendizaje automático, se consideró que el descenso de gradiente encontrará el óptimo local / global, pero en la era de aprendizaje profundo, donde la dimensión de las características de entrada es demasiado, en la práctica se muestra que la probabilidad de que todas las características estén ubicadas en su valor óptimo en un solo punto no es demasiado y, más bien, ver que hay ubicaciones óptimas en las funciones de costos, la mayoría de las veces se observan puntos de silla de montar. Esta es una de las razones por las que el entrenamiento con muchos datos y épocas de entrenamiento hacen que los modelos de aprendizaje profundo superen a otros algoritmos. Por lo tanto, si entrena a su modelo, encontrará un desvío o encontrará el camino para ir cuesta abajo y no se atascará en puntos de silla de montar, pero debe tener el tamaño de escalón adecuado.

Para más intuiciones te sugiero que te refieras aquí y aquí .

Además de los puntos que mencionó (convergencia a mínimos no globales y pasos de gran tamaño que posiblemente conduzcan a algoritmos no convergentes), los "rangos de inflexión" también podrían ser un problema.

Considere el siguiente tipo de función de "silla reclinable".

Obviamente, esto se puede construir de modo que haya un rango en el medio donde el gradiente sea el vector 0. En este rango, el algoritmo se puede atascar indefinidamente. Los puntos de inflexión generalmente no se consideran extremos locales.

¡No se garantiza que el gradiente conjugado alcance un óptimo global o un óptimo local! Hay puntos donde el gradiente es muy pequeño, que no son óptimos (puntos de inflexión, puntos de silla de montar). La pendiente de gradiente podría converger a un punto para la función .f ( x ) = x $x = 0$$f(x) = x^3$

[Nota 5 de abril de 2019: se ha actualizado una nueva versión del documento en arXiv con muchos resultados nuevos. También presentamos versiones de retroceso de Momentum y NAG, y demostramos la convergencia bajo los mismos supuestos que para Backtracking Gradient Descent.

Los códigos fuente están disponibles en GitHub en el enlace: https://github.com/hank-nguyen/MBT-optimizer

Mejoramos los algoritmos para aplicar a DNN, y obtenemos un mejor rendimiento que los algoritmos de última generación como MMT, NAG, Adam, Adamax, Adagrad, ...

La característica más especial de nuestros algoritmos es que son automáticos, no es necesario hacer un ajuste manual de las tasas de aprendizaje como práctica común. Nuestro ajuste automático es de naturaleza diferente de Adam, Adamax, Adagrad, ... y así sucesivamente. Más detalles están en el documento.

]

Basado en resultados muy recientes: en mi trabajo conjunto en este artículo https://arxiv.org/abs/1808.05160

Mostramos que el descenso de gradiente de retroceso , cuando se aplica a una función arbitraria C ^ 1 , con solo un número contable de puntos críticos, siempre convergerá a un punto crítico o divergerá al infinito. Esta condición se cumple para una función genérica, por ejemplo, para todas las funciones Morse. También demostramos que, en cierto sentido, es muy raro que el punto límite sea un punto de silla de montar. Entonces, si todos sus puntos críticos no son degenerados, en cierto sentido, los puntos límite son todos mínimos. [Véanse también las referencias en el documento citado para los resultados conocidos en el caso del descenso de gradiente estándar.]$f$

Con base en lo anterior, propusimos un nuevo método de aprendizaje profundo que está a la par con los métodos más modernos y no necesita un ajuste manual de las tasas de aprendizaje. (En pocas palabras , la idea es que ejecute el descenso de gradiente de retroceso una cierta cantidad de tiempo, hasta que vea que las tasas de aprendizaje, que cambian con cada iteración, se estabilizan. Esperamos esta estabilización, en particular en un punto crítico que es C ^ 2 y no es degenerado, debido al resultado de convergencia que mencioné anteriormente. En ese punto, cambia al método de descenso de gradiente estándar. Consulte el documento citado para obtener más detalles. Este método también se puede aplicar a otros algoritmos óptimos .)

PD: En cuanto a su pregunta original sobre el método de descenso de gradiente estándar, que yo sepa, solo en el caso de que la derivada del mapa sea globalmente Lipschitz y la tasa de aprendizaje sea lo suficientemente pequeña como para que el método de descenso de gradiente estándar converja. [Si no se cumplen estas condiciones, existen simples contraejemplos que muestran que no es posible obtener un resultado de convergencia, consulte el documento citado para algunos.] En el documento citado anteriormente, argumentamos que a largo plazo el método de descenso de gradiente de retroceso será El método de descenso de gradiente estándar, que explica por qué el método de descenso de gradiente estándar suele funcionar bien en la práctica.