- Rating
- 4(+1)
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies the sample complexity of estimating a discrete distribution supported on with uniform discrete diffusion model, where the effective support size serves as a distribution-dependent measure of the problem complexity. For fixed-grid samplers satisfying a standard assumption on the entropy loss used for training the discrete diffusion model, the authors obtain an expected TV rate of magnitude and an expected KL rate of magnitude . (Almost) matching minimax lower bounds are also provided to show optimality of uniform discrete diffusion models in terms of both TV and KL divergences (up to a negligible factor). The paper also gives an exact one-step empirical reverse sampler and controlled SEDD experiments to support interpretation of the effective-support size.
Critical strengths
Firstly, the reviewer finds the statistical theory presented in this paper to fairly strong and rigorous. The formulation based on the effective support size provides substantially sharper guarantees than bounds based on ambient state-space and yields almost matching minimax rates in terms of both TV and KL. I particularly appreciate that the results recover the classical unrestricted rates under the regime , where the effective support saturates but remains informative. Secondly, results in terms of the KL divergence gives a useful interpretation of discrete diffusion model's generalization capability. The exact one-step construction in the appendix also turns out to be useful as it separates the statistical phenomenon from the unfavorable complexity caused by the fixed-grid implementation.
Critical weaknesses
The first weakness is that the statistical guarantee presented in the paper seems to be derived by the approximation of the empirical diffusion process rather than the generalization property of a realistically trained score network. Specifically, the proof constructs a sufficiently expressive ReLU class that approximates the discrete score function associated with the empirical distribution. The resulting sampler is then compared against the forward empirical measure smoothed by early stopping. This is valid statistically, but it makes the headline statement that ``uniform discrete diffusion models are minimax optimal'' a little bit stronger.
Secondly, the KL fixed-grid construction is not computationally meaningful in high dimension, and the experiment only validates the theory in an indirect way. As the authors describe in the paper, the explicit KL instantiation requires network width/sparsity and a number of sampling steps with exponential dependence on . Appendix D shows that this is not intrinsic to the statistical rate, but it limits the practical interpretation of the fixed-grid result. Empirically, the lower-temperature teacher distributions plausibly have smaller effective support and are learned more accurately, but the experiment does not report or , nor test the predicted dependence of error on the effective support size directly.
Questions for authors
-
For the exponential dependence on the dimension in the fixed-grid KL case, is the construction primarily an artifact of the KL comparison argument, or is there a plausible route to a guarantee of polynomial complexity in terms of ? The efficient one-step construction suggests that the such exponential dependence on may be an upper bound that is too loose.
-
Would it be possible for the authors to report the number of distinct observations or an estimate for the parameter for each population and training-set size in the experiments? This would make the empirical study connect more directly to the theory.
3 comments
Response
The reviewer thanks the authors for the detailed response, which has addressed most of the reviewer's concerns. Hence, the reviewer would be glad to increase the rating from 3 to 4.
Dear reviewer,
Thank you for your support for our paper. We have uploaded a revised version of our manuscript, which includes the promised synthetic experiment that validates our theory (Section 4.1), and also the effective support size table for the TinyStories experiment (Section 4.2). We have also clarified that sampling and network complexity are sufficient conditions for the statistical guarantee ("Interpretation" paragraphs in Sections 3.1&3.2). Please let us know if you have any remaining questions or concerns. We would be happy to provide further clarification.
We sincerely thank the reviewer for recognizing the statistical significance of our effective-support framework and the usefulness of our one-step sampler, as well as for their constructive suggestions. These motivated additional empirical evaluations, including a controlled synthetic experiment whose pilot results support our theory.
Weakness 1
Our main contribution is a finite-sample analysis connecting empirical score-entropy minimization, neural score approximation, and reverse sampling to minimax TV and near-minimax KL guarantees for uniform diffusion. Classical optimal estimators do not imply these guarantees for diffusion models. Our rates depend on sn(P0) and can remain informative when n≪Kd, where ambient-cardinality-based bounds become vacuous. The empirical distribution and its forward-smoothed counterpart serve as intermediate estimators, rather than constituting our main contribution.
Our results hold under explicit sufficient conditions on the network class, optimization error, and sampler, rather than claiming unconditional optimality for practically trained networks. Nevertheless, the synthetic pilot described under Question 2 provides preliminary evidence that trained SEDD follows the theoretical rate. We will clarify the scope of our guarantees in the final draft.
Weakness 2 and Question 1
The exponential architecture, optimization-precision, and sampling-step requirements of our fixed-grid KL theorem are conservative worst-case sufficient conditions, not computational lower bounds. Unlike TV, KL lacks a triangle inequality; transferring sampler accuracy relative to the early-stopped empirical distribution into population KL uses the uniform density floor ((1−e−1/n)/K)d≍(Kn)−d. This leads to exponentially stringent requirements, which have not been established as intrinsic limitations of uniform discrete diffusion under KL loss. Regarding Question 1, our current KL-transfer argument does not establish the near-minimax KL guarantee under polynomially small optimization error, and we could not find a way to remove this exponential dependence. Developing an alternative analysis that achieves comparable guarantees for learned-score samplers under polynomial requirements remains an important open problem.
Question 2
As requested, we report sn(P0)/n and Dn/n in our TinyStories experiment. Each cell gives (sn(P0)/n, Dn/n), both as percentages.
Lower temperatures yield smaller effective support sizes at fixed n, while Dn/n closely tracks sn(P0)/n, supporting the role of effective support in our statistical analysis.
Furthermore, we have completed a controlled synthetic pilot with K=4,d=5, three Zipfian populations (α∈{1.5,2,3}), and an exponential population (λ=0.1), varying n from 64 to 65,536. The small state space permits direct population TV and KL evaluation. Across all four scenarios, the observed TV and KL errors of trained SEDD exhibit convergence behavior closely matching the theoretical rate curves, providing strong preliminary empirical evidence for our guarantees. We are currently conducting the full experiment and will add a dedicated subsection with the complete results and rate comparisons to the final draft.