Convergence Analysis of Schrödinger-Föllmer Sampler without Convexity

Sampling from possibly unnormalized distributions is an import task in Bayesian statistics and machine learning. Ever since the Metropolis-Hastings (MH) algorithm [32, 25] was introduced, various random sampling methods were proposed, including Gibbs sampler, random walk sampler, independent sampler, Lagevin sampler, bouncy particle sampler, zig-zag sampler [23, 22, 37, 29, 35, 4, 2], among others, see [5, 14] and the references therein. The above mentioned sampling algorithms generate random samples by running an ergodic Markov chain whose stationary distribution is the target distribution.

In [26], the Schrödinger-Föllmer sampler (SFS), a novel sampling approach without requiring the property of ergodicity is proposed. SFS is based on the Schrödinger-Föllmer diffusion process, defined as

where the drift function

with $f(\cdot)=\frac{d\mu}{dN\left(0,\mbox{\bf I}_{p}\right)}(\cdot)$. According to [28] and [18], the process $\{X_{t}\}_{t\in[0,1]}$ in (1) was first formulated by Föllmer [19, 20, 21] when studying the Schrödinger bridge problem [36]. The main feature of the above Schrödinger-Föllmer process is that it interpolates $\delta_{0}$ and the target $\mu$ in time $[0,1]$, i.e., $X_{1}\sim\mu$, see Proposition 1. SFS samples from $\mu$ via the following Euler-Maruyama discretization of (1),

where $s=1/K$ is the step size, $t_{k}=sk$, and $\{\epsilon_{k}\}_{k=1}^{K}$ are independent and identically distributed from $N(0,\mbox{\bf I}_{p})$. If the expectations in the drift term $b(x,t)$ do not have analytical forms, one can use Monte Carlo method to evaluate $b\left(Y_{t_{k}},t_{k}\right)$ approximately, i.e., one can sample from $\mu$ according

where $\tilde{b}_{m}(\widetilde{Y}_{t_{k}},t_{k})=\frac{\frac{1}{m}\sum_{j=1}^{m}[\nabla f(\widetilde{Y}_{t_{k}}+\sqrt{1-t_{k}}Z_{j})]}{\frac{1}{m}\sum_{j=1}^{m}[f(\widetilde{Y}_{t_{k}}+\sqrt{1-t_{k}}Z_{j})]}$ with $Z_{1},...Z_{m}$ i.i.d $N(0,\mbox{\bf I}_{p})$. The numerical simulations in [26] demonstrate that SFS outperforms the exiting samplers based on egordicity.

In Section 4.2 of [26], they prove that

under a restricted assumption that the potential $U(x,t)$ is uniformly strongly convex, i.e.,

where $M$ is one finite and positive constant. In this paper we provide a new analysis of the above SFS iteration. We establish a nonasymptotic error bound on $W_{2}(\mbox{Law}(\widetilde{Y}_{t_{K}}),\mu)$ under the condition that $f$ and $\nabla f$ are Lipschitz continuous and $f$ has positive lower bound, but without using the uniformly strongly convexity requirement (2).

The rest of this paper is organized as follows. In Section 2, we recall the SFS method. In Section 3, we present our theoretical analysis. We conclude in Section 4. Proofs for all the theorems are provided in Appendix A.

In this section we recall the Schrödinger-Föllmer sampler briefly. More backgrounds on the Schrödinger-Föllmer diffusion process please see [10, 28, 7, 26].

Let $\mu\in\mathcal{P}\left(\mathbb{R}^{p}\right)$ be the target distribution and absolutely continuous with respect to the $p$-dimensional standard normal measure $G=N(0,\mbox{\bf I}_{p})$. Let

We assume that

• $(\textbf{A1})$

  $f,\nabla f$ are Lipschitz continuous with constant $\gamma$,

• $(\textbf{A2})$

  There exists $\xi>0$ such that $f\geq\xi$.

Define the heat semigroup $Q_{t},t\in[0,1]$ as

Proposition 1 shows that the Schrödinger-Föllmer diffusion will transport $\delta_{0}$ to the target $\mu$ on the unite time interval. Since drift term $b(x,t)$ is scale-invariant with respect to $f$ in the sense that $b(x,t)=\nabla\log Q_{1-t}Cf(x),\forall C>0$. Therefore, the Schrödinger-Föllmer diffusion can be used for sampling from $\mu(dx)=\exp(-V(x))dx/C$, where the normalizing constant of $C$ may not to be known. To this end, we use the Euler-Maruyama method to discretize the Schrödinger-Föllmer diffusion (3). Let

the Euler-Maruyama scheme reads

where $\{\epsilon_{k}\}_{k=1}^{K}$ are i.i.d. $N(0,\mbox{\bf I}_{p})$ and

From the definition of $b(Y_{t_{k}},t_{k})$ in (5) we may not get its explicit expression. Here, we can get one estimator $\tilde{b}_{m}$ of $b$ by replacing $\mathbb{E}_{Z}$ in $b$ with $m$-sample mean, i.e.,

or

where $Z_{1},\ldots,Z_{m}$ are i.i.d. $N(0,\mbox{\bf I}_{p})$. The detailed description of SFS is summarized in following Algorithm 1 below, which is Algorithm 2 in [26].

In Section 4.2 of [26], they proved that

under a restricted assumption that the potential is uniformly strongly convex, i.e, $U(x,t)$ satisfies (2). However, (2) is not easy to verify. In the next section, we establish a nonasymptotic bound on the Wasserstein distance between the law of $\widetilde{Y}_{t_{K}}$ generated by SFS (Algorithm 1) and the target $\mu$ under smooth and bounded conditions (A1) and (A2) but without using the strongly uniform convexity assumption (2) on $U(x,t)$.

Under conditions (A1) and (A2), one can easily deduce the growth condition and Lipschitz/Hölder continuity of the drift term $b(x,t)$ [26], i.e.,

and

and

where $C_{0}$ and $C_{1}$ are two finite and positive constants.

Let $\mathcal{D}(\nu_{1},\nu_{2})$ be the collection of coupling probability measures on $\left(\mathbb{R}^{2p},\mathcal{B}(\mathbb{R}^{2p})\right)$ such that its respective marginal distributions are $\nu_{1}$ and $\nu_{2}$. The Wasserstein of order $d\geq 1$ with which we measure the discrepancy between $\mbox{Law}(\widetilde{Y}_{t_{K}})$ and $\mu$ is defined as

In Theorem 2 and Theorem 3, we use (A2), i.e, $f$ has positive lower bound, however, (A2) may not hold if the target distribution admits compact support. To circumvent this difficulty, we consider the regularized probability measure

The corresponding density ratio is

Obviously, $f_{\varepsilon}$ satisfies (A1) and (A2) if $f$ and $\nabla f$ are Lipschitz continuous. Since $\mu_{\varepsilon}$ can approximate to $\mu$ well if we set $\varepsilon$ small enough, then we consider sampling from $\mu_{\varepsilon}$ by running SFS (Algorithm 1) with $f$ being replaced by $f_{\varepsilon}$. We use $\widetilde{Y}_{t_{K}}^{\varepsilon}$ to denote the last iteration of SFS.

In [26], Schrödinger-Föllmer sampler (SFS) was proposed for sampling from possibly unnormalized distributions. The key feature of SFS is that it does not need ergodicity as its theoretical basis. The consistency of SFS proved in [26] relies a restricted assumption that the potential function is uniformly strongly convex. In this paper we provide a new convergence analysis of the SFS without the strongly convexity condition on the potential. We establish a nonasymptotic error bound on Wasserstein distance between the law of the output of SFS and the target distribution under smooth and bounded assumptions on the density ratio of the target distribution over the standard normal distribution.

The authors would like to thank Professor Liming Wu at Université Clermont-Auvergne for helpful discussions on this topic.