19
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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! $\endgroup$ Apr 29, 2020 at 8:40
  • $\begingroup$ 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! $\endgroup$ Apr 29, 2020 at 8:57

2 Answers 2

17
$\begingroup$

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...

$\endgroup$
17
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .