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?
 A: 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...
A: 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 independent $\sigma^2$-subgaussian random variables. 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}
= \max_{1\leq i\leq n}\mathbb{E}e^{\lambda X_i}
\leq \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 independent $\sigma^2$-subgaussian random variables. 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.
