5
$\begingroup$

I am perplexed by the fact that many sources online such as this website refer to mirror descent as a non-Euclidean gradient descent.

enter image description here

Why non-Euclidean?

  1. The constraint set $\mathcal{C} \subset \mathbb{R}^n$ is perfectly Euclidean.
  2. The vectors $x \in \mathbb{R}^n, g_k \in \mathbb{R}^n$ both live in the Euclidean space.
  3. $D_h(x,x_k)$ is not a Euclidean norm, in fact, not any norm, not any metric either, even if we refer to it as a "distance", it is a distance on what set/space? I would not refer to $D_h$ as a non-Euclidean distance, it is not a distance at all.

I expected that when talking about "non-Euclidean gradient descent", we meant that we will equip a subset of $\mathbb{R}^n$ with some non-Euclidean norm, such as $\|\cdot\|_1$, and performs minimization on that space. But it seems that we are still performing minimization on the Euclidean space. Even the inner product $\langle \cdot, \cdot\rangle$ is the standard "Euclidean" dot product, which induces the Euclidean norm. Why non-Euclidean?

Can someone please clarify as to what "non-Euclidean" mean in this context?

$\endgroup$
2
  • $\begingroup$ The first link while googling has the answer. See the passing from (3) to (4), and the line before the yellow box enclosing (4). $\endgroup$
    – user530511
    Commented Feb 12, 2018 at 2:14
  • $\begingroup$ @sunwarm Thanks, the key problem for me was "non-Euclidean" but in what sense? $\endgroup$
    – Olórin
    Commented Feb 12, 2018 at 2:33

1 Answer 1

7
$\begingroup$

One comment is that the projected gradient descent iteration can be expressed as $$ x_{k+1} = \arg \min_{x \in C} \quad f(x_k) + \langle \nabla f(x_k),x - x_k \rangle + \frac{1}{2t} \|x - x_k \|_2^2. $$ Omitting terms that don't depend on $x$, we have $$ x_{k+1} = \arg \min_{x \in C} \quad \langle \nabla f(x_k), x \rangle + \frac{1}{2t} \|x - x_k \|_2^2. $$ This looks quite like the Mirror descent iteration given, except that the Euclidean distance $\| x - x_k \|_2$ has been replaced by the "non-Euclidean distance" $D_h(x,x_k)$. You might object that $D_h$ is not a metric, which is a valid point -- I think they are just speaking loosely.

"One of the miseries of life is that everybody names things a little bit wrong, and so it makes everything a little harder to understand." -- Richard Feynman

$\endgroup$
2
  • 1
    $\begingroup$ Thanks for the authoritative answer. I think the naming is indeed confusing, especially when you constrast it against optimization on Riemannian manifolds such as optimization-online.org/DB_FILE/2015/04/4881.pdf . $\endgroup$
    – Olórin
    Commented Feb 12, 2018 at 2:28
  • $\begingroup$ @ElCamino I'm glad you pointed out that paper, it looks interesting. $\endgroup$
    – littleO
    Commented Feb 12, 2018 at 2:32

You must log in to answer this question.

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