Source-linked AI summary
Optimally-Weighted Herding is Bayesian Quadrature
Ferenc Huszár, David Duvenaud
TL;DR
The paper asks how deterministic herding for representing distributions relates to Bayesian quadrature for integral estimation. It links their sample-selection criteria and presents sequential Bayesian quadrature as an optimally weighted herding method; empirical results report superior convergence over herding and a bound on empirical error.
Problem
The paper examines how deterministic methods for selecting distribution-representative samples relate to Bayesian quadrature’s task of estimating integrals.
Source: §1 · p. 1Method
Results
The authors report that sequential Bayesian quadrature converges faster than herding and establish a bound on the empirical error of its estimate.
Source: §8 · p. 9Takeaways & Limitations
Bayesian quadrature’s weights yield a minimax-optimal weighted herding method that dominates uniformly weighted and other non-optimally weighted herding in convergence rate.
Source: §1 · p. 2The method’s kernel must represent the integrand functions being integrated, and herding convergence is sensitive to kernel width.
Source: §7.1 · p. 8
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
The paper addresses computing expectations over probability distributions and situates deterministic quasi-Monte Carlo methods as alternatives to random sampling. It connects kernel herding with Bayesian quadrature, then introduces sequential Bayesian quadrature and compares its convergence empirically.
1 INTRODUCTION
- The target task is computing expectations of functions over distributions, with the paper assuming the distribution is known analytically and the function can be evaluated at arbitrary locations.Examples include marginal distributions, predictions marginalized over parameters, and Bayes risk.Source: §1 · p. 1
- Quasi-Monte Carlo methods select deterministic pseudo-samples by minimizing discrepancy and, when applicable, can converge faster than random sampling’s typical O(1/√N) rate.The paper focuses on this deterministic sampling approach rather than MCMC, whose estimate’s convergence is hard to estimate.Source: §1 · p. 1
- Bayesian quadrature’s sample-selection criterion matches the kernel-herding MMD criterion, and its weights are minimax-optimal over functions in the kernel-defined Hilbert space.The paper consequently characterizes Bayesian quadrature as weighted kernel herding that dominates uniformly weighted and other non-optimally weighted herding in convergence rate.Source: §1 · p. 2
- Sequential Bayesian quadrature uses a greedy method linked to approximately submodular sample selection to choose locations with Bayesian quadrature weights.The paper relates this selection problem to sparse dictionary selection.Source: §1 · p. 2
- The paper reports that sequential Bayesian quadrature converges faster than O(1/N) in empirical comparisons with herding and i.i.d. random sampling.The comparison covers the relative performance of all three methods.Source: §1 · p. 2
2 HERDING
Herding generates pseudo-samples to represent a target distribution, then estimates integrals using their empirical mean. Its sample-selection objective uses maximum mean discrepancy, with convergence guarantees that depend on the setting.
2 HERDING
- Herding generates pseudo-samples so nonlinear moments match those of the target distribution, then estimates the integral with their empirical mean.The paper identifies Welling (2009) as introducing herding.Source: §2 · p. 2
2.1 Maximum Mean Discrepancy
- Maximum mean discrepancy measures distributional divergence over a function class, and herding greedily minimizes this discrepancy to select each next pseudo-sample.For unit-norm functions in an RKHS, MMD can be expressed using expectations of the associated kernel; under constant k(x, x), the selection objective favors high target mass and discourages points near existing samples.Source: §2.1 · pp. 2–3
2.2 Complexity and Convergence Rates
- Evaluating the herding criterion requires integrating the kernel against the target distribution, which the paper assumes can be done in closed form.With O(n) criterion evaluation and O(1) optimization per step, producing N samples costs O(N^2); fast MMD convergence is not guaranteed in infinite-dimensional RKHSs such as those for Gaussian kernels.Source: §2.1 · p. 3, §2.2 · p. 3
3 BAYESIAN QUADRATURE
Bayesian quadrature (BQ) estimates an integral from function evaluations using a Gaussian-process posterior, producing a weighted estimate rather than the equal-weight average used by Monte Carlo and herding. It selects sample locations by minimizing posterior variance, with a greedy sequential method called SBQ.
3.1 BQ Estimator
- The posterior mean of the integral is the optimal Bayesian estimator under squared loss, and the Gaussian-process posterior makes it a linear combination of observed function values.The paper assumes a zero-mean GP prior with kernel function k.Source: §3.1 · pp. 3–4
- BQ is a weighted version of herding, and its optimal weights need not be positive or sum to one.This differs from approaches that assume or enforce weights form a probability distribution.Source: §3.1 · p. 4, §3.1.1 · p. 4
3.1.1 Non-normalized and Negative Weights
- A representative set of 100 BQ weights on samples representing Figure 1’s distribution includes several negative weights and sums to 0.93; Figure 3 shows these weights after 100 SBQ samples were selected.Source: §3.1.1 · p. 4, Figure 3 · p. 4
- With few samples, Bayesian weights shrink toward zero; Monte Carlo and herding weights do not show this shrinkage.The illustrated case uses a kernel width approximately 1/20 the distribution width and a zero-mean function prior.Source: Figure 4 · p. 4, §3.1.1 · p. 4
3.2 Optimal sampling for BQ
- BQ selects sample locations by minimizing the posterior variance of the integral, which depends on sample locations rather than observed function values.This allows optimal locations to be computed before observing f.Source: §3.2 · p. 5
- SBQ greedily minimizes that variance one sample at a time, trading off target-distribution density against sample diversity.With incremental Cholesky updates, the criterion takes O(n^2) time to evaluate and selecting N samples takes O(N^3), assuming O(1)-time optimization.Source: §3.2 · p. 5
4 RELATING V [Zf,p] TO MMD
The section relates Bayesian quadrature's posterior-variance criterion to the maximum mean discrepancy minimized by kernel herding. This gives BQ a Bayesian interpretation and a frequentist minimax interpretation in an RKHS.
4 RELATING V [Zf,p] TO MMD
- The BQ posterior mean is a Bayes estimator with minimum expected squared error, which the section uses to rewrite the criterion in minimax forms.The proof invokes the representer theorem and properties of a standard Gaussian process.Source: §4 · p. 5
- BQ minimizes the same objective as kernel herding, but replaces uniform sample weights with optimal weights.The section identifies the expected BQ variance with the MMD criterion.Source: §4 · p. 5
- The criterion has both a Bayesian interpretation as posterior variance and a frequentist interpretation as a minimax bound on RKHS estimation error.Source: §4 · p. 5
5 SUBMODULARITY
Sequential Bayesian quadrature (sbq) is approximately, rather than exactly, submodular because its objective connects to sparse dictionary selection. This weaker property supports a limited greedy-performance guarantee.
5 SUBMODULARITY
- Submodularity is a diminishing-returns property, for which greedy maximization has a constant-factor guarantee of (1 − 1/e); sbq has only the weaker approximate property.Source: §5 · p. 6
- Sbq is approximately submodular because its objective is identical to the sparse dictionary selection problem, although neither herding nor Bayesian quadrature satisfies all conditions for submodularity.The paper uses this connection to reason about greedy forward selection for sbq.Source: §5 · p. 6
- The Bayesian quadrature objective is weakly submodular with constant ε < 4r, where r is the kernel incoherency.Source: §5 · p. 6
- Weak submodularity does not give strong near-optimality guarantees, and the guarantee is very weak here because the objective is upper-bounded by a constant.The sparse-dictionary connection may nevertheless open directions for applying related algorithms and theory to kernel-based quasi-Monte Carlo methods.Source: §5 · p. 6
6 EXPERIMENTS
Across the experiments, sequential Bayesian quadrature (sbq) outperforms herding in matching the target distribution, and its empirical integral-error behavior is examined both within and outside the assumed RKHS. The experiments use a shared two-dimensional mixture-of-Gaussians target and compare against the herding setup of Chen et al. (2010).
6 EXPERIMENTS
- The experiments use a two-dimensional mixture of 20 Gaussians and a target distribution and kernel matching Chen et al. (2010, Fig. 1).Each sequential method selects the next location from a pool of 10,000 candidates randomly drawn from the base distribution.Source: §6 · p. 6
6.1 Matching a distribution
- Sbq dominates herding in MMD across the tested sample counts, and appears to converge faster than O(1/N), although the rate is unknown.Eight sbq samples with quadrature weights attain the same expected loss as 20 uniformly weighted herding samples.Source: §6.1 · pp. 6–7, Figure 5 · p. 7
- Reweighting herding samples with Bayesian quadrature weights initially performs similarly to sbq, but sbq achieves a better convergence rate as sample count increases.The authors attribute the increased rate to sbq's different sample locations, not only its weights.Source: §6.1 · p. 7
6.2 Estimating Integrals
- For functions in the kernel-defined RKHS unit ball, empirical integral-error rates appear similar to the MMD rates.The reported within-model empirical error is averaged over 250 functions drawn from that RKHS.Source: §6.2 · p. 7, Figure 6 · p. 7
- MMD provides an upper bound on sbq's integral-estimation error for functions in the RKHS unit ball, and the bound decreases quickly in the reported experiment.Source: §6.2 · p. 7, Figure 7 · p. 8
6.3 Out-of-model performance
- On functions drawn outside the assumed RKHS, the relative performance of the methods remains similar.The tested functions include narrow bumps and ridges not well modeled by the assumed isotropic kernel.Source: §6.3 · pp. 7–8
7 DISCUSSION
Kernel choice determines the scope and speed of convergence, while Bayesian quadrature’s computational cost grows faster with sample count than herding or Monte Carlo sampling. The accuracy–cost trade-off can favor sequential Bayesian quadrature when it needs fewer samples to reach a given accuracy.
7.1 Choice of Kernel
- With a characteristic kernel, MMD convergence implies convergence for any bounded measurable function, but may be slower than convergence within the kernel’s Hilbert space.Fast convergence for well-behaved functions can come at the expense of convergence outside that space.Source: §7.1 · p. 8
- Kernel choice must represent the integrands: herding convergence is sensitive to Gaussian-kernel width, and setting kernel parameters is difficult.The Bayesian interpretation offers a way to adapt the Hilbert space by fitting kernel parameters through Gaussian-process marginal likelihood.Source: §7.1 · p. 8
7.2 Computational Complexity
- Bayesian quadrature weights cost O(N^3) to compute, or O(N^2) per added sample; herding costs O(N) per sample and Monte Carlo O(1).The O(N^3) cost for Bayesian quadrature comes from inverting the Gram matrix; the incremental cost uses the Woodbury identity.Source: §7.2 · p. 8
- Sequential Bayesian quadrature may offset its higher computational cost by needing fewer samples for the same accuracy, and methods may be switched as sample counts grow.Table 1 compares convergence rates and computational complexity across the methods.Source: §7.2 · p. 9, Table 1 · p. 9
8 CONCLUSIONS
The conclusions connect kernel herding’s sample-selection loss to Bayesian quadrature’s, making sequential Bayesian quadrature an optimally weighted form of herding. They also report approximate submodularity, faster empirical convergence for SBQ than herding, and a bound on Bayesian quadrature’s empirical error.
8 CONCLUSIONS
- Kernel herding’s sample-selection loss is closely related to Bayesian quadrature’s, so sequential Bayesian quadrature is an optimally weighted version of herding.Source: §8 · p. 9
- Bayesian quadrature’s sample-selection loss is approximately submodular, connecting it to the dictionary-selection problem of Krause & Cevher (2010).Source: §8 · p. 9
- SBQ empirically achieves a faster convergence rate than herding, and the paper establishes a bound on Bayesian quadrature’s empirical error.Source: §8 · p. 9
8.1 Future Work
- Approximate submodularity gives only weak sub-optimality guarantees, motivating further study of links to dictionary selection for practical or theoretical developments.Source: §8.1 · p. 9