3
$\begingroup$

Recently I found a concentration inequality for infinite dimensional Gaussian r.v.s in this paper. Specifically, Lemma 4 on page 307 states (without a proof) that

There exists a universal constant $M$ such that for each Banach space valued Gaussian random variable $X$ (having zero mean): $$ \mathsf{P}(\|X\|\ge u)\le \exp\left(-\frac{u^2}{M\mathsf{E}\|X\|^2}\right). $$

The authors refer to an older paper which is not available online. So I'm wondering how one proves this result.


As a first step, applying the generic Chernoff bound, one gets $$ \mathsf{P}(\|X\|\ge u)\le e^{-su}\mathsf{E}e^{s\|X\|} $$ for any $s>0$. Then the desired inequality holds if $\mathsf{E}e^{s\|X\|}$ is bounded by $e^{Cs^2\mathsf{E}\|X\|^2}$.

$\endgroup$
  • $\begingroup$ See Lemma 3.1 in the Ledoux-Talagrand book, available online. $\endgroup$ – Aryeh Kontorovich Jan 30 at 13:34
  • $\begingroup$ Indeed, but it’s a mean-zero random variable, so one should be able to control the median (using concentration)?.. $\endgroup$ – Aryeh Kontorovich Jan 30 at 14:56
  • $\begingroup$ Yes, I see now. I thought it would be absorbed into the universal constant M. $\endgroup$ – Aryeh Kontorovich Jan 30 at 15:15
  • $\begingroup$ I tried to derive this bound for Gaussian vectors in $\mathbb{R}^d$. For $X\sim N(0,\Sigma)$, the best I could obtain so far is $$ \mathsf{P}(\|X\|_2\ge u)\le 2\exp(-u^2/(2\operatorname{tr}(\Sigma))), $$ and I don't see a way to get rid of the factor of $2$ before the exponent. $\endgroup$ – d.k.o. Jan 30 at 16:15
  • $\begingroup$ There's an unspecified universal constant $M$ in the OP -- doesn't that make any factor before the exponent meaningless? $\endgroup$ – Aryeh Kontorovich Jan 30 at 20:02
4
$\begingroup$

This inequality is false. E.g., consider the random vector $X_n:=(Z_1,\dots,Z_n)/\sqrt n$ in $\mathbb R^n$ with the Euclidean norm $\|\cdot\|$, where $Z_1,Z_2,\dots$ are independent standard normal random variables. Then $E\|X_n\|^2=1$ and, by the law of large numbers, $$\|X_n\|^2=\frac1n\,\sum_1^n Z_i^2\to1$$ in probability (as $n\to\infty$), so that $P(\|X_n\|\ge u)\to1$ for any $u\in(0,1)$. So, for any real constant $M>0$, any $u\in(0,1)$, and all large enough $n$ $$P(\|X_n\|\ge u)\not\le \exp\Big(-\frac{u^2}{M}\Big)=\exp\Big(-\frac{u^2}{M\,E\|X_n\|^2}\Big).$$


On the other hand, according to formula (3.5) in the Ledoux--Talagrand book, one has e.g. the inequality $$P(\|X\|\ge u)\le 4\exp\Big(-\frac{u^2}{8E\|X\|^2}\Big)$$ for $u\ge0$.

The constants here can be a bit improved by using Corollary 3, which states that $$P(\|X\|-E\|X\|\ge x)\le \exp\Big(-\frac{x^2}{2E\|X\|^2}\Big)\tag{1}$$ for $x\ge0$, which implies e.g. that $$P(\|X\|\ge u)\le\sqrt e\,\exp\Big(-\frac{u^2}{8E\|X\|^2}\Big)\tag{2}$$ for $u\ge0$.

Details on how to get (2) from (1): If $u^2<4E\|X\|^2$, then the upper bound on $P(\|X\|\ge u)$ in (2) is $>1$ and thus trivial. So, without loss of generality, $u^2\ge4E\|X\|^2\ge4(E\|X\|)^2$, so that $E\|X\|\le u/2$. Letting now $x:=u-E\|X\|\ge u/2$, we see that the left-hand of (1) becomes that of (2), and the right-hand of (1) is less than that of (2).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Interestingly, the same inequality is stated in another paper by Basu. $\endgroup$ – d.k.o. Jan 31 at 17:54
  • $\begingroup$ @Iosif Can you kindly explain how you went from Corollary 3 of your paper to this form in terms of u ? $\endgroup$ – gradstudent Feb 23 at 23:37
  • $\begingroup$ @d.k.o. : By "the same inequality", do you mean the false one? Maybe, this is how false results propagate. Hopefully, this omission of a constant factor does not affect most of the applications. $\endgroup$ – Iosif Pinelis Feb 24 at 0:58
  • $\begingroup$ @gradstudent : I have added details on how to get (2) from (1). $\endgroup$ – Iosif Pinelis Feb 24 at 0:59

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.