On Linear Convergence of Weighted Kernel Herding

Rajiv Khanna, 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 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, necessitating a massive number of samples.

Kernel-based sampling methods, such as Weighted Kernel Herding (WKH) and Sequential Bayesian Quadrature (SBQ), were developed to select "smarter" samples by minimizing the Maximum Mean Discrepancy (MMD) between the sample set and the target distribution. Despite their empirical success, theoretical understanding has lagged, with existing bounds often failing to explain their superior performance. This work bridges that gap by proving these algorithms can achieve "near-geometric" (exponential) convergence rates under a "realizability" assumption.

Methods: WKH and SBQ

The study focuses on two greedy algorithms that iteratively build a set of representative points $S$:

  1. Weighted Kernel Herding (WKH): Selects the next sample point to minimize MMD and subsequently optimizes the weights assigned to these points.
  2. Sequential Bayesian Quadrature (SBQ): A Gaussian Process-based approach where points are chosen to minimize posterior variance.

The general structure of these algorithms is detailed in Algorithm 1.

Algorithm 1: Weighted Kernel Herding (WKH) and Sequential Bayesian Quadrature (SBQ).

To address scalability, the authors also introduce Distributed Kernel Herding. This approach partitions the search space across multiple machines to perform local herding, with a central server aggregating the results to maintain efficiency on massive datasets.

Theoretical Insights: The Realizability Assumption

The core theoretical contribution is the introduction of the Realizability Assumption. This assumes the target distribution's mean embedding in a Reproducing Kernel Hilbert Space (RKHS) can be exactly represented by a finite number of atoms.

Under this assumption, the authors demonstrate:

  • Exponential Convergence: The error (MMD) decreases at a rate of $O(e^{-rm})$, where $m$ is the number of samples. This is a significant improvement over the $O(m^{-1/2})$ rate of Monte Carlo methods.
  • Near-Optimality: Theorem 1 establishes that these greedy algorithms are nearly as effective as the theoretically optimal (but computationally intractable) sampling algorithm, requiring only a few additional points to reach the same accuracy level.

Empirical Evaluation

The theoretical findings were validated through simulations and real-world data summarization tasks.

Datasets and Tasks

  • Simulated Data: A mixture of 20 two-dimensional Gaussians was used to track MMD convergence.
  • Data Summarization: Fisher Kernels were employed to create "coresets" for logistic regression on large-scale datasets:
  • ChemReact: 26,733 chemicals with 100 features.
  • CovType: 581,012 examples with 54 features.
  • WebSpam: 350,000 webpages with 127 features.

Key Results

  • Scaling: On large datasets like CovType and WebSpam, the distributed algorithm achieved nearly linear speedup relative to the number of machines, with minimal loss in accuracy.
  • Algorithm Comparison: Experiments confirmed that SBQ generally requires fewer samples than WKH to reach the same accuracy, though it is more computationally demanding per iteration due to weight optimization.

Conclusion and Future Work

This research provides a theoretical foundation for the high performance of kernel-based sampling in practice. By identifying the realizability assumption as a key driver for linear convergence, the authors offer a new perspective on algorithm design.

Future work includes extending the distributed convergence proofs to multi-atom cases and investigating algorithm behavior under "misspecified" settings where the kernel does not perfectly align with the target distribution. Additionally, the sensitivity of these methods to kernel choice remains a critical area for further exploration.

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{khanna2021linear,
  author = {Rajiv Khanna and Michael W. Mahoney},
  title = {{On Linear Convergence of Weighted Kernel Herding}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=j8LbT44Vxx},
}
Figure