Two-sample Test using Projected Wasserstein Distance

Overview

• The researchers developed a method called "projected Wasserstein distance" to compare two sets of samples and determine if they come from the same distribution.
• This addresses a problem known as the "curse of dimensionality" - when dealing with high-dimensional data, standard distance metrics like Wasserstein distance become less effective at distinguishing differences between distributions.
• The key idea is to find a low-dimensional linear projection that maximizes the Wasserstein distance between the projected distributions, bypassing the challenges of high-dimensional spaces.
• The researchers provide theoretical analysis of the method's properties and practical algorithms for computing the metric, validating their results through numerical examples.

Plain English Explanation

Imagine you have two bags of marbles - one blue and one red. You want to know if the marbles in the two bags come from the same source, or if they are different. One way to do this would be to measure the size of each marble and compare the distributions (how the marble sizes are spread out) between the two bags.

This "distribution comparison" problem is fundamental in statistics and machine learning. A common way to measure the difference between distributions is called the Wasserstein distance. However, the Wasserstein distance becomes less effective when the marbles have many attributes (like color, shape, weight, etc.) - this is the "curse of dimensionality."

The researchers' key insight is to first find a simple, low-dimensional way to represent the marbles (like just focusing on size) that still captures the important differences between the two bags. By projecting the high-dimensional marble data onto this low-dimensional representation, they are able to better compare the distributions and determine if the marbles came from the same source.

The researchers provide a rigorous mathematical framework for this "projected Wasserstein distance" approach, along with efficient algorithms to compute it. They demonstrate through examples that this technique outperforms standard high-dimensional Wasserstein distance comparisons, especially for complex, high-dimensional data.

Technical Explanation

The researchers developed a novel "projected Wasserstein distance" for the two-sample testing problem. This involves finding an optimal low-dimensional linear projection that maximizes the Wasserstein distance between the projected probability distributions of the two input datasets.

The key technical contribution is a theoretical characterization of the finite-sample convergence rate of this projected Wasserstein distance. The researchers show that by coupling the optimal projection step with the Wasserstein distance, they are able to bypass the "curse of dimensionality" that plagues standard high-dimensional Wasserstein metrics.

Practically, the researchers provide algorithms to efficiently compute the projected Wasserstein distance. Through numerical experiments, they validate their theoretical results and demonstrate that the projected distance outperforms the standard Wasserstein distance, especially in high-dimensional settings.

Critical Analysis

The proposed projected Wasserstein distance addresses an important problem and provides a theoretically-grounded and empirically-validated solution. However, the paper does not explore the sensitivity of the method to the choice of the low-dimensional linear projection - it assumes an "optimal" projection is found, but the process of identifying this optimal projection is not discussed in depth.

Additionally, the paper focuses on the two-sample testing scenario, but many real-world applications may involve comparing more than two datasets at a time. It would be valuable to see an extension of the projected Wasserstein distance to the multi-sample case.

Finally, while the numerical examples validate the theoretical results, it would be helpful to see the projected Wasserstein distance applied to a broader range of real-world problems to better understand its practical advantages and limitations.

Conclusion

The researchers have developed a novel "projected Wasserstein distance" that can effectively compare high-dimensional probability distributions, overcoming the limitations of standard Wasserstein distance in such settings. This work advances the state-of-the-art in statistical and machine learning techniques for distribution comparison, with applications in areas like anomaly detection, domain adaptation, and generative modeling. By projecting the data to a low-dimensional space, the method provides a computationally efficient and theoretically-grounded approach to this fundamental problem.