Minimax Estimation of Maximum Mean Discrepancy with Radial Kernels
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.
The paper deals with the estimation of Maximal Mean Discrepancy (MMD) with radial kernels from the minimax point of view.  It gives new lower bounds for the minimax probability, which coincide with the known upper bounds, up to multiplicative constants (depending on the properties of the kernel).  A first lower bound for Gaussian kernels is straightforwardly obtained from Le Cam's method, following the same arguments as Tolstikhin, Sriperumbudur and Muandet (2016), but this lower bound depend on the dimension of the data. A second lower bound is developed, not depending on this dimensionality parameter and generalized to radial kernels, based on classical arguments from the minimax theory for functionals (the two fuzzy hypotheses method, as named by Tsybakov (2008)).  This new lower bound enables to establish a classical minimax parametric rate of estimation of the MMD, and to prove that the empirical estimator and its $U$-statistic variant, used in the MMD two-sample tests for instance, are optimal in the presented minimax sense.
The paper is very interesting as it provides the first known lower bounds for the minimax rate of estimation of the MMD distance between two distributions based on finite random samples, considering general radial kernels, which match with the known upper bounds up to constants. Theses bounds lead to a classical parametric rate of estimation, not depending on the dimension of the data. The text could however be more fluent, and easier to read for nonspecialists of the minimax estimation theory. For instance, the results are all expressed with respect to the minimax probabilities. Could the link with the more classical minimax risk be clearly written ? Moreover, to my mind the only main drawback of this work is that it does not tackle the real target issue of minimax testing, which is usually closely related to the minimax estimation of functionals. The obtained parametric rate of estimation is indeed known to coincide with the parametric rates of testing when one considers weak distances (such as the Bounded Lipschitz or the MMD distances) between distributions. Finally, I noticed a few mistakes in the text (in (1) a absolute value bar is lacking, and $r_{n,m,k}(\mathcal{P})$ should be replaced by  $r_{n,m,k}(\mathcal{P})^{-1}$ in (2).