Por que os derivativos de segunda ordem são úteis na otimização convexa?

Acho que essa é uma pergunta básica e tem a ver com a direção do próprio gradiente, mas estou procurando exemplos em que os métodos de 2ª ordem (por exemplo, BFGS ) são mais eficazes do que a simples descida do gradiente.

Aqui está uma estrutura comum para interpretar a descida do gradiente e o método de Newton, que talvez seja uma maneira útil de pensar na diferença como um complemento à resposta do @ Sycorax. (BFGS aproxima o método de Newton; não falarei sobre isso em particular aqui.)

Estamos minimizando a função , mas não sabemos como fazer isso diretamente. Então, em vez disso, adotamos uma aproximação local em nosso ponto atual x e minimizamos isso.$f$$x$

O método de Newton aproxima a função usando uma expansão de Taylor de segunda ordem: onde ∇ f ( x ) denota o gradiente de f no ponto x e ∇ 2 f ( x ) o Hessiano em x . Em seguida, avança para arg min y N x ( y ) e se repete.

$$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)$

A descida do gradiente, apenas com o gradiente e não o hessiano, não pode apenas fazer uma aproximação de primeira ordem e minimizar isso, já que como observou @Hurkyl, não há um mínimo. Em vez disso, definimos um tamanho de etapa passo para$t$ . Mas observe que x - $x - t \nabla f(x)$ Assim, a descida do gradiente minimiza uma função 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).$$

Assim, a descida do gradiente é como usar o método de Newton, mas em vez de considerar a expansão de Taylor de segunda ordem, fingimos que o Hessiano é . EsseGgeralmente é uma aproximação substancialmente pior defqueNe, portanto, a descida do gradiente geralmente dá passos muito piores que o método de Newton. Isso é contrabalançado, é claro, pois cada passo da descida do gradiente é muito mais barato de calcular do que cada passo do método de Newton. O que é melhor depende inteiramente da natureza do problema, de seus recursos computacionais e de seus requisitos de precisão.$\tfrac1t I$$G$$f$$N$

Observando o exemplo da @ Sycorax de minimizar um quadrático

$$f(x) = \tfrac12 x^T A x + d^T x + c$$

$N = f$

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

Essencialmente, a vantagem de um método de segunda derivada como o método de Newton é que ele tem a qualidade da terminação quadrática. Isso significa que ele pode minimizar uma função quadrática em um número finito de etapas. Um método como a descida em gradiente depende muito da taxa de aprendizado, o que pode fazer com que a otimização converja lentamente, porque está oscilando em torno do ideal ou divergir completamente. Taxas de aprendizado estáveis ​​podem ser encontradas ... mas envolvem a computação do hessian. Mesmo ao usar uma taxa de aprendizado estável, você pode ter problemas como oscilação em torno do ideal, ou seja, nem sempre seguirá um caminho "direto" ou "eficiente" em direção ao mínimo. Portanto, pode levar muitas iterações para terminar, mesmo sevocê é relativamente próximo disso. O método BFGS e Newton pode convergir mais rapidamente, embora o esforço computacional de cada etapa seja mais caro.

$$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$

No contexto específico das redes neurais, o livro Design de Redes Neurais tem bastante informação sobre métodos de otimização numérica. A discussão acima é uma condensação da seção 9-7.

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

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

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

O caso multivariado é muito semelhante, basta usar gradientes para derivadas.

A @Dougal já deu uma ótima resposta técnica.

A explicação não matemática é que, embora a aproximação linear (ordem 1) forneça um "plano" tangencial a um ponto em uma superfície de erro, a aproximação quadrática (ordem 2) forneça uma superfície que abraça a curvatura da superfície de erro.

Os vídeos neste link fazem um ótimo trabalho de visualização desse conceito. Eles exibem aproximações de ordem 0, ordem 1 e ordem 2 à superfície da função, que apenas intuitivamente verifica o que as outras respostas apresentam matematicamente.

Além disso, um bom post no blog (aplicado às redes neurais) está aqui .