Definition. A random variable X∈RX \in \mathbb{R} is said to be sub-Gaussian with variance proxy σ2\sigma^2 if E[X]=0\mathbb{E} [X] = 0 and its moment generating function satisfies

E[exp⁡(sX)]≤exp⁡(σ2s22),∀s∈R. \mathbb{E}[ \exp (sX) ] \le \exp \left( \frac{\sigma^2 s^2 }{2} \right), \qquad \forall s \in \mathbb{R}.

In this case we write X∼subG(σ2)X \sim \text{subG}(\sigma^2).

Theorem. Let X1,…,XnX_1, \ldots, X_n be nn random variables such that Xi∼subG(σ2)X_i \sim \text{subG}(\sigma^2). Then

E[max⁡i∈[n]Xi]≤σ2log⁡n,E[max⁡i∈[n]∣Xi∣]≤σ2log⁡(2n). \mathbb{E} \Big[ \max_{i \in [n] } X_i \Big] \le \sigma \sqrt{ 2 \log n }, \qquad \mathbb{E} \Big[ \max_{i \in [n] } | X_i | \Big] \le \sigma \sqrt{ 2 \log (2 n ) }.

Proof. ∀s>0\forall s > 0,

E[max⁡i∈[n]Xi]=1sE[max⁡i∈[n]sXi]=1sE[ln⁡(exp⁡(max⁡i∈[n]sXi))]≤1sln⁡(E[exp⁡(max⁡i∈[n]sXi))]Jensen=1sln⁡(E[max⁡i∈[n]exp⁡(sXi))]≤1sln⁡(∑i∈[n]E[exp⁡(sXi))]≤1sln⁡(∑i∈[n]exp⁡(σ2s22))=1sln⁡n+σ2s2≤2σ22ln⁡nSetting s=2ln⁡nσ2=σ2ln⁡n. \begin{aligned} \mathbb{E} \Big[ \max_{i \in [n] } X_i \Big] &= \frac{1}{s} \mathbb{E} \Big[ \max_{i \in [n] } s X_i \Big] \\ &= \frac{1}{s} \mathbb{E} \Big[ \ln \Big( \exp \Big( \max_{i \in [n] } s X_i \Big) \Big) \Big] \\ &\le \frac{1}{s} \ln \Big( \mathbb{E} \Big[ \exp \Big( \max_{i \in [n] } s X_i \Big) \Big) \Big] \qquad \text{Jensen} \\ &= \frac{1}{s} \ln \Big( \mathbb{E} \Big[ \max_{i \in [n] } \exp \Big( s X_i \Big) \Big) \Big] \\ &\le \frac{1}{s} \ln \Big( \sum_{i \in [n] } \mathbb{E} \Big[ \exp \Big( s X_i \Big) \Big) \Big] \\ &\le \frac{1}{s} \ln \Big( \sum_{i \in [n] } \exp \Big( \frac{\sigma^2 s^2}{2} \Big) \Big) \\ &= \frac{1}{s} \ln n + \frac{\sigma^2 s}{2} \\ &\le 2 \sqrt{ \frac{\sigma^2}{2} \ln n} \qquad \text{Setting } s = \sqrt{ \frac{2 \ln n}{\sigma^2} } \\ &= \sigma \sqrt{ 2 \ln n}. \end{aligned}

To prove the second inequality, we can set Xi+n=−XiX_{i + n} = - X_i, for all i∈[n]i \in [n], so that

E[max⁡i∈[n]∣Xi∣]=E[max⁡i∈[2n]Xi]≤σ2log⁡(2n). \mathbb{E} \Big[ \max_{i \in [n] } | X_i | \Big] = \mathbb{E} \Big[ \max_{i \in [2n] } X_i \Big] \le \sigma \sqrt{ 2 \log (2n) }.

□\square

Reference

[1]. Rigollet, Phillippe, and Jan-Christian Hütter. "High dimensional statistics." Lecture notes for course 18S997 813 (2015): 814.