Optimally-Weighted Herding is Bayesian Quadrature

By Ferenc Huszár, David Kristjanson Duvenaud. 2012

114 citations recorded by the source corpus.

Herding and kernel herding are deterministic methods of choosing samples which summarise a probability distribution. A related task is choosing samples for estimating integrals using Bayesian quadrature. We show that the criterion minimised when selecting samples in kernel herding is equivalent to the posterior variance in Bayesian quadrature. We then show that sequential Bayesian quadrature can be viewed as a weighted version of kernel herding which achieves performance superior to any other weighted herding method. We demonstrate empirically a rate of convergence faster than O(1/N). Our results also imply an upper bound on the empirical error of the Bayesian quadrature estimate.

Subfields: Artificial Intelligence, Civil and Structural Engineering, Statistical and Nonlinear Physics, Probabilistic & Bayesian Methods

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Civil and Structural Engineering

In Statistical and Nonlinear Physics

In Probabilistic & Bayesian Methods

Citations in the corpus

Sequential Kernel Herding: Frank-Wolfe Optimization for Particle Filtering (2015, background): “See also Husz´ar and Duvenaud (2012) for an alternative approach with negative weights.”
Kernel Mean Embedding of Distributions: A Review and Beyonds (2016, methodology): “The effect of shrinkage in the context of kernel mean embedding has previously been observed in the experimental study of Huszar and Duvenaud (2012) that investigates the connection between kernel Herding and Bayesian quadrature.”
Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences (2018, background): “Another connection is between Bayesian quadrature [O’Hagan, 1991] and kernel herding [Chen et al., 2010], which are in fact equivalent approaches to numerical integration or deterministic sampling [Huszár and Duvenaud, 2012].”
Sparse Variational Inference: Bayesian Coresets from Scratch (2019, background): “Although the problem in finite-dimensions can be studied using well-known techniques from sparse regression, compressed sensing, random sketching, boosting, and greedy approximation [33–51], these projections incur an unknown error in the construction process in practice, and preclude asymptotic con”
On the Equivalence between Quadrature Rules and Random Features (2015, methodology): “For these problems, techniques based on positive deﬁnite kernels have emerged as having the potential to eﬃciently deal with these situations, and to improve over plain Monte-Carlo integration (O’Hagan, 1991; Rasmussen and Ghahramani, 2003; Husz´ar and Duvenaud, 2012; Oates and Girolami, 2015).”
Interpreting Black Box Predictions using Fisher Kernels (2018, methodology): “For the RKHS induced by the kernel H , we can equivalently re-write the cost function as [12, 2]: For a matrix A , the smallest (largest) k -sparse eigenvalues is min (max) of x (cid:62) Ax x (cid:62) x under the constraints (cid:107) x (cid:107) 0 ≤ k , and x (cid:54) = 0 .”
Black-box Importance Sampling (2016, background): “In the light of this, bound (7) is a form of the worse case bounds of the kernel-based quadrature rules (e.g., Chen et al., 2010; Bach, 2015; Huszár and Duvenaud, 2012; Niederreiter, 2010).”
Frank-Wolfe Bayesian Quadrature: Probabilistic Integration with Theoretical Guarantees (2015, methodology): “The posterior mean in BQ is a Bayes estimator and so the MMD takes a minimax form [16].”
Monte Carlo with determinantal point processes (2016, methodology): “There is empirical evidence [Huszár and Duvenaud, 2012] that the error EN (f) in Bayesian quadrature decreases faster than the Monte Carlo rate N−1/2.”