Is it true that a function is $c$-strongly convex if $f - c\|x\|^2_p$ is convex for ANY norm $\|x\|_p$?

Question

It is a common knowledge that a function is $c$-strongly convex if $f - c\|x\|^2_2$ is convex.

However, can we replace $\|x\|_2$ with any norm $\|x\|_p$? I strongly suspect this holds, but from looking at several references online (see p 26 of this), it might also be true that this condition ONLY holds for $p = 2$.

I find that almost all proofs on Mathstacksexchange implicitly assume that the norm is 2-norm. Whenever people write $\|x\|^2$ in their proofs, what they actually mean is that $\|x\|^2$ is the 2-norm.

Consider the example here, which the top-answer said to show $$"R := \alpha (1 - \alpha)\|x-y\|^2 + \|\alpha x + (1-\alpha) y\|^2 - \alpha \|x\|^2 - (1 - \alpha) \|y\|^2 = 0."$$ But this implicitly assumes $\|x\|^2$ is the 2-norm, otherwise I cannot see how this equality holds (otherwise it is simple if we just write $\|x-y\|^2$ as $(x-y)^T(x-y)$. But only holds for 2-norm.)

I would appreciate it if someone can verify/check this result.

Answer 1

Following the clarification in your comment, for a given norm $\|\cdot\|$ , $f(x)$ is here called $c$-strongly convex if for all $x,y$ and $\alpha \in [0,1]$ we have

$$f(\alpha x + (1-\alpha)y) \le \alpha f(x) + (1 - \alpha)f(y) - \frac{c}{2}\alpha(1-\alpha)\|x-y\|^2. \tag{1}$$

Note that for $\|\cdot\|_2$, this becomes equivalent to the definition of c-strong convexity commonly used in the literature (i.e., a function is called $c$-strongly convex if $f(x) - c\|x\|^2_2$ is convex).

Let us define

$$R(x,y) := \alpha (1 - \alpha)\|x-y\|^2 + \|\alpha x + (1-\alpha) y\|^2 - \alpha \|x\|^2 - (1 - \alpha) \|y\|^2.$$

From the proof given in this answer, we can see that

• if $R(x,y) \ge 0$ for $\|x\|_p$ , then inequality (1) implies convexity of $f(x) - c\|x\|^2_p$.
• if $R(x,y) \le 0$ for $\|x\|_p$ , then convexity of $f(x) - c\|x\|^2_p$ implies inequality (1).

For $p=2$, we always have $R(x,y) = 0$, so convexity of $f(x) - c\|x\|^2_2$ and (1) are equivalent:

$$\color{blue}{\fbox{inequality (1) holds for $\|\cdot\|_2$ iff $f(x) - c\|x\|^2_2$ is convex.}}$$

Negative result:

Neither $R(x,y) \ge 0$ nor $R(x,y) \le 0$ always holds for $\|x\|_p$ with any $p > 1$ excepting $p=2$.

Let $\alpha=\frac{1}{2}$ and $p=3$. Then, for

$$x=(0.10,0.93)$$ $$y=(0.87,0.50)$$

we have

$$R(x,y)=-0.0761486852525359,$$

whereas for

$$x=(0.43, 0.87)$$ $$y=(0.82, 0.29)$$

we have

$$R(x,y)=0.0101235872833216.$$

Other examples can be generated for any $p \neq 1,2$.

Positive result:

For $p=1$, it can proven that $R(x,y) \ge 0$, which means

$$\color{blue}{\fbox{inequality (1) for $\|\cdot\|_1$ implies convexity of $f(x) - c\|x\|^2_1$.}}$$

After some calculations, the proof reduces to show the inequality:

$$\alpha(1-\alpha) \big |(x_1-y_1)(x_2-y_2) \big|+\big |(\alpha x_1+(1-\alpha) y_1)(\alpha x_2+(1-\alpha) y_2) \big| \ge \alpha |x_1 x_2|+(1-\alpha) |y_1 y_2| \tag{2}$$

for any $\alpha \in [0,1]$, and $(x_1,y_1)$ and $(x_2,y_2)$. WLOG, we can assume $x_1, x_2, y_1, y_2 \ge0$, and define:

$$A=\alpha(1-\alpha)(x_1-y_1)(x_2-y_2)$$ $$B=(\alpha x_1+(1-\alpha) y_1)(\alpha x_2+(1-\alpha) y_2).$$

Then, the inequality (2) follows from

$$|A|+|B|\ge |A+B|=\alpha x_1 x_2+(1-\alpha) y_1 y_2.$$