Descenso de gradiente en funciones no convexas

9

¿Qué situaciones sabemos de dónde se puede mostrar que el descenso de gradiente converge (ya sea a un punto crítico o a un mínimo local / global) para funciones no convexas?


Para SGD en funciones no convexas, se ha revisado un tipo de prueba aquí, http://www.cs.cornell.edu/courses/cs6787/2017fa/Lecture7.pdf

graduado
fuente
2
Este documento: arxiv.org/pdf/1602.04915.pdf podría ser útil. En particular: "si [la función] es dos veces continuamente diferenciable y satisface la estricta propiedad del sillín, entonces el descenso del gradiente con una inicialización aleatoria y un tamaño de paso constante suficientemente pequeño converge a un minimizador local o infinito negativo casi con seguridad"
David Kozak
¡Gracias! Me pregunto si hay un sentido en el que el documento que citó es más débil que este resultado más reciente, arxiv.org/abs/1709.01434 ¿ Alguna idea?
gradstudent
Convenientemente que el papel ya está en mi lista para abordar esta semana, me pondré en contacto con usted con una respuesta adecuada una vez que haya digerido.
David Kozak
¡Gracias! Esperamos una discusión! : D ¡Avíseme si conoce algún prototipo "pequeño" de tales pruebas de mostrar convergencia en el descenso de gradiente no convexo!
gradstudent

Respuestas:

3

Consulte el apéndice B1 en https://web.stanford.edu/~boyd/cvxbook/ .

La función y la restricción pueden ser no convexas en un programa cuadrático restringido cuadráticamente, y aún puede ver una fuerte dualidad (se garantiza si se cumple una condición técnica conocida como calificador de restricción de Slater)

La fuerte dualidad en términos débiles significa que podemos resolver el problema de optimización. A partir del problema original que se llama primario, puede formular un problema alternativo llamado problema dual. La solución del problema dual proporciona una solución que, en cierto sentido, es el "mejor límite inferior" para sus problemas originales

En muchos de los problemas de optimización que no son convexos, habrá una brecha entre las soluciones primarias y duales, es decir, el límite inferior puede estar muy por debajo del verdadero valor óptimo (incluso el infinito negativo). En algunos casos especiales, el límite es apretado. Estos casos especiales son aquellos en los que tenemos una fuerte dualidad.

El algoritmo es una TÉCNICA utilizada para llegar al punto óptimo. La solución óptima y nuestra capacidad para encontrarla depende de la GEOMETRÍA del problema (que es a lo que intenta llegar la dualidad). En términos generales, el análisis dice que si la optimización configurada correctamente convergerá al mínimo.

En general, el descenso del gradiente convergerá a un punto estacionario. Este punto puede ser un mínimo local / mínimo global / mínimo de silla de montar. En solo unos pocos casos no convexos podemos garantizar a qué converge

Sid
fuente
¿Qué es un QCQP y qué significa ver una fuerte dualidad?
MachineEpsilon
@Sid ¿Qué tiene esto que ver con la convergencia del descenso de gradiente por el que estoy preguntando?
gradstudent
He editado mi respuesta. Mis disculpas por la breve respuesta
Sid
3

En esta respuesta exploraré dos documentos interesantes y relevantes que se mencionaron en los comentarios. Antes de hacerlo, intentaré formalizar el problema y arrojar algo de luz sobre algunos de los supuestos y definiciones. Comienzo con un artículo de 2016 de Lee et al.

Buscamos minimizar una función no convexa que está limitada a continuación. Requerimos que sea dos veces diferenciable. Utilizamos un algoritmo de descenso de gradiente de la forma:f:RdR

xxt+1=xxtαf(xxt) .

Además, tenemos el siguiente requisito:

f(xx1)f(xx2)xx1xx2,for all xx1,xx2 .

Es decir, requerimos que nuestra función sea -Lipschitz en su primera derivada. En inglés, esto se traduce en la idea de que nuestro gradiente no puede cambiar demasiado rápido en ninguna parte del dominio. Esta suposición asegura que podemos elegir un tamaño de paso tal que nunca terminemos con pasos que divergen.

Recuerde que un punto se dice que es una silla estricta si y y . Si todos los valores propios del Hessian tienen el mismo signo, entonces el punto es un mínimo (si son positivos) o un máximo (si son negativos). Si hay 0 valores propios, entonces se dice que es degenerado, y no es una silla de montar estricta.xxf(xx)=0λmin(2f(xx))<0λmax(2f(xx))>0

El documento muestra que con los supuestos anteriores, junto con el supuesto de que todos los puntos de silla de la función son de silla de montar estricta, se garantiza que el descenso del gradiente converja al mínimo.

La prueba es bastante técnica, pero la intuición es esta: defina un conjunto , donde es un punto de silla de montar. No me gusta esta notación en absoluto. A lo que intentan llegar es a que es el conjunto de valores iniciales para los cuales el mapa de gradiente envía a . Dicho más claramente, es el conjunto de inicializaciones aleatorias que finalmente convergerán en una silla de montar.Ws(xxs)={xx:limkgk(xx)=xxs}xxsWg:RdRdxxkxxs

Su argumento se basa en el teorema del múltiple estable. Con los supuestos anteriores y un montón de matemáticas esotéricas, concluyen que el conjunto debe ser cero, es decir, hay cero probabilidad de inicialización aleatoria en un punto que convergerá en un punto de silla de montar. Como sabemos que el descenso de gradiente en funciones del tipo descrito en los supuestos con tamaños de paso adecuadamente pequeños finalmente alcanzará un punto crítico, y ahora sabemos (casi seguramente) que nunca aterrizará en una silla de montar, sabemos que converge a Un minimizador.Ws

El segundo artículo más reciente de Reddi et al. Discutiré con menos detalle. Hay varias diferencias Primero, ya no están trabajando en un marco determinista, sino que optan por el marco de aproximación estocástico más relevante en una suma finita (piense en el Descenso de gradiente estocástico). Las principales diferencias son que el tamaño del paso requiere un cuidado adicional, y el gradiente se convierte en una variable aleatoria. Además, relajan la suposición de que todos los sillines son estrictos y buscan un punto estacionario de segundo orden. Es decir, un punto tal que, (f)ϵ,and,λmin(2f(xx))ρϵ

Donde es la constante de Lipschitz para el Hessian. (Es decir, además del requisito de que nuestro gradiente no varíe demasiado rápido, ahora tenemos un requisito similar en nuestro Hessian. Esencialmente, los autores están buscando un punto que parezca un mínimo tanto en la primera como en la segunda derivada.rho

El método por el cual logran esto es usar una variante (elija su favorito) de descenso de gradiente estocástico la mayor parte del tiempo. Pero cada vez que encuentran un punto donde , usan un método de segundo orden elegido adecuadamente para escapar de la silla de montar. Muestran que al incorporar esta información de segundo orden según sea necesario, convergerán en un punto estacionario de segundo orden.λmin(2f(xx))0

Técnicamente, este es un método de gradiente de segundo orden, que puede estar o no bajo el paraguas de algoritmos que le interesan.

Esta es un área de investigación muy activa y he dejado de lado muchas contribuciones importantes (ex Ge et al. ). También soy nuevo en el tema, por lo que esta pregunta me ha brindado la oportunidad de mirar. Estoy feliz de continuar la discusión si hay interés.

*** Elegido adecuadamente significa uno que se muestra que converge a un punto estacionario de segundo orden. Utilizan el método de Newton cúbico regularizado de Nesterov y Polyak.

David Kozak
fuente
1
¡Gracias por la respuesta! Dos comentarios (a) Creo que Reddi et. Alabama. es un mejor resultado que Lee et. Alabama. porque es una convergencia con un límite de velocidad y no solo un resultado asintótico. (b) Existe este documento que parece afirmar (y parece ser) mejor que todos estos documentos, opt-ml.org/papers/OPT2017_paper_16.pdf
gradstudent
De acuerdo, y es mucho más simple matemáticamente. Pero el resultado de Lee es interesante por su enfoque único: creo que habrá más progreso desde esa dirección a medida que comencemos a buscar más formas de comprender las superficies no convexas de alta dimensión. Revisaré el papel al que hizo referencia, ¡gracias por eso!
David Kozak
Agreguemos una pregunta más: dado esto, Reddi et. Alabama. hay todavía alguna relevancia del artículo más famoso del mismo grupo, arxiv.org/abs/1603.06160
gradstudent
Definitivamente hay relevancia ya que la variante de descenso de gradiente que usan en su artículo más reciente es SVRG. Podríamos cerrar esta pregunta y comenzar de nuevo para que la comunidad obtenga el beneficio de participar. Todavía no he leído el documento que recomendó más allá del resumen, pero está en la lista y puede inspirar más preguntas.
David Kozak
2

Trataré de responder la parte de la pregunta "¿Cuándo converge la pendiente de gradiente a un punto crítico"?

El documento "Convergencia de los métodos de descenso para problemas semi-algebraicos y domesticados: algoritmos proximales, división hacia adelante y hacia atrás y métodos Gauss-Seidel regularizados"

por Attouch, Bolte y Svaiter,

muestra que si la función objetivo satisface la desigualdad Kurdyka-Lojasiewicz (KL), entonces GD y otros métodos de descenso convergen de hecho a un minimizador. Tenga en cuenta que la condición de KL es extremadamente general pero difícil de comprender. Las funciones que satisfacen KL se dan, por ejemplo, mediante funciones semi-algebraicas (de nuevo, muy general pero no una noción simple).

Con el fin de dar algunas intuiciones sobre estas nociones, intentaré ser menos vago, pero también no demasiado técnico, tan desnudo conmigo. Una función satisface la condición KL en un punto crítico si existe una función (tenga en cuenta que estoy omitiendo algunas condiciones) de modo que para todo tal que para algún . La intuición es que existe una función que reparametriza nuestra función de interésfx¯ϕ

||(ϕf)(x)||1
xf(x¯)<f(x)<rrϕfde tal manera que sea nítida alrededor del punto crítico (la derivada se aleja de cero). En cierto sentido, esto significa que la función no puede ser demasiado plana alrededor de .x¯

Semialgebricity por otro lado es un poco más difícil. El campo que lo estudia también se conoce como geometría domesticada . Creo que el nombre domesticado captura muy bien la esencia. Las funciones que pertenecen a esta clase no pueden ser arbitrariamente "salvajes".

xel
fuente
¡Gracias! Déjame ver esto! ¿Puede agregar amablemente algunas intuiciones sobre esta condición?
gradstudent
Actualicé mi respuesta con cierta intuición. Espero eso ayude.
xel