Concentration and Correlation for Magnitudes of Gaussian Vectors

Question

Suppose we have a large collection of standard normal random variables $a_i\in\mathbb{R}^n$. We know by standard concentration results that if we take $m \geq C\left(t/\epsilon\right)^2n$ samples, then with probability greater than $1-\exp\left(-ct^2n\right)$ we have $$ \|\frac{1}{m}\sum_{i=1}^ma_ia_i^T-Id\|_{op} < \epsilon $$ where $Id$ is the $n\times n$ identity matrix.

This implies that for any $u\in S^{n-1}$ we have $$ |\sum_{i=1}^m(a_i^Tu)^2-m|<m\epsilon $$ so we can think of the map from the unit sphere in $\mathbb{R}^n$ to the $m\epsilon$-neighborhood of the simplex at height $m$ in $\mathbb{R}^m$ $$ g(u):S^{n-1}\rightarrow \mathcal{K}_m + (1+m\epsilon)B_1(0) $$ where $u\rightarrow \left((a_1^Tu)^2,(a_2^Tu)^2,...,(a_m^Tu)^2\right)$and $\mathcal{K}_m := \left\{v\in\mathbb{R}_+^m : \sum_{k} v_k = m\right\}$ is the simplex.

Now take $\alpha<1$ to be some scale parameter and consider the event $E_u$ defined by $$ \sum_{i=1}^m a_{i1}^2(a_i^Tu)^2 < \alpha \sum_{i=1}^m a_{i2}^2(a_i^Tu)^2. $$ or, $$ \langle g(e_1), g(u) \rangle < \alpha \langle g(e_2), g(u) \rangle. $$ Intuitively this says that in the direction of $u$ there is some bias for $a_{i2}^2$ being large relative to $a_{i1}^2$.

My question is this: Assuming our concentration of the variance/covariance matrix, if we choose $\epsilon$ small enough relative to $\alpha$, and possibly requiring logarithmically more samples can we show that $$ \mathbb{P}\left[\bigcup_{u\in S^{n-1}} E_u\right] < \exp\left(-Cn\right) $$ for some $C$ which only depends on $\alpha$?

Thoughts: We can assume the points actually lie on the simplex: if we can prove exponential concentration there of the form $\exp(-Cm)$, then we pick up a factor of $$(1+ m\epsilon)^m = \exp\left(m\log(1+ m\epsilon)\right)$$ which might require $O(n\log n)$ samples instead.

In this scenario the worst case occurs whenever $g(e_2)=g(u)$ and we can imagine taking $g(u)$, scaling it down by $\alpha$, looking at the tangent hyperplane to the sphere at the point $\alpha g(u)$ and measuring the portion of the simplex which lies below this hyperplane, where we are measuring in the pushforward measure induced by the Gaussian.

At the barycenter of this simplex, the intersection of the simplex with this halfspace is empty. If we imagine moving $g(u)$ around the barycenter slightly, the intersection occurs around vertices of the simplex, which should have exponentially small probability. This suggests to me the total probability will be exponentially small in $m$ and thus $n$.

Answer 1

In case anyone is interested in situations like this, the answer is yes. The proof relies on an $\epsilon$-perturbation of the following lemma:

Suppose $w,x,y\in\mathbb{R}^m_+$ are three vectors on the probability simplex which satisfy $$ \langle w, x \rangle < \alpha\langle w, y\rangle $$ for some $\alpha < 1$. Then there exists a coordinate $k^*$ such that $$ x_{k^*} \geq 1-\alpha. $$

In my original notation, we apply this lemma to the vectors $g(u)/m, g(e_1)/m$, and $g(e_2)/m$ and find that for reasonable choices of $\alpha$, $g(e_1)=a_{i1}^2>(1-\alpha)m$ which occurs with probability less than $e^{-cm}$. Consequently, for each fixed $u\in S^{n-1}$ the existence of such a vector occurs with probability less than $me^{-cm}\leq e^{-cm/2} < e^{-Cn}$ and an $\epsilon$-net argument on the sphere produces the desired conclusion.