Single-sided and double-sided concentration inequality

42 Views Asked by At

Problem

In statistical learning theory, people are interested to bound something like $P[\vert X-\mathbb{E}[X]\vert\geq t]$ and this is done by $$ P[\vert X-\mathbb{E}[X]\vert\geq t]\leq P[X-\mathbb{E}[X]\geq t]+ P[X-\mathbb{E}[X]\leq -t] \tag{1} $$

Now if I could bound individual terms with $\exp(-2nt^2)$, i.e. \begin{align} P[X-\mathbb{E}[X]\geq t]\leq\exp(-2nt^2)\tag{2}\\ P[X-\mathbb{E}[X]\leq -t]\leq\exp(-2nt^2)\tag{3} \end{align}

By (1), I have $$ P[\vert X-\mathbb{E}[X]\vert\geq t] \leq 2\exp(-2nt^2)\tag{4} $$

Now if I set RHS of (2), (3) with $\frac{\delta}{2}$ and RHS of (1) with $\delta$, I have \begin{align} X-\mathbb{E}[X] \leq \sqrt{\frac{1}{2n}\log \frac{2}{\delta}} \ (\text{with probability at least}\ \frac{\delta}{2})\tag{5}\\ X-\mathbb{E}[X] \geq -\sqrt{\frac{1}{2n}\log \frac{2}{\delta}} \ (\text{with probability at least}\ \frac{\delta}{2})\tag{6}\\ \vert X-\mathbb{E}[X]\vert \leq \sqrt{\frac{1}{2n}\log \frac{1}{\delta}} \ (\text{with probability at least} \ \delta)\tag{7} \end{align}

I am confused with inequality (5), (6) and (7), which should be (but does not seem to be) equivalent by derivation from (1) through (4). Specifically, for (7), could I say with probability at least $\delta$, the following simultaneously hold?

$$ X-\mathbb{E}[X] \leq \sqrt{\frac{1}{2n}\log \frac{1}{\delta}} \ (\text{with probability at least}\ \delta)\\ X-\mathbb{E}[X] \geq -\sqrt{\frac{1}{2n}\log \frac{1}{\delta}} \ (\text{with probability at least}\ \delta)\\ $$