On the High-dimensional Power of Linear-time Kernel Two-Sample Testing under Mean-difference Alternatives

By Aaditya Ramdas, Sashank J. Reddi, Barnab'as P'oczos, Aarti Singh, Larry A. Wasserman. 2014

9 citations recorded by the source corpus.

Nonparametric two sample testing deals with the question of consistently deciding if two distributions are different, given samples from both, without making any parametric assumptions about the form of the distributions. The current literature is split into two kinds of tests - those which are consistent without any assumptions about how the distributions may differ (\textit{general} alternatives), and those which are designed to specifically test easier alternatives, like a difference in means (\textit{mean-shift} alternatives). The main contribution of this paper is to explicitly characterize the power of a popular nonparametric two sample test, designed for general alternatives, under a mean-shift alternative in the high-dimensional setting. Specifically, we explicitly derive the power of the linear-time Maximum Mean Discrepancy statistic using the Gaussian kernel, where the dimension and sample size can both tend to infinity at any rate, and the two distributions differ in their means. As a corollary, we find that if the signal-to-noise ratio is held constant, then the test's power goes to one if the number of samples increases faster than the dimension increases. This is the first explicit power derivation for a general nonparametric test in the high-dimensional setting, and also the first analysis of how tests designed for general alternatives perform when faced with easier ones.

Subfields: Artificial Intelligence, Statistics and Probability, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Lawrence Carin
2. Chunyuan Li
3. Ricardo Henao
4. Yizhe Zhang
5. Dinghan Shen
6. Zhe Gan
7. Kai Fan
8. Zhi Chen

In Statistics and Probability

1. Zhe Gan
2. Lawrence Carin
3. Ricardo Henao
4. Kai Fan
5. Dinghan Shen
6. Zhi Chen
7. Yizhe Zhang
8. Chunyuan Li

In Statistical Learning Theory

1. Zhe Gan
2. Lawrence Carin
3. Kai Fan
4. Zhi Chen

Citations in the corpus

• Adversarial Feature Matching for Text Generation (2017, methodology): “In fact, a reliable Gaussian kernel MMD two-sample test generally requires the size of the minibatch to be proportional to the number of dimensions (Ramdas et al., 2014).”
• Wasserstein Generative Adversarial Networks (2017, unknown): “…as standard as 64 x 64 images, we would need minibatches of size at least 4096 (without taking into account the constants in the bounds of (Ramdas et al., 2014) which would make this number substantially larger) and a total cost per iteration of 4096 2 , over 5 orders of magnitude more…”