Restricted Spectral Gap Decomposition for Simulated Tempering Targeting Mixture Distributions

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. Our complexity bound scales polynomially with the separation between modes, logarithmically with 1/ε, where ε denotes the target accuracy in total variation distance, and exponentially with the dimension d.

constructed in many ways. We present a construction which differs substantially from that of Ge et al. [2018]; it arises naturally from the structure of the algorithm and significantly simplifies the proof.

The remainder of the paper is organized as follows. In Section 2, we present our decomposition theorem. In Section 3, we apply this theorem to analyze the simulated tempering combined with the random walk Metropolis-Hastings (STMH) algorithm for sampling from mixtures of Gaussian distributions. In Section 4, we empirically validate our convergence guarantee for the STMH algorithm by sampling from a two-dimensional Gaussian mixture. Finally, Section 5 summarizes our key contributions and highlights promising directions for future research. Detailed proofs are provided in the appendix.

We begin by introducing the necessary notation that will be used throughout the paper. We adopt the convention that uppercase letters denote probability distributions (or transition kernels) and the corresponding lowercase letters their densities (or transition densities). For example, P will be used to denote the probability distribution with density p. We use L 2 (Ω, Π) to denote the space of all real-valued functions defined on Ω that are square-integrable with respect to a measure Π. Definition 1 (Restricted Spectral Gap). Let K be a Markov transition kernel with state space Ω and stationary probability measure Π. Let Ω 0 ⊆ Ω be measurable such that Π(Ω 0 ) > 0. The Ω 0 -restricted spectral gap of K, denoted by SpecGap Ω 0 (K), is defined as

We will refer to E Ω 0 (g, g; Π, K) as the Ω 0 -restricted Dirichlet form and omit Π, K when they are clear from the context. When Ω 0 = Ω, SpecGap Ω 0 (K) is known as the spectral gap of K, and we simply write SpecGap(K) = SpecGap Ω (K), E(g, g) = E Ω (g, g) and Var Π (g) = Var Π,Ω0 (g).

Note that Var Π (g) equals the variance of g(ω) with ω ∼ Π. Intuitively, the spectral gap quantifies how rapidly a Markov chain mixes: a larger gap corresponds to faster convergence to stationarity distribution. The restricted spectral gap generalizes this idea by measuring the rate of mixing in a subset Ω 0 of the state space.