PaperlayerView exact revision on arXiv

Source-linked AI summary

Layered Adaptive Importance Sampling

L. Martino, V. Elvira, D. Luengo, J. Corander

arXiv:1505.04732v4stat.COcs.LGstat.ML

TL;DR

Monte Carlo approximation depends on suitable proposal densities, but designing them is difficult. The paper introduces hierarchical proposal generation, a general multiple-importance-sampling framework, and adaptive schemes driven by MCMC chains. Its reported results include PI-MAIS outperforming other algorithms across nearly all tested parameter choices and showing robustness to initialization and covariance choice.

  • Problem

    Monte Carlo estimation uses proposal densities because direct target sampling is impossible in many applications, and proposal choice is crucial to performance.

    Source: §1 · p. 1, §2 · p. 3

  • Method

    The paper combines hierarchical proposal generation with a deterministic-mixture framework and uses MCMC chains to adapt populations of proposals for importance sampling.

    Source: §1 · p. 2

  • Results

    PI-MAIS outperforms the other algorithms virtually for all tested parameter choices and is more robust to initial values and covariance matrices.

    Source: §6.1 · p. 14

  • Takeaways & Limitations

    The resulting adaptive schemes retain MCMC’s explorative behavior while allowing straightforward estimation of the normalizing constant as in importance sampling.

    Source: §1 · p. 2

    Directly sampling the target as the mean-generating distribution is practically infeasible, so that choice cannot be used directly in implementation.

    Source: §3.3 · p. 4

Abstract

from arXiv · show

Monte Carlo methods represent the "de facto" standard for approximating complicated integrals involving multidimensional target distributions. In order to generate random realizations from the target distribution, Monte Carlo techniques use simpler proposal probability densities to draw candidate samples. The performance of any such method is strictly related to the specification of the proposal distribution, such that unfortunate choices easily wreak havoc on the resulting estimators. In this work, we introduce a layered (i.e., hierarchical) procedure to generate samples employed within a Monte Carlo scheme. This approach ensures that an appropriate equivalent proposal density is always obtained automatically (thus eliminating the risk of a catastrophic performance), although at the expense of a moderate increase in the complexity. Furthermore, we provide a general unified importance sampling (IS) framework, where multiple proposal densities are employed and several IS schemes are introduced by applying the so-called deterministic mixture approach. Finally, given these schemes, we also propose a novel class of adaptive importance samplers using a population of proposals, where the adaptation is driven by independent parallel or interacting Markov Chain Monte Carlo (MCMC) chains. The resulting algorithms efficiently combine the benefits of both IS and MCMC methods.

1 Introduction

Monte Carlo performance depends on choosing suitable proposals, while IS and MCMC offer complementary strengths. The paper develops a hierarchical proposal procedure, a unified multiple-importance-sampling framework, and adaptive variants driven by MCMC chains.

1 Introduction

  • IS offers straightforward normalizing-constant estimation, whereas MCMC is valued for exploration when target information is limited, especially in high dimensions.Running parallel MCMC chains can facilitate state-space exploration, at increased computational cost.Source: §1 · pp. 1–2
  • The hierarchical procedure generates proposal means at an upper level and candidate samples at a lower level, and standard PMC can be interpreted as using it implicitly.The procedure is intended for sample generation within Monte Carlo algorithms.Source: §1 · p. 2
  • A general deterministic-mixture framework covers multiple importance-sampling schemes, including standard PMC, AMIS, and APIS.The framework also describes iterative adaptive versions of these schemes.Source: §1 · p. 2
  • The proposed adaptive algorithms combine MCMC-style exploration with importance sampling’s straightforward normalizing-constant estimation.One or several MCMC chains drive a multiple-importance-sampling scheme.Source: §1 · p. 2
  • Two population-based variants update proposal means using independent parallel MCMC chains or an interacting adaptive strategy, with all proposals contributing to one global estimator.PI-MAIS is described as parallel chains exchanging statistical information toward a common estimator.Source: §1 · p. 2

2 Target distribution and related integrals

The paper formulates Bayesian inference around a target distribution and integrals to be approximated by Monte Carlo. Because direct target sampling is often unavailable, it considers using multiple proposal densities.

2 Target distribution and related integrals

  • The setup defines x as the variable of interest and y as observed data, and focuses on Bayesian applications while allowing broader simulation targets.The posterior is formed from the likelihood and prior.Source: §2 · p. 2
  • The objective is to approximate an integral measure and the model evidence using Monte Carlo, with the target represented by an unnormalized density when its normalizing constant is unknown.The Bayesian setup identifies the likelihood, prior, and model evidence.Source: §2 · pp. 2–3
  • Because direct sampling from the target is impossible in many applications, Monte Carlo uses simpler proposal densities to generate candidates and focuses here on several proposals.The proposals are denoted q1 through qJ.Source: §2 · p. 3

3 Hierarchical procedure for proposal generation

The hierarchical proposal procedure addresses the difficulty of tuning proposals to match the target by generating proposal parameters and samples in layers.

3 Hierarchical procedure for proposal generation

  • Proposal performance depends on its discrepancy from the target, motivating a hierarchical procedure that generates samples for later use in a Monte Carlo technique.The proposal density is parameterized by mean µ and covariance C.Source: §3 · p. 3
  • The procedure begins by drawing a mean vector µ_j from h(µ), then proceeds to draw a candidate sample.The supplied description gives the initial steps of the sampling procedure.Source: §3 · p. 3

2. Use all the generated samples, x(m)

The section develops a hierarchical proposal procedure, selects a prior for proposal means so the equivalent proposal can approach the target, and explains its practical implementation and relation to other adaptive Monte Carlo schemes.

2. Use all the generated samples, x(m)

  • The hierarchical procedure treats h(µ) as a prior over proposal means, whose samples are not used in the estimator; only the generated x samples enter it.This raises per-iteration computational cost, but the paper reports convergence savings and fewer required iterations in simulations.Source: §2 · p. 3

3.1 Optimal prior h∗(µ)

  • The optimal prior h*(µ|C) is sought with the equivalent proposal set to coincide with the target density.The analysis assumes the proposal form and covariance C are fixed.Source: §3.1 · p. 3

3.2 Asymptotically optimal choice of the prior h(µ)

  • As J →∞, the equivalent proposal density converges to the target when the proposal covariance uses its optimal choice C*.With h(µ) = π̄(µ), the mixture acts as a kernel density estimator; the optimal covariance shrinks toward zero as J increases.Source: §3.2 · p. 4

3.3 Practical implementation

  • Directly sampling proposal means from the target is impractical, so the proposed implementation uses another sampling method, such as MCMC, to obtain them.The upper level explores the state space through the means, while the lower level uses x samples to approximate local target features; the levels require separate tuning.Source: §3.3 · p. 4

3.4 Relationship with other adaptive MC schemes

  • Unlike PMC, SMC, P-MCMC, and SI-MCMC, the hierarchical scheme chooses each mean independently of the previous lower-level sample and excludes means from the resulting estimators.The mean distribution h(µ) is chosen in advance by the user.Source: §3.4 · pp. 4–5

4 Generalized Multiple Importance Sampling

The section develops a unified multiple-importance-sampling framework spanning static and adaptive schemes built from populations of proposal densities. It presents alternative mixture-based weighting and grouping strategies for these schemes.

4 Generalized Multiple Importance Sampling

  • The generalized framework covers static and iterative adaptive multiple importance sampling, including methods previously proposed independently as particular cases.It first treats static MIS alternatives, then their adaptive counterparts.Source: §4 · p. 5, §4.2 · p. 6

4.1 Generalized Static Multiple Importance Sampling

  • Deterministic-mixture MIS weights yield more efficient estimators than standard importance weights, but require JM total proposal evaluations rather than M.The number of target-density evaluations is unchanged; the added computational load may be excessive when J is large.Source: §4.1 · p. 5
  • Partial deterministic-mixture MIS partitions the J proposals into disjoint groups, each defining a mixture with P components.The groups cover all proposal indices without overlap.Source: §4.1 · p. 5
  • In the adaptive framework, each proposal is updated at every iteration using statistical information gathered from earlier iterations.M samples are drawn from each proposal at each iteration.Source: §4.2 · p. 6
  • Using ψ(x) or ξn(x) makes per-iteration computational cost increase with T, whereas φt(x) keeps it controlled by N regardless of the number of adaptive steps.With ψ(x) and ξn(x), earlier proposals must be evaluated at new samples; those algorithms can quickly become unfeasible as T grows.Source: §4.2 · p. 7
  • The iterative scheme may recalculate weights for previously generated samples, but choices Φn,t(x) = qn,t(x) or Φn,t(x) = φt(x) avoid that step.The algorithm can output weighted samples or an estimator of a target moment.Source: §4.2 · p. 7

5 Markov adaptation for GAMIS

Markov GAMIS adapts proposal means with MCMC in an upper layer and estimates the target through a lower-layer multiple-importance-sampling scheme. Its variants differ in their MCMC updates and weighting choices, while the hierarchy supports consistency under stated proposal-tail and weighting conditions.

5 Markov adaptation for GAMIS

  • Markov GAMIS uses MCMC to update proposal means in an upper layer, then applies a multiple-importance-sampling estimator in a lower layer.The lower layer uses the proposal population and a selected Φ function to compute weights.Source: §5 · p. 8

5.1 Theoretical support: adaptation and consistency

  • MAIS can be treated as static MIS because all means are generated independently of lower-level samples before estimation; consistency requires heavier-tailed proposals and a suitable weight denominator.The independence also supports parallelization.Source: §5.1 · pp. 8–9

5.2 The new class of algorithms

  • Markov GAMIS variants depend on the MCMC update and Φ choice; novel RWIS, PI-MAIS, and I2-MAIS use Φ=φ_t to avoid the weight-recalculation step.RWIS is the N=1 special case, with a distinct proposal for MH adaptation and IS estimation.Source: §5.2 · p. 9

5.3 Population-based algorithms

  • Population-based MAIS offers independent-chain and interacting adaptations, with all adapted proposals contributing to one global IS estimate.The proposed variants are presented as a trade-off between performance and computational cost.Source: §5.3 · p. 10

5.3.1 MCMC adaptation for PI-MAIS

  • PI-MAIS updates each mean with its own parallel MCMC chain, while the chains interact through the lower-layer partial deterministic-mixture weights.The iterative algorithm uses N parallel MH transitions, potentially with different proposal densities.Source: §5.3.1 · pp. 10–11

5.3.2 MCMC adaptation for I2-MAIS

  • I2-MAIS can update the full population in an extended state space, but its whole-population MH acceptance probability becomes very small for large N.Each iteration draws N candidate means and requires N new evaluations of the target.Source: §5.3.2 · p. 11

Sample Metropolis-Hastings (SMH) algorithm

SMH updates a population by proposing one new parameter and testing it against a selected population member. MH-within-Gibbs instead updates the means sequentially, and independent means can be generated before a parallel static MIS estimation.

Sample Metropolis-Hastings (SMH) algorithm

  • SMH proposes one parameter and selects a population member for replacement with probability proportional to the inverse of its standard importance weight.At most one population element changes per iteration, and only one new target and proposal evaluation is needed after initialization.Source: Sample Metropolis-Hastings (SMH)… · p. 11

MH within Gibbs

  • MH-within-Gibbs updates the N means sequentially with MH steps, producing one chain of NT states across T iterations.SMH requires E=MNT+T target evaluations; its multinomial selection cost increases with N.Source: MH within Gibbs · pp. 11–12, §5.4 · p. 12

5.5 Non-iterative and parallel implementations

  • With independent parallel chains, means can be generated in advance and the MIS estimates computed as a static framework; the resulting algorithm is completely parallelizable.This decomposition yields N parallel MAIS techniques whose partial estimates form the global estimators.Source: §5.5 · pp. 12–13

6 Numerical simulations

Across multimodal, nonlinear, high-dimensional, and localization tests, the proposed adaptive methods generally perform well, with PI-MAIS often outperforming comparison methods. Its advantage has exceptions, including high-dimensional settings and localization with the widest proposal spread.

6.1 Multimodal target distribution

  • PI-MAIS outperforms the other algorithms virtually across tested parameter choices and both initializations in the multimodal example, and better covers the target’s modes.The initialization may deliberately exclude all modes; PI-MAIS also improves on static approaches and is more robust to initial values and covariance choices.Source: §6.1 · p. 14, Figure 3 · p. 15

6.2 Nonlinear banana-shaped target distribution

  • PI-MAIS and I2-MAIS outperform the other techniques for virtually all tested proposal scales on the banana-shaped target; AMIS also performs well.The comparison uses a fixed total of 2·10^5 target evaluations; Fig. 4 depicts proposal configurations and shows PI-MAIS covering the high-probability region better than PMC.Source: §6.2 · p. 14, Figure 4 · p. 15

6.3 High dimensional target distribution

  • PI-MAIS provides the best results as dimension increases, except at N = 100 and Dx = 35 or 50, where SMC has lower MSE.At N = 100 and Dx = 40, the methods provide virtually the same MSE; all methods degrade as dimension increases under a fixed evaluation budget.Source: §6.3 · pp. 15–16

6.4 Localization problem in a wireless sensor network

  • In the localization task, PI-MAIS outperforms PMC when proposal standard deviations are drawn from U([5]) or U([10]), while PMC performs better for U().The comparison fixes total target evaluations at 2·10^5 and averages MSE over 3,000 independent runs.Source: §6.4 · p. 16

7 Conclusions

The paper presents a hierarchical framework for adaptive Monte Carlo methods and a general multiple-importance-sampling framework. Numerical comparisons on benchmark models support the benefit of layered adaptive sampling approaches.

7 Conclusions

  • The framework combines hierarchical sampling with deterministic-mixture importance sampling to introduce a novel class of adaptive importance-sampling schemes.The framework includes literature methods as special cases and also encompasses full or partial deterministic-mixture approaches.Source: §7 · p. 16
  • The hierarchical interpretation underlies the reported performance of random-walk proposals within Metropolis–Hastings and of standard PMC.The paper also discusses trade-offs between computational cost and improved estimator accuracy.Source: §7 · p. 16
  • Numerical comparisons on benchmark models confirm the benefit of layered adaptive sampling approaches.Source: §7 · p. 16

A Consistency of GAMIS estimators

The consistency discussion gives two asymptotic routes for GAMIS estimators: increasing samples per iteration at finite iteration count, or increasing iterations with fixed population and batch sizes.

A Consistency of GAMIS estimators

  • The analysis is simplified by making adaptation independent of the estimation steps, although a complete analysis should account for adaptation using previous weighted samples.Source: A Consistency of GAMIS estimators · p. 18
  • With finite T, GAMIS estimators are consistent as M or N tends to infinity, assuming proposal densities have heavier tails than the target.The argument treats the global estimator as a static batch multiple-importance-sampling estimator with suitable weights.Source: A Consistency of GAMIS estimators · p. 19
  • With finite N and M, the estimator is asymptotically unbiased as T tends to infinity because the estimate of the unknown normalizing constant converges to Z.The samples are conditionally independent across iterations and independent of one another within each iteration, despite adaptation to previous population configurations.Source: A Consistency of GAMIS estimators · p. 19

B Importance sampling with multiple proposals

This section describes joint importance-sampling estimators built from multiple proposals, including standard MIS and deterministic-mixture variants. The deterministic-mixture approach trades additional proposal evaluations for reduced estimator variance.

B Importance sampling with multiple proposals

  • Deterministic-mixture sampling draws a fixed number of samples from each proposal and treats their combined sample set as drawn from a mixture weighted by those sample counts.The mixture weights are proportional to the number of samples allocated to each proposal.Source: §B.2 · p. 19
  • The deterministic-mixture estimator evaluates every proposal for all Mtot samples, increasing computation relative to standard MIS but reducing estimator variance.The added cost is negligible when proposal evaluation is much cheaper than target evaluation.Source: §B.2 · p. 19
  • The joint estimator can be expressed as a convex combination of partial importance-sampling estimators, with each partial estimator based on one proposal.The construction extends to more than two proposals.Source: §B.3 · p. 20

C Hierarchical interpretation of PMC

Standard PMC can be viewed as a hierarchical sampling procedure, but its upper-level mean generation depends on previously generated samples and uses a changing empirical prior. As N grows, its conditional distribution for the means approaches the target distribution.

C Hierarchical interpretation of PMC

  • PMC’s mean-generation layer is not independent of its sample-generation layer because the means are generated using previously drawn samples.This is one of the stated differences between PMC and the hierarchical procedure introduced earlier.Source: C Hierarchical interpretation of PMC · p. 20
  • PMC draws proposal means by resampling from previously generated samples, then draws each sample from the proposal associated with its selected mean.The resampling uses normalized weights; each selected mean is one of the samples generated at the preceding level.Source: C Hierarchical interpretation of PMC · p. 20, §C.1 · p. 20
  • Unlike the proposed hierarchical scheme’s fixed prior, PMC’s empirical prior depends on lower-level samples and varies with iteration t and population size N.The empirical measure approximates the target distribution using previously generated samples.Source: C Hierarchical interpretation of PMC · p. 20
  • As N grows, PMC’s conditional distribution for the means becomes closer to the target distribution, and its prior approaches the target as N tends to infinity.The passage also states that the estimated normalizing constant converges to Z as N tends to infinity.Source: §C.1 · p. 21

C.1.1 Differences between PMC and MAIS algorithms

MAIS uses MCMC to draw from the target as its prior, with the transition determined by the selected chain kernels. For ergodic chains, the mean distribution approaches the target over time at fixed N, whereas PMC requires increasing N for the same result.

C.1.1 Differences between PMC and MAIS algorithms

  • With fixed N, ergodic MAIS chains with invariant density equal to the target yield a mean distribution that approaches the target as t tends to infinity; PMC requires increasing N.The current prior is determined by the transition kernels of the MCMC algorithms.Source: §C.1.1 · p. 21
  • The experiments also compare log(MSE) across proposal scales and report best and worst PI-MAIS results, while the cited tables describe MSE estimation settings.Table 9 uses initialization In1 and E = 2 · 10^5 target evaluations; the figure summaries include results across σ values and experiments.Source: Table 9 · p. 22, Figure 6 · p. 23, Table 10 · p. 23
  • The MAIS experiments plot log(MSE) against problem dimension for N = 100 and N = 500, keeping target evaluations fixed at E = 2 · 10^5.The figure caption states that the total iteration count is greater for N = 100 than for N = 500.Source: Figure 8 · p. 25
Loading 1505.04732v4…