According to Prof. Vandenberg's lecture notes [http://www.seas.ucla.edu/~vandenbe/236C/lectures/gradient.pdf], page 11, a function is called Lipschitz continuous gradient when $$ \|\nabla f(y)-\nabla f(x)\|_2 \leq \alpha\|y-x\|_2 $$ Note that the definition does not assume that $f$ is a convex function.

However, if $f$ is a convex function we have $$ f(y) \leq f(x) + \langle \nabla f(x),y-x \rangle + \frac{\alpha}{2}\|y-x\|_2^2 $$

Can we prove the reverse, i.e., if we have

$$ f(y) \leq f(x) + \langle \nabla f(x),y-x \rangle + \frac{\alpha}{2}\|y-x\|_2^2 $$ then $$ \|\nabla f(y)-\nabla f(x)\|_2 \leq \alpha\|y-x\|_2 $$

Hint: using $ f(y) \leq f(x) + \langle \nabla f(x),y-x \rangle + \frac{\alpha}{2}\|y-x\|_2^2 $ we can conclude that $g(x)=\frac{\alpha}{2}\|x\|_2^2-f(x)$ is convex. Since $g(x)$ is convex, monotonicity of the gradient of $g$ results in

$$ \langle \nabla f(x) - f(y),y-x \rangle \leq \alpha\|y-x\|_2^2 $$ but how is possible to get back to the following? $$ \|\nabla f(y)-\nabla f(x)\|_2 \leq \alpha\|y-x\|_2 $$ I am wondering if the above method is right way to prove it. In addition, is there any other condition that can be applied to the convex function $f(x)$ to have Lipschitz continuous gradient?


No. Intuitively, a function is Lipschitz means that the derivative is continuous. (It's a bit stronger, even.) Consider the function $f:\mathbb{R}\rightarrow\mathbb{R}$ such that $f(x)=|x|$. This function is convex, but its derivative is not continuous, therefore it is not Lipschitz.


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.