# Explicit convergence bounds for Metropolis Markov chains: isoperimetry,
spectral gaps and profiles

Christophe Andrieu, Anthony Lee, Sam Power, Andi Q. Wang
School of Mathematics, University of Bristol

###### Abstract

We derive the first explicit bounds for the spectral gap of a random walk
Metropolis algorithm on $\mathbb{R}^{d}$ for any value of the proposal
variance, which when scaled appropriately recovers the correct $d^{-1}$
dependence on dimension for suitably regular invariant distributions. We also
obtain explicit bounds on the ${\rm L}^{2}$-mixing time for a broad class of
models. In obtaining these results, we refine the use of isoperimetric profile
inequalities to obtain conductance profile bounds, which also enable the
derivation of explicit bounds in a much broader class of models. We also
obtain similar results for the preconditioned Crank–Nicolson Markov chain,
obtaining dimension-independent bounds under suitable assumptions.

###### Contents

  1. 1 Introduction
    1. 1.1 Results for Metropolis Markov chains
    2. 1.2 Roadmap
    3. 1.3 Related work
    4. 1.4 Notation
  2. 2 Conductance profile, spectral profile, and mixing time bounds
  3. 3 From isoperimetric profiles and close coupling to mixing time bounds
    1. 3.1 General results
    2. 3.2 Examples of isoperimetric profiles
      1. 3.2.1 Specific examples
      2. 3.2.2 Functional inequalities
      3. 3.2.3 Transfer principles
    3. 3.3 From spectral profile to mixing times: examples
  4. 4 Spectral gap of RWM in high dimensions
    1. 4.1 Lower bound on the conductance and spectral gap
    2. 4.2 Conductance and spectral gap upper bounds
      1. 4.2.1 Conductance upper bounds
      2. 4.2.2 Spectral gap upper bounds
    3. 4.3 Implications for the asymptotic variance
    4. 4.4 Discussion of the assumptions
  5. 5 Convergence and mixing time for RWM
    1. 5.1 Three phase mixing
    2. 5.2 Two feasible “warm starts”
    3. 5.3 Comparisons to existing results
  6. 6 Convergence and mixing time for pCN
    1. 6.1 Lower bounds for pCN
    2. 6.2 Mixing time for pCN
  7. A Additional proofs

##  1 Introduction

###  1.1 Results for Metropolis Markov chains

Let $\pi$ be a probability distribution on
$\left(\mathsf{E},\mathcal{\mathscr{E}}\right)$, where
$\mathsf{E}=\mathbb{R}^{d}$ and $\mathscr{E}$ denotes its Borel
$\sigma$-algebra, and suppose we seek to approximately sample from $\pi$.
Markov chain Monte Carlo (MCMC) algorithms address this problem by simulating
an ergodic, time-homogeneous Markov chain
$\left(X_{n}\right)_{n\in\mathbb{N}}$ with invariant distribution $\pi$. One
of the most simple and yet enduringly popular MCMC algorithms is the
Metropolis algorithm of Metropolis et al. (1953). Assuming that $\pi$ has
density $\varpi={\rm d}\pi/{\rm d}\nu$ with respect to some $\sigma$-finite
measure $\nu$, and $Q$ is a $\nu$-reversible Markov kernel, a Metropolis
Markov kernel may be written

$P\left(x,A\right)=\int_{A}Q\left(x,{\rm d}y\right)\alpha\left(x,y\right)+{\bf
1}_{A}\left(x\right)\bar{\alpha}\left(x\right),\qquad
x\in\mathsf{E},A\in\mathscr{E}.$ (1)

where for $x,y\in\mathsf{E}$,

$\alpha\left(x,y\right):=1\wedge\frac{\varpi\left(y\right)}{\varpi\left(x\right)},\quad\bar{\alpha}\left(x\right):=1-\alpha\left(x\right),\quad\alpha\left(x\right):=\int_{\mathsf{E}}Q\left(x,{\rm
d}y\right)\alpha\left(x,y\right).$ (2)

In many applications, $Q\left(x,\cdot\right)$ is a multivariate normal
distribution with mean $x$ and covariance matrix $\sigma^{2}\cdot I_{d}$,
where $I_{d}$ is the identity matrix, in which case $\nu$ is the Lebesgue
measure and $P$ is the Random-Walk Metropolis (RWM) Markov kernel. Despite its
simplicity, the RWM algorithm is known to perform very well for certain
classes of target distributions, and furthermore to be a robust algorithm
(see, e.g., Roberts et al., 1997; Christensen et al., 2005; Chen et al., 2020;
Livingstone and Zanella, 2022). In this paper, quantitative analysis of the
$\mathrm{L}^{2}$-mixing time and spectral gap of the RWM Markov chain is the
primary application, with a particular emphasis on the dependence of these
quantities on dimension. This analysis relies on a more general theory
applicable beyond the specific scenarios considered here; see Section 1.2.

For a given target distribution $\pi$, after fixing the coordinate system, the
only tuning parameter of the RWM kernel is the proposal variance $\sigma^{2}$.
It is well-known that if $\sigma^{2}$ is too large, then the acceptance
function $\alpha$ will deteriorate, and the Markov chain will tend to get
“stuck” for long periods. On the other hand, if $\sigma^{2}$ is too small,
then the Markov chain will tend to make very small steps. Both of these
regimes correspond intuitively to slow convergence of the Markov chain. In the
celebrated optimal scaling paper of Roberts et al. (1997), it was shown, for a
fairly restrictive class of target distributions, that the proposal variance
$\sigma^{2}$ of RWM on $\mathbb{R}^{d}$ should scale like $d^{-1}$ to obtain a
stable acceptance ratio in the high-dimensional limit, and that the complexity
of sampling depends linearly on dimension, via a particular but indicative
weak convergence result to a Langevin diffusion. In this paper, we study the
high-dimensional properties of the RWM algorithm from a different angle: we
seek to explicitly bound the spectral gap of the RWM kernel in arbitrary
dimension $d$ and for any value of $\sigma^{2}$. For appropriately regular
distributions, we find that scaling $\sigma^{2}$ as $d^{-1}$ does indeed imply
a spectral gap that is precisely of order $d^{-1}$, and that this choice of
polynomial scaling is optimal. The following is a combination of Corollary 35
and Theorem 46:

######  Theorem 1.

Let $\pi$ have density
$\pi\left(x\right)\propto\exp\left(-U\left(x\right)\right)$ with respect to
Lebesgue measure on $\mathbb{R}^{d}$, where the potential $U$ is $L$-smooth,
$m$-strongly convex and twice continuously differentiable. If $P$ is the
$\pi$-reversible RWM kernel with $\mathcal{N}\left(0,\sigma^{2}\cdot
I_{d}\right)$ proposal increments, then the spectral gap $\gamma_{P}$ of $P$
satisfies

$C\cdot L\cdot d\cdot\sigma^{2}\cdot\exp\left(-2\cdot L\cdot
d\cdot\sigma^{2}\right)\cdot\frac{m}{L}\cdot\frac{1}{d}\leqslant\gamma_{P}\leqslant\min\left\\{\frac{1}{2}\cdot
L\cdot\sigma^{2},\left(1+m\cdot\sigma^{2}\right)^{-d/2}\right\\},$ (3)

where $C=1.972\times 10^{-4}$.

Twice continuous differentiability of $U$ is only used to obtain the upper
bound. For some intuition, densities with $m$-strongly convex and $L$-smooth
potentials $U$ can be sandwiched between $\mathcal{N}\left(x_{*},L^{-1}\cdot
I_{d}\right)$ and $\mathcal{N}\left(x_{*},m^{-1}\cdot I_{d}\right)$, up to
constant factors, where $x_{*}$ is the maximizer of the density of $\pi$; see
Lemma 42.

Both the lower and upper bounds in (3) demonstrate that taking $\sigma^{2}$
too small or too large causes $\gamma_{P}$ to decrease. The lower bound in (3)
is maximized by taking $\sigma^{2}=1/\left(2\cdot L\cdot d\right)$, while the
rate at which the upper bound decreases with $d$ is also minimized, among
polynomial scalings, by scaling $\sigma^{2}$ with $d^{-1}$. Taking
$\sigma=\varsigma\cdot L^{-1/2}\cdot d^{-1/2}$ for any constant $\varsigma>0$,
we obtain

$C\cdot\varsigma^{2}\cdot\exp\left(-2\cdot\varsigma^{2}\right)\cdot\frac{m}{L}\cdot\dfrac{1}{d}\leqslant\gamma_{P}\leqslant\frac{\varsigma^{2}}{2}\cdot\dfrac{1}{d},$
(4)

so the $\mathcal{O}\left(d^{-1}\right)$ dimension dependence is tight. The
lower bound is maximized by taking $\varsigma^{2}=\frac{1}{2}$, although it is
unlikely that this is optimal in practice due to the results of Roberts et al.
(1997). Similarly, it seems likely that the optimal value of $C$ is possibly a
few orders of magnitude larger.

We also study the $\mathrm{L}^{2}$-convergence complexity of the RWM Markov
chain, noting that convergence can initially be faster than that indicated by
the spectral gap alone. Under the same conditions as Theorem 1 and taking
$\sigma=\varsigma\cdot L^{-1/2}\cdot d^{-1/2}$ as above, we obtain that for at
least two types of feasible initial distribution $\mu$ (see Theorem 49 and
Remarks 50 and 51) one may take

$n\in\mathcal{O}\left(\exp\left(2\cdot\varsigma^{2}\right)\cdot\varsigma^{-2}\cdot\kappa\cdot
d\cdot\left\\{\log d+\log\kappa+\log\left(\varepsilon_{{\rm
Mix}}^{-1}\right)\right\\}\right),$

and obtain $\chi^{2}\left(\mu P^{n},\pi\right)\leqslant\varepsilon_{{\rm
Mix}}$, where $\chi^{2}\left(\mu,\nu\right)$ denotes the $\chi^{2}$ divergence
between $\mu$ and $\nu$ and $\kappa:=L/m$ is the condition number.

In practice, fluctuations of ergodic averages of
$f\in\mathrm{L}^{2}\left(\pi\right)$ are of interest, and one may consider the
asymptotic variance, given by

${\rm var}\left(P,f\right):=\lim_{n\to\infty}n\cdot{\rm
var}\left(\frac{1}{n}\sum_{i=1}^{n}f\left(X_{i}\right)\right),$

where $X_{0}\sim\pi$. We show in Proposition 48 that with
$\sigma=\varsigma\cdot L^{-1/2}\cdot d^{-1/2}$,

$\displaystyle{\rm var}\left(P,f\right)$ $\displaystyle\leqslant
10141\cdot\varsigma^{-2}\cdot\exp\left(2\cdot\varsigma^{2}\right)\cdot\kappa\cdot
d\cdot\left\|f\right\|_{2}^{2},\qquad\varsigma>0.$

We also show that linear functions satisfy ${\rm var}\left(P,f\right)\geqslant
2\cdot\varsigma^{-2}\cdot d\cdot\left\|f\right\|_{2}^{2}.$

To prove these results we apply a general result, Theorem 18, which requires
quantitative lower bounds on the isoperimetric profile of $\pi$ for some
metric $\mathsf{d}$, complemented with a quantitative close coupling condition
for $P$:

######  Definition 2 (Close coupling).

For a metric $\mathsf{d}$ on $\mathsf{E}$ and $\epsilon,\delta>0$, a Markov
kernel $P$ evolving on $\mathsf{E}$ is
$\left(\mathsf{d},\delta,\varepsilon\right)$-close coupling if

$\mathsf{d}\left(x,y\right)\;\leqslant\delta\Rightarrow\left\|P\left(x,\cdot\right)-P\left(y,\cdot\right)\right\|_{{\rm
TV}}\leqslant 1-\varepsilon,\qquad x,y\in\mathsf{E}.$

This is to be contrasted with what is known about the overdamped Langevin
diffusion, which solves the stochastic differential equation

$\mathrm{d}X_{t}=\nabla\log\pi\left(X_{t}\right)\,\mathrm{d}t+\sqrt{2}\cdot\mathrm{d}W_{t},$

for which knowledge of the isoperimetric profile alone can provide information
on its convergence. For example, the overdamped Langevin diffusion is
associated with the classical Dirichlet form $f\mapsto\pi\left(\left|\nabla
f\right|^{2}\right)$; (see, e.g. Pavliotis, 2014, Section 4.5), and this
allows one to deduce Poincaré and log-Sobolev inequalities in the presence of
appropriate isoperimetric inequalities (see, e.g., Milman, 2012, Section 2.2).
The RWM chain may indeed be viewed as a discretization of this diffusion, but
our results do not explicitly compare the diffusion with the Markov chain;
indeed our quantitative bounds are valid in any dimension and for any value of
$\sigma^{2}$. The additional close coupling condition required for RWM in fact
introduces a penalty in the convergence bounds, by which convergence degrades
as the product $\delta\cdot\varepsilon$ decreases. To demonstrate close
coupling for Metropolis chains, we show that for
$\alpha_{0}:=\inf_{z\in\mathsf{E}}\alpha\left(z\right)$, with $\alpha$ as in
(2),

$\left\|P\left(x,\cdot\right)-P\left(y,\cdot\right)\right\|_{{\rm
TV}}\leqslant\left\|Q\left(x,\cdot\right)-Q\left(y,\cdot\right)\right\|_{{\rm
TV}}+1-\alpha_{0},$

and we show that $\alpha_{0}$ can be lower bounded for any $\sigma^{2}$ under
the assumption of $L$-smoothness. One may then take $\delta$ such that
$\left|x-y\right|\leqslant\delta\Rightarrow\left\|Q\left(x,\cdot\right)-Q\left(y,\cdot\right)\right\|_{{\rm
TV}}\leqslant\frac{1}{2}\cdot\alpha_{0}$ to obtain that $P$ is close coupling
with $\varepsilon\geqslant\frac{1}{2}\cdot\alpha_{0}$. In our analysis, we
find that to maximize the spectral gap of $P$ as a function of dimension, it
is sufficient to scale $\sigma^{2}$ as $d^{-1}$. Ultimately, one may view the
penalty for running an appropriately tuned RWM instead of Langevin as being of
order $d^{-1}$ in terms of the spectral gap.

We will also analyze the preconditioned Crank–Nicolson (pCN) Markov chain via
essentially analogous theory to the RWM chain, since it is also a Metropolis
Markov chain, obtaining dimension-independent bounds under suitable
assumptions.

###  1.2 Roadmap

In Section 2, we review the notions of conductance profile and spectral
profile for Markov chains, and show how these can be used to establish bounds
on the spectral gap and mixing time of the chain.

In Section 3, we introduce notions of isoperimetric profiles of probability
measures with respect to a given metric. We show that when combined with the
close coupling condition for an invariant Markov kernel, one can deduce bounds
on the conductance profile of the chain, and hence on the spectral gap and
mixing time. We then give a number of concrete examples in which the
isoperimetric profile can be well-controlled, and discuss the implications on
convergence. See Figure 1 for a diagram of these results. We also prove a
general close-coupling result for Metropolis algorithms.

1\. Regular isoperimetric minorant $\tilde{I}_{\pi}$ 2\. Lower bound on
isoperimetric profile 3\. Three-set isoperimetric inequality 4\. Bound on
conductance profile 5\. Bound on spectral profile 6\. Lower bound on Dirichlet
form $\mathcal{E}(P,f)$ 7\. Upper bound on convergence of $P^{n}$ 8\. Mixing
time bounds Definition 13Lemma 14ptWith close coupling, concavity of
$\tilde{I}_{\pi}$ptLemma 15, Corollary 16Lemma 6Lemma 7Theorem 8Positive
reversible chainTheorem 18 Figure 1: Outline of the results of Sections 2, 3

In Sections 4–5, we apply these tools to study the RWM algorithm. Although one
can obtain non-asymptotic bounds for the spectral gap and mixing time under
various isoperimetric and smoothness assumptions using our techniques, we
focus on obtaining concrete results when $U$ is $m$-strongly convex and
$L$-smooth. In this case, we obtain non-asymptotic estimates on both the
spectral gap and the mixing time. Furthermore, we show that for this class of
densities the dependence of the spectral gap on dimension is sharp, up to sub-
polynomial factors. We also demonstrate that, when appropriately tuned, the
asymptotic variance of a RWM chain is upper bounded by a linear factor $d$
times the ideal variance, and that there is a matching linear lower bound for
linear functions.

In Section 6, we apply the same tools to the study of the pCN algorithm for
sampling perturbations of Gaussian measures. We again obtain non-asymptotic
estimates on both the spectral gap and mixing time of the chain.

###  1.3 Related work

This paper develops in a systematic manner a comparatively crude analysis in a
technical report by the authors (Andrieu et al., 2022, Sections 5.3–5.4).

One of the first attempts to establish directly the existence of a (right)
$\mathrm{L}^{2}$-spectral gap for RWM on $\mathbb{R}^{d}$ is Miclo and Roberto
(2000), where a quantization approach is used to approximate the initial
problem, and results concerning Markov chains on graphs are leveraged. The
authors focus on the scenario $d=1$, although it is argued that the results
could be generalized to multiple dimensions. The assumptions made on the
negative log-density $U$ are less stringent than those considered here,
however no quantitative bounds were provided. Another contribution in this
direction is Jarner and Yuen (2004) where a lower bound on the conductance was
obtained for monotone log-concave distributions on $\mathbb{R}$. The existence
of an $\mathrm{L}^{2}$ spectral gap can also be established using drift and
minorization techniques: for example, Jarner and Hansen (2000) demonstrate
that the RWM chain is ${\rm L}^{1}$\- geometrically ergodic under fairly mild
conditions on $\pi$, and since RWM chains are reversible those conditions also
imply $\mathrm{L}^{2}$-geometric ergodicity and the existence of a spectral
gap (Roberts and Rosenthal, 1997; Roberts and Tweedie, 2001). However, these
techniques typically do not provide accurate quantitative bounds on the size
of the gap; see for instance, Qin and Hobert (2021).

The results and the approach we take here are inspired by several papers. The
recent papers Belloni and Chernozhukov (2009), Dwivedi et al. (2019) and Chen
et al. (2020) are most closely related to our approach. All three of these
papers also consider bounds on the conductance or conductance profile of the
RWM kernel $P$, but restricted to some compact subset $K$ of $\mathbb{R}^{d}$.
As a consequence, they do not provide a positive lower bound on the spectral
gap of the unrestricted $P$. More precisely, Belloni and Chernozhukov (2009)
and Dwivedi et al. (2019) prove a restricted variant of Corollary 16 for the
conductance, corresponding to connection 3–4 in Figure 1. Chen et al. (2020)
prove restricted variants of connections 3–8. Dwivedi et al. (2019) and Chen
et al. (2020) obtain complexity bounds for convergence of $\mu P^{n}$ to $\pi$
on $\mathbb{R}^{d}$ using the notion of $s$-conductance, which entails
delicate balancing of the desired final error, the size of $K$, properties of
$\mu$ and even $\sigma^{2}$. In particular, we emphasize that all three prior
complexity analyses involve using specific, theoretically-motivated and
typically unknown values of $\sigma^{2}$, so the results do not cover the
arbitrary values of $\sigma^{2}$ used in practice. The restriction to $K$ in
these papers is necessary since the authors only verify the close coupling
condition for $P$ on $K$. In contrast, we are able to verify this condition
globally, and hence there is no need to consider restrictions. As a result, we
can obtain a positive lower bound on the spectral gap, and the convergence
analysis does not require the same type of fine balancing. In particular, we
also find an improved dependence of the mixing time on the condition number
$\kappa$, in comparison to the dependence in Chen et al. (2020).

Belloni and Chernozhukov (2009) and Dwivedi et al. (2019) use a type of 3-set
exponential isoperimetric profile inequality to infer a bound on the
conductance of the chain restricted to $K$, in the presence of the close
coupling condition. The isoperimetric inequality is verified for
(perturbations of) $m$-strongly convex potentials. In Chen et al. (2020), a
Gaussian 3-set isoperimetric profile inequality is used to infer a bound on
the conductance profile of the restricted chain in the presence of the same
coupling condition, and an isoperimetric profile inequality is verified for
strongly convex potentials. Our main contribution in relation to this part of
the theory is to show that any sufficiently regular isoperimetric profile
implies a corresponding 3-set isoperimetric inequality. In fact, Chen et al.
(2020)’s consideration of the Gaussian 3-set isoperimetric inequality and its
implication for rapid convergence far from equilibrium was the main
inspiration for our results relating classical isoperimetric profiles and
conductance profiles more generally. Our subsequent mixing time results are
mostly direct consequences of the relationships between the conductance
profile, spectral profile and $\mathrm{L}^{2}$-convergence, as developed by
Goel et al. (2006).

Hairer et al. (2014) show the existence and stability of the spectral gap of
pCN as $d\to\infty$ under quite general conditions, but the bounds so obtained
are understood to be somewhat loose numerically, and their dependence on the
various parameters of the target measure is implicit. Here, we make more
restrictive assumptions on the target measure, which allows us to obtain
bounds which are more interpretable and perhaps sharper.

###  1.4 Notation

We make use of the following notation throughout the manuscript.

  * •

The Euclidean norm on $\mathsf{E}=\mathbb{R}^{d}$ is denoted
$\left|\cdot\right|$, which we will also use to denote the associated metric.

  * •

We write ${\rm Leb}$, and plainly $\mathrm{d}x$, for the Lebesgue measure on
$\mathbb{R}^{d}$.

  * •

We write $\mathrm{L}^{2}\left(\pi\right)$ for the Hilbert space of
(equivalence classes of) real-valued $\pi$-square-integrable measurable
functions with inner product

$\left\langle
f,g\right\rangle=\int_{\mathsf{E}}f\left(x\right)g\left(x\right)\,\mathrm{d}\pi\left(x\right)\,,$

and corresponding norm $\left\|\cdot\right\|_{2}$. For
$g\in\mathrm{L}^{2}\left(\pi\right)$,
$\mathrm{Var}_{\pi}\left(g\right):=\left\|g-\pi\left(g\right)\right\|_{2}^{2}$.
We write $\mathrm{L}^{2}_{0}\left(\pi\right)$ for the set of functions
$f\in\mathrm{L}^{2}\left(\pi\right)$ which also satisfy $\pi\left(f\right)=0$.

  * •

Given a set $A\in\mathcal{E}$ with $\pi\left(A\right)>0$, we define the
probability measure $\pi_{A}$ on $\left(\mathsf{E},\mathscr{E}\right)$ via
$\pi_{A}\left(\cdot\right):=\pi\left(\cdot\cap A\right)/\pi\left(A\right)$.

  * •

Given a probability measure $\pi$ and a function $T$ on $\mathsf{E}$, we
define the pushforward measure of $\pi$ under the action of $T$ by
$\left(T_{\\#}\pi\right)\left(A\right):=\pi\left(T^{-1}\left(A\right)\right)$.

  * •

For a set $A\in\mathscr{E}$, its complement in $\mathsf{E}$ is denoted by
$A^{\complement}$. We denote the corresponding indicator function by
$\mathbf{1}_{A}:\mathsf{E}\to\left\\{0,1\right\\}$.

  * •

For two sets $A,B\in\mathscr{E}$ and a metric $\mathsf{d}$ on $\mathsf{E}$,
the distance between the two sets is given by

$\mathsf{d}\left(A,B\right):=\inf\left\\{\mathsf{d}\left(x,y\right):x\in
A,y\in B\right\\}.$

When one of the sets is a singleton, we will simply write
$\mathsf{d}\left(x,B\right)$ for
$\mathsf{d}\left(\left\\{x\right\\},B\right)$, say.

  * •

For two measures $\mu$ and $\nu$, we write $\nu\ll\mu$ to mean that $\nu$ is
absolutely continuous with respect to $\mu$.

  * •

For two probability measures $\mu$ and $\nu$ on
$\left(\mathsf{E},\mathscr{E}\right)$, we let $\mu\otimes\nu\left(A\times
B\right):=\mu\left(A\right)\cdot\nu\left(B\right)$ for $A,B\in\mathscr{E}$.
For a Markov kernel $P\left(x,\mathrm{d}y\right)$ on
$\mathsf{E}\times\mathscr{E}$, we write for
$\bar{A}\in\mathscr{E}\otimes\mathscr{E}$, the minimal product
$\sigma$-algebra, $\mu\otimes
P\left(\bar{A}\right):=\int_{\bar{A}}\mu\left(\mathrm{d}x\right)P\left(x,\mathrm{d}y\right)$.

  * •

For a probability measure $\mu\ll\pi$, the chi-squared divergence between
$\mu$ and $\pi$ is given by
$\chi^{2}\left(\mu,\pi\right):=\left\|\frac{\mathrm{d}\mu}{\mathrm{d}\pi}-1\right\|_{2}^{2}$.

  * •

A point mass distribution at $x$ is denoted by $\delta_{x}$.

  * •

We associate, to a $\pi$-invariant Markov kernel $P$, the bounded linear
operator also denoted
$P:\mathrm{L}^{2}\left(\pi\right)\to\mathrm{L}^{2}\left(\pi\right)$, given by
$Pf\left(x\right)=\int_{\mathsf{E}}P\left(x,{\rm d}y\right)f\left(y\right)$.
We may refer to $P$ as a kernel or as an operator, the meaning being clear
from the context.

  * •

We write $\mathrm{Id}$ for the identity mapping on
$\mathrm{L}^{2}\left(\pi\right)$, and $\mathrm{id}$ for the identity mapping
on $\mathbb{R}$, and $I_{d}$ for the $d\times d$ identity matrix.

  * •

Given a bounded linear operator
$P:\mathrm{L}^{2}\left(\pi\right)\to\mathrm{L}^{2}\left(\pi\right)$, we define
the Dirichlet form
$\mathcal{E}\left(P,f\right):=\left\langle\left(\mathrm{Id}-P\right)f,f\right\rangle$
for any $f\in\mathrm{L}^{2}\left(\pi\right)$.

  * •

For a mapping
$T:\left(\mathsf{E},\mathsf{d}\right)\to\left(\mathsf{E}^{\prime},\mathsf{d}^{\prime}\right)$
between metric spaces, the Lipschitz norm is defined as $\left|T\right|_{{\rm
Lip}}:=\sup_{x\neq
y}\frac{\mathsf{d}^{\prime}\left(T\left(x\right),T\left(y\right)\right)}{\mathsf{d}\left(x,y\right)}$.

  * •

The spectrum of a bounded linear operator $P$ is the set

$\mathcal{S}\left(P\right):=\left\\{\lambda\in\mathbb{C}:P-\lambda\cdot{\rm
Id}\text{ is not invertible}\right\\}.$

  * •

For a $\pi$-invariant Markov kernel $P$, we denote by
$\mathcal{S}_{0}\left(P\right)$ the spectrum of the restriction of $P$ to
$\mathrm{L}^{2}_{0}\left(\pi\right)$. We define the spectral gap of $P$ to be
$\gamma_{P}:=1-\sup\left|\mathcal{S}_{0}\left(P\right)\right|$.

  * •

If $P$ is a $\pi$-reversible Markov kernel, then
$\mathcal{S}_{0}\left(P\right)\subseteq\left[-1,1\right]$ and we may define
the right spectral gap as ${\rm Gap_{{\rm
R}}}\left(P\right):=1-\sup\mathcal{S}_{0}\left(P\right)$, which satisfies
(see, e.g., Douc et al., 2018, Theorem 22.A.19),

${\rm
Gap}_{\mathrm{R}}\left(P\right)=\inf_{g\in\mathrm{L}^{2}_{0}\left(\pi\right),g\neq
0}\frac{\mathcal{E}\left(P,g\right)}{\left\|g\right\|_{2}^{2}}\,.$

  * •

We say that a $\pi$-reversible Markov kernel $P$ is positive if $\left\langle
f,Pf\right\rangle\geqslant 0$ for all $f\in\mathrm{L}^{2}\left(\pi\right)$. In
this case, $\gamma_{P}=\mathrm{Gap_{{\rm R}}}\left(P\right)$.

  * •

We write $\mathcal{N}\left(\cdot;m,\Sigma\right)$, where $m\in\mathbb{R}^{d}$
and $\Sigma$ is a $d\times d$ covariance matrix, for the corresponding
Gaussian distribution on $\mathbb{R}^{d}$ and also
$\mathcal{N}\left(x;m,\Sigma\right)$ for its density with respect to Lebesgue
at $x\in\mathbb{R}^{d}$.

  * •

We adopt the following $\mathcal{O}$ (resp. $\Omega$) notation to indicate
when functions grow no faster than (resp. no slower than) other functions. For
$a\in\mathbb{R}\cup\\{\infty\\}$,

    * –

If $f\left(x\right)\in\mathcal{O}\left(g\left(x\right)\right)$ as $x\to a$,
this means that $\underset{x\to
a}{\lim\sup}\left|\frac{f\left(x\right)}{g\left(x\right)}\right|<\infty$. When
$a=+\infty$, then we may drop explicit mention of $a$.

    * –

If $f\left(x\right)\in\Omega\left(g\left(x\right)\right)$ as $x\to a$, this
means that $\underset{x\to
a}{\lim\inf}\left|\frac{f\left(x\right)}{g\left(x\right)}\right|>0$. In
particular $f\in\mathcal{O}\left(g\right)\iff g\in\Omega\left(f\right)$.

##  2 Conductance profile, spectral profile, and mixing time bounds

The spectral gap $\gamma_{P}$ of a $\pi$-reversible Markov kernel $P$ provides
important information on the convergence of the chain. Indeed, for any
$n\in\mathbb{N}_{0}$,

$\left\|P^{n}f\right\|_{2}\leqslant\left\|f\right\|_{2}\cdot\left(1-\gamma_{P}\right)^{n},\qquad
f\in\mathrm{L}^{2}_{0}\left(\pi\right),$ (5)

and the factor $\left(1-\gamma_{P}\right)$ cannot be reduced in general,
motivating quantitative lower bounds on $\gamma_{P}$. By taking $f={\rm
d}\mu/{\rm d}\pi-1$ in (5) we may deduce bounds on $\chi^{2}\left(\mu
P^{n},\pi\right)$, the chi-squared divergence between $\mu P^{n}$ and $\pi$,
and thereby upper bound mixing times. However, using only this bound can give
very conservative bounds when $\chi^{2}\left(\mu,\pi\right)$ is large, and so
we will use more refined techniques to control the convergence behaviour of
the chain when it is far from equilibrium. In particular, we make use of the
spectral profile (Goel et al., 2006) and conductance profile of the Markov
chain (Lovász and Kannan, 1999; Morris and Peres, 2005). These techniques are
able to capture the following phenomenon: many Markov chains, when far from
equilibrium, are able to mix at faster than exponential rates, or equally,
that sets of small measure in the state space are comparatively easier to
escape from. Moreover, these techniques are capable of providing greatly-
improved bounds on mixing times, and in some cases, nearly-optimal bounds
(see, e.g., Kozma, 2007).

######  Definition 3 (Conductance and conductance profile).

The conductance profile of a $\pi$-invariant Markov kernel $P$ is

$\Phi_{P}\left(v\right):=\inf\left\\{\frac{\left(\pi\otimes
P\right)\left(A\times
A^{\complement}\right)}{\pi\left(A\right)}:A\in\mathscr{E},\pi\left(A\right)\leqslant
v\right\\},\qquad v\in\left(0,\frac{1}{2}\right].$

The conductance of $P$ is $\Phi_{P}^{*}:=\Phi_{P}\left(\frac{1}{2}\right)$.

######  Definition 4 (Spectral profile).

Let $P$ be a $\pi$-invariant Markov kernel, then we define

$C_{0}^{+}\left(A\right):=\left\\{g:\mathsf{E}\to\mathbb{R}\;\mid\;{\rm
supp}\,g\subseteq A,g\geqslant 0,g\neq\text{const. }\right\\},\qquad
A\in\mathscr{E},$

where $\mathrm{supp}\,g$ is the closure of
$\left\\{x\in\mathsf{E}:\left|g\left(x\right)\right|>0\right\\}$, and

$\lambda_{P}\left(A\right):=\inf_{g\in
C_{0}^{+}\left(A\right)}\frac{\mathcal{E}\left(P,g\right)}{{\rm
Var}_{\pi}\left(g\right)}.$

The spectral profile of $P$ is

$\Lambda_{P}\left(v\right):=\inf\left\\{\lambda_{P}\left(A\right):A\in\mathscr{E},\pi\left(A\right)\leqslant
v\right\\},\qquad v>0.$

We note that for all $v>0$ and $\pi$-reversible $P$, we have that
$\Lambda_{P}\left(v\right)\geqslant{\rm Gap}_{{\rm
R}}\left(P\right)\geqslant\gamma_{P}$. To proceed from here, we first use a
Cheeger-type argument to bound the spectral profile using the conductance
profile. The statement and proof of Lemma 6 are very similar to Chen et al.
(2020, Lemma 12), with one difference being that we do not restrict the state
space. The proof can be found in Appendix A. We also recall Cheeger’s
inequalities.

######  Lemma 5 (Lawler and Sokal 1988, Theorem 3.5; Cheeger’s inequalities).

If $P$ is a $\pi$-reversible Markov kernel, then

$\frac{1}{2}\cdot\left[\Phi_{P}^{*}\right]^{2}\leqslant\mathrm{Gap_{{\rm
R}}}\left(P\right)\leqslant\Phi_{P}^{*}.$

######  Lemma 6.

If $P$ is a $\pi$-reversible Markov kernel, then

$\Lambda_{P}\left(v\right)\geqslant\begin{cases}\frac{1}{2}\cdot\Phi_{P}\left(v\right)^{2}&0<v\leqslant\frac{1}{2},\\\
\frac{1}{2}\cdot\left[\Phi_{P}^{*}\right]^{2}&v>\frac{1}{2}.\end{cases}$

We will make use of the following lower bound on the Dirichlet form in terms
of the spectral profile.

######  Lemma 7 (Goel et al. 2006, Lemma 2.1).

For non-constant, nonnegative $g\in\mathrm{L}^{2}\left(\pi\right)$,

$\mathcal{E}\left(P,g\right)\geqslant{\rm
Var}_{\pi}\left(g\right)\cdot\frac{1}{2}\cdot\Lambda_{P}\left(4\cdot\frac{\left[\pi\left(g\right)\right]^{2}}{{\rm
Var}_{\pi}\left(g\right)}\right).$

We note a similarity between the consequences of the spectral profile and the
so-called ‘super-Poincaré’ inequalities of Wang (2000). See Proposition 62 in
Appendix A for some details on this connection, which may be known among
experts, but does not appear to have been explicitly documented.

Our final result in this section shows how the conductance profile can be used
to deduce bounds on convergence of $P$. We build on previous work,
particularly Goel et al. (2006) in the discrete setting and Chen et al. (2020)
on general state spaces with ‘restricted’ conductance profiles.

######  Theorem 8.

Let $P$ be a positive, $\pi$-reversible Markov kernel with $\Phi_{P}^{*}>0$,
$\mu\ll\pi$ a probability measure, and $\varepsilon_{{\rm
Mix}}\in\left(0,8\right)$. To ensure

$\left\|P^{n}\left(\frac{{\rm d}\mu}{{\rm
d}\pi}-1\right)\right\|_{2}^{2}\leqslant\varepsilon_{{\rm Mix}},$

it suffices to take

$\displaystyle n$ $\displaystyle\geqslant 2+4\cdot\int_{\min\left\\{4\cdot
u_{0}^{-1},1/2\right\\}}^{1/2}\frac{1}{v\cdot\Phi_{P}\left(v\right)^{2}}\,{\rm
d}v$
$\displaystyle+\left[\Phi_{P}^{*}\right]^{-2}\cdot\log\left(\max\left\\{\frac{\min\left\\{u_{0},8\right\\}}{\varepsilon_{{\rm
Mix}}},1\right\\}\right),$

where $u_{0}=\left\|\frac{{\rm d}\mu}{{\rm d}\pi}-1\right\|_{2}^{2}$.

###### Proof.

Writing $h=\frac{{\rm d}\mu}{{\rm d}\pi}$ and $u_{n}:={\rm
Var}_{\pi}\left(P^{n}h\right)=\chi^{2}\left(\mu P^{n},\pi\right)$, compute
that

$\displaystyle u_{n}-u_{n+1}$
$\displaystyle=\mathcal{E}\left(P^{2},P^{n}h\right)$
$\displaystyle\geqslant\mathcal{E}\left(P,P^{n}h\right)$
$\displaystyle\geqslant u_{n}\cdot\frac{1}{2}\cdot\Lambda_{P}\left(4\cdot
u_{n}^{-1}\right)$

where we have used the positivity of $P$ to bound
$\mathcal{E}\left(P^{2},f\right)\geqslant\mathcal{E}\left(P,f\right)$, Lemma
7, and recalled that $\pi\left(P^{n}h\right)=1$ for all $n$. Defining
$L_{P}\left(\eta\right):=\frac{1}{2}\cdot\eta\cdot\Lambda_{P}\left(4\cdot\eta^{-1}\right)$
for $\eta>0$, it thus holds that $u_{n}-u_{n+1}\geqslant
L_{P}\left(u_{n}\right)$.

We now distinguish between whether $u_{0}$ is greater or smaller than $8$,
noting that in the latter case, using the spectral gap directly allows for
tighter control of the increment $u_{n}-u_{n+1}$.

Supposing that $u_{0}\geqslant 8$, we will first estimate how long it takes
for $u_{n}$ to drop below $8$. Recalling that $\Lambda_{P}$ is a decreasing
function, it is straightforward to see that $L_{P}$ is an increasing function,
and hence measurable. Additionally, since $\Lambda_{P}$ is bounded below by
$\gamma_{P}>0$, it follows that $L_{P}$ is bounded away from $0$ on intervals
not containing $0$. Assuming that both $u_{n}$, $u_{n+1}$ are at least $8$, we
can then write

$\int_{u_{n+1}}^{u_{n}}\frac{{\rm
d}\eta}{L_{P}\left(\eta\right)}\geqslant\frac{u_{n}-u_{n+1}}{L_{P}\left(u_{n}\right)}\geqslant
1.$

Moreover, if $u_{0}\geqslant u_{1}\geqslant\cdots\geqslant u_{n}\geqslant 8$,
then we may sum up these inequalities to see that

$\int_{8}^{u_{0}}\frac{{\rm
d}\eta}{L_{P}\left(\eta\right)}\geqslant\int_{u_{n}}^{u_{0}}\frac{{\rm
d}\eta}{L_{P}\left(\eta\right)}\geqslant n.$

In particular, for $n\geqslant 1+\int_{8}^{u_{0}}\frac{{\rm
d}\eta}{L_{P}\left(\eta\right)}$, it must hold that $u_{n}<8$. Now, recall
that for $\eta\geqslant 8$, we can bound

$\displaystyle L_{P}\left(\eta\right)$
$\displaystyle:=\frac{1}{2}\cdot\eta\cdot\Lambda_{P}\left(4\cdot\eta^{-1}\right)$
$\displaystyle\geqslant\frac{1}{2}\cdot\eta\cdot\left\\{\frac{1}{2}\cdot\Phi_{P}\left(4\cdot\eta^{-1}\right)^{2}\right\\}$
$\displaystyle=\frac{\Phi_{P}\left(4\cdot\eta^{-1}\right)^{2}}{4\cdot\eta^{-1}}.$

We then compute that

$\displaystyle\int_{8}^{u_{0}}\frac{{\rm d}\eta}{L_{P}\left(\eta\right)}$
$\displaystyle\leqslant\int_{8}^{u_{0}}\frac{4\cdot\eta^{-1}}{\Phi_{P}\left(4\cdot\eta^{-1}\right)^{2}}\,{\rm
d}\eta$ $\displaystyle=4\cdot\int_{4\cdot
u_{0}^{-1}}^{1/2}\frac{1}{v\cdot\Phi_{P}\left(v\right)^{2}}\,{\rm d}v,$

noting that $\Phi_{P}$ is monotone, hence measurable, and bounded below by
$\Phi_{P}\left(\frac{1}{2}\right)>0$, hence the integral exists.

For $u_{0}<8$, we control the decay of $u_{n}$ more tightly by using the
spectral gap of $P$, $\gamma_{P}$. We obtain

$\displaystyle u_{n}-u_{n+1}$
$\displaystyle=\mathcal{E}\left(P^{2},P^{n}h\right)$
$\displaystyle\geqslant\left(1-\left(1-\gamma_{P}\right)^{2}\right)\cdot{\rm
Var}_{\pi}\left(P^{n}h\right)$ $\displaystyle\implies\quad u_{n+1}$
$\displaystyle\leqslant\left(1-\gamma_{P}\right)^{2}\cdot u_{n}$

and thus that

$\displaystyle u_{n}$ $\displaystyle\leqslant\left(1-\gamma_{P}\right)^{2\cdot
n}\cdot u_{0}$ $\displaystyle\leqslant\exp\left(-2\cdot\gamma_{P}\cdot
n\right)\cdot u_{0}.$

One can then deduce that for $n\geqslant
1+\frac{1}{2}\cdot\gamma_{P}^{-1}\cdot\log\left(\frac{u_{0}}{\varepsilon_{{\rm
Mix}}}\right)$, $u_{n}\leqslant\varepsilon_{{\rm Mix}}$. By Lemma 5, we recall
that $\gamma_{P}\geqslant\frac{1}{2}\cdot\left[\Phi_{P}^{*}\right]^{2}$. The
result follows by assembling the various cases. ∎

##  3 From isoperimetric profiles and close coupling to mixing time bounds

###  3.1 General results

From this point onwards, the following assumption is in force. All statements
are made with respect to a given metric $\mathsf{d}$ on $\mathsf{E}$, the
dependence on which may be suppressed when no ambiguity can result.

######  Assumption 9.

The probability distribution $\pi$ has a positive density w.r.t. Lebesgue,
given by $\pi\propto\exp\left(-U\right)$, for some potential
$U:\mathbb{R}^{d}\to\mathbb{R}$.

######  Definition 10 (Three-set isoperimetric inequality).

A probability measure $\pi$ satisfies a _three-set isoperimetric inequality_
with metric $\mathsf{d}$ and function
$F:\left(0,\frac{1}{2}\right]\to\left[0,\infty\right)$ if for all measurable
partitions of the state space $\mathsf{E}=S_{1}\sqcup S_{2}\sqcup S_{3}$,

$\pi\left(S_{3}\right)\geqslant\mathsf{d}\left(S_{1},S_{2}\right)\cdot
F\left(\min\left\\{\pi\left(S_{1}\right),\pi\left(S_{2}\right)\right\\}\right).$

######  Definition 11 (Isoperimetric Profile).

For $A\in\mathscr{E}$ and $r\geqslant 0$, let
$A_{r}:=\left\\{x\in\mathsf{E}:\mathsf{d}\left(x,A\right)\leqslant
r\right\\}$, and define the Minkowski content of $A$ under $\pi$ with respect
to $\mathsf{d}$ by

$\pi^{+}\left(A\right)=\lim\inf_{r\to
0^{+}}\frac{\pi\left(A_{r}\right)-\pi\left(A\right)}{r}.$

The isoperimetric profile of $\pi$ with respect to the metric $\mathsf{d}$ is

$I_{\pi}\left(p\right):=\inf\left\\{\pi^{+}\left(A\right):A\in\mathscr{E},\pi\left(A\right)=p\right\\},\qquad
p\in\left(0,1\right).$

We note briefly that the isoperimetric profile can be controlled explicitly in
many cases of interest; examples to this effect are provided in Section 3.2.
The following is a special case of a non-trivial result for distributions
defined on Riemannian manifolds which is the product of extensive research by
several authors, and holds specifically for $\mathsf{d}$ being the natural
metric induced by the given Riemannian structure; we recall it here to
emphasize that the notion of regularity on the isoperimetric profile that we
assume is reasonable.

######  Lemma 12 (Milman 2009a, Theorem 1.8).

If $U$ is convex and twice-continuously differentiable, then $I_{\pi}$ is
symmetric about $\frac{1}{2}$ and concave.

######  Definition 13.

We say that $\tilde{I}_{\pi}:\left(0,1\right)\to\left(0,\infty\right)$ is an
isoperimetric minorant of $\pi$ if $\tilde{I}_{\pi}\leqslant I_{\pi}$
pointwise. We furthermore say that $\tilde{I}_{\pi}$ is regular if it is
symmetric about $\frac{1}{2}$, continuous, and monotone increasing on
$\left(0,\frac{1}{2}\right]$.

To begin with, we show that given any regular isoperimetric minorant of our
target measure, one can directly deduce a three-set isoperimetric inequality
for the same measure.

######  Lemma 14.

Let $\pi$ have a regular isoperimetric minorant $\tilde{I}_{\pi}$ w.r.t. the
metric $\mathsf{d}$. Then $\pi$ satisfies a three-set isoperimetric inequality
with metric $\mathsf{d}$ and function $F=\tilde{I}_{\pi}$ on
$(0,\frac{1}{2}]$.

###### Proof.

Following Bobkov and Houdré (1997b, Theorem 4.1 and Remark 4.2), for any
Lipschitz $f:\mathsf{E}\to\left[0,1\right]$ one may write

$\pi\left(\left|\nabla
f\right|\right)\geqslant\int_{0}^{1}\pi^{+}\left(f>t\right)\,{\rm
d}t\geqslant\int_{0}^{1}I_{\pi}\left(\pi\left(f>t\right)\right)\,{\rm
d}t\geqslant\int_{0}^{1}\tilde{I}_{\pi}\left(\pi\left(f>t\right)\right)\,{\rm
d}t,$

where we have written $\left(f>t\right)$ for the set
$\left\\{x\in\mathsf{E}:f\left(x\right)>t\right\\}$, and

$\left|\nabla f\left(x\right)\right|:=\underset{\mathsf{d}\left(x,y\right)\to
0^{+}}{\lim\sup}\frac{\left|f\left(x\right)-f\left(y\right)\right|}{\mathsf{d}\left(x,y\right)}\in\left[0,\infty\right],$

is the modulus of the gradient of $f$. Now let $\mathsf{E}=S_{1}\sqcup
S_{2}\sqcup S_{3}$, and following the construction in the proof of Berestycki
and Nickl (2009, Theorem 2), we define $f:\mathsf{E}\to\left[0,1\right]$ by
$f(x):=\min\left\\{1,\frac{\mathsf{d}\left(S_{1},x\right)}{\mathsf{d}\left(S_{1},S_{2}\right)}\right\\}$.
This function is $\mathsf{d}\left(S_{1},S_{2}\right)^{-1}$-Lipschitz on
$S_{3}$ and flat elsewhere. It thus holds for this $f$ that

$\displaystyle\pi\left(\left|\nabla f\right|\right)$
$\displaystyle\leqslant\pi\left(S_{3}\right)\cdot\mathsf{d}\left(S_{1},S_{2}\right)^{-1}$
$\displaystyle\implies\quad\pi\left(S_{3}\right)$
$\displaystyle\geqslant\mathsf{d}\left(S_{1},S_{2}\right)\cdot\pi\left(\left|\nabla
f\right|\right).$

We now seek a lower bound on $\pi\left(\left|\nabla f\right|\right)$, for
which we will make use of the isoperimetric profile. Observe that for
$t\in\left[0,1\right)$, it holds that

$\displaystyle\left\\{x\in\mathsf{E}:f\left(x\right)>t\right\\}$
$\displaystyle=\left\\{x\in S_{2}:f\left(x\right)>t\right\\}\sqcup\left\\{x\in
S_{3}:f\left(x\right)>t\right\\}$ $\displaystyle=S_{2}\sqcup\left\\{x\in
S_{3}:f\left(x\right)>t\right\\}.$

and hence that
$\pi\left(f>t\right)\in\left[\pi\left(S_{2}\right),\pi\left(S_{2}\sqcup
S_{3}\right)\right]=\left[\pi\left(S_{2}\right),\pi\left(S_{1}^{\complement}\right)\right]$.

Suppose now that
$\max\left\\{\pi\left(S_{1}\right),\pi\left(S_{2}\right)\right\\}\geqslant\frac{1}{2}$,
and without loss of generality that
$\pi\left(S_{1}\right)\geqslant\frac{1}{2}\geqslant\pi\left(S_{2}\right)$. It
then follows for $t\in\left(0,1\right)$ that
$\pi\left(f>t\right)\in\left[\pi\left(S_{2}\right),\pi\left(S_{1}^{\complement}\right)\right]\subseteq\left[0,\frac{1}{2}\right]$.
By monotonicity of $\tilde{I}_{\pi}$ on $\left(0,\frac{1}{2}\right]$, it then
holds that
$\tilde{I}_{\pi}\left(\pi\left(f>t\right)\right)\geqslant\tilde{I}_{\pi}\left(\pi\left(S_{2}\right)\right)$
and thus that $\pi\left(\left|\nabla
f\right|\right)\geqslant\tilde{I}_{\pi}\left(\pi\left(S_{2}\right)\right)$,
from which it follows that

$\pi\left(S_{3}\right)\geqslant\mathsf{d}\left(S_{1},S_{2}\right)\cdot\tilde{I}_{\pi}\left(\pi\left(S_{2}\right)\right)=\mathsf{d}\left(S_{1},S_{2}\right)\cdot\tilde{I}_{\pi}\left(\min\left\\{\pi\left(S_{1}\right),\pi\left(S_{2}\right)\right\\}\right).$

On the contrary, suppose that
$\max\left\\{\pi\left(S_{1}\right),\pi\left(S_{2}\right)\right\\}<\frac{1}{2}$.
It then holds that any median $\nu$ of $f$ under $\pi$ lies in
$\left(0,1\right)$, so one can write that

$\displaystyle t\in\left[0,\nu\right]$
$\displaystyle\implies\pi\left(f>t\right)\geqslant\frac{1}{2}$ $\displaystyle
t\in\left(\nu,1\right]$
$\displaystyle\implies\pi\left(f>t\right)\leqslant\frac{1}{2}.$

Letting $\nu$ be such a median, observe that
$t\mapsto\tilde{I}_{\pi}\left(\pi\left(f>t\right)\right)$ is increasing on
$\left[0,\nu\right]$ and decreasing on $\left[\nu,1\right]$. In particular,

$\tilde{I}_{\pi}\left(\pi\left(f>t\right)\right)\geqslant\tilde{I}_{\pi}\left(\pi\left(f>0\right)\right)=\tilde{I}_{\pi}\left(\pi\left(S_{1}^{\complement}\right)\right),\qquad
t\in\left[0,\nu\right],$

making use of the fact that $\pi\ll{\rm Leb}$. Similarly,

$\tilde{I}_{\pi}\left(\pi\left(f>t\right)\right)\geqslant\tilde{I}_{\pi}\left(\pi\left(f>u\right)\right),\qquad\nu<t\leqslant
u\leqslant 1,$

and therefore

$\tilde{I}_{\pi}\left(\pi\left(f>t\right)\right)\geqslant\lim_{u\to
1^{-}}\tilde{I}_{\pi}\left(\pi\left(f>u\right)\right)=\tilde{I}_{\pi}\left(\lim_{u\to
1^{-}}\pi\left(f>u\right)\right)\geqslant\tilde{I}_{\pi}\left(\pi\left(S_{2}\right)\right),$

taking limits in $u$ and applying continuity of $\tilde{I}_{\pi}$.

We thus decompose

$\displaystyle\int_{0}^{1}\tilde{I}_{\pi}\left(\pi\left(f>t\right)\right)\,{\rm
d}t$
$\displaystyle=\int_{0}^{\nu}\tilde{I}_{\pi}\left(\pi\left(f>t\right)\right)\,{\rm
d}t+\int_{\nu}^{1}\tilde{I}_{\pi}\left(\pi\left(f>t\right)\right)\,{\rm d}t$
$\displaystyle\geqslant\int_{0}^{\nu}\tilde{I}_{\pi}\left(\pi\left(S_{1}^{\complement}\right)\right)\,{\rm
d}t+\int_{\nu}^{1}\tilde{I}_{\pi}\left(\left(\pi\left(S_{2}\right)\right)\right)\,{\rm
d}t$
$\displaystyle=\nu\cdot\tilde{I}_{\pi}\left(\pi\left(S_{1}^{\complement}\right)\right)+\left(1-\nu\right)\cdot\tilde{I}_{\pi}\left(\pi\left(S_{2}\right)\right)$
$\displaystyle\geqslant\min\left\\{\tilde{I}_{\pi}\left(\pi\left(S_{1}^{\complement}\right)\right),\tilde{I}_{\pi}\left(\pi\left(S_{2}\right)\right)\right\\}$
$\displaystyle=\min\left\\{\tilde{I}_{\pi}\left(\pi\left(S_{1}\right)\right),\tilde{I}_{\pi}\left(\pi\left(S_{2}\right)\right)\right\\},$

from which we may conclude. ∎

We now show that given a three-set isoperimetric inequality with a monotone
increasing $F$, together with the _close coupling_ _assumption_ on the Markov
kernel, one may deduce a lower bound on the conductance of any set for that
Markov kernel. The proof, housed in Appendix A, follows closely that of
Dwivedi et al. (2019, Lemma 6), which itself is based on several earlier
works.

######  Lemma 15.

Suppose that $\pi$ satisfies a three-set isoperimetric inequality with metric
$\mathsf{d}$ and function $F$ monotone increasing on
$\left[0,\frac{1}{2}\right)$. Let $P$ be a
$\left(\mathsf{d},\delta,\varepsilon\right)$-close coupling, $\pi$-invariant
Markov kernel. Then for any $A\in\mathscr{E}$ with
$\pi(A)\leqslant\frac{1}{2}$,

$\frac{\left(\pi\otimes P\right)\left(A\times
A^{\complement}\right)}{\pi\left(A\right)}\geqslant\sup_{\theta\in\left[0,1\right]}\min\left\\{\frac{1}{2}\cdot\left(1-\theta\right)\cdot\varepsilon,\frac{1}{4}\cdot\varepsilon\cdot\delta\cdot\theta\cdot\left(F/{\rm
id}\right)\left(\theta\cdot\pi\left(A\right)\right)\right\\}.$

Since $\tilde{I}_{\pi}/{\rm id}$ is decreasing for a concave, regular
isoperimetric minorant $\tilde{I}_{\pi}$, we obtain the following bounds on
the conductance profile by combining Lemma 14, Lemma 15 and Definition 3. We
emphasize that concavity of $\tilde{I}_{\pi}$ is crucial for obtaining non-
zero lower bounds. Considering functions on $(0,\frac{1}{2}]$ of the form
$p\mapsto c\cdot p^{k}$ the critical case is $k=1$ and any $k>1$ implies only
a conductance profile lower bound of $0$; our examples give isoperimetric
minorants of the form $p\mapsto c\cdot p\cdot\log\left(\frac{1}{p}\right)^{r}$
on $(0,\frac{1}{2}]$ for $r\in[0,1]$. Additionally, it is well-known that the
uniform measure on the sphere $\mathbb{S}^{d}\subset\mathbb{R}^{d+1}$
satisfies $I\left(p\right)\asymp p^{\frac{d-1}{d}}$; see e.g. Section 9 of
Bobkov and Houdré (1997b).

######  Corollary 16.

Suppose that $\tilde{I}_{\pi}$ is a regular, concave isoperimetric minorant of
$\pi$ w.r.t. the metric $\mathsf{d}$. Let $P$ be a
$(\mathsf{d},\delta,\varepsilon)$-close coupling, $\pi$-invariant Markov
kernel. Then for any $v\in\left(0,\frac{1}{2}\right]$,

$\displaystyle\Phi_{P}\left(v\right)$
$\displaystyle\geqslant\sup_{\theta\in\left[0,1\right]}\min\left\\{\frac{1}{2}\cdot\left(1-\theta\right)\cdot\varepsilon,\frac{1}{4}\cdot\varepsilon\cdot\delta\cdot\theta\cdot\left(\tilde{I}_{\pi}/{\rm
id}\right)\left(\theta\cdot v\right)\right\\}$
$\displaystyle\geqslant\frac{1}{4}\cdot\varepsilon\cdot\min\left\\{1,\frac{1}{2}\cdot\delta\cdot\frac{\tilde{I}_{\pi}\left(\frac{1}{2}\cdot
v\right)}{\frac{1}{2}\cdot v}\right\\}.$

######  Remark 17.

For obtaining tighter bounds on the conductance when
$\delta\cdot\tilde{I}_{\pi}\left(\frac{1}{2}\right)$ is sufficiently small,
one can take $\theta=1-\delta\cdot\tilde{I}_{\pi}\left(\frac{1}{2}\right)$ to
see that

$\Phi_{P}^{*}\geqslant\frac{1}{2}\cdot\varepsilon\cdot\delta\cdot\tilde{I}_{\pi}\left(\frac{1}{2}\cdot\left(1-\delta\cdot\tilde{I}_{\pi}\left(\frac{1}{2}\right)\right)\right)\to\frac{1}{2}\cdot\varepsilon\cdot\delta\cdot\tilde{I}_{\pi}\left(\frac{1}{2}\right),$

as $\delta\cdot\tilde{I}_{\pi}\left(\frac{1}{2}\right)\to 0^{+}$, which is a
slight improvement on the non-asymptotic bound
$\Phi_{P}^{*}=\Phi_{P}\left(\frac{1}{2}\right)\geqslant\frac{1}{2}\cdot\varepsilon\cdot\delta\cdot\tilde{I}_{\pi}\left(\frac{1}{4}\right)$.

The following theorem is the culmination of this and the preceding section;
see Figure 1. For the mixing time bound, it is useful to note that
$v_{*}^{-1}$ will typically increase quite rapidly as $\delta$ decreases. The
bounds suggest three-stage behaviour when $v_{*}<\frac{1}{2}$, recalling that
$u_{0}=\chi^{2}(\mu,\pi)$. The first term is active when $u_{0}>4\cdot
v_{*}^{-1}>8$, either because $u_{0}$ is extremely large or $\delta$ is large,
while the second term is active when $u_{0}>8$ and the third term is active
when $u_{0}>\varepsilon_{{\rm Mix}}$. Of course, if
$u_{0}\leqslant\varepsilon_{{\rm Mix}}$, then one may take $n=0$.

######  Theorem 18.

Let $\pi$ have a regular, concave isoperimetric minorant $\tilde{I}_{\pi}$
w.r.t. the metric $\mathsf{d}$, and $P$ be a
$\left(\mathsf{d},\delta,\varepsilon\right)$-close coupling, $\pi$-reversible,
positive Markov kernel. Then

  1. 1.

For $v\in\left(0,\frac{1}{2}\right]$,
$\Phi_{P}\left(v\right)\geqslant\frac{1}{4}\cdot\varepsilon\cdot\min\left\\{1,\frac{1}{2}\cdot\delta\cdot\left(\tilde{I}_{\pi}/{\rm
id}\right)\left(\frac{1}{2}\cdot v\right)\right\\}$,

  2. 2.

$\Phi_{P}^{*}\geqslant\frac{1}{4}\cdot\varepsilon\cdot\min\left\\{1,2\cdot\delta\cdot\tilde{I}_{\pi}\left(\frac{1}{4}\right)\right\\}$,

  3. 3.

${\rm\gamma}_{P}\geqslant\frac{1}{2}\cdot\left[\Phi_{P}^{*}\right]^{2}\geqslant
2^{-5}\cdot\varepsilon^{2}\cdot\min\left\\{1,4\cdot\delta^{2}\cdot\tilde{I}_{\pi}\left(\frac{1}{4}\right)^{2}\right\\}.$

Furthermore, let $\varepsilon_{{\rm Mix}}\in\left(0,8\right)$ and $\mu\ll\pi$
be a probability measure. To ensure that

$\left\|P^{n}\left(\frac{{\rm d}\mu}{{\rm
d}\pi}-1\right)\right\|_{2}^{2}\leqslant\varepsilon_{{\rm Mix}},$

it suffices to take

$\displaystyle n$ $\displaystyle\geqslant
2+2^{6}\cdot\varepsilon^{-2}\cdot\max\left\\{\log\left(\frac{u_{0}}{4\cdot
v_{*}^{-1}}\right),0\right\\}$
$\displaystyle+2^{8}\cdot\varepsilon^{-2}\cdot\delta^{-2}\cdot\int_{\max\left\\{\min\left\\{2\cdot
u_{0}^{-1},1/4\right\\},v_{*}/2\right\\}}^{1/4}\frac{\xi}{\tilde{I}_{\pi}\left(\xi\right)^{2}}\,{\rm
d}\xi.$
$\displaystyle+2^{4}\cdot\max\left\\{1,2^{-2}\cdot\delta^{-2}\cdot\tilde{I}_{\pi}\left(\frac{1}{4}\right)^{-2}\right\\}\cdot\varepsilon^{-2}\cdot\log\left(\max\left\\{\frac{\min\left\\{u_{0},8\right\\}}{\varepsilon_{{\rm
Mix}}},1\right\\}\right).$

where $u_{0}:=\left\|\frac{{\rm d}\mu}{{\rm d}\pi}-1\right\|_{2}^{2}$ and

$v_{*}:=\min\left\\{\frac{1}{2},\max\left\\{0,\sup\left\\{v>0:1\leqslant\frac{1}{2}\cdot\delta\cdot\frac{\tilde{I}_{\pi}\left(\frac{1}{2}\cdot
v\right)}{\frac{1}{2}\cdot v}\right\\}\right\\}\right\\}.$ (6)

###### Proof.

By Corollary 16, we have

$\displaystyle\Phi_{P}\left(v\right)$
$\displaystyle\geqslant\frac{1}{4}\cdot\varepsilon\cdot\min\left\\{1,\frac{1}{2}\cdot\delta\cdot\frac{\tilde{I}_{\pi}\left(\frac{1}{2}\cdot
v\right)}{\frac{1}{2}\cdot v}\right\\}\qquad v\in\big{(}0,1/2\big{]},$

and the bounds on $\Phi_{P}^{*}$ and $\gamma_{P}$ follow then from Definition
3, Lemma 5 and positivity of $P$. Writing $h=\frac{{\rm d}\mu}{{\rm d}\pi}$
and $u_{n}:={\rm Var}_{\pi}\left(P^{n}h\right)=\chi^{2}\left(\mu
P^{n},\pi\right)$, we recall by Theorem 8 that in order to ensure that
$u_{n}\leqslant\varepsilon_{{\rm Mix}}$, it suffices to take

$n\geqslant 2+4\cdot\int_{\min\left\\{4\cdot
u_{0}^{-1},1/2\right\\}}^{1/2}\frac{{\rm
d}v}{v\cdot\Phi_{P}\left(v\right)^{2}}+\left[\Phi_{P}^{*}\right]^{-2}\cdot\log\left(\max\left\\{\frac{\min\left\\{u_{0},8\right\\}}{\varepsilon_{{\rm
Mix}}},1\right\\}\right).$

Then for $v\in\left(0,v_{*}\right)$, as defined in (6), it holds that
$\Phi_{P}\left(v\right)\geqslant\frac{1}{4}\cdot\varepsilon$, and for
$v\in\left(v_{*},\frac{1}{2}\right)$, it holds that
$\Phi_{P}\left(v\right)\geqslant\frac{1}{8}\cdot\varepsilon\cdot\delta\cdot\frac{\tilde{I}_{\pi}\left(\frac{1}{2}\cdot
v\right)}{\frac{1}{2}\cdot v}$. One thus writes

$\displaystyle\int_{\min\left\\{4\cdot
u_{0}^{-1},1/2\right\\}}^{1/2}\frac{1}{v\cdot\Phi_{P}\left(v\right)^{2}}\,{\rm
d}v$ $\displaystyle=\int_{\min\left\\{4\cdot
u_{0}^{-1},1/2\right\\}}^{\max\left\\{\min\left\\{4\cdot
u_{0}^{-1},1/2\right\\},v_{*}\right\\}}\frac{1}{v\cdot\Phi_{P}\left(v\right)^{2}}\,{\rm
d}v$ $\displaystyle+\int_{\max\left\\{\min\left\\{4\cdot
u_{0}^{-1},1/2\right\\},v_{*}\right\\}}^{1/2}\frac{1}{v\cdot\Phi_{P}\left(v\right)^{2}}\,{\rm
d}v.$

We treat the two integrals separately. For the first, write

$\displaystyle\int_{\min\left\\{4\cdot
u_{0}^{-1},1/2\right\\}}^{\max\left\\{\min\left\\{4\cdot
u_{0}^{-1},1/2\right\\},v_{*}\right\\}}\frac{{\rm
d}v}{v\cdot\Phi_{P}\left(v\right)^{2}}$
$\displaystyle\leqslant\int_{\min\left\\{4\cdot
u_{0}^{-1},1/2\right\\}}^{\max\left\\{\min\left\\{4\cdot
u_{0}^{-1},1/2\right\\},v_{*}\right\\}}\frac{1}{v\cdot\left(\frac{1}{4}\cdot\varepsilon\right)^{2}}\,{\rm
d}v$
$\displaystyle=2^{4}\cdot\varepsilon^{-2}\cdot\log\left(\frac{\max\left\\{\min\left\\{4\cdot
u_{0}^{-1},1/2\right\\},v_{*}\right\\}}{\min\left\\{4\cdot
u_{0}^{-1},\frac{1}{2}\right\\}}\right)$
$\displaystyle=2^{4}\cdot\varepsilon^{-2}\cdot\max\left\\{\log\left(\frac{u_{0}}{4\cdot
v_{*}^{-1}}\right),0\right\\},$

where the final equality follows from a case-by-case analysis. For the second,
write

$\displaystyle\int_{\max\left\\{\min\left\\{4\cdot
u_{0}^{-1},1/2\right\\},v_{*}\right\\}}^{1/2}$ $\displaystyle\frac{{\rm
d}v}{v\cdot\Phi_{P}\left(v\right)^{2}}$
$\displaystyle\leqslant\int_{\max\left\\{\min\left\\{4\cdot
u_{0}^{-1},1/2\right\\},v_{*}\right\\}}^{1/2}\frac{1}{v\cdot\left(\frac{1}{8}\cdot\varepsilon\cdot\delta\cdot\frac{\tilde{I}_{\pi}\left(\frac{1}{2}\cdot
v\right)}{\frac{1}{2}\cdot v}\right)^{2}}\,{\rm d}v$
$\displaystyle=2^{6}\cdot\varepsilon^{-2}\cdot\delta^{-2}\cdot\int_{\max\left\\{\min\left\\{4\cdot
u_{0}^{-1},1/2\right\\},v_{*}\right\\}}^{1/2}\frac{\left(\frac{1}{2}\cdot
v\right)^{2}}{v\cdot\tilde{I}_{\pi}\left(\frac{1}{2}\cdot v\right)^{2}}\,{\rm
d}v$
$\displaystyle=2^{6}\cdot\varepsilon^{-2}\cdot\delta^{-2}\cdot\int_{\max\left\\{\min\left\\{4\cdot
u_{0}^{-1},1/2\right\\},v_{*}\right\\}}^{1/2}\frac{\left(\frac{1}{2}\cdot
v\right)}{\tilde{I}_{\pi}\left(\frac{1}{2}\cdot v\right)^{2}}\,{\rm
d}\left(\frac{1}{2}\cdot v\right)$
$\displaystyle=2^{6}\cdot\varepsilon^{-2}\cdot\delta^{-2}\cdot\int_{\max\left\\{\min\left\\{2\cdot
u_{0}^{-1},1/4\right\\},v_{*}/2\right\\}}^{1/4}\frac{\xi}{\tilde{I}_{\pi}\left(\xi\right)^{2}}\,{\rm
d}\xi.$

For the final term, we have $\Phi_{P}^{*}=\Phi_{P}(\frac{1}{2})\geqslant
2^{-2}\cdot\varepsilon\cdot\min\left\\{1,2\cdot\delta\cdot\tilde{I}_{\pi}\left(\frac{1}{4}\right)\right\\}$.
We conclude by combining these bounds. ∎

We conclude our general results with a result that can be used to establish
the close-coupling condition for Metropolis kernels, which we will use in the
sequel to analyze both the RWM and pCN Markov chains.

######  Lemma 19.

Let $Q$ be a $\nu$-reversible Markov kernel where $\nu\gg\pi$ is a
$\sigma$-finite measure, $P$ be the $\pi$-reversible Metropolis kernel with
proposal $Q$ defined by (1) and
$\alpha_{0}:=\inf_{x\in\mathsf{E}}\alpha\left(x\right)$. Then

$\left\|P\left(x,\cdot\right)-P\left(y,\cdot\right)\right\|_{{\rm
TV}}\leqslant\left\|Q\left(x,\cdot\right)-Q\left(y,\cdot\right)\right\|_{{\rm
TV}}+1-\alpha_{0},\qquad x,y\in\mathsf{E}.$

###### Proof.

Let $x,y\in\mathsf{E}$ be arbitrary. We write
$\varpi=\frac{\mathrm{d}\pi}{\mathrm{d}\nu}$. We construct a specific coupling
of $\left(X^{{}^{\prime}},Y^{{}^{\prime}}\right)$ such that
$X^{{}^{\prime}}\sim P\left(x,\cdot\right)$ and $Y^{{}^{\prime}}\sim
P\left(y,\cdot\right)$. Without loss of generality, we may assume that
$\varpi\left(x\right)\geqslant\varpi\left(y\right)$. Let
$\left(W_{x},W_{y}\right)$ be drawn from a maximal coupling of
$Q\left(x,\cdot\right)$ and $Q\left(y,\cdot\right)$, so that

$\mathbb{P}\left(W_{x}=W_{y}\right)=1-\left\|Q\left(x,\cdot\right)-Q\left(y,\cdot\right)\right\|_{{\rm
TV}}.$

With $\mathcal{U}\sim{\rm Unif}\left(0,1\right)$, we complete the
specification of the distribution of
$\left(X^{{}^{\prime}},Y^{{}^{\prime}}\right)$ via

$X^{{}^{\prime}}\mid\left\\{W_{x}=w_{x},W_{y}=w_{y},\mathcal{U}=u\right\\}=\begin{cases}w_{x}&u\leqslant\varpi\left(w_{x}\right)/\varpi\left(x\right),\\\
x&u>\varpi\left(w_{x}\right)/\varpi\left(x\right),\end{cases}$

and

$Y^{{}^{\prime}}\mid\left\\{W_{x}=w_{x},W_{y}=w_{y},\mathcal{U}=u\right\\}=\begin{cases}w_{y}&u\leqslant\varpi\left(w_{y}\right)/\varpi\left(y\right),\\\
y&u>\varpi\left(w_{y}\right)/\varpi\left(y\right).\end{cases}$

On the event
$\left\\{W_{x}=W_{y}\right\\}\cap\left\\{X^{{}^{\prime}}=W_{x}\right\\}$, we
have $X^{{}^{\prime}}=Y^{{}^{\prime}}=W_{x}$ since
$\varpi\left(x\right)\geqslant\varpi\left(y\right)$. Hence,

$\displaystyle\mathbb{P}\left(X^{{}^{\prime}}=Y^{{}^{\prime}}\right)$
$\displaystyle\geqslant\mathbb{P}\left(W_{x}=W_{y},X^{{}^{\prime}}=W_{x}\right)$
$\displaystyle\geqslant\mathbb{P}\left(W_{x}=W_{y}\right)+\mathbb{\mathbb{P}}\left(X^{{}^{\prime}}=W_{x}\right)-1$
$\displaystyle=\left(1-\left\|Q\left(x,\cdot\right)-Q\left(y,\cdot\right)\right\|_{{\rm
TV}}\right)+\mathbb{\mathbb{P}}\left(X^{{}^{\prime}}=W_{x}\right)-1$
$\displaystyle\geqslant\left(1-\left\|Q\left(x,\cdot\right)-Q\left(y,\cdot\right)\right\|_{{\rm
TV}}\right)+\alpha_{0}-1$
$\displaystyle=\alpha_{0}-\left\|Q\left(x,\cdot\right)-Q\left(y,\cdot\right)\right\|_{{\rm
TV}}.$

We conclude by the coupling inequality:
$\left\|P\left(x,\cdot\right)-P\left(y,\cdot\right)\right\|_{{\rm
TV}}\leqslant\mathbb{P}\left(X^{{}^{\prime}}\neq Y^{{}^{\prime}}\right)$. ∎

###  3.2 Examples of isoperimetric profiles

In this section, we provide some concrete examples of probability measures for
which the isoperimetric profile admits regular, concave and tractable
isoperimetric profiles or minorants. We first describe explicitly the profiles
associated to specific measures, and then describe some general results which
hold over well-behaved families of measures. The results in this subsection
are not originally ours, and are included in order to provide context on the
breadth of applicability of our main results.

####  3.2.1 Specific examples

######  Example 20.

Let $\varphi_{\gamma}$, $\Phi_{\gamma}$ denote the PDF and CDF respectively of
the one-dimensional standard Gaussian measure. For any $d\in\mathbb{N}$, the
isoperimetric profile of $\pi=\mathcal{N}\left(0,I_{d}\right)$ w.r.t.
$\left|\cdot\right|$ satisfies
$I_{\pi}\left(p\right)=\left(\varphi_{\gamma}\circ\Phi_{\gamma}^{-1}\right)\left(p\right)$
(Borell, 1975; Sudakov and Tsirel’son, 1978), which satisfies

$\lim_{p\to
0^{+}}\frac{I_{\pi}\left(p\right)}{p\cdot\left(\log\frac{1}{p}\right)^{1/2}}=\sqrt{2},$

see, e.g., Barthe and Maurey (2000). Observing that $I_{\pi}$ is concave and
regular, one can also deduce that

$I_{\pi}\left(p\right)\geqslant 2\cdot
I_{\pi}\left(\frac{1}{2}\right)\cdot\min\left\\{p,1-p\right\\}=\left(\frac{2}{\pi}\right)^{1/2}\cdot\min\left\\{p,1-p\right\\}.$

######  Example 21.

For the Laplace measure $\pi\left({\rm
d}x\right)\propto\exp\left(-\left|x\right|\right)\,{\rm d}x$ in one dimension,
the isoperimetric profile w.r.t. $\left|\cdot\right|$ is given by
$I_{\pi}\left(p\right)=\min\left\\{p,1-p\right\\}$ (see, e.g., Bobkov, 1999).

######  Example 22.

For the Subbotin measure $\pi\left({\rm
d}x\right)\propto\exp\left(-\left|x\right|^{\alpha}\right)\,{\rm d}x$ in one
dimension, with $\alpha\in\left(1,2\right)$, it holds that the isoperimetric
profile w.r.t. $\left|\cdot\right|$ can be bounded from below for
$p\in\left[0,\frac{1}{2}\right]$ as $I_{\pi}\left(p\right)\geqslant
K\left(\alpha\right)\cdot p\cdot\left(\log\frac{1}{p}\right)^{1-1/\alpha}$ for
some $K\left(\alpha\right)>0$ (see, e.g., Latała and Oleszkiewicz, 2000;
Barthe et al., 2006).

####  3.2.2 Functional inequalities

Many analyses of MCMC algorithms restrict to considering strongly log-concave
targets $\pi$, i.e. $U$ is strongly convex, to obtain quantitative bounds.
This means that for potentials with inhomogeneous local convexity properties,
but good global isoperimetric properties (e.g. strongly convex in the tails,
weakly convex in the center of the space), complexity bounds can be somewhat
pessimistic. In this subsection, we give some examples of how to estimate
isoperimetric profiles when $\pi$ is only log-concave, given additional
quantitative information about functional inequalities which they satisfy.

######  Example 23.

For any log-concave $\pi$, there exists $\gamma_{\pi}>0$ such that

$\forall f\,\text{locally Lipschitz,}\quad\pi\left(\left|\nabla
f\right|^{2}\right)\geqslant\gamma_{\pi}\cdot{\rm Var}_{\pi}\left(f\right),$

that is, $\pi$ satisfies a Poincaré inequality (see, e.g., Bakry et al., 2014,
Theorem 4.6.3). It is also known that Poincaré inequalities can be translated
into ${\rm L}^{1}$-Poincaré inequalities, with explicit control of the
constants (Cattiaux and Guillin, 2020). Finally, ${\rm L}^{1}$-Poincaré
inequalities are equivalent to isoperimetric inequalities with respect to
$\left|\cdot\right|$ of the form $I_{\pi}\left(p\right)\geqslant
c\cdot\min\left\\{p,1-p\right\\}$, with the same constant (see, e.g.,
Kolesnikov, 2007). Combining these facts, if $\pi$ is log-concave, one can
deduce that

$I_{\pi}\left(p\right)\geqslant\frac{1}{6}\cdot\gamma_{\pi}^{1/2}\cdot\min\left\\{p,1-p\right\\}.$

######  Example 24.

Consider log-concave $\pi$ satisfying a logarithmic Sobolev inequality with
constant $\lambda_{\pi}$, namely,

$\forall f\,\text{locally Lipschitz,}\quad\pi\left(\left|\nabla
f\right|^{2}\right)\geqslant\lambda_{\pi}\cdot{\rm
Ent}_{\pi}\left(f^{2}\right),$

where for positive $f$, ${\rm Ent}_{\pi}\left(f\right):=\pi\left(f\cdot\log
f\right)-\pi\left(f\right)\cdot\log\pi\left(f\right)$. A result of Ledoux
(2011) then gives the following bound for the isoperimetric profile w.r.t.
$\left|\cdot\right|$,

$I_{\pi}\left(p\right)\geqslant\frac{1}{34}\cdot\lambda_{\pi}^{1/2}\cdot
p\cdot\left(\log\frac{1}{p}\right)^{1/2}\quad\mathrm{for}\,p\in\left[0,\frac{1}{2}\right].$

######  Example 25.

For log-concave $\pi$ satisfying a $q$-log-Sobolev inequality (see Bobkov and
Zegarlinski, 2005), i.e.

$\forall f\,\text{locally Lipschitz,}\quad D\cdot{\rm
Ent}_{\pi}\left(\left|f\right|^{q}\right)\leqslant\pi\left(\left|\nabla
f\right|_{q}^{q}\right),$

a result of Milman (2009b) establishes that for the isoperimetric profile
w.r.t. $\left|\cdot\right|$,

$I_{\pi}\left(p\right)\geqslant c_{q}\cdot D\cdot
p\cdot\left(\log\frac{1}{p}\right)^{1/q}\quad\text{for
}p\in\big{(}0,1/2\big{]},$

where $c_{q}>0$ is universal. Note that for $q=2$, this entails the standard
log-Sobolev inequality; for $q\in\left[1,2\right)$, the assumption becomes
stronger and corresponds to potentials which have tail behaviour like
$U\left(x\right)\sim\left|x\right|^{q_{*}}$, where $q^{-1}+q_{*}^{-1}=1$,
interpreting $q=1$ as the setting of $\pi$ with compact support.

####  3.2.3 Transfer principles

Another practical aspect of working with isoperimetric profiles is that they
are often preserved under suitably regular perturbations, some of which we
detail here. These transfer principles can be used to accommodate potentials
that are not convex. The first of these concerns the transfer of isoperimetric
properties under Lipschitz transport; related statements are made in Barthe
(2001).

######  Lemma 26.

For $i=1,2$, let $\mu_{i}$ be a probability measure on the metric space
$\left(\mathsf{E}_{i},\mathsf{d}_{i}\right)$. Suppose that these measures are
related through transport as

$\mu_{2}=T_{\\#}\mu_{1},$

where $T:\mathsf{E}_{1}\to\mathsf{E}_{2}$ is a Lipschitz bijection. Then, for
$\tilde{I}$ any isoperimetric minorant of $\mu_{1}$ w.r.t. $\mathsf{d}_{1}$,
it holds that $\left|T\right|_{{\rm Lip}}^{-1}\cdot\tilde{I}$ is an
isoperimetric minorant of $\mu_{2}$ w.r.t. the metric $\mathsf{d}_{2}$. In
particular, if $T$ is also an isometry, then $\mu_{1}$ and $\mu_{2}$ have
identical isoperimetric profiles w.r.t. their respective metrics.

###### Proof.

Let $A\subseteq\mathsf{E}_{2}$ be measurable and
$A_{r}=\left\\{x\in\mathsf{E}_{2}:\mathsf{d}_{2}\left(x,A\right)\leqslant
r\right\\}$. Write $B:=T^{-1}\left(A\right)$, and compute that

$\displaystyle A_{r}$
$\displaystyle=\left\\{x\in\mathsf{E}:\mathsf{d}_{2}\left(x,A\right)\leqslant
r\right\\}$
$\displaystyle=\left\\{x\in\mathcal{\mathsf{E}}:\mathsf{d_{2}}\left(T\left(T^{-1}\left(x\right)\right),T\left(B\right)\right)\leqslant
r\right\\}$
$\displaystyle\supseteq\left\\{T\left(y\right)\in\mathsf{E}:\mathsf{d}_{1}\left(y,B\right)\leqslant\left|T\right|_{{\rm
Lip}}^{-1}\cdot r\right\\}$ $\displaystyle=T\left(B_{\left|T\right|_{{\rm
Lip}}^{-1}\cdot r}\right),$

where $B_{s}:=\left\\{y\in\mathsf{E}:\mathsf{d}_{1}\left(y,B\right)\leqslant
s\right\\}$. Then

$\frac{\mu_{2}\left(A_{r}\right)-\mu_{2}\left(A\right)}{r}\geqslant\frac{\mu_{2}\left(T\left(B_{\left|T\right|_{{\rm
Lip}}^{-1}\cdot
r}\right)\right)-\mu_{2}\left(T\left(B\right)\right)}{r}=\frac{\mu_{1}\left(B_{\left|T\right|_{{\rm
Lip}}^{-1}\cdot r}\right)-\mu_{1}\left(B\right)}{r},$

whence it follows that

$\displaystyle\mu_{2,\mathsf{d}_{2}}^{+}\left(A\right)$
$\displaystyle=\lim\inf_{r\to
0^{+}}\frac{\mu_{2}\left(A_{r}\right)-\mu_{2}\left(A\right)}{r}$
$\displaystyle\geqslant\lim\inf_{r\to
0^{+}}\frac{\mu_{1}\left(B_{\left|T\right|_{{\rm Lip}}^{-1}\cdot
r}\right)-\mu_{1}\left(B\right)}{r}$ $\displaystyle\geqslant\lim\inf_{s\to
0^{+}}\frac{\mu_{1}\left(B_{s}\right)-\mu_{1}\left(B\right)}{\left|T\right|_{{\rm
Lip}}\cdot s}$ $\displaystyle=\left|T\right|_{{\rm
Lip}}^{-1}\cdot\mu_{1,\mathsf{d}_{1}}^{+}\left(B\right).$

By definition of isoperimetric minorants and $\mu_{2}$, it holds that
$\mu_{1,\mathsf{d}_{1}}^{+}\left(B\right)\geqslant\tilde{I}\left(\mu_{1}\left(B\right)\right)=\tilde{I}\left(\mu_{2}\left(A\right)\right)$,
so the first result follows. For the second result, note that bjiective
isometries from $\mathsf{E}_{1}$ to $\mathsf{E}_{2}$ satisfy
$\left|T\right|_{\mathrm{Lip}}=\left|T^{-1}\right|_{{\rm\mathrm{Lip}}}=1$
(noting that these Lipschitz norms are technically defined on different
spaces), and that the isoperimetric profile is always an isoperimetric
minorant. Applying the first result in both directions allows us to conclude.
∎

The following result will be used frequently in the sequel, where $m$-strong
convexity of $U$ is assumed.

######  Lemma 27.

For an $m$-strongly convex potential $U$, with
$\mathsf{d}=\left|\cdot\right|$, we have

$I_{\pi}\left(p\right)\geqslant
m^{1/2}\cdot\left(\varphi_{\gamma}\circ\Phi_{\gamma}^{-1}\right)\left(p\right)\geqslant
C_{\ell}\cdot
m^{1/2}\cdot\min\left\\{p,1-p\right\\}\cdot\left(\log\frac{1}{\min\left\\{p,1-p\right\\}}\right)^{1/2},$

where
$C_{\ell}:=\left(\frac{2}{\pi\cdot\log\left(2\right)}\right)^{1/2}\geqslant
0.958357$. Moreover, if we let
$\tilde{I}_{\pi}\left(p\right):=m^{1/2}\cdot\left(\varphi_{\gamma}\circ\Phi_{\gamma}^{-1}\right)\left(p\right)$,
which is regular and concave, then

$\tilde{I}_{\pi}\left(\frac{1}{4}\right)=m^{1/2}\cdot C_{{\rm\gamma}},$

where
$C_{{\rm\gamma}}:=\left(\varphi\circ\Phi^{-1}\right)\left(\frac{1}{4}\right)\geqslant
0.3177765$.

###### Proof.

By the contraction principle of Caffarelli (2000), it is known that if one
takes $\mu=\mathcal{N}\left(0,m^{-1}\cdot I_{d}\right)$, then there exists a
1-Lipschitz mapping $T$ which pushes $\mu$ onto $\pi$, and hence a
$m^{-1/2}$-Lipschitz mapping which pushes $\mathcal{N}\left(0,I_{d}\right)$
onto $\pi$. By Lemma 26, the first inequality follows. For the second
inequality, observe that the function

$g(p)=\frac{\left(\varphi_{\gamma}\circ\Phi_{\gamma}^{-1}\right)\left(p\right)}{p\cdot\left(\log\left(\frac{1}{p}\right)\right)^{1/2}},$

is minimized on $(0,\frac{1}{2}]$ at $\frac{1}{2}$; see Figure 2, and defining
$C_{\ell}=g\left(\frac{1}{2}\right)$ gives the second inequality. The final
claim is a direct computation. ∎

######  Example 28.

Isoperimetric profiles also transfer under bounded changes of measure, in the
style of e.g. Holley and Stroock (1986). In particular, suppose that $\mu$ has
isoperimetric profile $I_{\mu}$, and that $\frac{{\rm d}\nu}{{\rm
d}\mu}\geqslant c>0$. One can then compute for $A\in\mathcal{E}$ that

$\nu\left(A_{r}\right)-\nu\left(A\right)=\nu\left(A_{r}\cap
A^{\complement}\right)\geqslant c\cdot\mu\left(A_{r}\cap
A^{\complement}\right)=c\cdot\left(\mu\left(A_{r}\right)-\mu\left(A\right)\right),$

from which it is straightforward to deduce that $I_{\nu}\geqslant c\cdot
I_{\mu}$.

######  Remark 29.

The above example provides an improvement of Belloni and Chernozhukov (2009,
Lemma 2), who (essentially) work in the setting of probability measures whose
density can be expressed as

$\pi\left(x\right)=\exp\left(-\frac{1}{2}\left|x\right|^{2}-V\left(x\right)-\xi\left(x\right)\right),$

where $V$ is convex, and $\xi$ is uniformly bounded above and below. They
deduce a ‘pseudo’-three-set isoperimetric inequality of the form

$\pi\left(S_{3}\right)\geqslant c\cdot\exp\left(-{\rm
Osc}\left(\xi\right)\right)\cdot t\cdot\exp\left(-\frac{1}{2}\cdot
t^{2}\right)\cdot\min\left\\{\pi\left(S_{1}\right),\pi\left(S_{2}\right)\right\\},$

where ${\rm Osc}\left(\xi\right):={\rm ess}\sup\xi-{\rm ess}\inf\xi$,
$t=\mathsf{d}\left(S_{1},S_{2}\right)$, $\mathsf{d}=\left|\cdot\right|$ , and
$c>0$ is an explicit constant.

In fact, using Caffarelli’s result, one can see that
$\exp\left(-\frac{1}{2}\left|x\right|^{2}-V\left(x\right)\right)\,{\rm d}x$
will admit $\varphi_{\gamma}\circ\Phi_{\gamma}^{-1}$ as an isoperimetric
minorant, and so combining this with the Holley–Stroock-type result, one
obtains that $\pi$ satisfies the inequality

$\pi\left(S_{3}\right)\geqslant\exp\left(-{\rm
Osc}\left(\xi\right)\right)\cdot\mathsf{d}\left(S_{1},S_{2}\right)\cdot\left(\varphi_{\gamma}\circ\Phi_{\gamma}^{-1}\right)\left(\min\left\\{\pi\left(S_{1}\right),\pi\left(S_{2}\right)\right\\}\right),$

which relates to a result of Bobkov (2010) (which is stronger, but only valid
in dimension $1$). Combining this observation with the spectral profile
approach and the other calculations of Belloni and Chernozhukov (2009), it
seems likely that one could improve the dimension-dependence of their results.
We do not pursue this claim further in this work.

######  Example 30.

It is known that under suitable convexity assumptions that isoperimetric
profiles ‘almost’ tensorize, i.e. that the isoperimetric profile of
$\pi^{\otimes n}$ satisfies $\inf_{n\geqslant 1}I_{\pi^{\otimes n}}\geqslant
c\cdot I_{\pi}$ for some constant $c>0$. In particular, the isoperimetric
profile of product measures can be lower-bounded independently of dimension.
We refer the reader to Bobkov and Houdré (1997a); Roberto (2010) for details.

Figure 2: A plot of
$p\mapsto\frac{\left(\varphi_{\gamma}\circ\Phi_{\gamma}^{-1}\right)\left(p\right)}{p\cdot\left[\log\left(\frac{1}{p}\right)\right]^{1/2}}$.

###  3.3 From spectral profile to mixing times: examples

In this section, we describe how to combine an isoperimetric profile for $\pi$
with the close coupling condition assumption on $P$ to estimate mixing times
for the chain. Write
$u_{0}=\left\|\frac{\mathrm{d}\mu}{\mathrm{d}\pi}-1\right\|_{2}$ for the
initial $\mathrm{L}^{2}$ distance to equilibrium.

In all of our examples, our isoperimetric minorants take the form
$\tilde{I}_{\pi}\left(p\right)=c\cdot p\cdot\log\left(\frac{1}{p}\right)^{r}$
for $p\in\left(0,\frac{1}{2}\right]$, with $r\in\left[0,1\right]$. We briefly
recap how the $r$ parameter maps onto simple assumptions, before providing
explicit calculations:

  * •

$r=0$ is ‘exponential-type’ isoperimetry, which holds for any log-concave
measure and corresponds roughly to potentials which have a tail growth of
order or faster than $\left|x\right|$.

  * •

$r=\frac{1}{2}$ is ‘Gaussian-type’ isoperimetry, which holds for any log-
concave measure with sub-Gaussian tails.

  * •

$r\in\left[0,\frac{1}{2}\right]$ corresponds to ‘intermediate’ isoperimetry,
and roughly corresponds to potentials which have tail growth
$U\left(x\right)\sim\left|x\right|^{\frac{1}{1-r}}\in\left(\left|x\right|^{1},\left|x\right|^{2}\right)$.

  * •

$r\in\left[\frac{1}{2},1\right]$ corresponds to ‘light-tailed’ isoperimetry,
and roughly corresponds to potentials which have tail growth
$U\left(x\right)\sim\left|x\right|^{\frac{1}{1-r}}\gg\left|x\right|^{2}$.

Now, to compute: recall by Theorem 18 that in order to ensure that
$\left\|P^{n}\left(\frac{\mathrm{d}\mu}{\mathrm{d}\pi}-1\right)\right\|_{2}\leqslant\varepsilon_{{\rm
Mix}}\leqslant 8$, it suffices to take

$\displaystyle n$ $\displaystyle\geqslant
2+2^{6}\cdot\varepsilon^{-2}\cdot\max\left\\{\log\left(\frac{u_{0}}{4\cdot
v_{*}^{-1}}\right),0\right\\}$
$\displaystyle+2^{8}\cdot\varepsilon^{-2}\cdot\delta^{-2}\cdot\int_{\max\left\\{\min\left\\{2\cdot
u_{0}^{-1},1/4\right\\},v_{*}/2\right\\}}^{1/4}\frac{\xi}{\tilde{I}_{\pi}\left(\xi\right)^{2}}\,{\rm
d}\xi.$
$\displaystyle+2^{4}\cdot\max\left\\{1,2^{-2}\cdot\delta^{-2}\cdot\tilde{I}_{\pi}\left(\frac{1}{4}\right)^{-2}\right\\}\cdot\varepsilon^{-2}\cdot\log\left(\max\left\\{\frac{\min\left\\{u_{0},8\right\\}}{\varepsilon_{{\rm
Mix}}},1\right\\}\right).$

Assuming for now that $u_{0}\geqslant 8$ is intermediate, and $v_{*}\leqslant
4\cdot u_{0}^{-1}$ is small, with $v_{*}$ given in (6), we focus on the value
of the middle integral,

$\int_{2\cdot
u_{0}^{-1}}^{1/4}\frac{\xi}{\tilde{I}_{\pi}\left(\xi\right)^{2}}\,{\rm
d}\xi=c^{-2}\cdot\int_{2\cdot
u_{0}^{-1}}^{1/4}\frac{1}{\xi\cdot\log\left(\frac{1}{\xi}\right)^{2r}}\,{\rm
d}\xi=c^{-2}\cdot\int_{\log\left(4\right)}^{\log\left(u_{0}/2\right)}\frac{{\rm
d}u}{u^{2r}}.$

There is now a trichotomy of behaviours based upon the relative positions of
$r$ and $\frac{1}{2}$ (recalling that in practice, the parameter $\varepsilon$
is typically of constant order):

  * •

If $r\in\left[\frac{1}{2},1\right]$, then the inner integral evaluates to
$\frac{1}{2r-1}\cdot\left(\log\left(4\right)^{-\left(2r-1\right)}-\log\left(u_{0}/2\right)^{-\left(2r-1\right)}\right)\in\mathcal{O}\left(1\right)$.
The total mixing time then scales roughly like

$\max\left\\{\log\left(\frac{u_{0}}{4\cdot
v_{*}^{-1}}\right),0\right\\}+\delta^{-2}\cdot\left\\{{\bf
1}_{u_{0}>8}+\log\frac{1}{\varepsilon_{{\rm Mix}}}\right\\}.$

  * •

If $r=\frac{1}{2}$, then the inner integral evaluates to
$\log\left(\frac{\log\left(u_{0}/2\right)}{\log\left(4\right)}\right)\in\mathcal{O}\left(\log\log
u_{0}\right)$. The total mixing time then scales roughly like

$\max\left\\{\log\left(\frac{u_{0}}{4\cdot
v_{*}^{-1}}\right),0\right\\}+\delta^{-2}\cdot\left\\{\log\min\left\\{\log
u_{0},v_{*}^{-1}\right\\}\cdot{\bf 1}_{u_{0}>8}+\log\frac{1}{\varepsilon_{{\rm
Mix}}}\right\\}.$

  * •

If $r\in\left[0,\frac{1}{2}\right]$, then the inner integral evaluates to
$\frac{1}{1-2r}\cdot\left(\log\left(u_{0}/2\right)^{1-2r}-\log\left(4\right)^{1-2r}\right)\in\mathcal{O}\left(\log\left(u_{0}\right)^{1-2r}\right)$.
The total mixing time then scales roughly like

$\max\left\\{\log\left(\frac{u_{0}}{4\cdot
v_{*}^{-1}}\right),0\right\\}+\delta^{-2}\cdot\left\\{\left(\min\left\\{\log
u_{0},v_{*}^{-1}\right\\}\right)^{1-2r}\cdot{\bf
1}_{u_{0}>8}+\log\frac{1}{\varepsilon_{{\rm Mix}}}\right\\}.$

In particular, when $r=0$, one obtains the same
$\mathcal{O}\big{(}\log\left(u_{0}\right)\big{)}$ dependence implied by a
standard spectral gap approach, i.e. the spectral profile provides no strict
benefit. Indeed for $\delta$ sufficiently small one checks that $v_{*}=0$, and
so the first term vanishes entirely. Moreover, the second and third terms are
qualitatively identical, and thus there is no ‘three-phase’ behaviour, but
instead only one phase.

Recalling that $v_{*}^{-1}$ grows rapidly as $\delta$ decreases we see that
the effect of $\delta^{-2}$ is amplified for large $u_{0}$ or $v_{*}^{-1}$ for
$r\leqslant 1/2$, roughly corresponding to distributions with tails heavier
than Gaussians, and that this is not the case for lighter tailed distributions
i.e. $r>1/2$.

##  4 Spectral gap of RWM in high dimensions

In Sections 4–5, we denote by $P$ the RWM kernel defined by (1) with $Q$ the
Gaussian proposal kernel defined for a fixed but arbitrary $\sigma>0$ by

$Q\left(x,A\right)=\int{\bf 1}_{A}\left(x+\sigma\cdot z\right)\,{\cal
N}\left({\rm d}z;0,I_{d}\right),\qquad x\in\mathsf{E},A\in\mathscr{E}.$

Since $Q$ is reversible w.r.t. the Lebesgue measure on $\mathbb{R}^{d}$, we
have $\varpi=\pi\propto\exp\left(-U\right)$, following Assumption 9. It is
standard to deduce by Baxendale (2005, Lemma 3.1) that $P$ is a positive
Markov kernel for this particular $Q$. We note the following useful expression

$\alpha\left(x\right)=\int{\cal N}\left({\rm
d}z;0,I_{d}\right)\cdot\min\left\\{1,\exp\left(-\left(U\left(x+\sigma\cdot
z\right)-U\left(x\right)\right)\right)\right\\},$ (7)

and we also denote $\alpha_{0}=\inf_{x\in\mathsf{E}}\alpha\left(x\right)$.

For the purposes of obtaining explicit bounds and matching negative results
with dimension, we impose the following further assumption about $\pi$, noting
that Assumption 9 is already in force. As will be discussed in Section 4.4,
both $m$-strong convexity and $L$-smoothness can be weakened to obtain
explicit bounds on the spectral gap.

######  Assumption 31.

For some $0<m\leqslant L$, $U$ is $m$-strongly convex and $L$-smooth:

$\frac{m}{2}\cdot\left|h\right|^{2}\leqslant
U\left(x+h\right)-U\left(x\right)-\left\langle\nabla
U\left(x\right),h\right\rangle\leqslant\frac{L}{2}\cdot\left|h\right|^{2},\qquad
x,h\in\mathsf{E}.$

We write $\kappa:=L/m$ for the condition number of the target measure.

######  Example 32.

Let $\pi=\mathcal{N}\left(0,\sigma_{0}^{2}\cdot I_{d}\right)$, so that
$U\left(x\right)=\frac{1}{2\cdot\sigma_{0}^{2}}\cdot\left|x\right|^{2}$. Then

$U\left(x+h\right)-U\left(x\right)-\left\langle\nabla
U\left(x\right),h\right\rangle=\frac{1}{2\cdot\sigma_{0}^{2}}\cdot\left|h\right|^{2},\qquad
x,h\in\mathsf{E},$

so $U$ is $m$-strongly convex and $L$-smooth with $L=m=1/\sigma_{0}^{2}$ and
$\kappa=1$.

Another natural class of examples with strongly convex and smooth potentials
comes from considering Bayesian posterior measures for which the prior is
normal, and the log-likelihood is concave with bounded Hessian.

######  Example 33.

Consider the task of Bayesian logistic regression, taking as prior
$\pi_{0}=\mathcal{N}\left(0,\sigma_{0}^{2}\cdot I_{d}\right)$, and observing
covariate-response pairs
$\left\\{\left(a_{i},y_{i}\right)\right\\}_{i=1}^{N}\subset\mathbb{R}^{d}\times\left\\{0,1\right\\}$.
The potential corresponding to the posterior measure is then given up to an
additive constant by

$U\left(x\right)=\frac{1}{2\cdot\sigma_{0}^{2}}\cdot\left|x\right|^{2}+\sum_{i=1}^{N}\left\\{\log\left(1+\exp\left(-\left\langle
a_{i},x\right\rangle\right)\right)-y_{i}\cdot\left\langle
a_{i},x\right\rangle\right\\}.$

Writing $A$ for the $N\times d$ matrix with rows given by the
$\left\\{a_{i}\right\\}$, one can check that $U$ is $m$-strongly convex and
$L$-smooth with $m\geqslant\frac{1}{\sigma_{0}^{2}}$ and
$L\leqslant\frac{1}{\sigma_{0}^{2}}+\frac{1}{4}\cdot\lambda_{{\rm
Max}}\left(AA^{\top}\right)$, $\lambda_{{\rm Max}}$ denoting the largest
eigenvalue of a symmetric matrix. This gives $\kappa\leqslant
1+\frac{1}{4}\cdot\sigma_{0}^{2}\cdot\lambda_{{\rm
Max}}\left(AA^{\top}\right)$.

###  4.1 Lower bound on the conductance and spectral gap

The following is a general result, depending only on macroscopic properties of
the target measure: if the measure has good isoperimetry, and the acceptance
rate is lower bounded, then the chain will equilibrate at a rate commensurate
with these properties (roughly in accordance with the convergence of the
overdamped Langevin diffuson with the same target measure), attenuated only by
the choice of $\sigma$.

######  Theorem 34.

Let $\pi$ admit a regular, concave isoperimetric minorant $\tilde{I}_{\pi}$
w.r.t. $\left|\cdot\right|$. Then

$\Phi_{P}^{*}\geqslant
2^{-3}\cdot\alpha_{0}\cdot\min\left\\{1,2\cdot\alpha_{0}\cdot\sigma\cdot\tilde{I}_{\pi}\left(\frac{1}{4}\right)\right\\},$

and

$\gamma_{P}\geqslant
2^{-7}\cdot\alpha_{0}^{2}\cdot\min\left\\{1,4\cdot\alpha_{0}^{2}\cdot\sigma^{2}\cdot\tilde{I}_{\pi}\left(\frac{1}{4}\right)^{2}\right\\}.$

###### Proof.

By Lemma 38, $P$ is
$\left(\left|\cdot\right|,\alpha_{0}\cdot\sigma,\frac{1}{2}\cdot\alpha_{0}\right)$-close-
coupling, and we conclude from Theorem 18. ∎

######  Corollary 35.

Under Assumption 31, let $\sigma=\varsigma\cdot L^{-1/2}\cdot d^{-1/2}$ for
any $\varsigma>0$, and $C_{\gamma}$ as in Lemma 27. Then

$\Phi_{P}^{*}\geqslant 2^{-4}\cdot
C_{\gamma}\cdot\varsigma\cdot\exp\left(-\varsigma^{2}\right)\cdot
d^{-1/2}\cdot\left(\frac{m}{L}\right)^{1/2},$

and

$\gamma_{P}\geqslant 2^{-9}\cdot
C_{\gamma}^{2}\cdot\varsigma^{2}\cdot\exp\left(-2\cdot\varsigma^{2}\right)\cdot
d^{-1}\cdot\frac{m}{L}.$

###### Proof.

By Corollary 40,
$\alpha_{0}\geqslant\frac{1}{2}\cdot\exp\left(-\frac{1}{2}\cdot\varsigma^{2}\right)$
and we can take $\tilde{I}_{\pi}\left(\frac{1}{4}\right)\geqslant m^{1/2}\cdot
C_{\gamma}$ by Lemma 27. Since

$C_{\gamma}\cdot\exp\left(-\frac{1}{2}\cdot\varsigma^{2}\right)\cdot\varsigma\cdot
L^{-1/2}\cdot d^{-1/2}\cdot m^{1/2}\leqslant
C_{\gamma}\cdot\mathrm{e}^{-1/2}\cdot 1<1,$

for any $d\in\mathbb{N}$ and $\varsigma>0$ (noting that $m\leqslant L$), we
deduce that

$\displaystyle\Phi_{P}^{*}$ $\displaystyle\geqslant
2^{-3}\cdot\alpha_{0}\cdot\min\left\\{1,2\cdot\alpha_{0}\cdot\sigma\cdot\tilde{I}_{\pi}\left(\frac{1}{4}\right)\right\\}$
$\displaystyle\geqslant
2^{-4}\cdot\exp\left(-\frac{1}{2}\cdot\varsigma^{2}\right)\cdot\min\left\\{1,\exp\left(-\frac{1}{2}\cdot\varsigma^{2}\right)\cdot\varsigma\cdot
L^{-1/2}\cdot d^{-1/2}\cdot m^{1/2}\cdot C_{\gamma}\right\\}$
$\displaystyle=2^{-4}\cdot
C_{\gamma}\cdot\varsigma\cdot\exp\left(-\varsigma^{2}\right)\cdot
d^{-1/2}\cdot\left(\frac{m}{L}\right)^{1/2},$

and the lower bound on $\gamma_{P}$ follows similarly. ∎

######  Remark 36.

We find that $\Phi_{P}^{*}\in\Omega\left(d^{-1/2}\right)$, and
$\gamma_{P}\in\Omega\left(d^{-1}\right)$. Fixing $\varsigma$, we obtain (non-
asymptotically) that

$\displaystyle\Phi_{P}^{*}\cdot d^{1/2}$ $\displaystyle\geqslant 2^{-4}\cdot
C_{\gamma}\cdot\varsigma\cdot\exp\left(-\varsigma^{2}\right)\cdot\left(\frac{m}{L}\right)^{1/2}$
$\displaystyle\geqslant
0.019861\cdot\varsigma\cdot\exp\left(-\varsigma^{2}\right)\cdot\left(\frac{m}{L}\right)^{1/2}.$

This lower bound is maximized in $\varsigma$ by taking
$\varsigma^{2}=\frac{1}{2}$, which yields

$\Phi_{P}^{*}\cdot d^{1/2}\geqslant
0.008518\cdot\left(\frac{m}{L}\right)^{1/2}$

This particular bound-maximizing value of $\varsigma$ is likely an artifact of
the proof technique; optimal scaling results of Roberts and Rosenthal (2001)
suggest that $\varsigma\approx 2.38$ is optimal in high dimensions when
$\pi=\mathcal{N}(0,I_{d})$ , although they do not provide a bound on the
conductance or spectral gap of the associated Markov kernel. Similarly, this
leads to the following bound for the spectral gap:

$\gamma_{P}\cdot d\geqslant 3.62784\times 10^{-5}\cdot\frac{m}{L}.$

The following lemma gives a useful bound on the total variation distance
between the proposals; the proof can be found in Appendix A.

######  Lemma 37.

If $v>0$ and $x,y\in\mathsf{E}$ satisfy $\left|x-y\right|\leqslant
v\cdot\sigma$,

$\left\|Q\left(x,\cdot\right)-Q\left(y,\cdot\right)\right\|_{{\rm
TV}}\leqslant\frac{1}{2}\cdot v.$

The following is a key lemma establishing the close coupling condition for
$P$.

######  Lemma 38.

$P$ is
$\left(\left|\cdot\right|,\alpha_{0}\cdot\sigma,\frac{1}{2}\cdot\alpha_{0}\right)$-close-
coupling.

###### Proof.

Assume $x,y\in\mathsf{E}$ are such that
$\left|x-y\right|\leqslant\alpha_{0}\cdot\sigma$. Then
$\left\|Q\left(x,\cdot\right)-Q\left(y,\cdot\right)\right\|_{{\rm
TV}}\leqslant\frac{1}{2}\cdot\alpha_{0}$ by Lemma 37. We conclude by applying
Lemma 19. ∎

To lower bound the acceptance rate for the RWM kernel, we first prove a result
which holds under a general smoothness condition on the potential $U$, and
then obtain the case of $L$-smoothness as a corollary.

######  Lemma 39.

Suppose that for some nonnegative, nondecreasing $\psi$, the potential $U$
satisfies the smoothness bound

$U\left(x+h\right)-U\left(x\right)-\left\langle\nabla
U\left(x\right),h\right\rangle\leqslant\psi\left(\left|h\right|\right),\qquad
x,h\in\mathsf{E}.$

  1. 1.

Then for any $\sigma\geqslant 0$,

$\alpha_{0}\geqslant\frac{1}{2}\cdot\exp\left(-\int{\cal N}\left({\rm
d}z;0,I_{d}\right)\cdot\psi\left(\sigma\cdot\left|z\right|\right)\right).$

  2. 2.

Let $\sigma=\varsigma\cdot d^{-1/2}$ where $\varsigma>0$ is arbitrary, $\psi$
be twice-differentiable, such that for some $c_{0},c_{1}>0$,

$\left(\varsigma\cdot\psi^{{}^{\prime\prime}}-\psi^{{}^{\prime}}\right)\left(t\right)\leqslant
c_{0}\cdot\exp\left(c_{1}\cdot t\right).$

Then

$\alpha_{0}\geqslant\frac{1}{2}\cdot\exp\left(-\psi\left(\varsigma\right)+\mathcal{O}\left(d^{-1}\right)\right)\in\Omega\left(1\right).$

###### Proof.

The proof proceeds by direct calculation. Let $x\in\mathsf{E}$ be arbitrary.
Applying the growth bound assumption, it holds that

$U\left(x+\sigma\cdot z\right)-U\left(x\right)\leqslant\left\langle\nabla
U\left(x\right),\sigma\cdot
z\right\rangle+\psi\left(\sigma\cdot\left|z\right|\right),$

and substituting this into (7) gives

$\displaystyle\alpha\left(x\right)$ $\displaystyle\geqslant\int{\cal
N}\left({\rm
d}z;0,I_{d}\right)\cdot\min\left\\{1,\exp\left(-\left\langle\nabla
U\left(x\right),\sigma\cdot
z\right\rangle-\psi\left(\sigma\cdot\left|z\right|\right)\right)\right\\}.$

Applying the inequality $\min\left\\{1,a\cdot
b\right\\}\geqslant\min\left\\{1,a\right\\}\cdot\min\left\\{1,b\right\\}$
establishes that

$\displaystyle\alpha\left(x\right)$ $\displaystyle\geqslant\int{\cal
N}\left({\rm
d}z;0,I_{d}\right)\cdot\min\left\\{1,\exp\left(-\left\langle\nabla
U\left(x\right),\sigma\cdot
z\right\rangle\right)\right\\}\cdot\min\left\\{1,\exp\left(-\psi\left(\sigma\cdot\left|z\right|\right)\right)\right\\}$
$\displaystyle\geqslant\int{\cal N}\left({\rm
d}z;0,I_{d}\right)\cdot\exp\left(-\psi\left(\sigma\cdot\left|z\right|\right)\right)\cdot\min\left\\{1,\exp\left(-\left\langle\nabla
U\left(x\right),\sigma\cdot z\right\rangle\right)\right\\}$
$\displaystyle=\int{\cal N}\left({\rm
d}z;0,I_{d}\right)\cdot\exp\left(-\psi\left(\sigma\cdot\left|z\right|\right)\right)\cdot\min\left\\{1,\exp\left(+\left\langle\nabla
U\left(x\right),\sigma\cdot z\right\rangle\right)\right\\},$

where the last equality follows from the change of variables $z\mapsto-z$.
Averaging these final two expressions and noting that
$\min\left\\{1,a\right\\}+\min\left\\{1,a^{-1}\right\\}\geqslant 1$, it
follows that

$\alpha\left(x\right)\geqslant\frac{1}{2}\cdot\int{\cal N}\left({\rm
d}z;0,I_{d}\right)\cdot\exp\left(-\psi\left(\sigma\cdot\left|z\right|\right)\right).$

By the convexity of $\psi\mapsto\exp\left(-\psi\right)$, we may apply Jensen’s
inequality to bound this integral from below, and so the first part follows.

Finally, take $\sigma=\varsigma\cdot d^{-1/2}$, and Taylor expand
$s\mapsto\psi\left(s^{1/2}\right)$ with a second-order remainder term around
$s=\varsigma^{2}$. Applying the hypothesis on the derivatives of $\psi$ then
yields that for sufficiently large $d$, there exists
$F\left(\varsigma\right)>0$ such that

$\int{\cal N}\left({\rm d}z;0,I_{d}\right)\cdot\psi\left(\varsigma\cdot
d^{-1/2}\cdot\left|z\right|\right)\leqslant\psi\left(\varsigma\right)+F\left(\varsigma\right)\cdot
d^{-1},$

and we conclude. ∎

######  Corollary 40.

Under Assumption 31, let $\sigma=\varsigma\cdot d^{-1/2}\cdot L^{-1/2}$ where
$\varsigma>0$ is arbitrary. Then

$\alpha_{0}\geqslant\frac{1}{2}\cdot\exp\left(-\frac{1}{2}\cdot\varsigma^{2}\right).$

###### Proof.

Assumption 31 implies that $U$ satisfies the growth bound

$U\left(x+h\right)-U\left(x\right)-\left\langle\nabla
U\left(x\right),h\right\rangle\leqslant\psi\left(\left|h\right|\right)$

with $\psi:r\mapsto\frac{1}{2}\cdot L\cdot r^{2}$. Applying the first part of
Lemma 39, we see that

$\displaystyle\alpha_{0}$
$\displaystyle\geqslant\frac{1}{2}\cdot\exp\left(-\int{\cal N}\left({\rm
d}z;0,I_{d}\right)\cdot\frac{1}{2}\cdot
L\cdot\sigma^{2}\cdot\left|z\right|^{2}\right)$
$\displaystyle=\frac{1}{2}\cdot\exp\left(-\frac{1}{2}\cdot
L\cdot\sigma^{2}\cdot d\right)$
$\displaystyle=\frac{1}{2}\cdot\exp\left(-\frac{1}{2}\cdot\varsigma^{2}\right).\qed$

###  4.2 Conductance and spectral gap upper bounds

To complement our lower bounds, we can show matching upper bounds with respect
to dimension under Assumption 31. This shows that the the conductance and
spectral gap must decrease at least as fast as
$\mathcal{O}\left(d^{-1/2}\right)$ and $\mathcal{O}\left(d^{-1}\right)$
respectively, and that these are the slowest polynomial decays possible.
Hence, we may infer that in terms of optimizing conductance and spectral gap,
$d^{-1}$ is the correct polynomial scaling of $\sigma^{2}$.

We emphasize that the upper bounds are uniform over the class of $m$-strongly
convex and $L$-smooth potentials, indicating that the dimension-dependence of
this particular class of target distributions is well-characterized by the
analysis. This is in contrast to bounds which rely only on specific examples
exhibiting poor performance, as in minimax complexity analysis: for example,
Wu et al. (2022) show that the optimal scaling of step-size with dimension in
the Metropolis-adjusted Langevin algorithm is not uniform in this class.

####  4.2.1 Conductance upper bounds

######  Theorem 41.

Under Assumption 31 and twice continuous-differentiability of $U$,

$\Phi_{P}^{*}\leqslant\min\left\\{4\cdot
L^{1/2}\cdot\sigma,\left(1+m\cdot\sigma^{2}\right)^{-d/2}\right\\}.$

Hence, among polynomial scalings of $\sigma$, the scaling $\sigma\sim
d^{-1/2}$ is optimal with $\Phi_{P}^{*}\sim d^{-1/2}$.

###### Proof.

The bounds follow from Propositions 44 and 45. Now let $\sigma=\varsigma\cdot
L^{-1/2}\cdot d^{-\beta}$. If $\beta\geqslant 1/2$, then we obtain
$\Phi_{P}^{*}\in\mathcal{O}\left(d^{-\beta}\right)$ and this is maximized by
taking $\beta=\frac{1}{2}$. Combined with Theorem 34 we may conclude that
$\Phi_{P}^{*}$ decays as $d^{-1/2}$ as $d\to\infty$ when $\beta=\frac{1}{2}$.
For $\beta<\frac{1}{2}$, we recall that by Proposition 45, the conductance
decays faster than any polynomial in $1/d$, and in particular, faster than
$d^{-1/2}$, from which the claim follows. ∎

######  Lemma 42.

Under Assumption 31, let $x_{*}$ be the (unique) minimizer of $U$. Then

$\left(\frac{m}{L}\right)^{d/2}\cdot\mathcal{N}\left(x;x_{*},L^{-1}\cdot
I_{d}\right)\leqslant\pi\left(x\right)\leqslant\left(\frac{L}{m}\right)^{d/2}\cdot\mathcal{N}\left(x;x_{*},m^{-1}\cdot
I_{d}\right).$

###### Proof.

Applying the definitions of $m$-strong convexity and $L$-smoothness, one sees
that

$\frac{m}{2}\cdot\left|x-x_{*}\right|^{2}\leqslant
U\left(x\right)-U\left(x_{*}\right)-\left\langle\nabla
U\left(x_{*}\right),x-x_{*}\right\rangle\leqslant\frac{L}{2}\cdot\left|x-x_{*}\right|^{2},$

and since $\nabla U\left(x_{*}\right)=0$, this can be simplified to

$\frac{m}{2}\cdot\left|x-x_{*}\right|^{2}\leqslant
U\left(x\right)-U\left(x_{*}\right)\leqslant\frac{L}{2}\cdot\left|x-x_{*}\right|^{2}.$

Recalling that
$\pi\left(x\right)=\frac{1}{Z}\cdot\exp\left(-U\left(x\right)\right)$ for some
normalizing constant $Z$, this implies that

$\left(\frac{2\pi}{L}\right)^{d/2}\cdot\mathcal{N}\left(x;x_{*},L^{-1}\cdot
I_{d}\right)\leqslant\pi\left(x\right)\cdot
Z\cdot\exp\left(U\left(x_{*}\right)\right)\leqslant\left(\frac{2\pi}{m}\right)^{d/2}\cdot\mathcal{N}\left(x;x_{*},m^{-1}\cdot
I_{d}\right).$

By integrating the above inequalities over space, one sees that

$\left(\frac{2\pi}{L}\right)^{d/2}\leqslant
Z\cdot\exp\left(U\left(x_{*}\right)\right)\leqslant\left(\frac{2\pi}{m}\right)^{d/2},$

and substituting these bounds into the preceding display completes the proof.
∎

######  Lemma 43.

Under Assumption 31 and twice continuous-differentiability of $U$, Assumption
31 holds for any finite-dimensional marginal of $\pi$.

###### Proof.

Preservation of $m$-strong log-concavity of the marginals of $\pi$ is shown by
Saumard and Wellner (2014, Theorem 3.8). For preservation of $L$-smoothness of
the potential of any marginal of $\pi$, write the state as
$x=\left(x_{1},x_{2}\right)$, such that
$\pi\left(x_{1},x_{2}\right)=\exp\left(-U\left(x_{1},x_{2}\right)\right)$, and
define the marginal
$\pi\left(x_{1}\right)=\int\exp\left(-U\left(x_{1},x_{2}\right)\right)\mathrm{d}x_{2}=\exp\left(-V\left(x_{1}\right)\right).$
Formal computations give that

$\displaystyle\nabla V\left(x_{1}\right)$
$\displaystyle={\bf\mathbb{E}}\left[\nabla_{x_{1}}U\left(x_{1},X_{2}\right)|X_{1}=x_{1}\right]$
$\displaystyle\nabla^{2}V\left(x_{1}\right)$
$\displaystyle={\bf\mathbb{E}}\left[\nabla_{x_{1}}^{2}U\left(x_{1},X_{2}\right)|X_{1}=x_{1}\right]-{\bf
Cov}\left[\nabla_{x_{1}}U\left(x_{1},X_{2}\right)|X_{1}=x_{1}\right].$

By the smoothness of $U$, for any fixed $x_{1}$ one can bound
$\left|\nabla_{x_{1}}U\left(x_{1},x_{2}\right)\right|\lesssim
1+\left|x_{2}\right|$,
$\left|\nabla_{x_{1}}^{2}U\left(x_{1},x_{2}\right)\right|\lesssim 1$, and
since log-concave measures admit moments of all orders, it is guaranteed that
the integrals above do indeed exist and are finite. Combining this with the
twice continuous-differentiability of $U$, we may validly interchange
differentiation and integration, so that the formal identities described above
hold.

Recalling that covariance matrices are positive-semidefinite and that $U$ is
$L$-smooth, compute that

$\displaystyle\nabla^{2}V\left(x_{1}\right)$
$\displaystyle={\bf\mathbb{E}}\left[\nabla_{x_{1}}^{2}U\left(x_{1},X_{2}\right)|X_{1}=x_{1}\right]-{\bf
Cov}\left[\nabla_{x_{1}}U\left(x_{1},X_{2}\right)|X_{1}=x_{1}\right]$
$\displaystyle\preceq{\bf\mathbb{E}}\left[\nabla_{x_{1}}^{2}U\left(x_{1},X_{2}\right)|X_{1}=x_{1}\right]$
$\displaystyle\preceq L\cdot I_{d},$

from which the $L$-smoothness of $V$ follows. ∎

######  Proposition 44.

Under Assumption 31 and twice continuous-differentiability of $U$,

$\Phi_{P}^{*}\leqslant 2\cdot L^{1/2}\cdot\sigma.$

###### Proof.

First, let $\nu_{1}$ be a median of $x_{1}$, the first coordinate of $x$,
under $\pi$, and let $x_{*,1}$ be the mode of the marginal law of $x_{1}$
under $\pi$, which exists and is unique as a consequence of Lemma 43. Now,
define $A=\left\\{x\in\mathsf{E}:x_{1}\geqslant\nu_{1}\right\\}$, so that
$\pi\left(A\right)=\frac{1}{2}$. We let
$Z\sim\mathcal{N}\left(0,I_{d}\right)$, and by neglecting the acceptance
probability, we obtain the bounds

$\displaystyle\left(\pi\otimes P\right)\left(A\times A^{\complement}\right)$
$\displaystyle=\int_{A}\pi\left({\rm
d}x\right)P\left(x,A^{\complement}\right)$
$\displaystyle=\int_{A}\pi\left({\rm d}x\right)\int_{\mathsf{E}}{\cal
N}\left({\rm d}z;0,I_{d}\right)\cdot\min\left\\{1,\frac{\pi\left(x+\sigma\cdot
z\right)}{\pi\left(x\right)}\right\\}\cdot{\bf 1}\left[x+\sigma\cdot z\in
A^{\complement}\right]$ $\displaystyle\leqslant\int_{A}\pi\left({\rm
d}x\right)\mathbb{P}\left(x+\sigma\cdot Z\in A^{\complement}\right)$
$\displaystyle=\int_{A}\pi\left({\rm
d}x\right)\mathbb{P}\left(x_{1}+\sigma\cdot Z_{1}<\nu_{1}\right)$
$\displaystyle=\int_{x_{1}\geqslant\nu_{1}}\pi_{1}\left({\rm
d}x_{1}\right)\mathbb{P}\left(x_{1}+\sigma\cdot Z_{1}<\nu_{1}\right),$

where $\pi_{1}$ is the marginal law of $x_{1}$ under $\pi$. Recall that by
Lemma 43, $\pi_{1}$ will also be $m$-strongly log-concave and admit an
$L$-smooth potential, and so we may apply Lemma 42 to control the density of
$\pi_{1}$ as $\pi_{1}\left({\rm
d}x_{1}\right)\leqslant\left(\frac{L}{m}\right)^{1/2}\cdot{\cal N}\left({\rm
d}x_{1};x_{*,1},m^{-1}\right)$. Substituting this, we may bound

$\displaystyle\left(\pi\otimes P\right)\left(A\times A^{\complement}\right)$
$\displaystyle\leqslant\left(\frac{L}{m}\right)^{1/2}\cdot\int_{x_{1}\geqslant\nu_{1}}{\cal
N}\left({\rm d}x_{1};x_{*,1},m^{-1}\right)\mathbb{P}\left(x_{1}+\sigma\cdot
Z_{1}<\nu_{1}\right)$
$\displaystyle=\left(\frac{L}{m}\right)^{1/2}\cdot\int_{x_{1}\geqslant\nu_{1}}{\cal
N}\left({\rm
d}x_{1};x_{*,1},m^{-1}\right)\mathbb{P}\left(Z_{1}<\frac{\nu_{1}-x_{1}}{\sigma}\right)$
$\displaystyle\leqslant\left(\frac{L}{m}\right)^{1/2}\cdot\int_{x_{1}\geqslant\nu_{1}}{\cal
N}\left({\rm
d}x_{1};x_{*,1},m^{-1}\right)\exp\left(-\frac{1}{2\cdot\sigma^{2}}\cdot\left(\nu_{1}-x_{1}\right)^{2}\right)$
$\displaystyle=\left(\frac{L}{2\pi}\right)^{1/2}\cdot\int_{x_{1}\geqslant\nu_{1}}\exp\left(-\frac{m}{2}\cdot\left(x_{1}-x_{*,1}\right)^{2}-\frac{1}{2\cdot\sigma^{2}}\cdot\left(\nu_{1}-x_{1}\right)^{2}\right){\rm
d}x_{1},$

where we have used the Chernoff bound
$\mathbb{P}\left(Z_{1}\leqslant-z\right)\leqslant\exp\left(-\frac{1}{2}z^{2}\right)$
for $z>0$, to move from the second to the third line.

Computing directly that

$\displaystyle\frac{m}{2}\left(x_{1}-x_{*,1}\right)^{2}+\frac{1}{2\cdot\sigma^{2}}\cdot\left(\nu_{1}-x_{1}\right)^{2}$
$\displaystyle=\frac{1}{2}\cdot\frac{1+m\cdot\sigma^{2}}{\sigma^{2}}\cdot\left(x_{1}-\frac{\nu_{1}+m\cdot\sigma^{2}\cdot
x_{*,1}}{1+m\cdot\sigma^{2}}\right)^{2}$ $\displaystyle\hskip
85.35826pt+\frac{m}{2\cdot\left(1+m\cdot\sigma^{2}\right)}\cdot\left(\nu_{1}-x_{*,1}\right)^{2},$

one sees that

$\displaystyle\pi\otimes P\left(A\times
A^{\complement}\right)\leqslant\left(\frac{L}{2\pi}\right)^{1/2}\cdot\int_{x_{1}\geqslant\nu_{1}}\exp\left(-\frac{1}{2}\cdot\frac{1+m\cdot\sigma^{2}}{\sigma^{2}}\cdot\left(x_{1}-\frac{\nu_{1}+m\cdot\sigma^{2}\cdot
x_{*,1}}{1+m\cdot\sigma^{2}}\right)^{2}\right.$ $\displaystyle\hskip
170.71652pt\cdot\exp\left(\left.-\frac{m}{2\cdot\left(1+m\cdot\sigma^{2}\right)}\cdot\left(\nu_{1}-x_{*,1}\right)^{2}\right)\right)\,{\rm
d}x_{1}$ $\displaystyle=$
$\displaystyle\left(\frac{L\cdot\sigma^{2}}{1+m\cdot\sigma^{2}}\right)^{1/2}\cdot\exp\left(-\frac{m}{2\cdot\left(1+m\cdot\sigma^{2}\right)}\cdot\left(\nu_{1}-x_{*,1}\right)^{2}\right)$
$\displaystyle\hskip 170.71652pt\cdot\int_{x_{1}\geqslant\nu_{1}}{\cal
N}\left({\rm d}x_{1};\frac{\nu_{1}+m\cdot\sigma^{2}\cdot
x_{*,1}}{1+m\cdot\sigma^{2}},\frac{\sigma^{2}}{1+m\cdot\sigma^{2}}\right)$
$\displaystyle\leqslant$
$\displaystyle\left(\frac{L\cdot\sigma^{2}}{1+m\cdot\sigma^{2}}\right)^{1/2}\cdot
1\cdot 1$ $\displaystyle\leqslant$ $\displaystyle\>L^{1/2}\cdot\sigma.$

Recalling that
$\pi\left(A\right)=\pi\left(A^{\complement}\right)=\frac{1}{2}$, the result
follows. ∎

######  Proposition 45.

Under Assumption 31,

$\Phi_{P}^{*}\leqslant\left(1+m\cdot\sigma^{2}\right)^{-d/2}.$

Furthermore, if $\sigma=\varsigma\cdot L^{-1/2}\cdot d^{-\beta}$ with
$\beta<1/2$, then $\Phi_{P}^{*}={\cal O}\left(\exp\left(-c\cdot
d^{1-2\cdot\beta}\right)\right)$ for any
$c\in\left(0,\frac{1}{2}\cdot\frac{m}{L}\cdot\varsigma^{2}\right)$, and in
particular, decays faster than any polynomial in $1/d$.

###### Proof.

By $m$-strong convexity of the potential, it holds that

$U\left(x+\sigma\cdot z\right)-U\left(x\right)\geqslant\left\langle\nabla
U\left(x\right),\sigma\cdot z\right\rangle+\frac{1}{2}\cdot
m\cdot\sigma^{2}\cdot\left|z\right|^{2},$

and substituting this into (7) we obtain

$\displaystyle\alpha\left(x\right)$ $\displaystyle\leqslant\int{\cal
N}\left({\rm
d}z;0,I_{d}\right)\cdot\min\left\\{1,\exp\left(-\left\langle\nabla
U\left(x\right),\sigma\cdot z\right\rangle-\frac{1}{2}\cdot
m\cdot\sigma^{2}\cdot\left|z\right|^{2}\right)\right\\}.$

Applying the inequality $\min\left\\{1,c\right\\}\leqslant c$ establishes that

$\alpha\left(x\right)\leqslant\int{\cal N}\left({\rm
d}z;0,I_{d}\right)\cdot\exp\left(-\left\langle\nabla
U\left(x\right),\sigma\cdot z\right\rangle-\frac{1}{2}\cdot
m\cdot\sigma^{2}\cdot\left|z\right|^{2}\right).$

Straightforward computations show that

$\displaystyle{\cal N}\left({\rm
d}z;0,I_{d}\right)\cdot\exp\left(-\left\langle\nabla
U\left(x\right),\sigma\cdot z\right\rangle-\frac{1}{2}\cdot
m\cdot\sigma^{2}\cdot\left|z\right|^{2}\right)=\left(1+m\cdot\sigma^{2}\right)^{-d/2}$
$\displaystyle\hskip
28.45274pt\cdot\exp\left(\frac{1}{2}\cdot\frac{\sigma^{2}\cdot\left|\nabla
U\left(x\right)\right|^{2}}{1+m\cdot\sigma^{2}}\right)\cdot{\cal N}\left({\rm
d}z;-\frac{\sigma}{1+m\cdot\sigma^{2}}\cdot\nabla
U\left(x\right),\frac{1}{1+m\cdot\sigma^{2}}\cdot I_{d}\right),$

which allows us to write

$\alpha\left(x\right)\leqslant\left(1+m\cdot\sigma^{2}\right)^{-d/2}\cdot\exp\left(\frac{1}{2}\cdot\frac{\sigma^{2}}{1+m\cdot\sigma^{2}}\cdot\left|\nabla
U\left(x\right)\right|^{2}\right).$

Now, for $\rho>0$, define the set

$B_{\rho}=\left\\{x:\frac{\sigma^{2}}{1+m\cdot\sigma^{2}}\cdot\left|\nabla
U\left(x\right)\right|^{2}\leqslant\rho^{2}\right\\},$

which for $\rho$ small enough will have
$0<\pi\left(B_{\rho}\right)<\pi\left(B_{\rho}^{\complement}\right)$. It then
follows that

$\displaystyle\Phi_{P}^{*}$ $\displaystyle\leqslant\frac{\pi\otimes
P\left(B_{\rho}\times
B_{\rho}^{\complement}\right)}{\pi\left(B_{\rho}\right)}$
$\displaystyle=\int\pi_{B_{\rho}}\left({\rm d}x\right)\cdot
P\left(x,B_{\rho}^{\complement}\right)$
$\displaystyle\leqslant\int\pi_{B_{\rho}}\left({\rm d}x\right)\cdot
P\left(x,\left\\{x\right\\}^{\complement}\right)$
$\displaystyle=\int\pi_{B_{\rho}}\left({\rm
d}x\right)\cdot\alpha\left(x\right)$
$\displaystyle\leqslant\left(1+m\cdot\sigma^{2}\right)^{-d/2}\cdot\exp\left(\frac{1}{2}\cdot\rho^{2}\right),$

and taking an infimum as $\rho\to 0^{+}$ gives that
$\Phi_{P}\leqslant\left(1+m\cdot\sigma^{2}\right)^{-d/2}$, as claimed.

For the subsequent remark, compute that

$\displaystyle\log\Phi_{P}^{*}$ $\displaystyle\leqslant-\frac{1}{2}\cdot
d\cdot\log\left(1+m\cdot\sigma^{2}\right)$ $\displaystyle=-\frac{1}{2}\cdot
d\cdot\log\left(1+\frac{m}{L}\cdot\frac{\varsigma^{2}}{d^{2\cdot\beta}}\right)$
$\displaystyle=-\frac{1}{2}\cdot
d^{1-2\cdot\beta}\cdot\left(d^{2\cdot\beta}\cdot\log\left(1+\frac{m}{L}\cdot\frac{\varsigma^{2}}{d^{2\cdot\beta}}\right)\right)$
$\displaystyle=-\frac{1}{2}\cdot
d^{1-2\cdot\beta}\cdot\left(\frac{m}{L}\cdot\varsigma^{2}+{\cal
O}\left(d^{-2\cdot\beta}\right)\right)$ $\displaystyle=-\frac{1}{2}\cdot
d^{1-2\cdot\beta}\cdot\frac{m}{L}\cdot\varsigma^{2}\cdot\left(1+{\cal
O}\left(d^{-2\cdot\beta}\right)\right)$
$\displaystyle\leqslant-\frac{1}{2}\cdot\frac{m}{L}\cdot\varsigma^{2}\cdot
d^{1-2\cdot\beta}\cdot\left(1+o\left(1\right)\right).$

Fixing $c\in\left(0,\frac{1}{2}\cdot\frac{m}{L}\cdot\varsigma^{2}\right)$, it
holds for sufficiently large $d$ that $\log\Phi_{P}^{*}\leqslant-c\cdot
d^{1-2\cdot\beta}$. ∎

####  4.2.2 Spectral gap upper bounds

A natural question is whether the lower bound for the spectral gap is of the
correct order when $\sigma\sim d^{-1/2}$, i.e. whether indeed $\gamma_{P}={\rm
Gap}_{R}\left(P\right)$ scales as $d^{-1}$. Under Assumption 31, we verify
this directly and also show that this is the optimal polynomial scaling.

######  Theorem 46.

Under Assumption 31 and twice continuous-differentiability of $U$,

$\gamma_{P}\leqslant\min\left\\{\frac{1}{2}\cdot
L\cdot\sigma^{2},\left(1+m\cdot\sigma^{2}\right)^{-d/2}\right\\}.$

Hence, among polynomial scalings of the $\sigma$, the scaling $\sigma\sim
d^{-1/2}$ is optimal with $\gamma_{P}\sim d^{-1}$.

###### Proof.

The bounds follow from Lemma 47 and Proposition 45 combined with Lemma 5. Let
$\sigma=\varsigma\cdot L^{-1/2}\cdot d^{-\beta}$. If
$\beta\geqslant\frac{1}{2}$ then we obtain
$\gamma_{P}\in\mathcal{O}\left(d^{-2\cdot\beta}\right)$ and this rate is
maximized by taking $\beta=\frac{1}{2}$. Combined with Corollary 35, we may
conclude that $\gamma_{P}$ decays as $d^{-1}$ as $d\to\infty$ when
$\beta=\frac{1}{2}$. On the other hand, if $\beta<\frac{1}{2}$ then
$\gamma_{P}\cdot d$ converges to $0$ and hence $\beta<\frac{1}{2}$ leads to a
faster decay of $\gamma_{P}$ than $\beta=\frac{1}{2}$. ∎

######  Lemma 47.

Let $U$ be $L$-smooth and twice continuously differentiable. Then

$\gamma_{P}\leqslant\frac{1}{2}\cdot L\cdot\sigma^{2}.$

###### Proof.

By the Cramér–Rao inequality (see, e.g., Saumard and Wellner, 2014, Eq.
10.25), it holds for any $v\in\mathbb{R}^{d}$ that

${\rm Var}_{\pi}\left(\left\langle v,X\right\rangle\right)\geqslant
v^{\top}\cdot{\bf\mathbb{E}}_{\pi}\left[\nabla^{2}\left(-\log\pi\left(X\right)\right)\right]^{-1}\cdot
v\geqslant L^{-1}\cdot\left|v\right|^{2},$

by $L$-smoothness. For $v\neq 0$, define $g_{v}\left(x\right):=\left\langle
v,x-{\bf\mathbb{E}}_{\pi}\left[X\right]\right\rangle$, and compute

$\displaystyle\mathcal{E}\left(P,g_{v}\right)$
$\displaystyle=\frac{1}{2}\int\pi\left({\rm d}x\right)P\left(x,{\rm
d}y\right)\left(g_{v}\left(y\right)-g_{v}\left(x\right)\right)^{2}$
$\displaystyle=\frac{1}{2}\int\pi\left({\rm d}x\right)P\left(x,{\rm
d}y\right)\left\langle v,y-x\right\rangle^{2}$
$\displaystyle\leqslant\frac{1}{2}\int\pi\left({\rm d}x\right)Q\left(x,{\rm
d}y\right)\left\langle v,y-x\right\rangle^{2}$
$\displaystyle=\frac{1}{2}\int\pi\left({\rm d}x\right){\cal N}\left({\rm
d}z;0,I_{d}\right)\left\langle v,\sigma\cdot z\right\rangle^{2}$
$\displaystyle=\frac{1}{2}\cdot\sigma^{2}\cdot\left|v\right|^{2}.$

We obtain

$\gamma_{P}={\rm Gap}_{{\rm
R}}\left(P\right)=\inf_{f\in\mathrm{L}^{2}_{0}\left(\pi\right)}\frac{{\cal
E}\left(P,f\right)}{\left\|f\right\|_{2}^{2}}\leqslant\frac{{\cal
E}\left(P,g_{v}\right)}{\left\|g_{v}\right\|_{2}^{2}}\leqslant\frac{\frac{1}{2}\cdot\sigma^{2}\cdot\left|v\right|^{2}}{L^{-1}\cdot\left|v\right|^{2}}=\frac{1}{2}\cdot
L\cdot\sigma^{2}.\qed$

###  4.3 Implications for the asymptotic variance

In this sub-section, we address the asymptotic variance of MCMC estimators
computed from RWM chains. We will show that when using appropriately-tuned RWM
chains to compute expectations of functions under $\pi$, the asymptotic
variance of these estimators is an inflation of the ideal variance by a factor
which scales linearly with the dimension of the problem. Furthermore, we will
exhibit that for a specific class of functions (in particular, affine
functions) that this bound is tight in terms of its dimension-dependence.

######  Proposition 48.

Let Assumption 31 hold, and $\sigma=\varsigma\cdot L^{-1/2}\cdot d^{-1/2}$ for
any $\varsigma>0$. Then, for any $f\in\mathrm{L}^{2}_{0}\left(\pi\right)$, the
asymptotic variance of $f$ can be bounded as

$\displaystyle{\rm var}\left(P,f\right)$ $\displaystyle\leqslant 2^{10}\cdot
C_{\gamma}^{-2}\cdot\varsigma^{-2}\cdot\exp\left(2\cdot\varsigma^{2}\right)\cdot\kappa\cdot
d\cdot\left\|f\right\|_{2}^{2}.$

Additionally, for any linear $f\in\mathrm{L}^{2}_{0}\left(\pi\right)$, it
holds that

${\rm var}\left(P,f\right)\geqslant 2\cdot\varsigma^{-2}\cdot
d\cdot\left\|f\right\|_{2}^{2}.$

###### Proof.

Since $P$ is reversible and ${\rm Gap}_{{\rm R}}\left(P\right)>0$, ${\rm
Id}-P$ is invertible on $\mathrm{L}^{2}_{0}\left(\pi\right)$. We may then
write that

$\displaystyle{\rm var}\left(P,f\right)$ $\displaystyle=\left\langle
f,\left(\mathrm{Id}+P\right)\cdot\left(\mathrm{Id}-P\right)^{-1}\cdot
f\right\rangle,$

Moreover, by considering the spectral resolution of $f$ with respect to $P$,
it is classical that

$\displaystyle\left\langle
f,\left(\mathrm{Id}+P\right)\cdot\left(\mathrm{Id}-P\right)^{-1}\cdot
f\right\rangle$ $\displaystyle\leqslant\frac{2}{{\rm
Gap}_{\mathrm{R}}\left(P\right)}\cdot\left\|f\right\|_{2}^{2},$

where ${\rm Gap}_{\mathrm{R}}\left(P\right)$ is the right spectral gap of $P$.
Recalling that ${\rm Gap}_{\mathrm{R}}\left(P\right)\geqslant\gamma_{P}$ (for
any reversible $P$), we apply Corollary 35 to bound

$\displaystyle{\rm Gap}_{\mathrm{R}}\left(P\right)$ $\displaystyle\geqslant
2^{-9}\cdot
C_{\gamma}^{2}\cdot\varsigma^{2}\cdot\exp\left(-2\cdot\varsigma^{2}\right)\cdot
d^{-1}\cdot\frac{m}{L},$

and deduce the first bound. For the second bound, by positivity of $P$ we may
write

${\rm var}\left(P,f\right)=\left\langle
f,\left(\mathrm{Id}+P\right)\cdot\left(\mathrm{Id}-P\right)^{-1}\cdot
f\right\rangle\geqslant\left\langle f,\left(\mathrm{Id}-P\right)^{-1}\cdot
f\right\rangle.$

Recall the variational representation (see, e.g., Caracciolo et al., 1990),

$\left\langle f,\left(\mathrm{Id}-P\right)^{-1}\cdot
f\right\rangle=\sup_{g\in\mathrm{L}^{2}_{0}\left(\pi\right)}\left\\{2\cdot\left\langle
f,g\right\rangle-\mathcal{E}\left(P,g\right)\right\\}.$

We will consider taking $f:x\mapsto\left\langle
v,x-\mathbb{E}_{\pi}\left[X\right]\right\rangle$, and $g=c\cdot f$ for
$c\in\mathbb{R}$. By the argument in the proof of Lemma 47, it holds that

$\left\|f\right\|_{2}^{2}\geqslant
L^{-1}\cdot\left|v\right|^{2},\qquad\mathcal{E}\left(P,f\right)\leqslant\frac{1}{2}\cdot\sigma^{2}\cdot\left|v\right|^{2}.$

We thus see that

$\displaystyle{\rm var}\left(P,f\right)$ $\displaystyle\geqslant\left\langle
f,\left(\mathrm{Id}-P\right)^{-1}\cdot f\right\rangle$
$\displaystyle=\sup_{g\in\mathrm{L}^{2}_{0}\left(\pi\right)}\left\\{2\cdot\left\langle
f,g\right\rangle-\mathcal{E}\left(P,g\right)\right\\}$
$\displaystyle\geqslant\sup_{c\in\mathbb{R}}\left\\{2\cdot
c\cdot\left\|f\right\|_{2}^{2}-c^{2}\cdot\mathcal{E}\left(P,f\right)\right\\}$
$\displaystyle=\frac{\left\|f\right\|_{2}^{2}}{\mathcal{E}\left(P,f\right)}\cdot\left\|f\right\|_{2}^{2}$
$\displaystyle\geqslant\frac{L^{-1}\cdot\left|v\right|^{2}}{\frac{1}{2}\cdot\sigma^{2}\cdot\left|v\right|^{2}}\cdot\left\|f\right\|_{2}^{2}$
$\displaystyle=2\cdot\varsigma^{-2}\cdot d\cdot\left\|f\right\|_{2}^{2}.\qed$

###  4.4 Discussion of the assumptions

Under Assumption 31, Corollary 35 provides explicit bounds on the spectral gap
of the RWM kernel for any $\sigma>0$. Theorem 46 further shows that the
optimal dependence on dimension is $d^{-1}$ for this class of target measures.
On the other hand, it is clear from the proof that the lower bounds on the
spectral gap and conductance profile have $m$-strong convexity and
$L$-smoothness of $U$ as sufficient but not necessary conditions.

For showing lower bounds, $m$-strong convexity of the potential is only used
to verify an appropriate isoperimetric profile inequality. Hence, any other
method for establishing such inequalities could be used instead. For instance,
one may follow Example 23 to deduce an isoperimetric profile inequality for
any log-concave probability measure; an explicit constant could be obtained by
study of the corresponding overdamped Langevin diffusion. Example 28 could
also be used to extend this reasoning to perturbations of log-concave
probability measures. Similarly, for showing lower bounds, $L$-smoothness is
only assumed to establish that the acceptance probability is uniformly lower
bounded above $0$, i.e.
$\alpha_{0}=\inf_{x\in\mathsf{E}}\alpha\left(x\right)>0$; our Lemma 39 shows
that this is possible under far less restrictive smoothness conditions on $U$,
covering both light-tailed targets and potentials whose gradients are only,
e.g., Hölder-continuous. As such, $L$-smoothness should not be viewed as
strictly necessary for the RWM to be performant; this stands in contrast to
various gradient-based MCMC algorithms, whose performance can deteriorate in
the absence of $L$-smoothness (see, e.g., Livingstone and Zanella, 2022).

On the other hand, if $U$ has particularly poor regularity (e.g. non-uniformly
continuous gradients), then it can be necessary to scale $\sigma$ differently
in order to stabilize the acceptance probability away from $0$. For a concrete
example, consider the target with potential given by
$U\left(x\right)=\left|x\right|_{p}^{p}$ for $p\in[1,2)$. Observing that
$U\left(\sigma\cdot
z\right)-U\left(0\right)=\sigma^{p}\cdot\left(\sum_{i=1}^{d}\left|z_{i}\right|^{p}\right)$,
one sees that unless $\sigma^{p}\in\mathcal{O}\left(d^{-1}\right)$, then
$\alpha\left(0\right)$ will tend to $0$ as $d\to\infty$. Similar cautionary
examples which necessitate anomalous scalings of $\sigma$ can be constructed
by designing potentials with ‘sharp’ growth around a local minimum, and
following the strategy of Proposition 45.

##  5 Convergence and mixing time for RWM

In this section, we analyze the mixing time for the RWM kernel $P$ defined in
Section 4 under Assumption 31.

###  5.1 Three phase mixing

The mixing time bound essentially consists of up to three phases. If the
initial chi-squared divergence is very large, then there is an initial phase
during which the convergence takes place at an exponential rate depending only
on $\alpha_{0}$ (and in particular, not directly on $\sigma^{2}$).
Subsequently, there is a secondary phase during which convergence takes place
at a faster-than-exponential rate, depending now on both $\sigma^{2}$ and
$\alpha_{0}$. Finally, once the chi-squared divergence drops below a universal
constant (e.g. $8$), the convergence is again exponential, again with a rate
depending on both $\sigma^{2}$ and $\alpha_{0}$. Qualitatively similar
behaviour was also observed (for a different algorithm) in the work of Mou et
al. (2022). We provide three different bounds, valid for any $\varsigma>0$,
which are successively weaker. In particular, the third bound may be
conservative when $u_{0}\leqslant 4\cdot v_{\circ}^{-1}$, since in that case
the first phase is non-existent and the second phase is bounded fairly
crudely.

######  Theorem 49.

Under Assumption 31, let $\mu\ll\pi$ be a probability measure and
$u_{0}=\chi^{2}\left(\mu,\pi\right)$. Let $\sigma=\varsigma\cdot L^{-1/2}\cdot
d^{-1/2}$ and $\kappa=L/m$, with $\varsigma>0$ arbitrary and let the universal
constants $C_{\ell},C_{\gamma}$ be as defined in Lemma 27.

Then, to guarantee that $\chi^{2}\left(\mu
P^{n},\pi\right)\leqslant\varepsilon_{{\rm Mix}}\in\left(0,8\right)$:

  1. 1.

We may take

$\displaystyle n$ $\displaystyle\geqslant
2+2^{8}\cdot\alpha_{0}^{-2}\cdot\max\left\\{\log\left(\frac{u_{0}}{4\cdot
v_{\circ}^{-1}}\right),0\right\\}$ $\displaystyle+2^{10}\cdot
C_{\ell}^{-2}\cdot\alpha_{0}^{-4}\cdot\sigma^{-2}\cdot
m^{-1}\cdot\log\left(\frac{\log\left(\min\left\\{\max\left\\{\frac{1}{2}\cdot
u_{0},4\right\\},2\cdot v_{\circ}^{-1}\right\\}\right)}{\log 4}\right)$
$\displaystyle+2^{4}\cdot\max\left\\{1,2^{-2}\cdot
C_{\gamma}^{-2}\cdot\alpha_{0}^{-2}\cdot\sigma^{-2}\cdot
m^{-1}\right\\}\cdot\alpha_{0}^{-2}\cdot\log\left(\max\left\\{\frac{\min\left\\{u_{0},8\right\\}}{\varepsilon_{{\rm
Mix}}},1\right\\}\right),$

where $v_{\circ}:=\min\left\\{\frac{1}{2},2\cdot\exp\left(-4\cdot
C_{\ell}^{-2}\cdot\sigma^{-2}\cdot\alpha_{0}^{-2}\cdot
m^{-1}\right)\right\\}$.

  2. 2.

We may take

$\displaystyle n$ $\displaystyle\geqslant
2+2^{10}\cdot\exp\left(\varsigma^{2}\right)\cdot\max\left\\{\log\left(\frac{u_{0}}{4\cdot
v_{\circ}^{-1}}\right),0\right\\}$ $\displaystyle+2^{14}\cdot
C_{\ell}^{-2}\cdot\exp\left(2\cdot\varsigma^{2}\right)\cdot\varsigma^{-2}\cdot\kappa\cdot
d\cdot\log\left(\frac{\log\left(\min\left\\{\max\left\\{\frac{1}{2}\cdot
u_{0},4\right\\},2\cdot v_{\circ}^{-1}\right\\}\right)}{\log 4}\right)$
$\displaystyle+2^{6}\cdot
C_{\gamma}^{-2}\cdot\exp\left(2\cdot\varsigma^{2}\right)\cdot\varsigma^{-2}\cdot\kappa\cdot
d\cdot\log\left(\max\left\\{\frac{\min\left\\{u_{0},8\right\\}}{\varepsilon_{{\rm
Mix}}},1\right\\}\right),$

and $v_{\circ}^{-1}\leqslant\frac{1}{2}\cdot\exp\left(16\cdot
C_{\ell}^{-2}\cdot\exp\left(\varsigma^{2}\right)\cdot\varsigma^{-2}\cdot\kappa\cdot
d\right)$.

  3. 3.

We may take

$\displaystyle n$ $\displaystyle\geqslant
2+2^{10}\cdot\exp\left(\varsigma^{2}\right)\cdot\log\left(\max\left\\{u_{0},1\right\\}\right)$
$\displaystyle+2^{14}\cdot
C_{\ell}^{-2}\cdot\exp\left(2\cdot\varsigma^{2}\right)\cdot\varsigma^{-2}\cdot\kappa\cdot
d\cdot\left\\{\log\left(16\cdot
C_{\ell}^{-2}\varsigma^{-2}\right)+\log\left(\kappa\cdot
d\right)+\varsigma^{2}\right\\}$ $\displaystyle+2^{6}\cdot
C_{\gamma}^{-2}\cdot\exp\left(2\cdot\varsigma^{2}\right)\cdot\varsigma^{-2}\cdot\kappa\cdot
d\cdot\log\left(\frac{8}{\varepsilon_{{\rm Mix}}}\right),$

i.e., $n$ can be taken of order $\mathcal{O}\left(\log u_{0}+\kappa\cdot
d\cdot\log\left(\kappa\cdot d\right)+\kappa\cdot
d\cdot\log\left(\varepsilon_{{\rm Mix}}^{-1}\right)\right)$.

###### Proof.

From Lemma 27, we can write
$I_{\pi}\left(p\right)\geqslant\tilde{I}_{\pi}\left(p\right):=m^{1/2}\cdot\left(\varphi_{\gamma}\circ\Phi_{\gamma}^{-1}\right)\left(p\right)$,
which admits the bounds

$\tilde{I}_{\pi}\left(p\right)\geqslant C_{\ell}\cdot m^{1/2}\cdot
p\cdot\left(\log\frac{1}{p}\right)^{1/2}\qquad p\in\big{(}0,1/2\big{]},$

and $\tilde{I}_{\pi}\left(\frac{1}{4}\right)=m^{1/2}\cdot C_{{\rm\gamma}}$.
From Theorem 18,

$\displaystyle n$ $\displaystyle\geqslant
2+2^{6}\cdot\varepsilon^{-2}\cdot\max\left\\{\log\left(\frac{u_{0}}{4\cdot
v_{*}^{-1}}\right),0\right\\}$
$\displaystyle+2^{8}\cdot\varepsilon^{-2}\cdot\delta^{-2}\cdot\int_{\max\left\\{\min\left\\{2\cdot
u_{0}^{-1},1/4\right\\},v_{*}/2\right\\}}^{1/4}\frac{\xi}{\tilde{I}_{\pi}\left(\xi\right)^{2}}\,{\rm
d}\xi$
$\displaystyle+2^{4}\cdot\max\left\\{1,2^{-2}\cdot\delta^{-2}\cdot\tilde{I}_{\pi}\left(\frac{1}{4}\right)^{-2}\right\\}\cdot\varepsilon^{-2}\cdot\log\left(\max\left\\{\frac{\min\left\\{u_{0},8\right\\}}{\varepsilon_{{\rm
Mix}}},1\right\\}\right)$

is sufficient, where $v_{*}$ is defined in (6). Additionally, from Lemma 38,
$P$ is
$\left(\left|\cdot\right|,\alpha_{0}\cdot\sigma,\frac{1}{2}\cdot\alpha_{0}\right)$-close
coupling. Substituting these values and using the lower bound on
$\tilde{I}_{\pi}\left(p\right)$ to upper bound the integrand and lower bound
$v_{*}\geqslant v_{\circ}$ it suffices to take

$\displaystyle n$ $\displaystyle\geqslant
2+2^{8}\cdot\alpha_{0}^{-2}\cdot\max\left\\{\log\left(\frac{u_{0}}{4\cdot
v_{\circ}^{-1}}\right),0\right\\}$ $\displaystyle+2^{10}\cdot
C_{\ell}^{-2}\cdot\alpha_{0}^{-4}\cdot\sigma^{-2}\cdot
m^{-1}\cdot\int_{\max\left\\{\min\left\\{2\cdot
u_{0}^{-1},1/4\right\\},v_{\circ}/2\right\\}}^{1/4}\frac{1}{\xi\cdot\log\left(\frac{1}{\xi}\right)}\,{\rm
d}\xi$ $\displaystyle+2^{4}\cdot\max\left\\{1,2^{-2}\cdot
C_{\gamma}^{-2}\cdot\alpha_{0}^{-2}\cdot\sigma^{-2}\cdot
m^{-1}\right\\}\cdot\alpha_{0}^{-2}\cdot\sigma^{-2}\cdot\log\left(\max\left\\{\frac{\min\left\\{u_{0},8\right\\}}{\varepsilon_{{\rm
Mix}}},1\right\\}\right),$

and computing that

$0<a<b<1\implies\quad\int_{a}^{b}\frac{1}{\xi\cdot\log\left(\frac{1}{\xi}\right)}\,{\rm
d}\xi=\log\left(\frac{\log\left(1/a\right)}{\log\left(1/b\right)}\right)$

provides the first bound.

By Corollary 40 and
$\exp\left(\varsigma^{2}\right)\cdot\varsigma^{-2}\geqslant\exp\left(1\right)$,
we obtain

$\displaystyle\max\left\\{1,2^{-2}\cdot
C_{\gamma}^{-2}\cdot\alpha_{0}^{-2}\cdot\sigma^{-2}\cdot m^{-1}\right\\}$
$\displaystyle\leqslant\max\left\\{1,C_{\gamma}^{-2}\cdot\exp\left(\varsigma^{2}\right)\cdot\varsigma^{-2}\cdot\kappa\cdot
d\right\\}$
$\displaystyle=C_{\gamma}^{-2}\cdot\exp\left(\varsigma^{2}\right)\cdot\varsigma^{-2}\cdot\kappa\cdot
d,$

and simplifying the other terms provides the second bound. Similarly, we have

$\displaystyle v_{\circ}^{-1}$
$\displaystyle=\max\left\\{2,\frac{1}{2}\exp\left(4\cdot
C_{\ell}^{-2}\cdot\sigma^{-2}\cdot\alpha_{0}^{-2}\cdot m^{-1}\right)\right\\}$
$\displaystyle\leqslant\max\left\\{2,\frac{1}{2}\cdot\exp\left(16\cdot
C_{\ell}^{-2}\cdot\exp\left(\varsigma^{2}\right)\cdot\varsigma^{-2}\cdot\kappa\cdot
d\right)\right\\}$ $\displaystyle\leqslant\frac{1}{2}\cdot\exp\left(16\cdot
C_{\ell}^{-2}\cdot\exp\left(\varsigma^{2}\right)\cdot\varsigma^{-2}\cdot\kappa\cdot
d\right).$

The final bound is obtained by the following observations. Since
$v_{\circ}^{-1}\geqslant 2$, we have $\frac{u_{0}}{4\cdot
v_{\circ}^{-1}}\leqslant u_{0}$, leading to the bound on the first term. The
second term follows from

$\displaystyle\log\left(\frac{\log\left(\min\left\\{\max\left\\{\frac{1}{2}\cdot
u_{0},4\right\\},2\cdot v_{\circ}^{-1}\right\\}\right)}{\log 4}\right)$
$\displaystyle\leqslant\log\left(\frac{\log\left(2\cdot
v_{\circ}^{-1}\right)}{\log 4}\right)$
$\displaystyle\leqslant\log\left(\log\left(2\cdot
v_{\circ}^{-1}\right)\right)$ $\displaystyle\leqslant\log\left(16\cdot
C_{\ell}^{-2}\cdot\varsigma^{-2}\cdot\kappa\cdot d\right)+\varsigma^{2},$

where we have used the bound on $v_{\circ}^{-1}$ to arrive at the final
inequality. ∎

###  5.2 Two feasible “warm starts”

We provide two complexity bounds based on Theorem 49, corresponding to two
different algorithmically feasible initial distributions $\mu$. In Remark 50,
we consider a Gaussian initial distribution centered at the mode of the
density $\pi$ with covariance $L^{-1}\cdot I_{d}$; when $U$ is convex,
identifying the mode numerically is feasible and hence the strategy relies on
explicit knowledge of $L$. In Remark 51 we consider the approach suggested by
Belloni and Chernozhukov (2009), for which the initial distribution is given
by the distribution of the first ‘accepted’ proposal from
$Q\left(x_{0},\cdot\right)$ where $x_{0}$ is arbitrary. This does not require
explicit knowledge of $L$, only e.g. a bound that allows one to tune $\sigma$
such that $\varsigma\in\Theta\left(1\right)$, and corresponds directly to how
RWM chains are often initialized in practice. In particular, we observe that
the RWM mixing time is fairly robust to the choice of initial point $x_{0}$ as
long as it is not very far from the mode, and this is due to the fast phases
of convergence identified in Theorem 49.

######  Remark 50.

If $\mu=\mathcal{N}\left(x_{*},L^{-1}\cdot I_{d}\right)$, with $x_{*}$ the
mode of $\pi$, then by Lemma 42 we may obtain the bound
$u_{0}=\chi^{2}\left(\mu,\pi\right)\leqslant\kappa^{d/2}$. It then holds that
$\log u_{0}=\mathcal{O}\left(d\cdot\log\kappa\right)$, and one obtains a
mixing time bound which scales as $\mathcal{O}\left(\kappa\cdot
d\cdot\log\left(\kappa\cdot d\right)+\kappa\cdot
d\cdot\log\left(\varepsilon_{{\rm Mix}}^{-1}\right)\right)$. In relation to
the comments preceding Theorem 49, we note that by taking $\varsigma$
sufficiently small, one may ensure $u_{0}\leqslant 4\cdot v_{\circ}^{-1}$ and
thereby reduce the complexity to $\mathcal{O}\left(\kappa\cdot
d\cdot\log\left(d\cdot\log\kappa\right)+\kappa\cdot
d\cdot\log\left(\varepsilon_{{\rm Mix}}^{-1}\right)\right)$.

######  Remark 51.

There is another approach to obtaining a warm start which neatly sidesteps the
need for any preliminary optimization, suggested by Belloni and Chernozhukov
(2009). The idea is to initialize the chain by a single accepted move of the
Metropolis kernel from some arbitrary point $x_{0}$, i.e.

$\displaystyle\mu\left(\mathrm{d}x\right)$
$\displaystyle=P^{\alpha}\left(x_{0},\mathrm{d}x\right)$
$\displaystyle:=Q\left(x_{0},\mathrm{d}x\right)\cdot\alpha\left(x_{0},x\right)\cdot\alpha\left(x_{0}\right)^{-1}.$

To this end, one can compute directly (in fact, for any Metropolis–Hastings
chain) that

$\displaystyle\pi\left(\mathrm{d}x\right)\cdot
P^{\alpha}\left(x,\mathrm{d}y\right)$
$\displaystyle=\pi\left(\mathrm{d}x\right)\cdot
Q\left(x,\mathrm{d}y\right)\cdot\alpha\left(x,y\right)\cdot\alpha\left(x\right)^{-1}$
$\displaystyle=\pi\left(\mathrm{d}y\right)\cdot
Q\left(y,\mathrm{d}x\right)\cdot\alpha\left(y,x\right)\cdot\alpha\left(x\right)^{-1}.$

Disintegrating this joint measure appropriately, one sees for the RWM that

$\displaystyle\frac{\mathrm{d}P^{\alpha}\left(x_{0},\cdot\right)}{\mathrm{d}\pi}\left(x\right)$
$\displaystyle=\alpha\left(x,x_{0}\right)\cdot\alpha\left(x_{0}\right)^{-1}\cdot\frac{\mathrm{d}Q\left(x,\cdot\right)}{\mathrm{d}\pi}\left(x_{0}\right)$
$\displaystyle\leqslant
1\cdot\alpha_{0}^{-1}\cdot\left(\sup_{y\in\mathsf{E}}\frac{\mathrm{d}Q\left(x,\cdot\right)}{\mathrm{d}{\rm
Leb}}\left(y\right)\right)\cdot\left(\frac{\mathrm{d}\pi}{\mathrm{d}{\rm
Leb}}\left(x_{0}\right)\right)^{-1}.$

Computing that $\alpha_{0}^{-1}\leqslant
2\cdot\exp\left(\frac{1}{2}\cdot\varsigma^{2}\right)$,
$\sup_{y\in\mathsf{E}}\frac{\mathrm{d}Q\left(x,\cdot\right)}{\mathrm{d}{\rm
Leb}}\left(y\right)=\left(2\cdot\pi\cdot\sigma^{2}\right)^{-d/2}$,
$\left(\frac{\mathrm{d}\pi}{\mathrm{d}{\rm
Leb}}\left(x_{0}\right)\right)^{-1}\leqslant\kappa^{d/2}\cdot\left(2\cdot\pi\cdot
L^{-1}\right)^{d/2}\cdot\exp\left(\frac{1}{2}\cdot
L\cdot\left|x_{0}-x_{*}\right|^{2}\right)$, one obtains that

$\displaystyle\sup_{x\in\mathsf{E}}\frac{\mathrm{d}P^{\alpha}\left(x_{0},\cdot\right)}{\mathrm{d}\pi}\left(x\right)$
$\displaystyle\leqslant
2\cdot\exp\left(\frac{1}{2}\cdot\varsigma^{2}\right)\cdot\left(\frac{\kappa\cdot
d}{\varsigma^{2}}\right)^{d/2}\cdot\exp\left(\frac{1}{2}\cdot
L\cdot\left|x_{0}-x_{*}\right|^{2}\right)$
$\displaystyle\in\exp\left(\mathcal{O}\left(d\cdot\log\left(d\cdot\kappa\right)+L\cdot\left|x_{0}-x_{*}\right|^{2}\right)\right),$

when $\varsigma$ is of order $1$. As such, provided that
$L\cdot\left|x_{0}-x_{*}\right|^{2}\in\mathcal{O}\left(\kappa\cdot
d\cdot\log\left(\kappa\cdot d\right)\right)$, it holds that $\log
u_{0}\in\mathcal{O}\left(\kappa\cdot d\cdot\log\left(\kappa\cdot
d\right)\right)$, and one obtains a mixing time bound which again scales as
$\mathcal{O}\left(\kappa\cdot d\cdot\log\left(\kappa\cdot d\right)+\kappa\cdot
d\cdot\log\left(\varepsilon_{{\rm Mix}}^{-1}\right)\right)$. From the
perspective of complexity analysis, it is thus essentially sufficient to
initialize the chain by identifying some point within a reasonable distance,
i.e. $\mathcal{O}\left(\left(\frac{d}{m}\cdot\log\left(\kappa\cdot
d\right)\right)^{1/2}\right)$ of the mode, and waiting until a single proposed
move is accepted.

###  5.3 Comparisons to existing results

The prior work of Belloni and Chernozhukov (2009) is closely related; the
authors study the application of MCMC techniques to frequentist estimation
tasks for which direct optimization of the objective function is challenging.
For their application, a different isoperimetric inequality is used, which
allows them to handle potentials which are non-convex, non-smooth, or even
both. However they assume that their target distributions are supported on a
(large) closed ball. Their complexity bounds are essentially obtained by
estimating the spectral gap, and constructing an appropriate ‘warm start’,
i.e. an initial distribution $\mu$ which satisfies $\frac{{\rm d}\mu}{{\rm
d}\pi}\leqslant W<\infty$, which implies a bound on the initial
$\mathrm{L}^{2}$ distance to equilibrium, recalled in Remark 51. Their result
holds for a particular choice of $\sigma^{2}$, which depends on theoretical
quantities that are typically unknown. In contrast, our bounds are valid for
any $\sigma^{2}$. Their conductance bound is of the form
$\Phi_{P}^{*}\in\Omega\left(d^{-1}\right)$, as opposed to the
$\Phi_{P}^{*}\in\Omega\left(d^{-1/2}\right)$ that we find. This may appear
suboptimal, but it may also be the case that their class of target
distributions is sufficiently harder than those which we consider, to the
point that the conductance is genuinely worse in this way.

Closest to our work are the twin papers Dwivedi et al. (2019) and Chen et al.
(2020), which give complexity bounds for the RWM under Assumption 31. Under a
‘feasible’ Gaussian initial law (roughly as in Remark 50), Dwivedi et al.
(2019) obtain complexity bounds of
$\mathcal{O}\left(d^{2}\cdot\kappa^{2}\cdot\log^{1.5}\left(\kappa\cdot\varepsilon_{{\rm
Mix}}^{-1}\right)\right)$ which Chen et al. (2020) refined to
$\mathcal{O}\left(d\cdot\kappa^{2}\cdot\log\left(d\cdot\varepsilon_{{\rm
Mix}}^{-1}\right)\right)$ by making use of the conductance profile framework;
we observe that our complexity analysis implies a weaker dependence on
$\kappa$. Their results also assume precise values of $\sigma^{2}$ that are
typically unknown in practical applications, in contrast with ours.

##  6 Convergence and mixing time for pCN

In this section, we apply the same technique to analyze the convergence to
equilibrium of the preconditioned Crank–Nicolson algorithm. We consider the
following class of distributions, consistent with both Assumptions 9 and 31:

######  Assumption 52.

The target measure $\pi$ on $\mathsf{E}=\mathbb{R}^{d}$ can be written

$\pi\left({\rm d}x\right)\propto\mathcal{N}\left({\rm
d}x;0,\mathsf{C}\right)\cdot\exp\left(-\Psi\left(x\right)\right),$

where $\Psi$ is convex, $L$-smooth, and minimized at $x=0$, and $\mathsf{C}$
is a positive definite covariance matrix.

Letting $\nu=\mathcal{N}\left(0,\mathsf{C}\right)$, throughout this section we
denote by $P$ the pCN kernel defined by (1), with $Q$ the $\nu$-reversible
Gaussian kernel defined for a fixed but arbitrary $\rho\in(0,1)$ by

$Q\left(x,A\right)=\int\mathbf{1}_{A}\left(\rho\cdot x+\eta\cdot
z\right)\,\mathcal{N}\left(\mathrm{d}z;0,\mathsf{C}\right),\qquad
x\in\mathsf{E},A\in\mathscr{E},$

where $\rho^{2}+\eta^{2}=1$. We will refer to $\eta$ as the step-size of this
kernel, and denote $\alpha_{0}:=\inf_{x\in\mathsf{E}}\alpha\left(x\right)$. In
particular, we have that $\varpi\propto\exp\left(-\Psi\right)$ is the density
of $\pi$ w.r.t. the reference measure $\nu$. By Doucet et al. (2015,
Proposition 3(i)), we may deduce that $P$ is positive, taking in their
notation $\chi=\nu$ and $r\left(u,v\right)=\mathcal{N}\left(u;\rho^{1/2}\cdot
v,\left(1-\rho\right)\cdot\mathsf{C}\right)$.

The pCN algorithm is particularly popular in Bayesian Inverse Problems (see,
e.g., Stuart, 2010, Example 5.3), where $\mathsf{C}$ is typically a finite