0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

As you mentioned the strong convexity means

$$\left( x-y | \nabla f(x) - \nabla f(y) \right) \ge m ||x-y||^2 $$

(I write $\left(.|.\right)$ for the inner product). And the Lipschitz property of the gradient means

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

Combining both gives:

$$ \left( x-y | \nabla f(x) - \nabla f(y) \right) = 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. $$

$\endgroup$

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.