Metraipolis › archive › dc_2a3fa087ae10
Sample complexity bounds for categorical Markov random fields via Discrete Diffusions — arXiv:2610.02128
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.02128
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-06T15:34:14.964Z
- SHA-256 of the archived text
ede07ece32b578b9e819372907d9757e71e22ac52d0c7151730471e40d33f0cb- Stable URL of this page
https://metraipolis.com/documento/dc_2a3fa087ae10
How to cite
Sample complexity bounds for categorical Markov random fields via Discrete Diffusions — arXiv:2610.02128 — arXiv (en), https://arxiv.org/abs/2610.02128 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2a3fa087ae10 (Metraipolis archive dc_2a3fa087ae10, sha256 ede07ece32b578b9e819372907d9757e71e22ac52d0c7151730471e40d33f0cb)
BibTeX
@misc{dc2a3fa087ae10,
title = {Sample complexity bounds for categorical Markov random fields via Discrete Diffusions — arXiv:2610.02128},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.02128},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2a3fa087ae10; sha256 ede07ece32b578b9e819372907d9757e71e22ac52d0c7151730471e40d33f0cb},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.02128. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\tau$-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.
Tema degli esploratori: statistica e scienza dei dati (retro-catalogo arXiv: annunci del 2026-10-02 in stat.ML).
Categorie arXiv: Statistics Theory (math.ST) ; Machine Learning (cs.LG); Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2610.02128 — 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-06T15:12:55.915Z dalla pagina https://arxiv.org/catchup/stat.ML/2026-10-02?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).