鏡像降下法のソースを表示

'''鏡像降下法'''（きょうぞうこうかほう、{{Lang-en-short|mirror descent}}）とは、[[数理最適化]]において[[微分可能関数]]の[[極値]]を求める[[反復法]]の一種。

鏡像降下法は[[最急降下法]]や{{仮リンク|乗算型重み更新法|en|Multiplicative weight update method}}を一般化した[[アルゴリズム]]である。

== 歴史 ==
鏡像降下法は1983年に{{仮リンク|アルカディ・ネミロフスキ|en|Arkadi Nemirovsky}}、ユーディンによって初めて提案された<ref>Arkadi Nemirovsky and David Yudin. Problem Complexity and Method Efficiency in Optimization. John Wiley & Sons, 1983</ref>。

== 動機 ==
[[最急降下法]]において学習率の列 <math>(\eta_n)_{n \geq 0}</math> を微分可能関数 <math>F</math> に適用する。関数 <math>F</math> の極小値を求めるために初期点 <math>\mathbf{x}_0</math> から開始し、点列 <math>\mathbf{x}_0, \mathbf{x}_1, \mathbf{x}_2, \ldots</math> を求めていく:

:<math>\mathbf{x}_{n+1}=\mathbf{x}_n-\eta_n \nabla F(\mathbf{x}_n),\ n \ge 0.</math>

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

:<math>\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)</math>

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

この二乗ユークリッド距離は{{仮リンク|ブレグマンダイバージェンス|en|Bregman divergence|label=ブレグマン距離}}の特別な例である。別のブレグマン距離を使用すると特定の幾何上で最適化するのに適した Hedgeアルゴリズムなどのアルゴリズムを導くことができる<ref>Nemirovski, Arkadi (2012) Tutorial: mirror descent algorithms for large-scale deterministic and stochastic convex optimization.https://www2.isye.gatech.edu/~nemirovs/COLT2012Tut.pdf</ref><ref>{{Cite web |title=Mirror descent algorithm |url=https://tlienart.github.io/posts/2018/10/27-mirror-descent-algorithm/ |access-date=2022-07-10 |website=tlienart.github.io }}</ref>。

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

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

初期点 <math>x_0 \in K</math> から始め、各反復における鏡像降下法の手続きは:

* 双対空間への写像: <math>\theta_t \leftarrow \nabla h (x_t)</math>
* 勾配ステップにおいて双対空間を更新する: <math>\theta_{t+1} \leftarrow \theta_t - \eta_t \nabla f(x_t)</math>
* 主空間に写像: <math>x'_{t+1} \leftarrow (\nabla h)^{-1}(\theta_{t+1})</math>
* 実行可能空間 <math>K</math> に射影: <math>x_{t+1} \leftarrow \mathrm{arg}\min_{x \in K}D_h(x||x'_{t+1})</math>、ただし、<math>D_h</math> は{{仮リンク|ブレグマンダイバージェンス|en|Bregman divergence}}である。

== 拡張 ==
{{仮リンク|オンライン最適化|en|Online optimization}}における鏡像降下法はオンライン鏡像降下法（{{Lang-en-short|Online Mirror Descent}}: OMD）として知られている<ref>{{cite arXiv |last1=Fang |first1=Huang |last2=Harvey |first2=Nicholas J. A. |last3=Portella |first3=Victor S. |last4=Friedlander |first4=Michael P.|date=2021-09-03 |title=Online mirror descent and dual averaging: keeping pace in the dynamic case |class=cs.LG |eprint=2006.02585 }}</ref>。

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 関連項目 ==
* [[最急降下法]]
* {{仮リンク|乗算型重み更新法|en|Multiplicative weight update method}}
* {{仮リンク|ブレグマンダイバージェンス|en|Bregman divergence}}

{{最適化アルゴリズム}}

{{DEFAULTSORT:きようそうこうかほう}}
[[Category:最適化アルゴリズムとメソッド]]
[[Category:勾配法]]
[[Category:数学に関する記事]]