A paper I am currently reading seem to be using the bound $$ E_h\left[\inf_{\|z\|_{\infty}\leq t} \|z-h\|^2\right] \leq n\frac{1}{\pi}\frac1t e^{-t^2/2},$$ where $n$ is the dimension of the vector, and $h$ is a standard Gaussian random vector. I tried expanding the terms, but the $\inf$ seems to be hard to deal with. How should I derive this bound? Thanks.

  • $\begingroup$ what is $z$ and which vector's dimension is $n$? $\endgroup$ – Hayk May 21 at 12:13
  • $\begingroup$ The term in the expectation is the minimum distance between a Gaussian random variable $h$ and a vector $z$ whose each of the entries are less than $t$ in magnitude. Now, consider two cases, $\| h \|_{\infty} \leq t$ and $\| h \|_{\infty} > t$. Try finding out the inner expression for these two cases and then use tail bounds to find the expectation. I think that should help. $\endgroup$ – sudeep5221 May 21 at 12:40
  • $\begingroup$ @Hayk Both the dimension of $z$ and $h$ are $n$, and $z$ is the vector you take the inf over. $\endgroup$ – GavinZZZ May 21 at 13:12

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.