En el caso de problemas convexos, ¿el gradiente en el Gradiente de Gradiente Estocástico (SGD) siempre apunta al valor extremo global?

Question

Dado un convexa de la función de costo, el uso de SGD para la optimización, vamos a tener un gradiente (vector) en un cierto punto durante el proceso de optimización.

Mi pregunta es, dado el punto en el convexo, ¿el gradiente único punto en la dirección en la que la función de aumentar/disminuir más rápido, o el gradiente apunta siempre a la óptima/punto extremo de la función de costo?

El primero es un local de concepto, este último es un concepto global.

SGD puede eventualmente convergen a los valores extremos de la función de costo. Me pregunto acerca de la diferencia entre la dirección de la gradiente dado un punto arbitrario en la parte convexa y la dirección en la que apunta a la global de valor extremo.

El gradiente de la dirección debe ser la dirección en la que la función de aumento/disminución más rápida en ese punto, ¿verdad?

Answer 1

Dicen que una imagen vale más que mil palabras. En el ejemplo siguiente (cortesía de MS Paint, una herramienta muy útil para aficionados y profesionales estadísticos, se puede ver una función convexa de la superficie y un punto donde la dirección de la mayor descenso difiere claramente de la dirección hacia el óptimo.

En serio: Hay muy superior respuestas en este hilo que también merecen una upvote.

Answer 2

• Gradiente de la pendiente de los métodos de uso de la pendiente de la superficie.
• Esto no necesariamente (o incluso más probable es que no) punto directamente hacia el punto extremo.

Una visión intuitiva es imaginar un camino de descenso que es un camino con curvas. Véase, por ejemplo, los siguientes ejemplos.

Como una analogía: Imagina que yo venda de los ojos y ponerlo en algún lugar en una montaña con la tarea a caminar de regreso a la extrema (bajo) punto. En la colina, si sólo dispone de locales de información, entonces usted está no saber en qué dirección el fondo del lago será.

Si usted puede asumir que la convexidad

• Entonces usted sabe que sólo hay un punto extremo.
• Entonces usted sabe que son sin duda va a llegar el punto extremo mientras se mueve hacia abajo.
• Y, a continuación, usted también sabe que el ángulo entre la mayor descenso de la dirección y la dirección óptima es siempre en la mayoría de las $\pi/2$, como Solomonoff s Secret se menciona en los comentarios.

Sin convexidad

• El ángulo puede exceder $\pi/2$. En la imagen de abajo esto es enfatizado por el dibujo de una flecha de dirección de descenso de un punto en particular donde la solución final está detrás de la línea perpendicular a la dirección de descenso.

  En la parte convexa del problema que esto no es posible. Usted podría relacionar esta a las isolíneas para la función de costo de tener una curvatura todos en el mismo la dirección cuando el problema es convexo.

En El Estocástico Gradiente De La Pendiente

• Usted siga la línea de máxima dirección de un solo punto (y repetidamente dar un paso por un punto diferente). En el ejemplo, el problema es convexo, pero puede haber más de una solución. En el ejemplo los valores extremos se encuentran sobre una línea (en lugar de un solo punto), y desde este punto de vista particular, se podría decir que La mayor descenso de la dirección, puede apuntar directamente a la "óptima" (aunque sólo sea el óptimo para la función de esa formación particular punto de muestra)

A continuación es otro punto de vista para los cuatro puntos de datos. Cada una de las cuatro imágenes se muestra la superficie de un diferente punto único. Cada paso de un punto diferente es elegido a lo largo de la cual el gradiente se calcula. Esto hace que sólo hay cuatro direcciones a lo largo de la cual un paso, pero el stepsizes disminuir cuando nos acercamos a la solución.

---

---

Las imágenes de arriba son de 4 tipos de datos generados por la función:

$$y_i = e^{-0.4x_i}-e^{-0.8 x_i} + \epsilon_i$$

x = 0      2      4      6           
y = 0.006  0.249  0.153  0.098

which results in:

• a non-convex optimization problem when we minimize the (non-linear) cost function $$ S(a,b) = \sum_{i=1} \left( y_i - (e^{-ax_i}-e^{-b x_i}) \right)^2$$ $$\nabla S(a,b) = \begin{bmatrix} \sum_{i=1} 2 x_i e^{-a x_i}\left( y_i - e^{-ax_i}-e^{-b x_i} \right) \\ \sum_{i=1} -2 x_i e^{-b x_i}\left( y_i - e^{-ax_i}-e^{-b x_i} \right) \end{bmatrix}$$

• un problema de optimización convexa (como cualquier lineal de mínimos cuadrados), cuando nos minimizar $$ S(a,b) = \sum_{i=1} \left( y_i - (a e^{-0.4 x_i}- b e^{-0.8 x_i} )\right)^2$$ $$\nabla S(a,b) = \begin{bmatrix} \sum_{i=1} -2 e^{-0.4x_i}\left( y_i - a e^{-0.4x_i}- b e^{-0.8 x_i} \right) \\ \sum_{i=1} 2 e^{-0.8x_i}\left( y_i - a e^{-0.4x_i}- b e^{-0.8 x_i} \right) \end{bmatrix}$$

• un problema de optimización convexa (pero no con un solo mínimo) cuando nos minimizar específicos para algunas $i$ $$ S(a,b) = \left( y_i - (a e^{-0.4 b x_i}- b e^{-0.8 x_i}) \right)^2$$ which has gradient $$\nabla S(a,b) = \begin{bmatrix} -2 e^{-0.4x_i}\left( y_i - a e^{-0.4x_i}- b e^{-0.8 x_i} \right) \\ 2 e^{-0.8x_i}\left( y_i - a e^{-0.4x_i}- b e^{-0.8 x_i} \right) \end{bmatrix}$$ this has multiple minima (there are multiple $$ and $b$ for which $S = 0$ )

---

Answer 3

Más brusco descenso puede ser ineficiente , incluso si la función objetivo es fuertemente convexo.

Ordinario de gradiente de la pendiente

Me refiero a "ineficiente" en el sentido de que steepest descent pueden tomar medidas que oscilan tremendamente lejos de la óptima, incluso si la función es fuertemente convexo o incluso cuadrática.

Considere la posibilidad de $f(x)=x_1^2 + 25x_2^2$. Este es convexa porque es una ecuación cuadrática con coeficientes positivos. Por la inspección, se puede ver que tiene un mínimo global en $x=[0,0]^\top$. Se ha degradado $$ \nabla f(x)= \begin{bmatrix} 2x_1 \\ 50x_2 \end{bmatrix} $$

Con una tasa de aprendizaje de $\alpha=0.035$, y la estimación inicial $x^{(0)}=[0.5, 0.5]^\top,$ tenemos el gradiente de actualización

$$ x^{(1)} =x^{(0)}-\alpha \nabla f\left(x^{(0)}\right) $$

que presenta este salvajemente oscilante progreso hacia el mínimo.

De hecho, el ángulo de $\theta$ formado entre el $(x^{(i)}, x^*)$ $(x^{(i)}, x^{(i+1)})$ sólo poco a poco se desintegra a 0. Lo que esto significa es que la dirección de la actualización es a veces mal-en la mayoría, es malo por casi 68 grados, aunque el algoritmo es convergente y funcionando correctamente.

Cada paso es muy oscilante debido a que la función es mucho más pronunciado en el $x_2$ dirección de la $x_1$ dirección. Debido a este hecho, podemos inferir que el gradiente no es siempre, o, incluso, generalmente, apuntando hacia el mínimo. Esta es una propiedad general de la gradiente de la pendiente cuando los autovalores de Hesse $\nabla^2 f(x)$ están en diferentes escalas. El progreso es lento en las direcciones correspondientes a los vectores propios con la menor de las correspondientes autovalores, y el más rápido en las direcciones con los mayores valores propios. Es esta propiedad, en combinación con la elección de la tasa de aprendizaje, que determina la rapidez con la gradiente de la pendiente a medida que progresa.

El camino directo a la mínima sería mover "en diagonal", en lugar de en esto de la moda que está fuertemente dominado por la vertical de las oscilaciones. Sin embargo, el gradiente de descenso sólo tiene información sobre los locales de la pendiente, por lo que "no sabe" que la estrategia sería más eficiente, y que está sujeto a los caprichos de Hesse tener autovalores en diferentes escalas.

Estocástico de gradiente de la pendiente

SGD tiene las mismas propiedades, con la excepción de que las actualizaciones son ruidosos, lo que implica que el contorno de la superficie tiene un aspecto diferente de una iteración a la siguiente, y por lo tanto los gradientes son también diferentes. Esto implica que el ángulo entre la dirección de la gradiente de paso y la óptima también han ruido - imagínese que en el mismo parcelas con algunas fluctuaciones.

Más información:

• Podemos aplicar analiticidad de una red neuronal para mejorar la gradiente de la pendiente?

• ¿Por qué son de segundo orden derivados útil en la optimización convexa?

• ¿Cómo se puede cambiar en función de costo positivo?

---

Esta respuesta se toma prestado este ejemplo y la figura de las Redes Neuronales de Diseño (2ª Ed.). Capítulo 9 por Martin T. Hagan, Howard B. Demuth, Mark Hudson Beale, Orlando De Jesús.

Answer 4

La dirección más empinada local no es lo mismo con la dirección óptima global. Si lo fuera, entonces su dirección de gradiente no cambiaría; porque si vas hacia tu óptimo siempre, tu vector de dirección apuntaría siempre óptimo. Pero ese no es el caso. Si fuera el caso, ¿por qué molestarse en calcular su gradiente en cada iteración?

Answer 5

Las otras respuestas resaltar algunos molestos tasa de convergencia para GD/SGD, pero su comentario "SGD puede eventualmente convergen..." no siempre es la correcta (ignorando pedante uso de comentarios acerca de la palabra "puede", ya que parece que significa "voluntad").

Un buen truco para encontrar ejemplos de lo contrario con SGD, es notar que si cada punto de datos es la misma, su función de costo es determinista. Imaginar la extremadamente patológico ejemplo donde tenemos un punto de datos $$(x_0,y_0)=(1,0)$$ and we have a model for how our system should work based on a single parameter $\alfa$ $$f(x,\alpha)=\sqrt{\alpha^2-\alpha x}.$$

Con el MSE como nuestra función de costo, esto se simplifica a $$(f(x_0,\alpha)-y_0)^2=\alpha^2-\alpha,$$ a convex function. Suppose we choose our learning rate $\beta$ poorly so that our update rule is as follows: $$\alpha_{n+1}=\alpha_n-\beta(2\alpha_n-1)=\alpha_n-(2\alpha_n-1)=1-\alpha_n.$$ Now, our cost function has a minimum at $\alpha=\frac12$, but if we start literally anywhere other than $p=\frac12$ then SGD will simply bounce between cycle between the starting point $p$ and $1-p$ y nunca convergen.

No estoy seguro de si la convexidad es suficiente para romper un poco peor comportamiento que existe para general SGD, pero si permite a funciones tan complejas como cúbicas por su función de coste, a continuación, SGD puede rebotar en un subconjunto denso del dominio y nunca convergen en cualquier lugar o acercarse a cualquier ciclo.

SGD también pueden enfoque/obtener ciclos de cualquier longitud finita, que divergen hacia la $\infty$, oscilar hacia la $\pm\infty$ (excusa de la notación), y tienen toneladas de otras patologías del comportamiento.

Una cosa interesante acerca de toda la situación es que no existe una cantidad no numerable de funciones (como SGD), que toma arbitraria de las funciones convexas como entradas y, a continuación, la salida de una actualización de la regla de que siempre converge rápidamente con el mínimo global (si existe uno). Aunque conceptualmente existen un montón de ellos, nuestros mejores intentos de optimización convexa todos tienen patológico contraejemplos. De alguna manera la idea de un simple/intuitivo/rendimiento regla de actualización va en contra de la idea de un modo demostrable actualización correcta de la regla.