Gaussian-Smoothed Optimal Transport: Metric Structure and Statistical Efficiency

Ziv Goldfeld, Kristjan H. Greenewald

Introduction

Optimal Transport (OT), particularly the 1-Wasserstein distance, has emerged as a cornerstone in machine learning for comparing probability distributions. Its ability to provide meaningful geometric distances between distributions with non-overlapping supports makes it invaluable for generative modeling (GANs), domain adaptation, and natural language processing.

However, standard OT suffers from a significant "curse of dimensionality." When estimating the distance between a true distribution and its empirical counterpart based on $n$ samples, the error scales as $O(n^{-1/d})$. In high-dimensional settings, such as image processing where $d$ can be thousands, this rate makes empirical estimates practically unusable. While entropic regularization (e.g., the Sinkhorn algorithm) mitigates this statistical hurdle, it does so at the cost of the underlying metric structure—violating the identity of indiscernibles and the triangle inequality.

Gaussian-Smoothed Optimal Transport (GOT)

To address these limitations, this research introduces Gaussian-Smoothed Optimal Transport (GOT). The approach is conceptually straightforward: before computing the 1-Wasserstein distance, both distributions $\mu$ and $\nu$ are convolved with an isotropic Gaussian kernel of variance $\sigma^2$. Mathematically, this is equivalent to comparing random variables after adding independent Gaussian noise:

$$W_1^{(\sigma)}(\mu, \nu) = W_1(\mu * G_\sigma, \nu * G_\sigma)$$

where $G_\sigma$ is the Gaussian density. This formulation allows the method to retain the geometric benefits of OT while gaining the statistical stability of smoothing.

Theoretical Advantages

Unlike entropic OT, GOT preserves the rigorous mathematical properties of a distance metric:

  1. Metricity: GOT satisfies the identity of indiscernibles, symmetry, and the triangle inequality.
  2. Weak Convergence: It metrizes the weak convergence of probability measures, ensuring that small changes in the distribution lead to small changes in the distance.
  3. Statistical Efficiency: The authors prove that for any $\sigma > 0$, the empirical approximation rate of GOT is $O(n^{-1/2})$, effectively bypassing the curse of dimensionality. Notably, this parametric rate holds for any subgaussian noise distribution, not just Gaussian.

Empirical Results

The authors validated their theoretical findings using synthetic data, drawing i.i.d. samples from a uniform distribution over a $d$-dimensional hypercube $[0,1]^d$. They employed a neural network-based dual optimization approach to estimate the distance, utilizing a gradient penalty to enforce the Lipschitz constraint required by the Kantorovich-Rubinstein duality.

Empirical convergence rates of GOT across dimensions $d=5, 10, 100$. For $\sigma > 0$, the error decays at a consistent $O(n^{-1/2})$ rate, whereas the standard Wasserstein distance ($\sigma=0$) slows significantly as $d$ increases.

As shown in the figure above, the standard Wasserstein distance ($\sigma=0$) exhibits a flattening slope as the dimension $d$ increases, illustrating the curse of dimensionality. In contrast, for any positive smoothing parameter $\sigma$, the convergence rate remains stable and follows the predicted $O(n^{-1/2})$ slope on the log-log plot across all tested dimensions ($d=5, 10, 100$).

Discussion and Limitations

While GOT offers significant theoretical advantages, its practical implementation via neural networks presents challenges. The dual formulation requires approximating a Lipschitz function, typically enforced via a Gradient Penalty. As the number of samples $n$ increases, the network must effectively overfit the empirical measure to maintain accuracy, which becomes increasingly difficult in high dimensions. Despite these implementation hurdles, the foundational theory suggests GOT is a viable drop-in replacement for entropic OT in large-scale applications like generative modeling.

Conclusion

Gaussian-Smoothed Optimal Transport provides a "best of both worlds" solution. It maintains the mathematical rigor of a true metric while offering the statistical efficiency needed for high-dimensional machine learning. By simply smoothing distributions with noise, GOT transforms a computationally and statistically difficult problem into one with a dimension-independent convergence rate.

Summary updated

Abstract

Optimal transport (OT), and in particular the Wasserstein distance, has seen a surge of interest and applications in machine learning. However, empirical approximation under Wasserstein distances suffers from a severe curse of dimensionality, rendering them impractical in high dimensions. As a result, entropically regularized OT has become a popular workaround. However, while it enjoys fast algorithms and better statistical properties, it looses the metric structure that Wasserstein distances enjoy. This work proposes a novel Gaussian-smoothed OT (GOT) framework, that achieves the best of both worlds: preserving the 1-Wasserstein metric structure while alleviating the empirical approximation curse of dimensionality. Furthermore, as the Gaussian-smoothing parameter shrinks to zero, GOT $Γ$-converges towards classic OT (with convergence of optimizers), thus serving as a natural extension. An empirical study that supports the theoretical results is provided, promoting Gaussian-smoothed OT as a powerful alternative to entropic OT.
BibTeX
@inproceedings{goldfeld2020gaussian,
  author = {Ziv Goldfeld and Kristjan H. Greenewald},
  title = {{Gaussian-Smoothed Optimal Transport: Metric Structure and Statistical Efficiency}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=Fxf7YSJf0N},
}
Figure