# Lower bound for Strongly convex and Lipschitz gradient function

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.

• I think we are reading the same paper, and I still didn't figure out this inequality... Feb 16, 2021 at 19:03

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"

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

• I reached the same (final) inequality you wrote, what the OP stated is from a published paper, and I can't figure out why the coefficient within the second term on the right hand side is $1/(m+M)$ rather than $m^2/M^2\,(m+M)$ Feb 16, 2021 at 19:00

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.