Quantifying the Empirical Wasserstein Distance to a Set of Measures: Beating the Curse of Dimensionality

Nian Si, Jose H. Blanchet, Soumyadip Ghosh, Mark S. SquillanteNeurIPS 2020 · OpenReview

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

Abstract

We consider the problem of estimating the Wasserstein distance between the empirical measure and a set of probability measures whose expectations over a class of functions (hypothesis class) are constrained. If this class is sufficiently rich to characterize a particular distribution (e.g., all Lipschitz functions), then our formulation recovers the Wasserstein distance to such a distribution. We establish a strong duality result that generalizes the celebrated Kantorovich-Rubinstein duality. We also show that our formulation can be used to beat the curse of dimensionality, which is well known to affect the rates of statistical convergence of the empirical Wasserstein distance. In particular, examples of infinite-dimensional hypothesis classes are presented, informed by a complex correlation structure, for which it is shown that the empirical Wasserstein distance to such classes converges to zero at the standard parametric rate. Our formulation provides insights that help clarify why, despite the curse of dimensionality, the Wasserstein distance enjoys favorable empirical performance across a wide range of statistical applications.
BibTeX
@inproceedings{si2020quantifying,
  author = {Nian Si and Jose H. Blanchet and Soumyadip Ghosh and Mark S. Squillante},
  title = {{Quantifying the Empirical Wasserstein Distance to a Set of Measures: Beating the Curse of Dimensionality}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=tACV7On7Lit},
}
Figure