Divide-and-Conquer Posterior Sampling for Denoising Diffusion priors
Authors: Yazid Janati
Badr MOUFAD
Alain Oliviero Durmus
Eric Moulines
Jimmy Olsson
Venue: NeurIPS 2024 poster (2024)
Keywords: Denoising Diffusion models
posterior sampling
Monte Carlo methods
Primary area: probabilistic_methods

Abstract: Recent advancements in solving Bayesian inverse problems have spotlighted denoising diffusion models (DDMs) as effective priors.
Although these have great potential, DDM priors yield complex posterior distributions that are challenging to sample from.
Existing approaches to posterior sampling in this context address this problem either by retraining model-specific components, leading to stiff and cumbersome methods, or by introducing approximations with uncontrolled errors that affect the accuracy of the produced samples.
We present an innovative framework, divide-and-conquer posterior sampling, which leverages the inherent structure of DDMs to construct a sequence of intermediate posteriors that guide the produced samples to the target posterior.
Our method significantly reduces the approximation error associated with current techniques without the need for retraining.
We demonstrate the versatility and effectiveness of our approach for a wide range of Bayesian inverse problems.
The code is available at \url{https://github.com/Badr-MOUFAD/dcps}

Divide-and-Conquer Posterior Sampling for Denoising Diffusion Priors
Yazid Janati":
Badr Moufad
Alain Durmus'
Eric Moulines
Jimmy Olsson
1 CMAP, Ecole polytechnique
2 KTH Royal Institute of Technology
MBZUAI
Abstract
Recent advancements solving Bayesian inverse problems have spotlighted de- noising diffusion models (DDMs) effective priors. Although these have great potential, DDM priors yield complex posterior distributions that are challeng- ing sample. Existing approaches to posterior sampling in this context address this problem either by retraining model-specific components, leading to stiff and cumbersome methods, by introducing approximations with uncontrolled rors that affect the accuracy of the produced samples. We present an innovative framework, divide-and-conquer posterior sampling, which leverages the inher- ent structure of DDMs to construct a sequence of intermediate posteriors that guide the produced samples the target posterior. Our method significantly reduces the approximation error associated with current techniques without the need for retraining. We demonstrate the versatility and effectiveness of our ap- proach for wide range of Bayesian inverse problems. The code is available at https:// //ggtttt.../...//// com Bet//Bddr--UUFFFAA
Introduction
Many problems in machine learning can be formulated as inverse problems, such as superresolution, deblurring, and inpainting, to name but few. They all have the same goal, namely to recover signal of interest from an indirect observation. One line of research addresses these problems through the lens of the Bayesian framework by specifying two components: prior distribution, which embodies the specification of the signal, and a likelihood that describes the law of the observation conditionally the signal. Once these elements are specified, the inverse problem is solved by sampling from the posterior distribution, which, after including the observation, contains all available information about the signal and thus about uncertainty as well [12]. The importance of the specification of the prior in solving Bayesian ill-posed inverse problems is paramount. In the last decade, the success of priors based on deep generative models has fundamentally changed the field of linear inverse problems [40, 55, 19, 36, 24J. Recently, denoising diffusion probabilistic models (DDMs) have received special attention. Thanks their ability to learn complex and multimodal data distributions. DDM represent the state-of-the-an in many generative modeling tasks, e.g. image generation [45, 20, 50, 52, 15, 46, 49]. super-resolution [43, 1]. and inpainting [45, 11, 22].
Popular methods to sample from posterior distribution include Markov chain Monte Carlo (MCMC) and variational inference: [53, and the references therein. These methods are iterative schemes that require an explicit procedure to evaluate pointwise the prior distribution and often its (Stein) score function [21] in order compute acceptance ratios and construct efficient proposals. While
Equal contribution
Corresponding authors: (yazid.jam janati, badr.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

sampling from the DDM priors is straightforward, posterior sampling is usually challenging since the intractability of the posterior density and its score make them computationally prohibitive and thus invalidate all conventional simulation methods. Although approx exist, their associated iterative sampling schemes can be computationally intensive and exhibit high sensitivity to the choice of hyperparameters: see e.g. [24].
This paper proposes the DIVIDE-AND- AAIDE-AND-CONQUER CONQUER POSTERIOR SAMPLER (DCPS), novel approach to posterior sampling in Bayesian inverse problems with DDM priors. Thanks to the Markov property of the data-gent satt-renng backward diffusion, the posterior can be expressed as the marginal distribution of a Feynman Kac (FK) path measure [13]. whose length corresponds to the number of diffusion steps and whose user-defined potentials serve to bias the dynamics of the data- gettarenngating backward diffusion to align with the likelihood of the observation. Besides, for a given choice of potentials, the FK path law becomes Markovian, making possible to express the posterior as the marginal of a time-reversed inhomogeneous Markov chain.
This approach is tempting, yet, the backward Markov decomposition remains difficult apply in practice as these specific potential functions are difficult to approximate, especially when the number of diffusion steps is large. We tackle this problem with a divide-and-conquer approach. More precisely, instead of targeting the given posterior by a single simulation run through the full backward decomposition, our proposed scheme targets backward a sequence (TT 2o of distributions along the path measure leading to the target posterior distribution (section 3). These distributions are induced by a sequence of increasingly complex potentials and converge the target distribution. Starting with sample from "Ke4 a draw from Tx is formed by a combination of Langevin iterations and the simulation of an inhomogeneous Markov chain. In other words, Tk,, is expressed as the final marginal distribution of a time-reversed inhomogeneous Markov chain of moderate length ke+1 - kg E N with an initial distribution " This chain, whose transition densities are intractable, is approximately sampled using Gaussian variational inference. The rationale behind our approach stems from the observation that the Gaussian approximation error can be reduced by shortening the length of the intermediate FK path measures (i.e. by increasing L); result that we show in Proposition A. We finally illustrate that our algorithm can provide high-quality solutions to Bayesian inverse problems involving a variety of datasets and tasks.
To sum up our contribution, we
show that the existing approximations of the Markovian backward decomposition can be im- proved using a bridge-kernel smoothing technique
design a novel divide-and sande-and-conquee sampling approach that enables efficient bidu-reduced sam- pling from the posterior, and illustrate its performance several Bayesian inverse problems including inpainting, outpainting, Poisson imaging, and JPEG dequantization,
propose a new technique to efficiently generate approximate samples from the backward decom- position using Gaussian variational inference.
Notation. For (m, n) E N2 such that m < we let [m, n| := (m,,.., n). We use N(x; n,, E) to denote the density at x Gaussian distribution with mean μ and covariance matrix Σ. La is the d- d-dimensional identity matrix and 5 denotes the Dirac mass W2 denotes the Wasserstein distance of order 2. We use uppercase for random variables and lowercase for their realizations.
2 Posterior sampling with DDM prior
DDM priors. We provide a brief overview of DDMs [45, 50, 20]. Suppose we can access an empirical sample from some data distribution Pam defined on Rd=, For n E large enough and h: E [[]. define the distribution y4 (Ix) := (amn((ro) (T (ro)dro with jojo (zr) == N(=6; Vagao, (1 an)) ). where (ox))_ is a decreasing sequence with og 1 and on approxi- mately equals zero. The probability density 93 corresponds to the marginal distribution time & of
an auto-regressive process on Rd= given by Xx+1 = / //ss1//////// Xa + /1 - ax++ / with Xn Piuss and (= being a sequence of i.i.d. d.ndiinnnio standard Gaussians.
1o (oolar)ddn where DDMs leverage parametric approximations iggs. of the mappings zg +> f 1o l01
o (zo xxk) x Pama (2o) (=) is the conditional distribution of Xo given X² Zg. Each 6

---

is defined as *0 (ax) := (z - (n /as,, where eg is a noise predictor network trained by minimizing denoising objective; see [46, Eq. (5) and Appendix A for details. Following [15, Section 4.2], & also provides an estimate of the score V log 43 (zxx given by (zx) := - t
yar-f (1x) (11=))((= We denote by 0* the minimizer of the denoising objective. Having access to 0*, we can define a generative model for Pam by adopting the denoising diffusion probabilistic model (DDPM) framework of [20]. As long as is large enough, In can be confused with a multivariate standard Gaussian. Define the bridge kernel 9a 0+ (2& Zo, 2k++1 X 91jo [2o) 1|s (x (1*+1 which is a Gaussian distribution with mean / (To, F4+1) and diagonal covariance of RR441 Id,
defined in Appendix A.1. Define the generative model for Pau
po: (10m) = (,( I P h41 (x++1))
(2.1)
where for every &s E [L, n 1], the backward transitions are PkiK+ (Ia/ == 2ujo. (Ir 1 -
+ (I 2k+1))
(2.2)
with poj (-la1) == (en) and Pa (xx) = N( 0, Ia,) In the following, we assume that we have access to a pre-trained DDM and omit the superscript 6* from the notation, writing simply p and folk when referring the generative model and the denoiser, respectively. In addition, we denote by Pkc the k-th marginal of Po.n and write, for all (l, m) E [[] such that & < m, Pe[m (ze|Zm))
= lime Pk]s+41(2 (I
Posterior sampling. Let 9n be a nonnegative function on Rdd When solving Bayesian inverse problems, 9o is taken the likelihood of the signal given the observation specified using the forward model (see the next section). Our objective is to sample from the posterior distribution
To (zo) == 90 (xo) (zo))
(2.3)
where Z := f (1o) Po Po(2o)da the normalizing constant and the prior Po is the marginal of (2.1) w.r.t. Te. in which case the posterior (2.3) can be expressed as
To (xO)
1 z go (zo)
II Pa Po (Za) dæim.
Thus, Equation (2.3) can be interpreted as the marginal of a time-reversed FK (Feynman -aae)annnKKK))--- model with non-trivial potential only for l = O; see [13] for comprehensive introduction to FK models. In this work, we twist, without modifying the law of the FK model, the backward transitions Pk|K+1 by artificial positive potentials ( each being function on Rdd,, and write
1 To(oo)= 2 f gm (En)
9g(2 k= I6+1 (I++1) PEtK+1 (Fa( drin.
II
(2.4)
This allows the posterior of interest be expressed as the time-zero marginal of FK model with initial distribution P,,. Markov transition kernels (Pæj=+1) > and (ow)
Recent works that aim to sample from the posterior (2.3) generally employ the FK representation (2.4). These studies, however, adopt varying auxiliary potentials [10, 47, 60, 4, 54, 59]. FK models can be effectively sampled using sequential Monte Carlo (SMC) methods; see, e.g., [13, 9]. SMC methods sequentially propagate weighted samples, whose associated weighted empirical distributions target the flow of the FK marginal distributions. The effectiveness of this technique depends heavily on the choice of intermediate potentials (fx))= as discussed in [54, 59, 7, 16]. However, SMC methods require number of samples proportional and often exponential in the dimensionality of the problems hence limiting their application in these setups due to the resulting probabitive memory cost [2]. On the other hand, reducing the number of samples makes them vulnerable to mode collapse.
In the following, we will focus on particular choice of potential functions (g for which the posterior mo can be expressed as the time-zero marginal distribution of time-reversed Markov chain. The transition densities of this chain are obtained by twisting the transition densities of the generative model with the considered potential functions. More precisely, define, for all k.
3

---

the potentials 9 (xx))= == f 90 (o())) Poja (2ol drg. Note that these potentials satisfy the recursion ( = 9 (2*) Ps 1+1 (I (x drg. Builing upon that, define the Markov transitions
(7 9 PkIE+11 PRIE+1(2 (x0/(2++1)))
TA|++1 (oe (x4+)))
(2.5)
allowing the posterior (2.4) to be rewritten as
n-1
=o(2u) == nT (In)
xh 1 dzims (,((n) = km
II
(2.6)
In other words, the distribution To is the time-zero marginal of Markov model with transition densities ( and initial distribution nT According to this decomposition, a sample Xī from the posterior (2.3) can be obtained by sampling X ~ n and then, recursively sampling X TT Tk/A+1 (-1xx())) from k n 1 till k = O. In practice, however, neither the Markov transition densities *I|++1 nor the probability density function n, are tractable. The main challenge in estimating "*|k+1 stems essentially from the intractability of the potential g (2x) as it involves computing expectation under the high-cost sampling distribution Pojk (-12x).
Recent works have focused on developing tractable approximations of Poja (-(2a). For the Diffusion Posterior Sampling (DPS) algorithm [10], the point mass approximation ((x) of Pojs (-12x))
results in the estimate Vay log No o (3+)) of Va, log (3a)). Then, given sample XR+1, an approximate sample X2 from x ([X++)) is obtained by first sampling Xx+ Peuu+1 (+14)+1) and then setting
= Xx Ve log (e ( (1=-1))
(2.7)
where Ç 0 is tuning parameter. As noted in [48, 7. 4], the DPS updates (2.7) do not lead to an accurate approximation of the posterior To even in the simplest examples; see also Section 4. Alternatively, [47] proposed the Guuiddddvers--Guiied Diffusion Model (IIGDM), which uses Gaussian approximation of Pojæ (- with mean Zoou (zx) and diagonal covariance matrix set to - Jd, which corresponds the covariance of 9n-e--1la (-12%) ) if Pam had been a standard Gaussian; see [47, Appendix 1.3]. More recently. [17, 4] proposed to approximate the exact KL projection of Poja k ( (ia) onto the space of Gaussian distributions by noting that both its mean and covariance matrix can be estimated using oo (xx) and its Jacobian matrix. We discuss in more depth the related works in Appendix B.
The DCPS algorithm
Smoothing the DPS approximation. The bias of the DPS updates (2.7) stems from the point mass approximation of the conditional distribution (1 This approximation becomes more accurate as k tends to zero and is crude otherwise. We aim here to mitigate the resulting approximation errors. A core result that we leverage in this paper is that for any (k, () E [0, nz]² such that & < k. we can construct an estimate Prps ((zx) of Peix (-1ax) that bears a smaller approximation error than the estimate 62 (mx) relatively to Pojk (flarg)- Formally, let Po (+1ar)) denote any approximation of Poju (11x)), such as that of the DPS or IIGDM, and define the approximation of (-(xa)
PeI(())(Z)) = / geja, (xel Ia Poja (x)) dæo.
(3.1)
where qejo, (zel m4) is defined in (A.4). We then have the following result. Proposition 3.1 (informal). Let & E [1. For all & E [0, l 1] and In E TRd,, Wa(Peye(-lass) (-xx+) var(1 - ax/ar)
W (2(Po (-12x)) Poju (-1x+)).
(3.2)
-ap)
The proof is postponed Appendix A.3. Note that the ratio in the right-hand-side of (3.2) is less than 1 and decreases as l increases. As an illustration, using the DPS approximation of Poja (-)2x), we find that Peja (x)) q ( (zel (#t), improves upon DPS in terms of approximation error.

---

This observation prompts to consider DPS-like approximations on shorter time intervals; instead of approximating expectations under Pojs (-|2z), such as the potential g (Ix), we should transform our initial sampling problem so that we only have to estimate expectations under Peje (-12x)) for any & such that the difference k- - l is small. This motivates the blocking approach introduced next.
Intermediate posteriors. We approach the original problem of sampling from To via a series of simpler, intermediate posterior sampling problems of increasing difficulty. More precisely, let us consider the intermediate posteriors defined as
f
Zke := 10, (Ike Pi,, (Ike) dakkr The (x : 9k, (a Pk, (Ikr)/Zx, with
(3.3)
where (gea) )= are potential functions designed by the user and (kz) is an increasing sequence in [0, nil such that kn = and hi = n. Here, I. is typically much smaller than n. To obtain an approximate sample from = ka the DCPS algorithm recursively uses approximate sample Xkeas from Thet1 to obtain an approximate sample Xxe from Thk- Indeed, mirroring (2.6) it holds
ke41
The (arke) = f Thei (Ikk41)
II m=
af mlm+1 (fml 11)+) d. +1:ke4
(3.4)
where for m E like ke+1 - II.
Them (Ikees) = Shets (#key Pkees ( 2k,
Ait
T mmmm+ (I'm (mm+2) == gin" Pm m 1 (Zmm (m++1) / Im (mm-1)
and for m E like 1, kettal.
/ gko (I Pke cl (Tk, (mm) dr
Im (Im) =
(3.5)
We emphasize that the initial distribution =T/ in (3.4) is different from the posterior "ky_, the former involves the user-defined potential whereas the latter the intractable one. The main advantage of our approach lies in the fact that, unlike the potentials in the transition densities (2.5), which involve expectations under Poja (-1xx,, the potentials (3.5) are given by expectations under the distributions Pm (-Izm), which are easier to approximate in the light of Proposition 3.1. In the sequel, we use this approximation for the estimation of the potentials (3.5); this yields approximate potentials
L.* (Im) : 9he (Ik; Pkalm (I [mm) drk, m E [kk + 1, 11,44ll.. 9m
(3.6)
which serve as substitute for the intractable ofx*. Let us now summarize how our algorithm works. Starting from a sample X which is approximately distributed according to T the next sample Xxe is generated in the next two steps:
1. Perform Langevin Monte Carlo steps initialized at Xk24, and targeting Thens yielding X keas'
2. Simulate a Markov chain (X,) (x,)) initialized with Xkeas = X and whose transition from X,+1 to X5 is the minimizer of
KL KL (L())1++1((Xx-i))) ((xx)())))))),,,
(3.7)
where Ali+1 is a mean-field field Gaussian approximation with parameters yp == (jr,)) E RRds x R.y
X, is drawn from X (X, (+IX,+1), where (X)(X)+1) is minimizer of the proxy of (3.7).
In the following, we elaborate more on Step and Step 2 and discuss the choice of the intermediate potentials. The pscudo-code of the DCPS algorithm is in Algorithm 1.
Sampling the initial distribution. In order to perform Step 1, we use the discretized Langevin dynamics [38] with the estimate V loggü
d. + & 8kell of the score V log of e This estimate results from the use of 8 as an approximation of V log in combination with the approximate potential (3.6). We then obtain the approximate sample X²2 of Tk.=, by running M steps of the tamed unadjusted Langevin (TULA) scheme [5]; see Algorithm 1. Here, the intractability of the involved densities hinder the usage of the Metropolis-Hasting corrections to reduce the inherent bias of the Langevin algorithm.
5

---

Sampling the transitions. We now turn to Step 2. Given X,+1, we optimize the following estimate of Equation (3.7), where we simply replace 9j" by the approximation (3.6):
-f fLoR (12)) 11b+1 (2g (1++)) dr, + 144
Py1s+1 (1ag+))))))))
Letting 2 J1 (1y) = N(ry; Pj. diag(e :)), where the variational parameters AJ. ūg are in R.d..
the previous estimate yields the objective
C) 051 == -B[ [ogg (es + e
[iū (1144((13+111
dz
(3.8)
51i+1
2
1=1
51i+1
where Z is de- dd-dimensional standard Gaussian and 2 (25+1) is the mean of (2.2). Note here that we have used the reparameterization trick [26] and the closed-form expression of the KL divergence between two multivariate Gaussian distributions. We optimize the previous objective using a few
steps of SGD by estimating the first term on the r.h.s. with a single sample as in [26]. For each j E [kk, k - 1I] we use Pjli+1 and log o +12+1 as initialization for AJ and 83.
Intermediate potentials. Here, we give general guidelines to choose the user-defined potentials (9h, ) Our design choice is to rescale the input and then anneal the initial potential go. Therefore, we suggest
9ke (z) = 90 Au. yTee
(3.9)
where Thee 3kz > 0 are tunable paramerters. This design choice is inspired from the tempering sampling scheme [33] which uses the principle of progressively moving intial distribution to the targeted one. We provide some examples in the case of Bayesian inverse problems where the modelled jointly
unobserved signal and the observation
realization of Y) ~ p(y) ()oo))))())) where p(y x:) is the conditional density of Y given X = x. In this case, the posterior To of X given Y = is is given by (2.3) with go(x) p(ylx))
Linear inverse problems with Gaussian noise. In this case, go(x) N(y; Ax, o where A E Rdd, Popular applications in image processing include super-resolution, inpainting, outpaint- ing, and deblurring. We use (3.9) with (Ste: = (Vake (ik,).
Ik. (x) N(Vor,, Ax, o(
(3.10)
which corresponds to the likelihood of x given the pseudo observation /ag,y/ under the same linear observation model that defines 90- This choice of Is, enables exact computation of (3.6) and allows information on the observation y to be taken into account early in the denoising process.
Low-count (or shot-noise) Poisson denoising. In Poisson model for an image, the grey levels of the image pixels are modelled as Poisson-distributed random variables. More specifically, let A E IRd, be a matrix with nonnegative entries and æ E [0. 255) xx where C' is the number of channels and H the height and W the width. For every E d.J. Y; is Poisson- distributed with mean (Az), and the likelihood of given the observation is therefore given by I + - (AAx)): e -(xAA)/ //y! where >> is the rate. Following [10] we consider as likelihood its normal approximation, i.e. 90 III dy N(y5; X(Ax)j. v2). This model is relevant for many tasks such as low-count photon imaging and computed tomography (CT) reconstruction [35, 39, 31j. We
use (3.9) with BR, The V
dy Ih, (x) = II N( A(Ax),, Van.ls).
(3.11)
==1 JPEG dequantization. JPEG [57] is ubiquitous method for lossy compression of images. Use hy to denote the JPEG encoding function with quality factor q E [o, 100], where a small is associated with high compression. Denote by hJ the JPEG decoding function that returns an image in RGB space with certain loss of detail, depending on the degree of compression g. compared to the original image. Since we require the potential to be differentiable almost everywhere, we use the differentiable approximation of JPEG developed in [44], which replaces the rounding function used in the quantization matrix with a differentiable approximation that has non-zero derivatives almost everywhere. In this case, (r) = N(hi, (h,( (z)),, where y is in YCbCr space. Combin- ing this with Equation (3.9) with (3kz 7h,) = (ark, ; (x2)) and assuming that the composition ht by is a homogenious map, the intermediate potentials are 9k, (x) N(yaa, ht)()): hī (hg (x)), l.....

---

4 Experiments
DCPS
DDRM
DPS
HIGDM
REDDIFF
MCGDIFF
Figure I: First two dimensions of samples (in red) from each algorithm on the 25 component Gaussian mixture posterior sampling problem with (da,dy) = (100, 1). The true posterior samples are given in blue.
In this section, we demonstrate the performance of DCPS and compare it with DPS [10], HIGDM [47], DDRM [24], REDDIFF [32], and MCGDIFF [7] on several Bayesian inverse problems. We also benchmark our algorithm against DIFFPIR [62]. DDNM [58], FPS [16], and SDA [42] but we defer the results to the Appendix C.5.
First, we consider a simple toy experiment in which the posterior distribution available in closed form. Next, we apply our algorithm to superresolution (SR 4x and 16x), inpainting and outpainting tasks with Gaussian and Poisson noise, and JPEG dequantization. For these imaging experiments, we the FFHQ256 [23] and ImageNet:256 [14] datasets and the publicly available pre-trained models of [8] and [15]. Finally, we benchmark our method on a trajectory inpainting task using the pedestrian dataset UCY for which we have trained a Diffusion model. All details can be found in Appendix C.I.
Gaussian mixture. We first evaluate the accuracy of DCPS on a linear inverse problem with Gaussian mixture (GM) prior, for which the posterior can be explicitly computed: is also Gaussian mixture whose means, covariance matrices, and weights are in a closed form; see Appendix C.2. In this case, the predictor a is available in closed form; see Appendix C.2 for more details. We consider a Gaussian mixture prior with 25 components in dimensions de = 10 and d₂ 100. The potential is (x) N(y; Ax, of Ia,) with dy = 1 and A is a 1 x dz vector. The results are averaged over 30 randomly generated replicates of the measurement model (y, A, ..)) and the mixture weights. Then, for each pair of prior distribution and measurement model, we generate N, 2000 samples with each algo- rithm and compare them with N, samples from the true posterior distribution using the sliced Wasserstein (SW) distance. For DCPS, we used L 3 blocks and K = 2 gradient steps, respectively, and compared two configurations, denoted by DCPS and DCPS of the algorithm with M = 50 and M = 500 Langevin steps, respectively. See Algorithm The results are reported in Table 1. It is worthwhile to note that DCPS outperforms all baselines except for MCGDIFF. However, by increasing the number of Langevin steps, its performance closely matches that of MCGDIFF.
Table 1: 95% confidence interval for the SW on GM experiment.
d, 10.
d, 100,d,
DCPS;0
2.91 0.74
4.04 + 1.00
DCPS
2.19 0.68
3.29 = 0.95
DPS
5.80 0.75
5.68 + 0.73
DDRM
0.77
5.70 0.78
HIGMM
4.23 4.90
4.61 + 0.68
REDDIFF
6.36 1.27
7.47 = 0.87
MCGDIFF
2.28 0.75
2.83 0.71
Imaging experiment. Table 2 reports the results for the linear inverse problems with Gaussian noise with two noise variance levels oy = 0.05 and o, = 0.3, Table 3 for the JPEG dequantization problem with Ty = 10-3 QF E {2,8). and Table for the Poisson denoising task with rate 0.1. For all tasks and datasets, we use the same parameters for DCPS and therefore do not perform any task or sptaset- tuning. We use L. 3, K = gradient steps, and M I Langevin steps. To ensure a fair comparison with DPS and ITGDM we use 300 DDPM steps for DCPS and 1000 steps for both DPS and IIGDM, which ensures that all the algorithms have the same runtime and memory footprint; see Table 4. For MCGDIFF, which has large memory requirement, we use N 32 particles in the SMC sampling step and then randomly draw one sample from the resulting particle approximation of the posterior. Finally, for DDRM we use 200 diffusion steps and for REDDIFF we use 1000 gradient steps and the parameters recommended in the original paper. We provide the implementation details for all algorithms in Appendix C.I.
7

---

Oberrvaion
DCPS
DDRM
DPS
TGGD
RenDue
MCGDar
DCPS
EDRM
DPS
FICD
RenDer
MCGDiT
Figure 2: Sample images for inpainting with center, half, expand masks and for Super Resolution with 4x and 16x factors. On the left: FFHQ dataset and on the right ImageNet dataset.
For the JPEG dequantization task, we use By = 10-3 and À = 0.1. We only benchmark our method against JIDDM and REDDIFF, since MCGDIFF and DDRM do not handle non-linear inverse problems. We did not include DPS in our benchmark because we have not managed find a suitable choice of hyperparam- eters achieve reasonable re- sults. Finally, for the Poisson- shot noise case, we compare against DPS. We use the step size for super-resolution recom- mended in the original paper [see 10, Appendix D.IJ, and found, via grid search, that the same value is also effective for the other tasks.
Table 2: Mean LPIPS value on different tasks. Lower better.
Dataset /,
DCPS
DDRM
DPPS
IIGD
REDDIE
MCGDII
Half
0.20
0.25
0.24
0.26
0.28
0.36
Center
0.05
0.06
0.07
0.19
0.12
0.24
PFRQ/0.0
SR 4x
0.09
0.18
0.09
0.33
0.36
0.15
SR 16x
0.44
Half 0.25
0.30
0.31
0.64
0.76
0.80
FFHO /D3
Center
0.10
0.21
0.13
0.19
0.11
0.77
0.62
0.75
0.65
0.55
SR 16x
0.35
0.41
0.43
0.64
0.74
0.52
Half 0.35
0.10
0.41
0.38
0:14
0.83
0.45
Tragalwe /
SR 4x
0.24
0.38
0.41
0.78
0.56
1.32
SR 10x
0.44
0.72
0.50
0.60
0.83
1.33
Half
0.40
0.46
0.48
0.82
0.76
0.86
Imagellet /0.3
Conter
SR 4x
0.34
0.43
0.25
0.30
0.40
0.47
0.68
0.87
0.71
0.83
0.47
1.31
SR 16x
0.72
0.77
0.57
0.72
0.92
0.67
Average
0.32
0.57
0.60
0.67
Evaluation. As shown in Table 2, DCPS outper- forms the other baselines on 13 out of 16 tasks and has the best average performance. ticular, it compares favorably with IIGDM and DPS, its closest competitors, while exhibiting the same runtime and memory requirements; see Ta- ble 4, where memory usage for each algorithm. The mem- ory consumption is measured by how many ples each algorithm can generate in parallel on single 48GB L40S NVIDIA GPU for the Diffusion model trained FFHQ [15]. We emphasize that DCPS is more robust to larger noise levels than HIDM and REDDIFF, as evidenced by the large increase in the LPIPS value for these algorithms in the o, = 0.3. On the JPEG dequantization task (Table 3), DCPS also shows better performance than these algorithms and even more for the high compression level (QF- = 2). On the Poisson-shot noise tasks, DCPS outperforms DPS by significant margin; see Table 6. Finally, we display various reconstructions obtained with each algorithm. More specifically, we have generated 4 samples each, with the same seed. Figure 2 displays the first sample and the remaining ones are deferred to Appendix D. For MCGD1FF we show random samples of the same particle filter. Due the collapse of the particle filter in very large dimensions [2], they are all similar. Surprisingly, the samples produced by DDRM and REDDIFF for the outpainting tasks also show striking similarities, although the samples have been drawn independently.
Table 3: Mean LPIPS value on JPEG dequanti- zation.
In par-
Dataset
Task
DCPS
HIGMM
REDDIFF
QF 00=2
0.20
0.37
0.32
FFHQ
0.08
0.18
give the average runtime and
Imagelet
QF
0.44
0.93
0.50
QF
0.24
0.95
0.31
8

---

DCPS
HIGD
Obsevation
DCPS
Cbuznatic
DCPS
Figure 3: Left: JPEG dequantization with QF Middle: Poisson denoising. Right: SR 4x Poisson denoising.
Trajectory prediction. We evaluate our algorithm on the UCY dataset consisting of pedestrian trajecto- rics, encoded as 2D time series with 20 time steps [27, 29, 18, 30J. We pre-train trajectory model this dataset and then use for trajectory reconstruc- tion tasks. The model architecture and implementation are detailed in Appendix C.4. We focus on the com- pletion of trajectories where only few timesteps are observed. The missing steps are filled in based on the observations and the pre-trained prior model, similar to the inpainting task in the previous section. We use MCGDIFF with 5000 particles to obtain approximate samples from the posterior. Indeed, as the dimension of the observation space low (d. 40) and MCGDIFF is asymptotically exact as the number of particles tends infinity, it yields an accurate approximation of the posterior; see [7, Proposition 2.1]. Then, we compute the fz distance between the median. quantile 25, and quantile 75 of the MCGDIFF samples and the recon- structions of each algorithm. We report these results in Table 5. Finally, in Figure 4 we illustrate the recon- structed trajectories on a specific trajectory completion problem.
(ours) DDRM
RunDer
0.4
100
200
25
65
Rumime (S)
Mat. samples per GPU
Table 4: LPIPS metric against the runtime and memory cost the algorithms.
Table 5: & distance quantiles with MCGDIFF as reference.
D.006
0.01
950
225
G75
950
Q25
677
DPS
1.34
1.36
1.48
DDRM
1.48
1.46
1.61
1.59
1.62
1.61
IIDM
1.36
1.35
1.37
1.42
REDDIN
1.67
1.57
1.56
Reconsiruction
Groundiruth
MCGDiFF
DCPS (ours)
DDRM
DPS
IIDDM
REDDIFF
time stpps
Figure 4: Trajectory completion where only the middle part of the trajectory is observed. The figures in the 1s display 3 reconstructions per algorithm. The 2 and 3d show confidence intervals across different time steps. The Groundtruth is trajectory taken from the UCY datasct.
5 Conclusion.
In this paper, we introduce DCPS to handle Bayesian linear inverse problems with DDM priors without the need for problem-specific additional training. Our divide-and-conquer strategy helps to reduce the approximation error of existing approaches, and our variational framework provides

---

principled method for estimating the backward kemels. DCPS applies to various relevant inverse problems and is competitive with existing methods.
Limitations and future directions. Our method has some limitations that shed light on opportu- nities for further development and refinement. First, the intermediate potentials that we considered were specifically designed for each problem, meaning our method is not universally applicable to all inverse problems. For instance, our approach can not applied to for linear inverse problems using latent diffusion models [41] since there is no clear choice of intermediate potentials. Therefore, in our opinion, deriving a learning procedure that is capable to automatically design effective intermediate potentials applicable to any 9o is an important research direction. Moreover, there is aspect of the choice of the intermediate potentials and the number of blocks L that remains to be understood properly. Indeed, while our backward approximations reduce the local approximation errors w.r.t DPS and IIGDM; nonetheless DCPS requires appropriate intermediate potentials in order to perform well. DCPS still provide decent performance with irrelevant intermediate potentials as long as the number of Langevin steps, in-between the blocks, is large enough. Finally, although our method provides decent results with the same computational cost as DPS and IIGMM, it remains slower than REDDIFF and DDRM which which do not compute vector-jacobian product over the denoiser. Therefore, overcoming this bottleneck when optimizing the KL objective would be significant improvement for our method.
Acknowledgments. The work of YJJ. and B.M. has been supported by Technology Innovation Institute (TII), project Fed2Learn. The work of Eric Moulines has been partly funded by the European Union
1601). Views and opinions expressed of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.
however those
10

---

References
[1] Georgios Batzolis, Jan Stanczuk, Carola-Bibiane Schönlieb, and Christian Etmann. Conditional image generation with score-based diffusion models. arXiv preprint 0rXiv:2111.13660 2021.
[2] P. Bickel, B. Li, and T. Bengtsson. Sharp failure rates for the bootstrap particle filter in high dimensions. In B. Clarke and S. Ghosal, editors, Pushing the Limits of Contemporary Statisties: Contributions in Honor of Jayanta K. Ghosh, pages 318-329 329.. Institute of Mathematical Statistics, 2008.
[3] Christopher M. Bishop. Pattern Recognition and Machine Learning (Information Science and Statistics). Springer-Verlag, Berlin, Heidelberg, 2006.
[4] Benjamin Boys, Mark Girolami, Jakiw Pidstrigach, Sebastian Reich, Alan Mosca, and O Deniz Akyildiz. Tweedie moment projected diffusions for inverse problems. arXiv preprint arXiv:2310006221, 2023.
[5] Nicolas Brosse, Alain Durmus, Éric Moulines, and Sotirios Sabanis. The tamed unadjusted langevin algorithm. Stochastic Processes and their Applications, 129(10):3638-366) -666633888666,--- 2019.
[6] Daniela Calvetti and Erkki Somersalo. Inverse problems: From regularization to Bayesian inference. Wiley Interdisciplinary Reviews: Computational Statistics, 10(3))e1427, 2018.
[7] Gabriel Cardoso, Yazid Janati, Fric Moulines, and Sylvain Le Corff. Monte carlo guided denoising diffusion models for bayesian linear inverse problems. In The Twelfth International Conference on Learning Representations, 2024.
[8] Jooyoung Choi, Sungwon Kim, Yonghyun Jeong, Youngjune Gwon, and Sungroh Yoon. IIvr: Conditioning method for denoising diffusion probabilistic models. arXiv preprint arXiv:2108. 0293008 2021.
[9] Nicolas Chopin, Omiros Papaspiliopoulos, et al. An introduction to sequential Monte Carlo, volume 4. Springer, 2020.
[10] Hyungjin Chung. Jeongsol Kim, Michael Thompson Mccann, Marc Louis Klasky, and Jong Chul Ye. Diffusion posterior sampling for general noisy inverse problems. In The Eleventh Interna- tional Conference on Learning Representations, 2023.
[11] Hyungjin Chung, Byeongsu Sim, and Jong Chul Ye. Come-closer-diffuse fasteff Accelerating conditional diffusion models for inverse problems through stochastic contraction. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 12413-12422, 2022.
[12] Masoumeh Dashti and Andrew M. Stuart. The Bayesian Approach to Inverse Problems, pages 311-428. Springer International Publishing, Cham, 2017.
[13] Pierre Del Moral. Feynman-kac formulae. In Feynman- Formulae, pages 47-93. Springer, 2004.
[14] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pages 248-228 255. Ieee, 2009.
[15] Prafulla Dhariwal and Alexander Nichol. Diffusion models beat gans on image synthesis. Advances neural information processing systems, 34:8780-8794 2021.
[16] Zehao Dou and Yang Song. Diffusion posterior sampling for linear inverse problem solving: A filtering perspective. In The Twelfth International Conference on Learning Representations, 2024.
[17] Mare Anton Finzi, Anudhyan Boral, Andrew Gordon Wilson, Fei Sha, and Leonardo Zepeda- Núñez. User-defined event sampling and uncertainty quantification in diffusion models for physical dynamical systems, International Conference on Machine Learning, pages 10136- 10152, PMLR, 2023.

---

[18] Tianpei Gu, Guangyi Chen, Junlong Li, Chunze Lin, Yongming Rao, Jie Zhou, and Jiwen Lu. Stochastic trajectory prediction via motion indeterminacy diffusion. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 17113-17122 2022.
[19] Bichuan Guo, Yuxing Han, and Jiangtao Wen. Agem: Solving linear inverse problems via deep priors and sampling. Advances in Neural Information Processing Systems, 32, 2019.
[20] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 33:6840-6851, 2020.
[21] Aapo Hyvärinen, Some extensions of score matching. Computational statistics & data analysis, (((5):249-2511, 2007.
[22] Bowen Jing, Gabriele Corso, Renato Berlinghieri, and Tommi Jaakkola. Subspace diffusion generative models. In European Conference on Computer Vision, pages 274-289. Springer, 2022.
[23] Tero Karras, Samuli Laine, and Timo Aila. A style-based generator architecture for generative adversarial networks. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 4401-4410, 2019.
[24] Bahjat Kawar, Michael Elad, Stefano Ermon, and Jiaming Song. Denoising diffusion restoration models, Advances in Neural Information Processing Systems, 35:23593-23606, 2022.
[25] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization.
[26] Diederik P Kingma and Max Welling, Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114, 2013.
[27] Alon Lerner, Yiorgos Chrysanthou, and Dani Lischinski. Crowds by example. In Computer graphics forum, 2007.
[28] Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. arXiv preprint arXiv:1608.03900 039833388880......0 2016.
[29] Karttikeya Mangalam, Yang An, Harshayu Girase, and Jitendra Malik. From goals, waypoints & paths to long term human trajectory forecasting, In IEEE/CVF, 2021.
[30] Weibo Mao. Chenxin Xu, Qi Zhu, Siheng Chen, and Yanfeng Wang. Leapfrog diffusion model for stochastic trajectory prediction. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5517-5526, 2023.
[31] Willem Marais and Rebecca Willett. Proximal Proximal-gradient methods for poisson image reconstruc- tion with bm3d-based regularization. In 2017 JEEE 7th International Workshop on Computa- lional Advances in Multi-Sensor Adaptive Processing (CAMSAP), pages 1-5. IEEE, 2017.
[32] Morteza Mardani, Jiaming Song, Jan Kautz, and Arash Vahdat. A variational perspective solving inverse problems with diffusion models. In The Twelfth International Conference on Learning Representations, 2024.
[33] Radford M Neal. Annealed importance sampling. Statistics and computing, 11: 11:125-139, 2001.
[34] Alexander Quinn Nichol and Prafulla Dhariwal. Improved denoising diffusion probabilistic models, In International conference on machine learning, pages 8162-8171. PMLR, 2021.
[35] Robert D Nowak and Eric D Kolaczyk. A statistical multiscale framework for poisson inverse problems. IEEE Transactions on Information Theory, 46(5): 1825, 2000.
[36] Xingang Pan, Xiaohang Zhan, Bo Dai, Dahua Lin, Chen Change Loy, and Ping Luo. Exploiting deep generative prior for versatile image restoration and manipulation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(11):7474 2021.
[37] Michael K Pitt and Neil Shephard. Filtering via simulation: Auxiliary particle filters. Amer. Statist. Assoc., 94(446))590-590) 1999.
12

---

[38] Gareth O. Roberts and Richard L. Tweedie. Geometric convergence and central limit theorems for multichmensional Hastings and Metropolis algorithms. Biometrika, 83:95-110, 1996.
[39] Isabel Rodrigues, Joao Sanches, and Jose Bioucas-Dias. Denoising of medical images corrupted by poisson noise. In 2008 15th IEEE international conference image processing, pages 1756-1759. IEEE, 2008.
[40] Yaniv Romano, Michael Elad, and Peyman Milanfar. The little engine that could: Regularization by denoising (red). STAM Journal on Imaging Sciences, 1044):1804-184, 2017.
[41] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Bjöm Ommer. High- resolution image synthesis with latent diffusion models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages
2022.
[42] Franccois Rozet and Gilles Louppe. Score-based data assimilation. Advances in Neural Information Processing Systems, 36:40521-40544 2023.
[43] Chitwan Saharia, Jonathan Ho, William Chan, Tim Salimans, David Fleet, and Mohammad Norouzi. Image super-resolution via iterative refinement. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(4):4713-477 2022.
[44] Richard Shin and Dawn Song. Jpeg-resistant adversarial images. In NIPS 2017 workshop on machine learning and computer security, volume 1, page 8, 2017.
[45] Jascha vised learning using nonequilibrium thermodynamics. International Conference on Machine Learning, pages 2256-2265. PMLR, 2015.
Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsuper-
[46] Jiaming Song. Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. In International Conference on Learning Representations, 2021.
[47] Jiaming Song, Arash Vahdat, Morteza Mardani, and Jan Kautz. Pseudoinverse-guuee diffusion models for inverse problems. In International Conference on Learning Representations, 2023.
[48] Jiaming Song, Qinsheng Zhang, Hongxu Yin, Morteza Mardani, Ming- Yu Liu, Jan Kautz, Yongxin Chen, and Arash Vahdat. Loss-guided diffusion models for plug-and -and controllable generation. In International Conference on Machine Learning, pages 12483-32499 PMLR, 2023.
[49] Yang Song, Conor Durkan, Iain Murray, and Stefano Ermon. Maximum likelihood training of score-based diffusion models. Advances in Neural Information Processing Systems, 34:1415- 1428, 2021.
[50] Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in neural information processing systems, 32, 2019.
[51] Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. arXiv preprint arXiv:2011. 2020.
[52] Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. In International Conference on Learning Representations, 2021.
[53] Andrew M Stuart. Inverse problems: 2010.
Bayesian perspective. Acta numerica, 19:451-559,
[54] Brian L. Trippe. Jason Yim, Doug Tischer, David Baker, Tamara Broderick, Regina Barzilay, and Tommi Jaakkola. Diffusion probabilistic modeling of protein backbones 3d for the motif- scaffolding problem. In The Eleventh International Conference on Learning Representations, 2023.
[55] Dmitry Ulyanov, Andrea Vedaldi, and Victor Lempitsky. Deep image prior. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 9446-9454, 2018.
13

---

[56] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
[57] Gregory K Wallace. The jpeg still picture compression standard. IEEE transactions consumer electronics, 38(1): -xxiv, 1992.
[58] Yinhuai Wang, Jiwen Yu, and Jian Zhang. Zero-shot image restoration using denoising diffusion null-space model. In The Eleventh International Conference Learning Representations, 2023.
[59] Luhuan Wu, Brian L. Trippe, Christian A Naesseth, John Patrick Cunningham, and David Blei. Practical and asymptotically exact conditional sampling in diffusion models. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[60] Guanhua Zhang, Jiabao Ji, Yang Zhang, Mo Yu, Tommi Jaakkola, and Shiyu Chang. Towards co- herent image inpainting using denoising diffusion implicit models. In International Conference on Machine Learning, pages 41164-41199 PMLR, 2023.
[61] Richard Zhang, Phillip Isola, Alexei A Efros, Eli Shechtman, and Oliver Wang. The unrea- sonable effectiveness of deep features as perceptual metric. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 586-595, 2018.
[62] Yuanzhi Zhu, Kai Zhang, Jingyun Liang, Jiezhang Cao, Bihan Wen, Radu Timofte, and Luc Van Gool. Denoising diffusion models for plug-and-play image restoration. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1219-1229, 2023.
14

---

A Methodology details
A.1 Denoising Diffusion models
DDMs learn a sequence (z) of denoisers by minimizing, using SGD, the objective
w, [ller - (o + VI- [1?]
(A.1)
w.r.t. the neural network parameter 0, where (ee)==1 are i.i.d. standard normal vectors and (w; (w;){=1 are some nonnegative weights. We denote by H* an estimator of the minimizer of the previous loss. Having access 9", we can define generative model for Paun- Let (t& /=o be an increasing sequence of time instants in [O. T7 with tu = 0. We assume that i, is large enough so that 4.,, is approximately multivariate standard normal. For convenience, we assign the index & to any quantity depending on 4as e.g., we denote pt, by Pk. For kj, E [1, 1J2 such that j < ki define
(20, xb)) == Vay ax/aa))
VOL /ax/ay/ 0t)) 2k.
20 +
(A.2)
1 1-a2 ai
- 0.1
(1 - (1)) an/aa)
(A.3)
-ax
Then the bridge kernel
(3 sra) = (010(1y (o))) (
(A.4)
is a Gaussian distribution with mean (zo and covariance 3 Idz. DDPM [20] posits the following variational approximation
pb.. (Jom) = P,, (T.))
PhI (#xx (xa)) k=
II
where P (2x(2x+11) In (at -0 (I #*+1) and p (1122) 6sg, (m1) An effi- cient generative model is then obtained by plugging in the parameter 0*
A.2 Further details on DCPS
In this section we provide further details on Steps and 2 detailed in the main paper. The complete algorithm is given in Algorithm 1.
Tamed unadjusted Langevin. For the tamed unadjusted Langevin steps we simulate the Markov chain (X,) where
X -+==8,+70" (X,) 2272, X. X + 1,
(A.5)
and M-1 obtained from the previous iteration of the algorithm, and for all pdd and y >
(o are i.i.d. diddinnnsionnl standard normal, X₂ + 1 is an approximate sample from 7t+1
V log of (I) (xr)
GZ(a))=
(A.6)
1 1+ log (z) (z) + 8 (x)
We then set X = XAs, which serves as an initialization of the Markov chain Step 2.
Potential computation. In order to perform the tamed Langevin steps and to optimize the variational approximation using the criterion (3.8), it is crucial to be able to compute exactly the potential (3.6). The optimal potentials have proposed for both linear inverse problems with Gaussian noise (3. and low-count Poisson denoising (3.11) (for > 0) are available a closed form:
(x,) N(var y, (z)) 21)
(A.7)
15

---

where
Σj ois + oglds
(Linear inverse problem)
- = o + Vardiag(y), t>0,
(Poisson-shot noise)
May(oy) == ( (zz), (z)), and oă is defined in (A.2). As a result, the first term of the
variational criterion [(ú 0ji xj+1) in (3.8), given by
E log of. (0, + e 2 2) f log (x,) (1))
Aitt1 (ry (r dry,
be computed exactly. Indeed, Melj is linear function of Ty, this expectation is simply that of quadratic function under a Gaussian density, given by
E log "j "f
(Øs + "0,
= - VI Ape
+ + +C.
Hence, for these cases, (3.8) has closed-form expression. However, it involves the computation of an inverse matrix which, for many problems, can be prohibitively expensive. To avoid this inversion, instead optimize biased estimate of Lş 05; obtained by drawing two noise vectors (Z, Z') N(Oa,, la.) and setting
(,g, 05) = - log gelee (Mg + e, + oi
|0, - Pili+1 1 (2++1) 11
d=
(A.8)
20
This estimator computable for any choice choice of potential and we have found in practice that is sufficient to ensure good enough performance for our algorithm. Regarding the tamed unadjusted Langevin steps, we use the same biased estimate when the matrix inversions are expensive to compute; i.e. at each Langevin step, we approximate G (Xx) by
V log ge (#141) + T2 2x) + 8p41 (Iz +
(A.9)
Vee+1 log (e + 0e 2x) + 8641 (It + 1)1l
Algorithm DIVIDE-AND-CONQUEE POSTERIOR SAMPLER (DCPS)
Input: timesteps (ke) learning-rate C, numbers K and M of gradient and Langevin steps, respectively.
Initial sample Xkg. ~ ~N(Od,, Ta.); for &. = I, 1 to 0 do
Draw 7 ~ -N((0,, Id.)) and compute G. (X (X (A.9);
X k + -Xki
for == to M do
Z N(Od,,, Id,);
Xhet: + X ki- + +G keas) 2277
end for
for ki+1
to ki do B + M1))+1 (Xf+1);
úg t log o1s+1 14,;
for r 1 to K do
Draw (Z, 7')
N(Oa,, Ia,)) and compute Ey(0i 0y; X x (A.8);
<II (n X5111 (, 03; x
end for
8 &~ N la.)
x² + My + d
end for Xk. Xx; end for
16

---

A.3 Proof of Proposition 3.1
For all [0, 1] we denote by 91tk+1 (Tt [K+11) the exact backward kernel which satisfies
(((e==1))000+000110 (z (x+1) = qu (2x (x*))x+11 ija (2k+1|
(A.10)
Note that the backward kernels PaJK+1 are to be understood as Gaussian approximations of the true backward kernels 4N|R+1- Below we give complete statement of the proposition and provide proof.
Proposition A.1. Let k E [1. Assume that 4x|k+1 (#x|=R+1) Pk|K+1 (2e()&+1) for all (zk, (R+1) E (RR)). For all 8 [0, 1] and I& RR,,,
W2(Deju Pelk (-(((11xx)) 2 Vaz(11 ax//ae) (e((Pop(((xx)) Poja Poja (-1x=))
Proof of Proposition A.I. Under the assumptions of the proposition, we have, for all m >> t
Pela (xel())) = ()(o(() f gejo, (1re 2x) quie (dro qujje (ax).
Indeed, by definition of the backward kernel 9n ( (xx) and (A.10), it holds that
J Aaoooelee ro, a. Mopie (ro (ra) dor
/
aoja Tojo (mj to (x0))) (2)) aajo (Ix (m0)
dzo
4A (3
ʃ (00(00))))(())) dro (x1))
gx(2x))
(x
As result, we have that
(x)(()))())) = / ae a,s (dure .ro, Ia Moja (zo (mx)) dro.
(x)l()))) le o. (dwr//oo v ) (20) dro.
where, by definition, Pope (-1zx) is Gaussian approximation of aoja (+|zx) as defined in the main paper.
Next, let Toja (-1are) denote a coupling of qo ( (-12x) and Poj ( (xx), i..., for all A E B(R*.),
/ (z(z)) (p): (0o) H1 a (zo, 2o xx) dzodio / 1 1 901u (zo (rx) dro.
[ ILv.. (20) (oo) 11 (zo, to x dxodio = / 1 A ( Poja (6o xxx) dêo
Consider then the random variables
Xajs = var(1 04/04))
Nojk + v onk /as/ar(1 - aae)
(1 -a=) - aa//ee)
26 +
Z,
1 - akk
1 1-
v1 az
xA var(1 wx/(x))
/an/cur(1 - ar)
oz) aa//a))
Xojs +
7
a
1 ax
v1 O'k
where (Xojkz X01k) (+2x))) and 2 NNOa, Ta.). Then (Xeje: Xex) is distributed according to coupling of Peja (-120)) and Pena (+12x), and consequently
W, (1 (2xx) E | Xz 1P]
1/2
Varl an/(xr))
Nooo 1/2
E
[|
(1 (1-ax) a4)
The result is obtained by taking the infinimum of the rhs with respect to all couplings of oojk ( (-12%) and Pojx (-12z))
17

---

B Related works.
In this section we discuss in more details existing works that bear some similarities with DCPS.
SMC based approaches. The MCGDIFF, the Twisted Diffusion sampler (TDS) of [59] using the FK representation (2.4). MCGDIFF is specific to linear inverse problems and the potentials used are 9g (2a) = N( ((ya Arx, (1 - [a,) when o, 0. TDS applies to any potential In and relies on the DPS approximation for its potentials; i.e. gr = go foo (zx)). either cases, a particle approximation of the posterior of interest To is obtained using the Auxiliary Particle filter framework [37]. [16] also use particle filters for the posterior distribution; the potentials used are (zx)) /ky Ark, axo))a.) where (yx) )==. with go y is sequence of observations sampled according to an auto-regressive process; see [16, Equation 7]. The posterior is thus viewed as approximately the time 0 marginal of a Hidden Markov model with transition PœJк+1 and observation likelihood 9g- which is different from the FK representation (2.4). Our choice of intermediate potentials for linear inverse problems with Gaussian noise differs from that of MCGDIFF by the standard deviation of the observation model, which we set to be oy. A major difference of DCPS with these works lies in the fact that we do not rely on particle filters, thus avoiding the collapse in very large dimensions. As we have shown in the experimental section DCPS can achieve comparable performance to MCGDIFF in low dimensions, see Table while also being efficient in very large dimensions, see Table 2. A second and major difference is that we have derived potentials for both the JPEG dequantization and Poisson-shot denoising tasks, which may be used to extend MCGDIFF and FPS-SMC [16] to these problems.
RedDiff. In this work we have also proposed to use Gaussian variational inference to approximate the intractable backward transition of "k One particularity of our approach is that we do not use amortized variational inference [26] and instead optimize the variational distribution at each step of the diffusion. A similar approach is used in REDDIFF [32] but in a different way. Indeed, the authors use non-amortized Gaussian variational approximation for the posterior Ty. meaning that in order to draw one sample from REDDIFF, several steps of optimization are performed on a score- matching -iikinngggkee//ie loss. Interestingly, this approach does not require differentiating through the denoising network and is thus faster and more memory efficient. However, we found that this comes at the cost of performance as can be seen in Table 1, and 3.
SDA. In [42], the authors introduce a posterior sampling algorithm for inverse problem where the chosen potential approximation is
9 = ((y A&g oz 711 7 AA7),
with y > 0 being a tunable parameter. Noteworthy, this potential is similar to one used in [47] with slightly different choice of variance. Then, the Score-based Data Assimilation (SDA) algorithm proceed following the Predictor- Correccor framework [51]. In the Prediction stage, a sample X given X is drawn using the conditional score
5++1(2411)
log (141(1141) + V log 1oggg++1220 (
In the Correction stage, a Langevin MC targeting the marginal distribution g& (xx))x (æx) is simulated starting from the predicted sample following
x ri+1 = X & + 20x
~ N),,
where 6 is state-dependent step-size. We emphasise that due to the dependence of the step sizes on the states, these are only Langevin-like updates that do not inherit the theoretical guarantees of the unadjusted Langevin algorithm. While SDA and our algorithm DCPS both use Langevin, the pivotal difference is that its purpose, in our case, is not to correct to ensure that the sample Xs. is distributed according to the marginal THe (ITx) X IE, (I Pk, ( but rather to ensure that the sample is distributed according to the next distribution TT (3 which is the initial distribution of the next block, as per Equation (3.4). Hence, in our case, Langevin MC used between blocks and not within blocks.
18

---

C
Experiments
C.1 Implementation details
In this section we provide the global implementation details for each algorithm. We provide the specific parameters (when needed) used for each experiment (Gaussian mixture, image restoration and trajectory inpainting) in the dedicated sections below.
DCPS. For all the experiments we implement Algorithm 1. We use the same parameters L= 3 and Ç for all the experiments. For the number of Langevin steps, we set it to M = 50 and M 500 (respectively) for the Gaussian mixture experiment and M 5 for the imaging and trajectory inpainting experiments.
DDRM. We have used the official implementation and used the recommended parameters in the original paper. We use 200 steps for DDRM and found that it works better than when used 1000 steps.
DPS. We have implemented both Algorithm 1 (for linear inverse problems) and Algorithm 2 (for Poisson-shot restoration) given in [10]. In all the experiments we run DPS with 1000 Diffusion steps.
RedDiff. For RedDiff, we have used the publicly available implementation" We have empirically found that RedDiff works best in the low observation standard deviation regime and produces spatially coherent reconstructions in the larger noise regime but struggles with getting rid of the noise as evidenced by the large increase in LPIPS values in Table 2. Note also that it not clear how the parameters of the algorithm depend on the inverse problem standard deviation; indeed, looking at Algorithm I and then Appendix C.2 where the authors consider noisy inverse problem² there seems to be no clear dependence of À on o. (a, with our notations). In fact the authors use À = 0.25 similarly to the noiseless experiments in the main paper and we believe that the tuning is performed only on the initial step-size of Adam. As a result, for the experiments with By = 0.3, we have tuned it using grid-search 1, 0.25) and retained 0.1.
HGDM. Regarding IIGDM [47], note that there is publicly available implementation and we have thus implemented the noisy version [47, Algorithm 1] in the original paper. However, we did not manage obtain appropriate results and found it to be quite unstable. We have further investigated the issue and found that IIGDM is implemented in the github repository of RedDiff', which is by the same authors. We have noted that has slight difference with Algorithm of the TIGDM paper; the gradient term, coined g in [47, Algorithm 1], is multiplied by /0r- instead of simply /a,- We have found that this stabilizes the algorithm significantly for the linear inverse problem experiment. We use the same rescaling for the Gaussian mixture and trajectory inpainting experiment. However, even with this modification the algorith we found that IIGDM does not perform well when the noise standard deviation is large; see Table 2. For the JPEG experiment we do this rescaling we found that the algorithm remains stable.
MCGDiIT. For MCGDiff we have used the official implementation' with N = 32 particles for the imaging experiments. There are no further tuning parameters as far as we can tell.
DIFFPIR We implemented [62, Algorithm and the hyperparameters recommended in the official, released version".
DDNM. We adapted the implementation in the released code? to our code base.
htcpes//gtthab..o//bbbaatttt-e /ddm
19

---

SDA. We implement the posterior sampling algorithm by combining [42, Algo and 4 in Appendix CJ. In the experiments, we use two Langevin corrections steps and found that y = 0.1 works well across problems for the diagonal approximation the same = 0.1 for the Langevin correction steps size.
FPS
We implement [16, Algorithm 2] provided in the appendix.
C.2
Gaussian mixtures
For given dimension dæ, we consider Pau a mixture of 25 Gaussian random variables, The means of the Gaussian components of the mixture are (m;). == {8ii 8j, 8i, 8j) E R (f,j) E 2-2.-1, 0, 1, 2 The covariance of each component identity. The mixture (unnormalized) weights wij are independently drawn from Dirichlet distribution.
Metries. To assess the performance of each algorithm we draw 2000 samples and compare against 2000 samples from the true posterior distribution using the Sliced Wasserstein distance by averaging over 10* slices. In Table we report the average SW and the 95% confidence interval over 30 seeds. We found DPS and I1GDM to be sometimes unstable, resulting in NaN values. To account for these unstabilities when computing the average SW distance, we replace NaN with which is the typical value obtained when stable algorithm fails to sample from the posterior.
Parameters.
For DPS we use Sm = 0.1/1ly - A& 0lm (fm)ll at step m of the Diffusion. As to
DCPS use ? 10-2 for the Langevin step-size.
Denoisers.
Note that the loss (A.1) can be written as
W/ [|le - El(VaiXo + vI=a)e)l
T
Wi
[[[V[ aie - VI aie( + vI- (1
Wi
E
|X, - VarXo - v1 ane! (x (x
X,
-I onef (Xt)
E
Xo
ai
vas
Hence the minimizer is
(2,)
Ft
04 E Xo = xxc]
which yields "g. = XX = -J. Next, by Tweedie's formula we have that
0g (x1) + (1 Vz log (xr)
Vau
Hence, since Adata is mixture of Gaussians, is also mixture of Gaussians with means (Va,,,))25 and unit covariances. Therefore, v log g, (2x) and hence ag (z.) can be computed using automatic differentiation libraries.
Measurement model. For a pair of dimensions (dz, dly) the measurement model (v, A, a.y) is drawn as follows: the elements d₂ dy elements of the matrix are drawn i.i.d. from standard Gaussian distribution, then By drawn uniformly [0, 1] and finally we draw x² Pau and (O Ia,) and set y Ax oye.
20

---

Table 6: Mean LPIPS value low count Poisson restoration.
Dataset
Task
DCPS
DPS
Denoising
0.07
0.12
FFEQ
SR 1x
0.17
0.31
Denoising SR 4x
0.17
0.24
ImageNet
0.36
0.80
Posterior. Having drawn both Pam and (y, A. oy)) the posterior can be computed exactly using
standard Gaussian conjugation formulas [3, Eq. 2. 2.116) and hence the posterior is Gaussian mixture
where all the components have the same covariance matrix E = (Idz +oy A A) and weights given by
and means
m == (ATy/o) m.)
W; x wyN(y; Am; Tyj + AAT).
C,3 Imaging experiments
Parameters. For DCPS
10-3 for the Langevin step-size. For DPS we use the parameters recommended in the original paper, which we found to work well even on the half and expand masks; see [10, Appendix D.1].
Evaluation. In order to evaluate each algorithm we compute the LPIPS metric [61] on each dataset using 100 samples from the validation sets and report the average in Table 2, and 6.
JPEG dequantization. We use the differentiable JPEG framework [44] which replaces the rounding function x + [x] used the quantization part with æ + [ar] + (2: [=])} which has non-zero derivatives almost everywhere.
C.4 Trajectory inpainting experiment
Trajectory DDM prior. The denoiser of the diffusion model has Transformer-like architecture. In the entry of the network, the trajectory is augmented to higher dimensional space (512) via dense layer. At this stage a positional encoding [56] is added to account for the diffusion step. Afterward, the output is flowed through transformer encoder [56] whose feedforward layer dimension is 2048 to learn temporal dependence within the trajectory before being feed to an MLP with 4 layers (512 + 1024 - 1024 + 512) and in between ReLU activation functions, output the added noise. A Cosine noise scheduler with 1000 diffusion steps was used [34]. The UCY-student dataset was split int train and a validation sets with 1450 and 140 trajectories respectively. The batch size was set to 10 times the training set, namely 145 samples The denoiser was trained to minimize the loss of DDPM [20] for 1000 epochs using Adam solver [25] with Cosine learning rate scheduler [28]. The training was performed on 48GB L40S NVIDIA GPU and took roughly one minute to complete.
Metrics. The trajectory completion experiment was performed on the validation set. Every trajec- tory was masked randomly. Leveraging MCGDIFF 's asymptotical approximation of the posterior, was run with 5000 particles to sample 100 samples from the posterior and afterward these were checked against a 100 reconstructions of each other algorithm by computing the timestep wise &2 distance between the quantile 50 (median), 25, 75 and also by computing the Sliced Wasserstein distance. This procedure each algorithm were aggregated by the mean Eg distances. Finally, this experiment was performed for two levels of noise oy 0.005 and oy 0.01.
repeated for all trajectories in the validation set and later the results of
C.5 Additional experiments
Here, we provide the complete tables of results on imaging and trajectories inpainting experiments that includes addition DIFFPIR, DDNM, FPS and SDA. These additional experiments were conducted during the rebuttal phase of our work.
21

---

Table 7: Mean LPIPS value on different tasks, Lower is better.
Dataset 1
Task
DCPS
DDRM
DPS
IIGD
REDDIFF
MCGDIFF
DIFFPIR
DDNM
SDA
FPS
Half
0.20
0.25
0.24
0.26
0.28
0.36
0.23
0.28
FRRQ 00.05 0.005
Center
0.05
0.06
0.07
0.19
0.12
0.24
0.06
0.05
0.05
0.09
0.09
0.33
SR 16x
0.23
0.36
0.24
0.44
0.51
0.32
0.28
0.30
0.44
0.71
Half
0.25
0.30
0.31
0.66
0.76
0.80
0,30
01.6
0.26
0.67
FFRQ
SR 4x
0.21
0.26
0.19
0.77
0.77
0.65
0.28
0.19
0.75
SR 16x
0.35
0.41
0.43
0.64
0.74
0.52
01.4
0.39
0.49
0.71
Imagellet: 0.05
Conter 0.18
0.14
0.31
0.29
0.22
0.45
0.14
0.13
0.14
0.19
SR 4x
0.24
0.38
0.41
0.78
0,56
1.32
0.36
0.34
0.85
0.27
Half 0.40
0.46
0.48
0.82
0.76
0,86
0.50
0.44
0.61
0.71
InageNet 10.3
Center
0.24
0.70
4x
0.43
0.50
0.47
0.83
1.31
0.61
0.46
1.14
0.84
SR 16x
0.72
0.77
0.57
0.72
0.92
0.67
0.76
0.75
1.19
0.74
Average Median
0.28
0.60
0.53
0.24
0.33
0.35
0.63
0.72
0.60
0.32
0.28
0.35
0.69
Table 8: & distance quantiles with MCGDIFF as reference.
0.005
By
950
q25
975
950
d25
975
DCPS
1.31
1.33
1.47
1.33
1.42
1.42
1.34
1.40
1.61
1.36
1.48
1.52
DDRM
1.48
1.46
1.61
1.59
1.62
1.61
1.37
1.43
1.42
REDDIFF
1,67
1.57
1.82
1.56
1.54
1.65
DIFFPIR
1.57
1.84
1.98
1.52
1.94
1.89
DDNM
1.45
1.45
1.65
1.52
1.59
1.59
FPS
2.60
2.61
2.62
2.91
2.90
2.89
D Sample reconstructions
In this section we display the remaining samples from the experiments in the main paper. We remind the reader that all algorithms are run with the same seed and we draw in parallel 4 samples from each algorithm and display them in their order of appearance.
Groend
O0
101
TICPS
DCPS
103
103
100
103
DPPS
Figure 5: Denoising task with Poisson noise on FFHQ.
22

---

Obaarsastio Gevenal
Gonca trath
TNCPP
Figure 6: Denoising task with Poisson noise ImageNet.
Observation Cround truta
DEPS
DO3M
EPP
MOGDE1
RinDiF
Figure 7: Outpainting task with half mask on ImageNet.
23

---

Obsersatim Goven
Gourad
DCPS
ners
TPSS
Drs
TCCDM
MoCtees
MOGDle
Reobees
Figure 8: Inpainting with box mask FFHQ.
Obseevatton Gcound trath
Obeecwatoon Goocad troth
DEPS
DODRA
TYPS
TICDAI
MOCDIFF
Figure 9: Inpainting task with box mask on ImageNet.
24

---

Obsersatiom Govend
Goucad
DCPS
ners
TPS
HCCD
MoCtees
Reobies
Figure 10: Outpainting task with half mask FFHQ.
Obseevattion Gcoond trath
Cheeewtton Goorad teoth
DEPS
DONM
mT
nenA
MOCDIF
Figure 11: Outpainting task with half mask on ImageNet.
25

---

Obseessstim Govend
trath
DCPS
ners
TISS
HCCDI
MOCTees
Renhies
Figure 12: Outpainting expend task FFHQ.
Obseevation
Gcoond trath
Obseevation Coorad troth
DEPS
DORRM
DORM
MOCDIFF
Rrotuer
Figure 13: Outpainting expend task on ImageNet.
26

---

troih
PAGPS
DCPS
DIPS
Tirs
Figure 14: SR 4x task with Poisson noise FFHQ.
Obwrrvacio Ground trath
Obeersation Grocad trith
DEPS
DORM
DORM
TIPS
DPS
MOCTEET
Figure 15: SR 4x task on ImageNett
27

---

DCPS
DePs
FIDR
DDRM
TIPS
Tifs
HenD
MOGDEE
McCDBY
Rrodies
ReoDeer
Obseevation Ground trith
Obeeewtton Grocad troth
DCPS
DCrS
DIORRA
DOnM
DVPS
MOCIDEY
MCDDET
Figure 16: SR 16x task on FFHQ.
28

---

Grorad
DOPS
TPSS
TItS
mcToN
MCGDEEI
Obocrvation Ground troth
DCTS
DV'
DCDM
MCDDE1
Figure 17: SR 16x task on ImageNet.
29

---

Obsrrvation
Geound trath
Olesewiin Grocad truih
DYPPS
RamDir
Figure 18: JPEG task with QF=8 on FFHQ
Obanevatiin Geoan trath
Olesevatim Gonaal traik
DOPS
hops
Figure 19: JPEG task with QF=2 on FFHQ
30

---

Obarrvation
Geound trath
Oleaewinm
Grocal truik
DOPS
TICDM
Figure 20: JPEG task with QF=8 ImageNet.
Obarrvsiio Geeand trath
Olesevatim
Goncal truik
DOPS
Figure 21: JPEG task with QF-2 ImageNet.
31

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The claims are clearly stated in the introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We have added limitations section.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texx system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess..
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
32

---

Justification:
All the assumptions needed are stated clearly.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We have provided the exact implementation details in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
33

---

Answer: [Yes]
Justification: We have provided a link with the relevant code as well as the link to download the datasets have used
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/ httpe//gudeee//eeeeeeee
wwwssoooooiii Policyl for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ /nips. wwtppppcccggppideeeccococcccccpe htteggguuddee//eeuniiiiiii setsSubmissinPP... ssisnssslols onoooicy)))) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: These are all given in Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We report the 95% confidence intervals for experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
34

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors Is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative emror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide the memory usage and runtime for each algorithm.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: //l::///neee /////nnuripps htc/pppulic//thhcccccdeeeeeeeeee
Answer: [Yes]
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate
35

---

to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning conrectly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We properly cite the authors that have released the datasets and models
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
36

---

Answer: [Yes]
Justification: The released code is accompanied by a README file detailing its contents, installation instructions, and usage guidelines.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
37


Reviews:
[{"review_id": "TMihFJ2ESg", "reviewer": "Reviewer_vN6C", "summary": "This paper presents a sampling algorithm (DCPS) that leverages diffusion models as priors to solve linear inverse problems. DCPS defines and recursively solves a series of intermediate inverse problems that converge to the original inverse problem. In each iteration, a sample is drawn from the next posterior distribution following a combination of Langevin dynamics and an inhomogeneous Markov chain. DCPS shows nice results in synthetic inverse problems and also image restoration tasks.", "questions": "- It is noted for the Gaussian mixture experiments that DCPS does not beat MCGDiff in terms of accurate posterior sampling. However, it outperforms MCGDiff by a large margin in image restoration tasks. What are the pros and cons of DCPS compared to MCGDiff? And what makes synthetic inverse problems and image restoration tasks so different?\n\n- Would it be possible to apply DCPS to more realistic inverse problems in other domains? What are the possible limitations of this work when adapted to more complicated inverse problems?", "limitations": "The authors address the limitations and provide possible future directions in their paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "- DCPS is well-motivated by intuition to mitigate the approximation error of the conditional distribution, which is supported by solid theoretical evidence in Proposition 3.1.\n- The experimental results on synthetic data validate the claim of accurate posterior sampling.", "weaknesses": "The experiments on images are not convincing enough. DCPS performs slightly better than DPS and DDRM, while recent works like DDNM[1], DiffPIR[2], and ReSample[3] have claimed much better posterior sampling quality on image restoration tasks but are not compared as baselines.\n\n[1] Yinhuai Wang, Jiwen Yu, and Jian Zhang. Zero-shot image restoration using denoising diffusion null-space model. ICLR, 2023.\n\n[2] Yuanzhi Zhu, Kai Zhang, Jingyun Liang, Jiezhang Cao, Bihan Wen, Radu Timofte, and Luc Van Gool. Denoising diffusion models for plug-and-play image restoration. CVPR, 2023.\n\n[3] Bowen Song, Soo Min Kwon, Zecheng Zhang, Xinyu Hu, Qing Qu, Liyue Shen. Solving Inverse Problems with Latent Diffusion Models via Hard Data Consistency. ICLR, 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer vN6C,\n\nWe would like to thank you for your time, your feedback and suggestions. We answer your questions below. \n\n**Further experiments:** We have followed your suggestion and proceeded to compare our algorithm with DDNM [1] and DiffPIR [2] on the imaging experiment. We did not compare with ReSample [3] since it is specialized for latent diffusion, which is not the focus of the present paper and is left for future work. We have also added a discussion of these papers to the manuscript. Following the suggestions of Reviewer xni9 and af3x we have also added FPS [4] and SDA [3] to our benchmark. The results can be found in the PDF in the main rebuttal. Both algorithms you suggested show strong performance, with DDNM coming second in our benchmark, and DiffPIR scoring third in terms of median performance and fourth in terms of average. Our algorithm, DCPS, still ranks first. Finally, we would like to emphasize that it ranks first or second consistently on 14 of the 16 tasks we have considered (across low and large observation standard deviation), which is not the case for any other algorithm under consideration.  \n\n**Comparison with MCGDiff:** Please note that SMC-based methods like MCGDiff heavily suffer from the curse of dimensionality. More specifically, these methods iteratively evolve a set of $N$ samples approximating the final posterior. The number of samples required to obtain a good approximation to the posterior distribution should be an increasing function of the dimension of the problem and may even grow exponentially with this quantity (see [5]),  requiring a prohibitive amount of memory. Typically, for a number of samples $N$ which has been chosen too small relative to the dimension, all samples typically collapse into a single one, so that the final posterior distribution is approximated by basically a Dirac mass.\n\nIn our high-dimensional experiments, we used 32 particles for MCGDiff, which is far from sufficient, but this was the maximal number we were able to tackle due to memory constraints. The returned approximation is therefore relatively poor. For the Gaussian mixture experiment, the dimension is low, and this is exactly the setting where MCGDiff performs best and is thus better than DCPS. Nonetheless, note that if the computational budget of DCPS is increased, it can still perform better than MCGDiff, as we show in the $10$-dimensional example. To summarize, the comparison with MCGDiff provides a convincing argument in favor of DCPS; in low dimensions it comes very close to the performance of SMC methods, and, crucially, it performs much better for high-dimensional problems. \n\n\n**Other applications:** As an example of other possible applications, we are currently applying DCPS to zero-shot conditional sampling for traffic simulation. In this setting, one has access to a diffusion model for the joint distribution of $N$ interacting agents and the aim is to be able to sample joint agent trajectories that satisfy user-specified constraints. Two notable examples are the simulation of joint trajectories that do not collide or trajectories that satisfy certain speed limits, see Table I in [6]. Both cases define specific potentials $g_0: \\mathbb{R}^{N \\times T \\times d} \\to \\mathbb{R}$ where $N$ is the number of agents, $T$  is the length of the trajectory and $d$ is the number of trajectory features considered. DCPS applies successfully by considering potentials built following the same recipe as in the paper; please see the second point in the main rebuttal for more details. We have found that this general principle works well for various inverse problems and as a future work we aim to understand how to select these hyperparameters in a principled manner. \n\n[3] Rozet et al. \"Score-based Data Assimilation\". In Advances in Neural Information Processing Systems. 2023.\n\n[4] Dou, Zehao, and Yang Song. \"Diffusion posterior sampling for linear inverse problem solving: A filtering perspective.\" _The Twelfth International Conference on Learning Representations. 2024.\n\n[5] Bickel, Peter, Bo Li, and Thomas Bengtsson. \"Sharp failure rates for the bootstrap particle filter in high dimensions.\" In Pushing the limits of contemporary statistics: Contributions in honor of Jayanta K. Ghosh, vol. 3, pp. 318-330. Institute of Mathematical Statistics, 2008.\n\n[6] Zhong, Ziyuan, Davis Rempe, Danfei Xu, Yuxiao Chen, Sushant Veer, Tong Che, Baishakhi Ray, and Marco Pavone. \"Guided conditional diffusion for controllable traffic simulation.\" In 2023 IEEE International Conference on Robotics and Automation (ICRA), pp. 3560-3566. IEEE, 2023.", "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": "", "extra_scores": {}}, {"review_id": "dsRycFYay5", "reviewer": "Reviewer_xni9", "summary": "This paper aims to solve the inverse problem within the Bayesian framework. The authors propose DCPS, which approximately samples from the posterior. DCPS creates a sequence of intermediate posterior distributions to approach the target posterior step by step. The authors showcase the effectiveness of DCPS on inverse problems like image restoration and trajectory prediction.", "questions": "1. the unadjusted Langevin is a biased sampler for any finite time step. Why not include the Metroplis-Hasting correction? \n2. Why is L much smaller than n? How does the value of L affect the final performance? \n3. In the image restoration experiments, the authors claim to use only 5 Langevin steps. It is very unlikely that the algorithm is sampling from the right distribution within 5 Langevin steps. Langevin Monte Carlo is known for slow convergence for high-dimensional problems, which takes hundreds of steps even on simple low-dimensional problems. How can the proposed DCPS work with only 5 Langevin steps?", "limitations": "1. Problem-specific intermediate potentials must be designed, limiting DCPS's application from a wider range of inverse problems. \n2. While the goal of this paper is posterior sampling, the proposed DCPS is a biased sampler that does not converge to the true posterior.", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "1. Good empirical results on Gaussian mixture problems. \n2. DCPS is computationally efficient.", "weaknesses": "1. No justification for the design of the intermediate potentials. They are approximations of $g^*_k$ defined in line 122. But why are they good approximations? The manuscript will benefit from a theoretical analysis of the approximation error. \n2. In general, it is unclear how to design intermediate potential for nonlinear forward models. DCPS seems limited to linear problems. \n4. Only LPIPS is reported in the image restoration tasks. The experiment section would benefit from adding evaluation metrics such as PSNR and SSIM. \n5. DCPS generates pseudo observations in a similar way to the prior work FPS [1]. I believe this is an important baseline to discuss and compare. \n6. Overall, the paper is hard to parse, with many long sentences, redundant phrases, and inconsistent notation usage. Just list some of the issues here. I believe a major revision is needed to make this paper more accessible. \n\t1. Typos in Algorithm 1: \"$X^l_{l+1}\\leftarrow X_l+1$\" and\"for $j=l+1-1$ to $l$\" \n\t2. $l$ is used in subscript and superscript together, which is very confusing. For example, $X^l_{l+1}$ in Algorithm 1, $\\pi^l_{k_l}$ in Eq. (3.4).  \n\t3. Line 66: remove the comma before \"and illustrate\"\n\t4. Line 64: \"describe theoretically\" -> \"theoretically describe\"\n\t5. Line 70: \"generate efficiently\" -> \"efficiently generate\"\n\t6. Line 158: a comma is missing before \"we find\"\n\t7. The authors use $N(x;\\mu, \\Sigma)$ to represent the Gaussian density. I suggest the conventional notation $\\mathcal{N}$  from the literature for better consistency with the field. \n\t8. Calling $g_k$ as the potential is confusing when it's actually a likelihood function. \n\t9. The use of upper case $X$ and lower case $x$ is confusing throughout the paper. For example, in line 85, it's $X_k=x_k$.\n\t10. Redundant phrases and long sentences should be revised for clarity. For example, line 62-71, line 96-99, line 151-153, line 160-163.\n\t11. Line 102: \"where $\\mathcal{Z}=\\int g_0(x_0)p_0(dx_0)$\" -> \"where $\\mathcal{Z}=\\int g_0(x_0)p_0(x_0)dx_0$\"\n\t12. Incorrect inline citations throughout the paper. \n\n[1]: Dou, Zehao, and Yang Song. \"Diffusion posterior sampling for linear inverse problem solving: A filtering perspective.\" _The Twelfth International Conference on Learning Representations. 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer xni9,\n\nWe would like to thank you for the time you took to review our manuscript and for your feedback and suggestions. Please find below our response to what we believe are the most crucial points.\n\n**On the approximation of $g_k ^{*}$ and design of the intermediate potentials**: We would like to emphasize that in our methodology the functions $g_k$ are completely user-defined. This is exactly the main point of our paper; we propose a principled method that deals with the intractability of the true potentials and allows the use of problem-informed, user-defined potentials. Therefore, it is not particularly relevant to question whether the functions $g_k$ are precise approximations of the functions $g_k^*$. As already emphasized in the paper, our method **does not require** any knowledge of $g^* _k$.\n\nIn the paper we have proposed choices of potentials for three important problems and their design follows the same principle; please see the second point in the main rebuttal for more details. We do not claim that these potentials are good approximations of $g^*_k$ as **this is not a requirement of our method**; nevertheless, we demonstrate that although they may not be accurate approximations, our method still demonstrates strong performance; as evidenced by our experiments. As an illustration, you can find in the PDF of the main rebuttal a plot of the gradient field of our log potentials compared with those of the true potentials $g^* _k$ (which are computable in a closed form in the Gaussian mixture case). Notably, these are very different and yet DCPS achieves a strong performance, as you stated in the strengths. \n\nFinally, many recent published papers in top conferences [1, 2, 3, 4, 5, 6, 7] (including the FPS paper you suggest we should compare with) has focused only on linear inverse problems, which continues to be a highly relevant and challenging problem class, and as far as we are concerned there is still no gold-standard algorithm that is widely accepted for its robust performance. Besides linear problems, our study also covers two other significant inverse problems for which we also design potentials $g_k$ and empirically assess and illustrate their benefits. Therefore, while it would undoubtedly be ideal to have a *parameter-free* general solution, up to our knowledge only no existing works have been able to tackle this degree of generality while showing a performance comparable to more “specialized” schemes.\n\n**Comparison to FPS**:  We agree with the reviewer that both DCPS and FPS rely on “pseudo-observations,” as acknowledged in the paper (see the discussion in Section A.4 of the appendix where we already describe FPS). For the sake of completeness, we have added a comparison with FPS on imaging experiments but also with three other competitors suggested by the other reviewers, see the main rebuttal. Clearly, DCPS outperforms FPS by a significant margin. While SMC-based algorithms like FPS and MCGDiff have strong theoretical guarantees, their performance scales poorly with increasing dimensions, requiring exponentially more memory. In contrast, DCPS performs well across both low and high dimensions without incurring such high memory costs.\n\n**LPIPS only**: We want to emphasize a key point. Our goal is to develop a sampling algorithm that efficiently generates diverse samples over the entire posterior distribution. For the multimodal examples in our paper, high-quality samples should be varied and differ significantly from the true image. A pixel-by-pixel comparison with the true image is not meaningful for posterior sampling, as it doesn't reflect sampler performance. Since the true image is near the maximum a posteriori (MAP) estimator, good pixel-by-pixel performance might indicate the algorithm generates non-diversified draws from dominant modes, failing to explore the full posterior support.\n\n**Why no Metropolis-Hastings correction?** The author is right in thinking about the use of a MH correction. However, note that we do not actually have access to (unnormalized versions of) $\\pi^\\ell \\_{k_{\\ell+1}}$ since we cannot evaluate $p_k$. Therefore we cannot use MH type algorithms. LMC is of course biased when run for a finite number of steps, but as we show with the Gaussian mixture example, it can still perform decently, very close to that of the asymptotically exact algorithm MCGDiff.\n\n**Typos**: We would like to thank you for drawing our attention to the notation problems present in Algorithm 1 and we apologize for these. Please find a corrected version of our algorithm in the PDF attached to the main rebuttal. Thank you also for pointing out other typos and suggesting corrections.  Note that throughout the paper we use upper case for random variables and lower case for their realizations. With this in mind, saying that $p_{0|k}(\\cdot | x_k)$ is the conditional density of $X_0$ given $X_k = x_k$ is not confusing.\n\n**bias of our algorithm**: To our knowledge, all methods for sampling from posterior distributions with probabilistic diffusion priors are biased with finite iterations. This includes algorithms based on importance sampling, like SMC, which are also biased with limited particles. Regarding LMC, similarly to SMC using an infinite number of particles, if we were using decreasing step sizes converging to $0$, it is also asymptotically unbiased by [8, 9]. DCPS can be made asymptotically unbiased by running LMC targeting the posterior with the final sample from Algorithm 1. The key issue is whether our method’s samples are adequate initializations. While we have shown this empirically, a quantitative analysis of our algorithm’s accuracy remains for future work.  Therefore, based on the current existing literature, pointing out that our method is biased (without any further indications) as a limitation seems unjustified in our opinion. We humbly ask the reviewer to elaborate more on their comment.", "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": "", "extra_scores": {}}, {"review_id": "MKUIun4oDR", "reviewer": "Reviewer_af3x", "summary": "This work proposes a new posterior sampling scheme for unconditional diffusion models. The sampling algorithm, named divide-and-conquer posterior sampling (DCPS), combines Langevin Monte Carlo and Gaussian variational inference to operate the transitions between noise levels along the reverse diffusion process. The authors apply their sampling scheme to several inverse problems and compare their results with several previous works. DCPS seems to improve upon these works, both quantitatively and qualitatively.", "questions": "See weaknesses.", "limitations": "See weaknesses.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The manuscript is well written for the most part.\n* The subject of posterior sampling algorithms in diffusion models is interesting and relevant for the ML and scientific communities.\n* The proposed algorithm seems sound, albeit too complex in my opinion (see weaknesses).\n* The experiments are well described and the results are clearly presented.\n* The code is provided, although it is not documented and instructions to reproduce experiments are minimal.", "weaknesses": "* The proposed method, although presented quite differently, is very similar to the predictor-corrector approach proposed by Rozet et al. [1], where the predictor is a classic DDPM/DDIM step which approximates the transition from one noise level to the next, while the corrector is a number of Langevin Monte Carlo (LMC) iterations. The similarity is striking, especially when noticing that the DDPM step is a Gaussian approximation of the transition. The authors do not discuss nor mention Rozet et al. [1]. The authors should highlight the differences between their posterior sampling algorithm and the one of Rozet et al. [1] and compare their results.\n\n* Even if it were correct, the link between diffusion posterior sampling and Feynman-Kac (FK) models in Section 2 is not relevant and confusing. Unlike the authors state (line 110), the overwhelming majority of diffusion/score-based posterior sampling literature uses either a Markov chain or a stochastic differential equation (SDE) representation. Furthermore, this link with FK models is not even leveraged as part of the method, which only relies on Markov chain properties.\n\n* As mentioned by the authors, intermediate potentials should be designed for each problem, which could be difficult for some inverse problems. In addition the convolution of these potentials with the bridge kernel (Eq. (3.6)) should be (cheaply) tractable and differentiable.\n\n* There are two aspects to the proposed algorithm: the LMC iterations and the intermediate potentials/posteriors. It is hard to assess the contribution of each aspect in the results. My hypothesis is that most of the quality gains are due to the LMC iterations. My rationale is that the potentials $g^l_m(x_m) = \\mathbb{E} [ g_{k_l}(x_{k_l}) \\mid x_m ]$ are actually user-defined potentials, just like $g_m(x_m) = g_0(x_m)$ or $g_m(x_m) = \\mathbb{E} [ g_0(x_0) \\mid x_m ]$. As long as they converge to $g_0$ when $m \\to 0$, the algorithm should work.\n\n### Comments\n\n* I am not sure to understand the reference to \"divide-and-conquer\" from dynamic programming.\n* At line 80, $t$ is undefined.\n* At line 143, Finzi et al. [2] are the first to propose to use the Jacobian of the denoiser to estimate the covariance. Boys et al. [3] later proposed an approximation using the diagonal of the Jacobian.\n* In Algorithm 1, I think there is a typo in \"for $j = \\ell + 1 - 1$ to $\\ell$ do\".\n* Table 5 should be Figure 5.\n* At line 232, \"resort to a optimizing\" -> \"resort to optimizing\".\n* At line 258, $K$ is not defined in the main text.\n* At line 334, if I understand correctly DCPS is not limited to linear inverse problems.\n\n[1] Rozet et al. \"Score-based Data Assimilation\". In Advances in Neural Information Processing Systems. 2023.\n\n[2] Finzi et al. \"User-defined Event Sampling and Uncertainty Quantification in Diffusion Models for Physical Dynamical Systems\". In Proceedings of the 40th International Conference on Machine Learning. 2023.\n\n[3] Boys et al. \"Tweedie Moment Projected Diffusions for Inverse Problems\". 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer af3x, \n\nWe would like to thank you for the time you took to review our manuscript and for your feedback and suggestions. Please find below our response to what we believe is the most crucial point in your review. Please consider reading the main rebuttal containing comparisons with new competitors and comments on the choice of potentials. \n \n**Similarity with [1]:** We humbly disagree with the claim that our algorithm is similar to SDA [1]. To clarify this misunderstanding, let us first give a brief description of SDA. The authors propose an approximation of $p(y|x_t)$ ($g_t ^{*} (x_t)$ with our notation). The resulting density approximation is $$\\hat{p}(y|x_t)=N(y;A \\hat{x}\\_{0|t}^\\theta(x_t), \\sigma^2 \\_y + \\frac{\\gamma  (1 - \\alpha_t)}{\\alpha_t} AA^T )$$. It should be noted that it is similar to the one used in PGDM [3], but with a slightly different choice of variance. After sampling $X_{t-1}$ given $X_t$ by leveraging the approximate conditional score, the authors perform few corrections steps using Langevin Diffusion targeting the marginal distribution $\\propto \\hat{p}(y|x_{t-1}) p_{t-1}(x_{t-1})$. As the authors acknowledge, this PC  step is not new and already appears in the seminal paper of Song et al. 2021\n\nWe now proceed to a step-by-step comparison with [1].\n\n- **Intermediate posteriors** (Please see also the second point in the main rebuttal): While [1] focuses on deriving a new approximation of $p(y|x_t)$ using a Gaussian approximation of $p_{0|t}(\\cdot  x_t)$, we take a different approach and introduce likelihood functions $g_{k_\\ell}$ at different timesteps $(k_\\ell) \\_{\\ell = 0} ^L$ of the diffusion process. By introducing these likelihood functions, we transform the initial problem of sampling from the posterior of interest to that of sampling from the intermediate posteriors, denoted by $\\pi_{k_\\ell}$ in our paper. DCPS is then an iterative procedure where at each step we aim to  sample from $\\pi_{k \\_\\ell}$ using approximate samples from the previous posterior $\\pi \\_{k \\_{\\ell+1}}$. In short, we reduce the initial problem to that of solving $L$ simpler posterior sampling problems. These problems are simpler since, in contrast with the initial problem which required deriving an approximation of the difficult to estimate distribution $p_{0|t}(\\cdot | x_t)$, now we only require approximating the simpler distributions $p_{k_\\ell | t}(\\cdot | x_t)$ for $t \\in [k_{\\ell}: k_{\\ell+1}]$. \n\n- **Backward transition approximation**: The conditional score  in [1] is used within DDIM whereas we posit a Gaussian approximation with learnable mean and diagonal covariance matrix and perform KL minimization on the conditional target distribution that immediately precedes Eq. 3.5. This is **step 2** (see line 185). This step does not target the same distribution as [1] and relies on a different approximation.\n- **Langevin steps**: In [1], $C$-Langevin steps are performed directly after each DDIM step. On the other hand, we resort to Langevin steps **only** to move from one block to the next, i.e., to obtain an approximate sample of $\\pi^\\ell _{k _{\\ell+1}}$ that initializes the next block; see Eq. 3.4. This is **step 1**, (see line 183). We thus use significantly less LMC steps than SDA and the performance gains are not simply due to them, as opposed to [1]. \n\nOur algorithm DCPS and the algorithm in [1] are thus entirely different. We have implemented SDA and compared it with ours on linear inverse problem imaging experiments using the authors' implementation. We used two Langevin correction steps, $\\tau = 0.1$ for the Langevin step size, and a diagonal approximation of $\\gamma = 0.1$ after tuning. While SDA performs well on FFHQ, we couldn't find optimal parameters for ImageNet, resulting in degraded performance. DCPS outperforms it in both average and median LPIPS scores. Please see the PDF in the main rebuttal for detailed results and comparisons with other prominent algorithms.\n\n**Choice of potentials**: Please see the second point of the main rebuttal. The reviewer is right in that the choice of potentials is arbitrary and any sequence should perform well as long as it converges to the inverse problem likelihood function. **However**, in practice, a mischosen potential will require a very large number of Langevin steps or may even result in significant instabilities. We  illustrate the latter point. Take as example the choice of potential $g_m(x_m) = g_0(x_m)$ that you propose. Assume that $x \\in R^2$ and $g_0(x) = N(y; x_1, \\sigma^2 \\_y)$. Assume that $x \\in R^2$ and $g_0(x) = N(y; x_1, \\sigma^2 \\_y)$. We also assume that the prior distribution is for example a mixture with well separated modes far from 0 and that we observe $y >> 0$, the first coordinate of either one of the modes. During the early steps of the diffusion, when $\\sigma_y \\approx 0$, samples from the intermediate posteriors have first coordinates centered around $y$, while the second coordinate remains nearly Gaussian. This leads to instabilities in subsequent steps. When moving to the next step, i.e., sampling $X_{k-1}$ given $X_k$, the denoiser network is evaluated at $X_k$. However, at the $k$-th noise step, the denoising network has been trained to process samples that are almost white noise, which is not the case for our current sample $X_k$, which has a large first component. As a result, the network returns an incoherent value, and since this happens at every step of the diffusion, the errors accumulate, leading to significant instabilities.\n\nAs for the second example $g_m(x_m) = \\mathbb{E}[g_0(X_0) | X_m = x_m]$, this is a valid argument and we believe that it can work well in practice. However, it should be noted that using this method requires a significant amount of memory and further increases the runtime. Namely, differentiating the loss in Eq. A.8 with respect to both parameters requires differentiating the composition of two Denoisers, which is very computationally intensive.", "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": "", "extra_scores": {}}, {"review_id": "6UJLj3vXu0", "reviewer": "Reviewer_GK7d", "summary": "The topic of using a pre-trained diffusion model as a prior for a Bayesian posterior sampling problem is considered. This formulation is compelling (particularly for images) as it combines the powerful generative capacities of large-scale diffusion models with the coherent inference under certainty provided by Bayes’ theorem.\n\nThe paper refines the diffusion posterior sampler of Chung et al by replacing a point mass approximation with a variational Gaussian approximation to the conditional transition distributions.\n\n*Chung et al: Diffusion posterior sampling for general noisy inverse problems, ICLR, 2023*", "questions": "Would MAP estimation (over posterior sampling) also be feasible/performative in this setting? And perhaps computationally easier?\n\nIt's not clear to me how exactly the proposed DCPS algorithm is \"divide-and-conquer\". Over which axis does it divide? And which computational bottleneck does this speed-up? How does this compare to other computational bottlenecks? (I.e. is it dominating)", "limitations": "The authors have addressed key limitations of the work. I see no potential for negative societal impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper tackles an interesting problem and is mathematically compelling as the point mass approximation is likely to be crude in practice.\n\nThe experiments are practical and varied - investigating various likelihoods (linear+Gaussian, Poisson, JPEG decoding). And the results for the introduced sampler are promising.", "weaknesses": "The paper is (perhaps understandably quite dense), in particular, I think some more clarity on the use of twisted potentials and how this differs (or to what extent) from the Chung et al approach would aid the reader.\n\nThe resulting algorithm is somewhat complex and it is not clear how sensitive the algorithm is to the choice of twisting potential and hyperparameters, in particular the number of internal Langevin (M) and VI gradient steps (K).\n\nAdditionally, as noted by the authors, the choice of twisting potentials considered is bespoke in that they have to be specified for each problem. A more general-purpose posterior sampling pipeline that fully separates likelihood and data specification from (automated) posterior sampling would be highly desirable. Although understandably as a future direction in the considered work.\n\n*Chung et al: Diffusion posterior sampling for general noisy inverse problems, ICLR, 2023*", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer GK7d,\n\nWe thank you for your time, your feedback and suggestions. Please find our response to your questions below. In the PDF attached to the main rebuttal you can also find an update of Table 2 in the main paper with 4 more competitors suggested by the other Reviewers. These new results further demonstrate the strength of our method in comparison with the state-of-the-art. \n\n**More precision on the difference with Chung et al.**: The potentials, and the subsequent approximations we introduce in this paper, differ in many aspects from the approximation developed in Chung et al. While [1] derives a new Gaussian approximation of $p(y|x_t)$, we take a different approach by introducing likelihood functions at various timesteps $(k \\_\\ell) \\_{\\ell=0}^L$ in the diffusion process. This transforms the initial sampling problem into sampling from intermediate posteriors, $\\pi \\_{k_\\ell}$, defined by these new likelihoods. DCPS then iteratively samples from $\\pi \\_{k_\\ell}$ using approximate samples from the previous posterior $\\pi_{k_{\\ell+1}}$. Essentially, we reduce the initial problem to solving $L$ simpler posterior sampling problems , which only require approximating $p_{k_\\ell|t}(\\cdot|x_t)$ for $t \\in [k_{\\ell}, k_{\\ell+1}]$ (hence the divide-and-conquer terminology), rather than the difficult-to-estimate $ p_{0|t}(\\cdot|x_t)$ on which DPS but also many recent works in the literature have focused on deriving accurate estimates. When unrolling the backward transitions involved in our algorithm, it can be seen that these are fundamentally different from those of DPS. We will add a side by side comparison in the revised version of the manuscript. \n\n**Choice of twisting potentials**: In the paper, we proposed choices of potentials for three important problems, all following the same principle: each potential is derived by annealing the initial potential and applying it to a rescaled input, i.e., $g_k(x_k) = g_0 \\left( \\frac{x_k}{\\beta_k} \\right)^{\\gamma_k}$, where $\\beta_k$ and $\\gamma_k$ are tunable parameters. Specifically, we used $\\beta_k = \\sqrt{\\alpha_k}$ and $\\gamma_k = \\alpha_k$ for linear inverse problems and JPEG dequantization. For the Poisson problem, we used $\\gamma_k = \\sqrt{\\alpha_k}$ and the normal approximation of the Poisson distribution for $g_0$. We believe that this principle can serve as a general recipe for constructing potentials, leaving the tuning of the parameters to the users. Future works include deriving informed choices of hyperparameters in the general case. We have added a discussion of this matter in the revision of the manuscript. \n\n**Sensitivity to hyperparameters**: Please note that in the Gaussian mixture experiment we examine the impact of the number of Langevin steps, which can be seen to significantly improve the performance when using a large number of steps. Similarly, we have found experimentally that increasing the number of gradient steps improves the performance. \n\n**MAP estimation**: We believe that the principles we presented in this paper can be extended to MAP estimation; one could also design a sequence of intermediate posteriors well-suited for MAP estimation such that the terminal distribution is the posterior of interest, and sequentially solve these problems. The MAP at the previous iteration should be a good initialization for the optimization in the next step. An initial guess would be to start off with the sequence of distributions used in our paper.", "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": "", "extra_scores": {}}]

Author rebuttal:
Firstly, we would like to sincerely thank the reviewers for taking the time to review our paper and for providing constructive feedback. Here below we address the two recurring comments across your reviews. 

**More competitors**: Following the suggestions of Reviewer vN6C, xni9 and af3x we have added 4 more competitors; DiffPIR, DDNM, SDA and FPS. We now compare DCPS with **9 algorithms** from the literature on linear inverse problems and we are happy to report that it ranks first both in average and median LPIPS. The results can be found in the attached PDF. 

**On the choice of potentials**: The methodology we present in this paper relies on the use of different potentials that define intermediate posterior distributions and their purpose is to guide the samples towards the desired posterior distribution. This principle is widely used in the sampling literature; when aiming to sample from a given distribution $\pi$, practitioners define a sequence $(\pi \_t)\_{t = 0} ^T$ which starts with a simple base distribution $\pi_0$ that is generally straightforward to sample, and then progressively move to the desired posterior $\pi_T = \pi$. The design of these intermediate distributions is made on the basis that two consecutive distributions $\pi_t$ and $\pi_{t+1}$ should be close to each other in terms of some divergence or distance. Popular examples include tempering; see for example [1], or annealing; see for example [2]. 

In this paper we have followed a similar principle, adapted to the sampling of a posterior distribution with prior given by a pre-trained diffusion model. While the corresponding diffusion provides a natural path for sampling from the posterior, the grad log of $g^* _k$  (defined before eq. 2.5 in the paper) is in most cases intractable, rendering this path difficult to use in practice. Many works in the literature have focused on approximating it and in this paper we take a different approach and consider more general paths defined through different potential functions, as is usually done in the sampling literature. Hence, we no longer need to find an accurate approximation of $g^* _k$ and we are free to design more convenient potentials. In the paper we consider the sequence defined in eq. 3.3 and we have proposed three examples of potentials for three important problems; linear inverse problems, JPEG dequantization, and inverse problems with Poisson noise. The design of these potentials follows a single principle, which is to use an annealing of the initial potential $g_0$ applied to a rescaled input, i.e. set $$g_k(x_k) = g_0 (x_k / \beta_k)^{\gamma_k}$$ where $\beta_k$ and $\gamma_k$ are tunable parameters. In the examples considered in the paper we used $\beta_k = \sqrt{\alpha_k}$ for the rescaling parameter and $\gamma_k = \alpha_k$ for linear inverse problems and JPEG dequantization (with an additional approximation), while for the Poisson problem we used $\gamma_k = \sqrt{\alpha_k}$ and the normal approximation of the Poisson distribution for $g_0$. This generic principle is also clearly inspired by tempering schemes used in the sampling literature in which many practitioners use $\pi_k(x) \propto p(y|x)^{\gamma_k} p(x)$ where $p$ is the prior and $\gamma_k$ is a sequence that tends to 1 as $k$ increases. Here in our context, with a very specific prior distribution, we add a rescaling factor that we set to $1 / \sqrt{\alpha_k}$ since during the forward process the noised states are obtained by first scaling the initial sample by $\sqrt{\alpha_k}$ and then adding noise. The annealing coefficient $\gamma_k$ is on the other hand a tunable parameter of which we leave the study for future work. A second important aspect of our work is the way we sample from this path of distributions. Practitioners in the sampling literature use either variants of the Metropolis-Hastings algorithms or sequential Monte Carlo (SMC) methods to sequentially sample from the intermediate posteriors. In our context we cannot the Metropolis-Hastings correction since we do not have access to the densities of the distribution within the path and secondly, we do not use SMC due to the curse of dimensionality. Instead, our sampling scheme relies on the structure of the prior as well as variational inference and Langevin Monte Carlo.  

[1] Syed, Saifuddin, Vittorio Romaniello, Trevor Campbell, and Alexandre Bouchard-Côté. "Parallel tempering on optimized paths." In International Conference on Machine Learning, pp. 10033-10042. PMLR, 2021.

[2] Neal, Radford M. "Annealed importance sampling." Statistics and computing 11 (2001): 125-139.

Meta-review: The paper presents a posterior sampling method that combines Langevine MC and VI and uses diffusion processes. Four reviewers provided feedback, with three of the reviewers scoring an unambiguous Accept and one reviewer raising the score during feedback to a less firm Borderline Reject. The reviewers thought the paper was well written and the idea was novel and relevant to NeurIPS. Some concern was raised about how convincing the experiments were, but the general sense was that the authors demonstrated that the idea is indeed practically useful. Therefore, the paper would be suitable for acceptance as a poster.
Decision: Accept (poster)