arXiv：cs.LG· Dongsun Yoon, Saptarshi Chakraborty·· 4 小时前AI 评分34
均匀离散扩散模型在有效支撑集较小时达到分布估计的极小极大最优
Uniform Discrete Diffusion Models are Minimax Optimal for Estimating Distributions with Small Effective Support Size
AI 导读
研究证明均匀离散扩散模型在估计有效支撑集较小的分布时达到极小极大最优。在 [K]^d 上 n 个 i.i.d. 样本下，期望 TV 损失以 O(√(s_n(P_0)/n)) 缩放，KL 散度上界为 O((1/n)s_n(P_0)log(eK^d/s_n(P_0))log n)，其中 s_n(P_0) 为有效支撑集大小。
正文
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 $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(\sqrt{s_n(P_0)/n})$, while the expected Kullback--Leibler (KL) divergence is bounded by $O(\frac{1}{n}s_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.
| Subjects: | Machine Learning (stat.ML); Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.07655 [stat.ML] |
| (or arXiv:2610.07655v1 [stat.ML] for this version) | |
| https://doi.org/10.48550/arXiv.2610.07655 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Dongsun Yoon [view email]
[v1]
Tue, 6 Oct 2026 02:50:13 UTC (55 KB)
来源：arXiv：cs.LG · arxiv.org