Executive Summary
The Wasserstein distance is a powerful metric for comparing probability distributions, but it is notoriously plagued by the "curse of dimensionality" in theoretical settings. This paper introduces a novel framework that calculates the Wasserstein distance between an empirical sample and a set of distributions defined by specific characteristics, known as a "hypothesis class." By focusing on relevant features rather than the entire distribution, the authors prove that the distance converges at a fast parametric rate, effectively bypassing the curse of dimensionality and explaining the metric's empirical success in high-dimensional applications.
The Curse of Dimensionality
The Wasserstein distance (often referred to as the "Earth Mover's Distance") has become a cornerstone in modern machine learning, particularly in Generative Adversarial Networks (GANs), image analysis, and operations research. Despite its practical success, it possesses a significant theoretical flaw: in high-dimensional spaces ($d$), the distance between an empirical sample of size $n$ and its true underlying distribution converges at a sluggish rate of $O(n^{-1/d})$.
This theoretical bound suggests that achieving an accurate estimate in a 20-dimensional space would require an astronomical dataset. Yet, in practice, Wasserstein-based models perform remarkably well with modest amounts of data. This paper seeks to resolve this discrepancy between pessimistic theory and successful practice.
Methodology: Distance to a Set of Measures
To bridge this gap, the authors propose a paradigm shift. Instead of measuring the distance to a single target distribution, they measure the distance to a set of measures that satisfy specific constraints, such as matching particular moments or expectations.
The technical foundation of this approach relies on several key contributions:
- A Generalized Duality Theorem: The authors establish a strong duality result that generalizes the celebrated Kantorovich-Rubinstein duality. This transforms a complex optimization problem over probability measures into a more tractable "supremum" problem over a class of functions.
- The Hypothesis Class ($\mathcal{B}$): This class represents a set of functions defining the characteristics that are actually relevant to the task at hand (e.g., specific structural features of an image), allowing the model to ignore irrelevant background noise.
- The $c$-transform: A mathematical transformation is utilized to handle the cost function within the dual formulation, ensuring computational feasibility.
- Function Approximation: For numerical implementation, the authors employ Marr wavelet basis functions to approximate infinite-dimensional hypothesis classes.
Experimental Validation
Because the paper focuses on foundational theory, it evaluates the framework using synthetic datasets rather than standard large-scale benchmarks like ImageNet. The primary experiment involves a 20-dimensional ($d=20$) problem where the target distribution is a mixture of four standard Gaussians. The model is tested on its ability to reject a "false" distribution (a Gaussian mixture with different centers) using extremely small sample sizes.
Key Findings and Insights
- Parametric Convergence: The most significant theoretical breakthrough is the proof that, for certain infinite-dimensional hypothesis classes, the empirical Wasserstein distance converges at a standard parametric rate of $O(n^{-1/2})$ or even $O(n^{-1})$. This holds regardless of the dimension $d$, effectively "curing" the curse of dimensionality.
- Relevance Over Completeness: The framework demonstrates that we rarely need a distribution to fit perfectly across every possible dimension. By projecting the empirical measure onto a set defined by the hypothesis class, the method isolates the signal from the noise.
- Remarkable Sample Efficiency: In the $d=20$ experiment, the method successfully distinguished between two distributions with a Type I error of 5% and a Type II error of 32% using only 25 samples. Under standard Wasserstein theory, 25 samples would be vastly insufficient to characterize a 20-dimensional space.
- Computational Tractability: The inner optimization is reduced to a $K$-dimensional problem (where $K$ is the number of projection directions) rather than a $d$-dimensional one, making it feasible on standard hardware.
Limitations and Future Directions
While the proposed framework offers a robust theoretical foundation, it comes with practical considerations:
- Selecting the Hypothesis Class: The success of the method is highly dependent on choosing an appropriate hypothesis class $\mathcal{B}$. If the class is too restrictive, critical information is lost; if it is too broad (e.g., encompassing all Lipschitz functions), the curse of dimensionality re-emerges.
- Compactness Constraints: The strongest duality results presented require the sample space to be compact (bounded). Extensions for non-compact spaces (like $\mathbb{R}^d$) are provided but must be handled on a case-by-case basis.
- Algorithmic Scaling: Although more efficient than standard methods, the numerical experiments still required Newton iterations and multiple restarts. Developing faster, "plug-and-play" algorithms for these projections remains an important area for future research.
Summary updated