Strict/Strong convexity of non-Euclidean norm

Question

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?

Answer 1

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.

Answer 2

I hope this answer can be useful, I also gave it as an answer to that question: Strong convexity of squared $\ell_p$ norm in Bregman divergence

I think from that paper (not the original reference but they cite the original one) that the answer is positive for $p\in(1, 2] $, with $\sigma = p-1$: from section 7.2, they say:

For any $p \in (1,2]$, the function $\frac{1}{2}||w||_p^2$ is strongly convex with respect to $||·||_p$ with the convexity parameter p−1 (e.g., Juditsky and Nemirovski, 2008)