Méthodes de Newton et quasi-Newton

Utiliser la courbure

La descente de gradient ne connaît que la pente. La méthode de Newton utilise aussi la courbure : elle remplace $f$ près du point courant par la quadratique de même valeur, même gradient et même hessienne, et saute directement au minimum de cette quadratique. Le pas est $\mathbf w\leftarrow\mathbf w-H^{-1}\mathbf g$. Sur une fonction exactement quadratique, cela tombe sur le minimum en un seul pas, quel que soit le conditionnement. Près du minimum d'une fonction lisse, la convergence est quadratique : l'erreur est à peu près élevée au carré à chaque pas, donc le nombre de chiffres exacts double environ.

La méthode de Newton a un prix. Avec $n$ paramètres la hessienne a $n^2$ entrées et résoudre avec elle coûte environ $n^3$ opérations : correct pour des centaines de paramètres, impossible pour des millions. Loin du minimum, ou là où $H$ n'est pas définie positive, le pas de Newton peut même monter ; les versions pratiques l'amortissent donc par une recherche linéaire. Les méthodes quasi-Newton gardent l'essentiel de la vitesse sans le coût. BFGS construit une approximation de l'inverse de la hessienne à partir des variations observées $\mathbf s=\mathbf w_{k+1}-\mathbf w_k$ et $\mathbf y=\mathbf g_{k+1}-\mathbf g_k$, en imposant la condition sécante $B\mathbf s=\mathbf y$. Elle n'utilise que des gradients, coûte $O(n^2)$ par pas et converge de façon superlinéaire. L-BFGS ne stocke que les $m$ dernières paires, typiquement 5 à 20, donc la mémoire est $O(mn)$. C'est le cheval de trait habituel des calibrations lisses et des estimations de maximum de vraisemblance, comme les optimiseurs par défaut de SciPy.

• Newton : $\mathbf w\leftarrow\mathbf w-H^{-1}\mathbf g$ ; un pas sur une quadratique, convergence quadratique près du minimum.
• BFGS : apprend une approximation de l'inverse de la hessienne à partir des différences de gradient, sans dérivées secondes.
• L-BFGS : ne garde que les dernières paires, donc passe à l'échelle de nombreux paramètres.

Lab : ce qui est noté

• Le premier pas de Newton15 pts
• Le deuxième pas de Newton15 pts
• Un pas de Newton en deux variables15 pts
• Pas sur une quadratique15 pts
• La condition sécante15 pts
• Méthodes et idées10 pts
• Pourquoi on évite Newton exact pour les très gros problèmes15 pts