Empirical approximation of the gaussian distribution in ${\mathbb{R}}^d$

Abstract

Let $G_1,\dots ,G_m$ be independent copies of the standard gaussian random vector in ${\mathbb{R}}^d$. We show that there is an absolute constant $c$ such that for any $A\subset S^{d-1}$, with probability at least $1-2\exp (-c\hat{I}”m)$, for every $t\in \mathbb{R}$, \[ \sup_{x \in A} \left| \frac{1}{m}\sum_{i=1}^m 1_{ \{\langle G_i,x\rangle \leq t \}} - \mathbb{P}(\langle G,x\rangle \leq t) \right| \leq Δ+ σ(t) \sqrtΔ. \] Here $\ddot{I}ƒ(t)$ is the variance of $1_{\{⟨G,x⟩\le t\}}$ and $\hat{I}”\ge \hat{I}{”}_0$, where $\hat{I}{”}_0$ is determined by an unexpected complexity parameter of $A$ that captures the set's geometry (Talagrand's ${\hat{I}}_1^3$ functional). The bound, the probability estimate, and the value of $\hat{I}{”}_0$ are all (almost) optimal. We use this fact to show that if $\hat{I}“={\sum }_{i=1}^m⟨G_i,x⟩e_i$ is the random matrix that has $G_1,\dots ,G_m$ as its rows, then the structure of $\hat{I}“(A)=\{\hat{I}“x:x\in A\}$ is far more rigid and well-prescribed than was previously expected.