Asymptotically Optimal One- and Two-Sample Testing With Kernels
Asymptotically Optimal One- and Two-Sample Testing With Kernels
复制标题
DOI：
10.1109/tit.2021.3059267
复制
发表时间：
2019-08
影响因子：
2.5
通讯作者：
Shengyu Zhu;Biao Chen;Zhitang Chen;Pengfei Yang
中科院分区：
文献类型：
--
作者：
Shengyu Zhu;Biao Chen;Zhitang Chen;Pengfei Yang
我们描述了非参数单样本和双样本检验的渐近性能。采用第二类错误概率的指数衰减率或误差指数作为渐近性能指标，在对第一类错误概率的恒定水平约束下，最优测试达到最大速率。利用Sanov定理，我们导出了在一般情况下，即对于定义备择假设的任何分布，单样本检验获得最优误差指数的一个充分条件。然后，我们证明了两类基于最大平均差异（MMD）的测试在$\mathbb R^{d}$上获得了最优的ii型误差指数，而基于二次核斯坦差异（KSD）的测试在渐近水平约束下实现了这一最优性。然而对于一般的两样本检验，Sanov定理不足以得到相似的充分条件。我们进一步建立了萨诺夫定理的扩展版本，并推导了基于二次时间MMD的两样本检验的精确误差指数。得到的误差指数在满足给定水平约束的所有两样本测试中是最优的。因此，我们的工作提供了一个可实现的结果，最优的非参数单样本和双样本测试在普遍设置。讨论了在离线变更检测中的应用及相关问题。
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 $\mathbb R^{d}$ , 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.