A concentration inequality with random normal distributions

914 Views Asked by At

Given a constant $C >0$ and $X \sim {\cal N}(\vec{\mu}, \Sigma_{d \times d})$ then do we have a good upperbound on the deviation probability, $\mathbb{P} [ \Vert X \Vert \geq C ]$ ?

Assume $\Sigma$ is a diagonal or even isotropic if that makes it tractable.

1

There are 1 best solutions below

5
On

Let $X':=X-\mu$. For $C'\equiv C-\|\mu\|_2>0$, there exists a constant $M>0$ s.t. \begin{align} \mathsf{P}(\|X\|_2>C)&\le\mathsf{P}(\|X'\|_2>C')\overset{(1)}{\le} 2\exp\left(-\frac{C'^2}{2\operatorname{tr}(\Sigma)}\right). \end{align}


Proof of $(1)$. Let $Q\Lambda Q^{\top}$ be the eigendecomposition of $\Sigma$. Then $\|X'\|_2\overset{d}{=}\|\Lambda^{1/2} Y\|_2$, where $Y\sim N(0,I_d)$, and for $y\ge 0$ and $s>0$, \begin{align} \mathsf{P}(\|\Lambda^{1/2} Y\|_2>y)&\le \mathsf{P}(\|\Lambda^{1/2}Y\|_1>y)\le e^{-sy}\prod_{i=1}^d\mathsf{E}e^{s\sqrt{\lambda_i}|Y_i|} \\ &\le 2e^{\frac{s^2}{2}\sum_{i=1}^d \lambda_i-sy}, \end{align} where $\lambda_1,\ldots,\lambda_d$ are the eigenvalues of $\Sigma$. Optimizing over $s$, one gets $$ \mathsf{P}(\|\Lambda^{1/2} Y\|_2>y)\le 2e^{-\frac{y^2}{2\sum_{i=1}^d\lambda_i}}=2e^{-\frac{y^2}{2\operatorname{tr}(\Sigma)}} \tag*{$\square$} $$