Learning Diffusion Bridges on Constrained Domains
Authors: Xingchao Liu
Lemeng Wu
Mao Ye
qiang liu
Venue: ICLR 2023 notable top 25% (2023)

Abstract: Diffusion models have achieved promising results on generative learning recently. However, because diffusion processes are most naturally applied  on the unconstrained Euclidean space $\mathrm{R}^d$, key challenges arise for developing diffusion based models for learning data on constrained and structured domains. We present a simple and unified framework to achieve this that can be easily adopted to various types of domains, including product spaces of any type (be it bounded/unbounded, continuous/discrete, categorical/ordinal, or  their mix). In our model, the diffusion process is driven by a drift force that is a sum of two terms: one singular force designed by $Doob's~ h$-$transform$ that ensures all outcomes of the process to belong to the desirable domain, and one non-singular neural force field that is trained to make sure the outcome follows the data distribution statistically. Experiments show that our methods perform superbly on generating tabular data, images, semantic segments and 3D point clouds. 

Published as a conference paper at ICLR 2023
LEARNING DIFFUSION BRIDGES ON CONSTRAINED DOMAINS
Xingchao Liu, Lemeng Wu, Mao Ye, Qiang Liu Department of Computer Science University of Texas Austin [xcliu, Imwu, my21, 1qi @cia lta.:/a..uttxs.c...mm utexas.edu
ABSTRACT
Diffusion models have achieved promising results on generative learning recently. However, because diffusion processes are most naturally applied on the uncon- strained Euclidean space Id key challenges arise for developing diffusion based models for learning data on constrained and structured domains. We present a simple and unified framework achieve this that can be easily adopted various types of domains, including product spaces of any type (be it bounded/unbounddd, continuous/diserete, categorical/ordinal, sion process is driven by a drift force that is a sum of two terms: one singular force designed by Doob's h-Iransform that ensures all outcomes of the process to belong to the desirable domain, and one non-singular neural force field that is trained make sure the outcome follows the data distribution statistically. Ex- periments show that our methods perform superbly on generating tabular data, images, semantic segments and 3D point clouds. Code is available at https:
their mix). In our model, the diffu-
INTRODUCTION
Diffusion-based deep generative models, notably score matching with Langevin dynamics (SMLD) (Song & Ermon, 2019, 2020), denoising diffusion probabilistic models (DDPM) (Ho et al., 2020), and their variants (e.g., Song et al., 2020b,a; Kong & Ping, 2021; Song et al., 2021; Nichol & Dhariwal, 2021), have shown to achieve new state of the art results for image synthesis (Dhariwal & Nichol, 2021; Ramesh et al., 2022; Ho et al., 2022; Liu et al., 2021), audio synthesis (Chen et al., 2020; Kong et al., 2020), point cloud synthesis (Luo & Hu, 202 b; Zhou et al., 2021), I), and many other Al tasks. These methods train deep neural network to drive drift force diffusion process to generate data, and are shown to outperform competitors, mainly GANs and VAES, on stability and sample diversity (Xiao et al., 2021; Ho et al., 2020; Song et al., 2020b).
However, due to the continuous nature of diffusion processes, the standard approaches are restricted generating unconstrained continuous data in Rd. For generating data constrained on special struc- tured domains, such as discrete, bound data or mixes of them, special techniques. e.g.. dequantiza- tion (Uria et al., 2013; Ho et al., 2019) and multinomial diffusion (Hoogeboom et al., 2021; Austin et al., 2021), I). need to be developed case by case and the results still tend to be unsatisfying despite promising recent advances (Hoogeboom al., 2021; Austin et al., 2021).
This work proposes a simple and unified framework for learn- ing diffusion models on general constrained domains Ω em- bedded in the Euclidean space Rd The idea is to learn a continuous -ad-ue diffusion process Z, on time interval t E [0, 7), with carefully designed force field, such that the final state Zt guarantees to 1) fall into the desirable domain Q and 2) follows the data distribution asympiotically. We achieve both steps by leveraging a key tool in stochastic calculus called Doob's 's h-transform (Doob, 1984). which provides formula for deriving the diffusion processes whose final states are guaran- teed to fall into specific equal specific value.
p
Time t
Figure An 2-Bridge on discrete do-
main Ω2 = (1, 3,4).

---

Published as a conference paper at ICLR 2023
Algorithm Learning Diffusion Models Constrained Domains (a Simple Example)
Input: A dataset = (x(*) drawn from distribution II on domain = {e1, ................................ ek). Goal: Learn diffusion model that terminates at time T to generate samples from III. Learning: Solve the optimization below with stochastic gradient descent (or other optimizers)
! EAND (2s) Vz log wx Ze, tc, dt,
0- arg min 0
(1)
where
|| 2012
exp
2(T - 1)
t 74
t(T t).
w (x
1,,
aro
T E,
(2)
13 e11 2(
T
Σ exp EEn
with r drawn from the dataset D, f ~ NN I), and 2o any initial point. Sampling: Generate sample Zr from
dZ [ 1 (2x, (Zx
(111, 11 2(T - 1) --11--111) di dW,, Zo z0-
Zz log
exp
Remark When the domain J is manifold (e.g., line or surface) in Rd simply replace the sum Ecen with the corresponding line or surface (in general Hausdorff) integration Sg on f2
Our simple procedure can be applied any domain Ω once properly defined summation (for discrete sets) or integration (for continuous domains) can be evaluated. To give a quick overview on the practical intuition without invoking the mathematical theory, show in Algorithm simple instance of the framework when the domain is discrete set Ω = (eI,-..,ex] The idea is to set up the diffusion model have form of
1|2- el1 2(T - 1)
dz, - v2 (Z,, dt dWW (² log Σ exp eEll
V
(3)
where the drift is sum of non-singular (e.g., bounded) term (z, which is trainable neural force field with parameter 0, and a singular term V ( (2,t), t), which drives Ze towards set Ω as (2,t). t). The (2, t) measures the closeness of to set Ω2 as the log- ligelikelihood of a Gaussian mixture model (GMM) centered on the elements in Ω with variance T t. When t approaches to the terminal time T, the variance T / of the GMM goes zero, and the magnitude of V R2, 1) grows to infinity, hence ensuring that Zr must belong to Ω. In particular, note that
gradient ascent on d (2,
|=-e|| exp
(z,t)
Σ eEL
(E 2,1) 2
6-2 T-1
(e 2,t)
2(1-1)
exp(v> (2,
which increases with an O(1((T -t)) rate as f -> T: here w ( 2. !) is the softmax probability measuring the relative closeness of z to the elements e Q (see also Eq (2)).
As show in Section 2.3, once f is non-singular in the sense of the mild condition of fe Bil]|" (Zz, t) [|] ( +00, the diffusion model (3) guarantees yield a final state Zr that belongs to 52, and hence provides flexible model family on Ω. Moreover, as shown in Eq 1 in Algorithm I, the neural field fo can be simply trained to approximate
log " 2, t) with plugged as the data point that we expect to achieve when starting from at time t. Intuitively, such fitted f increases the relative probability of the observed data points and hence allows us to fit the data distribution. Empirically, diffusion models learned through R-bridge achieves favorable results in generating mixed discrete/comtinuouss tabular data, point clouds on grids, categorical semantic segments and discrete CIFAR 10 images.
2

---

Published as a conference paper at ICLR 2023
Outline The rest of the paper is organized as follows. Section 2 introduces h-transform, which allows us to derive bridge processes that are guaranteed to enter specific sets at the terminal time, and Section 2.3 specifies the parametric diffusion models for 1-bridges. Then, with the learnable diffusion models, Section 3 introduces the general learning framework along with the loss function.
BACKGROUND: DIFFUSION PROCESSES AND T-TRASSFORM
diffusion process Z [Z E [0, l]} on Rdd follows a stochastic differential equation of form Q dZ = bZ t)dt + (Ze, ()dW,,
where We is Wiener process, and [0. Rd R is positive diffusion coefficient, and b E [0, 7' x IRd + Rd is a drift function. We use Q (or P) to denote the path measure of stochastic processes Z, which are probability measures the space of continuous paths. Let Qr be the marginal distribution of Z, at time / under Q.
Our framework heavily relies the bridge processes, special stochastic processes that guarantee achieve a deterministic value or fall into given set at the final state I".
For a set Q S Rd. a process in I2d with law called an ft-bridge ifQ(Zz Q)) = 1.
One natural approach to constructing bridge processes is to derive the conditioned process of a general unconstrained process given that the desirable bridge constraint happens. Specifically, as- sume that Q is the law of a general unconstrained diffusion process of form (4), and denote by (P)-) = Q ZT 52) the conditioned distribution given that the event of Zr E S happens. Then Q is guaranteed to be an f2-bridge by definition. Importantly, remarkable result from Doob (Doob, 1984), now known as h-transform, shows that Q is the law of diffusion process with properly modified drift term. Below, we introduce this results, first for the case x-bridge when Ω = { includes a single point, and then for more general sets For simplicity, we only state formula from h--ransform that useful for without proofs. See e.g., Oksendal (2013); Rogers & Williams (2000) for more background on h-transform.
2.1
x BRIDGES
Let us first consider the x-bridge Q+(+) == Q( ZT x)) the process Q pinned a deterministic terminal point Zr = x. By the result from h-transform (see e.g., Oksendal (2013)), the conditioned process (-) = (- Zr = 2), if exists, can be shown be the law of
dz, = (MZ,, t) + 2 V, log ( Z)) dt + aZ, f)WW.
(5)
where (2/2)) is the density function of the transition probability
Qrie(dr 2) = Q(Zr E dx Z, = =).
where dæ denotes an infinitesimal volume centering around a. Compared with the diffusion pro- cess (4) of Q, the main difference is that the conditioned process has additional drift force o² V) & log (z])) which plays the role of steering Z, towards the target Zr this is singular force whose magnitude increases to infinity as t > T, because @T ( 2) is a delta measure centered z when i = T.
In addition, by Bayes rule, the distribution of the initial state Zo should be given by Zo Qojr( xx)
Qop (dz|æ) x Qo(d2)er)o(===)) Example 2.1. If Q is the law of d7, adWW, we have Q+))(+))) NN(2, Br Bc), where 3t 1or ds... Hence, following the formula in (5), O = Q(-1Z = x) is the law of Z,
(6)
d2. 0, 3r 3,
dt + o,dW,
and Zu ~ (d2) x (o(d))0(z 2, - Bt), and o(,),u, d²) is the density function of N o?). The process in (7) is known (time-scaled) Brownian bridge. Note that the drift in (7) grows to infinity in magnitude with a rate of ((1 - Bt)) as t + T, which ensures that Ze = z with probability one.
3

---

Published as a conference paper at ICLR 2023
Arbitrary initialization To make (5) the conditioned process of (4), the initial distribution must follow the Bayes rule in (6). However, thanks to the singular force V. log ( 2). the process (5) can guarantee Zí- z from arbitrary initialization once the process is well defined. When the initialization is different from (6), the process in (5) is no longer the conditioned process of (4), is still guaranteed. To see why this is the case,
but it remains to be an x-bridge in that Z4 assume that Q is initialized from a deterministic point Zo = Io. Then we would still have Zo, = 20 when conditioned on ZT E 9 by Bayes rule. This suggests that (5) starting from any deterministic initialization is the condition process of Q with the same deterministic initialization, and is hence an z-bridge. As a result, (5) from any stochastic initialization is also an z-bridge because it can be viewed as the mixture of the processes with different deterministic initialization, all of which are a --birdges. See Appendix A.4 for a detailed analysis, in which shown that (5) with an arbitrary initialization can be viewed as the conditioned process of a special class of non-Markov processes called reciprocal process.
2.2 Q-BRIDGES
More generally, for the law Q of (4) and set S2 E R2, the 2-bridge Q Q(- Zr Q) follows
dZ = 7 (Z,, t)dt + t)dW
(8)
with (z,t)) b(z + (z, t) V ( =)], Zo ~ Qorr(
| 2r E (2),
where drift force n7 is similar to that of the z-bridge in (5), except that the final state æ is now randomly drawn from an Q-truncated (or f-conditioned) transition probability:
Qrj, =2 == Q(Zr E dæ E2 = z, Zr E S)),
which is the transition probability from Z, to Zr, conditioned on that ZT E Q. In practice, its form can be derived using Bayes rule. Example 2.2. Assume follows dZ, o. Then Q2 yields the following Ω-bridge:
dz = 10 ozwd..
o.dW
(2, o.
x
Br 3.
where Na(2, 02) = Law(2 (Z) | Z E Q) with Z ~ NNH, 0²), which is an I-truncated Gaussian distribution ((,, d²), whose density function is Φạ(z) x I( E M) o) with Φ(z|μ, σ7) the density function of 2 o1)
Note that tractable to calculate T once we can evaluate the expectation of Na1 3r Bt). A general case is when Ω = In x ... Ia. for which the expectation reduces to one dimensional Gaussian integrals. See Appendix A.6 and A.7 for details and examples of I
As in the z-bridge, that can reach Ω following Q (precisely, points 2n that satisfy Q (nnsupppuur (-rp((Qr((ZZz = 20)) + 0) using the mixture of initialization argument.
set the initialization to be any distribution supported the set of points
2.3 A PARAMETRIC FAMILY OF 2-BRIDGES
The formula in (8) only provides a fixed process for a given Q. For the purpose of learning generative models, however, we need rich family of 12-bridges within which we can search for a best one to fit with the data distribution. It turns out we can achieve this by simply adding an extra non-singular drift force, which can be a trainable neural network, on top of the Q-bridge in (8). Specifically, we construct the following parametric diffusion model Ip:;
(10) where (2, is neural network with input (2 and parameter 0 which will be trained based on the empirical observations. Adding the neural drift (Zz.t) (Z,,,) term does not break the Q-bridge condition, once it satisfies a very mild regularization condition:
I²::
dZ. = (a(Zz,t)f' + 77 (Z,, t))dt + or tZ,,) Zo ~ P
Proposition 2.3. For any Q following d.z = (Z,, t) + of (Ze, t)dW, that is an Ω2-riddge the po in (10) is also an Q-bridge if E/ U (Z, 1) || dt) < +oo and (C TP8) < +00
4

---

Published as a conference paper at ICLR 2023
The condition on f is very mild, and it is satisfied if f is bounded. Moreover, it can easily hold even when fo not bounded. For example, assuming that fo(x) S |||=|| which holds for ReLU network with 3 = 1, we just need to require that the underlying process has a bounded moment Ez So | at) < +00, which is typical regularity condition to expect.
3 LEARNING Ω O-BRIDGE MODELS
Let {1) be an i.d.. sample from an unknown distribution II" on domain Ω S R.. Our goal is to learn the parameter for the Ω2-rridge model p6 in (10) such that the terminal distribution ZT ~ Pyg. matches the data X II.. We should distinguish TP, which is the trainable generative model, and Q, which is a fixed "baseline process" that helps us to derive methods for constructing
and learning the model. Q can be the simple Brownian motion in Example 2.1 and 2.2.
II'
As the case of other diffusion models, IP can be viewed as a model with an infinite dimensional latent variable of the intermediate tra- jectories of Z. Hence, canonical learning approach is expectation maximization (EM), which alternates between
Qui
1) stepp: estimating the posterior p = Po Z Zr = z) of the latent trajectories Z given the observation Z 2;;
Po
ttrainin
2) M-step: estimating the parameter A with Z imputed from p0...
Time
A key challenge, however, is that the posterior distribution 10 is difficult to calculate due to the presence of neural force field in Te (as the h-transform formula would have no closed form), and it need to be iteratively updated as 0 changes. Following DDPM (Ho et al., 2020), we consider a simpler approach that replaces the posterior po,= with an arbitrary x-bridge, denoted by Q This yields a simplified EM algorithm without the expensive posterior inference in the E-step. A natural choice is the conditioned process Q == (Z ZT = z), but the method works for a general x-bridge.
Specifically, let Q" = (-)(") (dæ) be the mixture of the x-bridges whose end point x is randomly drawn from the data distribution x ~ IT.. The trajectories from Q can be generated in the following "backward" way: first drawing data point æ II", and then Z Q conditioned on the end point Obviously, by construction, the terminal distribution of Q equals II", that is, Q4 II. Then, the model pd can be estimated by fitting data drawn from Q" using maximum likelihood estimation:
min {c(0)= = KCIQ" =C( [1)))
||
(11)
The classical (variational) EM would alternatively update (M-step) and Q (E-step) make Q p0,z Why is it OK to simply drop the E-step? At the high level, it is the benefit from using universal approximators like deep neural networks: if the model space of Td is sufficiently rich, by minimizing the KL divergence in (11), Ie approximate the given Q"" well enough (in way that is made precise in the Appendix A) such that their terminal distributions
close: P9. se QT II.
Learning latent variable models require no E-step if the model space is sufficiently rich.
We should see that in this case the latent variables Z in the learned model p6 is dictated by the choice of the imputation distribution Q since we have p0.. = Q when the KL divergence in (11) fully minimized to zero; EM also achieves p0.. Q but has the imputation distribution Q determined by the model IP, not the other way.
Loss Function its general form, the x-bridge Q that we use can be a non-Markov diffusion process
dz, = (Z, + -o (Z,, dww, Zo n",
(12)
which has the same diffusion coefficient a (Zc,t) Iet in (10), and any z-dependent r7" and initial- ization fr" once the bridee condition is ensured. As the general framework, we assume that r7" can depend on the whole trajectory Z.
5

---

Published as a conference paper at ICLR 2023
Algorithm 2 Learning 22-Bridge Diffusion Models
Input: A dataset D = (xx()) drawn from distribution II" on a domain f
Setup: Specify 2-bridge O' and an St-ridde Q
Q" dz 17" (Z, + (Z,, ()
Q :2, =f (Zz, Od,,
Specify the generative model p based on Q and a neural network fo:
pº: dZ, = (o(Z, t) t) (Z,,) + ( t) + oZz, t)dW,, Zo ~ Po
Default: let Q be the law of dZ, = o,dW, and derive the bridges by h-transform as Q Q( Zr x) in Eq (7) and Q = Q(-IZz E Q) in Eq (9).
Training: Estimating / by minimizing the loss function (13) using any off-the-shelf optimizer. Sampling:
Generate sample Zr from Ipo with the trained parameter A.
Using Girsanov theorem (e.g.. Oksendal, 2013), with 1d in (10) and Q in (12), the KL divergence in (11) can be shown to equal to
2 / |oo (Ze
((0) = -E Bx-IT* Z~
log Po (Z))
(z (2, dt + const, (13)
MLEE of initial dist.
score matching
where we write s" as the overall drift force of I in (10), that is,
o2, =z,,
(2,t)
and P is the probability density function (PDF) of the initial distribution F.g Therefore, L(0) is sum of the negative log- likelioel of the initial distribution that encourages Pd ~ Q and a least squares loss between s" and 1y" In practice, we simply fix the initial distribution T be delta measure on a fixed point (say zn = 0), so only need to train the drift function f Algorithm shows a simple instance the framework when the baseline process Q is the standard Brownian
motion d2, = dW, Q Q Zz x) and a(z, () 1. Note that the least squares term in (13) can be viewed as enforcing f z o (T 17²), which reduces to f" ze V Vlog w in the case of Algorithm 1.
Related Works Bridge processes provide a simple and flexible approach to learning diffusion generative models, which was explored in Peluchetti (2021); Ye et al. (2022); Wu et al. (2022); De Bortoli et al. (2021). Heng et al. (2021) investigates the orthogonal problem of simulating from the bridge Qa for a given Q. In comparison, our method learns diffusion models on general domains Ω on which 12-bridge can be derived (using ft-transform any other method), and hence provides a highly flexible framework for learning with structured data (including discrete, continuous, and their mixes). This distinguishes it with existing approaches that designed for special types of data (e.g., Ho et al. (2020); Hoogeboom et al. (2021); Austin et al. (2021); Li et al. (2022); Dieleman al. (2022) for discrete data). De Bortoli al. (2022) discusses how learn score-based generative models on general Riemannian manifolds. Another highly related work is Ye et al. (2022), which proposes to learn first hitting diffusion models for generating data on both discrete sets and spheres. The advantage of our approach is that it is simpler and casier to derive for more complex types of domains.
EXPERIMENTS
We evaluate our algorithms for generating mixed-typed tabular data, grid-valued point clouds, cate- gorical semantic segmentation maps, discrete CIFAR10 images. We observe that Ω-bridge provides a particularly attractive and superb approach to generating data from various constrained domains.
use Algorithm 2 with the default choice of Q" in (7) and @ in (9). The specific form of r7 is derived based on the specific choice of the domain Q. By default, set the initialization Zo 0 and the optimizer Adam.
Algorithm Overview For all experiments,

---

Published as a conference paper at ICLR 2023
Logistic (1)
AdaBoost (f)
MLP (f)
Real Training Data
0.877+0.021
0.912++0.013
0.897+0.012
TVAE (Xu et al., 2019)
0.825=0.012
0.876=:00005
0.845#0.008
CTGAN (Xu et al., 2019)
0.649+t0.014
0.841#0.021
0.843=000066
CopulaGAN (Patki et al., 2016)
0.683++0.015
0.859+0.0004
0.853+40.009
Hlixed-Bridge
0..6810.0000
0.084
0.877=1.0006
Table 1: Classification accuracy the Adult Income dataset with different classifiers when trained with data synthesized by generative models. Real Training Data shows the upper bound of the metrics.
4.1 GENERATING MIXED- TABULAR DATA
Learning to generate tabular data is challenging, because tabular data usually contains mixture of discrete and continuous attributes (Xu et al., 2019; Park et al., 2018). Unlike carefully designing special GANs in previous works (Xu et al., 2019; Srivastava et al., 2017). 92-ridgge can be seam- lessly applied to mixed-typed tabular data generation without any further modification. In contrast, diffusion processes that solely work on discrete domain (Austin et al., 2021; Hoogeboom et al., 2021) cannot be applied to this task.
In this experiment, ing samples. The data points are described by a series of attributes, including continuous (age, sapital-gate
the Adult Income dataset (Kohavi, 1996), which contains 30,162 train-
etc.) and discrete (sex, race, etc.). We compare with conditional tabular GAN (Xu et al., 2019) (CTGAN), CopulaGAN (Patki et al., 2016), and Table VAE (Xu et al., 2019) (TVAE). which are ofate-of-the-ar GAN-based and VAE-based generative models for mixed-typed tabular data. Following previous works (Xu et al., 2019; Patki et al., 2016), we measure the classifi- cation accuracy on the real data of logistic regression, AdaBoost classifier and MLP classifier when trained on the generated data.
In the b2-bridge model, we set o; cxp( 3f) and f a 3-layer MLP. this case, I1 X I15, where I to Iy are discrete domains and Iıo to I15 are non-negative continuous domains. For dis- crete domains, I = {c1,... ..), we have, 1// (,, t) = V. log EeEl exp
||s-e| 2(Br-A))) ): for non-
negative continuous domains, = [0, +o0), derivation shows 1/ (z, 1) = ofV, x log [F (((Bra)))
where F is the standard Gaussian CDF. Finally, we have (2, -1' (2,, t) for the whole domain Ω. We set the number of diffusion steps to K = 2000. Results are shown in Table 1.
Result All the three different classifiers yield the highest accuracy when trained the data gen- erated by our method. referred to as Mixed Bridge in this case. The result reflects that the data generated by Hixed-Bridge is closer the real distribution than the baseline methods.
PCD
Brride
Grid-Bridge
Method
MMD 4
COV 1
1-NNA +
Generated
PCD (Luo & Hu, 2021a)
13.37
46.60
58.94
Point Clouds
Rd -
13.30
46.52
59.32
Grid-Bridge
12.85
47.78
56.25
Reconstracted Meshes
Figure 2 & Table 2: The point clouds (upper row) generated by different methods and meshes reconstructed from them (lower row). trid-Bridge obtains more uniform points and hence better mesh thanks the integer constraints. Numbers in the table are multiplied by 10
4.2 GENERATING INTEGER-VALUED VALUED POINT CLOUDS
A feature of point clouds in 3D objects graphics that they tend to distribute evenly, especially if they are discretized from mesh. This aspect is omitted in most existing works on point cloud generation. As a result they tend to generate non-uniform points that are unsuitable for real applica- tions, which often involve converting back to meshes with procedures like Ball- Ball-Pivoting (Bemarriii

---

Published as a conference paper at ICLR 2023
Value
Disributtin
Dimension
Time t
Real
Generated
Figure 3: Results on generating categorical segmentation maps. Each pixel here one-hot vector. Each
dimension of the f2-bridge starts from deterministic and evolve through stochastic trajectory to converge either or 1. The generated samples have similar visual quality to the training data.
Methods
ELBO (L)
IWBO (L)
Uniform Dequantization (Uria et al., 2013)
1.010
0,930
Variational Dequantization (Ho et al., 2019)
0.334
0.315
Argmax Flow (Softplus thres.) (Hoogeboom et al., 2021)
0.303
0.290
Argmax Flow (Gumbel distr.) (Hoogeboom et al., 2021)
0.365
0.341
Argmax Flow (Gumbel thres.) (Hoogeboom et al., 2021)
0.307
0.287
Multinomial Diffusion (Hoogeboom et al., 2021)
0.305
Cat.-Bridge (Constant Noise)
0.844
0.707
Cat.-Bridge (Noise Decay A)
0.276
0.232
Cat.-Bridgs (Noise Decay B)
0.301
0,285
(Noise Decay C)
0.363
0.302
Table 3:
Results on the CityScapes dataset. Cat. refers to 'Categorical'.
et al., 1999). We apply our method to generate point clouds that constrained on integer grid which we show yields much more uniformly distributed points. To the best of our knowledge, we are the first work on integer-valued 3D point cloud generation.
point cloud set of points { I; E TR& in the 3D space, where m refers to the number of points. We apply two variants of our method: Rr-Bridge and Grid-Bridge. Rd-Bridge generates points in the continuous 3D space, i.e., Qg = 3m Grid-Bridg generate points that on integer grids, Pona = fl..... 128) 3m We fix the diffusion coefficient o, steps K is set to 1000. We test our method on ShapeNet (Chang et al., 2015) chair models, and compare it with Point Cloud Diffusion (PCD) (Luo & Hu, 2021a), a state-of-the-art continuous iiffusion-based generative model for point clouds. The neural network f" in methods the same as that of PCD for fair comparison. Qualitative results and quantitative results are shown in Figure 2 and Table 2. As common practice (Luo & Hu, 202 1a,b), measure minimum matching distance (MMD), coverage score (COV) and I-NN accuracy (1-NNA) using Chamfer Distance (CD) with the test dataset.
The number of diffusion
Result Both Ed and Grid- get better MMD, COV, and I-NNA than PCD. More- over, by constraining the domain of interest to the integer grids, Grid-Bridge yields even better performance than R R In Figure 2, since the point clouds generated by Grid-Bridge are lim- ited to integer grids, the reconstructed meshes from Ball-Pivoting clearly have higher quality than RddBridge and PCD.
4.3 GENERATING SEMANTIC SEGMENTATION MAPS ON CITYSCAPES
We consider unconditionally generating categorical semantic segmentation maps. We represent each pixels as one-hot categorical vector. Hence the data domain is Ω = {ei,..., Jxx where is the number classes and e is the i-th c-dimensional one-hot vector, and h, represent the height and width of the image. In CityScapes (Cordts et al., 2016), h = 32, w = 64, = 8, In this experiment, we test different schedule of the diffusion coefficient at, including (Constant Noise): a - f); (Noise Decay C) a;
oe 1; (Noise Decay A): a, = a exx(-bb)) (Noise Decay B): a(l - expp(=(11-1ppeeeeeeeeeeeee1 t))). Here a and are syper-parameters. The number diffusion steps is set to 500. We measure the negative log-likelihood (NLL) of the test set using the learned models. The is estimated with evidence lower bound (ELBO) and importance weighted bound (IWBO) (Burda et al., 2016), respectively, in (Hoogeboom et al., 2021). We compare Q-Bridge with a state-of-the-an categorical diffusion algorithm. Argmax Flow (and Multinomial Diffusion) (Hoogeboom al., 2021), and the traditional methods, uniform dequantization (Uria
NLL
8

---

Published as a conference paper at ICLR 2023
Methods
IS (T)
FID (Q)
NLL (1)
Discrete
D3PM uniform Lub (Austin et al., 2021)
5.99
51.27
5.08
D3PM absorbing Lus (Austin et al., 2021)
6,26
41.28
4.83
D3PM Gauss L.b (Austin et al., 2021)
7.75
15.30
3.966
D3PM Gauss 1x=0.001 (Austin et al., 2021)
8.54
8.34
3.975
D3PM Gauss logistic Tx=0.001
8.56
7.34
3.435
Integer- (Init. A)
8.77
6.77
3.46
Breger-Bridge (Init. B)
8.68
6.91
3.35
Integer-Bridge (Init. C)
8.72
6.94
3.40
Table 4: Discrete CIFARIO Image Generation
et al., 2013) and variational dequantization (Ho et al., 2019). The numerical results of the baselines directly adopted from (Hoogeboom et al., 2021), and experiment configuration is kept the same for fair comparison. The neural network f is the same as (Hoogeboom et al., 2021). The results shown in Figure and Table 3. Our f2-rridge is named Categorical-Bridge (Cat.-Bridge) in this experiment.
Result We observe that all the four kinds of Cat.-Bridge can successfully generate categorical mantic segments, and different noise schedules result in different empirical performance. Among the four variants of Cat.-Bridge, Cat.-Bridge with Noise Decay A yields the best ELBO and IWBO, surpassing all the other algorithms in comparison.
4.4 GENERATING DISCRETE CIFARIO IMAGES
this experiment, we apply three types of bridges. All of these bridges the same out- put domain Q =
Initialization A
255255522 hx55)xxxx hxuxe, where h, w. the height, width and number of channels of the images, respectively. We set or 3 exxp(-3t). We consider different ini- tial distributions: (Init. A) Zo = 128; (Init. B) Zo Ao. (Init. C) Zy (Āo, ou), where No and ōu are the empirical mean and variance of pixels in the CIFARIO training set. The num- ber of diffusion steps K is set 1000. We compare with the variants of state-of-the-arr discrete diffusion model, D3PM (Austin et al., 2021). For fair comparison, we use the DDPM backbone (Ho al., 2020) the neural drift f in our method, similar to D3PM. We report the Inception Score (IS) Salimans et al. (2016), Fréchet Inception Distance (FID) Heusel al. (2017) and negative log-likelihood (NLL) of the test dataset. We call our method Integer-Bridge in this The results are shown in Table and Figure 4.
Initialization
Initialization C
Time
Figure 4: integer-bridger
generate high-quality
discrete samples with different initial distribution.
with Initialization A,B,C can all get lower FIDs (S 7) than the variants of D3PM. Among the three kinds of Integer-bridges, Breger-Bridge (Init. B) obtains the lowest NLL (3.35). It also beats D3PM Gauss logistic (3.435) NLL, which has the best NLL the variants of D3PM.
Result In Table 4, Integer-Bride
CONCLUSION AND LIMITATIONS
We present framework for learning diffusion generative models on constrained data domains. leaves number of directions for further explorations and improvement. For example, the practical impact the choices of the bridges Q in terms initialization, dynamics, and noise schedule, are still not well understood and need more systematical studies. Besides, current method is limited to Ω that are factorizable and integrable. Moreover, application of Ω-bridge to many other practical fields also needs investigation in the future.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
This research is supported by NSF CAREERI 1846421, SenSE2037267, EAGER-2041327, Office of Navy Research, and NSF AI Institute for Foundations of Machine Learning (IFML).
REFERENCES
Jacob Austin, Daniel Johnson, Jomathan Ho, Daniel Tarlow, and Rianne van den Berg. Structured denoising diffusion models in discrete state-spaces. Advances in Neural Information Processing Systems, 14:11981-77993, 2021.
Fausto Bernardini, Joshua Mittleman, Holly Rushmeier, Cláudio Silva, and Gabriel Taubin. The ball-pivoting algorithm for surface reconstruction. IEEE transactions on visualization and com- puter graphics, 5(4):349-359 1999.
Yuri Burda, Roger B Grosse, and Ruslan Salakhutdinov. Importance weighted autoencoders. In
ICLR (Poster), 2016.
Angel X Chang, Thomas Funkhouser, Leonidas Guibas, Pat Hanrahan, Qixing Huang, Zimo Li, Silvio Savarese, Manolis Savva, Shuran Song, Hao Su, et al. Shapenet: An information-rich 3d model repository. arXiv preprint arXiv: 2015.
Nanxin Chen, Yu Zhang, Heiga Zen, Ron Weiss, Mohammad Norouzi, and William Chan. Wave- grad: Estimating gradients for waveform generation. In International Conference on Learning Representations, 2020.
Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bernt Schiele. The cityscapes dataset for semantic urban scene understanding. In Proc. of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
Valentin De Bortoli, James Thorton, Jeremy Heng, and Arnaud Doucet. Diffusion schrödinger bridge with applications to score-based generative modeling. Advances in Neural Information Processing Systems, 1495799997,709 2021.
Valentin De Bortoli, Emile Mathieu, Michael Hutchinson, James Thornton, Yee Whye Teh, and Arnaud Doucet. Riemannian score-based generative modeling. arXiv preprint arXiv:2202.007663, 2022.
Prafulla Dhariwal and Alexander Nichol. Diffusion models beat gans image synthesis. Advances in Neural Information Processing Systems, 34, 2021.
Sander Dieleman, Laurent Sartran, Arman Roshannai, Nikolay Savinov, Yaroslav Ganin, Pierre H Richemond, Arnaud Doucet, Robin Strudel, Chris Dyer, Conor Durkan, et al. Continuous diffu- sion for categorical data. arXiv preprint arXiv:2211.1508) 2022.
Joseph L Doob. Classical potential theory and its probabilistic counterpart, volume 549. Springer, 1984.
Jeremy Heng, Valentin De Bortoli, Amaud Doucet, and James Thortoo.. Simulating diffusion bridges with score matching. arXiv preprint 1rXiv:2/11.07244. 2021.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by a two time-scale update rule converge local nash equilibrium. Advances in neural information processing systems, 30, 2017.
Jonathan Ho. Xi Chen, Aravind Srinivas, Yan Duan, and Pieter Abbeel. Flow++: based generative models with variational dequantization and architecture design. In International Conference on Machine Learning, pp. 2722-2730. PMLR, 2019.
Improving flow-
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 33:6840 -6511, 2020.
10

---

Published as a conference paper at ICLR 2023
Jonathan Ho, Chitwan Saharia, William Chan, David Fleet, Mohammad Norouzi, and Tim Sali- mans. Cascaded diffusion models for high fidelity image generation. Journal of Machine Learning Research, 23(47):1-33, 2022.
Emiel Hoogeboom, Didrik Nielsen, Priyank Jaini, Patrick Forré, and Max Welling, Argmax flows and multinomial diffusion: Learning categorical distributions. Advances in Neural Information Processing Systems, 34, 2021.
Ron Kohavi. Scaling up the accuracy of naive-bayes classifiers: decision-tree hybrid. In Kdd, volume 96, pp. 202-207, 1996.
Zhifeng Kong and Wei Ping. On fast sampling of diffusion probabilistic models. In ICML Workshop on Invertible Neural Networks, Normalizing Flows, and Explicit Likelihood Models, 2021.
Zhifeng Kong, Wei Ping, Jiaji Huang, Kexin Zhao, and Bryan Catanzaro. Diffwave: A versatile diffusion model for audio synthesis. In International Conference on Learning Representations, 2020.
Antoine Lejay. The girsanov theorem without (so much) stochastic analysis. In Séminaire de Prob- abilités XLIX, pp. 329-361. Springer, 2018.
Christian Léonard, Sylvie Rælly, and Jean-Claude Zambrini. Reciprocal processes. measure-
theoretical point of view. Probability Surveys, 11:237-269, 2014.
Xiang Lisa Li, John Thickstun, Ishaan Guirajani, Percy Liang, and Tatsunori B Hashimoto. Diffusion-Im Im improves controllable text generation. arXiv preprint arXiv:2205.14217. 2022.
Xingchao Liu, Xin Tong, and Qiang Liu. Sampling with trusthworthy constraints: A variational gra- dient framework. Advances in Neural Information Processing Systems, 14:23557-23566 2021.
Shitong Luo and Wei Hu. Diffusion probabilistic models for 3d point cloud generation. In Proceed- ings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 2837-2844 2021a.
Shitong Luo and Wei Hu. Score-based point cloud denoising. In Proceedings of the IEEF/CVF International Conference Computer Vision, pp. 4583-4592, 2021b.
Alexander Quinn Nichol and Prafulla Dhariwal. Improved denoising diffusion probabilistic models.
In International Conference on Machine Learning, pp. 8162-8171. PMIR, 2021.
Bernt Oksendal. Stochastic differential equations: an introduction with applications. Springer
Science & Business Media, 2013.
Noseong Park, Mahmoud Mohammadi, Kshitij Gorde, Sushil Jajodia, Hongkyu Park, and Young- min Kim. Data synthesis based on generative adversarial networks. Proceedings of the VLDB Endowment, (1(1)), 2018
N. Patki, R. Wedge, and K. Veeramachaneni. The synthetic data vault. In 2016 IEEE International Conference on Data Science and Advanced Analytics (DSAA), pp. 399-4199 Oct 2016. doi: 10. 1109/DSAA.2016.49.
Stefano Peluchetti. Non-denoising forward-time diffusions. 2021.
Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. Hierarchical text- conditional image generation with clip latents. arXiv preprint arXiv:2204.06125. 2022.
L Chris G Rogers and David Williams. Diffusions, Markov processes and martingales: Volume 2, Itô calculus, volume 2. Cambridge university press, 2000.
Tim Salimans, Ian Goodfellow, Wojciech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen. Improved techniques for training gans. Advances in neural information processing systems, 29, 2016.
Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. In Interna- fional Conference on Learning Representations, 2020a.

---

Published as a conference paper at ICLR 2023
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in Neural Information Processing Systems, 32, 2019.
Yang Song and Stefano Ermon. Improved techniques for training score-based generative models. Advances in neural information processing systems, 33:12438-12445, 2020.
Yang Song, Jascha Sohl-Dickstein, Diederik Kingma, Abhishek Kumar, Stefano Ermon, and Ben
Poole. Score-based generative modeling through stochastic differential equations. In Interna- tional Conference on Learning Representations, 2020b.
Yang Song, Conor Durkan, lain Murray, and Stefano Ermon. Maximum likelihood training score- based diffusion models. Advances in Neural Information Processing Systems, 34, 2021.
Akash Srivastava, Lazar Valkov, Chris Russell, Michael U Gutmann, and Charles Sutton. Veegan: Reducing mode collapse in gans using implicit variational learning. Advances in neural informa- tion processing systems, 30, 2017.
Benigno Uria, lain Murray, and Hugo Larochelle. Rnade: The real-valued neural autoregressive density-estimator. Advances in Neural Information Processing Systems, 26, 2013.
Aad W Van der Vaart. Asymptotic statistics, volume 3. Cambridge university press, 2000.
Lemeng Wu, Chengyue Gong, Xingehao Liu, Mao Ye, and Qiang Liu. Diffusion-based molecule generation with informative prior bridges. arXiv preprint arXiv:2209.00866 2022.
Zhisheng Xiao, Karsten Kreis, and Arash Vahdat. Tackling the generative learning trilemma with
denoising diffusion gans, arXiv preprint arXiv:21 2021.
Lei Xu, Maria Skoularidou, Alfredo Cuesta- and Kalyan Veeramachaneni. Modeling tabular data using conditional gan. Advances in Neural Information Processing Systems, 32, 2019.
Mao Ye, Lemeng Wu, and Qiang Liu. arXiv:2209.01170, 2022.
First hitting diffusion models. arXiv preprint
Linqi Zhou, Yilun Du, and Jiajun Wu. 3d shape generation and completion through point-voxel diffusion. In Proceedings of the IEEE/CVF International Conference on Computer Vision pp- 1826-5835, 2021.
12

---

Published as a conference paper at ICLR 2023
Roadmap
The appendix is structured follows:
Appendix provides the theoretical analysis and derivation of diffusion bridges. In particu- lar, Appendix A.I shows the derivation of the main training loss; Appendix A.2 derives the drift term 17" of Q"" Appendix A.3 proves that mine-marginals with Q""" Appendix A.4 explains why we can use arbitrary initialization when con- structing bridge processes and discusses the reciprocal structure of Q" Appendix A.5 provides analysis on the time-discretization error and statístical error of the practical discretized algorithm. Appendix A.6 and A.7 presents details on the condition and examples of f2-bridge construction. Appendix shows additional experiment details and results.
actually use Markov model 1 to match all
A THEORETICAL ANALYSIS ON BRIDGES
A.1 DERIVATION THE MAIN EQUATION (13)
[Proof of Equation (13) Denote by Q = Q( = r). Note that
dQ
K || [PPP) = E zmQ"
log dlo (2)
dQ² log cTP (Z) + log
dQUr
EI-IT-Z2-0 22-2"
d (2)
E [KL((* || [PO]]
const,
where const denotes a constant that is independent 77 (Z t)dt + aZz, t),W,, and pe follows dZt s (Z,, t)dt + (Ze, t)dW, By Girsanov theorem (e.g., Lejay, 2018),
Recall that Q follows dz,
[ (1,)( 1 (20,0 11 dt
KC 1| = KC Po) + =B
loo (Zo)
+
2
2
1
1/'
-
(|,0(Z,, of (2000)) (12 const.
Hence
log (Z) + ///² [|,"(Z,,t) 11" (Z100.0) [oooa)=))]l t) dt
T
L(0) = E 2-00
+ const
2
/'
T
= Ezzzn-
loo (Z)) + 2 2 ||s) 17 2 (2 1))1 dt
+ const.
A.2 DERIVATION OF THE DRIFT T OF QT
Lemma A.1. Let Q is the law of dz; 1/" (Z l)dt + oZ7 (Z), l)dW, Zo ~ -
and Q = Q (dx) for a distribution II on Rdd Then 8T" is the law of
d7, n1" (7 t) + oZ,, t)dW, Zo D!"
where (Fu.),) = ZZ
z- (n) (.... Z/o.1 = =/o. Q (dzo) = Er- (dzo))
[Proof] Q is the solution of the following optimization problem:
q" = arg min [xC(Q"" P) = Ez-H- ( []] + const
13

---

Published as a conference paper at ICLR 2023
By Girsanov's Theorem (e.g., Lejay, 2018), any stochastic process IP that has KC(@"* || P) too (and hence is equivalent to Q*") has form of dZt 17" (210.1, t)dt + ((Z,,t)dW, for some measurable function r7" and
Ez-HI- [KC(Q*) P)]
1 /" / oo(2n,t) (20o.).) (2 0)) /
E (CC || Po)] + EI Z~00
2 /
It is clear that to achieve the minimum, we need to take Po(.)) E (.) and 17 (=10.0).)) Br 2~Q In" (Z10,)) t) Z|o.1] = =io,s:], which yields the desirable form of Q""
A.3 pe YIELDS A MARKOVIZATION OF QII
As p6 is Markov by the model assumption, it not perfectly fit Q" which is non-Markov in general. This is substantial problem because Q"" can be non-Markov even if Q is Markov for all E Ω (see Section A.4). In fact, using Doob's le-transform method (Doob, 1984), Q"" can be shown to the law of a diffusion process
d2: TH (210,), l)dd a (Ze, ()dW,, r) (=10.4), = Ez (7 (2j0,0, () Z10,4| =0044]
where y7" is the expectation of of when x = Zr is drawn from Q conditioned on Z10.1]-
We resolve this by observing that it is not necessary to match the whole path measure (Po R Q"')
to match the terminal (Pq. Rs Q4 = IT*). It is enough for pe to be the best Markov approximation (a.k.a Markovization) of Q"" which matches all (hence terminal) fixed-time marginals with Q"":
Proj(Q" .M) = arg margmin (C IP), = the set of all Markov processes on [0, T..
PEM
Proposition A.2. The global optimum of ((0) in (11) and (13) is achieved by 0 if
00 (2, Rz-qu- 2r (7)0,); () 7 = 2] n (dzo) Q Ex-- [Q (dzo)) (14)
In this case, po Proj( .M) is the Markovization of Q with which it matches all time- marginals: pd- = for all time t [). In addition,
KC(II [1 < KC((P" || [|P)) KCCQ"" - [| - C()) -000))((00) (15)
Note that 96 is a conditional expectation of r7" n, 5 (2,t) Ez~gn= (1) (Z t) Z, 2). Theorem 1 of Peluchetti (2021) gives related result that the marginals of mixtures of Markov diffusion processes can be matched by another Markov diffusion process, but does not discuss the issue of Markovization nor connect to KI. divergence. Theorem of Song et al. (2021) is the special case of (15) when IT""" is Markov.
[Proof of Proposition A.2] It is the combined result of Lemma A.3 and Lemma A.4 below.
Lemma A.3. Let Q be a non-Markov diffusion process on [0, T) of form
dz, = (,) t)dt oZ,, t)WW, Zu Qo
and M arg min M KLQ || PP) be the Markovization of Q where M is the set of all Markov processes on [o. T). Then Q is the law of
M:
dZ, m( t)dt oZZ,, Zo Qo.
where
m(z,t) t) = Ez Ez (n( [o.)) t) Ze = 2].
In addition, we have Q+ M, for all time [0,
14

---

Published as a conference paper at ICLR 2023
[Proof] By Girsanov's Theorem (e.g., Lejay, 2018), any process that has KL(Q M) (and hence is equivalent to Q) has form of dZ, = m (0.00. t) + o oZe, t)dW,, where m is measurable function, Since M. Markov, we have mlZ00.) 1) = m m(z,,)) Then
too
///o 2
1 1
KC(QII - Po) EE
(n( m (z, 0))
It is clear that to achieve the minimum, we need to take Mo = Qo and m(z,t) t) Ez-alu(Z1o.0.)) Zz =|
To prove Q M, note that by the chain rule of KL divergence:
xC(Q IP) KCC(Qe PP) + Q (CC((()))((2222 Z.) P() Vt E [0, T).
As the second term P--| [2) is independent of the choice of the marginal IP at time E [0, 21. the optimum should be achieved by M- only if M, = Qr.
Lemma A.4. Let
Q
dz (7 ()dt + a ()d,),
1)WW,
Zo ~ Qo
M dZ, m( m(Z,, t) + oZ,, t)dW,,
Zo Qo. Zo ~ Pe
Ip" dz, = (Z,, t) + oZe, t)dWe,
where MI is the Markovization Q (see Lemma A.3). Then
KC PP) KC(Q || M) + KCL IPO)
Hence, assume there exists 0 such that 1p0 MI and write ((0) = KCC( P.)) We have
KC(Qr || 14) = KCMMY || p4)) z KLCM pPa) = [()) - -())).
[Proof] Note that K.C(M || IP))
= -KL(Ml 1P)) + 2 En ~M, 1 10(22 - m 13/1 di
m(,, {" EZInM [10 (l0(2,t)) - +>>1 dt
KCC(M 11 (P/) + J/
KCCQO || 11)
1
/-" EZIne
(T
m (2,, 1)]1]] dt
//Q = -M,, 1I
2
1 T
KCC(Qu || (P)) + Eznq
- ml m(Z,,0))1
2
KC 11 P/) 2 11s0 $150-ma -m12-
where we define Il Ezna | 5o [lo(zz,t) f(2,,
On the other hand,
1 2
XCC( || IP9) = KC(@o P!) + Ex~e
1o(2,.))- - ((200 011
2
KCCCQ
IP() + ||s² -1112.
KC(( || Ml) = Rznz
2 / [lo( [ ml,,,
0))3 -m)
||17
m 2.
15

---

Published as a conference paper at ICLR 2023
Using Lemma A.5 with a(z) = (((,,,))=)(()( and b(2jo,s) = (2((0)) t), we have the :/(2000):
following variinc decomposition:
|| s" 12,0 ||ss mlle. + 111 mll..
Hence, KC(Q 11 = KM PPn) + KC M.).
Finally, KC || Pf) & KL(M || Po) is the direct result of the following factorization of KI.
divergence:
K.C(M || po) KC 11 ER [KC(MT((1Z 11 =))]
Lemma A.5, Let (X, Y) be random variable and a(x)). b(xr, y) are square integral functions. Let m(x) = B(6(X, Y) X zz.. We have
[x] 1) ([]la(X) m(x) E1]b(X,)) - m(())12)
[Proof]
[ = - + x1)
(X]la(X) ml (X) 6(X, r)1 +2A,
where
A B[(a(X) m(X)) (m(x) b(X, Y)JI
= B[(a(X) - m(X)) ([((((X) - 6(X, X
B[(a(X) -m(X)) (m(X) - -m()) = 0.
A.4 MARKOV AND RECIPROCAL PROPERTIES OF Q"I
set Mixture of Bridges and Initialization It is immediate observation that the mixtures of a of bridges are also bridges: let Qz..A be a set of A-bridges indexed by a variable 2, then QA == ((d2)((d)) is an x-bridge for any distribution y on
special case is to take the mixture of the conditional bridges in (5) starting from different deter- ministic initialization, which shows that we can obtain a valid x-bridge by equipping the same drift in (5) with essentially any initialization. Hence, the choices of the drift force and initialization in Q can be completely decouple.
Proposition A.6. Let Q is a path measure and 9y the set of z for which (2)o.(()) = Q7-1Zz = x, Zo zn) exists. Then Q = - p(dza x) is an x-bridge, for any distribution μl on Ω x Ω.
[Proof of Proposition A.6] This is an obvious result. We have Q (ZT x) by the definition of conditioned processes. Hence (Zr = x) = F (Zr x)u(dzo x) = -s [((2 x) = 1.
Markoy and Reciprocal Properties of Q"' If QF is constructed as Q Q(-1Zr = x), it
easy to see that Q Q" (dz) is Markov iff Q is Markov.
Proposition A.7. Assume Q Q(- Zr x) and (2) everywhere. Then Q"' is Markev, Q is Markev.
aer 2z) exists and is positive
dn
[Proof of Proposition A.7] If th = Q Zy = z:), we have from the definition of IT:":
II' (Z) Q II (Zr) Q(2)m² (Zr),
16

---

Published as a conference paper at ICLR 2023
air" (Zr). Therefore, QT is obtained by multiplying positive factor x² (Zz) on d22 the terminal state Zr of Q. Hence Q" has the same Markov structure as that of Q.
where x =Zrr
If Q" is constructed from mixtures of bridges above, the resulting Q" is more complex. In fact, simply varying the initialization μs in Proposition (A.6) can change the Markov structure of Q"" Proposition A.8. Take Q2" to be the dynamics in (7) initialized from Zo (O, vo). Assume or > 0, Vt E [0, T Then Qh" is Markov only when = 0, or +00.
[Proof of Proposition A.8] When taking Q be the dynamics (7) initialized from Zo ~ p = NO, vo), we have Q = f (o(d2)) ) where a ②-- 7g 20: 7T x) with Q fol- lowing Brownian motion dZz = dW, Hence, we can write Q"" (dZ) - Q(dZ)r(Zo) Zr), where r(zo: 2T) duu@Il" for some f and which is not the case except the degenerated case (vo and eo +00 because Q0,1 is not factorized.
dQo.r (zo, 2T). From Léonard et al. (2014), Q"" is Markov iff r(z, 20) (2))
On the other hand, when O, we have that Q QQ-IZz- = =x) is the standard Brownian bridge and hence Q is Markov following Proposition A.7. When Up +00, as the case of SMLD, Q"" is the law of Z, Zr-1 with dZz dW, and Zo II", which is also Markov.
The right characterization of Q"I from Proposition (A.6) involves reciprocal processes (Léonard al., 2014). Definition A.9, A process Z with law Q on [0, is said to be reciporcal if it can be written into Q f
#0 u(d2o, d2r), where Q is a Markov process and Q @ 2g: Zi 21 and μ is probability measure on Ω x Ω.
Proposition A.10. Q"T is reciprocal iff Q J 1:00 u(deo x) for Markov Q and distribution
[Proof of Proposition A.10] Note that
n (-) - T(dx) (())))(())((((((((())) x(dr)a(dz) (x)(=m())
Hence if Q is Markov, Q" is reciprocal by Definition A.9.
On the other hand, if Q" is reciprocal, we have QT (.) (+)=1 M= ()) dr) for some Markov process MI and probability measure μ Ω x Ω. In this case, have Q+)() Q" (-1Z) x) f |M (-)u(dz) 2), assuming exits.
Intuitively, a reciprocal process can be viewed as connecting the head and tail of a Markov chain, yielding a single loop structure. A characteristic property is Q[[ E A Zjo.s]: Z(rrT) = ((1aa.) E A Z, Zt), where is any event that occur between time s and Solutions of the Schrodinger bridge problems are reciprocal processes (Léonard et al., 2014).
A.5 PRACTICAL ALGORITHM AND ERROR ANALYSIS
In practice, we need to introduce empirical and numerical approximations in both training and in- ference phases. Denote by = K+ a grid of time points with 0 = T1 < T2 ... < TK++ = T. During training, minimize an empirical and time dine-eisce surrogate of L(0) as follows
(00
1
n Σ E(0 2(0) (1))
E(0: (. - log (Zo) + 2K 200
(16)
17 (2.o..,)))1 where (0;; 2,t) = | (sss ((p.))))))( and ( { is drawn from Q" and ((1) can be either a deterministic uniform grid of T). i.c., (() = {i/K)K or drawn i.d. uniformly on (0, 7) (see e.g.,ong et al. (2020b); Ho al. (2020)). A subtle problem here is that the
17

---

Published as a conference paper at ICLR 2023
variance of (0;; Z,t) grows to infinite T. Hence, we should not include A Z,T) the end point 5 [K+1 = T into the sum in the loss {(8, 2,T) to avoid variance exploding.
In the sampling phase, the continuous-ting model Ie should be approximated numerically. A stan- dard approach is the Muilr-Maauyamm method, which simulates the trajectory on a time grid 7 by
20211 = Zrz + Exs (2rz, Tw) + VELo TR) Ek - Th+1 Thi Ex NO, Ia), (17)
The final output is Zr. The following result shows the KL divergence between 11 and the dis- tribution of Zr can be bounded by the sum of the step size and the expected optimality gap B[((0) - [()))] of the time-discretized loss in (16).
A.5.1 TIME- SIME-DISCRETIZATION ERROR ANALYSIS (PROPOSITION A.11)
Proposition A.11. Assume Ω = Rd and o(2,t) o(t) is state-independent. Take the uniform time grid uuiif == {ic] with step size c = K in the sampling step (17). Assume at) > c > O, Vi and (t) is piecewise constant w.r.t. time grid uumit, Let (0) = Ez~qar [e(0; Z, Z,zumit), }] Let phe be the distribution of the resulting sample Zr. Let 8" be optimal parameter satisfying (14), Assume Co = =supz,t (11=0 (2,)"((,,)) /(1 ||21)),, (z, Ega- [112o111) < too, and
||"0 (2,1) - (E,1)) T. (1== =²11² + lt 111) for V2, TRd and 1, 1' [0, T). Then
KC || [ - C. (0) L. (0+) OVV).
We provide the analysis and proof for Proposition A.11 in the following text.
Proposition A.12. Assume f2 = RRd and (2, = (t)) is state- vute-independen and a(t) > c > O.
Vt E [0, Take the uniform time grid uuiif == {ic l==o with step size = T/K in the sampling step (17), Let (0) = Ez-çur [he 2)] with
K
log L, Z,) = log ph Po +
Σ
o0% (s (Zo, - 27 (Z (.A)): +x))
2K
where e >> 0 is step size with T = Ke and ts = (k- - 1)c, and of == (t4+1 - tx)) -xx= S/a dt) Let p be the distribution of the sample ZT resulting from the following Euler method:
2 2n, + fesss27n (Zemn (x) + VeakEs.
where & ~ (O, Ia) is the standard Gaussian noise in Rdd Let 6" be an optimal parameter satisfy-
ing (14). Assume Co = supz,t (11** (2, (2, /(1 ||=113), ir(o2(z,()) Eeg- 111 +00,
and 8 satisfies
(z,t) (z, "6 (z (z/, $ L (11=- 2'11 + 1t- -l) for Vz, E Rdd and
2 E [0, Then we have
V KC(TTI || [1. (00))) O(Ve.
[Proof of Proposition A.11] This is the result of Lemma A.13 below by noting that the jor there equivalent to the Euler method above, and (0) ((( < (.) - (.- (because of
((4+11 - (4) fte 1t (1))))-1 S (4++1 - (4) f a
Lemma A.13. Let h be a step size and 6 = T/K for a positive integer K. For each t E (0),
denote by [t]e = max((1 (ke: k E N) n [0, t), Assume
dz, n (Z...). t)dt t t)dW, Zo Qo
po
dz, 56 (Z,, t) + o t)d,, Zo ~ Qo
p
dz, = a ((z,, t)dt + (Z,, t)dW,,
Zn ~ Pd
ee
dz, 3 (Z t)dt + o (Z,, f)dW, Zo pP
18

---

Published as a conference paper at ICLR 2023
where Ipo is the Markovianization of Q", and Ip is discretized version P". Define
(0) = B log log + / (Zz ( () (2 [t]e) - 2r (1, [tte)l dt
T
Assume the conditions of Lemma A.17 holds for 1p"" and o(z,t) 2 >> for all a,t, and S satisfies (2,t)
(2,t) 80 (z',1))l2 - L (1I= =112 + 11-1% (1l) for Vz, E R2 and t, e [0,
Then
V KCC(P II P0) S v (2( (. + +CVE
where C' is a constant that is independent of
[Proof] Define I1 = Ex-elf II((2, [)] for convenient notation. Let s2(2)
5 (Z [t]e). and 7h R (21) Lt].).
KCL(P0" 21
KC((F (P)) +
1
s"
2
S KCC(P8 (Pg + 2
1
(1+ w)
b
9'
800 - 6 + (1 1/w)
po
pe
+ (1+ + (1+1/w)J1
where w > 0 is any positive number and
I 1
KC(P8 1
+
8
1 w
KCC(F
11
I+
111
S KCC(F)))
+
1
8-
2
Qm 0
S KCC(PE
|| [1 +
|10
11
Zr
2
0'
2r
I/Lemma A.5
2
cu
= (.( 10))),
and
00
00'
2
1
10
L
Epp-
(Z,,t) (1Zr - Z1.,112 -5(1-
(t [t]e) dt
2
L
1. (12: -111.)² + Ltle))dt
T
Epo
26
L
+ 1) 1" (1 - ((Je)dt //Lemma A.17
(Cpo-
20
L (Cpu- + 1) Tc.
//Lemma A.15,
2c
where Opa- a constant depending on pp" that comes from Lemma A.17. Hence
KC((P"'
|| [P0)
inf (1 w)t1 (1 + 1/w)12 w20
(V I1 + VT2²
1 L - (.r)) (2.)))) + 2V 2
(Cre- + Te
This completes the proof.
19

---

Published as a conference paper at ICLR 2023
Lemma A.14. For any a, b R", and 2 0,
||a bll2 = (1 + walll + (1+ 1/w) |06|
[Proof]
(1 + w) ||al2 - (1+ + 1/(1 1011 2 |a112 + 1661 + Ta = ||a + 6
Lemma A.15. Assume T 2 0, and T/c E N. We have
L (t (t-lt]j (t-Itle)at=
[t]e)dt= Tc
[Proof]
R- 1
I (t dt] =
Σ
(hk + hk)dæ
K-1
Σ
adx
k=0
K2//2
Te/2.
Lemma A.16 (Grönwall's ' inequality). Let I denote an interval of the real line of the form [a, oo) or (a, bj or b) with < b. Let az 3 and be real-valued functions defined T. Assume that 3 and u are continuous and that the negative part of a is integrable on every closed and bounded subinterval of I.
(a) If B is non-negative and if u satisfies the integral inequality
u(() S a(1) + [[ (())
VIE
which is true if
w'(1) +
then
u(t) < a(t)) [ ((s))(()) exp ([[((r)) ds,
(())
TEl.
(b) If. in addition, the function o is non-decreasing, then
m(t) S al)) (f B(s)
TET.
Lemma A.17. Consider
dX, =x,=b(Z,, 1)dl + (Zi, Idd,,
Xo 0, [0,T].
Assume there exists a finite constant Co, such that
[Ib(x, t)1 < Co(1 + ||~]()) Ve E Rd, te [0, tr(pa (x, t)) < Co.
Vo e R [0,T].
and El|lZoll < Co.
Then for any T, have
E|IlZ, - 1 & Kc.rr(t ()) s),
where KCo. finite constant that depends Co and T.
20

---

Published as a conference paper at ICLR 2023
[Proof] Let supx,, tr(oro tI). We have by Ito Lemma,
112 Zall = E [2(2, - () + +
dt
E
[2(Z; - bZ,) +1
E
12. Zall2 [16(2, e)11 + d)
< E
1Z Z.ll2 Co(1 + | [7]
< (1+ [12 2u12]
+П+ Co(1 + + 12.1 )
Using Gronwall's inequality,
IB
11 - _all²] - (t - +) 2. exp ((t - +Co))
Taking s = yields that
E 112 2o123] s 1(1 Co(1 + 2B||| z exp (41 + 2C)))
Hence
E 2 - 2E 12 Zo11 + 2E |
$ 21(1 + Co + 23 Z (2) exp (t(1++ 2E 1
< 4T + exp( (06)) 2C%.
Therefore,
E 11z 20
$ (t s)(1 + Co(1 22(1Z, exp ((t ((t- s)(1 + 2C,))
< C(t s),
where
C C2 + 40 SCoT + (%) exp( 2C))) exp (T(1 + 2C))).
A.5.2 STATISTICAL ERROR ANALYSIS (PROPOSITION A.18)
To provide a simple analysis of the statistical error, we assume that é, = arg ming ((0) is an asymptotically normal M-estimator of 6* following classical asymptotic statistics (Van der Vaart, 2000), with which we can estimate the rate of the excess risk ((,)) - C. and hence the KL divergence.
Proposition A.18. Assume the conditions in Proposition (A.11). Assume O,. = arg ming (.) with (.) Ei=1 E(0; 7 muilt) )/o, z(0) Qur". Take Q" to be the standard Brown- T-t dt + dW, with Zo NOO, vo) and Up > O. Assume vn((, 0²) 4 N(O,E.) as n + to0, where E, is the asymptotic covariance matrix of the M estimator On Assume L.(0) is second order continuously differentiable and strongly vex at 0*. Assume 11 has a finite covariance and admits density function & that satisfies ||Vos** (Zi, t)]l (1 |/V log 7 (Zrr)]1 tr( log n (Zr))) < +00. We have
ian bridge dz, z-2;
SUPreJo.T] BEgar
E XCCIII || (Pf = =0(1 log(1/e) +
+ V²).
(18)
21

---

Published as a conference paper at ICLR 2023
The expectation in Eq. (18) is w.r.t. the randomness of 0n. The (1/c) factor shows up the of a harmonic series as the variance of (6;; Z,t) grows with ( - t)) when t T. Taking
é = 1/n yields KCL(II* || ( Olog n/n). If we want to achieve KC || ( - O()).
is sufficient to take K = TTee = ((1/n) steps and = 0(log(1/n)/v) data points.
[Proof of Proposition A.18] Let
1 Σ ((0; z(),,
0 arg min (0) := Bz- [e(0; Z)
0, - arg min C.(
0
M= is drawn ii.d. from Q" We assume that d, is an asymptotically normal M- estimator, in which case we have
where (
Vn(O,, 0*) ~,,(0, E.).
where
= = V.H,'
H, = Ez-on (Z)
V, = 2/ 11
and
1 212 Vm H. - -6.) x tr(H,
nB((C((0.) - - 2(0))) =
2
where f x g denotes that - = o(1). We now need bound tr Vr(H, Combining the results in Lemma A. and Lemma A.23, we have when 4 = (k - 1)e and T = Ke,
1
tr( 0
1+
O(1 + log(/e)))
K
T
tx
k=
Hence,
Ely KCC(TT
|| (phno")
= 0
Ely c(O.) - [(0*) Ve
=0 EL(C(O.) C(0+)] + Ve
= 0 log(L/E+1) ve)
Lemma A.19. Assume the conditions in Proposition A.18. Define
1o Enugn || log of (2o) (2.)
1s = Enngn F100000 (Zr, te)l (T (x) 2w))
for vk 1,... K. Then
1/2
tr(111V..112 <
1
Σ
1x
Amin (H,)
K
[Proof] From Lemma A.21, tr(H, VV.) 1 (Amin ((x.)))(r(((...)) tr(V.).
Hence we just need to bound
22

---

Published as a conference paper at ICLR 2023
tr(V.)1/2= = uvV.))/2=Ez =Ezweu
|Voe(( 2)13
1/2
$ &Rz-g
|1Voe(00 _))12]
1/2
+
K
Z--Qtt"
V Vos (Ze (6 (2)n)4)) 1/2 (210,t)) 4 ))
1 27
K
k=1
Vol(o _)1
1/2
| VZs (Zoz txa) (60 (Zee (Z 17 (2)o.t) tx)))
[[]
1/2) 1/2
Ez-anr
+ z~ z~-Q""
K
k=1
Ez
|Voo(00 2)
1/2
+
B Bn-
||VoS (2re, 4x) 1n) (coorr (1)2 (20,es))))) Zon))
1/2
K
K
-10/
1/2
1
1/2
+
K
k
$
1/2
k
Lemma A.20. Assume the results in Lemma A. and Lemmn A.23 hold. Assume
Vos" (Ze, tx) 1| (1 log x- (Zx) + tr(V2 x5 (271))
max Ez-II-
(
<+00,
KEI...,
Then for k = I...., K, we have IN- = - (- +1).
[Proof] It is a direction application of (20).
Lemma A.21. Let and B be two d x positive semi-definite matrices. Then tr(AB) s Amax (max(A))i (A)
[Proof] Write A into A Ei= Araiy where x and u, is the i-th eigenvalue and eigenvectors of A, respectively. Then
d tr(AB) = tr Auu Bus)= S Amax(A)tr Σ u Bu,) = Amax (B)
Controlling the Conditional Variance of the Regression Problem Assume Q is the standard Brownian bridge:
O+ az x- 21-
--t dt + +dW, Zo ~ vO),
(19)
In this case, the (ideal) loss function is
logrū(Zo) /" 1 ().
where X - Zo 1-t t
(()) = -xxiIl Z~ox
The second part of the loss is least square regression for predicting Y, = (Z, with 8 (Ze, t)- The conditioned variance cov(Y; Z.) is an important factor that influences the error the regres- sion problem. We now show that tr(cov(Y,, Zz)) O(1/T - t) which means that it explodes to infinity when é T.
First, note that tr(coo(Yy) | Z,)) (ύ- (r--ratrccov( tr(cov(X Zt)). Using the estimate in Lemma A.23, have
tr(cov(V, Z)) o
"5" (x)) 7g )
T-1 + R
V I "" (X)11 + tr (V2 log
(20)
23

---

Published as a conference paper at ICLR 2023
Lemma A.22. For the standard Brownian bridge in (19), we have
Li N (
t(T t)
+ (T - t)2
T 00
T
[Proof] Let 2, be the same process that is initialized from Zo 20. We have from the textbook result regarding Brownian bridge that we can write Z, tT+ 1) + [(T Ee
where & is some standard Gaussian random variable. The result follows directly as 7 2, with Zo (O,
Lemma A.23. Let I² be the density function IT on RRd whose covariance matrix exists. When X IT and 7. Qx from (19) with un 0. Then the density function p=(x)z) of X 2t satisfies
[ 1
pe(x)z) x T (x)
(21)
2 T(T-t) + 00 (T-1)
In addition, there exists positive constants e < too and T E (0, such that
tr(cov, P. (x|=)) x wpd + w V log (x) + ir (V2 log " (x)) {
when 7 SIST
when 0 05t2m
where u, T(T-1) + un (T-1)² So poov (xl22) is bounded and decay to with rate O as 1 T.
[Proof] We know that X II and 2 N(t/TXX wt). Hence, (21) is direct result Bayes rule. Then Lemma A.25 gives
tr(cov,, (xl=)) = wid + wf | log x- (x) + ir (V² log ग (x))
On the other hand,
T
p=(x12) x n (x) exp(
|
twi z x),
20c
Hence, Pt (x|z) converges n" (" L 0. as result, tr(cov,, or (x(2)) + tr(cov, x' (x)) < t00 Therefore, for any >> 0, there exists to > 0, such that tr(cov,, p. (z|²)) & tr(cov, (x)) c when 0 t to.
When
have 1/w, 0 and T (/(ww/
Remark A.24. We need have vo > O to ensure that T/(tw;) 0 in the proof of Lemma A.23. This purely a technical reason, for yielding a finite bound of the conditioned variance when t is close O. We can establish the same result when vo by adding the assumption that
max 1..........KK Ez-qu- [|| tx)l22 tr(covi,,,, (Zr)) < +o,, where II; is the distribution with density n (x)) π (I:) exp(= x/T).
Lemma A.25. Let p(x) (xx) exp (-ale-))) be a positive probability density function on IRd,
where a > 0, b E R and log is continuously second order differentiable. Then
(x)c < 1 = a a (I
log ( tr( log (g))()))))
[Proof] Let us focus on the case when first. Stein's identity says that
Ep [VV (og=(x) az) ((x) + (xx)] 0,
for general continuously differentiable function when the integrals above are finite.
24

---

Published as a conference paper at ICLR 2023
Taking & yields that
Ep [VV log (x) -z)) -x)" d) =0,
which gives
|p[||=|| = a ( x]]+ dd)
On the other hand, taking (bx) v log (x) yields
Ep [V az) log + tr (r 0,
which gives
Ep V logTt) = a =a)
(B (o
This gives
Ep1l| = da + a- V log tr(V"log
(-3 |===1")
For + O, define p(x)) (xr + b) exp
which is the distribution of x = x b when
x ~ p. Then applying the result above to p yields
tr(cov,(z)) tr(covp(I))
S a - d + a 2 Beup
| log a (x b)ll + tr (v2 log x (o + b))
a a + a - Brup
V log (x) + (V (z)))((())))))))))))))))))) (s))
A.6 CONDITION FOR 2-BRIDGES
We provide the proof for Proposition 2.3.
[Proof of Proposition 2.3] By the formula of KL divergence between diffusion processes, have
KC(QO ||P*) KC PP)) + Ez-ca [ (1,
< <xx.
This means that Q and p6 absolutely continuous to each other, and hence have the same support. Therefore, @Zr E Ω!) = implies that (Zz E .)) = 1.
A.7 EXAMPLES OF Q-BRIDGES
If I product space, the integration can be factorized into one-dimensional integrals. Specifically, assume Ω = 1 x ... Id. then
(2, [n (z, 0)
where 17'h is the drift fore of the I.-bridge, and is the i-th element of [2,]. Therefore, it is sufficient focus on ID case below.
Consider the bridge process constructed from the Brownian motion in (9). If Ω is discrete set, say (er ..., ...,,c,, ). we have
K ((e, 2,
(2, = o² EK w(ek, 2,t)
Cb 2
BT - 3r
kmml
00 V log
w(ex, 2,t),
1=1
25

---

Published as a conference paper at ICLR 2023
vurtoriax fahlet
adacation
martia-statte
oecopation
mutttionapi
rare
ert capital-pinn eapitaliios: hours nuun-ppr-redd natree-ornntyy lncame
Sethamp-nahiiee
Profopedisly
Sif-em--nat-ic 313479
Some Nevermamiid
Machne-sp-inset
Hustand
United >50K
81
Without pay 106224
9th
Mari ed die sposse
Adm clorical
husband Block
Malc
1910
66
24
United States <>50K
41
Prinade
285037
50h
Divrradd
Astreleeccl
huaband White
Male
3754
Poland ces
22
Prtvate
21419
Sachelor
Widowed
mare-manoperal
Cam-chil White Pemale
208
United-tanes c:10K
Figure 5: Generated tabular data from Mixed-Bridge.
where
w(ek; 2, exp (-
||2 Ek 11 2( - 3B)
If Ω [aa bl, we have
T = of
1
['
h
w(e, 2,t) 2(t e- de
Sr u(e,, 2,t)
3T 3r
= - log
w(c,2,t)de
= o 2 log
F1 11-2-__ a
))
--F( z-b
VBr - Bi /Br Be
where the standard Gaussian CDF.
B ADDITIONAL MATERIALS OF THE EXPERIMENTS
In our experiments, T and e = T/K = 1/K. Moreover, we take the time grid by randomly sampling from {i/K] K-1 for the training objective Eq. (13). For evaluation, we calculate the standard evidence lower bound (ELBO) by viewing the resulting time-discretized model as latent variable model:
Pi(Zz)
Pheealta Ita (Zez. Z(ee K
Ex-n. log logg < Ez-g" log
log
go (0)
To ltv (Zex Zean)
where 4 = (k-1)e, and jo is the density function the time-discretized version of Ip and g is the density function of Q. We adopt Monte-Carlo sampling estimate the log-likelihood. As in (Song al., 2020b), we repeat times the test set for the estimation. For categorical/inteerrggii gen- eration, the likelihood of the last step should take the rounding into account: in practice, have Z. rounding(2,, (2xx + es (Zex: (x) Feo Zz,, Ex, ②)) where rounding(2, .2) denotes find- ing the nearest element of x Ω, and hence the likelihood Prie of the last step should incorporate the rounding operator part of the model.
B.1 GENERATING MIXED-TYPE TABULAR DATA
In this experiment, the metrics are measured by the implementation from Symthetic Data Vault (SDV) (Patki al., 2016). For baseline methods, adopt their open-sourced official implementa- tion! For the machine learning models adopted for evaluation, logistic regerssion, AdaBoost and their default configuration in SDV. For the results in Table 1, repeat the
MLP. we directly periments with different random seeds and report their standard deviation. We provide additional generated samples from Mixed-Bridge in Figure 5.
hhttps://gi thub. com/ adv-dew/CTGa
26

---

Published as a conference paper at ICLR 2023
Figure 6: Visualization of the noïse schedule of Noise decay A, Noise decay B and Noise decay C.
B.2 GENERATING INTEGER VALUED POINT CLOUDS
In this experiment, we need to process point cloud data integer grid. To prepare the data, firstly sample 2048 points from the ground truth mesh. Then, we normalize all the point clouds to unit bounding box. After this, simply project the points onto grid point by rounding the coordinate to integer. The metrics in the main text, MMD, COV and I-NNA are computed with respect to the post-processed integer-valued training point clouds. For the results in Table 2, repeat the experiments for 3 times and report the mean of the experiments.
B.3 GENERATING SEMANTIC SEGMENTATION MAPS ON CITYSCAPES
In this experiment, we set (Noise Decay A): of exp(-3))) (Noise Decay B): of = 3(1 - t); (Noise Decay C) of = 3 3 exxp(33(1 - -)). We visualize the noise schedule in Figure 6. Note that, except for Constant Noise, all the other three processes gradually decrease the magnitude of the noise + 1. For fair comparison, we use the same neural network in Hoogeboom et al. (2021). The network is optimized with Adam optimizer with learning rate of 0.0002. The model is trained for 500 epochs. The CityScapes dataset (Cordts et al., 2016) contains photos captured by the cameras on the driving cars. A wixel-wise semantic segmentation map is labeled for each photo. As in (Hoogeboom et al., 2021), rescale the segmentation maps from cityscapes to 32 64 images using nearest neighbour interpolation. Our training set and test set is exactly the same as that of (Hoogeboom al., 2021) for fair comparison. For the results in Table 3,we repeat the experiments for 3 times and report the mean of the experiments. We provide more samples in Figure 9.
B.4 DISCRETE CIFAR1O GENERATION
The model is trained using the same training strategy as DDPM (Ho et al., 2020) with the code base provided in Song al. (2020b). Specifically, the neural network is the same U-Net structure as the implementation in Song et al. (2020b). The optimizer is Adam with a learning rate of 0.0002. According to common practice (Song& & Ermon, 2020; Song et al., 2020b), the training is smoothed by exponential moving average (EMA) with a factor of 0.999. We use K = 1000 and dt 0.001 for discretizing the SDE. To account for the discretization error, after the final step, we apply rounding to the generated images to get real integer-valued images. We compare the value distribution of the generated images in Figure
27

---

Published as a conference paper at ICLR 2023
1
0
0.0
0.5 t
1.0
Figure 7:
Diffussio process of pixel 8-dimensional vector) in CityScapes. As t 1, of the dimensions reaches O, while the dimensions reaches 1, turning the vector one-hot vector.
126
127
126
129
130
126
127
128
129
130
(a) Consin--onssssooss
(b) Bridge-Integer
Figure Final distribution the generated images with Bridge Bridge-Continnous Continuuun Bridge-Integer (before rounding) on CIFAR10. We only show the values in [125.5, 130.5] for visual clarity. Integer- Bridge generates discrete values.
28

---

Published as a conference paper at ICLR 2023
(a) Real Data
(b) Constant Noise
(c) Noise Decay A
(d) Noise Decay B
(e) Noise Decay C
Figure 9: Additional samples from real data, Constant Noise, Noise decay A, Noise decay and Noise decay
C.
29


Reviews:
[{"review_id": "HQ8nzFFosb7", "reviewer": "Reviewer_bJKz", "summary": "", "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": "", "summary_of_the_paper": "This paper proposes a method to learn diffusion models which is forced to converge to a specified set of points. It does this by using Doob's h-transform, a classical tool in stochastic calculus. Experimental results show a general improvement when modeling data that has some sort of discrete structure (e.g. image pixel values).", "summary_of_the_review": "Overall, I lean to accept the paper as the method is relatively nice and the results are very convincing. Importantly, I found there to be some problems in the methodological setup, but this is to be expected due to the nature of the problem (continuous to discrete). My rating is conditioned on the authors responding to the comments above and updating the manuscript to reflect the limitations.", "strength_and_weaknesses": "Strengths\n-----------\n* The method is theoretically-principled (building off of known results in the stoch analysis literature). In addition, it is reasonably clean (for example avoiding simulating an SDE as is usual for diffusion models).\n* The empirical results are very convincing. In particular, there is extensive evaluation on many different datasets, including some applications of discrete diffusion which are novel.\n* The idea seems impactful. In particular, there seems to be a lot of work on learning diffusion models which generate discrete structured data.\n\nWeaknesses\n---------------\n* The proposed claim about diffusion processes that end on general compact spaces is not really supported. In particular, note that the proposed methodology would require an intractable integral over the whole domain. This is supported by the fact that experiments don't showcase this, even though such examples exist in the literature [1]. I would remove this claim especially in light of existing literature for diffusion models on manifolds.\n* There seems to be several technical limitations to the proposed approach:\n\n1) Since the gradient/eta term goes to infinity for $x \\notin \\Omega$,  there should be some numerical difficulties when training and sampling. In particular, since $f$ is constructed to be bounded, any small amount of numerical error should cause significant problems. Furthermore, for sampling, I imagine that really small step size must be used (or it should be annealed as $t \\to T$).\n\n2) Prop 2.3 is presented as a simple requirement that can be easily overcome (by making the neural network bounded). However, this only works when the activations are bounded (assuming an MLP like structure) and are not something like ReLU. Furthermore, while it is true that we still retain universal approximation, how does this work with the numerical blowup of the gradient/eta term (as described in 1)? In particular, does this significantly hamper training?\n\n3) The evaluation of the gradient/eta term requires a discrete summation over all points in the domain. This seems like it would very computational expensive (akin to the computational blowup of Gaussian Mixture Models). For experiments in this paper, this amounts to evaluating a 256^{32 x 32 x 3} GMM (at least for CIFAR). I don't believe that the paper touches upon this, and I also don't think naive techniques like MC sampling would work during training/sampling (due to pole-nature of the sampled points).\n\n4) The paper does not present a way to calculate exact log-likelihoods. This may be difficult since we are projecting from a continuous space to a discrete space, but this still represents a significant limitation when compared to vanilla SDE-diffusion models which normally have this.\n\n* The (Key et al. 2022) paper that is mentioned seems very similar, and the paper should devote more time and space to explain the differences. (It is technically concurrent work since it appeared in arxiv less than a month before ICLR submissions).\n* Some of the metrics used for evaluating the datasets are quite weak. For example, the experiments in 4.1 train another ML model to fit the generated datapoints, which seems like a very difficult comparison to make since there are so many hyperparameters to tune.\n\n[1] https://arxiv.org/abs/2202.02763", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "9IeM_AanKG", "reviewer": "Reviewer_EaLU", "summary": "", "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": "", "summary_of_the_paper": "The authors propose a method of learning diffusion models on constrained domains. Specifically, the propose to add a term composed of the gradient of a gaussian mixture model with bandwidth $T-t$ to encourage diffusion towards a domain embedded in Euclidean space. This is tested in a variety of domains against relevant models. ", "summary_of_the_review": "I found this paper an enjoyable read. I would be curious as to the extra time it takes to evaluate for some of the larger categorical spaces. I would also suggest more specific parameter specifications, and more discussion of the limitations of the h-transform in terms of efficiency. ", "strength_and_weaknesses": "Strengths:\n\n- A conceptually simple framework for enforcing discrete generation that is theoretically sound and works well experimentally\n- Comprehensive experiments on a number of domains including new domains, tabular data with both discrete and continuous data, and standard domains (discrete Cityscapes and CIFAR10).\n\nWeaknesses:\n\n- The GMM framework means that the current implementation is efficiently computable on discrete domains or domains that can be efficiently integrated over.\n- No mention of compute times. From my understanding generating CIFAR10 images requires a distance computation to ~2^17 points each of the 1000 diffusion steps? This seems like it would be quite slow for large domains.\n- For the Cityscapes and cifar10 comparisons, the parameters used are slightly different than those used in previous work. While these discrepancies are small, the performance improvements are also rather small. Since the numbers are taken from the prior papers, it would be useful to use the same setup as the prior papers for direct comparison of the methods.\n- The limitations of this work are not discussed in the limitations section.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "3hNauYyjBs", "reviewer": "Reviewer_pq3t", "summary": "", "questions": "", "limitations": "", "rating": 10, "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": "", "summary_of_the_paper": "This paper proposes a new technique for learning generative diffusion-based models of data in constrained (discrete / bounded / mixed) domains. Interestingly, the diffusion process occurs in continuous time and space, but is \"pinned\" to always generate outputs in a potentially discrete constrained set; this pinning is accomplished by incorporating Doob's h-transform into the learned process.\n\nThe paper starts with a clearly written introduction to x-bridges (constrained to points), the h-transform, and $\\Omega$-bridges (constrained to sets), and then introduces a parameterized family of such bridges, which can be used as a generative model. Next, it describes an approach for learning these bridges by minimizing the KL divergence between the parameterized family and a ground-truth mixture of point bridges, which turns out to be a straightforward score-matching objective.\n\nFinally, the authors present results on a wide variety of constrained domains introduced by previous works, including mixed-categorical-continuous tabular data, point clouds, categorical segmentation maps, and discretized images. Across all domains and metrics, their approach achieves improved results.", "summary_of_the_review": "Overall this is a good paper, which clearly describes relevant background, introduces a novel and elegant technique, and shows that it does very well across a large number of tasks of interest to the community. As such, I think this paper should be accepted. I think this paper could be even stronger with a discussion of the conditions under which minimizing the proposed loss will guarantee that the learned model faithfully represents the data distribution given enough capacity (or, even better, a proof that this is always the case).\n\n*Updated review:* The authors have added a significantly expanded derivation in the appendix, which does indeed show that minimizing the proposed objective under the proposed parameterization exactly recovers the data distribution (and is furthermore a Markovization of the constrained diffusion process). Since this method appears to be both theoretically principled and empirically very strong, I have increased my score from 8 to 10. (However, most of the theoretical justification is in the appendix, and might be easy for readers to miss; I hope the authors can emphasize their theoretical contributions more in the final revision if this work is accepted.)", "strength_and_weaknesses": "Strengths:\n\n- The paper is very clearly written, and provides sufficient background to understand the approach for readers who are unfamiliar with bridge processes and Doob's h-transform.\n- The technique itself is very elegant and principled, and appears to be both simple to implement and widely applicable.\n- The authors provide both a general, high-level framework (for arbitrary noise processes and constraint sets) and a concrete realization of it (using simple Brownian motion and constraints consisting of discrete sets, bounded intervals, and product spaces) which could be readily implemented for new tasks.\n- Empirically, the results are very strong across a wide range of existing tasks, outperforming many individual models designed for specific tasks.\n\nWeaknesses:\n\n- **(addressed by new revision)** It's not obvious to me that the learned process $\\mathbb{P}^{\\theta}$ can exactly capture the fixed posterior $\\mathbb{Q}^{\\Pi^*}$ used for training, and thus that minimizing the loss in (13) is sufficient in theory to obtain a correct terminal distribution. (But perhaps I am not understanding something. Empirically, at least, it seems to be able to do this in practice.)\n- The authors could discuss connections to prior work in a bit more depth.\n- Since the trained model and inference process use discrete step sizes in practice, the learned model doesn't always generate values within the constraint set, so some form of rounding is still necessary. (But hopefully the amount of rounding required is quite small!)", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "-usRaH4jts", "reviewer": "Reviewer_WZ2o", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "", "summary_of_the_paper": "The authors proposed to leverage Doob's h-transform to learn diffusion models within a constraint domain, including product spaces of any type, such as discrete, categorical, and their mix. Various experiments are conducted to demonstrate the interesting applications of such an algorithm.", "summary_of_the_review": "I like the idea of Doob's h transform in studying diffusion models in a constrained domain, however, a few fundamental claims seem to be quite rushed and not fully verified. There are quite a few weird mathematical notations with kind of ambitious claims. I would suggest the authors elaborate more on the methodology part and why Doob's h transform extends from point to distribution.\n\n\n========= post-review ==============\n\nThe variational gap should not be a severe issue due to the novelty in the methodologies to extend score matching with other (e.g. discrete) state spaces. ", "strength_and_weaknesses": "**Pros:**\n\n1. The use of Doob's h-transform to steer the particles toward the desired point is an interesting idea and seems promising.\n\n\n**Cons:**\n\nSeveral claims may need to be justified:\n\n1. My **biggest concern** is if Doob's h transform can be extended to model the data distribution: since Doob's h transform is often used to steer the solution to some point at the terminal time, while the authors seem to naturally extend that to distributions. I suspect that this may **not be a trivial extension**. Any reference supporting similar ideas would be greatly appreciated.\n\nMinor: \n\n1. The use of the path measure $\\mathbb{Q}$ is slightly confusing. $d\\mathbb{Q}_t/dx$ is often referred to as a distribution instead of $\\mathbb{Q}_t$.\n\n2. I don't understand what $Z_T\\in dx$ means, it seems weird. \n\nOther minor issues:\n3. The figures and table in the appendix should use a better format. (larger font / y axis)", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%