Partition Function Estimation under Bounded f-Divergence
| Authors | Adam Block & Abhishek Shetty |
| Year | 2026 |
| Field | Statistics / ML |
| arXiv | 2602.23535 |
| Download | |
| Categories | stat.ML, cs.LG |
Abstract
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 -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 -divergences as well as a generalization of the classical Paley-Zygmund inequality.
Engineering Breakdown
Plain English
This paper solves the problem of estimating partition functions—a fundamental quantity in statistics and machine learning—when you have samples from a proposal distribution and access to an unnormalized density ratio between a target and proposal distribution. Prior work required strong assumptions about the domain structure or model geometry to provide theoretical guarantees, but this paper provides a general, information-theoretic framework that depends only on how the proposal and target distributions relate to each other. The key innovation is introducing the integrated coverage profile, a functional that measures how much target probability mass exists in regions where the density ratio is large. The authors prove that this quantity exactly characterizes the sample complexity of multiplicative partition function estimation and provide matching upper and lower bounds, giving a complete theoretical picture.
Core Technical Contribution
The paper's core contribution is shifting from geometry-dependent to divergence-dependent analysis of partition function estimation. Instead of assuming the domain has nice structure or the model has convex geometry, the authors characterize complexity purely through the integrated coverage profile—a functional measuring target mass concentration in high-density-ratio regions. This is novel because it removes structural assumptions entirely and instead focuses on the fundamental information-theoretic relationship between proposal and target distributions. The matching upper and lower bounds prove that integrated coverage is not just sufficient but also necessary, making it a tight characterization of sample complexity.
How It Works
The setup is: you have access to samples from a proposal distribution q and can evaluate an unnormalized density ratio h(x) = p(x)/q(x), where p is the target. The goal is to estimate the partition function Z = ∫ p(x) dx with multiplicative accuracy guarantees. The authors introduce the integrated coverage profile, which formally quantifies what fraction of target mass p(x) appears in regions where h(x) exceeds a given threshold. The algorithm likely works by adaptively sampling from the proposal, reweighting by the density ratio, and aggregating estimates across regions of varying density ratio magnitude. The theoretical analysis derives sample complexity bounds expressed in terms of this coverage profile, showing that regions with higher density ratios contribute more to estimation difficulty. The paper then provides both algorithms that achieve the upper bounds and information-theoretic lower bounds that prove no algorithm can do significantly better.
Production Impact
For engineers building Monte Carlo inference pipelines, this provides a principled way to predict how many samples you'll need for accurate partition function estimates without redesigning your sampler or domain. If you're using importance sampling or ratio-based methods for posterior inference, likelihood computation, or evidence estimation, this framework lets you quantify sample complexity directly from the mismatch between your proposal and target. In practice, you'd measure or estimate the integrated coverage profile empirically (how much target mass sits in low/medium/high density ratio regions) and use that to set your sample budget and confidence intervals. The trade-off is computational: computing tight coverage bounds may require preliminary runs, but it eliminates guessing at sample sizes and dramatically improves sample efficiency for well-chosen proposals. This is particularly valuable in Bayesian inference and generative modeling where partition functions are expensive and proposals are carefully engineered.
Limitations and When Not to Use This
The paper assumes you have exact sample access to the proposal distribution and can exactly evaluate the unnormalized density ratio h(x), which breaks down if either source has approximation error or bias. For high-dimensional problems, the integrated coverage profile may be expensive to estimate empirically, and the paper doesn't provide practical algorithms for computing or approximating it in very high dimensions beyond the theoretical framework. The analysis is restricted to multiplicative partition function estimation; additive error bounds or settings with bounded support may require different techniques. The paper also doesn't address the case where the proposal and target diverge significantly in tail regions, which can cause density ratios to become numerically unstable in practice—a common problem in real inference systems.
Research Context
This work builds on the classical literature of partition function estimation (e.g., importance sampling, annealed importance sampling) and connects to recent information-theoretic work on f-divergences and optimal transport. It extends beyond geometry-dependent analyses (like those assuming log-concavity or convexity) by instead leveraging divergence-based metrics that are agnostic to domain structure. The paper likely improves upon prior work by removing restrictive assumptions—previous bounds required curvature bounds, diameter bounds, or other geometric properties, whereas this work only needs the empirical relationship between proposal and target. This opens research directions in adaptive proposal selection, where you'd learn a proposal distribution that minimizes the integrated coverage profile, and in variational inference where you'd optimize a proposal specifically to tighten partition function estimates.
:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::