行列が半正定値になってほしかった話

たまにはマジメな話も書いてみる

（おそらくボツ方針なので公開しても良きでしょ）

（キーワード）

弱凸関数・ヘッセ行列・半正定値行列

f:id:chika0509:20190619195658p:plain

背景

最近、弱凸関数(weakly convex function)の最適化問題を考えている。

職場で何人かの優秀最適化ニンゲンにこの単語をチラッと出してみたのだけど意外に知らないので、どうもマイナーな単語なのかもしれない（？）。

弱凸関数というのは要するに

もうちょいで凸関数！でも残念！非凸でしたァ😂

という非凸関数のクラスで、滑らかでない（勾配がリプシッツ連続でない）関数も含んでいる。

ふつう、非凸かつ滑らかでない関数に関する最適化問題というのは、

定常点(微分ゼロの点；局所解・鞍点・ほか微分ゼロなflat regionも含む)への収束を示すことすらムリポなのだけど、

弱凸なら定常点への収束証明くらいはなんとかなるで！！とのことで、

最適化系の有名ジャーナルに最近ちらほらソレ系の話題が出ているごようす。

定常点収束が言えると、

初期解ランダムに振って並列にぶん回して、

1個でもよさげな解に辿り着ければヨッシャ！

みたいなことができるので、少しは嬉しい、という理解。

弱凸関数というのは、

$x \mapsto f(x) + \rho \|x \|^2$

が凸関数になるような関数 $f(x)$ のこと（ここで $\rho$ は非負定数 *1 )

$\rho-$ 強凸関数(strongly convex function)と言ってなんのことかわかる人は

定義式の $\rho$ の項の符号を逆転させたものと言ったほうがわかるかもしれない。

つまり、こういうこと。

$f(x) \geq f(y) + \langle \xi, x-y \rangle - \frac{\rho}{2}\| x - y \|^2 ( \xi \in \partial_x f )$

またヘッセ行列を使ってこんなふうにも書ける

$\nabla^2 f \succeq - \rho I$

（定義からほとんど明らか）

weakly convex functionまわりの話題はこのブログを見ると良きですが（13分で読めるらしい）

ads-institute.uw.edu

非凸かつ非滑らかでも定常点収束が保証されるのは

弱凸関数の場合、Moreau envelopeを使ってスムージングをかけると強凸関数の最適化問題に近似できるから、という理屈（詳細はブログなり論文なりをご参照あれ）なのだけど、

弱凸関数に限らず言えば、Moreau envelopeを使う話は昔からあるらしいので、

最適化ニンゲンから見ると、それほど驚くべき話ではないのかもしれない（？）。

やりたかったこと

ニューラルネッツのような関数 $h_{\theta}$ を最適化したいときに、

ニュラールネッツが弱凸関数になるように制約をかけながら最適化できれば

定常点収束が言えて良きなんじゃないかと考えた。

具体的にはこんなかんじの最小化問題で、

$\min_{\theta} \frac{1}{n} \sum_i l (h_{\theta}(x_i), y_i) + \lambda \Omega_{\theta}$

罰則項 $\Omega_{\theta}$ として、

$h_{\theta}$ を弱凸にしてくれる関数、

つまり行列 $\nabla^2 h_{\theta} + \rho I$ を半正定値行列にしてくれるような関数

を導入すればいけるんじゃないか？？と考えていた。

結論をいうと、まず $h_{\theta}$ が $\rho-$ 弱凸だからといって、

誤差関数 $l(h_{\theta}(x_i), y_i)$ が $\theta$ に関して $\rho-$ 弱凸だとは限らないし、

２乗損失とかで仮に $\rho^2-$ 弱凸になるとかが言えたとして、

というか罰則項 $\Omega_{\theta}$ が弱凸になってくれないと困るけど

（全体として弱凸でないと先ほどのMoreau envelopeで定常点収束の話が使えない）

そもそもヘッセ行列（というか2階導関数）が弱凸の保証がどこにもないやんけ？？

となり、今日はここまで！やむなし！！となった。

考えたこと

でもこういう

パラメータ $\theta$ の関数が成分になっているような行列が

半正定値行列になってほしいとき、ヒトはナニを考えるのだろう？？

と、少し興味が湧いたので今回こうして考えたことを文章に書き起こしてみた。

勾配ノルムに制約を課す話なら例えばW-GANとか、まだあり得る話だと思うのだけど、

ヘッセ行列に制約を課す話は聞いたことがなくてフムゥと悩んでしまった。

（そもそも計算量がデカくなるし、あまり美しくない気がする）

以下、考えたことまとめ

半正定値行列は直交行列の積に書き下せる！ → 直交行列を新たなパラメータで表して、それ含めて推定する → そんなことできるんか・・・？
半正定値行列は特異値（固有値）が全て非負 → 最小固有値が非負になるような制約を課す → 最大固有値は行列のスペクトルノルム、最小固有値は逆行列のスペクトルノルムの逆数*2 → 逆行列が求められる前提で逆行列のスペクトルノルムを使った関数で制約 $\Omega_{\theta}$ を表す？（計算はpower iterationとかで頑張る？？）