Skip to yearly menu bar Skip to main content


Minimax Estimation of Maximum Mean Discrepancy with Radial Kernels

Ilya Tolstikhin · Bharath Sriperumbudur · Bernhard Schölkopf

Area 5+6+7+8 #58

Keywords: [ Learning Theory ] [ (Other) Statistics ] [ Kernel Methods ]

Abstract: Maximum Mean Discrepancy (MMD) is a distance on the space of probability measures which has found numerous applications in machine learning and nonparametric testing. This distance is based on the notion of embedding probabilities in a reproducing kernel Hilbert space. In this paper, we present the first known lower bounds for the estimation of MMD based on finite samples. Our lower bounds hold for any radial universal kernel on $\R^d$ and match the existing upper bounds up to constants that depend only on the properties of the kernel. Using these lower bounds, we establish the minimax rate optimality of the empirical estimator and its $U$-statistic variant, which are usually employed in applications.

Live content is unavailable. Log in and register to view live content