Abstract
The rate of convergence of weighted kernel herding (WKH) and sequential Bayesian quadrature (SBQ), two kernel-based sampling algorithms for estimating integrals with respect to some target probability measure, is investigated. Under verifiable conditions on the chosen kernel and target measure, we establish a near-geometric rate of convergence for target measures that are nearly atomic. Furthermore, we show these algorithms perform comparably to the theoretical best possible sampling algorithm under the maximum mean discrepancy. An analysis is also conducted in a distributed setting. Our theoretical developments are supported by empirical observations on simulated data as well as a real world application.
Introduction
Estimating expectations—calculating the average value of a function over a probability distribution—is a fundamental task in machine learning and statistics. While standard Monte Carlo (MC) integration is widely used, its convergence rate of $O(m^{-1/2})$ is often too slow for high-precision requirements. Kernel-based methods like "herding" and Bayesian Quadrature offer an alternative by greedily selecting samples to minimize the Maximum Mean Discrepancy (MMD) in a Reproducing Kernel Hilbert Space (RKHS). However, the theoretical underpinnings for the fast convergence of unconstrained versions of these algorithms have been incomplete. This work provides a rigorous analysis of these rates and introduces scalable distributed implementations.
Methods
We analyze two primary algorithms: Weighted Kernel Herding (WKH) and Sequential Bayesian Quadrature (SBQ). Both methods iteratively build a representative set of samples $S$ to approximate a target distribution.
As shown in Algorithm 1, these methods greedily select a new point $\mathbf{x}_n$ and then update the weights $\mathbf{w}$ by solving a linear system involving the kernel Gram matrix $\mathbf{K}$. The key theoretical framework introduced is the Realizability Assumption, which assumes the target distribution's mean embedding can be represented by a finite set of $r$ atoms.
To address computational challenges in large-scale settings, we also propose a distributed variant. This method partitions the search domain across multiple nodes, performs local herding, and aggregates results to maintain approximation quality while significantly reducing runtime.
Results and Discussion
Our theoretical analysis demonstrates that under the realizability assumption, both WKH and SBQ achieve a near-geometric convergence rate of $O(e^{-rm})$. This exponential decay significantly outperforms the polynomial rates of standard Monte Carlo methods. Furthermore, we prove that these greedy strategies are nearly as effective as the optimal (but computationally intractable) exhaustive search for representative points.
Empirical evaluations were conducted on synthetic Gaussian mixtures and large-scale real-world datasets, including ChemReact, CovType, and WebSpam. In data summarization tasks for logistic regression, the algorithms successfully selected small "coresets" that maintained high model accuracy. The distributed implementation achieved a near-linear speedup (approximately 5x with 5 machines) on the larger datasets with negligible loss in performance compared to centralized versions.
Conclusion
This work establishes the first near-geometric convergence rates for unconstrained kernel-based sampling. While the current distributed theory is focused on the $r=1$ case, the empirical results suggest broader applicability. Future research will focus on extending the distributed proofs and optimizing the computational overhead of kernel matrix inversions for larger sample sets.
Summary updated