\ \ \text{(see \eqref{def tilde T arrival time of large jump rescaled} for
definition of the stopping time involved)}$

and fix some $N>0$. From Lemma C.1, we see that (for all sufficiently small
$\eta$)

$\mathbb{P}(A^{\times}_{1}(\eta))\leq\eta^{N}.$

Besides, using Lemma B.2 together with the fact that
$\beta<\alpha(1-\widetilde{\gamma})$, we know the existence of some constant
$\theta>0$ such that

$\displaystyle\mathbb{P}(A^{\times}_{2}(\eta))\leq\eta^{\theta}$

for all sufficiently small $\eta$.

Now we focus on the behavior of the SGD iterates on event
$\Big{(}A^{\times}_{1}(\eta)\cap A^{\times}_{2}(\eta)\Big{)}^{c}$. Let us
arbitrarily choose some $x\in\Omega_{i}$ such that
$|x-s_{i}|\vee|x-s_{i-1}|>2\eta^{\gamma}$. First, from Lemma B.4 and (C.4), we
know that

$\displaystyle|\textbf{x}^{\eta}_{t}(x)-\textbf{y}^{\eta}_{\lfloor
t\rfloor}(x)|\leq 2\eta M\exp\big{(}2Mc_{2}\gamma\log(1/\eta)\big{)}\leq
2\eta^{2\widetilde{\gamma}-2Mc_{2}\gamma}\leq
2\eta^{\widetilde{\gamma}}\leq\eta^{\gamma}\ \ \forall t\leq
2c_{2}\gamma\log(1/\eta)/\eta$ (C.5)

Next, from the definition of the function $t^{\uparrow}(\cdot)$ and (C.5), we
know that for

$\displaystyle
T_{\text{GD,return}}(x;\eta,\Delta)\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\min\\{n\geq
0:\textbf{y}^{\eta}_{n}(x)\in B(m_{i},\frac{\Delta}{2}+\eta^{\gamma})\\},$
(C.6)

we have

$\displaystyle T_{\text{GD,return}}(x;\eta,\Delta)$ $\displaystyle\leq
2c_{2}\gamma\log(1/\eta)/\eta$ (C.7)
$\displaystyle\textbf{y}^{\eta}_{n}>s_{i-1}+\eta^{\gamma},\
\textbf{y}^{\eta}_{n}$ $\displaystyle<s_{i}-\eta^{\gamma}\ \ \forall n\leq
2c_{2}\gamma\log(1/\eta)/\eta.$ (C.8)

Furthermore, on event $\Big{(}A^{\times}_{1}(\eta)\cap
A^{\times}_{2}(\eta)\Big{)}^{c}$, due to Lemma B.3 and (C.4), we have that

$\displaystyle|X^{\eta}_{n}(x)-\textbf{y}^{\eta}_{n}(x)|\leq\eta^{\widetilde{\gamma}/2}\exp\big{(}2Mc_{2}\log(1/\eta)\big{)}=\eta^{\frac{\widetilde{\gamma}}{2}-2Mc_{2}\gamma}\leq\eta^{\widetilde{\gamma}/4}<\eta^{\gamma}\
\ \forall n\leq 2c_{2}\gamma\log(1/\eta)/\eta.$

Combining this with (C.7), (C.8), we can conclude that (recall that due to
(C.4) we have $2\eta^{\gamma}<\Delta/2$)

$\displaystyle T^{(i)}_{\text{return}}(\eta,\Delta)$ $\displaystyle\leq
2c_{2}\gamma\log(1/\eta)/\eta$ $\displaystyle X^{\eta}_{n}\in\Omega_{i}\ \ $
$\displaystyle\forall n\leq 2c_{2}\gamma\log(1/\eta)/\eta$

on event $\Big{(}A^{\times}_{1}(\eta)\cap A^{\times}_{2}(\eta)\Big{)}^{c}$.
Therefore,

$\displaystyle\liminf_{\eta\downarrow
0}\inf_{x\in\Omega_{i}:|x-s_{i-1}|\vee|x-s_{i}|\geq
2\eta^{\gamma}}\mathbb{P}_{x}\Big{(}T^{(i)}_{\text{return}}(\eta,\Delta)\leq
2c_{2}\gamma\log(1/\eta)/\eta,\ X^{\eta}_{n}\in\Omega_{i}\ \forall n\leq
T^{(i)}_{\text{return}}(\eta,\Delta)\Big{)}$ $\displaystyle\geq$
$\displaystyle\liminf_{\eta\downarrow
0}\mathbb{P}\Big{(}\Big{(}A^{\times}_{1}(\eta)\cap
A^{\times}_{2}(\eta)\Big{)}^{c}\Big{)}\geq\liminf_{\eta\downarrow
0}1-\eta^{N}-\eta^{\theta}=1.$

This concludes the proof. ∎

The takeaway of the next lemma is that, almost always, the SGD iterates will
quickly escape from the neighborhood of any $s_{i}$, the boundaries of each
attraction fields.

######  Lemma C.3.

Given any $\gamma\in(0,1),t>0$, we have

$\displaystyle\liminf_{\eta\downarrow
0}\inf_{x\in[-L,L]}\mathbb{P}_{x}\Big{(}\min\big{\\{}n\geq
0:X^{\eta}_{n}\notin\bigcup_{i}B(s_{i},2\eta^{\gamma})\big{\\}}\leq\frac{t}{H(1/\eta)}\Big{)}=1.$

###### Proof.

We only consider $\eta$ small enough so that

$\displaystyle\min_{i=2,3,\cdots,n_{\text{min}}-1}|s_{i}-s_{i-1}|$
$\displaystyle>3\eta^{\frac{1+\gamma}{2}},$ $\displaystyle\eta M$
$\displaystyle<\eta^{\gamma}.$

Also, the claim is trivial if $x\notin\cup_{j}B(s_{j},2\eta^{\gamma})$, so
without loss of generality we only consider the case where there is some
$j\in[n_{\text{min}}]$ and $x\in[-L,L],x\in B(s_{j},2\eta^{\gamma})$. Let us
define stopping times

$\displaystyle T^{\gamma}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\min\\{n\geq
1:\eta|Z_{n}|>5\eta^{\gamma}\\};$ (C.9) $\displaystyle
T^{\gamma}_{\text{escape}}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\min\\{n\geq
0:X^{\eta}_{n}\notin\cup_{j}B(s_{j},2\eta^{\gamma})\\},$ (C.10)

and the following two events

$\displaystyle A^{\times}_{1}(\eta)$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\\{T^{\gamma}>\frac{t}{H(1/\eta)}\\},$
$\displaystyle A^{\times}_{2}(\eta)$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\\{\eta|Z_{T^{\gamma}}|>\eta^{\frac{1+\gamma}{2}}\\}.$

First, using Lemma B.1 and the regularly varying nature of
$H(\cdot)=\mathbb{P}(|Z_{1}|>\cdot)$, we know the existence of some $\theta>0$
such that

$\displaystyle\mathbb{P}(A^{\times}_{1}(\eta))\leq\exp(-1/\eta^{\theta})$

for all $\eta>0$ sufficiently small. Next, by definition of $T^{\gamma}$, one
can see that (for any $\eta\in(0,1)$)

$\displaystyle\mathbb{P}(A^{\times}_{2}(\eta))$
$\displaystyle=\frac{H(1/\eta^{\frac{1-\gamma}{2}})}{H(5/\eta^{1-\gamma})}.$

Again, due to $H\in\mathcal{RV}_{-\alpha}$ and $1-\gamma>0$, we know the
existence of some $\theta_{1}>0$ such that

$\displaystyle\mathbb{P}(A^{\times}_{2}(\eta))<\eta^{\theta_{1}}$

for all $\eta>0$ sufficiently small. To conclude the proof, we only need to
note the following fact on event $\big{(}A^{\times}_{1}(\eta)\cup
A^{\times}_{2}(\eta)\big{)}^{c}$. There are only two possibilities on this
event: $T^{\gamma}_{\text{escape}}\leq T^{\gamma}-1$, or
$T^{\gamma}_{\text{escape}}\geq T^{\gamma}$. Now we analyze the two cases
respectively.

  * •

On $\big{(}A^{\times}_{1}(\eta)\cup
A^{\times}_{2}(\eta)\big{)}^{c}\cap\\{T^{\gamma}_{\text{escape}}\leq
T^{\gamma}-1\\}$, we must have $T^{\gamma}_{\text{escape}}<T^{\gamma}\leq
t/H(1/\eta)$.

  * •

On $\big{(}A^{\times}_{1}(\eta)\cup
A^{\times}_{2}(\eta)\big{)}^{c}\cap\\{T^{\gamma}_{\text{escape}}\geq
T^{\gamma}\\}$, we know that at $n=T^{\gamma}-1$, there exists an integer
$j\in\\{1,2,\cdots,n_{\text{min}}-1\\}$ such that $X^{\eta}_{n}\in
B(s_{j},2\eta^{\gamma})$. Now since $\eta M<\eta^{\gamma}$ and
$\eta|Z_{T^{\gamma}}|>5\eta^{\gamma}$, we must have

$\displaystyle|X^{\eta}_{T^{\gamma}}-X^{\eta}_{T^{\gamma}-1}|>4\eta^{\gamma}\Rightarrow
X^{\eta}_{T^{\gamma}}\notin B(s_{j},2\eta^{\gamma}).$

On the other hand, the exclusion of event $A^{\times}_{2}(\eta)$ tells us that
$|X^{\eta}_{T^{\gamma}}-X^{\eta}_{T^{\gamma}-1}|<2\eta^{\frac{1+\gamma}{2}}$.
Due to (C.9), we then have
$X^{\eta}_{n}\notin\cup_{i}B(s_{i},2\eta^{\gamma})$.

In summary, $\big{(}A^{\times}_{1}(\eta)\cup
A^{\times}_{2}(\eta)\big{)}^{c}\subseteq\\{T^{\gamma}_{\text{return}}\leq
t/H(1/\eta)\\}$ and this conclude the proof. ∎

In the next lemma, we analyze the number of transitions needed to visit a
certain local minimizer in the loss landscape. In general, we focus on a
communication class $G$ and, for now, assume it is absorbing. Next, we
introduce the following concepts to record the transitions between different
local minimum. To be specific, for any $\eta>0$ and any $\Delta>0$ small
enough so that $B(m_{j},\Delta)\cap\Omega_{j}^{c}=\emptyset$ for all $j$,
define

$\displaystyle T_{0}(\eta,\Delta)$ $\displaystyle=\min\\{n\geq 0:\
X_{n}^{\eta}\in\cup_{j}B(m_{j},2\Delta)\\};$ (C.11) $\displaystyle
I_{0}(\eta,\Delta)$ $\displaystyle=j\text{ iff
}X^{\eta}_{T_{0}(\eta,\Delta)}\in B(m_{j},2\Delta);$ (C.12) $\displaystyle
T_{k}(\eta,\Delta)$ $\displaystyle=\min\\{n>T_{k-1}(\eta,\Delta):\
X_{n}^{\eta}\in\cup_{j\neq I_{k-1}(\eta,\Delta)}B(m_{j},2\Delta)\\}\ \ \forall
k\geq 1$ (C.13) $\displaystyle I_{k}(\eta,\Delta)$ $\displaystyle=j\text{ iff
}X^{\eta}_{T_{k}(\eta,\Delta)}\in B(m_{j},2\Delta)\ \ \forall k\geq 1.$ (C.14)

As mentioned earlier, the next goal is to analyze the transitions between
attraction fields it takes to visit $m_{j}$ when starting from $m_{i}$ when
$m_{i},m_{j}\in G$. Define

$\displaystyle K_{i}(\eta,\Delta)$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\min\\{k\geq
0:\ I_{k}(\eta,\Delta)=i\\}.$

######  Lemma C.4.

Assume that $G$ is an absorbing communication class on the graph
$\mathcal{G}$. Then there exists some constant $p>0$ such that for any $i$
with $m_{i}\in G$, any $\epsilon>0$, and any $\Delta>0$,

$\displaystyle\sup_{j:\ m_{j}\in G;\ x\in
B(m_{j},2\Delta)}\mathbb{P}_{x}(K_{i}(\eta,\Delta)>u\cdot
n_{\text{min}})\leq\mathbb{P}(\text{Geom}(p)\geq u)+\epsilon\ \ \forall
u=1,2,\cdots,$ $\displaystyle\sup_{j:\ m_{j}\in G;\ x\in
B(m_{j},2\Delta)}\mathbb{P}_{x}\Big{(}\exists k\in[K_{i}(\eta,\Delta)]\ s.t.\
m_{I_{k}(\eta,\Delta)}\notin G\Big{)}\leq\epsilon$

hold for all $\eta>0$ sufficiently small.

###### Proof.

The claim is trivial if, for the initial condition, we have $x\in
B(m_{i},2\Delta)$. Next, let us observe the following facts.

  * •

Define (recall the definitions of measure $\mu_{i}$ and sets $E_{i},E_{i,j}$
in (3)(7)(8))

$\displaystyle J(j)$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\arg\min_{\widetilde{j}:\mu_{i}(E_{j,\widetilde{j}})>0}|i-\widetilde{j}|\
\ \forall j\neq i$ $\displaystyle p^{*}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\min_{j:\
j\neq i,\ m_{j}\in G}\frac{\mu_{j}(E_{j,J(j)})}{\mu_{j}(E_{j})}.$

  * •

From the definition of $J(j)$ and the fact that there are only finitely many
attraction fields we can see that $p^{*}>0$. Moreover, $G$ being a
communication class implies that

$|J(j)-i|<|j-i|\ \ \ \forall j\neq i,\ m_{j}\in G.$

Indeed, if $i<j$, then since $G$ is a communication class and there are some
$m_{i}\in G$ with $i<j$, we will at least have $\mu_{j}(E_{j,j-1})>0$, so
$|J(j)-i|\leq|i-j|-1$; the case that $i>j$ can be approached analogously.

  * •

Now from the definition of $J(j)$ and Proposition B.24, together with the
previous bullet point, we know that for all $\eta$ sufficiently small,

$\displaystyle\inf_{x\in[-L,L]}\mathbb{P}_{x}(|I_{k+1}-i|\leq|I_{k}-i|-1,\
m_{I_{k+1}}\in G\ |\ K_{i}(\eta,\Delta)>k,\ m_{I_{k}}\in G)\geq p^{*}/2$

uniformly for all $k\geq 0$.

  * •

Meanwhile, since $p^{*}>0$, we are able to fix some $\delta>0$ small enough
such that

$\displaystyle\frac{n_{\text{min}}\delta}{({p^{*}}/{2})^{n_{\text{min}}}}<\epsilon.$

  * •

On the other hand, for any $\widetilde{j}$ with $m_{\widetilde{j}}\notin G$,
by definition of the typical transition graph we must have
$\mu_{j}(E_{j,\widetilde{j}})=0$ for any $j$ with $m_{j}\in G$. Then due to
Proposition B.24 again, one can see that for all $\eta>0$ that is sufficiently
small,

$\displaystyle\sup_{x\in[-L,L]}\mathbb{P}_{x}(m_{I_{k+1}}\notin G\ |\
K_{i}(\eta,\Delta)>k,\ m_{I_{k}}\in G)<\delta$

uniformly for all $k\geq 0$.

  * •

Repeat this argument for $n_{\text{min}}$ times, and we can see that for all
$\eta$ sufficiently small

$\displaystyle\inf_{x\in[-L,L]}\mathbb{P}_{x}(K_{i}(\eta,\Delta)\leq
k+n_{\text{min}}\ |\ K_{i}(\eta,\Delta)>k,\ m_{I_{k}}\in G)$
$\displaystyle\geq\Big{(}\frac{p^{*}}{2}\Big{)}^{n_{\text{min}}}$
$\displaystyle\sup_{x\in[-L,L]}\mathbb{P}_{x}(\exists l\in[n_{\text{min}}]\
\text{s.t.}\ m_{I_{k+l}}\notin G\ |\ K_{i}(\eta,\Delta)>k,\ m_{I_{k}}\in G)$
$\displaystyle\leq n_{\text{min}}\delta$

uniformly for all $k\geq 1$.

  * •

Lastly, to apply the bounds established above, we will make use of the
following expression of several probabilities. For any $j$ with $m_{j}\in G$
and $x\in B(m_{j},2\Delta)$ and any $u=1,2,\cdots$,

$\displaystyle\mathbb{P}_{x}(\exists l\in[un_{\text{min}}]\ \text{s.t.
}m_{I_{l}}\notin G,\ K_{i}(\eta,\Delta)>u\cdot n_{\text{min}})$
$\displaystyle=$ $\displaystyle\sum_{v=0}^{u-1}\mathbb{P}_{x}\Big{(}\exists
k\in[n_{\text{min}}]\ \text{s.t. }m_{I_{k+vn_{\text{min}}}}\notin G\ \Big{|}\
K_{i}(\eta,\Delta)>v\cdot n_{\text{min}},\ m_{I_{l}}\in G\ \forall l\leq
vn_{\text{min}}\Big{)}$ $\displaystyle\ \ \
\cdot\prod_{w=0}^{v-1}\mathbb{P}_{x}\Big{(}K_{i}(\eta,\Delta)>(w+1)n_{\text{min}},\
m_{I_{k+wn_{\text{min}}}}\in G\ \forall k\in[n_{\text{min}}]\ \Big{|}\
K_{i}(\eta,\Delta)>w\cdot n_{\text{min}},\ m_{I_{l}}\in G\ \forall l\leq
wn_{\text{min}}\Big{)}$ $\displaystyle\mathbb{P}_{x}(m_{I_{l}}\in G\ \forall
l\in[un_{\text{min}}],\ K_{i}(\eta,\Delta)>u\cdot n_{\text{min}})$
$\displaystyle=$
$\displaystyle\prod_{v=0}^{u-1}\mathbb{P}\Big{(}K_{i}(\eta,\Delta)>(v+1)n_{\text{min}},\
m_{I_{k+vn_{\text{min}}}}\in G\ \forall k\in[n_{\text{min}}]\ \Big{|}\
K_{i}(\eta,\Delta)>vn_{\text{min}},\ m_{I_{k}}\in G\ \forall
k\in[vn_{\text{min}}]\Big{)}$

In summary, now we can see that (for sufficiently small $\eta$)

$\displaystyle\sup_{j:\ m_{j}\in G;\ x\in
B(m_{j},2\Delta)}\mathbb{P}_{x}\Big{(}\exists k\in[K_{i}(\eta,\Delta)]\ s.t.\
m_{I_{k}(\eta,\Delta)}\notin G\Big{)}$ $\displaystyle\leq$
$\displaystyle\sum_{u=0}^{\infty}\sup_{j:\ m_{j}\in G;\ x\in
B(m_{j},2\Delta)}\mathbb{P}_{x}\Big{(}\exists v\in[n_{\text{min}}]\text{ such
that }m_{I_{v+un_{\text{min}}}}\notin G,\
K_{i}(\eta,\Delta)>un_{\text{min}},m_{I_{k}}\in G\ \forall
k\in[un_{\text{min}}]\Big{)}$ $\displaystyle\leq$
$\displaystyle\sum_{u=0}^{\infty}\sup_{j:\ m_{j}\in G;\ x\in
B(m_{j},2\Delta)}\mathbb{P}_{x}\Big{(}\exists v\in[n_{\text{min}}]\text{ such
that }m_{I_{v+un_{\text{min}}}}\notin G\ \Big{|}\
K_{i}(\eta,\Delta)>un_{\text{min}},m_{I_{k}}\in G\ \forall
k\in[un_{\text{min}}]\Big{)}$ $\displaystyle\cdot\prod_{v=0}^{u-1}$
$\displaystyle\sup_{j:\ m_{j}\in G;\ x\in
B(m_{j},2\Delta)}\mathbb{P}_{x}\Big{(}K_{i}(\eta,\Delta)>(v+1)n_{\text{min}},m_{I_{k+vn_{\text{min}}}}\in
G\ \forall
k\in[n_{\text{min}}]\Big{|}K_{i}(\eta,\Delta)>vn_{\text{min}},m_{I_{k}}\in G\
\forall k\in[vn_{\text{min}}]\Big{)}$ $\displaystyle\leq$
$\displaystyle\sum_{u\geq
0}n_{\text{min}}\delta\Big{(}1-(\frac{p^{*}}{2})^{n_{\text{min}}}\Big{)}^{u-1}=\frac{n_{\text{min}}\delta}{({p^{*}}/{2})^{n_{\text{min}}}}\leq\epsilon$

and

$\displaystyle\sup_{j:m_{j}\in G,\ x\in
B(m_{j},2\Delta)}\mathbb{P}_{x}(K_{i}(\eta,\Delta)>u\cdot n_{\text{min}})$
$\displaystyle\leq$ $\displaystyle\sup_{j:m_{j}\in G,\ x\in
B(m_{j},2\Delta)}\mathbb{P}_{x}(\exists l\in[un_{\text{min}}]\ \text{s.t.
}m_{I_{l}}\notin G,\ K_{i}(\eta,\Delta)>u\cdot n_{\text{min}})$
$\displaystyle+$ $\displaystyle\sup_{j:m_{j}\in G,\ x\in
B(m_{j},2\Delta)}\mathbb{P}_{x}(m_{I_{l}}\in G\ \forall
l\in[un_{\text{min}}],\ K_{i}(\eta,\Delta)>u\cdot n_{\text{min}})$
$\displaystyle\leq$
$\displaystyle\sum_{v=1}^{u}n_{\text{min}}\delta\Big{(}1-(\frac{p^{*}}{2})^{n_{\text{min}}}\Big{)}^{v-1}+\Big{(}1-(\frac{p^{*}}{2})^{n_{\text{min}}}\Big{)}^{u}$
$\displaystyle\leq$
$\displaystyle\frac{n_{\text{min}}\delta}{({p^{*}}/{2})^{n_{\text{min}}}}+\Big{(}1-(\frac{p^{*}}{2})^{n_{\text{min}}}\Big{)}^{u}$
$\displaystyle\leq$
$\displaystyle\epsilon+\Big{(}1-(\frac{p^{*}}{2})^{n_{\text{min}}}\Big{)}^{u}$

uniformly for all $u=1,2,\cdots$. To conclude the proof, it suffices to set
$p=(\frac{p^{*}}{2})^{n_{\text{min}}}$. ∎

The proof above can be easily adapted to the case when the communication class
$G$ is transient. Define

$\displaystyle K^{G}_{i}(\eta,\Delta)$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\min\\{k\geq
0:\ I_{k}(\eta,\Delta)=i\ \text{or }m_{I_{k}(\eta,\Delta)}\notin G\\}.$

######  Lemma C.5.

Assume that $G$ is a transient communication class on the graph $\mathcal{G}$.
Then there exists some constant $p>0$ such that for any $i$ with $m_{i}\in G$
and any $\Delta\in(0,\bar{\epsilon}/3)$,

$\displaystyle\sup_{j:\ m_{j}\in G;\ x\in
B(m_{j},2\Delta)}\mathbb{P}_{x}(K^{G}_{i}(\eta,\Delta)>u\cdot n_{\text{min}})$
$\displaystyle\leq\mathbb{P}(\text{Geom}(p)\geq u)\ \ \forall u=1,2,\cdots$
(C.15)

hold for all $\eta>0$ sufficiently small.

###### Proof.

The structure of this proof is analogous to that of Lemma C.4. Again, the
claim is trivial if, for the initial condition, we have $x\in
B(m_{i},2\Delta)$. Next, let us observe the following facts.

  * •

Define (recall the definitions of measure $\mu_{i}$ and sets $E_{i},E_{i,j}$
in (3)(7)(8))

$\displaystyle J(j)$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\arg\min_{\widetilde{j}:\mu_{i}(E_{j,\widetilde{j}})>0}|i-\widetilde{j}|\
\ \forall j\neq i$ $\displaystyle p^{*}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\min_{j:\
j\neq i,\ m_{j}\in G}\frac{\mu_{j}(E_{j,J(j)})}{\mu_{j}(E_{j})}.$

  * •

From the definition of $J(j)$ and the fact that there are only finitely many
attraction fields we can see that $p^{*}>0$. Moreover, $G$ being a
communication class implies that

$|J(j)-i|<|j-i|\ \ \ \forall j\neq i,\ m_{j}\in G.$

Indeed, if $i<j$, then since $G$ is a communication class and there are some
$m_{i}\in G$ with $i<j$, we will at least have $\mu_{j}(E_{j,j-1})>0$, so
$|J(j)-i|\leq|i-j|-1$; the case that $i>j$ can be approached analogously.

  * •

Now from the definition of $J(j)$ and Proposition B.24, together with the
previous bullet point, we know that for all $\eta$ sufficiently small,

$\displaystyle\inf_{x\in[-L,L]}\mathbb{P}_{x}(|I_{k+1}-i|\leq|I_{k}-i|-1,\
m_{I_{k+1}}\in G\ |\ K^{G}_{i}(\eta,\Delta)>k\geq p^{*}/2$

uniformly for all $k\geq 0$.

  * •

Repeat this argument for $n_{\text{min}}$ times, and we can see that for all
$\eta$ sufficiently small

$\displaystyle\inf_{x\in[-L,L]}\mathbb{P}_{x}(K^{G}_{i}(\eta,\Delta)\leq
k+n_{\text{min}}\ |\ K^{G}_{i}(\eta,\Delta)>k)$
$\displaystyle\geq\Big{(}\frac{p^{*}}{2}\Big{)}^{n_{\text{min}}}$

uniformly for all $k\geq 1$.

  * •

Lastly, for any $j\neq i$ with $m_{j}\in G$ and $x\in B(m_{j},2\Delta)$ and
any $u=1,2,\cdots$,

$\displaystyle\mathbb{P}_{x}(K^{G}_{i}(\eta,\Delta)>u\cdot n_{\text{min}})$
$\displaystyle=$
$\displaystyle\prod_{v=0}^{u-1}\mathbb{P}_{x}\Big{(}K^{G}_{i}(\eta,\Delta)>(v+1)n_{\text{min}}\
\Big{|}\ K^{G}_{i}(\eta,\Delta)>v\cdot n_{\text{min}}\Big{)}$ $\displaystyle=$
$\displaystyle\prod_{v=0}^{u-1}\bigg{(}1-\mathbb{P}_{x}\Big{(}K^{G}_{i}(\eta,\Delta)\leq(v+1)n_{\text{min}}\
\Big{|}\ K^{G}_{i}(\eta,\Delta)>v\cdot n_{\text{min}}\Big{)}\bigg{)}$

In summary, now we can see that (for suffciently small $\eta$)

$\displaystyle\sup_{j:m_{j}\in G,\ x\in
B(m_{j},2\Delta)}\mathbb{P}_{x}(K^{G}_{i}(\eta,\Delta)\geq u\cdot
n_{\text{min}})\leq\Big{(}1-(\frac{p^{*}}{2})^{n_{\text{min}}}\Big{)}^{u}$

uniformly for all $u=1,2,\cdots$. To conclude the proof, it suffices to set
$p=(\frac{p^{*}}{2})^{n_{\text{min}}}$. ∎

We are now ready to prove Lemma 9, which, as demonstrated earlier, is the key
tool in proof of Theorem 2.

###### Proof of Lemma 9. .

The claim is trivial if $l^{\text{large}}=1$, so we focus on the case where
$l^{\text{large}}\geq 2$. Fix some

$\displaystyle\widetilde{\gamma}\in(0,(1-\frac{1}{\alpha})\wedge(\frac{1}{2})),\
\beta\in\big{(}1,(2-2\widetilde{\gamma})\wedge(\alpha-\alpha\widetilde{\gamma})\big{)},\
\gamma\in(0,\frac{\widetilde{\gamma}}{16Mc_{2}}\wedge\frac{\widetilde{\gamma}}{4}).$

Let $q^{*}=\max_{j}\mu_{j}(E_{j}(0))$. We show that for any
$t\in(0,\frac{\delta}{4q^{*}})$ the claim is true.

Now we only consider $\Delta\in(0,\bar{\epsilon}/3)$ and $\eta$ small enough
so that $\eta M\leq\eta^{\gamma}$ and $\eta^{\gamma}<\Delta$. Consider the
following stopping times

$\displaystyle T^{\gamma}_{\text{escape}}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\min\\{n\geq
0:X^{\eta}_{n}\notin\cup_{j}B(s_{j},2\eta^{\gamma})\\};$ $\displaystyle
T^{\gamma}_{\text{return}}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\min\\{n\geq
0:X^{\eta}_{n}\in\cup_{j}B(m_{j},2\eta^{\gamma})\\}.$

First, from Lemma C.3, we know that

$\displaystyle\sup_{x\in[-L,L]}\mathbb{P}_{x}(T^{\gamma}_{\text{escape}}>1/H(1/\eta))<\delta/2$

for all $\eta$ sufficiently small. Besides, by combining Lemma C.2 with Markov
property (applied at $T^{\gamma}_{\text{escape}}$), we have

$\displaystyle\sup_{x\in[-L,L]}\mathbb{P}_{x}\Big{(}\
T^{\gamma}_{\text{return}}-T^{\gamma}_{\text{escape}}>2c_{2}\gamma\log(1/\eta)/\eta\
\Big{|}\ T^{\gamma}_{\text{escape}}\leq\frac{1}{H(1/\eta)}\Big{)}<\delta/2$

for all $\eta$ sufficiently small. Therefore, for all $\eta$ sufficiently
small,

$\displaystyle\sup_{x\in[-L,L]}\mathbb{P}\Big{(}T^{\gamma}_{\text{return}}>\frac{1}{H(1/\eta)}+2c_{2}\gamma\frac{\log(1/\eta)}{\eta}\Big{)}<\delta.$
(C.16)

Let $J$ be the unique index such that
$X^{\eta}_{T^{\gamma}_{\text{return}}}\in\Omega_{J}$. Our next goal is to show
that, almost always, the SGD iterates will visit the local minimum at some
large attraction fields. Therefore, without loss of generality, we can assume
that $m_{J}\notin M^{\text{large}}$, and define

$\displaystyle
T^{\gamma}_{\text{large}}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\min\\{n\geq
T^{\gamma}_{\text{return}}:\ X^{\eta}_{n}\in\bigcup_{i:m_{i}\in
M^{\text{large}}}B(m_{i},2\Delta)\\}$

and introduce the following definitions:

$\displaystyle\tau_{0}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}T^{\gamma}_{\text{return}},\
J_{0}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}J$
$\displaystyle\tau_{k}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\min\\{n>\tau_{k-1}:\
X^{\eta}_{n}\in\bigcup_{j\neq J_{k-1}}B(m_{j},2\Delta)\\}$ $\displaystyle
J_{k}$ $\displaystyle=j\Leftrightarrow X^{\eta}_{\tau_{k}}\in\Omega_{j}\ \
\forall k\geq 1$ $\displaystyle K$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\min\\{k\geq
0:\ m_{J_{k}}\in M^{\text{large}}\\}.$

In other words, the sequence of stopping times $(\tau_{k})_{k\geq 1}$ is the
time that, starting from $T^{\gamma}_{\text{return}}$, the SGD iterates
visited a local minimum that is different from the one visited at
$\tau_{k-1}$, and $(J_{k})_{k\geq 0}$ records the label of the visited local
minima. The random variable $K$ is the number of transitions required to visit
a minimizer in a large attraction field. From Lemma C.4, we know the existence
of some $p^{*}>0$ such that (for all $\eta$ sufficiently small)

$\displaystyle\sup_{x\in[-L,L]}\mathbb{P}_{x}(K\geq u\cdot
n_{\text{min}})\leq\mathbb{P}\Big{(}\text{Geom}(p^{*})\geq
u\Big{)}+\frac{\delta}{2}\ \ \forall u=1,2,3,\cdots.$

where $\text{Geom}(a)$ is a Geometric random variable with success rate
$a\in(0,1)$. Therefore, one can find integer $N(\delta)$ such that (for all
sufficiently small $\eta$)

$\displaystyle\sup_{x\in[-L,L]}\mathbb{P}(K\geq N(\delta))\leq\delta.$ (C.17)

Next, given results in Proposition B.24 and the fact that there are only
finitely many attraction fields, one can find a real number $u(\delta)$ such
that (for all sufficiently small $\eta$)

$\displaystyle\sup_{x\in[-L,L]}\mathbb{P}_{x}(\tau_{k}-\tau_{k-1}\leq\frac{u(\delta)}{\lambda_{J_{k-1}}(\eta)})\leq\delta/N(\delta)$
(C.18)

uniformly for all $k=1,2,\cdots,N(\delta)$. From (C.16), (C.17),(C.18), we now
have

$\displaystyle\sup_{x\in[-L,L]}\mathbb{P}_{x}\Big{(}X^{\eta}_{n}\notin\bigcup_{j:m_{j}\in
M^{\text{large}}}B(m_{j},2\Delta)\ \forall n\leq
N(\delta)u(\delta)\frac{H(1/\eta)/\eta}{\lambda^{\text{large}}(\eta)}+\frac{1}{H(1/\eta)}+2c_{2}\gamma\frac{\log(1/\eta)}{\eta}\Big{)}\leq
3\delta$ (C.19)

for any sufficiently small $\eta$. To conclude the proof we just observe the
following facts. First, due to $H\in\mathcal{RV}_{-\alpha}$ and
$l^{\text{large}}\geq 2$, we have

$\displaystyle\lim_{\eta\downarrow 0}H(1/\eta)/\eta=0,\ \ \lim_{\eta\downarrow
0}\frac{\lambda^{\text{large}}(\eta)}{H(1/\eta)}=0,\ \ \lim_{\eta\downarrow
0}\frac{\log(1/\eta)}{\eta}\lambda^{\text{large}}(\eta)=0.$

Therefore, for sufficiently small $\eta$, we will have (note that
$\epsilon,\delta$ are fixed constants in this proof, so $N(\delta),u(\delta)$
are also fixed)

$\displaystyle\frac{N(\delta)u(\delta)\frac{H(1/\eta)/\eta}{\lambda^{\text{large}}(\eta)}+\frac{1}{H(1/\eta)}+2c_{2}\gamma\frac{\log(1/\eta)}{\eta}}{\lfloor
t/\lambda^{\text{large}}(\eta)\rfloor}\leq\epsilon.$ (C.20)

Second, recall that we fixed some $t\in(0,\frac{\delta}{4q^{*}})$ where
$q^{*}=\max_{j}\mu_{j}(E_{j})$. Also, choose some $C>0$ small enough so that

$\displaystyle C<\delta/2,\ 2(1+C)^{2}<4.$

From Proposition B.22 and the fact that there are only finitely many
attraction fields, there exists some $\bar{\eta}_{0}>0$ such that for any
$\eta\in(0,\bar{\eta}_{0})$ and any $\Delta>0$ sufficiently small,

$\displaystyle\sup_{i:m_{i}\in
M^{\text{large}}}\sup_{x\in[m_{i}-2\Delta,m_{i}+2\Delta]}\mathbb{P}_{x}\Big{(}\sigma_{i}(\eta)\leq\frac{t}{\lambda^{\text{large}}(\eta)}\Big{)}$
$\displaystyle\leq$ $\displaystyle\sup_{i:m_{i}\in
M^{\text{large}}}\sup_{x\in[m_{i}-2\Delta,m_{i}+2\Delta]}\mathbb{P}_{x}\Big{(}\mu_{i}(E_{i})\lambda^{\text{large}}(\eta)\sigma_{i}(\eta)\leq
q^{*}t\Big{)}$ $\displaystyle\leq$ $\displaystyle C+2(1+C)^{2}q^{*}t\leq
2\delta.$

Combine this bound with Markov property (applied at $\tau_{K}$), and we obtain
that

$\displaystyle\sup_{x\in[-L,L]}\mathbb{P}_{x}\Big{(}\exists n\in\big{[}\lfloor
t/\lambda^{\text{large}}(\eta)\rfloor\big{]}\ s.t.\
X^{\eta}_{n+\tau_{K}}\notin\bigcup_{i:m_{i}\in
M^{\text{large}}}\Omega_{i}\Big{)}\leq 2\delta$

for all $\eta$ sufficiently small. Together with (C.19)(C.20), we have shown
that

$\displaystyle\sup_{x\in[-L,L]}\mathbb{P}_{x}\Big{(}V^{\text{small}}(\eta,\epsilon,t)>\epsilon\Big{)}\leq
5\delta$

holds for all $\eta$ sufficiently small. ∎

###  C.2 Proof of Lemma 10, 11

We shall return to the discussion about the dynamics of SGD iterates on a
communication class $G$. Recall that

$G^{\text{large}}=\\{m^{\text{large}}_{1},\cdots,m^{\text{large}}_{i_{G}}\\},\
G^{\text{small}}=\\{m^{\text{small}}_{1},\cdots,m^{\text{small}}_{i_{G}^{\prime}}\\}.$

If $X^{\eta}_{n}$ is initialized at some sharp minimum on $G$, then we are
interested in the behavior of $X^{\eta}_{n}$ at the first visit to some large
attraction fields on $G$. Define

$\displaystyle
T_{G}(\eta,\Delta)\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\min\\{n\geq
0:X^{\eta}_{n}\in\bigcup_{i:\ m_{i}\in G^{\text{large}}}B(m_{i},2\Delta)\text{
or }X^{\eta}_{n}\notin\cup_{i:\ m_{i}\in G}\Omega_{i}\\}.$ (C.21)

Not only is this definition of $T_{G}$ analogous to the one for $T^{DTMC}_{G}$
in (33), but, as illustrated in the next lemma, $T_{G}$ also behaves similarly
as $T_{G}$ on a communication class $G$ in the following sense: the
probabilities $p_{i,j}$ defined in (34) govern the dynamics regarding which
large attraction field on $G$ is the first one to be visited. Besides, $T_{G}$
is usually rather small, meaning that the SGD iterates would efficiently
arrive at a large attraction field on $G$ or simply escape from $G$.

######  Lemma C.6.

Given any $\theta\in(0,(\alpha-1)/2)$, $\epsilon\in(0,1)$,
$i,j\in[n_{\text{min}}]$ such that $m_{i}\in G^{\text{small}},\ m_{j}\notin
G^{\text{large}}$, the following claims hold for all $\Delta>0$ that is
sufficiently small:

$\displaystyle\limsup_{\eta\downarrow 0}\sup_{x\in
B(m_{i},2\Delta)}\mathbb{P}_{x}\Big{(}T_{G}(\eta,\Delta)\leq\frac{\eta^{\theta}}{\lambda_{G}(\eta)},\
X^{\eta}_{T_{G}}\in B(m_{j},2\Delta)\Big{)}$ $\displaystyle\leq
p_{i,j}+5\epsilon,$ $\displaystyle\liminf_{\eta\downarrow 0}\inf_{x\in
B(m_{i},2\Delta)}\mathbb{P}_{x}\Big{(}T_{G}(\eta,\Delta)\leq\frac{\eta^{\theta}}{\lambda_{G}(\eta)},\
X^{\eta}_{T_{G}}\in B(m_{j},2\Delta)\Big{)}$ $\displaystyle\geq
p_{i,j}-5\epsilon,$ $\displaystyle\limsup_{\eta\downarrow 0}\sup_{x\in
B(m_{i},2\Delta)}\mathbb{P}_{x}\Big{(}T_{G}(\eta,\Delta)>\frac{\eta^{\theta}}{\lambda_{G}(\eta)}\Big{)}$
$\displaystyle\leq 2\epsilon.$

###### Proof.

For $G^{\text{small}}\neq\emptyset$ to hold (and the discussion to be
meaningful), we must have $l^{*}_{G}\geq 2$. Throughout the proof, we assume
this is the case. Besides, we require that $\Delta\in(0,\bar{\epsilon}/3)$ so
we have

$\displaystyle B(m_{i},3\Delta)\cap\Omega_{i}^{c}=\emptyset\ \forall
i\in[n_{\text{min}}]$

and the $3\Delta$-neighborhood of each local minimum will not intersect with
each other. In this proof we will only consider $\Delta$ in this range.

From Lemma C.4 (if $G$ is absorbing) or Lemma C.5 (if $G$ is transient), we
know the existence of some integer $N(\epsilon)$ such that for (see the
definition of $I_{k}$ in (C.11)-(C.14))

$\displaystyle
N_{G}(\eta,\Delta)\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\min\\{k\geq
0:\ m_{I_{k}(\eta,\Delta)}\in G^{\text{large}}\ \text{or
}m_{I_{k}(\eta,\Delta)}\notin G\\},$

we have

$\displaystyle\sup_{x\in
B(m_{i},2\Delta)}\mathbb{P}_{x}\Big{(}N_{G}(\eta,\Delta)>N(\epsilon)\Big{)}<\epsilon$

for all $\eta$ sufficiently small. Fix such $N(\epsilon)$. Next, from
Proposition B.24, we can find $u(\epsilon)\in(0,\infty)$ and
$\bar{\Delta}\in(0,\bar{\epsilon}/3)$ such that for all
$\Delta\in(0,\bar{\Delta})$, we have

$\displaystyle\sup_{x\in
B(m_{i},2\Delta)}\mathbb{P}_{x}\Big{(}T_{k}(\eta,\Delta)-T_{k-1}(\eta,\Delta)>u(\epsilon)/\Lambda\big{(}I_{k-1}(\eta,\Delta),\eta\big{)}\Big{)}\leq\epsilon/N(\epsilon)\
\ \forall k\in[N(\epsilon)]$

for all $\eta$ sufficiently small. Fix such $u(\epsilon)$ and $\bar{\Delta}$.
Now note that on the event

$\displaystyle A$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\Big{\\{}N_{G}\leq
N(\epsilon)\Big{\\}}\cap\Big{\\{}T_{k}(\eta,\Delta)-T_{k-1}(\eta,\Delta)\leq
u(\epsilon)/\Lambda\big{(}I_{k-1}(\eta,\Delta),\eta\big{)}\ \forall
k\in[N(\epsilon)]\Big{\\}},$

due to the choice of $\theta\in(0,(\alpha-1)/2)$ and
$H\in\mathcal{RV}_{-\alpha}$, we have (when $\eta\in(0,1)$)

$\displaystyle
T_{k}(\eta,\Delta)-T_{k-1}(\eta,\Delta)\leq\frac{\eta^{2\theta}}{\lambda_{G}(\eta)}\
\forall k<N_{G}(\eta,\Delta)$ $\displaystyle\Rightarrow$ $\displaystyle
T_{G}(\eta,\Delta)=T_{N_{G}(\eta,\Delta)}(\eta,\Delta)\leq
N(\epsilon)u(\epsilon)\frac{\eta^{2\theta}}{\lambda_{G}(\eta)}.$

For any $\eta$ sufficiently small, we will have
$N(\epsilon)u(\epsilon)\frac{\eta^{2\theta}}{\lambda_{G}(\eta)}<\frac{\eta^{\theta}}{\lambda_{G}(\eta)}$.
In summary, we have established that for all $\Delta\in(0,\bar{\Delta)}$,

$\displaystyle\limsup_{\eta\downarrow 0}\sup_{x\in
B(m_{i},2\Delta)}\mathbb{P}_{x}\Big{(}T_{G}>\frac{\eta^{\theta}}{\lambda_{G}(\eta)}\Big{)}\leq\limsup_{\eta\downarrow
0}\sup_{x\in B(m_{i},2\Delta)}\mathbb{P}_{x}(A^{c})<2\epsilon.$ (C.22)

Next, let

$\displaystyle\textbf{S}(\epsilon)\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\Big{\\{}\big{(}m^{\prime}_{1},\cdots,m^{\prime}_{N(\epsilon)}\big{)}\in\\{m_{1},\cdots,m_{n_{\text{min}}}\\}^{N(\epsilon)}:\
\exists k\in[N(\epsilon)]\ \text{s.t. }m^{\prime}_{k}=m_{j}\Big{\\}}.$

We can see that $\textbf{S}(\epsilon)$ contains all the possible transition
path for $Y^{DTMC}$ where the state $m_{j}$ is visited within the first
$N(\epsilon)$ steps. Obviously, $|\textbf{S}(\epsilon)|<\infty$. Let
$\epsilon_{1}=\epsilon/|\textbf{S}(\epsilon)|$. If we are able to show the
existence of some $\bar{\Delta}_{1}>0$ such that for all
$\Delta\in(0,\bar{\Delta}_{1})$, the following claim holds for any
$(m^{\prime}_{k})_{k=1}^{N(\epsilon)}\in\textbf{S}(\epsilon)$:

$\displaystyle\limsup_{\eta\downarrow 0}\sup_{x\in
B(m_{i},2\Delta)}\Big{|}\mathbb{P}_{x}\Big{(}m_{I_{k}}=m^{\prime}_{k}\ \forall
k\in[N(\epsilon)]\Big{)}-\mathbb{P}\Big{(}Y^{DTMC}_{k}(m_{i})=m^{\prime}_{k}\
\forall k\in[N(\epsilon)]\Big{)}\Big{|}<\epsilon_{1},$ (C.23)

then we must have (for all $\Delta\in(0,\bar{\Delta}\wedge\bar{\Delta}_{1})$)

$\displaystyle\limsup_{\eta\downarrow 0}\sup_{x\in
B(m_{i},2\Delta)}\Big{|}\mathbb{P}_{x}\Big{(}X^{\eta}_{T_{G}}\in
B(m_{j},2\Delta)\Big{)}-p_{i,j}\Big{|}$ $\displaystyle=$
$\displaystyle\limsup_{\eta\downarrow 0}\sup_{x\in
B(m_{i},2\Delta)}\Big{|}\mathbb{P}_{x}\Big{(}X^{\eta}_{T_{G}}\in
B(m_{j},2\Delta),\ T_{G}\leq
N(\epsilon)\Big{)}+\mathbb{P}_{x}\Big{(}X^{\eta}_{T_{G}}\in B(m_{j},2\Delta),\
T_{G}>N(\epsilon)\Big{)}$ $\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \
-\mathbb{P}\Big{(}Y^{DTMC}_{T^{DTMC}_{G}}(m_{i})=m_{j},\ T^{DTMC}_{G}\leq
N(\epsilon)\Big{)}-\mathbb{P}\Big{(}Y^{DTMC}_{T^{DTMC}_{G}}(m_{i})=m_{j},\
T^{DTMC}_{G}>N(\epsilon)\Big{)}\Big{|}$ $\displaystyle\leq$
$\displaystyle\limsup_{\eta\downarrow 0}\sup_{x\in
B(m_{i},2\Delta)}\Big{|}\mathbb{P}_{x}\Big{(}X^{\eta}_{T_{G}}\in
B(m_{j},2\Delta),\ T_{G}\leq
N(\epsilon)\Big{)}-\mathbb{P}\Big{(}Y^{DTMC}_{T^{DTMC}_{G}}(m_{i})=m_{j},\
T^{DTMC}_{G}\leq N(\epsilon)\Big{)}\Big{|}$ $\displaystyle\ \ \ \ \ \ \ \
+\limsup_{\eta\downarrow 0}\sup_{x\in
B(m_{i},2\Delta)}\mathbb{P}_{x}(T_{G}>N(\epsilon))+\mathbb{P}({T^{DTMC}_{G}}(m_{i})>N(\epsilon))$
$\displaystyle\leq$
$\displaystyle|\textbf{S}(\epsilon)|\epsilon_{1}+\limsup_{\eta\downarrow
0}\sup_{x\in
B(m_{i},2\Delta)}\mathbb{P}_{x}(T_{G}>N(\epsilon))+\mathbb{P}({T^{DTMC}_{G}}(m_{i})>N(\epsilon))$
$\displaystyle\leq$ $\displaystyle 3\epsilon.$

To show that (C.23) is true, we fix some
$(m^{\prime}_{k})_{k=1}^{N(\epsilon)}\in\textbf{S}(\epsilon)$ and let
$(\textbf{k}^{\prime}(k))_{k=1}^{N(\epsilon)}$ be the sequence with
$m_{\textbf{k}^{\prime}(k)}=m^{\prime}_{k}$ for each $k\in[N(\epsilon)]$. From
the definition of $Y^{DTMC}$ we have (let $\textbf{k}^{\prime}(0)=i$)

$\displaystyle\mathbb{P}\Big{(}Y^{DTMC}_{k}(m_{i})=m^{\prime}_{k}\ \forall
k\in[N(\epsilon)]\Big{)}=\prod_{k=0}^{N(\epsilon)-1}\frac{\mu_{\textbf{k}^{\prime}(k)}(E_{\textbf{k}^{\prime}(k),\textbf{k}^{\prime}(k+1)})}{\mu_{\textbf{k}^{\prime}(k)}(E_{\textbf{k}^{\prime}(k)})}.$

On the other hand, using Proposition B.24, we know that for any arbitrarily
chosen $\epsilon^{\prime}\in(0,1)$, we have

$\displaystyle\limsup_{\eta\downarrow 0}\sup_{x\in
B(m_{i},2\Delta)}\mathbb{P}_{x}\Big{(}m_{I_{k}(\eta,\Delta)}=m^{\prime}_{k}\
\forall
k\in[N(\epsilon)]\Big{)}\leq\prod_{k=0}^{N(\epsilon)-1}\frac{\mu_{\textbf{k}^{\prime}(k)}(E_{\textbf{k}^{\prime}(k),\textbf{k}^{\prime}(k+1)})}{\mu_{\textbf{k}^{\prime}(k)}(E_{\textbf{k}^{\prime}(k)})}\cdot(1+\epsilon^{\prime}),$
$\displaystyle\liminf_{\eta\downarrow 0}\inf_{x\in
B(m_{i},2\Delta)}\mathbb{P}_{x}\Big{(}m_{I_{k}(\eta,\Delta)}=m^{\prime}_{k}\
\forall
k\in[N(\epsilon)]\Big{)}\geq\prod_{k=0}^{N(\epsilon)-1}\frac{\mu_{\textbf{k}^{\prime}(k)}(E_{\textbf{k}^{\prime}(k),\textbf{k}^{\prime}(k+1)})}{\mu_{\textbf{k}^{\prime}(k)}(E_{\textbf{k}^{\prime}(k)})}\cdot(1-\epsilon^{\prime}),$

for all $\Delta>0$ sufficiently small. The arbitrariness of
$\epsilon^{\prime}>0$, together with $|\textbf{S}(\epsilon)|<\infty$, allows
us to see the existence of some $\bar{\Delta}_{1}>0$ such that with
$\Delta\in(0,\bar{\Delta}_{1})$, (C.23) holds for any
$(m^{\prime}_{k})_{k=1}^{N(\epsilon)}\in\textbf{S}(\epsilon)$. To conclude the
proof, observe that

$\displaystyle\limsup_{\eta\downarrow 0}\sup_{x\in
B(m_{i},2\Delta)}\Big{|}\mathbb{P}_{x}\Big{(}X^{\eta}_{T_{G}}\in
B(m_{j},2\Delta)\Big{)}-\mathbb{P}_{x}\Big{(}T_{G}(\eta,\Delta)\leq\frac{\eta^{\theta}}{\lambda_{G}(\eta)},\
X^{\eta}_{T_{G}}\in B(m_{j},2\Delta)\Big{)}\Big{|}$ $\displaystyle\leq$
$\displaystyle\limsup_{\eta\downarrow 0}\sup_{x\in
B(m_{i},2\Delta)}\mathbb{P}_{x}\Big{(}T_{G}>\frac{\eta^{\theta}}{\lambda_{G}(\eta)}\Big{)}<\epsilon$

due to (C.22). ∎

Recall that continuous-time process $X^{*,\eta}$ is the scaled version of
$X^{\eta}$ defined in (30), and the mapping
$\textbf{T}^{*}(n,\eta)\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}n\lambda_{G}(\eta)$
returns the timestamp $t$ for $X^{*,\eta}_{t}$ corresponding to the unscaled
step $n$ on the time horizon of $X^{\eta}_{n}$. As an inverse mapping of
$\textbf{T}^{*}$, we define the mapping $\textbf{N}^{*}(t,\eta)=\lfloor
t/\lambda_{G}(\eta)\rfloor$ that maps the scaled timestamp $t$ back to the
step number $n$ for the unscaled process $X^{\eta}$.

In the next lemma, we show that, provided that $X^{*,\eta}$ stays on a
communication class $G$ before some time $t$, the scaled process
$X^{*,\eta}_{t}$ is almost always in the largest attraction fields of a
communication class $G$.

######  Lemma C.7.

Let $G$ be a communication class on the graph $\mathcal{G}$. Given any
$\epsilon_{1}>0$, $t>0$ and any $x\in\Omega_{i}$ with $m_{i}\in G$, the
following claim holds for all $\Delta>0$ small enough:

$\displaystyle\limsup_{\eta\downarrow
0}\mathbb{P}_{x}\Big{(}\Big{\\{}X^{*,\eta}_{t}\notin\bigcup_{j:m_{j}\in
G^{\text{large}}}B(m_{j},3\Delta)\Big{\\}}\cap\Big{\\{}X^{*,\eta}_{s}\in\bigcup_{k:\
m_{k}\in G}\Omega_{k}\ \forall s\in[0,t]\Big{\\}}\Big{)}\leq 2\epsilon_{1}.$

###### Proof.

Let $\Delta\in(0,\bar{\epsilon}/3)$ for the constant $\bar{\epsilon}$ in
(B.15)(B.16), so we are certain that each $B(m_{i},2\Delta)$ lies entirely in
$\Omega_{i}$ and would not intersect with each other since

$\displaystyle B(m_{i},3\Delta)\cap\Omega_{i}^{c}=\emptyset\ \ \forall
i\in[n_{\text{min}}].$

Besides, with $\epsilon=\Delta/3$, we know the existence of some $\delta>0$
such that claims in Lemma B.12 would hold of the chosen $\epsilon,\delta$. Fix
such $\delta$ for the entirety of this proof. Lastly, fix some

$\displaystyle\widetilde{\gamma}\in(0,(1-\frac{1}{\alpha})\wedge(\frac{1}{2})),\
\beta\in\big{(}1,(2-2\widetilde{\gamma})\wedge(\alpha-\alpha\widetilde{\gamma})\big{)},\
\gamma\in(0,\frac{\widetilde{\gamma}}{16Mc_{2}}\wedge\frac{\widetilde{\gamma}}{4}).$

The blueprint of this proof is as follows. We will define a sequence of
stopping times $(N_{j})_{j=1}^{6}$ such that the corresponding scaled
timestamps $\textbf{T}^{*}_{j}=\textbf{T}^{*}(N_{j},\eta)$ gradually approach
$t$. By analyzing the behavior of $X^{*,\eta}$ on a time interval
$[t-\Delta_{t},t]$ that is very close to $t$ (in particular, on the
aforementioned stopping times $\textbf{T}^{*}_{j}$), we are able to establish
the properties of a series of events $A_{1}\supseteq A_{2}\supseteq A_{3}$.
Moreover, we will show that
$A_{3}\subseteq\\{X^{*,\eta,\Delta}_{t}\in\bigcup_{i:\ m_{i}\in
G^{\text{large}}}B(m_{i},3\Delta)\\}$, so the properties about events
$A,A_{2},A_{3}$ can be used to bound the probability of the target event.

Arbitrarily choose some $\Delta_{t}\in(0,t)$. To proceed, let
$N_{0}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\textbf{N}^{*}(t-\Delta_{t},\eta)$
be the stopping time corresponding to timestamp $t-\Delta_{t}$ for the scaled
process. Using Lemma C.3, we know that for stopping time
$N_{1}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\min\\{n\geq
N_{0}:\ X^{\eta}_{n}\notin\cup_{j}B(s_{j},2\eta^{\gamma})\\}$, we have

$\displaystyle\liminf_{\eta\downarrow
0}\inf_{x\in[-L,L]}\mathbb{P}_{x}(N_{1}-N_{0}<\frac{\Delta_{t}/4}{H(1/\eta)})=1.$

Next, let
$N_{2}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\min\\{n\geq
N_{1}:\ X^{\eta}_{n}\in\cup_{j}B(m_{j},2\Delta)\\}$. From Lemma C.2 and
$H\in\mathcal{RV}_{-\alpha}$ (so that $\log(1/\eta)/\eta=o(H(1/\eta))$, we
have

$\displaystyle\liminf_{\eta\downarrow
0}\inf_{x\in[-L,L]}\mathbb{P}_{x}(N_{2}-N_{1}<\frac{\Delta_{t}/4}{H(1/\eta)})=1.$

Collecting results above, we have

$\displaystyle\liminf_{\eta\downarrow
0}\inf_{x\in[-L,L]}\mathbb{P}_{x}(N_{2}-N_{0}<\frac{\Delta_{t}/2}{H(1/\eta)})=1.$
(C.24)

Now note the following fact on the event
$\\{N_{2}-N_{0}<\frac{\Delta_{t}/2}{H(1/\eta)}\\}$. The definition of the
mapping $\textbf{T}^{*}$ implies that, for any pair of positive integers
$n_{1}\leq n_{2}$, we have
$\textbf{T}^{*}(n_{2},\eta)-\textbf{T}^{*}(n_{1},\eta)=(n_{2}-n_{1})\lambda_{G}(\eta)\leq(n_{2}-n_{1})\cdot
H(1/\eta)$. Therefore, on
$\\{N_{2}-N_{0}\leq\frac{\Delta_{t}/2}{H(1/\eta)}\\}$ we have

$\displaystyle\textbf{T}^{*}(N_{2},\eta)-\textbf{T}^{*}(N_{0},\eta)<\Delta_{t}/2\Rightarrow\textbf{T}^{*}(N_{2},\eta)<t-\frac{\Delta_{t}}{2}.$

Besides, let $\textbf{T}^{*}_{2}=\textbf{T}^{*}(N_{2},\eta)$. Now we can see
that for event

$\displaystyle
A_{0}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\Big{\\{}X^{*,\eta}_{s}\in\bigcup_{k:\
m_{k}\in G}\Omega_{k}\ \forall
s\in[0,t]\Big{\\}}\cap\Big{\\{}N_{2}-N_{0}<\frac{\Delta_{t}/2}{H(1/\eta)}\Big{\\}},$

we have

$\displaystyle A_{0}\subseteq
A_{1}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\Big{\\{}\textbf{T}^{*}_{2}<t-\frac{\Delta_{t}}{2}\Big{\\}}\cap\Big{\\{}X^{*,\eta}_{s}\in\bigcup_{k:\
m_{k}\in G}\Omega_{k}\ \forall s\in[0,\textbf{T}^{*}_{2}]\Big{\\}}.$

Meanwhile, from (C.24) we obtain that

$\displaystyle\limsup_{\eta\downarrow
0}\sup_{x\in[-L,L]}\mathbb{P}_{x}\Big{(}A_{1}^{c}\cap\\{X^{*,\eta}_{s}\in\bigcup_{k:\
m_{k}\in G}\Omega_{k}\ \forall s\in[0,t]\\}\Big{)}=0.$ (C.25)

Moving on, we consider the following stopping times

$\displaystyle N_{3}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\min\\{n\geq
N_{2}:\ X^{\eta}_{n}\in\bigcup_{j:\ m_{j}\in
G^{\text{large}}}B(m_{j},2\Delta)\text{ or }X^{\eta}_{n}\notin\bigcup_{j:\
m_{j}\in G}\Omega_{j}\\},$ $\displaystyle\textbf{T}^{*}_{3}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\textbf{T}^{*}(N_{3},\eta).$

Using Lemma C.6, we have

$\displaystyle\limsup_{\eta\downarrow
0}\mathbb{P}_{x}\Big{(}N_{3}-N_{2}>\frac{\Delta_{t}/4}{\lambda_{G}(\eta)}\
\Big{|}\ A_{1}\Big{)}\leq\epsilon_{1}.$ (C.26)

Meanwhile, on event
$A_{1}\cap\Big{\\{}N_{3}-N_{2}\leq\frac{\Delta_{t}/4}{\lambda_{G}(\eta)}\Big{\\}}\cap\Big{\\{}X^{*,\eta}_{s}\in\bigcup_{k:\
m_{k}\in G}\Omega_{k}\ \forall s\in[0,t]\Big{\\}},$ we have
$\textbf{T}^{*}_{3}-\textbf{T}^{*}_{2}\leq\Delta_{t}/4$, hence
$\textbf{T}^{*}_{3}\in[t-\Delta_{t},t-\Delta_{t}/4]$. In summary,

$\displaystyle
A_{1}\cap\Big{\\{}N_{3}-N_{2}\leq\frac{\Delta_{t}/4}{\lambda_{G}(\eta)}\Big{\\}}\cap\Big{\\{}X^{*,\eta}_{s}\in\bigcup_{k:\
m_{k}\in G}\Omega_{k}\ \forall s\in[0,t]\Big{\\}}$
$\displaystyle\subseteq\Big{\\{}\textbf{T}^{*}_{3}\in[t-\Delta_{t},t-\Delta_{t}/4]\Big{\\}}\cap\Big{\\{}X^{*,\eta}_{s}\in\bigcup_{k:\
m_{k}\in G}\Omega_{k}\ \forall s\in[0,\textbf{T}^{*}_{3}]\Big{\\}}$

Moreover, on event $\Big{\\{}X^{*,\eta}_{s}\in\bigcup_{k:\ m_{k}\in
G}\Omega_{k}\ \forall s\in[0,t]\Big{\\}}$, if we let $J_{3}$ be label of the
local minimum visited at $\textbf{T}^{*}_{3}$ such that $J_{3}=j\iff
X^{*,\eta}_{T^{*}_{3}}\in B(m_{j},2\Delta)$, then we must have $m_{J_{3}}\in
G^{\text{large}}$. Meanwhile, consider the following stopping times

$\displaystyle\textbf{T}^{\sigma}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\min\\{s>\textbf{T}^{*}_{3}:\
X^{*,\eta}_{s}\notin\Omega_{J_{3}}\\}.$

From Proposition B.24, we know that

$\displaystyle\limsup_{\eta\downarrow
0}\mathbb{P}_{x}\Big{(}\textbf{T}^{\sigma}-\textbf{T}^{*}_{3}\leq\Delta_{t}\
\Big{|}\
\Big{\\{}\textbf{T}^{*}_{3}\in[t-\Delta_{t},t-\Delta_{t}/4]\Big{\\}}\cap\Big{\\{}X^{*,\eta}_{s}\in\bigcup_{k:\
m_{k}\in G}\Omega_{k}\ \forall s\in[0,\textbf{T}^{*}_{3}]\Big{\\}}\Big{)}$
$\displaystyle\leq$
$\displaystyle\epsilon_{1}+1-\exp\big{(}-(1+\epsilon_{1})q^{*}\Delta_{t}\big{)}$
(C.27)

where $q^{*}=\max_{j}\mu_{j}(E_{j})$. Now we define the event

$\displaystyle
A_{2}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}A_{1}\cap\Big{\\{}N_{3}-N_{2}\leq\frac{\Delta_{t}/4}{\lambda_{G}(\eta)}\Big{\\}}\cap\Big{\\{}\textbf{T}^{\sigma}-\textbf{T}^{*}_{3}>\Delta_{t}\Big{\\}}\cap\Big{\\{}X^{*,\eta}_{s}\in\bigcup_{k:\
m_{k}\in G}\Omega_{k}\ \forall s\in[0,\textbf{T}^{*}_{3}]\Big{\\}}.$

Using (C.25)-(C.27), we get

$\displaystyle\limsup_{\eta\downarrow
0}\sup_{x\in[-L,L]}\mathbb{P}_{x}\Big{(}A_{2}^{c}\cap\\{X^{*,\eta}_{s}\in\bigcup_{k:\
m_{k}\in G}\Omega_{k}\ \forall s\in[0,t]\\}\Big{)}\leq
2\epsilon_{1}+1-\exp\big{(}-(1+\epsilon_{1})q^{*}\Delta_{t}\big{)}.$ (C.28)

Furthermore, on event $A_{2}$, due to
$\textbf{T}^{*}_{3}\in[t-\Delta_{t},t-\Delta_{t}/4]$ as established above, we
must have

$\displaystyle X^{*,\eta}_{s}\in\Omega_{J_{3}}\ \forall
s\in[\textbf{T}^{*}_{3},t].$

Now let us focus on a timestamp
$\textbf{T}^{*}_{4}=t-\frac{\Delta_{t}/8}{H(1/\eta)}\lambda_{G}(\eta)$ and
$N_{4}=\textbf{N}^{*}(\textbf{T}^{*}_{4},\eta)$ . Obviously,
$\textbf{T}^{*}_{4}>\textbf{T}^{*}_{3}$ on event $A_{2}$. Next, define

$\displaystyle N_{5}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\min\\{n\geq
N_{4}:\ X^{\eta}_{n}\in\bigcup_{j}B(m_{j},2\Delta)\\}$
$\displaystyle\textbf{T}^{*}_{5}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\textbf{T}^{*}(N_{5},\eta).$

Using Lemma C.2 and C.3 again as we did above when obtaining (C.24), we can
show that

$\displaystyle\limsup_{\eta\downarrow
0}\mathbb{P}_{x}\Big{(}N_{5}-N_{4}>\frac{\Delta_{t}/16}{H(1/\eta)}\Big{)}=0.$
(C.29)

On the other hand, on event
$A_{2}\cap\Big{\\{}N_{5}-N_{4}\leq\frac{\Delta_{t}/16}{H(1/\eta)}\Big{\\}}$ we
must have

  * •

$\textbf{T}^{*}_{5}-\textbf{T}^{*}_{4}\leq\frac{\Delta_{t}/16}{H(1/\eta)}\lambda_{G}(\eta)$,
so
$\textbf{T}^{*}_{5}\in[t-\frac{\Delta_{t}/8}{H(1/\eta)}\lambda_{G}(\eta),t-\frac{\Delta_{t}/16}{H(1/\eta)}\lambda_{G}(\eta)]$;

  * •

$X^{*,\eta}_{\textbf{T}^{*}_{5}}\in\Omega_{J_{3}}$, due to
$\textbf{T}^{\sigma}-\textbf{T}^{*}_{3}>\Delta_{t}$.

This implies that for event

$\widetilde{A}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\Big{\\{}\textbf{T}^{*}_{5}\in[t-\frac{\Delta_{t}/8}{H(1/\eta)}\lambda_{G}(\eta),t-\frac{\Delta_{t}/16}{H(1/\eta)}\lambda_{G}(\eta)],\
X^{*,\eta}_{\textbf{T}^{*}_{5}}\in\Omega_{J_{3}}\Big{\\}}\cap\\{X^{*,\eta}_{s}\in\bigcup_{k:\
m_{k}\in G}\Omega_{j}\ \forall s\in[0,\textbf{T}^{*}_{5}]\\},$

we have
$A_{2}\cap\Big{\\{}N_{5}-N_{4}\leq\frac{\Delta_{t}/16}{H(1/\eta)}\Big{\\}}\subseteq\widetilde{A}$.
Lastly, observe that

  * •

From Lemma B.2, we know that for
$N_{6}(\delta)\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\min\\{n>N_{5}:\eta|Z_{n}|>\delta\\}$
we have

$\displaystyle\limsup_{\eta\downarrow
0}\mathbb{P}\big{(}N_{6}(\delta)-N_{5}\leq\Delta_{t}/H(1/\eta)\big{)}\leq\Delta_{t}/\delta^{\alpha};$

  * •

As stated at the beginning of the proof, our choice of $\delta$ allows us to
apply Lemma B.12 and show that

$\displaystyle\limsup_{\eta\downarrow
0}\sup_{x\in[-L,L]}\mathbb{P}_{x}\big{(}\exists n=N_{5},\cdots,N_{6}-1\
\text{s.t. }X^{\eta}_{n}\notin B(m_{J_{3}},3\Delta)\ |\
\widetilde{A}\big{)}=0;$

  * •

Combining the two bullet points above, we get

$\displaystyle\limsup_{\eta\downarrow 0}\mathbb{P}_{x}\Big{(}\exists
s\in[\textbf{T}^{*}_{5},t]\text{ such that }X^{*,\eta}_{s}\notin
B(m_{J_{3}},3\Delta)\ \Big{|}\
\widetilde{A}\Big{)}\leq\Delta_{t}/\delta^{\alpha}.$ (C.30)

On the other hand,

$\displaystyle\widetilde{A}\cap\\{X^{*,\eta}_{s}\in B(m_{J_{3}},3\Delta)\
\forall s\in[\textbf{T}^{*}_{5},t]\\}\subseteq\\{X^{*,\eta}_{t}\in\bigcup_{k:\
m_{k}\in G^{\text{large}}}B(m_{k},3\Delta)\\}.$

In summary, for event

$\displaystyle
A_{3}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}A_{2}\cap\Big{\\{}N_{5}-N_{4}\leq\frac{\Delta_{t}/16}{H(1/\eta)}\Big{\\}}\cap\Big{\\{}X^{*,\eta}_{s}\in
B(m_{J_{3}},3\Delta)\ \forall s\in[\textbf{T}^{*}_{5},t]\Big{\\}},$

we have $A_{3}\subseteq\\{X^{*,\eta}_{t}\in\bigcup_{k:\ m_{k}\in
G^{\text{large}}}B(m_{k},3\Delta)\\}$. Besides, due to (C.28)(C.29)(C.30), we
get

$\displaystyle\limsup_{\eta\downarrow
0}\sup_{x\in[-L,L]}\mathbb{P}_{x}\Big{(}A_{3}^{c}\cap\\{X^{*,\eta}_{s}\in\bigcup_{k:\
m_{k}\in G}\Omega_{k}\ \forall s\in[0,t]\\}\Big{)}$ $\displaystyle\leq$
$\displaystyle
2\epsilon_{1}+1-\exp\big{(}-(1+\epsilon_{1})q^{*}\Delta_{t}\big{)}+\frac{\Delta_{t}}{\delta^{\alpha}}.$

Remember that $\delta,\epsilon_{1},q^{*}$ are fixed constants while
$\Delta_{t}$ can be made arbitrarily small, so by driving $\Delta_{t}$ to 0 we
can conclude the proof. ∎

Recall the definition of jump processes in Definition 2. Central to the proof
of Lemma 10, the next result provides a set of sufficient conditions for the
convergence of a sequence of such jump processes in the sense of finite
dimensional distributions.

######  Lemma C.8.

For a sequence of processes $(Y^{n})_{n\geq 1}$ that, for each $n\geq 1$,
$Y^{n}$ is a $\Big{(}(U^{n}_{j})_{j\geq 0},(V^{n}_{j})_{j\geq 0}\Big{)}$ jump
process, and a $\Big{(}(U_{j})_{j\geq 0},(V_{j})_{j\geq 0}\Big{)}$ jump
process $Y$, if

  * •

$U_{0}\equiv 0$;

  * •

$(U^{n}_{0},V^{n}_{0},U^{n}_{1},V^{n}_{1},U^{n}_{2},V^{n}_{2},\cdots)$
converges in distribution to $(0,V_{0},U_{1},V_{1},U_{2},V_{2},\cdots)$ as
$n\rightarrow\infty$;

  * •

For any $x>0$ and any $n\geq 1$,

$\displaystyle\mathbb{P}(U_{1}+\cdots+U_{n}=x)=0;$

  * •

For any $x>0$,

$\displaystyle\lim_{n\rightarrow\infty}\mathbb{P}(U_{1}+U_{2}+\cdots
U_{n}>x)=1,$

then the finite dimensional distribution of $Y^{n}$ converges to that of $Y$
in the following sense: for any $k\in\mathbb{N}$ and any
$0<t_{1}<t_{2}<\cdots<t_{k}<\infty$, the random element
$(Y^{n}_{t_{1}},\cdots,Y^{n}_{t_{k}})$ converges in distribution to
$(Y_{t_{1}},\cdots,Y_{t_{k}})$ as $n\rightarrow\infty$.

###### Proof.

Fix some $k\in\mathbb{N}$ and $0<t_{1}<t_{2}<\cdots<t_{k}<\infty$. For
notational simplicity, let $t=t_{k}$. Let $(\mathbb{D},\textbf{d})$ be the
metric space where $\mathbb{D}=\mathbb{D}_{[0,t]}$, the space of all càdlàg
functions in $\mathbb{R}$ on the time interval $[0,t]$, and d is the Skorokhod
metric defined as

$\displaystyle\textbf{d}(\zeta_{1},\zeta_{2})\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\inf_{\lambda\in\Lambda}\left\lVert\zeta_{1}-\zeta_{2}\circ\lambda\right\rVert\vee\left\lVert\lambda-I\right\rVert$

where $\Lambda$ is the set of all nondecreasing homeomorphism from $[0,t]$
onto itself, and $I(s)=s$ is the identity mapping. Also, we arbitrarily choose
some $\epsilon\in(0,1)$ and some open set $A\subseteq\mathbb{R}^{k}$.

From the assumption, we can find integer $J(\epsilon)$ such that
$\mathbb{P}\Big{(}\sum_{j=1}^{J(\epsilon)}U_{j}\leq t\Big{)}<\epsilon$, as
well as an integer $N(\epsilon)$ such that, for all $n\geq N(\epsilon)$, we
have $\mathbb{P}\Big{(}\sum_{j=1}^{J(\epsilon)}U^{n}_{j}\leq
t\Big{)}+\mathbb{P}\Big{(}U^{n}_{0}\geq t_{1}\Big{)}<\epsilon$. We fix such
$J(\epsilon),N(\epsilon)$ (we may abuse the notation slightly and simply write
$J,N$ when there is no ambiguity).

Using Skorokhod’s representation theorem, we can construct a probability space
$(\bm{\Omega},\mathcal{F},\mathbb{Q})$ that supports random variables
$(\widetilde{U}^{n}_{0},\widetilde{V}^{n}_{0},\cdots,\widetilde{U}^{n}_{J},\widetilde{V}^{n}_{J})_{n\geq
1}$ and
$(\widetilde{U}_{0},\widetilde{V}_{0},\cdots,\widetilde{U}_{J},\widetilde{V}_{J})$
and satisfies the following conditions:

  * •

$\mathcal{L}(U^{n}_{0},V^{n}_{0},\cdots,U^{n}_{J},V^{n}_{J})=\mathcal{L}(\widetilde{U}^{n}_{0},\widetilde{V}^{n}_{0},\cdots,\widetilde{U}^{n}_{J},\widetilde{V}^{n}_{J})$
for all $n\geq 1$;

  * •

$\mathcal{L}(U_{0},V_{0},\cdots,U_{J},V_{J})=\mathcal{L}(\widetilde{U}_{0},\widetilde{V}_{0},\cdots,\widetilde{U}_{J},\widetilde{V}_{J})$;

  * •

$U^{n}_{j}\xrightarrow{a.s.}U_{j}$ and $V^{n}_{j}\xrightarrow{a.s.}V_{j}$ as
$n\rightarrow\infty$ for all $j\in[J]$.

Therefore, on $(\bm{\Omega},\mathcal{F},\mathbb{Q})$ we can define the
following random elements (taking values in the space of càdlàg functions):

$\displaystyle Y_{s}^{n,\downarrow J}$
$\displaystyle=\begin{cases}\phantom{-}\widetilde{V}^{n}_{0}&\text{if
}s<\widetilde{U}^{n}_{0}\\\
\sum_{j=0}^{J}\widetilde{V}^{n}_{j}\mathbbm{1}_{[\widetilde{U}^{n}_{0}+\widetilde{U}^{n}_{1}+\cdots+\widetilde{U}^{n}_{j},\
\widetilde{U}^{n}_{0}+\widetilde{U}^{n}_{1}+\cdots+\widetilde{U}^{n}_{j+1})}(s)&\text{otherwise}\end{cases},$
$\displaystyle Y^{\downarrow J}_{s}$
$\displaystyle=\sum_{j=0}^{J}\widetilde{V}_{j}\mathbbm{1}_{[\widetilde{U}_{1}+\cdots+\widetilde{U}_{j},\
\widetilde{U}_{1}+\cdots+\widetilde{U}_{j+1})}(s)\ \ \forall s\geq 0.$

Note that (1) for the first jump time of $Y^{\downarrow J}$ we have
$\widetilde{U}_{0}\equiv 0$, hence $Y^{\downarrow J}_{0}=\widetilde{V}_{0}$;
(2) when defining $Y^{n,\downarrow J}$ we set its value on
$[0,\widetilde{U}^{n}_{0})$ to be $\widetilde{V}^{n}_{0}$ instead of 0.

Since $U^{n}_{j}\xrightarrow{a.s.}U_{j}$ and
$V^{n}_{j}\xrightarrow{a.s.}V_{j}$ as $n\rightarrow\infty$ for all $j\in[J]$,
we must have

$\displaystyle\lim_{n}\textbf{d}(Y_{s}^{n,\downarrow J},Y_{s}^{\downarrow
J})=0$

almost surely, which further implies that $Y_{s}^{n,\downarrow J}\Rightarrow
Y_{s}^{\downarrow J}$ as $n\rightarrow\infty$ on $(\mathbb{D},\textbf{d})$.
Now from our assumption that, for the jump times $U_{1}+\cdots+U_{j}$, we have
$\mathbb{P}(U_{1}+\cdots+U_{j}=x)=0\ \forall x>0,j\geq 1$, as well as (13.3)
in [1], we then obtain

$\displaystyle(Y^{n,\downarrow J}_{t_{1}},\cdots,Y^{n,\downarrow
J}_{t_{k}})\Rightarrow(Y^{\downarrow J}_{t_{1}},\cdots,Y^{\downarrow
J}_{t_{k}})$ (C.31)

as $n\rightarrow\infty$. Recall that $A$ is the open set we arbitrarily chose
at the beginning of the proof, and $\epsilon>0$ is also chosen arbitrarily.
Now we observe the following facts.

  * •

Using (C.31), we can see that

$\displaystyle\liminf_{n}\mathbb{Q}\big{(}(Y^{n,\downarrow
J}_{t_{1}},\cdots,Y^{n,\downarrow J}_{t_{k}})\in
A\big{)}\geq\mathbb{Q}\big{(}Y^{\downarrow J}_{t_{1}},\cdots,Y^{\downarrow
J}_{t_{k}})\in A\big{)}.$

  * •

The choice of $N(\epsilon)$ and $J(\epsilon)$ above implies that

$\displaystyle\big{|}\mathbb{Q}\big{(}(Y^{\downarrow
J(\epsilon)}_{t_{1}},\cdots,Y^{\downarrow J(\epsilon)}_{t_{k}})\in
A\big{)}-\mathbb{P}\big{(}(Y_{t_{1}},\cdots,Y_{t_{k}})\in A\big{)}\big{|}$
$\displaystyle\leq\mathbb{P}\Big{(}\sum_{j=1}^{J(\epsilon)}U_{j}\leq
t\Big{)}<\epsilon$ $\displaystyle\big{|}\mathbb{Q}\big{(}(Y^{n,\downarrow
J(\epsilon)}_{t_{1}},\cdots,Y^{n,\downarrow J(\epsilon)}_{t_{k}})\in
A\big{)}-\mathbb{P}\big{(}(Y^{n}_{t_{1}},\cdots,Y^{n}_{t_{k}})\in
A\big{)}\big{|}$
$\displaystyle\leq\mathbb{P}\Big{(}\sum_{j=1}^{J(\epsilon)}U^{n}_{j}\leq
t\Big{)}+\mathbb{P}\Big{(}U^{n}_{0}\geq t_{1}\Big{)}<\epsilon\ \ \forall n\geq
N(\epsilon).$

Collecting the two results above, we have established that

$\displaystyle\liminf_{n}\mathbb{P}\big{(}(Y^{n}_{t_{1}},\cdots,Y^{n}_{t_{k}})\in
A\big{)}\geq\mathbb{P}\big{(}(Y_{t_{1}},\cdots,Y_{t_{k}})\in
A\big{)}-2\epsilon.$

From Portmanteau theorem, together with arbitrariness of $\epsilon>0$ and open
set $A$, we can now conclude that $(Y^{n}_{t_{1}},\cdots,Y^{n}_{t_{k}})$
converges in distribution to $(Y_{t_{1}},\cdots,Y_{t_{k}})$. ∎

The following lemma concerns the scaled version of the marker process
$\hat{X}^{*,\eta,\Delta}$ defined in (30)-(31). Obviously, it is a jump
process that complies with Definition 2. When there is no ambiguity about the
sequences $(\eta_{n})_{n\geq 1}$ and $(\Delta_{n})_{n\geq 1}$, let
$\hat{X}^{(n)}_{t}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\hat{X}^{*,\eta_{n},\Delta_{n}}_{t}$.
From (23)-(28) and (32), we know that for any $n\geq 1$, $\hat{X}^{(n)}$ is a
$\Big{(}\big{(}\tau^{*}_{k}(\eta_{n},\Delta_{n})-\tau^{*}_{k-1}(\eta_{n},\Delta_{n})\big{)}_{k\geq
0},\ \big{(}m_{I_{k}(\eta_{n},\Delta_{n})}\big{)}_{k\geq 0}\Big{)}$-jump
process (with the convention that $\tau^{*}_{-1}=0$). Also, for clarity of the
exposition, we let (for all $n\geq 1,k\geq 0$)

$\displaystyle\widetilde{S}^{(n)}_{k}$
$\displaystyle=\sigma^{*}_{k}(\eta_{n},\Delta_{n})-\tau^{*}_{k-1}(\eta_{n},\Delta_{n}),$
$\displaystyle S^{(n)}_{k}$
$\displaystyle=\tau^{*}_{k}(\eta_{n},\Delta_{n})-\tau^{*}_{k-1}(\eta_{n},\Delta_{n}),$
$\displaystyle\widetilde{W}^{(n)}_{k}$
$\displaystyle=m_{\widetilde{I}^{G}_{k}(\eta_{n},\Delta_{n})},$ $\displaystyle
W^{(n)}_{k}$ $\displaystyle=m_{I^{G}_{k}(\eta_{n},\Delta_{n})}.$

Lastly, remember that $Y$ is the continuous-time Markov chain defined in
(35)-(38) and $\pi_{G}(\cdot)$ is the random mapping defined in (39) that is
used to initialize $Y$. Besides, $Y$ is a $\big{(}(S_{k})_{k\geq
0},(W_{k})_{k\geq 0}\big{)}$ jump process under Definition 2, with $S_{0}=0$
and $W_{0}=\pi_{G}(m_{i})$ (here $x\in\Omega_{i}$ and $X^{\eta}_{0}=x$, so $i$
is the index of the attraction field where the SGD iterate is initialized).
The following result states that, given a sequence of learning rates
$(\eta_{n})_{n\geq 1}$ that tend to $0$, we are able to find a sequence of
$(\Delta_{n})_{n\geq 1}$ to parametrize
$\hat{X}^{(n)}=\hat{X}^{*,\eta_{n},\Delta_{n}},{X}^{(n)}={X}^{*,\eta_{n},\Delta_{n}}$
so that they have several useful properties, one of which is that the jump
times and locations of $\hat{X}^{(n)}$ converges in distribuiton to those of
$Y(\pi_{G}(m_{i}))$.

######  Lemma C.9.

Assume the communication class $G$ is absorbing. Given any $m_{i}\in G$,
$x\in\Omega_{i}$, finitely many real numbers $(t_{l})_{l=1}^{k^{\prime}}$ such
that $0<t_{1}<t_{2}<\cdots<t_{k^{\prime}}$, and a sequence of strictly
positive real numbers $(\eta_{n})_{n\geq 1}$ with $\lim_{n\rightarrow
0}\eta_{n}=0$, there exists a sequence of strictly positive real numbers
$(\Delta_{n})_{n\geq 1}$ with $\lim_{n}\Delta_{n}=0$ such that

  * •

Under $\mathbb{P}_{x}$ (so $X^{\eta}_{0}=x$), as $n$ tends to $\infty$,

$\displaystyle(S^{(n)}_{0},W^{(n)}_{0},S^{(n)}_{1},W^{(n)}_{1},S^{(n)}_{2},W^{(n)}_{2},\cdots)\Rightarrow(S_{0},W_{0},S_{1},W_{1},S_{2},W_{2},\cdots)$
(C.32)

  * •

(Recall the definition of $T_{k},I_{k}$ in (C.11)-(C.14)) Given any
$\epsilon>0$, the following claim holds for all $n$ sufficiently large:

$\displaystyle\sup_{k\geq 0}\mathbb{P}_{x}\Big{(}\exists
j\in[T_{k}(\eta_{n},\Delta_{n}),T_{k}(\eta_{n},\Delta_{n})]\ s.t.\
X^{\eta}_{j}\notin\bigcup_{l:\ m_{l}\in G}\Omega_{l}\ |\
m_{I_{k}(\eta_{n},\Delta_{n})}\in G\Big{)}<\epsilon;$ (C.33)

  * •

Given any $\epsilon>0$, the following claim holds for all $n$ sufficiently
large,

$\displaystyle\sup_{k\geq
0}\mathbb{P}_{k}\Big{(}m_{I_{k}(\eta_{n},\Delta_{n})+v}\notin
G^{\text{large}}\ \forall v\in[un_{\text{min}}]\ \Big{|}\
m_{I_{k}(\eta_{n},\Delta_{n})}\in G\Big{)}\leq\mathbb{P}(Geom(p^{*})\geq
u)+\epsilon\ \forall u=1,2,\cdots;$ (C.34)

  * •

For any $l\in[k^{\prime}]$,

$\displaystyle\lim_{n\rightarrow\infty}\mathbb{P}_{x}\Big{(}X^{*,\eta_{n}}_{t_{l}}\notin\bigcup_{j:\
m_{j}\in G^{\text{large}}}B(m_{j},\Delta_{n}),\
X^{*,\eta_{n}}_{s}\in\bigcup_{j:\ m_{j}\in G}\Omega_{j}\ \forall
s\in[0,t_{k^{\prime}}]\Big{)}=0$ (C.35)

where $p^{*}>0$ is a constant that does not vary with our choices of
$\eta_{n}$ or $\Delta_{n}$.

###### Proof.

Let

$\displaystyle\nu_{j}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}q_{j}=\mu_{j}(E_{j})$
$\displaystyle\nu_{j,k}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\mu_{j}(E_{j,k})$

so from the definition of $q_{j,k}$ we have $q_{j,k}=\mathbbm{1}\\{j\neq
k\\}\nu_{j,k}+\sum_{l:\ m_{l}\in G^{\text{small}}}\nu_{j,l}p_{l,k}$.

In order to specify our choice of $(\Delta_{n})_{n\geq 1}$, we consider a
construction of sequences $(\bar{\bm{\Delta}}(j))_{j\geq
0},(\bar{\bm{\eta}}(j))_{j\geq 0}$ as follows. Fix some
$\theta\in(0,\alpha-1)/2)$. Let $\bar{\bm{\Delta}}(0)=\bar{\bm{\eta}}(0)=1$.
One can see the existence of some $(\bar{\bm{\Delta}}(j))_{j\geq
1},(\bar{\bm{\eta}}(j))_{j\geq 1}$ such that

  * •

$\bar{\bm{\Delta}}(j)\in\big{(}0,\bar{\bm{\Delta}}(j-1)/2\big{]},\
\bar{\bm{\eta}}(j)\in\big{(}0,\bar{\bm{\eta}}(j-1)/2\big{]}$ for all $j\geq
1$;

  * •

(Due to Lemma C.2) for any $j\geq 1$, $\eta\in(0,\bar{\bm{\eta}}(j)]$,
(remember that $x$ and $i$ are the fixed constants prescribed in the
description of the lemma)

$\displaystyle\mathbb{P}_{x}\Big{(}\sigma^{*}_{0}\big{(}\eta,\bar{\bm{\Delta}}(j)\big{)}<\eta^{\theta},\
\widetilde{I}^{G}_{0}\big{(}\eta,\bar{\bm{\Delta}}(j)\big{)}=i\Big{)}>1-\frac{1}{2^{j}}.$

For definitions of
$\sigma^{G}_{k},\tau^{G}_{k},I^{G}_{k},\widetilde{I}^{G}_{k}$, see (23)-(28).

  * •

(Due to Lemma C.6) for any $j\geq 1$, $\eta\in(0,\bar{\bm{\eta}}(j)]$,

$\displaystyle\bigg{|}\mathbb{P}_{x}\Big{(}\tau^{*}_{k}\big{(}\eta,\bar{\bm{\Delta}}(j)\big{)}-\sigma^{*}_{k}\big{(}\eta,\bar{\bm{\Delta}}(j)\big{)}<\eta^{\theta},\
I^{G}_{k}\big{(}\eta,\bar{\bm{\Delta}}(j)\big{)}=i_{2}\ \Big{|}\
\widetilde{I}^{G}_{k}\big{(}\eta,\bar{\bm{\Delta}}(j)\big{)}=i_{1}\Big{)}-p_{i_{1},i_{2}}\bigg{|}<1/2^{j}$

uniformly for all $k\geq 0$ and all $m_{i_{1}}\in
G^{\text{small}},m_{i_{2}}\in G^{\text{large}}$. Also, by definition of
$\sigma^{*}$ and $\tau^{*}$, we must have

$\displaystyle\mathbb{P}_{x}\Big{(}\tau^{*}_{k}\big{(}\eta,\bar{\bm{\Delta}}(j)\big{)}-\sigma^{*}_{k}\big{(}\eta,\bar{\bm{\Delta}}(j)\big{)}=0,\
I^{G}_{k}\big{(}\eta,\bar{\bm{\Delta}}(j)\big{)}=i_{1}\ \Big{|}\
\widetilde{I}^{G}_{k}\big{(}\eta,\bar{\bm{\Delta}}(j)\big{)}=i_{1}\Big{)}=1$

for all $k\geq 0$ and $m_{i_{1}}\in G^{\text{large}}$.

  * •

(Due to Proposition B.24) for any $j\geq 1$, $\eta\in(0,\bar{\bm{\eta}}(j)]$,

$\displaystyle-\frac{1}{2^{j}}+\exp\big{(}-(1+\frac{1}{2^{j}})q_{i_{1}}u\big{)}\frac{\nu_{i_{1},i_{2}}-\frac{1}{2^{j}}}{q_{i_{1}}}$
$\displaystyle\leq$
$\displaystyle\mathbb{P}_{x}\Big{(}\sigma^{*}_{k+1}\big{(}\eta,\bar{\bm{\Delta}}(j)\big{)}-\tau^{*}_{k}\big{(}\eta,\bar{\bm{\Delta}}(j)\big{)}>u,\
\widetilde{I}^{G}_{k+1}=i_{2}\ \Big{|}\
I^{G}_{k}\big{(}\eta,\bar{\bm{\Delta}}(j)\big{)}=i_{1}\Big{)}$
$\displaystyle\leq$
$\displaystyle\frac{1}{2^{j}}+\exp\big{(}-(1-\frac{1}{2^{j}})q_{i_{1}}u\big{)}\frac{\nu_{i_{1},i_{2}}+\frac{1}{2^{j}}}{q_{i_{1}}}$

uniformly for all $k\geq 1$, all $u>1/2^{j}$, and all $m_{i_{1}}\in
G^{\text{large}},m_{i_{2}}\in G$.

  * •

(Due to $G$ being absorbing and, again, Proposition B.24) for any $j\geq 1$,
for any $j\geq 1$, $\eta\in(0,\bar{\bm{\eta}}(j)]$, (Recall the definition of
$T_{k},I_{k}$ in (C.11)-(C.14))

$\displaystyle\mathbb{P}_{x}\Big{(}I_{k+1}\big{(}\eta,\bar{\bm{\Delta}}(j)\big{)}=i_{2}\
|\ I_{k}\big{(}\eta,\bar{\bm{\Delta}}(j)\big{)}=i_{1}\Big{)}<\frac{1}{2^{j}}$
(C.36)

uniformly for all $k\geq 0$, $m_{i_{1}}\in G,m_{i_{2}}\notin G$.

  * •

(Due to Lemma C.4) There exists some $p^{*}>0$ such that for any $j\geq 1$,
for any $j\geq 1$, $\eta\in(0,\bar{\bm{\eta}}(j)]$,

$\displaystyle\mathbb{P}_{x}\Big{(}m_{v+I_{k}\big{(}\eta,\bar{\bm{\Delta}}(j)\big{)}}\notin
G^{\text{large}}\ \forall v\in[un_{\text{min}}]\ \Big{|}\
I_{k}\big{(}\eta,\bar{\bm{\Delta}}(j)\big{)}=i_{1}\Big{)}\leq\mathbb{P}(Geom(p^{*})\geq
u)+1/2^{j}$ (C.37)

uniformly for all $k\geq 0,u\geq 1$ and $m_{i_{1}}\in G$.

  * •

(Due to Lemma C.7) for any $j\geq 1$, for any $j\geq 1$,
$\eta\in(0,\bar{\bm{\eta}}(j)]$,

$\displaystyle\mathbb{P}_{x}\Big{(}X^{*,\eta_{n}}_{t_{k}}\notin\bigcup_{j:\
m_{j}\in G^{\text{large}}}B(m_{j},\bar{\bm{\Delta}}(j)),\
X^{*,\eta_{n}}_{s}\in\bigcup_{j:\ m_{j}\in G}\Omega_{j}\ \forall
s\in[0,t_{k^{\prime}}]\Big{)}<1/2^{j}$ (C.38)

uniformly for all $k\in[k^{\prime}]$.

Fix such $(\bar{\bm{\Delta}}(j))_{j\geq 0},(\bar{\bm{\eta}}(j))_{j\geq 0}$.
Define a function $\textbf{J}(\cdot):\mathbb{N}\mapsto\mathbb{N}$ as

$\displaystyle\textbf{J}(n)=0\vee\max\\{j\geq 0:\
\bar{\bm{\eta}}(j)\geq\eta_{n}\\}$

with the convention that $\max\emptyset=-\infty$. Lastly, let

$\displaystyle\Delta_{n}=\bar{\bm{\Delta}}(\textbf{J}(n))\ \forall n\geq 1.$

Note that, due to $\lim_{n}\eta_{n}=0$, we have
$\lim_{n}\textbf{J}(n)=\infty$, hence $\lim_{n}\Delta_{n}=0$. Besides, the
definition of $\textbf{J}(\cdot)$ tells us that in case that
$\textbf{J}(n)\geq 1$ (which will hold for all $n$ sufficiently large), the
claims above holds with $\eta=\eta_{n}$ and $j=\textbf{J}(n)$. In particular,
by combining $\lim_{n}\textbf{J}(n)=\infty$ with (C.36)(C.37)(C.38)
respectively, we have (C.33)(C.34)(C.35).

Now it remains to prove (C.32). To this end, it suffices to show that, for any
positive integer $K$, we have
$(S^{(n)}_{0},W^{(n)}_{0},\cdots,S^{(n)}_{K},W^{(n)}_{K})$ converges in
distribution $(S_{0},W_{0},\cdots,S_{K},W_{K})$ as $n$ tends to infinity. In
particular, note that $S_{0}=0,W_{0}=\pi_{G}(m_{i})$, so $W_{0}=m_{j}$ with
probability $p_{i,j}$ if $m_{i}\in G^{\text{small}}$, and $W_{0}\equiv m_{i}$
if $m_{i}\in G^{\text{large}}$.

For clarity of the exposition, we restate some important claims above under
the new notational system with
$\widetilde{S}^{(n)}_{k},\widetilde{W}^{(n)}_{k},S^{(n)}_{k},W^{(n)}_{k}$ we
introduced right above this lemma. Given any $\epsilon>0$, the following
claims hold for all $n$ sufficiently large:

  * •

First of all,

$\displaystyle\mathbb{P}_{x}\Big{(}\widetilde{S}^{(n)}_{0}<\eta_{n}^{\theta},\
\widetilde{W}^{(n)}_{0}=m_{i}\Big{)}>1-\epsilon.$ (C.39)

  * •

For all $k\geq 0$ and all $m_{i_{1}}\in G^{\text{small}},m_{i_{2}}\in
G^{\text{large}}$,

$\displaystyle\bigg{|}\mathbb{P}_{x}\Big{(}S^{(n)}_{k}-\widetilde{S}^{(n)}_{k}<\eta_{n}^{\theta},\
{W}^{(n)}_{k}=m_{i_{2}}\ \Big{|}\
\widetilde{W}^{(n)}_{k}=m_{i_{1}}\Big{)}-p_{i_{1},i_{2}}\bigg{|}<\epsilon.$
(C.40)

  * •

For all $k\geq 0$ and all $m_{i_{1}}\in G^{\text{large}}$,

$\displaystyle\mathbb{P}_{x}\Big{(}S^{(n)}_{k}-\widetilde{S}^{(n)}_{k}=0,\
{W}^{(n)}_{k}=m_{i_{1}}\ \Big{|}\ \widetilde{W}^{(n)}_{k}=m_{i_{1}}\Big{)}=1.$
(C.41)

  * •

For all $k\geq 0$, all $m_{i_{1}}\in G^{\text{large}},m_{i_{2}}\in G$ and all
$u>\epsilon$,

$\displaystyle-\epsilon+\exp\big{(}-(1+\epsilon)q_{i_{1}}u\big{)}\frac{\nu_{i_{1},i_{2}}-\epsilon}{q_{i_{1}}}$
$\displaystyle\leq$
$\displaystyle\mathbb{P}_{x}\Big{(}\widetilde{S}^{(n)}_{k+1}-S^{(n)}_{k}>u,\
\widetilde{W}^{(n)}_{k+1}=m_{i_{2}}\ \Big{|}\ W^{(n)}_{k}=m_{i_{1}}\Big{)}$
$\displaystyle\leq$
$\displaystyle\mathbb{P}_{x}\Big{(}\widetilde{S}^{(n)}_{k+1}-S^{(n)}_{k}>u-\eta_{n}^{\theta},\
\widetilde{W}^{(n)}_{k+1}=m_{i_{2}}\ \Big{|}\ W^{(n)}_{k}=m_{i_{1}}\Big{)}$
$\displaystyle\leq$
$\displaystyle\epsilon+\exp\big{(}-(1-\epsilon)q_{i_{1}}u\big{)}\frac{\nu_{i_{1},i_{2}}+\epsilon}{q_{i_{1}}}$
(C.42)

  * •

Here is one implication of (C.40). Since $|G|\leq n_{\text{min}}$, we have

$\displaystyle\mathbb{P}_{x}\Big{(}S^{(n)}_{k}-\widetilde{S}^{(n)}_{k}\geq\eta_{n}^{\theta}\
\Big{|}\ \widetilde{W}^{(n)}_{k}=m_{i_{1}}\Big{)}<n_{\text{min}}\cdot\epsilon$
(C.43)

for all $k\geq 0$ and $m_{i_{1}}\in G^{\text{small}}$.

  * •

Note that for any $m_{i_{1}},m_{i_{2}}\in G^{\text{large}}$ and any $k\geq 0$

$\displaystyle\mathbb{P}_{x}\Big{(}S^{(n)}_{k+1}-S^{(n)}_{k}>u,\
W^{(n)}_{k+1}=m_{i_{2}}\ \Big{|}\ W^{(n)}_{k}=m_{i_{1}}\Big{)}$
$\displaystyle=$ $\displaystyle\mathbbm{1}\\{i_{2}\neq
i_{1}\\}\mathbb{P}_{x}\Big{(}\widetilde{S}^{(n)}_{k+1}-S^{(n)}_{k}>u,\
\widetilde{W}^{(n)}_{k+1}=m_{i_{2}}\ \Big{|}\ W^{(n)}_{k}=m_{i_{1}}\Big{)}$
$\displaystyle+$ $\displaystyle\sum_{i_{3}:\ m_{i_{3}}\in
G^{\text{small}}}\int_{s>0}\mathbb{P}_{x}\Big{(}S^{(n)}_{k+1}-\widetilde{S}^{(n)}_{k+1}\geq(u-s)\vee
0,\ \widetilde{W}^{(n)}_{k+1}=m_{i_{2}}\ \Big{|}\
\widetilde{W}^{(n)}_{k}=m_{i_{3}}\Big{)}$ $\displaystyle\ \ \ \ \ \ \ \ \ \ \
\ \cdot\mathbb{P}_{x}\Big{(}\widetilde{S}^{(n)}_{k+1}-S^{(n)}_{k}=ds,\
\widetilde{W}^{(n)}_{k+1}=m_{i_{3}}\ \Big{|}\ W^{(n)}_{k}=m_{i_{1}}\Big{)}.$

Fix some $i_{3}$ with $m_{i_{3}}\in G^{\text{small}}$. On the one hand, due to
(C.43),

$\displaystyle\int_{s\in(0,u-\eta^{\theta}_{n}]}\mathbb{P}_{x}\Big{(}S^{(n)}_{k+1}-\widetilde{S}^{(n)}_{k+1}\geq
u-s,\ \widetilde{W}^{(n)}_{k+1}=m_{i_{2}}\ \Big{|}\
\widetilde{W}^{(n)}_{k}=m_{i_{3}}\Big{)}$ $\displaystyle\ \ \ \ \ \ \ \ \ \
\cdot\mathbb{P}_{x}\Big{(}\widetilde{S}^{(n)}_{k+1}-S^{(n)}_{k}=ds,\
\widetilde{W}^{(n)}_{k+1}=m_{i_{3}}\ \Big{|}\ W^{(n)}_{k}=m_{i_{1}}\Big{)}$
$\displaystyle\leq$ $\displaystyle n_{\text{min}}\epsilon.$

On the other hand, by considering the integral on
$(u-\eta_{n}^{\theta},\infty)$, we get

$\displaystyle\int_{s\in(u-\eta^{\theta}_{n},\infty)}\mathbb{P}_{x}\Big{(}S^{(n)}_{k+1}-\widetilde{S}^{(n)}_{k+1}\geq(u-s)\vee
0,\ \widetilde{W}^{(n)}_{k+1}=m_{i_{2}}\ \Big{|}\
\widetilde{W}^{(n)}_{k}=m_{i_{3}}\Big{)}$ $\displaystyle\ \ \ \ \ \ \ \ \ \
\cdot\mathbb{P}_{x}\Big{(}\widetilde{S}^{(n)}_{k+1}-S^{(n)}_{k}=ds,\
\widetilde{W}^{(n)}_{k+1}=m_{i_{3}}\ \Big{|}\ W^{(n)}_{k}=m_{i_{1}}\Big{)}$
$\displaystyle\geq$
$\displaystyle\int_{s\in(u,\infty)}\mathbb{P}_{x}\Big{(}\widetilde{W}^{(n)}_{k+1}=m_{i_{2}}\
\Big{|}\
\widetilde{W}^{(n)}_{k}=m_{i_{3}}\Big{)}\cdot\mathbb{P}_{x}\Big{(}\widetilde{S}^{(n)}_{k+1}-S^{(n)}_{k}=ds,\
\widetilde{W}^{(n)}_{k+1}=m_{i_{3}}\ \Big{|}\ W^{(n)}_{k}=m_{i_{1}}\Big{)}$
$\displaystyle\geq$
$\displaystyle(p_{i_{3},i_{2}}-\epsilon)\Big{(}-\epsilon+\exp\big{(}-(1+\epsilon)q_{i_{1}}u\big{)}\frac{\nu_{i_{1},i_{3}}-\epsilon}{q_{i_{1}}}\Big{)}$

due to (C.40) and (C.42). Meanwhile,

$\displaystyle\int_{s\in(u-\eta^{\theta}_{n},\infty)}\mathbb{P}_{x}\Big{(}S^{(n)}_{k+1}-\widetilde{S}^{(n)}_{k+1}\geq(u-s)\vee
0,\ \widetilde{W}^{(n)}_{k+1}=m_{i_{2}}\ \Big{|}\
\widetilde{W}^{(n)}_{k}=m_{i_{3}}\Big{)}$ $\displaystyle\ \ \ \ \ \ \ \ \ \
\cdot\mathbb{P}_{x}\Big{(}\widetilde{S}^{(n)}_{k+1}-S^{(n)}_{k}=ds,\
\widetilde{W}^{(n)}_{k+1}=m_{i_{3}}\ \Big{|}\ W^{(n)}_{k}=m_{i_{1}}\Big{)}$
$\displaystyle\leq$
$\displaystyle(n_{\text{min}}\epsilon+p_{i_{3},i_{2}}+\epsilon)\Big{(}\epsilon+\exp\big{(}-(1-\epsilon)q_{i_{1}}u\big{)}\frac{\nu_{i_{1},i_{3}}+\epsilon}{q_{i_{1}}}\Big{)}$

due to (C.40), (C.42) and (C.43).

  * •

Therefore, for any $m_{i_{1}},m_{i_{2}}\in G^{\text{large}}$ and any $k\geq
0$,

$\displaystyle\mathbb{P}_{x}\Big{(}S^{(n)}_{k+1}-S^{(n)}_{k}>u,\
W^{(n)}_{k+1}=m_{i_{2}}\ \Big{|}\ W^{(n)}_{k}=m_{i_{1}}\Big{)}$
$\displaystyle\leq$ $\displaystyle
g(\epsilon)+\exp\big{(}-(1-\epsilon)q_{i_{1}}u\big{)}\frac{\mathbbm{1}\\{i_{2}\neq
i_{1}\\}\nu_{i_{1},i_{2}}+\sum_{i_{3}:\ m_{i_{3}}\in
G^{\text{small}}}\nu_{i_{1},i_{3}}p_{i_{3},i_{2}}}{q_{i_{1}}}$
$\displaystyle\leq$ $\displaystyle
g(\epsilon)+\exp\big{(}-(1-\epsilon)q_{i_{1}}u\big{)}\frac{q_{i_{1},i_{2}}}{q_{i_{1}}}$
(C.44)

and

$\displaystyle\mathbb{P}_{x}\Big{(}S^{(n)}_{k+1}-S^{(n)}_{k}>u,\
W^{(n)}_{k+1}=m_{i_{2}}\ \Big{|}\ W^{(n)}_{k}=m_{i_{1}}\Big{)}$
$\displaystyle\geq$
$\displaystyle-g(\epsilon)+\exp\big{(}-(1+\epsilon)q_{i_{1}}u\big{)}\frac{\mathbbm{1}\\{i_{2}\neq
i_{1}\\}\nu_{i_{1},i_{2}}+\sum_{i_{3}:\ m_{i_{3}}\in
G^{\text{small}}}\nu_{i_{1},i_{3}}p_{i_{3},i_{2}}}{q_{i_{1}}}$
$\displaystyle\geq$
$\displaystyle-g(\epsilon)+\exp\big{(}-(1+\epsilon)q_{i_{1}}u\big{)}\frac{q_{i_{1},i_{2}}}{q_{i_{1}}}$
(C.45)

where $q^{*}=\max_{i}q_{i}$ and

$\displaystyle
g(\epsilon)\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\epsilon+\frac{\epsilon}{q^{*}}+n_{\text{min}}(1+\epsilon)\epsilon+\epsilon\frac{1+\epsilon}{q^{*}}n_{\text{min}}+n_{\text{min}}(\epsilon+\frac{\epsilon}{q^{*}})+n_{\text{min}}(n_{\text{min}}\epsilon+\epsilon+1)(1+\frac{1}{q^{*}})\epsilon.$

Note that $\lim_{\epsilon\downarrow 0}g(\epsilon)=0$.

Now we apply the bounds in (C.39)(C.44)(C.45) to establish the weak
convergence claim regarding
$(S^{(n)}_{0},W^{(n)}_{0},\cdots,S^{(n)}_{K},W^{(n)}_{K})$. Fix some positive
integer $K$, some strictly positive real numbers $(s_{k})_{k=0}^{K}$, a
sequence $(w_{k})_{k=0}^{K}\in\big{(}G^{\text{large}}\big{)}^{K+1}$ with
$w_{k}=m_{i_{k}}$ for each $k$, and some $\epsilon>0$ such that
$\epsilon<\min_{k=0,1,\cdots,K}\\{s_{k}\\}$. On the one hand, the definition
of the CTMC $Y$ implies that

$\displaystyle\mathbb{P}\Big{(}S_{0}<t_{0},W_{0}=w_{0};\ S_{k}>s_{k}\
\text{and }W_{k}=w_{k}\ \forall k\in[K]\Big{)}$ $\displaystyle=$
$\displaystyle\mathbb{P}(\pi_{G}(m_{i})=w_{0})\prod_{k=1}^{K}\Big{(}S_{k}>s_{k}\
\text{and }W_{k}=w_{k}\ \Big{|}\ W_{k-1}=w_{k-1}\Big{)}$ $\displaystyle=$
$\displaystyle\Big{(}\mathbbm{1}\\{m_{i}\in G^{\text{large}},\
i_{0}=i\\}+\mathbbm{1}\\{m_{i}\in
G^{\text{small}}\\}p_{i_{0},i_{1}}\Big{)}\cdot\prod_{k=1}^{K}\exp(-q_{i_{k-1}}s_{k})\frac{q_{i_{k-1},i_{k}}}{q_{i_{k-1}}}.$

On the other hand, using (C.39)(C.44)(C.45), we know that for all $n$
sufficiently large,

$\displaystyle\mathbb{P}_{x}\Big{(}S^{(n)}_{0}<s_{0},W^{(n)}_{0}=w_{0};\
S^{(n)}_{k}>s_{k}\ \text{and }W^{(n)}_{k}=w_{k}\ \forall k\in[K]\Big{)}$
$\displaystyle\geq$ $\displaystyle(1-\epsilon)\Big{(}\mathbbm{1}\\{m_{i}\in
G^{\text{large}},\ i_{0}=i\\}+\mathbbm{1}\\{m_{i}\in
G^{\text{small}}\\}(p_{i_{0},i_{1}}-\epsilon)\Big{)}\cdot\prod_{k=1}^{K}\Big{(}-g(\epsilon)+\exp(-(1+\epsilon)q_{i_{k-1}}s_{k})\frac{q_{i_{k-1},i_{k}}}{q_{i_{k-1}}}\Big{)}$

and

$\displaystyle\mathbb{P}_{x}\Big{(}S^{(n)}_{0}<s_{0},W^{(n)}_{0}=w_{0};\
S^{(n)}_{k}>s_{k}\ \text{and }W^{(n)}_{k}=w_{k}\ \forall k\in[K]\Big{)}$
$\displaystyle\leq$ $\displaystyle\Big{(}\mathbbm{1}\\{m_{i}\in
G^{\text{large}},\ i_{0}=i\\}+\mathbbm{1}\\{m_{i}\in
G^{\text{small}}\\}(p_{i_{0},i_{1}}+\epsilon)\Big{)}\cdot\prod_{k=1}^{K}\Big{(}g(\epsilon)+\exp(-(1-\epsilon)q_{i_{k-1}}s_{k})\frac{q_{i_{k-1},i_{k}}}{q_{i_{k-1}}}\Big{)}.$

Since $\epsilon>0$ can be arbitrarily small, we now obtain

$\displaystyle\lim_{n\rightarrow\infty}\mathbb{P}_{x}\Big{(}S^{(n)}_{0}<t_{0},W^{(n)}_{0}=w_{0};\
S^{(n)}_{k}>s_{k}\ \text{and }W^{(n)}_{k}=m_{k}\ \forall k\in[K]\Big{)}$
$\displaystyle=$ $\displaystyle\mathbb{P}\Big{(}S_{0}<s_{0},W_{0}=w_{0};\
S_{k}>s_{k}\ \text{and }W_{k}=w_{k}\ \forall k\in[K]\Big{)},$

and the arbitrariness of the integer $K$, the strictly positive real numbers
$(s_{k})_{k=0}^{K}$, and the sequence
$(w_{k})_{k=0}^{K}\in\big{(}G^{\text{large}}\big{)}^{K+1}$ allows us to
conclude the proof. ∎

To extend the result above to the case where the communication class $G$ is
transient, we revisit the definition of the $Y^{\dagger}$ in (43). Let
$\bar{G}=G^{\text{large}}\cup\\{\bm{\dagger}\\}$ and let $m_{0}=\bm{\dagger}$
(remember that all the local minimizers of $f$ on $[-L,L]$ are
$m_{1},\cdots,m_{\text{min}}$). Meanwhile, using $q_{i}$ and $q_{i,j}$ in
(37)(38), we can define

$\displaystyle q^{\dagger}_{i,j}=\begin{cases}q_{i,j}&\text{if }i\geq 1,\
j\geq 1\\\ \mathbbm{1}\\{j=0\\}&\text{if }i=0\\\
\sum_{j\in[n_{\text{min}}],m_{j}\notin G}q_{i,j}&\text{if }i\geq 1,\
j=0.\end{cases}$

and $q^{\dagger}_{0}=1,\ q^{\dagger}_{i}=q_{i}\ \forall i\geq 1.$ Next, fix
some $i$ with $m_{i}\in G$ and $x\in\Omega_{i}$. Define a sequence of random
variables $(S^{\dagger}_{k})_{k\geq 0},(W^{\dagger}_{k})_{k\geq 0}$ such that
$S^{\dagger}_{k}=0$ and
$W_{0}=\pi_{G}(m_{i}),W^{\dagger}_{0}=\bm{\dagger}\mathbbm{1}\\{W_{0}\notin
G^{\text{large}}\\}+W_{0}\mathbbm{1}\\{W_{0}\in G^{\text{large}}\\}$ (see the
definition of random mapping $\pi_{G}$ in (39)) and (for all $k\geq 0$ and
$i,j$ with $m_{j},m_{l}\in\bar{G}$)

$\displaystyle\mathbb{P}\Big{(}W^{\dagger}_{k+1}=m_{l},\ S^{\dagger}_{k+1}>t\
\Big{|}\ W^{\dagger}_{k}=m_{j},\ (W^{\dagger}_{l})_{l=0}^{k-1},\
(S^{\dagger}_{l})_{l=0}^{k}\Big{)}$ (C.46) $\displaystyle=$
$\displaystyle\mathbb{P}\Big{(}W^{\dagger}_{k+1}=m_{l},\ S^{\dagger}_{k+1}>t\
\Big{|}\
W^{\dagger}_{k}=m_{j}\Big{)}=\exp(-q^{\dagger}_{j}t)\frac{q^{\dagger}_{j,l}}{q^{\dagger}_{j}}\
\forall t>0$ (C.47)

Then it is easy to see that $Y^{\dagger}(\pi_{G}(m_{i}))$ defined in (43) is a
$\big{(}(S^{\dagger}_{k})_{k\geq 0},(W^{\dagger}_{k})_{k\geq 0}\big{)}$ jump
process. In particular, from at any state that is not $\bm{\dagger}$ (namely,
any $m_{j}$ with $m_{j}\in G^{\text{large}}$), the probability that
$Y^{\dagger}$ moves to $\bm{\dagger}$ in the next transition is equal to the
chance that, starting from the same state, $Y$ moves to a state that is not in
$G$. Once entering $m_{0}=\bm{\dagger}$, the process $Y^{\dagger}$ will only
make dummy jumps (with interarrival times being iid Exp(1)): indeed, we have
$q^{\dagger}_{0}=q^{\dagger}_{0,0}=1$ and $q^{\dagger}_{0,j}=0$ for any $j\geq
1$, implying that, given $W^{\dagger}_{k}=m_{0}=\bm{\dagger}$, we must have
$W^{\dagger}_{k+1}=m_{0}=\bm{\dagger}$. These dummy jumps ensure that
$Y^{\dagger}$ is stuck at the cemetery state $\bm{\dagger}$ after visiting it.

Similarly, we can characterize the jump times and locations of the jump
process $\hat{X}^{\dagger,*,\eta,\Delta}$ (for the definition, see (42)). When
there is no ambiguity about the sequences $(\eta_{n})_{n\geq
1},(\Delta_{n})_{n\geq 1}$, let
$\hat{X}^{\dagger,(n)}=\hat{X}^{\dagger,*,\eta_{n},\Delta_{n}}$ and
$X^{\dagger,(n)}=X^{*,\eta_{n},\Delta_{n}}$. Also, recall that $\tau_{G}$
defined in (12) is the step $n$ when $X^{\eta}_{n}$ exits the communication
class $G$. Now let $(E_{k})_{k\geq 0}$ be a sequence of iid Exp(1) random
variables that is also independent of the noises $(Z_{k})_{k\geq 1}$ (so they
are independent from the SGD iterates $X^{\eta}_{n}$). For all $n\geq 1,k\geq
0$, define (see (23)-(28) and (32) for definitions of the quantities involved)

$\displaystyle\widetilde{S}^{\dagger,(n)}_{k}$
$\displaystyle=\begin{cases}\sigma^{*}_{k}(\eta_{n},\Delta_{n})\wedge\textbf{T}^{*}(\tau_{G}(\eta_{n}),\eta_{n})-\tau^{*}_{k-1}(\eta_{n},\Delta_{n})&\text{if
}\tau^{*}_{k-1}(\eta_{n},\Delta_{n})<\textbf{T}^{*}(\tau_{G}(\eta_{n}),\eta_{n})\\\
0&\text{otherwise}\end{cases}$ $\displaystyle S^{\dagger,(n)}_{k}$
$\displaystyle=\begin{cases}\tau^{*}_{k}(\eta_{n},\Delta_{n})\wedge\textbf{T}^{*}(\tau_{G}(\eta_{n}),\eta_{n})-\tau^{*}_{k-1}(\eta_{n},\Delta_{n})&\text{if
}\tau^{*}_{k-1}(\eta_{n},\Delta_{n})<\textbf{T}^{*}(\tau_{G}(\eta_{n}),\eta_{n})\\\
E_{k}&\text{otherwise}\end{cases}$
$\displaystyle\widetilde{W}^{\dagger,(n)}_{k}$
$\displaystyle=\begin{cases}m_{\widetilde{I}^{G}_{k}(\eta_{n},\Delta_{n})}&\text{if
}\sigma^{*}_{k}(\eta_{n},\Delta_{n})<\textbf{T}^{*}(\tau_{G}(\eta_{n}),\eta_{n})\\\
\bm{\dagger}&\text{otherwise}\end{cases}$ $\displaystyle W^{\dagger,(n)}_{k}$
$\displaystyle=\begin{cases}m_{I^{G}_{k}(\eta_{n},\Delta_{n})}&\text{if
}\tau^{*}_{k}(\eta_{n},\Delta_{n})<\textbf{T}^{*}(\tau_{G}(\eta_{n}),\eta_{n})\\\
\bm{\dagger}&\text{otherwise}\end{cases}$

with the convention that $\tau^{*}_{-1}=0$. Note that
$\textbf{T}^{*}(\tau_{G}(\eta_{n}),\eta_{n})$ is the scaled timestamp for
$X^{(n)}=X^{*,\eta}$ corresponding to $\tau_{G}(\eta_{n})$, hence
$\textbf{T}^{*}(\tau_{G}(\eta_{n}),\eta_{n})=\min\\{t\geq
0:X^{(n)}\notin\bigcup_{j:\ m_{j}\in G}\Omega_{j}\\}$. One can see that
$\hat{X}^{\dagger,(n)}$ is a $\big{(}(S^{\dagger,(n)}_{k})_{k\geq
0},(W^{\dagger,(n)}_{k})_{k\geq 0}\big{)}$ jump process. The next lemma is
similar to Lemma C.9 and discusses the convergence of the jump times and
locations of $\hat{X}^{\dagger,(n)}$ on a communication class $G$ in the
transient case.

######  Lemma C.10.

Assume that the communication class $G$ is transient. Given any $m_{i}\in G$,
$x\in\Omega_{i}$, finitely many real numbers $(t_{l})_{l=1}^{k^{\prime}}$ such
that $0<t_{1}<t_{2}<\cdots<t_{k^{\prime}}$, and a sequence of strictly
positive real numbers $(\eta_{n})_{n\geq 1}$ with $\lim_{n\rightarrow
0}\eta_{n}=0$, there exists a sequence of strictly positive real numbers
$(\Delta_{n})_{n\geq 1}$ with $\lim_{n}\Delta_{n}=0$ such that

  * •

Under $\mathbb{P}_{x}$ (so $X^{\eta}_{0}=x$), as $n$ tends to $\infty$,

$\displaystyle(S^{\dagger,(n)}_{0},W^{\dagger,(n)}_{0},S^{\dagger,(n)}_{1},W^{\dagger,(n)}_{1},S^{\dagger,(n)}_{2},W^{\dagger,(n)}_{2},\cdots)\Rightarrow(S^{\dagger}_{0},W^{\dagger}_{0},S^{\dagger}_{1},W^{\dagger}_{1},S^{\dagger}_{2},W^{\dagger}_{2},\cdots)$
(C.48)

  * •

For any $l\in[k^{\prime}]$,

$\displaystyle\lim_{n\rightarrow\infty}\mathbb{P}_{x}\Big{(}X^{\dagger,(n)}_{t_{l}}\notin\bigcup_{j:\
m_{j}\in G^{\text{large}}}B(m_{j},\Delta_{n}),\
X^{\dagger,(n)}_{s}\in\bigcup_{j:\ m_{j}\in G}\Omega_{j}\ \forall
s\in[0,t_{l}]\Big{)}=0$ (C.49)

###### Proof.

Let

$\displaystyle\nu_{j,k}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\mu_{j}(E_{j,k})\
\forall j,k\geq 1,\ j\neq k$ $\displaystyle p_{j,\dagger}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\sum_{\widetilde{j}:\
m_{\widetilde{j}}\notin G}p_{j,\widetilde{j}}\ \ \ \forall m_{j}\in
G^{\text{small}}$ $\displaystyle q_{j,\dagger}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\sum_{k:m_{k}\notin
G}\nu_{j,k}+\sum_{k:\ m_{k}\in G^{\text{small}}}\nu_{j,k}p_{k,\dagger}\ \ \
\forall m_{j}\in G^{\text{large}}.$

In order to specify our choice of $(\Delta_{n})_{n\geq 1}$, we consider a
construction of sequences $(\bar{\bm{\Delta}}(j))_{j\geq
0},(\bar{\bm{\eta}}(j))_{j\geq 0}$ as follows. Fix some
$\theta\in(0,\alpha-1)/2)$. Let $\bar{\bm{\Delta}}(0)=\bar{\bm{\eta}}(0)=1$.
One can see the existence of some $(\bar{\bm{\Delta}}(j))_{j\geq
1},(\bar{\bm{\eta}}(j))_{j\geq 1}$ such that

  * •

$\bar{\bm{\Delta}}(j)\in\big{(}0,\bar{\bm{\Delta}}(j-1)/2\big{]},\
\bar{\bm{\eta}}(j)\in\big{(}0,\bar{\bm{\eta}}(j-1)/2\big{]}$ for all $j\geq
1$;

  * •

(Due to Lemma C.2) for any $j\geq 1$, $\eta\in(0,\bar{\bm{\eta}}(j)]$,
(remember that $x$ and $i$ are the fixed constants prescribed in the
description of the lemma)

$\displaystyle\mathbb{P}_{x}\Big{(}\sigma^{*}_{0}\big{(}\eta,\bar{\bm{\Delta}}(j)\big{)}<\eta^{\theta},\
\widetilde{I}^{G}_{0}\big{(}\eta,\bar{\bm{\Delta}}(j)\big{)}=i\Big{)}>1-\frac{1}{2^{j}}.$

For definitions of
$\sigma^{G}_{k},\tau^{G}_{k},I^{G}_{k},\widetilde{I}^{G}_{k}$, see (23)-(28).

  * •

(Due to Lemma C.6) for any $j\geq 1$, $\eta\in(0,\bar{\bm{\eta}}(j)]$,

$\displaystyle\bigg{|}\mathbb{P}_{x}\Big{(}\tau^{*}_{k}\big{(}\eta,\bar{\bm{\Delta}}(j)\big{)}-\sigma^{*}_{k}\big{(}\eta,\bar{\bm{\Delta}}(j)\big{)}<\eta^{\theta},\
I^{G}_{k}\big{(}\eta,\bar{\bm{\Delta}}(j)\big{)}=i_{2}\ \Big{|}\
\widetilde{I}^{G}_{k}\big{(}\eta,\bar{\bm{\Delta}}(j)\big{)}=i_{1}\Big{)}-p_{i_{1},i_{2}}\bigg{|}<1/2^{j}$

uniformly for all $k\geq 0$ and all $m_{i_{1}}\in
G^{\text{small}},m_{i_{2}}\notin G^{\text{small}}$. Also, by definition of
$\sigma^{*}$ and $\tau^{*}$, we must have

$\displaystyle\mathbb{P}_{x}\Big{(}\tau^{*}_{k}\big{(}\eta,\bar{\bm{\Delta}}(j)\big{)}-\sigma^{*}_{k}\big{(}\eta,\bar{\bm{\Delta}}(j)\big{)}=0,\
I^{G}_{k}\big{(}\eta,\bar{\bm{\Delta}}(j)\big{)}=i_{1}\ \Big{|}\
\widetilde{I}^{G}_{k}\big{(}\eta,\bar{\bm{\Delta}}(j)\big{)}=i_{1}\Big{)}=1$

for all $k\geq 0$ and $m_{i_{1}}\in G^{\text{large}}$.

  * •

(Due to Proposition B.24) for any $j\geq 1$, $\eta\in(0,\bar{\bm{\eta}}(j)]$,

$\displaystyle-\frac{1}{2^{j}}+\exp\big{(}-(1+\frac{1}{2^{j}})q_{i_{1}}u\big{)}\frac{\nu_{i_{1},i_{2}}-\frac{1}{2^{j}}}{q_{i_{1}}}$
$\displaystyle\leq$
$\displaystyle\mathbb{P}_{x}\Big{(}\sigma^{*}_{k+1}\big{(}\eta,\bar{\bm{\Delta}}(j)\big{)}-\tau^{*}_{k}\big{(}\eta,\bar{\bm{\Delta}}(j)\big{)}>u,\
\widetilde{I}^{G}_{k+1}=i_{2}\ \Big{|}\
I^{G}_{k}\big{(}\eta,\bar{\bm{\Delta}}(j)\big{)}=i_{1}\Big{)}$
$\displaystyle\leq$
$\displaystyle\frac{1}{2^{j}}+\exp\big{(}-(1-\frac{1}{2^{j}})q_{i_{1}}u\big{)}\frac{\nu_{i_{1},i_{2}}+\frac{1}{2^{j}}}{q_{i_{1}}}$

uniformly for all $k\geq 1$, all $u>1/2^{j}$, and all $m_{i_{1}}\in
G^{\text{large}},m_{i_{2}}\in G$.

  * •

(Due to Lemma C.7) for any $j\geq 1$, for any $j\geq 1$,
$\eta\in(0,\bar{\bm{\eta}}(j)]$,

$\displaystyle\mathbb{P}_{x}\Big{(}X^{(n)}_{t_{k}}\notin\bigcup_{j:\ m_{j}\in
G^{\text{large}}}B(m_{j},\bar{\bm{\Delta}}(j)),\ X^{(n)}_{s}\in\bigcup_{j:\
m_{j}\in G}\Omega_{j}\ \forall s\in[0,t_{k}]\Big{)}<1/2^{j}$ (C.50)

uniformly for all $k\in[k^{\prime}]$.

Fix such $(\bar{\bm{\Delta}}(j))_{j\geq 0},(\bar{\bm{\eta}}(j))_{j\geq 0}$.
Define a function $\textbf{J}(\cdot):\mathbb{N}\mapsto\mathbb{N}$ as

$\displaystyle\textbf{J}(n)=0\vee\max\\{j\geq 0:\
\bar{\bm{\eta}}(j)\geq\eta_{n}\\}$

with the convention that $\max\emptyset=-\infty$. Lastly, let

$\displaystyle\Delta_{n}=\bar{\bm{\Delta}}(\textbf{J}(n))\ \forall n\geq 1.$

Note that, due to $\lim_{n}\eta_{n}=0$, we have
$\lim_{n}\textbf{J}(n)=\infty$, hence $\lim_{n}\Delta_{n}=0$. Besides, since
$X^{\dagger,(n)}_{t}=X^{(n)}_{t}$ given $X^{(n)}_{s}\in\bigcup_{j:\ m_{j}\in
G}\Omega_{j}$ for all $s\in[0,t]$, by combining $\lim_{n}\textbf{J}(n)=\infty$
with (C.50) we obtain (C.49).

Now it remains to prove (C.48). To this end, it suffices to show that, for any
positive integer $K$, we have
$(S^{\dagger,(n)}_{0},W^{\dagger,(n)}_{0},\cdots,S^{\dagger,(n)}_{K},W^{\dagger,(n)}_{K})$
converges in distribution
$(S^{\dagger}_{0},W^{\dagger}_{0},\cdots,S^{\dagger}_{K},W^{\dagger}_{K})$ as
$n$ tends to infinity. In particular, due to introduction of the dummy jumps,
we know that for any $k$ with
$\tau^{*}_{k}(\eta_{n},\Delta_{n})\geq\tau_{G}(\eta_{n})$ (in other words,
$\hat{X}^{\dagger,(n)}$ has reached state $\bm{\dagger}$ within the first $k$
jumps) we have $S^{\dagger,(n)}_{k+1}\sim\text{Exp}(1)$ and
$W^{\dagger,(n)}_{k+1}\equiv\bm{\dagger}$. Similarly, for any $k$ with
$S^{\dagger}_{0}+\cdots+S^{\dagger}_{k}\leq\tau^{Y}_{G}$, we have
$S^{\dagger}_{k+1}\sim\text{Exp}(1)$ and
$W^{\dagger}_{k+1}\equiv\bm{\dagger}$. Therefore, it suffices to show that,
for any positive integer $K$, any series of strictly positive real numbers
$(s_{k})_{k=0}^{K}$, any sequence
$(w_{k})_{k=0}^{K}\in\big{(}\bar{G}\big{)}^{K+1}$ such that
$w_{j}\neq\bm{\dagger}$ for any $j<K$, indices $i_{k}$ such that
$w_{k}=m_{i_{k}}$ for each $k$, we have

$\displaystyle\lim_{n\rightarrow\infty}\mathbb{P}_{x}\Big{(}S^{\dagger,(n)}_{0}<t_{0},W^{\dagger,(n)}_{0}=w_{0};\
S^{\dagger,(n)}_{k}>s_{k}\ \text{and }W^{\dagger,(n)}_{k}=w_{k}\ \forall
k\in[K]\Big{)}$ $\displaystyle=$
$\displaystyle\mathbb{P}\Big{(}S^{\dagger}_{0}<s_{0},W^{\dagger}_{0}=w_{0};\
S^{\dagger}_{k}>s_{k}\ \text{and }W^{\dagger}_{k}=w_{k}\ \forall
k\in[K]\Big{)}$ (C.51)

Fix some $(s_{k})_{k=0}^{K}$,
$(w_{k})_{k=0}^{K}\in\big{(}\bar{G}\big{)}^{K+1}$, and indices
$(i_{k})_{k=1}^{K}$ satisfying the conditions above. Besides, arbitrarily
choose some $\epsilon>0$ so that $\epsilon<\min_{k=0,\cdots,K}s_{k}$. To
proceed, we start by translating the inequalities established above under the
new system of notations.

  * •

First of all, for all $n$ sufficiently large, (remember that $x$ and $i$ are
prescribed constants in the description of this lemma)

$\displaystyle\mathbb{P}_{x}\Big{(}\widetilde{S}^{\dagger,(n)}_{0}<\eta_{n}^{\theta},\
\widetilde{W}^{\dagger,(n)}_{0}=m_{i}\Big{)}>1-\epsilon.$ (C.52)

  * •

For all $k\geq 0$ and all $m_{i_{1}}\in G^{\text{small}},m_{i_{2}}\in
G^{\text{large}}$, it holds for all $n$ sufficiently large that

$\displaystyle\bigg{|}\mathbb{P}_{x}\Big{(}S^{\dagger,(n)}_{k}-\widetilde{S}^{\dagger,(n)}_{k}<\eta_{n}^{\theta},\
{W}^{\dagger,(n)}_{k}=m_{i_{2}}\ \Big{|}\
\widetilde{W}^{\dagger,(n)}_{k}=m_{i_{1}}\Big{)}-p_{i_{1},i_{2}}\bigg{|}<\epsilon.$
(C.53)

  * •

On the other hand, for all $k\geq 0$ and all $m_{i_{1}}\in G^{\text{small}}$,
it holds for all $n$ sufficiently large that

$\displaystyle\bigg{|}\mathbb{P}_{x}\Big{(}S^{\dagger,(n)}_{k}-\widetilde{S}^{\dagger,(n)}_{k}<\eta_{n}^{\theta},\
{W}^{\dagger,(n)}_{k}=\bm{\dagger}\ \Big{|}\
\widetilde{W}^{\dagger,(n)}_{k}=m_{i_{1}}\Big{)}-\sum_{i_{2}:\ m_{i_{2}}\notin
G}p_{i_{1},i_{2}}\bigg{|}$ $\displaystyle=$
$\displaystyle\bigg{|}\mathbb{P}_{x}\Big{(}S^{\dagger,(n)}_{k}-\widetilde{S}^{\dagger,(n)}_{k}<\eta_{n}^{\theta},\
{W}^{\dagger,(n)}_{k}=\bm{\dagger}\ \Big{|}\
\widetilde{W}^{\dagger,(n)}_{k}=m_{i_{1}}\Big{)}-p_{i_{1},\dagger}\bigg{|}<\epsilon.$
(C.54)

  * •

For all $k\geq 0$ and all $m_{i_{1}}\in G^{\text{large}}$, it holds for all
$n$ that

$\displaystyle\mathbb{P}_{x}\Big{(}S^{\dagger,(n)}_{k}-\widetilde{S}^{\dagger,(n)}_{k}=0,\
{W}^{\dagger,(n)}_{k}=m_{i_{1}}\ \Big{|}\
\widetilde{W}^{\dagger,(n)}_{k}=m_{i_{1}}\Big{)}=1.$ (C.55)

  * •

For all $k\geq 0$, all $m_{i_{1}}\in G^{\text{large}},m_{i_{2}}\in G$ and all
$u>\epsilon$, the following claim holds for all $n$ sufficiently large:

$\displaystyle-\epsilon+\exp\big{(}-(1+\epsilon)q_{i_{1}}u\big{)}\frac{\nu_{i_{1},i_{2}}-\epsilon}{q_{i_{1}}}$
$\displaystyle\leq$
$\displaystyle\mathbb{P}_{x}\Big{(}\widetilde{S}^{\dagger,(n)}_{k+1}-S^{\dagger,(n)}_{k}>u,\
\widetilde{W}^{\dagger,(n)}_{k+1}=m_{i_{2}}\ \Big{|}\
W^{\dagger,(n)}_{k}=m_{i_{1}}\Big{)}$ $\displaystyle\leq$
$\displaystyle\mathbb{P}_{x}\Big{(}\widetilde{S}^{\dagger,(n)}_{k+1}-S^{\dagger,(n)}_{k}>u-\eta_{n}^{\theta},\
\widetilde{W}^{\dagger,(n)}_{k+1}=m_{i_{2}}\ \Big{|}\
W^{\dagger,(n)}_{k}=m_{i_{1}}\Big{)}$ $\displaystyle\leq$
$\displaystyle\epsilon+\exp\big{(}-(1-\epsilon)q_{i_{1}}u\big{)}\frac{\nu_{i_{1},i_{2}}+\epsilon}{q_{i_{1}}}$
(C.56)

  * •

On the other hand, for all $k\geq 0$, all $m_{i_{1}}\in G^{\text{large}}$, the
following claim holds for all $n$ sufficiently large:

$\displaystyle-\epsilon+\exp\big{(}-(1+\epsilon)q_{i_{1}}u\big{)}\frac{-\epsilon+\sum_{i_{2}:\
m_{i_{2}}\notin G}\nu_{i_{1},i_{2}}}{q_{i_{1}}}$ $\displaystyle\leq$
$\displaystyle\mathbb{P}_{x}\Big{(}\widetilde{S}^{\dagger,(n)}_{k+1}-S^{\dagger,(n)}_{k}>u,\
\widetilde{W}^{\dagger,(n)}_{k+1}=\bm{\dagger}\ \Big{|}\
W^{\dagger,(n)}_{k}=m_{i_{1}}\Big{)}$ $\displaystyle\leq$
$\displaystyle\mathbb{P}_{x}\Big{(}\widetilde{S}^{\dagger,(n)}_{k+1}-S^{\dagger,(n)}_{k}>u-\eta_{n}^{\theta},\
\widetilde{W}^{\dagger,(n)}_{k+1}=\bm{\dagger}\ \Big{|}\
W^{\dagger,(n)}_{k}=m_{i_{1}}\Big{)}$ $\displaystyle\leq$
$\displaystyle\epsilon+\exp\big{(}-(1-\epsilon)q_{i_{1}}u\big{)}\frac{\epsilon+\sum_{i_{2}:\
m_{i_{2}}\notin G}\nu_{i_{1},i_{2}}}{q_{i_{1}}}$ (C.57)

  * •

Here is one implication of (C.53)(C.54). Since $|G|\leq n_{\text{min}}$, we
have (when $n$ is sufficiently large)

$\displaystyle\mathbb{P}_{x}\Big{(}S^{(n)}_{k}-\widetilde{S}^{(n)}_{k}\geq\eta_{n}^{\theta}\
\Big{|}\ \widetilde{W}^{(n)}_{k}=m_{i_{1}}\Big{)}<n_{\text{min}}\cdot\epsilon$
(C.58)

for all $k\geq 0$ and $m_{i_{1}}\in G^{\text{small}}$.

  * •

Note that for any $m_{i_{1}},m_{i_{2}}\in G^{\text{large}}$ and any $k\geq 0$

$\displaystyle\mathbb{P}_{x}\Big{(}S^{\dagger,(n)}_{k+1}-S^{\dagger,(n)}_{k}>u,\
W^{\dagger,(n)}_{k+1}=m_{i_{2}}\ \Big{|}\
W^{\dagger,(n)}_{k}=m_{i_{1}}\Big{)}$ $\displaystyle=$
$\displaystyle\mathbbm{1}\\{i_{2}\neq
i_{1}\\}\mathbb{P}_{x}\Big{(}\widetilde{S}^{\dagger,(n)}_{k+1}-S^{\dagger,(n)}_{k}>u,\
\widetilde{W}^{\dagger,(n)}_{k+1}=m_{i_{2}}\ \Big{|}\
W^{\dagger,(n)}_{k}=m_{i_{1}}\Big{)}$ $\displaystyle+$
$\displaystyle\sum_{i_{3}:\ m_{i_{3}}\in
G^{\text{small}}}\int_{s>0}\mathbb{P}_{x}\Big{(}S^{\dagger,(n)}_{k+1}-\widetilde{S}^{\dagger,(n)}_{k+1}\geq(u-s)\vee
0,\ \widetilde{W}^{\dagger,(n)}_{k+1}=m_{i_{2}}\ \Big{|}\
\widetilde{W}^{\dagger,(n)}_{k}=m_{i_{3}}\Big{)}$ $\displaystyle\ \ \ \ \ \ \
\ \ \ \ \
\cdot\mathbb{P}_{x}\Big{(}\widetilde{S}^{\dagger,(n)}_{k+1}-S^{\dagger,(n)}_{k}=ds,\
\widetilde{W}^{\dagger,(n)}_{k+1}=m_{i_{3}}\ \Big{|}\
W^{\dagger,(n)}_{k}=m_{i_{1}}\Big{)}.$

Fix some $i_{3}$ with $m_{i_{3}}\in G^{\text{small}}$. Due to (C.58)

$\displaystyle\int_{s\in(0,u-\eta^{\theta}_{n}]}\mathbb{P}_{x}\Big{(}S^{\dagger,(n)}_{k+1}-\widetilde{S}^{\dagger,(n)}_{k+1}\geq
u-s,\ \widetilde{W}^{\dagger,(n)}_{k+1}=m_{i_{2}}\ \Big{|}\
\widetilde{W}^{\dagger,(n)}_{k}=m_{i_{3}}\Big{)}$ $\displaystyle\ \ \ \ \ \ \
\ \ \
\cdot\mathbb{P}_{x}\Big{(}\widetilde{S}^{\dagger,(n)}_{k+1}-S^{\dagger,(n)}_{k}=ds,\
\widetilde{W}^{\dagger,(n)}_{k+1}=m_{i_{3}}\ \Big{|}\
W^{\dagger,(n)}_{k}=m_{i_{1}}\Big{)}$ $\displaystyle\leq$ $\displaystyle
n_{\text{min}}\epsilon.$

Meanwhile, by considering the integral on $(u-\eta_{n}^{\theta},\infty)$, we
get

$\displaystyle\int_{s\in(u-\eta^{\theta}_{n},\infty)}\mathbb{P}_{x}\Big{(}S^{\dagger,(n)}_{k+1}-\widetilde{S}^{\dagger,(n)}_{k+1}\geq(u-s)\vee
0,\ \widetilde{W}^{\dagger,(n)}_{k+1}=m_{i_{2}}\ \Big{|}\
\widetilde{W}^{\dagger,(n)}_{k}=m_{i_{3}}\Big{)}$ $\displaystyle\ \ \ \ \ \ \
\ \ \
\cdot\mathbb{P}_{x}\Big{(}\widetilde{S}^{\dagger,(n)}_{k+1}-S^{\dagger,(n)}_{k}=ds,\
\widetilde{W}^{\dagger,(n)}_{k+1}=m_{i_{3}}\ \Big{|}\
W^{\dagger,(n)}_{k}=m_{i_{1}}\Big{)}$ $\displaystyle\geq$
$\displaystyle\int_{s\in(u,\infty)}\mathbb{P}_{x}\Big{(}\widetilde{W}^{\dagger,(n)}_{k+1}=m_{i_{2}}\
\Big{|}\
\widetilde{W}^{\dagger,(n)}_{k}=m_{i_{3}}\Big{)}\cdot\mathbb{P}_{x}\Big{(}\widetilde{S}^{\dagger,(n)}_{k+1}-S^{\dagger,(n)}_{k}=ds,\
\widetilde{W}^{\dagger,(n)}_{k+1}=m_{i_{3}}\ \Big{|}\
W^{\dagger,(n)}_{k}=m_{i_{1}}\Big{)}$ $\displaystyle\geq$
$\displaystyle(p_{i_{3},i_{2}}-\epsilon)\Big{(}-\epsilon+\exp\big{(}-(1+\epsilon)q_{i_{1}}u\big{)}\frac{\nu_{i_{1},i_{3}}-\epsilon}{q_{i_{1}}}\Big{)}$

due to (C.53) and (C.56). As for the upper bound,

$\displaystyle\int_{s\in(u-\eta^{\theta}_{n},\infty)}\mathbb{P}_{x}\Big{(}S^{\dagger,(n)}_{k+1}-\widetilde{S}^{\dagger,(n)}_{k+1}\geq(u-s)\vee
0,\ \widetilde{W}^{\dagger,(n)}_{k+1}=m_{i_{2}}\ \Big{|}\
\widetilde{W}^{\dagger,(n)}_{k}=m_{i_{3}}\Big{)}$ $\displaystyle\ \ \ \ \ \ \
\ \ \
\cdot\mathbb{P}_{x}\Big{(}\widetilde{S}^{\dagger,(n)}_{k+1}-S^{\dagger,(n)}_{k}=ds,\
\widetilde{W}^{\dagger,(n)}_{k+1}=m_{i_{3}}\ \Big{|}\
W^{\dagger,(n)}_{k}=m_{i_{1}}\Big{)}$ $\displaystyle\leq$
$\displaystyle(n_{\text{min}}\epsilon+p_{i_{3},i_{2}}+\epsilon)\Big{(}\epsilon+\exp\big{(}-(1-\epsilon)q_{i_{1}}u\big{)}\frac{\nu_{i_{1},i_{3}}+\epsilon}{q_{i_{1}}}\Big{)}$

due to (C.53), (C.56) and (C.58).

  * •

Therefore, for any $m_{i_{1}},m_{i_{2}}\in G^{\text{large}}$ and any $k\geq
0$,

$\displaystyle\mathbb{P}_{x}\Big{(}S^{\dagger,(n)}_{k+1}-S^{\dagger,(n)}_{k}>u,\
W^{\dagger,(n)}_{k+1}=m_{i_{2}}\ \Big{|}\
W^{\dagger,(n)}_{k}=m_{i_{1}}\Big{)}$ $\displaystyle\leq$ $\displaystyle
g(\epsilon)+\exp\big{(}-(1-\epsilon)q_{i_{1}}u\big{)}\frac{\mathbbm{1}\\{i_{2}\neq
i_{1}\\}\nu_{i_{1},i_{2}}+\sum_{i_{3}:\ m_{i_{3}}\in
G^{\text{small}}}\nu_{i_{1},i_{3}}p_{i_{3},i_{2}}}{q_{i_{1}}}$
$\displaystyle\leq$ $\displaystyle
g(\epsilon)+\exp\big{(}-(1-\epsilon)q_{i_{1}}u\big{)}\frac{q_{i_{1},i_{2}}}{q_{i_{1}}}$
(C.59)

and

$\displaystyle\mathbb{P}_{x}\Big{(}S^{\dagger,(n)}_{k+1}-S^{\dagger,(n)}_{k}>u,\
W^{\dagger,(n)}_{k+1}=m_{i_{2}}\ \Big{|}\
W^{\dagger,(n)}_{k}=m_{i_{1}}\Big{)}$ $\displaystyle\geq$
$\displaystyle-g(\epsilon)+\exp\big{(}-(1+\epsilon)q_{i_{1}}u\big{)}\frac{\mathbbm{1}\\{i_{2}\neq
i_{1}\\}\nu_{i_{1},i_{2}}+\sum_{i_{3}:\ m_{i_{3}}\in
G^{\text{small}}}\nu_{i_{1},i_{3}}p_{i_{3},i_{2}}}{q_{i_{1}}}$
$\displaystyle\geq$
$\displaystyle-g(\epsilon)+\exp\big{(}-(1+\epsilon)q_{i_{1}}u\big{)}\frac{q_{i_{1},i_{2}}}{q_{i_{1}}}$
(C.60)

where $q^{*}=\max_{i}q_{i}$ and

$\displaystyle
g(\epsilon)\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}2\epsilon+\frac{\epsilon}{q^{*}}+n_{\text{min}}(1+\epsilon)\epsilon+\epsilon\frac{1+\epsilon}{q^{*}}n_{\text{min}}+n_{\text{min}}(\epsilon+\frac{\epsilon}{q^{*}})+n_{\text{min}}(n_{\text{min}}\epsilon+\epsilon+1)(1+\frac{1}{q^{*}})\epsilon.$

Note that $\lim_{\epsilon\downarrow 0}g(\epsilon)=0$.

  * •

On the other hand, for the case where the marker process
$\hat{X}^{\dagger,(n)}$ jumps to the cemetery state $\bm{\dagger}$ from some
$m_{i_{1}}\in G^{\text{large}}$, note that

$\displaystyle\mathbb{P}_{x}\Big{(}S^{\dagger,(n)}_{k+1}-S^{\dagger,(n)}_{k}>u,\
W^{\dagger,(n)}_{k+1}=\bm{\dagger}\ \Big{|}\
W^{\dagger,(n)}_{k}=m_{i_{1}}\Big{)}$ $\displaystyle=$
$\displaystyle\mathbb{P}_{x}\Big{(}\widetilde{S}^{\dagger,(n)}_{k+1}-S^{\dagger,(n)}_{k}>u,\
\widetilde{W}^{\dagger,(n)}_{k+1}=\bm{\dagger}\ \Big{|}\
W^{\dagger,(n)}_{k}=m_{i_{1}}\Big{)}$ $\displaystyle+$
$\displaystyle\sum_{i_{3}:\ m_{i_{3}}\in
G^{\text{small}}}\int_{s>0}\mathbb{P}_{x}\Big{(}S^{\dagger,(n)}_{k+1}-\widetilde{S}^{\dagger,(n)}_{k+1}\geq(u-s)\vee
0,\ \widetilde{W}^{\dagger,(n)}_{k+1}=\bm{\dagger}\ \Big{|}\
\widetilde{W}^{\dagger,(n)}_{k}=m_{i_{3}}\Big{)}$ $\displaystyle\ \ \ \ \ \ \
\ \ \ \ \
\cdot\mathbb{P}_{x}\Big{(}\widetilde{S}^{\dagger,(n)}_{k+1}-S^{\dagger,(n)}_{k}=ds,\
\widetilde{W}^{\dagger,(n)}_{k+1}=m_{i_{3}}\ \Big{|}\
W^{\dagger,(n)}_{k}=m_{i_{1}}\Big{)}.$

Arguing similarly as we did above by considering the integral on
$[0,u-\eta^{\theta}_{n}]$ and $(u-\eta^{\theta}_{n},\infty)$ separately, and
using (C.54) and (C.57), we then get (for all $n$ sufficiently large)

$\displaystyle\mathbb{P}_{x}\Big{(}S^{\dagger,(n)}_{k+1}-S^{\dagger,(n)}_{k}>u,\
W^{\dagger,(n)}_{k+1}=\bm{\dagger}\ \Big{|}\
W^{\dagger,(n)}_{k}=m_{i_{1}}\Big{)}$ $\displaystyle\leq$ $\displaystyle
g(\epsilon)+\exp\big{(}-(1-\epsilon)q_{i_{1}}u\big{)}\frac{\sum_{i_{2}:m_{i_{2}}\notin
G}\nu_{i_{1},i_{2}}+\sum_{i_{2}:m_{i_{2}}\in
G^{\text{small}}}\nu_{i_{1},i_{2}}p_{i_{2},\dagger}}{q_{i_{1}}}$
$\displaystyle=$ $\displaystyle
g(\epsilon)+\exp\big{(}-(1-\epsilon)q_{i_{1}}u\big{)}\frac{q_{i_{1},\dagger}}{q_{i_{1}}}$
(C.61)

and

$\displaystyle\mathbb{P}_{x}\Big{(}S^{\dagger,(n)}_{k+1}-S^{\dagger,(n)}_{k}>u,\
W^{\dagger,(n)}_{k+1}=\bm{\dagger}\ \Big{|}\
W^{\dagger,(n)}_{k}=m_{i_{1}}\Big{)}$ $\displaystyle\geq$
$\displaystyle-g(\epsilon)+\exp\big{(}-(1+\epsilon)q_{i_{1}}u\big{)}\frac{\sum_{i_{2}:m_{i_{2}}\notin
G}\nu_{i_{1},i_{2}}+\sum_{i_{2}:m_{i_{2}}\in
G^{\text{small}}}\nu_{i_{1},i_{2}}p_{i_{2},\dagger}}{q_{i_{1}}}$
$\displaystyle=$
$\displaystyle-g(\epsilon)+\exp\big{(}-(1+\epsilon)q_{i_{1}}u\big{)}\frac{q_{i_{1},\dagger}}{q_{i_{1}}}$
(C.62)

For simplicity of presentation, we also let $q_{j,0}=q_{j,\dagger}$ and
$p_{j,0}=p_{j,\dagger}$. First of all, remember that we have fixed some series
of strictly positive real numbers $(s_{k})_{k=0}^{K}$, some sequence
$(w_{k})_{k=0}^{K}\in\big{(}\bar{G}\big{)}^{K+1}$ such that
$w_{j}\neq\bm{\dagger}$ for any $j<K$, and indices $i_{k}$ such that
$w_{k}=m_{i_{k}}$ for each $k$. The definition of the continuous-time Markov
chain $Y^{\dagger}$ implies that

$\displaystyle\mathbb{P}\Big{(}S_{0}<t_{0},W_{0}=w_{0};\ S_{k}>s_{k}\
\text{and }W_{k}=w_{k}\ \forall k\in[K]\Big{)}$ $\displaystyle=$
$\displaystyle\mathbb{P}(\pi_{G}(m_{i})=w_{0})\prod_{k=1}^{K}\Big{(}S_{k}>s_{k}\
\text{and }W_{k}=m_{k}\ \Big{|}\ W_{k-1}=w_{k-1}\Big{)}$ $\displaystyle=$
$\displaystyle\Big{(}\mathbbm{1}\\{m_{i}\in G^{\text{large}},\
i_{0}=i\\}+\mathbbm{1}\\{m_{i}\in
G^{\text{small}}\\}p_{i_{0},i_{1}}\Big{)}\cdot\prod_{k=1}^{K}\exp(-q_{i_{k-1}}s_{k})\frac{q_{i_{k-1},i_{k}}}{q_{i_{k-1}}}.$

On the other hand, using (C.59)-(C.62), we know that for all $n$ sufficiently
large,

$\displaystyle\mathbb{P}_{x}\Big{(}S^{(n)}_{0}<s_{0},W^{(n)}_{0}=w_{0};\
S^{(n)}_{k}>s_{k}\ \text{and }W^{(n)}_{k}=w_{k}\ \forall k\in[K]\Big{)}$
$\displaystyle\geq$ $\displaystyle(1-\epsilon)\Big{(}\mathbbm{1}\\{m_{i}\in
G^{\text{large}},\ i_{0}=i\\}+\mathbbm{1}\\{m_{i}\in
G^{\text{small}}\\}(p_{i_{0},i_{1}}-\epsilon)\Big{)}\cdot\prod_{k=1}^{K}\Big{(}-g(\epsilon)+\exp(-(1+\epsilon)q_{i_{k-1}}s_{k})\frac{q_{i_{k-1},i_{k}}}{q_{i_{k-1}}}\Big{)}$

and

$\displaystyle\mathbb{P}_{x}\Big{(}S^{(n)}_{0}<s_{0},W^{(n)}_{0}=w_{0};\
S^{(n)}_{k}>s_{k}\ \text{and }W^{(n)}_{k}=m_{k}\ \forall k\in[K]\Big{)}$
$\displaystyle\leq$ $\displaystyle\Big{(}\mathbbm{1}\\{m_{i}\in
G^{\text{large}},\ i_{0}=i\\}+\mathbbm{1}\\{m_{i}\in
G^{\text{small}}\\}(p_{i_{0},i_{1}}+\epsilon)\Big{)}\cdot\prod_{k=1}^{K}\Big{(}g(\epsilon)+\exp(-(1-\epsilon)q_{i_{k-1}}s_{k})\frac{q_{i_{k-1},i_{k}}}{q_{i_{k-1}}}\Big{)}.$

The arbitrariness of $\epsilon>0$ then allows us to establish (C.51) and
conclude the proof. ∎

Now we are ready to prove Lemma 10 and Lemma 11.

###### Proof of Lemma 10. .

From Lemma C.9, one can see the existence of some $(\Delta_{n})_{n\geq 1}$
with $\lim_{n}\Delta_{n}=0$ such that (C.32)-(C.35) hold. For simplicity of
notations, we let
$\hat{X}^{(n)}=\hat{X}^{*,\eta_{n},\Delta_{n}},X^{(n)}=X^{*,\eta_{n}}$, and
let $\bar{t}=t_{k^{\prime}}$

Combine (C.32) with Lemma C.8, and we immediately get (40). In order to prove
(41), it suffices to show that for any $\epsilon>0$,

$\displaystyle\limsup_{n}\mathbb{P}_{x}\Big{(}X^{(n)}_{t_{k}}\notin\bigcup_{j:\
m_{j}\in G^{\text{large}}}B(m_{j},\Delta_{n})\Big{)}\leq 4\epsilon\ \forall
k\in[k^{\prime}].$

Fix $\epsilon>0$, and observe following bound by decomposing the events

$\displaystyle\mathbb{P}_{x}\Big{(}X^{(n)}_{t_{k}}\notin\bigcup_{j:\ m_{j}\in
G^{\text{large}}}B(m_{j},\Delta_{n})\Big{)}$ $\displaystyle\leq$
$\displaystyle\mathbb{P}_{x}\Big{(}X^{(n)}_{t_{k}}\notin\bigcup_{j:\ m_{j}\in
G^{\text{large}}}B(m_{j},\Delta_{n}),\ X^{(n)}_{t}\in\bigcup_{j:\ m_{j}\in
G}\Omega_{j}\ \forall t\in[0,\bar{t}]\Big{)}$ $\displaystyle+$
$\displaystyle\mathbb{P}_{x}\Big{(}\exists t\in[0,\bar{t}]\ \text{such that
}X^{(n)}_{t}\notin\bigcup_{j:\ m_{j}\in G}\Omega_{j}\Big{)}$

Therefore, given (C.35), it suffices to prove

$\displaystyle\limsup_{n}\mathbb{P}_{x}\Big{(}\exists t\in[0,\bar{t}]\
\text{such that }X^{(n)}_{t}\notin\bigcup_{j:\ m_{j}\in
G}\Omega_{j}\Big{)}\leq 3\epsilon.$ (C.63)

Let

$\displaystyle T^{(n)}_{0}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\min\\{t\geq
0:\ X^{(n)}_{t}\in\bigcup_{j:m_{j}\in G}B(m_{j},2\Delta_{n})\\}$
$\displaystyle I^{(n)}_{0}$ $\displaystyle=j\iff X^{(n)}_{T^{(n)}_{0}}\in
B(m_{j},2\Delta_{n})$ $\displaystyle T^{(n)}_{k}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\min\\{t>T^{(n)}_{k-1}:\
X^{(n)}_{t}\in\bigcup_{j:m_{j}\in G,\ j\neq
I^{(n)}_{k-1}}B(m_{j},2\Delta_{n})\\}$ $\displaystyle I^{(n)}_{k}$
$\displaystyle=j\iff X^{(n)}_{T^{(n)}_{k}}\in B(m_{j},2\Delta_{n}).$

Building upon this definition, we define the following stopping times and
marks that only records the hitting time to minimizer in large attraction
fields in $G$ (with convention
$\textbf{k}^{(n),\text{large}}(-1)=-1,T^{(n),\text{large}}_{-1}=0,T^{(n)}_{-1}=0$)

$\displaystyle\textbf{k}^{(n),\text{large}}(k)$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\min\\{l>\textbf{k}^{(n),\text{large}}({k-1}):\
m_{I^{(n)}_{l}}\in G^{\text{large}}\\}$ $\displaystyle
T^{(n),\text{large}}_{k}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}T^{(n)}_{\textbf{k}^{(n),\text{large}}(k)},\
\ \
I^{(n),\text{large}}_{k}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}I^{(n)}_{\textbf{k}^{(n),\text{large}}(k)}.$

Now by defining

$\displaystyle J^{(n)}(t)$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\\#\\{k\geq
0:\ T^{(n)}_{k}\leq t\\},$ $\displaystyle J^{(n)}_{\text{large}}(t)$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\\#\\{k\geq
0:\ T^{(n),\text{large}}_{k}\leq t\\},$ $\displaystyle J^{(n)}(s,t)$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\\#\\{k\geq
0:\ T^{(n)}_{k}\in[s,t]\\},$

we use $J^{(n)}(t)$ to count the numbers of visits to local minima on $G$, and
$J^{(n)}_{\text{large}}(t)$ for the number of visits to minimizers in the
large attraction fields on $G$. $J^{(n)}(s,t)$ counts the indices $k$ such
that at $T^{(n)}_{k}$ a minimizer on $G$ is visited and regarding the hitting
time we have $T^{(n)}_{k}\in[s,t]$.

First of all, the weak convergence result in (C.32) implies the existence of
some positive integer $N(\epsilon)$ such that

$\displaystyle\limsup_{n}\mathbb{P}_{x}(J^{(n)}_{\text{large}}(\bar{t})>N(\epsilon))<\epsilon.$

Fix such $N(\epsilon)$. Next, from (C.34), we know the existence of some
integer $K(\epsilon)$ such that

$\displaystyle\limsup_{n}\sup_{k\geq
0}\mathbb{P}_{x}\Big{(}J^{(n)}\big{(}T^{(n),\text{large}}_{k-1},T^{(n),\text{large}}_{k}\big{)}>K(\epsilon)\Big{)}\leq\epsilon/N(\epsilon).$

Fix such $K(\epsilon)$ as well. From the results above, we know that for event

$\displaystyle
A_{1}(n)\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\\{J^{(n)}_{\text{large}}(\bar{t})\leq
N(\epsilon)\\}\cap\Big{\\{}J^{(n)}\big{(}T^{(n),\text{large}}_{k-1},T^{(n),\text{large}}_{k}\big{)}\leq
K(\epsilon)\ \forall k\in[N(\epsilon)]\Big{\\}},$

we have $\limsup_{n}\mathbb{P}_{x}\Big{(}\big{(}A_{1}(n)\big{)}^{c}\Big{)}\leq
2\epsilon$. On the other hand, on event $A_{1}(n)$, we must have

$\displaystyle J^{(n)}(\bar{t})\leq N(\epsilon)K(\epsilon).$

Meanwhile, it follows immediately from (C.33) that

$\displaystyle\limsup_{n}\sup_{k\geq 0}\mathbb{P}\Big{(}\exists
t\in[T^{(n)}_{k-1},T^{(n)}_{k}]\ \text{such that
}X^{(n)}_{t}\notin\bigcup_{j:\ m_{j}\in
G}\Omega_{j}\Big{)}<\frac{\epsilon}{N(\epsilon)K(\epsilon)},$

hence for event

$\displaystyle
A_{2}(n)\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\Big{\\{}X^{(n)}_{t}\in\bigcup_{j:\
m_{j}\in G}\Omega_{j}\ \forall
t\in[0,T^{(n)}_{N(\epsilon)K(\epsilon)}]\Big{\\}},$

we must have
$\limsup_{n}\mathbb{P}_{x}\Big{(}\big{(}A_{2}(n)\big{)}^{c}\Big{)}\leq\epsilon$.
To conclude the proof, note that

$\displaystyle A_{1}(n)\cap A_{2}(n)$
$\displaystyle\subseteq\\{J^{(n)}(\bar{t})\leq
N(\epsilon)K(\epsilon)\\}\cap\Big{\\{}X^{(n)}_{t}\in\bigcup_{j:\ m_{j}\in
G}\Omega_{j}\ \forall t\in[0,T^{(n)}_{N(\epsilon)K(\epsilon)}]\Big{\\}}$
$\displaystyle=\\{T^{(n)}_{N(\epsilon)K(\epsilon)}\geq\bar{t}\\}\cap\Big{\\{}X^{(n)}_{t}\in\bigcup_{j:\
m_{j}\in G}\Omega_{j}\ \forall
t\in[0,T^{(n)}_{N(\epsilon)K(\epsilon)}]\Big{\\}}$
$\displaystyle\subseteq\Big{\\{}X^{(n)}_{t}\in\bigcup_{j:\ m_{j}\in
G}\Omega_{j}\ \forall t\in[0,\bar{t}]\Big{\\}}$

so we have established (C.63). ∎

###### Proof of Lemma 11. .

From Lemma C.10, one can see the existence of some $(\Delta_{n})_{n\geq 1}$
with $\lim_{n}\Delta_{n}=0$ such that (C.48) and (C.49) hold. For simplicity
of notations, we let
$\hat{X}^{\dagger,(n)}=\hat{X}^{\dagger,*,\eta_{n},\Delta_{n}},X^{\dagger,(n)}=X^{\dagger,*,\eta_{n}}$,
and let $\bar{t}=t_{k^{\prime}}$

Combine (C.48) with Lemma C.8, and we immediately get (44). In order to prove
(45), note that

$\displaystyle\Big{\\{}X^{\dagger,(n)}_{t_{k}}\notin\bigcup_{j:\ m_{j}\in
G^{\text{large}}}B(m_{j},\Delta_{n})\text{ and
}X^{\dagger,(n)}_{t_{k}}\neq\bm{\dagger}\Big{\\}}$ $\displaystyle=$
$\displaystyle\Big{\\{}X^{\dagger,(n)}_{t_{k}}\notin\bigcup_{j:\ m_{j}\in
G^{\text{large}}}B(m_{j},\Delta_{n})\text{ and
}X^{\dagger,(n)}_{s}\in\bigcup_{j:m_{j}\in G}\Omega_{j}\ \forall
s\in[0,t_{k}]\Big{\\}}$

so the conclusion of the proof follows directly from (C.49). ∎

##  Appendix D Proofs of Lemma B.1,B.2,B.3

###### Proof of Lemma B.1. .

For any $\epsilon>0$,

$\displaystyle\mathbb{P}\Big{(}U(\epsilon)>\frac{1}{b(\epsilon)}\Big{)}$
$\displaystyle=\Big{(}1-a(\epsilon)\Big{)}^{\lfloor 1/b(\epsilon)\rfloor}.$

By taking logarithm on both sides, we have

$\displaystyle\ln\mathbb{P}\Big{(}U(\epsilon)>\frac{1}{b(\epsilon)}\Big{)}$
$\displaystyle=\lfloor 1/b(\epsilon)\rfloor\ln\Big{(}1-a(\epsilon)\Big{)}$
$\displaystyle=\frac{\lfloor
1/b(\epsilon)\rfloor}{1/b(\epsilon)}\frac{\ln\Big{(}1-a(\epsilon)\Big{)}}{-a(\epsilon)}\frac{-a(\epsilon)}{b(\epsilon)}.$

Since $\lim_{x\rightarrow 0}\frac{\ln(1+x)}{x}=1$, we know that for $\epsilon$
sufficiently small, we will have

$\displaystyle-c\frac{a(\epsilon)}{b(\epsilon)}\leq\ln\mathbb{P}\Big{(}U(\epsilon)>\frac{1}{b(\epsilon)}\Big{)}\leq-\frac{a(\epsilon)}{c\cdot
b(\epsilon)}.$ (D.1)

By taking exponential on both sides, we conclude the proof. ∎

###### Proof of Lemma B.2. .

To begin with, for any $\epsilon>0$ we have

$\displaystyle\mathbb{P}\Big{(}U(\epsilon)\leq\frac{1}{b(\epsilon)}\Big{)}$
$\displaystyle=1-\mathbb{P}\Big{(}U(\epsilon)>\frac{1}{b(\epsilon)}\Big{)}.$

Using bound (D.1), we know that for $\epsilon$ sufficiently small,
$\mathbb{P}(U(\epsilon)>1/b(\epsilon))\geq\exp(-c\cdot
a(\epsilon)/b(\epsilon))$. The upper bound follows from the generic bound
$1-\exp(-x)\leq x,\ \forall x\in\mathbb{R}$ with $x=c\cdot
a(\epsilon)/b(\epsilon)$.

Now we move onto the lower bound. Again, from bound (D.1), we know that for
sufficiently small $\epsilon$, we will have

$\mathbb{P}\Big{(}U(\epsilon)\leq\frac{1}{b(\epsilon)}\Big{)}\geq
1-\exp(-\frac{1}{\sqrt{c}}\cdot\frac{a(\epsilon)}{b(\epsilon)}).$

Due to the assumption that $\lim_{\epsilon\downarrow
0}a(\epsilon)/b(\epsilon)=0$ and the fact that
$1-\exp(-x)\geq\frac{x}{\sqrt{c}}$ for $x>0$ sufficiently close to $0$, we
will have (for $\epsilon$ small enough)
$\mathbb{P}\Big{(}U(\epsilon)\leq\frac{1}{b(\epsilon)}\Big{)}\geq\frac{1}{c}\cdot\frac{a(\epsilon)}{b(\epsilon)}.$
∎

###### Proof of Lemma B.3. .

Let
$a_{k}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}x_{k}-\widetilde{x}_{k}$.
From the fact that $g\in\mathcal{C}^{2}$ and Taylor expansion of $g^{\prime}$,
one can easily see that

$\displaystyle a_{k}$
$\displaystyle=\eta\sum_{j=1}^{k}\Big{(}g^{\prime}(\widetilde{x}_{j-1})-g^{\prime}(x_{j-1})\Big{)}+\eta(z_{1}+\cdots+z_{k})+x-\widetilde{x};$
$\displaystyle\Rightarrow|a_{k}|$ $\displaystyle\leq\eta
C(|a_{0}|+\cdots|a_{k-1}|)+\widetilde{c}.$

The desired bound then follows immediately from Gronwall’s inequality (see
Theorem 68, Chapter V of [24], where we let function $\alpha(t)$ be
$\alpha(t)=|a_{\lfloor t\rfloor}|$). ∎

##  Appendix E Notations

Table LABEL:tableRefNotations lists the notations used in Appendix B.

Table E.1: Summary of notations frequently used in Appendix B $[k]$ |  $\\{1,2,\ldots,k\\}$
---|---
$\eta$ |  Learning rate (gradient descent step size)
$b$ |  Truncation threshold of stochastic gradient
$\epsilon$ |  An accuracy parameter; typically used to denote an $\epsilon-$neighborhood of $s_{i},m_{i}$
$\delta$ |  A threshold parameter used to define large noises
$\bar{\epsilon}$ |  A constant defined for (B.15)-(B.16). Since $\bar{\epsilon}<\epsilon_{0}$, in (B.1) the claim holds for $|x-y|<\bar{\epsilon}$. Note that the value of the constant $\bar{\epsilon}$ does not vary with our choice of $\eta,\epsilon,\delta$.
$M$ |  Upper bound of $|f^{\prime}|$ and $|f^{\prime\prime}|$ (B.3)
$L$ |  Radius of training domain (B.3)
$\Omega$ |  The open interval $(s_{-},s_{+})$; a simplified notation for $\Omega_{i}$
$\varphi$, $\varphi_{c}$ |  $\varphi_{c}(w)\triangleq\varphi(w,c)\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}(w\wedge c)\vee(-c)$ truncation operator at level $c>0$
$Z^{\leq\delta,\eta}_{n}$ |  $Z_{n}\mathbbm{1}\\{\eta|Z_{n}|\leq\delta\\}$ “small” noise (B.7)
$Z^{>\delta,\eta}_{n}$ |  $Z_{n}\mathbbm{1}\\{\eta|Z_{n}|>\delta\\}$ “large” noise (B.8)
$T^{\eta}_{j}(\delta)$ |  $\min\\{n>T^{\eta}_{j-1}(\delta):\ \eta|Z_{n}|>\delta\\}$ arrival time of $j$-th large noise (B.9)
$W^{\eta}_{j}(\delta)$ |  $Z_{T^{\eta}_{j}(\delta)}$ size of $j$-th large noise (B.10)
$X^{\eta}_{n}(x)$ |  $X^{\eta}_{n+1}(x)=\varphi_{L}\Big{(}X^{\eta}_{n}(x)-\varphi_{b}\big{(}\eta(f^{\prime}(X^{\eta}_{n}(x))-Z_{n+1})\big{)}\Big{)}$, $X^{\eta}_{0}(x)=x$ SGD
$\textbf{y}^{\eta}_{n}(x)$ |  $\textbf{y}_{n}^{\eta}(x)=\textbf{y}_{n-1}^{\eta}(x)-\eta f^{\prime}(\textbf{y}_{n-1}^{\eta}(x))$, $\textbf{y}_{0}^{\eta}(x)=x$ GD
${Y}^{\eta}_{n}(x)$ |  $\textbf{y}^{\eta}_{n}(x)$ perturbed by large noises $(\mathbf{T}^{\eta}(\delta),\mathbf{W}^{\eta}(\delta))$ GD + large jump
$\widetilde{\textbf{y}}^{\eta}_{n}(x;\textbf{t},\textbf{w})$ |  $\textbf{y}^{\eta}_{n}(x)$ perturbed by noise vector $(\textbf{t},\textbf{w})$ perturbed GD
$\textbf{x}^{\eta}(t,x)$ |  $d\textbf{x}^{\eta}(t;x)=-\eta f^{\prime}\Big{(}\textbf{x}^{\eta}(t;x)\Big{)}dt$, $\textbf{x}^{\eta}(0;x)=x$ ODE
$\textbf{x}(t,x)$ |  $\textbf{x}^{1}(t,x)$
$\widetilde{\textbf{x}}^{\eta}(t,x;\textbf{t},\textbf{w})$ |  $\textbf{x}^{\eta}(t,x)$ perturbed by noise vector $(\textbf{t},\textbf{w})$ perturbed ODE
$A(n,\eta,\epsilon,\delta)$ |  $\displaystyle\Big{\\{}\max_{k\in[n\wedge(T^{\eta}_{1}(\delta)-1)]}\eta|Z_{1}+\cdots+Z_{k}|\leq\epsilon\Big{\\}}.$ (B.28)
$r$ |  $r\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\min\\{-s_{-},s_{+}\\}$. Effective radius of the attraction field $\Omega$.
$l^{*}$ |  $l^{*}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}\lceil r/b\rceil$. The minimum number of jumps required to escape $\Omega$ when starting from its local minimum $m=0$.
$h(\textbf{w},\textbf{t})$ |  A mapping defined as $h(\textbf{w},\textbf{t})=\widetilde{\textbf{x}}(t_{l^{*}},0;\textbf{t},\textbf{w})$.
$\bar{t},\ \bar{\delta}$ |  Necessary conditions for $h(\textbf{w},\textbf{t})$ to be outside of $\Omega$ (B.21)-(B.22)
$\hat{t}(\epsilon)$ |  $\hat{t}(\epsilon)\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptscriptstyle\Delta}}}{}c_{1}\log(1/\epsilon).$ The quantity $\hat{t}(\epsilon)/\eta$ provides an upper bound for the time it takes $\textbf{x}^{\eta}$ to return to $2\epsilon-$neighborhood of local minimum $m=0$ when starting from somewhere $\epsilon-$away from $s_{-},s_{+}$. See (B.23).
$E(\epsilon)$ |  $\big{\\{}(\textbf{w},\textbf{t})\subseteq\mathbb{R}^{l^{*}}\times\mathbb{R}_{+}^{l^{*}-1}:h(\textbf{w},\textbf{t})\notin[(s_{-}-\epsilon)\vee(-L),(s_{+}+\epsilon)\wedge L]\big{\\}}$
$p(\epsilon,\delta,\eta)$ |  The probability that, for $\textbf{t}=\big{(}T^{\eta}_{j}(\delta)-1\big{)}_{j=1}^{l^{*}}$ and $\textbf{w}=\big{(}\eta W^{\eta}_{j}(\delta)\big{)}_{j=1}^{l^{*}}$, we have $(\textbf{w},\textbf{t})\in E(\epsilon)$ conditioning on $\\{T^{\eta}_{1}(\delta)=1\\}$. Intuitively speaking, it characterizes the probability that the first $l^{*}$ large noises alone can drive the ODE out of the attraction field. Defined in (B.53).
$\nu_{\alpha}$ |  The Borel measure on $\mathbb{R}$ with density ν_α(dx) = 1{x ¿ 0}αp+xα\+ 1 \+ 1{x ¡0}αp-—x—α\+ 1 where $p_{-},p_{+}$ are constants in Assumption 2 in the main paper.
$\mu$ |  The product measure $\mu=(\nu_{\alpha})^{l^{*}}\times(\textbf{Leb}_{+})^{l^{*}-1}.$
$\sigma(\eta)$ |  $\min\\{n\geq 0:X^{\eta}_{n}\notin\Omega\\}.$ first exit time
$H(x)$ |  $\mathbb{P}(|Z_{1}|>x)=x^{-\alpha}L(x)$
$T_{\text{return}}(\epsilon,\eta)$ |  $\min\\{n\geq 0:X^{\eta}_{n}(x)\in[-2\epsilon,2\epsilon]\\}$