L-BFGS法の更新式を導出

L-BFGS法の更新式を導出してみる。

ニュートン法の復習

最小化したい損失関数を$L(\mathit{w})$とする。

$${\mathit{w}}_{k+1}={\mathit{w}}_k-{\alpha }_k{\mathit{H}}_k^{-1}{\mathit{g}}_k$$

ただし、${\alpha }_k$はステップ幅、${\mathit{g}}_k$は勾配ベクトル、${\mathit{H}}_k$はヘッセ行列である。

詳しくは弊ブログのニュートン法の更新式を導出を参照。

BFGS法

まずBFGS法について。

セカント法 (secant method)によるヘッセ行列の近似

割線法ともいう。求根アルゴリズム（root-finding algorithm）の1種である。
関数$f(x)$が区間$[x_{n-2},x_{n-1}]$で連続であり、かつ根が1つだけ存在する場合

$$x_{n+1}=x_n-\frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})}f(x_n)$$

として$x$を更新していく。

セカント法を用いて${\mathit{w}}_k$の更新式を求めると

$${\mathit{w}}_{k+1}={\mathit{w}}_k-\frac{{\mathit{w}}_k-{\mathit{w}}_{k-1}}{{\mathit{g}}_k-{\mathit{g}}_{k-1}}{\mathit{g}}_k$$

となる。これは

$${\mathit{H}}_k\approx {\mathit{B}}_k=\frac{{\mathit{g}}_k-{\mathit{g}}_{k-1}}{{\mathit{w}}_k-{\mathit{w}}_{k-1}}$$

とヘッセ行列${\mathit{H}}_k$を正定値対称行列${\mathit{B}}_k$で近似していることになる。

（TODO: なぜ$\frac{{\mathit{g}}_k-{\mathit{g}}_{k-1}}{{\mathit{w}}_k-{\mathit{w}}_{k-1}}$が正定値対称行列になるのか？）

${\mathit{H}}_k$の更新

${\mathit{s}}_k={\mathit{w}}_{k+1}-{\mathit{w}}_k,{\mathit{y}}_k={\mathit{g}}_{k+1}-{\mathit{g}}_k$とすると、 ${\mathit{H}}_k$の更新式は、

$${\mathit{H}}_{k+1}=[\mathit{I}-\frac{{\mathit{s}}_k{\mathit{y}}_k^T}{{\mathit{y}}_k^T{\mathit{s}}_k}]{\mathit{H}}_k[\mathit{I}-\frac{{\mathit{y}}_k{\mathit{s}}_k^T}{{\mathit{y}}_k^T{\mathit{s}}_k}]+\frac{{\mathit{s}}_k{\mathit{s}}_k^T}{{\mathit{y}}_k^T{\mathit{s}}_k}$$

と表される（TODO: 要導出）。

${\mathit{\rho }}_k=\frac{1}{{\mathit{y}}_k^T{\mathit{s}}_k},{\mathit{V}}_k=\mathit{I}-\frac{{\mathit{y}}_k{\mathit{s}}_k^T}{{\mathit{y}}_k^T{\mathit{s}}_k}$とすると、

$${\mathit{H}}_{k+1}={\mathit{V}}_k^T{\mathit{H}}_k{\mathit{V}}_k+{\mathit{\rho }}_k{\mathit{s}}_k{\mathit{s}}_k^T$$

BFGS法ではヘッセ行列を陽に求める必要はなくなったが、
${\mathit{H}}_k$は対称行列なので$O(\frac{n^2-n}{2}+n)=O(\frac{n^2}{2}+\frac{n}{2})$のメモリ領域を必要とする。

LBFGS法

更新式を再帰的に展開すると、

$$\begin{array}{rl}{\mathit{H}}_{k+1}=& ({\mathit{V}}_k^T\cdots {\mathit{V}}_0^T){\mathit{H}}_0({\mathit{V}}_0\cdots {\mathit{V}}_k)\\ & +{\rho }_0({\mathit{V}}_k^T\cdots {\mathit{V}}_1^T){\mathit{s}}_0{\mathit{s}}_0^T({\mathit{V}}_1\cdots {\mathit{V}}_k)\\ & +{\rho }_1({\mathit{V}}_k^T\cdots {\mathit{V}}_2^T){\mathit{s}}_1{\mathit{s}}_1^T({\mathit{V}}_2\cdots {\mathit{V}}_k)\\ & ⋮\\ & +{\rho }_k{\mathit{s}}_k{\mathit{s}}_k^T\end{array}$$

となる。
${\mathit{H}}_0$は正定値対角行列であり、 $k$ステップ分の$\mathit{w}$と$\mathit{g}$が必要になるのでメモリ使用量は$O((2k+1)n)$。
つまりステップ数が増えるにつれメモリ使用量も増えてしまう。

そこで、全ステップではなく直近$m$ステップの$\mathit{w}$と$\mathit{g}$を使用するようにする。
$m$は通常$<10$などの小さい値が取られる。

$$\begin{array}{rl}{\mathit{H}}_{k+1}=& ({\mathit{V}}_k^T\cdots {\mathit{V}}_{k-m}^T){\mathit{H}}_0({\mathit{V}}_{k-m}\cdots {\mathit{V}}_k)\\ & +{\rho }_{k-m}({\mathit{V}}_k^T\cdots {\mathit{V}}_{k-m+1}^T){\mathit{s}}_{k-m}{\mathit{s}}_{k-m}^T({\mathit{V}}_{k-m+1}\cdots {\mathit{V}}_k)\\ & +{\rho }_{k-m+1}({\mathit{V}}_k^T\cdots {\mathit{V}}_{k-m+2}^T){\mathit{s}}_{k-m+1}{\mathit{s}}_{k-m+1}^T({\mathit{V}}_{k-m+2}\cdots {\mathit{V}}_k)\\ & ⋮\\ & +{\rho }_k{\mathit{s}}_k{\mathit{s}}_k^T\end{array}$$

直近$m$ステップのみなのでメモリ使用量は$O((2m+1)n)$に抑えられる。

参考文献・URL

• Nocedal, Jorge. “Updating quasi-Newton matrices with limited storage.” Mathematics of computation 35.151 (1980): 773-782.
• Liu, Dong C., and Jorge Nocedal. “On the limited memory BFGS method for large scale optimization.” Mathematical programming 45.1 (1989): 503-528.
• 2.3 セカント法
• 2.7 準 Newton 法
• L-BFGS法はだからメモリが節約できるのか！ - あらびき日記
• 3分でわかるL-BFGS - Kotaro’s blog