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. $

  • 2
    $\begingroup$ Do you mean $prox$ instead of $prog$? $\endgroup$ – Tony S.F. Feb 22 '18 at 20:54
  • $\begingroup$ How is that relevant? $\endgroup$ – Sudipta Roy Feb 23 '18 at 4:43
  • 4
    $\begingroup$ You're asking how using the correct term for a function/operator is relevant? $\endgroup$ – Michael Grant Feb 23 '18 at 21:35
  • $\begingroup$ I dont follow. Can you please elaborate ? The specific question is from [arxiv.org/pdf/1407.1537.pdf] . $\endgroup$ – Sudipta Roy Feb 24 '18 at 9:44
  • 1
    $\begingroup$ 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. $\endgroup$ – dohmatob Feb 24 '18 at 12:18

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. $$


[1] https://en.wikipedia.org/wiki/Convex_conjugate#Table_of_selected_convex_conjugates

[2] https://fr.wikipedia.org/wiki/Fonction_conjugu%C3%A9e#Norme


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.