出典: フリー百科事典『ウィキペディア（Wikipedia）』
鏡像降下法 （きょうぞうこうかほう、英 : mirror descent ）とは、数理最適化 において微分可能関数 の極値 を求める反復法 の一種。
鏡像降下法は最急降下法 や乗算型重み更新法 （英語版 ） アルゴリズム である。
鏡像降下法は1983年にアルカディ・ネミロフスキ （英語版 ） [ 1]
最急降下法 において学習率の列
(
η
n
)
n
≥
0
{\displaystyle (\eta _{n})_{n\geq 0}}
F
{\displaystyle F}
F
{\displaystyle F}
x
0
{\displaystyle \mathbf {x} _{0}}
x
0
,
x
1
,
x
2
,
…
{\displaystyle \mathbf {x} _{0},\mathbf {x} _{1},\mathbf {x} _{2},\ldots }
x
n
+
1
=
x
n
−
η
n
∇
F
(
x
n
)
,
n
≥
0.
{\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\eta _{n}\nabla F(\mathbf {x} _{n}),\ n\geq 0.}
これを以下のように書き換える:
x
n
+
1
=
arg
min
x
(
F
(
x
n
)
+
∇
F
(
x
n
)
T
(
x
−
x
n
)
+
1
2
η
n
‖
x
−
x
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)}
言い換えると、
x
n
+
1
{\displaystyle \mathbf {x} _{n+1}}
F
{\displaystyle F}
x
n
{\displaystyle \mathbf {x} _{n}}
‖
x
−
x
n
‖
2
{\displaystyle \|\mathbf {x} -\mathbf {x} _{n}\|^{2}}
この二乗ユークリッド距離はブレグマン距離 （英語版 ） [ 2] [ 3]
凸集合
K
⊂
R
n
{\displaystyle K\subset \mathbb {R} ^{n}}
f
{\displaystyle f}
R
n
{\displaystyle \mathbb {R} ^{n}}
‖
⋅
‖
{\displaystyle \|\cdot \|}
また、各ノルムには
α
{\displaystyle \alpha }
h
:
R
n
→
R
{\displaystyle h\colon \mathbb {R} ^{n}\to \mathbb {R} }
勾配
∇
h
:
R
n
→
R
n
{\displaystyle \nabla h\colon \mathbb {R} ^{n}\to \mathbb {R} ^{n}}
初期点
x
0
∈
K
{\displaystyle x_{0}\in K}
双対空間への写像:
θ
t
←
∇
h
(
x
t
)
{\displaystyle \theta _{t}\leftarrow \nabla h(x_{t})}
勾配ステップにおいて双対空間を更新する:
θ
t
+
1
←
θ
t
−
η
t
∇
f
(
x
t
)
{\displaystyle \theta _{t+1}\leftarrow \theta _{t}-\eta _{t}\nabla f(x_{t})}
主空間に写像:
x
t
+
1
′
←
(
∇
h
)
−
1
(
θ
t
+
1
)
{\displaystyle x'_{t+1}\leftarrow (\nabla h)^{-1}(\theta _{t+1})}
実行可能空間
K
{\displaystyle K}
x
t
+
1
←
a
r
g
min
x
∈
K
D
h
(
x
|
|
x
t
+
1
′
)
{\displaystyle x_{t+1}\leftarrow \mathrm {arg} \min _{x\in K}D_{h}(x||x'_{t+1})}
D
h
{\displaystyle D_{h}}
ブレグマンダイバージェンス （英語版 ） オンライン最適化 （英語版 ） 英 : Online Mirror Descent : OMD）として知られている[ 4]
^ Arkadi Nemirovsky and David Yudin. Problem Complexity and Method Efficiency in Optimization. John Wiley & Sons, 1983
^ Nemirovski, Arkadi (2012) Tutorial: mirror descent algorithms for large-scale deterministic and stochastic convex optimization.https://www2.isye.gatech.edu/~nemirovs/COLT2012Tut.pdf
^ “Mirror descent algorithm ”. tlienart.github.io . 2022年7月10日閲覧。 ^ Fang, Huang; Harvey, Nicholas J. A.; Portella, Victor S.; Friedlander, Michael P. (3 September 2021). "Online mirror descent and dual averaging: keeping pace in the dynamic case". arXiv :2006.02585 cs.LG ]。
