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?

  • $\begingroup$ Isn't this a consequence of the fact that all norms on $\mathbb{R}^n$ are equivalent? $\endgroup$ – madnessweasley Aug 8 '19 at 20:20
  • $\begingroup$ @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. $\endgroup$ – 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.

  • $\begingroup$ Thanks! You actually answered both of my questions. $\endgroup$ – Sean Ian Aug 8 '19 at 20:44

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.