3

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$?

Armen Aghajanyan
  • 233
  • if $f(X_1, \dots, X_n) \sim \mathcal{N}(0, 1)$ doesn't it mean that $f(\cdot)$ is linear with proper normalization? – tortue Aug 15 '18 at 21:31
  • 1
    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. – tortue Aug 15 '18 at 21:38
  • I'm not sure what you mean, it's possible to have a larger Lipschitz constant that fulfills the constraint. Could you please explain? – Armen Aghajanyan Aug 15 '18 at 22:02
  • what metric are you using for Lipschitz continuity on $\mathbf{R}^n$? – tortue Aug 16 '18 at 13:40
  • I'm using euclidean norm induced metric. $d(x,y)=||x-y||$ – Armen Aghajanyan Aug 16 '18 at 16:28
  • How have you concluded that $e^{-t^2/2} \leq e^{-t^2/2L^2}$? $\lambda$ is chosen to minimise $e^{\lambda^2/2 - \lambda t}$ and this isn't necessarily the same thing as being the best constant $c$ such that $\mathbb{P}(f(X_1,\dots,X_n) \geq t) \leq e^{-t^2/2c}$ as far as I can see, which is what I think you want for your claim. – Rhys Steele Aug 17 '18 at 22:18
  • Shouldn't the lower bound be 1 from (https://math.stackexchange.com/questions/1586624/bound-on-variance-of-function-of-a-random-variable). Also I pick the $\lambda$ which gives me the tightest bound which is equivalent to picking the best Lipschitz. Could you please expand on what you mean? – Armen Aghajanyan Aug 17 '18 at 22:21
  • No, you pick $\lambda$ to optimise the bound you get from this particular application of Markov's inequality. This is not the same thing as picking the best Lipschitz constant. It could be that the best bound you can get from this application of Markov's inequality is not the best bound of the form $e^{-at^2}$ you could get in general. (btw in future you should type e.g. @RhysSteele in your comment so I get a notification that you've replied) – Rhys Steele Aug 22 '18 at 16:39
  • @RhysSteele Interesting. Thank you. Any ideas on how to upper bound Lipschitz constant? – Armen Aghajanyan Aug 23 '18 at 21:32

0 Answers0