Geometric rates of convergence for kernel-based sampling algorithms

Rajiv Khanna, Liam Hodgkinson, Michael W. Mahoney

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 cornerstone of statistics and machine learning. When these integrals cannot be solved analytically, researchers turn to sampling. Standard tools like Monte Carlo (MC) or Markov Chain Monte Carlo (MCMC) are reliable but slow, typically converging at a rate of $O(m^{-1/2})$, where $m$ is the number of samples.

To achieve "super-root-m" speeds, kernel-based methods like Kernel Herding and Sequential Bayesian Quadrature (SBQ) were developed. While these methods appeared fast in experiments, existing theoretical proofs often struggled to justify anything better than the standard $O(m^{-1/2})$ rate, or relied on restrictive assumptions that do not apply to modern use cases. This paper provides the "missing link" explaining why these algorithms often converge much faster in practice.

Methodology

The research focuses on two greedy algorithms:

  1. Weighted Kernel Herding (WKH): Iteratively selects points to minimize the Maximum Mean Discrepancy (MMD) between the target distribution and the sample set.
  2. Sequential Bayesian Quadrature (SBQ): Minimizes posterior variance by viewing the problem through a Gaussian Process lens.

The Realizability Assumption

The authors introduce a "realizability" assumption: the target distribution's mean embedding can be exactly reproduced by a finite number of "atoms" ($r$ samples). This allows them to move beyond slow $O(m^{-1/2})$ bounds. Theorem 1 demonstrates that these greedy algorithms are "good enough"—they perform comparably to a theoretical, computationally impossible exhaustive search for the best $r$ atoms, requiring only a logarithmic factor more samples to match performance.

Convergence of MMD for various kernel-based sampling algorithms showing faster-than-standard rates.

Distributed Kernel Herding

To scale these algorithms to massive datasets, the authors propose a "map-reduce" style framework. The search domain is partitioned across multiple machines, each running herding locally. A central server then collates the results. This bypasses the computational bottleneck of searching a massive candidate set on a single machine, which is often the primary limitation of SBQ and WKH.

Experimental Results

The distributed approach was evaluated on simulated mixtures of Gaussians and real-world datasets including ChemReact (26,733 compounds), CovType (581,012 examples), and WebSpam (350,000 webpages). For real-world data, Fisher Kernels were used to turn the problem into a data summarization task.

Key Findings

  • Geometric Convergence: Under the realizability assumption, WKH and SBQ achieve a linear (geometric) convergence rate ($O(e^{-rm})$), independent of dimension-dependent constants. This explains why they drastically outperform Monte Carlo in applications like data summarization.
  • Scalable Performance: In distributed experiments using 5 machines, the authors observed a 5x speedup with only minimal degradation in MMD and log-likelihood. For massive datasets like CovType, the distributed version successfully extracted summaries of a few hundred points that maintained high predictive accuracy.
Negative log-likelihood performance on a real-world dataset comparing standard and distributed (5-machine) variants.

Conclusion and Limitations

The study confirms that kernel-based sampling methods can achieve near-exponential convergence when the target measure is nearly atomic. While the distributed algorithm performs excellently for complex targets ($r > 1$) in practice, the current theoretical proof for its convergence only covers the single-atom case ($r=1$). Future work will focus on refining these proofs for more complex distributed scenarios and exploring the impact of non-atomic, smooth distributions on these geometric rates.

Summary updated

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.
BibTeX
@inproceedings{khanna2021geometric,
  author = {Rajiv Khanna and Liam Hodgkinson and Michael W. Mahoney},
  title = {{Geometric rates of convergence for kernel-based sampling algorithms}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=j8LbT44Vxx},
}
Figure