Skip to content

Sample complexity bounds for categorical Markov random fields via Discrete Diffusions

Oct 2026 · 0 citations
Mathematics Computer Science

TL;DR

This work studies 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, and trains a single score network across uniform noise levels while leaving the sampling discretization to be chosen at inference-time.

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 $\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.

View source

Similar papers

#machine learning Preprint Oct 2026

Uniform Discrete Diffusion Models are Minimax Optimal for Estimating Distributions with Small Effective Support Size

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...

D.-H. Yoon, Saptarshi Chakraborty · 0 citations

Information Estimation with Discrete Diffusion

Information-theoretic measures, such as Mutual Information (MI), play a crucial role in understanding non-linear relationships between random variables and are widely used across scientific disciplines. Yet, their use on real-world discrete data remains challenging. Existing methods typically rely on embedding discrete...

Alberto Foresti, Giulio Franzese, P. Michiardi · 3 citations
#machine learning Preprint Oct 2026

Finite-Sample Guarantees for Fully Discrete Conditional Diffusion Models

The approach aligns the score-training objective with the sampling grid, allowing statistical estimation and numerical discretization errors to be analyzed together, and establishes finite-sample guarantees for conditional diffusion models learned from data and implemented with finitely many denoising steps.

Qiu-Yun Zhu · 0 citations
#machine learning Preprint Oct 2026

Diffusion Removes Langevin's Conditioning Dependence: A Sharp Gaussian Analysis

Despite their empirical success, why diffusion models overcome the bottlenecks of classical score-based samplers remains unclear. In this work, we leverage Gaussian distributions to isolate this phenomenon. We establish 2-Wasserstein convergence bounds for optimized hyperparameters, showing that diffusion processes ach...

Adam Perbost, F. Bach, Pierre Marion · 0 citations
Preprint Nov 2026

Finite-Time Online Sample Complexity for Conditional Diffusion Models

We study the finite-time training and sampling error of conditional diffusion models trained by online stochastic-gradient denoising score matching. Rather than assuming access to an exact empirical or population risk minimizer, we analyze the score network produced after a finite number of stochastic-gradient updates...

Mudit Gaur, Prashant Trivedi, Sasidhar Kunapuli et al. · 0 citations
Preprint Sep 2026

Second-order perturbation bounds for Gibbs samplers under strong spatial mixing

The basic question in perturbation analysis of Markov chains is how small changes in their transition kernels affect their stationary distributions. Classical perturbation bounds typically require the kernel error to be much smaller than $1/\tau$, where $\tau$ is a mixing or relaxation time. Although this scaling is sh...

Na Lin, Aaron Smith, Yi-Qiang Q. Zhao · 0 citations

Related blog posts

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.