Complexity Analysis of Normalizing Constant Estimation: from Jarzynski Equality to Annealed Importance Sampling and beyond

arXiv:2502.04575v3 Announce Type: replace-cross Abstract: Given an unnormalized probability density piproptoe^{-V}, estimating its normalizing constant Z=int_{R^d}e^{-V(x)}dx or free energy F=-log Z is a crucial problem in Bayesian statistics, statistical mechanics, and machine learning. It is challenging especially in high dimensions or when pi is multimodal. To mitigate the high variance of conventional importance sampling estimators, annealing-based methods such as Jarzynski equality and annealed importance sampling are commonly adopted, yet their quantitative complexity guarantees remain largely unexplored. We take a first step toward a non-asymptotic analysis of annealed importance sampling. In particular, we derive an oracle complexity of widetilde{O}left(frac{deta^2{A}^2}{arepsilon^4}right) for estimating Z within arepsilon relative error with high probability, where eta is the smoothness of V and A denotes the action of a curve of probability measures interpolating pi and a tractable reference distribution. Our analysis, leveraging Girsanov's theorem and optimal transport, does not explicitly require isoperimetric assumptions on the target distribution. Finally, to tackle the large action of the widely used geometric interpolation, we propose a new algorithm based on reverse diffusion samplers, establish a framework for analyzing its complexity, and empirically demonstrate its efficiency in tackling multimodality.

Source: arXiv cs.LG | 2026-05-20