Paper Proposes Sparse Priors To Cut Sample Needs In Distribution Learning

Standard theory on learning a probability distribution from samples has long carried a discouraging rate: as the number of dimensions d grows, the error shrinks only as n raised to the power of minus one over roughly d, a rate the authors describe as minimax optimal under the usual smoothness assumptions. That rate is the reason distribution learning in high dimensions is treated as fundamentally hard, and it sits behind the intuition that generative models need exponentially more data as their output space grows richer.

Goyal and Poczos argue the pessimism comes from the assumption itself rather than from the problem. Real distributions used in practice, they write, often carry more structure than a smoothness bound can see. To capture that structure they define a class of sparse priors and a quantity called the Sparse Dimension, a measure of how sparse a prior is across the space of possible distributions. Under a k sparse prior, they show a Bayesian risk lower bound of order the square root of k over n under common distance metrics, and a matching upper bound for total variation distance up to logarithmic terms, under mild extra conditions. Because k can be far smaller than d, the bound removes the exponential dependence on dimension that the classical result carries.

The paper also shows that learning a distribution and learning to sample from it are statistically equivalent in this Bayesian setting, so the same result covers models built to generate samples rather than to estimate density directly, which is the mode most deployed generative systems actually use.

The numbers

• The classical minimax rate for distribution learning in d dimensions degrades as n to the power of minus one over a quantity that grows with d, the pessimistic baseline the paper argues against.
• Under a k sparse prior, the paper’s Bayesian risk bound is of order the square root of k over n, a rate that does not grow worse with dimension the way the classical bound does.
• The upper bound for total variation distance matches the lower bound up to logarithmic factors in n and k, under the paper’s stated mild assumptions.

The result is theoretical, with no benchmark or released model attached, but it speaks directly to a question every vendor training generative systems faces: how much data is enough. If real world distributions are closer to sparse than to merely smooth, as the authors hypothesize, then sample requirements could scale with a hidden sparse dimension rather than with the raw dimensionality of the output space, a distinction that matters for anyone deciding how much training data a given accuracy target actually needs.