# Partition Function Estimation under Bounded f-Divergence

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 43 references that are in the map.
- First posted on arXiv 26 Feb 2026.

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

- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Importance Weighted Autoencoders](https://mlsanity.com/paper/1509.00519/) (2015)
- [A* Sampling](https://mlsanity.com/paper/1411.0030/) (2014)
- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Self-Improvement in Language Models: The Sharpening Mechanism](https://mlsanity.com/paper/2412.01951/) (2024)
- [Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignment](https://mlsanity.com/paper/2503.21878/) (2025)
- [The Coverage Principle: How Pre-Training Enables Post-Training](https://mlsanity.com/paper/2510.15020/) (2025)
- [Accelerating RL for LLM Reasoning with Optimal Advantage Regression](https://mlsanity.com/paper/2505.20686/) (2025)
- [The Sample Complexity of Approximate Rejection Sampling with Applications to Smoothed Online Learning](https://mlsanity.com/paper/2302.04658/) (2023)
- [Provable benefits of annealing for estimating normalizing constants: Importance Sampling, Noise-Contrastive Estimation, and beyond](https://mlsanity.com/paper/2310.03902/) (2023)
- [A Faster Approximation Algorithm for the Gibbs Partition Function](https://mlsanity.com/paper/1608.04223/) (2016)
- [Some Notes on the Sample Complexity of Approximate Channel Simulation](https://mlsanity.com/paper/2405.04363/) (2024)
- [Optimality in importance sampling: a gentle survey](https://mlsanity.com/paper/2502.07396/) (2025)

## Abstract (arXiv)

We study the statistical complexity of estimating partition functions given sample access to a proposal distribution and an unnormalized density ratio for a target distribution. While partition function estimation is a classical problem, existing guarantees typically rely on structural assumptions about the domain or model geometry. We instead provide a general, information-theoretic characterization that depends only on the relationship between the proposal and target distributions. Our analysis introduces the integrated coverage profile, a functional that quantifies how much target mass lies in regions where the density ratio is large. We show that integrated coverage tightly characterizes the sample complexity of multiplicative partition function estimation and provide matching lower bounds. We further express these bounds in terms of f-divergences, yielding sharp phase transitions depending on the growth rate of f and recovering classical results as a special case while extending to heavy-tailed regimes. Matching lower bounds establish tightness in all regimes. As applications, we derive improved finite-sample guarantees for importance sampling and self-normalized importance sampling, and we show a strict separation between the complexity of approximate sampling and counting under the same divergence constraints. Our results unify and generalize prior analyses of importance sampling, rejection sampling, and heavy-tailed mean estimation, providing a minimal-assumption theory of partition function estimation. Along the way we introduce new technical tools including new connections between coverage and f-divergences as well as a generalization of the classical Paley-Zygmund inequality.