The information geometry of product-reference discrete diffusion: Interaction growth complexity and optimal scheduling

Martin J. Wainwright

stat.MLAug 28, 2026

The information geometry of product-reference discrete diffusion: Interaction growth complexity and optimal scheduling

Authors: Martin J. Wainwright

Organizations: Lab for Information and Decision Systems Statistics and Data Science Center EECS and Mathematics, Massachusetts Institute of Technology

Abstract

We study a class of product-reference diffusion algorithms for sampling from a discrete distribution. We show that their sampling performance can be characterized using a path-based measure of data geometry that we call the interaction growth complexity (IGC). We show that a bivariate IGC kernel gives an exact representation of both the KL discretization error and a simple one-step upper bound. The simpler univariate IGC density can be used to study the effect of stepsize choices on the iteration complexity required to obtain $ε$ -accurate samples in KL divergence. Samplers that traverse the path with equi-spaced steps in log-squared-reliability-odds have performance that depends on the aggregate IGC mass, whereas refined choices of stepsizes have a lower complexity depending on a square-root functional. In the fine-grid limit, both of these characterizations become sharp. We also allow general product reference distributions and show that the reference law can substantially reshape the IGC profile and the resulting sampling complexity; in particular, references far from both the uniform and the data marginals can yield dimension-dependent improvements. Finally, the aggregate IGC mass admits bounds in terms of total correlation and dual total correlation, thereby connecting the pathwise geometry to classical measures of multivariate dependence.

Figures & tables

Figure 1: Plots of the IGC density

\mathsf{q}

for the noisy repeated bit model in equation ( 5 ), for three different settings of the noise level

\eta\in\{0.01,0.30,0.45\}

. The IGC density captures the decaying dependence on the latent bit

U

\eta

evolves towards the endpoint

1/2

Figure 2: Illustration of the IGC density for the Curie–Weiss model ( 6 ). Bottom panels from left to right correspond to

\beta\in\{0.70,1.00,1.20,1.60\}

. For each choice of

\beta

, the matrix presents a collection of random samples

Z\sim\mathbb{P}_{Z}

, one in each row.

Figure 3: Plots of the IGC densities

\mathsf{q}

associated with various types of hierarchical binary-prototype mixtures. The rows correspond to hierarchy depths

L=2

and

L=3

. Left panels (a) and (c) show the leaf prototypes, while right panels (b) and (d) show the corresponding densities

\mathsf{q}

Figure 4: Log-odds IGC densities

\mathsf{q}

for Ensemble A, with

\epsilon_{d}=d^{-1/2}

, under (a) the uniform reference, (b) the absorbing-state reference, and (c) the marginal-matched reference.

Figure 5: Dimension dependence of the aggregate IGC for different choices of reference. Panel (a) shows Ensemble A, with

\epsilon_{d}=d^{-1/2}

, for which the marginal-matched reference becomes increasingly unfavorable. Panel (b) shows Ensemble B, with

1-\epsilon_{d}=d^{-1}

, for which the uniform reference has constant-order IGC whereas the IGC for the absorbing-state reference grows as

\Theta(\log d)

Diffusion Sampling

Diffusion sampling studies how to turn a trained diffusion model into high-quality samples efficiently and reliably.

See all 265 papers

Denoising growth complexity: Data geometry and certified schedules for diffusion sampling
Jul 28, 2026Martin J. WainwrightSample Complexity Diffusion Sampling
Lab for Information and Decision Systems Statistics and Data Science Center EECS and Mathematics, Massachusetts Institute of Technology
The data geometry of masking diffusion: Certified-optimal schedules via unmasking growth complexity
Aug 13, 2026Martin J. WainwrightMasked Diffusion Models Diffusion Sampling
Lab for Information and Decision Systems · Statistics and Data Science Center · EECS and Mathematics
Iterative Exact Discrete Guidance for Energy-Based Sampling
Sep 29, 2026Yuwen Qian, Yidong Ouyang, Zhengyan Wan +1Sampling from Unnormalized Distributions Adaptive Sampling
School of Science and Engineering, The Chinese University of Hong Kong, Shenzhen · Department of Statistics, University of California, Los Angeles · School of Data Science, The Chinese University of Hong Kong, Shenzhen

Jul 28, 2026J/K move · Enter open · S save

Denoising growth complexity: Data geometry and certified schedules for diffusion sampling

Martin J. Wainwright

Lab for Information and Decision Systems Statistics and Data Science Center EECS and Mathematics, Massachusetts Institute of Technology

Sample Complexity Diffusion Sampling Adaptive Sampling Diffusion Model Acceleration

Open paper AskPDF arXiv

Two central challenges in diffusion-based sampling are the theoretical one of understanding their remarkable effectiveness even in high-dimensional settings, and the practical one of designing algorithms with certified performance guarantees. We show that these questions are intimately connected via the denoising growth complexity (

\mathsf{DGC}

). It is a geometric measure defined by a log-time weighted integral of the derivative of the denoising mean-squared error along the Gaussian heat flow. We show how the

\mathsf{DGC}

increments lead to a simple and explicit bound on the KL error of an Euler scheme applied to the stochastic innovations representation. The bound is local along the path: each step is controlled by the corresponding

\mathsf{DGC}

increment and its relative stepsize. This structure allows us to derive KL sampling guarantees for optimized stepsize schedules, both in a simpler single-block setting and in a more refined

K

-block setting. The

\mathsf{DGC}

function has a natural martingale structure, which we exploit to develop fully data-certified versions of these algorithms. It also admits information-theoretic upper bounds in terms of covariance, rate distortion, metric entropy, and the Poincar'e constant, thereby recovering and sharpening a range of existing diffusion-sampling guarantees, as well as giving new results. In log heat-time, the fine partition limit is governed by an integral involving the square root of the

\mathsf{DGC}

density, whereas a single-block schedule depends on its ordinary integral. This comparison precisely characterizes when adaptation to data geometry yields substantial computational gains, including logarithmic-to-constant separations for simple Gaussian mixture models.

Abstract

Diffusion Sampling

Explore similar work

Denoising growth complexity: Data geometry and certified schedules for diffusion sampling

The data geometry of masking diffusion: Certified-optimal schedules via unmasking growth complexity

Iterative Exact Discrete Guidance for Energy-Based Sampling