Universal Hypothesis Testing with Kernels: Asymptotically Optimal Tests for Goodness of Fit
arXiv:1802.07581
Abstract
We characterize the asymptotic performance of nonparametric goodness of fit testing. The exponential decay rate of the type-II 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 type-I error probability. We show that two classes of Maximum Mean Discrepancy (MMD) based tests attain this optimality on , while the quadratic-time 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 quadratic-time MMD based two-sample tests are also optimal for general two-sample 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.
arXiv commentcamera-ready version for AISTATS 2019 (with supplementary material)
References in corpus (15)
- Rényi Divergence and Kullback-Leibler Divergence
- MMD GAN: Towards Deeper Understanding of Moment Matching Network
- Generative Moment Matching Networks
- Training generative neural networks via Maximum Mean Discrepancy optimization
- Generative Models and Model Criticism via Optimized Maximum Mean Discrepancy
- Measuring Sample Quality with Stein's Method
- A Kernel Test of Goodness of Fit
- Measuring Sample Quality with Kernels
- Fast Two-Sample Testing with Analytic Representations of Probability Measures
- Degenerate U- and V-statistics under weak dependence: Asymptotic theory and bootstrap consistency
- Universal and Composite Hypothesis Testing via Mismatched Divergence
- A Linear-Time Kernel Goodness-of-Fit Test
- On the optimal estimation of probability measures in weak and strong topologies
- Kernel Distribution Embeddings: Universal Kernels, Characteristic Kernels and Kernel Metrics on Distributions
- A Wild Bootstrap for Degenerate Kernel Tests