Rapidly Mixing Multiple-try Metropolis Algorithms for Model Selection Problems
Authors: Hyunwoong Chang
Changwoo J. Lee
Zhao Tang Luo
Huiyan Sang
Quan Zhou
Venue: NeurIPS 2022 Accept (2022)
Keywords: Bayesian model selection
Markov chain Monte Carlo
mixing time
Multiple-try Metropolis

Abstract: The multiple-try Metropolis (MTM) algorithm is an extension of the Metropolis-Hastings (MH) algorithm by selecting the proposed state among multiple trials according to some weight function. Although MTM has gained great popularity owing to its faster empirical convergence and mixing than the standard MH algorithm, its theoretical mixing property is rarely studied in the literature due to its complex proposal scheme. We prove that MTM can achieve a mixing time bound smaller than that of MH by a factor of the number of trials under a general setting applicable to high-dimensional model selection problems with discrete state spaces. Our theoretical results motivate a new class of weight functions called locally balanced weight functions and guide the choice of the number of trials, which leads to improved performance over standard MTM algorithms. We support our theoretical results by extensive simulation studies and real data applications with several Bayesian model selection problems.

Rapidly Mixing Multiple-try Metropolis Algorithms for Model Selection Problems
Hyunwoong Chang" Department of Statistics Texas A&M University hwchangåstat. tamu. edu
Changwoo J. Lee" Department of Statistics Texas A&M University c. leelsttt....... tamu. edu
Zhao Tang Luo Department of Statistics Texas A&M University ztluo@stat. tamu. edu
Huiyan Sang Department of Statistics
Quan Zhou Department of Statistics Texas A&M University quan@stat tamu. edu
Texas A&M University huiyan@stat. tamu, edu
Abstract
The multiple-try Metropolis (MTM) algorithm is an extension of the Metropolis- Hastings (MH) algorithm by selecting the proposed state among multiple trials according to some weight function. Although MTM has gained great popularity owing its faster empirical convergence and mixing than the standard MH al- gorithm, its theoretical mixing property is rarely studied in the literature due to complex proposal scheme. We prove that MTM can achieve a mixing time bound smaller than that of MH by factor of the number of trials under a general setting applicable to nigh-dimensional model selection problems with discrete state spaces. Our theoretical results motivate new class of weight functions called locally balanced weight functions and guide the choice of the number of trials, which leads to improved performance over standard MTM algorithms. We support our theoretical results by extensive simulation studies and real data applications with several Bayesian model selection problems.
Introduction
The Markov chain Monte Carlo (MCMC) method has become a powerful and standard tool for Bayesian posterior computation. In particular, the Metropolis- Hastings (MH) algorithm widely employed in many statistical and machine learning models to sample from posterior distributions with intractable normalizing constants. prominent usage example MH the vast class of Bayesian model selection problems with liscrete-valuee high dith-niinnsional parameters, whose pos- terior probabilities are infeasible to evaluate because the size of model space potentially grows (super-)expone)) Jexponentially with the number of parameters. Examples of Bayesian model selection prob- lems and their applications are ubiquitous, including Bayesian variable selection (BVS) [45, and references therein], stochastic block model (SBM) [20, 34], Bayesian structure learning [10, 15, 29], change-point detection model [5. 11], spatial clustering models [23, 26, 28), and many others.
Despite the popularity of MCMC algorithms, their convergence rate analysis is often challenging. Mixing time is a key concept of interest when analyzing the convergence of MCMC, which defines the number of iterations needed to converge
stationary distribution within small total variation distance [25]. We say a chain is rapidly mixing the mixing time grows at most polynomially in some complexity parameters, Mixing time bound has been studied extensively for problems such as card shuffling [3]. random walks on groups [2]. graph colorings [21], and the Ising model [14], across
Equual contribution
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the fields of probability. physics, and computer science [40]. Although there is a rich literature on discrete-state-space mixing time analysis in many areas, the focus has been primarily on approximate counting and random generation, but only recently has research on the MCMC convergence in the context of statistical model selection begun to emerge. [47] proved rapid mixing of an MH algorithm in iigh-dimensional BVS problem, and [38] improved the bound when a "warm start" is available. Rapid mixing results of MH algorithms are established for Bayesian community detection problem with SBM [55] and for learning equivalence class in a high-dimensional Bayesian structure learning [52]. Recently, locally informed MH algorithms have been developed to incorporate local information about the target distribution. [48] proposed locally balanced proposal and proved their optimality in terms of Peskun ordering [37] for discrete space models without providing mixing time rate analysis. [54] also proposed informed MCMC and proved dimension-fii -fee mixing time bound but only for a BVS problem.
The multiple-try Metropolis (MTM) algorithm [27] is an extension of the MH algorithm, which uses weight function to choose the proposed state among randomly sampled trials from a proposal distribution. The variety of weight functions and the number of trials enrich the algorithm class but result in a much more complex transition probability than standard MH algorithmss, hampering the theoretical development on the mixing time of MTM. As result, there is a lack of theoretical guidance for practitioners on the choices of weight functions and number of trials in MTM and also the choice between MTM and other MCMC algorithms. Only very recently, [46] considered the MTM independence sampler (MTM-IS), a special case of MTM where the proposal does not depend on the current state. They conducted the convergence rate analysis of MTM-IS, which shows it is less efficient than the simpler approach of repeated Metropolised independent sampling at the same computational cost, but they did not diseuss the choices of weight functions and the number of trials. As acknowledged in [46], MTM is significantly different from MTM-IS, and its convergence rate is more challenging to analyze. In this paper, we establish the mixing time bound of MTM for general model selection problems. Our main contributions are the following:
1) We show that MTM with existing popular choices of weight functions can have mixing issues and propose new class of weight functions called locally balanced weight functions.
2) With locally balanced weight functions, we prove that the mixing time bound of the MTT algorithm is smaller than that of the MH algorithm by factor of the number of trials N in general model selection setting, under some regularity conditions including a rate condition on N.
3) We provide theoretical justification for the counterintuitive phenomenon that an increase in the number of trials N may not always lead to a proportionate improvement in mixing, and suggest a theoretically guided algorithm to choose N for practical use.
4) We validate our theoretical findings via extensive simulation studies and real data applications with various model selection problems: Bayesian variable selection, stochastic block models, spatial clustering models, and structure learning models.
2 Preliminary
2.1 Notation
For a positive integer m e N, let [m] = {1, {l...., ., m) and [m] be the largest integer no greater than m. Let denote the cardinality of set. Let X' Xp denote finite state space where |X grows in complexity parameter p E N. We use P : X x X - [0, 1] to denote the transition probability matrix of an irreducible, aperiodic and reversible Markov chain. We denote by I an identity matrix. We call probability distribution on X a stationary distribution or a target distribution of a chain P if it satisfies ΣEEx (2)) ((x) for all x E X. In Bayesian inference, is a posterior distribution. Net X + 2x be a set-valued map called neighborhood relation, which maps state to a set of states. We say the neighborhood relation A is symmetric if x E (x(x)) iff a E (a')) for all # x'_ We define the random walk proposal matrix as Knw (I. y)
[ (2) where 1x(=) denotes the indicator function of (xx). We say K is symmetric if K y) K(y,z). x). We denote graph by (V, E) where V is the vertex set and E C V x V is the set of edges. We say 5(x, v) = (Mo,.... Um) is an E-path (with length m) from I to y e = (#-1,, v)) E E for i E [m]. 20 x, Um y, and all vertices are distinct.
2

---

Algorithm 1: Multiple-try Metropolis (MTM) algorithm with proposal KRW
Input: An initial state z0. neighborhood relation N, the number of trials N, weight function w defined in (1), the number of Markov chain iterations T.
for f O....,
1 do
2
Step 1. Draw M1..... UN uniformly at random from (zz,, and compute w(y; xx) for j -= 1. ,I..,,,,, N.
Step 2. Select j E [M] with probability proportional to w(y; (xr)) and define y = Mj-
Step 3. Sample .i...., -1 uniformly random from A(yy) and define
{
{1, w(y x4) + EIE(N) w xx)) w w(1 ()) + Die w(x v) S
min
(2)
Step 4. With probability a, accept y and let U+41 yi otherwise, let 1e41 Zz.
Output: A set of Markov chain samples {
2.2 Multiple-try Metropolis algorithm
We present the MTM algorithm [27] on a discrete state space in Algorithm 1. Here N trial states "1..... y/N are first sampled from the proposal K Rww(x, +), and then the proposed state y is selected among the trials using the weight function
w(y 2) = TVy Knw xyy x),
where X(y, .) can be any symmetric function that is positive whenever KRw (y,z) O. Note that Algorithm/ becomes the standard random walk MH algorithm when the number of trials N is one.
There have been efforts generalize the MTM algorithm [9, 12, 30]- [35] extends the weight function class by proposing a general form of acceptance probability to achieve the reversibility of a chain when the weight function does not belong
(1). While one can easily find a weight function satisfying (I), there is little research on the most appropriate form of weight functions. [27] investigated some particular class of weight functions and claimed the performance insensitive to the choice of weight functions within this class; w(y x)) = π (zy (when KRw is symmetric) and w(yl 2)) = π (v)/ Rw (z, y) are popular choices in this class [6, 33).
Another important component of the MTM method is the number of trials N. It has been reported with empirical evidence that increasing N does necessarily result in corresponding improvement in mixing under the random walk proposal [32]. They illustrate a counterintuitive phenomenon that the acceptance probability for a proposal move to higher probability regions be extremely low. As a solution, they suggest randomly selecting N at each iteration. Despite the anecdotal observation that certain choices of N make the algorithm less efficient, the principled way choose N is rarely discussed in the literature.
2.3 Analysis on mixing time via geometric tools
theoretical foundation for employing MCMC methods sample from a posterior distribution on a finite state space is the well-known convergence theorem, which states that an irreducible and aperiodic Markov chain with stationary distribution converges the stationary distribution regardless of the initial distribution [25, Theorem 4.9]. However, since it is impossible to sim- ulate a chain infinitely long, our main interest is analyze how well the chain approximates the target distribution after a certain number of steps. To this end, we introduce e-mixing time
(e) = max min E N: |PPi (z. - -x)1 S { where ||- is the total variation (TV) distance, is small positive constant, and Plazy (P + 1)/2 denotes the lazy version of P, which is introduced merely for theoretical convenience since all eigenvalues of P Pazyy are non neg-nveative (the use of lazy Markov chains is standard in mixing time analysis). In words, fmix quantifies the necessary number of steps for the chain to have small TV distance from the stationary distribution. Among several techniques for characterizing the mixing property [8, 18, 25, 42), path method is employed to derive our main result [13, 43]. We also refer readers to [25, Section 13.4] and [42, Section 3] for more details about the path method. Intuitively, the mixing time depends on how well the states "communicate". especially among those which have high values of æ. In contrast to
3

---

samplers defined on continuous state space with Euclidean topology, posterior landscape and modality on a finite state space are more difficult envision since it highly depends on how one defines the neighborhood relation. Given a transition probability matrix P, we define the neighbor- hood of a state x: by N(x) = {a' E EX \ {x} P(x, a') > 0), the set of reachable states by one-step transition from z, and we say x is a mode if x(x) > maX (ar). This specification of the neighborhood enables to define a graph (X',) E) where E = {(x, x²) E X' x X' x' E (xx)) is an (undirected since we have a symmetric neighborhood relation by the reversibility of P) edge set. For each (x. v) E X' X X' with * y, we choose only one E-path from x to y and denote it as 8(z, y). path ensemble defined as collection of the paths A = {ō(x, y) : x, E Xx x # y). path ensemble is a "configuration of path network" that helps quantify the quality of the communication within the state space X. The following proposition, which serves as base of our main result, gives mixing time bound by means of path ensemble. Proposition! 1 ([43)). For any path ensemble A.
min ((x) }
(mx S 2p(A)((A) log(1/e) + log
DE
where ((A) maxx,9 16(2, y) and
p( = max
E
T())T(y).
(3)
(0,0)E TI (u)
z.y:((r.)))tw.0))
For completeness, we provide a proof of Proposition with a detailed discussion Appendix A. The quantity p(A) is called the congestion purameter, and ((A) is the length of the longest path in A. To interpret ((A) ) and f( ((), ), some terminologies from transportation networks in graph theory are often useful. Consider л (u)P v)) the capacity of an edge (u, v). and (xx)T(y) as the unit flow of a path ((, y). Then p{A) quantifies the maximum loading of an edge under the configuration A. If one edge with small capacity is traversed by a huge number of paths with a high unit flow, it results in a constriction. Consider ((A) as the diameter of the configuration A. If the diameter is extremely large, it causes inefficient communication, especially among the states lying the margin of the configuration. it is possible to design the path system in a way that no edge is overloaded by paths and no two states are far apart, then the chain have good mixing behavior. One of the key steps in the proof of the main result is to identify a good path ensemble A (see Appendix A.3).
3 Main result
In this section, prove the rapid mixing of the MTM algorithm for general model selection problems on a finite model space X', where we assume that there is only one state with the highest posterior mass, denoted by x². Throughout the section, we may assume that |.X| grows with the complexity parameter (e.g., the number of variables in BVS), and the posterior distribution æ and other related objects are implicitly parameterized by p.
3.1 A mixing time bound with locally balanced weight functions
While extending the possible form of weight functions has been the main focus the literature [33, 35), the choice of weight function is rarely discussed. We introduce class of weight functions by using a function h: R5:0 + R: that satisfies hu)) = w/(1//1 /u) for all u > O; such a function is called balancing function [31, 48]. The class of balancing functions is very broad:
can choose an arbitrary non-negative function on (0, 1]. and then h(u) on u E (1, oo) is defined by the "balancing rule". h(u)= wh(1/ (//).. Typical choices of balancing functions include vū, min (1, u), max u). u/(u- + 1), and u + 1. The following proposition states that Algorithm with the proposed weight function induces reversible Markov chain with its stationary distribution.
Proposition 2 (Locally balanced weight functions). Suppose that weight function is defined as
( KRw
w(yl x) h
(4)
(T(x)) (RW (x,
where is a balancing function. Then, a Markov chain PMTM induced by Algorithm I has stationary distribution

---

The proof is deferred to Appendix A.2. We call weight functions of the form (4) locally balanced functions; though we only consider random walk proposals in this paper, Raw in Proposition can be replaced by any other proposal matrix. Compared with the popular choice of weight function in the existing MTM literature such as w(y x) = π (y), the locally balanced weight function can be viewed as transformed and scaled version with respect to the posterior probability at current state For example, if h((u) vu and Kaw is symmetric, then w(y (x) v (z))
Before providing rigorous mixing time bound of MTM under our new choice of w 2). we give an intuitive explanation for why the existing unscaled weight function may have poor mixing properties. First, it is reasonable to assume that the true data- generraiig model, x², will have the largest posterior probability when the posterior contraction or the model selection consistency holds asymptotically. Indeed, such results have been established for a variety of model selection problems [47, 52, 55]. On the other hand, a model space X' is often endowed with natural neighborhood relation such that the degree of "model fit" (measured by goodness of fit and penalization on model size) between neighboring models tends to have a small difference. This implies that a small modification of model may lead to a marginal change in the posterior probability. For example, in a Bayesian variable selection problem with the number of variables p. the model space can be represented as set of binary vectors y E {0, 1 where 7 = 1 (resp. 7 = 0) indicates j-th variable is included (resp. excluded) in the model. Let us assume that > is the true data generating, model and has the highest posterior probability, and define a Hamming distance du(7, = Σラ= 1 {7g * 73} for y, 7 E {0, 1.P. One often defines the neighborhood. (N(7) as the set of states with small Hamming distance to y [19, 47, 54], and models in the neighborhood tend to have similar posterior probabilities. A state with a large Hamming distance from 7 usually has a small poste- rior probability because its structure is largely different from the true data- getta-genraatig model. Figure depicts such relationship between posterior probabilities and structural similarities among the models. Given that y the current state, Step 2 of Algorithm tends to propose a neighboring state y' with a higher posterior prob- ability, so 7/ tends to be closer to "" in Hamming distance, i.e. du(7', ?") < du(T, r*). On average, the Hamming distance be- tween a neighboring state of 7 and >" will be smaller than that between a neighboring state of with with?"" Therefore, the expected value of posterior probability of a neighboring state of y (in the denominator part in (2), shown in red in Figure 1) will be typically larger than that of a neighboring state of y (in the numerator part in (2), shown in blue in Figure 1). If we resort to the unscaled weight function wi>' (7) = π (7'',, this can cause a significantly low acceptance probability, especially when the number of trials N is large (due to the law of large numbers, the acceptance ratio converges the ratio of average posterior probabilities of the two neighborhoods); see also Appendix A.4 for a concrete example. A locally balanced weight function (4), however, is able mitigate this counterintuitive phenomenon by "scaling" the weight function with respect to the current state. We shall demonstrate the effectiveness of locally balanced weight functions in the simulation studies. Although the scope of our study is limited finite state spaces, employing (4) also improves the algorithm on continuous state spaces. We provide the relevant discussion in Appendix D.2.
167">
High E (x)
in (6)'
Low (x) in (P()
Figure 1: An illustration of the reason that the weight func- tion w(y (+) (t) may fail. Each vertical bar represents the posterior probability on the corresponding state, and thin lines connect neighboring states. The expected value of the posterior probability of the neighborhood of > (red) is typically greater than that of Y (blue).
In order for the MTM procedure to efficiently sample states from high posterior region, it is sensible to assign a larger weight to those states with a higher posterior probability in the proposal, i.e. Step 2 of Algorithm 1. To this end, we only require h to be non-decreasing. Now we introduce the main result, which states that the mixing time bound can be improved linearly in the number of trials N for our locally balanced weighting scheme.
Theorem 1. Let P PMTM denote a Markov chain induced by Algoritium I with a locally balanced weight function (4) with some non-decreasing balancing function h. Define
S(x) = (a' E (N)):: (xx))/ ) (x:) > p²'} for some constant L and 80 = maxzex (S(z)). Suppose that the following conditions hold with p 2 2 and t2, t3, t4 2 0 being some constants that satisfy t1 < t2. t3 S t1 < tt.
(5)
5

---

(i) There exists x' E (xx) such that π (x²)/T(x) 2 p'a for every x # x".
(ii) For any x E X, pts S [W(x)) S p'a.
(iii) N = o (min (ipletta-ta فا
Mipiitt-aaj 50
Then, we have the e-mixing time of PMTT
)
Emix(()) (t log
min x (x) <EEX
(6)
where A is path ensemble defined in Appendix A.3.
Remark 1. By the recent result of [53, Lemma 3] based refined path argument, we can remove the term E(A²) from (6) without changing the order of the bound.
Sketch the proof. The complete proof is deferred to Appendix A.3. The first key step of our proof is to identify suitable path ensemble A by defining function g X' - X' such that g(a)) has the highest posterior probability the neighhorhood of the state x. With x being unimodal and X being finite, repeated composition of g for any will always lead to the mode x", that is 9z x= for x # y. See Appendix A.5 for some m E N. which we utilize to construct 8* 8xx y) for any z, E X,
an toy example. The other key step is to bound the congestion parameter p((>)) defined in (3). To this end, we prove that the lower bound of the transition probability P(x, g(x)) gets closer to Ny -ts asymptotically, for any state
X )x
Condition (i) implies that the posterior distribution is unimodal with the peak at the model x=. We emphasize that the unimodality is with respect to the neighborhood relation N and is usually satisfied with some appropriate choice of a large enough neighborhood. For example, for Bayesian variable selection, it is shown in [47] that their proposed posterior may not be unimodal if a neighborhood is defined as a set of models within 1-Hamming distance, but expanding to the 2-Hamming distance neighborhood satisfies Condition (i) with 82- = 2. Similarly, the community detection problem considered in [55] and the structure learning problem in [52] satisfy (i) with some positive constant &2 by choosing appropriate N. Next, Condition (ii) states that the neighborhood size [x(x should neither be too huge nor vary much from state to state. The purpose of this condition is to control the ratio KRw( (y, KRw (z. y) in (4) that the posterior ratio π (v)/x(x) dominates the term. Last but not least, Condition (iii) implies that the number of trials N should not be arbitrarily large. This is consistent with the empirical observation of [32] that additional trials do not always result in better mixing. Condition (iii) also implies that 6o = o(p')) since N 2 1. This seems to be a strong condition, since the number of neighboring states with relatively large posterior probability with respect to the current state can be very large if we consider a state with the smallest posterior that is surrounded by states with greater posterior. Yet, it common practice to restrict the support of the prior to rule out unrealistic models by imposing some high-dimennsioal regularity assumptions, such sparsity. For example, [47] introduced the parameter of the maximum number of important covariates in variable selection, and [52] considered the maximum in -egreee and out-degree in structure learning to restrict the model space. In the same context, [55] suggested the use of a feasible set for the initial partition in the community detection problem. In this regard, we may consider X' as the restricted space so that So can be controlled. Most importantly. Condition (ii) provides key idea on how to select the number of trials N, which will be discussed in Section 3.2.
Remark 2 (Problem-specific applications). Theorem 1 can be used to prove rapid mixing of the MTM algorithm for Bayesian variable selection [47] and structure learning [52] with order N improvement of the mixing bound, given that the choice of N satisfies the condition (iii).
Remark 3 (Computational benefits). Since MTM with N trials requires calculating 2/V 1 weight functions at each iteration, improving the mixing time bound by the factor of N leads to the same overall computational complexity as the single-try MH algorithm until the convergence of the Markov chain. However, compared the single-try MH with N times longer sequential iterations, the calculation of N weight functions can be efficiently done in parallel. For example, calculating multiple weight functions can often be converted into a series of matrix multiplication problems, and optimized linear algebra libraries such as BLAS [7] can be used to exploit multiple execution units and pipe-lining. As examples, we outline parallelization strategies for the Bayesian variable selection (Section 4.1) and stochastic block model (Section 4.2) in Appendix D. Indeed, Table 1 in our simulation study results shows that MTM with moderate choice of N significantly reduces the wall-clock time until the convergence of the Markov chain.

---

3.2 Choice of the number of trials
Motivated by Condition (iii) in Theorem we propose an algorithm choose the number of trials N under a general setting applicable to high-dimensional model selection problems. For conciseness, we shall only focus on illustrating the case when we have balancing function h2))) vu and symmetric proposals (known i3 ta) so that Condition (iii) becomes N o (min (p (p(tz-t))/2 p /su) }), although the algorithm can be easily generalized to other choices of h and non-symmetric proposals.
Algorithm 2: The choice of the number of trials, when h(u) vu and known ł3 t4.
Input: An initial state zo. neighborhood N, constant vp E (0,1).
Step 1. Calculate log, (w;) (xx)) for all yy E (x J. 1....... ((xo)
Step 2. Run k-means algorithm with k=2 log-ratios (*(5)/ (((())//(m))))) (ma))) to obtain
partition, C₁ (set of small log-ratios) and C2 (set of big log-ratios).
3 Step 3. Let f2 = min C2, f = max C1 and šu = [C2|."
while -
pp//pp/aaaa/ /S0 do L Update C₁ + Ci M.. +- max C1 and so + so + 1.
Output: The number of trials N /
1 If l2 < 4. redefine C,, C2 such that & = max & La < minC, = lz. If no such C2 exists, set
& La, so 1 and I, max
Algorithm 2 is depicted in Figure 2. In Step the log probability ratio is calculated for all neighboring states of the initial state Tg. Step 2 identifies two subsets Ci and C2. corresponding to "bad moves" and "good moves" respectively. In Step 3, motivated by Condition (i), we set f2 min Cz, lower bound of log probability tios among good moves. After t2 is fixed, we first set f = max C1, &n = |C2] and gradually decrease f (so that 8n increases) until the "crossing" p(62-11)/2 2 //5/80 hap- pens. The choice of N = L(pl>////// { immediately after the crossing point approximates the worst-case scenario of
log notio
Figure 2: An illustration of Algorithm 2.
min p²a /so) }. hence providing a conservative estimate of N. We set 10 = 0.9 to match with the asymptotic dominance condition (iii).
We run Algorithm 2 only once for an initial state zo. It is based on the insight that for model selection problems. log probability ratios can often be partitioned into "bad moves" and "good moves". Although we considered any z E X') ('({²*) in Condition (i), analyzing the initial state xo not only computationally simple but also gives a good guess of t2 since as chain proceeds to the highest posterior state x², the number of good moves and the magnitude of ratios generally decreases, for example in the Bayesian variable selection problem [54]. Another possible way of using Algorithm 2 is to re-evaluate N after certain number of MCMC iterations. We note that another clustering algorithm can substituted for the k-means algorithm in Step 2.
Simulation studies
In this section, present the results for two Bayesian model selection problems, BVS and SBM. We defer the result for spatial clustering models to Appendix B.3 due to the page limit. Throughout the simulation studies, we use symmetric proposal schemes. We run single-try MH and MTM with different choices of N E (5, 10, 50, 100, 500, 1000, 2000, 5000} and four different choices of weight functions, one with (unscaled) ordinary weight function Word x:) πςy), and three with the proposed locally balanced weight functions Wegre(y (y|=) / ( Wmin(y x²) min(1, (x)) and Wmax æ) = max(1. 11 (x)) We consider the scenarios where the data-generating model x² receives the highest posterior probability to verify our main theoretical
results. Similarly to [54], two performance measures are considered: 1) H = min(! It = x²} (hitting iteration): the number of MCMC iterations until the Markov chain (æo, #1,...) hits x 2) Th (wall-clock hitting time): the wall-clock time taken until the chain hits x²
7

---

4.1 Bayesian variable selection (BVS)
Consider a high-dimensional linear model with response vector y E E and design matrix X R where the number of predictors is much larger than the sample size n. BVS seeks to find the best subset of predictors, denoted as binary vector y E {0. 1]"h described in Section 3.1, using the sparsity-inducing prior. We adopt the prior introduced by [47]:
Linear model:
y - 3, + 6, 6~ (0, Φ In)
Prior on B, and di
B 1 N (0,90= x, 1) (()) x 1/6
Sparsity prior:
7( ((7) x x17| 00110 ||>| S Smazl
where X, submatrix of X consisting of all j-th columns with 7 = 1, B, E RR is the subvector of B E I2 with nonzero coefficients, where hy - 7/-- The hyperparameters 9, and Smax control the weight of prior effect [50], sparsity strength and the maximum model size, respectively. We sample y from the posterior distribution (t> y) where other parameters By and are marginalized out; see Appendix B.1 for details. We consider the following random walk proposal:
Kaw (),,)) p (t()) (single flip)
if hy Smax.
2p [wn()) + 2)0e AN (6') (single or double flip)
if hr = 8max-
where (1) = {>/ du((; = t} and M2(()) = {y = (7 U ())){ : e 7, E 7). With 1000 and p = 5000, we consider different settings of design matrix where each row is i.i.d. sampled from æ; ~ N(O, I,) (independent) or æ; ~ N(O, Σ). Ene = exp(-li - j'l) (dependent). The response vector y is generated from y N X (( with & having only 10 nonzero entries at the first 10 coordinates:
SNR / (log p//pp/nn2 3, 2, 2, 3,,, 22,3, 22 where SNR {2, 4) a signal-to-noise ratio. For each of the four settings, we simulate 50 replicate datasets. Per each replicate, algorithms are randomly initialized with state "o such that Ny 0 and d1 ?") 20 which implies H = 20 is the minimum required hitting iteration. All hyperparameter setups, the number of MCMC iterations, and other details are deferred Appendix B.I.
2800 1000
No-ntt
Ilsrations until hit
10000
2000
1000
0092-
0012-
single try MH
MTM (N- 10) with sqrt log poste for true model
(bst
10
100
600
1000
2000
5000
5000
16000
20000
numbar of multiple trials (N)
Iterations
mothod
arthaay =
Figure 3: BVS simulation results for independent design and SNR = 4. (Left) Trace plots of unnormalized log- nog-posterior probability using single-try MH and MTM (N = 10) with square root weighting function. (Right) Boxplot of H. the number of iterations until hit, against different choices of weight function and N based on 50 replicates.
Results under independent design with SNR = are summarized in Figure 3. The trace plot shows that single-try MH reaches the true state 7- around 20,000 iterations, whereas the MTM with N = 10 reaches the true state 7 at around 2,000 iterations, smaller by a factor of 10. The boxplot confirms our findings that a larger number of trials N not always desirable, especially when using the ordinary weight function Word The proposed locally balanced weight functions using three different choices of h perform much better than Word for large N. Especially, the performance of Wmin seems to be robust to the choice of large N in the high SNR case. This can be explained by the fact that the denominator (2) is often larger in high SNR data, and the choice of min(1, (ty)/(()) limits its growth; see also Section 3. The choice of N suggested from Algorithm 2 with v = 0.9 is overall reasonable, which has a median of 349 over datasets. The detailed results for other settings available in Appendix B.I.
8

---

4.2 Stochastic block model (SBM)
SBM [20] is a popular generative model of an undirected graph which assumes a block structure of edge connection probabilities Q to describe community structure. We consider Bayesian SBM [34] by assigning prior on Q and partition z = (21..... 2pp) E {l..... K} with fixed number of blocks K, where zi indicates membership label of i-th node. The main goal is to find partition (up to
label permutation) that best describes the graph, denoted as an adjacency matrix E follow the prior of [55]:
{0, 1)XP. We
Edge appearance:
Asj Q, z
Prior on blockwise probabilities:
Que aid Beta(k1, (2), u
Prior on partition:
T(2) x E
of for all = I..... K} for some a >> O, which excludes partitions whose block sizes differ too much. We sample z from the posterior Tt A) where is marginalized out; see Appendix B.2 for details. We consider the following proposal where du is permutation-invariie Hamming distance [51]:
1(2 with restricted partition space S. {z 1 u) ok
RRw (z. z = (/(p(K - (z)) N(z)) = (z' du(z, z') = 1} (single flip).
1000, we consider two different settings of the blocks K E {2, 5} with true partition z" (1, ......... 1. 1.... ...... K) being balanced (p/ K times each) which ensures z" E Sa. In each setting of K. we generate graph from the homogencous SBM [16, 55], where Que = a if
With the number of nodes
and Quv b otherwise. We choose probability pairs (a. b) based on the Chernoff- Hellinger divergence (CH) [1] defined as CH := p(va- /b)²/ /K log for a, b x (logp). /p, which can be interpreted as a signal-to-noise ratio. Our choices are CH R 2 (weak signal) and CH R 10 (high signal), both being greater than which is necessary to satisfy posterior consistency [1, 51, 55]. For each of the the four combinations of (K, CH), we simulate 50 replicate datasets. For each replicate, algorithms are randomly initialized with state zn such that (2o, =²) 400 which implies H = 400 is the minimum required hitting iteration. All hyperparameter setups, the number of MCMC iterations, and other details are deferred Appendix B.2.
No-Hi
Illetatoon undi hi
10000
(pe0))
number multiple trials
methad
(1) diggle--yy MH ordnary
(30 square
Figure 4: (Left) An example graph generated from SBM with p 100, 2.a 0.32, and b = 0.02 so that CH x 2. Node shape (square, circle) denotes the true partition. Node color (blue, yellow) represents the initial state Zn satisfying dn z²) = 40. (Right) Boxplot of H against different weight functions and N based on 50 replicates when p = 1000, K = 2, and CH 2.
Results for K = 2 and CH & 2 are summarized in Figure 4. The boxplot of / is similar to that of Figure 3: word quickly deteriorates as N increases, but the locally balanced weight functions mostly converge with larger choice of N, although some Markov chains fail to converge due to the low CH. Especially, now the performance of Wmax or Wagrt is slightly better than wmin when N is large. This can be explained by the fact that in low signal case (CH ~ 2). there are few neighboring states that have high probability ratios. is important to eatch such states to increase the acceptance ratio (2), and the Wiin cannot do this efficiently as it is upper bounded by 1. The choice of N suggested from Algorithm with v = 0.9 has a median of over 50 datasets. The detailed simulation results for other settings are available at Appendix B.2.

---

Table Summary of Th, median wall-clock time (in seconds) until the Markov chain hit the highest posterior state, for the previous two examples using the square root weight function over 50 replicates.
N
1
5
10
50
100
500
1000
2000
5000
BVS. indep. SNR=
4
1.30
0.81
0.46
0.11
0.07
0.04
0.05
0.09
0.30
TB
SBM, K = 2, CH R 2
0.82
0.40
0.35
0.48
0.75
1.49
2.15
3.78
9.30
Finally, Table provides the summary of wall-clock hitting time Th for the previous two examples, which shows the clear computational benefit of MTM over the single-try MH thanks to the parallelism. As N increases, computation becomes more demanding compared the decreasing rate of H, so the optimal choice of N with respect to Th is often less than the minimizer of H.
Spatial clustering models and additional information. In Appendix B.3, we present simulation study results with spatial clustering models where the key findings align with those from BVS and SBM. In Appendix B.4, also analyze the behavior of MTM algorithms on multimodal target distributions. The code is available at https: // ////gtiie github........ httpchuu.ooooeeeeeeee hom/changwoo- lee/ beerapidMMM.
5 Real data applications and discussion
Real data applications. We carry out two real data application analyses to corroborate our findings beyond the scope of the simulation settings. The performance measures suggested in Section 4, the hitting iteration H and the corresponding wall-clock hitting time Th, are no longer available for real data analysis since we cannot identify the true data generating state x². Instead, we evaluate the performance based on the acceptance rate and the number of unique states visited. Both real data analyses confirm our theory: the performance deteriorates significantly as the number of trials N grows when using word, but it does not when using Waqrt, Wmin: or Wmax.
The first real data application is to find a subset of genetic variants from a genome-wine wide association study (GWAS) dataset that best explains the cup-to-disk ratio averaged over two eyes, which used to assess the risk of glaucoma. We employ BVS model described in Section 4.1, with the number of samples n 5418 and the number of gene variants p 7255 which are selected after the preliminary screening procedure described in [54, Section 6]. We tabulate the acceptance rate and the number of unique states visited along the different number of trials N, and also report the posterior inclusion probabilities of the top 10 genetic variants in Appendix C.1 and E with discussion.
The other application is to learn the underlying directed acyclic graph (DAG) model for the single-cell RNA dataset on Alzheimer's ' disease [22]. We preprocess the dataset as [10, Section 6), which yields the sample size 1666 and 73 genes, and we utilize the DAG model described in [10, Section 2.2), whose model size is equal to 73! = 4.5 x 10 We defer the performance result and other details (including the log-posterior trace plots for 4 different weight functions) to Appendix C.2.
Discussion and future work. We prove that, under some assumptions, the mixing time bound of the MTM algorithm is smaller than that of the MH algorithm by a factor of the number of trials. Motivated by the observation that popular choices of weight function can cause mixing problems, we propose locally balanced weight functions for which mixing time bound is proven. We also suggest a theoretically guided choice of N for practical use. Future research may investigate the mixing time of other generalizations of MTM such as the case with correlated weight functions. will also be of interest to extend MTM and analyze its mixing time to better handle the potential multimodality in the target distribution, by combining it with techniques such as annealing or tempering [9].
Acknowledgments and Disclosure of Funding
We thank James Cai for providing us with the processed single-cell data set on Alzheimer's dis- ease. We thank the submitters and participants of the two dbGaP studies (phs000308. vl.pl and phs000238.v 1100233.v1..pl.. 1.p1), which were funded by NIH. We thank Florian Maire, Giacomo Zanella, and Philippe Gagnon for the helpful discussion at ISBA 2022. The research of Changwoo Lee, Zhao Tang Luo, and Huiyan Sang was partially supported by NSF DMS- 145-555 and
10

---

References
[1] Emmanuel Abbe. Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research, ((1):6446-6553) 2017.
[2] David Aldous. Random walks on finite groups and rapidly mixing Markov chains. In Séminaire de Probabilités XVII 1981/82, pages 243-297. Springer, 1983.
[3] David Aldous and Persi Diaconis. Shuffling cards and stopping times. The American Mathe- matical Monthly, (3(5))3333344 1986.
[4] Dominique Bakry, Ivan Gentil, Michel Ledoux, et al. Analysis and geometry of Markov diffusion operators, volume 103. Springer, 2014.
[5] Daniel Barry and John A Hartigan. A Bayesian analysis for change point problems. Journal of the American Statistical Association, 88(421):309-33) 1993.
[6] Mylène Bédard, Randal Douc, and Eric Moulines. Scaling analysis of multiple-try MCMC methods. Stochastic Processes and their Applications, 122(3):55--786 2012.
[7] Susan Blackford, Antoine Petitet, Roldan Pozo, Karin Remington, Clint Whaley, James Demmel, Jack Dongarra, lain Duff, Sven Hammarling, Greg Henry, et al. An updated set of basic linear algebra subprograms (BLAS). ACM Transactions on Mathematical Software, (8(2):135-155) 2002.
[8] Russ Bubley and Martin Dyer. Path coupling: A technique for proving rapid mixing in Markov chains. In Proceedings 38th Annual Symposium Foundations of Computer Science, pages 223-231. IEEE, 1997.
[9] Roberto Casarin, Radu Craiu, and Fabrizio Leisen. Interacting multiple try algorithms with different proposal distributions. Statistics and Computing, 23(2):185-200 2013.
[10] Hyunwoong Chang, James Cai, and Quan Zhou. brser- structure learning without score equivalence. arXiv preprint arXiv:2202.051550 2022.
[11] Siddhartha Chib. Estimation and comparison of multiple change-point models. Journal of econometrics, 86(2):221-24) 1998.
[12] Radu V Craiu and Christiane Lemieux. Acceleration of the multiple-try Metropolis algorithm using antithetic and stratified sampling. Statistics and computing, 17(2):109-12) 2007.
[13] Persi Diaconis and Daniel Stroock. Geometric bounds for cigenvalues of Markov chains. The annals of applied probability, pages 36-61, 1991.
[14] Roland Lvovich Dobrushin, Roman Kotecký, and Senya Shlosman. Wulfs consttuctti:n:: global shape from local interaction, volume 104. American Mathematical Society Providence, 1992.
[15] Nir Friedman and Daphne Koller. Being Bayesian about network structure. A Bayesian approach to structure discovery in Bayesian networks. Machine learning, 50(1):95-125, 2003.
[16] Junxian Geng, Anirban Bhattacharya, and Debdeep Pati. Probabilistic community detection with unknown number of communities. Journal of the American Statistical Association,
114(526):893-9055 2019.
[17] Edward George and Robert E McCulloch. Approaches for Bayesian variable selection. Statistica sinica, pages 339-373, 1997.
[18] Venkatesan Guruswami. Rapidly mixing Markov chains: comparison of techniques (a survey).
arXiv preprini arXiv:1603.015 1603.01522 2016.
[19] Chris Hans, Adrian Dobra, and Mike West. Shotgun stochastic search for "large p" regression.
Journal of the American Statistical Association, 102(478):507-516 2007.
[20] Paul Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels:
First steps. Social networks, 5(2): 109-177,, 1983.
[21] Mark Jerrum. A very simple algorithm for estimating the number of k-colorings of a low-degree graph. Random Structures & Algorithms,, 7(2):157-165, 1995.
[22] Jing Jiang, Cankun Wang, Ren Qi, Hongjun Fu, and Qin Ma. scREAD: single-cell rna-seq database for alzheimer's 's disease. Iscience, 23(11):001769, 2020.
[23] Changwoo Lee, Zhao Tang Luo, and Huiyan Sang. T-LoHo: A Bayesian regularization model
for structured sparsity and smoothness on graphs. Advances Neural Information Processing Systems, 34:598-660 669, 2021.

---

[24] Sirio Legramanti, Tommaso Rigon, Daniele Durante, and David B Dunson. Extended stochas- tic block models with application to criminal networks. The Annals of Applied Statisties, 16(4):2369-2395 2022.
[25] David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017.
[26] Furong Li and Huiyan Sang. Spatial homogeneity pursuit of regression coefficients for large datasets. Journal of the American Statistical Association, 1 114(577::0500-1062, 2019.
[27] Jun S Liu, Faming Liang. and Wing Hung Wong. The multiple-try method and local optimization in Metropolis sampling. Journal of the American Statistical Association, 95(449):121-144 2000.
[28] Zhao Tang Luo, Huiyan Sang, and Bani Mallick. A Bayesian contiguous partitioning method for learning clustered latent variables. Journal of Machine Learning Research, 22(37):1-52, 2021.
[29] David Madigan, Jeremy York, and Denis Allard. Bayesian graphical models for discrete data. International Statistical Review/Revue Internationale de Statistique, pages 215-232, 1995.
[30] Luca Martino. A review of multiple try MCMC algorithms for signal processing, Digital Signal Processing, 75:134 1521134--22222 2018.
[31] Luca Martino and Victor Elvira. Metropolis sampling. Wiley StatsRef: Statistics Reference Online, pages 1-18, 2017.
[32] Luca Martino and Francisco Louzada. Issues in the multiple try Metropolis mixing. Computa- tional Statistics, 32(1):23--252, 2017.
[33] Luca Martino and Jesse Read. On the flexibility of the design of multiple try Metropolis schemes. Computational Statistics, 28(6) 2013.
[34] Nowicii and Tom A B Snijders. Estimation and prediction for stochastic blockstruc- tures. Journal of the American statistical association, 1675557 2001.
Nowicki
[35] Silvia Pandolfi, Francesco Bartolucci, and Nial Friel. A generalization of the multiple-try Metropolis algorithm for Bayesian estimation and model selection. In Proceedings of the thirteenth international conference artificial intelligence and statistics, pages 581-588.
JMLR Workshop and Conference Proceedings, 2010.
[36] Yuval Peres and Perla Sousi. Mixing times are hitting times of large sets. Journal of Theoretical Probubility, 28(2):488-519, 2015.
[37] Peter H Peskun. Optimum Monte-Cart Conte sampling using Markov chains. Biometrika, 60(3):607-
612, 1973.
[38] David Pollard and Dana Yang. Rapid mixing of a Markov chain for an exponentially weighted aggregation estimator. arXiv preprini urXiv:/909. //73, 2019.
[39] William M Rand. Objective criteria for the evaluation of clustering methods. Journal of the American Staristical association, 66(336):846 850, 1971.
[40] Dana Randall. Rapidly mixing Markov chains with applications in computer science and physics. Computing in Science & Engineering, 8(2):30 2006.
[41] Ramakrishna Rau and Joseph Fisher. Instruction-level parallel processing: History, overview, and perspective. The journal of Supercomputing, 7(1):9-50, 1993.
[42] Laurent Saloff- Lectures on finite Markov chains. Lectures on probability theory and statistics, pages 301-413, 1997.
[43] Alistair Sinclair. Improved bounds for mixing rates of Markov chains and multicommodity flow. Combinatorics, probability and Computing, 144):351-370, 1992.
[44] Michael Smith and Robert Kohn. Nonparametric regression using Bayesian variable selection. Journal of Econometrics, 75(2)317-343, 1996.
[45] Mahlet G Tadesse and Marina Vannucci. Handbook of Bayesian variable selection. CRC Press, 2021.
[46] Xiaodong Yang and Jun S Liu. Convergence rate of multiple-try Metropolis independent sampler. arXiv preprint arX5::2111.1004, 2021.
12

---

[47] Yun Yang, Martin J Wainwright, and Michael I Jordan. On the computational complexity of lige-dimensional Bayesian variable selection. The Annals of Statisties, 44(6):2997-2532, 2016.
[48] Giacomo Zanella. Informed proposals for local MCMC in discrete spaces. Journal of the American Statistical Association, 15(530))852-865, 2020.
[49] Giacomo Zanella and Gareth Roberts. Scalable importance tempering and Bayesian variable selection. Journal the Royal Statistical Society: Series B (Statistical Methodology), 81(3):489 517, 2019.
[50] Arnold Zellner. On assessing prior distributions and Bayesian regression analysis with g-prior distributions. Bayesian inference and decision techniques, 1986.
[51] Anderson Y Zhang and Harrison H Zhou. Minimax rates of community detection in stochastic block models. The Annals of Statistics, 44(5):2252-2280, 2016.
[52] Quan Zhou and Hyunwoong Chang. Complexity analysis of Bayesian learning of high- dimensional DAG models and their equivalence classes. arXiv preprint arXiv:2101.0408/ 2021.
[53] Quan Zhou and Aaron Smith. Rapid convergence of informed importance tempering. In International Conference on Artificial Intelligence and Statistics, pages 10939-10965.. PMI.,, 2022.
[54]
Quan Zhou, Jun Yang, Dootika Vats, Gareth O Roberts, and Jeffrey S Rosenthal. Dimension- free mixing for high-dimensional Bayesian variable selection. Journal of the Royal Statistical Society: Series B, to appear., 2022+.
[55] Bumeng Zhuo and Chao Gao. Mixing time of Metropolis-Hastinge for Bayesian community detection. Journal of Machine Learning Research, 22(10):1-88 2021.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 5 for the future work direction.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This work is mainly theoretical and does not present any foreseeable societal consequences.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix for all proofs.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material as URL)? [Yes]] The code is available at https: / htt//gitttt github. com/
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Please Section and Appendix B.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] See boxplots associated with simulation results.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix B for the detailed settings of the simulation results.
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [Yes]
The code is available at https : //g/ thub. com/ changwoo wareggooooeeeeaeeo Mee/rapidMTy
(d) Did you discuss whether and how consent was obtained from people whose data you're 're
using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "qz25sA4hXaL", "reviewer": "Reviewer_CaBA", "summary": "Update: I acknowledge the rebuttal and raise my score to accept given the extensive discussion and provided improvements. \n\nThe paper studies multiple try metropolis (MTM) Hastings algorithms, a class of MCMC algorithms for discrete state spaces. A theoretical bound on the mixing time is provided that shows that MTM mixes faster than standard Metropolis Hastings (MH). The results suggests a new class of weight functions that improves upon standard MTM. The results are highlighted empirically in a simulation study using synthetic data, focusing on model (variable) selection problems. \n", "questions": "Does your algorithm apply to discrete state spaces only? Could you make this more explicit, please? \nAlgorithm 2: \nDo you have to run Alg. 2 several times? This looks highly dependent on your initial state x_0 (that might be fare away from regions of high posterior probability). ", "limitations": "In my understanding, the approach applies to discrete state spaces only and the experimental results lack use of real world data and comparison with other approaches. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper provides a theoretical analysis and an extension of existing theory that looks sound. The paper is well written and motivates in detail the perspective taken. \nExperiments: \n“The trace plot shows that single-try MH reaches the true state γ∗ at around 20,000 iterations, whereas the MTM with N = 10 reaches the true state γ∗ at around 2,000 iterations, smaller by a factor of 10”. \nIt really looks as if the computation gain is achieved by only shifting computational cost from a longer chain to a shorter chain with more trials. This does not seem too convincing, in particular as parallelisation does not seem to be the main motivation for this work. \nThe experiment section is also lacking comparison with other methods (such as RJMCMC, for example) to better situate the contribution. I would have also liked to see some real data applications, that is absent from this paper. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "N4XTVNKh3ec", "reviewer": "Reviewer_x268", "summary": "The authors studied the mixing time of the MTM algorithm.\n\nThey propose a new class of weights (or a generalization of the previous weights).", "questions": "- I believe that the problem with the number of tries (`` It has been reported with empirical evidence that an increase in the number of trials N does not necessarily result in a corresponding improvement in mixing'') could be associated to the choice of the weights.\nUsing Importance Sampling (IS) weights this behavior should disappear. Please, discuss it.\n\n- If you have some results results associated to the optimal weights, please remark them.\n\n- In order to complete the state-of-the-art discuss, consider\n\nL. Martino, \"A Review of Multiple Try MCMC algorithms for Signal Processing\", Digital Signal Processing, Volume 75, Pages: 134-152, 2018.\n\nS. Pandolfi, F. Bartolucci, N.Friel, A generalization of the Multiple-try Metropolis algorithm for Bayesian estimation and model selection, Journal of Machine Learning Research (Workshop and Conference Proceedings Volume 9: AISTATS 2010) 9 (2010) 581–588\n\nand regarding the balancing functions a good reference is\n\nL. Martino, V. Elvira. \"Metropolis Sampling\", Wiley StatsRef: Statistics Reference Online, 2017.\n\n- The explanations of the models in the numerical examples are extremely synthetic.\nTry to give more information if possible.  ", "limitations": "Some parts are not easy to read (maybe less synthesis could help )  ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The analysis of the mixing time is important and the MTM scheme is a relevant algorithm.\nMoreover, the paper is well-written in my opinion.\n\nSince it is a bit mathematical work, some parts are not easy to follow. Also the numerical examples are hard to read.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "LrN1fVRyCe8", "reviewer": "Reviewer_8J7v", "summary": "EDIT: satisfied by the rebuttal and the proposed modifications by the authors, I decided to increase my grade by 1 point.\n\nThe paper studies multiple-try Metropolis for discrete state spaces, a variant of MH where one draws several times independently from the same proposal at each iteration. The main result is a bound on the mixing time, with an additional algorithmic degree of freedom (the balancing function) compared to previous work. An algorithm for selecting the number of trials in each MCMC iteration is also given. Supporting experiments are shown in two Bayesian model selection tasks.\n", "questions": "## Questions to discuss\nHere are a few points extracted from my longer list of comments below, which I suggest the authors to discuss in their rebuttal. Feel free to also challenge the identified weaknesses above.\n* L109: why consider the lazyfied version of the Markov kernel here to judge the performance of P? Do you actually recommend using P in practice?\n* Proposition 2: what does it take for pi to be the unique stationary distribution?\n* Figure 3: it seems that multiplying the number of trials by 10 decreases by 10 the number of iterations. So the gain comes from the parallelizability of MTM, right? Swapping sequential iterations for parallel ones is already interesting, but can you comment on how expensive parallelization is in your two examples (BVS and SBM)? Can you use linear algebraic tricks to further speed up parallel computation, as hinted in the text?\n\n## Comments\n* L60: at this stage of the paper, points 2 and 3 seem incompatible. Can you comment?\n* L109: why consider the lazyfied version of the Markov kernel here to judge the performance of P? Do you actually recommend using P in practice?\n* L122: this paragraph is slighlty confusing. Notions like \"configuration of path network\" are not defined. Also, from the notation L122, it is not clear whether Delta contains all paths from x to y, or is just a subset of these paths.\n* L128ff: same for this paragraph. Can you give a textbook reference for this terminology, and maybe a figure in the appendix with a simple example?\n* Theorem 1: can you give an idea of the proof? How do you build the right path-ensemble?\n* L152: what do you mean by \"applying the balancing rule\"?\n* Proposition 2: what does it take for pi to be the unique stationary distribution?\n* L138: it would help to spend one paragraph going through one example (say, a simple case of BVS) and explain how the assumptions of Proposition 2 translate in that case. \n* Section 4.1: what kernel do you use to infer other parameters, such as beta and phi? How does this impact the mixing time?\n* Figure 3: it seems that multiplying the number of trials by 10 decreases by 10 the number of iterations. So the gain comes from the parallelizability of MTM, right? Swapping sequential iterations for parallel ones is already interesting, but can you comment on how expensive parallelization is in your two examples (BVS and SBM)? Can you use linear algebraic tricks to further speed up parallel computation, as hinted in the text?\n \n## Typos\n* L10 \"improved performance over\"\n* L15 \"MCMC methods have\" or \"The MCMC method has\".\n* L30 Ising model\n* L72: I would say \"Markov kernel\" instead of \"transition probability\", but maybe this is just my habit.\n* L130 rather \"from transportation networks in graph theory\"?\n* L157 rather \"Then, the Markov kernel P_{MTM} induced by Algorithm 1 has stationary pi\". \n* L172 rather \"with number of variables p\".\n* L249 rather \"until convergence of the Markov chain\".\n* L256 rather \"the log probability ratio\"\n* L285 do you mean \"wallclock time\"?", "limitations": "Adequately addressed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, I like the paper, as it gives a thorough treatment of whether MTM improves the mixing time of MH. For a theoretical paper, it is well presented, although the text is sometimes a bit dense, and would benefit from having a running example like Bayesian variable selection, as well as a more detailed experimental section.\n\n## Strengths\n* a mixing time bound for MTM.\n* a discussion and an algorithm for automatically choosing the number of trials.\n* an honest treatment, showing that we gain in practice only if we can parallelize evaluations of the weight function.\n  \n## Weaknesses\n* lack of details in the experimental section\n* lack of comparison to other MCMC kernels for the same models, e.g. reversible-jump MCMC. However, since the main purpose of the paper is its theoretical bound and the improvement over classical MH, this is a small weakness.\n* The improvement over classical MH seems to be swapping a factor in the number of sequential iterations for the same factor of parallelizable evaluations. Thus, I would expect more to be said on how efficiently the parallelization can be implemented, and how much can be gained in a challenging application on real data (only toy models are investigated).\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept