0

Let $p \in (1,2]$ and also let $X = \mathbb{R}^n$. I want to calculate a gradient of a following function (i.e. $\nabla S$)

$$S(y) = \sup_{x \in X} \{ \langle x, y \rangle - \frac{1}{2(p-1)} \cdot ||x||_{p}^2 \}$$

My problem is that that $\sup$ is really irritant for me.

Particularly, I would like to use $p = 1+ \frac{1}{d}$ where $d>0$ is sufficiently big.

Can anyone help me?

Applicable Math
  • 327
  • 2
  • 10
  • Let me mention that S(y) corresponds to the legendre transformation of $\frac{1}{2(p-1)} ||x||_{p}^2$ – Applicable Math Apr 19 '17 at 22:27
  • 1
    You really need to calculate $S$ explicitly first. Derivatives and suprema don't mix well at all. – Chappers Apr 19 '17 at 22:43
  • Because the squared euclidean norm is self-dual, when $p = 2$ we have $s(y) \equiv \frac{1}{2}|y|_2^2$ and so $\nabla S(y) \equiv y$. In general $S_p(y)$ will not be differentiable... – dohmatob Apr 20 '17 at 13:55
  • It turns out that you can compute $S_p(y)$ explicitly for any $p > 1$. Also, if you replace the square by any real number > 1, you'll still obtain a closed-form formula. In any case, you problem reduces to the studying the differentiability of squares of general norms on euclidean spaces. See my answer below. – dohmatob Apr 20 '17 at 14:18

1 Answers1

1

Because the squared euclidean $\ell_2$ norm is self-dual (see why here), we have $S_2(y) \equiv \frac{1}{2}\|y\|_2^2$ and so $\nabla S_2(y) \equiv y$.

In general, $S_p(y)$ will not be differentiable at the origin. Indeed, extending the above idea for the $p=2$ case, it's not difficult to show (e.g see this wikipedia page, in french) that

$$(\frac{1}{2}\|.\|_p^2)^* = \frac{1}{2}\|.\|_q^2, $$ where $q > 1$ is the harmonic conjugate of $p$, i.e $1/p + 1 / q = 1$.

Thus, in case $p \in (1, 2)$, your problem is reduced to studying the differentiability of a squared norm $\|.\|_q^2$ , with $q := p/(p-1) > 2$. Note that this is differentiable everywhere except perhaps at the origin, where you'll need to administer special treatment...

dohmatob
  • 9,535
  • I think I understood what you're talking to me. But what I don't understand now is the fact that you're taking coefficient equal to $\frac{1}{2}$ (I suppose that this is due to the generalization that you've done above)

    If I take $p = 1 + \frac{1}{\ln{d}}$, I obtain $q = 1 + \ln{d}$. So, what would be $( \frac{k}{2(p-1)} || x||{p}^2 )^*$? It would be $\frac{1}{2(q-1)} ||x||{q}^2$?

    I don't get why the coefficient that you have calculated (which accompanies to $||x||_{p}^2$ remains as constant, without depending on $p$.

    Thank you...

     – Applicable Math Apr 20 '17 at 15:36
  • I did it finally. Thanks. – Applicable Math Apr 20 '17 at 15:49
  • Just in case, the scaling property of the Fenchel-Legendre transform: $(\alpha f)^(x) \equiv \alpha f^(x/\alpha)$ for any nonzero real $\alpha$. Thus in your problem, it suffices to study the scaled version of $S_p$ (i.e without the abnoxious $1/(p-1)$ coefficient... – dohmatob Apr 20 '17 at 18:26
  • Yes haha... my problem was that I never had seen legendre transform in my entire life... Thanks :) – Applicable Math Apr 20 '17 at 19:50
  • Excuse me. Doing what you told me, I've got this: $$\left( \frac{1}{p-1} \frac{1}{2} || x||{p}^2 \right)^* & = \frac{1}{p-1} \left( \frac{1}{2} \left\Vert \frac{x}{\frac{1}{p-1}}\right\Vert{p} ^2 \right)^*
    \ & = \frac{1}{p-1} \left( \frac{(p-1)^2}{2} \left\Vert x \right\Vert_{p} ^2 \right)^* \ & = (p-1) \cdot \left( \frac{1}{2} \left\Vert \frac{x}{(p-1)^2} \right\Vert \right)^* \ & = (p-1) \cdot \left( \frac{1}{2(p-1)^4} ||x||_{p}^2 \right)^*$$

    Which is not seems to be something useful.

    Can you help me just a little bit more please?

     – Applicable Math Apr 24 '17 at 02:26
  • Excuse me. Doing what you told me, I've got this:

    $\left( \frac{1}{p-1} \frac{1}{2} || x||{p}^2 \right)^* = \frac{1}{p-1} \left( \frac{1}{2} \left\Vert \frac{x}{\frac{1}{p-1}}\right\Vert{p} ^2 \right)^* $

    $= \frac{1}{p-1} \left( \frac{(p-1)^2}{2} \left\Vert x \right\Vert_{p} ^2 \right)^* = (p-1) \cdot \left( \frac{1}{2} \left\Vert \frac{x}{(p-1)^2} \right\Vert \right)^* $

     – Applicable Math Apr 24 '17 at 02:28
  • $ = (p-1) \cdot \left( \frac{1}{2(p-1)^4} ||x||{p}^2 \right)^* \left( \frac{1}{p-1} \frac{1}{2} || x||{p}^2 \right)^* = \frac{1}{p-1} \left( \frac{1}{2} \left\Vert \frac{x}{\frac{1}{p-1}}\right\Vert_{p} ^2 \right)^* $ ; $ = \frac{1}{p-1} \left( \frac{(p-1)^2}{2} \left\Vert x \right\Vert_{p} ^2 \right)^* = (p-1) \cdot \left( \frac{1}{2} \left\Vert \frac{x}{(p-1)^2} \right\Vert \right)^* $ ; $= (p-1) \cdot \left( \frac{1}{2(p-1)^4} ||x||_{p}^2 \right)^*$

    Which is not seems to be something useful. Can you help me just a little bit more please?

     – Applicable Math Apr 24 '17 at 02:28
  • $S_p(x) := \left(\dfrac{1}{2(p-1)}|.|_p^2\right)(x) = \dfrac{1}{p-1}|(p-1)x|_q^2 = (p-1)|x|_q^2$ – dohmatob Apr 24 '17 at 08:07