Sharp Rates of MMD Empirical Estimation with Power Kernels

Abstract

We establish quantitative rates of convergence for the empirical estimation of probability measures by means of the Maximum Mean Discrepancy (MMD) with power kernel $K_q(x,y)=-|x-y{|}^q$, $q\in (0,2)$. The resulting discrepancy is the classical \emph{energy distance} $${\mathcal{E}}_q^2(\hat{I}¼,\ddot{I}‰)=-\frac{1}{2}{\iint }_{{\mathbb{R}}^d\times {\mathbb{R}}^d}|x-y{|}^{q}d(\hat{I}¼-\ddot{I}‰)(x)d(\hat{I}¼-\ddot{I}‰)(y),$$ and we ask how fast the best $N$-point empirical approximation ${\inf }_{\hat{I}{¼}_N\in {\mathcal{P}}^N}{\mathcal{E}}_q(\hat{I}{¼}_N,\ddot{I}‰)$ decays as $N\to \infty$. Given a probability measure $\ddot{I}‰$ on ${\mathbb{R}}^d$ with compact support satisfying an Ahlfors regularity condition of exponent ${\hat{I}}^2\in (0,d]$, we prove that the sharp two-sided bound $${\mathcal{E}}_q(\hat{I}{¼}_N,\ddot{I}‰)\asymp N^{-\frac{1}{2}\left(1+{\frac{q}{\hat{I}}}^2\right)}$$ holds both for the worst-case empirical measure $\hat{I}{¼}_N$ (lower bound, holding for every configuration of $N$ points) and for an optimally chosen empirical measure $\hat{I}{¼}_N$ (upper bound). This complements the qualitative consistency result of Fornasier and Hütter \cite{fornasier2014consistency}, who proved narrow convergence of the minimizers of ${\mathcal{E}}_q^2(\cdot ,\ddot{I}‰)$ over empirical measures without quantitative rates.

References update and typos correction. Comments very welcome!