ミラー降下

数学において、ミラー降下法は微分可能関数の局所的最小値を見つけるための反復的な 最適化 アルゴリズムです。

勾配降下法や乗法重みなどのアルゴリズムを一般化します。

ミラー降下法は、 1983年にネミロフスキーとユディンによって最初に提案されました^。[1]

微分可能関数に学習率の列を適用した勾配降下法では、の局所的最小値の推測から始めて、次のような 列を考える。${\displaystyle (\eta _{n})_{n\geq 0}}$${\displaystyle F}$${\displaystyle \mathbf {x} _{0}}$${\displaystyle F,}$${\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)}$

言い換えると、近接項 を追加することで、での1 次近似を に最小化します。 ${\displaystyle \mathbf {x} _{n+1}}$${\displaystyle F}$${\displaystyle \mathbf {x} _{n}}$${\displaystyle \|\mathbf {x} -\mathbf {x} _{n}\|^{2}}$

この二乗ユークリッド距離項はブレグマン距離の特別な例です。他のブレグマン距離を使用すると、特定の形状での最適化により適したヘッジなどの他のアルゴリズムが生成されます。 ^{[2] [3]}

凸集合 上で最適化する凸関数と、上の何らかのノルムが与えられます。 ${\displaystyle f}$${\displaystyle K\subset \mathbb {R} ^{n}}$${\displaystyle \|\cdot \|}$${\displaystyle \mathbb {R} ^{n}}$

また、微分可能な凸関数 も与えられます。これは、与えられたノルムに関して強凸です。これは距離生成関数と呼ばれ、その勾配はミラー マップとして知られています。 ${\displaystyle h\colon \mathbb {R} ^{n}\to \mathbb {R} }$${\displaystyle \alpha}$ ${\displaystyle \nabla h\colon \mathbb {R} ^{n}\to \mathbb {R} ^{n}}$

初期 から始めて、Mirror Descent の各反復で次のようになります。 ${\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})}$
• 実行可能領域 に投影し直します。ここで、Bregman ダイバージェンスとなります。${\displaystyle K}$${\displaystyle x_{t+1}\leftarrow \mathrm {arg} \min _{x\in K}D_{h}(x||x'_{t+1})}$${\displaystyle D_{h}}$

オンライン最適化設定におけるミラー降下法は、オンラインミラー降下法（OMD）として知られています。^[4]

• 勾配降下法
• 乗法重み更新法
• ヘッジアルゴリズム
• ブレグマンダイバージェンス