Research map / Learning theory and algorithms / Sample complexity

On the Expressive Power of Tree-Structured Probabilistic Circuits

NeurIPS 2024 · Learning theory and algorithms › Sample complexity · approach: Computational thresholds in graphs and structure · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that DAG-structured probabilistic circuits can be converted to equivalent tree PCs of quasi-polynomial size n^{O(log n)} and depth O(log n), and proves a super-polynomial tree-vs-DAG separation under depth o(log n).

Problem

Whether there is an exponential size gap between tree-structured and DAG-structured probabilistic circuits (PCs), i.e., the expressive power of tree-structured PCs relative to general DAG PCs.

Approach

Adapts partial-derivative-based depth reduction from arithmetic circuit complexity to PCs (without the binary-children restriction) to get a depth-O(log n) DAG, then duplicates shared nodes to obtain a quasi-polynomial tree; for the lower bound, reduces tree PCs with bounded depth to monotone arithmetic formula lower bounds.

Key results

• Any DAG-structured PC over n variables of polynomial size admits an equivalent tree PC of size n^{O(log n)} and depth O(log n).
• There exists a polynomial computable by an O(n log n)-size depth-O(log n) PC, but any tree PC of depth o(log n) computing it has size n^{omega(1)}.

Surprising findings

• The conjectured exponential gap between DAG and tree PCs does not hold: a quasi-polynomial upper bound exists for trees.

Limitations

• Lower bound holds only under a depth restriction o(log n) on the tree; no unconditional exponential separation.
• Upper bound n^{O(log n)} is still prohibitively large for growing n.
• Results are over Boolean variables and theoretical only, with no experiments.

Experimental setup

Builds on: probabilistic circuits arithmetic circuit depth reduction (Valiant et al.) monotone formula lower bounds

Closest papers by meaning

• On the Hardness of Approximating Distributions with Tractable Probabilistic Models (NeurIPS 2025 · similarity 0.89)
• The Expressivity Boundary of Probabilistic Circuits: A Comparison with Large Language Models (NeurIPS 2026 · similarity 0.88)
• Scaling Probabilistic Circuits via Monarch Matrices (ICML 2025 · similarity 0.88)
• Sum-Product-Set Networks: Deep Tractable Models for Tree-Structured Graphs (ICLR 2024 · similarity 0.87)
• Distribution Learning Meets Graph Structure Sampling (NeurIPS 2025 · similarity 0.86)
• Probabilistic Neural Circuits (AAAI 2024 · similarity 0.86)