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

Given a joint probability density \(f(x,y)\) with respect to measure \(\mu\times \nu\) on the set \(X \times Y\), the data augmentation (DA) algorithm is a Markov chain Monte Carlo technique which is used to explore the marginal probability density \(f_X(x)= \int_Y f(x,y) \nu(dy)\). The Markov chain underlying the algorithm, denoted by \(\{X_n\}_{n=0}^\infty\), is the following. If \(X_n=x\), then \(X_{n+1}\) is simulated in two steps: draw \(Y \sim f_{Y|X}(\cdot|x)\), call the result \(y\), and then draw \(X_{n+1} \sim f_{X|Y}(\cdot|y)\). Although DA is easy to implement it often suffers from slow convergence. The sandwich algorithm is an alternative to DA. Given the same conditions and \(X_n^*=x\), each iteration of the sandwich algorithm is simulated in three steps (one additional step is ``sandwiched'' between two original steps): draw \(Y \sim f_{Y|X}(\cdot|x)\), call the result \(y\), draw \(Y' \sim R(y,\cdot)\), call the result \(y'\), and then draw \(X_{n+1}^* \sim f_{X|Y}(\cdot|y')\). Here, \(R(y,dy')\) is any Markov transition function reversible with respect to \(f_Y(y)\nu(dy)\). If \(R(y,dy')\) is properly chosen, the sandwich algorithm \(\{X_n^*\}_{n=0}^\infty\) can converge much faster than DA while requiring roughly the same computational effort per iteration. Empirical studies pointing to the superiority of the sandwich algorithm abound. The development of confirmatory theoretical results has been slow. It is known that sandwich algorithm always converges at least as fast as the corresponding DA algorithm in the sense that \(\|K^*\| \leq \|K\|\), where \(K\) and \(K^*\) are the Markov operators associated with the DA and sandwich algorithms, respectively, and \(\| \cdot \|\) denotes the operator norm. In this paper, a substantial refinement of this operator norm inequality is developed. Results are applied to a new DA algorithm for Bayesian quantile regression introduced by \textit{H. Kozumi} and \textit{G. Kobayashi} [``Gibbs sampling methods for Bayesian quantile regression'', J. Stat. Comput. Simul. 81, No. 11, 1565--1578 (2011; \url{doi:10.1080/00949655.2010.496117})].