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

[edit]

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

Motivation

[edit]

In gradient descent with the sequence of learning rates applied to a differentiable function , one starts with a guess for a local minimum of and considers the sequence such that

This can be reformulated by noting that

In other words, minimizes the first-order approximation to at with added proximity term .

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

[edit]

We are given convex function to optimize over a convex set , and given some norm on .

We are also given differentiable convex function , -strongly convex with respect to the given norm. This is called the distance-generating function, and its gradient is known as the mirror map.

Starting from initial , in each iteration of Mirror Descent:

  • Map to the dual space:
  • Update in the dual space using a gradient step:
  • Map back to the primal space:
  • Project back to the feasible region : , where is the Bregman divergence.

Extensions

[edit]

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

See also

[edit]

References

[edit]
  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. ^ "Mirror descent algorithm". tlienart.github.io. Retrieved 2022-07-10.
  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". arXiv:2006.02585 [cs.LG].