Fast Reconstruction of Mixtures of Bernoulli Product Distributions

Sanyam Agarwal, Pranjal Dutta, Markus Bläser
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:794-816, 2026.

Abstract

Mixtures of Bernoulli product distributions are a simple and widely used latent-variable model, with applications in e.g. recommendation systems, crowdsourcing, and medical data analysis. We consider the problem of reconstructing the mixture parameters from oracle access to its probability generating polynomial (PGP), for instance represented by a probabilistic generating circuit (PGC). We show that the parameters are uniquely identifiable for almost all mixtures, and give a randomized algorithm that exactly recovers the mixture weights and component marginals for mixtures of $r$ Bernoulli product distributions over $n$ variables using only $O(nr^2)$ oracle queries. The algorithm repeatedly applies restrictions to $O(r)$ variables, extracts low-degree coefficients, and then recovers the parameters using a moment-based tensor decomposition. To the best of our knowledge, this is the first exact reconstruction algorithm in this PGP oracle model with query complexity linear in $n$ and polynomial in $r$.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-agarwal26b, title = {Fast Reconstruction of Mixtures of Bernoulli Product Distributions}, author = {Agarwal, Sanyam and Dutta, Pranjal and Bl\"{a}ser, Markus}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {794--816}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/agarwal26b/agarwal26b.pdf}, url = {https://proceedings.mlr.press/v306/agarwal26b.html}, abstract = {Mixtures of Bernoulli product distributions are a simple and widely used latent-variable model, with applications in e.g. recommendation systems, crowdsourcing, and medical data analysis. We consider the problem of reconstructing the mixture parameters from oracle access to its probability generating polynomial (PGP), for instance represented by a probabilistic generating circuit (PGC). We show that the parameters are uniquely identifiable for almost all mixtures, and give a randomized algorithm that exactly recovers the mixture weights and component marginals for mixtures of $r$ Bernoulli product distributions over $n$ variables using only $O(nr^2)$ oracle queries. The algorithm repeatedly applies restrictions to $O(r)$ variables, extracts low-degree coefficients, and then recovers the parameters using a moment-based tensor decomposition. To the best of our knowledge, this is the first exact reconstruction algorithm in this PGP oracle model with query complexity linear in $n$ and polynomial in $r$.} }
Endnote
%0 Conference Paper %T Fast Reconstruction of Mixtures of Bernoulli Product Distributions %A Sanyam Agarwal %A Pranjal Dutta %A Markus Bläser %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-agarwal26b %I PMLR %P 794--816 %U https://proceedings.mlr.press/v306/agarwal26b.html %V 306 %X Mixtures of Bernoulli product distributions are a simple and widely used latent-variable model, with applications in e.g. recommendation systems, crowdsourcing, and medical data analysis. We consider the problem of reconstructing the mixture parameters from oracle access to its probability generating polynomial (PGP), for instance represented by a probabilistic generating circuit (PGC). We show that the parameters are uniquely identifiable for almost all mixtures, and give a randomized algorithm that exactly recovers the mixture weights and component marginals for mixtures of $r$ Bernoulli product distributions over $n$ variables using only $O(nr^2)$ oracle queries. The algorithm repeatedly applies restrictions to $O(r)$ variables, extracts low-degree coefficients, and then recovers the parameters using a moment-based tensor decomposition. To the best of our knowledge, this is the first exact reconstruction algorithm in this PGP oracle model with query complexity linear in $n$ and polynomial in $r$.
APA
Agarwal, S., Dutta, P. & Bläser, M.. (2026). Fast Reconstruction of Mixtures of Bernoulli Product Distributions. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:794-816 Available from https://proceedings.mlr.press/v306/agarwal26b.html.

Related Material