Performance analysis of greedy algorithms for minimising a Maximum Mean Discrepancy

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 ke…