Provable Posterior Sampling with Denoising Oracles via Tilted Transport

Authors: joan  bruna
jiequn  han
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 16:44:16

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

Main paper: 
 introduction: 
 Inverse problems consist in reconstructing a signal of interest from noisy measurements. As such, they are a central object of study across many scientific domains, including signal processing, imaging, astrophysics or computational biology. In the common settings where the measurement information is limited, a reliable solution for these problems usually depends on prior knowledge of the data. One popular approach is to choose a regularizer that utilizes data properties such as smoothness or sparseness, and then solve a regularized optimization problem to obtain a point estimate of the original data. However, this approach often struggles with selecting an appropriate regularizer and might be unstable in the presence of large measurement noise. A more robust approach takes a statistical formulation and seeks to sample the posterior distribution of data based on Bayes's theorem, which allows for uncertainty quantification in the reconstructed data by leveraging a model for the prior data distribution.While accurate models for high-dimensional distributions are notoriously complex to estimate, the resurgence of deep neural networks has provided unprecedented capabilities for modeling complex data distributions in certain high-dimensional regimes. Specifically, score-based diffusion models [55, 33, 58] have achieved remarkable empirical success in generating high-dimensional data across various domains, including images, video, text, and audio. These models implicitly parameterize data distributions through an iterative denoising process that builds up data from noise. Furthermore, there is a growing literature developing theoretical foundations of score-based diffusion models [17, 7, 45, 16, 19] , giving a comprehensive error analysis including score estimation, initialization error and time-discretization error. By generating high-fidelity data, these models can also serve as data prior for posterior sampling in inverse problems in high dimensions. Following this idea, many studies (see, e.g., [40, 22] ) have leveraged diffusion models for posterior sampling. However, as discussed below, various categories of approaches for posterior sampling introduce different uncontrollable errors, such as those arising from the approximation of the conditional score or the use of a limited variational family. This abundance of heuristics contrasts with the principled sampling used in prior data generation, and is often at odds with the statistical guarantees needed in many scientific applications.In this work, we aim to bridge the gap between principled diffusion-based algorithms for both prior and posterior distributions. Focusing on the canonical setting of linear inverse problems, where measurements are of the form 𝑦 = 𝐴𝑥 + 𝑤, with 𝑥 ∼ 𝜋 the signal to be estimated and 𝑤 an independent noise, we first illustrate a negative result, revealing that no method can efficiently sample the posterior in general cases, even with the prior denoising oracle. Subsequently, we develop the tilted transport technique, which utilizes the quadratic structure of the log-likelihood in linear inverse problems in combination with the prior denoising oracle to exactly transform the original posterior sampling problem into a new one that is easier to sample. Figure 1 illustrates a schematic plot of the method using two-dimensional Gaussian mixture examples, showing that while the original target posterior problem remains multimodal, the boosted posterior resembles a unimodal distribution. We establish a precise condition where the density of the transformed posterior problem becomes strongly log-concave, making it suitable for efficient sampling via Langevin dynamics. This condition showcases the interplay between a geometric property of the prior (what we call tilted spread; see Section 5) and the conditioning and noise level of the measurements. Interestingly, the condition can be satisfied when the signal-to-noise ratio (SNR) is either moderately low or moderately high, in contrast with traditional sampling methods, which typically excel only within a specific regime.As a first application, we show that tilted transport can sample from Ising models of the form 𝜈(𝑥) ∝ 𝑒 -1 2 𝑥 ⊤ 𝑄𝑥 , where 𝑥 ∈ {±1} 𝑑 is supported in the hypercube, up to the critical threshold determined by the gap 𝜆 max (𝑄) -𝜆 min (𝑄) = 1, thus matching the performance of Glauber dynamics [24, 1] as well as the computational threshold predicted by the low-degree method [42] . More generally, even when the boosted posterior is not strongly log-concave, it remains easier to sample than the original one. Thus, tilted transport can be combined with any existing black-box posterior sampling methods to enhance their performance. This technique operates without any additional computational cost and functions in a plug-and-play fashion, allowing for straightforward integration into various frameworks. When working with high-dimensional Gaussian mixtures, where an analytical solution to the posterior is available, we numerically validate our theory and demonstrate enhanced posterior sampling performance.Numerous studies in recent years have explored score-based priors for posterior sampling. We note that several recent works [60, 20, 29, 54, 21] introduce hyperparameters to balance the influence of the prior and measurements, resulting in sampling strategies that guide output to regions where the given observation is more likely. These strategies typically deviate from the principles of Bayesian posterior sampling and often lack a precise definition of the resulting distribution. In contrast, other approaches adhere more closely to Bayesian principles. One such approach is variational inference, which involves designing variational objectives and optimization methods based on the structure of score-based diffusion [41, 47, 26, 37] . However, even with an accurate prior score, the accuracy of posterior sampling heavily depends on the choice of variational family and optimization procedures, not to mention the additional optimization cost. Another popular strategy focuses on approximating the score conditional on the measurement using various heuristics [58, 40, 36, 22, 48, 56, 57] . In this approach, approximation errors typically remain largely uncontrollable due to the challenges associated with tracking the conditional distribution for intermediate states. Recently, some studies have adopted sequential Monte-Carlo methods to systematically approximate the conditional score [62, 13, 23] , providing consistency as the number of particles used to approximate the conditional distribution of the intermediate states increases. However, this particle-based method still struggles with highdimensional problems due to the curse of dimensionality [9] . Alternatively, [61, 63] propose plug-and-play methods with denoising oracles for posterior sampling, offering asymptotic guarantees, though the required steps may grow prohibitively in high dimensions.We note that [13] also intuitively explores the possibility of reducing the original posterior to an equivalent one under restrictive conditions in the discrete-time setting. In contrast, our tilted transport technique operates in a fairly generic setting and is supported by a clear theoretical foundation. Concurrently, [49] proposes a conceptually similar two-stage approach for posterior sampling in sparse linear regression, based on a different structural prior rather than denoising oracles. 
preliminaries: 
 Notations:. P (ℝ 𝑑 ) denotes the space of probability measures over ℝ 𝑑 . 𝛾 𝑑 denotes the 𝑑-dimensional standard Gaussian measure, and by slight abuse of notation, 𝛾 𝛿 or 𝛾 Σ denote the centered Gaussian measure with covariance 𝛿𝐼 𝑑 or Σ when the context is clear. For 𝑄 ⪰ 0 in ℝ 𝑑×𝑑 and 𝑏 ∈ ℝ 𝑑 in the span of 𝑄, the quadratic tilt of 𝜋 is the measure T 𝑄,𝑏 𝜋 ≪ 𝜋 with density proportional to dT 𝑄,𝑏 𝜋 d 𝜋 (𝑥) ∝ exp -1 2 𝑥 ⊤ 𝑄𝑥 + 𝑥 ⊤ 𝑏 . We also use the notation T 𝑄 when 𝑏 = 0. ∥𝑄∥ denotes its operator norm. 𝜋 ★ 𝛾 denotes the convolution of two measures 𝜋 and 𝛾. For 𝛼 ≥ 0 and 𝜋 ∈ P (ℝ 𝑑 ), we define D 𝛼 𝜋(𝑥) := 𝛼 𝑑 𝜋(𝛼𝑥) as the dilation of 𝜋. For 𝛽 ≥ 0 and 𝜋 ∈ P (ℝ 𝑑 ), we define C 𝛽 𝜋(𝑥) := 𝜋 ★ (D 𝛽 -1/2 𝛾 𝑑 ) as the Gaussian convolution of 𝜋.Problem Setup. Consider a high-dimensional object of interest 𝑥 ∈ ℝ 𝑑 , drawn from a certain probability distribution 𝜋 ∈ P (ℝ 𝑑 ). We suppose that one has managed to learn a generative model for 𝜋 via the DDPM objective [33] ; in other words, for any 𝑦 ∈ ℝ 𝑑 and 𝜎 ≥ 0, we have access to the denoising oracle DO 𝜋 (𝑦, 𝜎) := 𝔼[𝑥|𝑦], where 𝑦 = 𝑥 + 𝜎𝑤, with 𝑥 ∼ 𝜋 and 𝑤 ∼ 𝛾 𝑑 independent. It is now well-established that, such denoising oracle enables efficient sampling of 𝜋, well beyond the classic isoperimetric assumptions for fast relaxation of Langevin dynamics [17] .Suppose that we now measure 𝑦 = 𝐴𝑥 + 𝜎𝑤, where again 𝑥 ∼ 𝜋 and 𝑤 ∼ 𝛾 𝑑 ′ are independent, but now 𝐴 ∈ ℝ 𝑑 ′ ×𝑑 is a known linear operator different from the identity. Given these linear measurements, we are now interested in the posterior sampling of 𝑥 given 𝑦. This corresponds to the basic setup of linear inverse problems, encompassing many applications such as image inpainting, super-resolution, tomography, or source separation, to name a few. We are interested in the following natural question: can the power of denoising oracles be provably transferred to posterior sampling? By Bayes' rule, the posterior distribution 𝜈 𝑦, 𝐴 (denoted simply by 𝜈 when the context is clear) has density proportional to 𝜋(𝑥) 𝑝(𝑦|𝑥) ∝ exp -1 2𝜎 2 ∥ 𝐴𝑥 -𝑦∥ 2 𝜋(𝑥), and thus we can write it as a quadratic tilt of 𝜋:𝜈 = T 𝑄,𝑏 𝜋 , with 𝑄 = 𝜎 -2 𝐴 ⊤ 𝐴 , 𝑏 = -𝜎 -2 𝐴 ⊤ 𝑦 .We readily identify certain regimes where sampling from 𝜈 might be easy:• If 𝜆 min (𝑄) is sufficiently large, 𝜆 min (𝑄) ≫ 1, then one expects 𝜈 to be strongly log-concave, enabling fast relaxation of Langevin dynamics.• If 𝜆 max (𝑄) is sufficiently small, 𝜆 max (𝑄) ≪ 1, then one expects 𝜈 ≈ 𝜋 in the appropriate sense, and therefore that samples from 𝜋 (which can be produced efficiently thanks to DO 𝜋 ) may be perturbed into samples from 𝜈. • If 𝐴 ∈ O 𝑑 is a unitary transformation, then 𝑄 = 𝜎 -2 Id and the inverse problem reduces to isotropic Gaussian denoising, and is thus at first glance 'compatible' with the structure of the denoising oracle (such observation will be formalized later).At this stage, we can already identify two key parameters of the problem that are likely to drive the difficulty of posterior sampling: on one hand, a proxy for the signal-to-noise ratio, measured e.g., by SNR := 𝜆 min (𝑄)= 𝜆 min ( 𝐴) 2 𝜎 2. On the other hand, the conditioning of the measurement operator 𝐴, 𝜅( 𝐴) := 𝜆 max ( 𝐴) 𝜆 min ( 𝐴) . As we shall see, these two characteristics of the linear measurement system will characterize necessary and sufficient conditions for probable posterior sampling. In the following, we assume the log of prior density 𝜋 is smooth and its Hessian exists ∀𝑥 ∈ ℝ 𝑑 .Denoising Oracles and Score-Based Diffusion. Let us first review the natural connection between denoising and score-based generative modeling. Score-based diffusion models consist of two processes: a forward process that gradually adds noise to input data and a reverse process that learns to generate data by iteratively removing this noise. For example, one widely used family for the forward process is the Ornstein-Uhlenbeck (OU) process1:EQUATIONwhere 𝑊 𝑡 is the standard Wiener process. We use 𝜋 𝑡 to denote the density of 𝑋 𝑡 , given by the action of the OU semigroup𝜋 𝑡 = O * 𝑡 𝜋, defined by O 𝑡 𝑓 (𝑥) = 𝔼[ 𝑓 (𝑋 𝑡 )|𝑋 0 = 𝑥],and explicitly given by dilated Gaussian convolutions, O * 𝑡 := C 𝛽 𝑡 D 𝛼 𝑡 , with 𝛽 𝑡 = 1 -𝑒 -2𝑡 and 𝛼 𝑡 = 𝑒 𝑡 . With a sufficiently large 𝑇, we know that 𝜋 𝑇 is close to the density of standard Gaussian 𝛾 𝑑 , owing to the exponential contraction of the OU semigroup: KL(𝜋 𝑇 ||𝛾 𝑑 ) ≤ 𝑒 -𝑇 KL(𝜋||𝛾 𝑑 ).Finally, the measure 𝜋 𝑡 solves the Fokker-Plank equationEQUATIONBy writing (2) as a transport equation 𝜕 𝑡 𝜋 𝑡 = ∇ • ((𝑥 + ∇ log 𝜋 𝑡 )𝜋 𝑡 ), we can formally reverse the transport starting at a large time 𝑇 and solvingEQUATIONSince π𝑡 = 𝜋 𝑇 -𝑡 for 0 ≤ 𝑡 ≤ 𝑇, introducing again the dissipative term leads to 𝜕 𝑡 π𝑡 = ∇ • (-(𝑥 + 2∇ log π𝑡 ) π𝑡 ) + Δ π𝑡 , π0 = 𝜋 𝑇 , which admits the SDE representationEQUATIONIn practice, one runs this reverse diffusion starting from X0 ∼ 𝛾 𝑑 rather than X0 ∼ 𝜋 𝑇 . However, by the data-processing inequality, we have that KL(𝜋|| π𝑇 ) ≤ KL(𝜋 𝑇 ||𝛾 𝑑 ) = 𝑂 (𝑒 -𝑇 ), thus incurring in insignificant error. To facilitate later exposition, we write the above process reverse in time [2, 31] d𝑋EQUATIONand interpret the data generation process as running the reverse SDE from 𝑇 back to 0.By the well-known Tweedie's formula, and up to time reparametrisation, the denoising oracle is equivalent to the time-dependent score ∇ log 𝜋 𝑡 : Fact 1 (Tweedie's formula, [32] ). We have∇ log 𝜋 𝑡 (𝑥) = -(1 -𝑒 -2𝑡 ) -1 (𝑥 -𝑒 -2𝑡 DO 𝜋 (𝑥, 1 -𝑒 2𝑡 )).Log-Sobolev Inequality and Fast Relaxation of Langevin Dynamics. Given a Gibbs distribution 𝜋 ∈ P (ℝ 𝑑 ) of the form 𝜋 ∝ 𝑒 -𝑓 , a powerful and versatile method to sample from 𝜋 is to consider the Langevin dynamicsEQUATION1In practice, it is also common to introduce a positive smooth function 𝛽: ℝ + → ℝ + and consider the time-rescaled OU process d𝑋 𝑡 = -𝛽(𝑡) 𝑋 𝑡 d𝑡 + √︁ 2𝛽(𝑡)d𝑊 𝑡 . Our results could be applied directly to these variants by rescaling time. For the ease of notation, we keep 𝛽(𝑡) ≡ 1 in the main text.where 𝜇 0 is an arbitrary initial distribution. It is easy to verify that these dynamics define a Markov process that admits 𝜋 as its unique invariant measure. Perhaps less obvious is the fact that the Fokker-Plank equation associated with eq. ( 6), given by 𝜕 𝑡 𝜇 = ∇ • (∇ 𝑓 𝜇) + Δ𝜇 (and where 𝜇 𝑡 is the law of 𝑋 𝑡 ) is in fact a Wasserstein gradient flow for the relative entropy functional KL(𝜇||𝜋) [38] . Under this interpretation, one can quantify the convergence of Langevin dynamics to their invariant measure, i.e., its time to relaxation, by establishing a sharpness or Polyak-Lowacjevitz (PL)-type inequality. Indeed, by noticing that 𝑑 𝑑𝑡 KL(𝜇||𝜋) = -I(𝜇||𝜋), where I(𝜇||𝜋) = 𝔼 𝜇 [∥∇ log 𝜇 -∇ log 𝜋∥ 2 ] is the Fisher divergence, the PL-type inequality in this setting is given by the Logarithmic Sobolev Inequality (LSI): we say that a measure 𝜋 satisfies LSI(𝜌) if for any 𝜇 ∈ P (ℝ 𝑑 ) it holds KL(𝜇||𝜋) ≤ 1 2𝜌 I(𝜇||𝜋) . This functional inequality directly implies KL(𝜇 𝑡 ||𝜋) ≤ 𝑒 -2𝜌𝑡 KL(𝜇 0 ||𝜋). While for general 𝜋 it is typically hard to establish the LSI, there are two important sources of structure that lead to quantitative (i.e., 𝜌 = Ω 𝑑 (1)) bounds: when 𝜋 is a product measure 𝜋 = π⊗𝑑 (in which case 𝜋 satisfies LSI with the same constant as π), and when 𝜋 is strongly log-concave2, i.e., -∇ 2 log 𝜋(𝑥) ⪰ 𝛼𝐼 for all 𝑥, in which case the celebrated Bakry-Emery criterion [3] states that 𝜌 ≥ 𝛼.As shown in the main text, the proposed boosted posterior provably works for both low SNR and high SNR regimes. In this section, we formally argue that the importance sampling method is a nature baseline for posterior sampling with a large noise (low SNR regime) , but can suffer from exponential complexity when the SNR is high.In order to estimate an integral of a function 𝑓 with respect to the posterior measure 𝜈:𝐼 ( 𝑓 ) ∫ ℝ 𝑑 𝑓 (𝑥)d𝜈(𝑥),the idea of importance sampling is to independently sample 𝑋 1 , . . . , 𝑋 𝑛 from the prior 𝜋 and calculate𝐼 𝑛 ( 𝑓 ) 𝑛 𝑖=1 𝑓 (𝑋 𝑖 )𝜏(𝑋 𝑖 ) 𝑛 𝑖=1 𝜏(𝑋 𝑖 ), where 𝜏(𝑥) is the observation likelihood exp(-1 2 𝑥 ⊤ 𝑄𝑥 + 𝑥 ⊤ 𝑟). With the Denoising Oracle, we can sample from the prior efficiently. Intuitively, one can think if the posterior and prior are very similar, for example, when 𝜎 is large such that the ratio 𝜏 is close to 1, 𝐼 𝑛 ( 𝑓 ) computed from prior samples can efficiently approximate 𝐼 ( 𝑓 ). On the contrary, if 𝜎 is small, 𝜏(𝑥) can have very large variance and the importance sampling can be inefficient since many prior proposals have very small weights. The work [15, Theorem 1.2] proves that, in a fairly general setting, a sample of size approximately exp(KL(𝜈||𝜋)) is necessary and sufficient for accurate estimation by importance sampling, where KL(𝜈||𝜋) is the Kullback-Leibler divergence of 𝜋 from 𝜈:KL(𝜈||𝜋) = ∫ ℝ 𝑑 log d𝜈 d𝜋 d𝜈 = ∫ ℝ 𝑑 (- 1 2 𝑥 ⊤ 𝑄𝑥 + 𝑥 ⊤ 𝑏)d𝜈(𝑥).This result confirms one part of the intuition above: if 𝜎 is sufficiently small, then the magnitude of 𝑄 and 𝑟 will be sufficiently small, and so is (𝜈||𝜋) and the number of samples needed in the importance sampling. Next we show that for a fairly generic prior distribution 𝜋, when the SNR is large, KL(𝜈||𝜋) will be also large such that we need approximately O (𝑒 𝑑•SNR ) examples to implement importance sampling, which is unachievable.Without loss of generality, we assume the covariance of the prior 𝜋 is 𝐼 𝑑 .EQUATIONThen, when SNR > 𝐿 + 2, we haveEQUATIONand therefore the sample complexity of IS is exponential in dimension.Proof. We wish to lower bound KL(𝜈||𝜋) with tools of functional inequalities for the concentration of measure. By the celebrated work [51, 10] that the log-Sobolev inequality implies the Talagrand transport-entropy inequality, we haveEQUATION)Here 𝑊 (𝜈, 𝜋) denotes the Wassertain distance between 𝜈 and 𝜋:𝑊 (𝜈, 𝜋) = √︂ inf 𝛾 ∈Γ(𝜈, 𝜋 ) ∥𝑥 -𝑦∥ 2 d𝛾(𝑥, 𝑦) ,where Γ(𝜈, 𝜋) denotes the set of probability measures on ℝ 𝑑 × ℝ 𝑑 with marginals 𝜈 and 𝜋.First by Equation ( 63), we haveEQUATIONEQUATIONby Bakry-Emery criterion [3] . Furthermore, we have the lower bound for the Wasserstain distance [28] 𝑊 2 (𝜈, 𝜋) ≥ ∥mean(𝜈)mean(𝜋) ∥ 2 + trace(Cov(𝜈) + Cov(𝜋) -2(Cov(𝜋)EQUATION(68)EQUATION= trace(Diag(Cov(𝜈))EQUATIONwhere the second-to-last equality comes from the fact that the trace remains unchanged under orthogonal transformation. By (66) and Brascamp-Lieb Inequality (Theorem 16), we have Std(𝜈EQUATIONCollecting eqs. (65), (67) and (72), we obtain our final estimateEQUATION■ Theorem 16 (Brascamp-Lieb Inequality, [11] ). If 𝜋 is a strongly-log-concave measure on ℝ 𝑑 , i.e., of the form 𝜋 = 𝑒 -𝑓 with ∇ 2 𝑓 (𝑥) ⪰ 𝛼Id for all 𝑥 ∈ ℝ 𝑑 , then ∥Cov(𝜋) ∥ ≤ 𝛼 -1 .In the numerical implementation of boosted posterior, we typically encounter certain errors. Especially, we may have imperfect score subject to certain 𝐿 2 errors, and we may not be able to sample the boosted posterior 𝜈 𝑡 exactly. Suppose that instead of starting from 𝜈 𝑡 at 𝑡 and run the exact reverse SDE (5), we start from an approximate distribution 𝑞 𝑡 ≈ 𝜈 𝑡 and run the reverse SDE (5) with approximating score 𝑠 𝜃 (𝑥, 𝑡) ≈ ∇ log 𝜋 𝑡 (𝑥) where 𝜃 denote the parameters parametrizing the score. Denote the distribution of the final samples by 𝑞 0 , we have the following error estimate Proposition 17. Suppose 𝜈 𝑡 , 𝑞 𝑡 , ∇ log 𝜋 𝑡 , 𝑠 𝜃 (𝑥, 𝑡) has enough regularities such that the reverse SDEs exist, if the Novikov's condition 𝔼 exp(EQUATIONThe above proposition ensures that if both the initialization error and score error (over the posterior paths) are small, then the distribution of our final samples is close to the target posterior. The proof is provided in Appendix C.3. Note that we consider the reverse dynamics in continuous-time without time discretization error. There are various works [44, 45, 17, 8] analyzing the time discretization error and those techniques can be further incorporated into the above error estimate.The proof is similar to that in [59] . Here we provide the proof in our posterior sampling context for completeness.Proof. Consider the following two reverse dynamics needed for the error estimate: one is based on the exact score and starts from the exact boosted posteriorEQUATIONand another one is based on the approximate score and starts from the approximation to the boostedEQUATIONNote that these two dynamics are defined backwardly for 𝜏 ∈ [0, 𝑡] and we drop the superscript ← for notation simplicity. We denote the path measure of {𝑋 𝜏 } 𝜏 ∈ [0,𝑡 ] and { X𝜏 } 𝜏 ∈ [0,𝑡 ] by ν and q, respectively. Then 𝜈 and 𝑞 0 are the marginal distributions of the two path measures at 𝑡 = 0. By data processing inequality and chain rule of KL divergence, we haveEQUATIONGiven the Novikov's condition, we can apply the Girsanov theorem [50] to eq. ( 75)76 to compute the second term aboveEQUATION≤ -𝔼 ν log dq dν (80)EQUATIONWe have shown that posterior sampling of 𝜈 = T 𝑄 𝜋 can be reduced to sampling from 𝜈 𝑇 * by running the reverse SDE. While 𝜈 𝑇 * is easy to sample under the conditions presented in Section 5, these may not be verified in several situations of interest. In this context, a natural question is whether one could still leverage the tilted transport, at the expense of introducing sampling error. This is what we address in this section.Let 𝜆 1 , . . . 𝜆 𝑑 be the eigenvalues of 𝑄. Let us assume for simplicity that 𝑏 = 0 and all eigenvalues have multiplicity 1, so 𝜆 𝑖 > 𝜆 𝑖+1 . We define the events 𝑇 * 𝑗 for 𝑗 = 1 . . . 𝑑 given by EQUATIONEQUATION)For 𝑘 < 𝑘 * , assume first that one had sampling access to 𝜈 𝑘+1 . Running the reverse tilted transport for time 𝜂 𝑘 = 𝑇 * 𝑘+1 -𝑇 * 𝑘 would produce samples from a tilted measure ν𝑘 := T Q𝑘 𝜋 𝑇 * 𝑘 , where Q𝑘 has eigenvalues (𝜓(𝜂 𝑘 ), . . . , 𝜓(𝜂 𝑘 ), 𝜆 𝑘+1 (𝑇 * 𝑘 ), . . . , 𝜆 𝑑 (𝑇 * 𝑘 )), where we defined 𝜓(𝑡) := (𝑒 -2𝑡 -1) -1 as the inverse of 𝜆 ↦ → 1 2 log(1 + 𝜆 -1 ). It is thus a non-singular measure in ℝ 𝑑 , capturing the fact that the denoising oracle driving the reverse dynamics is isotropic, and thus oblivious to the existence of the singular support of 𝜈 𝑘 .We thus need a procedure to transform samples from ν𝑘 to samples of 𝜈 𝑘 . The easiest procedure is to simply marginalize the coordinates (𝑥 EQUATIONwhere we defined x 𝑘 = (𝑥 1 , . . . , 𝑥 𝑘 ) and x -𝑘 = (𝑥 𝑘+1 , . . . , 𝑥 𝑑 ).We can then iteratively run the tilted transport backwards, from 𝑘 = 𝑘 * -1 to 𝑘 = 0, as illustrated in Algorithm 2:Algorithm 2 Sampling Using Iterated Tilted Transport Run tilted transport starting at 𝑋 𝑘+1 for time 𝜂 𝑘 , resulting in X.Set 𝑋 𝑘 = (y 𝑘 ; X-𝑘 ). 5: end for 6: return 𝑋 0 By the data-processing inequality, the TV error will accumulate linearly at each step. Denoting ν the law of 𝑋 0 , we have TV( ν, 𝜈) ≤ ∑︁ 0<𝑘<𝑘 * TV( ν𝑘 , 𝜈 𝑘 ) .(87)This bound can be interpreted as the accumulation of errors arising from conditioning a measure by marginalizing over its first components. To the extent that 𝜓(𝜂 𝑘 ) is large, these variables are nearly deterministic, so one would expect that marginalization is a good approximation of conditioning. The outstanding question is to understand conditions when this error guarantee can be quantified.Inspired by [18] , a natural extension of this simple iterative procedure is to apply 'thermalization' towards the stationary measure 𝜈 𝑘 after line 4 of Algorithm 2 above, by running Langevin dynamics in Ω 𝑘 with score ∇ log 𝜈 𝑘 :EQUATION)The drift of this diffusion is available, since both 𝑄 𝑇 * 𝑘 and ∇ log 𝜋 𝑇 * 𝑘 are known, so is ∇ log 𝜈 𝑘 . Denote by ν𝑘 the law of 𝑋 𝑡 after time 𝑡 = 𝐵 𝑘 . While the time to relaxation of such Langevin dynamics is generally not quantitative (otherwise 𝑘 * ≤ 𝑘), even a short amount of thermalization is able to improve upon the previous method. Indeed, by the reverse transport inequality [ For a given dimension 𝑑 with 𝑑 mod 2 = 0, we consider prior data a mixture of 25 Gaussian distributions, the same as considered in [13] . The Gaussian distribution has mean (8𝑖, 8 𝑗, • • • , 8𝑖, 8 𝑗) ∈ ℝ 𝑑 for (𝑖, 𝑗) ∈ {-2, -1, 0, 1, 2} 2 and unit variance. Each (unnormalized) mixture weight is independently drawn according to a 𝜒 2 distribution.For the measurement model considered in Figure 3 , we generate 𝐴 in the following way. We first sample a 𝑑 × 𝑑 matrix with each entry sampled from the standard normal and compute its SVD to get 𝑈 and 𝑉 for 𝐴. The singular value is given by [1, • For all the experiments we run the boosted posterior from 𝑇 * -0.01 such that the ODE solution 𝑄, 𝑏 is well-defined. We use BlackJAX [12] to implement the No-U-turn sampler.Besides results reported in Figure 3 , we further test tilted transport when 𝑑 ′ < 𝑑. In this setting, 𝜆 min (𝑄 𝑡 ) remains zero but the signal corresponding to the non-zero eigenvalues still gets enhanced. Therefore, although it becomes more difficult for 𝜈 𝑇 * to be strongly log-concave, the tilted transport can still make the new posterior easier to sample even if it is not strongly log-concave yet. As shown in Table 1 , when 𝑑 ′ = 0.9𝑑, 10% percent eigenvalues of 𝑄 𝑡 are zero, our tilted transport technique still reduces the statistical distance of the posterior samples significantly. We also consider an even more challenging case where 𝑑 ′ = 1 such that the target posterior is still heavlily multimodal (as visualized in the 2D example in Figure 2 ). In this case, LMC suffers from the local maxima of the potential and thus cannot explore the multimodal distribution efficiently. We use the No-U-turn sampler [34] , a Hamilton Monte Carlo (HMC) method, as the baseline method, which can move among different modes more efficiently than Langevin. We find that the tilted transport technique can still boost the performance of HMC in this challenging setting. We also verify Theorem 5 by sampling from the boosted posterior directly from its analytical formula and running the reverse SDE, and the obtained samples approximate the target posterior well, as reported in Table 1 . We perform four inverse tasks on the Flickr-Faces-HQ Dataset (FFHQ) [39] to demonstrate the application of the tilted transport technique on imaging data as a proof of concept. To apply the proposed tilted transport technique to these problems, we still need to select a baseline method for sampling from the boosted posterior 𝜈 𝑇 * . In the case of ill-conditioned problems, sampling 𝜈 𝑇 * may still be challenging for principled algorithms like LMC, and we still need to rely on heuristic methods for imaging tasks. However, as noted in the introduction, most existing heuristic methods primarily facilitate conditional generation based on the measurement, lacking principled guarantees for posterior sampling. Consequently, we lack a principled interpretation for enhancing these methods with tilted transport. Nevertheless, we can still experiment with such methods as a proof of concept. We chose Diffusion Model Based Posterior Sampling (DMPS) [48] as the baseline method for the following reasons: The main assumption of DMPS in approximating the time-dependent conditional score is that the prior 𝜋 is uninformative (flat) with respect to 𝑋 𝑡 , such that 𝑝(𝑋 0 |𝑋 𝑡 ) ∝ 𝑝(𝑋 𝑡 |𝑋 0 ). This assumption only holds approximately in early phases of the forward diffusion, and hopefully a higher SNR provided by tilted transport makes the effect of this approximation error smaller.We conducted four tasks: (a) denoising; (b) inpainting with random masks from [53] ; (c) 4× super-resolution; and (d) deblurring using a Gaussian kernel. Our algorithm was implemented using the NVIDIA codebase [47] with 1000 diffusion steps for posterior sampling, and utilized the score function from a pretrained diffusion model [20] . Similar to our Gaussian mixture model experiments where we adjusted the timing for the boosted posterior to avoid the singularity of 𝑄 𝑡 , we shifted 6 -10 timesteps for setting the boosted posterior. Experiments show that the final performance is robust with respect to the number of shifted steps. Figure 4 showcases examples from the inpainting task, demonstrating how tilted transport enhances the baseline DMPS method. Additionally, we report various sample statistics including peak signal-to-noise ratio (PSNR), structural similarity index (SSIM), and Learned Perceptual Patch Similarity (LPIPS). However, it is important to note that while these statistics assess the quality of prior data generation, they may not accurately reflect the quality of posterior samples. , 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 authors 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 be possible for other researchers to have some path to reproducing or verifying the results. Justification: Code for Gaussian mixture is uploaded in a single zip file. Our results on imaging tasks in Appendix E.2 are mainly for a proof-of-concept.Guidelines:• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. (vi) Experimental Setting/Details Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results? Answer: [Yes] Justification: See the main text, Appendix E and code. Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary 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. (vii) Experiment Statistical Significance Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [Yes] Justification: In each experiment, we report percentiles or standard deviation. Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.38th Conference on Neural Information Processing Systems (NeurIPS 2024). 
evidence of computational hardness in the generic case: 
 We start our analysis of posterior sampling by discussing negative results for the general case. Recently, [30] established computational lower bounds for this task using cryptographic hardness assumptions. In this section, we complement these results by illustrating a correspondence with sampling problems on Ising models, leading to an arguably simpler conclusion.For this purpose, consider π = Unif ({±1} 𝑑 ) the uniform measure of the hypercube. Quadratic tilts of π define generic Ising models, a rich and intricate class of high-dimensional distributions. Since π is a product measure, its associated denoising oracle becomes a separable function that can be computed in closed-form: Given a symmetric matrix 𝑄 ∈ ℝ 𝑑×𝑑 , an Ising model is given by the tilt T 𝑄 π ∈ P ({±1} 𝑑 ). In our setting, we can thus view such models as the posterior distribution of a linear inverse problem associated with the uniform prior π. Efficiently sampling from Ising models is a fundamental question at the interface of statistical physics and high-dimensional probability, and several works provide evidence of computational hardness under a variety of settings.Notably, by treating 𝑄 as the adjacency matrix of a regular graph, [27] establishes that sampling from 𝜈 is impossible for 𝜆 max (𝑄) -𝜆 min (𝑄) ≥ 2 + 𝜀, for any 𝜀 > 0, unless NP = RP. In other words, for poorly conditioned tilt 𝑄 (in the sense that there is a large gap between the smallest and largest eigenvalue), there is no efficient posterior sampling algorithm, even with the knowledge of the prior denoising oracle. The threshold can even be reduced to 1 + 𝜀 by using a weaker notion of computational hardness [42] , given by the low-degree polynomial method [4, 43] . Remarkably, this threshold agrees with the current best-known algorithmic results for sampling generic Ising models with Glauber dynamics [25, 1] . Finally, we also mention that when 𝑄 is a random Gaussian symmetric matrix, the associated so-called Sherrington-Kirkpatrick (SK) model, has been analyzed with dedicated algorithms. In this setting, it is also known [24] that 'stable' sampling algorithms fail to sample from the SK model as soon as 𝜆 max (𝑄) -𝜆 min (𝑄) > 1. In summary, we have:Theorem 3 (Computational Hardness of Sampling Ising Models, [42, 27] ). There exist no generalpurpose, efficient posterior sampling algorithms, for 𝑄 sufficiently ill-conditioned, even under the knowledge of the prior denoising oracle.One could wonder whether this computational hardness comes from the discrete nature of the hypercube. It is not hard to observe that this is not the case: the following proposition, proved in Appendix A, shows a simple reduction from a model where the prior π is replaced by a smooth mixture of Gaussians 𝜋 centered at the corners of the hypercube, with variance 𝛿.2or a suitable perturbation of it via the Hooley-Strook perturbation principle [35] Proposition 4 (Hardness extends to smooth priors). Assume a posterior sampler exists for the smooth prior with TV error 𝜖 and 𝛿 = 𝑜(𝑑 -1/2 ). Then there exists a sampler for the associated Ising model with TV error 1.1𝜖.In conclusion, one cannot hope for a generic method that leverages the prior denoising oracle to perform efficient posterior sampling, as soon as 𝐴 is mildly ill-conditioned. Thus, in order to perform provable posterior sampling, one needs to either (i) constraint the measurements, or (ii) exploit structural properties of the prior measure. In the following, we focus on (i), namely providing guarantees for well-conditioned 𝐴 that leverage the OU semigroup for generic prior distributions. 
posterior sampling via tilted transport: 
 We now present a simple method that reduces the original posterior sampling problem to another posterior sampling problem with more benign geometry, by leveraging the shared quadratic structure of the posterior tilt and the OU semigroup. The power of the denoising oracle to perform sampling of the prior 𝜋 comes from its ability to run the transport equation ( 3) in either direction, and leveraging the fact that sampling from 𝜋 𝑇 is easy. To transfer this power to posterior sampling, we can thus attempt to replicate this scheme: can we implement a transport between the posterior 𝜈 and a terminal measure 𝜈 𝑇 that is easy to sample, that only relies on the pre-trained prior DO 𝜋 ?A Motivating Example. Consider first the denoising setting: 𝑦 = 𝑥 + 𝜎𝑤. According to the forward process, we have𝑝(𝑋 𝑠 |𝑋 0 ) 𝑑 = N (𝑒 -𝑠 𝑋 0 , (1 -𝑒 -2𝑠 )𝐼 𝑑 ). Introduce 𝑇 * > 0 and define ỹ = 𝑒 -𝑇 * 𝑦 = 𝑒 -𝑇 * 𝑥 + 𝑒 -𝑇 * 𝜎𝑤 such that 𝑝( ỹ|𝑥) 𝑑 = N (𝑒 -𝑇 * 𝑥, 𝑒 -2𝑇 * 𝜎 2 𝐼 𝑑 ). We match the variance by letting 𝑒 -2𝑇 * 𝜎 2 = 1 -𝑒 -2𝑇 * , i.e., 𝑇 * = 1 2 log(1 + 𝜎 2 ), then we have 𝑝( ỹ|𝑥) = 𝑝(𝑋 𝑇 * |𝑋 0 ), which gives (𝑥, ỹ) 𝑑 = (𝑋 0 , 𝑋 𝑇 * ). Therefore, to perform the posterior sampling 𝑝(𝑥| ỹ), we only need to do the sampling 𝑝(𝑋 0 |𝑋 𝑇 * ), which can be achieved through the reverse SDE. Specifically, let 𝑋 𝑇 * = 𝑒 -𝑇 * 𝑦 and run the reverse SDE (5) from 𝑇 * to 0, then 𝑋 0 will be the desired posterior.Hamilton-Jacobi Equation and Quadratic Tilts. If 𝜋 𝑡 solves the Fokker-Plank eq. ( 2), then one can verify that the time-varying potentials 𝑓 𝑡 := log 𝜋 𝑡 solve the viscous Hamilton-Jacobi PDE (HJE)EQUATIONNow, the posterior 𝜈 = T 𝑄,𝑏 𝜋 creates an additional quadratic term in the potential log 𝜈 = 𝑓 -1 2 𝑥 ⊤ 𝑄𝑥 + 𝑥 • 𝑏.One could naively hope that this additive quadratic term would still define a solution of the HJE with the tilted initial condition f0 = log 𝜈 -or equivalently that the measure T 𝑄,𝑏 𝜋 𝑡 solves the transport equation (3) . Unfortunately, due to the nonlinearity in (8) brought by the terms ∥∇ 𝑓 𝑡 ∥ 2 , this is not the case. However, as we shall see now, this is not far from being true: one just needs to consider time-varying quadratic tilts in order to satisfy the HJE.We consider then a one-parameter family of distributions 𝜈 𝑡 of the form 𝜈 𝑡 = T 𝑄 𝑡 ,𝑏 𝑡 𝜋 𝑡 , with 𝑄 0 = 𝑄 and 𝑏 0 = 𝑏. As it turns out, one can ensure that log 𝜈 𝑡 solves the HJE associated with the reverse process by asking that 𝑄 𝑡 , 𝑏 𝑡 satisfy the first-order ODEEQUATIONTheorem 5 (Tilted Transport). Assume 𝑡 < 𝑇 * such that the ODE (9) is well-defined on [0, 𝑡]. By initializing 𝑋 𝑡 ∼ 𝜈 𝑡 and run the reverse SDE (5) from 𝑡 to 0, we have 𝑋 𝑠 ∼ 𝜈 𝑠 for 𝑠 ∈ [0, 𝑡], specifically, 𝑋 0 gives the desired posterior.Solution to eq. ( 9). Without loss of generality, we assume 𝑑 ′ ≤ 𝑑, and the observation operator 𝐴 ∈ ℝ 𝑑 ′ ×𝑑 has a general singular value decomposition form 𝐴 = 𝑈Σ𝑉 ⊤ with non-zero singular values𝜆 1 ≥ 𝜆 2 ≥ • • • ≥ 𝜆 𝑑 ′ > 0.By diagonalizing 𝑄 and solving the scalar ODE 𝑞 𝑡 = 2(1 + 𝑞 𝑡 )𝑞 𝑡 for diagonal entries, we have 𝑄 𝑡 = 𝑉diag𝑒 2𝑡 1+𝜎 2 /𝜆 2 1 -𝑒 2𝑡 , • • • , 𝑒 2𝑡 1+𝜎 2 /𝜆 2 𝑑 ′ -𝑒 2𝑡 , 0, • • • , 0 𝑉 ⊤ ,where the solution is defined up to the blowup time 𝑇 * := 1 2 log(1+ 𝜎 2 /𝜆 2 1 ) = 1 2 log(1 + 𝜆 max (𝑄) -1 ). 𝑏 𝑡 can be further solved from the solution 𝑄 𝑡 ; see Appendix B.2 for more details.With the explicit solution of 𝑄 𝑡 , 𝑏 𝑡 , we can interpret the term exp(- 1 2 𝑥 ⊤ 𝑄 𝑡 𝑥 + 𝑥 ⊤ 𝑏 𝑡 ) as the likelihood of the inverse problem with respect to the new prior distribution 𝜋 𝑡 and the corresponding operator. Based on this observation and Theorem 5, we have the following corollary, transforming the original posterior sampling problem to a new posterior sampling problem exactly. We remark that when 𝐴 is identity, the corollary recovers the analysis we have in the motivating example; see Appendix B.2 for the proof and more discussions. Corollary 6. Fix 𝑡 < 𝑇 * . Sampling from the original posterior is equivalent to a two-step process: first, sample from a new posterior 𝑋 𝑡 ∼ 𝜈 𝑡 , and then run the reverse SDE (5) from time 𝑡 to 0. 
quantitative conditions for provable sampling: 
 Now we show that the new posterior sampling problem described above is provably easier to sample than the original posterior sampling problem from two aspects. On the one hand, the (negative) eigenvalues of the quadratic tilt -1 2 𝑥 ⊤ 𝑄 𝑡 𝑥 + 𝑥 ⊤ 𝑏 𝑡 become more negative, essentially meaning that the SNR of the new observation model becomes larger. To be more specific, as 𝑡 → 𝑇 * ,𝜆 min (𝑄 𝑡 ) → 1+𝜆 max (𝑄) -1𝜆 min (𝑄) -1 -𝜆 max (𝑄) -1 > 𝜆 min (𝑄). On the other hand, the new prior distribution 𝜋 𝑇 * becomes closer to a single-mode Gaussian (recall that KL(𝜋 𝑡 ||𝛾 𝑑 ) = 𝑂 (𝑒 -𝑡 )), which is also easier to sample. Combining these two arguments, we expect that, as 𝑡 increases, 𝜈 𝑡 becomes easier to sample due to easier prior and easier likelihood:𝜈 𝑡 (𝑥) ∝ 𝜋 𝑡 (𝑥) easier prior exp - 1 2 𝑥 ⊤ 𝑄 𝑡 𝑥 + 𝑥 ⊤ 𝑏 𝑡 .easier likelihoodLet us now quantify the above intuition.Sufficient Conditions for Strong Log-Concavity of 𝜈 𝑇 * . We start by giving a simple sufficient condition that ensures that 𝜈 𝑇 * is strongly log-concave. As discussed earlier, this ensures fast relaxation of the Langevin dynamics, enabling efficient sampling from 𝜈 𝑇 * -and therefore of 𝜈 as per Corollary 6. For that purpose, given the prior 𝜋 ∈ P (ℝ 𝑑 ) and 𝑡 ≥ 0, we defineEQUATIONwhere the covariance is given by Cov[𝜇] = 𝔼 𝑥∼𝜇 [𝑥𝑥 ⊤ ] -(𝔼 𝑥∼𝜇 [𝑥]) (𝔼 𝑥∼𝜇 [𝑥]) ⊤ .𝜒 𝑡 (𝜋) thus measures the largest 'spread' of any tilted measure of the form T 𝑡 ,𝑥 𝜋. Equipped with this definition, we have the following sufficient condition to ensure that 𝜈 𝑇 * is strongly log-concave:EQUATION)The proof is in Appendix C. It relates two parameters of the measurement process, the condition number of 𝐴 and the signal-to-noise ratio in terms of ∥𝑄∥, with a geometric property of the prior, the spread function 𝜒 𝑡 (𝜋). While this function is not immediately transparent, the following examples illuminate its behavior in reprsentative high-dimensional settings.Example 8 (Behavior of 𝜒 𝑡 (𝜋)). We have the following examples(i) Gaussian measure: 𝜒 𝑡 (𝛾 𝑑 ) = 1 1+𝑡 . (ii) Compactly Supported Gaussian Mixture: If 𝜇 is compactly-supported in a ball of radius 𝑅 and 𝛿 ≥ 0, then 𝜒 𝑡 (𝜇 ★ 𝛾 𝛿 ) ≤ 𝑅 1+ 𝛿𝑡 2 + 𝛿 1+ 𝛿𝑡 . (iii) Tensorization: If 𝜇 = 𝜇 1 ⊗ 𝜇 2 • • • ⊗ 𝜇 𝑑 , then 𝜒 𝑡 (𝜇) = max 𝑖 𝜒 𝑡 (𝜇 𝑖 ).(iv) Uniform measure on hypercube: If 𝜋 is uniform on the hypercube H 𝑑 , then 𝜒 𝑡 (𝜋) = 1.Ising Models. As a direct consequence of Proposition 7 and Example 8 (iv), we establish a sampling guarantee for Ising models: Corollary 9 (Tilted Transport for the Ising Model). Let 𝜋 be the uniform measure on the hypercube, and 𝑄 such that 𝜆 max (𝑄) -𝜆 min (𝑄) < 1. Then 𝜈 𝑇 * is strongly log-concave, and therefore 𝜈 = T 𝑄 𝜋 can be sampled efficiently (in continuous-time).This result thus establishes that Ising models admit an efficient continuous-time procedure for sampling provided their spectrum satisfies 𝜆 max (𝑄) -𝜆 min (𝑄) < 1, thus precisely matching the threshold of [25, 1] achieved by Glauber dynamics, as well as the low-degree prediction from [42] . We remark though that our procedure is not (yet) algorithmic; a careful analysis of the discrete-time complexity and the approximation rates is beyond the current scope, but our next endeavor. If one specializes the previous result to the SK model, the equivalent inverse temperature that guarantees sampling is 𝛽 * = 1/4, which remains below 𝛽 = 1, the threshold of the hard phase. For this threshold, dedicated AMP-based sampling succeeds [24, 14] . We also remark that, in itself, it should not come as a surprise that 𝜈 may be sampled under these conditions, since [5] already established an LSI on 𝜈 directly, using an entropy decomposition along the so-called Polchinski renormalization group [6] that refines our Bakry-Emery criterion. In this context, it would be interesting to explore whether this refined criterion could be applied to 𝜈 𝑇 * to improve upon Proposition 7 under appropriate conditions. Gaussian Mixtures. By applying Proposition 7 to Example 8 (ii), we directly obtain the following guarantee for generic comptactly supported Gaussian mixtures: Corollary 10 (Tilted Transport for Gaussian Mixtures). If 𝜋 = 𝜇 ★ 𝛾 𝛿 and diam(supp(𝜇)) ≤ 𝑅, then 𝜈 𝑇 * is strongly log-concave ifEQUATION)It also holds when 𝛿 = 0 and the prior 𝜋 is any distribution with a bounded support radius 𝑅.Figure 2 displays several contours of the condition in eq. ( 12) as a function of SNR and 𝜅( 𝐴). Each 𝑈-shaped contour is determined by a combination of 𝛿 and 𝑅, which uniquely characterizes the prior. For all points ((SNR), 𝜅( 𝐴)) outside of a contour, representing a specific inverse problem, 𝜈 𝑇 * is strongly log-concave and thus easy to sample. Given an observation model where both SNR and 𝜅( 𝐴) are fixed, it is straightforward to see that the condition in eq. ( 12) is more readily satisfied as 𝛿 increases and 𝑅 decreases. Figure 2 also confirms this result since as 𝛿 increases or 𝑅 decreases, the 𝑈-shaped contour shrinks and the region of easy to sample expands. Now we discuss the implications in the reverse scenario where the prior is fixed and the observation model is adjusted. If we look at Figure 2 horizontally, we know that given a prior and 𝜅( 𝐴), the target posterior can be reliably sampled if the SNR is either sufficiently low or high, with the region of mid-SNR being challenging. The closer 𝜅( 𝐴) is to 1, the smaller this challenging region is. When the problem is denoising such that 𝜅( 𝐴) = 1, the challenging region vanishes, and sampling the posterior is straightforward using the denoising oracle, as previously explained. Comparisons. 1. (with Langevin dynamics) As introduced above, Langevin dynamics and its discretized version, Langevin Monte Carlo (LMC) [52, 46] serve as ideal baselines for efficient posterior sampling in high SNR regimes where the posterior becomes strongly log-concave. Proposition 7 demonstrates that our tilted transport technique enables provably efficient sampling from a broader range of prior distributions compared to traditional Langevin dynamics without a denoising oracle. Particularly, in low SNR regimes where conventional Langevin dynamics struggle with severe non-log-concavity and slow mixing times, tilted transport can transform the sampling challenge into a tractable problem for log-concave distributions.2. (with Importance Sampling) In the low SNR regime with a well-conditioned 𝐴, the posterior measure can be viewed as a small perturbation of the prior. As such, a natural baseline for posterior sampling is importance sampling using the prior as a proposal -for which samples can be efficiently obtained thanks to the denoising oracle and the variance of sample weights is small. However, as detailed in Appendix C.2, the sampling complexity is exponential with the SNR when the SNR is sufficiently large, assuring the failure of the importance sampling on this extreme.In the numerical implementation of the boosted posterior, we often encounter specific errors. Appendix C.3 provides a stability analysis of the two-step process outlined in Corollary 6, focusing on initialization error and score error, and demonstrates that the quality of the final samples is robust with respect to these errors. 
numerical experiments: 
 Our theory above demonstrates that 𝜈 𝑇 * is provably easier to sample than the original posterior 𝜈. Thus, given a baseline sampling algorithm Alg, we can first sample from the boosted posterior and then apply the denoising oracle to obtain the final sample, rather than directly sampling from 𝜈 using Alg. Algorithm 8 provides a complete description of this approach using tilted transport. In this instance, we use Euler discretization with equal time steps to transport samples from from T 𝑄 T ,𝑏 T 𝜋 T to T 𝑄,𝑏 𝜋, though alternative time integrators and grids can also be applied. We now validate our theoretical results by applying Algorithm 8 to the Gaussian mixture model in high dimensions, using LMC as the baseline algorithm. Same to the models considered in [13] , the prior distribution is a mixture of 25 components with known means and variances (see Figure 1 for a 2D visualization and Appendix E for detailed settings). We examine three cases where 𝑑 = 20, 40, and 80. In each scenario, we set 𝑑 ′ = 𝑑, fix 𝜅 = 20, and vary the SNR from 10 -5 to 10 -1 . We use the Sliced Wasserstein distance as a principled error metric, computed from samples obtained by our algorithms and samples directly from the analytically computed posterior Gaussian mixture. Figure 3 illustrates the comparison between LMC and LMC boosted by tilted transport. As analyzed earlier, LMC is effective when the SNR is high enough to render the target posterior strongly log-concave, but its error quickly increases as the SNR decreases. In contrast, the tilted transport enhances LMC to perform well in both low and high SNR regimes with small sampling errors. Its performance is weaker in the mid-SNR regime compared to the extremes, as predicted by Corollary 10. However, the tilted transport still improves upon LMC in this challenging regime by boosting effective SNR and simplifying the prior.We further test tilted transport when 𝑑 ′ < 𝑑, in which 𝜆 min (𝑄 𝑡 ) remains zero but the signal corresponding to the non-zero eigenvalues still gets enhanced. Therefore, although it becomes more difficult for 𝜈 𝑇 * to be strongly log-concave, the tilted transport can still make the new posterior easier to sample even if it is not strongly log-concave yet. Detailed results are reported in Appendix E.1. 
discussion and future work: 
 In this paper, we theoretically investigate posterior sampling using powerful priors provided by denoising oracles. We demonstrate that efficient posterior sampling can be challenging even with a perfect denoising oracle for the prior. To achieve provable posterior sampling, one must either constrain the measurements or leverage the structural properties of the prior. We focus on the former, showing that well-conditioned measurements enable the proposed tilted transport technique to simplify the task significantly, providing a clear, verifiable condition for efficient sampling, as demonstrated on the Ising model. Several questions remain open: Can this approach provably handle poorly-conditioned measurements, such as inpainting? Can it be extended from linear to nonlinear inverse problems? We show in Appendix D how to extend the tilted transport beyond the condition of Proposition 7 via 'iterated tilts', at the expense of introducing approximation errors. On the theory side, the key object underlying the success of the tilted transport is the spread 𝜒 𝑡 (𝜋); in particular, understanding when one can remove dimension dependence is an interesting question. We also aim to systematically evaluate the empirical performance of tilted transport in imaging and scientific computing. Appendix E.2 provides a proof-of-concept for various imaging tasks. We suspect that tilted transport could even improve existing posterior point estimate methods by boosting SNR and enabling proper uncertainty quantification through the reverse process.Let 𝛿 > 0 and π be the uniform measure in the 𝑑-dimensional hypercube. Consider a Gaussian mixture prior 𝜋 defined as 𝜋 = π ★ 𝛾 𝛿 .Since both π and 𝛾 𝛿 are product measures, it follows that 𝜋 is also a product measure, and therefore its denoising oracle DO 𝜋 is explicitly given by DO 𝜋 (𝑦, 𝑡) 𝑖 = 𝜓(𝑦 𝑖 , 𝑡), withEQUATION)EQUATIONObserve that 𝑞 𝑣,𝑡 is the density of a Gaussian mixture in ℝ of the form 𝛼N (𝑏 -, 𝜎) + (1 -𝛼)N (𝑏 + , 𝜎), with parametersEQUATIONEQUATION)EQUATION)and thus 𝜓(𝑣, 𝑡) = 𝛼𝑏 -+ (1 -𝛼)𝑏 + .Let us now denote by 𝜇 𝑄 the target Ising model, supported in the 𝑑-dimensional hypercube, and define the approximation 𝜇 𝜎 𝑄 := T 𝑄 𝜋. Suppose that there is an algorithm A that leverages the denoising oracle of 𝜋 that can efficiently sample from 𝜇 𝜎 𝑄 : its law μ satisfies TV(𝜇 𝜎 𝑄 , μ) ≤ 𝜖 with runtime polynomial in 𝑑 and log(𝜖 -1 ).Let now 𝑅(𝑥) = sign(𝑥), and consider the sampler 𝑅 • A, which is now supported in the hypercube. By the triangle and data-processing inequalities, we directly haveEQUATION≤ TV( μ, 𝜇 𝛿 𝑄 ) + TV(𝑅 # 𝜇 𝛿 𝑄 , 𝜇 𝑄 )EQUATIONIt remains to bound the second term in the RHS. We have to compare two measures in the hypercube.For 𝜎 ∈ H 𝑑 := {±1} 𝑑 , they are given respectively byEQUATIONEQUATION)Applying the Laplace approximation into each integral we obtain, as 𝛿 → 0,EQUATIONwhere 𝜎 ⊕ 𝑧 is the XOR, and |𝜎 -𝑧| is the Hamming distance. We thus have, for any 𝜎 ∈ H 𝑑 ,EQUATIONEQUATION)It follows that we can write 𝑅 # 𝜇 𝛿 𝑄 (𝜎) as𝑅 # 𝜇 𝛿 𝑄 (𝜎) = 𝐶 (𝑒 -1 2 𝜎 ⊤ 𝑄 𝜎 + 𝜂 𝜎 ) ,with a relative errorEQUATIONIt follows thatEQUATIONand thus if 𝛿 ≪ 1√ 𝑑, we have a negligible TV approximation.Proof. We denote the time-dependent score function ∇ log 𝜋 𝑡 (𝑥) by 𝑠 𝑡 (𝑥). As derived in Section 2, if we initialize 𝑋 𝜏 according to density 𝜌 𝜏 and run the reverse SDE eq. ( 5), the density of 𝑋 𝑡 for 𝑡 ≤ 𝜏, denoted by 𝜌 𝑡 , satisfies the backward PDE:EQUATIONWe need to verify that 𝜈 𝑡 satisfies the above PDE.Note that a general positive function 𝜌 𝑡 satisfies this PDE is equivalent to that ℎ 𝑡 = log 𝜌 𝑡 satisfies the following Hamilton-Jacobi PDEEQUATIONBy definition, we know ℎ 𝑡 = log 𝜋 𝑡 satisfies the above PDE, and we need to prove ℎ 𝑡 = log 𝜈 𝑡 = log 𝜋 𝑡 -1 2 𝑥 ⊤ 𝑄 𝑡 𝑥 + 𝑥 ⊤ 𝑏 𝑡 + 𝐹 (𝑡) satisfies this PDE as well. Here 𝐹 (𝑡) denotes the normalizing constant. Taking the difference between two equations, we needEQUATIONwhich can be satisfied by the ODE dynamics (9) . ■Sanity Check for the Motivating Example. In the denoising setting, we have 𝑄 0 = 1 𝜎 2 𝐼 𝑑 , 𝑏 0 = 1 𝜎 2 𝑦. The ODE (9) has the explicit solution𝑄 𝑡 = 𝑒 2𝑡 1 + 𝜎 2 -𝑒 2𝑡 𝐼 𝑑 .Note that this solution has a finite blow-up time when 1 + 𝜎 2 -𝑒 2𝑡 → 0 + , which is exactly at 𝑇 * = 1 2 log(1 + 𝜎 2 ), as derived in the main text by matching the SNR. As 𝑡 → 𝑇 * , 𝑄 𝑡 → ∞𝐼 𝑑 ,𝜈 𝑡 = exp 𝑓 𝑡 (𝑥) - 1 2 𝑥 ⊤ 𝑄 𝑡 𝑥 + 𝑥 ⊤ 𝑏 𝑡 + 𝐹 (𝑡) → N (𝑄 -1 𝑡 𝑏 𝑡 , 𝑄 -1 𝑡 ).To see the limit of 𝑄 -1 𝑡 𝑏 𝑡 , we only need to consider the ODE for each component since 𝑄 is diagonal. So we view the above ODE as scalar ODEs. Considering the dynamics of d d𝑡EQUATIONgives𝑄 -1 𝑡 𝑏 𝑡 = 𝑒 -𝑡 𝑄 -1 0 𝑏 0 . Therefore lim 𝑡→(𝑇 * ) -𝑄 -1 𝑡 𝑏 𝑡 = 𝑒 -𝑇 * 𝑄 -1 0 𝑏 0 = 𝑒 -𝑇 * 𝑦,which matches the initial condition derived in the main text for the denoising case. Furthermore, we can explicitly verify that the intermediate distribution of 𝑋 𝑡 by running the reverse SDE from 𝜈 * 𝑇 is 𝜈 𝑡 :EQUATIONEQUATIONTo match the form of 𝜈 𝑡 , we have𝑄 𝑡 = 1 𝑒 2(𝑇 * -𝑡 ) -1 = 𝑒 2𝑡1+𝜎 2 -𝑒 2𝑡 , 𝑄 -1 𝑡 𝑏 𝑡 = 𝑒 -𝑡 𝑦, which are the solutions of the ODE (9) . Solution to eq. ( 9). We recall that the observation operator 𝐴 ∈ ℝ 𝑑 ′ ×𝑑 has a general singular value decomposition form 𝐴 = 𝑈Σ𝑉 ⊤ with non-zero singular values𝜆 1 ≥ 𝜆 2 ≥ • • • ≥ 𝜆 𝑑 ′ > 0. By definition, we have 𝑄 0 = 𝑉diag(𝜆 2 1 /𝜎 2 , • • • , 𝜆 2 𝑑 ′ /𝜎 2 , 0, • • • , 0)𝑉 ⊤ .By left multiplying 𝑉 ⊤ and right multiplying 𝑉 to the first ODE in we can diagonalize it to scalar equations 𝑞 𝑡 = 2(1 + 𝑞 𝑡 )𝑞 𝑡 for each diagonal entry. Solving this ODE givesEQUATIONHere we explain how to solve 𝑏 𝑡 from eq. ( 9). We denote𝑉 = [𝑣 1 , • • • , 𝑣 𝑑 ],in which 𝑣 𝑖 are eigenvectors of 𝑄 (and 𝑄 𝑡 as well), and denote the eigenvalues of 𝑄 𝑡 (0 ≤ 𝑡 < 𝑇 * ) byEQUATIONBy definition, we know λ𝑖 satisfies the ODE λ = 2(1 + λ) λ.We rewrite the solution 𝑏 𝑡 = 𝑑 𝑖 𝜉 𝑖 (𝑡)𝑣 𝑖 and aim to solve 𝜉 𝑖 (𝑡). From 𝑏 0 = 𝑉 ( 1 𝜎 2 Σ ⊤ 𝑈 ⊤ 𝑦), we have the initial conditionEQUATIONTaking the inner product between 𝑣 𝑖 and both sides of the ODE 𝑟 𝑡 = (𝐼 + 2𝑄 𝑡 )𝑏 𝑡 , we have𝜉 𝑖 (𝑡) = (1 + 2 λ𝑖 (𝑡))𝜉 𝑖 (𝑡).Therefore, for 𝑑 ′ + 1 ≤ 𝑖 ≤ 𝑑, 𝜉 𝑖 (𝑡) = 0. For 1 ≤ 𝑖 ≤ 𝑑 ′ , same to the derivation in eq. ( 32), we have d d𝑡EQUATIONEQUATIONEQUATION)Proof of Corollary 6. Given Theorem 5, we only need to prove that sampling from𝜈 𝑡 = T 𝑄 𝑡 ,𝑏 𝑡 𝜋 𝑡 ∝ 𝜋 𝑡 (𝑥) exp - 1 2 𝑥 ⊤ 𝑄 𝑡 𝑥 + 𝑥 ⊤ 𝑏 𝑡is equivalent to sampling from a new posterior. Taking 𝜋 𝑡 as the corresponding prior, we only need to show that the factor exp -1 2 𝑥 ⊤ 𝑄 𝑡 𝑥 + 𝑥 ⊤ 𝑏 𝑡 is the likelihood of certain observation model in the form of ỹ = 𝐴 𝑡 𝑥 + 𝑤 with 𝑤 ∼ 𝛾 𝑑 . To end, we need to ensure exp -1 2 𝑥 ⊤ 𝑄 𝑡 𝑥 + 𝑥 ⊤ 𝑏 𝑡 ∝ exp(- 1 2 ∥ 𝐴 𝑡 𝑥 -ỹ∥ 2 )Choosing 𝐴 𝑡 in the standard SVD form 𝐴 𝑡 = Σ 𝑡 𝑉 ⊤ where the singular values of 𝐴 𝑡 (the diagonal entries of Σ 𝑡 ) are𝑒 𝑡 (1+𝜎 2 /𝜆 2 𝑖 -𝑒 2𝑡 ) 1/2 for 1 ≤ 𝑖 ≤ 𝑑 ′ ,the quadratic term is matched. Matching the first order term requires 𝑏 𝑡 = 𝐴 ⊤ ỹ = 𝑉 Σ ⊤ 𝑡 ỹ. Further matching the coefficients in the basis of 𝑉 requires that(Σ ⊤ 𝑡 ỹ) 𝑖 = 𝜉 𝑖 (𝑡) = 𝑒 𝑡 𝜆 𝑖 (1 + 𝜎 2 /𝜆 2 𝑖 -𝑒 2𝑡 ) (𝑈 ⊤ 𝑦) 𝑖 , 1 ≤ 𝑖 ≤ 𝑑 ′ .It is easy to verify that ỹ 3) to generate samples with the probability flow ODE [58] backward in time= Σ ′ 𝑡 𝑈 ⊤ 𝑦 with Σ ′ 𝑡 = diag 1 ( 𝜎 2 +𝜆 2 1 (1-𝑒 2𝑡 ) ) 1/2 , . . . , 1 ( 𝜎 2 +𝜆 2 𝑑 ′ (1-𝑒 2𝑡 ) )EQUATIONfrom 𝑋 ← 𝑇 ∼ 𝛾 𝑑 . Combining the fact that 𝜈 𝑡 satisfies the PDE (5) andΔ𝜈 𝑡 = ∇•(∇𝜈 𝑡 ) = ∇•(𝑠 𝑡 -𝑄 𝑡 𝑥+𝑏 𝑡 ), we have that 𝜈 𝑡 also satisfies the transport equation 𝜕 𝑡 𝑝 𝑡 = ∇•((𝑠 𝑡 +(𝐼+𝑄 𝑡 )𝑥-𝑏 𝑡 ) 𝑝 𝑡 ). Therefore, for any 𝑡 < 𝑇 * , by initializing 𝑋 𝑡 ∼ 𝜈 𝑡 and run the reverse ODE d𝑋← 𝑡 = (-(𝐼 +𝑄 𝑡 ) 𝑋 ← 𝑡 -∇ log 𝜋 𝑡 (𝑋 ← 𝑡 ) + 𝑏 𝑡 )d𝑡 then 𝑋 ←0 also gives the desired posterior. However, we note that unlike the reverse SDE case, the corresponding transport PDE and the vector field in the reverse ODE case are different from those used in the prior data generation. As discussed below, both 𝑄 𝑡 and 𝑏 𝑡 are singular near 𝑇 * . Therefore running the reverse SDE might be preferrable for better numerical stability.Proof of Proposition 7. By definition, we need to showEQUATION)From the argument in the main text, we know 𝑇 * = 1 2 log(1 + 𝜆 max (𝑄) -1 ), and thusEQUATION)Let 𝑚 = 𝜆 min (𝑄). Therefore, we can guarantee that 𝜈 𝑇 * is strongly log-concave ifEQUATIONor equivalentlyEQUATION)■ Lemma 12 (Hessian of Gaussian Mixture Potential). Let 𝜋 = 𝜇 ★ 𝛾 Σ be a Gaussian mixture. Then∇ 2 log 𝜋(𝑥) = Σ -1 Cov T Σ -1 ,Σ -1 𝑥 𝜇 Σ -1 -𝐼 .Proof. Let us first compute the score ∇ log 𝜋. By definition we haveEQUATIONand thusEQUATIONwhere we defined Cov[𝜇] = 𝔼 𝑥∼𝜇 [𝑥𝑥 ⊤ ] -(𝔼 𝑥∼𝜇 𝑥) (𝔼 𝑥∼𝜇 𝑥) ⊤ . ■ Corollary 13.In particular, we haveEQUATION)Proof. From Lemma 12 and𝜋 𝑡 = C 1-𝑒 -2𝑡 (D 𝑒 𝑡 𝜋) = D 𝑒 𝑡 𝜋 ★ 𝛾 1-𝑒 -2𝑡, we directly haveEQUATION)Now, using the commutation property between the isotropic tilt and the dilationEQUATIONand therefore supEQUATION)Using that 𝑒 2𝑇 * -1 = ∥𝑄∥ -1 , we thus obtainEQUATION■ Lemma 14 (Isotropic Tilt of a Gaussian Mixture). If 𝜋 = 𝜇 ★ 𝛾 𝛿 , thenEQUATION)where 𝜎 -2 = 𝛿 -1 + 𝑡 andEQUATION)Proof. By definition, we haveT 𝑡 𝐼,𝑧 𝜋 ∝ ∫ d𝜇(𝑦)𝑒 -1 2 𝑡 ∥ 𝑥 ∥ 2 +𝑥•𝑧-1 2 𝛿 -1 ∥ 𝑥-𝑦 ∥ 2.By expressingEQUATIONEQUATION)EQUATION)which gives the desired result after performing the affine change of variables from 𝑦 to ỹ. ■Proof of Examples 8. The first example is immediate, after observing that T 𝑡 𝛾 is a Gaussian of variance (1 + 𝑡) -1 . For the Gaussian mixture example, we observe from Lemma 14 that T 𝑡 (𝜇 ★ 𝛾 𝛿 ) is a Gaussian mixture of variance (𝑡 + 𝛿 -1 ) -1 , where the mixture distribution is supported in a ball of radius 𝑅 𝛿 -1 𝛿 -1 +𝑡 . Moreover, the covariance of a homogeneous mixture of the form 𝜇 ★ 𝛾 Σ is Σ + Cov(𝜇). If 𝜇 is a product measure, we observe that the isotropic tilt T 𝑡 𝜇 is also a product measure, and therefore its covariance is diagonal. Finally, by the previous argument, if 𝜋 is the uniform measure on the hypercube, then 𝜒 𝑡 (𝜋) = 𝜒 𝑡 ( 1 2 (𝛿 -1 + 𝛿 +1 )) = 1. ■ Proof of Corollary 10. We plug the spread function 𝜒 𝑡 (𝜋) = 𝜒 𝑡 (𝜇 ★ 𝛾 𝛿 ) ≤ 𝑅 1+ 𝛿𝑡 2 + 𝛿 1+ 𝛿𝑡 from Example 8 (ii) into eq. ( 12) to get (we use 𝜅 to denote 𝜅( 𝐴) for simplicity∥𝑄∥ -1 𝜅 2 (𝜅 2 -1) > 𝑅 1 + 𝛿∥𝑄∥ 2 + 𝛿 1 + 𝛿∥𝑄∥ (59) ⇔ (1 + 𝛿∥𝑄∥) ((1 + 𝛿∥𝑄∥))𝜅 2 ∥𝑄∥ (𝜅 2 -1) -𝛿 > 𝑅 2 (60) ⇔ ((1 + 𝛿∥𝑄∥) (𝜅 2 + 𝛿∥𝑄∥) ∥𝑄∥ (𝜅 2 -1)> 𝑅 2 ( 61)⇔ (1 + 𝛿SNR 2 ) (𝛿𝜅 2 + SNR -2 ) 𝜅 2 -1 > 𝑅 2 (62) ■ C. 
 
 Appendix:  


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

Reviews: review: paper_summary: paper_summary: The paper "Provable Posterior Sampling with Denoising Oracles through Tilted Transport" analyses the possibility of posterior sampling utilizing denoising oracles, such as score-based diffusion models. To demonstrate the possibilities the authors focus on linear inverse problems and propose the tilted transport technique. It uses the quadratic log-likelihood structure of linear inverse problems together with the oracle to transform the original posterior into one easier to sample. Based on the example of the Ising model the authors show that well-conditioned measurements allow the transport to simplify the task. Furthermore, first empirical tests for image tasks indicate promising practical use.
strength_weakness: strength_weakness: The topic is far from my expertise. I cannot see obvious weaknesses for this analysis. It has its limitations, but it is clearly stated and argued by the authors.
questions: questions: What is the reason for the peak with large percentiles for 10^-3 SNR in Figure 3?
limitations: limitations: yes
paper_summary: paper_summary: This paper proposes a novel posterior sampling algorithm specialized to linear inverse problems. The proposed algorithm relies on a sequence of intermediate and **tractable** posterior distributions $\nu_t$ that satisfy a transport equation up to some time $T^*$. The algorithm then operates as follows; first draw approximate samples from the distribution $\vu_{T^*}$ using any approximate inference algorithm, and then run the reverse SDE from $T^*$ to $0$ starting at the obtained samples. Of course, the computational hardness is transferred to $\nu_{T^*}$ and the authors derive sufficient conditions that ensure it is strongly log concave. The study of the algorithm is then specialized to both the Ising model and Gaussian mixtures. They show for example that $\nu_{T^*}$ is strongly log-concave for the Ising model under the condition that the eigenvalues difference is smaller than 1, thus providing a new efficient continuous time procedure for sampling from it.
strength_weakness: strength_weakness: There isn’t any serious weakness; perhaps I would have liked to see more challenging experiments and comparisons with denoising diffusion based posterior sampling algorithms, but in my opinion this is optional for this paper, since it is more on the theoretical side and has strong contributions.
questions: questions: N/A
limitations: limitations: N/A
paper_summary: paper_summary: The paper presents a theory regarding posterior sampling in linear inverse problems with additive Gaussian noise. It provides two major contributions:

* A proof that no general algorithm exists for posterior sampling of Ising models when the degradation operator is ill-conditioned.
* A transport equation for the coefficients of the quadratic form of the posterior distribution in the linear setup, transforming it into a new distribution that is easier to sample from. This includes conditions on SNR and condition number for strong log-concavity of the transformed probability, allowing for efficient sampling.

The authors illustrate their theoretical results with a toy example with Gaussian mixture model.
strength_weakness: strength_weakness: * Figure 1 and its description are not clear. I would expect it to clearly summarize the essence of the work, particularly highlighting the second contribution.

* While the paper contains rigorous derivations, it lacks intuitive explanations and simplified examples, making it difficult for readers to understand the overall direction and implications of the work as they read.
This lack of accessibility limits the paper's potential audience.  

* The focus on linear problems with additive Gaussian noise limits the practicality and potential impact of the work.

* The lack of a practical algorithm for implementing the tilted transport map limits the applicability of this work.

* The authors' decision to place the extension to nonlinear setups and imaging experiments to the appendix is puzzling, as these results are compelling and could strengthen the paper's main arguments if presented in the main body.
questions: questions: Please address weaknesses.
limitations: limitations: The limitations of the work, e.g. the focus on linear setups, are only briefly mentioned in the discussion section. This warrants a more extensive and dedicated discussion to adequately address their implications.
paper_summary: paper_summary: This work studies posterior sampling using unconditional diffusion models, or denoising oracles. The authors propose a "tilted transport" technique to combine a linear inverse problem and denoising oracles into a "boosted" posterior sampling problem. The authors study the feasibility of "boosted" posterior sampling with respect to properties (e.g. singular values) of $A$ (or $A^\top A$), the measurement operator. They devise conditions on these properties for which "boosted" posterior sampling is tractable.
strength_weakness: strength_weakness: * The presentation of this manuscript is very poor. First, the formulation is very different from other diffusion (or generative) models papers, with unusual notations and concepts, some of which are undefined in the text (e.g. quadratic tilt or $\ll$ at line 99). Second, it feels like the authors use this different formulation to purposely obfuscate their contribution. If I understand correctly, the "tilted transport" technique is an annealing of the likelihood $p(y | x_t)$ with respect to the added noise $\sigma_t^2 = 1 - \exp(-2t)$, such that it converges to $p(y | x)$ as $t$ goes to $0$. This is similar to previous works [1-4], but because the notations are so different, it is impossible for the reader to compare them. The authors should provide a thorough comparison of their method (preferably using standard formulation) with these previous works [1-4].

* In the introduction (lines 40-46), the error of previous works using heuristics (including [1-4]) is not "uncontrollable" but not analyzed. In fact, Rozet et al. [3] propose a sampling scheme that is exact for enough LMC (Langevin Monte Carlo) corrections steps. I don't see how this "contrasts with the principled sampling used in prior data generation".

* There is no algorithm to concisely describe the method. The provided code does not help as it is undocumented and frankly messy.

* The tilted transport technique is not applicable to any distribution $\pi$. In particular, sampling from $\nu_{T^*}$ is only possible in contrived settings. For most distributions $\pi$ and most measurement matrix $A$, sampling from $\nu_{T^*}$ is as hard as sampling from $\nu_0$.

* The experiments are not relevant for most general linear inverse problems. The prior distributions are low-dimensional ($d \leq 80$) mixture of few (25 components) Gaussians. The condition number of $A^\top A$ is controlled ($\kappa = 20$).

* In appendix, the authors compare their method with Meng et al. [5] which is a quite poor (and not peer-reviewed) baseline. Better baselines [1-4] are not considered.

[1] Song et al. "Pseudoinverse-Guided Diffusion Models for Inverse Problems". In International Conference on Learning Representations. 2023.

[2] Finzi et al. "User-defined Event Sampling and Uncertainty Quantification in Diffusion Models for Physical Dynamical System". In International Conference on Machine Learning. 2023.

[3] Rozet et al. "Score-based Data Assimilation". In Advances in Neural Information Processing Systems. 2023.

[4] Adam et al. "Posterior samples of source galaxies in strong gravitational lenses with score-based priors". 2022.

[5] Meng et al. "Diffusion model based posterior sampling for noisy linear inverse problems". 2022.
questions: questions: * To my understanding, simulating the reverse SDE Eq. (3) from $T$ to $0$ only generates samples from $\pi_0$ if $\pi_t$ is the measure defined by applying the Ornstein-Uhlenbeck process to $\pi_0$, i.e. $\pi_t = C_{\beta_t} D_{\alpha_t} \pi_0$. Therefore, for $\nu_t = T_{Q_t, b_t} \pi_t$ to generate samples from $\nu_0 = T_{Q, b} \pi_0$ with the reverse SDE, it would be necessary that $\nu_t = C_{\beta_t} D_{\alpha_t} \nu_0$. Is this the case?

* What is the relationship of $\nu_t$ with previous heuristics [1-4] ?

### Typos

* Line 110, $w \sim \gamma_{d'}$
* Line 122, $Q = \sigma^{-2} I_d$
* Line 222, $p(\tilde{y} | x) = p(X_{T^*} | X_0)$
limitations: limitations: See weaknesses.

Comments: title: Answer by Reviewer
Rebuttal by Authors (cont.)
comment: Thank you for the clarification
I appreciate the clarifications provided in the rebuttal. 
I believe my current score is appropriate.
Thank you, it makes much more sense. Based on my updated understanding, I now believe that this work has potential for high impact. However, I agree with reviewer **jPCg** that the manuscript lacks accessibility, which I partly attribute my misunderstanding to. Therefore, even though the contribution seems clearer for me now, you should consider making it more accessible.

In this light, I now argue for acceptance and will raise my score to 6 (previously 3).
Thank you for your quick response. Your updated understanding is correct: we construct the time-dependent family $\nu_t(x)$ and prove that the same reverse dynamics based on $\nabla \log \pi_t(x)$ used for prior data generation can transport samples along this family of distributions. This explanation is for theoretical understanding. At the algorithm level, we do only need $\nu_{T^*}$ to sample $X_{T^*}$ (or $\nu_{T^*-\epsilon}$ to sample $X_{T^*-\epsilon}$ for numerical stability).

Given your updated understanding of our approach, we hope you might consider revisiting the score for our submission. We appreciate your review and your willingness to understand our work in more detail.
Thank you for your detailed rebuttal and taking the time to answer my questions. Upon reading the algorithm provided in the global rebuttal, I notice that you are using $\nabla \log \pi_t(x)$ to simulate the reverse SDE and not $\nabla \log \nu_t(x)$ like previous posterior sampling methods would. Am I correct in understanding that $\nu_t(x)$ is only used to sample the initial $X_{T^*}$ then? If it is the case, the proposed method is indeed fundamentally different from previous methods and I am sorry for the rather harsh review.
> There is no algorithm to concisely describe the method. The provided code does not help as it is undocumented and frankly messy.


We provide a description of the algorithm in the PDF for the global response. We will improve the readability of the code in a later revision.


> The tilted transport technique is not applicable to any distribution $\pi$. In particular, sampling from $\nu_{T^*}$ is only possible in contrived settings. For most distributions $\pi$ and most measurement matrix $A$, sampling from $\nu_{T^*}$ is as hard as sampling from $\nu_0$.

While the reviewer is technically correct that our tilted transport technique is not applicable for arbitrary $\pi$, we note that in Section 3 we show that such universal guarantees are impossible. Our Corollary 10 then lays out sufficient conditions that ensure efficient sampling. We are not sure to understand the second remark, since Figure 2 in the paper shows a phase diagram indicating the interplay between A and pi that fullfils our sufficient guarantees. We also note that in Appendix C we describe an iterated tilted transport that operates under more general conditions, at the expense of introducing additional sampling error (but which can be quantified). 

> The experiments are not relevant for most general linear inverse problems. The prior distributions are low-dimensional ($d\leq 80$) mixture of few (25 components) Gaussians. The condition number of $A^\top A$ is controlled ($\kappa=20$).

We shall remark that a majority of existing methods cannot sample the posterior in this case, as noted in [1,2]. Our method, however, has both theoretical guarantees and numerical support for accurately sampling the posterior when the condition number is not too large. This is demonstrated in our numerical experiments, which validate our theoretical claims.

[1] Cardoso et al. Monte Carlo guided Denoising Diffusion models for Bayesian linear inverse problems. (2024)

[2] Janati et al. Divide-and-Conquer Posterior Sampling for Denoising Diffusion Priors (2024)


> In appendix, the authors compare their method with Meng et al. [5] which is a quite poor (and not peer-reviewed) baseline. Better baselines [1-4] are not considered.

Thank you for your comments. Our main paper primarily focuses on a provable and principled posterior sampling algorithm, and we numerically demonstrate the algorithm on Gaussian mixture priors where we can precisely characterize the ground-truth posterior and quantitatively compute the statistical quality of the obtained samples. In contrast, our experiments on imaging are preliminary. Although we demonstrated that the boosted posterior $\nu_{T^*}$ is easier to sample than $\nu_0$, $\nu_{T^*}$ may still present significant sampling challenges, leading to non-negligible errors. Consequently, a deeper investigation is required to understand how the tilted transport technique performs when $\nu_{T^*}$ has such errors.

Furthermore, it is much more difficult to assess sample quality in the posterior distribution sense for imaging problems, as a single realistic image does not necessarily imply more accurate posterior sampling. Therefore, we have decided to focus the main text on the theoretical aspects and include the imaging experiments in the appendix as potential future directions. We acknowledge the need for comparisons with better baselines and will consider these in future work as we further develop and test our method.

 
> To my understanding, simulating the reverse SDE Eq. (3) from T to 0 only generates samples from $\pi_0$ if $\pi_t$ is the measure defined by applying the Ornstein-Uhlenbeck process to $\pi_0$, i.e. $\pi_t = C_{\beta_t}D_{\alpha_t}\pi_0$. Therefore, for $\nu_t = T_{Q_t, b_t} \pi_t$ to generate samples from $\nu_0$ with the reverse SDE, it would be necessary that $\nu_t = C_{\beta_t}D_{\alpha_t}\pi_0$. Is this the case?

That is not the case. To be more specific, your first sentence is correct. However, the key finding of our tilted transport technique is that for $\nu_t = T_{Q_t, b_t} \pi_t$, which is NOT in the form of $\nu_t = C_{\beta_t}D_{\alpha_t}\pi_0$, the reverse SDE Eq. (3) from $t$ to $0$ can generate samples EXACTLY without any approximation from the target posterior $\nu_0 = T_{Q_0, b_0} \pi_0$.


> Typos. 

Thanks for pointing out these typos.