Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: EDIT: satisfied by the rebuttal and the proposed modifications by the authors, I decided to increase my grade by 1 point.

The 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.

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.

## Strengths
* a mixing time bound for MTM.
* a discussion and an algorithm for automatically choosing the number of trials.
* an honest treatment, showing that we gain in practice only if we can parallelize evaluations of the weight function.
  
## Weaknesses
* lack of details in the experimental section
* 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.
* 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).

questions: ## Questions to discuss
Here 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.
* 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?
* Proposition 2: what does it take for pi to be the unique stationary distribution?
* 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?

## Comments
* L60: at this stage of the paper, points 2 and 3 seem incompatible. Can you comment?
* 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?
* 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.
* 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?
* Theorem 1: can you give an idea of the proof? How do you build the right path-ensemble?
* L152: what do you mean by "applying the balancing rule"?
* Proposition 2: what does it take for pi to be the unique stationary distribution?
* 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. 
* Section 4.1: what kernel do you use to infer other parameters, such as beta and phi? How does this impact the mixing time?
* 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?
 
## Typos
* L10 "improved performance over"
* L15 "MCMC methods have" or "The MCMC method has".
* L30 Ising model
* L72: I would say "Markov kernel" instead of "transition probability", but maybe this is just my habit.
* L130 rather "from transportation networks in graph theory"?
* L157 rather "Then, the Markov kernel P_{MTM} induced by Algorithm 1 has stationary pi". 
* L172 rather "with number of variables p".
* L249 rather "until convergence of the Markov chain".
* L256 rather "the log probability ratio"
* L285 do you mean "wallclock time"?
limitations: Adequately addressed.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: Update: I acknowledge the rebuttal and raise my score to accept given the extensive discussion and provided improvements. 

The 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. 

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. 
Experiments: 
“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”. 
It 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. 
The 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. 

questions: Does your algorithm apply to discrete state spaces only? Could you make this more explicit, please? 
Algorithm 2: 
Do 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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors studied the mixing time of the MTM algorithm.

They propose a new class of weights (or a generalization of the previous weights).
strengths_and_weaknesses: The analysis of the mixing time is important and the MTM scheme is a relevant algorithm.
Moreover, the paper is well-written in my opinion.

Since it is a bit mathematical work, some parts are not easy to follow. Also the numerical examples are hard to read.
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.
Using Importance Sampling (IS) weights this behavior should disappear. Please, discuss it.

- If you have some results results associated to the optimal weights, please remark them.

- In order to complete the state-of-the-art discuss, consider

L. Martino, "A Review of Multiple Try MCMC algorithms for Signal Processing", Digital Signal Processing, Volume 75, Pages: 134-152, 2018.

S. 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

and regarding the balancing functions a good reference is

L. Martino, V. Elvira. "Metropolis Sampling", Wiley StatsRef: Statistics Reference Online, 2017.

- The explanations of the models in the numerical examples are extremely synthetic.
Try to give more information if possible.  
limitations: Some parts are not easy to read (maybe less synthesis could help )
review_title: null

Meta-review: metareview: Based on the reviews and discussions, we are happy to recommend acceptance. Please make sure that all comments in the discussion threads are taken into account in the final version of the manuscript.

confidence: Certain
Decision: Accept