5
$\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$

1 Answer 1

Reset to default
7
$\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$
2
  • $\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, 2016 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, 2016 at 2:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .