一般的な交互最小化の収束性について(2)

2019-11-15 10:552019-11-26 11:04

Reference Chapter4. of Non-convex Optimization for Machine Learning https://arxiv.org/abs/1712.07897 "Alternating Minimization".

前ページ、一般的な交互最小化の収束性についての続きです。

補題1 Bistable Pointの必要十分条件

関数\(f:\mathbb{R}^p\times\mathbb{R}^q\to\mathbb{R}\)が連続微分可能で、それぞれの変数について周辺凸関数であるとき、点\((x,y)\)がbistableであることと\(\nabla f(x,y)=0\)であることは同値。

Proof : bistableなら\(\nabla f(x,y)=0\)は明らか。不安なら前ページのProp. 1、 Prop. 2なんかの分解を参照せよ。逆は、まず\(x\)についての周辺凸性の定義より

\[ f(x',y)-f(x,y)\ge\langle\nabla_x f(x,y), x'-x\rangle=0\]

で右辺は仮定が\(\nabla f(x,y)=0\)なのでゼロ。従って\(f(x',y)\ge f(x,y)\)が任意の\(y,x'\)について成立するので\(x\)はmOPT\(_f(y)\)の点、同じように\(y\)\(y\)についての周辺凸性よりmOPT\(_f(x)\)の点であることが言える。よってbistableで逆も成立。

定義6 (Robust Bistability Property)

関数\(f:\mathbb{R}^p\times\mathbb{R}^q\to\mathbb{R}\)\(C\)-robust bistabeであるとは、ある\(C>0\)があって任意の\((x,y)\in\mathbb{R}^p\times\mathbb{R}^q\)について

\[ f(x,y^*)+f(x^*,y)-2f*\le C\cdot(2f(x,y)-f(x,\tilde{y})-f(\tilde{x},y))\]

を満たすこと。ただし、\(x^*,y^*\)\(f(x^*,y^*)=f^*\)を満たす点、\(\tilde{x},\tilde{y}\)\(\tilde{x}\in\)mOPT\(_f(y)\)\(\tilde{y}\in\)mOPT\(_f(x)\)である。

補題2 (Robust Bistability Property under \(alpha\)-MSC、\(\beta\)-MSS)

連続微分可能な関数\(f\)\(alpha\)-MSC、\(\beta\)-MSSであり、\(C\)-robust bistableであるとき任意の\((x,y)\in\mathbb{R}^p\times\mathbb{R}^q\)について

\[ \|x-x^*\|_2^2+\|y-y^*\|_2^2\le\frac{C\beta}{\alpha}(\|x-\tilde{x}\|_2^2+\|y-\tilde{y}\|_2^2)\]

を満たす。ただし、\(x^*,y^*\)\(f(x^*,y^*)=f^*\)を満たす点、\(\tilde{x},\tilde{y}\)\(\tilde{x}\in\)mOPT\(_f(y)\)\(\tilde{y}\in\)mOPT\(_f(x)\)である。

Proof : \(\alpha\)-MSC性より

\[ \begin{gather} \frac{\alpha}{2}\|x-x^*\|_2^2\le f(x,y^*)-f(x^*,y^*)+0\\ \frac{\alpha}{2}\|y-y^*\|_2^2\le f(x^*,y)-f(x^*,y^*)+0 \end{gather}\]

ちなみにゼロ、のところは\(\nabla_x f(x^*,y^*)=\nabla_y f(x^*,y^*)=0\)による。2式を足し合わせることによる

\[ \frac{\alpha}{2}(\|x-x^*\|_2^2+\|y-y^*\|_2^2)\le f(x,y^*)+f(x^*,y)-2f(x^*,y^*)\]

まったく同じようにして、\(\beta\)-MSS性より

\[ \begin{gather} f(x,y)-f(\tilde{x},y)+0\le\frac{\beta}{2}\|x-\tilde{x}\|_2^2\\ f(x,y)-f(x,\tilde{y})+0\le\frac{\beta}{2}\|y-\tilde{y}\|_2^2 \end{gather}\]

なので

\[ 2f(x,y)\le f(\tilde{x},y)+f(x,\tilde{y})+ \frac{\beta}{2}(\|x-\tilde{x}\|_2^2+\|y-\tilde{y}\|_2^2)\]

がわかる。ちなみにこっちのゼロは\(\nabla_x f(\tilde{x},y)=\nabla_y f(x,\tilde{y})=0\)によります。これらを\(C\)-robust stabilityの定義式にそのまま入れると主張の式が得られる。

定理:補題2の条件を満たす(凸とは限らない)関数に対する交互最小化は収束する

凸関数とは限らない連続微分可能な関数\(f:\mathbb{R}^p\times\mathbb{R}^q\)が、領域\(S_0=\{(x,y):f(x,y)\le f(0,0)\}\)においてそれぞれの変数について\(\alpha\)-MSC、\(\beta\)-MSSかつ\(C\)-robust stabilityを満たすとする。このとき、\((x_1,y_1)=(0,0)\)からスタートした交互最小化は多くとも\(T=O(\log \epsilon^{-1})\)ステップで\(f(x_T,y_T)\le f^*+\epsilon\)とすることができる。

証明) 今度は\(\Phi_t=f(x_t,y_t)-f^*\)とおく。この\(\Phi_t\to 0\)を示すことが出来ればok。\(\beta\)-MSS性において\(\nabla_x f(x^*,y^*)=0\)を使うことにより

\[ f(x_{t+1},y^*)-f(x^*,y^*)\le\frac{\beta}{2} \|x_{t+1}-x^*\|_2^2\]

を得る。ちなみに勾配がゼロは\(x^*,y^*\)がbistableであることから従う。さらに、交互最小化の手順より\(y_{t+1}\in\)mOPT\(_f(x_{t+1})\)であることが保証されているので

\[ \Phi_{t+1}=f(x_{t+1},y_{t+1})-f^* \le f(x_{t+1},y^*)-f^* \le \frac{\beta}{2}\|x_{t+1}-x^*\|_2^2\]

一見すると\(y^*\)の関数値が一番小さいような気がしますが\(x_{t+1}\)との組み合わせでは\(y_{t+1}\)の関数値の方が小さいということです。次に\(\alpha\)-MSC性において同様に\(\nabla_x f(x_{t+1},y_t)=0\)を用いることにより次を得る。ちなみにこちらの勾配がゼロというのは\(x_{t+1}\in\)mOPT\(_f(y_t)\)であることから従う。

\[ \begin{align} f(x_t,y_t)&\ge f(x_{t+1},y_t)+\frac{\alpha}{2}\|x_{t+1}-x_t\|_2^2\\ &\ge f(x_{t+1},y_{t+1})+\frac{\alpha}{2}\|x_{t+1}-x_t\|_2^2 \end{align}\]

1行目が\(\alpha\)-MSC性、2行目は同様に\(y_{t+1}\in\)mOPT\(_f(x_{t+1})\)であることから従う。両辺から\(f^*\)を引いて\(\Phi_t\)つかって表すと

\[ \Phi_t-\Phi_{t+1}\ge\frac{\alpha}{2}\|x_{t+1}-x_t\|_2^2\]

がわかる。次に補題2の式を使う。まず

\[ \|x_t-x^*\|_2^2\le\|x_t-x^*\|_2^2+\|y_t-y^*\|_2^2\]

が右辺第2項が正であることから従い、この右辺は補題2の左辺であるのでさらに上からおさえられる。よって、

\[ \|x_t-x^*\|_2^2\le\frac{C\beta}{\alpha}(\|x_t-\tilde{x}\|_2^2+\|y_t-\tilde{y}\|_2^2)\]

さらに、交互最小化の手順より\(y_t\in\)mOPT\(_f(x_t)\)だから右辺第2項は消える。さらに、\(x_{t+1}\in\)mOPT\(_f(y_t)\)から\(\tilde{x}\)\(x_{t+1}\)に書き換えられる。まとめると

\[ \|x_t-x^*\|_2^2\le\frac{C\beta}{\alpha}\|x_t-x_{t+1}\|_2^2\]

がわかる。最後に\((a+b)^2\le 2(a^2+b^2)\)\(\beta\)-MSSの式から

\[ \begin{gather} \Phi_{t+1}\le\frac{\beta}{2}\|x_{t+1}-x^*\|_2^2 \le\beta\left( \|x_{t+1}-x_t\|_2^2+\|x_t-x^*\|_2^2 \right)\\ \le \beta\left(1+\frac{C\beta}{\alpha}\right) \|x_{t+1}-x_t\|_2^2 \le \frac{2\beta}{\alpha}\left(1+\frac{C\beta}{\alpha}\right) (\Phi_t-\Phi_{t+1}) \end{gather}\]

2行目にかけて、直前の\(\|x_t-x^*\|_2^2\)の不等式を用いている。さらに、その次の不等式で\(\|x_{t+1}-x_t\|_2^2\)\(\Phi_t-\Phi_{t+1}\)の不等式をつかっている。これを\(\Phi_{t+1}\)について整理すると

\[ \Phi_{t+1}\le \mu_0\cdot\Phi_t\]

という形にできる。ここで

\[ \mu_0=\frac{2\kappa(1+C\kappa)}{1+2\kappa(1+C\kappa)} ,\qquad\kappa=\frac{\beta}{\alpha}\]

とおいた。

\[ \begin{gather} \Phi_T\le \frac{\Phi_1}{\mu_0}\cdot\mu_0^T\\ f(x_T,y_T)\le f^*+\frac{\Phi_1}{\mu_0}\cdot\mu_0^T \end{gather}\]

であるので、\(\mu_0<1\)から\(T\to\infty\)において右辺はゼロに行く。従って\(f(x_T,y_T)-f^*\to 0\)。ついでにオーダについては、\(\epsilon\sim \mu_0^T\)みたいな感じから\(T=O(\log 1/\epsilon)\)ぽいことがわかる。一応\(\mu_0<1\)でlogの符号変わることに注意。