# Strong convexity and Lipschitz

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$

• This is a bit vague. – copper.hat Oct 1 '13 at 15:20
• I edited it. Does that help? – Alice Oct 1 '13 at 15:33
• 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. – Harald Hanche-Olsen Oct 1 '13 at 15:34
• Actually, it'd be very helpful if you could perhaps show the steps? – Alice Oct 1 '13 at 15:37

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

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.

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