Mirror descent

Mirror descent was originally proposed by Nemirovski and Yudin in 1983.Arkadi Nemirovsky and David Yudin. Problem Complexity and Method Efficiency in Optimization. John Wiley & Sons, 1983

In gradient descent with the sequence of learning rates $(\backslash eta\_n)\_\{n\; \backslash geq\; 0\}$ applied to a differentiable function $F$, one starts with a guess $\backslash mathbf\{x\}\_0$ for a local minimum of $F,$ and considers the sequence $\backslash mathbf\{x\}\_0,\; \backslash mathbf\{x\}\_1,\; \backslash mathbf\{x\}\_2,\; \backslash ldots$ such that

:$\backslash mathbf\{x\}\_\{n+1\}=\backslash mathbf\{x\}\_n-\backslash eta\_n\; \backslash nabla\; F(\backslash mathbf\{x\}\_n),\backslash \; n\; \backslash ge\; 0.$

This can be reformulated by noting that

:$\backslash mathbf\{x\}\_\{n+1\}=\backslash arg\; \backslash min\_\{\backslash mathbf\{x\}\}\; \backslash left(F(\backslash mathbf\{x\}\_n)\; +\; \backslash nabla\; F(\backslash mathbf\{x\}\_n)^T\; (\backslash mathbf\{x\}\; -\; \backslash mathbf\{x\}\_n)\; +\; \backslash frac\{1\}\{2\; \backslash eta\_n\}\backslash |\backslash mathbf\{x\}\; -\; \backslash mathbf\{x\}\_n\backslash |^2\backslash right)$

In other words, $\backslash mathbf\{x\}\_\{n+1\}$ minimizes the first-order approximation to $F$ at $\backslash mathbf\{x\}\_n$ with added proximity term $\backslash |\backslash mathbf\{x\}\; -\; \backslash mathbf\{x\}\_n\backslash |^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.Nemirovski, Arkadi (2012) Tutorial: mirror descent algorithms for large-scale deterministic and stochastic convex optimization.https://www2.isye.gatech.edu/~nemirovs/COLT2012Tut.pdf{{Cite web |title=Mirror descent algorithm |url=https://tlienart.github.io/posts/2018/10/27-mirror-descent-algorithm/ |access-date=2022-07-10 |website=tlienart.github.io}}

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

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

Starting from initial $x\_0\; \backslash in\; K$, in each iteration of Mirror Descent:

• Map to the dual space: $\backslash theta\_t\; \backslash leftarrow\; \backslash nabla\; h\; (x\_t)$
• Update in the dual space using a gradient step: $\backslash theta\_\{t+1\}\; \backslash leftarrow\; \backslash theta\_t\; -\; \backslash eta\_t\; \backslash nabla\; f(x\_t)$
• Map back to the primal space: $x\text{'}\_\{t+1\}\; \backslash leftarrow\; (\backslash nabla\; h)^\{-1\}(\backslash theta\_\{t+1\})$
• Project back to the feasible region $K$: $x\_\{t+1\}\; \backslash leftarrow\; \backslash mathrm\{arg\}\backslash min\_\{x\; \backslash in\; K\}D\_h(x||x\text{'}\_\{t+1\})$, where $D\_h$ is the Bregman divergence.

Mirror descent in the online optimization setting is known as Online Mirror Descent (OMD).{{cite arXiv|last1=Fang|first1=Huang|last2=Harvey|first2=Nicholas J. A.|last3=Portella|first3=Victor S.|last4=Friedlander|first4=Michael P.|date=2021-09-03|title=Online mirror descent and dual averaging: keeping pace in the dynamic case|class=cs.LG|eprint=2006.02585}}

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

{{reflist}}

{{Optimization algorithms|unconstrained}}

Category:Mathematical optimization

Category:Optimization algorithms and methods

Category:Gradient methods