Diffusion Models as Plug-and-Play Priors
Authors: Alexandros Graikos
Nikolay Malkin
Nebojsa Jojic
Dimitris Samaras
Venue: NeurIPS 2022 Accept (2022)
Keywords: diffusion models
conditional generation
image segmentation

Abstract: We consider the problem of inferring high-dimensional data $x$ in a model that consists of a prior $p(x)$ and an auxiliary differentiable constraint $c(x,y)$ on $x$ given some additional information $y$. In this paper, the prior is an independently trained denoising diffusion generative model. The auxiliary constraint is expected to have a differentiable form, but can come from diverse sources. The possibility of such inference turns diffusion models into plug-and-play modules, thereby allowing a range of potential applications in adapting models to new domains and tasks, such as conditional generation or image segmentation. The structure of diffusion models allows us to perform approximate inference by iterating differentiation through the fixed denoising network enriched with different amounts of noise at each step. Considering many noised versions of $x$ in evaluation of its fitness is a novel search mechanism that may lead to new algorithms for solving combinatorial optimization problems. The code is available at https://github.com/AlexGraikos/diffusion_priors.

Diffusion models as plug-and-play priors
Alexandros Graikos Stony Brook University
Nikolay Malkin
Mila, Université Montréal
Stony Brook, NY agraikoe@ee..tooybbooo.cc edu
Montréal, QC, Canada
nikolay malkin@millll la. quebec
Nebojsa Jojic Microsoft Research Redmond, WA joj mojicmmicrosot.ccom
Dimitris Samaras
Stony Brook University
Stony Brook, NY samaras@cs www.::/ssssssooooooooooo
Abstract
We consider the problem of inferring high-dimensional data in a model that consists of a prior p(x) and an auxiliary differentiable constraint c(x,y) on x given some additional information y. In this paper, the prior is an indepen- dently trained denoising diffusion generative model. The auxiliary constraint is expected have a differentiable form, but can come from diverse sources. The possibility of such inference turns diffusion models into plug-and-plan mod- ules, thereby allowing a range of potential applications in adapting models new domains and tasks, such as conditional generation or image segmentation. The structure of diffusion models allows us to perform approximate inference by iterating differentiation through the fixed denoising network enriched with different amounts of noise at each step. Considering many noised versions x in evaluation of its fitness is a novel search mechanism that may lead to new algorithms for solving combinatorial optimization problems. The code available at phttts::/ggtthii //github.. http//uubooooaaaaeooaaaaaooaeoee Awwxtraikos/ wwtp://ooooooffooooooooooooooooo
1
Introduction
Deep generative models, such as denoising diffusion probabilistic models [DDPMs; 39 capture the details of very complex distributions over high-dimensional continuous data p(x)
13 can
30 7
1.38 4 15 The immense effective depth of DDPMs, sometimes with thousands of deep network evaluations in the generation process, an apparent limitation on their use off-thh-shelff modules in hierarchical generative models, where models can be mixed and one model may serve prior for another conditional model. In this paper, we show that DDPMs trained on image data can be directly used as priors in systems that involve other differentiable constraints.
In our main problem setting, assume that we have a prior p(x) over nigh-dimensiooal data x and we wish to perform inference in model that involves this prior and constraint c(x,y) on given some additional information y. That is, we want find an approximation
the posterior distribution p(xly) x p(x)c(x, y). y). In this paper, p(x Xg. h {x7, .... X1 is provided in the form of an independently trained DDPM over XT, Xp 2.2
making the DDPM 'plug-and-pla prior.
Although the recent community interest in DDPMs has spurred progress in training algorithms and fast generation schedules [30] 37 45), the possibility of their use as plug-and-play modules has been explored. Furthermore, as opposed to existing work on plug-and-play models (starting from 29). the algorithms we propose do not require additional training finetuning of model components or inference networks.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

One obvious application of plug-and und-play priors is conditional image generation ($3.1 $3.2) For example, a denoising diffusion model trained on MNIST digit images might define p(x), while the constraint c(x, y) may be be the probability of digit class y under an off-the-shelf classifier. However, changing the semantics of x, we can also use such models for inference tasks where neural networks struggle with domain adaptation, such as image segmentation: c(x,y) constrains the segmentation to match an appearance or a weak labeling y ($4). Finally, we describe a path towards using DDPM priors to solve continuous relaxations of combinatorial search problems by treating y latent variable with combinatorial structure that is deterministically encoded x ($5).
1.1 Related work
Conditioning DDPMs DDPMs have previously been used for conditional generation and image
segmentation [6 42 I. With few exceptions such as [3], which uses a pretrained DDPM as a
feature extractor these algorithms assume access to paired data and conditioning information during training of the DDPM model. In 77 a classifier p(y xx) that guides the denoising model towards the desired subset of images with the attribute is trained in parallel with the denoiser. In [5], generation conditioned on an auxiliary image by guiding the denoising process through correction steps that match the low-frequency components of the generated and conditioning images. In contrast, we aim
to build models that combine an independently trained DDPM with an auxiliary constraint.
Our approach is also related to work on adversarial examples. Adversarial samples are produced by optimizing an image x satisfy a desired constraint c classifier p(y|x) without reference to the prior over data. As supervised learning algorithms can ignore the structure in data x, focusing only on the conditional distribution, is possible to optimize for input that provides the desired classification in various surprising ways [41] In [II, diffusion model is used to defend from adversarial samples by making images more likely under a DDPM p(x). We are instead interested in inference, where we seek samples that satisfy both the classifier and the prior. (Our work may, however, have consequences for adversarial generation.)
Conditional generation from unconditional models. Works that preceded the recent popularity of DDPMs [29 9 show how an unconditional generative model, such as a generative adversarial network [GAN: or variational autoencoder [VAE;21], can be combined with constraint model to generate conditional samples. Regarding generative diffusion models, recent literature has focused on utilizing unconditional, pretrained DDPMs priors to solve linear inverse imaging problems. Both in [40 and (00), the authors modify the DDPM sampling algorithm, with knowledge of the linear degradation operator, reconstruct measurements. A generalization of these methods in [18] shows how any pretrained denoising network can be used the prior for solving linear inverse problems. We also clarify that although the term plug-and-play' is widely used in the inverse imaging literature we refer to it in the scope of in-domain generation under differentiable constraints, in the same sense 29
image consistent with the learned prior and given
Modeling the latent prior distribution in VAE-like models using a DDPM has been studied in [38 [3 On the other hand, in $5) we perform inference in the low- dimensional latent space under a pretrained DDPM on high-dimensionall data space. Our approach to semantic segmentation ($4) is also related to [4]. where prior p(z) over latents is used to tune posterior network (())x). There, the priors are of relatively simple structure and are sample-specific,
Latent vectors in DDPMs.
rather than global diffusion priors like in this paper.
2 Method
2.1 Problem setting
Recall that we want to find an approximation to the posterior distribution p(xly) x p(x)c(x,)) y), where p(x) is a fixed prior distribution. Fixing y and introducing an approximate variational posterior q(x), the free energy
F - Ex(e)) Bogg) p(x) + log c(x, y) - log ((x)]
(1)
minimized when q(x) is closest to the true posterior, i.e., when ([x(())))((())) is minimized. When q(x), and the learning algorithm used to fit it, are expressive enough to capture the true

---

posterior, this minimization yields the exact posterior p(xly). seeking' approximation to the true posterior [27]: particular, if q(y) is Dirac delta, it optimal to concentrate y at the mode of p(x(y). When the prior involves latent variables h (i.e., p(x) = Sa (x)) dh), the free energy
Otherwise, q will capture a 'mode-
F (x(x) [(, h) + log c(x, y) (
(h(x))ghh))) |lgg p(x, h) log (x))(((x)()) E. E (og y)].
We are, in particular, interested in general procedure for minimizing F with respect to approxi- mate posterior ((x) for any differentiable c when is a DDPM ($2.2).
A free energy of the same structure was also studied in 4% where a DDPM p(z) over a latent space hybridized as a parent
decoder p(x(z), with an additional inference model (z(xx) trained jointly with both of these models. On the other hand, we aim to work with independently trained components that operate directly the pixel space, e.g., an off-the-shelf diffusion model p(x) trained on images of faces and an off-the-shelf face classifier p(y(x), without training or finetuning them jointly (..2).
2.2 Denoising difflusion probabilistic models as priors
Denoising diffusion probabilistic models (DDPMs) 33 13 generate samples No by reversing (Gaussian) noising process. DDPMs are deep directed stochastic networks:
p(xT, XT-1 xo) = p(xx) II po (x--1 xt),
(3)
(x xx) -V(xxx11
Mo (xL, t), Ex(xi, t)),
p(x))= -NO.)_N((II))
(4)
where (4g and Eg are neural networks with learned parameters (often, as in this paper, En is fixed to scalar diagonal matrix depending on t). The model starts with a sample from a unit Gaussian Xy and successively transforms it with a nonlinear network (x, f) adding small Gaussian innovation signal at each step according
noise schedule. After T steps, the sample x X obtained.
In general, using such a model as a prior over x would require an intractable integration over latent variables h = (X.,.... X1):
p(x) = p(XT,
X1 x) dxr
dx1-
(5)
However, DDPMs are trained under the assumption that the posterior g(xx| xx,xx is simple diffusion process that successively adds Gaussian noise according to predefined schedule 3r:
q(x1 x (x(i V1
3,1), 1 1=
Therefore, if p(x) is the likelihood 5 of x under DDPM, then in the first expectation of ( we should use g(h {xr,..., x |/x00 x) II q(x; xx-1). The simplest approximation the posterior over x Xo is a point estimate:
((x) 6(x (xx-m) m)
where by d we denote the Dirac delta function. Thus, we can sample x, at any arbitrary time step using the forward noising process as
(xx) = Nixx Van (1 -,,)))
(
where a 3r and ār I ay Analogously
we can also extract a conditional Gaussian q(x-11 xx, m7) and express the first expectation in as
- Exlxxig(h)))) llg h) log logg(x) = Σ (L(g(x xx, xx, n) (x xx)),
(9)
which after reparametrization 13 leads to
Σ wi (3) co t)]3) = = =Von + VI -ae.
(10)
3

---

Algorithm I Inferring point estimate of p(xly) s 6(x 7)), under DDPM prior and constraint.
input pretrained DDPM EB, auxiliary data constraint time schedule (t:) learning rate À Initialize x NN(0 I).
2: for i= T.1 do
NN I) 3: Sample
4: Xt. = Va x + vI C
5: x x X V x cx 4:ll2 log y)
6: end for
output 1)
where the stage noise reconstruction EØ (xx, is linear transformation of the model's expectation Hg (x),);))
1
B,
Ho (x t)
X
v1 - ã. es ex(x,)))
(11)
Var
The weighting we (13) is generally function of the noise schedule, but most pretrained diffusion models it is set to 1. Thus, the free energy in (2) reduces to
F Σ Ee-vionn <x 1) [x(x) (oxx)log loge(xxy))))
= - Eew..lll (x 1 log cn, x = =vvann++ vI âje.
(12)
The first term is the cost usually used to learn the parameters 1 of the diffusion model. To perform inference under an already trained model Eg. we instead minimize F with respect to n through sampling in the summands over t.
similar derivation applies a Gaussian approximation the posterior q(x) is used (see SA. Such an approximation allows to model not only mode of the posterior, but the uncertainty in its vicinity.
We summarize the algorithm for point estimate (xx) Algorithm| 1 Variations on this algorithm are possible. Depending on how close to a good mode we can initialize v), this optimization may involve summing only over / S ''axx < T: different time step schedules can be considered depending on the desired diversity in the estimated x. Note that optimization is stochastic and each time it is run can produce different point estimates of which are are both likely under the diffusion prior and satisfy the constraint as much as possible.
We observed that optimizing simultaneously for all t makes it difficult to guide the sample towards mode in image generation applications; therefore, we anneal from high to low values. Intuitively, the first few iterations of gradient descent should coarsely explore the search space, while later iterations gradually reduce the temperature to steadily reach a nearby local maximum of p(x(y). Examples of annealing schedules designed for the tasks demonstrated in (Fig. B.
are presented in the Appendix
Another interesting case is when x is parametrized through a latent variable (this can be seen case of a hard, non-diffcrentiable constraint: if x a deterministic function of y. x = f(y). ). then c(x, y) is supported the corresponding manifold). Then the procedure in Algorithm I can be performed with gradient descent steps with respect to on V1- ā, 1
|| le-colVar,
(13)
instead of steps and 5. (For some semantics of the latent representation, one may wish to make the prior on the pushforward by f of known prior the latent y. In this case, [3 must be weighted by the Jacobian of f at y.).
Experiments: Conditional image generation
3.1 Simple illustration MNIST
We first explore the idea of generating conditional samples from an unconditional diffusion model on MNIST. We train the DDPM model of 7 on MNIST digits and experiment with different sets of

---

(h)
8
(c)
S
(d)
4
(c)
3
3
Thin
Thick
Vert. Asymmetry
Horiz. Asymmetry
Class '3'
Class '3' & Symmetry
Figure I: Inferred MNIST samples under different conditions c(x,y).
constraints log c(x, y) to generate samples with specific attributes. The examples in Fig. showcase such generated samples. For the digit in (a) we set the constraint log e to be the unnormalized score of "thin' digits, computed as negative of the average image intensity, whereas in (b) we invert that and generate a 'thick' digit with high mean intensity. Similarly, in (c) and (d) we hand-craft a score that penalizes the vertical and horizontal symmetry respectively, by computing the L distance between the two folds (vertical/horizontaa) of the digit x, which leads to the generation of skewed, non-symmetric samples.
We also showcase how the auxiliary constraint c(x, y) can modeled by a different, independently trained network. The digit in Fig. (e) is generated by constraining the DDPM with a classifier network that is separately trained to distinguish between the digit class y = and all other digits. The auxiliary constraint in this case is the likelihood of the inferred digit, as it is estimated by the classifier. Finally, for (f) we multiply horizontal symmetry and digit classifier constraints, prompting the inference procedure to generate perfectly centered and symmetric digit. Details of model training and inference can be found in the Appendix ($B.I).
3.2 Using off-the-shelf components for conditional generation of faces
We consider the generation of natural images with a pretrained DDPM prior and a learned constraint. We utilize the pretrained DDPM network on FFHQ-256 [9 from 3 and a pretrained ResNet-18 face attribute classifier on CelebA 25.. The attribute classifier computes the likelihood of presence of various facial features y in given image x, as they are defined by the CelebA dataset. Examples of such features are no beard, smiling, blond hair and male. To generate conditional sample from the unconditional DDPM network we select a subset these and enforce their presence or absence using the classifier predicted likelihoods as our constraint If y is set of attributes we wish to be present, the constraint log c(x. y) can be expressed as
log c(x,
Σ log ply xx
(14)
BEy
We only strictly enforce a small subset of facial attributes and therefore x is allowed to converge towards different modes that correspond to samples that exhibit, in varying levels, the desired features.
In Fig. 2 we demonstrate our ability to infer conditional samples x with desired attributes y, using only the unconditional diffusion model and the classifier ply x). In the first row, we show the results of the optimization procedure of Algorithm T for various attributes. The classifier objective c)x, manipulates the image with the goal of making the classifier network produce the desired attribute predictions, whereas the diffusion objective attempts to pull the sample x towards the learned distribution p(x). If we ignored the denoising loss, the result would be some adversarial noise that fools the classifier network. The DDPM prior, however, is strong enough to guide the process towards realistic-looking images that simultaneously satisfy the classifier constraint set.
We notice that the generated samples x, although having converged towards a correct mode of p(x). still exhibit noticeable amount of noise related to the optimization of classifier objective. To address that, inspired by [31], we simply denoise the image using the DDPM model alone, starting from the low noise level f 200 so to retain the overall structure. The results of this denoising are shown in the second row of Fig. 2
In Fig. 3 we showcase the intermediate steps of the optimization process for inference with the conditions blond bmirissiiigg+nol male, thus solving a problem like that studied in [8] using only independently trained attribute classifiers and an unconditional generative model of faces. The sample
r is initialized with Gaussian noise (O, I), and as we perform gradient steps with decreasing values of t, observe facial features being added in coarse-to-fine manner.
5

---

Blonde
Five-o' cloock
Oval
High Cheekbones
Eyeglasses
Goatee & Big Nose
Shadow
Conditional FFHQ samples x for constraints c(x, y) with various attribute sets Second row: denoising in [31 to remove artifacts that appear when optimizing with classifier network enforcing the constraint.
Figure 2: First row:
1000 t 962 - 896 t- 807 t = 701 t= 585 t 465 f= 349 t 242
Denoise
Figure 3: FFHQ conditional generation for (Blonde, Smiling, Female). The last step performs denoising as [3] to remove artifacts that appear when training on a classifier as a constraint.
In the Appendix BB2.2 provide additional samples and further discuss the sample quality in comparison to unconditional generation. We also present results on inference with conflicting attributes well common failure cases.
Experiments: Semantic image segmentation
We test the applicability of diffusion priors in discrete tasks, such inferring semantic segmentations from images. For this purpose, we use the EnviroAtlas dataset [32) which is composed of 5-class, Im-resolution land cover labels from four geographically diverse cities across the US; Pittsburgh, PA, Durham, NC, Austin, TX and Phoenix, AZ. We only have access to the high resolution labels from Pittsburgh, and the task is infer the land cover labels in the other three cities, given only probabilistic weak labels Ewaak derived from coarse auxiliary data [34]. We use Algorithm | perform an inference procedure that does not directly take imagery input, but uses constraints derived from unsupervised color clustering. We use only cluster indices in inference, making the algorithm dependent on image structure, but not color. Local cluster indices as a representation have a promise of extreme domain transferability. but they require a form of combinatorial search which matches local cluster indices to semantic labels so that the created shapes resemble previously observed land cover, as captured by denoising diffusion model of semantic segmentations.
DDPM on semantic pixel labels. We train a DDPM model on the -eesoluutio one-hot represen- tations the land cover labels. using the U-Net diffusion model architecture from 7 To convert the one-hot diffusion samples to probabilities we follow [15] and assume that for any pixel in the inferred sample the distribution over the label is. p(E.) x fol. N(x Mr. o), where is user-defined parameter. We chose this approach for its simplicity and ease to apply in our inference setting of Algorithm[] Alternatively, we could use diffusion models for categorical data [14] with the appropriate modifications to our inference procedure. Samples drawn from the learned distribution presented in Fig
Inferring semantic segmentations. In order to infer the segmentation of a single image, under the diffusion prior, we directly apply Algorithm with hand-crafted constraint e which provides structural and label guidance. To construct c, we first compute a local color clustering of input

---

Water
Impervious Surface
Soil and Barren
Trees and Forest
Grass and Herhaceous
Figure 4: Unconditional samples from the DDPM trained on land cover segmentations (cf. Fig.
Weak
Image
Clustering
Labels Eweak
Inferred x
Ground Truth
Figure 5: Segmentation inference results. The inferred segmentation is initialized with the weak labels to reduce the number of steps needed. The samples are chosen from (top to hottom) Durham, NC, Austin, TX and Phoenix, AZ. Although AZ has vastly different joint distribution of colors and labels, the inferred segmentation still captures the overall structure. Note that the inference algorithm does use the pixel intensities in the input image, only an unsupervised color clustering.
the image (BB.3 in the Appendix). In addition, we utilize the available weak labels w [34] and force the predicted segments' distribution to match the weak label distribution when averaged in non-overlapping blocks. We combine the two objectives a single constraint c(x, z, &weak) by (i) computing the mutual information between the color clustering z and the predicted labels trans- formed into a valid probability distribution from the inferred one-hot vectors, in overlapping image patches and (ii) computing the negative KL divergence between the average predicted distribution and the distribution given by the weak labels in non-overlapping blocks
log c(x, 2, Eweak) = MI(x, 2) KT[( (weak).
(15)
Empirically, find that we can reduce the number of optimization steps needed to perform inference by initializing the sample x with the weak labels &weak instead of random noise, allowing us to start from smaller t4. Examples of images and their inferred segmentations are shown in Fig. 5
Domain transfer with inferred samples. The above inference procedure is agnostic to colors by design, and we expect it have greater ability to perform new areas than the approach [44] which still finetunes networks that take raw images as input. We also investigate domain transfer approaches where patches segmented using the the diffusion prior are used to train neural networks for fast inference. We pretrain standard U-Net inference network p(x I) solely on 20k batches of 16 randomly sampled x image patches in PA. We randomly sample 640 images in each the other geographies and generate semantic segmentations using our inference procedure, then finetune the inference network on these segmentations. This network is then evaluated on the entire target geography.

---

Table 1: Accuracies and class mean -overuuuinn- scores on the EnviroAtlas dataset in various geographic domains. The model in the second-to-ha row was pretrained in supervised way on labels in the Pittsburgh, PA, region.
Durham, NC
Austin, TX
Phoenix, AZ
Algorithm
Acc %
IoU %
Acc %
IoU %
Acc %
IoU %
PA supervised
74.2
35,9
71.9
36.8
6.7
13.4
PA supervised + weak
78.9
47.9
77.2
50.5
62.8
24.2
Implicit posterior (34
79.0
48.4
76.6
49.5
76.2
46.0
Ours (from scratch)
76.0
39.9
74.8
39.4
69.5
31.6
Ours (fine-tuned)
79.8
46.4
79.5
45.4
69.6
32.4
Full US supervised
33
77.0
49.6
76.5
51.8
24.7
23.6
The results in Table demonstrate that this approach to domain transfer is comparable with the state-of-the-arr work of (34 for
training. The naïve approach training a U-Net only the available high-resolution PA data (PA supervised) fails to generalize to the geographically different location of Phoenix, AZ. Similarly, the model [33]. which is a US-wide high-resolution land cover model trained on imagery and labels, and multi-resolution auxiliary data the entire contiguous US also suffers. When the weak labels are provided as input (PA supervised + weak) the results can improve significantly.
Experiments: Continuous relaxation of combinatorial problems
So far, we have considered inference under DDPM prior and differentiable constraint c(x, y). We consider the case of a 'hard' constraint, where y is latent vector deterministically encoded in an image x fy)) and we have a DDPM prior over images PDDPM(X) (x). We will use the variation of Algorithm described at the end of $2. to obtain a point estimate of the distribution over p(y) X PDDPM (f())).
We illustrate this in the setting of a well-known combinatorial problem, the traveling salesman problem (TSP). Recall that a Fuclidean traveling salesman problem the plane is described by N points U1,.... UN E R², which form the vertex set of complete weighted graph G, where the weight of the edge from v to oy is the Euclidean distance ||e; - rtyl- A tour of G connected subgraph in which every vertex has degree 2. The TSP is the optimization problem of finding the tour with minimal total weight of the edges, or, equivalently, permutation of {1, 2,..., N) that minimizes
|| (2) + (2)) (3)] +... (N [o(l) + (l() (o(D)
Although the general form of the TSP is NP-hard, polynomial-time approximation scheme is known to exist in the Euclidean case 2 28 and can yield proofs tour optimality for small problems.
Humans have been shown to have natural propensity for solving the Euclidean TSP (see [26] for survey). Humans construct tour by processing an image representation of the points , UN through their visual system. However, the optimization algorithms in common use for solving the TSP do not use vision inductive bias, instead falling into two broad categories:
Discrete combinatorial optimization algorithms and efficient integer programming solvers, studied for decades in the optimization literature 24 10):
More recently, there has been work on neural nets, trained by reinforcement learning or imitation learning, that build tours sequentially learn heuristics for their (discrete) iterative refinement. Successful recent approaches 6
16
have used Transformer and graph neural
network 22 architectures.
The algorithm we propose using DDPMs a hybrid of these categories: it reasons over a continuous relaxation of the problem, but exploits the learning of generalizable structure in example solutions by a neural model. addition, ours is the first TSP algorithm to mimic the convolutional inductive bias of the visual system.

---

Optimize latent adjacency matrix w.r.t. denoising model
Recover
Input
256
192
=188
-4
t
Extracted
+ 2-opt
Oracle
Figure 7: The procedure for solving the Euclidean TSP with a DDPM: Gradient descent is performed on a latent adjacency matrix A to minimize a stochastic denoising loss on an image representation f(4) with steadily decreasing amounts of noise (here, 256 steps). In the process, pieces of the tour are 'burned and later recombined in creative ways. Finally, a tour extracted from the inferred adjacency matrix and refined by uncrossing moves. For both problems shown, the length of the inferred tour within 1% of the optimum.
Encoding function. Fix set of points uI...., E [0, 1] 1]. We encode an symmetric N N matrix with 0 diagonal A as 64 x 64 greyscale image f(A) by superimposing: (i) raster images of line segments from to by with intensity value As for every pair (). and (ii) raster images small black dots placed at n for each For example, if the adjacency matrix of tour, then / (AA is a visualization of this tour as a 64 x 64 image.
Diffusion model training. We use dataset of Euclidean TSPs, with ground truth tours obtained by a state-of-the-an TSP solver [10], from (23] (we consider two variants of the dataset, each with ~1,5m training graphs: with 50 vertices in each graph and with varying number from 20 to 50 vertices in each graph). Each training tour is represented via its adjacency matrix A and encoded as an image f(A). We then train DDPM with the U-Net architecture from 7 on all of such encoded image. Model and training details can be found in the Appendix ($B.4). Some unconditional samples from the trained DDPM are shown Fig. most samples indeed resemble image representations of tours.
Solving new TSPs. Suppose we are given new set of points UI,..., Uy. Solving the TSP requires finding the adjacency matrix A of a tour of minimal length. As differentiable relaxa relaxation, + ST. where N X N matrix with zero diagonal (parametrized via softmax of a matrix of parameters over rows), We run the inference procedure using the trained DDPM PDDPM (f (A)) as a prior to estimate A. The hyperparameters and noise schedule are de- scribed in B.4 Examples the optimization shown Fig.
we set A
stochastic
Figure 6: Two unconditional samples from the diffusion model trained images of solved TSPs.
Although the inferred entries close to 0 or 1), rounding A to 0 or does not always give the adjacency matrix of tour (see, for example, the top row of Fig. 7 other common incorrect outputs include pairs of disjoint tours). To extract tour from the inferred A, we greedily insert edges to form an initial proposal, then refine using a standard and lightweight combinatorial procedure, the 2-opt heuristic (24] (amounting to iteratively uncrossing pairs of edges that intersect). The entire procedure is shown in Fig. 7 and full details can be found in the Appendix B.4).
usually sharp (i.e.,
Results We evaluate the trained models test sets of 1280 graphs each with N = 50 and N 100 vertices. We report the average length the inferred tour and the gap (discrepancy from the length of the ground truth tour) in Table 2 (left), from which make several observations.

---

Table 2: Left: Mean tour length and optimality gap on Euclidean TSP test sets. The baseline results from 23 16 4 are taken from the respective papers. The two DDPMs were trained on 1.5m images of solved TSP instances (with different numbers of vertices) and used to infer latent adjacency matrices in the test set. Right: Performance of the DDPM trained on images of 50-vertex TSP instances with different numbers of inference steps (see the Appendix ($B.4) for time schedule details). We also show the mean number of 2-opt (uncrossing) steps per instance, suggesting that the DDPM prior assigns high likelihood to adjacency matrices that are in less need of refinement.
50
N
100
Algarithm
Gup
Obj
Gap
N 50
N 100
Oracle (Concorde 10)
5.69
0.00
7.759
0.00
Diff. steps
Obj
Gap %
Steps
Obj
Gap %
Steps
2-opt 2
5.86
2,95
8.03
3.54
256
5.763
1.28
11.6
7,930
2.19
64
5.780
2.60
14.3
7.942
2.35
45.7
Transformer
5.80
1.76
8.12
4.53
16
5,858
2.98
25.9
8.052
3.78
GNN [16
5.87
3,10
8.41
8.38
5.851
2.86
23.9
8.031
3.50
52.8
Transformer
7.88
1.42
2-opt
5.856
24.4
3.54
Diffusion 20-50 50
5.76
1.23
7.92
2.11
Diffusion 50
5.76
1.28
7,93
2.19
The right side of Table 2 shows the number of 2-opt (edge uncrossing) steps performed in the refinement step of the algorithm when the inference algorithm run for varying numbers of steps. Running the inference with more steps results in extracted tours that closer local minima with respect to the 2-opt neighbourhood, indicating that the DDPM encodes meaningful information about the shape of tours.
The DDPM inference is competitive with recent baseline algorithms that do not use beam search in generation of the tour (those shown the table). These baseline algorithms improve when beam search decoding with very large beam size is used, but encounter diminishing returns as the computation cost grows. Our performance on the 100-vertex problems similar to (23 with largest beam size they report (5000), which has 2.18% gap, while having similar computation time.
The model trained on problems with 50 nodes performs almost identically to the model trained on problems with 50 or fewer nodes, and both models generalize better than baseline methods from 50-node problems to the out-of-distributie 100-node problems.
We emphasize unique feature of our algorithm: all 'reasoning' in our inference procedure happens via the image space. This property also leads to sublinear computation cost scaling with increasing size of the graph as long as the computation cost of inference is borne by running the denoiser on images a fixed size. In the Appendix ($B.4) we explore the generalization of the model trained on 20- 50-node TSP instances to problems with 200 nodes and discuss potential extensions.
reasonably be represented in 64 64 image since most of
Conclusion
We have shown how inference in denoising diffusion models can be performed under constraints in a variety of settings. Imposing constraints that arise from pretrained classifiers enables conditional generation, while common-sense conditions, such mutual information with a clustering diver- gence from weak labels, can lead to models that are less sensitive to domain shift in the distribution of conditioning data.
notable limitation of DDPMs, which is inherited by our algorithms, is the high cost of inference, requiring a large number of passes through the denoising network to generate sample. We expect that with further research on DDPMs for which inference procedures converge in fewer steps [37 45) plug-an and-alas
of DDPMs will become more appealing in various applications.
Finally, our results on the traveling salesman problem illustrate the ability of DDPMs to reason over uncertain hypotheses in a manner that can mimic human 'puzzle-solving' behavior. These results open the door to future research on using DDPMs to efficiently generate candidates in combinatorial search problems.
10

---

Acknowledgments
The authors thank the anonymous NeurIPS 2022 reviewers for their comments.
All authors are funded by their primary institutions. Partial support was provided by the NASA Biodiversity program (Award 80NSSC2I NSF grants IIS-2123920 and I1S-2212046, and the Partner University Fund 4D Vision award.
References
[1] Tomer Amit, Eliya Nachmani, Tal Shaharabany, and Lior Wolf. Segdiff: Image segmentation with diffusion probabilistic models. arXiv preprint 2112.00390, 2021.
[2] Sanjeev Arora. Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. Journal of the Association for Computing Machinery, 45(5):753-78,, 09 1998.
[3] Dmitry Baranchuk, Andrey Voynov, Ivan Rubachev, Valentin Khrulkov, and Artem Babenko. Label-efficient semantic segmentation with diffusion models. International Conference Learning Representations (ICIR), 2022.
[4] Xavier Bresson and Thomas Laurent. The transformer network for the traveling salesman problem. arXiv preprint 2103.03012, 2021.
[5] Jooyoung Choi, Sungwon Kim, Yonghyun Jeong, Youngjune Gwon, and Sungroh Yoon. ILVR: conditioning method for denoising diffusion probabilistic models. International Conference on Computer Vision (ICCV), 2021.
[6] Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis-Martin Rousseau. Learning heuristics for the TSP by policy gradient. In Integration of Constraint Programming. Artificial Intelligence, and Operations Research, pages 170-181. Springer International Publishing, 2018
[7] Prafulla Dhariwal and Alexander Quinn Nichol. Diffusion models beat GANs on image synthesis. Neural Information Processing Systems (NeurIPS), 2021.
[8] Yilun Du, Shuang Li, and Igor Mordatch. Compositional visual generation with energy based models. Neural Information Processing Systems (NeurIPS), 2020.
[9] Jesse H. Engel, Matthew D. Hoffman, and Adam Roberts. Latent constraints: Learning to generate conditionally from unconditional generative models. International Conference on Learning Representations (ICLR), 2018.
[10] David Applegate et al. Concorde TSP solver. http::/www..n math. www.wrloo..ccaaappppppppp... concorde. 1997-2003.
[11] Ian Goodfellow, Jean Pouget-Abadis Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Neural Information Processing Systems (NeurIPS), 2014.
[12] Keld Helsgaun. An effective implementation of the Lin KirnKanni traveling salesman heuristic. European Journal of Operational Research, 126(1):106-13))) 2000.
[13] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Neural Information Processing Systems (NeurIPS), 2020.
[14] Emiel Hoogeboom, Didrik Nielsen, Priyank Jaini, Patrick Forré, and Max Welling, Argmax flows and multinomial diffusion: Learning categorical distributions. Neural Information Processing Systems (NeurIPS), 2021.
[15] Emiel Hoogehoom, Victor Garcia Satorras, Clément Vignac, and Max Welling. Equivariant diffusion for molecule generation in 3D. arXiv preprint 2203.17003, 2022.

---

[16] Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint 1906.01227, 2019.
[17] Chaitanya Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Laurent. Learning tsp requires rethinking generalization. International Conference on Principles and Practice of Constraint Programming, 2021.
[18] Zahra Kadkhodaic and Eero Simoncelli. Stochastic solutions for linear inverse problems using the prior implicit in a denoiser. Neural Information Processing Systems (NeurIPS), 2021.
[19] Tero Karras, Samuli Laine, and Timo Aila. style-based generator architecture for generative adversarial networks. Computer Vision and Pattern Recognition (CVPR), 2019.
[20] Bahjat Kawar, Gregory Vaksman, and Michael Elad. SNIPS: Solving noisy inverse problems stochastically. Neural Information Processing Systems (NeurIPS), 2021.
[21] Diederik P. Kingma and Max Welling, Auto-encoding variational bayes. International Confer- ence on Learning Representations (ICLR), 2014.
[22] Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations (ICLR), 2017.
[23] Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! International Conference on Learning Representations (ICLR), 2019.
[24] Shen Lin and Brian Kernighan. An effective heuristic algorithm for the traveling-salesman problem. Operations Research, 21(2):498-511 1973.
[25] Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. International Conference on Computer Vision (ICCV), 2015.
[26] James MacGregor and Yun Chu. Human performance on the traveling salesman and related problems: A review. The Journal of Problem Solving, 3, 02 2011.
[27] Tom Minka. Divergence measures and message passing, Microsoft Research Technical Report, 2005.
[28] Joseph S. B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric tsp, k-mst, and related problems. SIAM Journal on Computing, 28(4): 1999.
[29] Anh Nguyen, Jeff Clune, Yoshua Bengio, Alexey Dosovitskiy, and Jason Yosinski. Plug & play generative networks: Conditional iterative generation of images in latent space. Computer Vision and Pattern Recognition (CVPR), 2017.
[30] Alex Nichol and Prafulla Dhariwal. Improved denoising diffusion probabilistic models. Inter- national Conference on Machine Learning (ICML), 2021.
[31] Weili Nie, Brandon Guo, Yujia Huang, Chaowei Xiao, Arash Vahdat, and Anima Anandkumar. Diffussin models for adversarial purification. International Conference on Machine Learning (ICML), 2022. To appear; arXiv preprint 2205.07460.
[32] Brian R. Pickard, Jessica Daniel, Megan Mehaffey, Laura E. Jackson, and Anne Neale. Envi- roatlas: A new gcospatial tool to foster ecosystem services science and resource management. Ecosystem Services, 445))55555, 2015. URL https://EconPapeers repec. org/RePEct
eee: exe::ccoer::o : v: 14: :::
[33] Caleb Robinson, Le Hou, Nikolay Malkin, Rachel Soobitsky, Jacob Czawlytko, Bistra Dilkina, and Nebojsa Jojic. Large scale high-resolution land cover mapping with multi-resolution data. Computer Vision and Pattern Recognition (CVPR), 2019.
[34] Esther Rolf, Nikolay Malkin, Alexandros Graikos, Ana Jojic, Caleb Robinson, and Nebojsa Jojic. Resolving label uncertainty with implicit posterior models. Uncertainty Artificial Intelligence ( (UAI), 2022. To appear, arXiv preprint 2202.14000
12

---

[35] Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedical image segmentation. Medical Image Computing and Computer-Assie Asssistt Intervention (MICCAT). 2015.
[36] Chitwan Saharia, Jonathan Ho, William Chan, Tim Salimans, David J. Fleet, and Mohammad Norouzi. Image super-resolution via iterative refinement. arXiv preprint 2104.07636, 2021.
[37] Tim Salimans and Jonathan Ho. Progressive distillation for fast sampling of diffusion models. International Conference on Learning Representations (ICLR), 2022.
[38] Abhishek Sinha, Jiaming Song, Chenlin Meng, and Stefano Ermon. D2C: diffusion-decoding models for few-shot conditional generation. Neural Information Processing Systems (NeurIPS), 2021.
[39] Jascha Sohl-Dickstein, Eric A. Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. International Conference on Machine Learning (ICML), 2015.
[40] Yang Song, Liyue Shen, Lei Xing, and Stefano Ermon. Solving inverse problems in medi- cal imaging with score-based generative models. In International Conference on Learning Representations (ICLR), 2021.
[41] Christian Szegedy, Wojeiech Zaremba, Ila Sutskever, Joan Bruna, Dumitru Erhan, Ian Good- fellow, and Rob Fergus. Intriguing properties of neural networks. International Conference on Learning Representations (ICIR), 2014.
[42] Yusuke Tashiro, Jiaming Song, Yang Song, and Stefano Ermon. CSDI: conditional score- based diffusion models for probabilistic time series imputation. Neural Information Processing Systems (NeurIPS), 2021.
[43] Arash Vahdat, Karsten Kreis, and Jan Kautz. Score-based generative modeling in latent space. Neural Information Processing Systems (NeurIPS), 2021.
[44] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Neural Information Processing Systems (NIPS), 2017.
[45] Zhisheng Xiao, Karsten Kreis, and Arash Vahdat. Tackling the generative learning trilemma with denoising diffusion GANs. International Conference on Learning Representations (ICLR), 2022.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See the conclusion and discussion throughout the paper.
(c) Did you discuss any potential negative societal impacts your work? [N/A] Although no immediate negative societal impacts expected, researchers should bear in mind
the risks of flexible conditional generation of images, e.g., for creating 'deep fakes'.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material or as URL.) [Yes] For most experiments; see the Appendix.
13

---

(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See the Appendix and relevant experiment sections.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- time.
ments multiple times)? [No] Main experiments were
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See the Appendix.
4. If you are using existing assets (c.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] See the relevant experiment sections.
(b) Did you mention the license of the assets? [No] But all datasets used are free to use for research purposes; see the relevant citations.
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "bOtdFJjI0uG", "reviewer": "Reviewer_6Fox", "summary": "In this work, the authors consider the problem of inferring high-dimensional data x in a model that consists of a prior and an auxiliary constraint, which has a differentiable form and can come from diverse sources. The authors demonstrate the efficiency of the proposed framework in different tasks.", "questions": "Please refer to the weaknesses part.", "limitations": "The author addressed some limitations in the conclusion part.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Interesting idea. The proposed model provides different conditional information, which seeks samples x that satisfy both the classifier and the prior. It does not require additional training or finetuning model components or inference networks.\n- Novel methodology. Though recently using diffusion priors for high-fidelity synthesis has been studied in a wide range of literature, the proposed algorithm in this work is original and novel. \n- Good presentation. The paper is well-written.\n\n\nWeaknesses: \n- Insufficient experiments. The authors conduct experiments on conditional generation, image segmentation, and combinatorial search problems. However, quantitative analysis is missing. How does the proposed model outperform previous arts? Furthermore, the author spends two pages describing the traveling salesman's problems, while the reviewer thinks focusing more on the benchmark image synthesis task could be better.\n- More Question: The author presents their classifier-guided conditional image synthesis results on the FFHQ dataset, but what is the difference between some popular Guided-Diffusion methods?\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ZsZpaOsSj_0", "reviewer": "Reviewer_akx3", "summary": "This paper uses the diffusion model as prior modeling, and it mainly focuses on downstream tasks.", "questions": "-", "limitations": "-", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "$\\textbf{Strengths}$\n- This paper formalizes the estimation of the posterior distribution using a pre-trained diffusion model. This is not a new idea, but its strength lies in the formalization and vast applications.\n- A majority of conditional diffusion models re-train their score network, but having a fixed diffusing SDE, there is no need to re-train the estimated perturbed score function, and an endeavor is needed to solve downstream tasks without re-training the pre-trained diffusion model. This paper gives the most general framework in this aspect.\n- Aside from the framework, the novelty of this paper could be evaluated by its application cases. It solves semantic image segmentation and traveling salesman problem using DDPM, which is the first to the best of my knowledge. Solving these problems with DDPM is a significant novelty.\n\n$\\textbf{Weaknesses}$\n- The framework is not a new idea, and a number of papers already applied this framework without mentioning or formalizing explicitly. Therefore, suggesting a framework itself is relatively a weak contribution in the community.\n- We think that the authors suggested a framework on an abstract level because they tried to put multiple downstream tasks in a single paper. However, generally, this is not a desirable approach to write a paper. We recommend authors to focus down on each task in separate manuscripts.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "IRfkHFMGG6", "reviewer": "Reviewer_3SJz", "summary": "This paper proposed to use pre-trained denoising diffusion probabilistic models (DDPM) as priors for other inference tasks. The way the authors use DDPM is to revert a DDPM by inputting $x$ and output a random noise $\\epsilon$. By comparing the difference between inverse mapping and noise (usually Gaussian), the proposed framework can ensure $x$ lie in the range of DDPM. Furthermore, the authors construct an optimization problem where the loss function is the summation of log likelihood (auxiliary constraint) and l2 loss. By iteratively searching for the solution that both stays in the range of DDPM and satisfies the constraint, the proposed framework makes DDPM a plug-and-play prior for arbitrary inference tasks.", "questions": "1. Please show more detailed deriviation from Eq.7-11, especially the re-parameterization trick.\n2. line 109, \"To perform nference under an already trained model ϵθ, we instead minimize F wrt to η (and ψ if desired) through sampling ϵ in the summands over t.\". Don't you directly minimize $x_t$?\n3. In the segmentation task, how were the DDPM networks finetuned? Does scratch mean pre-trained?", "limitations": "One limitation of the experiment is the lack of image restoration tasks, which I believe can better demonstrate the prior information provided by DDPM.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength:**\n- The author proposes a novel Plug-and-play priors by leveraging DDPM. Different from the existing priors based on GAN, the proposed framework inversely map the image $x$ into the latent space. In this way, the iterate is no longer the latent variable but the actual image.\n- The paper demonstrates its generality on a wide range of tasks, including segmentation, face generation, and traveling salesman problems. It is my first time to see someone solves a combinatorial problem by using DDPM.\n\n**Weakness:**\n- The paper is not easy to read. There is not enough detailed derivations between eq.7-11\n- The novelty of the work is not clearly stated.\n- The naming of the framework is confusing. Plug-and-play priors (PnP) is a well-known framework in the literature of image restoration and imaging inverse problems. The title confuses me in the first place.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "AuarsVu1QNd", "reviewer": "Reviewer_FMow", "summary": "The authors propose a new conditional sampling approach by using denoising diffusion models (DDPM) as priors, in which they explicitly model the auxiliary constraint (e.g., pretrained classifiers, etc.) in the reverse diffusion process. The resulting model is demonstrated on conditional image generation, semantic image segmentation, and traveling salesman problem (TSP). Experiments show that their new conditional sampling model can be implemented in practice.", "questions": "1), The instruction of the proposed method in Sec. 2.2 is somehow ambiguous and hard to follow in some parts. Specifically, in line 97-98, what’s the value or definition of $\\eta$ and $\\psi$ and how to link $q(x_t)$ in Eq. 8 to the tractable forward process $q(x_t | x_0) = N(x_t;\\sqrt{\\bar{a_t}}x_0,(1-\\bar{a_t})\\mathsf{I})$ in [Jonathan. et al, 2020]. It is also unclear the meaning of $ q(x_{t-1} | x_t, \\eta, \\psi) $ in the KL in Eq. 9. Is this the same as $ q(x_{t-1} | x_t, x_0) $? Additionally, what is the objective function F minimizing?  In brief, a clearer explanation and instruction of the proposed method will be helpful.\n\n2), From very high-level point of view, what make this proposal different from existing score-based conditional model such as [R1, R2]? The existing methods can also take pretrained unconditional generative models as denoising priors to solve cross domain tasks such as image inverse problems, which is similar to the “plug-and-play” term used in this work.\n\n3), In the same line above, what is the main difference between GAN-based priors and the diffusion model priors? Will the predefined time schedule affect the generation performance? A deeper understanding and intuition would be helpful.\n\n4), There lack enough numerical comparisons to baseline methods for conditional image generation. How is the performance compared to other SOTA conditional generative models? Only visual examples of the proposed method are presented in current manuscript. \n\nRef:\n\n[R1] Song, et al., Solving Inverse Problems in Medical Imaging with Score-Based Generative Models, 2021.\n\n[R2] Kawar, et al., SNIPS: Solving Noisy Inverse Problems Stochastically, 2021. \n\nMinor comments:\n\nTypos in line 33, 237-238, and 266-267 in the main manuscript.\n", "limitations": "The authors mentioned the high computational cost by using DDPMs as priors to generate samples. This is also the bottleneck for many DDPMs.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper builds on other works in the recent literature and proposes something useful. It is overall well written. It presents a conditional generation model that can take many pretrained unconditional DDPMs as “black-box” prior. The numerical results demonstrate the effectiveness of this proposal on various imaging and none imaging tasks. However, the writing of the method section could be improved to make it easier to follow. Additionally, the methodological contributions and novelty of this proposal is somewhat unclear due to the lack of literature review and a deeper comparison to existing work. Please find my technical comments as follows.  ", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept