On the Decreasing Power of Kernel and Distance Based Nonparametric Hypothesis Tests in High Dimensions

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

215 citations recorded by the source corpus.

This paper is about two related decision theoretic problems, nonparametric two-sample testing and independence testing. There is a belief that two recently proposed solutions, based on kernels and distances between pairs of points, behave well in high-dimensional settings. We identify different sources of misconception that give rise to the above belief. Specifically, we differentiate the hardness of estimation of test statistics from the hardness of testing whether these statistics are zero or not, and explicitly discuss a notion of "fair" alternative hypotheses for these problems as dimension increases. We then demonstrate that the power of these tests actually drops polynomially with increasing dimension against fair alternatives. We end with some theoretical insights and shed light on the median heuristic for kernel bandwidth selection. Our work advances the current understanding of the power of modern nonparametric hypothesis tests in high dimensions.

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

In Statistics and Probability

In Statistical Learning Theory

Citations in the corpus

Kernel Mean Embedding of Distributions: A Review and Beyonds (2016, background): “Ramdas et al. (2015a) also demonstrates that the power of the kernel-based tests degrades with dimension.”
Failing Loudly: An Empirical Study of Methods for Detecting Dataset Shift (2018, methodology): “While off-the-shelf methods for kernel-based multivariate two-sample tests are appealing, they scale badly with dataset size and their statistical power is known to decay badly with high ambient dimension [37].”
Detecting and Correcting for Label Shift with Black Box Predictors (2018, background): “Per theory and experiments in (Ramdas et al., 2015) two-sample tests in high dimensions are exponentially harder.”
Interpretable Distribution Features with Maximum Testing Power (2016, background): “The performance of MMD-lin degrades quickly with increasing dimension, as expected from Ramdas et al. (2015).”
Bayesian Learning of Kernel Embeddings (2016, background): “Cases in which the median heuristic performs quite well and also cases in which it performs quite poorly are discussed in (Reddi et al., 2015; Ramdas et al., 2015).”
Minimax Estimation of Kernel Mean Embeddings (2016, background): “n of a Gaussian distribution, thereby establishing the minimax rate to be n−1/2. These results show that the empirical estimator—and other estimators we discussed above—of µP is minimax rate optimal. Ramdas et al. (2015, Corollary 1) derived a special case of (3) for the Gaussian kernel kby ignoring”
Adaptivity and Computation-Statistics Tradeoffs for Kernel and Distance based High Dimensional Two Sample Testing (2015, background): “It was proved in Reddi et al. [2015] that the power of the linear-time statistic is given by and hence its power in the low SNR regime is given by Φ √ n √ 8 d Ψ 2 in the (very very) high SNR regime of Ψ = ω ( √ d ) , its power does not suffer, and is exactly Φ( √ n Ψ / √ 8) like all the above…”
Fast Two-Sample Testing with Analytic Representations of Probability Measures (2015, methodology): “We want to apply Lemma 2 to the analytic function f = Λ P − Λ Q , with the measure µ = µ T i , to see that if P (cid:54) = Q then f (cid:54) = 0 a.s.”
Imitation Learning via Kernel Mean Embedding (2018, methodology): “However, rather than using the fixed values for the bandwidth parameters, we employed the median heuristics which is theoretically well justified (Schölkopf and Smola 2002; Ramdas et al. 2015).”
M-Statistic for Kernel Change-Point Detection (2015, methodology): “In the following examples, we use a Gaussian kernel: k(Y, Y 0) = exp kY Y 0k2/2 2 , where > 0 is the kernel bandwidth and we use the “median trick” [10, 8] to get the bandwidth which is estimated using the background data.”
A Lagrangian Perspective on Latent Variable Generative Models (2018, background): “, 2017) or cannot handle complex distributions in high dimensions (Ramdas et al., 2015).”
Multivariate Rank-Based Distribution-Free Nonparametric Testing Using Measure Transportation (2019, unknown): “[119] Ramdas, A.”
Parametric Adversarial Divergences are Good Task Losses for Generative Modeling (2017, background): “It was also shown theoretically in (Reddi et al., 2015) that the power of the MMD statistical test drops polynomially with increasing dimension.”
Learning the Stein Discrepancy for Training and Evaluating Energy-Based Models without Sampling (2020, methodology): “Unfortunately, it is known that methods based on distances and kernels quickly degrade in performance as dimension increases (Ramdas et al., 2015).”
On the High Dimensional Power of a Linear-Time Two Sample Test under Mean-shift Alternatives (2015, background): “Such behavior has already been noted (but not explained) in the experiments of Ramdas et al. (2015) and we will verify this carefully in our experiments section.”