Sample complexity bounds for categorical Markov random fields via Discrete Diffusions

Shivam Kumar; Nabarun Deb

math.STOct 1, 2026

Sample complexity bounds for categorical Markov random fields via Discrete Diffusions

Authors: Shivam Kumar, Nabarun Deb

Organizations: Booth School of Business, University of Chicago

Abstract

Many applications in statistics, economics, and physics require sampling from high-dimensional categorical distributions with local dependence structures. Examples include finite memory language models, Ising and Potts systems in statistical physics and protein folding, etc. In modern machine learning, discrete diffusions have emerged as a flexible approach for sampling such data, with strong empirical performance. Motivated by this, we develop learning methods with end-to-end sample complexity bounds for discrete diffusion with uniform noising under local dependence, which we model through low order Markov random fields (MRFs). Our main technical insight is a new \emph{pinning decomposition} of the discrete score. It shows that unlike in continuous diffusions, the score decomposes into components where the dependence on time separates multiplicatively from the dependence on the target. Building on this decomposition, we propose a \emph{weight-sharing neural score learner} and combine it with $τ$ -leaping to obtain an end-to-end sampling procedure. Rather than treating score-learning error as a black-box input, as is common in existing sampling analyses, we study the score learning error from finite data and derive optimal sampling guarantees with explicit dependence on the vocabulary size, the interaction order of the MRF, and the sample size. Moreover, our strategy trains a single score network across uniform noise levels while leaving the sampling discretization to be chosen at inference-time. This allows the same trained model to trade accuracy for computational cost as inference-time budgets vary. Numerical experiments on Potts, Ising, and tree-structured models show that weight-sharing score networks outperform fully connected ones for sampling long sequences.

Figures & tables

Panel of Figure 1 — Fig 1: Weight sharing across spatial positions in a CNN and time steps in an unrolled RNN. Matching edge labels denote shared coefficients, replicated by $\omega$ . Here $\rho$ is ReLU; biases and zero entries are omitted.

\mathbf{z}_{0}\sim\operatorname{Unif}([S]^{{\mathsf{D}}}).

Algorithm 1

\tau

-leaping for uniform noising

Panel of Figure 3 — Fig 2: The bottleneck in the example ( 4.12 ), with ${\mathsf{D}}=6$ , $d=2$ , ${\mathsf{m}}=\{1,2,3\}$ , and $S=3$ . (a) Summing out the sixth coordinate $b=z^{6}$ involves the three tables linking it to the pinned coordinates (green), which carry the input $\mathbf{x}_{\mathsf{m}}$ , and the tables $\psi_{\{4,6\}}$ (blue) and $\psi_{\{5,6\}}$ (red), which do not depend on the input. Dashed edges join pinned coordinates and are evaluated directly, and $\psi_{\{4,5\}}$ (grey) enters only at the next step. (b) The step touches the $S^{3}=27$ positions $(z^{4},z^{5},b)$ , and the weight at each position is the product $a_{z^{4}b}e_{z^{5}b}$ of an entry of $\psi_{\{4,6\}}$ and an entry of $\psi_{\{5,6\}}$ . The shaded entry $a_{21}$ fills three positions, and so does $e_{32}$ , so the $2S^{2}=18$ stored numbers fill all $27$ positions.

	Smaller dimension			Larger dimension
Model	${\mathsf{D}}$	$S$	$d$	${\mathsf{D}}$	$S$	$d$
Potts chain	8	3	2	32	3	2
Ising ladder	8	2	2	32	2	2
Categorical tree	7	3	2	32	3	2

Table 1: Target distributions used in the experiments. Here

{\mathsf{D}}

is the dimension,

S

is the vocabulary size, and

d

is the interaction order.

Potts chain
Method	Risk $\times 10^{3}\downarrow$	Edge TV $\downarrow$	MMD ${}^{2}\times 10^{3}\downarrow$	$W_{1}(H)\downarrow$
LSE	$10.786\,\pm\,0.113$	$0.1356\,\pm\,0.0012$	$1.555\,\pm\,0.124$	$9.097\,\pm\,0.086$
Conv	$\mathbf{6.714\,\pm\,0.913}$	$\mathbf{0.1017\,\pm\,0.0119}$	$\mathbf{1.138\,\pm\,0.243}$	$\mathbf{6.084\,\pm\,0.973}$
Butterfly	$52.858\,\pm\,0.915$	$0.3652\,\pm\,0.0037$	$4.333\,\pm\,0.114$	$24.393\,\pm\,0.237$
MLP	$56.175\,\pm\,0.423$	$0.3817\,\pm\,0.0034$	$4.303\,\pm\,0.116$	$25.422\,\pm\,0.235$
Ising ladder

Table 2: Larger examples (

{\mathsf{D}}=32

) at

n=8192

and

K=N=256

. Entries are mean

\pm

SE over ten repetitions. Bold marks the smallest mean for each target and metric.

Potts chain
Method	Risk $\times 10^{3}\downarrow$	Edge TV $\downarrow$	MMD ${}^{2}\times 10^{3}\downarrow$	$W_{1}(H)\downarrow$
LSE	$10.131\,\pm\,0.205$	$0.1380\,\pm\,0.0036$	$6.012\,\pm\,0.239$	$2.116\,\pm\,0.055$
Conv	$\mathbf{5.081\,\pm\,0.183}$	$\mathbf{0.0742\,\pm\,0.0036}$	$\mathbf{1.445\,\pm\,0.415}$	$\mathbf{0.785\,\pm\,0.084}$
Butterfly	$13.843\,\pm\,0.964$	$0.1267\,\pm\,0.0089$	$2.808\,\pm\,0.588$	$1.811\,\pm\,0.137$
MLP	$10.092\,\pm\,0.199$	$0.0995\,\pm\,0.0052$	$1.605\,\pm\,0.170$	$1.410\,\pm\,0.110$
Ising ladder

Table 3: Smaller examples at

n=8192

and

K=N=256

. Entries are mean

\pm

SE over ten repetitions. Bold marks the smallest mean for each target and metric.

Potts chain
$K$	LSE	Conv	Butterfly	MLP
64	$10.756\,\pm\,0.137$	$\mathbf{4.836\,\pm\,0.153}$	$53.005\,\pm\,0.892$	$56.128\,\pm\,0.352$
128	$10.708\,\pm\,0.117$	$\mathbf{5.225\,\pm\,0.165}$	$53.107\,\pm\,0.820$	$56.231\,\pm\,0.421$
256	$10.786\,\pm\,0.113$	$\mathbf{6.714\,\pm\,0.913}$	$52.858\,\pm\,0.915$	$56.175\,\pm\,0.423$
Ising ladder
64	$\mathbf{1.388\,\pm\,0.022}$	$9.958\,\pm\,0.553$	$13.325\,\pm\,0.561$	$19.597\,\pm\,0.446$

Table 4: Score risk (

\times 10^{3}

) across training grids for

{\mathsf{D}}=32

and

n=8192

. Entries are mean

\pm

SE over ten repetitions. Bold marks the smallest mean in each row.

Fig 3: Changes from

N=32

in squared MMD (top,

\times 10^{3}

) and mean edge-pair TV (bottom), with

{\mathsf{D}}=32

n=8192

, and

K=256

. Negative values indicate improvement. Error bars show SE of paired differences over ten repetitions. Dashed curves use the exact target score. Vertical scales differ across panels.

Target	Regime	${\mathsf{D}}$	$S$	$\|E\|$	$p$
Potts chain	Smaller	8	3	7	7
Ising ladder	Smaller	8	2	10	18
Categorical tree	Smaller	7	3	6	38
Potts chain	Larger	32	3	31	31
Ising ladder	Larger	32	2	46	78
Categorical tree	Larger	32	3	31	188

Table A.1: Dimensions, graph sizes, and numbers

p

of target-feature coefficients. All examples have interaction order

d=2

Example	LSE	Conv	Butterfly	MLP
Small Potts chain	23	10146	13314	39824
Small Ising ladder	56	10081	13249	37768
Small Categorical tree	116	10146	13314	39182
Large Potts chain	95	16354	21634	55232
Large Ising ladder	236	16289	21569	47008
Large Categorical tree	566	16354	21634	55232

Table A.2: Trainable parameter counts. Parameter budgets are not matched.

Metric	LSE	Conv	Butterfly	MLP
Smaller Potts chain
Score risk	$0.01013\,\pm\,0.00021$	$\mathbf{0.00508\,\pm\,0.00018}$	$0.01384\,\pm\,0.00096$	$0.01009\,\pm\,0.00020$
Centered DSE	$-0.0621\,\pm\,0.0008$	$\mathbf{-0.0669\,\pm\,0.0013}$	$-0.0580\,\pm\,0.0012$	$-0.0619\,\pm\,0.0011$
DSE obs. SD	$0.0476\,\pm\,0.0014$	$0.0645\,\pm\,0.0022$	$0.0589\,\pm\,0.0019$	$0.0610\,\pm\,0.0022$
Score MSE	$0.2329\,\pm\,0.0102$	$\mathbf{0.1243\,\pm\,0.0079}$	$0.2182\,\pm\,0.0122$	$0.1801\,\pm\,0.0090$
Log-score RMSE	$0.1897\,\pm\,0.0015$	$\mathbf{0.1519\,\pm\,0.0024}$	$0.2429\,\pm\,0.0077$	$0.2053\,\pm\,0.0034$

Table A.3: Additional metrics at

n=8192

K=256

and, for sample metrics,

N=256

. Sample-based quantities use

\tau

-leaping; the four joint discrepancies use the low-dimensional coordinate-splitting law. Entries are mean

\pm

SE; bold denotes the smallest mean for accuracy metrics. Observation-level DSE SD is descriptive and is not ranked.

Method	Edge TV difference	MMD 2 difference $\times 10^{3}$
Smaller Potts chain
LSE	$0.0385\;[0.0274,\,0.0497]$	$4.406\;[3.825,\,4.988]$
Conv	$-0.0253\;[-0.0385,\,-0.0120]$	$-0.160\;[-1.076,\,0.756]$
Butterfly	$0.0272\;[0.0087,\,0.0457]$	$1.203\;[-0.281,\,2.686]$
Smaller Ising ladder
LSE	$0.0018\;[-0.0046,\,0.0082]$	$0.092\;[-0.226,\,0.410]$

Table A.4: Paired differences from MLP for

\tau

-leaping at

n=8192

K=N=256

: mean difference [pointwise 95% interval]. Negative values favor the shared model. MMD-squared differences are multiplied by

10^{3}

Example	Joint TV	Edge TV	MMD ${}^{2}\times 10^{3}$	$W_{1}(H)$
Small Potts chain	$0.000145$	$0.0432\,\pm\,0.0021$	$0.153\,\pm\,0.222$	$0.1208\,\pm\,0.0213$
Small Ising ladder	$0.001001$	$0.0286\,\pm\,0.0014$	$-0.118\,\pm\,0.130$	$0.0703\,\pm\,0.0095$
Small Categorical tree	$0.000375$	$0.0484\,\pm\,0.0025$	$-0.002\,\pm\,0.204$	$0.0723\,\pm\,0.0058$
Large Potts chain	—	$0.0425\,\pm\,0.0015$	$-0.120\,\pm\,0.082$	$0.2883\,\pm\,0.0281$
Large Ising ladder	—	$0.0269\,\pm\,0.0013$	$0.160\,\pm\,0.181$	$0.1502\,\pm\,0.0208$
Large Categorical tree	—	$0.0496\,\pm\,0.0010$	$-0.067\,\pm\,0.053$	$0.1968\,\pm\,0.0253$

Table A.5: Oracle-score evaluation at

N=256

, using the

n=8192

records. Joint TV is evaluated on the full coordinate-splitting law and is available only for the smaller examples. All other columns use

\tau

-leaping, with 512 generated observations, 8192 reference observations for edge TV and energy

W_{1}

, and 512 reference observations for MMD. Sample-based entries are mean

\pm

SE across ten repetitions; deterministic joint TV is shown without SE.

Fig A.1: Normalized score risk versus sample size, with

K=256

. Error bars are SE across ten repetitions. Panels have separate vertical scales.

Fig A.2: Unbiased squared Hamming MMD versus sample size, with

K=N=256

. Both dimensions use

\tau

-leaping at

n\in\{2048,8192\}

. Error bars are SE across ten repetitions; negative estimates are retained.

Fig A.3: Unbiased squared Hamming MMD versus the training-grid size

K

, with

n=8192

and

N=256

. Both dimensions use

\tau

-leaping. Every branch has the same refinement budget. Error bars are SE.

Fig A.4: Sampling-grid refinement for the smaller examples, with

n=8192

K=256

, using

\tau

-leaping. Top: squared MMD from 512 observations per distribution. Bottom: mean edge TV from 512 generated and 8192 reference observations. Error bars are SE; dashed curves use the exact score in the same

\tau

-leaping sampler.

Fig A.5: Supplementary MMD curves for the original low-dimensional coordinate-splitting sampler, with

K=N=256

and

n\in\{128,512,2048,8192\}

. Each MMD estimate uses 512 observations from each distribution. Error bars are SE across ten repetitions.

Explore similar work

Feb 16, 2026cs.LG

Efficient Sampling with Discrete Diffusion Models: Sharp and Adaptive Guarantees

Diffusion models over discrete spaces have recently shown striking empirical success, yet their theoretical foundations remain incomplete. In this paper, we study the sampling efficiency of score-based discrete diffusion models under a continuous-time Markov chain (CTMC) formulation, with a focus on

τ

-leaping-based samplers. We establish sharp convergence guarantees for attaining

\varepsilon

accuracy in Kullback-Leibler (KL) divergence for both uniform and masking noising processes. For uniform discrete diffusion, we show that the

τ

-leaping algorithm achieves an iteration complexity of order

\tilde O(d/\varepsilon)

, with

d

the ambient dimension of the target distribution, eliminating linear dependence on the vocabulary size

S

and improving existing bounds by a factor of

d

; moreover, we establish a matching algorithmic lower bound showing that linear dependence on the ambient dimension is unavoidable in general. For masking discrete diffusion, we introduce a modified

τ

-leaping sampler whose convergence rate is governed by an intrinsic information-theoretic quantity, termed the effective total correlation, which is bounded by

d \log S

but can be sublinear or even constant for structured data. As a consequence, the sampler provably adapts to low-dimensional structure without prior knowledge or algorithmic modification, yielding sublinear convergence rates for various practical examples (such as hidden Markov models, image data, and random graphs). Our analysis requires no boundedness or smoothness assumptions on the score estimator beyond control of the score entropy loss.

Daniil Dmitriev, Zhihan Huang, Yuting Wei

Department of Statistics and Data Science, the Wharton School, University of Pennsylvania

Score-Based Diffusion Model Diffusion Dynamics Diffusion Models Markov

Ask PDF

Apr 12, 2026cs.LG

Query Lower Bounds for Diffusion Sampling

Diffusion models generate samples by iteratively querying learned score estimates. A rapidly growing literature focuses on accelerating sampling by minimizing the number of score evaluations, yet the information-theoretic limits of such acceleration remain unclear. In this work, we establish the first score query lower bounds for diffusion sampling. We prove that for

d

-dimensional distributions, given access to score estimates with polynomial accuracy

\varepsilon=d^{-O(1)}

(in any

L^p

sense), any sampling algorithm requires

\widetildeΩ(\sqrt{d})

adaptive score queries. In particular, our proof shows that, within any polynomial total-query budget, successful sampling requires searching over

\widetildeΩ(\sqrt{d})

distinct noise levels, providing a formal explanation for why multiscale noise schedules are necessary in practice.

Zhiyang Xun, Eric Price

UT Austin

Diffusion Sampling Optimal Sample Complexity Uncertainty Score Lower Bounds Information-Theoretic Limits Queries+1

Ask PDF

Jul 25, 2026cs.LG

From Score Learning to Discretized Sampling: An End-to-End Generalization Analysis of Diffusion Models

Despite the empirical success of score-based diffusion models, a complete theoretical understanding of how finite-sample learning, network parameterization, and numerical discretization jointly dictate generative quality remains underdeveloped. Existing sampling analyses often evaluate the generative performance conditional on an oracle score or a pre-specified error threshold. In this work, we establish a unified convergence and generalization framework for score-based diffusion models parameterized by practical ResNet-type architectures. We analyze the generalization and convergence properties from the practical finite-sample, discrete-time learning problem of the score function to the ideal continuous-time, population-level objective. Based on the generalization result of the learning problem of score function, we analyze the sampling process induced by the learned score function and provide an end-to-end total variation distance estimate for the generated terminal distribution. This estimate explicitly decomposes the overall generative error into four interpretable components: the truncation error of the forward process, the reverse-time discretization error, the generalization error incorporating both finite data and forward-time discretization, and the training optimization gap. Our results quantitatively characterize how the training sample size, temporal discretization grids, and optimization accuracy jointly control the final fidelity of samples generated by diffusion models.

Jinshu Huang, Yiming Jiang, Chunlin Wu

School of Mathematical Sciences, Nankai University, Tianjin, China

Score-Based Diffusion Model Diffusion Models Time Discretization Convergence Learning-Augmented Algorithms

Ask PDF