17
$\begingroup$

I am trying to wrap my head around why mirror descent is such a popular optimization algorithm. Based on my reading, it seems like the main reason is that it improves upon the convergence rate of subgradient descent, while only using full gradient information of a strongly convex function $\psi$ (acting as a term in a Bregman divergence).

Additionally, there seems to be hints that based on the choice of $\psi$, you might also have decomposition advantages.

So my questions are:

1) If the full gradient information of the objective function is used, does mirror descent have any convergence advantage over gradient descent?

2) What is an example where using $\psi \neq \|\cdot\|_2^2$ is advantageous?

3) What exactly is the connection of mirror descent with duality, e.g. what interpretation motivates this method?

Thank you!

$\endgroup$
1

1 Answer 1

17
$\begingroup$

The advantage of using mirror descent over gradient descent is that it takes into account the geometry of the problem through the potential function $\Phi$.

We can see mirror descent as a generalization of the projected gradient descent, which ordinarily is based on an assumed euclidean geometry. Projected gradient descent is a special case of mirror descent using the potential $\Phi = \|\cdot\|^2/2$. But sometimes there are other choices of $\Phi$ that can better model the geometry of our problem. Examples include $x\log x$ or $-\log x$, both of which are useful for problems over the positive orthant, simplex, etc.

To answer 1), it depends on the geometry of the problem. In high dimensions (large scale optimization), it can be advantageous to abandon the euclidean geometry to improve the constants in our convergence rates. As an example, consider the differentiable convex function $f$ on the Euclidean ball $B_{2,n}$ with $\|\nabla f(x)\|_{\infty}\leq 1$ for all $x\in B_{2,n}$. Then, $|\nabla f(x)|_2\leq \sqrt{n}$ and the projected gradient descent converges at a rate of $\sqrt{\frac{n}{k}}$. However, using mirror descent with an appropraitely chosen $\Phi$ we can get a rate of $\sqrt{\frac{\log(n)}{k}}$. When $n$ is quite large, this is a huge improvement. The key step is that our choice of $\Phi$ (potential) determines the new geometry.

To answer 2), many times when considering probability distributions the euclidean distance is lackluster and we prefer to use the so called Kullback Liebler divergence to measure the 'distance' between two probability distributions. In such scenarios, mirror descent with $\Phi$ set to be the entropy provides better constants in our convergence rates.

To answer 3), we map our primal point $x$ to the dual space (through the mapping $\nabla \Phi$) and take a step in the direction given by the gradient of our function, then we map back to the primal space (through $\nabla\Phi^{-1}$) after that step. For spaces which are reflexive (i.e. $X^{**} = X$) this is not a big deal, for example in Hilbert spaces we do not worry so much since the norm arises naturally from an inner product and our space is isomorphic to its dual already. However, in a more general context (any banach space), we have to be careful about handling this duality.

I know this is a vague answer that doesn't quite answer your questions, but I hope it helps you find the right way.

$\endgroup$
4
  • $\begingroup$ Thanks for this well thought out answer! I was not familiar with the convergence result so that is a very concrete plus. As far as the other distances, since they are all solving the same original problem, i guess it must be either a) for per iteration complexity reduction or b) a faster overall convergence rate. i think i need to play around more with real examples to get an idea of why other geometries would be preferred. $\endgroup$
    – Y. S.
    Feb 27, 2018 at 18:36
  • 1
    $\begingroup$ After learning more about this topic I would like to say that another useful aspect of mirror descent is that in works in more general spaces than, say, gradient descent. If we are in a non reflexive Banach space then we cannot necessarily write something like $x_{k+1} = x_k - \gamma_k \nabla f(x_k)$ because $x_k$ and $\nabla f(x_k)$ can live in different vector spaces. Mirror Descent aids this in some sense by mapping everything to the dual and then taking the step, mapping back to the primal space afterwards. $\endgroup$ Mar 21, 2019 at 17:25
  • $\begingroup$ @TSF Did you find a situation where there were interesting consequences to doing Mirror descent in a non-reflexive Banach space, or is it just a (useful) conceptual difference? $\endgroup$
    – Elle Najt
    Dec 4, 2019 at 19:42
  • $\begingroup$ @LorenzoNajt home.ttic.edu/~karthik/cvxgames_colt2010.pdf Convex games in Banach spaces $\endgroup$ May 9, 2021 at 3:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .