# Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Bounds

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Nov 2019.

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

- [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)
- [Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions](https://mlsanity.com/paper/2106.05480/) (2021)
- [The query complexity of sampling from strongly log-concave distributions in one dimension](https://mlsanity.com/paper/2105.14163/) (2021)
- [Fisher information lower bounds for sampling](https://mlsanity.com/paper/2210.02482/) (2022)
- [Query lower bounds for log-concave sampling](https://mlsanity.com/paper/2304.02599/) (2023)
- [Complexity Analysis of Normalizing Constant Estimation: from Jarzynski Equality to Annealed Importance Sampling and beyond](https://mlsanity.com/paper/2502.04575/) (2025)
- [Convergence Rates for Non-Log-Concave Sampling and Log-Partition Estimation](https://mlsanity.com/paper/2303.03237/) (2023)
- [Sampling Approximately Low-Rank Ising Models: MCMC meets Variational Methods](https://mlsanity.com/paper/2202.08907/) (2022)
- [Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants](https://mlsanity.com/paper/2210.06539/) (2022)
- [Nonlinear Assimilation via Score-based Sequential Langevin Sampling](https://mlsanity.com/paper/2411.13443/) (2024)
- [A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplers](https://mlsanity.com/paper/2405.16736/) (2024)
- [Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions](https://mlsanity.com/paper/2310.11445/) (2023)
- [Kernelized Normalizing Constant Estimation: Bridging Bayesian Quadrature and Bayesian Optimization](https://mlsanity.com/paper/2401.05716/) (2024)
- [Evaluation and Comparison of Deep Learning Methods for Pavement Crack Identification with Visual Images](https://mlsanity.com/paper/2112.10390/) (2021)
- [Asymptotically Optimal Change Detection for Unnormalized Pre- and Post-Change Distributions](https://mlsanity.com/paper/2410.14615/) (2024)

## Abstract (arXiv)

Estimating the normalizing constant of an unnormalized probability distribution has important applications in computer science, statistical physics, machine learning, and statistics. In this work, we consider the problem of estimating the normalizing constant Z=intℝd e-f(x),dx to within a multiplication factor of 1 ± varepsilon for a μ-strongly convex and L-smooth function f, given query access to f(x) and nabla f(x). We give both algorithms and lowerbounds for this problem. Using an annealing algorithm combined with a multilevel Monte Carlo method based on underdamped Langevin dynamics, we show that widetildeOBigl(fracd4/3kappa + d7/6kappa7/6varepsilon2Bigr) queries to nabla f are sufficient, where kappa= L / μ is the condition number. Moreover, we provide an information theoretic lowerbound, showing that at least fracd1-o(1)varepsilon2-o(1) queries are necessary. This provides a first nontrivial lowerbound for the problem.