PaperlayerView exact revision on arXiv

Source-linked AI summary

Universal Bounds for Self-Normalized Kullback-Leibler Estimation

Buu Phan, Lester Mackey, David Alvarez-Melis

arXiv:2610.12851v1stat.MLcs.LG

TL;DR

Finite-sample guarantees for self-normalized importance sampling are challenging because random normalization couples samples, and sharper bounds typically require bounded weights or higher moments. The paper analyzes an entropy estimator of normalized weights, proves a universal log 2 excess bound, and bounds resampled-distribution KL by both the estimator expectation and the target–proposal KL.

  • Problem

    At finite sample sizes, random normalization couples self-normalized importance-sampling samples, and sharper nonasymptotic guarantees typically require bounded weights or finite higher moments.

    Source: §1 · pp. 1–2

  • Method

    The paper studies an entropy-based estimator of target–proposal KL constructed from normalized importance weights and bounds the divergence of the importance-weighted resampling distribution.

    Source: §1 · pp. 1–2

  • Results

    log 2: for every N, E[ bDN] < DKL(p∥q) + log 2, while DKL(pN∥q) is bounded by both E[ bDN] and DKL(p∥q).

    Source: §1 · p. 2

  • Takeaways & Limitations

    The estimator provides a directly estimated upper bound on resampled-distribution KL without explicitly evaluating pN.

    Source: §1 · p. 2

    For Soft Best-of-N, the reward-range-and-N bound need not be tight and does not capture the asymptotic behavior as πN,β converges to πβ.

    Source: §2.2 · pp. 3–4

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper studies a normalized-weight entropy estimator for target–proposal KL divergence, whose finite-sample guarantees are difficult because random normalization couples samples. It proves a universal excess bound and shows that the KL divergence of the resampled distribution is bounded by both the estimator’s expectation and the target–proposal divergence.

1 INTRODUCTION

  • The studied KL estimator is the entropy of normalized importance weights and remains computable when the target normalizing constant is unknown.At finite N, random normalization couples samples, while sharper nonasymptotic guarantees typically require bounded weights or finite higher moments.Source: §1 · pp. 1–2
  • For every sample size N, E[ bDN] < DKL(p∥q) + log 2, without bounded importance weights or additional moment assumptions.The authors note that log 2 is unlikely to be tight; exhaustive search suggests the optimal universal slack may be near 0.15.Source: §1 · p. 2
  • For every N, DKL(pN∥q) is bounded above by both E[ bDN] and DKL(p∥q).The estimator gives a straightforward upper bound without explicitly evaluating pN, the distribution induced by proposal sampling and resampling.Source: §1 · p. 2
  • A lower-bound estimator and the resampling upper bound provide a practical bracket for DKL(pN∥q) without explicitly evaluating pN.As M then B increase, the lower-bound estimator converges almost surely to the divergence.Source: §1 · p. 2
  • The bounds are applied to test-time alignment via Soft Best-of-N sampling and to approximate relative entropy coding, without higher-moment conditions.The paper reports tighter bounds across relevant regimes in both settings.Source: §1 · p. 2

2 DIVERGENCE GUARANTEES FOR SOFT BEST-OF-N

Soft Best-of-N approximates a reward-tilted policy using samples from the base policy, and the paper gives finite-sample guarantees for its distributional shift. The estimator tracks the finite-N divergence across tested reward geometries, while its expected value exceeds the population divergence by at most log 2.

2.1 Test-Time Alignment with KL Control

  • Soft Best-of-N uses self-normalized importance sampling to approximate a reward-tilted policy from base-policy samples and reward evaluations.The goal is to approximate the population Gibbs policy while evaluating expected reward and distributional shift.Source: §2.1 · p. 3, §2.2 · p. 3

2.2 Soft Best-of-N Alignment and KL Guarantees

  • The finite-N SBoN policy is no farther from the base policy than the population Gibbs policy, and converges to it when the normalizing constant is finite.The analysis also applies to continuous generative models using importance-weighted sampling or resampling.Source: §2.2 · pp. 3–5
  • E[bDN] upper-bounds the finite-N policy divergence and exceeds the population divergence by at most log 2.Unlike Aminian et al. (2026), the estimator-based bound stays within this universal additive slack of the population divergence.Source: §2.2 · p. 4

2.3 Experiments

  • Across reward geometries, E[bDN] closely tracks the exact finite-N divergence, while the population divergence gives its limiting value.The Aminian et al. (2026) guarantee is insensitive to reward-reference geometry for fixed (N, β).Source: §2.3 · p. 5, Figure 2 · p. 6
  • In the Monte Carlo experiments, K = 16 appeared sufficient for a reliable empirical upper bound, while K = 64 tracked the true expectation closely.Uncertainty depends on both the estimator's range and the location of its expectation within that range.Source: §2.3 · p. 7

3 RELATIVE ENTROPY CODING

Relative entropy coding communicates a target-distributed sample using shared proposal randomness, with coding cost related to KL divergence. The paper derives a finite-sample CE-ISC coding bound that avoids bounded-likelihood-ratio and higher-moment assumptions.

3 RELATIVE ENTROPY CODING

  • Relative entropy coding uses shared proposal randomness to communicate a target-distribution sample, with coding cost closely related to the distributions' KL divergence.The section applies the result to communication-efficient importance sampling-based compression (CE-ISC).Source: §3 · p. 7
  • CE-ISC selects a proposal according to normalized importance weights and communicates its index, with expected log-index cost bounded by the estimator plus δ.The earlier guarantee's remainder depends on bounded likelihood ratios and higher-order moments; the paper describes such bounds as potentially uninformative at small-to-moderate N when ratios or moments are large.Source: §3 · p. 7
  • H(J) ≤ I(X; Y) + log2(I(X; Y) + 2) + 5 under CE-ISC, giving a finite-sample coding-cost bound without bounded likelihood ratios or higher-order moment assumptions.The bound follows by applying the estimator result conditionally and averaging over X.Source: §3 · p. 8

4 RELATED WORK

The paper places its estimator in work on adaptive importance sampling, self-normalized importance-sampling bounds, and importance-weighted resampling. It distinguishes its finite-sample certificates from prior analyses that require moment or bounded-reward assumptions.

4 RELATED WORK

  • Earlier finite-sample SNIS analyses use moment assumptions, and Phan et al. (2024) derive an estimator-expectation bound under restrictive boundedness assumptions.The normalized-weight entropy term has also appeared in adaptive importance sampling, particle filtering, and importance-weighted variational inference.Source: §4 · p. 8
  • Chatterjee and Diaconis (2018) relate the characteristic importance-sampling sample size to exp(D_KL(p∥q)), while Sanz-Alonso (2018) gives nonasymptotic necessary sample-size conditions involving KL and other f-divergences.The cited results frame forward KL as a measure of target–proposal mismatch relevant to sample-size analysis.Source: §4 · p. 8
  • Verdun et al. (2025) analyze convergence of finite-sample Soft Best-of-N policies to the tilted target, while this work certifies KL-related shifts from the base policy without bounded-reward or higher-moment assumptions.Aminian et al. (2026) analyze the same finite-sample divergence with a bounded-reward bound that this work says it improves.Source: §4 · p. 8

5 CONCLUSION

The paper establishes nonasymptotic guarantees for a self-normalized importance-sampling estimator of forward KL and connects normalized weights to target–proposal discrepancy. It applies these guarantees to test-time alignment and relative entropy coding.

5 CONCLUSION

  • The paper characterizes finite-sample estimator behavior without bounded importance weights or finite higher moments, and connects normalized importance weights to target–proposal discrepancy.The guarantees are applied to test-time alignment and relative entropy coding.Source: §5 · p. 8
  • Future work includes tightening the additive slack, extending distribution-free guarantees to other normalized-weight functionals, and studying adaptive sampling and test-time-compute settings.The paper notes that proposal or sample design could be chosen to reduce target–proposal mismatch.Source: §5 · p. 8

Supplementary Materials

The supplementary material establishes asymptotic consistency, proves a contraction lemma used in the analysis, and begins the proof of Theorem 1 by setting up the likelihood-ratio estimator.

A ASYMPTOTIC CONVERGENCE

  • Under shared support and finite target–proposal KL, the estimator and its expectation converge asymptotically to the target–proposal KL.The proposition states these conditions for asymptotic consistency.Source: A ASYMPTOTIC CONVERGENCE · p. 11

B A CONTRACTION LEMMA

  • The contraction lemma shows that E[g(T) log g(T)] ≤ E[T log T] under its stated conditions, with g moving values toward an anchor.The proof uses the fact that g(t) lies between t and the anchor a.Source: B A CONTRACTION LEMMA · p. 15

C PROOF OF THEOREM 1

  • The proof setup assumes same support and positive likelihood ratios, then uses exchangeability and treats N = 1 separately.The excerpt introduces the likelihood ratio and the estimator before reducing the proof by exchangeability.Source: C PROOF OF THEOREM 1 · pp. 16–17

C.1 Proof Overview

The proofs establish divergence bounds by decomposing a tilted joint divergence and comparing importance-weighted with uniform selection from an i.i.d. proposal-sampled candidate pool. They control the divergence terms using pointwise and second-moment bounds, exchangeability of normalized weights, and data processing to relate output distributions.

C.1 Proof Overview

  • The chain rule splits the tilted joint divergence into the marginal divergence of Y and the average conditional divergence of X1 given Y.The proof first establishes that the tilted law is a probability law.Source: §C.1 · pp. 17, 19

C.2 Bounding the Conditional Contribution

  • For every well-defined x2:N, the conditional divergence is bounded by D_KL(p∥q), so averaging over tilted Y yields the conditional contribution bound.The proof establishes this stronger pointwise inequality before taking the expectation over Y.Source: §C.2 · p. 19

C.2.1 Proof of Corollary 3

  • The proof of Corollary 3 shows that h_t(w) lies between w and its positive fixed point a for every w > 0.This follows from the fixed-point and monotonicity properties established for h_t.Source: §C.2.1 · pp. 22–23

C.3 Bounding the Marginal Contribution

  • The marginal contribution is controlled using Jensen’s inequality together with a second-moment bound on its likelihood ratio B(Y).The proof identifies B as the marginal likelihood ratio and uses its second moment to bound the marginal divergence.Source: §C.3 · p. 24

Bounding the Second Moment

  • The second-moment argument uses independent variables and exchangeability of normalized weights to establish E[B(Y)^2] ≤ 2N/(N+1).The bound is proved by expressing the moment using independent Y, U, and V, then applying symmetry of the normalized weights.Source: Bounding the Second Moment · pp. 25–27

D PROOF OF THEOREM 2

  • Both joint distributions use an i.i.d. candidate pool from q, differing only in whether the selected index is importance-weighted or uniform.Under importance-weighted selection the output has marginal p_N; under uniform selection it has marginal q.Source: D PROOF OF THEOREM 2 · p. 27
  • The proof uses the data-processing inequality to relate the output marginals, citing Polyanskiy and Wu (2025).The passage identifies the two marginals as p_N and q but does not include the resulting divergence inequality.Source: D PROOF OF THEOREM 2 · p. 27

D.2 Proof of DKL(pN∥q) ≤DKL(p∥q)

The proof reduces the KL comparison to an entropy inequality for the transformed likelihood ratio, using a fixed point of the transformation and its monotonicity properties.

D.2 Proof of DKL(pN∥q) ≤DKL(p∥q)

  • E_q[hN(W) log hN(W)] ≤ E_q[W log W], giving the KL comparison for pN and q.The proof identifies these expectations with the divergences because pN and p are probability distributions.Source: §D.2 · p. 28
  • A positive fixed point c of hN exists, and hN is strictly increasing.The proof assumes N ≥ 2 for the remainder of its argument.Source: §D.2 · p. 28
  • Because hN(t)/t is strictly decreasing, hN(t) − t can cross zero at most once, from positive to negative.Continuity and values on either side of the crossing establish the fixed point used in the proof.Source: §D.2 · pp. 29–30

E PROOF OF THEOREM 3

The proof estimates pN(y)/q(y) by averaging SNIS selection probabilities over fresh auxiliary proposal sets, then uses unbiasedness and logarithm concavity in its argument.

E PROOF OF THEOREM 3

  • The auxiliary-sample estimator bθM(y) is unbiased for pN(y)/q(y), so logarithm concavity gives the stated Jensen bound.The auxiliary proposal samples are independent of Y distributed according to pN.Source: E PROOF OF THEOREM 3 · p. 30
  • For each fixed y, the strong law gives convergence of the auxiliary estimate, and continuity of the logarithm transfers that convergence to its log.The proof then applies this pointwise convergence for fixed B.Source: E PROOF OF THEOREM 3 · pp. 30–31
  • Changing measure from pN to q is used to handle the negative part of the log-estimator argument.Source: E PROOF OF THEOREM 3 · p. 31

F PROOF FOR SOFT BEST-OF-N OPTIMALITY

The appendix derives the KL-constrained reward optimum, establishes convergence of Soft Best-of-N to that policy, and shows population KL is nondecreasing with inverse temperature for β ≥ 0.

F PROOF FOR SOFT BEST-OF-N OPTIMALITY

G CONSISTENCY OF SOFT BEST-OF-N

H MONOTONICITY OF THE POPULATION KL IN β

I PROOF OF COROLLARY 1

The experiments examine finite-sample slack in the SNIS KL estimator and validate bounds on the divergence of the importance-weighted resampling distribution. Across the tested settings, the observed slack stays below the universal log 2 bound, while the upper estimator is more stable than the lower estimator under equal computational budgets.

I PROOF OF COROLLARY 1

  • Soft Best-of-N is precisely the sampling-importance-resampling procedure covered by the main results.The proof passage also states that the first two claims follow from Propositions 1 and 2.Source: I PROOF OF COROLLARY 1 · p. 34

J EXPERIMENTAL VALIDATION

  • Across all settings considered, no observed gap exceeds 0.15, suggesting the theoretical log 2 additive constant may be conservative.The experiments use 50,000 independent replicates for Monte Carlo estimates of E[bD_N].Source: J EXPERIMENTAL VALIDATION · p. 35

J.1 Empirical Study of the Additive Slack

  • The Bernoulli family’s largest observed slack is approximately 0.0844, when p concentrates on state 0 while that state remains relatively unlikely under q.The observed maximum is substantially below log 2, and further decreasing ϵ1 appears to approach a finite limit.Source: Figure 4 · p. 35, §J.1 · p. 36
  • For Weibull targets with a fixed exponential proposal, the slack remains negative across the considered samples and increases toward zero as N grows.The maximum slack stays close to zero over the considered shape–scale range, including heavier-tailed targets.Source: §J.1 · p. 36, Figure 5 · p. 36
  • Rare-bump slack reaches approximately 0.142 at β = 0.01 and N = 320, remaining well below the universal log 2 bound.The observed slack increases with geometry parameters A and S and appears to approach a limiting value as β decreases.Source: §J.1 · p. 37, Figure 6 · p. 37

J.2 Validating the Lower and Upper Bounds on DKL(pN∥q)

  • In the first three examples, E[bD_N] is consistently larger than DKL(p_N∥q), while L_N,4 closely tracks DKL(p_N∥q) across the examples despite using only M = 4 auxiliary samples.In the final example, E[bD_N] is non-monotone and exceeds the population divergence for intermediate N, reaching approximately 0.603 at N = 6 compared with DKL(p∥q) ≈ 0.559.Source: §J.2 · p. 37
  • Under equal proposal-sampling budgets, the upper estimator has narrower sampling intervals than the lower estimator, which is especially variable at small and moderate N.The lower estimator uses nested Monte Carlo; in most tested settings, M = 1 gives the narrowest interval because it leaves more budget for outer samples.Source: §J.2 · pp. 38–39, Figure 8 · p. 39
  • In the shifted-Gaussian setup, increasing computational budget reduces variability for both estimators, while the lower estimator remains considerably more variable.Source: §J.2 · p. 39

J.3 Additional Experiments on Soft BoN Compute

Additional Soft BoN experiments examine performance across discretized distribution pairs and compute budgets. K = 16 already gives sufficiently accurate and stable estimates in the considered scenarios, while K = 64 yields tighter estimates that closely track the expected value.

J.3 Additional Experiments on Soft BoN Compute

Loading 2610.12851v1…