鏡像降下法

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

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

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

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

${\displaystyle \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)}$

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

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

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

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

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

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

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