# Performance analysis of greedy algorithms for minimising a Maximum Mean Discrepancy

arXiv: https://arxiv.org/abs/2101.07564 · HTML: https://mlsanity.com/paper/2101.07564/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 50 references that are in the map.
- First posted on arXiv 19 Jan 2021.

## Builds on (most cited first, 11 of 11)

- [Stein Variational Gradient Descent: A General Purpose Bayesian Inference Algorithm](https://mlsanity.com/paper/1608.04471/) (2016)
- [Coordinate Descent Algorithms](https://mlsanity.com/paper/1502.04759/) (2015)
- [Measuring Sample Quality with Kernels](https://mlsanity.com/paper/1703.01717/) (2017)
- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Control functionals for Monte Carlo integration](https://mlsanity.com/paper/1410.2392/) (2014)
- [A Stein variational Newton method](https://mlsanity.com/paper/1806.03085/) (2018)
- [Stein Points](https://mlsanity.com/paper/1803.10161/) (2018)
- [Support points](https://mlsanity.com/paper/1609.01811/) (2016)
- [Stein Point Markov Chain Monte Carlo](https://mlsanity.com/paper/1905.03673/) (2019)
- [Frank-Wolfe Bayesian Quadrature: Probabilistic Integration with Theoretical Guarantees](https://mlsanity.com/paper/1506.02681/) (2015)
- [Optimal quantisation of probability measures using maximum mean discrepancy](https://mlsanity.com/paper/2010.07064/) (2020)

## Built on by (most cited first, 7 of 7)

- [Biological Sequence Kernels with Guaranteed Flexibility](https://mlsanity.com/paper/2304.03775/) (2023)
- [Sparse solutions of the kernel herding algorithm by improved gradient approximation](https://mlsanity.com/paper/2105.07900/) (2021)
- [Enhancing Semi-Supervised Learning via Representative and Diverse Sample Selection](https://mlsanity.com/paper/2409.11653/) (2024)
- [Monte Carlo with kernel-based Gibbs measures: Guarantees for probabilistic herding](https://mlsanity.com/paper/2402.11736/) (2024)
- [Bayesian Quadrature](https://mlsanity.com/paper/2602.16218/) (2026)
- [EndoCIL: A Class-Incremental Learning Framework for Endoscopic Image Classification](https://mlsanity.com/paper/2510.17200/) (2025)
- [On the Optimisation Landscape of Overparameterised Weighted MMD](https://mlsanity.com/paper/2610.19861/) (2026)

## Abstract (arXiv)

We analyse the performance of several iterative algorithms for the quantisation of a probability measure μ, based on the minimisation of a Maximum Mean Discrepancy (MMD). Our analysis includes kernel herding, greedy MMD minimisation and Sequential Bayesian Quadrature (SBQ). We show that the finite-sample-size approximation error, measured by the MMD, decreases as 1/n for SBQ and also for kernel herding and greedy MMD minimisation when using a suitable step-size sequence. The upper bound on the approximation error is slightly better for SBQ, but the other methods are significantly faster, with a computational cost that increases only linearly with the number of points selected. This is illustrated by two numerical examples, with the target measure μ being uniform (a space-filling design application) and with μ a Gaussian mixture. They suggest that the bounds derived in the paper are overly pessimistic, in particular for SBQ. The sources of this pessimism are identified but seem difficult to counter.