Fast Conditional Mixing of MCMC Algorithms for Non-log-concave Distributions
Authors: Xiang Cheng
Bohan Wang
Jingzhao Zhang
Yusong Zhu
Venue: NeurIPS 2023 poster (2023)
Keywords: Sampling
MCMC
Conditional Mixing
Non-log-concave Distributions

Abstract: MCMC algorithms offer empirically efficient tools for sampling from a target distribution $\pi(x) \propto \exp(-V(x))$. However, on the theory side, MCMC algorithms suffer from slow mixing rate when $\pi(x)$ is non-log-concave. Our work examines this gap and shows that when Poincar\'e-style inequality holds on a subset $\mathcal{X}$ of the state space, the conditional distribution of MCMC iterates over $\mathcal{X}$ mixes fast to the true conditional distribution. This fast mixing guarantee can hold in cases when global mixing is provably slow. We formalize the statement and quantify the conditional mixing rate. We further show that conditional mixing can have interesting implications for sampling from mixtures of Gaussians, parameter estimation for Gaussian mixture models, and Gibbs-sampling with well-connected local minima.

Fast Conditional Mixing of MCMC Algorithms for Non-log-concave Distributions
Xiang Cheng* MIT x.cheng berkeley.edu
Bohan Wang" USTC bhwangfy @ gmail.com
Jingzhao Zhang*
Yusong Zhu"
III, Tsinghua: Shanghai Qizhi Institute
Tsinghua University zhuys19 @ mails tsinguua.ddu.cc
jingzhaoz @ tninghua
Abstract
MCMC algorithms offer empirically efficient tools for sampling from target distribution (2) ix exp(-V(x)) However, on the theory side, MCMC algorithms suffer from slow mixing rate when (④x) is non-log-concave. Our work examines this gap and shows that when Poincaré-style inequality holds on subset X of the state space, the conditional distribution of MCMC iterates over X' mixes fast to the true conditional distribution. This fast mixing guarantee can hold in cases when global mixing provably slow. We formalize the statement and quantify the conditional mixing rate. We further show that conditional mixing can have interesting implications for sampling from mixtures of Gaussians, parameter estimation for Gaussian mixture models and Gibbs-sampling with well-connected local minima.
Introduction
Sampling from given target distribution of the form (xx) & -V(x) plays central role in many machine learning problems, such as Bayesian inference, optimization, and generative modeling [9, 14, 15]. The Langevin MCMC algorithm in particular has received lot of recent attention; makes use of the first-order gradient information VV(r), and can be viewed as the sampling analog of gradient descent.
Langevin MCMC has been shown to converge quickly when T(x) is log-concave [6. 10]. More recently, similar guarantees have been established for p(x) satisfying weaker conditions such as log-Sobolev inequality (LSI) [23], for instance, (xx) -v(x)) can have good LSI constant when V(x) is a small perturbation of convex function. However, few guarantees exist for general non- log-concave distributions. One simple example when p(x) is well-separated mixture of two Gaussian distributions; in this case, one verifies that Langevin MCMC mixes at rate proportional to the inverse of the exponential of the separation distance.
Many important modern machine-learning problems are highly non-convex, one prominent class being functions arising from neural networks. Though finding the global minimum of a non-convex function can be difficult, gradient descent can often be shown to converge rather quickly to local optimum [3]. This raises the important question:
What is the sampling analog of a local minimum? And how can we sample efficiently from such minimum?
Alphabetical author order
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

In [3], authors provide a partial answer to this question by adopting the view of Langevin Diffusion as the gradient flow of KL divergence probability space. Under this perspective, the gradient of KL divergence is given by the Fisher Information (FI). Authors of [3] show that LMC achieves error in Fl in O(1/c²) steps.
However, one crucial question remains unanswered: how does the local optimality of FI help us sample from non-convex distributions? Intuitively, small FI is useful for characterizing local convergence when ı is multi-modal. Authors of [3] suggested this connection, but it remains unclear how local mixing defined and how small FI can quantitatively lead to good local mixing. Thus motivated, one of the goals of this paper is to provide useful interpretation of the FI bound.
To this end, propose rigorous quantitative measure of "local mixing". We also provide more general notion of "stationary point" for the sampling problem. Under these definitions, we show that LMC can achieve error in our proposed "measure of local mixing", in polynomial time. Finally, consider discrete-time analog of the aforementioned ideas, and prove local convergence for random walk on a hypercube. Below is detailed description of our theoretical contributions.
1.1 Main Contributions
1. We define notion of conditional convergence: Let X' C Ω denote a subset of the state space. We study the convergence of TH. X to T |XY where Tr denotes distributions of LMC iterates and denotes the target distribution. This definition of convergence is much weaker than the standard global convergence, but in exchange, LMC can achieve fast conditional convergence in settings where global convergence is known to be exponentially slow.
2. We define local Logarithmii Sobolev Incquality and show how to combine it with existing results on the convergence of Fisher information to derive the conditional convergence of LMC.
3. When local Logarithmic Sobolev Inequality does not hold, define local Poincaré Inequal- ity and Poincaré Fisher information (which is an analogy of Fisher information). We show the convergence of Poincaré Fisher information assuming strong dissipativity and show the conditional convergence of LMC when local Poincaré Inequality is present.
4. To showcase the applications of our results, we respectively study sampling from Gaussian mixture model with the same covariance and sampling from the power posterior distribution of symmetric two-component Gaussian mixtures. The global isometric constants of these examples are exponential in dimension and may have slow global convergence. We show that the local isoperimetric constants of these examples are polynomial in dimension, and prove fast conditional convergence for these examples.
5. In Theorem I, we consider an application of our result to Gibbs sampling on discrete state space. We show that fast conditional mixing happens when the spectral gap is not small. We further show in Theorem 2 that a subset has large spectral gap if it contains only one local minimum and is well connected.
2
Related Work
When the target distribution is strongly log-concave, the entropy Ent, [+] is known be strongly convex with respect to μ., and thus Langevin Dynamics converges exponentially fast [2). Such a result is later extended to LMC [8, 4, 9, 7, 21]. Several works further loosen the assumption by using isoperimetric inequalities such as Logarithmic Sobolev Inequality and Poincaré Inequality instead of strong log-concavity [24, 25, 11]. However, there are few existing works on general non-log-concave sampling. Recently, Balasubramanian [3] defines convergence in relative Fisher information a kind of "weak convergence" for sampling and proves polynomial guarantee in general non-log-concave case only assuming global Lipschitz condition. However, this paper doesn't 't give any rigorous statistical interpretation of this weak convergence; Majka et al. [18] and Erdogdu et al. [11] study the cases when the target distribution is con-log-concane but has some good tail growth or curvature; Ma et al. [17] analyze the situation when the target distribution is non-log-concave inside the region but log-concave outside. Although these works give strict proofs of polynomial time guarantee in their setting, their results only hold for a small branch of non-log-concave distributions. It is still hardly possible to obtain polynomial guarantee in general

---

non-log-coneave concave cases. Multimodality, as special case of wow.-looatiittt....mmmmmo.mm..e. has attracted lots of attention due to prevalence applied science. Many modified versions of MCMC were proposed to try tackle the sampling of these distributions, such as Darting MC [1], Wormhole HMC [16], and etc. However, these algorithms require explicit knowledge of the location of the modes.
Conditional Mixing for MCMC
In this section, we provide formal definition of "conditional mixing". Specifically, let μe denote the distribution of Markov chain [Zr]; , at time We assume that the Markov chain dynamics is reversible with a unique stationary distribution л. Existing analyses mostly focus on understanding the rate of convergence measured by d(jte, X) where is some probability distance.
However, unless the stationary distribution satisfies certain restrictive properties (c.g.. log- concavity), the rate of convergence can be exponentially slow in the problem dimension the distribution moments even for simple distributions such as the mixture of Gaussians. For this reason, consider weaker notion of convergence below.
Definition (Conditional mixing). Given distribution pr supported on the state space Q. We say H4 converges conditioned on set X C with respect to the divergence if
d(pelx, 21 S e,
where we have the conditional distribution
[r( (x Px(
For now we can think the distance the total variation distance. Later will discuss stronger divergence such as KL-divergence or Chi-squared divergence.
The focus of work is identifying several sufficient conditions for fast convergence, and quantitatively bounding the convergence rate under these conditions. We focus on two MCMC algorithms: the Langevin Monte Carlo in continuous space, and the Gibbs sampling algorithm in discrete space. We further discuss the implications conditional convergence for the two algorithms.
Conditional Mixing for Langevin Monte Carlo
In this section, study the conditional mixing of the Langevin Monte Carlo (LMC) algorithm. This section is organized as follows: in Subsection 4.1, we first introduce the Langevin Monte Carlo algorithm, Langevin Dynamics, functional inequalities, and the Fisher information; in Subsection 4.2, we provide our main results characterizing the conditional convergence of LMC; finally, in Subsection 4.3, we showcase two applications of our main results.
4.1 Preliminaries
Langevin Monte Carlo. We are interested the convergence Langevin Monte Carlo (LMC), which is standard algorithm employed to sample from a target probability density x <- Rd R. where V called the potential function. The pseudocode LMC given in Algorithm 1.
Algorithm Langevin Monte Carlo
Input: Initial parameter z, potential function V, step size h, number of itcration
1: Initialization 20 +
2: For /
T:
3: Generate Gaussian random vector & ~ IOO,Ia)
4: Update (((+1)A < (ZV()))) + V2hg.
5: EndFor
LMC can be viewed as a time-discretization of Langevin Dynamics (LD), described by the following stochastic differential equation:
=Z,=-vV(ZZ) dt V2dB,
(I)
3

---

We can interpolate LMC following the similar manner of LD as
dz, (Zkh) dt V2dB, t E kh, kh +h k N.
(2)
1oe in One can easily observe that J J= in Eq. (2) has the same joint distribution as { Algorithm 1, and thus Eq. (2) is a continuous-time interpolation of Algorithm 1.
Poincaré Inequality & Logarithmic Sobolev Inequalities. The convergence of LMC does not necessarily hold for all potential functions, and quantitative bounds require specific conditions over the potential function V. Poincare Inequality (PI) and Logarithmic Sobolev Inequality (LSI) are two commonly used conditions in the analysis of LMC convergence. We present these below:
Definition (Poincaré Inequality). A probability measure π on R satisfies the Poincaré inequality with constant p > 0 (abbreviated as PI(p)). for all functions f F. R.
[V dr(x)) 2 [Var=
(PI)
Definition 3 (Logarithmic Sobolev Inequality). Given function f I2d - R and a probability
measure on R.d. define (f) & loo dv(x) (x)( (log J [x(())) We say that
distribution a on R satisfies the Logarithmic Sobolev Inequality (abbreviated as ISS(())) with some constant a, if for all functions f R.d + Rt,
[+(22] dr(x) 2 a (f)x
(LSI)
Both PI and LSI imply the convergence of LMC when the step size h is small. Specifically, denote Teh as the distribution of žth LMC (Algorithm 1) and म. as the distribution of Z, in Langevin Dynamics (Eq,(1)). We further denote ग. as the distribution of Z, interpolating LMC. The seft-hand-sse of (PI) with f f is then the derivative (w.r.t. time) of the entropy of f. i... Ent, Ri and thus we directly establish the exponential convergence of Var, [i The convergence of LMC can then be induced by bounding the discretization error between LMC and Langevin Dynamics. The methodology is similar when we have LSI.
Fisher information. is well-known that if V either strongly convex or convex with bounded support, then it obeys both PI and LSI, and the convergence of LMC follows immediately according to the arguments above. However, real-world sampling problems usually have non-convex potential functions, and for these problems we may no longer have either PI or LSI. If we revisit the above methodology establish the convergence of LMC under LSI, we find that we still have
d Entz π
V In
(x)) (x), Ent
Entz
L.'
/
me v In
(x))
d dt.
de
and thus lim minkefo.ry f (x) dx(x) = O. Following this methodology, [3] uses
the considers notion of convergence which is defined using Fisher Information [T) A V In//|// p//||/ du, which they use to analyze LMC convergence. We present the result of [3] for completeness:
Proposition 1 (Theorem 2, [3]). Assume VV is I-llischitzz. Then, for any step size h E (0, 3.))
1
{ Th
2 Ent 33o
Th. FI, (T. (t.llT)
+ +8I dh.
Th
4.2 Rates of convergence
4.2.1
Conditional mixing under local Logarithmic Sobolev Inequality
We first show that if the target distribution π obeys a local Logarithmic Sobolev Inequality (defined below), then convergence of Fisher information implies conditional convergence.
Definition& 4 (Local Logarithmic Sobolev Inequality). We say that distribution on Red satisfies the local Logarithmic Sobolev Inequality over subset Rdd with some constant a (abbreviated as LSIs(a)), if T1S satisfies LSI(a).

---

Definition 4 characterizes the local property of one distribution. It is considerably weaker than global LSI (i.e., Definition 3) when is convex, and recovers LSI when S R The intuition that when the distribution is multi-modal, it is quite possible that LSI does not hold (or hold but with an exponentially small constant). contrast, we can reasonably expect local L.II hold within each mode. In Subsection 4.3, we will show that Gaussian mixture model with the same covariance satisfies Local Logarithmic Sobolev Inequality. We show in the following lemma that, whenever we have an estimation on the Fisher information between μ and x, we can turn it to an estimation of the entropy between yaS and T|S given LSIg(a).
Lemma 1. Let S X and assume that ι obeys LSIs(a). For any distribution p. such that FI(H|[+) S E, we have that either p(S) S V/a or Eut, s 44
We defer the proof of Lemma 1 to Appendix A. Intuitively, Lemma 1 states that if the distribution satisfies local LSI over the region S and has small global Fisher information with respect distribution 14, one can expect that either the probability mass of over S is minor, or is close to π both conditional over S. In other words, μ close conditional over S whenever μ has moderate mass over S. Note that Proposition 1 has already guaranteed global FI of LMC with little assumption, which together with Lemma leads to the following corollary:
Corollary 1. Assume VV is L-lipschitz and S C X' satisfies that π obeys LSIg(a). Define TTK Vd Eut T0
h de Th
Choosing step size h
L. VT
we have that either TT)(S) S O
VaVT
or
[rrilS ss x
Vd E +)) Vo VaNT VT
Entajs
SO
Corollary is one of our key results. Intuitively, it shows that LMC can achieve local mixing when only local LSI is assumed. As we discussed under Definition 4, we can reasonably expect that local LSI holds within each mode when the distribution is multi-modal, in which case Corollary can be further applied to show local mixing with polynomial rate. Note here the dependence of the local mixing rate is polynomial over the dimension d, meaning that considering local mixing helps to get rid of the exponential dependence over the dimension in the global mixing rate when studying multi-modal distributions.
4.2.2 Conditional Convergence under local Poincaré Inequality
We have established the conditional convergence of LMC under local Logarithmic Sobolev Inequality above. However, there cases where even local LSI fails to hold. To tackle these cases and inspired by Poincaré Incquality, we introduce a weaker notion than local LSI called local Poincaré Inequality: Definition 5 (Local Poincaré Inequality). A distribution æ on Rd satisfies the local Poincaré Inequality over a subset S C Rd with constant (abbreviated as Pls(p)), if T|S salisfies PI(p).
As Poincaré Inequality is weaker than Logarithmic Sobolev Inequality, one can easily see that local Poincaré Inequality is also weaker than local Logarithmic Sobolev Inequality. Based on local Poincaré Inequality, have the following Poincaré version of Lemma 1, which converts an estimation of Poincaré Fisher information to an estimation of chi-squared divergence of the conditional distributions.
Lemma 2. Define Poincaré Fisher information as PF[( & f/IV (p/ /12 du. Let S C. X and assume that ι obeys (ps For any distribution μ such that PFI T) I E, we have that either
Var) Mls
(3)
To derive the conditional convergence of LMC under local Poincaré inequality, we further need to bound Poincaré Fisher information of LMC. Such result, however, does exist in the literature our best knowledge. In analogy to the analysis in [3], we develop the following lemma to control the Fisher information of LD (recall that 7, is the distribution of Langevin Dynamics in time t).
Proposition 2. Denote ārn. Tih and n.
f a. de Th
Then, we have the following estimation of the PFI between
Var, ia
PFI (T) dt
2Th
5

---

or The proof can be directly derived by taking the derivative of [ with respect to t. We defer the formal proof to Appendix A.2. Combining Lemma 2, Proposition 2. and recent advances discrete error analysis of L.D [19], we obtain the following result showing conditional convergence under local Poincaré inequality.
Corollary 2. Assume VV and V2V is I-lipscchii, V satisfies strong dissipativity, i.e. (VV(z), a) 2 m m=|3=:| b, and S C X satisfies that als obeys Pl(()). Initialize Za NN0,, o²T) and select
Var- F2j3
L n. dt Th
Then either #Tr(S) O dd Var (4) O p
Recall that TTb
T p
Drv [Thh (S (|]] = 0 ad Var, [
p T112
Corollary 2 shows that conditional mixing can be established when local PI holds, which is a weaker assumption than local LSI. However, the assumption of Corollary is stronger than its LSI counterpart, and the mixing rate depends on Var, Ru] instead of Ent (x)) ) which can be considerably large. These drawbacks are mainly due to that the dynamics of chi-square distance are much harder than that of KL divergence, even when global PI holds [12].
Extension to Rényi divergence. In some prior works, e-g. [5, 23), Rényi divergence considered natural "measure" of convergence, due to the analytical simplicity of the resulting expressions. One may wonder if our methodology above can be extended establish a local mixing rate of Rényi divergence. Unfortunately, there are technical difficulties which for now we have not find a way to tackle or bypass, which list in Appendix A.3.
4.3 Applications
In this subsection, we apply Corollary 1 and Corollary 2 to two concrete examples to demonstrate their usage in obtaining local mixing rates. We start by analyzing the example of sampling from Gaussian Mixture Models with uniform covariance and then turn to the example of sampling from the power posterior distribution of symmetric two-component Gaussian mixtures.
4.3.1 Case Study: Sampling from Gaussian Mixture Model with the uniform covariance
Target distribution and potential function. We are interested in the gaussian mixture model formed by gaussians with the same variance but different means. Specifically, the target distribution is defined as π Σi= W:p; E (IR"), where w; > 0, >i - | W; = 1, pi N(u,, >) and Σ > o²I,. The potential function is then defined as V(x) = - log E w,,:(x)).
Partition of Space. We divide the space according to the sub-level set. Specifically, we define S, A {x (z) 2 P,(x), Vj # i}. One can easily verify that Uن_ Rd. Furthermore, S; is convex since by the definition of pt. we have
S = (x - p4) Mー - m1) S (x - m1))
";:TTTT T
As Σ is positive definite and symmetric, definite and symmetric. We then obtain
decompose Σ into UU, where U is also positive
U-LS = {a (x- U-) (x- --c-u-pp (x (
and thus U-1S, is one region of the Voronoi diagrams generated by [u~} which is convex. As St can be obtained by performing linear transformation to U- obtain that S, is also convex. Verification of local Logarithmic Sobolev Inequality. We prove the local Logarithmic Sobolev Inequality of n over each partition S, as follows.
Lemma 3. For all i E {1,..., n),, SS obeys LSI( o- mintett) We
max.e(() Wt
Lemma 3 is proved by first showing pa SS obeys LSI(O through Bakry-Emer criterion due the convexity of S; and p; is strongly convex, and then applying Holley-Stroode perturbation principle by viewing perturbation of pæ over S. The concrete proof is deferred to Appendix B.I.
Verification of Lipschitz gradient. By direct caleulation, we derive the following bound on the Lipschitz constant of VV.

---

Lemma 4. Vo R.. [ max;, llne will"
0-
As conclusion, we obtain the following guarantee of running LMC over this example.
Corollary 3. Let the stepsize of LMC be h
O (()))
Assume T > O a min,e(a] w
muxielel me
Then,
for every E [n]. either (S:) S E, or Eutz|s.
fru SS 7|S.
S E.
Corollary 3 indicates that running LMC over gaussian mixture distribution (with the same covariance) can ensure local mixing with cost polynomial over the dimension and independent of the distance between the means. By contrast, is folk-tale that even the global mixing of gaussian mixture with 2 components has global mixing rate exponential over the distance, which suggests local mixing analysis provide a more concrete analysis of what is going on over each component.
4.3.2 Sampling from the power posterior distribution of symmetric Gaussian mixtures
Target distribution and potential function. The symmetric Gaussian mixture model is given as
1 2 20( to, Ia) +
foo (a)
2 20(2; - Go Ma)-
Here sp(x; fo Ia) denotes the multivariate Gaussian distribution with location parameter Ou R and covariance matrix La. Without loss of generality, we assume &n E span(e1 }. ie., all coordinates d except the first is zero, and Og c1 The power posterior distribution, the target distribution, IT= (fo (fo()))))) (/"A())
is defined Tn,8/n (0 (= I (X.)) (/.)) "(u)ddi We set À for simplicity. When no ambiguity is possible, we abbreviate 9/.9/n {X,) )))) as (0). The potential function is then given as V(0) :- _/4 1 log
+ + (0 + X.)) + log X(0).
Partition of Space. With an accuracy budget E, we define R1 = [0, A) B(O, M), R2 = [| ((0, M), and R3 = (R1 U R2)", where A and M are e-dependent hyperparameter specified latter.
Verification of local Poincaré Inequality over R1 and R2. We have the following characterization for the local Poincaré Inequality over R₁ and R2:
||oo| + 1 and 2 (((A+ M) then with probability at least 1 8 with respect to the sampling of {x.) we have that a obeys Pla, (0(1/(AMM)) and PlR, (
Lemma 5. A, M 2
The lemma is derived by first considering the distribution corresponding to the potential function V-EV and proving local Poincaré Inequality of न R2 (or म R2), then bounding the difference between V and V through concentration inequality, and finally completing the proof by applying Holley-Stroock perturbation principle to pass local Poincaré Inequality from R to π T/ A concrete proof is deferred Appendix B.2.
Verification of strong dissipativity. Similar to local Logarithmic Sobolev Inequality, we can show strong dissipativity of V holds in high probability.
Lemma 6. n > (((d+ [] log(1/8)) then with probability least 1- 8 over the sampling of (x.)% (()]I (d).
| (VV 0) 2(110113) (110,12 + 1). and [[) <
Bounding the probability of R3. Using strong dissipativity, we can bound ग. (Ra) as follows.
Lemma 7. If > @(dd + |00 22) log(1/0)), then with probability at least 1 - over the sampling
162(19.) (1)(1 -1)--d-ma)
of (x))) we have ग.. (Rs)= < 32c
All in all, we obtain the following characterization of running LMC over this example.
Corollary 4. Initialize 20 ~ N(0,0=11 for o² < T+I and select h = è ++) Set A M (ld++lo(1/e)) IfT= = ((d and @(d+ |00ll)) log(1 (o)(1/))). then with probability at least 1- over the sampling of (x,) either 7Tn R2)) S 8 or Drv [TTal [ S & i (1, and Fry (Ra) <
7F

---

As a comparison, such a problem was also studied by [20], where they constructed a specific sampling algorithm with prior knowledge this problem to achieve global convergence. In contrast, we analyze LMC, which does not require any prior knowledge of the problem, and derive the conditional convergence of LMC.
Conditional Mixing for Gibbs Sampling on Finite States
In previous sections, we showed that conditional mixing can happen for LMC on a continuous state space. We now show that similar results hold for MCMC algorithms on a finite state space. For simplicity, we consider an energy function f {0, 1) + f0, 1.2.,..... M) =: [M] defined on the vertices hypercube. Denote its corresponding Gibbs measure क ((x) x e -((r)
We consider vertices of the hypercube as a d-regular graph where for any 2, y E {0, 1]", an edge exists if and only if they differ by one coordinate, dutmmiig (z. y) 1. Then lazy Gibbs sampler has the following transition matrix on this finite graph:
7(V)
+())+
p(a,y) y) = 1 2d Ex'st pla (()))
x(x)
== I,
0.
otherwise.
Note that the process is lazy because, p(r, x) 2 1/2 for any x. This is assumed for simplicity of analysis to avoid almost periodic behaviors. This assumption does not make the analysis less general, as a lazy self loop with probability 1/2 only changes the mixing time by a multiplicative absolute constant (see Corollary 9.5 [22]).
To prove conditional convergence, we need an analogue of conditional Poincaré Inequality. The story for the discrete state space can be more convoluted as the transition matrix, in addition to the stationary distribution, plays a role here. Many of the analyses below are inspired by [13].
First, given a finite number of subsets {KiJigm we define the conditional probability x; = T|A supported on X, and hence for w/ = π (X));
(σx) Σ (x) Ex)
We also need to design conditioned transition kernel so that Va, y E Xi,
px(x, v) -p(x,))) - (z= P(x,
where X denotes the complement of X, and hence the conditioned kernel simply rejects all outgoing transitions. Then we can easily tell that p; is reversible with unique stationary distribution n. We are now ready to give an analogue Corollary 1.
Theorem 1. Given a sequence of subsets {Xi (ig) for every i, Pa defined in (3) as a distribution on X₂ has spectral gap at least a, then we have that either for some t. the distribution pe has small probability on X, (xG) S (-1)/--1/4 or the conditional mixing happens with respect to Chi-squared divergence,
Σ
Vara
H x|X
Var
Hg π
T
The proof builds upon the convergence of the Dirichlet form and can be found in Appendix C. The above theorem suggests that if the spectral gap of the Gibbs sampling algorithm is lower bounded on local subset, then after polynomial number of iterations, we get either 14: has very small probability on this set, conditioned on the set, the distribution is close the stationary distribution.
One thing less clear, in finite-state Gibbs sampling as compared to the LMC, is when would the spectral gap for Gibbs distribution be large. For the Langevin Monte Carlo algorithm, classical results show that the spectral gap cannot too small if the stationary distribution is locally near log-concave. Below we provide an analogue of this observation for discrete state space.

---

5.1 Spectral Gap for Gibbs Sampling
We first define a graph g = (V, E), where V = {0.1) 13", and (s,y) E E if and only if ditamiingg (1r, each iteration can only move to a neighbor or stay at the current vertex. Then we introduce the counterpart of quasi-convexity on a function defined on vertices of graphs.
Then define quasi-concavity in this case. Note that Gibbs sampling in
Definition 6. Let 9 = (V',E") be a subgraph, V' VVV = (z.y) E E/ V' y E V.. We say a function f : V [Md] is quasi-convex with radius D subgraph G = (V' E"), if there exists a local minimum u* E V' such that for any e E V', any shortest path v + V1 7 7 e² from v is of length most D. and f is non non-increasing along the path.
Before providing a guarantee for the spectral gap, we give two examples of quasi-convexity.
Example 5.1. I RR + IR is a quasi-convex fuasi-converuunccioon function defined on positive reals. Then for a given x' E V' " V any function f(x) = g(a- d(x, x²) + b) is a quasi quasi-convex function on the graph where a, are reals and d(z,) y) the shortest path length from I to y.
Example 5.2. If on a subser V V. fz) = c x for some c E R x E 10, (i.e. f is a linear function), then f is quasi-convex on the graph.
The next theorem states that for such function, the spectral gap is polynomial in problem dimension d and the diameter of the region D.
Theorem 2. If a function I is quasi-convex with radius D a subset X, S {0, 10,1)4 then the conditional transition of Gibbs sampling defined in (3) has a spectral gap lower bounded by Tza-
The proof studies the conductance of the Markov chain and can be found in Appendix D. The above theorem suggests that although Gibbs sampling can mix very slowly, any subset with a well connected local minimum, the conditional mixing to the stationary distribution can be fast. This concludes our analysis and we move on to verify our statements with experiments in the next section.
6 Experiments
6.1 Observations on Gaussian Mixture
In this section, conduct experiments to verify the theoretical results and compare global mixing versus conditional mixing for Gaussian mixture models. We take three Gaussian mixtures: 2I = ( 1) 0.1N, (10, 1), 1/2
(-1, - 0.15N, (-2.5, 1) 1) + 0.2N, (5, 1), and L3 = 0.4N2((-5, -5), T2) + 0.4N2 (5, 5), 12) +
(0, 1) + 0.2N, (.1N2((-5) 12) + ((, -5), I2) as our target distributions. We use Algorithm sampling algorithm, and set step size h = 10-2 The initial distributions are both uniform in large enough range. We plot the sampling distribution after T = 500, 5000, 500 rounds respectively in Figure la, lb, and Ic, and plot the conditional and global KL divergence in Figure Id, Ic. and If.
our
We make the following observations: (1) The global KL divergences of the sampling distributions of 1/2 and V3 decrease fast at first. Then they maintain at a constant level and never converge to O. It is reasonable since v1, V/3 have very bad LSI constants (exponential in the distance between means). Thus, by classic Langevin Danymics analysis results[23], global KI, divergence would have exponentially slow convergence rate. (2) Both the global and conditional divergences of the sampling distribution of v2 converge very fast. This is because dense Gaussian mixtures like 1/ have good LSI constant. The KL values are noisy due to the limited calculation precision of KL divergence. (3) The conditional divergence of the sampling distribution of 1/2 converges faster than the global divergence because the LSI constant bound of 1/2 is much worse than the conclusion in Corollary 1, which means conditional convergence is faster than global convergence. (4) The conditional KL divergences of the sampling distributions of 112 and 2/3 converge the limit of calculation precision), which could be seen as a verification of our theoretical result. (5) The sampling distributions of i) and V3 after T iterations contain all of the Gaussian components in target distributions, the only difference between them is weight. Since learning the right weight and component will directly lead to global KI. convergence, this observation could be seen as an example of the gap between global convergence and conditional convergence.
very fast (the flat part due to

---

samping tarqet per
sampling target par
0.10
0.08
0.2
0.06
0.1
0.04
0.0
-20
100
0.00
-10
(a) sample distribution(1))
(b) sample distribution(22))
global (c) sample distribution(
global
ondd
conditioned
conditioned
I.. (oooirrien
conditionne
3.13
condilc y
conditionned
-2
300
Noration
Itoration
(d) KL divergence(v1)
(e) KL divergence(/22)
(f) KL divergence(vs)
Figure we plot the sampling distributions after T iterations and the KL. divergences w.r.t
6.2 Observations on LMC with restarts
In the LMC analysis, We study the evolution of a distribution that usually is an absolutely continuous distribution. However, in practice, more common implementation is below: one first randomly generates an initial point zo, runs the sampling algorithm for T iterations, and then collects samples along single trajectory. gap between theory and practice here is that we always assume continuity and smoothness conditions on the initial distribution in theory, while in practice, we only generate limited number of initial points (sometimes only one point) run the sampling algorithm.
For log-concave sampling, this gap is usually negligible since the ergodicity of Langevin Dynamics guarantees that could always capture the features of the target distribution. Thus, it's reasonable that there are plenty of works about the discretization error on the time scale, while we hardly pay attention the approximation error of initial distribution. When it comes non-log-concave sampling, this gap may become crucial. We conduct several experiments in Appendix to verify this conjecture and show that LMC with restarts could empirically help eliminate the gap and improve the convergence speed.
7 Conclusions
Our work examines sampling problems where the global mixing of an MCMC algorithm is slow. We show that in such cases, fast conditional mixing can be achieved subsets where the target distribu- tion has benign local structures. We make the above statements rigorous and provide polynomial- guarantees for conditional mixing. We give several examples, such the mixture of Gaussian and the power posterior to show that the benign local structure often exists despite the global mixing rate is exponentially slow.
Much remains be done. Theoretically, whether faster convergence rates can achieved or lower bound exists remain unknown. Instantiating our analyses to more MCMC algorithms may also lead to new observations. More importantly, the implication of being able to sample efficiently from local distributions requires more careful analysis. This may lead to a new theoretical guarantee for problems with symmetry (such as permutation symmetry, sign symmetry, rotation invariance, etc) where all local minima are equally good and sampling from any mode suffices.
10

---

Acknowledgments and Disclosure of Funding
Jingzhao Zhang acknowledges support from Tsinghua University Initiative Scientific Research Program.
References
[1] S. Ahn, Y. Chen, and M. Welling. Distributed and adaptive darting monte carlo through regenerations. In International Conference on Artificial Intelligence and Statistics, 2013.
[2] D. Bakry and M. Emery. Diffussons hypercontractives. In Séminaire de Probabilités XIX 1983/84: Proceedings, pages 177-206. Springer, 2006.
[3] K. Balasubramanian, S. Chewi, M. A. Erdogdu, A. Salim, and S. Zhang, Towards theory of non-log-concave sampling: first-order stationarity guarantees for langevin monte carlo. In Conference on Learning Theory, pages 2896-2923, PMLR, 2022.
[4] X. Cheng and P. Bartlett. Convergence of langevin meme in kl-divergence. In Algorithmic Learning Theory, pages 186-211. PMLR, 2018.
[5] S. Chewi, M. A. Erdogdu, M. B. Li, R. Shen, and M. Zhang. Analysis of langevin monte carlo from poincaré log-sobolev, 2021.
[6] A. Dalalyan. Theoretical guarantees for approximate sampling from smooth and log-concave densities. Journal of the Royal Statistical Society. Series B (Statistical Methodology), pages 651-676, 2017.
[7] A. S. Dalalyan and A. Karagulyan. User-friendly guarantees for the langevin monte carlo with inaccurate gradient. Stochastic Processes and their Applications, 129((2):527-5511, 2019.
[8] A. Dalalyan and A. B. Tsybakov. Sparse regression learning by aggregation and langevin monte-carlo. Journal of Computer and System Sciences, 78(5):1423-1445 2012.
2012.
[9] A. Durmus, S. Majewski, and B. Miasojedow. Analysis langevin monte carlo via convex optimization. The Journal of Machine Learning Research, 20(1))2666-2711 2019.
[10] A. Durmus and E. Moulines. Nonasymptotic convergence analysis for the unadjusted langevin algorithm. 2017.
[11] M. A. Erdogdu and R. Hosseinzadeh. On the convergence of langevin monte carlo: The interplay between tail growth and smoothness, 2020.
[12] M. A. Erdogdu, R. Hosseinzadeh, and S. Zhang. Convergence of langevin monte carlo in chi-squared and rényi divergence. In International Conference Artificial Intelligence and Statistics, pages 8151-8175. PMLR, 2022.
[13] Y. Guan and S. M. Krone. Small-world meme and convergence to multi-modal distributions: From slow mixing to fast mixing. 2007.
[14] A. T. Kalai and S. Vempala. Simulated annealing for convex optimization. Mahematics of Operations Research, 31 31(2):553-266, 2006.
[15] D. Kingma, T. Salimans, B. Poole, and Ho. Variational diffusson models. Advances in neural information processing systems, 34:21696-21707, 2021.
[16] S. Lan, J. Streets, and B. Shahbaba. Wormhole hamiltonian monte carlo, 2014.
[17] Y-A. Ma, Y. Chen, C. Jin, N. Flammarion, and M. I. Jordan. Sampling can be faster than optimization. Proceedings of the National Academy of Sciences, 116(42):20881-20888 sep 2019.
[18] M. Majka, A. Mijatović, and Szpruch. Non-asymptotic bounds for sampling algorithms without concciica,,,y, 2019.

---

[19] W. Mou, N. Flammarion, M. Wainwright, and P. L. Bartlett. Improved bounds for discretiza- tion of langevin diffusions: Near-optimal rates without convexity. Bernoulli, 28(3):1577-1011, 2022.
[20] W. Mou, N. Ho, M. J. Wainwright, P. L. Bartlett, and M. I. Jordan. Sampling for bayesian mixture models: Meme with polynomial-time mixing. arXiv preprint arXiv:1912.05153, 2019.
[21] A. Mossenii T. Farghly, He, K. Balasubramanian, and M. A. Erdogdu. Towards complete analysis of langevin monte carlo: Beyond poincar' 'e inequality. arXiv preprint
arXiv:2303.0358% 2023.
[22] Y. Peres and P. Sousi. Mixing times are hitting times of large sets. Journal of Theoretical Probability, 28:488-519, 2015.
[23] S. Vempala and A. Wibisono. Rapid convergence of the unadjusted langevin algorithm: Isoperimetry suffices. Advances in neural information processing systems, 32, 2019.
[24] S. S. Vempala. Recent progress and open problems in algorithmic convex geometry. In IARCS Anmual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Schloss Bagstuhl-Lcibniz-zenttue fuer Informatik, 2010.
[25] A. Wibisono. Proximal langevin algorithm: Rapid convergence under isoperimetry. arXiv preprint 191100 2019.
12

---

A Proofs of results in Section 4.2
A.1
Local LSI: Proof of Lemma 1
Proof.
Since
((S) /
4 M S
क Txx (x)2 dr / - (w))
xxx)² u(x)
dx - / V (x)
| x2))²
(x))
dx,
Mxx, (I:
ulx))
if ({() S V the proof is finished. Otherwise, have
p TTs
uls (a)
n xx (x)
Entals
<
dx S Vea.
x
p x3 (x)
The proof is completed.
A.2 Local Pl: Proof of Proposition
To begin with, we provide the proof of Lemma 2.
Proof of Lemma 2. Since
s(S)²
/
4 uss (x) a|
V (w) d())
/ v (a)
(()) dr.
(S))
π
The proof is completed by noticing that
1
V uls (x) n
PPii)llss dls(x) PFI(uls| (|s))
Varrls
p
We then prove Proposition 2.
Proof of Propsition 2. By applying the definition of LD, we have
dVar 2
dt
Taking integration of both sides of the above equation then gives
Th PFI( dt.
Var,
Var,
Var
x
π
The proof is then completed by noting that according to Hölder's inequality,
/ x
hh We
dl
T x(x) dæ s S.d
/ V # (x)
x ((x) dx dt = l Th
V
(x)
PFI [T) dt.
The proof is then completed.
We then restate the main result from [19], which provides tight characterization of the discretization error between LMC and LD. Proposition 3 (Theorem 2, [19]). Assume VV and V2V is L-lipschtiz. Initialize according to Gaussian and select h (1)Ln). Then for E Th, KT(@.llm.) (l22TT).
should be noticed that in the original version of [Theorem 2, [19]]. the result is only stated for interger time, i.e., kh where k E (0.... ,T). However, their proof also applies non-integer time which leads to the above proposition.
We are now ready prove Corollary 2.
13

---

Proof of Corollary 2. Combing Proposition 2 and Lemma 2, we have that
fruls
Var To
(S)
a|s
2Thp
Using Pinsker's inequality, we further obtain
TSS) [
25) Drv [Trn|s||=ss]
(4)
hTh
On the other hand, according to Proposition 3 and Pinsker's inequality, obtain that for t E [0, Th).
Drv [ | 2 O(P2dT))
and thus
Drv
Due to the convexity of L1 norm, we then obtain
Th #A(A) Th [ Th
Drv [Trll(TT = sup
Te(A) dt
A
Th
sup (A( (A))
Th
1
Th DTv [el[TTe] dt O(hdTT).
(5)
Let A be a positive constant.
According to Eq. (4), we have either (T) S A, or In the former case, combined with Eq. (5), we have that AVThp
Varr [
Drv [[]]s]][]ss] =
TTn < A+ OhddTT).
In the latter case, we have that
(ddVT
Drv [#rals||Talss]
A
and thus
|arr1
hd
Drv [T||TT]] 5o
+0
AvThp
A
The proof is completed by selecting h Var, jin T 3
ab Var,
and A
77
A.3 Difficulty extension Rényi divergence
Given two distribution æ and μ., Rényi divergence of between them, i.e., (MllTT is defined as follows:
P (a)))
R.(([[(T) 9
In Exg
For simplicity, here we consider Langevin Dynamics defined as Eq. (1) with the distribution of time denoted as #, The measure of convergence is then defined as RR (T. (T)) the derivative of which, according to (Lemma 6, [23]) given
d
Gg (
(T((TT) = =-q -q (Tell
dt
14

---

where
We 2
( (TL)
9-2
4
Gg (TellT)
Ex
log
Er
V
E
π
π
π
q²
π
Fg (m|](T) = En
If would like to follow the routine of Lemma 1, need to firstly lower bound Ca (()) by
G, (((((11))]((x) and secondly transfer (=(((,)))](((((s)) Fo(( ([][[)) back to ({(((()))((] The second step can be accomplished following the same routine as (Lemma 9,[24]) using local PI. However, we are still unaware of how implement the first step. This is because although have
S
$
(S)9 T (S))9111
Gg (TellT))
E
EEIS
q²
q²
T
which is similar to the analysis of local LSI, we also have
(S)
Fg ( = Ex
Ex
X
(S)
In other words, when restricting to S, both the denominator and the numerator of Gg(sell will get smaller, which makes G,(a.]lx) longer lower bounded by [S(((]))) We leave how to Fg((n 8) (()()))
(x(ril)))) resolve this challenge as an interesting future work.
B Proof of Applications
B.1 Proof of gaussian-mixture
To start with, we recall Bakry-Emery criterion and Holley-Stroode perturbation principle.
Lemma 8 (Bakry-Emery criterion). Let Q Rn be convex and let Ω + be a Hamiltonian with Gibbs measure μ(x) xx 1a()) and assume that 2 (xx) 2 k 0 for all x E supp(ps).
Then satisfies LST(K).
Lemma 9 (Holley-Strocck perturbation principle). If E (S)) satisfies LST();),, and th : TR. satisfies m 1/2 < M, where m, M >> 0. Then, q E A()) x upp satisfes LSI 3 mt).
We now ready prove Lemma 3.
Proof of Lemma 3. Since S; is convex, by applying Lemma 8, we obtain pils, is LSI(o"). Let min; wi.
Meanwhile, we have over Sj
cp S wypj Sp= Σ w.p, + Wyps S
Σ wips + wyPj = Pj.
141
Therefore, by Holley-Stroock perturbation principle, we have that pls, satisfies LSI (o
Proof of Lemma 4. Through direct calculation, we obtain
V2V Σー1 -- Eig (1))),())) - 13) - -
E-1
Then, for any Rd with ||al| = 1. we have
1
Ei, (xw) T
a V =a Ty-la
2
Eh wip((x))2
<a TITII1 a
1
<
-
15

---

and
a VV <a --' 12 is (.).pp())p (3) a
Eig (ewsp (Ei=1 wbpz(x))2 T--aa ス 0
maxi, 1/1s - 1/l1
The proof is completed.
B.2 Proof of sampling from the power posterior distribution of symmetric Gaussian mixtures
To begin with, define the expected potential function V as
((0) = 3Ex log [ - (0 x) 2 + log X(0).
We further define the corresponding distribution as x v
The following lemmas will be needed in the proof.
Lemma (Thcorem [20]) If A, M 2 ||]@oI||| + 1, we have HlR, satisfies PI(O(1/A^M3)).
Lemma (Lemma 4, [20])- If A, M 2 ||0o]| + 1, we have with probability at least
d
m(A d)
sup [[(0.A|xB(0MM))
[V V()0) S O(11 + A+ 1+MM
log n
Lemma 12. Suppose V obeys strong dissipativity i.e., VV is L-lipschitz and (VV(x), 2 m -| - b. Then, rumning LMC with h < T67 and h S 4b+32d
8m
we have
E Exa~xe Tm lay 32 exp
(8b + 64d)
4m
Proof. Define f(x) = e am |=
Assume wlog that VV(0) =
Then.
f(xx+1) = exp
|x
1 (-NVV(I*) + V2hEk. 3.K.
+
-hVV(xx) + /2hEo
4m
2m
4m
exp
1
||
1
(112112
V2h
(Ek, xK) + 2m
||>\V((>>))
"
11Ex|
4m
2m
2m
m
exp
1
|
||xx||
26)
+
22h
(Ek+ 2x) + -
h
||Ex
4m
4m
2m
m
Let Eg denote expectation wrt &x. Then
[x[[(xx-1)) ])] 5 Sexp
||a21112
h
||arze 1200-22200 (22-2 )
Ex
2h
(EN, xN)
+
-
h
||Ex
4m
4m
2m
1/2
< exp
||
|| 112 ( 2
Ex
22h (Ek,
En
2h
| 1|
4m
4m
m
Using the fact that x² variable is sub-exponential,
2h [15al1
4hd
Ex
exp
exp
m
16

---

On the other hand, notice that (E), ~ (O, [| ) is a 1-dimensional gaussian random variable. can be shown that
22
(Ex, at )
2h
Eg
exp
S exp
m²
|
(6)
m
Combining the above,
Bx]f(IK+1]] sexp
| 11
h
(10x112-266
+ 2hd
h
|| 1?
4m
4m
m
m2
h
| 11
||0xa|2 4b
-32dd)
Sexp
4m
8m
Let denote expectation wrt all randomness. Then
-46 4b-32d) ]
<B
exp
[
||zx||]
2|
4m
8m
=E
exp
|
2
||>x||
4b ab2-3 1 |axe|l 2 8b + oud}
4m
8m
+
E
exp
2
(1122112 - 4b 32d) 1 |1oaa1 s 86 + 6ld)
4m
8m
SR
exp
2
h
(4b + 32d) 1 1( ||00 1| 8b + oua}
4m
16m
+
E
cxp
|
1 + 8m
(4b+ + 32d) 1 { ||>2|| $ 8b + +4d
4m
||ax|112 1|= 22 8h + 6ld) (1-
h
(4b + 32d) ]
<E
exp
| 22
4m
32m
+
E
exp
| 12)
|| & 8b + +4dd
(1+ 4m
(4b + )20)
4m
|| (2) #)]
4m | 11 1 ||لa|| 2 86 + 6ld
=E
exp
(46 + 32d)
E exp
4m
32m
+ 4m
(4b + 32d) E
exp
|| 11²)
|||08||
S 8b + 6ld)
4m
|| 11 $)
(1 | 11 )
<
exp
(46 + 32d)
E
exp
4m
32m
4m
h
+ m
(4b + 32d)
exp
(8b + 64d)
4m
[xx]
h
(4b + 32d) [[f(=x]] + (4b + 32d)
exp
1 4m
(8b + 64d)
32m
Suppose that Iy is drawn from the invariant distribution under LMC. Then we know that (xx.) E (x(+))). In this case,
+ h (4b+ (3b) exp (8b + 64d))
55 32m
(4b + 32d) B[f(xx))
m
4m
Moving things around gives
1 4m
(8b + bld))
ES(xx)
32. exp
17

---

We are now ready to prove the lemmas in the main text.
Proof of Lemma 5, Based on Lemma 11, if @((A M)dd have with probability at least 1 - 6,
sup BER,
V ( - 0(1).
As result, we have
R (0) = ((1). and by Lemma 9 and Lemma 10, the proof is completed. RR
Proof of Lemma 6. To begin with, set E ~ (0, La). we have
x (110b + - 0) + + (11ooller + +5+0) 00 (1l6blle + 5 0) (10blle1 +
0)0 AT (11ooller + +.)
(V)()),) =1100|| + 3E
B 2
1012
(116b11 ( +1).
obtain
(VV 0) 2 2 _1011 - 23 (1161l +1)
following standard empirical process argument due to n 2 Ō((A 2 (see Lemma 6, [20] as an example).
Meanwhile, denote 7; if X; sampled from (O,, I1a) and 7; -1 else-wise. We have
|00.123
4p(X; - (Xx
V0) =BLa
(pp(X; 0) + + 0))² eiei
n
(v((X, 0) + ((x; 0))2 (X; - -xx
4i ()p(X; + 0)
- -aaii-r-ll000 T=10bblei)T
Σm and thus (3 - |1.113 A |X - T. 1:110olle111 12) S v2V(0) S B1g. As X; - T.llobller ~
(O Ta). by concentration inequality of chi-square variable and since 2 @((A (A + M) (12llog(1/8)) we have with probability at least
VVVV())) < 23 + 110.113).
The claim for || can be calculated following the similar routine. The proof is completed.
Proof of Lemma 7. The claim directly follows by applying Markov's incquality to Lemma 12.
C Proof of Theorem 1
We consider the variational form of spectral gap. We first define the Dirichlet form and the variance
Proof.
Ep(0, σ) (0, - Σ (()))(=)((< P(x,,)))
a.M
Var [0) = Σ (())(o(z) 2=
Then by the fact that P is lazy, and hence P 2/[ P) for some reversible transition P, we have
Var, [Po] Var, [6] (p(
By nonnegativity Er(á, Φ) 2 0,, have
Σ
Er
14 14
P40 Var=
π π
π
IS
18

---

By the variational form of spectral gap.
Ep(ó, 0)
inf nom consiant
Var [0]
Therefore, applying the Markov chain generated by P. we have that for any i S m,
Pe K π 2
Hel Mel
Σ Varz;
Σ
Ep.
(8)
M T
We then note that
Ep
Ft
Mt π
1 2
Σ
P(z y) (x) (1))
π
π
z,y
1
Σ
x(z)P(z.))) (z) 1t (y))
Σ
2
π
2,yEX
1
Σ
(1)))((z))(
He (v))
2
Z
Σ
(P))( - Pe(x, u))( Mt (x)
2
RUER
We note by (PI) that for any I, E Xr x # y, P(x,8) = P2 3) Therefore, the second term is zero. Hence,
Ut U1 Ep
T(x))² (x,)
[el u. X
2
Ep.
π
+|. x|xi
Combining with (7) and (8) get,
Σ
Varm
Pel T|A;
/mx(X,)²
S
Var
No0
(9)
T
T xxX;)
π
The claim then follows by discussing if for all (xG;) S (x 1/4 then
7
1
Σ
Varz:
Me X
X
S
xT1/2
Var
Ho
(10)
D Proof for Theorem 2
Proof. Given the subgraph V, we have that conditioned transition kernel is
p' (I, v) p(2, v) + 1 {- = nn P(x, (V')9.
We analyze the conductance on graph V induced by p',
EvEr: T (x)) Vi9)
min VICV'
(V),
For any partition V1, 1/2 of V", without loss of generality assume the local min of f is in V22, v² E V/2. For simplicity, for any Ví, we denote r(z) be the last element in its shortest path to v², We note that
d(z, (x)) $ D, (x) & ((((z))
Denote T(Vi) be the of such elements in V.. Then we have
Ever(v,) ((x)
Σ (x))
(1I)
4d
ZEV
19

---

Further denote T(x, r)) for some E {0, ..., df as the set of elements at distance r from ((x) along the descending shortest paths. We provide an illustrative figure in Then we have that
(Vi)
E
Σ ((,)))
(12)
(())
We note by reversibility that
1)) = T ( 1),,
(13)
Further by the fact that the function along the path is descending, we get that
p' 7(E, 1)) 2 ( 11,,
(14)
Therefore,
x()(,,r)) (
(15)
Hence we have
D ((,,r) s D=(((Vi))
7 *(v))
Σ
(16)
(())
Therefore, when (V)) $ 1/2 we have
Ezer (2))
2 4dD
min 1
when (Vi) 2 1/2 we have
Exer T<x)'(x,, Vi) min(((V)),1=<MM)
2 Σ {x,)p((x, VT)
zeVi
E Emer(V) ((r)
(T((V)))
1
2d
2dD
4dD
The theorem then follows by Cheeger's inequality.
X
v+
[xx
T(x,
V
Figure 2: An illustration for the definitions of r(x)and T(x, r).
Additional Experiments
We still use गı in 6.1 as target distribution. We initially set 1, 10, 2000 particles to run the LMC sampling algorithm respectively. We collect the locations of these particles after T = 1000 iterations as valid samples. The target distribution is shown in Figure 3a; empirical distributions using n = 1, 10, 2000 particles are shown in Figure 3b, 3c, and 3d.
We highlight two observations from the experiments. First when we use only one particle, it is always trapped in one Gaussian component and we never get samples from other modes. It has very bad global convergence, but still gets good conditional convergence: The convergence result conditioned
20

---

target distribution
(b) partiele
(c) 10 partieles
(d) 2000 partieles
on the st quadrant is good, and the sample after 7 iterations has no probability distributed on the other 3 quadrants. Second, when the number of particles grows, the sample after T iterations has non-negligible probabilities distributed on all of the 4 quadrants, which means we could capture all of the Gaussian components. The results indicate that although restarting LMC may not directly lead to global convergence, it may help capture the features in multi-modal distributions, which further implies we may empirically eliminate the "small probability mass" condition Corollary and mitigate the gap between sampling distribution and target distribution.
broader implication could be on ensemble and stochastic averaging in neural network training. where ensemble follows the restart procedure where as stochastic averaging is closer to sampling from single trajectory. Our theory and experiment suggest that the two can have very different distributions in the end.
21


Reviews:
[{"review_id": "WuI0JqvhW6", "reviewer": "Reviewer_Edvq", "summary": "This paper, following the framework of Balasubramanian et al., shows that for target distributions that are non-log-concave, isoperimetric inequalities on subsets of the state space will yield fast mixing for the conditional distributions of MCMC on that space. This adds formal justification for the observed phenomena of metastability and “local convergence”. Additionally, some analogous conditional convergence results are also reported for a random walk on a hypercube.\n", "questions": "The local mixing seems to be at a significantly worse rate than the global mixing under e.g. LSI, which we would expect to be something like $d/\\epsilon$ at least for the LSI case. On the other hand, we obtain something more like $d^2/\\epsilon^4$. Is there a principled reason for this difference and could the rate potentially be improved, or is the analysis expected to be somewhat sharp.\n\nIn some prior works, e.g. [6, 23], Renyi divergence is considered as a natural “measure” of convergence, due to the analytical simplicity of the resulting expressions. Would analogous results hold for this case? Furthermore, is there any barrier to considering e.g. Latala-Oleszkiewicz or other isoperimetries in the analysis? I would imagine so given that the “Fisher information” would now need to correspond to an inequality of LO-type.\n\nHow does the discrete sampling result compare to existing MCMC results in that field? See my comment in “Weaknesses”.\n\nTypos:\nFisher in Fisher information should always be capitalized\n\nL. 74 space after Balasubramanian\n\nL. 81 distribution -> distributions\n\nL. 82. Multimode -> multimodality\n\nL. 106 “the Langevin Monte Carlo algorithm”, function inequalities -> functional inequalities\n\nThe definition of a Lipschitz condition should be given explicitly.\n\nSome in-line equations are a bit difficult to read and should be presented as displays, e.g. L. 231 or L. 252.\n\nL. 286 “D” -> “Appendix D”\n", "limitations": "None beyond those raised in earlier sections.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "The definition and usage of these local isoperimetric conditions is entirely novel, as well as the local mixing results. In particular, the mixing rates seem to offer very good insight into the phenomenon of “metastability”, i.e. that particular modes may be well-explored while the global structure is not correct. \n\nThe paper is well illustrated with examples such as the Gaussian mixture and the posterior sampling example, with transparent computation of the constants. In particular, it is easy to see when the conditions of the paper hold, and to compute the resulting rate estimates.\n\nThe hypercube sampling result is novel, although it is difficult to assess this in the context of existing literature since the assumptions/results differ greatly.\n\nExperimental evidence is also provided to quantify the phenomena of local convergence.\n", "weaknesses": "The rate of local mixing in both local LSI and local Poincare cases are quite bad. See my remark in the “Questions” section.\n\nThe discrete state space case is difficult to assess compared to other results for discrete space MCMC. If this is to be a main result in the paper, I would recommend a more detailed survey of the literature on discrete space MCMC with relevant comments be included in the Related Work.\n\nThe experiments are not surprising and seem to illustrate the same phenomena as seen in earlier works on multimodal sampling, but I would argue that they are still fairly useful illustrations in the context of this paper. In my opinion, the experiments section could be shortened.\n\nThis paper could benefit from some proofreading to catch grammatical mistakes, of which I was able to find quite a few.\n\nTo summarize, I feel that this paper makes unique contributions to the theory and intuition of MCMC algorithms, and the issues with it are relatively minor. Therefore I am happy to recommend acceptance.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time to read our paper, and for the comments and suggestions. Here are our main responses: \n\n**Q1**: I would recommend a more detailed survey of the literature on discrete space MCMC with relevant comments be included in the Related Work.\n\n**A1**: Thank you for the suggestion. We will provide a more detailed literature review on discrete space MCMC in Section 2 of the revised paper.\n\n**Q2**: The experiments section could be shortened.\n\n**A2**: Thank you for the suggestion. We acknowledge that the current experiment section is a bit redundant, and will make the experiments section more condensed in the revised paper.\n\n**Q3**: The local mixing seems to be at a significantly worse rate than the global mixing under e.g. LSI. Is there a principled reason?\n\n**A3**: Thank you for the insightful question. We do not intend to claim that our rate to be sharp, and the local mixing rate may possibly be be improvable. Our main goal is to derive a mixing rate that is _polynomial over dimension_. Investigating the optimal local mixing rate is definitely an interesting future direction.\n\n**Q4**: Can the analysis be extended under Renyi divergence?\n\n**A4**: We acknowledge that Renyi divergence is a good measure of convergence, and have tried to extend our analysis under Renyi divergence but failed. In the analysis for Renyi divergence, the analogy for Fisher information $FI(\\pi_t||\\pi)$ is $G_{q,\\pi}(\\pi_t)/F_{q,\\pi} (\\pi_t)$. However, there is no clear relationship between $G_{q,\\pi}(\\pi_t)/F_{q,\\pi} (\\pi_t)$ and its local version due to the existence of $F_{q,\\pi} (\\pi_t)$ in the denominator. Therefore, even if we can show that  $G_{q,\\pi}(\\pi_t)/F_{q,\\pi} (\\pi_t)$ is small, we are unable to convert it to its local version and apply local isoperimetry.\n\n**Q5**: Is there any barrier to considering Latala-Oleszkiewicz isoperimetry?\n\n**A5**: Thank you for the suggestion. To our knowledge, existing analyses under Latala-Oleszkiewicz isoperimetry uses Renyi divergence, and the same problem in A4 will occur.\n\nFinally, thank you for pointing out the typos and minor suggestions, they have been duly revised. \n\nWe sincerely hope that the response to your concerns, as well as the overall response to other reviewers’ concerns, helps assuage your concerns, and view this paper in a more favorable light."}, {"review_id": "AEjX3wBstm", "reviewer": "Reviewer_7WcG", "summary": "This work studies the convergence of MCMC algorithms for sampling from non-log-concave distributions. This is much less well-understood than the log-concave setting. The authors introduce the notion of conditional mixing, this occurs when the markov chain is close to the true (conditional) distribution when conditioned on being in some specific part of the space. They give sufficient conditions under which conditional mixing occurs. They give applications to sampling from mixture distributions of gaussians and related problems.", "questions": "Regarding sampling from a Gaussian mixture distribution: Could you mention where your techniques break down when allowing differing covariances for the mixture distributions?", "limitations": "Maybe I missed this, but I do not think limitations were mentioned.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors propose a new framework to go beyond log-concave sampling, an important problem in the sampling literature and give evidence for its utility. They show that in some cases conditional mixing can appear very quickly, whereas global mixing provably takes much longer.\n\nThe paper is overall well-written.", "weaknesses": "I think non-expert readers could benefit from a high-level technical overview.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and positive feedback. Your concerns are correspondingly addressed as follows.\n\n**Q1**: Lack of high-level technical overview.\n\n**A1**: We thank the reviewer for the suggestion. We will expand our related work to provide more overview to the problem. Due to limited space, we can not copy the entire section, but we give an outline below:\n\na. MCMC, LMC, and their applications.\n\nb. Theoretical guarantees for LMC, and that PI / LSI / log-concavity can lead to fast mixing.\n\nc. Hardness result for LMC without log-concavity, evidenced by two mixtures of Gaussian.\n\nd. Results on non-log-concave distributions. \n\ne. discrete space MCMC.\n\n**Q2**: Difficulties for allowing different covariances for the mixture distributions.\n\n**A2**: Our current analysis is based on one important fact: the sublevel sets(i.e. $S_i = \\{x: p_i(x) \\geq p_j(x), \\forall j \\neq i\\}$) are convex when the covariances are identical because the sublevel sets can be viewed as a Voronoi diagram after affine transformation. However, if we allow each mixture to have different covariance, the sub-level set may be no longer convex. As an example, consider the following mixture of Gaussian over $\\mathbb{R}^2$: $p=\\frac{1}{2}p_1+\\frac{1}{2}p_2$, where $p_1\\propto \\mathcal{N}(0,\\mathbb{I})$ and $p_2\\propto \\mathcal{N}((1,0),2\\mathbb{I})$, the set $\\{x: p_2(x)\\ge p_1(x)\\}$ can be viewed removing an ellipsoid section from the entire space, which is not convex. Therefore, Bakry-Émery criterion can no longer be applied to derive Logarithmic Sobolev Inequality. It may be, however, still possible to derive local Logarithmic Sobolev Inequality by considering other partitions. This is highly nontrivial and we leave it as a future work. \n\n\n**Q3**: No limitations were mentioned.\n\n**A3**: Thanks for pointing it out. We include limitations in the revised manuscript. For example, some limitations of this paper include:\n\n1. lack of guarantee that our local mixing rate is sharp;\n\n2. lack of a principled way to derive local isoperimetric inequalities beyond mixture of Gaussians with identical covariances.\n\n3. lack of additional potential implications of fast conditional mixing.\n\nThank you once again for taking the time to review our paper. We sincerely hope that the response to your concerns, as well as the overall response to other reviewers’ concerns, helps assuage your concerns, and view this paper in a more favorable light."}, {"review_id": "jnqOvUIyNi", "reviewer": "Reviewer_UgtB", "summary": "The paper studies MCMC algorithms like the Langevin dynamics and Gibbs sampler on non-log-concave distributions. Many natural distributions are non-log-concave and multimodal, for example, mixtures of Gaussians and the posterior distribution of Gaussian mixtures. While classical results show that MCMC algorithms suffer from slow mixing on such multimodal distributions, the paper shows that when isoperimetric inequalities such as Poincare or log-Sobolev hold on a subset X of the state space, the conditional distribution of the MCMC iterate over X mixes fast to the conditional distribution of the target distribution on X. Thus, the paper shows that while MCMC algorithms converge to the true global distribution slowly, it can still converge very fast locally. For example, on a mixture of two isomorphic Gaussians, the Langevin dynamics (LMC) converges to the true conditional distribution around each mode but might put the wrong weight on the two Gaussian components. i.e. the true distribution is mu = 1/2 N(-u, sigma^2) +1/2 N (u, sigma^2) but the distribution of the LMC might be 1/3 N(-u, sigma^2) + 2/3 N(u,sigma^2). To show these results, the paper uses that for any target distribution mu, including non-log-concave ones, the LMC quickly converges to a distribution nu whose Fisher information to mu is small [Balasubramanian, Chewi, Erdogdu, Salim, Zhang—PMLR’22], then uses isoperimetric inequalities for the conditional distribution of mu on subsets of the state space to show that if the conditional distribution of mu on S satisfies isoperimetric inequality, then either nu puts small mass on S or the conditional distribution of nu on S is close to that of mu on S in Kullback-Leiber or chi-square distance (see Lemma 1, Corollary 1 for the case when the conditional distributions satisfy log-Sobolev inequalities, and Lemma 2, Theorem 2 and Corollary 2 for the case when the conditional distributions satisfy the weaker Poincare inequalities). Note that this is essentially the best statement one can hope for: for example, if mu is a mixture of two Gaussians whose centers are very far apart, and the LMC is initialized at the center of the first Gaussian, then the LMC will put almost all mass on the first Gaussian component and almost 0 mass on the second Gaussian component and one cannot have any reasonable guarantee about the conditional distribution of the LMC iterate on regions around the mode of the second component. In Theorem 2, the paper proves an analogous result for Gibbs sampler on discrete state space such as the hypercube.  For a distribution mu supported on the hypercube {0,1}^d, the Gibbs sampler operates by picking one random coordinate and flipping the value at that coordinate from 0 to 1 or 1 to 0 with probabilities chosen so that mu is the stationary distribution (see Section 5). The paper shows that if the vertices of the hypercube can be partitioned into subsets X_1,.., X_m such that on each subset, the Markov chain induced by the Gibbs sampler has a large spectral gap, then either the distribution nu produced by the Gibbs sampler puts small mass on X_i or the conditional of nu on X_ is close to that of mu on X_i. ", "questions": "-For mixtures of Gaussians, is the assumption that Gaussian components have the same covariance matrix necessary? Is this assumption natural?\n-The quasi-concave condition for the Gibbs sampler to have a large spectral gap appears rather unnatural. The author(s) could consider investigating natural multimodal discrete distributions such as the Ising/Curie-Weiss model at low temperatures (see [Levin-Luczak-Peres—Probability and Related Fields’2010]).\n", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper shows an interesting result using relatively simple techniques. While fast convergence of LMC iterates in Fisher information for general non-log-concave distribution and local isoperimetric inequalities are known and used in previous works (see [Balasubramanian, Chewi, Erdogdu, Salim, Zhang—PMLR’22] and [Mou, Ho, Wainwright, Bartlett, Jordan’2019]), the paper cleverly combines these two ingredients together to show local mixing of familiar MCMC algorithms likThe paper shows an interesting result using relatively simple techniques. While fast convergence of LMC iterates in Fisher information for general non-log-concave distribution and local isoperimetric inequalities are known and used in previous works (see [Balasubramanian, Chewi, Erdogdu, Salim, Zhang—PMLR’22] and [Mou, Ho, Wainwright, Bartlett, Jordan’2019]), the paper cleverly combines these two ingredients together to show local mixing of familiar MCMC algorithms like the LMC and Gibbs sampler on multimodal distributions. The main results appear to be novel and correct. I verify the proof of Lemma 1, Corollary 1, and Lemma 3.e the LMC and Gibbs sampler on multimodal distributions.  ", "weaknesses": "The result on mixtures of Gaussians requires the assumption that the Gaussian components share the same covariance. It’s unclear if this assumption is natural, and the author(s) don’t give any justification for this assumption.\nThe paper has a few typos. Details below.\n- Proof of Lemma 1, supplement, appendix A: The claim is either $\\mu(S) \\leq sqrt{\\epsilon}/sqrt{\\alpha}$ or $Ent_{\\pi|S}(\\mu|S || \\nu|S )\\leq sqrt{\\epsilon}/sqrt{\\alpha}$ but the proof instead show that either $\\mu(S) \\leq \\sqrt{\\epsilon}$ or $Ent_{\\pi|S}(\\mu|S || \\nu|S )\\leq sqrt{\\epsilon}/\\alpha.$ The fix is simple, in line 416, it should be $\\mu(S)\\leq \\sqrt{\\epsilon}/\\sqrt{\\alpha}$ and in line the following displayed equation, the rhs should be $\\epsilon/(\\sqrt{\\epsilon}/\\sqrt{\\alpha}) = \\sqrt{\\epsilon \\alpha}.$\n- In proof of Lemma 3, supplement, appendix C.1: c is undefined, though I believe c = min_i w_i so that c\\leq w_j and cp_j \\leq w_j p_j holds in the first line of the proof. The proof, Lemma 3 only proves that p |S_j satisfies LSI with constant 1/min_i w_i sigma^{-2},  but lemma 3 claims that the LSI constant is max_i w_i/min_i w_i sigma^{-2}. However, 1 \\leq m max_i w_i where m is the number of components/parts in the partition of the state space, so the bound the proof achieves is only worse than the claimed bound by a factor of m, which doesn’t significantly affect the result.\n-In the statement of Lemma 2, in both the main paper and supplement, pi satisfies PFI -> pi satisfies PI.\n-In section 4.3.1 of the main paper, line 210, P is undefined, but I believe the author(s) mean U.\n-In Lemma 5, lines 239 and 240 of the main paper, the author claims that the target distribution satisfies local LSI, but its proof (Lemma 13, line 467 of the supplement) states that the target distribution only satisfies local Poincare inequalities.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and positive feedbacks. Your concerns are correspondingly addressed as follows.\n\n\n**Q1**: Typos &  mistakes.\n\n**A1**: We thank the reviewer for pointing out the typos. We will update our draft with the following changes:\n\na. Lemma 1: In line 416, it should be $\\mu(\\mathcal{X}_i) < \\sqrt{\\frac{\\epsilon}{\\alpha}}$, and rhs of the following equation should be $\\sqrt{\\epsilon\\alpha}$. \n\nb. Lemma 2: $\\pi$ should obey $PI(\\rho)$ instead of $PFI(\\rho)$ in both the main paper and supplement. \n\nc. Lemma 3: In Lemma 3, $c$ should be $\\min_{i} w_i$. The result should be $\\pi\\vert S_i$ obeys $LSI(\\frac{\\sigma^{-2}\\min_i w_i}{m \\max_i w_i})$ or just $LSI(\\sigma^{-2}\\min_i w_i)$, where $m$ is the number of components in the partition of the state space.\n\nd. Section 4.3.1: In line 210 and 211, $P$ should be $U$, the same as previous notation. \n\ne. Lemma 5: Here LSI is a mistake in line 239 and 240. It should be PI, which is consisitent with our proof in the supplement and with following bounds on variance instead of entropy. \n\n**Q2**: Assmuption of Gaussian components having the same covariance matrix\n\n**A2**: We thank the reviewer for pointing this out. That the components share the same covariance is necessary for our analysis. Extending the result to mixtures with different covariance matrix is possible but highly nontrivial. We mainly considered and tried two ways to tackle this more general situation:\n\n1. Find a partition of sublevel sets that are all convex. In this way, we tried to use the same partition as we have in our paper. However, the assumption of Gaussian components having the same covariance matrix is important in our proofs, as it enables us to decompose the sample space into convex subsets.\nIf we allow different covariances, the sub-level sets (i.e. $S_i = \\{x: p_i(x) \\geq p_j(x), \\forall j \\neq i\\}$) can no longer be convex.  As an example, consider the following mixture of gaussian over $\\mathbb{R}^2$: $p=\\frac{1}{2}p_1+\\frac{1}{2}p_2$, where $p_1\\propto \\mathcal{N}(0,\\mathbb{I})$ and $p_2\\propto \\mathcal{N}((1,0),2\\mathbb{I})$, the set $\\{x: p_2(x)\\ge p_1(x)\\}$ can be viewed removing an ellipsoid section from the entire space, which is not convex. Therefore, Bakry-Émery criterion can no longer be applied to derive Logarithmic Sobolev Inequality. It may be still possible to derive local Logarithmic Sobolev Inequality by considering other partitions, which we leave as a future work. \n\n2. Use identical Gaussians to approach to mixtures of K non-homogeneous Gaussians. More generally, a more complex distribution, such as a mixture of K non-homogeneous Gaussians can be approximated by a N identical Gaussians, for some N > K. The price for this reduction is increasing the number of components; but we have not worked out the optimal tradeoff for how large N needs to be. \n\nWe acknowledge that sampling from more complicated mixtures is an important question for future work, and thank the reviewer for raising this point.\n\n**Q3**: Quasi-concave condition for the Gibbs sampler seems unnatural\n\n**A3**: We first explain our intuition in the quasi-convex condition. We aimed to identify a discrete analogue of log-concavity. In order to define concavity on a discrete space, we naturally resort to geodesic-concavity, in which all function super-level sets are convex with respect to geodesics (i.e. shortest paths). In our paper we show that such a condition can lower bound the spectral gap of Glauber dynamics, and hence previous analyses can readily apply.\n\nWe appreciate the reviewer's refernce to closely-related and interesting work. It is possible that we generalize the CW model to multimodal setup, maybe via increasing the rank of the energy function. We think this can be an interesting direction but we won't be able to finish this within the Neurips timeline. \n\nThank you once again for taking the time to review our paper. We sincerely hope that the response to your concerns, as well as the overall response to other reviewers’ concerns, helps assuage your concerns, and view this paper in a more favorable light."}, {"review_id": "v7k2WwX0Ny", "reviewer": "Reviewer_Lt2V", "summary": "This paper introduces a new concept of conditional convergence of an algorithm (i.e. convergence of the distribution restricted to e.g. a local mode), and presents extension of recent results using e.g. Poincare Inequality to bound this new measure.", "questions": "Can you more convincingly explain the practical importance of Corollary 1? \n\nAs part of this, it feels like the rate of convergence matters (as we have convergence of LMC in general, just that it can be very slow). The slowness of LMC is, I believe, linked to e.g. constants for convergence depending on features of the target (more separated modes implies slower convergence) -- so it feels like you want stronger results than Corollary 1 where you get a handle on the constants. I.e. are the results in Corollary 1 uniform over targets?", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "I think this paper tackles an important problem: sampling from multi-modal distributions is likely to get stuck in a local optima and so understanding how well it samples from that mode is sensible (particularly when thinking about how a sampling based approach compares to an optimisation one).\n\nThe idea and definition of conditional convergence is new and interesting -- and one could see a new body of research around this type of topic.\n\nThe theory is based on a single, simple results (Lemma 1) which can then be used to generalise existing results on convergence to conditional convergence.", "weaknesses": "The main weakness is that the current result, e.g. Corollary 1, are weaker than one would hope. In particular \n\nCorollary 1 seems to have a time-dependent step-size (so to understand pi_T we need a smaller step size as T increases). This is different from how algorithms are implemented.\n\nThe conclusion after corollary 1 does not make sense to me. “Either the probability mass … over S converges to 0, or…” : But whilst LMC can converge slowly, it still converges to pi (if we ignore the discretisation error). Thus surely for any set S that is not a null-set of pi we have pi_T(S) will be non-zero in the limit as T goes to infinity?\n\nMore generally, this corollary is quite the result you want. You want something that says “if I have a partition of the the state-space in sets S_1,S_2,\\ldots, and observe that the proportion of time LMC stays in S_i is greater than … then the LMC output restricted to S_i will be close to pi restricted to S_i” or similar. \n\nSo I struggle to really understand the practical importance of the result.\n\nSeparately, the presentation could be improved in places: \n\nE.g. missing “the”s for *the* local Poincare inequality, and *the* Poincare Figure information (and e.g. “fisher”->”Fisher”, gaussian to Gaussian etc.); also “Gibbs sampling on discrete state *spaces*” etc.\n\nWhen describing Langevin Monte Carlo, there are two different approaches depending on whether you use a Metropolis correction. The paper could be clearer about what its results relate to. Form the definition in Algorithm 1 it looks like you are considering the unadjusted Langevin algorithm (ULA).\n\nIf you are using ULA, then there is a discretisation error — i.e. the stationary distribution for ULA is different to that of the Langevin diffusion/the distribution you want to sample from. I think the paper could be up-front about this, and discuss how this impacts the results in the paper. I also wonder if informal statements such as “The convergence of LMC” (top p.4) are really referring to the convergence of the Langevin diffusion and not ULA. The paper does comment on “PI .. implies the convergence of LMC when the step size h is small”, but this could be more precise. I guess part of the confusion is that you are commenting on converging, but it is not completely clear what you are converging to. In general the ULA will not converge to pi for a fixed (albeit small) step-size as the discretisation error will change the stationary distribution.\n\nThe argument under Fisher information seems to ignore the discretisation error — i.e. be just for the Langevin diffusion, but is says for LMC. (Though this is corrected in Proposition 1 which is for LMC). This part could have been improved with some references to the results you are summarising.\n\n[It may be that a cleaner presentation would be to have had a subsection commenting on the approximation error between ULA and the Langevin diffusion, and then presenting the results just for the Langevin diffusion?]\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for acknowledging the importance of our problem. After reading the review, we find that there could be several misunderstandings. We begin with clarifying these misunderstandings and then address other concerns.\n\n**On \"convergence of LMC\".** In this paper, when we talk about \"convergence of LMC\", we mean that \"by running LMC with step size $h$ and total iteration $T$, we can obtain a distribution $\\mu$ with distance (global or conditional) smaller than $\\varepsilon$ from the target distribution $\\pi$, where $h$ and $T$ can depend on $\\varepsilon$\". This definition of convergence has been employed by many existing works including [1,2]. The reviewer seems to misunderstand the \"convergence\" as \"the step size $h$ does not depend on $\\varepsilon$\". We will include the above explanation of \"convergence of LMC\" in the revised paper.\n\n\n**On  Practical Importance of Corollary 1.** To address this point, we briefly recall the motivation and goal of our study:\n\n(1)The global convergence of LMC in general non-log-concave cases has been proven to be **exponentially slow in the worst case**. For a simple example, consider the following mixture of two standard Gaussians:\n> $p(x;c) \\propto \\frac{1}{2} e^{- (x+c)^2} + \\frac{1}{2} e^{- (x-c)^2}$.\n\nThe global convergence is provably exponentially slow in the separation distance $c$.\n\n(2) However, Corollary 1 shows the remarkable fact that **local mixing can be fast even when global mixing is provably slow.** For instance, for $p(x;c)$ above, $\\pi_t \\vert_{(-\\infty, 0]}$  is $\\epsilon$ close to $p(x;c) \\vert_{(-\\infty, 0]}$ in $O(1/\\varepsilon^4)$ steps, **independent of $c$** (ditto for $[0,\\infty)$). As the reviewer notes, **one would expect that** \"more separated modes imply slower convergence\", so it is highly remarkable that local convergence rate **in fact does not depend on the separation distance $c$!**\n\nMore generally, Corollary 1 guarantees polynomial-time sampling as long as **each mixture component has a good LSI constant**, which is a much more lax requirement than for the entire distribution to have good LSI. For instance, each component of $p(x;c)$ has LSI constant of $\\Theta(1)$, but $p(x;c)$ has LSI constant of $\\Theta(e^{-c^2})$.\n\n(3) The catch to Corollary 1 is that local convergence says nothing about mixture weights, so you can have two very unbalanced modes. However, in many practical settings, even guaranteeing accurate samples within a mode is valuable (e.g. one might care more about generating accurate pictures of dogs/cats, and care less about the ratio of dog pictures to cat pictures.)\n\n\n**Other concerns.**\n\n**Q1**: Corollary 1 uses time-dependent step-size.\n\n**A1**: In all our results, T stands for the total iterations that the algorithm runs. The T-dependent stepsize can be easily transformed into an epsilon-dependent step-size. For instance, in Corollary 1, for epsilon target accuracy we need $T = O(\\alpha^2 d^2 /\\epsilon^4)$, so the stepsize $\\delta = \\alpha d/\\epsilon^2$. Perhaps you will find this formulation more familiar, and most MCMC papers do have stepsize depending on epsilon (e.g. in [1,2]).\n\n**Q2**： \"probability mass ... converges to 0\" seems redundant.\n\n**A2**: The reviewer also acknowledges that \"LMC can converge slowly\". In fact, the global convergence rate for a simple mixture of Gaussians can often be as slow as $e^{-d}$. It is therefore highly non-trivial that Corollary 1 has polynomial dependence on all problem parameters. As T goes to infinity, a \"set S that is not a null-set of pi\" will indeed eventually have significant mass, but this can take **an exponentially long time (see the Gaussian mixture example in \"On  Practical Importance of Corollary 1.\" above)**, so one cannot simply assume that every set S has sufficiently positive probability in practical settings when the total iteration number T is not exponentially in problem dimension d.\n\n**Q3**：\" this corollary is quite the result you want\"\n\n**A3** The reviewer's suggestion is in fact quite similar to our Corollary 1. Consider the following re-statement of Corollary 1, using similar phrasing as the reviewer's suggestion: \n> “if I have a partition of the the state-space in sets S_1,S_2,\\ldots, and observe that **the probability $Z_t$ stays in S_i** is greater than … then **$\\bar{\\pi_t}$ restricted to S_i** will be close to $\\pi$ restricted to S_i”\n\nThe difference from the reviewer's suggestion is bolded. Qualitatively, Corollary 1 is almost identical to the reviewer's suggestion, except we consider probability at time $t$ ($\\mu_t$) instead of path-average. We are thus unsure about what the reviewer means here. We will greatly appreciate it if the reviewer can elaborate on/clarify this point.\n\n\n**Q4**: Presentation.\n\n**A4**: We thank the reviewer for this suggestion and will correct the typos and update the manuscript. We will also further highlight (currently in line 113-118) that we consider the unadjusted Langevin algorithm and the analyses done in our work are for discretized algorithms.\n\n\n**Q5**: Is Corollary 1 uniform over all targets?\n\n**A5**: We are uncertain about the reviewer's use of the term \"uniform,\" but we will attempt to clarify it in this context.\n\n1. It is indeed possible to derive outcomes from Corollary 1 based on certain \"features of the target.\" This is due to the rate in Corollary 1 being dependent on the local LSI constant $\\alpha$, which in turn relies on the \"features.\" In Section 4.3, we demonstrate how to calculate the local LSI using the \"features.\"\n\n2. Although the global convergence rate is also influenced by the \"features,\" it can be exponentially slow and, therefore, impractical. This is exemplified by the mixture of two standard Gaussian distributions, as discussed earlier.\n\n \n**References:**\n\n[1].  Analysis of Langevin Monte Carlo from Poincar´e to Log-Sobolev\n\n[2]. Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlo\n\n"}]

Author rebuttal:

Meta-review: The authors study the important problem of sampling from non-log-concave/multimodal distributions where fast mixing is generally hard to come by. They instead formulate and establish guarantees on conditional mixing, a weaker and more achievable guarantee which can be sufficient for downstream applications. The theory is well-developed and explained. The paper received high ratings, and I recommend acceptance.
Decision: Accept (poster)