9
$\begingroup$

What can you say about the L and $\lambda$ for a $\lambda$-strongly convex differentiable function, if its gradient if L-Lipschitz?

Also, it is given that $\lVert \nabla f(y) - \nabla f(x)\rVert_2 \ge \lambda\lVert y-x\rVert_2 $

$\endgroup$
  • 1
    $\begingroup$ This is a bit vague. $\endgroup$ – copper.hat Oct 1 '13 at 15:20
  • $\begingroup$ I edited it. Does that help? $\endgroup$ – Alice Oct 1 '13 at 15:33
  • $\begingroup$ The edit just gives the definition of $\lambda$-strongly convex, right? Write it up next to the definition of $L$-Lipshitz for the gradient, and I think you have your answer. $\endgroup$ – Harald Hanche-Olsen Oct 1 '13 at 15:34
  • $\begingroup$ Actually, it'd be very helpful if you could perhaps show the steps? $\endgroup$ – Alice Oct 1 '13 at 15:37
4
$\begingroup$

Suppose that $f:\mathbb{R}^n\to\mathbb{R}$ is strongly convex with the modulus $\lambda$ and it is differentiable with its derivative satisfying $$ \textbf{(I)}\quad\quad\|\nabla f(x)-\nabla f(y)\|\leq L\|x-y\|, \quad \forall x,y\in \mathbb{R}^n. $$ Then, we have $\lambda \leq L$.

Proof.

Step 1. For all $x,y\in \mathbb{R}^n$ $$ \textbf{(II)}\quad\quad f(x)-f(y)\geq \langle\nabla f(y), x-y\rangle+(\lambda/2)\|x-y\|^2. $$ By the strong convexity of $f$ $$ f(\alpha x+(1-\alpha)y)\leq \alpha f(x)+(1-\alpha)f(y)-\lambda\alpha(1-\alpha)\|x-y\|^2/2. $$ for all $\alpha\in (0,1)$. It implies that $$ f(x)-f(y)\geq\frac{f(y+\alpha(x-y))-f(y)}{\alpha}+\lambda(1-\alpha)\|x-y\|^2/2. $$ Letting $\alpha\to 0^+$, we obtain (I).

Step 2. For all $x,y\in \mathbb{R}^n$ $$ \textbf{(III)}\quad\quad\langle \nabla f(x)-\nabla f(x), x-y\rangle\geq \lambda \|x-y\|^2. $$ Applying inequality (II) we deduce $$ f(x)-f(y)\geq \langle\nabla f(y), x-y\rangle+(\lambda/2)\|x-y\|^2, $$ $$ f(y)-f(x)\geq \langle\nabla f(x), y-x\rangle+(\lambda/2)\|x-y\|^2. $$ Adding two inequalities we get (II).

Step 3. $\quad\lambda\leq L$

Choosing $x,y\in\mathbb{R}^n$ such that $x\ne y$. By (I), (III), and the Cauchy Schwarz $$ \lambda \|x-y\|^2\leq \langle \nabla f(x)-\nabla f(x), x-y\rangle\leq\|\nabla f(x)-\nabla f(x)\|\|x-y\|\leq L\|x-y\|^2. $$ Since $x\ne y$, this follows that $\lambda\leq L$.

$\endgroup$
3
$\begingroup$

Assuming that the definitions are what I think they are, the two requirements are $$\begin{aligned} \|\nabla f(y)-\nabla f(x)\|&\ge\lambda\|y-z\|&&\text{$f$ is $\lambda$-convex}\\ \|\nabla f(y)-\nabla f(x)\|&\le L\|y-z\|&&\text{$\nabla f$ is $L$-Lipschitz} \end{aligned} $$ for all $y$, $z$. Really, I insist that you draw the inevitable conclusion without my help.

$\endgroup$
  • $\begingroup$ Sounds good. Thanks! $\endgroup$ – Alice Oct 1 '13 at 16:02

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.