Performance analysis of greedy algorithms for minimising a Maximum Mean Discrepancy. (arXiv:2101.07564v2 [stat.ML] UPDATED)

We analyse the performance of several iterative algorithms for the
quantisation of a probability measure $\mu$, 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 …

algorithms analysis arxiv mean ml performance performance analysis