Descenso de gradiente en funciones no convexas

¿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

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

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: \mathbb{R}^d \to \mathbb{R}$

$\pmb{x}_{t+1} = \pmb{x}_t - \alpha\nabla f(\pmb{x}_t)$ .

Además, tenemos el siguiente requisito:

$\| \nabla f(\pmb{x}_1)-\nabla f(\pmb{x}_2) \| \leq \ell \| \pmb{x}_1 - \pmb{x}_2 \|, \quad \text{for all } \pmb{x}_1, \pmb{x}_2$ .

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.$\ell$

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.$\pmb{x}$$\nabla f(\pmb{x}) = 0$$\lambda_{\min}\left(\nabla^2 f(\pmb{x})\right) < 0$$\lambda_{\max}\left(\nabla^2 f(\pmb{x})\right) > 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.$W^s(\pmb{x}^s) = \{\pmb{x} : \lim_k g^k(\pmb{x}) = \pmb{x}^s \}$$\pmb{x}^s$$W$$g : \mathbb{R}^d \to \mathbb{R}^d$$\pmb{x}_k$$\pmb{x}^s$

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.$W^s$

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, $\|\nabla(f) \| \leq \epsilon, \quad \text{and}, \quad \lambda_{\min}\left(\nabla^2 f(\pmb{x})\right)\geq -\sqrt{\rho\epsilon}$

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.$\lambda_{\min}\left(\nabla^2 f(\pmb{x})\right)\leq 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.

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és$f$$\bar{x}$$\phi$

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".