Tail bound for the maximum of a reduced-rank Gaussian random vector

197 Views Asked by At

Suppose that $X_i, i=1,...,n$ are Gaussian random variables, each with mean equal to $0$ and variance equal to $1$. However, suppose that their covariance matrix is reduced rank (assume that such a rank is $r<<n$). I am interested in characterizing the tail behavior of the maximum of these random variables, i.e. $\Pr(Z>t)$, where $Z=\max_{1\le i\le n} |X_i|$.

Consider the following conservative tail bound obtained under independence: $$\Pr(Z>t)\le n\cdot \Pr(|X_i|>t)\le n\cdot e^{-t^2/2},$$ which implies $Z=O_p(\sqrt{2\log n})$.

Is there a way to sharpen this bound by using the reduced-rank property of the covariance matrix of the $X$'s?

1

There are 1 best solutions below

1
On

Let's say $x\sim \mathcal{N}(0,\Sigma)$ is the Gaussian random vector of dimension $n$, where $\Sigma$ is a covariance matrix of rank $r<<n$. In particular, as $\Sigma$ is positive semi-definite, we can write $\Sigma=AA^T$, where $A$ is an $n\times r$ matrix, and therefore $x=Ay$, where $y\sim \mathcal{N}(0,I_r)$ is an $r$-dimensional standard Gaussian with independent entries. Moreover, if the diagonal of $\Sigma$ is identically $1$ as you specify, then evidently the $i$th row $A_i\in \mathbb{R}^r$ has length $1$.

It is known via standard Gaussian concentration arguments that \begin{equation} \mathbb{P}(\sup_i x_i -\mathbb{E}[\sup_i x_i]>\lambda)\leq \exp\bigg(\frac{-\lambda^2}{2\sup_i \mathbb{E}[x_i^2]}\bigg)=\exp\bigg(\frac{-\lambda^2}{2}\bigg), \end{equation} so in some sense, your question amounts to determining good bounds for $\mathbb{E}[\sup_i x_i]=\mathbb{E}[\sup_i \langle A_i,y\rangle]$. This in turn has been found to be essentially completely captured by the theory of majorizing measures, but is probably better understood using the notion of covering numbers. Think of the set of vectors $\{A_i\}_{i=1}^n\subseteq \mathbb{S}^{r-1}$. It turns out that $\mathbb{E}[\sup_i x_i]$ is tightly related to the complexity of this set, in terms of how many small balls are needed to cover this set. Imagine that all the $A_i$ are close to equal; then a single, very small ball can cover all of them, which the theory will show makes $\mathbb{E}[\sup_i x_i]$ small, as even though this is a supremum over a set of size $n$, all of the Gaussians are essentially the same. On the other hand, if the $A_i$ are very spread out, then you need many small balls to cover them; in the most extreme case, suppose that the $A_i$ form nearly a net of $\mathbb{S}^{r-1}$; then $\sup_i \langle A_i,y\rangle\approx \|y\|_2$, and this has expectation $\approx \sqrt{r}$.

So, the long answer is it depends on how far spread out the rows of $A$ are. I'd recommend taking a look at Chapters 5 and 6 of van Handel's lecture notes.