6
$\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$
7
$\begingroup$

The advantage over using mirror descent of gradient descent is that it takes into account the geometry of the problem. We can see it 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 MDA using the potential $\Phi = \|\cdot\|^2/2$.

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. 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 MDA 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 convergence rates.

To answer 3), we map our primal point $x$ to the dual space and take a step in the gradient direction, then we map back to the primal space 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$
  • $\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 '18 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$ – TSF Mar 21 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$ – Lorenzo Najt Dec 4 at 19:42
  • $\begingroup$ @LorenzoNajt Optimal Transport involving the space of Radon measures $\endgroup$ – TSF Dec 5 at 7:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.