A Kernel Two Sample Test and Curse of Dimensionality

Question

Gretton et al describes the Kernel Maximum Mean Discrepancy, a measure of distance between distributions. In order to compare two distributions, it turns out you can do much better than, say, taking the L2 distance between density estimates. As explained in section 3.3.1, the latter approach suffers from curse of dimensionality, whereas their Kernel MMD does not.

I understand why density estimation in high dimensions is a very hard problem: you need more points in order to "fill up all the space." However, it is not clear to me why Kernel MMD does not also suffer in high dimensions. In fact, they show examples (e.g. Figure 5B) where it does better in high dimensions.

If you are using, say, a RBF Gaussian kernel with the Kernel MMD, why do you not suffer from curse of dimensionality? It is my understanding that in high dimensions, "all points are equally far from eachother," and since the Gaussian kernel is a function of Euclidean distance, why does its performance not degrade in high dimensions? Is it perhaps related to the "blessing of non-uniformity" referenced here?

To put it simply: why does the performance of Kernel MMD not suffer in high dimensions?

Answer 1

Just happen to see this post while going over MMD papers. In the context of two-sample testing and considering the test power under a given level, the answer is it does suffer from high dimension.

Previous experiment might be misleading because they did not select a fair alternative for testing. For example, consider $P=\mathcal N(0,I)$ and $Q=\mathcal N(\mu, I)$, so $P$ and $Q$ only differ in the mean vector. As dimension increases, you may pick $\mu=[1,0,0,\ldots,0]$ or $\mu=[1,1,1,\ldots,1]$. The latter is more easy to distinguish, which is the one selected in their experiments. The paper below fixes the Kullback-Leibler divergence between $P$ and $Q$ for all dimensions (for example, pick $\mu=[1,0,0,\ldots,0]$), guided by the fact that KLD usually acts as a quantity of how hard a hypothesis testing problem is in information theory. Then the test power is shown to decrease as dimension increases.

Also notice the above choice does not take into account the sample sizes. In fact, fixing the KLD is only a heuristic, stated by the authors. We have got a new result on this respect, to which I will post a link once a draft is complete. In summary, fixing the KLD is still a reasonable strategy for fair alternative.

Check this paper: "On the Decreasing Power of Kernel and Distance based Nonparametric Hypothesis Tests in High Dimensions"

Answer 2

Oh, of course the method strongly suffers from the curse of dimensionality. It's just that they derive their results under what essentially is a parametric alternative, hidden behind the RKHS notation and not made too explicit.

Indeed, motivated by exactly the same question as yours, Ery Arias-Castro, Bruno Pelletier and Venkatesh Saligrama recently wrote a paper demonstrating exactly this ("Remember the Curse of Dimensionality: The Case of Goodness-of-Fit Testing in Arbitrary Dimension", available on arXiv). You should read this for a more detailed answer.

Answer 3

I found the introduction of paper, "Can Shared-Neighbor Distances Defeat the Curse of Dimensionality" by Houle et al (2010) to be helpful. Particularly, they make the distinction between dimensions bearing relevant information and irrelevant information. For example, two Gaussian distribution clusters with separated means are more easily separated as dimension increases. On the other hand, if "irrelevant" features (e.g. pure noise) are added as additional dimensions, the separability will not be improved.

As such, it makes a great deal of sense that in Figure 5B in Gretton et al. (2012), the performance of the MMD improves when separating Gaussians in higher dimensions. Intuitively, since the Gaussians are "separate" on each new dimension, it can be thought of as "additional information" and hence, is helpful. If pure noise were added as additional dimensions, I would expect the performance of the MMD to decrease. Indeed, as @air's citation demonstrates, the MMD does suffer from the curse of dimensionality.

However, that does not mean that it is not vastly superior to density estimation in the high dimensional setting. Density estimation in high dimensions is a very hard problem. Below is a table quoted in Wasserman et al. 2006 (section 6.5) that shows sample size necessary to ensure a relative mean squared error of less than 0.1 at 0 when the density is Gaussian and the optimal bandwidth is chosen:

                                        

The sample size is increasing very quickly with dimension. This is because the L2 error converges as $O(n^{-4/(4+d)})$, when the optimal bandwidth is used, where d is the dimension. The point is that to do density estimation in high dimensions, you need huge samples.

My intuition is that as the number of dimensions increases, the "volume" of the space is increasing exponentially. And hence, if you are going to try and do density estimation by splitting the volume up into small hypercubes and count the number of points in each, you will need exponentially many hypercubes. Kernel MMD, on the other hand, is only looking at pairwise distance between points, and not integrating over the space in which the points lie. As such, it does not care if there is a huge volume of empty space. Of course, as dimensionality increases, all points become increasingly equidistant, and hence the performance of any metric-based method will degrade, but apparently this effect is not as dramatic.

One other point of confusion for me was that although Kernel MMD allows you to perform a two sample test without density estimation, in section 3.3.1, they show that the L2 distance between Parzen window density estimates is a special case of the MMD. So, clearly, if you choose a specific kernel they describe, then the kernel MMD is exactly doing density estimation, and hence, I presume, it will scale just as poorly with increasing dimension. Indeed, the kernel $k (x,y) =\int \kappa(x - z) \kappa(y-z) dz$ derived in 3.3.1, for which testing using the kernel MMD coincides with taking the L2 distance between density estimates, is integrating over the underlying space--just as in density estimation--unlike say, if a Gaussian RBF kernel were used instead.