Help with a subgaussian proposition

Question

I have been trying a question from Van Handel's HDP book

Show that if $\mathbf{E}\left[e^{X^{2} / 6 C}\right] \leq 2$, then $X$ is $18 C$-subgaussian.

And How is this related to :If $X_{1}, \ldots, X_{n}$ are independent, $C$-subgaussian, with mean 0 , then $\frac{1}{\sqrt{n}} \sum_{i=1}^{n} X_{i}$ is $18 C$-subgaussian.

---

It is given.

Hint: for large values of $\lambda$, use Young's inequality $|\lambda X| \leq \frac{a \lambda^{2}}{2}+\frac{X^{2}}{2 a}$ for a suitable choice of $a$; for small values of $\lambda$, use Young's inequality together with $\mathbf{E}\left[e^{\lambda X}\right] \leq 1+\frac{\lambda^{2}}{2} \mathbf{E}\left[X^{2} e^{|\lambda X|}\right]$ by Taylor's theorem.

But I am unable to complete this proof, Can anyone help me in this?

Answer 1

Let $\sigma^2 = C$. Using the hint, we can write $$ \mathbb{E}\left[e^{\lambda X}\right] \leqslant 1+\frac{\lambda^{2}}{2} \mathbb{E}\left[X^{2} \exp (|\lambda X|)\right]. $$ The proof follows from a easy Taylor expansion of both sides, and assuming $\mathbb{E}[X] = 0$. Now, we will use Young's inequality with $a = 6\sigma^2$: $$e^{|\lambda X|} \leq e^{3\lambda^2\sigma^2} e^{\frac{X^2}{12\sigma^2}}.$$ Plugging this identity in into the first inequality, we arrive at: $$ \begin{aligned} \mathbb{E}\left[e^{\lambda X}\right] &\leqslant 1+\frac{\lambda^{2}}{2} \mathbb{E}\left[X^2e^{3 \sigma^{2} \lambda^{2}+\frac{X^{2}}{12 \sigma^{2}}}\right]\\ &\leqslant 1+\frac{\lambda^{2}}{2} e^{3 \sigma^{2} \lambda^{2}} \mathbb{E}\left[X^{2} e^{\frac{X^{2}}{12 \sigma^{2}}}\right]\\ &\leqslant 1+3 \lambda^{2} \sigma^{2} e^{3 \sigma^{2} \lambda^{2}} \mathbb{E}\left[\frac{X^{2}}{6 \sigma^{2}} e^{\frac{X^{2}}{12 \sigma^{2}}}\right]\\ &\leqslant 1+3 \lambda^{2} \sigma^{2} e^{3 \sigma^{2} \lambda^{2}} \mathbb{E}\left[\exp^{2}\left(\frac{X^{2}}{12 \sigma^{2}}\right)\right]&& (e^{t/2}\geq t)\\ &=1+3 \lambda^{2} \sigma^{2} e^{3 \lambda^{2} \sigma^{2}} \mathbb{E}\left[\exp \left(\frac{X^{2}}{6 \sigma^{2}}\right)\right]\\ &\leqslant 1+3 \lambda^{2} \sigma^{2} e^{3 \lambda^{2} \sigma^{2}} \times 2&& (\mathbb{E}[e^{X^2/6\sigma^2}] \leq 2 \text{ by assumption})\\ &\leqslant(1+6 \lambda^{2} \sigma^{2}) e^{3 \lambda^{2} \sigma^{2}} \leqslant e^{9\lambda^2\sigma^2} && (1 + t \leq e^t). \end{aligned} $$

This implies that X is $18\sigma^2$-subgaussian. This is by the definition of sub-gaussianty: $Y$ is $w$ sub-gaussian iff $\mathbb{E}e^{\lambda Y} \leq e^{\lambda^2w^2/2}$.

For the second part of the question, we follow nejimban's comment. First, we apply Chernoff's bound for the random variable $Y = \frac{1}{\sqrt{N}}\sum_{i=1}^{N} X_i$. We get

$$ \begin{aligned} \mathbb{P}[Y \geqslant t]&=\mathbb{P}\left[\frac{1}{\sqrt{N}} \sum_{i=1}^{N} X_{i} \geqslant t\right]=\mathbb{P}\left[\sum_{i=1}^{N} X_{i} \geqslant \sqrt{N} t\right]\\ &\leqslant \frac{\mathbb{E}\left(e^{s \sum_{i=1}^{N} X_{i}}\right)}{e^{s \sqrt{N} t}} \quad \text { (by Chernoff's bound) }\\ &=\frac{\prod_{i=1}^{N} \mathbb{E} e^{s X_{i}}}{e^{s \sqrt{N} t}} \quad \text { (independence) }\\ &\leqslant \frac{\prod_{i=1}^{N} e^{ s^{2} \sigma^{2} / 2}}{e^{s \sqrt{N} t}}=\exp\left({ \frac{s^{2} \sigma^{2} N}{2}-s \sqrt{N} t}\right) = e^{f(s)}. \end{aligned} $$

Optimizing $f(\cdot)$, we get $\mathbb{P}[Y\geqslant t] \leqslant \exp\left(\frac{-t^2}{2\sigma^2}\right)$. Similarly, we can go through the same steps for $-Y$. Hence, we get $\mathbb{P}[|Y|\geqslant t] \leqslant 2\exp\left(\frac{-t^2}{2\sigma^2}\right)$ with union bound. Based on part (d) of problem 3.1 of van Handel's notes, this implies $\mathbb{E}\left[e^{X^2/6\sigma^2}\right] \leq 2.$ Second part of your question is proved by using this fact and part one of your question.

Answer 2

• Young's inequality $$\lvert{\lambda X}\rvert\le\frac{a\lambda^2}2+\frac{X^2}{2a}$$ for $a:=3 C$ gives, using the assumption $\mathbb E\,\mathrm e^{X^2/6 C}\le2$, \begin{align*} \mathbb E\exp(\lambda X) &\le\exp\!\left({\frac{3 C\lambda^2}2}\right)\mathbb E\,\mathrm\exp\!\left(\frac{X^2}{6 C}\right)\!,\\[.4em] &\le2\exp\left(\frac{3 C\lambda^2}2\right). \end{align*} Hence if $|\lambda|\ge A/\sqrt{C}$ (with $A$ to be chosen later), then $$\psi(\lambda):=\log\mathbb E\exp(\lambda X)\le\left(3+\frac{2\log 2}{A^2}\right)\frac{\lambda^2 C}2.\tag{1}$$

• Suppose now $|\lambda|<A/\sqrt{C}$. Taylor-Lagrange inequality yields $$\mathrm e^{\lambda X}-1-\lambda X\le\frac{\lambda^2X^2}2\,\mathrm e^{|\lambda X|}.$$ Thus (assuming $\mathbb E\,X=0$ for simplicity) $$\mathbb E\,\mathrm e^{\lambda X}\le1+\frac{\lambda^2}2\,\mathbb E\,X^2\,\mathrm e^{A|X|/\sqrt{C}},$$ and using $\log(1+x)\le x$ for all $x\ge0$, we get $$\psi(\lambda)\le\frac{\lambda^2}2\,\mathbb E\,X^2\,\mathrm e^{A|X|/\sqrt{C}}.$$ Let $\varepsilon>0$. If $|X|\le\varepsilon\sqrt{C}$, then $X^2\,\mathrm e^{A|X|/\sqrt{C}}\le\varepsilon^2\,\mathrm e^{\varepsilon A}\, C$; otherwise $X^2>\varepsilon\sqrt{C}|X|$ and $X^2\le\frac{\varepsilon C}A\,\mathrm e^{AX^2/\varepsilon C}$. Therefore $$ \mathbb E\,X^2\,\mathrm e^{A|X|} \le\varepsilon^2\,\mathrm e^{\varepsilon A}\, C+\frac{\varepsilon C}A\,\mathbb E\,\mathrm e^{AX^2/\varepsilon C}. $$ Choosing $\varepsilon:=6A$ leads to $$\mathbb E\,X^2\,\mathrm e^{A|X|}\le(36A^2)\mathrm e^{6A^2}\, C+(6 C)\cdot2=\left(12+36A^2\mathrm e^{6A^2}\right) C.$$ Hence, for $|\lambda|<A/\sqrt{C}$, $$\psi(\lambda)\le\left(12+36A^2\mathrm e^{6A^2}\right)\frac{\lambda^2 C}2.\tag{2}$$

• We conclude from $(1)$ and $(2)$ that for all $\lambda\in\mathbb R$, $$\psi(\lambda)\le\left(\inf_{A>0}f(A)\right)\frac{\lambda^2 C}2,$$ where $f(A):=\max\left(3+\frac{2\log 2}{A^2},12+36A^2e^{6A^2}\right)$. It is easy to see numerically that $f(0.305)\le18$.