Numerical Approximation of Gaussian-Smoothed Optimal Transport

Abstract

The Optimal Transport (OT) Distance, especially the Wasserstein distance, has important applications in statistics and machine learning. Though the optimal transport distance possesses many favorable properties, it is not widely applicable, especially in high dimensions, due to its computational cost and the "curse of dimensionality". In the past few years, the Sinkhorn Algorithm [Cuturi, 2013], which uses entropy regularization to relieve the computational burden, provides an efficient approximation of the optimal transport distances. Moreover, the recently proposed Gaussian-Smoothed Optimal Transport (GOT) framework by [Goldfeld and Greenewald, 2020] provides potential solution to alleviate the "curse of dimensionality". Furthermore, [Makkuva et al., 2020] proposed a new algorithm that uses the Input Convex Neural Network (ICNN) to represent the optimal transport map with the gradient of convex functions. Inspired by previous works, we addressed the characteristics of different approximation algorithms for Optimal Transport distances and proposed a multiple sampling scheme under the Gaussian-Smoothed Optimal Transport framework. The simulation study shows that the multiple sampling essentially leads to better representation of Gaussian smoothness, and thus provides more accurate approximation, especially in high dimensions. Finally, we proposed a derivation that transforms 2-Wasserstein distance into the mean-width of a convex hull under a specific pair of distribution classes, and thus allows the analytical computation of 2-Wasserstein distances. We further verified this analytical result by Monte-Carlo simulation.