Stationary MMD Points for Cubature
This work addresses a fundamental problem in cubature, data compression, and optimization by offering a computationally feasible approach with improved convergence rates, though it is incremental as it builds on existing MMD-based methods.
The paper tackles the problem of approximating a target probability distribution with a finite set of points by focusing on stationary points of the maximum mean discrepancy (MMD), which are easier to compute than global minima. It shows that these stationary points achieve super-convergence, with cubature error vanishing faster than the MMD for integrands in the reproducing kernel Hilbert space, and provides a practical method using discretised gradient flows with a non-asymptotic finite-particle error bound.
Approximation of a target probability distribution using a finite set of points is a problem of fundamental importance, arising in cubature, data compression, and optimisation. Several authors have proposed to select points by minimising a maximum mean discrepancy (MMD), but the non-convexity of this objective precludes global minimisation in general. Instead, we consider \emph{stationary} points of the MMD which, in contrast to points globally minimising the MMD, can be accurately computed. Our main theoretical contribution is the (perhaps surprising) result that, for integrands in the associated reproducing kernel Hilbert space, the cubature error of stationary MMD points vanishes \emph{faster} than the MMD. Motivated by this \emph{super-convergence} property, we consider discretised gradient flows as a practical strategy for computing stationary points of the MMD, presenting a refined convergence analysis that establishes a novel non-asymptotic finite-particle error bound, which may be of independent interest.