Response Letter for “Convergence Rate of Multiple-Try Metropolis Independent Sampler”

“My main concern about the paper is that the convergence results provided in the paper is very implicit. In particular, practitioners are often interested in how the convergence rates scale with the complexities of the posterior and the space. For instance, in continuous spaces, one often wonders the dependence of the convergence rates on the dimension of the space, the smoothness of the log posterior, and the convexity or other intrinsic property of the posterior such as the concentration or isoperimetry properties. In discrete spaces, one often considers the dependence on the number of states and similarly the isoperimetric constants of the posterior distribution. The characterization provided in the current paper does not illustrate the scaling of the convergence rates with respect to the complexities of the posterior and the space.

Because of the implicit nature of the convergence rates being provided, some of the claims in the paper are not definitive. For example, the claim that ‘the Multiple-Try Metropolis strategy is most helpful in help jumping among multiple modes of the target distribution’ is not clear from the discussion of the paper. Instead we only know that the independent Multiple-Try Metropolis samplers are not as efficient as their vanilla Metropolis counterparts with the corresponding amount of thinning.”

Response: Thank you very much for your very insightful and also ambitious comments. We agree that those properties you mentioned of an MCMC algorithm are highly valuable and desirable. Unfortunately, for most practically used algorithms in real applications such results are very scarce. We also would like to argue respectfully that, since the IMH and MTM-IS algorithms are not as flexible and general as the Metropolis-Hastings or Gibbs sampling algorithms, our explicit expressions of the convergence rates for IMH and MTM-IS algorithms are equally helpful for practitioners. For example, our rate results suggest explicitly that one needs to choose a fatter-tailed (but not overly fat) sampling distribution than the target one. In contrast, some published rates results on general MCMC often involve unknown constants and unrealistic and unverifiable assumptions on the target distribution, which cannot be used directly by practitioners. Furthermore, the efficiency of a MCMC sampler can also highly depend on parameterizations as recently revealed in the work of zanella2021multilevel, which cannot be reflected well by those dimension-related rate results.

We are fortunate to have been dealing with a much simpler setting in this paper: independence sampler. As shown in liu1996metropolized and here, the convergence rate of the IMH and MTM-IS are precisely related to the importance weight in importance sampling and are largely affected by how the proposal distribution matches the target one, especially in the tail part. For example, if our proposal distribution $p$ perfectly matches the target distribution, the IMH converges in one step regardless of the dimension! But this is not the case for a standard MCMC algorithm. We also know trivially that a generic importance sampling algorithm (and also IMH and MTM-IS) scales badly (exponentially) with dimension. Thus, there seems to be no unambiguous and non-trivial formulation of the dimension-scaling property for an importance sampling or IMH/MTM-IS algorithm. A key for making these algorithms practically useful for high-dimensional problems is to design the sampling distribution carefully in a problem-specific way, such as the sequential importance sampler for 0-1 tables (chen2005sequential) and sequential Monte Carlo methods for dynamic systems (doucet2001sequential). However, once we start changing both dimension of the target and the sampling distribution in a case-specific way, the question of how convergence rate of an IMH algorithm scales with dimension is no longer valid. Indeed, as shown in much work related to sequential Monte Carlo including our own, there is a huge difference between a nicely designed importance sampler versus a naive one. In our current work since the proposal is not specified exactly, our convergence results do not address the complexities of such sampling problems.

One may argue, which we agree, that for fixed classes of target and proposal distributions, it is useful and possible to get some results on how convergence rates scale with dimensions. Motivated by your comments, we investigate a case (Section 4.2) where the target is a Gaussian mixture, but we are only allowed to use a $N(0,\sigma^{2}I_{p})$ as the sampling distribution. In this case, the convergence rate indeed scales exponentially bad even if we optimize $\sigma$. We also rearranged Section 5 added Subsection 5.1 with a new proposition to show how MTM can help in real molecular simulation applications.

“In the framework proposed within the paper, one can perhaps try to provide inequalities of the form: $1-H_{k_{1}}(w^{\ast})\leq(1-\frac{1}{w^{\ast}})^{k_{2}}$ where in different cases, ratios between $k_{1}$ and $k_{2}$ are different. For example, for a multi-modal distribution, $k_{1}/k_{2}$ in the above inequality may be much smaller than that for a strongly log-concave distribution. In discrete space, one can design a distribution that is only supported on a graph with one single vertex connecting two subgraphs. By changing the probability mass of this vertex, one can discuss similarly quantify how “multimodal” the distribution is.”

Response: When $k\geq 2$, function $H_{k}$ involves the computation of the integral of a complicated function over the proposal distribution $p$, which is often analytically intractable. So we only perform numerical illustrations instead. Readers can find pairs of $(k_{1},k_{2})$ by drawing horizontal lines at different levels in our plots from Section 4.

We feel that plainly letting $k_{1}\neq k_{2}$ may not lead to useful findings since we believe that one should compare convergence performances of two algorithms based on the same (or nearly same) computational budget. However, if one allows the algorithm to take advantage of parallel computing infrastructures, it can add another interesting dimension for the problem and make the suggested comparison meaningful.

Inspired by your comment, we added Section 5.1 to illustrate how MTM may help in a partial MTM framework adopted in the molecular simulation literature. This partial MTM-IS spiritually resembles a case with $k_{1}=1$ and $k_{2}\gg k_{1}$ for a low-cost part of the whole distribution.

“More effort is need for this work to be able to provide richer insights for practitioners. I believe that an inequality of the form: $1-H_{k_{1}}(w^{\ast})\leq(1-\frac{1}{w^{\ast}})^{k_{2}}$ can be achieved for a special class of posterior (and proposal distributions). The explicit dependence on dimension etc. may be difficult to achieve within the current framework. In such case, I suggest performing a comprehensive experiment for a class of distributions (Gaussian e.g.) with different dimensions and conditioning. Such results will do a much greater service to the readers of the paper.”

Response: Thanks for your constructive comments and suggestion. We have now included a comprehensive numerical study on multivariate Gaussian and Gaussian mixtures (Section 4) so as to gain more insights on the dimension-dependency of the convergence rates of IMH and MTM-IS, which provides useful guidance to practitioners.