Uniform Discrete Diffusion Models are Minimax Optimal for Estimating Distributions with Small Effective Support Size
Abstract
Discrete diffusion models have emerged as a practically successful framework for generative modeling on discrete product spaces, yet their statistical generalization properties remain poorly understood. Discrete real-world data such as text or biological sequences often concentrate on a small fraction of the astronomically large ambient space because of semantic or physical constraints, but existing bounds fail to capture this distributional structure and instead scale with the size of the ambient space, giving rise to almost vacuous error bounds. We address this gap for uniform discrete diffusion, one of the two dominant discrete diffusion paradigms alongside masking diffusion, by deriving statistical guarantees governed by the effective support size sn(P0), a sample-size-dependent measure of distributional complexity. Given n independent and identically distributed (i.i.d.) samples from an unknown data distribution P0 on [K]d, we show that, with appropriate choices of network size and hyperparameters, the expected total variation (TV) loss scales as O(√(sn(P0)/n)), while the expected Kullback--Leibler (KL) divergence is bounded by O(1/nsn(P0)log(eKd/sn(P0))log n). Furthermore, we show that the TV rate is minimax optimal and that the KL rate is minimax optimal up to a factor of log n. Together, these upper and lower bounds show that uniform discrete diffusion successfully avoids the curse of dimensionality for distributions with small effective support size: the TV error rate depends on the ambient state-space size only through sn(P0), while the corresponding KL rate incurs only an additional logarithmic dependence on the ambient state-space size.
Related
- Synchronization in Probability of Reaction–Diffusion Neural Networks Under Stochastic Sampling Governed by Infinite Discrete Distributions
- From Truncation to Commitment: Persistent Context in Uniform Discrete Diffusion
- Weighted universal Value-at-Risk Superadditivity for discrete distributions
- Tensor network representations of discrete maximum entropy distributions via mean polytopes
- Uniform convergence of canonical discrete uniformization on equilateral approximations
BibTeX
@misc{yoon2026uniform,
title = {{Uniform Discrete Diffusion Models are Minimax Optimal for Estimating Distributions with Small Effective Support Size}},
author = {Dongsun Yoon and Saptarshi Chakraborty},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.07655},
eprint = {2610.07655},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.07655},
}
RIS
TY - UNPB
TI - Uniform Discrete Diffusion Models are Minimax Optimal for Estimating Distributions with Small Effective Support Size
AU - Dongsun Yoon
AU - Saptarshi Chakraborty
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.07655
UR - https://arxiv.org/abs/2610.07655
AB - Discrete diffusion models have emerged as a practically successful framework for generative modeling on discrete product spaces, yet their statistical generalization properties remain poorly understood. Discrete real-world data such as text or biological sequences often concentrate on a small fraction of the astronomically large ambient space because of semantic or physical constraints, but existing bounds fail to capture this distributional structure and instead scale with the size of the ambient space, giving rise to almost vacuous error bounds. We address this gap for uniform discrete diffusion, one of the two dominant discrete diffusion paradigms alongside masking diffusion, by deriving statistical guarantees governed by the effective support size s_n(P_0), a sample-size-dependent measure of distributional complexity. Given n independent and identically distributed (i.i.d.) samples from an unknown data distribution P_0 on [K]^d, we show that, with appropriate choices of network size and hyperparameters, the expected total variation (TV) loss scales as O(√(s_n(P_0)/n)), while the expected Kullback--Leibler (KL) divergence is bounded by O(1/ns_n(P_0)log(eK^d/s_n(P_0))log n). Furthermore, we show that the TV rate is minimax optimal and that the KL rate is minimax optimal up to a factor of log n. Together, these upper and lower bounds show that uniform discrete diffusion successfully avoids the curse of dimensionality for distributions with small effective support size: the TV error rate depends on the ambient state-space size only through s_n(P_0), while the corresponding KL rate incurs only an additional logarithmic dependence on the ambient state-space size.
ER -