# Tail bounds for maximum of sub-Gaussian random variables

I have a question similar to this one, but am considering sub-Guassian random variables instead of Gaussian. Let $X_1,\ldots,X_n$ be centered $1$-sub-Gaussian random variables (i.e. $\mathbb{E} e^{\lambda X_i} \le e^{\lambda^2 /2}$), not necessarily independent. I am familiar with the bound $\mathbb{E} \max_i |X_i| \le \sqrt{2 \log (2n)}$, but am looking for an outline of a tail bound for the maximum.

A union bound would give $$\mathbb{P}(\max_i |X_i| > t) \le \sum_i \mathbb{P}(|X_i| > t) \le 2n e^{-t^2/2},$$ but I am looking for a proof of something of the form $$\mathbb{P}(\max_i |X_i| > \sqrt{2 \log (2n)} + t) \le \mathbb{P}(\max_i |X_i| > \mathbb{E} \max_i |X_i| + t) \le 2e^{-t^2/2}.$$ Does anyone have any hints?

• Hi, quick question about the problem you posted above: by "$1$-subgaussian", do you mean that the Orlicz norm is $1?$ I noticed that some authors use the word "variance proxy $\sigma^2",$ so I'm trying to understand if you meant variance proxy $1$, and that automatically implies that the Orlicz norm is also $1?$ Sorry to ask a question on top of your question, I'm learning the subject myself! Apr 29, 2020 at 8:40
• Also, the original question math.stackexchange.com/questions/1460412/… you referred to, has essentially a two-sided inequality, so it tells us the maximum of the absolute values of $n$ gaussians concentrate near $\sqrt{2 log(2n)}$. But I see that your question asks for a one sided inequality, can it be made two-sided for subgaussians? I'd hope yes! Apr 29, 2020 at 8:57

I'm not sure but I think this works. Applying the union bound directly gives. \begin{align} \mathbb{P}(\max_i |X_i| > \sqrt{2\log(2n)} + t) &\le 2n \exp\left( -(\sqrt{2\log(2n)}+t)^2/2 \right)\\ &= 2n \exp(-\log (2n) - t\sqrt{2 \log(2n)} - t^2/2)\\ &\le e^{-t\sqrt{2 \log(2n)}} e^{-t^2/2}\\ &\le e^{-t^2/2} \end{align} This is tighter than the bound given in the post I linked in my question, so maybe there I've made a mistake...

I needed something along those lines recently and didn't have a specific reference to cite, so here is a proof of a self-contained statement implying yours.

Theorem. Let $$X_1,...,X_n$$ be $$\sigma^2$$-subgaussian random variables with mean zero. Then $$\mathbb{E}[\max_{1\leq i\leq n} X_i] \leq \sqrt{2\sigma^2\log n} \tag{1}$$ and, for every $$t>0$$, $$\mathbb{P}\!\left\{\max_{1\leq i\leq n} X_i \geq \sqrt{2\sigma^2(\log n + t)}\right\} \leq e^{-t}\,. \tag{2}$$

Proof. The first part is quite standard: by Jensen's inequality, monotonicity of $$\exp$$, and $$\sigma^2$$-subgaussianity, we have, for every $$\lambda \in \mathbb{R}$$, $$e^{\lambda \mathbb{E}[\max_{1\leq i\leq n} X_i]} \leq \mathbb{E}e^{\lambda \max_{1\leq i\leq n} X_i} = \mathbb{E} \Big[ \max_{1 \leq i \leq n} e^{\lambda X_i} \Big] \leq \mathbb{E} \left[ \sum_{i=1}^n e^{\lambda X_i} \right] = \sum_{i=1}^n\mathbb{E}e^{\lambda X_i} \leq n e^{\frac{\sigma^2\lambda^2}{2}}$$ so, taking logarithms and reorganizing, we have $$\mathbb{E}[\max_{1\leq i\leq n} X_i] \leq \frac{1}{\lambda}\ln n + \frac{\lambda \sigma^2}{2}\,.$$ Choosing $$\lambda := \sqrt{\frac{2\ln n}{\sigma^2}}$$ proves (1). $${}$$ Turning to (2), let $$u := \sqrt{2\sigma^2(\log n + t)}$$. We have $$\mathbb{P}\{ \max_{1\leq i\leq n} X_i \geq u \} = \mathbb{P}\{ \exists i,\; X_i \geq u \} \leq \sum_{i=1}^n \mathbb{P}\{ X_i \geq u \} \leq n e^{-\frac{u^2}{2\sigma^2}} = e^{-t}$$ the last equality recalling our setting of $$u$$. $$\square$$

Here is now an immediate corollary:

Corollary. Let $$X_1,...,X_n$$ be $$\sigma^2$$-subgaussian random variables with mean zero. Then, for every $$u>0$$, $$\mathbb{P}\!\left\{\max_{1\leq i\leq n} X_i \geq \sqrt{2\sigma^2\log n}+ u \right\} \leq e^{-\frac{u^2}{2\sigma^2}}\,. \tag{3}$$

Proof. For any $$u>0$$, $$\mathbb{P}\!\left\{\max_{1\leq i\leq n} X_i \geq \sqrt{2\sigma^2\log n} + u \right\} \leq e^{-\frac{u^2}{2\sigma^2} - u\sqrt{\frac{2\log n}{\sigma^2}}} \leq e^{-\frac{u^2}{2\sigma^2}},$$ the inequality by choosing $$t := \frac{u^2}{2\sigma^2} + u\sqrt{\frac{2\log n}{\sigma^2}}$$ and using (2). $$\square$$

More: the slides of some lecture notes by John Duchi.

• In the proof of the Corollary, is the first inequality in the right direction according to (1)? Jan 31, 2021 at 20:30
• @Ankitp Thanks for spotting this, you're right. I've made the required change. Jan 31, 2021 at 21:16
• Note: independence is not even required (we take a union bound). Feb 2, 2021 at 19:47