Nesting Probabilistic Programs

Tom Rainforth
Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, PMLR R16:248-257, 2018.

Abstract

We formalize the notion of nesting probabilistic programming queries and investigate the result- ing statistical implications. We demonstrate that while query nesting allows the definition of models which could not otherwise be ex- pressed, such as those involving agents reason- ing about other agents, existing systems take approaches which lead to inconsistent estimates. We show how to correct this by delineating pos- sible ways one might want to nest queries and asserting the respective conditions required for convergence. We further introduce a new on- line nested Monte Carlo estimator that makes it substantially easier to ensure these conditions are met, thereby providing a simple framework for designing statistically correct inference en- gines. We prove the correctness of this online estimator and show that, when using the recom- mended setup, its asymptotic variance is always better than that of the equivalent fixed estimator, while its bias is always within a factor of two.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR16-rainforth18a, title = {Nesting Probabilistic Programs}, author = {Rainforth, Tom}, booktitle = {Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence}, pages = {248--257}, year = {2018}, editor = {Globerson, Amir and Silva, Ricardo}, volume = {R16}, series = {Proceedings of Machine Learning Research}, month = {06--10 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r16/main/assets/rainforth18a/rainforth18a.pdf}, url = {https://proceedings.mlr.press/r16/rainforth18a.html}, abstract = {We formalize the notion of nesting probabilistic programming queries and investigate the result- ing statistical implications. We demonstrate that while query nesting allows the definition of models which could not otherwise be ex- pressed, such as those involving agents reason- ing about other agents, existing systems take approaches which lead to inconsistent estimates. We show how to correct this by delineating pos- sible ways one might want to nest queries and asserting the respective conditions required for convergence. We further introduce a new on- line nested Monte Carlo estimator that makes it substantially easier to ensure these conditions are met, thereby providing a simple framework for designing statistically correct inference en- gines. We prove the correctness of this online estimator and show that, when using the recom- mended setup, its asymptotic variance is always better than that of the equivalent fixed estimator, while its bias is always within a factor of two.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Nesting Probabilistic Programs %A Tom Rainforth %B Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2018 %E Amir Globerson %E Ricardo Silva %F pmlr-vR16-rainforth18a %I PMLR %P 248--257 %U https://proceedings.mlr.press/r16/rainforth18a.html %V R16 %X We formalize the notion of nesting probabilistic programming queries and investigate the result- ing statistical implications. We demonstrate that while query nesting allows the definition of models which could not otherwise be ex- pressed, such as those involving agents reason- ing about other agents, existing systems take approaches which lead to inconsistent estimates. We show how to correct this by delineating pos- sible ways one might want to nest queries and asserting the respective conditions required for convergence. We further introduce a new on- line nested Monte Carlo estimator that makes it substantially easier to ensure these conditions are met, thereby providing a simple framework for designing statistically correct inference en- gines. We prove the correctness of this online estimator and show that, when using the recom- mended setup, its asymptotic variance is always better than that of the equivalent fixed estimator, while its bias is always within a factor of two. %Z Reissued by PMLR on 04 October 2026.
APA
Rainforth, T.. (2018). Nesting Probabilistic Programs. Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R16:248-257 Available from https://proceedings.mlr.press/r16/rainforth18a.html. Reissued by PMLR on 04 October 2026.

Related Material