Universal Hypothesis Testing with Kernels: Asymptotically Optimal Tests for Goodness of Fit.

We characterize the asymptotic performance of nonparametric goodness of fittesting, otherwise known as the universal hypothesis testing that dates back toHoeffding (1965). The exponential decay rate of the type-II error probabilityis used as the asymptotic performance metric, hence an optimal test achievesthe maximum decay rate subject to a constant level constraint on the type-Ierror probability. We show that two classes of Maximum Mean Discrepancy (MMD)based tests attain this optimality on $\mathbb R^d$, while a Kernel SteinDiscrepancy (KSD) based test achieves a weaker one under this criterion. In thefinite sample regime, these tests have similar statistical performance in ourexperiments, while the KSD based test is more computationally efficient. Key toour approach are Sanov's theorem from large deviation theory and recent resultson the weak convergence properties of the MMD and KSD.