鏡像降下法

鏡像降下法（きょうぞうこうかほう、英: mirror descent）とは、数理最適化において微分可能関数の極値を求める反復法の一種。

鏡像降下法は最急降下法や乗算型重み更新法を一般化したアルゴリズムである。

歴史

鏡像降下法は1983年にアルカディ・ネミロフスキ、ユーディンによって初めて提案された。

動機

最急降下法において学習率の列 $(\eta _{n})_{n\geq 0}$ を微分可能関数 $F$ に適用する。関数 $F$ の極小値を求めるために初期点 $\mathbf {x} _{0}$ から開始し、点列 $\mathbf {x} _{0},\mathbf {x} _{1},\mathbf {x} _{2},\ldots$ を求めていく:

$\mathbf {x} _{n+1}=\mathbf {x} _{n}-\eta _{n}\nabla F(\mathbf {x} _{n}),\ n\geq 0.$

これを以下のように書き換える:

$\mathbf {x} _{n+1}=\arg \min _{\mathbf {x} }\left(F(\mathbf {x} _{n})+\nabla F(\mathbf {x} _{n})^{T}(\mathbf {x} -\mathbf {x} _{n})+{\frac {1}{2\eta _{n}}}\|\mathbf {x} -\mathbf {x} _{n}\|^{2}\right)$

言い換えると、$\mathbf {x} _{n+1}$ は関数 $F$ の点 $\mathbf {x} _{n}$ における一次式に近似の項 $\|\mathbf {x} -\mathbf {x} _{n}\|^{2}$ を追加した関数を最小化する。

この二乗ユークリッド距離はブレグマン距離の特別な例である。別のブレグマン距離を使用すると特定の幾何上で最適化するのに適した Hedgeアルゴリズムなどのアルゴリズムを導くことができる。

定式化

凸集合 $K\subset \mathbb {R} ^{n}$ 上で凸関数 $f$ を最適化することを考える。そして $\mathbb {R} ^{n}$ でいくつかのノルム $\|\cdot \|$ が与えられているとする。

また、各ノルムには$\alpha$-強凸関数の微分可能凸関数 $h\colon \mathbb {R} ^{n}\to \mathbb {R}$ が与えられる。これは距離生成関数（distance-generating function）と呼ばれ、その勾配 $\nabla h\colon \mathbb {R} ^{n}\to \mathbb {R} ^{n}$ は鏡像写像（mirror map）として知られている。

初期点 $x_{0}\in K$ から始め、各反復における鏡像降下法の手続きは:

• 双対空間への写像: $\theta _{t}\leftarrow \nabla h(x_{t})$
• 勾配ステップにおいて双対空間を更新する: $\theta _{t+1}\leftarrow \theta _{t}-\eta _{t}\nabla f(x_{t})$
• 主空間に写像: $x'_{t+1}\leftarrow (\nabla h)^{-1}(\theta _{t+1})$
• 実行可能空間 $K$ に射影: $x_{t+1}\leftarrow \mathrm {arg} \min _{x\in K}D_{h}(x||x'_{t+1})$、ただし、$D_{h}$ はブレグマンダイバージェンスである。

拡張

オンライン最適化における鏡像降下法はオンライン鏡像降下法（英: Online Mirror Descent: OMD）として知られている。

関連項目

• 最急降下法
• 乗算型重み更新法
• ブレグマンダイバージェンス