Performance analysis of greedy algorithms for minimising a Maximum Mean Discrepancy
This work addresses the problem of efficient quantisation for researchers in machine learning and statistics, but it is incremental as it builds on existing methods with refined analysis.
The paper analyzes the performance of iterative algorithms like kernel herding, greedy MMD minimisation, and Sequential Bayesian Quadrature for quantising probability measures by minimising Maximum Mean Discrepancy, showing that the approximation error decreases as 1/n for all methods, with SBQ having a slightly better bound but the others being significantly faster with linear computational cost.
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.