Regularized Stochastic BFGS Algorithm

最近読んだ論文のポイントを書いておく。

"RES: Regularized Stochastic BFGS Algorithm"
by Aryan Mokhtari, Alejandro Ribeiro
http://arxiv.org/abs/1401.7625

１．問題定式化
変数 $w \in R^n$, ランダム変数 $\theta \in R^p$ があって、関数 $f(w, \theta): R^{n \times p} \to R$ について、$\theta$ での期待値 $F(w) := E_{\theta} [f(w, \theta)]$ を最小化する。つまり、

$w^* = argmin_{w} E_{\theta} [f(w, \theta)]$

２．今回のアルゴリズムの目玉

Stochastic Gradient を $s = \frac{1}{L} \sum_{l=1}^L \nabla f(w, \theta_l)$ としたとき、Stochastic Gradient Method に現れる更新式 $w_{t+1} = w_t - \epsilon_t s$ にヘッセ行列の近似行列である $B$ の逆行列を挿んで、$w_{t+1} = w_t - \epsilon_t B_t^{-1} s$ とする。
また、$B_{t+1}$ を$B_t$からつくるときに、正則項を入れている。

３．主な結果

＋条件数がいい問題では、Stochastic Gradient Method と同じだけの性能しか出ない
＋条件数が悪いときは、正則化 Stochastic BFGS のほうがいい結果が出る

４．ほかに面白い情報
Stochastic Newton 法があまり使われていないのは、Newton ステップの不偏推定量が簡単に計算できないため。


論文の構成としては、アルゴリズムの紹介、収束性の証明、数値実験結果、というところ。