2
$\begingroup$

I tried to solve the exercise below which can be seen as a generalization of the Bernstein's concentration inequality. However, I have difficulty bounding the moment generating function of $Z$ (see $(2)$ below) with appropriate terms that yield the desired tail bound following the Chernoff method.

Let $X_1,X_2,\ldots ,X_n$ be iid copies of a real random variable $X$ that for some $p\geq 1$ obeys

\begin{align} \mathbb{P}\left(\left\vert X\right\vert > u\right)& \leq \exp\left(-u^p\right),\tag{1} \end{align}

for all $u>0$. For any $s\in \mathbb{R}^n$ and with $q$ denoting the conjugate of $p$ (i.e., $1/p+1/q=1$) prove that

\begin{align} \mathbb{P}\left(Z:=\sum _{i=1}^n s_i X_i > t \right)&\le L \exp\left(-\frac{1}{L}\min \left(\frac{t^2}{\left\Vert s\right\Vert_2^2},\frac{t^p}{\left\Vert s\right\Vert_q^p}\right)\right),\tag{2} \end{align} where $L>0$ is a constant that only depends on $p$, but not $n$.

I have shown that it suffices to establish \begin{align*} \log\mathbb{E}\left[e^{\lambda Z}\right] & \leq \log L + \max\left(\frac{L\left\Vert s\right\Vert_2 ^2\lambda ^2}{4} ,\frac{(p-1)L^{q-1}\left\Vert s\right\Vert_q^q\lambda^q}{p^q}\right). \end{align*}

I also know that \begin{align*} \mathbb{E}\left[e^{\lambda X}\right]& \leq \mathbb{E}\left[e^{\lambda \left\vert X\right\vert}\right]\\ & = 1 + \lambda \int_0^\infty \mathbb{P}\left(\left\vert X\right\vert > t\right)e^{\lambda t}\mathrm{d}t\\ &\leq 1 + \lambda \int_0^\infty e^{\lambda t - t^p}\mathrm{d}t \end{align*} However, I have trouble (i) simplifying this bound and (ii) use it obtain the desired bound on the cumulant generating function of $Z$ mentioned above which should be independent of $n$.

Update: Here's another incomplete attempt. Clearly we have $$\begin{align*} \mathbb{E}\left[e^{\lambda X}\right]&\leq\sum_{k\geq 0}\frac{\lambda^k}{k!}\mathbb{E}\left[|X|^k\right]. \end{align*}$$ Furthermore, using $(1)$ we can bound the moments as $$\begin{align*} \mathbb{E}\left[|X|^k\right]&=\int_{0}^\infty\mathbb{P}\left(|X|^k\geq u^k\right)du^k\\ &\leq \int_0^\infty e^{-u^p}du^k\\ &=\int_{0}^\infty e^{-u}du^{k/p}=\Gamma\left(\frac{k}{p}+1\right),\tag{3} \end{align*}$$ where $\Gamma\left(\cdot\right)$ is the Gamma function. Using log-convexity of the Gamma function we have $\Gamma\left(\frac{k}{p}+1\right)\leq \left(\Gamma\left(k+1\right)\right)^{1/p}=\left(k!\right)^{1/p}$, and thus $$\begin{align*} \mathbb{E}\left[|X|^k\right]&\leq\left(k!\right)^{1/p}. \end{align*}$$ Putting this bound back in $(3)$ we obtain $$\begin{align*} \mathbb{E}\left[e^{\lambda X}\right]&\leq\sum_{k\geq 0} \frac{\lambda^k}{\left(k!\right)^{1/q}}. \end{align*}$$ If we can simplify the series in the latter inequality or find a good approximation for it then we might be able to follow the standard Chernoff bound and obtain the desired result. However, so far I haven't been able to simplify the series.

$\endgroup$
  • $\begingroup$ Yes, my answer is incorrect. Thanks for pointing it out. I have deleted it. For the benefit of others, one of the tricks I used, albeit unsuccessfully, was Holder's inequality. $\endgroup$ – Theja Jun 22 '14 at 4:56
  • $\begingroup$ In which book did you finder this exercise? $\endgroup$ – Thomas Ahle May 27 at 21:38
  • 1
    $\begingroup$ @ThomasAhle It's a book on Concentration Inequalities by Boucheron, Lugosi, and Masart (Oxford University Press) 2013 $\endgroup$ – S.B. May 27 at 22:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.