Mirror descent

Beck and Teboulle (2003):

The mirror descent algorithm (MDA) was introduced by Nemirovsky and Yudin for solving convex optimization problems. This method exhibits an efficiency estimate that is mildly dependent on the decision variables dimension, and thus suitable for solving very large-scale optimization problems. We present a new derivation and analysis of this algorithm. We show that the MDA can be viewed as a nonlinear projected-subgradient type method, derived from using a general distance-like function instead of the usual Euclidean squared distance. Within this interpretation, we derive in a simple way convergence and efficiency estimates. We then propose an Entropic mirror descent algorithm for convex minimization over the unit simplex, with a global efficiency estimate proven to be mildly dependent on the dimension of the problem.

Bubeck’s lectures are good: Bubeck (2019).

Mirror Descent generalizes gradient descent to settings where the feasible set $X\subset {\mathbb{R}}^r$ is not naturally Euclidean. It relies on:

1. A mirror map $\mathrm{\Phi }:C\to \mathbb{R}$, a strictly convex, differentiable function whose gradient $\mathrm{\nabla }\mathrm{\Phi }$ maps the primal space $X$ into the dual space ${\mathbb{R}}^r$.

2. The associated Bregman divergence

   $$D_{\mathrm{\Phi }}(p,q)=\mathrm{\Phi }(p)-\mathrm{\Phi }(q)-⟨\mathrm{\nabla }\mathrm{\Phi }(q),p-q⟩.$$

Starting from $x_0\in X$, each iteration does

$$\mathrm{\nabla }\mathrm{\Phi }(y_{k+1})=\mathrm{\nabla }\mathrm{\Phi }(x_k)-\eta g_k,x_{k+1}=\arg \underset{x\in X}{min}{D}_{\mathrm{\Phi }}(x,y_{k+1}),$$

where $g_k\in \partial f(x_k)$ . So that’s two steps, really, interleaved, a gradient descent in the dual space and then a projection in the primal space. Equivalently,

$$x_{k+1}=\arg \underset{x\in X}{min}⟨\eta g_k,x⟩+D_{\mathrm{\Phi }}(x,x_k).$$

As to why we’d bother: many reasons.

1. Mirror descend corresponds to what we want to do anyway, in situation where we have two natural representations of an estimand. So it’s easy.
2. It is theoretically very tractable, so it’s easy to prove stuff about it
3. It is fast, in that you can provably require few iterations to get very close to the optimum, and it’s a first order method (kinda) so you might hope that these iterations will be tractable.
4. It easily generalises to online/SGD settings where we observe data sequentially

Rarely is the obvious thing the best thing, in practical mathematics. AFAICT Mirror descent is a nearly obvious thing that is nearly the best.