3
$\begingroup$

I would like to know if the following conjecture is true or false?

If $f(x) = g(x) + h(x)$ where $g$ is m-strongly convex and $h$ is convex, then $f$ is m-strongly convex.

NOTE: For a non-differentiable function $F$, m-strongly convexity means $F(y) \geq F(x) + g^T(y - x) + \frac{m}{2} ||y - x||^2, \forall x, y$ where $g \in \partial F(x)$ is a subgradient of $F$ at $x$. If $F$ is differentiable, m-strongly convexity can also be defined as $\nabla^2 F(x) \succeq m I, \forall x$ where $I$ is the identity matrix. You can see the wikipedia page, this blog post by Sébastien Bubeck, or these lecture notes from the Algorithms course at Cornell University for more details on strong convexity.

$\endgroup$
5
$\begingroup$

Sure, you can just add the inequalities. That is, if $g$ is $m$-strongly convex then, for some $a \in \partial g(x)$ $$ g(y) \ge g(x) + a^T(y-x) + \frac{m}{2}\|y-x\|^2, $$ And if $h$ is convex, then for some $b \in \partial h(x)$: $$ h(y) \ge h(x) + b^T(y-x), $$ Then by adding we have: $$ g(y) +h(y) \ge g(x) +h(x) + (a+b)^T(y-x) + \frac{m}{2}\|y-x\|^2 $$ $$ f(y) \ge f(x) + (a+b)^T(y-x) + \frac{m}{2}\|y-x\|^2 $$ So $f$ is strongly $m$-convex and $a+b \in \partial f(x)$:

$\endgroup$
  • $\begingroup$ thank you for the proof! It all makes sense. I think to finish the proof we need to show that the conclusion holds for any $g \in \partial f$, and for that we can use the fact that $\partial f = \partial g + \partial h$ where $+$ is the sumset (en.wikipedia.org/wiki/Sumset) of the two subgradient sets. $\endgroup$ – Sobi Feb 3 '16 at 15:19
  • $\begingroup$ The above argument shows that $\partial g + \partial h \subseteq \partial f$, which is all you need for this. $\endgroup$ – p.s. Feb 4 '16 at 2:23

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.