# Why is the mirror descent considered a "non-Euclidean" algorithm?

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

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?

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

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.