数学における概念
数学において、 ミラー降下法は 微分可能な関数 の 局所的最小値 を見つけるための 反復的な 最適化 アルゴリズム です 。
勾配降下法 や 乗法重み などのアルゴリズムを一般化します 。
歴史 ミラー降下法は、 1983年に ネミロフスキー とユディンによって最初に提案されました 。[1]
モチベーション 微分可能関数に 学習率の列を適用した 勾配降下法 では、 の局所的最小値の 推測から始めて、 次のような 列を考える。 （ η n ） n ≥ 0 {\displaystyle (\eta _{n})_{n\geq 0}} F {\displaystyle F} × 0 {\displaystyle \mathbf {x} _{0}} F 、 {\displaystyle F,} × 0 、 × 1 、 × 2 、 … {\displaystyle \mathbf {x} _{0},\mathbf {x} _{1},\mathbf {x} _{2},\ldots }
× n + 1 ＝ × n − η n ∇ F （ × n ） 、 n ≥ 0。 {\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\eta _{n}\nabla F(\mathbf {x} _{n}),\ n\geq 0.} これを次のように言い換えることができる。
× n + 1 ＝ 引数 分 × （ F （ × n ） + ∇ F （ × n ） T （ × − × n ） + 1 2 η n ‖ × − × n ‖ 2 ） {\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 次近似を で 最小 化します 。 × n + 1 {\displaystyle \mathbf {x} _{n+1}} F {\displaystyle F} × n {\displaystyle \mathbf {x} _{n}} ‖ × − × n ‖ 2 {\displaystyle \|\mathbf {x} -\mathbf {x} _{n}\|^{2}}
この二乗ユークリッド距離項は、 ブレグマン距離の具体的な例です。他のブレグマン距離を用いると、 ヘッジ法 などの他のアルゴリズムが得られ 、特定の形状における最適化により適している可能性があります。 [2] [3]
凸集合 上で最適化する 凸関数と、 上の ノルムが与えられます 。 f {\displaystyle f} K ⊂ R n {\displaystyle K\subset \mathbb {R} ^{n}} ‖ ⋅ ‖ {\displaystyle \|\cdot \|} R n {\displaystyle \mathbb {R} ^{n}}
また、微分可能な凸関数 も与えられます 。 これ は与えられたノルムに関して 強凸です。これは 距離生成関数 と呼ばれ、その 勾配は ミラー写像 として知られています 。 h : R n → R {\displaystyle h\colon \mathbb {R} ^{n}\to \mathbb {R} } α {\displaystyle \alpha} ∇ h : R n → R n {\displaystyle \nabla h\colon \mathbb {R} ^{n}\to \mathbb {R} ^{n}}
初期 から始めて 、ミラー降下の各反復で次のようになります。 × 0 ∈ K {\displaystyle x_{0}\in K}
双対空間へのマップ: θ t ← ∇ h （ × t ） {\displaystyle \theta _{t}\leftarrow \nabla h(x_{t})} 勾配ステップを使用してデュアル空間で更新します。 θ t + 1 ← θ t − η t ∇ f （ × t ） {\displaystyle \theta _{t+1}\leftarrow \theta _{t}-\eta _{t}\nabla f(x_{t})} 原始空間にマップし直す: × t + 1 ′ ← （ ∇ h ） − 1 （ θ t + 1 ） {\displaystyle x'_{t+1}\leftarrow (\nabla h)^{-1}(\theta _{t+1})} 実行可能領域 に投影し直します 。 ここで、 Bregman ダイバージェンス は です 。 K {\displaystyle K} × t + 1 ← 1つの r グラム 分 × ∈ K D h （ × | | × t + 1 ′ ） {\displaystyle x_{t+1}\leftarrow \mathrm {arg} \min _{x\in K}D_{h}(x||x'_{t+1})} D h {\displaystyle D_{h}}
他のメソッドや拡張機能との接続 ミラー降下法は情報幾何学における自然勾配やリーマン勾配降下法と関連している。 [4]
オンライン最適化 設定におけるミラー降下法は 、オンラインミラー降下法（OMD）として知られています。 [5]
参照
参考文献 ^ アルカディ・ネミロフスキー、デイヴィッド・ユディン著『最適化における問題の複雑性と手法の効率性』ジョン・ワイリー・アンド・サンズ、1983年 ^ Nemirovski, Arkadi (2012) チュートリアル: 大規模な決定論的および確率的凸最適化のためのミラー降下アルゴリズム。https://www2.isye.gatech.edu/~nemirovs/COLT2012Tut.pdf ^ 「ミラー降下アルゴリズム」. tlienart.github.io . 2022年7月10日 閲覧 。 ^ ニールセン、フランク、「自然勾配とリーマン勾配、鏡面降下法、そして通常の勾配との関連についての注釈」 （PDF） 、 ブログ 。 ^ Fang, Huang; Harvey, Nicholas JA; Portella, Victor S.; Friedlander, Michael P. (2021-09-03). 「オンラインミラー降下法と双対平均化：動的ケースにおけるペース維持」 arXiv : 2006.02585 [cs.LG].
最適化では最大値と最小値を計算します。
