# Provable benefits of annealing for estimating normalizing constants: Importance Sampling, Noise-Contrastive Estimation, and beyond

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 53 references that are in the map.
- First posted on arXiv 5 Oct 2023.

## Builds on (most cited first, 17 of 17)

- [Score-Based Generative Modeling through Stochastic Differential Equations](https://mlsanity.com/paper/2011.13456/) (2020)
- [Flow Contrastive Estimation of Energy-Based Models](https://mlsanity.com/paper/1912.00589/) (2019)
- [Density Estimation in Infinite Dimensional Exponential Families](https://mlsanity.com/paper/1312.3516/) (2013)
- [An invitation to sequential Monte Carlo samplers](https://mlsanity.com/paper/2007.11936/) (2020)
- [The Thermodynamic Variational Objective](https://mlsanity.com/paper/1907.00031/) (2019)
- [Analyzing and Improving the Optimization Landscape of Noise-Contrastive Estimation](https://mlsanity.com/paper/2110.11271/) (2021)
- [q-Paths: Generalizing the Geometric Annealing Path using Power Means](https://mlsanity.com/paper/2107.00745/) (2021)
- [All in the Exponential Family: Bregman Duality in Thermodynamic Variational Inference](https://mlsanity.com/paper/2007.00642/) (2020)
- [The Optimal Noise in Noise-Contrastive Learning Is Not What You Think](https://mlsanity.com/paper/2203.01110/) (2022)
- [Improving Mutual Information Estimation with Annealed and Energy-Based Bounds](https://mlsanity.com/paper/2303.06992/) (2023)
- [Adaptive Annealed Importance Sampling with Constant Rate Progress](https://mlsanity.com/paper/2306.15283/) (2023)
- [Analysis of Noise Contrastive Estimation from the Perspective of Asymptotic Variance](https://mlsanity.com/paper/1808.07983/) (2018)
- [Pitfalls of Gaussians as a noise distribution in NCE](https://mlsanity.com/paper/2210.00189/) (2022)
- [Variational Optimization of Annealing Schedules](https://mlsanity.com/paper/1502.05313/) (2015)
- [Warp Bridge Sampling: The Next Generation](https://mlsanity.com/paper/1609.07690/) (2016)
- [Improving Bridge estimators via f-GAN](https://mlsanity.com/paper/2106.07462/) (2021)
- [Optimizing the Noise in Self-Supervised Learning: from Importance Sampling to Noise-Contrastive Estimation](https://mlsanity.com/paper/2301.09696/) (2023)

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

- [Density Ratio Estimation with Conditional Probability Paths](https://mlsanity.com/paper/2502.02300/) (2025)
- [Annealing Flow Generative Models Towards Sampling High-Dimensional and Multi-Modal Distributions](https://mlsanity.com/paper/2409.20547/) (2024)
- [Complexity Analysis of Normalizing Constant Estimation: from Jarzynski Equality to Annealed Importance Sampling and beyond](https://mlsanity.com/paper/2502.04575/) (2025)
- [The Cosine Schedule is Fisher-Rao-Optimal for Masked Discrete Diffusion Models](https://mlsanity.com/paper/2508.04884/) (2025)
- [Provable Convergence and Limitations of Geometric Tempering for Langevin Dynamics](https://mlsanity.com/paper/2410.09697/) (2024)
- [Path-Guided Particle-based Sampling](https://mlsanity.com/paper/2412.03312/) (2024)
- [BoltzNCE: Learning Likelihoods for Boltzmann Generation with Stochastic Interpolants and Noise Contrastive Estimation](https://mlsanity.com/paper/2507.00846/) (2025)
- [SPACE: Noise Contrastive Estimation Stabilizes Self-Play Fine-Tuning for Large Language Models](https://mlsanity.com/paper/2512.07175/) (2025)
- [Hitchhiker's guide on the relation of Energy-Based Models with other generative models, sampling and statistical physics: a comprehensive review](https://mlsanity.com/paper/2406.13661/) (2024)
- [A Minimum Variance Path Principle for Accurate and Stable Score-Based Density Ratio Estimation](https://mlsanity.com/paper/2602.00834/) (2026)
- [A Unified View on Learning Unnormalized Distributions via Noise-Contrastive Estimation](https://mlsanity.com/paper/2409.18209/) (2024)
- [Learning Energy-Based Models from Stochastic Interpolants using Spatiotemporal Differences](https://mlsanity.com/paper/2605.26850/) (2026)
- [Partition Function Estimation under Bounded f-Divergence](https://mlsanity.com/paper/2602.23535/) (2026)

## Abstract (arXiv)

Recent research has developed several Monte Carlo methods for estimating the normalization constant (partition function) based on the idea of annealing. This means sampling successively from a path of distributions that interpolate between a tractable "proposal" distribution and the unnormalized "target" distribution. Prominent estimators in this family include annealed importance sampling and annealed noise-contrastive estimation (NCE). Such methods hinge on a number of design choices: which estimator to use, which path of distributions to use and whether to use a path at all; so far, there is no definitive theory on which choices are efficient. Here, we evaluate each design choice by the asymptotic estimation error it produces. First, we show that using NCE is more efficient than the importance sampling estimator, but in the limit of infinitesimal path steps, the difference vanishes. Second, we find that using the geometric path brings down the estimation error from an exponential to a polynomial function of the parameter distance between the target and proposal distributions. Third, we find that the arithmetic path, while rarely used, can offer optimality properties over the universally-used geometric path. In fact, in a particular limit, the optimal path is arithmetic. Based on this theory, we finally propose a two-step estimator to approximate the optimal path in an efficient way.