Optimally-Weighted Herding is Bayesian Quadrature

Problem Statement
A fundamental challenge in statistical machine learning is computing expectations of functions over probability distributions, expressed as $Z_{f,p} = \int f(x)p(x)dx$. While Monte Carlo methods approximate this via random sampling with a convergence rate of $O(1/\sqrt{N})$, they suffer from stochastic variance. Quasi-Monte Carlo methods offer a deterministic alternative by generating pseudo-samples to minimize the discrepancy between the empirical distribution of samples and the target distribution $p(x)$. Two prominent deterministic methods are Kernel Herding, which minimizes the Maximum Mean Discrepancy (MMD) to select samples, and Bayesian Quadrature (BQ), which infers a posterior distribution over the integrand $f$ to estimate the integral. The paper addresses the theoretical connection between these two methods and investigates whether a weighted approach to sample selection can outperform standard herding.

Methodology
The authors establish a theoretical link between Kernel Herding and Bayesian Quadrature by analyzing the objective functions minimized by each.

1. Equivalence of Criteria: The paper demonstrates that the criterion minimized in Kernel Herding (MMD) is mathematically equivalent to the posterior variance of the integral estimate in Bayesian Quadrature, assuming a Gaussian Process (GP) prior on $f$. Specifically, the expected error in BQ corresponds to the MMD between the target distribution $p$ and a discrete distribution defined by the samples and their weights.
2. Sequential Bayesian Quadrature (SBQ): While standard Herding assigns uniform weights ($1/N$) to samples, BQ assigns optimal weights derived from the GP posterior. The authors propose Sequential Bayesian Quadrature (SBQ), a greedy algorithm that selects sample locations to minimize the posterior variance (equivalent to minimizing MMD with optimal weights).
3. Weight Analysis: The paper analyzes the properties of BQ weights, noting they are not necessarily positive and do not sum to one. These weights are shown to be optimal in a minimax sense over the Reproducing Kernel Hilbert Space (RKHS) defined by the kernel.
4. Submodularity: The authors investigate the convergence properties of SBQ by relating the selection process to the sparse dictionary selection problem. They prove that the objective function is "approximately submodular," allowing for theoretical bounds on the performance of the greedy selection strategy, though these bounds are weaker than those for strictly submodular functions.

Key Contributions

1. Theoretical Unification: The paper proves that the loss minimized by Kernel Herding is identical to the expected error (posterior variance) in Bayesian Quadrature. Consequently, BQ is framed as a weighted version of Kernel Herding where the weights are optimal for the given RKHS.
2. Optimality of Weights: It is shown that the weights derived from BQ dominate uniformly weighted Herding and other non-optimally weighted herding methods in terms of convergence rate.
3. Algorithmic Connection: The work connects the greedy selection of samples in BQ to the sparse dictionary selection problem, establishing that the objective is approximately submodular.
4. Empirical Validation: The authors provide empirical evidence demonstrating that SBQ achieves a convergence rate faster than $O(1/N)$, outperforming both standard Herding and i.i.d. random sampling in terms of Maximum Mean Discrepancy and integral estimation error.

Results

• Convergence Rates: In experiments using a 2D mixture of Gaussians, SBQ demonstrated a convergence rate superior to the $O(1/N)$ rate typically associated with Herding in finite-dimensional spaces. While the exact theoretical rate for SBQ in infinite-dimensional spaces remains unknown, empirical results suggest it is faster than $O(1/N)$.
• Sample Efficiency: The paper illustrates that a small number of SBQ samples (e.g., 8) with optimal weights can achieve the same estimation error as a larger number of Herding samples (e.g., 20) with uniform weights.
• Robustness: Experiments on functions outside the assumed RKHS showed that while the theoretical guarantees rely on the function belonging to the RKHS, the relative performance ranking of the methods (SBQ > Herding > i.i.d.) remained consistent even for "out-of-model" functions.
• Error Bounds: The MMD provides a provable upper bound on the empirical error of the BQ estimate, which was shown to decrease rapidly with the number of samples.

Significance and Claims
The paper claims that Sequential Bayesian Quadrature represents a significant advancement over Kernel Herding by integrating optimal weighting into the sample selection process. By viewing BQ as an optimally-weighted Herding method, the authors provide a unified theoretical framework that explains the superior performance of BQ. The work highlights that while BQ incurs a higher computational cost ($O(N^3)$ for weight computation vs. $O(N^2)$ for Herding), the faster convergence rate may render it more efficient in scenarios where function evaluations are expensive. The authors modestly note that while they establish an upper bound on the empirical error and demonstrate faster-than-$O(1/N)$ convergence empirically, the theoretically optimal convergence rate for SBQ in infinite-dimensional spaces remains an open question for future research. The paper concludes that the choice of method depends on the trade-off between computational cost and the expense of evaluating the integrand $f$.