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}\lbrace \frac{L}{2}\| y-x\|^2 + \langle\nabla f(x), y-x\rangle\rbrace$

$Prog(x) = \min_{y\in \mathbb{R}^n}\lbrace \frac{L}{2}\| y-x\|^2 + \langle\nabla f(x), y-x\rangle\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. $• Do you mean$prox$instead of$prog$? – Tony S.F. Feb 22 '18 at 20:54 • How is that relevant? – Sudipta Roy Feb 23 '18 at 4:43 • You're asking how using the correct term for a function/operator is relevant? – Michael Grant Feb 23 '18 at 21:35 • I dont follow. Can you please elaborate ? The specific question is from [arxiv.org/pdf/1407.1537.pdf] . – Sudipta Roy Feb 24 '18 at 9:44 • I agree with the other comments that you can't just toss ad-hoc pseudonyms for otherwise well-known concepts. Also asking "how is that relevant ?" sounds rude and nonconstructive, in IMHO. – dohmatob Feb 24 '18 at 12:18 1 Answer 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