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 ステップの不偏推定量が簡単に計算できないため。


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

CVX の log_det(X) と log(det(X))

正定値行列 X について、log(det(X)) はバリア関数になったりするため、内点法の理論とも密接に関係している。

CVX には、 log も det も準備されているが、log_det という関数も準備されている。
log(det(X)) と log_det(X) は数学的には同値なのであれば、 CVX ではどちらか一方では解が求まるが、もう一方では解が求まらない、という状況が起こったりする。

おそらく、log_det のほうは、 X を対称正定値行列に限定していることから、微分計算にダイレクトに inv(X) を用いているのでは？と推測してみたりする。

研究者の人生はアブストラクトとして数秒で消費される運命にある

今日になって、研究についての本を読んでいるが、本の最初の節のタイトルが

「研究者の人生はアブストラクトとして数秒で消費される運命にある」

となっている。
一見するとネガティブな言葉に見えがちだけど、本を読むとポジティブな発想に基づいた言葉であった。
この節を読むだけでも、とても参考になる。

今日の作業内容：証明検討 1h
今日のランチ：豚肉にんにくの芽炒め
明日の予測作業時間：3h

rank 制約付き行列の体積

arXiv に出てきた論文をチェックしていると、rank が制限されたところの対称行列の体積を計算しているものがあった。

http://arxiv.org/abs/1401.4853

SDP 緩和などは、rank-1 制約を緩和することで得ているものが多いので、rank-1の行列の体積が分かると SDP 緩和の強さなどを計量的に評価する道具になるのかもしれない。

今日の作業内容：証明検討 2h

今日のランチ：食堂 若鶏の酢豚風炒め

明日の予測作業時間：2h

証明の勉強になる本

数理最適化関係の本は多くあるが、非線形最適化などの証明が詳しく載っている本はそれほど多くない。

証明の勉強として参考になる本としては、日本語であれば、

工学基礎 最適化とその応用

が役に立つし、洋書では

Linear and Nonlinear Optimization

がおススメである。
たとえば、「最急降下法などがなぜ最適解に収束するか」などは非線形最適化の証明の基本となる要素を多く含んでいるので、こういった本の証明を暗記してみると勉強になる。

今日の作業内容：証明検討　1h
今日のランチ：久絵 カキフライ定食
明日の予測作業時間：3h

CPLEXのインストールで Malformed encoding error となるときは

CPLEX を Linux にインストールするときに、Java が Malformed encoding error というメッセージを出力してインストールできないときがある。

このときは、
export PS1= '>'
としてから実行すると、なぜかインストールできる。
どうやら、Java が環境変数の PS1 を参照しているようだ。

今回参考にしたのは、
http://www.maplesoft.com/support/faqs/detail.aspx?sid=35272

今日の作業内容：証明検討 4h
今日のランチ：ちゅらさん 豆腐ちゃんぷる
明日の予測作業時間：2h

emacs で日本語ディレクトリを扱う

Debian で UTF-8による日本語ディレクトリにあるファイルを emacs で開こうとすると
（たとえば、$ emacs ~/テスト/test.txt など）
emacs 自体は起動できるが、中身が表示されない状態になる。

これを回避するには、日本語ファイル名を扱えるようにするのと同様に
(set-default-coding-systems 'utf-8)
を ~/.emacs.d/init.el に追加すればよい。

参考にしたのは、
http://q.hatena.ne.jp/1254913040

今日の作業内容：定式化検討 2h
今日のランチ：味庵 牛焼肉丼
明日の予測作業時間：3h

温故知新

以前に一通り読んだ論文をもう一度読み直しているが、証明などでよくわからなかった点がようやくわかるようになった。
一度時間を置いたうえで、もう一度戻ってくると、別のところで勉強したことが役にたつようだ。
今回の読み直しで分かった点から、またいろんなことがわかってきたので、それを役立てていこうと思う。

今日の作業内容：証明読み直し 2h
今日のランチ：つかさ かんぱちのから揚げ
明日の予測作業時間：4h

発表を聞くことも大事

今日は研究集会に参加して、発表を聞いてきた。
やはり、自分の見えている範囲は狭いので、こうやって発表を聞くと違った視点でものを見ることが出来て大変勉強になる。
もう少し時間があれば、もっと発表を聞きたいところでもあった。

今日の作業内容：論文読み込み 2h
今日のランチ：食堂 チキンソテーの和風おろしソース
明日の予測作業時間：3h

1000記事目

今日の投稿で、このブログは1000記事目に到達しました。
スタートしたのが2009年9月26日なので、ざっと3年3か月といったところかと思います。

ここまでの1000記事を振り返ってみるといろんなことがありますが、ここまで来れたのも多くの方に支えてもらっているからこそだと思っています。
このブログでは日本人が登場しないことになっていますので、具体的にどの方に支えてもらったかは明記しませんが、あちこちの方にお世話になっております。

今日も、証明が行き詰りつつも、そんな証明を楽しんでいるのも、ここまでのことがあってこそ。
2000記事になるのがいつの日付になるかは分かりませんが、ここまでのお世話になったことからスタートして社会に役立てたりなどで形にできたら、と思ったりいしています。


今日の作業内容：証明の続き 2h
今日のランチ：シッダルータ エッグカレー
明日の予測作業時間：3h

証明の続きを検討

昨日から続けての証明検討だが、関数の形がまだ手探り状態なので、もう少し検討が必要そうだ。
でも、こういったコツコツと進めていくのが、あとあとでは要になってきそうでもある。

今日の作業内容：証明検討 2h
今日のランチ：らく 鶏の照り焼き定食
明日の予測作業時間： 3h

証明について、いろいろと検討

今まで少しずつ調べておいたことについて、本腰を入れて証明を検討することにした。
まずは、どういった数式で記述すると証明の見通しがよくなるか、というところからであるが、このあたりは手探りからとなる。
ある程度の形が見えたところで記述を再検討したいと思ってもいる。

今日の作業内容：証明検討 2h
今日のランチ：味庵 白身魚のチリソース
明日の予測作業時間：2h