Minimax Optimality of Score-Entropy Discrete Diffusion

• URL: http://arxiv.org/abs/2608.20635v1
• Date: Fri, 21 Aug 2026 00:16:00 GMT
• Title: Minimax Optimality of Score-Entropy Discrete Diffusion
• Abstract summary: We investigate the fundamental statistical limits of concrete score estimation.<n>We propose an MLE-based thresholding estimator that matches a lower bound under the score-entropy loss.<n>We show that, for any target distribution, this density ratio is naturally controlled under both uniform and masking discrete diffusion models.
• Score: 4.831510571088151
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Discrete diffusion models have demonstrated strong performance across a range of datasets, including natural language data and graph-structured data. Among many variants, score-entropy discrete diffusion (SEDD) has achieved particularly strong empirical results. In SEDD, new samples are generated by iteratively evaluating a sequence of concrete score functions, which are learned by minimizing a score-entropy loss. While much of the prior theoretical literature on discrete diffusion has focused on the sampling efficiency of SEDD under the assumption of small score estimation error, recent work has begun to investigate the finite-sample properties of score estimation itself. In this work, we take a different route by investigating the fundamental statistical limits of concrete score estimation. We focus on uniform and masking discrete diffusions, two of the most widely adopted discrete diffusion models. We establish a minimax lower bound under the score-entropy loss, and propose an MLE-based thresholding estimator that matches this lower bound up to constant and polylogarithmic factors that depend on neighboring density ratios. We further show that, for any target distribution, this density ratio is naturally controlled under both uniform and masking discrete diffusion models, yielding nearly matching minimax lower and upper bounds for the aggregated score estimation error. Our results imply that, with appropriate initialization and discretization, SEDD can achieve nearly optimal minimax sample complexity, as measured by the KL divergence between the target and generated distributions.

Related papers

• From Scores to Gibbs Correctors: Accelerating Uniform-Rate Discrete Diffusion Models [58.02657021435213]
  We propose a novel Gibbs-based corrector for discrete diffusion models, termed Gibbs-Accelerated Discrete Diffusion (GADD)<n>We show GADD achieves an overall sampling complexity of $mathcalO(mathrmpolylog (varepsilon-1)$, yielding the first such rate for diffusion-based samplers for uniform-rate discrete diffusion models.
  arXiv  Detail & Related papers  (2026-05-26T17:52:28Z)
• Diffusion Models with Heavy-Tailed Targets: Score Estimation and Sampling Guarantees [8.437829850850358]
  We study score-based diffusion models when the target distribution is heavy-tailed.<n>We derive sharp minimax rates for score estimation, revealing a dichotomy.<n>In total variation, the distribution generated at the minimax optimal rate $n-/(2+d)$, and at a $$-dependent rate under exponential tails.
  arXiv  Detail & Related papers  (2026-01-10T23:05:25Z)
• Dimension-free error estimate for diffusion model and optimal scheduling [22.20348860913421]
  Diffusion generative models have emerged as powerful tools for producing synthetic data from an empirically observed distribution.<n>Previous analyses have quantified the error between the generated and the true data distributions in terms of Wasserstein distance or Kullback-Leibler divergence.<n>In this work, we derive an explicit, dimension-free bound on the discrepancy between the generated and the true data distributions.
  arXiv  Detail & Related papers  (2025-12-01T15:58:20Z)
• Minimax Optimality of the Probability Flow ODE for Diffusion Models [8.15094483029656]
  This work develops the first end-to-end theoretical framework for deterministic ODE-based samplers.<n>We propose a smooth regularized score estimator that simultaneously controls both the $L2$ score error and the associated mean Jacobian error.<n>We demonstrate that the resulting sampler achieves the minimax rate in total variation distance, modulo logarithmic factors.
  arXiv  Detail & Related papers  (2025-03-12T17:51:29Z)
• Theory on Score-Mismatched Diffusion Models and Zero-Shot Conditional Samplers [49.97755400231656]
  We present the first performance guarantee with explicit dimensional dependencies for general score-mismatched diffusion samplers.<n>We show that score mismatches result in an distributional bias between the target and sampling distributions, proportional to the accumulated mismatch between the target and training distributions.<n>This result can be directly applied to zero-shot conditional samplers for any conditional model, irrespective of measurement noise.
  arXiv  Detail & Related papers  (2024-10-17T16:42:12Z)
• 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)
• O(d/T) Convergence Theory for Diffusion Probabilistic Models under Minimal Assumptions [6.76974373198208]
  We establish a fast convergence theory for the denoising diffusion probabilistic model (DDPM) under minimal assumptions.<n>We show that the convergence rate improves to $O(k/T)$, where $k$ is the intrinsic dimension of the target data distribution.<n>This highlights the ability of DDPM to automatically adapt to unknown low-dimensional structures.
  arXiv  Detail & Related papers  (2024-09-27T17:59:10Z)
• An analysis of the noise schedule for score-based generative models [7.180235086275926]
  Score-based generative models (SGMs) aim at estimating a target data distribution by learning score functions using only noise-perturbed samples from the target.<n>Recent literature has focused extensively on assessing the error between the target and estimated distributions, gauging the generative quality through the Kullback-Leibler (KL) divergence and Wasserstein distances.<n>We establish an upper bound for the KL divergence between the target and the estimated distributions, explicitly depending on any time-dependent noise schedule.
  arXiv  Detail & Related papers  (2024-02-07T08:24:35Z)
• 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)
• Score Approximation, Estimation and Distribution Recovery of Diffusion Models on Low-Dimensional Data [68.62134204367668]
  This paper studies score approximation, estimation, and distribution recovery of diffusion models, when data are supported on an unknown low-dimensional linear subspace. We show that with a properly chosen neural network architecture, the score function can be both accurately approximated and efficiently estimated. The generated distribution based on the estimated score function captures the data geometric structures and converges to a close vicinity of the data distribution.
  arXiv  Detail & Related papers  (2023-02-14T17:02:35Z)
• Minimax Optimal Estimation of KL Divergence for Continuous Distributions [56.29748742084386]
  Esting Kullback-Leibler divergence from identical and independently distributed samples is an important problem in various domains. One simple and effective estimator is based on the k nearest neighbor between these samples.
  arXiv  Detail & Related papers  (2020-02-26T16:37:37Z)

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.