More Like this

1. Convergence speed and approximation accuracy of numerical MCMC

   https://doi.org/10.1017/apr.2024.28  

   Cui, Tiangang; Dong, Jing; Jasra, Ajay; Tong, Xin T (March 2025, Advances in Applied Probability)

   Abstract When implementing Markov Chain Monte Carlo (MCMC) algorithms, perturbation caused by numerical errors is sometimes inevitable. This paper studies how the perturbation of MCMC affects the convergence speed and approximation accuracy. Our results show that when the original Markov chain converges to stationarity fast enough and the perturbed transition kernel is a good approximation to the original transition kernel, the corresponding perturbed sampler has fast convergence speed and high approximation accuracy as well. Our convergence analysis is conducted under either the Wasserstein metric or the$$\chi^2$$metric, both are widely used in the literature. The results can be extended to obtain non-asymptotic error bounds for MCMC estimators. We demonstrate how to apply our convergence and approximation results to the analysis of specific sampling algorithms, including Random walk Metropolis, Metropolis adjusted Langevin algorithm with perturbed target densities, and parallel tempering Monte Carlo with perturbed densities. Finally, we present some simple numerical examples to verify our theoretical claims. 

   more » « less
2. Mixing time for Markov chain on linear extensions

   Rhodes, John; Schilling, Anne (January 2021, Séminaire lotharingien de combinatoire)

   We provide a general framework for computing mixing times of finite Markov chains when its minimal ideal is left zero. Our analysis is based on combining results by Brown and Diaconis with our previous work on stationary distributions of finite Markov chains. We introduce a new Markov chain on linear extensions of a poset with n vertices, which is a variant of the promotion Markov chain of Ayyer, Klee and the last author, and show that it has a mixing time O(n log n). 

   more » « less
3. Mixing time for Markov chain on linear extensions

   Rhodes, John; Schilling, Anne (January 2021, Seminaire lotharingien de combinatoire)

   We provide a general framework for computing mixing times of finite Markov chains when its minimal ideal is left zero. Our analysis is based on combining results by Brown and Diaconis with our previous work on stationary distributions of finite Markov chains. We introduce a new Markov chain on linear extensions of a poset with n vertices, which is a variant of the promotion Markov chain of Ayyer, Klee and the last author, and show that it has a mixing time O(n log n). 

   more » « less
4. PAC-Bayes Bounds on Variational Tempered Posteriors for Markov Models

   https://doi.org/10.3390/e23030313  

   Banerjee, Imon; Rao, Vinayak; Honnappa, Harsha (March 2021, Entropy)

   Alquier, Pierre (Ed.)

   Datasets displaying temporal dependencies abound in science and engineering applications, with Markov models representing a simplified and popular view of the temporal dependence structure. In this paper, we consider Bayesian settings that place prior distributions over the parameters of the transition kernel of a Markov model, and seek to characterize the resulting, typically intractable, posterior distributions. We present a Probably Approximately Correct (PAC)-Bayesian analysis of variational Bayes (VB) approximations to tempered Bayesian posterior distributions, bounding the model risk of the VB approximations. Tempered posteriors are known to be robust to model misspecification, and their variational approximations do not suffer the usual problems of over confident approximations. Our results tie the risk bounds to the mixing and ergodic properties of the Markov data generating model. We illustrate the PAC-Bayes bounds through a number of example Markov models, and also consider the situation where the Markov model is misspecified. 

   more » « less
5. On the Computational Complexity of Metropolis-Adjusted Langevin Algorithms for Bayesian Posterior Sampling

   Tang, Rong; Yang, Yun (April 2024, Journal of machine learning research)

   In this paper, we examine the computational complexity of sampling from a Bayesian posterior (or pseudo-posterior) using the Metropolis-adjusted Langevin algorithm (MALA). MALA first employs a discrete-time Langevin SDE to propose a new state, and then adjusts the proposed state using Metropolis-Hastings rejection. Most existing theoretical analyses of MALA rely on the smoothness and strong log-concavity properties of the target distribution, which are often lacking in practical Bayesian problems. Our analysis hinges on statistical large sample theory, which constrains the deviation of the Bayesian posterior from being smooth and log-concave in a very specific way. In particular, we introduce a new technique for bounding the mixing time of a Markov chain with a continuous state space via the s-conductance profile, offering improvements over existing techniques in several aspects. By employing this new technique, we establish the optimal parameter dimension dependence of d^1/3 and condition number dependence of κ in the non-asymptotic mixing time upper bound for MALA after the burn-in period, under a standard Bayesian setting where the target posterior distribution is close to a d-dimensional Gaussian distribution with a covariance matrix having a condition number κ. We also prove a matching mixing time lower bound for sampling from a multivariate Gaussian via MALA to complement the upper bound. 

   more » « less