Interacting Annealed Importance Sampling via Population-Based MCMC Kernels

Haoxuan Chen; Lexing Ying

stat.COJan 28, 2024

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

Abstract

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.

Figures & tables

w_{s}=\frac{p_{1}(s_{\frac{1}{2}})}{p_{0}(s_{\frac{1}{2}})}\cdots\frac{p_{L}(s_{L-\frac{1}{2}})}{p_{L-1}(s_{L-\frac{1}{2}})}\propto\frac{e^{-U_{1}(s_{\frac{1}{2}})}}{e^{-U_{0}(s_{\frac{1}{2}})}}\cdots\frac{e^{-U_{L}(s_{L-\frac{1}{2}})}}{e^{-U_{L-1}(s_{L-\frac{1}{2}})}}.

(3)

Algorithm 1 Annealed Importance Sampling (AIS)

\displaystyle\rho(r)\propto|r|^{d-1}p(x_{j}+re)=|r|^{d-1}p\Big((1-r)x_{j}+rx_{l}\Big),

(8)

Algorithm 4 Snooker Algorithm

\displaystyle\mathbb{P}\left(x_{l,s}=y_{l,s},x_{j,s}=y_{j,s}\right)=\mathbb{P}\left(x_{l,s}=y_{j,s},x_{j,s}=y_{l,s}\right)=\frac{1}{2}.

Algorithm 5 Genetic Algorithm

Panel of Figure 1 — Figure 1: (a) Contour plot of the target density in 4.1.1 ; (b) Plots of $\mathcal{L}_{\text{KL}}$ evaluated at evolving weighted samples generated by different testing algorithms in 4.1.1 .

Panel of Figure 2 — Figure 2: Evolving Estimations of $\mathbb{E}[f(x,y)]$ evaluated at weighted samples generated by different testing algorithms in 4.1.1 for $f_{1}(x,y)=y$ and $f_{2}(x,y)=\frac{1}{3}x^{2}+\frac{1}{5}y^{2}$ .

Panel of Figure 3 — 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.

Panel of Figure 4 — Figure 4: (a) & (b) Two minimizers $\bm{x}_{+}^{(1)}$ and $\bm{x}_{-}^{(1)}$ of the 1D Ginzburg-Landau Energy ( 12 ) with $\lambda=0.05$ ; (c) Plots of $\mathcal{L}_{\text{KL}}$ evaluated at evolving weighted samples generated by different testing algorithms in the 1D case of 4.1.2 .

Panel of Figure 5 — Figure 5: Scatter plots of the marginal distribution at $(x_{5},x_{6})$ 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.

Panel of Figure 6 — Figure 6: (a) & (b) Two minimizers $\bm{x}_{+}^{(2)}$ and $\bm{x}_{-}^{(2)}$ of the 2D Ginzburg-Landau Energy ( 12 ) with $\lambda=0.125$ ; (c) Plots of $\mathcal{L}_{\text{KL}}$ evaluated at evolving weighted samples generated by different testing algorithms in the 2D case of 4.1.2 .

Panel of Figure 7 — Figure 7: Scatter plots of the marginal distribution at $(x_{5},x_{6})$ 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.

Panel of Figure 8 — Figure 8: (a) Plots of $\mathcal{L}_{\text{KL}}$ 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.

Panel of Figure 9 — Figure 9: One-dimensional ferromagnetic Ising model with $\beta=0.8$ and $d=20$ ; (a) Box plot with fixed sample size $N=512$ ; (b) Error plot with varying sample sizes $N\in\{64,128,256,512,1024\}$ ; (c) Target distribution; (d) Empirical distribution formed by samples generated by Algorithm 8 (sample size $N=65536$ ).

Panel of Figure 10 — Figure 10: One-dimensional antiferromagnetic Ising model with $\beta=0.8$ and $d=20$ ; (a) Box plot with fixed sample size $N=512$ ; (b) Error plot with varying sample sizes $N\in\{64,128,256,512,1024\}$ ; (c) Target distribution; (d) Empirical distribution formed by samples generated by Algorithm 8 (sample size $N=65536$ ).

Panel of Figure 11 — Figure 11: Two-dimensional ferromagnetic Ising model with $\beta=0.3$ and $d=4$ ; (a) Box plot with fixed sample size $N=512$ ; (b) Error plot with varying sample sizes $N\in\{64,128,256,512,1024\}$ ; (c) Target distribution; (d) Empirical distribution formed by samples generated by Algorithm 8 (sample size $N=65536$ ).

Panel of Figure 12 — Figure 12: Two-dimensional antiferromagnetic Ising model with $\beta=0.3$ and $d=4$ ; (a) Box plot with fixed sample size $N=512$ ; (b) Error plot with varying sample sizes $N\in\{64,128,256,512,1024\}$ ; (c) Target distribution; (d) Empirical distribution formed by samples generated by Algorithm 8 (sample size $N=65536$ ).

Panel of Figure 13 — Figure 13: (a) Plot of the potential function $V(x)$ with $\beta=0.001$ ; (b) Plots of $\mathcal{L}_{\text{KL}}$ evaluated at evolving weighted samples generated by different testing algorithms.

Panel of Figure 14 — Figure 14: Scatter plots of the marginal distribution at $(x_{1},x_{2})$ returned by different testing algorithms; (a) MALA + Snooker + BD; (b) MALA + BD; (c) MALA + Reweight; (d) Gaussian MH + Reweight.

Importance Sampling

Importance sampling uses weighted samples from easier or adaptive distributions to estimate quantities under a target distribution.

See all 73 papers

Amortised adaptive importance sampling
Oct 12, 2026Arran Carter, Víctor Elvira, Esmeralda S. WhitammerImportance Sampling Adaptive Sampling
University of Edinburgh
Sampling from multimodal distributions with warm starts: Non-asymptotic bounds for the Reweighted Annealed Leap-Point Sampler
Dec 19, 2025Holden Lee, Matheau Santana-GijzenMarkov Chain Monte Carlo
Beyond Effective Sample Size: Effective Number of Proposals for Adaptive Importance Sampling
Aug 15, 2026Ali Mousavi, Victor ElviraImportance Sampling
Department of Computer Engineering, Islamic Azad University, Neyshabur Branch, Neyshabur, Iran · School of Mathematics, University of Edinburgh, United Kingdom

Oct 12, 2026J/K move · Enter open · S save

Amortised adaptive importance sampling

Arran Carter, Víctor Elvira, Esmeralda S. Whitammer

University of Edinburgh

Importance Sampling Adaptive Sampling Amortized Inference

Open paper AskPDF arXiv

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.

Abstract

Importance Sampling

Explore similar work

Amortised adaptive importance sampling

Sampling from multimodal distributions with warm starts: Non-asymptotic bounds for the Reweighted Annealed Leap-Point Sampler

Beyond Effective Sample Size: Effective Number of Proposals for Adaptive Importance Sampling