Energy-based sampling improves accuracy on complex discrete models
Iterative Exact Discrete Guidance for Energy-Based Sampling
Machine Learning
Summary
Sampling from complicated discrete distributions is hard when the target distribution is very different from a simple starting point. The authors propose a new method called Iterative Exact Discrete Guidance (IEDG) that breaks the problem into smaller steps along a guided path, improving the accuracy of sampling by learning corrections at each stage. Their approach adapts step sizes based on sample quality and achieves better performance on well-known physics models and combinatorial problems compared to existing neural methods.
What this means in practice
- •For machine learning engineers: Generate more accurate samples in discrete probabilistic models used for structured prediction and combinatorial optimization tasks.
- •For operations research teams: Improve solution quality for combinatorial optimization problems like Max-Cut by effectively sampling from complex distribution landscapes.
Authors
Yuwen Qian, Yidong Ouyang, Zhengyan Wan, Hongyuan Zha
Abstract
Sampling from unnormalized distributions over large discrete state spaces becomes difficult when a multimodal target is far from a tractable reference. We introduce Iterative Exact Discrete Guidance (IEDG), a population-exact, trajectory-wise guidance framework for unnormalized discrete targets. Rather than learn the full reference-to-target correction in one step, IEDG introduces a global Boltzmann tilt along an annealing trajectory. Each stage learns a stage-local posterior correction for an incremental Boltzmann tilt of the current source, while the resulting corrections are accumulated relative to a fixed analytic posterior. At the population optimum, exact stage posteriors recover the correct reverse dynamics, whose exact simulation reproduces the target distribution. IEDG chooses stage increments by relative effective sample size (rESS), which controls Rényi-2 displacement and locally adapts the step size to the thermodynamic geometry of the annealing path. Our stagewise total-variation analysis shows that limited overlap amplifies Bregman fitting error by $1/\sqrt{\mathrm{rESS}}$, while posterior, simulation, and truncation errors enter additively. IEDG improves all distribution-level errors over the neural baselines on ordered, exactly enumerated Ising $4\times4$, while substantially reducing one-shot errors on Ising/Potts $16\times16$ across thermodynamic regimes and attaining the best neural-sampler result on several reported local-statistic and phase-coverage metrics. On Max-Cut, its best-of-512 and average-sample ratios exceed all the baselines. Code and artifacts are available at https://github.com/StillFantasy123/iterative-exact-discrete-guidance.