ニュートン法

最急降下法の収束性を改善したニュートン法について触れる。

最急降下法では、1次近似を基に更新規則を設計した。

\begin{aligned} f(\bm x + \Delta \bm x) = f(\bm x) + \left( \frac{\partial f (\bm x)}{\partial \bm x} \right)^\mathsf{T} \Delta \bm x \end{aligned}

これを2次の項まで拡張して考える。

\begin{aligned} f(\bm x + \Delta \bm x) \approx f(\bm x) + \left( \frac{\partial f (\bm x)}{\partial \bm x} \right)^\mathsf{T} \Delta \bm x + \frac{1}{2} \Delta \bm x ^\mathsf{T} \left( \frac{\partial^2 f (\bm x)}{\partial \bm x^2} \right) \Delta \bm x \end{aligned}

2次の項の $\dfrac{\partial^2 f}{\partial \bm x^2}$ はヘッセ行列である。近似された $f(\bm x + \Delta \bm x)$ をできるだけ小さくする $\Delta \bm x$ を探す。

\begin{aligned} \operatorname*{minimize} \quad f(\bm x) + \left( \frac{\partial f (\bm x)}{\partial \bm x} \right)^\mathsf{T} \Delta \bm x + \frac{1}{2} \Delta \bm x ^\mathsf{T} \left( \frac{\partial^2 f (\bm x)}{\partial \bm x^2} \right) \Delta \bm x \end{aligned}

これは $\Delta \bm x$ について2次なので、次のように平方完成できる。詳細はこちらを参照。

\begin{aligned} &\hspace{-1pc} f(\bm x) + \left( \frac{\partial f (\bm x)}{\partial \bm x} \right)^\mathsf{T} \Delta \bm x + \frac{1}{2} \Delta \bm x ^\mathsf{T} \left( \frac{\partial^2 f (\bm x)}{\partial \bm x^2} \right) \Delta \bm x \\ ={}& \frac{1}{2} \left( \Delta \bm x + \left( \frac{\partial^2 f (\bm x)}{\partial \bm x^2} \right)^{-1} \frac{\partial f (\bm x)}{\partial \bm x} \right) ^\mathsf{T} \frac{\partial^2 f (\bm x)}{\partial \bm x^2} \left( \Delta \bm x + \left( \frac{\partial^2 f (\bm x)}{\partial \bm x^2} \right)^{-1} \frac{\partial f (\bm x)}{\partial \bm x} \right) + \mathrm{const.} \end{aligned}

したがって、次のように $\Delta \bm x$ を定めればよい。

\begin{aligned} \Delta \bm x = - \left( \frac{\partial^2 f (\bm x)}{\partial \bm x^2} \right)^{-1} \frac{\partial f (\bm x)}{\partial \bm x} \end{aligned}

更新規則は次のように与えられる。

\begin{aligned} \bm x \gets \bm x - \left( \frac{\partial^2 f (\bm x)}{\partial \bm x^2} \right)^{-1} \frac{\partial f (\bm x)}{\partial \bm x} \end{aligned}

このような更新規則に基づいて局所最適解を探すアルゴリズムをニュートン法 (Newton's method) またはニュートン-ラフソン法 (Newton-Laphson method) という。

ニュートン法は最急降下法に比べて局所解への収束が早い (2次収束) ことが知られている。したがって目的関数 $f(\bm w)$ が2階微分可能であるならば、(ステップ数の観点からいえば) かなり高速に最適解を求められる。

しかし、更新規則にヘッセ行列の逆行列が含まれていることから、1ステップあたりの時間計算量が莫大になる (ナイーブには $\mathcal O(n^3)$ もかかる！)。次元の大きなパラメータの最適化にそのまま使用するのは現実的ではない。

H. B. Fine. 1916. “On Newton’s Method of Approximation.” Proceedings of the National Academy of Sciences of the United States of America 2 (9): 546–52.
梅谷俊治. 2020. しっかり学ぶ数理最適化モデルからアルゴリズムまで. 講談社.
田中和之, 片岡駿, 大関真之, 安田宗樹. 2018. 画像処理の統計モデリング確率的グラフィカルモデルとスパースモデリングからのアプローチ. クロスセクショナル統計シリーズ. 共立出版.