Reference Chapter4. of Non-convex Optimization for Machine Learning https://arxiv.org/abs/1712.07897 "Alternating Minimization".
多変数関数における変数の分割
関数\(f:\mathbb{R}^d\to\mathbb{R}\)を目的関数とする最小化問題について考える。\(d=p+q\)なる\(p,q\)を用いて関数\(f\)を\(f:\mathbb{R}^p\times\mathbb{R}^q\to\mathbb{R}\)と見なすことが出来る。これは変数の内\(p\)個のサブセットを取ってきて変数を分割しただけ。残った変数\(q\)個をまた別な変数とおく。これを\((x,y)\in\mathbb{R}^p\times\mathbb{R}^q\)として新たに\(f(x,y)\)とおく。よりたくさんの変数に分割する場合にも2分割を繰り返せばよいので一般性を失っていない。制約集合による条件\((x,y)\in\mathcal{X}\times\mathcal{Y}\)を考えてもよい。一般にはそれぞれの制約集合が独立にな条件で与えられているとは限らないので\((x,y)\in\mathcal{Z}\subset\mathbb{R}^p\times\mathbb{R}^q\)という形になることに注意せよ。
本稿では基本的にベクトルの成分をいじくらないことから、混同のおそれが無く変数がベクトルであっても細字で記載するものとする。
定義1 (結合凸性 : Joint Convexity)
\(f:\mathbb{R}^p\times\mathbb{R}^q\to\mathbb{R}\)を連続微分可能とする。このとき、 任意の\((x_1,y_1),(x_2,y_2)\in\mathbb{R}^p\times\mathbb{R}^q\)について
\[ f(x_2,y_2)\ge f(x_1,y_1)+\left\langle \nabla f(x_1,y_1), (x_2,y_2)-(x_1,y_1) \right\rangle\]
を満たすとき、\(f\)は結合凸であるという。
定義2 (周辺凸性 : Marginal Convexity)
\(f:\mathbb{R}^p\times\mathbb{R}^q\to\mathbb{R}\)を連続微分可能とする。このとき、 任意の\(y\in\mathbb{R}^q\)について、\(f(\cdot,y)\)という\(x\)についての関数が凸であるとき、すなわち
\[ f(x_2,y)\ge f(x_1,y)+\left\langle \nabla_x f(x_1,y),x_2-x_1 \right\rangle\]
を任意の\(x_1,x_2\in\mathbb{R}^p\)について満たすとき、\(f(x,y)\)は\(x\)について周辺凸であるという。
Prop. 1 : 結合凸関数であれば任意の変数の部分集合について周辺凸関数である
Proof : 結合凸性の定義の右辺は
\[ f(x_1,y_1)+\langle\nabla_x f(x_1,y_1),x_2-x_1\rangle +\langle\nabla_y f(x_1,y_1),y_2-y_1\rangle\]
と書き直せる。結合凸関数においては、任意の\(y_1,y_2\)についてこれが成り立っているから\(y=y_1=y_2\)と取れば第3項はゼロ、直ちに周辺凸性の定義が従う。
定義3 (周辺強凸関数、周辺強？関数 : Marginally Strongly Convex/Smooth Function)
\(f:\mathbb{R}^p\times\mathbb{R}^q\to\mathbb{R}\)を連続微分可能とする。このとき、任意の\(y\in\mathbb{R}^q\)について、\(f(\cdot,y)\)という\(x\)についての関数が\(\alpha\)-Strongly Convex : SC、\(\beta\)-Strongly Smooth : SSであるとき、すなわち
\[ \frac{\alpha}{2}\|x_2-x_1\|_2^2\le f(x_2,y)-f(x_1,y)-\langle \nabla_x f(x_1,y), x_2-x_1\rangle\le \frac{\beta}{2}\|x_2-x_1\|_2^2\]
を任意の\(x_1,x_2\in\mathbb{R}^p\)について満たすとき、関数\(f(x,y)\)は\(x\)についてそれぞれ\(\alpha\)-Marginally Strongly Convex : MSC、\(\beta\)-Marginally Strongly Smooth : MSSであるという。なお、それぞれの日本語は\(\alpha\)-周辺強凸性、\(\beta\)-周辺強なんとか性。なんとかの部分は不明。
Prop. 2 : \(\alpha\)-SC、\(\beta\)-SSであれば任意の変数の部分集合について\(\alpha\)-MSC、\(\beta\)-MSS
Proof : Prop. 1に同じである。念のため結合したものにあたる定義を書き下しておくと、
\[ \begin{gather} \frac{\alpha}{2}\|(x_2,y_2)-(x_1,y_1)\|_2^2\le f(x_2,y_2)-f(x_1,x_1)-\langle \nabla f(x_1,y_1), (x_2,y_2)-(x_1,y_1)\rangle\\ \le\frac{\beta}{2}\|(x_2,y_2)-(x_1,y_1)\|_2^2 \end{gather}\]
となり
\[ \begin{gather} \|(x_2,y_2)-(x_1,y_1)\|_2^2=\|x_2-x_1\|_2^2+\|y_2-y_1\|_2^2\\ \langle \nabla f(x_1,y_1), (x_2,y_2)-(x_1,y_1)\rangle= \langle\nabla_x f(x_1,y_1),x_2-x_1\rangle +\langle\nabla_y f(x_1,y_1),y_2-y_1\rangle \end{gather}\]
として\(y=y_1=y_2\)と取ればこれらの右辺第2項はゼロ、直ちに\(\alpha\)-MSC、\(\beta\)-MSSの定義が従う。
交互最小化:Alternating Minimization
関数\(f(x,y)\)を最小化する\((x,y)\)を求めたいとして、次の手順を踏む。
- \((x_1,y_1)\)を適当に初期化する
- \(x_{t+1}:=\mathop{\rm argmin}_{x\in\mathcal{X}} f(x,y_t)\)
- \(y_{t+1}:=\mathop{\rm argmin}_{y\in\mathcal{Y}} f(x_{t+1},y)\)
- \(t=1,2,\dots,T\)についてこれを繰り返す
- \((x_T,y_T)\)を出力とする
定義4 (Marginally Optimum Coordinate)
関数\(f\)を\(\mathcal{X}\times\mathcal{Y}\)上の関数とする。\(\tilde{x}\in\mathcal{X}\)が、固定されたある\(y\in\mathcal{Y}\)について\(\forall x\in\mathcal{X}, f(\tilde{x},y)\le f(x,y)\)を満たすような点であるとき\(\tilde{x}\)を\(y\)についての周辺最適点といい、そのような点の集合をmOPT\(_f(y)\)と表記する。同じように\(y\)についても\(x\)についての周辺最適点による集合を\(\tilde{y}\in\)mOPT\(_f(x)\)と表記する。
Remark : Coordinateとあるが、最適点や点の集合に対して「座標」は不適切であるので無視。
定義5 (Bistable Point)
関数\(f\)を\(\mathcal{X}\times\mathcal{Y}\)上の関数とする。点\((x,y)\in\mathcal{X}\times\mathcal{Y}\)が\(x\in\)mOPT\(_f(y)\)かつ\(y\in\)mOPT\(_f(x)\)を満たすとき、bistableな点であるという。
Remark: Bistableを日本語にすることを諦めた。
定理1:それぞれの変数について強くなめらかな結合凸関数に対する交互最小化は収束する
\(f:\mathbb{R}^p\times\mathbb{R}^q\to\mathbb{R}\)を連続微分可能な結合凸関数とし、それぞれの変数についての\(\beta\)-MSS性を満たすとする。また\(f^*=\min_{x,y}f(x,y)>-\infty\):最適値が下に有界、\(S_0=\{x,y : f(x,y)\le f(0,0)\}\subset\mathbb{R}^{p+q}\)は有界領域とする。このとき、\((x_1,y_1)=(0,0)\)から上記の交互最小化の手続きを行うと、多くとも\(T=O(\epsilon^{-1})\)ステップで\(f(x_T,y_T)\le f^*+\epsilon\)を満たすことができる。
証明) 交互最小化を行っていることからただちに、
\[ f(x_{t+1},y_{t+1})\le f(x_{t+1},y_t)\le f(x_t,y_t)\]
\(S_0\)とこの単調減少性より任意の\(t\)について\((x_t,y_y)\in S_0\)がわかる。有界領域としている\(S_0\)上を動くため、\((x_t,y_y)\)も有界であり発散しない。\(\Phi_t=1/(f(x_t,y_t)-f^*)\)とすると常に\(\Phi_t>0\)、さらに\(\Phi_t\to\infty\)であれば最適値への収束が言える。
\(t\le 2\)とする。周辺最小化を勾配降下によって行うときにある1ステップを次のように書く。
\[ \begin{gather} \tilde{x}_{t+1}=x_t-\frac1\beta \nabla_x f(x_t,y_t)\\ \tilde{x}_{t+1}-x_t=-\frac1\beta \nabla_x f(x_t,y_t) \end{gather}\]
周辺Strongly Smooth性から
\[ \begin{align} f(\tilde{x}_{t+1},y_t) &\le f(x_t,y_t)+\left\langle \nabla_x f(x_t,y_t),\tilde{x}_{t+1}-x_t \right\rangle+\frac{\beta}{2}\|\tilde{x}_{t+1}-x_t\|_2^2\\ &= f(x_t,y_t)-\left\langle \nabla_x f(x_t,y_t),\frac1\beta\nabla_x f(x_t,y_t) \right\rangle+\frac{\beta}{2}\left\|-\frac1\beta\nabla_x f(x_t,y_t)\right\|_2^2\\ &= f(x_t,y_t) -\frac1\beta\|\nabla_x f(x_t,y_t)\|_2^2 +\frac{\beta}{2}\cdot \frac1{\beta^2}\|\nabla_x f(x_t,y_t)\|_2^2\\ &= f(x_t,y_t) -\frac1{2\beta}\|\nabla_x f(x_t,y_t)\|_2^2 \end{align}\]
\(\tilde{x}_{t+1}\)は、周辺最小化の結果\(x_{t+1}\)を求めるときのある1ステップ後の結果であり、最終的な結果\(x_{t+1}\)における関数値はその途中よりも必ず小さい。従って\(f(x_{t+1},y_t)\le f(\tilde{x}_{t+1},y_t)\)で、この右辺がさらに1つ上の式よりも小さい。
\[ f(x_{t+1},y_{t+1})\le f(x_{t+1},y_t)\le f(x_t,y_t) -\frac1{2\beta}\|\nabla_x f(x_t,y_t)\|_2^2\]
さらに、いま\(t\le 2\)としていて1つ前のステップで\(y_t\in\mathop{\rm argmin}_{y} f(x_t,y)\)と決めていたので\(\nabla_y f(x_t,y_t)=0\)が成り立っており、
\[ \begin{align} \|\nabla f(x_t,y_t)\|_2^2 &=\|\nabla_x f(x_t,y_t)\|_2^2+\|\nabla_y f(x_t,y_t)\|_2^2\\ &=\|\nabla_x f(x_t,y_t)\|_2^2 \end{align}\]
が成立。 関数\(f\)の結合凸性より
\[ f(x_t,y_t)-f^*\le \left\langle \nabla f(x_t,y_t), (x_t,y_t)-(x^*,y^*) \right\rangle\]
さらに、\((x_t,y_t),(x^*,y^*)\in S_0\)で、\(S_0\)は有界であるのでその差のノルムも有界となる。よって、ある定数\(R\)を用いて\(\|(x_t,y_t)-(x^*,y^*)\|_2\le R\)とできる。Cauchy-Schwartzの不等式より
\[ \begin{align} \left\langle \nabla f(x_t,y_t), (x_t,y_t)-(x^*,y^*) \right\rangle &\le \|\nabla f(x_t,y_t)\|_2\|(x_t,y_t)-(x^*,y^*)\|_2\\ &\le R\|\nabla f(x_t,y_t)\|_2 \end{align}\]
これらを一旦まとめて
\[ \begin{align} f(x_t,y_t)-f^*&\le R\|\nabla f(x_t,y_t)\|_2\\ &=R\|\nabla_x f(x_t,y_t)\|_2 \end{align}\]
これを先の不等式に代入することにより
\[ f(x_{t+1},y_{t+1})\le f(x_t,y_t)-\frac1{2\beta R^2}(f(x_t,y_t)-f^*)^2\]
\(\Phi_t=1/(f(x_t,y_t)-f^*)\)をつかってこれらを書き直すと
\[ \frac1{\Phi_{t+1}}\le \frac1{\Phi_t}-\frac1{2\beta R^2}\frac1{\Phi_t^2}\]
さらに\(\Phi_t<\Phi_{t+1}\)を右辺第2項の分母の\(\Phi_t^2=\Phi_t\cdot\Phi_t\)の1個目だけに使って大小関係に注意すると
\[ \frac1{\Phi_{t+1}}\le \frac1{\Phi_t}-\frac1{2\beta R^2}\frac1{\Phi_t\Phi_{t+1}}\]
がわかる。ここで再び\(\Phi_t>0\)より\(\Phi_t\Phi_{t+1}>0\)を両辺に掛けると
\[ \Phi_{t+1}-\Phi_t\ge\frac1{2\beta R^2}\]
最後に、
\[ \begin{align} \Phi_3-\Phi_2&\ge\frac1{2\beta R^2}\\ \Phi_4-\Phi_3&\ge\frac1{2\beta R^2}\\ &\vdots\\ \Phi_T-\Phi_{T-1}&\ge\frac1{2\beta R^2}\\ \end{align}\]
という感じにして両辺足し合わせることにより
\[ \begin{gather} \Phi_T-\Phi_2\ge \frac{T-2}{2\beta R^2}\\ \Phi_T\ge\frac{T-2}{2\beta R^2} \end{gather}\]
がいえる。\(\Phi_2>0\)に注意せよ。\(\Phi_T\)を戻して分母分子掛けると
\[ f(x_T,y_T)\le f^*+\frac{2\beta R^2}{T-2}\]
なのでざっくり\(T=O(\epsilon^{-1})\)ぽいことが言えた。オーダがどうこうはめんどくさいので説明しません。
次ページ、一般的な交互最小化の収束性について（２）につづく。