BayesSum: Bayesian Quadrature in Discrete Spaces

Sophia Seulkee Kang, Francois-Xavier Briol, Toni Karvonen, Zonghao Chen
Proceedings of the 2nd International Conference on Probabilistic Numerics, PMLR 341:73-89, 2026.

Abstract

This paper addresses the challenging computational problem of estimating intractable expectations over discrete domains. Existing approaches, including Monte Carlo and Russian Roulette estimators, are consistent but often require a large number of samples to achieve accurate results. We propose a novel estimator, \emph{BayesSum}, which is an extension of Bayesian quadrature to discrete domains. It is more sample efficient than alternatives due to its ability to make use of prior information about the integrand through a Gaussian process. We show this through theory, deriving a convergence rate significantly faster than Monte Carlo in a broad range of settings. We also demonstrate empirically that our proposed method does indeed require fewer samples on several synthetic settings as well as for parameter estimation for Conway-Maxwell-Poisson and Potts models.

Cite this Paper

BibTeX
@InProceedings{pmlr-v341-kang26a, title = {{B}ayesSum: {B}ayesian Quadrature in Discrete Spaces}, author = {Kang, Sophia Seulkee and Briol, Francois-Xavier and Karvonen, Toni and Chen, Zonghao}, booktitle = {Proceedings of the 2nd International Conference on Probabilistic Numerics}, pages = {73--89}, year = {2026}, editor = {Karvonen, Toni and Bosch, Nathanael and Cockayne, Jon and Gessner, Alexandra and Hennig, Philipp and Kouw, Wouter}, volume = {341}, series = {Proceedings of Machine Learning Research}, month = {09--11 Sep}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v341/main/assets/kang26a/kang26a.pdf}, url = {https://proceedings.mlr.press/v341/kang26a.html}, abstract = {This paper addresses the challenging computational problem of estimating intractable expectations over discrete domains. Existing approaches, including Monte Carlo and Russian Roulette estimators, are consistent but often require a large number of samples to achieve accurate results. We propose a novel estimator, \emph{BayesSum}, which is an extension of Bayesian quadrature to discrete domains. It is more sample efficient than alternatives due to its ability to make use of prior information about the integrand through a Gaussian process. We show this through theory, deriving a convergence rate significantly faster than Monte Carlo in a broad range of settings. We also demonstrate empirically that our proposed method does indeed require fewer samples on several synthetic settings as well as for parameter estimation for Conway-Maxwell-Poisson and Potts models.} }
Endnote
%0 Conference Paper %T BayesSum: Bayesian Quadrature in Discrete Spaces %A Sophia Seulkee Kang %A Francois-Xavier Briol %A Toni Karvonen %A Zonghao Chen %B Proceedings of the 2nd International Conference on Probabilistic Numerics %C Proceedings of Machine Learning Research %D 2026 %E Toni Karvonen %E Nathanael Bosch %E Jon Cockayne %E Alexandra Gessner %E Philipp Hennig %E Wouter Kouw %F pmlr-v341-kang26a %I PMLR %P 73--89 %U https://proceedings.mlr.press/v341/kang26a.html %V 341 %X This paper addresses the challenging computational problem of estimating intractable expectations over discrete domains. Existing approaches, including Monte Carlo and Russian Roulette estimators, are consistent but often require a large number of samples to achieve accurate results. We propose a novel estimator, \emph{BayesSum}, which is an extension of Bayesian quadrature to discrete domains. It is more sample efficient than alternatives due to its ability to make use of prior information about the integrand through a Gaussian process. We show this through theory, deriving a convergence rate significantly faster than Monte Carlo in a broad range of settings. We also demonstrate empirically that our proposed method does indeed require fewer samples on several synthetic settings as well as for parameter estimation for Conway-Maxwell-Poisson and Potts models.
APA
Kang, S.S., Briol, F., Karvonen, T. & Chen, Z.. (2026). BayesSum: Bayesian Quadrature in Discrete Spaces. Proceedings of the 2nd International Conference on Probabilistic Numerics, in Proceedings of Machine Learning Research 341:73-89 Available from https://proceedings.mlr.press/v341/kang26a.html.

Related Material