Let's say $X$ is a vector space with inner product $\langle \cdot,\cdot\rangle$ and induced norm $\|\cdot\|$. Then for a scalar $\theta > 0$ we define $\langle \cdot,\cdot\rangle_{\theta} := \theta\langle \cdot,\cdot\rangle$, and therefore $\|\cdot\|_{\theta} = \theta^{\frac{1}{2}}\|\cdot\|$.

Suppose that for a function $f:X \to \mathbb{R}$ differentiable on $X$ the following Lipschitz condition holds: $$ \|\nabla f(x) - \nabla f(x')\|_{*} \leq C\|x - x'\| \quad \forall x, x' \in X \quad (1)$$ where $\|\cdot\|_*$ denotes the dual norm $$ \|\cdot\| := \max_{\|x'\|=1} \{\langle x, x' \rangle\}$$. What can I say about the Lipschitz condition with respect to $\|\cdot\|_{\theta}$? I'm reading that one can get the same condition $(1)$ with constant $C_{\theta} = \theta^{-1}C$, but on my math I keep getting that it holds with the same constant... What am I doing wrong here?

  • $\begingroup$ How is the dual norm associated to $\lVert\,\cdot\,\rVert_\theta$ related to $\lVert\,\cdot\,\rVert_\ast$? $\endgroup$ – Daniel Fischer Jul 24 '15 at 14:28
  • $\begingroup$ Well, the text isn't clear. I assumed that it was refering to $(1)$ with the dual norm with respect to $\|\|_{\theta}$, such as $(\|\cdot\|_{\theta})_{*} := \max_{\|x'\|_{\theta}=1}\langle x,x' \rangle_{\theta}$, but even then I get that $(1)$ holds with the same $C$... $\endgroup$ – karlabos Jul 24 '15 at 14:40

The dual norm associated to $\lVert\,\cdot\,\rVert_\theta$ satisfies $\lVert\,\cdot\,\rVert_{\theta\ast} = \theta^{-1/2}\lVert\,\cdot\,\rVert_\ast$:

$$\lVert\lambda\rVert_{\theta\ast} = \sup_{x\neq 0} \frac{\lvert\lambda(x)\rvert}{\lVert x\rVert_\theta} = \sup_{x\neq 0} \frac{\lvert\lambda(x)\rvert}{\theta^{1/2}\lVert x\rVert} = \theta^{-1/2}\sup_{x\neq 0} \frac{\lvert\lambda(x)\rvert}{\lVert x\rVert} = \theta^{-1/2}\lVert\lambda\rVert_\ast.$$

Thus we obtain

$$\lVert\nabla f(x) - \nabla f(x')\rVert_{\theta\ast} = \theta^{-1/2}\lVert\nabla f(x) - \nabla f(x')\rVert_\ast \leqslant \theta^{-1/2} C\lVert x-x'\rVert = \theta^{-1/2}C \theta^{-1/2}\lVert x-x'\rVert_\theta,$$

which means we have the Lipschitz constant $\theta^{-1}C$, as claimed.

  • $\begingroup$ I see. But is the definition of dual norm you used equivalent to the one the text gave? It gave in terms of the inner product, or are you assuming you that $\lambda(x)$ is $\langle \cdot, x \rangle$? But then we are evaluating the norm on a vector of $X$ and not on a function... $\endgroup$ – karlabos Jul 24 '15 at 15:28
  • $\begingroup$ You might be missing that $|\lambda(x)|_\theta^2 = \theta|\lambda(x)|^2$. $\endgroup$ – Yuval Filmus Jul 24 '15 at 15:33
  • $\begingroup$ @karlabos The definition of the dual norm is not in terms of the inner product (can't be, since the two arguments belong to different spaces), it is in terms of the dual pairing $\langle\,\cdot\,,\,\cdot\,\rangle \colon X^\ast \times X \to \mathbb{R}$. That's why I prefer to denote inner products with $\langle v\mspace{-2mu}\mid\mspace{-2mu}w\rangle$, then you can't confuse inner products and dual pairings. And then $\sup \lvert \{\langle \lambda, x\rangle\rvert : \lVert x\rVert = 1\}$ is an equivalent definition. $\endgroup$ – Daniel Fischer Jul 24 '15 at 15:34
  • $\begingroup$ @YuvalFilmus $\lambda (x) \in \mathbb{R}$, and we use the ordinary absolute value there (unless specified otherwise). $\endgroup$ – Daniel Fischer Jul 24 '15 at 15:35

We have $\|x-x'\| = \theta^{-1/2} \|x-x'\|_\theta$. The Lipschitz condition shows that $$ \|\nabla f(x) - \nabla f(x')\|_* \leq C\theta^{-1/2} \|x-x'\|_\theta. $$ So for all $z$ such that $\|z\|=1$, $$ \langle \nabla f(x) - \nabla f(x'), z \rangle \leq C\theta^{-1/2} \|x-x'\|_\theta. $$ If $\|w\|_\theta=1$ then $\|w\|=\theta^{-1/2}$, and so $\|\theta^{1/2}w\|=1$, implying $$ \langle \nabla f(x) - \nabla f(x'), \theta^{1/2}w \rangle \leq C\theta^{-1/2} \|x-x'\|_\theta. $$ In other words, for all $\|w\|_\theta = 1$, we have $$ \langle \nabla f(x) - \nabla f(x'), w \rangle \leq C\theta^{-1} \|x-x'\|_\theta. $$ This implies that for all $\|w\|_\theta = 1$, $$ \theta^{-1} \langle \nabla f(x) - \nabla f(x'), w \rangle_\theta \leq C\theta^{-1} \|x-x'\|_\theta. $$ Cancelling $\theta^{-1}$, we conclude that $$ \|\nabla f(x) - \nabla f(x'), w\|_{\theta,*} \leq C \|x-x'\|_\theta. $$ So it seems you are correct.

  • $\begingroup$ That's more or less what I did. By the other hand Daniel gave the answer above with the constant $C\theta^{-1}$... Now I am confused $\endgroup$ – karlabos Jul 24 '15 at 15:29
  • $\begingroup$ See Daniel's answer. Apparently you shouldn't use $\langle \cdot, \cdot \rangle_\theta$. $\endgroup$ – Yuval Filmus Jul 24 '15 at 15:36

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.