Métodos de Newton e quase-Newton

Usar a curvatura

A descida do gradiente só conhece a inclinação. O método de Newton também usa a curvatura: troca $f$ perto do ponto atual pela quadrática com o mesmo valor, gradiente e hessiana, e salta direto para o mínimo dessa quadrática. O passo é $\mathbf w\leftarrow\mathbf w-H^{-1}\mathbf g$. Numa função exatamente quadrática isso cai no mínimo em um único passo, seja qual for o número de condição. Perto do mínimo de qualquer função suave, a convergência é quadrática: o erro é aproximadamente elevado ao quadrado a cada passo, então o número de dígitos corretos mais ou menos dobra.

O método de Newton tem um preço. Com $n$ parâmetros a hessiana tem $n^2$ entradas e resolver com ela custa cerca de $n^3$ operações, bom para centenas de parâmetros e impossível para milhões. Longe do mínimo, ou onde $H$ não é definida positiva, o passo de Newton pode até subir, então as versões práticas o amortecem com busca linear. Os métodos quase-Newton mantêm quase toda a velocidade sem o custo. O BFGS monta uma aproximação da inversa da hessiana a partir das variações observadas $\mathbf s=\mathbf w_{k+1}-\mathbf w_k$ e $\mathbf y=\mathbf g_{k+1}-\mathbf g_k$, impondo a condição secante $B\mathbf s=\mathbf y$. Precisa só de gradientes, custa $O(n^2)$ por passo e converge superlinearmente. O L-BFGS guarda apenas os últimos $m$ pares, tipicamente de 5 a 20, então a memória é $O(mn)$. É o cavalo de batalha usual em calibrações suaves e ajustes de máxima verossimilhança, como os otimizadores padrão do SciPy.

• Newton: $\mathbf w\leftarrow\mathbf w-H^{-1}\mathbf g$; um passo numa quadrática, convergência quadrática perto do mínimo.
• BFGS: aprende uma aproximação da inversa da hessiana a partir de diferenças de gradiente, sem segundas derivadas.
• L-BFGS: guarda só os últimos pares, então escala para muitos parâmetros.

Lab: o que é avaliado

• O primeiro passo de Newton15 pts
• O segundo passo de Newton15 pts
• Um passo de Newton em duas variáveis15 pts
• Passos em uma quadrática15 pts
• A condição secante15 pts
• Métodos e ideias10 pts
• Por que se evita o Newton exato em problemas enormes15 pts