betaFeedback

WorksComputer Science

Simulation-free Schrödinger bridges via score and flow matching

Abstract

We present simulation-free score and flow matching ([SF]2^2M), a simulation-free objective for inferring stochastic dynamics given unpaired samples drawn from arbitrary source and target distributions. Our method generalizes both the score-matching loss used in the training of diffusion models and the recently proposed flow matching loss used in the training of continuous normalizing flows. [SF]2^2M interprets continuous-time stochastic generative modeling as a Schrödinger bridge problem. It relies on static entropy-regularized optimal transport, or a minibatch approximation, to efficiently learn the SB without simulating the learned stochastic process. We find that [SF]2^2M is more efficient and gives more accurate solutions to the SB problem than simulation-based methods from prior work. Finally, we apply [SF]2^2M to the problem of learning cell dynamics from snapshot data. Notably, [SF]2^2M is the first method to accurately model cell dynamics in high dimensions and can recover known gene regulatory networks from simulated data. Our code is available in the TorchCFM package at https://github.com/atong01/conditional-flow-matching.

INTRODUCTION

Score-based generative models (SBGMs), including diffusion models, are a powerful class of generative models that can represent complex distributions over high-dimensional spaces [70, 73, 56, 17] (Ho et al. 2020). SBGMs typically generate samples by simulating the evolution of a source density – nearly always a Gaussian – according to a stochastic differential equation (SDE) [75]. Despite their empirical success, SBGMs are restricted by their assumption of a Gaussian source, which is essential for optimization with the simulation-free denoising objective. This assumption is often violated in the temporal evolution of physical or biological systems, such as in the case of single-cell gene expression data, which prevents the use of SBGMs for learning the underlying dynamics.

An approach of choice in such problems has been to use flow-based generative models, synonymous with continuous normalizing flows (CNFs) [12, 29, 22]. Flow-based models assume a deterministic continuous-time generative process and fit an ordinary differential equation (ODE) that transforms the source density to the target density. Flow-based models were previously limited by inefficient simulation-based training objectives that require an expensive integration of the ODE at training time. However, recent work has introduced simulation-free training objectives that make CNFs competitive with SBGMs when a Gaussian source is assumed [44, 48 Pooladian et al.,]

  1. and extended these objectives to the case of arbitrary source distributions [47, 2, 79]. However, these objectives do not yet apply to learning stochastic dynamics, which can be beneficial both for generative modeling and for recovering the dynamics of systems.

The Schrödinger bridge (SB) problem – the canonical probabilistic formulation of stochastically mapping between two arbitrary distributions – considers the most likely evolution between a source and target probability distributions under a given reference process [65, 43]. The SB problem has been applied in a wide variety of problems, including generative modeling [16, 82, 13, 85, 73], modeling natural stochastic dynamical systems [64, 32, 38], and mean field games [45]. Except for a small number of special cases (e.g., Gaussian [50, 9]), the SB problem typically does not have a closed-form solution, but can be approximated with iterative algorithms that require simulating the learned stochastic process [16, 13, 9]. While theoretically sound, these methods present numerical and practical issues that limit their scalability to high dimensions [67].

This paper introduces a simulation-free objective for the Schrödinger bridge problem called simulation-free score and flow matching ([SF]2M\left[\mathrm{SF}\right]^{2}\mathrm{M}). [SF]2M\left[\mathrm{SF}\right]^{2}\mathrm{M} simultaneously generalizes (1) the simulation-free objectives for CNFs [79, 48] to the case of stochastic dynamics and (2) the denoising training objective for diffusion models to the case of arbitrary source distributions (Figure 1). Our algorithm uses a connection between the SB problem and entropic optimal transport (OT) to express the Schrödinger bridge as a mixture of Brownian bridges [16, 43]. In contrast to dynamic SB algorithms that require simulating an SDE at every iteration, [SF]2M\left[\mathrm{SF}\right]^{2}\mathrm{M} takes advantage of static entropic OT maps between source and target distributions, which are efficiently computed by the Sinkhorn algorithm [69].

Figure 1. Left: ODE and SDE paths from 8gaussians to moons, sampled from a model trained using [SF]2M\left[\mathrm{SF}\right]^{2}\mathrm{M}. [SF]2M\left[\mathrm{SF}\right]^{2}\mathrm{M} makes it possible to vary the diffusion schedule at inference time and thus interpolate between ODEs and SDEs that have the same marginal densities. Right: Illustration of the stochastic regression objective in [SF]2M\left[\mathrm{SF}\right]^{2}\mathrm{M}. Given a source point x0x_0 and target point x1x_1 sampled from an entropic OT plan between marginals, an intermediate point xtx_t is sampled from the Brownian bridge (marginal in light blue) in a simulation-free way. Neural networks are regressed to the ODE drift uto(xt∣x0,x1)u_t^o(x_t|x_0,x_1) and to the conditional score ∇log⁡pt(xt∣x0,x1)\nabla\log p_t(x_t|x_0,x_1). The regression objective is stochastic, as the same point xtx_t may appear on different conditional paths, e.g., the dotted path from x0′x'_0 to x1′x'_1. The stochastic regression recovers dynamics that transform the marginal at time 0 to that at time 1.

We demonstrate the effectiveness of [SF]2M\left[\mathrm{SF}\right]^{2}\mathrm{M} on both synthetic and real-world datasets. On synthetic data, we show that [SF]2M\left[\mathrm{SF}\right]^{2}\mathrm{M} performs better than related prior work and finds a better approximation to the true Schrödinger bridge. As an application to real data, we consider modeling sequences of cross-sectional measurements (i.e., unpaired time series observations) by a sequence of Schrödinger bridges. While there are many prior methods on modeling cells with Schrödinger bridges in the static setting [64, 34, 41, 57] or low-dimensional dynamic setting (Bunne et al., 2022b,a; Koshizuka and Sato, 2023), [SF]2M\left[\mathrm{SF}\right]^{2}\mathrm{M} is the first method able to scale to thousands of gene dimensions, as its training is completely simulation-free. We also introduce a static manifold geodesic map which improves cell interpolations in the dynamic setting, demonstrating one of the first practical applications of Schrödinger bridge approximations with non-Euclidean costs. Finally, we show that unlike with static optimal transport, we are able to directly model and recover the gene-gene interaction network driving the cell dynamics.

We summarize our main contributions below:

  • We present [SF]²M, the first simulation-free objective for the Schrödinger bridge problem, and prove its correctness.

  • We study effective empirical and minibatch approximations to the entropic OT plan used in [SF]²M.

  • We validate our proposed method on synthetic distributions and in several single-cell dynamics problems.

PRELIMINARIES

We consider a pair of compactly supported distributions over Rd\mathbb{R}^{d} with (unknown) densities q(x0)q(x_{0}) and q(x1)q(x_{1}) (also denoted q0,q1q_{0},q_{1}). We assume access to a finite dataset of samples from q0q_{0} and q1q_{1}. The problem of continuous-time stochastic generative modeling, or SDE inference, consists in finding a stochastic mapping ff that transforms q0q_{0} to q1q_{1}. Samples from q1q_{1} can then be generated by drawing a sample from q0q_{0} and applying ff to obtain a sample from q1q_{1}.

Schrödinger bridges via entropic OT

The Schrödinger bridge problem asks to find most likely evolution between two probability measures q0q_{0} and q1q_{1} with respect to a reference stochastic process Q\mathbb{Q}. Formally, the Schrödinger bridge is the solution of:

P⋆=arg⁡min⁡P:p0=q0,p1=q1KL⁡(P∥Q),(1)\mathbb{P}^{\star}=\underset{\mathbb{P}:p_{0}=q_{0},p_{1}=q_{1}}{\arg\min}\operatorname{KL}(\mathbb{P}\mathbin\Vert\mathbb{Q}), \tag*{(1)}

where P\mathbb{P} is a stochastic process (distribution over continuous paths [0,1]→Rd[0,1]\to\mathbb{R}^{d}) with law pp (with marginals denoted ptp_{t}).

SDEs and diffusion processes. The stochastic processes we consider can be represented as Itô SDEs of the form dx=ut(x) dt+g(t) dwtdx=u_{t}(x)\,dt+g(t)\,dw_{t}, where utu_{t} is a smooth vector field and dwtdw_{t} a Brownian motion. A density p(x0)p(x_{0}) evolved according to a SDE induces marginal distributions pt(xt)p_{t}(x_{t}), viewed as a function p:[0,1]×Rd→R+p:[0,1]\times\mathbb{R}^{d}\to\mathbb{R}_{+}. They are characterized by the initial conditions p0p_{0} and the Fokker–Planck equation

∂tpt=−∇⋅(ptut)+g2(t)2Δpt,\partial_{t}p_{t}=-\nabla\cdot(p_{t}u_{t})+\frac{g^{2}(t)}{2}\Delta p_{t},

where Δpt=∇⋅(∇pt)\Delta p_{t}=\nabla\cdot(\nabla p_{t}) is the Laplacian.

In this work, we consider Q=σW\mathbb{Q}=\sigma\mathbb{W}, where W\mathbb{W} is the standard Brownian motion defined by the SDE dx=dwtdx=dw_{t}, in which case the solution to (1) is known as the diffusion Schrödinger bridge [16, 9]. We refer to Léonard [42] for a full discussion on Schrödinger bridges.

Entropically-regularized optimal transport. The entropic OT problem is defined as follows:

πε⋆(q0,q1)=arg⁡min⁡π∈U(q0,q1)∫d(x0,x1)2 dπ(x0,x1)+εKL⁡(π∥q0⊗q1),(2)\pi_{\varepsilon}^{\star}(q_{0},q_{1})= \underset{\pi\in U(q_{0},q_{1})}{\arg\min}\int d(x_{0},x_{1})^{2}\,d\pi(x_{0},x_{1})+\varepsilon\operatorname{KL}(\pi\Vert q_{0}\otimes q_{1}), \tag*{(2)}

where U(q0,q1)U(q_{0},q_{1}) is the set of admissible transport plans (joint distributions over x0x_{0} and x1x_{1} whose marginals are equal to q0q_{0} and q1q_{1}), d(⋅,⋅)d(\cdot,\cdot) is the ground cost, ε\varepsilon is the regularization parameter, and q0⊗q1q_{0}\otimes q_{1} is the joint distribution over x0,x1x_{0},x_{1} in which x0x_{0} and x1x_{1} are independent. When ε→0\varepsilon\to0, we recover exact optimal transport. We now recall a cornerstone theorem that connects the SB problem to the entropic OT plan:

Proposition 2.1 (Föllmer [24]). Let the reference process be a Brownian motion (i.e., Q=σW\mathbb{Q}=\sigma\mathbb{W}). Then the Schrödinger bridge problem admits a unique solution P⋆\mathbb{P}^{\star} having the form of a mixture of Brownian bridges weighted by an entropic OT plan:

P⋆((xt)t∈[0,1])=∫Q((xt)t∈[0,1]∣x0,x1) dπσ2⋆(x0,x1)(3)\mathbb{P}^{\star}((x_{t})_{t\in[0,1]})=\int\mathbb{Q}((x_{t})_{t\in[0,1]}\mid x_{0},x_{1})\,d\pi_{\sigma^{2}}^{\star}(x_{0},x_{1}) \tag*{(3)}

where Q((xt)t∈(0,1)∣x0,x1)\mathbb{Q}((x_{t})_{t\in(0,1)}\mid x_{0},x_{1}) is the Brownian bridge between x0x_{0} and x1x_{1} with diffusion rate σ\sigma.

Motivated by this result, the algorithm we propose stochastically regresses the parameters defining an unconditional SDE to those defining Brownian bridges.

Neural SDEs and probability flows

In this section, we consider an SDE dx=ut(x) dt+g(t) dwtdx=u_{t}(x)\,dt+g(t)\,dw_{t}. We review some important properties and discuss the approximation of utu_{t} by a neural network.

Score and flow parametrization. In the degenerate case g(t)≡0g(t)\equiv0, an SDE becomes an ODE and the Fokker–Planck equation recovers the continuity equation ∂p∂t=−∇⋅(put)\frac{\partial p}{\partial t}=-\nabla\cdot(pu_{t}). From the Fokker–Planck and continuity equations, it can easily be derived that the ODE

dx=[ut(x)−g(t)22∇log⁡pt(x)]⏟ut∘(x)dt,(4)dx=\underbrace{\left[u_{t}(x)-\frac{g(t)^{2}}{2}\nabla\log p_{t}(x)\right]}_{u_{t}^{\circ}(x)}dt, \tag*{(4)}

together with a distribution over initial conditions p(x0)p(x_{0}), induces the same marginal distributions pt(⋅)p_{t}(\cdot) as the SDE; therefore, (4) is called the probability flow ODE of the stochastic process. Conversely, if the probability flow ODE’s drift ut∘(x)u_{t}^{\circ}(x), the diffusion schedule g(⋅)g(\cdot), and the score function ∇log⁡pt(x)\nabla\log p_{t}(x) are known, then the SDE’s drift term can be recovered via

ut(x)=ut∘(x)+g(t)22∇log⁡pt(x).(5)u_{t}(x)=u_{t}^{\circ}(x)+\frac{g(t)^{2}}{2}\nabla\log p_{t}(x). \tag*{(5)}

Therefore, **specifying an SDE is tantamount to specifying the probability flow ODE and its score function. By reversing the sign of ut∘u_t^\circ in the ODE (4) and converting it to an SDE using (5), we also get the time reversal formula from Anderson [6]:

dx=[−ut∘(x)+g(t)22∇log⁡pt(x)]dt+g(t) dwt=[−ut∘(x)+g(t)2∇log⁡pt(x)]dt+g(t) dwt,(6)\begin{aligned} dx=\left[-u_t^\circ(x)+\frac{g(t)^2}{2}\nabla\log p_t(x)\right]dt+g(t)\,dw_t \\ &=\left[-u_t^\circ(x)+g(t)^2\nabla\log p_t(x)\right]dt+g(t)\,dw_t, \tag*{(6)} \end{aligned}

which induces the same distribution on x1−tx_{1-t} as the original SDE does on xtx_t.

Approximating SDEs with neural networks. If the marginal pt(x)p_t(x) can be tractably sampled and one knows the probability flow ODE’s drift ut∘(x)u_t^\circ(x) and score ∇log⁡pt(x)\nabla\log p_t(x), both can be approximated by neural networks. Specifically, time-varying vector fields vθ(⋅,⋅):[0,1]×Rd→Rdv_\theta(\cdot,\cdot):[0,1]\times\mathbb{R}^d\to\mathbb{R}^d and sθ(⋅,⋅):[0,1]×Rd→Rds_\theta(\cdot,\cdot):[0,1]\times\mathbb{R}^d\to\mathbb{R}^d can be trained with the (unconditional) score and flow matching objective

LU[SF]2M(θ)=E[∥vθ(t,x)−ut∘(x)∥2⏟flow matching loss+λ(t)2∥sθ(t,x)−∇log⁡pt(x)∥2⏟score matching loss],(7)\mathcal{L}_{\mathrm{U[SF]2M}}(\theta)= \mathbb{E}\left[ \underbrace{\lVert v_\theta(t,x)-u_t^\circ(x)\rVert^2}_{\text{flow matching loss}} +\lambda(t)^2\underbrace{\lVert s_\theta(t,x)-\nabla\log p_t(x)\rVert^2}_{\text{score matching loss}} \right], \tag*{(7)}

where the expectation is over t∼U(0,1)t\sim U(0,1), x∼pt(x)x\sim p_t(x) and λ(⋅)\lambda(\cdot) is some choice of positive weights. (In practice, it can be more stable to approximate g(t)2∇log⁡pt(x)g(t)^2\nabla\log p_t(x) rather than ∇log⁡pt(x)\nabla\log p_t(x), a simple parametrization change that does not change the learning problem or the objective.) Once trained, vθv_\theta and sθs_\theta can be used to simulate the SDE from source samples x0x_0. This procedure is described in Alg. 2.

Remarkably, with a separate parametrization of the probability flow ODE and the score, we can simulate the SDE at inference time with an arbitrary diffusion rate g(⋅)g(\cdot) that need not match the one used at training time. If the global optimum of (7) is attained (Figure 1), we are ensured to obtain samples from the same marginals for any arbitrary diffusion rate g(⋅)g(\cdot). For example, we can simulate the probability flow ODE by setting g(t)≡0g(t)\equiv0. Similarly, the backward SDE can be simulated starting at samples x1x_1 using the time reversal formula (6).

ODEs and SDEs for Brownian bridges. For processes whose marginals pt(x)p_t(x) are Gaussian, Theorem 3 of Lipman et al. [44] or Theorem 2.1 of Tong et al. [79] yield expressions for the flow and score. The main case of interest is the Brownian bridge from x0x_0 to x1x_1 with constant diffusion rate g(t)=σg(t)=\sigma. The marginals are given by pt(x)=N(x;tx1+(1−t)x0,σ2t(1−t))p_t(x)=\mathcal{N}(x;tx_1+(1-t)x_0,\sigma^2t(1-t)), and the ODE and score are computed using the aforementioned result:

ut∘(x)=1−2tt(1−t)(x−(tx1+(1−t)x0))+(x1−x0),u_t^\circ(x)=\frac{1-2t}{t(1-t)}\left(x-\left(tx_1+(1-t)x_0\right)\right)+(x_1-x_0),
∇log⁡pt(x)=tx1+(1−t)x0−xσ2t(1−t).(8)\nabla\log p_t(x)=\frac{tx_1+(1-t)x_0-x}{\sigma^2t(1-t)}. \tag*{(8)}

The Schrödinger bridge approximation algorithm we will propose leverages fast solutions to the entropy-regularized OT problem (2) and the closed-form ut∘u_t^\circ and ∇log⁡pt\nabla\log p_t of Brownian bridges (8).

Simulation-free SDE training

We next describe our simulation-free method to learn SDEs through score and flow matching, summarized in Alg. 1. We present the general case in §3.1, then consider the Schrödinger bridge case in §3.2.

Matching the conditional flow and score

Tong et al. [79] described a simulation-free stochastic regression objective, conditional flow matching (CFM), that fits an ODE generating marginal distributions given by mixtures of simpler probability paths. We generalize CFM to matching stochastic dynamics.

Suppose the stochastic process P((xt)t∈[0,1])\mathbb{P}((x_t)_{t\in[0,1]}), with marginals pt(x)p_t(x), is a mixture over a latent variable zz with density q(z)q(z), i.e.,

P((xt)t∈[0,1])=∫P((xt)t∈[0,1]∣z)q(z) dz.(9)\mathbb{P}((x_t)_{t\in[0,1]})=\int\mathbb{P}((x_t)_{t\in[0,1]}\mid z)q(z)\,dz. \tag*{(9)}

Suppose that P((xt)∣z)\mathbb{P}((x_t)\mid z) is defined by the SDE dx=ut(x∣z) dt+g(t) dwtdx=u_t(x\mid z)\,dt+g(t)\,dw_t with initial conditions p0(x∣z)p_0(x\mid z), and let ut∘(x∣z)u_t^\circ(x\mid z) be drift of the corresponding probability flow ODE given by (4). One then has expressions for the probability flow ODE and score that generate the marginals of the process P\mathbb{P} given initial conditions p0(x)=∫zp0(x∣z)q(z) dzp_0(x)=\int_z p_0(x\mid z)q(z)\,dz:

ut∘(x)=Eq(z)[ut∘(x∣z)pt(x∣z)pt(x)],u_t^\circ(x)=\mathbb{E}_{q(z)}\left[\frac{u_t^\circ(x\mid z)p_t(x\mid z)}{p_t(x)}\right],
∇log⁡pt(x)=Eq(z)[pt(x∣z)pt(x)∇log⁡pt(x∣z)].(10)\nabla\log p_t(x)=\mathbb{E}_{q(z)}\left[\frac{p_t(x\mid z)}{p_t(x)}\nabla\log p_t(x\mid z)\right]. \tag*{(10)}

To be precise, we generalize Theorem 3.1 from Tong et al. [79] to stochastic settings:

Theorem 3.1. Under mild regularity conditions, the ODE dx=ut∘(x) dtdx=u_t^\circ(x)\,dt generates the marginals ptp_t of P\mathbb{P} from initial conditions p0p_0, and the score is given by (10). The SDE dx=[ut∘(x)+12g(t)2∇log⁡pt(x)]dx+g(t) dtdx=[u_t^\circ(x)+\frac{1}{2}g(t)^2\nabla\log p_t(x)]dx+g(t)\,dt generates the Markovization of P\mathbb{P}.

We emphasize that, in general, the SDE in Theorem 3.1 does not recover P\mathbb{P}, but only its Markovization (i.e., the process with the same infinitesimal transition kernel). A process P\mathbb{P} of the form (9) is not necessarily Markovian and may not be generated by any SDE.

A stochastic regression objective. The marginal ODE drift and score expressions in (10) motivate objectives for fitting ut∘(x)u_t^\circ(x) and ∇log⁡pt(x)\nabla\log p_t(x) with neural Algorithm 1 Score and Flow Matching Training

Input: Efficiently samplable q(z)q(z), pt(x∣z)p_t(x|z), computable ut∘(x∣z)u_t^{\circ}(x|z), initial networks vθv_\theta and sθs_\theta.

while Training do

z∼q(z);t∼U(0,1);x∼pt(x∣z)z \sim q(z);\quad t \sim\mathcal{U}(0,1);\quad x \sim p_t(x|z)

L[SF]2M←∥vθ(t,x)−ut∘(x∣z)∥2+λ(t)2∥sθ(t,x)−∇xlog⁡pt(x∣z)∥2▹\mathcal{L}_{[\mathrm{SF}]^2\mathrm{M}} \leftarrow\lVert v_\theta(t,x)-u_t^{\circ}(x|z)\rVert^2+\lambda(t)^2\lVert s_\theta(t,x)-\nabla_x\log p_t(x|z)\rVert^2 \triangleright see (11)

θ←Update⁡(θ,∇θL[SF]2M)\theta\leftarrow\operatorname{Update}(\theta,\nabla_\theta\mathcal{L}_{[\mathrm{SF}]^2\mathrm{M}})

return vθ,sθv_\theta,s_\theta

networks when only the conditional ODEs and scores are known. Generalizing (7), we define the (conditional) simulation-free score and flow matching objective ([SF]2^2M) for neural networks vθ(⋅,⋅)v_\theta(\cdot,\cdot) approximating the ODE drift and sθ(⋅,⋅)s_\theta(\cdot,\cdot) approximating the score:

L[SF]2M(θ)=EQ′∥vθ(t,x)−ut∘(x∣z)∥2+EQ′λ(t)2∥sθ(t,x)−∇log⁡pt(x∣z)∥2(11)\mathcal{L}_{[\mathrm{SF}]^2\mathrm{M}}(\theta)=\mathbb{E}_{Q'}\left\lVert v_\theta(t,x)-u_t^{\circ}(x|z)\right\rVert^2+\mathbb{E}_{Q'}\lambda(t)^2\left\lVert s_\theta(t,x)-\nabla\log p_t(x|z)\right\rVert^2 \tag*{(11)}

where, as in (7), λ(⋅)\lambda(\cdot) is some choice of positive weights and Q′=(t∼U(0,1))⊗q(z)⊗pt(x∣z)Q'=(t\sim\mathcal{U}(0,1))\otimes q(z)\otimes p_t(x|z). This objective can be used to approximate the quantities defined in (10), provided the conditional ODEs and scores are known and pt(x∣z)p_t(x|z) can be tractably sampled. Correctness is guaranteed by the following Theorem:

Theorem 3.2 (Equality of conditional gradients). If pt(x)>0p_t(x)>0 for all x∈Rdx\in\mathbb{R}^d and t∈[0,1]t\in[0,1], then ∇θLU[SF]2M(θ)=∇θL[SF]2M(θ)\nabla_\theta\mathcal{L}_{U[\mathrm{SF}]^2\mathrm{M}}(\theta)=\nabla_\theta\mathcal{L}_{[\mathrm{SF}]^2\mathrm{M}}(\theta), where LU[SF]2M(θ)\mathcal{L}_{U[\mathrm{SF}]^2\mathrm{M}}(\theta) is the unconditional score and flow matching loss (7).

This result generalizes Tong et al. [79]. It provides a simulation-free way to train neural networks sufficient to simulate an SDE generating marginals pt(x)p_t(x) with arbitrary diffusion rate g(⋅)g(\cdot) (cf. the discussion following (7)). The training and inference algorithms are summarized in Alg. 1, Alg. 2.

In our approach, the SDE recovered from the ODE and score defined via (10) is the Markovization of the mixture of stochastic processes indexed by zz.

Sources of conditional ODEs and scores. Although the [SF]2^2M framework can handle general conditioning information zz, in this paper we consider the case where zz is identified with a pair (x0,x1)(x_0,x_1) of a source and target point. For a given z=(x0,x1)z=(x_0,x_1), we will take the conditional probability path pt(x∣z)p_t(x|z) to be a Brownian bridge with constant diffusion scale σ\sigma, so that ut∘(x∣z)u_t^{\circ}(x|z) and ∇log⁡pt(x∣z)\nabla\log p_t(x|z) are given by (8). To avoid numerical issues for tt close to 0 or 1, we add a small smoothing constant to the variance. The conditional distributions are thus peaky at x0x_0 and x1x_1 at t=0t=0 and t=1t=1. (An extension to nonconstant diffusion scale is described in Appendix E.)

Building Schrödinger bridges via [SF]2M and entropic optimal transport

For the resulting marginal pt(x)p_t(x) to satisfy the boundary conditions p0(x)=q0(x)p_0(x)=q_0(x) and p1(x)=q1(x)p_1(x)=q_1(x), q(x0,x1)q(x_0,x_1) must be a coupling of q0q_0 and q1q_1 (i.e., a transport plan). This is formalized in the following theorem:

Theorem 3.3 ([SF]2^2M recovers marginals from bridges). If q(⋅,⋅)∈U(q0,q1)q(\cdot,\cdot)\in U(q_0,q_1) and vθ∗,sθ∗v_\theta^*,s_\theta^* globally minimize L[SF]2M(θ)\mathcal{L}_{[\mathrm{SF}]^2\mathrm{M}}(\theta), the SDE with drift [vθ∗+12g(t)2sθ∗][v_\theta^*+\frac{1}{2}g(t)^2s_\theta^*] and diffusion gg, and initial conditions p0=q0p_0=q_0, is the Markovization of the mixture of Brownian bridges from x0x_0 to x1x_1 over q(x0,x1)q(x_0,x_1). In particular, if the SDE generates marginals ptp_t, then p1=q1p_1=q_1.

This theorem tells us that as long as our joint distribution q(x0,x1)q(x_0,x_1) has the correct marginals, [SF]2^2M will recover a valid generative model which pushes q0q_0 to q1q_1.

In the previous section, we showed that our method, [SF]2^2M, can approximate the marginal probability ptp_t of a mixture of processes of the form (9). In this section, we explain how our [SF]2^2M approximates the SB.

[SF]2^2M approximates the Schrödinger bridge. In order to achieve an efficient approximation of the SB, we leverage Proposition 2.1. The SB can be expressed as a mixture of Brownian bridges weighted by an entropic optimal transport plan (3). Therefore, to approximate the SB with [SF]2^2M, we set the distribution q(x0,x1)q(x_0,x_1) to be equal to the entropic OT plan π2σ2∗(q0,q1)\pi^{*}_{2\sigma^2}(q_0,q_1) and train the networks vθv_\theta and sθs_\theta using Alg. 1. We show that this procedure recovers the SB:

Proposition 3.4 ([SF]2^2M with entropic OT recovers the SB process). Let P∗\mathbb{P}^* be the Schrödinger bridge between q0q_0 and q1q_1 with respect to Q=σW\mathbb{Q}=\sigma\mathbb{W}. If vθ∗,sθ∗v_\theta^*,s_\theta^* globally minimize L[SF]2M\mathcal{L}_{[\mathrm{SF}]^2\mathrm{M}}, with coupling π2σ2∗(q0,q1)\pi^*_{2\sigma^2}(q_0,q_1), then P∗\mathbb{P}^* is defined by the SDE with drift [vθ∗+12g(t)2sθ∗][v_\theta^*+\frac{1}{2}g(t)^2s_\theta^*], diffusion gg, and initial conditions p0=q0p_0=q_0.

Empirical approximation. Unfortunately, the real distributions q0q_0 and q1q_1 are usually unknown and we only have access to i.i.d. samples forming empirical distributions q^0\widehat q_0 and q^1\widehat q_1 of size nn. Therefore, we can only approximate the true entropic OT plan by computing the entropic OT plan π2σ2∗(q^0,q^1)\pi^*_{2\sigma^2}(\widehat q_0,\widehat q_1) between the empirical distributions (Cuturi [14]; Altschuler et al. [5]). This empirical OT plan can be used in [SF]2^2M to construct an empirical Schrödinger bridge.

Fortunately, the true entropic OT can be efficiently approximated using empirical distributions, even in high-dimensional spaces (Genevay et al. [25]; Mena and Niles-Weed [51]), and it was recently shown that the Schrödinger bridge inherits this property (Stromme [76]). In turn, the entropic OT plan between empirical distributions can be efficiently computed using the Sinkhorn algorithm [14], which has O(n2)O(n^2) computational complexity [5], or using stochastic algorithms [26, 66]. However, if this cost is to high (e.g., if nn is too large or if one has the true generative process, as in the Gaussian-to-data setting), the plan can be further approximated using minibatch OT [19, 18]; see Appendix § 10.

The use of an entropic OT plan and marginalization via stochastic regression distinguishes [SF]²M from existing neural SB algorithms (Table 1). Such past approaches include mean-matching (DSB and NLSB, De Bortoli et al., 2021; Koshizuka and Sato, 2023), and bridge-matching approaches (DSBM and IDBM, Shi et al., 2023; Peluchetti, 2023), both of which require an outer iterative proportional fitting loop with an inner training loop. Others have studied the problem assuming paired source and target data (I²SB and ASB, Liu et al., 2023a; Somnath et al., 2023); [SF]²M can be thought of as inferring the pairing while jointly fitting the SDE.

Algorithm →I²SB/ASBDSB/NLSBDSBM/IDBM[SF]²M
Unpaired samples✗✓✓✓
Bridge matching✓✗✓✓
Single loop✓✗✗✓
Sim.-free training✓✗✗/✓✓
No explicit (x0,x1)(x_0, x_1) pairing✓✓✓✗

Table 1. Comparison of SB algorithms (see § 6). [SF]²M is the first algorithm that does not assume paired samples, require SDE integration during training, or use an IPF outer loop. DSBM uses simulation only in the outer loop.

See §C.3 for further discussion of the implications of these choices and practical recommendations.

LEARNING CELL DYNAMICS WITH [SF]²M

Modeling cell dynamics is a major open problem in single-cell data science, as it is important for understanding – and eventually intervening in – cellular programs of development and disease [40]. In this section, we show how [SF]²M can be used for and adapted to modeling single-cell dynamics.

The cellular dynamics between time-resolved snapshot data, representing observations of cells lying in the space of gene activations, are commonly modeled using Schrödinger bridges [30, 64, 9, 38]. The applicability of the SB formulation to cell dynamics relies upon the principle of least action, which is thought to hold for cellular systems over short timescales [63], and motivates our choice to apply [SF]²M to these problems.

Learning flows on cell manifolds. Cells are thought to lie on a low-dimensional manifold in the space of gene expressions [52], which has motivated work on density-adhering regularizations [80, 38] and manifold embeddings [33]. Because [SF]²M can use a coupling between marginals q(x0,x1)q(x_0, x_1) defined by entropic OT with an arbitrary cost function, we can take advantage of these embeddings to compute the pairing using a ground cost that is adapted to the geometry of the manifold. Specifically, we use the Geodesic Sinkhorn method [34], which computes the entropic OT plan with cost

cgeo(x0,x1)=−log⁡Ht(x0,x1).(12)c_{\mathrm{geo}}(x_0, x_1) = \sqrt{-\log\mathcal{H}_t(x_0, x_1)}. \tag*{(12)}

The matrix Ht\mathcal{H}_t approximates the heat kernel defined via the Laplace-Beltrami operator on the manifold, efficiently approximated using a kk-nearest-neighbour graph. We find using this cost leads to more accurate trajectories in high dimensions (see Table 5).

Dim. →501001000
Alg. ↓ | Dataset →CiteMultiCiteMultiCiteMulti
[SF]2^2M-Geo38.52±0.2944.80±1.9144.50±0.4252.20±1.9640.09±1.5351.29±0.09
[SF]2^2M-Exact40.01±0.7845.34±2.8346.53±0.4352.89±1.9943.66±0.7253.15±1.86
DSBM53.81±7.7466.43±14.3958.99±7.6270.75±14.0350.09±4.8161.71±13.90
OT-CFM38.76±0.4047.58±6.6245.39±0.4254.81±5.8643.25±0.7352.29±1.55
I-CFM41.83±3.2849.78±4.4348.28±3.2857.26±3.8644.12±0.5252.99±1.50

Table 5. Leave-one-timepoint-out testing of dynamics interpolation methods measuring the error between the predicted and ground truth left out timepoint using the 1-Wasserstein distance. We test on 50 and 100 principal components as well as 1000 highly variable genes.

Learning developmental landscapes. A common model of cell development, known as Waddington’s epigenetic landscape [83], assumes that cells evolve and differentiate in the space of gene expressions by following (noisy) gradient ascent on an energy function. While a few heuristic methods have been proposed to approximate this energy function from single-cell data before [77, 61], we propose a novel approach to model the landscape directly. In our approach, the negative energy can be directly interpreted as an action potential, inspired by the modeling in Neklyudov et al. [54].

To do this, we impose a Langevin dynamics parametrization on the flow and score in [SF]²M: vθ(t,x)=−∇xEv(t,x)v_\theta(t, x) = -\nabla_x E_v(t, x) and sθ(t,x)=−∇xEs(t,x)s_\theta(t, x) = -\nabla_x E_s(t, x), where EvE_v and EsE_s are neural networks. We can define the Waddington’s landscape by W:=Ev+12g(t)2EsW := E_v + \frac{1}{2}g(t)^2 E_s. The drift of the SDE is then ut(x)=−∇xW(t,x)u_t(x) = -\nabla_x W(t, x), meaning that the time-evolution of a cell follows gradient dynamics on WW with added Gaussian noise of scale g(t)g(t). We visualize these landscapes in Figure 2 with further details in §F.6.

Visualization of learned Waddington's landscape

Figure 2. Visualization of learned Waddington’s landscape WW with a bifurcating trajectory for one Gaussian to two Gaussians (left) and for the Embryoid Body (EB) data [53] (right). The dimensions are space (left-right), time (forward-back), and potential (up-down).

Learning gene regulatory networks. Finally, we use [SF]2^2M to learn gene regulatory networks from population snapshots of gene expressions, a persisting challenge in cellular biology ([60]). Following previous work in discovering sparse interaction structure from continuous-time systems ([78, 4, 8, 3, 7]), we define the gene regulatory network as the directed graph whose vertices are genes (dimensions of the space) and an edge i→ji\to j is present if and only if ∂(vθ(t,x))j∂xi≠0\frac{\partial(v_\theta(t,x))_j}{\partial x_i}\ne0. This directed graph is expected to be sparse.

Previous work resorted to performing inference of trajectories in a low-dimensional (and dense) representation ([81, 10]), which complicated the discovery of the sparse graph structure in gene space. [SF]2^2M is the first Schrödinger bridge method to scale to high dimensions. This allows us to learn a dynamic directly in the gene space and recover the sparse gene interactions. To accomplish this, we use a specialized parametrization of vθv_\theta, inspired by Bellot and Branson [8], which enables the graph structure to be read out from the sparsity pattern of the initial layer of the trained model (see §F.7 for details).

RELATED WORK

Stochastic continuous-time modeling. Our framework is related to both flow-based ([12, 29, 1, 2, 55, 47]) and score-based ([70, 73, 74, 75, 87, 17, 86] (Ho et al. 2020)) generative modeling. Both have drawn attention due to their stability and efficiency in training and high quality of generated samples. See Appendix C for further discussion.

Schrödinger bridge approximation methods. While there is significant theoretical work on the SB problem ([43, 76, 1]), practical solutions have assumed paired samples from the Schrödinger bridge or required simulation during training. Algorithms based on iterative proportional fitting (DSB and DSBM; [16, 67]) have the advantage of yielding the exact Schrödinger bridge if trained to optimality on each iteration, but may accumulate error with each outer-loop step due to underfitting and function approximation. On the other hand, our proposed [SF]2^2M requires neither training-time integration nor outer-loop iteration and therefore will converge to the exact SB – if the neural network function class and learning algorithm so allow – but, unlike DSB and DSBM, require knowledge of the entropic OT plan and the conditional paths (see Table 1).

The relative advantages of these algorithms and practical recommendations are further discussed in §3.2, §C.3. Furthermore, in Appendix D we show that the simulation-based outer loop in Peluchetti [58]; ); Shi et al. [67] can be combined with [SF]2^2M to improve the SB marginals at the cost of generative performance.

Applications to cell dynamics. When the observer seeks to recover dynamics from multiple snapshots with scRNA-seq data, the machinery of optimal transport can be used ([64, 89, 80, 10, 33, 9, 38]). However, these methods all require simulation during training, which scales poorly to high dimensions.

EXPERIMENTS

In this section we empirically evaluate [SF]2^2M with respect to optimal transport, generative modeling, and single-cell interpolation criteria. We compare:

  • Minibatch [SF]2^2M with exact OT minibatches ([SF]2^2M-Exact), with entropic OT (Sinkhorn) mini-

batches (-Sink), with independent couplings (-I), and with Geodesic OT (-Geo) when applicable.

  • A variety of (ODE) flow-based models, including optimal transport conditional flow matching (OT-CFM, Tong et al., [79]), rectified flow (RF, Liu, [47]), and flow matching (FM, Lipman et al., [44]).

  • Schrödinger bridge models: diffusion Schrödinger bridges (DSB, De Bortoli et al., [16]) and diffusion Schrödinger bridge matching (DSBM, Shi et al., [67]), which is equivalent to work on iterated diffusion mixture transport (IDBM, Peluchetti, [58]).

  • Single-cell dynamics models: Neural Lagrangian Schrödinger bridges (NLSB, Koshizuka and Sato, [38]), TrajectoryNet (Tong et al., [80]).

See Appendix F for all experiment details. All results are presented as mean ± std. over five seeds.

[SF]2^2M is a competitive generative model for low-dimensional data. We first evaluate in Table 2 how well various methods approximate dynamic optimal transport on low-dimensional datasets (8gaussians, moons, and scurve). We train Schrödinger bridges between a Gaussian and each dataset, and between 8gaussians and moons, using [SF]2^2M. We report the 2-Wasserstein distance between the predicted distribution and the target distribution with samples of size 10,000. Following Tong et al. [79], we also report the Normalized Path Energy relative to the 2-Wasserstein distance, defined as NPE⁡(p,q):=∣∫∥vθ(t,x)∥2dt−W22(p,q)∣/W22(p,q)\operatorname{NPE}(p,q) := \left|\int\lVert v_\theta(t,x)\rVert^2 \mathrm{d}t - \mathcal{W}_2^2(p,q)\right|/\mathcal{W}_2^2(p,q). This metric is equal to zero if and

only if vθv_\theta solves the dynamic optimal transport problem. Table 2 summarizes our results, showing that [SF]2^2M outperforms all methods, both stochastic (top) and deterministic (bottom). Despite minibatch OT bias (which can be seen as a form of regularization like the entropic regularization (Fatras et al., [19])), we find [SF]2^2M-Exact approximates the Schrödinger bridge best, with the OT computation accounting for only 1% of the training time on batch sizes of 512.

[SF]2^2M recovers the SB. Next we evaluate how well [SF]2^2M can model Schrödinger bridge marginals. We use a Gaussian-to-Gaussian Schrödinger bridge because it has closed-form Gaussian marginals (Mallasto et al., [50]; Bunne et al., [9]) following De Bortoli et al. [16]. After training all methods, we evaluate the quality of empirical marginals with respect to the ground truth by sampling trajectories using Alg. 2. We compute the KL divergence between a Gaussian approximation of the empirical marginal and the Gaussian marginal of the ground truth Schrödinger bridge at multiple timepoints. This evaluation is shown in Table 3 at just the last timepoint (t=1t = 1) and an average over 21 equally spaced timepoints. We train each method for an equal number of steps, using 20 outer loops for DSB and DSBM, which require iterative optimization of forward and backward models. We find that in low dimensions SB-CFM, which corresponds to [SF]2^2M’s probability ODE flow, performs the best, closely followed by [SF]2^2M-Exact. In high dimensions, [SF]2^2M-Exact better matches the target distribution, and performs similarly to DSBM and significantly better than DSB on the intermediate marginals.

[SF]2^2M accurately models high-dimensional single cell dynamics. We train our method [SF]2^2M on single cell dynamics, as described in §4, on three real-world datasets in the setup established by Tong et al. [80] (see §F.6) and gathered our results for different dimensions in Table 4 and Table 5. Given KK unpaired data distributions representing a cell population at KK different timepoints, we solve a SB problem between every two successive time points, sharing parameters between the models. To test the interpolation ability of the trained models, we perform leave-one-out interpolation, predicting timepoint kk using a model trained on timepoints [1,…,k−1,k+1,…,K][1,\ldots,k-1,k+1,\ldots,K]. We consider four data representations of different dimensionality: using the first 5, 50, or 100 whitened principal components and using the 1000 dimensions corresponding to the most highly variable genes [88]. [SF]2M[\mathrm{SF}]^{2}\mathrm{M} performs the best among the Schrödinger bridge methods and similarly to the ODE-based OT-CFM on the low-dimensional data (Table 4), but is better in higher dimensions (Table 5). As the number of dimensions grows, the advantage of geodesic interpolation ([SF]2M[\mathrm{SF}]^{2}\mathrm{M}-Geo) becomes apparent.

Algorithm ↓ | Dataset →CiteEBMulti
[SF]2^2M-Geo1.017±0.1040.879±0.1481.255±0.179
[SF]2^2M-Exact0.920±0.0490.793±0.0660.933±0.054
[SF]2^2M-Sink1.054±0.0871.198±0.3421.098±0.308
DSBM (Shi et al., [67])1.705±0.1601.775±0.4291.873±0.631
DSB (De Bortoli et al., [16])0.953±0.1400.862±0.0231.079±0.117
OT-CFM (Tong et al., [79])0.882±0.0580.790±0.0680.937±0.054
I-CFM (Tong et al., [79])0.965±0.1110.872±0.0871.085±0.099
SB-CFM (Tong et al., [79])1.067±0.1071.221±0.3801.129±0.363
Reg. CNF (Finlay et al., [22])*—0.825—
TrajectoryNet (Tong et al., [80])*—0.848—
NLSB (Koshizuka and Sato, [38])—0.970—

Table 4. Single-cell comparison over three datasets, averaged over leaving out different intermediate timepoints on 5 PCs. For each left-out point, we measure the 1-Wasserstein distance between the imputed and ground truth distributions at the left-out time point, following Tong et al. [80]. *Indicates values taken from aforementioned work.

We also compare the stochastic process modeled by [SF]2M[\mathrm{SF}]^{2}\mathrm{M} to its probability flow ODE SB-CFM. We show in Figure 3 that [SF]2M[\mathrm{SF}]^{2}\mathrm{M} models a stochastic dependence of the output on the input, unlike SB-CFM, despite the two algorithms sharing marginal densities. This is important in the EB data as the initial stem cells are thought to be pluripotent and should evolve stochastically into differentiated cell types over time. Such differentiation cannot be modelled by ODE-based methods, thus motivating the use of a stochastic process for modeling single-cell dynamics.

Simulation of trajectories from a given cell on 2D EB data

Figure 3. Simulation of trajectories from a given cell on 2D EB data. Left: Probability flow ODE trajectory, approximated by SB-CFM [79]. Right: Five SDE trajectories from [SF]2M[\mathrm{SF}]^{2}\mathrm{M}; more target samples (20) in blue.

[SF]2M[\mathrm{SF}]^{2}\mathrm{M} can be used to recover gene regulatory networks. We demonstrate the use-case of [SF]2M[\mathrm{SF}]^{2}\mathrm{M} for recovering gene regulatory networks (GRNs) from single-cell gene expression using the algorithm described at the end of §4. We show how we can use [SF]2M[\mathrm{SF}]^{2}\mathrm{M} to simultaneously learn dynamics and GRN structure from single-cell gene expression data. We use BoolODE [60] to simulate two single-cell systems given ground truth GRNs: (1) a system with bifurcating trajectories (7 genes), and (2) a system with trifurcating trajectories (9 genes). We summarize our results in Table 6. We also measure how accurately the ground truth GRN is recovered using the standard AUC-ROC and average precision (AP) metrics. We find that [SF]2M[\mathrm{SF}]^{2}\mathrm{M}-Exact with no noise (corresponding to OT-CFM [79]) performs best at inferring the underlying GRN as compared to correlation baselines (Pearson and Spearman correlation), a mutual information baseline DREMI [39], and pairwise Granger causality [28]. Higher values of σ\sigma do not perform as well, but still outperform the baselines on most metrics.

GRN →\rightarrowBifurcating SystemTrifurcating System
Alg. ↓\downarrow | Metric →\rightarrowAUC-ROC (↑\uparrow)AP (↑\uparrow)AUC-ROC (↑\uparrow)AP (↑\uparrow)
NGM-[SF\mathrm{SF}]2Mσ=0.1^{2}\mathrm{M}_{\sigma=0.1}0.786±0.081_{\pm0.081}0.521±0.160_{\pm0.160}0.764±0.066_{\pm0.066}0.485±0.105_{\pm0.105}
NGM-[SF\mathrm{SF}]2Mσ=0.1^{2}\mathrm{M}_{\sigma=0.1}0.723±0.014_{\pm0.014}0.444±0.030_{\pm0.030}0.731±0.077_{\pm0.077}0.453±0.091_{\pm0.091}
Spearman0.755±0.003_{\pm0.003}0.438±0.002_{\pm0.002}0.718±0.00_{\pm0.00}0.413±0.005_{\pm0.005}
Pearson0.744±0.000_{\pm0.000}0.415±0.000_{\pm0.000}0.710±0.00_{\pm0.00}0.405±0.002_{\pm0.002}
DREMI0.594±0.017_{\pm0.017}0.293±0.011_{\pm0.011}0.419±0.02_{\pm0.02}0.205±0.007_{\pm0.007}
Granger0.664±0.013_{\pm0.013}0.421±0.04_{\pm0.04}0.613±0.04_{\pm0.04}0.343±0.039_{\pm0.039}
SCODE0.570±0.036_{\pm0.036}0.370±0.028_{\pm0.028}0.570±0.06_{\pm0.06}0.332±0.077_{\pm0.077}

Table 6. GRN recovery from simulated time-lapsed single-cell gene expression. Shows structure predictive performance in terms of area under the receiver operator characteristic (AUC-ROC) and average precision (AP).

CONCLUSION

We have introduced a novel class of simulation-free objectives for learning continuous-time stochastic generative models between general source and target distributions. For sources and targets with finite support, we can directly approximate the continuous-time Schrödinger bridge without simulation by computing the entropic OT plan via efficient algorithms. We have shown how our method can be applied to learn cell dynamics and extract the gene regulatory structure. Future work can consider how to train [SF]2M[\mathrm{SF}]^{2}\mathrm{M}-like models with interventional data to improve GRN inference.

Limitations. The main limitation of [SF]2M[\mathrm{SF}]^{2}\mathrm{M} is that it requires knowledge of conditional path distributions (Brownian bridges). These distributions are not available in closed form if one considers more general reference processes [21], which may be useful to encode biological priors [38], or on general Riemannian manifolds.

Acknowledgments

We would like to thank Hananeh Aliee, Paul Bertin, Valentin de Bortoli, Stefano Massaroli, and Austin Stromme for productive conversations. The authors acknowledge funding from CIFAR, Genentech, Samsung, IBM, Microsoft, and Google. We are also grateful to the anonymous reviewers for suggesting numerous improvements. This research was enabled in part by compute resources provided by Mila (mila.quebec) and NVIDIA Corporation. In addition, K.F. acknowledges funding from NSERC (RGPIN-2019-06512) and G.W. acknowledges funding from NSERC Discovery grant 03267 and NIH grant R01GM135929.

Checklist

  1. For all models and algorithms presented, check if you include: (a) A clear description of the mathematical setting, assumptions, algorithm, and/or model. [Yes] (b) An analysis of the properties and complexity (time, space, sample size) of any algorithm. [Yes] (c) Source code, with specification of all dependencies, including external libraries. [Yes]

  1. For any theoretical claim, check if you include: (a) Statements of the full set of assumptions of all theoretical results. [Yes] (b) Complete proofs of all theoretical results. [Yes] (c) Clear explanations of any assumptions. [Yes]

  1. For all figures and tables that present empirical results, check if you include: (a) The code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL). [Yes] (b) All the training details (e.g., data splits, hyperparameters, how they were chosen). [Yes] (c) A clear definition of the specific measure or statistics and error bars (e.g., with respect to the random seed after running experiments multiple times). [Yes] (d) A description of the computing infrastructure used. (e.g., type of GPUs, internal cluster, or cloud provider). [Yes]

  1. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets, check if you include: (a) Citations of the creator if your work uses existing assets. [Yes] (b) The license information of the assets, if applicable. [Not Applicable] (c) New assets either in the supplemental material or as a URL, if applicable. [Not Applicable] (d) Information about consent from data providers/curators. [Not Applicable] (e) Discussion of sensible content if applicable, e.g., personally identifiable information or offensive content. [Not Applicable]

  1. If you used crowdsourcing or conducted research with human subjects, check if you include: (a) The full text of instructions given to participants and screenshots. [Not Applicable] (b) Descriptions of potential participant risks, with links to Institutional Review Board (IRB) approvals if applicable. [Not Applicable] (c) The estimated hourly wage paid to participants and the total amount spent on participant compensation. [Not Applicable]

Simulation-Free Schrödinger Bridges via Score and Flow Matching: Supplementary Materials

Our code can be found at https://github.com/atong01/conditional-flow-matching. The supplementary material is structured as follows:

  • Appendix A gives more background on optimal transport.

  • Appendix B presents the proofs of our different results.

  • Appendix C gives more background on the related work.

  • Appendix D describes additional results and experiments.

  • Appendix E discusses Schrödinger bridges with varying diffusion rate.

  • Appendix F presents the experimental details of our experiments in the main paper.

BACKGROUND ON OPTIMAL TRANSPORT

In this section, we review optimal transport and its application in machine learning.

Minibatch OT

Algorithm 2 Simulation-Free Score and Flow Matching Inference (with Euler-Maruyama integration)

Input: Source distribution q0q_0, flow and score networks vθv_\theta and sθs_\theta, diffusion schedule g(⋅)g(\cdot), integration step size Δt\Delta t.

x0∼q0(x)x_0 \sim q_0(x)

for tt in [0,1/Δt)[0, 1/\Delta t) do

ut←vθ(t,xt)+g(t)22sθ(t,xt)u_t \leftarrow v_\theta(t, x_t) + \frac{g(t)^2}{2}s_\theta(t, x_t)

xt+Δt∼N(x+utΔt,g(t)2Δt)x_{t+\Delta t} \sim\mathcal{N}(x + u_t\Delta t, g(t)^2\Delta t)

return Samples x1x_1

Minibatch OT

In the context of generative modeling, the source distribution is a Gaussian distribution and the target distribution is the real data distribution. This scenario corresponds to a semi-discrete optimal transport problem. Therefore, the Sinkhorn algorithm cannot be used to compute the entropic OT plan between distributions. It is nonetheless possible to compute it with stochastic algorithms [26]. Unfortunately, these stochastic algorithms are slow to converge and it is prohibitive for large scale datasets. Therefore, we chose to rely on a minibatch optimal transport approximation [19, 20]. Minibatch OT computes the OT between minibatches of samples and thus corresponds to the discrete-discrete optimal transport setting. It is known to have quadratic computational and memory costs in the number of samples (see §A.2 for a longer discussion).

The minibatch optimal transport approximation has been successfully before used in generative modeling [27, 62]. As it is different from the original optimal transport problem, we want to make sure that the basic properties from Schrödinger Bridges are conserved. We use the minibatch optimal transport plans definitions from [19], namely

Definition A.1 (minibatch transport plan [19]). Consider αn\alpha_n and βn\beta_n two empirical probability distributions. For each A={a1,…,am}∈Pm(αn)A = \{a_1, \ldots, a_m\} \in\mathcal{P}_m(\alpha_n) and B={b1,…,bm}∈Pm(βn)B = \{b_1, \ldots, b_m\} \in\mathcal{P}_m(\beta_n) we denote by ΠA,B\Pi_{A,B} the optimal plan between the random variables, considered as a n×nn \times n matrix where all entries are zero except those indexed in A×BA \times B. We define the averaged minibatch transport matrix:

Πm(αn,βn)=(nm)−2∑A∈Pm(αn)∑B∈Pm(βn)ΠA,B.(13)\Pi^m(\alpha_n,\beta_n) = \binom{n}{m}^{-2} \sum_{A \in\mathcal{P}_m(\alpha_n)} \sum_{B \in\mathcal{P}_m(\beta_n)} \Pi_{A,B}. \tag*{(13)}

Following the subsampling idea, we define the subsampled minibatch transportation matrix:

Πk(αn,βn):=k−1∑(A,B)∈DkΠA,B(14)\Pi^k(\alpha_n,\beta_n) := k^{-1} \sum_{(A,B) \in D_k} \Pi_{A,B} \tag*{(14)}

where DkD_k is a set of cardinality kk whose elements are drawn at random from the uniform distribution on Γ:=Pm({x01,…,x0n})×Pm({x11,…,x1n})\Gamma:= \mathcal{P}_m(\{x_0^1,\ldots,x_0^n\}) \times\mathcal{P}_m(\{x_1^1,\ldots,x_1^n\}).

Note that Πk\Pi_k converges exponentially fast to Πm\Pi_m as kk grows [19 Theorem 2]. In practice, it is enough to set kk equal to 1 to get good performance in deep learning applications [27, 15, 18]. Therefore, the subsampling estimator does not have the correct marginals in general, contrary to Πm\Pi_m which has always the right marginals [19 Proposition 1]. Minibatch optimal transport has been shown to implicitly regularize the transport plan [19, 20]. Indeed, as we draw uniformly at random sample to build the minibatches, we create non optimal connections. This is similar to the entropic optimal transport which densifies the transport plan. Therefore, coupling the minibatch approximation with the entropic OT cost might lead to an extremely dense plan that is close to the uniform transport plan. Unfortunately such a transport plan looses all geometric insights from data and is also far from the original entropic OT cost. We illustrate this phenomenon in Figure 4 on a toy example between two 2D data distributions. Notably, the minibatch OT plan is closer to the entropic OT plan than the minibatch entropic OT plan. That is why in our experiments, we observed that the minibatch approximation with exact optimal transport outperforms the minibatch approximation with the entropic OT cost. We leave the question of closeness between minibatch OT and entropic OT as future work. While it would have been possible to decrease these non-optimal connections with OT variants [18], it would have added extra hyperparameters that would have led to more compute.

Figure 4. Optimal transport couplings for different OT costs and batch sizes on a 2D example. The top row represent the OT matching between samples while the bottom row represent the minibatch OT plan. We can see that coupling entropic OT with minibatches lead to a uniform plan contrary to using only entropic regularization or minibatch approximation.

Computational complexity

The batch size we use is 512 for all experiments except for the Gaussian-to-Gaussian experiments, which use batch size 500 to match the DSBM baseline. The complexity of static discrete OT is cubic in the batch size mm and linear in the dimension dd: O(m3+m2d)O(m^3 + m^2d). This can be reduced to quadratic complexity in the entropy-regularized discrete OT case. However, for batches <10k<10k, the exact minibatch OT is often actually faster than the Sinkhorn solver for the entropic OT problem thanks to the optimized simplex solver code in POT [23]. Note that the memory complexity is quadratic in the number of samples due to the storage of the ground cost matrix.

The asymptotic complexity does not tell the full story, as these discrete algorithms run much faster than the (theoretically linear time) neural network training. In practice, for high dimensional settings we find a <1%<1\% overhead in including the OT solution per batch (much of which is in the transfer from GPU to CPU and back). We note that this is significantly faster than contemporary works such as DSBM and IBDM, which must train a bridge matching model for every iterative proportional fitting (IPF) step.

PROOFS OF THEOREMS

Theorem 3.1. Under mild regularity conditions, the ODE dx=ut∘(x) dt\mathrm{d}x = u_t^\circ(x)\,\mathrm{d}t generates the marginals ptp_t of P\mathbb{P} from initial conditions p0p_0, and the score is given by (10). The SDE dx=[ut∘(x)+12g(t)2∇log⁡pt(x)] dx+g(t) dt\mathrm{d}x = [u_t^\circ(x) + \frac{1}{2}g(t)^2\nabla\log p_t(x)]\,\mathrm{d}x + g(t)\,\mathrm{d}t generates the Markovization of P\mathbb{P}.

Proof of Theorem 3.1. We assume ut(x∣z)u_t(x\mid z), ∇log⁡pt(x∣z)\nabla\log p_t(x\mid z), and their first derivatives are continuous in xx, uniformly in zz. The first statement is Tong et al. [79], but we reproduce the key derivation here for completeness:

ddtpt(x)=ddt∫pt(x∣z)q(z) dz=∫ddt(pt(x∣z)q(z)) dz=−∫∇⋅(ut∘(x∣z)pt(x∣z)q(z)) dz=−∇⋅(∫ut∘(x∣z)pt(x∣z)q(z) dz)=−∇⋅(ut∘(x)pt(x)),\begin{aligned} \frac{\mathrm{d}}{\mathrm{d}t}p_t(x) &= \frac{\mathrm{d}}{\mathrm{d}t}\int p_t(x\mid z)q(z)\,\mathrm{d}z \\ &= \int\frac{\mathrm{d}}{\mathrm{d}t}\bigl(p_t(x\mid z)q(z)\bigr)\,\mathrm{d}z \\ &= -\int\nabla\cdot\bigl(u_t^\circ(x\mid z)p_t(x\mid z)q(z)\bigr)\,\mathrm{d}z \\ &= -\nabla\cdot\left(\int u_t^\circ(x\mid z)p_t(x\mid z)q(z)\,\mathrm{d}z\right) \\ &= -\nabla\cdot\bigl(u_t^\circ(x)p_t(x)\bigr), \end{aligned}

showing that ptp_t and ut∘u_t^\circ satisfy the continuity equation ddtpt(x)+∇⋅(ut∘(x)pt(x))=0\frac{\mathrm{d}}{\mathrm{d}t}p_t(x) + \nabla\cdot\bigl(u_t^\circ(x)p_t(x)\bigr) = 0, which implies that ut∘u_t^\circ generates ptp_t from initial conditions p0p_0.

To show the score is given by the expression in (10), using that pt(x)=Eq(z)pt(x∣z)p_t(x) = \mathbb{E}_{q(z)}p_t(x\mid z), we have

∇log⁡pt(x)=∇Eq(z)[pt(x∣z)]pt(x)=Eq(z)[∇pt(x∣z)]pt(x)=Eq(z)[pt(x∣z)∇log⁡pt(x∣z)pt(x)],\begin{aligned} \nabla\log p_t(x) &= \frac{\nabla\mathbb{E}_{q(z)}[p_t(x\mid z)]}{p_t(x)} \\ &= \frac{\mathbb{E}_{q(z)}[\nabla p_t(x\mid z)]}{p_t(x)} \\ &= \mathbb{E}_{q(z)}\left[\frac{p_t(x\mid z)\nabla\log p_t(x\mid z)}{p_t(x)}\right], \end{aligned}

as desired.

The Markovization of a mixture of SDEs P\mathbb{P} with a common diffusion rate g(t)g(t) is an SDE dx=ut(x) dt+g(t) dw\mathrm{d}x = u_t(x)\,\mathrm{d}t + g(t)\,\mathrm{d}w, where

ut(xt)=lim⁡Δt→0Ext+Δt∼P(xt+Δt∣xt)[xt+Δt−xtΔt].u_t(x_t) = \lim_{\Delta t\to0}\mathbb{E}_{x_{t+\Delta t}\sim\mathbb{P}(x_{t+\Delta t}\mid x_t)}\left[\frac{x_{t+\Delta t}-x_t}{\Delta t}\right].

Using the definition of P\mathbb{P} as a mixture in (9), we decompose this expectation over the posterior p(z∣xt)=pt(xt∣z)q(z)pt(xt)p(z\mid x_t) = \frac{p_t(x_t\mid z)q(z)}{p_t(x_t)}:

lim⁡Δt→0Ext+Δt∼P(xt+Δt∣xt)[xt+Δt−xtΔt]=lim⁡Δt→0Ez∼p(z∣xt)Ext+Δt∼P(xt+Δt∣xt,z)[xt+Δt−xtΔt]=Ez∼p(z∣xt)lim⁡Δt→0Ext+Δt∼P(xt+Δt∣xt,z)[xt+Δt−xtΔt]=Ez∼p(z∣xt)[ut(xt∣z)].\begin{aligned} \lim_{\Delta t\to0}\mathbb{E}_{x_{t+\Delta t}\sim\mathbb{P}(x_{t+\Delta t}\mid x_t)}\left[\frac{x_{t+\Delta t}-x_t}{\Delta t}\right] &= \lim_{\Delta t\to0}\mathbb{E}_{z\sim p(z\mid x_t)}\mathbb{E}_{x_{t+\Delta t}\sim\mathbb{P}(x_{t+\Delta t}\mid x_t,z)}\left[\frac{x_{t+\Delta t}-x_t}{\Delta t}\right] \\ &= \mathbb{E}_{z\sim p(z\mid x_t)}\lim_{\Delta t\to0}\mathbb{E}_{x_{t+\Delta t}\sim\mathbb{P}(x_{t+\Delta t}\mid x_t,z)}\left[\frac{x_{t+\Delta t}-x_t}{\Delta t}\right] \\ &= \mathbb{E}_{z\sim p(z\mid x_t)}[u_t(x_t\mid z)]. \end{aligned}

The score and probability flow defined in (10) can equivalently be expressed as

ut∘(xt)=Ez∼p(z∣xt)ut∘(xt∣z),∇log⁡pt(xt)=Ez∼p(z∣xt)∇log⁡pt(xt∣z),u_t^\circ(x_t) = \mathbb{E}_{z\sim p(z\mid x_t)}u_t^\circ(x_t\mid z), \qquad\nabla\log p_t(x_t) = \mathbb{E}_{z\sim p(z\mid x_t)}\nabla\log p_t(x_t\mid z),

which, together with ut(x∣z)=ut∘(x∣z)+12g(t)2∇log⁡pt(x∣z)u_t(x \mid z) = u_t^\circ(x \mid z) + \frac{1}{2}g(t)^2\nabla\log p_t(x \mid z), implies that

ut(x)=Ez∼p(z∣x)[ut(x∣z)]=ut∘(x)+12g(t)2∇log⁡pt(x),u_t(x) = \mathbb{E}_{z\sim p(z\mid x)}[u_t(x \mid z)] = u_t^\circ(x) + \frac{1}{2}g(t)^2\nabla\log p_t(x),

as desired.

Theorem 3.2 (Equality of conditional gradients). If pt(x)>0p_t(x) > 0 for all x∈Rdx \in\mathbb{R}^d and t∈[0,1]t \in[0,1], then ∇θLU[SF]2M(θ)=∇θL[SF]2M(θ)\nabla_\theta\mathcal{L}_{\mathrm{U[SF]^2M}}(\theta) = \nabla_\theta\mathcal{L}_{\mathrm{[SF]^2M}}(\theta), where LU[SF]2M(θ)\mathcal{L}_{\mathrm{U[SF]^2M}}(\theta) is the unconditional score and flow matching loss (7).

Proof of Theorem 3.2. We show this individually for the flow matching and score matching parts of the losses. (Note that the equality of gradients of the flow matching parts of U[SF]2M\mathrm{U[SF]^2M} and [SF]2M\mathrm{[SF]^2M} is equivalent to Theorem 3.2 of Tong et al. [79].)

We claim that for any conditional vector field wt∘(x∣z)w_t^\circ(x|z) and wt∘(x):=Eq(z)pt(x∣z)pt(x)wt∘(x∣z)w_t^\circ(x) := \mathbb{E}_{q(z)\frac{p_t(x|z)}{p_t(x)}}w_t^\circ(x|z), and approximating vector field wθ(t,x)w_\theta(t,x), under some regularity conditions on wt(x∣z)w_t(x|z), we have

∇θEz∼q(z),x∼pt(x∣z)[∥wθ(t,x)−wt∘(x∣z)∥2]=∇θEx∼pt(x)[∥wθ(t,x)−wt∘(x)∥2].(15)\nabla_\theta\mathbb{E}_{z\sim q(z),x\sim p_t(x|z)}\left[\left\|w_\theta(t,x)-w_t^\circ(x|z)\right\|^2\right] = \nabla_\theta\mathbb{E}_{x\sim p_t(x)}\left[\left\|w_\theta(t,x)-w_t^\circ(x)\right\|^2\right]. \tag*{(15)}

Assuming this claim, the theorem would follow from applying the claim to wt∘(x∣z)=ut∘(x∣z)w_t^\circ(x|z)=u_t^\circ(x|z) and to wt∘(x∣z)=∇pt(x∣z)w_t^\circ(x|z)=\nabla p_t(x|z) for every value of tt, noting that in these cases wt∘(x)=ut∘(x)w_t^\circ(x)=u_t^\circ(x) and wt∘(x)=∇pt(x)w_t^\circ(x)=\nabla p_t(x), respectively, by Theorem 3.1, and integrating over tt.

We proceed to prove the claim. We drop the distributions in the expectations for conciseness, noting that because pt(x)=Ez∼q(z)p(x∣z)p_t(x)=\mathbb{E}_{z\sim q(z)}p(x|z), no ambiguity is caused: the marginal distribution over xx that stands under the expectation is the same in Ex∼pt(x)\mathbb{E}_{x\sim p_t(x)} and in Ez∼q(z),x∼pt(x∣z)\mathbb{E}_{z\sim q(z),x\sim p_t(x|z)}.

∇θ(Ez,x[∥wθ(t,x)−wt∘(x∣z)∥2]−Ex[∥wθ(t,x)−wt∘(x)∥2])=∇θ(−2Ez,x⟨wθ(t,x),wt∘(x∣z)⟩+2Ex⟨wθ(t,x),wt∘(x)⟩)\begin{aligned} \nabla_\theta\left(\mathbb{E}_{z,x}\left[\left\|w_\theta(t,x)-w_t^\circ(x|z)\right\|^2\right]-\mathbb{E}_x\left[\left\|w_\theta(t,x)-w_t^\circ(x)\right\|^2\right]\right) \\ =\nabla_\theta\left(-2\mathbb{E}_{z,x}\langle w_\theta(t,x),w_t^\circ(x|z)\rangle+2\mathbb{E}_x\langle w_\theta(t,x),w_t^\circ(x)\rangle\right) \end{aligned}

where we rewrote the squared norms as inner products and used that wt∘(x∣z)w_t^\circ(x|z), wt∘(x)w_t^\circ(x) are independent of θ\theta and that wθ(t,x)w_\theta(t,x) is independent of zz. To conclude, we compute

Ex⟨wθ(t,x),wt∘(x)⟩=∬⟨wθ(t,x),wt∘(x)⟩pt(x) dx=∬⟨wθ(t,x),pt(x∣z)pt(x)wt∘(x∣z)q(z) dz⟩pt(x) dx=∬⟨wθ(t,x),wt∘(x∣z)⟩pt(x∣z)q(z) dx dz=Ez,x⟨wθ(t,x),wt∘(x∣z)⟩,\begin{aligned} \mathbb{E}_x\langle w_\theta(t,x),w_t^\circ(x)\rangle &=\iint\langle w_\theta(t,x),w_t^\circ(x)\rangle p_t(x)\,dx \\ &=\iint\left\langle w_\theta(t,x),\frac{p_t(x|z)}{p_t(x)}w_t^\circ(x|z)q(z)\,dz\right\rangle p_t(x)\,dx \\ &=\iint\langle w_\theta(t,x),w_t^\circ(x|z)\rangle p_t(x|z)q(z)\,dx\,dz \\ &=\mathbb{E}_{z,x}\langle w_\theta(t,x),w_t^\circ(x|z)\rangle, \end{aligned}

showing that the difference of gradients vanishes. Note that the above derivation required exchanging the order of integration, which requires some assumptions of regularity at infinity. (Absolute convergence of the integrals is sufficient, and in particular, guaranteed by polynomial growth of in xx of wθw_\theta wt∘(x∣z)w_t^\circ(x|z) and exponential decay of pt(x∣z)p_t(x|z) uniformly in zz.)

Theorem 3.3 ([SF]2M\mathrm{[SF]^2M} recovers marginals from bridges). If q(⋅,⋅)∈U(q0,q1)q(\cdot,\cdot) \in U(q_0,q_1) and vθ∗,sθ∗v_\theta^\ast,s_\theta^\ast globally minimize L[SF]2M(θ)\mathcal{L}_{\mathrm{[SF]^2M}}(\theta), the SDE with drift [vθ∗+12g(t)2sθ∗][v_\theta^\ast+\frac{1}{2}g(t)^2s_\theta^\ast] and diffusion gg, and initial conditions p0=q0p_0=q_0, is the Markovization of the mixture of Brownian bridges from x0x_0 to x1x_1 over q(x0,x1)q(x_0,x_1). In particular, if the SDE generates marginals ptp_t, then p1=q1p_1=q_1.

Proof of Theorem 3.3. The probability flow drift ut∘u_t^\circ and score ∇log⁡pt\nabla\log p_t of the mixture in question are given by Theorem 3.1 shows. By Theorem 3.2, assuming sufficient regularity, optimization of L[SF]2M(θ)\mathcal{L}_{\mathrm{[SF]^2M}}(\theta) is equivalent to optimization of LU[SF]2M(θ)\mathcal{L}_{\mathrm{U[SF]^2M}}(\theta), which is globally minimized when vθ(t,x)=ut∘(x)v_\theta(t,x)=u_t^\circ(x) and sθ(x)=∇log⁡pt(x)s_\theta(x)=\nabla\log p_t(x) for (Lebesgue,pt)(\mathrm{Lebesgue},p_t)-almost all t∈[0,1]t\in[0,1] and x∈Rdx\in\mathbb{R}^d. Moreover, ‘almost all’ implies ‘all’ if ut∘u_t^\circ, ∇log⁡pt\nabla\log p_t, vθv_\theta, sθs_\theta are continuous in tt and xx and ptp_t has full support.

By hypothesis, the vector field ut∘(x)u_t^\circ(x) satisfies the continuity equation jointly with pt(x)=Eq(z)pt(x∣z)p_t(x)=\mathbb{E}_{q(z)}p_t(x|z), which was assumed to satisfy p0(x)=q0(x)p_0(x)=q_0(x) and p1(x)=q1(x)p_1(x)=q_1(x). By the algebraic derivation in §2, ut∘(x)+12g(t)2∇log⁡pt(x)u_t^\circ(x)+\frac{1}{2}g(t)^2\nabla\log p_t(x) and pt(x)p_t(x) jointly satisfy the Fokker-Planck equation. Assuming all derivatives appearing in the Fokker-Planck equation exist and are continuous everywhere, the given SDE generates marginal probabilities ptp_t from initial conditions p0p_0.

Proposition 3.4 ([SF]2^2M with entropic OT recovers the SB process). Let P∗P^* be the Schrödinger bridge between q0q_0 and q1q_1 with respect to Q=σWQ = \sigma W. If vθ∗v_\theta^* globally minimize L[SF]2M\mathcal{L}_{[\mathrm{SF}]^2\mathrm{M}} with coupling π∗=12σ2(q0,q1)\pi^* = \frac{1}{2\sigma^2}(q_0,q_1), then P∗P^* is defined by the SDE with drift [vθ∗+12g(t)2sθ∗][v_\theta^* + \frac{1}{2}g(t)^2s_\theta^*], diffusion gg, and initial conditions p0=q0p_0=q_0.

Proof of Proposition 3.4. This is an immediate consequence of Theorem 3.3, which shows that the SDE learned by [SF]2^2M is the Markovization of a mixture of Brownian bridges, and of Proposition 2.1, which characterizes the SB as a mixture of Brownian bridges with mixture weights given by the entropic OT plan.

FURTHER DISCUSSION ON RELATED WORK

Next we discuss similarities and differences in related algorithms, including deterministic flow models and stochastic score-based generative models.

Flow models

Recently, there has been significant advances in simulation-free training of flow models, which were originally trained using maximum likelihood training in what is termed as continuous normalizing flows ([12, 29]). In this section, we discuss the more recent flow matching techniques, which allow for simulation-free training of flow models. In this paper we show that any deterministic flow model can be converted into a stochastic model with the addition of a conditional score matching loss. This generalizes flow matching ideas to SDEs and provides a simple link between score-based generative modelling and flow-based generative modeling.

Conditional flow matching, terminology introduced by Lipman et al. [44], and extended to dynamic optimal transport in Tong et al. [79]; Pooladian et al. [59], trains with the conditional flow matching loss,

LCFM(θ)=Et∼U(0,1),z∼q(z),x∼pt(x∣z)∥vθ(t,x)−ut∗(x∣z)∥2.(16)\mathcal{L}_{\mathrm{CFM}}(\theta) = \mathbb{E}_{t\sim U(0,1),z\sim q(z),x\sim p_t(x\mid z)}\lVert v_\theta(t,x)-u_t^*(x\mid z)\rVert^2. \tag*{(16)}

for some predefined conditional paths zz, q(z)q(z), ut(x∣z)u_t(x\mid z), and pt(x∣z)p_t(x\mid z). Depending on the choice of conditioning and probability paths we can recover most known flow matching techniques, such as the originally described flow matching (Lipman et al. [44]), action matching (Neklyudov et al. [55]), stochastic interpolants (Albergo and Vanden-Eijnden [2]; Albergo et al. [1]), the 1-rectified flow (Liu [47]), optimal transport conditional flow matching (OT-CFM) (Tong et al. [79]) also known as multisample flow matching (Pooladian et al. [59]), and its deterministic Schrödinger bridge counterpart, Schrödinger bridge conditional flow matching (SB-CFM) (Tong et al. [79]).

SDEs vs. ODEs. Flow models are a powerful way to learn deterministic dynamics which are often faster to sample from Song et al. [72], particularly with ideas from dynamic optimal transport (Tong et al. [79]; Pooladian et al. [59]). However, recent work (Liu et al. [46]; Shi et al. [67]) has noted advantages of stochastic dynamics which we also observe (see Table 2 and Table 3), particularly in high dimensional settings and in terms of generative performance. In this work, we also seek to model an inherently stochastic system, where there is randomness introduced based on a variety of external factors. In particular, the fact that a single-cell develops into a whole organism, and similarly, the fact that a single population of stem cells develops into a multitude of different cell types, requires the modelling with stochastic dynamics that can model complex conditional distributions. While it is possible to approximate the conditional distribution with lineage-tracing techniques (Kester and van Oudenaarden, [35]; Wagner and Klein, [84]; Klein et al., [37]), these are biologically complex, and we leave their analysis to future work.

Metric →\toW2W_2 (↓\downarrow)Normalized Path Energy (↓\downarrow)
Algorithm ↓\downarrowDataset →\toN→8N\to8gaussiansmoons→8\to8gaussiansN→N\tomoonsN→N\toscurveN→8N\to8gaussiansmoons→8\to8gaussiansN→N\tomoonsN→N\toscurve
[SF]2^2M-Exact0.275±0.058\mathbf{0.275}\pm0.0580.726±0.1370.726\pm0.1370.124±0.023\mathbf{0.124}\pm0.0230.128±0.005\mathbf{0.128}\pm0.0050.016±0.012\mathbf{0.016}\pm0.0120.045±0.0310.045\pm0.0310.053±0.038\mathbf{0.053}\pm0.0380.034±0.0240.034\pm0.024
[SF]2^2M-I0.393±0.0540.393\pm0.0541.482±0.1511.482\pm0.1510.185±0.0280.185\pm0.0280.201±0.0620.201\pm0.0620.160±0.0190.160\pm0.0192.577±0.3232.577\pm0.3230.855±0.1300.855\pm0.1300.845±0.1060.845\pm0.106
DSBM-IPF (Shi et al. [67]) *0.315±0.0790.315\pm0.0790.812±0.0920.812\pm0.0920.140±0.0060.140\pm0.0060.140±0.0240.140\pm0.0240.022±0.0200.022\pm0.0200.244±0.0270.244\pm0.0270.383±0.0340.383\pm0.0340.297±0.0360.297\pm0.036
DSBM-IMF (Shi et al. [67]) *0.338±0.0910.338\pm0.0910.838±0.0980.838\pm0.0980.144±0.0240.144\pm0.0240.145±0.0370.145\pm0.0370.029±0.0170.029\pm0.0170.345±0.0490.345\pm0.0490.230±0.0280.230\pm0.0280.286±0.0330.286\pm0.033
DSB (De Bortoli et al. [16]) *0.411±0.0840.411\pm0.0840.987±0.3240.987\pm0.3240.190±0.0490.190\pm0.0490.272±0.0650.272\pm0.065————
OT-CFM (Tong et al. [79])0.303±0.0430.303\pm0.0430.601±0.027\mathbf{0.601}\pm0.0270.130±0.0160.130\pm0.0160.144±0.0280.144\pm0.0280.031±0.0270.031\pm0.0270.015±0.010\mathbf{0.015}\pm0.0100.083±0.0090.083\pm0.0090.027±0.012\mathbf{0.027}\pm0.012
SB-CFM (Tong et al. [79])2.314±2.1122.314\pm2.112—0.434±0.5940.434\pm0.5940.341±0.4680.341\pm0.4681.000±0.0001.000\pm0.000—0.995±0.0000.995\pm0.0000.745±0.0390.745\pm0.039
RF (Liu [47])0.421±0.0710.421\pm0.0711.525±0.3301.525\pm0.3300.283±0.0450.283\pm0.0450.345±0.0790.345\pm0.0790.044±0.0310.044\pm0.0310.203±0.0900.203\pm0.0900.130±0.0780.130\pm0.0780.099±0.0660.099\pm0.066
I-CFM (Tong et al. [79])0.373±0.1030.373\pm0.1031.557±0.4071.557\pm0.4070.178±0.0140.178\pm0.0140.242±0.1410.242\pm0.1410.202±0.0550.202\pm0.0552.680±0.2922.680\pm0.2920.891±0.1200.891\pm0.1200.856±0.0310.856\pm0.031
FM (Lipman et al. [44])0.343±0.0580.343\pm0.058—0.209±0.0550.209\pm0.0550.198±0.0370.198\pm0.0370.190±0.0540.190\pm0.054—0.762±0.0990.762\pm0.0990.743±0.1160.743\pm0.116

Table 2. Two-dimensional data: generative modeling performance (W2W_2) and dynamic OT optimality (NPE) divided into SDE methods (top) and ODE methods (bottom). [SF]2^2M performs the best on 3 of 4 datasets and is similar to OT-CFM, which is equivalent to [SF]2^2M as g(t)→0g(t)\to0. *Indicates results taken from Shi et al. [67].

Metric →KL(p1,p1∗p_1,p_1^*)Mean KL(pt,pt∗p_t,p_t^*)
Alg. ↓ | Dim. →5205052050
[SF]2^2M-Exact0.007±0.0000.029±0.0020.124±0.0030.006±0.0000.028±0.0010.258±0.001
DSBM-IPF0.015±0.0050.132±0.0040.528±0.0130.005±0.0020.050±0.0020.221±0.004
DSB8.757±—49.963±—221.213±—8.757±—49.963±—221.213±—
SB-CFM0.001±0.0000.034±0.0030.170±0.0020.008±0.0000.086±0.0020.447±0.003

Table 3. Gaussian-to-Gaussian Schrödinger bridges with 10410^4 datapoints between a Gaussian with parameters estimated from empirical samples (ptp_t) with error to the continuous Schrödinger bridge marginals (pt∗p_t^*) either at the target distribution (left) or averaged across 21 timepoints (right).

Learning Schrödinger bridges

Schrödinger bridge models have been used as the source-conditioned variation of score-based generative models, which can be conditioned on a variety of source distributions including dirac (Wang et al., [85]), and from data or noised data (Somnath et al., [71]; Liu et al., [46]). Most algorithms are based on mean-matching, which is simulation-based and requires simulating, storing, and matching whole trajectories [16], with similar algorithms introduced by [82, 13]. In particular, these algorithms parameterize a forward drift vθfv_\theta^f and backwards drift vθbv_\theta^b, simulating trajectories in one direction and training the reverse direction to match them. Recent work extends this to Markovian bridges (termed bridge matching) [67, 58], which greatly improves performance.

Practical implications of Schrödinger bridge modeling choices

Approximation error. All known algorithms for learning Schrödinger bridges for general distributions can only approximate the Schrödinger bridge. Approximation error accumulates from a number of sources, which can roughly be categorized into the following areas:

  1. Error in the static joint optimization π^(x0,x1)\hat{\pi}(x_0,x_1) approximating the true joint π∗(x0,x1)\pi^*(x_0,x_1). Since there is no closed form for this optimization, all approximations are iterative and discrete. Error in this distribution accumulates in two places, and can be divided into error on the marginals ∣π^(x0,⋅)−q(x0)∣|\hat{\pi}(x_0,\cdot)-q(x_0)|, ∣π^(⋅,x1)−q(x1)∣|\hat{\pi}(\cdot,x_1)-q(x_1)|, and error on the joint ∣π^(x0,x1)−π∗(x0,x1)∣|\hat{\pi}(x_0,x_1)-\pi^*(x_0,x_1)|: (a) Marginal and Joint error from using a finite number of iterations (IPF underfitting). IPF both in continuous space (as used by mean-matching and bridge matching) and IPF in discrete space (as used by [SF]²M) are run for a finite number of iterations. Continuous space IPF is much more expensive (involving fitting and simulating neural networks) and is thus is used with tens of iterations, often L=20L=20 [16, 68]. In contrast, discrete space IPF uses many more iterations. We use the default python optimal transport (POT) parameters with Lmax⁡=1000L_{\max}=1000 with early stopping if the marginal error is <10−9<10^{-9} [23]. The discrete OT computation adds a negligible (<1%<1\%) computational overhead in [SF]²M. (b) Joint error from minibatch approximation (discrete IPF only). By using discrete OT solvers, we accumulate discretization error between by using finite batch sizes. This affects the recovery of the true Schrödinger bridge, but does not affect the marginal error, which is the important error for generative modeling performance at the endpoints. As batch size →∞\to\infty, this error goes to zero; for a finite dataset of small enough size, [SF]²M can use full-batch discrete entropic OT, where the batch size used for OT can be larger than that used for neural network training.

In practice, [SF]²M, by using discrete OT solvers, trades off increased error in the joint via minibatch approximation error for reduced error from IPF underfitting. It is difficult to bound these errors theoretically, however, our experiments show that this tradeoff is useful in practice. We leave further theoretical investigation to future work.

  1. Finite sample error. Datasets are often finite (i.e., discrete). Approximating the continuous densities from discrete samples is challenging and accumulates error.

  1. Neural network fitting approximation (applicable to all neural SDE approximations to Schrödinger bridges).

  1. Discretization error. Simulation-free objectives like [SF]²M treat time as a continuous variable, but, at inference time, error accumulates from integration in discrete time (e.g., using an Euler-Maruyama scheme). We note that simulation-based objectives, such as that of DSB [16], also train in a fixed time discretization, inducing a further approximation error.

Iterative fitting. Both mean-matching and bridge matching Schrödinger bridge methods require an outer IPF step, which samples data to train for each inner neural network optimization step (Table 1). At each step, new data is resampled to determine the boundary distributions of the next iteration (Alg. 3). This multiplies the training time by LL (the number of outer loops), and cannot guarantee that that the neural networks match the right endpoint marginals until the outer IPF step has converged.

In contrast, [SF]²M is always optimizing for the correct marginals, but at the cost of a biased Schrödinger bridge due to bias in the minibatch OT. We hypothesize that this is one of the reasons that [SF]²M has better generative modeling performance than mean-matching or bridge-matching methods.

In summary, we recommend using DSBM / IDBM when approximating the true Schrödinger bridge is important and the computational budget is large. We recommend using [SF]²M when the computational budget is small or when the generative performance is more important than matching the true Schrödinger bridge process.

Table 7: Gaussian-to-Gaussian Schrödinger bridges with 10,000 datapoints. Here we test Sinkhorn-Exact which uses the exact OT (default), against the Sinkhorn algorithm for the static OT within batches, and using outer loops where we simulate 10,000 trajectories for further training 20 times following Shi et al. [67].

Additional Results and Ablations

Figure 5. Learned ODE (top) and SDE (bottom) simulations for σ∈[0.1,1,2,3]\sigma\in[0.1, 1, 2, 3] from left to right for trained [SF]2^{2}M model. The marginals match regardless of the chosen σ\sigma. Trajectory initializations are matched between runs.

Looped SF2M

As previously discussed, the majority of Schrödinger bridge algorithms to date have used outer iterations to perform iterative proportional fitting on the continuous distributions. This can create marginals closer to the true Schrödinger bridge marginals at the cost of additional computation, and potentially worse generative modelling performance. [SF]2^{2}M is the first Schrödinger bridge method to approximate Schrödinger bridges without performing the iterative proportional fitting in continuous time and space, instead using much more efficient iterations in the static, discrete OT setting.

However, [SF]2^{2}M is compatible with outer looping. In Table 7 we see that outer looping (with 20 outer loops following Shi et al. [67]) produces better Schrödinger bridge marginals, but worse marginals at time 1 indicating worse generative performance. We note that outer looping takes much longer to train as [SF]2^{2}M effectively takes a single outer loop, and may have advantages even over a single outer loop as shown in [79, 59] where the static solution sped up training in the deterministic setting.

Dim[SF]2^{2}M-Sinkhorn[SF]2^{2}M-Exact[SF]2^{2}M-Exact-Looped
KL(p1,q1p_1, q_1)20.002 ± 0.0000.003 ± 0.0000.032 ± 0.009
50.004 ± 0.0010.007 ± 0.0000.088 ± 0.011
200.029 ± 0.0010.029 ± 0.0020.293 ± 0.021
500.122 ± 0.0030.124 ± 0.0030.610 ± 0.033
1000.493 ± 0.0100.486 ± 0.0051.578 ± 0.026
Mean KL(pt,qtp_t, q_t)20.001 ± 0.0000.004 ± 0.0000.006 ± 0.002
50.004 ± 0.0000.006 ± 0.0000.019 ± 0.003
200.042 ± 0.0010.028 ± 0.0010.080 ± 0.006
500.276 ± 0.0010.258 ± 0.0010.243 ± 0.012
1001.000 ± 0.0070.977 ± 0.0030.792 ± 0.008

Table 7. Gaussian-to-Gaussian Schrödinger bridges with 10,000 datapoints. Here we test Sinkhorn-Exact which uses the exact OT (default), against the Sinkhorn algorithm for the static OT within batches, and using outer loops where we simulate 10,000 trajectories for further training 20 times following Shi et al. [67].

Vector fields at $t = 0.00$, $0.17$, $0.33$, $0.50$, $0.67$, $0.83$, and $1.00$

Figure 6. From top to bottom vθ(t,x)v_\theta(t, x), sθ(t,x)s_\theta(t, x) and ut(x)u_t(x) inferred through (5) for the 8-Gaussians to moons dataset.

Here we accomplish outer looping by simulating 5,000 (stochastic) trajectories from the backwards SDE and 5,000 trajectories from the forwards SDE. We then use the start and end points of these trajectories as samples from the approximate static OT matrix in the next iteration. This algorithm is detailed in Alg. 3. We always set nn (the number of samples per outer loop) to the size of the empirical dataset, fix the number of outer loops to 20, and the number inner loops to the [SF]2M[\mathrm{SF}]^{2}\mathrm{M} without outer loops divided by 20. This gives the same number of gradient descent steps for all methods, but we note that the outer loop methods require simulation for each outer loop. This adds additional computation cost.

On the choice of static OT method: Sinkhorn vs. Exact

As the minibatch size gets large, [SF]2M[\mathrm{SF}]^{2}\mathrm{M} with entropic OT with ϵ=2σ2\epsilon= 2\sigma^{2} is the correct choice. However, with minibatching, we want a smaller ϵ\epsilon. In practice we often use ϵ=0\epsilon= 0 corresponding to exact (unregularized) optimal transport. We test this on the Gaussian-to-Gaussian experiment in Table 7. Here we see that [SF]2M[\mathrm{SF}]^{2}\mathrm{M} with sinkhorn OT works better in low dimensions, but struggles in high dimensions. We believe this is because minibatch-OT effectively adds more entropy in higher dimensions. More experimentation and theory is needed to determine the optimal setting of ϵ\epsilon for a given dataset and minibatch size.

Extra experiments on Cifar10

We have conducted experiments on Cifar 10 using the code from Tong et al. [79] and the experimental evaluation from Shi et al. [67]. Results are gathered in Table 8.

[SF]2M[\mathrm{SF}]^{2}\mathrm{M}I-CFMOT-CFMDSBMFMRF
4.1454.3814.4564.5114.6116.01

Table 8. CIFAR-10 FID using 100-step Euler integration. First 4 models trained with batch size 128 for 16 A100-hours. Last 2 models from the DSBM paper, trained for ∼200\sim200 A100-hours. [SF]2M[\mathrm{SF}]^{2}\mathrm{M} performs better than DSBM (with 1/12 the compute) and the deterministic methods (I-CFM, OT-CFM, FM). Better performance can be obtained by considering higher-order or adaptive step solvers.

SCHRÖDINGER BRIDGES WITH VARYING DIFFUSION RATE

Algorithm 3 Looped Minibatch Simulation-Free Score and Flow Matching Training

Input: Samplable source and target q0q_0, q1q_1, number of outer loop iterations LL, inner loop iterations II, cache size nn, noise term σ\sigma, weighting schedule λ(t)\lambda(t), initial networks vθv_\theta and sθs_\theta.

for Outer loop l∈[1,…,L]l \in[1,\ldots,L] do &nbsp;&nbsp;&nbsp;&nbsp;for Inner loop i∈[1,…,I]i \in[1,\ldots,I] do &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if l=0l=0 then &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x0,x1∼q0⊗m,q1⊗mx_0,x_1 \sim q_0^{\otimes m},q_1^{\otimes m} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;π←Sinkhorn⁡(x0,x1,2σ2)\pi\leftarrow\operatorname{Sinkhorn}(x_0,x_1,2\sigma^2) ▹\triangleright Or OT⁡(x0,x1)\operatorname{OT}(x_0,x_1) see §A.1 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x0,x1∼π⊗mx_0,x_1 \sim\pi^{\otimes m} ▹\triangleright Resample OT pairs from π\pi &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x0,x1∼T⊗mx_0,x_1 \sim\mathbb{T}^{\otimes m} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;t∼U(0,1)t \sim\mathcal{U}(0,1) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;pt(x∣x0,x1)←N(x;tx1+(1−t)x0,σ2t(1−t))p_t(x\mid x_0,x_1) \leftarrow\mathcal{N}(x;tx_1+(1-t)x_0,\sigma^2t(1-t)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x∼pt(x∣x0,x1)x \sim p_t(x\mid x_0,x_1) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;L[SF]2M←∥vθ(t,x)−ut∗(x∣x0,x1)∥2+λ(t)2∥sθ(t,x)−∇xlog⁡pt(x∣x0,x1)∥2\mathcal{L}_{[\mathrm{SF}]^2\mathrm{M}} \leftarrow\lVert v_\theta(t,x)-u_t^*(x\mid x_0,x_1)\rVert^2+\lambda(t)^2\lVert s_\theta(t,x)-\nabla_x\log p_t(x\mid x_0,x_1)\rVert^2 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;θ←Update⁡(θ,∇θL[SF]2M)\theta\leftarrow\operatorname{Update}(\theta,\nabla_\theta\mathcal{L}_{[\mathrm{SF}]^2\mathrm{M}}) &nbsp;&nbsp;&nbsp;&nbsp;Tf←(x0,x^1)⊗n/2T_f \leftarrow(x_0,\hat{x}_1)^{\otimes n/2} ▹\triangleright where x^1\hat{x}_1 is sampled according to Alg. 2 &nbsp;&nbsp;&nbsp;&nbsp;Tb←(x^0,x1)⊗n/2T_b \leftarrow(\hat{x}_0,x_1)^{\otimes n/2} ▹\triangleright where x^0\hat{x}_0 is sampled according to the backwards analog of Alg. 2 &nbsp;&nbsp;&nbsp;&nbsp;T←[Tf,Tb]T \leftarrow[T_f,T_b] return vθ,sθv_\theta,s_\theta

SCHRÖDINGER BRIDGES WITH VARYING DIFFUSION RATE

While we consider constant diffusion for the majority of this paper, the theory also applies for time varying diffusion with the variation as specified in the following Lemma.

Lemma E.1 (Brownian bridge with time-varying diffusion). Suppose xtx_t is a stochastic process with values in functions [0,1]→Rd[0,1]\to\mathbb{R}^d, defined by initial conditions x0=ax_0=a and SDE dxt=σ(t)dwt\mathrm{d}x_t=\sigma(t)\mathrm{d}w_t, where σ(t)\sigma(t) is continuous and positive on (0,1)(0,1). Define F(t)=∫0tσ2(s) dsF(t)=\int_0^t\sigma^2(s)\,\mathrm{d}s. Then xtx_t satisfies

xt∼N(a,F(t))x_t\sim\mathcal{N}(a,F(t))
xt∣x1=b∼N(a+(b−a)F(t)F(1),F(t)−F(t)2F(1)).x_t\mid x_1=b\sim\mathcal{N}\left(a+(b-a)\frac{F(t)}{F(1)},F(t)-\frac{F(t)^2}{F(1)}\right).

Proof. The constraints on σ\sigma guarantee that FF has a unique inverse F−1F^{-1} on [0,F(1)][0,F(1)]. Consider the process

yt=xF−1(F(1)t)−aF(1),y_t=\frac{x_{F^{-1}(F(1)t)}-a}{\sqrt{F(1)}},

which is equivalently characterized by

xt=a+F(1)yF(t)/F(1).x_t=a+\sqrt{F(1)}y_{F(t)/F(1)}.

A straightforward computation using the chain rule shows that yty_t satisfies y0=0y_0=0 and dyt=dwt\mathrm{d}y_t=\mathrm{d}w_t, i.e., yty_t is Brownian motion.

By standard facts about Brownian bridges, we have

yt∼N(0,t)yt∣y1=b−aF(1)∼N(b−aF(1)t,t(1−t)).\begin{aligned} y_t &\sim\mathcal{N}(0,t)\\ y_t \mid y_1 &= \frac{b-a}{\sqrt{F(1)}} \sim\mathcal{N}\left(\frac{b-a}{\sqrt{F(1)}}t,t(1-t)\right). \end{aligned}

The result follows by applying the reverse transformation to obtain the marginals of xtx_t.

Because Markovization commutes with time reparametrization, and the SB is the Markovization of a mixture of Brownian bridges, this immediately implies:

Corollary E.2. The solution pp to the SB problem with reference process dxt=σ(t)dwtd x_t = \sigma(t)d w_t has marginal p(x0,x1)=π2F(1)(x0,x1)p(x_0,x_1) = \pi_{2F(1)}(x_0,x_1).

EXPERIMENTAL DETAILS

Algorithm 4 Minibatch Optimal Transport Simulation-Free Score and Flow Matching Training

Input: Samplable source and target q0q_0, q1q_1, noise term σ\sigma, weighting schedule λ(t)\lambda(t), initial networks vθv_\theta and sθs_\theta.

while Training do

t∼U(0,1)t \sim\mathcal{U}(0,1)

x0,x1∼q0⊗m,q1⊗mx_0,x_1 \sim q_0^{\otimes m},q_1^{\otimes m}

π←Sinkhorn⁡(x0,x1,2σ2)\pi\leftarrow\operatorname{Sinkhorn}(x_0,x_1,2\sigma^2) ▷ Or OT⁡(x0,x1)\operatorname{OT}(x_0,x_1) see §A.1

x0,x1∼π⊗mx_0,x_1 \sim\pi^{\otimes m} ▷ Resample OT pairs from π\pi

pt(x∣x0,x1)←N(x;tx1+(1−t)x0,σ2t(1−t))p_t(x\mid x_0,x_1) \leftarrow\mathcal{N}(x;tx_1+(1-t)x_0,\sigma^2t(1-t))

x∼pt(x∣x0,x1)x \sim p_t(x\mid x_0,x_1)

L[SF]2M←∥vθ(t,x)−ut(x∣x0,x1)∥2+λ(t)2∥sθ(t,x)−∇xlog⁡pt(x∣x0,x1)∥2\mathcal{L}_{[\mathrm{SF}]^2\mathrm{M}} \leftarrow\lVert v_\theta(t,x)-u_t(x\mid x_0,x_1)\rVert^2+\lambda(t)^2\lVert s_\theta(t,x)-\nabla_x\log p_t(x\mid x_0,x_1)\rVert^2 ▷ see (8, 11)

θ←Update⁡(θ,∇θL[SF]2M)\theta\leftarrow\operatorname{Update}(\theta,\nabla_\theta\mathcal{L}_{[\mathrm{SF}]^2\mathrm{M}})

return vθ,sθv_\theta,s_\theta

Implementation details and settings

Throughout we use networks of three layers of width 64 with SeLU activations [36] except for the 1000 dimensional experiment where we use width 256, and for the neural graphical model (NGM) model used in the gene regulatory network recovery task. For optimization we use ADAM-W [49] with learning rate 10−310^{-3} and weight decay 10−510^{-5}. We train for 1,000 epochs unless otherwise noted. The flow network and score networks always have exactly the same structure. We provide a more detailed picture of the algorithm used in Alg. 4. For sampling we always take 100 integration steps with either the Euler integrator for ODEs or Euler-Maruyama integrator for SDEs, except for the Gaussian experiments where we take 20 steps to match the setup of De Bortoli et al. [16]; Shi et al. [67]. When there are multiple timepoints (e.g., single-cell trajectories) we take 100 steps between each timepoint for a total of 100k steps for all methods. We use σ=1\sigma= 1 unless otherwise noted.

Weighting schedule λ(t)\lambda(t)

Similar to other score and diffusion-based losses, the [SF]2M[\mathrm{SF}]^2\mathrm{M} loss is defined with a weighting schedule λ(t)\lambda(t). Since ∇log⁡pt(x∣z)\nabla\log p_t(x\mid z) goes to infinity as tt tends to zero or one, we must standardize the loss to be roughly even over time. We set λ(t)\lambda(t) such that the target has zero mean and unit variance, i.e., we predict the noise added in sampling xx from μt\mu_t before multiplying by σt(1−t)\sigma\sqrt{t(1-t)}. This leads to the setting:

λ(t)=σt=σt(1−t)(17)\lambda(t)=\sigma_t=\sigma\sqrt{t(1-t)} \tag*{(17)}

this weighting schedule ensures that the regression target for sθs_\theta is distributed N(0,1)\mathcal{N}(0,1).

We also experiment with directly regressing sθs_\theta against the scaled target 12σ2∇xlog⁡pt(x∣z)\frac{1}{2}\sigma^2\nabla_x \log p_t(x|z), with a different weighting function

λ(t)=2σt2σt=2t(1−t)σ(18)\lambda(t) = \frac{2}{\sigma_t^2}\sigma_t = \frac{2\sqrt{t(1-t)}}{\sigma} \tag*{(18)}

which also ensures the regression target for σ\sigma is distributed N(0,1)\mathcal{N}(0,1). With this λ\lambda, and since ∇xlog⁡pt(x∣z)\nabla_x \log p_t(x|z) with a Gaussian pt(x∣z)p_t(x|z) can be simplified to −ϵ/σt-\epsilon/\sigma_t where ϵ∼N(0,1)\epsilon\sim\mathcal{N}(0,1) we have the simplified objective:

λ(t)2∥sθ(t,x)−∇xlog⁡pt(x∣x0,x1)∥2=∥λ(t)sθ(t,x)−λ(t)∇xlog⁡pt(x∣x0,x1)∥2(19)\lambda(t)^2\left\|s_\theta(t,x)-\nabla_x\log p_t(x|x_0,x_1)\right\|^2 = \left\|\lambda(t)s_\theta(t,x)-\lambda(t)\nabla_x\log p_t(x|x_0,x_1)\right\|^2 \tag*{(19)}
=∥λ(t)sθ(t,x)+ϵt∥2(20)= \left\|\lambda(t)s_\theta(t,x)+\epsilon_t\right\|^2 \tag*{(20)}

This is also numerically stable as it avoids dividing by anything that approaches zero. We leave improved weighting schedules to future work. In practice we use the schedule in (18) and the simplified objective in (20).

Static optimal transport

As discussed in §A.1 it is sometimes preferable to use exact optimal transport instead of entropic optimal transport. In addition to the “entropy” added by minibatching, there are also numerical and practical considerations. In practice, we find that for batches of size <10000< 10000, implementations of exact OT through the Python Optimal Transport package (POT) [23] are often faster than implementations of the Sinkhorn algorithm [14], as the Sinkhorn algorithm is known to have numerical difficulties and needs many iterations for good approximation of the true entropic transport for small values of σ\sigma.

Computational resources

All experiments were performed on a shared heterogeneous high-performance-computing cluster. This cluster is primarily composed of GPU nodes with RTX8000, A100, and V100 Nvidia GPUs, and CPU nodes with 32 and 64 CPUs.

Two-dimensional experimental details

For the two-dimensional experiments we follow the setup from Shi et al. [67]. This is adapted from the setup of Tong et al. [79] except using larger test sets for lower variance in the empirical estimation of the Wasserstein distance. We use a training set size of 10,000, a validation set size of 10,000, and a test set size of 10,000 for all methods and models.

We evaluate the empirical 2-Wasserstein distance for 10,000 forward samples from our model pushing the source distribution to the target. The number reported for W2W_2 is then

W2=(min⁡π∈U(p^1,q1)∫∥x−y∥22dπ(x,y))1/2(21)W_2 = \left(\min_{\pi\in U(\hat{p}_1,q_1)} \int\|x-y\|_2^2d\pi(x,y)\right)^{1/2} \tag*{(21)}

where p^1\hat{p}_1 is sampled via Alg. 2, and q1q_1 is the test set.

As mentioned in the main text, we also measure the Normalized Path Energy. We note that this is only defined for ODE integration, hence for stochastic methods, (i.e., [SF]2^2M, DSBM) we measure the normalized path energy of the probability flow ODE (see (4)). The normalized path energy measures the relative deviation of the path energy of the model (∫∥vθ(t,x)∥2)\left(\int\|v_\theta(t,x)\|^2\right) to the path energy of the optimal paths (W22(q0,q1)W_2^2(q_0,q_1)), which is equivalent to the squared 2-Wasserstein distance between the test set source and the test set target. More formally, the normalized path energy can be calculated as

NPE(q0,q1,vθ)=∣Ex(0)∼q0∫∥vθ(t,xt)∥2dt−W22(q0,q1)∣W22(22)NPE(q_0,q_1,v_\theta) = \frac{\left|\mathbb{E}_{x(0)\sim q_0}\int\|v_\theta(t,x_t)\|^2dt-W_2^2(q_0,q_1)\right|}{W_2^2} \tag*{(22)}

where xtx_t is the solution of the probability flow ODE with dx=vθ(t,x)dtdx=v_\theta(t,x)dt with initial condition x0x_0. This measures how close the paths defined by vθ(t,x)v_\theta(t,x) are to the optimal transport paths in terms of average energy. We note that measuring the path energy rather than the length (W22W_2^2 instead of W1W_1) has the additional benefit that the energy differentiates between models that follow the same paths, but at different rates, encouraging constant rate models.

Gaussian-to-Gaussian experimental details

Gaussian-to-Gaussian experimental details

Similar to experiments in De Bortoli et al. [16]; Shi et al. [67], we train on a sample of 10,000 points from a N(−0.1,I)\mathcal{N}(-0.1,I) source to 10,000 points sampled from a N(0.1,I)\mathcal{N}(0.1,I) target, for dimensions 5, 20, and 50. We could not find all the details of those previous experiments but we match what we can here. Since we know the closed-form solution to the Schrödinger bridge from Mallasto et al. [50]; Bunne et al. [9] qtq_t, we can compare our estimate of the marginal at time tt (p^t\hat{p}_t) with the true distribution at time tt. In particular, we compare a Gaussian approximation of p^t\hat{p}_t, p~t\tilde{p}_t with mean and covariance estimated from 10,000 samples of the model with qtq_t which has the form

qt(x)=N(x;0.2t−0.1,(t(1−t)4+σ4+(1−t)2+t2)I)(23)q_t(x) = \mathcal{N}\left(x; 0.2t - 0.1, \left(t(1-t)\sqrt{4+\sigma^4}+(1-t)^2+t^2\right)I\right) \tag*{(23)}

with the KL divergence.

We compare either the average KL over 21 timepoints (including the start and end timepoints) i.e.,

KL‾=120∑k=020KL(p~k/20∥qk/20)(24)\overline{\mathrm{KL}} = \frac{1}{20}\sum_{k=0}^{20}\mathrm{KL}(\tilde{p}_{k/20}\|q_{k/20}) \tag*{(24)}

to measure how closely the learned flow matches the true Schrödinger bridge marginals, and we also compare the KL divergence at time t=1t = 1, to measure the performance as a generative model.

KL(p~1∥q1)(25)\mathrm{KL}(\tilde{p}_1\|q_1) \tag*{(25)}

Waddington's landscape experimental details

We use two Waddington landscapes, one Gaussian to two Gaussians and cross-sectional measurements of Embryoid Body (EB) data, to demonstrate the versatility of [SF]²M for trajectory inference. The three dimensions of the landscape are space, time and potential.

More specifically, the space dimension is evolved according to the drift of the SDE by ut(x)=−∇xW(t,x)u_t(x) = -\nabla_x W(t,x). The potential dimension is the Waddington’s landscape by W:=Ev+12g(t)2EsW := E_v + \frac{1}{2}g(t)^2 E_s, where vθ(t,x)=−∇xEv(t,x)v_\theta(t,x) = -\nabla_x E_v(t,x) and sθ(t,x)=−∇xEs(t,x)s_\theta(t,x) = -\nabla_x E_s(t,x) are the flow and score for Langevin dynamics. EsE_s and EvE_v are both parameterized by three layer neural networks of width 64, the only difference with our standard implementation of vθv_\theta and sθs_\theta is that they have output dimension width of one instead of dd.

For the experiment of one Gaussian to two Gaussians, we train on a sample of 256 points from the one-dimensional source N(0,0.1)\mathcal{N}(0,0.1) to 256 points sampled from the one-dimensional target N(−1,0.1)∪N(1,0.1)\mathcal{N}(-1,0.1) \cup\mathcal{N}(1,0.1) for 10,000 steps. We then plot 20 trajectories from the source to the target with the potentials following from the gradient descend of WW.

For the cross-sectional measurements from the embryoid body (EB) data, we first embed the data in one dimension with the non-linear dimensionality reduction technique PHATE (Moon et al. [53]), which we then whiten to ensure the data is at a reasonable scale for the neural network initialization. We train the [SF]²M model following Alg. 5 for 50,000 steps and plot 100 stochastic trajectories along with the height of W(t,x)W(t,x) normalized so to gradually descend over time.

Single-cell interpolation experimental details

Here we perform two comparisons, the first matching the setup of Tong et al. [80] in low dimensions and the second exploring higher dimensional single-cell interpolation. Following Huguet et al. [34], we repurpose the CITE-seq and Multiome datasets from a recent NeurIPS competition for this task (Burkhardt et al., [11]) as well as the Embryoid-body data from Moon et al. [53]; Tong et al. [80], which has 5 population measurements over 30 days.

For the Embryoid body (EB) data, we use the same processed artifact which contains the first 100 principal components of the data. For our tests in Table 4, we truncate to the first five dimensions, then whiten each dimension following Tong et al. [80] before interpolation. For the Embryoid body (EB) dataset which consists of 5 timepoints collected over 30 days we train separate models leaving out times 1, 2, 3 in turn. During testing we

Algorithm 5 Trajectory Simulation-Free Score and Flow Matching Training

Input: Samplable source and target Q={q0,⋯ ,qK−1}Q = \{q_0, \cdots, q_{K-1}\}, noise term σ\sigma, weighting schedule λ(t)\lambda(t), initial networks vθv_\theta and sθs_\theta.

while Training do

for k∈[0,⋯ ,K−2]k \in[0, \cdots, K - 2] do

xk,xk+1∼qk⊗m,qk+1⊗mx_k, x_{k+1} \sim q_k^{\otimes m}, q_{k+1}^{\otimes m}

π←Sinkhorn⁡(xk,xk+1,2σ2)\pi\leftarrow\operatorname{Sinkhorn}(x_k, x_{k+1}, 2\sigma^2) ▷ Or OT⁡(xk,xk+1)\operatorname{OT}(x_k, x_{k+1}) see §A.1

Xk∼π⊗mX_k \sim\pi^{\otimes m} ▷ Resample OT pairs from π\pi

k∼U(1,K)⊗mk \sim\mathcal{U}(1, K)^{\otimes m}

t∼U(0,1)⊗mt \sim\mathcal{U}(0, 1)^{\otimes m}

x0i,x1i←Xkix_0^i, x_1^i \leftarrow X_k^i

pt(x∣x0,x1)←N(x;tx1+(1−t)x0,σ2t(1−t))p_t(x|x_0, x_1) \leftarrow\mathcal{N}(x; tx_1 + (1 - t)x_0, \sigma^2 t(1 - t))

x∼pt(x∣x0,x1)x \sim p_t(x|x_0, x_1)

L[SF]2M←∥vθ(t+k,x)−ut(x∣x0,x1)∥2+λ(t)∥sθ(t+k,x)−∇xlog⁡pt(x∣x0,x1)∥2\mathcal{L}_{[\mathrm{SF}]^2\mathrm{M}} \leftarrow\|v_\theta(t + k, x) - u_t(x|x_0, x_1)\|^2 + \lambda(t)\|s_\theta(t + k, x) - \nabla_x \log p_t(x|x_0, x_1)\|^2

θ←Update⁡(θ,∇θL[SF]2M)\theta\leftarrow\operatorname{Update}(\theta, \nabla_\theta\mathcal{L}_{[\mathrm{SF}]^2\mathrm{M}})

return vθ,sθv_\theta, s_\theta

push forward all observed points Xt−1X_{t-1} to time tt then measure the 1-Wasserstein distance between the predicted and true distribution.

For the Cite and Multi datasets these are sourced from the Multimodal Single-cell Integration challenge at NeurIPS 2022, a NeurIPS challenge hosted on Kaggle where the task was multi-modal prediction [11]. Here, we repurpose this data for the task of time series interpolation. Both of these datasets consist of four timepoints from CD34+ hematopoietic stem and progenitor cells (HSPCs) collected on days 2, 3, 4, and 7. For more information and the raw data see the competition site.2 We preprocess this data slightly to remove patient specific effects by focusing on a single donor (donor 13176).

Since these data have the full (pre-processed) gene level single-cell data, we try interpolating on higher-dimensional unwhitened principle components, and on the first 1000 highly variable genes, which is a standard preprocessing step in single-cell data analysis. To our knowledge, [SF]2M[\mathrm{SF}]^2\mathrm{M} is the first method to scale to the gene space of single-cell data. In Table 5, we again measure the 1-Wasserstein distance between the push forward predicted distribution and the ground truth distribution.

Geodesic ground costs

We also introduce the Geodesic Sinkhorn method from Huguet et al. [34] for dynamic Schrödinger bridge interpolation. Here the cost is a geodesic cost based on a kk-nearest-neighbour graph between cells.

Gene regulatory network recovery experimental details

Using the neural graphical model (NGM), we can parameterize the gene-gene interaction graph directly within the ODE drift model vθ(t,x)v_\theta(t, x). To do so, following from Bellot and Branson [8] we can define:

vθj(t,x)=ϕ(⋯ϕ(ϕ(xθj(1))θj(2))⋯ )θj(K),j=1,…,d,(26)v_{\theta_j}(t, x) = \phi(\cdots\phi(\phi(x\theta_j^{(1)})\theta_j^{(2)})\cdots)\theta_j^{(K)}, \qquad j = 1, \ldots, d, \tag*{(26)}

where θj(1)∈Rd×h\theta_j^{(1)} \in\mathbb{R}^{d \times h} represents a continuous adjacency matrix of the gene-gene interactions, θj(k)∈Rh×h\theta_j^{(k)} \in\mathbb{R}^{h \times h}, k=2,…,K−1k = 2, \ldots, K - 1 are parameters of each proceeding hidden layer, θj(K)∈Rh×1\theta_j^{(K)} \in\mathbb{R}^{h \times1}, x∈Rdx \in\mathbb{R}^d, and ϕ(.)\phi(.) is an activation function. Then we can consider vθ(t,x)=(vθ1(t,x),…,vθd(t,x))v_\theta(t, x) = (v_{\theta_1}(t, x), \ldots, v_{\theta_d}(t, x)) as hh ensembles over structure θ(1)\theta^{(1)}. We can then use Algorithm Alg. 1 to train the NGM model with the addition of an L1L^1 penalty over structure to enforce sparsity on gene-gene interactions, i.e λ1∥θ(1)∥1\lambda_1\|\theta^{(1)}\|_1. We include bias terms in our implementation of (26).

Using BoolODE (Pratapa et al., [60]), we generate simulated single-cell gene expression trajectories for a bifurcating system and a trifurcating system. For the bifurcating system we consider 7 synthetic genes and generate trajectories over 1000 cells using a simulation time of 5 and an initial condition on gene 1 at a value of 1.

We post-process the data and sub-sample to 55 timepoints and scramble the cell pairing to emulate real-world data. For the trifurcating system we consider 9 synthetic genes and generate trajectories over 800 cells using a simulation time of 6 and an initial condition on gene 1 at a value of 1. We post-process the data and sub-sample to 66 timepoints and scramble the cell pairing to emulate real-world data. We use a train-test data split of {0.8,0.2}\{0.8, 0.2\} respectively, and leave out the end timepoints for trajectory prediction evaluation. We the show underlying synthetic GRNs and simulated single-cell trajectories in Figure 7.

Simulated single-cell trajectories given synthetic GRNs emulating bifurcating and trifurcating systems

Figure 7. Simulated single-cell trajectories given synthetic GRNs emulating bifurcating (top) and trifurcating (bottom) systems. GRNs contain directed edges of Boolean relationships between genes. For example, a red edge between gene 3 and gene 0 (top left) indicates that the rule for gene 0 is (not gene 3). Likewise, a blue edge between gene 6 and gene 4 indicates that rule for gene 6 is (gene 4 and gene 6). This follows from the procedure for defining synthetic GRNs using the BoolODE framework [60]. The color bar indicates the scale of temporal progression.

For OT-CFM (i.e., [SF]2^{2}M with σ=0\sigma= 0), we parameterize the NGM model with two hidden layers where θj(1)∈Rd×h\theta_j^{(1)} \in\mathbb{R}^{d \times h} with h=100h = 100 and dd represents the number of input genes. Then the second layer (i.e., k=2k = 2) is θj(2)∈Rh×1\theta_j^{(2)} \in\mathbb{R}^{h \times1}. We use this parameterization for both the bifurcating system and trifurcating systems. For [SF]2^{2}M with σ>0\sigma> 0, we use two heads stemming from θj(1)\theta_j^{(1)} for the flow matching model and score matching model, respectively. Specifically, we use an additional layer θ~j(2)∈Rh×1\tilde{\theta}_j^{(2)} \in\mathbb{R}^{h \times1} such that sθj(x,t)=ϕ(ϕ(xθj(1))θ~j(2))s_{\theta_j}(x,t) = \phi(\phi(x\theta_j^{(1)})\tilde{\theta}_j^{(2)}), j=1,…,dj = 1, \ldots, d. We use the SeLU activation functions for both models. To train [SF]2^{2}M and NGM-[SF]2^{2}M models on the bifurcating system, we use the Adam optimizer with a learning rate of 0.01 and batch size of 128 and use λ1=10−5\lambda_1 = 10^{-5}. On the trifurcating system, we use the Adam optimizer with a learning rate of 0.01 and batch size of 64 and use λ1=10−6\lambda_1 = 10^{-6}. We generate results for 5 model seeds. For baseline methods (i.e., Spearman, Pearson, DREMI, and Granger) we generate results over 5 cell-pair scramble seeds. To evaluate GRN recovery performance, we compute the area under the receiver operator characteristic (AUC-ROC) and average precision (AP) scores of the predicted GRNs compared to the ground truth GRNs used for generating the simulated data. We mask out the diagonal elements (self regulation loops) of the predicted and ground truth GRNs for computing the AUC-ROC and AP. We provide the full results of the GRN recovery experiments in Table 9.

Bifurcating SystemTrifurcating System
W2W_2 (↓)RBF-MMD (↓)AUC-ROC (↑)AP (↑)W2W_2 (↓)RBF-MMD (↓)AUC-ROC (↑)AP (↑)
OT-CFM0.782 ± 0.1050.054 ± 0.004——0.921 ± 0.1420.068 ± 0.006——
[SF]2^2M0.791 ± 0.0970.056 ± 0.005——0.932 ± 0.1590.062 ± 0.006——
NGM-[SF]2^2Mσ=0_{\sigma=0}0.783 ± 0.1120.055 ± 0.0060.786 ± 0.0810.521 ± 0.1600.912 ± 0.1610.064 ± 0.0050.764 ± 0.0660.485 ± 0.105
NGM-[SF]2^2Mσ=0.1_{\sigma=0.1}0.835 ± 0.0890.064 ± 0.0110.723 ± 0.0140.444 ± 0.0301.049 ± 0.1950.080 ± 0.0140.731 ± 0.0770.453 ± 0.091
NGM-[SF]2^2Mσ=0.01_{\sigma=0.01}0.813 ± 0.1010.064 ± 0.0080.715 ± 0.0470.442 ± 0.0330.956 ± 0.1210.069 ± 0.0050.726 ± 0.0810.451 ± 0.094
NGM-[SF]2^2Mσ=0.001_{\sigma=0.001}0.844 ± 0.0630.082 ± 0.0180.699 ± 0.0430.418 ± 0.0601.005 ± 0.1500.094 ± 0.0140.725 ± 0.0800.445 ± 0.082
Spearman——0.755 ± 0.0030.438 ± 0.002——0.718 ± 0.0050.413 ± 0.005
Pearson——0.744 ± 0.0000.415 ± 0.000——0.710 ± 0.0020.405 ± 0.005
DREMI (Krishnaswamy et al. [39])——0.594 ± 0.0170.293 ± 0.011——0.419 ± 0.0210.205 ± 0.007
Granger (Granger [28])——0.664 ± 0.0130.421 ± 0.043——0.613 ± 0.0480.343 ± 0.039

Table 9. GRN recovery and leave-last-timepoint-out testing using single-cell gene expression over two simulated datasets. We measure performance of predicting the distribution of the final left-out timepoints (2-Wasserstein and radial basis function maximum mean discrepancy) as well accuracy of structure recovery (AUC-ROC and AP).

References

  1. [1]Albergo, M. S., Boffi, N. M., and Vanden-Eijnden, E. (2023). Stochastic interpolants: A unifying framework for flows and diffusions. arXiv preprint 2303.08797.arxiv.org/abs/2303.08797
  2. [2]Albergo, M. S. and Vanden-Eijnden, E. (2023). Building normalizing flows with stochastic interpolants. International Conference on Learning Representations (ICLR).arxiv.org/abs/2209.15571
  3. [3]Aliee, H., Richter, T., Solonin, M., Ibarra, I., Theis, F., and Kilbertus, N. (2022). Sparsity in continuous-depth neural networks. Neural Information Processing Systems (NeurIPS).arxiv.org/abs/2210.14672
  4. [4]Aliee, H., Theis, F. J., and Kilbertus, N. (2021). Beyond predictions in neural ODEs: Identification and interventions. arXiv preprint 2106.12430.arxiv.org/abs/2106.12430
  5. [5]Altschuler, J., Niles-Weed, J., and Rigollet, P. (2017). Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration. Neural Information Processing Systems (NIPS).arxiv.org/abs/1705.09634
  6. [6]Anderson, B. D. (1982). Reverse-time diffusion equation models. Stochastic Processes and their Applications, 12(3):313–326.DOI
  7. [7]Atanackovic, L., Tong, A., Hartford, J., Lee, L. J., Wang, B., and Bengio, Y. (2023). DynGFN: Bayesian dynamic causal discovery using generative flow networks. Neural Information Processing Systems (NeurIPS).
  8. [8]Bellot, A. and Branson, K. (2022). Neural Graphical Modelling in Continuous Time: Consistency Guarantees and Algorithms. International Conference on Learning Representations (ICLR).arxiv.org/abs/2105.02522
  9. [9]Bunne, C., Hsieh, Y.-P., Cuturi, M., and Krause, A. (2022a). The Schrödinger bridge between gaussian measures has a closed form. arXiv preprint 2202.05722.arxiv.org/abs/2202.05722
  10. [10]Bunne, C., Meng-Papaxanthos, L., Krause, A., and Cuturi, M. (2022b). Proximal optimal transport modeling of population dynamics. Artificial Intelligence and Statistics (AISTATS).arxiv.org/abs/2106.06345
  11. [11]Burkhardt, D., Bloom, J., Cannoodt, R., Luecken, M. D., Krishnaswamy, S., Lance, C., Pisco, A. O., and Theis, F. J. (2022). Multimodal single-cell integration across time, individuals, and batches. In NeurIPS Competitions.
  12. [12]Chen, R. T. Q., Rubanova, Y., Bettencourt, J., and Duvenaud, D. (2018). Neural ordinary differential equations. Neural Information Processing Systems (NeurIPS).arxiv.org/abs/1806.07366
  13. [13]Chen, T., Liu, G.-H., and Theodorou, E. A. (2022). Likelihood training of Schrödinger bridge using forward-backward SDEs theory. International Conference on Learning Representations (ICLR).arxiv.org/abs/2110.11291
  14. [14]Cuturi, M. (2013). Sinkhorn distances: Lightspeed computation of optimal transport. Neural Information Processing Systems (NIPS).arxiv.org/abs/1306.0895
  15. [15]Damodaran, B. B., Kellenberger, B., Flamary, R., Tuia, D., and Courty, N. (2018). DeepJDOT: Deep joint distribution optimal transport for unsupervised domain adaptation. European Conference on Computer Vision (ECCV).arxiv.org/abs/1803.10081
  16. [16]De Bortoli, V., Thornton, J., Heng, J., and Doucet, A. (2021). Diffusion Schrödinger bridge with applications to score-based generative modeling. Neural Information Processing Systems (NeurIPS).arxiv.org/abs/2106.01357
  17. [17]Dhariwal, P. and Nichol, A. (2021). Diffusion models beat GANs on image synthesis. Neural Information Processing Systems (NeurIPS).arxiv.org/abs/2105.05233
  18. [18]Fatras, K., Sejourne, T., Flamary, R., and Courty, N. (2021a). Unbalanced minibatch optimal transport; applications to domain adaptation. International Conference on Machine Learning (ICML).arxiv.org/abs/2103.03606
  19. [19]Fatras, K., Zine, Y., Flamary, R., Gribonval, R., and Courty, N. (2020). Learning with minibatch Wasserstein: Asymptotic and gradient properties. Artificial Intelligence and Statistics (AISTATS).
  20. [20]Fatras, K., Zine, Y., Majewski, S., Flamary, R., Gribonval, R., and Courty, N. (2021b). Minibatch optimal transport distances; analysis and applications. arXiv preprint 2101.01792.arxiv.org/abs/2101.01792
  21. [21]Fernandes, D., Vargas, F., Ek, C. H., and Campbell, N. D. F. (2022). Shooting Schrödinger’s cat. Advances in Approximate Bayesian Inference.
  22. [22]Finlay, C., Jacobsen, J.-H., Nurbekyan, L., and Oberman, A. M. (2020). How to train your neural ode: The world of Jacobian and kinetic regularization. International Conference on Machine Learning (ICML).arxiv.org/abs/2002.02798
  23. [23]Flamary, R., Courty, N., Gramfort, A., Alaya, M. Z., Boisbunon, A., Chambon, S., Chapel, L., Corenflos, A., Fatras, K., Fournier, N., Gauthèron, L., Gayraud, N. T. H., Janati, H., Rakotomamonjy, A., Redko, I., Rolet, A., Schutz, A., Seguy, V., Sutherland, D. J., Tavernier, R., Tong, A., and Vayer, T. (2021). POT: Python Optimal Transport. Journal of Machine Learning Research (JMLR), 22.
  24. [24]Föllmer, H. (1988). Random fields and diffusion processes. In Hennequin, P.-L., editor, École d’Été de Probabilités de Saint-Flour XV–XVII, 1985–87, pages 101–203, Berlin, Heidelberg. Springer Berlin Heidelberg.
  25. [25]Genevay, A., Chizat, L., Bach, F., Cuturi, M., and Peyré, G. (2019). Sample complexity of Sinkhorn di- vergences. Artificial Intelligence and Statistics (AISTATS).
  26. [26]Genevay, A., Cuturi, M., Peyré, G., and Bach, F. (2016). Stochastic optimization for large-scale optimal transport. Neural Information Processing Systems (NIPS).arxiv.org/abs/1605.08527
  27. [27]Genevay, A., Peyre, G., and Cuturi, M. (2018). Learning generative models with sinkhorn divergences. Artificial Intelligence and Statistics (AISTATS).arxiv.org/abs/1706.00292
  28. [28]Granger, C. W. J. (1969). Investigating causal relations by econometric models and cross-spectral methods. Econometrica, 37(3):424–438.
  29. [29]Grathwohl, W., Chen, R. T. Q., Bettencourt, J., Sutskever, I., and Duvenaud, D. (2019). Ffjord: Free-form continuous dynamics for scalable reversible generative models. International Conference on Learning Representations (ICLR).arxiv.org/abs/1810.01367
  30. [30]Hashimoto, T. B., Gifford, D. K., and Jaakkola, T. S. (2016). Learning population-level diffusions with generative recurrent networks. International Conference on Machine Learning (ICML).
  31. [32]Holdijk, L., Du, Y., Hooft, F., Jaini, P., Ensing, B., and Welling, M. (2022). Path integral stochastic optimal control for sampling transition paths. arXiv preprint 2207.02149.
  32. [33]Huguet, G., Magruder, D. S., Tong, A., Fasina, O., Kuchroo, M., Wolf, G., and Krishnaswamy, S. (2022a). Manifold interpolating optimal-transport flows for trajectory inference. Neural Information Processing Systems (NeurIPS).
  33. [34]Huguet, G., Tong, A., Zapatero, M. R., Wolf, G., and Krishnaswamy, S. (2022b). Geodesic Sinkhorn: Optimal transport for high-dimensional datasets. arXiv preprint 2211.00805.
  34. [35]Kester, L. and van Oudenaarden, A. (2018). Single-cell transcriptomics meets lineage tracing. Cell Stem Cell, 23(2):166–179.DOI
  35. [36]Klambauer, G., Unterthiner, T., Mayr, A., and Hochreiter, S. (2017). Self-normalizing neural networks. Neural Information Processing Systems (NIPS).
  36. [37]Klein, D., Palla, G., Lange, M., Klein, M., Piran, Z., Gander, M., Meng-Papaxanthos, L., Sterr, M., Bastidas-Ponce, A., Tarquis-Medina, M., Lickert, H., Bakhti, M., Nitzan, M., Cuturi, M., and Theis, F. J. (2023). Mapping cells through time and space with moscot. bioRxiv preprint 2023.05.11.540374.
  37. [38]Koshizuka, T. and Sato, I. (2023). Neural Lagrangian Schrödinger bridge. International Conference on Learning Representations (ICLR).
  38. [39]Krishnaswamy, S., Spitzer, M. H., Mingueneau, M., Bendall, S. C., Litvin, O., Stone, E., Pe’er, D., and Nolan, G. P. (2014). Conditional density-based analysis of T cell signaling in single-cell data. Science, 346(6213):1250689.DOI
  39. [40]Lähnemann, D., Köster, J., Szczurek, E., McCarthy, D. J., Hicks, S. C., Robinson, M. D., Vallejos, C. A., Campbell, K. R., Beerenwinkel, N., Mahfouz, A., Pinello, L., Skums, P., Stamatakis, A., Attolini, C. S.-O., Aparicio, S., Baajien, J., Balvert, M., Barbanson, B. D., Cappuccio, A., Corleone, G., Dutilh, B. E., Florescu, M., Guryev, V., Holmer, R., Jahn, K., Lobo, T. J., Keizer, E. M., Khatri, I., Kielbasa, S. M., Korbel, J. O., Kozlov, A. M., Kuo, T.-H., Lelieveldt, B. P., Mandoiu, I. I., Marioni, J. C., Marschall, T., Mölder, F., Niknejad, A., Raczkowski, L., Reinders, M., Ridder, J. D., Saliba, A.-E., Somarakis, A., Stegle, O., Theis, F. J., Yang, H., Zelikovsky, A., McHardy, A. C., Raphael, B. J., Shah, S. P., and Schönhuth, A. (2020). Eleven grand challenges in single-cell data science. Genome Biology, 21(1):31.DOI
  40. [41]Lavenant, H., Zhang, S., Kim, Y.-H., and Schiebinger, G. (2021). Towards a mathematical theory of trajectory inference.arxiv.org/abs/2102.09204
  41. [42]Léonard, C. (2014a). Some properties of path measures. In Donati-Martin, C., Lejay, A., and Rouault, A., editors, Séminaire de Probabilités XLVI, pages 207–230. Springer.
  42. [43]Léonard, C. (2014b). A survey of the Schrödinger problem and some of its connections with optimal transport. Discrete and Continuous Dynamical Systems, 34(4):1533–1574.arxiv.org/abs/1308.0215
  43. [44]Lipman, Y., Chen, R. T. Q., Ben-Hamu, H., Nickel, M., and Le, M. (2023). Flow matching for generative modeling. International Conference on Learning Representations (ICLR).
  44. [45]Liu, G.-H., Chen, T., So, O., and Theodorou, E. A. (2022). Deep generalized Schrödinger bridge. Neural Information Processing Systems (NeurIPS).
  45. [46]Liu, G.-H., Vahdat, A., Huang, D.-A., Theodorou, E. A., Nie, W., and Anandkumar, A. (2023a). I²sb: Image-to-image schrödinger bridge. International Conference on Machine Learning (ICML).
  46. [47]Liu, Q. (2022). Rectified flow: A marginal preserving approach to optimal transport. arXiv preprint 2209.14577.arxiv.org/abs/2209.14577
  47. [48]Liu, X., Gong, C., and Liu, Q. (2023b). Flow straight and fast: Learning to generate and transfer data with rectified flow. International Conference on Learning Representations (ICLR).arxiv.org/abs/2209.03003
  48. [49]Loshchilov, I. and Hutter, F. (2019). Decoupled weight decay regularization. International Conference on Learning Representations (ICLR).
  49. [50]Mallasto, A., Gerolin, A., and Ha Quang, M. (2022). Entropy-regularized 2-Wasserstein distance between Gaussian measures. Information Geometry, 5.arxiv.org/abs/2006.03416
  50. [51]Mena, G. and Niles-Weed, J. (2019). Statistical bounds for entropic optimal transport: sample complexity and the central limit theorem. Neural Information Processing Systems (NeurIPS).arxiv.org/abs/1905.11882
  51. [52]Moon, K. R., Stanley, J. S., Burkhardt, D., van Dijk, D., Wolf, G., and Krishnaswamy, S. (2018). Manifold learning-based methods for analyzing single-cell mRNA-sequencing data. Current Opinion in Systems Biology, 7:36–46.DOI
  52. [53]Moon, K. R., van Dijk, D., Wang, Z., Gigante, S., Burkhardt, D. B., Chen, W. S., Yim, K., van den Elzen, A., Hirn, M. J., Coifman, R. R., Ivanova, N. B., Wolf, G., and Krishnaswamy, S. (2019). Visualizing structure and transitions in high-dimensional biological data. Nature Biotechnology, 37(12):1482–1492.
  53. [54]Neklyudov, K., Brekelmans, R., Severo, D., and Makhzani, A. (2023). Action matching: Learning stochastic dynamics from samples. International Conference on Machine Learning (ICML).arxiv.org/abs/2210.06662
  54. [55]Neklyudov, K., Severo, D., and Makhzani, A. (2022). Action matching: A variational method for learning stochastic dynamics from samples. arXiv preprint 2210.06662.arxiv.org/abs/2210.06662
  55. [56]Nichol, A. and Dhariwal, P. (2021). Improved denoising diffusion probabilistic models. International Conference on Machine Learning (ICML).
  56. [57]Nolan, T. M., Vukašinović, N., Hsu, C.-W., Zhang, J., Vanhoutte, I., Shahan, R., Taylor, I. W., Greenstreet, L., Heitz, M., Afanassiev, A., Wang, P., Szekely, P., Brosnan, A., Yin, Y., Schiebinger, G., Ohler, U., Russinova, E., and Benfey, P. N. (2023). Brassinosteroid gene regulatory networks at cellular resolution in the arabidopsis root. Science, 379(6639):eadf4721.DOI
  57. [58]Peluchetti, S. (2023). Diffusion bridge mixture transports, Schrödinger bridge problems and generative modeling. Journal of Machine Learning Research (JMLR), 24:1–51.arxiv.org/abs/2304.00917
  58. [59]Pooladian, A.-A., Ben-Hamu, H., Domingo-Enrich, C., Amos, B., Lipman, Y., and Chen, R. T. (2023). Multisample flow matching: Straightening flows with minibatch couplings. International Conference on Learning Representations (ICLR).arxiv.org/abs/2304.14772
  59. [60]Pratapa, A., Jalihal, A. P., Law, J. N., Bharadwaj, A., and Murali, T. (2020). Benchmarking algorithms for gene regulatory network inference from single-cell transcriptomic data. Nature methods, 17.
  60. [61]Qin, X., Rodriguez, F. C., Sufi, J., Vlckova, P., Claus, J., and Tape, C. J. (2023). A single-cell perturbation landscape of colonic stem cell polarisation. Preprint, Cancer Biology.DOI
  61. [62]Salimans, T., Zhang, H., Radford, A., and Metaxas, D. (2018). Improving GANs using optimal transport. International Conference on Learning Representations (ICLR).
  62. [63]Schiebinger, G. (2021). Reconstructing developmental landscapes and trajectories from single-cell data. Current Opinion in Systems Biology, 27:100351.
  63. [64]Schiebinger, G., Shu, J., Tabaka, M., Cleary, B., Subramanian, V., Solomon, A., Gould, J., Liu, S., Lin, S., Berube, P., Lee, L., Chen, J., Brumbaugh, J., Rigollet, P., Hochedlinger, K., Jaenisch, R., Regev, A., and Lander, E. S. (2019). Optimal-transport analysis of single-cell gene expression identifies developmental trajectories in reprogramming. Cell, 176(4):928–943.e22.
  64. [65]Schrödinger, E. (1932). Sur la théorie relativiste de l’électron et l’interprétation de la mécanique quantique. Annales de l’Institut Henri Poincaré, 2(4):269–310.
  65. [66]Seguy, V., Damodaran, B. B., Flamary, R., Courty, N., Rolet, A., and Blondel, M. (2018). Large scale optimal transport and mapping estimation. International Conference on Learning Representations (ICLR).arxiv.org/abs/1711.02283
  66. [67]Shi, Y., De Bortoli, V., Campbell, A., and Doucet, A. (2023). Diffusion Schrödinger bridge matching. arXiv preprint 2303.16852.
  67. [68]Shi, Y., De Bortoli, V., Deligiannidis, G., and Doucet, A. (2022). Conditional simulation using diffusion Schrödinger bridges. Uncertainty in Artificial Intelligence (UAI).arxiv.org/abs/2202.13460
  68. [69]Sinkhorn, R. (1964). A relationship between arbitrary positive matrices and doubly stochastic matrices.DOI
  69. [70]Sohl-Dickstein, J., Weiss, E. A., Maheswaranathan, N., and Ganguli, S. (2015). Deep unsupervised learning using nonequilibrium thermodynamics. International Conference on Machine Learning (ICML).
  70. [71]Somnath, V. R., Pariset, M., Hsieh, Y.-P., Martinez, M. R., Krause, A., and Bunne, C. (2023). Aligned diffusion Schrödinger bridges. Uncertainty in Artificial Intelligence (UAI).
  71. [72]Song, J., Meng, C., and Ermon, S. (2021a). Denoising diffusion implicit models. International Conference on Learning Representations (ICLR).
  72. [73]Song, Y. and Ermon, S. (2019). Generative modeling by estimating gradients of the data distribution. Neural Information Processing Systems (NeurIPS).
  73. [74]Song, Y. and Ermon, S. (2020). Improved techniques for training score-based generative models. Neural Information Processing Systems (NeurIPS).arxiv.org/abs/2006.09011
  74. [75]Song, Y., Sohl-Dickstein, J., Kingma, D. P., Kumar, A., Ermon, S., and Poole, B. (2021b). Score-based generative modeling through stochastic differential equations. International Conference on Learning Representations (ICLR).
  75. [76]Stromme, A. (2023). Sampling from a Schrödinger bridge. Artificial Intelligence and Statistics (AISTATS).
  76. [77]Tang, Y. (2017). Potential landscape of high dimensional nonlinear stochastic dynamics with large noise. Scientific Reports.
  77. [78]Tank, A., Covert, I., Foti, N., Shojaie, A., and Fox, E. (2021). Neural Granger Causality. IEEE Transactions on Pattern Analysis and Machine Intelligence.
  78. [79]Tong, A., Fatras, K., Malkin, N., Huguet, G., Zhang, Y., Rector-Brooks, J., Wolf, G., and Bengio, Y. (2024). Improving and generalizing flow-based generative models with minibatch optimal transport. Transactions on Machine Learning Research.arxiv.org/abs/2302.00482
  79. [80]Tong, A., Huang, J., Wolf, G., van Dijk, D., and Krishnaswamy, S. (2020). TrajectoryNet: A dynamic optimal transport network for modeling cellular dynamics. International Conference on Machine Learning (ICML).
  80. [81]Tong, A., Kuchroo, M., Gupta, S., Venkat, A., Perez San Juan, B., Rangel, L., Zhu, B., Lock, J. G., Chaffer, C., and Krishnaswamy, S. (2023). Learning transcriptional and regulatory dynamics driving cancer cell plasticity using neural ode-based optimal transport. bioRxiv preprint 2023.03.28.534644.
  81. [82]Vargas, F., Thodoroff, P., Lawrence, N. D., and Lamacraft, A. (2021). Solving Schrödinger bridges via maximum likelihood. Entropy, 23(9).DOI
  82. [83]Waddington, C. H. (1942). The epigenotype. Endeavour, 1:18–20.
  83. [84]Wagner, D. E. and Klein, A. M. (2020). Lineage tracing meets single-cell omics: Opportunities and challenges. Nature Reviews Genetics, 21(7):410–427.DOI
  84. [85]Wang, G., Jiao, Y., Xu, Q., Wang, Y., and Yang, C. (2021). Deep generative learning via Schrödinger bridge. International Conference on Machine Learning (ICML).arxiv.org/abs/2106.10410
  85. [86]Watson, J. L., Juergens, D., Bennett, N. R., Trippe, B. L., Yim, J., Eisenach, H. E., Ahern, W., Borst, A. J., Ragotte, R. J., Milles, L. F., Wicky, B. I. M., Hanikel, N., Pellock, S. J., Courbet, A., Sheffler, W., Wang, J., Venkatesh, P., Sappington, I., Torres, S. V., Lauko, A., De Bortoli, V., Mathieu, E., Barzilay, R., Jaakkola, T. S., DiMaio, F., Baek, M., and Baker, D. (2023). Broadly applicable and accurate protein design by integrating structure prediction networks and diffusion generative models. Nature.
  86. [87]Winkler, L., Ojeda, C., and Opper, M. (2023). A score-based approach for training Schrödinger bridges for data modelling. Entropy, 25(2):316.DOI
  87. [88]Wolf, F. A., Angerer, P., and Theis, F. J. (2018). SCANPY: Large-scale single-cell gene expression data analysis. Genome Biology, 19(1):15.DOI
  88. [89]Yang, K. D., Damodaran, K., Venkatachalapathy, S., Soylemezoglu, A. C., Shivashankar, G. V., and Uhler, C. (2020). Predicting cell lineages using autoencoders and optimal transport. PLOS Computational Biology, 16:1–20.DOI

Paper details

vlnc:W_4y39jr8z
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents