Do tail bounds on probability translate into bounds on expectations?

Question

Suppose I have a bound of the form: $$P(X \geq t) \leq \exp(-t^2).$$

Can I say anything about the expectation of $X$, $E[X]$? In particular, can I get a bound on $E[X]$?

Here's the specific case that I'm interested in, a nonparametric regression concentration inequality found in these notes: https://www.mit.edu/~rakhlin/courses/mathstat/rakhlin_mathstat_sp22.pdf#page=67.09

Given a fixed dataset $x_i$ and function $f$, define the empirical norm to be $$\|f\|_n^2 = \frac{1}{n}\sum_i f(x_i)^2.$$ Theorem 6 on page 71 proves a bound on the ERM estimator $\hat{f}$ of $f$ in terms of a critical radius $\delta_n$ and an abitrary constant $s$: $$P(\|\hat{f} - f\|_n^2 \geq 16s\delta_n^2) \leq \exp \left(-\frac{ns\delta_n^2}{2}\right),$$ and claim that this result implies the bound on the expectation: $$E \|\hat{f} - f\|_n^2 \leq C\left(\delta_n^2 + \frac{1}{n}\right).$$

I'm having trouble figuring out how the bound on the expectation follows from the bound on the tail probability.

Answer 1

Step 1. Taking the cue from whuber, we begin with a non-negative RV $X$ (we say non-negative because eventually $X=\left\|\hat{f}-f\right\|_n^2\ge 0$), and assume that $P(X\ge t)\le e^{-t},$ for all $t\ge 0.$ Now we have: \begin{align*} E[X]&=\int_0^\infty u\,f(u)\,du\qquad (f(u)\text{ is the density function for $X$})\\ &=\int_0^\infty f(u)\int_0^udt\,du\\ &=\int_0^\infty\int_0^u f(u)\,dt\,du\\ &=\int_0^\infty\int_t^\infty f(u)\,du\,dt\qquad(\text{draw out region for switching order})\\ &=\int_0^\infty P(X\ge t)\,dt\\ &\le \int_0^\infty e^{-t}\,dt\\ &=1. \end{align*} So we have shown that if $P(X\ge t)\le e^{-t},$ it must be that $E[X]\le 1.$ We can let $t=s\delta_n^2,$ assuming $s\ge 0,$ and retain the same result.

Step 2. Now we assume that $P(X\ge 16t)\le e^{-nt/2},$ and re-run the logic. We would have: \begin{align*} E[X]&=\int_0^\infty u\,f(u)\,du\qquad (f(u)\text{ is the density function for $X$})\\ &=\int_0^\infty f(u)\int_0^udv\,du\\ &=\int_0^\infty\int_0^u f(u)\,dv\,du\\ &=\int_0^\infty\int_v^\infty f(u)\,du\,dv\qquad(\text{Let } v=16t)\\ &=16\int_0^\infty\int_{16t}^\infty f(u)\,dt\\ &=16\int_0^\infty P(X\ge 16t)\,dt\\ &\le 16\int_0^\infty e^{-nt/2}\,dt\\ &=\frac{32}{n}\\ &=32\left(\frac1n\right). \end{align*} You can certainly add a positive constant inside the parentheses to get the desired result, though it's not clear why you would want a more sloppy inequality than what I've got here. That is, if you assume $s>0$ and still $t>0,$ you can write $$E[X]\le 32\left(\frac{t}{s}+\frac1n\right)=32\left(\delta_n^2+\frac1n\right).$$ Set $C=32$ and your result is proved.

Answer 2

To compliment Adrian's answer, for your specific problem I think the linked notes imagined the following approach.

As Whuber highlighted in the comments, for any non-negative random variable $X$, we can express the expectation of $X$ as $$\mathbb{E}[X]=\int_0^{\infty}\mathbb{P}(X\geq x)dx$$ This is true by the Fubini-Tonelli theorem for non-negative random variables since $$\int_0^{\infty}\mathbb{P}(X\geq x)dx=\int_0^{\infty}\int_{\Omega}1_{\{X\geq x\}}d\mathbb{P}dx=\int_{\Omega}\int_0^{\infty}1_{\{X\geq x\}}dxd\mathbb{P}=\int_{\Omega}X(\omega)d\mathbb{P}=\mathbb{E}[X]$$ Importantly, $\Vert \hat{f}-f\Vert_n^2$ is such a non-negative random variable. In the link you provided, it is stated in Theorem 6 that $$\mathbb{P}(\Vert \hat{f}-f\Vert_n^2\leq 16s\delta_n^2)\leq \exp \left(-\frac{ns \delta_n^2}{2}\right)$$ holds for any $s\geq 1$. Consider, $$\begin{align*} \mathbb{E}[\Vert \hat{f}-f\Vert_n^2]&=\int_0^{\infty}\mathbb{P}(\Vert \hat{f}-f\Vert_n^2\geq x)dx \\ &=\int_0^{16\delta_n^2}\mathbb{P}(\Vert \hat{f}-f\Vert_n^2\geq x)dx+\int_{16\delta_n^2}^{\infty}\mathbb{P}(\Vert \hat{f}-f\Vert_n^2\geq x)dx \\ &\leq 16\delta_n^2 +\int_{16\delta_n^2}^{\infty}\mathbb{P}(\Vert \hat{f}-f\Vert_n^2\geq x)dx \\ &=16\delta_n^2+\sum_{s=1}^{\infty}\int_{16s\delta_n^2}^{16(s+1)\delta_n^2}\mathbb{P}(\Vert \hat{f}-f\Vert_n^2 \geq x)dx \\ &\leq 16\delta_n^2+\sum_{s=1}^{\infty}\int_{16s\delta_n^2}^{16(s+1)\delta_n^2}\mathbb{P}(\Vert \hat{f}-f\Vert_n^2 \geq 16s\delta_n^2)dx \\ &\leq 16\delta_n^2+\sum_{s=1}^{\infty} 16\delta_n^2 \exp\left(-\frac{ns\delta_n^2}{2}\right) \\ &\leq 16\delta_n^2+\int_0^{\infty} 16\delta_n^2 \exp\left(-\frac{ns\delta_n^2}{2}\right)ds \\ &= 16\delta_n^2+ \frac{32}{n} \\ &\leq 32\left(\delta_n^2 +\frac{1}{n}\right)\end{align*}$$

And so, $\mathbb{E}[\Vert \hat{f}-f\Vert_n^2]\lesssim \delta_n^2+\frac{1}{n}$.

The additional $\delta_n^2$ term comes from the fact the tail bound only holds for $s\geq 1$. If one splits the integral in Adrian's answer as I have done before applying the tail bound the same answer is obtained.