Interacting Annealed Importance Sampling via Population-Based MCMC Kernels
Authors: Haoxuan Chen, Lexing Ying
Organizations: Institute for Computational and Mathematical Engineering (ICME), Stanford University, Stanford, CA, 94305, USA · Department of Mathematics and Institute for Computational and Mathematical Engineering (ICME), Stanford University, Stanford, CA, 94305, USA
Sampling from a multimodal distribution is a fundamental and challenging problem in computational science and statistics. Among various approaches proposed for this task, one popular method is Annealed Importance Sampling (AIS). In this paper, we propose an interaction-based version of AIS by combining it with population-based Monte Carlo methods to improve its efficiency. By keeping track of an ensemble instead of a single sampler along some continuation path between the starting distribution and the target distribution, we take advantage of the interaction within the ensemble to encourage the exploration of undiscovered modes. Specifically, our main idea is to utilize either the snooker algorithm or the genetic algorithm used in Evolutionary Monte Carlo. We discuss how the proposed algorithm can be implemented and derive a partial differential equation governing the evolution of the ensemble under the continuous time and mean-field limit. We also test the efficiency of the proposed algorithm on various continuous and discrete distributions.
Figure 1: (a) Contour plot of the target density in 4.1.1 ; (b) Plots of LKL evaluated at evolving weighted samples generated by different testing algorithms in 4.1.1 .
Figure 2: Evolving Estimations of E[f(x,y)] evaluated at weighted samples generated by different testing algorithms in 4.1.1 for f1(x,y)=y and f2(x,y)=31x2+51y2 .
Figure 3: Scatter plots of the empirical samples returned by different testing algorithms in 4.1.1 ; (a) MALA + Snooker + BD; (b) MALA + BD; (c) MALA + Reweight; (d) Gaussian MH + Reweight.
Figure 4: (a) & (b) Two minimizers x+(1) and x−(1) of the 1D Ginzburg-Landau Energy ( 12 ) with λ=0.05 ; (c) Plots of LKL evaluated at evolving weighted samples generated by different testing algorithms in the 1D case of 4.1.2 .
Figure 5: Scatter plots of the marginal distribution at (x5,x6) returned by different testing algorithms in the 1D case of 4.1.2 ; (a) MALA + Snooker + BD; (b) MALA + BD; (c) MALA + Reweight; (d) Gaussian MH + Reweight.
Figure 6: (a) & (b) Two minimizers x+(2) and x−(2) of the 2D Ginzburg-Landau Energy ( 12 ) with λ=0.125 ; (c) Plots of LKL evaluated at evolving weighted samples generated by different testing algorithms in the 2D case of 4.1.2 .
Figure 7: Scatter plots of the marginal distribution at (x5,x6) returned by different testing algorithms in the 2D case of 4.1.2 ; (a) MALA + Snooker + BD; (b) MALA + BD; (c) MALA + Reweight; (d) Gaussian MH + Reweight.
Figure 8: (a) Plots of LKL for the posterior distribution ( 15 ) evaluated at evolving weighted samples generated by different testing algorithms; (b) Plots of the squared loss function evaluated at the testing set.
Figure 9: One-dimensional ferromagnetic Ising model with β=0.8 and d=20 ; (a) Box plot with fixed sample size N=512 ; (b) Error plot with varying sample sizes N∈{64,128,256,512,1024} ; (c) Target distribution; (d) Empirical distribution formed by samples generated by Algorithm 8 (sample size N=65536 ).
Figure 10: One-dimensional antiferromagnetic Ising model with β=0.8 and d=20 ; (a) Box plot with fixed sample size N=512 ; (b) Error plot with varying sample sizes N∈{64,128,256,512,1024} ; (c) Target distribution; (d) Empirical distribution formed by samples generated by Algorithm 8 (sample size N=65536 ).
Figure 11: Two-dimensional ferromagnetic Ising model with β=0.3 and d=4 ; (a) Box plot with fixed sample size N=512 ; (b) Error plot with varying sample sizes N∈{64,128,256,512,1024} ; (c) Target distribution; (d) Empirical distribution formed by samples generated by Algorithm 8 (sample size N=65536 ).
Figure 12: Two-dimensional antiferromagnetic Ising model with β=0.3 and d=4 ; (a) Box plot with fixed sample size N=512 ; (b) Error plot with varying sample sizes N∈{64,128,256,512,1024} ; (c) Target distribution; (d) Empirical distribution formed by samples generated by Algorithm 8 (sample size N=65536 ).
Figure 13: (a) Plot of the potential function V(x) with β=0.001 ; (b) Plots of LKL evaluated at evolving weighted samples generated by different testing algorithms.
Figure 14: Scatter plots of the marginal distribution at (x1,x2) returned by different testing algorithms; (a) MALA + Snooker + BD; (b) MALA + BD; (c) MALA + Reweight; (d) Gaussian MH + Reweight.
Monte Carlo sampling algorithms aim to produce samples from a target distribution with a given unnormalised probability density function. The high cost of running Monte Carlo algorithms, with many simulation steps or particles needed to obtain a good empirical approximation to the target, can be reduced by introducing learnable components into the sampler -- a form of amortisation. Once these components are trained, amortised samplers can produce high-quality samples with less computation at sampling time than training-free algorithms would require. We propose an amortised sampler built upon the framework of adaptive importance sampling -- a hierarchical importance sampling procedure where the proposal is iteratively adapted. Our amortised adaptive importance sampling algorithm fits a lightweight neural network that adapts the proposal using information obtained over the course of sampling. By training our sampler over many different targets taken from the same family of distributions, we obtain a sampler that can adapt to a specific target at sampling time without a priori access to the target's parameters. We show that our procedure can efficiently sample from targets within the family the sampler was trained on, giving improvements over target-specific amortised samplers and training-free adaptive importance sampling algorithms. We also explore the potential for generalisation, where the trained sampler is used to sample from targets outwith its training family.
Arran Carter, Víctor Elvira, Esmeralda S. Whitammer
Sampling from multimodal distributions is a central challenge in Bayesian inference and machine learning. In light of hardness results for sampling -- classical MCMC methods, even with tempering, can suffer from exponential mixing times -- a natural question is how to leverage additional information, such as a warm start point for each mode, to enable faster mixing across modes. To address this, we introduce Reweighted ALPS (Re-ALPS), a modified version of the Annealed Leap-Point Sampler (ALPS) that dispenses with the Gaussian approximation assumption. We prove the first polynomial-time bound that works in a general setting, under a natural assumption that each component contains significant mass relative to the others when tilted towards the corresponding warm start point. Similarly to ALPS, we define distributions tilted towards a mixture centered at the warm start points, and at the coldest level, use teleportation between warm start points to enable efficient mixing across modes. In contrast to ALPS, our method does not require Hessian information at the modes, but instead estimates component partition functions via Monte Carlo. This additional estimation step is crucial in allowing the algorithm to handle target distributions with more complex geometries besides approximate Gaussian. For the proof, we show convergence results for Markov processes when only part of the stationary distribution is well-mixing and estimation for partition functions for individual components of a mixture.
Population-based adaptive importance sampling (AIS) methods use a set of proposal densities to approximate complex target distributions. Their performance is commonly assessed through effective sample size (ESS) and related weight-based diagnostics, which measure the concentration of normalized importance weights. However, a large ESS only indicates that the normalized sample weights are not strongly concentrated; it does not describe how the proposal components are arranged in the sampling space. In population-based AIS, several proposal components may generate samples in the same region of the target, so the sample weights can appear well balanced even though the effective number of distinct proposal components is small. This letter introduces the effective number of proposals (ENP), a similarity-aware proposal-level diagnostic for population-based AIS. ENP combines the total normalized weight assigned to each proposal with a redundancy measure computed from similarities among target-weighted samples, estimating the number of non-redundant empirical proposal contributions to the approximation. We establish basic effective-number properties and show that ENP detects proposal collapse and duplication missed by standard ESS. We also illustrate its use as a targeted feedback signal for proposal rejuvenation.
Ali Mousavi, Victor Elvira
Department of Computer Engineering, Islamic Azad University, Neyshabur Branch, Neyshabur, Iran · School of Mathematics, University of Edinburgh, United Kingdom