A Fast Proximal Point Method for Computing Exact Wasserstein Distance
arXiv:1802.04307
Abstract
Wasserstein distance plays increasingly important roles in machine learning, stochastic programming and image processing. Major efforts have been under way to address its high computational complexity, some leading to approximate or regularized variations such as Sinkhorn distance. However, as we will demonstrate, regularized variations with large regularization parameter will degradate the performance in several important machine learning applications, and small regularization parameter will fail due to numerical stability issues with existing algorithms. We address this challenge by developing an Inexact Proximal point method for exact Optimal Transport problem (IPOT) with the proximal operator approximately evaluated at each iteration using projections to the probability simplex. The algorithm (a) converges to exact Wasserstein distance with theoretical guarantee and robust regularization parameter selection, (b) alleviates numerical stability issue, (c) has similar computational complexity to Sinkhorn, and (d) avoids the shrinking problem when apply to generative models. Furthermore, a new algorithm is proposed based on IPOT to obtain sharper Wasserstein barycenter.
References in corpus (2)
Cited by in corpus (24)
- ViLT: Vision-and-Language Transformer Without Convolution or Region Supervision
- Improving Cross-lingual Information Retrieval on Low-Resource Languages via Optimal Transport Distillation
- UFO: A UniFied TransfOrmer for Vision-Language Representation Learning
- Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey
- Towards Mitigating Dimensional Collapse of Representations in Collaborative Filtering
- A Fast Globally Linearly Convergent Algorithm for the Computation of Wasserstein Barycenters
- Probing Inter-modality: Visual Parsing with Self-Attention for Vision-Language Pre-training
- Weakly supervised cross-domain alignment with optimal transport
- Graph Matching Optimization Network for Point Cloud Registration
- Learning High Dimensional Wasserstein Geodesics
- Randomised Wasserstein Barycenter Computation: Resampling with Statistical Guarantees
- CPOT: Channel Pruning via Optimal Transport
- Unbalanced Optimal Transport through Non-negative Penalized Linear Regression
- Neural Monge Map estimation and its applications
- Representation Transfer by Optimal Transport
- Fast Topological Clustering with Wasserstein Distance
- Low-rank Matrix Recovery With Unknown Correspondence
- Learning Graphons via Structured Gromov-Wasserstein Barycenters
- Sampling-Based Methods for Multi-Block Optimization Problems over Transport Polytopes
- An efficient implementable inexact entropic proximal point algorithm for a class of linear programming problems
- Multiview Sensing With Unknown Permutations: An Optimal Transport Approach
- Low-Rank Sinkhorn Factorization
- Probabilistic Metric Learning with Adaptive Margin for Top-K Recommendation
- JointGT: Graph-Text Joint Representation Learning for Text Generation from Knowledge Graphs