TY - JOUR
T1 - Asymptotically Optimal One-and Two-Sample Testing with Kernels
AU - Zhu, Shengyu
AU - Chen, Biao
AU - Chen, Zhitang
AU - Yang, Pengfei
N1 - Funding Information:
Manuscript received August 25, 2019; revised December 15, 2020; accepted January 24, 2021. Date of publication February 12, 2021; date of current version March 18, 2021. The work of Biao Chen was supported in part by the National Science Foundation under Grant CNS-1731237. This article was presented in part at the 2019 International Conference on Artificial Intelligence and Statistics (AISTATS). (Corresponding author: Shengyu Zhu.) Shengyu Zhu and Zhitang Chen are with Huawei Noah’s Ark Lab, Hong Kong (e-mail: szhu05@syr.edu; chenzhitang2@huawei.com). Biao Chen is with the Department of Electrical Engineering and Computer Science, Syracuse University, Syracuse, NY 13244 USA (e-mail: bichen@syr.edu). Pengfei Yang is with Point72 Asset Management, L.P., New York City, NY 10022 USA (e-mail: ypengf@gmail.com). Communicated by N. Merhav, Associate Editor for Shannon Theory. Color versions of one or more figures in this article are available at https://doi.org/10.1109/TIT.2021.3059267. Digital Object Identifier 10.1109/TIT.2021.3059267
Publisher Copyright:
© 1963-2012 IEEE.
PY - 2021/4
Y1 - 2021/4
N2 - 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 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.
AB - 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 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.
KW - Universal hypothesis testing
KW - error exponent
KW - kernel Stein discrepancy (KSD)
KW - large deviations
KW - maximum mean discrepancy (MMD)
UR - http://www.scopus.com/inward/record.url?scp=85101448564&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85101448564&partnerID=8YFLogxK
U2 - 10.1109/TIT.2021.3059267
DO - 10.1109/TIT.2021.3059267
M3 - Article
AN - SCOPUS:85101448564
SN - 0018-9448
VL - 67
SP - 2074
EP - 2092
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
IS - 4
M1 - 9354188
ER -