Permutation-Free Kernel Hypothesis Tests

Abstract: Kernel-based methods have become popular in recent years for solving nonparametric testing problems, such as two-sample and independence testing. However, the test statistics involved in these methods (such as kernel-MMD and HSIC) have intractable null distributions, as they are instances of degenerate U-statistics. Thus, in practice, we often have to resort to using permutation distributions to calibrate these tests, which involves recomputing the statistic several hundred times. While permutation tests ensure non-asymptotic validity, the increased computational costs can make them infeasible, especially in large-scale problems.

In this talk, I will introduce a modified class of kernel test statistics, based on the ideas of sample-splitting and studentization, which have a standard normal limiting null distribution in a wide range of scenarios. Due to the simple null distribution, the tests based on these statistics are easy to calibrate, and in particular, they do not need permutations. Compared to permutation tests, our tests achieve a hundred-fold reduction in computational cost at the price of a small loss in power.

This talk is based on joint work with Ilmun Kim and Aaditya Ramdas.

BIO: Shubhanshu Shekhar is an assistant professor in the EECS department at the University of Michigan. Prior to this, he was a postdoctoral researcher in the Statistics department at Carnegie Mellon University, and he obtained his PhD in Electrical Engineering from the University of California, San Diego. His research interests lie broadly in the areas of statistics and machine learning.