Restricted Spectral Gap Decomposition for Simulated Tempering Targeting Mixture Distributions

• URL: http://arxiv.org/abs/2505.15059v1
• Date: Wed, 21 May 2025 03:28:55 GMT
• Title: Restricted Spectral Gap Decomposition for Simulated Tempering Targeting Mixture Distributions
• Authors: Jhanvi Garg, Krishna Balasubramanian, Quan Zhou,
• Abstract summary: We consider simulated tempering combined with an arbitrary local chain Monte Carlo sampler.<n>We present a new decomposition theorem that provides a lower bound on the restricted spectral gap of the algorithm for sampling from mixture distributions.
• Score: 3.7577421880330535
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Simulated tempering is a widely used strategy for sampling from multimodal distributions. In this paper, we consider simulated tempering combined with an arbitrary local Markov chain Monte Carlo sampler and present a new decomposition theorem that provides a lower bound on the restricted spectral gap of the algorithm for sampling from mixture distributions. By working with the restricted spectral gap, the applicability of our results is extended to broader settings such as when the usual spectral gap is difficult to bound or becomes degenerate. We demonstrate the application of our theoretical results by analyzing simulated tempering combined with random walk Metropolis--Hastings for sampling from mixtures of Gaussian distributions. We show that in fixed-dimensional settings, the algorithm's complexity scales polynomially with the separation between modes and logarithmically with $1/\varepsilon$, where $\varepsilon$ is the target accuracy in total variation distance.

Related papers

• 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)
• Theory on Score-Mismatched Diffusion Models and Zero-Shot Conditional Samplers [49.97755400231656]
  We present the first performance guarantee with explicit dimensional dependencies for general score-mismatched diffusion samplers.<n>We show that score mismatches result in an distributional bias between the target and sampling distributions, proportional to the accumulated mismatch between the target and training distributions.<n>This result can be directly applied to zero-shot conditional samplers for any conditional model, irrespective of measurement noise.
  arXiv  Detail & Related papers  (2024-10-17T16:42:12Z)
• Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis [56.442307356162864]
  We study the theoretical aspects of score-based discrete diffusion models under the Continuous Time Markov Chain (CTMC) framework.<n>We introduce a discrete-time sampling algorithm in the general state space $[S]d$ that utilizes score estimators at predefined time points.<n>Our convergence analysis employs a Girsanov-based method and establishes key properties of the discrete score function.
  arXiv  Detail & Related papers  (2024-10-03T09:07:13Z)
• 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)
• Langevin Quasi-Monte Carlo [6.146093081175471]
  Langevin Monte Carlo (LMC) and its gradient versions are powerful algorithms for sampling from complex high-dimensional distributions. We show that the estimation error of LMC can also be reduced by using quasi-random samples.
  arXiv  Detail & Related papers  (2023-09-22T07:15:18Z)
• Noise-Free Sampling Algorithms via Regularized Wasserstein Proximals [3.4240632942024685]
  We consider the problem of sampling from a distribution governed by a potential function. This work proposes an explicit score based MCMC method that is deterministic, resulting in a deterministic evolution for particles.
  arXiv  Detail & Related papers  (2023-08-28T23:51:33Z)
• 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)
• Mean-Square Analysis of Discretized It\^o Diffusions for Heavy-tailed Sampling [17.415391025051434]
  We analyze the complexity of sampling from a class of heavy-tailed distributions by discretizing a natural class of Ito diffusions associated with weighted Poincar'e inequalities. Based on a mean-square analysis, we establish the iteration complexity for obtaining a sample whose distribution is $epsilon$ close to the target distribution in the Wasserstein-2 metric.
  arXiv  Detail & Related papers  (2023-03-01T15:16:03Z)
• Sampling in Combinatorial Spaces with SurVAE Flow Augmented MCMC [83.48593305367523]
  Hybrid Monte Carlo is a powerful Markov Chain Monte Carlo method for sampling from complex continuous distributions. We introduce a new approach based on augmenting Monte Carlo methods with SurVAE Flows to sample from discrete distributions. We demonstrate the efficacy of our algorithm on a range of examples from statistics, computational physics and machine learning, and observe improvements compared to alternative algorithms.
  arXiv  Detail & Related papers  (2021-02-04T02:21:08Z)
• Generative Modeling with Denoising Auto-Encoders and Langevin Sampling [88.83704353627554]
  We show that both DAE and DSM provide estimates of the score of the smoothed population density. We then apply our results to the homotopy method of arXiv:1907.05600 and provide theoretical justification for its empirical success.
  arXiv  Detail & Related papers  (2020-01-31T23:50:03Z)

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.