BayesSum: Bayesian Quadrature in Discrete Spaces
This addresses a computational bottleneck for researchers and practitioners in statistics and machine learning dealing with discrete inference, though it is an incremental extension of Bayesian quadrature to discrete spaces.
The paper tackled the problem of estimating intractable expectations over discrete domains by proposing BayesSum, a Bayesian quadrature extension, which achieved significantly faster convergence rates and required fewer samples than Monte Carlo methods in synthetic and model estimation tasks.
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.