skip to main content

This content will become publicly available on August 1, 2024

Title: Convergence rate of multiple-try Metropolis independent sampler
Abstract The multiple-try Metropolis method is an interesting extension of the classical Metropolis–Hastings algorithm. However, theoretical understanding about its usefulness and convergence behavior is still lacking. We here derive the exact convergence rate for the multiple-try Metropolis Independent sampler (MTM-IS) via an explicit eigen analysis. As a by-product, we prove that an naive application of the MTM-IS is less efficient than using the simpler approach of “thinned” independent Metropolis–Hastings method at the same computational cost. We further explore more variants and find it possible to design more efficient algorithms by applying MTM to part of the target distribution or creating correlated multiple trials.  more » « less
Award ID(s):
1903139 2015411
Author(s) / Creator(s):
Date Published:
Journal Name:
Statistics and Computing
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ABSTRACT We introduce Bilby-MCMC, a Markov chain Monte Carlo sampling algorithm tuned for the analysis of gravitational waves from merging compact objects. Bilby-MCMC provides a parallel-tempered ensemble Metropolis-Hastings sampler with access to a block-updating proposal library including problem-specific and machine learning proposals. We demonstrate that learning proposals can produce over a 10-fold improvement in efficiency by reducing the autocorrelation time. Using a variety of standard and problem-specific tests, we validate the ability of the Bilby-MCMC sampler to produce independent posterior samples and estimate the Bayesian evidence. Compared to the widely used Dynesty nested sampling algorithm, Bilby-MCMC is less efficient in producing independent posterior samples and less accurate in its estimation of the evidence. However, we find that posterior samples drawn from the Bilby-MCMC sampler are more robust: never failing to pass our validation tests. Meanwhile, the Dynesty sampler fails the difficult-to-sample Rosenbrock likelihood test, over constraining the posterior. For CBC problems, this highlights the importance of cross-sampler comparisons to ensure results are robust to sampling error. Finally, Bilby-MCMC can be embarrassingly and asynchronously parallelized making it highly suitable for reducing the analysis wall-time using a High Throughput Computing environment. Bilby-MCMC may be a useful tool for the rapid and robust analysis of gravitational-wave signals during the advanced detector era and we expect it to have utility throughout astrophysics. 
    more » « less
  2. Abstract

    We recently extended our Parker-type transport equation for energetic particle interaction with numerous dynamic small-scale magnetic flux ropes (SMFRs) to include perpendicular diffusion in addition to parallel diffusion. We present a new analytical solution to this equation assuming heliocentric spherical geometry with spherical symmetry for all SMFR acceleration mechanisms present in the transport theory. With the goal of identifying the dominant mechanism(s) through which particles are accelerated by SMFRs, a search was launched to identify events behind interplanetary shocks that could be explained by our new solution and not classical diffusive shock acceleration. Two new SMFR acceleration events were identified in situ for the first time within heliocentric distances of 1 astronomical unit (au) in Helios A data. A Metropolis–Hastings algorithm is employed to fit the new solution to the energetic proton fluxes so that the relative strength of the transport coefficients associated with each SMFR acceleration mechanism can be determined. We conclude that the second-order Fermi mechanism for particle acceleration by SMFRs is more important than first-order Fermi acceleration due to the mean compression of the SMFRs regions during these new events. Furthermore, with the aid of SMFR parameters determined via the Grad–Shafranov reconstruction method, we find that second-order Fermi SMFR acceleration is dominated by the turbulent motional electric field parallel to the guide/background field. Finally, successful reproduction of energetic proton flux data during these SMFR acceleration events also required efficient particle escape from the SMFR acceleration regions.

    more » « less
  3. Many Markov Chain Monte Carlo (MCMC) methods leverage gradient information of the potential function of target distribution to explore sample space efficiently. However, computing gradients can often be computationally expensive for large scale applications, such as those in contemporary machine learning. Stochastic Gradient (SG-)MCMC methods approximate gradients by stochastic ones, commonly via uniformly subsampled data points, and achieve improved computational efficiency, however at the price of introducing sampling error. We propose a non-uniform subsampling scheme to improve the sampling accuracy. The proposed exponentially weighted stochastic gradient (EWSG) is designed so that a non-uniform-SG-MCMC method mimics the statistical behavior of a batch-gradient-MCMC method, and hence the inaccuracy due to SG approximation is reduced. EWSG differs from classical variance reduction (VR) techniques as it focuses on the entire distribution instead of just the variance; nevertheless, its reduced local variance is also proved. EWSG can also be viewed as an extension of the importance sampling idea, successful for stochastic-gradient-based optimizations, to sampling tasks. In our practical implementation of EWSG, the non-uniform subsampling is performed efficiently via a Metropolis-Hastings chain on the data index, which is coupled to the MCMC algorithm. Numerical experiments are provided, not only to demonstrate EWSG's effectiveness, but also to guide hyperparameter choices, and validate our non-asymptotic global error bound despite of approximations in the implementation. Notably, while statistical accuracy is improved, convergence speed can be comparable to the uniform version, which renders EWSG a practical alternative to VR (but EWSG and VR can be combined too).

    more » « less
  4. Abstract Summary

    Biological models contain many parameters whose values are difficult to measure directly via experimentation and therefore require calibration against experimental data. Markov chain Monte Carlo (MCMC) methods are suitable to estimate multivariate posterior model parameter distributions, but these methods may exhibit slow or premature convergence in high-dimensional search spaces. Here, we present PyDREAM, a Python implementation of the (Multiple-Try) Differential Evolution Adaptive Metropolis [DREAM(ZS)] algorithm developed by Vrugt and ter Braak (2008) and Laloy and Vrugt (2012). PyDREAM achieves excellent performance for complex, parameter-rich models and takes full advantage of distributed computing resources, facilitating parameter inference and uncertainty estimation of CPU-intensive biological models.

    Availability and implementation

    PyDREAM is freely available under the GNU GPLv3 license from the Lopez lab GitHub repository at

    Supplementary information

    Supplementary data are available at Bioinformatics online.

    more » « less
  5. Abstract Motivation

    A large proportion of risk regions identified by genome-wide association studies (GWAS) are shared across multiple diseases and traits. Understanding whether this clustering is due to sharing of causal variants or chance colocalization can provide insights into shared etiology of complex traits and diseases.


    In this work, we propose a flexible, unifying framework to quantify the overlap between a pair of traits called UNITY (Unifying Non-Infinitesimal Trait analYsis). We formulate a Bayesian generative model that relates the overlap between pairs of traits to GWAS summary statistic data under a non-infinitesimal genetic architecture underlying each trait. We propose a Metropolis–Hastings sampler to compute the posterior density of the genetic overlap parameters in this model. We validate our method through comprehensive simulations and analyze summary statistics from height and body mass index GWAS to show that it produces estimates consistent with the known genetic makeup of both traits.

    Availability and implementation

    The UNITY software is made freely available to the research community at:

    Supplementary information

    Supplementary data are available at Bioinformatics online.

    more » « less