New bounds improve understanding of entropy based KL divergence estimates
Universal Bounds for Self-Normalized Kullback-Leibler Estimation
Machine Learning
Summary
Measuring how different two things are, like two groups of animals or sets of data, can be complicated. This paper looks at a new way to estimate this difference using a method called KL divergence and shows it won’t be wildly off by more than a certain small amount, no matter how much data you have. It also explores how taking weighted samples affects the measurements, without needing strict limits on the numbers involved. The authors apply this to improving how computer programs that generate new data are checked and to making certain types of data coding more efficient.
What this means in practice
- •For generative model engineers: Provide guaranteed bounds on divergence estimates used when tuning and testing generative AI models with importance sampling approaches.
- •For data compression teams: Offer moment-free finite-sample guarantees that help assess the cost and reliability of entropy-based coding methods.
A theory result. No direct application yet.
Authors
Buu Phan, Lester Mackey, David Alvarez-Melis
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.