Partition Function Estimation under Bounded f-Divergence

Adam Block; Abhishek Shetty

stat.MLFeb 26, 2026

Partition Function Estimation under Bounded f-Divergence

Authors: Adam Block, Abhishek Shetty

Organizations: Department of Computer Science, Columbia University · Department of Electrical Engineering, Columbia University · MIT

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 $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.

Figures & tables

Figure 1: Sample complexity ( $n$ ) regimes for estimating $Z$ to $(1\pm\varepsilon)$ accuracy based on the growth rate of the $f$ defining $\mathrm{D}_{f}\left(\nu\middle\|\mu\right)$ .

Importance Sampling

Importance sampling uses weighted samples from easier or adaptive distributions to estimate quantities under a target distribution.

See all 69 papers

Oct 9, 2026

Universal Bounds for Self-Normalized Kullback-Leibler Estimation

This work studies an entropy-based estimator of Kullback-Leibler (KL) divergence constructed from normalized importance weights. We prove a universal finite-sample bound showing that its expectation can exceed the target-proposal KL divergence by at most

\log 2

for any sample size. We then characterize the KL divergence between the distribution induced by importance-weighted resampling and the proposal, showing that it is upper bounded by both the expectation of the entropy-based estimator and the target-proposal KL divergence. Importantly, these bounds require neither bounded importance weights nor finite higher moments. We apply these results to test-time alignment of generative models via Soft Best-of-

N

sampling, an importance-sampling-based scaling technique proposed by Verdun et al. (2025), and to relative entropy coding, obtaining finite-sample policy-divergence certificates and moment-free bounds on coding cost.

Buu Phan, Lester Mackey, David Alvarez-Melis

University of Toronto · Microsoft Research · Harvard University

Kullback-Leibler Divergence Importance Sampling

Ask PDF

Feb 18, 2026

Ratio Covers of Convex Sets and Optimal Mixture Density Estimation

We study density estimation in Kullback-Leibler divergence: given an i.i.d. sample from an unknown density

p^\star

, the goal is to construct an estimator

\widehat{p}

such that

\mathrm{KL}(p^\star,\widehat{p})

is small with high probability. We consider two fundamental settings involving a finite dictionary of densities: (i) model aggregation, where

p^\star

belongs to the dictionary, and (ii) convex aggregation (mixture density estimation), where

p^\star

is a mixture of densities from the dictionary. Crucially, we make no assumption on the base densities: their ratios may be unbounded and their supports may differ. For both problems, we identify the best possible high-probability guarantees in terms of the dictionary size, sample size, and confidence level. These optimal rates are higher than those achievable when density ratios are bounded by absolute constants; for mixture density estimation, they match existing lower bounds in the special case of discrete distributions. Our analysis of the mixture case hinges on two new covering results. First, we provide a sharp, distribution-free upper bound on the local Hellinger entropy of the class of mixtures of

M

distributions. Second, we prove an optimal ratio covering theorem for convex sets: for every convex compact set

K \subset \mathbb{R}_+^d

, there exists a subset

A \subset K

with at most

2^{O(d)}

elements such that each element of

K

is coordinate-wise dominated by an element of

A

up to a universal constant factor. This geometric result is of independent interest; notably, it yields new cardinality estimates for

\varepsilon

-approximate Pareto sets in multi-objective optimization with convex feasible set.

Spencer Compton, Gábor Lugosi, Jaouad Mourtada +2

Department of Computer Science, Stanford University. · Department of Economics and Business, Pompeu Fabra University, Barcelona, Spain; ICREA, Barcelona, Spain; Barcelona Graduate School of Economics. · Department of Statistics, CREST/ENSAE Paris, Palaiseau, France. +2

Density Estimation Minimax Estimation

Ask PDF

Oct 8, 2026

Product Monte Carlo: Expectation Under a Product of Densities

Aggregating independently computed sub-sample inferences is a well-known challenge in large-scale Bayesian computation, federated learning, and opinion pooling. The core problem is to approximate a distribution whose density is proportional to a product of individual densities. We propose Product Monte Carlo (PMC), an algorithm for computing arbitrary expectations under a product of densities using only Monte Carlo draws from individual densities. We turn the intractable product expectation into a regression problem by expressing it through a family of computable conditional expectations. Besides the point estimate, our fully Bayesian regression formulation provides coherent uncertainty quantification and principled diagnostics. We establish theoretical guarantees on consistency and characterize convergence rates for the PMC estimator. Across simulated and real-data experiments varying the number, dimensionality, and heterogeneity of the component distributions, PMC achieves higher estimation accuracy, better-calibrated uncertainty coverage, and improved scalability at a lower computational cost than existing methods. In addition, PMC requires no density evaluation, making it applicable to simulation-based inference, as we demonstrate in an application with protein images.

Pietro Carlotti, Sifan Liu, Yuling Yao

University of Texas at Austin, Department of Statistics and Data Sciences · Duke University, Department of Statistical Science

Bayesian Inference

Ask PDF

Abstract

Importance Sampling

Explore similar work

Universal Bounds for Self-Normalized Kullback-Leibler Estimation

Ratio Covers of Convex Sets and Optimal Mixture Density Estimation

Product Monte Carlo: Expectation Under a Product of Densities