Minimax Estimation of Maximum Mean Discrepancy with Radial Kernels
Ilya O Tolstikhin, Bharath K. Sriperumbudur, Bernhard Schölkopf
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.
BibTeX
@inproceedings{NIPS2016_5055cbf4,
author = {Tolstikhin, Ilya O and Sriperumbudur, Bharath K. and Sch\"{o}lkopf, Bernhard},
booktitle = {Advances in Neural Information Processing Systems},
editor = {D. Lee and M. Sugiyama and U. Luxburg and I. Guyon and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Minimax Estimation of Maximum Mean Discrepancy with Radial Kernels},
url = {https://proceedings.neurips.cc/paper_files/paper/2016/file/5055cbf43fac3f7e2336b27310f0b9ef-Paper.pdf},
volume = {29},
year = {2016}
}