A Higher-Order Kolmogorov-Smirnov Test

Veeranjaneyulu Sadhanala, Yu-Xiang Wang, Aaditya Ramdas, Ryan J. Tibshirani
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:2621-2630, 2019.

Abstract

We present an extension of the Kolmogorov-Smirnov (KS) two-sample test, which can be more sensitive to differences in the tails. Our test statistic is an integral probability metric (IPM) defined over a higher-order total variation ball, recovering the original KS test as its simplest case. We give an exact representer result for our IPM, which generalizes the fact that the original KS test statistic can be expressed in equivalent variational and CDF forms. For small enough orders $(k \le 5)$, we develop a linear-time algorithm for computing our higher-order KS test statistic; for all others $(k \ge 6)$, we give a nearly linear-time approximation. We derive the asymptotic null distribution for our test, and show that our nearly linear-time approximation shares the same asymptotic null. Lastly, we complement our theory with numerical studies.

Cite this Paper

BibTeX
@InProceedings{pmlr-v89-sadhanala19a, title = {A Higher-Order Kolmogorov-Smirnov Test}, author = {Sadhanala, Veeranjaneyulu and Wang, Yu-Xiang and Ramdas, Aaditya and Tibshirani, Ryan J.}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {2621--2630}, 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/sadhanala19a/sadhanala19a.pdf}, url = {https://proceedings.mlr.press/v89/sadhanala19a.html}, abstract = {We present an extension of the Kolmogorov-Smirnov (KS) two-sample test, which can be more sensitive to differences in the tails. Our test statistic is an integral probability metric (IPM) defined over a higher-order total variation ball, recovering the original KS test as its simplest case. We give an exact representer result for our IPM, which generalizes the fact that the original KS test statistic can be expressed in equivalent variational and CDF forms. For small enough orders $(k \le 5)$, we develop a linear-time algorithm for computing our higher-order KS test statistic; for all others $(k \ge 6)$, we give a nearly linear-time approximation. We derive the asymptotic null distribution for our test, and show that our nearly linear-time approximation shares the same asymptotic null. Lastly, we complement our theory with numerical studies.} }
Endnote
%0 Conference Paper %T A Higher-Order Kolmogorov-Smirnov Test %A Veeranjaneyulu Sadhanala %A Yu-Xiang Wang %A Aaditya Ramdas %A Ryan J. Tibshirani %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-sadhanala19a %I PMLR %P 2621--2630 %U https://proceedings.mlr.press/v89/sadhanala19a.html %V 89 %X We present an extension of the Kolmogorov-Smirnov (KS) two-sample test, which can be more sensitive to differences in the tails. Our test statistic is an integral probability metric (IPM) defined over a higher-order total variation ball, recovering the original KS test as its simplest case. We give an exact representer result for our IPM, which generalizes the fact that the original KS test statistic can be expressed in equivalent variational and CDF forms. For small enough orders $(k \le 5)$, we develop a linear-time algorithm for computing our higher-order KS test statistic; for all others $(k \ge 6)$, we give a nearly linear-time approximation. We derive the asymptotic null distribution for our test, and show that our nearly linear-time approximation shares the same asymptotic null. Lastly, we complement our theory with numerical studies.
APA
Sadhanala, V., Wang, Y., Ramdas, A. & Tibshirani, R.J.. (2019). A Higher-Order Kolmogorov-Smirnov Test. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:2621-2630 Available from https://proceedings.mlr.press/v89/sadhanala19a.html.

Related Material