3
$\begingroup$

Consider a 1-Lipschitz function $f: \mathbb R^n \to \mathbb R$ satisfying the inequality \begin{align*} |f(x) - f(y)| \le \|x-y\|_2, \;\forall x,y \in \mathbb R^n. \end{align*} For $n \ge 2$, can we find a 1-Lipschitz function that saturates the above inequality on the average?

To make the notion of "on the average" precise, let $x$ and $y$ be independent standard Gaussian vectors, i.e., $x,y \sim N(0,I_n)$. One can show that $$\mathbb E \big|\|x\|_2 - \|y\|_2\big| \asymp 1.$$ while $$\mathbb E\|x-y\|_2 \asymp \sqrt{n}.$$ Is there a 1-Lipschitz function $f : \mathbb R^n \to \mathbb R$ such that $$\mathbb E|f(x) - f(y)| \asymp \sqrt{n}?$$ Here $\asymp$ means inequalities go in both directions up to constants.

A related question is determining the order of $$ \sup_{f \in \text{Lip}(1)}\mathbb E|f(x) - f(y)| $$ where $\text{Lip}(1)$ is the set of $1$-Lipschitz functions from $\mathbb R^n$ to $\mathbb R$.

$\endgroup$
  • 1
    $\begingroup$ What do you mean by $\|x\|$ as opposed to $\|x\|_2$? $\endgroup$ – Anthony Quas Jan 24 at 0:47
  • $\begingroup$ @AnthonyQuas, yes, the $\ell_2$ norm. $\endgroup$ – passerby51 Jan 24 at 2:22
  • $\begingroup$ All the norms are the $\ell_2$ norm. I have edited the question. $\endgroup$ – passerby51 Jan 24 at 2:32
3
$\begingroup$

There is no $1$-Lipschitz function $f\colon \mathbb R^n \to \mathbb R$ such that $$\mathbb E|f(x) - f(y)| \asymp \sqrt{n}.$$

Indeed, for any such function, by the Gaussian concentration for Lipschitz functions (see e.g. Theorem 2.4, page 31), $$P(|f(x)-Ef(x)|\ge t)\le2e^{-t^2/2}$$ for all $t\ge0$. So,
$$E|f(x)-Ef(x)|=\int_0^\infty P(|f(x)-Ef(x)|\ge t)\,dt\le\sqrt{2\pi},$$ and hence also $E|f(y)-Ef(x)|=E|f(y)-Ef(x)|\le\sqrt{2\pi}$, so that $$E|f(x)-f(y)|\le E|f(x)-Ef(x)|+E|f(y)-Ef(x)|\le2\sqrt{2\pi}=o(\sqrt n).$$

It also follows that $$\sup_{f\in\text{Lip}(1)}E|f(x) - f(y)|\asymp1.$$

$\endgroup$
  • $\begingroup$ Ah, you are right! How I did not notice that.... Now how about general sub-Gaussian distributions. I have updated the question. $\endgroup$ – passerby51 Jan 24 at 2:23
  • 1
    $\begingroup$ @passerby51 : If you have additional questions, please ask them in separate posts, especially when your original question has been fully answered. $\endgroup$ – Iosif Pinelis Jan 24 at 2:37
  • $\begingroup$ OK, fair enough. $\endgroup$ – passerby51 Jan 24 at 2:40

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.