A Fast Proximal Point Method for Computing Exact Wasserstein Distance

Yujia Xie, Xiangfeng Wang, Ruijia Wang, Hongyuan ZhaUAI 2019 · OpenReview

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. While the Sinkhorn algorithm provides a fast approximation, it introduces entropic bias and numerical instability. This paper presents IPOT (Inexact Proximal point method for exact Optimal Transport), which achieves linear convergence to the exact Wasserstein distance with $O(n^2)$ complexity per iteration. By utilizing a proximal point framework with a single inner iteration, IPOT maintains the efficiency of Sinkhorn while eliminating its inherent "blurring" bias.

Introduction

The Wasserstein distance (or Optimal Transport distance) is a powerful metric for comparing probability distributions, but it faces significant computational challenges. Traditional linear programming solvers for exact OT scale at $O(n^3 \log n)$, which is prohibitive for large-scale machine learning. To address this, researchers often use the Sinkhorn algorithm, which adds an entropy regularization term to the OT objective. While this reduces complexity to $O(n^2)$, it creates a fundamental trade-off: large regularization leads to "blurry" (biased) results, while small regularization causes numerical underflow. The authors of this paper aim to bridge this gap by providing an exact solution with the speed and scalability of the Sinkhorn method.

The IPOT Algorithm

The proposed Inexact Proximal point method for exact Optimal Transport (IPOT) solves the original OT problem by iteratively solving a sequence of proximal sub-problems. Instead of solving a single regularized problem, IPOT uses the previous estimate to regularize the current one using Bregman divergence (specifically, entropy-based).

Conceptual comparison of (a) Sinkhorn, (b) Exact proximal, and (c) Inexact proximal (IPOT) solutions.

A key innovation is the "inexact" approach: the algorithm converges even if only a single inner Sinkhorn iteration ($L=1$) is performed per outer proximal step. This keeps the per-iteration complexity at $O(n^2)$. Furthermore, IPOT is highly robust to the choice of the regularization parameter ($\beta$) and avoids the numerical stability issues that plague standard Sinkhorn implementations when the regularization is small.

Experimental Evaluation

The authors evaluated IPOT across synthetic distributions, high-dimensional data, and real-world datasets like MNIST and natural images. A primary advantage of IPOT is its ability to avoid the "shrinkage" problem in generative models like WGANs, where entropic bias can cause the learned distribution to fail to cover the full support of the target data.

Convergence of IPOT vs Sinkhorn. IPOT reaches exact solutions ($10^{-14}$ error) while Sinkhorn plateaus due to bias.

As shown in the convergence plots, IPOT demonstrates linear convergence to the exact Wasserstein distance, reaching a precision of $10^{-14}$. In contrast, the Sinkhorn method remains stuck at a biased error floor. Despite this increased accuracy, IPOT's computational time remains competitive with Sinkhorn and is significantly faster than "stabilized" Sinkhorn variants required for high-precision tasks.

Conclusion

IPOT provides a robust and efficient framework for computing the exact Wasserstein distance. By combining the proximal point method with an inexact inner solver, it achieves the accuracy of linear programming with the speed of entropic regularization. Qualitatively, this leads to sharper results in tasks such as color transfer and Wasserstein barycenter computation. Future work may focus on reducing memory requirements for large-scale barycenter problems.

Summary updated

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 complex...
BibTeX
@inproceedings{xie2019fast,
  author = {Yujia Xie and Xiangfeng Wang and Ruijia Wang and Hongyuan Zha},
  title = {{A Fast Proximal Point Method for Computing Exact Wasserstein Distance}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2019},
  url = {https://openreview.net/forum?id=s9rASiAGjU},
}
Figure