3
$\begingroup$

Let $X_1, X_2, \dots, X_n$ i.i.d. $N(0,\sigma^2)$ and let $Y_1, Y_2, \dots, Y_n$ be independent and identical Bernoulli random variables (where $Y_i$ may depend on $X_i$).

I am searching for a tailbound / concentration inequality of the form $$P(|\frac{1}{n}\sum_{i=1}^n X_iY_i - \mathbb{E}(X_iY_i)|>z)\leq 2\exp(-c z^2)$$ for some specific value of $c$ (which should obviously depend on the variance of $X_iY_i$).

If the tailbound holds I am very interested in a concrete (and "sharp") value of $c$!).


Possible way to go:

For me it looks like as if $X_iY_i-\mathbb{E}(X_iY_i)$ will still be sub-Gaussian (with which parameter!?). If this could be checked, then one would have to apply a Hoeffding bound to bound the sum of independent subgaussian random variables (which are sub-Gaussian again) and would be done.

However I am having trouble showing that $X_iY_i-\mathbb{E}(X_iY_i)$ is sub Gaussian and finding the correct parameter.

Any help is greatly appreciated.


Edit: as Whuber pointed out with reference to wikipedia it is easy to see that $Z_i:=X_iY_i-\mathbb{E}(X_iY_i)$ is sub-Gaussian by checking the $\Psi_2$ condition. (Here done in more detail than needed, see Whuber's comment: it would have been enough to check the condition directly for $X_iY_i$)

Indeed: since $Z^2 \leq 2(X_iY_i)^2 + 2 \mathbb{E}(X_iY_i)^2$ and $|E(X_iY_i)|<d$ for some $d>0$ we have for all $a>0:$ \begin{align*} \mathbb{E}(\exp(aZ^2)) & \leq \mathbb{E}(\exp(2a (X_iY_i)^2 + 2a\mathbb{E}(X_iY_i)^2))\\ & =\exp(2a\mathbb{E}(X_iY_i)^2)\mathbb{E}(\exp(2a (X_iY_i)^2))\\ & \leq \exp(2ad^2) \mathbb{E}(\exp(2a (X_iY_i)^2))\\ & \leq \exp(2ad^2) \mathbb{E}(\exp(2a X_i^2)) < \infty, \end{align*} since $X_i$ itself is sub-Gaussian and hence follows the $\Psi_2$ condition. Hence $Z_i:=X_iY_i -\mathbb{E}(X_iY_i)$ is sub-Gaussian with some parameter $b$ and $\sum_{i=1}^n Z_i$ is sub-Gaussian with parameter $nb$

However: I am still in need of a concrete value of the constant $c$ (or equivalently: $b$) (as sharp as possible)

The true dependency between $X_i$ and $Y_i$ is too complicated to be given here, hence a more general bound on $c$ would be sufficient (which I feel should be possible, since |Y_i| is bounded by 1). However, if it is of any help/as a starter one could think that for each $i$, the relationship of $(X_i,Y_i)$ could be described by a logistic regression model.

$\endgroup$
  • $\begingroup$ Since $|X_iY_i|\le |X_i|$ and $|\mathbb{E}(X_iY_i)|\le |\sigma|$, isn't the sub-Gaussianity immediate? And when it comes down to finding a "sharp" value of $c$, isn't it equally evident its value must depend on precisely how each $Y_i$ depends on $X_i$? So, aside from these trivialities, there doesn't seem to be much more one could say without more specific information about the $Y_i$. $\endgroup$ – whuber Jul 25 '17 at 15:43
  • $\begingroup$ While I suspect too that the parameter of the sub-Gaussian of $Z:= X_iY_i-\mathbb{E}(X_iY_i)$ is the same as of $X_i$ (i.e. $\sigma$), I don't think it is enough to bound only the first moment of $X_iY_i$ to check for the sub-Gaussian. I think one must at least bound all absolute moments of $Z$? But by doing this I get $$\mathbb{E}(|Z|^p)\leq 2^p E(|X_iY_i|^p) \leq 2^p \mathbb{E}(|X_i|^p)$$ which will at least induce an additional factor of $2$. It's not what I expected + I don't know if the moments are sufficient. $(X_i,Y_i)$ could for example be related through a logistic regression model. $\endgroup$ – chRrr Jul 25 '17 at 16:21
  • $\begingroup$ The bounds on the moments are irrelevant: for any constant $\mu$, $Z$ and $Z-\mu$ are either both subgaussian or both not. Provided, then, that $Z$ has finite expectation, it makes no difference whether you study $Z$ or $Z-\mathbb{E}(Z)$. $\endgroup$ – whuber Jul 25 '17 at 16:26
  • 1
    $\begingroup$ See en.wikipedia.org/wiki/Sub-Gaussian_distribution. One easy characterization of a subgaussian variable $Z$ is that for all $a$, $\mathbb{E}(e^{aZ^2})\lt \infty$. Obviously the finiteness of this expectation is unchanged when $Z$ is shifted to $Z-\mu$, QED. $\endgroup$ – whuber Jul 25 '17 at 16:34
  • 1
    $\begingroup$ The strict inequalities in probabilities make no difference at all, because my examples can be approached arbitrarily closely while still respecting them. The point is that the $Y_i$ can suppress the chances of large $|X_iY_i|\in\{|X_i|, 0\}$ appearing or they can allow large $|X_iY_i|$ to appear at essentially the same rate they would in the underlying Normal distribution for $X_i$--and any behavior in between is possible. To make any progress, you must supply information about the rates at which the $Y_i$ reduce the chances of large $|X_iY_i|$ appearing. $\endgroup$ – whuber Jul 25 '17 at 18:10
1
$\begingroup$

For explicit absolute constants in the bound, you can use symmetrization and contraction. Indeed, if $\epsilon_1,...,\epsilon_n$ are independent random variables taking values $\pm1$ with probability $1/2$ (and independent of the $X_i$ and the $Y_i$, then by symmetrization (noting that $t\to\exp(\lambda t)$ is convex) we get

$E[ \exp(\lambda \sum_{i=1}^n (X_iY_i - E[X_iY_i]) \le E\exp(2\lambda \sum_{i=1}^n \epsilon_i X_i Y_i).$

Next, by contraction you get rid of the Bernoulli (even if $X_i,Y_i$ are dependent):

$E\exp(2\lambda \sum_{i=1}^n \epsilon_i X_i Y_i) \le E\exp(2\lambda \sum_{i=1}^n X_i)$.

But now $\sum_{i=1}^n X_i$ is $N(0, n\sigma^2)$ so the right hand side equals $\exp(2 \lambda^2 n \sigma^2)$. This implies by Markov inequality with $\lambda =t/(2\sigma\sqrt n)$

\[ P\left( \frac{1}{\sqrt n}\sum_{i=1}^n (X_i Y_i-E[X_i Y_i]) > t \sigma \right) \le e^{-\lambda t \sigma \sqrt n + 2n\lambda^2\sigma^2 } = e^{-t^2/4}. \] We may use the same argument for the other direction.

What is symmetrization?

If $\epsilon_1,...,\epsilon_n$ are iid $\pm 1$ as above, independent of $Z_1,...,Z_n$ which are iid with $E[Z_i]=0$, then for any convex positive function $F$,

$E[ F(\sum_{i=1}^nZ_i) ]\le E[ F(\sum_{i=1}^n\epsilon_i Z_i) ]$.

Why is this true? of $Z_1',...,Z_n'$ are independent copies of $Z_1,...,Z_n$ then by Jensen's inequality \begin{align} E[ F(\sum_{i=1}^nZ_i) ] & \le E[ F(\sum_{i=1}^n (Z_i-Z_i') ] \\ &= E[ F(\sum_{i=1}^n \epsilon_i(Z_i-Z_i') ] \\ &\le \frac 1 2 E[ F(2\sum_{i=1}^n \epsilon_iZ_i) ] + \frac 1 2 E[ F(2\sum_{i=1}^n -\epsilon_i Z_i') ] \\ &= E[ F(2\sum_{i=1}^n \epsilon_i Z_i) ]. \end{align} Here, the first inequality is Jensen's and the $Z_i'$ have mean zero, the first equality is because $\epsilon_i(Z_i-Z_i')$ has the same distribution as $Z_i-Z_i'$ (because its distribution is symmetric), the second inequality is Jensen's again, and the last equality is because $\epsilon_iZ_i$ and $-\epsilon_iZ_i'$ are equal in distribution.

What is contraction?

If you have deterministic $x_1,...,x_n$ and random signs $\epsilon_1,...,\epsilon_n$ as above, then \[ \sup_{\boldsymbol y\in [-1,1]^n} E_\epsilon [F(\sum_{i=1}^n \epsilon_i y_i x_i) = E_\epsilon[F(\sum_{i=1}^n \epsilon_i x_i). \] (Here the only random variables are the $\epsilon_i$s). Why is this true? Because the function $G:\boldsymbol y \to E[F(\sum_{i=1}^n \epsilon_i y_i x_i)$ from $[-1,1]^n\to R$ is convex, and convex functions over polytopes such as $[-1,1]^n$ attains their maximum at a vertex. Here, the vertices of $[-1,1]^n$ are of the form $y_i=\pm 1$ for each $i=1,...,n$. But for any $\boldsymbol y$ of such form, $G(\boldsymbol y) = E_\epsilon[F(\sum_{i=1}^n \epsilon_i x_i)$ because $(\epsilon_1,...,\epsilon_n)$ has the same distribution as $(y_1\epsilon_1,...,y_n\epsilon_n)$ when $y_i=\pm 1$.

Contraction for random $X_1,...,X_n$ and $Y_1,...,Y_n$...

Now if $X_1,...,X_n$ and $Y_1,...,Y_n$ are random with $Y_i\in[-1,1]$ (as in your example), then by conditioning on the $X_i,Y_i$'s, \begin{align} E[ F( 2 \sum_{i=1}^n \epsilon_i X_i Y_i) ] & = E\Big[ E[ F( 2 \sum_{i=1}^n \epsilon_i X_i Y_i) \Big|X_1,...,X_n,Y_1,...,Y_n] \Big] \\ &\le E\Big[ \max_{\boldsymbol y\in[-1,1]^n} E[ F( 2 \sum_{i=1}^n \epsilon_i X_i y_i) \Big|X_1,...,X_n] \Big] \\ & = E\Big[ E[ F( 2 \sum_{i=1}^n \epsilon_i X_i) \Big|X_1,...,X_n] \Big] = E[ F(2 \sum_{i=1}^n \epsilon_i X_i ) ]. \end{align}

$\endgroup$
0
$\begingroup$

I think I got one answer. It doubt it to be the sharpest bound, but at least it is a usable bound.

I am using Theorem 2.1 from this rough draft:

It is easy to see that (III) in Theorem 2.1 holds: $$\mathbb{E}((X_iY_i-\mathbb{E}(X_iY_i))^{2k})\leq \frac{(2k)!}{2^k k!} (2\sigma)^{2k}=\frac{(2k)!}{2^k k!} \theta^{2k},$$ where $\theta = 2\sigma$ From the proof $ (III) \rightarrow (I)$ given in Appendix A of the rough draft (p.39) we then may immediately conclude that for all $\lambda>0$ we have

$$\mathbb{E}(\exp(\lambda (X_iY_i-\mathbb{E}(X_iY_i))) \leq \exp(\frac{(\lambda \sqrt{2}\theta)^2}{2}),$$

i.e., by definition, $Z_i:=(X_iY_i-\mathbb{E}(X_iY_i))$ is sub-Gaussian with parameter $\sqrt{2}\theta = 2^{\frac{3}{2}}\sigma$.

Since $Z_1,\dots Z_n$ are independent sub-Gaussian r.v. with parameter $2^{\frac{3}{2}}\sigma$. It follows from the Hoeffding bound that also $$P(\frac{1}{n}|\sum_{i=1}^n (X_iY_i-\mathbb{E}(X_iY_i))| \geq t) \leq 2 \exp(-\frac{t^2 n}{2^4\sigma^2})= 2\exp(-ct^2)$$ where $c \equiv c_n = \frac{n}{2^4 \sigma^2}$ (hence the value $c$ is not a pure constant, but depends also on $n$).

Moreover I think that one might still improve the factor $\frac{1}{2^4}$ appearing in $c$.

$\endgroup$
  • $\begingroup$ If by "parameter" you mean the value "$c$" in your question, then this result cannot be correct. (Test it in the case $n=1$ and $Y_1$ is an independent Bernoulli$(1/2)$ variable, making $X_1Y_1$ a Normal$(0,\sigma^2)$ variable.) You might be switching back and forth between understanding $\sigma$ as the precision and $\sigma$ as the standard deviation of the underlying Normal distribution, or perhaps there's a typo in the question and you meant to write $1/c^2$ instead of $c$. $\endgroup$ – whuber Jul 26 '17 at 13:54
  • $\begingroup$ for $n=1$ it follows from $$\mathbb{E}(\exp(\lambda (X_iY_i-\mathbb{E}(X_iY_i))) \leq \exp(\frac{(\lambda \sqrt{2}\theta)^2}{2})$$ that $$P(|X_iY_i-\mathbb{E}(X_iY_i))|\geq z) \leq 2 \exp(-\frac{z^2}{2 (2^{\frac{3}{2}\sigma})^2}),$$ hence the corresponding value of $c$ would be $$c = \frac{1}{16\sigma^2}.$$ If $X_iY_i$ would be $N(0,\sigma^2)$ then this bound is, as expected, rather rough ($c=\frac{1}{16\sigma^2}$ vs $c_{normal} = \frac{1}{2\sigma^2}$), but I can't see anything wrong in it. (a sharper bound would be, of course, still better) $\endgroup$ – chRrr Jul 26 '17 at 14:22
  • $\begingroup$ Could you please, once and for all, explain what you mean by the "parameter" of a sub-Gaussian? Your edit to this answer indicates it's not $c$, but $c$ explicitly is what you refer to in the question. $\endgroup$ – whuber Jul 26 '17 at 15:17
  • $\begingroup$ Definition: A r.v. $X$ with $\mathbb{E}(X)=\mu$ is called sub-Gaussian if $\exists \sigma>0$ s.t. for all $\lambda>0$ $$\mathbb{E}(\exp(\lambda)(X-\mu))\leq \exp(\frac{\sigma^2\lambda^2}{2})$$ $\sigma$ is called the sub-Gaussian parameter. Short: $X \sim sG(\sigma)$. If $X_1,\dots, X_n$ ind. $sG(\sigma)$ one gets the Hoeffding bound $$ P(\frac{1}{n}|\sum_{i=1}^n(X_i-\mu_i))| \geq t) \leq 2 \exp(-\frac{t^2n}{2 \sigma^2}) \leq 2\exp(-ct^2)$$ for some "constant" $c$.$c$ is not the sG parameter but a "constant" (depending on n) bounding the $exp$-fct.I search a tight $c$. $\endgroup$ – chRrr Jul 26 '17 at 15:48

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.