Mirror descent

In mathematics, mirror descent is an iterative optimization algorithm for finding a local minimum of a differentiable function.

It generalizes algorithms such as gradient descent and multiplicative weights.

History

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

Motivation

In gradient descent with the sequence of learning rates ${\displaystyle (\eta _{n})_{n\geq 0}}$ 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}-\eta _{n}\nabla F(\mathbf {x} _{n}),\ n\geq 0.}$

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\eta _{n}}}\|\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 squared 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.^[2][3]

Formulation

We are given convex function ${\displaystyle f}$ to optimize over a 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(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 \mathrm {arg} \min _{x\in K}D_{h}(x||x'_{t+1})}$, where ${\displaystyle D_{h}}$ is the Bregman divergence.

Extensions

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

See also

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