# Lower Bounds on the Rate of Convergence for Accept-Reject-Based Markov
Chains

Austin Brown and Galin L. Jones Department of Statistics, University of
Warwick, email<EMAIL_ADDRESS>of Statistics, University
of Minnesota, email<EMAIL_ADDRESS>
###### Abstract

To avoid poor empirical performance in Metropolis-Hastings and other accept-
reject-based algorithms practitioners often tune them by trial and error.
Lower bounds on the convergence rate are developed in both total variation and
Wasserstein distances in order to identify how the simulations will fail so
these settings can be avoided, providing guidance on tuning. Particular
attention is paid to using the lower bounds to study the convergence
complexity of accept-reject-based Markov chains and to constrain the rate of
convergence for geometrically ergodic Markov chains.

The theory is applied in several settings. For example, if the target density
concentrates with a parameter $n$ (e.g. posterior concentration, Laplace
approximations), it is demonstrated that the convergence rate of a Metropolis-
Hastings chain can tend to $1$ exponentially fast if the tuning parameters do
not depend carefully on $n$. This is demonstrated with Bayesian logistic
regression with Zellner’s g-prior when the dimension and sample increase in
such a way that size $d/n\to\gamma\in(0,1)$ and flat prior Bayesian logistic
regression as $n\to\infty$.

##  1 Introduction

Metropolis-Hastings algorithms [23, 35, 56] are foundational to the use of
Markov chain Monte Carlo (MCMC) methods in statistical applications [10].
Metropolis-Hastings requires the choice of a proposal distribution and this
choice is crucial to the efficacy of the resulting sampling algorithm. The
choice of tuning parameters for the proposal distribution prompted ground-
breaking research into optimal scaling [48] and adaptive MCMC methods [20].
Nevertheless, in many applications this remains a difficult task and is often
accomplished by trial and error. A significant goal here is to provide further
guidance on this task, especially in high-dimensional settings.

Metropolis-Hastings Markov chains are an instance of accept-reject-based (ARB)
Markov chains, which require a proposal distribution and either accept or
reject a proposal at each step. While Metropolis-Hastings chains are the most
widely used and studied ARB chains, others are of practical importance or
theoretical interest. This includes, among others, non-reversible Metropolis-
Hastings [8], Barker’s algorithm [6], portkey Barker’s algorithm [60], and the
Lazy-Metropolis-Hastings algorithm [32]. The main difference between varieties
of ARB chains is the definition of the acceptance probability, but the choice
of a proposal remains crucial for the efficacy of the associated sampling
algorithm. Indeed, there has been recent interest in the optimal scaling
problem for more general ARB chains [1].

Under standard regularity conditions, ARB chains converge to their target
distribution and thus will eventually produce a representative sample from it.
If the proposal is not well chosen, then this convergence can take
prohibitively long. In fact, one goal is to provide a general tool for
identifying when an ARB chain will fail to produce a representative sample
within any reasonable amount of time. This is achieved by developing novel
lower bounds on the convergence rate. These lower bounds have wide application
to aid in choosing proposal distributions and tuning parameters to avoid poor
convergence behavior.

General lower bounds on the convergence rate have not been previously
investigated for ARB chains outside of some Metropolis-Hastings independence
samplers [11, 45, 64]. Others have instead focused on upper bounding the
spectral gap using the conductance [2, 9, 22, 25, 26, 33, 52, 66, 67]. An
upper bound on the spectral gap lower bounds the convergence rate but requires
a reversible Markov chain [18, 33], which is not assumed in the development of
the general lower bounds below.

Most commonly, the convergence of ARB chains has been measured with total
variation [51, 55]. However, recently, the Wasserstein distances [30, 62, 63]
from optimal transportation have been used in the convergence analysis of
high-dimensional MCMC algorithms [13, 14, 22, 40, 41]. The interest in
Wasserstein distances mainly is due to the observation that Wasserstein
distances may enjoy improved scaling properties in high dimensions compared to
the total variation distance. The new lower bounds are similar whether total
variation or a Wasserstein distance is used, but the conditions required for
lower bounding the Wasserstein distances are slightly stronger than those for
total variation. In particular, the Wasserstein lower bounds show when the
chain has poor convergence properties in total variation, then it will often
do so in Wasserstein distances.

Convergence rate analysis of MCMC chains on general state spaces largely has
centered on establishing upper bounds on the convergence rate [27, 51] or,
failing that, in establishing qualitative properties such as geometric
ergodicity, which ensures an exponential convergence rate to the target
distribution in either total variation or Wasserstein distances [21, 28, 36,
51, 55]. There has been important work establishing geometric ergodicity for
Metropolis-Hastings chains [e.g. 24, 34, 47], but, even though there is some
recent work for a specific random-walk Metropolis-Hastings chain [3], it has
not yet produced much understanding of their quantitative rates of
convergence. The lower bounds developed here allow the exponential rate of
convergence to be bounded below and hence, in conjunction with the existing
approaches, will help provide a clearer picture of the quantitative
convergence properties of geometrically ergodic ARB chains.

Convergence complexity of MCMC algorithms with respect to the dimension $d$
and sample size $n$ has been of significant recent interest [7, 11, 15, 26,
40, 41, 68, 69, 71]. Lower bounds can be used to study conditions on the
tuning parameters which imply the convergence rate rapidly tends to $1$ with
the dimension $d$ and sample size $n$ even in the setting where the chain is
geometrically ergodic for fixed $d$ and $n$. This can then be used to choose
the scaling so that the poor high-dimensional convergence properties might be
avoided. One implication of the theory developed below is that the scaling
should be chosen explicitly as a function of both $n$ and $d$, with the
details dependent upon the setting, since if they are chosen otherwise, the
resulting ARB chain can have poor convergence properties. In comparison,
optimal scaling results are derived in the setting where the dimension
$d\to\infty$, but the explicit scaling dependence on $n$ is often infeasible
to compute.

Throughout, the theory is illustrated with straightforward examples, some of
which concern ARB chains that are not versions of Metropolis-Hastings.
However, several significant, practically relevant applications of Metropolis-
Hastings are also studied. One application concerns a class of Metropolis-
Hastings algorithms using a general Gaussian proposal which in special cases
is the proposal used in independence samplers, random-walk Metropolis-Hastings
(RWMH) [55], Metropolis-adjusted Langevin algorithm (MALA) [43, 46], and other
variants such as Riemannian manifold MALA [19].

The lower bounds are also studied for random walk Metropolis-Hastings
algorithm with log-concave target densities. In particular, an application to
RWMH for Bayesian logistic with Zellner’s g-prior is studied as
$d,n\to\infty$. In this example, the convergence rate can tend to $1$
exponentially fast if the scaling does not depend carefully on $d$ and $n$.
More general target densities are studied under conditions which imply they
concentrate towards their maximum point with $n$ (e.g. Bayesian posterior
concentration, Laplace approximations) as $d,n\to\infty$. Once again, if the
tuning parameters do not depend on $n$, the convergence rate can tend to $1$
rapidly as $d,n\to\infty$. As an application of the general result, flat prior
Bayesian logistic regression is studied as only $n\to\infty$.

The remainder is organized as follows. Section 2 provides a formal definition
of ARB Markov chains and some relevant background. Total variation lower
bounds are studied in Section 3, including a comparison with conductance
methods. Applications of the theoretical results are considered in Section 4.
Then Section 5 presents lower bounds in Wasserstein distances. Final remarks
are given in Section 6. Most proofs are deferred to the appendices.

##  2 Accept-reject-based Markov chains

Let $\Omega$ be a nonempty measurable space and $\mathcal{B}(\Omega)$ the
Borel sigma algebra on $\Omega$. Suppose $\Pi$ is a probability measure on
$(\Omega,\mathcal{B}(\Omega))$ supported on a nonempty measurable set
$\Theta\subseteq\Omega$ with density $\pi$ with respect to a sigma-finite
measure $\lambda$ on $(\Omega,\mathcal{B}(\Omega))$. The support of $\pi$ is
$\Theta$ so for each $\theta\in\Theta$, $\pi(\theta)>0$. Assume for each
$\theta\in\Theta$, $\lambda(\\{\theta\\})=0$ and $\lambda$ is strictly
positive (e.g., Lebesgue measure) meaning for nonempty, measurable open sets
$U\subseteq\Theta$, $\lambda(U)>0$. While this general setting will suffice
for most of the work, at various points more specific assumptions on $\Omega$
will be required.

For each $\theta\in\Omega$, suppose that $Q(\theta,\cdot)$ is a proposal
distribution on $(\Omega,\mathcal{B}(\Omega))$ having density
$q(\theta,\cdot)$ with respect to $\lambda$. If
$a:\Omega\times\Omega\to[0,1]$, define the acceptance probability by

$A(\theta)=\int
a(\theta,\theta^{\prime})q(\theta,\theta^{\prime})d\lambda(\theta^{\prime}).$

Let $\delta_{x}$ denote the Dirac measure at the point $x$. The accept-reject-
based Markov kernel $P$ is defined on $(\Omega,\mathcal{B}(\Omega))$ for
$\theta\in\Omega$ and measurable sets $B\subseteq\Omega$ as

$P(\theta,B)=\int_{B}a(\theta,\theta^{\prime})q(\theta,\theta^{\prime})d\lambda(\theta^{\prime})+\delta_{\theta}(B)[1-A(\theta)].$

Let $\mathbb{Z}_{+}$ denote the set of positive integers. The Markov kernel
for iteration time $t\in\mathbb{Z}_{+}$ with $t\geq 2$ is defined recursively
by

$P^{t}(\theta,\cdot)=\int P^{t-1}(\cdot,\cdot)dP(\theta,\cdot)$

where $P\equiv P^{1}$.

It is assumed that $a$ is such that $\Pi$ is invariant for $P$. Invariance is
often ensured through a detailed balance (i.e., reversibility) condition, but
this is not required in general. For example, detailed balance does not hold
for non-reversible Metropolis-Hastings yet $\Pi$ is invariant [8]. Of course,
detailed balance holds for Metropolis-Hastings (MH) where

$a_{MH}(\theta,\theta^{\prime})=\begin{cases}\frac{\pi(\theta^{\prime})q(\theta^{\prime},\theta)}{\pi(\theta)q(\theta,\theta^{\prime})}\wedge
1,\text{ if }\pi(\theta)q(\theta,\theta^{\prime})>0\\\ 1,\hskip
56.9055pt\text{ if }\pi(\theta)q(\theta,\theta^{\prime})=0.\end{cases}$ (1)

Define the total variation distance between probability measures $\mu,\nu$ on
$(\Omega,\mathcal{B}(\Omega))$ by
$\left\lVert\mu-\nu\right\rVert_{\text{TV}}=\sup_{f\in\mathcal{M}_{1}}\left[\int
fd\mu-\int fd\nu\right]$ where $\mathcal{M}_{1}$ is the set of Borel
measurable functions $f:\Omega\to[0,1]$. It is well-known that if $P$ is
$\Pi$-irreducible, aperiodic, and Harris recurrent, the ARB Markov chain
converges in total variation, as $t\to\infty$, to the invariant distribution
[55, 56] and hence will eventually produce a representative sample from $\Pi$.
Section 3 considers measuring this convergence with the total variation norm,
while Section 5 considers doing so with Wasserstein distances from optimal
transportation.

##  3 Total variation lower bounds

###  3.1 Lower bounds

Previously, a lower bound in the total variation distance was shown for the
Metropolis-Hastings independence sampler [64, Lemma 1]. A similar argument
provides a lower bound for general ARB chains.

######  Theorem 1.

For every $t\in\mathbb{Z}_{+}$ and every $\theta\in\Theta$,

$\left\lVert
P^{t}(\theta,\cdot)-\Pi\right\rVert_{\text{TV}}\geq\left[1-A(\theta)\right]^{t}.$

Although it has been suppressed here, $A(\theta)$ often depends on the sample
size $n$ and the dimension $d$; for example, consider the setting where $\pi$
is a Bayesian posterior density. If $A(\theta)\to 0$ as $n\to\infty$ or
$d\to\infty$, then the total variation lower bound will approach 1 and the ARB
Markov chain will be ineffective in that regime. However, once this has been
identified, the proposal can often be chosen so as to avoid the difficulties.

Of course, $A(\theta)$ can be difficult to calculate analytically. However,
this is often unnecessary since it typically suffices to study an upper bound
for it. If a finer understanding is required, it is straightforward to use
Monte Carlo sampling to produce a functional estimate of $A(\theta)$. Both of
these approaches will be illustrated in several examples later. Consider the
following simple example of a non-reversible Metropolis-Hastings Markov chain
[8, Section 4.3].

######  Example 1.

For $d\in\mathbb{Z}_{+}$, let $\mathbb{R}^{d}$ be the Euclidean space of
dimension $d$. Denote the standard $p$-norms by
$\left\lVert\cdot\right\rVert_{p}$. Denote the Gaussian distribution on
$\mathbb{R}^{d}$ with mean $\mu$ and symmetric, positive-definite covariance
matrix $C$ by $N(m,C)$. For $h\in(0,1]$, consider the Crank-Nicolson proposal
$N(\sqrt{1-h}\theta,hI_{d})$ so that the proposal has the standard Gaussian
density as its invariant density, which is denoted $\rho$. Suppose $\pi$ is a
Gaussian density of the distribution $N(0,\sigma^{2}I_{d})$ with
$\sigma^{2}>1$. For $c=1/(2^{d}\sigma^{d})$,

$c\rho(\theta)/\pi(\theta)=\frac{1}{2^{d}}\exp\left(-\frac{1}{2}(1-1/\sigma^{2})\theta^{T}\theta\right)\in(0,1].$

Define

$\gamma(\theta,\theta^{\prime})=c\left[\frac{\rho(\theta)}{\pi(\theta)}\pi(\theta)q(\theta,\theta^{\prime})-\frac{\rho(\theta^{\prime})}{\pi(\theta^{\prime})}\pi(\theta^{\prime})q(\theta^{\prime},\theta)\right]$

and then $\gamma$ defines a valid non-reversible Metropolis-Hastings Markov
chain [8, Section 4.1] since

$\displaystyle\gamma(\theta,\theta^{\prime})+\pi(\theta^{\prime})q(\theta^{\prime},\theta)$
$\displaystyle=c\frac{\rho(\theta)}{\pi(\theta)}\pi(\theta)q(\theta,\theta^{\prime})+\left[1-c\frac{\rho(\theta^{\prime})}{\pi(\theta^{\prime})}\right]\pi(\theta^{\prime})q(\theta^{\prime},\theta)\geq
0.$

If $A_{NR}$ and $A_{MH}$ are the acceptance probabilities for non-reversible
MH and the usual MH with the same proposal, respectively, then

$\displaystyle A_{NR}(\theta)$
$\displaystyle=\int\left[\frac{\gamma(\theta,\theta^{\prime})+\pi(\theta^{\prime})q(\theta^{\prime},\theta)}{\pi(\theta)q(\theta,\theta^{\prime})}\wedge
1\right]q(\theta,\theta^{\prime})d\theta^{\prime}$ $\displaystyle\leq
2^{-d}+A_{MH}(\theta).$

For large $d$, the lower bounds of Theorem 1 will be similar for both Markov
chains. However, for small values of $d$, the lower bound for non-reversible
MH can be appreciably smaller than the lower bound for MH.

In general, it is difficult to compare ARB Markov chains based on lower
bounds. However, there are some settings where it may be informative.

######  Proposition 1.

Let $P_{1}$ and $P_{2}$ be ARB kernels with acceptance functions $a_{1}$ and
$a_{2}$, respectively. If $a_{1}(\theta,\theta^{\prime})\geq
a_{2}(\theta,\theta^{\prime})$ for all $\theta,\theta^{\prime}$, then

$\left\lVert
P_{2}^{t}(\theta,\cdot)-\Pi\right\rVert\geq[1-A_{2}(\theta)]^{t}\geq[1-A_{1}(\theta)]^{t}.$

If $A_{1}(\theta)\to 0$ (perhaps as $d,n\to\infty$), then the lower bound for
both $P_{1}$ and $P_{2}$ will tend to 1. Of course, if $A_{1}(\theta)\to c>0$,
then it may still be the case that $A_{2}(\theta)\to 0$. That is, $P_{1}$
might avoid poor convergence properties while $P_{2}$ does not.

######  Example 2.

Consider the portkey Barker’s kernel [60] where if
$d(\theta,\theta^{\prime})\geq 0$ is symmetric so that
$d(\theta,\theta^{\prime})=d(\theta^{\prime},\theta)$, then

$a_{PB}(\theta,\theta^{\prime})=\frac{\pi(\theta^{\prime})q(\theta^{\prime},\theta)}{\pi(\theta)q(\theta,\theta^{\prime})+\pi(\theta^{\prime})q(\theta^{\prime},\theta)+d(\theta,\theta^{\prime})}.$
(2)

Notice that Barker’s [6] algorithm is recovered if
$d(\theta,\theta^{\prime})=0$.

It is well-known that Metropolis-Hastings is more efficient than Barker’s in
the Peskun sense [39] so that the variance of the asymptotic normal
distribution for a sample mean will be larger if the Monte Carlo sample is
produced using Barker’s algorithm. However, the asymptotic variance is only
greater by a factor of 2 [32] and there are some settings where portkey
Barker’s is preferred [60].

Notice that if the same proposal density is used for Metropolis-Hastings and
portkey Barker’s, then

$a_{PB}(\theta,\theta^{\prime})\leq a_{MH}(\theta,\theta^{\prime})\leq 1$

and hence, by Proposition 1,

$\left\lVert
P_{PB}^{t}(\theta,\cdot)-\Pi\right\rVert\geq(1-A_{PB}(\theta))^{t}\geq(1-A_{MH}(\theta))^{t}.$

The lower bound for portkey Barker’s cannot be better than the lower bound for
Metropolis-Hastings.

###  3.2 Geometric ergodicity

The kernel $P$ is $(\rho,M)$-geometrically ergodic if there is a
$\rho\in(0,1)$ and a function $\theta\mapsto M(\theta)\in(0,\infty)$ such that
for every $\theta\in\Theta$ and every $t\in\mathbb{Z}_{+}$,

$\left\lVert P^{t}(\theta,\cdot)-\Pi(\cdot)\right\rVert_{\text{TV}}\leq
M(\theta)\rho^{t}.$

There has been substantial effort put into establishing the existence of
$\rho$ for some ARB Markov chains [see, e.g., 24, 34, 46, 47], but, outside of
the Metropolis-Hastings independence sampler [64], these efforts have not
yielded any constraints on $\rho$.

######  Theorem 2.

If $P$ is $(\rho,M)$-geometrically ergodic, then

$\rho\geq 1-\inf_{\theta\in\Theta}A(\theta).$

######  Example 3.

Let $b>1$ and consider the following Gaussian densities

$f(x,y)=\frac{b}{\pi}e^{-(x^{2}+b^{2}y^{2})}\quad\text{ and }\quad
g(x,y)=\frac{b}{\pi}e^{-(b^{2}x^{2}+y^{2})}.$

Set

$\pi(x,y)=\frac{1}{2}f(x,y)+\frac{1}{2}g(x,y)$

and consider a random walk MH kernel with a Gaussian proposal centered at the
previous step and scale matrix $hI_{2}$. This RWMH is geometrically ergodic
[24], but only the existence of $\rho<1$ has been established.

For any $(x,y)$

$A(x,y)\leq\iint\frac{\pi(u,v)}{\pi(x,y)}q(u,v\mid
x,y)dudv\leq\frac{1}{bh[e^{-(x^{2}+b^{2}y^{2})}+e^{-(b^{2}x^{2}+y^{2})}]}.$

By Theorem 2,

$\rho\geq 1-\frac{1}{2bh}$

and hence large values of the proposal variance $h$ should be avoided.

###  3.3 Comparison with conductance methods

In this section, the ARB Markov kernel is assumed to be reversible with
respect to $\Pi$. Let $L^{p}(\mu)$ denote the Lebesgue spaces with respect to
a measure $\mu$. Conductance can be used to lower bound the convergence rate
and this is compared to the techniques used above. If a Markov kernel $P$
satisfies

$\sup_{\begin{subarray}{c}f\in L^{2}(\Pi)\\\ \left\lVert f-\int
fd\Pi\right\rVert_{L^{2}(\Pi)}\not=0\end{subarray}}\frac{\left\lVert Pf-\int
fd\Pi\right\rVert_{L^{2}(\Pi)}}{\left\lVert f-\int
fd\Pi\right\rVert_{L^{2}(\Pi)}}=\beta\in(0,1),$

then it is said to have a $1-\beta$ spectral gap. For measurable sets $B$ with
$0<\Pi(B)<1$, define

$k_{P}(B)=\frac{\int_{B}P(\cdot,B^{c})d\Pi}{\Pi(B)\Pi(B^{c})}$

and define the conductance $k_{P}=\inf\\{k_{P}(B):0<\Pi(B)<1\\}$ [33]. The
conductance can be used to upper bound the spectral gap [33, Theorem 2.1]:

$1-\beta\leq k_{P}.$

Since $P$ is a reversible Markov kernel, there is an equivalence between a
spectral gap and geometric convergence in total variation [18, Theorem 2.1].
Specifically, there is a $\rho\in(0,1)$ such that for every probability
measure $\mu$ with $d\mu/d\Pi\in L^{2}(\Pi)$, there is a constant
$C_{\mu}\in(0,\infty)$ such that

$\left\lVert\mu P^{t}-\Pi\right\rVert_{\text{TV}}\leq C_{\mu}\rho^{t}$

if and only if there is a spectral gap with $\beta\leq\rho$. Under these
conditions, the convergence rate can be lower bounded by the conductance so
that

$1-\rho\leq k_{P}.$

Under further conditions on the function $M$, the conductance will also lower
bound the convergence rate if $P$ is $(\rho,M)-$geometrically ergodic [18,
Proposition 2.1 (ii), Theorem 2.1].

For sets $B$ with $0<\Pi(B)\leq 1/2$, to move from $B$ to $B^{c}$, the
Metropolis-Hastings kernel $P$ must accept and [22, Proposition 2.16]

$k_{P}\leq 2\sup_{x\in B}A(x).$

######  Proposition 2.

Assume $(\Omega,d)$ is a nonempty metric space. Let $P$ be a ARB Markov kernel
with an upper semicontinuous acceptance probability $A(\cdot)$. Then

$k_{P}\leq\inf_{\theta\in\Theta}A(\theta).$

The results of this section also imply that under the stronger condition that
$\int M^{2}d\Pi<\infty$ and $A(\cdot)$ is upper semicontinuous, existing
results [42, Proposition 2.1 (ii), Theorem 2.1] combined with Proposition 2
will yield the conclusion of Theorem 2.

##  4 Applications using Metropolis-Hastings

###  4.1 Gaussian proposals for Metropolis-Hastings

Suppose $h\in(0,\infty)$, $C$ is a positive-definite, symmetric matrix, and
$\mu:\mathbb{R}^{d}\to\mathbb{R}^{d}$. Let the proposal distribution be
$N(\mu(\theta),hC)$. For specific choices of $\mu$ and $C$, this is the
proposal used in many popular Metropolis-Hastings algorithms. For example, if
$C=I_{d}$ and $\mu(\theta)=\theta$, then RWMH results but if $C$ is not the
identity, then a Riemannian manifold RWMH algorithm is obtained [19]. Of
course, if $\mu(\theta)$ is a constant vector, then an independence sampler
results. If $\log\pi$ is differentiable, $C=I_{d}$, and
$\mu(\theta)=\theta+h\nabla\log\pi(\theta)/2$, then this is the proposal used
in MALA [46]. A general covariance $C$ and
$\mu(\theta)=\theta+hC\nabla\log\pi(\theta)/2$ defines the proposal used in
Riemannian manifold MALA [19]. The following result lower bounds the
convergence rate of a Metropolis-Hastings kernel independently of
$\mu(\theta)$.

######  Proposition 3.

Let $\theta_{0}\in\Theta$ and the proposal distribution be
$N(\mu(\theta),hC)$. The Metropolis-Hastings acceptance probability satisfies

$A(\theta_{0})\leq\frac{1}{\pi(\theta_{0})(2\pi h)^{d/2}\det(C)^{1/2}}.$

Even though the bound in Proposition 3 is not sharp, it results in general
restrictions on the magnitude of the tuning parameter $h$ in that it forces
$h$ to be small in order to avoid poor convergence properties. This suggests,
that MH algorithms can have convergence rates with a poor dimension
dependence, especially if the tuning parameter is not chosen carefully.

######  Example 4.

Suppose $\Pi$ is the standard $d$-dimensional Normal distribution,
$\text{N}_{d}(0,I_{d})$, and consider the Metropolis-Hastings algorithm with
proposal $N(\mu(\theta),hC)$. Fix $\theta_{0}\in\mathbb{R}^{d}$ and note that

$A(\theta_{0})\leq\frac{(2\pi
h)^{-d/2}}{(2\pi)^{-d/2}e^{-\frac{1}{2}\theta_{0}^{T}\theta_{0}}}=\frac{1}{h^{d/2}}e^{\frac{1}{2}\theta_{0}^{T}\theta_{0}}.$

Thus, for any fixed $h>1$ the acceptance probability will approach 0 for large
$d$ and hence the convergence rate will approach 1. However, this can be
avoided if, for example, $h<1$. If, instead, $d$ is fixed, then the acceptance
probability will approach 0 for large $h$. Large values of $h$ should be
avoided when tuning any of the MH algorithms in this example.

An alternative is to take $h\propto d^{-\delta}$ for some $\delta>0$, which is
reminiscent of the guidelines developed in the optimal scaling literature for
large $d$. In particular, the optimal scaling guidelines for RWMH suggest
taking $h\propto d^{-1}$ [50] while for MALA the optimal scaling guidelines
suggest taking $h\propto d^{-1/3}$ [44].

Normal proposal distributions are common in many applications of MH, but the
key requirement in the proof of Proposition 3 is the boundedness of the
proposal density. Consider using a multivariate $t$-distribution as a proposal
instead, specifically $t_{\nu}(\mu(\theta),hC)$. Then, if $\Gamma(\cdot)$
denotes the usual gamma function,

$q(\theta,\theta_{0})\leq\frac{\Gamma((\nu+d)/2)}{\Gamma(\nu/2)(h\pi)^{d/2}\det(C)^{1/2}}$

and the same argument in the proof yields that

$A(\theta_{0})\leq\frac{\Gamma((\nu+d)/2)}{\pi(\theta_{0})\Gamma(\nu/2)(h\pi)^{d/2}\det(C)^{1/2}}.$

As with the example above, this suggests that large values of $h$ should be
avoided.

###  4.2 RWMH with log-concave targets

Let $f:\Theta\to\mathbb{R}$ and $\pi=Z^{-1}\exp(-f)$ where $Z$ is the
normalizing constant. Consider sampling from $\pi$ with RWMH using a
$d$-dimensional Gaussian proposal centered at the current state with variance
$hI_{d}$. In this case, for all $\theta\in\Theta$,

$A(\theta)=\int\left[\frac{\pi(\theta^{\prime})}{\pi(\theta)}\wedge
1\right]q(\theta^{\prime}\mid\theta)d\theta^{\prime}\leq\frac{1}{(2\pi
h)^{d/2}}\int
e^{\left(f(\theta)-f(\theta^{\prime})\right)}e^{-\frac{1}{2h}\left\lVert\theta^{\prime}-\theta\right\rVert^{2}_{2}}d\theta^{\prime}$

More can be said with more assumptions on $f$. Consider the setting where $f$
satisfies a strong-convexity requirement. That is, if $S$ is a convex set and
$\xi\in(0,\infty)$, the function $f$ is $\xi^{-1}$-strongly convex if
$\theta\mapsto f(\theta)-\left\lVert\theta\right\rVert_{2}^{2}/2\xi$ is convex
on $S$. Also, let $\partial f(\theta)$ denote the set of subgradients of $f$
at the point $\theta$.

######  Proposition 4.

Suppose $\Theta$ is convex and that, for $\xi\in(0,\infty)$, $f$ is
$\xi^{-1}$-strongly convex on $\Theta$. If $\theta_{0}\in\Theta$, then, for
any $v\in\partial f(\theta_{0})$,

$A(\theta_{0})\leq\frac{1}{(1+h/\xi)^{d/2}}\exp\left\\{\frac{h}{2}\left(\frac{1}{1+h/\xi}\right)\|v\|^{2}_{2}\right\\}.$

There are at least two settings where Proposition 4 yields specifc lower
bounds.

######  Corollary 1.

Suppose $\Theta$ is convex and that, for $\xi\in(0,\infty)$, $f$ is
$\xi^{-1}$-strongly convex on $\Theta$. If $\theta^{*}$ is the point which
maximizes $\pi$, then

$A(\theta^{*})\leq(1+h/\xi)^{-d/2}$

and hence

$\|P^{t}(\theta^{*},\cdot)-\Pi\|\geq\left(1-\frac{1}{(1+h/\xi)^{d/2}}\right)^{t}.$

###### Proof.

This is immediate from Proposition 4 with the observation that $0\in\partial
f(\theta^{*})$. ∎

######  Corollary 2.

Suppose $\Theta$ is convex and that, for $\xi\in(0,\infty)$, $f$ is
$\xi^{-1}$-strongly convex on $\Theta$. If the RWMH kernel is
$(\rho,M)$-geometrically ergodic, then

$\rho\geq 1-(1+h/\xi)^{-d/2}.$

###### Proof.

This is immediate from Theorem 2 and Corollary 1. ∎

For any fixed value of $h$, the lower bound will increase exponentially as
$d\to\infty$. However, if $h\propto 1/d$, then this can be avoided, an
observation that agrees with the optimal scaling guidelines [49], but under
much weaker conditions on $\Pi$.

An adversarial example using a Gaussian target showed the spectral gap for the
RWMH algorithm tends to $0$ polynomially fast with the dimension [22]. An
adversarial example in a non-toy example where the convergence rate can tend
to $1$ exponentially in the dimension follows.

######  Example 5.

(RWMH for Bayesian logistic regression) Suppose, for $i=1,\ldots,n$,
$X_{i}\in\mathbb{R}^{d}$ and

$\displaystyle\beta\sim N(0,\sigma_{\text{prior}}^{2}I_{d})$ $\displaystyle
Y_{i}|X_{i},\beta\stackrel{{\scriptstyle
ind}}{{\sim}}\text{Bern}\left(\left(1+\exp\left(-\beta^{T}X_{i}\right)\right)^{-1}\right).$

Consider RWMH with Gaussian proposal centered at the current state, scale
$hI_{d}$, and having the posterior distribution as its invariant distribution.
The RWMH is $(\rho,M)$-geometrically ergodic for some unknown $(\rho,M)$ [61].
The negative log-likelihood in this model is convex and applying Corollary 2,
obtain

$\rho\geq 1-(h/\sigma^{2}_{\text{prior}}+1)^{-d/2}.$

####  4.2.1 Bayesian logistic regression with Zellner’s g-prior

A specific application is considered where both $d$ and $n$ are allowed to
increase and the data-generating mechanism for Bayesian logistic regression
with Zellner’s g-prior [70] need not be correct. Let $(Y_{i},X_{i})_{i=1}^{n}$
with $Y_{i}$ taking values in $\\{0,1\\}$ and $X_{i}$ taking values in
$\mathbb{R}^{d}$. Let $g\in(0,\infty)$ be a fixed constant and set
$X=(X_{1},\ldots,X_{n})^{T}$. If $X^{T}X$ is positive-definite and $s(\cdot)$
denotes the sigmoid function, the posterior density is characterized by

$\pi_{n}(\beta)\propto\prod_{i=1}^{n}s\left(\beta^{T}X_{i}\right)^{Y_{i}}\left(1-s\left(\beta^{T}X_{i}\right)\right)^{1-Y_{i}}\exp\left(-\frac{1}{2g}\beta^{T}X^{T}X\beta\right).$

Assume $(X_{i,j})_{i,j}$ are independent and identically distributed random
variables with zero mean, unit variance, and a finite fourth moment. Consider
RWMH with a Gaussian proposal centered at the current state and scale $hI_{d}$
and invariant density $\pi_{n}$. If $d_{n}/n\to\gamma\in(0,1)$ as
$n\to\infty$, the following result implies that the convergence rate will
exponentially tend to $1$ with $n$ unless $h\leq
2g/[(1-\sqrt{\gamma})^{2}nd_{n})]$.

######  Proposition 5.

Let $\beta_{n}^{*}$ denote the point which maximizes $\pi_{n}$. If
$n\to\infty$ in such a way that $d_{n}/n\to\gamma\in(0,1)$, then, with
probability 1, for all sufficiently large $n$, the acceptance probability for
RWMH satisfies

$A(\beta^{*}_{n})\leq\left(\frac{hn(1-\sqrt{\gamma})^{2}}{2g}+1\right)^{-d_{n}/2}.$

It is useful to empirically investigate the convergence of the RWMH algorithm
in this example for different tuning parameters. The acceptance probability at
the posterior maximum $\beta^{*}_{n}$ can be estimated using standard Monte
Carlo with $10^{3}$ samples. Since $\pi_{n}$ is log-concave, $\beta^{*}_{n}$
can be estimated efficiently using gradient descent. In turn, Theorem 1 will
be used to estimate the lower bound to the convergence rate. Artificial data
$(Y_{i},X_{i})_{i}$ will be considered where $X_{i}\sim\text{Unif}(-1,1)$,
$g=10$, and the data are generated with increasing dimensions $d$ and sample
sizes $n=4d$, specifically,

$(d,n)\in\\{(2,8),(4,16),(4,24),(8,32),(10,40),(12,48),(14,56)\\}.$

As a guideline, Corollary 5 says to choose $h\leq 20/d^{2}$ at least when $n$
is large enough. This example does not satisfy the required theoretical
assumptions for optimal scaling guidelines [49] and hence is anticipated to
perform poorly here. It is compared to optimal scaling with $h=2.38^{2}/d$, a
fixed variance parameter $h=.6$, and scaling with $h=1/(dn)$ according to
Corollary 5. Repeating the simulation $50$ times with randomly generated data,
Figure 1(a) displays the estimates to these lower bounds using the average
within $1$ standard error. Figure 1(b) plots the log acceptance probability at
the target’s maximum to compare the speed at which the convergence rate tends
to 1. According to the theory, optimal scaling and fixed parameter choices
should behave poorly as the dimension increases which corresponds with the
simulation results shown in Figure 1.

(a)

(b)

Figure 1: (a) Lower bounds to the rate of convergence the RWMH algorithm with
different scaling values for logistic regression model with Zellner’s g-prior.
(b) Log acceptance probability at the target’s maximum. The shaded regions
represent $1$ standard deviation from the average after repeated simulations.

###  4.3 Lower bounds under concentration

Section 4.2.1 considered lower bounds on RWMH under concentration of a
strongly log-concave posterior. If the target density is concentrating to its
maximal point with $n$, intuition suggests that the tuning parameters of the
Metropolis-Hastings algorithm should also depend on the parameter $n$. In
infinitely unbalanced Bayesian logistic regression, proposals which depend on
the sample size have been shown to exhibit more appealing convergence
complexity when compared to data augmentation Gibbs samplers [26].

Consider target distributions indexed by a parameter $n\in\mathbb{Z}_{+}$ such
as Bayesian posteriors where $n$ is the sample size. Let
$f_{n}:\mathbb{R}^{d}\to\mathbb{R}$ and
$Z_{n}=\int_{\mathbb{R}^{d}}\exp(-nf_{n}(\theta))d\theta$. Define the target
density by $\pi_{n}(\theta)=Z_{n}^{-1}\exp\left(-nf_{n}(\theta)\right)$. If
the proposal density is bounded so that there is $B<\infty$, with $B$ possibly
depending on $n$ or $d$, such that $q(\theta^{\prime},\theta)\leq B$ (cf.
Section 4.1), then for MH algorithms,

$A(\theta_{0})\leq BZ_{n}e^{nf_{n}(\theta_{0})}.$

Of course, the best lower bound will result at $\theta_{0}=\theta_{n}^{*}$, a
point maximizing $\pi_{n}$.

A Laplace approximation can be used to lower bound the target density at its
maximum point. The following result is inspired by previous results on Laplace
approximations [31, 57, 58], but unlike high-dimensional Laplace
approximations [53, 54], $f_{n}$ is not required to be differentiable.

######  Proposition 6.

Suppose there exists at least one $\theta_{n}^{*}\in\Theta$ which maximizes
$\pi_{n}$ for each $n$. Assume for some $\kappa\in(0,1)$, the dimension
$d_{n}\leq n^{\kappa}$ and that the following holds for some constants
$\delta_{0},\lambda_{0},f^{*},I_{0}\in(0,\infty)$ and for all sufficiently
large $(n,d_{n})$:

1\. $f_{n}$ is $\lambda_{0}^{-1}$-strongly convex for all
$\left\lVert\theta-\theta_{n}^{*}\right\rVert_{2}\leq\delta_{0}$.

2\. The optimal point satisfies the strict optimality condition:

$\inf_{\left\lVert v\right\rVert>\delta_{0}}f_{n}(\theta_{n}^{*}+v)\geq
f_{n}(\theta_{n}^{*})+f^{*}$

3\. The integral is controlled away from the optimum:

$\int_{\left\lVert
v\right\rVert_{2}>\delta_{0}}\exp\left(-\left(f_{n}(\theta_{n}^{*}+v)-f_{n}(\theta_{n}^{*})\right)\right)dv\leq(I_{0}n)^{d_{n}}.$

Then for any $c\in(0,1]$, for all sufficiently large $(n,d_{n})$, the density
$\pi_{n}$ concentrates at $\theta^{*}_{n}$ with

$\displaystyle\pi_{n}(\theta^{*}_{n})$
$\displaystyle\geq\frac{1}{1+c}\left(\frac{n}{2\pi\lambda_{0}}\right)^{d_{n}/2}.$

Moreover, f the proposal density is bounded so that there is $B<\infty$, with
$B$ possibly depending on $n$ or $d$, such that $q(\theta^{\prime},\theta)\leq
B$, then

$A(\theta_{n}^{*})\leq
B(1+c)\left(\frac{2\pi\lambda_{0}}{n}\right)^{d_{n}/2}.$

Proposition 6 requires the dimension to not grow too fast with $n$. The first
assumption is a locally strong convex assumption which ensures sufficient
curvature of $f_{n}$ locally near the maximum point of $f_{n}$. Since only a
lower bound on the density is required, the need to control higher order
derivatives used in high-dimensional Laplace approximations [53, 54] is
avoided. The second and third assumptions ensure sufficient decay of $f_{n}$
away from $\theta^{*}_{n}$ similar to assumptions made previously [31, 54].
Similar assumptions are also used for Bayesian posterior densities with proper
priors when the dimension is fixed [37, Theorem 4].

######  Example 6.

Recall the definitions of $\mu(\theta)$, $C$, and $h$ from Section 4.1 and
consider MH with a $N(\mu(\theta),hC)$ proposal. Under the conditions of
Proposition 6, the acceptance probability satisfies

$A(\theta_{n}^{*})\leq\left(\frac{\lambda_{0}}{nh}\right)^{d_{n}/2}\frac{1+c}{\det(C)^{1/2}}.$
(3)

Similarly, Proposition 6 can be applied with the $t_{\nu}(\mu(\theta),hC)$
proposal which was considered in Section 4.1.

It is evident from (3) that Proposition 6 can be important when tuning
Metropolis-Hastings algorithms used in Bayesian statistics. In particular, if
the target density is concentrating at its maximum point and the tuning
parameters $h$ and $C$ do not depend carefully on $n$, then it easily can
happen that $\lim_{(n,d_{n})\to\infty}A(\theta_{n}^{*})=0$ rapidly. Moreover,
it can happen that the geometric convergence rate
$\lim_{(n,d_{n})\to\infty}\rho_{n}=1$ rapidly.

####  4.3.1 Flat prior Bayesian logistic regression

Consider flat prior Bayesian logistic regression without assuming correctness
of the data generation. Let $(Y_{i},X_{i})_{i=1}^{n}$ be independent and
identically distributed with $Y_{i}\in\\{0,1\\}$ and $X_{i}\in\mathbb{R}^{d}$.
With the sigmoid function $s(\cdot)$, the posterior density is characterized
by

$\pi_{n}(\beta)\propto\prod_{i=1}^{n}s\left(\beta^{T}X_{i}\right)^{Y_{i}}\left(1-s\left(\beta^{T}X_{i}\right)\right)^{1-Y_{i}}.$

######  Assumption 1.

Let $z_{i}=1$ if $Y_{i}=0$ and $z_{i}=-1$ if $Y_{i}=1$ and define $X^{*}$ to
be the matrix with rows $z_{i}X_{i}^{T}$. Suppose:

1\. $X=(X_{1},\ldots,X_{n})^{T}$ is full column rank.

2\. There exists a vector $a\in\mathbb{R}^{n}$ with all components positive
such that ${X^{*}}^{T}a=0$.

If Assumption 1 holds with probability $1$ for all sufficiently large $n$,
then both the maximum likelihood estimator (MLE) $\beta_{n}^{*}$ and the
random Bayesian logistic regression posterior density, $\pi_{n}(\beta)$, exist
[12, Theorems 2.1, 3.1].

The Pólya-Gamma Gibbs sampler has been shown to be geometrically ergodic for
this model [65], but it remains an open question if Metropolis-Hastings is
geometrically ergodic. Since the prior is improper, previous results on
posterior concentration [37] do not apply, but the next result shows that the
posterior density can indeed concentrate so that Proposition 6 can be applied
for MH algorithms with bounded proposals. For the sake of specificity recall
the definitions of $\mu(\theta)$, $C$, and $h$ from Section 4.1 so that the MH
algorithms uses a $N(\mu(\theta),hC)$ proposal distribution.

######  Theorem 3.

Assume the following:

  1. 1.

With probability $1$, Assumption 1 holds for all sufficiently large $n$.

  2. 2.

The MLE $\beta^{*}_{n}$ is almost surely consistent to some
$\beta_{0}\in\mathbb{R}^{d}$.

  3. 3.

$\left\lVert X_{1}\right\rVert_{2}\leq 1$ with probability $1$.

  4. 4.

For $u\in\mathbb{R}^{d}$, if $u\not=0$, then $X_{1}^{T}u\not=0$ with
probability $1$.

Then, with probability $1$, for all sufficiently large $n$, there is a
$\lambda_{0}\in(0,\infty)$ so that the MH acceptance probability satisfies

$A(\beta_{n}^{*})\leq\left(\frac{\lambda_{0}}{nh}\right)^{d/2}\frac{2}{\det(C)^{1/2}}.$

Assumption 1 ensures existence of the posterior density and MLE [12, Theorem
2.1, 3.1]. Consistency of the MLE in Assumption 2 is a well-studied problem
and conditions are available when the model is correctly specified [16] or
using M-estimation [59, Example 5.40]. Assumption 4 was used previously [37,
Theorem 13] and is used to ensure identifiability in generalized linear models
[59]. Assumption 2 requires standardization of the features which is often
done for numerical stability.

In this example an explicit value for $\lambda_{0}$ is unavailable, but the
robustness of the scaling can be investigated empirically via a standard Monte
Carlo estimate of the acceptance probability at the MLE $\beta^{*}_{n}$. The
estimate will be based on $10^{3}$ Monte Carlo samples. Consider using MH with
a fixed variance parameter $h=.1$, and scaling with $h=5/n$, $h=1/n$, and
$h=.1/n$. Artificial data is generated with $(Y_{i},X_{i})_{i}$ where
$X_{i}\sim\text{Unif}(-1,1)$ in fixed dimension $d=10$ and increasing sample
sizes $n\in\\{100,200,300,400\\}$. The simulation is replicated $50$ times
independently. Figure 2(a) shows the total convergence rate lower bound and
Figure 2(b) shows the log acceptance probability at the target’s maximum using
the average within $1$ estimated standard error. It is apparent that $h=5/n$
scales worse than $h=1/n,.1/n$, but the scaling is not nearly as problematic
as the fixed variance parameter which is commonly used in practice.

(a)

(b)

Figure 2: (a) Lower bounds to the rate of convergence for flat prior Bayesian
logistic regression with RWMH with different scaling values. (b) Log
acceptance probability at the target’s maximum. The shaded regions represent
$1$ standard deviation from the average after repeated simulations.

##  5 Wasserstein lower bounds

Wasserstein distances have become popular in the convergence analysis of high-
dimensional MCMC algorithms due to improved scaling properties in high
dimensions compared to the total variation distance. There are lower bounds
available for many Wasserstein distances which are analogous to the lower
bounds from Section 3 and which can result in similar conclusions if the
acceptance probability is not well-behaved.

The Wasserstein lower bounds also yield necessary conditions for Wasserstein
geometric ergodicity of ARB chains that are similar to those available for
total variation [47]. A result of independent interest establishes the
equivalence between the a spectral gap and Wasserstein geometric ergodicity
for general reversible Markov chains, complementing existing results for total
variation [42].

###  5.1 Lower bounds

For probability measures $\mu,\nu$, let $\mathcal{C}(\mu,\nu)$ be the set of
all joint probability measures with marginals $\mu,\nu$. With a metric cost
function $c(\cdot,\cdot)$, the $c$-Wasserstein distance of order
$p\in\mathbb{Z}_{+}$ is

$\mathcal{W}_{c}^{p}\left(\mu,\nu\right)=\left(\inf_{\Gamma\in\mathcal{C}(\mu,\nu)}\int
c(\theta,\omega)^{p}d\Gamma(\theta,\omega)\right)^{1/p}.$

Generally, the metric $c$ is the metric on the space.

We consider the following assumption on the target density.

######  Assumption 2.

Suppose $\Omega=\mathbb{R}^{d}$ where $d\in\mathbb{Z}_{+}$ and
$\Theta\subseteq\mathbb{R}^{d}$. Suppose $\pi$ is a density with respect to
Lebesgue measure and suppose $s=\sup_{\theta\in\Theta}\pi(\theta)<\infty$.

The Wasserstein distances are required to satisfy the following condition.

######  Assumption 3.

Suppose for some constant $C_{0,d}$, $c(\cdot,\cdot)\geq
C_{0,d}\left\lVert\cdot-\cdot\right\rVert_{1}$.

As norms are equivalent on $\mathbb{R}^{d}$, these cost metrics include any
norm $\left\lVert\cdot\right\rVert$ on $\mathbb{R}^{d}$.

For the special case of the Metropolis-Hastings independence sampler there are
existing lower bounds for some Wasserstein distances [11]. The above
assumptions are enough to ensure lower bounds for the general ARB Markov chain
and a wider class of Wasserstein distances.

######  Theorem 4.

Let assumptions 2 and 3 hold. If
$C_{d,\pi}=C_{0,d}d[2s^{\frac{1}{d}}(1+d)^{1+\frac{1}{d}}]^{-1}$, then for
every $t\in\mathbb{Z}_{+}$ and every $\theta\in\mathbb{R}^{d}$

$\mathcal{W}_{c}^{p}(P^{t}(\theta,\cdot),\Pi)\geq
C_{d,\pi}[1-A(\theta)]^{t\left(1+\frac{1}{d}\right)}.$

The same argument used in establishing Proposition 1 can be used with Theorem
4 to obtain an analogous comparison result.

######  Proposition 7.

Let $P_{1}$ and $P_{2}$ be ARB kernels with acceptance functions $a_{1}$ and
$a_{2}$, respectively. If assumptions 2 and 3 hold and
$a_{1}(\theta,\theta^{\prime})\geq a_{2}(\theta,\theta^{\prime})$ for all
$\theta,\theta^{\prime}$, then

$\mathcal{W}_{c}^{p}(P_{2}^{t}(\theta,\cdot),\Pi)\geq
C_{d,\pi}[1-A_{2}(\theta)]^{t\left(1+\frac{1}{d}\right)}\geq
C_{d,\pi}[1-A_{1}(\theta)]^{t\left(1+\frac{1}{d}\right)}$

###  5.2 Geometric ergodicity

Say $P$ is $(c,p,\rho,M)$-geometrically ergodic if there is a $\rho\in(0,1)$
and a function $\theta\mapsto M(\theta)\in(0,\infty)$ such that for every
$\theta\in\Theta$ and every $t\in\mathbb{Z}_{+}$,

$\mathcal{W}_{c}^{p}\left(P^{t}(\theta,\cdot),\Pi\right)\leq
M(\theta)\rho^{t}.$

Compared to the definition of geometric ergodicity in total variation, this
requires a metric cost function $c$ for the Wasserstein distance of order $p$.

######  Theorem 5.

Let assumptions 2 and 3 hold. If $P$ is $(c,p,\rho,M)$-geometrically ergodic,
then

$\rho^{\frac{d}{d+1}}\geq 1-\inf_{\theta\in\Theta}A(\theta).$

Recall that if the rejection probability cannot be bounded below one, that is,
if the acceptance probability satisfies
$\inf_{\theta\in\mathbb{R}^{d}}A(\theta)=0$, then a Metropolis-Hastings
algorithm fails to be geometrically ergodic [47, Proposition 5.1]. Theorem 5
yields the same in these Wasserstein distances for ARB kernels. There are well
known examples where the condition on this happens [34, Example 1], [47,
Proposition 5.2].

######  Corollary 3.

Let assumptions 2 and 3 hold. If $\inf_{\theta\in\Theta}A(\theta)=0$, then $P$
cannot be $(c,p,\rho,M)$-geometrically ergodic.

###### Proof.

If it were $(c,p,\rho,M)$-geometrically ergodic, then, by Theorem 5,
$\rho^{\frac{d}{d+1}}\geq 1$, which is a contradiction. ∎

Analogous comparisons can be made to conductance methods as in Section 3.3. In
particular, the lower bounds on the spectral gap can also lower bound the
exponential convergence rate in the Wasserstein distance. We extend previously
developed sufficient conditions for a spectral gap using the Wasserstein
distance to an equivalence condition [22, Proposition 2.8]. Note that the
assumptions in the following proposition are self-contained and hold for
reversible Markov kernels under more general conditions.

######  Proposition 8.

Let $\Pi$ be any probability measure on a Polish space
$(\Omega,d,\mathcal{B}(\Omega))$, and let $P$ be any Markov kernel on
$(\Omega,d,\mathcal{B}(\Omega))$ reversible with respect to $\Pi$. For a
$\rho\in(0,1)$, the following are equivalent if they hold for every
probability measure $\mu$ on $\Omega$ with $d\mu/d\Pi\in L^{2}(\Pi)$:

(i) The Markov operator $P$ has a spectral gap at least $1-\rho$.

(ii) There is a $C_{\mu}\in(0,\infty)$ depending on $\mu$ such that for every
$t\in\mathbb{Z}_{+}$,

$\mathcal{W}_{d\wedge 1}\left(\mu P^{t},\Pi\right)\leq C_{\mu}\rho^{t}.$

For reversible Metropolis-Hastings under the conditions of Proposition 2, if
Proposition 8 (ii) holds, then

$1-\rho\leq\inf_{\theta\in\Theta}A(\theta).$

Under these conditions, an application of Hölder’s inequality extends this
lower bound to Wasserstein distances of order $p$. For probability measures
$\mu$ with $d\mu/d\Pi\in L^{2}(\Pi)$, if there is a $C_{\mu}\in(0,\infty)$
such that for every $t\in\mathbb{Z}_{+}$,

$\mathcal{W}_{d}^{p}\left(\mu P^{t},\Pi\right)\leq C_{\mu}\rho^{t},$

then $\rho\geq 1-\inf_{\theta}A(\theta)$ as well.

##  6 Final remarks

The lower bounds studied above can guide practitioners in tuning ARB
algorithms, including Metropolis-Hastings algorithms. Particular attention was
paid to the convergence complexity of geometrically ergodic ARB chains and it
was demonstrated that the tuning parameters should carefully take into account
both the sample size $n$ and parameter dimension $d$. In particular, RWMH and
MALA type algorithms have strong restrictions on the scaling parameter $h$
when the target density concentrates with $n$.

Lower bounds on the convergence rate appear to be available for other sampling
algorithms such as Hamiltonian Monte Carlo, component-wise MCMC (e.g.
Metropolis-within-Gibbs), and some adaptive MCMC algorithms, but these are
beyond the scope of the current work.

##  7 Supplementary material and code availability

The Python package ”mhlb” and the code used for the simulations and plots are
made available for download at https://github.com/austindavidbrown/lower-
bounds-for-Metropolis-Hastings.

##  8 Acknowledgements

We thank Riddhiman Bhattacharya, Qian Qin, and Dootika Vats for their helpful
comments on an earlier draft. Jones was partially supported by NSF grant
DMS-2152746.

## References

  * Agrawal et al. [2021] Sanket Agrawal, Dootika Vats, Krzysztof Łatuszyński, and Gareth O. Roberts.  Optimal scaling of MCMC beyond Metropolis.  _To appear in Advances in Applied Probability_, 2021.
  * Andrieu and Vihola [2015] Christophe Andrieu and Matti Vihola.  Convergence properties of pseudo-marginal Markov chain Monte Carlo algorithms.  _The Annals of Applied Probability_ , 25(2):1030 – 1077, 2015.
  * Andrieu et al. [2022] Christophe Andrieu, Anthony Lee, Sam Power, and Andi Q. Wang.  Explicit convergence bounds for Metropolis Markov chains: isoperimetry, spectral gaps and profiles.  _preprint arXiv:2211.08959_ , 2022.
  * Bach [2010] Francis Bach.  Self-concordant analysis for logistic regression.  _Electronic Journal of Statistics_ , 4:384 – 414, 2010\.
  * Bai and Yin [1993] Z. D. Bai and Y. Q. Yin.  Limit of the smallest eigenvalue of a large dimensional sample covariance matrix.  _The Annals of Probability_ , 21(3):1275 – 1294, 1993.
  * Barker [1964] A. A. Barker.  Monte Carlo calculations of the radial distribution functions for a proton-electron plasma.  _Australian Journal of Physics_ , 18:119–132, 1964.
  * Belloni and Chernozhukov [2009] Alexandre Belloni and Victor Chernozhukov.  On the computational complexity of MCMC-based estimators in large samples.  _The Annals of Statistics_ , 37(4):2011–2055, 2009.
  * Bierkens [2015] Joris Bierkens.  Non-reversible Metropolis-Hastings.  _Statistics and Computing_ , 26(6):1213–1228, 2015.
  * Bou-Rabee and Eberle [2020] Nawaf Bou-Rabee and Andreas Eberle.  Markov chain Monte Carlo methods, 2020.
  * Brooks et al. [2011] Stephen P. Brooks, Andrew Gelman, Galin L. Jones, and Xiao-Li Meng (Ed).  _Handbook of Markov Chain Monte Carlo_.  Chapman & Hall, London, 2011.
  * Brown and Jones [2022] Austin Brown and Galin L. Jones.  Exact convergence analysis for Metropolis-Hastings independence samplers in Wasserstein distances.  _preprint arXiv:2111.10406_ , 2022.
  * Chen and Shao [2000] Ming-Hui Chen and Q. Shao.  Propriety of posterior distribution for dichotomous quantal response models.  _Proceedings of the American Mathematical Society_ , 129(1):293 – 302, 2000.
  * Dalalyan [2017] Arnak S. Dalalyan.  Theoretical guarantees for approximate sampling from smooth and log-concave densities.  _Journal of the Royal Statistical Society, Series B_ , 79:651–676, 2017.
  * Durmus and Moulines [2015] Alain Durmus and Éric Moulines.  Quantitative bounds of convergence for geometrically ergodic Markov chain in the Wasserstein distance with application to the Metropolis adjusted Langevin algorithm.  _Statistics and Computing_ , 25:5–19, 2015.
  * Ekvall and Jones [2021] Karl Oskar Ekvall and Galin L. Jones.  Convergence analysis of a collapsed Gibbs sampler for Bayesian vector autoregressions.  _Electronic Journal of Statistics_ , 15:691 – 721, 2021\.
  * Fahrmeir and Kaufmann [1985] Ludwig Fahrmeir and Heinz Kaufmann.  Consistency and asymptotic normality of the maximum likelihood estimator in generalized linear models.  _The Annals of Statistics_ , 13(1):342 – 368, 1985.
  * Folland [1999] Gerald B. Folland.  _Real Analysis: Modern Techniques and Their Applications_.  Wiley, 2 edition, 1999.
  * Fort et al. [2003] G. Fort, E. Moulines, Gareth O. Roberts, and J. S. Rosenthal.  On the geometric ergodicity of hybrid samplers.  _Journal of Applied Probability_ , 40(1):123–146, 2003.
  * Girolami and Calderhead [2011] Mark Girolami and Ben Calderhead.  Riemann manifold Langevin and Hamiltonian Monte Carlo methods.  _Journal of the Royal Statistical Society. Series B (Statistical Methodology)_ , 73(2):123–214, 2011.
  * Haario et al. [2001] Heikki Haario, Eero Saksman, and Johanna Tamminen.  An adaptive Metropolis algorithm.  _Bernoulli_ , 7(2):223 – 242, 2001.
  * Hairer and Mattingly [2011] Martin Hairer and Jonathan C. Mattingly.  Yet another look at Harris’ ergodic theorem for Markov chains.  _Seminar on Stochastic Analysis, Random Fields and Applications VI_ , 63, 2011.
  * Hairer et al. [2014] Martin Hairer, Andrew M. Stuart, and Sebastian J. Vollmer.  Spectral gaps for a Metropolis–Hastings algorithm in infinite dimensions.  _The Annals of Applied Probability_ , 24:2455–2490, 2014\.
  * Hastings [1970] W. K. Hastings.  Monte Carlo sampling methods using Markov chains and their applications.  _Biometrika_ , 57(1), 1970.
  * Jarner and Hansen [2000] Søren F. Jarner and Ernst Hansen.  Geometric ergodicity of Metropolis algorithms.  _Stochastic Processes and their Applications_ , 85:341–361, 2000.
  * Jarner and Yuen [2004] Søren F. Jarner and Wai Kong Yuen.  Conductance bounds on the $l^{2}$ convergence rate of Metropolis algorithms on unbounded state spaces.  _Advances in Applied Probability_ , 36:243–266, 2004.
  * Johndrow et al. [2019] James E. Johndrow, Aaron Smith, Natesh Pillai, and David B. Dunson.  MCMC for imbalanced categorical data.  _Journal of the American Statistical Association_ , 114(527):1394–1403, 2019.
  * Jones and Hobert [2001] Galin L. Jones and James P. Hobert.  Honest exploration of intractable probability distributions via Markov chain Monte Carlo.  _Statistical Science_ , 16:312–334, 2001.
  * Jones and Hobert [2004] Galin L. Jones and James P. Hobert.  Sufficient burn-in for Gibbs samplers for a hierarchical random effects model.  _The Annals of Statistics_ , 32(2):784 – 817, 2004.
  * Kallenberg [2021] Olav Kallenberg.  _Foundations of Modern Probability_.  Springer, Cham, 3 edition, 2021.
  * Kantorovich and Rubinstein [1957] L. V. Kantorovich and G. S. Rubinstein.  On a function space in certain extremal problems.  _Dokl. Akad. Nauk USSR_ , 115(6):1058–1061, 1957\.
  * Kass et al. [1990] Robert E. Kass, Luke Tierney, and Joseph B. Kadane.  The validity of posterior expansions based on Laplace’s method.  _Bayesian and Likelihood Methods in Statistics and Econometrics_ , pages 473–488, 1990.
  * Łatuszyńki and Roberts [2013] K. Łatuszyńki and G. O. Roberts.  CLTs and asymptotic variance of time-sampled Markov chains.  _Methodology and Computing in Applied Probability_ , 15:237–247, 2013.
  * Lawler and Sokal [1988] Gregory F. Lawler and Alan D. Sokal.  Bounds on the $l^{2}$ spectrum for Markov chains and Markov processes: A generalization of Cheeger’s inequality.  _Transactions of the American Mathematical Society_ , 309(2):557–580, 1988.
  * Mengersen and Tweedie [1996] Kerrie L. Mengersen and Richard L. Tweedie.  Rates of convergence of the Hastings and Metropolis algorithms.  _The Annals of Statistics_ , 24:101–121, 1996.
  * Metropolis et al. [1953] N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller.  Equations of state calculations by fast computing machine.  _Journal of Chemical Physics_ , 21, 1953.
  * Meyn and Tweedie [2009] Sean P. Meyn and Richard L. Tweedie.  _Markov Chains and Stochastic Stability_.  Cambridge University Press, USA, 2 edition, 2009.
  * Miller [2021] Jeffrey W. Miller.  Asymptotic normality, concentration, and coverage of generalized posteriors.  _Journal of Machine Learning Research_ , 22:1–53, 2021\.
  * Nesterov [2018] Yurii Nesterov.  _Lectures on Convex Optimization_.  Springer International Publishing, 2 edition, 2018.
  * Peskun [1973] P. Peskun.  Optimum Monte Carlo sampling using Markov chains.  _Biometrika_ , 89:745–754, 1973.
  * Qin and Hobert [2019] Qian Qin and James P Hobert.  Convergence complexity analysis of Albert and Chib’s algorithm for Bayesian probit regression.  _Annals of Statistics_ , 47:2320–2347, 2019.
  * Rajaratnam and Sparks [2015] Bala Rajaratnam and Doug Sparks.  MCMC-based inference in the era of big data: A fundamental analysis of the convergence complexity of high-dimensional chains.  _preprint arXiv:1508.00947_ , 2015.
  * Roberts and Rosenthal [1997] Gareth O. Roberts and Jeffrey S. Rosenthal.  Geometric ergodicity and hybrid Markov chains.  _Electronic Communications in Probability_ , 2:13–25, 1997\.
  * Roberts and Rosenthal [1998a] Gareth O. Roberts and Jeffrey S. Rosenthal.  Optimal scaling of discrete approximations to Langevin diffusions.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 60(1):255––268, 1998a.
  * Roberts and Rosenthal [1998b] Gareth O. Roberts and Jeffrey S Rosenthal.  Optimal scaling of discrete approximations to Langevin diffusions.  _Journal of the Royal Statistical Society: Series B_ , 60:255–268, 1998b.
  * Roberts and Rosenthal [2011] Gareth O. Roberts and Jeffrey S. Rosenthal.  Quantitative non-geometric convergence bounds for independence samplers.  _Methodology and Computing in Applied Probability volume_ , 13:391––403, 2011.
  * Roberts and Tweedie [1996a] Gareth O. Roberts and Richard L. Tweedie.  Exponential convergence of Langevin distributions and their discrete approximations.  _Bernoulli_ , 2(4):341–363, 1996a.
  * Roberts and Tweedie [1996b] Gareth O. Roberts and Richard L. Tweedie.  Geometric convergence and central limit theorems for multidimensional Hastings and Metropolis algorithms.  _Biometrika_ , 83:95–110, 1996b.
  * Roberts et al. [1997a] Gareth O. Roberts, A. Gelman, and W. R. Gilks.  Weak convergence and optimal scaling of random walk metropolis algorithms.  _The Annals of Applied Probability_ , 7(1):110–120, 1997a.
  * Roberts et al. [1997b] Gareth O. Roberts, Andrew Gelman, and W. R. Gilks.  Weak convergence and optimal scaling of random walk Metropolis algorithms.  _The Annals of Applied Probability_ , 7(1):110 – 120, 1997b.
  * Roberts et al. [1997c] Gareth O. Roberts, Andrew Gelman, and Walter R Gilks.  Weak convergence and optimal scaling of random walk Metropolis algorithms.  _Annals of Applied Probability_ , 7:110–120, 1997c.
  * Rosenthal [1995] Jeffrey S. Rosenthal.  Minorization conditions and convergence rates for Markov chain Monte Carlo.  _Journal of the American Statistical Association_ , 90:558–566, 1995.
  * Schmidler and Woodard [2011] Scott C. Schmidler and Dawn B. Woodard.  Lower bounds on the convergence rates of adaptive MCMC methods.  _Technical Report, Duke University_ , 2011.
  * Shun and McCullagh [1995] Zhenming Shun and Peter McCullagh.  Laplace approximation of high dimensional integrals.  _Journal of the Royal Statistical Society. Series B (Methodological)_ , 57(4):749–760, 1995.
  * Tang and Reid [2021] Yanbo Tang and Nancy Reid.  Laplace and saddlepoint approximations in high dimensions.  _preprint arXiv:2107.10885_ , 2021.
  * Tierney [1994] Luke Tierney.  Markov chains for exploring posterior distributions.  _The Annals of Statistics_ , 22:1701–1728, 1994.
  * Tierney [1998] Luke Tierney.  A note on Metropolis-Hastings kernels for general state spaces.  _The Annals of Applied Probability_ , 8:1–9, 1998.
  * Tierney and Kadane [1986] Luke Tierney and Joseph B. Kadane.  Accurate approximations for posterior moments and marginal densities.  _Journal of the American Statistical Association_ , 81(393):82–86, 1986.
  * Tierney et al. [1989] Luke Tierney, Robert E. Kass, and Joseph B. Kadane.  Approximate marginal densities of nonlinear functions.  _Biometrika_ , 76(3):425–433, 1989.
  * Vaart [1998] A. W. van der Vaart.  _Asymptotic Statistics_.  Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 1998.
  * Vats et al. [2022] D. Vats, F. B. Gonçalves, K. Łatuszyńki, and G. O. Roberts.  Efficient Bernoulli factory Markov chain Monte Carlo for intractable posteriors.  _Biometrika_ , 109:369–385, 2022.
  * Vats et al. [2019] Dootika Vats, James M. Flegal, and Galin L. Jones.  Multivariate output analysis for Markov chain Monte Carlo.  _Biometrika_ , 106:321–337, 2019.
  * Villani [2003] Cédric Villani.  _Topics in Optimal Transportation_.  Graduate studies in mathematics. American Mathematical Society, 2003.
  * Villani [2009] Cédric Villani.  _Optimal Transport: Old and New_.  Springer Berlin, Heidelberg, 1 edition, 2009.
  * Wang [2022] Guanyang Wang.  Exact convergence analysis of the independent Metropolis-Hastings algorithms.  _Bernoulli_ , 28(3):2012 – 2033, 2022.
  * Wang and Roy [2018] Xin Wang and Vivekananda Roy.  Geometric ergodicity of Pólya-gamma Gibbs sampler for Bayesian logistic regression with a flat prior.  _Electronic Journal of Statistics_ , 12(2):3295 – 3311, 2018.
  * Woodard et al. [2009] Dawn Woodard, Scott Schmidler, and Mark Huber.  Sufficient conditions for torpid mixing of parallel and simulated tempering.  _Electronic Journal of Probability_ , 14:780 – 804, 2009\.
  * Woodard [2015] Dawn B. Woodard.  A lower bound on the mixing time of uniformly ergodic Markov chains in terms of the spectral radius.  _preprint arXiv:1405.0028_ , 2015.
  * Yang and Rosenthal [2017] Jun Yang and Jeffrey S. Rosenthal.  Complexity results for MCMC derived from quantitative bounds.  _preprint arXiv:1708.00829_ , 2017.
  * Yang et al. [2016] Yun Yang, Martin J. Wainwright, and Michael I. Jordan.  On the computational complexity of high-dimensional Bayesian variable selection.  _Annals of Statistics_ , 44:2497–2532, 2016.
  * Zellner [1986] Arnold Zellner.  On assessing prior distributions and Bayesian regression analysis with g-prior distributions.  _Bayesian Inference and Decision Techniques: Essays in Honor of Bruno de Finetti_ , pages 233–243, 1986.
  * Zhuo and Gao [2021] Bumeng Zhuo and Chao Gao.  Mixing time of Metropolis-Hastings for Bayesian community detection.  _Journal of Machine Learning Research_ , 22(10):1–89, 2021.

##  Appendix A Proofs for Section 3

###### Proof of Theorem 1.

Fix $\theta\in\Theta$ and let $\varphi(\cdot)=I_{\\{\theta\\}}(\cdot)$. Then

$\int_{\Theta}\varphi dP(\theta,\cdot)=\int_{\Theta}\varphi
a(\theta,\cdot)dQ(\theta,\cdot)+[1-A(\theta)]\varphi(\theta)\geq[1-A(\theta)]\varphi(\theta).$

Applying this recursively we obtain for $t\geq 1$

$\int_{\Theta}\varphi dP^{t}(\theta,\cdot)=\int_{\Theta}\int_{\Theta}\varphi
dP^{t-1}(\theta,u)dP(u,\cdot)\geq[1-A(\theta)]^{t}\varphi(\theta).$

and, since $\pi$ is a Lebesgue density on $\Theta$, $\int_{\Theta}\varphi
d\Pi=0$.

Let $\Psi$ be the set of functions $\psi:\Theta\to[0,1]$. Notice that
$\varphi\in\Psi$ and, since $\pi$ is a Lebesgue density on $\Theta$,
$\int_{\Theta}\varphi d\Pi=0$. Thus,

$\displaystyle\left\lVert P^{t}(\theta,\cdot)-\Pi\right\rVert_{\text{TV}}$
$\displaystyle=\sup_{\psi\in\Psi}\left|\int_{\Theta}\psi
dP^{t}(\theta,\cdot)-\int_{\Theta}\psi d\Pi\right|$
$\displaystyle\geq\left|\int_{\Theta}\varphi
dP^{t}(\theta,\cdot)-\int_{\Theta}\varphi d\Pi\right|$
$\displaystyle=\int_{\Theta}\varphi dP^{t}(\theta,\cdot)$
$\displaystyle\geq[1-A(\theta)]^{t}.$

∎

###### Proof of Proposition 1.

Since, $a_{1}(\theta,\theta^{\prime})\geq a_{2}(\theta,\theta^{\prime})$ for
all $\theta,\theta^{\prime}$ we have

$1-A_{1}(\theta)\leq 1-A_{2}(\theta)$

and the claim follows from Theorem 1. ∎

###### Proof of Proposition 2.

Fix $\theta_{0}\in\Theta$. By regularity of $\Pi$ [29, Lemma 1.36], we can
find a sequence
$B_{r_{n}}(\theta_{0})=\\{x\in\Theta:d(x,\theta_{0})<r_{n}\\}\subseteq\Theta$
of open balls with radius $r_{n}$ centered at $\theta_{0}$ such that

$\lim_{n}\Pi(B_{r_{n}}(\theta_{0}))=\Pi(\\{\theta_{0}\\})=0.$

We can choose $n$ large enough so that $\Pi(B_{r_{n}}(\theta_{0}))<1$. Since
$\theta_{0}\in\Theta$ and $B_{r_{n}}(\theta_{0})\subseteq\Theta$, then by
assumption on the support of $\pi$ and since $\lambda$ is strictly positive,
then

$\Pi(B_{r_{n}}(\theta_{0}))=\int_{B_{r_{n}}(\theta_{0})}\pi d\lambda>0.$

For $x\in B_{r_{n}}(\theta_{0})$, $\delta_{x}(B_{r_{n}}(\theta_{0})^{c})=0$
and so,

$\displaystyle
k_{P}\leq\frac{\int_{B_{r}}P(\cdot,B_{r_{n}}(\theta_{0})^{c})d\Pi}{\Pi(B_{r_{n}}(\theta_{0}))\Pi(B_{r_{n}}(\theta_{0})^{c})}$
$\displaystyle=\frac{\int_{B_{r_{n}}(\theta_{0})}\int_{B_{r_{n}}(\theta_{0})^{c}}a(\cdot,\cdot)dQ(\cdot,\cdot)d\Pi}{\Pi(B_{r_{n}}(\theta_{0}))\Pi(B_{r_{n}}(\theta_{0})^{c})}$
$\displaystyle\leq\frac{\int_{B_{r_{n}}(\theta_{0})}A(\cdot)d\Pi}{\Pi(B_{r_{n}}(\theta_{0}))\Pi(B_{r_{n}}(\theta_{0})^{c})}$
$\displaystyle\leq\frac{\sup_{x\in
B_{r_{n}}(\theta_{0})}A(x)}{\Pi(B_{r_{n}}(\theta_{0})^{c})}.$ (4)

Choose a sequence $x^{*}_{n}\in B_{r_{n}}(\theta_{0})$ such that

$\sup_{x\in B_{r_{n}}(\theta_{0})}A(x)\leq A(x^{*}_{n})+1/n.$

Since $d(x^{*}_{n},\theta_{0})<r_{n}$, then
$\lim_{n\to\infty}d(x^{*}_{n},\theta_{0})=0$. By upper semicontinuity of
$A(\cdot)$ and taking the limit superior of (4), we have

$k_{P}\leq\limsup_{n\to\infty}\frac{\sup_{x\in
B_{r_{n}}(\theta_{0})}A(x)}{1-\Pi(B_{r_{n}}(\theta_{0}))}\leq\limsup_{n\to\infty}A(x^{*}_{n})\leq
A(\theta_{0}).$

Since this holds for every $\theta_{0}\in\Theta$, the desired result follows
by taking the infimum. ∎

##  Appendix B Proofs for Section 4

###### Proof of Proposition 3.

For all $\theta^{\prime}$, $\theta$,

$q(\theta,\theta^{\prime})\leq(2\pi h)^{-d/2}\det(C)^{-1/2}$

and hence

$\displaystyle A(\theta_{0})$
$\displaystyle=\int_{\Theta}\left\\{1\wedge\frac{\pi(\theta^{\prime})q(\theta^{\prime},\theta_{0})}{\pi(\theta_{0})q(\theta_{0},\theta^{\prime})}\right\\}q(\theta_{0},\theta^{\prime})d\theta^{\prime}$
$\displaystyle=\int_{\Theta}\left\\{\frac{q(\theta_{0},\theta^{\prime})}{\pi(\theta^{\prime})}\wedge\frac{q(\theta^{\prime},\theta_{0})}{\pi(\theta_{0})}\right\\}\pi(\theta^{\prime})d\theta^{\prime}$
$\displaystyle\leq\int_{\Theta}\frac{q(\theta^{\prime},\theta_{0})}{\pi(\theta_{0})}\pi(\theta^{\prime})d\theta^{\prime}$
$\displaystyle\leq\frac{1}{\pi(\theta_{0})(2\pi h)^{d/2}\det(C)^{1/2}}.$ (5)

∎

###### Proof of Proposition 4.

By the subgradient inequality [38, Corollary 3.2.1], for every
$\theta,\theta_{0}\in\Theta$ and $v\in\partial f(\theta_{0})$,

$\displaystyle f(\theta)-f(\theta_{0})$ $\displaystyle\geq
v^{T}(\theta-\theta_{0})+\frac{1}{2\xi}\left\lVert\theta-\theta_{0}\right\rVert_{2}^{2}.$

Thus,

$\displaystyle A(\theta_{0})$ $\displaystyle\leq\frac{1}{(2\pi
h)^{d/2}}\int\exp\left\\{f(\theta_{0})-f(\theta)\right\\}\exp\left\\{-\frac{1}{2h}\left\lVert\theta-\theta_{0}\right\rVert_{2}^{2}\right\\}d\theta$
$\displaystyle\leq\frac{1}{(2\pi
h)^{d/2}}\int\exp\left\\{v^{T}(\theta_{0}-\theta)+\frac{1}{2\xi}\left\lVert\theta-\theta_{0}\right\rVert_{2}^{2}\right\\}\exp\left\\{-\frac{1}{2h}\left\lVert\theta-\theta_{0}\right\rVert_{2}^{2}\right\\}d\theta$

and a routine calculation involving completing the square yields the claim. ∎

###### Proof of Proposition 5.

To apply Proposition 4, it will be shown that with probability 1, for
sufficiently large $n$, the target density is strongly convex.

Notice that, with probability $1$, if $d_{n}/n\to\gamma\in(0,1)$, then

$\lambda_{min}\left(\frac{1}{n}X^{T}X\right)\geq\frac{1}{2}(1-\sqrt{\gamma})^{2}$

for all $n$ sufficiently large [5, Theorem 2]. Define

$f_{n}(\beta)=\frac{1}{n}\sum_{i=1}^{n}\left[\log\left(1+\exp\left(\beta^{T}X_{i}\right)\right)-Y_{i}\beta^{T}X_{i}\right]+\frac{1}{2gn}\beta^{T}X^{T}X\beta,$

and write the posterior density $\pi_{n}\propto\exp(-nf_{n})$. Let
${\nabla}^{2}f_{n}$ denote the Hessian of $f_{n}$. For every
$v,u\in\mathbb{R}^{d}$,

$u^{T}{\nabla}^{2}f_{n}(v)u\geq\frac{1}{gn}u^{T}X^{T}Xu\geq\frac{(1-\sqrt{\gamma})^{2}}{2g}\left\lVert
u\right\rVert_{2}^{2}.$

Then $nf_{n}(\cdot)$ is strongly convex with convexity parameter
$\frac{n(1-\sqrt{\gamma})^{2}}{2g}$ on $\mathbb{R}^{d}$ with probability $1$
[38, Theorem 2.1.11]. ∎

###### Proof of Proposition 6.

Take $n$ sufficiently large so that the each of the assumptions hold. After
changing the variables, obtain the decomposition

$\displaystyle\frac{1}{\pi(\theta^{*}_{n})}$
$\displaystyle=\int_{\mathbb{R}^{d}}\exp(-n(f_{n}(\theta)-f_{n}(\theta_{n}^{*})))d\theta$
$\displaystyle=\frac{1}{n^{d/2}}\int_{\left\lVert
un^{-1/2}\right\rVert_{2}\leq\delta_{0}}\exp(-n(f_{n}(\theta_{n}^{*}+un^{-1/2})-f_{n}(\theta_{n}^{*})))du$
(6) $\displaystyle\hskip 11.38092pt+\int_{\left\lVert
v\right\rVert_{2}>\delta_{0}}\exp(-n(f_{n}(\theta_{n}^{*}+v)-f_{n}(\theta_{n}^{*})))dv.$
(7)

Consider the first integral (6). Since the closed ball
$\overline{B_{\delta_{0}}(\theta_{n}^{*})}$ is convex, for all $\left\lVert
un^{-1/2}\right\rVert_{2}\leq\delta_{0}$, by the subgradient inequality [38,
Lemma 3.2.3],

$\displaystyle nf_{n}(\theta^{*}_{n}+un^{-1/2})-nf_{n}(\theta^{*}_{n})$
$\displaystyle\geq\frac{1}{2\lambda_{0}}\left\lVert u\right\rVert_{2}^{2}.$

This implies

$\displaystyle\frac{1}{n^{d_{n}/2}}\int_{\left\lVert
n^{-1/2}u\right\rVert_{2}\leq\delta_{0}}\exp(nf_{n}(\theta^{*}_{n})-nf_{n}(\theta^{*}_{n}+un^{-1/2}))du$
$\displaystyle\leq\frac{1}{n^{d_{n}/2}}\int_{\left\lVert
un^{-1/2}\right\rVert_{2}\leq\delta_{0}}\exp\left(-\frac{1}{2\lambda_{0}}\left\lVert
u\right\rVert_{2}^{2}\right)du$
$\displaystyle\leq\left(\frac{2\pi\lambda_{0}}{n}\right)^{d_{n}/2}.$

Consider the second integral (7). We have

$\displaystyle\int_{\left\lVert
v\right\rVert_{2}>\delta_{0}}\exp\left(-n\left(f_{n}(\theta_{n}^{*}+v)-f_{n}(\theta_{n}^{*})\right)\right)dv$
$\displaystyle=\int_{\left\lVert
v\right\rVert_{2}>\delta_{0}}\exp\left(-(n-1)\left(f_{n}(\theta_{n}^{*}+v)-f_{n}(\theta_{n}^{*})\right)-\left(f_{n}(\theta_{n}^{*}+v)-f_{n}(\theta_{n}^{*})\right)\right)dv$
$\displaystyle\leq e^{-(n-1)f^{*}}\int_{\left\lVert
v\right\rVert_{2}>\delta_{0}}\exp\left(-\left(f_{n}(\theta_{n}^{*}+v)-f_{n}(\theta_{n}^{*})\right)\right)dv$
$\displaystyle\leq e^{-(n-1)f^{*}}(I_{0}n)^{d_{n}}.$

Combining these results,

$\displaystyle\int_{\mathbb{R}^{d}}\exp(-n(f_{n}(\theta)-f_{n}(\theta_{n}^{*})))d\theta$
$\displaystyle\leq\left(\frac{2\pi\lambda_{0}}{n}\right)^{d_{n}/2}\left[1+\left(\frac{n}{2\pi\lambda_{0}}\right)^{d_{n}/2}e^{-(n-1)f^{*}}(I_{0}n)^{d_{n}}\right].$

Since $d_{n}\leq n^{\kappa}$,

$\displaystyle\limsup_{n\to\infty}\left(\frac{n}{2\pi\lambda_{0}}\right)^{d_{n}/2}e^{-(n-1)f^{*}}(I_{0}n)^{d_{n}}=0.$

The desired result follows at once. ∎

###### Proof of Theorem 3.

The proof will show the conditions of Proposition 6 hold with probability $1$
for large enough $n$. Using Assumption 1, with probability $1$, assume $n$ is
sufficiently large so that the posterior density $\pi_{n}^{*}$ and the MLE
$\beta^{*}_{n}$ exist. Define

$f_{n}(\beta)=\frac{1}{n}\sum_{i=1}^{n}\left[\log\left(1+\exp\left(\beta^{T}X_{i}\right)\right)-Y_{i}\beta^{T}X_{i}\right]$

and write $\pi_{n}^{*}=Z_{n}^{-1}\exp(-nf_{n})$ where
$Z_{n}=\int\exp(-nf_{n}(\beta))d\beta$. The first step is to develop
sufficient curvature of the target density at $\beta_{n}^{*}$. Denote the
$k$th derivative matrix or tensor of the function $f_{n}$ by
${\nabla}^{k}f_{n}$. Recall that $s$ is the sigmoid function. For every
$v\in\mathbb{R}^{d}$,

$v^{T}{\nabla}^{2}f_{n}(\beta_{n}^{*})v=\frac{1}{n}\sum_{i=1}^{n}v^{T}X_{i}X_{i}^{T}vs\left(X_{i}^{T}\beta_{n}^{*}\right)\left(1-s\left(X_{i}^{T}\beta_{n}^{*}\right)\right)$

and

${\nabla}^{3}f_{n}(\beta_{n}^{*})v^{(3)}=\frac{1}{n}\sum_{i=1}^{n}(X_{i}^{T}v)^{3}s\left(X_{i}^{T}\beta_{n}^{*}\right)\left(1-s\left(X_{i}^{T}\beta_{n}^{*}\right)\right)\left(1-2s\left(X_{i}^{T}\beta_{n}^{*}\right)\right).$

Since $\left\lVert X_{i}\right\rVert_{2}\leq 1$ with probability $1$, by the
strong law of large numbers [17, Theorem 10.13], almost surely,

$\displaystyle{\nabla}^{2}f_{n}(\beta_{0})$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}X_{i}X_{i}^{T}s\left(X_{i}^{T}\beta_{0}\right)\left(1-s\left(X_{i}^{T}\beta_{0}\right)\right)$
$\displaystyle\to\mathbb{E}\left(X_{1}X_{1}^{T}s\left(X_{1}^{T}\beta_{0}\right)\left(1-s\left(X_{1}^{T}\beta_{0}\right)\right)\right).$

By Assumption 4, for any $u\in\mathbb{R}^{d}$, $u\not=0$, with probability
$1$,

$u^{T}X_{1}X_{1}^{T}us\left(X_{1}^{T}\beta_{0}\right)\left(1-s\left(X_{1}^{T}\beta_{0}\right)\right)>0.$

Since expectations preserve strict inequalities, there is a sufficiently small
$\epsilon_{0}\in(0,1)$ so that for any $u\in\mathbb{R}^{d}$, $u\not=0$,

$\left(\frac{u}{\left\lVert
u\right\rVert_{2}}\right)^{T}\mathbb{E}\left(X_{1}X_{1}^{T}s\left(X_{1}^{T}\beta_{0}\right)\left(1-s\left(X_{1}^{T}\beta_{0}\right)\right)\right)\left(\frac{u}{\left\lVert
u\right\rVert_{2}}\right)\geq\epsilon_{0}.$

Combining these results, for all $u\in\mathbb{R}^{d}$, with probability $1$,

$\displaystyle u^{T}{\nabla}^{2}f_{n}(\beta_{0})u$
$\displaystyle\geq\frac{\epsilon_{0}}{2}\left\lVert u\right\rVert_{2}^{2}$

for all sufficiently large $n$. By Assumption 3, $\left\lVert
X_{i}\right\rVert_{2}\leq 1$ with probability $1$ and $|x(1-x)(1-2x)|\leq
1/4$, so by the mean value theorem, almost surely,

$\left\lVert{\nabla}^{2}f_{n}(\beta_{n}^{*})-{\nabla}^{2}f_{n}(\beta_{0})\right\rVert_{2}\leq
4^{-1}\left\lVert\beta^{*}_{n}-\beta_{0}\right\rVert_{2}\to 0.$

For all $u\in\mathbb{R}^{d}$, with probability $1$, for all $n$ sufficiently
large,

$\displaystyle u^{T}{\nabla}^{2}f_{n}(\beta_{n}^{*})u$ $\displaystyle\geq
u^{T}{\nabla}^{2}f_{n}(\beta_{0})u-\frac{\epsilon_{0}}{4}\left\lVert
u\right\rVert_{2}^{2}$ $\displaystyle\geq\frac{\epsilon_{0}}{4}\left\lVert
u\right\rVert_{2}^{2}.$ (8)

For the remainder of this argument, assume $n$ is sufficiently large so that
(8) holds with probability $1$ and the remainder of the proof is taken to hold
with probability $1$ without reference. Since $\left\lVert
X_{i}\right\rVert_{2}\leq 1$, for all $u\in\mathbb{R}^{d}$ and
$t\in(0,\infty)$,

$|{\nabla}^{3}f_{n}(\beta_{n}^{*}+tu)u^{(3)}|\leq\left\lVert
u\right\rVert_{2}u^{T}{\nabla}^{2}f_{n}(\beta_{n}^{*}+tu)u.$

It is immediate that [4, Proposition 1 (6)] for $\left\lVert
v\right\rVert_{2}\leq 2$ and all $u,v\in\mathbb{R}^{d}$,

$u^{T}{\nabla}^{2}f_{n}(\beta_{n}^{*}+v)u\geq
u^{T}{\nabla}^{2}f_{n}(\beta_{n}^{*})u\exp(-\left\lVert
v\right\rVert_{2})\geq\frac{\epsilon_{0}}{4}\exp(-2)\left\lVert
u\right\rVert_{2}^{2}.$

Since closed balls are convex, $f_{n}$ is strongly convex on the closed ball
$\overline{B_{2}(\beta_{n}^{*})}$ [38, Theorem 2.1.11]. Thus, the local strong
convexity condition (1) in Proposition 6 holds.

Since $\nabla f_{n}(\beta_{n}^{*})\equiv 0$ [4, Proposition 1 (3)]

$f_{n}(\beta_{n}^{*}+v)-f_{n}(\beta_{n}^{*})\geq\frac{v^{T}{\nabla}^{2}f_{n}(\beta_{n}^{*})v}{\left\lVert
v\right\rVert_{2}^{2}}\left(\exp(-\left\lVert v\right\rVert_{2})+\left\lVert
v\right\rVert_{2}-1\right)$

Using (8) and the fact that $e^{-x}\geq 1-x$, obtain, for all
$v\in\mathbb{R}^{d}$ with $v\not=0$,

$\displaystyle\frac{v^{T}{\nabla}^{2}f_{n}(\beta_{n}^{*})v}{\left\lVert
v\right\rVert_{2}^{2}}\left(\exp(-\left\lVert v\right\rVert_{2})+\left\lVert
v\right\rVert_{2}-1\right)$
$\displaystyle\geq\frac{\epsilon_{0}}{4}\left(\exp(-\left\lVert
v\right\rVert_{2})+\left\lVert v\right\rVert_{2}-1\right)$
$\displaystyle\geq\frac{\epsilon_{0}}{4}\left(\left\lVert
v\right\rVert_{2}-1\right).$

Hence, for all $v\in\mathbb{R}^{d}$ with $v\not=0$,

$f_{n}(\beta_{n}^{*}+v)-f_{n}(\beta_{n}^{*})\geq\frac{\epsilon_{0}}{4}\left(\left\lVert
v\right\rVert_{2}-1\right).$

Thus, for $\left\lVert v\right\rVert_{2}>2$, the strict optimality condition
(2) in Proposition 6 holds.

The required control of the integral (3) in Proposition 6 also holds since

$\displaystyle\int_{\left\lVert
v\right\rVert_{2}>2}\exp\left(-\left(f_{n}(\beta_{n}^{*}+v)-f_{n}(\beta_{n}^{*})\right)\right)dv$
$\displaystyle\leq e^{\frac{\epsilon_{0}}{4}}\int_{\left\lVert
v\right\rVert_{2}>2}\exp\left(-\frac{\epsilon_{0}}{4}\left\lVert
v\right\rVert_{2}\right)dv<\infty.$

∎

##  Appendix C Proofs for Section 5

###### Proof of Theorem 4.

We will first construct a suitable Lipschitz function. Fix
$\theta\in\mathbb{R}^{d}$, and fix $\alpha\in(0,\infty)$. Define the function
$\varphi_{\alpha,\theta}:\mathbb{R}^{d}\to\mathbb{R}$ by
$\varphi_{\alpha,\theta}(\omega)=\exp\left(-\alpha\left\lVert\omega-\theta\right\rVert_{1}\right)$.
We have for every $\omega,\omega^{\prime}\in\mathbb{R}^{d}$,

$\displaystyle|\varphi_{\alpha,\theta}(\omega)-\varphi_{\alpha,\theta}(\omega^{\prime})|$
$\displaystyle=|\exp\left(-\alpha\left\lVert\omega-\theta\right\rVert_{1}\right)-\exp\left(-\alpha\left\lVert\omega^{\prime}-\theta\right\rVert_{1}\right)|$
$\displaystyle\leq\alpha|\left\lVert\omega-\theta\right\rVert_{1}-\left\lVert\omega^{\prime}-\theta\right\rVert_{1}|$
$\displaystyle\leq\alpha\left\lVert\omega-\omega^{\prime}\right\rVert_{1}.$

Therefore, $\alpha^{-1}\varphi_{\alpha,\theta}$ is a bounded Lipschitz
function with respect to the distance $\left\lVert\cdot\right\rVert_{1}$ and
the Lipschitz constant is $1$. By assumption there exists $s$ such that
$\pi\leq s$. Then, using the fact that
$\int_{\mathbb{R}^{d}}\exp\left(-\alpha\left\lVert\theta^{\prime}-\theta\right\rVert_{1}\right)d\theta^{\prime}=2^{d}\alpha^{-d}$,
we obtain

$\displaystyle\int\varphi_{\alpha,\theta}(\theta^{\prime})\pi(\theta^{\prime})d\theta^{\prime}$
$\displaystyle\leq
s\int_{\mathbb{R}^{d}}\exp\left(-\alpha\left\lVert\theta^{\prime}-\theta\right\rVert_{1}\right)d\theta^{\prime}$
$\displaystyle=s2^{d}\alpha^{-d}.$ (9)

Fix a positive integer $t$. Then, for each $s\in\\{0,\ldots,t-1\\}$ and each
$\omega\in\mathbb{R}^{d}$, we obtain the lower bound

$\displaystyle\int\varphi_{\alpha,\theta}(\theta^{\prime})\left(1-A(\theta^{\prime})\right)^{s}P(\omega,d\theta^{\prime})$
$\displaystyle=\int\varphi_{\alpha,\theta}(\theta^{\prime})\left(1-A(\theta^{\prime})\right)^{s}a(\omega,\theta^{\prime})dQ(\omega,\theta^{\prime})+\varphi_{\alpha,\theta}(\omega)\left(1-A(\omega)\right)^{s+1}$
$\displaystyle\geq\varphi_{\alpha,\theta}(\omega)\left(1-A(\omega)\right)^{s+1}.$

We now apply this lower bound multiple times:

$\displaystyle\int\varphi_{\alpha,\theta}(\theta_{t})P^{t}(\theta,d\theta_{t})$
$\displaystyle=\int\left\\{\int\varphi_{\alpha,\theta}(\theta_{t})P(\theta_{t-1},d\theta_{t})\right\\}P^{t-1}(\theta,d\theta_{t-1})$
$\displaystyle\geq\int\varphi_{\alpha,\theta}(\theta_{t-1})\left(1-A(\theta_{t-1})\right)P^{t-1}(\theta,d\theta_{t-1})$
$\displaystyle\vdots$
$\displaystyle\geq\varphi_{\alpha,\theta}(\theta)\left(1-A(\theta)\right)^{t}$
$\displaystyle=\left(1-A(\theta)\right)^{t}.$ (10)

The final step follows from the fact that $\varphi_{\alpha,\theta}(\theta)=1$.
Combining (9) and (10), we then have the lower bound,

$\displaystyle\int\left(\frac{1}{\alpha}\varphi_{\alpha,\theta}\right)dP^{t}(\theta,\cdot)-\int\left(\frac{1}{\alpha}\varphi_{\alpha,\theta}\right)d\Pi\geq\frac{\left(1-A(\theta)\right)^{t}-s2^{d}\alpha^{-d}}{\alpha}.$
(11)

The case where
$\mathcal{W}_{\left\lVert\cdot\right\rVert_{1}}(P^{t}(\theta,\cdot),\Pi)=+\infty$
is trivial so we assume this is finite. We then have by the Kantovorich-
Rubinstein theorem [62, Theorem 1.14] and the lower bound in (11),

$\displaystyle\mathcal{W}_{\left\lVert\cdot\right\rVert_{1}}(P^{t}(\theta,\cdot),\Pi)$
$\displaystyle\geq\sup_{\left\lVert\varphi\right\rVert_{\text{Lip}(\left\lVert\cdot\right\rVert_{1})}\leq
1}\left[\int\varphi dP^{t}(\theta,\cdot)-\int\varphi d\Pi\right]$
$\displaystyle\geq\int\left(\frac{1}{\alpha}\varphi_{\alpha,\theta}\right)dP^{t}(\theta,\cdot)-\int\left(\frac{1}{\alpha}\varphi_{\alpha,\theta}\right)d\Pi$
$\displaystyle\geq\frac{\left(1-A(\theta)\right)^{t}-s2^{d}\alpha^{-d}}{\alpha}.$

If $A(\theta)=1$, then taking the limit of $\alpha\to\infty$, completes the
proof. Suppose then that $A(\theta)<1$. Maximizing this lower bound with
respect to $\alpha$ yields
$\alpha=2s^{\frac{1}{d}}(1+d)^{\frac{1}{d}}\left(1-A(\theta)\right)^{-\frac{t}{d}}$.
We then have

$\displaystyle\frac{\left(1-A(\theta)\right)^{t}-s2^{d}\alpha^{-d}}{\alpha}$
$\displaystyle=\frac{\left(1-\frac{1}{1+d}\right)}{2s^{\frac{1}{d}}\left(1+d\right)^{\frac{1}{d}}}\left(1-A(\theta)\right)^{t\left(1+\frac{1}{d}\right)}.$

This completes the proof for the norm $\left\lVert\cdot\right\rVert_{1}$ and
by assumption, $\mathcal{W}_{c}(\cdot,\cdot)\geq
C_{0,d}\mathcal{W}_{\left\lVert\cdot\right\rVert_{1}}(\cdot,\cdot)$.

Finally, let $\Gamma$ be a coupling for $P^{t}(\theta,\cdot)$ and $\Pi$. Using
Hölder’s inequality [17, Theorem 6.2] with $1/p+1/q=1$,

$\displaystyle\mathcal{W}_{c}^{1}(P^{t}(\theta,\cdot),\Pi)$
$\displaystyle\leq\int c(\theta^{\prime},\omega^{\prime})\cdot
1d\Gamma(\theta^{\prime},\omega^{\prime})$ $\displaystyle\leq\left(\int
c(\theta^{\prime},\omega^{\prime})^{p}d\Gamma(\theta^{\prime},\omega^{\prime})\right)^{1/p}\left(\int
1^{q}d\Gamma(\theta,\theta^{\prime})\right)^{1/q}$
$\displaystyle\leq\left(\int
c(\theta^{\prime},\omega^{\prime})^{p}d\Gamma(\theta^{\prime},\omega^{\prime})\right)^{1/p}.$

Taking the infimum over $\Gamma$ completes the proof. ∎

###### Proof of Proposition 8.

It will suffice to show (ii) implies (i) [18, Theorem 2.1]. Condition (ii)
implies convergence in the bounded Lipschitz norm, that is,

$\sup\left\\{\int\varphi d\mu P^{t}-\int\varphi
d\Pi:\left\lVert\varphi\right\rVert_{\text{Lip}(d)}+\sup_{x}|\varphi(x)|\leq
1\right\\}\leq C_{\mu}\rho^{t}.$

The following proof is similar to that of an existing result [22, Proposition
2.8]. Let $t\in\mathbb{Z}_{+}$ and let $\varphi:\Omega\to\mathbb{R}$ be a non-
negative, bounded, Lipschitz with Lispchitz constant
$L(\varphi)\in(0,\infty)$. We can assume $\varphi>0$ on some positive
probability of $\Pi$ so that $\int\varphi d\Pi>0$. Then we can define
$g=\varphi/\int\varphi d\Pi$ so that $\int gd\Pi=1$. The function $g$ is
Lipschitz since for $x,y\in\Omega$,

$|g(x)-g(y)|=\frac{|\varphi(x)-\varphi(y)|}{\int\varphi
d\Pi}\leq\frac{L(\varphi)}{\int\varphi d\Pi}d(x,y).$

Define the probability measure by $\mu_{\varphi}(B)=\int_{B}gd\Pi$ and so
$\mu_{\varphi}\in L^{2}(\Pi)$. We have constructed $g$ so that

$\left\lVert
g\right\rVert_{\text{Lip}(d)}+\sup_{x}|g(x)|\leq\frac{L(\varphi)}{\int\varphi
d\Pi}+\frac{\sup_{x}|\varphi(x)|}{\int\varphi d\Pi}.$

By (ii), there is a constant $C_{\mu_{\varphi}}\in(0,\infty)$ such that

$\int gd\mu_{\varphi}P^{t}-\int gd\Pi\leq
C_{\mu_{\varphi}}\left[\frac{L(\varphi)}{\int\varphi
d\Pi}+\frac{\sup_{x}|\varphi(x)|}{\int\varphi d\Pi}\right]\rho^{t}.$

By reversibility, $\int(P^{n}g)^{2}d\Pi=\int(P^{2n}g)gd\Pi$. We then have

$\displaystyle\frac{1}{(\int\varphi d\Pi)^{2}}\left\lVert
P^{t}\varphi-\int\varphi d\Pi\right\rVert_{L^{2}(\Pi)}^{2}$
$\displaystyle=\left\lVert P^{t}g-\int gd\Pi\right\rVert_{L^{2}(\Pi)}^{2}$
$\displaystyle=\int(P^{t}g)^{2}d\Pi-\left(\int gd\Pi\right)^{2}$
$\displaystyle=\int(P^{2t}g)gd\Pi-\int gd\Pi$ $\displaystyle=\int
g\mu_{\varphi}P^{2t}-\int gd\Pi$ $\displaystyle\leq
C_{\mu_{\varphi}}\left[\frac{L(\varphi)}{\int\varphi
d\Pi}+\frac{\sup_{x}|\varphi(x)|}{\int\varphi d\Pi}\right]\rho^{2t}.$

Now let $\varphi:\Omega\to\mathbb{R}$ be a bounded, Lipschitz function with
Lipschitz constant $L(\varphi)\in(0,\infty)$. Denote the positive and negative
parts of $\varphi$ by $\varphi^{+},\varphi^{-}$. There are then constants
$C_{\mu_{\varphi^{+}}},C_{\mu_{\varphi^{-}}}\in(0,\infty)$ such that

$\displaystyle\left\lVert P^{t}\varphi-\int\varphi
d\Pi\right\rVert_{L^{2}(\Pi)}^{2}$ $\displaystyle\leq
2C_{\mu_{\varphi^{+}}}\int\varphi^{+}d\Pi\left[L(\varphi)+\sup_{x}|\varphi^{+}(x)|\right]\rho^{2t}$
$\displaystyle\hskip
11.38092pt+2C_{\mu_{\varphi^{-}}}\int\varphi^{-}d\Pi\left[L(\varphi)+\sup_{x}|\varphi^{-}(x)|\right]\rho^{2t}.$

This holds for arbitrary $t$ and so applying [22, Lemma 2.9],

$\left\lVert P^{t}\varphi-\int\varphi
d\Pi\right\rVert_{L^{2}(\Pi)}^{2}\leq\rho^{2t}\left\lVert\varphi-\int\varphi
d\Pi\right\rVert_{L^{2}(\Pi)}^{2}.$

Now let $\varphi:\Omega\to\mathbb{R}$ be a bounded, lower semicontinuous
function with $\int\varphi d\Pi=0$. The approximation
$\varphi_{m}(\cdot)=\inf_{y}[\varphi(y)+md(\cdot,y)]$ is Lipschitz continuous,
uniformly bounded and $\varphi_{m}\uparrow\varphi$ pointwise. Now by the
dominated convergence theorem [17, Theorem 2.24], $P\varphi_{m}\uparrow
P\varphi$ pointwise. By the dominated convergence theorem and since
$\varphi_{m}$ is bounded and Lipschitz,

$\displaystyle\left\lVert P\varphi\right\rVert_{L^{2}(\Pi)}^{2}$
$\displaystyle=\lim_{m\to\infty}\left\lVert
P\varphi_{m}\right\rVert_{L^{2}(\Pi)}^{2}$
$\displaystyle\leq\rho^{2}\lim_{m\to\infty}\left\lVert\varphi_{m}\right\rVert_{L^{2}(\Pi)}^{2}$
$\displaystyle=\rho^{2}\left\lVert\varphi\right\rVert_{L^{2}(\Pi)}^{2}.$

Now let $\varphi\in L^{2}(\Pi)$ with $\int\varphi d\Pi=0$. By [29, Lemma
1.37], we can choose a sequence $(\varphi_{m})_{m}$ of bounded, continuous
functions converging to $\varphi$ in $L^{2}(\Pi)$. By reversibility and
Jensen’s inequality,

$\displaystyle\int(P\varphi_{m}-P\varphi)^{2}d\Pi$
$\displaystyle\leq\int\int(\varphi_{m}(y)-\varphi(y))^{2}dP(x,y)d\Pi(x)$
$\displaystyle=\int\int(\varphi_{m}(y)-\varphi(y))^{2}d\Pi(y)dP(y,x)$
$\displaystyle\to 0.$

So, if $\varphi_{m}\to\varphi$ in $L^{2}(\Pi)$, then $P\varphi_{m}\to
P\varphi$ in $L^{2}(\Pi)$ as well. Therefore, since $\varphi_{m}$ is bounded
and lower semicontinuous, after taking limits, we conclude

$\displaystyle\left\lVert P\varphi\right\rVert_{L^{2}(\Pi)}^{2}$
$\displaystyle\leq\rho^{2}\left\lVert\varphi\right\rVert_{L^{2}(\Pi)}^{2}.$

The condition $\int\varphi d\Pi=0$ can be extended to all of $L^{2}(\Pi)$ by
shifting $\varphi$ and thus this holds for all of $L^{2}(\Pi)$. ∎