mlsanityData to 14 Oct 2026

Sum of Squares Circuits

arXiv 2408.11778 ↗First posted 21 Aug 2024cs.LG cs.AI cs.CCcited by 21

Not on the map. Why?

Abstract (arXiv)

Designing expressive generative models that support exact and efficient inference is a core question in probabilistic ML. Probabilistic circuits (PCs) offer a framework where this tractability-vs-expressiveness trade-off can be analyzed theoretically. Recently, squared PCs encoding subtractive mixtures via negative parameters have emerged as tractable models that can be exponentially more expressive than monotonic PCs, i.e., PCs with positive parameters only. In this paper, we provide a more precise theoretical characterization of the expressiveness relationships among these models. First, we prove that squared PCs can be less expressive than monotonic ones. Second, we formalize a novel class of PCs -- sum of squares PCs -- that can be exponentially more expressive than both squared and monotonic PCs. Around sum of squares PCs, we build an expressiveness hierarchy that allows us to precisely unify and separate different tractable model classes such as Born Machines and PSD models, and other recently introduced tractable probabilistic models by using complex parameters. Finally, we empirically show the effectiveness of sum of squares circuits in performing distribution estimation.

Key facts. Cited by 21 papers in the map (data through 14 Oct 2026). Builds on 30 of its 79 references that are in the map. First posted on arXiv 21 Aug 2024.

Builds on

30 of 79 references.

References · 30

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,349
  3. 2014Deep Learning Face Attributes in the Wildcited by 3,693
  4. 2016Complex Embeddings for Simple Link Predictioncited by 902
  5. 2019RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Spacecited by 898
  6. 2017Masked Autoregressive Flow for Density Estimationcited by 684
  7. 2015Unitary Evolution Recurrent Neural Networkscited by 294
  8. 2022Semantic Probabilistic Layers for Neuro-Symbolic Learningcited by 103
  9. 2013A Differential Approach to Inference in Bayesian Networkscited by 93
  10. 2017Unsupervised Generative Modeling Using Matrix Product Statescited by 88
  11. 2019Tree Tensor Networks for Generative Modelingcited by 64
  12. 2023Not All Neuro-Symbolic Concepts Are Created Equal: Analysis and Mitigation of Reasoning Shortcutscited by 63
18 more
  1. 2019Expressive power of tensor-network factorizations for probabilistic modeling, with applications from hidden Markov models to quantum machine learningcited by 55
  2. 2020Non-parametric Models for Non-negative Functionscited by 41
  3. 2016On the Latent Variable Interpretation in Sum-Product Networkscited by 40
  4. 2023Subtractive Mixture Models via Squaring: Representation and Learningcited by 39
  5. 2024BEARS Make Neuro-Symbolic Models Aware of their Reasoning Shortcutscited by 37
  6. 2016Parameterized Machine Learning for High-Energy Physicscited by 34
  7. 2019Conditional Sum-Product Networks: Imposing Structure on Deep Probabilistic Architecturescited by 24
  8. 2021PSD Representations for Effective Probability Modelscited by 23
  9. 2023How to Turn Your Knowledge Graph Embeddings into Generative Modelscited by 20
  10. 2014On the Expressive Efficiency of Sum Product Networkscited by 16
  11. 2024On the Relationship Between Monotone and Squared Probabilistic Circuitscited by 14
  12. 2015A mathematical motivation for complex-valued convolutional networkscited by 13
  13. 2023Squared Neural Families: A New Class of Tractable Density Modelscited by 12
  14. 2024Polynomial Semantics of Tractable Probabilistic Circuitscited by 12
  15. 2014Positive semidefinite rankcited by 10
  16. 2024Scaling Continuous Latent Variable Models as Probabilistic Integral Circuitscited by 9
  17. 2024Exact, Fast and Expressive Poisson Point Processes via Squared Neural Familiescited by 6
  18. 2014The square root rank of the correlation polytope is exponentialcited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 2; 2025: 11; 2026: 8.

21 papers.

Sort:

By area:

  1. 2024What is the Relationship between Tensor Factorizations and Circuits (and How Can We Exploit it)?cited by 22
  2. 2025A Probabilistic Neuro-symbolic Layer for Algebraic Constraint Satisfactioncited by 11
  3. 2025Scaling Probabilistic Circuits via Monarch Matricescited by 9
  4. 2025Fast and Expressive Multi-Byte Prediction with Probabilistic Circuitscited by 9
  5. 2024Restructuring Tractable Probabilistic Circuitscited by 7
  6. 2025How to Square Tensor Networks and Circuits Without Squaring Themcited by 5
  7. 2025Rethinking Probabilistic Circuit Parameter Learningcited by 4
  8. 2025Tractable Representation Learning with Probabilistic Circuitscited by 4
  9. 2026Hellinger Multimodal Variational Autoencoderscited by 3
  10. 2026An Embarrassingly Simple Way to Optimize Orthogonal Matrices at Scalecited by 3
  11. 2025On the Hardness of Approximating Distributions with Tractable Probabilistic Modelscited by 2
  12. 2025The Limits of Tractable Marginalizationcited by 2
9 more
  1. 2025Squared families: Searching beyond regular probability modelscited by 1
  2. 2025A Quantum Information Theoretic Approach to Tractable Probabilistic Modelscited by 1
  3. 2026The Theory and Practice of MAP Inference over Non-Convex Constraintscited by 1
  4. 2026Geometry-Aware Probabilistic Circuits via Voronoi Tessellationscited by 1
  5. 2026A Sobering Look at Tabular Data Generation via Probabilistic Circuitscited by 1
  6. 2026How to Approximate Inference with Subtractive Mixture Modelscited by 1
  7. 2025Scalable Expectation Estimation with Subtractive Mixture Modelscited by 0
  8. 2026Learning Markov Processes as Sum-of-Square Forms for Analytical Belief Propagationcited by 0
  9. 2026On the Approximation Complexity of Matrix Product Operator (MPO) Born Machinescited by 0