Mirror descent explained

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

( η _{n)} _{n} applied to a differentiable function F , one starts with a guess x _{0} for a local minimum of F, and considers the sequence x _{0,} x _{1,} x _{2,} \ldots such thatx _{n+1} = x _{n-η} _{n} \nabla F( x _{n), n} \ge 0 .

This can be reformulated by noting that

x _{n+1} = \arg min _{x} \left(F( x _{n)} + \nabla F( x ^{T} _{n)} ( x - x _{n)} + (1)/(2η _{n}) \| x - x ^{2 \right)} _{n\|}

In other words,

x _{n+1} minimizes the first-order approximation to F at x _{n} with added proximity term \| x - x ^{2} _{n\|} .

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

f to optimize over a convex set K \subset R ^{n} , and given some norm \| ⋅ \| on R ^{n} .

We are also given differentiable convex function

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

Starting from initial

x _{0} \in K , in each iteration of Mirror Descent:

• Map to the dual space:

\theta _{t} \leftarrow \nabla h (x _{t)}

• Update in the dual space using a gradient step:

\theta _{t+1} \leftarrow \theta _{t} - η _{t} \nabla f(x _{t)}

• Map back to the primal space:

x' _{t+1} \leftarrow (\nabla h) ^{-1} (\theta _{t+1} )

• Project back to the feasible region

K : x _{t+1} \leftarrow arg min _{x} D _{h(x||x'} _{t+1} ) , where 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

Notes and References

1. Arkadi Nemirovsky and David Yudin. Problem Complexity and Method Efficiency in Optimization. John Wiley & Sons, 1983
2. Nemirovski, Arkadi (2012) Tutorial: mirror descent algorithms for large-scale deterministic and stochastic convex optimization.https://www2.isye.gatech.edu/~nemirovs/COLT2012Tut.pdf
3. Web site: Mirror descent algorithm . 2022-07-10 . tlienart.github.io.
4. Fang. Huang. Harvey. Nicholas J. A.. Portella. Victor S.. Friedlander. Michael P.. 2021-09-03. Online mirror descent and dual averaging: keeping pace in the dynamic case. cs.LG. 2006.02585.