Asymptotically Optimal One- and Two-Sample Testing With Kernels

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 Rd, while the quadratictime Kernel Stein Discrepancy (KSD) based tests achieve this optimality with an asymptotic level constraint. For general twosample 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 twosample tests satisfying a given level constraint. Our work hence provides an achievability result for optimal nonparametric oneand two-sample testing in the universal setting. Application to off-line change detection and related issues are also discussed.

Automated summary

This study characterizes the asymptotic performance of nonparametric one- and two-sample testing, focusing on optimal tests and error exponents. Sanov's theorem is used to derive sufficient conditions for achieving optimal error exponents in one-sample tests, while MMD and KSD based tests are shown to achieve optimal performance in specific conditions. An extended version of Sanov's theorem is established for general two-sample testing to derive tests with optimal error exponents under given constraints.