Squared $L_2$ norm is strongly convex w.r.t. $L_1$ norm

113 Views Asked by At

I am not assured to say True or False of the statement written in the title.

Suppose a function $h$ receives a $K$-dimensional vector $\boldsymbol{p}$, which is a member of $K$-simplex (i.e., $\Delta_K$). (Please note that $\boldsymbol{w}$ is just a given fixed probability vector also in $\Delta_K$, thus the function $h$ calculates the squared $L_2$ norm of difference between $\boldsymbol{p}$ and $\boldsymbol{w}$) $$h(\boldsymbol{p})=\|\boldsymbol{p}-\boldsymbol{w}\|_2^2$$

To check the strong convexity of the function $h$ w.r.t. $L_1$ norm, I used the well-known property of the strong convexity as below.

$$\begin{gathered} \langle\nabla h(\boldsymbol{p})-\nabla h(\boldsymbol{q}), \boldsymbol{p}-\boldsymbol{q}\rangle \\ =2 \sum_{i=1}^K\left(\left(p_i-w_i\right)-\left(q_i-w_i\right)\right)\left(p_i-q_i\right) \\ =2 \sum_{i=1}^K\left(p_i-q_i\right)^2=2\|\boldsymbol{p}-\boldsymbol{q}\|_2^2 \\ =2 \sum_{i=1}^K\left|p_i-q_i\right|^2 \geq \frac{2}{K}\left(\sum_{i=1}^K\left|p_i-q_i\right|\right)^2 \\ =\frac{2}{K}\|\boldsymbol{p}-\boldsymbol{q}\|_1^2 \end{gathered}$$

About the inequality, I have used the relationship between $L_1$ and $L_2$ norm. (https://myweb.uiowa.edu/pbreheny/7110/wiki/l1-l2-inequality.html)

I wonder if I can conclude that the squared $L_2$ norm is therefore $\frac{2}{K}$-strongly convex w.r.t. $L_1$ norm as the above derivation. Is this approach legitimate?

If not, can I get reasons why? Thank you all in advance!

Addendum) The above derivation is in fact inspired from proving $1$-strong convexity of negative entropy w.r.t. $L_1$ norm from (Lemma 6.17 of Orabona, 2019; strong convxity of a negative entropy w.r.t. L1 norm)

If my derivation is legitimate, then can I also conclude that the negative entropy is 1-strongly convex w.r.t. $L_2$ norm, since $L_1$ norm is greater than equal to $L_2$ norm?