The sample size required in importance sampling

By Sourav Chatterjee, Persi Diaconis. 2015

235 citations recorded by the source corpus.

The goal of importance sampling is to estimate the expected value of a given function with respect to a probability measure $\nu$ using a random sample of size $n$ drawn from a different probability measure $\mu$. If the two measures $\mu$ and $\nu$ are nearly singular with respect to each other, which is often the case in practice, the sample size required for accurate estimation is large. In this article it is shown that in a fairly general setting, a sample of size approximately $\exp(D(\nu||\mu))$ is necessary and sufficient for accurate estimation by importance sampling, where $D(\nu||\mu)$ is the Kullback-Leibler divergence of $\mu$ from $\nu$. In particular, the required sample size exhibits a kind of cut-off in the logarithmic scale. The theory is applied to obtain a general formula for the sample size required in importance sampling for one-parameter exponential families (Gibbs measures).

Subfields: Computational Mechanics, Statistical and Nonlinear Physics, Statistics and Probability, Probabilistic & Bayesian Methods

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Statistical and Nonlinear Physics

In Statistics and Probability

In Probabilistic & Bayesian Methods

Citations in the corpus

AUTO-ENCODING VARIATIONAL BAYES (2020, unknown): “Plugging in the concentration bound from Lemma 1 in the result of in [25], we obtain an error bound on the IS estimator for posterior expectations.”
Pareto Smoothed Importance Sampling (2015, background): “7 Several authors (Sanz-Alonso, 2018; Agapiou et al., 2017; Chatterjee and Diaconis, 2018), have proved, under a variety of assumptions, that a minimum sample size to control the importance sampling error is roughly”
Practical and Asymptotically Exact Conditional Sampling in Diffusion Models (2023, unknown): “Consequently, this approach will be impractical if p θ ( x 0 | y ) is too dissimilar from p θ ( x 0 ) : the number of particles required for accurate estimation of p θ ( x 0: T | y ) is exponential in KL p θ ( x 0: T | y ) ∥ p θ ( x 0: T ) (Chatterjee and Diaconis, 2018).”
An approximate sampler for energy-based models with divergence diagnostics (2022, background): “This highlights the need for better proposal distributions to compute these quantities, especially considering that the number of samples that IS needs to compute partition function of P ( x ) is inversely proportional to exp( D KL ( p, q )) (Chatterjee and Diaconis, 2018).”