Entropy-Guided Sampling of Flat Modes in Discrete Spaces
This addresses a crucial yet underexplored problem in discrete sampling for applications like combinatorial optimization and generative modeling, though it appears incremental as it builds on existing sampling methods by adding entropy guidance.
The paper tackles the problem of sampling from flat modes in discrete spaces, which is important for combinatorial optimization and discrete generative modeling, and proposes the Entropic Discrete Langevin Proposal (EDLP) method that incorporates local entropy to guide sampling, achieving consistent empirical outperformance over traditional approaches across various tasks.
Sampling from flat modes in discrete spaces is a crucial yet underexplored problem. Flat modes represent robust solutions and have broad applications in combinatorial optimization and discrete generative modeling. However, existing sampling algorithms often overlook the mode volume and struggle to capture flat modes effectively. To address this limitation, we propose \emph{Entropic Discrete Langevin Proposal} (EDLP), which incorporates local entropy into the sampling process through a continuous auxiliary variable under a joint distribution. The local entropy term guides the discrete sampler toward flat modes with a small overhead. We provide non-asymptotic convergence guarantees for EDLP in locally log-concave discrete distributions. Empirically, our method consistently outperforms traditional approaches across tasks that require sampling from flat basins, including Bernoulli distribution, restricted Boltzmann machines, combinatorial optimization, and binary neural networks.