Lower bound for Strongly convex and Lipschitz gradient function

Question

I was reading this paper but could not understand one of it's condition. It says a function $f(x)$ is twice differentiable and strongly convex with parameter $m$ and Lipschitz continuous gradient with parameter $M$ and $M\geq m$. Then: $$(x-y)^T(\nabla f(x)-\nabla f(y) \geq \frac{mM}{m+M} \lVert x-y \rVert^2+\frac{1}{m+M}\lVert \nabla f(x)-\nabla f(y) \rVert ^2$$

I know that if $f$ is strongly convex and Lipshcitz continuous gradient, then : $$(x-y)^T(\nabla f(x)-\nabla f(y)) \geq m \rVert x-y\lVert ^2$$ and $$(x-y)^T(\nabla f(x)-\nabla f(y)) \geq \frac{1}{M} \lVert \nabla f(x)-\nabla f(y) \rVert ^2 $$. I tried multiply each by $M$ and $m$ and adding up but that didn't quite work.

Answer 1

I emailed the author of the paper, here is the reply I got: "It is a non trivial result which is often used in convex optimization. I guess you can find it in Nesterov's book Introductory Lectures on Convex Optimization: A Basic Course.​ Theorem 2.1.12"

Answer 2

Are you sure about the coefficient within the second term on the right hand side?

As you mentioned the strong convexity means

$$(x-y)\cdot (\nabla f(x) - \nabla f(y) ) \ge m ||x-y||^2, $$

and the Lipschitz property of the gradient means

$$ ||\nabla f(x) - \nabla f(y)|| \le M ||x-y||. $$

Combining both gives:

$$ (x-y) \cdot (\nabla f(x) - \nabla f(y)) = m\frac{m+M}{m+M} ||x-y||^2 \ge \frac{mM}{m+M} ||x-y||^2 + \frac{m^2}{m+M} ||x-y||^2 \ge \frac{mM}{m+M} ||x-y||^2 + \frac{m^2}{M^2(m+M)} ||\nabla f(x) - \nabla f(y)||^2. $$

Answer 3

you can define $g(x)=f(x)-\frac{m}{2}\|x\|^2$, which is convex because $f$ is strongly convex with constant $m$. The function $g$ also satisfies $$g(y)-g(x)-\langle\nabla g(x),y-x\rangle = f(y)-f(x)-\langle\nabla f(x),y-x\rangle-\frac{m}{2}\|x-y\|^2 \le \frac{M-m}{2}\|x-y\|^2,$$ because $\nabla f$ is Lipschitz-continuous with constant $M$. It follows that $\nabla g$ is Lipschitz-continuous with constant $M-m$ and cocoercive with constant $(M-m)^{-1}$ (these three implications are actually equivalences, as shown in Theorem 18.15 in the book of Bauschke and Combettes), which means that $$\langle \nabla g(x)-\nabla g(y),x-y\rangle\ge\frac{1}{M-m}\|\nabla g(x)-\nabla g(y)\|^2.$$ Rewriting this back in terms of $f$, yields the desired inequality. I hope this helps.