BayesSum: Bayesian Quadrature in Discrete Spaces

• URL: http://arxiv.org/abs/2512.16105v1
• Date: Thu, 18 Dec 2025 02:43:30 GMT
• Title: BayesSum: Bayesian Quadrature in Discrete Spaces
• Authors: Sophia Seulkee Kang, François-Xavier Briol, Toni Karvonen, Zonghao Chen,
• Abstract summary: Existing approaches, including Monte Carlo and Russian Roulette estimators, are consistent but often require a large number of samples to achieve accurate results.<n>We propose a novel estimator, emphBayesSum, which is an extension of Bayesian quadrature to discrete domains.
• Score: 8.571182593542565
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Using Gaussian Boson Samplers to Approximate Gaussian Expectation Problems [0.0]
  We show that two estimators using GBS samples can bring an exponential speedup over the plain Monte Carlo (MC) estimator.<n> Precisely speaking, the exponential speedup is defined in terms of the guaranteed sample size for these estimators to reach the same level of accuracy.
  arXiv  Detail & Related papers  (2025-02-26T17:30:49Z)
• Nested Expectations with Kernel Quadrature [6.531113005552847]
  Existing algorithms, such as nested Monte Carlo or multilevel Monte Carlo, are known to be consistent but require a large number of samples at both inner and outer levels to converge.<n>We propose a novel estimator consisting of nested kernel quadrature estimators.
  arXiv  Detail & Related papers  (2025-02-25T15:19:10Z)
• Multivariate root-n-consistent smoothing parameter free matching estimators and estimators of inverse density weighted expectations [51.000851088730684]
  We develop novel modifications of nearest-neighbor and matching estimators which converge at the parametric $sqrt n $-rate.<n>We stress that our estimators do not involve nonparametric function estimators and in particular do not rely on sample-size dependent parameters smoothing.
  arXiv  Detail & Related papers  (2024-07-11T13:28:34Z)
• Bayesian Circular Regression with von Mises Quasi-Processes [57.88921637944379]
  In this work we explore a family of expressive and interpretable distributions over circle-valued random functions.<n>For posterior inference, we introduce a new Stratonovich-like augmentation that lends itself to fast Gibbs sampling.<n>We present experiments applying this model to the prediction of wind directions and the percentage of the running gait cycle as a function of joint angles.
  arXiv  Detail & Related papers  (2024-06-19T01:57:21Z)
• On diffusion-based generative models and their error bounds: The log-concave case with full convergence estimates [5.13323375365494]
  We provide theoretical guarantees for the convergence behaviour of diffusion-based generative models under strongly log-concave data.<n>Our class of functions used for score estimation is made of Lipschitz continuous functions avoiding any Lipschitzness assumption on the score function.<n>This approach yields the best known convergence rate for our sampling algorithm.
  arXiv  Detail & Related papers  (2023-11-22T18:40:45Z)
• Parallelized Acquisition for Active Learning using Monte Carlo Sampling [0.0]
  Recent attention has been directed towards the use of emulators of the posterior based on Gaussian Process (GP) regression. We show how to generate a Monte Carlo sample of the posterior using almost-embarrassingly parallel sequential samplers. The resulting nearly-sorted Monte Carlo sample is used to generate a batch of candidates ranked according to their sequentially conditioned acquisition function values.
  arXiv  Detail & Related papers  (2023-05-30T17:57:34Z)
• Langevin Monte Carlo for Contextual Bandits [72.00524614312002]
  Langevin Monte Carlo Thompson Sampling (LMC-TS) is proposed to directly sample from the posterior distribution in contextual bandits. We prove that the proposed algorithm achieves the same sublinear regret bound as the best Thompson sampling algorithms for a special case of contextual bandits.
  arXiv  Detail & Related papers  (2022-06-22T17:58:23Z)
• Pathwise Conditioning of Gaussian Processes [72.61885354624604]
  Conventional approaches for simulating Gaussian process posteriors view samples as draws from marginal distributions of process values at finite sets of input locations. This distribution-centric characterization leads to generative strategies that scale cubically in the size of the desired random vector. We show how this pathwise interpretation of conditioning gives rise to a general family of approximations that lend themselves to efficiently sampling Gaussian process posteriors.
  arXiv  Detail & Related papers  (2020-11-08T17:09:37Z)
• Mean-Field Approximation to Gaussian-Softmax Integral with Application to Uncertainty Estimation [23.38076756988258]
  We propose a new single-model based approach to quantify uncertainty in deep neural networks. We use a mean-field approximation formula to compute an analytically intractable integral. Empirically, the proposed approach performs competitively when compared to state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-06-13T07:32:38Z)
• Efficiently Sampling Functions from Gaussian Process Posteriors [76.94808614373609]
  We propose an easy-to-use and general-purpose approach for fast posterior sampling. We demonstrate how decoupled sample paths accurately represent Gaussian process posteriors at a fraction of the usual cost.
  arXiv  Detail & Related papers  (2020-02-21T14:03:16Z)
• Distributionally Robust Bayesian Quadrature Optimization [60.383252534861136]
  We study BQO under distributional uncertainty in which the underlying probability distribution is unknown except for a limited set of its i.i.d. samples. A standard BQO approach maximizes the Monte Carlo estimate of the true expected objective given the fixed sample set. We propose a novel posterior sampling based algorithm, namely distributionally robust BQO (DRBQO) for this purpose.
  arXiv  Detail & Related papers  (2020-01-19T12:00:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.