TL;DR
This paper tackles the computational bottleneck of Bayesian Quadrature (BQ), a powerful probabilistic integration technique, by introducing methods to select batches of points for evaluation, rather than one at a time. This parallelization significantly speeds up integration, especially for expensive integrands, making BQ more practical for real-world machine learning tasks.
What Problem Does This Paper Address?
Many problems in machine learning, such as model averaging and computing posterior distributions, require integrating functions that are often intractable. Bayesian Quadrature (BQ) offers a probabilistic approach to this by modeling the integrand with a Gaussian Process (GP) and inferring the integral's value and uncertainty. While BQ is promising, its traditional implementation is serial: it selects one point at a time to evaluate the integrand. This becomes a major bottleneck when evaluating the integrand is computationally expensive, as it limits the benefits of modern parallel computing hardware. The paper aims to bridge this gap by enabling parallel evaluation of the integrand through batch selection.
Methods
The core contribution of this paper is the development of batch selection strategies for Bayesian Quadrature, drawing inspiration from similar techniques in Batch Bayesian Optimization.
- Batch Selection: Instead of picking a single point, the algorithm now selects a batch of points to evaluate the integrand. This allows for parallel computation.
- Local Penalisation: A novel approach to batch selection is introduced. It modifies the acquisition function (which guides where to sample next) by penalizing regions around already selected points. This encourages diversity within the batch, preventing all selected points from being too similar and thus uninformative.
- This penalization is achieved by incorporating a "Lipschitz Cone" that bounds the slope of the acquisition function around selected points.
- A "soft minimization" using an $l_p$-norm with a negative $p$ is used to make the penalized acquisition function differentiable everywhere except at the selected points, avoiding issues with non-differentiability.
- Kriging Believer: This is a more standard batch selection heuristic borrowed from Bayesian Optimization, where points are selected sequentially based on the acquisition function, and the model is updated after each "virtual" selection before the next point is chosen.
- Warped Bayesian Quadrature (WSABI): The paper builds upon existing work that uses a square-root transformation (WSABI-L) to handle non-negative integrands, which is particularly relevant for likelihood functions.
Datasets
Not discussed in the paper. The experiments use synthetic integrands and a benchmark function for Gaussian Process model evidence computation.
Key Insights and Ideas
- Parallelism is Key for Expensive Integrands: The fundamental insight is that the serial nature of traditional BQ is its Achilles' heel when integrand evaluations are costly. Batching directly addresses this by enabling parallel computation, leading to significant speedups.
- Diversity in Batches is Crucial: Simply picking the highest points on the acquisition function is suboptimal. The paper highlights the need for diverse batches to ensure that the selected points provide a broad and informative coverage of the integrand's behavior, especially for integration.
- Local Penalization Offers a Principled Way to Ensure Diversity: The proposed local penalization method provides a novel and effective way to encourage batch diversity by actively discouraging sampling in already well-explored regions, while still allowing exploration of promising areas.
- BQ is Competitive with MCMC for Small Budgets: The paper reinforces the idea that BQ, especially with parallelization, can be competitive with or outperform MCMC methods when the total number of integrand evaluations (or "samples") is limited.
Key Results
- Significant Speedup with Batching: Experiments show that increasing the batch size leads to much faster convergence in terms of the number of batches required to reach a certain absolute error. For instance, larger batch sizes converged "much more quickly" on an in-model integrand.
- Comparable Performance of Batching Methods: Both the proposed Local Penalisation and the standard Kriging Believer batch selection methods demonstrated comparable performance, suggesting that both are effective strategies for parallelizing BQ.
- Outperforming MCMC: In the experiment computing model evidence for a Gaussian Process, the batched BQ methods clearly outperformed Metropolis-Hastings and NUTS (a state-of-the-art MCMC method), especially when considering the number of batches.
- Effective for Non-negative Integrands: The use of WSABI-L demonstrates the effectiveness of the approach for integrands that are known to be non-negative, a common scenario in machine learning.
Limitations and Future Work
- Stopping Criterion: The paper notes that for the specific WSABI-L model, using the GP variance as a stopping criterion is problematic because the model can be overconfident away from data. They resort to a fixed computational budget for their experiments. This suggests future work could explore more robust stopping criteria.
- Tuning Parameters: The paper mentions that the "soft minimization" parameter ($p$) and the scaling of the Lipschitz cone gradient could be tuned to influence exploration. While they found good values for their experiments ($p=-6$), further investigation into optimal tuning strategies is warranted.
- Generalization of Local Penalization: The proposed local penalization is tailored for integration. Its applicability and effectiveness in other contexts, like pure optimization, might require further study.
- Theoretical Guarantees: While the empirical results are strong, further theoretical analysis of the convergence properties of the proposed batch selection methods would be valuable.
Summary updated