← Back to all news
arXiv Machine Learning

Universal Bounds for Self-Normalized Kullback-Leibler Estimation

The paper introduces an entropy-based estimator for Kullback-Leibler divergence that uses normalized importance weights. It establishes a universal finite-sample bound, proving that the estimator’s expectation can exceed the true target‑proposal KL divergence by no more than λ2, regardless of sample size. Additionally, it shows that the KL divergence between the distribution produced by importance‑weighted resampling and the proposal is bounded by both the estimator’s expectation and the target‑proposal KL divergence, without requiring bounded weights or finite higher moments. The authors apply these theoretical results to test‑time alignment of generative models via Soft Best‑of‑N sampling and to relative entropy coding, yielding finite‑sample policy‑divergence guarantees and moment‑free bounds on coding cost.

Related stories

arXiv Machine Learning
Oct 8

Efficient Best-of-N policy evaluation for inference-time alignment

The paper introduces a sample‑only framework for evaluating and selecting Best‑of‑N (BoN) inference‑time alignment policies without needing response likelihoods. By exploiting the order‑statistic structure of BoN, the authors express required density ratios through score‑rank probabilities that can be estimated from samples alone, and develop a doubly robust estimator (BoN‑DR) that reuses a shared auxiliary sample pool across candidate budgets. The method provides valid asymptotic inference even with reward estimator misspecification, proves efficiency, and offers two selection rules—maximizing estimated policy value or a lower confidence bound—to avoid over‑optimization and guarantee no harm, as demonstrated on synthetic data and GSM8K.

By Jonas Schweisthal, Yuxin Wang, Athiya Deviyani, Stefan Feuerriegel, Dennis Frauen
safety
More like this →
arXiv Machine Learning
Oct 7

Sample-Optimal Estimation of the Fr\'echet Inception Distance

The paper investigates the sample complexity of estimating the Fréchet Inception Distance (FID) between high‑dimensional Gaussian distributions when one distribution is known. It establishes tight bias and variance bounds for the empirical plug‑in estimator, shows how higher‑order extrapolation reduces bias, and introduces a new Relative Taylor Debiasing (RTD) algorithm that achieves optimal sample complexity. Experiments on synthetic data and ImageNet confirm the theoretical predictions and demonstrate RTD’s superior accuracy with limited samples.

By Ziyun Chen, Jerry Li, Kevin Tian, Yusong Zhu
ragsafety
More like this →
arXiv Machine Learning
Aug 4

Tail-Aware Information-Theoretic Bounds for LLM Alignment under Heavy-Tailed Rewards

arXiv:2604. 10727v2 Announce Type: replace-cross Abstract: Classical information-theoretic learning bounds typically rely on KL mutual information and moment-generating-function (MGF) arguments, which are well matched to bounded or sub-Gaussian losses but can be ineffective when losses or rewards are heavy-tailed.

By Huiming Zhang, Binghan Li, Wan Tian, Qiang Sun
llmsreinforcement-learningsafety
More like this →