Provable Posterior Sampling with Denoising Oracles via Tilted Transport
Authors: Joan Bruna
Jiequn Han
Venue: NeurIPS 2024 poster (2024)
Keywords: diffusion based model; posterior sampling; inverse problem; provable sampling
Primary area: diffusion_based_models
TL;DR: We develop the tilted transport technique, which leverages the prior score to exactly transform the original posterior sampling problem into a new one that is provably easier to sample.

Abstract: Score-based diffusion models have significantly advanced high-dimensional data generation across various domains, by learning a denoising oracle (or score) from datasets. From a Bayesian perspective, they offer a realistic modeling of data priors and facilitate solving inverse problems through posterior sampling. Although many heuristic methods have been developed recently for this purpose, they lack the quantitative guarantees needed in many scientific applications. This work addresses the topic from two perspectives. We first present a hardness result indicating that a generic method leveraging the prior denoising oracle for posterior sampling becomes infeasible as soon as the measurement operator is mildly ill-conditioned. We next develop the *tilted transport* technique, which leverages the quadratic structure of the log-likelihood in linear inverse problems in combination with the prior denoising oracle to exactly transform the original posterior sampling problem into a new one that is provably easier to sample from. We quantify the conditions under which the boosted posterior is strongly log-concave, highlighting how task difficulty depends on the condition number of the measurement matrix and the signal-to-noise ratio. The resulting general scheme is shown to match the best-known sampling methods for Ising models, and is further validated on high-dimensional Gaussian mixture models.

Provable Posterior Sampling with Denoising Oracles via Tilted Transport
Joan Bruna
Jiequn Han Flatiron Institute Jhanesinoossoonndiioon org
New York University & Flatiron Institute bruna@cims.ng nyu. nyy. edu
Abstract
Score-based diffusion models have significantly advanced high-dimensional data generation across various domains, by learning a denoising oracle (or score) from datasets. From a Bayesian perspective, they offer a realistic modeling of data priors and facilitate solving inverse problems through posterior sampling. Although many heuristic methods have been developed recently for this purpose, they lack the quantitative guarantees needed in many scientific applications. This work addresses the topic from two perspectives. We first present hardness result indicating that generie method leveraging the prior denoising oracle for posterior sampling becomes infeasible as soon as the mcasurement operator is mildly ill-conditioned. We next develop the rilted transport technique, which leverages the quadratic in linear inverse problems in combination with
structure of the log-likelihoo the prior denoising oracle to exactly transform the original posterior sampling problem into new one that is provably easier to sample from. We quantify the conditions under which the boosted posterior is strongly log concave, highlighting how task difficulty depends on the condition number of the measurement matrix and the signal-to-noie ratio. The resulting general scheme shown to match the best-known sampling methods for Ising models, and is further validated on high-dimensional Gaussian mixture models.
Introduction
Inverse problems consist in reconstructing signal of interest from noisy measurements. As such, they are a central object of study across many scientific domains, including signal processing, imaging, astrophysics or computational biology. the common settings where the measurement information is limited, reliable solution for these problems usually depends on prior knowledge of the data. One popular approach is to choose a regularizer that utilizes data properties such as smoothness or sparseness, and then solve regularized optimization problem to obtain a point estimate of the original data. However, this approach often struggles with selecting an appropriate regularizer and might be unstable in the presence of large measurement noise. A more robust approach takes statistical formulation and seeks to sample the posterior distribution data based on Bayes's theorem, which allows for uncertainty quantification in the reconstructed data by leveraging a model for the prior data distribution.
While accurate models for high-dimensional distributions are notoriously complex to estimate, the resurgence deep neural networks has provided unprecedented capabilities for modeling complex data distributions in certain high-dimensional regimes. Specifically, score-based diffusion models have achieved remarkable empirical success in generating high-dimensional data across various domains, including images, video, text, and audio. These models implicitly parameterize data distributions through an iterative denoising process that builds up data from noise. Furthermore, there is a growing literature developing theoretical foundations of score-based diffusion models
[55 33 58)
38th Conference on Neural Information Processing Systems (NeurIPS 2024).

---

17 45 16 19,, giving a comprehensive error analysis including score estimation, initialization error and dimediiscrtizzation error. By generating high-fidelity data, these models can also serve as data prior for posterior sampling in inverse problems in high dimensions. Following this idea, many studies (see, e.g..
40 22 have leveraged diffusion models for posterior sampling. However, as discussed below, various categories of approaches for posterior sampling introduce different uncontrollable errors, such as those arising from the approximation of the conditional score or the use of limited variational family. This abundance of heuristics contrasts with the principled sampling used in prior data generation, and is often at odds with the statistical guarantees needed in many scientific applications.
In this work, we aim to bridge the gap between principled diffusion-based algorithms for both prior and posterior distributions. Focusing on the canonical setting of linear inverse problems, where measurements are of the form y = Ax w, with x ~ x the signal to be estimated and an independent noise, we first illustrate a negative result, revealing that no method can efficiently sample the posterior in general cases, even with the prior denoising oracle. Subsequently, we develop the tilted transport technique, which utilizes the quadratic structure of the log-likelihood in linear inverse problems in combination with the prior denoising oracle to exactly transform the original posterior sampling problem into new one that is easier to sample. Figure Tillustrates schematic plot of the method using
Gaussian mixture examples, showing that while the original target posterior problem remains multimodal, the boosted posterior resembles unimodal distribution.
prior data generation: large standard Gaussian
same roverse SDE 2V Lugn/XX jjl v/aW
ax?
x
posterior generation:
homa choown bonoled prstectrr
target ponterior
boooted posterior foneaatly sample)
Figure 1: Schematic plot of tilted transport boosting posterior sampling with 2D Gaussian mixture example. The density plot shows the first variable's density, and the scatter plot displays the samples.
We establish precise condition where the density of the transformed posterior problem becomes strongly log-concave, making it suitable for efficient sampling via Langevin dynamics. This condition showcases the interplay between geometric property of the prior (what we call tilted spread; see Section (5) and the conditioning and noise level of the measurements. Interestingly, the condition can be satisfied when the signal-to-noise ratio (SNR) either moderately low or moderately high, in contrast with traditional sampling methods, which typically excel only within specific regime.
As a first application, we show that tilted transport can sample from Ising models of the form v(x) o e e- Qx where x E [+1)d determined by the gap Amax(() (2) mian (Q) = 1, thus matching the performance of Glauber dynamics 24 as well as the computational threshold predicted by the low-degree method 42 More generally, even when the boosted posterior is not strongly log-concave, it remains easier sample than the original one. Thus, tilted transport can be combined with any existing black box posterior sampling methods to enhance their performance. This technique operates without any additional computational cost and functions in a plug-and-play fashion, allowing for straightforward integration into various frameworks. When working with high-dimensional Gaussian mixtures, where analytical solution to the posterior is available. we numerically validate our theory and demonstrate enhanced posterior sampling performance.
d is supported in the hypercube, up to the critical threshold
1.1 Related Work
Numerous studies in recent years have explored score-based priors for posterior sampling. We note that several recent works (60 20 29, 21 introduce hyperparameters to balance the influence of the prior and measurements, resulting in sampling strategies that guide output to regions where the given

---

observation is more likely. These strategies typically deviate from the principles of Bayesian posterior sampling and often lack a precise definition of the resulting distribution. In contrast, other approaches adhere more closely to Bayesian principles. One such approach is variational inference, which involves designing variational objectives and optimization methods based on the structure of score-based However, even with an accurate prior score, the accuracy of posterior sampling heavily depends on the choice of variational family and optimization procedures, not to mention the additional optimization cost. Another popular strategy focuses on approximating the score conditional on the measurement using various heuristics (58) 40 (6 22 48 56 [7]. In this approach, approximation errors typically remain largely uncontrollable due to the challenges associated with tracking the conditional distribution for intermediate states. Recently, some studies have adopted sequential Cante-Crrlo methods to systematically approximate the conditional score [62] B (3], providing consistency as the number of partieles used to approximate the conditional distribution of the intermediate states increases. However, this particle-based method still struggles with high- dimensional problems due to the curse of dimensionality 19). Alternatively, [61] [3] propose
diffusion 41 47 26
[.7]
sas-and-play methods with denoising oracles for posterior sampling, offering asymptotic guarantees, though the required steps may grow prohibitively in high dimensions.
We note that [3 also intuitively explores the possibility of reducing the original posterior to an equivalent one under restrictive conditions in the discrete-time setting. In contrast, our tilted transport technique operates in fairly generic setting and is supported by clear theoretical foundation. Concurrently, [49] proposes a conceptually similar two-stage approach for posterior sampling in sparse linear regression, based on different structural prior rather than denoising oracles.
2 Preliminaries
Notations:. ((R denotes the space probability measures over Rd. Ya denotes the d-dimensional standard Gaussian measure, and by slight abuse of notation, Ys or yr denote the centered Gaussian measure with covariance ōla or Σ when the context is clear. For Q 0 in Raxd and b e Rd in the span of Q, the quadratic tilt of æ is the measure TQ.bT < π with density proportional
to Too. (x) or exp (- xx+x We also use the notation To when = 0. Il@l| denotes its operator norm. y denotes the convolution of two measures π and y. For 2 0 and T E P(R)). ). we define (x) == a ((xx) as the dilation of π. For B 2 0 and x E P(RR), we (D (-) as the Gaussian convolution of π.
define CBT(x)=
Problem Setup. Consider a high-dimensional object of interest E Rd drawn from certain probability distribution æ E P P(R)). We suppose that one has managed to learn a generative model for via the DDPM objective 33 in other words, for any y Rd and or 2 0, we have access to the denoising oracle xr,x (y, or) == E [x where y = x + orw, with x ~ π and w Ya independent. It is now well-established that, such denoising oracle enables efficient sampling of π, well beyond the classic isoperimetric assumptions for fast relaxation of Langevin dynamics [17].
Suppose that we now measure Ax+ where again x ~ π and w Yd' are independent, but now A E Rd xd is a known linear operator different from the identity. Given these linear measurements, we are now interested in the posterior sampling of given y. This corresponds to the basic setup of linear inverse problems, encompassing many applications such as image inpainting, super-resolution, tomography, source separation, to name a few. We are interested in the following natural question: can the power of denoising oracles be provably transferred to posterior sampling?
By Bayes' rule, the posterior distribution Vy.A (denoted simply by y when the context is clear) has density proportional to (xx)p(y(x) & exp - 11xx y112 x(x), and thus we can write it as a quadratic tilt of
V == Tobb, with Q = - -=A
We readily identify certain regimes where sampling from v might be easy:
If Amin (Q) sufficiently large, Amin > 1, then one expects v to strongly log-concave, enabling fast relaxation of Langevin dynamics.
3

---

If (Q) is sufficiently small, Amax < 1. then one expects 2 π in the appropriate sense, and therefore that samples from æ (which can be produced efficiently thanks to x) may be perturbed into samples from
If A E Od is a unitary transformation, then Q = - and the inverse problem reduces to isotropic Gaussian denoising, and is thus first glance "compatible" with the structure of the denoising oracle (such observation will be formalized later).
At this stage, difficulty of posterior sampling: on one hand, a proxy for the signal-to-noise ratio, measured e.g.. by SNR == min (2) (A)" On the other hand, the conditioning of the measurement operator A, x(A)= Amn (A)
already identify two key parameters of the problem that are likely to drive the
or
Anii (A) As shall see, these two characteristics of the linear measurement system will characterize necessary and sufficient conditions for probable posterior sampling. In the following, assume the log of prior density π is smooth and its Hessian exists Vx R
Denoising Oracles and Scorr-Based Diffusion. Let us first review the natural connection between denoising and score-based generative modeling. Score-based diffusion models consist of two processes: forward process that gradually adds noise to input data and reverse process that learns to generate data by iteratively removing this noise. For example, one widely used family for the forward process is the FensteinUUhlenbee (OU) proces:
dX,- = -x, v2dW,
Xo~ ~ n,
(1)
where W, is the standard Wiener process. We use π, to denote the density of X,, given by the action of the OU semigroup x, xr defined by O,f(x) [X xx. and explicitly given by dilated Gaussian convolutions, Oj := Cp, Da, with B, 1 2- and a; e', With sufficiently large T, we know that æy is close to the density of standard Gaussian owing to the exponential contraction of the OU semigroup: KL(Tr llya) e- (L((ll))))
Finally, the measure x, solves the Fokker-Plank equation
0, V (xx,) Ax, xn =
(2)
By writing (2) as transport equation ,, V ((x V log ),,), formally reverse the transport starting at a large time 7 and solving
a, V (-(x+ -) Āo =
Since ã, πT for / s T, introducing again the dissipative term leads to 0, = V. (-(x+ + 2V log n, R,) An, Ap = which admits the SDE representation
dx, (X, 2V log (X)) v2aw,. Xo πΙ
(4)
In practice, one runs this reverse diffusion starting from X, ~ Ya rather than X, ~ Ry. However, by the data-processing inequality, we have that (l(()((r)) z (I((zrllra)
()) thus incurring in insignificant error. To facilitate later exposition, we write the above process reverse in time 31]
dx; = (-x,- 2V log n, (x; dr + v2dW,. X7 Yd-
(5)
and interpret the data generation process running the reverse SDE from T back to 0.
By the well-known Tweedie's 's formula, and up time reparamctrisation, the denoising oracle is equivalent to the time-dependent score V log n
Fact 1 (Tweedie's formula, 32 We have log ny (x) = -1 e e1y-e-21- (x (x,
Log-Sobar Log-Sobolev Inequality and Fast Relaxation of Langevin Dynamics. Given a Gibbs distribution л E P(R)) of the form π f-_ powerful and versatile method sample from æ is to consider the Langevin dynamics
dx,- -Vff(x)drr + v2aw, Xo p4
(6)
In practice, it is also common to introduce positive smooth function B: R4 R2 and consider the time-rescaled OU process dX, - +2,((Waw, Our results could be applied directly to these variants by rescaling time. For the ease of notation, keep ((t) I in the main text.

---

where ol is an arbitrary initial distribution. It is easy to verify that these dynamics define a Markov process that admits π as its unique invariant measure. Perhaps less obvious is the fact that the Fokker-Plank equation associated with eq. (6) given by 0,μ V (V fH) + Ap (and where is the law of X)) is in fact Wasserstein gradient flow for the relative entropy functional (l((ulzz) 38. Under this interpretation, one can quantify the convergence of Langevin dynamics to their invariant measure, i... its time to relaxation, by establishing a sharpness or Polyak- Lowacjevitz (PL)-type inequality. Indeed, by noticing that d di KL(H=|=> -IGu[]x), where I(H||x)
[1 log μ - v log æ is the Fisher divergence, the PL-type inequality in this setting is given by the Logarithmic Sobolev Inequality (LSI): we say that a measure satisfies LSI(p) if for any μ E P(Rd) it holds (L(H s (p((((
This functional inequality directly implies KL,(H, ||=) 3 e -2r (l)(=ll While for general æ is typically hard to establish the LSI, there are two important sources of structure that lead to quantitative (i.e., p = (2)(1) bounds: when π is product measure x = eed (in which case π satisfies LSI with the same constant as f), and when is strongly log-concave] i.e.. -Va log (xx Z al for all in which case the celebrated Bakry- Emery criterion [3] states that p 2 a.
3 Evidence of Computational Hardness in the Generic Case
We start our analysis of posterior sampling by discussing negative results for the general case. Recently, 30] established computational lower bounds for this task using cryptographie hardness assumptions. In this section, we complement these results by illustrating a correspondence with sampling problems on Ising models, leading to an arguably simpler conclusion.
For this purpose, consider ग Unif( (=1)4) the uniform measure of the hypercube. Quadratic tilts of स define generic Ising models, rich and intricate class of high dish-iiinnsioall distributions. Since ă is a product measure, associated denoising oracle becomes a separable function that can be computed in closed-form:
Fact 2 (Denoising Oracle for π)), Let y(I.,, = exp ( 11 11- Then we have
y(1,+1,0) - x1, DOx (d(y;:))) with o1 y(1,+1, + +
Given symmetric matrix Q E Rdxd, an Ising model is given by the tilt Tox P({=1]9). In our setting, we can thus view such models as the posterior distribution of linear inverse problem associated with the uniform prior πt Efficiently sampling from Ising models is a fundamental question at the interface statistical physics and high-dimensional probability, and several works provide evidence of computational hardness under variety of settings.
Notably, by treating Q as the adjacency matrix of a regular graph, 27 establishes that sampling from is impossible for Amax (Q) Amin((Q (Q) 2 2 + E, for any > O, unless NP = RP. In other words, for poorly conditioned tilt Q (in the sense that there is large gap between the smallest and largest eigenvalue). there is no efficient posterior sampling algorithm, even with the knowledge of the prior denoising oracle. The threshold can even be reduced to + & by using a weaker notion of computational hardness [42], given by the low-degree polynomial method 43) Remarkably, this threshold agrees with the current best-known algorithmic results for sampling generic Ising models with Glauber dynamics (25 II. Finally, we also mention that when Q is random Gaussian symmetric matrix, the associated so-called Sherrington BeerringtonKKirppatrrekk (SK) model, has been analyzed with dedicated algorithms. In this setting, it is also known (24] that 'stable' sampling algorithms fail to sample from the SK model as soon as A (Q) - A ( > In summary, we have:
271). There exist no general- purpose, efficient posterior sampling algorithms, for Q sufficiently ill-conditioned, even under the knowledge of the prior denoising oracle.
Theorem (Computational Hardness of Sampling Ising Models, (4|27))
One could wonder whether this computational hardness comes from the discrete nature of the hypercube. It is not hard to observe that this is not the case: the following proposition, proved in Appendix A shows simple reduction from model where the prior is replaced by a smooth mixture of Gaussians centered at the corners of the hypercube, with variance 6.
For suitable perturbation of via the Hooley- Strook perturbation principle 33
5

---

Proposition 4 (Hardness extends to smooth priors), Assume a posterior sampler exists for the smooth prior with TV error e and ò = o(2-1/2) Then there exists a sampler for the associated Ising model with error I.le.
In conclusion, one cannot hope for a generic method that leverages the prior denoising oracle to perform efficient posterior sampling, as soon as A is mildly ill-conditioned. Thus, in order to perform provable posterior sampling, one needs to either (i) constraint the measurements, or (ii) exploit structural properties of the prior measure. In the following, focus on (i), namely providing guarantees for well-conditioned A that leverage the OU semigroup for generic prior distributions.
4 Posterior Sampling via Tilted Transport
We now present simple method that reduces the original posterior sampling problem another posterior sampling problem with more benign geometry, by leveraging the shared quadratic structure of the posterior tilt and the OU semigroup. The power of the denoising oracle perform sampling of the prior π comes from its ability to run the transport equation (3) in either direction, and leveraging
the fact that sampling from œт is easy. To transfer this power to posterior sampling, we can thus attempt to replicate this scheme: can we implement a transport between the posterior y and a terminal measure YT that is easy sample, that only relies on the pre-trained prior x
Motivating Example. Consider first the denoising setting: == orw. According to the forward process, we have (() 4 N(e Xo, (1 e (--2-)) (2))). Introduce 7 > and define e= y= x==e"x+e"" ow such that p(iix) _ N((-Txx,e" o²la). We match the variance by letting e- 2T 02= =1 2T i.e., = log((++ then we have p(f(x) = pxx (Xo), which gives
() L (Xp. Xr.). Therefore, to perform the posterior sampling pxx})), we only need to do the sampling ) which can be achieved through the reverse SDE. Specifically, let X7- = e and run the reverse SDE (5) from 7 to O, then X6 will be the desired posterior.
Hamilton-Jacee Equation and Quadratic Tilts. If solves the Fokker-Plan Plank eq. (2) then one can verify that the time-varying potentials fi log n, solve the viscous Hamilton-Jacobe PDE (HJE)
a fi A.; 2 + V f.
(8)
Now, the posterior y= =TQ creates an additional quadratic term in the potential log f fxx +x+xx b. One could naively hope that this additive quadratic term would still define solution of the HJE with the tilted initial condition fo = log v - or equivalently that the measure To solves the transport equation (3). Unfortunately, due to the nonlinearity in (8) brought by the terms | II,, this is not the case. However, as we shall see now, this is not far from being true: one just needs to consider time-varying quadratic tilts in order to satisfy the HJE.
Tilt Transport Equation. We consider then a one-parameter family of distributions v, of the form v T Q..b, Tr, with Qo Q and bo b. As it turns out, one can ensure that log v, solves the HJE associated with the reverse process by asking that Qt, b, satisfy the first-order ODE
è, 2(1 Q.),,
=0=
b, = (I+
bo b
Theorem 5 (Tilted Transport). Assume T such that the ODE (9) is well-defined on [0. By initializing X, ~ Y, and run the reverse SDE from I to 0, we have X2 ~ Vs for s E [0,1], specifically, Xo gives the desired posterior.
Solution to eq. 9 Without loss of generality, we assume s d, and the observation operator A E Rd xd has general singular value decomposition form A U.VT with non-zero singular values A 2 A2 2 2 da > O. By diagonalizing Q and solving the scalar ODE 9, 2(1 + 4:)4,
for diagonal entries, we have 2, Vdiag
21 140-"
I+ 14 - O, 0) VT. where the
solution defined up to the blowup time T" := log(1 + o² 02/2)) log(1 (1 + A (Qm=(())1) (1)-1). b, can be B.2
further solved from the solution 2 see Appendix B.2 for more details.

---

With the explicit solution of Q1, b,, we can interpret the term exp(- Q,x+x"b) exp(=3x"Q0xxx""> as the likelihood of the inverse problem with respect to the new prior distribution N, and the corresponding operator. Based on this observation and Theorem we have the following corollary, transforming the original posterior sampling problem to new posterior sampling problem exactly. We remark that when identity, the corollary recovers the analysis we have in the motivating example; see Appendix B.2 for the proof and more discussions.
Corollary 6. Fix I < T Sampling from the original posterior is equivalent to a two-step process: first, sample from new posterior X₁ Vt. and then run the reverse SDE (5) from time O.
5 Quantitative Conditions for Provable Sampling
Now we show that the new posterior sampling problem described above is provably easier to sample than the original posterior sampling problem from two aspects. On the one hand, the (negative) eigenvalues of the quadratic tilt =xxT0xx= + +x"b, become more negative, essentially meaning that the SNR of the new observation model becomes larger. To be more specific, - T",
Amia On the other hand, the new prior distribution πтς becomes closer to single-mode Gaussian (recall that (L(x))ly))) O(e ())")), which is also easier to sample. Combining these two arguments, we expect that, as t increases, becomes easier to sample due to easier prior and easier likelihood:
Amin (2i) Anin
(Q)=
(x) & (x) exp
1 ž" @ix+xx+bbll
easier prior
easier likelihood
Let us now quantify the above intuition.
Sufficient Conditions for Strong Log-Concen Pog-Concavity of vr.. We start by giving simple sufficient condition that ensures that vr- is strongly log-concave. As discussed earlier, this ensures fast relaxation of the Langevin dynamics, enabling efficient sampling from VT- and therefore of as Corollary For that purpose, given the prior л E P P(Rd) and f 2 O, we define
Xi (T) sup [[Cov[T
(10)
x
where the covariance is given by Cov Exx-a [xx (E==
Xi (x) thus measures the largest 'spread' of any tilted measure of the form T..x Equipped with this definition, we have the following sufficient condition to ensure that yr- is strongly log-concave:
Proposition 7 (Strong Log-Con Concavity vr vr- is strongly log-concave if
x(A)
Xnel (x) < 11@11-1 (x(A)
(11)
The proof is in Appendix C It relates two parameters of the measurement process, the condition number of and the hignal-to-noise ratio in terms of ||Q1], with geometric property of the prior, the spread function X² (T). While this function is not immediately transparent, the following examples illuminate its behavior in reprsentative high-dimensiona settings.
Example 8 (Behavior of Xi (z)).. We have the following examples
(i) Gaussian measure: Xt(ra) =
1H7
(ii) Compactly Supported Gaussian Mixture: If is compactly-supporte in ball of radius R and then Xi (μ * ya)
T+51
1+8t
(iii) Tensorization: If = #ı @ μ2 @ Ha. then (i(p) = max; Xi (H:;).
(iv) Uniform measure hypercube: If is uniform the hypercube Ha, then (T)) 1.
7

---

Ising Models. As direct consequence of Proposition 7 and Example (iv), we establish sampling guarantee for Ising models:
Corollary 9 (Tilted Transport for the Ising Model). Let be the uniform measure on the hypercube, and Q such that Amax (Q) Amin (Q) < 1. Then vr- is strongly log- log-concave, and therefore v T can be sampled efficiently (in continuous-ting
This result thus establishes that Ising models admit an efficient continuous-time procedure for sampling provided their spectrum satisfies Amax (2) -Amin ()) < 1, thus precisely matching the threshold of [25 I achieved by Glauber dynamics, as well as the low-degree prediction from [42]. We remark though that our procedure not (yet) algorithmic; a careful analysis of the discrete-time complexity and the approximation rates is beyond the current scope, but our next endeavor. If one specializes the previous result to the SK model, the equivalent inverse temperature that guarantees sampling is 8 1/4, which remains below
1, the threshold of the hard phase. For this threshold, dedicated AMP-based sampling succeeds [24. 14]. We also remark that, in itself, it should not come as a surprise that may be sampled under these conditions, since [3] already established an LSI on directly, using an entropy decomposition along the so-called Polchinski renormalization group [6] that refines our Bakry-Emery criterion. In this context, it would be interesting explore whether this refined criterion could be applied to Vy- to improve upon Proposition 7
under appropriate conditions.
Gaussian Mixtures. By applying Proposition 7 to Example g (ii), we directly obtain the following
guarantee for generic comptactly supported Gaussian mixtures:
Corollary 10 (Tilted Transport for Gaussian Mixtures.. If * 7 and diam s R, then VT- is strongly log-concave if
(I (L5OR))) SNR 3 > R²
(12)
x(A)2
also holds when = 0 and the prior π is any distribution with a bounded support radius R.
Figure 2 displays several contours of the condition in eq. (12) function of SNR and x(A). Each U-shaped contour is determined by a combination of 8 and R. which uniquely characterizes the prior. For all points ((SNR), x(A)) outside of contour, representing specific inverse problem, Vy- is strongly log-concave and thus easy to sample. Given an observation model where both SNR and x(A) are fixed, it is straightforward see that the condition in eq. (12) is more readily satisfied increases and R decreases. Figure also confirms this result since as ó increases or R decreases, the U-shaped contour shrinks and the region of easy sample expands. Now we discuss the implications in the reverse scenario where the prior is fixed and the observation model is adjusted. If we look Figure 2
horiizonallly, we know that given prior and k k(A), the target posterior can be reliably
sampled if the SNR is either sufficiently low or high, with the region of mid-SNR being challenging. The closer x (AA) is to the smaller this challenging region When the problem is denoising such that x(A) ((A) 1, the challenging region vanishes, and sampling the posterior is straightforward using the denoising oracle, as previously explained.
20
20-
Easy
Easy
Easy
Hard
Easy
10-
6-61, 16
A-15.tw12
11
10
10.
10
3.2
1.0
10
10
10-2
102
107
Figure 2: Phase diagram for the boosted posterior Vy- being strongly log-concave in Corollary 10
Comparisons. 1. (with Langevin dynamics) As introduced above, Langevin dynamics and its discretized version, Langevin Monte Carlo (LMC) [52 46 serve as ideal baselines for efficient posterior sampling in high SNR regimes where the posterior becomes strongly log-concave. Proposition
8

---

demonstrates that our tilted transport technique enables provably efficient sampling from a broader range of prior distributions compared to traditional Langevin dynamics without a denoising oracle. Particularly, in low SNR regimes where conventional Langevin dynamics struggle with severe non-log-cove con-log-concavity and slow mixing times, tilted transport can transform the sampling challenge into a tractable problem for log-concave distributions.
2. (with Importance Sampling) In the low SNR regime with a well-conditioned A, the posterior measure can be viewed as a small perturbation of the prior. As such, a natural baseline for posterior sampling is importance sampling using the prior as proposal - for which samples can be efficiently obtained thanks to the denoising oracle and the variance of sample weights is small. However, as detailed in Appendix C.2 the sampling complexity exponential with the SNR when the SNR is sufficiently large, assuring the failure of the importance sampling on this extreme.
Stability. In the numerical implementation of the boosted posterior, often encounter specific errors. Appendix CC3 provides a stability analysis of the two-step process outlined in Corollary 6 focusing initialization error and score error, and demonstrates that the quality of the final samples is robust with respect to these errors.
Numerical Experiments
Our theory above demonstrates that VT- is provably easier to sample than the original posterior v. Thus, given baseline sampling algorithm Alg, then apply the denoising oracle to obtain the final sample, rather than directly sampling from v using Alg. Algorithm 8 provides complete description of this approach using tilted transport. In this instance, we use Euler discretization with equal time steps to transport samples from from TT T TT, though alternative time integrators and grids can also be applied.
first sample from the boosted posterior and
Algorithm 1 Sampling Using Tilted Transport
Require: Parameters of quadratic tilt Q. b. small time shift e, baseline sampling algorithm Alg. time-dependent score log π. (-), Ar for reverse SDE
Ensure: A sample Xo from posterior distribution To.b
1: Calculate the blowup time by 7 == _ log(1 Amax (()-1)
2: Determine the number of reverse SDE steps by N N= - and starting time î = NAr
3: Use baseline sampling algorithm Alg to sample XN from b
4: for to 1 do
5: Sample Z; NNO, 1a)
6: X;-1 X; (X; 2V log TIN (Xi))A+ + V2A Z₁
7: end for
8: return Xo
We now validate our theoretical results by applying Algorithm to the Gaussian mixture model in high dimensions, using LMC as the baseline algorithm. Same to the models considered in [13] the prior distribution is mixture of 25 components with known means and variances (see Figure [ for a 2D visualization and Appendix t for detailed settings). We examine three cases where d 20, 40, and 80. In each scenario, we set d
fix x 20, and vary the SNR from 10-5 to 10-1, We use the Sliced Wasserstein distance as a principled error metric, computed from samples obtained by our algorithms and samples directly from the analytically computed posterior Gaussian mixture. Figure 3 illustrates the comparison between LMC and LMC boosted by tilted transport. As analyzed earlier, LMC is effective when the SNR is high enough to render the target posterior strongly log log-concave, but its error quickly increases as the SNR decreases. In contrast, the tilted transport enhances LMC to perform well in both low and high SNR regimes with small sampling errors. Its performance is weaker in the mid-SNR regime compared to the extremes, predicted by Corollary [T]] However, the tilted transport still improves upon LMC in this challenging regime by boosting effective SNR and simplifying the prior.
We further test tilted transport when d' < d, in which Amin( remains zero but the signal corresponding to the non-zero eigenvalues still gets enhanced. Therefore, although it becomes more

---

d+ 20
4
d 80
Langern Boosee Langevh
Sioced Waserstan distane
60
0.
10
Figure 3: Comparison Langevin and boosted Langevin for Gaussian mixture prior. We generate the the posterior under 20 different instances in each setting. The sliced
prior, measurement and sample Wasserstein distances are plotted with the median in the middle, and the 25th and 75th percentiles indicated by the error bars.
difficult for Vy- to be strongly log-concave, the tilted transport can still make the new posterior easier to sample even if it is not strongly log-concave yet. Detailed results are reported in Appendix E.
7 Discussion and Future Work
In this paper, we theoretically investigate posterior sampling using powerful priors provided by denoising oracles. We demonstrate that efficient posterior sampling be challenging even with a perfect denoising oracle for the prior. To achieve provable posterior sampling, one must either constrain the measurements leverage the structural properties of the prior. We focus the former, showing that well-conditioned measurements enable the proposed tilted transport technique to simplify the task significantly, providing clear, verifiable condition for efficient sampling, as demonstrated on the Ising model. Several questions remain open: Can this approach provably handle poorly-conditioncl measurements, such as inpainting? Can be extended from linear to nonlinear inverse problems? We show in Appendix D how to extend the tilted transport beyond the condition of Proposition 7 via 'iterated tilts', the expense of introducing approximation errors. the theory side, the key object underlying the success of the tilted transport is the spread Xı (T)); in particular, understanding when one can remove dimension dependence an interesting question. We also aim to systematically evaluate the empirical performance of tilted transport in imaging and scientific computing. Appendix [F.2 provides a proof-of-concept for various imaging tasks. We suspect that tilted transport could even improve existing posterior point estimate methods by boosting SNR and enabling proper uncertainty quantification through the reverse process.
References
[1] N. Anari, V. Jain, F. Koehler, H. T. Pham, and T.-D. Vuong. Entropic independence I: Modified log-Sobolev inequalities for fractionally log-concave distributions and high-tenn gigh-temperature ising models. arXiv preprint arXiv:2106. 04105, 2021.
[2] B. D. Anderson. Reverse-time time diffusion equation models. Stochastic Processes and their Applications, 12(3):313-326 1982.
[3] D. Bakry and M. Emery. Diffusions hypercontractives. In J. Azéma and M. Yor, editors. Séminaire de Probabilités XIX 1983/84, pages 177-206. Springer Berlin Heidelberg, Berlin, Heidelberg, 1985.
[4] B. Barak, S. Hopkins, J. Kelner, P. K. Kothari, A. Moitra, and A. Potechin. A nearly tight -fsuurrsss lower bound for the planted clique problem. SIAM Journal on Computing, 48 (2):687-735. 2019.
[5] R. Bauerschmidt and T. Bodineau. A very simple proof of the LSI for high temperature spin systems. Journal of Functional Analysis, 276(8):2582-5588 2019.
[6] R. Bauerschmidt, T. Bodineau, and B. Dagallier. Stochastic dynamics and the Polchinski equation: an introduction. arXiv preprint arXiv:2307.07619, 2023.
[7] Benton, V. De Bortoli, Doucet, and Deligiannidis. Linear convergence bounds for
diffusion models via stochastic localization. arXiv preprint arXiv:2308.03688 2023.
10

---

[8] J. Benton, V. De Bortoli, A. Doucet, and G. Deligiannidis. Nearly d-linear convergence bounds for diffusion models via stochastic localization. The Twelfth International Conference on Learning Representations, 2024.
[9] P. Bickel, B. Li, and T. 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, volume 3, pages 318-330. Institute of Mathematical Statistics, 2008
[10] S. G. Bobkov, I. Gentil, and M. Ledoux. Hypercontractivity of comilton-Jacohte equations. Journal de Mathématiques Pures et Appliquées, 80(7):669-66) 2001.
[11] H. J. Brascamp and E. H. Lieb. On extensions of the Brunn-Minkowski and Prékopa-Leine Leindler theorems, including inequalities for log concave functions, and with an application to the diffusion equation. Journal of functional analysis, 22(4):366-389) 1976.
[12] A. Cabezas, A. Corenflos, J. Lao, and R. Louf. Blackjax: Composable Bayesian inference in JAX, 2024.
[13] G. Cardoso, Y. Janati El idrissi, S. L. Corff, and E. Moulines. Monte Carlo guided denoising diffusion models for Baysian linear inverse problems. In The Twelfth International Conference on Learning Representations, 2024.
[14] M. Celentano. Saankov--Frnique poMt and proof of the local convexity of the TAP free energy. The Annals of Probability, 52(3):923-955 954, 2024.
[15] S. Chatterjee and P. Diaconis. The sample size required in importance sampling. The Annals of Applied Probability, 28(2):1099-1135, 2018.
[16] H. Chen, H. Lee, and J. Lu. Improved analysis of score-based generative modeling: User-friendly bounds under minimal smoothness assumptions. In International Conference on Machine Learning, pages 4735-4763, PMLR, 2023.
[17] S. Chen, S. Chewi, J. Li, Y. Li, Salim, and A. Zhang. Sampling is as easy learning the score: theory for diffusion models with minimal data assumptions. In The Eleventh International Conference on Learning Representations, 2023.
[18] S. Chen, S. Chewi, H. Lee, Y. Li, J. Lu, and A. Salim. The probability flow ODE is provably fast, Advances in Neural Information Processing Systems, 36, 2024.
[19] S. Chen, V. Kontonis, and K. Shah. Learning general gaussian mixtures with efficient score matching. arXiv preprint arXiv:2404. 18893, 2024.
[20] Choi, S. Kim, Y. Jeong, Y. Gwon, and S. Yoon. ILVR: Conditioning method for denoising diffusion probabilistic models. arXiv preprint arXiv:2 0293388, 2021.
[21] H. Chung, B. Sim, and J. C. Ye. Come-closee closer-difffse-feeee faster: Accelerating conditional diffusion models for inverse problems through stochastic contraction. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12413-12422, 2022.
[22] H. Chung, J. Kim, M. T. Mecann, M. L.. Klasky, and J. C. Ye. Diffusion posterior sampling for general noisy inverse problems. In The Eleventh International Conference on Learning Representations, 2023.
[23] Z.. Dou and Y. Song. Diffusion posterior sampling for linear inverse problem solving: A filtering perspective. In The Twelfth International Conference on Learning Representations, 2024.
[24] A. El Alaoui, A. Montanari, and M. Sellke. Sampling from the CherringtonnKKikparriee Gibbs measure via algorithmic stochastic localization. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 323-334 IEEE, 2022.
[25] R. Eldan, F. Koehler, and O. Zeitouni. A spectral condition for spectral gap: fast mixing in high-temperature ising models. Probability theory and related fields 182(3): 2022
[26] B. T. Feng, J. Smith, M. Rubinstein, H. Chang, K. L. Bouman, and W. T. Freeman. Score-based diffusion models as principled priors for inverse imaging. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 10520-10531, 2023.
[27] A. Galanis, D. Stefankovič, and E. Vigoda. Inapproximability of the partition function for the antiferromagnetic ising and hard-core models. Combinatorics, Probability and Computing. 25 (4):500-559, 2016.
[28] M. Gelbrich. On a formula for the I.2 wasserstein metric between measures on euclidean and Hilbert spaces. Mathematische Nachrichten, 147(1):185-22)) 1990.
11

---

[29] A. Graikos, N. Malkin, N. Jojic, and D. Samaras. Diffusion models as plug-and-pla priors. Advances Neural Information Processing Systems, 35:14715-14728, 2022.
[30] S. Gupta, A. Jalal, A. Parulekar, E. Price, and Z. Xun. Diffusion posterior sampling is computationally intractable. arXiv preprint arXiv22402.12227, 2024.
[31] U. G. Haussmann and E. Pardoux. Time reversal of diffusions. The Annals of Probability, pages
1 1188-1205, 1986.
[32] R. Herbert. An empirical bayes approach to statistics. In Proceedings of the third berkeley symposium on mathematical statistics and probability, volume 1, pages 157-163, 1956.
[33] Ho, A. Jain, and P. Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840-688 101000666111222 2020.
[34] M. D. Hoffman and A. Gelman. The No-U-Turn sampler: adaptively setting path lengths in Hamiltonian Monte Carlo. Journal of Machine Learning Research, 15()):1933-163, 2014.
[35] R. Holley and D. Stroock. Logarithmic Sobolev inequalities and stochastic ising models. Journal of Statistical Physics, 46(5-6):
1 159-1194, Mar. 1987.
[36] A. Jalal, M. Arvinte, G. Daras, E. Price, A. G. Dimakis, and J. Tamir. Robust compressed sensing mri with deep generative priors. Advances in Neural Information Processing Systems,
34:14938-14954, 2021.
[37] Y. Janati, A. Durmus, F. Moulines, and J. Olsson. Divide-and-conquer posterior sampling for denoising diffusion priors. arXiv preprint arXiv:2403. 1407, 2024.
[38] R. Jordan, D. Kinderiehrer, and F. Otto. The variational formulation of the tokker-plande equation. SIAM journal on mathematical analysis, 29(1):1-17, 1998.
[39] Karras, S. Laine, and T. Aila. style-based generator architecture for generative adversarial networks. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pages 4401-4410, 2019.
[40] B. Kawar, G. Vaksman, and M. Elad. SNIPS: Solving noisy inverse problems stochastically. Advances in Neural Information Processing Systems, 34:21757-21766 2021.
[41] B. Kawar, M. Elad, S. Ermon, and J. Song. Denoising diffusion restoration models. Advances in Neural Information Processing Systems, 35:23593 236066, 2022.
[42] D. Kunisky. Optimality of Glauber dynamics for general-purpose Ising model sampling and free energy approximation. Proceedings of the 2024 Anmual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 5013-5028, 2023.
[43] D. Kunisky, A. S. Wein, and A. S. Bandeira. Notes computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio. In ISAAC Congress (International Society for Analysis, its Applications and Computation), pages 1-50. Springer, 2019.
[44] H. Lee, J. Lu, and Y. Tan. Convergence for ccore-based generative modeling with polynomial complexity. Advances in Neural Information Processing Systems, 55:22870-228883 2022.
[45] H. Lee, J. Lu, and Y. Tan. Convergence of score-based generative modeling for general data distributions. In International Conference on Algorithmic Learning Theory, pages 946-985. PMLR, 2023.
[46] Y.-A. Ma, T. Chen, and E. Fox. A complete recipe for stochastic gradient MCMC. Advances in neural information processing systems, 28, 2015.
[47] M. Mardani, J. Song, J. Kautz, and A. Vahdat. A variational perspective on solving inverse problems with diffusion models. arXiv preprint arXiv:2305. 04391, 2023.
[48] X. Meng and Y. Kabashima. Diffusion model based posterior sampling for noisy linear inverse problems. arXiv preprint arXiv:2211.1222
2022.
[49] A. Montanari and Y. Wu. Provably efficient posterior sampling for sparse linear regression via measure decomposition. arXiv preprint arXiv:2406. 2.Xx:2406.115500. 2024.
[50] B. Oksendal. Stochastic differential equations: introduction with applications. Springer Science & Business Media, 2013.
[51] Otto and C. Villani. Generalization of an inequality by Talagrand and links with the logarithmic Sobolev incquality. Journal of Functional Analysis, 173(2):361-400 2000.
12

---

[52] G. O. Roberts and R. L. Tweedie. Exponential convergence of langevin distributions and their discrete approximations. Bernoulli, pages 341 341-363, 1996.
[53] C. Saharia, W. Chan, H. Chang, C. Lee, Ho, T. Salimans, D. Fleet, and M. Norouzi. Palette: Image-to-image diffusion models. In ACM SIGGRAPH 2022 conference proceedings, pages 1-10, 2022.
[54] S. Shoushtari, J. Liu, and U. S. Kamilov. Dolph: Diffusion models for phase retrieval. arXiv preprint wtXiv:2211.0052/ 2022.
[55] Sohl-Dickstein, E. Weiss, N. Maheswaranathan, and Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In International conference on machine learning, pages 9266-2265. PMLR, 2015.
[56] Song, A. Vahdat, M. Mardani, and J. Kautz. Preudoinverss--guided diffusion models for inverse problems. In International Conference on Learning Representations, 2022.
[57] J. Song. Zhangg H. Yin, M. Mardani, M.-Y. Liu, J. Kautz, Chen, and A. Vahdat. Loss- gusded diffusion models for plug-and soug-and--lay controllable generation. In International Conference Machine Learning, pages 32483-32498, PMLR, 2023.
[58] Y. Song, Sohl-Dickstein,
Kingma, Kumar, S. Ermon, and B. Poole. Score-based generative modeling through stochastic differential equations. arXiv preprint ar 2020.
[59] Y. Song, C. Durkan, I. Murray, and S. Ermon. Maximum likelihood training of score-based diffusion models. Advances in neural information processing systems, 34:1415 2021.
[60] Y. Song, I.. Shen, I.. Xing, and S. Ermon. Solving inverse problems in medical imaging with score-based generative models. In International Conference Learning Representations, 2022.
[61] Y. Sun, Z. Wu, Y. Chen, B. T. Feng, and K. I.. Bouman. Provable probabilistic imaging using score-based generative priors. IEEE Transactions on Computational Imaging, 2024.
[62] L. Wu, B. Trippe. C. Naesseth, D. Blei, and J. P. Cunningham. Practical and asymptotically exact conditional sampling in diffusion models. In Advances in Neural Information Processing Systems, volume 36, pages 31372-31400 2023.
[63] X. Xu and Y. Chi. Provably robust score-based diffusion posterior sampling for plug-and-play image reconstruction. arXiv preprint arXiv: / 70422, 2024.
13

---

A Proof of Proposition
Let 0 and be the uniform measure in the d-dimensional hypercube. Consider a Gaussian mixture prior defined
π * Yá.
Since both π and Y are product measures, it follows that is also a product measure, and therefore its denoising oracle ,O,, x is explicitly given by DV,(y.r); = (/ f), with
((v.1) = St uuv,r(u)du,
(13)
qv.r(u) = z-1 (e- 1 (1- (v-w)) + ee" (0-0=
(14)
Observe that qv is the density of a Gaussian mixture in R of the form aN (l((,,,))((1-))W with parameters
2 -8-=2-+
(15)
b. +1
(16)
2xr
(17)
16-
2012
(-6 2u1
2
e
20
and thus (v, = abb + +1 a)-
Let denote by fro the target Ising model, supported in the d-dimensional hypercube, and define the approximation 1 == Tœa. Suppose that there an algorithm A that leverages the denoising oracle of æ that can efficiently sample from P²: its law á satisfies TV( A) with runtime polynomial in d and log(E")).
Let now R(x) = sign(x), and consider the sampler R o A, which is now supported in the hypercube. By the triangle and data-procedd Kata-processing inequalities, we directly have
TV(Ref. HO) s TV(R* + TV(RoHO
(18)
s <VV(,, TV 10) < TV
(19)
(20)
remains to bound the second term in the RHS. We have compare two measures in the hypercube. For a E Ha := {+1]d, they are given respectively by
me(or= = To Qv 7.
(21)
R (o) Ż Σ f
e 2xo dr.
(22)
zEHH R(x)=o
Applying the Laplace approximation into each integral obtain, as ō 0.
S - 1Ix=21 ~ Ca,se- lor
=
Ca,se ((ore))Qlobt)
lar-el 26
otherwise
(23)
where or @ 2 is the XOR, and lo 2/ is the Hamming distance. We thus have, for any o E Ha.
(CRug (o) -e -er Qo s 2d damil111)) 102
(24)
tor (rrgddd(uma dldmm (0))))mmm)))222 -
(25)
It follows that write Rap (0) as
R (o) -irTrr +,o)
14

---

with relative error
Morl to Q0
1 ed(l+ (0) (2))
(26)
follows that
TV( =
(27)
and thus if 8 < Vd' have negligible TV approximation.
B Proofs of Section
B.1 Proof of Theorem 5
Proof. We denote the time-dependent score function V log ny (x) by sy (x). As derived in Section 2 we initialize X, according to density Pr and run the reverse SDE eq. (5). the density of X, for S denoted by Pr, satisfies the backward PDE:
a,p: = V
(28)
We need to verify that satisfies the above POE.Note that general positive function or satisfies this PDE equivalent to that h, = log P, satisfies the following Hamilton-Jacobi PDE
a, + 2V S, Vh, (x 2s,) (Ah, + 11
(29)
By definition, know h, log n satisfies the above PDE, and we need prove h, log v. log n, - xxx+xTT, F satisfies this PDE as well. Here F(1) denotes the normalizing constant. Taking the difference between two equations, we need
1 /x Qix+x b- (x
+ trace || ||s, exx b,ll2 (30)
9 - x + (00=+++bb++ 20, |1b,112 (ea)
(31)
which can be satisfied by the ODE dynamics
B.2 Derivation of Solution eq.
Sanity Check for the Motivating Example. The ODE ( has the explicit solution
In the denoising setting, we have Qo L bu J.y.
20 la.
Q
1+ 22
Note that this solution has a finite blow-up time when x²2 - 2 0t, which is exactly T" log(1 I o as derived in the main text by matching the SNR. As T 2, cold.
v. exp (x) Tex+x (f N(e," -(C)) e,
To see the limit of e- b,. we only need to consider the ODE for each component since Q is diagonal. So view the above ODE scalar ODEs. Considering the dynamics of
d r 10 10-r r
(32)
d Q2
gives 2, =0 bb. Therefore
lim e, e, b, = - 20 bo = -T
(-(7-
15

---

which matches the initial condition derived in the main text for the denoising case. Furthermore, we can explicitly verify that the intermediate distribution of X, by running the reverse SDE from vy Vy:
Xx p(X))p(Xr =e = y
1lee y- c e- x112
(X, exp
exp
2 e-
yye -x11
ny xx, exp
(33)
22
To match the form of yr, we have Qr -2(7-111 of the ODE (
1tal- Q, b, e which are the solutions
Solution to eq. We recall that the observation operator A E Rd'xd x has general singular
value decomposition form A UEVT with non-zero singular values d1 d2 2 ..... dg 0. By definition, we have Qo = / 2 .., _2, .0.2...... OOVO. By left multiplying V and right multiplying V the first ODE in (9), can diagonalize it to scalar equations è, 2(1 4: 4:)4; for each diagonal entry. Solving this ODE gives
2
2
,0
2 = Vdiag
(34)
1 o 113
1
12 2
We denote V [r],.... val, in which v; eigenvectors of Q (and Q, as well), and denote the eigenvalues of Q, (0 < 1 7*) by
Here we explain how solve b, from eq. 9
2
Isisd d'
1,(1)=
1+ 22
(35)
0.
d'+lsisd
By definition, we know d, satisfies the ODE
== 2(1 1)A.
We rewrite the solution b, Σd (r)rv; and aim solve (i()). From bo VTTT)) have the initial condition
4 (UT y),
isisd d'
(0)
(36)
0.
s+lsish d
Taking the inner product between v; and both sides of the ODE (1 2Q,) have
= (1+ (1)
=
Therefore, for d
d. 1. For s i d', same the derivation eq. 332 we have
a: E: dr T 2,
which gives
E(() -1 (0)
(37)
11(1) 2₂(0)
21
(1)) = -12 d,
(UT y);
(38)
1+02122 221
el
=E(1=
(UTh (UT)).
(39)
2 + 0 122 21)
16

---

Proof of Corollary 6 Given Theorem 5 we only need to prove that sampling from
Vi b, (x) exp - =
equivalent to sampling from new posterior. Taking n, as the corresponding prior, we only need to show that the factor cxp 1-1x² 2xx + x" by) is the likelihood of certain observation model in the form of y A,X + w with w Ya. To end, we need to ensure
1 x 2xx+x
exp(-2 11,,1 5112)
exp
2
Choosing A, in the standard SVD form A, V where the singular values of A, (the diagonal entries of Σ,) are (440-/1j-e-0 - for s d', the quadratic term is matched. Matching the first order term requires b, = A 5 V2, y. Further matching the coefficients in the basis of V requires that
2), = =((1)= 1; + 121 ee2r) y), ssisd.
is easy to verify that y = E,UTy y with Σ diag
satisfies
(1
(orlo)g (1-eat
the above requirement.
Remark 11. Also, one can directly use the backward transport equation the probability flow ODE [58] backward in time
to generate samples with
dx;- (-x; -
log sT, (X; ))
(40)
from X Ydd Combining fact that v, satisfies the PDE (5) and Av, vV V -xxx,- we have that v, also satisfies the transport equation 0; P; = (((((+++((())))))))))) Therefore, for forany any (-(I+ Vlog n, dd
T by initillizing X, Y2 and run the reverse ODEdX; then X5- also gives the desired posterior. However, we note that unlike the reverse SDE case, the corresponding transport PDE and the vector field in the reverse ODE case are different from those used in the prior data generation. As discussed below, both Q₁ and b, are singular near T Therefore running the reverse SDE might be preferrable for better numerical stability.
C Proofs of Section 5
C.1 Proof of Proposition 7
Proof of Proposition)
By definition, we need to show
-Amin (Qr-) + sup Amxx (v2 log (r- (x)) < 0.
(41)
From the argument in the main text, we know T
2 log(1 + Amax (1)- and thus
1 Amax (!)-
Amin (Qr:) Amin (Q) Amax (0)
From Corollary we have
sup Amax 2 log & (1 + (I)I (I -
(42)
Let m = Amin (Q). Therefore, we can guarantee that Y7- is strongly log-concave if
+ -1 m 1| (1 + (ID (11llxiee1 1)
(43)
or equivalently
X1ee (T) < 11 x²(A)
(44)
<²(A) -1
17

---

Lemma 12 (Hessian of Gaussian Mixture Potential), Ler μ Yy be Gaussian mixture. Then
V² Volog (xx) Σー! (Cov (Cov [T--,_-->+ Σ-
Proof. Let us first compute the score V log By definition we have
f /
Vlog = x
(45)
( -(--)))--
=-Σ [Tx--xx-1Hl)
(46)
and thus
v (og = = (Cov [--- E x-1
(47)
where we defined Cov[u] Ex-ulxx"] Corollary 13. In particular, we have
sup Amax V22 logTr-(())) 1 (1 (IlI)) (I@Ilx)en(T) 1))
(48)
Proof. From Lemma
12 and nT, 2 (D De Y1-e-i, we directly have
V2 log n (x) = (1 e -1ー (1 (1-
- 1)
(49)
Now, using the commutation property between the isotropic tilt and the dilation D T7,0 = Tan we have
Cov
(() = Cov [D₂- T -0==
(50)
= [T (-
(51)
and therefore
sup Coov
s e 21 X(62-11-1
(52)
Using that 2T - 11el1 -1, we thus obtain
sup Amax V (r s (1 ((@I)) (I -
(53)
Lemma 14 (Isotropic Tilt of a Gaussian Mixture). If = μ * yo, then
T ui Yo
(54)
where -2 --61 +1 and
a()) & (rr)
(55)
Proof. By definition, have
T f duls)ee fol
By expressing
1 -01111x y112 -1111--11' -
- ||x||| +
-21x - 5112 -- -
have
- -- +1.
(56)
8 +
5= = 8-1+1 +1
(57)
C= 2 lo 1|7l1 8 [|]]]]]
(58)
which gives the desired result after performing the affine change of variables from to 5.
18

---

Proof of Examples 8 The first example is immediate, after observing that T,Y is Gaussian of variance (1 (1+1)=1 For the Gaussian mixture example, we observe from Lemma [4 that (2 * Ys) is a Gaussian mixture of variance (1 5 --- where the mixture distribution is supported in ball of Moreover, the covariance of homogeneous mixture of the form j yx Σ Cov(u).
radius R
6-1 8-14
If j is a product measure, we observe that the isotropic tilt T is also a product measure, and therefore its covariance is diagonal. Finally, by the previous argument, if π is the uniform measure on the hypercube, then X (T) = x6() + 8+1))
Proof of Corollary 10
We plug the spread function Xi (π) = Xi ya) s
(Toee
from T+ar
Example 8 (ii) into
[12 to get (we use A to denote x( ()) for simplicity
x²
R
8
1011
>
(59)
(x2 1)
1+
1 + +11
((1+
(1+81101)
R²
(60)
1121((22-1) 1)
((1 (1++))21)(+++0111) 61le)) R²
(61)
11 II)
(I+ 65K?) SNR 3) > R²
(62)
C.2 Exponential Complexity of Importance Sampling in High SNR Regime
As shown in the main text, the proposed boosted posterior provably works for both low SNR and high SNR regimes. In this section, we formally argue that the importance sampling method is nature baseline for posterior sampling with large noise (low SNR regime). but can suffer from exponential complexity when the SNR is high.
In order to estimate an integral of a function f with respect to the posterior measure
10 10= -fe (x)dd((x)
the idea of importance sampling is to independently sample XI.... X,, from the prior and calculate I, Σ f(X))=(X))
T(X,)
where r.x) is the observation likelihood exp(=f*TQx+x'* xrT)). With the Denoising Oracle, we can sample from the prior efficiently. Intuitively, one think if the posterior and prior are very similar, for example, when or is large such that the ratio r is close to I, In (f) computed from prior samples can efficiently approximate I(f). On the contrary, if o is small, r(x) can have very large variance and the importance sampling can be inefficient since many prior proposals have very small weights. The work [15] Theorem 1.2] proves that, in a fairly general setting, sample of size approximately (PP(LLllll)) is necessary and sufficient for accurate estimation by importance sampling, where KL(vllx) is the -robback-Liiblee divergence of from
KL(vII>) f log
dv dr
dv S (-/x'eexx (-xr'exx=""bjaxc)) b))r(x).
This result confirms one part of the intuition above: if o is sufficiently small, then the magnitude of Q and will be sufficiently small, and is (и|lи) and the number of samples needed in the importance sampling. Next we show that for fairly generic prior distribution æ, when the SNR is large, KL(vl will be also large such that we need approximately (ed-SNR) examples implement importance sampling, which is unachievable.
Without loss of generality, we assume the covariance of the prior is ld-
19

---

Proposition 15 (Importance Sampling Sample Complexity Lower Bound). Assume V Vlog (l) is L-Lipschitz:
V (x) log L||x z||
(63)
Then, when SNR > L L+2, 2, have
KL(v|læ) 2 (d SNR).
(64)
and therefore the sample complexity of IS is exponential in dimension.
Proof. We wish lower bound KL(vll>) with tools of functional inequalities for the concentration of measure. By the celebrated work [0] that the log- sog-ooolev inequality implies the Talagrand transport-entropy inequality, have
((,
KL(vllx) N
(65)
2
Here w(v, denotes the Wassertain distance between and x:
W(v inf ||x yl12dy(x.y). Vee((v.x)
where [(v, π² denotes the set of probability measures on Rd x Rdd with marginals and æ.
First by Equation (63) have
2 (- (SNR L)Id,
(66)
which gives
LSI(v) 2 (SNR- L)
(67)
by Bakry-Emery criterion
3]
Furthermore, have the lower bound for the Wasserstain distance
28
(v, 2 []mean(v) - mean(r)]]* + trace( trace(Cov(v) + Cov(r) ((Cov())
(68)
(Cov(vv))
(69)
trace(DiaggCov//() la (Dog
(70)
((1 3)
(71)
where the second-to- equality comes from the fact that the trace remains unchanged under orthogonal transformation. By (66) and Brascamp-Lieb Inequality (Theorem 16), we have Std(r); v SNR-
With condition SNR L 2,
2 d.
W2 (v, x) 2
(72)
2
Collecting eqs. (65). (67 and 772 obtain final estimate
KI[(V]<>) 2 O(d SNR).
(73)
Theorem 16 (Brascamp-Lieh Inequality, [I]. If nt is strongly-log-concuue measure on Rd, i.e. of the form e with 2 fxx( flr all x E Rd. then [|Cov(z))] =!
20

---

C.3 Stability Analysis
In the numerical implementation of boosted posterior, we typically encounter certain errors. Especially, we may have imperfect score subject to certain L errors, and we may not be able to sample the boosted posterior V, exactly. Suppose that instead of starting from V, f and run the exact reverse SDE (5). we start from an approximate distribution q, s and run the reverse SDE ( with approximating score so(x,1) f) = log π, (x) where 0 denote the parameters parametrizing the score. Denote the distribution of the final samples by 4o, we have the following error estimate
Proposition 17. Suppose Vr. qr, V Vlog Rt, (x(x. 1) has enough regularities such that the reverse SDEs exist, if the Novikov's 's condition [xxp IVlog -s((x, s,((x, +))
co, then
<L((llgo) J IV, log so(x, 2) KI((v1l4.).
(74)
The above proposition ensures that if both the initialization error and score error (over the posterior paths) are small, then the distribution our final samples is close to the target posterior. The proof provided in Appendix C.3 Note that consider the reverse dynamics in continuous-time without
time discretization error. There are various works [44] 45 17 g analyzing the time discretization
error and those techniques can be further incorporated into the above error estimate.
The proof is similar to that in Here we provide the proof in our posterior sampling context for
completeness.
Proef. Consider the following two reverse dynamies needed for the error estimate: one is based on the exact score and starts from the exact boosted posterior
dx, (-X, 2V log x (X+))drr v2dW.. ~
(75)
and another one is based the approximate score and starts from the approximation the boosted posterior
= 2xo r)) + vždW., X, ~ qt-
(76)
Note that these two dynamics are defined backwardly for E [0, and we drop the superscript for notation simplicity. We denote the path measure of {X+)re(o.) and (X+)re(o.r] by and q. respectively. Then and go are the marginal distributions of the two path measures at 0. By data processing inequality and chain rule of KL divergence, we have
KL(vllqo) z (Lil))
(77)
s kv (>>llq7>> + Ez-v, (L =)11q(11
(78)
Given the Novikov's s condition, we can apply the Girsanov theorem [50] to eq. 75) to compute the second term above
Eg-v, =0lq( 2))
(79)
log dq
E
(80)
dv
2 (x)xxx))) J'' [[Vlog=((x)) so(x, r)
E,
(81)
E
n (x) - (x. Pf
(82)
Ey, le.llVoog,,,,p a (x) (x, 1r
(83)
D Iterated Tilted Transport
We have shown that posterior sampling = R can reduced to sampling from VT- by running the reverse SDE, While yr- is easy to sample under the conditions presented in Section 5 these may
21

---

not be verified in several situations of interest. In this context, a natural question is whether one could still leverage the tilted transport, at the expense of introducing sampling error. This is what we address in this section.
Let . be the eigenvalues of Q. Let assume for simplicity that b 0 and all eigenvalues have multiplicity 1, so 2 Ai+1- We define the events Tj for = I.... d given by
Tj log(1 + +27)).
(84)
Denote by
1,(1) = 8o
ifrz
(1(1)) otherwise.
where 2,(1) = (2 eea)) is the solution the ODE á, 2(1 41)9r. By abusing notation, we denote by Ô. T the matrix that shares eigenvectors with Q, and with eigenvalues (d,(t)....,Ad(()), Denote by V2 [vd-k... Val
va] E Rdxk the orthogonal projection onto the last
eigenvectors.
While previously considered only the transport between and V1 := VT7, now can consider the sequence V& T TTr; "Tz for k I.....d. Observe that Mą is measure supported subspace L2 of dimension d k; in other words, where k directions singular, corresponding the eigenvectors associated with the oa eigenvalues of Qr:- and thus Q2 = {x R V yy for some yx IR*
min(k; v: is s.l.c.): that is, the first k such that va is strongly log- concave, and therefore efficiently sampleable by Langevin dynamics. Under the same assumptions as Corollary 10 and by defining Ką AL the condition number of the truncated Q, we immediately obtain the bound
Now, us consider
(1 + (2R) + SNR
k min k:
R²
(85)
K1 -
For k*, assume first that one had sampling access Vk+1. Running the reverse tilted transport for time 17k Te. T would produce samples from a tilted measure V2 := =To . where Qx has eigenvalues (1/ (1x). ... (Tx)) AR+1 (T)) (72)... ................................ (T))), where defined (1) == (e 22 1)- as the inverse of d + $/2 log( 1 + +- is thus a non- non-singular measure in Rd, capturing the fact that the denoising oracle driving the reverse dynamics is isotropic, and thus oblivious to the existence of the singular support yk-
We thus need procedure to transform samples from Ve to samples of The easiest procedure is to simply marginalize the coordinates (xI,..., V R
VA (ALtI........ = Lcc. 8 (dx),....... drt.. P((d-A).
and then 'lift' this measure in the subspace 22 i.e.
(x := 5(x; (x-))
(86)
where we defined X = (XI..... xx) and x .xa)).
We then iteratively run the tilted transport backwards, from k k²- to k 0, as illustrated in Algorithm 2
Algorithm 2 Sampling Using Iterated Tilted Transport
Start by sampling Xx- Vg*.
2: for k = k" to do
3: Run tilted transport starting at Xes1 for time 77, resulting in X.
4: Set X (yx; X-1).
5: end for
6: return Xo
22

---

By the data-pra processing inequality, the TV error will accumulate linearly at each step. Denoting 1 the law of Xo. we have
TV(2,)) S
Σ TV vk..
(87)
Ockck'
This bound can be interpreted as the accumulation of errors arising from conditioning measure by marginalizing over its first components. To the extent that (TTx) is large, these variables are nearly deterministic, so one would expect that marginalization is good approximation of conditioning. The outstanding question is to understand conditions when this error guarantee can be quantified.
Inspired by 18], a natural extension of this simple iterative procedure is to apply 'thermalization' towards the stationary measure Vy after line f of Algorithm above, by running Langevin dynamics in 22g with score V log Vk:
dx, V log (X,)dt+ V2dW, Xn nx.
(88)
The drift of this diffusion is available, since both Qr: and V log मyद are known, so is log VA-
Denote by Vx the law of X, after time f Bx. While the time relaxation of such Langevin dynamics is generally not quantitative (otherwise k- I k), even a short amount of thermalization able to improve upon the previous method. Indced. by the reverse transport inequality [O Lemma 4.2], a weaker Wasserstein guarantee W2(Px, v&) can be 'upgraded' to a TV guarantee of the form TV( V4) = 22 (ft, vx)) by running Langevin dynamies for time B5 @(1/Le), where Lę sup, Amax 2v2 log (x)) > 0 is the largest eigenvalue of V log Vk, which is positive by definition of k* and < k", In summary, the 'thermalized' iterated tilted transport satisfies an error bound of the form
TV(P,v) S Σ
LL v&).
(89)
Ockek
E
Experimental Details
E.1
Gaussian mixture models
For agre dimension d with mod2 2 = O, consider prior data mixture of Gaussian distributions, the same as considered in [[3]. The Gaussian distribution has mean (8i, (8i,8j... 8j..... 8i, 8j) e Rd for (i, E 11, 0, 1, 2,2 and unit variance. Each (unnormalized) mixture weight is independently drawn according to a x² distribution.
For the measurement model considered in Figure 3 we generate A in the following way. We first sample a d d matrix with each entry sampled from the standard normal and compute its SVD to get U and V for A. The singular value is given by [1, 1/20] where each component in between independently sampled from Unif [[1/ 20, 1]) such that the condition number of is 20. The observation noise is then determined by SNR. For the measurement model considered in Table [ the matrix U and V for the SVD form of A is the same to the above. Each singular value in is independently sampled from [ 1)), and or is sampled from Unif([O.2 max S, max S)).
For all the experiments we run the boosted posterior from T 0.01 such that the ODE solution Q, is well-defined. We use BlackJAX [2 to implement the No-U-turn sampler.
Besides results reported in Figure 3 further test tilted transport when d' d. In this setting, Amin (Q.) remains zero but the signal corresponding to the non-zero eigenvalues still gets enhanced. Therefore, although it becomes more difficult for Yy> be strongly log-concave, the tilted transport can still make the new posterior easier to sample even if is not strongly log-concave yet. As shown in Table I when d' 0.9d, 10% percent eigenvalues of Q, are zero, our tilted transport technique still reduces the statistical distance of the posterior samples significantly. We also consider an even more challenging case where d' such that the target posterior still heavlily multimodal (as visualized in the 2D example in Figure 2 In this case, LMC suffers from the local maxima of the potential and thus cannot explore the multimodal distribution efficiently. We use the No-U-turn sampler (34), Hamilton Monte Carlo (HMC) method, as the baseline method, which can move among different modes more efficiently than Langevin. We find that the tilted transport technique can still boost the performance of HMC in this challenging setting. We also verify Theorem 5 by sampling from the boosted posterior directly from analytical formula and running the reverse SDE, and the obtained samples approximate the target posterior well, as reported in Table [
23

---

Table 1: Sliced Wasserstein distance for Gaussian mixture prior for degenerate case
d' 0.9d
d' =
Boosted Langevin
Analytic Boost
Boosted HMC
Analytic Boost
d
Langevin
HMC
20
4.21 = 1.87
2.32 + 2.42
0.02 = 0.00
1.33 1.02
1.11 + 0.83
0.12 = 0.07 0.13 = 0.07
40
4.09 2.02
2.45 + 1.79
0.02 = 0.00
2.04 1.26
1.81 1.03
80
4.40 = 2.31
2.75 + 2.10
0.02 = 0.00
2.98 = 2.15
2.77 + 2.32
0.11 = 0.06
E.2
Imaging Problems
We perform four inverse tasks the Flickr-Paces-HI Dataset (FFHQ) (39 to demonstrate the application of the tilted transport technique on imaging data as a proof of concept. To apply the proposed tilted transport technique to these problems, still need to select baseline method for sampling from the boosted posterior vr. the case of ill-conditioned problems, sampling vr- may still be challenging for principled algorithms like LMC, and still need to rely heuristic methods for imaging tasks. However, as noted in the introduction, most existing heuristic methods primarily facilitate conditional generation based the measurement, lacking principled guarantees for posterior sampling. Consequently, we lack a principled interpretation for enhancing these methods with tilted transport. Nevertheless, We chose Diffusion Model Based Posterior Sampling (DMPS) 48] as the baseline method for the following reasons: The main assumption of DMPS in approximating the time-dependent conditional score is that the prior π is uninformative (flat) with respect to X,, such that p(Xg|X) x p(X, (X)). This assumption only holds approximately early phases the forward diffusion, and hopefully higher SNR provided by tilted transport makes the effect of this approximation error smaller.
still experiment with such methods proof of concept.
We conducted four tasks: (a) denoising; (b) inpainting with random masks from [53]: (c) 4x super-resolution; and (d) deblurring using a Gaussian kernel. Our algorithm was implemented using the NVIDIA codebase [47] with 1000 diffusion steps for posterior sampling, and utilized the score function from pretrained diffusion model [20). Similar to our Gaussian mixture model experiments where we adjusted the timing for the boosted posterior to avoid the singularity of Qr, we shifted 6- 10 timesteps for setting the boosted posterior. Experiments show that the final performance robust with respect the number of shifted steps. Figure showcases examples from the inpainting task. demonstrating how tilted transport enhances the bascline DMPS method. Additionally, we report various sample statisties including peak signal-to-noise ratio (PSNR), structural similarity index (SSIM), and Learned Perceptual Patch Similarity (LPIPS). However, it is important to note that while these statistics assess the quality of prior data generation, they may not accurately reflect the quality of posterior samples.
Table 2: Performance for tasks FFHQ Dataset.
Task Metrics
||
Denoising
Inpainting
Super-resolution
Deblur
DMPS
Boost
DMPS
Boost
DMPS
Boost
DMPS
Boost
PSNR(dB)
32.153
32.350
22.458
23.312
26.761
26.899
29.088
29.155
SSIM T LPIPS 1
0.886
0.886
0.786
0.800
0,760
0.754
0.815
0.815
0.060
0.039
0.131
0.098
0.129
0.109
0.098
0.094
24

---

Original
Observed
DMPS
DMPS from Boosted
Figure 4: Examples for inpainting with random masks over FFHQ dataset
25

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility. transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and precede the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant
information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No] is perfectly acceptable to answer "[No] provided proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA]" is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
(i) Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: This work focuses on provable sampling of posterior distribution with denoising oracles and the proposed tilted transport technique.
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 be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
(ii) Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
26

---

Justification:
See the last section.
Guidelines:
The answer NA means that the paper has no 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 separate "Limitations" section 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 how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets 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, a facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text 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 fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, 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 important role developing norms that preserve the integrity of the community. Reviewers will be specifically instructed
penalize honesty concerning limitations.
(iii) Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
All the details of proof provided in Appendix.
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 or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
(iv)
Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: See Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
27

---

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.
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 specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
Depending on the contribution, reproducibility
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g.. large language model), then there should either be way to access this model for reproducing the results or a way to reproduce the model (e.g.. with open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
(v) Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Code for Gaussian mixture is uploaded in single zip file. Our results on imaging tasks in Appendix E.2 are mainly for a proof-of-concept.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (nttps://nips.co cc/
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 NeurIPS code and data submission guidelines http:///guuiieee/oooeubbmaasssss wooeeSuumisssiooooliiiooo.
for more details.
The authors should provide instructions on 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. If only a 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).
28

---

Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
(vi) 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 optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
See the main text, Appendix (eeendixEEandd and code.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
(vii) 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: In each experiment, we report percentiles or standard deviation.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confidence 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 are 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.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or 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 show in tables figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
(viii)
Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: Our experiments with the Gaussian mixture model require only few seconds per run on a laptop.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
29

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
(ix) Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We conform the the NeurIPS Code of Ethics.
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 a deviation from the Code of Ethics.
The authors should make sure preserve anonymity (e.g.. if there is special consideration due to laws or regulations in their jurisdiction).
(x) Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our paper mainly focuses provable sampling of the posterior distribution.
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 uses (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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate 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 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 correctly. harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or 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 to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
(xi) Safeguards
Question: 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, scraped datasets)?
Answer: [NA]
Justification:
The work poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
30

---

Released models that have 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
(xii) Licenses for existing assets
Are the creators 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: [NA]
Justification: We use open-source packages.
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 dataset.
The authors should state which version of the asset 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 (e.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 of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information not available online, the authors are encouraged to reach the asset's s creators.
(xiii) New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [No]
Justification:
No new asset is released.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model 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.
(xiv)
Crowdsourcing and Research with Human Subjects
Question: For crowdsoureing 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]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
31

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
(xv)
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]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
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 NeurIPS 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.
32


Reviews:
[{"review_id": "ZMoImeTikv", "reviewer": "Reviewer_ue87", "summary": "The paper \"Provable Posterior Sampling with Denoising Oracles through Tilted Transport\" analyses the possibility of posterior sampling utilizing denoising oracles, such as score-based diffusion models. To demonstrate the possibilities the authors focus on linear inverse problems and propose the tilted transport technique. It uses the quadratic log-likelihood structure of linear inverse problems together with the oracle to transform the original posterior into one easier to sample. Based on the example of the Ising model the authors show that well-conditioned measurements allow the transport to simplify the task. Furthermore, first empirical tests for image tasks indicate promising practical use.", "questions": "What is the reason for the peak with large percentiles for 10^-3 SNR in Figure 3?", "limitations": "yes", "rating": 8, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Well written and well structured with proofs. Potential for impact is high", "weaknesses": "The topic is far from my expertise. I cannot see obvious weaknesses for this analysis. It has its limitations, but it is clearly stated and argued by the authors.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer very much for the time and effort spent in reviewing our paper, and for the positive evaluation.  Below we address your specific question. \n\n> What is the reason for the peak with large percentiles for 10^-3 SNR in Figure 3?\n\nThe peak observed with large percentiles for an SNR of $10^{-3}$ in Figure 3 is precisely predicted by our theoretical analysis in Corollary 10. The text following Corollary 10 and Figure 2 provides a detailed interpretation of this result. Specifically, given a prior and $\\kappa(A)$, the target posterior can be reliably sampled if the SNR is either sufficiently low or high, as the sufficient condition in Corollary 10 is met. However, for moderate SNR values, the sufficient condition in Corollary 10 may not be satisfied. Consequently, while the transported measure $\\nu_{T^*}$ may be easier to sample than $\\nu_0$, it may still pose challenges for Langevin Monte Carlo sampling. As a result, the final statistical error between our samples and the target posterior might be larger for moderate SNRs compared to extremely low or high SNRs. The peak observed for an SNR of $10^{-3}$ in Figure 3 provides strong numerical verification of our theoretical predictions.", "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": "boOFRGZiL0", "reviewer": "Reviewer_G6DH", "summary": "This paper proposes a novel posterior sampling algorithm specialized to linear inverse problems. The proposed algorithm relies on a sequence of intermediate and **tractable** posterior distributions $\\nu_t$ that satisfy a transport equation up to some time $T^*$. The algorithm then operates as follows; first draw approximate samples from the distribution $\\vu_{T^*}$ using any approximate inference algorithm, and then run the reverse SDE from $T^*$ to $0$ starting at the obtained samples. Of course, the computational hardness is transferred to $\\nu_{T^*}$ and the authors derive sufficient conditions that ensure it is strongly log concave. The study of the algorithm is then specialized to both the Ising model and Gaussian mixtures. They show for example that $\\nu_{T^*}$ is strongly log-concave for the Ising model under the condition that the eigenvalues difference is smaller than 1, thus providing a new efficient continuous time procedure for sampling from it.", "questions": "N/A", "limitations": "N/A", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Overall, this paper is highly original and I greatly appreciated reading it. It has quite a few contributions and the proposed main algorithm is interesting. The writing is clean so that the paper is relatively easy to understand, while still sufficiently detailed. The properties of the algorithm are well investigated throughout the Ising model and Gaussian mixture examples.", "weaknesses": "There isn’t any serious weakness; perhaps I would have liked to see more challenging experiments and comparisons with denoising diffusion based posterior sampling algorithms, but in my opinion this is optional for this paper, since it is more on the theoretical side and has strong contributions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer very much for the time and effort spent in reviewing our paper, and for the positive evaluation.", "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": "uqnLSHqbhK", "reviewer": "Reviewer_jPCg", "summary": "The paper presents a theory regarding posterior sampling in linear inverse problems with additive Gaussian noise. It provides two major contributions:\n\n* A proof that no general algorithm exists for posterior sampling of Ising models when the degradation operator is ill-conditioned.\n* A transport equation for the coefficients of the quadratic form of the posterior distribution in the linear setup, transforming it into a new distribution that is easier to sample from. This includes conditions on SNR and condition number for strong log-concavity of the transformed probability, allowing for efficient sampling.\n\nThe authors illustrate their theoretical results with a toy example with Gaussian mixture model.", "questions": "Please address weaknesses.", "limitations": "The limitations of the work, e.g. the focus on linear setups, are only briefly mentioned in the discussion section. This warrants a more extensive and dedicated discussion to adequately address their implications.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper effectively presents the problem and necessary background, along with detailed and rigorous derivations.\n* In the context of the linear setup, the paper presents impactful and theoretically sound results regarding posterior sampling.", "weaknesses": "* Figure 1 and its description are not clear. I would expect it to clearly summarize the essence of the work, particularly highlighting the second contribution.\n\n* While the paper contains rigorous derivations, it lacks intuitive explanations and simplified examples, making it difficult for readers to understand the overall direction and implications of the work as they read.\nThis lack of accessibility limits the paper's potential audience.  \n\n* The focus on linear problems with additive Gaussian noise limits the practicality and potential impact of the work.\n\n* The lack of a practical algorithm for implementing the tilted transport map limits the applicability of this work.\n\n* The authors' decision to place the extension to nonlinear setups and imaging experiments to the appendix is puzzling, as these results are compelling and could strengthen the paper's main arguments if presented in the main body.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and effort in reviewing our submission. We will do our best below to address your concerns and queries.\n\n> Figure 1 and its description are not clear. I would expect it to clearly summarize the essence of the work, particularly highlighting the second contribution.\n\nOur technique is based on the following two proven facts:\n\n1. We can construct a time-dependent family of likelihoods $\\nu_t \\propto \\exp\\left(-\\frac{1}{2} x^\\top Q_t x + x^\\top b_t\\right)$ such that at $t=0$, this likelihood matches our desired posterior.\n\n2. The same reversed SDE dynamics used in prior data generation can transport this time-dependent likelihood from $T^*$ to 0 exactly. We have proven that $\\nu_{T^*}$ is much easier to sample than $\\nu_0$.\n\nFigure 1 is intended to demonstrate our technique in the Gaussian mixture case, where the bottom row represents our technique and the top row represents the standard prior data generation. We will revise the description of Figure 1 to better explain this.\n\nThe second fact highlights the advantages of our method: if we ignore time discretization error, a single step of the reverse SDE over $\\delta t$ directly moves the sample from $\\nu_{t+\\delta t}$ to $\\nu_t$ in the distributional sense. In contrast, with two distributions having noise levels $\\sigma_{t+\\delta t}$ and $\\sigma_t$, we can only ensure that these distributions are close, but moving from one to the other may require multiple steps of Langevin Monte Carlo, which is much less efficient.\n\n\n\n> While the paper contains rigorous derivations, it lacks intuitive explanations and simplified examples, making it difficult for readers to understand the overall direction and implications of the work as they read. This lack of accessibility limits the paper's potential audience.\n\nThank you for your comments. We intended to use the paragraph \"A Motivating Example\" at the beginning of Section 4 as a simplified example to provide readers with some intuitive explanations. For this example, most methods in the literature cannot sample the posterior exactly, while our tilted transport technique can solve this task elegantly as a special case. We will better illustrate this intuition using this example in the revision.\n\n> The focus on linear problems with additive Gaussian noise limits the practicality and potential impact of the work.\n\nWhile our primary focus is on linear problems with additive Gaussian noise, it's worth noting that additive Poisson noise, another common type of noise in the literature, can be well approximated by Gaussian noise with high accuracy; see [1]. Thus, our method is also applicable to Poisson noise. We acknowledge that our results are heavily dependent on the linear structure of the problem, which allows us to derive a principled and provable posterior sampling algorithm. To the best of our knowledge, there is currently no principled algorithm for nonlinear problems, even when using a Gaussian mixture as the prior. The only exceptions might be methods based on sequential Monte Carlo, which guarantee asymptotic performance but may require an impractically large number of particles. Therefore, we believe that developing a principled algorithm for nonlinear problems remains an open challenge for future research.\n\n[1] Chung et al. “Diffusion Posterior Sampling for General Noisy Inverse Problems”, ICLR 2023.\n\n> The lack of a practical algorithm for implementing the tilted transport map limits the applicability of this work.\n\nWe provide a description of the algorithm in the PDF for the global response.\n\n> The authors' decision to place the extension to nonlinear setups and imaging experiments to the appendix is puzzling, as these results are compelling and could strengthen the paper's main arguments if presented in the main body.\n\nWe would like to clarify that our appendix does not address any nonlinear setups. The iterated tilted transport discussed in Appendix C is still about linear problems but with even larger condition numbers, in which the boosted posterior $\\nu_{T^*}$ may still be challenging to sample. While this idea is promising, it is still relatively immature compared to the one-round tilted transport presented in the main text. Therefore, we believe it is more appropriate to include it in the appendix to highlight a potential future direction without causing unnecessary confusion.\n\nWe appreciate the positive evaluation of our imaging experiments. These experiments are promising but also preliminary. Our main paper primarily focuses on *provable and principled* posterior sampling based on score-based diffusion models. For imaging problems, although we demonstrated that the boosted posterior $\\nu_{T^*}$ is easier to sample than $\\nu_0$, $\\nu_{T^*}$ may still present significant sampling challenges, leading to non-negligible errors. Consequently, a deeper investigation is required to understand how the tilted transport technique performs when $\\nu_{T^*}$ has such errors. Therefore, we have decided to focus the main text on the theoretical aspects and include the imaging experiments in the appendix as potential future directions.", "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": "u8iXZNSsBn", "reviewer": "Reviewer_SHHR", "summary": "This work studies posterior sampling using unconditional diffusion models, or denoising oracles. The authors propose a \"tilted transport\" technique to combine a linear inverse problem and denoising oracles into a \"boosted\" posterior sampling problem. The authors study the feasibility of \"boosted\" posterior sampling with respect to properties (e.g. singular values) of $A$ (or $A^\\top A$), the measurement operator. They devise conditions on these properties for which \"boosted\" posterior sampling is tractable.", "questions": "* To my understanding, simulating the reverse SDE Eq. (3) from $T$ to $0$ only generates samples from $\\pi_0$ if $\\pi_t$ is the measure defined by applying the Ornstein-Uhlenbeck process to $\\pi_0$, i.e. $\\pi_t = C_{\\beta_t} D_{\\alpha_t} \\pi_0$. Therefore, for $\\nu_t = T_{Q_t, b_t} \\pi_t$ to generate samples from $\\nu_0 = T_{Q, b} \\pi_0$ with the reverse SDE, it would be necessary that $\\nu_t = C_{\\beta_t} D_{\\alpha_t} \\nu_0$. Is this the case?\n\n* What is the relationship of $\\nu_t$ with previous heuristics [1-4] ?\n\n### Typos\n\n* Line 110, $w \\sim \\gamma_{d'}$\n* Line 122, $Q = \\sigma^{-2} I_d$\n* Line 222, $p(\\tilde{y} | x) = p(X_{T^*} | X_0)$", "limitations": "See weaknesses.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 1, "contribution": 3, "strengths": "* The subject (posterior sampling from denoising oracles) is interesting and relevant to the ML community.", "weaknesses": "* The presentation of this manuscript is very poor. First, the formulation is very different from other diffusion (or generative) models papers, with unusual notations and concepts, some of which are undefined in the text (e.g. quadratic tilt or $\\ll$ at line 99). Second, it feels like the authors use this different formulation to purposely obfuscate their contribution. If I understand correctly, the \"tilted transport\" technique is an annealing of the likelihood $p(y | x_t)$ with respect to the added noise $\\sigma_t^2 = 1 - \\exp(-2t)$, such that it converges to $p(y | x)$ as $t$ goes to $0$. This is similar to previous works [1-4], but because the notations are so different, it is impossible for the reader to compare them. The authors should provide a thorough comparison of their method (preferably using standard formulation) with these previous works [1-4].\n\n* In the introduction (lines 40-46), the error of previous works using heuristics (including [1-4]) is not \"uncontrollable\" but not analyzed. In fact, Rozet et al. [3] propose a sampling scheme that is exact for enough LMC (Langevin Monte Carlo) corrections steps. I don't see how this \"contrasts with the principled sampling used in prior data generation\".\n\n* There is no algorithm to concisely describe the method. The provided code does not help as it is undocumented and frankly messy.\n\n* The tilted transport technique is not applicable to any distribution $\\pi$. In particular, sampling from $\\nu_{T^*}$ is only possible in contrived settings. For most distributions $\\pi$ and most measurement matrix $A$, sampling from $\\nu_{T^*}$ is as hard as sampling from $\\nu_0$.\n\n* The experiments are not relevant for most general linear inverse problems. The prior distributions are low-dimensional ($d \\leq 80$) mixture of few (25 components) Gaussians. The condition number of $A^\\top A$ is controlled ($\\kappa = 20$).\n\n* In appendix, the authors compare their method with Meng et al. [5] which is a quite poor (and not peer-reviewed) baseline. Better baselines [1-4] are not considered.\n\n[1] Song et al. \"Pseudoinverse-Guided Diffusion Models for Inverse Problems\". In International Conference on Learning Representations. 2023.\n\n[2] Finzi et al. \"User-defined Event Sampling and Uncertainty Quantification in Diffusion Models for Physical Dynamical System\". In International Conference on Machine Learning. 2023.\n\n[3] Rozet et al. \"Score-based Data Assimilation\". In Advances in Neural Information Processing Systems. 2023.\n\n[4] Adam et al. \"Posterior samples of source galaxies in strong gravitational lenses with score-based priors\". 2022.\n\n[5] Meng et al. \"Diffusion model based posterior sampling for noisy linear inverse problems\". 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our submission. We regret that you have a rather negative view of the paper. It seems to us that there are some fundamental misunderstandings of our tilted transport technique. We hope that our clarifications below, as well as the other reviews, can help resolve these misunderstandings. Below we address specific questions. The response is split due to length constraints.\n\n> The presentation of this manuscript is very poor. First, the formulation is very different from other diffusion models papers, with unusual notations and concepts, some of which are undefined in the text (e.g. $\\ll$ at line 99). Second, it feels like the authors use this different formulation to purposely obfuscate their contribution. If I understand correctly, the \"tilted transport\" technique is an annealing of the likelihood $p(y|x_t)$ with respect to the added noise $\\sigma_t^2 = 1-\\exp(-2t)$, such that it converges to $p(y|x)$ as $t$ goes to 0. This is similar to previous works [1-4], but because the notations are so different, it is impossible for the reader to compare them. The authors should provide comparison of their method with these previous works].\n\nWe would like to first clarify that our formulation of the score-based diffusion in terms of the Ornstein–Uhlenbeck (OU) forward process is quite standard and is also known as variance preserving. As further explained in the footnote, the commonly used noise schedule $dX_t = -\\beta(t)X_t~dt + \\sqrt{2\\beta(t)}dW_t$ can be interpreted as a time-rescaled version of the standard OU process, ensuring that all our results directly apply.\n\nSecond, we clarify that the \"tilted transport technique\" is not equivalent to annealing the likelihood, if by \"annealing\" the reviewer refers to a process that adjusts noise levels or, equivalently, temperature. In contrast, our technique operates based on the following two facts that we prove:\n\n1. We can construct a time-dependent family of likelihoods $\\nu_t \\propto \\exp\\left(-\\frac{1}{2} x^\\top Q_t x + x^\\top b_t\\right)$ such that at $t=0$, this likelihood matches our desired posterior.\n\n2. The same reversed SDE dynamics used in prior data generation can transport this time-dependent likelihood from $T^*$ to 0 exactly, and we can prove that $\\nu_{T^*}$ is much easier to sample than $\\nu_0$.\n\nThe second fact above also highlights the advantages of our method: if we ignore time discretization error, a single step of the reverse SDE over $\\delta t$ directly moves the sample from $\\nu_{t+\\delta t}$ to $\\nu_t$ in the distributional sense. In contrast, if we have two distributions with noise levels $\\sigma_{t+\\delta t}$ and $\\sigma_t$, we can only ensure that these two distributions are close, but moving from the former to the latter may require multiple steps of Langevin Monte Carlo, which is much less efficient. Further discussion on this point is provided in our reply to the third point.\n\nFinally, we would like to clarify that for two measures $\\nu$ and $\\mu$, the notation $\\nu \\ll \\mu$ is a standard notation in measure theory, indicating that $\\nu$ is absolutely continuous with respect to $\\mu$, meaning the Radon–Nikodym derivative $\\frac{d\\nu}{d\\mu}$ exists. More details can be found at Radon–Nikodym theorem.\n\n> What is the relationship of $\\nu_t$ with previous heuristics [1-4]?  \n\nOur $\\nu_t$ is fundamentally different from previous heuristics [1-4]. We have established that if an accurate score is obtained from training on prior data, one can (1) first sample $\\nu_{T^*}$ and (2) run the reverse dynamics from $T^*$ to 0 to get samples from $\\nu_0$. We provide sufficient conditions under which $\\nu_{T^*}$ allows for fast sampling, ensuring that the total cost of both steps is low while the final result is accurate.\n\nIn contrast, heuristics [1-4] encounter significant approximation errors. They assume that the probability $p(x_t | x_0)$ follows a Gaussian distribution with its mean given by Tweedie’s formula. This assumption is generally not true, even for a simple Gaussian mixture prior. Without LMC corrections, achieving accurate sampling with these methods requires extreme conditions. If LMC corrections are used, it is difficult to estimate in advance how many correction steps are needed to guarantee accurate sampling. Our method, therefore, offers a more principled and efficient approach with clear conditions for achieving accurate results.\n\n\n> In the introduction (lines 40-46), the error of previous works using heuristics (including [1-4]) is not \"uncontrollable\" but not analyzed. In fact, Rozet et al. [3] propose a sampling scheme that is exact for enough LMC (Langevin Monte Carlo) corrections steps. I don't see how this \"contrasts with the principled sampling used in prior data generation\".\n\nThe difference between our method and other heuristics has been clarified above. We agree with the reviewer that if one uses enough LMC correction steps, the algorithm in Rozet et al. can be nearly exact. In fact, for any sampling algorithm, augmenting it with enough LMC steps will result in nearly exact samples — even running LMC directly on the posterior likelihood. \nHowever, we believe such a guarantee is insufficient since the required number of LMC correction steps can be unfeasibly large without isoperimetry assumptions. For instance, sampling a Gaussian mixture using LMC may take an exponential number of steps in relation to the dimension.\n\nIn contrast, the prior data generation in score-based diffusion is substantially more powerful, as it comes with quantitative error bounds for every source, including initialization error, time discretization error, and score estimation error. The goal of our paper is to achieve a similar level of quantitative control for posterior sampling. Specifically, we provide explicit conditions ensuring that $\\nu_{T^*}$ is log-concave, allowing LMC to sample it with fast convergence, and the remaining cost associated with tilted transport is similar to prior data generation.", "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:
We would like to thank all reviewers for their time and effort in reviewing our paper and for providing valuable suggestions that imrpove the draft. We address most points raised by individual reviewers in separate rebuttals. **Here we attach a line-by-line description of our tilted transport algorithm in the PDF to clarify the confusion of the algorithm from two reviewers.**

To further clarify, in our paper, we provide explicit conditions ensuring that the boosted posterior $\nu_{T^*}$ is log-concave, which allows Langevin Monte Carlo (LMC) to sample it with fast convergence. The cost associated with tilted transport is comparable to prior data generation. This feature stands in contrast to most existing methods that rely on LMC or particle methods to guarantee accuracy. In those methods, the number of LMC steps or particles required is hard to estimate a priori and can potentially grow exponentially with the dimension.

Meta-review: The paper presents a method for posterior sampling using a tilted transport method and focusing on linear inverse problems. Four reviewers all agreed that the paper was above threshold for acceptance and not a borderline case. While one strong accept was very low confidence and both strong accepts were light in content, the consensus indicates that the paper should be accepted. One reviewer who initially had concerns was convinced to change their view during the feedback period interaction.  The paper is technically interesting and novel and should be accepted.
Decision: Accept (poster)