Strict/Strong convexity of non-Euclidean norm

It is well-known that $$l_2$$ norm squared, $$f(x) = \frac{1}{2}\|x\|_2^2$$, is strongly convex with respect to $$l_2$$ norm. My question is what about other non-Euclidean norm squared, such as $$\frac{1}{2}\|x\|^2_1$$, $$\frac{1}{2}\|x\|^2_{\infty}$$. Are they strongly convex w.r.t. itself? ($$\frac{1}{2}\|x\|_1^2$$ strongly convex w.r.t. $$\|\cdot\|_1$$, etc.). Here the definition of strong convexity w.r.t. norm $$\|\cdot\|$$ is given by

$$f(\lambda x+ (1-\lambda)y) \leq \lambda f(x) + (1-\lambda)f(y)-\frac{\lambda(1-\lambda)}{2}\|x-y\|^2 \quad \forall x,y$$

Actually, are they even strictly convex?

• Isn't this a consequence of the fact that all norms on $\mathbb{R}^n$ are equivalent? – madnessweasley Aug 8 '19 at 20:20
• @madnessweasley Strong/Strict convexity are not topological properties; they are metric properties, so they do not remain invariant under equivalence of norms, which only guarantees topological equivalence. – uniquesolution Aug 8 '19 at 20:34

Claim. Assume that a certain norm $$\|\cdot\|$$ is not strictly convex. That is, there exist points $$x,y$$ such that $$x\neq y$$ and $$1=\|x\|=\|y\|=\|\frac{x+y}{2}\|$$ Consider the function $$f(x)=\frac{1}{2}\|x\|^2$$. Then $$f(x)$$ is not strongly convex with respect to the norm.
Proof. Choose $$x,y$$ as above and $$\lambda = \frac{1}{2}$$, we have $$f(\lambda x+(1-\lambda)y)=\frac{1}{2}\|\frac{x+y}{2}\|^2=\frac{1}{2}$$ and $$(1-\lambda)f(x)+(1-\lambda)f(y)=\frac{1}{2}\cdot\frac{1}{2}\|x\|^2+\frac{1}{2}\cdot\frac{1}{2}\|y\|^2=\frac{1}{2}$$ but $$\frac{\lambda(1-\lambda)}{2}\|x-y\|^2=\frac{1}{8}\|x-y\|^2>0,$$ because $$x\neq y$$. So the inequality defining strong convexity fails. Q.E.D
Since both the $$\|\cdot\|_1$$ and the $$\|\cdot\|_{\infty}$$ are not strictly convex, it follows that the functions in your question are not strongly convex with respect to their respective norms.