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