Mirror descent

Mirror descent was originally proposed by Nemirovski and Yudin in 1983.[1]

In gradient descent applied to a differentiable function ${\displaystyle F}$, one starts with a guess ${\displaystyle \mathbf {x} _{0}}$ for a local minimum of ${\displaystyle F}$, and considers the sequence ${\displaystyle \mathbf {x} _{0},\mathbf {x} _{1},\mathbf {x} _{2},\ldots }$ such that

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

(assuming a constant learning rate)

We have a monotonic sequence

${\displaystyle F(\mathbf {x} _{0})\geq F(\mathbf {x} _{1})\geq F(\mathbf {x} _{2})\geq \cdots ,}$

so, hopefully, the sequence ${\displaystyle (\mathbf {x} _{n})}$ converges to the desired local minimum.

This can be reformulated by noting that

${\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\gamma }}\|\mathbf {x} -\mathbf {x} _{n}\|^{2}\right)}$

In other words, ${\displaystyle \mathbf {x} _{n+1}}$ minimizes the first-order approximation to ${\displaystyle F}$ at ${\displaystyle \mathbf {x} _{n}}$ with added proximity term ${\displaystyle \|\mathbf {x} -\mathbf {x} _{n}\|^{2}}$.

This Euclidean distance term is a particular example of a Bregman distance. Using other Bregman distances will yield other algorithms such as Hedge which may be more suited to optimization over particular geometries.

We are given convex function ${\displaystyle f}$ to optimize over convex set ${\displaystyle K\subset \mathbb {R} ^{n}}$, and given some norm ${\displaystyle \|\cdot \|}$ on ${\displaystyle \mathbb {R} ^{n}}$.

We are also given differentiable convex function ${\displaystyle h\colon \mathbb {R} ^{n}\to \mathbb {R} }$, ${\displaystyle \alpha }$-strongly convex with respect to the given norm. This is called the distance-generating function, and its gradient ${\displaystyle \nabla h\colon \mathbb {R} ^{n}\to \mathbb {R} ^{n}}$ is known as the mirror map.

Starting from initial ${\displaystyle x_{0}\in K}$, in each iteration of Mirror Descent:

• Map to the dual space: ${\displaystyle \theta _{t}\leftarrow \nabla h(x_{t})}$
• Update in the dual space using a gradient step: ${\displaystyle \theta _{t+1}\leftarrow \theta _{t}-\eta _{t}\nabla f_{t}(x_{t})}$
• Map back to the primal space: ${\displaystyle x'_{t+1}\leftarrow (\nabla h)^{-1}(\theta _{t+1})}$
• Project back to the feasible region ${\displaystyle K}$: ${\displaystyle x_{t+1}\leftarrow \min _{x\in K}D_{h}(x||x'_{t+1})}$, where ${\displaystyle D_{h}}$ is the Bregman divergence

Mirror descent in the online optimization setting is known as Online Mirror Descent (OMD).[2]

• Gradient descent
• Multiplicative weight update method
• Hedge algorithm
• Bregman divergence