Adaptive Annealed Importance Sampling with Constant Rate Progress
Shirin Goshtasbpour Victor Cohen Fernando Perez-Cruz
Annealed Importance Sampling (AIS) synthesizes weighted samples from an
intractable distribution given its unnormalized density function. This
algorithm relies on a sequence of interpolating distributions bridging the
target to an initial tractable distribution such as the well-known geometric
mean path of unnormalized distributions which is assumed to be suboptimal in
general. In this paper, we prove that the geometric annealing corresponds to
the distribution path that minimizes the KL divergence between the current
particle distribution and the desired target when the feasible change in the
particle distribution is constrained. Following this observation, we derive the
constant rate discretization schedule for this annealing sequence, which
adjusts the schedule to the difficulty of moving samples between the initial
and the target distributions. We further extend our results to $f$-divergences
and present the respective dynamics of annealing sequences based on which we
propose the Constant Rate AIS (CR-AIS) algorithm and its efficient
implementation for $\alpha$-divergences. We empirically show that CR-AIS
performs well on multiple benchmark distributions while avoiding the
computationally expensive tuning loop in existing Adaptive AIS.