Wasserstein-based methods for convergence complexity analysis of MCMC with application to Albert and Chib's algorithm
share
Over the last 25 years, techniques based on drift and minorization (d&m) have been mainstays in the convergence analysis of MCMC algorithms. However, results presented herein suggest that d&m may be less useful in the emerging area of convergence complexity analysis, which is the study of how Monte Carlo Markov chain convergence behavior scales with sample size, n, and/or number of covariates, p. The problem appears to be that minorization becomes a serious liability as dimension increases. Alternative methods of constructing convergence rate bounds (with respect to total variation distance) that do not require minorization are investigated. These methods incorporate both old and new theory on Wasserstein distance and random mappings, and produce bounds that are apparently more robust to increasing dimension than those based on d&m. Indeed, the Wasserstein-based bounds are used to develop strong convergence complexity results for Albert and Chib's (1993) algorithm in the challenging asymptotic regime where both n and p diverge. We note that Qin and Hobert's (2019) d&m-based analysis of the same algorithm led to useful results in the cases where n →∞ with p fixed, and p →∞ with n fixed, but these authors provided no results for the case where n and p are both large.
READ FULL TEXT