Source-linked AI summary
Adaptive Importance Sampling in General Mixture Classes
Olivier Cappé, Randal Douc, Arnaud Guillin, Jean-Michel Marin, Christian P. Robert
TL;DR
The paper addresses the limitation that adaptive mixture importance sampling previously improved only mixture weights while leaving component kernels fixed. It proposes iterative updates of both weights and component parameters using an entropy criterion, and reports improved robustness from Rao–Blackwellised updates across general mixture densities, including multivariate Student t mixtures.
Problem
Earlier adaptive approaches improved mixture weights but kept proposal kernels fixed, limiting adaptation of parameterised mixture importance-sampling densities.
Method
The method recursively updates mixture weights and component parameters through an integrated-EM-like importance-sampling scheme, with an optional Rao–Blackwellised update.
Results
Rao–Blackwellised updates reduced disastrous or mediocre outcomes from about 60% to below 20% in repeated adaptation runs.
Takeaways & Limitations
The framework provides a flexible approach for adapting general mixture importance-sampling densities, including mixtures of Student t distributions for heavier-tailed targets.
Takeaways & Limitations
Depending on initialization, the local adaptive algorithm can converge to the best-fitting Gaussian stationary point rather than the desired outcome.
Abstract
from arXiv · showhide
In this paper, we propose an adaptive algorithm that iteratively updates both the weights and component parameters of a mixture importance sampling density so as to optimise the importance sampling performances, as measured by an entropy criterion. The method is shown to be applicable to a wide class of importance sampling densities, which includes in particular mixtures of multivariate Student t distributions. The performances of the proposed scheme are studied on both artificial and real examples, highlighting in particular the benefit of a novel Rao-Blackwellisation device which can be easily incorporated in the updating scheme.
1 Introduction
The paper motivates adaptive importance sampling as a parallelizable Monte Carlo alternative and extends mixture adaptation beyond fixed component kernels. It also develops a general integrated-EM updating scheme while addressing robustness through Rao–Blackwellisation.
- Importance sampling supports parallel implementations and facilitates Monte Carlo error assessment when variance estimates are trustworthy.
- Earlier adaptive PMC methods tuned mixture weights while keeping component transition kernels fixed.
- This paper extends adaptive importance sampling to update both mixture weights and component parameters.
- Updating component parameters can create robustness issues, especially for multidimensional scaling parameters, motivating a modest-complexity Rao–Blackwellisation scheme.
- The method uses an entropy criterion suited to performance across a range of typical functions rather than one specific target function.
- The proposed integrated-EM updates apply to independent IS mixtures and all missing-data representations of the proposal kernel, not only finite mixtures.
2 Adapting the Importance Sampling Density
The paper develops M-PMC, an adaptive importance-sampling scheme that updates mixture weights and component parameters through an integrated-EM construction approximated with weighted samples. Rao–Blackwellisation makes parameter updates more robust, while convergence and perplexity provide monitoring tools.
- Criterion and formulation: The entropy criterion for an independent mixture proposal is equivalent to a mixture optimization problem resembling maximum likelihood, with integration under the target replacing empirical averaging.The latent mixture representation enables an EM-style optimization of the criterion.
- M-PMC algorithm: M-PMC iteratively samples from the current mixture, computes normalized importance weights and component posterior probabilities, and updates the mixture parameters.The algorithm starts from fixed parameters and recursively updates them using the current weighted sample.
- Monitoring and convergence: The normalized perplexity exp(Ht,N)/N is asymptotically non-decreasing and consistently estimates exp[−E(π, q(αt,N,θt,N))].It therefore supplies a sample-based monitor for the entropy performance criterion.
- Integrated updates: The integrated-EM updates use the latent component indicator, with mixture weights and component parameters obtained by maximizing an expected complete log-likelihood under the target distribution.The E-step-like expectation is taken over component assignments conditional on the current parameters, with an outer expectation under X ∼ π.
- Integrated updates: The resulting entropy criterion sequence is non-decreasing under the integrated-EM update mechanism.This follows from the same convexity argument used for regular EM estimation.
- Approximate updates: Rao–Blackwellisation replaces sampled component indicators with conditional posterior probabilities, allowing every point to contribute to each component update and improving robustness when N is small or D is large.The original update costs O(N), whereas the Rao–Blackwellised update has overall cost proportional to D × N.
- Monitoring and convergence: Convergence as N increases relies on triangular-array arguments, integrability, positivity, and uniform regularity conditions on the component densities.The paper notes that efficient implementations also require closed-form parameter updates, so convergence of approximations is handled case by case.
3 The Gaussian mixture case
The Gaussian case adapts both mixture weights and component parameters through empirical importance-sampling updates, with Rao–Blackwellisation replacing component indicators by conditional expectations. A two-mode Gaussian experiment shows substantial variance reduction, while robustness depends on sample size, initialization, and defensive safeguards.
- Gaussian mixture proposals parameterize each component by its mean and covariance, providing a direct instance of the general adaptive framework.
- The empirical updates estimate numerator and denominator terms using self-normalised importance sampling, with Rao–Blackwellisation replacing component indicators by their conditional expectations.
- In the ten-dimensional two-mode target, the components have Kullback–Leibler divergence 80, making one component a useless proposal for the other or for the mixture.
- The best-fitting Gaussian approximation reduces variance by about four orders of magnitude for typical functions, while the perfect two-Gaussian fit adds a reduction by less than four.
- A defensive component guarantees finite variance but can slightly limit achievable performance, while insufficient samples or initialization can leave the algorithm at the single-Gaussian outcome.
4 Robustification via mixtures of multivariate t’s
The paper extends adaptive mixture importance sampling to multivariate Student t components using latent-variable representations and fixed degrees of freedom. In the Pima example, Rao–Blackwellised updates substantially stabilise parameter adaptation while preserving a close Bayesian estimate.
- Mixtures of multivariate t distributions: Mixtures of t distributions provide heavier tails than normal mixtures, helping capture a wider range of non-Gaussian targets with fewer components.The t-mixture setting is more challenging because closed-form updates require exploiting the distribution’s latent-variable representation.
- Mixtures of multivariate t distributions: The t proposal is represented using observable values, mixture indicators, and chi-squared latent variables in a normal/chi-squared decomposition.Integrating over the latent variables recovers the t-mixture proposal.
- Adaptive updates: The algorithm updates mixture expectations and covariance structures while keeping each component’s degrees of freedom fixed because no closed-form update is available for them.The component parameters are θd = (µd, Σd), with νd held constant throughout adaptation.
- Pima Indian example: With N = 10,000, T = 500, four components, and ν = (3, 6, 9, 18), non-Rao–Blackwellised updates showed wide component movement despite a stable overall estimate.The weighted estimate of β remained approximately (−5.54, 0.051, 0.019, 0.055, 0.022) over most iterations.
- Pima Indian example: The entropy estimate became quasi-constant after roughly 100 non-Rao–Blackwellised iterations, indicating little benefit from continuing to 500 iterations.The corresponding plot tracks cumulative weights alongside the estimated entropy divergence.
- Pima Indian example: Rao–Blackwellised updates immediately stabilised the weights, means, and covariance parameters, producing a close estimate of β: (−5.63, 0.052, 0.019, 0.056, 0.022).The authors recommend fewer than T = 10 iterations in this example, reserving computation for larger sample sizes and final importance-sampling accuracy.
5 Conclusions
The M-PMC algorithm adapts general mixture importance densities and extends to heavier-tailed t mixtures. The paper reports early stabilisation with sufficiently large per-iteration samples and identifies function-specific entropy adaptation as a possible extension.
- M-PMC provides a flexible and robust framework for adapting general importance sampling densities represented as mixtures.
- The extension to t mixtures broadens the method’s scope to targets with heavier tails.
- With sufficiently large sample sizes, especially initially, mixture estimates and the entropy criterion commonly stabilise within a few iterations.The paper therefore considers large T unnecessary in typical applications.
- A future h-entropy variant could target low approximation error for a particular function h rather than relying on the generic entropy criterion.