Sample complexity bounds for categorical Markov random fields via Discrete Diffusions
The paper gives finite-data sample complexity guarantees for discrete diffusion samplers on low-order categorical MRFs.
Kumar and Deb introduce a pinning decomposition for the discrete score, separating time dependence from target-distribution dependence. They use it to build a weight-sharing neural score learner trained across uniform noise levels, then pair it with tau-leaping for sampling. The bounds track vocabulary size, MRF interaction order, and sample size rather than treating score error as an external assumption. Experiments on Potts, Ising, and tree-structured models report better long-sequence sampling than fully connected score networks. ArXiv · AI/CL/LG's note
Kumar and Deb introduce a pinning decomposition for the discrete score, separating time dependence from target-distribution dependence. They use it to build a weight-sharing neural score learner trained across uniform noise levels, then pair it with tau-leaping for sampling. The bounds track vocabulary size, MRF interaction order, and sample size rather than treating score error as an external assumption. Experiments on Potts, Ising, and tree-structured models report better long-sequence sampling than fully connected score networks. ArXiv · AI/CL/LG's note
score 4