Sampling Decisions: Exact Path-Space Correction, Prior Cancellation and Local-Boltzmann Guidance (arxiv.org)
arXiv:2503.14549v3 Announce Type: replace-cross
Abstract: How can a cheap but biased sequential, finite-horizon sampler over a discrete space be corrected so that its terminal output follows a prescribed Gibbs distribution? We formulate Sampling Decisions as a path-space relative-entropy projection on a growing autoregressive state graph. The unique prior-relative minimizer is a Doob transform governed by a linear backward recursion. A route-resolved formulation then yields a finite-particle algorithm based on conditional self-normalized importance sampling, and we prove convergence of its transition kernels and terminal law as the path budget grows.
For binary graphical models, we prove an exact cancellation theorem: all fixed singleton-product priors disappear from the population correction; only the ordering policy survives. Thus, more accurate one-point marginals may not produce a better finite-budget sampler. We therefore introduce a prefix-dependent autoregressive Local-Boltzmann prior that conditions each new spin on its revealed neighbors, while the path-space correction supplies the missing look-ahead field generated by the unrevealed subgraph.
Experiments on 33, 44, and 5*5 Ising grids show that singleton-product priors suffer severe importance-weight degeneracy, whereas Local-Boltzmann guidance maintains substantially larger effective sample size and reaches the exact-target reference band at the tested budgets. The results identify correlated, prefix-dependent guidance as the decisive ingredient in sequential sampling.
Abstract: How can a cheap but biased sequential, finite-horizon sampler over a discrete space be corrected so that its terminal output follows a prescribed Gibbs distribution? We formulate Sampling Decisions as a path-space relative-entropy projection on a growing autoregressive state graph. The unique prior-relative minimizer is a Doob transform governed by a linear backward recursion. A route-resolved formulation then yields a finite-particle algorithm based on conditional self-normalized importance sampling, and we prove convergence of its transition kernels and terminal law as the path budget grows.
For binary graphical models, we prove an exact cancellation theorem: all fixed singleton-product priors disappear from the population correction; only the ordering policy survives. Thus, more accurate one-point marginals may not produce a better finite-budget sampler. We therefore introduce a prefix-dependent autoregressive Local-Boltzmann prior that conditions each new spin on its revealed neighbors, while the path-space correction supplies the missing look-ahead field generated by the unrevealed subgraph.
Experiments on 33, 44, and 5*5 Ising grids show that singleton-product priors suffer severe importance-weight degeneracy, whereas Local-Boltzmann guidance maintains substantially larger effective sample size and reaches the exact-target reference band at the tested budgets. The results identify correlated, prefix-dependent guidance as the decisive ingredient in sequential sampling.
Comments