Enhancing Gradient-based Discrete Sampling via Parallel Tempering

• URL: http://arxiv.org/abs/2502.19240v1
• Date: Wed, 26 Feb 2025 15:51:15 GMT
• Title: Enhancing Gradient-based Discrete Sampling via Parallel Tempering
• Authors: Luxu Liang, Yuhang Jia, Feng Zhou,
• Abstract summary: 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.
• Score: 8.195708231156546
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: While gradient-based discrete samplers are effective in sampling from complex distributions, they are susceptible to getting trapped in local minima, particularly in high-dimensional, multimodal discrete distributions, owing to the discontinuities inherent in these landscapes. To circumvent this issue, we combine parallel tempering, also known as replica exchange, with the discrete Langevin proposal and develop the Parallel Tempering enhanced Discrete Langevin Proposal (PTDLP), which are simulated at a series of temperatures. Significant energy differences prompt sample swaps, which are governed by a Metropolis criterion specifically designed for discrete sampling to ensure detailed balance is maintained. Additionally, we introduce an automatic scheme to determine the optimal temperature schedule and the number of chains, ensuring adaptability across diverse tasks with minimal tuning. Theoretically, we establish that our algorithm converges non-asymptotically to the target energy and exhibits faster mixing compared to a single chain. Empirical results further emphasize the superiority of our method in sampling from complex, multimodal discrete distributions, including synthetic problems, restricted Boltzmann machines, and deep energy-based models.

Related papers

• Scalable Equilibrium Sampling with Sequential Boltzmann Generators [60.00515282300297]
  We extend the Boltzmann generator framework and introduce Sequential Boltzmann generators with two key improvements. The first is a highly efficient non-equivariant Transformer-based normalizing flow operating directly on all-atom Cartesian coordinates. We demonstrate the first equilibrium sampling in Cartesian coordinates of tri, tetra, and hexapeptides that were so far intractable for prior Boltzmann generators.
  arXiv  Detail & Related papers  (2025-02-25T18:59:13Z)
• Policy Gradients for Optimal Parallel Tempering MCMC [0.276240219662896]
  Parallel tempering is a meta-algorithm for Markov Chain Monte Carlo that uses multiple chains to sample from tempered versions of the target distribution.<n>We present an adaptive temperature selection algorithm that dynamically adjusts temperatures during sampling using a policy gradient approach.
  arXiv  Detail & Related papers  (2024-09-03T03:12:45Z)
• 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)
• Gradient-based Discrete Sampling with Automatic Cyclical Scheduling [8.017203108408973]
  We propose an automatic cyclical scheduling for efficient and accurate sampling in multimodal discrete distributions. We prove the non-asymptotic convergence and inference guarantee for our method in general discrete distributions.
  arXiv  Detail & Related papers  (2024-02-27T17:23:40Z)
• Broadening Target Distributions for Accelerated Diffusion Models via a Novel Analysis Approach [49.97755400231656]
  We show that a novel accelerated DDPM sampler achieves accelerated performance for three broad distribution classes not considered before. Our results show an improved dependency on the data dimension $d$ among accelerated DDPM type samplers.
  arXiv  Detail & Related papers  (2024-02-21T16:11:47Z)
• Iterated Denoising Energy Matching for Sampling from Boltzmann Densities [109.23137009609519]
  Iterated Denoising Energy Matching (iDEM) iDEM alternates between (I) sampling regions of high model density from a diffusion-based sampler and (II) using these samples in our matching objective. We show that the proposed approach achieves state-of-the-art performance on all metrics and trains $2-5times$ faster.
  arXiv  Detail & Related papers  (2024-02-09T01:11:23Z)
• 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)
• Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
  Annealed Importance Sampling (AIS) synthesizes weighted samples from an intractable distribution. We propose the Constant Rate AIS algorithm and its efficient implementation for $alpha$-divergences.
  arXiv  Detail & Related papers  (2023-06-27T08:15:28Z)
• Differentiating Metropolis-Hastings to Optimize Intractable Densities [51.16801956665228]
  We develop an algorithm for automatic differentiation of Metropolis-Hastings samplers. We apply gradient-based optimization to objectives expressed as expectations over intractable target densities.
  arXiv  Detail & Related papers  (2023-06-13T17:56:02Z)
• Importance sampling for stochastic quantum simulations [68.8204255655161]
  We introduce the qDrift protocol, which builds random product formulas by sampling from the Hamiltonian according to the coefficients. We show that the simulation cost can be reduced while achieving the same accuracy, by considering the individual simulation cost during the sampling stage. Results are confirmed by numerical simulations performed on a lattice nuclear effective field theory.
  arXiv  Detail & Related papers  (2022-12-12T15:06:32Z)
• Sampling from high-dimensional, multimodal distributions using automatically tuned, tempered Hamiltonian Monte Carlo [0.0]
  Hamiltonian Monte Carlo (HMC) is widely used for sampling from high-dimensional target distributions with probability density known up to proportionality. Traditional tempering methods, commonly used to address multimodality, can be difficult to tune, particularly in high dimensions. We propose a method that combines a tempering strategy with Hamiltonian Monte Carlo, enabling efficient sampling from high-dimensional, strongly multimodal distributions.
  arXiv  Detail & Related papers  (2021-11-12T18:48:36Z)
• Ensemble Slice Sampling: Parallel, black-box and gradient-free inference for correlated & multimodal distributions [0.0]
  Slice Sampling has emerged as a powerful Markov Chain Monte Carlo algorithm that adapts to the characteristics of the target distribution with minimal hand-tuning. This paper introduces Ensemble Slice Sampling (ESS), a new class of algorithms that bypasses such difficulties by adaptively tuning the initial length scale. These affine-invariant algorithms are trivial to construct, require no hand-tuning, and can easily be implemented in parallel computing environments.
  arXiv  Detail & Related papers  (2020-02-14T19:00:12Z)

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.