Asymptotically Optimal One- and Two-Sample Testing with Kernels
arXiv:1908.10037
Abstract
We characterize the asymptotic performance of nonparametric one- and two-sample testing. The exponential decay rate or error exponent of the type-II error probability is used as the asymptotic performance metric, and an optimal test achieves the maximum rate subject to a constant level constraint on the type-I error probability. With Sanov's theorem, we derive a sufficient condition for one-sample tests to achieve the optimal error exponent in the universal setting, i.e., for any distribution defining the alternative hypothesis. We then show that two classes of Maximum Mean Discrepancy (MMD) based tests attain the optimal type-II error exponent on , while the quadratic-time Kernel Stein Discrepancy (KSD) based tests achieve this optimality with an asymptotic level constraint. For general two-sample testing, however, Sanov's theorem is insufficient to obtain a similar sufficient condition. We proceed to establish an extended version of Sanov's theorem and derive an exact error exponent for the quadratic-time MMD based two-sample tests. The obtained error exponent is further shown to be optimal among all two-sample tests satisfying a given level constraint. Our work hence provides an achievability result for optimal nonparametric one- and two-sample testing in the universal setting. Application to off-line change detection and related issues are also discussed.
arXiv commentAccepted to IEEE Transactions on Information Theory. This version may be further modified
References in corpus (15)
- Rényi Divergence and Kullback-Leibler Divergence
- Estimating divergence functionals and the likelihood ratio by convex risk minimization
- Equivalence of distance-based and RKHS-based statistics in hypothesis testing
- MMD GAN: Towards Deeper Understanding of Moment Matching Network
- 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
- A Wild Bootstrap for Degenerate Kernel Tests
- On the Optimality of Kernel-Embedding Based Goodness-of-Fit Tests