# Finite Sample Complexity of Sequential Monte Carlo Estimators on Multimodal
Target Distributions

Joseph<EMAIL_ADDRESS>[ Scott C.
<EMAIL_ADDRESS>[ Department of
Statistical Science, Duke University presep=, ]e1  Department of Statistical
Science, Duke University presep=, ]e2

###### Abstract

We prove finite sample complexities for sequential Monte Carlo (SMC)
algorithms which require only local mixing times of the associated Markov
kernels. Our bounds are particularly useful when the target distribution is
multimodal and global mixing of the Markov kernel is slow; in such cases our
approach establishes benefits of SMC over the corresponding Markov chain Monte
Carlo (MCMC) estimator. The lack of global mixing is addressed by sequentially
controlling the bias introduced by SMC resampling procedures. We apply these
results to obtain complexity bounds for approximating expectations under
mixtures of log-concave distributions, and show that SMC provides a fully
polynomial time randomized approximation scheme for some difficult multimodal
problems where the corresponding Markov chain sampler is exponentially slow.
Finally, we compare the bounds obtained by our approach to existing bounds for
tempered Markov chains on the same problems.

65C05,

60J22,

65C40,

Sequential Monte Carlo,

Multimodal distributions,

Finite sample bounds,

###### keywords:

[class=MSC]

###### keywords:

and

##  1 Introduction

Approximating integrals with respect to a complicated, high-dimensional
probability distribution $\pi$ is an important problem spanning multiple
disciplines, such as Bayesian statistical inference, machine learning,
statistical physics, and theoretical computer science [13, 17]. Sequential
Monte Carlo (SMC) methods are a large class of stochastic approximation
algorithms designed to solve these problems by combining Markov chain Monte
Carlo (MCMC) methods and resampling strategies to sequentially sample from a
series of probability distributions. Some examples of SMC algorithms include
population Monte Carlo methods [2], annealed importance sampling [27],
sequential particle filters [3], and population annealing [40], among many
others [15]. Closely related - but purely MCMC - methods include parallel
tempering (PT) [14] and simulated tempering (ST) [23], which have been
referred to as population-based MCMC methods [15].

An SMC sampler is generally constructed as follows. The target distribution
$\pi$ is embedded in a sequence of distributions
$\mu_{0},\ldots,\mu_{V-1},\mu_{V}=\pi$ chosen such that $\mu_{0}$ is easy to
sample from and $\mu_{v-1}$ is ‘close’ to $\mu_{v}$ for $v=1,\ldots,V$. Random
variables (called particles) are initially sampled from $\mu_{0}$ and are
propagated through the sequence of distributions sequentially via a
combination of time-inhomogeneous MCMC and resampling moves until step $V$,
where the resulting particles can be used to approximate expectations under
$\pi$. For a comparison of various resampling strategies, see [6]. For a
discussion of different Markov kernels used for the MCMC (mutation) step, see
[5]. For adaptive strategies, see [1] and [12]. An explicit statement of the
algorithm considered in this paper is given in Section 2.1.

Two properties of SMC samplers make them particularly attractive to
practitioners. First, they can be parallelized easily, improving their
scalability to high-dimensional problems [8]. Second, SMC samplers are
believed to perform well when $\pi$ has multiple, well-separated modes. In
these situations, standard MCMC methods such as random walk Metropolis [26],
Hamiltonian Monte Carlo [28] and Gibbs samplers, often exhibit metastable
behavior, leading to slow mixing and poor approximation performance (see e.g.
[22]). SMC samplers are frequently applied to such multimodal targets across
different disciplines, see e.g. [8, 32, 37] for applications to Bayesian
statistics and [30, 39, 40] for applications to spin models in statistical
physics. The performance of SMC on multimodal problems has also been tested
via simulation studies on various model problems in [15, 31, 35]. See also
[38] for simulation studies comparing the performance of SMC methods to PT and
ST algorithms on the Potts model.

However, theoretical results in support of these purported benefits of SMC
over MCMC are limited. For one thing, such comparisons require quantitative
analysis of the number of particles or steps required by each algorithm on a
given problem. But while the asymptotic properties of SMC samplers have been
explored extensively in the literature (for example, [4] establishes a central
limit theorem under various resampling strategies, [29] proves a central limit
theorem for SMC methods using adaptive schemes, [7] proves a law of large
numbers, and [30] bound the asymptotic variance of SMC for multimodal
problems), rigorous results on finite-sample performance are much more
limited. Results for finite particle sets have been obtained by use of
Feynman-Kac formulations [41, 33, 34, 10, 11]; however, these bounds typically
involve expectations of the corresponding Feynman-Kac propagators, which are
generally not available explicitly, and assume mixing conditions on the
associated MCMC kernels which are difficult to verify on general state spaces.
These factors make it difficult to determine the dependence of SMC algorithms
on key quantities of interest such as the problem dimension. More recently,
[24] established finite sample bounds using a coupling construction. However,
their results depend on the global mixing rates of the mutation kernels, and
problems where these are controllable (e.g when polynomial rather than
exponential in problem size) are likely to be precisely those cases where MCMC
performs well without SMC.

In this paper we establish rigorous conditions guaranteeing the performance of
SMC samplers on multimodal target distributions by proving upper bounds on the
computational complexity. These results are obtained by establishing upper
bounds on the number of particles and MCMC steps needed to closely approximate
expectations under the target distribution with high probability. Our approach
builds on that of [24], but here we emphasize settings where global mixing may
be slow, as in multimodal situations, but where the kernel can be assumed to
mix locally. In particular, our approach assumes particles are only mutated
through restricted Markov kernels, corresponding to an arbitrary partition of
the state space. This ‘local mixing’ approach is similar to [34, 30], but here
we use this approach to obtain finite sample bounds rather than asymptotic
ones. We show that when SMC accurately approximates ‘local’ expectations (i.e.
expectations restricted to each partition element), global expectations can
also be approximated accurately. This approach also calls to mind the previous
mixing time analyses of the PT and ST algorithms in [42] (see also [16]), who
used the state space decomposition approach of [20]. We apply our bounds to
mixtures of log-concave distributions and the mean field Ising model. In
addition, we use our bounds to provide a rigorous comparison of the SMC, PT,
and ST algorithms.

While our approach builds on the coupling argument of [24], the inability to
rely on global mixing substantially complicates the analysis. Unlike in [24],
particles can no longer be coupled to a set of exact i.i.d. random variates,
as the bias introduced by resampling is no longer ‘corrected’ automatically by
a globally mixing kernel, and instead must be controlled directly.
Consequently our analysis highlights the benefits obtained from the resampling
step, which indeed is crucial to the success of the algorithm when the
mutation kernel cannot be assumed to mix globally at each step.

This paper is organized as follows. Section 2 establishes notation, formalizes
the SMC algorithm we are considering, and outlines our proof approach. Section
4 contains our main theorem and supporting results. Section 5, applies these
results to obtain bounds for mixtures of log-concave distributions and the
mean field Ising model. Section 6 compares our bounds to those obtained by
[42, 16] for the parallel and simulated tempering algorithms. Section 7,
concludes with a discussion of future directions.

##  2 Problem Setup

Let $\pi$ be a target distribution defined on a state space $\mathcal{X}$ with
corresponding $\sigma$-field $\mathcal{B}$ and dominating measure $\rho$. In a
slight abuse of notation we use the same letter to denote both the
distribution and its corresponding density (e.g. the density of $\pi$ is
$\pi(x)$). Let $\mathcal{A}=\\{A_{j}:j=1,\ldots,p\\}$ be a partition of
$\mathcal{X}$. Typically $\mathcal{A}$ will represent a partition of
$\mathcal{X}$ into local modes of $\pi$, although our results apply for any
partition. While $\mathcal{A}$ is usually not specified in practice, the
algorithm given in Section 2.1 serves as a useful theoretical model for
understanding the behavior of SMC algorithms when $\pi$ is multimodal.

###  2.1 Sequential Monte Carlo (SMC)

Let $\mu_{0},\ldots,\mu_{V}$ be a sequence of distributions defined on
$\mathcal{X}$ with dominating measure $\rho$ and $\mu_{V}=\pi$. We write
$\mu_{v}(x)=q_{v}(x)/z_{v}$ with $q_{v}(x)$ denoting the unnormalized density
and $z_{v}$ the (often unknown) normalizing constant. Define the importance
weight $w_{v}(x):=q_{v}(x)/q_{v-1}(x)$. We assume that the density ratios are
uniformly bounded.

######  Assumption A1.

$\displaystyle\frac{\mu_{v}(x)}{\mu_{v-1}(x)}=\frac{z_{v-1}}{z_{v}}\cdot\frac{q_{v}(x)}{q_{v-1}(x)}=\frac{z_{v-1}}{z_{v}}\cdot
w_{v}(x)\leq ZW,$

where $Z=\max_{v\in\\{0,\ldots,V\\}}\frac{z_{v-1}}{z_{v}}$ and
$W=\max_{v\in\\{0,\ldots,V\\}}\sup_{x\in\mathcal{X}}w_{v}(x)$.

Denote the minimum probability of all partition elements across all steps as
$\mu^{\star}:=\min_{v=0,\ldots,V}\min_{j=1,\ldots,p}\mu_{v}(A_{j})$. The
algorithm we analyze is defined by the following procedure:

  1. 1.

For $v=0$, draw $X^{1:N}_{0}\overset{iid}{\sim}\mu_{0}$

  2. 2.

For $v=1,\ldots,V$,

    1. (a)

Set $\tilde{X}^{i}_{v}=X^{k}_{v-1}$ with probability
$w_{v}(X^{k}_{v-1})/\sum^{N}_{m=1}w_{v}(X^{m}_{v-1})$ independently for
$i=1,\ldots,N$.

    2. (b)

Draw $X^{i}_{v}\sim K_{v|A_{\xi^{i}_{v}}}^{t}(\tilde{X}^{i}_{v},\cdot)$ for
$i=1,\ldots,N$ and $t\geq 1$,

where $\xi^{i}_{v}=\sum^{p}_{j=1}j\mathbbm{1}_{A_{j}}(\tilde{X}_{v}^{i})$ is
the (random) partition element index containing $\tilde{X}_{v}^{i}$, and

$\displaystyle K_{v|A}(x,B)=K_{v}(x,B)+K_{v}(x,A^{c})\mathbbm{1}_{x\in
B}\text{ for }x\in A,B\subset A,$ (1)

where $K_{v}$ is a $\mu_{v}$-invariant Markov kernel and $K_{v\mid A}$ is the
restriction of $K$ to $A\subset\mathcal{X}$. Note that $K_{v\mid A}$ is
$\mu_{v\mid A}$-invariant by construction and is assumed to be ergodic for any
$A\subset\mathcal{X}$, where

$\displaystyle\mu_{v|A}(B)=\frac{\mu_{v}(A\cap B)}{\mu_{v}(A)},\text{ for
}B\subset\mathcal{X}$

The use of $K_{v\mid A_{j}}$ instead of $K_{v}$ implies that the mutation
kernel cannot cross between modes/partition elements. Consequently, we have
that $X^{i}_{v}\in A_{j}$ if and only if $\tilde{X}^{i}_{v}\in A_{j}$. Each
iteration of the algorithm above generates a set of resampled particles
$\tilde{X}^{1:N}_{v}:=(\tilde{X}^{1}_{v},\ldots,\tilde{X}^{N}_{v})$ and
mutated particles $X^{1:N}_{v}:=(X^{1}_{v},\ldots,X^{N}_{v})$. The full
algorithm then produces a total of $N(2V+1)$ particles defined on
$\mathcal{X}^{2N(V+1)}$ that evolve according to the following joint
probability laws,

$\displaystyle\operatorname{\mathbb{P}}_{0}(X^{1:N}_{0}\in
B_{1}\times\ldots\times B_{N})$ $\displaystyle=\prod^{N}_{i=1}\mu_{0}(B_{i})$
(2) $\displaystyle\tilde{\operatorname{\mathbb{P}}}_{v}(\tilde{X}^{1:N}_{v}\in
B_{1}\times\ldots\times B_{N}\mid X^{1:N}_{v-1})$
$\displaystyle=\prod^{N}_{i=1}\sum^{N}_{k=1}\frac{w_{v}(X^{k}_{v-1})\mathbbm{1}_{B_{i}}(X^{k}_{v-1})}{N\sum^{p}_{r=1}\hat{w}^{r}_{v}}$
(3) $\displaystyle\operatorname{\mathbb{P}}_{v}(X^{1:N}_{v}\in
B_{1}\times\ldots\times B_{N}\mid\tilde{X}^{1:N}_{v})$
$\displaystyle=\prod^{N}_{i=1}K_{v|A_{\xi^{i}_{v}}}^{t}(\tilde{X}^{i}_{v},B_{i}),$
(4)

where
$\hat{w}^{j}_{v}=N^{-1}\sum^{N}_{i=1}w_{v}(X^{i}_{v-1})\mathbbm{1}_{A_{j}}(X_{v-1}^{j})$
and $B_{i}\subset\mathcal{X}$ for $i=1,\ldots,N$.

###  2.2 Mixing times

A distribution $\nu$ is said to be $M$-warm with respect to a distribution
$\mu$ if $\sup_{B\subset\mathcal{X}}\nu(B)/\mu(B)\leq M$. Let
$\mathcal{P}_{M}(\mu)$ denote the set of all such distributions. Define the
$M$-warm mixing time for $j=1,\ldots,p$ by:

$\displaystyle\tau_{v,j}(\epsilon,M):=\min\left\\{t:\sup_{\eta\in\mathcal{P}_{M}(\mu_{v|A_{j}})}\left\lVert\int_{A_{j}}\eta_{|A_{j}}(dx)K_{v|A_{j}}^{t}(x,\cdot)-\mu_{v|A_{j}}(\cdot)\right\rVert_{\text{TV}}\leq\epsilon\right\\}$
(5)

Assuming that the initial distribution is $M$ warm is common among MCMC mixing
time results (see e.g. [9, 18, 44]); however, choosing such an initial
distribution can be difficult in practice.

####  2.2.1 Locally Warm Distributions

In later sections we will require a stronger notion of warmness than the
standard definition above. We call this stronger version local warmness:

######  Definition 1.

A distribution $\nu$ is _locally $M$-warm_ with respect to a distribution
$\mu$ and partition $\mathcal{A}=\\{A_{j}:j=1,\ldots,p\\}$ if,

$\displaystyle\sup_{B\subset A_{j}}\frac{\nu_{|A_{j}}(B)}{\mu_{|A_{j}}(B)}\leq
M$

Note that this is a stronger notion of warmness since it requires that
$\tilde{\mu}_{v}$ assign sufficiently large probability to each partition
element. Local warmness is useful when considering potentially multimodal
target distributions, because warmness of an initial distribution by the
standard definition is insufficient to guarantee rapid mixing on multimodal
distributions. For example, consider the Gaussian mixture
$\mu(x)=\frac{1}{2}\mathcal{N}(x;-\mathbf{1}_{d},I_{d})+\frac{1}{2}\mathcal{N}(x;\mathbf{1}_{d},\sigma^{2}I_{d})$
studied by [43]. The initial distribution
$\nu(x)=\mathcal{N}(x;-\mathbf{1}_{d},I_{d})$ provides a $2$-warm start but,
as the authors show, a random-walk Metropolis-Hastings algorithm still
produces a torpidly mixing chain. A key step in our analysis will be to show
that the resampling step (2a) of the SMC algorithm produces a distribution
$\tilde{\mu}$ that is locally warm for arbitrary partitions.

###  2.3 Coupling Constructions

The proof of Lemma 5 involves the construction of coupled random variables. We
briefly introduce some notation for this here but defer the detailed
construction to Appendix A. Our analysis constructs coupled pairs of random
variables $(X^{i}_{v},\bar{X}^{i}_{v})$. The pairs are conditionally
independent given $\tilde{X}^{i}_{v}$ and satisfy for $i=1,\ldots,N$ and
$j=1,\ldots,p$,

  1. (a)

$\operatorname{\mathbb{P}}(X^{i}_{v}\in B\mid\tilde{X}^{i}_{v}\in
A_{j})=\hat{\mu}_{v|A_{j}}(B)$

  2. (b)

$\operatorname{\mathbb{P}}(\bar{X}^{i}_{v}\in B\mid\tilde{X}^{i}_{v}\in
A_{j})=\mu_{v|A_{j}}(B)$

  3. (c)

$\operatorname{\mathbb{P}}(X^{i}_{v}\neq\bar{X}^{i}_{v}\mid\tilde{X}^{i}_{v}\in
A_{j})=||\hat{\mu}_{v|A_{j}}(\cdot)-\mu_{v|A_{j}}(\cdot)||_{\text{TV}}$

While the $X_{v}^{i}$’s represent the particles produced by the SMC algorithm
as described above, the coupled random variables
$\bar{X}^{1:N}_{v}:=(\bar{X}^{1}_{v},\ldots,\bar{X}^{N}_{v})$ are simply a
theoretical tool for our analysis and are not constructed in practice. Note
that the construction preserves $\mathcal{L}(X^{i}_{v})$ and so the behavior
of the algorithm given in Section 2.1 is unchanged (see Section A).

###  2.4 Probability space and Marginal Distributions

Going forward, it should be understood that expectations are taken with
respect to the joint probability measure defined by (2)-(4) and the coupling
constructions up to time $V$. We simply write a generic
$\operatorname{\mathbb{P}}$ (and similarly for $\operatorname{\mathbb{E}}$) to
denote this joint probability measure. The corresponding state space is
$\mathcal{X}^{N(3V+1)}$ with product $\sigma$-field $\mathcal{B}^{N(3V+1)}$.
Our analysis will focus on the marginal distribution of individual resampled,
mutated, or coupled particles. We denote these marginal distributions as

$\displaystyle\tilde{\mu}_{v}(B)$
$\displaystyle:=\operatorname{\mathbb{P}}(\tilde{X}^{i}_{v}\in B)$
$\displaystyle\hat{\mu}_{v}(B)$
$\displaystyle:=\operatorname{\mathbb{P}}(X^{i}_{v}\in B)$
$\displaystyle\bar{\mu}_{v}(B)$
$\displaystyle:=\operatorname{\mathbb{P}}(\bar{X}^{i}_{v}\in B),$

which are identical for $i=1,\ldots,N$ by symmetry. Similarly, conditional
distributions are denoted by $\tilde{\mu}(B\mid
H)=\operatorname{\mathbb{P}}(\tilde{X}^{i}_{v}\in B\mid H)$ for
$B\subset\mathcal{X}$ and $H\in\mathcal{B}^{N(3V+1)}$. In addition, we will
use the convenient shorthand $\tilde{\mu}_{v|A_{j}}$, $\hat{\mu}_{v|A_{j}}$,
and $\bar{\mu}_{v|A_{j}}$ to denote the corresponding restricted
distributions, e.g.
$\tilde{\mu}_{v|A_{j}}(B)=\tilde{\mu}_{v}(B\mid\tilde{X}_{v}^{i}\in A_{j})$,
and the mixed notation $\tilde{\mu}_{v|A_{j}}(B\mid
H)=\operatorname{\mathbb{P}}(\tilde{X}^{i}_{v}\in B\mid\tilde{X}^{i}_{v}\in
A_{j},H)$ for restrictions of conditional distributions. We note that
$\bar{\mu}_{v}\neq\mu_{v}$ in general (see Appendix A for details). Finally,
we define the filtration
$\mathcal{F}_{v}:=\sigma(\\{X^{1:N}_{k},\tilde{X}^{1:N}_{k}\\}^{v}_{k=1})$
with $\mathcal{F}_{0}=\sigma(X^{1:N}_{0})$ and denote the probability of
resampling into $A_{j}$ as

$\displaystyle\hat{P}^{j}_{v}:=\tilde{\mu}_{v}(A_{j}\mid\mathcal{F}_{v-1})=\frac{\hat{w}^{j}_{v}}{\sum^{p}_{r=1}\hat{w}^{r}_{v}},$

where $\hat{w}^{j}_{v}$ is defined in Section 2.1. That is,
$\\{\hat{P}^{j}_{v}\\}$ is a stochastic processes adapted to the filtration
$\\{\mathcal{F}_{v}\\}$.

##  3 Approach

Given some $\operatorname{\mathbb{P}}$-measurable function $\left|f\right|\leq
1$, our goal is to show that the SMC estimator
$\hat{f}=\frac{1}{N}\sum_{i=1}^{N}f(X_{V}^{i})$ approximates $E_{\pi}[f]$ to
high accuracy with high probability. The challenge is to do so without
requiring $X_{V}^{i}\sim\pi$. Observe that

$\displaystyle\operatorname{\mathbb{E}}_{\pi}[f]=\sum^{p}_{j=1}\operatorname{\mathbb{E}}_{\pi_{\mid
A_{j}}}[f]\pi(A_{j})\quad\text{ while
}\quad\operatorname{\mathbb{E}}[\hat{f}]=\sum^{p}_{j=1}\operatorname{\mathbb{E}}_{\hat{\mu}_{V\mid
A_{j}}}[\hat{f}_{j}]\,\hat{\mu}_{V}(A_{j})$

where
$\hat{f}_{j}=\frac{1}{N}\sum^{N}_{i=1}f(X^{i}_{V})\mathbbm{1}_{A_{j}}(X^{i}_{V})$.
Consequently, we must control two sources of error: the deviation of $\hat{f}$
from its expectation $|\hat{f}-\operatorname{\mathbb{E}}[\hat{f}]|$, and the
error in the expectation itself (bias)
$|\operatorname{\mathbb{E}}[\hat{f}]-\operatorname{\mathbb{E}}_{\pi}[f]|$.
Controlling the latter source of error is the more delicate of the two. To do
so, we will define a sequence of events conditional upon which
$\hat{\mu}_{v\mid A_{j}}\approx\mu_{v\mid A_{j}}$ and
$\hat{\mu}_{v}(A_{j})\approx\mu_{v}(A_{j})$, and then show that this sequence
of events occurs with sufficiently high probability. This requires choosing
$N$ sufficiently large to sequentially control the bias introduced by
resampling. Previously, Marion, Mathews and Schmidler [24] control this by
constructing a coupling to i.i.d. particles and invoking concentration
properties thereof. The main difficulty here is that, in the absence of
assumptions of global mixing, the coupling construction provides particles
which are neither independent nor have the correct distribution
($\mathcal{L}(\bar{X}^{i}_{v})\neq\mu_{v}$). As a result, establishing
concentration properties involving $\bar{X}^{1:N}_{v}$ (and consequently
$X^{1:N}_{v}$) is non-trivial.

For $j=1,\ldots,p$ and $v=1,\ldots,V$, define the following events on the
probability space
$(\mathcal{X}^{N(3V+1)},\mathcal{B}^{N(3V+1)},\operatorname{\mathbb{P}})$:

$\displaystyle\mathcal{C}^{j}_{1}(i)$
$\displaystyle=\left\\{\left|\bar{w}^{j}_{1}-\frac{z_{1}}{z_{0}}\mu_{1}(A_{j})\right|\leq\lambda\cdot\frac{z_{1}}{z_{0}}\mu_{1}(A_{j})\right\\}$
(6) $\displaystyle\mathcal{C}^{j}_{v}(i)$
$\displaystyle=\left\\{\left|\bar{w}^{j}_{v}-\operatorname{\mathbb{E}}[\bar{w}^{j}_{v}\mid\mathcal{F}_{v-2}]\right|\leq\lambda\cdot\operatorname{\mathbb{E}}[\bar{w}^{j}_{v}\mid\mathcal{F}_{v-2}]\right\\}\text{
for }v\geq 2$ (7) $\displaystyle\mathcal{C}_{v}(ii)$
$\displaystyle=\left\\{\bar{X}^{1:N}_{v}=X^{1:N}_{v}\right\\},$ (8)

where
$\bar{w}^{j}_{v}=N^{-1}\sum^{N}_{i=1}w_{v}(\bar{X}^{i}_{v-1})\mathbbm{1}_{A_{j}}(\bar{X}_{v-1}^{i})$,
and $\lambda=\frac{\epsilon}{24V}$ where $\epsilon\in(0,\frac{1}{2})$ is the
error tolerance chosen by the user in the application of Theorem 1. The event
$\mathcal{C}_{v}^{j}(i)$ represents the successful approximation by
$\bar{w}^{j}_{k}$ of its conditional mean to within desired relative error
bound $\lambda$. Note that
$\operatorname{\mathbb{E}}[\bar{w}^{j}_{v}|\mathcal{F}_{v-2}]$ is a random
variable; the event $\mathcal{C}^{j}_{v}(i)$ corresponds to $\bar{w}^{j}_{v}$
being ‘sandwiched’ between two other random variables. $\mathcal{C}_{v}(ii)$
is the simultaneous coupling event for all particles at step $k$. Our approach
is to show that all of the events $\mathcal{C}_{v}^{j}(i)$,
$\mathcal{C}_{v}^{j}(ii)$, $j=1,\ldots,p$, $k=1,\ldots,V$, occur
simultaneously with high probability, and that conditional on their
simultaneous occurrence we have $\hat{\mu}_{v\mid A_{j}}\approx\mu_{v\mid
A_{j}}$ and $\hat{\mu}_{v}(A_{j})\approx\mu_{v}(A_{j})$ for all
$v=1,\ldots,V$.

In Section 4.1, we show that simultaneous occurrence of these events ensures
$\hat{\mu}_{v\mid A_{j}}\approx\mu_{v\mid A_{j}}$ and
$\hat{\mu}_{v}(A_{j})\approx\mu_{v}(A_{j})$, and hence that
$\sum^{p}_{r=1}\operatorname{\mathbb{E}}[\hat{w}^{r}_{v}]$ closely
approximates $z_{v+1}/z_{v}$. In Section 4.2 we show that all of the events
$\mathcal{C}_{v}^{j}(i)$, $\mathcal{C}_{v}^{j}(ii)$, $j=1,\ldots,p$,
$k=1,\ldots,V$, occur simultaneously with high probability. We will do so by
induction on $k$. In particular, let
$\mathcal{C}^{1:p}_{v}(i)=\cap^{p}_{r=1}\mathcal{C}^{r}_{v}(i)$. For each $V$
and for a chosen $\lambda$ we will show that the probability of the following
event is large:

$\displaystyle\mathcal{E}_{v}:=\cap^{v}_{k=1}\\{\mathcal{C}^{1:p}_{k}(i)\cap\mathcal{C}_{k}(ii)\\}$

$\mathcal{E}_{v}$ is the joint event that all (6), (7), and (8) occur for
steps $1,\ldots,v$. It will also be convenient to define the events
$\mathcal{G}_{v}:=\mathcal{E}_{v-1}\cap\mathcal{C}^{1:p}_{v}(i)$ for $v\geq 2$
and $\mathcal{G}_{1}=\mathcal{C}^{1:p}_{1}(i)$ so that
$\mathcal{E}_{v}=\mathcal{G}_{v}\cap\mathcal{C}_{v}(ii)$.

##  4 Results

Our main result for the algorithm in Section 2.1 is stated in the following
Theorem. Supporting lemmas used in the proof of Theorem 1 are given in Section
4.1 and Section 4.2.

######  Theorem 1.

Suppose $|f|\leq 1$ and (A1) holds. Let $\epsilon\in(0,\frac{1}{2})$ and
choose

  1. 1.

$N>\frac{1}{\epsilon^{2}}\cdot\max\left\\{3456\cdot\left(\frac{VWZ}{\mu^{\star}}\right)^{2}\cdot\log(\frac{64Vp}{\mu^{\star}}),\
p^{2}\cdot\log(1024p^{2})\right\\}$

  2. 2.

$t>\max\limits_{j=1,\ldots,p}\max\limits_{v=1,\ldots,V}\tau_{v,j}(\frac{\mu^{\star}}{16NV},7)$,

Then with probability at least $3/4$,

$\displaystyle\left|\frac{1}{N}\sum^{N}_{i=1}f(X^{i}_{V})-\frac{(1+\frac{\epsilon^{2}}{16})}{(1-\frac{\epsilon^{2}}{16})}\operatorname{\mathbb{E}}_{\pi}[f]\right|\leq\epsilon.$

Note that Theorem 1 provides bounds on the total number of Markov transition
steps $NVt$ required to approximate $\operatorname{\mathbb{E}}_{\pi}[f]$ for
an arbitrary bounded function $f(x)$. For specific choices of $f$, improved
bounds may be available.

###  4.1 Results Over Restricted Space

We establish three key lemmas. The first shows that $\hat{P}^{j}_{v}$ closely
approximates $\mu_{v}(A_{j})$ over $\mathcal{G}_{v}\subset\mathcal{E}_{v}$.
The second shows that $\sum^{p}_{r=1}\hat{w}^{r}_{v}$ closely approximates
$z_{v+1}/z_{v}$ conditional on $\mathcal{G}_{v}$. The third shows that the
distribution $\tilde{\mu}_{v}(\cdot\mid\mathcal{G}_{v})$ is locally 7-warm
(see Definition 1) with respect to $\mathcal{A}$. Note that all of these
results describe what happens conditional on $\mathcal{G}_{v}$ holding. In
Section 4.2, we use the results developed here to show also that
$\mathcal{G}_{v}$ occurs with high probability. The results in these two
sections are then combined to obtain the proof of Theorem 1.

######  Lemma 1.

Let $\phi(\lambda)=\phi=\frac{1+\lambda}{1-\lambda}$. For $v=1,\ldots,V$,

$\displaystyle\operatorname{\mathbb{P}}\left(\phi^{-v}\mu_{v}(A_{j})\leq\hat{P}_{v}^{j}\leq\phi^{v}\mu_{v}(A_{j})\mid\mathcal{G}_{v}\right)=1.$

In particular, since
$\tilde{\mu}(A_{j}\mid\mathcal{G}_{v})=\operatorname{\mathbb{P}}(\tilde{X}^{i}_{v}\in
A_{j}\mid\mathcal{G}_{v})=\operatorname{\mathbb{E}}\left[\hat{P}^{j}_{v}\mid\mathcal{G}_{v}\right]$
we have:

$\displaystyle\phi^{-v}\mu_{v}(A_{j})\leq\tilde{\mu}_{v}(A_{j}\mid\mathcal{G}_{v})\leq\phi^{v}\mu_{v}(A_{j}).$

###### Proof.

(Lemma 1) First notice that given $\mathcal{G}_{v}$ we have

$\displaystyle\hat{P}_{v}^{j}=\frac{\hat{w}^{j}_{v}}{\sum^{p}_{r=1}\hat{w}^{r}_{v}}=\frac{\bar{w}^{j}_{v}}{\sum^{p}_{r=1}\bar{w}^{r}_{v}}$
$\displaystyle\leq\frac{(1+\lambda)\operatorname{\mathbb{E}}[\bar{w}^{j}_{v}\mid\mathcal{F}_{v-2}]}{(1-\lambda)\sum^{p}_{r=1}\operatorname{\mathbb{E}}[\bar{w}^{r}_{v}\mid\mathcal{F}_{v-2}]}$
$\displaystyle=\phi\frac{\operatorname{\mathbb{E}}[\bar{w}^{j}_{v}\mid\mathcal{F}_{v-2}]}{\sum^{p}_{r=1}\operatorname{\mathbb{E}}[\bar{w}^{r}_{v}\mid\mathcal{F}_{v-2}]}$
(9)

where the second equality follows by recalling that
$\mathcal{C}_{v-1}(ii)=\\{X_{v-1}^{1:N}=\bar{X}^{1:N}_{v-1}\\}$ and
$\mathcal{C}_{v-1}(ii)\subset\mathcal{G}_{v}$, and the first inequality by
recalling that $\mathcal{C}^{1:p}_{v}(i)\subset\mathcal{G}_{v}$ and
$\mathcal{C}^{1:p}_{v}(i)=\\{(1-\lambda)\operatorname{\mathbb{E}}[\bar{w}^{j}_{v}|\mathcal{F}_{v-2}]\leq\bar{w}^{j}_{v}\leq(1+\lambda)\operatorname{\mathbb{E}}[\bar{w}^{j}_{v}|\mathcal{F}_{v-2}]\\}$.
Lemma 10 in Appendix A shows that

$\displaystyle\operatorname{\mathbb{E}}[\bar{w}^{j}_{v}|\mathcal{F}_{v-2}]=\frac{z_{v}}{z_{v-1}}\cdot\frac{\mu_{v}(A_{j})}{\mu_{v-1}(A_{j})}\cdot\hat{P}^{j}_{v-1}$
(10)

Intuitively, this means that
$\operatorname{\mathbb{E}}[\bar{w}^{j}_{v}|\mathcal{F}_{v-2}]$ is the ratio of
the normalizing constants of the restricted distributions $\mu_{v|A_{j}}$ and
$\mu_{v-1|A_{j}}$ but weighted by the probability that a particle is resampled
into $A_{j}$. We can think of the filtration as being summarized solely
through $\hat{P}^{j}_{v-1}$ due to the conditional independence properties of
the constructed particles (see Lemma 9 in Appendix A). Combining (9) and (10)
and canceling, we have

$\displaystyle\frac{\hat{w}^{j}_{v}}{\sum^{p}_{r=1}\hat{w}^{r}_{v}}\leq\phi\frac{\frac{\mu_{v}(A_{j})}{\mu_{v-1}(A_{j})}\hat{P}^{j}_{v-1}}{\sum^{p}_{r=1}\frac{\mu_{v}(A_{r})}{\mu_{v-1}(A_{r})}\hat{P}^{r}_{v-1}}=\phi\frac{\frac{\mu_{v}(A_{j})}{\mu_{v-1}(A_{j})}\hat{w}^{j}_{v-1}}{\sum^{p}_{r=1}\frac{\mu_{v}(A_{r})}{\mu_{v-1}(A_{r})}\hat{w}^{r}_{v-1}}$
(11)

Barring the constant terms, the right hand side of (11) is the same as the
left hand side except the index has been decremented by one. Recall that
$\mathcal{G}_{v}$ ensures that the events $\mathcal{C}_{v}^{1:p}(i)$ and
$\mathcal{C}_{v-1}(ii)$ which we appealed to for step $v$ also hold for all
previous steps $0,\ldots,v-1$. Thus given $\mathcal{G}_{v}$ the argument above
can be repeated recursively to give

$\displaystyle\frac{\hat{w}^{j}_{v}}{\sum^{p}_{r=1}\hat{w}^{r}_{v}}\leq\phi\frac{\frac{\mu_{v}(A_{j})}{\mu_{v-1}(A_{j})}\hat{w}^{j}_{v-1}}{\sum^{p}_{r=1}\frac{\mu_{v}(A_{r})}{\mu_{v-1}(A_{r})}\hat{w}^{r}_{v-1}}$
$\displaystyle\leq\phi^{2}\frac{\frac{\mu_{v}(A_{j})}{\mu_{v-2}(A_{j})}\hat{w}^{j}_{v-2}}{\sum^{p}_{r=1}\frac{\mu_{v}(A_{r})}{\mu_{v-2}(A_{r})}\hat{w}^{r}_{v-2}}$
$\displaystyle\ldots$
$\displaystyle\leq\phi^{v-1}\frac{\frac{\mu_{v}(A_{j})}{\mu_{1}(A_{j})}\hat{w}^{j}_{1}}{\sum^{p}_{r=1}\frac{\mu_{v}(A_{r})}{\mu_{1}(A_{r})}\hat{w}^{r}_{1}}$

Recall that $\mathcal{C}^{1:p}_{0}(i)\subset\mathcal{G}_{v}$ is the event that
$\hat{w}^{j}_{1}$ closely approximates the normalizing constant of the
restricted distribution $\mu_{1|A_{j}}$; plugging this in gives

$\displaystyle\hat{P}_{v}^{j}=\frac{\hat{w}^{j}_{v}}{\sum^{p}_{r=1}\hat{w}^{r}_{v}}\leq\phi^{v}\frac{\frac{\mu_{v}(A_{j})}{\mu_{1}(A_{j})}\frac{z_{1}\mu_{1}(A_{j})}{z_{0}}}{\sum^{p}_{r=1}\frac{\mu_{v}(A_{r})}{\mu_{1}(A_{r})}\frac{z_{1}\mu_{1}(A_{r})}{z_{0}}}=\phi^{v}\mu_{v}(A_{j})$

Repeating the argument in the other direction (with $\phi^{-1}$ in place of
$\phi$) yields the result.

∎

######  Remark 1.

Note that the same argument implies

$\displaystyle\operatorname{\mathbb{P}}\left(\phi^{-v}\mu_{v}(A_{j})\leq\hat{P}_{v}^{j}\leq\phi^{v}\mu_{v}(A_{j})\mid\mathcal{G}_{v^{\prime}}\right)=1$

for any $v^{\prime}\geq v$. To see this, notice that
$\mathcal{G}_{v}\subset\mathcal{G}_{v^{\prime}}$ and the above argument holds
for any set containing $\mathcal{G}_{v}$.

To establish local warmness of $\tilde{\mu}_{v}$, we will use the following
lemma which shows that $\sum_{j}\hat{w}^{j}_{v}$ closely approximates
$z_{v}/z_{v-1}$ over $\mathcal{G}_{v}$. This establishes that, within the set
$\mathcal{G}_{v}$, the algorithm given in Section 2.1 can be used to
approximate $z_{v}$ for any $v=1,\ldots,V$ when the initial $z_{0}$ is known.

######  Lemma 2.

For $v=1,\ldots,V$ we have

$\displaystyle\operatorname{\mathbb{P}}\left(\frac{1}{\phi^{v}}\frac{z_{v}}{z_{v-1}}\leq\sum^{p}_{r=1}\hat{w}^{r}_{v}\leq\phi^{v}\frac{z_{v}}{z_{v-1}}\Bigm{|}\mathcal{G}_{v}\right)=1$

###### Proof.

Note that $\mathcal{C}_{v-1}(ii)\subset\mathcal{G}_{v}$ and so
$\hat{w}^{j}_{v}=\bar{w}^{j}_{v}$ for $j=1,\ldots,p$ given $\mathcal{G}_{v}$.
We then have

$\displaystyle\sum_{j=1}^{p}\bar{w}_{v}^{j}\geq\frac{z_{v}}{z_{v-1}}\sum_{j=1}^{p}(1-\lambda)\frac{\mu_{v}(A_{j})}{\mu_{v-1}(A_{j})}\hat{P}_{v-1}^{j}$
$\displaystyle\geq\frac{(1-\lambda)}{\phi^{v-1}}\frac{z_{v}}{z_{v-1}}\sum_{j=1}^{p}\mu_{v}(A_{j})$
$\displaystyle\geq\frac{1}{\phi^{v}}\cdot\frac{z_{v}}{z_{v-1}}$

The first inequality follows since
$\mathcal{C}^{1:p}_{v}(i)\subset\mathcal{G}_{v}$ and by Lemma 10 (see Appendix
A). The second inequality follows by Lemma 1. An identical argument can be
repeated in the other direction showing
$\sum_{j=1}^{p}\bar{w}_{v}^{j}\leq\phi^{v}\frac{z_{v}}{z_{v-1}}$. ∎

We now show that $\tilde{\mu}_{v}(\cdot\mid\mathcal{G}_{v})$ is a locally
7-warm distribution with respect to $\mu_{v}$ and $\mathcal{A}$. To do this,
we first state an inequality regarding $\phi^{v}$.

######  Proposition 1.

Let $\phi(\lambda)=\phi=\frac{1+\lambda}{1-\lambda}$ and recall
$\lambda\leq\frac{\epsilon}{6V}$ . Then
$\phi^{v}<\phi^{2v}<\frac{1+\epsilon}{1-\epsilon}$ for $v=1,\ldots,V$,

###### Proof.

$\displaystyle\phi^{2v}=\left(\frac{1+\frac{\epsilon}{6V}}{1-\frac{\epsilon}{6V}}\right)^{2v}\leq\frac{e^{\frac{\epsilon}{3}}}{1-\frac{\epsilon}{3}}\leq\frac{1+\frac{\epsilon}{3}+\frac{\epsilon^{2}}{9}}{1-\frac{\epsilon}{3}}\leq\frac{1+\epsilon}{1-\epsilon},$

where we used the elementary inequalities $1+x\leq e^{x}$, $(1+x)^{p}\geq
1+xp$ for $x>-1$ and $p>1$, and $e^{x}\leq 1+x+x^{2}$ for $x\in(0,1)$. ∎

Proposition 1 shows that taking $\lambda$ to be $\mathcal{O}(V^{-1})$ suffices
to ensure the bound in Lemma 1 is uniform over $v=1,\ldots,V$.

######  Lemma 3.

Suppose
$\operatorname{\mathbb{P}}(\mathcal{G}^{c}_{v})\leq\frac{\mu^{\star}}{4}$ and
recall $\lambda=\frac{\epsilon}{24V}\leq\frac{1}{6V}$. Then
$\tilde{\mu}(\cdot\mid\mathcal{G}_{v})$ is locally 7-warm with respect to
$\mu_{v}$ for partition $\mathcal{A}$; that is,

$\displaystyle\sup_{B\subset A_{j}}\frac{\tilde{\mu}_{v\mid
A_{j}}(B\mid\mathcal{G}_{v})}{\mu_{v\mid A_{j}}(B)}<7,\text{ for
}j=1,\ldots,p.$

###### Proof.

Expand

$\displaystyle\frac{\tilde{\mu}_{v\mid
A_{j}}(B\mid\mathcal{G}_{v})}{\mu_{v\mid
A_{j}}(B)}=\frac{\tilde{\mu}_{v}(B\cap
A_{j}\mid\mathcal{G}_{v})\mu_{v}(A_{j})}{\tilde{\mu}_{v}(A_{j}\mid\mathcal{G}_{v})\mu_{v}(B\cap
A_{j})}$ (12)

and consider first the term $\tilde{\mu}_{v}(B\cap
A_{j}\mid\mathcal{G}_{v})=\operatorname{\mathbb{P}}(\tilde{X}^{i}_{v}\in B\cap
A_{j}\mid\mathcal{G}_{v})$. We have

$\displaystyle\operatorname{\mathbb{P}}(\tilde{X}^{i}_{v}\in B\cap
A_{j}\mid\mathcal{G}_{v})$
$\displaystyle=\operatorname{\mathbb{E}}\left[\frac{\frac{1}{N}\sum^{N}_{n=1}w_{v}(\bar{X}^{n}_{v-1})\mathbbm{1}_{A_{j}\cap
B}(\bar{X}^{n}_{v-1})}{\sum^{p}_{r=1}\bar{w}^{r}_{v}}\Bigm{|}\mathcal{G}_{v}\right]$
$\displaystyle\leq\phi^{v}\operatorname{\mathbb{E}}\left[\frac{\mu_{v}(\bar{X}^{i}_{v-1})}{\mu_{v-1}(\bar{X}^{i}_{v-1})}\mathbbm{1}_{A_{j}\cap
B}(\bar{X}^{i}_{v-1})\Bigm{|}\mathcal{G}_{v}\right]$
$\displaystyle=\frac{\phi^{v}}{\operatorname{\mathbb{P}}(\mathcal{G}_{v})}\operatorname{\mathbb{E}}\left[\frac{\mu_{v}(\bar{X}^{i}_{v-1})}{\mu_{v-1}(\bar{X}^{i}_{v-1})}\mathbbm{1}_{A_{j}\cap
B}(\bar{X}^{i}_{v-1})\mathbbm{1}_{\mathcal{G}_{v}}(X_{1:v-1}^{1:N},\bar{X}_{1:v-1}^{1:N})\right]$
$\displaystyle\leq\frac{\phi^{v}}{\operatorname{\mathbb{P}}(\mathcal{G}_{v})}\operatorname{\mathbb{E}}\left[\frac{\mu_{v}(\bar{X}^{i}_{v-1})\mathbbm{1}_{A_{j}\cap
B}(\bar{X}^{i}_{v-1})}{\mu_{v-1}(\bar{X}^{i}_{v-1})}\Bigm{|}\bar{X}^{i}_{v-1}\in
A_{j}\right]\bar{\mu}_{v-1}(A_{j})$
$\displaystyle=\frac{\phi^{v}}{\operatorname{\mathbb{P}}(\mathcal{G}_{v})}\mu_{v}(A_{j}\cap
B)\frac{\tilde{\mu}_{v-1}(A_{j})}{\mu_{v-1}(A_{j})}$

The first inequality follows by Lemma 2. The second inequality follows from
non-negativity of the integrand and from the law of total probability. The
latter is required because $\bar{\mu}_{v-1}\neq\mu_{v-1}$ but
$\operatorname{\mathbb{P}}(\bar{X}^{i}_{v-1}\in
B^{\prime}\mid\bar{X}^{i}_{v-1}\in A_{j})=\mu_{v-1|A_{j}}(B{{}^{\prime}})$ for
$B{{}^{\prime}}\subset\mathcal{X}$ (see Appendix A). This fact is also used in
the final line, along with the fact that
$\bar{\mu}_{v}(A_{j})=\tilde{\mu}_{v}(A_{j})$ holds for all $i,j,v$ by
construction (see Appendix A). As a result, from (12) we have:

$\displaystyle\frac{\tilde{\mu}_{v\mid
A_{j}}(B\mid\mathcal{G}_{v})}{\mu_{v\mid
A_{j}}(B)}\leq\frac{\phi^{v}}{\operatorname{\mathbb{P}}(\mathcal{G}_{v})}\frac{\operatorname{\mathbb{P}}(\tilde{X}^{i}_{v-1}\in
A_{j})}{\mu_{v-1}(A_{j})}\cdot\frac{\mu_{v}(A_{j})}{\tilde{\mu}_{v}(A_{j}\mid\mathcal{G}_{v})}.$

Now by Lemma 1,
$\tilde{\mu}_{v}(A_{j}\mid\mathcal{G}_{v})\geq\phi^{-v}\mu_{v}(A_{j})$ and
therefore
$\frac{\mu_{v}(A_{j})}{\tilde{\mu}_{v}(A_{j}\mid\mathcal{G}_{v})}\leq\phi^{v}$
provides a lower bound on the relative marginal probability of undersampling
partition elements. From Lemma 1 we also have

$\displaystyle\operatorname{\mathbb{P}}(\tilde{X}^{i}_{v-1}\in
A_{j})\,=\tilde{\mu}_{v-1}(A_{j})\leq\phi^{v-1}\mu_{v-1}(A_{j})\operatorname{\mathbb{P}}(\mathcal{G}_{v})+\operatorname{\mathbb{P}}(\mathcal{G}^{c}_{v}).$

Our assumptions on $\lambda$ and
$\operatorname{\mathbb{P}}(\mathcal{G}^{c}_{v})$ then yield

$\displaystyle\sup_{B\subset A_{j}}\frac{\tilde{\mu}_{v\mid
A_{j}}(B\mid\mathcal{G}_{v})}{\mu_{v\mid A_{j}}(B)}$
$\displaystyle\leq\frac{\phi^{2v}}{\operatorname{\mathbb{P}}(\mathcal{G}_{v})\mu_{v-1}(A_{j})}\operatorname{\mathbb{P}}(\tilde{X}^{i}_{v-1}\in
A_{j})$
$\displaystyle\leq\frac{\phi^{2v}}{\operatorname{\mathbb{P}}(\mathcal{G}_{v})}\left[\frac{\phi^{v-1}\mu_{v-1}(A_{j})\operatorname{\mathbb{P}}(\mathcal{G}_{v})+\operatorname{\mathbb{P}}(\mathcal{G}_{v}^{c})}{\mu_{v-1}(A_{j})}\right]$
$\displaystyle\leq\phi^{3v-1}+\frac{\phi^{2v}}{\operatorname{\mathbb{P}}(\mathcal{G}_{v})}$
$\displaystyle\leq 4\,e^{\frac{1}{2}}\,<\,7$

The third inequality follows since $\mu^{\star}\leq\mu_{v-1}(A_{j})$. The
final inequality is obtained by repeating the argument of Proposition 1 for
the choice of $\lambda$ to get $\phi^{jv}<\frac{6e^{\frac{j}{6}}}{6-j}$, and
using $\operatorname{\mathbb{P}}(\mathcal{G}_{v})>3/4$. ∎

###  4.2 Induction Argument

The remainder of the analysis is to show that $\mathcal{G}_{v}$ holds with
high probability. We will do so inductively by first establishing that
$\operatorname{\mathbb{P}}(\mathcal{E}_{v}\mid\mathcal{E}_{v-1})$ is
sufficiently large for all $v$.

######  Lemma 4.

Let $0<\delta<1$ and suppose
$N>\frac{2W^{2}Z^{2}\phi^{2(v-1)}\log(\frac{4p}{\delta})}{\lambda^{2}(\mu^{\star})^{2}}$.
Then

$\displaystyle\operatorname{\mathbb{P}}(\mathcal{C}^{1:p}_{v}(i)\mid\mathcal{E}_{v-1})\geq
1-\frac{\delta}{\operatorname{\mathbb{P}}(\mathcal{E}_{v-1})}$

###### Proof.

Note that $\mathcal{G}_{v-1}\subset\mathcal{E}_{v-1}$. By combining Lemma 10
(Appendix A) and Lemma 1, we have over $\mathcal{G}_{v-1}$,

$\displaystyle\operatorname{\mathbb{E}}[\bar{w}^{j}_{v}\mid\mathcal{F}_{v-2}]=\frac{z_{v}}{z_{v-1}}\cdot\frac{\mu_{v}(A_{j})}{\mu_{v-1}(A_{j})}\cdot\hat{P}^{j}_{v-1}\geq\frac{z_{v}}{z_{v-1}}\cdot\phi^{-(v-1)}\cdot\mu_{v}(A_{j})$

Then

$\displaystyle\operatorname{\mathbb{P}}((\mathcal{C}^{j}_{v}(i))^{c}\mid\mathcal{E}_{v-1})=$
$\displaystyle\operatorname{\mathbb{P}}\left(\left|\bar{w}^{j}_{v}-\operatorname{\mathbb{E}}[\bar{w}^{j}_{v}\mid\mathcal{F}_{v-2}]\right|>\lambda\operatorname{\mathbb{E}}[\bar{w}^{j}_{v}\mid\mathcal{F}_{v-2}]\mid\mathcal{E}_{v-1}\right)$
$\displaystyle\leq$
$\displaystyle\operatorname{\mathbb{P}}\left(\left|\bar{w}^{j}_{v}-\operatorname{\mathbb{E}}[\bar{w}^{j}_{v}\mid\mathcal{F}_{v-2}]\right|>\lambda\frac{z_{v}}{z_{v-1}}\phi^{-(v-1)}\mu_{v}(A_{j})\mid\mathcal{E}_{v-1}\right)$
$\displaystyle\leq$
$\displaystyle\frac{1}{\operatorname{\mathbb{P}}(\mathcal{E}_{v-1})}\operatorname{\mathbb{P}}\left(\left|\bar{w}^{j}_{v}-\operatorname{\mathbb{E}}[\bar{w}^{j}_{v}\mid\mathcal{F}_{v-2}]\right|>\lambda\frac{z_{v}}{z_{v-1}}\phi^{-(v-1)}\mu_{v}(A_{j})\right)$
$\displaystyle\leq$
$\displaystyle\frac{\delta}{p\operatorname{\mathbb{P}}(\mathcal{E}_{v-1})}$

where the last line in Appendix A with
$N>\frac{2W^{2}Z^{2}\phi^{2(v-1)}\log(\frac{4p}{\delta})}{\lambda^{2}(\mu^{\star})^{2}}$.
By the union bound,

$\displaystyle\operatorname{\mathbb{P}}(\cup^{p}_{j=1}(\mathcal{C}^{j}_{v}(i))^{c}\mid\mathcal{E}_{v-1})\leq\frac{\delta}{\operatorname{\mathbb{P}}(\mathcal{E}_{v-1})}$

DeMorgan’s law gives the result. ∎

To complete the inductive step, it remains to show that
$P(\mathcal{C}_{v}(ii)\mid\mathcal{C}_{v}^{1:p},\mathcal{E}_{v-1})$ is also
large. To do so, we use the local warmness result established in Lemma 3.

######  Lemma 5.

Suppose
$\operatorname{\mathbb{P}}(\mathcal{G}^{c}_{v})\leq\frac{\mu^{\star}}{4}$ and
recall $\lambda\leq\frac{1}{6V}$. Let

$\displaystyle
t>\max_{v=1,\ldots,V}\max_{j=1,\ldots,p}\tau_{v,j}\left(\frac{\delta}{N},7\right)$

Then $\operatorname{\mathbb{P}}(\mathcal{C}_{v}(ii)\mid\mathcal{G}_{v})\geq
1-\delta$.

###### Proof.

Since $\hat{\mu}_{v}(A_{j})=\tilde{\mu}_{v}(A_{j})$ for all $v,j$ (see
Appendix A), we have for $j=1,\ldots,p$ and $B\subset\mathcal{X}$,

$\displaystyle\hat{\mu}_{v|A_{j}}(B\mid\mathcal{G}_{v})$
$\displaystyle=\frac{\operatorname{\mathbb{P}}(X_{v}^{i}\in
B,\tilde{X}_{v}^{i}\in
A_{j}\mid\mathcal{G}_{v})}{\operatorname{\mathbb{P}}(\tilde{X}_{v}^{i}\in
A_{j}\mid\mathcal{G}_{v})}$
$\displaystyle=\frac{1}{\tilde{\mu}_{v}(A_{j}\mid\mathcal{G}_{v})}\int_{A_{j}}\tilde{\mu}_{v}(dx\mid\mathcal{G}_{v})K_{v|A_{j}}^{t}(x,B)$
$\displaystyle=\int_{\mathcal{X}}\tilde{\mu}_{v|A_{j}}(dx\mid\mathcal{G}_{v})K_{v|A_{j}}^{t}(x,B)$

By Lemma 3,
$\tilde{\mu}_{v|A_{j}}(\cdot\mid\mathcal{G}_{v})\in\mathcal{P}_{7}(\mu_{v|A_{j}})$.
Hence, by our choice of $t$,

$\displaystyle\left\lVert\hat{\mu}_{v|A_{j}}(\cdot\mid\mathcal{G}_{v})-\mu_{v|A_{j}}(\cdot)\right\rVert_{\text{TV}}\leq\frac{\delta}{N}\text{
for }j=1,\ldots,p$

It follows that we can construct $(X^{i}_{v},\bar{X}^{i}_{v})$ conditional on
$\tilde{X}^{i}_{v}$ independently for $i=1,\ldots,N$ such that

$\displaystyle\operatorname{\mathbb{P}}(X^{i}_{v}\neq\bar{X}^{i}_{v}\mid\tilde{X}^{i}_{v}\in
A_{j},\mathcal{G}_{v})\leq\frac{\delta}{N},\text{ for }j=1,\ldots,p$

(see Appendix A for details). It follows that
$\operatorname{\mathbb{P}}(X^{i}_{v}\neq\bar{X}^{i}_{v}\mid\mathcal{G}_{v})\leq\frac{\delta}{N}$
by the law of total probability. Finally, taking a union bound gives us the
stated result:

$\displaystyle\operatorname{\mathbb{P}}(\mathcal{C}_{v}(ii)\mid\mathcal{G}_{v})=\operatorname{\mathbb{P}}(X^{1:N}_{v}\neq\bar{X}^{1:N}_{v}\mid\mathcal{G}_{v})$
$\displaystyle\leq\delta$

∎

Lemma 4 and Lemma 5 are enough to establish that
$\operatorname{\mathbb{P}}(\mathcal{E}_{v}\mid\mathcal{E}_{v-1})$ can be made
sufficiently large, which gives us the following result.

######  Lemma 6.

Let $\delta\in(0,\frac{1}{4})$ and $\epsilon\in(0,\frac{1}{2})$. Choose

  1. 1.

$N>3456\cdot\left(\frac{VWZ}{\epsilon\mu^{\star}}\right)^{2}\cdot\log\left(\frac{8Vp}{\delta\mu^{\star}}\right)$

  2. 2.

$t>\max\limits_{j=1,\ldots,p}\max\limits_{v=1,\ldots,V}\tau_{v,j}(\frac{\delta\mu^{\star}}{2NV},7)$

Then

$\displaystyle\operatorname{\mathbb{P}}(\mathcal{E}_{V})\geq
1-\delta\mu^{\star}$

###### Proof.

First, suppose that
$\operatorname{\mathbb{P}}(\mathcal{G}_{k}^{c})\leq\frac{\mu^{\star}}{4}$ for
$k=1,\ldots,v$ so that we can directly apply Lemma 3 and Lemma 5 for steps
$k=1,\ldots,v$. Let $\delta^{\prime}=\frac{\delta\mu^{\star}}{2V}$. Then by
the definition of $\mathcal{E}_{v}$ and our choice of $N$ and $t$,

$\displaystyle\operatorname{\mathbb{P}}(\mathcal{E}_{v})$
$\displaystyle=\operatorname{\mathbb{P}}(\mathcal{C}^{1:p}_{v}(i)\,\cap\,\mathcal{C}_{v}(ii)\,\cap\,\mathcal{E}_{v-1})$
$\displaystyle=\operatorname{\mathbb{P}}(\mathcal{C}_{v}(ii)\mid\mathcal{C}^{1:p}_{v}(i)\,\cap\,\mathcal{E}_{v-1})\operatorname{\mathbb{P}}(\mathcal{C}^{1:p}_{v}(i)\mid\mathcal{E}_{v-1})\operatorname{\mathbb{P}}(\mathcal{E}_{v-1})$
$\displaystyle\geq(1-\delta^{\prime})\Big{(}1-\frac{\delta^{\prime}}{\operatorname{\mathbb{P}}(\mathcal{E}_{v-1})}\Big{)}\operatorname{\mathbb{P}}(\mathcal{E}_{v-1})$
$\displaystyle\geq\operatorname{\mathbb{P}}(\mathcal{E}_{v-1})-2\delta^{\prime}$

The first inequality follows by Lemmas 4 and Lemma 5. (Note that the choice of
$N$ here satisfies the bound required to apply Lemma 4 since $\phi^{2V}<3$ for
$\epsilon<\frac{1}{2}$ by Proposition 1). Since we have assumed
$\operatorname{\mathbb{P}}(\mathcal{G}_{k}^{c})\leq\frac{\mu^{\star}}{4}$ for
$k=1,\ldots,v$, we can apply this argument recursively to obtain

$\displaystyle\operatorname{\mathbb{P}}(\mathcal{E}_{v})\geq\operatorname{\mathbb{P}}(\mathcal{E}_{1})-2(v-1)\delta^{\prime}$
$\displaystyle=\operatorname{\mathbb{P}}(\mathcal{C}_{1}(ii)\mid\mathcal{G}_{1})\operatorname{\mathbb{P}}(\mathcal{G}_{1})-2(v-1)\delta^{\prime}$
$\displaystyle\geq(1-\delta^{\prime})(1-\delta^{\prime})-2(v-1)\delta^{\prime}$
$\displaystyle\geq 1-2v\delta^{\prime}$
$\displaystyle=1-\delta\mu^{\star}\frac{v}{V}$ (13)

The first inequality follows by Lemma 5 and because our choice of $N$
guarantees

$\displaystyle\operatorname{\mathbb{P}}(\mathcal{G}_{1})=\operatorname{\mathbb{P}}(\mathcal{C}^{1:p}_{1}(i))>1-\frac{\delta\mu^{\star}}{2V}$
(14)

It is straightforward to check this using Hoeffding’s inequality since
$X^{1:N}_{0}\overset{\mbox{\tiny{iid}}}{\sim}\mu_{0}$.

However, as noted above the application of Lemma 5 is invalid unless
$\operatorname{\mathbb{P}}(\mathcal{G}^{c}_{v})\leq\frac{\mu^{\star}}{4}$. We
now show this holds for $v=1,\ldots,V$ by way of induction. Indeed, the base
case holds by (14). Now suppose
$\operatorname{\mathbb{P}}(\mathcal{G}^{c}_{k})\leq\frac{\mu^{\star}}{4}$ for
$k=1,\ldots,v-1$. Then we have

$\displaystyle\operatorname{\mathbb{P}}(\mathcal{G}_{v})$
$\displaystyle=\operatorname{\mathbb{P}}(\mathcal{C}^{1:p}_{v}(i)|\mathcal{E}_{v-1})\operatorname{\mathbb{P}}(\mathcal{E}_{v-1})$
$\displaystyle\geq\operatorname{\mathbb{P}}(\mathcal{E}_{v-1})-\frac{\delta\mu^{\star}}{2V}$
$\displaystyle\geq 1-\frac{\delta\mu^{\star}v}{V}$ $\displaystyle\geq
1-\frac{\mu^{\star}}{4}$

The first inequality follows by Lemma 4 and choice of $N$. The second
inequality follows since the inductive hypothesis guarantees
$\operatorname{\mathbb{P}}(\mathcal{E}_{v-1})\geq
1-\delta\mu^{\star}\frac{v-1}{V}$ by (13). It follows that
$\operatorname{\mathbb{P}}(\mathcal{G}^{c}_{v})\leq\frac{\mu^{\star}}{4}$ for
$v=1,\ldots,V$. Hence (13) also holds for all $v=1,\ldots,V$ and so
$\operatorname{\mathbb{P}}(\mathcal{E}_{V})\geq 1-\delta\mu^{\star}$ as
required. ∎

###  4.3 Proof of Theorem 1

The proof of Theorem 1 uses the following additional lemma regarding the
target random variables $X^{1:N}_{V}$.

######  Lemma 7.

Let $\epsilon\in(0,\frac{1}{2})$ and recall $\lambda=\frac{\epsilon}{24V}$.
For any $f$ such that $|f|\leq 1$,

$\displaystyle\left|\sum^{p}_{j=1}\operatorname{\mathbb{E}}\left[f(\bar{X}^{i}_{V})\mathbbm{1}_{A_{j}}(\bar{X}^{i}_{V})\mid\mathcal{F}_{V-1}\right]-\frac{(1+\frac{\epsilon^{2}}{16})}{(1-\frac{\epsilon^{2}}{16})}\operatorname{\mathbb{E}}_{\pi}[f]\right|\leq\frac{3}{4}\epsilon$

###### Proof.

Write $f(x)=f^{+}(x)-f^{-}(x)$, where $f^{+}(x)=\max\\{f(x),0\\}$ and
$f^{-}(x)=\max\\{-f(x),0\\}$. To be consistent with Proposition 1, write
$\lambda$ as $\frac{\tilde{\epsilon}}{6V}$ where
$\tilde{\epsilon}=\epsilon/4$. For $j=1,\ldots,p$ we have

$\displaystyle\operatorname{\mathbb{E}}\left[f(\bar{X}^{i}_{V})\mathbbm{1}_{A_{j}}(\bar{X}^{i}_{V})\mid\mathcal{F}_{V-1}\right]$
$\displaystyle=\operatorname{\mathbb{E}}_{\pi_{|A_{j}}}[f^{+}]\hat{P}^{j}_{V}-\operatorname{\mathbb{E}}_{\pi_{|A_{j}}}[f^{-}]\hat{P}^{j}_{V}$
$\displaystyle\leq\frac{(1+\tilde{\epsilon})}{(1-\tilde{\epsilon})}\operatorname{\mathbb{E}}_{\pi}[f^{+}\mathbbm{1}_{A_{j}}(\bar{X}^{i}_{V})]-\frac{(1-\tilde{\epsilon})}{(1+\tilde{\epsilon})}\operatorname{\mathbb{E}}_{\pi}[f^{-}\mathbbm{1}_{A_{j}}(\bar{X}^{i}_{V})]$
$\displaystyle\leq\frac{(1+\tilde{\epsilon}^{2})}{(1-\tilde{\epsilon}^{2})}\operatorname{\mathbb{E}}_{\pi}[f\mathbbm{1}_{A_{j}}(\bar{X}^{i}_{V})]+\frac{2\tilde{\epsilon}}{(1-\tilde{\epsilon}^{2})}\pi(A_{j}),$

The first line follows by Lemma 10, the second by application of Lemma 1
followed by Proposition 1 with our choice of $\lambda$, and the last since
$|f|\leq 1$. Summing over $j$ gives

$\displaystyle\sum^{p}_{j=1}\operatorname{\mathbb{E}}\left[f(\bar{X}^{i}_{V})\mathbbm{1}_{A_{j}}(\bar{X}^{i}_{V})\mid\mathcal{F}_{V-1}\right]\leq\frac{(1+\frac{\epsilon^{2}}{16})}{(1-\frac{\epsilon^{2}}{16})}\operatorname{\mathbb{E}}_{\pi}[f]+\frac{3}{4}\epsilon.$

The argument for the lower bound is identical. ∎

We are now ready to give the complete proof of Theorem 1.

###### Proof.

(Theorem 1) Define the concentration event,

$\displaystyle\mathcal{D}^{j}=\left\\{\left|\bar{f}^{j}-\operatorname{\mathbb{E}}[f(\bar{X}^{i}_{V})\mathbbm{1}_{A_{j}}(\bar{X}^{i}_{V})|\mathcal{F}_{V-1}]\right|\leq\frac{\epsilon}{p}\right\\},$

where
$\bar{f}^{j}=\frac{1}{N}\sum^{N}_{i=1}f(\bar{X}^{i}_{V})\mathbbm{1}_{A_{j}}(\bar{X}^{i}_{V})$.
Note that over $\mathcal{E}_{v}$ we have

$\displaystyle\frac{1}{N}\sum^{N}_{i=1}f(X^{i}_{V})=\frac{1}{N}\sum^{N}_{i=1}\sum^{p}_{j=1}f(\bar{X}^{i}_{V})\mathbbm{1}_{A_{j}}(\bar{X}^{i}_{V})=\sum^{p}_{j=1}\bar{f}^{j}$

By Lemma 7, it follows that over
$\mathcal{E}_{V}\cap\mathcal{D}^{1}\cap\ldots\cap\mathcal{D}^{p}$,

$\displaystyle\frac{(1+\frac{\epsilon^{2}}{16})}{(1-\frac{\epsilon^{2}}{16})}\operatorname{\mathbb{E}}_{\pi}[f]-\epsilon\leq\frac{1}{N}\sum^{N}_{i=1}f(X^{i}_{V})\leq\frac{(1+\frac{\epsilon^{2}}{16})}{(1-\frac{\epsilon^{2}}{16})}\operatorname{\mathbb{E}}_{\pi}[f]+\epsilon$

It remains to show
$\operatorname{\mathbb{P}}(\mathcal{E}_{V}\cap\mathcal{D}^{1}\cap\ldots\cap\mathcal{D}^{p})\geq\frac{3}{4}$.
First, by Lemma 11,

$\displaystyle\operatorname{\mathbb{P}}(\cup^{p}_{j=1}(\mathcal{D}^{j})^{c})\leq\sum^{p}_{j=1}\operatorname{\mathbb{P}}\left(\left|\bar{f}^{j}-\operatorname{\mathbb{E}}[\bar{f}^{j}|\mathcal{F}_{V-1}]\right|>\frac{\epsilon}{p}\right)\leq\frac{1}{8},$

for $N>\frac{2p^{2}}{\epsilon^{2}}\log(32p)$. Note that
$\operatorname{\mathbb{P}}(\mathcal{E}_{V})\geq\frac{7}{8}$ by our choice of
$N$ and $t$ after applying Lemma 6 with $\delta=\frac{1}{8}$. By the union
bound,

$\displaystyle\operatorname{\mathbb{P}}((\mathcal{D}^{1})^{c}\cup\ldots\cup(\mathcal{D}^{p})^{c}\cup\mathcal{E}^{c}_{V})\leq\frac{1}{8}+\frac{1}{8}=\frac{1}{4}.$

∎

##  5 Applications

In this section, we apply the results in the previous section to obtain bounds
on the complexity of using sequential Monte Carlo to approximate expectations
for two specific classes of multimodal distributions: mixtures of log-concave
distributions and the mean-field Ising model. Each problem defines a nested
sequence of distributions indexed by a dimension parameter $d$, and we
consider the computational complexity, i.e. the growth of the computational
cost with increasing $d$. We characterize the computational cost of applying
the SMC algorithm given in Section 2.1 by the total number of Markov
transition steps $NVt$ required to apply Theorem 1, since the Markov
transition steps are typically the most computationally expensive step of the
algorithm. Throughout we will assume the corresponding partition sequence
$\mathcal{A}(d)$ satisfies $\pi^{*}=\min_{j\in\\{1,\ldots,p\\}}\pi(A_{j})$
decays at most polynomially in $d$. (Otherwise, the contribution of
$\operatorname{\mathbb{E}}_{\pi}[f\mathbbm{1}_{A_{j^{*}}}]$ to
$\operatorname{\mathbb{E}}_{\pi}[f]$ for the corresponding $j^{*}$ is
negligible for $d$ large since $\left|f\right|\leq 1$.)

###  5.1 Mixtures of Log-Concave Distributions

Consider the mixture distribution

$\displaystyle\pi(x)\propto
w\pi_{1}(x)\mathbbm{1}_{H}(x)+(1-w)\pi_{2}(x)\mathbbm{1}_{H^{c}}(x)\text{ for
}x\in\mathbb{R}^{d},$ (15)

where $w\in(0,1)$, $\pi_{j}(x)\propto e^{-f_{j}(x)}$, $f_{j}(x)>0$ is a convex
function for $j\in\\{1,2\\}$, and $H$ is a half-space. Throughout, we assume
without loss of generality that $H$ and $H^{c}$ contain
$\operatorname{\mathbb{E}}_{\pi_{1}}[X]$ and
$\operatorname{\mathbb{E}}_{\pi_{2}}[X]$, respectively. Note that $\pi$ is a
sum of log-concave functions, since $H$ and $H^{c}$ being half-spaces means
$\mathbbm{1}_{H}$ and $\mathbbm{1}_{H^{c}}$ are log-concave functions and log-
concavity is closed under multiplication.

Suppose we are interested in sampling from $\pi(x)$ using SMC, and we set
$\mu_{v}(x)\propto\pi^{\beta_{v}}(x)$ for $\beta_{v}\in(0,1]$ and
$\beta_{0},\ldots,\beta_{V}$ a strictly increasing sequence with
$\beta_{V}=1$. Since $f_{j}(x)>0$, it follows that $w_{v}(x)\leq 1$ uniformly
in $v$. We will assume that the following equality holds:

$\displaystyle\int_{\mathbbm{R}^{d}}e^{-\beta_{v}f_{1}(x)}dx=\int_{\mathbbm{R}^{d}}e^{-\beta_{v}f_{2}(x)}dx\text{
for }\beta_{v}\in(0,1]$ (16)

For example, if $f_{j}(x)=2^{-1}\sigma_{j}^{-2}\left\lVert
x-\mu_{j}\right\rVert^{2}$, as below in Section 5.2, then (16) requires that
$\sigma_{1}=\sigma_{2}$. More generally, (16) holds when $\pi_{1}$ and
$\pi_{2}$ are log-concave product distributions that belong to the same
location-scale family and have equal scales. Similar assumptions have been
made in previous analyses of these types of problems (see [42] and [16]), and
it is unclear whether the assumption (16) can be dropped. For example, if
$\sigma_{1}>\sigma_{2}$ in the problem considered in Section 5.2, then
$\mu^{\star}$ decays exponentially in $d$ [43].

Note that $\mu_{v}(x)$ can also be written as a sum of log-concave functions
and assumption (16) gives

$\displaystyle\mu_{v}(H)$
$\displaystyle=\frac{w\int_{H}\pi_{1}^{\beta_{v}}(x)dx}{w\int_{\mathbb{R}^{d}}\pi_{1}^{\beta_{v}}(x)\mathbbm{1}_{H}(x)dx+(1-w)\int_{\mathbb{R}^{d}}\pi_{2}^{\beta_{v}}(x)\mathbbm{1}_{H^{c}}(x)dx}$
$\displaystyle=\frac{w\pi_{1,v}(H)}{w\pi_{1,v}(H)+(1-w)\pi_{2,v}(H^{c})}$

where
$\pi_{v,j}(x)=e^{-\beta_{v}f_{j}(x)}/\int_{\mathbbm{R}^{d}}e^{-\beta_{v}f_{j}(x)}dx$
is an (untruncated) log-concave density function. By [19], if $h(x)$ is a log-
concave density and $H$ is a half-space containing the centroid of $h(x)$,
then $\int_{H}h(x)dx\geq e^{-1}$. Hence,
$\mu^{\star}\geq\max\\{w,1-w\\}/e=\mathcal{O}(1)$.

Since $H$ and $H^{c}$ are convex sets and $\pi_{v,j}(x)$ is a log-concave
density function, $\mu_{v|H}(x)$ and $\mu_{v|H^{c}}(x)$ are log-concave
density functions. Upper bounds on the mixing time of various Markov kernels
have been obtained in the literature for log-concave target distributions,
assuming a warm start. For example, [19] proved that both the ball walk and
hit-and-run walk are rapidly mixing when the target distribution is a
$C$-isotropic log-concave density function, and show that any $d$-dimensional
log-concave density function can be brought into a $C$-isotropic position in
$\mathcal{O}^{*}(d^{5})$ time (see [36] for a survey of these results). Recall
that both $\mu^{\star}=\mathcal{O}(1)$ and $W=\mathcal{O}(1)$. It follows that
by plugging into the bound on $N$ in Theorem 1 we obtain

$\displaystyle\frac{NV}{\mu^{\star}}=\mathcal{O}\left(\frac{V^{3}Z^{2}}{\epsilon^{2}}\cdot\log(V)\right)=\mathcal{O}(\text{poly}(V,\log(V),Z,\epsilon^{-1}))),$
(17)

Therefore, by choosing $K_{v|A_{j}}$ to be either the ball walk or hit-and-run
walk and applying the results of [19], we conclude

$\displaystyle\max\limits_{j=1,\ldots,p}\max\limits_{v=1,\ldots,V}\tau_{v,j}\left(\frac{\mu^{\star}}{16NV},7\right)=\mathcal{O}(\text{poly}(d,V,\log(V),Z,\epsilon^{-1}))$
(18)

Combining (17) and (18) gives that the computational cost of applying SMC to
this problem is $\mathcal{O}(\text{poly}(d,V,\log(V),Z,\epsilon^{-1}))$.

###  5.2 Gaussian mixtures

We can provide more explicit bounds when $f_{j}(x)$ is known. Consider the
Gaussian mixture distribution $f_{j}(x)=(2\sigma^{2})^{-1}\left\lVert
x-(-1)^{j+1}\mathbf{1}_{d}\right\rVert^{2}_{2}$ for $j\in\\{1,2\\}$ and
$H=\\{x:x^{\top}\mathbf{1}_{d}>0\\}$ studied by Woodard, Schmidler and Huber
[42]. Here we assume $w=\frac{1}{2}$; similar results apply if
$w\neq\frac{1}{2}$. Since the components share a common scale $\sigma>0$, it
is straightforward to check that (16) holds and clearly both
$\mathbf{1}_{d}\in H$ and $-\mathbf{1}_{d}\in H^{c}$. Define the sequence of
inverse-temperatures

$\displaystyle\beta_{v}=\frac{1}{d}\left(1+\frac{1}{d}\right)^{v}\text{ for
}v=0,\ldots,\lceil d\log(d)\rceil-1\text{ and }\beta_{V}=1.$

Note $\beta_{0}=d^{-1}$, which ensures rapid mixing for initialization (see
[42] for details). To bound the normalizing constants, notice

$\displaystyle\frac{z_{v-1}}{z_{v}}$
$\displaystyle=\frac{\int_{\mathbbm{R}^{d}}e^{-\beta_{v-1}f_{1}(x)}\mathbbm{1}_{H}(x)dx+\int_{\mathbbm{R}^{d}}e^{-\beta_{v-1}f_{2}(x)}\mathbbm{1}_{H^{c}}(x)dx}{\int_{\mathbbm{R}^{d}}e^{-\beta_{v}f_{1}(x)}\mathbbm{1}_{H}(x)dx+\int_{\mathbbm{R}^{d}}e^{-\beta_{v}f_{2}(x)}\mathbbm{1}_{H^{c}}(x)dx}$
$\displaystyle=\frac{\Phi(\frac{\sqrt{d\beta_{v-1}}}{\sigma})\left(\frac{2\pi\sigma^{2}}{\beta_{v-1}}\right)^{\frac{d}{2}}}{\Phi(\frac{\sqrt{d\beta_{v}}}{\sigma})\left(\frac{2\pi\sigma^{2}}{\beta_{v}}\right)^{\frac{d}{2}}}\leq
2\left(\frac{\beta_{v}}{\beta_{v-1}}\right)^{\frac{d}{2}}$

We see that $Z\leq 2e=\mathcal{O}(1)$. Next, we have

$\displaystyle\mu_{v}(H)=\frac{\int_{\mathbbm{R}^{d}}e^{-\beta_{v}f_{1}(x)}\mathbbm{1}_{H}(x)dx}{\int_{\mathbbm{R}^{d}}e^{-\beta_{v}f_{1}(x)}\mathbbm{1}_{H}(x)dx+\int_{\mathbbm{R}^{d}}e^{-\beta_{v}f_{2}(x)}\mathbbm{1}_{H^{c}}(x)dx}\geq\frac{1/2}{2}=\frac{1}{4}$

It follows that $\mu^{\star}\geq\frac{1}{4}=\mathcal{O}(1)$. Since
$V=\mathcal{O}(d\log(d))$, combining with (17) and (18) implies that a
computational complexity of

$\displaystyle\mathcal{O}(\text{poly}(d,\log(d),\log(d\log(d)),\epsilon^{-1}))=\mathcal{O}^{*}(\text{poly}(d))$

for SMC on this problem, where $\mathcal{O}^{*}$ indicates that the dependence
on logarithmic and error terms is suppressed.

###  5.3 Mean Field Ising Model

Let $\mathcal{X}=\\{-1,1\\}^{d}$ for $d\in\mathbbm{N}$. The mean field Ising
model is defined by the distribution

$\displaystyle\pi(x)=\frac{1}{Z}\exp\left\\{\frac{\alpha}{2d}\left(\sum^{d}_{i=1}x_{i}\right)^{2}\right\\},$

with normalizing constant
$Z=\sum_{x\in\mathcal{X}}\exp\\{\frac{\alpha}{2d}(\sum^{d}_{i=1}x_{i})^{2}\\}$
and interaction parameter $\alpha\in\mathbbm{R}$. We will assume $d$ is odd as
in [42]. Let $K_{v}$ be a Metropolis-Hastings chain with limiting distribution
$\mu_{v}(x)\propto\pi^{\beta_{v}}(x)$. We assume $K_{v}$ uses a single site
proposal distribution in which a coordinate $i\in\\{1,\ldots,d\\}$ is chosen
uniformly and the sign of $x_{i}$ is flipped. Letting $V=d$ and
$\beta_{v}=v/d$, it follows that both the parallel tempering and simulated
tempering algorithms are rapidly mixing [21, 42]. We will show that SMC also
provides a polynomial time approximation of
$\operatorname{\mathbb{E}}_{\pi}[f]$ for $|f|\leq 1$ using the same sequence
of distributions, in that the bounds on $N,t$ required to apply Theorem 1 grow
at most polynomially in $d$.

Our result is essentially a direct consequence of those from Madras and Zheng
[21] and Woodard, Schmidler and Huber [42]. Let
$A_{1}=\\{x:\sum^{d}_{i=1}x_{i}\geq 0\\}$ and
$A_{2}=\\{x:\sum^{d}_{i=1}x_{i}<0\\}$. First, note that sampling from
$\mu_{0}(x)\propto 1$ is trivial. Now, notice that $\pi(x)$ is symmetric with
respect to this partition for $\mu_{0},\ldots,\mu_{V}$ if $d$ is odd. It
follows that $\mu_{v}(A_{1})=\mu_{v}(A_{2})=1/2$ for $v=0,\ldots,V$ and so
$\mu^{\star}=1/2$. Woodard, Schmidler and Huber [42] show that

$\displaystyle\frac{\mu_{v}(x)}{\mu_{v-1}(x)}\in\left[\exp\left\\{-\frac{\alpha}{2}\right\\},\exp\left\\{\frac{\alpha}{2}\right\\}\right]$

therefore $ZW\leq\exp\\{\frac{\alpha}{2}\\}$. Since $V=d$, $p=2$,
$\mu^{\star}=\mathcal{O}(1)$, and $ZW=\mathcal{O}(1)$, we have that Theorem 1
requires

$\displaystyle
N>\frac{1}{\epsilon^{2}}\cdot\max\left\\{c_{1}\cdot\left(\frac{VWZ}{\mu^{\star}}\right)^{2}\log\left(\frac{c_{2}Vp}{\mu^{\star}}\right),\
p^{2}\cdot\log\left(c_{3}p^{2}\right)\right\\}=\mathcal{O}^{*}(d^{2}),$

where $c_{1}$, $c_{2}$, and $c_{3}$ are positive constants. To obtain the
required bound for $t$, note also that
$NV/\mu^{\star}=\mathcal{O}(d^{3}\log(d))$. A mixing time bound can be
obtained [20, 42] by defining the restricted kernel as in (1) with
corresponding invariant distributions $\mu_{v|A_{j}}$. Madras and Zheng [21]
show that $\min_{v,j}\text{Gap}(K_{v|A_{j}})$ decays at most polynomially in
$d$. Since for $j\in\\{1,2\\}$ we have (see [24])

$\displaystyle\tau_{v,j}(\epsilon,M)$
$\displaystyle\leq\frac{1}{\text{Gap}(K_{v\mid
A_{j}})}\left[\log(2\epsilon^{-1})+\log(M-1)\right]$ (19)
$\displaystyle\leq\frac{1}{\min_{\begin{subarray}{c}v^{\prime}=1,\ldots,V\\\
j^{\prime}=1,\ldots,p\end{subarray}}\text{Gap}(K_{v^{\prime}\mid
A_{j^{\prime}}})}\left[\log(2\epsilon^{-1})+\log(M-1)\right],$ (20)

we obtain $\tau_{v,j}(\epsilon,M)=\mathcal{O}(\text{poly}(d,\log(d)))$. Hence,
$NVt=\mathcal{O}^{*}(\text{poly}(d))$. That is, the values of $N$ and $t$
required to apply Theorem 1 grow at most polynomially in $d$.

##  6 Comparing SMC and Tempered MCMC

Throughout this section, we assume that the sequence of interpolating
distributions is a tempered sequence, i.e.,

$\displaystyle\mu_{v}(x)\propto\pi^{\beta_{v}}(x)\quad\text{ for
}\;0<\beta_{0}<\ldots<\beta_{V}=1,$ (21)

and that $\mu_{v}(x)/\mu_{v-1}(x)\leq ZW$. We let
$\pi^{\star}=\min_{j=1,\ldots,p}\pi(A_{j})$ and $K_{v|A_{j}}$ a restricted
kernel of the form (1).

Although population MC algorithms [15] such as SMC have been argued to perform
better on multimodal target distributions than existing MCMC algorithms, it is
reasonable to wonder whether the sequential, parallel nature of SMC plays a
role, or whether any such benefits are simply attributable to the use of the
distribution sequence (21). If the latter, then an MCMC algorithm that also
takes advantage of the same distribution sequence may be expected to succeed
(or fail) on the same problems where SMC succeeds (or fails). The following
results support this conjecture under fairly relaxed assumptions.

Ideally, we would like to show that the bounds on $N$ and $t$ in Theorem 1
grow at most polynomially in the problem size if and only if the parallel and
simulated tempering algorithms are rapidly mixing on the same problem. The
results below allow us to partially resolve the ‘if’ direction by relating the
lower bounds of [42] on the spectral gap of swapping chains to our results. To
formalize this, we first relate certain quantities defined in [42] to those
appearing in Theorem 1. Two key quantities appearing in the mixing time bounds
of Woodard, Schmidler and Huber [42] are the persistence and the overlap. The
following two propositions relate these quantities to the $\mu^{*}$ and $ZW$
quantities appearing in Theorem 1.

######  Proposition 2.

Define the _persistence_ [43] of partition $\mathcal{A}$ under distribution
sequence $\mu_{0},\ldots,\mu_{V}$ by

$\displaystyle\gamma(\mathcal{A})=\min_{j=1,\ldots,p}\prod^{V}_{v=1}\min\left\\{1,\frac{\mu_{v-1}(A_{j})}{\mu_{v}(A_{j})}\right\\}$
(22)

Then $\mu^{\star}>\gamma(\mathcal{A})\cdot\pi^{\star}$

###### Proof.

For any $v=0,\ldots,V$ and $j=1,\ldots,p$, we have that

$\displaystyle\mu_{v}(A_{j})$
$\displaystyle=\frac{\mu_{v}(A_{j})}{\mu_{v+1}(A_{j})}\cdot\frac{\mu_{v+1}(A_{j})}{\mu_{v+2}(A_{j})}\ldots\frac{\mu_{V-1}(A_{j})}{\mu_{V}(A_{j})}\cdot\pi(A_{j})\geq\gamma(\mathcal{A})\cdot\pi^{\star}$

Since this holds for any $v$ and $j$, it must hold for $\mu^{\star}$ as well.
∎

Controlling $\gamma(\mathcal{A})$ is critical to the success of the PT and ST
algorithms (see [43]). The quantity $\gamma(\mathcal{A})$ describes how the
measure of the partition elements of $\mathcal{A}$ ‘persists’ under tempering
of the target distribution $\pi$. There is a close relationship between
$\mu^{\star}$ and $\gamma(\mathcal{A})$. Recall that $\pi^{\star}$ decays at
most polynomially in $d$ by assumption. It follows that polynomial decay in
$\gamma(\mathcal{A})$ is enough to guarantee polynomial decay in $\mu^{\star}$
by Proposition 2.

######  Proposition 3.

Define the _overlap_ [42] for distribution sequence $\mu_{0},\ldots,\mu_{V}$
and partition $\mathcal{A}$ by

$\displaystyle\delta(\mathcal{A})=\min_{\begin{subarray}{c}v=0,\ldots,V-1\\\
j=1,\ldots,p\end{subarray}}\frac{\int_{A_{j}}\min\\{\mu_{v}(x),\mu_{v+1}(x)\\}dx}{\max\\{\mu_{v}(A_{j}),\mu_{v+1}(A_{j})\\}}$
(23)

Then,

$\displaystyle\delta(\mathcal{A})\geq\min\left\\{1,\frac{1}{ZW}\right\\}\cdot\gamma(\mathcal{A})\cdot\pi^{\star}$

###### Proof.

Since $\mu_{v}(x)/\mu_{v+1}(x)\geq 1/ZW$, it follows that for any
$v=0,\ldots,V-1$ and $j=1,\ldots,p$,

$\displaystyle\int_{A_{j}}\min\left\\{\mu_{v}(x),\mu_{v+1}(x)\right\\}dx$
$\displaystyle\geq\min\left\\{1,\frac{1}{ZW}\right\\}\cdot\mu_{v+1}(A_{j})\geq\min\left\\{1,\frac{1}{ZW}\right\\}\cdot\mu^{\star}$

The result follows by Proposition 2. ∎

The overlap $\delta(\mathcal{A})$ controls the rate at which temperature jumps
occur in the simulated tempering algorithm and lower bounds the probability of
swapping states at adjacent temperatures in the parallel tempering algorithm
(see [42]). By Proposition 3, if both $\gamma(\mathcal{A})$ and $(ZW)^{-1}$
decay at most polynomially in $d$, then the overlap decays at most
polynomially.

Both $\delta(\mathcal{A})$ and $ZW$ can often be controlled in practice by
decreasing the inverse temperature spacings. Conversely, $\gamma(\mathcal{A})$
and $\mu^{\star}$ are highly dependent on the chosen form of the interpolating
densities and are potentially problematic. For example, Woodard, Schmidler and
Huber [43] showed that $\gamma(\mathcal{A})$ decays exponentially for the
truncated Gaussian mixture model of Section 5.2 and for the mean field Pott’s
model, leading to torpid mixing of PT and ST in both cases.

Applying Proposition 2 and (19) allows us to restate Theorem 1 with
$\gamma(\mathcal{A})\cdot\pi^{\star}$ in place of $\mu^{\star}$ and the mixing
times bounded by $\text{Gap}(K_{v\mid A_{j}})^{-1}$:

######  Corollary 1.

Suppose $|f|\leq 1$ and (A1) holds. Let $\epsilon\in(0,\frac{1}{2})$ and
choose

  1. 1.

$N>\frac{1}{\epsilon^{2}}\cdot\max\left\\{3456\cdot\left(\frac{VWZ}{\pi^{\star}\gamma(\mathcal{A})}\right)^{2}\cdot\log(\frac{64Vp}{\pi^{\star}\gamma(\mathcal{A})}),\
p^{2}\cdot\log(1024p^{2})\right\\}$

  2. 2.

$t>\log\left(\frac{288NV}{\gamma(\mathcal{A})\pi^{\star}}\right)\cdot\left[\min_{\begin{subarray}{c}v=1,\ldots,V\\\
j=1,\ldots,p\end{subarray}}\textnormal{Gap}(K_{v|A_{j}})\right]^{-1}$

Then with probability at least $3/4$,

$\displaystyle\left|\frac{1}{N}\sum^{N}_{i=1}f(X^{i}_{V})-\frac{(1+\frac{\epsilon^{2}}{16})}{(1-\frac{\epsilon^{2}}{16})}\operatorname{\mathbb{E}}_{\pi}[f]\right|\leq\epsilon$

Comparing the complexity results for swapping chain algorithms (see Theorem
3.1 of [42]) to the bounds in Corollary 1, we make the following observations.
The dependence of $N$ on $\gamma(\mathcal{A})$ is quadratic (up to logarithmic
terms) in Corollary 1 rather than exponential in $\left|\mathcal{A}\right|$ as
in [42]. (This is similar to the results stated in [16], who proved a lower
bound on the spectral gap of a simulated tempering chain with quadratic
dependence on the minimum measure of a given partition (similar to
$\mu^{\star}$)). In addition, the dependence in Corollary 1 on the number of
temperatures $V$ is quadratic rather than quartic, and dependence on
$|\mathcal{A}|$ quadratic rather than cubic, compared to [42] (omitting
logarithmic terms). (Note that $\text{Gap}(K_{0})$ appears in the bound of
Woodard, Schmidler and Huber [42] but not in ours, but our assumption in
Section 2.1 that $\mu_{0}$ can be sampled efficiently is equivalent to
assuming $\text{Gap}(K_{0})$ decays at most polynomially.)

Unfortunately, we are currently unable to replace $\delta(\mathcal{A})$ in
Corollary 1 with $ZW$. Proposition 3 suggests that (at most) polynomial growth
of $ZW$ may be a stronger requirement than polynomial decay of
$\delta(\mathcal{A})$. This prevents us from concluding the ‘if’ direction of
our conjecture precisely. Nevertheless, we suspect that polynomial decay in
$(ZW)^{-1}$ and $\delta(\mathcal{A})$ can be guaranteed on many problems of
interest by decreasing the temperature spacings. We can summarize this
discussion with the following corollary.

######  Corollary 2.

Suppose $|f|\leq 1$, (A1) holds, and $\textnormal{Gap}(K_{v|A_{j}})$,
$\textnormal{Gap}(K_{0})$, $\gamma(\mathcal{A})$, $\pi^{\star}$, $(ZW)^{-1}$
decay at most polynomially in $d$ for
$v=1,\ldots,V=\mathcal{O}(\textnormal{poly}(d))$ and $j=1,\ldots,p$. Then

  1. 1.

The parallel and simulated tempering algorithms provide a polynomial time
$(\epsilon,\delta$)-randomized approximation for
$\operatorname{\mathbb{E}}_{\pi}[f]$.

  2. 2.

The SMC algorithm given in Section 2.1 provides a polynomial time
$(\epsilon,\delta$)-randomized approximation for
$\operatorname{\mathbb{E}}_{\pi}[f]$.

###### Proof.

This is a direct consequence of Corollary 1 and the results from [42], along
with the remarks regarding $\text{Gap}(K_{0})$ above. ∎

Corollary 2 says that if the parallel and simulated tempering algorithms
provide an efficient Monte Carlo approximation, then the SMC algorithm in
Section 2.1 will as well, up to the approximate equivalence of $(ZW)^{-1}$ and
$\delta(\mathcal{A})$ discussed above. (It is unclear at this time if the
latter distinction represents a meaningful difference in the algorithms, or
simply an artifact of different proof approaches.)

Concluding the ‘only if’ direction of our conjecture necessitates development
of lower bounds on SMC which are comparable to those in Woodard, Schmidler and
Huber [43]. This is of interest but beyond the scope of the current paper.

##  7 Conclusion

The upper bounds established in Theorem 1 demonstrate that SMC algorithms can
approximate global expectations using a polynomial number of Markov transition
steps without assuming globally mixing mutation kernels. These results can be
viewed as a generalization of those given in [24]: consider the special case
of $\mathcal{A}=\mathcal{X}$ so that $\mu^{\star}=1$ and $p=1$, then the
bounds stated in Theorem 1 differ from those in [24] only by a
$\mathcal{O}(V^{2})$ term appearing in the lower bound on $N$. To see why this
occurs, note that when the mutation kernels globally mix, $X^{1:N}_{v}$
couples to an i.i.d. sample from $\mu_{v}$ (see [24]). In this case,
controlling $\hat{P}^{j}_{v}$ is unnecessary, since
$N^{-1}\sum^{N}_{i=1}w_{v}(X^{i}_{v-1})$ always approximates $z_{v}/z_{v-1}$
for sufficiently large $N$ (conditional on the coupling event), regardless of
whether $\tilde{\mu}_{v-1}(A_{j})$ approximates $\mu_{v-1}(A_{j})$ well. That
is, globally mixing mutation kernels ‘correct’ for the bias of
$N^{-1}\sum^{N}_{i=1}w_{v}(X^{i}_{v-1})$ even if the resampling at step $v-1$
goes terribly wrong. When global mixing cannot be assumed, it is necessary to
control the trajectory of the resampling probability $\hat{P}^{j}_{v}$ across
steps $v=1,\ldots,V$ in order to obtain such a concentration result; the
$\mathcal{O}(V^{2})$ term represents the cost of doing so.

In Section 5 we applied our results to two well known example multimodal
problems: sampling from mixtures of log-concave distributions and the mean
field Ising model. We found that the total number of mutation steps $NVt$
required to apply Theorem 1 is comparable to bounds on the spectral gap given
in the literature for seemingly similar algorithms. We explored this
relationship further in Section 6 by comparing our results to those obtained
in [42] for the parallel and simulated tempering algorithms. Corollary 2
almost suggests that if the complexity results of [42] grow at a polynomial
rate in the problem size, then so do the lower bounds on $N$ and $t$ given in
Theorem 1. However, this conclusion cannot be made directly since we require
uniform bounds on the density ratios. Establishing lower bounds on $Nt$ to
obtain results comparable to Woodard, Schmidler and Huber [43] is also of
interest.

Finally, our results suggests that designing sequences of interpolating
distributions for multimodal target distributions is an important problem.
Indeed, Theorem 1 describes all of the properties such sequences should
possess. Namely, adjacent densities should be ‘close’ to control $ZW$ while
still ensuring $V$ polynomial in $d$, and modes should not be ‘lost’ to
control $\mu^{\star}$. Naturally $\mu_{0}$ must also be easy to sample from.
Unfortunately, finding such sequences is not straightforward. For example,
annealed sequences break down on seemingly simple problems such as Gaussian
mixtures with unequal scales (see [43] and [16]). The effect of distribution
sequence choice on the computational complexity of SMC is considered further
elsewhere [25].

## References

  * Beskos et al. [2013] [author] Beskos, A.A., Jasra, A.A., Kantas, N.N. and Thiery, A.A. (2013). On the Convergence of Adaptive Sequential Monte Carlo Methods. Annals of Applied Probability 26\.
  * Cappé et al. [2012] [author] Cappé, O.O., Guillin, A.A., Marin, J. M.J. M. and Robert, C. P.C. P. (2012). Population Monte Carlo. Journal of Computational and Graphical Statistics 13 907–929.
  * Chopin [2002] [author] Chopin, N.N. (2002). A sequential particle filter method for static models. Biometrika 89 539–551.
  * Chopin [2004] [author] Chopin, N.N. (2004). Central limit theorem for sequential Monte Carlo methods and its application to Bayesian inference. Annals of Statistics 32 2385–2411.
  * Del Moral, Doucet and Jasra [2006] [author] Del Moral, P.P., Doucet, A.A. and Jasra, A.A. (2006). Sequential Monte Carlo samplers. J. R. Stat. Soc 68 411–436.
  * Douc and Cappé [2005] [author] Douc, R.R. and Cappé, O.O. (2005). Comparison of resampling schemes for particle filtering. ISPA 2005. Proceedings of the 4th International Symposium on Image and Signal Processing and Analysis, 2005 64–69.
  * Douc and Moulines [2008] [author] Douc, R.R. and Moulines, E.E. (2008). Limit Theorems for Weighted Samples with Applications to Sequential Monte Carlo Methods. Annals of Statistics 36 2344–2376.
  * Durham and Geweke [2014] [author] Durham, G.G. and Geweke, J.J. (2014). Adaptive Sequential Posterior Simulators for Massively Parallel Computing Environments. Bayesian Model Comparison (Advances in Econometrics Vol. 34) 1–44.
  * Dwivedi et al. [2018] [author] Dwivedi, R.R., Chen, Y.Y., Wainwright, M.M. and Yu, B.B. (2018). Log-concave sampling: Metropolis-Hastings algorithms are fast! Proceedings of the 31st Conference On Learning Theory 75\.
  * Eberle and Marinelli [2010] [author] Eberle, A.A. and Marinelli, C.C. (2010). $L^{p}$ estimates for Feynman-Kac propagators with time-dependent reference measures. Journal of Mathematical Analysis and Applications 365 120–134.
  * Eberle and Marinelli [2013] [author] Eberle, A.A. and Marinelli, C.C. (2013). Quantitative approximations of evolving probability measures and sequential Markov chain Monte Carlo methods. Probability Theory and Related Fields 155 665–701.
  * Fearnhead and Taylor [2010] [author] Fearnhead, P.P. and Taylor, B.B. (2010). An Adaptive Sequential Monte Carlo Sampler. Bayesian Analysis 8 411–438.
  * Gelman et al. [2013] [author] Gelman, A.A., Carlin, J. B.J. B., Stern, H. S.H. S., Dunson, D. B.D. B., Vehtari, A.A. and Rubin, D. B.D. B. (2013). Bayesian Data Analysis, 3rd edition. Chapman & Hall/CRC.
  * Geyer [1991] [author] Geyer, C. J.C. J. (1991). Markov chain Monte Carlo maximum likelihood. Computing Science and Statistics: Proceedings of the 23rd Symposium on the Interface 23 156–163.
  * Jasra, Stephens and Holmes [2007] [author] Jasra, A.A., Stephens, D.D. and Holmes, C.C. (2007). On population-based simulation for static inference. Statistics and Computing 17 263–279.
  * Lee, Risteski and Ge [2018] [author] Lee, H.H., Risteski, A.A. and Ge, R.R. (2018). Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo. Adv. in NeurIPS 31 31\.
  * Levin, Peres and Wilmer [2009] [author] Levin, D. A.D. A., Peres, Y.Y. and Wilmer, E. L.E. L. (2009). Markov chains and Mixing Times. American Mathematical Society.
  * Lovász and Vempala [2006] [author] Lovász, L.L. and Vempala, S.S. (2006). Fast algorithms for logconcave functions: Sampling rounding, integration, and optimization. Proceedings of 47th Annual IEEE Symp. on Foundations of Computer Science 57–68.
  * Lovász and Vempala [2007] [author] Lovász, L.L. and Vempala, S.S. (2007). The geometry of logconcave functions and sampling algorithms. Random Structures & Algorithms 30 307–358.
  * Madras and Randall [2002] [author] Madras, N.N. and Randall, D.D. (2002). Markov Chain Decomposition for Convergence Rate Analysis. Annals of Applied Probability 12 581–606.
  * Madras and Zheng [2003] [author] Madras, N.N. and Zheng, Z.Z. (2003). On the swapping algorithm. Random Structures & Algorithms 22 67–97.
  * Mangoubi, Pillai and Smith [2021] [author] Mangoubi, O.O., Pillai, N.N. and Smith, A.A. (2021). Simple conditions for metastability of continuous Markov chains. Journal of Applied Probability 58 83–105.
  * Marinari and Parisi [1992] [author] Marinari, E.E. and Parisi, G.G. (1992). Simulated tempering: A new Monte Carlo scheme. Europhys. Lett. EPL 19 451–458.
  * Marion, Mathews and Schmidler [2021] [author] Marion, J.J., Mathews, J.J. and Schmidler, S.S. (2021). Finite Sample Complexities for Sequential Monte Carlo Estimators. arXiv:1803.09365 (Submitted for Publication).
  * Marion, Mathews and Schmidler [2022] [author] Marion, J.J., Mathews, J.J. and Schmidler, S.S. (2022). Finite Sample ${L}_{2}$ Bounds for Sequential Monte Carlo and Adaptive Path Selection. Under revision.
  * Metropolis et al. [1953] [author] Metropolis, N.N., Rosenbluth, A.A., Rosenbluth, M.M., Teller, A.A. and Teller, E.E. (1953). Equations of state calculations by fast computing machines. J. Chem. Phys. 21 1087–1092.
  * Neal [2001] [author] Neal, R.R. (2001). Annealed importance sampling. Statistics and Computing 11 125–139.
  * Neal [2011] [author] Neal, R.R. (2011). MCMC Using Hamiltonian Dynamics. Handbook of Markov Chain Monte Carlo, Ch. 5.
  * P., A and A. [2012] [author] P., Del MoralD. M., A, DoucetD. and A., JasraJ. (2012). On adaptive resampling strategies for sequential Monte Carlo methods. Bernoulli 18 252–278.
  * Paulin, Jasra and Thiery [2019] [author] Paulin, D.D., Jasra, A.A. and Thiery, A.A. (2019). Error bounds for sequential Monte Carlo samplers for multimodal distributions. Bernoulli 25 310–340.
  * Rudoy and Wolfe [2016] [author] Rudoy, D.D. and Wolfe, P. J.P. J. (2016). Monte Carlo Methods for Multi-Modal Distributions. 2006 Fortieth Asilomar Conference on Signals, Systems and Computers 2019–2023.
  * Salomone et al. [2018] [author] Salomone, R.R., South, L.L., Drovandi, C. C.C. C. and Kroese, D. P.D. P. (2018). Unbiased and Consistent Nested Sampling via Sequential Monte Carlo. arXiv: 1805.03924.
  * Schweizer [2011] [author] Schweizer, N.N. (2011). Non-asymptotic error bounds for sequential MCMC methods. PhD thesis, University of Bonn.
  * Schweizer [2012] [author] Schweizer, N.N. (2012). Non-asymptotic error bounds for sequential MCMC methods in multimodal settings. arXiv:1205.6733.
  * Tan [2015] [author] Tan, Z.Z. (2015). Resampling Markov Chain Monte Carlo Algorithms: Basic Analysis and Empirical Comparisons. Journal of Computational and Graphical Statistics 24 328–356.
  * Vempala [2005] [author] Vempala, S.S. (2005). Geometric random walks: A survey. Combinatorial and Computational Geometry.
  * Wan and Zabaras [2011] [author] Wan, J.J. and Zabaras, N.N. (2011). A Bayesian approach to multiscale inverse problems using the sequential Monte Carlo method. Inverse Problems 27\.
  * Wang, Machta and Katzgraber [2015] [author] Wang, W.W., Machta, J.J. and Katzgraber, H.H. (2015). Comparing Monte Carlo methods for finding ground states of Ising spin glasses: Population annealing, simulated annealing, and parallel tempering. Phys. Rev. E 92\.
  * Weigel et al. [2017] [author] Weigel, M.M., Barash, L. V.L. V., Borovsky, M.M., Janke, W.W. and Shchur, L. N.L. N. (2017). Population annealing: Massively parallel simulations in statistical physics. Journal of Physics: Conference Series 921\.
  * Weigel et al. [2021] [author] Weigel, M.M., Barash, L.L., Shchur and Janke, W.W. (2021). Understanding population annealing Monte Carlo simulations. Phys. Rev. E. 103\.
  * Whiteley [2012] [author] Whiteley, N.N. (2012). Sequential Monte Carlo samplers: error bounds and insensitivity to initial conditions. Stochastic Analysis and Applications 30 774–798.
  * Woodard, Schmidler and Huber [2009a] [author] Woodard, D.D., Schmidler, S.S. and Huber, M.M. (2009a). Conditions for rapid mixing of parallel and simulated tempering on multimodal distributions. Annals of Applied Probability 19 617–640.
  * Woodard, Schmidler and Huber [2009b] [author] Woodard, D.D., Schmidler, S.S. and Huber, M.M. (2009b). Sufficient Conditions for Torpid Mixing of Parallel and Simulated Tempering. Electronic Journal of Probability 14 780–804.
  * Wu, Schmidler and Y. [2021] [author] Wu, K.K., Schmidler, S.S. and Y., ChenC. (2021). Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Sampling. arXiv: 2109.13055.

##  Appendix A Appendix

In this section, we provide the construction of the coupled random variables
$\bar{X}^{1:N}_{v}$. Let $j\in\\{1,\ldots,p\\}$ and define

$\displaystyle\frac{dK^{t}_{v\mid
A_{j}}(x,\cdot)}{d\rho_{x}}:=f^{j}_{x}\qquad\qquad\frac{d\mu_{v\mid
A_{j}}}{d\rho_{x}}:=g_{x}^{j},$

where $\rho_{x}$ is some dominating measure. The subscript denotes the
implicit dependence on $x\in\mathcal{X}$, and the superscript denotes the
partition element $A_{j}$. Now, let $h^{j}_{x}=\min\\{g_{x}^{j},f^{j}_{x}\\}$
and set

$\displaystyle a^{j}_{x}=\int_{\mathcal{X}}h^{j}_{x}d\rho_{x},\ \
b^{j}_{x}=\int_{\mathcal{X}}(f^{j}_{x}-h^{j}_{x})d\rho_{x},\ \
c^{j}_{x}=\int_{\mathcal{X}}(g_{x}^{j}-h^{j}_{x})d\rho_{x}$

Each $\bar{X}^{i}_{v}$ is constructed independently according to the following
‘coupling map’ $C:\mathcal{X}\rightarrow\mathcal{X}\times\mathcal{X}$. Let
$Z^{i}_{v\mid j}$, $U_{v\mid j}^{i}$, and $V^{i}_{v\mid j}$ denote random
variables whose distributions have densities $h^{j}_{x}/a^{j}_{x}$,
$(f^{j}_{x}-h^{j}_{x})/b_{x}$, and $(g_{x}^{j}-h^{j}_{x})/c^{j}_{x}$,
respectively, for $j\in 1,\ldots,p$. The map $C$ transitions
$\tilde{X}^{i}_{v}$ to $(X^{i}_{v},\bar{X}^{i}_{v})$ as follows

  1. 1.

Independently draw $Z^{i}_{v\mid\xi^{i}_{v}}$, $U^{i}_{v\mid\xi^{i}_{v}}$, and
$V^{i}_{v\mid\xi^{i}_{v}}$.

  2. 2.

Set
$(X^{i}_{v},\bar{X}^{i}_{v})=(Z^{i}_{v|\xi^{i}_{v}},Z^{i}_{v\mid\xi^{i}_{v}})$
with probability $a^{\xi^{i}_{v}}_{\tilde{X}^{i}_{v}}$. Else, set
$(X^{i}_{v},\bar{X}^{i}_{v})=(U^{i}_{v|\xi^{i}_{v}},V^{i}_{v\mid\xi^{i}_{v}})$.

Then for $x\in A_{j}$ we have

$\displaystyle\operatorname{\mathbb{P}}(C(x)\in B\times\mathcal{X})$
$\displaystyle=\operatorname{\mathbb{P}}(U^{i}_{v\mid j}\in
B\,\cap\,V^{i}_{v\mid
j}\in\mathcal{X})(1-a^{j}_{x})+\operatorname{\mathbb{P}}(Z^{i}_{v\mid j}\in
B\,\cap\,\mathcal{X})a^{j}_{x},$
$\displaystyle=\operatorname{\mathbb{P}}(U^{i}_{v\mid j}\in
B)\operatorname{\mathbb{P}}(V^{i}_{v\mid
j}\in\mathcal{X})(1-a^{j}_{x})+\operatorname{\mathbb{P}}(Z^{i}_{v\mid j}\in
B)a^{j}_{x}$ $\displaystyle=K^{t}_{v\mid A_{j}}(x,B)$

and similarly, for $x\in A_{j}$ we have that
$\operatorname{\mathbb{P}}(C(x)\in\mathcal{X}\times B)=\mu_{v\mid A_{j}}(B)$.

We see then have that the new state $(X^{i}_{v},\bar{X}^{i}_{v})$ satisfies

$\displaystyle\operatorname{\mathbb{P}}(X^{i}_{v}\in B\mid\tilde{X}^{i}_{v}\in
A_{j})=\int_{\mathcal{X}}\tilde{\mu}_{v|A_{j}}(dx)K_{v|A_{j}}^{t}(x,B)=\hat{\mu}_{v\mid
A_{j}}(B)$

and $\bar{\mu}_{v}(B\mid\tilde{X}_{v}^{i}\in
A_{j})=\operatorname{\mathbb{P}}(\bar{X}^{i}_{v}\in B\mid\tilde{X}^{i}_{v}\in
A_{j})=\mu_{v\mid A_{j}}(B)$. By the law of total probability, it follows that
$\mathcal{L}(X^{i}_{v})=\hat{\mu}_{v}$. That is, even though the constructions
are performed conditionally on $\\{\tilde{X}^{i}_{v}\in A_{j}\\}$, the
marginal law of $X^{i}_{v}$ is preserved. However, note that this does not
apply to coupled variable $\bar{X}_{v}^{i}$; that is, marginally
$\mathcal{L}(\bar{X}^{i}_{v})\neq\mu_{v}$ since in general
$\operatorname{\mathbb{P}}(\tilde{X}^{i}_{v}\in A_{j})\neq\mu_{v}(A_{j})$.
Instead we have

$\mathcal{L}(\bar{X}^{i}_{v})=\sum_{j=1}^{p}\mu_{v\mid
A_{j}}\operatorname{\mathbb{P}}(\tilde{X}^{i}_{v}\in
A_{j})\neq\sum_{j=1}^{p}\mu_{v\mid A_{j}}\mu_{v}(A_{j})=\mu_{v}.$ (24)

Note also that by construction,
$\operatorname{\mathbb{P}}(X^{i}_{v}=\bar{X}^{i}_{v}\mid\tilde{X}^{i}_{v}\in
A_{j})=\|\hat{\mu}_{v\mid A_{j}}(\cdot)-\mu_{v\mid
A_{j}}(\cdot)\|_{\text{TV}}$.

The next lemma shows that the random variables produced by $C$ satisfy certain
useful conditional independencies.

######  Lemma 8.

Let $[-i]=\\{1,\ldots,i-1,i+1,\ldots,N\\}$. For $i=1,\ldots,N$ we have:

  1. (a)

$\bar{X}^{i}_{v}\operatorname{\perp\\!\\!\\!\perp}\tilde{X}^{[-i]}_{v}\mid\tilde{X}^{i}_{v}$

  2. (b)

$\bar{X}^{i}_{v}\operatorname{\perp\\!\\!\\!\perp}\bar{X}^{[-i]}_{v}\mid\tilde{X}^{i}_{v}$

  3. (c)

$\bar{X}^{i}_{v}\operatorname{\perp\\!\\!\\!\perp}(X^{1:N}_{k},\tilde{X}^{1:N}_{k})^{v-1}_{k=1}\mid\tilde{X}^{i}_{v}$

###### Proof.

Let
$W^{i}_{v}=(Z^{i}_{v\mid\xi^{i}_{v}},\,U^{i}_{v\mid\xi^{i}_{v}},\,V^{i}_{v\mid\xi^{i}_{v}})$.
All three statements follow immediately from the fact that

$\displaystyle
W^{i}_{v}\,\operatorname{\perp\\!\\!\\!\perp}\,W^{[-i]}_{v}\mid\tilde{X}^{i}_{v}$

for $i=1,\ldots,N$. That is, $Z^{i}_{v\mid\xi^{i}_{v}}$ ,
$U^{i}_{v\mid\xi^{i}_{v}}$, and $V^{i}_{v\mid\xi^{i}_{v}}$ are, by
construction, drawn independently of
$((W^{1:N}_{k},\tilde{X}^{1:N}_{k})^{v-1}_{k=1},W^{[-i]}_{v},\tilde{X}^{[-i]}_{v})$
conditional on $\tilde{X}^{i}_{v}$ for each $i=1,\ldots,N$. ∎

Since the constructions are performed conditional on the event
$\tilde{X}^{i}_{v}\in A_{j}$, the $\bar{X}^{1:N}_{v}$ random variables are
conditionally independent but not marginally independent; this is because the
$\tilde{X}^{1:N}_{v}$ random variables are dependent. Nonetheless, we can
still refine Lemma 8(c) slightly as follows:

######  Lemma 9.

For $B\subset\mathcal{X}$,

$\displaystyle\operatorname{\mathbb{P}}(\bar{X}^{i}_{v}\in
B\mid\mathcal{F}_{v-1},\tilde{X}^{i}_{v}\in
A_{j})=\operatorname{\mathbb{P}}(\bar{X}^{i}_{v}\in B\mid\tilde{X}^{i}_{v}\in
A_{j})$

###### Proof.

$\displaystyle\operatorname{\mathbb{P}}(\bar{X}^{i}_{v}\in
B\mid\mathcal{F}_{v-1},\tilde{X}^{i}_{v}\in A_{j})$
$\displaystyle=\operatorname{\mathbb{E}}[\operatorname{\mathbb{P}}(\bar{X}^{i}_{v}\in
B\mid\tilde{X}^{i}_{v})\mid\mathcal{F}_{v-1},\tilde{X}^{i}_{v}\in A_{j}]$
$\displaystyle=\operatorname{\mathbb{E}}[\mu_{v\mid
A_{\xi^{i}_{v}}}(B)\mid\mathcal{F}_{v-1},\tilde{X}^{i}_{v}\in A_{j}]$
$\displaystyle=\mu_{v\mid A_{j}}(B)$
$\displaystyle=\operatorname{\mathbb{P}}(\bar{X}^{i}_{v}\in
B\mid\tilde{X}^{i}_{v}\in A_{j})$

The first equality follows by iterated expectations and Lemma 8(c), the second
by the definition of $C$, and the third since the expectation is constant upon
conditioning on $\tilde{X}^{i}_{v}\in A_{j}$. The final equality follows since
$\\{\tilde{X}^{i}_{v}\in A_{j}\\}=\\{\bar{X}^{i}_{v}\in A_{j}\\}$ by the
definition of $C$. ∎

The next result is a consequence of Lemma 9

######  Lemma 10.

Let $f:\mathcal{X}\rightarrow\mathbb{R}$ be a
$\operatorname{\mathbb{P}}$-measurable function. Then

$\displaystyle\operatorname{\mathbb{E}}[f(\bar{X}^{i}_{v})\mathbbm{1}_{A_{j}}(\bar{X}^{i}_{v})\mid\mathcal{F}_{v-1}]=\operatorname{\mathbb{E}}_{\mu_{v|A_{j}}}[f]\cdot\hat{P}^{j}_{v}$
(25)

In particular,

$\displaystyle\operatorname{\mathbb{E}}[\bar{w}^{j}_{v+1}|\mathcal{F}_{v-1}]=\frac{z_{v+1}}{z_{v}}\cdot\frac{\mu_{v+1}(A_{j})}{\mu_{v}(A_{j})}\cdot\hat{P}^{j}_{v}$
(26)

where
$\bar{w}^{j}_{v+1}=N^{-1}\sum^{N}_{i=1}w_{v+1}(\bar{X}^{i}_{v})\mathbbm{1}_{A_{j}}(\bar{X}_{v}^{i})$
as before.

Note that if we had $\bar{X}_{v-1}^{i}$ distributed exactly according to
$\mu_{v-1}$ then we would have
$\operatorname{\mathbb{E}}_{\mu_{v-1}}[w_{v}(\bar{X}_{v-1}^{i})\mathbbm{1}_{A_{j}}(\bar{X}_{v-1}^{i})]=\frac{z_{v}}{z_{v-1}}\mu_{v}(A_{j})$.
However, $\mathcal{L}(\bar{X}_{v-1}^{i})\neq\mu_{v-1}$ as noted by (24) above.
Lemma 10 says however that if the sample history
$\\{(\tilde{X}_{s}^{1:N},X_{s}^{1:N},\bar{X}_{s}^{1:N})\\}_{s=1}^{v-2}$
satisfies conditions (6-8) for steps $1,\ldots,v-2$, the sample estimator
$\bar{w}_{v}^{j}$ of this quantity is unbiased up to a multiplicative error
$\hat{P}_{v-1}^{j}/\mu_{v-1}(A_{j})$ introduced by the fact that the marginal
probability of resampling into $A_{j}$ at step $v-1$ is $\hat{P}_{v-1}^{j}$
rather than exactly $\mu_{v-1}(A_{j})$.

###### Proof.

We show (25) for the case of $f(\cdot)=w_{v+1}(\cdot)$; the argument for the
general case is identical. The result (26) follows by linearity of
expectation.

Assume that $\hat{P}^{j}_{v}\neq 0$, otherwise the result holds trivially
since this implies
$\operatorname{\mathbb{E}}[\bar{w}^{j}_{v+1}|\mathcal{F}_{v-1}]=0=\hat{P}^{j}_{v}$
(recall the events $\tilde{X}_{v}^{i}\in A_{j}$ and $\bar{X}_{v}^{i}\in A_{j}$
are equivalent). Then we compute that

$\displaystyle\operatorname{\mathbb{E}}[w_{v+1}(\bar{X}^{i}_{v})\mathbbm{1}_{\bar{X}^{i}_{v}\in
A_{j}}\mid\mathcal{F}_{v-1}]$ $\displaystyle=$
$\displaystyle\operatorname{\mathbb{E}}[w_{v+1}(\bar{X}^{i}_{v})\mid\mathcal{F}_{v-1},\tilde{X}^{i}_{v}\in
A_{j}]\operatorname{\mathbb{P}}(\tilde{X}^{i}_{v}\in A_{j}|\mathcal{F}_{v-1})$
$\displaystyle=$
$\displaystyle\operatorname{\mathbb{E}}[w_{v+1}(\bar{X}^{i}_{v})\mid\tilde{X}^{i}_{v}\in
A_{j}]\operatorname{\mathbb{P}}(\tilde{X}^{i}_{v}\in A_{j}|\mathcal{F}_{v-1})$
$\displaystyle=$
$\displaystyle\frac{z_{v+1}}{z_{v}}\frac{\mu_{v+1}(A_{j})}{\mu_{v}(A_{j})}\left[\frac{\sum^{N}_{i=1}w_{v}(X^{i}_{v-1})\mathbbm{1}_{X^{i}_{v-1}\in
A_{j}}}{\sum^{N}_{i=1}w_{v}(X^{i}_{v-1})}\right]$ $\displaystyle=$
$\displaystyle\frac{z_{v+1}}{z_{v}}\cdot\frac{\mu_{v+1}(A_{j})}{\mu_{v}(A_{j})}\cdot\hat{P}^{j}_{v}$

The second equality follows by Lemma 9. The third equality follows since
$\operatorname{\mathbb{P}}(\bar{X}^{i}_{v}\in B\mid\tilde{X}^{i}_{v-1}\in
A_{j})=\bar{\mu}_{v}(B\mid\tilde{X}^{i}_{v-1}\in A_{j})=\mu_{v|A_{j}}(B)$ by
the definition of $C$. ∎

We conclude with the following concentration bound, which is a consequence of
the results derived so far.

######  Lemma 11.

Let $f:\mathcal{X}\rightarrow(a,b)$ be a
$\operatorname{\mathbb{P}}$-measurable bounded function and
$\bar{f}=N^{-1}\sum^{N}_{i=1}f(\bar{X}^{i}_{v})$. Then for $\lambda>0$,

$\operatorname{\mathbb{P}}\left(\left|\bar{f}-\operatorname{\mathbb{E}}[\bar{f}\mid\mathcal{F}_{v-1}]\right|>\lambda\right)\leq
4e^{-\frac{N\lambda^{2}}{2(b-a)^{2}}}$

###### Proof.

Note that
$\operatorname{\mathbb{E}}[\bar{f}\mid\mathcal{F}_{v-1}]=\operatorname{\mathbb{E}}[\operatorname{\mathbb{E}}[\bar{f}\mid\tilde{X}^{1:N}_{v}]\mid\mathcal{F}_{v-1}]$
by Lemma 8. Applying the triangle inequality and the union bound gives

$\displaystyle\operatorname{\mathbb{P}}\left(\left|\bar{f}-\operatorname{\mathbb{E}}[\bar{f}\mid\mathcal{F}_{v-1}]\right|>\lambda\right)$
$\displaystyle\leq$
$\displaystyle\operatorname{\mathbb{P}}\left(\left|\bar{f}-\operatorname{\mathbb{E}}[\bar{f}\mid\tilde{X}^{1:N}_{v}]\right|>\frac{\lambda}{2}\right)+\operatorname{\mathbb{P}}\left(\left|\operatorname{\mathbb{E}}[\bar{f}\mid\tilde{X}^{1:N}_{v}]-\operatorname{\mathbb{E}}[\operatorname{\mathbb{E}}[\bar{f}\mid\tilde{X}^{1:N}_{v}]\mid\mathcal{F}_{v-1}]\right|>\frac{\lambda}{2}\right),$

Notice that

$\displaystyle\operatorname{\mathbb{E}}[\bar{f}\mid\tilde{X}^{1:N}_{v}]=\operatorname{\mathbb{E}}\left[\frac{1}{N}\sum^{N}_{i=1}f(\bar{X}^{i}_{v})\Bigm{|}\tilde{X}^{1:N}_{v}\right]=\frac{1}{N}\sum^{N}_{i=1}\operatorname{\mathbb{E}}[f(\bar{X}^{i}_{v})\mid\tilde{X}^{i}_{v}]$
(27)

where the second equality follows by Lemma 8. Since
$\bar{X}^{1}_{v}\operatorname{\perp\\!\\!\\!\perp}\ldots\operatorname{\perp\\!\\!\\!\perp}\bar{X}^{N}_{v}\mid\tilde{X}^{1:N}_{v}$
by Lemma 8, the first term can be controlled by the conditional form of
Hoeffding’s inequality:

$\displaystyle\operatorname{\mathbb{P}}\left(\left|\bar{f}-\operatorname{\mathbb{E}}[\bar{f}\mid\tilde{X}^{1:N}_{v}]\right|>\frac{\lambda}{2}\right)$
$\displaystyle=\operatorname{\mathbb{E}}\left[\operatorname{\mathbb{P}}\left(\left|\bar{f}-\operatorname{\mathbb{E}}[\bar{f}\mid\tilde{X}^{1:N}_{v}]\right|>\frac{\lambda}{2}\Bigm{|}\tilde{X}^{1:N}_{v}\right)\right]$
$\displaystyle=\operatorname{\mathbb{E}}\left[\operatorname{\mathbb{P}}\left(\left|\sum^{N}_{i=1}\left(f(\bar{X}^{i}_{v})-\operatorname{\mathbb{E}}[f(\bar{X}^{i}_{v})\mid\tilde{X}^{1:N}_{v}]\right)\right|>\frac{N\lambda}{2}\Bigm{|}\tilde{X}^{1:N}_{v}\right)\right]$
$\displaystyle\leq 2e^{-\frac{N\lambda^{2}}{2(b-a)^{2}}}$

Next, note that the random variable
$\operatorname{\mathbb{E}}[f(\bar{X}^{i}_{v})\mid\tilde{X}^{i}_{v}]$ is also a
bounded function of $\tilde{X}^{i}_{v}$. But we always have that
$\tilde{X}^{1}_{v}\operatorname{\perp\\!\\!\\!\perp}\ldots\operatorname{\perp\\!\\!\\!\perp}\tilde{X}^{N}_{v}\mid\mathcal{F}_{v-1}$,
so we can reapply an identical argument using the conditional version of
Hoeffding’s inequality:

$\displaystyle\operatorname{\mathbb{P}}\left(\left|\sum^{N}_{i=1}\left(\operatorname{\mathbb{E}}[f(\bar{X}^{i}_{v})\mid\tilde{X}^{i}_{v}]-\operatorname{\mathbb{E}}[\,\operatorname{\mathbb{E}}[f(\bar{X}^{i}_{v})\mid\tilde{X}^{i}_{v}]\mid\mathcal{F}_{v-1}]\right)\right|>\frac{N\lambda}{2}\right)\leq
2e^{-\frac{N\lambda^{2}}{2(b-a)^{2}}}$

It follows that

$\displaystyle\operatorname{\mathbb{P}}\left(\left|\bar{f}-\operatorname{\mathbb{E}}[\bar{f}|\mathcal{F}_{v-1}]\right|>\lambda\right)\leq
4e^{-\frac{N\lambda^{2}}{2(b-a)^{2}}}$

∎