Métodos de Newton y cuasi-Newton

Usar la curvatura

El descenso de gradiente solo conoce la pendiente. El método de Newton usa también la curvatura: sustituye $f$ cerca del punto actual por la cuadrática con el mismo valor, gradiente y hessiano, y salta directamente al mínimo de esa cuadrática. El paso es $\mathbf w\leftarrow\mathbf w-H^{-1}\mathbf g$. En una función exactamente cuadrática cae en el mínimo en un solo paso, sea cual sea el número de condición. Cerca del mínimo de cualquier función suave, la convergencia es cuadrática: el error se eleva aproximadamente al cuadrado en cada paso, así que el número de cifras correctas se duplica más o menos.

El método de Newton tiene un precio. Con $n$ parámetros el hessiano tiene $n^2$ entradas y resolver con él cuesta unas $n^3$ operaciones, bien para cientos de parámetros e imposible para millones. Lejos del mínimo, o donde $H$ no es definida positiva, el paso de Newton puede incluso subir, por lo que las versiones prácticas lo amortiguan con una búsqueda lineal. Los métodos cuasi-Newton conservan casi toda la velocidad sin el coste. BFGS construye una aproximación del inverso del hessiano a partir de los cambios observados $\mathbf s=\mathbf w_{k+1}-\mathbf w_k$ y $\mathbf y=\mathbf g_{k+1}-\mathbf g_k$, imponiendo la condición secante $B\mathbf s=\mathbf y$. Solo necesita gradientes, cuesta $O(n^2)$ por paso y converge superlinealmente. L-BFGS guarda solo los últimos $m$ pares, típicamente de 5 a 20, así que la memoria es $O(mn)$. Es el caballo de batalla habitual en calibraciones suaves y ajustes de máxima verosimilitud, como los optimizadores por defecto de SciPy.

• Newton: $\mathbf w\leftarrow\mathbf w-H^{-1}\mathbf g$; un paso en una cuadrática, convergencia cuadrática cerca del mínimo.
• BFGS: aprende una aproximación del inverso del hessiano a partir de diferencias de gradiente, sin segundas derivadas.
• L-BFGS: guarda solo los últimos pares, así que escala a muchos parámetros.

Lab: qué se califica

• El primer paso de Newton15 pts
• El segundo paso de Newton15 pts
• Un paso de Newton en dos variables15 pts
• Pasos en una cuadrática15 pts
• La condición secante15 pts
• Métodos e ideas10 pts
• Por qué se evita Newton exacto en problemas enormes15 pts