Universal Hypothesis Testing with Kernels: Asymptotically Optimal Tests for Goodness of Fit
[edit]
Proceedings of Machine Learning Research, PMLR 89:15441553, 2019.
Abstract
We characterize the asymptotic performance of nonparametric goodness of fit testing. The exponential decay rate of the typeII error probability is used as the asymptotic performance metric, and a test is optimal if it achieves the maximum rate subject to a constant level constraint on the typeI error probability. We show that two classes of Maximum Mean Discrepancy (MMD) based tests attain this optimality on $\mathbb R^d$, while the quadratictime Kernel Stein Discrepancy (KSD) based tests achieve the maximum exponential decay rate under a relaxed level constraint. Under the same performance metric, we proceed to show that the quadratictime MMD based twosample tests are also optimal for general twosample problems, provided that kernels are bounded continuous and characteristic. Key to our approach are Sanov’s theorem from large deviation theory and the weak metrizable properties of the MMD and KSD.
Related Material


