Universal Bounds for Self-Normalized Kullback-Leibler Estimation
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.
Related
- On The Linear Convergence of Bregman Proximal Gradient Methods with Applications to Kullback--Leibler regression
- Consistency of variational approximations under bounded Kullback-Leibler divergence
- Kullback–Leibler Asymmetry and Information Homogeneity in Natural Exponential Families
- Beyond the Kullback--Leibler divergence: the likelihood-ratio distribution as a detectability measure
- Unbiased estimation of normalized scale-invariant indices under the Gamma distribution
BibTeX
@misc{phan2026universal,
title = {{Universal Bounds for Self-Normalized Kullback-Leibler Estimation}},
author = {Buu Phan and Lester Mackey and David Alvarez-Melis},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.12851},
eprint = {2610.12851},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.12851},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Universal Bounds for Self-Normalized Kullback-Leibler Estimation
AU - Buu Phan
AU - Lester Mackey
AU - David Alvarez-Melis
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2610.12851
UR - https://arxiv.org/abs/2610.12851
AB - 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.
ER -