Score-based sampling without diffusions: Guidance from a simple and modular scheme
2025
Read Score-based sampling without diffusions: Guidance from a simple and modular scheme (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-24152.txt.
Introduction
M J Wainwright, a statistician, simplifies the theory of score-based sampling. Such sampling powers many modern generative models. It needs approximate score functions at several noise levels. Those scores are often available when direct sampling is hard. Wainwright asks what that availability buys in general.
His answer is a reduction. The general sampling problem splits into a sequence of easier sub-problems. Each sub-problem is strongly log-concave. The sequence is built adaptively along the way. Any good sampler for the easy case can serve as a subroutine. Complexity bounds then follow directly. One case stands out. When the target itself is strongly log-concave, the number of steps grows only logarithmically in the condition number. That yields the first efficient method with that dependence. For general targets, the count depends on score geometry.
Catalog record
| YEAR | 2025 |
|---|---|
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 96 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-24152
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Score-based sampling without diffusions: Guidance from a simple and modular scheme Abstract Sampling based on score diffusions has led to striking empirical results, and has attracted considerable attention from various research communities. It depends on availability of (approximate) Stein score functions for various levels of additive noise. We describe and analyze a modular scheme that reduces score-based sampling to solving a short sequence of “nice” sampling problems, for which high-accuracy samplers are known. We show how to design forward trajectories such that both (a) the terminal distribution, and (b) each of the backward conditional distribution is defined by a strongly log concave (SLC) distribution. This modular reduction allows us to exploit any SLC sampling algorithm in order to traverse the backwards path, and we establish novel guarantees with short proofs for both uni-modal and multi-modal densities. The use of high-accuracy routines yields ε \varepsilon -accurate answers, in either KL or Wasserstein distances, with polynomial dependence on log ( 1 / ε ) \log(1/\varepsilon) and d \sqrt{d} dependence on the dimension. Martin J. Wainwright [email protected] Lab for Information and Decision Systems Statistics and Data Science Center EECS and Mathematics, Massachusetts Institute of Technology August 10, 2026 1 Introduction The problem of drawing samples from a d -dimensional density is a core computational challenge. Efficient samplers are essential for Monte Carlo approximation (e.g., 47 ; 50 ); exploration of posterior distributions in Bayesian statistics and inverse problems (e.g., 31 ; 7 ); and generation of images, audio and other structured data in generative AI (e.g., 49 ; 22 ; 57 ; 11 ). Score-based diffusions: In recent years, researchers have demonstrated dramatic advances in sampling through the use of score-based diffusion models 51 ; 52 ; 34 ; 53 . All these procedures are based on a forward noising process: beginning with a sample X from the target distribution {p_{\mathsf{x}}} , it converts it to some form of “noise”, most often a standard Gaussian vector. In continuous time, this forward process can be described by a stochastic differential equation (SDE), and the problem of drawing samples corresponds to simulating the evolution of the reverse-time SDE 33 ; 3 that tracks backward from the noise W to a fresh sample from {p_{\mathsf{x}}} . Stochastic sampling schemes are based on careful discretizations of this reverse-time SDE (e.g., 34 ; 53 ; 37 ; 39 ; 38 ; 13 ; 9 ; 5 ), whereas other sampling schemes make use of an ordinary differential equation (ODE) that describes the backwards evolution (e.g., 53 ; 6 ; 1 ; 12 ; 8 ). In both cases, the forward process is useful, it provides the data needed to estimate the Stein score functions that describe the backwards evolution, using methods such as score matching or Tweedie-based denoising (e.g., 46 ; 41 ; 36 ; 55 ). There are now a wide variety of schemes within the general diffusion framework along with a relatively rich theoretical understanding; see Section 1.2 for further discussion. High-accuracy sampling for “nice” distributions: In parallel, the past ten years have witnessed tremendous advances in the problem of drawing samples from “nice” distributions, based only on first-order information from the original distribution (and not invoking a diffusion path). For instance, there are highly efficient methods, along with associated theoretical guarantees, for sampling from SLC class: Distributions that are strongly log-concave (SLC) and well-conditioned. Sobolev/Poincaré classes: Distributions satisfying a geometric inequality, such as a log-Sobolev inequality (LSI) or a milder Poincaré inequality. A wide spectrum of methods have been studied, including the unadjusted Langevin algorithm (ULA), its Metropolis-corrected variant (MALA), higher-order extensions including Hamiltonian Monte Carlo, as well as various proximal schemes (e.g., 24 ; 23 ; 25 ; 17 ; 28 ; 29 ; 42 ; 14 ; 54 ; 18 ; 16 ); see Section 2.1 for more detailed discussion. The modular scheme of this paper allows any of these samplers to be applied, but we focus primarily on the availability of root-dimension samplers, with iteration complexity growing as \sqrt{d} in the dimension, as well as the availability of high-accuracy samplers , capable of achieving error \varepsilon with iteration complexity that grows only polynomially in \log(1/\varepsilon) , alongside the \sqrt{d} dependency. Unifying yields a reduction: The main contribution of this paper is to bring these two lines of research into close contact, in particular by describing and analyzing a simple and modular scheme for score-based sampling. We show how, given the availability of annealed Stein scores, it is possible to “reduce” the problem of sampling from a general target density {p_{\mathsf{x}}} to the following sub-problems: • a single call to an SLC sampler applied to a distribution with condition number at most 4 , • a sequence of K calls to an SLC sampler applied to distributions with condition number at most 2 . Using this framework, we derive novel results for both sampling from log-concave densities ( Theorem 1 ), as well as from more general multi-modal densities ( Theorem 2 ). (a) (b) (c) (d) Figure 1: Contour plots of a 2- D probability densities, along with quiver plots of the Stein scores. (a) Forward marginal distributions p_{k}\equiv p_{Y_{k}} for the forward process (Y_{1},Y_{2},Y_{3},Y_{4},Y_{5}) : they are initially multi-modal, but then become progressively simpler. It is straightforward to draw samples from the density p_{Y_{5}} in the fifth panel. (b) Backward conditional distributions p_{k\mid k+1}\equiv p_{Y_{k}\mid Y_{k+1}} for k=1,2,3,4 , obtained with one random choice of sequence Y=(Y_{2},\ldots,Y_{5}) defining the backward conditionals p_{k\mid k+1}(\cdot|Y_{k+1}) . Panels (c) and (d) give same illustration with different choices of backward sequence. All three panels (b)–(d) show “nice” backward distributions; our theory gives conditions under which each of these backward conditional distributions are in the SLC class. 1.1 A geometric view Let us provide some intuition and context for the modular scheme analyzed in this paper. For a given positive integer K , we begin with the standard forward noising process \displaystyle Y_{k+1} \displaystyle=\theta_{k}X+\sqrt{1-\theta_{k}^{2}}\;W_{k}\qquad\mbox{with $W_{k}\sim\mathcal{N}(0,\mathbf{I})$,} (1) for k=0,1,\ldots K-1 . Setting \theta_{0}=1 ensures that Y_{1}=X , and (\theta_{1},\ldots\theta_{K-1}) are scalars in the interval (0,1) to be chosen. In the standard diffusion approach, the sequence ( 1 ) represents a discretization of a variance-preserving SDE 34 ; 53 . The trajectory length K=K(\varepsilon) is chosen as a function of the target accuracy \varepsilon so as to ensure accurate tracking of the reverse-time SDE or ODE; for this reason, one essential \varepsilon -dependent bottleneck is the discretization error, and leads to iteration complexities that scale linearly in dimension d , and polynomially in (1/\varepsilon) . In contrast, our modular scheme avoids any consideration of discretized diffusions, and makes use of trajectory lengths K that are independent of the target accuracy \varepsilon , and satisfy the following two properties: (T) It is easy to sample from the terminal marginal distribution Y_{K}\sim p_{K} , and (B) Each of the backward conditional distributions Y_{k}\mid Y_{k+1} are strongly log-concave (SLC) with constant condition number, and hence easy for sampling. When these two properties hold, we can carry out each transition in the reverse chain by exploiting fast samplers for SLC distributions. Our analysis quantifies the size of the steps \theta_{k} and hence trajectory length that guarantee these two properties. A simple