\section{Theoretical results} \label{app:theory}

We include all theoretical results from the paper. Throughout this section, we only deal with the case that the underlying proposal distribution $q_{t}$ does not change with $t$. To deal with typical small adaptations, we believe that the following framework can be combined with, e.g., the approach of \citet{roberts2007coupling}, but this would result in a significantly longer paper and these adaptations are not central to our approach.

\subsection{General bounds on non-Markovian approximate MCMC algorithms}

Proceeding more formally, let $\{\hat{X}_t, \hat{K}_t, \mathcal{F}_t\}_{t \geq 0}$ be a triple satisfying:
\begin{enumerate}
    \item $\{\hat{X}_t\}_{t \geq 0}$ is a sequence of \textit{random variables} on $\mathbb{R}^{d}$;
    \item $\{\hat{K}_t\}_{t \geq 0}$ is a (typically random) sequence of \textit{transition kernels} on $\mathbb{R}^{d}$;
    \item $\{\mathcal{F}_t\}_{t \geq 0}$ is a \textit{filtration}, and $\{\hat{X}_t, \hat{K}_t\}_{t \geq 0}$ is \textit{adapted} to this filtration;
    \item the three agree in the sense that 
    \begin{equation} 
        \mathbb{P}[X_{s+1} \in A \vert \mathcal{F}_{s}] = \hat{K}_s(\hat{X}_s, A)
    \end{equation}
    for all $s \geq 0$ and all measurable $A$. Note that, in particular, both left- and right-hand sides are $\mathcal{F}_s$-measurable random variables in $[0, 1]$.
\end{enumerate}
In practice, $\mathcal{F}_{s}$ is generated by our sequence of approximations to the true log-target. We use the following quantitative assumptions:
\begin{assumption}
(Lyapunov inequality). There exists $V: \mathbb{R}^{d} \to [1, \infty)$ and constants $0 < \alpha \leq 1$ and $0 \leq \beta < \infty$ so that 
\begin{equation}
    (\hat{K}_s V)(\hat{X}_{s}) \leq (1-\alpha) V(\hat{X}_{s}) + \beta
\end{equation} 
and
\begin{equation}
    (KV)(x) \leq (1-\alpha) V(x) + \beta
\end{equation} 
for all $s \geq 0$. The second inequality should hold deterministically; note that this is an $\mathcal{F}_{s}$-measurable event.
\label{assumption:lyapunov-inequality}
\end{assumption}
\begin{assumption}
(Good approximation). Let Assumption \ref{assumption:lyapunov-inequality-simple} or \ref{assumption:lyapunov-inequality}  hold. There exists a monotonically decreasing function $\delta:[0, \infty) \to [0, 0.5)$ so that 
\begin{equation}
    \|K(\hat{X}_{s}, \cdot) - \hat{K}_s(\hat{X}_{s}, \cdot)\|_{TV} \leq \delta(s) V(x)
\end{equation}
for all $s \geq 0$ and $x \in \mathbb{R}^{d}$. Again, this inequality should hold deterministically, which is an $\mathcal{F}_{s}$-measurable event. For notational convenience, we define $\delta(s) = \delta(0)$ for all $s < 0$.
\label{assumption:good-approximation}
\end{assumption}

\subsubsection{Initial coupling bounds}

The following is our main technical lemma. It is \textit{not} monotone in the time $s$; this will be remedied in applications.
\begin{lemma}
 Let Assumptions \ref{assumption:geometric-ergodicity}, \ref{assumption:lyapunov-inequality}, and \ref{assumption:good-approximation} hold. There exists a constant $0 < C < \infty$ depending only on $\alpha$, $\beta$, $R$, and $\gamma$ so that for $x \in \mathbb{R}^{d}$ and triple $\{\hat{X}_t, \hat{K}_t, \mathcal{F}_t\}_{t \geq 0}$ started at $\hat{X}_0 = x$, we have 
 \begin{equation*}
\| \mathbb{P}[\hat{X}_s \in \cdot] - \pi(\cdot) \|_{TV} \leq \begin{cases}
1 & \mbox{if } s \leq C_0 \\
 C \delta(0) s & \mbox{if } s > C_0,
\end{cases}
 \end{equation*}
 where $C_0 = C \log{(\delta(0)^{-1}V(x))}$.
 \label{lem:approx-chain-bound}
\end{lemma}

\begin{proof}
Define the ``small set'' 
\begin{equation} \label{EqSmallSet}
    \mathcal{C} = \left\{y : V(y) \leq \frac{4 \beta}{\alpha}\right\}    
\end{equation}
and the associated hitting time 
\begin{equation} \label{EqSmallSetHitting}
    \tau_{\mathcal{C}} = \min{\{t : \hat{X}_t \in \mathcal{C}\}}.
\end{equation}
Denote by $T_b \geq 0$ a ``burn-in'' time whose value will be fixed toward the end of the proof. 

By the triangle inequality, for all measurable $A \subset \mathbb{R}^{d}$
\begin{eqnarray}
\vert \mathbb{P}[\hat{X}_s \in A] - \pi(A) \vert &\leq& \vert \mathbb{P}[\hat{X}_s \in A, \tau_{\mathcal{C}} \leq T_b] - \pi(A) \mathbb{P}[\tau_{\mathcal{C}} \leq T_b] \vert \nonumber  + \vert \mathbb{P}[\hat{X}_s \in A, \tau_{\mathcal{C}} > T_b] - \pi(A) \mathbb{P}[\tau_{\mathcal{C}} > T_b] \vert \nonumber \\
&\leq& \vert \mathbb{P}[\hat{X}_s \in A, \tau_{\mathcal{C}} \leq T_b] - \pi(A) \mathbb{P}[\tau_{\mathcal{C}} \leq T_b] \vert \nonumber  + \mathbb{P}[\tau_{\mathcal{C}} > T_b] \label{eq:chain-inequality}
\end{eqnarray}
To bound the first term, note that
\begin{eqnarray}
    \vert \mathbb{P}[\hat{X}_s \in A, \tau_{\mathcal{C}} \leq T_b] - \pi(A) \mathbb{P}[\tau_{\mathcal{C}} \leq T_b] \vert \nonumber  &\leq& \sup_{y \in \mathcal{C}, 0 \leq u \leq T_b}{\vert \mathbb{P}[\hat{X}_s\in A \vert \hat{X}_u = y, \tau_{\mathcal{C}}=u] - \pi(A) \vert} \nonumber \\
    &\leq& \sup_{y \in \mathcal{C}, 0 \leq u \leq T_b}{\vert \mathbb{P}[\hat{X}_s\in A \vert \hat{X}_u = y, \tau_{\mathcal{C}}=u] - K^{s-u-1}(y, A) \vert} \nonumber \\ && + \sup_{y \in \mathcal{C}, 0 \leq u \leq T_b}{\vert K^{s-u-1}(y, A) - \pi(A) \vert}.
    \label{eq:chain-inequality-first-term}
\end{eqnarray}
Assumption \ref{assumption:geometric-ergodicity} gives 
\begin{equation*}
    \sup_{y \in \mathcal{C}, 0 \leq u \leq T_b}{\left| K^{s-u-1}(y, A) - \pi(A)\right|} \leq R \gamma^{s-T_b-1}    
\end{equation*}
and Assumption \ref{assumption:good-approximation} gives 

\begin{equation*}
  \sup_{y \in \mathcal{C}, 0 \leq u \leq T_b}{\vert 
\mathbb{P}[\hat{X}_s\in A \vert \hat{X}_u = y, \tau_{\mathcal{C}}=u] - K^{s-u-1}(y, A) \vert} \leq \sup_{y \in \mathcal{C}, 0 \leq u \leq T_b}{\sum_{t=u}^{s-1} \delta(t) (K^{s-t-1} V)(y)}.
\end{equation*}

Furthermore,
\begin{equation*}
    \sup_{y \in \mathcal{C}, 0 \leq u \leq T_b}{\sum_{t=u}^{s-1} \delta(t) (K^{s-t-1} V)(y)} +  R \gamma^{s-T_b-1}  \leq \sup_{y \in \mathcal{C}}{\sum_{t=0}^{s-1} \delta(t) (K^{s-t-1} V)(y)} +  R \gamma^{s-T_b-1}.
\end{equation*}
Substituting this back into \eqref{eq:chain-inequality-first-term} and by Assumption \ref{assumption:lyapunov-inequality}, 
\begin{subequations}
\begin{eqnarray}
    \vert \mathbb{P}[\hat{X}_s \in A, \tau_{\mathcal{C}} \leq T_b] - \pi(A) \mathbb{P}[\tau_{\mathcal{C}} \leq T_b] \vert  &\leq& \sup_{y \in \mathcal{C}}{\sum_{t=0}^{s-1} \delta(t) ((1-\alpha)^{s-t-1} V(y) + \beta/\alpha)} +  R \gamma^{s-T_b-1} \\
    &\leq& \sum_{t=0}^{s-1} \delta(t) ((1-\alpha)^{s-t-1} 4 \beta/\alpha + \beta/\alpha) +  R \gamma^{s-T_b-1} \\
    &\leq& \delta(0) 5 s \beta /\alpha +  R \gamma^{s-T_b-1}.
\end{eqnarray}
\label{eq:chain-inequality-first-term-bound}
\end{subequations}

To bound the second term in \eqref{eq:chain-inequality}, recall from Assumption \ref{assumption:lyapunov-inequality} that 
\begin{eqnarray*}
    \mathbb{E}[V(\hat{X}_{t+1}) \mathbf{1}_{\tau_{\mathcal{C}} > t} \vert \mathcal{F}_t] &\leq& ((1-\alpha)V(\hat{X}_t) + \beta) \mathbf{1}_{V(\hat{X}_t)>4 \beta/\alpha} \\
    &\leq& \left(1-\frac{3\alpha}{4}\right)V(\hat{X}_t) + \left(\beta - \frac{\alpha}{4} V(\hat{X}_t)\right) \mathbf{1}_{V(\hat{X}_t)>4 \beta/\alpha} \\
    &\leq& \left(1-\frac{3\alpha}{4}\right)V(\hat{X}_t) + \left(\beta - \frac{\alpha}{4} \frac{4 \beta}{\alpha}\right) \mathbf{1}_{V(\hat{X}_t)>4 \beta/\alpha} \\
    &\leq& \left(1-\frac{3\alpha}{4}\right)V(\hat{X}_t)
\end{eqnarray*}
for all $t \geq 0$. Iterating, we find by induction on $t$ that 
\begin{equation*}
    \mathbb{E}[V(\hat{X}_{t}) \mathbf{1}_{\tau_{\mathcal{C}} > t}] \leq \left(1-\frac{3\alpha}{4}\right)^{t} V(\hat{X}_0) = \left(1-\frac{3\alpha}{4}\right)^{t} V(x).   
\end{equation*}
Thus, by Markov's inequality,
\begin{equation}
    \mathbb{P}[\tau_{\mathcal{C}}>T_b] = \mathbb{P}\left[V(\hat{X}_{\tau_{\mathcal{C}}}) \mathbf{1}_{\tau_{\mathcal{C}} > T_b}>\frac{4 \beta}{\alpha} \right] \leq \frac{\alpha}{4 \beta}\left(1-\frac{3\alpha}{4}\right)^{T_b} V(x).
    \label{eq:chain-inequality-second-term-bound}
\end{equation}
Combining \eqref{eq:chain-inequality-first-term-bound} and \eqref{eq:chain-inequality-second-term-bound}, we have shown that
\begin{equation}
\vert \mathbb{P}[\hat{X}_s \in A] - \pi(A) \vert \leq \delta(0) \frac{5 s \beta}{\alpha} +  R \gamma^{s-T_b-1} + \frac{\alpha}{4 \beta}\left(1-\frac{3\alpha}{4}\right)^{T_b} V(x).
\end{equation}
Finally, we can choose $T_b$. Set 
\begin{equation*}
    T(s) = \max{\{t : R \gamma^{s-t-1}, \frac{\alpha}{4\beta}\left(1-\frac{3\alpha}{4}\right)^{t} V(x) \leq \frac{1}{2}\delta(0)\}}    
\end{equation*}
and define $T_b = \lfloor T(s) \rfloor$ when $0 < T(s) < \infty$ and $T_b = 0$ otherwise. Define $S=\min{\{s : T(s) \in (0, \infty)\}}$. Noting that $S = \Theta(\log{(\delta(0)^{-1})}+\log{(V(x))})$ for fixed $\alpha$, $\beta$, $R$, and $\gamma$ completes the proof.
\begin{flushright}$\qed$\end{flushright}
\end{proof}

We strengthen Lemma \ref{lem:approx-chain-bound} by first observing that, if $\hat{X}_0$ satisfies $V(\hat{X}_0) \leq 4 \beta / \alpha$, then
\begin{equation}
    \mathbb{E}[V(\hat{X}_1)] \leq (1-\alpha) \mathbb{E}[ V(\hat{X}_0)]+ \beta \leq (1-\alpha) \frac{4 \beta}{\alpha} + \beta \leq \frac{4 \beta}{\alpha}.
\end{equation}
Thus, by induction, if $\mathbb{E}[V(\hat{X}_{0})] \leq 4 \beta / \alpha$, then $\mathbb{E}[V(\hat{X}_s)] \leq 4 \beta / \alpha$ for \textit{all} time $s \geq 0$. Using this (and possibly relabelling the starting time to the quantity denoted by $T_{0}(s)$), Lemma \ref{lem:approx-chain-bound} has the immediate slight strengthening:
\begin{lemma}
  Let Assumptions \ref{assumption:geometric-ergodicity}, \ref{assumption:lyapunov-inequality}, and \ref{assumption:good-approximation} hold. There exists a constant $0 < C < \infty$ depending only on $\alpha$, $\beta$, $R$, and $\gamma$ so that for all starting distributions $\mu$ on $\mathbb{R}^{d}$ with $\mu(V) \leq 4 \beta / \alpha$ and triple $\{\hat{X}_t, \hat{K}_t, \mathcal{F}_t\}_{t \geq 0}$ started at $\hat{X}_0 \sim \mu$, we have 
  \begin{equation*}
\| \mathbb{P}[\hat{X}_s \in \cdot] - \pi(\cdot) \|_{TV} \leq \begin{cases}
1, & s \leq C_0 \\
  C \delta( T_{0}(s) ) \log{(\delta(T_{0}(s))^{-1})}, & s > C_0,
\end{cases}
  \end{equation*}
where $C_0 = C \delta(0) \log{(\delta(0)^{-1})}$ and 
\begin{equation}
T_{0}(s) = s - C \delta(0) \log{(\delta(0)^{-1})}.
\label{EqT0Def}
\end{equation}
  \label{lem:approx-chain-bound-distribution}
\end{lemma}

\subsubsection{Application to bounds on mean-squared error}

Recall that $f : \mathbb{R}^{d} \to [-1,1]$ with $\pi(f) = 0$. We apply Lemma \ref{lem:approx-chain-bound-distribution} to obtain the following bound on the Monte Carlo bias:
\begin{lemma}
  (Bias estimate). Let Assumptions \ref{assumption:geometric-ergodicity}, \ref{assumption:lyapunov-inequality}, and \ref{assumption:good-approximation} hold. There exists a constant $0 < C < \infty$ depending only on $\alpha$, $\beta$, $R$, and $\gamma$ so that for all starting points $x \in \mathbb{R}^{d}$ with $V(x) \leq 4 \beta / \alpha$ and triple $\{\hat{X}_t, \hat{K}_t, \mathcal{F}_t\}_{t \geq 0}$ started at $\hat{X}_0 = x$ we have 
  \begin{equation*}
    \left| \mathbb{E}\left[ \frac{1}{T} \sum_{t=1}^{T} f(\hat{X}_t) \right] \right|  \ \leq \ \begin{cases}
    1, & T \leq C_0 \\
    \frac{C_0}{T} + \frac{C}{T} \displaystyle\sum_{s=C_0}^{T} \delta(T_{0}(s)) \log{(\delta(T_{0}(s))^{-1})} & T > C_0,
    \end{cases}
  \end{equation*}
where $C_0 = C \delta(0) \log{(\delta(0)^{-1})}$.
\label{lem:bias-estimate}
\end{lemma}
\begin{proof}
 In the notation of Lemma \ref{lem:approx-chain-bound-distribution}, we have for $T > C_0$ sufficiently large
\begin{eqnarray*} 
 \left|\mathbb{E}\left[ \frac{1}{T} \sum_{t=1}^{T} f(\hat{X}_t) \right] \right| & \leq &  \frac{1}{T} \sum_{t=1}^{C_0} |\mathbb{E}[f(\hat{X}_{t})]| + \frac{1}{T} \sum_{t=C_0}^{T} |\mathbb{E}[f(\hat{X}_{t})]| \\
&\leq& \frac{C_0}{T} + \frac{C}{T} \sum_{s=C_0}^{T} \delta(T_{0}(s)) \log(\delta(T_{0}(s))^{-1}). 
\end{eqnarray*}
\begin{flushright}$\qed$\end{flushright}
\end{proof}
We have a similar bound for the Monte Carlo variance: 
\begin{lemma}
  (Covariance estimate). Let Assumptions \ref{assumption:geometric-ergodicity}, \ref{assumption:lyapunov-inequality}, and \ref{assumption:good-approximation} hold. There exists a constant $0 < C < \infty$ depending only on $\alpha$, $\beta$, $R$, and $\gamma$ so that for all starting points $x \in \mathbb{R}^{d}$ with $V(x) \leq 4 \beta / \alpha$ and triple $\{\hat{X}_t, \hat{K}_t, \mathcal{F}_t\}_{t \geq 0}$ started at $\hat{X}_0 = x$ we have 
  \begin{equation*}
      \sqrt{\vert\mathbb{E}[f(\hat{X}_s) f(\hat{X}_t)] - \mathbb{E}[f(\hat{X}_s)] \mathbb{E}[f(\hat{X}_t)] \vert} \  \leq \ \begin{cases}
1, & m(s,t) \leq C_0 \\
  C \delta( T_{0} ) \log{(\delta(T_{0})^{-1})}, & m(s,t) > C_0,
\end{cases}
  \end{equation*}
where $m(s,t) = \min(s,t,|t-s|)$, $T_{0} = T_{0}(m(s,t))$ is as in \eqref{EqT0Def}, and $C_0 = C \delta(0) \log{(\delta(0)^{-1})}$ as before.
\label{lem:covariance-estimate}
\end{lemma}
\begin{proof}
 By the triangle inequality 
 \begin{equation*}
    \vert\mathbb{E}[f(\hat{X}_s) f(\hat{X}_t)] - \mathbb{E}[f(\hat{X}_s)] \mathbb{E}[f(\hat{X}_t)] \vert \leq \vert\mathbb{E}[f(\hat{X}_s) f(\hat{X}_t)] \vert + \vert \mathbb{E}[f(\hat{X}_s)] \mathbb{E}[f(\hat{X}_t)] \vert.
 \end{equation*}
 As above, applying Lemma \ref{lem:approx-chain-bound-distribution} completes the proof.
 \begin{flushright}$\qed$\end{flushright}
\end{proof}

The above bias and variance estimates immediate imply our main theorem on the total error of the Monte Carlo estimator: 

\begin{theorem} \label{thm_main_mce}
Let Assumptions \ref{assumption:geometric-ergodicity}, \ref{assumption:lyapunov-inequality}, and \ref{assumption:good-approximation} hold. There exists a constant $0 < C < \infty$ depending only on $\alpha$, $\beta$, $R$, and $\gamma$ so that for all starting points $x \in \mathbb{R}^{d}$ with $V(x) \leq 4 \beta / \alpha$ and triple $\{\hat{X}_t, \hat{K}_t, \mathcal{F}_t\}_{t \geq 0}$ started at $\hat{X}_0 = x$ we have 
\begin{equation*}
\mathbb{E}\left[ \left( \frac{1}{T} \sum_{t=1}^{T} f(\hat{X}_t) \right)^2 \right]  \leq \frac{2C_{0}}{T^{2}}\sum_{s=1}^{T} C(s) + \frac{3}{T} \sum_{s=1}^{T} C(s)^{2},
\end{equation*}
where $C(s) = C \delta(T_{0}(s)) \log(\delta(T_{0}(s))^{-1})$ and we write $C_{0} = C_{0}(0)$.
\label{thm:expected-error}
\end{theorem}
\begin{proof}
We calculate
\begin{eqnarray*}
\mathbb{E}\left[ \left( \frac{1}{T} \sum_{t=1}^{T} f(\hat{X}_t) \right)^2 \right]
&=& T^{-2}\left[\sum_{t=1}^{T} \mathbb{E}[f(\hat{X}_{t})^{2}] \ + \sum_{s,t \, : \, m(s,t) < C_{0}} \mathbb{E}[f(\hat{X}_{s}) f(\hat{X}_{t})]  \ + \sum_{s,t \, : \, m(s,t) \geq C_{0}} \mathbb{E}[f(\hat{X}_{s}) f(\hat{X}_{t})] \right] \\
&\leq& T^{-2} \left[\sum_{s=1}^{T} C_{0}(s) + C_{0} \sum_{s=1}^{T} C_{0}(s) + 3 T \sum_{s=1}^{T} C_{0}(s)^{2} \right] \\
&\leq& \frac{2C_{0}}{T^{2}}\sum_{s=1}^{T} C_{0}(s) + \frac{3}{T} \sum_{s=1}^{T} C_{0}(s)^{2}.
\end{eqnarray*}
\begin{flushright}$\qed$\end{flushright}
\end{proof}

\subsection{Inheriting Lyapunov conditions} \label{SubsecInheritLyap}

Observe that each step of the main ``for'' loop in Algorithm \ref{alg:la-mcmc} determines an entire transition kernel from \textit{any} starting point; denote the kernel in step $t$ by $\mathcal{K}_{t}$. Finally, let $\mathcal{F}_{t}$ be the associated filtration.

\begin{lemma} \label{LemmaLyapSimpleGen}
Let Assumptions \ref{assumption:lyapunov-inequality-simple} and \ref{assumption:good-appr} hold. Then in fact Assumption \ref{assumption:lyapunov-inequality} holds as well. 
\label{lem:lyapunov-correction}
\end{lemma}
\begin{proof}
Under Assumption \ref{assumption:good-appr}, all proposals that \textit{decrease} $V$ are \textit{more} likely to be accepted under $\hat{K}_{t}$ than under $K$, while all proposals that \textit{increase} $V$ are \textit{less} likely to be accepted under $\hat{K}_{t}$ than under $K$. Thus, for all $x$ and all $t$,
\begin{equation}
(\hat{K}_{t}V)(\hat{X}_{t}) \leq (KV)(\hat{X}_{t}) \leq (1 - \alpha) V(\hat{X}_{t}) + \beta,
\end{equation}
which completes the proof.
\begin{flushright}$\qed$\end{flushright}
\end{proof}

\subsection{Final estimates}

We combine the theoretical results in the previous sections to obtain a final estimate on the error of our algorithm. Continuing the notation as above, we have our main theoretical result: Theorem \ref{thm:convergence-rate}, whose proof we give here.

\begin{proof}
We set some notation. Define
\begin{equation}
    E(T) \equiv \mathbb{E}\left[ \left( \frac{1}{T} \sum_{t=1}^{T} f(\hat{X}_t) \right)^2 \right]. 
\end{equation}
Also define the ``burn-in" time $T_{b} = \log(T)^{2}$, and define the hitting time $\tau_{\mathcal{C}}$ as in Equation \eqref{EqSmallSetHitting}.


By Lemma \ref{LemmaLyapSimpleGen}, Assumption \ref{assumption:lyapunov-inequality} in fact holds. Note that our assumptions also immediately give Assumption \ref{assumption:good-approximation} with
\[
\delta(t) \leq 2 \gamma_{0} \sqrt{\frac{\tau_{0}}{t}}.
\]
Thus, applying Theorem \ref{thm_main_mce} in line 3 and then Assumption  \ref{assumption:lyapunov-inequality} and Markov's inequality in line 4, we have (in the notation of that theorem and assumption): 

\begin{align*}
E(T) &\leq \mathbb{E}\left[ \left( \frac{1}{T} \sum_{t=1}^{T_{b}} f(\hat{X}_t) \right)^2 \right] + \mathbb{E}\left[ \left( \frac{1}{T} \sum_{t=T_{b}+1}^{T} f(\hat{X}_t) \right)^2 \right] + 2 \mathbb{E}\left[ \frac{1}{T^{2}} \left( \sum_{t=1}^{T_{b}} f(\hat{X}_t) \right) \left( \sum_{t=T_{b}+1}^{T} f(\hat{X}_t) \right) \right]\\
&\leq \mathbb{E}\left[ \left( \frac{1}{T} \sum_{t=1}^{T_{b}} f(\hat{X}_t) \right)^2 \right] + \frac{T_{b}^{2}}{T^{2}} + \frac{2T_{b}}{T} \\
&\leq \frac{2C_{0}}{T^{2}}\sum_{s=1}^{T} C_{0}(s) + \frac{3}{T} \sum_{s=1}^{T} C_{0}(s)^{2} + \mathbb{P}[\tau_{\mathcal{C}} > T_{b}] + \frac{T_{b}^{2}}{T^{2}} + \frac{2T_{b}}{T} \\
&\leq \frac{2C_{0}}{T^{2}}\sum_{s=1}^{T} C_{0}(s) + \frac{3}{T} \sum_{s=1}^{T} C_{0}(s)^{2} + \frac{\alpha}{4 \beta} (1-\alpha)^{T_{b}} V(x) + \frac{T_{b}^{2}}{T^{2}} + \frac{2T_{b}}{T} \\
&=O\left ( \frac{1}{T^{2}} \sum_{s=1}^{T} \sqrt{\frac{\tau_{0}}{s}} \log\left (\sqrt{\frac{\tau_{0}}{s}} \right )  + \frac{1}{T} \sum_{s=1}^{T}\frac{\tau_{0}}{s} \log\left (\sqrt{\frac{\tau_{0}}{s}}\right )^{2} + \frac{\log(T)^{2}}{T} \right )\\
&= O \left ( \frac{\log(T)^{3}}{T} \right ).
\end{align*}
\begin{flushright}$\qed$\end{flushright}
\end{proof}
{"config": "arxiv", "file": "2006.00032/theory_filtration.tex"}