$\nabla f(\gamma_{t})$ belongs to
$\nabla_{p}\bar{\mathcal{H}}(\gamma_{t},\mathcal{X})$. Therefore, as in the
proof of Lemma D.3, invoking the implicit function theorem on the equation

$\nabla_{p}\bar{\mathcal{H}}(x,p)=\nabla f(x)+v$ (D.2.41)

we obtain that there exists $\delta(\gamma_{t})>0$,
$p\colon\mathbb{B}(\gamma_{t},\delta(\gamma_{t}))\times\mathbb{B}(0,\delta(\gamma_{t}))\to\mathcal{X}$
such that,

$\nabla_{p}\bar{\mathcal{H}}(x,p(x,v))=\nabla f(x)+v\,,$ (D.2.42)

or, equivalently

$\nabla_{p}\mathcal{H}(x,p(x,v))=v\,.$ (D.2.43)

Therefore, as in the proof of Lemma D.3, we obtain that $\mathcal{L}$ is
continuous on
$\overline{\mathbb{B}}(\gamma_{t},\delta(\gamma_{t})/2)\times\overline{\mathbb{B}}(0,\delta(\gamma_{t})/2)$
and therefore bounded by $M(\gamma_{t})>0$. Since $\gamma$ is continuous,
$\left\\{\gamma_{t}:t\in[0,T]\right\\}$ is compact and therefore, by
extracting a finite covering from

$\bigcup_{t\in[0,T]}\mathbb{B}(\gamma_{t},\delta(\gamma_{t})/2)\,,$ (D.2.44)

we obtain that there exists $\delta>0$ and $M>0$ such that, for every
$t\in[0,T]$, $\mathcal{L}(\gamma_{t},\cdot)$ is finite and bounded by $M$ on
$\mathbb{B}(\gamma_{t},\delta)$. Choosing a $\varphi$ reparametrization of
$\gamma$, which is $\mathcal{C}^{1}$, such that
$\lVert\dot{\varphi}_{t}\rVert<\delta$ for every $t\in[0,S]$, we thus obtain a
path such that

$\mathcal{S}_{0,S}(\varphi)=\int_{0}^{T}alt\mathcal{L}(\varphi_{t},\dot{\varphi}_{t})\>dt\leq
MS<\infty\,,$ (D.2.45)

which implies that $B(x,x^{\prime})<\infty$. ∎

###  D.3. Lyapunov condition

######  Definition 5 (Stopping times for the accelerated process).

For any set $S\subset\mathcal{X}$, we define the hitting and exit times of
$S$:

$\displaystyle\sigma_{S}$ $\displaystyle\coloneqq\inf\\{n\geq
1:x^{\eta}_{n}\in S\\}$ (D.3.1a) $\displaystyle\tau_{S}$
$\displaystyle\coloneqq\inf\\{n\geq 0:x^{\eta}_{n}\notin S\\}\,.$ (D.3.1b)

We will need the following concentration lemma and its corollary.

######  Lemma D.13 (Part of the proof of [60, Th. 1.19]).

Let $X$ be a random variable in $\mathbb{R}^{d}$ such that, for all
$v\in\mathbb{R}^{d}$,

$\log\operatorname{\mathbb{E}}\left[\exp\left(\langle
v,X\rangle\right)\right]\leq\frac{\lVert v\rVert^{2}}{2}\,.$ (D.3.2)

Then, for all $t>0$, we have

$\operatorname{\mathbb{P}}\left(\lVert X\rVert^{2}\geq t\right)\leq
6^{d}\exp\left(-\frac{t}{8}\right)\,.$ (D.3.3)

######  Corollary D.2.

In the context of Lemma D.13, it holds that

$\operatorname{\mathbb{E}}\left[\lVert X\rVert^{2}\right]\leq 16d\log 6\,.$
(D.3.4)

###### Proof.

Since $\lVert X\rVert^{2}$ is non-negative, its expectation can be written as

$\displaystyle\operatorname{\mathbb{E}}\left[\lVert X\rVert^{2}\right]$
$\displaystyle=\int_{0}^{+\infty}\operatorname{\mathbb{P}}\left(\lVert
X\rVert^{2}>t\right)\>dt$ $\displaystyle\leq 8d\log 6+\int_{8d\log
6}^{+\infty}\operatorname{\mathbb{P}}\left(\lVert X\rVert^{2}>t\right)\>dt\,.$
(D.3.5)

Invoking Lemma D.13 then yields that

$\operatorname{\mathbb{E}}\left[\lVert X\rVert^{2}\right]\leq 8d\log
6+6^{d}\int_{8d\log 6}^{+\infty}\exp\left(-\frac{t}{8}\right)\>dt\leq 8d\log
6+8\,,$ (D.3.6)

which concludes the proof since $1\leq d\log 6$. ∎

######  Lemma D.14 (Lyapunov condition).

Define $U_{\infty}$ as in Lemma D.6. Then, there exists
$\mathcal{K}\subset\mathcal{X}$ compact, $\eta_{0}>0$, $c>0$ such that, for
any $\eta\leq\eta_{0}$, $n\geq 0$, if $x_{n}\notin\mathcal{K}$, then, almost
surely,

$\displaystyle U_{\infty}(x_{n+1})-U_{\infty}(x_{n})$
$\displaystyle\leq\eta\left(\frac{\lVert\mathsf{U}(x_{n},\omega_{n})\rVert^{2}}{\sigma_{\infty}^{2}(f(x_{n}))}-\frac{\lVert\nabla
f(x_{n})\rVert^{2}}{\sigma_{\infty}^{2}(f(x_{n}))}\right)$
$\displaystyle\leq\eta\left(\frac{\lVert\mathsf{U}(x_{n},\omega_{n})\rVert^{2}}{\sigma_{\infty}^{2}(f(x_{n}))}-(16d\log
6+c)\right)\,.$ (D.3.7)

###### Proof.

By Assumption 3∗∗, there is $R\geq{\frac{1}{2}}$, $c>0$ such that, for any
$x\in\mathcal{X}$ such that $\lVert x\rVert\geq R$,

$\begin{cases}f(x)\geq c\\\ c\leq\frac{\sigma_{\infty}^{2}(f(x))}{\lVert
x\rVert^{s}}\leq c^{-1}\\\ \frac{\lVert\nabla
f(x)\rVert^{2}}{\sigma_{\infty}^{2}(f(x))}\geq 16d\log 6+c\,.\end{cases}$
(D.3.8)

Then, define $\mathcal{K}\coloneqq\overline{\mathbb{B}}(0,2R+1)$.

By definition, $U_{\infty}$ is twice continuously differentiable and, its
Hessian satisfies, for any $x\in\mathcal{X}$,

$\operatorname{Hess}U_{\infty}(x)\preccurlyeq\frac{2\operatorname{Hess}f(x)}{\sigma_{\infty}^{2}(f(x))}\preccurlyeq\frac{2\beta(f)}{\sigma_{\infty}^{2}(f(x))}I\,.$
(D.3.9)

For the sake of clarity, for any $n\geq 0$, denote by $\delta x_{n}$ the
quantity

$\delta x_{n}=\frac{x_{n+1}-x_{n}}{\eta}\,.$ (D.3.10)

For any $n\geq 0$, we now have

$\displaystyle U_{\infty}(x_{n+1})-U_{\infty}(x_{n})$
$\displaystyle\leq\eta\langle\nabla U_{\infty}(x_{n}),\delta x_{n}\rangle$
$\displaystyle+\frac{\eta^{2}}{2}\lVert\delta
x_{n}\rVert^{2}\sup_{t\in[0,1]}\frac{2\beta(f)}{\sigma_{\infty}^{2}(f(x_{n}+t(x_{n+1}-x_{n})))}\,.$
(D.3.11)

We first focus on bounding the last term. First note that, by the blanket
assumptions, $\lVert x_{n+1}-x_{n}\rVert\leq 2\eta M(1+\lVert x_{n}\rVert)$ so
that, For any $t\in[0,1]$, $\eta\leq(4M)^{-1}$,

$\displaystyle\lVert x_{n}+t(x_{n+1}-x_{n})\rVert$ $\displaystyle\geq\lVert
x_{n}\rVert-\lVert x_{n+1}-x_{n}\rVert$ $\displaystyle\geq\lVert
x_{n}\rVert-2\eta M(1+\lVert x_{n}\rVert)$
$\displaystyle\geq{\frac{1}{2}}(\lVert x_{n}\rVert-1)\,.$ (D.3.12)

If $x_{n}$ is outside of $\mathcal{K}$, we have that $\lVert x_{n}\rVert\geq
2R+1$ and thus $\lVert x_{n}+t(x_{n+1}-x_{n})\rVert\geq R$. Moreover, since
$R\geq{\frac{1}{2}}$, $x_{n}$ being outside of $\mathcal{K}$ also implies that
${\frac{1}{2}}\lVert x_{n}\rVert\geq 1$ and so $\lVert
x_{n}+t(x_{n+1}-x_{n})\rVert\geq\tfrac{1}{4}\lVert x_{n}\rVert$. By the
definition of $R$, we thus have

$\displaystyle\sigma_{\infty}^{2}(f(x_{n}+t(x_{n+1}-x_{n})))$
$\displaystyle\geq c\lVert x_{n}+t(x_{n+1}-x_{n})\rVert^{s}$
$\displaystyle\geq c\left(\frac{1}{4}\right)^{s}\lVert x_{n}\rVert^{s}$
$\displaystyle\geq\frac{c^{2}}{4^{s}}\sigma_{\infty}^{2}(f(x_{n}))\,.$
(D.3.13)

Thus, if $x_{n}\notin\mathcal{K}$, Eq. D.3.9 yields that

$U_{\infty}(x_{n+1})-U_{\infty}(x_{n})\leq\eta\langle\nabla
U_{\infty}(x_{n}),\delta
x_{n}\rangle+\eta^{2}\frac{4^{s}\beta(f)}{c^{2}\sigma_{\infty}^{2}(f(x_{n}))}\lVert\delta
x_{n}\rVert^{2}\,.$ (D.3.14)

Now, we can rewrite the inner product as

$\displaystyle\langle\nabla U_{\infty}(x_{n}),\delta x_{n}\rangle$
$\displaystyle=\frac{2\langle\nabla f(x_{n}),\delta x_{n}\rangle
missing}{\sigma_{\infty}^{2}(f(x_{n}))}$ $\displaystyle=\frac{\lVert\delta
x_{n}+\nabla
f(x_{n})\rVert^{2}}{\sigma_{\infty}^{2}(f(x_{n}))}-\frac{\lVert\nabla
f(x_{n})\rVert^{2}}{\sigma_{\infty}^{2}(f(x_{n}))}-\frac{\lVert\delta
x_{n}\rVert^{2}}{\sigma_{\infty}^{2}(f(x_{n}))}\,.$ (D.3.15)

Plugging this into Eq. D.3.14 and assuming that
$\eta\leq\frac{c^{2}}{4^{s}\beta(f)}$, we obtain

$\displaystyle U_{\infty}(x_{n+1})-U_{\infty}(x_{n})$
$\displaystyle\leq\eta\left(\frac{\lVert\delta x_{n}+\nabla
f(x_{n})\rVert^{2}}{\sigma_{\infty}^{2}(f(x_{n}))}-\frac{\lVert\nabla
f(x_{n})\rVert^{2}}{\sigma_{\infty}^{2}(f(x_{n}))}\right)$
$\displaystyle\leq\eta\left(\frac{\lVert\mathsf{U}(x_{n},\omega_{n})\rVert^{2}}{\sigma_{\infty}^{2}(f(x_{n}))}-\frac{\lVert\nabla
f(x_{n})\rVert^{2}}{\sigma_{\infty}^{2}(f(x_{n}))}\right)$ (D.3.16)

where we unrolled $\delta x_{n}$ in the last inequality. Using again that
$x_{n}\notin\mathcal{K}$, we obtain

$U_{\infty}(x_{n+1})-U_{\infty}(x_{n})\leq\eta\left(\frac{\lVert\mathsf{U}(x_{n},\omega_{n})\rVert^{2}}{\sigma_{\infty}^{2}(f(x_{n}))}-(16d\log
6+c)\right)$ (D.3.17)

which concludes the proof. ∎

We will reuse, in later sections, the following fact that we thus state as a
lemma: the sequence of iterates of SGD is _(weak) Feller_ (see e.g., [24, Def.
4.4.2]).

######  Lemma D.15.

The Markov chain $(x_{n})_{n\geq 0}$ is (weak) Feller.

###### Proof.

since both $\nabla f$ and $\mathsf{U}$ are continuous, for any
$g\colon\mathcal{X}\to\mathbb{R}$ continuous and bounded, the function.

$x\in\mathcal{X}\longmapsto\operatorname{\mathbb{E}}_{x}\left[g\left(x_{1}\right)\right]=\operatorname{\mathbb{E}}_{x}\left[g\left(x-\eta\nabla
f(x)+\eta\mathsf{U}(x,\omega)\right)\right]$ (D.3.18)

is still continuous and bounded. Therefore, the Markov chain $(x_{n})_{n\geq
0}$ is weak-Feller. ∎

######  Lemma D.16.

There is $\eta_{0}>0$ such that, for any $\eta\leq\eta_{0}$, there exists an
invariant probability measure for $(x_{n})_{n\geq 0}$.

###### Proof.

We invoke a general result on weak-Feller Markov chains that satisfy a
Lyapunov condition, e.g., Hernández-Lerma & Lasserre [24, Thm. 7.2.4] or Douc
et al. [14, Thm. 12.3.6].

First, Lemma D.15 ensures that $(x_{n})_{n\geq 0}$ is weak-Feller.

Moreover, by Lemma D.14, there exists $\mathcal{K}\subset\mathcal{X}$ compact,
$\eta_{0}>0$, $c>0$ such that, for any $\eta\leq\eta_{0}$,
$x_{0}=x\notin\mathcal{K}$,

$U_{\infty}(x_{1})-U_{\infty}(x)\leq\eta\left(\frac{\lVert\mathsf{U}(x,\omega_{0})\rVert^{2}}{\sigma_{\infty}^{2}(f(x))}-(16d\log
6+c)\right)\,.$ (D.3.19)

Passing to the expectation yields that, for any $x\notin\mathcal{K}$,

$\operatorname{\mathbb{E}}_{x}\left[U_{\infty}(x_{1})\right]-{U_{\infty}(x)}\leq\eta\left(\frac{\operatorname{\mathbb{E}}_{x}\left[\lVert\mathsf{U}(x,\omega_{0})\rVert^{2}\right]}{\sigma_{\infty}^{2}(f(x))}-(16d\log
6+c)\right)\,.$ (D.3.20)

Appplying Corollary D.2 with
$X\leftarrow\frac{\mathsf{U}(x,\omega_{0})}{\sqrt{\sigma_{\infty}^{2}(f(x))}}$
(the conditions of application are verified from Assumption 2∗Item (c.5pt))
yields that

$\operatorname{\mathbb{E}}_{x}\left[U_{\infty}(x_{1})\right]-{U_{\infty}(x)}\leq-\eta
c\,.$ (D.3.21)

Hence, for any $x\in\mathcal{X}$, it holds

$\operatorname{\mathbb{E}}_{x}\left[U_{\infty}(x_{1})\right]-{U_{\infty}(x)}\leq-\eta
c+\operatorname{\mathds{1}}\\{x\in\mathcal{K}\\}\left(\sup_{x^{\prime}\in\mathcal{K}}\operatorname{\mathbb{E}}_{x^{\prime}}[U_{\infty}(x^{\prime})]-\inf_{\mathcal{X}}U_{\infty}+\eta
c\right)\,,$ (D.3.22)

with $U_{\infty}$ which is not identically equal to its minimum since $f$ is
coercive.

Therefore, we can apply Hernández-Lerma & Lasserre [24, Thm. 7.2.4] with
$U_{\infty}-\inf_{\mathcal{X}}U_{\infty}$, that guarantees that there exists
an invariant probability measure for $(x_{n})_{n\geq 0}$. ∎

######  Lemma D.17.

There exists a compact set $\mathcal{D}\subset\mathcal{X}$, $\eta_{0}>0$, such
that for any compact set $\mathcal{D}^{\prime}\subset\mathcal{X}$ such that
$\mathcal{D}\subset\mathcal{D}^{\prime}$, there exists $a,b>0$, such that

$\forall\eta\leq\eta_{0}\,,\,x\in\mathcal{D}^{\prime}\setminus\mathcal{D}\,,\,n\geq
0\,,\,\operatorname{\mathbb{P}}_{x}\left(\sigma_{\mathcal{D}}>n\right)\leq\exp\left(-\frac{an}{\eta}+\frac{b}{\eta}\right)\,.$
(D.3.23)

###### Proof.

This result is a consequence of Lemma D.14: there exists
$\mathcal{K}\subset\mathcal{X}$ compact, $\eta_{0}>0$, $c>0$ such that, for
any $\eta\leq\eta_{0}$, $n\geq 0$, if $x_{n}\notin\mathcal{K}$, then, almost
surely,

$U_{\infty}(x_{n+1})-U_{\infty}(x_{n})\leq\eta\left(\frac{\lVert\mathsf{U}(x_{n},\omega_{n})\rVert^{2}}{\sigma_{\infty}^{2}(f(x_{n}))}-(16d\log
6+c)\right)\,.$ (D.3.24)

First, let us choose $\mathcal{D}$. There is some $R>0$ such that
$\mathcal{K}\subset\mathbb{B}(0,R)$. Define $\widetilde{R}\coloneqq
e^{4M+1}(R+1)$ and
$\mathcal{D}\coloneqq\overline{\mathbb{B}}(0,\widetilde{R})$. With
$\eta\leq(4M)^{-1}$, if, for some $n\geq 0$, $x_{n}$ is not in $\mathcal{D}$,
by Lemma B.3, for any $k\leq\lceil\eta^{-1}\rceil$, $x_{n+k}$ has norm greater
or equal to $R$ and thus $x_{n+k}$ is not in $\mathcal{K}$ either.

Now, fix $N\geq 0$ and consider the event
$\left\\{\sigma_{\mathcal{D}}>N\right\\}$ with
$x_{0}=x\in\mathcal{D}^{\prime}\setminus\mathcal{D}$. This means that, for any
$0\leq n\leq N$, $x^{\eta}_{n}$ is outside of $\mathcal{D}$ and so, for any
$0\leq n\leq N\lfloor\eta^{-1}\rfloor$, $x_{n}$ is not in $\mathcal{K}$.

Summing Eq. D.3.24 over $n=0,\dots,N\lfloor\eta^{-1}\rfloor-1$ yields

$\displaystyle U_{\infty}(x^{\eta}_{N})-U_{\infty}(x_{0})$
$\displaystyle=U_{\infty}(x_{N\lfloor\eta^{-1}\rfloor})-U_{\infty}(x_{0})$
$\displaystyle\leq\eta\sum_{n=0}^{N\lfloor\eta^{-1}\rfloor-1}\left(\frac{\lVert\mathsf{U}(x_{n},\omega_{n})\rVert^{2}}{\sigma_{\infty}^{2}(f(x_{n}))}-(16d\log
6+c)\right)\,.$ (D.3.25)

Define
$\Delta\coloneqq\sup_{\mathcal{D}^{\prime}\setminus\mathcal{D}}U_{\infty}-\inf_{\mathcal{X}\setminus\mathcal{D}}U_{\infty}$
which is finite since $f$ is coercive. By definition, we have that
$U_{\infty}(x^{\eta}_{N})-U_{\infty}(x_{0})\geq-\Delta$.

Therefore, on the event $\left\\{\sigma_{\mathcal{D}}>N\right\\}$, we have

$\sum_{n=0}^{N\lfloor\eta^{-1}\rfloor-1}{\frac{\lVert\mathsf{U}(x_{n},\omega_{n})\rVert^{2}}{\sigma_{\infty}^{2}\circ
f(x_{n})}}\geq N\lfloor\eta^{-1}\rfloor(16d\log 6+c)-\frac{\Delta}{\eta}\,.$
(D.3.26)

Now, on the whole event, consider the random variable
$X\in\mathbb{R}^{N\lfloor\eta^{-1}\rfloor d}$ defined by

$(X_{nd}+1,\dots,X_{(n+1)d})=\frac{\mathsf{U}(x_{n},\omega_{n})}{\sqrt{\sigma_{\infty}^{2}\circ
f(x_{n})}}\quad\text{ for }n=0,\dots,N\lfloor\eta^{-1}\rfloor-1\,,$ (D.3.27)

we have that
$\operatorname{\mathbb{P}}_{\\!#1}\left(\sigma_{\mathcal{D}}>N\right)\leq\operatorname{\mathbb{P}}_{\\!#1}\left(\lVert
X\rVert^{2}\geq N\lfloor\eta^{-1}\rfloor(16d\log
6+c)-\frac{\Delta}{\eta}\right)$.

Since, for any $v\in\mathbb{R}^{d}$,

$\log\operatorname{\mathbb{E}}\left[\exp\left(\left\langle
v,\frac{\mathsf{U}(x_{n},\omega_{n})}{\sqrt{\sigma_{\infty}^{2}\circ
f(x_{n})}}\right\rangle\right)\nonscript\,\middle|\nonscript\,\mathopen{}x_{0},x_{1},\dots,x_{n}\right]\leq\frac{\lVert
v\rVert^{2}}{2}\,,$ (D.3.28)

the random variable $X$ satisfies the assumptions of Lemma D.13 with
$d\leftarrow N\lfloor\eta^{-1}\rfloor d$.

First, suppose that $t\coloneqq N\lfloor\eta^{-1}\rfloor(16d\log
6+c)-\frac{\Delta}{\eta}$ is non-negative. Applying Lemma D.13 with this $t$
yields that

$\displaystyle\operatorname{\mathbb{P}}_{\\!#1}\left(\sigma_{\mathcal{D}}>N\right)$
$\displaystyle\leq\operatorname{\mathbb{P}}_{\\!#1}\left(\lVert
X\rVert^{2}\geq N\lfloor\eta^{-1}\rfloor(16d\log
6+c)-\frac{\Delta}{\eta}\right)$ $\displaystyle\leq
6^{N\lfloor\eta^{-1}\rfloor
d}\exp\left(-\frac{N\lfloor\eta^{-1}\rfloor(16d\log
6+c)-\frac{\Delta}{\eta}}{8}\right)$
$\displaystyle=\exp\left(-\frac{N\lfloor\eta^{-1}\rfloor(8d\log
6+c)-\frac{\Delta}{\eta}}{8}\right)\,.$ (D.3.29)

If $t$, defined above, is negative, then in particular
$\frac{\Delta}{\eta}\geq N\lfloor\eta^{-1}\rfloor c$ so that this bounds still
(trivially) holds.

Finally, in particular, for $\eta\leq 1/2$,
$\lfloor\eta^{-1}\rfloor\geq(2\eta)^{-1}$ so we obtain

$\operatorname{\mathbb{P}}_{\\!#1}\left(\sigma_{\mathcal{D}}>N\right)\leq\exp\left(-\frac{N(8d\log
6+c)}{16\eta}+\frac{\Delta}{8\eta}\right)$ (D.3.30)

and our proof is complete. ∎

###  D.4. Preliminary estimates and lemmas

We will use the following lemma, which corresponds to Kifer [35, Lem. 5.3].

######  Lemma D.18.

Let $\mathcal{K}\subset\mathcal{X}$ be a compact set such that
$\mathcal{K}\cap\operatorname{crit}f=\emptyset$. Then there exists $c>0$,
$N\geq 1$, $\eta_{0}>0$, such that, for any $n>N$, $x\in\mathcal{K}$,
$\eta\leq\eta_{0}$,

$\operatorname{\mathbb{P}}_{x}\left(\sigma_{\mathcal{X}\setminus\mathcal{K}}>n\right)=\operatorname{\mathbb{P}}_{x}\left(\tau_{\mathcal{K}}>n\right)\leq\exp\left(-c(n-N)/\eta\right)\,.$
(D.4.1)

###### Proof.

The proof is exactly the same as the proof Kifer [35, Lem. 5.3], which only
uses the l.s.c. of $\mathcal{A}_{N}$ (Corollary C.2). ∎

The following lemma provides a convenient reformulation of the results of
Lemma D.17 and Lemma D.18.

######  Lemma D.19.

  * •

There exists $\mathcal{D}\subset\mathcal{X}$ a compact set, $\eta_{0}>0$, such
that for any $\mathcal{D}^{\prime}\subset\mathcal{X}$ compact set such that
$\mathcal{D}\subset\mathcal{D}^{\prime}$, there exists $\alpha_{0},a,b>0$ such
that,

$\forall\eta\leq\eta_{0},\,\alpha\leq\alpha_{0},\,x\in\mathcal{D}^{\prime}\setminus\mathcal{D}\,,\quad\operatorname{\mathbb{E}}_{x}\left[e^{\frac{\alpha\sigma_{\mathcal{D}}}{\eta}}\right]\leq
e^{\frac{a\alpha}{\eta}+b}\,.$ (D.4.2)

  * •

For any $\mathcal{K}\subset\mathcal{X}$ compact such that
$\mathcal{K}\cap\operatorname{crit}f=\emptyset$, there exists
$\eta_{0},\alpha_{0},a,b>0$ such that,

$\forall\eta\leq\eta_{0},\,\alpha\leq\alpha_{0},\,x\in\mathcal{K}\,,\quad\operatorname{\mathbb{E}}_{x}\left[e^{\frac{\alpha\tau_{\mathcal{K}}}{\eta}}\right]\leq
e^{\frac{a\alpha}{\eta}+b}\,.$ (D.4.3)

###### Proof.

The proofs of both statements are very similar, so we prove only the second
one for notational convenience. Fix $\mathcal{K}\subset\mathcal{X}$ compact
such that $\mathcal{K}\cap\operatorname{crit}f=\emptyset$. By Lemma D.18,
there exists $c>0$, $N\geq 1$ such that, for any $n>N$, $x\in\mathcal{K}$,
$\eta\leq\eta_{0}$,

$\operatorname{\mathbb{P}}_{x}\left(\tau_{\mathcal{K}}>n\right)\leq\exp\left(-c(n-N)/\eta\right)\,.$
(D.4.4)

Let us first bound
$\operatorname{\mathbb{E}}_{x}\left[\exp\left(\frac{\alpha(\tau_{\mathcal{K}}-N)}{\eta}\right)\right]$.
We have that

$\displaystyle\operatorname{\mathbb{E}}_{x}\left[\exp\left(\frac{\alpha(\tau_{\mathcal{K}}-N)}{\eta}\right)\right]$
$\displaystyle=\int_{0}^{\infty}\operatorname{\mathbb{P}}_{x}\left(\exp\left(\frac{\alpha(\tau_{\mathcal{K}}-N)}{\eta}\right)>t\right)\>dt$
$\displaystyle\leq
e^{\frac{\alpha}{\eta}}+{\int_{e^{\frac{\alpha}{\eta}}}^{\infty}\operatorname{\mathbb{P}}_{x}\left(\tau_{\mathcal{K}}>N+\frac{\eta\log
t}{\alpha}\right)\>dt}$ $\displaystyle\leq
e^{\frac{\alpha}{\eta}}+{\int_{e^{\frac{\alpha}{\eta}}}^{\infty}\operatorname{\mathbb{P}}_{x}\left(\tau_{\mathcal{K}}>N+\left\lfloor\frac{\eta\log
t}{\alpha}\right\rfloor\right)\>dt}$ $\displaystyle\leq
e^{\frac{\alpha}{\eta}}+{\int_{e^{\frac{\alpha}{\eta}}}^{\infty}\exp\left(-\frac{c}{\eta}\left\lfloor\frac{\eta\log
t}{\alpha}\right\rfloor\right)\>dt}\,,$ (D.4.5)

where we used Eq. D.4.4 in the last inequality.

Lower bounding $\lfloor s\rfloor$ by $s-1$, we obtain that

$\displaystyle\operatorname{\mathbb{E}}_{x}\left[\exp\left(\frac{\alpha(\tau_{\mathcal{K}}-N)}{\eta}\right)\right]$
$\displaystyle\leq
e^{\frac{\alpha}{\eta}}+{\int_{e^{\frac{\alpha}{\eta}}}^{\infty}\exp\left(-\frac{c}{\eta}\frac{\eta\log
t}{\alpha}+\frac{c}{\eta}\right)\>dt}$
$\displaystyle=e^{\frac{\alpha}{\eta}}+{\int_{e^{\frac{\alpha}{\eta}}}^{\infty}e^{\frac{c}{\eta}}t^{-\frac{c}{\alpha}}\>dt}\,.$
(D.4.6)

Performing the change of variable $s\leftarrow e^{-\frac{\alpha}{\eta}}t$, we
obtain that

$\displaystyle\operatorname{\mathbb{E}}_{x}\left[\exp\left(\frac{\alpha(\tau_{\mathcal{K}}-N)}{\eta}\right)\right]$
$\displaystyle\leq
e^{\frac{\alpha}{\eta}}\left(1+{\int_{1}^{\infty}s^{-\frac{c}{\alpha}}\>ds}\right)\,.$
(D.4.7)

When $\alpha\leq c/2$, we obtain that

$\operatorname{\mathbb{E}}_{x}\left[\exp\left(\frac{\alpha(\tau_{\mathcal{K}}-N)}{\eta}\right)\right]\leq
e^{\frac{\alpha}{\eta}}\left(1+\int_{1}^{\infty}s^{-2}\>ds\right)\,,$ (D.4.8)

and therefore,

$\operatorname{\mathbb{E}}_{x}\left[\exp\left(\frac{\alpha\tau_{\mathcal{K}}}{\eta}\right)\right]\leq
e^{\frac{(N+1)\alpha}{\eta}}\left(1+\int_{1}^{\infty}s^{-2}\>ds\right)\,,$
(D.4.9)

which concludes the proof. ∎

The following lemma upper-bounds the probability of exiting a large
neighborhood of the critical points before visiting a smaller one critical
points.

######  Lemma D.20.

Consider
$\operatorname{crit}f\subset\mathcal{U}\subset\mathcal{D}\subset\mathcal{X}$
with $\mathcal{U}$ an open set and $\mathcal{D}$ a compact set. There exists
$\mathcal{D}^{\prime}\subset\mathcal{X}$ compact set such that
$\mathcal{D}\subset\mathcal{D}^{\prime}$, $\Delta>0$, $\eta_{0}>0$ such that,
for any $\eta\leq\eta_{0}$, $x\in\mathcal{D}$,

$\operatorname{\mathbb{P}}_{x}\left(\tau_{\mathcal{D}^{\prime}}<\sigma_{\mathcal{U}}\right)\leq\exp\left(-\frac{\Delta}{\eta}\right)\,.$
(D.4.10)

###### Proof.

Define
$\mathcal{D}^{\prime}\coloneqq\\{x\in\mathcal{X}:f(x)\leq\sup_{\mathcal{D}}f+1\\}$
and let $U_{\infty}$ be as in Lemma D.6.

Since $\alpha_{\infty}$ is (stricly) increasing as its derivative is (stricly)
positive by definition, we have

$\Delta\coloneqq\alpha_{\infty}\left(\sup_{\mathcal{D}}f+1\right)-\alpha_{\infty}\left(\sup_{\mathcal{D}}f\right)>0\,.$
(D.4.11)

By Lemma D.18 applied to
$\mathcal{K}\leftarrow\mathcal{D}^{\prime}_{\delta}\setminus\mathcal{U}$,
there exists $c>0$, $N_{0}\geq 1$, $\eta_{0}>0$ such that for any $n>N_{0}$,
$x\in\mathcal{D}^{\prime}_{\delta}\setminus\mathcal{U}$, $\eta\leq\eta_{0}$,

$\operatorname{\mathbb{P}}_{x}\left(\tau_{\mathcal{D}^{\prime}_{\delta}\setminus\mathcal{U}}>n\right)\leq\exp\left(-c(n-N_{0})/\eta\right)\,.$
(D.4.12)

Defining $N\coloneqq\left\lceil\frac{\Delta}{c}\right\rceil+N_{0}$, which is
greater or equal than 1, we obtain that, for any $\eta\leq\eta_{0}$,
$x\in\mathcal{D}^{\prime}_{\delta}\setminus\mathcal{U}$,

$\operatorname{\mathbb{P}}_{x}\left(\tau_{\mathcal{D}^{\prime}_{\delta}\setminus\mathcal{U}}\geq
N\right)\leq\exp\left(-\frac{\Delta}{\eta}\right)\,.$ (D.4.13)

Note that this inequality actually holds for any
$x\in\mathcal{D}^{\prime}_{\delta}$.

We now bound
$\operatorname{\mathbb{P}}_{x}\left(\tau_{\mathcal{D}^{\prime}_{\delta}}>\sigma_{\mathcal{U}}\right)$
for $x\in\mathcal{D}$ by distinguishing the cases where
$\tau_{\mathcal{D}^{\prime}_{\delta}}<N$ and
$\tau_{\mathcal{D}^{\prime}_{\delta}}\geq N$. For any $x\in\mathcal{D}$, we
have that

$\displaystyle\operatorname{\mathbb{P}}_{x}\left(\tau_{\mathcal{D}^{\prime}_{\delta}}<\sigma_{\mathcal{U}}\right)$
$\displaystyle\leq\operatorname{\mathbb{P}}_{x}\left(\tau_{\mathcal{D}^{\prime}_{\delta}}<\sigma_{\mathcal{U}},\,\tau_{\mathcal{D}^{\prime}_{\delta}}<N\right)+\operatorname{\mathbb{P}}_{x}\left(\tau_{\mathcal{D}^{\prime}_{\delta}}<\sigma_{\mathcal{U}},\,\tau_{\mathcal{D}^{\prime}_{\delta}}\geq
N\right)$
$\displaystyle\leq\operatorname{\mathbb{P}}_{x}\left(\tau_{\mathcal{D}^{\prime}_{\delta}}<N\right)+\operatorname{\mathbb{P}}_{x}\left(\tau_{\mathcal{D}^{\prime}_{\delta}\setminus\mathcal{U}}\geq
N\right)$
$\displaystyle\leq\operatorname{\mathbb{P}}_{x}\left(\tau_{\mathcal{D}^{\prime}_{\delta}}<N\right)+\exp\left(-\frac{\Delta}{\eta}\right)$
(D.4.14)

where we used Eq. D.4.13.

We now focus on bounding the first term. For this, we first show that
$\tau_{\mathcal{D}^{\prime}_{\delta}}<N$ implies that

$\operatorname{dist}_{N}\left(x^{\eta},\Gamma^{\\{x\\}}_{N}(\Delta/4)\right)>\delta/2\,.$
(D.4.15)

For the sake of contradiction, suppose that this inequality does not hold.
Therefore, there must exist $\xi\in\Gamma^{\\{x\\}}_{N}(\Delta/4)$ such that
$\operatorname{dist}_{N}\left(x^{\eta},\xi\right)<\delta$. In particular,
there is some $n<N$ such that $\xi_{n}\notin\mathcal{D}^{\prime}$, so that, by
Definition 3,

$\mathcal{A}_{N}(\xi)\geq\mathcal{A}_{n+1}(\xi)\geq B(\xi_{0},\xi_{n})\,.$
(D.4.16)

By Lemma D.6, we have that

$\displaystyle B(\xi_{0},\xi_{n})$
$\displaystyle\geq{\frac{1}{2}}\left(U_{\infty}(\xi_{n})-U_{\infty}(\xi_{0})\right)$
$\displaystyle\geq{\frac{1}{2}}\left(\alpha_{\infty}\left(\inf_{\mathcal{X}\setminus{\mathcal{D}^{\prime}}}f\right)-\alpha_{\infty}\left(\sup_{\mathcal{D}^{\prime}}f\right)\right)\,,$
(D.4.17)

since $\alpha_{\infty}$ is increasing. By construction of
$\mathcal{D}^{\prime}$, we have further that

$B(\xi_{0},\xi_{n})\geq{\frac{1}{2}}\left(\alpha_{\infty}\left(\sup_{\mathcal{D}}f+1\right)-\alpha_{\infty}\left(\sup_{\mathcal{D}}f)\right)\right)={\frac{\Delta}{2}}\,,$
(D.4.18)

so that $\mathcal{A}_{N}(\xi)\geq\Delta/2$, which is a contradiction with
$\xi\in\Gamma^{\\{x\\}}_{N}(\Delta/4)$.

Therefore, we have that

$\displaystyle\operatorname{\mathbb{P}}\left(\tau_{\mathcal{D}^{\prime}_{\delta}}<N\right)$
$\displaystyle\leq\operatorname{\mathbb{P}}\left(\operatorname{dist}_{N}\left(x^{\eta},\Gamma^{\\{x\\}}_{N}(\Delta/4)\right)>\delta/2\right)$
$\displaystyle\leq\exp\left(-\frac{\Delta}{8\eta}\right)$ (D.4.19)

where we invoked Corollary C.2 with $\delta\leftarrow\delta/2$,
$s\leftarrow\Delta/2$, $\varepsilon\leftarrow\Delta/8$. ∎

The following lemma is key to our analysis: it shows that SGD spends most of
its time near its critical points.

######  Lemma D.21.

Consider
$\operatorname{crit}f\subset\mathcal{U}\subset\mathcal{D}\subset\mathcal{X}$
with $\mathcal{U}$ an open set and $\mathcal{D}$ a compact set. Then, there is
some $\eta_{0},\alpha_{0},a,b>0$ such that,

$\forall\eta\leq\eta_{0},\,\alpha\leq\alpha_{0},\,x\in\mathcal{D}\,,\quad\operatorname{\mathbb{E}}_{x}\left[e^{\frac{\alpha\sigma_{\mathcal{U}}}{\eta}}\right]\leq
e^{\frac{a\alpha}{\eta}+b}\,.$ (D.4.20)

###### Proof.

Fix $\varepsilon>0$. Without loss of generality, assume that $\mathcal{D}$ is
large enough to include the compact set given by the first item of Lemma D.19
(note that the guarantee of the first item of Lemma D.19 still holds even if
$\mathcal{D}$ is larger).

Apply Lemma D.20 with $\mathcal{U}\leftarrow\mathcal{U}$,
$\mathcal{D}\leftarrow\mathcal{D}$ and denote by $\tilde{\mathcal{D}}$ the
obtained compact and $\eta_{0},\Delta>0$ such that, for every
$\eta\leq\eta_{0}$, $x\in\mathcal{D}$,

$\operatorname{\mathbb{P}}_{x}\left(\tau_{\tilde{\mathcal{D}}}<\sigma_{\mathcal{U}}\right)\leq\exp\left(-\frac{\Delta}{\eta}\right)\,.$
(D.4.21)

Define $r\coloneqq\sup_{x\in\tilde{\mathcal{D}}}\lVert x\rVert$ and
$R=e^{8M}(1+r)$. Assuming that $\eta\leq 1$, by Lemma B.2, for any
$x\in\tilde{\mathcal{D}}$, the next two iterates of $(x^{\eta}_{n})_{n\geq 0}$
satisfies $\lVert x^{\eta}_{1}\rVert\leq R$ and $\lVert x^{\eta}_{2}\rVert\leq
R$. Define $\mathcal{D}^{\prime}\coloneqq\overline{\mathbb{B}}(0,R)$.

We invoke both items of Lemma D.19 with
$\mathcal{K}\leftarrow\tilde{\mathcal{D}}\setminus\mathcal{U}$ and denote by
$c>0$ a constant that satisfies the bounds of both items. In the rest of the
proof, we consider $\eta$ and $\alpha$ smaller than the bounds given by this
lemma.

Our goal is to bound, for any $N\geq 0$, the quantity,

$s_{N}(\alpha,\eta)\coloneqq\sup_{x\in\mathcal{D}}\operatorname{\mathbb{E}}_{x}\left[\exp\left(\frac{\alpha\sigma_{\mathcal{U}}^{N}}{\eta}\right)\right]\,,\quad\text{where}\quad\sigma_{\mathcal{U}}^{N}\coloneqq\min(N,\sigma_{\mathcal{U}})\,.$
(D.4.22)

Note that, by construction, $s_{N}(\alpha,\eta)$ is finite.

Take $x\in\mathcal{D}$. In particular, Lemma D.19 implies that
$\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}}<+\infty$ almost surely for all
$x\in\mathcal{D}$.

$\displaystyle\exp\left(\frac{\alpha\sigma_{\mathcal{U}}^{N}}{\eta}\right)$
$\displaystyle=\operatorname{\mathds{1}}\\{x^{\eta}_{\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}}}\in\mathcal{U}\\}\exp\left(\frac{\alpha\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}}}{\eta}\right)$
$\displaystyle\qquad+\operatorname{\mathds{1}}\\{x^{\eta}_{\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}}}\notin\mathcal{D}_{\delta}\\}\exp\left(\frac{\alpha\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}}}{\eta}\right)\exp\left(\frac{\alpha\left(\sigma_{\mathcal{U}}^{N}-\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}}\right)}{\eta}\right)$
$\displaystyle\leq\operatorname{\mathds{1}}\\{x^{\eta}_{\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}}}\in\mathcal{U}\\}\exp\left(\frac{\alpha\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}}}{\eta}\right)$
$\displaystyle\qquad+\operatorname{\mathds{1}}\\{x^{\eta}_{\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}}}\notin\mathcal{D}_{\delta}\\}\exp\left(\frac{\alpha\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}}}{\eta}\right)\exp\left(\frac{\alpha\min\left(\sigma_{\mathcal{U}}-\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}},N\right)}{\eta}\right)$
(D.4.23)

so that we can apply the strong Markov property to the Markov chain
$(x^{\eta}_{n})_{n\geq 0}$ with stopping time
$\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}}$ to obtain that

$\displaystyle\operatorname{\mathbb{E}}_{x}\left[\exp\left(\frac{\alpha\sigma_{\mathcal{U}}^{N}}{\eta}\right)\right]$
$\displaystyle\leq\operatorname{\mathbb{E}}_{x}\bigg{[}\operatorname{\mathds{1}}\\{x^{\eta}_{\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}}}\in\mathcal{U}\\}\exp\left(\frac{\alpha\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}}}{\eta}\right)$
$\displaystyle\qquad+\operatorname{\mathds{1}}\\{x^{\eta}_{\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}}}\notin\mathcal{D}_{\delta}\\}\exp\left(\frac{\alpha\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}}}{\eta}\right)\operatorname{\mathbb{E}}_{x^{\eta}_{\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}}}}\left[\exp\left(\frac{\alpha\sigma_{\mathcal{U}}^{N}}{\eta}\right)\right]\bigg{]}$
(D.4.24)

We now bound

$\operatorname{\mathds{1}}\\{x^{\eta}_{\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}}}\notin\mathcal{D}_{\delta}\\}\operatorname{\mathbb{E}}_{x^{\eta}_{\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}}}}\left[\exp\left(\frac{\alpha\sigma_{\mathcal{U}}^{N}}{\eta}\right)\right]=\operatorname{\mathbb{E}}_{x^{\eta}_{\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}}}}\left[\operatorname{\mathds{1}}\\{x^{\eta}_{0}\notin\mathcal{D}_{\delta}\\}\exp\left(\frac{\alpha\sigma_{\mathcal{U}}^{N}}{\eta}\right)\right]$
(D.4.25)

Since $x$ is in $\mathcal{D}$, by definition,
$\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}}$ is at least equal to 1 and
$x^{\eta}_{\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}}-1}$ is still in
$\tilde{\mathcal{D}}$. By definition of $\mathcal{D}^{\prime}$,
$x^{\eta}_{\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}}}$ must still be in
$\mathcal{D}^{\prime}$. Therefore, the guarantee of Lemma D.19 applies and,
since in particular it implies that $\sigma_{\mathcal{D}}$ is finite almost
surely when the chain is started at
$x^{\eta}_{\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}}}$, we can apply the
strong Markov property to obtain that

$\displaystyle\operatorname{\mathbb{E}}_{x^{\eta}_{\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}}}}\left[\operatorname{\mathds{1}}\\{x_{0}\notin\tilde{\mathcal{D}}\\}\exp\left(\frac{\alpha\sigma_{\mathcal{U}}^{N}}{\eta}\right)\right]$
$\displaystyle\leq\operatorname{\mathbb{E}}_{x^{\eta}_{\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}}}}\left[\operatorname{\mathds{1}}\\{x_{0}\notin\tilde{\mathcal{D}}\\}\exp\left(\frac{\alpha\sigma_{\mathcal{D}}}{\eta}\right)\operatorname{\mathbb{E}}_{x^{\eta}_{\sigma_{\mathcal{D}}}}\left[\exp\left(\frac{\alpha\sigma_{\mathcal{U}}^{N}}{\eta}\right)\right]\right]$
$\displaystyle\leq
s_{N}(\alpha,\eta)\operatorname{\mathbb{E}}_{x^{\eta}_{\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}}}}\left[\operatorname{\mathds{1}}\\{x_{0}\notin\tilde{\mathcal{D}}\\}\exp\left(\frac{\alpha\sigma_{\mathcal{D}}}{\eta}\right)\right]$
(D.4.26)

where, for the second inequality, we used the definition of
$s_{N}(\alpha,\eta)$ and the fact that $x_{\sigma_{\mathcal{D}}}$ is in
$\mathcal{D}$.

Now, to bound the remaining expectation, note that $x_{0}$ does not belong to
$\tilde{\mathcal{D}}$ and, _a fortiori_ , does not belong to $\mathcal{D}$.
Therefore, $\sigma_{\mathcal{D}}$ depends only on $(x^{\eta}_{n})_{n\geq 1}$
and the (weak) Markov property implies that

$\displaystyle\operatorname{\mathbb{E}}_{x^{\eta}_{\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}}}}\left[\operatorname{\mathds{1}}\\{x_{0}\notin\tilde{\mathcal{D}}\\}\exp\left(\frac{\alpha\sigma_{\mathcal{D}}}{\eta}\right)\right]$
$\displaystyle\leq\operatorname{\mathbb{E}}_{x^{\eta}_{\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}}}}\left[\operatorname{\mathds{1}}\\{x_{0}\notin\tilde{\mathcal{D}}\\}\operatorname{\mathbb{E}}_{x_{1}}\left[\exp\left(\frac{\alpha(1+\sigma_{\mathcal{D}})}{\eta}\right)\right]\right]$
$\displaystyle\leq\exp\left(\frac{\alpha(1+c)}{\eta}\right)\operatorname{\mathbb{E}}_{x^{\eta}_{\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}}}}\left[\operatorname{\mathds{1}}\\{x_{0}\notin\tilde{\mathcal{D}}\\}\right]\,,$
(D.4.27)

by Lemma D.19, since the
$x^{\eta}_{\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}}-1}$ is still in
$\tilde{\mathcal{D}}$ so that $x_{1}$ of the chain started at
$x^{\eta}_{\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}}}$ is still in
$\mathcal{D}^{\prime}$.

Lemma D.20 then implies that,

$\displaystyle\operatorname{\mathbb{E}}_{x^{\eta}_{\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}}}}\left[\operatorname{\mathds{1}}\\{x_{0}\notin\tilde{\mathcal{D}}\\}\exp\left(\frac{\alpha\sigma_{\mathcal{D}^{\prime}}}{\eta}\right)\right]\leq\exp\left(\frac{\alpha(1+a)-\Delta}{\eta}+b\right)$
(D.4.28)

Combining these bounds with Eq. D.4.24 then gives

$\displaystyle\operatorname{\mathbb{E}}_{x}\left[\exp\left(\frac{\alpha\sigma_{\mathcal{U}}^{N}}{\eta}\right)\right]$
$\displaystyle\leq\left(1+s_{N}(\alpha,\eta)\exp\left(\frac{\alpha(1+a)-\Delta}{\eta}+b\right)\right)\operatorname{\mathbb{E}}_{x}\left[\exp\left(\frac{\alpha\tau_{\tilde{\mathcal{D}}\setminus\mathcal{U}}}{\eta}\right)\right]$
$\displaystyle\leq\left(1+s_{N}(\alpha,\eta)\exp\left(\frac{\alpha(1+a)-\Delta}{\eta}+b\right)\right)\exp\left(\frac{a\alpha}{\eta}+b\right)\,,$
(D.4.29)

by Lemma D.19. Since this inequality is valid for any $x\in\mathcal{D}$, we
have shown that

$s_{N}(\alpha,\eta)\leq\left(e^{\frac{a\alpha}{\eta}+b}+s_{N}(\alpha,\eta)e^{\frac{\alpha(1+2a)-\Delta}{\eta}+b}\right)\,.$
(D.4.30)

For $\alpha\leq\Delta/(2(1+2a))$ and $\eta$ small enough,

$e^{\frac{\alpha(1+2a)-\Delta}{\eta}+b}\leq
e^{-\frac{\Delta}{2\eta}+b}\leq{\frac{1}{2}}\,,$ (D.4.31)

and we obtain that

$s_{N}(\alpha,\eta)\leq 2e^{\frac{a\alpha}{\eta}+b}\,.$ (D.4.32)

Taking $N\to+\infty$ and using Fatou’s lemma yields that

$\sup_{x\in\mathcal{D}}\operatorname{\mathbb{E}}_{x}\left[\exp\left(\frac{\alpha\sigma_{\mathcal{U}}}{\eta}\right)\right]\leq
2e^{\frac{a\alpha}{\eta}+b}\,,$ (D.4.33)

which concludes the proof. ∎

###  D.5. Estimates of the invariant measure

Define, for sets $A,B\subset\mathcal{X}$,

$B(A,B)\coloneqq\inf\\{B(x,z):x\in A,z\in B\\}\,.$ (D.5.1)

Recall that for any $i,j$, we define

$B_{i,j}=B(\mathcal{K}_{i},\mathcal{K}_{j})=\inf\\{B(x,z):x\in\mathcal{K}_{i},z\in\mathcal{K}_{j}\\}\,.$
(D.5.2)

Recall that, to avoid degenerate cases, we assume that Assumption 4 holds,
that is,

$B_{ij}<\infty\quad\text{for all $i,j=1,\dotsc,K$}.$ (D.5.3)

With Lemma D.12, this assumption is satisfied in particular if the following
condition holds: for any $i,j=1,\dotsc,K$, there exists a $\mathcal{C}^{1}$
path $\gamma$ joining $\mathcal{K}_{i}$ and $\mathcal{K}_{j}$ such that, for
all $t$, $\nabla f(\gamma_{t})$ belongs to the interior of the closed convex
hull of the support of the noise $\mathsf{U}(\gamma_{t},\omega)$:

$\nabla
f(\gamma_{t})\in\operatorname{int}\operatorname{\overline{conv}}\operatorname{supp}\mathsf{U}(\gamma_{t},\omega)\,,$
(D.5.4)

This means there is a sufficient level of noise for the probability of going
from $\mathcal{K}_{i}$ to $\mathcal{K}_{j}$ with at least one path to be non-
zero (though it can be vanishingly small). Note that it does not constrain the
nature of the noise itself — which can be discrete, continuous or else —, only
the support of its distribution.

Moreover, if Assumption 4 did not hold, the same analysis as in this section
could still be carried out. We would consider the components of the graph
$\mathcal{G}$ connected by edges with finite weights proceed with the proof on
each of them, and obtain the same results on each of these components. To keep
the complexity of the proof reasonable, we will not consider this case here.

We adapt to our context Kifer [35, Lem. 5.4] and simplify it using ideas from
Freidlin & Wentzell [20, Chap. 6].

######  Definition 6 (Freidlin & Wentzell [20, Chap. 6,§2]).

For $i,j$,

$\widetilde{B}_{i,j}\coloneqq\inf\left\\{\mathcal{A}_{N}(\xi):N\geq
1,\xi\in\mathcal{X}^{N},\,\xi_{0}\in\mathcal{K}_{i},\,\xi_{N-1}\in\mathcal{K}_{j},\,\xi_{n}\notin\bigcup_{l\neq
i,j}\mathcal{K}_{l}\text{ for }n=1,\dots,N-2\right\\}\,.$ (D.5.5)

We now defined an important object: the law of the (accelerated) iterated at
the first time they reach some set $\mathcal{V}$ (typically a neighborhood of
the critical set), following e.g., Douc et al. [14, Chap. 3.4].

######  Definition 7 (Kifer [35, Prop. 5.3]).

For $\mathcal{V}$ open set, with hitting time (of the accelerated sequence)
$\sigma_{\mathcal{V}}\coloneqq\inf\\{n\geq 1:x^{\eta}_{n}\in\mathcal{V}\\}\,,$
(as in Definition 5), denote the law of $x^{\eta}_{\sigma_{\mathcal{V}}}$
started at $x$ by $\operatorname{\mathbb{Q}}_{\mathcal{V}}(x,\cdot)$ and the
corresponding $N$-step transition probability by
$\operatorname{\mathbb{Q}}_{\mathcal{V}}^{N}(x,\cdot)$.

In words, $\operatorname{\mathbb{Q}}_{\mathcal{V}}(x,\cdot)$ is the
distributions of the $x^{\eta}$ started at $x$ at the first time they reach
$\mathcal{V}$. Typically,
$\operatorname{\mathbb{Q}}_{\mathcal{V}}(x,\mathcal{U})$ is the probability
that $\mathcal{U}\subset\mathcal{V}$ is reached first among $\mathcal{V}$.
Then, $\operatorname{\mathbb{Q}}_{\mathcal{V}}^{N}(x,\cdot)$ is the
distribution of the $x^{\eta}$ started at $x$ at the $N$-th time they reach
$\mathcal{V}$.

We first give estimates of the transition probabilities using the
$\widetilde{B}_{i,j}$. We will then translate them to $B_{i,j}$.

######  Lemma D.22.

For any $\varepsilon>0$, for any small enough neighborhoods $\mathcal{V}_{i}$
of $\mathcal{K}_{i}$, $i=1,\dots,K$ , there is some $\eta_{0}>0$ such that for
all $i,j$, $x\in\mathcal{V}_{i}$, $0<\eta<\eta_{0}$,

$\operatorname{\mathbb{Q}}_{\mathcal{V}}(x,\mathcal{V}_{j})\leq\exp\left(-\frac{\widetilde{B}_{i,j}}{\eta}+\frac{\varepsilon}{\eta}\right)\,.$
(D.5.6)

where we defined $\mathcal{V}\coloneqq\bigcup_{i=1}^{K}\mathcal{V}_{i}$.

###### Proof.

Assume that, without loss of generality, $\varepsilon$ is small enough so that
Lemma D.8 with $r\leftarrow\varepsilon$ can be applied to every
$\mathcal{K}_{i}$, $i=1,\dots,K$. Denote by $\mathcal{W}_{i}$, $i=1,\dots,K$
the corresponding neighborhoods of $\mathcal{K}_{i}$.

Since these $\mathcal{W}_{i}$’s are open neighborhoods of the
$\mathcal{K}_{i}$’s, there exists $\delta>0$ such that
$\mathcal{U}_{2\delta}(\mathcal{K}_{i})\subset\mathcal{W}_{i}$ for all
$i=1,\dots,K$. Require then that $\mathcal{V}_{i}$ be contained in
$\mathcal{U}_{\delta}(\mathcal{K}_{i})$ so that
$\mathcal{U}_{\delta}(\mathcal{V}_{i})\subset\mathcal{W}_{i}$ for all
$i=1,\dots,K$. Moreover, assume that $\delta>0$ is small enough so that the
neighborhoods $\mathcal{U}_{\delta}(\mathcal{K}_{i})$, $i=1,\dots,K$ are
pairwise disjoint.

Define $0<\delta^{\prime}\leq\delta$ such that
$\mathcal{U}_{\delta}^{\prime}(\mathcal{K}_{i})$ is contained in
$\mathcal{V}_{i}$ for all $i=1,\dots,K$.

Fix $i,j\in I$ and consider $\xi\in(\mathcal{X})^{N}$ such that
$\xi_{0}\in\mathcal{U}_{\delta}^{\prime}(\mathcal{V}_{i})\subset\mathcal{W}_{i}$,
$\xi_{N-1}\in\mathcal{U}_{\delta}^{\prime}(\mathcal{V}_{j})\subset\mathcal{W}_{j}$
and
$\xi_{n}\in\mathcal{U}_{\delta^{\prime}}\left(\mathcal{X}\setminus\bigcup_{l\neq
i,j}\mathcal{V}_{l}\right)$ for all $n=1,\dots,N-2$. By the choice of
$\delta^{\prime}$, $\xi_{n}$ cannot be in $\bigcup_{l\neq i,j}\mathcal{K}_{l}$
for any $n=1,\dots,N-2$.

By definition of $\mathcal{W}_{i}$ and $\mathcal{W}_{j}$, there are
$x\in\mathcal{K}_{i}$, $x^{\prime}\in\mathcal{K}_{j}$ such that
$\rho(x,\xi_{0})<\varepsilon$, $\rho(\xi_{N-1},x^{\prime})<\varepsilon$.
Therefore, the path $\zeta\in(\mathcal{X})^{N+2}$ defined as
$\zeta=(x,\xi_{0},\xi_{1},\dots,\xi_{N-1},x^{\prime})$ satisfies

$\mathcal{A}_{N}(\xi)\geq\mathcal{A}_{N+2}(\zeta)-2\varepsilon\,.$ (D.5.7)

and, by definition of $\widetilde{B}_{i,j}$, we thus obtain,

$\mathcal{A}_{N}(\xi)\geq\mathcal{A}_{N+2}(\zeta)-2\varepsilon\geq\widetilde{B}_{i,j}-2\varepsilon\,.$
(D.5.8)

Fix $x\in\mathcal{V}_{i}$. Let us now bound the probability

$\operatorname{\mathbb{Q}}_{\mathcal{V}}(x,\mathcal{V}_{j})=\operatorname{\mathbb{P}}_{x}\left(x^{\eta}_{\sigma_{\mathcal{V}}}\in\mathcal{V}_{i}\right)\,.$
(D.5.9)

We have, for any $N\geq 0$,

$\operatorname{\mathbb{P}}_{x}\left(x^{\eta}_{\sigma_{\mathcal{V}}}\in\mathcal{V}_{i}\right)\leq\operatorname{\mathbb{P}}_{x}\left(x^{\eta}_{\sigma_{\mathcal{V}}}\in\mathcal{V}_{i},\,\sigma_{\mathcal{V}}<N\right)+\operatorname{\mathbb{P}}_{x}\left(\sigma_{\mathcal{V}}\geq
N\right)\,.$ (D.5.10)

We first bound the second probability using Lemma D.21 applied to
$\mathcal{U}\leftarrow\mathcal{V}_{i}$. Take $N$ such that
$\alpha_{0}(a-N)+\eta_{0}b\leq-\widetilde{B}_{i,j}$. Then, by Markov’s
inequality and Lemma D.21, it holds that for all $\eta\leq\eta_{0}$

$\displaystyle\operatorname{\mathbb{P}}_{x}\left(\sigma_{\mathcal{V}}\geq
N\right)$
$\displaystyle\leq\operatorname{\mathbb{P}}_{x}\left(\exp\left(\frac{\alpha_{0}\sigma_{\mathcal{V}}}{\eta}\right)\geq\exp\left(\frac{\alpha_{0}N}{\eta}\right)\right)$
$\displaystyle\leq\exp\left(\frac{\alpha_{0}(a-N)}{\eta}+b\right)$
$\displaystyle\leq\exp\left(\frac{-\widetilde{B}_{i,j}}{\eta}\right)\,.$
(D.5.11)

We now bound the term
$\operatorname{\mathbb{P}}_{x}\left(x^{\eta}_{\sigma_{\mathcal{V}}}\in\mathcal{V}_{j},\,\sigma_{\mathcal{V}}<N\right)$
for this choice of $N$.

For this, we show that $x^{\eta}_{\sigma_{\mathcal{V}}}\in\mathcal{V}_{j}$
with $\sigma_{\mathcal{V}}<N$ implies that

$\operatorname{dist}_{N}\left(x^{\eta},\Gamma_{N}^{\\{x\\}}\left(\widetilde{B}_{i,j}-3\varepsilon\right)\right)>{\frac{\delta^{\prime}}{2}}\,.$
(D.5.12)

Indeed, on the event $x^{\eta}_{\sigma_{\mathcal{V}}}\in\mathcal{V}_{j}$ with
$\sigma_{\mathcal{V}}<N$, there is some $N^{\prime}\leq N$ such that
$\sigma_{\mathcal{V}}=N^{\prime}-1$. If
$\operatorname{dist}_{N}\left(x^{\eta},\Gamma_{N}^{\\{x\\}}\left(\widetilde{B}_{i,j}-3\varepsilon\right)\right)>{\frac{\delta^{\prime}}{2}}$
did not hold, this would mean that there exists
$\xi\in(\mathcal{X})^{N^{\prime}}$ such that
$\operatorname{dist}_{N^{\prime}}(x^{\eta},\xi)<\delta^{\prime}$, $\xi_{0}=x$
and, $\mathcal{A}_{N^{\prime}}(\xi)\leq\widetilde{B}_{i,j}-3\varepsilon$. In
particular, $\xi$ would also satisfy
$\xi_{N^{\prime}-1}\in\mathcal{U}_{\delta^{\prime}}(\mathcal{V}_{j})$,
$\xi_{n}\in\mathcal{U}_{\delta^{\prime}}(\mathcal{X}\setminus\mathcal{V})$ for
all $n=1,\dots,N^{\prime}-2$. This would be in direct contradiction of Eq.
D.5.8.

Therefore, we have that

$\displaystyle\operatorname{\mathbb{P}}_{x}\left(x^{\eta}_{\sigma_{\mathcal{V}}}\in\mathcal{V}_{j},\,\sigma_{\mathcal{V}}<N\right)$
$\displaystyle\leq\operatorname{\mathbb{P}}_{x}\left(\operatorname{dist}_{N}\left(x^{\eta},\Gamma_{N}^{\\{x\\}}\left(\widetilde{B}_{i,j}-3\varepsilon\right)\right)>{\frac{\delta^{\prime}}{2}}\right)$
$\displaystyle\leq\exp\left(-\frac{\widetilde{B}_{i,j}-4\varepsilon}{\eta}\right)\,,$
(D.5.13)

by Corollary C.2.

Combining this bound with Eq. D.5.11 yields

$\operatorname{\mathbb{P}}_{x}(x^{\eta}_{\sigma_{\mathcal{V}}}\in\mathcal{V}_{j})\leq\exp\left(-\frac{\widetilde{B}_{i,j}-4\varepsilon}{\eta}\right)+\exp\left(\frac{-\widetilde{B}_{i,j}}{\eta}\right)\,,$
(D.5.14)

which concludes the proof. ∎

######  Lemma D.23.

For any $\varepsilon>0$,for any neighborhoods $\mathcal{V}_{i}$ of
$\mathcal{K}_{i}$, $i=1,\dots,K$ small enough, there exists $N\geq 0$,
$\eta_{0}>0$ such that for all $i,j$, $x\in\mathcal{V}_{i}$,
$0<\eta<\eta_{0}$,

$\operatorname{\mathbb{Q}}_{\mathcal{V}}^{N}(x,\mathcal{V}_{j})\geq\exp\left(-\frac{\widetilde{B}_{i,j}}{\eta}-\frac{\varepsilon}{\eta}\right)\,.$
(D.5.15)

###### Proof.

For any $i,j$, there exists $N_{i,j}\geq 1$,
$\xi^{i,j}\in(\mathcal{X})^{N_{i,j}}$ such that
$\xi^{i,j}_{0}\in\mathcal{K}_{i}$, $\xi^{i,j}_{N_{i,j}-1}\in\mathcal{K}_{j}$,
$\xi^{i,j}_{n}\notin\bigcup_{l\neq i,j}\mathcal{K}_{l}$ for all
$n=1,\dots,N_{i,j}-2$ and
$\mathcal{A}_{N_{i,j}}(\xi^{i,j})\leq\widetilde{B}_{i,j}+\varepsilon$. Define
$\delta_{i,j}\coloneqq\min\left\\{d(\xi^{i,j}_{n},\bigcup_{l\neq
i,j}\mathcal{K}_{l}):n=1,\dots,N_{i,j}-2\right\\}$ and
$\delta\coloneqq\min_{i,j\in I}\delta_{i,j}$. By construction, it holds that
$\delta>0$.

Require that $\mathcal{V}_{i}$ be contained in
$\mathcal{W}_{i}\cap\mathcal{U}_{\delta/2}(\mathcal{K}_{i})$ for all
$i=1,\dots,K$. Now, given such $\mathcal{V}_{i}$ neighborhoods of
$\mathcal{K}_{i}$, $i=1,\dots,K$, there exists $0<\delta^{\prime}\leq\delta/2$
such that $\mathcal{U}_{\delta}^{\prime}(\mathcal{K}_{i})$ is contained in
$\mathcal{V}_{i}$ for all $i=1,\dots,K$.

Apply Lemma D.9 to $\mathcal{K}_{i}$, $i=1,\dots,K$ with
$\varepsilon\leftarrow\min(\varepsilon,\delta^{\prime}/2)$ and denote by
$N_{i}$ the bound on the length of paths obtained. Define

$N\coloneqq\max_{i\in I}N_{i}+1\,.$ (D.5.16)

Fix $i,j\in I$ and $x\in\mathcal{V}_{i}$. Since
$\mathcal{V}_{i}\subset\mathcal{W}_{i}$, there exists $z\in\mathcal{K}_{i}$
such that $\rho(x,z)<\varepsilon$. Moreover, note that $\rho(z,z)=0$ since $z$
is a critical point of $f$.

By Lemma D.9, there exists $n\leq N$, $\xi\in(\mathcal{X})^{n}$ such that
$\xi_{0}=z$, $\xi_{N-1}=\xi^{i,j}_{0}$,
$\xi_{k}\in\mathcal{U}_{\delta^{\prime}/2}(\mathcal{K}_{i})$ for all
$k=1,\dots,n-2$ and $\mathcal{A}_{n}(\xi)<\varepsilon$.

Considering the concatenation

$\zeta\coloneqq\left(x,\underbrace{z,z,\dots,z}_{N-n\text{
times}},\xi_{0},\xi_{1},\dots,\xi_{n-2},\xi_{n-1},\xi^{i,j}_{1},\dots,\xi^{i,j}_{N_{i,j}-1}\right)$
(D.5.17)

which is a path of length $N+N_{i,j}$ made of $x\in\mathcal{V}_{i}$, then
exactly $N$ points in $\mathcal{U}_{\delta^{\prime}/2}(\mathcal{K}_{i})$ then
$N_{i,j}-2$ in $\mathcal{X}\setminus\mathcal{U}_{\delta/2}(\mathcal{V})$ and
$\xi^{i,j}_{N_{i,j}-1}\in\mathcal{K}_{j}$. Moreover, by construction,
$\mathcal{A}_{N+N_{i,j}}(\zeta)\leq\widetilde{B}_{i,j}+3\varepsilon$.
Therefore, if

$\operatorname{dist}_{N+N_{i,j}}\left(x^{\eta},\zeta\right)<\delta^{\prime}/2\,,$
(D.5.18)

with $x^{\eta}_{0}=x$, then $x^{\eta}_{1},\dots,x^{\eta}_{N}$ are in
$\mathcal{U}_{\delta^{\prime}}(\mathcal{K}_{i})\subset\mathcal{V}_{i}$ and,
since $\delta^{\prime}\leq\delta/2$,
$x^{\eta}_{N+1},\dots,x^{\eta}_{N+N_{i,j}-2}$ are not in
$\mathcal{U}_{\delta/4}(\mathcal{V})$, and therefore not in $\mathcal{V}$.
Moreover, $x^{\eta}_{N+N_{i,j}-1}$ would be in
$\mathcal{U}_{\delta^{\prime}/2}(\mathcal{K}_{j})\subset\mathcal{V}_{j}$.

Thus, all the paths $x^{\eta}$ satisfying (D.5.18) with $x^{\eta}_{0}=x$ are
started at $x$ and their $N$-th point that fall into $\mathcal{V}$ belongs to
$\mathcal{V}_{j}$.

Therefore, using the definition of
$\operatorname{\mathbb{Q}}_{\mathcal{V}}^{N}$, we have that

$\displaystyle\operatorname{\mathbb{Q}}_{\mathcal{V}}^{N}(x,\mathcal{V}_{j})$
$\displaystyle\geq\operatorname{\mathbb{P}}_{x}\left(\operatorname{dist}_{N+N_{i,j}}\left(x^{\eta},\zeta\right)<\delta^{\prime}/2\right)$
$\displaystyle\geq\exp\left(-\frac{\widetilde{B}_{i,j}+4\varepsilon}{\eta}\right)\,,$
(D.5.19)

by Corollary C.2. ∎

######  Lemma D.24.

For any $i,j\in I$,

$\displaystyle B_{i,j}$
$\displaystyle=\min\left\\{\sum_{l=0}^{n-2}\widetilde{B}_{i_{l},i_{l+1}}:i_{0}=i,\,i_{n-1}=j,\,i_{l}\in
I\text{ for }l=1,\dots,n-2\,,n\geq 1\right\\}$
$\displaystyle=\min\left\\{\sum_{l=0}^{K-2}\widetilde{B}_{i_{l},i_{l+1}}:i_{0}=i,\,i_{K-1}=j,\,i_{l}\in
I\text{ for }l=1,\dots,K-2\right\\}\,.$ (D.5.20)

###### Proof.

It suffices to show that

$B_{i,j}=\min\left\\{\sum_{l=0}^{n-2}\widetilde{B}_{i_{l},i_{l+1}}:i_{0}=i,\,i_{n-1}=j,\,i_{l}\in
I\text{ for }l=1,\dots,n-2\,,n\geq 1\right\\}\,.$ (D.5.21)

The statement of the lemma then follows from the fact that
$\widetilde{B}_{l,l}=0$ for all $l\in I$ and that shortest paths on graphs can
be chosen not to visit the same node twice.

For the inequality $(\geq)$, notice that any path between $\mathcal{K}_{i}$
and $\mathcal{K}_{j}$ can be decomposed into a concatenation of paths between
$\mathcal{K}_{i}$ and $\mathcal{K}_{i_{1}}$, $\mathcal{K}_{i_{1}}$ and
$\mathcal{K}_{i_{2}}$, …, $\mathcal{K}_{i_{n-1}}$ and $\mathcal{K}_{j}$ for
some $i_{1},\dots,i_{n-1}\in I$ that do not enter any other equivalence class
in between. Therefore, the inequality $(\geq)$ follows from the definition of
$B_{i,j}$ and $\widetilde{B}_{i_{l},i_{l+1}}$.

We now focus on $(\leq)$.

Fix $\varepsilon$. Take $n\geq 1$, $i_{0}=i$, $i_{n-1}=j$, $i_{l}\in I$ for
$l=1,\dots,n-2$. There are paths $\xi^{0},\dots,\xi^{n-2}$ of lengths
$N_{0},\dots,N_{n-2}$ such that $\xi^{l}_{0}\in\mathcal{K}_{i_{l}}$,
$\xi^{l}_{N_{l}-1}\in\mathcal{K}_{i_{l+1}}$,
$\mathcal{A}_{N_{l}}(\xi^{l})\leq\widetilde{B}_{i_{l},i_{l+1}}+\varepsilon/n$
for $l=0,\dots,n-2$.

By Lemma D.9, for all $l=0,\dots,n-2$, $\xi^{l}_{N_{l}-1}$ and $\xi^{l+1}_{0}$
can be connected by path of cost at most $\varepsilon/n$. Therefore
concatenating all these paths yield $\zeta$ of length $N$ with
$\zeta_{0}\in\mathcal{K}_{i}$, $\zeta_{N-1}\in\mathcal{K}_{j}$ and
$\mathcal{A}_{N}(\zeta)\leq\sum_{l=0}^{n-2}\widetilde{B}_{i_{l},i_{l+1}}+2\varepsilon$.
Since $\mathcal{A}_{N}(\zeta)\geq B_{i,j}$, we obtain the desired result. ∎

######  Notation 1.

We will write, for non-decreasing $f\colon\mathbb{R}\to\mathbb{R}$,

$a\asymp f(b\pm c)\iff f(b-c)\leq a\leq f(b+c)\,.$ (D.5.22)

######  Proposition D.2.

For any $\varepsilon>0$ and any small enough neighborhoods $\mathcal{V}_{i}$
of $\mathcal{K}_{i}$, $i=1,\dots,K$, there exists $N\geq 0$, $\eta_{0}>0$ such
that for all $i,j$, $x\in\mathcal{V}_{i}$, $0<\eta<\eta_{0}$,

$\operatorname{\mathbb{Q}}_{\mathcal{V}}^{N}(x,\mathcal{V}_{j})\asymp\exp\left(-\frac{B_{i,j}}{\eta}\pm\frac{\varepsilon}{\eta}\right)\,.$
(D.5.23)

###### Proof.

Let us first start with $(\geq)$.

Let $N$ satisfy the conditions of Lemma D.23 and define
$N^{\prime}\coloneqq(K-1)N$. For any $i,j\in I$, by Lemma D.24, there exist
$i_{0}=i$, $i_{K-1}=j$, $i_{l}\in I$ for $l=1,\dots,K-2$ such that

$B_{i,j}=\sum_{l=0}^{K-2}\widetilde{B}_{i_{l},i_{l+1}}\,.$ (D.5.24)

Therefore, we have that the probability of reaching $\mathcal{V}_{j}$ from
$x\in\mathcal{V}_{i}$ in $N^{\prime}=(K-1)N$ steps is greater than the
probability of reaching sequentially the $\mathcal{V}_{i_{l+1}}$ from any
point $x\in\mathcal{V}_{i_{l}}$, i.e.,

$\displaystyle\inf_{x\in\mathcal{V}_{i}}\operatorname{\mathbb{Q}}_{\mathcal{V}}^{N^{\prime}}(x,\mathcal{V}_{j})$
$\displaystyle\geq\prod_{l=0}^{K-2}\inf_{x\in\mathcal{V}_{i_{l}}}\operatorname{\mathbb{Q}}_{\mathcal{V}}^{N}(x,\mathcal{V}_{i_{l+1}})$
$\displaystyle\geq\prod_{l=0}^{K-2}\exp\left(-\frac{\widetilde{B}_{i_{l},i_{l+1}}}{\eta}-\frac{\varepsilon}{\eta}\right)=\exp\left(-\frac{B_{i,j}}{\eta}-\frac{(K-1)\varepsilon}{\eta}\right)\,$
(D.5.25)

where we used Lemma D.23 to get the second inequality.

Now for the reverse inequality $(\leq)$. Take $i,j\in I$ and denote $i_{0}=i$,
$i_{N^{\prime}-1}=j$. By Lemma D.22, we have that

$\displaystyle\sup_{x\in\mathcal{V}_{i}}\operatorname{\mathbb{Q}}_{\mathcal{V}}^{N^{\prime}}(x,\mathcal{V}_{j})$
$\displaystyle\leq\sum_{i_{1},\dots,i_{K-2}\in
I}\prod_{l=0}^{K-2}\sup_{x\in\mathcal{V}_{i_{l}}}\operatorname{\mathbb{Q}}_{\mathcal{V}}^{N}(x,\mathcal{V}_{i_{l+1}})$
$\displaystyle\leq\sum_{i_{1},\dots,i_{K-2}\in
I}\prod_{l=0}^{K-2}\exp\left(-\frac{\widetilde{B}_{i_{l},i_{l+1}}}{\eta}+\frac{\varepsilon}{\eta}\right)$
$\displaystyle\leq\sum_{i_{1},\dots,i_{K-2}\in
I}\exp\left(-\frac{\sum_{l=0}^{N^{\prime}}\widetilde{B}_{i_{l},i_{l+1}}}{\eta}+\frac{(K-1)\varepsilon}{\eta}\right)\,.$
(D.5.26)

Using Lemma D.24, we obtain that

$\displaystyle\sup_{x\in\mathcal{V}_{i}}\operatorname{\mathbb{Q}}_{\mathcal{V}}^{N^{\prime}}(x,\mathcal{V}_{j})$
$\displaystyle\leq\sum_{i_{1},\dots,i_{K-2}\in
I}\exp\left(-\frac{B_{i,j}}{\eta}+\frac{(K-1)\varepsilon}{\eta}\right)$
$\displaystyle={K}^{K-2}\exp\left(-\frac{B_{i,j}}{\eta}+\frac{(K-1)\varepsilon}{\eta}\right)$
(D.5.27)

which concludes the proof. ∎

Let us now give our first estimates on the invariant measure.

######  Definition 8 ([20, Chap. 6,§4]).

Define, for every $i\in I$,

$E_{i}=E(\mathcal{K}_{i})\coloneqq\min_{T\in\mathcal{T}_{i}}\sum_{(j\to l)\in
T}B_{j,l}\,,$ (D.5.28)

where $\mathcal{T}_{i}$ denotes the set of trees rooted at $i$ in the complete
graph on $I$.

######  Proposition D.3.

For any $\mu_{\mathcal{V}}$ invariant probability measure for
$\operatorname{\mathbb{Q}}_{\mathcal{V}}$, the induced chain on $\mathcal{V}$,
in the setting of Proposition D.2, for any $i\in I$,

$\mu_{\mathcal{V}}(\mathcal{V}_{i})\asymp\exp\left(-\frac{E(\mathcal{K}_{i})-\min_{j\in
I}E(\mathcal{K}_{j})}{\eta}\pm\frac{\varepsilon}{\eta}\right)\,.$ (D.5.29)

###### Proof.

If $\mu_{\mathcal{V}}$ is an invariant measure of
$\operatorname{\mathbb{Q}}_{\mathcal{V}}$, then it is an invariant measure of
$\operatorname{\mathbb{Q}}_{\mathcal{V}}^{N}$ for any $N$ given by Proposition
D.2.

Freidlin & Wentzell [20, Chap .6, Lem. 3.1-3.2] combined with Proposition D.2
then give

$\displaystyle\exp(-(2\operatorname{card}I+2)\varepsilon/\eta)\frac{\exp(-E(\mathcal{K}_{i})/\eta)}{\sum_{j\in
I}\exp(-E(\mathcal{K}_{j})/\eta)}$
$\displaystyle\leq\mu_{\mathcal{V}}(\mathcal{V}_{i})$
$\displaystyle\leq\exp((2\operatorname{card}I+2)\varepsilon/\eta)\frac{\exp(-E(\mathcal{K}_{i})/\eta)}{\sum_{j\in
I}\exp(-E(\mathcal{K}_{j})/\eta)}\,.$ (D.5.30)

For $\eta$ small enough, it holds that

$\sum_{j\in I}\exp(-E(\mathcal{K}_{j})/\eta)\asymp\exp\left(-\min_{j\in
I}E(\mathcal{K}_{j})/\eta\pm\varepsilon/\eta\right)\,,$ (D.5.31)

which concludes the proof. ∎

We now state a result that links invariant measures of $(x^{\eta}_{n})_{n}$
and $\operatorname{\mathbb{Q}}_{\mathcal{V}}$. It is a consequence of Douc et
al. [14, Thm. 3.6.5].

######  Lemma D.25.

There is $\eta_{0}>0$ such that, for $0<\eta\leq\eta_{0}$, if
$(x^{\eta}_{n})_{n}$ has an invariant probability measure $\mu_{\infty}$,
then, for any $\mathcal{V}$ measurable neighborhood of $\operatorname{crit}f$,
we have that $\mu_{\infty}(\mathcal{V})>0$ and $\mu_{\mathcal{V}}$, the
restriction of ${\mu_{\infty}}/{\mu_{\infty}(\mathcal{V})}$ to $\mathcal{V}$
is an invariant measure for the induced chain on $\mathcal{V}$ and, for any
measurable set $E\subset\mathcal{X}$,

$\frac{\mu_{\infty}(E)}{\mu_{\infty}(\mathcal{V})}=\int_{\mathcal{V}}\>d\mu_{\mathcal{V}}(x)\operatorname{\mathbb{E}}_{x}\left[\sum_{n=0}^{\sigma_{\mathcal{V}}-1}\operatorname{\mathds{1}}\\{x^{\eta}_{n}\in
E\\}\right]\,.$ (D.5.32)

###### Proof.

We invoke the first item of Lemma D.19: there exists
$\mathcal{D}\subset\mathcal{X}$ a compact set, $\eta_{0}>0$, such that for any
$\mathcal{D}^{\prime}\subset\mathcal{X}$ compact set such that
$\mathcal{D}\subset\mathcal{D}^{\prime}$, there exists $\alpha_{0}>0$ such
that,

$\forall\eta\leq\eta_{0},\,x\in\mathcal{D}^{\prime}\,,\quad\operatorname{\mathbb{E}}_{x}\left[e^{\frac{\alpha_{0}\sigma_{\mathcal{D}}}{\eta}}\right]<+\infty\,.$
(D.5.33)

Without loss of generality, at the potential expense of expanding
$\mathcal{D}$, assume that $\mathcal{V}\subset\mathcal{D}$.

By applying Lemma D.21 to $\mathcal{U}\leftarrow\mathcal{V}$ and
$\mathcal{D}\leftarrow\mathcal{D}$, we get that there is some
$\eta_{0},\alpha_{0},>0$ such that, for any $\eta\leq\eta_{0}$,
$x\in\mathcal{D}$,

$\operatorname{\mathbb{E}}_{x}\left[e^{\frac{\alpha\sigma_{\mathcal{V}}}{\eta}}\right]<+\infty\,.$
(D.5.34)

In particular, we have that
$\operatorname{\mathbb{P}}_{x}(\sigma_{\mathcal{V}}<\infty)=1$ for any
$x\in\mathcal{D}$, and _a fortiori_ for any $x\in\mathcal{V}$.

Let us now show that, for any $x\in\mathcal{X}$,
$\operatorname{\mathbb{P}}_{x}(\sigma_{\mathcal{V}}<\infty)=1$. Fix
$x\in\mathcal{X}$. By choosing $\mathcal{D}^{\prime}$ large enough to contain
both $\mathcal{D}$ and $x$, Eq. D.5.33 implies that, with $x_{0}=x$,
$\sigma_{\mathcal{D}}<\infty$ almost surely. Therefore, by the strong Markov
property, it holds that,

$\operatorname{\mathbb{P}}_{x}(\sigma_{\mathcal{V}}<\infty)\geq\inf_{z\in\mathcal{D}}\operatorname{\mathbb{P}}_{z}(\sigma_{\mathcal{V}}<\infty)=1\,.$
(D.5.35)

Therefore the assumptions of Douc et al. [14, Thm. 3.6.5] are satisfied as
well as its first item which yields the result. ∎

We reach the next proposition, which is the first part of our main result. It
is an adaptation of Freidlin & Wentzell [20, Thm. 4.1] to the discrete time
setting.

######  Proposition D.4.

For any $\varepsilon>0$, for any $\mathcal{V}_{1},\dots,\mathcal{V}_{K}$
measurable neighborhoods of $\mathcal{K}_{1},\dots,\mathcal{K}_{K}$ small
enough, there exists $\eta_{0}>0$ such that for any $0<\eta<\eta_{0}$,
$\mu_{\infty}$ invariant probability measure for $(x^{\eta}_{n})_{n}$, for any
$i\in I$,

$\mu_{\infty}(\mathcal{V}_{i})\asymp\exp\left(-\frac{E(\mathcal{K}_{i})-\min_{j\in
I}E(\mathcal{K}_{j})}{\eta}\pm\frac{\varepsilon}{\eta}\right)\,.$ (D.5.36)

###### Proof.

Let us first provide estimates for the unnormalized measure defined by, for
any measurable set $E$,

$\widetilde{\mu}(E)\coloneqq\int_{E}\>d\mu_{\mathcal{V}}(x)\operatorname{\mathbb{E}}_{x}\left[\sum_{n=0}^{\sigma_{\mathcal{V}}-1}\operatorname{\mathds{1}}\\{x^{\eta}_{n}\in
E\\}\right]\,.$ (D.5.37)

By definition of $\sigma_{\mathcal{V}}$, in the sequence of points
$x^{\eta}_{0},\dots,x^{\eta}_{\sigma_{\mathcal{V}}-1}$, only $x^{\eta}_{0}$
can be in $\mathcal{V}$. Therefore, for any $i,j\in I$, $x\in\mathcal{V}_{j}$,

$\operatorname{\mathbb{E}}_{x}\left[\sum_{n=0}^{\sigma_{\mathcal{V}}-1}\operatorname{\mathds{1}}\\{x^{\eta}_{n}\in\mathcal{V}_{i}\\}\right]=\begin{cases}1&\text{if
}i=j\,,\\\ 0&\text{otherwise}\,.\end{cases}$ (D.5.38)

Thus, we have that,

$\displaystyle\widetilde{\mu}(\mathcal{V}_{i})$
$\displaystyle=\mu_{\mathcal{V}}(\mathcal{V}_{i})$
$\displaystyle\asymp\exp\left(-\frac{E(\mathcal{K}_{i})-\min_{j\in
I}E(\mathcal{K}_{j})}{\eta}\pm\frac{\varepsilon}{\eta}\right)\,,$ (D.5.39)

by Proposition D.3. It now remains to estimate the normalization constant
$\widetilde{\mu}(\mathcal{X})$. On the one hand, we have that

$\displaystyle\widetilde{\mu}(\mathcal{X})$ $\displaystyle\geq\max_{i\in
I}\widetilde{\mu}(\mathcal{V}_{i})$ $\displaystyle\geq\max_{i\in
I}\exp\left(-\frac{E(\mathcal{K}_{i})-\min_{j\in
I}E(\mathcal{K}_{j})}{\eta}-\frac{\varepsilon}{\eta}\right)=\exp\left(-\frac{\varepsilon}{\eta}\right)\,.$
(D.5.40)

On the other hand, by Lemma D.21 applied with
$\mathcal{U}\leftarrow\mathcal{V}$ and
$\mathcal{D}\leftarrow\operatorname{cl}{\mathcal{V}}$ (choosing $\mathcal{V}$
small enough so that is bounded), the quantity

$c\coloneqq\sup\\{\operatorname{\mathbb{E}}_{x}[\sigma_{\mathcal{V}}]:x\in\mathcal{V},\,0<\eta\leq\eta_{0}\\}$
(D.5.41)

is finite. Therefore, we have that

$\displaystyle\widetilde{\mu}(\mathcal{X})$
$\displaystyle=\int_{\mathcal{X}}\>d\mu_{\mathcal{V}}(x)\operatorname{\mathbb{E}}_{x}\left[\sigma_{\mathcal{V}}\right]$
$\displaystyle\leq c\int_{\mathcal{X}}\>d\mu_{\mathcal{V}}(x)=c\,,$ (D.5.42)

which, along with choosing $\eta_{0}$ small enough so that
$c\leq\exp(\varepsilon/\eta)$, concludes the proof. ∎

We will need the following lemma to prove the second part of our main result.

######  Lemma D.26.

For any $\varepsilon>0$, for any $\mathcal{V}_{1},\dots,\mathcal{V}_{K}$
measurable neighborhoods of $\mathcal{K}_{1},\dots,\mathcal{K}_{K}$ small
enough, $D$ measurable set, $\delta_{D}>0$, there exists $\eta_{0}>0$ such
that, for any $0<\eta<\eta_{0}$, for any $i\in I$, $x\in\mathcal{V}_{i}$,

$\operatorname{\mathbb{P}}_{x}\left(\sigma_{D_{-\delta_{D}}}<\sigma_{\mathcal{V}}\right)\leq\exp\left(-\frac{B(\mathcal{K}_{i},D)-\varepsilon}{\eta}\right)\,,$
(D.5.43)

where

$D_{-\delta_{D}}\coloneqq\left\\{z\in D:d(z,\mathcal{X}\setminus
D)\geq\delta_{D}\right\\}\,.$ (D.5.44)

###### Proof.

The requirement on the $\mathcal{V}_{i}$ are the same in the proof of Lemma
D.22 but we restate them here for completeness.

Assume that, without loss of generality, $\varepsilon$ is small enough so that
Lemma D.8 with $r\leftarrow\varepsilon$ can be applied to every
$\mathcal{K}_{i}$, $i=1,\dots,K$. Denote by $\mathcal{W}_{i}$, $i=1,\dots,K$
the corresponding neighborhoods of $\mathcal{K}_{i}$. Since these
$\mathcal{W}_{i}$’s are neighborhoods of the $\mathcal{K}_{i}$’s, there exists
$\delta>0$ such that
$\mathcal{U}_{2\delta}(\mathcal{K}_{i})\subset\mathcal{W}_{i}$ for all
$i=1,\dots,K$. Require then that $\mathcal{V}_{i}$ be contained in
$\mathcal{U}_{\delta}(\mathcal{K}_{i})$ so that
$\mathcal{U}_{\delta}(\operatorname{cl}\mathcal{V}_{i})\subset\mathcal{W}_{i}$
for all $i=1,\dots,K$. Moreover, assume that $\delta>0$ is small enough so
that the neighborhoods $\mathcal{U}_{\delta}(\mathcal{K}_{i})$, $i=1,\dots,K$
are pairwise disjoint and that $\delta\leq\delta_{D}$. Define
$0<\delta^{\prime}\leq\delta$ such that
$\mathcal{U}_{\delta}^{\prime}(\mathcal{K}_{i})$ is contained in
$\mathcal{V}_{i}$ for all $i=1,\dots,K$.

Fix $i\in I$ and consider $\xi\in(\mathcal{X})^{N}$ such that
$\xi_{0}\in\mathcal{U}_{\delta}^{\prime}(\operatorname{cl}\mathcal{V}_{i})$,
$\xi_{N-1}\in\mathcal{U}_{\delta}^{\prime}(D_{-\delta_{D}})$. By construction,
$\xi_{0}\in\mathcal{U}_{\delta}(\mathcal{V}_{i})\subset\mathcal{W}_{i}$.
Therefore, there exists $x\in\mathcal{K}_{i}$ such that
$\rho(x,\xi_{0})<\varepsilon$. Moreover, since
$\delta^{\prime}\leq\delta\leq\delta_{D}$,
$\mathcal{U}_{\delta}^{\prime}(D_{-\delta_{D}})\subset D$ so that
$\xi_{N-1}\in D$.

Define $\zeta\coloneqq(x,\xi_{0},\dots,\xi_{N-1})$ which is a path from
$\mathcal{K}_{i}$ to $D$ so that

$\mathcal{A}_{N}(\xi)\geq\mathcal{A}_{N+1}(\zeta)-\varepsilon\geq
B\left(\mathcal{K}_{i},D\right)-\varepsilon\,.$ (D.5.45)

We now follow the same outline as for the proof of Lemma D.22. Fix
$x\in\mathcal{V}_{i}$. For any $N\geq 0$, we have that

$\displaystyle\operatorname{\mathbb{P}}_{x}\left(\sigma_{D_{-\delta_{D}}}<\sigma_{\mathcal{V}}\right)$
$\displaystyle\leq\operatorname{\mathbb{P}}_{x}\left(\sigma_{D_{-\delta_{D}}}<\sigma_{\mathcal{V}}\,,\sigma_{\mathcal{V}}<N\right)+\operatorname{\mathbb{P}}_{x}\left(\sigma_{\mathcal{V}}\geq
N\right)\,.$ (D.5.46)

For some $N$ large enough, Lemma D.21 yields

$\operatorname{\mathbb{P}}_{x}\left(\sigma_{\mathcal{V}}\geq
N\right)\leq\exp\left(-\frac{B\left(\mathcal{K}_{i},D\right)-\varepsilon}{\eta}\right)\,.$
(D.5.47)

We now bound
$\operatorname{\mathbb{P}}_{x}\left(\sigma_{D_{-\delta_{D}}}<\sigma_{\mathcal{V}}\,,\sigma_{\mathcal{V}}<N\right)$
for this choice of $N$. For this, it suffices to note that
$\sigma_{D_{-\delta_{D}}}<\sigma_{\mathcal{V}}\,,\sigma_{\mathcal{V}}<N$
implies that
$\operatorname{dist}_{N}\left(x^{\eta},\Gamma_{N}^{\\{x\\}}\left(\xi-2\varepsilon\right)\right)>{\frac{\delta^{\prime}}{2}}$.
Then, applying Corollary C.2 yields

$\operatorname{\mathbb{P}}_{x}\left(\sigma_{D_{-\delta_{D}}}<\sigma_{\mathcal{V}}\,,\sigma_{\mathcal{V}}<N\right)\leq\exp\left(-\frac{B\left(\mathcal{K}_{i},D\right)-3\varepsilon}{\eta}\right)\,,$
(D.5.48)

which concludes the proof. ∎

We can use this lemma to upper-bound the $\mu_{\infty}(D)$.

######  Lemma D.27.

For any $\varepsilon>0$, any bounded measurable set $D$, there exists
$\eta_{0}>0$ such that for any $0<\eta<\eta_{0}$, $\mu_{\infty}$ invariant
probability measure for $(x^{\eta}_{n})_{n}$, for any $i\in I$,

$\mu_{\infty}(D_{-\delta_{D}})\leq\exp\left(-\frac{\min_{i\in
I}\left\\{E(\mathcal{K}_{i})+B\left(\mathcal{K}_{i},D\right)\right\\}-\min_{i\in
I}E(\mathcal{K}_{i})}{\eta}+\frac{\varepsilon}{\eta}\right)\,,$ (D.5.49)

where

$D_{-\delta_{D}}\coloneqq\left\\{z\in\mathcal{X}:d(z,\mathcal{X}\setminus
D)\geq\delta_{D}\right\\}\,.$ (D.5.50)

###### Proof.

Using $\mathcal{V}_{1},\dots,\mathcal{V}_{K}$ measurable neighborhoods of
$\mathcal{K}_{1},\dots,\mathcal{K}_{K}$ small enough given by Lemma D.26, we
provide an estimate for the weight of $D$ for the unnormalized measure
$\widetilde{\mu}$ defined in the proof of Proposition D.4, i.e., for

$\widetilde{\mu}(D_{-\delta_{D}})\coloneqq\int_{\mathcal{V}}\>d\mu_{\mathcal{V}}(x)\operatorname{\mathbb{E}}_{x}\left[\sum_{n=0}^{\sigma_{\mathcal{V}}-1}\operatorname{\mathds{1}}\\{x^{\eta}_{n}\in
D_{-\delta_{D}}\\}\right]\,,$ (D.5.51)

and the result will follow from the estimate on the normalization constant
$\widetilde{\mu}(\mathcal{X})$ obtained in the proof of Proposition D.4.

By Lemma D.21 applied with $\mathcal{U}\leftarrow\mathcal{V}$ and
$\mathcal{D}\leftarrow\operatorname{cl}{\mathcal{V}\cup D}$ (choosing
$\mathcal{V}$ small enough so that is bounded), the quantity

$c\coloneqq\sup\\{\operatorname{\mathbb{E}}_{x}[\sigma_{\mathcal{V}}]:x\in\mathcal{V}\cup
D,\,0<\eta\leq\eta_{0}\\}$ (D.5.52)

is finite.

Fix $i\in I$ and $x\in\mathcal{V}_{i}$. If
$\sigma_{D_{-\delta_{D}}}\geq\sigma_{\mathcal{V}}$, then
$\sum_{n=0}^{\sigma_{\mathcal{V}}-1}\operatorname{\mathds{1}}\\{x^{\eta}_{n}\in
D_{-\delta_{D}}\\}$ would be 0 so, we have that

$\displaystyle\operatorname{\mathbb{E}}_{x}\left[\sum_{n=0}^{\sigma_{\mathcal{V}}-1}\operatorname{\mathds{1}}\\{x^{\eta}_{n}\in
D_{-\delta_{D}}\\}\right]$
$\displaystyle=\operatorname{\mathbb{E}}_{x}\left[\operatorname{\mathds{1}}\\{\sigma_{D_{-\delta_{D}}}<\sigma_{\mathcal{V}}\\}\sum_{n=0}^{\sigma_{\mathcal{V}}-1}\operatorname{\mathds{1}}\\{x^{\eta}_{n}\in
D_{-\delta_{D}}\\}\right]$
$\displaystyle\leq\operatorname{\mathbb{E}}_{x}\left[\operatorname{\mathds{1}}\\{\sigma_{D_{-\delta_{D}}}<\sigma_{\mathcal{V}}\\}\sigma_{\mathcal{V}}\right]$
$\displaystyle=\operatorname{\mathbb{E}}_{x}\left[\operatorname{\mathds{1}}\\{\sigma_{D_{-\delta_{D}}}<\sigma_{\mathcal{V}}\\}\left(\sigma_{D_{-\delta_{D}}}+\operatorname{\mathbb{E}}_{x^{\eta}_{\sigma_{D_{-\delta_{D}}}}}\left[\sigma_{\mathcal{V}}\right]\right)\right]\,,$
(D.5.53)

where we used the strong Markov property. Bounding $\sigma_{D_{-\delta_{D}}}$
by $\sigma_{\mathcal{V}}$ on the event
$\\{\sigma_{D_{-\delta_{D}}}<\sigma_{\mathcal{V}}\\}$, we obtain that

$\displaystyle\operatorname{\mathbb{E}}_{x}\left[\sum_{n=0}^{\sigma_{\mathcal{V}}-1}\operatorname{\mathds{1}}\\{x^{\eta}_{n}\in
D_{-\delta_{D}}\\}\right]$
$\displaystyle\leq\operatorname{\mathbb{E}}_{x}\left[\operatorname{\mathds{1}}\\{\sigma_{D_{-\delta_{D}}}<\sigma_{\mathcal{V}}\\}\left(\sigma_{\mathcal{V}}+\operatorname{\mathbb{E}}_{x^{\eta}_{\sigma_{\mathcal{V}}}}\left[\sigma_{\mathcal{V}}\right]\right)\right]$
$\displaystyle\leq
2c\operatorname{\mathbb{P}}_{x}\left(\sigma_{D_{-\delta_{D}}}<\sigma_{\mathcal{V}}\right)$
$\displaystyle\leq
2c\exp\left(-\frac{B\left(\mathcal{K}_{i},D\right)-\varepsilon}{\eta}\right)\,,$
(D.5.54)

where we invoked Lemma D.26 for the last inequality.

Combining this bound and Proposition D.3, we obtain that

$\displaystyle\widetilde{\mu}(D_{-\delta_{D}})$ $\displaystyle\leq
2c\sum_{i\in
I}\mu_{\mathcal{V}}(\mathcal{V}_{i})\exp\left(-\frac{B\left(\mathcal{K}_{i},D\right)-\varepsilon}{\eta}\right)$
$\displaystyle\leq 2c\operatorname{card}I\exp\left(-\frac{\min_{i\in
I}\left\\{E(\mathcal{K}_{i})+B\left(\mathcal{K}_{i},D\right)\right\\}-\min_{i\in
I}E(\mathcal{K}_{i})}{\eta}+\frac{2\varepsilon}{\eta}\right)\,,$ (D.5.55)

which concludes the proof. ∎

###  D.6. Convergence and stability

Let us first begin by showing that, for every initial point, the flow of $f$
converges to one of the $\mathcal{K}_{i}$.

######  Lemma D.28.

For any $x\in\mathcal{X}$, there is $i\in I$ such that

$\lim_{t\to+\infty}d(\Theta_{t}(x),\mathcal{K}_{i})=0.$ (D.6.1)

###### Proof.

Fix $x\in\mathcal{X}$. For any $t\geq 0$, $\Theta_{t}(x)$ belongs to
$\\{z\in\mathcal{X}:f(z)\leq f(x)\\}$, which is compact by coercivity of $f$.
Therefore, the set of accumulation points of
$\left(\Theta_{t}(x)\right)_{t\geq 0}$ is non-empty, connected and included in
$\operatorname{crit}f$. Therefore, since the $\mathcal{K}_{i}$, for $i\in I$,
are the connected components of $\operatorname{crit}f$, there is $i\in I$ such
that the accumulation points of $\left(\Theta_{t}(x)\right)_{t\geq 0}$ all
belong to $\mathcal{K}_{i}$.

If $d(\Theta_{t}(x),\mathcal{K}_{i})$ did not converge to $0$, there would be
a subsequence that would converge to some point out of any $\mathcal{K}_{i}$,
which would be a contradiction. Therefore, $d(\Theta_{t}(x),\mathcal{K}_{i})$
must converge to $0$. ∎

Let us restate the definition of minimizing component that we introduced in
the main text.

######  Definition 9.

For any $i\in I$, we say that $\mathcal{K}_{i}$ is a _minimizing component_ if
there exists $\mathcal{U}$ a neighborhood of $\mathcal{K}_{i}$ such that,

$\operatorname*{arg\,min}_{x\in\mathcal{U}}f(x)=\mathcal{K}_{i}\,.$ (D.6.2)

$\mathcal{K}_{i}$ is called minimizing otherwise.

We now state a standard definition for asymptotic stability.

######  Definition 10.

A connected component of the critical points $\mathcal{K}_{i}$, for some $i\in
I$, is said to be _asymptotically stable_ if there exists $\mathcal{U}$ a
neighborhood of $\mathcal{K}_{i}$ such that, for any $x\in\mathcal{U}$,
$\Theta_{t}(x)$ converges to $\mathcal{K}_{i}$.

The notions of minimizing component and asymptotic stability are equivalent in
our context.

######  Lemma D.29.

For any $i\in I$, $\mathcal{K}_{i}$ is a minimizing component if and only if
it is asymptotically stable.

###### Proof.

We start with the direct implication. Assume that $\mathcal{K}_{i}$ is a
minimizing component. Therefore, there exists $\delta>0$ such that

$\operatorname*{arg\,min}_{x\in\operatorname{cl}\mathcal{U}_{\delta}(\mathcal{K}_{i})}f(x)=\mathcal{K}_{i}\,.$
(D.6.3)

Moreover, assume that $\delta$ is small enough so that,
$\operatorname{cl}\mathcal{U}_{\delta}(\mathcal{K}_{i})\cap\operatorname{crit}f=\mathcal{K}_{i}$.

Then, for any $x\in\mathcal{U}_{\delta}(\mathcal{K}_{i})$,
$f(x)<f(\mathcal{K}_{i})$ and, for any
$x\in\mathcal{X}\setminus\operatorname{cl}\mathcal{U}_{\delta}(\mathcal{K}_{i})$,
$f(x)>f(\mathcal{K}_{i})$. By continuity of $f$, compactness of
$\operatorname{cl}\mathcal{U}_{\delta}(\mathcal{K}_{i})\setminus\mathcal{U}_{\delta/2}(\mathcal{K}_{i})$
and definition of minimizing component, we have that

$\min_{x\in\operatorname{cl}\mathcal{U}_{\delta}(\mathcal{K}_{i})\setminus\mathcal{U}_{\delta/2}(\mathcal{K}_{i})}f(x)>f(\mathcal{K}_{i})\,.$
(D.6.4)

Define
$\delta^{\prime}\coloneqq{\frac{1}{2}}\min_{x\in\operatorname{cl}\mathcal{U}_{\delta}(\mathcal{K}_{i})\setminus\mathcal{U}_{\delta/2}(\mathcal{K}_{i})}\left\\{f(x)-f(\mathcal{K}_{i})\right\\}$
and

$\mathcal{V}\coloneqq\left\\{x\in\mathcal{U}_{\delta/2}(\mathcal{K}_{i}):f(x)<f(\mathcal{K}_{i})+\delta^{\prime}\right\\}\,,$
(D.6.5)

which is a neighborhood of $\mathcal{K}_{i}$ by continuity of $f$.

We now show that trajectories of the flow starting in $\mathcal{V}$ converge
to $\mathcal{K}_{i}$. Take $x\in\mathcal{V}$. Since $f(\Theta_{t}(x))$ is non-
increasing, then $(\Theta_{t}(x))_{t}$ remains in $\mathcal{V}$ by
construction. By Lemma D.28, $(\Theta_{t}(x))_{t}$ converges to some component
of the critical points, which must be $\mathcal{K}_{i}$ since $\mathcal{V}$ is
disjoint from the other components.

We now show the converse implication. Since $\mathcal{K}_{i}$ is a connected
component of $\operatorname{crit}f$, $f$ is constant on $\mathcal{K}_{i}$.
Denote by $f_{i}^{\ast}$ this value. Take $\delta>0$ small enough such that
$\mathcal{U}_{\delta}(\mathcal{K}_{i})\cap\operatorname{crit}f=\mathcal{K}_{i}$
and such that, for any $x\in\mathcal{U}_{\delta}(\mathcal{K}_{i})$,
$(\Theta_{t}(x))_{t}$ converges to $\mathcal{K}_{i}$. Take
$x\in\mathcal{U}_{\delta}(\mathcal{K}_{i})\setminus\mathcal{K}_{i}$. We show
that $f(x)>f_{i}^{\ast}$. For any $t>0$,

$f(\Theta_{t}(x))-f(\mathcal{K}_{i})=-\int_{0}^{t}\lVert\nabla
f(\Theta_{s}(x))\rVert^{2}\>ds\,,$ (D.6.6)

which must (strictly) negative since $x$ is not a critical point of $f$. Since
$f(\Theta_{t}(x))$ is non-increasing in $t$ and lower-bounded — because
$\inf_{\mathcal{X}}f>-\infty$ by coercivity of $f$ —, it must converge as
$t\to+\infty$ and its limit satisfies
$\lim_{t\to+\infty}f(\Theta_{t}(x))<f(x)$. Moreover, $(\Theta_{t}(x))_{t}$
converges to $\mathcal{K}_{i}$ so that all its accumulation points belong to
$\mathcal{K}_{i}$ and have the same objective value $f_{i}^{\ast}$. Hence, we
have that $\lim_{t\to+\infty}f(\Theta_{t}(x))=f_{i}^{\ast}$ and
$f_{i}^{\ast}<f(x)$. ∎

In the following, we will thus use the terms minimizing component and
asymptotically stable interchangeably.

The next lemma shows that if $\mathcal{K}_{i}$ is not asymptotically stable,
then it is unstable in the sense of Freidlin & Wentzell [20, Chap. 6,§4].

######  Lemma D.30.

If $\mathcal{K}_{i}$ is not asymptotically stable, then there exists $j\in I$
such that $B_{i,j}=0$.

###### Proof.

If $\mathcal{K}_{i}$ is not asymptotically stable, then, for every $n\geq 1$,
there exists $x_{n}\in\mathcal{U}_{1/n}(\mathcal{K}_{i})$ such that
$\Theta_{t}(x_{n})$ does not converge to $\mathcal{K}_{i}$. By Lemma D.28,
there exists $j_{n}\in I$ such that $(\Theta_{t}(x_{n}))_{t}$ converges to
$\mathcal{K}_{j_{n}}$. Since $I$ is finite, there exists $j\in I$ such that
$j_{n}=j$ for infinitely many $n$. Replacing $(x_{n})_{n\geq 1}$ by a
subsequence, we can assume that $(\Theta_{t}(x_{n}))_{t}$ converges to
$\mathcal{K}_{j}$ for all $n\geq 1$.

We now show that $B_{i,j}=0$.

Fix $\varepsilon>0$ and consider
$\mathcal{W}_{\varepsilon}(\mathcal{K}_{i}),\mathcal{W}_{\varepsilon}(\mathcal{K}_{j})$
which are neighborhoods of $\mathcal{K}_{i},\mathcal{K}_{j}$ by Lemma D.8.
Since $(x_{n})_{n\geq 1}$ converges to $\mathcal{K}_{i}$, there exists $n$
such that $x_{n}\in\mathcal{W}_{\varepsilon}(\mathcal{K}_{i})$. In turn, since
$\Theta_{t}(x_{n})$ converges to $\mathcal{K}_{j}$, there exists $T>0$, which
we can choose integer, such that,
$\Theta_{T}(x_{n})\in\mathcal{W}_{\varepsilon}(\mathcal{K}_{j})$. Therefore,
there exists $x\in\mathcal{K}_{i}$ and $z\in\mathcal{K}_{j}$ such that
$\rho(x,x_{n})<\varepsilon$ and $\rho(\Theta_{T}(x_{n}),z)<\varepsilon$.
Consider the discrete path $\xi\in\mathcal{X}^{T+3}$ defined by $\xi_{0}=x$,
$\xi_{n}=\Theta_{n-1}(x)$ for all $1\leq n\leq T+1$ and $\xi_{T+2}=z$. By
Lemma D.2, we have that

$\mathcal{A}_{T+3}(\xi)=\rho(x,x_{n})+\rho(\Theta_{T}(x),z)<2\varepsilon\,,$
(D.6.7)

and therefore, since $\xi_{0}\in\mathcal{K}_{i}$ and
$\xi_{T+2}\in\mathcal{K}_{j}$, $B_{i,j}<2\varepsilon$. ∎

The following lemma is now a straightforward adaptation of Freidlin & Wentzell
[20, Chap. 6, Lemma 4.2].

######  Lemma D.31.

If $\mathcal{K}_{i}$ is not asymptotically stable, then there exists $j\in I$
such that $B_{i,j}=0$ and such that, for any $l\in I$, $B_{j,l}>0$.

###### Proof.

For the sake of contradiction, assume that such a $j$ does not exist. Then we
build an infinite sequence $j_{0}=i,j_{1},\dots$ such that
$B_{j_{n},j_{n+1}}=0$ for all $n\geq 0$. By definition of equivalence classes,
any $j$ cannot appear twice in this sequence. But since $I$ is finite, this is
a contradiction. ∎

We now reach our final result on unstable equivalence classes: they have
negligible weight in the invariant measure.

######  Lemma D.32.

If $\mathcal{K}_{i}$ is not asymptotically stable, or, equivalently, non-
minimizing, then there exists $j\in I$ such that $\mathcal{K}_{j}$ is
asymptotically stable, $B_{i,j}=0$ and,

$E_{j}<E_{i}$ (D.6.8)

###### Proof.

By Lemma D.31, there exists $j\in I$ such that $B_{i,j}=0$ and such that, for
any $l\in I$, $B_{j,l}>0$. Lemma D.30 implies in particular that
$\mathcal{K}_{j}$ must be asymptotically stable

It remains to show that $E_{j}<E_{i}$. Take $T\in\mathcal{T}_{i}$ such that

$E_{i}=\sum_{(l\to k)\in T}B_{l,k}\,.$ (D.6.9)

$j$ has an outgoing edge in $T$ and denote by $j^{\prime}$ the other end of
that edge. Now, consider the tree $T^{\prime}\in\mathcal{T}_{j}$ obtained from
$T$ by removing the outgoing edge from $j$ to $i^{\prime}$ and adding an edge
from $i$ to $j$. Then, by definition of $E_{j}$,

$\displaystyle E_{j}$ $\displaystyle\leq\sum_{(l\to k)\in
T^{\prime}}B_{l,k}=\sum_{(l\to k)\in T}B_{l,k}-B_{j,j^{\prime}}+B_{i,j}\,.$
(D.6.10)

But, by definition of $j$, $B_{i,j}=0$ and $B_{j,j^{\prime}}>0$. Therefore,
$E_{j}<E_{i}$. ∎

We now show the second part of our main result: the invariant measure
concentrates on the ground states, which are asymptotically stable by Lemma
D.32.

For this, we need the following lemma.

######  Lemma D.33.

For any $i\in I$ such that $\mathcal{K}_{i}$ is minimizing, there exists
$\delta>0$ such that, for any $0<\delta^{\prime}\leq\delta$,

$B(\mathcal{K}_{i},\mathcal{X}\setminus\mathcal{U}_{\delta}^{\prime}(\mathcal{K}_{i}))>0\,.$
(D.6.11)

###### Proof.

Since $\mathcal{K}_{i}$ is minimizing, there exists $\delta>0$ such that, for
any $x\in\mathcal{U}_{\delta}(\mathcal{K}_{i})$, $f(x)>f_{i}$ where $f_{i}$ is
the value of $f$ on $\mathcal{K}_{i}$. Take $\delta^{\prime}\leq\delta$,
$\mathcal{U}\coloneqq\mathcal{U}_{\delta}^{\prime}(\mathcal{K}_{i})$ and

$\Delta\coloneqq\min\left\\{U_{\infty}(x)-\alpha_{\infty}(f_{i}):x\in\mathcal{X},\,d(x,\mathcal{K}_{i})=\delta^{\prime}/2\right\\}\,.$
(D.6.12)

Then, by the continuity of $U_{\infty}$ and the fact that $\alpha_{\infty}$ is
(strictly) increasing, we have that $\Delta>0$. To conclude the proof of this
lemma, we now show that
$B(\mathcal{K}_{i},\mathcal{X}\setminus\mathcal{U})\geq{\frac{\Delta}{2}}$.
Consider some $T>0$ and $\gamma\in\mathcal{C}([0,T],\mathcal{X})$ such that
$\gamma_{0}\in\mathcal{K}_{i}$ and
$\gamma_{T}\in\mathcal{X}\setminus\mathcal{W}$. By continuity of $\gamma$ and
$d(\cdot,\mathcal{K}_{i})$, there exists $t\in[0,T]$ such that
$d(\gamma_{t},\mathcal{K}_{i})=\delta^{\prime}/2$. By the same computation as
in Lemma D.6, we have that

$\displaystyle\Delta$ $\displaystyle\leq
U_{\infty}(\gamma_{t})-U_{\infty}(\gamma_{0})$
$\displaystyle=2\int_{0}^{t}\frac{\langle\dot{\gamma}_{s},\nabla
f(\gamma_{s})\rangle}{\sigma_{\infty}^{2}(f(\gamma_{s}))}$ $\displaystyle\leq
2\mathcal{S}_{[0,t]}(\gamma)$ $\displaystyle\leq
2\mathcal{S}_{[0,T]}(\gamma)\,.$ (D.6.13)

Since this is valid for any $\gamma$, we obtain that
$B(\mathcal{K}_{i},\mathcal{X}\setminus\mathcal{U})\geq{\frac{\Delta}{2}}$. ∎

The next proposition shows that the invariant measure concentrates
exponentially on states that are asymptotically stable (and contain the ground
states).

######  Proposition D.5.

Consider $J\subset I$ such that, for all $i\in J$, $\mathcal{K}_{i}$ is
minimizing and, such that, $J$ contains $\operatorname*{arg\,min}_{i\in
I}E_{i}$. Consider $\mathcal{V}_{i}$ small enough neighborhoods of
$\mathcal{K}_{i}$ for $i\in J$. Then, there exists $c>0$, $\eta_{0}>0$ such
that, for any $\eta\leq\eta_{0}$, for any $\mu_{\infty}$ invariant measure of
$(x^{\eta}_{n})_{n\geq 0}$,

$\mu_{\infty}\left(\mathcal{X}\setminus\bigcup_{i\in
J}\mathcal{V}_{i}\right)\leq e^{-\frac{c}{\eta}}\,.$ (D.6.14)

###### Proof.

Take $\delta>0$ small enough so that, for any $i\in J$,
$\mathcal{U}_{\delta}(\mathcal{K}_{i})\subset\mathcal{V}_{i}$ and

$d(\mathcal{K}_{i},\mathcal{X}\setminus\mathcal{U}_{\delta}(\mathcal{K}_{i}))>0\,.$
(D.6.15)

This is possible by Lemma D.33.

Define

$D\coloneqq\mathcal{X}\setminus\bigcup_{i\in
J}\mathcal{U}_{\delta/2}(\mathcal{K}_{i})\,.$ (D.6.16)

With the notations of Lemma D.27, we show that

$\mathcal{X}\setminus\bigcup_{i\in J}\mathcal{V}_{i}\subset D_{-\delta/2}\,.$
(D.6.17)

Indeed, take $x\in\mathcal{X}\setminus\bigcup_{i\in J}\mathcal{V}_{i}$. Then,
for any $i\in J$, it holds that $d(x,\mathcal{K}_{i})\geq\delta$ and so, we
have

$d(x,\mathcal{X}\setminus D)=d\left(x,\mathcal{X}\setminus\bigcup_{i\in
J}\mathcal{U}_{\delta/2}(\mathcal{K}_{i})\right)\geq\frac{\delta}{2}\,.$
(D.6.18)

Hence $x\in D_{-\delta/2}$ and, it suffices to bound
$\mu_{\infty}(D_{-\delta/2})$ to show the result.

Moreover, for any $i\in J$,

$B(\mathcal{K}_{i},D)\geq
B(\mathcal{K}_{i},\mathcal{X}\setminus\mathcal{U}_{\delta/2}(\mathcal{K}_{i}))>0\,,$
(D.6.19)

so that the quantity

$c\coloneqq\min\left(\min_{i\notin J}E_{i}-\min_{i\in I}E_{i},\min_{i\in
J}B(\mathcal{K}_{i},D)\right)$ (D.6.20)

is positive.

Apply Lemma D.27 with $\delta_{D}\leftarrow\delta/2$, $\varepsilon\leftarrow
c/2$ to get that, for any $\eta\leq\eta_{0}$,

$\mu_{\infty}(D_{-\delta/2})\leq\exp\left(-\frac{\min_{i\in
I}\left\\{E(\mathcal{K}_{i})+B\left(\mathcal{K}_{i},D\right)\right\\}-\min_{j\in
I}E(\mathcal{K}_{j})}{\eta}+\frac{c}{2\eta}\right)\,.$ (D.6.21)

But, for any $i\in I$, the exponent can be estimated as

$\left\\{E(\mathcal{K}_{i})+B\left(\mathcal{K}_{i},D\right)\right\\}-\min_{j\in
I}E(\mathcal{K}_{i})\geq\begin{cases}E(\mathcal{K}_{i})-\min_{j\in
I}E(\mathcal{K}_{j})&\text{if }i\notin J\\\ B(\mathcal{K}_{i},D)&\text{if
}i\in J\,,\end{cases}$ (D.6.22)

which is always positive, even in the first case, since
$\operatorname*{arg\,min}_{j\in I}E(\mathcal{K}_{j})\subset J$. Therefore, it
holds that

$\min_{i\in
I}\left\\{E(\mathcal{K}_{i})+B\left(\mathcal{K}_{i},D\right)\right\\}-\min_{j\in
I}E(\mathcal{K}_{j})-\varepsilon\geq c-\varepsilon=\frac{c}{2}\,,$ (D.6.23)

which concludes the proof. ∎

###  D.7. Main results

In this section, we restate the main results Theorems 1, 2, 3 and 4 and
provide their proofs. They are now mostly corollaries of the results of
Sections D.5 and D.6.

######  Theorem D.1.

Suppose that $\mu_{\infty}$ is invariant under (SGD), fix a tolerance level
$\varepsilon>0$, and let $\mathcal{U}_{i}\equiv\mathcal{U}_{i}(\delta)$,
$i=1,\dotsc,K$, be $\delta$-neighborhoods of the components of
$\operatorname{crit}f$. Then, for all sufficiently small $\delta,\eta>0$, we
have

$\left\lvert\eta\log\mu_{\infty}(\mathcal{U}_{i})+E_{i}-\min\nolimits_{j}E_{j}\right\rvert\leq\varepsilon$
(D.7.1)

and

$\left\lvert\eta\log\frac{\mu_{\infty}(\mathcal{U}_{i})}{\mu_{\infty}(\mathcal{U}_{j})}+E_{i}-E_{j}\right\rvert\leq\varepsilon.$
(D.7.2)

More compactly, with notation as above, we have:

$\mu_{\infty}(\mathcal{U}_{i})\propto\exp\left(-\frac{E_{i}+\operatorname{\mathcal{O}}(\varepsilon)}{\eta}\right).$
(D.7.3)

###### Proof.

Note that if $\mu_{\infty}$ is invariant for (SGD), it is _a fortiori_
invariant for the accelerated process $(x^{\eta}_{n})_{n\geq 0}$. This result
is then a direct consequence of Proposition D.4 (Section D.5). ∎

######  Theorem D.2.

Suppose that $\mu_{\infty}$ is invariant under (SGD), and let $\mathcal{K}$ be
a non-minimizing component of $f$. Then, with notation as in Theorem 1, there
exists a minimizing component $\mathcal{K}^{\prime}$ of $f$ and a positive
constant $c\equiv c(\mathcal{K},\mathcal{K}^{\prime})>0$ such that

$\frac{\mu_{\infty}(\mathcal{U})}{\mu_{\infty}(\mathcal{U}^{\prime})}\leq\exp\left(-\frac{c(\mathcal{K},\mathcal{K}^{\prime})+\varepsilon}{\eta}\right)$
(D.7.4)

for all all sufficiently small $\eta>0$ and all sufficiently small
neighborhoods $\mathcal{U}$ and $\mathcal{U}^{\prime}$ of $\mathcal{K}$ and
$\mathcal{K}^{\prime}$ respectively. In particular, in the limit $\eta\to 0$,
we have $\mu_{\infty}(\mathcal{U})\to 0$.

###### Proof.

Let $\mathcal{K}=\mathcal{K}_{i}$ be a non-minimizing component. By Lemma
D.32, there exists $j\in I$ such that $E_{j}<E_{i}$. The statement then
follows from Theorem 1. ∎

######  Theorem D.3.

Suppose that $\mu_{\infty}$ is invariant under (SGD), fix a tolerance level
$\delta>0$, and let $\mathcal{U}\equiv\mathcal{U}(\delta)$ be a
$\delta$-neighborhood of $\operatorname{crit}f$. Then there exists a constant
$c\equiv c_{\delta}>0$ such that, for all sufficiently small $\eta>0$, we
have:

$\mu_{\infty}(\mathcal{U})\geq 1-e^{-c/\eta}.$ (D.7.5)

###### Proof.

We actually show a slighly stronger result. Define $J\coloneqq\left\\{i\in
I:\mathcal{K}_{i}\text{ is minimizing}\right\\}$. We prove that there exists
$\mathcal{U}$ neighborhood of $\bigcup_{i\in J}\mathcal{K}_{i}$, a constant
$c>0$, such that, for all $\eta$ small enough,

$\mu_{\infty}\left(\mathcal{X}\setminus\bigcup_{i\in
J}\mathcal{V}_{i}\right)\leq e^{-\frac{c}{\eta}}\,.$ (D.7.6)

This is then a consequence of Proposition D.5 (Section D.6) with $J\leftarrow
J$. Note $J$ contain the ground states since they are minimizing by Lemma
D.32. ∎

######  Theorem D.4.

Suppose that $\mu_{\infty}$ is invariant under (SGD), fix a tolerance level
$\delta>0$, and let $\mathcal{U}_{0}\equiv\mathcal{U}_{0}(\delta)$ be a
$\delta$-neighborhood of the system’s ground state $\mathcal{K}_{0}$. Then
there exists a constant $c\equiv c_{\delta}>0$ such that, for all sufficiently
small $\eta>0$, we have:

$\mu_{\infty}(\mathcal{U}_{0})\geq 1-e^{-c/\eta}.$ (D.7.7)

###### Proof.

It suffices to apply Proposition D.5 (Section D.6) with $J$ as the set of
ground states $\operatorname*{arg\,min}_{i\in I}E_{i}$. They are necessarily
minimizing by Lemma D.32. ∎

###  D.8. Extension: the mean occupation measures

We now state and prove analogue of Theorems 1, 2, 3 and 4 for the mean
occupation measure $\mu_{n}$.

For this we will need a strengthened version of Assumption 3∗, viz.

######  Assumption 3∗∗ (Variant of Assumption 3∗).

The signal-to-noise ratio of $\operatorname{\mathsf{G}}$ satisfies

$\frac{\lVert\nabla
f(x)\rVert^{2}}{\sigma_{\infty}^{2}(f(x))}\to\infty\quad\text{as}\quad\lVert
x\rVert\to\infty\,.$ (4∗∗)

In this section, we will posit that Assumption 3∗∗ holds in addition to
Assumptions 1∗, LABEL:, 2∗, LABEL: and 4. We then have the following series of
results for the occupation measure $\mu_{n}$ of (SGD).

######  Theorem 1∗ (Occupation variant of Theorem 1).

Fix a tolerance level $\varepsilon>0$, and let
$\mathcal{U}_{i}\equiv\mathcal{U}_{i}(\delta)$, $i=1,\dotsc,K$, be
$\delta$-neighborhoods of the components of $\operatorname{crit}f$. Then, for
all sufficiently small $\delta,\eta>0$ and large enough $n$, we have

$\left\lvert\eta\log\mu_{n}(\mathcal{U}_{i})+E_{i}-\min\nolimits_{j}E_{j}\right\rvert\leq\varepsilon$
(D.8.1)

and

$\left\lvert\eta\log\frac{\mu_{n}(\mathcal{U}_{i})}{\mu_{n}(\mathcal{U}_{j})}+E_{i}-E_{j}\right\rvert\leq\varepsilon.$
(D.8.2)

More compactly, with notation as above, we have:

$\mu_{n}(\mathcal{U}_{i})\propto\exp\left(-\frac{E_{i}+\operatorname{\mathcal{O}}(\varepsilon)}{\eta}\right).$
(D.8.3)

######  Theorem 2∗ (Occupation variant of Theorem 2).

Let $\mathcal{K}$ be a non-minimizing component of $f$. Then, with notation as
in Theorem 1, there exists a minimizing component $\mathcal{K}^{\prime}$ of
$f$ and a positive constant $c\equiv c(\mathcal{K},\mathcal{K}^{\prime})>0$
such that

$\frac{\mu_{n}(\mathcal{U})}{\mu_{n}(\mathcal{U}^{\prime})}\leq\exp\left(-\frac{c(\mathcal{K},\mathcal{K}^{\prime})+\varepsilon}{\eta}\right)$
(D.8.4)

for all all sufficiently small $\eta>0$, $n$ large enough and all sufficiently
small neighborhoods $\mathcal{U}$ and $\mathcal{U}^{\prime}$ of $\mathcal{K}$
and $\mathcal{K}^{\prime}$ respectively.

######  Theorem 3∗ (Occupation variant of Theorem 3).

Fix a tolerance level $\delta>0$, and let
$\mathcal{U}\equiv\mathcal{U}(\delta)$ be a $\delta$-neighborhood of
$\operatorname{crit}f$. Then there exists a constant $c\equiv c_{\delta}>0$
such that, for all sufficiently small $\eta>0$ and large enough $n$, we have:

$\mu_{n}(\mathcal{U})\geq 1-e^{-c/\eta}.$ (D.8.5)

######  Theorem 4∗ (Occupation variant of Theorem 4).

Fix a tolerance level $\delta>0$, and let
$\mathcal{U}_{0}\equiv\mathcal{U}_{0}(\delta)$ be a $\delta$-neighborhood of
the system’s ground state $\mathcal{K}_{0}$. Then there exists a constant
$c\equiv c_{\delta}>0$ such that, for all sufficiently small $\eta>0$ and
large enough $n$, we have:

$\mu_{n}(\mathcal{U}_{0})\geq 1-e^{-c/\eta}.$ (D.8.6)

We begin with a preliminary lemma which shows that, under Assumption 3∗∗, the
sequence of mean occupation measure $(\mu_{n})_{n\geq 0}$ is tight (see e.g.,
Kallenberg [32, Chap. 23]).

######  Lemma D.34.

The sequence of mean occupation measures $(\mu_{n})_{n\geq 0}$ is tight.

The proof of this lemma first follows the proof of Lemma D.16 and then relies
on the same reasoning as the proof of Douc et al. [14, Thm. 12.3.3].

###### Proof.

By Lemma D.14, there exists $\mathcal{K}\subset\mathcal{X}$ compact,
$\eta_{0}>0$, $c>0$ such that, for any $\eta\leq\eta_{0}$,
$x_{0}=x\notin\mathcal{K}$,

$U_{\infty}(x_{1})-U_{\infty}(x)\leq\eta\left(\frac{\lVert\mathsf{U}(x,\omega_{0})\rVert^{2}}{\sigma_{\infty}^{2}(f(x))}-\frac{\lVert\nabla
f(x)\rVert^{2}}{\sigma_{\infty}^{2}(f(x))}\right)\,.$ (D.8.7)

Passing to the expectation yields that, for any $x\notin\mathcal{K}$,

$\operatorname{\mathbb{E}}_{x}\left[U_{\infty}(x_{1})\right]-{U_{\infty}(x)}\leq\eta\left(\frac{\operatorname{\mathbb{E}}_{x}\left[\lVert\mathsf{U}(x,\omega_{0})\rVert^{2}\right]}{\sigma_{\infty}^{2}(f(x))}-\frac{\lVert\nabla
f(x)\rVert^{2}}{\sigma_{\infty}^{2}(f(x))}\right)\,.$ (D.8.8)

Appplying Corollary D.2 with
$X\leftarrow\frac{\mathsf{U}(x,\omega_{0})}{\sqrt{\sigma_{\infty}^{2}(f(x))}}$
(the conditions of application are verified from Assumption 2∗Item (c.5pt))
yields that

$\operatorname{\mathbb{E}}_{x}\left[U_{\infty}(x_{1})\right]-{U_{\infty}(x)}\leq-\eta\frac{\lVert\nabla
f(x)\rVert^{2}}{\sigma_{\infty}^{2}(f(x))}+\eta\times 16d\log 6\,.$ (D.8.9)

Hence, for any $x\in\mathcal{X}$, we have

$\displaystyle\operatorname{\mathbb{E}}_{x}\left[U_{\infty}(x_{1})\right]-U_{\infty}(x)$
$\displaystyle\leq\operatorname{\mathds{1}}\\{x\in\mathcal{K}\\}\left(\sup_{x^{\prime}\in\mathcal{K}}\operatorname{\mathbb{E}}_{x^{\prime}}[U_{\infty}(x^{\prime})]-\inf_{\mathcal{X}}U_{\infty}\right)$
$\displaystyle-\operatorname{\mathds{1}}\\{x\notin\mathcal{K}\\}\left(\eta\frac{\lVert\nabla
f(x)\rVert^{2}}{\sigma_{\infty}^{2}(f(x))}-\eta\times 16d\log 6\right)\,,$
(D.8.10)

or, after rearranging,

$\displaystyle\operatorname{\mathbb{E}}_{x}\left[U_{\infty}(x_{1})\right]$
$\displaystyle-\operatorname{\mathds{1}}\\{x\in\mathcal{K}\\}\left(\sup_{x^{\prime}\in\mathcal{K}}\operatorname{\mathbb{E}}_{x^{\prime}}[U_{\infty}(x^{\prime})]-\inf_{\mathcal{X}}U_{\infty}\right)$
$\displaystyle+\operatorname{\mathds{1}}\\{x\notin\mathcal{K}\\}\left(\eta\frac{\lVert\nabla
f(x)\rVert^{2}}{\sigma_{\infty}^{2}(f(x))}-\eta\times 16d\log 6\right)\leq
U_{\infty}(x)\,.$ (D.8.11)

Since the function

$\displaystyle x\mapsto$
$\displaystyle-\operatorname{\mathds{1}}\\{x\in\mathcal{K}\\}\left(\sup_{x^{\prime}\in\mathcal{K}}\operatorname{\mathbb{E}}_{x^{\prime}}[U_{\infty}(x^{\prime})]-\inf_{\mathcal{X}}U_{\infty}\right)$
$\displaystyle+\operatorname{\mathds{1}}\\{x\notin\mathcal{K}\\}\left(\eta\frac{\lVert\nabla
f(x)\rVert^{2}}{\sigma_{\infty}^{2}(f(x))}-\eta\times 16d\log 6\right)$
(D.8.12)

is measurable, lower-bounded and goes to infinity as $\lVert x\rVert\to\infty$
by Assumption 3∗∗, one can then apply the same computations as in the proof of
Douc et al. [14, Thm. 12.3.3] to obtain that the sequence of occupation
measures $(\mu_{n})_{n\geq 0}$ is tight. ∎

We now prove Theorem 1∗ by adapting the proof of Theorem 1. Since the process
is exactly the same for Theorems 2∗, 3∗ and 4∗, we omit their proofs. While we
rely on it heavily, it is not made clear that $\mathcal{U}_{i}$ are open
neighborhoods.

###### Proof of Theorem 1∗.

We show that, for sufficiently small $\delta,\eta>0$, for any $i\in I$, we
have that

$\displaystyle\exp\left(-\frac{E_{i}-\min\nolimits_{j}E_{j}+\varepsilon}{\eta}\right)$
$\displaystyle\leq\liminf_{n\to\infty}\mu_{n}(\mathcal{U}_{i})$
$\displaystyle\leq\limsup_{n\to\infty}\mu_{n}(\mathcal{U}_{i})$
$\displaystyle\leq\exp\left(-\frac{E_{i}-\min\nolimits_{j}E_{j}-\varepsilon}{\eta}\right)$
(D.8.13)

and the results in the statement will follow with $2\varepsilon$ in place of
$\varepsilon$.

We apply Proposition D.4 (Section D.5): take $\delta$ small enough so
Proposition D.4 can be applied with both the neighborhoods
$\mathcal{U}_{1},\dots,\mathcal{U}_{K}$ and
$\operatorname{cl}\mathcal{U}_{1},\dots,\operatorname{cl}\mathcal{U}_{K}$. One
then obtain $\eta_{0}>0$ such that, for all $0<\eta<\eta_{0}$ and any
$\mu_{\infty}$ invariant probability measure for $(x^{\eta}_{n})_{n}$, for any
$i\in I$,

$\displaystyle\mu_{\infty}(\mathcal{U}_{i})$
$\displaystyle\geq\exp\left(-\frac{E(\mathcal{K}_{i})-\min_{j\in
I}E(\mathcal{K}_{j})}{\eta}-\frac{\varepsilon}{\eta}\right)$ (D.8.14)
$\displaystyle\mu_{\infty}(\operatorname{cl}\mathcal{U}_{i})$
$\displaystyle\leq\exp\left(-\frac{E(\mathcal{K}_{i})-\min_{j\in
I}E(\mathcal{K}_{j})}{\eta}+\frac{\varepsilon}{\eta}\right)\,.$

We now prove that Eq. D.8.13 holds. Fix $i\in I$. By Lemma D.34, the sequence
of mean occupation measures $(\mu_{n})_{n\geq 0}$ is tight, so that, by
Prohorov theorem [32, Thm. 23.2], it is sequentially compact for the weak
topology, or, in other terms, for the convergence in distribution. Therefore,
$(\mu_{n})_{n\geq 0}$ admits a weak accumulation point which is a probability
distribution and that we denote by $\nu$. Applying Portmanteau theorem [32,
Thm. 5.25] to the open set $\mathcal{U}_{i}$ and the closed set
$\operatorname{cl}\mathcal{U}_{i}$ yields that

$\nu(\mathcal{U}_{i})\leq\liminf_{n\to\infty}\mu_{n}(\mathcal{U}_{i})\leq\limsup_{n\to\infty}\mu_{n}(\operatorname{cl}\mathcal{U}_{i})\leq\nu(\operatorname{cl}\mathcal{U}_{i})\,.$
(D.8.15)

Since $(x_{n})_{n\geq 0}$, the sequence of iterates of SGD, is (weak) Feller
by Lemma D.15, $\nu$ is actually invariant for $(x_{n})_{n\geq 0}$, by, e.g.,
Douc et al. [14, Prop. 12.3.1], and _a fortiori_ invariant for the accelerated
process $(x^{\eta}_{n})_{n\geq 0}$. Combining Eq. D.8.14 with Eq. D.8.15 gives
the result Eq. D.8.13. ∎

##  Appendix E Potential for the invariant measure

###  E.1. Gaussian noise

Though it does not formally fit into our setting, let us first begin with the
case where the noise is Gaussian. Since it is unbounded, our assumptions are
not satisfied and our theorems describing the invariant measure do not apply.
However, all the objects we consider are still well-defined, and, in that
case, it is possible to compute the $E_{i}$ explicitely. Moreover, this
section serves as a blueprint for the truncated Gaussian case of the next
section.

Assume that, for every $x\in\mathcal{X}$, $\mathsf{U}(x,\omega)$ follows a
centered Gaussian distribution with covariance $\sigma^{2}(f(x))I$ for some
continuous function $\sigma^{2}:\mathbb{R}\to(0,+\infty)$.

Akin to $U_{\infty}$ in Appendix D, a key role is played by the function
$U:\mathcal{X}\to\mathbb{R}$ defined by

$U(x)\coloneqq 2\alpha(f(x))\quad\text{ with
}\quad\alpha\colon\mathbb{R}\to\mathbb{R}\quad\text{ a primitive of }\quad
1/{\sigma^{2}}\,.$ (E.1.1)

Since the noise is Gaussian, the Lagrangian and Hamiltonian have explicit
expressions: for every $x,p,v\in\mathcal{X}$,

$\displaystyle\mathcal{H}(x,p)$ $\displaystyle=-\langle\nabla
f(x),p\rangle+{\frac{1}{2}}\sigma^{2}(f(x))\lVert p\rVert^{2}$ (E.1.2a)
$\displaystyle\mathcal{L}(x,v)$ $\displaystyle=\frac{\lVert v+\nabla
f(x)\rVert}{2\sigma^{2}(f(x))}\,.$ (E.1.2b)

This expression of $\mathcal{L}$ make it clear that the action function
penalizes the deviation of a path from the flow: for a path
$\gamma\in\mathcal{C}([0,T])$ for some $T>0$,

$\mathcal{S}_{T}(\gamma)=\int_{0}^{T}\frac{\lVert\dot{\gamma}_{t}+\nabla
f(\gamma_{t})\rVert^{2}}{2\sigma^{2}(f(\gamma_{t}))}\>dt\,.$ (E.1.3)

The computation of the $E_{i}$ relies on the following observation. Take a
path $\gamma\in\mathcal{C}([0,T])$ for some $T>0$ and consider $\varphi$
defined by $\varphi_{t}=\gamma_{T-t}$ for $t\in[0,T]$. Then, the action cost
of $\varphi$ is given by,

$\displaystyle\mathcal{S}_{T}(\varphi)$
$\displaystyle=\int_{0}^{T}\frac{\lVert-\dot{\gamma}_{t}+\nabla
f(\gamma_{t})\rVert^{2}}{2\sigma^{2}(f(\gamma_{t}))}\>dt$
$\displaystyle=\int_{0}^{T}\frac{\lVert\dot{\gamma}_{t}+\nabla
f(\gamma_{t})\rVert^{2}}{2\sigma^{2}(f(\gamma_{t}))}\>dt-\int_{0}^{T}\frac{2\langle\dot{\gamma}_{t},\nabla
f(\gamma_{t})\rangle missing}{\sigma^{2}(f(\gamma_{t}))}\>dt$
$\displaystyle=\mathcal{S}_{T}(\gamma)-\int_{0}^{T}\langle\dot{\gamma}_{t},\nabla
U(\gamma_{t})\rangle\>dt\,,$ (E.1.4)

since $\nabla U(x)=2\nabla\alpha(f(x))\nabla f(x)$. Therefore, we get that

$\mathcal{S}_{T}(\varphi)=\mathcal{S}_{T}(\gamma)-(U(\gamma_{T})-U(\gamma_{0}))\,.$
(E.1.5)

Take $i,j\in I$. This equality then translates to a relation between $B_{i,j}$
and $B_{j,i}$: considering $\gamma\in\mathcal{C}([0,T])$ such that
$\gamma_{0}\in\mathcal{K}_{i}$, $\gamma_{T}\in\mathcal{K}_{j}$ and taking the
infimum over all such paths, we get that

$B_{j,i}\leq B_{i,j}+(U_{j}-U_{i})\,.$ (E.1.6)

where, since $f$ is constant on $\mathcal{K}_{i}$ and $\mathcal{K}_{j}$, we
denote by $U_{i}$ and $U_{j}$ the values of $U$ on $\mathcal{K}_{i}$ and
$\mathcal{K}_{j}$ respectively.

Reversing the roles of $i$ and $j$ and applying the same argument shows that
this inequality is an equality:

$B_{j,i}+U_{j}=B_{i,j}+U_{i}\,.$ (E.1.7)

Denote by $C_{i,j}$ this common value. Crucially, $C_{i,j}$ is symmetric in
$i$ and $j$.

Consider now $T^{\ast}$ a minimum weight spanning tree on the complete but now
undirected graph on $I$ with weights $(C_{i,j})_{i,j}$. We show that the
minima in the $E_{i}$ are attained $T^{\ast}$, or more precisely, a directed
version of it.

Fix $i$ and consider $T\in\mathcal{T}_{i}$ a spanning tree rooted at $i$. We
have that, since any node $j$ is the origin of exactly one edge in $T$,

$\displaystyle\sum_{(j\to l)\in T}B_{j,l}+\sum_{j\in I}U_{j}$
$\displaystyle=\sum_{(j\to l)\in T}\left(B_{j,l}+U_{j}\right)+U_{i}$
$\displaystyle=\sum_{(j\to l)\in T}C_{j,l}+U_{i}\,.$ (E.1.8)

But by definition of $T^{\ast}$, this sum is at least greater than
$\sum_{(j\leftrightarrow l)\in T^{\ast}}C_{j,l}$ so that we have

$\sum_{(j\to l)\in T}B_{j,l}+\sum_{j\in I}U_{j}\geq\sum_{(j\leftrightarrow
l)\in T^{\ast}}C_{j,l}+U_{i}\,,$ (E.1.9)

and taking $T_{i}$ an oriented version of $T^{\ast}$ rooted at $i$, the
equality is attained. Therefore, we have that

$E_{i}=\sum_{(j\to l)\in T_{i}}B_{j,l}-\sum_{j\in I}U_{j}+U_{i}\,,$ (E.1.10)

or, in short, $E_{i}=U_{i}+c$ where $c>0$ is independent of $i$.

Therefore, the mass distribution over critical points is governed by a Gibbs
measure with potential $U$.

Let us now mention two particular cases.

  * •

If $\sigma^{2}$ is constant, then $U=\frac{2f}{\sigma^{2}}$.

  * •

It $\sigma^{2}$ is linear, i.e., of the form
$\sigma^{2}(f(x))=\sigma^{2}_{1}(f(x)+\sigma^{2}_{0})$, then
$U=\frac{2}{\sigma^{2}_{1}}\log(f+\sigma^{2}_{0})$.

###  E.2. Truncated Gaussian noise

To fit into our theoretical framework, we consider truncated Gaussian noise
instead. The general outline of the proof but with added steps to handle the
error due to the truncation. In particular, one must show that, without loss
of generality, we can only conider paths whose derivative has the same norm as
the gradient of $f$. This is done with Freidlin & Wentzell [20, Chap. 4, Lem.
3.1] that we adapt to our setting.

Assume that $\mathsf{U}(x,\omega)$ follows a centered Gaussian distribution
with covariance $\sigma^{2}(f(x))I$ conditioned on being in
$\mathbb{B}(0,R(x))$ for some $R(x)>0$.

As in Definition 4, we define $U(x)=2\alpha(f(x))$ with
$\alpha^{\prime}=\frac{1}{\sigma^{2}}$ and denote by $U_{i}$ the value taken
by $U$ on $\mathcal{K}_{i}$.

Consider some $0<\delta\leq{\frac{1}{2}}$ and assume that

$\sup_{x\in\mathcal{X}}2^{d+4}(d+1)e^{-\tfrac{R^{2}}{16\sigma^{2}}}\leq\delta\,,$
(E.2.1)

so that the error term $2E(\sigma^{2}(f(x)),R(x))$ in Lemma F.2 is bounded by
$\delta$.

Moreover, assume that, for any $x\in\mathcal{X}$

$\lVert\nabla f(x)\rVert\leq\frac{R(x)}{8}$ (E.2.2)

######  Lemma E.1.

Consider $\gamma\in\mathcal{C}([0,T])$. Then, there exists
$\widetilde{\gamma}\in\mathcal{C}([0,S])$ a reparametrization of $\gamma$ such
that, for any $t\in[0,S]$,

$\lVert\dot{\widetilde{\gamma}}_{s}\rVert=\lVert\nabla
f(\widetilde{\gamma}_{s})\rVert\,.$ (E.2.3)

and

$\mathcal{S}_{T}(\gamma)\geq\int_{0}^{S}\frac{\lVert\dot{\widetilde{\gamma}}_{s}+\nabla
f(\widetilde{\gamma}_{s})\rVert^{2}}{2(1+\delta)\sigma^{2}(f(\widetilde{\gamma}_{s}))}\>ds\,.$
(E.2.4)

###### Proof.

By the proof Freidlin & Wentzell [20, Chap. 4, Lem. 3.1], there exists $t(s)$
change of time such that, with $\widetilde{\gamma}_{s}=\gamma_{t(s)}$,
$\lVert\dot{\widetilde{\gamma}}_{s}\rVert=\lVert\nabla
f(\widetilde{\gamma}_{s})\rVert$.

We have that

$\mathcal{S}_{T}(\gamma)=\int_{0}^{t^{-1}(T)}\dot{t}(s)\mathcal{L}(\widetilde{\gamma}_{s},(\dot{t}(s))^{-1}\dot{\widetilde{\gamma}}_{s})\>ds\,,$
(E.2.5)

so it suffices to bound
$\mathcal{L}(\widetilde{\gamma}_{s},\dot{\widetilde{\gamma}}_{s})$ from below:
by definition, we have

$\displaystyle\mathcal{L}(\widetilde{\gamma}_{s},(\dot{t}(s))^{-1}\dot{\widetilde{\gamma}}_{s})$
$\displaystyle\geq\sup\left\\{\langle
p,(\dot{t}(s))^{-1}\dot{\widetilde{\gamma}}_{t}+\nabla
f(\widetilde{\gamma}_{s})\rangle-\bar{\mathcal{H}}(\widetilde{\gamma}_{s},p):\lVert
p\rVert\leq\frac{R(\widetilde{\gamma}_{s})}{2\sigma^{2}(f(\widetilde{\gamma}_{s}))}\right\\}$
$\displaystyle\geq\sup\left\\{\langle
p,(\dot{t}(s))^{-1}\dot{\widetilde{\gamma}}_{t}+\nabla
f(\widetilde{\gamma}_{s})\rangle-(1+\delta){\frac{\sigma^{2}(f(\widetilde{\gamma}_{s}))}{2}}\lVert
p\rVert^{2}:\lVert
p\rVert\leq\frac{R(\widetilde{\gamma}_{s})}{2\sigma^{2}(f(\widetilde{\gamma}_{s}))}\right\\}\,,$
(E.2.6)

by Lemma F.2. Applying Lemma F.3 with $\lambda\leftarrow\dot{t}(s)$, now
exactly yields, for almost all $s$,

$\displaystyle\mathcal{L}(\widetilde{\gamma}_{s},(\dot{t}(s))^{-1}\dot{\widetilde{\gamma}}_{s})$
$\displaystyle\geq\dot{t}(s)\sup\left\\{\langle
p,\dot{\widetilde{\gamma}}_{t}+\nabla
f(\widetilde{\gamma}_{s})\rangle-(1+\delta){\frac{\sigma^{2}(f(\widetilde{\gamma}_{s}))}{2}}\lVert
p\rVert^{2}:\lVert
p\rVert\leq\frac{R(\widetilde{\gamma}_{s})}{2\sigma^{2}(f(\widetilde{\gamma}_{s}))}\right\\}$
$\displaystyle=\dot{t}(s)\frac{\lVert\dot{\widetilde{\gamma}}_{s}+\nabla
f(\widetilde{\gamma}_{s})\rVert^{2}}{2(1+\delta)\sigma^{2}(f(\widetilde{\gamma}_{s}))}\,,$
(E.2.7)

since $\lVert\dot{\widetilde{\gamma}}_{s}+\nabla
f(\widetilde{\gamma}_{s})\rVert\leq\frac{R(\widetilde{\gamma}_{s})}{2}$. ∎

######  Lemma E.2.

With this setting, for any $i\in I$

$E_{i}=U_{i}+\sum_{(j\to l)\in T_{i}}B_{j,l}-\sum_{j\in
I}U_{j}+\operatorname{\mathcal{O}}\left(\delta\right)$ (E.2.8)

###### Proof.

Consider $\gamma\in\mathcal{C}([0,T])$ such that
$\gamma_{0}\in\mathcal{K}_{i}$, $\gamma_{T}\in\mathcal{K}_{j}$ and
$\mathcal{S}_{T}(\gamma)<+\infty$. Then, by the previous lemma Lemma E.1,
there exists $\widetilde{\gamma}\in\mathcal{C}([0,S])$ a reparametrization of
$\gamma$ such that, for any $t\in[0,S]$,

$\displaystyle\mathcal{S}_{T}(\gamma)$
$\displaystyle\geq\int_{0}^{S}\frac{\lVert\dot{\widetilde{\gamma}}_{s}+\nabla
f(\widetilde{\gamma}_{s})\rVert^{2}}{2(1+\delta)\sigma^{2}(f(\widetilde{\gamma}_{s}))}\>ds$
$\displaystyle=\int_{0}^{S}\frac{\lVert-\dot{\widetilde{\gamma}}_{s}+\nabla
f(\widetilde{\gamma}_{s})\rVert^{2}}{2(1+\delta)\sigma^{2}(f(\widetilde{\gamma}_{s}))}\>ds+\frac{U(\gamma_{T})-U(\gamma_{0})}{1+\delta}\,,$
(E.2.9)

where we performed the same computations as above in Section E.1. Considering
the path $(\widetilde{\gamma}_{S-s})_{s\in[0,S]}$ and invoking the upper-bound
on the Lagrangian from Lemma F.2 with $-\dot{\widetilde{\gamma}}_{s}+\nabla
f(\widetilde{\gamma}_{s})$ which still has norm less than
$R(\widetilde{\gamma}_{s})/4$, we get that

$\mathcal{S}_{T}(\gamma)\geq\frac{1-\delta}{1+\delta}B_{j,i}+\frac{U(\gamma_{T})-U(\gamma_{0})}{1+\delta}\,.$
(E.2.10)

The result now follows from the same computations as in Section E.1. ∎

###  E.3. Local dependencies

Under local assumptions similar to Mori et al. [56], we demonstrate how the
modelling of the noise influences the invariant measure.

######  Lemma E.3.

Consider $\mathcal{K}_{i}$ minimizing,
$\sigma^{2}\colon\mathbb{R}\to(0,+\infty)$ continuous, and take
$\alpha\colon\mathbb{R}\to\mathbb{R}$ such that
$\alpha^{\prime}=\frac{1}{\sigma^{2}}$. Assume that $H^{\ast}$ is a positive
definite matrix such that, locally near $\mathcal{K}_{i}$, it holds that:

$\alpha(f(x))=\sum_{\lambda\in\operatorname{eig}H^{\ast}}g^{\lambda}(x_{\lambda})\,,$
(E.3.1)

where $x_{\lambda}$ denotes the orthogonal projection of $x$ on the eigenspace
of the eigenvalue $\lambda$ and where
$g^{\lambda}\colon\mathcal{X}\to\mathbb{R}$ is continuously differentiable.
Define the potential $U\colon\mathcal{X}\to\mathbb{R}$ by

$U(x)=\sum_{\lambda\in\operatorname{eig}H^{\ast}}\frac{2g^{\lambda}(x_{\lambda})}{\lambda}\,.$
(E.3.2)

If we have the anistropic subGaussian bound: for $x$ in a neighborhood of
$\mathcal{K}_{i}$, $p\in\overline{\mathbb{B}}(0,\lVert U(x)\rVert)$,

$\bar{\mathcal{H}}(x,p)\leq\frac{\sigma^{2}(f(x))}{2}\langle
p,H^{\ast}p\rangle\,,$ (E.3.3)

then there is $\delta>0$ such that, for all $j\neq i$, any
$0<\delta^{\prime}\leq\delta$,

$E_{j}\geq\min\left\\{U(x)-U_{i}:x,d(x,\mathcal{K}_{i})=\delta^{\prime}\right\\}>0\,,$
(E.3.4)

where $U_{i}$ is the value of $U$ on $\mathcal{K}_{i}$.

Moreover, there exists $R>\delta$ such that, if there exists $c>0$, $s^{2}>0$,
such that, for all
$x\in\overline{\mathbb{B}}(0,R)\setminus\mathcal{U}_{\delta}(\mathcal{K}_{i})$,
$v\in\mathbb{B}(\nabla f(x),c)$,

$\bar{\mathcal{L}}(x,v)\leq\frac{\lVert v\rVert}{2s^{2}}\,,$ (E.3.5)

then there exists $C>0$ that depends only on $r,R,c$, $f$ restricted to
$\mathcal{X}\setminus\mathcal{U}_{r}(\mathcal{K}_{i})$ such that

$E_{i}\leq\frac{C}{s^{2}}\,.$ (E.3.6)

The assumptions on the Hamiltonian and the Lagrangian roughly say that the
noise share some similarities with Gaussian distributions with the prescribed
variances. In particular, they are satisfied in the (truncated) Gaussian case,
as shown in Lemma F.2.

Moreover, a takeaway of this lemma is that, if $\sigma^{2}$ or the eigenvalues
of $H^{\ast}$ are small enough, then $\mathcal{K}_{i}$ must be the ground
state even if it may not be the global minimum of $U$. This lemma is general
enough to handle non-constant variance: a notable example is when
$\sigma^{2}(f(x))$ is linear in $f(x)$ and where the resulting potential $U$
then depends logarithmically on the value $f$.

###### Proof.

Denote $P_{\lambda}\in\mathbb{R}^{d\times d}$ the orthogonal projection on the
eigenspace of $H^{\ast}$ associated with the eigenvalue $\lambda$. $U$ can
thus be rewritten as

$.U(x)=\sum_{\lambda\in\operatorname{eig}H^{\ast}}\frac{2g^{\lambda}(P_{\lambda}x)}{\lambda}\,,$
(E.3.7)

so that its gradient is given by

$\nabla
U(x)=\sum_{\lambda\in\operatorname{eig}H^{\ast}}\frac{2P_{\lambda}\nabla
g^{\lambda}(P_{\lambda}x)}{\lambda}\,.$ (E.3.8)

In particular, we obtain that for $x$ close enough to $\mathcal{K}_{i}$, using
the orthogonality of the projections,

$\displaystyle\bar{\mathcal{H}}(x,\nabla U(x))$
$\displaystyle\leq\frac{\sigma^{2}(f(x))}{2}\langle\nabla U(x),H^{\ast}\nabla
U(x)\rangle$
$\displaystyle=\frac{\sigma^{2}(f(x))}{2}\sum_{\lambda\in\operatorname{eig}H^{\ast}}\frac{4\lVert
P_{\lambda}\nabla g^{\lambda}(P_{\lambda}x)\rVert^{2}}{\lambda}$
$\displaystyle=\frac{\sigma^{2}(f(x))}{2}\left\langle\nabla
U(x),2\nabla(\alpha\circ f)(x)\right\rangle$ $\displaystyle=\left\langle\nabla
U(x),\nabla f(x)\right\rangle\,.$ (E.3.9)

Therefore, for $x$ close enough to $\mathcal{K}_{i}$, we have that

$\displaystyle\mathcal{H}(x,\nabla U(x))$ $\displaystyle=-\left\langle\nabla
U(x),\nabla f(x)\right\rangle+\bar{\mathcal{H}}(x,\nabla U(x))\leq 0\,.$
(E.3.10)

For $x$ close to $\mathcal{K}_{i}$, let us compute $\langle\nabla U(x),\nabla
f(x)\rangle$:

$\displaystyle\langle\nabla U(x),\nabla f(x)\rangle$
$\displaystyle=\sigma^{2}(f(x))\langle\nabla U(x),\nabla(\alpha\circ
f)(x)\rangle$
$\displaystyle=\sigma^{2}(f(x))\sum_{\lambda\in\operatorname{eig}H^{\ast}}\frac{2\lVert
P_{\lambda}\nabla g^{\lambda}(P_{\lambda}x\rVert}{\lambda}\,,$ (E.3.11)

which is (stricly) positive in a small neighborhood of $\mathcal{K}_{i}$
(excluding $\mathcal{K}_{i}$ itself). Therefore, $U$ is decreasing on
trajectories of the flow in this neighborhood. With the same proof as in Lemma
D.29, we deduce that there exists $\delta>0$ such that
$\operatorname*{arg\,min}_{x\in\mathcal{U}_{\delta}(\mathcal{K}_{i})}U(x)=\mathcal{K}_{i}$.
Moreover, take $\delta>0$ small enough such that Eq. E.3.10 holds on
$\mathcal{U}_{\delta}(\mathcal{K}_{i})$,
$\mathcal{U}_{\delta}(\mathcal{K}_{i})\cap\operatorname{crit}f=\mathcal{K}_{i}$
and the trajectories of the flow started in
$\mathcal{U}_{\delta}(\mathcal{K}_{i})$ stay converge to $\mathcal{K}_{i}$. We
now proceed as in the proof of Lemma D.33. Take $\delta^{\prime}\leq\delta/2$,
$\mathcal{U}\coloneqq\mathcal{U}_{\delta}^{\prime}(\mathcal{K}_{i})$ and
$\Delta\coloneqq\min\left\\{U(x)-U_{i}:x\in\mathcal{X},\,d(x,\mathcal{K}_{i})=\delta^{\prime}\right\\}$,
which is positive by definition. Fix $j\neq i$: we show that
$B_{i,j}\geq\Delta$. Consider some $T>0$ and
$\gamma\in\mathcal{C}([0,T],\mathcal{X})$ such that
$\gamma_{0}\in\mathcal{K}_{i}$ and $\gamma_{T}\in\mathcal{K}_{j}$. By
definition of $\delta$ and by continuity of $\gamma$ and
$d(\cdot,\mathcal{K}_{i})$, there exists $t\in[0,T]$ such that
$d(\gamma_{t},\mathcal{K}_{i})=\delta^{\prime}$. Therefore, we have that

$\displaystyle\mathcal{S}_{0,T}(\gamma)$
$\displaystyle\geq\mathcal{S}_{0,t}(\gamma)=\int_{0}^{t}\mathcal{L}(\gamma_{s},\dot{\gamma}_{s})\>ds\,,$
(E.3.12)

and therefore, by definition of $\mathcal{L}$ as the conjugate of
$\mathcal{H}$, we obtain that

$\displaystyle\mathcal{S}_{0,T}(\gamma)$
$\displaystyle\geq\int_{0}^{t}\left\langle\dot{\gamma}_{s},\nabla
U(\gamma_{s})\right\rangle-\bar{\mathcal{H}}(\gamma_{s},\nabla
U(\gamma_{s}))\>ds\geq\int_{0}^{t}\left\langle\dot{\gamma}_{s},\nabla
U(\gamma_{s})\right\rangle\,,$ (E.3.13)

where we used Eq. E.3.10 in the last inequality. Thus, we get

$\displaystyle\mathcal{S}_{0,T}(\gamma)$ $\displaystyle\geq
U(\gamma_{t})-U(\gamma_{0})\geq\Delta\,,$ (E.3.14)

with any $\delta^{\prime}\leq\delta/2$ (and therefore $\delta$ in the
statement corresponds to $\delta/2$ here).

Finally, it remains to show that, any $l\neq i$, $E_{l}\geq\Delta$. Consider
any tree rooted at $l$: it must have an edge of the form $i\to j$ for some
$j\in I$ and therefore the sum of its weights will be at least
$B_{i,j}\geq\Delta$. Hence, since it holds for any such tree, we have that
$E_{l}\geq\Delta$.

We now prove the second part of the lemma. $\delta$ was chosen small enough so
that it is possible to find $R>\delta$ such that
$\mathbb{B}(0,R)\setminus\mathcal{U}_{\delta}(\mathcal{K}_{i})$ contains all
the $\mathcal{K}_{j}$ for $j\neq i$ and not $\mathcal{K}_{i}$. The assumption
on the Lagrangian implies that, for any
$x\in\mathbb{B}(0,R)\setminus\mathcal{U}_{\delta}(\mathcal{K}_{i})$,
$v\in\mathbb{B}(0,c)$,

$\mathcal{L}(x,v)\leq\frac{\lVert v+\nabla f(x)\rVert^{2}}{2s^{2}}\,.$
(E.3.15)

Fix $j\neq i$ and take $\gamma\in\mathcal{C}^{1}([0,T],\mathcal{X})$ such that
$\gamma_{0}\in\mathcal{K}_{j}$,
$x\coloneqq\gamma_{T}\in\mathcal{U}_{\delta}(\mathcal{K}_{i})$ and $\gamma$
remains in
$\overline{\mathbb{B}}(0,R)\setminus\mathcal{U}_{\delta}(\mathcal{K}_{i})$.
Without loss of generality, at the expense of replacing $\gamma$ by a
reparametrization, we can assume that $\dot{\gamma}_{t}$ in $\mathbb{B}(0,c)$
for all $t\in[0,T]$. Then, we have that

$\displaystyle\mathcal{S}_{0,T}(\gamma)$
$\displaystyle\leq\int_{0}^{T}\mathcal{L}(\gamma_{s},\dot{\gamma}_{s})\>ds\leq\int_{0}^{T}\frac{\lVert\dot{\gamma}_{s}+\nabla
f(\gamma_{s})\rVert^{2}}{2s^{2}}\>ds\,,$ (E.3.16)

which depends only on the value of $\nabla f$ outside of
$\mathcal{U}_{\delta/2}(\mathcal{K}_{i})$. But, by the same reasoning as in
Lemma D.31, since the flow started at $x$ converges to $\mathcal{K}_{i}$, we
have that $B(\\{x\\},\mathcal{K}_{i})=0$. Therefore, we have that,

$B_{j,i}\leq\int_{0}^{T}\frac{\lVert\dot{\gamma}_{s}+\nabla
f(\gamma_{s})\rVert^{2}}{2s^{2}}\>ds\,,$ (E.3.17)

and, taking the maximum of such quantities over all $j\neq i$, we obtain $C>0$
such, for any $j\neq i$,

$B_{j,i}\leq\frac{C}{s^{2}}\,.$ (E.3.18)

To conclude on the value of $E_{i}$, we consider the tree rooted at $i$ made
of all the edges $(j,i)$ for $j\neq i$. It has weight at most $(K-1)C/s^{2}$
and therefore, we have that $E_{i}\leq(K-1)C/s^{2}$. ∎

##  Appendix F Auxiliary results

###  F.1. Truncated Gaussian distribution

######  Lemma F.1.

Consider $X\sim\mathcal{N}(0,\Sigma)$ a multivariate Gaussian distribution
$\Sigma\in\mathbb{R}^{d\times d}$ positive definite. For $R>0$, define the
truncated Gaussian random variable (r.v.) $X_{R}$ by conditioning $X$ to the
ball $\overline{\mathbb{B}}(0,R)$. Define

$\bar{\mathcal{H}}(p)\coloneqq\log\operatorname{\mathbb{E}}\left[e^{\langle
p,X_{R}\rangle}\right]$ (F.1.1)

and

$\widetilde{E}(\Sigma,\widetilde{R})\coloneqq
e^{-\tfrac{\widetilde{R}^{2}}{4\lVert\Sigma\rVert}}(\operatorname{tr}\Sigma+\lVert\Sigma\rVert)2^{d+3}$
(F.1.2)

Then, for $\widetilde{R}>0$ such that

$\widetilde{R}\geq\sqrt{\lVert\Sigma\rVert(2d+4)\log 2}\,,$ (F.1.3)

it holds that, for any $p\in\mathcal{X}$ such that $\lVert\Sigma p\rVert\leq
R-\widetilde{R}$,

$\displaystyle\left\lvert\bar{\mathcal{H}}(p)-\tfrac{1}{2}\langle p,\Sigma
p\rangle\right\rvert$
$\displaystyle\leq\tfrac{1}{2}\widetilde{E}(\Sigma,\widetilde{R})\lVert
p\rVert^{2}$ (F.1.4a)
$\displaystyle\left\lVert\nabla\bar{\mathcal{H}}(p)-\Sigma p\right\rVert$
$\displaystyle\leq\widetilde{E}(\Sigma,\widetilde{R})\lVert p\rVert$ (F.1.4b)
$\displaystyle\left\lVert\operatorname{Hess}\bar{\mathcal{H}}(p)-\Sigma\right\rVert$
$\displaystyle\leq\widetilde{E}(\Sigma,\widetilde{R})\,.$ (F.1.4c)

###### Proof.

Define, for $S$ a measurable set,

$Z(S)=\int_{S}e^{-\tfrac{1}{2}{x\cdot\Sigma^{-1}x}}\>dx\,,$ (F.1.5)

and, for convenience, $\mathcal{K}\coloneqq\overline{\mathbb{B}}(0,R)$. For
notational convenience, in this proof, we will denote the inner product
between two vectors $x$ and $p$ with a simple dot $x\cdot p$. We have that

$\displaystyle\operatorname{\mathbb{E}}\left[e^{X_{R}\cdot p}\right]$
$\displaystyle=\frac{e^{\tfrac{1}{2}p\cdot\Sigma
p}}{Z(\mathcal{K})}\int_{\mathcal{K}}e^{-\tfrac{1}{2}(x-\Sigma
p)\cdot\Sigma^{-1}(x-\Sigma p)}\>dx$
$\displaystyle=\frac{e^{\tfrac{1}{2}p\cdot\Sigma
p}}{Z(\mathcal{K})}\int_{\mathcal{K}-\Sigma
p}e^{-\tfrac{1}{2}x^{\prime}\cdot\Sigma^{-1}x^{\prime}}\>dx^{\prime}$
$\displaystyle=e^{\tfrac{1}{2}p\cdot\Sigma p}\frac{Z(\mathcal{K}-\Sigma
p)}{Z(\mathcal{K})}\,,$ (F.1.6)

where we performed the change of variable $x^{\prime}\leftarrow x-\Sigma p$.

Define

$f(p)\coloneqq Z(\mathcal{K}-\Sigma
p)=\int_{\mathcal{K}}e^{-\tfrac{1}{2}(x-\Sigma p)\cdot\Sigma^{-1}(x-\Sigma
p)}\>dx\,.$ (F.1.7)

so that

$\bar{\mathcal{H}}(p)=\log\operatorname{\mathbb{E}}\left[e^{X_{R}\cdot
p}\right]={\frac{1}{2}}p\cdot\Sigma p+\log\frac{f(p)}{f(0)}\,.$ (F.1.8)

Therefore it suffices to bound $\log\frac{f(p)}{f(0)}$ and its derivatives.

Differentiating yields

$\displaystyle\nabla f(p)$ $\displaystyle=\int_{\mathcal{K}}(x-\Sigma
p)e^{-\tfrac{1}{2}(x-\Sigma p)\cdot\Sigma^{-1}(x-\Sigma p)}\>dx$ (F.1.9a)
$\displaystyle\operatorname{Hess}f(p)$
$\displaystyle=\int_{\mathcal{K}}(x-\Sigma p)(x-\Sigma
p)^{\top}e^{-\tfrac{1}{2}(x-\Sigma p)\cdot\Sigma^{-1}(x-\Sigma p)}\>dx-\Sigma
f(p)\,.$ (F.1.9b)

Note that, by symmetry of $\overline{\mathbb{B}}(0,R)$, $\nabla f(0)=0$.

We first bound $\operatorname{Hess}f(p)$. Performing the change of variable
$x^{\prime}\leftarrow x-\Sigma p$ again gives us

$\displaystyle\operatorname{Hess}f(p)$ $\displaystyle=\int_{\mathcal{K}-\Sigma
p}x^{\prime}x^{\prime\top}e^{-\tfrac{1}{2}x^{\prime}\cdot\Sigma^{-1}x^{\prime}}\>dx^{\prime}-\Sigma
f(p)$ $\displaystyle=\int_{\mathcal{K}-\Sigma
p}(x^{\prime}x^{\prime\top}-\Sigma)e^{-\tfrac{1}{2}x^{\prime}\cdot\Sigma^{-1}x^{\prime}}\>dx^{\prime}$
$\displaystyle=-\int_{\mathcal{X}\setminus(\mathcal{K}-\Sigma
p)}(x^{\prime}x^{\prime\top}-\Sigma)e^{-\tfrac{1}{2}x^{\prime}\cdot\Sigma^{-1}x^{\prime}}\>dx^{\prime}\,,$
(F.1.10)

where we used that
$\int_{\mathcal{X}}(x^{\prime}x^{\prime\top}-\Sigma)e^{-\tfrac{1}{2}x^{\prime}\cdot\Sigma^{-1}x^{\prime}}\>dx^{\prime}=0$.

By definition of $\widetilde{R}$, $\mathcal{K}-\Sigma p$ contains
$\overline{\mathbb{B}}(0,\widetilde{R})$. We now bound the operator norm of
$\operatorname{Hess}f(p)$:

$\displaystyle\left\lVert\operatorname{Hess}f(p)\right\rVert$
$\displaystyle\leq\int_{\mathcal{X}\setminus(\mathcal{K}-\Sigma p)}(\lVert
x^{\prime}\rVert^{2}+\lVert\Sigma\rVert)e^{-\tfrac{1}{2}x^{\prime}\cdot\Sigma^{-1}x^{\prime}}\>dx^{\prime}$
$\displaystyle\leq\int_{\mathcal{X}\setminus\overline{\mathbb{B}}(0,\widetilde{R})}(\lVert
x^{\prime}\rVert^{2}+\lVert\Sigma\rVert)e^{-\tfrac{1}{2}x^{\prime}\cdot\Sigma^{-1}x^{\prime}}\>dx^{\prime}$
$\displaystyle\leq
e^{-\tfrac{\widetilde{R}^{2}}{4\lVert\Sigma\rVert}}\int_{\mathcal{X}}(\lVert
x^{\prime}\rVert^{2}+\lVert\Sigma\rVert)e^{-\tfrac{1}{4}x^{\prime}\cdot\Sigma^{-1}x^{\prime}}\>dx^{\prime}$
$\displaystyle=e^{-\tfrac{\widetilde{R}^{2}}{4\lVert\Sigma\rVert}}(\operatorname{tr}\Sigma+\lVert\Sigma\rVert)(4\pi)^{d/2}\det(\Sigma)^{1/2}\,,$
(F.1.11)

We now bound $\nabla f(p)$. The change of variable $x^{\prime}\leftarrow
x-\Sigma p$ yields

$\displaystyle\nabla f(p)$ $\displaystyle=\int_{\mathcal{K}-\Sigma
p}x^{\prime}e^{-\tfrac{1}{2}x^{\prime}\cdot\Sigma^{-1}x^{\prime}}\>dx^{\prime}=\int_{\mathcal{X}\setminus(\mathcal{K}-\Sigma
p)}x^{\prime}e^{-\tfrac{1}{2}x^{\prime}\cdot\Sigma^{-1}x^{\prime}}\>dx^{\prime}\,,$
(F.1.12)

where we used that
$\int_{\mathcal{X}}x^{\prime}e^{-\tfrac{1}{2}x^{\prime}\cdot\Sigma^{-1}x^{\prime}}\>dx^{\prime}=0$.

Therefore, similar computations as above yield that

$\displaystyle\lVert\nabla f(p)\rVert$
$\displaystyle\leq\int_{\mathcal{X}\setminus(\mathcal{K}-\Sigma p)}\lVert
x^{\prime}\rVert
e^{-\tfrac{1}{2}x^{\prime}\cdot\Sigma^{-1}x^{\prime}}\>dx^{\prime}$
$\displaystyle\leq\int_{\mathcal{X}\setminus\overline{\mathbb{B}}(0,\widetilde{R})}\lVert
x^{\prime}\rVert
e^{-\tfrac{1}{2}x^{\prime}\cdot\Sigma^{-1}x^{\prime}}\>dx^{\prime}$
$\displaystyle\leq
e^{-\tfrac{\widetilde{R}^{2}}{4\lVert\Sigma\rVert}}\int_{\mathcal{X}}\lVert
x^{\prime}\rVert
e^{-\tfrac{1}{4}x^{\prime}\cdot\Sigma^{-1}x^{\prime}}\>dx^{\prime}$
$\displaystyle\leq
e^{-\tfrac{\widetilde{R}^{2}}{4\lVert\Sigma\rVert}}\sqrt{\operatorname{tr}\Sigma}(4\pi)^{d/2}\det(\Sigma)^{1/2}\,.$
(F.1.13)

Let us now lower-bound $f(p)$. In the same fashion as above, we have that

$\displaystyle f(p)$ $\displaystyle=\int_{\mathcal{K}-\Sigma
p}e^{-\tfrac{1}{2}x^{\prime}\cdot\Sigma^{-1}x^{\prime}}\>dx^{\prime}$
$\displaystyle\geq\int_{\overline{\mathbb{B}}(0,\widetilde{R})}e^{-\tfrac{1}{2}x^{\prime}\cdot\Sigma^{-1}x^{\prime}}\>dx^{\prime}$
$\displaystyle\geq(2\pi)^{d/2}\det(\Sigma)^{1/2}\left(1-2^{d/2}e^{-\tfrac{\widetilde{R}^{2}}{4\lVert\Sigma\rVert}}\right)\,,$
(F.1.14)

so that, if $\widetilde{R}\geq\sqrt{\lVert\Sigma\rVert(2d+4)\log 2}$, it holds
that

$f(p)\geq\tfrac{1}{2}(2\pi)^{d/2}\det(\Sigma)^{1/2}$ (F.1.15)

The Hessian of $\log f/f(0)$ is then given by

$\operatorname{Hess}\log\frac{f(p)}{f(0)}=\frac{\operatorname{Hess}f(p)}{f(p)}-\frac{\nabla
f(p)\nabla f(p)^{\top}}{f(p)^{2}}\,.$ (F.1.16)

Eqs. F.1.11, F.1.13 and F.1.15 combined yield that

$\displaystyle\left\lVert\operatorname{Hess}\log\frac{f(p)}{f(0)}\right\rVert$
$\displaystyle\leq
e^{-\tfrac{\widetilde{R}^{2}}{4\lVert\Sigma\rVert}}(\operatorname{tr}\Sigma+\lVert\Sigma\rVert)2^{d/2+1}+\left(e^{-\tfrac{\widetilde{R}^{2}}{4\lVert\Sigma\rVert}}\sqrt{\operatorname{tr}\Sigma}2^{d/2+1}\right)^{2}$
$\displaystyle\leq
e^{-\tfrac{\widetilde{R}^{2}}{4\lVert\Sigma\rVert}}(\operatorname{tr}\Sigma+\lVert\Sigma\rVert)2^{d+3}=\widetilde{E}(\Sigma,\widetilde{R})\,.$
(F.1.17)

Taylor-Lagrange inequality now yields the full result since $\log f(0)/f(0)=0$
and $\nabla\log f(0)=0$. ∎

######  Lemma F.2.

Consider $X\sim\mathcal{N}(0,\sigma^{2}I)$ a multivariate Gaussian
distribution with $\sigma^{2}>0$. For $R>0$, define the truncated Gaussian
r.v. $X_{R}$ by conditioning $X$ to the ball $\overline{\mathbb{B}}(0,R)$.
Define

$\displaystyle\mathcal{H}(p)$
$\displaystyle\coloneqq\log\operatorname{\mathbb{E}}\left[e^{\langle
p,X_{R}\rangle}\right]$ (F.1.18a) $\displaystyle\mathcal{L}(p)$
$\displaystyle\coloneqq\mathcal{H}^{*}(p)\,,$ (F.1.18b)

and

$E(\sigma^{2},R)\coloneqq e^{-\tfrac{R^{2}}{16\sigma^{2}}}2^{d+3}(d+1)$
(F.1.19)

and assume that $R>0$ satisfies

$R\geq 4\sigma\sqrt{(d+3)\log 2+\log(d+1)}\,.$ (F.1.20)

Then, for any $p\in\mathcal{X}$ such that $\lVert
p\rVert\leq\frac{R}{2\sigma^{2}}$, $v\in\mathcal{X}$ such that $\lVert
v\rVert\leq\frac{R}{4}$, it holds that

$\displaystyle\left(1-E(\sigma^{2},R)\right)\frac{\sigma^{2}\lVert
p\rVert^{2}}{2}\leq$
$\displaystyle\bar{\mathcal{H}}(p)\leq\left(1+E(\sigma^{2},R)\right)\frac{\sigma^{2}\lVert
p\rVert^{2}}{2}$ (F.1.21a)
$\displaystyle\left(1-2E(\sigma^{2},R)\right)\frac{\lVert
v\rVert^{2}}{2\sigma^{2}}\leq$
$\displaystyle\bar{\mathcal{L}}(v)\leq\left(1+2E(\sigma^{2},R)\right)\frac{\lVert
v\rVert^{2}}{2\sigma^{2}}\,.$ (F.1.21b)

###### Proof.

First, let us show that, for any $r>0$,
$\nabla\mathcal{H}\left(\overline{\mathbb{B}}(0,r)\right)$ is an open ball
centered at 0. Since the distribution of $X_{R}$ is invariant by rotation,
this set can be rewritten as

$\nabla\mathcal{H}\left(\overline{\mathbb{B}}(0,r)\right)=\left\\{v\in\mathcal{X}:\lVert
v\rVert\in\left\\{\left\lVert\nabla\mathcal{H}(p)\right\rVert:p\in\overline{\mathbb{B}}(0,r)\right\\}\right\\}\,.$
(F.1.22)

But, by connectedness of $\overline{\mathbb{B}}(0,r)$ and continuity of
$\nabla\mathcal{H}$,
$\left\\{\left\lVert\nabla\mathcal{H}(p)\right\rVert:p\in\overline{\mathbb{B}}(0,r)\right\\}$
is an interval. Since $\nabla\mathcal{H}(0)=0$, it is either
$[0,\left\lVert\nabla\mathcal{H}(r)\right\rVert]$ or
$[0,\left\lVert\nabla\mathcal{H}(-r)\right\rVert)$.
$\nabla\mathcal{H}\left(\overline{\mathbb{B}}(0,r)\right)$ being compact and
therefore closed, it must be the latter. Hence, we have shown that

$\nabla\mathcal{H}\left(\overline{\mathbb{B}}(0,r)\right)=\overline{\mathbb{B}}\left(0,\sup_{\overline{\mathbb{B}}(0,r)}\left\lVert\nabla\mathcal{H}\right\rVert\right)\,.$
(F.1.23)

We apply Lemma F.1 with $\widetilde{R}\leftarrow{\frac{R}{2}}$. Note that our
choice of $R$ implies that $\widetilde{R}$ satisfies the condition of Lemma
F.1 and, moreover, that $E(\sigma^{2},R)\leq{\frac{1}{2}}$. Lemma F.1 directly
implies the bound on $\bar{\mathcal{H}}$.

Consider $p\in\mathcal{X}$ such that $\lVert
p\rVert\leq\frac{R}{2\sigma^{2}}$. Then, by Lemma F.1, we have that

$\displaystyle\left\lVert\nabla\bar{\mathcal{H}}\left(p\right)\right\rVert$
$\displaystyle\geq\sigma^{2}\lVert
p\rVert-e^{-\tfrac{R^{2}}{16\sigma^{2}}}2^{d+3}\left(\operatorname{tr}\left(\sigma^{2}I\right)+\left\lVert\sigma^{2}I\right\rVert\right)\lVert
p\rVert$ $\displaystyle=\sigma^{2}\lVert p\rVert(1-E(\sigma^{2},R))$
$\displaystyle\geq\frac{\sigma^{2}\lVert p\rVert}{2}\,,$ (F.1.24)

where we used that $E(\sigma^{2},R)\leq{\frac{1}{2}}$. Therefore, we obtain
that
$\sup\left\\{\left\lVert\nabla\bar{\mathcal{H}}(p)\right\rVert:p\in\overline{\mathbb{B}}\left(0,\frac{R}{2\sigma^{2}}\right)\right\\}\geq\frac{R}{4}$
so that
$\nabla\mathcal{H}\left(\overline{\mathbb{B}}(0,\frac{R}{2\sigma^{2}})\right)$
contains $\overline{\mathbb{B}}(0,\frac{R}{4})$.

Take $p\in\overline{\mathbb{B}}(0,\frac{R}{4})$ which therefore belongs to
$\nabla\mathcal{H}\left(\overline{\mathbb{B}}(0,\frac{R}{2\sigma^{2}})\right)$.
Therefore, $\bar{\mathcal{L}}(v)$ can be rewritten as

$\bar{\mathcal{L}}(v)=\sup_{p\in\overline{\mathbb{B}}(0,\frac{R}{2\sigma^{2}})}\langle
v,p\rangle-\bar{\mathcal{H}}(p)\,.$ (F.1.25)

Using Lemma F.1 again, we obtain that

$\displaystyle\sup_{p\in\overline{\mathbb{B}}(0,\frac{R}{2\sigma^{2}})}\langle
v,p\rangle-\frac{\sigma^{2}}{2}(1+E(\sigma^{2},R))\lVert
v\rVert^{2}\leq\bar{\mathcal{L}}(v)\leq\sup_{p\in\overline{\mathbb{B}}(0,\frac{R}{2\sigma^{2}})}\langle
v,p\rangle-\frac{\sigma^{2}}{2}(1-E(\sigma^{2},R))\lVert v\rVert^{2}\,,$
(F.1.26)

so that, since $E(\sigma^{2},R)\leq{\frac{1}{2}}$, we obtain that

$\frac{\lVert
v\rVert^{2}}{2\sigma^{2}(1+E(\sigma^{2},R))}\leq\bar{\mathcal{L}}(v)\leq\frac{\lVert
v\rVert^{2}}{2\sigma^{2}(1-E(\sigma^{2},R))}\,.$ (F.1.27)

Since, for $x\in[0,1/2]$, both $\frac{1}{1+x}\geq 1-2x$ and $\frac{1}{1-x}\leq
1+2x$ hold, we get

$\frac{\lVert
v\rVert^{2}}{2\sigma^{2}}\left(1-2E(\sigma^{2},R)\right)\leq\bar{\mathcal{L}}(v)\leq\frac{\lVert
v\rVert^{2}}{2\sigma^{2}}\left(1+2E(\sigma^{2},R)\right)$ (F.1.28)

which concludes the proof. ∎

We will require the following technical lemma.

######  Lemma F.3.

Consider $v,w\in\mathcal{X}$ such that $0<\lVert w\rVert\leq\tfrac{\mu R}{2}$
for some $R,\mu>0$. Define,

$f(u)=\sup_{p\in\mathcal{X}:\lVert p\rVert\leq R}\langle
p,u\rangle-{\frac{\mu}{2}}\lVert p\rVert^{2}\,,$ (F.1.29)

then, with $\lambda=\frac{\lVert v\rVert}{\lVert w\rVert}$,

$\lambda f\left(\frac{v}{\lambda}+w\right)\leq f(v+w)\,.$ (F.1.30)

###### Proof.

Define $p\coloneqq\frac{1}{\mu}\left(\frac{v}{\lambda}+w\right)$ which has
norm at most $R$ since $\lVert w\rVert\leq\frac{R}{2\mu}$. Then, we have that

$\displaystyle\lambda f\left(\frac{v}{\lambda}+w\right)-f(v+w)$
$\displaystyle\leq\lambda\left(\left\langle
p,\frac{v}{\lambda}+w\right\rangle-{\frac{\mu}{2}}\lVert
p\rVert^{2}\right)-\left(\langle p,v+w\rangle-{\frac{\mu}{2}}\lVert
p\rVert^{2}\right)$ $\displaystyle=(\lambda-1)\left(\langle
p,w\rangle-{\frac{\mu}{2}}\lVert p\rVert^{2}\right)$
$\displaystyle=(\lambda-1)\times\frac{1}{\mu}\left(\frac{\langle v,w\rangle
missing}{\lambda}+\lVert w\rVert^{2}-{\frac{1}{2}}\left(2\lVert
w\rVert^{2}+2\frac{\langle v,w\rangle missing}{\lambda}\right)\right)$
$\displaystyle=0\,,$ (F.1.31)

and our proof is complete. ∎

## References

  * Alongi & Nelson [2007] Alongi, J. M. and Nelson, G. S.  _Recurrence and Topology_ , volume 85 of _Graduate Studies in Mathematics_.  American Mathematical Society, 2007.
  * Antonakopoulos et al. [2022] Antonakopoulos, K., Mertikopoulos, P., Piliouras, G., and Wang, X.  AdaGrad avoids saddle points.  In _ICML ’22: Proceedings of the 39th International Conference on Machine Learning_ , 2022.
  * Benaïm [1999] Benaïm, M.  Dynamics of stochastic approximation algorithms.  In Azéma, J., Émery, M., Ledoux, M., and Yor, M. (eds.), _Séminaire de Probabilités XXXIII_ , volume 1709 of _Lecture Notes in Mathematics_ , pp. 1–68. Springer Berlin Heidelberg, 1999.
  * Benaïm & Hirsch [1995] Benaïm, M. and Hirsch, M. W.  Dynamics of Morse-Smale urn processes.  _Ergodic Theory and Dynamical Systems_ , 15(6):1005–1030, December 1995.
  * Bertsekas & Tsitsiklis [2000] Bertsekas, D. P. and Tsitsiklis, J. N.  Gradient convergence in gradient methods with errors.  _SIAM Journal on Optimization_ , 10(3):627–642, 2000.
  * Blanc et al. [2020] Blanc, G., Gupta, N., Valiant, G., and Valiant, P.  Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process.  In _COLT ’20: Proceedings of the 33rd Annual Conference on Learning Theory_ , 2020.
  * Brown [1986] Brown, L. D.  _Fundamentals of Statistical Exponential Families with Applications in Statistical Decision Theory_ , volume 9 of _Lecture Notes-Monograph Series_.  Institute of Mathematical Statistics, 1986.
  * Choromanska et al. [2015] Choromanska, A., Henaff, M., Mathieu, M., Ben Arous, G., and LeCun, Y.  The loss surfaces of multilayer networks.  In _AISTATS ’15: Proceedings of the 18th International Conference on Artificial Intelligence and Statistics_ , 2015.
  * Coste [1999] Coste, M.  An introduction to $o$-minimal geometry, 1999.
  * Dauphin et al. [2014] Dauphin, Y. N., Pascanu, R., Gulcehre, C., Cho, K., Ganguli, S., and Bengio, Y.  Identifying and attacking the saddle point problem in high-dimensional non-convex optimization.  In _NIPS ’14: Proceedings of the 27th International Conference on Neural Information Processing Systems_ , 2014.
  * de Acosta [2022] de Acosta, A. D.  _Large Deviations for Markov Chains_.  Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, UK, 2022.
  * Dembo & Zeitouni [1998] Dembo, A. and Zeitouni, O.  _Large Deviations Techniques and Applications_.  Springer-Verlag, Berlin, 1998.
  * Dieuleveut et al. [2020] Dieuleveut, A., Durmus, A., and Bach, F.  Bridging the gap between constant step size stochastic gradient descent and Markov chains.  _The Annals of Statistics_ , 48(3):1348–1382, June 2020.
  * Douc et al. [2018] Douc, R., Moulines, E., Priouret, P., and Soulier, P.  _Markov Chains_.  Springer Series in Operations Research and Financial Engineering. Springer, 2018.