PaperlayerView exact revision on arXiv

Source-linked AI summary

Generalized Multiple Importance Sampling

Víctor Elvira, Luca Martino, David Luengo, Mónica F. Bugallo

arXiv:1511.03095v3stat.CO

TL;DR

The paper addresses the lack of a unified account of how samples are drawn and weighted when multiple proposal densities are available. It develops a general MIS framework encompassing existing and novel schemes, then compares them theoretically and experimentally. The results identify performance differences among schemes, with N3 performing best in the reported numerical experiments while some alternatives reduce proposal evaluations; variance conclusions for self-normalized estimators remain approximate.

  • Problem

    With multiple proposal densities, sampling and weighting are not uniquely defined, and valid MIS combinations can differ substantially in estimator performance.

  • Method

    The paper unifies MIS sampling and weighting through three sampling procedures, five generic weighting functions, and theoretical analysis of the resulting schemes.

  • Results

    The framework contains existing MIS methods and yields three novel schemes; numerical experiments report N3 as best overall, with R3 also generally strong and R1/N1 generally worse.

  • Takeaways & Limitations

    Scheme interpretation matters: N2 and R2 can approach N3’s variance reduction in some settings while using fewer proposal evaluations, and no-replacement schemes help when sample counts are small.

  • Takeaways & Limitations

    Variance results for the self-normalized estimator cannot be directly extrapolated from the analyzed estimators without an approximation, and adaptive schemes may become prohibitively costly with many proposals.

Abstract

from arXiv · show

Importance Sampling methods are broadly used to approximate posterior distributions or some of their moments. In its standard approach, samples are drawn from a single proposal distribution and weighted properly. However, since the performance depends on the mismatch between the targeted and the proposal distributions, several proposal densities are often employed for the generation of samples. Under this Multiple Importance Sampling (MIS) scenario, many works have addressed the selection or adaptation of the proposal distributions, interpreting the sampling and the weighting steps in different ways. In this paper, we establish a general framework for sampling and weighing procedures when more than one proposal are available. The most relevant MIS schemes in the literature are encompassed within the new framework, and, moreover novel valid schemes appear naturally. All the MIS schemes are compared and ranked in terms of the variance of the associated estimators. Finally, we provide illustrative examples which reveal that, even with a good choice of the proposal densities, a careful interpretation of the sampling and weighting procedures can make a significant difference in the performance of the method.

1. INTRODUCTION

Multiple importance sampling uses several proposal densities, but available sampling and weighting combinations can differ substantially in estimator performance. The paper introduces a unified framework that contains existing MIS methods, supports new schemes, and compares them theoretically and empirically.

  • Motivation: MIS uses a population of proposal pdfs to make importance sampling more robust than relying on a single proposal.Different implementations depend on assumptions such as known normalizing constants and prior proposal information.
  • Motivation: With multiple proposals, sampling and weighting are not uniquely determined, and different valid combinations can have substantially different estimator performance.The paper identifies this as the central methodological problem addressed by its framework.
  • Framework: The paper introduces a unified theoretical framework describing possible MIS sampling and weighting procedures.It interprets MIS algorithms as drawing from an equally weighted mixture of available proposals.
  • Framework: The framework combines three sampling approaches with five weighting functions and provides rules for devising additional valid strategies.All analyzed sampling/weighting combinations provide consistent estimates of the parameters of interest.
  • Contributions: The framework includes existing MIS methodologies, permits novel techniques, and compares the resulting schemes by estimator variance.The paper reports three new schemes and organizes the work around theoretical analysis, scheme connections, variance analysis, and numerical examples.

2. PROBLEM STATEMENT AND BACKGROUND

Importance sampling approximates target distributions or integrals using samples from proposal densities and weights based on target-to-proposal ratios. The background motivates multiple proposals because estimator variance depends on proposal-target mismatch.

  • Standard importance sampling: Importance sampling approximates integrals involving a target pdf by drawing samples from a proposal pdf and assigning ratio-based weights.The random measure formed by samples and weights approximates the target distribution.
  • Standard importance sampling: The proposal should have heavier tails than the target under the standard importance-sampling formulation.Under mild tail assumptions, the normalizing-constant and self-normalized estimators are consistent.
  • Estimators: All generated samples contribute to importance-sampling estimators, unlike MCMC methods that use a burn-in period.The samples and weights form a random measure used to approximate the posterior.
  • Estimators: When the normalizing constant is unknown, self-normalized importance sampling estimates it from the weighted samples.The paper distinguishes the unbiased estimator available when the normalizing constant is known from the self-normalized alternative.
  • Motivation: Estimator variance depends on the discrepancy between the target and proposal distributions, motivating strategies that reduce their mismatch.This relationship also applies to the target multiplied by the magnitude of the integrand.

3. SAMPLING IN MULTIPLE IMPORTANCE SAMPLING

MIS draws samples from a set of proposal pdfs through an index-selection process followed by proposal sampling. The framework studies replacement and no-replacement strategies and the distributions induced by each choice.

  • Generic sampling scheme: MIS uses multiple proposal pdfs, draws samples from them, and weights the samples to approximate the target distribution.The sampling and weighting procedures determine the different MIS variants.
  • Generic sampling scheme: Each sample is generated by selecting a proposal index and then sampling from the selected proposal pdf.The index-selection probabilities are initially left unspecified, allowing several sampling mechanisms.
  • Sampling strategies: The three sampling strategies are random selection with replacement, random selection without replacement, and deterministic selection without replacement.The without-replacement strategies ensure that each proposal generates exactly one sample, while replacement can omit or repeat proposals.
  • Example: The running Gaussian example illustrates that replacement can select the same proposal repeatedly, whereas no-replacement schemes use distinct proposals.For three proposals, the example gives index sequences {3,3,1}, {3,1,2}, and {1,2,3} for S1, S2, and S3.
  • Induced distributions: Under random index selection, each sample’s marginal distribution is the equally weighted mixture ψ of the proposals.Under deterministic selection, the n-th sample instead has the n-th proposal as its marginal distribution.
  • Induced distributions: The framework considers sequential sampling schemes valid when a uniformly selected sample from the generated set has density ψ(x).This generic random-variable view treats the samples jointly rather than only by their individual indices.

4. WEIGHTING IN MULTIPLE IMPORTANCE SAMPLING

The framework defines valid MIS weighting functions through how each sample’s generating proposal is interpreted. Five such functions yield valid estimators and differ in the proposal information included in each denominator.

  • Weighting principle: MIS weighting functions use weights of the form π(x_n) divided by an interpreted proposal density ϕ_Pn(x_n).The interpretation of the proposal density determines the weighting strategy.
  • Weighting principle: A weighting scheme is valid when its function ϕ_Pn makes the resulting estimator unbiased under the framework’s expectation condition.The paper defines proper weighting through this estimator-validity requirement.
  • Weighting functions: The five weighting functions correspond to conditional and marginal distributions associated with the sampling process.They are derived from the sample distributions discussed in the sampling section.
  • Weighting functions: W2 interprets the selected sample as drawn from its selected proposal q_jn, while W3 uses the sample’s marginal density p(x_n).W3 is described as a natural choice when no further generation knowledge is assumed.
  • Weighting functions: W4 uses the conditional density of the sample given the full set of proposal indexes.This interpretation incorporates the entire index set into the denominator.
  • Comparison: All listed weighting functions yield valid estimators, while different schemes require different numbers of proposal evaluations.They require the same number of target evaluations, which are usually more expensive.

5. MULTIPLE IMPORTANCE SAMPLING SCHEMES

The paper combines three sampling strategies with five weighting functions, yielding six unique valid MIS schemes. The framework recovers existing methods and naturally identifies novel schemes, including R1, R2, and N2.

  • Combining three sampling strategies with five weighting functions produces fifteen possibilities but only six unique MIS methods.Three methods use sampling with replacement, and three use sampling without replacement.
  • R schemes sample with replacement from the whole mixture, while N schemes generate exactly one sample from each proposal.The six schemes are labeled R or N according to whether sampling uses replacement.
  • R1 uses only the selected proposal in each denominator, R2 uses an a posteriori mixture of selected proposals, and R3 uses the full initial mixture.These three weighting choices share the S1 sampling procedure.
  • N1 uses the generating proposal, N2 uses the proposals still available, and N3 uses the whole mixture in each denominator.N1 and N3 may use random or deterministic no-replacement sampling, whereas N2 requires random ordering.
  • The framework includes the known MIS algorithms and yields new valid schemes R1, R2, and N2.The authors state that additional schemes can also be proposed within the framework.

6. VARIANCE ANALYSIS OF THE SCHEMES

The variance analysis establishes a hierarchy among the six unbiased MIS estimators and identifies N3 as the strongest scheme in the reported comparisons. In a bimodal example with perfectly matched proposals, R3 and N3 perform well, while self-normalized variance conclusions require approximation.

  • All six MIS estimators are unbiased, but their variances can differ dramatically.The paper provides an exhaustive variance analysis of the estimators associated with the six schemes.
  • N3 outperforms every other MIS scheme in the literature considered by the authors in terms of estimator variance.For N = 2, N3 also outperforms the novel schemes R2 and N2.
  • Using the whole mixture in every denominator exchanges information across proposals, while deterministic sampling from each mixand adds a stratified-sampling variance-reduction effect.The paper connects this mechanism to multimodal targets and residual resampling.
  • Variance results for the unnormalized estimator cannot be directly transferred to the self-normalized estimator because its analysis involves dependent ratios and covariance terms.The paper treats reduced variance for the self-normalized estimator as a reasonable expectation supported by simulations, not as a direct theorem.
  • Running example: For a bimodal target exactly replicated by two matched proposal densities, the normalizing-constant variances of R3 and N3 are both 0.The example uses N = 2 proposals centered on the two target modes with matching variance.
  • Running example: In the same bimodal example, R3 and N3 perform well, whereas the other schemes do not.This conclusion is reported for proposals perfectly placed in the target modes.

7. APPLYING THE MIS SCHEMES

The paper presents practical guidelines for choosing MIS schemes by balancing estimator variance, proposal-evaluation cost, parallelization, and adaptive or multimodal settings. N3 generally offers the strongest variance performance, while R2 and N2 can reduce computational complexity when proposal sets are large or target evaluations are inexpensive.

  • 7.1 Computational complexity: N3 requires the most proposal evaluations, while R2 has a variable evaluation count because proposals may be repeated or unused.Across the framework, every MIS estimator performs N target evaluations, but proposal-evaluation costs differ by weighting function.
  • 7.1 Computational complexity: N3 should be chosen when proposal-density evaluations are negligible relative to target evaluations because it yields lower variance at little additional cost.This setting includes Big Data Bayesian applications with expensive likelihood evaluations.
  • 7.2 A priori partition approach: A priori partitioning divides proposals into disjoint subsets, applies MIS schemes within subsets, and combines the resulting partial estimators.The partition notation assumes equal subset sizes for simplicity, but the conclusions extend to unequal subsets.
  • 7.2 A priori partition approach: Merging proposal subsets decreases estimator variance, with P = 1 corresponding to N3 and P = N corresponding to N1.The partition approach can therefore trade computational cost against variance reduction.
  • 7.4 Guidelines for applying MIS: For large proposal sets, R2 or N2 may provide good performance with lower complexity, whereas N3 is preferred when N is small or target evaluations are expensive.Further work is needed to characterize R2 and N2 and to construct partitions that retain most of N3’s variance reduction.
  • 7.3 Generalized Adaptive Multiple Importance Sampling: In adaptive MIS, using all spatial and temporal proposals in every denominator has strong potential but becomes computationally prohibitive as the number of proposals grows.The generalized adaptive setting contains N = JT proposals distributed across state space and adaptation time.
  • 7.4 Guidelines for applying MIS: N3 is recommended for multimodal scenarios when the number of proposals is comparable to the number of modes, while N1 should be avoided.When the proposal count is much larger, R2 or N2 may achieve similar performance with less computational complexity.

8. NUMERICAL EXAMPLES

The numerical examples compare MIS schemes across well-tuned multimodal, adaptive, and high-dimensional banana-shaped targets. N3 generally performs best, while sampling and weighting choices substantially affect estimator variance.

  • 8.1 Running example: N3 has the lowest variance in the one-dimensional running example, outperforming direct sampling from the target; R1 and N1 have high variance.R2 and N2 also behave poorly in this example.
  • 8.2.1 Bivariate Gaussian mixture: N3 again performs best in adaptive LAIS and PMC experiments on a five-component bivariate Gaussian mixture.The experiments use J = 100 proposals and T = 200 iterations; R2 and N2 also show satisfactory performance.
  • 8.2.2 Banana-shaped distribution: In the banana-shaped target, N3 and R3 provide similarly good performance across dimensions, while N2 approaches N3 in high dimensions.The LAIS experiment varies dx from 2 to 40 and averages results over 300 runs.
  • 8.3 Discussion: The experiments corroborate the theoretically established variance hierarchy, including for the self-normalized estimator when the normalizing constant is accurately approximated.For sufficiently large sample sizes, the self-normalized schemes are ordered as in the direct estimator comparisons.
  • 8.3 Discussion: R1 and N1 generally perform much worse because their weight denominators use only the proposal that generated each sample.This limitation is especially problematic in multimodal settings.
  • 8.3 Discussion: R2 and N2 can achieve much of N3’s variance reduction with fewer proposal evaluations when many proposals cover relatively few target modes.Both schemes are competitive with N3 in the adaptive experiments.
  • 8.3 Discussion: With few samples, N1, N2, and N3 perform better because sampling without replacement guarantees that every proposal is used.This reduces variance from proposal-index selection.

9. CONCLUSIONS

The paper concludes by framing MIS as a unified sampling-and-weighting problem with many valid combinations. Its framework includes existing methods, yields new schemes, and connects deterministic proposal selection with variance-reduction ideas.

  • 9. CONCLUSIONS: The framework combines three sampling procedures with five generic weighting functions for MIS.The weighting functions relate to conditional and marginal distributions determined by the sampling scheme.
  • 9. CONCLUSIONS: Deterministic sampling S3 draws one sample from each proposal, regardless of draw order, and can be interpreted as sampling from the equally weighted proposal mixture.This interpretation follows by viewing a uniformly selected sample index as generating the mixture distribution.
  • 9. CONCLUSIONS: S3 is connected to stratified sampling, quasi-Monte Carlo index sequences, and residual resampling of proposal indexes.These connections explain S3 as a structured alternative to random proposal-index selection.

APPENDIX B: CONNECTIONS WITH RESAMPLING METHODS

The appendix relates MIS proposal selection to particle-filter resampling while emphasizing that the proposals remain equally weighted in the mixture.

  • APPENDIX B: MIS sampling mechanisms correspond to particle-filter resampling schemes: S1 is multinomial resampling, while S2 and S3 use sampling without replacement.The key distinction is that MIS proposals are equally weighted in the mixture.

APPENDIX C: PROOFS OF UNBIASEDNESS OF THE MIS ESTIMATORS

The appendices establish unbiasedness and analyze estimator variance for the generalized MIS combinations. The proofs use marginalization, conditional independence, and inequalities between proposal averages.

  • Unbiasedness proofs: The appendix proves unbiasedness for the five weighting options in the generalized MIS framework.Each weighting function is analyzed through the general expectation expression for the estimator.
  • Weighting options: Weighting options W1–W4 are obtained by substituting different conditional or marginal sampling densities into the estimator expectation.The derivations include proposal-specific, index-dependent, and mixture-based denominators.
  • Variance analysis: The variance analysis handles dependence among estimator terms by conditioning on the complete proposal-index sequence.Conditional independence then permits the relevant variance expressions to be applied.
  • Scheme-specific analysis: The six schemes R1, R2, R3, N1, N2, and N3 are analyzed through their sampling and weighting combinations.The appendix identifies independence, conditional independence, or averaging over proposal-index sequences for the individual schemes.
  • Variance ordering: The proofs establish Var(Î_N1) ≥ Var(Î_R3) and Var(Î_R3) ≥ Var(Î_N3).These propositions contribute to the theoretical variance ordering of the MIS estimators.
  • Variance ordering: One variance comparison reduces to the arithmetic-mean–harmonic-mean inequality for the proposal densities.The two sides of the inequality correspond to inverses of the arithmetic and harmonic means.

D.3 Proof of Theorem 6.2

The section derives variance relations for MIS schemes, proving the relevant comparison for N=2 while leaving broader claims conditional or conjectural. It also examines a two-proposal Gaussian example and records an exact estimator equivalence.

  • Proof of Theorem 6.2: For N=2, the proposition follows because Var(Î_N1) ≥ Var(Î_N3).The cited inequality establishes the required ordering at least in the two-proposal case.
  • Proof of Theorem 6.2: Theorem 6.2 may extend to N>2, but this remains a hypothesis because R2 and N2 average estimators with different variance behavior.The text relates one component to N3 and another to N1 without claiming a general proof.
  • Proof of Theorem 6.2: No general inequality is established between R3 and R2 because their ordering may depend on π(x), g(x), and the proposal densities.The comparison is therefore proposal- and target-dependent rather than universal.
  • Gaussian example: In the two-proposal Gaussian example, the proposal mixture equals the target, and N2 and R2 produce identical estimators.The example estimates a specific moment using M=2 samples and gives explicit variances for six MIS schemes.

APPENDIX E: MULTIDIMENSIONAL MIXTURE OF GENERALIZED GAUSSIAN DISTRIBUTIONS

This appendix evaluates MIS schemes on a multidimensional mixture of generalized Gaussian target distributions as the state-space dimension increases. The experiments show that low-dimensional method differences diminish at higher dimensions as fixed proposal locations cover the space less effectively.

  • Target distribution: The target is a mixture of multivariate generalized Gaussian distributions whose components factorize across dimensions.The family includes Gaussian and Laplace cases, and the experiment uses specified means, scales, and shape parameters.
  • Experimental setup: The experiment varies the state-space dimension dx from 2 to 10 while estimating the target mean averaged across dimensions.Each method uses M=kN samples with k=32, and results are averaged over 200 runs.
  • Results: R1 and N1 perform poorly at lower dimensions, whereas the other MIS schemes behave similarly in the multidimensional mixture experiment.The hierarchy from Section 6 remains valid regardless of dimension before the methods converge in performance at higher dimensions.
  • Results: At dx ≥6, all methods have similar performance because fixed proposal locations cover the state space less effectively as dimension increases.The proposals are well covered at low dimensions with N=500 densities, but coverage worsens in higher dimensions.
Loading 1511.03095v3…