Expectation of top-K selection of squared Gaussian random variables

Question

Let us have $$ Z = [z_1, z_2, \dots, z_n], $$ where $z_i \sim N(0, \sigma^2)$ and are iid. Additionally, consider $$ X_k := \{ x \in \{0, 1\}^n : e^T x = k \} $$ If $Y = \max_{X \in X_k} |Z^T X|^2,$ could you suggest an upper bound for $\mathbb{E}(Y)$ and a concentration inequality $$\operatorname{Pr}(|Y - \mathbb{E}(Y)|>t) < f(t)\;? $$

Answer 1

Let $Z \sim \mathcal{N}(0,\sigma^2 I_n)$ be an $n$-dimensional Gaussian vector with independent $\mathcal{N}(0,\sigma^2)$ components. Consider the family of binary vectors in $\mathbb{R}^n$ with exactly $k$ ones, denoted by $\mathcal{X}_k = \{x \in \{0,1\}^n : |x|_1 = k\}$, where $1 \leq k \leq \lfloor n/2 \rfloor$. Define $Y = \sup_{X \in \mathcal{X}_k} |\langle Z, X \rangle|^2$.

Now consider the vector $x \in \mathbb{R}^n$ and define $|x|_1 = \sum_{i=1}^n |x_i|$ and $\|x\|_2 = \sqrt{\sum_{i=1}^n x_i^2}$. The set $\mathcal{X}_k$, equipped with the Euclidean metric $d(x,y) = \|x-y\|_2$, has a diameter of $\sqrt{2k}$. For each $X \in \mathcal{X}_k$, let $Z_X = \langle Z,X\rangle = \sum_{i=1}^n Z_i x_i$ which follows a $\mathcal{N}(0,\sigma^2 k)$ distribution only when $X$ has $k$ ones and the rest are zeros. We also define the Gaussian process $G(X) = \sum_{i=1}^n w_i x_i$ where $w_i$ are i.i.d. $\mathcal{N}(0,\sigma^2)$ variables.

Considering any two vectors $X, X' \in \mathcal{X}_k$, the covariance $\mathrm{Cov}(Z_X, Z_{X'}) = \sigma^2 \sum_{i=1}^n x_i x'_i$, which is equal to $\sigma^2 k$ if and only if $X$ and $X'$ overlap completely in their nonzero entries. Similarly, $\mathrm{Cov}(G(X), G(X')) = \sigma^2 \sum_{i=1}^n x_i x'_i$. Therefore, for any $X, X' \in \mathcal{X}_k$, $\mathrm{Cov}(Z_X, Z_{X'}) = \mathrm{Cov}(G(X), G(X'))$.

By applying the Sudakov-Fernique inequality, which is applicable since $\mathcal{X}_k$ is a finite subset of Euclidean space and the Gaussian covariances obey the relationship described, we have:

$$ \mathbb{E}[\sup_{X \in \mathcal{X}_k} Z_X] \leq \mathbb{E}[\sup_{X \in \mathcal{X}_k} G(X)] $$

Using the Dudley entropy integral bound with an absolute constant $K > 0$ and noting that $|\mathcal{X}_k| = {n \choose k} \leq (\frac{en}{k})^k$, we obtain:

$$ \mathbb{E}[\sup_{X \in \mathcal{X}_k} G(X)] \leq K\int_0^{\sqrt{2k}} \sqrt{\log |\mathcal{X}_k|\epsilon^{-1}} d\epsilon \leq C_1 \sigma \sqrt{2k\log(\frac{en}{k})} < \infty $$

for some universal constant $C_1 > 0$, confirming that $\mathbb{E}[Y]$ is indeed finite.

To derive the concentration inequality, we employ the Borell-TIS (Tsirelson-Ibragimov-Sudakov) inequality. This inequality states that if $Y$ is a centered Gaussian process, then for any $t > 0$,

$$ \mathbb{P}(|Y - \mathbb{E}[Y]| \geq t) \leq 2\exp\left(-\frac{t^2}{2\sigma^2_Y}\right) $$

where $\sigma^2_Y$ is the supremum of the variance of the process. In our context, $Y$ is the supremum of a Gaussian process indexed by vectors in $\mathcal{X}_k$, and $\sigma^2_Y = \sigma^2 k$ reflects the maximum variance of $Z_X$ across all $X \in \mathcal{X}_k$.

The refinement considers the cardinality of $\mathcal{X}_k$. By employing a union bound over the elements of $\mathcal{X}_k$, we adjust the concentration inequality to account for the multiple comparisons being made. This leads to:

$$ \mathbb{P}(|Y - \mathbb{E}[Y]| > t) \leq 2|\mathcal{X}_k|e^{-\frac{t^2}{2\sigma^2 k}} $$

So the probability of a large deviation decreases exponentially with $t^2$, but the rate of decrease is moderated by the cardinality of $\mathcal{X}_k$.