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

Supongo que esta es una pregunta básica y tiene que ver con la dirección del gradiente en sí, pero estoy buscando ejemplos en los que los métodos de segundo orden (por ejemplo, BFGS ) sean más efectivos que el simple descenso del gradiente.

Aquí hay un marco común para interpretar tanto el descenso de gradiente como el método de Newton, que tal vez sea una forma útil de pensar en la diferencia como un suplemento a la respuesta de @ Sycorax. (BFGS se aproxima al método de Newton; aquí no hablaré sobre ello en particular).

Estamos minimizando la función $f$ , pero no sabemos cómo hacerlo directamente. Entonces, en cambio, tomamos una aproximación local en nuestro punto actual $x$ y minimizamos eso.

El método de Newton aproxima la función usando una expansión de Taylor de segundo orden: donde ∇ f ( x ) denota el gradiente de f en el punto x y ∇ 2 f ( x ) el Hessian en x . Luego pasa a arg min y N x ( y ) y se repite.

$$f(y) \approx N_x(y) := f(x) + \nabla f(x)^T (y - x) + \tfrac12 (y - x)^T \, \nabla^2 f(x) \, (y - x) ,$$ $\nabla f(x)$$f$$x$$\nabla^2 f(x)$$x$$\arg\min_y N_x(y)$

El descenso de gradiente, que solo tiene el gradiente y no el hessiano, no puede simplemente hacer una aproximación de primer orden y minimizar eso, ya que, como señaló @Hurkyl, no tiene un mínimo. En su lugar, definimos un tamaño de paso y paso a x - t ∇ $t$ . Pero tenga en cuenta que x $x - t \nabla f(x)$ Por lo tanto, el descenso de gradiente minimiza una función Gx(y):=f(x)+∇f(x)T(y-x)+

$$\begin{align} x - t \,\nabla f(x) &= \arg\max_y \left[f(x) + \nabla f(x)^T (y - x) + \tfrac{1}{2 t} \lVert y - x \rVert^2\right] \\&= \arg\max_y \left[f(x) + \nabla f(x)^T (y - x) + \tfrac12 (y-x)^T \tfrac{1}{t} I (y - x)\right] .\end{align}$$ $$G_x(y) := f(x) + \nabla f(x)^T (y - x) + \tfrac12 (y-x)^T \tfrac{1}{t} I (y - x).$$

Por lo tanto, el descenso de gradiente es como usar el método de Newton, pero en lugar de tomar la expansión de Taylor de segundo orden, pretendemos que el hessiano es . EsteGes a menudo una aproximación sustancialmente peor afqueN, y por lo tanto, el descenso del gradiente a menudo toma pasos mucho peores que el método de Newton. Esto está contrarrestado, por supuesto, porque cada paso del descenso del gradiente es mucho más barato de calcular que cada paso del método de Newton. Lo que es mejor depende completamente de la naturaleza del problema, sus recursos computacionales y sus requisitos de precisión.$\tfrac1t I$$G$$f$$N$

Mirando el ejemplo de @ Sycorax de minimizar una f ( x ) cuadrática = 1

$$f(x) = \tfrac12 x^T A x + d^T x + c$$ por un momento, vale la pena señalar que esta perspectiva ayuda a comprender ambos métodos.

Con el método de Newton, tendremos para que termine con la respuesta exacta (hasta problemas de precisión de coma flotante) en un solo paso.$N = f$

El descenso de gradiente, por otro lado, usa

$$G_x(y) = f(x) + (A x + d)^T y + \tfrac12 (x - y)^T \tfrac1t I (x-y)$$ $x$$A$

Esencialmente, la ventaja de un método de segunda derivada como el método de Newton es que tiene la calidad de terminación cuadrática. Esto significa que puede minimizar una función cuadrática en un número finito de pasos. Un método como el descenso de gradiente depende en gran medida de la velocidad de aprendizaje, lo que puede hacer que la optimización converja lentamente porque rebota alrededor de lo óptimo o diverja por completo. Se pueden encontrar tasas de aprendizaje estables ... pero implican calcular el hessian. Incluso cuando usa una tasa de aprendizaje estable, puede tener problemas como la oscilación alrededor del óptimo, es decir, no siempre tomará un camino "directo" o "eficiente" hacia el mínimo. Por lo tanto, puede llevar muchas iteraciones terminar, incluso siEstás relativamente cerca de eso. BFGS y el método de Newton pueden converger más rápidamente a pesar de que el esfuerzo computacional de cada paso es más costoso.

$$F(x)=\frac{1}{2}x^TAx+d^Tx+c$$ $$\nabla F(x)=Ax+d$$ $$x_{k+1}= x_k-\alpha(Ax_k+d) = (I-\alpha A)x_k-\alpha d.$$

$I-\alpha A$

$$\alpha<\frac{2}{\lambda_{max}},$$ $\lambda_{max}$$A$$A$$A$

En el contexto específico de las redes neuronales, el libro Neural Network Design tiene bastante información sobre métodos de optimización numérica. La discusión anterior es una condensación de la sección 9-7.

En la optimización convexa, está aproximando la función como polinomio de segundo grado en un caso unidimensional:

$$f(x)=c+\beta x + \alpha x^2$$

En este caso la segunda derivada

$$\partial^2 f(x)/\partial x^2=2\alpha$$

Si conoce las derivadas, entonces es fácil obtener la siguiente aproximación para el óptimo:

$$\text{guess}=-\frac{\beta}{2\alpha}$$

El caso multivariante es muy similar, solo use gradientes para derivados.

@Dougal ya dio una gran respuesta técnica.

La explicación no matemática es que mientras la aproximación lineal (orden 1) proporciona un "plano" que es tangencial a un punto en una superficie de error, la aproximación cuadrática (orden 2) proporciona una superficie que abraza la curvatura de la superficie de error.

Los videos en este enlace hacen un gran trabajo al visualizar este concepto. Muestran aproximaciones de orden 0, orden 1 y orden 2 a la superficie de la función, que solo verifica intuitivamente lo que las otras respuestas presentan matemáticamente.

Además, una buena publicación de blog sobre el tema (aplicada a redes neuronales) está aquí .