Source-linked AI summary
Adaptive Multiple Importance Sampling
Jean-Marie Cornuet, Jean-Michel Marin, Antonietta Mira, Christian P. Robert
TL;DR
Importance sampling becomes difficult as dimensionality grows, and combining samples from different proposals can be unstable when some weights are poorly behaved. The paper proposes AMIS, which adaptively builds proposals from past weighted samples and recomputes all past and present weights; experiments report improved performance, including a population-genetics analysis with similar outputs to MCMC at much lower execution time. Its convergence properties cannot be fully established.
Problem
Importance sampling suffers performance degradation with dimensionality, while raw pooling of samples from different proposals can be dominated by poorly performing importance functions.
Method
AMIS sequentially constructs adaptive importance proposals from past weighted samples and recomputes the importance weights of all past and present simulations using deterministic multiple mixtures.
Results
In population genetics, IS-AMIS produced similar outputs to MCMC, with execution taking approximately 20 min versus about 2 hours for each MCMC run.
Takeaways & Limitations
Recycling the full simulation history provides a scope for processing heterogeneous simulations together and reducing computational cost in costly likelihood settings.
Takeaways & Limitations
The dependence of AMIS’s bias and variance is too intricate for the authors to determine its asymptotic bias or establish theoretical convergence properties.
Abstract
from arXiv · showhide
The Adaptive Multiple Importance Sampling (AMIS) algorithm is aimed at an optimal recycling of past simulations in an iterated importance sampling scheme. The difference with earlier adaptive importance sampling implementations like Population Monte Carlo is that the importance weights of all simulated values, past as well as present, are recomputed at each iteration, following the technique of the deterministic multiple mixture estimator of Owen and Zhou (2000). Although the convergence properties of the algorithm cannot be fully investigated, we demonstrate through a challenging banana shape target distribution and a population genetics example that the improvement brought by this technique is substantial.
1 Introduction
AMIS extends multiple-mixture importance sampling by constructing proposals sequentially and adaptively while recomputing weights for all past and present samples. It is designed to recycle heterogeneous simulations and address importance sampling’s degradation with dimensionality.
- Importance sampling addresses the difficulty of simulating from complex target distributions, but its performance typically degrades as dimensionality increases.
- AMIS pools importance samples from different importance distributions rather than treating each simulation stream separately.The paper presents this pooling as a novel perspective on multiple-mixture importance sampling.
- Deterministic mixture weights replace each sample’s original denominator with a mixture of the densities that generated the samples.This modification is described as a stabilizing alternative to crudely merging samples with their original weights.
- AMIS constructs its proposal family sequentially and adaptively, deriving each iteration’s distribution from past importance-weighted samples.
- At each iteration, AMIS modifies the weights of all present and past simulated variables using the current proposal collection, then uses the full sample history to construct the next proposal.Using the entire simulation history provides stabilization but requires more involved mathematical machinery.
- The paper evaluates AMIS on a challenging banana-shaped target and a realistic population-genetics application motivated by costly likelihood calculations.The introduction notes that all simulated particles are recycled in the population-genetics setting.
2 Multiple mixtures
Multiple-mixture importance sampling can combine samples from different proposals, but raw mixing can be dominated by a single proposal with unstable weights. Deterministic mixtures instead exploit efficient proposals while reducing the influence of poorly performing ones.
- Samples from several importance functions can be pooled, but marginal approximation to the target does not guarantee satisfactory sample performance.
- An importance function with infinite weight variance can leave extremely large weights in the cumulative sample, overwhelming samples from otherwise efficient proposals.
- Raw mixing of samples and weights from different proposals can therefore harm overall performance compared with using a single sample.
- A deterministic mixture can exploit the most efficient proposals without rejecting simulated values or samples while reducing estimator variance.
- As the number of mixtures increases, poorly performing importance functions are eliminated through erosion of their weights.
3 The AMIS algorithm
AMIS adaptively recycles the entire accumulated importance-sampling history by recomputing deterministic-mixture weights and updating proposals from all weighted particles. It supports several proposal families and parameter-fitting criteria, while allowing additional post-processing of the controlled weighted sample.
- Core algorithm: The accumulated sample can be interpreted as homogeneously sampled from a deterministic mixture of all proposals, although no mixture simulation generated it.The authors describe this as a Rao-Blackwell type of importance sampling.
- Core algorithm: AMIS recomputes every simulated value’s weight at each iteration using an appropriate deterministic mixture, rather than retaining only current particles.The adaptive proposal is estimated from all weighted samples accumulated so far.
- Adaptation: AMIS estimates proposal parameters from the recycled weighted sample using moment matching, variance minimization, or Kullback-Leibler minimization.The generic algorithm repeatedly estimates θ_t within a parametric proposal family.
- Adaptation: A vanilla implementation uses a Student’s t proposal T3(µ, Σ), updating its mean and covariance from self-normalized AMIS estimates of the target’s first moments.The degrees of freedom are fixed at 3, though they could also be estimated at each iteration.
- Proposal extensions: AMIS also accommodates richer proposals, including mixtures of Student’s t or Gaussian densities and blockwise proposals for hierarchical models.For Gaussian mixtures, weighted EM estimates the mixture parameters, with the component count fixed or selected by ICL.
- Proposal extensions: The controlled weighted sample can support final clustering and a subsequent Student’s t resampling stage without losing the deterministic representation.The paper presents this as a possible improvement rather than an elaborated part of the algorithm.
4 Initialization
Initialization is treated as a major determinant of adaptive importance-sampling performance, so AMIS calibrates the starting distribution using effective sample size. The proposed generic construction transforms uniform samples through a scaled inverse-logistic map and selects the scale by ESS maximization.
- Initialization motivation: A poor starting sample can be difficult to recover from because adaptation focuses on already visited regions, motivating substantial initialization effort.The paper characterizes this as a primary difficulty of adaptive importance algorithms.
- Initialization criterion: ESS measures initialization efficiency as the size of an equivalent iid sample from the target and can be estimated from importance-weight variability.The measure does not depend on the test function h.
- Initialization procedure: The proposed initialization independently samples points on a p-dimensional hypercube and maps them coordinatewise to R^p with an inverse logistic transformation.The transformed particles use a scale parameter s.
- Initialization procedure: The logistic scale is optimized to maximize the ESS, producing the selected value s∗ for the starting cohort.The procedure uses a numerical simplex optimization method for this maximization.
- Initialization caveat: The generic logistic initialization is not fool-proof, and the authors favor informed alternatives when target-distribution information or pilot runs are available.They explicitly connect informed initialization to available information about the target.
5 Convergence issues and tuning
AMIS has difficult theoretical behavior because adaptive proposal construction complicates unbiasedness and convergence, while practical tuning depends on the target dimension and estimation goal.
- Convergence issues: Adaptive proposal construction makes the estimator potentially biased and prevents a general convergence result without additional restrictions.The paper notes that compactness restrictions or upper bounds on the target density are needed for convergence analysis in the adaptive setting.
- Convergence issues: The formal convergence analysis studies a Student’s t AMIS variant with one new simulation per iteration and mean-only adaptation, a setting not recommended in practice.The covariance matrix is fixed arbitrarily in this extreme analytical case.
- Convergence issues: The adaptive dependence makes unbiasedness difficult: future simulations alter earlier weights, producing bias whose dependence on iteration is too intricate to analyze asymptotically.The same dependence also prevents a theoretical convergence conclusion in the analyzed formulation.
- Convergence issues: For fixed iteration and earlier sample sizes, the estimator converges in probability to the target expectation as the final sample size increases.This is the paper’s stated lemma for the asymptotic regime where NT goes to infinity.
- Tuning: The authors recommend choosing Nt from 25 to 500 as dimension increases, while noting that increasing sample sizes over iterations may be more efficient if automated selection becomes available.The stated range runs from 25 for small dimensions to 500 around p = 20.
- Tuning: AMIS can target function expectations, marginal distributions, or global samples, so the required ESS depends on the intended output.For function approximation, the paper relates the ESS threshold to the function-specific estimation error and proposes stopping when the desired ESS is reached.
6 A banana shape target example
On a challenging banana-shaped target, AMIS is compared with AIS using the same adaptive proposal framework but different weighting schemes. Across the reported experiments, AMIS consistently outperforms AIS, with gains attributed to stabilizing deterministic-mixture averaging.
- Target and setup: The benchmark twists a centered p-variate Gaussian into a banana-shaped distribution, with tail heaviness controlled by the twisting parameters.The experiment uses the mild setting σ2 = 100 and b = 0.03.
- Target and setup: AIS and AMIS both adapt Gaussian-mixture proposals from past simulations, but AIS uses usual importance weights whereas AMIS uses Gaussian deterministic-mixture weights.This isolates the weighting and recycling strategy in the comparison.
- Target and setup: The comparison uses an initial sample of N0 = 10^5 particles, followed by T = 10 iterations with Nt = 10,000 particles per iteration.Both schemes begin from a rescaled standard logistic distribution.
- Results: The results consistently favor AMIS, with a substantial ESS gain and root mean square error improvements that can reach threefold.The paper attributes the gain to the strong stabilization brought by AMIS averaging.
- Results: Figure 1 compares boxplots of 10 replicate ESS values for AMIS and AIS at p = 5, 10, and 20 using 200,000 total particles.AMIS is shown on the left and AIS on the right.
- Results: The absolute-error boxplots convey the same pattern of uniform AMIS domination in this benchmark setting.This provides a second evaluation view alongside ESS and mean square error.
7 An example from population genetics
The population-genetics example estimates demographic parameters under a costly likelihood model using MCMC and an IS-AMIS approach. Across repeated analyses, IS-AMIS produced similar outputs in approximately one-sixth the runtime, with slightly better repeatability.
- Problem: The benchmark estimates three effective population sizes and divergence time from microsatellite genotypes under a strict Stepwise Mutation model.The parameters are θ1, θ2, θA, and τ, scaled by the locus mutation rate.
- MCMC control: The control analysis jointly updates gene trees and four demographic parameters in a single MCMC chain.
- IS-AMIS analysis: IS-AMIS combines adaptive multiple importance sampling with importance-sampling likelihood estimates based on simulated gene genealogies.Likelihoods are computed by averaging importance weights of gene trees simulated under proposal distributions and parameter values.
- Evaluation: Four repeats per dataset were used to assess the stability and repeatability of both methods.
- Results: 20 min versus about 2 hours: IS-AMIS produced similar outputs to MCMC while running substantially faster and showing slightly better repeatability.The authors attribute the computational advantage to recycling all particles, reducing calls to the costly likelihood approximation.
8 Conclusion
The paper extends deterministic multiple mixtures into an adaptive importance-sampling method that sequentially builds proposals from all samples produced so far. AMIS recycles past simulations and reports substantial practical efficiency, although its theoretical convergence remains unresolved.
- Contribution: AMIS extends deterministic multiple mixtures by constructing sequential importance proposals from previously produced samples.
- Contribution: Integral recycling lets AMIS process heterogeneous past simulations as a single entity.
- Limitation: The theoretical convergence issue remains unresolved, motivating work on acceptable growth rates for the sample sizes N_t as t increases.