Theoretical guarantees for sampling and inference in generative models with latent diffusions

Introduction and informal summary of results

Recently there has been much interest in using continuous-time processes to analyze discrete-time algorithms and probabilistic models (Wibisono et al., 2016; Li et al., 2017; Mandt et al., 2017; Chen et al., 2018; Yang et al., 2018). In particular, diffusion processes have been examined as a way towards a better understanding of first- and second-order optimization methods, as they afford an analysis of behavior over non-convex landscapes using a rich array of techniques from the mathematical physics literature (Li et al., 2017; Raginsky et al., 2017; Zhang et al., 2017). Gradient flows and diffusions have also found a role in the analysis of deep neural nets, where they are interpreted as describing the limiting case of infinitely many layers, with each layer being ‘infinitesimally thin’ (e.g., Chen et al. (2018); Li et al. (2018)). As in the case of optimization, continuous-time frameworks enable the use of a different set of tools for studying standard questions of relevance, such as sampling and inference, i.e., forward and backward passes through the network.

In this work, we consider a class of generative models where the latent object $X=\{X_{t}\}_{t\in}$ is a $d$-dimensional diffusion and the observable object $Y$ is a random element of some space $\mathsf{Y}$:

where (1.1a) is a $d$-dimensional Itô diffusion process whose drift $b(\cdot,\cdot;\theta)$ is a member of some parametric function class, such as multilayer feedforward neural nets, and (1.1b) prescribes an observation model for generating $Y$ conditionally on $X_{1}$. To the best of our knowledge, generative models of this form were first considered by Movellan et al. (2002) as a noisy continuous-time counterpart of recurrent neural nets. More recently, Hashimoto et al. (2016) and Ryder et al. (2018) investigated the use of discrete-time recurrent neural nets to approximate the population dynamics of biological systems that are classically modeled by diffusions. It is natural to view (1.1) as a continuum limit of deep generative models introduced by Rezende et al. (2014) — in fact, as we explain in Section 4, one can simulate a model of the above form using a deep generative model with a random number of layers. Alternatively, one can think of (1.1) as a neural stochastic differential equation, in analogy to the neural ODE framework of Chen et al. (2018).

There are three main questions that are natural to ask concerning the usefulness of such models: How expressive can they be? How might one sample from such a diffusion process? How might one perform inference on it? As our first contribution, we provide a unified view of sampling and inference through the lens of stochastic control. In particular, by adding a control $u_{t}$ to the drift of some reference diffusion, one can obtain a desired distribution at $t=1$, and the minimal-cost control that yields exact sampling is given by the so-called Föllmer drift (Föllmer, 1985; Dai Pra, 1991; Lehec, 2013; Eldan and Lee, 2018). Complementarily, we show that any control $u_{t}$ added to the drift $b(\cdot,t;\theta)$ in (1.1a) leads to a variational upper bound on the log-likelihood of a given tuple of observations $(y_{1},\ldots,y_{n})$. Variational inference then reduces to minimizing the expected control cost over a tractable class of controls. While we provide a unifying viewpoint that captures both sampling and inference, we emphasize that this is a synthesis of a number of existing results, and serves as a conceptual underpinning and motivation for our subsequent analysis. Specifically, after establishing that diffusion-based generative models can be effectively worked with, we explore their expressive power vis-à-vis neural nets: We show that, if the target density of $X_{1}$ can be efficiently approximated using a neural net, then the corresponding Föllmer drift can also be efficiently approximated by a neural net, such that the terminal law of the diffusion with this approximate drift is $\varepsilon$-close to the target density in Kullback–Leibler divergence. Finally, we investigate unbiased simulation methods for generative models with underlying diffusion processes and provide bounds on the variance of the resulting estimators.

To arrive at the unified perspective of sampling and inference, we begin by formulating a stochastic control problem that captures all of our desiderata: sampling from a target probability law $\mu$ at terminal time $t=1$; a set of tractable controls that might be used to take it there; and an appropriate notion of cost with that captures both the ‘control effort’ and the terminal cost that quantifies the discrepancy between the final probability law and the target measure $\mu$.

Our first result, stated in Theorem 2.1, is an explicit characterization of the value function of this control problem, which has a free-energy interpretation and can be understood from an information-theoretic viewpoint: the Kullback–Leibler divergence between the law of the path of the uncontrolled diffusion and that of the path of the controlled diffusion is the expected total work done by the control. The negative free energy with respect to the uncontrolled process is a lower bound on that of the controlled process after accounting for the work done, and equality is achieved by the optimal control. As pointed out above, this result is a synthesis of a number of existing results, and its main purpose is to motivate the use of controlled diffusions in probabilistic generative modeling.

Finally, we discuss the issue of unbiased simulation with the goal of estimating expected values of functions of $X_{1}$. The standard Euler–Maruyama scheme (Graham and Talay, 2013, Chap. 7) is straightforward, but produces a biased estimator. Typically, one uses Monte Carlo sampling to reduce the variance; if the estimator is biased, then the variance will be reduced by a factor of $N^{1-\delta}$ for some $\delta\in(0,1)$, instead of the optimal reduction by the factor of $N$, for $N$ Monte Carlo runs. One way to obtain an unbiased estimator is to employ a random discretization of the time interval $$, where the sampling times are generated by a point process on the real line. Unbiased simulation schemes of this type have been proposed and analyzed by Bally and Kohatsu-Higa (2015), Andersson and Kohatsu-Higa (2017), and Henry-Labordère et al. (2017). Our final result, Theorem 4.1, builds on the latter work and presents an unbiased, finite-variance simulation scheme. Conceptually, the simulation scheme can be thought of as a deep latent Gaussian model in the sense of Rezende et al. (2014), but with a random number of layers. Unfortunately, the variance of the resulting estimator can exhibit exponential dependence on dimension. We show why this is the case via an analysis of the moment-generating function of the point process used to generate the random mesh and propose alternatives to reduce the variance.

2 Notation

Exact sampling and variational inference: a unified stochastic control viewpoint

Before addressing the specific questions posed in the Introduction, we aim to demonstrate that both sampling and variational inference in generative models of the form (1.1) can be viewed through the lens of stochastic control. We give a brief description of the relevant ideas in Appendix A; the book by Fleming and Rishel (1975) is an excellent and readable reference.

Let $(\Omega,\mathcal{F},\{\mathcal{F}_{t}\},\mathbf{P})$ be a probability space with a complete and right-continuous filtration $\{\mathcal{F}_{t}\}$, and let $W=\{W_{t}\}$ be a standard $d$-dimensional Brownian motion adapted to $\{\mathcal{F}_{t}\}$. Consider the Itô diffusion process

and we say that a control $u^{*}\in\mathcal{U}$ is optimal if $J^{u^{*}}(x,t)=v(x,t)$ for all $x$ and $t$. The following theorem is, essentially, a synthesis of the results of Pavon (1989) and Dai Pra (1991):

Consider the control problem (2.4). The value function $v$ is given by

where $p_{s,t}(\cdot)$ is the transition density (2.2) of the uncontrolled process.

This result, proved in Appendix A, also admits an information-theoretic interpretation. Let $\mathbf{P}^{0}$ denote the probability law of the path $X_{}$ of the uncontrolled diffusion process (2.1) and let $\mathbf{P}^{u}$ denote the corresponding object for the controlled diffusion (2.3). Since $X$ and $X^{u}$ differ from each other by a change of drift, the probability measures $\mathbf{P}^{u}$ and $\mathbf{P}^{0}$ are mutually absolutely continuous, and the Radon–Nikodym derivative $\operatorname{d\!}\mathbf{P}^{u}/\operatorname{d\!}\mathbf{P}^{0}$ is given by the Girsanov formula (Protter, 2005)

where $u_{t}^{\hbox{\it\tiny T}}\operatorname{d\!}W_{t}\mathrel{\mathop{\mathchar 58\relax}}=\sum^{d}_{i=1}u_{i,t}\operatorname{d\!}W_{i,t}$, with $u_{i,\cdot}$ and $\operatorname{d\!}W_{i,\cdot}$ denoting the $i$th coordinates of $u$ and $W$ respectively. From (2.8), we can calculate the Kullback–Leibler divergence between $\mathbf{P}^{u}$ and $\mathbf{P}^{0}$:

Therefore, by Theorem 2.1, for any control $u\in\mathcal{U}$, we can write

with equality if and only if $u=u^{*}$. An inequality of this form holds more generally for real-valued measurable functions of the entire path $X_{}$ (Boué and Dupuis, 1998).

We will now demonstrate how both the problem of sampling and the problem of variational inference can be addressed via the above theorem.

2 Exact sampling: the Föllmer drift

Recall that, in the context of exact sampling, the objective is to construct a diffusion process $\{X_{t}\}_{t\in}$, such that $X_{1}$ has a given target distribution $\mu$. We will consider the case when $\mu$ is absolutely continuous with respect to the standard Gaussian measure $\gamma_{d}$ and let $f$ denote the Radon–Nikodym derivative $\operatorname{d\!}\mu/\operatorname{d\!}\gamma_{d}$. This problem goes back to a paper of Schrödinger (1931); for rigorous treatments, see, e.g., Jamison (1975), Föllmer (1985), Dai Pra (1991), Lehec (2013), Eldan and Lee (2018). The derivation we give below is not new (see, e.g., Dai Pra (1991, Thm. 3.1)), but the route we take is somewhat different in that we make the stochastic control aspect more explicit.

We take $b(x,t)\equiv 0$ and $X_{0}=0$ in (2.1). Then the diffusion process $\{X_{t}\}$ is simply the standard $d$-dimensional Brownian motion $\{W_{t}\}$, which has the Gaussian transition density

Now consider the control problem (2.4) with $g=f$. By Theorem 2.1, the value function $v$ is given by $v(x,t)=-\log\mathbf{E}[f(W_{1})|W_{t}=x]$, and can be computed explicitly. For $0\leq t<1$, we have

where $Q$ denotes the Euclidean heat semigroup (1.2). Hence, $v(x,t)=-\log Q_{1-t}f(x)$, and the optimal diffusion process $\{X^{*}_{t}\}$ has the drift $u^{*}(x,t)=-\nabla v(x,t)=\nabla\log Q_{1-t}f(x)$. Following Lehec (2013) and Eldan and Lee (2018), we will refer to $u^{*}$ as the Föllmer drift in the sequel.

Moreover, using the entropy inequality (2.10), we can show that the Föllmer drift is optimal in the following strong sense: Consider any control $u\in\mathcal{U}$ with $X^{u}_{0}=0$ and with the property that ${\rm Law}(X^{u}_{1})=\mu$. For any such control,

while clearly $\log\mathbf{E}[f(W_{1})]=0$. Therefore, it follows from (2.10) that, for any such control $u$,

with equality if and only if $u=u^{*}$. Thus, the Föllmer drift has the minimal ‘energy’ among all admissible controls that induce the distribution $\mu$ at $t=1$, and this energy is precisely the Kullback–Leibler divergence between $\mu$ and the standard Gaussian measure $\gamma_{d}$ (Dai Pra, 1991; Lehec, 2013; Eldan and Lee, 2018).

3 Variational inference

We now turn to the problem of variational inference. We are given an $n$-tuple of observations $\boldsymbol{y}=(y_{1},\ldots,y_{n})\in\mathsf{Y}^{n}$, and wish to upper-bound the negative log-likelihood

where $L(y;\theta)\mathrel{\mathop{\mathchar 58\relax}}=-\log\mathbf{E}[q(y|X_{1})]$ and $\{X_{t}\}$ is the diffusion process (1.1).

We take $b=b(\cdot,\cdot;\theta)$ in (2.1) and consider the control problem (2.4) with $g(x)=q(y|x)$ for some fixed $y\in\mathsf{Y}$. Then, by Theorem 2.1, any control $u\in\mathcal{U}$ gives rise to an upper bound on $L(y;\theta)$:

Expressiveness

Now that we have shown that generative models of the form (1.1) allow for both sampling and variational inference, we turn to the analysis of their expressiveness. Specifically, our objective is to show that, by working with a suitable structured class of drifts $b(\cdot,\cdot;\theta)$, we can achieve approximate sampling from a rich class of distributions at the terminal time $t=1$.

Let $\mu$ be the target probability measure for $X_{1}$. We assume that $\mu$ is absolutely continuous with respect to $\gamma_{d}$ and let $f$ denote the Radon–Nikodym derivative $\operatorname{d\!}\mu/\operatorname{d\!}\gamma_{d}$. From Section 2.2 we know that the diffusion process governed by the Itô SDE

with the Föllmer drift $b(x,t)=\nabla\log Q_{1-t}f(x)$ has the property that $\mu={\rm Law}(X_{1})$, and, moreover, it is optimal in the sense that it minimizes the ‘energy’ $\frac{1}{2}\int^{1}_{0}\mathbf{E}\|u_{t}\|^{2}\operatorname{d\!}t$ among all adapted drifts $\{u_{t}\}$ that result in distribution $\mu$ at time $t=1$. The main result of this section is as follows: If the Radon–Nikodym derivative $f$ can be approximated efficiently by multilayer feedforward neural nets, then, for any $\varepsilon>0$, there exists a drift $\widehat{b}(x,t)=\widehat{b}(x,t;\theta)$ that can be implemented exactly by a neural net whose parameters $\theta$ do not depend on time or space, and the terminal law $\widehat{\mu}\mathrel{\mathop{\mathchar 58\relax}}={\rm Law}(\widehat{X}_{1})$ of the diffusion process

is an $\varepsilon$-approximation to $\mu$ in the KL-divergence: $D(\mu\|\widehat{\mu})\leq\varepsilon$. Moreover, the size of the neural net that implements the approximate Föllmer drift $\widehat{b}$ can be estimated explicitly in terms of the size of a suitable approximating neural net for $f$.

We begin by imposing some assumptions on $f$. The first assumption is needed to guarantee enough regularity for the Föllmer drift:

The function $f$ is differentiable, both $f$ and $\nabla f$ are $L$-Lipschitz, and there exists a constant $c\in(0,1]$, such that $f\geq c$ everywhere.

We assume that the activation function $\sigma$ is differentiable and universal, in the sense that any univariate Lipschitz function which is nonconstant on a bounded interval can be approximated arbitrarily well by an element of $\mathcal{N}^{\sigma}_{2}$:

We also make the following assumption regarding approximability of $f$ by neural nets:

Typical results on neural net approximation are concerned with approximating a given function uniformly on a given compact set. By contrast, Assumption 3.3 requires uniform approximability of both $f$ and its gradient $\nabla f$ on a compact set by some neural net $\widehat{f}$ and its gradient $\nabla\widehat{f}$. Such simultaneous approximation guarantees can also be found in the literature, see, e.g., Hornik et al. (1990); Yukich et al. (1995); Li (1996). See Safran and Shamir (2017) for a discussion of various trade-offs between depth and width (maximum number of neurons per layer) in neural net approximation.

We are now in a position to state the main result of this section:

with the drift $\widehat{b}(x,t)=\widehat{v}(x,\sqrt{1-t})$, then $\widehat{\mu}\mathrel{\mathop{\mathchar 58\relax}}={\rm Law}(\widehat{X}_{1})$ satisfies $D(\mu\|\widehat{\mu})\leq\varepsilon$.

Let $\boldsymbol{\mu}\mathrel{\mathop{\mathchar 58\relax}}={\rm Law}(X_{})$ and $\widehat{\boldsymbol{\mu}}\mathrel{\mathop{\mathchar 58\relax}}={\rm Law}(\widehat{X}_{})$. The Girsanov formula gives

where the interchange of the integral and the expectation follows from Fubini’s theorem because both $b$ and $\widehat{b}$ are bounded by Lemma B.1 in Appendix B and (3.7). We now proceed to estimate the integrand. For each $t\in$,

where $T_{1}\leq\varepsilon$ by (3.6). To estimate $T_{2}$, we first observe that, since the Föllmer drift is bounded in norm by $L/c$ by Lemma B.1, we have

(Bubeck et al., 2018, Lemma 3.8). Therefore,

Choosing $R$ large enough to guarantee $T_{2}\leq\varepsilon$ and putting everything together, we obtain $D(\boldsymbol{\mu}\|\widehat{\boldsymbol{\mu}})\leq\varepsilon$. Therefore, $D(\mu\|\widehat{\mu})\leq D(\boldsymbol{\mu}\|\widehat{\boldsymbol{\mu}})\leq\varepsilon$ by the data processing inequality.

Unbiased simulation

In particular, for each $1\leq i\leq n+1$,

where $C_{g}(x)>0$ is some constant that depends on $g$ and on the starting point $x$ (Graham and Talay, 2013). Recently, several authors (Bally and Kohatsu-Higa, 2015; Andersson and Kohatsu-Higa, 2017; Henry-Labordère et al., 2017) have studied unbiased simulation of SDEs using Euler–Maruyama schemes with random partitions, where the partition breakpoints are generated by a Poisson point process on the real line. In this section, we build on this line of work and present a scheme for unbiased simulation in the context of generative models of the form (1.1) that uses random partitions generated by arbitrary renewal processes (Kallenberg, 2002, Chap. 9) with sufficiently well-behaved densities of interrenewal times. Our analysis closely follows that of Henry-Labordère et al. (2017), but we provide a more refined analysis of the variance of the resulting estimators.

We first describe the simulation procedure. In what follows, we will drop the index $\theta$ from the drift to keep the notation clean. Let $\tau_{1},\tau_{2},\ldots$ be i.i.d. nonnegative random variables with an absolutely continuous distribution whose support contains the interval $[0,1+\varepsilon]$ for some $\varepsilon>0$. Let $F_{\tau}$ and $f_{\tau}$ denote the cdf and the pdf of $\tau_{1}$. Let $T_{0}=0$ and

Define a process $\widehat{X}=\{\widehat{X}_{t}\}_{t\in}$ with $\widehat{X}_{0}=x$ as the Euler–Maruyama scheme (4.1) on the random partition $0=T_{0}<T_{1}<\ldots<T_{N}<T_{N+1}\equiv 1$ of $$, and let

This process can be interpreted as a deep generative model in the sense of Rezende et al. (2014), but with a random number of layers. Specifically, let $\xi_{1},\xi_{2},\ldots\stackrel{{\scriptstyle{\rm i.i.d.}}}{{\sim}}\gamma_{d}$ be independent of $\{\tau_{i}\}$, and define $\widehat{X}^{(0)},\widehat{X}^{(1)},\ldots,\widehat{X}^{(N+1)}$ recursively by taking $\widehat{X}^{(0)}=x$ and

where $\stackrel{{\scriptstyle{\rm d}}}{{=}}$ denotes equality of probability distributions. We are now ready to state our main result on unbiased simulation (see Appendix E for the proof):

Suppose that the drift $b(x,t)$ is uniformly bounded, Lipschitz in $x$, and $\frac{1}{2}$-Hölder in $t$, i.e., for some constants $b_{\infty}>0$ and $L_{b}>0$,

where $K={\rm poly}(|g(x)|,L_{b},L_{g},b_{\infty},d)$, $\kappa=\log{\rm poly}(C,L_{b},L_{g},b_{\infty},d)$, and $M_{N}(\theta)\mathrel{\mathop{\mathchar 58\relax}}=\mathbf{E}[\exp(\theta N)]$ is the moment-generating function of $N$.

For example, the type of drift used in the construction of Section 3 has the property (4.3). The key implication of Theorem 4.1 is that the variance of the estimator $\widehat{\psi}$ is controlled by the moment-generating function of $N$, and is therefore related to the tail behavior of the sums $S_{k}\mathrel{\mathop{\mathchar 58\relax}}=\sum^{k}_{i=1}\tau_{i}$. In some cases, one can calculate $M_{N}$ in closed form. For instance, if we take $\tau_{1},\tau_{2},\ldots\stackrel{{\scriptstyle{\rm i.i.d.}}}{{\sim}}{\rm Exp}(\lambda)$ for some $\lambda>0$, then the estimator (4.2) reduces to the one introduced by Henry-Labordère et al. (2017). Since $F_{\tau}(s)=1-e^{-\lambda s}$ and $f_{\tau}(s)=\lambda e^{-\lambda s}$ for $s\geq 0$, (4.4) holds with $C=1/\lambda$ and $a=\lambda$; moreover, $N\sim{\rm Pois}(\lambda)$ with

Thus, ${\rm Var}[\widehat{\psi}]$ grows like $\exp(d^{2})$, as already observed by Henry-Labordère et al. (2017). One way to reduce the variance is to choose the $\tau_{i}$’s with lighter tails. To see this, we need estimates of $\Lambda_{N}$; the following lemma provides a computable upper bound:

Let $M_{\tau}$ denote the moment-generating function of $\tau$. Then

As an example, suppose $\tau_{1},\tau_{2},\ldots$ are i.i.d. samples from the uniform distribution on $[0,T]$ for some $T>1$. Then

and it is a matter of straightforward but lengthy algebra to show that $M_{\tau}(-\beta)\leq e^{-2(\theta+1)}$ for all $\beta$ satisfying

Using this in (4.6) yields the estimate $M_{N}(\theta)\lesssim e^{{\rm poly}(\theta)}$. The density of a ${\rm Uniform}(0,T)$ random variable clearly satisfies (4.4). Thus, applying Theorem 4.1 to the estimator (4.2) with $\tau_{i}\stackrel{{\scriptstyle{\rm i.i.d.}}}{{\sim}}{\rm Uniform}(0,T)$, we see that its variance scales quasipolynomially in $d$, i.e., ${\rm Var}[\widehat{\psi}]\lesssim e^{{\rm polylog}(d)}$. However, choosing $\tau_{i}$’s with lighter tails will generally lead to larger values of $N$, i.e., a deeper generative model will be needed.

Appendix A The proof of Theorem 2.1

We first need some background on controlled diffusion processes, see, e.g., Fleming and Rishel (1975). As in Section 2, let $\mathcal{U}$ be the set of controls, where each $u\in\mathcal{U}$ defines a controlled diffusion governed by the Itô SDE

where $\mathcal{L}_{t}$ is the (time-varying) generator of the diffusion (2.1):

The PDE (A.2) is called the Bellman equation associated to the control problem (A.1).

In fact, the control (A.4) is optimal among a much wider class of adapted controls, i.e., all stochastic processes $\{u_{t}\}_{t\in}$ adapted to the filtration $\{\mathcal{F}_{t}\}$. The class $\mathcal{U}$ defined above consists of so-called Markov controls, where $u_{t}$ is a deterministic function of $X^{u}_{t}$ and $t$. In that case, the controlled diffusion $X^{u}$ is a Markov process.

We now turn to the proof of Theorem 2.1. The first step is to use the logarithmic transformation due to Fleming (1978); see also Fleming and Sheu (1985); Sheu (1991). Consider the function $h(x,t)\mathrel{\mathop{\mathchar 58\relax}}=\mathbf{E}[g(X_{1})|X_{t}=x]$. By the Feynman–Kac formula (Kallenberg, 2002, Thm. 24.1), this function is a $C^{2,1}$ solution of the Cauchy problem

It is a matter of simple calculus to verify that $v(x,t)=-\log h(x,t)$ solves the Cauchy problem

Moreover, using the variational representation

where the optimizer is given by $\alpha^{*}=-\nabla v$, it is readily verified that (A.6) is the Bellman equation (A.2) associated to the control problem (2.4). Hence, by the verification theorem, $v(x,t)=-\log h(x,t)$ is the value function we seek, and the optimal control is given by $u^{*}(x,t)=-\nabla v(x,t)$.

Since $h$ solves (A.5), the transition density of $\{X^{*}_{t}\}$ is given by (2.7) by a result of Jamison (1975) and Dai Pra (1991).

Appendix B Regularity properties of f𝑓f and the Föllmer drift

We first show that Assumption 3.1 holds for Gibbs measures

Likewise, the Lipschitz continuity of $\nabla f$ follows from the Lipschitz continuity of $\nabla F$: since $\nabla e^{-F}=-e^{-F}\nabla F$, we have

Finally, suppose that $F$ is also bounded from above, $F\leq a$ for some $a>0$. Then $f\geq c$ everywhere, where $0<c\leq 1$ because both $\mu$ and $\gamma_{d}$ are probability measures.

We will also need the following simple lemma:

Under Assumption 3.1, the Föllmer drift $b(x,t)=\nabla\log Q_{1-t}f(x)$ is bounded in norm by $L/c$ and is Lipschitz with Lipschitz constant $L/c+L^{2}/c^{2}$, where $L$ is the maximum of the Lipschitz constants of $f$ and $\nabla f$.

Appendix C Uniform approximation of the heat semigroup by a finite sum

In this appendix, we prove the following result, which is used in the proof of Theorem 3.2:

We gather some preliminaries first. We recall the definition of the Orlicz exponential norm of order $2$ (Giné and Nickl, 2016, Sec. 2.3): for a real-valued random variable $U$,

The $\psi_{2}$ norm dominates the $L^{2}$ norm $\|U\|_{2}\mathrel{\mathop{\mathchar 58\relax}}=(\mathbf{E}|U|^{2})^{1/2}$: $\|U\|_{2}\leq\|U\|_{\psi_{2}}$. A simple application of Markov’s inequality leads to the following tail bound:

Let $U=\|Z\|$, where $Z\sim\gamma_{d}$. Then $\|U\|_{\psi_{2}}\leq\sqrt{d}+\sqrt{6}$.

This implies that $\|\xi\|_{\psi_{2}}\leq\sqrt{6}$ (Giné and Nickl, 2016, Eq. (2.25)). Taking $F(Z)=U$ and using the triangle inequality, we obtain

where $\mathbf{E}U\leq\|U\|_{2}=\sqrt{d}$ by Jensen’s inequality. ∎

Let $U_{1},\ldots,U_{N}$, $N\geq 2$, be a collection of (possibly dependent) random variables with finite $\psi_{2}$ norms. Then we have the following maximal inequality:

which is a random variable under standard regularity assumptions on $\mathcal{G}$, such as separability. The expected supremum $\mathbf{E}\|P_{N}-P\|_{\mathcal{G}}$ is controlled by the covering numbers of $\mathcal{G}$. The $L^{2}(Q)$ covering numbers of $\mathcal{G}$ with respect to a probability measure $Q$ on $\mathsf{Z}$ are defined by

The Koltchinskii–Pollard $\varepsilon$-entropy of $\mathcal{G}$ is given by

where the supremum is over all probability measures $Q$ supported on finitely many points of $\mathsf{Z}$. Then we have the following bound on the expectation of $\|P_{N}-P\|_{\mathcal{G}}$ (Theorem 3.54 and Eq. (3.177) in Giné and Nickl (2016)):

Let $\mathcal{G}$ be a class of functions containing , such that

Let $Z_{1},\ldots,Z_{N}$ be i.i.d. copies of a random element $Z$ of $\mathsf{Z}$ with probability law $P$, such that $F\in L^{2}(P)$. Then

We also have the following generalization of Talagrand’s concentration inequality to unbounded classes of functions, due to Adamczak (2008) (see also Sec. 2.3 in Koltchinskii (2011)):

Let $\mathcal{G}$ be a class of real-valued functions on $\mathsf{Z}$ with envelope $F$. Then there exists an absolute constant $C>0$, such that, for any $\gamma>0$,

With these preliminaries out of the way, we have the following result:

with probability at least $1-e^{-\gamma}$.

Thus we can estimate the $L^{2}(Q)$ covering numbers of $\mathcal{G}$ by

where $(u)_{+}\mathrel{\mathop{\mathchar 58\relax}}=u\vee 0$, and therefore

where we have used the triangle inequality for $\|\cdot\|_{\psi_{2}}$, as well as the maximal inequality (C.3). Using the estimates (C.5), (C.6), and (C.7) in Adamczak’s inequality, we obtain (C.4). ∎

We are now ready to prove Theorem C.1. The proof is via the probabilistic method. Let $\varepsilon>0$ and $R>0$ be given, and choose

We will show that $\mathbf{P}\{E_{0}\cup E_{1}\cup E_{2}\}<1$, which will imply that there exists at least one realization of $Z_{1},\ldots,Z_{N}$ verifying the statement of the theorem.

By Lemma C.1, $U=\|Z\|$ satisfies $\|U\|_{\psi_{2}}\leq\sqrt{d}+\sqrt{6}$, and therefore $U^{*}_{N}\mathrel{\mathop{\mathchar 58\relax}}=\max_{n\leq N}U_{n}$ satisfies $\|U^{*}_{N}\|_{\psi_{2}}\leq\sqrt{32(d+6)\log N}$ by the maximal inequality (C.3). Consequently, it follows from (C.2) that

Moreover, since the function $f$ and all of its partial derivatives are $L$-Lipschitz, Lemma C.4 (with $\gamma=\log 4(d+1)$) and the union bound give $\mathbf{P}\{E_{1}\cup E_{2}\}\leq 1/4$. Therefore, $\mathbf{P}\{E_{0}\cup E_{1}\cup E_{2}\}\leq 1/2$.

Appendix D The proof of Theorem 3.2: uniform approximation of the Föllmer drift by a neural net

These approximations suffice for our purposes. However, if one uses the ReLU activation function $x\mapsto x\vee 0$, then both multiplication and reciprocals can be $\varepsilon$-approximated by neural nets with size and depth polylogarithmic in $1/\varepsilon$ (Yarotsky, 2017; Telgarsky, 2017).

which is a $2$-layer neural net with size $m\leq 8c_{\sigma}\frac{M^{2}}{\delta}+1$. Indeed, using the polarization identity $4xy=(x+y)^{2}-(x-y)^{2}$, we have

For approximating the reciprocal, consider the univarite function

which is $(1/a^{2})$-Lipschitz and constant outside of the interval $[-b,b]$. The existence of the function $q$ with the stated properties follows immediately from Assumption 3.2. ∎

can be computed by a neural net of size $N\cdot{\rm poly}(1/\delta,d,L,R)$, such that

where we have used the fact that $\delta\leq c/4$. Without loss of generality, we may assume that $L\geq 1$. Then, for any $x\in\mathsf{B}^{d}(R)$ and $t\in$,

where we have used Lemma B.1 to bound $\|\frac{\nabla Q_{t}f}{Q_{t}f}\|\leq L/c$. In other words, $\nabla\log\widehat{\varphi}(x,\sqrt{t})$ approximates $\nabla\log Q_{t}f(x)$ to accuracy $\varepsilon/2$ uniformly on $\mathsf{B}^{d}(R)\times$. It remains to approximate $\nabla\log\widehat{\varphi}(x,\sqrt{t})$ by a neural net to accuracy $\varepsilon/2$.

To that end, we first represent $\nabla\log\widehat{\varphi}(x,\sqrt{t})$ as a composition of several elementary operations and then approximate each step by a neural net. Specifically, the computation of $v_{i}=\partial_{i}\log\widehat{\varphi}(x,\sqrt{t})$ can be represented as a computation graph with the following structure:

Compute $a=\widehat{\varphi}(x,\sqrt{t})$.

Compute $b_{i}=\partial_{i}\widehat{\varphi}(x,\sqrt{t})$.

Given $x$ and $\sqrt{t}$, $a$ is computed by a neural net with activation function $\sigma$, of size ${\rm poly}(1/\delta,d,L,R)$ and depth ${\rm poly}(1/\delta,d,L,R)$. Therefore, by the cheap gradient principle (Lemma D.1), $b_{i}$ can be computed by a neural net of size ${\rm poly}(1/\delta,d,L,R)$, where the activation function of each neuron is an element of the set $\{\sigma,\sigma^{\prime}\}$. Next, since $a$ takes values in $[c/2,L(R+\sqrt{d})+f(0)+c/2]$, by Lemma D.2 the reciprocal $r=1/a$ can be computed to accuracy $\varepsilon/(4L\sqrt{d})$ by a $2$-layer neural net with activation function $\sigma$ and of size

Let $\widehat{r}$ denote the resulting approximation. Then, since $|b_{i}|\leq 2L$ and $|\widehat{r}|\leq 2/c+\varepsilon/(4L\sqrt{d})\leq 4/c$, by Lemma D.2 the product $\widehat{r}b_{i}$ can be approximated to accuracy $\varepsilon/4\sqrt{d}$ by a $2$-layer neural net with activation function $\sigma$ and with at most

neurons. The overall accuracy of approximation is

Appendix E Proof of Theorem 4.1

We follow the strategy of Henry-Labordère et al. (2017) and construct a sequence $\{\psi_{n}\}_{n\geq 0}$ of unbiased estimators, such that $\mathbf{E}[\psi_{n}]\xrightarrow{n\to\infty}\mathbf{E}[\psi]$, where $\psi\mathrel{\mathop{\mathchar 58\relax}}=\lim_{n\to\infty}\psi_{n}$. By a standard approximation argument, we can assume that $g$ is bounded and Lipschitz.

Let $\Delta^{T}_{k}\mathrel{\mathop{\mathchar 58\relax}}=T_{k}-T_{k-1}$ and $\Delta^{W}_{k}\mathrel{\mathop{\mathchar 58\relax}}=W_{T_{k}}-W_{T_{k-1}}$, for $k\geq 1$. For each $n\geq 0$, let

where $h(x,t)\mathrel{\mathop{\mathchar 58\relax}}=\mathbf{E}[g(X_{1})|X_{t}=x]$. We will show that $\mathbf{E}[\psi_{n}]=\mathbf{E}[g(X_{1})]$ for all $n$ and that the sequence $\{\psi_{n}\}_{n\geq 0}$ is uniformly integrable. Then it will follow from the dominated convergence theorem that

is also an unbiased estimator. Observe that the estimator $\widehat{\psi}$ defined in (C.2) differs from $\psi$: instead of $g(\widehat{X}_{1})$, we have $g(\widehat{X}_{1})-g(\widehat{X}_{N}){\mathbf{1}}_{\{N>0\}}$. Just as in Henry-Labordère et al. (2017), the term proportional to $g(\widehat{X}_{N}){\mathbf{1}}_{\{N>0\}}$ serves as a control variate to ensure that $\widehat{\psi}$ has finite variance. Indeed, since $\mathbf{E}[\Delta^{W}_{N+1}|T_{N}]=0$, it is easy to see that

and therefore $\mathbf{E}[\widehat{\psi}-\psi]=0$.

This process has the infinitesimal generator

Then, by Dynkin’s formula (Kallenberg, 2002, Lemma 19.21), for any $t\leq s\leq 1$,

and using this in (E.3), we obtain the formula

In particular, since $h(x,t)=\mathbf{E}[g(X_{1})|X_{t}=x]$ by the Feynman–Kac formula, we have

where $\mathbf{E}[M^{t}_{t}-M^{t}_{1}]=0$ since $M^{h,t}$ is a martingale.

Using Eq. (E.5) with $t=0$ and $v=v_{0}\mathrel{\mathop{\mathchar 58\relax}}=b(x,0)$, we have

Recalling that $T_{1}=\tau_{1}\wedge 1$ is independent of the Brownian motion $\{W_{t}\}$ and $\mathbf{P}[T_{1}\geq 1]=\mathbf{P}[\tau_{1}\geq 1]=1-F_{\tau}(1)$, we have

where the last equality follows from the fact that $T_{1}=\Delta^{T}_{1}\geq 1$ if and only if $N=0$.

Moreover, if we change the initial condition from $t=0,v=v_{0}$ to $t=T_{1},v=v_{1}\mathrel{\mathop{\mathchar 58\relax}}=b(\widehat{X}_{T_{1}},T_{1})$, then it follows from (E.9) that, conditionally on $(\widehat{X}_{T_{1}},T_{1})$, whenever $T_{1}<1$,

Substituting (E.10) into (E.8) and using the fact that the event $\{T_{1}<1\leq T_{2}\}$ is equivalent to $\{N=1\}$, we have $h(x,0)=\mathbf{E}[\psi_{1}]$. Repeating this procedure, we have

We claim that the sequence $\{\psi_{n}\}_{n\geq 0}$ is uniformly integrable. To see this, first observe that, for each $k$, $\mathbf{E}[\|\Delta^{W}_{k+1}\|||T_{k+1}]\leq(\Delta^{T}_{k+1}d)^{1/2}$. Then the uniform integrability follows from the boundedness of $b$, $g$, $\nabla h$, and from Lemma E.2 in Section E.3. Therefore, taking the limit as $n\to\infty$, we obtain

where the second equality follows from the dominated convergence theorem.

E.2 Variance

Let $L\mathrel{\mathop{\mathchar 58\relax}}=L_{b}\vee L_{g}$. For $1\leq k\leq N+1$, let $\Delta^{\widehat{X}}_{k}\mathrel{\mathop{\mathchar 58\relax}}=\widehat{X}_{T_{k+1}}-\widehat{X}_{T_{k}}$ denote the increments of $\widehat{X}$. Since $T_{N+1}=1$, we have

Using this and (4.4), we can upper-bound $\widehat{\psi}$ as follows:

Let $\mathcal{F}_{k}\mathrel{\mathop{\mathchar 58\relax}}=\sigma(T_{j},\widehat{X}_{j}\mathrel{\mathop{\mathchar 58\relax}}1\leq j\leq k)$. Then, since ${\rm Law}(\Delta^{W}_{k+1}|\mathcal{F}_{k})={\rm Law}((\Delta^{T}_{k+1})^{1/2}Z|\mathcal{F}_{k})$, where $Z\sim\gamma_{d}$ is independent of $\mathcal{F}_{k}\vee\sigma(T_{k+1})$, we have

E.3 Auxiliary lemmas

The next lemma is used to show that the sequence $\{\psi_{n}\}$ is uniformly integrable:

For each $n\geq 0$, define the $n$-simplex

with $s_{0}\equiv 0$ and $s_{n+1}\equiv 1$. Consider the partial sums $S_{k}\mathrel{\mathop{\mathchar 58\relax}}=\sum^{k}_{i=1}\tau_{i}$. Since the $\tau_{i}$’s are i.i.d., the conditional joint density of $(S_{1},S_{2},\ldots,S_{n})$ given $N=n$ is equal to

where we have set $s_{0}\equiv 0$. Then a calculation similar to the one in Appendix B of Andersson and Kohatsu-Higa (2017) leads to

where $\operatorname{d\!}s$ is the Lebesgue measure on $\mathcal{S}^{n}$ and

Appendix F Proof of Lemma 4.1

For each $t\geq 0$, let $N_{t}\mathrel{\mathop{\mathchar 58\relax}}=\max\{k\mathrel{\mathop{\mathchar 58\relax}}S_{k}<t\leq S_{k+1}\}$. Then $N_{1}=N$ and $T_{n}=S_{n}$ for $n\leq N$. Moreover, $\{N_{t}\}_{t\geq 0}$ is a renewal process with renewal times $\{S_{k}\}_{k\geq 0}$ and i.i.d. interrenewal times with pdf $f_{\tau}$. The moment-generating function of $M_{t}$ can be upper-bounded as follows (Glynn and Whitt, 1994):

Using Markov’s inequality and the fact that the $\tau_{i}$’s are i.i.d., we can further estimate

Substituting these estimates into (F.1) and optimizing over $\beta$, we get (4.6).

Acknowledgments

The authors would like to thank Matus Telgarsky for many enlightening discussions. This work was supported in part by the NSF CAREER award CCF-1254041, in part by the Center for Science of Information (CSoI), an NSF Science and Technology Center, under grant agreement CCF-0939370, in part by the Center for Advanced Electronics through Machine Learning (CAEML) I/UCRC award no. CNS-16-24811, and in part by the Office of Naval Research under grant no. N00014-12-1-0998.

References