📊 statistics

The Tractability Landscape of Sampling with Inexact Scores

This paper establishes a tight characterization of inexact score oracle access, proving that any error weaker than the sub-Gaussian assumption renders unbiased sampling intractable for well-behaved target distributions, thereby strengthening previous algorithm-agnostic results.

Original authors: Anming Gu, Kevin Tian, Hubert Yang, Yusong Zhu

Published 2026-07-22

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Anming Gu, Kevin Tian, Hubert Yang, Yusong Zhu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot to draw a perfect picture of a specific landscape, like a mountain range at sunset. You can't show the robot the whole picture at once; instead, you have to give it a tiny, blurry hint every time it asks, "Which way should I go next?" to get closer to the right spot. In the world of computer science and statistics, this is called sampling. The "landscape" is a complex mathematical distribution (a map of where things are likely to be), and the "hint" is a score, which is just a fancy word for a compass needle pointing toward the most likely areas.

For years, scientists have been trying to figure out how much the compass can be broken or "noisy" before the robot gets hopelessly lost. If the compass is perfect, the robot finds the mountain easily. But what if the compass is slightly off? What if it points the right way most of the time, but occasionally spins wildly? This is the question of inexact scores. The big deal here is that if we can tolerate a broken compass, we can build faster, cheaper, and more powerful AI tools for everything from drug discovery to generating art. But if the compass is too broken, no amount of clever programming will save us; the robot will never find the mountain, no matter how long it walks.

This paper, titled "The Tractability Landscape of Sampling with Inexact Scores," dives right into that messy middle ground. The authors, Anming Gu, Kevin Tian, Hubert Yang, and Yusong Zhu, are essentially playing a high-stakes game of "gotcha" with the rules of how broken a compass can be. They start by looking at a recent idea from other researchers who suggested that as long as the compass errors are "sub-Gaussian" (a specific, very strict type of randomness where wild spins are extremely rare), we can still find our way. The authors of this paper say, "Hold on a second. Is that the only way it works? What if the errors are just a tiny bit less strict than that?"

Their main finding is a definitive "no." They prove that if you relax the rules even a little bit—allowing for errors that are slightly more unpredictable than the "sub-Gaussian" limit, such as errors with "bounded moments" or "sub-Weibull" behavior—then it becomes impossible to sample correctly, no matter how smart your algorithm is. It's like saying, "If your compass is allowed to spin even 1% more wildly than this specific limit, you are doomed to wander in circles forever." They didn't just guess this; they built a mathematical trap, a specific scenario involving two very similar-looking but distinct landscapes (two separated Gaussian hills), to prove that any algorithm trying to use a slightly weaker compass will inevitably fail to tell the difference between the two.

The paper also clarifies that the strict rules used by previous researchers aren't just a safe bet; they are the tightest possible rules. You can't loosen them up without breaking the whole system. The authors show that even if you let the error bound get smaller and smaller (approaching zero), if the type of error is the wrong kind, the robot still can't converge to the right answer. They use a clever geometric trick: imagine two hills that are far apart. The "broken compass" they design points correctly on the hills but acts weirdly in the empty space between them. Because the hills are far apart, the robot rarely visits the weird space, so the compass looks perfect most of the time. But that tiny bit of weirdness is enough to confuse the robot into thinking the two hills are actually the same place, or that it's somewhere else entirely.

In short, this paper draws a hard line in the sand. It tells us that the "sub-Gaussian" assumption isn't just a convenient mathematical shortcut; it is a fundamental requirement. If you want to sample from a well-behaved distribution using an imperfect compass, that compass must be incredibly reliable. If it's even a little bit more chaotic than that, the problem becomes unsolvable. The authors didn't just suggest this; they proved it with a rigorous mathematical argument that rules out any algorithm, past, present, or future, from succeeding under those weaker conditions. It's a reminder that in the world of AI and math, sometimes the difference between success and failure is as thin as the edge of a mathematical cliff.

Technical Summary: The Tractability Landscape of Sampling with Inexact Scores

Problem Statement
This paper investigates the fundamental limits of sampling from a target distribution $\pi$ on $\mathbb{R}^d$ when the algorithm only has access to an approximate score function $s \approx s_\pi := \nabla \log \pi$ . The central question (Problem 1) is: Under what error assumptions on the pair $(s, \pi)$ is it possible to generate samples with vanishing total variation (TV) distance to $\pi$ as the error bound approaches zero?

The authors focus on a standard, well-behaved target family: distributions that are log-smooth (the true score is Lipschitz) and satisfy a Log-Sobolev Inequality (LSI). This class includes strongly log-concave distributions and is widely considered the regime where sampling is tractable.

Methodology and Preliminaries
The paper establishes a theoretical framework by defining two primary classes of score error assumptions:

$L_p$ Error: The $p$ -th moment of the error norm is bounded by $\epsilon$ .
MGF (Moment Generating Function) Error: A stronger condition involving the expectation of the exponential of the error norm, parameterized by $\beta$ and $r$ . This generalizes sub-Gaussian error (where $\beta=2$ ).

The authors prove that MGF error implies $L_p$ error (Lemma 1), establishing that lower bounds derived under MGF assumptions automatically apply to $L_p$ assumptions.

Key Contributions and Results
The paper's primary contribution is a tight characterization of the error conditions required for tractable sampling. The main result (Theorem 2) demonstrates that the sub-Gaussian error assumption used in prior work [YW26] is not merely sufficient but necessary for unbiased sampling within this target family.

Intractability of Weaker Errors: The authors prove that any error condition qualitatively weaker than the sub-Gaussian assumption used by [YW26] renders unbiased sampling impossible. Specifically, sampling to vanishing TV distance is impossible if the error satisfies:
- Sub-Weibull errors: MGF errors with $\beta \in (0, 2)$ .
- Bounded moments: Standard $L_p$ error assumptions for any $p > 0$ .
- Tight sub-Gaussian parameters: Even within the sub-Gaussian regime ( $\beta=2$ ), if the parameter $r$ is too small (specifically $r < 1/18$ ), sampling is intractable.
The Counterexample (Proposition 1): The proof relies on a simple, geometric counterexample involving two well-separated Gaussian distributions, $\pi_1 = \mathcal{N}(0, 1)$ and $\pi_2 = \mathcal{N}(R, 1)$ , where $R$ is large.
- The authors construct a single approximate score function $s_\epsilon$ that interpolates between the true scores of $\pi_1$ and $\pi_2$ .
- This $s_\epsilon$ agrees with the true score of $\pi_1$ on the left tail and $\pi_2$ on the right tail, differing only in the low-probability region between them.
- Crucially, because the distributions assign negligible mass to the region where $s_\epsilon$ is incorrect, the pair $(s_\epsilon, \pi_i)$ satisfies the weaker error assumptions (sub-Weibull or bounded moments) for arbitrarily small $\epsilon$ .
- However, because the true distributions are far apart in TV distance ( $> 2/3$ ), no algorithm querying only $s_\epsilon$ can distinguish between $\pi_1$ and $\pi_2$ , making it impossible to sample from the correct target with vanishing bias.

Significance and Relation to Prior Work
The paper claims to strengthen the conclusions of recent work by [CCSW26] in two specific ways:

Algorithm-Agnostic: While [CCSW26] only disproved the convergence of inexact Langevin dynamics, this result rules out any algorithm that queries the score oracle, regardless of the specific sampling method used.
Broader Scope: It rules out a wider range of error notions, essentially covering the entire spectrum of error assumptions below the sub-Gaussian threshold used by [YW26].

The authors emphasize that their result is "tight up to constant factors." The parameters required for the sub-Gaussian assumption in [YW26] are shown to be necessary; relaxing them leads to intractability.

Limitations and Scope
The paper explicitly notes that this intractability result does not naturally extend to the Denoising Diffusion Probabilistic Model (DDPM) setting. In DDPMs, approximate score access is assumed at all convolution scales, including scales where the separation between Gaussians ( $R$ ) shrinks to zero. In that specific regime, $L_2$ error is known to suffice for TV convergence, a condition not met by the fixed-separation counterexample used here.

In summary, the paper establishes that for log-smooth, LSI-satisfying distributions, the sub-Gaussian error assumption is the precise threshold for tractability. Any weaker assumption allows for the construction of "hard" instances where the score oracle is misleading in low-probability regions, rendering unbiased sampling impossible.

Technical Summary: The Tractability Landscape of Sampling with Inexact Scores

More like this