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

References

• v
• t
• e

Optimization: Algorithms, methods, and heuristics

Unconstrained nonlinear

Functions Golden-section search Interpolation methods Line search Nelder–Mead method Successive parabolic interpolation Gradients Convergence Trust region Wolfe conditions Quasi–Newton Berndt–Hall–Hall–Hausman Broyden–Fletcher–Goldfarb–Shanno and L-BFGS Davidon–Fletcher–Powell Symmetric rank-one (SR1) Other methods Conjugate gradient Gauss–Newton Gradient Mirror Levenberg–Marquardt Powell's dog leg method Truncated Newton Hessians Newton's method

Constrained nonlinear
General Barrier methods Penalty methods Differentiable Augmented Lagrangian methods Sequential quadratic programming Successive linear programming

Convex optimization
Convex minimization Cutting-plane method Reduced gradient (Frank–Wolfe) Subgradient method Linear and quadratic Interior point Affine scaling Ellipsoid algorithm of Khachiyan Projective algorithm of Karmarkar Basis-exchange Simplex algorithm of Dantzig Revised simplex algorithm Criss-cross algorithm Principal pivoting algorithm of Lemke

Combinatorial
Paradigms Approximation algorithm Dynamic programming Greedy algorithm Integer programming Branch and bound/cut Graph algorithms Minimum spanning tree Borůvka Prim Kruskal Shortest path Bellman–Ford SPFA Dijkstra Floyd–Warshall Network flows Dinic Edmonds–Karp Ford–Fulkerson Push–relabel maximum flow

Metaheuristics
Evolutionary algorithm Hill climbing Local search Parallel metaheuristics Simulated annealing Spiral optimization algorithm Tabu search

• Software