$\displaystyle\quad+s^{2}(k-2)\iint\left(9L^{\frac{3}{2}}\left\|\nabla
f(x)\right\|_{2}^{2}+11L^{\frac{5}{2}}\left\|\frac{y-x}{s}\right\|_{2}^{2}\right)\left|D^{k-3}_{s}\left(x,\frac{y-x}{s}\right)\right|\cdot
e^{-f(x)}\frac{e^{-\frac{\left\|y-x\right\|_{2}^{2}}{2s^{2}}}}{\sqrt{(2\Pi
s^{2})^{d}}}dydx.$

Similarly, for $T_{4}$, using integration by parts with respect to $x$, we
have

$\displaystyle\quad\iint\nabla
f(x)^{\top}\left(\mathbb{I}_{d}-\frac{s^{2}}{2}H_{y}\right)H_{y-\frac{s^{2}}{2}\nabla
f(y)}(y-x)D^{k-2}_{s}\left(x,\frac{y-x}{s}\right)\cdot
e^{-f(x)}\frac{e^{-\frac{\left\|y-x\right\|_{2}^{2}}{2s^{2}}}}{\sqrt{(2\Pi
s^{2})^{d}}}dydx$
$\displaystyle\overset{(ii)}{=}s^{2}\iint\operatorname{trace}\left(\left(H_{x}-\nabla
f(x)\nabla
f(x)^{\top}\right)\left(\mathbb{I}_{d}-\frac{s^{2}}{2}H_{y}\right)H_{y-\frac{s^{2}}{2}\nabla
f(y)}\right)$ $\displaystyle\hskip 180.0003pt\cdot
D^{k-2}_{s}\left(x,\frac{y-x}{s}\right)\cdot
e^{-f(x)}\frac{e^{-\frac{\left\|y-x\right\|_{2}^{2}}{2s^{2}}}}{\sqrt{(2\Pi
s^{2})^{d}}}dydx$ $\displaystyle\quad+s^{2}(k-2)\iint\nabla
f(x)^{\top}\left(\mathbb{I}_{d}-\frac{s^{2}}{2}H_{y}\right)H_{y-\frac{s^{2}}{2}\nabla
f(y)}\frac{\partial D_{s}(x,\frac{y-x}{s})}{\partial x}$ $\displaystyle\hskip
180.0003pt\cdot D^{k-3}_{s}\left(x,\frac{y-x}{s}\right)\cdot
e^{-f(x)}\frac{e^{-\frac{\left\|y-x\right\|_{2}^{2}}{2s^{2}}}}{\sqrt{(2\Pi
s^{2})^{d}}}dydx$

Hence, using the derivative bound (A.5.2), we have

$\displaystyle\quad\left|\iint
T_{4}D^{k-2}_{s}\left(x,\frac{y-x}{s}\right)\cdot
e^{-f(x)}\frac{e^{-\frac{\left\|y-x\right\|_{2}^{2}}{2s^{2}}}}{\sqrt{(2\Pi
s^{2})^{d}}}dydx\right|$ $\displaystyle\leq
2s^{2}L^{2}d\iint\left|D^{k-2}_{s}\left(x,\frac{y-x}{s}\right)\right|\cdot
e^{-f(x)}\frac{e^{-\frac{\left\|y-x\right\|_{2}^{2}}{2s^{2}}}}{\sqrt{(2\Pi
s^{2})^{d}}}dydx$ $\displaystyle\quad+s^{2}\iint L\left\|\nabla
f(x)\right\|_{2}^{2}\left|D^{k-2}_{s}\left(x,\frac{y-x}{s}\right)\right|\cdot
e^{-f(x)}\frac{e^{-\frac{\left\|y-x\right\|_{2}^{2}}{2s^{2}}}}{\sqrt{(2\Pi
s^{2})^{d}}}dydx$
$\displaystyle\quad+s^{2}(k-2)\iint\left(6L^{\frac{3}{2}}\left\|\nabla
f(x)\right\|_{2}^{2}+3L^{\frac{5}{2}}\left\|\frac{y-x}{s}\right\|_{2}^{2}\right)\left|D^{k-3}_{s}\left(x,\frac{y-x}{s}\right)\right|\cdot
e^{-f(x)}\frac{e^{-\frac{\left\|y-x\right\|_{2}^{2}}{2s^{2}}}}{\sqrt{(2\Pi
s^{2})^{d}}}dydx.$

Finally, combining the $T_{1},T_{2},T_{3},T_{4}$ bounds into Equation (A.5.2)
and then Equation (A.5.2), we obtain

$\displaystyle\quad\left|{\mathbb{E}}_{q_{0}\sim\pi}{\mathbb{E}}_{p_{0}\sim\mathcal{N}(0,\mathbb{I}_{d})}D^{k}_{s}(q_{0},p_{0})\right|$
$\displaystyle\leq(k-1){\mathbb{E}}_{q_{0}\sim\pi,p_{0}\sim\mathcal{N}(0,\mathbb{I}_{d})}\left[\left(4s^{2}L^{2}d+12s^{2}L^{2}\left\|p_{0}\right\|_{2}^{2}+7s^{2}L\left\|\nabla
f(q_{0})\right\|_{2}^{2}\right)\left|D_{s}^{k-2}(q_{0},p_{0})\right|\right]$
$\displaystyle\quad+(k-1)(k-2){\mathbb{E}}_{q_{0}\sim\pi,p_{0}\sim\mathcal{N}(0,\mathbb{I}_{d})}\left[\left(14s^{2}L^{\frac{5}{2}}\left\|p_{0}\right\|_{2}^{2}+15s^{2}L^{\frac{3}{2}}\left\|\nabla
f(q_{0})\right\|_{2}^{2}\right)\left|D_{s}^{k-3}(q_{0},p_{0})\right|\right].$

For $k\geq 4$ an even positive integer, applying Hölder’s inequality, we
relate $D_{s}^{k-2}$ and $D_{s}^{k-3}$ with $D_{s}^{k}$. We have

$\displaystyle\quad{\mathbb{E}}_{q_{0}\sim\pi,p_{0}\sim\mathcal{N}(0,\mathbb{I}_{d})}D^{k}_{s}(q_{0},p_{0})$
$\displaystyle\leq
ks^{2}L\left(4Ld+12L\left({\mathbb{E}}_{p_{0}\sim\mathcal{N}(0,\mathbb{I}_{d})}\left\|p_{0}\right\|_{2}^{k}\right)^{2/k}+7\left({\mathbb{E}}_{q_{0}\sim\pi}\left\|\nabla
f(q_{0})\right\|_{2}^{k}\right)^{2/k}\right)$ $\displaystyle\hskip
170.00026pt\cdot\left({\mathbb{E}}_{q_{0}\sim\pi,p_{0}\sim\mathcal{N}(0,\mathbb{I}_{d})}D^{k}_{s}(q_{0},p_{0})\right)^{\frac{k-2}{k}}$
$\displaystyle\quad+k^{2}s^{2}L^{\frac{3}{2}}\left(14L\left({\mathbb{E}}_{p_{0}\sim\mathcal{N}(0,\mathbb{I}_{d})}\left\|p_{0}\right\|_{2}^{k}\right)^{2/k}+15\left({\mathbb{E}}_{q_{0}\sim\pi}\left\|\nabla
f(q_{0})\right\|_{2}^{k}\right)^{2/k}\right)$ $\displaystyle\hskip
170.00026pt\cdot\left({\mathbb{E}}_{q_{0}\sim\pi,p_{0}\sim\mathcal{N}(0,\mathbb{I}_{d})}D^{k}_{s}(q_{0},p_{0})\right)^{\frac{k-3}{k}}.$

Hence

$\displaystyle\quad{\mathbb{E}}_{q_{0}\sim\pi,p_{0}\sim\mathcal{N}(0,\mathbb{I}_{d})}L^{-\frac{k}{2}}D^{k}_{s}(q_{0},p_{0})$
$\displaystyle\leq\max\left\\{1,60(3k)^{k}s^{k}\max\left\\{L^{\frac{k}{2}}d^{\frac{k}{2}},L^{\frac{k}{2}}{\mathbb{E}}_{p_{0}\sim\mathcal{N}(0,\mathbb{I}_{d})}\left\|p_{0}\right\|_{2}^{k},{\mathbb{E}}_{q_{0}\sim\pi}\left\|\nabla
f(q_{0})\right\|_{2}^{k}\right\\}\right\\}.$

##  B Lemmas related to the lower bound

We provide the proof of Lemma 14 and Lemma 15 in Appendix B.1 and B.2.

###  B.1 Proof of Lemma 14

Define the event

$\displaystyle F_{1}:=\Bigg{\\{}x\in{}^{d}\bigg{|}$
$\displaystyle\max_{i\in[d]}\sqrt{L}\left|x_{[i]}\right|<4\sqrt{\log(8d)},$
$\displaystyle L\left\|x\right\|_{2}^{2}<d+d^{1-4\zeta}+5\sqrt{d},$
$\displaystyle\sum_{i=1}^{d}-\cos(d^{\zeta}L^{\frac{1}{2}}x_{[i]})<-\frac{1}{4}d^{1-2\zeta}+\frac{1}{2}d^{1-4\zeta}+2d^{\frac{1}{2}},$
$\displaystyle\left|\sum_{i=1}^{d}-\cos(2d^{\zeta}L^{\frac{1}{2}}x_{[i]})+\frac{1}{16}d^{1-2\zeta}\right|\leq\frac{1}{8}d^{1-4\zeta}+2d^{\frac{1}{2}},$
$\displaystyle\left|\sum_{i=1}^{d}L^{\frac{1}{2}}x_{[i]}\sin(d^{\zeta}L^{\frac{1}{2}}x_{[i]})\right|<\frac{1}{2}d^{1-4\zeta}+2d^{\frac{1}{2}}\Bigg{\\}}$
(75)

Bounding the measure of $F_{1}$ under $\pi_{1}$ requires concentration
inequalities for $\pi_{1}$. Its proof is deferred to Lemma 23, where we proved
$\pi_{1}(F_{1})>1/6$.

Let $\zeta=1/4-\theta$. For any $x\in{}^{d}$, denote the negative log density
by
$f(x)=\frac{L}{2}\sum_{i=1}^{d}x_{[i]}^{2}-\frac{1}{2d^{2\zeta}}\sum_{i=1}^{d}\cos(d^{\zeta}L^{\frac{1}{2}}x_{[i]})$
and its cosine part by
$f_{P}(x)=-\frac{1}{2d^{2\zeta}}\sum_{i=1}^{d}\cos(d^{\zeta}L^{\frac{1}{2}}x_{[i]})$.
The gradient of $f$ at $x$ is

$\displaystyle\nabla f(x)$ $\displaystyle=Lx+\nabla
f_{P}(x)=Lx+\frac{L^{\frac{1}{2}}}{2d^{\zeta}}\begin{bmatrix}\sin(d^{\zeta}L^{\frac{1}{2}}x_{[1]})\\\
\vdots\\\ \sin(d^{\zeta}L^{\frac{1}{2}}x_{[d]})\end{bmatrix}.$

For any $x\in F_{1}$ and $y\in{}^{d}$, we can express the quantity of interest
as follows

$\displaystyle\quad\frac{\pi_{1}(y)Q_{1}(y,x)}{\pi_{1}(x)Q_{1}(x,y)}$
$\displaystyle=\exp\left[f(x)-f(y)-\frac{1}{4h}\left\|x-y+h\nabla
f(y)\right\|_{2}^{2}+\frac{1}{4h}\left\|y-x+h\nabla
f(x)\right\|_{2}^{2}\right].$

Define $g:=y-x+h\nabla f(x)$. We further decompose the quantity of interest by
isolating the linear, quadratic terms on $g$ and the cosine part $f_{P}$. We
have

$\displaystyle\quad f(x)-f(y)$
$\displaystyle=\frac{L}{2}\left(\left\|x\right\|_{2}^{2}-\left\|y\right\|_{2}^{2}\right)+f_{P}(x)-f_{P}(y)$
$\displaystyle=\frac{L}{2}\left(\left\|x\right\|_{2}^{2}-\left\|x-h\nabla
f(x)+g\right\|_{2}^{2}\right)+f_{P}(x)-f_{P}(y)$
$\displaystyle=-\frac{L}{2}\left(\left(-2Lh+L^{2}h^{2}\right)\left\|x\right\|_{2}^{2}+2(1-Lh)\left\langle
x,g\right\rangle+\left\|g\right\|_{2}^{2}\right)$
$\displaystyle\quad+L\left\langle h\nabla
f_{P}(x),(1-Lh)x+g\right\rangle-\frac{Lh^{2}}{2}\left\|\nabla
f_{p}(x)\right\|_{2}^{2}+f_{P}(x)-f_{P}(y).$

And we have

$\displaystyle\quad-\frac{1}{4h}\left\|x-y+h\nabla
f(y)\right\|_{2}^{2}+\frac{1}{4h}\left\|y-x+h\nabla f(x)\right\|_{2}^{2}$
$\displaystyle=-\frac{1}{4h}\left\|h\nabla f(x)+h\nabla
f(y)-g\right\|_{2}^{2}+\frac{1}{4h}\left\|g\right\|_{2}^{2}$
$\displaystyle=\frac{1}{2}\left\langle g,\nabla f(x)+\nabla
f(y)\right\rangle-\frac{h}{4}\left\|\nabla f(x)+\nabla f(y)\right\|_{2}^{2}$
$\displaystyle=\frac{L}{2}\left\|g\right\|_{2}^{2}+\frac{1}{2}\left\langle
g,L(2-Lh)x+(1-Lh)\nabla f_{P}(x)+\nabla
f_{P}(y)\right\rangle-\frac{h}{4}\left\|\nabla f(x)+\nabla
f(y)\right\|_{2}^{2}$
$\displaystyle=\frac{L}{2}\left\|g\right\|_{2}^{2}+\frac{1}{2}\left\langle
g,L(2-Lh)x+(1-Lh)\nabla f_{P}(x)+\nabla f_{P}(y)\right\rangle$
$\displaystyle\quad-\frac{hL^{2}}{4}\left\|(2-Lh)x+g\right\|_{2}^{2}-\frac{hL}{2}\left\langle(2-Lh)x+g,(1-Lh)\nabla
f_{P}(x)+\nabla f_{P}(y)\right\rangle$
$\displaystyle\quad-\frac{h}{4}\left\|(1-Lh)\nabla f_{P}(x)+\nabla
f_{P}(y)\right\|_{2}^{2}.$

Rearranging the terms in the above two equations, we have

$\displaystyle\quad f(x)-f(y)-\frac{1}{4h}\left\|x-y+h\nabla
f(y)\right\|_{2}^{2}+\frac{1}{4h}\left\|y-x+h\nabla f(x)\right\|_{2}^{2}$
$\displaystyle=\underbrace{f_{P}(x)-f_{P}(y)}_{\Delta_{1}}+\underbrace{\left(\frac{L^{3}h^{2}}{2}-\frac{L^{4}h^{3}}{4}\right)\left\|x\right\|_{2}^{2}-\frac{L^{2}h}{4}\left\|g\right\|_{2}^{2}}_{\Delta_{2}}+\underbrace{\left(\frac{L^{3}h^{2}}{2}-\frac{L^{2}h}{2}\right)\left\langle
x,g\right\rangle}_{\Delta_{3}}$
$\displaystyle\quad+\underbrace{\left\langle\nabla
f_{P}(x),\left(\frac{1+L^{2}h^{2}}{2}\right)g\right\rangle-\left\langle\nabla
f_{P}(y),\frac{1+Lh}{2}g\right\rangle}_{\Delta_{4}}$
$\displaystyle\quad+\underbrace{\left\langle\nabla
f_{P}(x),\left(\frac{L^{2}h^{2}}{2}-\frac{L^{3}h^{3}}{2}\right)x\right\rangle-\left\langle\nabla
f_{P}(y),\frac{Lh}{2}\left(2-Lh\right)x\right\rangle}_{\Delta_{5}}$
$\displaystyle\quad\underbrace{-Lh^{2}\left\|\nabla
f_{P}(x)\right\|_{2}^{2}}_{\Delta_{6}}\underbrace{-\frac{h}{4}\left\|(1-Lh)\nabla
f_{P}(x)+\nabla f_{P}(y)\right\|_{2}^{2}}_{\Delta_{7}}$ (76)

We bound each of these seven terms in Lemma 24 under the condition $x\in
F_{1}$, $y=x-h\nabla f(x)+g$ and $g\sim\mathcal{N}(0,2h\mathbb{I}_{d})$.
According to Lemma 24, for $h\geq 1/\left(Ld^{1/2-3\theta}\right)$, any fixed
$x\in F_{1}$ and $y\sim\mathcal{N}(x-h\nabla f(x),2h\mathbb{I}_{d})$ we have

$\displaystyle\sum_{i=1}^{7}\Delta_{i}(x,y)\leq-d^{4\theta}/32$

with probability at least $1-10\exp\left(-d^{4\theta}/16384\right)$. Finally,
Lemma 14 follows by setting $G_{x}$ to be
$\left\\{y\in{}^{d}\mid\sum_{i=1}^{7}\Delta_{i}(x,y)\leq-d^{4\theta}/32\right\\}$.

####  B.1.1 Lemmas on concentration properties of the perturbed Gaussian
distribution

In this section we present three lemmas (Lemma 21, 22 and 23) to characterize
several properties of the perturbed Gaussian distribution $\pi_{1}$ in
Equation (47). Lemma 23 directly implies that the set $F_{1}$ in Equation
(B.1) satisfies $\pi_{1}(F_{1})>1/6$. Additionally, these lemmas are useful to
complete the proof of Lemma 24 in Appendix B.1.2.

The following lemma establishes bounds on the expectations of cosine terms. It
is adapted from Lemma 31 in Chewi et al. (2021).

###### Lemma 21

Fix $\xi\sim\mathcal{N}(0,1)$ and constants $a,b\in\real$. Then we have

  1. (a)

$\left|{\mathbb{E}}[\cos(a+b\xi)]\right|\leq\exp\left(-\frac{b^{2}}{2}\right)$.

  2. (b)

$\left|{\mathbb{E}}[\xi\cos(a+b\xi)]\right|\leq\left|b\right|\exp\left(-\frac{b^{2}}{2}\right)$

  3. (c)

$\left|{\mathbb{E}}[\xi^{2}\cos(a+b\xi)]\right|\leq\left|b^{2}-1\right|\exp\left(-\frac{b^{2}}{2}\right)$

Proof  Let $\text{Re}(\cdot)$ denote the real part of a complex number. Since
${\mathbb{E}}[e^{it\xi}]=e^{-\frac{1}{2}t^{2}}$, for any integer $\ell\geq 0$,
we have

$\displaystyle{\mathbb{E}}[\xi^{\ell}\cos(a+b\xi)]$
$\displaystyle={\mathbb{E}}[\text{Re}(\xi^{\ell}e^{i(a+b\xi})]$
$\displaystyle=\text{Re}\left(e^{ia}{\mathbb{E}}\left[\xi^{\ell}e^{ib{\xi}}\right]\right)$
$\displaystyle=\text{Re}\left(e^{ia}i^{-\ell}{\mathbb{E}}\left[\dfrac{\text{d}^{\ell}}{\text{dt}^{\ell}}e^{it\xi}\Big{|}_{t=b}\right]\right)$
$\displaystyle=\text{Re}\left(e^{ia}i^{-\ell}\dfrac{\text{d}^{\ell}}{\text{dt}^{\ell}}e^{-\frac{t^{2}}{2}}\Big{|}_{t=b}\right)$

Three results now follow from taking $\ell=0,1,2$.

Next we analyze several expectations under the perturbed Gaussian distribution
using Lemma 21. The first three statements in Lemma 21 are adapted from Lemma
32 in Chewi et al. (2021).

###### Lemma 22

Let $\zeta\in(1/5,1/4),d\geq 2048$ and $L>0$. Consider the one-dimensional
distribution
$\pi(x)=\frac{1}{Z}\exp\left(-\frac{L}{2}x^{2}+\frac{1}{2d^{2\zeta}}\cos(d^{\zeta}L^{\frac{1}{2}}x)\right)$,
where the normalization constant
$Z=\int\exp\left(-\frac{L}{2}x^{2}+\frac{1}{2d^{2\zeta}}\cos(d^{\zeta}L^{\frac{1}{2}}x)\right)dx$.
We have

  1. (a)

$\left|\frac{1}{Z}\sqrt{\frac{2\pi}{L}}-1\right|\leq\frac{1}{2}d^{-4\zeta}+d^{-2\zeta}\exp\left(-\frac{1}{2}d^{2\zeta}\right)$.

  2. (b)

${\mathbb{E}}_{x\sim\pi}[Lx^{2}]-1\leq d^{-4\zeta}$.

  3. (c)

$\left|{\mathbb{E}}_{x\sim\pi}[\cos(d^{\zeta}L^{\frac{1}{2}}x)]-\frac{1}{4}d^{-2\zeta}\right|\leq\frac{1}{2}d^{-4\zeta}$.

  4. (d)

$\left|{\mathbb{E}}_{x\sim\pi}\left[L^{\frac{1}{2}}x\sin\left(d^{\zeta}L^{\frac{1}{2}}x\right)\right]\right|\leq\frac{1}{2}d^{-4\zeta}$.

Proof

  1. (a)

The normalizing constant $Z$ is

$\displaystyle Z$
$\displaystyle=\int\exp\left(-\frac{L}{2}x^{2}+\frac{1}{2d^{2\zeta}}\cos(d^{\zeta}L^{1/2}x)\right)dx$
$\displaystyle\overset{(i)}{=}\frac{1}{\sqrt{L}}\int\exp\left(-\frac{1}{2}\xi^{2}+\frac{1}{2d^{2\zeta}}\cos(d^{\zeta}\xi)\right)d\xi$
$\displaystyle=\sqrt{\frac{2\pi}{L}}{\mathbb{E}}_{\xi\sim\mathcal{N}(0,1)}\left[\exp\left(\frac{1}{2d^{2\zeta}}\cos(d^{\zeta}\xi)\right)\right]$
$\displaystyle\overset{(ii)}{=}\sqrt{\frac{2\pi}{L}}{\mathbb{E}}_{\xi\sim\mathcal{N}(0,1)}\left[1+\frac{1}{2d^{2\zeta}}\cos(d^{\zeta}\xi)+R_{1}\right]$
$\displaystyle=\sqrt{\frac{2\pi}{L}}\left(1+\frac{1}{2d^{2\zeta}}{\mathbb{E}}_{\xi\sim\mathcal{N}(0,1)}\left[\cos(d^{\zeta}\xi)\right]+{\mathbb{E}}_{\xi\sim\mathcal{N}(0,1)}[R_{1}]\right)$

where step $(i)$ uses the transformation $\xi=\sqrt{L}x$ and step $(ii)$
introduces the remainder term
$R_{1}=\exp\left(\frac{1}{2d^{2\zeta}}\cos(d^{\zeta}\xi)\right)-1-\frac{1}{2d^{2\zeta}}\cos(d^{\zeta}\xi)$.
By Lemma 21, the second term in the last line satisfies

$\displaystyle\left|\frac{1}{2d^{2\zeta}}{\mathbb{E}}_{\xi\sim\mathcal{N}(0,1)}\left[\cos(d^{\zeta}\xi)\right]\right|\leq\frac{d^{-2\zeta}\exp\left(-\frac{d^{2\zeta}}{2}\right)}{2}$

Since $1+x\leq\exp(x)\leq 1+x+x^{2}$ for $x\in[-1,1]$, we have $0\leq
R_{1}\leq 1/(4d^{4\zeta})$. We obtain

$\displaystyle\left|\sqrt{\frac{L}{2\pi}}Z-1\right|\leq\frac{1}{4}d^{-4\zeta}+\frac{1}{2}d^{-2\zeta}\exp\left(-\frac{1}{2}d^{2\zeta}\right)$

The result now follows by $1/(1-x)\leq 1+2x$ and $1/(1+x)\geq 1-2x$ when
$x\in(0,1/2)$.

  2. (b)

We write the expectation as

$\displaystyle{\mathbb{E}}_{x\sim\pi}[Lx^{2}]$ $\displaystyle=\frac{1}{Z}\int
Lx^{2}\exp\left(-\frac{L}{2}x^{2}+\frac{1}{2d^{2\zeta}}\cos(d^{\zeta}L^{1/2}x)\right)dx$
$\displaystyle\overset{(i)}{=}\frac{1}{Z}\sqrt{\frac{2\pi}{L}}{\mathbb{E}}_{\xi\sim\mathcal{N}(0,1)}\left[\xi^{2}\exp\left(\frac{1}{2d^{2\zeta}}\cos(d^{\zeta}\xi)\right)\right]$
$\displaystyle\overset{(ii)}{=}\frac{1}{Z}\sqrt{\frac{2\pi}{L}}{\mathbb{E}}_{\xi\sim\mathcal{N}(0,1)}\left[\xi^{2}\left(1+\frac{1}{2d^{2\zeta}}\cos(d^{\zeta}\xi)+R_{2}\right)\right]$
$\displaystyle=\frac{1}{Z}\sqrt{\frac{2\pi}{L}}\left(1+\frac{1}{2d^{2\zeta}}{\mathbb{E}}_{\xi\sim\mathcal{N}(0,1)}\left[\xi^{2}\cos(d^{\zeta}\xi)\right]+{\mathbb{E}}_{\xi\sim\mathcal{N}(0,1)}[R_{2}]\right),$

where step $(i)$ uses the transformation $\xi=\sqrt{L}x$ and step $(ii)$
introduces $R_{2}$ as the remainder term. Lemma 21 guarantees that the second
term satisfies

${\mathbb{E}}_{\xi\sim\mathcal{N}(0,1)}[\xi^{2}\cos(d^{\zeta}\xi)]/(2d^{2\zeta})\leq\exp\left(-d^{2\zeta}/2\right)/2$.
The remainder term satisfies

${\mathbb{E}}_{\xi\sim\mathcal{N}(0,1)}[R_{2}]\leq d^{-4\zeta}/4$ because
$\exp(x)\leq 1+x+x^{2}$ for $x\in[-1,1]$. Using the above estimates and part
(a), we obtain

$\displaystyle{\mathbb{E}}_{x\sim\pi}\left[Lx^{2}\right]$
$\displaystyle\leq\left(1+\frac{1}{2}d^{-4\zeta}+d^{-2\zeta}\exp\left(-\frac{1}{2}d^{2\zeta}\right)\right)\left(1+\frac{1}{2}\exp\left(-\frac{1}{2}d^{2\zeta}\right)+\frac{1}{4}d^{-4\zeta}\right)$
$\displaystyle\leq\left(1+\frac{1}{2}d^{-4\zeta}+\frac{1}{16}d^{-6\zeta}\right)\left(1+\frac{1}{32}d^{-4\zeta}+\frac{1}{4}d^{-4\zeta}\right)$
$\displaystyle\leq 1+d^{-4\zeta},$

where we use $\exp(x/2)\geq 16x^{2}$ for $x\geq 20$ with $x=d^{2\zeta}$.

  3. (c)

Using a similar strategy as above, we obtain

$\displaystyle\quad{\mathbb{E}}_{x\sim\pi}[\cos(d^{\zeta}L^{1/2}x)]$
$\displaystyle=\frac{1}{Z}\int\cos(d^{\zeta}L^{1/2}x)\exp\left(-\frac{L}{2}x^{2}+\frac{1}{2d^{2\zeta}}\cos(d^{\zeta}L^{1/2}x)\right)dx$
$\displaystyle\overset{(i)}{=}\frac{1}{Z}\sqrt{\frac{2\pi}{L}}{\mathbb{E}}_{\xi\sim\mathcal{N}(0,1)}\left[\cos(d^{\zeta}\xi)\exp\left(\frac{1}{2d^{2\zeta}}\cos(d^{\zeta}\xi)\right)\right]$
$\displaystyle\overset{(ii)}{=}\frac{1}{Z}\sqrt{\frac{2\pi}{L}}{\mathbb{E}}_{\xi\sim\mathcal{N}(0,1)}\left[\cos(d^{\zeta}\xi)+\frac{1}{2d^{2\zeta}}\cos^{2}(d^{\zeta}\xi)+R_{3}\right]$
$\displaystyle=\frac{1}{Z}\sqrt{\frac{2\pi}{L}}\Big{(}{\mathbb{E}}_{\xi\sim\mathcal{N}(0,1)}\left[\cos(d^{\zeta}\xi)\right]+\frac{1}{4d^{2\zeta}}+\frac{1}{4d^{2\zeta}}{\mathbb{E}}_{\xi\sim\mathcal{N}(0,1)}\left[\cos(2d^{\zeta}\xi)\right]$
$\displaystyle\hskip
40.00006pt+{\mathbb{E}}_{\xi\sim\mathcal{N}(0,1)}[R_{3}]\Big{)},$

where step $(i)$ uses the transformation $\xi=\sqrt{L}x$ and step $(ii)$
introduces $R_{3}$ as the remainder term. We have
$\left|{\mathbb{E}}_{\xi\sim\mathcal{N}(0,1)}[\cos(d^{\zeta}\xi)\right|\leq\exp(-d^{2\zeta}/2)$
and $\left|{\mathbb{E}}_{\xi\sim\mathcal{N}(0,1)}[\cos(2d^{\zeta}\xi)]\right|$
$\leq\exp(-2d^{2\zeta})$ by Lemma 21. The remainder term satisfies
$\left|{\mathbb{E}}_{\xi\sim\mathcal{N}(0,1)}[R_{3}]\right|\leq d^{-4\zeta}/4$
again because $1+x\leq\exp(x)\leq 1+x+x^{2}$ for $x\in[-1,1]$. Plugging in
these estimates and using part (a), we obtain

$\displaystyle\quad\left|{\mathbb{E}}_{x\sim\pi}[\cos(d^{\zeta}L^{1/2}x)]-\frac{1}{4}d^{-2\zeta}\right|$
$\displaystyle\leq\left(1+\frac{1}{2}d^{-4\zeta}+d^{-2\zeta}\exp\left(-\frac{1}{2}d^{2\zeta}\right)\right)\left(\frac{1}{4}d^{-2\zeta}+\frac{1}{4}d^{-4\zeta}+2\exp(-\frac{1}{2}d^{2\zeta})\right)-\frac{1}{4}d^{-2\zeta}$
$\displaystyle\leq\left(1+\frac{1}{2}d^{-4\zeta}+\frac{1}{16}d^{-6\zeta}\right)\left(\frac{1}{4}d^{-2\zeta}+\frac{1}{4}d^{-4\zeta}+\frac{1}{8}d^{-4\zeta}\right)-\frac{1}{4}d^{-2\zeta}$
$\displaystyle\leq\frac{1}{2}d^{-4\zeta}.$

  4. (d)

We have

$\displaystyle\quad{\mathbb{E}}_{x\sim\pi}\left[L^{\frac{1}{2}}x\sin\left(d^{\zeta}L^{\frac{1}{2}}x\right)\right]$
$\displaystyle=\frac{1}{Z}\int
L^{\frac{1}{2}}x\sin\left(d^{\zeta}L^{\frac{1}{2}}x\right)\exp\left(-\frac{L}{2}x^{2}+\frac{1}{2d^{2\zeta}}\cos\left(d^{\zeta}L^{\frac{1}{2}}x\right)\right)dx$
$\displaystyle=\frac{1}{Z}\sqrt{\frac{2\pi}{L}}{\mathbb{E}}_{\xi\sim\mathcal{N}(0,1)}\left[\xi\cos(d^{\zeta}\xi)\exp\left(\frac{1}{2d^{2\zeta}}\cos(d^{\zeta}\xi)\right)\right]$
$\displaystyle=\frac{1}{Z}\sqrt{\frac{2\pi}{L}}{\mathbb{E}}_{\xi\sim\mathcal{N}(0,1)}\left[\xi\cos(d^{\zeta}\xi)+\frac{\xi}{2d^{2\zeta}}\cos(d^{\zeta}\xi)^{2}+\xi
R_{3}\right]$
$\displaystyle=\frac{1}{Z}\sqrt{\frac{2\pi}{L}}\left({\mathbb{E}}_{\xi\sim\mathcal{N}(0,1)}\left[\xi\cos(d^{\zeta}\xi)\right]+{\mathbb{E}}_{\xi\sim\mathcal{N}(0,1)}\left[\frac{\xi}{4d^{2\zeta}}\cos(2d^{\zeta}\xi)\right]+{\mathbb{E}}_{\xi\sim\mathcal{N}(0,1)}\left[\xi
R_{3}\right]\right).$

Applying Lemma 21 again, we obtain

$\displaystyle\left|{\mathbb{E}}_{\xi\sim\mathcal{N}(0,1)}\left[\xi\cos(d^{\zeta}\xi)\right]\right|$
$\displaystyle\leq d^{\zeta}\exp\left(-\frac{d^{2\zeta}}{2}\right)$
$\displaystyle\left|{\mathbb{E}}_{\xi\sim\mathcal{N}(0,1)}\left[\xi\cos(2d^{\zeta}\xi)\right]\right|$
$\displaystyle\leq 2d^{\zeta}\exp\left(-2d^{2\zeta}\right)$
$\displaystyle\left|{\mathbb{E}}_{\xi\sim\mathcal{N}(0,1)}[\xi R_{3}]\right|$
$\displaystyle\leq{\mathbb{E}}_{\xi\sim\mathcal{N}(0,1)}[\xi^{2}R_{3}^{2}]^{1/2}\leq\frac{d^{-4\zeta}}{4}$

Plugging these estimates and using part (a), we obtain

$\displaystyle\quad\left|{\mathbb{E}}_{x\sim\pi}\left[L^{\frac{1}{2}}x\sin\left(d^{\zeta}L^{\frac{1}{2}}x\right)\right]\right|$
$\displaystyle\leq\left(1+\frac{1}{2}d^{-4\zeta}+d^{-2\zeta}\exp\left(-\frac{1}{2}d^{2\zeta}\right)\right)\left(d^{\zeta}\exp\left(-\frac{1}{2}d^{2\zeta}\right)+2d^{\zeta}\exp\left(-2d^{2\zeta}\right)+\frac{1}{4}d^{-4\zeta}\right)$
$\displaystyle\leq\left(1+\frac{1}{2}d^{-4\zeta}+\frac{1}{6}d^{-7\zeta}\right)\left(\frac{1}{6}d^{-4\zeta}+\frac{1}{96}d^{-4\zeta}+\frac{1}{4}d^{-4\zeta}\right)$
$\displaystyle\leq\frac{1}{2}d^{-4\zeta},$

where the last two steps use $\exp(x^{2}/2)\geq 6x^{5}$ for $x\geq 5$ with
$x=d^{\zeta}$.

Finally we provide constant probability bounds for each term in the definition
of $F_{1}$ in Equation (B.1) using Lemma 22.

###### Lemma 23

Fix $\zeta\in(\frac{1}{5},\frac{1}{4}),d\geq 2048$ and $L>0$. Assume that the
$d$-dimensional random variable $x$ follows the distribution
$\pi(x)\propto\exp\left(\frac{L}{2}\sum_{i=1}^{d}x_{[i]}^{2}-\frac{1}{2d^{2\zeta}}\sum_{i=1}^{d}\cos(d^{\zeta}L^{\frac{1}{2}}x_{[i]})\right)$,
we have

  1. (a)

$\displaystyle{\mathbb{P}}_{x\sim\pi}\left[\max_{i}\sqrt{L}\left|x_{[i]}\right|\geq
4\sqrt{\log(8d)}\right]\leq\frac{1}{4d}$

  2. (b)

$\displaystyle{\mathbb{P}}_{x\sim\pi}\left[L\left\|x\right\|_{2}^{2}\geq
d+d^{1-4\zeta}+5\sqrt{d}\right]\leq 0.14$

  3. (c)

$\displaystyle{\mathbb{P}}_{x\sim\pi}\left[\sum_{i=1}^{d}-\cos(d^{\zeta}L^{1/2}x_{[i]})\geq-\frac{1}{4}d^{1-2\zeta}+\frac{1}{2}d^{1-4\zeta}+2d^{\frac{1}{2}}\right]\leq
0.14$

  4. (d)

$\displaystyle{\mathbb{P}}_{x\sim\pi}\left[\left|\sum_{i=1}^{d}-\cos(2d^{\zeta}L^{\frac{1}{2}}x_{[i]})+\frac{1}{16}d^{1-2\zeta}\right|\geq\frac{1}{8}d^{1-4\zeta}+2d^{\frac{1}{2}}\right]\leq
0.28$

  5. (e)

$\displaystyle{\mathbb{P}}_{x\sim\pi}\left[\left|\sum_{i=1}^{d}L^{\frac{1}{2}}x_{[i]}\sin(d^{\zeta}L^{\frac{1}{2}}x_{[i]})\right|\geq\frac{1}{2}d^{1-4\zeta}+2d^{\frac{1}{2}}\right]\leq
0.26$

Proof

  1. (a)

See Lemma 33 in Chewi et al. (2021).

  2. (b)

By Lemma 22-(b), ${\mathbb{E}}_{x\sim\pi}[L\left\|x\right\|_{2}^{2}]\leq
d+d^{1-4\zeta}$. Note that $\pi$ is $L/2$-strongly log-concave, we deduce that
for a random variable $x$ drawn from $\pi$, $x-{\mathbb{E}}[x]$ is a sub-
Gaussian random vector with parameter $\sqrt{2/L}$ (see Proof of Lemma 1 in
Dwivedi et al. (2019)). Since $x\mapsto\sqrt{L}\left\|x\right\|_{2}$ is
$\sqrt{L}$ Lipschitz,
$\sqrt{L}\left\|x\right\|_{2}-{\mathbb{E}}[\sqrt{L}\left\|x\right\|_{2}]$ is a
sub-Gaussian with parameter $\sqrt{2}$. Applying the Chernoff bound (see for
example, Equation 2.9 in Wainwright (2019)), we have

$\displaystyle{\mathbb{P}}_{x\sim\pi}\left[\sqrt{L}\left\|x\right\|_{2}\geq{\mathbb{E}}[\sqrt{L}\left\|x\right\|_{2}]+t\right]\leq\exp\left(-\frac{t^{2}}{4}\right).$

Take $t=2$ and use
${\mathbb{E}}[\sqrt{L}\left\|x\right\|_{2}]\leq{\mathbb{E}}[L\left\|x\right\|_{2}^{2}]^{\frac{1}{2}}$,
we obtain

$\displaystyle{\mathbb{P}}_{x\sim\pi}\left[L\left\|x\right\|_{2}^{2}\geq
d+d^{1-4\zeta}+5\sqrt{d}\right]\leq\exp(-2)<0.14$

  3. (c)

By Lemma 22-(c),
${\mathbb{E}}_{x\sim\pi}\left[-\sum_{i=1}^{d}\cos(d^{\zeta}L^{1/2}x_{[i]})\right]\leq-d^{1-2\zeta}/4+d^{1-4\zeta}/2$.
Each cosine term is bounded in $[-1,1]$. Applying Hoeffding bound (see for
example, Proposition 2.1 in Wainwright (2019)), we have

$\displaystyle{\mathbb{P}}_{x\sim\pi}\left[-\sum_{i=1}^{d}\cos(d^{\zeta}L^{1/2}x_{[i]})\geq{\mathbb{E}}\left[-\sum_{i=1}^{d}\cos(d^{\zeta}L^{1/2}x_{[i]})\right]+td\right]\leq\exp\left(-\frac{t^{2}d}{2}\right).$

Take $t=2d^{-1/2}$, we obtain

$\displaystyle{\mathbb{P}}_{x\sim\pi}\left[-\sum_{i=1}^{d}\cos(d^{\zeta}L^{1/2}x_{[i]})\geq-\frac{1}{4}d^{1-2\zeta}+\frac{1}{2}d^{1-4\zeta}+2d^{\frac{1}{2}}\right]\leq\exp(-2)<0.14$

  4. (d)

The proof is the same as (c) using a two-sided Hoeffding bound.

  5. (e)

By Lemma 22-(d),
$\left|{\mathbb{E}}_{x\sim\pi}\left[\sum_{i=1}^{d}L^{\frac{1}{2}}x_{[i]}\sin\left(d^{\zeta}L^{\frac{1}{2}}x_{[i]}\right)\right]\right|\leq
d^{1-4\zeta}/2$. We also have

$\displaystyle{\rm
Var}\left[\sum_{i=1}^{d}L^{\frac{1}{2}}x_{[i]}\sin\left(d^{\zeta}L^{\frac{1}{2}}x_{[i]}\right)\right]$
$\displaystyle\leq L\sum_{i=1}^{d}{\mathbb{E}}x_{[i]}^{2}\leq d+d^{1-4\zeta}$

Applying Chebyshev’s inequality, we obtain

$\displaystyle{\mathbb{P}}_{x\sim\pi}\left[\sum_{i=1}^{d}L^{\frac{1}{2}}x_{[i]}\sin\left(d^{\zeta}L^{\frac{1}{2}}x_{[i]}\right)\geq\frac{1}{2}d^{1-4\zeta}+2d^{\frac{1}{2}}\right]\leq\frac{d+d^{1-4\zeta}}{4d}$
$\displaystyle<0.26$

####  B.1.2 High probability upper bound on the acceptance rate

In this section we bound each of the seven terms in Equation (B.1) with high
probability, which implies an high probability upper bound on the acceptance
rate for MALA applied $\pi_{1}$. Before we do so, we first state the following
two forms of the Bernstein’s inequality (see Propostion 2.14 in Wainwright
(2019) and Lemma 14.9 in Bühlmann and Van De Geer (2011)) which we frequently
use in the proof of the following lemma.

Let $X_{1},\ldots,X_{d}$ be i.i.d. random variables satisfying
$\left|X_{i}-{\mathbb{E}}[X_{i}]\right|\leq K$. Then for any $\epsilon\geq 0$,

$\displaystyle{\mathbb{P}}\left[\sum_{i=1}^{d}\left(X_{i}-{\mathbb{E}}[X]\right)\geq\epsilon\right]\leq\exp\left(-\frac{\epsilon^{2}}{2\left(\sum_{i=1}^{d}{\rm
Var}[X_{i}]+\frac{1}{3}K\epsilon\right)}\right)$ (77)

Let $X_{1},\ldots,X_{n}$ be i.i.d. random variables satisfying
${\mathbb{E}}[\left|X-{\mathbb{E}}[X]\right|^{\ell}]\leq\ell!K^{\ell-2}/2,\
\forall\ell\geq 2$. Then for any $\epsilon\geq 0$,

$\displaystyle{\mathbb{P}}\left[\sum_{i=1}^{d}\left(X_{i}-{\mathbb{E}}[X]\right)\geq
d(K\epsilon+\sqrt{2\epsilon})\right]\leq\exp\left(-d\epsilon\right).$ (78)

###### Lemma 24

Assume

$\displaystyle\theta\in(0,\frac{1}{20}),L>0,d^{\theta}\geq\max\left\\{\frac{1}{2}\log
d+6,10\right\\},h\geq\frac{1}{Ld^{\frac{1}{2}-3\theta}}.$ (79)

Given any fixed $x\in F_{1}$ defined in Equation (B.1). Let $\Delta_{i}(x,y)\
(1\leq i\leq 7)$ be the decomposed terms from the exponent of the acceptance
rate in Equation (B.1), in which $y\sim\mathcal{N}(x-h\nabla
f(x),2h\mathbb{I}_{d})$ and $g=y-x+h\nabla f(x)$. We have

$\displaystyle\sum_{i=1}^{7}\Delta_{i}(x,y)\leq-\frac{1}{32}d^{4\theta}$

with probability at least $1-10\exp\left(-d^{4\theta}/16384\right)$.

Proof  Recall that $\zeta=1/4-\theta$. All high probability bounds in the
proof are stated with respect to $\xi:=\left(y-x+h\nabla
f(x)\right)/\sqrt{2h}\sim\mathcal{N}(0,\mathbb{I}_{d})$. Now we bound each
$\Delta_{i}$ separately.

  1. (1)

We write $\Delta_{1}$ as

$\displaystyle\Delta_{1}=f_{P}(x)-f_{P}(y)=\sum_{i=1}^{d}\underbrace{-\frac{1}{2d^{2\zeta}}\cos(d^{\zeta}L^{\frac{1}{2}}x_{[i]})}_{\Delta_{1,1,i}}+\underbrace{\frac{1}{2d^{2\zeta}}\cos(d^{\zeta}L^{\frac{1}{2}}y_{[i]})}_{\Delta_{1,2,i}}.$

By the definition of $F_{1}$ in Equation (B.1), we have

$\displaystyle\sum_{i=1}^{d}\Delta_{1,1,i}$
$\displaystyle\leq-\frac{1}{8}d^{1-4\zeta}+\frac{1}{4}d^{1-6\zeta}+d^{\frac{1}{2}-2\zeta}$
$\displaystyle\leq-\frac{1}{8}d^{1-4\zeta}+\frac{1}{64}d^{1-4\zeta}$ (80)

where we use the assumption (79) in the last line. Since
$y_{[i]}=x_{[i]}-h\nabla f(x)_{[i]}+\sqrt{2h}\xi_{[i]}$, we have

$\displaystyle{\mathbb{E}}\left[\Delta_{1,2,i}\right]$
$\displaystyle\overset{(i)}{\leq}\frac{1}{2d^{2\zeta}}\exp\left(-Lhd^{2\zeta}\right)\overset{(ii)}{\leq}\frac{1}{128}d^{-4\zeta}$
$\displaystyle{\rm Var}\left[\Delta_{1,2,i}\right]$
$\displaystyle\leq{\mathbb{E}}\left[\Delta_{1,2,i}^{2}\right]\overset{(iii)}{\leq}\frac{1}{4d^{4\zeta}}$
$\displaystyle\left|\Delta_{1,2,i}\right|$
$\displaystyle\overset{(iv)}{\leq}\frac{1}{2d^{2\zeta}}$

Inequality (i) follows from Lemma 21-(a). Inequality (ii) follows from the
assumption (79). (iii) and (iv) simply bounds cousine by $1$.

With the above bounds for individual terms, applying Bernstein’s inequality
(77) with $\epsilon=d^{1-4\zeta}/128$, we obtain

$\displaystyle{\mathbb{P}}\left[\sum_{i=1}^{d}\Delta_{1,2,i}\geq\frac{1}{64}d^{1-4\zeta}\right]\leq\exp\left(-\frac{d^{1-4\zeta}}{16384}\right)$
(81)

Combine Equation ((1)) and (81), we have that for fixed $x\in F_{1}$, the
following bound

$\displaystyle\Delta_{1}\leq-\frac{3}{32}d^{1-4\zeta}.$ (82)

holds with probability at least $1-\exp(-d^{1-4\zeta}/16384)$.

  2. (2)

From the definition of $F_{1}$ in Equation (B.1), we have

$\displaystyle L\left\|x\right\|_{2}^{2}\leq d+d^{1-4\zeta}+5d^{\frac{1}{2}}.$

Since $\left\|\xi\right\|_{2}^{2}$ is Chi-square with $d$-degree of freedom,
standard Chi-square tail bound (Lemma 1 in Laurent and Massart (2000)) shows
that

$\displaystyle{\mathbb{P}}\left[\left\|\xi\right\|_{2}^{2}\leq
d-\frac{1}{64}d^{1-2\zeta}\right]\leq\exp\left(-\frac{d^{1-4\zeta}}{16384}\right).$

Given that $g=\sqrt{2h}\xi$, we obtian

$\displaystyle\Delta_{2}$
$\displaystyle=\left(\frac{L^{3}h^{2}}{2}-\frac{L^{4}h^{3}}{4}\right)\left\|x\right\|_{2}^{2}-\frac{L^{2}h}{4}\left\|g\right\|_{2}^{2}$
$\displaystyle\leq\frac{L^{2}h^{2}}{2}\cdot\left(d+d^{1-4\zeta}+5d^{\frac{1}{2}}\right)-\frac{L^{2}h}{4}\left(2hd-\frac{1}{32}hd^{1-2\zeta}\right)$
$\displaystyle\leq\left(\frac{1}{2}L^{2}h^{2}d^{1-4\zeta}+\frac{5}{2}L^{2}h^{2}d^{\frac{1}{2}}\right)+\frac{1}{128}L^{2}h^{2}d^{1-2\zeta}$
$\displaystyle\leq\frac{1}{32}L^{2}h^{2}d^{1-2\zeta}+\frac{1}{128}L^{2}h^{2}d^{1-2\zeta}$
$\displaystyle=\frac{5}{128}L^{2}h^{2}d^{1-2\zeta}$ (83)

holds with probability at least $1-\exp\left(-d^{1-4\zeta}/16384\right)$. The
last line makes use of the assumption (79).

  3. (3)

Since $\left\langle L^{1/2}x,\xi\right\rangle$ is
$\left\|L^{1/2}x\right\|_{2}$-Lipschitz with respect to $\xi$, it is sub-
Gaussian with the same Lipschitz constant. Using the tail bound for Lipschitz
function of sub-Gaussian random variables, we have

$\displaystyle{\mathbb{P}}\left[\left|\left\langle
L^{1/2}x,\xi\right\rangle\right|\geq\frac{1}{64}d^{1-2\zeta}\right]\leq
2\exp\left(-\frac{d^{2-4\zeta}}{8192L\left\|x\right\|_{2}^{2}}\right)\leq
2\exp\left(-\frac{d^{1-4\zeta}}{16384}\right).$

where we use the definition of $F_{1}$ and the assumption (79) to get
$L\left\|x\right\|_{2}^{2}\leq 2d$ in the last step. Now given that
$\left|\Delta_{3}\right|\leq\frac{1}{2}\left(L^{\frac{3}{2}}h^{\frac{3}{2}}+L^{\frac{5}{2}}h^{\frac{5}{2}}\right)\left|\left\langle
L^{\frac{1}{2}}x,\xi\right\rangle\right|$, we have

$\displaystyle\left|\Delta_{3}\right|$
$\displaystyle\leq\frac{1}{128}\left(L^{\frac{3}{2}}h^{\frac{3}{2}}+L^{\frac{5}{2}}h^{\frac{5}{2}}\right)d^{1-2\zeta}$
$\displaystyle\leq\left(\frac{1}{128}Lh+\frac{1}{256}L^{2}h^{2}+\frac{1}{128}L^{3}h^{3}\right)d^{1-2\zeta}$
(84)

with probability at least $1-2\exp\left(-d^{1-4\zeta}/16384\right)$.

  4. (4)

For $\left\langle\nabla f_{P}(x),g\right\rangle$, from the definition of
$F_{1}$ in Equation (B.1), we have

$\displaystyle\left\|\nabla f_{P}(x)\right\|_{2}^{2}$
$\displaystyle=\sum_{i=1}^{d}\frac{L}{4d^{2\zeta}}\sin^{2}(d^{\zeta}L^{\frac{1}{2}}x_{[i]})$
$\displaystyle=\sum_{i=1}^{d}\frac{L}{4d^{2\zeta}}\left(1-\cos(2d^{\zeta}L^{\frac{1}{2}}x_{[i]})\right)$
$\displaystyle\leq\frac{1}{4}{Ld^{1-2\zeta}}+\frac{1}{4}{Ld^{-2\zeta}}\left(-\frac{1}{16}d^{1-2\zeta}+\frac{1}{8}d^{1-4\zeta}+2d^{\frac{1}{2}}\right)$
$\displaystyle\leq\frac{1}{2}Ld^{1-2\zeta}-\frac{1}{64}Ld^{1-4\zeta},$

where the last step uses the assumption (79). Since $\left\langle\nabla
f_{P}(x),g\right\rangle$ is $\sqrt{2h}\left\|\nabla
f_{P}(x)\right\|_{2}$-Lipschitz with respect to $\xi$, it is sub-Gaussian with
the same Lipschitz constant. We have

$\displaystyle{\mathbb{P}}\left[\left|\left\langle\nabla
f_{P}(x),g\right\rangle\right|\geq\frac{1}{64}\sqrt{Lh}d^{1-3\zeta}\right]\leq
2\exp\left(-\frac{Ld^{2-6\zeta}/64^{2}}{4\left\|\nabla
f_{P}(x)\right\|_{2}^{2}}\right)\leq
2\exp\left(-\frac{d^{1-4\zeta}}{8192}\right)$ (85)

For $\left\langle\nabla f_{P}(y),g\right\rangle$, we have

$\displaystyle\left\langle\nabla f_{P}(y),g\right\rangle$
$\displaystyle=\sqrt{Lh}\sum_{i=1}^{d}\underbrace{\frac{\xi_{[i]}}{\sqrt{2}{d^{\zeta}}}\sin\left(d^{\zeta}L^{\frac{1}{2}}y_{[i]}\right)}_{\Delta_{4,2,i}}$

Applying Lemma 21, we can bound the moments of $\Delta_{4,2,i}$ as follows

$\displaystyle\left|{\mathbb{E}}\left[\Delta_{4,2,i}\right]\right|$
$\displaystyle\leq\sqrt{Lh}\exp\left(-Lhd^{2\zeta}\right)\overset{(i)}{\leq}\frac{1}{512}\sqrt{Lh}d^{-2\zeta}$
$\displaystyle{\mathbb{E}}\left[\left|\Delta_{4,2,i}-{\mathbb{E}}[\Delta_{4,2,i}]\right|^{\ell}\right]$
$\displaystyle\leq{\mathbb{E}}\left[2^{\ell-1}\left(\left|\Delta_{4,2,i}\right|^{\ell}+\left|{\mathbb{E}}\left[\Delta_{4,2,i}\right]\right|^{\ell}\right)\right]$
$\displaystyle\leq
2^{\ell-1}\left({\mathbb{E}}\left|\frac{\xi_{[i]}}{\sqrt{2}}\right|^{\ell}+\left|{\mathbb{E}}\left[\Delta_{4,2,i}\right]\right|^{\ell}\right)$
$\displaystyle\overset{(ii)}{\leq}2^{\ell-1}\left(\frac{(\ell-1)!!}{2^{\frac{\ell}{2}}}+\left(\frac{1}{2e}\right)^{\frac{\ell}{2}}\right)$
$\displaystyle\leq\frac{\ell!}{2}2^{\ell-2}.$

Step $(i)$ uses the assumption (79). Step (ii) uses the expected moments of
the normal distribution for the first term, and applies
$x\exp(-x^{2})\leq(2e)^{-1/2}$ for $x=\sqrt{Lh}$ to bound the second term.
Applying Bernstein’s inequality (78) with $K=2$ and
$\epsilon=d^{-4\zeta}/12800$, we have

$\displaystyle{\mathbb{P}}\left[\left\langle\nabla
f_{P}(y),g\right\rangle\geq\frac{1}{512}Lhd^{1-2\zeta}+\sqrt{Lh}\left(\frac{1}{6400}d^{1-5\zeta}+\frac{1}{80}d^{1-3\zeta}\right)\right]\leq\exp\left(-\frac{d^{1-4\zeta}}{12800}\right)$
(86)

Combining (85) and (86), we obtain

$\displaystyle\left|\Delta_{4}\right|$ $\displaystyle=\left|\left\langle\nabla
f_{P}(x),\left(\frac{1+L^{2}h^{2}}{2}\right)g\right\rangle-\left\langle\nabla
f_{P}(y),\frac{1+Lh}{2}g\right\rangle\right|$
$\displaystyle\leq\frac{1}{64}\left(1+L^{2}h^{2}\right)\sqrt{Lh}d^{1-3\zeta}+\frac{1}{512}(1+Lh)Lhd^{1-2\zeta}$
$\displaystyle\quad+\left(1+Lh\right)\sqrt{Lh}\left(\frac{1}{12800}d^{1-5\zeta}+\frac{1}{160}d^{1-3\zeta}\right)$
$\displaystyle\overset{(i)}{\leq}\frac{1}{128}(1+L^{2}h^{2})\left(4d^{1-4\zeta}+\frac{1}{4}Lhd^{1-2\zeta}\right)+\frac{1}{512}(1+Lh)Lhd^{1-2\zeta}$
$\displaystyle\quad+\frac{1}{128}\left(1+Lh\right)\left(4d^{1-4\zeta}+\frac{1}{4}Lhd^{1-2\zeta}\right)$
$\displaystyle=\left(\frac{1}{16}+\frac{1}{32}Lh+\frac{1}{32}L^{2}h^{2}\right)d^{1-4\zeta}+\left(\frac{3}{512}Lh+\frac{1}{256}L^{2}h^{2}+\frac{1}{512}L^{3}h^{3}\right)d^{1-2\zeta}$
(87)

with probability at least $1-3\exp\left(-d^{1-4\zeta}/12800\right)$. Step
$(i)$ uses the assumption (79).

  5. (5)

By the definition of $F_{1}$ in (B.1),

$\displaystyle\left|\left\langle\nabla f_{P}(x),x\right\rangle\right|$
$\displaystyle=\left|\sum_{i=1}^{d}\frac{L^{\frac{1}{2}}}{2d^{\zeta}}x_{[i]}\sin(d^{\zeta}L^{\frac{1}{2}}x_{[i]})\right|$
$\displaystyle\leq\frac{1}{2}d^{1-4\zeta}+2d^{\frac{1}{2}}$ (88)

We write $\left\langle\nabla f_{P}(y),x\right\rangle$ as

$\displaystyle\left\langle\nabla f_{P}(y),x\right\rangle$
$\displaystyle=\sum_{i=1}^{d}\underbrace{\frac{L^{\frac{1}{2}}}{2d^{\zeta}}x_{[i]}\sin(d^{\zeta}L^{\frac{1}{2}}y_{[i]})}_{\Delta_{5,i}}$

By the definition of $F_{1}$ and the assumption (79),

$\displaystyle{\mathbb{E}}\left|\Delta_{5,i}\right|$
$\displaystyle\leq\frac{L^{\frac{1}{2}}\left|x_{[i]}\right|}{2d^{\zeta}}\exp\left(-Lhd^{2\zeta}\right)\leq
2\left(\log(8d)\right)^{\frac{1}{2}}d^{-\zeta}\exp\left(-Lhd^{2\zeta}\right)\leq\frac{1}{512}d^{-2\zeta}$
$\displaystyle{\rm Var}\left[\Delta_{5,i}\right]$
$\displaystyle\leq\frac{L}{4d^{2\zeta}}x_{[i]}^{2}\leq
4\left(\log(8d)\right)d^{-2\zeta}$ $\displaystyle\left|\Delta_{5,i}\right|$
$\displaystyle\leq 2\left(\log(8d)\right)^{\frac{1}{2}}d^{-\zeta}$

Applying Bernstein’s inequality (77) with $\epsilon=d^{1-2\zeta}/512$, we have

$\displaystyle{\mathbb{P}}\left[\left|\left\langle\nabla
f_{P}(y),x\right\rangle\right|\geq\frac{1}{256}d^{1-2\zeta}\right]$
$\displaystyle\leq\exp\left(-\frac{d^{1-4\zeta}}{4096}\right)$ (89)

Combining Equation ((5)) and (89), we get

$\displaystyle\Delta_{5}$ $\displaystyle=\left\langle\nabla
f_{P}(x),\left(\frac{L^{2}h^{2}}{2}-\frac{L^{3}h^{3}}{2}\right)x\right\rangle-\left\langle\nabla
f_{P}(y),\frac{Lh}{2}\left(2-Lh\right)x\right\rangle$
$\displaystyle\leq\left(\frac{1}{4}L^{2}h^{2}d^{1-4\zeta}+L^{2}h^{2}d^{\frac{1}{2}}\right)+\left(\frac{1}{4}L^{3}h^{3}d^{1-4\zeta}+L^{3}h^{3}d^{\frac{1}{2}}\right)$
$\displaystyle\quad+\frac{1}{256}Lhd^{1-2\zeta}+\frac{1}{512}L^{2}h^{2}d^{1-2\zeta}$
$\displaystyle\overset{(i)}{\leq}\frac{1}{64}L^{2}h^{2}d^{1-2\zeta}+\frac{1}{64}L^{3}h^{3}d^{1-2\zeta}+\frac{1}{256}Lhd^{1-2\zeta}+\frac{1}{512}L^{2}h^{2}d^{1-2\zeta}$
$\displaystyle=\left(\frac{1}{256}Lh+\frac{9}{512}L^{2}h^{2}+\frac{1}{64}L^{3}h^{3}\right)d^{1-2\zeta}$
(90)

with probability at least $1-\exp\left(-d^{1-4\zeta}/4096\right)$. Step $(i)$
uses the assumption (79).

  6. (6)

By Definition of $F_{1}$ (B.1), we have

$\displaystyle-Lh^{2}\left\|\nabla f_{P}(x)\right\|_{2}^{2}$
$\displaystyle=-\frac{L^{2}h^{2}}{4d^{2\zeta}}\sum_{i=1}^{d}\sin^{2}\left(d^{\zeta}L^{\frac{1}{2}}x_{[i]}\right)$
$\displaystyle=-\frac{L^{2}h^{2}}{8d^{2\zeta}}\sum_{i=1}^{d}\left(1-\cos\left(2d^{\zeta}L^{\frac{1}{2}}x_{[i]}\right)\right)$
$\displaystyle\leq-\frac{1}{8}L^{2}h^{2}d^{1-2\zeta}-\frac{1}{128}L^{2}h^{2}d^{1-4\zeta}+\frac{1}{64}L^{2}h^{2}d^{1-6\zeta}+\frac{1}{4}L^{2}h^{2}d^{\frac{1}{2}-2\zeta}$
$\displaystyle\leq-\frac{1}{8}L^{2}h^{2}d^{1-2\zeta}-\frac{1}{128}L^{2}h^{2}d^{1-4\zeta}+\frac{1}{512}L^{2}h^{2}d^{1-2\zeta}$
(91)

where the last step follows from the assumption (79).

  7. (7)

We decompose $\Delta_{7}$ into three parts.

$\displaystyle\left\|(1-Lh)\nabla f_{P}(x)+\nabla f_{P}(y)\right\|_{2}^{2}$
$\displaystyle=(1-Lh)^{2}\left\|\nabla
f_{P}(x)\right\|_{2}^{2}+2(1-Lh)\left\langle\nabla f_{P}(x),\nabla
f_{P}(y)\right\rangle$ $\displaystyle\quad+\left\|\nabla
f_{P}(y)\right\|_{2}^{2}$

Similar to previous analysis of $\left\|\nabla f_{P}(x)\right\|_{2}^{2}$, we
have

$\displaystyle-\left\|\nabla f_{P}(x)\right\|_{2}^{2}$
$\displaystyle=-\sum_{i=1}^{d}\frac{L}{4d^{2\zeta}}\sin^{2}(d^{\zeta}L^{\frac{1}{2}}x_{[i]})=-\sum_{i=1}^{d}\frac{L}{4d^{2\zeta}}\left(1-\cos(2d^{\zeta}L^{\frac{1}{2}}x_{[i]})\right)$
$\displaystyle\leq-\frac{1}{4}{Ld^{1-2\zeta}}-\frac{1}{64}Ld^{1-4\zeta}+\frac{1}{32}Ld^{1-6\zeta}+\frac{1}{2}Ld^{\frac{1}{2}-2\zeta}$
$\displaystyle\leq-\frac{1}{4}{Ld^{1-2\zeta}}-\frac{1}{64}Ld^{1-4\zeta}+\frac{1}{512}Ld^{1-2\zeta}.$
(92)

By Lemma 21 and the definition of $F_{1}$, we have

$\displaystyle\left\langle\nabla f_{P}(x),\nabla f_{P}(y)\right\rangle$
$\displaystyle=\sum_{i=1}^{d}\underbrace{\frac{L}{4d^{2\zeta}}\sin(d^{\zeta}L^{\frac{1}{2}}x_{[i]})\sin(d^{\zeta}L^{\frac{1}{2}}y_{[i]})}_{\Delta_{7,1,i}}$
$\displaystyle{\mathbb{E}}\left|\Delta_{7,1,i}\right|$
$\displaystyle\leq\frac{L^{\frac{3}{2}}}{4d^{\zeta}}\left|x_{[i]}\right|\exp\left(-Ld^{2\zeta}h\right)\leq
L\left(\log(8d)\right)^{\frac{1}{2}}{d^{-\zeta}}\exp\left(-Ld^{2\zeta}h\right)\leq\frac{1}{1024}Ld^{-2\zeta}$
$\displaystyle{\rm Var}[\Delta_{7,1,i}]$
$\displaystyle\leq\frac{L^{3}}{16d^{2\zeta}}x_{[i]}^{2}\leq
L^{2}d^{-2\zeta}\log(8d)$ $\displaystyle\left|\Delta_{7,1,i}\right|$
$\displaystyle\leq L\left(\log(8d)\right)^{\frac{1}{2}}{d^{-\zeta}}$

Applying Bernstein’s inequality (77) with $\epsilon=Ld^{1-2\zeta}/1024$, we
have

$\displaystyle{\mathbb{P}}\left[\left|\left\langle\nabla f_{P}(x),\nabla
f_{P}(y)\right\rangle\right|\geq\frac{1}{512}Ld^{1-2\zeta}\right]\leq\exp\left(-\frac{d^{1-4\zeta}}{16384}\right)$
(93)

Similarly, we have

$\displaystyle\left\|\nabla f_{P}(y)\right\|_{2}^{2}$
$\displaystyle=\sum_{i=1}^{d}\frac{L}{4d^{2\zeta}}\sin^{2}(d^{\zeta}L^{\frac{1}{2}}y_{[i]})=\sum_{i=1}^{d}\underbrace{\frac{L}{4d^{2\zeta}}\left(1-\cos(2d^{\zeta}L^{\frac{1}{2}}y_{[i]})\right)}_{\Delta_{7,2,i}}$
$\displaystyle\left|{\mathbb{E}}[\Delta_{7,2,i}]-\frac{L}{4d^{2\zeta}}\right|$
$\displaystyle\leq\frac{L}{4d^{2\zeta}}\exp\left(-2Lhd^{2\zeta}\right)\leq\frac{1}{128}Ld^{-4\zeta}$
$\displaystyle{\rm Var}[\Delta_{7,2,i}^{2}]$
$\displaystyle\leq\frac{L^{2}}{16d^{4\zeta}}$
$\displaystyle\left|\Delta_{7,2,i}\right|$
$\displaystyle\leq\frac{L}{4d^{2\zeta}}$

Applying Bernstein’s inequality (77) with $\epsilon={L}d^{1-4\zeta}/128$, we
have

$\displaystyle{\mathbb{P}}\left[\left\|\nabla
f_{P}(y)\right\|_{2}^{2}\geq\frac{1}{4}Ld^{1-2\zeta}+\frac{1}{64}Ld^{1-4\zeta}\right]\leq\exp\left(-\frac{d^{1-4\zeta}}{16384}\right)$
(94)

From these three estimates ((7)), (93) and (94), we have

$\displaystyle\Delta_{7}$ $\displaystyle=-\frac{h}{4}\left\|(1-Lh)\nabla
f_{P}(x)+\nabla f_{P}(y)\right\|_{2}^{2}$
$\displaystyle\leq-\frac{1}{16}Lh(1-Lh)^{2}d^{1-2\zeta}-\frac{1}{256}Lh(1-Lh)^{2}d^{1-4\zeta}+\frac{1}{2048}Lh(1-Lh)^{2}d^{1-2\zeta}$
$\displaystyle\quad+\frac{1}{1024}Lh\left(1+Lh\right)d^{1-2\zeta}-\frac{1}{16}Lhd^{1-2\zeta}+\frac{1}{256}Lhd^{1-4\zeta}$
$\displaystyle=\left(-\frac{253}{2048}Lh+\frac{1}{8}L^{2}h^{2}-\frac{127}{2048}L^{3}h^{3}\right)d^{1-2\zeta}+\left(\frac{1}{128}L^{2}h^{2}-\frac{1}{256}L^{3}h^{3}\right)d^{1-4\zeta}$
(95)

with probability at least $1-2\exp\left(-d^{1-4\zeta}/16384\right)$.

Finally, combining seven bounds in Equation (82), ((2)), ((3)), ((4)), ((5)),
((6)) and ((7)), we obtain

$\displaystyle\sum_{i=1}^{7}\Delta_{i}$
$\displaystyle\leq-\frac{1}{32}d^{1-4\zeta}+\frac{1}{2048}\left(-217Lh+136L^{2}h^{2}-75L^{3}h^{3}\right)d^{1-2\zeta}$
$\displaystyle\hskip
20.00003pt+\left(\frac{1}{32}Lh+\frac{1}{32}L^{2}h^{2}-\frac{1}{256}L^{3}h^{3}\right)d^{1-4\zeta}$
$\displaystyle\overset{(i)}{\leq}-\frac{1}{32}d^{1-4\zeta}-\frac{17}{512}(1-Lh)^{2}d^{1-2\zeta}$
$\displaystyle\leq-\frac{1}{32}d^{1-4\zeta}$ (96)

with probability at least $1-10\exp\left(-d^{1-4\zeta}/16384\right)$ for
$y\sim\mathcal{N}(x-h\nabla f(x),2h\mathbb{I}_{d})$. Step $(i)$ uses
$Lhd^{1-4\zeta}\leq d^{1-2\zeta}/32$ and
$L^{2}h^{2}d^{1-4\zeta}\leq\left(Lhd^{1-2\zeta}+L^{3}h^{3}d^{1-2\zeta}\right)/64$
by the assumption (79), and throws all the other negative terms.

###  B.2 Proof of Lemma 15

We calculate the integral explicitly as follows.

$\displaystyle\int\frac{\pi_{2}(y)Q_{2}(y,x)}{\pi_{2}(x)}dy$
$\displaystyle=\int\frac{1}{\sqrt{4\pi
h}}\exp\left(\frac{m}{2}(x^{2}-y^{2})\right)\exp\left(-\frac{1}{4h}(x-(1-mh)y)^{2}\right)dy$
$\displaystyle=\frac{1}{\sqrt{1+m^{2}h^{2}}}\exp\left(\frac{m^{3}h^{2}x^{2}}{2(1+m^{2}h^{2})}\right)$
$\displaystyle\quad\cdot\int\sqrt{\frac{1+m^{2}h^{2}}{4\pi
h}}\exp\left(-\frac{1+m^{2}h^{2}}{4h}\big{(}y-\frac{1-mh}{1+m^{2}h^{2}}x\big{)}^{2}\right)dy$
$\displaystyle=\frac{1}{\sqrt{1+m^{2}h^{2}}}\exp\left(\frac{m^{3}h^{2}x^{2}}{2(1+m^{2}h^{2})}\right).$

Take $F_{2}=\left\\{x:x\in(-1/{\sqrt{m}},1/{\sqrt{m}})\right\\}$, then
$\pi_{2}(F_{2})\in(1/2,3/4)$. We have

$\displaystyle\int\frac{\pi_{2}(y)Q_{2}(y,x)}{\pi_{2}(x)}dy\leq\exp\Big{(}\frac{m}{2}x^{2}\Big{)}\leq
2,\ \ \forall x\in F_{2}.$ (97)

## References

  * Andrieu et al. (2003) C. Andrieu, N. De Freitas, A. Doucet, and M. I. Jordan.  An introduction to MCMC for machine learning.  _Machine learning_ , 50(1):5–43, 2003.
  * Bakry et al. (2014) D. Bakry, I. Gentil, and M. Ledoux.  _Analysis and geometry of Markov diffusion operators_ , volume 103\.  Springer, 2014.
  * Besag (1994) J. Besag.  Comments on “Representations of knowledge in complex systems” by U. Grenander and MI Miller.  _J. Roy. Statist. Soc. Ser. B_ , 56:591–592, 1994.
  * Borgs (2003) C. Borgs.  Statistical physics expansion methods in combinatorics and computer science.  _CBMS lecture notes (in preparation)_ , 2003.
  * Bou-Rabee and Hairer (2013) N. Bou-Rabee and M. Hairer.  Nonasymptotic mixing of the MALA algorithm.  _IMA Journal of Numerical Analysis_ , 33(1):80–110, 2013.
  * Bühlmann and Van De Geer (2011) P. Bühlmann and S. Van De Geer.  _Statistics for high-dimensional data: methods, theory and applications_.  Springer Science & Business Media, 2011.
  * Carpenter et al. (2017) B. Carpenter, A. Gelman, M. D. Hoffman, D. Lee, B. Goodrich, M. Betancourt, M. A. Brubaker, J. Guo, P. Li, and A. Riddell.  Stan: a probabilistic programming language.  _Grantee Submission_ , 76(1):1–32, 2017.
  * Chen et al. (2020) Y. Chen, R. Dwivedi, M. J. Wainwright, and B. Yu.  Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients.  _Journal of Machine Learning Research_ , 21(92):1–71, 2020.
  * Cheng and Bartlett (2018) X. Cheng and P. Bartlett.  Convergence of Langevin MCMC in KL-divergence.  _Proceedings of Machine Learning Research, Volume 83: Algorithmic Learning Theory_ , pages 186–211, 2018.
  * Cheng et al. (2018a) X. Cheng, N. S. Chatterji, Y. Abbasi-Yadkori, P. L. Bartlett, and M. I. Jordan.  Convergence rates for Langevin dynamics in the nonconvex setting.  _arXiv preprint arXiv:1805.01648_ , 2018a.
  * Cheng et al. (2018b) X. Cheng, N. S. Chatterji, P. L. Bartlett, and M. I. Jordan.  Underdamped Langevin MCMC: A non-asymptotic analysis.  In _Conference on Learning Theory_ , pages 300–323. PMLR, 2018b.
  * Chewi et al. (2021) S. Chewi, C. Lu, K. Ahn, X. Cheng, T. Le Gouic, and P. Rigollet.  Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm.  In _Conference on Learning Theory_ , pages 1260–1300. PMLR, 2021\.
  * Coulhon (1996) T. Coulhon.  Ultracontractivity and nash type inequalities.  _Journal of functional analysis_ , 141(2):510–539, 1996.
  * Coulhon and Grigor’yan (1997) T. Coulhon and A. Grigor’yan.  On-diagonal lower bounds for heat kernels and markov chains.  _Duke Mathematical Journal_ , 89(1):133–199, 1997\.
  * Coulhon et al. (2001) T. Coulhon, A. Grigor’yan, and C. Pittet.  A geometric approach to on-diagonal heat kernel lower bounds on groups.  In _Annales de l’institut Fourier_ , volume 51, pages 1763–1827, 2001\.
  * Cousins and Vempala (2014) B. Cousins and S. Vempala.  A cubic algorithm for computing Gaussian volume.  In _Proceedings of the twenty-fifth annual ACM-SIAM symposium on discrete algorithms_ , pages 1215–1228. SIAM, 2014.
  * Dalalyan (2017) A. S. Dalalyan.  Theoretical guarantees for approximate sampling from smooth and log-concave densities.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 79(3):651–676, 2017.
  * Dalalyan and Riou-Durand (2020) A. S. Dalalyan and L. Riou-Durand.  On sampling from a log-concave density using kinetic Langevin diffusions.  _Bernoulli_ , 26(3):1956–1988, 2020.
  * Diaconis and Saloff-Coste (1996) P. Diaconis and L. Saloff-Coste.  Logarithmic Sobolev inequalities for finite Markov chains.  _The Annals of Applied Probability_ , 6(3):695–750, 1996.
  * Durmus and Moulines (2017) A. Durmus and E. Moulines.  Nonasymptotic convergence analysis for the unadjusted Langevin algorithm.  _The Annals of Applied Probability_ , 27(3):1551–1587, 2017.
  * Durmus and Moulines (2019) A. Durmus and E. Moulines.  High-dimensional Bayesian inference via the unadjusted Langevin algorithm.  _Bernoulli_ , 25(4A):2854–2882, 2019.
  * Dwivedi et al. (2019) R. Dwivedi, Y. Chen, M. J. Wainwright, and B. Yu.  Log-concave sampling: Metropolis-hastings algorithms are fast.  _Journal of Machine Learning Research_ , 20(183):1–42, 2019.
  * Eberle et al. (2019) A. Eberle, A. Guillin, and R. Zimmer.  Couplings and quantitative contraction rates for Langevin dynamics.  _The Annals of Probability_ , 47(4):1982–2010, 2019.
  * Erdogdu et al. (2021) M. A. Erdogdu, R. Hosseinzadeh, and M. S. Zhang.  Convergence of Langevin Monte Carlo in Chi-Squared and Renyi divergence, 2021.
  * Goel et al. (2006) S. Goel, R. Montenegro, P. Tetali, et al.  Mixing time bounds via the spectral profile.  _Electronic Journal of Probability_ , 11:1–26, 2006.
  * Grenander and Miller (1994) U. Grenander and M. I. Miller.  Representations of knowledge in complex systems.  _Journal of the Royal Statistical Society: Series B (Methodological)_ , 56(4):549–581, 1994.
  * Hastings (1970) W. K. Hastings.  Monte carlo sampling methods using markov chains and their applications.  _Biometrika_ , 57(1):97–109, 1970.
  * Laurent and Massart (2000) B. Laurent and P. Massart.  Adaptive estimation of a quadratic functional by model selection.  _Annals of Statistics_ , pages 1302–1338, 2000.
  * Ledoux (2001) M. Ledoux.  _The concentration of measure phenomenon_ , volume 89.  American Mathematical Soc., 2001.
  * Lee et al. (2020) Y. T. Lee, R. Shen, and K. Tian.  Logsmooth gradient concentration and tighter runtimes for Metropolized Hamiltonian Monte Carlo.  In _Conference on Learning Theory_ , pages 2565–2597. PMLR, 2020\.
  * Lee et al. (2021a) Y. T. Lee, R. Shen, and K. Tian.  Lower bounds on Metropolized sampling methods for well-conditioned distributions.  _arXiv preprint arXiv:2106.05480_ , 2021a.
  * Lee et al. (2021b) Y. T. Lee, R. Shen, and K. Tian.  Structured logconcave sampling with a restricted gaussian oracle.  In _Conference on Learning Theory_ , pages 2993–3050. PMLR, 2021b.
  * Levin and Peres (2017) D. A. Levin and Y. Peres.  _Markov chains and mixing times_ , volume 107.  American Mathematical Soc., 2017.
  * Li et al. (2020) R. Li, H. Zha, and M. Tao.  Hessian-free high-resolution Nesterov acceleration for sampling.  _arXiv e-prints_ , pages arXiv–2006, 2020.
  * Lovász and Simonovits (1993) L. Lovász and M. Simonovits.  Random walks in a convex body and an improved volume algorithm.  _Random structures & algorithms_, 4(4):359–412, 1993.
  * Ma et al. (2021) Y.-A. Ma, N. S. Chatterji, X. Cheng, N. Flammarion, P. L. Bartlett, and M. I. Jordan.  Is there an analog of Nesterov acceleration for gradient-based MCMC?  _Bernoulli_ , 27(3):1942–1992, 2021.
  * Mangoubi and Vishnoi (2019) O. Mangoubi and N. K. Vishnoi.  Nonconvex sampling with the Metropolis-Adjusted Langevin Algorithm.  In _Conference on Learning Theory_ , pages 2259–2293. PMLR, 2019\.
  * Mengersen et al. (1996) K. L. Mengersen, R. L. Tweedie, et al.  Rates of convergence of the Hastings and Metropolis algorithms.  _Annals of Statistics_ , 24(1):101–121, 1996\.
  * Metropolis et al. (1953) N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller.  Equation of state calculations by fast computing machines.  _The journal of chemical physics_ , 21(6):1087–1092, 1953.
  * Meyn and Tweedie (2012) S. P. Meyn and R. L. Tweedie.  _Markov chains and stochastic stability_.  Springer Science & Business Media, 2012.
  * Montenegro (2006) R. Montenegro.  Eigenvalues of non-reversible Markov chains: Their connection to mixing times, reversible Markov chains, and Cheeger inequalities.  _arXiv preprint math/0604362_ , 2006.
  * Montenegro and Tetali (2006) R. R. Montenegro and P. Tetali.  _Mathematical aspects of mixing times in Markov chains_.  Now Publishers Inc, 2006.
  * Mortici (2011) C. Mortici.  Improved asymptotic formulas for the Gamma function.  _Computers & Mathematics with Applications_, 61(11):3364–3369, 2011.
  * Mou et al. (2021) W. Mou, Y.-A. Ma, M. J. Wainwright, P. L. Bartlett, and M. I. Jordan.  High-order Langevin diffusion yields an accelerated MCMC algorithm.  _Journal of Machine Learning Research_ , 22:42–1, 2021\.
  * Neal et al. (2011) R. M. Neal et al.  MCMC using Hamiltonian dynamics.  _Handbook of Markov Chain Monte Carlo_ , 2(11):2, 2011.
  * Nemirovskij and Yudin (1983) A. S. Nemirovskij and D. B. Yudin.  _Problem complexity and method efficiency in optimization_.  Wiley-Interscience, 1983.
  * Nesterov (2003) Y. Nesterov.  _Introductory lectures on convex optimization: A basic course_ , volume 87.  Springer Science & Business Media, 2003.
  * Parisi (1981) G. Parisi.  Correlation functions and computer simulations.  _Nuclear Physics B_ , 180(3):378–384, 1981.
  * Plummer et al. (2003) M. Plummer et al.  JAGS: A program for analysis of Bayesian graphical models using Gibbs sampling.  In _Proceedings of the 3rd international workshop on distributed statistical computing_ , volume 124, pages 1–10. Vienna, Austria., 2003.
  * Robert and Casella (2013) C. Robert and G. Casella.  _Monte Carlo statistical methods_.  Springer Science & Business Media, 2013.
  * Roberts and Rosenthal (1998) G. O. Roberts and J. S. Rosenthal.  Optimal scaling of discrete approximations to Langevin diffusions.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 60(1):255–268, 1998.
  * Roberts and Stramer (2002) G. O. Roberts and O. Stramer.  Langevin diffusions and Metropolis-Hastings algorithms.  _Methodology and computing in applied probability_ , 4(4):337–357, 2002.
  * Roberts and Tweedie (1996a) G. O. Roberts and R. L. Tweedie.  Exponential convergence of Langevin distributions and their discrete approximations.  _Bernoulli_ , pages 341–363, 1996a.
  * Roberts and Tweedie (1996b) G. O. Roberts and R. L. Tweedie.  Geometric convergence and central limit theorems for multidimensional Hastings and Metropolis algorithms.  _Biometrika_ , 83(1):95–110, 1996b.
  * Schmidler and Woodard (2011) S. Schmidler and D. B. Woodard.  Lower bounds on the convergence rates of adaptive MCMC methods, 2011\.
  * Sinclair and Jerrum (1989) A. Sinclair and M. Jerrum.  Approximate counting, uniform generation and rapidly mixing Markov chains.  _Information and Computation_ , 82(1):93–133, 1989.
  * Wainwright (2019) M. J. Wainwright.  _High-dimensional statistics: A non-asymptotic viewpoint_ , volume 48.  Cambridge University Press, 2019.
  * Wilson (2004) D. B. Wilson.  Mixing times of lozenge tiling and card shuffling Markov chains.  _The Annals of Applied Probability_ , 14(1):274–325, 2004.
  * Woodard et al. (2009) D. Woodard, S. Schmidler, and M. Huber.  Sufficient conditions for torpid mixing of parallel and simulated tempering.  _Electronic Journal of Probability_ , 14:780–804, 2009\.