Universal Bounds for Self-Normalized Kullback-Leibler Estimation

Buu Phan; Lester Mackey; David Alvarez-Melis

stat.MLOct 9, 2026

Universal Bounds for Self-Normalized Kullback-Leibler Estimation

Authors: Buu Phan, Lester Mackey, David Alvarez-Melis

Organizations: University of Toronto · Microsoft Research · Harvard University

Abstract

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.

Figures & tables

Panel of Figure 1 — Figure 1: Soft Best-of- $N$ and its KL guarantees. The population KL is the limiting SBoN divergence as $N\to\infty$ . Our estimator $\mathbb{E}[\widehat{D}_{N}]$ is tighter than the guarantee of Aminian et al. (2026) and can overshoot the population KL by at most $\log 2$ . In contrast, the bound of Aminian et al. (2026) depends only on the reward range and does not account for the geometry of the reward distribution under the base policy. It converges to $\beta R_{\max}$ , which is $12$ in this example, corresponding to the first column and last row of Figure 2(a) .

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 3 — Figure 3: Illustration of contraction toward the anchor $a$ , using $R_{a}(s)=(s-a)^{2}$ .

Panel of Figure 4 — Figure 4: Finite-sample slack in the Bernoulli setting with $p(0)=1-\epsilon_{1}$ , and $q(0)=\epsilon_{2}$ . (a) Maximum slack over the considered sample sizes $N$ as a function of $(\epsilon_{1},\epsilon_{2})$ . The maximum observed slack is indicated by the red star. (b) Exact finite-sample slack and its Monte Carlo approximation as $N$ varies for the parameter pair $(\epsilon_{1},\epsilon_{2})=(10^{-8},\,8.09\times 10^{-2})$ attaining the largest observed slack.

Panel of Figure 5 — Figure 5: Finite-sample behavior of the SNIS KL estimator for Weibull targets $p_{\mu,\nu}=\mathrm{Wei}(\mu,\nu)$ with fixed proposal $Q=\mathrm{Wei}(1,1)$ . Left: maximum slack $\Delta^{*}(\mu,\nu)$ over the shape–scale family. Right: trajectories of the gap $\mathbb{E}[\widehat{D}_{N}]-D_{\mathrm{KL}}(p\|q)$ as $N$ increases.

Figure 6: Profiled SNIS slack in the rare-bump setting. For each

(A,S)

and fixed

\beta

, we plot

\Delta^{*}(A,S;\beta):=\max_{N}\left\{\mathbb{E}[\widehat{D}_{N}]-D_{\mathrm{KL}}(p\|q)\right\}.

The red star marks the maximizing geometry for each value of

\beta

. Further decreasing

\beta

below

0.01

does not substantially increase the observed slack, suggesting that the maximum slack approaches a limiting value as

\beta\to 0

Panel of Figure 7 — Figure 7: Exact discrete validation of the ordering between $L_{N,4}$ $D_{\mathrm{KL}}(p_{N}\|q)$ , $\mathbb{E}[\widehat{D}_{N}]$ , and $D_{\mathrm{KL}}(p\|q)$ . The top row shows $p$ and $q$ for four representative settings, while the bottom row shows the corresponding divergences as a function of $N$ .

Panel of Figure 8 — Figure 8: Upper and lower estimators under equal computational budgets for the bimodal-target, unimodal-proposal experiment. The dashed curve shows the finite-sample divergence $D_{\mathrm{KL}}(p_{N}\|q)$ . Points and error bars show the empirical means and central 95% sampling intervals of the upper and lower estimators across independent repetitions. For each $(N,\text{budget})$ , the auxiliary sample size $M$ for the lower estimator is chosen to minimize the empirical interval width.

Panel of Figure 9 — Figure 9: Finite-compute behavior of the upper and lower estimators for shifted-Gaussian targets with increasing target–proposal mismatch, similar to Figure 8 but with the shifted Gaussian setup in Section 2.3 .

Family	Level	$\pi_{0}$	$\pi_{\beta}$	$D_{\mathrm{KL}}(\pi_{\beta}\\|\pi_{0})$
Mode mismatch Top row in Figure 10	1	$\mathcal{N}(0,1.25^{2})$	$\frac{1}{2}\mathcal{N}(-2,0.45^{2})+\frac{1}{2}\mathcal{N}(2,0.45^{2})$	1.13
	2	$\mathcal{N}(0,1.25^{2})$	$\frac{1}{2}\mathcal{N}(-3,0.45^{2})+\frac{1}{2}\mathcal{N}(3,0.45^{2})$	2.59
	3	$\mathcal{N}(0,1.25^{2})$	$\frac{1}{2}\mathcal{N}(-4,0.45^{2})+\frac{1}{2}\mathcal{N}(4,0.45^{2})$	4.12
	4	$\mathcal{N}(0,1.25^{2})$	$\frac{1}{2}\mathcal{N}(-5,0.45^{2})+\frac{1}{2}\mathcal{N}(5,0.45^{2})$	4.89
Tail mismatch Bottom row in Figure 10	1	$\mathcal{N}(0,1.00^{2})$	$\operatorname{Cauchy}(0,1)$	0.22
	2	$\mathcal{N}(0,0.65^{2})$	$\operatorname{Cauchy}(0,1)$	0.55

Appendix

Table 1: Distribution pairs used in the SNIS experiments in Appendix J.3 . The proposal distribution is denoted by

\pi_{0}

and the target distribution by

\pi_{\beta}

. For the irregular PMFs,

z=x/6

, with

x\in[-6,6]

Kullback-Leibler Divergence

See all 27 papers

Partition Function Estimation under Bounded f-Divergence
Feb 26, 2026Adam Block, Abhishek ShettyImportance Sampling
Department of Computer Science, Columbia University · Department of Electrical Engineering, Columbia University · MIT
Uniform Discrete Diffusion Models are Minimax Optimal for Estimating Distributions with Small Effective Support Size
Oct 6, 2026Dongsun Yoon, Saptarshi ChakrabortyMinimax Estimation Statistical Learning Theory
Department of Statistics, University of Michigan
Mode Coverage in Normalizing Flow Boltzmann Generators via Log-Ratio Variation
Sep 8, 2026Qi Feng, Rongjie Lai, Di Qi +1Normalizing Flows Molecular Generation
Department of Mathematics, Florida State University, Tallahassee, FL 32306 · Department of Mathematics, Purdue University, West Lafayette, IN 47907

Feb 26, 2026J/K move · Enter open · S save

Partition Function Estimation under Bounded f-Divergence

Adam Block, Abhishek Shetty

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

Importance Sampling

Open paper AskPDF 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.

Abstract

Kullback-Leibler Divergence

Explore similar work

Partition Function Estimation under Bounded f-Divergence

Uniform Discrete Diffusion Models are Minimax Optimal for Estimating Distributions with Small Effective Support Size

Mode Coverage in Normalizing Flow Boltzmann Generators via Log-Ratio Variation