1
$\begingroup$

My question concerns strong convexity and the composition of functions. Let $f:\Omega \subseteq \mathbb{R}^n \rightarrow \mathbb{R}$ be a continuous differentiable function. Recall that $f$ is convex if its epigraph $\{ (\mathbf{x}, \mu) \in \Omega \times \mathbb{R} \colon \mu \geq f(\mathbf{x}) \}$ is a convex set. Furthermore, $f$ is strongly convex if it holds $$( \nabla_{\mathbf{x}} f - \nabla_{\mathbf{y}}f )^T (\mathbf{x} - \mathbf{y})\geq m \| \mathbf{x} - \mathbf{y} \|_2^2$$ for a constant $m > 0$. Note that strong convexity is a strictly stronger definition than convexity.

It is well-known that if $f$ is convex and $g$ is convex non-decreasing over an univariate domain, then the function $g \circ f$ is also convex. Does this property extends to strong convexity? Specifically, if $f$ is a strongly convex function as described above and $g$ is convex non-decreasing, is the function $g \circ f$ also strongly convex?

Progress I made on this question: It can be easily proven that $f$ is strong convex iff. the function $f(\boldsymbol{x}) - \frac{m}{2} \| \boldsymbol{x} \|_2^2$ is convex. Hence, to answer this question it is sufficient to prove that $(g \circ f)(\boldsymbol{x}) - \frac{\beta}{2} \| \boldsymbol{x} \|_2^2$ is a convex function for some parameter $\beta > 0$, given that $f$ is strongly convex and $g$ is convex non-decreasing.

$\endgroup$
1
  • $\begingroup$ Also in the progress you mentioend, that is actually the definition of weakly convex. $f$ is $m$-strongly convex if $f-m\|\cdot\|^2/2$ is convex. $\endgroup$
    – Zim
    Jan 11 at 22:46
0
$\begingroup$

No; here is a counterexample:

Let $f=\|\cdot\|^2$ which is strongly convex. However, if we let $g$ be the zero function, then $g\circ f$ is also the zero function, which is convex, but not strongly convex.

$\endgroup$
2
  • $\begingroup$ Thank you for your reply. What if we take $g$ to be strongly convex then? $\endgroup$
    – fq00
    Jan 12 at 9:28
  • $\begingroup$ @fq00 Great question! It might even be enough to have $g$ strictly increasing, but I'm not sure $\endgroup$
    – Zim
    Jan 12 at 21:51

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.