Discrete diffusion models adapt efficiently to sparse categorical data
Discrete Diffusion Models are Minimax Optimal Under Sparsity
Machine Learning
Summary
Generating text and other data with many categories is challenging, especially when the data has underlying simple patterns. The paper shows that a type of model called discrete diffusion models can automatically adapt to such simplicity—or sparsity—without needing to know how simple the data is beforehand. The authors mathematically prove that their approach achieves the best possible accuracy in this sparse setting. This means these models work well not just in practice but also have solid theoretical guarantees.
What this means in practice
- •For natural language engineers: Build more statistically efficient text generation systems that automatically adapt to sparse data patterns without tuning sparsity parameters.
- •For data compression teams: Design improved categorical data compression algorithms using discrete diffusion models that adapt to underlying sparsity without prior data knowledge.
A theory result. No direct application yet.
Authors
Luca Blunda, Tyler Farghly, Umut Simsekli, Alain Durmus
Abstract
Discrete diffusion models have emerged as a leading alternative to autoregressive models for generating text and other categorical data, yet their theoretical foundations remain less developed than those of their continuous counterparts. For continuous diffusion models, a prominent line of theory suggests that these models can adapt to low-dimensional structure in the data, thereby improving statistical efficiency and generalization. In this work, we investigate the discrete analogue of this phenomenon by studying the statistical rates of discrete diffusion models under sparsity assumptions. By analyzing a nonparametric estimator derived from a regularized score-entropy objective, we establish minimax-optimal rates in the sparse regime. The proposed regularization can be viewed as an adaptation of label smoothing techniques introduced for classification, and does not require the knowledge of the sparsity parameter. This shows that discrete diffusion models can adapt intrinsically to sparsity.