Discrete State Diffusion Models: A Sample Complexity Perspective

• URL: http://arxiv.org/abs/2510.10854v1
• Date: Sun, 12 Oct 2025 23:33:46 GMT
• Title: Discrete State Diffusion Models: A Sample Complexity Perspective
• Authors: Aadithya Srikanth, Mudit Gaur, Vaneet Aggarwal,
• Abstract summary: We present a principled theoretical framework for discrete-state diffusion, providing the first sample complexity bound of $widetildemathcalO(epsilon-2)$.<n>Our structured decomposition of the score estimation error into statistical, approximation, optimization, and clipping components offers critical insights into how discrete-state models can be trained efficiently.
• Score: 43.61958734990224
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Diffusion models have demonstrated remarkable performance in generating high-dimensional samples across domains such as vision, language, and the sciences. Although continuous-state diffusion models have been extensively studied both empirically and theoretically, discrete-state diffusion models, essential for applications involving text, sequences, and combinatorial structures, remain significantly less understood from a theoretical standpoint. In particular, all existing analyses of discrete-state models assume score estimation error bounds without studying sample complexity results. In this work, we present a principled theoretical framework for discrete-state diffusion, providing the first sample complexity bound of $\widetilde{\mathcal{O}}(\epsilon^{-2})$. Our structured decomposition of the score estimation error into statistical, approximation, optimization, and clipping components offers critical insights into how discrete-state models can be trained efficiently. This analysis addresses a fundamental gap in the literature and establishes the theoretical tractability and practical relevance of discrete-state diffusion models.

Related papers

• Improved Sample Complexity For Diffusion Model Training Without Empirical Risk Minimizer Access [47.96419637803502]
  We present a principled theoretical framework analyzing diffusion models, providing a state-of-the-art sample complexity bound to $widetildemathcalO(epsilon-4)$.<n>Our structured decomposition of the score estimation error into statistical and optimization components offers critical insights into how diffusion models can be trained efficiently.
  arXiv  Detail & Related papers  (2025-05-23T20:02:15Z)
• Overcoming Dimensional Factorization Limits in Discrete Diffusion Models through Quantum Joint Distribution Learning [79.65014491424151]
  We propose a quantum Discrete Denoising Diffusion Probabilistic Model (QD3PM)<n>It enables joint probability learning through diffusion and denoising in exponentially large Hilbert spaces.<n>This paper establishes a new theoretical paradigm in generative models by leveraging the quantum advantage in joint distribution learning.
  arXiv  Detail & Related papers  (2025-05-08T11:48:21Z)
• How Discrete and Continuous Diffusion Meet: Comprehensive Analysis of Discrete Diffusion Models via a Stochastic Integral Framework [11.71206628091551]
  We propose a comprehensive framework for the error analysis of discrete diffusion models based on L'evy-type integrals.<n>Our framework unifies and strengthens the current theoretical results on discrete diffusion models.
  arXiv  Detail & Related papers  (2024-10-04T16:59:29Z)
• Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis [56.442307356162864]
  We study the theoretical aspects of score-based discrete diffusion models under the Continuous Time Markov Chain (CTMC) framework.<n>We introduce a discrete-time sampling algorithm in the general state space $[S]d$ that utilizes score estimators at predefined time points.<n>Our convergence analysis employs a Girsanov-based method and establishes key properties of the discrete score function.
  arXiv  Detail & Related papers  (2024-10-03T09:07:13Z)
• Unveil Conditional Diffusion Models with Classifier-free Guidance: A Sharp Statistical Theory [87.00653989457834]
  Conditional diffusion models serve as the foundation of modern image synthesis and find extensive application in fields like computational biology and reinforcement learning. Despite the empirical success, theory of conditional diffusion models is largely missing. This paper bridges the gap by presenting a sharp statistical theory of distribution estimation using conditional diffusion models.
  arXiv  Detail & Related papers  (2024-03-18T17:08:24Z)
• On the Generalization Properties of Diffusion Models [31.067038651873126]
  This work embarks on a comprehensive theoretical exploration of the generalization attributes of diffusion models.<n>We establish theoretical estimates of the generalization gap that evolves in tandem with the training dynamics of score-based diffusion models.<n>We extend our quantitative analysis to a data-dependent scenario, wherein target distributions are portrayed as a succession of densities.
  arXiv  Detail & Related papers  (2023-11-03T09:20:20Z)
• Diffusion Models are Minimax Optimal Distribution Estimators [49.47503258639454]
  We provide the first rigorous analysis on approximation and generalization abilities of diffusion modeling. We show that when the true density function belongs to the Besov space and the empirical score matching loss is properly minimized, the generated data distribution achieves the nearly minimax optimal estimation rates.
  arXiv  Detail & Related papers  (2023-03-03T11:31:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.