Not all Strongly Rayleigh Distributions Have Small Probabilistic Generating Circuits

Markus Bläser

Overview

This paper settles an open question in machine learning theory: can all "Strongly Rayleigh" (SR) distributions—a broad class of models used to capture negative dependence—be represented by small, efficient probabilistic circuits? The answer is a definitive no (assuming standard complexity theory conjectures). This proves that even advanced models like Probabilistic Generating Circuits (PGCs) have fundamental limits in their expressive power.

The Expressiveness vs. Tractability Trade-off

In probabilistic machine learning, researchers face a constant tug-of-war between expressiveness (how many types of distributions a model can represent) and tractability (how fast we can perform inference, like calculating marginal probabilities).

A probabilistic circuit and its corresponding probability distribution table.

Recently, a new model called Probabilistic Generating Circuits (PGCs) gained attention. Unlike standard probabilistic circuits that compute probability mass functions directly, PGCs represent distributions as probability generating functions—essentially treating the distribution as a giant polynomial. This approach is powerful because it subsumes many other models and makes certain types of inference highly efficient.

A particularly important class of distributions is the Strongly Rayleigh (SR) family. These distributions are used to model "negative dependence" (e.g., if you pick one item for a set, you are less likely to pick a similar one). Examples include spanning tree distributions and determinantal point processes. At ICML 2021, researchers asked: Can every SR distribution be represented by a polynomial-sized PGC? If the answer were yes, PGCs would be a universal tool for this vital class of models. This paper proves the answer is no.

Proving Impossibility via Complexity Theory

Because this is a theoretical paper focused on mathematical proofs and complexity bounds, the authors do not rely on empirical datasets. Instead, they use a proof technique from computational complexity theory. To prove that a small circuit cannot exist, they construct a "hard" SR distribution and show that if a small circuit existed for it, it would lead to a mathematical impossibility in complexity theory.

The key steps in their proof include:

  1. Constructing a "Double Function" Polynomial: The authors define a new type of multilinear polynomial based on "double functions" (pairs of functions between sets of nodes in a bipartite graph).
  2. Proving Real Stability: A distribution is Strongly Rayleigh if its generating polynomial is "real stable" (meaning it has no roots in the upper half of the complex plane). The authors use the "Multi-Affine Part" (MAP) operator to prove their constructed polynomial meets this strict mathematical requirement.
  3. Linking to #P-Hardness: The authors prove that evaluating this specific polynomial is equivalent to counting perfect matchings in a bipartite graph.
A bipartite graph highlighting a perfect matching, a combinatorial structure central to the paper's #P-hardness proof.

Counting perfect matchings is a famous problem in computer science known to be #P-complete—meaning it is computationally "harder" than standard NP-complete problems.

Key Insights and Theoretical Results

The paper elegantly bridges the gap between probability theory (real stability) and structural complexity (the Polynomial Hierarchy). It shows that the "hardness" of a distribution is tied to the difficulty of counting the combinatorial structures that define it.

A major challenge in the proof was that the initial "hard" polynomial had negative coefficients, which cannot represent valid probabilities. The authors used a clever "inversion" technique to flip the signs of the coefficients while maintaining the real stability property, successfully turning a raw polynomial into a valid SR distribution.

The "Collapse" Consequence

The main theorem states that if every SR distribution had a polynomial-sized PGC, then $P^{\#P} \subseteq P/poly$. Following Karp-Lipton and Toda’s theorems, this implies that the Polynomial Hierarchy (PH) would collapse to its second level ($\Sigma_2$).

Because a collapse of the PH is considered highly unlikely by computer scientists, the paper concludes that there must exist SR distributions that require super-polynomial (exponentially large) PGCs to represent.

Limitations and Future Work

The primary limitation of this work is that it provides a non-constructive existence proof. While it proves that "hard" SR distributions exist, it doesn't necessarily mean the SR distributions we use in everyday machine learning (like those for spanning trees) are hard to represent.

Future work could involve:

  • Identifying specific boundaries: Which subclasses of SR distributions are always tractable?
  • Exploring approximate representations: Can we represent these hard distributions with small circuits if we allow for a tiny bit of error?
  • Investigating other circuit types: Are there other ways to represent SR distributions that bypass these complexity-theoretic walls?

Summary updated

Abstract

Probabilistic modeling is a central task in machine learning. Probabilistic models should be tractable, i.e., allowing tractable probabilistic inference, but also efficient, i.e., being able to represent a large set of probability distributions. Zhang et al. (ICML 2021) recently proposed a new model, probabilistic generating circuits. They raised the question whether every strongly Rayleigh distribution can be efficiently represented by such circuits. We prove that this question has a negative answer, there are strongly Rayleigh distributions that cannot be represented by polynomial-sized probabilistic generating circuits, assuming a widely accepted complexity theoretic conjecture.
BibTeX
@inproceedings{blaser2023not,
  author = {Markus Bläser},
  title = {{Not all Strongly Rayleigh Distributions Have Small Probabilistic Generating Circuits}},
  booktitle = {International Conference on Machine Learning},
  year = {2023},
  url = {https://openreview.net/forum?id=zh7du3B8rx},
}
Figure