Diffusion Schrödinger Bridge with Applications to Score-Based Generative Modeling
Authors: Valentin De Bortoli
James Thornton
Jeremy Heng
Arnaud Doucet
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Theory
Optimal Transport
Diffusion
Schrodinger Bridge
Score matching

Abstract: Progressively applying Gaussian noise transforms complex data distributions to approximately Gaussian. Reversing this dynamic defines a generative model. When the forward noising process is given by a Stochastic Differential Equation (SDE), Song et al (2021) demonstrate how the time inhomogeneous drift of the associated reverse-time SDE may be estimated using score-matching. A limitation of this approach is that the forward-time SDE must be run for a sufficiently long time for the final distribution to be approximately Gaussian. In contrast, solving the Schrödinger Bridge (SB) problem, i.e. an entropy-regularized optimal transport problem on path spaces, yields diffusions which generate samples from the data distribution in finite time. We present Diffusion SB (DSB), an original approximation of the Iterative Proportional Fitting (IPF) procedure to solve the SB problem, and provide theoretical analysis along with generative modeling experiments. The first DSB iteration recovers the methodology proposed by Song et al. (2021), with the flexibility of using shorter time intervals, as subsequent DSB iterations reduce the discrepancy between the final-time marginal of the forward (resp. backward) SDE with respect to the prior (resp. data) distribution. Beyond generative modeling, DSB offers a widely applicable computational optimal transport tool as the continuous state-space analogue of the popular Sinkhorn algorithm (Cuturi, 2013).

Diffusion Schrödinger Bridge with Applications to Score-Based Generative Modeling
Valentin De Bortoli Department of Statistics, University of Oxford, UK
James Thornton Department of Statistics, University of Oxford, UK
Jeremy Heng ESSEC Business School, Singapore
Arnaud Doucet Department of Statistics, University of Oxford, UK
Abstract
Progressively applying Gaussian noise transforms complex data distributions to approximately Gaussian. Reversing this dynamic defines generative model. When the forward noising process is given by a Stochastic Differential Equation (SDE), Song et al. (2021) demonstrate how the time inhomogeneous drift of the associ- ated reverse-time SDE may be estimated using score-matching. A limitation of this approach is that the forward-time SDE must be run for sufficiently long time for the final distribution to be approximately Gaussian while ensuring that the corresponding dineetiscetiizaiion eтror is controlled. In contrast, solving the Schrödinger Bridge (SB) problem, i.e. an reetoppy-relrrizeee optimal transport problem on path spaces, yields diffusions which generate samples from the data distribution in finite time. We present Diffusion SB (DSB), original approxima- tion of the Iterative Proportional Fitting (IPF) procedure solve the SB problem, and provide theoretical analysis along with generative modeling experiments. The first DSB iteration recovers the methodology proposed by Song et (2021), with the flexibility of using shorter time intervals, subsequent DSB iterations reduce the discrepancy between the final-time marginal of the forward (resp. backward) SDE with respect to the Gaussian prior (resp. data) distribution. Beyond generative modeling, DSB offers a computational optimal transport tool as the continuous state-space analogue of the popular Sinkhorn algorithm (Cuturi, 2013).
Introduction
Score-Based Generative Modeling (SGM) is recently developed approach to probabilistic generative modeling that exhibits state-of-the-art performance on several audio and image synthesis tasks; see e.g. Song and Ermon (2019); Cai et al. (2020); Chen et al. (2021a); Kong et al. (2021); Gao et al. (2020); Maliceuu-Martineauu
Martineau et al. (2021b); Ho et (2020); Song and Ermon (2020); Song et al. (2020, 2021); Niu et al. (2020); Durkan and Song 2021); Hoogeboom et al. (2021); Saharia et al. (2021);
Luhman and Luhman (2021, 2020); Nichol and Dhariwal (2021); Popov et al. (2021); Dhariwal and Nichol (2021). Existing SGMs generally consist of two parts. Firstly, noise is incrementally added to the data order to obtain perturbed data distribution approximating an easy-to-sample prior distribution e.g. Gaussian. Secondly, neural network is used to learn the reverse-time denoising dynamics, which when initialized this prior distribution, defines a generative model (Sohl-Dickstein et al.. 2015; Ho et al., 2020; Song and Ermon, 2019; Song et al., 2021). Song al. (2021) have shown that one could fruitfully view the noising process as a Stochastic Differential Equation (SDE) that progressively perturbs the initial data distribution into approximately Gaussian
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

S
Forward
S
S-S
DSB
Backward
DSB Steps
S
Forward
DSB
S.
Backward
Generative Model
t=0
t T
Figure 1: The reference forward diffusion initialized from the 2-dimensional data distribution fails to converge to the Gaussian prior in T = 0.2 diffusion-time (N = 20 discrete time steps), and the reverse diffusion initialized from the Gaussian prior does not converge to the data distribution. However, convergence does occur after DSB iterations.
The corresponding reverse-time SDE is an inhomogeneous diffusion whose drift depends on the logarithmic gradients of the perturbed data distributions, i.e. the scores. In practice, these scores approximated using neural networks and score-matching techniques (Hyvärinen and Dayan, 2005; Vincent, 2011) while numerical SDE integrators used for the sampling procedure.
Although SGM provides state-of-the-ard results (Dhariwal and Nichol, 2021), sample generation computationally expensive. In order to learn the reverse-time SDE from the prior, i.e. the generative model, the forward noising SDE must be run for a sufficiently long time to converge to the prior and the step size must be sufficiently small to obtain a good numerical approximation of this SDE. By reformulating generative modeling as a Schrödinger bridge (SB) problem, we mitigate this issue and follows.
propose novel algorithm to solve SB problems. Our detailed contributions
Generative modeling as a Schrödinger bridge problem. The SB problem famous entropy- regularized Optimal Transport (OT) problem introduced by Schrödinger (1932); see e.g. (Léonard, 2014b; Chen al., 2021b) for reviews. Given a reference diffusion with finite time horizon T, data distribution and prior distribution, solving the SB amounts to finding the closest diffusion to the reference (in terms of Kullback-Leibe
divergence on path spaces) which admits the data distribution as marginal at time / = 0 and the prior at time / = T. The reverse-time diffusion solving this SB problem provides new SGM algorithm which enables approximate sample generation from the data distribution using shorter time intervals compared to the original SGM methods. Our method differs from the hurropy-regularized OT formulation in (Genevay et al., 2018), which deals with discrete distributions and relies static formulation of SB, opposed for continuous distributions which operates on path spaces. It also differs from (Finlay et al., 2020) which approximates the SB solution by diffusion whose drift is computed using potentials of the dual formulation of SB. Finally, Wang et al. (2021) have recently proposed to perform generative modeling by solving not one but SB problems. Contrary us. they do not formulate generative modeling as computing the SB between the data and prior distributions. Solving the Schrödinger bridge problem using score-based diffusions. The SB problem Proportional Fitting (IPF) (Fortet, 1940; Kullback, 1968; Chen et al., 2021b). We propose Diffusion SB (DSB), novel implementation of IPF using score-based diffusion techniques. DSB does not require discretizing the state-space (Chen et al., 2016; Reich, 2019), approximating potential functions using regression (Bernton et al., 2019; Dessein al., 2017: Pavon al., 2021). nor performing kernel density estimation (Pavon et al., 2021). The first DSB iteration recovers the method proposed by Song et al. (2021), with the flexibility of using shorter time intervals, as additional DSB iterations reduce the discrepancy between the final-time marginal of the forward (resp. backward) SDE w.r.t. prior (resp. data) distribution; see Figure for an illustration. An algorithm akin DSB has been proposed concurrently and independently by Vargas et al. (2021); the main difference with our algorithm is that they estimate the drifts of the SDEs using Gaussian processes while we use neural networks and score matching ideas.
dynamical approach
be solved using Iterative

---

Theoretical results. We provide the first quantitative convergence results for the methodology of Song et al. (2021). In particular, we show that while we simulate Langevin-type diffusions in potentially extremely high-dimensional spaces, the SGM approach does not suffer from poor mixing times. Additionally, we derive novel quantitative convergence results for IPF in continuous state-space which do not rely on classical compactness assumptions (Chen et al., 2016; Ruschendorf et al., 1995) and improve on the recent results of Léger (2020), Finally, we show that DSB may be viewed as the time discretization of dynamic version of IPF on path spaces based on forward/backwart diffusions.
Experiments. We validate our methodology by generating image datasets such as MNIST and CelebA. In particular, we show that using multiple steps of DSB always improve the generative model. We also show how DSB can be used to interpolate between two data distributions.
Notation. In the contimuous-time setting, we set C - C[ R2) the space of continuous functions from [0, T" to R and (CC) the Borel sets on For any measurable space (E, E), we denote by P (E) the space of probability measures on (E, For any E N, let P: = P ((R))) When it is defined, we denote H(p) = S--- p(x) log p(r)dz the entropy of p and (plg)) as the Kullback-Leibler
divergence between p and q. When there no ambiguity, we use the same notation for distributions and their densities. All proofs are postponed to the supplementary.
2 Denoising Diffusion, Score-Matching and Reverse-Time SDEs
2.1 Discrete-Time: Markov Chains and Time Reversal
Consider data distribution with positive density Paata 1 a positive prior density Ppeior W.r.t. Lebesgue measure both with support on T and a Markov chain with initial density Po = Pdata on R2d evolving according to positive transition densities Pk+ for k NN 13. Hence for any To:N
{ E X = (RR)N+1, the joint density may be expressed as
p(Zo.N) = (0 II = (
This joint density also admits the backward decomposition
p(Zo.N) = PN (xN) No P with Paca++1 (Ix (z4l))441)= pa pa(ondpeepnalannlll (2)
where (*x) =
is the marginal density at step 2 1. For
the purpose of generative modeling, we will choose transition densities such that (N = I p( Jd R (x for large N, where Pprior is an easy-to-sample prior density. One may sample approximately from Pdata using ancestral sampling with the reverse-time decomposition (2), i.e. first sample XN Pprior followed by X₁ PkJK+1 (-|X++1) for k E (N .....,
... O}. This idea is at the core of all recent SGM methods. The reverse-time transitions (2) cannot be simulated exactly but may be approximated if we consider forward transition density of the form
(6+1)((T4+1177) N (I1+15 + 7K41 (Tx), 11)+
with drift/ f Rd + dRd and stepsize 7 > O. We first make the following approximation from (2)
P = P exp/o - log Po
2s ( 7 + 27 V log Pa (Ix+1) 17 I),
(4)
using that p& & Px+1. a Taylor expansion of log Px+11 at 26+1 and f(xx) ~ f(I+ ). In practice, the approximation holds if | xx> is small which is ensured by choosing 7h+11 small enough. Although V Pog is not available, one may obtain an approximation using denoising score- matching methods (Hyvärinen and Dayan, 2005; Vincent. 2011; Song et al., 2021).
Assume that the conditional density Pk+ Pk+11o (100 (20) is available analytically as in (Ho et al., 2020; Song et al., 2021). We have P641(1141) = po po(oo) 110 (I (o d2g and elementary cal- culations show that V log P (#x+1) = Eppor: (Vze., log P1 [o)]. We can therefore
In this presentation, we assume that all distributions admit density w.r.t the Lebesgue measure for simplicity. However, the algorithms presented here only require having access samples from paaa and Priur-
3

---

formulate score estimation as a regression problem and use flexible class of functions, e.g. neural networks, to parametrize an approximation sp- (k, 2x) z log Pi: (2x) such that
0 = arg ming Eim Ex (1lss(kk Xx) as. log Pk (Xx [Xo)]]²],
where Po. (3r; mtg) = po (p)o)) (m0) is the joint density steps 0 and k. If pk:o is not available,
we use 8* = arg ming Σ Bp.-1, (l (k, Xx) - V log Pk|KK-1 (X& Xx x In summary.
SGM involves first estimating the score function sg. from noisy data, and then sampling Xo using XN Pprior and the approximation (4), i.e.
Lid. X = X - 7++1 (Xxx+)) + 2 (k + 1, XK+1) + 2 7x11, Zx+1 ~ II,,T). (5)
-
The random variable Xo is approximately po Pdata distributed if (xNN 2 Ppeio In what follows, we let {Y& (XN- and remark that {Y&) satisfies forward recursion.
2.2 Continuous-Time: SDEs, Reverse-Time SDEs and Theoretical results
For appropriate transition densities, Song al. (2021) showed that the forward and reverse-time Markov chains may be viewed as discretized diffusions. We derive the continuous- time limit of the procedure presented in Section 2.1 and establish convergence results. The Markov chain with kernel (3) corresponds to an Buler-Maruyeer discretization of (Xi) solving the following SDE
dx, f(X,)dt V2dB, Xo Po = Pdatu:
where (B))reju,ry is a Brownian motion and f R + Rdd is regular enough so that (strong) solutions exist. Under conditions on f. is well-known (see Haussmann and Pardoux (1986); Föllmer (1985); Cattiaux et al. (2021) for instance) that the reverse-timg time process (Yi)ee(o,T) = (XT-t)eejo.n) satisfies
dY, (-)(Y,) + 2V log dt + /2dB,,
with initialization Yo ~ pT, where pt denotes the marginal density of X,,
The reverse-time Markov chain { associated with (5) corresponds to an Fuler-Maruyama discretization of (7), where the score functions log (z) are approximated by sg. (t,z).
In what follows, we consider f(x) = -a for a 2 0. This framework includes the one of Song and Ermon (2019) (a O. Pprio( = (z; 0, 2T I)) for which (X4)4e(0,77 is simply a Brownian motion and Ho et al. (2020) (ax > O. Pprior (x) = Na;; 0, I/()) for which it is an Orntein-UUllebeed process, see Section S3.3 for more details. Contrary to Song et al. (2021) we consider time homogeneous diffusions. Both approaches approximate (5) using distinct discretizations but our setting leverages the ergodic properties of the Ornstein-Uhlenbers Uhlenbeck process to establish Theorem
Theorem 1. Assume that there exists M 2 0 such that for any & [0, T] and x Rd
(8) with sæ- C(10, 21 Rdd Rdd. Assume that Pdata C (xxd, (0, +oo)) bounded and that there
|| (t, x) - V log S M,
exist di, A,, As O. 31, B2, Bs N and m1 > O such that for any E IRd and i E (1,2,3)
| log Paiaa (x) S A, + 11 <V Pama (x), (t
S mm 12:1| + dg ||=]||,
with 31 = 1. Then for any a 2 O, there exist Ba, Ca, Do 2 O such that for any N E N and {Tx (
with 7/ > 0 for any k E {1, ,I,...,NN N}. the following bounds the total variation distance hold:
if (a)
0, we have (| Poaul ll S C. (M + +1112) exp + B. expl-a
(b) if 0, we have [[((X)) - Daaaal/TV S CM(M + ((MM++712))) 2122) exxx)xx
T-1/));
where T Σ nh 7 supke 7k and ((Xo) the distribution of X, given in (5).
We provide here a sketch of the proof. The whole proof is detailed in Section S3.2. Denote P E (CC) the path measure associated with (6) and pd its time-reversal. Denote QN the Markoy kernel taking from Yo to YN induced by (5). We have
Proof.
Ppric QN Pdata TV
IlP QN Pdata
PP T (IP DTyolTVV

---

Ppeeic QN Pprior (P /roolll lv + Pppttor (P*)) -Puu PuuuPrro TTol/v
lpppeice QN Ppeior (T. /rool/ + llpprior pr||TV.
We control the first term by bounding the discretization error of QN when compared to (IP)) 11j0 via
the Cirsanov theorem. The second term is controlled using the mixing properties of the forward diffusion process.
Condition (8) ensures that the neural network approximates the score with a given precision M 2 0. Under (8) and conditions on pdata- Theorem 1 states how the Markov chain defined by (5) approximates Pdaaa in the total variation norm || ||rv. The bounds of Theorem show that there a trade-off between the mixing properties of the forward diffusion which increases with a, and the quality of the discrete-time approximation which deteriorates as a and T increase, since Ba: Da aa-++ +oo. Indeed increasing makes the drift steeper and the continuous- smaller step sizes are required in order to control the error between the discrete and the continuous- time processes. Theorem is the first theoretical result assessing the convergence of SGM methods. Indeed while Block et al. (2020) establish convergence results for a time time-homogeneous Langevin diffusion targeting density whose score is approximated by a neural network, all SGM methods used in practice rely on hmmeinnhomogenouu processes. Contrary to the sume-homogencous case, this approach does not suffer from poor mixing times as the mixing time dependency in the bounds of Theorem is entirely determined by the mixing time of the forward process, given by a simple Brownian motion or an Ornstein Ulhenbeeck process, and is independent of the dimension. Finally, note that (8) is strong assumption. In practice we expect to obtain such bounds in expectation over X with high probability w.r.t. the data distribution as (Block et al., 2020, Proposition 9). Our results are also related to (Tzen and Raginsky, 2019, Theorem 3.1) 1) which establishes the expressiveness of related generative models using tools from stochastic control.
process converges faster but
3 Diffusion Schrödinger Bridge and Generative Modeling
3.1 Schrödinger Bridges
The SB problem is a classical problem appearing in applied mathematics, optimal control and probability; see e.g. Föllmer (1988); Léonard (2014b); Chen et al. (2021b). In the discrete-time setting, takes the following (dynamic) form. Consider as reference density p(zo.v) given by (1), describing the process adding noise to the data. We aim to find x NN1 such that
' arg min (KL(T)p) : P N+1 To Pdata TN Pprior
(9)
Assuming मt is available, a generative model can be obtained by sampling XN ~ Pprior, followed by the reverse-time dynamics X₁ ~ - (-) (-1Xx+1) for A E {N -,.... 0}. Before deriving method
to approximate n² in Section 3.2, we highlight some desirable features of Schrödinger bridges.
Statie Schrödinger bridge problem. First, we recall that the dynamic formulation (9) admits static analogue. Using e.g. Léonard (2014a, Theorem 2.4), the following decomposition holds for any π E 3 I1, (T() = KL( (po.v) + ET,,, x [K /pp..// where for any μ E PN we have μ = Mo.N with 'J the conditional distribution of X X1:N-1 given Xo, XN² Hence we have TT" (#a:N) = 7 Th (xo, N P/oo (I1:N-1 (T xN) where n-* E P2 with marginals = and
a,t is the solution of the static SB problem NN
n arg min [KL(T")Po.N) x" P2 T = Pdata TTy
Pprior
(10)
Link with optimal transport. Under mild assumptions, the static SB problem can be seen as entropy- reguopy-eguularized optimal transport problem since (10) is equivalent to H(r²) : T" E P2 क Pdama Ty = Pprior
π 5.* = arg min { --E,- P (Xx|
If P (12+1 (x)) N(x++1i 2x, 1) as in Song and Ermon (2019), then (Nio(2N WaN:: 0²) with x² = Ei= of which induces a quadratic cost and
T.. = arg min (E 1|x0 - 1 H(*)) : T² E P2, T = Pintas T = Pprior }
"See Section $4.1 for rigorous presentation using the disintegration theorem for probability measures.
5

---

Mikami (2004) showed that オ.* + zw weakly and 20 (KI(TT"/PP,NN - W (Puats Porior) as + O, where zy is the optimal transport plan between Pdata and Pprior and W2 is the 2- Wassersttei distance. Note that the transport cost c(2,, x²) - log PNjo('' (a))))) is not necessarily symmetric.
3.2 Iterative Proportional Fitting and Time Reversal
In all but trivial cases, the SB problem does not admit a closed-form solution. However, it can be solved using Iterative Proportional Fitting (IPF) (Fortet, 1940; Kullback, 1968; Ruschendorf et al., 1995) which is defined by the following recursion for N with initialization TO p given in (1):
π 2n+1 arg min ( : т E N+I, AN = Pprior f n n2n+2 = arg min [ :T E N+1, Tu = Pamas
(11)
This sequence is well-defined if there exists मे E N+1 such that Noo = Pdata. AN = Pprior and KL(#(p) < +o0. A standard representation of π² is obtained by updating the joint density p using potential functions, see Section S4.2 for details. However, this representation the IPF iterates is difficult to approximate it requires approximating the potentials. Our methodology builds upon an alternative representation that is better suited to numerical approximations for generative modeling where one has access to samples of pdat and Pprior-
Proposition 2. Assume that (P(paat & Prior Po < +00. Then for any E N, n2n and 2 admit positive densities w.r.t. the Lebesgue measure denoted as yd resp. q" and for any vo.n E X, we have pd (Fo:N) = =p( and
(((oo:) = ( IT== Pii (Ik) p=+11= (xT:N) = Paaa ( IT= lh 1ja (1
In practice we have access to P and Cel Hence, to compute PM and tf we use
Pk (GjA-((a//ae (xx Pk+ Pl+ ( (2k)p
1e+1j (3 2 (1xl=2200000 gh (21+1)
Pk (
Of (xxx)
To the best of our knowledge, this representation of the IPF iterates has surprisingly neither been presented nor explored in the literature. One may interpret these formulas as follows. At iteration 2n, we have 2 p" with p" given by the noising process (1). This forward process initalized with P = Pdata defines reverse-time transitions Pk|K+1> which, when combined with an initialization Ppeior
at step N defines the reverse- reverse-time process x 22n++ = q". The forward transitions 1k+1 associated to 9ºt are then used to obtain 22m+2 = =p*+1 IPF then iterates this procedure.
3.3 Diffusion Schrödinger Bridge Iterative Mean-Matching Proportional Fitting
To approximate the IPF recursion defined in Proposition 2, we use similar approximations to Sec- tion 2.1. If at step N we have PK (#x+1|=xx) = (2 + 7f+1 (zx). (**)) 27k-1I) where
pd = and f8 = f. then we can approximate the reverse-time transitions in Proposition 2 by k (Ix (x)+))
Pi (#e+1 (x) expllogp((xx)) log Ph+1 (#x+1))
N [zxs Ta++ + 7 184100+11 (#*+1). (6 11x+
with (1x41) - (1x++1 2V log pb+1 (1x+1). We can also approximate the forward transitions Proposition 2 by p Petil (2 (wx) R N( + 7h+ 7 (mt), ( with fk p=+1 (2x) - b% (xx)+ +2V log de (zx). Hence we have fr (xx) = fl (=x) 2V pi (xx) 2V log g% (Ix). ). It follows that one could estimate fr+1 bbt+1 by using score- matching to approximate {V log pk_ (z) (V log of {-)) This approach is prohibitively costly in terms of memory and compute, see Section S5. We follow an alternative approach which avoids these difficulties.
Proposition 3. Assume that for any n N and & E (O...., 13.
Maj++ 1 (ITA (1x+1) Nxx;; B (Ix+1), 2 I), P
N( FR (Fx), 2 + II,
with BR (x) = x x 7 b7 (I), (x) = x + - (x) (c)ffor for any I E IRd, Then we have for any
n E N and k E {o..... N -1
B arg min min Epg 1 [I (X++1 + FF 1X (12)
F=+1 arg miggpeeee Egg 1+1 [((x)) - (Xe + BP (X -B+,,)))111 (13)

---

Proposition 3 shows how one can recursively approximate BK=1 and F In practice, we use neural networks Bz (k, æ) se B (z) and Far (k,z) x) & (z). Note that the networks could also be learned jointly, In this case, equilibrium, we would obtain bridge between Pdata and Pprior but not necessarily the Schrödinger bridge.
Network parameters a"; ," learnt through gradient descent minimize empirical versions of the sum over & of the loss functions given by (12) and (13) computed using M samples and denoted as e, (3) and (a). The resulting algorithm approximating L E N IPF iterations is called Diffusion Schrödinger Bridge (DSB) and is summarized in Algorithm with 2 % for illustration.
Lid. N I), see Figure 1
Algorithm Diffusion Schrödinger Bridge
The DSB algorithm is initialized us- ing the reference dynamics foo (k: x) = can cas- ily approximately sample from Pant by sampling XN Pprie and then using XR-1 B3 (N:, X&) 22nu Zu with
1: for E {0,.... ......,,) L) do
f(z). Once 3 is learnt
2: while not converged do N.M
Sample 1 k.j=0' where X ~ Panta and
X = Pa (k, X 22
4: Compute é,, (8²) approximating (12)
Z₁ ~ (), The resulting samples Xo will be approximately distributed from Pdata Although DSB requires learn- ing a sequence of network parameters, a", ,"8 fewer diffusion steps needed compared to standard SGM. In addition, detailed in Section S9, 3 may be trained efficiently in a similar manner previous SGM methods. Subsequent a=+1, ,8 are refinements of a" ,r" hence may be fine-tuned from previous iterations.
5: 8 Gradient Step(()((")
6: end while
7: while not converged do N.M
8:
Sample ( where X3 Ppriors and
x= =B. (ks, x3) + 2 %
9:
Compute (=+1(aat) approximating (13)
10: a=+1 +- Gradient Step( (a**1))
11: end while
12:
end for 13: Output: (aL+1,34
3.4 Convergence of Iterative Proportional Fitting
In this section, investigate the theoretical properties of IPF. When the state-space is discrete and finite (Franklin and Lorenz, 1989; Peyré and Cuturi, 2019) or in the case where Pdata and Pprior compactly supported (Chen et al., 2016), IPF converges Birkhoff metric, see Lemmens and Nussbaum (2014) for a definition. Other than recent work by Léger (2020), only qualitative results exist in the general case where Pdata or Pprioe is not compactly supported (Ruschendorf et al., 1995; Rüschendorf and Thomsen, 1993). We establish here quantitative convergence of IPF in this non-compact setting as well novel monotonicity results. We require only the following mild assumption.
geometric rate w.r.t. the Hilbert-
A1. PN, Pprior 0, [[ < +00, f log pN ( (zo) Paata (Io Pprior (IN )drodæ < +00.
Assumption A1 satisfied in all of our experimental settings. We recall that for μ. E (E) with (E, measurable space, the Jeffrey's divergence is given by (1, v) KL(ulv) + (L(p)p).
Proposition 4. Assume AI. Then (πT)) is well-defiedd and for any n 2 1 we have (I(m"|="*)) (L(="(m"~))
<L( |x") < (I(T=="((=")
In addition, ( n+| T" )mlN and [((="t),""")nee )))) are non-increasing. Finally, we have limp-++0o ni (m[ (pam)) KL [Priior) 0.
more general result with additional monotonicity properties is given in Section S6. Under similar assumptions, Léger (2020, Corollary 1) established (L(=))P))) < C/n with C 2 0 using Bregman divergence gradient descent perspective. In contrast, our proof relies only on tools from information geometry. In addition, we improve the convergence rate and show that (TT)) converges in total variation towards π 70,, i.e. we not only obtain convergence of the marginals but also convergence of the joint distribution. Under restrictive conditions on Pdata and Ppriors Ruschendorf et al. (1995) showed that 2 the Schrödinger bridge. the following proposition, we avoid this assumption using results on automorphisms of measures (Beurling, 1960).
7

---

Proposition 5. Assume A1. Then there exists a solution T² E NN1 to the SB problem. Assume that 20 ||T"" -T= ||TV 0 with Thh E P N+I- Let h Po.N/ (po @ PN) and assume that E (((Rd)), (0, +oo)) and that there exist Po &N E C(R (0, +20) such that
Sgexe (flg ( + |log (o(2o) | + |log N (xx) ( D)Pasa (Fo Pprioo jdrgdæ < +00, with h(zo, ØN)= - Po(zo) (x.) If p is absolutely continuous w.E. nh" then πT n².
Proposition 5 extends previous IPF convergence results without the assumption that the mapping h is lower bounded, see Ruschendorf et al. (1995); Chen al. (2016). Our assumption on h can be relaxed and replaced by tighter condition on T, see Section S6.2. Proposition suggests a convergence rate of order o(n) for the IPF in the non-compact setting. However, in some situations, we recover geometric convergence rates with explicit dependency w.r.t. the problem constants, see Section S7. In practice, we do not run IPF for Pdata: Pprior but using empirical versions of these distributions. Recent results in Deligiannidis et al. (2021) show that the iterates of IPF based on empirical distributions remain close to the iterates one would obtain using the true distributions, uniformly in time. In particular, the SB computed using the empirical distributions converges to the one computed using the true distributions as the number of samples goes infinity.
3.5 Continuous-time IPF
We describe an IPF algorithm for solving SB problems continuous-time. We show that DSB proposed in Algorithm 1 can be seen as a discretization of this IPF, Given reference measure (C), the continuous formulation of the SB involves solving the following problem ((C)
II = arg min (I[PP) : I (C), II = Pdata I17 = Pprioct,
T= E= 7k+1-
Similarly (11), define the IPF (II*) mee with ITo P associated with (6) and for any N
I 1 = arg min {KL(I]]IT2*) II E (C),, II, = Pprior
1 = arg min {KL(II)T2*)) II P(),, IIo -Pata
One can show that for any n E N. II" Po,T. with (TT:"))EN the IPF for the static SB problem. In particular, Proposition and Proposition 5 extend to the continuous IPF framework. In what follows, for any IP E (C), we define jott as the reverse-time measure, i.e. for any A E B(C) we have (A) R) where AR {I + w(T - () w E A). The following result is the continuous counterpart of Proposition and states that each IPF iteration is associated with a diffusion, showing that DSB can be seen as a discretization of the continuous IPF.
Proposition 6. Assume Al and that there exist M E (C), E (R², R), 2 0 such that for any n E N, x Rdd (II MM) < +00. (z. (U())) 2 CC1+ 1|=13) and M is associated with dX, -x,=-VUC )dl + VddB,
(14)
with X. distributed according to the invariant distribution of (14). Then, for any n E N we have:
(a) (I R is associated with d = (Y? )t + 2dB with Ydu+i ~ Pprioni
(b) 112 is associated with ix22+2 = ft t (x, 2n-2 dt + 2dB with X 2n+2 ~ Pdarai
where for any n E N, [0,T] and x E Hdd (z) - fx)) 2V dogp(((; fr+t (x) -b² 2V logg (I), with pl (xx) f(x), see (6), and p?, of the densities of II?" and ITa+1
4 Experiments
Gaussian example. We first confirm that our algorithm recovers the true SB in a Gaussian setting where the ground truth is available. Let Pprior = (-a,, (2,1] I), Piata = (a, I) with a E Rd and consider a Brownian motion as reference dynamics. The analytic expression for the static SB is [s([[[ a, a). E) with Σ Rd2xxdd given in Section $7.2. We let 0.1 x 1 with d 50 d = In Figure we illustrate the convergence of DSB. We train each DSB with batch size of 128, N = 20 and y 1/40. We compare two network configurations: "small" where the network is given by Figure $2 (30k parameters) whereas "large" corresponds to the same network but with twice as many latent dimensions (240k parameters). The small network recovers the statistics of SB in the low-dimensional setting (d 5) but is unable to recover the variance and covariance for d = 50. Increasing the size of the network solves this problem.
8

---

Mean
Variance
Covariance
(Gl L1k 13 porpiico rood
144
12-
Figure 2: Convergence of DSB to ground-truth. From left to right: estimated mean, variance and covariance (first component) after each DSB iteration. The ground-truth value is given by the dashed line in each scenario.
Data distribution
Two dimensional toy experiments. We eval- uate the validity of our approach on toy two di- mensional examples. Contrary to existing SGM approaches we do not require that the number of steps large enough for pN R3 Pprior to hold, We use fully connected network with posi- tional encoding (Vaswani et al., 2017) to approx- imate By and FI. see Section S10.1 for details about our implementation. Animated plots of the DSB iterations may be found online project webpage?. In Figure 3, we illustrate the benefits of DSB over classical SGM. We fix f(x) = or and choose Pprior = (O0, dasta I), hence a = 1/ data where 2 is the variance of the dataset. We let N 20 and 7/ 0.01,
S
DSB Iteration
DSB Iteration 20
S
Figure 3: Data distributions Pdota distribution
t -= 0 for T = 0.2 after 1 and 20 DSB iterations.
ie. = 0.2. Since T is small, we do not have pN Rs Pprior and the reverse-time process obtained after the first DSB iteration (corresponding original SGM methods) does not yield a satisfactory generative model. However, multiple iterations of DSB improve the quality of the synthesis.
Generative modeling. DSB is the first practical algorithm for approximating the solution to the SB problem in high dimension (d = 3072 for CelebA). Whilst our implementation does not yet compete with state-of-the-art methods, initial SGMs (Song and Ermon, 2019) and demonstrate its performance on MNIST (LeCun and Cortes, 2010) and CelebA (Liu al., 2015).
show promising results with fewer diffusion steps compared to
t= 0.31 Figure 4: Generative model for CelebA 32 x 32 after 10 DSB iterations with N = 50 (7 = 0.63)
1=
t= 0.60
t= 0.63
reduced U-net architecture based on Nichol and Dhariwal (2021) used approximate B and FT. Further details are given in Section S10.2. Our method is validated on downscaled CelebA in Figure 4. Figure 5 illustrates qualitative improvement over DSB iterations with as few as N 12 diffusion steps. Note, shown in Section $10.2, we obtain better results with higher N yet still significantly fewer steps than in the original SGM procedures (Song and Ermon, 2020, 2019) which use N 100. Figure 6 illustrates how the sample quality, measured quantitatively in terms of Fréchet
bridge/

---

Inception Distance (FID) (Heusel et al., 2017), improves with the number of DSB iterations for various numbers of steps N.
3 A
02-
2 S A
2 5
2
Na
A
e
D 2
4
8
0
S 3
7
1
S
DSB
DSB
Figure Generated samples (N 12)
Figure 6: FID vs DSB Iterations.
Dataset interpolation. Schrödinger bridges not only allow us reduce the number of steps in SGM methods but also enable flexibility in the choice of the prior density Pptiors which is not necessarily Gaussian contrary previous works SGM. In particular, our approach is still valid if Pprior is any other data distribution Paaaa- In this case DSB converges towards bridge between Pdata and Paaa Figure 7. These experiments pave the way towards high-dimensional optimal transport between arbitrary data distributions.
S
0
d e C C 4
4 2
4 6 1
Ge 5 8
d D DCB
M D 2 8
BDAC
A d A
A
4 d
4 A AANCIAR
A 9 /
A AA A 4 C C 8
2
8
d C Accbaja
0
5
4
B /
8 23
8
7
2
25
Figure 7: First row: Swiss-roll to S-curve (2D). Iteration 9 of DSB with T = 1 (N
= 50). From left
to right: 0, 0.4.0.400 0.6, Second row: EMNIST (Cohen al., 2017) MNIST. Iteration 10 of
DSB with T = 1.5 (N 30). From left to right: t = 0, 0.4, 1.25,
5 Discussion
Score-based generative modeling (SGM) may be viewed as the first stage of solving a Schrödinger bridge problem. Building this interpretation, Schrödinger Bridge (DSB), that extends initial SGM approaches and allows one to perform generative modeling with fewer diffusion steps. DSB complements recent techniques to speed up existing SGM methods that rely on either different noise schedules (Nichol and Dhariwal, 2021; San-Roman 2021; Watson al., 2021), alternative discretizations knowledge distillation (Luhman and Luhman, 2021). Additionally, as the solution of the Schrödinger problem diffusion, it is possible in Song al. (2021, Section 4.3) obtain equivalent neural ordinary differential equation that admits the same marginals as the diffusion but enables exact likelihood computation, see Section S8.3. Even though the final time T > within DSB can be arbitrarily small, we observed that this has limits as choosing T too close to 0 decreases the quality of the generative models. One reason for this behavior is that if the endpoint of the original forward process is too far from the target distribution Ppeior, then learning the score around the support of Ppeior challenging even for DSB. From theoretical point of view, we have provided quantitative convergence results for SGM methods and derived new state-of-the-art convergence bounds for IPF as well as novel monotonicity results. We have demonstrated DSB on generative modeling and data interpolation tasks. Finally, although this work was motivated by generative modeling, DSB is much more widely applicable as can be thought of as the continuous state-space counterpart the celebrated Sinkhorn algorithm (Cuturi, 2013; Peyré and Cuturi, 2019). For example, DSB could be used to solve multi-marginal Schrödinger bridges problems (Di Marino and Gerolin, 2020), compute Wasserstein barycenters, find the minimizers of entropy-regularized Gromov-Waseersten problems (Mémoli, 2011) 1) or perform domain adaptation in continuous state-spaces.
developed a novel methodology, the Diffusion
et al., 2021a) or
10

---

Acknowledgments and Disclosure of Funding
Valentin De Bortoli and Arnaud Doucet are supported by the EPSRC CoSInES (COmputational Statis- tical INference for Engineering and Security) grant EP/R034710/1, James Thornton by the OxWaSP CDT through grant EP/L016770/ 10/1 and Jeremy Heng by the CY Initiative of Excellence (grant "In- vestissements d' Avenir"
Computing resources were provided through the Google Cloud research credits programme, Arnaud Doucet also acknowledges support from the UK Defence Science and Technology Laboratory (DSTL) and EPSRC under grant EP/R013616/ This is part of the collaboration between US DOD, UK MOD and UK EPSRC under the Multidisciplinary University Research Initiative. We thank Marcel Nutz for pointing out a mistake in an carlier version of the paper.
References
Ambrosio, L.., Gigli, N., and Savaré, G. (2008). Gradient Flows in Metric Spaces and in the Space of Probability Measures. Lectures in Mathematics ETH Zürich,. Birkhäuser Verlag, Basel, second edition.
Bakry, D., Gentil, I., and Ledoux, M. (2014). Analysis and Geometry of Markov Diffusion Operators, volume 348. Springer.
Bernton, E., Heng, J., Doucet, A., and Jacob, P. E. (2019). Schrödinger bridge samplers. arXiv preprint arXiv:1912.13117
Beurling, A. (1960). An automorphism of product measures. Annals of Mathematics, 72(1):189-200.
Block, A., Mroueh, Y., and Rakhlin, A. (2020). Generative modeling with denoising auto-encoders and Langevin sampling. arXiv preprint arXiv:2002.00107.
Cai, R., Yang, G., Averbuch-Elor H., Hao, Z., Belongie, S., Snavely, N., and Hariharan, B. (2020). Learning gradient fields for shape generation. European Conference on Computer Vision.
Cattiaux, P., Conforti, G., Gentil, I., and Léonard, C. (2021). Time reversal of diffusion processes under a finite entropy condition. arXiv preprint arXiv:2104.07708.
Chen, N., Zhang, Y., Zen, H., Weiss, J., Norouzi, M., and Chan, W. (2021a). Wavegrad: Estimating gradients for waveform generation. International Conference on Learning Representations.
Chen, Y., Georgiou, T., and Pavon, M. (2016). Entropic and displacement interpolation: a computa- tional approach using the Hilbert metric. SIAM Journal Applied Mathematics, 76(6):2375-2366
Chen, Y., Georgiou, T. T., and Pavon, M. (2021b). Optimal transport in systems and control. Annual Review of Control, Robotics, and Autonomous Systems, 4.
Cohen, G., Afshar, S., Tapson, J., and van Schaik, A. (2017). EMNIST: an extension of MNIST to handwritten letters. arXiv preprint 170.0:170..
Constantine, G. M. and Savits, T. (1996). multivariate Faà di Bruno formula with applications. Transactions of the American Mathematical Society, 348(2):503-520.
Csiszár, (1975), I-divergence geometry of probability distributions and minimization problems. The Annals of Probability, 3465:166-158
Cuturi, M. (2013). Sinkhom distances: Lightspeed computation of optimal transport. In Advances in Neural Information Processing Systems.
Deligiannidis, G., De Bortoli, V., and Doucet, A. (2021). Quantitative uniform stability of the iterative proportional fitting procedure. arXiv preprint arXiv:2108.081 08199.
Dellacherie, C. and Meyer, P.-A. (1988), Probabilities and Potential. C, volume 151 of North-Holland Mathematics Studies. North-Holland Publishing Co., Amsterdam. Potential theory for discrete and continuous semigroups, Translated from the French by J. Norris.
11

---

Deming, W. E. and Stephan, F. F. (1940). On least squares adjustment of a sampled frequeney table when the expected marginal totals are known. The Annals of Mathematical Statistics, (1(4):427-444
Dessein, A., Papadakis, N., and Deledalle, C.-A. (2017). Parameter estimation in finite mixture models by regularized optimal transport: A unified framework for hard and soft clustering, arXiv preprint 1r1 .44366
Dhariwal, P. and Nichol, A. (2021). Diffusion models beat GAN on image synthesis. arXiv preprint 003553
Di Marino, S. and Gerolin, A. (2020). An optimal transport approach for the Schrödinger bridge problem and convergence of Sinkhorn algorithm. Journal of Scientific Computing, 85(2):1-28.
Douc, R., Moulines, E., Priouret, P., and Soulier, P. (2019). Markov Chains. Springer.
Durkan, C. and Song, Y. (2021). On maximum likelihood training of score-based generative models. arXiv preprint arXiv:2101.09258
Durmus, A. and Moulines, E. (2017). Nonasymptotic convergence analysis for the unadjusted Langevin algorithm. The Annals of Applied Probability, 175))155
Enderton, H. B. (1977). Elements of Set Theory. Academic Pres, New York-London.
Ethier, S. N. and Kurtz, (1986). Markov Processes. Wiley Series in Probability and Mathe- matical Statistics: Probability and Mathematical Statistics. John Wiley & Sons, Inc., New York. Characterization and convergence.
Finlay, C., Gerolin, A., Oberman, A. M., and Pooladian, A.-A. (2020). Learning normalizing flows from entropy-Kantorovve Kantorovich potentials. arXiv preprint arXiv:2006. 06033.
Föllmer, H. (1985). An entropy approach to the time reversal of diffusiin processes. In Stochastic Differential Systems: Filtering and Control, pages 156-163. Springer.
Fölmerr H. (1988). Random fields and diffusion processes. In École d'Été de Probabilités de Saint-Flour XV-XVII, 1985-87, pages 101-203. Springer.
Fortet, R. (1940). Résolution d'un système d' d'équations de M. Schrödinger. Journal de Mathématiques Pures et Appliqués, 1:83-105.
Franklin, J. and Lorenz, J. (1989). On the scaling of multidimensional matrices. Linear Algebra and Its Applications, 11::717-735.
Gao, R., Song. Y., Poole, B., Wu, Y. N., and Kingma, D. P. (2020). Learning energy-based models by diffusion recovery likelihood. arXiv preprint arXiv:2012.08125.
Genevay, A., Peyré, G., and Cuturi, M. (2018), Learning generative models with Sinkhorn divergences. In International Conference on Artificial Intelligence and Statistics.
Haussmann, U. G. and Pardoux, E. (1986). Time reversal of diffusions. The Annals of Probability, (K()):188-124)
Heusel, M., Ramsauer, H., Unterthiner, T., Nessler, B., and Hochreiter, S. (2017). GANs trained by a two time-scale update rule converge local Nash equilibrium. arXiv preprint (ttl::/0000005555
Ho, J., Jain, A., and Abbecl, P. (2020). Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems.
Hoogeboom, E., Nielsen, D., Jaini, P., Forré, P., and Welling, M. (2021). Argmax flows and multino- mial diffusion: Towards con-euvoreeressvvve language models. arXiv preprint 2rXiv:2102.05379
Hyvärinen, A. and Dayan, P. (2005). Estimation of non-normalized statistical models by score matching. Journal of Machine Learning Research, 6(4).
12

---

Ikeda, N. and Watanabe, S. (1989). Stochastic Differential Equations and Diffiusion Processes, volume 24 of North-Holland Mathematical Library. North-Hoe North-Holland Publishing Co., Amsterdam; Kodansha, Ltd., Tokyo, second edition.
Jolicoeur-Mani Martuurr,artnneau, A., Li, K., Taillefe,,, R., Kachman, T., and Mitliagkas, I. (2021a), Gotta go fast when generating data with score- based models. arXiv preprint vrXiv:2105.14080
Dolicoeur-Marticauu A., Piché-Taillefe R., Tachet des Combes, R., and Mitliagkas, (2021b). Adversarial score matching and improved sampling for image generation. International Conference on Learning Representations.
Kingma, P. and Ba, J. (2014). Adam: A method for stochastic optimization. arXiv preprint arXiv:/412.6980
Kober, H. (1939). A theorem on Banach spaces. Compositio Mathematica, 7:135-140.
Kong, Z., Ping, W., Huang, J., Zhao, K., and Catanzaro, B. (2021). Diffwave: A versatile diffusion model for audio synthesis. International Conference on Learning Representations.
Kruithof, J. (1937). Telefoonverkeersrkkennng De Ingenieur, 52:15-25.
Kullback, S. (1968). Probability densities with given marginals. The Annals of Mathematical Statistics, 39(4): 1236-12333
Kullback, S. (1997). Information Theory and Statistics. Dover Publications, Inc., Mineola, NY. Reprint of the second (1968) edition.
Laumont, R., De Bortoli, V., Almansa, A., Delon, J., Durmus, A., and Pereyra, M. (2021). Bayesian imaging using plug & play priors: when Langevin meets Tweedie. arXiv preprint arXiv:2103.0477
LeCun, Y. and Cortes, C. (2010). MNIST handwritten digit database.
Léger, F. (2020). A gradient descent perspective Sinkhorn. Applied Mathematics & Optimization, pages 1-13.
Leha, G. and Ritter, G. (1984). On diffusion processes and their semigroups in Hilbert spaces with an application to interacting stochastic systems. The Annals of Probability 12(4):0077-1112
Lemmens, B. and Nussbaum, R. D. (2014). Birkhoff's version of Hilbert's metric and its applications in analysis. Handbook of Hilbert Geometry, pages 275-303.
Léonard, C. (2014a). Some properties of path measures. In Séminaire de Probabilités XLVI, pages 207-230. Springer.
Léonard, C. (2014b). A survey of the Schrödinger problem and some of its connections with optimal transport. Discrete & Continuous Dynamical Systems-A, 34(4):1533-1574
Léonard, C. (2019). Revisiting Fortet's proof of existence a solution to the Schrödinger system. arXiv preprint 1rXiv:1904.132.
Liptser, R. S. and Shiryaev, A. N. (2001). Statistics of Random Processes. I, volume of Applications of Mathematics (New York). Springer-Vertee Verlag, Berlin, expanded edition. General theory. Translated from the 1974 Russian original by A. B. Aries, Stochastic Modelling and Applied Probability.
Liu, Z., Luo, P., Wang, X., and Tang. X. (2015). Deep learning face attributes in the wild. In International Conference on Computer Vision.
Luhman, E. and Luhman, T. (2021). Knowledge distillation in iterative generative models for improved sampling speed. arXiv preprini arXiv:2101.02388.
Luhman, T. and Luhman, E. (2020). Diffusion models for handwriting generation. arXiv preprint arXiv:2011.0677
Mémoli, F. (2011). Gromov-Wassersten distances and the metric approach object matching. Foundations of Computational Mathematics. 11(4):417-487.
13

---

Meyn, S. P. and Tweedie, R. L. (1993). Stability of Markovian processes. III. Doster-Lyapuma criteria for continuous-time processes, Advances Applied Probability. 25(3):518-544
Mikami, T. (2004). Monge's ' problem with a quadratic cost by the zero-noise limit of h h-path processes. Probability Theory and Related Fields, 129(2):245-28)
Nichol, A. and Dhariwal, P. (2021). Improved denoising diffusion probabilistic models. arXiv preprint arXiv:2102.09672.
Niu, C.. Song, Y., Song, J., Zhao, S., Grover, A., and Ermon, S. (2020). Permutation invariant graph generation via score-based generative modeling. In International Conference on Artificial Intelligence and Statistics.
Pavon, M., Trigila, G., and Tabak, E. G. (2021). The data-driven Schrödinger bridge. Communications on Pure and Applied Mathematics, 14:1545-1573.
Peyré, G. and Cuturi, M. (2019). Computational optimal transport. Foundations and Trends@ in Machine Learning, 1 1(5-6))355-607,
Popov, V., Vovk, I,, Gogoryan, V., Sadekova, T., and Kudinov, M. (2021). Grad-tts: A diffusion probabilistic model for text-to-speech. arXiv preprint arXiV:2105.06337.
Reich, S. (2019). Data assimilation: the Schrödinger perspective. Acta Numerica, 28:635-711.
Revuz, D. and Yor, M. (1999). Continuous Martingales and Brownian Motion, volume 293 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Priinge--Verlag, Berlin, third edition.
Rogers, L. C. G. and Williams, D. (2000). Diffussins, Markov processes, and martingales. Vol. 2. Cambridge Mathematical Library. Cambridge University Press, Cambridge. ltô calculus, Reprint of the second (1994) edition.
Ruschendorf, et al. (1995), Convergence of the iterative proportional fitting procedure. The Annals of Statistics, 23(4): 160-1174.
Rüschendorf, and Thomsen, W. (1993). Note on the Schrödinger equation and i-projections. Statistics & Probability letters, 1765):369-375
Saharia, C., Ho, J., Chan, W., Salimans, T., Fleet, D. J., and Norouzi, M. (2021). Image super- resolution via iterative refinement. arXiv preprint arXiv:2/04.07636
San-Roman, R., Nachmani, E., and Wolf, L. (2021). Noise estimation for generative diffusson models. arXiv preprint arXiv:2104.02600
Schrödinger, (1932). Sur 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.
Silvester, J. R. (2000). Determinants of block matrices. The Mathematical Gazette, 84(501):460-467.
Sinkhorn, R. and Knopp, P. (1967). Concerning nonnegative matrices and doubly stochastic matrices. Pacific Journal of Mathematics, 21(2):343-348.
Sohl-Dickstein, J., Weiss, E., Maheswaranathan, N., and Ganguli, S. (2015). Deep unsupervised learning using nonequilibrium thermodynamics. In International Conference Machine Learning.
Song. J., Meng. C., and Ermon, S. (2020). Denoising diffusson implicit models. arXiv preprint arXiv:2010.02502.
Song. Y. and Ermon, S. (2019). Generative modeling by estimating gradients of the data distribution. In Advances in Neural Information Processing Systems.
Song, Y. and Ermon, S. (2020). Improved techniques for training score-based generative models, In Advances in Neural Information Processing Systems.
14

---

Song, Y., Sohl-Dickstein, J., Kingma, D. P., Kumar, A., Ermon, S., and Poole, B. (2021). Score-based generative modeling through stochastic differential equations. International Conference on Learning Representations.
Tzen, B. and Raginsky, M. (2019). Theoretical guarantees for sampling and inference in generative models with latent diffusions. Conference on Learning Theory, 99:3084-33 -1144
Vargas, F., Thodoroff, P., Lawrence, N. D., and Lamacraft, A. (2021). Solving schrödinger bridges via maximum likelihood. arXiv preprint arXiv:2106.0208/
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. (2017). Attention is all you need. In Advances in Neural Information Processing Systems.
Vincent, (2011). connection between score matching and denoising autoencoders. Neural Computation,
Wang, G., Jiao, Y., Xu, Q., Wang, Y., and Yang, C. (2021). Deep generative learning via schrödinger bridge. In International Conference on Machine Learning.
Watson, D., Ho, J., Norouzi, M., and Chan, W. (2021). Learning to efficiently sample from diffusion probabilistic models. arXiv preprint arXiv:2106 106.03882.
15


Reviews:
[{"review_id": "oAaH4SY1BLc", "reviewer": "Reviewer_hQmL", "summary": "The authors present a generative model based on the Iterative Proportional Fitting of the Schrödinger Bridge problem. They provide convergence analysis of their proposed algorithm, and show the performance of their algorithm with image generation and datasets interpolation.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Novelty: \nThis paper introduces a novel score-based generative model based on the Iterative Proportional Fitting of the Schrödinger Bridge problem. The proposed algorithm can be used as optimal transport between any distributions, which is also new, compared to existing score-based models. \n\n# Major concern:\nThe originality claimed in the paper is overestimated, and related works are not properly cited. In line 314, the authors said they have provided the first convergence result for SGM methods. As far as I know, the convergence of SGM has been studied by Block et al. 2020 and Wang et al. 2021. Also in line 283, the authors claim that their method DSB “is the first practical algorithm for approximating the solution to the SB problem in high dimension”. They should clearly discuss the connection and difference between their proposal and the method in Wang et al. 2021 which also utilizes SB for generative modeling. \n\nOverall, the paper is well-written and theoretically sound, and the authors show the image generation and interpolation results on image datasets and the reproducibility is good. This work has worthy contribution to the SGM methods.\n\nReference:\nBlock A, Mroueh Y, Rakhlin A. Generative modeling with denoising auto-encoders and Langevin sampling[J]. arXiv preprint arXiv:2002.00107, 2020.\nWang G, Jiao Y, Xu Q, et al. Deep Generative Learning via Schr\\\"{o} dinger Bridge[J]. In ICML 2021, arXiv preprint arXiv:2106.10410, 2021.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "16"}, "extra_text": {}}, {"review_id": "hCfu7m0f6m", "reviewer": "Reviewer_QQ6H", "summary": "Leveraging recent advance in score-based generative modeling with SDEs, this paper proposes to solve high dimensional Schrodinger bridge problems by iteratively training score-based models. The method is the first to effectively solve Schrodinger bridge problems in high dimensional spaces, with demonstrations on distributions of real-world images, and can be viewed as a generalization to the previous SDE approach for score-based generative modeling.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Score-based generative models/ diffusion models have attracted increasing attention for theorists and practitioners in machine learning. This work shows that the basic ideas of them can be generalized to solve high dimensional Schrodinger bridge problems, all while enabling new capabilities and applications. Here are several important advantages of this submission:\n\n1. Clear writing. Although fully understand everything in this submission definitely requires some background on stochastic analysis, authors have done a good job on conveying the intuition and basic concepts, which is not an easy task. The discussion on discrete cases makes it much easier for readers to intuitively comprehend the continuous case (Schrodinger bridges are defined as a continuous case) without much background.\n\n2. Solid theoretical analysis. Theorem 1 bounds the deviation of distributions with imperfect score estimations, and provides one of the first proofs of the convergence of SGMs. Section 3.4 proves the convergence of iterative proportional fitting in non-compact settings. Both are very solid contributions.\n\n3. The proposed framework generalizes score-based generative modeling with SDEs. The prior distribution is no longer required to be tractable, as long as samples can be obtained. The training procedure of prior work can be viewed as one step of iterative proportional fitting. As a result, the proposed method can be leveraged to fine-tune existing score-based models for better matching the prior, and allows additional applications like dataset interpolation.\n\nBelow are some drawbacks and questions for the authors:\n\n1. Shorter time intervals doesn't necessarily mean smaller number of iterations for sampling. The time scales of SDEs can be rescaled arbitrarily, so we can have arbitrarily small time horizon without having any practical difference. From this perspective, I'm not convinced that Schrodinger bridges can speed up sampling of score-based models in the general case.\n\n2. In section 3.3, authors claim that using score matching to approximate $\\\\{ \\nabla \\log p_{k+1}^i (x) \\\\}_{i=0}^n$ is prohibitively costly. However, if I understand it correctly, the mean-matching method proposed in Proposition 3 is **exactly** the same as using denoising score matching to estimate the score functions individually. \n\n3. Experiments are relatively weak as results are not competitive with previous score-based models on SDEs, and image resolutions are small.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No obvious concerns.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "bQbx-XgYCFF", "reviewer": "Reviewer_dJt4", "summary": "The paper proposes a novel training method to solve Schrödinger bridge (SB) problems by performing (approximate) iterative proportional fittings (IPFs). \n- SB problems is to find a diffusion process defined in a finite time range $t \\\\in [0, T]$ for given marginals at the two ends in time $t = 0, t=T$. Specifically, the paper focuses on cases when diffusion processes have state-independent and time-homogeneous diffusion terms. Note that SB problems can have variant conditions; for example, one gives a reference diffusion instead of the two marginals. \n- Classical IPFs solve SB problems when a reference diffusion is provided instead of the marginals at two time ends. IPFs iteratively solve optimization problems. With the given initial distribution at one end, each optimization problem finds a diffusion in one time direction by minimizing the reverse KL between it and a target. Here, the target is the previous step's solution (a diffusion runs reversed in time). Each IPF step alternates the time direction by setting initial distributions correspondingly. The first target is set to the reference distribution of the SB problem. For some limited cases, it has been proven that IPFs solve SB problems by repeating the optimizations.\n\nIn order to motivate the proposed method, the paper first shows that for discrete-time IPFs, the optimal solution $q_{k|k+1}^{n}$ of $n$-th IPF iteration (of one time direction) is the posterior $p_{k|k+1}^{n}$ of the previous step's solution $p_{k+1|k}^{n}$: the result also holds for reversed direction. Instead of minimizing the reverse KL on the entire path in time, the authors emphasize that one can minimize per-time-step loss between a current estimate and the previous optimal.\n\nThe paper then shows that there are two properties for discrete-time IPFs, when diffusion terms are state-independent and time-homogeneous diffusions. First, the optimal solution $q_{k|k+1}^{n}$ per each time step must follows the well-known reserve diffusion formula, which includes the target's $k$+$1$-th marginal score function $\\nabla \\log p_{k+1}^{n}$ (Song et al, 2021). Next, instead of using score functions, the optimal $q_{k|k+1}^{n}$'s mean can be written as the conditional expected value of $X_{k+1} + F_{k}^n(X_k) - F_{k}^n(X_{k+1})$ under $p_{k+1|k}^{n}$, where $F_k^n(\\cdot)$ is the mean function of $p_{k+1|k}^{n}$. Intuitively, this can be understood as representing marginal score as conditional expectation of finite difference.\n\nFinally, acknowledging these two properties, the paper proposes a novel (approximate) IPF method named Diffusion Schrödinger Bridge (DSB). Assume we have marginals at the two ends in time $t = 0, t=T$. Define two discrete-time Markov chain models: one runs in one time direction, and the other runs in reverse-time, combined with their corresponding initial distributions. For each $n$-th DSB step, by fixing one chain, e.g. $p_{k+1|k}^{n}$, the other chain $q_{k|k+1}^{n}$ learns their optimal mean by minimizing mean-squared loss, whose target is the conditional expected value of $X_{k+1} + F_{k}^n(X_k) - F_{k}^n(X_{k+1})$ under $p_{k+1|k}^{n}$. By alternating time directions of these mean matchings, both Markov chains learn to map from one distribution at one end to another. While the proposed method indirectly solves one IPF step, the authors demonstrate that the proposed methods converge in practice. The authors also emphasize that the proposed method works as long as sampling from the marginal distributions at two time-ends is available.\n\nFurthermore, the paper improves theoretical analysis in previous studies on IPFs to solve SB problems and score matching. In particular, the paper shows the convergence of both the discrete-time and continuous-time IPFs under more general assumptions. Another example includes the convergence of learning continuous-time diffusion-based generative models via score matchings for state-independent and time-homogeneous diffusion.\n\nIn the experiments, the paper demonstrates that the proposed DSBs can be used in generative modeling and modeling interpolations between two distributions.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "(Originality & Significance)  \nIn my understanding, the paper's contributions are clear, and I also consider that the results are essential for several reasons:  \nFirst, it introduces a novel learning model to attack SB problems, learning diffusions between two distributions, which is previously known to be challenging for high-dimensional settings.  \n\nSecond, the proposed method can be applied to various application cases, including generative models and learning random processes that transform one distribution to another. The proposed method can also be understood as one type of generalization of now-popular diffusion-based generative models. Moreover, the proposed method can be extended to more general cases beyond state-independent and time-homogeneous diffusions.  \n\nThird, the paper provides thorough theoretical discussions to motivate the proposed method.  \n\nFinally, the paper demonstrates the effectiveness of the proposed method by a series of experiments.  \n\n\n(Quality & Clarity)  \nIn general, the paper has a well-organized structure to motivate the proposed method and provide thorough discussions on relevant topics. However, the following aspects of the paper can be improved.\n\nFirst, discussions on the limitations of the proposed method can be improved. I found that the main text only emphasizes the pros of the proposed method without discussing any of its critical drawbacks. For example, the paper only states that the proposed method improves generation qualities for a given number of discretization steps compared to previous diffusion-based models. However, the main text doesn't correctly mention that the improvement is achieved by increasing the training time. Moreover, I can only find many non-trivial implementation tricks of DSB at the very end of the supplementary materials. Without properly mentioning such characteristics of the proposed method, the main text sounds misleading to me.\n\nSecond, the connection between Theorem 1 and the proposed method can be improved. I initially thought that Theorem 1 is introduced to prove the convergence of the approximate IPS (= DSB) (maybe I'm wrong). However, I couldn't find if Theorem 1 is used to discuss the convergence of the proposed method.\n\n(Typos)  \n- Lines 609-610, $p_{k|k+1}$ → $p^n_{k|k+1}$.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "(Limitations)  \nI strongly believe that the paper is excellent. However, I'm concerned that the limitations of the proposed method are understated. Improving such discussion will enormously improve the quality of the paper.\n\n(Societal Impact)\nN/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": ">12hrs"}, "extra_text": {}}, {"review_id": "-lgrC17KpJc", "reviewer": "Reviewer_TxZC", "summary": "The paper introduces a new method to iteratively refine a diffusion-based generative model, that is motivated by the so-called Schrödinger-bridge. The method amounts to iteratively train a forward and a backward model, in a manner that is simpler than previous work.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is definitely a great read, although it is a bit hard to follow at some crucial parts. The contribution is very interesting and will definitely prove very inspiring to many researchers, I recommend acceptance.\n\nHere are my comments on the fly:\n\n\n* Figure 1 is not really informative and should be extended to better represent what happens at each step\n* I guess approximation (4) is classical ? It would be better to write \"The following approximation is usually made\" instead of using \"we\", that would make it clearer it's not a contribution\n* is the other formulation for \\theta^\\star that uses all the \\log p_{k|k-1}(X_k|X_{k-1}) instead of p_{k|0} equivalent and also principled theoretically, or is it some kind of approximation ?\n* I think that your short discussion after th.1 is very interesting, but it's hard for me to understand why the second term for the bound is related to the increase of \\alpha. Could you please be a bit more precise on that point ?\n\n* I don't think your notations on the \"static Schrödinger bridge problem\" are easy to follow. What is \\mu_{0,N} exactly ? Is it the restriction of \\mu on 0 and N ? I guess that's the case, but the notation is a bit confusing. Maybe writing something like \\mu_{0:N}=\\mu_{0,N}\\mu_{1:N-1\\mid0,N} or something in this vein would be a bit clearer\n\n* As it is worded, I don't understand whether the result from Mikami holds only in the case of the gaussian transition probability P_{k+1\\mid k}.\n\n* From the point at which you introduced the SB problem, I think you should provide some wordy explanation regarding what you have and what you want to achieve. If I understand correctly, the objective is to progressively refine the transportation through iteratively apply this static SB problem ? There could be a figure about this giving the big picture, or something of the like. I must tell that the paper starts to be a bit hard to follow here.\n\n* The proposition 2 appears as very nice. However, I would once again gladly use a support figure to make the ideas clearer, that could very advantageously replace your current figure 1 that is not informative at all.\n\n* Proposition 3 seems like the central part of the paper, that holds the core contribution. However, I don't manage to understand where equations (12)-(13) come from, they are not sufficiently explained in my opinion, especially considering the space you take to explain other less important things. Please take the time to better explain the reason for these.\n\n* regarding figure 1 and proposition 3: it would be way more effective to have a figure where your actual networks appear (the B(k,x) and F(k,x)).\n\n* Is it important to train \\beta^0 using previous SGM methods, or would you propose an alternative easier way ?\n\n* Reading the text, it looks like we'll have to store all the N networks, but actually it looks like only the last one may be stored, so that we actually discard the other ones on the way, right ?\n\n\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't think there are any particular societal impact for this work that would require special treatment.\n\nRegarding the limitations, it is true that it could be interesting to have their opinion on what are actually the main weaknesses of their method to know which parts could benefit from further research.", "review_text": "", "extra_scores": {"ethical_concerns": "nothing particular", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers recommended accepting this paper, and even if there were a number of concerns, the consensus among the reviewers was clear. This was an enjoyable paper to read and I recommend that you address the issues raised by the reviewers in the camera-ready, and especially pay attention to the comments regarding improving clarity and facilitating understanding.
Decision: Accept (Spotlight)