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であることと$\mathrm{\nabla }f(x,y)=0$であることは同値。

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

$$f(x^{\prime },y)-f(x,y)\ge ⟨{\mathrm{\nabla }}_{x}f(x,y),x^{\prime }-x⟩=0$$

で右辺は仮定が$\mathrm{\nabla }f(x,y)=0$なのでゼロ。従って$f(x^{\prime },y)\ge f(x,y)$が任意の$y,x^{\prime }$について成立するので$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^{\ast })+f(x^{\ast },y)-2f\ast \le C\cdot (2f(x,y)-f(x,\tilde{y})-f(\tilde{x},y))$$

を満たすこと。ただし、$x^{\ast },y^{\ast }$は$f(x^{\ast },y^{\ast })=f^{\ast }$を満たす点、$\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$について

$$\Vert x-x^{\ast }{\Vert }_2^2+\Vert y-y^{\ast }{\Vert }_2^2\le \frac{C\beta }{\alpha }(\Vert x-\tilde{x}{\Vert }_2^2+\Vert y-\tilde{y}{\Vert }_2^2)$$

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

Proof : $\alpha$-MSC性より

$$\begin{array}{c}\frac{\alpha }{2}\Vert x-x^{\ast }{\Vert }_2^2\le f(x,y^{\ast })-f(x^{\ast },y^{\ast })+0\\ \frac{\alpha }{2}\Vert y-y^{\ast }{\Vert }_2^2\le f(x^{\ast },y)-f(x^{\ast },y^{\ast })+0\end{array}$$

ちなみにゼロ、のところは${\mathrm{\nabla }}_{x}f(x^{\ast },y^{\ast })={\mathrm{\nabla }}_{y}f(x^{\ast },y^{\ast })=0$による。2式を足し合わせることによる

$$\frac{\alpha }{2}(\Vert x-x^{\ast }{\Vert }_2^2+\Vert y-y^{\ast }{\Vert }_2^2)\le f(x,y^{\ast })+f(x^{\ast },y)-2f(x^{\ast },y^{\ast })$$

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

$$\begin{array}{c}f(x,y)-f(\tilde{x},y)+0\le \frac{\beta }{2}\Vert x-\tilde{x}{\Vert }_2^2\\ f(x,y)-f(x,\tilde{y})+0\le \frac{\beta }{2}\Vert y-\tilde{y}{\Vert }_2^2\end{array}$$

なので

$$2f(x,y)\le f(\tilde{x},y)+f(x,\tilde{y})+\frac{\beta }{2}(\Vert x-\tilde{x}{\Vert }_2^2+\Vert y-\tilde{y}{\Vert }_2^2)$$

がわかる。ちなみにこっちのゼロは${\mathrm{\nabla }}_{x}f(\tilde{x},y)={\mathrm{\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 {ϵ}^{-1})$ステップで$f(x_T,y_T)\le f^{\ast }+ϵ$とすることができる。

証明) 今度は${\mathrm{\Phi }}_t=f(x_t,y_t)-f^{\ast }$とおく。この${\mathrm{\Phi }}_t\to 0$を示すことが出来ればok。$\beta$-MSS性において${\mathrm{\nabla }}_{x}f(x^{\ast },y^{\ast })=0$を使うことにより

$$f(x_{t+1},y^{\ast })-f(x^{\ast },y^{\ast })\le \frac{\beta }{2}\Vert x_{t+1}-x^{\ast }{\Vert }_2^2$$

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

$${\mathrm{\Phi }}_{t+1}=f(x_{t+1},y_{t+1})-f^{\ast }\le f(x_{t+1},y^{\ast })-f^{\ast }\le \frac{\beta }{2}\Vert x_{t+1}-x^{\ast }{\Vert }_2^2$$

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

$$\begin{array}{rl}f(x_t,y_t)& \ge f(x_{t+1},y_t)+\frac{\alpha }{2}\Vert x_{t+1}-x_t{\Vert }_2^2\\ & \ge f(x_{t+1},y_{t+1})+\frac{\alpha }{2}\Vert x_{t+1}-x_t{\Vert }_2^2\end{array}$$

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

$${\mathrm{\Phi }}_t-{\mathrm{\Phi }}_{t+1}\ge \frac{\alpha }{2}\Vert x_{t+1}-x_t{\Vert }_2^2$$

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

$$\Vert x_t-x^{\ast }{\Vert }_2^2\le \Vert x_t-x^{\ast }{\Vert }_2^2+\Vert y_t-y^{\ast }{\Vert }_2^2$$

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

$$\Vert x_t-x^{\ast }{\Vert }_2^2\le \frac{C\beta }{\alpha }(\Vert x_t-\tilde{x}{\Vert }_2^2+\Vert y_t-\tilde{y}{\Vert }_2^2)$$

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

$$\Vert x_t-x^{\ast }{\Vert }_2^2\le \frac{C\beta }{\alpha }\Vert x_t-x_{t+1}{\Vert }_2^2$$

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

$$\begin{array}{c}{\mathrm{\Phi }}_{t+1}\le \frac{\beta }{2}\Vert x_{t+1}-x^{\ast }{\Vert }_2^2\le \beta (\Vert x_{t+1}-x_t{\Vert }_2^2+\Vert x_t-x^{\ast }{\Vert }_2^2)\\ \le \beta (1+\frac{C\beta }{\alpha })\Vert x_{t+1}-x_t{\Vert }_2^2\le \frac{2\beta }{\alpha }(1+\frac{C\beta }{\alpha })({\mathrm{\Phi }}_t-{\mathrm{\Phi }}_{t+1})\end{array}$$

2行目にかけて、直前の$\Vert x_t-x^{\ast }{\Vert }_2^2$の不等式を用いている。さらに、その次の不等式で$\Vert x_{t+1}-x_t{\Vert }_2^2$と${\mathrm{\Phi }}_t-{\mathrm{\Phi }}_{t+1}$の不等式をつかっている。これを${\mathrm{\Phi }}_{t+1}$について整理すると

$${\mathrm{\Phi }}_{t+1}\le {\mu }_0\cdot {\mathrm{\Phi }}_t$$

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

$${\mu }_0=\frac{2\kappa (1+C\kappa )}{1+2\kappa (1+C\kappa )},\kappa =\frac{\beta }{\alpha }$$

とおいた。

$$\begin{array}{c}{\mathrm{\Phi }}_T\le \frac{{\mathrm{\Phi }}_1}{{\mu }_0}\cdot {\mu }_0^T\\ f(x_T,y_T)\le f^{\ast }+\frac{{\mathrm{\Phi }}_1}{{\mu }_0}\cdot {\mu }_0^T\end{array}$$

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