TL;DR
This paper introduces Gaussian-Smoothed Optimal Transport (GOT), a new framework that bridges the gap between the theoretical elegance of Wasserstein distances and the practical need for efficient, high-dimensional computation in machine learning. GOT preserves the desirable metric properties of Wasserstein distances while overcoming the "curse of dimensionality" that plagues their empirical approximation, offering a powerful alternative to existing methods like entropic regularization.
What Problem Does This Paper Address?
Optimal Transport (OT), particularly the 1-Wasserstein distance, is a powerful tool for comparing probability distributions, finding applications in areas like data clustering, density estimation, and generative models. The Wasserstein distance has several attractive properties: it metrizes weak convergence of probability measures and defines a natural interpolation between them. However, a major hurdle for its practical use in machine learning is the "curse of dimensionality." When approximating Wasserstein distances using empirical data (i.e., samples from the distributions), the accuracy degrades rapidly as the data dimension increases, making it infeasible for high-dimensional datasets common in modern ML.
Entropic regularization has emerged as a popular workaround, offering faster algorithms and better statistical properties in some regimes. However, this approach sacrifices the crucial metric structure of the original Wasserstein distance, leading to limitations in theoretical guarantees and desirable properties. This paper aims to reconcile these two worlds by proposing a method that retains the metric structure while mitigating the curse of dimensionality.
Methods
The core contribution is the introduction of Gaussian-Smoothed Optimal Transport (GOT). The GOT distance between two probability measures $\mu$ and $\nu$ is defined as the 1-Wasserstein distance between their Gaussian-smoothed versions: $W^{(\sigma)}(\mu, \nu) = W_1(\mu * N_\sigma, \nu * N_\sigma)$, where $N_\sigma$ is an isotropic Gaussian measure with variance $\sigma^2$. This is equivalent to adding Gaussian noise to the samples from $\mu$ and $\nu$ and then computing the 1-Wasserstein distance.
The authors then establish several key theoretical properties of GOT:
- Metric Properties: They prove that $W^{(\sigma)}$ is a metric on the space of probability measures, preserving the "identity of indiscernibles" property.
- Weak Topology Metrization: Similar to $W_1$, $W^{(\sigma)}$ also metrizes the weak topology, meaning convergence in $W^{(\sigma)}$ is equivalent to weak convergence of measures.
- Dependence on $\sigma$: They show that $W^{(\sigma)}$ is continuous and monotonically non-increasing with respect to the smoothing parameter $\sigma$. Crucially, as $\sigma$ approaches zero, $W^{(\sigma)}$ converges to the original $W_1$ distance, and the optimal transport plans also converge.
- Empirical Approximation: The paper demonstrates that GOT significantly alleviates the curse of dimensionality for empirical approximation. They show that the expected error $E[W^{(\sigma)}(\mu_n, \mu)]$ converges at a rate of $O(n^{-1/2})$ in all dimensions, regardless of the data dimension, where $\mu_n$ is the empirical measure. This is a substantial improvement over the $O(n^{-1/d})$ rate for vanilla $W_1$. This result is generalized to any $\sigma$-subgaussian noise distribution with a bounded and monotone density.
Datasets
Not discussed in the paper. The experiments use synthetic data generated from uniform distributions on $[0, 1]^d$ for $d=5$ and $d=10$.
Key Insights and Ideas
- Bridging the Gap: The most significant insight is the elegant solution of smoothing probability measures with Gaussian noise to achieve both metric structure and statistical efficiency. This elegantly combines the theoretical appeal of Wasserstein distances with the practical necessity of handling high-dimensional data.
- Curse of Dimensionality Mitigation: The $O(n^{-1/2})$ convergence rate for empirical approximation under GOT, independent of dimension, is a major breakthrough. This suggests that GOT can be a viable alternative for high-dimensional machine learning tasks where vanilla Wasserstein distances fail.
- Continuity and Convergence: The fact that GOT converges to the original Wasserstein distance as the smoothing parameter $\sigma$ goes to zero is crucial. It implies that GOT is a natural extension and provides a theoretical bridge between the smoothed and unsmoothed versions.
- Generalization Beyond Gaussian: While the framework is named "Gaussian-smoothed," the theoretical results for empirical approximation extend to any $\sigma$-subgaussian noise distribution with specific properties, highlighting the robustness of the core idea.
Key Results
- Metric Properties: $W^{(\sigma)}(\mu, \nu)$ is proven to be a metric on the space of probability measures.
- Weak Topology: $W^{(\sigma)}$ metrizes the weak topology, meaning convergence in $W^{(\sigma)}$ is equivalent to weak convergence.
- Convergence to $W_1$: $\lim_{\sigma \to 0} W^{(\sigma)}(\mu, \nu) = W_1(\mu, \nu)$. Optimal transport plans for $W^{(\sigma)}$ also converge to optimal plans for $W_1$ as $\sigma \to 0$.
- Empirical Approximation Rate: For K-subgaussian measures $\mu$, $E[W^{(\sigma)}(\mu_n, \mu)] \le C_{\sigma,d,K} n^{-1/2}$ in all dimensions $d$. This is a parametric rate, a significant improvement over the $O(n^{-1/d})$ rate for vanilla $W_1$.
- Empirical Validation: Numerical experiments show that GOT converges significantly faster than vanilla $W_1$ in log-log plots, especially for higher dimensions ($d=10$), supporting the theoretical findings.
Limitations and Future Work
- Computational Cost: While GOT offers theoretical advantages, the paper mentions that evaluating the 1-Wasserstein distance between smoothed measures still requires specialized algorithms. The authors used a neural network-based approach for their experiments, which can be computationally intensive.
- Algorithm Design: A key future direction highlighted is the design of efficient algorithms specifically tailored for GOT computation, leveraging its unique structure beyond general Wasserstein distance algorithms.
- Alternative Noise Models: Exploring and comparing alternative noise models beyond Gaussian smoothing is also suggested as a future research avenue.
- Non-isotropic Noise: The paper notes that extensions to non-isotropic noise are possible but not delved into.
Summary updated