17
$\begingroup$

Suppose $X_1, X_2, \ldots, X_n$ are independent and each has the same distribution with a sub-exponential random variable $X$ (for example, $X$ is the square of a standard normal Gaussian variable). Can I obtain a concentration inequality for the square of sub-exponential $X_i$, say,

$$\mathbb{P}\left( \frac{1}{n} \left( X_1^2+\cdots+X_n^2 \right) \ge \mathbb{E}\left[X^2\right] + t \right) \le C \exp\left( - n \cdot \min\left( C_1 t^2, C_2 t, C_3 \sqrt{t} \right) \right),$$

where $C, C_1, C_2, C_3$ are constants?

This problem arises in my research.


Remark:

Actually, for i.i.d. sub-Gaussian random variables $Y_i\ (i=1,\ldots,n)$, I knew that

$$\mathbb{P}\left( \frac{1}{n} \left(Y_1+\cdots+Y_n\right) \ge \mathbb{E}\left[Y\right] + t \right) \le \exp\left( - n\cdot C_1 t^2 \right).$$

Besides, since $Y_i^2\ (i=1,2,\ldots,n)$ are sub-exponential, I also knew that

$$\mathbb{P}\left( \frac{1}{n} \left(Y_1^2+\cdots+Y_n^2\right)\ge \mathbb{E}\left[ Y^2 \right] + t \right) \le \exp\left( - n\cdot \min(C_1 t^2, C_2 t) \right).$$

These two inequalities can be proved by a Chernoff bound, since the moment generating functions of $Y$ (sub-Gaussian) and $Y^2$ (sub-exponential) both exist.

However, I want to know whether there is an inequality like

$$\mathbb{P}\left( \frac{1}{n} \left( Y_1^4+\cdots+Y_n^4 \right) \ge \mathbb{E}\left[Y^4\right] + t \right) \le C \exp\left( - n \cdot \min\left( C_1 t^2, C_2 t, C_3 \sqrt{t} \right) \right),$$

even though the moment generating function of $Y^4$ (square of sub-exponential) does not exist.

$\endgroup$
9
  • $\begingroup$ Have you checked Eq. (2.20), on p.20 of this? ["High-dimensional statistics: A non-asymptotic viewpoint," by M. Wainwright. Chapter 2, 2015.]; or Proposition 5.16 of these notes ["Introduction to the non-asymptotic analysis of random matrices", Roman Vershynin, 2011] $\endgroup$
    – Clement C.
    Feb 13, 2016 at 2:52
  • $\begingroup$ For the square of a standard Gaussian r.v., which is subexponential with parameters $(2,4)$, you should also have a look at Examples 2.4 and 2.5 of the first reference given. $\endgroup$
    – Clement C.
    Feb 13, 2016 at 3:02
  • $\begingroup$ @ClementC. Thank you very much for your reponse! I guess that you meant there actually "exists" a concentration inequality for sub-exponential variables. However, what I wonder is whether there exists an inequality for "the square of sub-exponential variables". See my remark above, edited just know. $\endgroup$
    – elimpalm
    Feb 13, 2016 at 7:25
  • 3
    $\begingroup$ No. $P(\frac {X_1^2}n\ge t)=\Omega(\exp(-\lambda \sqrt t\sqrt n))$. Once your variable is strongly not-sub-exponential, the max of the sum is achieved for a single large deviation probability of which no longer scales as $\exp(-\alpha n)$. $\endgroup$
    – A.S.
    Feb 16, 2016 at 23:40
  • 2
    $\begingroup$ Having said that, you should be able to find a $\exp(-C\sqrt n \sqrt t)$ type of bound with some polynomial pre-factor. $\endgroup$
    – A.S.
    Feb 16, 2016 at 23:54

1 Answer 1

8
+50
$\begingroup$

No. For non-negative i.i.d. $Y_i$, $$P(Y_1\ge (\mu+t)n)\le P\Bigg(\sum_{i=1}^n Y_i\ge (\mu+t)n\Bigg)\le\exp(-nf(t))$$ implies that $Y_1$ is sub-exponential and a square of a sub-exponential is not guaranteed to be sub-exponential.

However you can obtain $$P(X_1^2+\dots+X_n^2>nt)\sim nP(X_1^2>nt)=n\exp(-\lambda\sqrt {nt})$$ for $X_i\sim \exp(\lambda)$ which you can extend to all subexponential $X_i$ that have exponential tails.

$\endgroup$
5
  • 2
    $\begingroup$ How do you get the bound for the squared exponential distribution? $\endgroup$ Dec 12, 2018 at 20:59
  • 1
    $\begingroup$ Could you please provide more details on the $P(X_1^2+\cdots+X_n^2 > nt) \sim nP(X_1^2>nt)$ part? I'm trying to figure out the induction. Thanks! $\endgroup$
    – Tong He
    May 15, 2020 at 14:06
  • $\begingroup$ This is the known/standard fact from the general theory of heavy tailed distributions. Roughly, the sum is dominated by the heaviest one. $\endgroup$ Sep 13, 2020 at 20:07
  • $\begingroup$ i can not find this standard fact anywhere. Could you reference it please? Would be very helpful for my problem if this is true. $\endgroup$
    – crush3dice
    Jul 28, 2022 at 16:09
  • $\begingroup$ I found a source that supports the claim here : adamwierman.com/wp-content/uploads/2021/05/book-05-11.pdf Section 3.4. $\endgroup$
    – crush3dice
    Aug 9, 2022 at 13:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .