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.
翻译:在选定内核和目标测量的可核查条件下,我们为接近原子的目标测量设定了近几何趋同率。此外,我们还显示这些算法在最大平均值差异下与理论上可能的最佳采样算法相当。分析也在分布式环境中进行。我们的理论发展得到模拟数据的经验观测以及实际世界应用的支持。