Despite the widespread use and success of generative AI techniques today, theoretical guarantees on learning a distribution supported in d dimensions from n samples degrade as O(n−1/Θ(d)), though shown to be minimax optimal. We hypothesize that present bounds are too pessimistic because smoothness assumptions are not enough to capture the structure of distributions that often appear in real applications. Consequently, we introduce the class of sparse priors and define the "Sparse Dimension" as a measure of sparsity of a prior over the space of all distributions. We show that distribution learning under a k-sparse prior achieves a Bayesian risk lower bound of Ω(k/n) under common distance metrics, and show a matching (up to logarithmic terms asymptotically in n,k) upper bound for the TV distance under mild additional assumptions. We show the statistical equivalence of distribution learning and learning to sample in the Bayesian setting so that our results apply to learning to sample as well. While k can still depend on the dimension d, or a notion of intrinsic dimension, our results show that learning under an appropriate prior overcomes the curse of dimensionality with respect to the dependence on n.
Figures & tables
Figure 1: The standard Gaussian illustrated with a small perturbation of it, of the type common information theoretic lower bounds often consider. The perturbations are small enough that it would take an increasing number of samples to distinguish them as the dimensionality increases. In our framework however, we argue that such small perturbations likely receive small prior mass in realistic scenarios, which relaxes the sample complexity requirement for identifying the more likely distribution.
Statistical learning theory studies when data-driven algorithms generalize, how many samples they need, and what statistical or computational limits apply.
We show that every class of distributions that is learnable up to arbitrarily small target error in total variation distance with finitely many samples is also learnable under (ε,δ)-differential privacy up to arbitrarily small target error with finitely many samples. This proves a conjecture of Ashtiani. Previous work by Bun, Kamath, Mouzakis, and Singhal [arXiv:2402.00267] gave a weak refutation of this conjecture, showing that this implication is not true when learnability is defined with respect to a fixed target error. In contrast, we show that, under the standard definition of learnability, the conjecture is true.
Mohammad Afzali, Hassan Ashtiani, Alex Bie +4
University of British Columbia. · McMaster University and Vector Institute. · Google Research. +4
We propose a general framework for non-interactive locally differentially private (LDP) learning of structured univariate distributions that can be approximated by piece-wise polynomials. This gives the first sample-efficient LDP learners for several distribution classes, including mixtures of log-concave distributions, such as Gaussian mixture models (GMMs). These learners also provide agnostic guarantees and are computationally efficient. We also prove a lower bound for learning GMMs under LDP, improving on the standard pure-DP packing lower bounds of Bun et al. [BKSW19]. To obtain our general learning framework, we develop an efficient non-interactive LDP algorithm for synthetic data generation over large domains, which may be of independent interest. We then use it together with a deterministic adaptation of the non-private piecewise polynomial learner of Acharya et al. [ADLS17].
Mohammad Afzali, Hassan Ashtiani, Sivan Sabato
University of British Columbia · McMaster University · Vector Institute +1
Discrete diffusion models have emerged as a practically successful framework for generative modeling on discrete product spaces, yet their statistical generalization properties remain poorly understood. Discrete real-world data such as text or biological sequences often concentrate on a small fraction of the astronomically large ambient space because of semantic or physical constraints, but existing bounds fail to capture this distributional structure and instead scale with the size of the ambient space, giving rise to almost vacuous error bounds. We address this gap for uniform discrete diffusion, one of the two dominant discrete diffusion paradigms alongside masking diffusion, by deriving statistical guarantees governed by the effective support size sn(P0), a sample-size-dependent measure of distributional complexity. Given n independent and identically distributed (i.i.d.) samples from an unknown data distribution P0 on [K]d, we show that, with appropriate choices of network size and hyperparameters, the expected total variation (TV) loss scales as O(sn(P0)/n), while the expected Kullback--Leibler (KL) divergence is bounded by O(n1sn(P0)log(eKd/sn(P0))logn). Furthermore, we show that the TV rate is minimax optimal and that the KL rate is minimax optimal up to a factor of logn. Together, these upper and lower bounds show that uniform discrete diffusion successfully avoids the curse of dimensionality for distributions with small effective support size: the TV error rate depends on the ambient state-space size only through sn(P0), while the corresponding KL rate incurs only an additional logarithmic dependence on the ambient state-space size.