Not all Strongly Rayleigh Distributions Have Small Probabilistic Generating Circuits

Markus Bläser
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:2592-2602, 2023.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-blaser23a, title = {Not all Strongly Rayleigh Distributions Have Small Probabilistic Generating Circuits}, author = {Bl\"{a}ser, Markus}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {2592--2602}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/blaser23a/blaser23a.pdf}, url = {https://proceedings.mlr.press/v202/blaser23a.html}, 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.} }
Endnote
%0 Conference Paper %T Not all Strongly Rayleigh Distributions Have Small Probabilistic Generating Circuits %A Markus Bläser %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-blaser23a %I PMLR %P 2592--2602 %U https://proceedings.mlr.press/v202/blaser23a.html %V 202 %X 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.
APA
Bläser, M.. (2023). Not all Strongly Rayleigh Distributions Have Small Probabilistic Generating Circuits. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:2592-2602 Available from https://proceedings.mlr.press/v202/blaser23a.html.

Related Material