Suppose I have two Gaussian distributions $p(x) = \frac{1}{(2\pi)^{d/2}|\Sigma_p|^{1/2}}\exp(-\frac{1}{2}x^\top \Sigma_p^{-1} x)$ and $q(x) = \frac{1}{(2\pi)^{d/2}|\Sigma_q|^{1/2}}\exp(-\frac{1}{2}x^\top \Sigma_q^{-1} x)$.

The ratio between them is defined as $r(x) = \frac{p(x)}{q(x)} = \frac{|\Sigma_q|^{1/2}}{|\Sigma_p|^{1/2}}\exp(-\frac{1}{2}x^\top (\Sigma_p^{-1} - \Sigma_q^{-1})x)$.

We can see that $E_{x \sim q(x)}[\exp(-\frac{1}{2}x^\top (\Sigma_p^{-1} - \Sigma_q^{-1})x)]= \frac{|\Sigma_p|^{1/2}}{|\Sigma_q|^{1/2}}$.

Now I want to approximate the expectation using sample averages, that is given $n$ i.i.d samples $\{x_i\}_{i=1}^{n}$ from $q(x)$, I want to get the concentration inequality for $ P\Big(\big|\frac{1}{n}\sum_{i=1}^n\exp(-\frac{1}{2}x_i^\top (\Sigma_p^{-1} - \Sigma_q^{-1})x_i) - \frac{|\Sigma_p|^{1/2}}{|\Sigma_q|^{1/2}}\big|\geq t\Big) \leq ? $

I'm willing to assume that $\|\Sigma_p\|_{\max}$, $\|\Sigma_q\|_{\max}$ is bounded where $\|\cdot\|_{\max}$ is the largest element in absolute value. And furthermore, we can assume that $\|\Sigma_p^{-1} - \Sigma_q^{-1}\|_1$ is bounded, where $\|\cdot\|_1$ is the sum of absolute values.

  • $\begingroup$ What was the point of defining $r(x)$? $\endgroup$
    – S.B.
    Aug 11 '16 at 14:39

You may use the Chebyshev inequality for the calculation of that probability:

$P(|X-E[X]|\geq a) \leq \frac{Var(X)}{a^2} $

So as $E_{q(x)}[\frac{1}{n}\sum_{i=1}^ne^{\frac{-1}{2}x^T(\Sigma_p^{-1} - \Sigma_q^{-1})x}] = \frac{|\Sigma_p|^{\frac{1}{2}}}{|\Sigma_q|^{\frac{1}{2}}}$ then you can calculate your concentration inequality as:

$P\left(|\frac{1}{n}\sum_{i=1}^ne^{\frac{-1}{2}x^T(\Sigma_p^{-1} - \Sigma_q^{-1})x}| - \frac{|\Sigma_p|^{\frac{1}{2}}}{|\Sigma_q|^{\frac{1}{2}}} \geq t\right) \leq \frac{Var\left(e^{\frac{-1}{2}x^T(\Sigma_p^{-1} - \Sigma_q^{-1})x}\right)}{t^2} $

  • $\begingroup$ function may not have 2nd moment, as is easily seen in 1d $\endgroup$
    – user83457
    Oct 10 '16 at 14:07

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.