Source-linked AI summary
Convergence of adaptive mixtures of importance sampling schemes
R. Douc, A. Guillin, J. -M. Marin, C. P. Robert
TL;DR
Poor proposal choices complicate efficient importance sampling, and adaptive updates require convergence guarantees. The paper studies adaptive mixtures of fixed proposals and shows that Rao–Blackwellized PMC converges to a Kullback-divergence-optimal mixture, unlike the basic version; the approach remains constrained by high-dimensional complexity.
Problem
Importance-sampling efficiency depends on choosing a proposal distribution that can be difficult to calibrate, and poor choices may produce infinite-variance estimators.
Source: §1.1 · pp. 1–2Method
The paper adapts the weights of mixtures of fixed proposals in population Monte Carlo, including a Rao–Blackwellized update.
Source: §1.3 · p. 3, §3 · p. 7, §5 · p. 14Results
Under assumptions (A1)–(A2), Rao–Blackwellized PMC weights converge to the mixture optimal under the Kullback divergence criterion, whereas basic D-kernel PMC weights converge to 1/D.
Source: §3.2 · p. 9, §5.3 · p. 16Takeaways & Limitations
The method provides an adaptive mixture aimed at Kullback-divergence minimization, with the proposal-family parameterization restricted to mixture weights.
Source: §7 · p. 23High-dimensional use remains subject to the curse of dimensionality, requiring more proposals and exponentially more proposal parameters to tune.
Source: §7 · p. 26
Abstract
from arXiv · showhide
In the design of efficient simulation algorithms, one is often beset with a poor choice of proposal distributions. Although the performance of a given simulation kernel can clarify a posteriori how adequate this kernel is for the problem at hand, a permanent on-line modification of kernels causes concerns about the validity of the resulting algorithm. While the issue is most often intractable for MCMC algorithms, the equivalent version for importance sampling algorithms can be validated quite precisely. We derive sufficient convergence conditions for adaptive mixtures of population Monte Carlo algorithms and show that Rao--Blackwellized versions asymptotically achieve an optimum in terms of a Kullback divergence criterion, while more rudimentary versions do not benefit from repeated updating.
1. Introduction.
Choosing an importance proposal is difficult and consequential, while adaptive MCMC faces validity constraints. The paper studies adaptive mixtures of fixed proposals, updates their weights toward Kullback-divergence optimality, and contrasts basic PMC with its Rao–Blackwellized version.
1.1. Monte Carlo calibration.
- Poorly calibrated importance distributions can yield infinite-variance estimators, while local MCMC proposals may converge slowly and depend on exploration scale.The paper uses Kullback divergence to measure similarity between the target and proposal distributions.Source: §1.1 · pp. 1–2
1.2. Adaptivity in Monte Carlo settings.
- PMC uses repeated importance sampling to adapt proposals while preserving validity, but the original implementation may become asymptotically nonadaptive.Unlike adaptive MCMC, PMC can be stopped at any time and requires no burn-in.Source: §1.2 · p. 3
1.3. Plan and objectives.
- The paper studies mixtures of fixed proposals and proves that updating their weights converges to the mixture optimal under Kullback divergence.Its stated scope restricts proposal-family parameterization to mixture weights.Source: §1.3 · p. 3
- The paper contrasts a basic PMC version with a Rao–Blackwellized version that overcomes its limitations and achieves Kullback-criterion optimality.It also illustrates practical convergence on benchmark examples.Source: §1.3 · p. 3
2. Population Monte Carlo.
Population Monte Carlo repeatedly applies sampling importance resampling, using earlier iterations to inform proposals. The section explains the importance-sampling framework and its resampling step, then notes that adaptive proposal updates do not guarantee lasting improvement.
2. Population Monte Carlo.
- PMC is repeated sampling importance resampling, validated by the importance-sampling identity and stoppable at any time without a Markov-chain convergence result.Its simulations use the whole sequence rather than a Markovian state transition.Source: §2 · p. 4
2.1. The Monte Carlo framework.
- Importance-sampling accuracy depends strongly on proposal choice, which is delicate for complex, high-dimensional targets and requires substantial computational power.The target's normalizing constant may be unknown, motivating self-normalized importance sampling.Source: §2.1 · p. 5
2.2. Sampling importance resampling.
- SIR draws an importance sample from a proposal, then resamples weighted points into an unweighted sample marginally distributed from the target.The SIR estimator has greater variance than the self-normalized importance-sampling estimator because of the additional multinomial step.Source: §2.2 · pp. 5–6
2.3. The population Monte Carlo algorithm.
- PMC adapts proposals using earlier simulations, but open-ended updates do not guarantee permanent improvement, motivating comparison of mixture-based update schemes.The paper considers schemes in which improvement does not occur and in which it does.Source: §2.3 · pp. 6–7
3. The D-kernel PMC algorithm.
The D-kernel PMC scheme adapts a mixture of preselected transition kernels by adjusting their weights from simulated samples. As the sample size grows, the weights converge to uniform values, so repeated updates do not yield learning.
3. The D-kernel PMC algorithm.
- The algorithm adapts a mixture of proposals chosen before simulation by adjusting their weights toward kernels with higher survival rates during resampling.The component weights are proportional to the survival rates of their kernels in the previous resampling step.Source: §3 · p. 7
3.1. Algorithmic details.
- At each iteration, the scheme samples from a selected kernel, computes importance weights, and resamples; at the final iteration, it stops after weighting the sample.Resampling helps avoid propagation of very small importance weights and subsequent degeneracy.Source: §3.1 · p. 8
3.2. Convergence properties.
- Under the stated assumptions, a general law of large numbers applies to the simulated points and kernel indices, yielding a convergent estimator of π(f).The kernel indices are auxiliary variables rather than quantities needed for the original Monte Carlo target.Source: §3.2 · p. 9
- At every iteration, the D-kernel weights converge to 1/D as N grows, leaving the algorithm nonadaptive and making later large-sample iterations redundant.The weighted estimate of π(f) is nevertheless convergent.Source: §3.2 · p. 9
4. The Kullback divergence.
The section uses Kullback divergence to evaluate how well a transition-kernel mixture approximates the target, then develops iterative updates of mixture weights. The updates increase the criterion and the maximization procedure converges toward its optimum.
4.1. The criterion.
- The optimal weight vector αmax makes the product of π and the kernel mixture closest to the product distribution π̄.The criterion’s strict concavity gives it a unique global maximum.Source: §4.1 · p. 10
4.3. Averaged EM.
- The weight recursion starts from uniform weights and applies αt+1 = F(αt), an averaged EM update.The paper identifies this recursion with an averaged version of EM.Source: §4.2 · p. 10, §4.3 · p. 12
4.2. A maximization algorithm.
- Under assumptions (A1) and (A2), the update does not decrease the criterion, so the corresponding Kullback divergence decreases at each step.The update’s fixed points coincide with the points where the criterion is unchanged, and that fixed-point set is finite.Source: §4.2 · p. 11, §4.3 · p. 12
4.3. Averaged EM.
- The maximization procedure is shown convergent, with its iterates eventually remaining in a neighborhood of αmax.The convergence result is established under assumptions (A1) and (A2).Source: §4.3 · pp. 13–14
5. The Rao–Blackwellized D-kernel PMC.
The Rao–Blackwellized D-kernel PMC uses whole-mixture importance weights and Monte Carlo weight updates; under (A1)–(A2), it converges to a Kullback-optimal mixture.
5.1. The algorithm.
- Using the whole mixture in importance weights avoids conditioning on component choice and prevents infinite-variance importance-sampling estimators.A Monte Carlo version of the weight transform F is used iteratively, analogously to MCEM approximating EM.Source: §5.1 · p. 14, §5 · p. 14
5.2. The corresponding law of large numbers.
- The algorithm's samples satisfy a weak law of large numbers for any target-integrable test function, including unbounded functions, under (A1).The result applies to both weighted and resampled samples.Source: §5.2 · p. 15
5.3. Convergence of the weights.
- Under (A1)–(A2), the Monte Carlo weight update converges to the mixture optimal for the Kullback divergence criterion.The update approximates the theoretical weight update used to minimize that criterion.Source: §5.3 · p. 16
5.4. A corresponding central limit theorem.
- The unweighted sample has larger asymptotic variance than the weighted sample because of the additional multinomial resampling step.Source: §5.4 · p. 18
- The CLT integrability condition need hold for only one transition kernel, so other kernels may fail it.The theorem can therefore cover settings where condition (8) fails for some kernels.Source: §5.4 · p. 18
- The corresponding self-normalized importance-sampling proposal is not implementable because it depends on the unknown target and mixture weights.Source: §5.4 · p. 18
6. Illustrations.
Three illustrations show adaptive mixture weights converging rapidly, the Rao–Blackwellized D-kernel approaching a low-divergence mixture, and a contingency-table sampler stabilizing without an observed degeneracy signal.
Example 1
- In the independent-proposal toy example, accumulated weights reach 1/3 and 2/3 in less than ten iterations.Figure 1 plots the accumulated weights against those optimal values.Source: §6 · p. 20, Figure 1 · p. 21
Example 2
- The D-kernel algorithm approaches a neighborhood of the mixture's minimum-divergence weights from a random start.Strict divergence decrease requires large N, and precise convergence to αmax requires many iterations.Source: §6 · p. 22, Figure 2 · p. 22
Example 3
- The contingency-table model uses a flat prior on (α1, β0, β1) and ten normal random-walk proposals with scales spanning 1.35e−19 to 1.54e+07.The proposal covariance uses the Fisher information matrix evaluated at the maximum-likelihood estimate.Source: §6 · p. 22
- In the contingency-table example, accumulated weights for components 5–8 converge to 0, 0.003, 0.259, and 0.738, respectively.The mixture concentrates on medium variances, while the largest-variance kernels serve as importance-weight variance stabilizers.Source: §6 · p. 23
- The simulated points coincide with the posterior's unique modal region, and the authors report no sample degeneracy.Twenty percent of the sample corresponds to 95% of the weights, while 1% corresponds to 31%; later iterations show stabilization rather than degeneracy.Source: §6 · p. 23
7. Conclusion and perspectives.
The paper concludes that adaptive mixture weights can target minimum Kullback divergence, while noting restrictions on proposal parameterization and challenges for high-dimensional implementation.
Conclusion
- Adaptive mixture weights can target minimization of Kullback divergence with the distribution of interest.The paper also describes a companion update targeting minimum variance for a specified integral.Source: §7 · p. 23
- The results assume proposal families parameterized only by mixture weights; extension to general parameterized mixtures is described as work in development.Source: §7 · p. 23
Perspectives
- High-dimensional implementation remains challenging because the number of proposals and proposal parameters grows with dimension.The paper notes that this growth reflects the curse of dimensionality.Source: §7 · p. 26
APPENDIX A: CONVERGENCE THEOREMS FOR TRIANGULAR ARRAYS
Appendix A sets up triangular-array convergence results used to study the asymptotic behavior of the PMC algorithm, including convergence in probability and conditional-independence conditions.
APPENDIX A
- The appendix defines a triangular array of random variables and uses convergence in probability as N tends to infinity.The results are presented as tools for studying the PMC algorithm's asymptotic behavior.Source: Appendix A · p. 26
- Conditional independence means the variables within each row are independent given the corresponding σ-algebra.Source: Appendix A · p. 26
- The bounded-in-probability conditions include finite conditional absolute first moments and additional probability bounds.The appendix states the conditions for the triangular-array variables.Source: Appendix A · p. 26
APPENDIX B: PROOF OF PROPOSITION 3.1
Appendix B proves the proposition by induction over iterations, applying a triangular-array law of large numbers and verifying its tail condition at each step.
APPENDIX B
- At t = 0, the law of large numbers follows directly from convergence of the importance-sampling algorithm.Source: Appendix B · p. 27
- For t ≥ 1, the proof assumes the previous iteration's law of large numbers and reduces the target convergence to checking the normalizing-constant case and condition (iii).Source: Appendix B · p. 27
- The proof verifies condition (iii) using truncation and the fact that π ⊗ γu(FC) tends to zero as C grows.It then applies Theorem A.1 to conclude the induction step.Source: Appendix B · pp. 27–28