Numerical Approximation of Gaussian-Smoothed Optimal Transport

Loading...
Thumbnail Image

Date

2022

Journal Title

Journal ISSN

Volume Title

Repository Usage Stats

192
views
213
downloads

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.

Description

Provenance

Citation

Citation

Yang, Congwei (2022). Numerical Approximation of Gaussian-Smoothed Optimal Transport. Master's thesis, Duke University. Retrieved from https://hdl.handle.net/10161/25362.

Collections


Dukes student scholarship is made available to the public using a Creative Commons Attribution / Non-commercial / No derivative (CC-BY-NC-ND) license.