1
$\begingroup$

Suppose $f(\theta)=g(\theta)+h(b)$ where $\theta=(a, b)^\intercal$, $g(\cdot)$ is strongly convex and $h(\cdot)$ is convex. Note, $h(\cdot)$ may be non-differentiable. Is $f(\theta)$ strongly convex?

$\endgroup$

2 Answers 2

2
$\begingroup$

I will use the notation $\theta=(\theta_1, \theta_2)$ and $\Delta=(\Delta_1, \Delta_2)$.

Strong convexity of $g$ implies $$g(\theta + \Delta) - g(\theta) - \langle \nabla g(\theta), \Delta \rangle \ge \frac{1}{2} \|\Delta\|^2.$$ Convexity of $h$ implies $$h(\theta_2 + \Delta_2) - h(\theta_2) - h'(\theta_2) \Delta_2 \ge 0.$$

Noting that $\nabla f(\theta) = \nabla g(\theta) + (0, h'(\theta_2))$, we have $$f(\theta + \Delta) - f(\theta) - \langle \nabla f(\theta), \Delta \rangle \ge \frac{1}{2} \|\Delta\|^2.$$

$\endgroup$
1
$\begingroup$

For $g$ to be strongly convex, we have $\tilde{g}(x) := g(x) - \tfrac m2 x^T I x = g(x) - \tfrac m2 \|x\|_2^2$ such that $\tilde{g}$ is convex for some $m>0$, i.e., $\nabla^2 \tilde{g} \succeq 0$. But since $h$ is convex, we have $\nabla^2 h \succeq 0$ too. So, since the sum of convex functions is convex (i.e., looking at the second derivatives), we have that $g$ is strongly convex because $\nabla^2 (\tilde{g} + h) = \nabla^2 (g+h) - \nabla^2 \left(\tfrac m 2 x^T I x\right) \succeq 0 \implies \nabla^2 (g + h) \succeq \frac{m}{2}I$.

$\endgroup$
4
  • $\begingroup$ Note, the domains are different for $g$ and $h$. What if $h$ is not differentiable? $\endgroup$
    – jsmath
    Jun 8, 2018 at 0:15
  • $\begingroup$ Regarding domains, we could restrict to single dimensions for each dimension of the domains of $g$ and $h$ and use the second-derivative argument, so my answer is kind of hiding that...sorry. For the differentiability issue, I'd use the below or this argument, but you may be interested in the Hessian "equivalent" of sub-gradients (see (2.4)) $\endgroup$
    – jjjjjj
    Jun 8, 2018 at 0:39
  • $\begingroup$ Follow your argument. If $g(x) - \tfrac m2 \|x\|_2^2$ is convex, then $g(x)+h(x) - \tfrac m2 \|x\|_2^2$ is convex since $h(x)$ is convex. Thus $g(x)+h(x)$ is strongly convex. $\endgroup$
    – jsmath
    Jun 8, 2018 at 0:46
  • $\begingroup$ Ya, and we can see convexity in some informal sense by my $\nabla^2$ notation. It obscures the details of what happens when the domains are different (and not to mention the non-differentiable case), but it just takes some extra detail to look at these cases one-dimension by one-dimension at a time for the domain issue. For the differentiability issue, you could do something like that paper. But it'd be easier to do something like @angryavian's answer. So I guess my answer was a "moral" answer rather than a "detailed" answer $\endgroup$
    – jjjjjj
    Jun 8, 2018 at 0:50

You must log in to answer this question.

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