Entropy-Guided Sampling of Flat Modes in Discrete Spaces

• URL: http://arxiv.org/abs/2505.02296v2
• Date: Fri, 16 May 2025 03:46:16 GMT
• Title: Entropy-Guided Sampling of Flat Modes in Discrete Spaces
• Authors: Pinaki Mohanty, Riddhiman Bhattacharya, Ruqi Zhang,
• Abstract summary: Existing sampling algorithms often overlook the mode volume and struggle to capture flat modes effectively.<n>We propose emphEntropic Discrete Langevin Proposal (EDLP), which incorporates local entropy into the sampling process through a continuous auxiliary variable under a joint distribution.<n>We provide non-asymptotic convergence guarantees for EDLP in locally log-concave discrete distributions.
• Score: 9.099589602551573
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Diffusion-based supervised learning of generative models for efficient sampling of multimodal distributions [16.155593250605254]
  We propose a hybrid generative model for efficient sampling of high-dimensional, multimodal probability distributions for Bayesian inference.<n>Our numerical examples demonstrate that the proposed framework can effectively handle multimodal distributions with varying mode shapes in up to 100 dimensions.
  arXiv  Detail & Related papers  (2025-04-20T21:06:02Z)
• Enhancing Gradient-based Discrete Sampling via Parallel Tempering [8.195708231156546]
  A gradient-based discrete sampler is susceptible to getting trapped in local minima in high-dimensional, multimodal discrete distributions.<n>We develop a discrete Langevin proposal that combines parallel tempering, also known as replica exchange, with the discrete Langevin proposal.<n>We show that our algorithm converges non-asymptotically to the target energy and exhibits faster mixing compared to a single chain.
  arXiv  Detail & Related papers  (2025-02-26T15:51:15Z)
• Dynamical Measure Transport and Neural PDE Solvers for Sampling [77.38204731939273]
  We tackle the task of sampling from a probability density as transporting a tractable density function to the target. We employ physics-informed neural networks (PINNs) to approximate the respective partial differential equations (PDEs) solutions. PINNs allow for simulation- and discretization-free optimization and can be trained very efficiently.
  arXiv  Detail & Related papers  (2024-07-10T17:39:50Z)
• On the Trajectory Regularity of ODE-based Diffusion Sampling [79.17334230868693]
  Diffusion-based generative models use differential equations to establish a smooth connection between a complex data distribution and a tractable prior distribution. In this paper, we identify several intriguing trajectory properties in the ODE-based sampling process of diffusion models.
  arXiv  Detail & Related papers  (2024-05-18T15:59:41Z)
• Diffusive Gibbs Sampling [40.1197715949575]
  We propose Diffusive Gibbs Sampling (DiGS) for effective sampling from distributions characterized by distant and disconnected modes. DiGS integrates recent developments in diffusion models, leveraging Gaussian convolution to create an auxiliary noisy distribution. A novel Metropolis-within-Gibbs scheme is proposed to enhance mixing in the denoising sampling step.
  arXiv  Detail & Related papers  (2024-02-05T13:47:41Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  In this paper, we propose a distributed sampling scheme based on the alternating direction method of multipliers. We provide both theoretical guarantees of our algorithm's convergence and experimental evidence of its superiority to the state-of-the-art. In simulation, we deploy our algorithm on linear and logistic regression tasks and illustrate its fast convergence compared to existing gradient-based methods.
  arXiv  Detail & Related papers  (2024-01-29T02:08:40Z)
• Entropy-MCMC: Sampling from Flat Basins with Ease [10.764160559530849]
  We introduce an auxiliary guiding variable, the stationary distribution of which resembles a smoothed posterior free from sharp modes, to lead the MCMC sampler to flat basins. By integrating this guiding variable with the model parameter, we create a simple joint distribution that enables efficient sampling with minimal computational overhead. Empirical results demonstrate that our method can successfully sample from flat basins of the posterior, and outperforms all compared baselines on multiple benchmarks.
  arXiv  Detail & Related papers  (2023-10-09T04:40:20Z)
• Semi-Implicit Denoising Diffusion Models (SIDDMs) [50.30163684539586]
  Existing models such as Denoising Diffusion Probabilistic Models (DDPM) deliver high-quality, diverse samples but are slowed by an inherently high number of iterative steps. We introduce a novel approach that tackles the problem by matching implicit and explicit factors. We demonstrate that our proposed method obtains comparable generative performance to diffusion-based models and vastly superior results to models with a small number of sampling steps.
  arXiv  Detail & Related papers  (2023-06-21T18:49:22Z)
• Optimal Scaling for Locally Balanced Proposals in Discrete Spaces [65.14092237705476]
  We show that efficiency of Metropolis-Hastings (M-H) algorithms in discrete spaces can be characterized by an acceptance rate that is independent of the target distribution. Knowledge of the optimal acceptance rate allows one to automatically tune the neighborhood size of a proposal distribution in a discrete space, directly analogous to step-size control in continuous spaces.
  arXiv  Detail & Related papers  (2022-09-16T22:09:53Z)
• A Langevin-like Sampler for Discrete Distributions [15.260564469562542]
  discrete Langevin proposal (DLP) is a simple and scalable gradient-based proposal for sampling complex high-dimensional discrete distributions. DLP is able to update all coordinates in parallel in a single step and the magnitude of changes is controlled by a stepsize. We develop several variants of sampling algorithms, including unadjusted, adjusted, and preconditioned versions.
  arXiv  Detail & Related papers  (2022-06-20T17:36:03Z)
• Distributed Sketching Methods for Privacy Preserving Regression [54.51566432934556]
  We leverage randomized sketches for reducing the problem dimensions as well as preserving privacy and improving straggler resilience in asynchronous distributed systems. We derive novel approximation guarantees for classical sketching methods and analyze the accuracy of parameter averaging for distributed sketches. We illustrate the performance of distributed sketches in a serverless computing platform with large scale experiments.
  arXiv  Detail & Related papers  (2020-02-16T08:35:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.