Claim 1: {convex and non-decreasing func.} ◦ {convex func.} is convex
Claim 2: Norms are convex (The triangle inequality is the same thing as convexity of the norm)
Claim 3: {convex and non-decreasing func.} ◦ {metric} is probably not a metric (or, {concave and non-decreasing func.} ◦ {metric} is still a metric)
I've seen proof of each of these claims[1, 2, 3.1, 3.2]. However, claim 3 seems unexpected under the context of 1 and 2. How can I make sense of this?
Let's say we have a vector space $X$ and a function $p:X\to \mathbb{R}^+$ such that $p(ax)=|a|p(x)$ for all $a\in \mathbb{R}$ and $x\in X$, and such that $p(x)=0$ iff $x=0$.
Then $p$ satisfies the triangle inequality (and is therefore a norm) iff it's a convex function. This is where our connection between the triangle inequality and convexity come from. This is why we might expect $f(\|\cdot\|)$ to be a metric, because by $1$ and $2$, it's convex. So it should satisfy triangle inequality, right?
But the proof that $p$ satisfies triangle inequality iff it's convex uses the positive homogeneity. Note: $p$ actually satisfies something stronger than positive homogeneity: It is positive homogeneous and symmetric/balanced. By symmetric/balanced, we mean that $p(ax)=p(|a|x)$ for any scalar $a$ and any vector $x$. So we have assumed something more than positive homogeneity, but in our connections below, we actually will only use the positive homogeneity, in that we will only pull positive (or at least non-negative) scalars out of $p$.
If $p$ satisfies the triangle inequality, we have $$p(\theta x+(1-\theta)y)\leqslant p(\theta x)+p((1-\theta)y)=\theta p(x)+(1-\theta)p(y).$$ The second step where we pull the $\theta, 1-\theta$ out of $p$ uses positive homogeneity.
On the other hand, if $p$ is convex, we fix $x,y\neq 0$ and note that \begin{align*}p(x+y) & = (p(x)+p(y))p\Bigl(\frac{p(x)}{p(x)+p(y)} \cdot \frac{x}{p(x)}+\frac{p(y)}{p(x)+p(y)}\cdot \frac{y}{p(y)}\Bigr) \\ & \leqslant (p(x)+p(y))\Bigl(\frac{p(x)}{p(x)+p(y)}\cdot \frac{p(x)}{p(x)} + \frac{p(y)}{p(x)+p(y)}\cdot \frac{p(y)}{p(y)}\Bigr) \\ & = p(x)+p(y).\end{align*} We used positive homogeneity several times here to pull $p(x), p(y), p(x)+p(y)$ outside of $p$.
If we drop positive homogeneity (say $p(x)=\|x\|^2$, where $\|\cdot\|$ is some existing norm), then repeating the calculation above yields that $$p(x+y)\leqslant (p(x)+p(y))^2 \Bigl(\frac{p(x)}{p(x)+p(y)}\cdot \frac{p(x)}{p(x)^2}+\frac{p(y)}{p(x)+p(y)}\cdot \frac{p(y)}{p(y)^2}\Bigr).$$ That's because we now have $p(ax)=a^x2 p(x)$, so things get squared when we pull them outside of $p$. But this inequality isn't useful to see triangle inequality. Similarly, we could try $\frac{\sqrt{p(x)}}{\sqrt{p(x)}+\sqrt{p(y)}}$ as our first weight, which would yield $p(x)/p(x)$ and $p(y)/p(y)$ terms, but this only leads to triangle inequality on $\sqrt{p}=\|\cdot\|$ again.
So my summary for why $f(\|\cdot\|)$ isn't a metric even though it's convex (when $f$ is convex, non-decreasing, and $f(x)=0$ iff $x=0$) is that our familiar pairing of convexity and triangle inequality needs the positive homogeneity, which $f$ typically will not have.
EDIT: Through frequent association, we often associate convexity with the triangle inequality (for checking that a quasi-seminorm is a seminorm, for example). So the question asks: If convexity goes hand in hand with triangle inequality, we would expect convexity-preserving compositions to preserve triangle inequality, and $g\mapsto f\circ g$ is convexity-preserving when $f$ is convex and non-decreasing. But actually it turns out that we want $f$ to be concave and non-decreasing. Why?
When I read the question, I was stumped. After thinking about it for a bit, here's what I've come up with. The heuristic: We want subaddtivity preservation, not convexity preservation. It is a special property of norms (specifically, it uses positive homogeneity) that convexity implies subadditivity for a norm. But that's kind of a fluke, special to the case of a norm as opposed to other metrics. It's only in the special case of positive homogeneity that we get the convexity-subadditivity connection.
For a set $X$ and a function $\rho:X\times X\to \mathbb{R}^+$, $\rho$ satisfies the triangle inequality if for all $x,y,z\in X$, $\rho(x,z)\leqslant \rho(x,y)+\rho(y,z)$.
What conditions do we need to place on a function $f:\mathbb{R}^+\to \mathbb{R}^+$ to get that for any $X$ and any $\rho:X\times X\to \mathbb{R}^+$ satisfying the triangle inequality, $f\circ \rho$ also satisfies the triangle inequality?
Claim: If $f:\mathbb{R}^+\to \mathbb{R}^+$ is subadditive and non-decreasing, then for any $X$ and any $\rho:X\times X\to \mathbb{R}^+$ satisfying the triangle inequality, $f\circ \rho$ also satisfies the triangle inequality.
Proof: Assume that $f$ is subadditive and non-decreasing. Assume that $X$ is a set and $\rho:X\times X\to \mathbb{R}^+$ satisfies the triangle inequality. Fix any $x,y,z\in X$. Then $$f(\rho(x,z)) \leqslant f(\rho(x,y)+\rho(y,z))\leqslant f(\rho(x,y))+f(\rho(y,z)).$$ The first inequality uses that $f$ is non-decreasing, the second uses subadditivity.
We have a partial converse: Assume that $f$ is not subadditive. There exist $a,b\in \mathbb{R}^+$ such that $f(a)+f(b)<f(a+b)$. Define $\rho:\mathbb{R}^+\times\mathbb{R}^+\to \mathbb{R}^+$ by $\rho(x,y)=|x-y|$. Then take $x=0$, $y=a$, and $z=a+b$. $$f(\rho(x,z))=f(a+b)>f(a)+f(b)=f(\rho(x,y))+f(\rho(y,z)).$$
If $X$ is a vector space and $d:X\times X\to \mathbb{R}^+$ is a symmetric, translation invariant function (that is, $f(u,v)=f(v,u)$ and $f(u,v)=f(u+w,v+w)$ for all $u,v,w\in X$), then $d$ satisfies the triangle inequality if and only if $D(x):=d(0,x)$ is subadditive. In the case that we start with an absolutely homogeneous functional $p:X\to \mathbb{R}^+$ and ask if it's a seminorm, and then try to build a pseudometric out of it, the pseudometric candidate $d(x,y)$ is given by $d(x,y)=p(x-y)$, and then $D(x)=p(x)$ again. But the fact above regarding $d$ and $D$ is true, even without absolute homogeneity.
If we start with our symmetric, translation invariant $d$, then asking that the operation $d\mapsto f\circ d$ preserves the triangle inequality is equivalent to asking that $D\mapsto f\circ D$ preserve subadditivity.
An aside: If $f:\mathbb{R}^+\to \mathbb{R}^+$ is concave, then it is non-decreasing. To see this, note that if $0\leqslant a<b$ are such that $f(a)>f(b)$, then the function $g(x)=f(x+a)-f(a)$ is concave, satisfies $g(0)=0$, and satisfies $g(b-a)<0$. For $0<\theta<1$, \begin{align*} g(b-a) & = g(\theta \theta^{-1}(b-a)) = g(\theta \theta^{-1}(b-a)+(1-\theta)0)) \geqslant \theta g(\theta^{-1}(b-a))+(1-\theta)g(0) \\ & =\theta g(\theta^{-1}(b-a)).\end{align*} Therefore $$g(b-a)/\theta \geqslant g(\theta^{-1}(b-a)).$$ Letting $\theta$ approach $0$ from the right says that $\lim_{x\to\infty} g(x)=-\infty$. But this contradicts our original assumption that $f$ takes only non-negative values. This argument becomes much simpler if we assume differentiable, because then concavity says $f'$ is decreasing. If $f$ decreases at all, ever, then it decreases at least that fast forever, and therefore cannot stay positive forever.
Back to the question: If $f:\mathbb{R}^+\to \mathbb{R}^+$ is concave (and therefore non-decreasing), and $f(0)=0$, then $f$ is subadditive. This is mentioned in the comments here and proved in the linked questions in the original post. For the sake of having a complete answer here, I will repeat it.
Fix $x,y>0$. Then \begin{align*} f(x)+f(y) & = f\Bigl(\frac{x}{x+y}\cdot (x+y)+\frac{y}{x+y}\cdot 0\Bigr) \\ & + f\Bigl(\frac{y}{x+y}\cdot (x+y)+\frac{x}{x+y}\cdot 0\Bigr) \\ & \geqslant \frac{x}{x+y}f(x+y)+0+\frac{y}{x+y}f(x+y)+0\\ & =f(x+y).\end{align*} Here we're implicitly using that concave and $f(0)=0$ imply $f(\theta x)\geqslant \theta f(x)$, which doesn't come up at all for the positive homogeneous case, because we just pull $\theta$ out in that case.
On the other hand, if $p$ is a convex, positive homogeneous, non-negative functional on $X$ (and if $p(u)+p(v)>0$), then we have \begin{align*} p(u+v)& = (p(u)+p(v)+2\epsilon) p\Bigl(\frac{p(u)+\epsilon}{p(u)+p(v)+2\epsilon}\cdot \frac{u}{p(u)+\epsilon} + \frac{p(v)+\epsilon}{p(u)+p(v)+2\epsilon} \cdot \frac{v}{p(v)+\epsilon}\Bigr) \\ & \leqslant (p(u)+\epsilon)p\Bigl(\frac{u}{p(u)+\epsilon}\Bigr)+(p(v)+\epsilon)p\Bigl(\frac{v}{p(v)+\epsilon}\Bigr) \\ & < (p(u)+\epsilon)(1)+(p(v)+\epsilon)(1)\\ & = p(u)+p(v)+2\epsilon.\end{align*} Taking the limit as $\epsilon\to 0^+$ gives the triangle inequality. We added the $\epsilon$ to avoid dividing by zero in the trivial case that $u=v=0$.
So we can see that, in addition to using positive homogeneity frequently, the proof of subadditivity of $f$ from concavity represents $x$ and $y$, separately, as convex combinations of $x+y$ and $0$. The proof of subadditivity of $p$ from convexity of $p$ (roughly speaking) represents $x+y$ and convex combinations of $[p(u)+p(v)]u$ and $[p(u)+p(v)]v$. So the way that concavity/convexity are used within the arguments are kind of reverses of each other.
