Let $X_1,...,X_n$ be i.i.d $\mathcal{N}(0,1)$ and let $f: \mathbb{R}^n \rightarrow \mathbb{R}$ be a $L$-Lipschitz function. I'm trying to prove that if $f(X_1,...,X_n) \sim \mathcal{N}(0,1)$ then $f$ is 1-Lipschitz.

(Tsirelson-Ibragimov-Sudakov 1976) Let $X_1,...,X_n$ be i.i.d $\mathcal{N}(0,1)$ and let $f: \mathbb{R}^n \rightarrow \mathbb{R}$ be a $L$-Lipschitz function with respect to the Euclidean norm. Then \begin{equation} \mathbb{P}\left[f(X_1,...,X_n) - \mathbb{E}\left[f(X_1,...,X_n)\right] \geq t\right] \leq e^{\frac{-t^2}{2L^2}} \end{equation} If $f(X_1,...,X_n) \sim \mathcal{N}(0,1)$ then the expectation of $f=0$ and by the markov inequality we have \begin{align} \mathbb{P}\left[f(X_1,...,X_n) \geq t\right] &=\\ \inf_{\lambda>0} \mathbb{P}\left[\exp(\lambda f(X_1,...,X_n)) \geq e^{\lambda t}\right] &\leq\\ \inf_{\lambda>0} e^{-\lambda t}\mathbb{E}\left[\exp(\lambda f(X_1,...,X_n))\right] &=\\ \inf_{\lambda>0} e^{\frac{\lambda^2}{2} - \lambda t} = e^{\frac{-t^2}{2}} \end{align} after making the optimal choice $\lambda = t$. We now can rewrite our Lipschitz bound as: \begin{equation} \mathbb{P}\left[f(X_1,...,X_n) \geq t\right] \leq e^{\frac{-t^2}{2}} \leq e^{\frac{-t^2}{2L^2}} \end{equation} Therefore \begin{align} ||f||_L \geq 1 \\ \end{align}

This is as far as I got. Is there a way to upper bound the $||f||_L$?

  • $\begingroup$ if $f(X_1, \dots, X_n) \sim \mathcal{N}(0, 1)$ doesn't it mean that $f(\cdot)$ is linear with proper normalization? $\endgroup$ – pointguard0 Aug 15 '18 at 21:31
  • 1
    $\begingroup$ nevertheless, you've proved that $\mathbb{P}[f(X_1, \dots, X_n) \ge t] \le e^{-\frac {t^2} 2}$ [not equal] yielding $L=1$, by definition. $\endgroup$ – pointguard0 Aug 15 '18 at 21:38
  • $\begingroup$ I'm not sure what you mean, it's possible to have a larger Lipschitz constant that fulfills the constraint. Could you please explain? $\endgroup$ – Armen Aghajanyan Aug 15 '18 at 22:02
  • $\begingroup$ what metric are you using for Lipschitz continuity on $\mathbf{R}^n$? $\endgroup$ – pointguard0 Aug 16 '18 at 13:40
  • $\begingroup$ I'm using euclidean norm induced metric. $d(x,y)=||x-y||$ $\endgroup$ – Armen Aghajanyan Aug 16 '18 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.