L-BFGS法とは？わかりやすく解説

記憶制限BFGS法（きおくせいげんBFGSほう）またはL-BFGS法（英: Limited-memory BFGS method）とは、準ニュートン法に分類される最適化アルゴリズムであり、BFGS法をより小さな記憶容量を用いて近似的に実行する^[1]。機械学習におけるパラメーター推定に広く用いられる^[2]^[3]。L-BFGS法が解く対象は、実数ベクトル $x$ の関数 $f (x)$ の非制約最適化問題である。

元になったBFGS法と同様、L-BFGS法は逆ヘッセ行列の推定値を使用して変数空間を探索するが、BFGS法では逆ヘッセ行列の近似値を $n \times n$ 密行列（ $n$ は対象問題の変数の数）として記憶するのに対し、L-BFGS法では少数のベクトルのみを記憶し逆ヘッセ行列の近似値はこれらにより暗黙的に表現される。結果としてメモリ使用量のスケーリングは問題サイズの2乗から1乗ヘ低下するため、多くの変数が関わる最適化問題に特に適する。L-BFGS法では逆ヘッセ行列 $H k$ の代わりに、位置 $x$ と勾配 $\nabla f (x)$ の過去 $m$ 回の更新の履歴を記憶する（多くの場合 $m < 10$ ）。これらの情報から、 $H k$ とのベクトル積を必要とする操作を暗黙的に実行する。

アルゴリズム

L-BFGS法は、所与の初期推定 $x 0$ から、反復的により良い推定値 $x 1, x 2, \dots$ を算出する。目的関数の微分値 $g k := \nabla f (x k)$ を降下の方向の算出だけでなく、ヘッセ行列（2次微分）の推定値の更新にも用いる。

L-BFGS法は他の準ニュートン法アルゴリズムと多くの部分は共通だが、行列とベクトルの乗算 $d k = - H k g k$ の実行方法が大きく異なる。ここで、 $d k$ はニュートン方向の近似値、 $g k$ は現在の勾配であり、 $H k$ はヘッセ行列の逆行列である。これまでの履歴を使用してこの方向ベクトルを算出する複数のアプローチが発表されているが、ここでは、「2ループ再帰」と呼ばれる一般的なアプローチを示す^[4]^[5]。

$k$ 回目の反復における位置 $x k$ および勾配 $g k \equiv \nabla f (x k)$ を所与とする。また、すべてのベクトルは列ベクトルとし、直近 $m$ 回の更新履歴を次の形式で記憶していることを仮定する。

s_{k}=x_{k+1}-x_{k}

カテゴリ（最適化 • アルゴリズム） • ソフトウェア

[1]

[2]

[3]

[4]

[5]

一般	バリア関数ペナルティ関数法
微分可能	ラグランジュの未定乗数法拡張ラグランジュ乗数法（英語版）逐次二次計画法逐次線形計画法

L-BFGS法とは？ わかりやすく解説

L-BFGS法

アルゴリズム

急上昇のことば

「L-BFGS法」の関連用語

L-BFGS法とは？わかりやすく解説