Expectation of supremum of sub gaussians

Question

I am trying to prove Lemma 2.3 of ON THE SPECTRAL NORM OF GAUSSIAN RANDOM MATRICES, which states that

Let $X_1,\cdots,X_n$ be not necessarily independent random variables with $\mathbb{P}[X_i > x] \leq Ce^{-\frac{x^2}{C\sigma_i^2}}$, for all $x\geq 0$, i, where $C$ is a universal constant and $\sigma_i\geq 0$ are given. Then $\mathbb{E}[max_{1\leq i\leq n}X_i] \leq \max_{1\leq i\leq n}\sigma_i^\star\sqrt{\log(i+1)}$, where $\sigma_1^\star \geq \sigma_2^\star \geq\cdots\geq \sigma_n^\star$ is decreasing arrangement of $\sigma_1,\cdots,\sigma_n$.

As goes with the standard proof, we have

$\mathbb{E}[max_{1\leq i\leq n}X_i] = \int_0^{\infty}\mathbb{P}[max_{1\leq i\leq n}X_i > u]\,du = \int_0^{u_0} + \int_{u_0}^{\infty} \leq u_0 + \int_{u_0}^\infty C\sum_{i=1}^ne^{-\frac{u^2}{C\sigma_i^2}}\,du= u_0 + C\sum_{i=1}^n \int_{u_0}^\infty e^{-\frac{u^2}{C\sigma_i^2}}\,du$

This holds for any $u_0\geq 0$. Now using the fact that $\int_{u_0}^\infty e^{-\frac{u^2}{C\sigma_i^2}}\,du\leq \frac{C\sigma_i^2}{2u_0}e^{-\frac{u_0^2}{C\sigma_i^2}}$, the above expression is upper bounded by

$u_0 + \frac{C^2}{2u_0}\sum_{i=1}^n\sigma_i^2 e^{-\frac{u_0^2}{C\sigma_i^2}}$.

I am unable to pick suitable values for $u_0$ to bound the above exression. Any help would be great. Or maybe this is proved in different way?

Answer 1

$\newcommand\si\sigma$The inequality stated in that lemma is, not $$E\max_{1\le i\le n}X_i \le \max_{1\le i\le n}\si_i^\star\sqrt{\ln(i+1)}, \tag{0}\label{0}$$ but $$E\max_{1\le i\le n}X_i \lesssim \max_{1\le i\le n}\si_i^\star\sqrt{\ln(i+1)}, \tag{1}\label{1}$$ with the meaning of $\lesssim$ (apparently not explained in the paper) being apparently as follows: $A\lesssim B$ if $A\le cB$ for some real "constant" $c>0$. It is clear that (i) the constant $c$ in \eqref{1} must depend on the $C$ in the condition $P(X_i > x) \leq Ce^{-\frac{x^2}{C\si_i^2}}$ and (ii) for this reason, \eqref{0} will not hold in general.

Let us now prove \eqref{1}. As you noted, $$E\max_{1\le i\le n}X_i\le B:=u_0 + \frac{C^2}2\sum_{i=1}^n\frac{\si_i^2}{u_0} e^{-\frac{u_0^2}{C\si_i^2}}.$$ It is enough to show that $$B\lesssim D:=\max_{1\le i\le n}\si_i^*\sqrt{\ln(i+1)}.$$ To simplify the writing, note that, since $B$ is a symmetric function of the $\si_i$'s, without loss of generality $$\si_i^*=\si_i$$ for all $i$.

Let now $$u_0=K\max_{1\le i\le n}\si_i\sqrt{\ln(i+1)}=KD,$$ where $K:=\sqrt{2C}$. Then for all $i$ $$\frac{u_0^2}{C\si_i^2}\ge\frac{K^2}C\,\ln(i+1)=2\ln(i+1),$$ $$ e^{-\frac{u_0^2}{C\si_i^2}}\le\frac1{(i+1)^2},$$ $$\frac{\si_i^2}{u_0}\le\frac1{KD}\,\frac{D^2}{\ln2}=\frac D{K\ln2},$$ so that $$B\le KD+ \frac{C^2}2 \frac D{K\ln2} \sum_{i=1}^\infty \frac1{(i+1)^2}\lesssim D. \quad\Box$$

Answer 2

$\newcommand{\E}{\mathbb{E}}$I think a good way to think about those problems in general is the chaining technique. This might be slightly too strong of a hammer for the problem at hand, but it gives a concrete way to approach all similar problems. Let us pretend for a second that the random variables $X_1, \ldots X_n$ are instead jointly gaussian (but not necessairly independent).

Theorem (Chaining) Let $T$ be a finite set, and $\{X_t\}_{t \in T}$ be a family of jointly Gaussian random variables, with $\mathbb{E} X_t = 0$. We can introduce a (pseudo)metric on $T$ via $$ d(t_1, t_2) := \sqrt{\mathbb{E} (X_{t_1} - X_{t_2})^2}. $$

Then if $\{t_*\} = A_0 \subset A_1 \subset A_2 \ldots \subset A_m = T$ is a sequence of subsets of $T$, we have $$ \E \sup_t X_{t} \lesssim \sup_t \sum_{k} d(t, A_{k}) \sqrt{\log |A_{k+1}|}. $$ Proof. Let $\pi_k : T \to A_k$ map $t \in T$ to the nearest point in $A_k$. We have $$ X_t - X_{t_*} = \sum_{k} (X_{\pi_{k+1}(t)} - X_{\pi_{k}(t)}) = \sum_{k} d(\pi_{k+1}(t), \pi_k(t)) \frac{X_{\pi_{k+1}(t)} - X_{\pi_k(t)}}{d_{\pi_{k+1}(t), \pi_k(t)}}. $$ Taking supremum we get $$ \sup_t X_t - X_{t_*} \leq \sup_t \sum_k d(\pi_{k+1}(t), \pi_k(t)) \sup_{u\in A_k, v \in A_{k+1}} \frac{X_u - X_v}{d(u,v)}, $$ by linearity of expectation $$ \E \sup_t X_t - X_{t_*} \leq \sup_t \sum_k d(\pi_{k+1}(t), \pi_k(t)) \E \sup_{u\in A_k, v \in A_{k+1}} \frac{X_u - X_v}{d(u,v)}, $$ and since random variables $(X_{u} - X_{v})/d(u,v)$ are all gaussians with variance $1$, we have $\E \sup_{u \in A_k, v\in A_{k+1}} \frac{X_u - X_v}{d(u,v)} \lesssim \sqrt{\log(|A_k| |A_{k+1}|)} \lesssim \sqrt{\log |A_{k+1}|}$.

Finally, by triangle inequality we have $d(\pi_{k+1}(t), \pi_k(t)) \leq 2d(t, \pi_{k}(t))$, and hence $$ \E \sup_t X_t = \E \sup_t X_t - X_{t_*} \lesssim \sup_t \sum_k d(t, A_k) \sqrt{\log |A_{k+1}|}. $$ $\blacksquare$

Now to prove your statement for a collection of Gaussians $X_1, \ldots X_n$, let's just take $X_0 := 0$, and consider a collection $X_0, X_1, \ldots X_n$ together with subsets $A_k := \{0, 1, \ldots 2^{2^k}\}$. Clearly $d(j, A_k) = 0$ if $j \leq 2^{2^k}$ and is at most $\sigma_j$ otherwise, hence $$ \sum_k d(A_k, j) \sqrt{\log |A_{k+1}|} \leq \sigma_j \sum_{k} \mathbf{1}[2^{2^k} < j ] \sqrt{\log |A_{k+1}|} \leq \sigma_j \sqrt{\log(j+1)} \sum_{k\geq 0} 2^{-k/2} \lesssim \sigma_j \sqrt{\log(j+1)} $$

Finally, in case of your problem, we had a bit weaker assumption: $X_1, \ldots X_n$ are only subgaussian. As it turns out, the entire chaining theorem above works with the same proof if $X_1, \ldots X_n$ are subgaussian, where $d(u,v)$ is a subgaussian constant of $(X_u - X_v)$ (see for instance Orlicz norm $\Psi_2$ for the triangle inequality). There should be a way to extract out of this argument much more direct proof of the desired fact.