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

Gibbs measureimportance samplingMonte Carlo methodsphase transition

Mathematics Subject Classification ID

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

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

• A duality formula for Feynman-Kac path particle models
• A sequential importance sampling algorithm for generating random graphs with prescribed degrees
• A sequential Monte Carlo approach to computing tail probabilities in stochastic models
• 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
• 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?)
• Importance Sampling for EstimatingpValues in Linkage Analysis
• Importance sampling for families of distributions
• Importance sampling for multiscale diffusions
• Importance sampling in the Monte Carlo study of sequential tests
• Importance Sampling, Large Deviations, and Differential Games
• 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

(53)

• Efficient importance sampling in low dimensions using affine arithmetic
• Importance sampling: intrinsic dimension and computational cost
• Multilevel ensemble Kalman filtering for spatio-temporal processes
• Permanental generating functions and sequential importance sampling
• Convergence rates for optimised adaptive importance samplers
• Implicitly adaptive importance sampling
• On consistent and rate optimal estimation of the missing mass
• A principled stopping rule for importance sampling
• Reduced word enumeration, complexity, and randomization
• On a Metropolis-Hastings importance sampling estimator
• Sequential importance sampling for multiresolution Kingman-Tajima coalescent counting
• Assessing the effective sample size for large spatial datasets: a block likelihood approach
• A weighted discrepancy bound of quasi-Monte Carlo importance sampling
• Iterative importance sampling with Markov chain Monte Carlo sampling in robust Bayesian analysis
• Importance Sampling and Necessary Sample Size: An Information Theory Approach
• Sequential importance sampling for estimating the number of perfect matchings in bipartite graphs: an ongoing conversation with Laci
• Counting Walks and Graph Homomorphisms via Markov Chains and Importance Sampling
• Target-aware Bayesian inference: how to beat optimal conventional estimators
• Consistent estimation of small masses in feature sampling
• A Tight Analysis of Bethe Approximation for Permanent
• A lagged particle filter for stable filtering of certain high-dimensional state-space models
• Stability of sampling proposals for reducible diffusions over large time intervals
• scientific article; zbMATH DE number 5263157 (Why is no real title available?)
• Sequential Monte Carlo for Sampling Balanced and Compact Redistricting Plans
• An Invitation to Sequential Monte Carlo Samplers
• Generalized Bayes approach to inverse problems with model misspecification
• Advanced Multilevel Monte Carlo Methods
• Rao–Blackwellisation in the Markov Chain Monte Carlo Era
• Sequential importance sampling for estimating expectations over the space of perfect matchings
• Context-Aware Surrogate Modeling for Balancing Approximation and Sampling Costs in Multifidelity Importance Sampling and Bayesian Inverse Problems
• Distilling Importance Sampling for Likelihood Free Inference
• Variance analysis of multiple importance sampling schemes
• Emerging directions in Bayesian computation
• Variational representations of annealing paths: Bregman information under monotonic embedding
• Improving upon the effective sample size based on Godambe information for block likelihood inference
• Multi-index sequential Monte Carlo ratio estimators for Bayesian inverse problems
• The square root rule for adaptive importance sampling
• Large-sample analysis of cost functionals for inference under the coalescent
• Composite likelihood inference for the Poisson log-normal model
• Adaptive reduced tempering for Bayesian inverse problems and rare event simulation
• Adaptive reduced multilevel splitting
• A non-asymptotic error analysis for parallel Monte Carlo estimation from many short Markov chains
• Counting the number of group orbits by marrying the Burnside process with importance sampling
• A tight analysis of Bethe approximation for permanent
• Insight from the Kullback-Leibler divergence into adaptive importance sampling schemes for rare event analysis in high dimension
• Importance sampling-based gradient method for dimension reduction in Poisson log-normal model
• Channel simulation: theory and applications to lossy compression and differential privacy
• Spanning trees and redistricting: new methods for sampling and validation
• Mixtures of Gaussian process experts with \(\mathrm{SMC}^2\)
• Asymptotic theory of efficient nonparametric estimation of the ratio of two densities
• Large deviations for independent Metropolis Hastings and Metropolis-adjusted Langevin algorithm
• Mitigating mode collapse in normalizing flows by annealing with an adaptive schedule: application to parameter estimation
• Randomized sequential importance sampling for estimating the number of perfect matchings in bipartite graphs

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)