ランダム座標降下法

ランダム化（ブロック）座標降下法は、ネステロフ（2010）とリヒタリクとタカチ（2011）によって普及した最適化アルゴリズムです。この方法の最初の分析は、滑らかな凸関数を最小化する問題に適用され、ネステロフ（2010）によって行われました。^[1]ネステロフの分析では、未知のスケーリング係数を持つ元の関数の2次摂動にこの方法を適用する必要があります。リヒタリクとタカチ（2011）は、これを必要としない反復計算の複雑さの境界を示しています。つまり、この方法は目的関数に直接適用されます。さらに、彼らはこの設定を合成関数、つまり滑らかな凸関数と（滑らかでない可能性のある）凸ブロック分離関数の和を最小化する問題に一般化しています。

${\displaystyle F(x)=f(x)+\Psi (x),}$

ここで、は変数/座標のブロックに分解されます。およびは（単純な）凸関数です。 ${\displaystyle \Psi (x)=\sum _{i=1}^{n}\Psi _{i}(x^{(i)}),}$ ${\displaystyle x\in R^{N}}$${\displaystyle n}$${\displaystyle x=(x^{(1)},\dots ,x^{(n)})}$${\displaystyle \Psi _{1},\dots ,\Psi _{n}}$

例 (ブロック分解):および の場合、および を選択できます。 ${\displaystyle x=(x_{1},x_{2},\dots ,x_{5})\in R^{5}}$${\displaystyle n=3}$${\displaystyle x^{(1)}=(x_{1},x_{3}),x^{(2)}=(x_{2},x_{5})}$${\displaystyle x^{(3)}=x_{4}}$

例 (ブロック分離可能な正則化子):

1. ${\displaystyle n=N;\Psi (x)=\|x\|_{1}=\sum _{i=1}^{n}|x_{i}|}$
2. ${\displaystyle N=N_{1}+N_{2}+\dots +N_{n};\Psi (x)=\sum _{i=1}^{n}\|x^{(i)}\|_{2}}$ここで、および は標準ユークリッドノルムです。${\displaystyle x^{(i)}\in R^{N_{i}}}$${\displaystyle \|\cdot \|_{2}}$

最適化問題を考える

${\displaystyle \min _{x\in R^{n}}f(x),}$

ここで は凸で滑らかな関数です。 ${\displaystyle f}$

滑らかさ:滑らかさとは、次のことを意味します。 の勾配は、定数で座標方向にリプシッツ連続であると仮定します。つまり、 ${\displaystyle f}$${\displaystyle L_{1},L_{2},\dots ,L_{n}}$

${\displaystyle |\nabla_{i}f(x+he_{i})-\nabla_{i}f(x)|\leq L_{i}|h|,}$

すべてのおよびに対して、 は変数 に関する偏微分を表します。 ${\displaystyle x\in R^{n}}$${\displaystyle h\in R}$${\displaystyle \nabla _{i}}$${\displaystyle x^{(i)}}$

Nesterov、Richtarik、Takac は、次のアルゴリズムが最適点に収束することを示しました。

アルゴリズムランダム座標降下法
    入力: //開始点${\displaystyle x_{0}\in R^{n}}$
    出力：${\displaystyle x}$
x  := x_0
    と設定する

     k  := 1, ...に対して、
        座標を一様にランダムに選択する${\displaystyle i\in \{1,2,\dots ,n\}}$
        更新終了${\displaystyle x^{(i)}=x^{(i)}-{\frac {1}{L_{i}}}\nabla _{i}f(x)}$ 
    

このアルゴリズムの反復はランダムベクトルなので、複雑度の結果は、この方法が高確率で近似解を出力するために必要な反復回数の上限を与えることになる。 ^[2]では、、が最適 解（）、 が信頼水準、が目標精度である場合、 となること が示された。 ${\displaystyle k\geq {\frac {2nR_{L}(x_{0})}{\epsilon }}\log \left({\frac {f(x_{0})-f^{*}}{\epsilon \rho }}\right)}$${\displaystyle R_{L}(x)=\max _{y}\max _{x^{*}\in X^{*}}\{\|y-x^{*}\|_{L}:f(y)\leq f(x)\}}$${\displaystyle f^{*}}$${\displaystyle f^{*}=\min _{x\in R^{n}}\{f(x)\}}$${\displaystyle \rho \in (0,1)}$${\displaystyle \epsilon >0}$${\displaystyle {\text{Prob}}(f(x_{k})-f^{*}>\epsilon )\leq \rho }$

次の図は、原理的に反復中にどのように発展するかを示しています。問題は ${\displaystyle x_{k}}$

${\displaystyle f(x)={\tfrac {1}{2}}x^{T}\left({\begin{array}{cc}1&0.5\\0.5&1\end{array}}\right)x-\left({\begin{array}{cc}1.5&1.5\end{array}}\right)x,\quad x_{0}=\left({\begin{array}{cc}0&0\end{array}}\right)^{T}}$

このアルゴリズムは、当然、座標だけでなく、座標ブロックにも拡張できます。空間があると仮定します。この空間には 5 つの座標方向があり、具体的に はランダム座標降下法が移動できる空間です。ただし、いくつかの座標方向をブロックにグループ化して、5 つの座標方向の代わりに 3 つのブロック座標方向を持つことができます (画像を参照)。 ${\displaystyle R^{5}}$${\displaystyle e_{1}=(1,0,0,0,0)^{T},e_{2}=(0,1,0,0,0)^{T},e_{3}=(0,0,1,0,0)^{T},e_{4}=(0,0,0,1,0)^{T},e_{5}=(0,0,0,0,1)^{T}}$

• 座標降下
• 勾配降下法
• 数学的最適化