Universal Hypothesis Testing with Kernels: Asymptotically Optimal Tests for Goodness of Fit

Shengyu Zhu, Biao Chen, Pengfei Yang, Zhitang Chen
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:1544-1553, 2019.

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 $\mathbb R^d$, 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v89-zhu19b, title = {Universal Hypothesis Testing with Kernels: Asymptotically Optimal Tests for Goodness of Fit}, author = {Zhu, Shengyu and Chen, Biao and Yang, Pengfei and Chen, Zhitang}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {1544--1553}, year = {2019}, editor = {Chaudhuri, Kamalika and Sugiyama, Masashi}, volume = {89}, series = {Proceedings of Machine Learning Research}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/zhu19b/zhu19b.pdf}, url = {https://proceedings.mlr.press/v89/zhu19b.html}, 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 $\mathbb R^d$, 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.} }
Endnote
%0 Conference Paper %T Universal Hypothesis Testing with Kernels: Asymptotically Optimal Tests for Goodness of Fit %A Shengyu Zhu %A Biao Chen %A Pengfei Yang %A Zhitang Chen %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-zhu19b %I PMLR %P 1544--1553 %U https://proceedings.mlr.press/v89/zhu19b.html %V 89 %X 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 $\mathbb R^d$, 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.
APA
Zhu, S., Chen, B., Yang, P. & Chen, Z.. (2019). Universal Hypothesis Testing with Kernels: Asymptotically Optimal Tests for Goodness of Fit. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:1544-1553 Available from https://proceedings.mlr.press/v89/zhu19b.html.

Related Material