The Tractability Landscape of Sampling with Inexact Scores Anming Gu∗
Kevin Tian†
Hubert Yang‡
Yusong Zhu§
Abstract
arXiv:2607.19004v1 [stat.ML] 21 Jul 2026
We provide a simple and tight characterization of the types of inexact score oracle access that permit sampling with vanishing total variation bias, for a standard, well-behaved target family. Our main result shows that any weaker error than the sub-Gaussian assumption used by [YW26] rules out the tractability of unbiased sampling. This strengthens the conclusion of [CCSW26] to be algorithm-agnostic, and to hold for a wider range of error assumptions.
1
Introduction
The development of an inexact oracle complexity theory has been central to our understanding of stochastic optimization [NY83, ABRW12]. We consider an analogous question in sampling. Problem 1. Given a distribution π on Rd belonging to a well-behaved class, and oracle access to s : Rd → Rd that approximates sπ := ∇ log π, under what error assumptions on (s, π) is it possible to sample to within arbitrary TV distance of π, as we take the error bound to 0? We focus on the canonical family of π that are log-smooth (i.e., sπ is Lipschitz), and that satisfy a log-Sobolev inequality (LSI).1 For this target family, [YW26] shows that a sub-Gaussian score error (i.e., β = 2 in Definition 2) with appropriate parameters is sufficient to solve Problem 1. Our main finding is that the error condition assumed by [YW26] is necessary: any qualitatively weaker condition results in intractability, even for log-smooth, LSI targets. Theorem 1 (Informal, see Theorem 2). Standard weaker variants of the assumption used in [YW26], e.g., bounded moments (Definition 1) or sub-Weibull error (Definition 2 with β ∈ (0, 2)) make sampling to vanishing TV impossible, even as the error bound goes to 0. Moreover, the parameters used in the sub-Gaussian error assumption in [YW26] are also tight up to constant factors. Our counterexample is simple and geometric, and is illustrated in Figure 1. It uses two well-separated Gaussians, and an estimate s that interpolates between the true scores. The LSI property allows both distributions to simultaneously satisfy any weaker score error than sub-Gaussianity. ∗
University of Texas at Austin, [email protected] University of Texas at Austin, [email protected] ‡ University of Texas at Austin, [email protected] § University of Texas at Austin, [email protected] 1 The LSI is a robust form of isoperimetry that is often taken to admit tractability of sampling algorithms [VW19], and applies to (but is not limited to) strongly log-concave distributions [BÉ85]. †
1
Theorem 1 is related to recent work of [CCSW26], who considered the tractability of Problem 1 under score estimation error with bounded moments. Our result strengthens their lower bound in the following ways. First, it applies to any algorithm querying s, whereas [CCSW26] only disproved convergence of the inexact Langevin dynamics. Second, it rules out a wider range of inexactness notions, i.e., essentially the entire range of error assumptions below that used by [YW26]. Preliminaries. Let IE denote the 0-1 indicator of an event E. Let P(Ω) denote the set of probability measures on Ω. We only consider measures in P(Rd ) that are absolutely continuous with respect to the Lebesgue measure, and we overload notation by identifying a measure withRits density function. For µ, π ∈ P(Rd ), we denote their total variation distance by TV(µ, π) := 12 Rd |µ(x) − π(x)|dx. For π ∈ P(Rd ), we let sπ := ∇ log π be the true score. We use s : Rd → Rd to denote a vector field, often an approximate score. We say that π ∈ P(Rd ) is L-log-smooth and µ-strongly log-concave if, respectively, − log π is L-smooth and µ-strongly convex (cf. Sections 3.2, 3.4 [Bub15]). If π is µ-strongly log-concave, it also satisfies a µ-LSI. Next, we define the two types of score error assumptions we consider. Definition 1 (Lp error). For s : Rd → Rd , π ∈ P(Rd ), ε > 0, and p > 0, if Eπ [∥s − sπ ∥p2 ]
1/p
≤ ε,
we say that the pair (s, π) satisfies an ε-Lp error. Definition 2 (MGF error). For s : Rd → Rd , π ∈ P(Rd ), ε > 0, r > 0, and β > 0, if
i1/β h 1 β ≤ ε, log Eπ exp r ∥s − sπ ∥2 r
we say that the pair (s, π) satisfies an ε-(β, r)-MGF error. The following result shows that MGF error implies Lp error (with appropriate parameters), so that hard instances satisfying Definition 2 also act as lower bounds under Definition 1. Lemma 1. Fix ε > 0 and p > 0. There exist β ∈ (0, 2) and r > 0 such that if the pair (s, π) satisfies an ε-(β, r)-MGF error, then it also satisfies an ε-Lp error. Proof. Let β = 1 and r = pε , and assume that (s, π) satisfies an ε-(β, r)-MGF error. For every x > 0, we have log x ≤ x − 1, which rearranged gives xp ≤ exp(−p + px). Applying this pointwise with x ← 1ε ∥s − sπ ∥2 and taking expectations over π, Eπ
∥s − sπ ∥2 ε
p ≤ exp(−p)Eπ [exp (r ∥s − sπ ∥2 )] ≤ exp(−p) exp(rε) = 1,
where the last inequality used our MGF error assumption. Rearranging the above display and taking pth roots now shows that (s, π) satisfies an ε-Lp error. We also observe that by Jensen’s inequality, Definition 1 is monotone nondecreasing in strength as p grows, and Definition 2 is monotone nondecreasing in strength as r grows.
2
sπ1,ε (x) = −x
score interpolation
π2,ε = N (R, 1) x π1,ε = N (0, 1)
R/3
2R/3 sε (x)
sπ2,ε (x) = −(x − R) Figure 1: Scores only disagree with sε on regions where corresponding measures assign small mass.
2
Lower Bounds
We begin by providing our main hard example. Proposition 1. Fix β ∈ (0, 2) and r > 0. For any ε > 0, there exist two 1-log-smooth, 1-strongly log-concave distributions π1,ε , π2,ε ∈ P(Rd ), and 5-Lipschitz sε : Rd → Rd , such that (sε , π1,ε ) and (sε , π2,ε ) both satisfy ε-(β, r)-MGF error, and TV(π1,ε , π2,ε ) > 32 .2 Proof. Our example is in dimension d = 1, so we use sε instead of sε to denote the scalar approximate score. Choose R > 2 to be any value such that 1/β 1 3 R2 log 1 + √ exp − + rRβ ≤ ε. (1) r 18 R 2π Such a value exists as β < 2. We now take π1,ε = N (0, 1) and π2,ε = N (R, 1). It is immediate that both distributions are 1-strongly log-concave and 1-smooth, and that TV(π1,ε , π2,ε ) ≥ 32 . It remains to construct sε . We first define 1 ρ(t) ρ(t) := exp − It>0 , θ(t) := , t ρ(t) + ρ(1 − t)
χ(u) = θ(3u − 1).
Observe that θ ∈ C ∞ (R), θ(t) = 0 for t ≤ 0 and θ(t) = 1 for t ≥ 1. We next define x sε (x) := −x + R · χ , R which we note agrees with the scores of π1,ε and π2,ε on x ≤ R3 and x ≥ 2R 3 , respectively. We now bound the Lipschitz constant of sε . For t ∈ (0, 1), we can calculate ρ(t)ρ(1 − t) 1 1 ′ θ (t) = + . (ρ(t) + ρ(1 − t))2 t2 (1 − t)2 2
We use 32 for simplicity, but any constant < 1 is achievable through a small modification of the proof.
3
(2)
Outside this interval, θ′ = 0. Then, we can check that θ′ is maximized at t = 12 by observing θ′′ ≥ 0 over 0 ≤ t ≤ 12 and θ′ is symmetric on (0, 1). This ensures θ′ ∈ [0, 2], which implies s′ε ∈ [−1, 5]. We conclude by proving (sε , π1,ε ) satisfy ε-(β, r)-MGF error, and the same claim holds for π2,ε by symmetry. The true score is sπ1,ε (x) = −x and χ has range [0, 1], so by (2), ∆ = sup |sε − sπ1,ε | ≤ R. Moreover, since χ(u) = 0 if u ≤ 31 , we know that sε (x) ̸= sπ1,ε (x) implies x > R3 . Thus, i h i h β Ex∼π1,ε exp r sε (x) − sπ1,ε (x) ≤ 1 + Ex∼π1,ε exp r∆β − 1 Ix> R 3 R ≤ 1 + exp(rRβ ) Pr x > x∼π1,ε 3 2 3 R β ≤ 1 + √ exp − + rR . 18 R 2π The last line applied a standard Gaussian tail bound (e.g., Proposition 2.1.2, [Ver25]). Thus we have shown that (sε , π1,ε ) satisfies ε-(β, r)-MGF error, upon using the definition (1). 1 Corollary 1. The conclusion of Proposition 1 also holds when β = 2, r < 18 .
Proof. The only place the assumed bounds on (β, r) were used in Proposition 1’s proof was in the 1 existence of R satisfying (1). This existence still holds for β = 2, r < 18 . Theorem 2. There does not exist an algorithm A with the property that: for any 1-log-smooth π satisfying 1-LSI, and any s : Rd → Rd satisfying one of the following error assumptions, A only makes queries to s and returns a sample x such that TV(Law(x), π) ≤ 31 . 1 • (s, π) satisfies an ε-(β, r)-MGF error for any ε > 0, where either β ∈ (0, 2), or β = 2, r < 18 .
• (s, π) satisfies an ε-Lp error, for any ε > 0, p > 0. Proof. The first claim is immediate from Proposition 1 and Corollary 1, by taking s ← sε . Indeed, then π could be either π1,ε or π2,ε , and the triangle inequality contradicts TV(π1,ε , π2,ε ) > 32 . The second claim follows by applying Proposition 1 with (β, r) given by Lemma 1. 1 We note that the β = 2, r < 18 branch ruled out by Theorem 2 shows that the range of r handled by Theorem 2, [YW26] (roughly, larger than the inverse LSI constant) is also tight up to constants. p Remark 1. It suffices to take R ≈ log(1/ε) for the construction in Proposition 1. The construction does not extend if we restrict the range on R to be independent of ε. Indeed, no score s can have vanishing error ε → 0 with respect to both sπ1,ε (x) = −x and sπ2,ε (x) = −x + R:
h i h i R2 Ex∼N (0,1) |s(x) + x|2 + Ex∼N (R,1) |s(x) + x − R|2 ≥ (1 − TV (N (0, 1), N (R, 1))) · , 2 2
because |s + x|2 + |s + x − R|2 ≥ R2 for any choice of s, x. The right-hand side above cannot be taken → 0 without allowing R to grow. Notably, this shows Theorem 2 does not naturally extend to the 4
DDPM setting, where approximate score access with vanishing error is assumed at all convolution scales, including scales where, applied to unit-variance Gaussians, convolving takes R → 0. This is unsurprising, as L2 error is known to suffice for TV convergence there [CCL+ 23, CLL23].
References [ABRW12] Alekh Agarwal, Peter L. Bartlett, Pradeep Ravikumar, and Martin J. Wainwright. Information-theoretic lower bounds on the oracle complexity of stochastic convex optimization. IEEE Trans. Inf. Theory, 58(5):3235–3249, 2012. [BÉ85]
Dominique Bakry and Michel Émery. Diffusions hypercontractives. In Jacques Azéma and Marc Yor, editors, Séminaire de Probabilités XIX, 1983/84, volume 19 of Lecture Notes in Mathematics, pages 177–206. Springer, Berlin, 1985.
[Bub15]
Sébastien Bubeck. Convex optimization: Algorithms and complexity. Found. Trends Mach. Learn., 8(3-4):231–357, 2015.
[CCL+ 23] Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru Zhang. Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. In The Eleventh International Conference on Learning Representations, 2023. [CCSW26] Daniel Yiming Cao, August Y. Chen, Karthik Sridharan, and Yuchen Wu. On the robustness of Langevin dynamics to score function error. In Forty-third International Conference on Machine Learning, ICML 2026, Proceedings of Machine Learning Research. PMLR / OpenReview.net, 2026. [CLL23]
Hongrui Chen, Holden Lee, and Jianfeng Lu. Improved analysis of score-based generative modeling: User-friendly bounds under minimal smoothness assumptions. In International Conference on Machine Learning, ICML 2023, volume 202 of Proceedings of Machine Learning Research, pages 4735–4763. PMLR, 2023.
[NY83]
A.S̃. Nemirovsky and D.B̃. Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons, 1983.
[Ver25]
Roman Vershynin. High-dimensional probability, 2025.
[VW19]
Santosh Vempala and Andre Wibisono. Rapid convergence of the unadjusted Langevin algorithm: Isoperimetry suffices. Advances in neural information processing systems, 32, 2019.
[YW26]
Kaylee Yingxi Yang and Andre Wibisono. Convergence of the inexact Langevin algorithm in KL divergence with application to score-based generative models. arXiv preprint arXiv:2211.01512, 2026.
5