A spectral analytic comparison of trace-class data augmentation algorithms and their sandwich variants

Abstract

The data augmentation (DA) algorithm is a widely used Markov chain Monte Carlo algorithm that is easy to implement but often suffers from slow convergence. The sandwich algorithm is an alternative that can converge much faster while requiring roughly the same computational effort per iteration. Theoretically, the sandwich algorithm always converges at least as fast as the corresponding DA algorithm in the sense that $\Vert K^{\ast }\Vert \le \Vert K\Vert$, where $K$ and $K^{\ast }$ are the Markov operators associated with the DA and sandwich algorithms, respectively, and $\Vert \cdot \Vert$ denotes operator norm. In this paper, a substantial refinement of this operator norm inequality is developed. In particular, under regularity conditions implying that $K$ is a trace-class operator, it is shown that $K^{\ast }$ is also a positive, trace-class operator, and that the spectrum of $K^{\ast }$ dominates that of $K$ in the sense that the ordered elements of the former are all less than or equal to the corresponding elements of the latter. Furthermore, if the sandwich algorithm is constructed using a group action, as described by Liu and Wu [J. Amer. Statist. Assoc. 94 (1999) 1264--1274] and Hobert and Marchev [Ann. Statist. 36 (2008) 532--554], then there is strict inequality between at least one pair of eigenvalues. These results are applied to a new DA algorithm for Bayesian quantile regression introduced by Kozumi and Kobayashi [J. Stat. Comput. Simul. 81 (2011) 1565--1578].

Published in at http://dx.doi.org/10.1214/11-AOS916 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (2)

• A theoretical comparison of the data augmentation, marginal augmentation and PX-DA algorithms
• Improving the Convergence Properties of the Data Augmentation Algorithm with an Application to Bayesian Mixture Modeling

Cited by in corpus (11)

• Convergence analysis of the Gibbs sampler for Bayesian general linear mixed models with improper priors
• Convergence properties of Gibbs samplers for Bayesian probit regression with proper priors
• Comparison of Markov chains via weak Poincaré inequalities with application to pseudo-marginal MCMC
• BAMBI: An R package for Fitting Bivariate Angular Mixture Models
• Convergence analysis of block Gibbs samplers for Bayesian linear mixed models with $p>N$
• Consistent estimation of the spectrum of trace class data augmentation algorithms
• Scalable Bayesian shrinkage and uncertainty quantification in high-dimensional regression
• Estimating the spectral gap of a trace-class Markov operator
• Convergence Analysis of the Data Augmentation Algorithm for Bayesian Linear Regression with Non-Gaussian Errors
• Trace-class Monte Carlo Markov Chains for Bayesian Multivariate Linear Regression with Non-Gaussian Errors
• Fast Markov chain Monte Carlo for high dimensional Bayesian regression models with shrinkage priors