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の符号変わることに注意。