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

arXiv: https://arxiv.org/abs/2502.04575 · HTML: https://mlsanity.com/paper/2502.04575/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 47 of its 117 references that are in the map.
- First posted on arXiv 7 Feb 2025.

## Builds on (most cited first, 30 of 47)

- [Score-Based Generative Modeling through Stochastic Differential Equations](https://mlsanity.com/paper/2011.13456/) (2020)
- [Fast Sampling of Diffusion Models with Exponential Integrator](https://mlsanity.com/paper/2204.13902/) (2022)
- [Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions](https://mlsanity.com/paper/2209.11215/) (2022)
- [A survey of the Schr"odinger problem and some of its connections with optimal transport](https://mlsanity.com/paper/1308.0215/) (2013)
- [How to Train Your Energy-Based Models](https://mlsanity.com/paper/2101.03288/) (2021)
- [Path Integral Sampler: a stochastic control approach for sampling](https://mlsanity.com/paper/2111.15141/) (2021)
- [Convergence of score-based generative modeling for general data distributions](https://mlsanity.com/paper/2209.12381/) (2022)
- [Underdamped Langevin MCMC: A non-asymptotic analysis](https://mlsanity.com/paper/1707.03663/) (2017)
- [gDDIM: Generalized denoising diffusion implicit models](https://mlsanity.com/paper/2206.05564/) (2022)
- [Improved sampling via learned diffusions](https://mlsanity.com/paper/2307.01198/) (2023)
- [On the relation between optimal transport and Schr"odinger bridges: A stochastic control viewpoint](https://mlsanity.com/paper/1412.4430/) (2014)
- [Solving high-dimensional Hamilton-Jacobi-Bellman PDEs using neural networks: perspectives from the theory of controlled diffusions and measures on path space](https://mlsanity.com/paper/2005.05409/) (2020)
- [NETS: A Non-Equilibrium Transport Sampler](https://mlsanity.com/paper/2410.02711/) (2024)
- [Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlo](https://mlsanity.com/paper/2202.05214/) (2022)
- [Score-Based Diffusion meets Annealed Importance Sampling](https://mlsanity.com/paper/2208.07698/) (2022)
- [How Discrete and Continuous Diffusion Meet: Comprehensive Analysis of Discrete Diffusion Models via a Stochastic Integral Framework](https://mlsanity.com/paper/2410.03601/) (2024)
- [Sequential Controlled Langevin Diffusions](https://mlsanity.com/paper/2412.07081/) (2024)
- [Fast Solvers for Discrete Diffusion Models: Theory and Applications of High-Order Algorithms](https://mlsanity.com/paper/2502.00234/) (2025)
- [Learning Interpolations between Boltzmann Densities](https://mlsanity.com/paper/2301.07388/) (2023)
- [Reverse Diffusion Monte Carlo](https://mlsanity.com/paper/2307.02037/) (2023)
- [Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo](https://mlsanity.com/paper/1710.02736/) (2017)
- [Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincar'e Inequality](https://mlsanity.com/paper/2303.03589/) (2023)
- [Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Sampling](https://mlsanity.com/paper/2407.16936/) (2024)
- [Dynamical Measure Transport and Neural PDE Solvers for Sampling](https://mlsanity.com/paper/2407.07873/) (2024)
- [Zeroth-Order Sampling Methods for Non-Log-Concave Distributions: Alleviating Metastability by Denoising Diffusion](https://mlsanity.com/paper/2402.17886/) (2024)
- [In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies](https://mlsanity.com/paper/2405.01425/) (2024)
- [Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Bounds](https://mlsanity.com/paper/1911.03043/) (2019)
- [Improved Order Analysis and Design of Exponential Integrator for Diffusion Models Sampling](https://mlsanity.com/paper/2308.02157/) (2023)
- [Efficient Training of Energy-Based Models Using Jarzynski Equality](https://mlsanity.com/paper/2305.19414/) (2023)
- [Faster Sampling without Isoperimetry via Diffusion-based Monte Carlo](https://mlsanity.com/paper/2401.06325/) (2024)

## Built on by (most cited first, 11 of 11)

- [Trust Region Constrained Measure Transport in Path Space for Stochastic Optimal Control and Inference](https://mlsanity.com/paper/2508.12511/) (2025)
- [MDNS: Masked Diffusion Neural Sampler via Stochastic Optimal Control](https://mlsanity.com/paper/2508.10684/) (2025)
- [FEAT: Free energy Estimators with Adaptive Transport](https://mlsanity.com/paper/2504.11516/) (2025)
- [Proximal Diffusion Neural Sampler](https://mlsanity.com/paper/2510.03824/) (2025)
- [Bridge Matching Sampler: Scalable Sampling via Generalized Fixed-Point Diffusion Matching](https://mlsanity.com/paper/2603.00530/) (2026)
- [Non-equilibrium Annealed Adjoint Sampler](https://mlsanity.com/paper/2506.18165/) (2025)
- [Telegrapher's Generative Model via Kac Flows](https://mlsanity.com/paper/2506.20641/) (2025)
- [End-To-End Learning of Gaussian Mixture Priors for Diffusion Sampler](https://mlsanity.com/paper/2503.00524/) (2025)
- [Tracking large chemical reaction networks and rare events by neural networks](https://mlsanity.com/paper/2512.10309/) (2025)
- [Sample-efficient evidence estimation of score based priors for model selection](https://mlsanity.com/paper/2602.20549/) (2026)
- [Properties and limitations of geometric tempering for gradient flow dynamics](https://mlsanity.com/paper/2604.20301/) (2026)

## Abstract (arXiv)

Given an unnormalized probability density πproptoe-V, estimating its normalizing constant Z=intℝde-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 π 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 widetildeOleft(fracdβ2A2varepsilon4right) for estimating Z within varepsilon relative error with high probability, where β is the smoothness of V and A denotes the action of a curve of probability measures interpolating π 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.