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

1 Answer 1

5
$\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$
3
  • $\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
    Commented Jan 24, 2020 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$ Commented Jan 24, 2020 at 2:37
  • $\begingroup$ OK, fair enough. $\endgroup$
    – passerby51
    Commented Jan 24, 2020 at 2:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.