5
$\begingroup$

Pg 12 - 14 http://www.seas.ucla.edu/~vandenbe/236C/lectures/gradient.pdf

Def: A $C^1$ convex function $f$ is Lipschitz smooth if $\exists L > 0$ s.t. $\forall x, y\in \mathbb{R}^n$ \begin{equation} \|\nabla f(x) - \nabla f(y)\| \leq L\|x - y\| \end{equation}

Claim: A $C^1$ convex function $f$ that satisfies $$f(y) \leq f(x) + \nabla f(x)^T(y-x) + \dfrac{L}{2}\|y-x\|^2$$ is Lipschitz Smooth

(Note: 1. the reverse implication is referred to as the "quadratic upper bound property" 2. One poster suggested to use fenchel duality to show this Lipschitz Smoothness, Strong Convexity and the Hessian)

Proof attempt:

It seems that the direct approach is through re-arrange and combine, which gives: $$0 \leq (\nabla f(x)-\nabla f(y))^T(y-x) + L\|y-x\|^2$$ $$(\nabla f(y)-\nabla f(x))^T(y-x) \leq L\|y-x\|^2$$

Using CS-inequality on the above $(\nabla f(y)-\nabla f(x))^T(y-x) \leq L\|y-x\|^2$ gives:

$$(\nabla f(y)-\nabla f(x))^T(y-x) \leq \|\nabla f(y)-\nabla f(x)\|\|y-x\|$$ Now I have:

  1. $$(\nabla f(y)-\nabla f(x))^T(y-x) \leq L\|y-x\|^2$$

  2. $$(\nabla f(y)-\nabla f(x))^T(y-x) \leq \|\nabla f(y)-\nabla f(x)\|\|y-x\|$$

How do I conclude $\|\nabla f(x) - \nabla f(y)\| \leq L\|x - y\|$?


$\endgroup$
  • $\begingroup$ It seem's like first three terms of taylor series. $\endgroup$ – kolobokish Nov 19 '16 at 8:41
  • 1
    $\begingroup$ See what. The last expression you got, is exactly Cauchy-Swartz inequlaity(if we require positivness, and Lipshitz continuity.) So maybe it should be if and only if ?. $\endgroup$ – kolobokish Nov 19 '16 at 9:41
2
$\begingroup$

Co-coercivity of the gradient (Lecture 1, slides 15-16 in Vandenberghe's 236c notes) tells us that $$ \frac{1}{L} \| \nabla f(y) - \nabla f(x) \|^2 \leq (\nabla f(y) - \nabla f(x))^T (y - x) $$ for all $x,y$. Now combine this with your equation 1) to conclude that $$ \| \nabla f(y) - \nabla f(x) \| \leq L \| y - x \| $$ for all $x,y$.

$\endgroup$

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.