Posterior Sampling by Combining Diffusion Models with Annealed Langevin Dynamics
Authors: Zhiyang Xun
Shivam Gupta
Eric Price
Venue: NeurIPS 2025 poster ()
Keywords: Diffusion Models
Posterior Sampling
Langevin Dynamics
Compressed Sensing
Primary area: theory

Abstract: Given a noisy linear measurement $y = Ax + \xi$ of a distribution $p(x)$, and a good approximation to the prior $p(x)$, when can we sample from the posterior $p(x \mid y)$? Posterior sampling provides an accurate and fair framework for tasks such as inpainting, deblurring, and MRI reconstruction, and several heuristics attempt to approximate it. Unfortunately, approximate posterior sampling is computationally intractable in general.

To sidestep this hardness, we focus on (local or global) log-concave distributions $p(x)$. In this regime, Langevin dynamics yields posterior samples when the exact scores of $p(x)$ are available, but it is brittle to score--estimation error, requiring an MGF bound (sub‑exponential error). By contrast, in the unconditional setting, diffusion models succeed with only an $L^2$ bound on the score error. We prove that combining diffusion models with an *annealed* variant of Langevin dynamics achieves conditional sampling in polynomial time using merely an $L^4$ bound on the score error.

Posterior Sampling by Combining Diffusion Models with Annealed Langevin Dynamics
Zhiyang Xun UT Austin 2xun0cs. utexas.edu
Shivam Gupta
Eric Price
UT Austin" shivanguptaautexas.ccu
UT Austin & Microsoft Research ecpricedcs utexas. edu
Abstract
Given a noisy linear measurement = Az + & of a distribution p(z), and a good approximation to the prior p(z), when can sample from the posterior p(æ y)? Posterior sampling provides an accurate and fair framework for tasks such as inpainting, deblurring and MRI reconstruction, and several heuristics attempt approximate it. Unfortunately, approximate posterior sampling is computationally intractable in general.
To sidestep this hardness, we focus on (local or global) log-concave distributions p(z). In this regime, Langevin dynamics yields posterior samples when the exact scores of p(x) are available, but brittle score ecore-estimation error, requiring MGF bound (sub-exponential error). By contrast, in the unconditional setting, diffusion models succeed with only an L bound on score error. prove that combining diffusion models with an annealed variant of Langevin dynamics achieves conditional sampling in polynomial time using merely an L bound on the score error.
Introduction
Diffusion models are currently the leading approach to generative modeling of images. Diffu- sion models are based learning the "smoothed scores" sz²(x) of the modeled distribution p(x). Such scores can be approximated from samples of p(z) by optimizing the score matching objec- tive [HD05]: and given good L -aaproximatiins the scores, p(x) can be efficiently sampled using an SDE [SE19, HJA20, SSDK 21] or an ODE [SME20).
Much of the promise of generative modeling lies in the prospect of applying the modeled p(xr) as a prior: combining with some other information to perform a search over the manifold of plausible images. Many applications, including MRI reconstruction, deblurring, and inpainting, can be formulated as linear measurements
= Ax E for E A0 Im)
(1)
for some (known) matrix xd Posterior sampling. or sampling from p(æ y), is natural and useful goal. When aiming to reconstruct I accurately, it is 2-competitive with the optimal in any
metric [JAD*2] 21] and satisfies fairness guarantees with respect to protected classes [JKH*2] 221..
Researchers have developed a number of heuristics to approximate posterior sampling using the smoothed scores, including DPS [CKM+23], particle filtering methods [WTN+22 23, DS24], Diff- PIR [ZZL= [23,, and second-order approximations [RCK+24], Unfortunately, unlike for uncondi- tional sampling, these methods do not converge efficiently and robustly the posterior distribution. In fact, a lower bound shows that no algorithm exists for efficient and robust posterior sampling in
Now at Google DeepMind.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

However, Langevin dynamics adapts very well to posterior sampling: it works for posterior sam- pling under exactly the same conditions as it does for unconditional sampling. The difference from diffusion models is that the unsmoothed conditional score so(x | y) be computed from the general 24]. But the lower bound uses an adversarial, bizarre distribution p(z) based on one- way functions; actual image manifolds are likely much better behaved. Can we find an algorithm for provably efficient, robust posterior sampling for relatively nice distributions p? That is the goal of this paper: we describe conditions on p under which efficient, robust posterior sampling is possible.
A close relative to diffusion model sampling is Langevin dynamics, which is a different method for sampling that uses an SDE involving the unsmoothed score so. Unlike diffusion, Langevin dynamics is in general slow and not robust to errors in approximating the score. To be efficient, Langevin dynamics needs stronger conditions, like that p(z) is log-concaye concave and that the score estimation error satisfies an MGF bound (meaning that large errors are exponentially unlikely).
unconditional score 8n (x) and the explicit measurement model p(y xt), while the smoothed condi- tional score (which diffusion needs) cannot be easily computed.
So the current state is: diffusion models are efficient and robust for unconditional sampling, but essentially always inaccurate or inefficient for posterior sampling. No algorithm for posterior sam- pling is efficient and robust in general. Langevin dynamics efficient for log-concave distributions, but still not robust. Can make robust algorithm for this case?
Can we do posterior sampling with log-concave p(x) and L L'-accurate scores?
1.1 Our Results
Our first result answers this in the affirmative. Algorithm uses a diffusion model for initialization, followed by annealed version of Langevin dynamics, to do posterior sampling for log-concave p(z) with just Laccurreeee scores. Annealing is necessary here; see Section F for why standard Langevin dynamics would not suffice in this setting.
Assumption 1 (I,4 score accuracy). The score estimates (x)(x)) of the smoothed distributions (x=(x) = p(x)) * (V TaTa) have finite 1,A error, i.e.,
E (²2(1)
- (00(1)) S Excore < co.
Theorem 1.1 (Posterior sampling with global log-concavity). Let p(x) be an a-strongly log- concave distribution over I&d with L-Lipschitz score. For any E < 1, there exist Kı poly(d, m, n 2) and K2 = poly(d, m, nya" algorithm that takes K2 iterations sample from a distribution $(1 y) with
va LAIl, 1 b) such that: e S K, then there exists an
E [TV(p< 1 p(z v))] S.
For precise bounds on the polynomials, see Theorem E.6. To understand the parameters, qya be viewed as the signal-to-noise ratio of the measurement.
|||l|
should
Local log-concavity. Global log-coneavity, required by Theorem 1.1, is simple to state but fairly strong condition. In fact, Algorithm only needs a local log-concavity condition.
As motivation, consider MRI reconstruction. Given the MRI measurement y of æ, we would like to get as accurate an estimate of x as possible. We expect the image distribution p(x) to concentrate around a dow-dimensional manifold. We also know that existing compressed sensing methods (c.g., the LASSO [Tib96, CRT06]) can give a fairly accurate reconstruction zo; not as accurate as we are hoping to achieve with the full power of our diffusion model for p(x), but still pretty good. Then conditioned on To, we know basically where x lies on the manifold; if the manifold is well behaved, only really need to do posterior sampling distribution on this branch can be log-concave even when the overall p(x) is not.
single branch of the manifold. The posterior
In the theorem below, we suppose we are given a Gaussian measurement un = x + -N10 for some a, and that the distribution p is nearly log-concave ball polynomially larger than a. We can then converge to p( Zo. y).

---

Density p(x)
Anax(Vllogp(x) (Clipped: 300)
Circle-Gaussian Mixture (w= 0.1)
Circle-Gaussian Mixture
1.5
1.5
0.600
275.5
1.0
0.525
1.0
244.9
E Eigenn eeavalue
0.5
0.450
0.5
214.3
0.375
183.7
0.0
0.0
153.1
0.300
122.4
-0.5
0.225
0.5
91.8
0.150
61.2
-1.0
0.075
110
30.6
0.0
-1.5 -1
0.000
-1.5
-1
(a) Density of p. uniform distribution over unit circle (white), convolved with (O, 12).
(b) Amax (V² log p(x)) reaches (21//// ter, demonstrating strong non-log-coneavigg
/w") near the cen-
Figure 1: A "locally nearly log-concave" distribution suitable for Theorem 1.2: uniform the unit circle plus (00, 12). The Hessian's 's largest eigenvalue is much smaller near the bulk of the density than it is globally. Specifically, for |||||// /n 0(1), a Gaussian measurement T with S ow and Escore S cw-1 for small enough > enables sampling from p(æ v)
Theorem 1.2 (Posterior sampling with local log-concavity). For any E, R, 0, suppose p(x) is distribution over Rd such that
Pr [Vo E B(x', R): - -lla 3 V logp(r) ( 2 - 1 Z'pp
Then, there exist K1, K2 poly(d, (d, LA 1) and K3 poly(d, m, ||alo 1 L. such that: " Given a Gaussian measurement Fo = x + (00, IaIa) of x ~ with a S R/(K3 + 2T). If Ewore S Kaa' then there exists algorithm that takes K3 iterations sample from distribution p(x zo. y) such that
" '8
E 2
[fV
zo, v). zo, 8))l Se.
If is globally log-concave, we can set but we have local information then this just needs local log-concavity. For precise bounds and detailed discussion of the algorithm, see Section E.2.
xn is independent of and recover Theorem 1.1;
The largest eigenvalue of V log p(z) quantifies the extent which the distribution departs from log-concavity at a given point. In Figure I, we show an instance of a locally nearly log-concave distribution: uniformly on the unit circle plus ((0, I²)2). This distribution is very far from globally log-concave but it is nearly log- log-concave within w-ditth band of the unit circle. See Section E.4 for details.
Compressed Sensing. In compressed sensing, one would like to estimate æ as accurately as pos- sible from y. There many algorithms under many different structural assumptions on æ, most
Table 1: Summary of theorems and corresponding algorithms.
Theorem
Setting
Method
Target
Thcorem 1.1
Global log-concavity
Algorithm
p(æ v)
Run Algorithm using p( xa) the prior
Local log-concavity with
Theorem 1.2
p(x wo,
Gaussian measurcment zo
(Algorithm 2)
Run Algorithm but replace ao with zó zo + (/(0, o 1a) (Algorithm 3)
Local log-concavity with arbitrary noisy measurement
Corollary 1.3
small ||a - æo
3

---

Figure 2: Corollary 1.3 sampling process. Given the distribution p(r) and measurement we (1) start with a warm start estimate To. which may not lie the effective manifold containing p(a)); (2) use the diffusion process to sample from p(x) in ball around zo, getting #1 on the manifold but not matching y; and finally (3) use annealed Langevin dynamics to converge p(x y). This works
p(æ) is locally close to log-concave, even if it is globally complicated. See Section E.3 for a more detailed discussion.
notably the LASSO x known to be approximately sparse [Tib96, CRT06J. The LASSO does not much information about the structure of p(r), and one hope for significant improvements when p(z) known. Posterior sampling is known to be near-optimal for compressed sensing: any algorithm achieves r error with probability 1 - 6, then posterior sampling achieves at most 2r error with probability 26. But, as we discuss above, posterior sampling cannot be efficiently computed in general.
We can use Theorem 1.2 to construct a competitive compressed sensing algorithm under a "local" log-concavity condition on p. Suppose we have a naive compressed sensing algorithm (e.g., the LASSO) that recovers the true x to within It error; and p is usually log-concave within an R poly ball; then if any exponential time algorithm can get error from y, our algorithm gets 2r error in polynomial time.
Corollary 1.3 (Competitive compressed sensing). Consider attempting accurately reconstruct from y = Ax + E. Suppose that:
Information theoretically (but possibly requiring exponential time using exact knowledge
of p(x)), it is possible to recover from y satisfying || - x|| S r with probability 1 over p and y.
We have access to "naive" algorithm that recovers from y satisfying I|~0 x1| S R with probability
over x ~ and y.
For R' = R. poly m, 7
||A|R 1)
V B(x R)) LI, V2 lolgp((z) = _0] 2 8- x'>p
Pr
Then we give an algorithm that recovers &o satisfying || - xl| S with probability 0()), in poly(d, m. | n +8) time, under Assumption 1 with Escore < poly(d, A LRR))
That is, we go from a decent warm start to a near-optimal reconstruction, so long as the distribu- tion locally log-concave, with radius of locality depending on how accurate our warm start To our knowledge this is the first known guarantee of this kind. Per the lower bound [GJP+24], such guarantee would be impossible without any warm start or other assumption.
Figure illustrates the sampling process of Corollary 1.3. The initial estimate xo may lie well out- side the bulk of p(z); with just an L error bound, the unsmoothed score at 2g could be extremely bad. We add a bit of spherical Gaussian noise to .p. then treat this as a spherical Gaussian measure- ment of x, i.e., x + (0, RI); for spherical Gaussian measurements, the posterior p(z xx) can be sampled robustly and efficiently using the diffusion SDE. We take such a sample 21, which now won't be too far outside the distribution of p(r), then use xi as initialization for annealed Langevin dynamics to sample from p(x y). The key part of our paper is that this process will never evaluate a score with respect to a distribution far from the distribution was trained on, so the process robust error in the score estimates.

---

Algorithm Sampling from p( Ar (0, T =
1:
function POSTERIORSAMPLERIP R2 + IR E R"", E Ro 1f E IR) 7|N = 17 and 7 Ti....: TN-1 be an admissible schedule.
2: Let 7] > 7/2
3: Initialize yN = y
4: for i
down do Vi y--1 + (00, (n M mm)
5:
6:
end for
7:
Sample 11 ((x)
Approximately, using the diffusion SDE (5)
8:
for i= N 1 do
9:
Let 8++1 be the estimated score function for s1+1(1)) = V log p(x 15+1).
10:
Initialize 2g X,
11:
Simulate the SDE for time T;:
dx. = 8 (1) de + v2dB.
(2)
12:
Here, It. Le/Ae/ is the discretized Ii, where h is small enough step size. Set X,+1 <- TT.
(b)
13:
end for
15:
Return: XN as an approximation of p( Ar - (O, (m) = v).
end function
We summarize results in Table 1.
Notation and Background
We consider x ~ p(x) over Rd. The "score function" s(x) of p V Vlog((x). The "smoothed score function" (2) is the score of (x=( p(x)
Unconditional sampling. There are several ways to sample from p using the scores. Langevin dy- namics is a classical MCMC method that considers the following overdamped Langevin Stochastic Differential Equation (SDE):
dX; s(x)ddt V2dBe.
(3)
where B, is standard Brownian motion. The stationary distribution of this SDE is p. and discretized versions of it, such as the Unadjusted Langevin Algorithm (ULA), are known converge rapidly to p(z) when p(x) is strongly log-concave [Dal17]. One can replace the true score s(x) with an approximation 8, as long as satisfics a (fairly strong) MGF condition
E (t)p(a))
Texp (II=(x) /6
< oo, for some Emgf >> 0.
(4)
In particular, [YW22] showed that Langevin dynamics needs an MGF bound for convergence, and an IPPaccurate score estimator for any S < oo is insufficient.
An alternative approach, used by diffusion models, is to involve the smoothed scores. Starting from 2o ~ (0, Ia), one can follow a different SDE [And82]:
dxX, = (X, + 2, (X.)) + V2dB,
(5)
for a particular smoothing schedule o;: the result xr exponentially close (in T') to being drawn from p(r). This also has efficient discretizations [CCL- 22, CCSW22, BBDD24], does not require log-coneavity, and only requires an 122 guarantee such [CCL-22]
E
[||s (x) - مx [=] < e
to accurately sample from p(x). One can also run similar ODE with similar guarantees but faster [3].
5

---

Posterior sampling, Now, in this paper we are concerned with posterior sampling: we observe noisy linear measurement y E Rm of z, given by
y Ax +
for
{ (~~(0,,
and want to sample from p(r | v). The unsmoothed score 8y(x) = V logglle y) is easily computed by Bayes' rule:
A AT Ax)
V logp(r 1)) V logp(z) + V logply ( = s(x)
1/2
Thus run the Langevin SDE (3) with the same properties: if p( y) is strongly log log-concave and the score estimate satisfies the MGF enror bound (4), will converge quickly and accurately,
Naturally, researchers have looked to diffusion processes for more general and robust posterior sampling methods. The main difficulty is that the smoothed score of the posterior involves V. lologp(y Foz)) rather than the tractable unsmoothed term v Ply smoothed score is hard to evaluate exactly, range of approximation techniques has been pro- posed 2BG CKM+23, MK25, RCK+ SVMK23, WYZ23J. One prominent example is the DPS algorithm [CKM+23]. Other methods include Monte Carlo/MCCC-inspireee approxima- tions [C]cILCM24, DS24, WSC 24, EKZL25], singular value decomposition and transport tilting [KVE21, KSEE22, WYZ23, BH24], and schemes that combine corrector steps with standard diffu- sion updates [CL23, CY22, CSRY22, KBBW23, LKA 24, SKZ* 24, SSXE22, ZZL 7ZL*33, AVTT21, XC24, RLdB 24, R3D#233. These approaches have shown strong empirical performance, and several provide guarantees under additional structure of the linear measurement; however, general guarantees for fast and robust posterior sampling remain limited beyond these restricted regimes.
æ).. Because the
Several recent studies [JAD*21, 21, 7CB+25, KVE21] various annealed versions of the Langevin SDE as a key component in their diffusion-basse posterior sampling method and achieve strong empirical results. Still, these methods provide no theoretical guidance on two key aspects: how to design the annealing schedule and why annealing improves robustness. None of these approaches come with correctness guarantees for the overall sampling procedure.
Comparison with Computational Lower Bounds. Recent work of [GJP shows that it is ac- tually impossible achieve general algorithm that guaranteed fast and robust: there is an expo- nential computational gap between unconditional diffusion and posterior sampling. Under standard cryptographic assumptions, they construct distribution p over Rd such that
1. One can efficiently obtain an T.-aacurate estimate of the smoothed score of p, diffusion models can sample from p.
2. Any sub-exponential time algorithm that takes y Axr + +O 17 Tm) as input and outputs a sample from the posterior p(æ y) fails on most with high probability.
Our algorithm shows that, once an additional noisy observation that is close is provided, then we can efficiently sample from p(z y, R), circumventing the impossibility result.
To illustrate why the extra observation helps, consider the following simplified version of the hard- ness instance:
p: >== d(z) 2d/2
Σ 4E
f(s) x).
Here, f: (0, 1//22 - {0, 1]//2 one-way permutation - it takes exponential time to compute (x) for most x E (0. 1] 5(.) is the Dirac delta function, and we choose a < d-1/2 Thus, p(z) is a mixture of 2d/2 well-separated Gaussians centered at the points (s, f (s)).
Assume observe
= Ar + (00 A Ta/2), a < EEnEd-1
and let (v) denote the vertex of (0. 1) closest to Then the posterior p(x y) is approximately a Gaussian centered at (rnd(y)) ryd(y)) with covariance o² lT. Generating a single sample would therefore reveal (rld(()))))) which requires exp(I(d)) time.

---

However, suppose we have a coarse estimate zo satisfying 120 - - 1/3 (e.g., obtained by com- pressed sensing). Then, zo uniquely identifies the correct f()) with f(s) rnd(y), and the remaining task is just sampling from Gaussian. Therefore, this hard instance becomes easy once we have localized the task and does not contradict our Theorem 1.2.
We are able to handle the hard instance above well because it is exactly the type of distribution our approach is designed for: despite its complex global structure, exhibits well-behaved local properties. This gives an important conceptual takeaway from our work: the hardness of posterior sampling may only lie in localizing x within the exponentially large high High-dimensional space.
Therefore, although posterior sampling is an intractable task in general, it still possible to design robust, provably correct posterior sampling algorithm once we have localized the distribution.
We view our work as a first step towards this goal.
Techniques
The algorithm we propose is clean and simple, but the proof is quite involved. Before we dive into the details, we provide high-level overview the intuitions behind the algorithm, concentrating on the illustrative case where the prior density p(z) is a-strongly log-concave. Under this assumption, every posterior density p(x) y/) is also a-strongly log-concave. Therefore, posterior sampling could, in principle, be performed using classical Langevin dynamics.
The challenge arises because lack access the exact posterior score sy(x). We only possess an estimator derived from an estimate ((x) of the prior score s(r):
A (u Az)
Sy (z) ((x)
r)2
Assumption implies an L accuracy of s, average, but how do use this to support Langevin dynamics, which demands exponentially decaying error tails?
3.1 Score Accuracy: Langevin Dynamies vs. Diffusion Models
Why can diffusion models succeed with merely L Lacccrraeee scores, whereas Langevin dynamics require MGF accuracy?
Both diffusion models and Langevin dynamics utilize SDEs. The L error in the score-dependent drift term relates directly to the KL divergence between the true process (using s(x)) and the esti- mated process (using (())). Consequently, bounding the L score error with respect to the current distribution P. controls the KL divergence.
Diffusion models leverage this property effectively. The forward process transforms data into Gaussian, and the reverse generative process starts exactly from this Gaussian. At any time t, sup- pose Pt is close to Pot. then
E (x)))( 20 [1 Se Zerup
E semPot
-000) (0)(2))) S
by the 2 accuracy assumption. This keeps the process close to the ideal process, ensuring overall small eтror.
Langevin dynamics, by contrast, often starts from an arbitrary, not predefined initial distribution Pinitial- An T.P score accuracy guarantee with respect to Purget alone does not ensure accuracy for points that are not on the distributional manifold of Puurget (consider running Langevin starting from Zo in Figure 2). Therefore, a stronger MGF error bound is needed to prevent this from happen- ing.
3.2 Adapting Langevin Dynamics for Posterior Sampling
While can only use Langevin-type dynamics for posterior sampling, possess source of effective starting points: we can sample Zo ~ p(x)) efficiently using the unconditional diffusion model. Intuitively, zo already lies on the data manifold. The score estimator (2r) initially satisfies:
xo)pp(x) (x)) (z(0))
E []]=(z)) 3(zo) || < 2
zomp(a)

---

1.0
0.060
0.9
0.030
Var(X.)
0.8
0.015
0.7
0.007
0.6
Var(X;)
0.003
unit variance
0.5
0.000
0.00
0.01
0.02
0.03
0.04
0.05
0.06
-2
X
(a) (aa( as a function of
(b) X; ~ NNO, Var(X:) (+)) at different times
0.000. Starting from Xo p. run the Langevin SDE dX, sy dX, + v2dB,. Averaging over y, the marginal of X, remains Gaussian; its variance first contracts and then returns toward the prior. There is an intermediate time (* where X,- has constant factor lower variance; in high dimensions, this means X,- is concentrated exponentially small region of so an L bound on score error under does not effectively control the error under X... See Section F for details.
Figure 3: Let p 1) and
As the dynamics evolves, the distribution p(x²) transitions from p(z) towards p(r y). If xy con- verges to p(x y), we again expect reasonable accuracy on average:
E E (())))))))) Sy (x:0)11 # #imp(=lp)
E
E semp((alv)
[1|((1)) s(xz))1 = score.
Hence the estimator is accurate the start and convergence. The open question concerns the intermediate segment of the trajectory: does 24 wander into regions where the prior score a(x) is unreliable? Ideally, the aime-marginal of Ze, averaged over y. remains close p(r) throughout.
3.3 Annealing via Mixing Steps
In fact, though zo and Ix both have marginal p(z), the score estimate ((x) is accurate average at those times, this is not true at intermediate times. In Figure 3, we illustrate this with a simple Gaussian example: 20 and Foo have distribution A 7) while xe has marginal (O, el) for a constant < 1. An T.P error bound under x ~ N(0, T) does not give an I22 error bound under (O, which means Langevin dynamics may converge to the right distribution. A very strong accuracy guarantee like the MGF bound is needed here.
However, consider the case where the target posterior p(x y) is very close to the initial prior p(z), such as when the measurement noise is very large (low signal-to-noise ratio). Langevin dynamics between close distributions typically converges rapidly. This suggests key insight: if the required convergence time is short, the process 22 might not deviate substantially from its initial distribution p(zn)- In such short-time regimes, an 1,2 score potentially suffice to control the dynamics. While p(x) itself is already a good approximation for p(x: y) when 1) is very large, this motivates general strategy.
bound relative to p(ro) could
Instead of a single, potentially long Langevin run from p(x) to p(z y), we introduce an annealing scheme using multiple mixing steps. Given the measurement parameters (A, n, v),)), we construct decreasing noise schedule 1 > 1/2 > > AN = 17. Correspondingly, we generate a sequence of auxiliary measurements 1/1 1/2 ........2 VN y such that each ys is distributed Ar + A/ Im) and y; is appropriately coupled to V++1 (specifically, Yi ~ NM (n² m2 conditional on 11+1). This creates sequence of intermediate posterior distributions p(æ yt).
admissible schedule (formally defined in Definition D.1) ensures that:
?/ is sufficiently large, making p( y)) close the prior p(x)).
Consecutive 77 and m are sufficiently close, making p(x y.) close p(z w41).
Our algorithm proceeds as follows:
8

---

Iepeieiing
Saper Rosakron
Griaki betirring
few
1'000000
210 30
11
14-2
1000
Figure 4: For each of the three settings (inpainting, super-resolution, and Gaussian deblurring). we plot the T,2 distance between samples obtained by annealed Langevin method and the ground truth samples in red. We plot the FID of the distribution obtained by running annealed Langevin in blue. We plot the baseline L distance and FID for samples obtained by the DPS algorithm using red and blue dashed lines.
1. Start with sample Xo p(x). Since 7n is large, p(x) is close to p(x v1). so Xo serves as an approximate sample X1 f(x 31).
2. For i = to N - 1; Run Langevin dynamics for short time Tú starting from the previous sample X; p(1 yı), targeting the next posterior p(æ gi+1) using the score 6y. (I)).
Let the result be X ~ p( 36+1).
3. The final sample XN p( yN) approximates a draw from the target posterior p(1) y).
The core idea behind this annealing scheme is to actively control the process distribution p( ensuring remains on the manifold of the prior p(z). By design, each mixing step - i connects two statistically close intermediate posteriors, p(x yi) and p(x: yi+1). This closeness guarantees that short Langevin run T. can mix them, and this short duration prevents p(x+) from drifting significantly away from the step's starting distribution $(x y1). and we can then argue that
E p(rp))))))))
(. (x+) Sy, (xx [1 R
[11((1)) - ((x1) <
semp(2)ps)
soure
This contrasts fundamentally with a single long Langevin run, where #e could venture far "off- manifold" into regions of poor score accuracy. By inserting frequent checkpoints that re-anchor the process, our annealing method substitutes such strong assumptions with structural control: the frequent "checkpoints" p(x yyi ensure the process is repeatedly localized to regions where the L accuracy suffices. While error is incurred in each step, maintaining proximity to the manifold keeps this error small. The overall approach hinges on demonstrating that these small, per-step errors accumulate controllably across all N steps.
This strategy, however, requires rigorous analysis of three key technical challenges:
1. How to bound the required convergence time T; for the transition from p(z | ys) to p( 3 ? In particular, what happens when p only has local strong log-concavity?
2. How to bound the error incurred during single mixing step of duration T,, given the 4 score error assumption on the prior score estimate?
3. How to ensure the total error accumulated across all N mixing steps remains small?
Addressing these questions forms the core of our proof.
Proof Organization. Section A, we show that for globally strongly log-concave distributions
Langevin dynamics converges rapidly from p(z 9:) to p(z 31+1). We extend this convergence analysis to locally strongly log-concave distributions in Section B. Section C, we provide bounds
on the errors incurred by score emrors and discretization in Langevin dynamics. In Section D, we show how design the noise schedule to control the accumulated error of the full process. Sec- tion E, conclude the analysis for Algorithm 1, and apply it to establish the main theorems.

---

CNN
CNN
CNN
(a) Input
(b) DPS
(c) Ours
(d) Ground Truth
Figure 5: A set of samples for the inpainting task.
Input
(b) DPS
(c) Ours
(d) Ground Truth
Figure 6: A set of samples for the super-resolution task.
4
Experiments
To validate our theoretical analysis and assess real-world performance, we study three inverse prob- lems on FFHQ-256 [KLA21]: inpainting, 4x super-resolution, and Gaussian deblurring. Exper- iments use Ik validation images and the pre-trained diffusion model from ( Forward operators are specified as in [CKM*255 233]: inpainting masks 30%-70% of pixels uniformly at ran- dom; super-resolution downsamples by a factor of 4; deblurring convolves the ground-truth truth with Gaussian kernel of size 61 61 (std. 3.0). We first obtain initial reconstructions Zu via Diffu- sion Posterior Sampling (DPS) [DS24], then refine them with our annealed Langevin sampler to draw samples close to p(æ; To, y). To control runtime, we sweep the step size while keeping the annealing schedule fixed.
For each step size, we report the per-image L distance to the ground truth and the FID of the result- ing sample distribution (Figure 4). Across all three tasks, increasing the time devoted to annealed Langevin decreases _ but increases FID; in the inpainting setting, when the step size is sufficiently small, our method surpasses DPS on both metrics. Qualitatively, our reconstructions better preserve ground -ruth attributes compared DPS (Figures 5 and 6). All experiments were run on a cluster with four NVIDIA A100 GPUs and required roughly two hours per task.
Acknowledgments
This work is supported by the NSF Al Institute for Foundations of Machine Learning (IFML.. ZX is supported by NSF Grant CCF-2312573 and a Simons Investigator Award (#409864, David Zuckerman).
Bibliography
[And82] Brian DO Anderson. ceverse-time diffusion equation models. Stochastic Processes and their Applications, 12(3):313-326, 1982.
[AVTT21] Marius Arvinte, Sriram Vishwanath, Ahmed H. Tewfik, and Jonathan I. Tamir. Deep j-sense: Accelerated mri reconstruction via unrolled alternating optimization. In Medical Image Computing and Aosputer-Assisted Intervention (MICCAI 202/),
10

---

Part VI. volume 12905 of Lecture Notes in Computer Science, pages 350-360.
Springer, 2021.
[BBDD24] Joe Benton, Valentin De Bortoli, Arnaud Doucet, and George Deligiannidis. Nearly SdS-linear convergence bounds for diffusion models via stochastic localization. In The Twelfth International Conference on Learning Representations, 2024.
[BGP+24] Benjamin Boys, Mark Girolami, Jakiw Pidstrigach, Sebastian Reich, Alan Mosca, and Omer Deniz Akyildiz. Tweedie moment projected diffusions for inverse prob- lems. Transactions on Machine Learning Research, 2024. TMLR (ICLR 2025 Jour- nal Track).
[BH24] Joan Bruna and Jiequn Han. Provable posterior sampling with denoising oracles via tilted transport. In Advances in Neural Information Processing Systems (NeurIPS), 2024.
[CCL +2] Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru R Zhang. Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. arXiv preprint arXiv:2209. 1215, 2022.
[CCL++23) 233 Sitan Chen, Sinho Chewi, Holden Lee, Yuanzhi Li, Jianfeng Lu, and Adil Salim. The probability flow ODE is provably fast. In A. Oh, Neumann, Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Pro- cessing Systems, volume 36, pages 18552-68575. Curran Associates, Inc., 2023.
[CCSW22] Yongxin Chen, Sinho Chewi, Adil Salim, and Andre Wibisono. Improved analysis for a proximal algorithm for sampling. In Conference on Learning Theory, pages 2984-3014. PMLR, 2022.
[CJeILCM24] Gabriel Cardoso, Yazid Janati el Idrissi, Sylvain Le Corff, and Eric Moulines. Monte carlo guided denoising diffusion models for bayesian linear inverse problems. In International Conference Learning Representations (ICLR), 2024. Oral.
[CKM 23] Hyungjin Chung, Jeongsol Kim, Michael Thompson Mccamn, Marc Louis Klasky, and Jong Chul Ye. Diffusion posterior sampling for general noisy inverse problems. In The Eleventh International Conference on Learning Representations, 2023.
[CL23] Junqing Chen and Haibo Liu. An alternating direction method of multipliers for inverse lithography problem. Numerical Mathematics: Theory, Methods and Appli- cations, 16(3):820-846, 2023.
[CRT06] Emmanuel J Candes, Justin K Romberg, and Terence Tao. Stable signal recov- ery from incomplete and inaccurate measurements. Communications on Pure and Applied Mathematics: Journal Issued by the Courant Institute of Mathematical Sciences, 1277 2006.
[CSRY22] Hyungjin Chung, Byeongsu Sim, Dohoon Ryu, and Jong Chul Ye. Improving diffu- sion models for inverse problems using manifold constraints. In Advances Neural Information Processing Systems (NeurIPS), 2022.
[CY22] Hyungjin Chung and Jong Chul Ye. Score- diffusion models for accelerated mri. Medical Image Analysis, 80:102479, 2022.
[Dal17] Arnak S Dalalyan. Theoretical guarantees for approximate sampling from smooth and log-concave densities. Journal of the Royal Statistical Society Series B: Staristi- cal Methodology. 79(3):651-67) 2017.
[DS24] Zehao Dou and Yang Song. Diffusion posterior sampling for linear inverse prob- lem solving: filtering perspective. In The Twelfth International Conference Learning Representations, 2024.
[EKZL25] Filip Ekström Kelvinius, Zheng Zhao, and Fredrik Lindsten. Solving ganaain bayesian inverse problems with decoupled diffusion sequential monte carlo. In Pro- ceedings of the 42nd International Conference on Machine Learning (ICML), vol- ume 267 of Proceedings of Machine Learning Research, pages 55148-15181. 2025.
11

---

[GJP 24] Shivam Gupta, Ajil Jalal, Aditya Parulekar, Eric Price, and Zhiyang Xun. Diffusion posterior sampling is computationally intractable. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 17020- 17059. PMLR, 21-27 Jul 2024.
[HD05] Aapo Hyvärinen and Peter Dayan. Estimation of non-normalized statistical models by score matching. Journal of Machine Learning Research, 6(4), 2005.
[HJA20] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 0146840-65111 2020.
[JD+211] Ajil Jalal, Marius Arvinte, Giannis Daras, Eric Price, Alexandros Dimakis, and Jon Tamir. Robust compressed sensing mri with deep generative priors. Advances in Neural Information Processing Systems, 34:14938-1499 14954, 2021.
[JCP24] Yiheng Jiang, Sinho Chewi, and Aram-Alexandre Pooladian. Algorithms for mean- field variational inference via polyhedral optimization in the Wasserstein space. In Shipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 2720-2721. PMLR, 2024.
[JKH+21] Ajil Jalal, Sushrut Karmalkar, Jessica Hoffmann, Alex Dimakis, and Eric Price. Fair- ness for image generation with uncertain sensitive attributes. In International Con- ference on Machine Learning, pages 4721-4732. PMLR, 2021.
[KBBW23] Ulughek S. Kamilov, Charles A. Bouman, Gregery T. Buzzard, and Brendt Wohlberg. Plug-and-play methods for integrating physical and learned models in computational imaging: Theory, algorithms, and applications. IEEE Signal Process- ing Magazine, 40(1):85-97, 2023.
[KLA21] Tero Karras, Samuli Laine, and Timo Aila. A style-based generator architec- ture for generative adversarial networks. IEEE Trans. Putlern Anal. Mach. Intell., 43(12):4217-4222, December 2021.
[KSEE22] Bahjat Kawar, Jiaming Song, Stefano Ermon, and Michael Elad. Denoising dif- fusion restoration models. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
[KVE21] Bahjat Kawar, Gregory Vaksman, and Michael Elad. Snips: Solving noisy inverse problems stochastically. In Advances in Neural Information Processing Systems (NeurlPS), volume 34, pages 21757-21769, 2021.
[LKA* Xiang Li, Soo Min Kwon, Ismail R. Alkhouri, Saiprasad Ravishankar, and Qing Qu. Decoupled data consistency with diffusion purification for image restoration. arXiv preprint arXiv:2403.06054. 2024.
[LM00] B. Laurent and Pascal Massart. Adaptive estimation of a quadratic functional by model selection. Annals of Statistics, 28, 10 2000.
[MK25] Xiangming Meng and Yoshiyuki Kabashima. Diffusion model based posterior sam- pling for noisy linear inverse problems. In Proceedings of the 16th Asian Conference on Machine Learning (ACML), volume 260 of Proceedings of Machine Learning Re- search, pages 623-638. PMLR, 2025.
[RCK*24) Litu Rout, Yujia Chen, Abhishek Kumar, Constantine Caramanis, Sanjay Shakkottai, and Wen-Sheng Chu. Beyond first-order tweedie: Solving inverse problems using latent diffusion. In Proceedings of the IEFF/CVF Conference on Computer Vision and Pattern Recognition, pages 9481-9481, 2024.
12

---

[RLdB* 24] Marien Renaud, Jiaming Liu, Valentin de Bortoli, Andrés Almansa, and Ulugbek S. Kamilov. Plug-and-play posterior sampling under mismatched measurement and prior models. In International Conference on Learning Representations (ICLR), 2024.
[RRD*23] 23] Litu Rout, Negin Raoof, Giannis Daras, Constantine Caramanis, Alexandros G. Di- makis, and Sanjay Shakkottai. Solving linear inverse problems provably via posterior sampling with latent diffusion models. arXiv preprint arXiv:2307.00619, 2023.
[SE19] Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. In Advances in Neural Information Processing Systems (NeurIPS), volume 32, 2019.
[SKZ 24] Bowen Song, Soo Min Kwon, Zecheng Zhang, Xinyu Hu, Qing Qu, and Liyue Shen. Solving inverse problems with latent diffusion models via hard data consistency. In International Conference on Learning Representations (ICLR), 2024.
[SME20] Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit
models. arXiv preprint arXiv:2010.02502, 2020.
[SSDK+21] Yang Song, Jaseha Soht-Dickstein, Diederik P. Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differ- ential equations. In International Conference on Learning Representations (ICLR), 2021.
[SSXE22] Yang Song, Liyue Shen, Lei Xing, and Stefano Ermon. Solving inverse problems in medical imaging with score-based generative models. In International Conference on Learning Representations (ICLR), 2022.
[SVMK23] Jiaming Song, Arash Vahdat, Morteza Mardani, and Jan Kautz. Pseudoinverse- guided diffusion models for inverse problems. In International Conference on Learn- ing Representations (ICLR), 2023.
[Tib96] Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society Series B: Statistical Methodology, 58(1):267-288, 1996.
[WSC*24] Zihui Wu, Yu Sun, Yifan Chen, Bingliang Zhang, Yisong Yue, and Katherine Bouman. Principled probabilistic imaging using diffusion models as plug-and-play priors. In Advances in Neural Information Processing Systems (NeurIPS), 2024.
[3T Luhuan Wu, Brian Trippe, Christian Naesseth, David Blei, and John P Cunning- ham. Practical and asympiotically exact conditional sampling in diffusion models. Advances in Neural Information Processing Systems, 36:31372-31403, 2023.
[WYZ23] Yinhuai Wang, Jiwen Yu, and Jian Zhang. Zero-shot image restoration using denois- ing diffusion null-space model. In International Conference on Learning Represen- tations (ICLR), 2023.
[XC24] Xingyu Xu and Yuejie Chi. Provably robust score-based diffusion posterior sam- pling for plug-and-play image reconstruction. In Advances in Neural Information Processing Systems (NeurIPS), 2024.
[YW22] Kaylee Yingxi Yang and Andre Wibisono. Convergence in kl and rényi divergence of the unadjusted langevin algorithm using estimated score. In NeurlPS 2022 Workshop on Score-Based Methods, 2022.
IZBB+25 Bingliang Zhang, Wenda Chu, Julius Berner, Chenlin Meng, Anima Anandkumar, and Yang Song. Improving diffusion inverse problem solving with decoupled noise annealing. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2025.
[ZZL+ 2 Yuanzhi Zhu, Kai Zhang, Jingyun Liang, Jiezhang Cao, Bihan Wen, Radu Timofte, and Luc Van Gool. Denoising diffusion models for plug-and-play image restora- tion. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1219-1229, 2023.
13

---

A Langevin Convergence Between Strongly Log-concave Distributions
In this section, study the following problem. Let p be a probability distribution on R and let A E IR mxd be matrix. For a sequence of parameters > 7i+11 satisfying
T/ (1 + 7))
2
consider two random variables y, and Vi+1 defined as follows, First, draw x ~ Then, generate
Vi+1 Ar + ((, n Im);
and further perturb by
y1 Vi+1 N(O mm))
Define the score function
$1+((2)= = V log V141).
We analyze the following SDE:
dr. = 8:4 ( (z+) dt + v2dB,
p(x ys).
(6)
This is the ideal (no discretization, no score estimation error) version of the process (2) that we actually run. Our goal is to establish the following lemma.
Lemma A.1. Suppose the prior distribution p(x) is a-strongly log-concave Then, ranning the process (6) for time
T == mh log(A/E)
ensures that
Pr [TV(TT,pl (++1)) S 2 1 1-11-- X 36-16+11
A.1 x2 -iveergence Between Distributions
In this section, goal is bound x² (p(x) v.) [1 v6+1)). Since the posterior distributions can be expressed as
p( ye) p(y xx)((x)
p(e 19411)= p(u+41 x)p(2)
p(u))
p(1(+1)
The x2 divergence is
p(x 31))
x² (p(x ui) ppp( mo+1))
-
p(x M6+1)
p(y/ x))
p(U++1)
p(1++1 (x)
p(vi)
-
p(ua x))
p(U++1)
E x><p(>|0))
-1
p(U++1 (x)
p(y.)
We bound the term Empp(a)))) w.)
p(u: lw) p(u++112)
first.
Lemma A.2. We have
Plu: (x)
E a. Melllel 11
pl Mys-1 xx)
Proof. Let Z₁ = 1/+11 - Ax. and let Zz = yi - Ax.
Then we have
p(y: ar)
T2(2))
= -11 Pz, (22)
E
(2,, 22) d d 22
p(yi+1 2.3
x))
Zi.Za
[p(2))
Pz, (21)
Note that
Pz, P2i 2z (21, 22) pz, (21) f(22 21),
14

---

where f is the density function for N00, (n, 11t1) Mm). Therefore,
/| Pzz (2)) Pz, (z1) Pz,
/f p2)(22) f(22 d 22
22) (2)
/ pz. (22)
(f flee 21) 21) 22
Since ʃ is density function, its integral over R is 1. This gives that
f pzz (22) (f [fees
21) 21) -())
21 22
Pzs (22) =
Hence,
p(3k x)) p(yi+1
JE -i
= 1.
xx)
Corollary A.3. For any 1, we have
p(y: xx)
S 1- X
(mmplalue)
p xr)
Proof. By Lemma A.2, have
Plus x)
11
p(y/ x))
E
E
IE 1.
=1
Mc-We-1
1
Mn)
p(yi+1 1 xx)
p(yi+1 |x)
Applying Markov's inequality gives the result.
Now bound p(u++1) To make the lemma self-contained, abstract this little bit. p(an)
Lemma A... Let mi > 1)2 be two positive numbers, and let X E Rd be arbitrary random variable. Define Yi= = X + Zi and Y2 Y, + Uz where Zi ~ N(0, nî La) and Zo N (O, n la).
Then,
p(Y1) (P(22)
(0
dn
m
))
E
< Pr t] Y1 and Y2, respectively.
+
Y,,Y,
m
2
m
where p(Y1) and p(22) are the densities Y1
Proof. First, we turn to bound
Y2) := p()))
Pr |r StlY..
p(Y2)
Note that
J p(X p(x s)p(Hi X = ssdds
Px) (V 8) 1 1 - ds
F((Y,, Y2)
1(a =s)p(V2 X =s)dds
SpePx px (8) (8) of +r (Y22 8) d
We have
(1 - 8) [(ls)
< sup Popt, -) ee-Kllss (nf (Y₂ -s)
F((Y,,Y)) sup
sE + (Y22 s)
Write Y1 - = C1, and note that Y2 - s = C1 + Zz. Then define
61pl1 (c1)
G(el)
|ell St.
P(rf+ (e1 + Zz)
This gives that for any Y1, Y2, and f,
F( < sup G(ez). |
15

---

Bounding G(e))
To bound sup/lcs [ellsst G(e1), we expand Φ as the d-dimensional Gaussian proba-
bility density function:
G(e,) = 1 + 112
d/2
lei 1|
| + 22
exp
21f
2(7 + m/
Using the quadratic expansion
|e| + 2211²
||e
||
( E2) + 1| 12 we rewrite:
G((E)) = 11 + 12
4/2
| 2
|e
||e +12 72) + || |
exp
1/i
2n/
2(n + n3
Since ||ei|s and (e1, 22) - ||e ||||
Z211, we bound
2(e1, Zz))
22
<
2(1 + 112)
1/ + 77
Thus,
1/ 112
d/2
|| 12 1
2|
G(e)) S
exp
2( + m
oi + 13
Therefore, for any Y1, 12, and t, we have
n +
72
d/2
|| 11
2
Y2) s
exp
2( + 1/2
7f 1/
This gives that
P(
E
p (((2))
Fi(Y,,
E
Pr 1| St Yi]
1
'I +
1/2
d/2
2|
11
E
Pr [| || 1
of
exp
2( + 72)
of + vz
77 + 172
d/2
| 11 2(7
Z2l of + mz
EE
exp
Pr || S [
22
75
Bounding expectation over Zz.
We have
Zz 1
t Z2l
)
n/ 1
tm |
exp
2(7 + 1
r + m
E Z~N110,1a)
exp
20n + n3
गF n
We can apply results on the Gaussian moment generating functions to bound this. nr
Us-
F3 B ing Lemma A.10 by setting 2(x
mi
fnz and 7 1( +
have
17 1 2(7 + n3
tma l
)
12 1/ + +12) )
2 n ni
d/2
(0,
E
cxp
ni + m3
S exp
sexp
Finally, this gives
p(Y1)
exp (o
0
dnp
122
))
E V 11
+
p(Y2)
Pr Z S
mp
One need to verify that
E Y 15
< Pr 7 <
Pr [[|]
< Yi
Also,
E [P, Y2)] < exp (0 %
dni {(
)
+
This gives the result.
16

---

Lemma A.5. Let 1/2 > be two positive numbers, and let X E R be an arbitrary random
variable. Define Y = X + Zn and Y2 Y + Zz, where Z N(0, ní Ia) and Zn N(0 n2La).
There exists constant C > O such that for any >> 1,
p(1))
S exp (c.
dnp
Pr Y..Y2
+ In
2 X
((22)
where p(Yi) and 2(2) are the densities Y1 and Y2, respectively.
Proof. Lett = (vd+ 2lm(2)))m By applying Laurent-Massart bounds (Lemma A.11), we have
1
Pr [1 S S
2X
Taking these into Lemma A.4, we have
p (1)
I exp (o dnp
S exp (o
0
(d In
A)ni
))
+
Y, 12
2
7i
By applying Markov's inequality, for large enough constant C > 0, we have
p(Y) Axxp
(d (
(
In A) `f
Pr
Yalli
St
(p2))
2X
Cleaning up the bound a little bit, this implies that for a large enough constant
C >
0,
(Y1) S exp CC
dnp
2 +
+ Im
1
Pr
Yi Is Combining this with the probability that || || S t, union bound gives that
((2)
m/
2X
(Yi)
I exp C dng
+ in))) 2
Pr
((2))
vi
X
The x2 divergence is
p(a y))
x² (p(x v.) 1l (++1))
p(z Mi+1)
p(ya x))
p(U(+1)
p( |x:)
p(v))
p(y/ x))
p(U(+1)
E x-p((x
1.
p(1++1
|x)]
p(y.)
Now we can bound the diveeriiit Lemma A.6. There exists a constant > O such that for any >> 1,
[ (p(x y:) I|p(2 B++1)) S exp (c (m(p? n241)
+ In 1 ) 21 21-
Pr
Th
Proof. Note that
p x))
p(y(+1) 1.
x² (p(x) vi) [| v1+1)) xxpp(2)
p(y4+1 |x)
p(ys)
By Corollary A.3, we have
plus x))
1
Pr Ve-lh
E
$ 22
> 1
powp(ao us)
[p()+11 xx)
2X
By Lemma A.5, there exists a constant C > such that
p(Yi)
S exp (c (c(máni
(mm(n² m2t1)
Pr V..%
+ In
21 2X
p(2))
Then
A union bound these two implies that with probability of 1/X, p( x) p(y++1)
2x-exp (c mm(x"" - mit1) in)) eep
exp C''
(mii"² nitz)
+ 1m -m>)):
P(1+11 x) p(y;)
where O' is a positive constant. This concludes the lemma.
17

---

A.2 Convergence time of Langevin dynamies
We present the following result on the convergence Langevin dynamies:
Lemma A.7 ([Dal17)) Let p and q be probability distributions such that q is an o- log- concave distribution. Consider the Langevin dynamics initialized with p as the starting distribution. Then, for any t 2 O, we have
1 TV(p,, 9) S x= 2
This implies that
Lemma A.8. Let and be probability distributions such that is an oo-strong log-concave distri- bution. Consider the Langevin dynamics initialized with p the starting distribution. By running the diffusion for time
(LO8 (L/s) log x2 (
T= 0
have (PT,, g) S.
Now we show that the posterior distribution even more strongly log-concave than prior distribu- tion.
Lemma A.9. Suppose that p(x) is o-sttrongy log-concave. Then, the posterior density p(x A + N Im) = y4)
a-strooglly log-concave.
Proof. By Bayes' rule, the posterior density can be written (up to normalization)
p(a Ar + (n) = y:) x p(æ) exp(
|| Ax - y4 11
211²
Define the negative log posterior
1 || vel12.
p(x) = - -lo +
2n
Since p is a-strongly log-concave, its negative len-iensity satisfies
(- ž al.
Moreover, the Gaussian likelihood term has
V || vill3)
1 m.
AT A = 0.
2m
By the rule for Hessians,
V2 x(x) = V + - A = al.
1/
Hence op a-strongly convex, and the posterior density p(x Ar N( vi) x 6 + is a-strongly log-concave.
Now we are ready to prove Lemma A.1:
Proof of Lemma A.I. By Lemma A.9, p(a yi+1) is alpha-strongly log-concave, This allows us to apply Lemma A.8. Therefore, to achieve TV error convergence, we only need to run the process for
T= O log(1/s) log x (p(z yi) p B(41))
Taking in the result in Lemma A.6, we have with 1 1 à probability over and yit1, we only need
my log(2/E)
0
a
18

---

A.3 Utility Lemmas.
Lemma A.10. Let NO0 Ia) be d-dimensional standard Gaussian random vector, and let a,8 E R. For any > 0 satisfying + 2. we have
12
exp [ S exp
2(xx + -4/2
4/2
Proof. For all r 0 and any 0, it is easy to check that by AM-GM inequality,
8 47
Br S 3p
Taking ||||| and exponentiating both sides, obtain
8² 47
exp (311Z1) - exp (xp(x112122
Multiplying both sides by exp (a| 27]² yields
0² exp exp(all2](++3112) s exp
exp (a + 7)1111)))
47
This gives that
32
E
exp
a (alz) S exp
E exp (a 7))
For Z Ia), when a +y < 2 we have
E exp (a + ( =(1 - 2((( + +)))
Hence,
exp (al1z](++31111 S exp (x) (1 22(a + +1))-a122
(82)
(4n)
Lemma A.11 (Laurent-Massarr Bounds[LMM0)), Let N(0, Im). For any 0.
Pr[[|/]|2 2 2/ ml 21| Se Se Pr[[|u[|2 - m S 22 mt Se
B Convergence Between Locally Well-Conditioned Distributions
In the last section, we considered the convergence time between two posterior distributions of globally strongly log-con log-concave distribution. In this section, we will relax the assumption of global strong log-concavity and consider the convergence time between two distributions that are locally "well-hehaved". We give the following formal definition:
Definition B.1. For & E [0, and R, L, a (0, +oo), we say that a distribution p is (8, r, R, I, a) mode-centered locally well-conditioned if there exists @ such that
V 1og 0.
Przmpl [x E (0) 2 6-
For v, ((0, R), we have that [s(x) s(y)lls La || 1xx--l] y/l.
For a,y B0,, R), have that (s(y) s(x), 4) ||æ -y1?
19

---

Again, we consider the following process P, which is identical to process (6) we considered in the last section:
A Mit1
AT Art
dx
((x))) +
dt + Vdd,, To ~ pp 1v)
n2+1
Our goal is to prove the following lemma:
Lemma B.2. Suppose p is a (ò, r, R. L, a) mode-centered locally well-conditooned distribution. Let C > 0 be a large enough constant. We consider the process running for time
mr log(A/E)
T2C
Suppose that
T|A (IAllr Mitllmm+ (2ln(1/0)) + +2 dl Ed/TThig (2d//5).
R2 r
Tht1
Then TT Pr satisfies that
Pr [T(2r,,p( (i+1)) S 2o 2 21-0(1")) V4-34441
In this section, we will assume that is (6,r, R. a) mode-centered locally well-conditioned. Without loss of generality, we assume that the mode of p is i.e., 0 0.
B.1 High Probability Boundness of Langevin Dynamies
We consider the process p' defined as process P conditioned on æ, E B(0 R) for E [0, T).
Our goal is to prove the following lemma:
Lemma B.3. Suppose the following holds:
A|I (IAA]TT 1+alvm+++++++ 22l((1))) + +2 dl In(2//)).
R R2
We have that
E (TV)
We start by decomposing the total variation distance between P and Pl follows: Lemma B.4. We have that
(V((P,)))
Pr
3t E [0,
|
R xo E B(O, r)] +
BI-M+41
Proof. Recall that the process pr is defined the law of P conditioned on the event F {xz E B(0, R) for all t E [0,T]}.
Thus, for any fixed y we have
= -1- -1 POTT)
TV IV
where = (3t [0,T]: R).
Let {ro B(0, r) denote the event that the initial condition is "good." Then, by the law of
total probability.
P(F) P(F (E) + P(F NE < P(F 8) + P(E).
Taking the expectation with respect to and Fi+1, we obtain
E B s E P(F 8)]
P(
20

---

Since
P(F 8) Pr 3t [0, 7) ||0 R E B(0,r))
and by the law of total probability, have
P(E9)
Pr (1|= r) S 6, wmp
it follows that
TV(( s S 3t [0, T] | R xo B(0, + 8.
This completes the proof.
Now we focus bounding Begae Prr Bl E [0,7]: ||.|| R so (BO0r))] We start by observing the following lemma for log-concave distributions. Lemma B.5. Let p be log- con-cone distribution such that p is continuously differentiable. Suppose the mode of p is at O. Then, for all x E R
(V log p()), S.
Proof. Since log is concave, for any x, 0 E Rd the first-order condition for concavity yields log p(0) - logp(x) (Vlogp(z)) -z). -
Rearrange this inequality obtain
(Vlogp(z), -x) log p(0) - p(z).
Because 0 is mode, log p(0) 2 logp(z) for every Rd hence,
(V logg x) s 0.
Lemma B.6. Let Fe be the stochastic process
dx (f(x)) + g(xx)) dt + d2d To E Rd where B, is standard Rd-valued Brownian motion and the functions J g: RR + Rd satisfy
I[f(=)|s and (g(x),x) S for all Rdd.
with 2 0. Then, for any time horizon T > 0 and 8 E (0,
2d ||al| || || aaT + 2 T In
Pr
sup [E|O.T]
> 1 8.
8
Proof. Define r(() = ||aa|]- Although the Euclidean norm is not smooth at the origin, an application of Itô's formula yields that, for x, + O, one has
(ur, f(xx) + g(x+)) dt + /2 (o(tt,dB))
d-1 dt.
dr(t)
||>|||
||z,
where u(t) = xz/ 12,11 Using the bound (x:()) and the hypothesis (g(zz), S 0, it follows by the Cauchy-Schwarz inequality that
(ge, f(xa)
(Ft, g(xe)) |x
< and
S 0.
||x,|||
Discarding the nonnegative Itô correction term deduce that
d=1 dt (which can only increase the process), [
dr(t) < dt + 22 (u(t), dB.).
21

---

Introduce the one mee-imennioonl process
((0=[(wwa (u(s), f((uuo)) ((( dBa).
v(() || + B2)((,, with 8(1) - 8(1-
Since ||u(s)]l= for all s, the process ((t) is standard one-dimensional Brownian motion with quadratic variation (3), L. By standard comparison theorem for one-dimensional stochastic differential equations, follows that r()) (() almost surely for all / 0; hence,
| | v2 sup 3(t). te[o,T]
sup te[o,T]
classical application of the reflection principle for one-dimensional Brownian motion shows that, for any > O,
p²
Pr
3(t) 2 P] = Pr(3(T) 2 p) - 2 exp EE
2T
To incorporate the d-dimensional nature of the noise, one may use a union bound over the coordi- nate processes of B,, which yields that
2d
Pr
V2 sup tE|O.T]
B(t) s 2 Td
8.
Combining the foregoing estimates, deduce that
(n(²))
(
(2d
Pr sup [E[O.T]]
| || + 2 T 2 In
2 1 8,
which is the desired result.
Lemma B.7. For any E (0, 1) and T > 0, holds that
Pr sup 1 1A yetll Tht
2d + +2 d +2/Ta In (5)
xo B(0,r)] <8.
Pr 1E(0,7"
Proof. We first note that by Lemma B.5, for any Rdd, we have
AT Ar
((x)
n .x/
S (s(x,,))
||r||2 O.
mit1
By Lemma B.6, we have that
| 1itlllll
2d
Pr a
sup
||
|00||
+T
2 T in (
<8.
rE[o,T]
n
This gives that
Pr sup |x Pr
LA B1t1ll
+ 2/ Td In (n(20)) (2d)
2d
xo E B(00r)) <8.
Mia1
[E(0,2]
Lemma B.8. For any 5 E (0, 1), suppose
R2 A|A
m 221n(1/8)) + +2 dT (n22//0))
holds that
Pr
sup
|
Do E B(0,r) 26.
P
[0
22

---

Proof. Recall that
Wi+1 Ar + 114112 2~ N0, Im).
With probability least 1
|| vm+ 22l
Since |
with probability 1- 6. Thus, with probability at least 26, it follows that
11++ill5 || + |||||r m-+1 (vm /2ln(1/8)
Hence, with the 20 probability,
T ||AT 9++1l
T Illllllbb+
T||A|| (IAAI) mptllm /21n(118))
n/41
nh+1
n
Therefore, ensuring that
|AA stt1ll
2d T In ( + 2
R TT
2
In this case, Lemma B.7 guarantees that
mmll> R zo B(0,r) S 6.
sup [E.T)
Since the probability satisfying the condition is at least 22,, we have
| R xo E B(OOn]] 26.
E
Pr mer
sup 10
Putting Lemma B.4 and Lemma B.8 together, we directly obtain Lemma B.3.
B.2 Concentration of Strongly Log-Concave Distributions
Before moving futher, we first prove that strongly log-concave distribution is highly concentrated.
Lemma B.9 (Norm Bound for a-Strongly Logconcave Distributions). Let X be a random vector in Rd with density
<(x) exp(-V(z)),
where the potential Rdd + is a-strongly convex; that is,
VV((x) 2 aT for all x E Rdd_
Denote by μ = [[X] the mean of Then, for any 8 E (0,1), with probability at least ô we have
2lm(1/))
|X 1x-41s
Proof. Since V is a-strongly convex, the density x satisfies a logarithmic Sobolev inequality with constant 1/a. Consequently. for any I-Lipschitz function f I2d and any > one has the concentration inequality (via Herbst's argument)
IP - -[(()) 21) eexp ( at
-((())-
Noting that the function
f(x) = || llll
I-Lipschitz (by the triangle inequality). it follows that
at _ate)
P (II μl| -|I m1l $ exp
23

---

A standard calculation using the fact that the covariance matrix of X satisfies Cov(X) = 1/ gives
B|J 11|/ V
Thus, setting
2 2l(
we obtain
P P(Ix - 11l V
2 21n(1/0)
S 6.
This completes the proof.
Lemma B.10 (UCP244), Let μ and 0 denote the mean and the mode distribution p, respectively, where p is a-strongly log-concave and univariate. Then, 114 - 0 S Va
This immediately gives us the following corollary.
Corollary B.11. Let p be a a-strongly log-concave distribution on R.d. Let O be the mode of p. For every 0 < 5 < 1, we have
| 1x- 2 d 2log(118)
Pr X~p
11
This also implies that every a-strongly log-concave distribution is mode-centered locally well- conditioned.
Lemma B.12. Let p be an a-strongly log-concave distribution. Suppose the score function of
is L-Lipschitz. Then, for any 0 < 8 < 1, we have that p is (8, 2 (188(188) 00, L/a,
mode-centered locally well-conditioned.
B.3 Convergence to Target Distribution
Since p not globally strongly log-concave, we need to extend the distribution p to a globally strongly log-concave distribution. We will use the following lemma to extend the distribution.
Lemma B.13. Suppose g B(0, R)) + continuously differentiable with gradient s = Vg E
C(B(O, R); Rd) and satisfies
(s(y) s(x), x y) 2 a || yl
VE,y E B(0, R)-
(7)
For every z E ((0, R) define
(z) g(2) + (s(=), x 2)
a || - =||
x E Rdd
and set
g(xx),
|||||| S R, ||>||| > R.
[(x) =
(8)
inf
(z).
=E) R)
Then the density ((x) elte) is globally a-strongly log-concave.
Proof. For each fixed = E B(0, Rt) the mapping Ps has Hessian -ada hence is a-strongly concave on the whole space. Because of (7) have
((x) $ g()) + (s(2), x - 2) || - 2112 (x)). Vz, E B(0, R),
with equality when x z. Consequently ğ defined in (8) agrees with g on B(0, R). Fix E IR and choose above at d, the vector
E B(0, Rt) attaining the infimum in (8). Because sz, touches ğ from
{ = Viz, (x) = s(zx) a(x 2x)
24

---

belongs to (g(z). By strong concavity of Pzs.
Szx (v) S Paa (1) (E, y - x)
2 1y - x||
Vy R
Taking the infimum on the left and using ī(x) 2= (z) gives that
((v) ((x) + (5, - z) l 2 Vr,yER"
hence 9 is globally a-strongly concave, and therefore p is a atrongygly log-concave.
Lemma B.14. Let be a d-dimensional (ó,r. R. L, a) ability distribution with S 1/2 and > O. Assume
locally well-conditioned prob-
d
2 (1/0)
R 2
Then there exists an a-strongly log-concave distribution on R2 such that
TV 36.
Proof. Let 0 be the point in Definition B.1 and without loss of generality, assume 0 0. Write B = [0, R) and B == Rd B. By definition p( (B) I
Set g := logp, and let 9 be the function in Lemma B.13. Then, p(x) = e.(x) a-strongly log- concave and p p on B. Let Z = Sga and define ÿ : p/Z.
Now bound
TV 1)
1 / 11-
1
-1 B3=
/ 10 - LB + IB..
Corollary B.11 implies that ((B)) S 8. Therefore,
BB S _ (I((")) + +((()) < ō.
Note that J- p(B)= 2 and
J p S 82 (since ((B) S 8). Thus,
1- 1-052-10 xB) / p 26.
Since ~ p/Z on B, we have
Z -
28 48.
1
Therefore, IB - 1 48 28.
Combining,
TV < 25
5 35.
Now, we can consider process P defined as
AT Vit1 - AT Ax
dx
v ((g
dt + V2dB, p(= y:).
Then, we have the following lemma.
Lemma B.15. Suppose the following holds:
T|A
(IA + m4 221n(1/0)) + 22 ln(d5)))))
R2
have that
[V(( 26.
25

---

Proof. Let
3 sup (0
| - RJ and P'= P( 1
Because s() = Vlogp(z) for every x E BO0, R), the drift coefficients of P and P coincide on the event &, and hence conditioning on & gives P = P'.
Then, have
TV(P, = P(E9) P(E9.
Taking expectation over (yis 3i+1) gives
Lemma B.3 implies that E[P(ES) X E[ S 6. Therefore, we have
Furthermore, the same argument also implies that
(T)
Proof of Lemma B.2. We start by considering another process Pa defined as
dx; = (v (ogg((z))) +
AT 44411 A Axx
+ V2dB., xo ~ p(x ys).
We can see that Combining this with Lemma 1.15, we have that
E [IV(P,Pt) < EE(V(ol( m.) v:)))l 8.
E TV(P,
Pu) 5o.
By Markov's inequality, we have that
Pr TV P 2 1o s 0(1
Bi-34+1
Furthermore, by Lemma A. and our constraint on T,, we have that
TV Mx (++1)) < E 2 21-0
Pr
M
Therefore, we have that
Pr TV ((41)) < + {oa 1- 1(
Combining this with Pr (f( 1411).(( 1-- A0 2 1- O(x-1), we conclude that for
JT Pr.
Pr [TV |
(41) = إoa > 1 0(A
C Control of Score Approximation and Discretization Errors
In this section, we consider these processes running for time T:
Process P:
AT Mit1 - AT Au; di + V2dB. on ~ p (v)
dx. = (xxx)) +
Wi-1
Process P: Let 0 = t ...
< tM = T'' be the M discretization steps with step size
fj+1 - ty h. For t [tj, tg]]
dx. (S(ze,)
AT
Wi41 AT Ari, di V2dB, xo p(x 11)
Tht1
26

---

Note that P is exactly the process (2) we run in Algorithm 1, except that we start from 20 p(z y:).
We have shown that the process P will converge to the target distribution p(u yi+1). We will show that the process P will also converge to p(r 11+1) with small error
Lemma C.1. Let be (ò,r, R. L, a) mode-centered locally well-conditioned. Suppose the follow- ings hold for large enough constant C > 0:
-T>
mm max+ (og(A))
Th |AA1I TR?) S
C%
12 THAll Mh+s
(IAI]I+ 1o4 (02+((22)))) + 22
Then running P for time T guarantees that with probability least 1/2 over yi and yo+1,
have:
(Ta+ TR
(nTORR + 1|Al| R + MIlAlly mn + vall
TV ( ((41)) Se+ A8 A6 AVT.
Escore
of
In this section, we assume p (6, R, L, a) mode-centered locally well-conditioned. Without loss of generality, we assume that the mode of p O, i.e., 0 O. Let = La, iee, the Lipschitz. constant inside the ball (0, R).
We will also consider the following stochastic processes:
Process Q:
dx. = (xx)) + AT y:
A Axse
di + V2dB,
3o ~ p(æ yi)
17
Process Q' is the process Q conditioned on de E B(0, Rt) for 1 E [0, 7]
Process P' is the process P conditioned on 2, B(0, R) for I [0,
We first note that following the same proof in Lemma B.3 that bounds TV(P, P'), also bound TV(Q, Q').
Lemma C.2. Suppose the following holds:
A|l
(IAAIr mlvm++++++++++m+ (2 2 ln2d//6))).
R 7
We have that
EITV(Q,Q')
Lemma C.3. We have
hLR+ h ||||| |ell| + h ||A|| R
E xeea
[||
2e, 11 S
+ d
Proof.
E xr~i''
[|| I2,, 21,
11110 (s(or))
AF AT Axs
E xr
ds v2dB,
(f11 [o(os))) )
17
AT y1
AT Ax.
E
+ Bm
E
ds
E
/ d B,
(h [b]lA|I] [laal|
h || R
S(hLR)* +
+ E
2 B
27

---

Since Jr V2dB, ~ NN(O, (t - (t))aa), we have that Ells; v2dB, de tt,²² 2 dhh?. This
gives that
xi [| Ie, 11,11 x hLR+ h I|A
Mill + + +|||||
+ d
Ni ni C(n, 1/+,)3 12 for a large enough constant C. Lemma C.4. Suppose |All TR²) S
(dpp (((( ) = 0(1).
E TT
Proof. By Girsanov's theorem, for any Irajectory 2o.....t
dP'
cxp(..)))))MM
= cxp(M))
dQ'
where the Girsanov exponent M2 is given by
M, = 1
V2 / (by(ar) dB,, 1/- [
for
AT B1+1 A Ax
AT y/ AT Ax
(x,
Tit11 ATA Vi+1
y/1 - A Axu(m) - -1++1
Since Q' is supported in B(0, R),
[IAIIl 1411l1794411 10 11l n2+1) fig
( So
1/
Now, for := = 16 (x dd, we have that M, N (2-N((11) (-1 1
So.
E [exp(22M)) S exp(sy/2) exp(ni/t/2)
Note that l1 Vi+1 n2+12ill has mean (1 / ( Arrl and is subgamma with variance
m (1 v/ 11?) and scale n - " Thus, for ||| 12
nin we have
||11
11 1 - )
E (2x)(2MM)
< E
exp
mali 1:92
1
|| (T22 1/ T/t m22mm
S exp
2
+
1/
niiink mz
(1 - ) + (11 - -1 (((1)))1111(()))))
cxp
[|A - 12.1)22 (t2m + tR?)
exp
1/ 1/-11
$ 1.
28

---

Lemma C.5. Let E be the event on such that TV(Q.Q), S Suppose
1/ C(ni 12
Then,
TV(P', P)] $1-P1 ((+ A
mp ) hLLR+ h 11A R hIll
mon
vdh
+ Escore
Proof. Note that the bound is trivial when Pr [E]
< 1/2. Therefore, we can use the fact that E] [-] throughout the proof. We have, for any E [t,, t,11..
ATA T
E
E
||((z)) 5(22,) +1
(xt
Z1,)
Me E Pa
dp
ATA
(Tt Wziz) 17]1
E
E
- (1s(x)))((xr,))11) 3(1r,))12
With 11 E E'
aQ'
mp
P' (aq' (z+)
)
27
AAT A mp
E w: x
[|s(z1) - 5(2,,, +
(xc
2z,)
The first term can be bounded using Lemma C.4. Now we focus on the second term. Note that
WIE II~ [11)(x))) (zx,, )l{
E
<
E M.IB
E LI~O'
[1s((x)) sZ s211
+
E [[Is(1r,)
- -22,, )1
w.
Since is L-Lipschitz in B(0, Rt,, and using Lemma C.3, we have
A
E E
[10(2z) - a(1,,))))) =1
{xx I22s)
ZINQ'
7
AT
4
E
L
+
[1102] - Iz, [1
Th
AT 4
ILLR+ h ||A ys + h 11 R
4
+ d2
T
A
hLR+ 1 R + h A|I mmn
L+
dh
T
Since Q' a conditional measure Q, conditioned on E, we have Therefore,
I --TViQ $ 2.
E To
E EI
[1ls(1555) - 8( 11
E
2 E [11((1)))) - S( ) |1
M6
F.
[1(s(1e,)) ((cr,)111
E
@
score
This gives that
ATA
Iz,)) 27
E
E
[|s(2.) 5(1z,) 1|
(xe
vc m
A
||Al R + AIlA
<
L
[LLR+
ddh
+ 2
eccore
m1
v/3
29

---

Thus, by Girsanov's 's theorem,
M
511
A A
(xz It, 11
E Mi9t41
KL Pd P)
E
[Is(xe)) ( )1
j=
ST.
(1
(
||
hLR++
|||A|| - -1|lA||| /mnl
Vell
+ c ecore
os
By Pinsker's inequality,
E TV(P', s VT. ((1+ |1A|1 (II+)
)
h ||Al R + mll
ALL++
+ vih
Eccore
M..0441 E
mi
m
Hence,
TV(P', PP] 11-Pr(B) + TV(P', Pi]
Vc.8i41
$ 1r + VT. (1++ )
)
(IIR+
|||l
R + A|]l
+ v vdh
+ Eccore
Then have the following corollary: Corollary C.6.
Suppose
m < Chi v
Then,
E 0c.81411
PV(P.P) [T Q1)
((I+
(II+1AAlP)
11A11) )
1| R + M+III + vdh
+ VT.
[LLR+
np
mi
E Eccore
Proof. We have that
E 30.0++1
TV(P,P)]
< E [TV( E ITV(P,,))
Furthermore,
[TV(P,,))
SPr TV(Q,Q) 1 2 + VT. ((++
1|A113) oi
ILLR+
1|
R A||
mm
+ vdh
Eccore
SE(TV(Q. ((++1A)3)) (ALR+
1|AA
R
mmy
vel
Escore
where the last line follows from Markov's inequality. The gives the result.
Proof of Lemma C.I. We note that by our definition of ni.
(A TR²)= <
m
1
4
nf (
C(
12 2
C2?
30

---

Then, combining Corollary C.6 with Lemmas B.3 and C.2, we have
E
(T((P.P) & E +
04.0i+1
VT. (
||A12)
||A + ||
mmn
hLR+
Vah
+ Escore
28+V1 VT. ((=+1)) (1A))))))
hLR+ h
R + b|| ||
Vmn.
vdhh
+ E Escore
n
The conditions Lemmas B.3 and C.2 are satisfied by our assumptions, noting that 7h+1
< 4
implies the bound on R holds for both processes.
Applying Markov's inequality and combining Lemma B.2 with the above, we conclude the proof.
D Admissible Noise Schedule
Recall that define process P. that converges from p(æ: y:) to p(x y6+1): Let 0 ti
LM = T be the M discretization steps with step size li+1 - Li- = h. For E [4:4)
A A Yit1
A Art;
dx. (((1,))
dt v2dB, mo p(æ vi)
(10)
Th+
We have already proven that we can converge the process from p(x: y:) to p(æ: 36+1) with good probability, as long as some conditions are satisfied. Those conditions actually depend on the choice of the schedule of and T. In this section, we will specify the schedule of and T.
Now specify the schedule of nn and T.,
Definition D.1. We say a noise schedule 7h > ..... TJN together with running times Ti. TN-1 is admissible (for set of parameters C, a, A, d,E, R) if:
nN r
m 2 A|AI|| V
d. 0²
For all 7V (n./T441) 1, we have S 1 and
T, 2 C m% + log( (AEE)
Furthermore,
||
+TRR)) (T,, <
11
C22
The reason we need satisfy the last inequality is to satisfy the conditions Lemma C.I. We formalize this in the following lemma.
Lemma D.2. Let C 0 be sufficiently large constant and p be (8,r, R. L, a) mode-centered locally well-conditioned distribution. For any 8, E (0,1) and X > 1, suppose
(m log A| cm?
d dlog dlog(d/)) (mm))( log()/e))
R2
[IA]]r+ +og(110) +
For any admissible schedule (πK)εE[)) and (Ti) rumning the process for time Ta guaran- tees that with probability least 1/2 over yi and Me+1
log(A/e)
TV p(x: Bi+1)) $ 28
X
(Edis + Escore);
a
where
Edis = (Ia+
I1A1P) 12
(nTaRt
h
||
b|lAI| my
+ /dh.
172
31

---

Proof. It is straightforward to verify that an admissible schedule satisfies the first two conditions of Lemma C.I.
For the third condition regarding R, our assumption states:
(m + log || (14]] 104lr+ log(1/0)) d dllo(d/6)mm + log(A (A/e))
R2
an7
a
Given that T; <
m-/lng(AAr) this choice of is sufficient satisfy the third condition in Lemma C.I.
Therefore, applying Lemma C. at each step we obtain that with probability at least 1/A over and Vi+1:
TV(TT,P(2 Vi+1))
((oa l1Ali2)
(hīaR+ 1 1111111 R R+blllll/mm + Vdh
S WVT
Escore
th
+ log(A/s)
56+ \
(Sdis + sccore)
We also want to prove the following two lemmas:
Lemma D.3. Let p be d-dimensional (8,r, Rr L, a) mode-centered locally well-conditioned dis- tribution. For any 8 E (0, 1), suppose
d
2 llog(1/8)
R 2
Then, suppose m 2 ||al||
with probability at least over y1,
TV(p(x vi), p(x)) S + 26.
Lemma D.4.
There exists admissible noise such that
p²aR?
m²
log 2+ Avdp
N S
Vi m mlog(A/e) + aNE
where p
|||| nya
D.1 The Closeness Between p( yn) and p(x)
In this part, prove Lemma D.3, showing that any admissible schedule has large enough m, enabling us to use p(z) to approximate p(x y1).
We have the following standard information-theorees result.
Lemma D.5. Let X E R. be random variable, and Y = X + +0, 1m)) Then,
1(x;)) & log det [I Cov(X)
172
Lemma D.6. For any distribution p with Expp [|| Ex
m2 we have
||A||mz
E (TV(( v1))p(x)) S
2m
Proof. Note that E [KL(((> 9:) [l)() is exactly the mutual information between x and ys. In addition, we have
[p<(p [))l [(x) < (Ax; yi) s z log det 4m + Cov(Ar)
||||| ||||2m3
<
2n
32

---

By Pinsker's inequality, we have
||A||m2
T (TV((( v)). I
2m
Lemma D.7. Let p be d-dimensional (ō,r, R, L, o)) mode-centered locally well-conditioned prob- ability distribution. Assume
d +
2 llg((1/8)
R 2 2
Then
|||||
d
(V bn); p(x)) 2 m
Proof. Lemma B.14 provides an a-strongly log concave density satisfying
TV p) 35.
For an a-strongly log- concave law the Brascamp- Lieb inequality yields Cov, I a a hence
d
m2 = (El 1x113)1/2
Applying Lemma D.6 to ğ gives
d 2m V a
|||
E [[T((p( 181),(())
Note that
TV(p( 91), p(x)) & TV(p(1 v1), v1)) + TVx (1).(()) + TV()()).((t).
Integrating in yi and using the elementary fact
(TTV v1), [1)) (V,,
y1
together with the above calculaion, yields
|| d
E
[TV(( v1).p(x))
2 m V a
+ +8..
91
This proves the stated bound.
Now we prove Lemma D.3.
Proof of Lemma D.3. By Lemma D.7, have
|||||
d
[V v1), p(x))]
711
a
Since all admissible noise schedules satisfy m
This implies
A|ll
Consequently,
E (TV(( vi), p(x))) x 6
8.
X
By Markov's inequality, with probability at least 1 over y1
TV(p( vn), p(x)) S & + Ao.
which proves the lemma.
33

---

D.2 Bound for N Mixing Steps
In this part, we prove Lemma D.4. Lemma D.8. Let a, Do > 0, and let c > 0. Consider the number sequence
Fi+1 = (1 + min((ar:)), 1))xa
For every B > 0, let (B) be the minimum integer i such that 2; 2 B. Then
k(B) =0 =0(120)) log
_ )
B
1+
To
Proof.
We show in two steps that the time to go from to 1/a, then to B. Define
k min N 2 1/a),
Bound for kj. We first show that kn S (a Consider the quantities
N₂ min (i E N xi 2 20 and j be the smallest j such that NN 2 1/a. If instead To 2 1/a already, then h 0 and there is nothing to prove.
Assume 20 < 1/a. For each " define
1 = a000)) =
We claim that
N5+1 - N2 S 41.
Indeed, for each! j <,",
N₂ Nyttt=1 II Ny
(1 + (axx)))
DN,+0
NN
Ny 4- -1
2 aN,
II NN
(1 (1+ (axN,))) = IN, (1+ (axx,)))²
Since
(axN,) (a. 2'x0) tj¹
get
N 2 21+ UN, 2 2xN, 2 2 2+ xn.
By monotonicity of the sequence (z,), it follows that N,+1 S SN, +ts. Summing over j up j gives
--1
N₂. Σ (N N2) s
Σ (20) S (a
3=0
By definition, Nz- is the first index i such that x; 1/a, so ki N₁- S (axr)-
Bound to achieve B S 1/a, the bound already holds. Now we analyze how many steps Note that for every i 2 ki.
T+41 (1 min((ars)" 1))xr 2zr
Therefore, have
D 1 (1) > 2logg(B/ Ik. 2 B.
This proves that
B < ki + +082
(1+ B S (aro)~ -c *+ +log 1
B Z0
k(B)= < kn + logz
1
1+
Tkk
Fa
34

---

Lemma D99. Given parameters zo, a, > 0. consider sequence inductively defined by 2441
(1 + R),, where
% = min {n S : a²² + by S 2x:
Given B, let k(B) be the minimum integer such that Hi 2 B. Then,
b + log
B
k(B) -
1
D0 b
I0
Proof. We do case analysis.
Case 1: zo 2 62/a. We always choose Y Vxi/a.
We can verify that
2j +
1 Ij 2xi;
a
and this satisfies the requirement for %. By applying Lemma D.8, we have that
Iu
-1/2
B
B
k(B)
+
log
+
I
log
z0
20
Case 2: Fo S B BSb//a.
We always choose 7/6 min(m;; (2:/ /b 1). We verify that
C.3.
b
+ 24 S 2x,
62
and this satisfies the requirement for ". By applying Lemma D.8, we have that
B
k(B) (zo/b) -1 + log
1
Case 3: To S b2/a B. We combine the bound for the first cases, where we first go from z0 to b² then from 6²/a to B. Then we have
k(B) < (zo/6)-1 + log 1+ xo )
B
a +
B
b
a +
B 20
log
1+
log
1+
30
30
b
Proof of Lemma D.4. Now we describe how we construct an admissible noise schedule. Consider start from 1/1 7), and for each iteratively choose of be the maximum y S such that
(7f)*
|A (2( S
C22
and then set 1/441 2²)) We continue this process until reach n/'y 2 |||||| It easy to verify that (7'y) -/.-1--............ m/) is an admissible noise schedule. Now we bound the number of iterations N.
Since for all 7, we have condition for []4]){(7((7)m + (T(7) R2
fr( < [IAI((/mf(()) (nt)*
B/m
R2_ )² sufficient
is that
R
(n/)*
R²
(n/)²
2
[[AI((vmfr(>)
2/m m
C22
2/m
Cy
Therefore, fixing 1/6, we have that > is at least
max 1S1: || ml 1.5
||Al/2 Vmlog(A/E)
|| R²
(n/)
2 +
a
vm
C
35

---

Now we look at the inductive sequence starting from =f², and r++1 = 2o) where
|||| 2
1.5
| ( Vmllg(A/s)) + ||| R²
m
% max 7 7S1
a
By Lemma D.9, we know that for any Ngool
O, we can achieve ON 2 Ngoal within
|All (mLog(A/E)
|A|l R
m²
+ log 2 Ngoul
N S
an?
m log(A/E) + oRR
Taking in Ngool
IIl-II
Va. we conclude the lemma.
E Theoretical Analysis of Algorithm 1
In this section, we analyze the algorithm presented in Algorithm 1. In Algorithm 1, the algorithm initializes by drawing a sample from the prior distribution p(x) via the diffusion SDE, which intro- duces sampling error. [CCL*22 22] demonstrated that this diffusion sampling error is polynomially small, with the exact magnitude depending on the discretization scheme chosen for the diffusion SDE. Since the focus of this paper is on enabling perform posterior sampling, the choice of diffusion discretization and its associated error are not the focus of our analysis. Consequently, we omit the diffusion sampling error in the error analysis presented in this section. This omission does not impact the rigor of the theorems in the main paper, as the error is polynomially small.
unconditional diffusion sampling model to
We start with the following lemma: Lemma E.1. Let C > 0 be a large enough constant. Let be a (6,r, L, a) mode-centered locally well-conditioned distribution. For every ò, E (0, 1) and 1, suppose
(m log Aall
dlog(d/o)(m) log((A)))
(IAIlr n log(1/8) +
R2
a
Then running Algorithm will guarantee that
+ log(A/e)
(Edis + Excore) )
21 N X
Pr M
TV(XN. p(x S E A8 + +2
a
where
[|AII2
( h ||Al AllAll/mm mm
Edis = La +
dh
mp
1/2
Proof. Let Estep Co + A8 + XV
m+Hog(A/E) (Eais + Escore)
where Co is constant large
enough to absorb the implicit constants in Lemma D.3 and Lemma D.2. We prove by induction that for each i E [N]:
Pr (TV(X,, (o) yr)) S i @step] 2 1 X 3
(II)
For the base case (i 1), since X1 p(x), Lemma D.3 gives that (V(()x) p( vi)) ssep with probability at least 1 - 1/> over V/-
For the inductive step, assume the statement holds for some < N. Let E, be the event that TV(X,, p(x 8:)) < 1 Estep- so Pr[E[] < i/A.
Let X² p(# yi) and let X be the result of evolving X7 for time T; using the SDE in Equation (2). By Lemma D.2, the event Fi41 that TV(X; (++1)) S Estep has probability at
least 1 - 1/2 over yr, M+1 and the SDE path.
36

---

By the triangle inequality and data processing inequality:
(V Bi+1)) & p(x uc)) + (V p(z 11+1)).
(12)
If both E, and Fit1 occur, then TV TV(:++,, V)-1))) S (i stsp The probability that this bound fails at most:
Pr(Ef - Pr B ii [1,, Pr(Fi+1 :1.--.. v.]]
x 1 i+1
Thus, the induction holds for i 1, and the lemma follows for N.
Lemma E.2. Let Si and S2 be two random variables such that
Pr MN
[TV((S) .i....,yN) y1 (1...., uN)) 2 6.
Then have
Pr (T[((( UN), (S2 UN)) S 2c) 2
UN
Proof.
Let Ely.....,, yN) be the event such that TV((S) E)),(((2 F)) S e. Then, we have
that
TV((S: uN), (S2 uN)) S Pr[F un| +
Since Pr[F] 2 21-6 6, we apply Markov's inequality, and have
Ey Pr[E uN]l
Pr
Pr
[r UN 2 e]
Hence, we have with probability over y,
TV((1 UN), (S2 yN)) s 2e.
Applying Lemma E.2 on Lemma E.1 gives the following corollary.
Corollary E.3. Let C > O be large enough constant. Let p be a (8,r, R, I,, a) mode-centered locally well-conditioned distribution. For every 8, (0, 1) and X > suppose
(m (m++ anp
log
l + (IA]l A| A|
dlog flog(d/5)(m log (A/e))
R2r+C
a
Define Then running Algorithm will guarantee that
N
Pr[TV(XN,Pta v)) S cerror
2 1
ACervor
with
Eerror S N E + A5 X m + log(A/E) (Edis + eacore))
where
Edis = (Ia+ [1Al12) n2
(NTORR+ h 1| R A mm
v dh
172
Lemma E.4 (Main Analysis Lemma for Algorithm 1). Let p
|| n/a
For all < E, 8 <
there
exists
< δ _ ( (2 (mm2 p p² + 1) 72 m² dm)
+
m
+ log d
Ed
m
d
37

---

such that: suppose distribution p is (k.,//v.. RR, mode-centered locally well-conditioned Va/m K28 then theeehenneee Algorithm samples a distribution
distribution with 2 Ky//a and Escore S Pl v) such that
Pr (TV(p p). v)) se)
Furthermore, the total iteration complexity can be bounded by
(K3 m22 + m² m m² 1) - K p(L x²))
Proof. To distinguish the and in the lemma and the one in Corollary E.3, we will use Eeroor and Serror denote the & and 8 in our lemma statement. We need set parameters in Corollary E.3.
For any given 0 < dervor, Cerrors we set
Eerror X
Aderror
and we set À to be the minimum À that satisfies
p² /Vmlog(A// + p²aR²
vm m logo()/)) RR + log 2 Avdp
m²
< Aderoo Cerror-
Now verify the correctness.
Taking in the bound for N in Lemma D.4, have
R2a +
mlog(A/E) + aR + log 2 Avdp
m
S p² Vmlog(A/E)
I Aderror
vm
By the setting of our parameters, we have Ne S Eerrors A8 S Eerrors and N N//eerror S derror. This guarantees that
Pr TV(Xx. w)) S Eerror + AN + log(A/E) (Edis + Escore)
Serror
is easy to verify our bound on R satisfies the condition in Corollary E.3. Note that a distribu- tion is r, R. L, a) mode-centered locally well-conditioned, then it is also (6, r, R', L, ae) mode- centered locally well-conditioned for any R' s R. Therefore, we can set R be the minimum that satisfies the condition.
p²Vm+ PAR
m²
+ logd))
Eerrorderror
Vm
aR
p(m22 + 1) 72 + m p² + dm)
+ log ))
=
1
m + d
Eerrorderror
mm
$ K.
Therefore, only need AN m+tlo///E) (Edis Escore) S Eerror. This can be satisfied when
Va/m
Edis Eccore
X2deroo V log(A/e) +m" &
K2
Recall that
Edis (Ta+ [[AI12) IntaRt h 1|Al R R+ h||lA||| m n?
dh
n72
< [L+ 12) (hIaRt+ ap + hpyma + vdh
Therefore, need set
h- δ min Reroo alI + (a)( p²) + P pmma]
aa/m
K482 amnd }
38

---

Note that the bound for the sum of N mixing times can be bounded by
Σ T N(log(A/E) + m) I K
N-1
Therefore, the total iteration complexity is bounded by Ō
Kmm ah
Po)R p²) + //maa//maaaaa Serror + K K d(L + of of k <=m([+
Eerror Borro Eerror
We can relax it and make the bound be
of (K'Kkn'd+ +2m
Take and we have
δ (K3(Kmm m² m (mpp + ( + (2))
E.1
Application on Strongly Log-concave Distributions
By Lemma B.12, any a-strongly log-concave distribution that has L-Lipschitz score is locally well-conditioned distribution p is (ò, / + 22og(1/6)) xc, L/a, a) mode-centered locally well- conditioned. Therefore, take this into Lemma E.4, we have the following result.
a
Lemma E.S. Let p(x) be an a-strongly log-concave distribution over Red with I--Lipschizz score. All For all < E, < 1, there exists Let na
(2² (m p + m) d m² p²) + d + log d ))
K
Ed
m
Vafm K28
such that: suppose E score
then Algorithm samples from distribution p( y) such that
Pr [TV( p(x v)) = d.
Furthermore, the total iteration complexity can be bounded by
p(L// δ (K3 + m² m (mpp² +)Va) + K p R²))
To enhance clarity, we state our result in terms expectation and established the following theorem: Theorem E.6 (Posterior sampling with global log-cancavity). Let p(x) be an a-strongly log- concave distribution over Rd with L-Lipschitz score. Let = nVa exists
|all For all 0 < 1, there
/
p² ((m2 pt + m) d + m p²)
m log ))
K K
2
Vm
vo/m K²g
such that: suppose score S
then Algorithm samples distribution p(æ v) such that
[TV(p( v). p(x v))] S E.
Furthermore, the total iteration complexity can be bounded by
δ (K3 m² 2d + m3 p + m 1.5 (mpp +1)a)) + p22 + K²m² ((22p((//a + p2))
This gives Theorem 1.1.
39

---

Theorem 1.1 (Posterior sampling with global log.concavity). Let p(z) be an a-strongly log- concave distribution over TRd with I.-Lipschitz score. For any < e < 1, there exist K₁ = poly(d, m. nya² algorithm that takes K2 iterations to sample from a distribution p( y) with
Va ]A 1 ()) such that: if E Kg then there exists [[ 2) and K2 poly(d, m, nya
E [TV(pl 1y)p(x [1)]] S..
Remark E.7. The analysis above restricted to strongly log-concave distributions, where V Pogg(() O. However, this directly implies that we use algorithm to perform pos- terior sampling on log-concave distributions, for which 4 logp(r) 30.
Specifically, for any log-concave distribution p. we can define distribution g(z) & p(z)
2m3 22m -1x==1112²) ). where 0 is the mode of p and m is the variance of p. is straightforward
exp
log- concave. Therefore, by sampling from q(x: v), we can upproximate p(a y), incurring additional expected TV error ofe.
to verify that TV(p. S E, and q is (E²
E.2 Gaussian Measurement
In this section, we prove Theorem 1.2. In Algorithm 2, we describe how to make Algorithm I work on the Gaussian case.
We first verify that suppose Assumption holds, we can also have accuraaee estimates for the smoothed scores of Pzg. this satisfies the requirement of running Algorithm 1. We need to use the following lemma, with proof deferred to Section E.5.
Lemma E.8, Let X, Y, and be random vectors in R where Y = X + N(, oa and X + (0, La).). The conditional density of Z given Y, denoted p(Z Y). is a multivariate normal distribution with mean
Pz|
= =
= +02)
and covariance matrix
Σzer - 02 + - oo
Then, the gradient of the log-likelihood log p(Z Y) with respect to Y is given by
1 of (Z 0z -
Vy logg(Z Y)
Using this, caleulate the smoothed conditional score given No:
Lemma E.9. For any smoothing level 2 O, suppose we have score estimate Sya (xx(x) of the smoothed distributions (z) = p(x) * (0, t Ia) that satisfies
E (1)))())) sip (x))1) E & (x)
Then we can calculate score estimate & 2 (x) of the distribution P2 (x) = Pmo (x) *N 1l such that
E
120. (2))11))
Et Sccore
P
Proof. Let Pea. Then, for any value of (1), we have
1 (z)(t) = Zate log (+x (o)
2a0 log ((x - Van log p(ao | (0))
(t)(t())) + att logp(zo (*))
Note that the second term is exactly in the form of Lemma E.8, the first term, use score estimate λya (x))
calculate this exaclty. For
) for it. In this way, we have that for any
||3 (x) 1 (x) || (x) sx)))]
40

---

Therefore,
E
E (
(20)
Sm (x:
= (1 S20, (2))111 - 44
score
p22(2)
Applying Markov's inequality, we have:
Corollary E.10. Suppose Assumption 1 holds for our prior distribution p. Then with 1 prob- ability over zo: we have smoothed score estimates for Pag with L error bounded by s sccoee /ō; in other words, Assumption 1 holds for Pzg- where Eacore is substituted with Eccore/8 /
To capture the behavior of a Gaussian measurement more accurately, we first define relaxed version of mode-centered locally well-conditioned distribution.
Definition E.11. For å E [o. 1) and R. L, E (0, too), we say that distribution is (6, R, L, locally well-conditonee if there exists 0 such that
Przup [x E ((0, 21
For z, B(8 R), we have that [s(x)) s(y)ls La || y/l.
For v,y y E B( R), we have that (s(y) =sx), y) a ||ı -
Note that this definition due to the following fact:
still imply that the distribution is mode-centered local well-conditioned,
Lemma E.12. Let p be probability density Rd. Fix 0 < < R and 0 R such that
Pr 3(0,r)] 2 0.9, Vl(-log((z) ald (x B(0, R)), > 0.
If R >> 4dr, then there exists 6' E B(0, 4dr) with V p(0' = O.
We defer its proof to Section E.5. This implies the following lemma: Lemma E.13. Let p be r, R, I, oi) locally well conditioned distribution with R 9dr and < 0.1. Then p is (6, (4d + 1)r, R 4dr, L, a) mode-centered locally well conditioned.
This gives a version of Lemma E.4 for locally well-conditioned distributions as a corollary: Lemma E.14 Let p
||А|| nya
For all O < e, 5 < 1, there exists
1 p² ((m² p² + 1) d=7² + m² p² + dm). d + log d
K < Ō
8ō
vm
such that: suppose distribution is a f/, R, T,, mode-centered locally well-conditioned distribution with R > /Kymia and Escore S Valm tion p( y1) such that
K=5 Then Algorithm from a distribu-
Pr [TV((( p(x b) 2
Furthermore, the total iteration complexity can bounded by
δ (Kx (K3 m2d + m² p m mm= 1) p 2 K p(n p²))
The reason we want this relaxed notion locally well-conditioned that, this captures the behavior of Gaussian measurement. First note that:
Lemma E.15. Let p be distribution on Fdd Let Itrus NO, of ment of Dtrae p. Let pz(x) be the posterior distribution of given V. Then, for any 8 E (0, 1) and 8' (0, 1), with probability at least 8' over Σ,
La) be a Gaussian measure-
Pr 20pp
B 8
por=ooldd 22 )
41

---

Algorithm 2 Sampling from p( Wo. u) given extra Gaussian measurement To
1: function GAUSSIANSAMPLERG, R2 + RR zo R y E R", A R "1. E R)
2: Let Pao (x) := p(r x (0, zo).
3: Use Algorithm 1, return
POSTERIORSAMMLERR(PH y, A.
4: end function
Again, we defer its proof to Section E.5. This implies the following lemma.
Lemma E.16. For ő E (0, 1), suppose p is distribution over Rdd such that Pr [Va B(x', R) I.a. lolog((1) 3 (+2 / 2 5. g'rup
Given a Gaussian measurement xo NO o² La) of x ~ with
R
2/d + 2o (og(11))) + 2T
Let = N0,, where x Then, suppose R. with probability at least 1 1-36 probability To. Puo is (6, (l.o / 4llo )), R/2, 2L + 2, 2 locally well-conditioned.
Proof. Let us check the locally well-conditioned conditions with 0 Ig one by one. The concen- tration follows directly from Lemma E. incurring an error probability of 8.
By our choice of a, we have that
R
Pr |1:00
x|15
8.
2
Therefore,
Pr [Va B(ro R/2): - LIa 3 V By direct calculation, we have that
logg(()) 3 (F2/RR) 2 25.
1 2
-Laa = logg((z = (F = -LL+ = V2 logp(x) 3 (72 R2²
By our choice of a, we have that whenever - LIa 3 2 log (z) = (r
-(2Lo² + 2) 20
la logp(z) 3 20 la
This satisfics the Lipschitzness and the strong log concavity condition by giving an additional error probability of 28.
This gives us the main lemma for our local log-concavity case: Lemma E.17. For any 8, T, R, L > O, suppose p(x) is distribution over IR.d such that
Pr [Va B(x', R) LIa 2 logp(x) = (T²/R²) Id] 2 1 8.
x'op
Let |Alle There exists
(m?3pt + 1)d d + m² p² + dm)
+ log ))
K Ō
m d
Eδ
Vm
such that: suppose R22 2 (Kym + 40 and Excore S Ri/ma then Algorithm 2 samples from
distribution p( Zo. y) such that
Pr (f( xo p(x zo, w)) 2=|21-011 20.3)
Furthermore, the total iteration complexity can bounded by
δ (K3(K3 + m² m (mpp + L) + p² 1)2 K3 pompp(Lo' + +0² +
42

---

Algorithm Competitive Compressed Sensing Algorithm Given a Rough Estimation
function COMPLESSDDSENSINGP R² R. 20 R y R Ruxd 17, R. R)
2: Let a = R/6.
3: Sample z zo + (0, d²
4: Use Algorithm 2, return
GAUSSIANSAMPLER ". (,7,7.0)
5: end function
Proof. Combining Corollary E.10 with Lemma E.16 enables us to apply Lemma E,14 and proves lemma.
Expressing this in expectation, we have the following theorem.
Theorem E.18 (Posterior sampling with local log-concavity). For any 8, T, R. L > O, suppose p(x) distribution over IR such that
Pr [V E B(x', R) LIa logp()) 3 ( 2 x up
Let p ||lla There exists
0² ((m2p² + +1) d + mm + dm) m + log )
k
K
Eδ
vm
such that: given a Gaussian measurement zu = = la) of ~ p with R² 2 ( (KyTH +4T)o?
and scooee S K2//ma' then Algorithm samples from distribution p(x To, y) such that Fo, v..)),(
E
(TV
Fo. v))1 E
20.9
Furthermore, the total iteration complexity can be bounded by
δ (K3 m² p m (mp² +1)adj(To p² +)2 x2m2p(Lo + +p² x2+1) +1)
This gives us Theorem 1.2:
Theorem 1.2 (Posterior sampling with local log-concavity). For any E, , R, L > 0, suppose p(x) a distribution over Idd such that
Pr (Vo E B(x', , R): -Lla 4 x'pp
V logp(x) (72/18)) 2 -
Then, there exist K1, K2 = poly(d, m, LAIe ( and K3 = poly(d, m, LAll Loz) such that:
Given Gaussian measurement = x. + N(, Ta) of x p with S R/(K1 + 2r). If Kgo then there exists an algorithm that takes K3 iterations to sample from a distribution p(x No, y) such that
E Escone S. 1_
E (TV g.z0
zo, (n.).. p(x
No. (l):))]] Se.
E.3 Compressed Sensing
In this section, prove Corollary 1.3. We first describe the sampling procedure in Algorithm 3. Now we verify its correctness.
Lemma 19. For any 8, r,, R, R' L 0, suppose p(x) is distribution over B.d. such that
Pr Vr E B(x', R) : LIa = 2 ( d'op
Let p
|A|R There exists
( p² ((m2 + 1) d3 m3 + dm)
+ log d) ))
K s δ
+ m
82
mm
d
43

---

such that: suppose (R')3 2 (Kym + + and eccore S "K.mR then conditioned on I - a||5 R, Algorithm of Algorithm samples from a distribution p (depending on z/g and y) such that
Pr
(T. + NN(, = z/g, Ax + u)) = 6) 2 -
Furthermore, the total iteration complexity can be bounded by
δ K (K2 m + m mm 1)vā)(Loo* p² +1) K2m pLo 0² + +1)
Proof. This is a direct application of Lemma E.17. The sole difference is that zo follows 20 + N00 La) instead of x + (0, La). Because ||zg - x R. 4o remains sufficiently close to a for the local Hessian condition to hold, so the proof of Lemma E.17 carries over verbatim.
Now we explain why we want to sample from p(> x x+ = z/ Ax + = y). Essentially, the extra Gaussian measurement won't hurt the concentration of p(: y) itself. We abstract it the following lemma:
Lemma E.20. Let (X,Y Y) be jointly distributed random variables with X RRd Assume that for some >> 0 and 0 < 8 <1
Pr Y, X~xx)(
- - I| 2 8-8.
s
Define Z X 8 where NO o² la) is independent of (X,Y). If
r
2
28'
then for X p(X 2Y one has
Pr ||I - 811 Sr) 2 1- 33. Y.Z. X
Proof. Fix Y and draw auxiliary point X p(X Y). Let 2 Xe' with 9' ~N
independent of everything else. On the event
E = = - X rr
Z and Z' are Gaussians with the same covariance g²1, and means X and X. Pinsker's inequality combined with the KL divergence between the two Gaussians gives
| XI
o2 ( s
S
S 5.
20
20
Hence
XV, because Pr[E"] < by the hypothesis on p(X Y).
I Pr[E + < 28
By construction,
x(x r) E2 Y Y,
so
Pr
||| x|| St) 2 8.
Y,2, & X-p(X|
For the set A = 1(Y,2, X) : X X1|
r} the total-variation bound gives
Pr [A]
Pr Y
[A]] S 26,
x22X
whence
Pr X 81 Sr) 2 1 - 8 - 28 1 36.
Y.Z. X
This implies the following lemma:
44

---

Lemma E.21. Consider the random variables in Algorithm 3. Suppose that
Information theoretically, is possible to recover & from y satisfying 1| - æl1 S r with probability 1 5 over p and y.
. Pr x S R 1 8.
Then drawing sample T p( NO0 r2 =/ Ar + 5 y) would give that Pr
Pr|l +|| 2r] 2 -
Proof. By [JAD+21], the first condition implies that,
Pr 2. (..l)pp()
|||e 2 E||5 2r| 2 1 26.
Then by Lemma E,20, suppose we have x' = (00,00 I²Ia), then
Pr w.y2--p(eyv.otMM00000..
|| 100-21 2|| 2r] D 68.
Note that whenever | xolls r, we have
TV(x' 2,200 2, S 6.
This proves that
Pr w.y.-ppeey.z
-| E|| 2r] 2 68.
Lemma E.22. Consider attempting to accurately reconstruct from y Ax + &. Suppose that
Information theoretically, it is possible to recover &t from y satisfying || - xel S r with
probability 1 over p and y.
We have access "naive" algorithm that recovers zo from y satisfying 1|:00 =11 R with probability 1 - over I ~ p and y.
Let
||||| 78
There exists
p² (mm2p² + 11) d3 m² + dm)
+ log d ))
K <
m + d
82
mm
such that: suppose for R' (R/8) v
Kym p²
+
Pr WI B( R.) -La V logp(x) 1 (T 2 8.
P'O
Then give algorithm that recovers f satisfying || - < 2r with probability O()), in poly(d, m, n
|AIR 1) time, under Assumption with Escore < K² (m/58
Proof. By our assumption and Lemma E.19, we have that we are sampling from p(z + (0, o² o² = 2/1 Ax + E = y) with TV emror with 1 O(6) probability. By Lemma E,21, this would recover æ within distance 2r with 1 O()) probaility, Combining the two gives the result.
Setting 0 would give Corollary 1.3 corollary.
Corollary 1.3 (Competitive compressed sensing). Consider attempting to accurately reconstruct from y = Ar + E. Suppose that:
Information theoretically (but possibly requiring exponential time or using exact knowledge of p(x)), is possible to recover from y satisfying || - x1| v with probability over and y.
45

---

We have access to "naive" algorithm that recovers from y satisfying 1| -x s R with probability over p and y.
For Rt = R. poly(d, (d, m, [|ll 3).
"
VV B(d', R³) LLd I V2 logp(x) 20 x'up
Pr
Then give algorithm that recovers E satisfying | - x/l I 2r with probability O()), in
poly(d, m, | :) time, under Assumption I with Escore < poly(d, A ..RR)
E.4 Ring example
Let E (0, 0.01) and let po be the uniform probability measure the unit circle S {i R
|>||= 1}. Define the Gauss-Ga mixture
1
2r
expl ||
(cos
(cos0, 0, sin 111
p(z) (po NO0 u (x))
d0,
R22
2n
Jo
2
2w
Lemma F.23, For any x E R2 with radius r = ||>||>> 0, the Hessian of the log- density satisfes
we)
0<rs w
2w
2 logp(x) 1
w w2)
w² <r <1
2²r
0,
r>l.
Proof. Rotational invariance gives p(z) = p(r with
22
p(r) = 2 exp
To
r
r r20.
2w
w
Write f(r) logp(r) and z r/w² O. Using 11(2) [122, we get the first and second derivatives:
(3)//o))) ("(r)
-
((()
w
w 1o(=2
For r >> 0, the eigenvalues of 2 logp are
f( A(r) ('(r)
The Turán inequality is Ar(r).
2 implies X,(r) S -1/w²: thus, the largest eigenvalue
Since [=))/To(2) < for all > 0 and 1 (2)/Io(2) & 2/2 for 0 < <2
1
0 0< <<r< 5 w²
2
2
(z)
Xe(r)
2
2 To(2)
2² <r 1
u
22
0,
r > 1.
Lemma E.24. For every x E R.2, we have
v logg(()) 2
u Iz.
46

---

Proof.
Write u (cos 0, sin 0) and
/
2x
e 112 |la-wu1//(2vs) d8.
p(a) = 2n
2Tw²
Differentiating under the integral gives
Vp(x))
(-=
x u
1
1 (2=1)(/(22²) d0
p(x) (x
Elu xz),
w2
2T
2w
w
so
I
1E/u x]
V Vlog((>) =
w²
Differentiating once more,
12
2 (1)
V
Vl(u a]].
w²
w²
standard score-covariance identity shows
V x Cov mls( (u,
Cov ul))).))
w²
w²
hence
Cov ulr(u) 12
V log
w.
Since Cov w/a (u)(u) 2 0, it follows that
V logp(x) - w²
I2.
claimed.
Lemma E.25. For any (0,1/2), we have that
Pr
Va B(x', 1/2) la
1 w
2 logp(x)
1
1
Ta
2 1 2(11w²))
s' x'rup
2w
Proof. Note that
Pr |||>||> 3/4] 2 1 - -Q(Lww²)
wrop
The rest follows by combining Lemma E.23 and Lemma E.24.
Hence, we can apply Theorem 1.2 on our ring distribution and get the following corollary:
Corollary E.26. Let A E Cx2 be matrix for some constant C >> O. Consider x p with two measurements given by
= N and == + N 70,
Suppose |A|w/n O(1). Then, if a S ew and Escore S cw- for sufficiently small constant > Algorithm takes a constant number of iterations to sample from distribution p(x [ro, y) such that
[V Fo. v).p(z wo. v)) 0.01.
Fo.y
E.5 Deferred Proof
Lemma E.8. Let X, Y, and be random vectors in Rd, where Y X +N(0,, La and Z X + N(0, Ta). The conditional density of Z given Y, denoted p(Z Y), is a multivariate normal distribution with mean
Pzy = =0 +0,)
and covariance matrix
Σz1 = (o + -
Then, the gradient of the log-likelihood log pZz Y) with respect to Y is given by
1
Vy logp Y) =
(z 03 + -
oo
47

---

Proof. Since Z Y ~ [uzzi, ) the oog-likelhhod function is
log YY) - 1 ( (Z ) (Z (zirr) log det((z + dllog(2)))
To compute the gradient with respect to Y, focus the term involving Mzy
2 (Z- (2I) " 2 -(ZIx)
Differentiating with respect to gives:
Vy [z (zzr Σー y (z- = -2E - -z(rr) VYuzI.
Since Mzzy (o9 -y we have
VYRZYY o2(0p + +0²)=
Thus, the gradient becomes
Vy logp(z Y) = ->ziir (Z - (2zr)) o3 + +z))
Substituting the inverse of the covariance matrix Σgly, we get
1 Σ = o (o + 0z))
and the final expression for the gradient
Vy lo Y) = of
(Z o2(07 -r).
Lemma E.12. Let p be probability density on Rd. Fix 0 < r < R and 0 E Rdd such that
Pr(x E B(0,r) r)] 2 0.9, ((-logp(x)) 2 ala (x E B(0, R)), a > 0.
grop
If R >> 4dr, then there exists 0' E B(0, 4dr) with V log (0') = 0.
Proof. By Lemma 131,, there is a normalised density g satisfying V Vlog Vlogp on B(8, R) and such that log q is a-strongly concave IRd, The difference log log g is therefore constant on (0, R); hence
p(x) C ((x))
E B)O
for some C >
Let J arg max g: strong concavity gives V log ((1) = 0 and uniqueness of Assume for contradiction that || 0|| 4dr. Set 2r/1lr |Iw - O|| 1/(2d) and define
T(x) = (1 - A)x + Ap..
Then det Dr = (1 x) and rB)) B(0', (1 A)r) with 0' = (()) C B(8, R). Along
any ray starting at μ the function r log q(v + t(x n)) is strictly decreasing for 2 hence q(T(x)) 2 ((x) for every x.
change of variables yields
Pr[B(0', (1 A)r) / ((T(x)) x) dz (1 Pr(B((r)))
B(0rr
Because À S 1/(2d), (1 --² 2 -- 1/2 > 0.6. Multiplying by and using p Cg on B(B, R) gives
Pr|B(0', (1 X)r) > 0.6 Pr(B((.r)) 2 0.54.
The two balls B(8,r) and B(0', X)r) are disjoint, so > 0.9 + 0.54, a contradiction. Thus || 0||< 4dr.
Because 4dr < we have j B(0, R) and here Vogp V log y: consequently V Vlog(()) 0. Putting 0' = completes the proof.
48

---

Lemma E.15. Let p be distribution on R Let Itrue + (O, d² be a Gaussian measure- ment of Ptroe p. Let pz(x) be the posterior distribution of given Then, for any 8 E (0, and 8' E (0,1) with probability at least 8' over T,
Pr J 20p2
oldd+ V 2lgg log 55
Proof. Let Q()) Pr Prepps || [1--)| Đ||> r|. We want show that with probability at least 8' over I, Q()))))= S 8. This is equivalent to showing that Pr=[Q(²) > ö] S 8'.
We use Markov's inequality. For any 0:
[x)
Pr(o(#) > oj - 6
Thus, suffices to show that [x(Q(T)) S 68'.
Let's compute E3 [Q(T)]:
//m p(as d)
[[((T)] -a12
/ p(o) plas T)dr dā
( p(ar,, Fydor dē.
Using p(x1,3) = p(ū x1)p(x1), we can change the order of integration:
[[Q(T) f p(z1) (/ p( x1 dij dx1.
Given 21, the distribution of 7 is N(11, o² T2). Let 7 = - x1. Then Z ~ oT)) The inner integral is 11) rj. Let W = Z/o. Then ~ La). The inner integral be- comes Pa(r/o) Ptw-Noo.. r/a]. So, Ex[Q(T)= = Pa()) = Pa(r/a).
We need show Pa(r/o) 58'. We the standard Gaussian concentration inequality: for W ~ NO, Ta) and 1 0,
Pr[l[W| s
5e --/2 6/2
We want Po(r/o) < 88'. So we set e 2//2 88'. This implies f/2 log(11(88')), so t /2)8)( This choice of t is real and non-negative since 8, E (0, 1) implies 58' E 1), so log (og(1((888)) 2 O. We set r/a = vd + = vd + (2log(1/(86")) Thus, for (vd+ 2 log 58
1
have Pa(r/o) 86'. 56'
With this choice r, r, we have Eg (2())) < 58'. By Markov's 's inequality,
E (
58'
Pr Pr
8'
8
This means that Pr, [Q([) 2 8'. which is the desired statement:
8) 2 8-8
Pr Pr |||
क| 21
x<p;
49

---

Why Standard Langevin Dynamics Fails
As discussed in Section 3, after we get an initial sample Xg ~ p on the manifold, natural attempt to get sample from Py is to simply run vanilla Langevin SDE starting from Xo:
d X ((x.) + - AX.)) dl /2 d B,,
Xo~p
(13)
where ((x) is an approximation to the true score V (ogg(()) We now show that under any T/ score accuracy assumption, the score error could get exponentially large as the dynamics evolves.
Averaging over Y/ does not preserve the prior law. We first consider the simplest one-dimena Gaussian case of (13). Suppose p (0, 1), A and noise & = (O so y ~ (0, 1 + r7²). Then with the perfect score estimator ((X,) = V (lg) = -X, (13) reduces to
dx, (-X, + + - x.) dt V2 Br,
Xo ~(0,1)
(14)
Recall that the hope of guaranteeing the robustness using only L guarantee is that at any time f, averaging X₁ over y will preserve the original law p. We now show that this hope is unfounded even in this simplest case.
Lemma F.1. Let X, follow (14). Averaging over NO + 17)), and variance
X2 is Gaussian with mean
1 1 e-at
2at
(1 - e aatya
Var(X,) = 2att +
S 1,
n2
112 1n2 1 1+ 112
where a 1+42 1f² > In particular, Var(X,) 2(+077 time t =
Proof. Write the mild solution of (14):
X, Xge +n 2y ca((--)) ds+v2 f cal(t-e) d Xne -a
y 1-e -at
+V2 f call-oo dB..
Xne-at++
n7² a
Because Xo, B are independent of y, conditional moments are
1 - e oct
1 - 2-t
B[X, vl 77 a
Var(X, v) e -2at
2at
Applying the law of total variance with Var(y) 1 1/2 gives the stated formula. Since Xy and B are independent of y, conditioning on y gives
1/ at
Var(X, 1) e -2at + e 2nx
E X
1/2
By the law of total variance and Var(y) = + 1??
-2at 2at
+ (1 - -at)
Var(X,) = c -2at
a
1 1 172
Using a = (1 + //² and simple algebra, this simplifies to
Var(X,) = 1 2 2e- (1 -at)
1 172
which is at most 1 and attains 1 - 1//2(1 n when at = 1/2, that is at t*.
Thus Var(X,) first shrinks below 1 (by constant factor bounded away from when 1j is small) be- fore relaxing back to equilibrium. The phenomenon harmless in one dimension but is catastrophic in high dimension.
50

---

High-dimensional amplification. Let p (0, take A = Id, and set r7² 0.1. Then with the perfect score estimator, (13) reduces to
dx, (-X,+ Xi) d v2 d,,
Xo (O
(15)
By Lemma F.1 applied coordinatewise, at time t" := 17 In2 + 172 averaging over y yields
X.. ~ Pr- p= N(0, with 0² = 2(1 17²)
Hence X₃- is exponentially more concentrated in high dimension. We next show that this concen- tration amplifies score-estimation errors exponentially with the dimension.
6
Lemma F.2. Let (0, and let p =N(00 o² IaIa) with o²
For any finite k 1 and
11
E < there exists score estimate $ R Rdd such that
Exzp [1]((x) v logg(<>)) S Se
yet
Pr (1]3(x) v Vlogp<>)12> od E) 2 1 - 2e odd
for some constant e depending only on k.
Proof. Fix k > 1 and 0 <<< < 1. Let 11
(0.1) and choose E (0, mi,min(1/2, 1/02 -1)).
Define the shell
Sp = {x RR. |a112-o²d| S pa podd
Write m == Pra=p|æ E S,) and q == Praup, ( Sp). Since |x112/02 ~ Xa under pes, the
chi-square concentration inequality Lemma A.ll gives
p²d
q 2 exx
8
Since (1 + p)o² 1, the Chernoff left-tail bound for x3 yields
m zmup
Pr ||| (1 + p) < exp(-Id),
I:
11(((1 -1-2221-1(((0) -1 +p)0?) 0.
]/2 2/ ((
Choose any unit vector u and set
e(x) = M 1s, (x) u.
8(x) V logp(z) + e(x),
M :==em->>
Then
[|](()) v logg(<))
E smp [||{))]|* M ek
smop
Moreover [|e[x]]]= M on Sp. hence
- -2-88
Pr [(x) - V Vlogp<>)12 M
Pr [x E Spl 2 - zmpp
xmpp,
Using -Id we have M = = 1/2 (1/k)d Setting
{
1 / 0, K.
min
which depends only and gives
Pr
[[](()) logp(z)) ad [d E] 1- 1-2e-al
a-Pp-
This completes the proof.
51

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes, the main claims are all reflected in the scope and contributions, dis- cussed the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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.
fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss limitations of our algorithm and theorems in the introduction.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specificattin, asymptotic approximations only holding locally). The au- thors 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, c.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to 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 ad- dress 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 i acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Ys]]
52

---

The main paper contains proof overviews, and the appendices contain the full rigorous versions of all proofs of all stated lemmas and theorems.
Justification:
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 theo- rems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We provide details for reproducing the experiments in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data also be provided via
often one good way accomplish this, but reproducibility detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of model checkpoint, other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or a way to re- produce the model (e.g., with an 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 au- thors are welcome to 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., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
53

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We provide open access the code. The datasets we use are open access.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines
cc/
public/guicn Beeeii//uuddes/eeSataeeeee soteeesubbmsssioooooocoyc.o for more details.
While we encourage the release code and data, we understand that this might not be possible, so "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a 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 (https: //nips wwtpccccppccccaeeccccccccccceele ggwcc//g/////////ooo Codeeubmiii ssi siioiiyy 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. only a subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provide all details for the experiments in the paper
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to 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, or as supplemental material.
7. Experiment statistical significance
Question:
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We report error bars where relevant.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars 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.)
54

---

The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should careful not to show in tables or 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 tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide information about the compute needed in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well 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 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https::/ wttppuuripp..pppppppeeeee wc/ppulic/Bchiiccuteeeeee
Answer: [Yes]
Justification:
The authors read through and reviewed the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: Our contribution is aonain-agnostic foundational research, so a detailed societal-impan discussion would necessarily be high-level and speculative. We do not believe it would be a useful use of reviewer time.
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 or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
55

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning 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 mitiga- tion 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 ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We are not releasing data or models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by re- quiring 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 relcasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All the assets are properly credited and the license and terms of use are ex- plicitly mentioned and properly respected.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (c.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 the pack- age should be provided. For popular datasets, paperswi thcode. com/ datastts has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
56

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the pa- per include the full text instructions given to participants and sereenshots, applicable, well as details about compensation (if any)?
Question:
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 crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
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 equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
57

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification:
There is no LLM usage in the core methods in this research.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https:/ /ttppss///euris..../ cc/Confereecess220555 for what should or should not be described.
58


Reviews:
[{"review_id": "e8asw7gmQO", "reviewer": "Reviewer_EJdf", "summary": "This paper looks at how to sample from the posterior distribution  p(x | y) , where y = Ax + \\xi  is a noisy observation and the prior  p(x)  is known or well-approximated. Posterior sampling is useful in tasks like image inpainting, deblurring, and MRI reconstruction, but it’s usually hard to do in general.\n\nThe authors focus on the case where the prior is log-concave. Normally, Langevin dynamics can be used when the score function (the gradient of the log-density) is exact, but it is very sensitive to errors in score estimation.\n\nThis paper shows that by combining diffusion models with an annealed version of Langevin dynamics, it’s possible to do conditional sampling even when the score estimates are not perfect—only needing an  L^4  error bound instead of a much stronger condition. This is a nice theoretical improvement over previous work.", "questions": "- Is it possible to test or check in practice whether the L^4  error bound holds for learned score models?\n\n- Can the authors give a simple example where their result applies and shows the improvement clearly?\n\n- Could the method work for more general priors or other types of observations beyond the linear setting?", "limitations": "The main limitation is that this is only a theory paper—there’s no algorithm or experiments. It also doesn’t connect to a lot of newer work on how Langevin dynamics performs when actually used with step sizes. The setting is limited to log-concave priors and linear problems.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\nThe paper gives a new way to think about posterior sampling using recent tools from diffusion models.\n\nIt shows that weaker conditions on score accuracy are enough, which is important for practical settings.\n\nThe theory is clean and the goals are clear.\n\nHelps connect ideas between different sampling approaches (Langevin, diffusion, score-based methods).\n\nWeaknesses:\n\nThe paper is only theoretical—there’s no actual algorithm or method that someone can implement.\n\nIt doesn’t cover more general situations, like non-log-concave priors or nonlinear measurements.\n\nIt doesn’t mention or cite recent work on how Langevin methods behave. \n\nWhile the score error bound is weaker than before, it still might be hard to get in real-world settings.", "was_revised": true, "final_justification": "The authors explain more of my doubts, and according to this, I update my score.", "rebuttal": "Thank you for your review. We respond to your comments and questions below:\n\n> *The paper is only theoretical—there’s no actual algorithm or method that someone can implement.*\n\nThis comment, as well as the related one in the limitations section, perplexes us -- we have implemented the algorithm and shown improvements over the existing DPS method; see the Experiments section for details.\n\n> *It doesn’t cover more general situations, like non-log-concave priors or nonlinear measurements.*\n\nOur analysis *does* cover non-log-concave priors as long as they are *locally* log-concave as we describe on page 2 -- see Theorem 1.2 for the formal statement. For general non-log-concave priors, it is impossible to design a polynomial time posterior sampler, as [1] shows.\n\nWe thank you for asking about nonlinear measurements -- in general, unless the posterior density is log-concave, our analysis does not apply; for nonlinear measurements, log-concavity is not guaranteed. If this posterior is log-concave, our analysis gives a natural starting point for this setting, but a complete analysis is beyond the scope of this paper.\n\n> *It doesn’t mention or cite recent work on how Langevin methods behave.*\n\nWe have provided a comparison with existing works in the Langevin literature on page 5 -- to reiterate, when the score function is known exactly and the distribution is strongly log-concave, the Unadjusted Langevin Algorithm is known to converge rapidly [2]. If an approximation to the score is known satisfying a strong MGF condition, [3] showed that Langevin converges, but fails to converge if the score approximation is only $L^p$-accurate for any $1 \\le p < \\infty$. Our analysis shows that for *posterior sampling*, an annealed version of Langevin converges even if the score approximation is only $L^4$-accurate.\n\n> *Is it possible to test or check in practice whether the $L^4$ error bound holds for learned score models?*\n\nThis is a great question -- in practice we see that our method *does* improve upon DPS as noted above, which suggests that either the scores are being learned in $L^4$, or that our method continues to work even for $L^2$ accurate estimates.\n\n> *Can the authors give a simple example where their result applies and shows the improvement clearly?*\n\nOne simple example is the Poisson distribution -- since it is a log-concave distribution, our algorithm is guaranteed to converge. In contrast, DPS suffers error depending on the Jensen gap, which is non-zero for this distribution.\n\nNote that standard Langevin fails to converge even for the Gaussian distribution, while our annealed version converges -- see Appendix F for a discussion.\n\n\n[1] Diffusion Posterior Sampling is Computationally Intractable. Shivam Gupta, Ajil Jalal, Aditya Parulekar, Eric Price, and Zhiyang Xun. ICML 2024\n\n[2] Theoretical guarantees for approximate sampling from smooth and log-concave densities. Arnak S Dalalyan. Journal of the Royal Statistical Society Series B: Statistical Methodology, 2017.\n\n[3] Convergence in kl and rényi divergence of the unadjusted langevin algorithm using estimated score. Kaylee Yingxi Yang and Andre Wibisono. NeurIPS 2022 Workshop on Score-Based Methods, 2022."}, {"review_id": "PlPZXPTFMR", "reviewer": "Reviewer_FxWY", "summary": "## Summary\n* This paper shows that there exist polynominal time DPS given $\\epsilon$ error conditional score estimation, which is better aligned with the fact that DPS works practically. To the best of my knowledge, this paper is the first one to show there exist polynominal time approximated DPS. Despite many previous work have shown exact DPS can be achived asymptotically [Practical and Asymptotically Exact Conditional Sampling in Diffusion Models] [Diffusion Posterior Sampling for Linear Inverse Problem Solving: A Filtering Perspective], no complexity gauntree is given. Previous theory also shows that exact DPS requires expoential time [Diffusion Posterior Sampling is Computationally Intractable], while no complexity result is shown for approximate DPS.\n* The authors shows empirically that their method can improve DPS, given a DPS initialization on FFHQ dataset and linear operators.", "questions": "* I am wondering if Algorithm 1 will work without init from DPS, on real world images such as FFHQ.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "## Strength\n* Despite previous work show that exact DPS is computationally intractable [Diffusion Posterior Sampling is Computationally Intractable], this paper show that there exists polynomial time algorithm for DPS with small score error under some assumptions.\n* The proposed theory can be used to construct a very competitive compressed sensing. Their approach can be used as a refiner to a compressed sensing algorithm, such that if there exist any other refiner can do $y$ accurate in expoential time, their approach can do $2y$ accurate in polynomial time.\n* This paper seems to be the first one that can achieve DPS with arbitary small error with polynomial time at the same time.\n\n## Weakness\n* The log concave assumption of $p(x)$ is really strong and can be really far from true for natural images such as FFHQ. The general diffusion community has got rid of log concave assumption several years ago [Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions]. It might be better to use a different assumption, i.e. Gaussian Mixture Model [Theoretical insights for diffusion guidance: A case study for gaussian mixture models], which is a lot more aligned to the distribution of natural images.\n* Another practical consequence of log concave assumption is that, it is possible that Algorithm 1 works only locally because natural images are log concave only very very locally. In fact, considering the fact that log concavity limits the distribution to single mode, the natural images are log concave only if we limit to the local area of a single image. Therefore in Section 4, I am not even sure if Algorithm 1 can work independently without a good initialization from DPS. That is to say, the line 7 in Algorithm 1 should really be $X_1 \\sim \\hat{p}(x|y)$, where $\\hat{p}$ is some approximation to posterior.\n* The DPS works well practically. However, it might work as a maximizing a posterior estimator, not a conditional score estimator. In fact, [Guidance with Spherical Gaussian Constraint for Conditional Diffusion] [Rethinking Diffusion Posterior Sampling: From Conditional Score Estimator to Maximizing a Posterior] show that the score error of DPS is very large. To generate a good sample, the approach proposed is sufficient but might not necessary. It is possible to generate good sample with very large score error, and the theoretical result of DPS might be improved without limiting score error.", "was_revised": true, "final_justification": "Thanks for the rebuttal. I still recommend to accept this paper. \n\nI am really surprise that being a theoretical paper is considered a weakness by other reviewers. Personally I think this paper is a very interesting and important step over [Diffusion Posterior Sampling is Computationally Intractable]. And I encourage the other reviewers to take the theoretical contribution of this paper into consideration.", "rebuttal": "Thank you for your thorough review and positive evaluation. Below we address each of your comments point by point.\n\n> *The general diffusion community has got rid of log concave assumption several years ago.*\n\nYou're right that unconditional diffusion models can work with very flexible distributions, thanks to access to smoothed scores. Posterior sampling, however, is more difficult: you cannot quickly compute the smoothed score of the posterior from the smoothed scores of the prior. As shown in [1], once we lose access to smoothed scores and have to work with unsmoothed ones, no polynomial-time algorithm exists for sampling from a general non-log-concave posterior. That’s why in the literature on unsmoothed-score samplers, log-concavity remains a common assumption. \nIn fact, the hardness example in [1] is itself a Gaussian mixture, so replacing the prior by a mixture of Gaussians would not avoid the same barrier.\n\n> *It is possible that Algorithm 1 works only locally.*\n\nWe agree, and that’s exactly what we formalize in Theorem 1.2: When the prior isn't globally log-concave, as long as it's log-concave in a local region around the target, our algorithm can still do posterior sampling — once it's localized to that region.\n\n> *The line 7 in Algorithm 1 should really be $X_1 \\sim \\hat p (x \\mid y)$.*\n\nAlgorithm 1 is designed for priors that are globally log‑concave, so sampling $X_{1}$ from $p(x)$ is sufficient. For priors that are only locally log‑concave, Algorithm 2 in Appendix E.2 replace the global prior by its localized counterpart -- just as you suggest.\n\n> *The approach proposed is sufficient but might not necessary. It is possible to generate good sample with very large score error, and the theoretical result of DPS might be improved without limiting score error.*\n\nYou're absolutely right that DPS sometimes produces high-quality samples even with large score error, especially if it's implicitly maximizing the posterior. But in this work, our goal is sampling from the correct posterior — not just generating plausible outputs. Maximizing the posterior may give sharp samples, but they’re biased, even in simple settings like a mixture of two Gaussians.\n\n> *I am wondering if Algorithm 1 will work without init from DPS, on real world images such as FFHQ.*\n\nThe experiment in Section 4 falls under the locally log‑concave setting, where an initializer inside the correct region is required. DPS supplies such an initializer, but a simpler choice like the pseudoinverse $A^{\\dagger} y$ is also possible, albeit with weaker performance. For a truly globally log‑concave prior, Algorithm 1 would not need any special initialization.\n\n[1]: Diffusion Posterior Sampling is Computationally Intractable. Shivam Gupta, Ajil Jalal, Aditya Parulekar, Eric Price, and Zhiyang Xun. ICML 2024"}, {"review_id": "tYh7i494VM", "reviewer": "Reviewer_Q4o5", "summary": "The authors in [1] show that in general posterior sampling using diffusion models is intractable. However, under some conditions on the distribution (i.e., local or global log-concave $p(x)$) and $L^4$ error bounds the authors present a provably correct algorithm for posterior sampling.\n\n[1] Gupta et al. \"Diffusion Posterior Sampling is Computationally Intractable\" (2024)", "questions": "- Is Theorem 1.2 limited to Gaussian noise $x_0 = x + \\eta, \\eta \\sim \\mathcal{N}(0, \\sigma^2 I)$ or can it be extended to other noise types (e.g. Poisson, mixed Gaussian-Poisson)?\n- Why do you have equality for the equation after line 218? \n- page 1, line 26: I do not understand the sentence \"it is 2-competetive with optimal in any metric\" ? \n- Why do you express Theorem 1.1 and Theorem 1.2 as existence results (i.e., \"there exist an algorithm...\") and not directly state that Algorithm 1 satisfies these properties?\n- I think the result in Theorem 1.2 is more relevant for practical applications, as local log-concave is weaker than global log-concave. Looking at Section 3.3 (page 8) and Algorithm 1 it seems that you are not using the local log-concave condition? On page 2, line 67-74 you motivate the local condition, but Algorithm 1 does not make use of an initial reconstruction $x_0$. \n- I do not really understand the results in Figure 3. Why does the $L_2$ increase if you decrease the step size, is this not counter-intuitive? Also DPS seems to be better than your method in FID for both super-resolution and Gaussian deblurring?", "limitations": "The authors do not address limitations.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths:\n\nThe paper is a good response to [1], proving that one can do posterior sampling with score-based models under additional assumptions to the underlying distribution $p(x)$. The local log-concavity conditions is well motivated (e.g. Corollary 1.3 for compressed sensing). Further, the presentation of the paper is good - including Section 3 \"Techniques\" to present important details of the proof. \n\n### Weaknesses:\n\n- You always state that you need *merely* or *just* an $L^4$-error bound. Do you mean *merely* in comparison to the MGF bound? Because, in my opinion an $L^4$ error bound is still quite strong, given that the score matching loss is formulated in $L^2$. \n- On page 6 you use the estimator for the conditional score as $\\hat{s}_y(x) = \\hat{s}(x) + A^T(y - Ax)/\\eta^2$. It is fairly known, that is approximation is quite rough. Why do not use other approximation, e.g. DPS? Does the proof only work for your approximation? \n- You cite MRI as an application in multiple parts of the paper (page 1, line 32 or page 2, line 67 and even the abstract), so I would expect to also see MRI experiments. \n\nMinor things: \n- page 1, line 25: In MRI the forward operator should be in $\\mathbb{C}^{m \\times d}$. \n- page 3, line 98: Missing reference for \"posterior sampling is know to the near-optimal\" \n- page 3, line 99: Grammar \n\n\n[1] Gupta et al. \"Diffusion Posterior Sampling is Computationally Intractable\" (2024)\n\n[2] Chung et al. \"Diffusion Posterior Sampling for General Noisy Inverse Problems\" (2024)", "was_revised": true, "final_justification": "The authors have addressed all of my points. I raised my score to 4. I still think the paper is an important response to [1], showing that posterior sampling is possible under certain conditions on the distribution. However, I have not carefully read all steps of the proof, as most of it is part of the Appendix.\n\nI agree with reviewer afB1 that the paper would benefit from a stronger empirical evaluation.\n\n[1] Gupta et al. \"Diffusion Posterior Sampling is Computationally Intractable\" (2024)", "rebuttal": "Thank you for your review. We address your comments and questions below:\n\n> *$L^4$ bound requirement*\n\nOur requirement of $L^4$-accurate scores for posterior sampling is *significantly weaker* than the MGF bound required for log-concave sampling in general; [1] shows that score approximations that are $L^p$-accurate are insufficient for Langevin convergence for *any* $1 \\le p < \\infty$. \n\nWe admit that $L^4$-closeness is still a strong requirement -- we suspect that even $L^2$ accurate scores are sufficient for provable sampling using our algorithm, and hope to address this in future work.\n\n> *On page 6 you use the estimator for the conditional score as $\\widehat s_y(x) = \\widehat s(x) + A^T (y - Ax)/\\eta^2$. It is fairly known, that is approximation is quite rough. Why do not use other approximation, e.g. DPS? Does the proof only work for your approximation?*\n\nWe are confused by this comment -- if $s(x)$ is known exactly, $s_y(x) = s(x) + A^T (y - Ax)/\\eta^2$ is *precisely* the true conditional score. Thus, our approximation $\\widehat s_y(x)$ is the natural one given only approximate scores $\\widehat s(x)$.\n\nIn contrast, DPS attempts to replace the scores of the *smoothed* conditional distributions with a lossy approximation. We only work with the *unsmoothed* conditional distribution, which is the one that Langevin uses.\n\n> *Is Theorem 1.2 limited to Gaussian noise or can it be extended to other noise types (e.g. Poisson, mixed Gaussian-Poisson)?*\n\nThis is a great question -- our analysis certainly gives a natural starting point for analyzing other noise types, but doing so may require modifying the annealing schedule and is beyond the scope of this paper.\n\n> *2-competitive with optimal in any metric*\n\nThis means that if the best possible reconstruction algorithm achieves error $\\varepsilon$ with probability $1-\\delta$ in any metric, posterior sampling has error at most $2 \\varepsilon$ with probability $1-2\\delta$. \n\n> *Why do you express Theorem 1.1 and Theorem 1.2 as existence results*\n\nSure, we're happy to restate them more explicitly. The original phrasing follows a common convention in theory papers, where the focus is on the properties and guarantees rather than the specifics of the algorithm itself — to the extent that many such papers don’t even present the algorithm in full.\n\n> *Looking at Section 3.3 (page 8) and Algorithm 1 it seems that you are not using the local log-concave condition*\n\nAlgorithm $1$ is for Theorem 1.1, the global log-concave case -- Algorithm $3$ in Appendix $E.2$ handles the locally log-concave setting, and makes use of the initial estimate $x_0$.\n\n> *Figure 3*\n\nIn our experiments, we use the step size as a proxy for controlling the time spent running the algorithm. So, as we decrease step size, so that the time spent is decreased, we expect the sample obtained to be farther from the target conditional distribution, and closer to the starting sample $x_0$. Thus, we expect the sample to be farther from the ground truth, as we see. \n\n[1] Convergence in kl and rényi divergence of the unadjusted langevin algorithm using estimated score. Kaylee Yingxi Yang and Andre Wibisono. NeurIPS 2022 Workshop on Score-Based Methods, 2022."}, {"review_id": "I5dcrLic0I", "reviewer": "Reviewer_afB1", "summary": "The authors propose running annealed Langevin dynamics to sample from the posterior distribution when solving inverse problems of the form $y=Ax+\\xi$. The authors also propose a number of theoretical results with respect to this approach, namely deriving an upper bound on the estimation error of the conditional score.", "questions": "See Strengths and Weaknesses.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\nS1) The paper is reasonably well-written and easy to follow.\n\nS2) The theoretical results are interesting and (as far as I know) novel.\n\n**Weaknesses**\n\nThis paper suffers from three major weaknesses: novelty, discussion of related literature, and experimental evaluation. I outline these issues below.\n\n**W1) Novelty**\n\n- While the theoretical results are novel (to my knowledge), the proposed method - using annealed Langevin dynamics for posterior sampling in inverse problems - is not. However, the authors suggest that they are the first to propose this approach. This is problematic, as it impacts the novelty of this work significantly. \n- [1] was the first modern diffusion paper (to the best of my knowledge) to propose sampling with annealed Langevin dynamics in the unconditional case, and [2] directly extends this approach to conditional sampling, using the same conditional score proposed by the authors of this work (see the equation on the bottom of page 6 of the submitted paper and Eq. 4 in [2]).  I fail to see a meaningful difference between the proposed work and [2].\n\n**W2) Discussion of Related Literature**\n- The current discussion of related diffusion literature is insufficient. While I can appreciate trying to have a focused discussion on related methods (due to the breadth of diffusion methods for inverse problems), the current discussion is insufficient. Major methods such as DDRM [3], $\\Pi$GDM [4], and, perhaps most important, DAPS [5] are absent from the discussion (to name just a few methods). Consequently, the discussion of related work needs to be fundamentally revised to acknowledge the broader diffusion-for-inverse-problems literature.\n- One very noticeable missing citation is [6]. [6] is the foundation on top of which most modern diffusion literature is built, and Langevin dynamics is also discussed/applied in that paper (mostly based on [1]).\n\n**W3) Experimental Evaluation**\n- The experimental evaluation of the proposed method is completely insufficient and inconsistent with the broader literature. There is no evaluation table for the selected problems! The evaluation should be rebuilt from the ground up with quantitative results (nominally, PSNR, LPIPS, FID) for each problem listed in a well-formatted table. I would advise the authors to look at how DPS [7] presents their results in Tables 1 and 2 of that paper for inspiration.\n- In addition to presenting experimental results more clearly, the authors need to compare with more relevant baselines (e.g., [2, 3, 4, 5]) to better understand how their approach performs.\n\n**Some Minor Weaknesses**\n\nThese things do not impact my score, but I hope that the authors will take them under advisement.\n\n- It is good practice to differentiate scalar and vector quantities in the text. I would suggest something simple, like boldface to represent vectors/matrices. This makes reading and understanding the math much easier.\n- Figure 5 has a lot of wasted white space. I would suggest reformatting the figure to be more space efficient. Image grid figures also look nicer (generally) with less white space.\n\n[1] Y. Song and S. Ermon. 'Generative modeling by estimating gradients of the data\ndistribution', in Advances in Neural Information Processing Systems, 2019.\n\n[2] A. Jalal, et al., ‘Robust Compressed Sensing MRI with Deep Generative Priors,’ in Advances in Neural Information Processing Systems, 2021.\n\n[3] B. Kawar et al., ‘Denoising Diffusion Restoration Models,’ in Advances in Neural Information Processing Systems, 2022.\n\n[4] J. Song et al., 'Pseudoinverse-Guided Diffusion Models for Inverse Problems,' in International Conference on Learning Representations, 2023.\n\n[5] B. Zhang et al, 'Improving Diffusion Inverse Problem Solving with Decoupled Noise Annealing,' in Proceedings of the Computer Vision and Pattern Recognition Conference (CVPR), 2025.\n\n[6] Y. Song et al, 'Score-Based Generative Modeling through Stochastic Differential Equations,' in International Conference on Learning Representations, 2021.", "was_revised": true, "final_justification": "After reviewing the paper again, I am swayed by the authors' arguments. I did not properly evaluate this work in my initial review, and after doing so I feel that it is worthy of acceptance for its' theoretical contributions.", "rebuttal": "Thank you for the thorough review of our submission. We appreciate your feedback, though we believe the assessment overlooks the core contributions of our work. \nThis is a theory paper, and we hope it can be assessed based on the theoretical questions it addresses, the insights it provides, and the theorems it proves. We respectfully ask you to reconsider your evaluation based on these criteria.\n\nBelow, we respond to your specific concerns.\n\n\n### **Novelty**\n\nWe’re glad you found the theoretical results novel.\nYou expressed concern that the methods we used to obtain these results are too similar to existing approaches, which you feel significantly reduces the novelty of our work. We **strongly disagree** with this view.\n\nOur goal is to find a posterior sampling method that is provably robust. In this context, simplicity is a strength. Demonstrating that a relatively simple method (annealed Langevin dynamics) satisfies strong theoretical guarantees makes the result **more** meaningful, not less. In fact, if we could prove that even vanilla Langevin dynamics is a robust posterior sampling algorithm, that would be an even better result!  Except that such a statement is false, as we show in Appendix F, so we need to use annealing.\n\n> *I fail to see a meaningful difference between the proposed work and [2].*\n\nWe find this comment puzzling. Paper [2] doesn’t provide any robustness theorem, or any theoretical analysis of annealing, or guidance on choosing a schedule.  We also want to clarify that our proposed algorithm is quite different from [2] in design and purpose.\n\n\nSpecifically, [2] uses the same observation $y$ at all times, and just anneals down the measurement variance $\\sigma_t$.  In contrast, our method simulates a measurement process by also adding variance to $y$, so that at stage $t$ the measurement $y_t$ being considered is drawn according to the annealed variance $\\sigma_t$.  Our version ensures that on average, the marginal distribution of the intermediate samples $x_t \\sim p(x \\mid y_t)$ matches the original marginal $p(x)$; this is a key property to be able to bound the error in each stage.  We do not believe the algorithm in [2] could achieve our Theorem 1.1 for any annealing schedule.\n\nWhat also sets our work apart is that we don’t just use annealed Langevin dynamics — we analyze why and when it works, and offer a principled annealing schedule based on this analysis. That goes beyond what previous works have offered, which typically rely on heuristics or hand-tuned parameters.\n\n\n\nTo sum up, **the fact that annealed Langevin dynamics has had empirical success only strengthens the impact of our results**. We\n* identify failure modes of existing approaches,\n* introduce an alternative annealing design that circumvents those issues, and\n* provide formal theoretical guarantees.\n\n\n> *However, the authors suggest that they are the first to propose this approach.*\n\nWhere do we suggest this?  We never intended to suggest that \"annealed Langevin dynamics\" is a new idea, it's a pretty natural one.  We do believe that we are the first to prove a theorem about any version of annealed Langevin dynamics for posterior sampling.  Furthermore, our version of annealing does not appear in prior work.\n\n#### **Novelty of Techniques**\n You acknowledged the novelty of our theoretical results, but we also want to highlight the novelty of our proof techniques. Our paper is the first  to introduce the idea of “controlling the expectation of intermediate distributions” in posterior sampling (see Section 3 for a detailed discussion). We also provide a complete proof framework for formalizing this idea, as laid out in the appendix and in the proof organization paragraph on page 9.\n\nTaken together, we are confident that our work is both theoretically significant and methodologically novel.\n\n\n### **Related Literature** \n\nWe really appreciate your suggestion on including more related papers. We were mostly focusing on papers that have theoretical guarantees, but we will cite and discuss more related works in the final version of the paper.\n\n### **Experiments**\nLook, this is a theory paper and should be judged as such.  We view\nthe experimental section as \"better than nothing\": it demonstrates\nthat the algorithm can be implemented and perform OK, but not much\nmore.  We don't discuss our experiments until the last page of our\npaper.\n\nPlenty of theory papers at NeurIPS have no experiments at all; please\njudge our paper as if it didn't have them, rather than rejecting 55\npages of theory over 1 page of unconvincing experiments.\n Turning theoretical ideas into SOTA  systems that beat all baselines is a substantial effort in itself and goes beyond the intended scope of this paper.\n\n### **Formatting suggestions**\nWe appreciate your formatting and clarity suggestions. We’ll boldface vectors/matrices and tighten Figure 5 in the final version of the paper.\n\n\n---\n\nWe hope this clarifies the novelty and significance of our work. We’d be grateful if you could reconsider your evaluation in light of these points."}]

Author rebuttal:

Meta-review: This paper addresses the problem of sampling from a posterior defined by way of a diffusion model. Essentially, suppose a sample is drawn from a diffusion model, then put into a linear transformation, and then convolved with Gaussian noise. If that transformed+convolved output is observed, what is the posterior over the original image? This poses a significant computational challenge. This paper is shows that when annealed Langevin dynamics are used, samples from the posterior can be obtained with a provable bound on accuracy. This assumes that the diffusion model is log-concave. In fact, this holds even if the scores in the original model are only estimated with some error, although a moderately strong L^4 bound is needed. The method appears to work reasonably well in practice. All reviewers appreciated the work, although some asked for stronger empirical results.
Decision: Accept (poster)