arXiv：cs.LG· Buu Phan, Lester Mackey, David Alvarez-Melis·· 13 小时前
自归一化 KL 估计的通用界
Universal Bounds for Self-Normalized Kullback-Leibler Estimation
AI 导读
该研究为基于归一化重要性权重构建的 KL 散度熵估计器证明了通用有限样本界：无论样本量多少，其期望超出目标-提议 KL 散度至多 log 2，且不要求重要性权重有界或高阶矩有限。作者进一步刻画了重要性加权重采样分布与提议分布之间的 KL 散度上界，并将其应用于 Soft Best-of-N 采样和相对熵编码，得到有限样本策略散度证书与无矩编码代价界。
正文
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.
| Subjects: | Machine Learning (stat.ML); Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.12851 [stat.ML] |
| (or arXiv:2610.12851v1 [stat.ML] for this version) | |
| https://doi.org/10.48550/arXiv.2610.12851 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Buu Phan [view email]
[v1]
Fri, 9 Oct 2026 01:20:22 UTC (796 KB)
来源：arXiv：cs.LG · arxiv.org