0
$\begingroup$

Suppose you have samples from some distribution P. You have a prior distribution Q, which represents your estimate of P, and assume for now that it's parameterized the same way as P. Upon observing samples from P you perform a Bayesian update of Q, yielding a posterior Q'.

As more samples from P are observed, eventually the Kullback–Leibler divergence between Q' and P gets arbitrarily small, i.e. the KL(Q'||P) -> 0. My question is: can we write down a rate of converge as a function of the number of samples observed?

This is really a duplication of this question asked by someone else, but it has no satisfactory answers so I thought I'd ask here.

EDIT: I'm particularly interested in the case where P and Q are multinomial distributions.

$\endgroup$
  • $\begingroup$ I don't see how this can be done. Suppose something converges with a given rate. Taking $n' = [log(log(n))] $ or $ n' = [\exp(n)] $ it seems to me that one can change the rate of convergence without effecting anything else in your question. Similarly sample size should be irrelevant. $\endgroup$ – aginensky Jul 18 '18 at 16:09
  • $\begingroup$ I've done simulations of this scenario with Bernoulli, Multinomial and Gaussian distributions and the estimated/observed convergence rates are remarkably similar to each other. Specifically, I end up with something like log(KL) = -log(N) + b, where N is the number of samples and b is the initial divergence. That suggests to me that there's some deeper pattern, but I don't know what that pattern is. $\endgroup$ – tom Jul 18 '18 at 22:02
1
+50
$\begingroup$

$$ \newcommand{\KL}{\text{KL}} \newcommand{\N}{\mathcal{N}} \newcommand{\norm}[1]{\left|\left|#1\right|\right|} \newcommand{\Expect}[2]{\mathbb{E}_{#1}\left[#2\right]} $$

The original question on Math.SE is not well posed, as the KL between the empirical distribution and the true distribution has a non-zero probability of not being finite. You can do something with some assumptions, like trying to estimate some parameters of a functional form.


Assume you want are estimating the mean $\mu$ of a normal distribution with known variance $\sigma^2$ using the sample mean $\bar{x}$. In this case, the KL divergence reduces to

$$ \KL(\N(\bar{x}, \sigma^2) || \N(\mu, \sigma^2) = \frac{1}{2\sigma^2}\norm{\bar{x} - \mu}^2. $$

And assuming $\bar{x} = \frac{1}{n} \sum_{i=1}^n x_i$, $x_i \sim \N(\mu, \sigma)$, we have that $\Expect{\bar{x}}{\norm{\bar{x} - \mu}^2} = \sigma^2/n$, giving you a convergence rate of $1/n$.


For a Bayesian approach, assume that you have a prior on $\mu$ given by $\N(\mu_0, \sigma_0^2)$, and that after seeing $n$ samples your posterior is $\N(\mu_n, \sigma_n^2)$. You can consider the convergence in term of expected KL divergence,

$$ \begin{array}{rcl} \Expect{x \sim \N(\mu_n, \sigma_n^2)}{\KL(\N(x, \sigma^2) || \N(\mu, \sigma^2))} &=& \frac{1}{2\sigma^2}\Expect{x \sim \N(\mu_n, \sigma_n^2)}{\norm{x - \mu}^2},\\ &=& \frac{1}{2\sigma^2}\norm{\mu_n - \mu}^2 + \sigma_n^2. \end{array} $$

Following the bayesian update, seeing $\bar{x}$ across $n$ samples, (see for e.g. here),

$$ \begin{array}{rcl} \sigma_n^2 & = & \left(\frac{1}{\sigma_0^2} + \frac{n}{\sigma^2}\right)^{-1}\\ \mu_n & = & \sigma_n^2 \left(\frac{\mu_0}{\sigma_0^2} + n \frac{\bar{x}}{\sigma^2}\right) \end{array} $$

Plugging this back in and solving $\Expect{\bar{x}}{\frac{1}{2\sigma^2}\norm{\mu_n - \mu}^2 + \sigma_n^2}$ should also give you a convergence rate in $O(1/n)$.


For a Multivariate Gaussian with unknown covariance matrix, the math gets more complicated but the same principles apply;

$\endgroup$
  • $\begingroup$ Thank you for your answer, this is very close to what I'm looking for. I have a couple follow-up questions - do you know how general the O(1/n) result is? I.e. is it specific to Gaussian distributions, or do you think it also holds for any distribution in the exponential family if the distribution type is assumed known? Or failing that, does it hold for Bernoulli/multinomial distributions? $\endgroup$ – tom Aug 3 '18 at 13:23

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.