Smooth p-Wasserstein Distance: Structure, Empirical Approximation, and Statistical Applications

Sloan Nietert, Ziv Goldfeld, Kengo Kato

Overview

This paper provides a rigorous theoretical foundation for the Gaussian-smoothed $p$-Wasserstein distance ($W_p^{(\sigma)}$), proving that it overcomes the "curse of dimensionality" by achieving a parametric empirical convergence rate of $n^{-1/2}$ regardless of the dimension. By smoothing distributions with a Gaussian kernel, the authors create a distance measure that is both mathematically robust and statistically efficient for high-dimensional machine learning tasks like generative modeling and two-sample testing.

The Curse of Dimensionality in Optimal Transport

The Wasserstein distance ($W_p$) is a popular tool in machine learning for measuring the discrepancy between probability distributions, particularly in generative models like Wasserstein GANs (W-GANs). However, it suffers from a major flaw: the curse of dimensionality.

When estimating the standard Wasserstein distance from $n$ samples in $d$ dimensions, the error typically scales as $n^{-1/d}$. For high-dimensional data, such as images where $d$ can be in the thousands, an astronomical number of samples is required to achieve an accurate estimate. This paper investigates whether "smoothing" the distributions—blurring them slightly with Gaussian noise—can fix this scaling problem without losing the useful topological properties of the original Wasserstein distance.

Theoretical Framework: Gaussian-Smoothed Wasserstein Distance

The authors focus on the $\sigma$-smooth $p$-Wasserstein distance, defined as: $$W_p^{(\sigma)}(\mu, \nu) := W_p(\mu * \mathcal{N}_\sigma, \nu * \mathcal{N}_\sigma)$$ where $*$ denotes convolution and $\mathcal{N}_\sigma$ is an isotropic Gaussian kernel.

Key technical contributions include:

  • Structural Analysis: Proving that $W_p^{(\sigma)}$ is a true metric and induces the same topology as the standard Wasserstein distance.
  • Sobolev Comparison: To prove fast convergence, the authors introduce a new theoretical tool: a smooth $p$th-order Sobolev Integral Probability Metric (IPM), denoted as $d_p^{(\sigma)}$. They prove that $W_p^{(\sigma)}$ can be upper-bounded by this Sobolev distance.
  • Empirical Process Theory: By showing that the function class defining $d_p^{(\sigma)}$ is "Donsker," they prove the $n^{-1/2}$ convergence rate.
  • Efficient Computation for $p=2$: They demonstrate that for the quadratic case ($p=2$), the Sobolev proxy $d_2^{(\sigma)}$ can be computed efficiently as a Maximum Mean Discrepancy (MMD) with a specific reproducing kernel.

Key Insights: Beating the Curse

The most significant breakthrough is that smoothing allows for a parametric convergence rate ($n^{-1/2}$). This means the number of samples needed for a good estimate does not explode as the dimension increases, which is a game-changer for high-dimensional statistics.

Furthermore, the smoothed distance is highly stable. Small changes in the smoothing parameter $\sigma$ lead to only small changes in the distance, and as $\sigma \to 0$, it recovers the standard Wasserstein distance. While the theory holds for any $p \ge 1$, the $p=2$ case is particularly attractive because it links back to MMDs, which are computationally much cheaper than solving optimal transport problems.

The authors note that while their Sobolev bound $d_p^{(\sigma)}$ is a powerful tool for proving rates, it can be quite loose in practice. Its primary value lies in providing the correct asymptotic scaling.

Empirical convergence of $W_2^{(\sigma)}$ and the loose but theoretically important Sobolev upper bound.

Statistical Applications

The theoretical guarantees of the smoothed Wasserstein distance translate directly into robust statistical applications:

  • Fast Convergence: The paper proves that $E[W_p^{(\sigma)}(\hat{\mu}_n, \mu)] = O(n^{-1/2})$ under mild sub-Gaussian conditions, a massive improvement over the $n^{-1/d}$ rate of the unsmoothed version.
  • Two-Sample Testing: The authors developed a bootstrap-based two-sample test using $W_p^{(\sigma)}$ that is asymptotically consistent. Experiments showed the test maintains the correct "false alarm" rate across different dimensions.
  • Generative Modeling: The authors established the consistency and parametric convergence rates for Minimum Smooth Wasserstein Estimation (M-SWE), providing a solid theoretical footing for using smoothed distances as loss functions in generative models.
Scatter plots showing the $n^{-1/2}$ convergence of estimation errors for a Gaussian mixture model using M-SWE.

Limitations and Future Directions

While $d_2^{(\sigma)}$ is easy to compute, calculating $W_p^{(\sigma)}$ itself still typically requires standard optimal transport solvers (like Sinkhorn), which can be computationally heavy. Finding more specialized algorithms that exploit the Gaussian kernel's structure remains an open challenge. Additionally, although the rate is $n^{-1/2}$, the constant factor in front of that rate still scales exponentially with dimension $d$. The authors hypothesize that this might be improved by assuming the data lies on a lower-dimensional manifold. Finally, exploring extreme cases where $\sigma \to \infty$ or $p \to \infty$ (which connects to differential privacy) presents exciting avenues for future research.

Summary updated

Abstract

Discrepancy measures between probability distributions, often termed statistical distances, are ubiquitous in probability theory, statistics and machine learning. To combat the curse of dimensional...
BibTeX
@inproceedings{nietert2021smooth,
  author = {Sloan Nietert and Ziv Goldfeld and Kengo Kato},
  title = {{Smooth p-Wasserstein Distance: Structure, Empirical Approximation, and Statistical Applications}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=JETf7wEcztN},
}
Figure