Restricted Spectral Gap Decomposition for Simulated  Tempering Targeting Mixture Distributions
Authors: Jhanvi Garg
Krishna Balasubramanian
Quan Zhou
Venue: NeurIPS 2025 poster ()
Keywords: Simulated tempering
Multimodal sampling
Mixing time
Markov chain decomposition
Restricted spectral gap
Primary area: theory
TL;DR: We bound the restricted spectral gap of simulated tempering chain for mixture distributions and show that simulated tempering Metropolis–Hastings efficiently samples from Gaussian mixtures.

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

Restricted Spectral Gap Decomposition for Simulated Tempering Targeting Mixture Distributions
Jhanvi Garg Department of Statistics Texas A&M University College Station, TX 77843 gargjhanvi@tami edu
Krishnakumar Balasubramanian Department of Statistics University of California Davis, CA 95616 kbala@ucdavis. edu
Quan Zhou
Department of Statistics
Texas A&M University
College Station, TX 77843
quan@stat tamu. edu
Abstract
Simulated tempering is a widely used strategy for sampling from multimodal distributions. In this paper, consider simulated tempering combined with arbitrary local Markov chain Monte Carlo sampler and present a new decomposition theorem that provides lower bound 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 when the usual spectral gap difficult to bound or becomes degenerate. We demonstrate the application of our theoretical results by analyzing simulated tempering combined with random walk Metropolis-Hastine distributions. Our complexity bound scales polynomially with the separation between modes, logarithmically with 1/e, where denotes the target accuracy in total variation distance, and exponentially with the dimension d.
for sampling from mixtures of Gaussian
Introduction
Efficient sampling from complex distributions is foundational problem with numerous applications
across various fields, including computational statistics [Robert et al. 1999 Liu and Liu 2001 Brooks
al. [20T Owen 2013]. Bayesian inference [Gelman et al.) 20133. statistical physics Newman and
Barkema 1999 Landau and Binder (021]. and finance [agpunnr 2007 These distributions are
often multimodal, reflecting underlying heterogeneity the data. Sampling from such distributions
presents challenges closely related to those encountered in non-convex optimization, where objective functions with multiple local minima require methods capable of effectively exploring the solution space. While discretizations of Langevin dynamics (for comprehensive overview, see Chewi (024)) excel log-concave settings where gradients reliably guide the sampler toward a single mode, they tend to be less effective in multimodal landscapes, which require strategies capable of navigating between separated modes. The assumption of dissipativity, which limits the growth rate of the potential, has been widely used in previous works to establish better convergence rates for Langevin Monte Carlo (LMC) such settings [Raginsky et al. 2017 Durmus and Moulines, 2017 Erdogdu al. 2018 Erdogdu and Hosseinzadehl 2021 Mou et al. 2022 Hoossein et al. 2023]. More recently, Balasubramanian et al. [2022] characterized the performance averaged LMC for target densities that are only Hölder continuous, without relying functional inequalities or curvature-baat assumptions; they measured the convergence rate using the weaker Fisher information
metric.
For distributions that deviate significantly from log-concavity and exhibit numerous deep modes, additional techniques often required to ensure efficient sampling. A comprehensive discussion of the fundamental challenges in sampling from multimodal distributions, as well as an overview of major types of Markov chain Monte Carlo (MCMC) algorithms designed for this purpose-including
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

parallel tempering, mode jumping, and Wang Landau methods can be found in Eatuszyński al. 2025]. The recent work of Koehler al. [224]] addresses the problem of sampling from multimodal distribution by initializing the sampler using small number of stationary samples. They show that, under the assumption of a k-th order spectral gap, the chain efficiently yields an e-accurate sample in total variation (TV) distance with (kk/=") samples, and they further extend the result scenarios where the score (i.e., the drift term of LMC) is estimated. Lee and Santana- Santana-Gijzen
[024] studied the sequential Monte Carlo (SMC) method [Luu and Chen 1998 Del Moral et al.
2006 Chopin al., 2020, Syed al. 2024) and derived the complexity result for mixture target wiwpiiinnndffuson-bbbaee
distributions. Additionally,
samplers have been proposed for sampling from non-log-concave targets without relying on isoperimetric inequalities (Huang et al. [2023] 2024| (H
ct al. 2024b). These methods reverse the Frmstinn-Uhlenbee process and require estimating score functions (i.e., gradients of the log-density) via importance sampling, which becomes particularly
challenging in high-dimensional settings.
A widely used strategy for tackling multimodality is annealing or tempering, which leverages sequence of distributions to gradually explore complex landscapes. Guo et al.] (2024) provided a
non-asymptotic analysis of annealed Langevin Monte Carlo [Neal 2001]. highlighting its provable benefits for non-log-concane sampling. They demonstrated that a simple annealed Langevin Monte Carlo algorithm achieves 8² accuracy in Kullback-Leebllr divergence with an oracle complexity of Ô (d/e"). Chehab al. (2024) develops comprehensive theoretical framework for tempered Langevin dynamics, providing convergence guarantees in Kullback-Leibler divergence across a variety of tempering schedules. Simulated tempering (Marinari and Parisi] [992] has also been introduced as method to promote transitions between modes. By dynamically adjusting the "temperature" of the distribution, simulated tempering effectively smooths the energy landscape, allowing the sampler to escape local modes and traverse between high-probability regions. The sampler gradually returns to the original distribution as the temperature decreases. A version of simulated tempering was also used in Koehler et al. [2022] to sample from multimodal Ising models. Parallel tempering (Swendsen and Wang 1986] shares a similar mechanism with simulated tempering. but runs multiple chains in parallel at different temperatures, allowing exchanges between them to improve mixing. [Zheng (2003) established that the spectral gap of simulated tempering chain is bounded below by multiple of the spectral gap of parallel tempering chain and bound depending on the overlap between distributions at adjacent temperatures. |Woodard et al.] (009) provided a lower bound on the spectral gap for a simulated tempering chain using the state space decomposition technique [Madras and Randall 2002). This method analyzes the probability flow by dividing the state space into subsets and studying transitions within and between them. However, determining an optimal partition into subsets often requires complex spectral partitioning arguments, and estimating the spectral gap through conductance methods can introduce a squared-factor loss due Cheeger's inequality.
An alternative approach is to decompose the Markov chain directly rather than the state space, particularly when the target distribution is a mixture distribution or closely resembles one. This method can yield potentially tighter spectral gap bounds by separately analyzing two types of chains: local chains that efficiently explore each mixture component at every temperature level and a projected chain that governs transitions between different components and temperature levels. This decomposition technique was introduced in [G et al. (0188) as a framework for bounding the spectral gap of the simulated tempering chain combined with LMC for mixtures of strongly log-concave distributions that are translates of each other. They established that the runtime required to reach an E TV distance from the target distribution depends polynomially on the dimension d, the mode separation D. and the inverse accuracy I/e.
We introduce new Markov chain decomposition theorem for discrete-time chains, in contrast to the continuous time framework adopted by Ge et al. [2018). Since spectral gap bounds of discrete- Markov chains (e.g. Hutropolis-Hastingg algorithms) over unbounded Fuclidean spaces is often difficult to obtain, we propose to directly decompose the restricted spectral gap [Atchadé] 2021] }],
which, roughly speaking. can be thought of the spectral gap of the Markov chain restricted to subset of the state space. Geometric tools such as the path methods developed by Yuen (2000) can be used lower bound the restricted spectral gap. Intuitively, if each local chain mixes fast large subset of the space, where the target distribution concentrates, and the projected chain also mixes well, then the overall simulated tempering chain should converge fast. The projected chain can be
2

---

constructed in many ways. We present construction which differs substantially from that of Ge et al. 2018); 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-Hastingg distributions. In Section 4 we empirically validate our convergence guarantee for the STMH algorithm by sampling from a two-dimensional Gaussian mixture. Finally, S summarizes our key contributions and highlights promising directions for future research. Detailed proofs are provided in the appendix.
(STMH) algorithm for sampling from mixtures of Gaussian
2
A New Decomposition Theorem
2.1 Notation and Definitions
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 (1,, II) to denote the space of all real-valued functions defined on Ω that are square with respect to a measure
Definition 1 (Restricted Spectral Gap). Let K be a Markov transition kernel with state space Q and stationary probability measure II. Let 22 S. St be measurable such that II(22) 0. The Ω -esttttrid spectral gup of K, denoted by SpecGapno (K), is defined as
Ego g; 11, K)
inf SpecGapge (K)= = (0,2)))
Varn (g)
where
/ (o(w')-g(e [I((w) K (w, dw'),
(g. 11, K) = J.
[ [ [o(w<) [(w)] ((dw) (Tdw"))
Varm, (g) = 2 1r
We will refer to Ego (g. 9: II, K) as the f2 restrririe Dirichlet form and omit II, when they are clear from the context. When Ω2 Ω. Spee (K) is known the spectral gap of K, and we simply write SpecGap(K) = SpecGap, (KoCGGap,KK..... (g. = En(g. g) and (g) = Var (g). Note that (9) equals the variance of g(w) with ~ II. 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 subset Ω2 of the state space.
Simulated tempering can be viewed as a bivariate Markov chain. The key idea is to augment the state space with a temperature index that allows the chain to move between a family of distributions, ranging from the target distribution (low temperature) to flattened versions (high temperature). At higher temperatures the landscape is smoother, enabling easier transitions between modes, while samples from the target are obtained by collecting states only at the lowest temperature. Formally, it defined as follows.
(1.,...., L}. Definition 2 (Simulated Tempering Markov Chain), Let L > 2 be integer and [L] {1, ...,, Let À E (0, 1) and (ri)se(l) be constants such that r; > 0 for each i, and E
Ei=rr r. 1. Let M,, for each i E [L], be the transition kernel of a Markov chain with state space X and stationary density ps- The simulated tempering Markov chain has state space [L] x X. Denote its transition kernel by
M = M ((p.) (ri)t (M:
which has density
- (m,,),((
ifi = i' # x', if'l = i 1, =
(((,,)),(('a)))))
((',
where
(epe(
a((i, x)) (i', = min
(I)
rip;(x)
3

---

In words, the simulated tempering Markov chain evolves as follows. Given current state (i. 2)) we sample (ernoulli(A). If 0, draw x' from (x.)) and move (i,x') If u 1, propose i' = 1, each with equal probability 1 1/2, and accept the proposal with probability a(ii,z), (i', a)) ii & [Z]. the proposal always rejected). is easy to check that the stationary distribution P of the simulated tempering Markov chain M has density given by
p(i,,)) (T).
2.2 Decomposition of the Simulated Tempering Markov chain
Consider the simulated tempering Markov chain given in Definition 2 Let 2 C X be measurable subset of X, and our goal derive a decomposition theorem for the spectral gap of M restricted to [L] x X We assume that the distributions (Pi) satisfies the following assumption.
Assumption 1. For each i E [T.), the stationary density pt can be expressed a mixture of component densities:
pi(x)) Σ j=1 where w(i.)) 2 0 for each j E [n]] and E}=1 ((,) =.
For simplicity, in Assumption we assume that each stationary density p; can be expressed as mixture of simpler component densities, assumption also made in Ge al. 2018 Under Assumption [ we can introduce a latent variable J so that given 1 = i, J. X is drawn from the component distribution P(c.)). The density of the target distribution is augmented to p(i, P(L))))))) (z)) The overall strategy of our decomposition is similar to Theorem 6.3 of Ge et al. (2018) in that we directly decompose the Dirichlet form of M into the Dirichlet forms of Markov chains (M(L)))e(LL)
where M(.) has stationary distribution P(..) We assume that these chains are chosen such that the following assumption is satisfied.
Let , denote the X restrriiceed Dirichlet form of M,. For each i E [L], E [n]. let x be the X resttricted Dirichlet form of Markov chain M(i on X with stationary density P(t.)) For each and any 9 E (X, (UX,P, P.).
Assumption 2.
C6. (gr, 9.) S CiEi, (gt. 9i),
where C1 > is some constant. Further, each M(s) satisfies the following inequality with some constant C2 > 0:
aa (g:) S C2 (gts 9t).
(3)
Assumption 2 assumes lower bound on the mixing rate the local chains M(.j)) each targeting a single component P(i.)- Efficient mixing within each component is essential, as poor local mixing can limit global exploration and slow the overall convergence of the simulated tempering chain.
Remark 1. In Ge al. (0188), each M; a continuous-tine Langevin diffusion with stationary distribution P.. In this case, condition (2) can be easily satisfied by letting M(.j) be the Langevin diffusion having stationary distribution P(t.))- since
f |1V dr / g Σ ((.))P())))) dx = Σ (ass)
Eg 9b)
which yields Equation (2 with C, However, in our setting each M, a discrete-ting Markov chain (e.g. a Metropolis-Hasting algorithm), and finding Markov chains M(s,) satisfying (2) may not be trivial.
Remark 2. Condition 3 implies that the resttriie spectral gap of Maa at least C, In contrast, Ge et al. 2018 requires each "local chain" to have a positive spectral gap. By weakening this condition, we can develop a decomposition theorem that particularly useful in settings where the usual spectral gap is difficult to bound over the entire state space.

---

Loosely speaking, condition 2 allows us to view the dynamics of M, as governed by the hidden variable J. Conditional on J j. the behavior of M, can be approximated by M(..) The constant
C2 in 33) measures the convergence rate of each ((. on X To bound the convergence rate the simulated tempering Markov chain M, we need one more assumption characterizing the transitions between any (i, and (f'5"). To this end, we construct a projected chain as follows.
Definition 3. Let M be the simulated tempering Markov chain given in Definition 2 and Assumption 7
hold. Define
a((i, a((i, - min P
13. pe(ila)= = ((r.))(ss))())))
(L.) (2:
Pc(x)
Define the projected chain with transition matrix M on [Z] x [n] by
(1- X) / P()))(z)
xo (o.))(20)
(t)
x (x))) ((i,,, j. Φ), (f.5.)))d
if'' = = j
E(K))(())) M((i.)) (k,
j(
It is easy to prove that M is indeed transition rate matrix (i.e., all entries are non -en-etetvve and each row sums to one.) By checking the detailed balance condition, one obtains the following result.
Lemma 1, The stationary distribution of M is given by
P(i.j) (t.() (x))) P(LL) x 20)
Proof. See Appendix B
Assumption 3. Let be the Dirichlet form of M. Then, for any T: [4] x [m] + R, M satisfies the following inequality for some constant C3 > 0:
Var S Cg.
(4)
Assumption assumes a lower bound on the mixing rate of the projected chain. Intuitively, the components are well-separated, transitions between them becomes rare, resulting in slow mixing of the projected chain and, consequently, slow overall convergence of the simulated tempering chain. Conversely, when components are closer and transitions more likely, the chain mixes more rapidly.
Remark 3. Our construction of the projected chain M is significantly different from that in Ge et al. 2018 In particular, Ge et al. [018)] defined the transition between j. by
M ((i..) (i.j') O Chaxx( (P()))
where Xmax (PIQ) max (xx x² (Q) for two distributions P and Q. In Lemmas and in Appendix we show how to bound the Dirichlet form of our projected chain M, denoted by E. Compared to the approach of Ge al. [2018), our argument for bounding E is more straightforward and yields simpler and equally tight bound on the Poincaré constant of the simulated tempering chain in the decomposition theorem.
We are now ready to state our main decomposition theorem, which relates the restricted spectral gap of M to SpecGap (M() for i E j E [n] and SpecGap( (M). Roughly speaking, this result guarantees that the restricted spectral gap of M is (1(C)C,C,)-t).
Theorem 1. Consider the simulated tempering Markov chain M given in Definition Suppose Assumptions 1 and 3 hold, and define
0 P([T. x x)),, o=
= min (20))
4f
Then, we have SpecGap[Z)xaro (M) 2 Czd where
Cм = max 30C',, Ø11 - ((2 - A)Cs + +11 ((pxxx(1.9)
0C,C2
(5)
5

---

Proof. See Appendix B
When X X, we obtain a bound on the spectral gap of M, which similar in spirit to the continuous- time decomposition theorem of [e et al. [2018), though the two results are not directly comparable due the discrete-time setting and our construction of M.
Corollary 1. Consider the simulated tempering Markov chain M given in Definition 2 Suppose
Assumptions I and hold with X X. Then, SpecGap(M) CM where Cı is given by (5)
Proof. This immediately follows from Theorem
2.3 Mixing Time Bounds
Given two probability distributions II, and II, with densities and IT, we define their total variation distance by | T12llt = (x) - my (x)]d,, which takes values in [o, 2]. addition to Assumptions to we need to further require that M is both reversible and lazy, where "lazy" means that M L T {(i,)))) 2 1/2 for any (i, x) E [L.] x X. Both conditions are very mild and commonly used in the sampling literature. Then, if M has positive spectral gap. M converges exponentially fast to its stationary distribution P' in TV distance [Montenegro et al. 2006]. was shown in Atchade [02 that positive restricted spectral gap can also be used to obtain upper bound on the mixing time. The following lemma follows from the result Af(Ahde [202I], where also characterize the exponential convergence rate each temperature level.
Lemma 2. Assume that the simulated tempering Markov chain M, defined in Definition 2 is reversible and lazy, with stationary distribution P. Let po denote the initial distribution, and suppose that pe is absolutely continuous with respect to P. Define fo by
(i, fo(i,x) (().
Let PN denote the distribution of the chain after N steps, and for each temperature level E [L]. define the conditional distribution P.N (dx) x PÑ (i, dx). Fix E E (0, 1). Suppose that there exist constants B > xe 2 q q>> and measurable set X C X such that
1. (.folle(()) S B, where || (leaap) denotes the C w.r.t. P.
2. P([L) x 29)= 2 1 - - )0/0-2)
3. SpecGap (M) 2 C.-
Then, N 2 CM ( we have
3e || - Plev S, and ||P.N Pillov S minke] Tk
for all E [4].
(6)
Proof. See Appendix B
The constant Cw controls the rate of convergence of the simulated tempering chain to its stationary distribution in total variation distance; larger values of C's correspond to slower convergence.
3 Analysis of the Simulated Tempering Metropolis Metropolis-Hastinge Hastings Algorithm for Multivariate Gaussian Mixtures
Let function f: Rd + R be defined by
f(z) = 1--l0 log Σ wse (x-m))
where (4; E d for each i, Σ E ddxdd is positive definite matrix, and w; > for each such that -2 Wi = 1. We want to sample from probability distribution p with probability density
function p² (x) (xe), The target density p" corresponds to mixture of Gaussian components,

---

where each component has mean 14, weight w;, and shared covariance matrix E. We assume that we do have access to the individual means (#4))=1 and weights (w))==1 but we can evaluate f (a) at any point x E IR; the problem would become trivial if (Mi wa) are known.
We illustrate the use of our decomposition theorem by analyzing the sampling complexity of the simulated tempering Metropolis Hastings (STMH) algorithm for target distribution P".
Definition 4 (STMH). Given a target probability density p (I) exp(-f((x)) let
M = M (. (M²)
denote the simulated tempering Markov chain defined in Definition 2 Here,
pt (x) & exp(=3.f<x)),
(8)
where O < 31 <...< - 1 is a sequence of inverse temperatures. The transition kernel M; is that of the Metropolis- Hastings algorithm targeting Pž with a symmetric Gaussian proposal density ((2, y) = NN x, nT), where 1j > O is the step size. The constants Ti are set proportional to Z-/ Za. where Zi is the (unknown) normalizing constant of Pú, and Zi is its estimate. Specifically, set
Zr/Zz
T1
Σ k==1 Zk/ ZZx
so that E ri Et=rr
We define ri x Zi/2; because the true normalizing constants Z; (also known as partition functions, where Z is viewed as a function of the temperature index i) are typically unknown in practice. When implementing the STMH algorithm, the acceptance probability in Equation (I is given by
Ż, cxp((-Bx((x)
xi,, (f,))) min
Z exp(-8.f(zz)
This choice ensures that the acceptance probability depends only on the estimated normalizing constants Z: and not the true values Z, thereby making the algorithm implementable even when Z; unknown. Since acceptance probability depends only the ratio 2,/2p. it is sufficient to estimate the normalizing constants up to a common multiplicative factor. We set Z 1 and estimate the other normalizing constants using the inductive strategy considered by Ge et al. [2018]: for = 1...,, L we run STMH using l inverse temperatures $1 < < B and use the samples at temperature level to compute the estimate Ze-1- This estimation procedure is summarized in Algorithm in Appendix A After obtaining all estimates (Ze)se()), we run STMH using all L temperature levels, and the samples collected at the L-th temperature level can be used approximate the original target density p" (x) e f(=) Algorithm | in Appendix A summarizes the STMH algorithm given in Definition 4. assuming all partition functions are known.
The following theorem provides a mixing time bound for the STMH algorithm targeting the distribu- tion P Directly applying the spectral gap decomposition in Corollary [[ss very challenging, since it remains unclear how to effectively bound the spectral gap of the Metropolis-Hastings chain over an unbounded domain. In contrast, such bounds are more tractable within bounded regions (Yuen) 2000). This motivates the of the decomposition of restricted spectral gap given in Theorem Theorem 2. Let f(x) be defined as in Equation 7 and define
max
[pall V/umin kE(m)
max
Wmin := min Wij 15i5n
Tmmax
Vmin
where "imax and Miii denote the largest and smallest eigenvalues of the covariance matrix E, re- spectively. Then, assuming d is fixed, STMH algorithm can be used to generate a sample from distribution that is within total variation distance of the target distribution P*, in time
(_.
poly
log
Wmin
Proof. See Appendix C where precise version of the time complexity bound is also provided. -
7

---

Remark 4. The parameter D captures the spread and separation of the Gaussian mixture components since m ||p M,ll s 2D by the triangle inequality.
Remark 5. The time complexity in Theorem 2 is polynomial in the separation parameter D, log- arithmic in the inverse accuracy 1/e, and exponential the dimension d. In fixed-dimensional settings-whers d is constant-thir result provides high-accuracy guarantees, showing that STMH is particularly effective for sampling from such mixture distributions. For comparison, the proximal sampler incurs time complexity with exponential dependence on D, since the log-Sobolev constant and Poincaré constant for a Gaussian mixture distribution decays exponentially in D; see [Schlichting (211)] To further illustrate the scaling behavior of the proximal sampler, consider mixture of two Gaussians with identical covariance matrices and means located at (-m/2,....
mm/2) and m respectively. In this case, the separation becomes D = my which implies that the complexity of the proximal sampler scales exponentially in both m and d. The simulated temper- ing Langevin Monte Carlo (STLMC) algorithm Ge et al. (2018) admits an upper bound that scales polynomially with D, d, and 1/c. In contrast, the upper bound we obtain for STMH exhibits only a logarithmic dependence on 1 1/e, representing a sfate-of-the-
theoretical guarantee among existing known upper bounds. Table [ summarizes the theoretical complexity of STMH in comparison with several other sampling algorithms. It can be seen that no algorithm dominates STMH in terms of the complexity dependence on and 1/e. Our upper bound on the time complexity of STMH has exponential dependence on d, which is likely due to the use of the random walk Metropolis-Hasting (RWMH) sampler for each local chain M5. We conjecture that by replacing with proximal sam- pler [Chen et al. 2022 He et al.) 2024a] or cetroolis-adjustee Langevin algorithm [Wu et al., (2022). the resulting simulated tempering algorithm may achieve a better complexity dependence on
Remark 6. Theorem Dectoremesttallishhss convergence guarantees for STMH when sampling from a mixture of Gaussians with a shared covariance matrix. This result can be naturally extended to target distributions that are sufficiently close such mixtures, following an approach similar that Ge et al. 2018). In such cases, the time complexity would additionally depend on closeness between the actual distribution and the Gaussian mixture approximation. We also anticipate that similar techniques can be adapted to handle mixtures of log-concave distributions that are translates to each other, or more broadly, distributions that are well-approximated by such mixtures. However, as demonstrated by Ge et al. [2018], some seemingly mild violations of the assumptions, such as component covariance matrices differing by a constant factor, can lead to exponential time complexity for any reasonable algorithm with similar guarantees.
establishes
Algorithm
d D poly poly
1/E
STLMC Gee et al.
2018
poly
LMC
[Vempala and Wibisono
2019
d exp( D2y2
1/E²
Annealed LMC (Guo et al.
2024
poly
poly
poly
Proximal Sampler [ann et al
2023
d/2
exp(
log(1/s)
LMC (data-initialized) Koehler et al. 2024
poly
exp( D2y2
1/e²
STMH
exp
poly
log (1/e)
Table 1:
Dependence of time complexity on d, D and e for sampling from densities of the form in
The proof of Theorem is divided into several steps. In order to apply the decomposition arguments developed in Section we first define an approximate STMH chain that satisfies Assumption [
Definition 5 (Approximate STMH). Let
M = M (Goo) (ro)en (M:) (Mo)...))..
denote the simulated tempering Markov chain defined in Definition 2 where
{- (x T 11)) }
(x(x) w. exp
(9)
and transition kernel Mr is that of the Metropolis-Hasting algorithm targeling De. with symmetric Gaussian proposal density g(x, y) = N x. 17T) where step size 11 > O. The weights (ri) and are the same as in Definition 4
8

---

The stationary densities P; in Definition are mixtures of Gaussian densities; denote the component distributions by P(.... This enables us to apply Theorem | It is important to note that this approximate STMH sampler cannot be implemented in practice, as it requires knowledge of the component distributions, which is typically unavailable. We show that, for some X C R the X re-restricted spectral gap of the STMH chain constructed in Definition 4 is comparable to that of the approximate STMH chain given in Definition [ result is a discrete-timg extension of the argument used in Ge et al. (018], which suggests that adjusting the temperature is roughly equivalent to modifying the variance of Gaussian distribution. As result, it suffices to obtain a lower bound on the 2 reestricee spectral gap for the approximate STMH chain. Note that since Br- = 1, Pr. PL. = p"-
(see Lemma 9 in Appendix (C.T) This comparison
Next, we apply Theorem to derive a lower bound on the X -estttriete spectral gap of the approx- imate STMH chain. This involves three steps. First, we verify inequality (2) in Appendix C.2.I by comparing the transition density of the chain M(. with that of M, Second, we need to com- pute the X -esteictie spectral gap of the "local chain" M(a.)). which we define as the random walk Metropolis- Hastings algorithm targeting P(c.). the Gaussian distribution with mean J4y and covariance matrix 15 It is well known that for strongly log-concave target distributions, the MetsopolissHastings algorithm should mix fast [Johndrow and Smith [018]. To explicitly compute the bound, we apply the path method on continuous spaces proposed by [Yuen] 2000), which is detailed in Appendix C.2.2 Finally, the projected chain captures transitions between mixture com- ponents and temperature levels. Intuitively, it should mix fast because (i) if 31 is sufficiently small, the component distributions P(..))-..., P(...) overlap significantly, and (ii) if B B/BB-1 is not too big, then P(e.)) and P(E-1.)) also share substantial overlap. To compute lower bound on the spectral gap for the projected chain, we apply the well-known canonical path method [Levin and Peres 2017 see Appendix C.2.4]
To conclude the proof, derive error bounds on the estimated partition functions in Appendix C.4.3
4 Simulation Study
To numerically investigate the complexity of the STMH algorithm, we perform a simulation study with target distribution being a symmetric two-dimensional Gaussian mixture distribution, whose density is given by
1 N p" (z(x) =
D
1 + 2
D
12, 12
Ii
12, 12.12) 2/2
2/2
where /2 is the 2 x 2 identity matrix and 12 = (T, The parameter D controls the separation between the two components. We vary the parameter D to explore how increasing the separation between the modes affects the convergence behavior of the algorithm. For each value of D. we run the STMH algorithm with the parameters specified in Appendix C and initialized at (10, 10). To assess convergence, we monitor how quickly the empirical mean of the samples, denoted by f., approaches the true mean of the target distribution, 0). If the chain has not yet mixed, it tends to spend more time near one mode, resulting in an empirical mean that deviates from the target mean. Moreover, according to Nishiyamal [2022). when the empirical and target distribution have the same covariance matrix, we can lower bound their TV distance by |[a|2//CC + ||āll²) for some constant > O, which is a monotone increasing function of || |2. This justifies the use of || as measure of convergence. To reduce variability, we repeat the simulation 20, 000 times for each fixed D and average the empirical means over all runs. To provide a benchmark, we also run the baseline Hattopolis-Hasting (MH) algorithm under the same setup and compare its convergence behavior with that of STMH. All simulations were performed on a standard consumer- grade CPU with parallelization and completed within approximately six hours.
In the left panel of Figure I we plot the number of steps required for the empirical mean to fall below 0.1 for both STMH and the baseline MH algorithm. The error bars are obtained by computing the 95% coverage interval of the empirical mean at each step, and then determining the corresponding number of steps needed for the lower and upper bounds of the interval to cross the 0.1 threshold. The results show that this number grows approximately linearly with D for STMH, consistent with the theoretical bound in Theorem In contrast, for the baseline MH algorithm the number of

---

steps increases exponentially with D², reflecting its slower convergence, which is consistent with the well-known behavior of MH. To analyze how the mixing time depends on the threshold E, we fix D 30 and plot how || varies with the number of steps N in the right panel of Figure [ For STMH, the results show an approximately linear relationship between the number of steps and log" 2 (1/ll/ll), consistent with the theoretical bound in Theorem 2 In contrast, for the baseline MH algorithm the relationship is closer to logarithmic, implying polynomial dependence of the mixing time on 1/E, which aligns with the well-known limitations of MH in achieving high accuracy. The error bars represent 95% coverage intervals of the empirical mean, with the delta method applied to obtain the corresponding intervals for log" (1/ll Overall, these simulations demonstrate that STMH provides more efficient sampling from this Gaussian mixture distribution compared MH.
3300
STMW
ETypeea lical
22500
Number of stage Lnd (IA
10000
5000
1000
2000
Figure I: Left: number of steps until ||p|| < 0.1 versus D². Right: log? (1/1lATl versus the number of steps N for D 30.
5 Concluding Remarks
Simulated tempering addresses the challenge of sampling from multimodal distributions. In this work, we develop a general theoretical framework for analyzing simulated tempering and demonstrate its effectiveness through detailed analysis of simulated tempering combined with the Metropo- lis as-Hastings algorithm for sampling from Gaussian mixtures. Our framework can be used to analyze simulated tempering combined with other local MCMC samplers, such as the Metropolis-adjustee Langevin algorithm (MALA) and proximal algorithms, but verifying Assumptions 2 computing the constants C1, Cz. C3 these settings may be more involved. particular. ar, since has been shown in the literature that the dimensional dependence of the complexity of MALA for
and 3 and
log-concave target distributions is (vvd) [Chewi et al. 2021 Wu et al. 2022 it would be interesting to investigate the complexity of simulated tempering combined with MALA has a similar polyno- the exponential dependence in our result. Another promising
mial dependence on d, improving direction for future work is to generalize our techniques to a broader class of target distributions beyond Gaussian mixtures. The argument of Ge et al. [2018) can be used to extend our result to target distributions that are "sufficiently close" to Gaussian mixtures. Finally, while this work primarily focuses establishing lower bounds on the spectral gap, interesting direction for future work to investigate the tightness of these bounds by also deriving upper bounds on the spectral gap for simulated tempering Markov chains.
6
Acknowledgments
Jhanvi Garg and Quan Zhou were supported in part by NSF grants DMS-2245591 and DMS-2311307. Krishnakumar Balasubramanian was supported in part by NSF grant DMS-2413426.
References
Yves F Atchadé. Approximate spectral gaps for Markov chain mixing times in high dimensions.
SIAM Journal on Mathematics of Data Science, 3(3):854-872, 2021.
10

---

Yves F Atchadé, Gareth O Roberts, and Jeffrey S Rosenthal. Towards optimal scaling of Metropolis- coupled Markov chain Monte Carlo. Statistics and Computing, 21:555-568, 2011.
Krishna Balasubramanian, Sinho Chewi, Murat A Erdogdu, Adil Salim, and Shunshi Zhang. Towards theory of non-log-concaye concave sampling: first-order stationarity guarantees for Langevin Monte Carlo. In Conference on Leurning Thevry, pages 1996-2923. PMLR, 2022.
Steve Brooks, Andrew Gelman, Galin Jones, and Xiao-Li Meng. Handbook of Markov chain Monte Carlo. CRC press, 2011.
Hyunwoong Chang and Quan Zhou. Dimension-free relaxation times of informed MCMC samplers on discrete spaces. arXiv preprint arXiv:2404.03867, 2024.
Omar Chehab, Anna Korba, Austin Stromme, and Adrien Vacher. Provable convergence and limitations of geometric tempering for Langevin dynamies. arXiv preprint arXlv:2410.09697,
2024.
Yongxin Chen, Sinho Chewi, Adil Salim, and Andre Wibisono. Improved analysis for a proximal algorithm for sampling. In Conference on Learning Theory, pages 2984-300 3014. PMLR, 2022.
Sinho Chewi. Log-concave sampling, 2023. Book draft available at https://chwwisinho. github. io, 2024.
Sinho Chewi, Chen Lu, Kwangjun Ahn, Xiang Cheng, Thibaut Le Gouic, and Philippe Rigollet. Optimal dimension dependence of the detropolis-adjusted Langevin algorithm. In Conference on Learning Theory, pages 1260-1300. PMLR, 2021.
Nicolas Chopin, Omiros Papaspiliopoulos, et al. An introduction to sequential Monte Carlo, volume 4. Springer, 2020.
John Dagpunar. Simulation and Monte Carlo: With applications in finance and MCMC. John Wiley & Sons, 2007.
Pierre Del Moral, Arnaud Doucet, and Ajay Jasra. Sequential Monte Carlo samplers. Journal of the Royal Statistical Society Series B: Statistical Methodology, 68(3):411 1--36, 2006.
Alain Durmus and fric Moulines. Nonasymptotic convergence analysis for the unadjusted Langevin algorithm. The Annals of Applied Probability, pages 1551-1587, 2017.
Murat A Erdogdu and Rasa Hosseinzadeh. On the convergence of Langevin Monte Carlo: The interplay between tail growth and smoothness. In Conference on Learning Theory, pages 1776- 1822. PMLR, 2021.
Murat A Erdogdu, Lester Mackey, and Ohad Shamir. Global non-convex optimization with discretized diffusions. Advances in Neural Information Processing Systems, 31, 2018.
Jiaojiao Fan, Bo Yuan, and Yongxin Chen. Improved dimension dependence of a proximal algorithm for sampling. In The Thirty Sixth Annual Conference on Learning Theory, pages 1473-1521. PMLR, 2023.
Rong Ge, Holden Lee, and Andrej Risteski. Simulated tempering Langevin Monte Carlo ii: An improved proof using soft Markov chain decomposition. arXiv preprint arXiv: 1at:::0122009933 2018.
Gelman et al. Bayesian data analysis, 3rd: Boca Raton. Texts Statistical Science, 2013.
Wei Guo, Molei Tao, and Yongxin Chen. Provable benefit of annealed Langevin Monte Carlo for non-log-concave sampling. arXiv preprint 1.X1:24407.16936 2024.
Ye He, Alireza -ossseii,,,,,,in Krishna Balasubramanian, and Murat A Erdogdu. A separation in heavy-tailed sampling: Gaussian vs. stable oracles for proximal samplers. In The Thirty- eighth Annual Conference on Neural Information Processing Systems, 2024a. URL https
//openreview..o //openeevie...e//oooriiicc
Ye He, Kevin Rojas, and Molei Tao. Zeroth-order samplinng methods for non-log-concave distributions: Alleviating metastability by denoising diffusion. arXiv preprint arXiv: 2024b.
11

---

Xunpeng Huang, Hanze Dong, HAO Yifan, Yian Ma, and Tong Zhang. Reverse diffusion Monte Carlo. In The Twelfth International Conference on Learning Representations, 2023.
Xunpeng Huang, Difan Zou, Hanze Dong, Yi-An Ma, and Tong Zhang. Faster sampling without isoperimetry via diffusion-based Monte Carlo. In The Thirty Seventh Annual Conference on Learning Theory, pages 2438-2493. PMLR, 2024.
James E Johndrow and Aaron Smith. Fast mixing of Metropolis-Hasting with unimodal targets. arXiv preprint arXiv: 1ao.::0044044440 2018.
Frederic Koehler, Holden Lee, and Andrej Risteski. Sampling approximately low-rank Ising models: MCMC meets variational methods. In Conference on Learning Theory, pages 4945-4988. PMLR, 2022.
Frederic Koehler, Holden Lee, and Thuy-Duong Vuong. Efficiently learning and sampling multimodal distributions with data-based initialization. arXiv preprint urXiv:2411.09117 2024.
David Landau and Kurt Binder. A guide to Monte Carlo simulations in statistical physics. Cambridge university press, 2021.
Krzysztof Latuszyiskii, Matthew T Moores, and Timothée Stumpf-Fétizon. MCMC for multi-modal distributions. arXiv preprint arXiv:2501.05900 2025.
Holden Lee and Matheau Santana- Gijzen. Convergence bounds for sequential Monte Carlo on multimodal distributions using soft decomposition. arXiv preprint arXiv:2405. 19555,3300. 2024.
David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathemat- ical Soc., 2017.
Jun S Liu and Rong Chen. Sequential Monte Carlo methods for dynamic systems. Journal of the American statistical association, 93(443):1032-144 1998.
Jun Liu and Jun S Liu. Monte Carlo strategies in scientific computing, volume 10. Springer, 2001.
Neal Madras and Dana Randall. Markov chain decomposition for convergence rate analysis. Annals of Applied Probability, pages 581-606, 2002.
Enzo Marinari and Giorgio Parisi. Simulated tempering: a new Monte Carlo scheme. Europhysics letters, 19(6):451, 1992.
Ravi Montenegro, Prasad Tetali, et Mathematical aspects of mixing times in Markov chains. Foundations and Trends@ in Theoretical Computer Science, 1(3):237-354, 2006.
Wenlong Mou, Nicolas Flammarion, Martin Wainwright, and Peter L Bartlett. Improved bounds for discretization of Langevin diffusions: Near-optimal rates without convexity. Bernoulli, 28(3):
1577-1601, 2022.
Alireza Mousavi-Hosseini, Tyler K Farghly, Ye He, Krishna Balasubramanian, and Murat A Erdogdu. Towards complete analysis of Langevin Monte Carlo: Beyond Poincaré inequality. In The Thirty Sixth Annual Conference on Learning Theory, pages 1-35. PMLR, 2023.
Radford M Neal. Annealed importance sampling, Statistics and computing, 11:125 111125-19,,00 2001.
Mark EJ Newman and Gerard T Barkema. Monte Carlo methods in statistical physics. Clarendon Press, 1999.
Tomohiro Nishiyama. Lower bounds for the total variation distance given means and variances of distributions. arXiv preprint arXiv:22/2.05820, 2022.
Art B Owen. Monte Carlo theory, methods and examples, 2013.
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient Langevin dynamics: a nonasymptotic analysis. In Conference on Learning Theory, pages 1674-1703. PMLR, 2017.
12

---

Christian P Robert, George Casella, and George Casella. Monte Carlo statistical methods, volume 2. Springer, 1999.
André Schlichting. Poincaré and log-Sobolev inequalities for mixtures. Entropy, 21(1):89, 2019.
Robert H Swendsen and Sheng Wang. Replica Monte Carlo simulation of spin-glasses. Physical review letters, 57(21):2607, 1986.
Saifuddin Syed, Alexandre Bouchard-Côté Kevin Chern, and Arnaud Doucet. Optimised annealed sequential Monte Carlo samplers. arXiv preprint arXiv:2408. 12057, 2024.
Santosh Vempala and Andre Wibisono. Rapid convergence of the unadjusted Langevin algorithm: Isoperimetry suffices. Advances in neural information processing systems, 32, 2019.
Dawn B Woodard, Scott C Schmidler, and Mark Huber. Conditions for rapid mixing of parallel and simulated tempering multimodal distributions. The Annals of Applied Probability, 19(2): 617-640, 2009.
Keru Wu, Scott Schmidler, and Yuansi Chen. Minimax mixing time of the Metropolis-adjusted Langevin algorithm for log-coneave sampling. Journal of Machine Learning Research, 23(270): 1-63, 2022.
Wai Kong Yuen. Applications of geometric bounds to the convergence rate of Markov chains on R Stochastic processes and their applications, 87(1):1-23, 2000.
Zhongrong Zheng. On swapping and simulated tempering algorithms. Stochastic Processes and their Applications, 104(1):131-154 2003.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims in the abstract and introduction clearly state the main contributions and consistent with the theoretical and empirical results presented in the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
The paper discusses the limitations of the work in the conclusion section, highlighting potential extensions and directions for future research.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model spelfspeciiiitionn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All theoretical results are accompanied by clearly stated assumptions and complete, rigorous proofs. Proofs provided the appendix are referenced appropriately in the main text.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
14

---

The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The paper provides all necessary details to reproduce the experiments, includ- ing clear algorithm descriptions and parameter settings.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
The code is included ZIP file (code.zip) reproduce the experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
15

---

Please see the NeurIPS code and data submission guidelines (https://mips.co httpa///ggiieee//ooeuuubiiiii
oon for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ cttpss.ccppullcc/ggue gwtp://wweee/eeeeeeeeeeee /eddeeeeSSo www.iimiisiooooPoiioiooi for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: The paper does not involve standard training/test splits. However, all algorith- mic parameters are clearly specified.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
The paper reports error bars that are appropriately defined and clearly pre- sented.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
16

---

For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The experiment was run on a standard consumer-grade CPU with paralleliza-
tion and completed within approximately six hours.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
The research fully adheres the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper presents foundational theoretical results on sampling from complex, multimodal distributions. While the work tied to specific application or deployment, it has implications for domains such as Bayesian inference, generative modeling, and scientific computing. Given its theoretical nature, do not foresee any direct societal impacts at this stage.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper does not release any models or datasets that pose risk of misuse require safeguards.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use any external assets such as third-party code, datasets, or pretrained models.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version the asset used and, possible, include URI
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
18

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
This paper does not introduce or release any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve human subjects or crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve human subjects or crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
19

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: The research does not use LLMs as part of its core methods.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy for what should or should not be described.
20

---

Appendices
A Simulated Tempering Metropolis-Hastingg algorithm
Algorithm 1 Simulated Tempering Metsopolis-Haattings Algorithm
1: Input: funetion f. inverse temperatures f1,..., Be, partition function estimates Zi.... Ze,
number of steps N, step size 77, rate X, initial covariance matrix Eg.
2: Sample 20g (0, Σo)
3: - 1, 4- Io. <
4: while n N do
5: Sample u ~ Bernouli(AA.
6: if then
7: Propose x' ~ [[ m/)
8:
Sample v Uniform(0, 1) PeT())
9:
if e min I, --Petio)
then
10:
I t+r x'
11:
end
12:
else
13:
Propose = i 1, each with probability 1/2
14:
if S 1' L then
15:
Sample v ~ Uniform (0,
-. f(x) /2, 1, e 8,11a)/2.
16:
v min
then
17:
1-1
18:
end if
19:
end end if
20:
21:
n1 4- n
22:
end while
23:
Output: Sample (x, i) collected at the Nthh step.
Algorithm 2 Partition Function Estimation
Input: function f, inverse temperature sequence 31 By and number of samples s.
2,
for 8= = 1 to L do
Repeat Algorithm until samples (ız)}=1 are obtained at temperature level l.
Zo+1 (Zr/s) Σラ= e( (e))
end for
Remark Algorithm is always run for a fixed number of steps N and returns the sample obtained at the final step. In Algorithm if this sample is not from the desired temperature level, Algorithm simply re-run for another N steps.
21

---

B Proofs for Section 2
B.1 Proof of Lemma
Proof. Clearly, Σig P(i,)) = Hence, it only remains to check the detailed balance condition
((.)),
P((d M(() (((
for two types of moves. First, let i be fixed and consider j # j'. Then,
r. (u.) (), (i,5") = = / "(n)Pos)())) ((.))) dx, p;(x)
which is clearly symmetric with respect to j and j'. Similarly, if fixed and = (assuming both i, [L), we have
ram Pun))) M(.))))))
(+ (f,
X x
min (rww,,)))))))))))
dr,
x
which is symmetric with respect to and 6'.
B.2 Proof of Theorem 1
We first prove auxiliary lemma on the Dirichlet form of the simulated tempering Markov chain. Lemma 3. The [L] X restricted Dirichlet form ε( of the simulated tempering Markov chain M, defined in Definition can be expressed by
L (o ri (1- i=1
+ +xE& XE (9.9),
where vo oo is the resttriccedd Dirichlet form of the Markov chain M, 9 (3 x X, P) with gi(x) = g(i, for each i [L] and
(9,9)) 4
Σ
- / ol() (it (f,,)) dr.
(. 1'=
Proof. Since the stationary density M is p(i,x) = (x) and either x or is fixed in each simulated tempering iteration, the restricted Dirichlet form x (g.g) can be expressed by
Σ
(o(2,x)) - (0(t,,))(((u)))) o(i,u))² r.pd) rx):()) M ((i.x). dy)) dæ
i=1 xx
(10)
i,re[L]: #=id1 / (o(i,x) g(' r.p(()) M (((,a),, (f,,)) dr.
Σ
+ 2
dy) and M, has stationary density pi. Since M (i,, dy)) = (1- (1- M)M
1=1 x0 (g(1,)) g(),))) r (x)) M (() dr
/ (9.(z) - (v))²² (x(x) M (1 dy)dr = (1- A)
I
Σ r E (g..
2
i=1
For the second term the right-hand side of (OO). note that X
M ((i, x) ()) a(((,, (F,,
where the acceptance probability function given by IT. straightforward calculation then concludes the proof of the lemma.
D
22

---

Next, we prove two key lemmas about the Dirichlet form & of the Markov chain M constructed in Definition 3
Let P([L] )). Recall that under Assumption
|
we can augment the stationary
density to
f(i,,æ)) = (i.))))))) (z).
still denote the corresponding probability measure by P. Let Po denote the conditional probability measure given X E X², whose density is given by
po(1, (L)))))))))))))))
The Dirichlet form & can be expressed by
E(g.g)= = (g.g)
( + (g. +E'(g.0)
where
I.
$7.7
1
Σ
- F(i,j'))² rew( ((.,))))rr.ww...)
P ((,)
(((i,,))((,3)))
20
i=1
3,y==1
1
8' (7.0)
(T(1.) 5)) (.w(ss)) (.,,)))rramm))))) P ().
28
1=1 L
v=itl
Lemma Suppose Assumption
holds. For any g E (2((L) x P), define g:: X - R by x [n] - R by
(xxx) =g(i, z). and define g: [L]
((. / g x) (()
P(is)) (20) dr.
Then,
2(1 X)
L (i
3 (7. V 0
Var 2ar (g:).
Po.n)(2
Proof. For every x E X, E [L] and every pair j. E [n]. the following inequality holds
-(i,)))(i,,)))) < 2 (g(1. j) - g(i, x))² + (o(1,5") - g((, x)),
Hence, using the expression for M (i)) we get
E (..9)) 1-
(o(i,)) ,(i, 9(t.)")) (reeee)))))) f ((n)()))(()))))d
20
1=1 =1'=1
(1 - >) Σ Σ r(w((w)) ( ((0(i.)- 2( + (g(i,5") x) ((as)
0 Ps(j" (x((())))
da
1=1 =1
= -1- - + -"(1, - 9((,x))*]
(11)
where P denotes the joint probability measure of JI, X) with density
p(i,j.5',z) r.W(c.)P..)))) pr(j'lz)=
r (,,)(, (z).
0 pp((x)
for i E [L]. E [n]. E X Hence, under P, the joint distribution of and that of (I, X) are both given by Po. and thus
Ep (T(IJ)) g(1, x(), + (g(1, g(1, x)) = 2E -
g(1, x))] (12)
23

---

Since g(i.j) = E X) = i,J -], we find that
Epp (ī(I,)) g(T, x(), = Ep. p (1,) P ((n (29))
(xl, 5)
(a,)
Var Varp
(13)
(X
1=1 j=1
where in the last step we have used
[g(i.z) - g(i.,)} (()))(x) ((a
Var [=1,,=
drdy.
2 x0
(())) (()))
The claim then follows from Lemma 5. Consider the setting of Lemma 4
12 and (3).
We also have
E' CG.
3\ 0
L
Var Vor (g))
31 of (g.9)
(o3)
Proof. For every x E X, every pair i, [L]. and each j [n]. (g(i.)) "((" .)) 3 (g(i.)) - x)) + (g(i, g(i,, x()',x))) xx)² + (g(d' -(("
Then, using the definition of M(ii,) (t', ()) for = =i we get
(g.
A
Σ
Σ (g(i.)) ()' / ((),,))(((,s),)),, (f.
40
#=
31 I
Ep (T(I.)) x(T,x))² (g(1,X) g( x))² (7(1' -"",,))"',xx] x1) where is the probability measure of (1, I', J, X) with density [.W( (I) a( (i. 2), (f'.).))
2
if = i
20
,(i,i,j..)
f(i,i+ p(i, 1- 1,
if =1,
otherwise.
That is. we first draw J. Po and then update I' by proposing I' - with equal probability and accept it with probability a((i,,, j. x). (i'.j, j.)... Since the update for I' given 1, J, X is reversible with respect to Po. we also have (I', J, X) ~ Po. Hence,
Ep [=(()())) x(,,
Ep (g(L', 9(1', x)) = =Epo (
which has been characterized in 13 Finally,
Ep [((T, - ((T'xx))
1
Σ
Σ
(g(1,xx) (it (1,
20
i, iiit1 j=1
Σ
Σ
(g(i,z) - ((('xx)) min f (r.) (4), Te (x))) do
20
i,PE[L]] =ittl J=1
x
<
1
Σ
I (o(i,z) g(i', 2)) min (r.p((x), (x) dr
20
1.PE(L]: v=tt1
2
0
24

---

where (g. g) is defined in Lemma E, min E,min mij b,} min ES jj. Ej bj
Note that in the inequality above, we have used that for two non-negative sequences ay.
Proof of Theorem 7 Fix an arbitrary 9 E (LL x P). Define, for each i, g:: X + R by ge(x)) g(i and 7: [L] [m]
R by
g(i, 2) / No
P())(o)) dr.
g(i.j)
Note that g(,jj) is the conditional expectation of g(, X) given = and J = f under the joint probability measure Po. and P(i,j) is the marginal probability of I T= i, = under Po. Hence, by the law of total variance, Assumption and Equation 13 we find that
Varn, (0) Varp(g)
P(,,) Varn Varno -=,
j=1
(t,)
C3E(g.9)
Var (0))
0P (27)
Using (x))) 2 o and Assumption 2
OP Po.))) Var (r
(i.)
(g.) S
C2
r4
wass (()
C₁C₂
Σ (
0Φ
Recall that Elg.g) =E¹ -g'0 + + (g.g). By Lemma 4
2(1 A)
L a Til((i
2(1 2(1-A)C1C2 C2
L
3 (g.9)
Varp Varp x.)))))) S
E (gi,
(gi, 9t).
0
1=1 (2)))
By Lemma
31
n
31
E
Var xo)) + ot
(g:)
(g,()
(20)
0
j=1
32
31 E (gi,
< 0Φ
(90
Hence,
0 Var = Varn <
3XCa
(2 + 1]
Σ (0
0Φ
Comparing with Lemma 3 we obtain the Poincaré inequality for M
BC1C2 ((2 + A)Css + 11} E(1xxx0
Varp(()xxxo()) (g) max 30Cs, 6(1-X)
which concludes the proof of the theorem.
B.3 Proof for the Mixing Times
We first recall the mixing time bound given in Atchadé et al. [2011) using restricted spectral gaps.
Lemma 6 Atchade al. (2011). Let K be a lazy, reversible Markov transition kernel on state space Zt with stationary distribution II. Suppose the initial distribution Ho absolutely continuous
with respect to II, and define
(dlw) [lw()
25

---

Assume there exist constants B > 1 and > 2 such that ( S B, where ||
(I)) denotes
the L"-norm with respect to I1. Let E (0,1). 1). Further, suppose there exists a measurable subset Ω S such that
a/(a-2)
IT(29) 2 20BB
Then, for
2
N SpecGap K))
log E²
the total variation distance between the distribution of the Markov chain K after N steps and its stationary distribution Il is at most E.
Proof of Lemma 2
The first part of Equation (6) follows directly from Lemma 6 To prove the second
part of 6 we first note that the TV distance between P.V and P admits the following lower bound
(i, P(i, P(i,dx)) 2 f (11"(1,a--ra00)) (r)s( for all E [L]
||N Plly
For each i [L], let Mi PN (1, The TV distance between P.N. and P. is bounded by
| I (i, P. 1.11. / | IiiNee (i,x) p((x) dz
||PN Pollev
< / Mike" (1,z) - -ri'p" x)) dx + / "r:'p" (i,x) pi(x)
/ | (1,2x) - -r (i, dx + + Pllv.
where the first inequality follows from the triangle inequality. For the first term the last expression, using Ti = PN (i, X) we get
f Mridee (1,)) - ri p (1, de = ri lrs - r,,N S - I|
Pllv
where in the last step we use r; = P(A) and 11, = (N)) with A = {i} X. Combining the above two displayed inequalities and using the first part of Equation we get
3 E.
IP,. Prlly S
E E
2r;
2 m I'k
This completes the proof.
26

---

C Appendix for Section 3
C.1
Comparison of STMH chain with approximate STMH chain
To compare the STMH chain defined in Definition&Awill with the approximate STMH chain in Definition 5 it suffices to compare the stationary density P with Ps and transition kernel M2 with M,. For the former, we use Lemma 7.3 of of et al. [2018), which shows that varying the temperature roughly the same changing the variance of Gaussian distribution. For the latter, we derive a bound in Lemma g
Lemma (Lemma 7.3 of Ge et al. (018). Let < 8 S 1, and suppose Wi,.... Wn > are weights such that Di=1 Wi 1. Define the density fanctiins
(x)
Σ mETT(() and #(x)
Wazg (Ir),
where Thy.... Ta are component densities. Then,
Wmin" T(x) S <T)
(())
Wmin
where Wmin == miminnge sinn W/y
Lemma 8. For each E [L]. les Mt be the transition kernel defined Definition f with transition density m.. Also, let M, be the transition kernel defined in Desimition 5 with transition density m,,
Assume that Wmin == min sm Wi > O. Then, for all + E R. the following inequality holds
( I
m (z. y)
w
min
Proof. Let q denote the symmetric Gaussian proposal density used in the Metropolis Haatopolis-Hastingss algorithms Mf and M,. Then, for x * y, the transition densities are given by
mę v) (x. y) az (x, v), m,(x, y) q(z, v) (1 v).
where
af (2, min {1,
(v)
p (x) { ã.(,, min {
(v)
P:
Using Lemma 7 have
Pi(v) <
pł (v)
and pi(x) 2 Wmin (x),
Whnin
which gives
(((y)
I p((1)
(((x))
(x)
Hence,
m, y) <
a(x v) (2,
m (2,, (1,
w²
minn
Winn
which completes the proof.
From now on, we assume that X C Rd is measurable subset. Our next result, Lemma g shows that it suffices to obtain a lower bound on the [4] x -estttiidt spectral gap of the approximate STMH chain in order to derive corresponding bound for the STMH chain.
Lemma 9, Let M be the STMH chain defined in Definition 4 and let M be the approximate STMH chain defined in Definition S
Assume that the mixture weights satisfy Wiin minigisn Wy
Then, the [L] x X² rrestricted spectral gaps of M and M satisfy the inequality
1 SpecGap (M.).
SpeoGapppxxx000) S
w min
27

---

Proof. Let p" and denote the stationary densities of the Markov chains M and M, respectively.
Then, for all E [L] and E R2, we have
p¹ (i, - =rpp and x(i,)) - (.)
By Lemma| we have
Wmin (a( S (x) S w min Px(2)
(14)
for every (i, 2). and the same inequality holds for p" (i, x) and p(i, x) since the weights (r4) are the
same for pa and P. Let (1lxxx::114xx denote the [L] x xx -restriite Dirichlet forms associated with M and M respectively. Fix function y L ([L) X, P) and define gi (3) g(i, x)) for each (i,x). By Definition 1 suffices to show that
1
[M (g) S winnn
Var 2,12/(12x00000 (g), and E x (g.9)
x
w
For the first inequality, follows from that
/ (g(i,x) -((i pli, pli. v) dæ dy
111x=,14xxx00 S 2w min
x 2
i=1
j=1
Var Var (,1
By Lemma we have
I -1
Σ Ti & + ε (g, g),
(15)
and Eir [r]xxxo can be decomposed analogously. We will bound the two terms on the right-hand side of Equation (15) separately. For the first term, we apply Lemmas 7 and
8 to get
1 / / (a(x)) 9.())) (x)) (x, dr
(0r, 9.)
2 x x
S 2w min Sta./ (g((x) 9x(v)) px(x) M1 dy) da
For the second term, we apply Lemma to get
5I ())
1
Σ S(e. (di(z)-gr(an gx(2)) min (r.7.(x), (x)r dr
Σ
/ - ge min (ripi(a), (epe(x)) dx
< 4 Wmin
(g.g).
Wmin
Combining both bounds, obtain that (( S E 9), which concludes the proof.
C.2
Restricted Spectral Gap of the Approximate STMH Chain
We begin by introducing some notation. For each i E [L] and j E [n], define the j-th component of the density P. as
(x) x exp { ( ((y-)))TT T (x m1)
(16)
28

---

so that P; is a weighted mixture of the P(a.) 's:
(x( Σ ())(
Let M(J)) denote the Metropolis Hastings transition kernel targeting P(i.)) with symmetric Gaussian proposal density g(,, y) (y; n/), where v/ 0 the step size. We set
x = Rd ||-||| - R}
where R > 0 is fixed radius. To obtain a lower bound on the [L] -rsttriide spectral gap of the approximate STMH chain, invoke Theorem Assumption holds by construction of P. The following lemmas verify the other two assumptions required for this theorem.
C.2.1 Validation of Condition 22 in Assumption 2
Lemma 10. For each E [T), let ps be the density defined in Equation (9. and let 9t E (x, Then the following inequality holds
a
Σ
wy (0,.)) S (g. 9i) E [Z]
where E( denotes the x -restricted Dirichlet form of the kernel Mi.s) and &, denotes the X resttriccted Dirichlet form of the kernel Md as defined Definition
In particular, for the approximate STMH chain M defined in Definition condition holds with constant Cj = 1.
Proof. For any nonnegative real sequences {az} and {by}. we have the inequality min az, aj bソ 2 E, min {a,, bj} Applying this to p. = EE= (yP() we obtain
min (1))
Σ W min j=1
(17)
for x, E Rd and E [L]. Let denote the symmetric Gaussian proposal density associated with the Metropolis-Hastingg algorithms M, and M(.)). Then, applying Equation 17
we obtain
1
/ x
Ex (gr, 91)
(gi(x) gı(=))² ((x, min (+)))) dæ
2 x
1
(gi(x) - gx(=))² g(xx 2) Σ wy min (x) dr
This completes the proof of the Lemma.
C.2.2 Validation of Condition 3 in Assumption! 2
We lower bound the 2 restrricted spectral gap of each Metropolis- Hastings chain Mas) using the path method of Yuen (2000 in the following lemma.
Lemma 11. Let < S R2. For each [T.] and j E [n], the Markov chain Mass admits the following lower bound on its 0 restricted spectral gap
4/2
3/2
SpecGap (M(n))
Imin
29

---

In particular, for the approximate STMH chain M defined in Definition constant
condition
3
holds with
13R
C2
4/2
Jmin
Proof. We use the linear path method described in Section of Yuen 20000 This approach also extends to the restricted spectral gap setting; see, for example, Atchadé 2021 1 and and[Chang and Zhou [2024) where the canonical path method has been adapted the restricted spectral gap in discrete spaces. For each pair (I, y) E x x X we construct a linear path connecting æ to y, with all intermediate points lying in X Fix step size ò > 0, and define the number of steps along the path
by
|0 yl
bay
The path is then given by
(110) 1
(2xw) Tay
Yxy =
where
(Dry
1).: + by for sis bav.
12
bay
Let : fieyy (I E 2 x ) denote the collection of all such paths, and let E denote the set of all edges that appear in least one path Yey r. The capacity of edge (u, v) E given by
Tans(,,)) = (u) mus)(u v) (u) a(u, v) min {1, P(.n(o) ] (()
where ((. denotes the transition density corresponding to the kernel M(..)) and q(u, v) is the Gaussian proposal density associated with kernel M(.)) As shown in Section 2 of Yuen [2000] , the set of paths I' satisfies the regularity conditions and, for any (u, v) Tay the associated Jacobian satisfies Jn. (u, v) bg (see Yuen 2000 page 5] for details). Then, by Theorem 2.1 and Corollary 2.4 Yuen 2000), we have
SpecGap2 (M(s) 2 A
(18)
where
A css sup
Σ
hig P(iss) Po.n)))) bd
(u, v)
(a
Tay ((u,))
and Ysyl denotes the length of the path Yey. Since P(a)) log-concave, for any (u, v) E Yey. we have
min (F),)) P(o)(e)) I min (u),)) (v))
Hence, (us)(u, 2 a(u, v) min ( (1))) and we can upper bound A as
A < dd+1 ess sup
q(u,v)-
Σ
P(os)(ean))
(19)
(u,N)EE
where b = max (x9)) bry and Zn,yy y is defined
x, (tx (x),
Zz.9 =
y. otherwise.
Note that
2A12 Tmmm yd/2
(Enm)) 5
and the proposal density q(u, v) given by
|10 2112
g(u, v) = (2mm))d/2 exp
2n
30

---

Substituting this into Equation 19 we obtain
8 d/2
/
2/22++
||u
1
A
eSS sup exp
4/2
(u,e)E
27
mmin
where we have also used that an edge (u, 1) belongs to most 6² paths in r. Choose step size 5 = V51,, which yields
2R V
R
b -
Since 3 S 1, we obtain that
8 pd+
13R
A S
2.5
miin 1) 3/22
4/2
m
d/2
1/3/2
From Equation 18 we get
1
Tmin
d/2
1/3/2
SpecGapx M M(x))
A
13Rd+3
which concludes the proof.
C.2.3 Auxiliary Lemmas
To verify Assumption 3 and compute the constant C3 in condition (4) we will need several lemmas. The proof of Lemma is omitted.
Lemma 12 (Canonical Paths Bound). Let S be finite state space, and let K be the transition kernel of reversible Markov chain on with stationary distribution TI and Dirichlet form E. For each pair consisting of valid transitions under K,
of distinct states x. y E S, let "/z denote path from ie.,
I = - - Let I (Tzy : x,y 8, x f y be the collection of such paths for all distinct pairs (x, (). The edge congestion associated with I' is defined as
+
In-1 In y.
Pe(l')
Σ
K.VES
((,)
K(u,))>
(u,o)E EI
where lywyl denotes the length of the path Tay. Then, for any function g + R. the following Poincaré inequality holds
Varn(g) S Pe (g.g).
Lemma 13. Let II, be two probability distributions (absolutely continuous with respect to each other) with density function x, & respectively. Then,
de f min -1- i1 2 1 V
Lemma 14. Let [Σ] denote the determinant of matrix E. The Kullback-Leite divergence between two d-dimensional Gaussian distributions with equal means is given by
1
[2 En
KL (N E,) (N, E2)) log
- + tr(E E1)
Lemma 15. Let D max [maxke(n) |oll (imiu)
For each i E [L], j E [n]], define
f001z)= = Wi ())(())()))
for all x E Rdd
Σ
we (1)
k=1
where P(ss) (x) denotes the density defined in Equation E Rdd, the following inequalities hold
16.. Then, for all i E [L], j E [n], and
d/2
Bi
(| + +)}2
(x) 2
exp
(20)
2max
27min
B
p 2 wy exp
(||=]] + D)²
(21)
Timnn
31

---

Proof. To prove Equation 20), we write
B
d/2
3: 2 2 (x- E - (x mz)
(())
exp
YmrYmaxx
where the inequality follows from the bound
|Σ| S 1
mmxx
Next, we the inequality _
1
(1 - (5)-wa) --) 11)11
myll
(||=]|| ||
(||=]l D)2
Mini
Timn
7mmi
obtain
P(. (x)
B
d/2
exp
Be
(11=]] + D)²)
2T Ymaxx
27min
This establishes Equation (20). To prove Equation (21).
we define the function J: RR + |n] by
J(x) == arg max (a). kEinl
follows that for every [n].
(x) S (1,T(t))))))
and therefore,
wk P(L (x)
we P (i.T(()) (x) Pa),Taa)
Substituting this upper bound into the definition of (i x), get
wyP(t,)) P(t,((z))) (z)
p(11))
(22)
To simplify the ratio of Gaussian densities on the right-hand side, expand the expression explicitly as
(Z)))() exp { -B:(1((u)) - m1)) - 1 (uJE~ - 11(0e Σ - 33)n)))) (()))())) (x)
By definition of D, we have [|{](()) - -Mill s 2D. Using the Cauchy-Sehwarz inequality, we obtain
2D
(1()(()) (1j) E s || Mall Bell-|[E-aa ||E-1x1 x11 ||| -
||
Viiia
and similarly,
2D
11 1 14 13(())
Σ 3-1M3(e) $ (112)12+ |1 11) S
Viin
Yuin
Putting these together, we get
(x)
(-& (2DI|=) + D2) 2
Bi Vmin
81 (-B(11)
(())
exp
exp
Ymin
(||=] D)2)
(23)
Equations
and
23 together prove Equation
21
This completes the proof.
C.2.4 Validation of Condition in Assumption 3
Let M denote the projected chain associated with the approximate STMH chain M. We next establish a lower bound on the spectral gap of M using the canonical paths method. Recall that we define 0 {x RRd ||>||| < R).
Lemma 16. Let M denote the approximate STMH chain defined in Definition
Define the following
parameters
min
D==mas max
||uk]]s II, Vinin
[E(M)
max4e(1] ri
Suppose the following conditions hold
32

---

(i) Let R Z vdD be such that ((c.))229) 2 3/4 for all i E [L] and j E [n]]
(ii) 31 = (Tmmn// D2) and 31 1,
(iii) /
for all E [L--1 1].
Let M be the projected chain defined in Definition associated with M. Under these conditions, M satisfies the spectral gap bound
3 min A), r²
SpecGap(M) 2 eex(add
64L2nd/2 exp(ed)
where e. >>> O is fixed constant. In particular, for the approximate STMH chuin M, condition (4) holds with constant
C3 = 64I.2 exp(cd)
3 min A), 2}
Proof. We construct the canonical paths as follows. Fix two arbitrary states x = (i.j). y = (d', e [L] [n] with i i i'.
(a) j J', , let Ywu be (i,j) > (1 111) + +
(b) If j j', let Tay be (i, (i-1,3) -... (1.j) (1,5¹) (2.j')+ (f,5").
Define Yyu as the reverse of Yay- Let denote the collection of such paths over all distinct pairs (x,, 3). Let i [L]. [m], and i' i E [Z]. From the definition of M we have
> f (x) ()) (f.5) = 2 (()))
()) (f)).)) dx,
where the acceptance probability is given by
Fv P(r
1
a()..,,)). = min
ri P(..) (x)
Hence, the probability of transitioning from state (i, (i 1,5) under the projected chain M is given by
A
/
Ti-1 (())))(=), P(sslee) dr, ri
(1-1)) 2P (P x
min
for all i (,..... L} and j E [n]] Since ri-1/T; by definition and P(os)(2 1, we have
((i.)) 2 Ar
/ min (Fu-1.)(4)) (a))())))))) dr.
(24)
2 x0
By Lemma 13 and Lemma 14
and
f min (pt- (1)) dx 2 1
[KL(P(s)) P(o-1.9)
I
V
Vd
Bg
> 1
2 V
where f(x) = x 1 log x.
For 2 1, we have f(x) S (x 1)2/2 /2. Hence, if B 1/ 1/vd, then
[ min ())11)) (x)) dx 2 2
Condition (i) implies
[ min {p)-1))( (()n))))))))) dx 1
x
33

---

Substituting the above bound in Equation
24
we obtain
Ar
M((i.)), (i- 8
Similarly, we can derive the bound
Ar 8
(i
for all i e [T.- 1}, j [n].
Next, derive a lower bound on the transition probability from (1,j) (1,j") in the projected chain M, which is given by
(1.1")) = =1 21 Jxo P(,)(() G1
j.j [n]. S1, 1, we obtain
P(i (20)
By applying Lemma 15 and noting that (2))))
31
d/2
J
(- [-281
2
(1|z|l + D)}) dr.
((1,,), 2 (1 Ajma
exp
2mxx
Ymin such that
x
By condition (ii), there exist fixed constants C1. 02
7min
Ymmn
< 31 < C2
D2
D2
Let X2 far (z) (01....,,30 Ra) TRdd |
I D for all i E [d]] S X
Then for any X.,
have |||||| + D S 2vdD, which implies
exp (- 2/31 (|+l + D)2 2 exp
83,dD2
2 exp(-88222)
Timin
Pmin
Therefore, obtain the following lower bound
4/2
M(I.)). 2 (1 A)wy (c,)//2
Ymin
exp(-802d) Vol(X
max D2
where Vol(x denotes the volume of the cube X.D Substituting Vol(x = (2D)4, we get
d/2
(1,15) 2 (1 -))a) 24/2
Pmmn
(2D)d
2 D2
2 (1 A)wa K d/2 exp(-ccd
(25)
where e
is fixed constant.
Let "iyy be a path between any two vertices x, y E [L] x [n]. Then, haa I 2L. We now derive an upper bound on the edge congestion Pe (T) defined in Lemma 12 Let 2, E [L] x [n].
(a) Let (i, and w (i 1.)). Then the edge (z, w) is used only by paths between vertices and such that one lies in the set S == {i..... L} {j}. and the other in Sr. Therefore, its contribution to edge congestion is bounded by
Σ ((an))er((..)))))))))
Yeyl P(x) P())
(2L) ((S) P((i,)) (i 1,5))
P((i,j)) ((((,)), 1,
where
(2
P((C,A) Teti
E k [n]
P([L) xz0)'
denotes the stationary distribution of the projected chain M. We have the following bounds P(S) P(li L} {i})
4L
Ar
S1 (i 8
P((i.j))
P((ij))
3r
where the first bound follows from condition (i). Combining these, we conclude
Σ Eie.eerrtteoonaHLL..e hzy P(xr) P(u) S 3x'
64I.
(((1.)) M((,.). 11,))
Similarly, we obtain the same bound for (i.j) and w (i + 1,j).
34

---

(b) Let = (1, and w= (1, Then the edge (2. w) is used only by paths between vertices and y such that one of them lies in the set [L] {.} and the other in [L] {j"}. Therefore, its contribution to edge congestion is bounded by
Ees.)erraa Nay P(x) P(y) P((1,)) ((1,5), (1,31)
(2L) P([L) GD) P(LL) x D'D) P((I, ()) ((,
(1.3"))
We now bound each term on the right-hand side. By condition (i), we have
4L
P(L) x (')) = 4wy
P(L)) x ()) -
P((1,))),
3r
and from Equation 25 we have
(((1,)). 2 (1 Alwz x x-2 exp(-ca)
Combining these, we obtain
Ex..)) 1709 P(x) P(y) P((1,)) M((1,)), (1,j"))
32I.2n//22 exp(ed)
9(1 - A)r
Let À E 10, be a fixed constant. Thus, the edge congestion associated with I' is bounded by
64L 4/2 exp(cd) Pe 3 min (1 - A), A} 72
From Lemma 12 projected chain M satisfies the Poincaré inequality
64T2 exp(ed)
Var=()) <
m A}, E(G.)) 9).
gg:
L x [n] + R,
where E denotes the Dirichlet form associated with the projected chain M. This completes the proof of the lemma.
C.2.5 Restricted Spectral Gap Bound
We now invoke Theorem I to bound the [4] x -esttsttdeeed spectral gap of the approximate STMH chain M, formalized in the next lemma.
Lemma 17. Let M denote the approximate STMH chain, as defined in Definition with À being fixed constant. Under the same conditions as in Lemma 16 the [L] X restricted spectral gap of M admits the following lower bound
7min 2 7 3/2
4/2
SpecGappLii.xo(M) 2 Ω
Rd43 2/2 exp(ed)
where e >> is a fixed constant.
Proof. For the approximate STMH chain M, Assumption satisfied with constants Cj and
13Rd-3
C₂
d/2 m 3/222
Additionally, Assumption holdd with
4/2
C 3 min (1 A)
where e fixed constant. Since À is treated as fixed, combining these with Theorem D completes the proof of the lemma.
35

---

C.3 Restricted Spectral Gap of the STMH chain
We now establish lower bound on the [L] X -restriice spectral gap of the STMH chain M as formalized in next lemma.
Lemma 18. Let M be the STMH chain, as defined in Definition 4 with X being a fixed constant.
Under the same conditions as in Lemma 16 the [L] x X rrettricced spectral gap of M admits the lower bound
w min T 2) Rd+3 122 exp(ed)
d/2
Lp (M*) 2 Ω
where >> 0 is a fixed constant.
Proof. This follows directly from Lemma and Lemma 17
C.4 Estimation of Partition Functions
C.4.1 Assumptions on the Parameters
We now describe how to choose the algorithm ceaametrr-nnmbbee of temperature levels L, inverse temperature sequence (B:) temperature-swap rate X, proposal step size n, initial covariance matrix so that the STMH algorithm achieves asserted time complexity.
Eg, number of iterations Noso Recall that x Tmax/ TImax/Tmin Tmin
D2 Tmin
L + k {2 + log wiin + dl (1 + log x)} log
+
(26)
Piuin
Bi+1
1
Ymin
B1 = θ
min
1+
for i E [L 1],
(27)
D
B
Vd'
D22
Ymaxx
2
where v/ = 1 + log k +
log
d
Wmmn
20 L
R= D v dR.22 + 22 log
(28)
N Ca 2/22 exp(c'd)
L2kdd
log
for some fixed constants &' C²
(29)
4/2 Mmin w
62w2 min
Σg I where of -
(Naiin)
Ymin
(30)
81
À is any fixed constant,
(31)
7 R
(32)
C.4.2 Auxiliary Lemmas
Lemma 19. Let be an integer. Assume the partition-function estimates 7,,... 2r satisfy
2r/Zi
[[1- 4)) (1 (1+
for all i [L].
(33)
2
Define
Zi/Z,
T
for all i E [4].
L
Zw/Zu
k=1
Then,
-2
2²
< r; <
for forall's [Z].
(34)
L
36

---

Moreover.
m 2
[a Pi
Proof. For each E [L], define b; Zi/ Zi, and denote their sum by S,
L
by
Then r; = b/S.. From Equation 33) we have, for every i E [L].
(1 + ((--11)) K bi
I (1 - ()- -)-11)
(35)
which gives
Lb (1 -1)1(111
$ S s Lbi - -
(36)
Combining Equations
35 with 36).
wc get
by
bi (L + 11-+1)-(4-1)
1 1
r
Lb [L - 1)-
and
(1 11-1-1)-4-1)
L 1-1
ri -
Lbj (L (L+ = L L-1
Define
Cr L -ー 1-1
Taking logarithms and using log(1 + x) S x for all -1, we obtain
log CL (L 1L-11 1) log 1 : s (L 1) 121) 2,
so Cr. S e2. Likewise C7 2 -2 Therefore
c T S ri T
e² for all E [L],
establishing 34
This further implies that e completing the proof of the lemma.
Lemma 20, Let L > O be an integer, and suppose B1 and og satisfy Equation 27 and Equation 330
respectively. Then the initial density is given by
(1,-)) = (0.
- for all i E (1),
with the corresponding distribution denoted by po, The stationary density of the STMH chain M as defined in Definition
is
p(i.z) = (Z), ie [L], E Rd
19 and the component densities (p; (e))) are given in Equa- tion 8 Let P denote the corresponding stationary distribution. Define fo == dP0 /dP. Then,
where (ra).m are defined in Lemma
exp(c2d) L 4/2
1l I
Winin
for some fixed constants C1, C2 > 0.
Proof. The L norm of fo given by
( Σ
1.
/
pli, (5((,
1 (1, n pī(x)
dx,
(37)
37

---

where the second equality follows from the fact that po is supported only on = 1. By Lemma for all
R2 we have
pi (x) Wiin Pi (x)
Wmin
(
(38)
==1
where pi is defined in Equation and P(1.)) is defined in Equation (16). Substituting 38 into 37 we obtain
(1)(1,)))
1oll S
de.
Σj ()P(1.)
T1
Using the convexity of the x divvergeeece, we further bound this as
Σ ws / (1*
I 1 v
dx.
(39)
(()))
jml
For each j E [n], the density P(1,)) can be lower bounded as
(1),)(1))
2max
31
d/2
exp
2mii
31
11 m9l13)
(40)
Since (1,,)) ~ NO0 og we have
( (L,,
2TO (210))
exp (-
1 |1x1(3) (-o3 0
From Equation
30 we have fixed constants
< $1, 82 < 2 such that
Tmin
7min
< 00
S
B1
B1
This gives
B1
31
(L.)))
exp
|0||
(41)
2T8 Timin
82 Ymin
Substituting Equations
and
41
into Equation
we obtain
[| [ (P)
1/2
B1
4/2
31
[1 82)
82 Hy
2
my
exp
exp
dr
84 Tmi j=1
(2
82 7min
2'mi 82
82
d/2 d/2
82
W exp
B1
|| 112
of (2
d/) d/2 Wimin
(2
82 Train
From Equation
27 we have a fixed constant
$3 > 0 such that B S SyYmin/ D Substituting this,
we get
kd/2 4/2
[ < of 4/2 Wiii
$3
exp
2
82
19 we have 2 L)) Substituting this into the above bound on || I1 proves the lemma.
By Lemma
Lemma 21. Let follow the d-dimensional Gaussian distribution with mean p and covariance matrix E. Denote the largest eigenvalue of E by [[]] Then,
IP (I
|||||| + / E/ + /2|EE] log( log(1/e)) 2
38

---

Proof. Using the standard concentration inequality for Lipschitz functions of Gaussian random vectors, we get
P P plll 2 wll) + Se -2--//111 /2/1111111
Since B(IIX- pll) S v | we get
PP (IXX alll 2 vdjill +1 Se Se-1/211111
Letting -= 2/mxx (1g( and applying triangle inequality, get the asserted bound.
Lemma 22. Suppose 1 < E S I,, and let Algorithm [ be run with the potential function f(x) defined in Equation 7 inverse temperatures 31 <. < Be, and using the parameters specified
in Equations (27).
29). (30). 31 and (32. Assume that the partition function estimates
Zz...., Ze satisfy Equation 333. Let PM denote the distribution obtained after running Algorithm
for N steps, and let denote its stationary distribution. Then the total variation distance between
and PN satisfies
P PN I E.
Proof. Under the assumptions of the lemma, and by Lemmas 18 and 19 the [E] resteitte spectral gap of M* satisfies
d/2
w min min nd la xd/2 exp(ed)
XpecGapiexxx(M Ω
where c > is a fixed constant. Moreover, from Lemma where
20
2 is bounded above by B,
B Ci exp(c2d)ex<12
Wmin
and C1, > O are fixed constants. Applying Lemma with the above parameters yields the desired
total variation bound.
Lemma 23, Assume the same conditions and notations as Lemma 22 Let P denote the marginal stationary distribution temperature level l. with density (z(z) (x)(-3:f(z)), and let P.N denote the marginal distribution at level é after rumning Algoritium for N steps, with density Pd (x) x PN (f. Then the total variation distance between P and PNN bounded by
3e
|P- PN I
Proof. By Lemma 19
we have min Pi 1/(e²(). The proof now follows directly from Lem-
mas 2 and 22
In the following lemma, we analyze how many times Algorithm Mustt be re-run, with fixed number of steps N. in order to obtain sample from the desired temperature level.
Lemma 24. Suppose the partition function estimates 2....., Ze satisfy Equation 33
Let IN E [$]
denote the temperature index of the state returned after running Algorithm 7 for N steps. Suppose
the algorithm is run independently T times, each for N steps. Then, for any fixed temperature level E [d) if
T 2 (loo(())
a (0, 1),
the probability that least one of the T runs returns a sample from level k satisfies
P(tte [T] such that 1 = 2 1 a-a.
where 1 is the temperature level returned in the t-th run.
39

---

Proof. Let k E [e]. From Lemma 19 we have
P(Ix *k) 1-
1 P(IN =b) s e26
Hence,
P( AL (7) such that / = =k) S (1- 3 exp{- - -
Setting this upper bound no larger than 6, and solving for T. completes the proof of the lemma.
n
Assuming the partition function estimates satisfy Equation (33). we have shown that the algorithm
reaches total variation distance at most within the time complexity specified in Equation (29).
We now show that partition function estimates satisfy Equation (33) By combining these two components, establish the overall time complexity for the complete algorithm.
Lemma 25. Let E (0, 1) and S S L. Suppose the parameters satisfy Equations 26
(30 31 and 32). and assume that the partition function estimates Zi..... Ze satisfy Equation (3
Let L (og(L Collect samples from Algorithm 7 denoted by (x,)ā=1- Define the next
partition function estimate Ze+1
Ze11 == = Zi, where ::= Σ
exp -b)s((;))
j=1
Then, with probability at least 8, the estimate Ze41 also satisfies Equation 33 In particular,
Z 2
E (11-
1 +.
+
The proof of Lemma 25 requires the following results.
Lemma 26 (Lemma 9.1 of Ge et al. [2018). Suppose that P1 and P2 are probability measures N with density functions (with respect to a reference measure)
91 (x)
92(2x
(1(x)
and P2(x)
Z1
Zz
Suppose P1 is measure such that ||P Pilly < cc/2C², and g2(z) E [0, for all x e Z2 Given samples 21,..., from Ps, define the random variable
92 (xx)
91 (2(4
Let
g2 Z22
P
91 (x)
Z₁
and suppose r 2 1/C. Then with probability at least e nd? /(20*)
Sc c.
Lemma 27 (Lemma G.16 of Ge al. 2018)- Suppose that [(x log (Σi wi - -x(x)]]]] where fa(x) fo(x - pt), and fo TR. + k-strongly convex and K K-smooth function. For any a 0, let Pa denote the probability measure with density pa(x) eaf(()) Let Za be the
corresponding normalization constant, given by Za -pe - af(()) dx. Suppose that [| S for all [ni,, and let a, 3 > Let
K
2
= D
Vd + dlog
+ 2 log
Vax
K
Whii
If a < B, then
WERd
min (a(
(x)
2
Z
Zg
and
ZB
Z,o
_e
18 k
40

---

Proof of Lemma 25 By Equation 27 and Lemma 27 we have
1f exp (- (z)f(z)) [0,1/(2e]]
exp(-Be/(I))
for all L E [L - 1]. Moreover, by substituting = 4/(3EL) into Lemma 23
we obtain
2e²
1 - -P-pP 1lev
when
N C' CL cxp(c'd)
LA
log
d/2 1 min min
w min
where C², d' 0 are fixed constants. Next, by applying Lemma 26 with constants C 1/2e and
= L/L, we obtain the following bound
7 2e/Zt
1
1 L
E
1
L
The lemma then follows by induction on
C.4.3 Proof of Theorem 2
Proof of Theorem Let L denote the number of temperature levels defined in Equation (26) By applying Lemma 25 inductively with 8 = E/(4L), we obtain that, with probability at least E/4, the following bound holds
Ze Ze
1+ ++1) {
11-2)
Ž
for all E [L].
Z1
To ensure this guarantee, it sufficess to generate
L log (4L/s) samples from each temperature level [L] resulting a total of sL = L log (4L/s) samples from Algorithm
Applying
log (og(L/E))) we obtain that, with probability at least 1 E/4, 4, we obtain Lemma 24 with e/
8 samples from each temperature level [L] by running Algorithm [ for N steps (as defined in
Equation 29 and repeating this process independently T times, where
T'= - e² Log
-
=2
= L
4L
log
AL4
log
4L
)
Hence, the total time complexity for getting partition function estimates is
C' L k2/2 exp(c'd) log
LK EWmin
T partition -
d/2 S min Yuin
where C'C' >
0 are fixed constants. By applying Lemma 23 and Lemma 24 we conclude that, with probability at least - e/4, Algorithm I produces sample from distribution that is within total variation distance e/4 of the target distribution pa time T sampling where
(*)
C" Rod exp(e" log
12
sampling = 22 L log
4/2 m Vuin min
E² E wiin
C² Cd R/22 exp(c'd)
Lx
log?
d/2 5 min min
(Wwiin
where d' C,C',"",C" are fixed constants.
The overall time complexity T consists of two components: the time to get partition function estimates, and the time to generate sample from the target distribution
T T partition + T Tampling:
This completes the proof of the theorem.
41


Reviews:
[{"review_id": "junv0rCCU6", "reviewer": "Reviewer_36i2", "summary": "The work provides a framework of analysing the convergence of STMH algorithms using a restricted spectral gap. First, in Theorem 2 they provide a general bound on the Spectral Gap. Next, in Theorem 5, the authors provide a time bound on obtaining samples (with a STMH algorithm) from a distribution \\epsilon TV distance from a (multivariate normal mixture) target distribution. They frame the theoretical result they achieve amongst other theoretical results in the literature and give comparisons. Finally they offer an empirical result and observe how close their bound is in practice.", "questions": "1. My understanding is that r_i is a hyperparameter of the STMH algorithm which a practitioner would have to specify beforehand. As such, is it realistic to specify r_i as in Line 220? When one knows the target density (e.g. multivariate Gaussian mixture) perhaps this is possible, but this is not a situation in which practitioners will find themselves?\n\n2. To what extent can we understand whether the Assumptions on which Theorem 5 relies are true for the MVN-mixture case? Are the empirical results merely an inspection of the underlying assumptions and ‘what happens if they are not true’? More discussion on this would be appreciated, and would further justify the existence of the results section.\n\n3. What about those same assumptions applied to more realistic applied settings? Do you have any thoughts regarding what would happen?", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n1. The problem of sampling from mixture distributions is well known and is a fundamental task in MCMC sampling. Work towards this problem is certainly valuable.\n\n2. Concise introduction, which efficiently lays out the context of the problem. It also provides a literature review which appears comprehensive and is easy to follow and understand.\n\n3. The mathematics is easy to follow, and is well structured and concise. The bound achieved in Theorem 5, a time bound on achieving samples within \\epilson TV distance from the target, seems very strong and useful. I also greatly appreciate the comparison to STLMC, it provides details of the relative strengths of their results and provides some intuition.\n\n4. I appreciate the details regarding the proof of Theorem 5, and also like the fact this is included in the main text. It offers a lot of intuition for the various pieces of the proof, and gives readers an understanding from a high level.\n\nWeaknesses:\n1. I would like to see more justification for this work: what examples in the literature are there of people using STMH in practice? What implications will this work have on the wider field, how should it be interpreted etc?\n\n2. I would appreciate some text on the interpretation of a spectral gap. I would also appreciate a more gentle/intuitive introduction to the simulated tempering algorithm.\n\n3. I would appreciate a more intuitive (in words) explanation of many of the assumptions of the paper (namely, Assumptions 1 and 2). Are they standard assumptions? Are they likely true in reality? What are the consequences on performance if they aren’t true? More generally, there is very little intuition given to many of the assumptions, constants, and bounds throughout. Perhaps a large readership will be familiar with such concepts, but to those outside that group this is hard to interpret and thus use.\n\n4. I would appreciate more justification as to why we should care about convergence results on the STMH algorithm - what are the implications of such results? What is the practical advice to be gained from this paper? \n\n5. There is very little discussion on their empirical results: why is it only ‘approximately’ linear (Figure 1) - my understanding is that given the theoretical results it should be exactly linear? Is the discrepancy down to the assumptions not holding in practice?\n\nMinor: \n1. Why is Theorem 2 not Theorem 1 (same with Theorem 5, shouldn’t this be Theorem 2)?\n\n2. What is meant by [Line 178] ‘which can be compared to the continuous-time decomposition theorem of Ge et al. [2018]’ - is it that the bounds align, if so, say that. Or is it that the results can now be directly compared?\n\n3. Section 3 studies STMH on a multivariate Gaussian mixture, I think this should be clear from the Section title.", "was_revised": true, "final_justification": "The authors have responded clearly to my biggest concerns.\n\nThe other reviewers clearly agree the paper has merits, is easy to read, and is interesting.\n\nI leave my initial scores in tact, as I still feel my score reflects the merits of the paper.", "rebuttal": "First of all, we sincerely appreciate your careful reading of our work and your detailed feedback.  Below please find our point-by-point responses. \n\n**Weakness 1.**\nThanks for the question. Simulated tempering (ST) is a widely used MCMC sampling technique (see, e.g., the textbook [1]). The use of STMH dates back at least to the seminal work of [2] on the Ising model, and it remains as one of the most popular methods for tackling metastability in the chemical/statistical physics literature [3]. In Bayesian statistics, the theory and methodology of tempering-based methods have also been studied extensively since the work of [4]. \n\nST can be combined with any local MCMC kernel. In this work, we choose to focus on the random walk MH algorithm, which is a simple but illustrative and analytically tractable example. We analyze the complexity of STMH using a new decomposition theorem, which can also be used to analyze the convergence of ST combined with other local schemes such as MALA. Further, we expect that this technique can be adapted for analyzing other tempering-based algorithms such as parallel tempering (which has been utilized in many deep learning tasks [5, 6]), and those more advanced variants of ST  such as non-reversible ST [7].  Although random walk MH could be a naive choice in some applied settings, the broader contribution of this work lies in the general theoretical framework we develop, which can inform the analysis and design of general tempering-based samplers. \n\n[1] S. Brooks, A. Gelman, G. Jones, and X. Meng, eds. \"Handbook of Markov Chain Monte Carlo.'' CRC press, 2011. \n\n[2] E. Marinari, and P. Giorgio. \"Simulated tempering: a new Monte Carlo scheme.'' *Europhysics Letters* 19.6 (1992): 451. \n\n[3] Z. You, L. Li, J. Lu, and H. Ge. ``Integrated tempering enhanced sampling method as the infinite switching limit of simulated tempering.\" *The Journal of Chemical Physics* 149.8 (2018).\n\n[4] C. J. Geyer, and E. A. Thompson. \"Annealing Markov chain Monte Carlo with applications to ancestral inference.\" *Journal of the American Statistical Association 90.431* (1995): 909-920. \n\n[5] C. Smith, Q. T. Campbell, and T. Albash. ``Optimizing temperature distributions for training neural quantum states using parallel tempering.\" *Physical Review E* 111.5 (2025): 055306.\n\n[6] W. Deng, Q. Feng, L. Gao, F. Liang, and G. Lin. \"Non-convex learning via replica exchange stochastic gradient mcmc.\" In *International Conference on Machine Learning*, pp. 2474-2483. PMLR, 2020.\n\n[7] M. Biron-Lattes, T. Campbell, and A. Bouchard-Côté. \"Automatic regenerative simulation via non-reversible simulated tempering.\" *Journal of the American Statistical Association* 120.549 (2025): 318-330. \n\n**Weakness 2.** \nWe thank the reviewer for the suggestion. Roughly speaking, the spectral gap of a Markov chain quantifies the average-case convergence rate towards the stationary distribution; a larger gap implies faster mixing and thus more efficient sampling. However, in many scenarios, the spectral gap can be difficult to bound or vanish quickly, and the restricted spectral gap serves as a more robust and informative technique. \n\nTo explain simulated tempering more intuitively: the key idea is to augment the state space with a temperature index that allows the chain to move between a family of distributions, ranging from the original target distribution (low temperature) to a flattened version (high temperature). At higher temperatures, the probability landscape becomes smoother, allowing the chain to move more easily between modes. Transitions between temperature levels are governed by a Metropolis–Hastings rule, and samples from the target distribution are obtained by collecting states only at the lowest temperature (target distribution). This helps overcome the energy barriers between modes and promotes global exploration.\n\n**Weakness 3.** \nThanks for the suggestion. Assumptions 1 and 2 are motivated by the structure of mixture models, also used in prior works such as [8]. \nIntuitively, the sampler's convergence can be arbitrarily slow if (i) the mixture components are very far away from each other, or (ii) the mixing of the local chain targeting a single component is very slow (e.g. due to non-log-concavity). So some conditions are always needed to achieve a meaningful bound. We also want to clarify that these assumptions are only made for the decomposition theorem, and when applying the decomposition theorem to Gaussian mixtures, we rigorously prove that these assumptions hold. \nWe agree that a more intuitive explanation would improve clarity, and in the revised version, we will include more discussion on the intuition behind the assumptions and interpretation of key constants and bounds. \n\n[8] R. Ge, H. Lee, and A. Risteski. \"Simulated tempering Langevin Monte Carlo ii: An improved proof using soft Markov chain decomposition.\" arXiv preprint arXiv:1812.00793 (2018). \n\n**Weakness 4.** \nThanks for the question. First, our result characterizes the complexity of the algorithm (e.g. polynomial dependence on D),  which tells practitioners how the runtime of the algorithm scales as the problem becomes more difficult. Note that the dependence on other key parameters such as component weights and condition number is given in our proof of Theorem 5 in Appendix C.4.3. \nSecond, our result also provides practical guidance for how the tuning parameters of ST should be selected such as the temperature ladder; see Appendix C.4. \n\n**Weakness 5.** \nWe thank the reviewer for the thoughtful question. In Figure 1, we empirically study the convergence behavior of STMH as a function of mode separation. The observed relationship is approximately linear rather than exact, likely because (i) we use the rate at which the empirical sample mean approaches the target mean as a proxy for convergence, rather than measuring the total variation distance directly, and (ii) our theoretical result provides only an upper bound on the convergence time, rather than an exact characterization. \n\n**Minor 1.**\nWe will correct it in the revision. Thanks for pointing it out.  \n\n**Minor 2.** \nOur result is similar in spirit to the decomposition theorem in Ge et al. (2018) but not directly comparable, as our results applies in a discrete-time setting under different assumptions. We will clarify this in the revision.\n \n**Minor 3.** \nThanks for the suggestion. We will update the section title accordingly. \n\n\n**Question 1.** \nThank you for the question. To clarify, $r_i$ is not needed to run the algorithm, and we define $r_i \\propto Z_i / \\hat{Z}_i$ exactly because  $Z_i$ is typically unknown in practice. When implementing the STMH algorithm, one needs to evaluate the acceptance probability given in Equation (1), and this definition of $r_i$ ensures that the acceptance probability is independent of $Z_i$ and relies solely on the estimate $\\hat{Z}_i$. In Appendix C.4, we show how sufficiently good estimates for  $\\hat{Z}_i$ can be determined, which makes the whole STMH algorithm fully implementable. We understand that the writing might have caused confusion and will clarify this in the revision. \n\n**Question 2.** \nThanks for the thoughtful question. Thm 5 establishes the convergence guarantees for  STMH  when  sampling from a mixture of Gaussians with shared covariance matrix. This result can be naturally extended to target distributions that are sufficiently close to such Gaussian mixtures, as shown in Ge et al. (2018). In such cases, the time complexity would additionally depend on closeness between the actual distribution and the Gaussian mixture approximation. We also anticipate that similar techniques can be adapted to handle mixtures of log-concave distributions that are translates to each other, or more broadly, distributions that are well-approximated by such mixtures. However, as demonstrated by Ge et al. (2018), some seemingly mild violations of the assumptions, such as component covariance matrices differing by a constant factor, can lead to exponential time complexity for any reasonable algorithm with similar guarantees. \n\n**Question 3.** \nFollowing up on our answer to Q2, there are realistic applied settings where our assumptions may approximately hold, making the proposed framework useful. For instance,  [9] showed that the posterior distribution for Bayesian variable selection (which is one of the most common model selection problems in statistics) can be approximated by a mixture of Gaussians under certain conditions.  Another relevant application arises in the context of (Bayesian) DNNs.  Let the target be $e^{-f}$. In the context of DNN, $f$ is the loss composed with a neural network function, and the complexity of sampling will depend on the structure of $f$. If the widths of the neural networks tend to infinity, several works have shown that $f$ satisfied PL-type conditions and hence recent works like [10, 11, 12] could be used to show  $e^{-f}$ satisfies Poincare or Log-Sobolev type inequalities. Therefore, algorithms like LMC, proximal sampler or MALA can be used to sample from the posterior efficiently. However, in the practical regime where the width is finite, the $e^{-f}$ does not satisfy any isoperimetric inequalities and is highly multimodal, where the proposed algorithm is likely to be useful. \n \n[9] I. Castillo, J. Schmidt-Hieber  and A. Van der Vaart. \"Bayesian linear regression with sparse priors.\" *The Annals of Statistics* 43.5 (2015): 1986-2018. \n\n[10] Y. Gong, N. He  and Z. Shen. \"Poincare inequality for local log-Polyak-Łojasiewicz measures: Non-asymptotic analysis in low-temperature Regime.\" arXiv:2501.00429 (2024). \n\n[11] A. Y. Chen  and K. Sridharan. \"Optimization, isoperimetric inequalities, and sampling via Lyapunov potentials.\" arXiv:2410.02979 (2024).\n\n[12] S. Chewi and A. J. Stromme. ``The ballistic limit of the log-Sobolev constant equals the Polyak-Łojasiewicz constant.\" arXiv:2411.11415 (2024)."}, {"review_id": "UVbtqOsvRR", "reviewer": "Reviewer_W8WC", "summary": "This paper presents a new theoretical framework for analyzing simulated tempering algorithms, particularly in the context of sampling from multimodal distributions. The authors focus on bounding the restricted spectral gap, which allows for analyzing mixing times without requiring global spectral gap assumptions—often hard to establish in high dimensions or multimodal settings. Their main contribution is a discrete-time Markov chain decomposition theorem that yields lower bounds on the restricted spectral gap of the simulated tempering chain. This framework is applied to a simulated tempering Metropolis–Hastings (STMH) sampler targeting Gaussian mixture models, showing that the algorithm mixes in time polynomial in the mode separation and logarithmic in the target accuracy.", "questions": "On Assumption 2 :\nWhile the theoretical condition in Equation (2) is essential to the decomposition, in practical settings (especially for general Metropolis–Hastings chains), verifying or constructing Mij  that satisfy the inequality seems challenging. Can the authors provide further guidance or heuristics on how to check or enforce this assumption in practice?", "limitations": "The conclusion discusses some limitations, in particular on the assumptions 2/3.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- Quality:  The technical quality of the paper is high. The decomposition theorem is rigorously developed and soundly argued. The authors make a meaningful extension to discrete-time chains, which is valuable for practical MCMC algorithms like Metropolis–Hastings. The proofs, though deferred to the appendix, are sketched well in the main text and the assumptions are clearly stated.\n\n-Clarity: overall, the paper is clearly written, especially for readers familiar with MCMC theory and spectral gap analysis. However, certain key steps (e.g., interpretations of Assumptions 2 and 3, or the intuition behind Equation (2)) could benefit from additional motivation or examples. The paper assumes a fairly expert audience.\n\n-Significance: the contribution is significant for the MCMC and sampling community, especially in contexts where standard spectral gap bounds are either loose or intractable. The approach improves upon prior work (e.g., Ge et al., 2018) by simplifying the projection chain and relaxing some assumptions. Polynomial dependence on d  (mode separation) is significantly better than many standard samplers (e.g., unadjusted Langevin or proximal methods) which suffer exponential dependence on d.\n\n-Originality: the paper offers a novel discrete-time decomposition for restricted spectral gap analysis. While inspired by prior continuous-time analyses, the authors substantially modify the approach, especially in how they define and analyze the projected chain. The use of restricted spectral gap (vs. full spectral gap) as the main analytical tool is also a meaningful shift.\n\n\nWeaknesses:\n- Limited assumptions: (eg Ass 2) The paper does not offer constructive guidance or examples on how to ensure this assumption holds in practice for general mixture models.\n-The dependence on dimension d is exponential in their result (hidden in constants due to the use of random walk Metropolis–Hastings).\n- limited experiments: the empirical study focuses only on a symmetric 2D Gaussian mixture, which is a toy example.\nThere are no comparisons with baseline methods (e.g., Langevin, annealed Langevin, or proximal samplers), and no error bars or statistical significance reported.", "was_revised": true, "final_justification": "kept my score", "rebuttal": "First of all, we sincerely appreciate your careful review of our manuscript and your thoughtful feedback.  Below please find our point-by-point responses. \n\n**Weakness 1.** \nWe agree that Assumption 2 can be difficult to verify in general and typically needs to be assessed on a case-by-case basis. However, since our analysis is based on the restricted spectral gap, it is sufficient to verify this assumption only within a subset of the state space—often a compact set—rather than globally. This makes the assumption more tractable in practice. Specifically, for other Metropolis-Hastings samplers such as MALA (Metropolis-adjusted Langevin algorithm), inequality (2) in Assumption 2 essentially reduces to bounding the acceptance and proposal probabilities. Since we are focusing on compact subsets of the state space, obtaining such bounds is usually feasible. Inequality (3) in Assumption 2 essentially assumes a bound on the restricted spectral gap of each component chain. Again, on compact spaces, there are standard techniques for obtaining such bounds, such as the path methods of [1].  Whether the resulting mixing time bound is sharp has to be checked on a case-by-case basis. \n\nRegarding the dependence on dimension $d$, we acknowledge that the constants in our complexity bound scale exponentially with $d$ when using the random walk Metropolis–Hastings (RWMH) kernel. This is a known limitation of RWMH in high-dimensional settings and has already been discussed in Remark 5. We will make it more explicit in the revised version.\n\n[1] Yuen, Wai Kong. \"Applications of geometric bounds to the convergence rate of Markov chains on Rn.\" *Stochastic Processes and their Applications* 87.1 (2000): 1-23. \n\n**Weakness 2.** Thank you for the feedback. The goal of our experiment was to illustrate the theoretical result, and we found that the empirical behavior aligned well with the theory. However, we agree that the example used is a toy setting, and we have not included comparison with baseline methods or error bars. In the revised version, we will follow your suggestion to improve the presentation of this toy 2D Gaussian mixture example and strengthen the empirical evaluation  by adding a more realistic example. \n\n**Question 1.**\nThis has been addressed in the response to weakness 1."}, {"review_id": "KCAsNzntxo", "reviewer": "Reviewer_Beiq", "summary": "The paper analyzes the spectral gap of simulated tempering under a model of multimodality. In contrast to many related work, one strength of section 2 of the manuscript is that it does not assume a specific algorithm for the per-chain base MCMC algorithm. The authors then specialize the general framework to a specific algorithm in section 3 (namely, random walk MH) to demonstrate the utility of their approach.", "questions": "My main question is the issue of the marginal/conditional described above.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "I appreciate the honesty of the authors in stating that \"It is important to note that this approximate STMH sampler cannot be implemented in practice, as it requires knowledge of the component distributions\". I am OK with that leap of faith. Just as statisticians find value in a data model that is wrong but useful, theory can benefit from this kind of model-based approach.\nOf course, it is always good to describe the limitation of the model, and while a good effort has been made already by the author, I will add that it would be good to mention that real world multimodal posterior have an exponential number of components, and that irregular posteriors are not necessarily difficult because of multimodality, concentration to a manifold being another example. \n\nI really enjoyed the modularity of the theory, with the general framework in section 2 being applicable to other types of samplers. This modularity reminds me the work of Biron-Lattes et al (JASA, 2024), but from a different perspective.  \n\nA bit more discussion on whether the analysis has methodological recommendations associated with it would be good, if something can be said. \n\nThe paper briefly mentions in Remark 5 that the new bound has an exponential dependence in the dimensionality. I feel this should be flagged in the introduction, as well as by adding a row in Table 1 to include the proposed bound.\n\nThe paper falls in the usual fallacy of using upper bound comparisons to make statements about comparing algorithms, for example \"while 254 STMH achieves a more favorable logarithmic dependence on ε\" - what is being compared there are upper bounds, so no statement should be made about \"STMH achieving a more favourable dependence\". \n\nThe introduction promises results on the approximation of the target distribution. However, the closest formally stated result in the main text consists in bounds in TV with respect to P, which is ST's stationary distribution. Now, in contrast to the typical scenario where the target distribution is a marginal of the augmented target (such as with PT or HMC), with ST the target appears as a conditional, not a marginal. Hence I was not able to see exactly what result delivers the abstract's promises. Theorem 5 seems a likely candidate but it is only informally stated and the reader is sent to \"Appendix C\" in which again I could not exactly locate a result on TV of conditionals of ST. \n\nThere description of the classical ST algorithm in the supplement makes the notation very confusing. Algorithm 1 is presented as taking as input a deterministic number of steps. Then, in Algorithm 2, the inner loop calls Algorithm 1 to obtain a fixed number of samples. However, I infer from the importance sampling estimator in the line below that these samples are only the random subset at level s. However an algorithm with that kind of random stopping time does not match with how Algo 1 was defined. So I recommend to fix in Algo 1 what is the stopping time, to make it random, and also make explicit how the output samples are collected (to emphasize that it is NOT the list of all samples produced in contrast to standard MCMC algorithms). This makes me a bit worried that there is a gap between the actual algorithm and the analysis, because I did not see analysis of the random stopping time involved to get a prescribed number of samples. (alternatively, if the algorithm meant s to be random, then the algorithm is just ill defined since there could have been zero visit making the procedure undefined). \n\nRelatedly, the manuscript is often unclear on whether the adaptive MCMC algorithm estimating the normalization constants is being analyzed, or the homogeneous MCMC ST from Def 2.", "was_revised": true, "final_justification": "I am satisfied with the reviewer's responses to my comments.", "rebuttal": "We sincerely appreciate your careful review of our work and your insightful and constructive feedback. Below please find our point-by-point responses. \n\n``A bit more discussion on whether the analysis has methodological recommendations associated with it would be good, if something can be said.`` \n\nWe thank the reviewer for the thoughtful question. First, the main methodological contribution is that our theory provides practical guidance on how to tune algorithm parameters, such as the temperature ladder, as described in Appendix C.4. The conditions we have on the temperature ladder are not artifacts of our proof techniques (though a proof is not provided): intuitively, we need (1) the two adjacent temperatures to be close enough so that temperature swaps are likely to be accepted, and (2) the highest temperature to be large enough so that the tempered target can be explored efficiently by an algorithm like random walk Metropolis-Hastings or MALA. The conditions we have on $\\beta_i$ make these intuitions precise. Second, our theory characterizes the dependence of the complexity of STMH on key parameters such as mode separation, component weights, and condition number. In practice, one can use it to approximately estimate how the runtime would change if the problem becomes more difficult. \n\n``The paper briefly mentions in Remark 5 that the new bound has an exponential dependence in the dimensionality. I feel this should be flagged in the introduction, as well as by adding a row in Table 1 to include the proposed bound.``\n\nWe thank the reviewer for the suggestion. We agree that the exponential dependence on dimension should be made more transparent, and we will highlight this point in the revised version. \n\n``The paper falls in the usual fallacy of using upper bound comparisons to make statements about comparing algorithms, for example while 254 STMH achieves a more favorable logarithmic dependence on $\\varepsilon - what is being compared there are upper bounds, so no statement should be made about STMH achieving a more favourable dependence.``\n\nWe agree with the reviewer that the original phrasing may be misleading. Our intention was simply to highlight that the bound we obtain for STMH represents a state-of-the-art theoretical result among existing known upper bounds. We will revise the wording to make this distinction clear in the revision. \n\n**Question 1.**\nWe thank the reviewer for raising this truly insightful question. We did consider this very subtle issue when developing our proof,  and the current version has already addressed this, as we now explain. We recognize that the writing needs to be improved at a few places to further clarify the related argument. \n\nFirst, to clarify, Algorithm 1 is always run for a fixed number of steps $N$ and returns the sample one collects at the last step (we will clarify this in the revision.) If the resulting sample does not come from the desired temperature level, then Algorithm 1 is simply re-run for another $N$ steps. We do not run Algorithm 1 for a random number of steps until the desired temperature is reached (so no random stopping time is involved). Next, in Lemma 4, we analyze the total variation distance between the conditional distributions given the temperature index, which can be applied to the output of Algorithm 1 conditioning on the temperature level. Finally, to properly estimate the overall complexity of the whole algorithm including estimation of normalizing constants, in Lemma 27 we analyze how many times we need to re-run Algorithm 1 with $N$ steps (for fixed $N$) in order to obtain a sample from the desired temperature level. Note that we essentially followed the simulated tempering algorithm construction given in [1] but this final step (i.e., Lemma 27) apparently was missing in the proof of [1]. We will make this reasoning more explicit in the revised version. \n\nUsing a random stopping time (e.g. the first hitting time after N steps of a given temperature level) could be potentially problematic, since due to the Markovian nature of the algorithm, the distribution of such a sample collected can be severely biased. Of course, we are aware that our construction of Algorithm 1 is not practical; it is designed to facilitate the proof by producing independent samples for estimating normalizing constants. \n\n[1] Ge, Rong, Holden Lee, and Andrej Risteski. ``Simulated tempering Langevin Monte Carlo ii: An improved proof using soft Markov chain decomposition.\" arXiv preprint arXiv:1812.00793 (2018)."}, {"review_id": "Wam8lhi5yt", "reviewer": "Reviewer_MSfx", "summary": "There has been a lot of work in recent years on establishing the complexity of Langevin, MALA or related MCMC algorithms when sampling from a log-concave density. However, such approaches fail short when the target distribution is severely multi-modal. A related line of work is to study the complexity of tempering-based algorithms (such as parallel tempering, simulated tempering, or tempering SMC) under the weaker assumption that the underlying Markov kernels mixed well at least *locally*, in various subsets forming a partition of the sampling space. This paper continues this line of work, and used the concept of *restricted spectral gaps* to derive new, tighter complexity bounds for simulated tempering. \n\nThe first part derives new result under very general assumptions on the target distribution and the local kernels, whereas the second part specialises these results to the case where the target distribution is a Gaussian mixture, and the local kernels are random walk Metropolis kernels.", "questions": "* It would be nice if the authors could discuss a bit more the relevance of their work to multi-modal target distributions arising in ML, e.g., posterior distributions for neural networks.", "limitations": "* 42: there are more recent/relevant references for SMC samplers than Liu & Chen, e.g. Jasra et al. (2006, JRSSSB, read paper) the book of Chopin and Papaspiliopoulos (2020), or Syed et al (https://arxiv.org/abs/2408.12057).", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths\n=======\n\n* The paper is nicely written, I enjoyed reading it. \n\n* From a cursory reading, it looks like a significant improvement over previous results of the same type. In particular, the paper is quite close in spirit to Ge et al. (2018), but Ge et al consider the continuous-time settings (which is typically *easier* to deal with, because no Metropolis correction is required), and this paper uses novel tricks such as the the projected Markov chain (see Remark 3). Disclaimer: I have not read Ge et al. (2018). \n\nWeaknesses\n==========\n\n* A journal paper might be a better format for presenting this kind of results.\n\n* The direct relevance to ML is a bit debatable, especially the part on sampling from Gaussian mixture distributions (since it is a toy problem).", "was_revised": true, "final_justification": "Solid piece of work, I was happy with the initial version (rating 5), and I see no reason to change it.", "rebuttal": "We sincerely appreciate your careful review of our work and your positive feedback.  Below please find our point-by-point responses. \n\n**Weakness 1.** \nWe appreciate the perspective that the depth and technical nature of our results might be well-suited to a journal format. However, we expect that our contributions will be of strong interest to some conference audience as well, since quite a few similar works [1, 2] have been presented at conferences like NeurIPS and ICLR. We hope our paper will likewise contribute meaningfully to ongoing discussions in this area. \n\n**Weakness 2.**  We thank the reviewer for the thoughtful question. Theorem 5 establishes the convergence guarantees for   STMH  when sampling from a mixture of Gaussians with shared covariance matrix. This result can be naturally extended to target distributions that are sufficiently close to such Gaussian mixtures, as shown in [1]. In such cases, the time complexity would additionally depend on closeness between the actual distribution and the Gaussian mixture approximation. We also anticipate that similar techniques can be adapted to handle mixtures of log-concave distributions that are translates to each other, or more broadly, distributions that are well-approximated by such mixtures. \n\nAdditionally, there are realistic applied settings where our assumptions may approximately hold, making the proposed framework potentially applicable. For instance,  [3] showed that the posterior distribution for Bayesian variable selection (which is one of the most common model selection problems in statistics) can be approximated by a mixture of Gaussians under certain conditions.  \n\nAnother relevant application arises in the context of (Bayesian) deep neural networks.  Consider the case when the target is $e^{-f}$. In the context of DNN, $f$ is the loss composed with a neural network function. In this setting, the complexity of sampling will depend on the structure of $f$. If the widths of the neural networks tend to infinity, several works have shown that $f$ satisfied PL-type condition and hence by recent works like [4, 5, 6]  $e^{-f}$ satisfies Poincare or Log-Sobolev type isoperimetric inequalities. Therefore, algorithms like Langevin Monte Carlo, proximal samplers or MALA could be used to sample from the posterior.  However, in the practical regime where the width is finite, the corresponding $f$ does not satisfy any isoperimetric inequality and so $e^{-f}$ is highly multimodal, and the proposed algorithm is likely to be useful. \n\n**Question 1.**\nThis has been addressed in the response to Weakness 2.\n\n**Limitation.**\nWe thank the reviewer for pointing out the more relevant references related to sequential Monte Carlo methods. We will incorporate them into the revised version of the manuscript.\n\n[1] H. Lee, A. Risteski, and R. Ge. \"Beyond log-concavity: Provable guarantees for sampling multi-modal distributions using simulated tempering Langevin Monte Carlo.\" *Advances in neural information processing systems* 31 (2018).\n\n[2] O. Chehab,  A. Korba, A. J. Stromme, and A. Vacher. \"Provable convergence and limitations of geometric tempering for Langevin dynamics.\" In *The Thirteenth International Conference on Learning Representations* (2025).\n\n[3] I. Castillo, J. Schmidt-Hieber  and A. Van der Vaart. \"Bayesian linear regression with sparse priors.\" *The Annals of Statistics* 43.5 (2015): 1986-2018. \n\n[4] Y. Gong, N. He  and Z. Shen. \"Poincare inequality for local log-Polyak-Łojasiewicz measures: Non-asymptotic analysis in low-temperature Regime.\" *arXiv preprint* arXiv:2501.00429 (2024). \n\n[5] A. Y. Chen  and K. Sridharan. \"Optimization, isoperimetric inequalities, and sampling via Lyapunov potentials.\" *arXiv preprint* arXiv:2410.02979 (2024). \n\n[6] S. Chewi and A. J. Stromme. ``The ballistic limit of the log-Sobolev constant equals the Polyak-Łojasiewicz constant.\" *arXiv preprint* arXiv:2411.11415 (2024)."}]

Author rebuttal:

Meta-review: This paper tackles the problem of sampling from mixture distributions. The authors consider simulated tempering with a local MCMC sampler and develop a lower bound on the restricted spectral gap of the resulting algorithm which allows analyzing mixing times without restrictive global assumptions. These results were obtained using an improved theoretical framework for analyzing simulated tempering algorithms. The proposed method is applicable to a broader range of problems than existing approaches – i.e. can be used to develop efficient algorithms for them – and was validated on mixtures of Gaussians. 

The reviewers identified a number of strengths:
* The problem is important and hard and the approach to solve it is novel – substantially modifying existing techniques.
* The technical quality of the paper is high – the decomposition theorem is rigorously developed and the argument sound.
* The results are significant and the authors are honest about the limitations of their work.

The weaknesses of the paper were minor – e.g. improve clarity and presentation of both the method and results, provide constructive guidance on how to actually use the method for real problems, and clarify exponential dependence on dimension hidden in a constant. All of these concerns were addressed through the author discussion and all reviewers feel that the paper is a clear accept.
Decision: Accept (poster)