The sample size required in importance sampling

DOI10.1214/17-AAP1326MaRDI QIDQ1650098zbMATH OpenOpenAlexFDO

Authors Sourav Chatterjee, Persi Diaconis

Publication date 29 June 2018

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.01437, https://projecteuclid.org/euclid.aoap/1523433632

zbMATH Keywords

importance samplingphase transitionMonte Carlo methodsGibbs measure

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Central limit and other weak theorems (60F05)

Abstract: The goal of importance sampling is to estimate the expected value of a given function with respect to a probability measure $u$ using a random sample of size $n$ drawn from a different probability measure $mu$. If the two measures $mu$ and $u$ 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(u||mu))$ is necessary and sufficient for accurate estimation by importance sampling, where $D(u||mu)$ is the Kullback-Leibler divergence of $mu$ from $u$. 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).

Recommendations

• Importance Sampling and Necessary Sample Size: An Information Theory Approach
• Importance sampling: intrinsic dimension and computational cost
• Large deviations for weighted empirical measures arising in importance sampling
• Importance Sampling Via the Estimated Sampler
• On large deviations theory and asymptotically efficient Monte Carlo estimation

Cites work

• scientific article; zbMATH DE number 3856167 (Why is no real title available?)
• scientific article; zbMATH DE number 1303210 (Why is no real title available?)
• scientific article; zbMATH DE number 1829855 (Why is no real title available?)
• scientific article; zbMATH DE number 2106098 (Why is no real title available?)
• scientific article; zbMATH DE number 2117879 (Why is no real title available?)
• scientific article; zbMATH DE number 824739 (Why is no real title available?)
• scientific article; zbMATH DE number 3196612 (Why is no real title available?)
• A duality formula for Feynman-Kac path particle models
• A sequential Monte Carlo approach to computing tail probabilities in stochastic models
• A sequential importance sampling algorithm for generating random graphs with prescribed degrees
• Abstract tubes, improved inclusion-exclusion identities and inequalities and importance sampling
• Bayesian inference and the parametric bootstrap
• Blind Deconvolution via Sequential Imputations
• Closed form summation for classical distributions: variations on a theme of de Moivre
• Efficient importance sampling for Monte Carlo evaluation of exceedance probabilities
• Efficient importance sampling in ruin problems for multidimensional regularly varying random walks
• Efficient rare-event simulation for the maximum of heavy-tailed random walks
• Estimating and understanding exponential random graph models
• Examples comparing importance sampling and the Metropolis algorithm
• Free energy computations. A mathematical perspective
• Importance Sampling for EstimatingpValues in Linkage Analysis
• Importance Sampling, Large Deviations, and Differential Games
• Importance sampling for families of distributions
• Importance sampling for multiscale diffusions
• Importance sampling in the Monte Carlo study of sequential tests
• Importance sampling: intrinsic dimension and computational cost
• Inference in hidden Markov models.
• Large deviations for weighted empirical measures arising in importance sampling
• Mathematics and computer science: coping with finiteness
• Mean field simulation for Monte Carlo integration
• Methods of reducing sample size in Monte Carlo computations
• Monte Carlo strategies in scientific computing.
• Multidimensional variation for quasi-Monte Carlo
• Multipodal structure and phase transitions in large constrained graphs
• On Lyapunov inequalities and subsolutions for efficient importance sampling
• On the asymptotics of constrained exponential random graphs
• On the importance sampling of self-avoiding walks
• On the role of interaction in sequential Monte Carlo algorithms
• Quasi-Monte Carlo for integrands with point singularities at unknown locations
• Safe and Effective Importance Sampling
• Sequential Monte Carlo Methods for Statistical Analysis of Tables
• Sequential Monte Carlo Methods in Practice
• Sequential Monte-Carlo methods for permutations tests on truncated data
• Simulating normalizing constants: From importance sampling to bridge sampling to path sampling
• Some Approximations to the Binomial Distribution Function
• State-dependent importance sampling for regularly varying random walks
• Stochastic simulation: Algorithms and analysis
• Thermodynamic limit for the Mallows model on \(S_n\)
• Upper tails and independence polynomials in random graphs
• Weighted Average Importance Sampling and Defensive Mixture Distributions

Cited in

(38)

• Randomized sequential importance sampling for estimating the number of perfect matchings in bipartite graphs
• A weighted discrepancy bound of quasi-Monte Carlo importance sampling
• Variational representations of annealing paths: Bregman information under monotonic embedding
• Generalized Bayes approach to inverse problems with model misspecification
• A principled stopping rule for importance sampling
• Rao–Blackwellisation in the Markov Chain Monte Carlo Era
• Stability of sampling proposals for reducible diffusions over large time intervals
• Improving upon the effective sample size based on Godambe information for block likelihood inference
• A lagged particle filter for stable filtering of certain high-dimensional state-space models
• Distilling Importance Sampling for Likelihood Free Inference
• On a Metropolis-Hastings importance sampling estimator
• An Invitation to Sequential Monte Carlo Samplers
• Importance sampling: intrinsic dimension and computational cost
• Sequential importance sampling for estimating the number of perfect matchings in bipartite graphs: an ongoing conversation with Laci
• Convergence rates for optimised adaptive importance samplers
• Assessing the effective sample size for large spatial datasets: a block likelihood approach
• Multi-index sequential Monte Carlo ratio estimators for Bayesian inverse problems
• The square root rule for adaptive importance sampling
• Multilevel ensemble Kalman filtering for spatio-temporal processes
• Sequential importance sampling for multiresolution Kingman-Tajima coalescent counting
• scientific article; zbMATH DE number 5263157 (Why is no real title available?)
• A Tight Analysis of Bethe Approximation for Permanent
• Implicitly adaptive importance sampling
• Counting Walks and Graph Homomorphisms via Markov Chains and Importance Sampling
• Variance analysis of multiple importance sampling schemes
• Target-aware Bayesian inference: how to beat optimal conventional estimators
• Sequential importance sampling for estimating expectations over the space of perfect matchings
• Importance Sampling and Necessary Sample Size: An Information Theory Approach
• Sequential Monte Carlo for Sampling Balanced and Compact Redistricting Plans
• Iterative importance sampling with Markov chain Monte Carlo sampling in robust Bayesian analysis
• Permanental generating functions and sequential importance sampling
• Efficient importance sampling in low dimensions using affine arithmetic
• Context-Aware Surrogate Modeling for Balancing Approximation and Sampling Costs in Multifidelity Importance Sampling and Bayesian Inverse Problems
• On consistent and rate optimal estimation of the missing mass
• Advanced Multilevel Monte Carlo Methods
• scientific article; zbMATH DE number 7370523 (Why is no real title available?)
• Emerging directions in Bayesian computation
• Reduced word enumeration, complexity, and randomization

This page was built for publication: The sample size required in importance sampling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1650098)