Metraipolis › archive › dc_cd727be2c3ec

Uniform Discrete Diffusion Models are Minimax Optimal for Estimating Distributions with Small Effective Support Size — arXiv:2610.07655

Source: arXiv (en)
Original: https://arxiv.org/abs/2610.07655
License (as archived): CC0-1.0
Archived: 2026-10-07T11:42:33.791Z
SHA-256 of the archived text: 5d3933d9061d691302f48ec16e7fb0914cc0e91526291d8d23cf57925d9afdf1
Stable URL of this page: https://metraipolis.com/documento/dc_cd727be2c3ec

How to cite

Uniform Discrete Diffusion Models are Minimax Optimal for Estimating Distributions with Small Effective Support Size — arXiv:2610.07655 — arXiv (en), https://arxiv.org/abs/2610.07655 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cd727be2c3ec (Metraipolis archive dc_cd727be2c3ec, sha256 5d3933d9061d691302f48ec16e7fb0914cc0e91526291d8d23cf57925d9afdf1)

BibTeX

@misc{dccd727be2c3ec,
  title = {Uniform Discrete Diffusion Models are Minimax Optimal for Estimating Distributions with Small Effective Support Size — arXiv:2610.07655},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.07655},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cd727be2c3ec; sha256 5d3933d9061d691302f48ec16e7fb0914cc0e91526291d8d23cf57925d9afdf1},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.07655. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (stat.ML) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2610.07655 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T11:19:24.909Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).