曲率を使う
勾配降下法が知っているのは傾きだけです。ニュートン法は曲率も使います。現在の点の近くで f を、値・勾配・ヘッセ行列が同じ2次関数に置き換え、その2次関数の最小点へ一気に跳びます。ステップは w←w−H−1g です。厳密に2次の関数なら、条件数にかかわらず1ステップで最小値に着きます。滑らかな関数の最小値の近くでは収束は2次的で、誤差が1ステップごとにほぼ2乗されるため、正しい桁数がおよそ倍になります。
wk+1=wk−H(wk)−1∇f(wk),∥wk+1−w∗∥ ≲ C∥wk−w∗∥2(1) e^x − 2x へのニュートン法f(x)=ex−2x を最小化します。最小点は
x∗=ln2=0.693147 で、
f′=ex−2、
f′′=ex です。
x0=0 から、
x1=0−(−1)/1=1、次に
x2=1−0.7183/2.7183=0.7358、
x3=0.6940、
x4=0.693148 となります。誤差
0.307, 0.0426, 0.0009, 4⋅10−7 はどんな固定の係数よりも速く縮みます。2変数では、
f=(x−1)2+2(y+2)2 の点
(3,0) で
g=(4,8)、
H=diag(2,4) なので、ステップは
−H−1g=(−2,−2) で、1ステップで最小点
(1,−2) に着きます。
ニュートン法には代償があります。パラメータが n 個ならヘッセ行列は n2 個の要素を持ち、それを使った求解には約 n3 回の演算が必要で、数百個なら問題ありませんが数百万個では不可能です。最小点から遠い場所や H が正定値でない場所ではニュートンステップが上り坂を向くこともあるため、実用版は直線探索でステップを減衰させます。準ニュートン法はコストをかけずに速さの大部分を保ちます。BFGS は観測された変化 s=wk+1−wk と y=gk+1−gk からヘッセ行列の逆行列の近似を作り、セカント条件 Bs=y を課します。勾配だけで済み、1ステップのコストは O(n2)、収束は超1次です。L-BFGS は直近 m 組（通常5〜20）だけを保存するのでメモリは O(mn) で、SciPy の既定のオプティマイザのように、滑らかなキャリブレーションや最尤推定の定番として使われます。
- ニュートン法：w←w−H−1g。2次関数なら1ステップ、最小点の近くでは2次収束。
- BFGS：勾配の差から逆ヘッセ行列の近似を学ぶので、2階微分は不要です。
- L-BFGS：直近の数組だけを保持するので、多数のパラメータにも使えます。
ニュートン法には安全策が必要素のニュートン法は、悪い開始点から行き過ぎたり発散したりすることがあります。ライブラリの実装は直線探索や信頼領域を加え、ヘッセ行列が正定値でないときは勾配ステップに戻ります。キャリブレーションのために、こうした安全策のない素のニュートンのループを自作しないでください。
ラボ：採点される内容
- 最初のニュートンステップ15点
- 2番目のニュートンステップ15点
- 2変数でのニュートンステップ15点
- 2次関数でのステップ数15点
- セカント条件15点
- 手法と考え方10点
- 巨大な問題で厳密なニュートン法が避けられる理由15点
