Dirichlet draws are sparse with high probability

Matus TelgarskyarXiv 2013 · OpenReview

Abstract

This note provides an elementary proof of the folklore fact that draws from a Dirichlet distribution (with parameters less than 1) are typically sparse, meaning most coordinates are small. We show that for a Dirichlet distribution with parameter $\alpha = 1/n$, the number of significant coordinates is bounded by $O(\ln n)$ with high probability.

Introduction

In machine learning applications such as Latent Dirichlet Allocation (LDA) and Bayesian nonparametrics, the Dirichlet distribution is the standard prior for categorical distributions. It is widely recognized that when the concentration parameter $\alpha$ is less than 1, the resulting draws are sparse—the probability mass concentrates on a few coordinates while others remain near zero. Despite being a staple of "folklore," rigorous and simple formal bounds quantifying this sparsity have been surprisingly scarce. This paper fills this gap by providing concrete theorems that bound the number of coordinates exceeding a given threshold $\epsilon$ as the dimensionality $n$ increases.

Methodology

The primary challenge in analyzing Dirichlet draws is the dependency between coordinates (they must sum to 1). To circumvent this, we utilize an alternate representation: a Dirichlet vector $(X_1, \dots, X_n)$ can be constructed by normalizing $n$ independent and identically distributed (i.i.d.) Gamma random variables, $X_i = Y_i / \sum Y_j$.

The proof strategy involves analyzing the properties of the underlying i.i.d. Gamma variables, applying a novel inequality for the Gamma distribution's cumulative distribution function (CDF), and using multiplicative Chernoff bounds to show that both the total sum and the count of variables exceeding a threshold remain within predictable limits.

Empirical Validation

To validate the theoretical bounds, synthetic simulations were conducted. The author sampled 1,000 Dirichlet distributions for various dimensions $n$ (up to 1,000) and parameter choices $\alpha \in \{n^{-1}, n^{-2}\}$.

Simulated counts of coordinates exceeding various thresholds $\epsilon$ for $\alpha = n^{-1}$, normalized by $\ln n$.

As shown in the figure above, when $\alpha = 1/n$, the number of coordinates exceeding a threshold scales logarithmically with $n$, confirming that the $\ln n$ factor in the theoretical bounds is a real phenomenon and not a proof artifact. Furthermore, as the threshold $\epsilon$ decreases (e.g., from $n^{-1}$ to $n^{-4}$), the number of significant coordinates grows linearly.

Simulated counts of coordinates exceeding various thresholds $\epsilon$ for the high-sparsity case $\alpha = n^{-2}$.

In the extreme sparsity case where $\alpha = 1/n^2$ (shown above), the number of significant coordinates remains very small regardless of $n$, often dropping to just one or two as the dimensionality increases. This empirical evidence supports the theoretical claim that for very small $\alpha$, the distribution becomes extremely "spiky."

Key Theoretical Results

The paper establishes several key bounds on sparsity:

  • Standard Sparsity ($\alpha = 1/n$): Theorem 1.1 states that the probability of more than $6c_0 \ln n$ coordinates exceeding the threshold $1/n^{c_0}$ is at most $1/n^{c_0}$. In a 1,000-dimensional space, very few coordinates will ever be significantly large.
  • Extreme Sparsity ($\alpha = 1/n^2$): Theorem 1.3 shows that if $\alpha = 1/n^2$, there is at least a 64% probability that no more than 5 coordinates will exceed the threshold $n^{-2}$, regardless of how large $n$ is (for $n \ge 3$).
  • Generalized Bounds: Theorem 1.2 provides a flexible framework for researchers to calculate specific constants for their model constraints.

Limitations and Conclusion

While the methods provide tight bounds for the standard case, they are somewhat "loose" for extremely small parameters ($\alpha = o(1/n)$). For instance, while simulations suggest only one coordinate is typically large when $\alpha = 1/n^2$, the theoretical bound in Theorem 1.3 is limited to 5 coordinates. Tightening these bounds for high-sparsity regimes remains an area for future refinement. Overall, this work provides the necessary formal foundation for the long-held intuition regarding Dirichlet sparsity in machine learning.

Summary updated

Abstract

This note provides an elementary proof of the folklore fact that draws from a Dirichlet distribution (with parameters less than 1) are typically sparse (most coordinates are small).
BibTeX
@misc{telgarsky2013dirichlet,
  author = {Matus Telgarsky},
  title = {{Dirichlet draws are sparse with high probability}},
  year = {2013},
  eprint = {1301.4917},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1301.4917},
}
Figure