Non Euclidean Gradient Descent Let the Euclidean space $\mathbb{R}^n$ is equipped with an arbitrary inner product $\langle\cdot,\cdot\rangle$ and its corresponding norm $\|\cdot\|$, not necessarily $l_2$. Let $f:\mathbb{R}^n\rightarrow \mathbb{R}$ be a convex and differentiable function with is smooth, i.e there exists a constant $L>0$ such that $\| \nabla f(x) - \nabla f(y)\| \leq L\| x - y\|$, for all $x,y\in \mathbb{R}^n$. Let us define the following quantities
$$\tilde{x} = \arg\min_{y \in \mathbb{R}^n} \left\lbrace \frac{L}{2}\| y-x\|^2 + \langle\nabla f(x), y-x \rangle \right\rbrace$$
$$\mbox{Prog}(x) = \min_{y \in \mathbb{R}^n} \left\lbrace \frac{L}{2}\| y-x\|^2 + \langle\nabla f(x), y-x\rangle \right\rbrace$$
Then show that $Prog(x) = -\frac{1}{2L}\| \nabla f(x)\|^2_*$.
Here $\|\cdot\|_*$ is the dual norm defined as $\| x\|_* = \max \lbrace\langle x,y\rangle: \| y\|\leq1\rbrace$.
Note that for the standard inner product $\tilde{x} = x-\frac{1}{L}\nabla f(x)$ is the Gradient step and $Prog(x) = -\frac{1}{2L}\| \nabla f(x)\|^2$ and also note that dual of the $l_2$ norm is $l_2$ norm itself.
$
 A: Claim. $\frac{L}{2}\|x_{k+1}-x_k\|^2 + \langle \nabla f(x_k),x_{k+1}-x_k\rangle = -\frac{1}{2L}\|\nabla f(x_k)\|_*^2.$
Proof. By definition of $x_{k+1}$, we have
$$
\begin{split}
&\frac{L}{2}\|x_{k+1}-x_k\|^2 + \langle \nabla f(x_k),x_{k+1}-x_k\rangle = \min_y \frac{L}{2}\|y-x_k\|^2 + \langle \nabla f(x_k),y-x_k\rangle \\
&=-\max_y \langle -\nabla f(x_k),y\rangle - \frac{L}{2}\|y-x_k\|^2 + \langle \nabla f(x_k),x_k\rangle\\
&=: -\left(y \mapsto \frac{L}{2}\|y-x_k\|^2\right)^*(-\nabla f(x_k)) + \langle \nabla f(x_k),x_k\rangle\;\text{(definition of convex conjugate)}\\
&= -\left(y \mapsto \frac{L}{2}\|y\|^2\right)^*(-\nabla f(x_k))\;\text{ (translation property of convex conjugate [1])}\\
&= -\frac{L}{2}\|-(1/L) \nabla f(x_k)\|_*^2\;\text{ (convex conjugate of the squares of a generic norm [2])}\\
&= -\frac{1}{2L}\|\nabla f(x_k)\|_*^2. \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\Box
\end{split}
$$
Now plug this in the LHS of the inequality $(1.1)$ of the referenced article, namely
$$
f(y) \le f(x) + \frac{L}{2}\|y-x\|^2 + \langle \nabla f(x), y - y\rangle
$$
together with the choice $(x,y) = (x_k,x_{k+1})$, we get
$$
f(x_k) - f(x_{k+1}) \ge \frac{1}{2L}\|\nabla f(x_k)\|_*^2.
$$
References
[1] https://en.wikipedia.org/wiki/Convex_conjugate#Table_of_selected_convex_conjugates
[2] https://fr.wikipedia.org/wiki/Fonction_conjugu%C3%A9e#Norme
